?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
TODO: fix the build system with respect to docs.
[mit.git] / index.c
blob6a8dcecbcbf9509a349b448dbe1a5cc6672dfad0
1 /* index.c: module index file shared functions for modprobe and depmod
2 Copyright (C) 2008 Alan Jenkins <alan-jenkins@tuffmail.co.uk>.
3
4 These programs are free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 2 of the License, or
7 (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with these programs. If not, see <http://www.gnu.org/licenses/>.
16 */
17
18 #include <arpa/inet.h> /* htonl */
19 #include <stdlib.h>
20 #include <stdio.h>
21 #include <string.h>
22 #include <errno.h>
23 #include <fnmatch.h>
24
25 #include "logging.h"
26 #include "index.h"
27
28 #include "testing.h"
29
30 #define streq(a,b) (strcmp((a),(b)) == 0)
31
32 /*
33 * Index abstract data type (used only by depmod)
34 */
35
36 struct index_node *index_create()
37 {
38 struct index_node *node;
39
40 node = NOFAIL(calloc(sizeof(struct index_node), 1));
41 node->prefix = NOFAIL(strdup(""));
42 node->first = INDEX_CHILDMAX;
43
44 return node;
45 }
46
47 void index_values_free(struct index_value *values)
48 {
49 while (values) {
50 struct index_value *value = values;
51
52 values = value->next;
53 free(value);
54 }
55 }
56
57 void index_destroy(struct index_node *node)
58 {
59 int c;
60
61 for (c = node->first; c <= node->last; c++) {
62 struct index_node *child = node->children[c];
63
64 if (child)
65 index_destroy(child);
66 }
67 index_values_free(node->values);
68 free(node->prefix);
69 free(node);
70 }
71
72 static void index__checkstring(const char *str)
73 {
74 int i;
75
76 for (i = 0; str[i]; i++) {
77 int ch = str[i];
78
79 if (ch >= INDEX_CHILDMAX)
80 fatal("Module index: bad character '%c'=0x%x - only 7-bit ASCII is supported:"
81 "\n%s\n", (char) ch, (int) ch, str);
82 }
83 }
84
85 static int add_value(struct index_value **values,
86 const char *value, unsigned int priority)
87 {
88 struct index_value *v;
89 int duplicate;
90 int len;
91
92 /* report the presence of duplicate values */
93 for (v = *values; v; v = v->next) {
94 if (streq(v->value, value))
95 duplicate = 1;
96 }
97
98 /* find position to insert value */
99 while (*values && (*values)->priority < priority)
100 values = &(*values)->next;
101
102 len = strlen(value);
103 v = NOFAIL(calloc(sizeof(struct index_value) + len + 1, 1));
104 v->next = *values;
105 v->priority = priority;
106 memcpy(v->value, value, len + 1);
107 *values = v;
108
109 return duplicate;
110 }
111
112 int index_insert(struct index_node *node, const char *key,
113 const char *value, unsigned int priority)
114 {
115 int i = 0; /* index within str */
116 int ch;
117
118 index__checkstring(key);
119 index__checkstring(value);
120
121 while(1) {
122 int j; /* index within node->prefix */
123
124 /* Ensure node->prefix is a prefix of &str[i].
125 If it is not already, then we must split node. */
126 for (j = 0; node->prefix[j]; j++) {
127 ch = node->prefix[j];
128
129 if (ch != key[i+j]) {
130 char *prefix = node->prefix;
131 struct index_node *n;
132
133 /* New child is copy of node with prefix[j+1..N] */
134 n = NOFAIL(calloc(sizeof(struct index_node), 1));
135 memcpy(n, node, sizeof(struct index_node));
136 n->prefix = NOFAIL(strdup(&prefix[j+1]));
137
138 /* Parent has prefix[0..j], child at prefix[j] */
139 memset(node, 0, sizeof(struct index_node));
140 prefix[j] = '\0';
141 node->prefix = prefix;
142 node->first = ch;
143 node->last = ch;
144 node->children[ch] = n;
145
146 break;
147 }
148 }
149 /* j is now length of node->prefix */
150 i += j;
151
152 ch = key[i];
153 if(ch == '\0')
154 return add_value(&node->values, value, priority);
155
156 if (!node->children[ch]) {
157 struct index_node *child;
158
159 if (ch < node->first)
160 node->first = ch;
161 if (ch > node->last)
162 node->last = ch;
163 node->children[ch] = NOFAIL(calloc(sizeof(struct index_node), 1));
164
165 child = node->children[ch];
166 child->prefix = NOFAIL(strdup(&key[i+1]));
167 child->first = INDEX_CHILDMAX;
168 add_value(&child->values, value, priority);
169
170 return 0;
171 }
172
173 /* Descend into child node and continue */
174 node = node->children[ch];
175 i++;
176 }
177 }
178
179 static int index__haschildren(const struct index_node *node)
180 {
181 return node->first < INDEX_CHILDMAX;
182 }
183
184 /* Recursive post-order traversal
185
186 Pre-order would make for better read-side buffering / readahead / caching.
187 (post-order means you go backwards in the file as you descend the tree).
188 However, index reading is already fast enough.
189 Pre-order is simpler for writing, and depmod is already slow.
190 */
191 static uint32_t index_write__node(const struct index_node *node, FILE *out)
192 {
193 uint32_t *child_offs = NULL;
194 int child_count = 0;
195 long offset;
196
197 if (!node)
198 return 0;
199
200 /* Write children and save their offsets */
201 if (index__haschildren(node)) {
202 const struct index_node *child;
203 int i;
204
205 child_count = node->last - node->first + 1;
206 child_offs = NOFAIL(malloc(child_count * sizeof(uint32_t)));
207
208 for (i = 0; i < child_count; i++) {
209 child = node->children[node->first + i];
210 child_offs[i] = htonl(index_write__node(child, out));
211 }
212 }
213
214 /* Now write this node */
215 offset = ftell(out);
216
217 if (node->prefix[0]) {
218 fputs(node->prefix, out);
219 fputc('\0', out);
220 offset |= INDEX_NODE_PREFIX;
221 }
222
223 if (child_count) {
224 fputc(node->first, out);
225 fputc(node->last, out);
226 fwrite(child_offs, sizeof(uint32_t), child_count, out);
227 free(child_offs);
228 offset |= INDEX_NODE_CHILDS;
229 }
230
231 if (node->values) {
232 const struct index_value *v;
233 unsigned int value_count;
234 uint32_t u;
235
236 value_count = 0;
237 for (v = node->values; v != NULL; v = v->next)
238 value_count++;
239 u = htonl(value_count);
240 fwrite(&u, sizeof(u), 1, out);
241
242 for (v = node->values; v != NULL; v = v->next) {
243 u = htonl(v->priority);
244 fwrite(&u, sizeof(u), 1, out);
245 fputs(v->value, out);
246 fputc('\0', out);
247 }
248 offset |= INDEX_NODE_VALUES;
249 }
250
251 return offset;
252 }
253
254 void index_write(const struct index_node *node, FILE *out)
255 {
256 long initial_offset, final_offset;
257 uint32_t u;
258
259 u = htonl(INDEX_MAGIC);
260 fwrite(&u, sizeof(u), 1, out);
261 u = htonl(INDEX_VERSION);
262 fwrite(&u, sizeof(u), 1, out);
263
264 /* Second word is reserved for the offset of the root node */
265 initial_offset = ftell(out);
266 u = 0;
267 fwrite(&u, sizeof(uint32_t), 1, out);
268
269 /* Dump trie */
270 u = htonl(index_write__node(node, out));
271
272 /* Update first word */
273 final_offset = ftell(out);
274 fseek(out, initial_offset, SEEK_SET);
275 fwrite(&u, sizeof(uint32_t), 1, out);
276 fseek(out, final_offset, SEEK_SET);
277 }
278
279
280
281 static void read_error()
282 {
283 fatal("Module index: unexpected error: %s\n"
284 "Try re-running depmod\n", errno ? strerror(errno) : "EOF");
285 }
286
287 static int read_char(FILE *in)
288 {
289 int ch;
290
291 errno = 0;
292 ch = getc_unlocked(in);
293 if (ch == EOF)
294 read_error();
295 return ch;
296 }
297
298 static uint32_t read_long(FILE *in)
299 {
300 uint32_t l;
301
302 errno = 0;
303 if (fread(&l, sizeof(uint32_t), 1, in) <= 0)
304 read_error();
305 return ntohl(l);
306 }
307
308 /*
309 * Buffer abstract data type
310 *
311 * Used internally to store the current path during tree traversal.
312 * They help build wildcard key strings to pass to fnmatch(),
313 * as well as building values of matching keys.
314 */
315
316 struct buffer {
317 char *bytes;
318 unsigned size;
319 unsigned used;
320 };
321
322 static void buf__realloc(struct buffer *buf, unsigned size)
323 {
324 if (size > buf->size) {
325 buf->bytes = NOFAIL(realloc(buf->bytes, size));
326 buf->size = size;
327 }
328 }
329
330 static struct buffer *buf_create()
331 {
332 struct buffer *buf;
333
334 buf = NOFAIL(calloc(sizeof(struct buffer), 1));
335 buf__realloc(buf, 256);
336 return buf;
337 }
338
339 static void buf_destroy(struct buffer *buf)
340 {
341 free(buf->bytes);
342 free(buf);
343 }
344
345 /* Destroy buffer and return a copy as a C string */
346 static char *buf_detach(struct buffer *buf)
347 {
348 char *bytes;
349
350 bytes = NOFAIL(realloc(buf->bytes, buf->used + 1));
351 bytes[buf->used] = '\0';
352
353 free(buf);
354 return bytes;
355 }
356
357 /* Return a C string owned by the buffer
358 (invalidated if the buffer is changed).
359 */
360 static const char *buf_str(struct buffer *buf)
361 {
362 buf__realloc(buf, buf->used + 1);
363 buf->bytes[buf->used] = '\0';
364 return buf->bytes;
365 }
366
367 static int buf_fwrite(struct buffer *buf, FILE *out)
368 {
369 return fwrite(buf->bytes, 1, buf->used, out);
370 }
371
372 static void buf_pushchar(struct buffer *buf, char ch)
373 {
374 buf__realloc(buf, buf->used + 1);
375 buf->bytes[buf->used] = ch;
376 buf->used++;
377 }
378
379 static unsigned buf_pushchars(struct buffer *buf, const char *str)
380 {
381 unsigned i = 0;
382 int ch;
383
384 while ((ch = str[i])) {
385 buf_pushchar(buf, ch);
386 i++;
387 }
388 return i;
389 }
390
391 /* like buf_pushchars(), but the string comes from a file */
392 static unsigned buf_freadchars(struct buffer *buf, FILE *in)
393 {
394 unsigned i = 0;
395 int ch;
396
397 while ((ch = read_char(in))) {
398 buf_pushchar(buf, ch);
399 i++;
400 }
401
402 return i;
403 }
404
405 static void buf_popchar(struct buffer *buf)
406 {
407 buf->used--;
408 }
409
410 static void buf_popchars(struct buffer *buf, unsigned n)
411 {
412 buf->used -= n;
413 }
414
415 static void buf_clear(struct buffer *buf)
416 {
417 buf->used = 0;
418 }
419
420 /*
421 * Index file searching (used only by modprobe)
422 */
423
424 struct index_node_f {
425 FILE *file;
426 char *prefix; /* path compression */
427 struct index_value *values;
428 unsigned char first; /* range of child nodes */
429 unsigned char last;
430 uint32_t children[0];
431 };
432
433 static struct index_node_f *index_read(FILE *in, uint32_t offset)
434 {
435 struct index_node_f *node;
436 char *prefix;
437 int i, child_count = 0;
438
439 if ((offset & INDEX_NODE_MASK) == 0)
440 return NULL;
441
442 fseek(in, offset & INDEX_NODE_MASK, SEEK_SET);
443
444 if (offset & INDEX_NODE_PREFIX) {
445 struct buffer *buf = buf_create();
446 buf_freadchars(buf, in);
447 prefix = buf_detach(buf);
448 } else
449 prefix = NOFAIL(strdup(""));
450
451 if (offset & INDEX_NODE_CHILDS) {
452 char first = read_char(in);
453 char last = read_char(in);
454 child_count = last - first + 1;
455
456 node = NOFAIL(malloc(sizeof(struct index_node_f) +
457 sizeof(uint32_t) * child_count));
458
459 node->first = first;
460 node->last = last;
461
462 for (i = 0; i < child_count; i++)
463 node->children[i] = read_long(in);
464 } else {
465 node = NOFAIL(malloc(sizeof(struct index_node_f)));
466 node->first = INDEX_CHILDMAX;
467 node->last = 0;
468 }
469
470 node->values = NULL;
471 if (offset & INDEX_NODE_VALUES) {
472 int value_count;
473 struct buffer *buf = buf_create();
474 const char *value;
475 unsigned int priority;
476
477 value_count = read_long(in);
478
479 while (value_count--) {
480 priority = read_long(in);
481 buf_freadchars(buf, in);
482 value = buf_str(buf);
483 add_value(&node->values, value, priority);
484 buf_clear(buf);
485 }
486 buf_destroy(buf);
487 }
488
489 node->prefix = prefix;
490 node->file = in;
491 return node;
492 }
493
494 static void index_close(struct index_node_f *node)
495 {
496 free(node->prefix);
497 index_values_free(node->values);
498 free(node);
499 }
500
501 struct index_file {
502 FILE *file;
503 uint32_t root_offset;
504 };
505
506 /* Failures are silent; modprobe will fall back to text files */
507 struct index_file *index_file_open(const char *filename)
508 {
509 FILE *file;
510 uint32_t magic, version;
511 struct index_file *new;
512
513 file = fopen(filename, "r");
514 if (!file)
515 return NULL;
516 errno = EINVAL;
517
518 magic = read_long(file);
519 if (magic != INDEX_MAGIC)
520 return NULL;
521
522 version = read_long(file);
523 if (version >> 16 != INDEX_VERSION_MAJOR)
524 return NULL;
525
526 new = NOFAIL(malloc(sizeof(struct index_file)));
527 new->file = file;
528 new->root_offset = read_long(new->file);
529
530 errno = 0;
531 return new;
532 }
533
534 void index_file_close(struct index_file *index)
535 {
536 fclose(index->file);
537 free(index);
538 }
539
540
541 static struct index_node_f *index_readroot(struct index_file *in)
542 {
543 return index_read(in->file, in->root_offset);
544 }
545
546 static struct index_node_f *index_readchild(const struct index_node_f *parent,
547 int ch)
548 {
549 if (parent->first <= ch && ch <= parent->last)
550 return index_read(parent->file,
551 parent->children[ch - parent->first]);
552 else
553 return NULL;
554 }
555
556 /*
557 * Dump all strings as lines in a plain text file.
558 */
559
560 static void index_dump_node(struct index_node_f *node,
561 struct buffer *buf,
562 FILE *out,
563 const char *prefix)
564 {
565 struct index_value *v;
566 int ch, pushed;
567
568 pushed = buf_pushchars(buf, node->prefix);
569
570 for (v = node->values; v != NULL; v = v->next) {
571 fputs(prefix, out);
572 buf_fwrite(buf, out);
573 fputc(' ', out);
574 fputs(v->value, out);
575 fputc('\n', out);
576 }
577
578 for (ch = node->first; ch <= node->last; ch++) {
579 struct index_node_f *child = index_readchild(node, ch);
580
581 if (!child)
582 continue;
583
584 buf_pushchar(buf, ch);
585 index_dump_node(child, buf, out, prefix);
586 buf_popchar(buf);
587 }
588
589 buf_popchars(buf, pushed);
590 index_close(node);
591 }
592
593 void index_dump(struct index_file *in, FILE *out, const char *prefix)
594 {
595 struct index_node_f *root;
596 struct buffer *buf;
597
598 buf = buf_create();
599 root = index_readroot(in);
600 index_dump_node(root, buf, out, prefix);
601 buf_destroy(buf);
602 }
603
604 /*
605 * Search the index for a key
606 *
607 * Returns the value of the first match
608 *
609 * The recursive functions free their node argument (using index_close).
610 */
611
612 char *index_search(struct index_file *in, const char *key);
613 static char *index_search__node(struct index_node_f *node, const char *key, int i);
614
615 char *index_search(struct index_file *in, const char *key)
616 {
617 struct index_node_f *root;
618 char *value;
619
620 root = index_readroot(in);
621 value = index_search__node(root, key, 0);
622
623 return value;
624 }
625
626 static char *index_search__node(struct index_node_f *node, const char *key, int i)
627 {
628 struct index_node_f *child;
629 int ch;
630 int j;
631
632 while(node) {
633 for (j = 0; node->prefix[j]; j++) {
634 ch = node->prefix[j];
635
636 if (ch != key[i+j]) {
637 index_close(node);
638 return NULL;
639 }
640 }
641 i += j;
642
643 if (key[i] == '\0') {
644 if (node->values)
645 return strdup(node->values[0].value);
646 else
647 return NULL;
648 }
649
650 child = index_readchild(node, key[i]);
651 index_close(node);
652 node = child;
653 i++;
654 }
655
656 return NULL;
657 }
658
659 /*
660 * Search the index for a key. The index may contain wildcards.
661 *
662 * Returns a list of all the values of matching keys.
663 */
664
665 /* Level 1: interface function */
666 struct index_value *index_searchwild(struct index_file *in, const char *key);
667
668 /* Level 2: descend the tree (until we hit a wildcard) */
669 static void index_searchwild__node(struct index_node_f *node,
670 struct buffer *buf,
671 const char *key, int i,
672 struct index_value **out);
673
674 /* Level 3: traverse a sub-keyspace which starts with a wildcard,
675 looking for matches.
676 */
677 static void index_searchwild__all(struct index_node_f *node, int j,
678 struct buffer *buf,
679 const char *subkey,
680 struct index_value **out);
681
682 /* Level 4: add all the values from a matching node */
683 static void index_searchwild__allvalues(struct index_node_f *node,
684 struct index_value **out);
685
686
687 struct index_value *index_searchwild(struct index_file *in, const char *key)
688 {
689 struct index_node_f *root = index_readroot(in);
690 struct buffer *buf = buf_create();
691 struct index_value *out = NULL;
692
693 index_searchwild__node(root, buf, key, 0, &out);
694 buf_destroy(buf);
695 return out;
696 }
697
698 static void index_searchwild__node(struct index_node_f *node,
699 struct buffer *buf,
700 const char *key, int i,
701 struct index_value **out)
702 {
703 struct index_node_f *child;
704 int j;
705 int ch;
706
707 while(node) {
708 for (j = 0; node->prefix[j]; j++) {
709 ch = node->prefix[j];
710
711 if (ch == '*' || ch == '?' || ch == '[') {
712 index_searchwild__all(node, j, buf,
713 &key[i+j], out);
714 return;
715 }
716
717 if (ch != key[i+j]) {
718 index_close(node);
719 return;
720 }
721 }
722 i += j;
723
724 child = index_readchild(node, '*');
725 if (child) {
726 buf_pushchar(buf, '*');
727 index_searchwild__all(child, 0, buf, &key[i], out);
728 buf_popchar(buf);
729 }
730
731 child = index_readchild(node, '?');
732 if (child) {
733 buf_pushchar(buf, '?');
734 index_searchwild__all(child, 0, buf, &key[i], out);
735 buf_popchar(buf);
736 }
737
738 child = index_readchild(node, '[');
739 if (child) {
740 buf_pushchar(buf, '[');
741 index_searchwild__all(child, 0, buf, &key[i], out);
742 buf_popchar(buf);
743 }
744
745 if (key[i] == '\0') {
746 index_searchwild__allvalues(node, out);
747
748 return;
749 }
750
751 child = index_readchild(node, key[i]);
752 index_close(node);
753 node = child;
754 i++;
755 }
756 }
757
758 static void index_searchwild__all(struct index_node_f *node, int j,
759 struct buffer *buf,
760 const char *subkey,
761 struct index_value **out)
762 {
763 int pushed = 0;
764 int ch;
765
766 while (node->prefix[j]) {
767 ch = node->prefix[j];
768
769 buf_pushchar(buf, ch);
770 pushed++;
771 j++;
772 }
773
774 for (ch = node->first; ch <= node->last; ch++) {
775 struct index_node_f *child = index_readchild(node, ch);
776
777 if (!child)
778 continue;
779
780 buf_pushchar(buf, ch);
781 index_searchwild__all(child, 0, buf, subkey, out);
782 buf_popchar(buf);
783 }
784
785 if (node->values) {
786 if (fnmatch(buf_str(buf), subkey, 0) == 0)
787 index_searchwild__allvalues(node, out);
788 }
789
790 index_close(node);
791 buf_popchars(buf, pushed);
792 }
793
794 static void index_searchwild__allvalues(struct index_node_f *node,
795 struct index_value **out)
796 {
797 struct index_value *v;
798
799 for (v = node->values; v != NULL; v = v->next)
800 add_value(out, v->value, v->priority);
801 }
module-init-tools