mirror of
https://github.com/AuxXxilium/kmod.git
synced 2024-11-23 15:00:52 +07:00
d4f659e12a
Some are outdated, misleading or just repeat the same thing over and over. Remove them as they are not needed. Reviewed-by: Emil Velikov <emil.l.velikov@gmail.com> Link: https://lore.kernel.org/r/20240723185921.1005569-3-lucas.de.marchi@gmail.com Signed-off-by: Lucas De Marchi <lucas.de.marchi@gmail.com>
1069 lines
22 KiB
C
1069 lines
22 KiB
C
// SPDX-License-Identifier: LGPL-2.1-or-later
|
|
/*
|
|
* Copyright (C) 2011-2013 ProFUSION embedded systems
|
|
*/
|
|
|
|
#include <arpa/inet.h>
|
|
#include <assert.h>
|
|
#include <errno.h>
|
|
#include <fnmatch.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-internal.h"
|
|
#include "libkmod-index.h"
|
|
|
|
/* 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).
|
|
*
|
|
*
|
|
* 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 */
|
|
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) != sizeof(uint32_t))
|
|
read_error();
|
|
return ntohl(l);
|
|
}
|
|
|
|
static unsigned buf_freadchars(struct strbuf *buf, FILE *in)
|
|
{
|
|
unsigned i = 0;
|
|
int ch;
|
|
|
|
while ((ch = read_char(in))) {
|
|
if (!strbuf_pushchar(buf, ch))
|
|
break;
|
|
i++;
|
|
}
|
|
|
|
return i;
|
|
}
|
|
|
|
/*
|
|
* 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;
|
|
|
|
if (fseek(in, offset & INDEX_NODE_MASK, SEEK_SET) < 0)
|
|
return NULL;
|
|
|
|
if (offset & INDEX_NODE_PREFIX) {
|
|
struct strbuf buf;
|
|
strbuf_init(&buf);
|
|
buf_freadchars(&buf, in);
|
|
prefix = strbuf_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 strbuf buf;
|
|
const char *value;
|
|
unsigned int priority;
|
|
|
|
value_count = read_long(in);
|
|
|
|
strbuf_init(&buf);
|
|
while (value_count--) {
|
|
priority = read_long(in);
|
|
buf_freadchars(&buf, in);
|
|
value = strbuf_str(&buf);
|
|
add_value(&node->values, value, buf.used, priority);
|
|
strbuf_clear(&buf);
|
|
}
|
|
strbuf_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;
|
|
};
|
|
|
|
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 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;
|
|
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') {
|
|
value = node->values != NULL
|
|
? strdup(node->values[0].value)
|
|
: NULL;
|
|
|
|
index_close(node);
|
|
return value;
|
|
}
|
|
|
|
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)
|
|
{
|
|
// FIXME: return value by reference instead of strdup
|
|
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 strbuf *buf,
|
|
const char *subkey,
|
|
struct index_value **out)
|
|
{
|
|
int pushed = 0;
|
|
int ch;
|
|
|
|
while (node->prefix[j]) {
|
|
ch = node->prefix[j];
|
|
|
|
strbuf_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;
|
|
|
|
strbuf_pushchar(buf, ch);
|
|
index_searchwild__all(child, 0, buf, subkey, out);
|
|
strbuf_popchar(buf);
|
|
}
|
|
|
|
if (node->values) {
|
|
if (fnmatch(strbuf_str(buf), subkey, 0) == 0)
|
|
index_searchwild__allvalues(node, out);
|
|
else
|
|
index_close(node);
|
|
} else {
|
|
index_close(node);
|
|
}
|
|
|
|
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 strbuf *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) {
|
|
strbuf_pushchar(buf, '*');
|
|
index_searchwild__all(child, 0, buf, &key[i], out);
|
|
strbuf_popchar(buf);
|
|
}
|
|
|
|
child = index_readchild(node, '?');
|
|
if (child) {
|
|
strbuf_pushchar(buf, '?');
|
|
index_searchwild__all(child, 0, buf, &key[i], out);
|
|
strbuf_popchar(buf);
|
|
}
|
|
|
|
child = index_readchild(node, '[');
|
|
if (child) {
|
|
strbuf_pushchar(buf, '[');
|
|
index_searchwild__all(child, 0, buf, &key[i], out);
|
|
strbuf_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 strbuf buf;
|
|
struct index_value *out = NULL;
|
|
|
|
strbuf_init(&buf);
|
|
index_searchwild__node(root, &buf, key, 0, &out);
|
|
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[] = "";
|
|
|
|
struct index_mm {
|
|
const 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 */
|
|
v = get_unaligned((uint32_t *) addr);
|
|
|
|
*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);
|
|
}
|
|
|
|
int index_mm_open(const struct kmod_ctx *ctx, const char *filename,
|
|
unsigned long long *stamp, struct index_mm **pidx)
|
|
{
|
|
int fd, err;
|
|
struct stat st;
|
|
struct index_mm *idx;
|
|
struct {
|
|
uint32_t magic;
|
|
uint32_t version;
|
|
uint32_t root_offset;
|
|
} hdr;
|
|
void *p;
|
|
|
|
assert(pidx != NULL);
|
|
|
|
DBG(ctx, "file=%s\n", filename);
|
|
|
|
idx = malloc(sizeof(*idx));
|
|
if (idx == NULL) {
|
|
ERR(ctx, "malloc: %m\n");
|
|
return -ENOMEM;
|
|
}
|
|
|
|
if ((fd = open(filename, O_RDONLY|O_CLOEXEC)) < 0) {
|
|
DBG(ctx, "open(%s, O_RDONLY|O_CLOEXEC): %m\n", filename);
|
|
err = -errno;
|
|
goto fail_open;
|
|
}
|
|
|
|
if (fstat(fd, &st) < 0 || (size_t) st.st_size < sizeof(hdr)) {
|
|
err = -EINVAL;
|
|
goto fail_nommap;
|
|
}
|
|
|
|
idx->mm = mmap(NULL, st.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
|
|
if (idx->mm == MAP_FAILED) {
|
|
ERR(ctx, "mmap(NULL, %"PRIu64", PROT_READ, %d, MAP_PRIVATE, 0): %m\n",
|
|
st.st_size, fd);
|
|
err = -errno;
|
|
goto fail_nommap;
|
|
}
|
|
|
|
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);
|
|
err = -EINVAL;
|
|
goto fail;
|
|
}
|
|
|
|
if (hdr.version >> 16 != INDEX_VERSION_MAJOR) {
|
|
ERR(ctx, "major version check fail: %u instead of %u\n",
|
|
hdr.version >> 16, INDEX_VERSION_MAJOR);
|
|
err = -EINVAL;
|
|
goto fail;
|
|
}
|
|
|
|
idx->root_offset = hdr.root_offset;
|
|
idx->size = st.st_size;
|
|
idx->ctx = ctx;
|
|
close(fd);
|
|
|
|
*stamp = stat_mstamp(&st);
|
|
*pidx = idx;
|
|
|
|
return 0;
|
|
|
|
fail:
|
|
munmap(idx->mm, st.st_size);
|
|
fail_nommap:
|
|
close(fd);
|
|
fail_open:
|
|
free(idx);
|
|
return err;
|
|
}
|
|
|
|
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 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)
|
|
{
|
|
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') {
|
|
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]);
|
|
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)
|
|
{
|
|
// FIXME: return value by reference instead of strdup
|
|
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 strbuf *buf,
|
|
const char *subkey,
|
|
struct index_value **out)
|
|
{
|
|
int pushed = 0;
|
|
int ch;
|
|
|
|
while (node->prefix[j]) {
|
|
ch = node->prefix[j];
|
|
|
|
strbuf_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;
|
|
|
|
strbuf_pushchar(buf, ch);
|
|
index_mm_searchwild_all(child, 0, buf, subkey, out);
|
|
strbuf_popchar(buf);
|
|
}
|
|
|
|
if (node->values.len > 0) {
|
|
if (fnmatch(strbuf_str(buf), subkey, 0) == 0)
|
|
index_mm_searchwild_allvalues(node, out);
|
|
else
|
|
index_mm_free_node(node);
|
|
} else {
|
|
index_mm_free_node(node);
|
|
}
|
|
|
|
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 strbuf *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) {
|
|
strbuf_pushchar(buf, '*');
|
|
index_mm_searchwild_all(child, 0, buf, &key[i], out);
|
|
strbuf_popchar(buf);
|
|
}
|
|
|
|
child = index_mm_readchild(node, '?');
|
|
if (child) {
|
|
strbuf_pushchar(buf, '?');
|
|
index_mm_searchwild_all(child, 0, buf, &key[i], out);
|
|
strbuf_popchar(buf);
|
|
}
|
|
|
|
child = index_mm_readchild(node, '[');
|
|
if (child) {
|
|
strbuf_pushchar(buf, '[');
|
|
index_mm_searchwild_all(child, 0, buf, &key[i], out);
|
|
strbuf_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 strbuf buf;
|
|
struct index_value *out = NULL;
|
|
|
|
strbuf_init(&buf);
|
|
index_mm_searchwild_node(root, &buf, key, 0, &out);
|
|
strbuf_release(&buf);
|
|
return out;
|
|
}
|