3988N/A

3988N/A#include <stdlib.h>

3988N/A#include <unistd.h>

3988N/A#include <getopt.h>

3988N/A#include <string.h>

3988N/A

3988N/A#include "util.h"

3988N/A#include "strbuf.h"

3988N/A#include "conf-files.h"

3988N/A

3988N/A#include "udev.h"

3988N/A#include "libudev-hwdb-def.h"

4001N/A

3988N/A

3988N/Astatic const char * const conf_file_dirs[] = {

3988N/A "/etc/udev/hwdb.d",

3988N/A UDEVLIBEXECDIR "/hwdb.d",

3988N/A NULL

3988N/A};

3988N/A

3988N/Astruct trie {

3988N/A struct trie_node *root;

3988N/A struct strbuf *strings;

3988N/A

3988N/A size_t nodes_count;

3988N/A size_t children_count;

3988N/A size_t values_count;

3988N/A};

3988N/A

3988N/Astruct trie_node {

3988N/A /* prefix, common part for all children of this node */

3988N/A size_t prefix_off;

4001N/A

3988N/A /* sorted array of pointers to children nodes */

3988N/A struct trie_child_entry *children;

3988N/A uint8_t children_count;

3988N/A

3988N/A /* sorted array of key/value pairs */

3988N/A struct trie_value_entry *values;

3988N/A size_t values_count;

3988N/A};

3988N/A

3988N/Astruct trie_child_entry {

3988N/A uint8_t c;

3988N/A struct trie_node *child;

3988N/A};

3988N/A

3988N/Astruct trie_value_entry {

3988N/A size_t key_off;

3988N/A size_t value_off;

3988N/A};

3988N/A

3988N/Astatic int trie_children_cmp(const void *v1, const void *v2) {

3988N/A const struct trie_child_entry *n1 = v1;

3988N/A const struct trie_child_entry *n2 = v2;

3988N/A

3988N/A return n1->c - n2->c;

3988N/A}

3988N/A

3988N/Astatic int node_add_child(struct trie *trie, struct trie_node *node, struct trie_node *node_child, uint8_t c) {

3988N/A struct trie_child_entry *child;

3988N/A int err = 0;

3988N/A

3988N/A /* extend array, add new entry, sort for bisection */

3988N/A child = realloc(node->children, (node->children_count + 1) * sizeof(struct trie_child_entry));

3988N/A if (!child) {

3988N/A err = -ENOMEM;

3988N/A goto out;

3988N/A }

3988N/A node->children = child;

3988N/A trie->children_count++;

3988N/A node->children[node->children_count].c = c;

3988N/A node->children[node->children_count].child = node_child;

3988N/A node->children_count++;

3988N/A qsort(node->children, node->children_count, sizeof(struct trie_child_entry), trie_children_cmp);

4001N/A trie->nodes_count++;

4001N/Aout:

4001N/A return err;

4001N/A}

4001N/A

4001N/Astatic struct trie_node *node_lookup(const struct trie_node *node, uint8_t c) {

4001N/A struct trie_child_entry *child;

4001N/A struct trie_child_entry search;

4001N/A

4001N/A search.c = c;

4001N/A child = bsearch(&search, node->children, node->children_count, sizeof(struct trie_child_entry), trie_children_cmp);

4001N/A if (child)

4001N/A return child->child;

4001N/A return NULL;

4001N/A}

4001N/A

4001N/Astatic void trie_node_cleanup(struct trie_node *node) {

4001N/A size_t i;

4001N/A

4001N/A for (i = 0; i < node->children_count; i++)

4001N/A trie_node_cleanup(node->children[i].child);

4001N/A free(node->children);

4001N/A free(node->values);

4001N/A free(node);

4001N/A}

4001N/A

4001N/Astatic int trie_values_cmp(const void *v1, const void *v2, void *arg) {

3988N/A const struct trie_value_entry *val1 = v1;

3988N/A const struct trie_value_entry *val2 = v2;

3988N/A struct trie *trie = arg;

3988N/A

3988N/A return strcmp(trie->strings->buf + val1->key_off,

3988N/A trie->strings->buf + val2->key_off);

3988N/A}

3988N/A

3988N/Astatic int trie_node_add_value(struct trie *trie, struct trie_node *node,

3988N/A const char *key, const char *value) {

3988N/A ssize_t k, v;

3988N/A struct trie_value_entry *val;

3988N/A

3988N/A k = strbuf_add_string(trie->strings, key, strlen(key));

3988N/A if (k < 0)

3988N/A return k;

3988N/A v = strbuf_add_string(trie->strings, value, strlen(value));

3988N/A if (v < 0)

3988N/A return v;

3988N/A

3988N/A if (node->values_count) {

3988N/A struct trie_value_entry search = {

3988N/A .key_off = k,

3988N/A .value_off = v,

3988N/A };

3988N/A

3988N/A val = xbsearch_r(&search, node->values, node->values_count, sizeof(struct trie_value_entry), trie_values_cmp, trie);

3988N/A if (val) {

3988N/A /* replace existing earlier key with new value */

3988N/A val->value_off = v;

3988N/A return 0;

3988N/A }

3988N/A }

3988N/A

3988N/A /* extend array, add new entry, sort for bisection */

3988N/A val = realloc(node->values, (node->values_count + 1) * sizeof(struct trie_value_entry));

3988N/A if (!val)

3988N/A return -ENOMEM;

3988N/A trie->values_count++;

3988N/A node->values = val;

3988N/A node->values[node->values_count].key_off = k;

3988N/A node->values[node->values_count].value_off = v;

3988N/A node->values_count++;

3988N/A qsort_r(node->values, node->values_count, sizeof(struct trie_value_entry), trie_values_cmp, trie);

3988N/A return 0;

3988N/A}

3988N/A

3988N/Astatic int trie_insert(struct trie *trie, struct trie_node *node, const char *search,

3988N/A const char *key, const char *value) {

3988N/A size_t i = 0;

3988N/A int err = 0;

3988N/A

3988N/A for (;;) {

3988N/A size_t p;

3988N/A uint8_t c;

3988N/A struct trie_node *child;

3988N/A

3988N/A for (p = 0; (c = trie->strings->buf[node->prefix_off + p]); p++) {

3988N/A char *s;

3988N/A ssize_t off;

3988N/A

3988N/A if (c == search[i + p])

3988N/A continue;

3988N/A

3988N/A /* split node */

3988N/A child = calloc(sizeof(struct trie_node), 1);

4001N/A if (!child) {

3988N/A err = -ENOMEM;

3988N/A goto out;

3988N/A }

3988N/A

3988N/A /* move values from parent to child */

3988N/A child->prefix_off = node->prefix_off + p+1;

3988N/A child->children = node->children;

3988N/A child->children_count = node->children_count;

3988N/A child->values = node->values;

3988N/A child->values_count = node->values_count;

3988N/A

3988N/A /* update parent; use strdup() because the source gets realloc()d */

3988N/A s = strndup(trie->strings->buf + node->prefix_off, p);

3988N/A if (!s) {

3988N/A err = -ENOMEM;

3988N/A goto out;

3988N/A }

3988N/A off = strbuf_add_string(trie->strings, s, p);

3988N/A free(s);

3988N/A if (off < 0) {

3988N/A err = off;

3988N/A goto out;

3988N/A }

3988N/A node->prefix_off = off;

3988N/A node->children = NULL;

3988N/A node->children_count = 0;

3988N/A node->values = NULL;

3988N/A node->values_count = 0;

3988N/A err = node_add_child(trie, node, child, c);

3988N/A if (err)

3988N/A goto out;

3988N/A break;

3988N/A }

3988N/A i += p;

3988N/A

3988N/A c = search[i];

3988N/A if (c == '\0')

3988N/A return trie_node_add_value(trie, node, key, value);

3988N/A

3988N/A child = node_lookup(node, c);

3988N/A if (!child) {

3988N/A ssize_t off;

3988N/A

3988N/A /* new child */

3988N/A child = calloc(sizeof(struct trie_node), 1);

3988N/A if (!child) {

3988N/A err = -ENOMEM;

3988N/A goto out;

3988N/A }

3988N/A off = strbuf_add_string(trie->strings, search + i+1, strlen(search + i+1));

3988N/A if (off < 0) {

3988N/A err = off;

3988N/A goto out;

3988N/A }

3988N/A child->prefix_off = off;

3988N/A err = node_add_child(trie, node, child, c);

3988N/A if (err)

3988N/A goto out;

3988N/A return trie_node_add_value(trie, child, key, value);

3988N/A }

3988N/A

3988N/A node = child;

3988N/A i++;

3988N/A }

3988N/Aout:

3988N/A return err;

3988N/A}

3988N/A

3988N/Astruct trie_f {

3988N/A FILE *f;

3988N/A struct trie *trie;

3988N/A uint64_t strings_off;

3988N/A

3988N/A uint64_t nodes_count;

3988N/A uint64_t children_count;

3988N/A uint64_t values_count;

3988N/A};

3988N/A

3988N/Astatic void trie_store_nodes_size(struct trie_f *trie, struct trie_node *node) {

3988N/A uint64_t i;

3988N/A

3988N/A for (i = 0; i < node->children_count; i++)

3988N/A trie_store_nodes_size(trie, node->children[i].child);

3988N/A

3988N/A trie->strings_off += sizeof(struct trie_node_f);

3988N/A for (i = 0; i < node->children_count; i++)

3988N/A trie->strings_off += sizeof(struct trie_child_entry_f);

3988N/A for (i = 0; i < node->values_count; i++)

3988N/A trie->strings_off += sizeof(struct trie_value_entry_f);

3988N/A}

3988N/A

3988N/Astatic int64_t trie_store_nodes(struct trie_f *trie, struct trie_node *node) {

3988N/A uint64_t i;

3988N/A struct trie_node_f n = {

3988N/A .prefix_off = htole64(trie->strings_off + node->prefix_off),

3988N/A .children_count = node->children_count,

3988N/A .values_count = htole64(node->values_count),

3988N/A };

3988N/A struct trie_child_entry_f *children = NULL;

3988N/A int64_t node_off;

3988N/A

3988N/A if (node->children_count) {

3988N/A children = new0(struct trie_child_entry_f, node->children_count);

3988N/A if (!children)

3988N/A return -ENOMEM;

3988N/A }

3988N/A

3988N/A /* post-order recursion */

3988N/A for (i = 0; i < node->children_count; i++) {

3988N/A int64_t child_off;

3988N/A

3988N/A child_off = trie_store_nodes(trie, node->children[i].child);

3988N/A if (child_off < 0)

3988N/A return child_off;

3988N/A children[i].c = node->children[i].c;

3988N/A children[i].child_off = htole64(child_off);

3988N/A }

3988N/A

3988N/A /* write node */

3988N/A node_off = ftello(trie->f);

3988N/A fwrite(&n, sizeof(struct trie_node_f), 1, trie->f);

3988N/A trie->nodes_count++;

3988N/A

3988N/A /* append children array */

3988N/A if (node->children_count) {

3988N/A fwrite(children, sizeof(struct trie_child_entry_f), node->children_count, trie->f);

3988N/A trie->children_count += node->children_count;

3988N/A free(children);

3988N/A }

3988N/A

3988N/A /* append values array */

3988N/A for (i = 0; i < node->values_count; i++) {

3988N/A struct trie_value_entry_f v = {

3988N/A .key_off = htole64(trie->strings_off + node->values[i].key_off),

3988N/A .value_off = htole64(trie->strings_off + node->values[i].value_off),

3988N/A };

3988N/A

3988N/A fwrite(&v, sizeof(struct trie_value_entry_f), 1, trie->f);

3988N/A trie->values_count++;

3988N/A }

3988N/A

3988N/A return node_off;

3988N/A}

3988N/A

3988N/Astatic int trie_store(struct trie *trie, const char *filename) {

3988N/A struct trie_f t = {

3988N/A .trie = trie,

3988N/A };

3988N/A char *filename_tmp;

3988N/A int64_t pos;

3988N/A int64_t root_off;

3988N/A int64_t size;

struct trie_header_f h = {

.signature = HWDB_SIG,

.tool_version = htole64(atoi(VERSION)),

.header_size = htole64(sizeof(struct trie_header_f)),

.node_size = htole64(sizeof(struct trie_node_f)),

.child_entry_size = htole64(sizeof(struct trie_child_entry_f)),

.value_entry_size = htole64(sizeof(struct trie_value_entry_f)),

};

int err;

/* calculate size of header, nodes, children entries, value entries */

t.strings_off = sizeof(struct trie_header_f);

trie_store_nodes_size(&t, trie->root);

err = fopen_temporary(filename , &t.f, &filename_tmp);

if (err < 0)

return err;

fchmod(fileno(t.f), 0444);

/* write nodes */

fseeko(t.f, sizeof(struct trie_header_f), SEEK_SET);

root_off = trie_store_nodes(&t, trie->root);

h.nodes_root_off = htole64(root_off);

pos = ftello(t.f);

h.nodes_len = htole64(pos - sizeof(struct trie_header_f));

/* write string buffer */

fwrite(trie->strings->buf, trie->strings->len, 1, t.f);

h.strings_len = htole64(trie->strings->len);

/* write header */

size = ftello(t.f);

h.file_size = htole64(size);

fseeko(t.f, 0, SEEK_SET);

fwrite(&h, sizeof(struct trie_header_f), 1, t.f);

err = ferror(t.f);

if (err)

err = -errno;

fclose(t.f);

if (err < 0 || rename(filename_tmp, filename) < 0) {

unlink(filename_tmp);

goto out;

}

log_debug("=== trie on-disk ===\n");

log_debug("size: %8llu bytes\n", (unsigned long long)size);

log_debug("header: %8zu bytes\n", sizeof(struct trie_header_f));

log_debug("nodes: %8llu bytes (%8llu)\n",

(unsigned long long)t.nodes_count * sizeof(struct trie_node_f), (unsigned long long)t.nodes_count);

log_debug("child pointers: %8llu bytes (%8llu)\n",

(unsigned long long)t.children_count * sizeof(struct trie_child_entry_f), (unsigned long long)t.children_count);

log_debug("value pointers: %8llu bytes (%8llu)\n",

(unsigned long long)t.values_count * sizeof(struct trie_value_entry_f), (unsigned long long)t.values_count);

log_debug("string store: %8llu bytes\n", (unsigned long long)trie->strings->len);

log_debug("strings start: %8llu\n", (unsigned long long) t.strings_off);

out:

free(filename_tmp);

return err;

}

static int import_file(struct trie *trie, const char *filename) {

FILE *f;

char line[LINE_MAX];

char match[LINE_MAX];

char cond[LINE_MAX];

f = fopen(filename, "re");

if (f == NULL)

return -errno;

match[0] = '\0';

cond[0] = '\0';

while (fgets(line, sizeof(line), f)) {

size_t len;

if (line[0] == '#')

continue;

/* new line, new record */

if (line[0] == '\n') {

match[0] = '\0';

cond[0] = '\0';

continue;

}

/* remove newline */

len = strlen(line);

if (len < 2)

continue;

line[len-1] = '\0';

/* start of new record */

if (match[0] == '\0') {

strcpy(match, line);

cond[0] = '\0';

continue;

}

if (line[0] == '+') {

strcpy(cond, line);

continue;

}

/* TODO: support +; skip the entire record until we support it */

if (cond[0] != '\0')

continue;

/* value lines */

if (line[0] == ' ') {

char *value;

value = strchr(line, '=');

if (!value)

continue;

value[0] = '\0';

value++;

trie_insert(trie, trie->root, match, line, value);

}

}

fclose(f);

return 0;

}

static void help(void) {

printf("Usage: udevadm hwdb [--create] [--help]\n"

" --update update the hardware database\n"

" --test <modalias> query database and print result\n"

" --help\n\n");

}

static int adm_hwdb(struct udev *udev, int argc, char *argv[]) {

static const struct option options[] = {

{ "update", no_argument, NULL, 'u' },

{ "test", required_argument, NULL, 't' },

{ "help", no_argument, NULL, 'h' },

{}

};

const char *test = NULL;

bool update = false;

struct trie *trie = NULL;

int err;

int rc = EXIT_SUCCESS;

for (;;) {

int option;

option = getopt_long(argc, argv, "ut:h", options, NULL);

if (option == -1)

break;

switch (option) {

case 'u':

update = true;

break;

case 't':

test = optarg;

break;

case 'h':

help();

return EXIT_SUCCESS;

}

}

if (!update && !test) {

help();

return EXIT_SUCCESS;

}

if (update) {

char **files, **f;

trie = calloc(sizeof(struct trie), 1);

if (!trie) {

rc = EXIT_FAILURE;

goto out;

}

/* string store */

trie->strings = strbuf_new();

if (!trie->strings) {

rc = EXIT_FAILURE;

goto out;

}

/* index */

trie->root = calloc(sizeof(struct trie_node), 1);

if (!trie->root) {

rc = EXIT_FAILURE;

goto out;

}

trie->nodes_count++;

err = conf_files_list_strv(&files, ".hwdb", (const char **)conf_file_dirs);

if (err < 0) {

log_error("failed to enumerate hwdb files: %s\n", strerror(-err));

rc = EXIT_FAILURE;

goto out;

}

STRV_FOREACH(f, files) {

log_debug("reading file '%s'", *f);

import_file(trie, *f);

}

strv_free(files);

strbuf_complete(trie->strings);

log_debug("=== trie in-memory ===\n");

log_debug("nodes: %8zu bytes (%8zu)\n",

trie->nodes_count * sizeof(struct trie_node), trie->nodes_count);

log_debug("children arrays: %8zu bytes (%8zu)\n",

trie->children_count * sizeof(struct trie_child_entry), trie->children_count);

log_debug("values arrays: %8zu bytes (%8zu)\n",

trie->values_count * sizeof(struct trie_value_entry), trie->values_count);

log_debug("strings: %8zu bytes\n",

trie->strings->len);

log_debug("strings incoming: %8zu bytes (%8zu)\n",

trie->strings->in_len, trie->strings->in_count);

log_debug("strings dedup'ed: %8zu bytes (%8zu)\n",

trie->strings->dedup_len, trie->strings->dedup_count);

mkdir_parents(HWDB_BIN, 0755);

err = trie_store(trie, HWDB_BIN);

if (err < 0) {

log_error("Failure writing hardware database '%s': %s",

HWDB_BIN, strerror(-err));

rc = EXIT_FAILURE;

}

}

if (test) {

struct udev_hwdb *hwdb = udev_hwdb_new(udev);

if (hwdb) {

struct udev_list_entry *entry;

udev_list_entry_foreach(entry, udev_hwdb_get_properties_list_entry(hwdb, test, 0))

printf("%s=%s\n", udev_list_entry_get_name(entry), udev_list_entry_get_value(entry));

hwdb = udev_hwdb_unref(hwdb);

}

}

out:

if (trie) {

if (trie->root)

trie_node_cleanup(trie->root);

strbuf_cleanup(trie->strings);

free(trie);

}

return rc;

}

const struct udevadm_cmd udevadm_hwdb = {

.name = "hwdb",

.cmd = adm_hwdb,

.help = "maintain the hardware database index",

};