-/* index.c: module index file shared functions for modprobe and depmod
- Copyright (C) 2008 Alan Jenkins <alan-jenkins@tuffmail.co.uk>.
-
- These programs are free software; you can redistribute it and/or modify
- it under the terms of the GNU General Public License as published by
- the Free Software Foundation; either version 2 of the License, or
- (at your option) any later version.
-
- This program is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- GNU General Public License for more details.
-
- You should have received a copy of the GNU General Public License
- along with these programs. If not, see <http://www.gnu.org/licenses/>.
-*/
+/*
+ * libkmod - interface to kernel module operations
+ *
+ * Copyright (C) 2011-2012 ProFUSION embedded systems
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
+ */
#include <arpa/inet.h> /* htonl */
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <fnmatch.h>
+#include <assert.h>
#include "libkmod-private.h"
#include "libkmod-index.h"
#include "macro.h"
-/*
- * Index abstract data type (used only by depmod)
- */
+/* index.c: module index file shared functions for modprobe and depmod */
-struct index_node *index_create()
-{
- struct index_node *node;
+#define INDEX_CHILDMAX 128
- node = NOFAIL(calloc(sizeof(struct index_node), 1));
- node->prefix = NOFAIL(strdup(""));
- node->first = INDEX_CHILDMAX;
+/* Disk format:
- return node;
-}
+ uint32_t magic = INDEX_MAGIC;
+ uint32_t version = INDEX_VERSION;
+ uint32_t root_offset;
-void index_values_free(struct index_value *values)
-{
- while (values) {
- struct index_value *value = values;
+ (node_offset & INDEX_NODE_MASK) specifies the file offset of nodes:
- values = value->next;
- free(value);
- }
-}
+ char[] prefix; // nul terminated
-void index_destroy(struct index_node *node)
-{
- int c;
+ char first;
+ char last;
+ uint32_t children[last - first + 1];
- for (c = node->first; c <= node->last; c++) {
- struct index_node *child = node->children[c];
+ uint32_t value_count;
+ struct {
+ uint32_t priority;
+ char[] value; // nul terminated
+ } values[value_count];
- if (child)
- index_destroy(child);
- }
- index_values_free(node->values);
- free(node->prefix);
- free(node);
-}
+ (node_offset & INDEX_NODE_FLAGS) indicates which fields are present.
+ Empty prefixes are omitted, leaf nodes omit the three child-related fields.
-static void index__checkstring(const char *str)
-{
- int i;
+ This could be optimised further by adding a sparse child format
+ (indicated using a new flag).
+ */
+
+/* Format of node offsets within index file */
+enum node_offset {
+ INDEX_NODE_FLAGS = 0xF0000000, /* Flags in high nibble */
+ INDEX_NODE_PREFIX = 0x80000000,
+ INDEX_NODE_VALUES = 0x40000000,
+ INDEX_NODE_CHILDS = 0x20000000,
+
+ INDEX_NODE_MASK = 0x0FFFFFFF, /* Offset value */
+};
- for (i = 0; str[i]; i++) {
- int ch = str[i];
+void index_values_free(struct index_value *values)
+{
+ while (values) {
+ struct index_value *value = values;
- if (ch >= INDEX_CHILDMAX)
- fatal("Module index: bad character '%c'=0x%x - only 7-bit ASCII is supported:"
- "\n%s\n", (char) ch, (int) ch, str);
+ values = value->next;
+ free(value);
}
}
static int add_value(struct index_value **values,
- const char *value, unsigned int priority)
+ const char *value, unsigned len, unsigned int priority)
{
struct index_value *v;
- int duplicate = 0;
- int len;
-
- /* report the presence of duplicate values */
- for (v = *values; v; v = v->next) {
- if (streq(v->value, value))
- duplicate = 1;
- }
/* find position to insert value */
while (*values && (*values)->priority < priority)
values = &(*values)->next;
- len = strlen(value);
- v = NOFAIL(calloc(sizeof(struct index_value) + len + 1, 1));
+ v = malloc(sizeof(struct index_value) + len + 1);
+ if (!v)
+ return -1;
v->next = *values;
v->priority = priority;
- memcpy(v->value, value, len + 1);
+ v->len = len;
+ memcpy(v->value, value, len);
+ v->value[len] = '\0';
*values = v;
- return duplicate;
+ return 0;
}
-int index_insert(struct index_node *node, const char *key,
- const char *value, unsigned int priority)
-{
- int i = 0; /* index within str */
- int ch;
-
- index__checkstring(key);
- index__checkstring(value);
-
- while(1) {
- int j; /* index within node->prefix */
-
- /* Ensure node->prefix is a prefix of &str[i].
- If it is not already, then we must split node. */
- for (j = 0; node->prefix[j]; j++) {
- ch = node->prefix[j];
-
- if (ch != key[i+j]) {
- char *prefix = node->prefix;
- struct index_node *n;
-
- /* New child is copy of node with prefix[j+1..N] */
- n = NOFAIL(calloc(sizeof(struct index_node), 1));
- memcpy(n, node, sizeof(struct index_node));
- n->prefix = NOFAIL(strdup(&prefix[j+1]));
-
- /* Parent has prefix[0..j], child at prefix[j] */
- memset(node, 0, sizeof(struct index_node));
- prefix[j] = '\0';
- node->prefix = prefix;
- node->first = ch;
- node->last = ch;
- node->children[ch] = n;
-
- break;
- }
- }
- /* j is now length of node->prefix */
- i += j;
-
- ch = key[i];
- if(ch == '\0')
- return add_value(&node->values, value, priority);
-
- if (!node->children[ch]) {
- struct index_node *child;
-
- if (ch < node->first)
- node->first = ch;
- if (ch > node->last)
- node->last = ch;
- node->children[ch] = NOFAIL(calloc(sizeof(struct index_node), 1));
-
- child = node->children[ch];
- child->prefix = NOFAIL(strdup(&key[i+1]));
- child->first = INDEX_CHILDMAX;
- add_value(&child->values, value, priority);
-
- return 0;
- }
-
- /* Descend into child node and continue */
- node = node->children[ch];
- i++;
- }
-}
-
-static int index__haschildren(const struct index_node *node)
-{
- return node->first < INDEX_CHILDMAX;
-}
-
-/* Recursive post-order traversal
-
- Pre-order would make for better read-side buffering / readahead / caching.
- (post-order means you go backwards in the file as you descend the tree).
- However, index reading is already fast enough.
- Pre-order is simpler for writing, and depmod is already slow.
- */
-static uint32_t index_write__node(const struct index_node *node, FILE *out)
-{
- uint32_t *child_offs = NULL;
- int child_count = 0;
- long offset;
-
- if (!node)
- return 0;
-
- /* Write children and save their offsets */
- if (index__haschildren(node)) {
- const struct index_node *child;
- int i;
-
- child_count = node->last - node->first + 1;
- child_offs = NOFAIL(malloc(child_count * sizeof(uint32_t)));
-
- for (i = 0; i < child_count; i++) {
- child = node->children[node->first + i];
- child_offs[i] = htonl(index_write__node(child, out));
- }
- }
-
- /* Now write this node */
- offset = ftell(out);
-
- if (node->prefix[0]) {
- fputs(node->prefix, out);
- fputc('\0', out);
- offset |= INDEX_NODE_PREFIX;
- }
-
- if (child_count) {
- fputc(node->first, out);
- fputc(node->last, out);
- fwrite(child_offs, sizeof(uint32_t), child_count, out);
- free(child_offs);
- offset |= INDEX_NODE_CHILDS;
- }
-
- if (node->values) {
- const struct index_value *v;
- unsigned int value_count;
- uint32_t u;
-
- value_count = 0;
- for (v = node->values; v != NULL; v = v->next)
- value_count++;
- u = htonl(value_count);
- fwrite(&u, sizeof(u), 1, out);
-
- for (v = node->values; v != NULL; v = v->next) {
- u = htonl(v->priority);
- fwrite(&u, sizeof(u), 1, out);
- fputs(v->value, out);
- fputc('\0', out);
- }
- offset |= INDEX_NODE_VALUES;
- }
-
- return offset;
-}
-
-void index_write(const struct index_node *node, FILE *out)
-{
- long initial_offset, final_offset;
- uint32_t u;
-
- u = htonl(INDEX_MAGIC);
- fwrite(&u, sizeof(u), 1, out);
- u = htonl(INDEX_VERSION);
- fwrite(&u, sizeof(u), 1, out);
-
- /* Second word is reserved for the offset of the root node */
- initial_offset = ftell(out);
- u = 0;
- fwrite(&u, sizeof(uint32_t), 1, out);
-
- /* Dump trie */
- u = htonl(index_write__node(node, out));
-
- /* Update first word */
- final_offset = ftell(out);
- fseek(out, initial_offset, SEEK_SET);
- fwrite(&u, sizeof(uint32_t), 1, out);
- fseek(out, final_offset, SEEK_SET);
-}
-
-
-
-static void read_error()
+static void read_error(void)
{
fatal("Module index: unexpected error: %s\n"
"Try re-running depmod\n", errno ? strerror(errno) : "EOF");
* They help build wildcard key strings to pass to fnmatch(),
* as well as building values of matching keys.
*/
-
struct buffer {
char *bytes;
unsigned size;
unsigned used;
};
-static void buf__realloc(struct buffer *buf, unsigned size)
+#define BUF_STEP (2048)
+static bool buf_grow(struct buffer *buf, size_t newsize)
{
- if (size > buf->size) {
- buf->bytes = NOFAIL(realloc(buf->bytes, size));
- buf->size = size;
- }
+ void *tmp;
+ size_t sz;
+
+ if (newsize % BUF_STEP == 0)
+ sz = newsize;
+ else
+ sz = ((newsize / BUF_STEP) + 1) * BUF_STEP;
+
+ if (buf->size == sz)
+ return true;
+
+ tmp = realloc(buf->bytes, sz);
+ if (sz > 0 && tmp == NULL)
+ return false;
+ buf->bytes = tmp;
+ buf->size = sz;
+ return true;
}
-static struct buffer *buf_create()
+static void buf_init(struct buffer *buf)
{
- struct buffer *buf;
-
- buf = NOFAIL(calloc(sizeof(struct buffer), 1));
- buf__realloc(buf, 256);
- return buf;
+ buf->bytes = NULL;
+ buf->size = 0;
+ buf->used = 0;
}
-static void buf_destroy(struct buffer *buf)
+static void buf_release(struct buffer *buf)
{
free(buf->bytes);
- free(buf);
}
/* Destroy buffer and return a copy as a C string */
-static char *buf_detach(struct buffer *buf)
+static char *buf_steal(struct buffer *buf)
{
char *bytes;
- bytes = NOFAIL(realloc(buf->bytes, buf->used + 1));
+ bytes = realloc(buf->bytes, buf->used + 1);
+ if (!bytes) {
+ free(buf->bytes);
+ return NULL;
+ }
bytes[buf->used] = '\0';
-
- free(buf);
return bytes;
}
*/
static const char *buf_str(struct buffer *buf)
{
- buf__realloc(buf, buf->used + 1);
+ if (!buf_grow(buf, buf->used + 1))
+ return NULL;
buf->bytes[buf->used] = '\0';
return buf->bytes;
}
-static int buf_fwrite(struct buffer *buf, FILE *out)
+static bool buf_pushchar(struct buffer *buf, char ch)
{
- return fwrite(buf->bytes, 1, buf->used, out);
-}
-
-static void buf_pushchar(struct buffer *buf, char ch)
-{
- buf__realloc(buf, buf->used + 1);
+ if (!buf_grow(buf, buf->used + 1))
+ return false;
buf->bytes[buf->used] = ch;
buf->used++;
+ return true;
}
static unsigned buf_pushchars(struct buffer *buf, const char *str)
buf_pushchar(buf, ch);
i++;
}
+
return i;
}
-/* like buf_pushchars(), but the string comes from a file */
static unsigned buf_freadchars(struct buffer *buf, FILE *in)
{
unsigned i = 0;
int ch;
while ((ch = read_char(in))) {
- buf_pushchar(buf, ch);
+ if (!buf_pushchar(buf, ch))
+ break;
i++;
}
static void buf_popchar(struct buffer *buf)
{
+ assert(buf->used > 0);
buf->used--;
}
static void buf_popchars(struct buffer *buf, unsigned n)
{
+ assert(buf->used >= n);
buf->used -= n;
}
}
/*
- * Index file searching (used only by modprobe)
+ * Index file searching
*/
-
struct index_node_f {
FILE *file;
char *prefix; /* path compression */
fseek(in, offset & INDEX_NODE_MASK, SEEK_SET);
if (offset & INDEX_NODE_PREFIX) {
- struct buffer *buf = buf_create();
- buf_freadchars(buf, in);
- prefix = buf_detach(buf);
+ struct buffer buf;
+ buf_init(&buf);
+ buf_freadchars(&buf, in);
+ prefix = buf_steal(&buf);
} else
prefix = NOFAIL(strdup(""));
node->values = NULL;
if (offset & INDEX_NODE_VALUES) {
int value_count;
- struct buffer *buf = buf_create();
+ struct buffer buf;
const char *value;
unsigned int priority;
value_count = read_long(in);
+ buf_init(&buf);
while (value_count--) {
priority = read_long(in);
- buf_freadchars(buf, in);
- value = buf_str(buf);
- add_value(&node->values, value, priority);
- buf_clear(buf);
+ buf_freadchars(&buf, in);
+ value = buf_str(&buf);
+ add_value(&node->values, value, buf.used, priority);
+ buf_clear(&buf);
}
- buf_destroy(buf);
+ buf_release(&buf);
}
node->prefix = prefix;
uint32_t magic, version;
struct index_file *new;
- file = fopen(filename, "r");
+ file = fopen(filename, "re");
if (!file)
return NULL;
errno = EINVAL;
magic = read_long(file);
- if (magic != INDEX_MAGIC)
+ if (magic != INDEX_MAGIC) {
+ fclose(file);
return NULL;
+ }
version = read_long(file);
- if (version >> 16 != INDEX_VERSION_MAJOR)
+ if (version >> 16 != INDEX_VERSION_MAJOR) {
+ fclose(file);
return NULL;
+ }
new = NOFAIL(malloc(sizeof(struct index_file)));
new->file = file;
return new;
}
-void index_file_close(struct index_file *index)
+void index_file_close(struct index_file *idx)
{
- fclose(index->file);
- free(index);
+ fclose(idx->file);
+ free(idx);
}
-
static struct index_node_f *index_readroot(struct index_file *in)
{
return index_read(in->file, in->root_offset);
static struct index_node_f *index_readchild(const struct index_node_f *parent,
int ch)
{
- if (parent->first <= ch && ch <= parent->last)
+ if (parent->first <= ch && ch <= parent->last) {
return index_read(parent->file,
parent->children[ch - parent->first]);
- else
- return NULL;
-}
+ }
-/*
- * Dump all strings as lines in a plain text file.
- */
+ return NULL;
+}
-static void index_dump_node(struct index_node_f *node,
- struct buffer *buf,
- FILE *out,
- const char *prefix)
+static void index_dump_node(struct index_node_f *node, struct buffer *buf,
+ int fd)
{
struct index_value *v;
int ch, pushed;
pushed = buf_pushchars(buf, node->prefix);
for (v = node->values; v != NULL; v = v->next) {
- fputs(prefix, out);
- buf_fwrite(buf, out);
- fputc(' ', out);
- fputs(v->value, out);
- fputc('\n', out);
+ write_str_safe(fd, buf->bytes, buf->used);
+ write_str_safe(fd, " ", 1);
+ write_str_safe(fd, v->value, strlen(v->value));
+ write_str_safe(fd, "\n", 1);
}
for (ch = node->first; ch <= node->last; ch++) {
continue;
buf_pushchar(buf, ch);
- index_dump_node(child, buf, out, prefix);
+ index_dump_node(child, buf, fd);
buf_popchar(buf);
}
index_close(node);
}
-void index_dump(struct index_file *in, FILE *out, const char *prefix)
-{
- struct index_node_f *root;
- struct buffer *buf;
-
- buf = buf_create();
- root = index_readroot(in);
- index_dump_node(root, buf, out, prefix);
- buf_destroy(buf);
-}
-
-/*
- * Search the index for a key
- *
- * Returns the value of the first match
- *
- * The recursive functions free their node argument (using index_close).
- */
-
-char *index_search(struct index_file *in, const char *key);
-static char *index_search__node(struct index_node_f *node, const char *key, int i);
-
-char *index_search(struct index_file *in, const char *key)
+void index_dump(struct index_file *in, int fd, const char *prefix)
{
struct index_node_f *root;
- char *value;
+ struct buffer buf;
+ buf_init(&buf);
+ buf_pushchars(&buf, prefix);
root = index_readroot(in);
- value = index_search__node(root, key, 0);
-
- return value;
+ index_dump_node(root, &buf, fd);
+ buf_release(&buf);
}
static char *index_search__node(struct index_node_f *node, const char *key, int i)
return NULL;
}
}
+
i += j;
if (key[i] == '\0') {
}
/*
- * Search the index for a key. The index may contain wildcards.
+ * Search the index for a key
*
- * Returns a list of all the values of matching keys.
+ * Returns the value of the first match
+ *
+ * The recursive functions free their node argument (using index_close).
*/
+char *index_search(struct index_file *in, const char *key)
+{
+ struct index_node_f *root;
+ char *value;
-/* Level 1: interface function */
-struct index_value *index_searchwild(struct index_file *in, const char *key);
+ root = index_readroot(in);
+ value = index_search__node(root, key, 0);
+
+ return value;
+}
-/* Level 2: descend the tree (until we hit a wildcard) */
-static void index_searchwild__node(struct index_node_f *node,
- struct buffer *buf,
- const char *key, int i,
- struct index_value **out);
-/* Level 3: traverse a sub-keyspace which starts with a wildcard,
- looking for matches.
-*/
-static void index_searchwild__all(struct index_node_f *node, int j,
- struct buffer *buf,
- const char *subkey,
- struct index_value **out);
/* Level 4: add all the values from a matching node */
static void index_searchwild__allvalues(struct index_node_f *node,
- struct index_value **out);
+ struct index_value **out)
+{
+ struct index_value *v;
+ for (v = node->values; v != NULL; v = v->next)
+ add_value(out, v->value, v->len, v->priority);
-struct index_value *index_searchwild(struct index_file *in, const char *key)
+ index_close(node);
+}
+
+/*
+ * Level 3: traverse a sub-keyspace which starts with a wildcard,
+ * looking for matches.
+ */
+static void index_searchwild__all(struct index_node_f *node, int j,
+ struct buffer *buf,
+ const char *subkey,
+ struct index_value **out)
{
- struct index_node_f *root = index_readroot(in);
- struct buffer *buf = buf_create();
- struct index_value *out = NULL;
+ int pushed = 0;
+ int ch;
- index_searchwild__node(root, buf, key, 0, &out);
- buf_destroy(buf);
- return out;
+ while (node->prefix[j]) {
+ ch = node->prefix[j];
+
+ buf_pushchar(buf, ch);
+ pushed++;
+ j++;
+ }
+
+ for (ch = node->first; ch <= node->last; ch++) {
+ struct index_node_f *child = index_readchild(node, ch);
+
+ if (!child)
+ continue;
+
+ buf_pushchar(buf, ch);
+ index_searchwild__all(child, 0, buf, subkey, out);
+ buf_popchar(buf);
+ }
+
+ if (node->values) {
+ if (fnmatch(buf_str(buf), subkey, 0) == 0)
+ index_searchwild__allvalues(node, out);
+ else
+ index_close(node);
+ } else {
+ index_close(node);
+ }
+
+ buf_popchars(buf, pushed);
}
+/* Level 2: descend the tree (until we hit a wildcard) */
static void index_searchwild__node(struct index_node_f *node,
struct buffer *buf,
const char *key, int i,
return;
}
}
+
i += j;
child = index_readchild(node, '*');
}
}
-static void index_searchwild__all(struct index_node_f *node, int j,
- struct buffer *buf,
- const char *subkey,
- struct index_value **out)
+/*
+ * Search the index for a key. The index may contain wildcards.
+ *
+ * Returns a list of all the values of matching keys.
+ */
+struct index_value *index_searchwild(struct index_file *in, const char *key)
+{
+ struct index_node_f *root = index_readroot(in);
+ struct buffer buf;
+ struct index_value *out = NULL;
+
+ buf_init(&buf);
+ index_searchwild__node(root, &buf, key, 0, &out);
+ buf_release(&buf);
+ return out;
+}
+
+#include <sys/mman.h>
+#include <sys/stat.h>
+#include <unistd.h>
+
+static const char _idx_empty_str[] = "";
+
+/**************************************************************************/
+/*
+ * Alternative implementation, using mmap to map all the file to memory when
+ * starting
+ */
+struct index_mm {
+ struct kmod_ctx *ctx;
+ void *mm;
+ uint32_t root_offset;
+ size_t size;
+};
+
+struct index_mm_value {
+ unsigned int priority;
+ unsigned int len;
+ const char *value;
+};
+
+struct index_mm_value_array {
+ struct index_mm_value *values;
+ unsigned int len;
+};
+
+struct index_mm_node {
+ struct index_mm *idx;
+ const char *prefix; /* mmape'd value */
+ struct index_mm_value_array values;
+ unsigned char first;
+ unsigned char last;
+ uint32_t children[];
+};
+
+static inline uint32_t read_long_mm(void **p)
+{
+ uint8_t *addr = *(uint8_t **)p;
+ uint32_t v;
+
+ /* addr may be unalined to uint32_t */
+ memcpy(&v, addr, sizeof(uint32_t));
+
+ *p = addr + sizeof(uint32_t);
+ return ntohl(v);
+}
+
+static inline uint8_t read_char_mm(void **p)
+{
+ uint8_t *addr = *(uint8_t **)p;
+ uint8_t v = *addr;
+ *p = addr + sizeof(uint8_t);
+ return v;
+}
+
+static inline char *read_chars_mm(void **p, unsigned *rlen)
+{
+ char *addr = *(char **)p;
+ size_t len = *rlen = strlen(addr);
+ *p = addr + len + 1;
+ return addr;
+}
+
+static struct index_mm_node *index_mm_read_node(struct index_mm *idx,
+ uint32_t offset) {
+ void *p = idx->mm;
+ struct index_mm_node *node;
+ const char *prefix;
+ int i, child_count, value_count, children_padding;
+ uint32_t children[INDEX_CHILDMAX];
+ char first, last;
+
+ if ((offset & INDEX_NODE_MASK) == 0)
+ return NULL;
+
+ p = (char *)p + (offset & INDEX_NODE_MASK);
+
+ if (offset & INDEX_NODE_PREFIX) {
+ unsigned len;
+ prefix = read_chars_mm(&p, &len);
+ } else
+ prefix = _idx_empty_str;
+
+ if (offset & INDEX_NODE_CHILDS) {
+ first = read_char_mm(&p);
+ last = read_char_mm(&p);
+ child_count = last - first + 1;
+ for (i = 0; i < child_count; i++)
+ children[i] = read_long_mm(&p);
+ } else {
+ first = INDEX_CHILDMAX;
+ last = 0;
+ child_count = 0;
+ }
+
+ children_padding = (sizeof(struct index_mm_node) +
+ (sizeof(uint32_t) * child_count)) % sizeof(void *);
+
+ if (offset & INDEX_NODE_VALUES)
+ value_count = read_long_mm(&p);
+ else
+ value_count = 0;
+
+ node = malloc(sizeof(struct index_mm_node)
+ + sizeof(uint32_t) * child_count + children_padding
+ + sizeof(struct index_mm_value) * value_count);
+ if (node == NULL)
+ return NULL;
+
+ node->idx = idx;
+ node->prefix = prefix;
+ if (value_count == 0)
+ node->values.values = NULL;
+ else {
+ node->values.values = (struct index_mm_value *)
+ ((char *)node + sizeof(struct index_mm_node) +
+ sizeof(uint32_t) * child_count + children_padding);
+ }
+ node->values.len = value_count;
+ node->first = first;
+ node->last = last;
+ memcpy(node->children, children, sizeof(uint32_t) * child_count);
+
+ for (i = 0; i < value_count; i++) {
+ struct index_mm_value *v = node->values.values + i;
+ v->priority = read_long_mm(&p);
+ v->value = read_chars_mm(&p, &v->len);
+ }
+
+ return node;
+}
+
+static void index_mm_free_node(struct index_mm_node *node)
+{
+ free(node);
+}
+
+struct index_mm *index_mm_open(struct kmod_ctx *ctx, const char *filename,
+ bool populate, unsigned long long *stamp)
+{
+ int fd;
+ int flags;
+ struct stat st;
+ struct index_mm *idx;
+ struct {
+ uint32_t magic;
+ uint32_t version;
+ uint32_t root_offset;
+ } hdr;
+ void *p;
+
+ DBG(ctx, "file=%s\n", filename);
+
+ idx = malloc(sizeof(*idx));
+ if (idx == NULL) {
+ ERR(ctx, "malloc: %m\n");
+ return NULL;
+ }
+
+ if ((fd = open(filename, O_RDONLY|O_CLOEXEC)) < 0) {
+ ERR(ctx, "open(%s, O_RDONLY|O_CLOEXEC): %m\n", filename);
+ goto fail_open;
+ }
+
+ fstat(fd, &st);
+ flags = MAP_PRIVATE;
+ if (populate)
+ flags |= MAP_POPULATE;
+
+ if ((idx->mm = mmap(0, st.st_size, PROT_READ, flags, fd, 0))
+ == MAP_FAILED) {
+ ERR(ctx, "mmap(0, %zd, PROT_READ, %d, %d, 0): %m\n",
+ (size_t)st.st_size, flags, fd);
+ goto fail;
+ }
+
+ p = idx->mm;
+ hdr.magic = read_long_mm(&p);
+ hdr.version = read_long_mm(&p);
+ hdr.root_offset = read_long_mm(&p);
+
+ if (hdr.magic != INDEX_MAGIC) {
+ ERR(ctx, "magic check fail: %x instead of %x\n", hdr.magic,
+ INDEX_MAGIC);
+ goto fail;
+ }
+
+ if (hdr.version >> 16 != INDEX_VERSION_MAJOR) {
+ ERR(ctx, "major version check fail: %u instead of %u\n",
+ hdr.version, INDEX_MAGIC);
+ goto fail;
+ }
+
+ idx->root_offset = hdr.root_offset;
+ idx->size = st.st_size;
+ idx->ctx = ctx;
+ close(fd);
+
+ *stamp = stat_mstamp(&st);
+
+ return idx;
+
+fail:
+ close(fd);
+ if (idx->mm != MAP_FAILED)
+ munmap(idx->mm, st.st_size);
+fail_open:
+ free(idx);
+ return NULL;
+}
+
+void index_mm_close(struct index_mm *idx)
+{
+ munmap(idx->mm, idx->size);
+ free(idx);
+}
+
+static struct index_mm_node *index_mm_readroot(struct index_mm *idx)
+{
+ return index_mm_read_node(idx, idx->root_offset);
+}
+
+static struct index_mm_node *index_mm_readchild(const struct index_mm_node *parent,
+ int ch)
+{
+ if (parent->first <= ch && ch <= parent->last) {
+ return index_mm_read_node(parent->idx,
+ parent->children[ch - parent->first]);
+ }
+
+ return NULL;
+}
+
+static void index_mm_dump_node(struct index_mm_node *node, struct buffer *buf,
+ int fd)
+{
+ struct index_mm_value *itr, *itr_end;
+ int ch, pushed;
+
+ pushed = buf_pushchars(buf, node->prefix);
+
+ itr = node->values.values;
+ itr_end = itr + node->values.len;
+ for (; itr < itr_end; itr++) {
+ write_str_safe(fd, buf->bytes, buf->used);
+ write_str_safe(fd, " ", 1);
+ write_str_safe(fd, itr->value, itr->len);
+ write_str_safe(fd, "\n", 1);
+ }
+
+ for (ch = node->first; ch <= node->last; ch++) {
+ struct index_mm_node *child = index_mm_readchild(node, ch);
+
+ if (child == NULL)
+ continue;
+
+ buf_pushchar(buf, ch);
+ index_mm_dump_node(child, buf, fd);
+ buf_popchar(buf);
+ }
+
+ buf_popchars(buf, pushed);
+ index_mm_free_node(node);
+}
+
+void index_mm_dump(struct index_mm *idx, int fd, const char *prefix)
+{
+ struct index_mm_node *root;
+ struct buffer buf;
+
+ buf_init(&buf);
+ buf_pushchars(&buf, prefix);
+ root = index_mm_readroot(idx);
+ index_mm_dump_node(root, &buf, fd);
+ buf_release(&buf);
+}
+
+static char *index_mm_search_node(struct index_mm_node *node, const char *key,
+ int i)
+{
+ char *value;
+ struct index_mm_node *child;
+ int ch;
+ int j;
+
+ while(node) {
+ for (j = 0; node->prefix[j]; j++) {
+ ch = node->prefix[j];
+
+ if (ch != key[i+j]) {
+ index_mm_free_node(node);
+ return NULL;
+ }
+ }
+
+ i += j;
+
+ if (key[i] == '\0') {
+ if (node->values.len > 0) {
+ value = strdup(node->values.values[0].value);
+ index_mm_free_node(node);
+ return value;
+ } else {
+ return NULL;
+ }
+ }
+
+ child = index_mm_readchild(node, key[i]);
+ index_mm_free_node(node);
+ node = child;
+ i++;
+ }
+
+ return NULL;
+}
+
+/*
+ * Search the index for a key
+ *
+ * Returns the value of the first match
+ *
+ * The recursive functions free their node argument (using index_close).
+ */
+char *index_mm_search(struct index_mm *idx, const char *key)
+{
+ struct index_mm_node *root;
+ char *value;
+
+ root = index_mm_readroot(idx);
+ value = index_mm_search_node(root, key, 0);
+
+ return value;
+}
+
+/* Level 4: add all the values from a matching node */
+static void index_mm_searchwild_allvalues(struct index_mm_node *node,
+ struct index_value **out)
+{
+ struct index_mm_value *itr, *itr_end;
+
+ itr = node->values.values;
+ itr_end = itr + node->values.len;
+ for (; itr < itr_end; itr++)
+ add_value(out, itr->value, itr->len, itr->priority);
+
+ index_mm_free_node(node);
+}
+
+/*
+ * Level 3: traverse a sub-keyspace which starts with a wildcard,
+ * looking for matches.
+ */
+static void index_mm_searchwild_all(struct index_mm_node *node, int j,
+ struct buffer *buf,
+ const char *subkey,
+ struct index_value **out)
{
int pushed = 0;
int ch;
}
for (ch = node->first; ch <= node->last; ch++) {
- struct index_node_f *child = index_readchild(node, ch);
+ struct index_mm_node *child = index_mm_readchild(node, ch);
if (!child)
continue;
buf_pushchar(buf, ch);
- index_searchwild__all(child, 0, buf, subkey, out);
+ index_mm_searchwild_all(child, 0, buf, subkey, out);
buf_popchar(buf);
}
- if (node->values) {
+ if (node->values.len > 0) {
if (fnmatch(buf_str(buf), subkey, 0) == 0)
- index_searchwild__allvalues(node, out);
+ index_mm_searchwild_allvalues(node, out);
+ else
+ index_mm_free_node(node);
} else {
- index_close(node);
+ index_mm_free_node(node);
}
buf_popchars(buf, pushed);
}
-static void index_searchwild__allvalues(struct index_node_f *node,
- struct index_value **out)
+/* Level 2: descend the tree (until we hit a wildcard) */
+static void index_mm_searchwild_node(struct index_mm_node *node,
+ struct buffer *buf,
+ const char *key, int i,
+ struct index_value **out)
{
- struct index_value *v;
+ struct index_mm_node *child;
+ int j;
+ int ch;
- for (v = node->values; v != NULL; v = v->next)
- add_value(out, v->value, v->priority);
+ while(node) {
+ for (j = 0; node->prefix[j]; j++) {
+ ch = node->prefix[j];
- index_close(node);
+ if (ch == '*' || ch == '?' || ch == '[') {
+ index_mm_searchwild_all(node, j, buf,
+ &key[i+j], out);
+ return;
+ }
+
+ if (ch != key[i+j]) {
+ index_mm_free_node(node);
+ return;
+ }
+ }
+
+ i += j;
+
+ child = index_mm_readchild(node, '*');
+ if (child) {
+ buf_pushchar(buf, '*');
+ index_mm_searchwild_all(child, 0, buf, &key[i], out);
+ buf_popchar(buf);
+ }
+
+ child = index_mm_readchild(node, '?');
+ if (child) {
+ buf_pushchar(buf, '?');
+ index_mm_searchwild_all(child, 0, buf, &key[i], out);
+ buf_popchar(buf);
+ }
+
+ child = index_mm_readchild(node, '[');
+ if (child) {
+ buf_pushchar(buf, '[');
+ index_mm_searchwild_all(child, 0, buf, &key[i], out);
+ buf_popchar(buf);
+ }
+
+ if (key[i] == '\0') {
+ index_mm_searchwild_allvalues(node, out);
+
+ return;
+ }
+
+ child = index_mm_readchild(node, key[i]);
+ index_mm_free_node(node);
+ node = child;
+ i++;
+ }
+}
+
+/*
+ * Search the index for a key. The index may contain wildcards.
+ *
+ * Returns a list of all the values of matching keys.
+ */
+struct index_value *index_mm_searchwild(struct index_mm *idx, const char *key)
+{
+ struct index_mm_node *root = index_mm_readroot(idx);
+ struct buffer buf;
+ struct index_value *out = NULL;
+
+ buf_init(&buf);
+ index_mm_searchwild_node(root, &buf, key, 0, &out);
+ buf_release(&buf);
+ return out;
}
projects / thirdparty / kmod.git / blobdiff