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