]>
Commit | Line | Data |
---|---|---|
8f923be6 LDM |
1 | /* |
2 | * libkmod - interface to kernel module operations | |
3 | * | |
a66a6a99 | 4 | * Copyright (C) 2011-2012 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 | |
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 | |
19 | */ | |
e8847fd2 LDM |
20 | |
21 | #include <arpa/inet.h> /* htonl */ | |
22 | #include <stdlib.h> | |
23 | #include <stdio.h> | |
24 | #include <string.h> | |
25 | #include <errno.h> | |
26 | #include <fnmatch.h> | |
405f614a | 27 | #include <assert.h> |
bfcd31de | 28 | #include <inttypes.h> |
e8847fd2 LDM |
29 | |
30 | #include "libkmod-private.h" | |
31 | #include "libkmod-index.h" | |
32 | #include "macro.h" | |
33 | ||
8f923be6 LDM |
34 | /* index.c: module index file shared functions for modprobe and depmod */ |
35 | ||
148226ed GSB |
36 | #define INDEX_CHILDMAX 128 |
37 | ||
38 | /* Disk format: | |
39 | ||
40 | uint32_t magic = INDEX_MAGIC; | |
41 | uint32_t version = INDEX_VERSION; | |
42 | uint32_t root_offset; | |
43 | ||
44 | (node_offset & INDEX_NODE_MASK) specifies the file offset of nodes: | |
45 | ||
46 | char[] prefix; // nul terminated | |
47 | ||
48 | char first; | |
49 | char last; | |
50 | uint32_t children[last - first + 1]; | |
51 | ||
52 | uint32_t value_count; | |
53 | struct { | |
54 | uint32_t priority; | |
55 | char[] value; // nul terminated | |
56 | } values[value_count]; | |
57 | ||
58 | (node_offset & INDEX_NODE_FLAGS) indicates which fields are present. | |
59 | Empty prefixes are omitted, leaf nodes omit the three child-related fields. | |
60 | ||
61 | This could be optimised further by adding a sparse child format | |
62 | (indicated using a new flag). | |
63 | */ | |
64 | ||
65 | /* Format of node offsets within index file */ | |
66 | enum node_offset { | |
67 | INDEX_NODE_FLAGS = 0xF0000000, /* Flags in high nibble */ | |
68 | INDEX_NODE_PREFIX = 0x80000000, | |
69 | INDEX_NODE_VALUES = 0x40000000, | |
70 | INDEX_NODE_CHILDS = 0x20000000, | |
71 | ||
72 | INDEX_NODE_MASK = 0x0FFFFFFF, /* Offset value */ | |
73 | }; | |
74 | ||
e8847fd2 LDM |
75 | void index_values_free(struct index_value *values) |
76 | { | |
77 | while (values) { | |
78 | struct index_value *value = values; | |
79 | ||
80 | values = value->next; | |
81 | free(value); | |
82 | } | |
83 | } | |
84 | ||
e8847fd2 | 85 | static int add_value(struct index_value **values, |
1433ba9e | 86 | const char *value, unsigned len, unsigned int priority) |
e8847fd2 LDM |
87 | { |
88 | struct index_value *v; | |
e8847fd2 LDM |
89 | |
90 | /* find position to insert value */ | |
91 | while (*values && (*values)->priority < priority) | |
92 | values = &(*values)->next; | |
93 | ||
1433ba9e GSB |
94 | v = malloc(sizeof(struct index_value) + len + 1); |
95 | if (!v) | |
96 | return -1; | |
e8847fd2 LDM |
97 | v->next = *values; |
98 | v->priority = priority; | |
1433ba9e GSB |
99 | v->len = len; |
100 | memcpy(v->value, value, len); | |
101 | v->value[len] = '\0'; | |
e8847fd2 LDM |
102 | *values = v; |
103 | ||
558b0207 | 104 | return 0; |
e8847fd2 LDM |
105 | } |
106 | ||
93688880 | 107 | static void read_error(void) |
e8847fd2 LDM |
108 | { |
109 | fatal("Module index: unexpected error: %s\n" | |
110 | "Try re-running depmod\n", errno ? strerror(errno) : "EOF"); | |
111 | } | |
112 | ||
113 | static int read_char(FILE *in) | |
114 | { | |
115 | int ch; | |
116 | ||
117 | errno = 0; | |
118 | ch = getc_unlocked(in); | |
119 | if (ch == EOF) | |
120 | read_error(); | |
121 | return ch; | |
122 | } | |
123 | ||
124 | static uint32_t read_long(FILE *in) | |
125 | { | |
126 | uint32_t l; | |
127 | ||
128 | errno = 0; | |
129 | if (fread(&l, sizeof(uint32_t), 1, in) <= 0) | |
130 | read_error(); | |
131 | return ntohl(l); | |
132 | } | |
133 | ||
134 | /* | |
135 | * Buffer abstract data type | |
136 | * | |
137 | * Used internally to store the current path during tree traversal. | |
138 | * They help build wildcard key strings to pass to fnmatch(), | |
139 | * as well as building values of matching keys. | |
140 | */ | |
e8847fd2 LDM |
141 | struct buffer { |
142 | char *bytes; | |
143 | unsigned size; | |
144 | unsigned used; | |
145 | }; | |
146 | ||
405f614a GSB |
147 | #define BUF_STEP (2048) |
148 | static bool buf_grow(struct buffer *buf, size_t newsize) | |
e8847fd2 | 149 | { |
405f614a GSB |
150 | void *tmp; |
151 | size_t sz; | |
152 | ||
153 | if (newsize % BUF_STEP == 0) | |
154 | sz = newsize; | |
155 | else | |
156 | sz = ((newsize / BUF_STEP) + 1) * BUF_STEP; | |
157 | ||
435ad788 GSB |
158 | if (buf->size == sz) |
159 | return true; | |
160 | ||
405f614a GSB |
161 | tmp = realloc(buf->bytes, sz); |
162 | if (sz > 0 && tmp == NULL) | |
163 | return false; | |
164 | buf->bytes = tmp; | |
165 | buf->size = sz; | |
166 | return true; | |
e8847fd2 LDM |
167 | } |
168 | ||
405f614a | 169 | static void buf_init(struct buffer *buf) |
e8847fd2 | 170 | { |
405f614a GSB |
171 | buf->bytes = NULL; |
172 | buf->size = 0; | |
173 | buf->used = 0; | |
e8847fd2 LDM |
174 | } |
175 | ||
405f614a | 176 | static void buf_release(struct buffer *buf) |
e8847fd2 LDM |
177 | { |
178 | free(buf->bytes); | |
e8847fd2 LDM |
179 | } |
180 | ||
181 | /* Destroy buffer and return a copy as a C string */ | |
405f614a | 182 | static char *buf_steal(struct buffer *buf) |
e8847fd2 LDM |
183 | { |
184 | char *bytes; | |
185 | ||
405f614a GSB |
186 | bytes = realloc(buf->bytes, buf->used + 1); |
187 | if (!bytes) { | |
188 | free(buf->bytes); | |
189 | return NULL; | |
190 | } | |
e8847fd2 | 191 | bytes[buf->used] = '\0'; |
e8847fd2 LDM |
192 | return bytes; |
193 | } | |
194 | ||
195 | /* Return a C string owned by the buffer | |
196 | (invalidated if the buffer is changed). | |
197 | */ | |
198 | static const char *buf_str(struct buffer *buf) | |
199 | { | |
405f614a GSB |
200 | if (!buf_grow(buf, buf->used + 1)) |
201 | return NULL; | |
e8847fd2 LDM |
202 | buf->bytes[buf->used] = '\0'; |
203 | return buf->bytes; | |
204 | } | |
205 | ||
405f614a | 206 | static bool buf_pushchar(struct buffer *buf, char ch) |
e8847fd2 | 207 | { |
405f614a GSB |
208 | if (!buf_grow(buf, buf->used + 1)) |
209 | return false; | |
e8847fd2 LDM |
210 | buf->bytes[buf->used] = ch; |
211 | buf->used++; | |
405f614a | 212 | return true; |
e8847fd2 LDM |
213 | } |
214 | ||
758428a7 LDM |
215 | static unsigned buf_pushchars(struct buffer *buf, const char *str) |
216 | { | |
217 | unsigned i = 0; | |
218 | int ch; | |
219 | ||
220 | while ((ch = str[i])) { | |
221 | buf_pushchar(buf, ch); | |
222 | i++; | |
223 | } | |
224 | ||
225 | return i; | |
226 | } | |
227 | ||
e8847fd2 LDM |
228 | static unsigned buf_freadchars(struct buffer *buf, FILE *in) |
229 | { | |
230 | unsigned i = 0; | |
231 | int ch; | |
232 | ||
233 | while ((ch = read_char(in))) { | |
405f614a GSB |
234 | if (!buf_pushchar(buf, ch)) |
235 | break; | |
e8847fd2 LDM |
236 | i++; |
237 | } | |
238 | ||
239 | return i; | |
240 | } | |
241 | ||
242 | static void buf_popchar(struct buffer *buf) | |
243 | { | |
405f614a | 244 | assert(buf->used > 0); |
e8847fd2 LDM |
245 | buf->used--; |
246 | } | |
247 | ||
248 | static void buf_popchars(struct buffer *buf, unsigned n) | |
249 | { | |
405f614a | 250 | assert(buf->used >= n); |
e8847fd2 LDM |
251 | buf->used -= n; |
252 | } | |
253 | ||
254 | static void buf_clear(struct buffer *buf) | |
255 | { | |
256 | buf->used = 0; | |
257 | } | |
258 | ||
259 | /* | |
eb8bb32e | 260 | * Index file searching |
e8847fd2 | 261 | */ |
e8847fd2 LDM |
262 | struct index_node_f { |
263 | FILE *file; | |
264 | char *prefix; /* path compression */ | |
265 | struct index_value *values; | |
266 | unsigned char first; /* range of child nodes */ | |
267 | unsigned char last; | |
268 | uint32_t children[0]; | |
269 | }; | |
270 | ||
271 | static struct index_node_f *index_read(FILE *in, uint32_t offset) | |
272 | { | |
273 | struct index_node_f *node; | |
274 | char *prefix; | |
275 | int i, child_count = 0; | |
276 | ||
277 | if ((offset & INDEX_NODE_MASK) == 0) | |
278 | return NULL; | |
279 | ||
280 | fseek(in, offset & INDEX_NODE_MASK, SEEK_SET); | |
a7be73b9 | 281 | |
e8847fd2 | 282 | if (offset & INDEX_NODE_PREFIX) { |
405f614a GSB |
283 | struct buffer buf; |
284 | buf_init(&buf); | |
285 | buf_freadchars(&buf, in); | |
286 | prefix = buf_steal(&buf); | |
e8847fd2 LDM |
287 | } else |
288 | prefix = NOFAIL(strdup("")); | |
a7be73b9 | 289 | |
e8847fd2 LDM |
290 | if (offset & INDEX_NODE_CHILDS) { |
291 | char first = read_char(in); | |
292 | char last = read_char(in); | |
293 | child_count = last - first + 1; | |
a7be73b9 | 294 | |
e8847fd2 LDM |
295 | node = NOFAIL(malloc(sizeof(struct index_node_f) + |
296 | sizeof(uint32_t) * child_count)); | |
a7be73b9 | 297 | |
e8847fd2 LDM |
298 | node->first = first; |
299 | node->last = last; | |
300 | ||
301 | for (i = 0; i < child_count; i++) | |
302 | node->children[i] = read_long(in); | |
303 | } else { | |
304 | node = NOFAIL(malloc(sizeof(struct index_node_f))); | |
305 | node->first = INDEX_CHILDMAX; | |
306 | node->last = 0; | |
307 | } | |
a7be73b9 | 308 | |
e8847fd2 LDM |
309 | node->values = NULL; |
310 | if (offset & INDEX_NODE_VALUES) { | |
311 | int value_count; | |
405f614a | 312 | struct buffer buf; |
e8847fd2 LDM |
313 | const char *value; |
314 | unsigned int priority; | |
315 | ||
316 | value_count = read_long(in); | |
317 | ||
405f614a | 318 | buf_init(&buf); |
e8847fd2 LDM |
319 | while (value_count--) { |
320 | priority = read_long(in); | |
405f614a GSB |
321 | buf_freadchars(&buf, in); |
322 | value = buf_str(&buf); | |
1433ba9e | 323 | add_value(&node->values, value, buf.used, priority); |
405f614a | 324 | buf_clear(&buf); |
e8847fd2 | 325 | } |
405f614a | 326 | buf_release(&buf); |
e8847fd2 LDM |
327 | } |
328 | ||
329 | node->prefix = prefix; | |
330 | node->file = in; | |
331 | return node; | |
332 | } | |
333 | ||
334 | static void index_close(struct index_node_f *node) | |
335 | { | |
336 | free(node->prefix); | |
337 | index_values_free(node->values); | |
338 | free(node); | |
339 | } | |
340 | ||
341 | struct index_file { | |
342 | FILE *file; | |
343 | uint32_t root_offset; | |
344 | }; | |
345 | ||
346 | /* Failures are silent; modprobe will fall back to text files */ | |
347 | struct index_file *index_file_open(const char *filename) | |
348 | { | |
349 | FILE *file; | |
350 | uint32_t magic, version; | |
351 | struct index_file *new; | |
352 | ||
79e5ea91 | 353 | file = fopen(filename, "re"); |
e8847fd2 LDM |
354 | if (!file) |
355 | return NULL; | |
356 | errno = EINVAL; | |
357 | ||
358 | magic = read_long(file); | |
67d94ad3 CR |
359 | if (magic != INDEX_MAGIC) { |
360 | fclose(file); | |
e8847fd2 | 361 | return NULL; |
67d94ad3 | 362 | } |
e8847fd2 LDM |
363 | |
364 | version = read_long(file); | |
4088b27e CR |
365 | if (version >> 16 != INDEX_VERSION_MAJOR) { |
366 | fclose(file); | |
e8847fd2 | 367 | return NULL; |
4088b27e | 368 | } |
e8847fd2 LDM |
369 | |
370 | new = NOFAIL(malloc(sizeof(struct index_file))); | |
371 | new->file = file; | |
372 | new->root_offset = read_long(new->file); | |
373 | ||
374 | errno = 0; | |
375 | return new; | |
376 | } | |
377 | ||
0fbdfef3 | 378 | void index_file_close(struct index_file *idx) |
e8847fd2 | 379 | { |
0fbdfef3 LDM |
380 | fclose(idx->file); |
381 | free(idx); | |
e8847fd2 LDM |
382 | } |
383 | ||
e8847fd2 LDM |
384 | static struct index_node_f *index_readroot(struct index_file *in) |
385 | { | |
386 | return index_read(in->file, in->root_offset); | |
387 | } | |
388 | ||
389 | static struct index_node_f *index_readchild(const struct index_node_f *parent, | |
390 | int ch) | |
391 | { | |
e71970ae | 392 | if (parent->first <= ch && ch <= parent->last) { |
e8847fd2 LDM |
393 | return index_read(parent->file, |
394 | parent->children[ch - parent->first]); | |
e71970ae LDM |
395 | } |
396 | ||
397 | return NULL; | |
e8847fd2 LDM |
398 | } |
399 | ||
758428a7 LDM |
400 | static void index_dump_node(struct index_node_f *node, struct buffer *buf, |
401 | int fd) | |
402 | { | |
403 | struct index_value *v; | |
404 | int ch, pushed; | |
405 | ||
406 | pushed = buf_pushchars(buf, node->prefix); | |
407 | ||
408 | for (v = node->values; v != NULL; v = v->next) { | |
409 | write_str_safe(fd, buf->bytes, buf->used); | |
410 | write_str_safe(fd, " ", 1); | |
411 | write_str_safe(fd, v->value, strlen(v->value)); | |
412 | write_str_safe(fd, "\n", 1); | |
413 | } | |
414 | ||
415 | for (ch = node->first; ch <= node->last; ch++) { | |
416 | struct index_node_f *child = index_readchild(node, ch); | |
417 | ||
418 | if (!child) | |
419 | continue; | |
420 | ||
421 | buf_pushchar(buf, ch); | |
422 | index_dump_node(child, buf, fd); | |
423 | buf_popchar(buf); | |
424 | } | |
425 | ||
426 | buf_popchars(buf, pushed); | |
427 | index_close(node); | |
428 | } | |
429 | ||
430 | void index_dump(struct index_file *in, int fd, const char *prefix) | |
431 | { | |
432 | struct index_node_f *root; | |
433 | struct buffer buf; | |
434 | ||
435 | buf_init(&buf); | |
436 | buf_pushchars(&buf, prefix); | |
437 | root = index_readroot(in); | |
438 | index_dump_node(root, &buf, fd); | |
439 | buf_release(&buf); | |
440 | } | |
441 | ||
e8847fd2 LDM |
442 | static char *index_search__node(struct index_node_f *node, const char *key, int i) |
443 | { | |
444 | char *value; | |
445 | struct index_node_f *child; | |
446 | int ch; | |
447 | int j; | |
448 | ||
449 | while(node) { | |
450 | for (j = 0; node->prefix[j]; j++) { | |
451 | ch = node->prefix[j]; | |
a7be73b9 | 452 | |
e8847fd2 LDM |
453 | if (ch != key[i+j]) { |
454 | index_close(node); | |
455 | return NULL; | |
456 | } | |
457 | } | |
e71970ae | 458 | |
e8847fd2 | 459 | i += j; |
a7be73b9 | 460 | |
e8847fd2 | 461 | if (key[i] == '\0') { |
817f4e33 LDM |
462 | value = node->values != NULL |
463 | ? strdup(node->values[0].value) | |
464 | : NULL; | |
465 | ||
466 | index_close(node); | |
467 | return value; | |
e8847fd2 | 468 | } |
a7be73b9 | 469 | |
e8847fd2 LDM |
470 | child = index_readchild(node, key[i]); |
471 | index_close(node); | |
472 | node = child; | |
473 | i++; | |
474 | } | |
a7be73b9 | 475 | |
e8847fd2 LDM |
476 | return NULL; |
477 | } | |
478 | ||
479 | /* | |
1d152acc | 480 | * Search the index for a key |
e8847fd2 | 481 | * |
1d152acc LDM |
482 | * Returns the value of the first match |
483 | * | |
484 | * The recursive functions free their node argument (using index_close). | |
e8847fd2 | 485 | */ |
1d152acc LDM |
486 | char *index_search(struct index_file *in, const char *key) |
487 | { | |
ee1d188f | 488 | // FIXME: return value by reference instead of strdup |
1d152acc LDM |
489 | struct index_node_f *root; |
490 | char *value; | |
e8847fd2 | 491 | |
1d152acc LDM |
492 | root = index_readroot(in); |
493 | value = index_search__node(root, key, 0); | |
494 | ||
495 | return value; | |
496 | } | |
e8847fd2 | 497 | |
e8847fd2 | 498 | |
e8847fd2 LDM |
499 | |
500 | /* Level 4: add all the values from a matching node */ | |
501 | static void index_searchwild__allvalues(struct index_node_f *node, | |
1d152acc LDM |
502 | struct index_value **out) |
503 | { | |
504 | struct index_value *v; | |
e8847fd2 | 505 | |
1d152acc | 506 | for (v = node->values; v != NULL; v = v->next) |
1433ba9e | 507 | add_value(out, v->value, v->len, v->priority); |
e8847fd2 | 508 | |
1d152acc LDM |
509 | index_close(node); |
510 | } | |
511 | ||
512 | /* | |
513 | * Level 3: traverse a sub-keyspace which starts with a wildcard, | |
514 | * looking for matches. | |
515 | */ | |
516 | static void index_searchwild__all(struct index_node_f *node, int j, | |
517 | struct buffer *buf, | |
518 | const char *subkey, | |
519 | struct index_value **out) | |
e8847fd2 | 520 | { |
1d152acc LDM |
521 | int pushed = 0; |
522 | int ch; | |
a7be73b9 | 523 | |
1d152acc LDM |
524 | while (node->prefix[j]) { |
525 | ch = node->prefix[j]; | |
526 | ||
527 | buf_pushchar(buf, ch); | |
528 | pushed++; | |
529 | j++; | |
530 | } | |
531 | ||
532 | for (ch = node->first; ch <= node->last; ch++) { | |
533 | struct index_node_f *child = index_readchild(node, ch); | |
534 | ||
535 | if (!child) | |
536 | continue; | |
537 | ||
538 | buf_pushchar(buf, ch); | |
539 | index_searchwild__all(child, 0, buf, subkey, out); | |
540 | buf_popchar(buf); | |
541 | } | |
542 | ||
543 | if (node->values) { | |
544 | if (fnmatch(buf_str(buf), subkey, 0) == 0) | |
545 | index_searchwild__allvalues(node, out); | |
27fdf631 GSB |
546 | else |
547 | index_close(node); | |
1d152acc LDM |
548 | } else { |
549 | index_close(node); | |
550 | } | |
551 | ||
552 | buf_popchars(buf, pushed); | |
e8847fd2 LDM |
553 | } |
554 | ||
1d152acc | 555 | /* Level 2: descend the tree (until we hit a wildcard) */ |
e8847fd2 LDM |
556 | static void index_searchwild__node(struct index_node_f *node, |
557 | struct buffer *buf, | |
558 | const char *key, int i, | |
559 | struct index_value **out) | |
560 | { | |
561 | struct index_node_f *child; | |
562 | int j; | |
563 | int ch; | |
564 | ||
565 | while(node) { | |
566 | for (j = 0; node->prefix[j]; j++) { | |
567 | ch = node->prefix[j]; | |
a7be73b9 | 568 | |
e8847fd2 LDM |
569 | if (ch == '*' || ch == '?' || ch == '[') { |
570 | index_searchwild__all(node, j, buf, | |
571 | &key[i+j], out); | |
572 | return; | |
573 | } | |
a7be73b9 | 574 | |
e8847fd2 LDM |
575 | if (ch != key[i+j]) { |
576 | index_close(node); | |
577 | return; | |
578 | } | |
579 | } | |
e71970ae | 580 | |
e8847fd2 | 581 | i += j; |
a7be73b9 | 582 | |
e8847fd2 LDM |
583 | child = index_readchild(node, '*'); |
584 | if (child) { | |
585 | buf_pushchar(buf, '*'); | |
586 | index_searchwild__all(child, 0, buf, &key[i], out); | |
587 | buf_popchar(buf); | |
588 | } | |
a7be73b9 | 589 | |
e8847fd2 LDM |
590 | child = index_readchild(node, '?'); |
591 | if (child) { | |
592 | buf_pushchar(buf, '?'); | |
593 | index_searchwild__all(child, 0, buf, &key[i], out); | |
594 | buf_popchar(buf); | |
595 | } | |
a7be73b9 | 596 | |
e8847fd2 LDM |
597 | child = index_readchild(node, '['); |
598 | if (child) { | |
599 | buf_pushchar(buf, '['); | |
600 | index_searchwild__all(child, 0, buf, &key[i], out); | |
601 | buf_popchar(buf); | |
602 | } | |
a7be73b9 | 603 | |
e8847fd2 LDM |
604 | if (key[i] == '\0') { |
605 | index_searchwild__allvalues(node, out); | |
606 | ||
607 | return; | |
608 | } | |
a7be73b9 | 609 | |
e8847fd2 LDM |
610 | child = index_readchild(node, key[i]); |
611 | index_close(node); | |
612 | node = child; | |
613 | i++; | |
614 | } | |
615 | } | |
616 | ||
1d152acc LDM |
617 | /* |
618 | * Search the index for a key. The index may contain wildcards. | |
619 | * | |
620 | * Returns a list of all the values of matching keys. | |
621 | */ | |
622 | struct index_value *index_searchwild(struct index_file *in, const char *key) | |
e8847fd2 | 623 | { |
1d152acc | 624 | struct index_node_f *root = index_readroot(in); |
405f614a | 625 | struct buffer buf; |
1d152acc | 626 | struct index_value *out = NULL; |
e8847fd2 | 627 | |
405f614a GSB |
628 | buf_init(&buf); |
629 | index_searchwild__node(root, &buf, key, 0, &out); | |
630 | buf_release(&buf); | |
1d152acc | 631 | return out; |
e8847fd2 | 632 | } |
b471a6b4 LDM |
633 | |
634 | #include <sys/mman.h> | |
635 | #include <sys/stat.h> | |
636 | #include <unistd.h> | |
637 | ||
15c1c143 GSB |
638 | static const char _idx_empty_str[] = ""; |
639 | ||
b471a6b4 LDM |
640 | /**************************************************************************/ |
641 | /* | |
642 | * Alternative implementation, using mmap to map all the file to memory when | |
643 | * starting | |
644 | */ | |
645 | struct index_mm { | |
646 | struct kmod_ctx *ctx; | |
647 | void *mm; | |
648 | uint32_t root_offset; | |
649 | size_t size; | |
650 | }; | |
651 | ||
d0915464 GSB |
652 | struct index_mm_value { |
653 | unsigned int priority; | |
654 | unsigned int len; | |
655 | const char *value; | |
656 | }; | |
657 | ||
658 | struct index_mm_value_array { | |
659 | struct index_mm_value *values; | |
660 | unsigned int len; | |
661 | }; | |
662 | ||
836be9ac LDM |
663 | struct index_mm_node { |
664 | struct index_mm *idx; | |
15c1c143 | 665 | const char *prefix; /* mmape'd value */ |
d0915464 | 666 | struct index_mm_value_array values; |
836be9ac LDM |
667 | unsigned char first; |
668 | unsigned char last; | |
669 | uint32_t children[]; | |
670 | }; | |
671 | ||
672 | static inline uint32_t read_long_mm(void **p) | |
673 | { | |
fc2d835d GSB |
674 | uint8_t *addr = *(uint8_t **)p; |
675 | uint32_t v; | |
836be9ac | 676 | |
fc2d835d | 677 | /* addr may be unalined to uint32_t */ |
5bbec8cd | 678 | v = get_unaligned((uint32_t *) addr); |
836be9ac | 679 | |
fc2d835d | 680 | *p = addr + sizeof(uint32_t); |
836be9ac LDM |
681 | return ntohl(v); |
682 | } | |
683 | ||
684 | static inline uint8_t read_char_mm(void **p) | |
685 | { | |
fc2d835d GSB |
686 | uint8_t *addr = *(uint8_t **)p; |
687 | uint8_t v = *addr; | |
688 | *p = addr + sizeof(uint8_t); | |
689 | return v; | |
836be9ac LDM |
690 | } |
691 | ||
1433ba9e | 692 | static inline char *read_chars_mm(void **p, unsigned *rlen) |
836be9ac | 693 | { |
fc2d835d GSB |
694 | char *addr = *(char **)p; |
695 | size_t len = *rlen = strlen(addr); | |
696 | *p = addr + len + 1; | |
697 | return addr; | |
836be9ac LDM |
698 | } |
699 | ||
700 | static struct index_mm_node *index_mm_read_node(struct index_mm *idx, | |
701 | uint32_t offset) { | |
702 | void *p = idx->mm; | |
703 | struct index_mm_node *node; | |
15c1c143 | 704 | const char *prefix; |
d0915464 GSB |
705 | int i, child_count, value_count, children_padding; |
706 | uint32_t children[INDEX_CHILDMAX]; | |
707 | char first, last; | |
836be9ac LDM |
708 | |
709 | if ((offset & INDEX_NODE_MASK) == 0) | |
710 | return NULL; | |
711 | ||
712 | p = (char *)p + (offset & INDEX_NODE_MASK); | |
713 | ||
15c1c143 GSB |
714 | if (offset & INDEX_NODE_PREFIX) { |
715 | unsigned len; | |
716 | prefix = read_chars_mm(&p, &len); | |
717 | } else | |
718 | prefix = _idx_empty_str; | |
836be9ac LDM |
719 | |
720 | if (offset & INDEX_NODE_CHILDS) { | |
d0915464 GSB |
721 | first = read_char_mm(&p); |
722 | last = read_char_mm(&p); | |
836be9ac | 723 | child_count = last - first + 1; |
836be9ac | 724 | for (i = 0; i < child_count; i++) |
d0915464 | 725 | children[i] = read_long_mm(&p); |
836be9ac | 726 | } else { |
d0915464 GSB |
727 | first = INDEX_CHILDMAX; |
728 | last = 0; | |
729 | child_count = 0; | |
836be9ac LDM |
730 | } |
731 | ||
c6824b62 | 732 | children_padding = (sizeof(struct index_mm_node) + |
d0915464 | 733 | (sizeof(uint32_t) * child_count)) % sizeof(void *); |
836be9ac | 734 | |
d0915464 GSB |
735 | if (offset & INDEX_NODE_VALUES) |
736 | value_count = read_long_mm(&p); | |
737 | else | |
738 | value_count = 0; | |
836be9ac | 739 | |
d0915464 GSB |
740 | node = malloc(sizeof(struct index_mm_node) |
741 | + sizeof(uint32_t) * child_count + children_padding | |
742 | + sizeof(struct index_mm_value) * value_count); | |
743 | if (node == NULL) | |
744 | return NULL; | |
836be9ac | 745 | |
836be9ac | 746 | node->idx = idx; |
d0915464 GSB |
747 | node->prefix = prefix; |
748 | if (value_count == 0) | |
749 | node->values.values = NULL; | |
750 | else { | |
751 | node->values.values = (struct index_mm_value *) | |
752 | ((char *)node + sizeof(struct index_mm_node) + | |
753 | sizeof(uint32_t) * child_count + children_padding); | |
754 | } | |
755 | node->values.len = value_count; | |
756 | node->first = first; | |
757 | node->last = last; | |
758 | memcpy(node->children, children, sizeof(uint32_t) * child_count); | |
759 | ||
760 | for (i = 0; i < value_count; i++) { | |
761 | struct index_mm_value *v = node->values.values + i; | |
762 | v->priority = read_long_mm(&p); | |
763 | v->value = read_chars_mm(&p, &v->len); | |
764 | } | |
836be9ac LDM |
765 | |
766 | return node; | |
767 | } | |
768 | ||
769 | static void index_mm_free_node(struct index_mm_node *node) | |
770 | { | |
836be9ac LDM |
771 | free(node); |
772 | } | |
773 | ||
5109f2b4 | 774 | struct index_mm *index_mm_open(struct kmod_ctx *ctx, const char *filename, |
2e2e252b | 775 | unsigned long long *stamp) |
b471a6b4 LDM |
776 | { |
777 | int fd; | |
778 | struct stat st; | |
779 | struct index_mm *idx; | |
780 | struct { | |
781 | uint32_t magic; | |
782 | uint32_t version; | |
783 | uint32_t root_offset; | |
784 | } hdr; | |
785 | void *p; | |
786 | ||
787 | DBG(ctx, "file=%s\n", filename); | |
788 | ||
7d51d8bf LDM |
789 | idx = malloc(sizeof(*idx)); |
790 | if (idx == NULL) { | |
dfa96f15 | 791 | ERR(ctx, "malloc: %m\n"); |
b471a6b4 LDM |
792 | return NULL; |
793 | } | |
794 | ||
79e5ea91 | 795 | if ((fd = open(filename, O_RDONLY|O_CLOEXEC)) < 0) { |
73298175 | 796 | DBG(ctx, "open(%s, O_RDONLY|O_CLOEXEC): %m\n", filename); |
7d51d8bf | 797 | goto fail_open; |
b471a6b4 LDM |
798 | } |
799 | ||
7d51d8bf | 800 | fstat(fd, &st); |
5b05c327 LDM |
801 | if ((size_t) st.st_size < sizeof(hdr)) |
802 | goto fail_nommap; | |
5109f2b4 | 803 | |
2e2e252b | 804 | if ((idx->mm = mmap(0, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0)) |
5109f2b4 | 805 | == MAP_FAILED) { |
bfcd31de | 806 | ERR(ctx, "mmap(0, %"PRIu64", PROT_READ, %d, MAP_PRIVATE, 0): %m\n", |
2e2e252b | 807 | st.st_size, fd); |
5b05c327 | 808 | goto fail_nommap; |
b471a6b4 LDM |
809 | } |
810 | ||
811 | p = idx->mm; | |
812 | hdr.magic = read_long_mm(&p); | |
813 | hdr.version = read_long_mm(&p); | |
814 | hdr.root_offset = read_long_mm(&p); | |
815 | ||
816 | if (hdr.magic != INDEX_MAGIC) { | |
817 | ERR(ctx, "magic check fail: %x instead of %x\n", hdr.magic, | |
818 | INDEX_MAGIC); | |
819 | goto fail; | |
820 | } | |
821 | ||
822 | if (hdr.version >> 16 != INDEX_VERSION_MAJOR) { | |
823 | ERR(ctx, "major version check fail: %u instead of %u\n", | |
824 | hdr.version, INDEX_MAGIC); | |
825 | goto fail; | |
826 | } | |
827 | ||
828 | idx->root_offset = hdr.root_offset; | |
829 | idx->size = st.st_size; | |
830 | idx->ctx = ctx; | |
831 | close(fd); | |
832 | ||
6068aaae | 833 | *stamp = stat_mstamp(&st); |
9fd58f30 | 834 | |
b471a6b4 LDM |
835 | return idx; |
836 | ||
837 | fail: | |
5b05c327 LDM |
838 | munmap(idx->mm, st.st_size); |
839 | fail_nommap: | |
b471a6b4 | 840 | close(fd); |
a5a92a61 | 841 | fail_open: |
b471a6b4 LDM |
842 | free(idx); |
843 | return NULL; | |
844 | } | |
845 | ||
846 | void index_mm_close(struct index_mm *idx) | |
847 | { | |
848 | munmap(idx->mm, idx->size); | |
849 | free(idx); | |
850 | } | |
77bf936a LDM |
851 | |
852 | static struct index_mm_node *index_mm_readroot(struct index_mm *idx) | |
853 | { | |
854 | return index_mm_read_node(idx, idx->root_offset); | |
855 | } | |
91298dc7 LDM |
856 | |
857 | static struct index_mm_node *index_mm_readchild(const struct index_mm_node *parent, | |
858 | int ch) | |
859 | { | |
860 | if (parent->first <= ch && ch <= parent->last) { | |
861 | return index_mm_read_node(parent->idx, | |
862 | parent->children[ch - parent->first]); | |
863 | } | |
864 | ||
865 | return NULL; | |
866 | } | |
e33bb87c | 867 | |
758428a7 LDM |
868 | static void index_mm_dump_node(struct index_mm_node *node, struct buffer *buf, |
869 | int fd) | |
870 | { | |
871 | struct index_mm_value *itr, *itr_end; | |
872 | int ch, pushed; | |
873 | ||
874 | pushed = buf_pushchars(buf, node->prefix); | |
875 | ||
876 | itr = node->values.values; | |
877 | itr_end = itr + node->values.len; | |
878 | for (; itr < itr_end; itr++) { | |
879 | write_str_safe(fd, buf->bytes, buf->used); | |
880 | write_str_safe(fd, " ", 1); | |
881 | write_str_safe(fd, itr->value, itr->len); | |
882 | write_str_safe(fd, "\n", 1); | |
883 | } | |
884 | ||
885 | for (ch = node->first; ch <= node->last; ch++) { | |
886 | struct index_mm_node *child = index_mm_readchild(node, ch); | |
887 | ||
888 | if (child == NULL) | |
889 | continue; | |
890 | ||
891 | buf_pushchar(buf, ch); | |
892 | index_mm_dump_node(child, buf, fd); | |
893 | buf_popchar(buf); | |
894 | } | |
895 | ||
896 | buf_popchars(buf, pushed); | |
897 | index_mm_free_node(node); | |
898 | } | |
899 | ||
900 | void index_mm_dump(struct index_mm *idx, int fd, const char *prefix) | |
901 | { | |
902 | struct index_mm_node *root; | |
903 | struct buffer buf; | |
904 | ||
905 | buf_init(&buf); | |
906 | buf_pushchars(&buf, prefix); | |
907 | root = index_mm_readroot(idx); | |
908 | index_mm_dump_node(root, &buf, fd); | |
909 | buf_release(&buf); | |
910 | } | |
911 | ||
e33bb87c LDM |
912 | static char *index_mm_search_node(struct index_mm_node *node, const char *key, |
913 | int i) | |
914 | { | |
915 | char *value; | |
916 | struct index_mm_node *child; | |
917 | int ch; | |
918 | int j; | |
919 | ||
920 | while(node) { | |
921 | for (j = 0; node->prefix[j]; j++) { | |
922 | ch = node->prefix[j]; | |
923 | ||
924 | if (ch != key[i+j]) { | |
925 | index_mm_free_node(node); | |
926 | return NULL; | |
927 | } | |
928 | } | |
929 | ||
930 | i += j; | |
931 | ||
932 | if (key[i] == '\0') { | |
817f4e33 LDM |
933 | value = node->values.len > 0 |
934 | ? strdup(node->values.values[0].value) | |
935 | : NULL; | |
936 | ||
937 | index_mm_free_node(node); | |
938 | return value; | |
e33bb87c LDM |
939 | } |
940 | ||
941 | child = index_mm_readchild(node, key[i]); | |
942 | index_mm_free_node(node); | |
943 | node = child; | |
944 | i++; | |
945 | } | |
946 | ||
947 | return NULL; | |
948 | } | |
b797b791 LDM |
949 | |
950 | /* | |
951 | * Search the index for a key | |
952 | * | |
953 | * Returns the value of the first match | |
954 | * | |
955 | * The recursive functions free their node argument (using index_close). | |
956 | */ | |
957 | char *index_mm_search(struct index_mm *idx, const char *key) | |
958 | { | |
ee1d188f | 959 | // FIXME: return value by reference instead of strdup |
b797b791 LDM |
960 | struct index_mm_node *root; |
961 | char *value; | |
962 | ||
963 | root = index_mm_readroot(idx); | |
964 | value = index_mm_search_node(root, key, 0); | |
965 | ||
966 | return value; | |
967 | } | |
bf89f70c LDM |
968 | |
969 | /* Level 4: add all the values from a matching node */ | |
970 | static void index_mm_searchwild_allvalues(struct index_mm_node *node, | |
971 | struct index_value **out) | |
972 | { | |
d0915464 | 973 | struct index_mm_value *itr, *itr_end; |
bf89f70c | 974 | |
d0915464 GSB |
975 | itr = node->values.values; |
976 | itr_end = itr + node->values.len; | |
977 | for (; itr < itr_end; itr++) | |
978 | add_value(out, itr->value, itr->len, itr->priority); | |
bf89f70c LDM |
979 | |
980 | index_mm_free_node(node); | |
981 | } | |
982 | ||
983 | /* | |
984 | * Level 3: traverse a sub-keyspace which starts with a wildcard, | |
985 | * looking for matches. | |
986 | */ | |
987 | static void index_mm_searchwild_all(struct index_mm_node *node, int j, | |
988 | struct buffer *buf, | |
989 | const char *subkey, | |
990 | struct index_value **out) | |
991 | { | |
992 | int pushed = 0; | |
993 | int ch; | |
994 | ||
995 | while (node->prefix[j]) { | |
996 | ch = node->prefix[j]; | |
997 | ||
998 | buf_pushchar(buf, ch); | |
999 | pushed++; | |
1000 | j++; | |
1001 | } | |
1002 | ||
1003 | for (ch = node->first; ch <= node->last; ch++) { | |
1004 | struct index_mm_node *child = index_mm_readchild(node, ch); | |
1005 | ||
1006 | if (!child) | |
1007 | continue; | |
1008 | ||
1009 | buf_pushchar(buf, ch); | |
1010 | index_mm_searchwild_all(child, 0, buf, subkey, out); | |
1011 | buf_popchar(buf); | |
1012 | } | |
1013 | ||
d0915464 | 1014 | if (node->values.len > 0) { |
bf89f70c LDM |
1015 | if (fnmatch(buf_str(buf), subkey, 0) == 0) |
1016 | index_mm_searchwild_allvalues(node, out); | |
27fdf631 GSB |
1017 | else |
1018 | index_mm_free_node(node); | |
bf89f70c LDM |
1019 | } else { |
1020 | index_mm_free_node(node); | |
1021 | } | |
1022 | ||
1023 | buf_popchars(buf, pushed); | |
1024 | } | |
1025 | ||
1026 | /* Level 2: descend the tree (until we hit a wildcard) */ | |
1027 | static void index_mm_searchwild_node(struct index_mm_node *node, | |
1028 | struct buffer *buf, | |
1029 | const char *key, int i, | |
1030 | struct index_value **out) | |
1031 | { | |
1032 | struct index_mm_node *child; | |
1033 | int j; | |
1034 | int ch; | |
1035 | ||
1036 | while(node) { | |
1037 | for (j = 0; node->prefix[j]; j++) { | |
1038 | ch = node->prefix[j]; | |
1039 | ||
1040 | if (ch == '*' || ch == '?' || ch == '[') { | |
1041 | index_mm_searchwild_all(node, j, buf, | |
1042 | &key[i+j], out); | |
1043 | return; | |
1044 | } | |
1045 | ||
1046 | if (ch != key[i+j]) { | |
1047 | index_mm_free_node(node); | |
1048 | return; | |
1049 | } | |
1050 | } | |
1051 | ||
1052 | i += j; | |
1053 | ||
1054 | child = index_mm_readchild(node, '*'); | |
1055 | if (child) { | |
1056 | buf_pushchar(buf, '*'); | |
1057 | index_mm_searchwild_all(child, 0, buf, &key[i], out); | |
1058 | buf_popchar(buf); | |
1059 | } | |
1060 | ||
1061 | child = index_mm_readchild(node, '?'); | |
1062 | if (child) { | |
1063 | buf_pushchar(buf, '?'); | |
1064 | index_mm_searchwild_all(child, 0, buf, &key[i], out); | |
1065 | buf_popchar(buf); | |
1066 | } | |
1067 | ||
1068 | child = index_mm_readchild(node, '['); | |
1069 | if (child) { | |
1070 | buf_pushchar(buf, '['); | |
1071 | index_mm_searchwild_all(child, 0, buf, &key[i], out); | |
1072 | buf_popchar(buf); | |
1073 | } | |
1074 | ||
1075 | if (key[i] == '\0') { | |
1076 | index_mm_searchwild_allvalues(node, out); | |
1077 | ||
1078 | return; | |
1079 | } | |
1080 | ||
1081 | child = index_mm_readchild(node, key[i]); | |
1082 | index_mm_free_node(node); | |
1083 | node = child; | |
1084 | i++; | |
1085 | } | |
1086 | } | |
1087 | ||
1088 | /* | |
1089 | * Search the index for a key. The index may contain wildcards. | |
1090 | * | |
1091 | * Returns a list of all the values of matching keys. | |
1092 | */ | |
1093 | struct index_value *index_mm_searchwild(struct index_mm *idx, const char *key) | |
1094 | { | |
1095 | struct index_mm_node *root = index_mm_readroot(idx); | |
405f614a | 1096 | struct buffer buf; |
bf89f70c LDM |
1097 | struct index_value *out = NULL; |
1098 | ||
405f614a GSB |
1099 | buf_init(&buf); |
1100 | index_mm_searchwild_node(root, &buf, key, 0, &out); | |
1101 | buf_release(&buf); | |
bf89f70c LDM |
1102 | return out; |
1103 | } |