/*
* libkmod - interface to kernel module operations
*
- * Copyright (C) 2008 Alan Jenkins <alan.christopher.jenkins@googlemail.com>
- * Copyright (C) 2011 ProFUSION embedded systems
+ * Copyright (C) 2011-2013 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 version 2.1.
+ * 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
* 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
+ * License along with this library; if not, see <http://www.gnu.org/licenses/>.
*/
-#include <arpa/inet.h> /* htonl */
-#include <stdlib.h>
-#include <stdio.h>
-#include <string.h>
+#include <arpa/inet.h>
+#include <assert.h>
#include <errno.h>
#include <fnmatch.h>
-#include <assert.h>
+#include <inttypes.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <shared/macro.h>
+#include <shared/strbuf.h>
+#include <shared/util.h>
-#include "libkmod-private.h"
+#include "libkmod-internal.h"
#include "libkmod-index.h"
-#include "macro.h"
-/* index.c: module index file shared functions for modprobe and depmod */
+/* libkmod-index.c: module index file implementation
+ *
+ * Integers are stored as 32 bit unsigned in "network" order, i.e. MSB first.
+ * All files start with a magic number.
+ *
+ * Magic spells "BOOTFAST". Second one used on newer versioned binary files.
+ * #define INDEX_MAGIC_OLD 0xB007FA57
+ *
+ * We use a version string to keep track of changes to the binary format
+ * This is stored in the form: INDEX_MAJOR (hi) INDEX_MINOR (lo) just in
+ * case we ever decide to have minor changes that are not incompatible.
+ */
+#define INDEX_MAGIC 0xB007F457
+#define INDEX_VERSION_MAJOR 0x0002
+#define INDEX_VERSION_MINOR 0x0001
+#define INDEX_VERSION ((INDEX_VERSION_MAJOR<<16)|INDEX_VERSION_MINOR)
+/* The index file maps keys to values. Both keys and values are ASCII strings.
+ * Each key can have multiple values. Values are sorted by an integer priority.
+ *
+ * The reader also implements a wildcard search (including range expressions)
+ * where the keys in the index are treated as patterns.
+ * This feature is required for module aliases.
+ */
#define INDEX_CHILDMAX 128
/* Disk format:
-
- uint32_t magic = INDEX_MAGIC;
- uint32_t version = INDEX_VERSION;
- uint32_t root_offset;
-
- (node_offset & INDEX_NODE_MASK) specifies the file offset of nodes:
-
- char[] prefix; // nul terminated
-
- char first;
- char last;
- uint32_t children[last - first + 1];
-
- uint32_t value_count;
- struct {
- uint32_t priority;
- char[] value; // nul terminated
- } values[value_count];
-
- (node_offset & INDEX_NODE_FLAGS) indicates which fields are present.
- Empty prefixes are omitted, leaf nodes omit the three child-related fields.
-
- This could be optimised further by adding a sparse child format
- (indicated using a new flag).
+ *
+ * uint32_t magic = INDEX_MAGIC;
+ * uint32_t version = INDEX_VERSION;
+ * uint32_t root_offset;
+ *
+ * (node_offset & INDEX_NODE_MASK) specifies the file offset of nodes:
+ *
+ * char[] prefix; // nul terminated
+ *
+ * char first;
+ * char last;
+ * uint32_t children[last - first + 1];
+ *
+ * uint32_t value_count;
+ * struct {
+ * uint32_t priority;
+ * char[] value; // nul terminated
+ * } values[value_count];
+ *
+ * (node_offset & INDEX_NODE_FLAGS) indicates which fields are present.
+ * Empty prefixes are omitted, leaf nodes omit the three child-related fields.
+ *
+ * This could be optimised further by adding a sparse child format
+ * (indicated using a new flag).
+ *
+ *
+ * Implementation is based on a radix tree, or "trie".
+ * Each arc from parent to child is labelled with a character.
+ * Each path from the root represents a string.
+ *
+ * == Example strings ==
+ *
+ * ask
+ * ate
+ * on
+ * once
+ * one
+ *
+ * == Key ==
+ * + Normal node
+ * * Marked node, representing a key and it's values.
+ *
+ * +
+ * |-a-+-s-+-k-*
+ * | |
+ * | `-t-+-e-*
+ * |
+ * `-o-+-n-*-c-+-e-*
+ * |
+ * `-e-*
+ *
+ * Naive implementations tend to be very space inefficient; child pointers
+ * are stored in arrays indexed by character, but most child pointers are null.
+ *
+ * Our implementation uses a scheme described by Wikipedia as a Patrica trie,
+ *
+ * "easiest to understand as a space-optimized trie where
+ * each node with only one child is merged with its child"
+ *
+ * +
+ * |-a-+-sk-*
+ * | |
+ * | `-te-*
+ * |
+ * `-on-*-ce-*
+ * |
+ * `-e-*
+ *
+ * We still use arrays of child pointers indexed by a single character;
+ * the remaining characters of the label are stored as a "prefix" in the child.
+ *
+ * The paper describing the original Patrica trie works on individiual bits -
+ * each node has a maximum of two children, which increases space efficiency.
+ * However for this application it is simpler to use the ASCII character set.
+ * Since the index file is read-only, it can be compressed by omitting null
+ * child pointers at the start and end of arrays.
*/
/* Format of node offsets within index file */
uint32_t l;
errno = 0;
- if (fread(&l, sizeof(uint32_t), 1, in) <= 0)
+ if (fread(&l, sizeof(uint32_t), 1, in) != sizeof(uint32_t))
read_error();
return ntohl(l);
}
-/*
- * Buffer abstract data type
- *
- * Used internally to store the current path during tree traversal.
- * 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;
-};
-
-#define BUF_STEP (2048)
-static bool buf_grow(struct buffer *buf, size_t newsize)
-{
- 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 void buf_init(struct buffer *buf)
-{
- buf->bytes = NULL;
- buf->size = 0;
- buf->used = 0;
-}
-
-static void buf_release(struct buffer *buf)
-{
- free(buf->bytes);
-}
-
-/* Destroy buffer and return a copy as a C string */
-static char *buf_steal(struct buffer *buf)
-{
- char *bytes;
-
- bytes = realloc(buf->bytes, buf->used + 1);
- if (!bytes) {
- free(buf->bytes);
- return NULL;
- }
- bytes[buf->used] = '\0';
- return bytes;
-}
-
-/* Return a C string owned by the buffer
- (invalidated if the buffer is changed).
- */
-static const char *buf_str(struct buffer *buf)
-{
- if (!buf_grow(buf, buf->used + 1))
- return NULL;
- buf->bytes[buf->used] = '\0';
- return buf->bytes;
-}
-
-static bool buf_pushchar(struct buffer *buf, char ch)
-{
- if (!buf_grow(buf, buf->used + 1))
- return false;
- buf->bytes[buf->used] = ch;
- buf->used++;
- return true;
-}
-
-static unsigned buf_freadchars(struct buffer *buf, FILE *in)
+static unsigned buf_freadchars(struct strbuf *buf, FILE *in)
{
unsigned i = 0;
int ch;
while ((ch = read_char(in))) {
- if (!buf_pushchar(buf, ch))
+ if (!strbuf_pushchar(buf, ch))
break;
i++;
}
return 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;
-}
-
-static void buf_clear(struct buffer *buf)
-{
- buf->used = 0;
-}
-
/*
* Index file searching
*/
if ((offset & INDEX_NODE_MASK) == 0)
return NULL;
- fseek(in, offset & INDEX_NODE_MASK, SEEK_SET);
+ if (fseek(in, offset & INDEX_NODE_MASK, SEEK_SET) < 0)
+ return NULL;
if (offset & INDEX_NODE_PREFIX) {
- struct buffer buf;
- buf_init(&buf);
+ struct strbuf buf;
+ strbuf_init(&buf);
buf_freadchars(&buf, in);
- prefix = buf_steal(&buf);
+ prefix = strbuf_steal(&buf);
} else
prefix = NOFAIL(strdup(""));
node->values = NULL;
if (offset & INDEX_NODE_VALUES) {
int value_count;
- struct buffer buf;
+ struct strbuf buf;
const char *value;
unsigned int priority;
value_count = read_long(in);
- buf_init(&buf);
+ strbuf_init(&buf);
while (value_count--) {
priority = read_long(in);
buf_freadchars(&buf, in);
- value = buf_str(&buf);
+ value = strbuf_str(&buf);
add_value(&node->values, value, buf.used, priority);
- buf_clear(&buf);
+ strbuf_clear(&buf);
}
- buf_release(&buf);
+ strbuf_release(&buf);
}
node->prefix = prefix;
uint32_t root_offset;
};
-/* Failures are silent; modprobe will fall back to text files */
struct index_file *index_file_open(const char *filename)
{
FILE *file;
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 NULL;
}
+static void index_dump_node(struct index_node_f *node, struct strbuf *buf,
+ int fd)
+{
+ struct index_value *v;
+ int ch, pushed;
+
+ pushed = strbuf_pushchars(buf, node->prefix);
+
+ for (v = node->values; v != NULL; v = v->next) {
+ 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++) {
+ struct index_node_f *child = index_readchild(node, ch);
+
+ if (!child)
+ continue;
+
+ strbuf_pushchar(buf, ch);
+ index_dump_node(child, buf, fd);
+ strbuf_popchar(buf);
+ }
+
+ strbuf_popchars(buf, pushed);
+ index_close(node);
+}
+
+void index_dump(struct index_file *in, int fd, const char *prefix)
+{
+ struct index_node_f *root;
+ struct strbuf buf;
+
+ root = index_readroot(in);
+ if (root == NULL)
+ return;
+
+ strbuf_init(&buf);
+ strbuf_pushchars(&buf, prefix);
+ index_dump_node(root, &buf, fd);
+ strbuf_release(&buf);
+}
+
static char *index_search__node(struct index_node_f *node, const char *key, int i)
{
char *value;
i += j;
if (key[i] == '\0') {
- if (node->values) {
- value = strdup(node->values[0].value);
- index_close(node);
- return value;
- } else {
- return NULL;
- }
+ value = node->values != NULL
+ ? strdup(node->values[0].value)
+ : NULL;
+
+ index_close(node);
+ return value;
}
child = index_readchild(node, key[i]);
*/
char *index_search(struct index_file *in, const char *key)
{
+// FIXME: return value by reference instead of strdup
struct index_node_f *root;
char *value;
* looking for matches.
*/
static void index_searchwild__all(struct index_node_f *node, int j,
- struct buffer *buf,
+ struct strbuf *buf,
const char *subkey,
struct index_value **out)
{
while (node->prefix[j]) {
ch = node->prefix[j];
- buf_pushchar(buf, ch);
+ strbuf_pushchar(buf, ch);
pushed++;
j++;
}
if (!child)
continue;
- buf_pushchar(buf, ch);
+ strbuf_pushchar(buf, ch);
index_searchwild__all(child, 0, buf, subkey, out);
- buf_popchar(buf);
+ strbuf_popchar(buf);
}
if (node->values) {
- if (fnmatch(buf_str(buf), subkey, 0) == 0)
+ if (fnmatch(strbuf_str(buf), subkey, 0) == 0)
index_searchwild__allvalues(node, out);
else
index_close(node);
index_close(node);
}
- buf_popchars(buf, pushed);
+ strbuf_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,
+ struct strbuf *buf,
const char *key, int i,
struct index_value **out)
{
child = index_readchild(node, '*');
if (child) {
- buf_pushchar(buf, '*');
+ strbuf_pushchar(buf, '*');
index_searchwild__all(child, 0, buf, &key[i], out);
- buf_popchar(buf);
+ strbuf_popchar(buf);
}
child = index_readchild(node, '?');
if (child) {
- buf_pushchar(buf, '?');
+ strbuf_pushchar(buf, '?');
index_searchwild__all(child, 0, buf, &key[i], out);
- buf_popchar(buf);
+ strbuf_popchar(buf);
}
child = index_readchild(node, '[');
if (child) {
- buf_pushchar(buf, '[');
+ strbuf_pushchar(buf, '[');
index_searchwild__all(child, 0, buf, &key[i], out);
- buf_popchar(buf);
+ strbuf_popchar(buf);
}
if (key[i] == '\0') {
struct index_value *index_searchwild(struct index_file *in, const char *key)
{
struct index_node_f *root = index_readroot(in);
- struct buffer buf;
+ struct strbuf buf;
struct index_value *out = NULL;
- buf_init(&buf);
+ strbuf_init(&buf);
index_searchwild__node(root, &buf, key, 0, &out);
- buf_release(&buf);
+ strbuf_release(&buf);
return out;
}
+/**************************************************************************/
+/*
+ * Alternative implementation, using mmap to map all the file to memory when
+ * starting
+ */
#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 v;
/* addr may be unalined to uint32_t */
- memcpy(&v, addr, sizeof(uint32_t));
+ v = get_unaligned((uint32_t *) addr);
*p = addr + sizeof(uint32_t);
return ntohl(v);
child_count = 0;
}
- children_padding = (offsetof(struct index_mm_node, children) +
+ children_padding = (sizeof(struct index_mm_node) +
(sizeof(uint32_t) * child_count)) % sizeof(void *);
if (offset & INDEX_NODE_VALUES)
}
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 {
DBG(ctx, "file=%s\n", filename);
- if ((fd = open(filename, O_RDONLY)) < 0) {
- ERR(ctx, "%m\n");
+ idx = malloc(sizeof(*idx));
+ if (idx == NULL) {
+ ERR(ctx, "malloc: %m\n");
return NULL;
}
- fstat(fd, &st);
-
- idx = malloc(sizeof(*idx));
- if (idx == NULL) {
- ERR(ctx, "%m\n");
- goto fail;
+ if ((fd = open(filename, O_RDONLY|O_CLOEXEC)) < 0) {
+ DBG(ctx, "open(%s, O_RDONLY|O_CLOEXEC): %m\n", filename);
+ goto fail_open;
}
- flags = MAP_PRIVATE;
- if (populate)
- flags |= MAP_POPULATE;
+ if (fstat(fd, &st) < 0)
+ goto fail_nommap;
+ if ((size_t) st.st_size < sizeof(hdr))
+ goto fail_nommap;
- if ((idx->mm = mmap(0, st.st_size, PROT_READ, flags, fd, 0))
+ if ((idx->mm = mmap(NULL, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0))
== MAP_FAILED) {
- ERR(ctx, "%m\n");
- goto fail;
+ ERR(ctx, "mmap(NULL, %"PRIu64", PROT_READ, %d, MAP_PRIVATE, 0): %m\n",
+ st.st_size, fd);
+ goto fail_nommap;
}
p = idx->mm;
if (hdr.version >> 16 != INDEX_VERSION_MAJOR) {
ERR(ctx, "major version check fail: %u instead of %u\n",
- hdr.version, INDEX_MAGIC);
+ hdr.version >> 16, INDEX_VERSION_MAJOR);
goto fail;
}
idx->ctx = ctx;
close(fd);
+ *stamp = stat_mstamp(&st);
+
return idx;
fail:
+ munmap(idx->mm, st.st_size);
+fail_nommap:
close(fd);
- if (idx->mm)
- munmap(idx->mm, st.st_size);
+fail_open:
free(idx);
return NULL;
}
return NULL;
}
+static void index_mm_dump_node(struct index_mm_node *node, struct strbuf *buf,
+ int fd)
+{
+ struct index_mm_value *itr, *itr_end;
+ int ch, pushed;
+
+ pushed = strbuf_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;
+
+ strbuf_pushchar(buf, ch);
+ index_mm_dump_node(child, buf, fd);
+ strbuf_popchar(buf);
+ }
+
+ strbuf_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 strbuf buf;
+
+ root = index_mm_readroot(idx);
+ if (root == NULL)
+ return;
+
+ strbuf_init(&buf);
+ strbuf_pushchars(&buf, prefix);
+ index_mm_dump_node(root, &buf, fd);
+ strbuf_release(&buf);
+}
+
static char *index_mm_search_node(struct index_mm_node *node, const char *key,
int i)
{
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;
- }
+ value = node->values.len > 0
+ ? strdup(node->values.values[0].value)
+ : NULL;
+
+ index_mm_free_node(node);
+ return value;
}
child = index_mm_readchild(node, key[i]);
*/
char *index_mm_search(struct index_mm *idx, const char *key)
{
+// FIXME: return value by reference instead of strdup
struct index_mm_node *root;
char *value;
* looking for matches.
*/
static void index_mm_searchwild_all(struct index_mm_node *node, int j,
- struct buffer *buf,
+ struct strbuf *buf,
const char *subkey,
struct index_value **out)
{
while (node->prefix[j]) {
ch = node->prefix[j];
- buf_pushchar(buf, ch);
+ strbuf_pushchar(buf, ch);
pushed++;
j++;
}
if (!child)
continue;
- buf_pushchar(buf, ch);
+ strbuf_pushchar(buf, ch);
index_mm_searchwild_all(child, 0, buf, subkey, out);
- buf_popchar(buf);
+ strbuf_popchar(buf);
}
if (node->values.len > 0) {
- if (fnmatch(buf_str(buf), subkey, 0) == 0)
+ if (fnmatch(strbuf_str(buf), subkey, 0) == 0)
index_mm_searchwild_allvalues(node, out);
else
index_mm_free_node(node);
index_mm_free_node(node);
}
- buf_popchars(buf, pushed);
+ strbuf_popchars(buf, pushed);
}
/* Level 2: descend the tree (until we hit a wildcard) */
static void index_mm_searchwild_node(struct index_mm_node *node,
- struct buffer *buf,
+ struct strbuf *buf,
const char *key, int i,
struct index_value **out)
{
child = index_mm_readchild(node, '*');
if (child) {
- buf_pushchar(buf, '*');
+ strbuf_pushchar(buf, '*');
index_mm_searchwild_all(child, 0, buf, &key[i], out);
- buf_popchar(buf);
+ strbuf_popchar(buf);
}
child = index_mm_readchild(node, '?');
if (child) {
- buf_pushchar(buf, '?');
+ strbuf_pushchar(buf, '?');
index_mm_searchwild_all(child, 0, buf, &key[i], out);
- buf_popchar(buf);
+ strbuf_popchar(buf);
}
child = index_mm_readchild(node, '[');
if (child) {
- buf_pushchar(buf, '[');
+ strbuf_pushchar(buf, '[');
index_mm_searchwild_all(child, 0, buf, &key[i], out);
- buf_popchar(buf);
+ strbuf_popchar(buf);
}
if (key[i] == '\0') {
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 strbuf buf;
struct index_value *out = NULL;
- buf_init(&buf);
+ strbuf_init(&buf);
index_mm_searchwild_node(root, &buf, key, 0, &out);
- buf_release(&buf);
+ strbuf_release(&buf);
return out;
}
projects / thirdparty / kmod.git / blobdiff