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