blob: 7f0c0923a39fd9174f024a3e4bc27dc6bd783b00 [file] [log] [blame]
Lucas De Marchi8f923be2011-12-03 04:28:49 -02001/*
2 * libkmod - interface to kernel module operations
3 *
Lucas De Marchi8f923be2011-12-03 04:28:49 -02004 * Copyright (C) 2011 ProFUSION embedded systems
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
Lucas De Marchicb451f32011-12-12 18:24:35 -02008 * License as published by the Free Software Foundation; either
9 * version 2.1 of the License, or (at your option) any later version.
Lucas De Marchi8f923be2011-12-03 04:28:49 -020010 *
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 */
Lucas De Marchie8847fd2011-11-30 15:23:28 -020020
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>
Gustavo Sverzut Barbieri405f6142011-12-08 14:36:30 -020027#include <assert.h>
Lucas De Marchie8847fd2011-11-30 15:23:28 -020028
29#include "libkmod-private.h"
30#include "libkmod-index.h"
31#include "macro.h"
32
Lucas De Marchi8f923be2011-12-03 04:28:49 -020033/* index.c: module index file shared functions for modprobe and depmod */
34
Gustavo Sverzut Barbieri148226e2011-12-10 11:53:51 -020035#define INDEX_CHILDMAX 128
36
37/* Disk format:
38
39 uint32_t magic = INDEX_MAGIC;
40 uint32_t version = INDEX_VERSION;
41 uint32_t root_offset;
42
43 (node_offset & INDEX_NODE_MASK) specifies the file offset of nodes:
44
45 char[] prefix; // nul terminated
46
47 char first;
48 char last;
49 uint32_t children[last - first + 1];
50
51 uint32_t value_count;
52 struct {
53 uint32_t priority;
54 char[] value; // nul terminated
55 } values[value_count];
56
57 (node_offset & INDEX_NODE_FLAGS) indicates which fields are present.
58 Empty prefixes are omitted, leaf nodes omit the three child-related fields.
59
60 This could be optimised further by adding a sparse child format
61 (indicated using a new flag).
62 */
63
64/* Format of node offsets within index file */
65enum node_offset {
66 INDEX_NODE_FLAGS = 0xF0000000, /* Flags in high nibble */
67 INDEX_NODE_PREFIX = 0x80000000,
68 INDEX_NODE_VALUES = 0x40000000,
69 INDEX_NODE_CHILDS = 0x20000000,
70
71 INDEX_NODE_MASK = 0x0FFFFFFF, /* Offset value */
72};
73
Lucas De Marchie8847fd2011-11-30 15:23:28 -020074void index_values_free(struct index_value *values)
75{
76 while (values) {
77 struct index_value *value = values;
78
79 values = value->next;
80 free(value);
81 }
82}
83
Lucas De Marchie8847fd2011-11-30 15:23:28 -020084static int add_value(struct index_value **values,
Gustavo Sverzut Barbieri1433ba92011-12-08 14:50:29 -020085 const char *value, unsigned len, unsigned int priority)
Lucas De Marchie8847fd2011-11-30 15:23:28 -020086{
87 struct index_value *v;
Lucas De Marchie8847fd2011-11-30 15:23:28 -020088
89 /* find position to insert value */
90 while (*values && (*values)->priority < priority)
91 values = &(*values)->next;
92
Gustavo Sverzut Barbieri1433ba92011-12-08 14:50:29 -020093 v = malloc(sizeof(struct index_value) + len + 1);
94 if (!v)
95 return -1;
Lucas De Marchie8847fd2011-11-30 15:23:28 -020096 v->next = *values;
97 v->priority = priority;
Gustavo Sverzut Barbieri1433ba92011-12-08 14:50:29 -020098 v->len = len;
99 memcpy(v->value, value, len);
100 v->value[len] = '\0';
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200101 *values = v;
102
Gustavo Sverzut Barbieri558b0202011-12-08 16:36:48 -0200103 return 0;
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200104}
105
Lucas De Marchi93688882011-12-02 10:05:31 -0200106static void read_error(void)
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200107{
108 fatal("Module index: unexpected error: %s\n"
109 "Try re-running depmod\n", errno ? strerror(errno) : "EOF");
110}
111
112static int read_char(FILE *in)
113{
114 int ch;
115
116 errno = 0;
117 ch = getc_unlocked(in);
118 if (ch == EOF)
119 read_error();
120 return ch;
121}
122
123static uint32_t read_long(FILE *in)
124{
125 uint32_t l;
126
127 errno = 0;
128 if (fread(&l, sizeof(uint32_t), 1, in) <= 0)
129 read_error();
130 return ntohl(l);
131}
132
133/*
134 * Buffer abstract data type
135 *
136 * Used internally to store the current path during tree traversal.
137 * They help build wildcard key strings to pass to fnmatch(),
138 * as well as building values of matching keys.
139 */
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200140struct buffer {
141 char *bytes;
142 unsigned size;
143 unsigned used;
144};
145
Gustavo Sverzut Barbieri405f6142011-12-08 14:36:30 -0200146#define BUF_STEP (2048)
147static bool buf_grow(struct buffer *buf, size_t newsize)
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200148{
Gustavo Sverzut Barbieri405f6142011-12-08 14:36:30 -0200149 void *tmp;
150 size_t sz;
151
152 if (newsize % BUF_STEP == 0)
153 sz = newsize;
154 else
155 sz = ((newsize / BUF_STEP) + 1) * BUF_STEP;
156
Gustavo Sverzut Barbieri435ad782011-12-08 16:35:08 -0200157 if (buf->size == sz)
158 return true;
159
Gustavo Sverzut Barbieri405f6142011-12-08 14:36:30 -0200160 tmp = realloc(buf->bytes, sz);
161 if (sz > 0 && tmp == NULL)
162 return false;
163 buf->bytes = tmp;
164 buf->size = sz;
165 return true;
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200166}
167
Gustavo Sverzut Barbieri405f6142011-12-08 14:36:30 -0200168static void buf_init(struct buffer *buf)
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200169{
Gustavo Sverzut Barbieri405f6142011-12-08 14:36:30 -0200170 buf->bytes = NULL;
171 buf->size = 0;
172 buf->used = 0;
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200173}
174
Gustavo Sverzut Barbieri405f6142011-12-08 14:36:30 -0200175static void buf_release(struct buffer *buf)
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200176{
177 free(buf->bytes);
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200178}
179
180/* Destroy buffer and return a copy as a C string */
Gustavo Sverzut Barbieri405f6142011-12-08 14:36:30 -0200181static char *buf_steal(struct buffer *buf)
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200182{
183 char *bytes;
184
Gustavo Sverzut Barbieri405f6142011-12-08 14:36:30 -0200185 bytes = realloc(buf->bytes, buf->used + 1);
186 if (!bytes) {
187 free(buf->bytes);
188 return NULL;
189 }
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200190 bytes[buf->used] = '\0';
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200191 return bytes;
192}
193
194/* Return a C string owned by the buffer
195 (invalidated if the buffer is changed).
196 */
197static const char *buf_str(struct buffer *buf)
198{
Gustavo Sverzut Barbieri405f6142011-12-08 14:36:30 -0200199 if (!buf_grow(buf, buf->used + 1))
200 return NULL;
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200201 buf->bytes[buf->used] = '\0';
202 return buf->bytes;
203}
204
Gustavo Sverzut Barbieri405f6142011-12-08 14:36:30 -0200205static bool buf_pushchar(struct buffer *buf, char ch)
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200206{
Gustavo Sverzut Barbieri405f6142011-12-08 14:36:30 -0200207 if (!buf_grow(buf, buf->used + 1))
208 return false;
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200209 buf->bytes[buf->used] = ch;
210 buf->used++;
Gustavo Sverzut Barbieri405f6142011-12-08 14:36:30 -0200211 return true;
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200212}
213
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200214static unsigned buf_freadchars(struct buffer *buf, FILE *in)
215{
216 unsigned i = 0;
217 int ch;
218
219 while ((ch = read_char(in))) {
Gustavo Sverzut Barbieri405f6142011-12-08 14:36:30 -0200220 if (!buf_pushchar(buf, ch))
221 break;
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200222 i++;
223 }
224
225 return i;
226}
227
228static void buf_popchar(struct buffer *buf)
229{
Gustavo Sverzut Barbieri405f6142011-12-08 14:36:30 -0200230 assert(buf->used > 0);
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200231 buf->used--;
232}
233
234static void buf_popchars(struct buffer *buf, unsigned n)
235{
Gustavo Sverzut Barbieri405f6142011-12-08 14:36:30 -0200236 assert(buf->used >= n);
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200237 buf->used -= n;
238}
239
240static void buf_clear(struct buffer *buf)
241{
242 buf->used = 0;
243}
244
245/*
Lucas De Marchieb8bb322011-12-02 10:23:02 -0200246 * Index file searching
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200247 */
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200248struct index_node_f {
249 FILE *file;
250 char *prefix; /* path compression */
251 struct index_value *values;
252 unsigned char first; /* range of child nodes */
253 unsigned char last;
254 uint32_t children[0];
255};
256
257static struct index_node_f *index_read(FILE *in, uint32_t offset)
258{
259 struct index_node_f *node;
260 char *prefix;
261 int i, child_count = 0;
262
263 if ((offset & INDEX_NODE_MASK) == 0)
264 return NULL;
265
266 fseek(in, offset & INDEX_NODE_MASK, SEEK_SET);
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200267
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200268 if (offset & INDEX_NODE_PREFIX) {
Gustavo Sverzut Barbieri405f6142011-12-08 14:36:30 -0200269 struct buffer buf;
270 buf_init(&buf);
271 buf_freadchars(&buf, in);
272 prefix = buf_steal(&buf);
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200273 } else
274 prefix = NOFAIL(strdup(""));
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200275
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200276 if (offset & INDEX_NODE_CHILDS) {
277 char first = read_char(in);
278 char last = read_char(in);
279 child_count = last - first + 1;
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200280
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200281 node = NOFAIL(malloc(sizeof(struct index_node_f) +
282 sizeof(uint32_t) * child_count));
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200283
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200284 node->first = first;
285 node->last = last;
286
287 for (i = 0; i < child_count; i++)
288 node->children[i] = read_long(in);
289 } else {
290 node = NOFAIL(malloc(sizeof(struct index_node_f)));
291 node->first = INDEX_CHILDMAX;
292 node->last = 0;
293 }
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200294
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200295 node->values = NULL;
296 if (offset & INDEX_NODE_VALUES) {
297 int value_count;
Gustavo Sverzut Barbieri405f6142011-12-08 14:36:30 -0200298 struct buffer buf;
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200299 const char *value;
300 unsigned int priority;
301
302 value_count = read_long(in);
303
Gustavo Sverzut Barbieri405f6142011-12-08 14:36:30 -0200304 buf_init(&buf);
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200305 while (value_count--) {
306 priority = read_long(in);
Gustavo Sverzut Barbieri405f6142011-12-08 14:36:30 -0200307 buf_freadchars(&buf, in);
308 value = buf_str(&buf);
Gustavo Sverzut Barbieri1433ba92011-12-08 14:50:29 -0200309 add_value(&node->values, value, buf.used, priority);
Gustavo Sverzut Barbieri405f6142011-12-08 14:36:30 -0200310 buf_clear(&buf);
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200311 }
Gustavo Sverzut Barbieri405f6142011-12-08 14:36:30 -0200312 buf_release(&buf);
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200313 }
314
315 node->prefix = prefix;
316 node->file = in;
317 return node;
318}
319
320static void index_close(struct index_node_f *node)
321{
322 free(node->prefix);
323 index_values_free(node->values);
324 free(node);
325}
326
327struct index_file {
328 FILE *file;
329 uint32_t root_offset;
330};
331
332/* Failures are silent; modprobe will fall back to text files */
333struct index_file *index_file_open(const char *filename)
334{
335 FILE *file;
336 uint32_t magic, version;
337 struct index_file *new;
338
Cristian Rodríguez79e5ea92011-12-16 02:49:54 -0300339 file = fopen(filename, "re");
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200340 if (!file)
341 return NULL;
342 errno = EINVAL;
343
344 magic = read_long(file);
345 if (magic != INDEX_MAGIC)
346 return NULL;
347
348 version = read_long(file);
349 if (version >> 16 != INDEX_VERSION_MAJOR)
350 return NULL;
351
352 new = NOFAIL(malloc(sizeof(struct index_file)));
353 new->file = file;
354 new->root_offset = read_long(new->file);
355
356 errno = 0;
357 return new;
358}
359
Lucas De Marchi0fbdfef2011-12-02 09:56:22 -0200360void index_file_close(struct index_file *idx)
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200361{
Lucas De Marchi0fbdfef2011-12-02 09:56:22 -0200362 fclose(idx->file);
363 free(idx);
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200364}
365
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200366static struct index_node_f *index_readroot(struct index_file *in)
367{
368 return index_read(in->file, in->root_offset);
369}
370
371static struct index_node_f *index_readchild(const struct index_node_f *parent,
372 int ch)
373{
Lucas De Marchie71970a2011-12-02 10:27:15 -0200374 if (parent->first <= ch && ch <= parent->last) {
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200375 return index_read(parent->file,
376 parent->children[ch - parent->first]);
Lucas De Marchie71970a2011-12-02 10:27:15 -0200377 }
378
379 return NULL;
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200380}
381
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200382static char *index_search__node(struct index_node_f *node, const char *key, int i)
383{
384 char *value;
385 struct index_node_f *child;
386 int ch;
387 int j;
388
389 while(node) {
390 for (j = 0; node->prefix[j]; j++) {
391 ch = node->prefix[j];
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200392
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200393 if (ch != key[i+j]) {
394 index_close(node);
395 return NULL;
396 }
397 }
Lucas De Marchie71970a2011-12-02 10:27:15 -0200398
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200399 i += j;
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200400
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200401 if (key[i] == '\0') {
402 if (node->values) {
403 value = strdup(node->values[0].value);
404 index_close(node);
405 return value;
406 } else {
407 return NULL;
408 }
409 }
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200410
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200411 child = index_readchild(node, key[i]);
412 index_close(node);
413 node = child;
414 i++;
415 }
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200416
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200417 return NULL;
418}
419
420/*
Lucas De Marchi1d152ac2011-12-02 10:15:00 -0200421 * Search the index for a key
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200422 *
Lucas De Marchi1d152ac2011-12-02 10:15:00 -0200423 * Returns the value of the first match
424 *
425 * The recursive functions free their node argument (using index_close).
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200426 */
Lucas De Marchi1d152ac2011-12-02 10:15:00 -0200427char *index_search(struct index_file *in, const char *key)
428{
429 struct index_node_f *root;
430 char *value;
431
432 root = index_readroot(in);
433 value = index_search__node(root, key, 0);
434
435 return value;
436}
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200437
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200438
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200439
440/* Level 4: add all the values from a matching node */
441static void index_searchwild__allvalues(struct index_node_f *node,
Lucas De Marchi1d152ac2011-12-02 10:15:00 -0200442 struct index_value **out)
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200443{
Lucas De Marchi1d152ac2011-12-02 10:15:00 -0200444 struct index_value *v;
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200445
Lucas De Marchi1d152ac2011-12-02 10:15:00 -0200446 for (v = node->values; v != NULL; v = v->next)
Gustavo Sverzut Barbieri1433ba92011-12-08 14:50:29 -0200447 add_value(out, v->value, v->len, v->priority);
Lucas De Marchi1d152ac2011-12-02 10:15:00 -0200448
449 index_close(node);
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200450}
451
Lucas De Marchi1d152ac2011-12-02 10:15:00 -0200452/*
453 * Level 3: traverse a sub-keyspace which starts with a wildcard,
454 * looking for matches.
455 */
456static void index_searchwild__all(struct index_node_f *node, int j,
457 struct buffer *buf,
458 const char *subkey,
459 struct index_value **out)
460{
461 int pushed = 0;
462 int ch;
463
464 while (node->prefix[j]) {
465 ch = node->prefix[j];
466
467 buf_pushchar(buf, ch);
468 pushed++;
469 j++;
470 }
471
472 for (ch = node->first; ch <= node->last; ch++) {
473 struct index_node_f *child = index_readchild(node, ch);
474
475 if (!child)
476 continue;
477
478 buf_pushchar(buf, ch);
479 index_searchwild__all(child, 0, buf, subkey, out);
480 buf_popchar(buf);
481 }
482
483 if (node->values) {
484 if (fnmatch(buf_str(buf), subkey, 0) == 0)
485 index_searchwild__allvalues(node, out);
Gustavo Sverzut Barbieri27fdf632011-12-10 13:28:18 -0200486 else
487 index_close(node);
Lucas De Marchi1d152ac2011-12-02 10:15:00 -0200488 } else {
489 index_close(node);
490 }
491
492 buf_popchars(buf, pushed);
493}
494
495/* Level 2: descend the tree (until we hit a wildcard) */
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200496static void index_searchwild__node(struct index_node_f *node,
497 struct buffer *buf,
498 const char *key, int i,
499 struct index_value **out)
500{
501 struct index_node_f *child;
502 int j;
503 int ch;
504
505 while(node) {
506 for (j = 0; node->prefix[j]; j++) {
507 ch = node->prefix[j];
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200508
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200509 if (ch == '*' || ch == '?' || ch == '[') {
510 index_searchwild__all(node, j, buf,
511 &key[i+j], out);
512 return;
513 }
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200514
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200515 if (ch != key[i+j]) {
516 index_close(node);
517 return;
518 }
519 }
Lucas De Marchie71970a2011-12-02 10:27:15 -0200520
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200521 i += j;
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200522
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200523 child = index_readchild(node, '*');
524 if (child) {
525 buf_pushchar(buf, '*');
526 index_searchwild__all(child, 0, buf, &key[i], out);
527 buf_popchar(buf);
528 }
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200529
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200530 child = index_readchild(node, '?');
531 if (child) {
532 buf_pushchar(buf, '?');
533 index_searchwild__all(child, 0, buf, &key[i], out);
534 buf_popchar(buf);
535 }
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200536
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200537 child = index_readchild(node, '[');
538 if (child) {
539 buf_pushchar(buf, '[');
540 index_searchwild__all(child, 0, buf, &key[i], out);
541 buf_popchar(buf);
542 }
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200543
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200544 if (key[i] == '\0') {
545 index_searchwild__allvalues(node, out);
546
547 return;
548 }
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200549
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200550 child = index_readchild(node, key[i]);
551 index_close(node);
552 node = child;
553 i++;
554 }
555}
556
Lucas De Marchi1d152ac2011-12-02 10:15:00 -0200557/*
558 * Search the index for a key. The index may contain wildcards.
559 *
560 * Returns a list of all the values of matching keys.
561 */
562struct index_value *index_searchwild(struct index_file *in, const char *key)
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200563{
Lucas De Marchi1d152ac2011-12-02 10:15:00 -0200564 struct index_node_f *root = index_readroot(in);
Gustavo Sverzut Barbieri405f6142011-12-08 14:36:30 -0200565 struct buffer buf;
Lucas De Marchi1d152ac2011-12-02 10:15:00 -0200566 struct index_value *out = NULL;
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200567
Gustavo Sverzut Barbieri405f6142011-12-08 14:36:30 -0200568 buf_init(&buf);
569 index_searchwild__node(root, &buf, key, 0, &out);
570 buf_release(&buf);
Lucas De Marchi1d152ac2011-12-02 10:15:00 -0200571 return out;
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200572}
Lucas De Marchib471a6b2011-12-01 23:14:20 -0200573
574#include <sys/mman.h>
575#include <sys/stat.h>
576#include <unistd.h>
577
Gustavo Sverzut Barbieri15c1c142011-12-10 11:44:31 -0200578static const char _idx_empty_str[] = "";
579
Lucas De Marchib471a6b2011-12-01 23:14:20 -0200580/**************************************************************************/
581/*
582 * Alternative implementation, using mmap to map all the file to memory when
583 * starting
584 */
585struct index_mm {
586 struct kmod_ctx *ctx;
587 void *mm;
588 uint32_t root_offset;
589 size_t size;
590};
591
Gustavo Sverzut Barbierid0915462011-12-10 13:04:43 -0200592struct index_mm_value {
593 unsigned int priority;
594 unsigned int len;
595 const char *value;
596};
597
598struct index_mm_value_array {
599 struct index_mm_value *values;
600 unsigned int len;
601};
602
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200603struct index_mm_node {
604 struct index_mm *idx;
Gustavo Sverzut Barbieri15c1c142011-12-10 11:44:31 -0200605 const char *prefix; /* mmape'd value */
Gustavo Sverzut Barbierid0915462011-12-10 13:04:43 -0200606 struct index_mm_value_array values;
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200607 unsigned char first;
608 unsigned char last;
609 uint32_t children[];
610};
611
612static inline uint32_t read_long_mm(void **p)
613{
Gustavo Sverzut Barbierifc2d8352011-12-10 11:36:35 -0200614 uint8_t *addr = *(uint8_t **)p;
615 uint32_t v;
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200616
Gustavo Sverzut Barbierifc2d8352011-12-10 11:36:35 -0200617 /* addr may be unalined to uint32_t */
618 memcpy(&v, addr, sizeof(uint32_t));
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200619
Gustavo Sverzut Barbierifc2d8352011-12-10 11:36:35 -0200620 *p = addr + sizeof(uint32_t);
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200621 return ntohl(v);
622}
623
624static inline uint8_t read_char_mm(void **p)
625{
Gustavo Sverzut Barbierifc2d8352011-12-10 11:36:35 -0200626 uint8_t *addr = *(uint8_t **)p;
627 uint8_t v = *addr;
628 *p = addr + sizeof(uint8_t);
629 return v;
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200630}
631
Gustavo Sverzut Barbieri1433ba92011-12-08 14:50:29 -0200632static inline char *read_chars_mm(void **p, unsigned *rlen)
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200633{
Gustavo Sverzut Barbierifc2d8352011-12-10 11:36:35 -0200634 char *addr = *(char **)p;
635 size_t len = *rlen = strlen(addr);
636 *p = addr + len + 1;
637 return addr;
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200638}
639
640static struct index_mm_node *index_mm_read_node(struct index_mm *idx,
641 uint32_t offset) {
642 void *p = idx->mm;
643 struct index_mm_node *node;
Gustavo Sverzut Barbieri15c1c142011-12-10 11:44:31 -0200644 const char *prefix;
Gustavo Sverzut Barbierid0915462011-12-10 13:04:43 -0200645 int i, child_count, value_count, children_padding;
646 uint32_t children[INDEX_CHILDMAX];
647 char first, last;
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200648
649 if ((offset & INDEX_NODE_MASK) == 0)
650 return NULL;
651
652 p = (char *)p + (offset & INDEX_NODE_MASK);
653
Gustavo Sverzut Barbieri15c1c142011-12-10 11:44:31 -0200654 if (offset & INDEX_NODE_PREFIX) {
655 unsigned len;
656 prefix = read_chars_mm(&p, &len);
657 } else
658 prefix = _idx_empty_str;
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200659
660 if (offset & INDEX_NODE_CHILDS) {
Gustavo Sverzut Barbierid0915462011-12-10 13:04:43 -0200661 first = read_char_mm(&p);
662 last = read_char_mm(&p);
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200663 child_count = last - first + 1;
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200664 for (i = 0; i < child_count; i++)
Gustavo Sverzut Barbierid0915462011-12-10 13:04:43 -0200665 children[i] = read_long_mm(&p);
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200666 } else {
Gustavo Sverzut Barbierid0915462011-12-10 13:04:43 -0200667 first = INDEX_CHILDMAX;
668 last = 0;
669 child_count = 0;
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200670 }
671
Gustavo Sverzut Barbierid0915462011-12-10 13:04:43 -0200672 children_padding = (offsetof(struct index_mm_node, children) +
673 (sizeof(uint32_t) * child_count)) % sizeof(void *);
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200674
Gustavo Sverzut Barbierid0915462011-12-10 13:04:43 -0200675 if (offset & INDEX_NODE_VALUES)
676 value_count = read_long_mm(&p);
677 else
678 value_count = 0;
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200679
Gustavo Sverzut Barbierid0915462011-12-10 13:04:43 -0200680 node = malloc(sizeof(struct index_mm_node)
681 + sizeof(uint32_t) * child_count + children_padding
682 + sizeof(struct index_mm_value) * value_count);
683 if (node == NULL)
684 return NULL;
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200685
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200686 node->idx = idx;
Gustavo Sverzut Barbierid0915462011-12-10 13:04:43 -0200687 node->prefix = prefix;
688 if (value_count == 0)
689 node->values.values = NULL;
690 else {
691 node->values.values = (struct index_mm_value *)
692 ((char *)node + sizeof(struct index_mm_node) +
693 sizeof(uint32_t) * child_count + children_padding);
694 }
695 node->values.len = value_count;
696 node->first = first;
697 node->last = last;
698 memcpy(node->children, children, sizeof(uint32_t) * child_count);
699
700 for (i = 0; i < value_count; i++) {
701 struct index_mm_value *v = node->values.values + i;
702 v->priority = read_long_mm(&p);
703 v->value = read_chars_mm(&p, &v->len);
704 }
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200705
706 return node;
707}
708
709static void index_mm_free_node(struct index_mm_node *node)
710{
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200711 free(node);
712}
713
Lucas De Marchi5109f2b2011-12-08 15:10:55 -0200714struct index_mm *index_mm_open(struct kmod_ctx *ctx, const char *filename,
715 bool populate)
Lucas De Marchib471a6b2011-12-01 23:14:20 -0200716{
717 int fd;
Lucas De Marchi5109f2b2011-12-08 15:10:55 -0200718 int flags;
Lucas De Marchib471a6b2011-12-01 23:14:20 -0200719 struct stat st;
720 struct index_mm *idx;
721 struct {
722 uint32_t magic;
723 uint32_t version;
724 uint32_t root_offset;
725 } hdr;
726 void *p;
727
728 DBG(ctx, "file=%s\n", filename);
729
Lucas De Marchi7d51d8b2011-12-12 18:41:57 -0200730 idx = malloc(sizeof(*idx));
731 if (idx == NULL) {
Lucas De Marchib471a6b2011-12-01 23:14:20 -0200732 ERR(ctx, "%m\n");
733 return NULL;
734 }
735
Cristian Rodríguez79e5ea92011-12-16 02:49:54 -0300736 if ((fd = open(filename, O_RDONLY|O_CLOEXEC)) < 0) {
Lucas De Marchib471a6b2011-12-01 23:14:20 -0200737 ERR(ctx, "%m\n");
Lucas De Marchi7d51d8b2011-12-12 18:41:57 -0200738 goto fail_open;
Lucas De Marchib471a6b2011-12-01 23:14:20 -0200739 }
740
Lucas De Marchi7d51d8b2011-12-12 18:41:57 -0200741 fstat(fd, &st);
Lucas De Marchi5109f2b2011-12-08 15:10:55 -0200742 flags = MAP_PRIVATE;
743 if (populate)
744 flags |= MAP_POPULATE;
745
746 if ((idx->mm = mmap(0, st.st_size, PROT_READ, flags, fd, 0))
747 == MAP_FAILED) {
Lucas De Marchib471a6b2011-12-01 23:14:20 -0200748 ERR(ctx, "%m\n");
749 goto fail;
750 }
751
752 p = idx->mm;
753 hdr.magic = read_long_mm(&p);
754 hdr.version = read_long_mm(&p);
755 hdr.root_offset = read_long_mm(&p);
756
757 if (hdr.magic != INDEX_MAGIC) {
758 ERR(ctx, "magic check fail: %x instead of %x\n", hdr.magic,
759 INDEX_MAGIC);
760 goto fail;
761 }
762
763 if (hdr.version >> 16 != INDEX_VERSION_MAJOR) {
764 ERR(ctx, "major version check fail: %u instead of %u\n",
765 hdr.version, INDEX_MAGIC);
766 goto fail;
767 }
768
769 idx->root_offset = hdr.root_offset;
770 idx->size = st.st_size;
771 idx->ctx = ctx;
772 close(fd);
773
774 return idx;
775
776fail:
777 close(fd);
Lucas De Marchi7d51d8b2011-12-12 18:41:57 -0200778fail_open:
Lucas De Marchib471a6b2011-12-01 23:14:20 -0200779 if (idx->mm)
780 munmap(idx->mm, st.st_size);
781 free(idx);
782 return NULL;
783}
784
785void index_mm_close(struct index_mm *idx)
786{
787 munmap(idx->mm, idx->size);
788 free(idx);
789}
Lucas De Marchi77bf9362011-12-02 17:41:30 -0200790
791static struct index_mm_node *index_mm_readroot(struct index_mm *idx)
792{
793 return index_mm_read_node(idx, idx->root_offset);
794}
Lucas De Marchi91298dc2011-12-02 17:41:46 -0200795
796static struct index_mm_node *index_mm_readchild(const struct index_mm_node *parent,
797 int ch)
798{
799 if (parent->first <= ch && ch <= parent->last) {
800 return index_mm_read_node(parent->idx,
801 parent->children[ch - parent->first]);
802 }
803
804 return NULL;
805}
Lucas De Marchie33bb872011-12-02 17:45:01 -0200806
807static char *index_mm_search_node(struct index_mm_node *node, const char *key,
808 int i)
809{
810 char *value;
811 struct index_mm_node *child;
812 int ch;
813 int j;
814
815 while(node) {
816 for (j = 0; node->prefix[j]; j++) {
817 ch = node->prefix[j];
818
819 if (ch != key[i+j]) {
820 index_mm_free_node(node);
821 return NULL;
822 }
823 }
824
825 i += j;
826
827 if (key[i] == '\0') {
Gustavo Sverzut Barbierid0915462011-12-10 13:04:43 -0200828 if (node->values.len > 0) {
829 value = strdup(node->values.values[0].value);
Lucas De Marchie33bb872011-12-02 17:45:01 -0200830 index_mm_free_node(node);
831 return value;
832 } else {
833 return NULL;
834 }
835 }
836
837 child = index_mm_readchild(node, key[i]);
838 index_mm_free_node(node);
839 node = child;
840 i++;
841 }
842
843 return NULL;
844}
Lucas De Marchib797b792011-12-02 17:49:03 -0200845
846/*
847 * Search the index for a key
848 *
849 * Returns the value of the first match
850 *
851 * The recursive functions free their node argument (using index_close).
852 */
853char *index_mm_search(struct index_mm *idx, const char *key)
854{
855 struct index_mm_node *root;
856 char *value;
857
858 root = index_mm_readroot(idx);
859 value = index_mm_search_node(root, key, 0);
860
861 return value;
862}
Lucas De Marchibf89f702011-12-02 18:23:36 -0200863
864/* Level 4: add all the values from a matching node */
865static void index_mm_searchwild_allvalues(struct index_mm_node *node,
866 struct index_value **out)
867{
Gustavo Sverzut Barbierid0915462011-12-10 13:04:43 -0200868 struct index_mm_value *itr, *itr_end;
Lucas De Marchibf89f702011-12-02 18:23:36 -0200869
Gustavo Sverzut Barbierid0915462011-12-10 13:04:43 -0200870 itr = node->values.values;
871 itr_end = itr + node->values.len;
872 for (; itr < itr_end; itr++)
873 add_value(out, itr->value, itr->len, itr->priority);
Lucas De Marchibf89f702011-12-02 18:23:36 -0200874
875 index_mm_free_node(node);
876}
877
878/*
879 * Level 3: traverse a sub-keyspace which starts with a wildcard,
880 * looking for matches.
881 */
882static void index_mm_searchwild_all(struct index_mm_node *node, int j,
883 struct buffer *buf,
884 const char *subkey,
885 struct index_value **out)
886{
887 int pushed = 0;
888 int ch;
889
890 while (node->prefix[j]) {
891 ch = node->prefix[j];
892
893 buf_pushchar(buf, ch);
894 pushed++;
895 j++;
896 }
897
898 for (ch = node->first; ch <= node->last; ch++) {
899 struct index_mm_node *child = index_mm_readchild(node, ch);
900
901 if (!child)
902 continue;
903
904 buf_pushchar(buf, ch);
905 index_mm_searchwild_all(child, 0, buf, subkey, out);
906 buf_popchar(buf);
907 }
908
Gustavo Sverzut Barbierid0915462011-12-10 13:04:43 -0200909 if (node->values.len > 0) {
Lucas De Marchibf89f702011-12-02 18:23:36 -0200910 if (fnmatch(buf_str(buf), subkey, 0) == 0)
911 index_mm_searchwild_allvalues(node, out);
Gustavo Sverzut Barbieri27fdf632011-12-10 13:28:18 -0200912 else
913 index_mm_free_node(node);
Lucas De Marchibf89f702011-12-02 18:23:36 -0200914 } else {
915 index_mm_free_node(node);
916 }
917
918 buf_popchars(buf, pushed);
919}
920
921/* Level 2: descend the tree (until we hit a wildcard) */
922static void index_mm_searchwild_node(struct index_mm_node *node,
923 struct buffer *buf,
924 const char *key, int i,
925 struct index_value **out)
926{
927 struct index_mm_node *child;
928 int j;
929 int ch;
930
931 while(node) {
932 for (j = 0; node->prefix[j]; j++) {
933 ch = node->prefix[j];
934
935 if (ch == '*' || ch == '?' || ch == '[') {
936 index_mm_searchwild_all(node, j, buf,
937 &key[i+j], out);
938 return;
939 }
940
941 if (ch != key[i+j]) {
942 index_mm_free_node(node);
943 return;
944 }
945 }
946
947 i += j;
948
949 child = index_mm_readchild(node, '*');
950 if (child) {
951 buf_pushchar(buf, '*');
952 index_mm_searchwild_all(child, 0, buf, &key[i], out);
953 buf_popchar(buf);
954 }
955
956 child = index_mm_readchild(node, '?');
957 if (child) {
958 buf_pushchar(buf, '?');
959 index_mm_searchwild_all(child, 0, buf, &key[i], out);
960 buf_popchar(buf);
961 }
962
963 child = index_mm_readchild(node, '[');
964 if (child) {
965 buf_pushchar(buf, '[');
966 index_mm_searchwild_all(child, 0, buf, &key[i], out);
967 buf_popchar(buf);
968 }
969
970 if (key[i] == '\0') {
971 index_mm_searchwild_allvalues(node, out);
972
973 return;
974 }
975
976 child = index_mm_readchild(node, key[i]);
977 index_mm_free_node(node);
978 node = child;
979 i++;
980 }
981}
982
983/*
984 * Search the index for a key. The index may contain wildcards.
985 *
986 * Returns a list of all the values of matching keys.
987 */
988struct index_value *index_mm_searchwild(struct index_mm *idx, const char *key)
989{
990 struct index_mm_node *root = index_mm_readroot(idx);
Gustavo Sverzut Barbieri405f6142011-12-08 14:36:30 -0200991 struct buffer buf;
Lucas De Marchibf89f702011-12-02 18:23:36 -0200992 struct index_value *out = NULL;
993
Gustavo Sverzut Barbieri405f6142011-12-08 14:36:30 -0200994 buf_init(&buf);
995 index_mm_searchwild_node(root, &buf, key, 0, &out);
996 buf_release(&buf);
Lucas De Marchibf89f702011-12-02 18:23:36 -0200997 return out;
998}