• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * libkmod - interface to kernel module operations
3  *
4  * Copyright (C) 2011-2013  ProFUSION embedded systems
5  *
6  * This library is free software; you can redistribute it and/or
7  * modify it under the terms of the GNU Lesser General Public
8  * License as published by the Free Software Foundation; either
9  * version 2.1 of the License, or (at your option) any later version.
10  *
11  * This library is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this library; if not, see <http://www.gnu.org/licenses/>.
18  */
19 
20 #include <arpa/inet.h>
21 #include <assert.h>
22 #include <errno.h>
23 #include <fnmatch.h>
24 #include <inttypes.h>
25 #include <stdio.h>
26 #include <stdlib.h>
27 #include <string.h>
28 
29 #include <shared/macro.h>
30 #include <shared/strbuf.h>
31 #include <shared/util.h>
32 
33 #include "libkmod-internal.h"
34 #include "libkmod-index.h"
35 
36 /* libkmod-index.c: module index file implementation
37  *
38  * Integers are stored as 32 bit unsigned in "network" order, i.e. MSB first.
39  * All files start with a magic number.
40  *
41  * Magic spells "BOOTFAST". Second one used on newer versioned binary files.
42  * #define INDEX_MAGIC_OLD 0xB007FA57
43  *
44  * We use a version string to keep track of changes to the binary format
45  * This is stored in the form: INDEX_MAJOR (hi) INDEX_MINOR (lo) just in
46  * case we ever decide to have minor changes that are not incompatible.
47  */
48 #define INDEX_MAGIC 0xB007F457
49 #define INDEX_VERSION_MAJOR 0x0002
50 #define INDEX_VERSION_MINOR 0x0001
51 #define INDEX_VERSION ((INDEX_VERSION_MAJOR<<16)|INDEX_VERSION_MINOR)
52 
53 /* The index file maps keys to values. Both keys and values are ASCII strings.
54  * Each key can have multiple values. Values are sorted by an integer priority.
55  *
56  * The reader also implements a wildcard search (including range expressions)
57  * where the keys in the index are treated as patterns.
58  * This feature is required for module aliases.
59  */
60 #define INDEX_CHILDMAX 128
61 
62 /* Disk format:
63  *
64  *  uint32_t magic = INDEX_MAGIC;
65  *  uint32_t version = INDEX_VERSION;
66  *  uint32_t root_offset;
67  *
68  *  (node_offset & INDEX_NODE_MASK) specifies the file offset of nodes:
69  *
70  *       char[] prefix; // nul terminated
71  *
72  *       char first;
73  *       char last;
74  *       uint32_t children[last - first + 1];
75  *
76  *       uint32_t value_count;
77  *       struct {
78  *           uint32_t priority;
79  *           char[] value; // nul terminated
80  *       } values[value_count];
81  *
82  *  (node_offset & INDEX_NODE_FLAGS) indicates which fields are present.
83  *  Empty prefixes are omitted, leaf nodes omit the three child-related fields.
84  *
85  *  This could be optimised further by adding a sparse child format
86  *  (indicated using a new flag).
87  *
88  *
89  * Implementation is based on a radix tree, or "trie".
90  * Each arc from parent to child is labelled with a character.
91  * Each path from the root represents a string.
92  *
93  * == Example strings ==
94  *
95  * ask
96  * ate
97  * on
98  * once
99  * one
100  *
101  * == Key ==
102  *  + Normal node
103  *  * Marked node, representing a key and it's values.
104  *
105  * +
106  * |-a-+-s-+-k-*
107  * |   |
108  * |   `-t-+-e-*
109  * |
110  * `-o-+-n-*-c-+-e-*
111  *         |
112  *         `-e-*
113  *
114  * Naive implementations tend to be very space inefficient; child pointers
115  * are stored in arrays indexed by character, but most child pointers are null.
116  *
117  * Our implementation uses a scheme described by Wikipedia as a Patrica trie,
118  *
119  *     "easiest to understand as a space-optimized trie where
120  *      each node with only one child is merged with its child"
121  *
122  * +
123  * |-a-+-sk-*
124  * |   |
125  * |   `-te-*
126  * |
127  * `-on-*-ce-*
128  *      |
129  *      `-e-*
130  *
131  * We still use arrays of child pointers indexed by a single character;
132  * the remaining characters of the label are stored as a "prefix" in the child.
133  *
134  * The paper describing the original Patrica trie works on individiual bits -
135  * each node has a maximum of two children, which increases space efficiency.
136  * However for this application it is simpler to use the ASCII character set.
137  * Since the index file is read-only, it can be compressed by omitting null
138  * child pointers at the start and end of arrays.
139  */
140 
141 /* Format of node offsets within index file */
142 enum node_offset {
143 	INDEX_NODE_FLAGS    = 0xF0000000, /* Flags in high nibble */
144 	INDEX_NODE_PREFIX   = 0x80000000,
145 	INDEX_NODE_VALUES = 0x40000000,
146 	INDEX_NODE_CHILDS   = 0x20000000,
147 
148 	INDEX_NODE_MASK     = 0x0FFFFFFF, /* Offset value */
149 };
150 
index_values_free(struct index_value * values)151 void index_values_free(struct index_value *values)
152 {
153 	while (values) {
154 		struct index_value *value = values;
155 
156 		values = value->next;
157 		free(value);
158 	}
159 }
160 
add_value(struct index_value ** values,const char * value,unsigned len,unsigned int priority)161 static int add_value(struct index_value **values,
162 		     const char *value, unsigned len, unsigned int priority)
163 {
164 	struct index_value *v;
165 
166 	/* find position to insert value */
167 	while (*values && (*values)->priority < priority)
168 		values = &(*values)->next;
169 
170 	v = malloc(sizeof(struct index_value) + len + 1);
171 	if (!v)
172 		return -1;
173 	v->next = *values;
174 	v->priority = priority;
175 	v->len = len;
176 	memcpy(v->value, value, len);
177 	v->value[len] = '\0';
178 	*values = v;
179 
180 	return 0;
181 }
182 
read_error(void)183 static void read_error(void)
184 {
185 	fatal("Module index: unexpected error: %s\n"
186 			"Try re-running depmod\n", errno ? strerror(errno) : "EOF");
187 }
188 
read_char(FILE * in)189 static int read_char(FILE *in)
190 {
191 	int ch;
192 
193 	errno = 0;
194 	ch = getc_unlocked(in);
195 	if (ch == EOF)
196 		read_error();
197 	return ch;
198 }
199 
read_long(FILE * in)200 static uint32_t read_long(FILE *in)
201 {
202 	uint32_t l;
203 
204 	errno = 0;
205 	if (fread(&l, sizeof(uint32_t), 1, in) != sizeof(uint32_t))
206 		read_error();
207 	return ntohl(l);
208 }
209 
buf_freadchars(struct strbuf * buf,FILE * in)210 static unsigned buf_freadchars(struct strbuf *buf, FILE *in)
211 {
212 	unsigned i = 0;
213 	int ch;
214 
215 	while ((ch = read_char(in))) {
216 		if (!strbuf_pushchar(buf, ch))
217 			break;
218 		i++;
219 	}
220 
221 	return i;
222 }
223 
224 /*
225  * Index file searching
226  */
227 struct index_node_f {
228 	FILE *file;
229 	char *prefix;		/* path compression */
230 	struct index_value *values;
231 	unsigned char first;	/* range of child nodes */
232 	unsigned char last;
233 	uint32_t children[0];
234 };
235 
index_read(FILE * in,uint32_t offset)236 static struct index_node_f *index_read(FILE *in, uint32_t offset)
237 {
238 	struct index_node_f *node;
239 	char *prefix;
240 	int i, child_count = 0;
241 
242 	if ((offset & INDEX_NODE_MASK) == 0)
243 		return NULL;
244 
245 	if (fseek(in, offset & INDEX_NODE_MASK, SEEK_SET) < 0)
246 		return NULL;
247 
248 	if (offset & INDEX_NODE_PREFIX) {
249 		struct strbuf buf;
250 		strbuf_init(&buf);
251 		buf_freadchars(&buf, in);
252 		prefix = strbuf_steal(&buf);
253 	} else
254 		prefix = NOFAIL(strdup(""));
255 
256 	if (offset & INDEX_NODE_CHILDS) {
257 		char first = read_char(in);
258 		char last = read_char(in);
259 		child_count = last - first + 1;
260 
261 		node = NOFAIL(malloc(sizeof(struct index_node_f) +
262 				     sizeof(uint32_t) * child_count));
263 
264 		node->first = first;
265 		node->last = last;
266 
267 		for (i = 0; i < child_count; i++)
268 			node->children[i] = read_long(in);
269 	} else {
270 		node = NOFAIL(malloc(sizeof(struct index_node_f)));
271 		node->first = INDEX_CHILDMAX;
272 		node->last = 0;
273 	}
274 
275 	node->values = NULL;
276 	if (offset & INDEX_NODE_VALUES) {
277 		int value_count;
278 		struct strbuf buf;
279 		const char *value;
280 		unsigned int priority;
281 
282 		value_count = read_long(in);
283 
284 		strbuf_init(&buf);
285 		while (value_count--) {
286 			priority = read_long(in);
287 			buf_freadchars(&buf, in);
288 			value = strbuf_str(&buf);
289 			add_value(&node->values, value, buf.used, priority);
290 			strbuf_clear(&buf);
291 		}
292 		strbuf_release(&buf);
293 	}
294 
295 	node->prefix = prefix;
296 	node->file = in;
297 	return node;
298 }
299 
index_close(struct index_node_f * node)300 static void index_close(struct index_node_f *node)
301 {
302 	free(node->prefix);
303 	index_values_free(node->values);
304 	free(node);
305 }
306 
307 struct index_file {
308 	FILE *file;
309 	uint32_t root_offset;
310 };
311 
index_file_open(const char * filename)312 struct index_file *index_file_open(const char *filename)
313 {
314 	FILE *file;
315 	uint32_t magic, version;
316 	struct index_file *new;
317 
318 	file = fopen(filename, "re");
319 	if (!file)
320 		return NULL;
321 	errno = EINVAL;
322 
323 	magic = read_long(file);
324 	if (magic != INDEX_MAGIC) {
325 		fclose(file);
326 		return NULL;
327 	}
328 
329 	version = read_long(file);
330 	if (version >> 16 != INDEX_VERSION_MAJOR) {
331 		fclose(file);
332 		return NULL;
333 	}
334 
335 	new = NOFAIL(malloc(sizeof(struct index_file)));
336 	new->file = file;
337 	new->root_offset = read_long(new->file);
338 
339 	errno = 0;
340 	return new;
341 }
342 
index_file_close(struct index_file * idx)343 void index_file_close(struct index_file *idx)
344 {
345 	fclose(idx->file);
346 	free(idx);
347 }
348 
index_readroot(struct index_file * in)349 static struct index_node_f *index_readroot(struct index_file *in)
350 {
351 	return index_read(in->file, in->root_offset);
352 }
353 
index_readchild(const struct index_node_f * parent,int ch)354 static struct index_node_f *index_readchild(const struct index_node_f *parent,
355 					    int ch)
356 {
357 	if (parent->first <= ch && ch <= parent->last) {
358 		return index_read(parent->file,
359 		                       parent->children[ch - parent->first]);
360 	}
361 
362 	return NULL;
363 }
364 
index_dump_node(struct index_node_f * node,struct strbuf * buf,int fd)365 static void index_dump_node(struct index_node_f *node, struct strbuf *buf,
366 								int fd)
367 {
368 	struct index_value *v;
369 	int ch, pushed;
370 
371 	pushed = strbuf_pushchars(buf, node->prefix);
372 
373 	for (v = node->values; v != NULL; v = v->next) {
374 		write_str_safe(fd, buf->bytes, buf->used);
375 		write_str_safe(fd, " ", 1);
376 		write_str_safe(fd, v->value, strlen(v->value));
377 		write_str_safe(fd, "\n", 1);
378 	}
379 
380 	for (ch = node->first; ch <= node->last; ch++) {
381 		struct index_node_f *child = index_readchild(node, ch);
382 
383 		if (!child)
384 			continue;
385 
386 		strbuf_pushchar(buf, ch);
387 		index_dump_node(child, buf, fd);
388 		strbuf_popchar(buf);
389 	}
390 
391 	strbuf_popchars(buf, pushed);
392 	index_close(node);
393 }
394 
index_dump(struct index_file * in,int fd,const char * prefix)395 void index_dump(struct index_file *in, int fd, const char *prefix)
396 {
397 	struct index_node_f *root;
398 	struct strbuf buf;
399 
400 	root = index_readroot(in);
401 	if (root == NULL)
402 		return;
403 
404 	strbuf_init(&buf);
405 	strbuf_pushchars(&buf, prefix);
406 	index_dump_node(root, &buf, fd);
407 	strbuf_release(&buf);
408 }
409 
index_search__node(struct index_node_f * node,const char * key,int i)410 static char *index_search__node(struct index_node_f *node, const char *key, int i)
411 {
412 	char *value;
413 	struct index_node_f *child;
414 	int ch;
415 	int j;
416 
417 	while(node) {
418 		for (j = 0; node->prefix[j]; j++) {
419 			ch = node->prefix[j];
420 
421 			if (ch != key[i+j]) {
422 				index_close(node);
423 				return NULL;
424 			}
425 		}
426 
427 		i += j;
428 
429 		if (key[i] == '\0') {
430 			value = node->values != NULL
431 				? strdup(node->values[0].value)
432 				: NULL;
433 
434 			index_close(node);
435 			return value;
436 		}
437 
438 		child = index_readchild(node, key[i]);
439 		index_close(node);
440 		node = child;
441 		i++;
442 	}
443 
444 	return NULL;
445 }
446 
447 /*
448  * Search the index for a key
449  *
450  * Returns the value of the first match
451  *
452  * The recursive functions free their node argument (using index_close).
453  */
index_search(struct index_file * in,const char * key)454 char *index_search(struct index_file *in, const char *key)
455 {
456 // FIXME: return value by reference instead of strdup
457 	struct index_node_f *root;
458 	char *value;
459 
460 	root = index_readroot(in);
461 	value = index_search__node(root, key, 0);
462 
463 	return value;
464 }
465 
466 
467 
468 /* Level 4: add all the values from a matching node */
index_searchwild__allvalues(struct index_node_f * node,struct index_value ** out)469 static void index_searchwild__allvalues(struct index_node_f *node,
470 					struct index_value **out)
471 {
472 	struct index_value *v;
473 
474 	for (v = node->values; v != NULL; v = v->next)
475 		add_value(out, v->value, v->len, v->priority);
476 
477 	index_close(node);
478 }
479 
480 /*
481  * Level 3: traverse a sub-keyspace which starts with a wildcard,
482  * looking for matches.
483  */
index_searchwild__all(struct index_node_f * node,int j,struct strbuf * buf,const char * subkey,struct index_value ** out)484 static void index_searchwild__all(struct index_node_f *node, int j,
485 				  struct strbuf *buf,
486 				  const char *subkey,
487 				  struct index_value **out)
488 {
489 	int pushed = 0;
490 	int ch;
491 
492 	while (node->prefix[j]) {
493 		ch = node->prefix[j];
494 
495 		strbuf_pushchar(buf, ch);
496 		pushed++;
497 		j++;
498 	}
499 
500 	for (ch = node->first; ch <= node->last; ch++) {
501 		struct index_node_f *child = index_readchild(node, ch);
502 
503 		if (!child)
504 			continue;
505 
506 		strbuf_pushchar(buf, ch);
507 		index_searchwild__all(child, 0, buf, subkey, out);
508 		strbuf_popchar(buf);
509 	}
510 
511 	if (node->values) {
512 		if (fnmatch(strbuf_str(buf), subkey, 0) == 0)
513 			index_searchwild__allvalues(node, out);
514 		else
515 			index_close(node);
516 	} else {
517 		index_close(node);
518 	}
519 
520 	strbuf_popchars(buf, pushed);
521 }
522 
523 /* Level 2: descend the tree (until we hit a wildcard) */
index_searchwild__node(struct index_node_f * node,struct strbuf * buf,const char * key,int i,struct index_value ** out)524 static void index_searchwild__node(struct index_node_f *node,
525 				   struct strbuf *buf,
526 				   const char *key, int i,
527 				   struct index_value **out)
528 {
529 	struct index_node_f *child;
530 	int j;
531 	int ch;
532 
533 	while(node) {
534 		for (j = 0; node->prefix[j]; j++) {
535 			ch = node->prefix[j];
536 
537 			if (ch == '*' || ch == '?' || ch == '[') {
538 				index_searchwild__all(node, j, buf,
539 						      &key[i+j], out);
540 				return;
541 			}
542 
543 			if (ch != key[i+j]) {
544 				index_close(node);
545 				return;
546 			}
547 		}
548 
549 		i += j;
550 
551 		child = index_readchild(node, '*');
552 		if (child) {
553 			strbuf_pushchar(buf, '*');
554 			index_searchwild__all(child, 0, buf, &key[i], out);
555 			strbuf_popchar(buf);
556 		}
557 
558 		child = index_readchild(node, '?');
559 		if (child) {
560 			strbuf_pushchar(buf, '?');
561 			index_searchwild__all(child, 0, buf, &key[i], out);
562 			strbuf_popchar(buf);
563 		}
564 
565 		child = index_readchild(node, '[');
566 		if (child) {
567 			strbuf_pushchar(buf, '[');
568 			index_searchwild__all(child, 0, buf, &key[i], out);
569 			strbuf_popchar(buf);
570 		}
571 
572 		if (key[i] == '\0') {
573 			index_searchwild__allvalues(node, out);
574 
575 			return;
576 		}
577 
578 		child = index_readchild(node, key[i]);
579 		index_close(node);
580 		node = child;
581 		i++;
582 	}
583 }
584 
585 /*
586  * Search the index for a key.  The index may contain wildcards.
587  *
588  * Returns a list of all the values of matching keys.
589  */
index_searchwild(struct index_file * in,const char * key)590 struct index_value *index_searchwild(struct index_file *in, const char *key)
591 {
592 	struct index_node_f *root = index_readroot(in);
593 	struct strbuf buf;
594 	struct index_value *out = NULL;
595 
596 	strbuf_init(&buf);
597 	index_searchwild__node(root, &buf, key, 0, &out);
598 	strbuf_release(&buf);
599 	return out;
600 }
601 
602 /**************************************************************************/
603 /*
604  * Alternative implementation, using mmap to map all the file to memory when
605  * starting
606  */
607 #include <sys/mman.h>
608 #include <sys/stat.h>
609 #include <unistd.h>
610 
611 static const char _idx_empty_str[] = "";
612 
613 struct index_mm {
614 	const struct kmod_ctx *ctx;
615 	void *mm;
616 	uint32_t root_offset;
617 	size_t size;
618 };
619 
620 struct index_mm_value {
621 	unsigned int priority;
622 	unsigned int len;
623 	const char *value;
624 };
625 
626 struct index_mm_value_array {
627 	struct index_mm_value *values;
628 	unsigned int len;
629 };
630 
631 struct index_mm_node {
632 	struct index_mm *idx;
633 	const char *prefix; /* mmape'd value */
634 	struct index_mm_value_array values;
635 	unsigned char first;
636 	unsigned char last;
637 	uint32_t children[];
638 };
639 
read_long_mm(void ** p)640 static inline uint32_t read_long_mm(void **p)
641 {
642 	uint8_t *addr = *(uint8_t **)p;
643 	uint32_t v;
644 
645 	/* addr may be unalined to uint32_t */
646 	v = get_unaligned((uint32_t *) addr);
647 
648 	*p = addr + sizeof(uint32_t);
649 	return ntohl(v);
650 }
651 
read_char_mm(void ** p)652 static inline uint8_t read_char_mm(void **p)
653 {
654 	uint8_t *addr = *(uint8_t **)p;
655 	uint8_t v = *addr;
656 	*p = addr + sizeof(uint8_t);
657 	return v;
658 }
659 
read_chars_mm(void ** p,unsigned * rlen)660 static inline char *read_chars_mm(void **p, unsigned *rlen)
661 {
662 	char *addr = *(char **)p;
663 	size_t len = *rlen = strlen(addr);
664 	*p = addr + len + 1;
665 	return addr;
666 }
667 
index_mm_read_node(struct index_mm * idx,uint32_t offset)668 static struct index_mm_node *index_mm_read_node(struct index_mm *idx,
669 							uint32_t offset) {
670 	void *p = idx->mm;
671 	struct index_mm_node *node;
672 	const char *prefix;
673 	int i, child_count, value_count, children_padding;
674 	uint32_t children[INDEX_CHILDMAX];
675 	char first, last;
676 
677 	if ((offset & INDEX_NODE_MASK) == 0)
678 		return NULL;
679 
680 	p = (char *)p + (offset & INDEX_NODE_MASK);
681 
682 	if (offset & INDEX_NODE_PREFIX) {
683 		unsigned len;
684 		prefix = read_chars_mm(&p, &len);
685 	} else
686 		prefix = _idx_empty_str;
687 
688 	if (offset & INDEX_NODE_CHILDS) {
689 		first = read_char_mm(&p);
690 		last = read_char_mm(&p);
691 		child_count = last - first + 1;
692 		for (i = 0; i < child_count; i++)
693 			children[i] = read_long_mm(&p);
694 	} else {
695 		first = (char)INDEX_CHILDMAX;
696 		last = 0;
697 		child_count = 0;
698 	}
699 
700 	children_padding = (sizeof(struct index_mm_node) +
701 			    (sizeof(uint32_t) * child_count)) % sizeof(void *);
702 
703 	if (offset & INDEX_NODE_VALUES)
704 		value_count = read_long_mm(&p);
705 	else
706 		value_count = 0;
707 
708 	node = malloc(sizeof(struct index_mm_node)
709 		      + sizeof(uint32_t) * child_count + children_padding
710 		      + sizeof(struct index_mm_value) * value_count);
711 	if (node == NULL)
712 		return NULL;
713 
714 	node->idx = idx;
715 	node->prefix = prefix;
716 	if (value_count == 0)
717 		node->values.values = NULL;
718 	else {
719 		node->values.values = (struct index_mm_value *)
720 			((char *)node + sizeof(struct index_mm_node) +
721 			 sizeof(uint32_t) * child_count + children_padding);
722 	}
723 	node->values.len = value_count;
724 	node->first = first;
725 	node->last = last;
726 	memcpy(node->children, children, sizeof(uint32_t) * child_count);
727 
728 	for (i = 0; i < value_count; i++) {
729 		struct index_mm_value *v = node->values.values + i;
730 		v->priority = read_long_mm(&p);
731 		v->value = read_chars_mm(&p, &v->len);
732 	}
733 
734 	return node;
735 }
736 
index_mm_free_node(struct index_mm_node * node)737 static void index_mm_free_node(struct index_mm_node *node)
738 {
739 	free(node);
740 }
741 
index_mm_open(const struct kmod_ctx * ctx,const char * filename,unsigned long long * stamp,struct index_mm ** pidx)742 int index_mm_open(const struct kmod_ctx *ctx, const char *filename,
743 		  unsigned long long *stamp, struct index_mm **pidx)
744 {
745 	int fd, err;
746 	struct stat st;
747 	struct index_mm *idx;
748 	struct {
749 		uint32_t magic;
750 		uint32_t version;
751 		uint32_t root_offset;
752 	} hdr;
753 	void *p;
754 
755 	assert(pidx != NULL);
756 
757 	DBG(ctx, "file=%s\n", filename);
758 
759 	idx = malloc(sizeof(*idx));
760 	if (idx == NULL) {
761 		ERR(ctx, "malloc: %m\n");
762 		return -ENOMEM;
763 	}
764 
765 	if ((fd = open(filename, O_RDONLY|O_CLOEXEC)) < 0) {
766 		DBG(ctx, "open(%s, O_RDONLY|O_CLOEXEC): %m\n", filename);
767 		err = -errno;
768 		goto fail_open;
769 	}
770 
771 	if (fstat(fd, &st) < 0 || (size_t) st.st_size < sizeof(hdr)) {
772 		err = -EINVAL;
773 		goto fail_nommap;
774 	}
775 
776 	idx->mm = mmap(NULL, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
777 	if (idx->mm == MAP_FAILED) {
778 		ERR(ctx, "mmap(NULL, %"PRIu64", PROT_READ, %d, MAP_PRIVATE, 0): %m\n",
779 							st.st_size, fd);
780 		err = -errno;
781 		goto fail_nommap;
782 	}
783 
784 	p = idx->mm;
785 	hdr.magic = read_long_mm(&p);
786 	hdr.version = read_long_mm(&p);
787 	hdr.root_offset = read_long_mm(&p);
788 
789 	if (hdr.magic != INDEX_MAGIC) {
790 		ERR(ctx, "magic check fail: %x instead of %x\n", hdr.magic,
791 								INDEX_MAGIC);
792 		err = -EINVAL;
793 		goto fail;
794 	}
795 
796 	if (hdr.version >> 16 != INDEX_VERSION_MAJOR) {
797 		ERR(ctx, "major version check fail: %u instead of %u\n",
798 					hdr.version >> 16, INDEX_VERSION_MAJOR);
799 		err = -EINVAL;
800 		goto fail;
801 	}
802 
803 	idx->root_offset = hdr.root_offset;
804 	idx->size = st.st_size;
805 	idx->ctx = ctx;
806 	close(fd);
807 
808 	*stamp = stat_mstamp(&st);
809 	*pidx = idx;
810 
811 	return 0;
812 
813 fail:
814 	munmap(idx->mm, st.st_size);
815 fail_nommap:
816 	close(fd);
817 fail_open:
818 	free(idx);
819 	return err;
820 }
821 
index_mm_close(struct index_mm * idx)822 void index_mm_close(struct index_mm *idx)
823 {
824 	munmap(idx->mm, idx->size);
825 	free(idx);
826 }
827 
index_mm_readroot(struct index_mm * idx)828 static struct index_mm_node *index_mm_readroot(struct index_mm *idx)
829 {
830 	return index_mm_read_node(idx, idx->root_offset);
831 }
832 
index_mm_readchild(const struct index_mm_node * parent,int ch)833 static struct index_mm_node *index_mm_readchild(const struct index_mm_node *parent,
834 									int ch)
835 {
836 	if (parent->first <= ch && ch <= parent->last) {
837 		return index_mm_read_node(parent->idx,
838 					parent->children[ch - parent->first]);
839 	}
840 
841 	return NULL;
842 }
843 
index_mm_dump_node(struct index_mm_node * node,struct strbuf * buf,int fd)844 static void index_mm_dump_node(struct index_mm_node *node, struct strbuf *buf,
845 								int fd)
846 {
847 	struct index_mm_value *itr, *itr_end;
848 	int ch, pushed;
849 
850 	pushed = strbuf_pushchars(buf, node->prefix);
851 
852 	itr = node->values.values;
853 	itr_end = itr + node->values.len;
854 	for (; itr < itr_end; itr++) {
855 		write_str_safe(fd, buf->bytes, buf->used);
856 		write_str_safe(fd, " ", 1);
857 		write_str_safe(fd, itr->value, itr->len);
858 		write_str_safe(fd, "\n", 1);
859 	}
860 
861 	for (ch = node->first; ch <= node->last; ch++) {
862 		struct index_mm_node *child = index_mm_readchild(node, ch);
863 
864 		if (child == NULL)
865 			continue;
866 
867 		strbuf_pushchar(buf, ch);
868 		index_mm_dump_node(child, buf, fd);
869 		strbuf_popchar(buf);
870 	}
871 
872 	strbuf_popchars(buf, pushed);
873 	index_mm_free_node(node);
874 }
875 
index_mm_dump(struct index_mm * idx,int fd,const char * prefix)876 void index_mm_dump(struct index_mm *idx, int fd, const char *prefix)
877 {
878 	struct index_mm_node *root;
879 	struct strbuf buf;
880 
881 	root = index_mm_readroot(idx);
882 	if (root == NULL)
883 		return;
884 
885 	strbuf_init(&buf);
886 	strbuf_pushchars(&buf, prefix);
887 	index_mm_dump_node(root, &buf, fd);
888 	strbuf_release(&buf);
889 }
890 
index_mm_search_node(struct index_mm_node * node,const char * key,int i)891 static char *index_mm_search_node(struct index_mm_node *node, const char *key,
892 									int i)
893 {
894 	char *value;
895 	struct index_mm_node *child;
896 	int ch;
897 	int j;
898 
899 	while(node) {
900 		for (j = 0; node->prefix[j]; j++) {
901 			ch = node->prefix[j];
902 
903 			if (ch != key[i+j]) {
904 				index_mm_free_node(node);
905 				return NULL;
906 			}
907 		}
908 
909 		i += j;
910 
911 		if (key[i] == '\0') {
912 			value = node->values.len > 0
913 				? strdup(node->values.values[0].value)
914 				: NULL;
915 
916 			index_mm_free_node(node);
917 			return value;
918 		}
919 
920 		child = index_mm_readchild(node, key[i]);
921 		index_mm_free_node(node);
922 		node = child;
923 		i++;
924 	}
925 
926 	return NULL;
927 }
928 
929 /*
930  * Search the index for a key
931  *
932  * Returns the value of the first match
933  *
934  * The recursive functions free their node argument (using index_close).
935  */
index_mm_search(struct index_mm * idx,const char * key)936 char *index_mm_search(struct index_mm *idx, const char *key)
937 {
938 // FIXME: return value by reference instead of strdup
939 	struct index_mm_node *root;
940 	char *value;
941 
942 	root = index_mm_readroot(idx);
943 	value = index_mm_search_node(root, key, 0);
944 
945 	return value;
946 }
947 
948 /* Level 4: add all the values from a matching node */
index_mm_searchwild_allvalues(struct index_mm_node * node,struct index_value ** out)949 static void index_mm_searchwild_allvalues(struct index_mm_node *node,
950 						struct index_value **out)
951 {
952 	struct index_mm_value *itr, *itr_end;
953 
954 	itr = node->values.values;
955 	itr_end = itr + node->values.len;
956 	for (; itr < itr_end; itr++)
957 		add_value(out, itr->value, itr->len, itr->priority);
958 
959 	index_mm_free_node(node);
960 }
961 
962 /*
963  * Level 3: traverse a sub-keyspace which starts with a wildcard,
964  * looking for matches.
965  */
index_mm_searchwild_all(struct index_mm_node * node,int j,struct strbuf * buf,const char * subkey,struct index_value ** out)966 static void index_mm_searchwild_all(struct index_mm_node *node, int j,
967 					  struct strbuf *buf,
968 					  const char *subkey,
969 					  struct index_value **out)
970 {
971 	int pushed = 0;
972 	int ch;
973 
974 	while (node->prefix[j]) {
975 		ch = node->prefix[j];
976 
977 		strbuf_pushchar(buf, ch);
978 		pushed++;
979 		j++;
980 	}
981 
982 	for (ch = node->first; ch <= node->last; ch++) {
983 		struct index_mm_node *child = index_mm_readchild(node, ch);
984 
985 		if (!child)
986 			continue;
987 
988 		strbuf_pushchar(buf, ch);
989 		index_mm_searchwild_all(child, 0, buf, subkey, out);
990 		strbuf_popchar(buf);
991 	}
992 
993 	if (node->values.len > 0) {
994 		if (fnmatch(strbuf_str(buf), subkey, 0) == 0)
995 			index_mm_searchwild_allvalues(node, out);
996 		else
997 			index_mm_free_node(node);
998 	} else {
999 		index_mm_free_node(node);
1000 	}
1001 
1002 	strbuf_popchars(buf, pushed);
1003 }
1004 
1005 /* Level 2: descend the tree (until we hit a wildcard) */
index_mm_searchwild_node(struct index_mm_node * node,struct strbuf * buf,const char * key,int i,struct index_value ** out)1006 static void index_mm_searchwild_node(struct index_mm_node *node,
1007 					   struct strbuf *buf,
1008 					   const char *key, int i,
1009 					   struct index_value **out)
1010 {
1011 	struct index_mm_node *child;
1012 	int j;
1013 	int ch;
1014 
1015 	while(node) {
1016 		for (j = 0; node->prefix[j]; j++) {
1017 			ch = node->prefix[j];
1018 
1019 			if (ch == '*' || ch == '?' || ch == '[') {
1020 				index_mm_searchwild_all(node, j, buf,
1021 						      &key[i+j], out);
1022 				return;
1023 			}
1024 
1025 			if (ch != key[i+j]) {
1026 				index_mm_free_node(node);
1027 				return;
1028 			}
1029 		}
1030 
1031 		i += j;
1032 
1033 		child = index_mm_readchild(node, '*');
1034 		if (child) {
1035 			strbuf_pushchar(buf, '*');
1036 			index_mm_searchwild_all(child, 0, buf, &key[i], out);
1037 			strbuf_popchar(buf);
1038 		}
1039 
1040 		child = index_mm_readchild(node, '?');
1041 		if (child) {
1042 			strbuf_pushchar(buf, '?');
1043 			index_mm_searchwild_all(child, 0, buf, &key[i], out);
1044 			strbuf_popchar(buf);
1045 		}
1046 
1047 		child = index_mm_readchild(node, '[');
1048 		if (child) {
1049 			strbuf_pushchar(buf, '[');
1050 			index_mm_searchwild_all(child, 0, buf, &key[i], out);
1051 			strbuf_popchar(buf);
1052 		}
1053 
1054 		if (key[i] == '\0') {
1055 			index_mm_searchwild_allvalues(node, out);
1056 
1057 			return;
1058 		}
1059 
1060 		child = index_mm_readchild(node, key[i]);
1061 		index_mm_free_node(node);
1062 		node = child;
1063 		i++;
1064 	}
1065 }
1066 
1067 /*
1068  * Search the index for a key.  The index may contain wildcards.
1069  *
1070  * Returns a list of all the values of matching keys.
1071  */
index_mm_searchwild(struct index_mm * idx,const char * key)1072 struct index_value *index_mm_searchwild(struct index_mm *idx, const char *key)
1073 {
1074 	struct index_mm_node *root = index_mm_readroot(idx);
1075 	struct strbuf buf;
1076 	struct index_value *out = NULL;
1077 
1078 	strbuf_init(&buf);
1079 	index_mm_searchwild_node(root, &buf, key, 0, &out);
1080 	strbuf_release(&buf);
1081 	return out;
1082 }
1083