libkmod/libkmod-index.c

/*
 * libkmod - interface to kernel module operations
 *
 * Copyright (C) 2011  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 <stdio.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.c: module index file shared functions for modprobe and depmod */

#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).
 */

/* 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 */
};

void index_values_free(struct index_value *values)
{
	while (values) {
		struct index_value *value = values;

		values = value->next;
		free(value);
	}
}

static int add_value(struct index_value **values,
		     const char *value, unsigned len, unsigned int priority)
{
	struct index_value *v;

	/* find position to insert value */
	while (*values && (*values)->priority < priority)
		values = &(*values)->next;

	v = malloc(sizeof(struct index_value) + len + 1);
	if (!v)
		return -1;
	v->next = *values;
	v->priority = priority;
	v->len = len;
	memcpy(v->value, value, len);
	v->value[len] = '\0';
	*values = v;

	return 0;
}

static void read_error(void)
{
	fatal("Module index: unexpected error: %s\n"
			"Try re-running depmod\n", errno ? strerror(errno) : "EOF");
}

static int read_char(FILE *in)
{
	int ch;

	errno = 0;
	ch = getc_unlocked(in);
	if (ch == EOF)
		read_error();
	return ch;
}

static uint32_t read_long(FILE *in)
{
	uint32_t l;

	errno = 0;
	if (fread(&l, sizeof(uint32_t), 1, in) <= 0)
		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)
{
	unsigned i = 0;
	int ch;

	while ((ch = read_char(in))) {
		if (!buf_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
 */
struct index_node_f {
	FILE *file;
	char *prefix;		/* path compression */
	struct index_value *values;
	unsigned char first;	/* range of child nodes */
	unsigned char last;
	uint32_t children[0];
};

static struct index_node_f *index_read(FILE *in, uint32_t offset)
{
	struct index_node_f *node;
	char *prefix;
	int i, child_count = 0;

	if ((offset & INDEX_NODE_MASK) == 0)
		return NULL;

	fseek(in, offset & INDEX_NODE_MASK, SEEK_SET);

	if (offset & INDEX_NODE_PREFIX) {
		struct buffer buf;
		buf_init(&buf);
		buf_freadchars(&buf, in);
		prefix = buf_steal(&buf);
	} else
		prefix = NOFAIL(strdup(""));

	if (offset & INDEX_NODE_CHILDS) {
		char first = read_char(in);
		char last = read_char(in);
		child_count = last - first + 1;

		node = NOFAIL(malloc(sizeof(struct index_node_f) +
				     sizeof(uint32_t) * child_count));

		node->first = first;
		node->last = last;

		for (i = 0; i < child_count; i++)
			node->children[i] = read_long(in);
	} else {
		node = NOFAIL(malloc(sizeof(struct index_node_f)));
		node->first = INDEX_CHILDMAX;
		node->last = 0;
	}

	node->values = NULL;
	if (offset & INDEX_NODE_VALUES) {
		int value_count;
		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, buf.used, priority);
			buf_clear(&buf);
		}
		buf_release(&buf);
	}

	node->prefix = prefix;
	node->file = in;
	return node;
}

static void index_close(struct index_node_f *node)
{
	free(node->prefix);
	index_values_free(node->values);
	free(node);
}

struct index_file {
	FILE *file;
	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, "re");
	if (!file)
		return NULL;
	errno = EINVAL;

	magic = read_long(file);
	if (magic != INDEX_MAGIC) {
		fclose(file);
		return NULL;
	}

	version = read_long(file);
	if (version >> 16 != INDEX_VERSION_MAJOR) {
		fclose(file);
		return NULL;
	}

	new = NOFAIL(malloc(sizeof(struct index_file)));
	new->file = file;
	new->root_offset = read_long(new->file);

	errno = 0;
	return new;
}

void index_file_close(struct index_file *idx)
{
	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) {
		return index_read(parent->file,
		                       parent->children[ch - parent->first]);
	}

	return NULL;
}

static char *index_search__node(struct index_node_f *node, const char *key, int i)
{
	char *value;
	struct index_node_f *child;
	int ch;
	int j;

	while(node) {
		for (j = 0; node->prefix[j]; j++) {
			ch = node->prefix[j];

			if (ch != key[i+j]) {
				index_close(node);
				return NULL;
			}
		}

		i += j;

		if (key[i] == '\0') {
			if (node->values) {
				value = strdup(node->values[0].value);
				index_close(node);
				return value;
			} else {
				return NULL;
			}
		}

		child = index_readchild(node, key[i]);
		index_close(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_search(struct index_file *in, const char *key)
{
	struct index_node_f *root;
	char *value;

	root = index_readroot(in);
	value = index_search__node(root, key, 0);

	return value;
}



/* 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 *v;

	for (v = node->values; v != NULL; v = v->next)
		add_value(out, v->value, v->len, v->priority);

	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)
{
	int pushed = 0;
	int ch;

	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,
				   struct index_value **out)
{
	struct index_node_f *child;
	int j;
	int ch;

	while(node) {
		for (j = 0; node->prefix[j]; j++) {
			ch = node->prefix[j];

			if (ch == '*' || ch == '?' || ch == '[') {
				index_searchwild__all(node, j, buf,
						      &key[i+j], out);
				return;
			}

			if (ch != key[i+j]) {
				index_close(node);
				return;
			}
		}

		i += j;

		child = index_readchild(node, '*');
		if (child) {
			buf_pushchar(buf, '*');
			index_searchwild__all(child, 0, buf, &key[i], out);
			buf_popchar(buf);
		}

		child = index_readchild(node, '?');
		if (child) {
			buf_pushchar(buf, '?');
			index_searchwild__all(child, 0, buf, &key[i], out);
			buf_popchar(buf);
		}

		child = index_readchild(node, '[');
		if (child) {
			buf_pushchar(buf, '[');
			index_searchwild__all(child, 0, buf, &key[i], out);
			buf_popchar(buf);
		}

		if (key[i] == '\0') {
			index_searchwild__allvalues(node, out);

			return;
		}

		child = index_readchild(node, key[i]);
		index_close(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_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)
{
	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, "%m\n");
		return NULL;
	}

	if ((fd = open(filename, O_RDONLY|O_CLOEXEC)) < 0) {
		ERR(ctx, "%m\n");
		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, "%m\n");
		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);

	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 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;

	while (node->prefix[j]) {
		ch = node->prefix[j];

		buf_pushchar(buf, ch);
		pushed++;
		j++;
	}

	for (ch = node->first; ch <= node->last; ch++) {
		struct index_mm_node *child = index_mm_readchild(node, ch);

		if (!child)
			continue;

		buf_pushchar(buf, ch);
		index_mm_searchwild_all(child, 0, buf, subkey, out);
		buf_popchar(buf);
	}

	if (node->values.len > 0) {
		if (fnmatch(buf_str(buf), subkey, 0) == 0)
			index_mm_searchwild_allvalues(node, out);
		else
			index_mm_free_node(node);
	} else {
		index_mm_free_node(node);
	}

	buf_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,
					   const char *key, int i,
					   struct index_value **out)
{
	struct index_mm_node *child;
	int j;
	int ch;

	while(node) {
		for (j = 0; node->prefix[j]; j++) {
			ch = node->prefix[j];

			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;
}