blob: 7fb378c91ebf3f6998ac9d921ba685170e5d435c [file] [log] [blame]
Lucas De Marchi8f923be2011-12-03 04:28:49 -02001/*
2 * libkmod - interface to kernel module operations
3 *
Lucas De Marchie6b0e492013-01-16 11:27:21 -02004 * Copyright (C) 2011-2013 ProFUSION embedded systems
Lucas De Marchi8f923be2011-12-03 04:28:49 -02005 *
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
Lucas De Marchic2e42862014-10-03 01:41:42 -030021#include <arpa/inet.h>
22#include <assert.h>
Lucas De Marchie8847fd2011-11-30 15:23:28 -020023#include <errno.h>
24#include <fnmatch.h>
Lucas De Marchibfcd31d2012-03-02 21:28:11 -030025#include <inttypes.h>
Lucas De Marchic2e42862014-10-03 01:41:42 -030026#include <stdio.h>
27#include <stdlib.h>
28#include <string.h>
Lucas De Marchie8847fd2011-11-30 15:23:28 -020029
Lucas De Marchi576dd432014-10-02 22:03:19 -030030#include <shared/macro.h>
Lucas De Marchib4d1f442014-10-11 13:03:21 -030031#include <shared/strbuf.h>
Lucas De Marchi96573a02014-10-03 00:01:35 -030032#include <shared/util.h>
Lucas De Marchi576dd432014-10-02 22:03:19 -030033
Lucas De Marchi83b855a2013-07-04 16:13:11 -030034#include "libkmod-internal.h"
Lucas De Marchie8847fd2011-11-30 15:23:28 -020035#include "libkmod-index.h"
Lucas De Marchie8847fd2011-11-30 15:23:28 -020036
Lucas De Marchic4cbdf82014-10-28 01:47:50 -020037/* libkmod-index.c: module index file implementation
38 *
39 * Integers are stored as 32 bit unsigned in "network" order, i.e. MSB first.
40 * All files start with a magic number.
41 *
42 * Magic spells "BOOTFAST". Second one used on newer versioned binary files.
43 * #define INDEX_MAGIC_OLD 0xB007FA57
44 *
45 * We use a version string to keep track of changes to the binary format
46 * This is stored in the form: INDEX_MAJOR (hi) INDEX_MINOR (lo) just in
47 * case we ever decide to have minor changes that are not incompatible.
48 */
49#define INDEX_MAGIC 0xB007F457
50#define INDEX_VERSION_MAJOR 0x0002
51#define INDEX_VERSION_MINOR 0x0001
52#define INDEX_VERSION ((INDEX_VERSION_MAJOR<<16)|INDEX_VERSION_MINOR)
Lucas De Marchi8f923be2011-12-03 04:28:49 -020053
Lucas De Marchic4cbdf82014-10-28 01:47:50 -020054/* The index file maps keys to values. Both keys and values are ASCII strings.
55 * Each key can have multiple values. Values are sorted by an integer priority.
56 *
57 * The reader also implements a wildcard search (including range expressions)
58 * where the keys in the index are treated as patterns.
59 * This feature is required for module aliases.
60 */
Gustavo Sverzut Barbieri148226e2011-12-10 11:53:51 -020061#define INDEX_CHILDMAX 128
62
63/* Disk format:
Lucas De Marchic4cbdf82014-10-28 01:47:50 -020064 *
65 * uint32_t magic = INDEX_MAGIC;
66 * uint32_t version = INDEX_VERSION;
67 * uint32_t root_offset;
68 *
69 * (node_offset & INDEX_NODE_MASK) specifies the file offset of nodes:
70 *
71 * char[] prefix; // nul terminated
72 *
73 * char first;
74 * char last;
75 * uint32_t children[last - first + 1];
76 *
77 * uint32_t value_count;
78 * struct {
79 * uint32_t priority;
80 * char[] value; // nul terminated
81 * } values[value_count];
82 *
83 * (node_offset & INDEX_NODE_FLAGS) indicates which fields are present.
84 * Empty prefixes are omitted, leaf nodes omit the three child-related fields.
85 *
86 * This could be optimised further by adding a sparse child format
87 * (indicated using a new flag).
88 *
89 *
90 * Implementation is based on a radix tree, or "trie".
91 * Each arc from parent to child is labelled with a character.
92 * Each path from the root represents a string.
93 *
94 * == Example strings ==
95 *
96 * ask
97 * ate
98 * on
99 * once
100 * one
101 *
102 * == Key ==
103 * + Normal node
104 * * Marked node, representing a key and it's values.
105 *
106 * +
107 * |-a-+-s-+-k-*
108 * | |
109 * | `-t-+-e-*
110 * |
111 * `-o-+-n-*-c-+-e-*
112 * |
113 * `-e-*
114 *
115 * Naive implementations tend to be very space inefficient; child pointers
116 * are stored in arrays indexed by character, but most child pointers are null.
117 *
118 * Our implementation uses a scheme described by Wikipedia as a Patrica trie,
119 *
120 * "easiest to understand as a space-optimized trie where
121 * each node with only one child is merged with its child"
122 *
123 * +
124 * |-a-+-sk-*
125 * | |
126 * | `-te-*
127 * |
128 * `-on-*-ce-*
129 * |
130 * `-e-*
131 *
132 * We still use arrays of child pointers indexed by a single character;
133 * the remaining characters of the label are stored as a "prefix" in the child.
134 *
135 * The paper describing the original Patrica trie works on individiual bits -
136 * each node has a maximum of two children, which increases space efficiency.
137 * However for this application it is simpler to use the ASCII character set.
138 * Since the index file is read-only, it can be compressed by omitting null
139 * child pointers at the start and end of arrays.
Gustavo Sverzut Barbieri148226e2011-12-10 11:53:51 -0200140 */
141
142/* Format of node offsets within index file */
143enum node_offset {
144 INDEX_NODE_FLAGS = 0xF0000000, /* Flags in high nibble */
145 INDEX_NODE_PREFIX = 0x80000000,
146 INDEX_NODE_VALUES = 0x40000000,
147 INDEX_NODE_CHILDS = 0x20000000,
148
149 INDEX_NODE_MASK = 0x0FFFFFFF, /* Offset value */
150};
151
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200152void index_values_free(struct index_value *values)
153{
154 while (values) {
155 struct index_value *value = values;
156
157 values = value->next;
158 free(value);
159 }
160}
161
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200162static int add_value(struct index_value **values,
Gustavo Sverzut Barbieri1433ba92011-12-08 14:50:29 -0200163 const char *value, unsigned len, unsigned int priority)
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200164{
165 struct index_value *v;
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200166
167 /* find position to insert value */
168 while (*values && (*values)->priority < priority)
169 values = &(*values)->next;
170
Gustavo Sverzut Barbieri1433ba92011-12-08 14:50:29 -0200171 v = malloc(sizeof(struct index_value) + len + 1);
172 if (!v)
173 return -1;
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200174 v->next = *values;
175 v->priority = priority;
Gustavo Sverzut Barbieri1433ba92011-12-08 14:50:29 -0200176 v->len = len;
177 memcpy(v->value, value, len);
178 v->value[len] = '\0';
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200179 *values = v;
180
Gustavo Sverzut Barbieri558b0202011-12-08 16:36:48 -0200181 return 0;
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200182}
183
Lucas De Marchi93688882011-12-02 10:05:31 -0200184static void read_error(void)
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200185{
186 fatal("Module index: unexpected error: %s\n"
187 "Try re-running depmod\n", errno ? strerror(errno) : "EOF");
188}
189
190static int read_char(FILE *in)
191{
192 int ch;
193
194 errno = 0;
195 ch = getc_unlocked(in);
196 if (ch == EOF)
197 read_error();
198 return ch;
199}
200
201static uint32_t read_long(FILE *in)
202{
203 uint32_t l;
204
205 errno = 0;
Leandro Pereirab6d985c2014-04-28 20:47:49 -0300206 if (fread(&l, sizeof(uint32_t), 1, in) != sizeof(uint32_t))
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200207 read_error();
208 return ntohl(l);
209}
210
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300211static unsigned buf_freadchars(struct strbuf *buf, FILE *in)
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200212{
213 unsigned i = 0;
214 int ch;
215
216 while ((ch = read_char(in))) {
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300217 if (!strbuf_pushchar(buf, ch))
Gustavo Sverzut Barbieri405f6142011-12-08 14:36:30 -0200218 break;
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200219 i++;
220 }
221
222 return i;
223}
224
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200225/*
Lucas De Marchieb8bb322011-12-02 10:23:02 -0200226 * Index file searching
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200227 */
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200228struct index_node_f {
229 FILE *file;
230 char *prefix; /* path compression */
231 struct index_value *values;
232 unsigned char first; /* range of child nodes */
233 unsigned char last;
234 uint32_t children[0];
235};
236
237static struct index_node_f *index_read(FILE *in, uint32_t offset)
238{
239 struct index_node_f *node;
240 char *prefix;
241 int i, child_count = 0;
242
243 if ((offset & INDEX_NODE_MASK) == 0)
244 return NULL;
245
246 fseek(in, offset & INDEX_NODE_MASK, SEEK_SET);
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200247
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200248 if (offset & INDEX_NODE_PREFIX) {
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300249 struct strbuf buf;
250 strbuf_init(&buf);
Gustavo Sverzut Barbieri405f6142011-12-08 14:36:30 -0200251 buf_freadchars(&buf, in);
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300252 prefix = strbuf_steal(&buf);
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200253 } else
254 prefix = NOFAIL(strdup(""));
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200255
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200256 if (offset & INDEX_NODE_CHILDS) {
257 char first = read_char(in);
258 char last = read_char(in);
259 child_count = last - first + 1;
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200260
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200261 node = NOFAIL(malloc(sizeof(struct index_node_f) +
262 sizeof(uint32_t) * child_count));
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200263
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200264 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 }
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200274
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200275 node->values = NULL;
276 if (offset & INDEX_NODE_VALUES) {
277 int value_count;
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300278 struct strbuf buf;
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200279 const char *value;
280 unsigned int priority;
281
282 value_count = read_long(in);
283
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300284 strbuf_init(&buf);
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200285 while (value_count--) {
286 priority = read_long(in);
Gustavo Sverzut Barbieri405f6142011-12-08 14:36:30 -0200287 buf_freadchars(&buf, in);
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300288 value = strbuf_str(&buf);
Gustavo Sverzut Barbieri1433ba92011-12-08 14:50:29 -0200289 add_value(&node->values, value, buf.used, priority);
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300290 strbuf_clear(&buf);
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200291 }
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300292 strbuf_release(&buf);
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200293 }
294
295 node->prefix = prefix;
296 node->file = in;
297 return node;
298}
299
300static void index_close(struct index_node_f *node)
301{
302 free(node->prefix);
303 index_values_free(node->values);
304 free(node);
305}
306
307struct index_file {
308 FILE *file;
309 uint32_t root_offset;
310};
311
312/* Failures are silent; modprobe will fall back to text files */
313struct index_file *index_file_open(const char *filename)
314{
315 FILE *file;
316 uint32_t magic, version;
317 struct index_file *new;
318
Cristian Rodríguez79e5ea92011-12-16 02:49:54 -0300319 file = fopen(filename, "re");
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200320 if (!file)
321 return NULL;
322 errno = EINVAL;
323
324 magic = read_long(file);
Cristian Rodríguez67d94ad2011-12-23 03:06:56 -0200325 if (magic != INDEX_MAGIC) {
326 fclose(file);
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200327 return NULL;
Cristian Rodríguez67d94ad2011-12-23 03:06:56 -0200328 }
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200329
330 version = read_long(file);
Cristian Rodríguez4088b272011-12-26 01:38:04 -0300331 if (version >> 16 != INDEX_VERSION_MAJOR) {
332 fclose(file);
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200333 return NULL;
Cristian Rodríguez4088b272011-12-26 01:38:04 -0300334 }
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200335
336 new = NOFAIL(malloc(sizeof(struct index_file)));
337 new->file = file;
338 new->root_offset = read_long(new->file);
339
340 errno = 0;
341 return new;
342}
343
Lucas De Marchi0fbdfef2011-12-02 09:56:22 -0200344void index_file_close(struct index_file *idx)
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200345{
Lucas De Marchi0fbdfef2011-12-02 09:56:22 -0200346 fclose(idx->file);
347 free(idx);
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200348}
349
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200350static struct index_node_f *index_readroot(struct index_file *in)
351{
352 return index_read(in->file, in->root_offset);
353}
354
355static struct index_node_f *index_readchild(const struct index_node_f *parent,
356 int ch)
357{
Lucas De Marchie71970a2011-12-02 10:27:15 -0200358 if (parent->first <= ch && ch <= parent->last) {
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200359 return index_read(parent->file,
360 parent->children[ch - parent->first]);
Lucas De Marchie71970a2011-12-02 10:27:15 -0200361 }
362
363 return NULL;
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200364}
365
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300366static void index_dump_node(struct index_node_f *node, struct strbuf *buf,
Lucas De Marchi758428a2012-01-16 15:56:17 -0200367 int fd)
368{
369 struct index_value *v;
370 int ch, pushed;
371
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300372 pushed = strbuf_pushchars(buf, node->prefix);
Lucas De Marchi758428a2012-01-16 15:56:17 -0200373
374 for (v = node->values; v != NULL; v = v->next) {
375 write_str_safe(fd, buf->bytes, buf->used);
376 write_str_safe(fd, " ", 1);
377 write_str_safe(fd, v->value, strlen(v->value));
378 write_str_safe(fd, "\n", 1);
379 }
380
381 for (ch = node->first; ch <= node->last; ch++) {
382 struct index_node_f *child = index_readchild(node, ch);
383
384 if (!child)
385 continue;
386
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300387 strbuf_pushchar(buf, ch);
Lucas De Marchi758428a2012-01-16 15:56:17 -0200388 index_dump_node(child, buf, fd);
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300389 strbuf_popchar(buf);
Lucas De Marchi758428a2012-01-16 15:56:17 -0200390 }
391
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300392 strbuf_popchars(buf, pushed);
Lucas De Marchi758428a2012-01-16 15:56:17 -0200393 index_close(node);
394}
395
396void index_dump(struct index_file *in, int fd, const char *prefix)
397{
398 struct index_node_f *root;
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300399 struct strbuf buf;
Lucas De Marchi758428a2012-01-16 15:56:17 -0200400
Lucas De Marchi681bf892013-04-23 21:21:00 -0300401 root = index_readroot(in);
402 if (root == NULL)
403 return;
404
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300405 strbuf_init(&buf);
406 strbuf_pushchars(&buf, prefix);
Lucas De Marchi758428a2012-01-16 15:56:17 -0200407 index_dump_node(root, &buf, fd);
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300408 strbuf_release(&buf);
Lucas De Marchi758428a2012-01-16 15:56:17 -0200409}
410
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200411static char *index_search__node(struct index_node_f *node, const char *key, int i)
412{
413 char *value;
414 struct index_node_f *child;
415 int ch;
416 int j;
417
418 while(node) {
419 for (j = 0; node->prefix[j]; j++) {
420 ch = node->prefix[j];
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200421
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200422 if (ch != key[i+j]) {
423 index_close(node);
424 return NULL;
425 }
426 }
Lucas De Marchie71970a2011-12-02 10:27:15 -0200427
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200428 i += j;
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200429
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200430 if (key[i] == '\0') {
Lucas De Marchi817f4e32012-02-27 19:54:33 -0300431 value = node->values != NULL
432 ? strdup(node->values[0].value)
433 : NULL;
434
435 index_close(node);
436 return value;
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200437 }
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200438
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200439 child = index_readchild(node, key[i]);
440 index_close(node);
441 node = child;
442 i++;
443 }
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200444
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200445 return NULL;
446}
447
448/*
Lucas De Marchi1d152ac2011-12-02 10:15:00 -0200449 * Search the index for a key
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200450 *
Lucas De Marchi1d152ac2011-12-02 10:15:00 -0200451 * Returns the value of the first match
452 *
453 * The recursive functions free their node argument (using index_close).
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200454 */
Lucas De Marchi1d152ac2011-12-02 10:15:00 -0200455char *index_search(struct index_file *in, const char *key)
456{
Lucas De Marchiee1d1882012-02-27 18:48:02 -0300457// FIXME: return value by reference instead of strdup
Lucas De Marchi1d152ac2011-12-02 10:15:00 -0200458 struct index_node_f *root;
459 char *value;
460
461 root = index_readroot(in);
462 value = index_search__node(root, key, 0);
463
464 return value;
465}
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200466
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200467
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200468
469/* Level 4: add all the values from a matching node */
470static void index_searchwild__allvalues(struct index_node_f *node,
Lucas De Marchi1d152ac2011-12-02 10:15:00 -0200471 struct index_value **out)
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200472{
Lucas De Marchi1d152ac2011-12-02 10:15:00 -0200473 struct index_value *v;
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200474
Lucas De Marchi1d152ac2011-12-02 10:15:00 -0200475 for (v = node->values; v != NULL; v = v->next)
Gustavo Sverzut Barbieri1433ba92011-12-08 14:50:29 -0200476 add_value(out, v->value, v->len, v->priority);
Lucas De Marchi1d152ac2011-12-02 10:15:00 -0200477
478 index_close(node);
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200479}
480
Lucas De Marchi1d152ac2011-12-02 10:15:00 -0200481/*
482 * Level 3: traverse a sub-keyspace which starts with a wildcard,
483 * looking for matches.
484 */
485static void index_searchwild__all(struct index_node_f *node, int j,
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300486 struct strbuf *buf,
Lucas De Marchi1d152ac2011-12-02 10:15:00 -0200487 const char *subkey,
488 struct index_value **out)
489{
490 int pushed = 0;
491 int ch;
492
493 while (node->prefix[j]) {
494 ch = node->prefix[j];
495
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300496 strbuf_pushchar(buf, ch);
Lucas De Marchi1d152ac2011-12-02 10:15:00 -0200497 pushed++;
498 j++;
499 }
500
501 for (ch = node->first; ch <= node->last; ch++) {
502 struct index_node_f *child = index_readchild(node, ch);
503
504 if (!child)
505 continue;
506
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300507 strbuf_pushchar(buf, ch);
Lucas De Marchi1d152ac2011-12-02 10:15:00 -0200508 index_searchwild__all(child, 0, buf, subkey, out);
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300509 strbuf_popchar(buf);
Lucas De Marchi1d152ac2011-12-02 10:15:00 -0200510 }
511
512 if (node->values) {
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300513 if (fnmatch(strbuf_str(buf), subkey, 0) == 0)
Lucas De Marchi1d152ac2011-12-02 10:15:00 -0200514 index_searchwild__allvalues(node, out);
Gustavo Sverzut Barbieri27fdf632011-12-10 13:28:18 -0200515 else
516 index_close(node);
Lucas De Marchi1d152ac2011-12-02 10:15:00 -0200517 } else {
518 index_close(node);
519 }
520
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300521 strbuf_popchars(buf, pushed);
Lucas De Marchi1d152ac2011-12-02 10:15:00 -0200522}
523
524/* Level 2: descend the tree (until we hit a wildcard) */
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200525static void index_searchwild__node(struct index_node_f *node,
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300526 struct strbuf *buf,
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200527 const char *key, int i,
528 struct index_value **out)
529{
530 struct index_node_f *child;
531 int j;
532 int ch;
533
534 while(node) {
535 for (j = 0; node->prefix[j]; j++) {
536 ch = node->prefix[j];
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200537
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200538 if (ch == '*' || ch == '?' || ch == '[') {
539 index_searchwild__all(node, j, buf,
540 &key[i+j], out);
541 return;
542 }
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200543
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200544 if (ch != key[i+j]) {
545 index_close(node);
546 return;
547 }
548 }
Lucas De Marchie71970a2011-12-02 10:27:15 -0200549
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200550 i += j;
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200551
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200552 child = index_readchild(node, '*');
553 if (child) {
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300554 strbuf_pushchar(buf, '*');
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200555 index_searchwild__all(child, 0, buf, &key[i], out);
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300556 strbuf_popchar(buf);
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200557 }
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200558
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200559 child = index_readchild(node, '?');
560 if (child) {
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300561 strbuf_pushchar(buf, '?');
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200562 index_searchwild__all(child, 0, buf, &key[i], out);
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300563 strbuf_popchar(buf);
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200564 }
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200565
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200566 child = index_readchild(node, '[');
567 if (child) {
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300568 strbuf_pushchar(buf, '[');
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200569 index_searchwild__all(child, 0, buf, &key[i], out);
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300570 strbuf_popchar(buf);
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200571 }
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200572
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200573 if (key[i] == '\0') {
574 index_searchwild__allvalues(node, out);
575
576 return;
577 }
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200578
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200579 child = index_readchild(node, key[i]);
580 index_close(node);
581 node = child;
582 i++;
583 }
584}
585
Lucas De Marchi1d152ac2011-12-02 10:15:00 -0200586/*
587 * Search the index for a key. The index may contain wildcards.
588 *
589 * Returns a list of all the values of matching keys.
590 */
591struct index_value *index_searchwild(struct index_file *in, const char *key)
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200592{
Lucas De Marchi1d152ac2011-12-02 10:15:00 -0200593 struct index_node_f *root = index_readroot(in);
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300594 struct strbuf buf;
Lucas De Marchi1d152ac2011-12-02 10:15:00 -0200595 struct index_value *out = NULL;
Lucas De Marchia7be73b2011-11-30 15:59:36 -0200596
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300597 strbuf_init(&buf);
Gustavo Sverzut Barbieri405f6142011-12-08 14:36:30 -0200598 index_searchwild__node(root, &buf, key, 0, &out);
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300599 strbuf_release(&buf);
Lucas De Marchi1d152ac2011-12-02 10:15:00 -0200600 return out;
Lucas De Marchie8847fd2011-11-30 15:23:28 -0200601}
Lucas De Marchib471a6b2011-12-01 23:14:20 -0200602
603#include <sys/mman.h>
604#include <sys/stat.h>
605#include <unistd.h>
606
Gustavo Sverzut Barbieri15c1c142011-12-10 11:44:31 -0200607static const char _idx_empty_str[] = "";
608
Lucas De Marchib471a6b2011-12-01 23:14:20 -0200609/**************************************************************************/
610/*
611 * Alternative implementation, using mmap to map all the file to memory when
612 * starting
613 */
614struct index_mm {
615 struct kmod_ctx *ctx;
616 void *mm;
617 uint32_t root_offset;
618 size_t size;
619};
620
Gustavo Sverzut Barbierid0915462011-12-10 13:04:43 -0200621struct index_mm_value {
622 unsigned int priority;
623 unsigned int len;
624 const char *value;
625};
626
627struct index_mm_value_array {
628 struct index_mm_value *values;
629 unsigned int len;
630};
631
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200632struct index_mm_node {
633 struct index_mm *idx;
Gustavo Sverzut Barbieri15c1c142011-12-10 11:44:31 -0200634 const char *prefix; /* mmape'd value */
Gustavo Sverzut Barbierid0915462011-12-10 13:04:43 -0200635 struct index_mm_value_array values;
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200636 unsigned char first;
637 unsigned char last;
638 uint32_t children[];
639};
640
641static inline uint32_t read_long_mm(void **p)
642{
Gustavo Sverzut Barbierifc2d8352011-12-10 11:36:35 -0200643 uint8_t *addr = *(uint8_t **)p;
644 uint32_t v;
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200645
Gustavo Sverzut Barbierifc2d8352011-12-10 11:36:35 -0200646 /* addr may be unalined to uint32_t */
Lucas De Marchi5bbec8c2012-05-23 19:32:58 -0300647 v = get_unaligned((uint32_t *) addr);
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200648
Gustavo Sverzut Barbierifc2d8352011-12-10 11:36:35 -0200649 *p = addr + sizeof(uint32_t);
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200650 return ntohl(v);
651}
652
653static inline uint8_t read_char_mm(void **p)
654{
Gustavo Sverzut Barbierifc2d8352011-12-10 11:36:35 -0200655 uint8_t *addr = *(uint8_t **)p;
656 uint8_t v = *addr;
657 *p = addr + sizeof(uint8_t);
658 return v;
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200659}
660
Gustavo Sverzut Barbieri1433ba92011-12-08 14:50:29 -0200661static inline char *read_chars_mm(void **p, unsigned *rlen)
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200662{
Gustavo Sverzut Barbierifc2d8352011-12-10 11:36:35 -0200663 char *addr = *(char **)p;
664 size_t len = *rlen = strlen(addr);
665 *p = addr + len + 1;
666 return addr;
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200667}
668
669static struct index_mm_node *index_mm_read_node(struct index_mm *idx,
670 uint32_t offset) {
671 void *p = idx->mm;
672 struct index_mm_node *node;
Gustavo Sverzut Barbieri15c1c142011-12-10 11:44:31 -0200673 const char *prefix;
Gustavo Sverzut Barbierid0915462011-12-10 13:04:43 -0200674 int i, child_count, value_count, children_padding;
675 uint32_t children[INDEX_CHILDMAX];
676 char first, last;
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200677
678 if ((offset & INDEX_NODE_MASK) == 0)
679 return NULL;
680
681 p = (char *)p + (offset & INDEX_NODE_MASK);
682
Gustavo Sverzut Barbieri15c1c142011-12-10 11:44:31 -0200683 if (offset & INDEX_NODE_PREFIX) {
684 unsigned len;
685 prefix = read_chars_mm(&p, &len);
686 } else
687 prefix = _idx_empty_str;
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200688
689 if (offset & INDEX_NODE_CHILDS) {
Gustavo Sverzut Barbierid0915462011-12-10 13:04:43 -0200690 first = read_char_mm(&p);
691 last = read_char_mm(&p);
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200692 child_count = last - first + 1;
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200693 for (i = 0; i < child_count; i++)
Gustavo Sverzut Barbierid0915462011-12-10 13:04:43 -0200694 children[i] = read_long_mm(&p);
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200695 } else {
Gustavo Sverzut Barbierid0915462011-12-10 13:04:43 -0200696 first = INDEX_CHILDMAX;
697 last = 0;
698 child_count = 0;
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200699 }
700
Gustavo Sverzut Barbieric6824b62011-12-21 18:23:58 -0200701 children_padding = (sizeof(struct index_mm_node) +
Gustavo Sverzut Barbierid0915462011-12-10 13:04:43 -0200702 (sizeof(uint32_t) * child_count)) % sizeof(void *);
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200703
Gustavo Sverzut Barbierid0915462011-12-10 13:04:43 -0200704 if (offset & INDEX_NODE_VALUES)
705 value_count = read_long_mm(&p);
706 else
707 value_count = 0;
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200708
Gustavo Sverzut Barbierid0915462011-12-10 13:04:43 -0200709 node = malloc(sizeof(struct index_mm_node)
710 + sizeof(uint32_t) * child_count + children_padding
711 + sizeof(struct index_mm_value) * value_count);
712 if (node == NULL)
713 return NULL;
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200714
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200715 node->idx = idx;
Gustavo Sverzut Barbierid0915462011-12-10 13:04:43 -0200716 node->prefix = prefix;
717 if (value_count == 0)
718 node->values.values = NULL;
719 else {
720 node->values.values = (struct index_mm_value *)
721 ((char *)node + sizeof(struct index_mm_node) +
722 sizeof(uint32_t) * child_count + children_padding);
723 }
724 node->values.len = value_count;
725 node->first = first;
726 node->last = last;
727 memcpy(node->children, children, sizeof(uint32_t) * child_count);
728
729 for (i = 0; i < value_count; i++) {
730 struct index_mm_value *v = node->values.values + i;
731 v->priority = read_long_mm(&p);
732 v->value = read_chars_mm(&p, &v->len);
733 }
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200734
735 return node;
736}
737
738static void index_mm_free_node(struct index_mm_node *node)
739{
Lucas De Marchi836be9a2011-12-02 17:27:52 -0200740 free(node);
741}
742
Lucas De Marchi5109f2b2011-12-08 15:10:55 -0200743struct index_mm *index_mm_open(struct kmod_ctx *ctx, const char *filename,
Lucas De Marchi2e2e2522012-03-02 20:33:26 -0300744 unsigned long long *stamp)
Lucas De Marchib471a6b2011-12-01 23:14:20 -0200745{
746 int fd;
747 struct stat st;
748 struct index_mm *idx;
749 struct {
750 uint32_t magic;
751 uint32_t version;
752 uint32_t root_offset;
753 } hdr;
754 void *p;
755
756 DBG(ctx, "file=%s\n", filename);
757
Lucas De Marchi7d51d8b2011-12-12 18:41:57 -0200758 idx = malloc(sizeof(*idx));
759 if (idx == NULL) {
Gustavo Sverzut Barbieridfa96f12012-01-07 19:37:37 -0200760 ERR(ctx, "malloc: %m\n");
Lucas De Marchib471a6b2011-12-01 23:14:20 -0200761 return NULL;
762 }
763
Cristian Rodríguez79e5ea92011-12-16 02:49:54 -0300764 if ((fd = open(filename, O_RDONLY|O_CLOEXEC)) < 0) {
Lucas De Marchi73298172012-02-13 21:58:36 -0200765 DBG(ctx, "open(%s, O_RDONLY|O_CLOEXEC): %m\n", filename);
Lucas De Marchi7d51d8b2011-12-12 18:41:57 -0200766 goto fail_open;
Lucas De Marchib471a6b2011-12-01 23:14:20 -0200767 }
768
Leandro Pereirad36c8862014-04-28 20:44:14 -0300769 if (fstat(fd, &st) < 0)
770 goto fail_nommap;
Lucas De Marchi5b05c322012-06-06 09:36:29 -0300771 if ((size_t) st.st_size < sizeof(hdr))
772 goto fail_nommap;
Lucas De Marchi5109f2b2011-12-08 15:10:55 -0200773
Kees Cookc3e8d262013-02-18 12:02:34 -0800774 if ((idx->mm = mmap(NULL, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0))
Lucas De Marchi5109f2b2011-12-08 15:10:55 -0200775 == MAP_FAILED) {
Kees Cookc3e8d262013-02-18 12:02:34 -0800776 ERR(ctx, "mmap(NULL, %"PRIu64", PROT_READ, %d, MAP_PRIVATE, 0): %m\n",
Lucas De Marchi2e2e2522012-03-02 20:33:26 -0300777 st.st_size, fd);
Lucas De Marchi5b05c322012-06-06 09:36:29 -0300778 goto fail_nommap;
Lucas De Marchib471a6b2011-12-01 23:14:20 -0200779 }
780
781 p = idx->mm;
782 hdr.magic = read_long_mm(&p);
783 hdr.version = read_long_mm(&p);
784 hdr.root_offset = read_long_mm(&p);
785
786 if (hdr.magic != INDEX_MAGIC) {
787 ERR(ctx, "magic check fail: %x instead of %x\n", hdr.magic,
788 INDEX_MAGIC);
789 goto fail;
790 }
791
792 if (hdr.version >> 16 != INDEX_VERSION_MAJOR) {
793 ERR(ctx, "major version check fail: %u instead of %u\n",
Holger Obermaier1a4aa7e2014-09-04 14:38:16 +0200794 hdr.version >> 16, INDEX_VERSION_MAJOR);
Lucas De Marchib471a6b2011-12-01 23:14:20 -0200795 goto fail;
796 }
797
798 idx->root_offset = hdr.root_offset;
799 idx->size = st.st_size;
800 idx->ctx = ctx;
801 close(fd);
802
Lucas De Marchi6068aaa2012-01-17 12:10:42 -0200803 *stamp = stat_mstamp(&st);
Lucas De Marchi9fd58f32011-12-31 18:53:24 -0200804
Lucas De Marchib471a6b2011-12-01 23:14:20 -0200805 return idx;
806
807fail:
Lucas De Marchi5b05c322012-06-06 09:36:29 -0300808 munmap(idx->mm, st.st_size);
809fail_nommap:
Lucas De Marchib471a6b2011-12-01 23:14:20 -0200810 close(fd);
Gustavo Sverzut Barbieria5a92a62011-12-16 16:17:50 -0200811fail_open:
Lucas De Marchib471a6b2011-12-01 23:14:20 -0200812 free(idx);
813 return NULL;
814}
815
816void index_mm_close(struct index_mm *idx)
817{
818 munmap(idx->mm, idx->size);
819 free(idx);
820}
Lucas De Marchi77bf9362011-12-02 17:41:30 -0200821
822static struct index_mm_node *index_mm_readroot(struct index_mm *idx)
823{
824 return index_mm_read_node(idx, idx->root_offset);
825}
Lucas De Marchi91298dc2011-12-02 17:41:46 -0200826
827static struct index_mm_node *index_mm_readchild(const struct index_mm_node *parent,
828 int ch)
829{
830 if (parent->first <= ch && ch <= parent->last) {
831 return index_mm_read_node(parent->idx,
832 parent->children[ch - parent->first]);
833 }
834
835 return NULL;
836}
Lucas De Marchie33bb872011-12-02 17:45:01 -0200837
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300838static void index_mm_dump_node(struct index_mm_node *node, struct strbuf *buf,
Lucas De Marchi758428a2012-01-16 15:56:17 -0200839 int fd)
840{
841 struct index_mm_value *itr, *itr_end;
842 int ch, pushed;
843
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300844 pushed = strbuf_pushchars(buf, node->prefix);
Lucas De Marchi758428a2012-01-16 15:56:17 -0200845
846 itr = node->values.values;
847 itr_end = itr + node->values.len;
848 for (; itr < itr_end; itr++) {
849 write_str_safe(fd, buf->bytes, buf->used);
850 write_str_safe(fd, " ", 1);
851 write_str_safe(fd, itr->value, itr->len);
852 write_str_safe(fd, "\n", 1);
853 }
854
855 for (ch = node->first; ch <= node->last; ch++) {
856 struct index_mm_node *child = index_mm_readchild(node, ch);
857
858 if (child == NULL)
859 continue;
860
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300861 strbuf_pushchar(buf, ch);
Lucas De Marchi758428a2012-01-16 15:56:17 -0200862 index_mm_dump_node(child, buf, fd);
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300863 strbuf_popchar(buf);
Lucas De Marchi758428a2012-01-16 15:56:17 -0200864 }
865
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300866 strbuf_popchars(buf, pushed);
Lucas De Marchi758428a2012-01-16 15:56:17 -0200867 index_mm_free_node(node);
868}
869
870void index_mm_dump(struct index_mm *idx, int fd, const char *prefix)
871{
872 struct index_mm_node *root;
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300873 struct strbuf buf;
Lucas De Marchi758428a2012-01-16 15:56:17 -0200874
Lucas De Marchi681bf892013-04-23 21:21:00 -0300875 root = index_mm_readroot(idx);
876 if (root == NULL)
877 return;
878
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300879 strbuf_init(&buf);
880 strbuf_pushchars(&buf, prefix);
Lucas De Marchi758428a2012-01-16 15:56:17 -0200881 index_mm_dump_node(root, &buf, fd);
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300882 strbuf_release(&buf);
Lucas De Marchi758428a2012-01-16 15:56:17 -0200883}
884
Lucas De Marchie33bb872011-12-02 17:45:01 -0200885static char *index_mm_search_node(struct index_mm_node *node, const char *key,
886 int i)
887{
888 char *value;
889 struct index_mm_node *child;
890 int ch;
891 int j;
892
893 while(node) {
894 for (j = 0; node->prefix[j]; j++) {
895 ch = node->prefix[j];
896
897 if (ch != key[i+j]) {
898 index_mm_free_node(node);
899 return NULL;
900 }
901 }
902
903 i += j;
904
905 if (key[i] == '\0') {
Lucas De Marchi817f4e32012-02-27 19:54:33 -0300906 value = node->values.len > 0
907 ? strdup(node->values.values[0].value)
908 : NULL;
909
910 index_mm_free_node(node);
911 return value;
Lucas De Marchie33bb872011-12-02 17:45:01 -0200912 }
913
914 child = index_mm_readchild(node, key[i]);
915 index_mm_free_node(node);
916 node = child;
917 i++;
918 }
919
920 return NULL;
921}
Lucas De Marchib797b792011-12-02 17:49:03 -0200922
923/*
924 * Search the index for a key
925 *
926 * Returns the value of the first match
927 *
928 * The recursive functions free their node argument (using index_close).
929 */
930char *index_mm_search(struct index_mm *idx, const char *key)
931{
Lucas De Marchiee1d1882012-02-27 18:48:02 -0300932// FIXME: return value by reference instead of strdup
Lucas De Marchib797b792011-12-02 17:49:03 -0200933 struct index_mm_node *root;
934 char *value;
935
936 root = index_mm_readroot(idx);
937 value = index_mm_search_node(root, key, 0);
938
939 return value;
940}
Lucas De Marchibf89f702011-12-02 18:23:36 -0200941
942/* Level 4: add all the values from a matching node */
943static void index_mm_searchwild_allvalues(struct index_mm_node *node,
944 struct index_value **out)
945{
Gustavo Sverzut Barbierid0915462011-12-10 13:04:43 -0200946 struct index_mm_value *itr, *itr_end;
Lucas De Marchibf89f702011-12-02 18:23:36 -0200947
Gustavo Sverzut Barbierid0915462011-12-10 13:04:43 -0200948 itr = node->values.values;
949 itr_end = itr + node->values.len;
950 for (; itr < itr_end; itr++)
951 add_value(out, itr->value, itr->len, itr->priority);
Lucas De Marchibf89f702011-12-02 18:23:36 -0200952
953 index_mm_free_node(node);
954}
955
956/*
957 * Level 3: traverse a sub-keyspace which starts with a wildcard,
958 * looking for matches.
959 */
960static void index_mm_searchwild_all(struct index_mm_node *node, int j,
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300961 struct strbuf *buf,
Lucas De Marchibf89f702011-12-02 18:23:36 -0200962 const char *subkey,
963 struct index_value **out)
964{
965 int pushed = 0;
966 int ch;
967
968 while (node->prefix[j]) {
969 ch = node->prefix[j];
970
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300971 strbuf_pushchar(buf, ch);
Lucas De Marchibf89f702011-12-02 18:23:36 -0200972 pushed++;
973 j++;
974 }
975
976 for (ch = node->first; ch <= node->last; ch++) {
977 struct index_mm_node *child = index_mm_readchild(node, ch);
978
979 if (!child)
980 continue;
981
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300982 strbuf_pushchar(buf, ch);
Lucas De Marchibf89f702011-12-02 18:23:36 -0200983 index_mm_searchwild_all(child, 0, buf, subkey, out);
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300984 strbuf_popchar(buf);
Lucas De Marchibf89f702011-12-02 18:23:36 -0200985 }
986
Gustavo Sverzut Barbierid0915462011-12-10 13:04:43 -0200987 if (node->values.len > 0) {
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300988 if (fnmatch(strbuf_str(buf), subkey, 0) == 0)
Lucas De Marchibf89f702011-12-02 18:23:36 -0200989 index_mm_searchwild_allvalues(node, out);
Gustavo Sverzut Barbieri27fdf632011-12-10 13:28:18 -0200990 else
991 index_mm_free_node(node);
Lucas De Marchibf89f702011-12-02 18:23:36 -0200992 } else {
993 index_mm_free_node(node);
994 }
995
Lucas De Marchi15a7ae32014-10-11 13:25:51 -0300996 strbuf_popchars(buf, pushed);
Lucas De Marchibf89f702011-12-02 18:23:36 -0200997}
998
999/* Level 2: descend the tree (until we hit a wildcard) */
1000static void index_mm_searchwild_node(struct index_mm_node *node,
Lucas De Marchi15a7ae32014-10-11 13:25:51 -03001001 struct strbuf *buf,
Lucas De Marchibf89f702011-12-02 18:23:36 -02001002 const char *key, int i,
1003 struct index_value **out)
1004{
1005 struct index_mm_node *child;
1006 int j;
1007 int ch;
1008
1009 while(node) {
1010 for (j = 0; node->prefix[j]; j++) {
1011 ch = node->prefix[j];
1012
1013 if (ch == '*' || ch == '?' || ch == '[') {
1014 index_mm_searchwild_all(node, j, buf,
1015 &key[i+j], out);
1016 return;
1017 }
1018
1019 if (ch != key[i+j]) {
1020 index_mm_free_node(node);
1021 return;
1022 }
1023 }
1024
1025 i += j;
1026
1027 child = index_mm_readchild(node, '*');
1028 if (child) {
Lucas De Marchi15a7ae32014-10-11 13:25:51 -03001029 strbuf_pushchar(buf, '*');
Lucas De Marchibf89f702011-12-02 18:23:36 -02001030 index_mm_searchwild_all(child, 0, buf, &key[i], out);
Lucas De Marchi15a7ae32014-10-11 13:25:51 -03001031 strbuf_popchar(buf);
Lucas De Marchibf89f702011-12-02 18:23:36 -02001032 }
1033
1034 child = index_mm_readchild(node, '?');
1035 if (child) {
Lucas De Marchi15a7ae32014-10-11 13:25:51 -03001036 strbuf_pushchar(buf, '?');
Lucas De Marchibf89f702011-12-02 18:23:36 -02001037 index_mm_searchwild_all(child, 0, buf, &key[i], out);
Lucas De Marchi15a7ae32014-10-11 13:25:51 -03001038 strbuf_popchar(buf);
Lucas De Marchibf89f702011-12-02 18:23:36 -02001039 }
1040
1041 child = index_mm_readchild(node, '[');
1042 if (child) {
Lucas De Marchi15a7ae32014-10-11 13:25:51 -03001043 strbuf_pushchar(buf, '[');
Lucas De Marchibf89f702011-12-02 18:23:36 -02001044 index_mm_searchwild_all(child, 0, buf, &key[i], out);
Lucas De Marchi15a7ae32014-10-11 13:25:51 -03001045 strbuf_popchar(buf);
Lucas De Marchibf89f702011-12-02 18:23:36 -02001046 }
1047
1048 if (key[i] == '\0') {
1049 index_mm_searchwild_allvalues(node, out);
1050
1051 return;
1052 }
1053
1054 child = index_mm_readchild(node, key[i]);
1055 index_mm_free_node(node);
1056 node = child;
1057 i++;
1058 }
1059}
1060
1061/*
1062 * Search the index for a key. The index may contain wildcards.
1063 *
1064 * Returns a list of all the values of matching keys.
1065 */
1066struct index_value *index_mm_searchwild(struct index_mm *idx, const char *key)
1067{
1068 struct index_mm_node *root = index_mm_readroot(idx);
Lucas De Marchi15a7ae32014-10-11 13:25:51 -03001069 struct strbuf buf;
Lucas De Marchibf89f702011-12-02 18:23:36 -02001070 struct index_value *out = NULL;
1071
Lucas De Marchi15a7ae32014-10-11 13:25:51 -03001072 strbuf_init(&buf);
Gustavo Sverzut Barbieri405f6142011-12-08 14:36:30 -02001073 index_mm_searchwild_node(root, &buf, key, 0, &out);
Lucas De Marchi15a7ae32014-10-11 13:25:51 -03001074 strbuf_release(&buf);
Lucas De Marchibf89f702011-12-02 18:23:36 -02001075 return out;
1076}