2 * libkmod - interface to kernel module operations
4 * Copyright (C) 2011-2013 ProFUSION embedded systems
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.
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.
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
21 #include <arpa/inet.h>
30 #include <shared/macro.h>
31 #include <shared/strbuf.h>
32 #include <shared/util.h>
34 #include "libkmod-internal.h"
35 #include "libkmod-index.h"
37 /* libkmod-index.c: module index file implementation
39 * Integers are stored as 32 bit unsigned in "network" order, i.e. MSB first.
40 * All files start with a magic number.
42 * Magic spells "BOOTFAST". Second one used on newer versioned binary files.
43 * #define INDEX_MAGIC_OLD 0xB007FA57
45 * We use a version string to keep track of changes to the binary format
46 * This is stored in the form: INDEX_MAJOR (hi) INDEX_MINOR (lo) just in
47 * case we ever decide to have minor changes that are not incompatible.
49 #define INDEX_MAGIC 0xB007F457
50 #define INDEX_VERSION_MAJOR 0x0002
51 #define INDEX_VERSION_MINOR 0x0001
52 #define INDEX_VERSION ((INDEX_VERSION_MAJOR<<16)|INDEX_VERSION_MINOR)
54 /* The index file maps keys to values. Both keys and values are ASCII strings.
55 * Each key can have multiple values. Values are sorted by an integer priority.
57 * The reader also implements a wildcard search (including range expressions)
58 * where the keys in the index are treated as patterns.
59 * This feature is required for module aliases.
61 #define INDEX_CHILDMAX 128
65 * uint32_t magic = INDEX_MAGIC;
66 * uint32_t version = INDEX_VERSION;
67 * uint32_t root_offset;
69 * (node_offset & INDEX_NODE_MASK) specifies the file offset of nodes:
71 * char[] prefix; // nul terminated
75 * uint32_t children[last - first + 1];
77 * uint32_t value_count;
80 * char[] value; // nul terminated
81 * } values[value_count];
83 * (node_offset & INDEX_NODE_FLAGS) indicates which fields are present.
84 * Empty prefixes are omitted, leaf nodes omit the three child-related fields.
86 * This could be optimised further by adding a sparse child format
87 * (indicated using a new flag).
90 * Implementation is based on a radix tree, or "trie".
91 * Each arc from parent to child is labelled with a character.
92 * Each path from the root represents a string.
94 * == Example strings ==
104 * * Marked node, representing a key and it's values.
115 * Naive implementations tend to be very space inefficient; child pointers
116 * are stored in arrays indexed by character, but most child pointers are null.
118 * Our implementation uses a scheme described by Wikipedia as a Patrica trie,
120 * "easiest to understand as a space-optimized trie where
121 * each node with only one child is merged with its child"
132 * We still use arrays of child pointers indexed by a single character;
133 * the remaining characters of the label are stored as a "prefix" in the child.
135 * The paper describing the original Patrica trie works on individiual bits -
136 * each node has a maximum of two children, which increases space efficiency.
137 * However for this application it is simpler to use the ASCII character set.
138 * Since the index file is read-only, it can be compressed by omitting null
139 * child pointers at the start and end of arrays.
142 /* Format of node offsets within index file */
144 INDEX_NODE_FLAGS
= 0xF0000000, /* Flags in high nibble */
145 INDEX_NODE_PREFIX
= 0x80000000,
146 INDEX_NODE_VALUES
= 0x40000000,
147 INDEX_NODE_CHILDS
= 0x20000000,
149 INDEX_NODE_MASK
= 0x0FFFFFFF, /* Offset value */
152 void index_values_free(struct index_value
*values
)
155 struct index_value
*value
= values
;
157 values
= value
->next
;
162 static int add_value(struct index_value
**values
,
163 const char *value
, unsigned len
, unsigned int priority
)
165 struct index_value
*v
;
167 /* find position to insert value */
168 while (*values
&& (*values
)->priority
< priority
)
169 values
= &(*values
)->next
;
171 v
= malloc(sizeof(struct index_value
) + len
+ 1);
175 v
->priority
= priority
;
177 memcpy(v
->value
, value
, len
);
178 v
->value
[len
] = '\0';
184 static void read_error(void)
186 fatal("Module index: unexpected error: %s\n"
187 "Try re-running depmod\n", errno
? strerror(errno
) : "EOF");
190 static int read_char(FILE *in
)
195 ch
= getc_unlocked(in
);
201 static uint32_t read_long(FILE *in
)
206 if (fread(&l
, sizeof(uint32_t), 1, in
) != sizeof(uint32_t))
211 static unsigned buf_freadchars(struct strbuf
*buf
, FILE *in
)
216 while ((ch
= read_char(in
))) {
217 if (!strbuf_pushchar(buf
, ch
))
226 * Index file searching
228 struct index_node_f
{
230 char *prefix
; /* path compression */
231 struct index_value
*values
;
232 unsigned char first
; /* range of child nodes */
234 uint32_t children
[0];
237 static struct index_node_f
*index_read(FILE *in
, uint32_t offset
)
239 struct index_node_f
*node
;
241 int i
, child_count
= 0;
243 if ((offset
& INDEX_NODE_MASK
) == 0)
246 fseek(in
, offset
& INDEX_NODE_MASK
, SEEK_SET
);
248 if (offset
& INDEX_NODE_PREFIX
) {
251 buf_freadchars(&buf
, in
);
252 prefix
= strbuf_steal(&buf
);
254 prefix
= NOFAIL(strdup(""));
256 if (offset
& INDEX_NODE_CHILDS
) {
257 char first
= read_char(in
);
258 char last
= read_char(in
);
259 child_count
= last
- first
+ 1;
261 node
= NOFAIL(malloc(sizeof(struct index_node_f
) +
262 sizeof(uint32_t) * child_count
));
267 for (i
= 0; i
< child_count
; i
++)
268 node
->children
[i
] = read_long(in
);
270 node
= NOFAIL(malloc(sizeof(struct index_node_f
)));
271 node
->first
= INDEX_CHILDMAX
;
276 if (offset
& INDEX_NODE_VALUES
) {
280 unsigned int priority
;
282 value_count
= read_long(in
);
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
);
292 strbuf_release(&buf
);
295 node
->prefix
= prefix
;
300 static void index_close(struct index_node_f
*node
)
303 index_values_free(node
->values
);
309 uint32_t root_offset
;
312 struct index_file
*index_file_open(const char *filename
)
315 uint32_t magic
, version
;
316 struct index_file
*new;
318 file
= fopen(filename
, "re");
323 magic
= read_long(file
);
324 if (magic
!= INDEX_MAGIC
) {
329 version
= read_long(file
);
330 if (version
>> 16 != INDEX_VERSION_MAJOR
) {
335 new = NOFAIL(malloc(sizeof(struct index_file
)));
337 new->root_offset
= read_long(new->file
);
343 void index_file_close(struct index_file
*idx
)
349 static struct index_node_f
*index_readroot(struct index_file
*in
)
351 return index_read(in
->file
, in
->root_offset
);
354 static struct index_node_f
*index_readchild(const struct index_node_f
*parent
,
357 if (parent
->first
<= ch
&& ch
<= parent
->last
) {
358 return index_read(parent
->file
,
359 parent
->children
[ch
- parent
->first
]);
365 static void index_dump_node(struct index_node_f
*node
, struct strbuf
*buf
,
368 struct index_value
*v
;
371 pushed
= strbuf_pushchars(buf
, node
->prefix
);
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);
380 for (ch
= node
->first
; ch
<= node
->last
; ch
++) {
381 struct index_node_f
*child
= index_readchild(node
, ch
);
386 strbuf_pushchar(buf
, ch
);
387 index_dump_node(child
, buf
, fd
);
391 strbuf_popchars(buf
, pushed
);
395 void index_dump(struct index_file
*in
, int fd
, const char *prefix
)
397 struct index_node_f
*root
;
400 root
= index_readroot(in
);
405 strbuf_pushchars(&buf
, prefix
);
406 index_dump_node(root
, &buf
, fd
);
407 strbuf_release(&buf
);
410 static char *index_search__node(struct index_node_f
*node
, const char *key
, int i
)
413 struct index_node_f
*child
;
418 for (j
= 0; node
->prefix
[j
]; j
++) {
419 ch
= node
->prefix
[j
];
421 if (ch
!= key
[i
+j
]) {
429 if (key
[i
] == '\0') {
430 value
= node
->values
!= NULL
431 ? strdup(node
->values
[0].value
)
438 child
= index_readchild(node
, key
[i
]);
448 * Search the index for a key
450 * Returns the value of the first match
452 * The recursive functions free their node argument (using index_close).
454 char *index_search(struct index_file
*in
, const char *key
)
456 // FIXME: return value by reference instead of strdup
457 struct index_node_f
*root
;
460 root
= index_readroot(in
);
461 value
= index_search__node(root
, key
, 0);
468 /* Level 4: add all the values from a matching node */
469 static void index_searchwild__allvalues(struct index_node_f
*node
,
470 struct index_value
**out
)
472 struct index_value
*v
;
474 for (v
= node
->values
; v
!= NULL
; v
= v
->next
)
475 add_value(out
, v
->value
, v
->len
, v
->priority
);
481 * Level 3: traverse a sub-keyspace which starts with a wildcard,
482 * looking for matches.
484 static void index_searchwild__all(struct index_node_f
*node
, int j
,
487 struct index_value
**out
)
492 while (node
->prefix
[j
]) {
493 ch
= node
->prefix
[j
];
495 strbuf_pushchar(buf
, ch
);
500 for (ch
= node
->first
; ch
<= node
->last
; ch
++) {
501 struct index_node_f
*child
= index_readchild(node
, ch
);
506 strbuf_pushchar(buf
, ch
);
507 index_searchwild__all(child
, 0, buf
, subkey
, out
);
512 if (fnmatch(strbuf_str(buf
), subkey
, 0) == 0)
513 index_searchwild__allvalues(node
, out
);
520 strbuf_popchars(buf
, pushed
);
523 /* Level 2: descend the tree (until we hit a wildcard) */
524 static void index_searchwild__node(struct index_node_f
*node
,
526 const char *key
, int i
,
527 struct index_value
**out
)
529 struct index_node_f
*child
;
534 for (j
= 0; node
->prefix
[j
]; j
++) {
535 ch
= node
->prefix
[j
];
537 if (ch
== '*' || ch
== '?' || ch
== '[') {
538 index_searchwild__all(node
, j
, buf
,
543 if (ch
!= key
[i
+j
]) {
551 child
= index_readchild(node
, '*');
553 strbuf_pushchar(buf
, '*');
554 index_searchwild__all(child
, 0, buf
, &key
[i
], out
);
558 child
= index_readchild(node
, '?');
560 strbuf_pushchar(buf
, '?');
561 index_searchwild__all(child
, 0, buf
, &key
[i
], out
);
565 child
= index_readchild(node
, '[');
567 strbuf_pushchar(buf
, '[');
568 index_searchwild__all(child
, 0, buf
, &key
[i
], out
);
572 if (key
[i
] == '\0') {
573 index_searchwild__allvalues(node
, out
);
578 child
= index_readchild(node
, key
[i
]);
586 * Search the index for a key. The index may contain wildcards.
588 * Returns a list of all the values of matching keys.
590 struct index_value
*index_searchwild(struct index_file
*in
, const char *key
)
592 struct index_node_f
*root
= index_readroot(in
);
594 struct index_value
*out
= NULL
;
597 index_searchwild__node(root
, &buf
, key
, 0, &out
);
598 strbuf_release(&buf
);
602 /**************************************************************************/
604 * Alternative implementation, using mmap to map all the file to memory when
607 #include <sys/mman.h>
608 #include <sys/stat.h>
611 static const char _idx_empty_str
[] = "";
614 struct kmod_ctx
*ctx
;
616 uint32_t root_offset
;
620 struct index_mm_value
{
621 unsigned int priority
;
626 struct index_mm_value_array
{
627 struct index_mm_value
*values
;
631 struct index_mm_node
{
632 struct index_mm
*idx
;
633 const char *prefix
; /* mmape'd value */
634 struct index_mm_value_array values
;
640 static inline uint32_t read_long_mm(void **p
)
642 uint8_t *addr
= *(uint8_t **)p
;
645 /* addr may be unalined to uint32_t */
646 v
= get_unaligned((uint32_t *) addr
);
648 *p
= addr
+ sizeof(uint32_t);
652 static inline uint8_t read_char_mm(void **p
)
654 uint8_t *addr
= *(uint8_t **)p
;
656 *p
= addr
+ sizeof(uint8_t);
660 static inline char *read_chars_mm(void **p
, unsigned *rlen
)
662 char *addr
= *(char **)p
;
663 size_t len
= *rlen
= strlen(addr
);
668 static struct index_mm_node
*index_mm_read_node(struct index_mm
*idx
,
671 struct index_mm_node
*node
;
673 int i
, child_count
, value_count
, children_padding
;
674 uint32_t children
[INDEX_CHILDMAX
];
677 if ((offset
& INDEX_NODE_MASK
) == 0)
680 p
= (char *)p
+ (offset
& INDEX_NODE_MASK
);
682 if (offset
& INDEX_NODE_PREFIX
) {
684 prefix
= read_chars_mm(&p
, &len
);
686 prefix
= _idx_empty_str
;
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
);
695 first
= INDEX_CHILDMAX
;
700 children_padding
= (sizeof(struct index_mm_node
) +
701 (sizeof(uint32_t) * child_count
)) % sizeof(void *);
703 if (offset
& INDEX_NODE_VALUES
)
704 value_count
= read_long_mm(&p
);
708 node
= malloc(sizeof(struct index_mm_node
)
709 + sizeof(uint32_t) * child_count
+ children_padding
710 + sizeof(struct index_mm_value
) * value_count
);
715 node
->prefix
= prefix
;
716 if (value_count
== 0)
717 node
->values
.values
= NULL
;
719 node
->values
.values
= (struct index_mm_value
*)
720 ((char *)node
+ sizeof(struct index_mm_node
) +
721 sizeof(uint32_t) * child_count
+ children_padding
);
723 node
->values
.len
= value_count
;
726 memcpy(node
->children
, children
, sizeof(uint32_t) * child_count
);
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
);
737 static void index_mm_free_node(struct index_mm_node
*node
)
742 struct index_mm
*index_mm_open(struct kmod_ctx
*ctx
, const char *filename
,
743 unsigned long long *stamp
)
747 struct index_mm
*idx
;
751 uint32_t root_offset
;
755 DBG(ctx
, "file=%s\n", filename
);
757 idx
= malloc(sizeof(*idx
));
759 ERR(ctx
, "malloc: %m\n");
763 if ((fd
= open(filename
, O_RDONLY
|O_CLOEXEC
)) < 0) {
764 DBG(ctx
, "open(%s, O_RDONLY|O_CLOEXEC): %m\n", filename
);
768 if (fstat(fd
, &st
) < 0)
770 if ((size_t) st
.st_size
< sizeof(hdr
))
773 if ((idx
->mm
= mmap(NULL
, st
.st_size
, PROT_READ
, MAP_PRIVATE
, fd
, 0))
775 ERR(ctx
, "mmap(NULL, %"PRIu64
", PROT_READ, %d, MAP_PRIVATE, 0): %m\n",
781 hdr
.magic
= read_long_mm(&p
);
782 hdr
.version
= read_long_mm(&p
);
783 hdr
.root_offset
= read_long_mm(&p
);
785 if (hdr
.magic
!= INDEX_MAGIC
) {
786 ERR(ctx
, "magic check fail: %x instead of %x\n", hdr
.magic
,
791 if (hdr
.version
>> 16 != INDEX_VERSION_MAJOR
) {
792 ERR(ctx
, "major version check fail: %u instead of %u\n",
793 hdr
.version
>> 16, INDEX_VERSION_MAJOR
);
797 idx
->root_offset
= hdr
.root_offset
;
798 idx
->size
= st
.st_size
;
802 *stamp
= stat_mstamp(&st
);
807 munmap(idx
->mm
, st
.st_size
);
815 void index_mm_close(struct index_mm
*idx
)
817 munmap(idx
->mm
, idx
->size
);
821 static struct index_mm_node
*index_mm_readroot(struct index_mm
*idx
)
823 return index_mm_read_node(idx
, idx
->root_offset
);
826 static struct index_mm_node
*index_mm_readchild(const struct index_mm_node
*parent
,
829 if (parent
->first
<= ch
&& ch
<= parent
->last
) {
830 return index_mm_read_node(parent
->idx
,
831 parent
->children
[ch
- parent
->first
]);
837 static void index_mm_dump_node(struct index_mm_node
*node
, struct strbuf
*buf
,
840 struct index_mm_value
*itr
, *itr_end
;
843 pushed
= strbuf_pushchars(buf
, node
->prefix
);
845 itr
= node
->values
.values
;
846 itr_end
= itr
+ node
->values
.len
;
847 for (; itr
< itr_end
; itr
++) {
848 write_str_safe(fd
, buf
->bytes
, buf
->used
);
849 write_str_safe(fd
, " ", 1);
850 write_str_safe(fd
, itr
->value
, itr
->len
);
851 write_str_safe(fd
, "\n", 1);
854 for (ch
= node
->first
; ch
<= node
->last
; ch
++) {
855 struct index_mm_node
*child
= index_mm_readchild(node
, ch
);
860 strbuf_pushchar(buf
, ch
);
861 index_mm_dump_node(child
, buf
, fd
);
865 strbuf_popchars(buf
, pushed
);
866 index_mm_free_node(node
);
869 void index_mm_dump(struct index_mm
*idx
, int fd
, const char *prefix
)
871 struct index_mm_node
*root
;
874 root
= index_mm_readroot(idx
);
879 strbuf_pushchars(&buf
, prefix
);
880 index_mm_dump_node(root
, &buf
, fd
);
881 strbuf_release(&buf
);
884 static char *index_mm_search_node(struct index_mm_node
*node
, const char *key
,
888 struct index_mm_node
*child
;
893 for (j
= 0; node
->prefix
[j
]; j
++) {
894 ch
= node
->prefix
[j
];
896 if (ch
!= key
[i
+j
]) {
897 index_mm_free_node(node
);
904 if (key
[i
] == '\0') {
905 value
= node
->values
.len
> 0
906 ? strdup(node
->values
.values
[0].value
)
909 index_mm_free_node(node
);
913 child
= index_mm_readchild(node
, key
[i
]);
914 index_mm_free_node(node
);
923 * Search the index for a key
925 * Returns the value of the first match
927 * The recursive functions free their node argument (using index_close).
929 char *index_mm_search(struct index_mm
*idx
, const char *key
)
931 // FIXME: return value by reference instead of strdup
932 struct index_mm_node
*root
;
935 root
= index_mm_readroot(idx
);
936 value
= index_mm_search_node(root
, key
, 0);
941 /* Level 4: add all the values from a matching node */
942 static void index_mm_searchwild_allvalues(struct index_mm_node
*node
,
943 struct index_value
**out
)
945 struct index_mm_value
*itr
, *itr_end
;
947 itr
= node
->values
.values
;
948 itr_end
= itr
+ node
->values
.len
;
949 for (; itr
< itr_end
; itr
++)
950 add_value(out
, itr
->value
, itr
->len
, itr
->priority
);
952 index_mm_free_node(node
);
956 * Level 3: traverse a sub-keyspace which starts with a wildcard,
957 * looking for matches.
959 static void index_mm_searchwild_all(struct index_mm_node
*node
, int j
,
962 struct index_value
**out
)
967 while (node
->prefix
[j
]) {
968 ch
= node
->prefix
[j
];
970 strbuf_pushchar(buf
, ch
);
975 for (ch
= node
->first
; ch
<= node
->last
; ch
++) {
976 struct index_mm_node
*child
= index_mm_readchild(node
, ch
);
981 strbuf_pushchar(buf
, ch
);
982 index_mm_searchwild_all(child
, 0, buf
, subkey
, out
);
986 if (node
->values
.len
> 0) {
987 if (fnmatch(strbuf_str(buf
), subkey
, 0) == 0)
988 index_mm_searchwild_allvalues(node
, out
);
990 index_mm_free_node(node
);
992 index_mm_free_node(node
);
995 strbuf_popchars(buf
, pushed
);
998 /* Level 2: descend the tree (until we hit a wildcard) */
999 static void index_mm_searchwild_node(struct index_mm_node
*node
,
1001 const char *key
, int i
,
1002 struct index_value
**out
)
1004 struct index_mm_node
*child
;
1009 for (j
= 0; node
->prefix
[j
]; j
++) {
1010 ch
= node
->prefix
[j
];
1012 if (ch
== '*' || ch
== '?' || ch
== '[') {
1013 index_mm_searchwild_all(node
, j
, buf
,
1018 if (ch
!= key
[i
+j
]) {
1019 index_mm_free_node(node
);
1026 child
= index_mm_readchild(node
, '*');
1028 strbuf_pushchar(buf
, '*');
1029 index_mm_searchwild_all(child
, 0, buf
, &key
[i
], out
);
1030 strbuf_popchar(buf
);
1033 child
= index_mm_readchild(node
, '?');
1035 strbuf_pushchar(buf
, '?');
1036 index_mm_searchwild_all(child
, 0, buf
, &key
[i
], out
);
1037 strbuf_popchar(buf
);
1040 child
= index_mm_readchild(node
, '[');
1042 strbuf_pushchar(buf
, '[');
1043 index_mm_searchwild_all(child
, 0, buf
, &key
[i
], out
);
1044 strbuf_popchar(buf
);
1047 if (key
[i
] == '\0') {
1048 index_mm_searchwild_allvalues(node
, out
);
1053 child
= index_mm_readchild(node
, key
[i
]);
1054 index_mm_free_node(node
);
1061 * Search the index for a key. The index may contain wildcards.
1063 * Returns a list of all the values of matching keys.
1065 struct index_value
*index_mm_searchwild(struct index_mm
*idx
, const char *key
)
1067 struct index_mm_node
*root
= index_mm_readroot(idx
);
1069 struct index_value
*out
= NULL
;
1072 index_mm_searchwild_node(root
, &buf
, key
, 0, &out
);
1073 strbuf_release(&buf
);