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