]>
Commit | Line | Data |
---|---|---|
8f923be6 LDM |
1 | /* |
2 | * libkmod - interface to kernel module operations | |
3 | * | |
e6b0e49b | 4 | * Copyright (C) 2011-2013 ProFUSION embedded systems |
8f923be6 LDM |
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 | |
cb451f35 LDM |
8 | * License as published by the Free Software Foundation; either |
9 | * version 2.1 of the License, or (at your option) any later version. | |
8f923be6 LDM |
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 | |
dea2dfee | 17 | * License along with this library; if not, see <http://www.gnu.org/licenses/>. |
8f923be6 | 18 | */ |
e8847fd2 | 19 | |
c2e4286b LDM |
20 | #include <arpa/inet.h> |
21 | #include <assert.h> | |
e8847fd2 LDM |
22 | #include <errno.h> |
23 | #include <fnmatch.h> | |
bfcd31de | 24 | #include <inttypes.h> |
c2e4286b LDM |
25 | #include <stdio.h> |
26 | #include <stdlib.h> | |
27 | #include <string.h> | |
e8847fd2 | 28 | |
576dd439 | 29 | #include <shared/macro.h> |
b4d1f44a | 30 | #include <shared/strbuf.h> |
96573a02 | 31 | #include <shared/util.h> |
576dd439 | 32 | |
83b855a6 | 33 | #include "libkmod-internal.h" |
e8847fd2 | 34 | #include "libkmod-index.h" |
e8847fd2 | 35 | |
c4cbdf8e LDM |
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) | |
8f923be6 | 52 | |
c4cbdf8e LDM |
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 | */ | |
148226ed GSB |
60 | #define INDEX_CHILDMAX 128 |
61 | ||
62 | /* Disk format: | |
c4cbdf8e LDM |
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. | |
148226ed GSB |
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 | ||
e8847fd2 LDM |
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 | ||
e8847fd2 | 161 | static int add_value(struct index_value **values, |
1433ba9e | 162 | const char *value, unsigned len, unsigned int priority) |
e8847fd2 LDM |
163 | { |
164 | struct index_value *v; | |
e8847fd2 LDM |
165 | |
166 | /* find position to insert value */ | |
167 | while (*values && (*values)->priority < priority) | |
168 | values = &(*values)->next; | |
169 | ||
1433ba9e GSB |
170 | v = malloc(sizeof(struct index_value) + len + 1); |
171 | if (!v) | |
172 | return -1; | |
e8847fd2 LDM |
173 | v->next = *values; |
174 | v->priority = priority; | |
1433ba9e GSB |
175 | v->len = len; |
176 | memcpy(v->value, value, len); | |
177 | v->value[len] = '\0'; | |
e8847fd2 LDM |
178 | *values = v; |
179 | ||
558b0207 | 180 | return 0; |
e8847fd2 LDM |
181 | } |
182 | ||
93688880 | 183 | static void read_error(void) |
e8847fd2 LDM |
184 | { |
185 | fatal("Module index: unexpected error: %s\n" | |
186 | "Try re-running depmod\n", errno ? strerror(errno) : "EOF"); | |
187 | } | |
188 | ||
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 | ||
200 | static uint32_t read_long(FILE *in) | |
201 | { | |
202 | uint32_t l; | |
203 | ||
204 | errno = 0; | |
b6d985c6 | 205 | if (fread(&l, sizeof(uint32_t), 1, in) != sizeof(uint32_t)) |
e8847fd2 LDM |
206 | read_error(); |
207 | return ntohl(l); | |
208 | } | |
209 | ||
15a7ae30 | 210 | static unsigned buf_freadchars(struct strbuf *buf, FILE *in) |
e8847fd2 LDM |
211 | { |
212 | unsigned i = 0; | |
213 | int ch; | |
214 | ||
215 | while ((ch = read_char(in))) { | |
15a7ae30 | 216 | if (!strbuf_pushchar(buf, ch)) |
405f614a | 217 | break; |
e8847fd2 LDM |
218 | i++; |
219 | } | |
220 | ||
221 | return i; | |
222 | } | |
223 | ||
e8847fd2 | 224 | /* |
eb8bb32e | 225 | * Index file searching |
e8847fd2 | 226 | */ |
e8847fd2 LDM |
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 | ||
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 | fseek(in, offset & INDEX_NODE_MASK, SEEK_SET); | |
a7be73b9 | 246 | |
e8847fd2 | 247 | if (offset & INDEX_NODE_PREFIX) { |
15a7ae30 LDM |
248 | struct strbuf buf; |
249 | strbuf_init(&buf); | |
405f614a | 250 | buf_freadchars(&buf, in); |
15a7ae30 | 251 | prefix = strbuf_steal(&buf); |
e8847fd2 LDM |
252 | } else |
253 | prefix = NOFAIL(strdup("")); | |
a7be73b9 | 254 | |
e8847fd2 LDM |
255 | if (offset & INDEX_NODE_CHILDS) { |
256 | char first = read_char(in); | |
257 | char last = read_char(in); | |
258 | child_count = last - first + 1; | |
a7be73b9 | 259 | |
e8847fd2 LDM |
260 | node = NOFAIL(malloc(sizeof(struct index_node_f) + |
261 | sizeof(uint32_t) * child_count)); | |
a7be73b9 | 262 | |
e8847fd2 LDM |
263 | node->first = first; |
264 | node->last = last; | |
265 | ||
266 | for (i = 0; i < child_count; i++) | |
267 | node->children[i] = read_long(in); | |
268 | } else { | |
269 | node = NOFAIL(malloc(sizeof(struct index_node_f))); | |
270 | node->first = INDEX_CHILDMAX; | |
271 | node->last = 0; | |
272 | } | |
a7be73b9 | 273 | |
e8847fd2 LDM |
274 | node->values = NULL; |
275 | if (offset & INDEX_NODE_VALUES) { | |
276 | int value_count; | |
15a7ae30 | 277 | struct strbuf buf; |
e8847fd2 LDM |
278 | const char *value; |
279 | unsigned int priority; | |
280 | ||
281 | value_count = read_long(in); | |
282 | ||
15a7ae30 | 283 | strbuf_init(&buf); |
e8847fd2 LDM |
284 | while (value_count--) { |
285 | priority = read_long(in); | |
405f614a | 286 | buf_freadchars(&buf, in); |
15a7ae30 | 287 | value = strbuf_str(&buf); |
1433ba9e | 288 | add_value(&node->values, value, buf.used, priority); |
15a7ae30 | 289 | strbuf_clear(&buf); |
e8847fd2 | 290 | } |
15a7ae30 | 291 | strbuf_release(&buf); |
e8847fd2 LDM |
292 | } |
293 | ||
294 | node->prefix = prefix; | |
295 | node->file = in; | |
296 | return node; | |
297 | } | |
298 | ||
299 | static void index_close(struct index_node_f *node) | |
300 | { | |
301 | free(node->prefix); | |
302 | index_values_free(node->values); | |
303 | free(node); | |
304 | } | |
305 | ||
306 | struct index_file { | |
307 | FILE *file; | |
308 | uint32_t root_offset; | |
309 | }; | |
310 | ||
e8847fd2 LDM |
311 | struct index_file *index_file_open(const char *filename) |
312 | { | |
313 | FILE *file; | |
314 | uint32_t magic, version; | |
315 | struct index_file *new; | |
316 | ||
79e5ea91 | 317 | file = fopen(filename, "re"); |
e8847fd2 LDM |
318 | if (!file) |
319 | return NULL; | |
320 | errno = EINVAL; | |
321 | ||
322 | magic = read_long(file); | |
67d94ad3 CR |
323 | if (magic != INDEX_MAGIC) { |
324 | fclose(file); | |
e8847fd2 | 325 | return NULL; |
67d94ad3 | 326 | } |
e8847fd2 LDM |
327 | |
328 | version = read_long(file); | |
4088b27e CR |
329 | if (version >> 16 != INDEX_VERSION_MAJOR) { |
330 | fclose(file); | |
e8847fd2 | 331 | return NULL; |
4088b27e | 332 | } |
e8847fd2 LDM |
333 | |
334 | new = NOFAIL(malloc(sizeof(struct index_file))); | |
335 | new->file = file; | |
336 | new->root_offset = read_long(new->file); | |
337 | ||
338 | errno = 0; | |
339 | return new; | |
340 | } | |
341 | ||
0fbdfef3 | 342 | void index_file_close(struct index_file *idx) |
e8847fd2 | 343 | { |
0fbdfef3 LDM |
344 | fclose(idx->file); |
345 | free(idx); | |
e8847fd2 LDM |
346 | } |
347 | ||
e8847fd2 LDM |
348 | static struct index_node_f *index_readroot(struct index_file *in) |
349 | { | |
350 | return index_read(in->file, in->root_offset); | |
351 | } | |
352 | ||
353 | static struct index_node_f *index_readchild(const struct index_node_f *parent, | |
354 | int ch) | |
355 | { | |
e71970ae | 356 | if (parent->first <= ch && ch <= parent->last) { |
e8847fd2 LDM |
357 | return index_read(parent->file, |
358 | parent->children[ch - parent->first]); | |
e71970ae LDM |
359 | } |
360 | ||
361 | return NULL; | |
e8847fd2 LDM |
362 | } |
363 | ||
15a7ae30 | 364 | static void index_dump_node(struct index_node_f *node, struct strbuf *buf, |
758428a7 LDM |
365 | int fd) |
366 | { | |
367 | struct index_value *v; | |
368 | int ch, pushed; | |
369 | ||
15a7ae30 | 370 | pushed = strbuf_pushchars(buf, node->prefix); |
758428a7 LDM |
371 | |
372 | for (v = node->values; v != NULL; v = v->next) { | |
373 | write_str_safe(fd, buf->bytes, buf->used); | |
374 | write_str_safe(fd, " ", 1); | |
375 | write_str_safe(fd, v->value, strlen(v->value)); | |
376 | write_str_safe(fd, "\n", 1); | |
377 | } | |
378 | ||
379 | for (ch = node->first; ch <= node->last; ch++) { | |
380 | struct index_node_f *child = index_readchild(node, ch); | |
381 | ||
382 | if (!child) | |
383 | continue; | |
384 | ||
15a7ae30 | 385 | strbuf_pushchar(buf, ch); |
758428a7 | 386 | index_dump_node(child, buf, fd); |
15a7ae30 | 387 | strbuf_popchar(buf); |
758428a7 LDM |
388 | } |
389 | ||
15a7ae30 | 390 | strbuf_popchars(buf, pushed); |
758428a7 LDM |
391 | index_close(node); |
392 | } | |
393 | ||
394 | void index_dump(struct index_file *in, int fd, const char *prefix) | |
395 | { | |
396 | struct index_node_f *root; | |
15a7ae30 | 397 | struct strbuf buf; |
758428a7 | 398 | |
681bf89a LDM |
399 | root = index_readroot(in); |
400 | if (root == NULL) | |
401 | return; | |
402 | ||
15a7ae30 LDM |
403 | strbuf_init(&buf); |
404 | strbuf_pushchars(&buf, prefix); | |
758428a7 | 405 | index_dump_node(root, &buf, fd); |
15a7ae30 | 406 | strbuf_release(&buf); |
758428a7 LDM |
407 | } |
408 | ||
e8847fd2 LDM |
409 | static char *index_search__node(struct index_node_f *node, const char *key, int i) |
410 | { | |
411 | char *value; | |
412 | struct index_node_f *child; | |
413 | int ch; | |
414 | int j; | |
415 | ||
416 | while(node) { | |
417 | for (j = 0; node->prefix[j]; j++) { | |
418 | ch = node->prefix[j]; | |
a7be73b9 | 419 | |
e8847fd2 LDM |
420 | if (ch != key[i+j]) { |
421 | index_close(node); | |
422 | return NULL; | |
423 | } | |
424 | } | |
e71970ae | 425 | |
e8847fd2 | 426 | i += j; |
a7be73b9 | 427 | |
e8847fd2 | 428 | if (key[i] == '\0') { |
817f4e33 LDM |
429 | value = node->values != NULL |
430 | ? strdup(node->values[0].value) | |
431 | : NULL; | |
432 | ||
433 | index_close(node); | |
434 | return value; | |
e8847fd2 | 435 | } |
a7be73b9 | 436 | |
e8847fd2 LDM |
437 | child = index_readchild(node, key[i]); |
438 | index_close(node); | |
439 | node = child; | |
440 | i++; | |
441 | } | |
a7be73b9 | 442 | |
e8847fd2 LDM |
443 | return NULL; |
444 | } | |
445 | ||
446 | /* | |
1d152acc | 447 | * Search the index for a key |
e8847fd2 | 448 | * |
1d152acc LDM |
449 | * Returns the value of the first match |
450 | * | |
451 | * The recursive functions free their node argument (using index_close). | |
e8847fd2 | 452 | */ |
1d152acc LDM |
453 | char *index_search(struct index_file *in, const char *key) |
454 | { | |
ee1d188f | 455 | // FIXME: return value by reference instead of strdup |
1d152acc LDM |
456 | struct index_node_f *root; |
457 | char *value; | |
e8847fd2 | 458 | |
1d152acc LDM |
459 | root = index_readroot(in); |
460 | value = index_search__node(root, key, 0); | |
461 | ||
462 | return value; | |
463 | } | |
e8847fd2 | 464 | |
e8847fd2 | 465 | |
e8847fd2 LDM |
466 | |
467 | /* Level 4: add all the values from a matching node */ | |
468 | static void index_searchwild__allvalues(struct index_node_f *node, | |
1d152acc LDM |
469 | struct index_value **out) |
470 | { | |
471 | struct index_value *v; | |
e8847fd2 | 472 | |
1d152acc | 473 | for (v = node->values; v != NULL; v = v->next) |
1433ba9e | 474 | add_value(out, v->value, v->len, v->priority); |
e8847fd2 | 475 | |
1d152acc LDM |
476 | index_close(node); |
477 | } | |
478 | ||
479 | /* | |
480 | * Level 3: traverse a sub-keyspace which starts with a wildcard, | |
481 | * looking for matches. | |
482 | */ | |
483 | static void index_searchwild__all(struct index_node_f *node, int j, | |
15a7ae30 | 484 | struct strbuf *buf, |
1d152acc LDM |
485 | const char *subkey, |
486 | struct index_value **out) | |
e8847fd2 | 487 | { |
1d152acc LDM |
488 | int pushed = 0; |
489 | int ch; | |
a7be73b9 | 490 | |
1d152acc LDM |
491 | while (node->prefix[j]) { |
492 | ch = node->prefix[j]; | |
493 | ||
15a7ae30 | 494 | strbuf_pushchar(buf, ch); |
1d152acc LDM |
495 | pushed++; |
496 | j++; | |
497 | } | |
498 | ||
499 | for (ch = node->first; ch <= node->last; ch++) { | |
500 | struct index_node_f *child = index_readchild(node, ch); | |
501 | ||
502 | if (!child) | |
503 | continue; | |
504 | ||
15a7ae30 | 505 | strbuf_pushchar(buf, ch); |
1d152acc | 506 | index_searchwild__all(child, 0, buf, subkey, out); |
15a7ae30 | 507 | strbuf_popchar(buf); |
1d152acc LDM |
508 | } |
509 | ||
510 | if (node->values) { | |
15a7ae30 | 511 | if (fnmatch(strbuf_str(buf), subkey, 0) == 0) |
1d152acc | 512 | index_searchwild__allvalues(node, out); |
27fdf631 GSB |
513 | else |
514 | index_close(node); | |
1d152acc LDM |
515 | } else { |
516 | index_close(node); | |
517 | } | |
518 | ||
15a7ae30 | 519 | strbuf_popchars(buf, pushed); |
e8847fd2 LDM |
520 | } |
521 | ||
1d152acc | 522 | /* Level 2: descend the tree (until we hit a wildcard) */ |
e8847fd2 | 523 | static void index_searchwild__node(struct index_node_f *node, |
15a7ae30 | 524 | struct strbuf *buf, |
e8847fd2 LDM |
525 | const char *key, int i, |
526 | struct index_value **out) | |
527 | { | |
528 | struct index_node_f *child; | |
529 | int j; | |
530 | int ch; | |
531 | ||
532 | while(node) { | |
533 | for (j = 0; node->prefix[j]; j++) { | |
534 | ch = node->prefix[j]; | |
a7be73b9 | 535 | |
e8847fd2 LDM |
536 | if (ch == '*' || ch == '?' || ch == '[') { |
537 | index_searchwild__all(node, j, buf, | |
538 | &key[i+j], out); | |
539 | return; | |
540 | } | |
a7be73b9 | 541 | |
e8847fd2 LDM |
542 | if (ch != key[i+j]) { |
543 | index_close(node); | |
544 | return; | |
545 | } | |
546 | } | |
e71970ae | 547 | |
e8847fd2 | 548 | i += j; |
a7be73b9 | 549 | |
e8847fd2 LDM |
550 | child = index_readchild(node, '*'); |
551 | if (child) { | |
15a7ae30 | 552 | strbuf_pushchar(buf, '*'); |
e8847fd2 | 553 | index_searchwild__all(child, 0, buf, &key[i], out); |
15a7ae30 | 554 | strbuf_popchar(buf); |
e8847fd2 | 555 | } |
a7be73b9 | 556 | |
e8847fd2 LDM |
557 | child = index_readchild(node, '?'); |
558 | if (child) { | |
15a7ae30 | 559 | strbuf_pushchar(buf, '?'); |
e8847fd2 | 560 | index_searchwild__all(child, 0, buf, &key[i], out); |
15a7ae30 | 561 | strbuf_popchar(buf); |
e8847fd2 | 562 | } |
a7be73b9 | 563 | |
e8847fd2 LDM |
564 | child = index_readchild(node, '['); |
565 | if (child) { | |
15a7ae30 | 566 | strbuf_pushchar(buf, '['); |
e8847fd2 | 567 | index_searchwild__all(child, 0, buf, &key[i], out); |
15a7ae30 | 568 | strbuf_popchar(buf); |
e8847fd2 | 569 | } |
a7be73b9 | 570 | |
e8847fd2 LDM |
571 | if (key[i] == '\0') { |
572 | index_searchwild__allvalues(node, out); | |
573 | ||
574 | return; | |
575 | } | |
a7be73b9 | 576 | |
e8847fd2 LDM |
577 | child = index_readchild(node, key[i]); |
578 | index_close(node); | |
579 | node = child; | |
580 | i++; | |
581 | } | |
582 | } | |
583 | ||
1d152acc LDM |
584 | /* |
585 | * Search the index for a key. The index may contain wildcards. | |
586 | * | |
587 | * Returns a list of all the values of matching keys. | |
588 | */ | |
589 | struct index_value *index_searchwild(struct index_file *in, const char *key) | |
e8847fd2 | 590 | { |
1d152acc | 591 | struct index_node_f *root = index_readroot(in); |
15a7ae30 | 592 | struct strbuf buf; |
1d152acc | 593 | struct index_value *out = NULL; |
e8847fd2 | 594 | |
15a7ae30 | 595 | strbuf_init(&buf); |
405f614a | 596 | index_searchwild__node(root, &buf, key, 0, &out); |
15a7ae30 | 597 | strbuf_release(&buf); |
1d152acc | 598 | return out; |
e8847fd2 | 599 | } |
b471a6b4 | 600 | |
bb72153d LDM |
601 | /**************************************************************************/ |
602 | /* | |
603 | * Alternative implementation, using mmap to map all the file to memory when | |
604 | * starting | |
605 | */ | |
b471a6b4 LDM |
606 | #include <sys/mman.h> |
607 | #include <sys/stat.h> | |
608 | #include <unistd.h> | |
609 | ||
15c1c143 GSB |
610 | static const char _idx_empty_str[] = ""; |
611 | ||
b471a6b4 LDM |
612 | struct index_mm { |
613 | struct kmod_ctx *ctx; | |
614 | void *mm; | |
615 | uint32_t root_offset; | |
616 | size_t size; | |
617 | }; | |
618 | ||
d0915464 GSB |
619 | struct index_mm_value { |
620 | unsigned int priority; | |
621 | unsigned int len; | |
622 | const char *value; | |
623 | }; | |
624 | ||
625 | struct index_mm_value_array { | |
626 | struct index_mm_value *values; | |
627 | unsigned int len; | |
628 | }; | |
629 | ||
836be9ac LDM |
630 | struct index_mm_node { |
631 | struct index_mm *idx; | |
15c1c143 | 632 | const char *prefix; /* mmape'd value */ |
d0915464 | 633 | struct index_mm_value_array values; |
836be9ac LDM |
634 | unsigned char first; |
635 | unsigned char last; | |
636 | uint32_t children[]; | |
637 | }; | |
638 | ||
639 | static inline uint32_t read_long_mm(void **p) | |
640 | { | |
fc2d835d GSB |
641 | uint8_t *addr = *(uint8_t **)p; |
642 | uint32_t v; | |
836be9ac | 643 | |
fc2d835d | 644 | /* addr may be unalined to uint32_t */ |
5bbec8cd | 645 | v = get_unaligned((uint32_t *) addr); |
836be9ac | 646 | |
fc2d835d | 647 | *p = addr + sizeof(uint32_t); |
836be9ac LDM |
648 | return ntohl(v); |
649 | } | |
650 | ||
651 | static inline uint8_t read_char_mm(void **p) | |
652 | { | |
fc2d835d GSB |
653 | uint8_t *addr = *(uint8_t **)p; |
654 | uint8_t v = *addr; | |
655 | *p = addr + sizeof(uint8_t); | |
656 | return v; | |
836be9ac LDM |
657 | } |
658 | ||
1433ba9e | 659 | static inline char *read_chars_mm(void **p, unsigned *rlen) |
836be9ac | 660 | { |
fc2d835d GSB |
661 | char *addr = *(char **)p; |
662 | size_t len = *rlen = strlen(addr); | |
663 | *p = addr + len + 1; | |
664 | return addr; | |
836be9ac LDM |
665 | } |
666 | ||
667 | static struct index_mm_node *index_mm_read_node(struct index_mm *idx, | |
668 | uint32_t offset) { | |
669 | void *p = idx->mm; | |
670 | struct index_mm_node *node; | |
15c1c143 | 671 | const char *prefix; |
d0915464 GSB |
672 | int i, child_count, value_count, children_padding; |
673 | uint32_t children[INDEX_CHILDMAX]; | |
674 | char first, last; | |
836be9ac LDM |
675 | |
676 | if ((offset & INDEX_NODE_MASK) == 0) | |
677 | return NULL; | |
678 | ||
679 | p = (char *)p + (offset & INDEX_NODE_MASK); | |
680 | ||
15c1c143 GSB |
681 | if (offset & INDEX_NODE_PREFIX) { |
682 | unsigned len; | |
683 | prefix = read_chars_mm(&p, &len); | |
684 | } else | |
685 | prefix = _idx_empty_str; | |
836be9ac LDM |
686 | |
687 | if (offset & INDEX_NODE_CHILDS) { | |
d0915464 GSB |
688 | first = read_char_mm(&p); |
689 | last = read_char_mm(&p); | |
836be9ac | 690 | child_count = last - first + 1; |
836be9ac | 691 | for (i = 0; i < child_count; i++) |
d0915464 | 692 | children[i] = read_long_mm(&p); |
836be9ac | 693 | } else { |
d0915464 GSB |
694 | first = INDEX_CHILDMAX; |
695 | last = 0; | |
696 | child_count = 0; | |
836be9ac LDM |
697 | } |
698 | ||
c6824b62 | 699 | children_padding = (sizeof(struct index_mm_node) + |
d0915464 | 700 | (sizeof(uint32_t) * child_count)) % sizeof(void *); |
836be9ac | 701 | |
d0915464 GSB |
702 | if (offset & INDEX_NODE_VALUES) |
703 | value_count = read_long_mm(&p); | |
704 | else | |
705 | value_count = 0; | |
836be9ac | 706 | |
d0915464 GSB |
707 | node = malloc(sizeof(struct index_mm_node) |
708 | + sizeof(uint32_t) * child_count + children_padding | |
709 | + sizeof(struct index_mm_value) * value_count); | |
710 | if (node == NULL) | |
711 | return NULL; | |
836be9ac | 712 | |
836be9ac | 713 | node->idx = idx; |
d0915464 GSB |
714 | node->prefix = prefix; |
715 | if (value_count == 0) | |
716 | node->values.values = NULL; | |
717 | else { | |
718 | node->values.values = (struct index_mm_value *) | |
719 | ((char *)node + sizeof(struct index_mm_node) + | |
720 | sizeof(uint32_t) * child_count + children_padding); | |
721 | } | |
722 | node->values.len = value_count; | |
723 | node->first = first; | |
724 | node->last = last; | |
725 | memcpy(node->children, children, sizeof(uint32_t) * child_count); | |
726 | ||
727 | for (i = 0; i < value_count; i++) { | |
728 | struct index_mm_value *v = node->values.values + i; | |
729 | v->priority = read_long_mm(&p); | |
730 | v->value = read_chars_mm(&p, &v->len); | |
731 | } | |
836be9ac LDM |
732 | |
733 | return node; | |
734 | } | |
735 | ||
736 | static void index_mm_free_node(struct index_mm_node *node) | |
737 | { | |
836be9ac LDM |
738 | free(node); |
739 | } | |
740 | ||
5109f2b4 | 741 | struct index_mm *index_mm_open(struct kmod_ctx *ctx, const char *filename, |
2e2e252b | 742 | unsigned long long *stamp) |
b471a6b4 LDM |
743 | { |
744 | int fd; | |
745 | struct stat st; | |
746 | struct index_mm *idx; | |
747 | struct { | |
748 | uint32_t magic; | |
749 | uint32_t version; | |
750 | uint32_t root_offset; | |
751 | } hdr; | |
752 | void *p; | |
753 | ||
754 | DBG(ctx, "file=%s\n", filename); | |
755 | ||
7d51d8bf LDM |
756 | idx = malloc(sizeof(*idx)); |
757 | if (idx == NULL) { | |
dfa96f15 | 758 | ERR(ctx, "malloc: %m\n"); |
b471a6b4 LDM |
759 | return NULL; |
760 | } | |
761 | ||
79e5ea91 | 762 | if ((fd = open(filename, O_RDONLY|O_CLOEXEC)) < 0) { |
73298175 | 763 | DBG(ctx, "open(%s, O_RDONLY|O_CLOEXEC): %m\n", filename); |
7d51d8bf | 764 | goto fail_open; |
b471a6b4 LDM |
765 | } |
766 | ||
d36c886a LP |
767 | if (fstat(fd, &st) < 0) |
768 | goto fail_nommap; | |
5b05c327 LDM |
769 | if ((size_t) st.st_size < sizeof(hdr)) |
770 | goto fail_nommap; | |
5109f2b4 | 771 | |
c3e8d269 | 772 | if ((idx->mm = mmap(NULL, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0)) |
5109f2b4 | 773 | == MAP_FAILED) { |
c3e8d269 | 774 | ERR(ctx, "mmap(NULL, %"PRIu64", PROT_READ, %d, MAP_PRIVATE, 0): %m\n", |
2e2e252b | 775 | st.st_size, fd); |
5b05c327 | 776 | goto fail_nommap; |
b471a6b4 LDM |
777 | } |
778 | ||
779 | p = idx->mm; | |
780 | hdr.magic = read_long_mm(&p); | |
781 | hdr.version = read_long_mm(&p); | |
782 | hdr.root_offset = read_long_mm(&p); | |
783 | ||
784 | if (hdr.magic != INDEX_MAGIC) { | |
785 | ERR(ctx, "magic check fail: %x instead of %x\n", hdr.magic, | |
786 | INDEX_MAGIC); | |
787 | goto fail; | |
788 | } | |
789 | ||
790 | if (hdr.version >> 16 != INDEX_VERSION_MAJOR) { | |
791 | ERR(ctx, "major version check fail: %u instead of %u\n", | |
1a4aa7e2 | 792 | hdr.version >> 16, INDEX_VERSION_MAJOR); |
b471a6b4 LDM |
793 | goto fail; |
794 | } | |
795 | ||
796 | idx->root_offset = hdr.root_offset; | |
797 | idx->size = st.st_size; | |
798 | idx->ctx = ctx; | |
799 | close(fd); | |
800 | ||
6068aaae | 801 | *stamp = stat_mstamp(&st); |
9fd58f30 | 802 | |
b471a6b4 LDM |
803 | return idx; |
804 | ||
805 | fail: | |
5b05c327 LDM |
806 | munmap(idx->mm, st.st_size); |
807 | fail_nommap: | |
b471a6b4 | 808 | close(fd); |
a5a92a61 | 809 | fail_open: |
b471a6b4 LDM |
810 | free(idx); |
811 | return NULL; | |
812 | } | |
813 | ||
814 | void index_mm_close(struct index_mm *idx) | |
815 | { | |
816 | munmap(idx->mm, idx->size); | |
817 | free(idx); | |
818 | } | |
77bf936a LDM |
819 | |
820 | static struct index_mm_node *index_mm_readroot(struct index_mm *idx) | |
821 | { | |
822 | return index_mm_read_node(idx, idx->root_offset); | |
823 | } | |
91298dc7 LDM |
824 | |
825 | static struct index_mm_node *index_mm_readchild(const struct index_mm_node *parent, | |
826 | int ch) | |
827 | { | |
828 | if (parent->first <= ch && ch <= parent->last) { | |
829 | return index_mm_read_node(parent->idx, | |
830 | parent->children[ch - parent->first]); | |
831 | } | |
832 | ||
833 | return NULL; | |
834 | } | |
e33bb87c | 835 | |
15a7ae30 | 836 | static void index_mm_dump_node(struct index_mm_node *node, struct strbuf *buf, |
758428a7 LDM |
837 | int fd) |
838 | { | |
839 | struct index_mm_value *itr, *itr_end; | |
840 | int ch, pushed; | |
841 | ||
15a7ae30 | 842 | pushed = strbuf_pushchars(buf, node->prefix); |
758428a7 LDM |
843 | |
844 | itr = node->values.values; | |
845 | itr_end = itr + node->values.len; | |
846 | for (; itr < itr_end; itr++) { | |
847 | write_str_safe(fd, buf->bytes, buf->used); | |
848 | write_str_safe(fd, " ", 1); | |
849 | write_str_safe(fd, itr->value, itr->len); | |
850 | write_str_safe(fd, "\n", 1); | |
851 | } | |
852 | ||
853 | for (ch = node->first; ch <= node->last; ch++) { | |
854 | struct index_mm_node *child = index_mm_readchild(node, ch); | |
855 | ||
856 | if (child == NULL) | |
857 | continue; | |
858 | ||
15a7ae30 | 859 | strbuf_pushchar(buf, ch); |
758428a7 | 860 | index_mm_dump_node(child, buf, fd); |
15a7ae30 | 861 | strbuf_popchar(buf); |
758428a7 LDM |
862 | } |
863 | ||
15a7ae30 | 864 | strbuf_popchars(buf, pushed); |
758428a7 LDM |
865 | index_mm_free_node(node); |
866 | } | |
867 | ||
868 | void index_mm_dump(struct index_mm *idx, int fd, const char *prefix) | |
869 | { | |
870 | struct index_mm_node *root; | |
15a7ae30 | 871 | struct strbuf buf; |
758428a7 | 872 | |
681bf89a LDM |
873 | root = index_mm_readroot(idx); |
874 | if (root == NULL) | |
875 | return; | |
876 | ||
15a7ae30 LDM |
877 | strbuf_init(&buf); |
878 | strbuf_pushchars(&buf, prefix); | |
758428a7 | 879 | index_mm_dump_node(root, &buf, fd); |
15a7ae30 | 880 | strbuf_release(&buf); |
758428a7 LDM |
881 | } |
882 | ||
e33bb87c LDM |
883 | static char *index_mm_search_node(struct index_mm_node *node, const char *key, |
884 | int i) | |
885 | { | |
886 | char *value; | |
887 | struct index_mm_node *child; | |
888 | int ch; | |
889 | int j; | |
890 | ||
891 | while(node) { | |
892 | for (j = 0; node->prefix[j]; j++) { | |
893 | ch = node->prefix[j]; | |
894 | ||
895 | if (ch != key[i+j]) { | |
896 | index_mm_free_node(node); | |
897 | return NULL; | |
898 | } | |
899 | } | |
900 | ||
901 | i += j; | |
902 | ||
903 | if (key[i] == '\0') { | |
817f4e33 LDM |
904 | value = node->values.len > 0 |
905 | ? strdup(node->values.values[0].value) | |
906 | : NULL; | |
907 | ||
908 | index_mm_free_node(node); | |
909 | return value; | |
e33bb87c LDM |
910 | } |
911 | ||
912 | child = index_mm_readchild(node, key[i]); | |
913 | index_mm_free_node(node); | |
914 | node = child; | |
915 | i++; | |
916 | } | |
917 | ||
918 | return NULL; | |
919 | } | |
b797b791 LDM |
920 | |
921 | /* | |
922 | * Search the index for a key | |
923 | * | |
924 | * Returns the value of the first match | |
925 | * | |
926 | * The recursive functions free their node argument (using index_close). | |
927 | */ | |
928 | char *index_mm_search(struct index_mm *idx, const char *key) | |
929 | { | |
ee1d188f | 930 | // FIXME: return value by reference instead of strdup |
b797b791 LDM |
931 | struct index_mm_node *root; |
932 | char *value; | |
933 | ||
934 | root = index_mm_readroot(idx); | |
935 | value = index_mm_search_node(root, key, 0); | |
936 | ||
937 | return value; | |
938 | } | |
bf89f70c LDM |
939 | |
940 | /* Level 4: add all the values from a matching node */ | |
941 | static void index_mm_searchwild_allvalues(struct index_mm_node *node, | |
942 | struct index_value **out) | |
943 | { | |
d0915464 | 944 | struct index_mm_value *itr, *itr_end; |
bf89f70c | 945 | |
d0915464 GSB |
946 | itr = node->values.values; |
947 | itr_end = itr + node->values.len; | |
948 | for (; itr < itr_end; itr++) | |
949 | add_value(out, itr->value, itr->len, itr->priority); | |
bf89f70c LDM |
950 | |
951 | index_mm_free_node(node); | |
952 | } | |
953 | ||
954 | /* | |
955 | * Level 3: traverse a sub-keyspace which starts with a wildcard, | |
956 | * looking for matches. | |
957 | */ | |
958 | static void index_mm_searchwild_all(struct index_mm_node *node, int j, | |
15a7ae30 | 959 | struct strbuf *buf, |
bf89f70c LDM |
960 | const char *subkey, |
961 | struct index_value **out) | |
962 | { | |
963 | int pushed = 0; | |
964 | int ch; | |
965 | ||
966 | while (node->prefix[j]) { | |
967 | ch = node->prefix[j]; | |
968 | ||
15a7ae30 | 969 | strbuf_pushchar(buf, ch); |
bf89f70c LDM |
970 | pushed++; |
971 | j++; | |
972 | } | |
973 | ||
974 | for (ch = node->first; ch <= node->last; ch++) { | |
975 | struct index_mm_node *child = index_mm_readchild(node, ch); | |
976 | ||
977 | if (!child) | |
978 | continue; | |
979 | ||
15a7ae30 | 980 | strbuf_pushchar(buf, ch); |
bf89f70c | 981 | index_mm_searchwild_all(child, 0, buf, subkey, out); |
15a7ae30 | 982 | strbuf_popchar(buf); |
bf89f70c LDM |
983 | } |
984 | ||
d0915464 | 985 | if (node->values.len > 0) { |
15a7ae30 | 986 | if (fnmatch(strbuf_str(buf), subkey, 0) == 0) |
bf89f70c | 987 | index_mm_searchwild_allvalues(node, out); |
27fdf631 GSB |
988 | else |
989 | index_mm_free_node(node); | |
bf89f70c LDM |
990 | } else { |
991 | index_mm_free_node(node); | |
992 | } | |
993 | ||
15a7ae30 | 994 | strbuf_popchars(buf, pushed); |
bf89f70c LDM |
995 | } |
996 | ||
997 | /* Level 2: descend the tree (until we hit a wildcard) */ | |
998 | static void index_mm_searchwild_node(struct index_mm_node *node, | |
15a7ae30 | 999 | struct strbuf *buf, |
bf89f70c LDM |
1000 | const char *key, int i, |
1001 | struct index_value **out) | |
1002 | { | |
1003 | struct index_mm_node *child; | |
1004 | int j; | |
1005 | int ch; | |
1006 | ||
1007 | while(node) { | |
1008 | for (j = 0; node->prefix[j]; j++) { | |
1009 | ch = node->prefix[j]; | |
1010 | ||
1011 | if (ch == '*' || ch == '?' || ch == '[') { | |
1012 | index_mm_searchwild_all(node, j, buf, | |
1013 | &key[i+j], out); | |
1014 | return; | |
1015 | } | |
1016 | ||
1017 | if (ch != key[i+j]) { | |
1018 | index_mm_free_node(node); | |
1019 | return; | |
1020 | } | |
1021 | } | |
1022 | ||
1023 | i += j; | |
1024 | ||
1025 | child = index_mm_readchild(node, '*'); | |
1026 | if (child) { | |
15a7ae30 | 1027 | strbuf_pushchar(buf, '*'); |
bf89f70c | 1028 | index_mm_searchwild_all(child, 0, buf, &key[i], out); |
15a7ae30 | 1029 | strbuf_popchar(buf); |
bf89f70c LDM |
1030 | } |
1031 | ||
1032 | child = index_mm_readchild(node, '?'); | |
1033 | if (child) { | |
15a7ae30 | 1034 | strbuf_pushchar(buf, '?'); |
bf89f70c | 1035 | index_mm_searchwild_all(child, 0, buf, &key[i], out); |
15a7ae30 | 1036 | strbuf_popchar(buf); |
bf89f70c LDM |
1037 | } |
1038 | ||
1039 | child = index_mm_readchild(node, '['); | |
1040 | if (child) { | |
15a7ae30 | 1041 | strbuf_pushchar(buf, '['); |
bf89f70c | 1042 | index_mm_searchwild_all(child, 0, buf, &key[i], out); |
15a7ae30 | 1043 | strbuf_popchar(buf); |
bf89f70c LDM |
1044 | } |
1045 | ||
1046 | if (key[i] == '\0') { | |
1047 | index_mm_searchwild_allvalues(node, out); | |
1048 | ||
1049 | return; | |
1050 | } | |
1051 | ||
1052 | child = index_mm_readchild(node, key[i]); | |
1053 | index_mm_free_node(node); | |
1054 | node = child; | |
1055 | i++; | |
1056 | } | |
1057 | } | |
1058 | ||
1059 | /* | |
1060 | * Search the index for a key. The index may contain wildcards. | |
1061 | * | |
1062 | * Returns a list of all the values of matching keys. | |
1063 | */ | |
1064 | struct index_value *index_mm_searchwild(struct index_mm *idx, const char *key) | |
1065 | { | |
1066 | struct index_mm_node *root = index_mm_readroot(idx); | |
15a7ae30 | 1067 | struct strbuf buf; |
bf89f70c LDM |
1068 | struct index_value *out = NULL; |
1069 | ||
15a7ae30 | 1070 | strbuf_init(&buf); |
405f614a | 1071 | index_mm_searchwild_node(root, &buf, key, 0, &out); |
15a7ae30 | 1072 | strbuf_release(&buf); |
bf89f70c LDM |
1073 | return out; |
1074 | } |