[thirdparty/systemd.git] / src / udev / udevadm-hwdb.c

/***
  This file is part of systemd.

  Copyright 2012 Kay Sievers <kay@vrfy.org>

  systemd 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.

  systemd 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 systemd; If not, see <http://www.gnu.org/licenses/>.
***/

#include <stdlib.h>
#include <unistd.h>
#include <getopt.h>
#include <string.h>
#include <ctype.h>

#include "util.h"
#include "strbuf.h"
#include "conf-files.h"

#include "udev.h"
#include "hwdb-internal.h"
#include "hwdb-util.h"

/*
 * Generic udev properties, key/value database based on modalias strings.
 * Uses a Patricia/radix trie to index all matches for efficient lookup.
 */

static const char * const conf_file_dirs[] = {
        "/etc/udev/hwdb.d",
        UDEVLIBEXECDIR "/hwdb.d",
        NULL
};

/* in-memory trie objects */
struct trie {
        struct trie_node *root;
        struct strbuf *strings;

        size_t nodes_count;
        size_t children_count;
        size_t values_count;
};

struct trie_node {
        /* prefix, common part for all children of this node */
        size_t prefix_off;

        /* sorted array of pointers to children nodes */
        struct trie_child_entry *children;
        uint8_t children_count;

        /* sorted array of key/value pairs */
        struct trie_value_entry *values;
        size_t values_count;
};

/* children array item with char (0-255) index */
struct trie_child_entry {
        uint8_t c;
        struct trie_node *child;
};

/* value array item with key/value pairs */
struct trie_value_entry {
        size_t key_off;
        size_t value_off;
};

static int trie_children_cmp(const void *v1, const void *v2) {
        const struct trie_child_entry *n1 = v1;
        const struct trie_child_entry *n2 = v2;

        return n1->c - n2->c;
}

static int node_add_child(struct trie *trie, struct trie_node *node, struct trie_node *node_child, uint8_t c) {
        struct trie_child_entry *child;

        /* extend array, add new entry, sort for bisection */
        child = realloc(node->children, (node->children_count + 1) * sizeof(struct trie_child_entry));
        if (!child)
                return -ENOMEM;

        node->children = child;
        trie->children_count++;
        node->children[node->children_count].c = c;
        node->children[node->children_count].child = node_child;
        node->children_count++;
        qsort(node->children, node->children_count, sizeof(struct trie_child_entry), trie_children_cmp);
        trie->nodes_count++;

        return 0;
}

static struct trie_node *node_lookup(const struct trie_node *node, uint8_t c) {
        struct trie_child_entry *child;
        struct trie_child_entry search;

        search.c = c;
        child = bsearch(&search, node->children, node->children_count, sizeof(struct trie_child_entry), trie_children_cmp);
        if (child)
                return child->child;
        return NULL;
}

static void trie_node_cleanup(struct trie_node *node) {
        size_t i;

        for (i = 0; i < node->children_count; i++)
                trie_node_cleanup(node->children[i].child);
        free(node->children);
        free(node->values);
        free(node);
}

static int trie_values_cmp(const void *v1, const void *v2, void *arg) {
        const struct trie_value_entry *val1 = v1;
        const struct trie_value_entry *val2 = v2;
        struct trie *trie = arg;

        return strcmp(trie->strings->buf + val1->key_off,
                      trie->strings->buf + val2->key_off);
}

static int trie_node_add_value(struct trie *trie, struct trie_node *node,
                          const char *key, const char *value) {
        ssize_t k, v;
        struct trie_value_entry *val;

        k = strbuf_add_string(trie->strings, key, strlen(key));
        if (k < 0)
                return k;
        v = strbuf_add_string(trie->strings, value, strlen(value));
        if (v < 0)
                return v;

        if (node->values_count) {
                struct trie_value_entry search = {
                        .key_off = k,
                        .value_off = v,
                };

                val = xbsearch_r(&search, node->values, node->values_count, sizeof(struct trie_value_entry), trie_values_cmp, trie);
                if (val) {
                        /* replace existing earlier key with new value */
                        val->value_off = v;
                        return 0;
                }
        }

        /* extend array, add new entry, sort for bisection */
        val = realloc(node->values, (node->values_count + 1) * sizeof(struct trie_value_entry));
        if (!val)
                return -ENOMEM;
        trie->values_count++;
        node->values = val;
        node->values[node->values_count].key_off = k;
        node->values[node->values_count].value_off = v;
        node->values_count++;
        qsort_r(node->values, node->values_count, sizeof(struct trie_value_entry), trie_values_cmp, trie);
        return 0;
}

static int trie_insert(struct trie *trie, struct trie_node *node, const char *search,
                       const char *key, const char *value) {
        size_t i = 0;
        int err = 0;

        for (;;) {
                size_t p;
                uint8_t c;
                struct trie_node *child;

                for (p = 0; (c = trie->strings->buf[node->prefix_off + p]); p++) {
                        _cleanup_free_ char *s = NULL;
                        ssize_t off;
                        _cleanup_free_ struct trie_node *new_child = NULL;

                        if (c == search[i + p])
                                continue;

                        /* split node */
                        new_child = new0(struct trie_node, 1);
                        if (!new_child)
                                return -ENOMEM;

                        /* move values from parent to child */
                        new_child->prefix_off = node->prefix_off + p+1;
                        new_child->children = node->children;
                        new_child->children_count = node->children_count;
                        new_child->values = node->values;
                        new_child->values_count = node->values_count;

                        /* update parent; use strdup() because the source gets realloc()d */
                        s = strndup(trie->strings->buf + node->prefix_off, p);
                        if (!s)
                                return -ENOMEM;

                        off = strbuf_add_string(trie->strings, s, p);
                        if (off < 0)
                                return off;

                        node->prefix_off = off;
                        node->children = NULL;
                        node->children_count = 0;
                        node->values = NULL;
                        node->values_count = 0;
                        err = node_add_child(trie, node, new_child, c);
                        if (err)
                                return err;

                        new_child = NULL; /* avoid cleanup */
                        break;
                }
                i += p;

                c = search[i];
                if (c == '\0')
                        return trie_node_add_value(trie, node, key, value);

                child = node_lookup(node, c);
                if (!child) {
                        ssize_t off;

                        /* new child */
                        child = new0(struct trie_node, 1);
                        if (!child)
                                return -ENOMEM;

                        off = strbuf_add_string(trie->strings, search + i+1, strlen(search + i+1));
                        if (off < 0) {
                                free(child);
                                return off;
                        }

                        child->prefix_off = off;
                        err = node_add_child(trie, node, child, c);
                        if (err) {
                                free(child);
                                return err;
                        }

                        return trie_node_add_value(trie, child, key, value);
                }

                node = child;
                i++;
        }
}

struct trie_f {
        FILE *f;
        struct trie *trie;
        uint64_t strings_off;

        uint64_t nodes_count;
        uint64_t children_count;
        uint64_t values_count;
};

/* calculate the storage space for the nodes, children arrays, value arrays */
static void trie_store_nodes_size(struct trie_f *trie, struct trie_node *node) {
        uint64_t i;

        for (i = 0; i < node->children_count; i++)
                trie_store_nodes_size(trie, node->children[i].child);

        trie->strings_off += sizeof(struct trie_node_f);
        for (i = 0; i < node->children_count; i++)
                trie->strings_off += sizeof(struct trie_child_entry_f);
        for (i = 0; i < node->values_count; i++)
                trie->strings_off += sizeof(struct trie_value_entry_f);
}

static int64_t trie_store_nodes(struct trie_f *trie, struct trie_node *node) {
        uint64_t i;
        struct trie_node_f n = {
                .prefix_off = htole64(trie->strings_off + node->prefix_off),
                .children_count = node->children_count,
                .values_count = htole64(node->values_count),
        };
        struct trie_child_entry_f *children = NULL;
        int64_t node_off;

        if (node->children_count) {
                children = new0(struct trie_child_entry_f, node->children_count);
                if (!children)
                        return -ENOMEM;
        }

        /* post-order recursion */
        for (i = 0; i < node->children_count; i++) {
                int64_t child_off;

                child_off = trie_store_nodes(trie, node->children[i].child);
                if (child_off < 0) {
                        free(children);
                        return child_off;
                }
                children[i].c = node->children[i].c;
                children[i].child_off = htole64(child_off);
        }

        /* write node */
        node_off = ftello(trie->f);
        fwrite(&n, sizeof(struct trie_node_f), 1, trie->f);
        trie->nodes_count++;

        /* append children array */
        if (node->children_count) {
                fwrite(children, sizeof(struct trie_child_entry_f), node->children_count, trie->f);
                trie->children_count += node->children_count;
                free(children);
        }

        /* append values array */
        for (i = 0; i < node->values_count; i++) {
                struct trie_value_entry_f v = {
                        .key_off = htole64(trie->strings_off + node->values[i].key_off),
                        .value_off = htole64(trie->strings_off + node->values[i].value_off),
                };

                fwrite(&v, sizeof(struct trie_value_entry_f), 1, trie->f);
                trie->values_count++;
        }

        return node_off;
}

static int trie_store(struct trie *trie, const char *filename) {
        struct trie_f t = {
                .trie = trie,
        };
        _cleanup_free_ char *filename_tmp = NULL;
        int64_t pos;
        int64_t root_off;
        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 */
        err = fseeko(t.f, sizeof(struct trie_header_f), SEEK_SET);
        if (err < 0) {
                fclose(t.f);
                unlink_noerrno(filename_tmp);
                return -errno;
        }
        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);
        err = fseeko(t.f, 0, SEEK_SET);
        if (err < 0) {
                fclose(t.f);
                unlink_noerrno(filename_tmp);
                return -errno;
        }
        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_noerrno(filename_tmp);
                return err < 0 ? err : -errno;
        }

        log_debug("=== trie on-disk ===");
        log_debug("size:             %8"PRIu64" bytes", size);
        log_debug("header:           %8zu bytes", sizeof(struct trie_header_f));
        log_debug("nodes:            %8"PRIu64" bytes (%8"PRIu64")",
                  t.nodes_count * sizeof(struct trie_node_f), t.nodes_count);
        log_debug("child pointers:   %8"PRIu64" bytes (%8"PRIu64")",
                  t.children_count * sizeof(struct trie_child_entry_f), t.children_count);
        log_debug("value pointers:   %8"PRIu64" bytes (%8"PRIu64")",
                  t.values_count * sizeof(struct trie_value_entry_f), t.values_count);
        log_debug("string store:     %8zu bytes", trie->strings->len);
        log_debug("strings start:    %8"PRIu64, t.strings_off);

        return 0;
}

static int insert_data(struct trie *trie, struct udev_list *match_list,
                       char *line, const char *filename) {
        char *value;
        struct udev_list_entry *entry;

        value = strchr(line, '=');
        if (!value) {
                log_error("Error, key/value pair expected but got '%s' in '%s':", line, filename);
                return -EINVAL;
        }

        value[0] = '\0';
        value++;

        /* libudev requires properties to start with a space */
        while (isblank(line[0]) && isblank(line[1]))
                line++;

        if (line[0] == '\0' || value[0] == '\0') {
                log_error("Error, empty key or value '%s' in '%s':", line, filename);
                return -EINVAL;
        }

        udev_list_entry_foreach(entry, udev_list_get_entry(match_list))
                trie_insert(trie, trie->root, udev_list_entry_get_name(entry), line, value);

        return 0;
}

static int import_file(struct udev *udev, struct trie *trie, const char *filename) {
        enum {
                HW_MATCH,
                HW_DATA,
                HW_NONE,
        } state = HW_NONE;
        FILE *f;
        char line[LINE_MAX];
        struct udev_list match_list;

        udev_list_init(udev, &match_list, false);

        f = fopen(filename, "re");
        if (f == NULL)
                return -errno;

        while (fgets(line, sizeof(line), f)) {
                size_t len;
                char *pos;

                /* comment line */
                if (line[0] == '#')
                        continue;

                /* strip trailing comment */
                pos = strchr(line, '#');
                if (pos)
                        pos[0] = '\0';

                /* strip trailing whitespace */
                len = strlen(line);
                while (len > 0 && isspace(line[len-1]))
                        len--;
                line[len] = '\0';

                switch (state) {
                case HW_NONE:
                        if (len == 0)
                                break;

                        if (line[0] == ' ') {
                                log_error("Error, MATCH expected but got '%s' in '%s':", line, filename);
                                break;
                        }

                        /* start of record, first match */
                        state = HW_MATCH;
                        udev_list_entry_add(&match_list, line, NULL);
                        break;

                case HW_MATCH:
                        if (len == 0) {
                                log_error("Error, DATA expected but got empty line in '%s':", filename);
                                state = HW_NONE;
                                udev_list_cleanup(&match_list);
                                break;
                        }

                        /* another match */
                        if (line[0] != ' ') {
                                udev_list_entry_add(&match_list, line, NULL);
                                break;
                        }

                        /* first data */
                        state = HW_DATA;
                        insert_data(trie, &match_list, line, filename);
                        break;

                case HW_DATA:
                        /* end of record */
                        if (len == 0) {
                                state = HW_NONE;
                                udev_list_cleanup(&match_list);
                                break;
                        }

                        if (line[0] != ' ') {
                                log_error("Error, DATA expected but got '%s' in '%s':", line, filename);
                                state = HW_NONE;
                                udev_list_cleanup(&match_list);
                                break;
                        }

                        insert_data(trie, &match_list, line, filename);
                        break;
                };
        }

        fclose(f);
        udev_list_cleanup(&match_list);
        return 0;
}

static void help(void) {
        printf("Usage: udevadm hwdb OPTIONS\n"
               "  -u,--update          update the hardware database\n"
               "  --usr                generate in " UDEVLIBEXECDIR " instead of /etc/udev\n"
               "  -t,--test=MODALIAS   query database and print result\n"
               "  -r,--root=PATH       alternative root path in the filesystem\n"
               "  -h,--help\n\n");
}

static int adm_hwdb(struct udev *udev, int argc, char *argv[]) {
        enum {
                ARG_USR = 0x100,
        };

        static const struct option options[] = {
                { "update", no_argument,       NULL, 'u' },
                { "usr",    no_argument,       NULL, ARG_USR },
                { "test",   required_argument, NULL, 't' },
                { "root",   required_argument, NULL, 'r' },
                { "help",   no_argument,       NULL, 'h' },
                {}
        };
        const char *test = NULL;
        const char *root = "";
        const char *hwdb_bin_dir = "/etc/udev";
        bool update = false;
        struct trie *trie = NULL;
        int err, c;
        int rc = EXIT_SUCCESS;

        while ((c = getopt_long(argc, argv, "ut:r:h", options, NULL)) >= 0)
                switch(c) {
                case 'u':
                        update = true;
                        break;
                case ARG_USR:
                        hwdb_bin_dir = UDEVLIBEXECDIR;
                        break;
                case 't':
                        test = optarg;
                        break;
                case 'r':
                        root = optarg;
                        break;
                case 'h':
                        help();
                        return EXIT_SUCCESS;
                case '?':
                        return EXIT_FAILURE;
                default:
                        assert_not_reached("Unknown option");
                }

        if (!update && !test) {
                log_error("Either --update or --test must be used");
                return EXIT_FAILURE;
        }

        if (update) {
                char **files, **f;
                _cleanup_free_ char *hwdb_bin = NULL;

                trie = new0(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 = new0(struct trie_node, 1);
                if (!trie->root) {
                        rc = EXIT_FAILURE;
                        goto out;
                }
                trie->nodes_count++;

                err = conf_files_list_strv(&files, ".hwdb", root, conf_file_dirs);
                if (err < 0) {
                        log_error_errno(err, "failed to enumerate hwdb files: %m");
                        rc = EXIT_FAILURE;
                        goto out;
                }
                STRV_FOREACH(f, files) {
                        log_debug("reading file '%s'", *f);
                        import_file(udev, trie, *f);
                }
                strv_free(files);

                strbuf_complete(trie->strings);

                log_debug("=== trie in-memory ===");
                log_debug("nodes:            %8zu bytes (%8zu)",
                          trie->nodes_count * sizeof(struct trie_node), trie->nodes_count);
                log_debug("children arrays:  %8zu bytes (%8zu)",
                          trie->children_count * sizeof(struct trie_child_entry), trie->children_count);
                log_debug("values arrays:    %8zu bytes (%8zu)",
                          trie->values_count * sizeof(struct trie_value_entry), trie->values_count);
                log_debug("strings:          %8zu bytes",
                          trie->strings->len);
                log_debug("strings incoming: %8zu bytes (%8zu)",
                          trie->strings->in_len, trie->strings->in_count);
                log_debug("strings dedup'ed: %8zu bytes (%8zu)",
                          trie->strings->dedup_len, trie->strings->dedup_count);

                hwdb_bin = strjoin(root, "/", hwdb_bin_dir, "/hwdb.bin", NULL);
                if (!hwdb_bin) {
                        rc = EXIT_FAILURE;
                        goto out;
                }
                mkdir_parents(hwdb_bin, 0755);
                err = trie_store(trie, hwdb_bin);
                if (err < 0) {
                        log_error_errno(err, "Failure writing database %s: %m", hwdb_bin);
                        rc = EXIT_FAILURE;
                }
        }

        if (test) {
                _cleanup_hwdb_unref_ sd_hwdb *hwdb = NULL;
                int r;

                r = sd_hwdb_new(&hwdb);
                if (r >= 0) {
                        const char *key, *value;

                        SD_HWDB_FOREACH_PROPERTY(hwdb, test, key, value)
                                printf("%s=%s\n", key, value);
                }
        }
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,
};
Commit	Line	Data
796b06c2 KS	1	/***
	2	This file is part of systemd.
	3
1298001e	4	Copyright 2012 Kay Sievers <kay@vrfy.org>
796b06c2 KS	5
	6	systemd is free software; you can redistribute it and/or modify it
	7	under the terms of the GNU Lesser General Public License as published by
	8	the Free Software Foundation; either version 2.1 of the License, or
	9	(at your option) any later version.
	10
	11	systemd is distributed in the hope that it will be useful, but
	12	WITHOUT ANY WARRANTY; without even the implied warranty of
	13	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	14	Lesser General Public License for more details.
	15
	16	You should have received a copy of the GNU Lesser General Public License
	17	along with systemd; If not, see <http://www.gnu.org/licenses/>.
	18	***/
	19
	20	#include <stdlib.h>
	21	#include <unistd.h>
	22	#include <getopt.h>
	23	#include <string.h>
06639c09	24	#include <ctype.h>
796b06c2 KS	25
	26	#include "util.h"
	27	#include "strbuf.h"
	28	#include "conf-files.h"
	29
	30	#include "udev.h"
8b516fde	31	#include "hwdb-internal.h"
d640c07d	32	#include "hwdb-util.h"
796b06c2 KS	33
	34	/*
	35	* Generic udev properties, key/value database based on modalias strings.
	36	* Uses a Patricia/radix trie to index all matches for efficient lookup.
	37	*/
	38
	39	static const char * const conf_file_dirs[] = {
2001208c	40	"/etc/udev/hwdb.d",
796b06c2 KS	41	UDEVLIBEXECDIR "/hwdb.d",
	42	NULL
	43	};
	44
	45	/* in-memory trie objects */
	46	struct trie {
	47	struct trie_node *root;
	48	struct strbuf *strings;
	49
	50	size_t nodes_count;
	51	size_t children_count;
	52	size_t values_count;
	53	};
	54
	55	struct trie_node {
	56	/* prefix, common part for all children of this node */
	57	size_t prefix_off;
	58
	59	/* sorted array of pointers to children nodes */
	60	struct trie_child_entry *children;
	61	uint8_t children_count;
	62
	63	/* sorted array of key/value pairs */
	64	struct trie_value_entry *values;
	65	size_t values_count;
	66	};
	67
	68	/* children array item with char (0-255) index */
	69	struct trie_child_entry {
	70	uint8_t c;
	71	struct trie_node *child;
	72	};
	73
	74	/* value array item with key/value pairs */
	75	struct trie_value_entry {
	76	size_t key_off;
	77	size_t value_off;
	78	};
	79
	80	static int trie_children_cmp(const void v1, const void v2) {
	81	const struct trie_child_entry *n1 = v1;
	82	const struct trie_child_entry *n2 = v2;
	83
	84	return n1->c - n2->c;
	85	}
	86
	87	static int node_add_child(struct trie trie, struct trie_node node, struct trie_node *node_child, uint8_t c) {
	88	struct trie_child_entry *child;
796b06c2 KS	89
	90	/* extend array, add new entry, sort for bisection */
	91	child = realloc(node->children, (node->children_count + 1) * sizeof(struct trie_child_entry));
8c62ecf1 ZJS	92	if (!child)
	93	return -ENOMEM;
	94
796b06c2 KS	95	node->children = child;
	96	trie->children_count++;
	97	node->children[node->children_count].c = c;
	98	node->children[node->children_count].child = node_child;
	99	node->children_count++;
	100	qsort(node->children, node->children_count, sizeof(struct trie_child_entry), trie_children_cmp);
	101	trie->nodes_count++;
8c62ecf1 ZJS	102
8c62ecf1 ZJS	103	return 0;
796b06c2 KS	104	}
	105
	106	static struct trie_node node_lookup(const struct trie_node node, uint8_t c) {
	107	struct trie_child_entry *child;
	108	struct trie_child_entry search;
	109
	110	search.c = c;
	111	child = bsearch(&search, node->children, node->children_count, sizeof(struct trie_child_entry), trie_children_cmp);
	112	if (child)
	113	return child->child;
	114	return NULL;
	115	}
	116
	117	static void trie_node_cleanup(struct trie_node *node) {
	118	size_t i;
	119
	120	for (i = 0; i < node->children_count; i++)
	121	trie_node_cleanup(node->children[i].child);
	122	free(node->children);
	123	free(node->values);
	124	free(node);
	125	}
	126
	127	static int trie_values_cmp(const void v1, const void v2, void *arg) {
	128	const struct trie_value_entry *val1 = v1;
	129	const struct trie_value_entry *val2 = v2;
	130	struct trie *trie = arg;
	131
	132	return strcmp(trie->strings->buf + val1->key_off,
	133	trie->strings->buf + val2->key_off);
	134	}
	135
	136	static int trie_node_add_value(struct trie trie, struct trie_node node,
	137	const char key, const char value) {
c225f2ff	138	ssize_t k, v;
796b06c2	139	struct trie_value_entry *val;
796b06c2 KS	140
796b06c2 KS	141	k = strbuf_add_string(trie->strings, key, strlen(key));
c225f2ff KS	142	if (k < 0)
c225f2ff KS	143	return k;
796b06c2	144	v = strbuf_add_string(trie->strings, value, strlen(value));
c225f2ff KS	145	if (v < 0)
	146	return v;
	147
	148	if (node->values_count) {
	149	struct trie_value_entry search = {
	150	.key_off = k,
	151	.value_off = v,
	152	};
	153
	154	val = xbsearch_r(&search, node->values, node->values_count, sizeof(struct trie_value_entry), trie_values_cmp, trie);
	155	if (val) {
	156	/* replace existing earlier key with new value */
	157	val->value_off = v;
	158	return 0;
	159	}
796b06c2 KS	160	}
	161
	162	/* extend array, add new entry, sort for bisection */
	163	val = realloc(node->values, (node->values_count + 1) * sizeof(struct trie_value_entry));
	164	if (!val)
	165	return -ENOMEM;
	166	trie->values_count++;
	167	node->values = val;
	168	node->values[node->values_count].key_off = k;
	169	node->values[node->values_count].value_off = v;
	170	node->values_count++;
	171	qsort_r(node->values, node->values_count, sizeof(struct trie_value_entry), trie_values_cmp, trie);
	172	return 0;
	173	}
	174
	175	static int trie_insert(struct trie trie, struct trie_node node, const char *search,
	176	const char key, const char value) {
	177	size_t i = 0;
	178	int err = 0;
	179
	180	for (;;) {
	181	size_t p;
	182	uint8_t c;
8c62ecf1	183	struct trie_node *child;
796b06c2 KS	184
796b06c2 KS	185	for (p = 0; (c = trie->strings->buf[node->prefix_off + p]); p++) {
7fd1b19b	186	_cleanup_free_ char *s = NULL;
796b06c2	187	ssize_t off;
7fd1b19b	188	_cleanup_free_ struct trie_node *new_child = NULL;
796b06c2 KS	189
	190	if (c == search[i + p])
	191	continue;
	192
	193	/* split node */
955d98c9	194	new_child = new0(struct trie_node, 1);
8c62ecf1 ZJS	195	if (!new_child)
8c62ecf1 ZJS	196	return -ENOMEM;
796b06c2 KS	197
796b06c2 KS	198	/* move values from parent to child */
8c62ecf1 ZJS	199	new_child->prefix_off = node->prefix_off + p+1;
	200	new_child->children = node->children;
	201	new_child->children_count = node->children_count;
	202	new_child->values = node->values;
	203	new_child->values_count = node->values_count;
796b06c2 KS	204
	205	/* update parent; use strdup() because the source gets realloc()d */
	206	s = strndup(trie->strings->buf + node->prefix_off, p);
8c62ecf1 ZJS	207	if (!s)
	208	return -ENOMEM;
	209
796b06c2	210	off = strbuf_add_string(trie->strings, s, p);
8c62ecf1 ZJS	211	if (off < 0)
	212	return off;
	213
796b06c2 KS	214	node->prefix_off = off;
	215	node->children = NULL;
	216	node->children_count = 0;
	217	node->values = NULL;
	218	node->values_count = 0;
8c62ecf1	219	err = node_add_child(trie, node, new_child, c);
796b06c2	220	if (err)
8c62ecf1 ZJS	221	return err;
	222
	223	new_child = NULL; /* avoid cleanup */
796b06c2 KS	224	break;
	225	}
	226	i += p;
	227
	228	c = search[i];
	229	if (c == '\0')
	230	return trie_node_add_value(trie, node, key, value);
	231
	232	child = node_lookup(node, c);
	233	if (!child) {
	234	ssize_t off;
	235
	236	/* new child */
955d98c9	237	child = new0(struct trie_node, 1);
8c62ecf1 ZJS	238	if (!child)
	239	return -ENOMEM;
	240
796b06c2 KS	241	off = strbuf_add_string(trie->strings, search + i+1, strlen(search + i+1));
796b06c2 KS	242	if (off < 0) {
8c62ecf1 ZJS	243	free(child);
8c62ecf1 ZJS	244	return off;
796b06c2	245	}
8c62ecf1	246
796b06c2 KS	247	child->prefix_off = off;
796b06c2 KS	248	err = node_add_child(trie, node, child, c);
8c62ecf1 ZJS	249	if (err) {
	250	free(child);
	251	return err;
	252	}
	253
796b06c2 KS	254	return trie_node_add_value(trie, child, key, value);
	255	}
	256
	257	node = child;
	258	i++;
	259	}
796b06c2 KS	260	}
	261
	262	struct trie_f {
	263	FILE *f;
	264	struct trie *trie;
	265	uint64_t strings_off;
	266
	267	uint64_t nodes_count;
	268	uint64_t children_count;
	269	uint64_t values_count;
	270	};
	271
	272	/* calculate the storage space for the nodes, children arrays, value arrays */
	273	static void trie_store_nodes_size(struct trie_f trie, struct trie_node node) {
	274	uint64_t i;
	275
	276	for (i = 0; i < node->children_count; i++)
	277	trie_store_nodes_size(trie, node->children[i].child);
	278
	279	trie->strings_off += sizeof(struct trie_node_f);
	280	for (i = 0; i < node->children_count; i++)
	281	trie->strings_off += sizeof(struct trie_child_entry_f);
	282	for (i = 0; i < node->values_count; i++)
	283	trie->strings_off += sizeof(struct trie_value_entry_f);
	284	}
	285
	286	static int64_t trie_store_nodes(struct trie_f trie, struct trie_node node) {
	287	uint64_t i;
	288	struct trie_node_f n = {
	289	.prefix_off = htole64(trie->strings_off + node->prefix_off),
	290	.children_count = node->children_count,
	291	.values_count = htole64(node->values_count),
	292	};
2001208c	293	struct trie_child_entry_f *children = NULL;
796b06c2 KS	294	int64_t node_off;
	295
	296	if (node->children_count) {
	297	children = new0(struct trie_child_entry_f, node->children_count);
	298	if (!children)
	299	return -ENOMEM;
	300	}
	301
	302	/* post-order recursion */
	303	for (i = 0; i < node->children_count; i++) {
	304	int64_t child_off;
	305
	306	child_off = trie_store_nodes(trie, node->children[i].child);
ef89eef7 ZJS	307	if (child_off < 0) {
ef89eef7 ZJS	308	free(children);
796b06c2	309	return child_off;
ef89eef7	310	}
796b06c2 KS	311	children[i].c = node->children[i].c;
	312	children[i].child_off = htole64(child_off);
	313	}
	314
	315	/* write node */
	316	node_off = ftello(trie->f);
	317	fwrite(&n, sizeof(struct trie_node_f), 1, trie->f);
	318	trie->nodes_count++;
	319
	320	/* append children array */
	321	if (node->children_count) {
	322	fwrite(children, sizeof(struct trie_child_entry_f), node->children_count, trie->f);
	323	trie->children_count += node->children_count;
	324	free(children);
	325	}
	326
	327	/* append values array */
	328	for (i = 0; i < node->values_count; i++) {
	329	struct trie_value_entry_f v = {
	330	.key_off = htole64(trie->strings_off + node->values[i].key_off),
	331	.value_off = htole64(trie->strings_off + node->values[i].value_off),
	332	};
	333
	334	fwrite(&v, sizeof(struct trie_value_entry_f), 1, trie->f);
	335	trie->values_count++;
	336	}
	337
	338	return node_off;
	339	}
	340
	341	static int trie_store(struct trie trie, const char filename) {
	342	struct trie_f t = {
	343	.trie = trie,
	344	};
d4f1ef44	345	_cleanup_free_ char *filename_tmp = NULL;
796b06c2 KS	346	int64_t pos;
	347	int64_t root_off;
	348	int64_t size;
	349	struct trie_header_f h = {
	350	.signature = HWDB_SIG,
	351	.tool_version = htole64(atoi(VERSION)),
	352	.header_size = htole64(sizeof(struct trie_header_f)),
	353	.node_size = htole64(sizeof(struct trie_node_f)),
	354	.child_entry_size = htole64(sizeof(struct trie_child_entry_f)),
	355	.value_entry_size = htole64(sizeof(struct trie_value_entry_f)),
	356	};
	357	int err;
	358
	359	/* calculate size of header, nodes, children entries, value entries */
	360	t.strings_off = sizeof(struct trie_header_f);
	361	trie_store_nodes_size(&t, trie->root);
	362
	363	err = fopen_temporary(filename , &t.f, &filename_tmp);
	364	if (err < 0)
	365	return err;
	366	fchmod(fileno(t.f), 0444);
	367
	368	/* write nodes */
f901aaad TG	369	err = fseeko(t.f, sizeof(struct trie_header_f), SEEK_SET);
	370	if (err < 0) {
	371	fclose(t.f);
	372	unlink_noerrno(filename_tmp);
	373	return -errno;
	374	}
796b06c2 KS	375	root_off = trie_store_nodes(&t, trie->root);
	376	h.nodes_root_off = htole64(root_off);
	377	pos = ftello(t.f);
	378	h.nodes_len = htole64(pos - sizeof(struct trie_header_f));
	379
	380	/* write string buffer */
	381	fwrite(trie->strings->buf, trie->strings->len, 1, t.f);
	382	h.strings_len = htole64(trie->strings->len);
	383
	384	/* write header */
	385	size = ftello(t.f);
	386	h.file_size = htole64(size);
f901aaad TG	387	err = fseeko(t.f, 0, SEEK_SET);
	388	if (err < 0) {
	389	fclose(t.f);
	390	unlink_noerrno(filename_tmp);
	391	return -errno;
	392	}
796b06c2 KS	393	fwrite(&h, sizeof(struct trie_header_f), 1, t.f);
	394	err = ferror(t.f);
	395	if (err)
	396	err = -errno;
	397	fclose(t.f);
	398	if (err < 0 \|\| rename(filename_tmp, filename) < 0) {
d4f1ef44 LP	399	unlink_noerrno(filename_tmp);
d4f1ef44 LP	400	return err < 0 ? err : -errno;
796b06c2 KS	401	}
796b06c2 KS	402
9f6445e3	403	log_debug("=== trie on-disk ===");
90b2de37	404	log_debug("size: %8"PRIu64" bytes", size);
9f6445e3	405	log_debug("header: %8zu bytes", sizeof(struct trie_header_f));
90b2de37 ZJS	406	log_debug("nodes: %8"PRIu64" bytes (%8"PRIu64")",
	407	t.nodes_count * sizeof(struct trie_node_f), t.nodes_count);
	408	log_debug("child pointers: %8"PRIu64" bytes (%8"PRIu64")",
	409	t.children_count * sizeof(struct trie_child_entry_f), t.children_count);
	410	log_debug("value pointers: %8"PRIu64" bytes (%8"PRIu64")",
	411	t.values_count * sizeof(struct trie_value_entry_f), t.values_count);
	412	log_debug("string store: %8zu bytes", trie->strings->len);
	413	log_debug("strings start: %8"PRIu64, t.strings_off);
d4f1ef44 LP	414
d4f1ef44 LP	415	return 0;
796b06c2 KS	416	}
796b06c2 KS	417
06639c09 KS	418	static int insert_data(struct trie trie, struct udev_list match_list,
	419	char line, const char filename) {
	420	char *value;
	421	struct udev_list_entry *entry;
	422
	423	value = strchr(line, '=');
	424	if (!value) {
9f6445e3	425	log_error("Error, key/value pair expected but got '%s' in '%s':", line, filename);
06639c09 KS	426	return -EINVAL;
	427	}
	428
	429	value[0] = '\0';
	430	value++;
	431
36afca67 PH	432	/* libudev requires properties to start with a space */
	433	while (isblank(line[0]) && isblank(line[1]))
	434	line++;
	435
06639c09	436	if (line[0] == '\0' \|\| value[0] == '\0') {
9f6445e3	437	log_error("Error, empty key or value '%s' in '%s':", line, filename);
06639c09 KS	438	return -EINVAL;
	439	}
	440
	441	udev_list_entry_foreach(entry, udev_list_get_entry(match_list))
	442	trie_insert(trie, trie->root, udev_list_entry_get_name(entry), line, value);
	443
	444	return 0;
	445	}
	446
	447	static int import_file(struct udev udev, struct trie trie, const char *filename) {
	448	enum {
	449	HW_MATCH,
	450	HW_DATA,
	451	HW_NONE,
	452	} state = HW_NONE;
796b06c2 KS	453	FILE *f;
796b06c2 KS	454	char line[LINE_MAX];
06639c09 KS	455	struct udev_list match_list;
	456
	457	udev_list_init(udev, &match_list, false);
796b06c2 KS	458
	459	f = fopen(filename, "re");
	460	if (f == NULL)
	461	return -errno;
	462
796b06c2 KS	463	while (fgets(line, sizeof(line), f)) {
796b06c2 KS	464	size_t len;
06639c09	465	char *pos;
796b06c2	466
06639c09	467	/* comment line */
796b06c2 KS	468	if (line[0] == '#')
	469	continue;
	470
06639c09 KS	471	/* strip trailing comment */
	472	pos = strchr(line, '#');
	473	if (pos)
	474	pos[0] = '\0';
796b06c2	475
06639c09	476	/* strip trailing whitespace */
796b06c2	477	len = strlen(line);
06639c09 KS	478	while (len > 0 && isspace(line[len-1]))
	479	len--;
	480	line[len] = '\0';
	481
	482	switch (state) {
	483	case HW_NONE:
	484	if (len == 0)
	485	break;
	486
	487	if (line[0] == ' ') {
9f6445e3	488	log_error("Error, MATCH expected but got '%s' in '%s':", line, filename);
06639c09 KS	489	break;
06639c09 KS	490	}
796b06c2	491
06639c09 KS	492	/* start of record, first match */
	493	state = HW_MATCH;
	494	udev_list_entry_add(&match_list, line, NULL);
	495	break;
796b06c2	496
06639c09 KS	497	case HW_MATCH:
06639c09 KS	498	if (len == 0) {
9f6445e3	499	log_error("Error, DATA expected but got empty line in '%s':", filename);
06639c09 KS	500	state = HW_NONE;
	501	udev_list_cleanup(&match_list);
	502	break;
	503	}
796b06c2	504
06639c09 KS	505	/* another match */
	506	if (line[0] != ' ') {
	507	udev_list_entry_add(&match_list, line, NULL);
	508	break;
	509	}
	510
	511	/* first data */
	512	state = HW_DATA;
	513	insert_data(trie, &match_list, line, filename);
	514	break;
	515
	516	case HW_DATA:
	517	/* end of record */
	518	if (len == 0) {
	519	state = HW_NONE;
	520	udev_list_cleanup(&match_list);
	521	break;
	522	}
	523
	524	if (line[0] != ' ') {
9f6445e3	525	log_error("Error, DATA expected but got '%s' in '%s':", line, filename);
06639c09 KS	526	state = HW_NONE;
	527	udev_list_cleanup(&match_list);
	528	break;
	529	}
3cf7b686	530
06639c09 KS	531	insert_data(trie, &match_list, line, filename);
	532	break;
	533	};
796b06c2	534	}
06639c09	535
796b06c2	536	fclose(f);
06639c09	537	udev_list_cleanup(&match_list);
796b06c2 KS	538	return 0;
	539	}
	540
	541	static void help(void) {
e32a4e1e	542	printf("Usage: udevadm hwdb OPTIONS\n"
7643ac9a	543	" -u,--update update the hardware database\n"
33488f19	544	" --usr generate in " UDEVLIBEXECDIR " instead of /etc/udev\n"
7643ac9a ZJS	545	" -t,--test=MODALIAS query database and print result\n"
	546	" -r,--root=PATH alternative root path in the filesystem\n"
	547	" -h,--help\n\n");
796b06c2 KS	548	}
	549
	550	static int adm_hwdb(struct udev udev, int argc, char argv[]) {
33488f19 MP	551	enum {
	552	ARG_USR = 0x100,
	553	};
	554
796b06c2	555	static const struct option options[] = {
7643ac9a	556	{ "update", no_argument, NULL, 'u' },
33488f19	557	{ "usr", no_argument, NULL, ARG_USR },
7643ac9a ZJS	558	{ "test", required_argument, NULL, 't' },
	559	{ "root", required_argument, NULL, 'r' },
	560	{ "help", no_argument, NULL, 'h' },
796b06c2 KS	561	{}
796b06c2 KS	562	};
23b72453	563	const char *test = NULL;
3e49f2ec	564	const char *root = "";
33488f19	565	const char *hwdb_bin_dir = "/etc/udev";
796b06c2	566	bool update = false;
23b72453	567	struct trie *trie = NULL;
7643ac9a	568	int err, c;
796b06c2 KS	569	int rc = EXIT_SUCCESS;
796b06c2 KS	570
7643ac9a ZJS	571	while ((c = getopt_long(argc, argv, "ut:r:h", options, NULL)) >= 0)
7643ac9a ZJS	572	switch(c) {
796b06c2 KS	573	case 'u':
	574	update = true;
	575	break;
33488f19 MP	576	case ARG_USR:
	577	hwdb_bin_dir = UDEVLIBEXECDIR;
	578	break;
23b72453 KS	579	case 't':
	580	test = optarg;
	581	break;
3e49f2ec KS	582	case 'r':
	583	root = optarg;
	584	break;
796b06c2 KS	585	case 'h':
	586	help();
	587	return EXIT_SUCCESS;
7643ac9a ZJS	588	case '?':
	589	return EXIT_FAILURE;
	590	default:
	591	assert_not_reached("Unknown option");
796b06c2	592	}
796b06c2	593
23b72453	594	if (!update && !test) {
7643ac9a ZJS	595	log_error("Either --update or --test must be used");
7643ac9a ZJS	596	return EXIT_FAILURE;
796b06c2 KS	597	}
796b06c2 KS	598
23b72453 KS	599	if (update) {
23b72453 KS	600	char files, f;
3e49f2ec	601	_cleanup_free_ char *hwdb_bin = NULL;
796b06c2	602
955d98c9	603	trie = new0(struct trie, 1);
23b72453 KS	604	if (!trie) {
	605	rc = EXIT_FAILURE;
	606	goto out;
	607	}
796b06c2	608
23b72453 KS	609	/* string store */
	610	trie->strings = strbuf_new();
	611	if (!trie->strings) {
	612	rc = EXIT_FAILURE;
	613	goto out;
	614	}
796b06c2	615
23b72453	616	/* index */
955d98c9	617	trie->root = new0(struct trie_node, 1);
23b72453 KS	618	if (!trie->root) {
	619	rc = EXIT_FAILURE;
	620	goto out;
	621	}
	622	trie->nodes_count++;
	623
844ec79b	624	err = conf_files_list_strv(&files, ".hwdb", root, conf_file_dirs);
23b72453	625	if (err < 0) {
da927ba9	626	log_error_errno(err, "failed to enumerate hwdb files: %m");
23b72453 KS	627	rc = EXIT_FAILURE;
	628	goto out;
	629	}
	630	STRV_FOREACH(f, files) {
	631	log_debug("reading file '%s'", *f);
06639c09	632	import_file(udev, trie, *f);
23b72453 KS	633	}
	634	strv_free(files);
	635
	636	strbuf_complete(trie->strings);
	637
9f6445e3 LP	638	log_debug("=== trie in-memory ===");
9f6445e3 LP	639	log_debug("nodes: %8zu bytes (%8zu)",
3a4431ef	640	trie->nodes_count * sizeof(struct trie_node), trie->nodes_count);
9f6445e3	641	log_debug("children arrays: %8zu bytes (%8zu)",
3a4431ef	642	trie->children_count * sizeof(struct trie_child_entry), trie->children_count);
9f6445e3	643	log_debug("values arrays: %8zu bytes (%8zu)",
3a4431ef	644	trie->values_count * sizeof(struct trie_value_entry), trie->values_count);
9f6445e3	645	log_debug("strings: %8zu bytes",
3a4431ef	646	trie->strings->len);
9f6445e3	647	log_debug("strings incoming: %8zu bytes (%8zu)",
3a4431ef	648	trie->strings->in_len, trie->strings->in_count);
9f6445e3	649	log_debug("strings dedup'ed: %8zu bytes (%8zu)",
3a4431ef	650	trie->strings->dedup_len, trie->strings->dedup_count);
23b72453	651
33488f19 MP	652	hwdb_bin = strjoin(root, "/", hwdb_bin_dir, "/hwdb.bin", NULL);
33488f19 MP	653	if (!hwdb_bin) {
3e49f2ec KS	654	rc = EXIT_FAILURE;
	655	goto out;
	656	}
	657	mkdir_parents(hwdb_bin, 0755);
	658	err = trie_store(trie, hwdb_bin);
23b72453	659	if (err < 0) {
da927ba9	660	log_error_errno(err, "Failure writing database %s: %m", hwdb_bin);
23b72453 KS	661	rc = EXIT_FAILURE;
23b72453 KS	662	}
796b06c2	663	}
23b72453 KS	664
23b72453 KS	665	if (test) {
d640c07d TG	666	_cleanup_hwdb_unref_ sd_hwdb *hwdb = NULL;
d640c07d TG	667	int r;
23b72453	668
d640c07d TG	669	r = sd_hwdb_new(&hwdb);
	670	if (r >= 0) {
	671	const char key, value;
23b72453	672
d640c07d TG	673	SD_HWDB_FOREACH_PROPERTY(hwdb, test, key, value)
d640c07d TG	674	printf("%s=%s\n", key, value);
23b72453	675	}
796b06c2	676	}
796b06c2	677	out:
23b72453 KS	678	if (trie) {
	679	if (trie->root)
	680	trie_node_cleanup(trie->root);
	681	strbuf_cleanup(trie->strings);
	682	free(trie);
	683	}
796b06c2 KS	684	return rc;
	685	}
	686
	687	const struct udevadm_cmd udevadm_hwdb = {
	688	.name = "hwdb",
	689	.cmd = adm_hwdb,
796b06c2	690	};