[thirdparty/systemd.git] / src / libsystemd / sd-hwdb / hwdb-util.c

/* SPDX-License-Identifier: LGPL-2.1+ */

#include <ctype.h>
#include <stdio.h>
#include <sys/stat.h>

#include "alloc-util.h"
#include "conf-files.h"
#include "fd-util.h"
#include "fileio.h"
#include "fs-util.h"
#include "hwdb-internal.h"
#include "hwdb-util.h"
#include "label.h"
#include "mkdir.h"
#include "path-util.h"
#include "sort-util.h"
#include "strbuf.h"
#include "string-util.h"
#include "strv.h"
#include "tmpfile-util.h"

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

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

/* 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;
        size_t filename_off;
        uint32_t line_number;
        uint16_t file_priority;
};

static int trie_children_cmp(const struct trie_child_entry *a, const struct trie_child_entry *b) {
        return CMP(a->c, b->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 = reallocarray(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++;
        typesafe_qsort(node->children, node->children_count, 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 = typesafe_bsearch(&search, node->children, node->children_count, trie_children_cmp);
        if (child)
                return child->child;
        return NULL;
}

static void trie_node_cleanup(struct trie_node *node) {
        if (!node)
                return;

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

static void trie_free(struct trie *trie) {
        if (!trie)
                return;

        trie_node_cleanup(trie->root);
        strbuf_cleanup(trie->strings);
        free(trie);
}

DEFINE_TRIVIAL_CLEANUP_FUNC(struct trie*, trie_free);

static int trie_values_cmp(const struct trie_value_entry *a, const struct trie_value_entry *b, struct trie *trie) {
        return strcmp(trie->strings->buf + a->key_off,
                      trie->strings->buf + b->key_off);
}

static int trie_node_add_value(struct trie *trie, struct trie_node *node,
                               const char *key, const char *value,
                               const char *filename, uint16_t file_priority, uint32_t line_number, bool compat) {
        ssize_t k, v, fn = 0;
        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 (!compat) {
                fn = strbuf_add_string(trie->strings, filename, strlen(filename));
                if (fn < 0)
                        return fn;
        }

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

                val = typesafe_bsearch_r(&search, node->values, node->values_count, trie_values_cmp, trie);
                if (val) {
                        /* At this point we have 2 identical properties on the same match-string.
                         * Since we process files in order, we just replace the previous value. */
                        val->value_off = v;
                        val->filename_off = fn;
                        val->file_priority = file_priority;
                        val->line_number = line_number;
                        return 0;
                }
        }

        /* extend array, add new entry, sort for bisection */
        val = reallocarray(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] = (struct trie_value_entry) {
                .key_off = k,
                .value_off = v,
                .filename_off = fn,
                .file_priority = file_priority,
                .line_number = line_number,
        };
        node->values_count++;
        typesafe_qsort_r(node->values, node->values_count, 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,
                       const char *filename, uint16_t file_priority, uint32_t line_number, bool compat) {
        int r = 0;

        for (size_t i = 0;; i++) {
                size_t p;
                uint8_t c;
                struct trie_node *child;

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

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

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

                        /* move values from parent to child */
                        *new_child = (struct trie_node) {
                                .prefix_off = node->prefix_off + p+1,
                                .children = node->children,
                                .children_count = node->children_count,
                                .values = node->values,
                                .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 = (struct trie_node) {
                                .prefix_off = off,
                        };
                        r = node_add_child(trie, node, new_child, c);
                        if (r < 0)
                                return r;

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

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

                child = node_lookup(node, c);
                if (!child) {
                        _cleanup_free_ struct trie_node *new_child = NULL;
                        ssize_t off;

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

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

                        *new_child = (struct trie_node) {
                                .prefix_off = off,
                        };

                        r = node_add_child(trie, node, new_child, c);
                        if (r < 0)
                                return r;

                        child = TAKE_PTR(new_child);
                        return trie_node_add_value(trie, child, key, value, filename, file_priority, line_number, compat);
                }

                node = child;
        }
}

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, bool compat) {
        for (uint64_t i = 0; i < node->children_count; i++)
                trie_store_nodes_size(trie, node->children[i].child, compat);

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

static int64_t trie_store_nodes(struct trie_f *trie, struct trie_node *node, bool compat) {
        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),
        };
        _cleanup_free_ struct trie_child_entry_f *children = NULL;
        int64_t node_off;

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

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

                child_off = trie_store_nodes(trie, node->children[i].child, compat);
                if (child_off < 0)
                        return child_off;

                children[i] = (struct trie_child_entry_f) {
                        .c = node->children[i].c,
                        .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;
        }

        /* append values array */
        for (uint64_t i = 0; i < node->values_count; i++) {
                struct trie_value_entry2_f v = {
                        .key_off = htole64(trie->strings_off + node->values[i].key_off),
                        .value_off = htole64(trie->strings_off + node->values[i].value_off),
                        .filename_off = htole64(trie->strings_off + node->values[i].filename_off),
                        .line_number = htole32(node->values[i].line_number),
                        .file_priority = htole16(node->values[i].file_priority),
                };

                fwrite(&v, compat ? sizeof(struct trie_value_entry_f) : sizeof(struct trie_value_entry2_f), 1, trie->f);
        }
        trie->values_count += node->values_count;

        return node_off;
}

static int trie_store(struct trie *trie, const char *filename, bool compat) {
        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(PROJECT_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(compat ? sizeof(struct trie_value_entry_f) : sizeof(struct trie_value_entry2_f)),
        };
        int r;

        /* calculate size of header, nodes, children entries, value entries */
        t.strings_off = sizeof(struct trie_header_f);
        trie_store_nodes_size(&t, trie->root, compat);

        r = fopen_temporary(filename, &t.f, &filename_tmp);
        if (r < 0)
                return r;
        fchmod(fileno(t.f), 0444);

        /* write nodes */
        if (fseeko(t.f, sizeof(struct trie_header_f), SEEK_SET) < 0)
                goto error_fclose;

        root_off = trie_store_nodes(&t, trie->root, compat);
        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);
        if (fseeko(t.f, 0, SEEK_SET) < 0)
                goto error_fclose;
        fwrite(&h, sizeof(struct trie_header_f), 1, t.f);

        if (ferror(t.f))
                goto error_fclose;
        if (fflush(t.f) < 0)
                goto error_fclose;
        if (fsync(fileno(t.f)) < 0)
                goto error_fclose;
        if (rename(filename_tmp, filename) < 0)
                goto error_fclose;

        /* write succeeded */
        fclose(t.f);

        log_debug("=== trie on-disk ===");
        log_debug("size:             %8"PRIi64" 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 * (compat ? sizeof(struct trie_value_entry_f) : sizeof(struct trie_value_entry2_f)), t.values_count);
        log_debug("string store:     %8zu bytes", trie->strings->len);
        log_debug("strings start:    %8"PRIu64, t.strings_off);
        return 0;

 error_fclose:
        r = -errno;
        fclose(t.f);
        (void) unlink(filename_tmp);
        return r;
}

static int insert_data(struct trie *trie, char **match_list, char *line, const char *filename,
                       uint16_t file_priority, uint32_t line_number, bool compat) {
        char *value, **entry;

        assert(line[0] == ' ');

        value = strchr(line, '=');
        if (!value)
                return log_syntax(NULL, LOG_WARNING, filename, line_number, SYNTHETIC_ERRNO(EINVAL),
                                  "Key-value pair expected but got \"%s\", ignoring.", line);

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

        /* Replace multiple leading spaces by a single space */
        while (isblank(line[0]) && isblank(line[1]))
                line++;

        if (isempty(line + 1))
                return log_syntax(NULL, LOG_WARNING, filename, line_number, SYNTHETIC_ERRNO(EINVAL),
                                  "Empty key in \"%s=%s\", ignoring.",
                                  line, value);

        STRV_FOREACH(entry, match_list)
                trie_insert(trie, trie->root, *entry, line, value, filename, file_priority, line_number, compat);

        return 0;
}

static int import_file(struct trie *trie, const char *filename, uint16_t file_priority, bool compat) {
        enum {
                HW_NONE,
                HW_MATCH,
                HW_DATA,
        } state = HW_NONE;
        _cleanup_fclose_ FILE *f = NULL;
        _cleanup_strv_free_ char **match_list = NULL;
        uint32_t line_number = 0;
        int r, err;

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

        for (;;) {
                _cleanup_free_ char *line = NULL;
                size_t len;
                char *pos;

                r = read_line_full(f, LONG_LINE_MAX, READ_LINE_NOT_A_TTY, &line);
                if (r < 0)
                        return r;
                if (r == 0)
                        break;

                line_number ++;

                /* 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] == ' ') {
                                r = log_syntax(NULL, LOG_WARNING, filename, line_number, SYNTHETIC_ERRNO(EINVAL),
                                               "Match expected but got indented property \"%s\", ignoring line.", line);
                                break;
                        }

                        /* start of record, first match */
                        state = HW_MATCH;

                        err = strv_extend(&match_list, line);
                        if (err < 0)
                                return err;

                        break;

                case HW_MATCH:
                        if (len == 0) {
                                r = log_syntax(NULL, LOG_WARNING, filename, line_number, SYNTHETIC_ERRNO(EINVAL),
                                               "Property expected, ignoring record with no properties.");
                                state = HW_NONE;
                                match_list = strv_free(match_list);
                                break;
                        }

                        if (line[0] != ' ') {
                                /* another match */
                                err = strv_extend(&match_list, line);
                                if (err < 0)
                                        return err;

                                break;
                        }

                        /* first data */
                        state = HW_DATA;
                        err = insert_data(trie, match_list, line, filename, file_priority, line_number, compat);
                        if (err < 0)
                                r = err;
                        break;

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

                        if (line[0] != ' ') {
                                r = log_syntax(NULL, LOG_WARNING, filename, line_number, SYNTHETIC_ERRNO(EINVAL),
                                               "Property or empty line expected, got \"%s\", ignoring record.", line);
                                state = HW_NONE;
                                match_list = strv_free(match_list);
                                break;
                        }

                        err = insert_data(trie, match_list, line, filename, file_priority, line_number, compat);
                        if (err < 0)
                                r = err;
                        break;
                };
        }

        if (state == HW_MATCH)
                log_syntax(NULL, LOG_WARNING, filename, line_number, 0,
                           "Property expected, ignoring record with no properties.");

        return r;
}

int hwdb_update(const char *root, const char *hwdb_bin_dir, bool strict, bool compat) {
        _cleanup_free_ char *hwdb_bin = NULL;
        _cleanup_(trie_freep) struct trie *trie = NULL;
        _cleanup_strv_free_ char **files = NULL;
        char **f;
        uint16_t file_priority = 1;
        int r = 0, err;

        /* The argument 'compat' controls the format version of database. If false, then hwdb.bin will be created with
         * additional information such that priority, line number, and filename of database source. If true, then hwdb.bin
         * will be created without the information. systemd-hwdb command should set the argument false, and 'udevadm hwdb'
         * command should set it true. */

        trie = new0(struct trie, 1);
        if (!trie)
                return -ENOMEM;

        /* string store */
        trie->strings = strbuf_new();
        if (!trie->strings)
                return -ENOMEM;

        /* index */
        trie->root = new0(struct trie_node, 1);
        if (!trie->root)
                return -ENOMEM;

        trie->nodes_count++;

        err = conf_files_list_strv(&files, ".hwdb", root, 0, conf_file_dirs);
        if (err < 0)
                return log_error_errno(err, "Failed to enumerate hwdb files: %m");

        STRV_FOREACH(f, files) {
                log_debug("Reading file \"%s\"", *f);
                err = import_file(trie, *f, file_priority++, compat);
                if (err < 0 && strict)
                        r = err;
        }

        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 = path_join(root, hwdb_bin_dir ?: default_hwdb_bin_dir, "hwdb.bin");
        if (!hwdb_bin)
                return -ENOMEM;

        mkdir_parents_label(hwdb_bin, 0755);
        err = trie_store(trie, hwdb_bin, compat);
        if (err < 0)
                return log_error_errno(err, "Failed to write database %s: %m", hwdb_bin);

        err = label_fix(hwdb_bin, 0);
        if (err < 0)
                return err;

        return r;
}

int hwdb_query(const char *modalias) {
        _cleanup_(sd_hwdb_unrefp) sd_hwdb *hwdb = NULL;
        const char *key, *value;
        int r;

        assert(modalias);

        r = sd_hwdb_new(&hwdb);
        if (r < 0)
                return r;

        SD_HWDB_FOREACH_PROPERTY(hwdb, modalias, key, value)
                printf("%s=%s\n", key, value);

        return 0;
}
Commit	Line	Data
6a34639e YW	1	/* SPDX-License-Identifier: LGPL-2.1+ */
	2
	3	#include <ctype.h>
d6609f82	4	#include <stdio.h>
ca78ad1d	5	#include <sys/stat.h>
6a34639e YW	6
	7	#include "alloc-util.h"
	8	#include "conf-files.h"
	9	#include "fd-util.h"
	10	#include "fileio.h"
	11	#include "fs-util.h"
	12	#include "hwdb-internal.h"
	13	#include "hwdb-util.h"
	14	#include "label.h"
	15	#include "mkdir.h"
	16	#include "path-util.h"
760877e9	17	#include "sort-util.h"
6a34639e YW	18	#include "strbuf.h"
	19	#include "string-util.h"
	20	#include "strv.h"
e4de7287	21	#include "tmpfile-util.h"
6a34639e YW	22
	23	static const char *default_hwdb_bin_dir = "/etc/udev";
	24	static const char * const conf_file_dirs[] = {
	25	"/etc/udev/hwdb.d",
	26	UDEVLIBEXECDIR "/hwdb.d",
	27	NULL
	28	};
	29
	30	/*
	31	* Generic udev properties, key-value database based on modalias strings.
	32	* Uses a Patricia/radix trie to index all matches for efficient lookup.
	33	*/
	34
	35	/* in-memory trie objects */
	36	struct trie {
	37	struct trie_node *root;
	38	struct strbuf *strings;
	39
	40	size_t nodes_count;
	41	size_t children_count;
	42	size_t values_count;
	43	};
	44
	45	struct trie_node {
	46	/* prefix, common part for all children of this node */
	47	size_t prefix_off;
	48
	49	/* sorted array of pointers to children nodes */
	50	struct trie_child_entry *children;
	51	uint8_t children_count;
	52
	53	/* sorted array of key-value pairs */
	54	struct trie_value_entry *values;
	55	size_t values_count;
	56	};
	57
	58	/* children array item with char (0-255) index */
	59	struct trie_child_entry {
	60	uint8_t c;
	61	struct trie_node *child;
	62	};
	63
	64	/* value array item with key-value pairs */
	65	struct trie_value_entry {
	66	size_t key_off;
	67	size_t value_off;
	68	size_t filename_off;
	69	uint32_t line_number;
	70	uint16_t file_priority;
	71	};
	72
	73	static int trie_children_cmp(const struct trie_child_entry a, const struct trie_child_entry b) {
	74	return CMP(a->c, b->c);
	75	}
	76
	77	static int node_add_child(struct trie trie, struct trie_node node, struct trie_node *node_child, uint8_t c) {
	78	struct trie_child_entry *child;
	79
	80	/* extend array, add new entry, sort for bisection */
	81	child = reallocarray(node->children, node->children_count + 1, sizeof(struct trie_child_entry));
	82	if (!child)
	83	return -ENOMEM;
	84
	85	node->children = child;
86	trie->children_count++;
87	node->children[node->children_count].c = c;
88	node->children[node->children_count].child = node_child;
89	node->children_count++;
90	typesafe_qsort(node->children, node->children_count, trie_children_cmp);
91	trie->nodes_count++;
92
93	return 0;
94	}
95
96	static struct trie_node node_lookup(const struct trie_node node, uint8_t c) {
97	struct trie_child_entry *child;
98	struct trie_child_entry search;
99
100	search.c = c;
101	child = typesafe_bsearch(&search, node->children, node->children_count, trie_children_cmp);
102	if (child)
103	return child->child;
104	return NULL;
105	}
106
107	static void trie_node_cleanup(struct trie_node *node) {
6a34639e YW	108	if (!node)
	109	return;
	110
327d8f3a	111	for (size_t i = 0; i < node->children_count; i++)
6a34639e YW	112	trie_node_cleanup(node->children[i].child);
	113	free(node->children);
	114	free(node->values);
	115	free(node);
	116	}
	117
	118	static void trie_free(struct trie *trie) {
	119	if (!trie)
	120	return;
	121
	122	trie_node_cleanup(trie->root);
	123	strbuf_cleanup(trie->strings);
	124	free(trie);
	125	}
	126
	127	DEFINE_TRIVIAL_CLEANUP_FUNC(struct trie*, trie_free);
	128
	129	static int trie_values_cmp(const struct trie_value_entry a, const struct trie_value_entry b, struct trie *trie) {
	130	return strcmp(trie->strings->buf + a->key_off,
	131	trie->strings->buf + b->key_off);
	132	}
	133
	134	static int trie_node_add_value(struct trie trie, struct trie_node node,
	135	const char key, const char value,
	136	const char *filename, uint16_t file_priority, uint32_t line_number, bool compat) {
80f1b344	137	ssize_t k, v, fn = 0;
6a34639e YW	138	struct trie_value_entry *val;
	139
	140	k = strbuf_add_string(trie->strings, key, strlen(key));
	141	if (k < 0)
	142	return k;
	143	v = strbuf_add_string(trie->strings, value, strlen(value));
	144	if (v < 0)
	145	return v;
	146
	147	if (!compat) {
	148	fn = strbuf_add_string(trie->strings, filename, strlen(filename));
	149	if (fn < 0)
	150	return fn;
	151	}
	152
	153	if (node->values_count) {
	154	struct trie_value_entry search = {
	155	.key_off = k,
	156	.value_off = v,
	157	};
	158
	159	val = typesafe_bsearch_r(&search, node->values, node->values_count, trie_values_cmp, trie);
	160	if (val) {
	161	/* At this point we have 2 identical properties on the same match-string.
	162	* Since we process files in order, we just replace the previous value. */
	163	val->value_off = v;
	164	val->filename_off = fn;
	165	val->file_priority = file_priority;
	166	val->line_number = line_number;
	167	return 0;
	168	}
	169	}
	170
	171	/* extend array, add new entry, sort for bisection */
	172	val = reallocarray(node->values, node->values_count + 1, sizeof(struct trie_value_entry));
	173	if (!val)
	174	return -ENOMEM;
	175	trie->values_count++;
	176	node->values = val;
e3b9fd0a YW	177	node->values[node->values_count] = (struct trie_value_entry) {
	178	.key_off = k,
	179	.value_off = v,
	180	.filename_off = fn,
	181	.file_priority = file_priority,
	182	.line_number = line_number,
	183	};
6a34639e YW	184	node->values_count++;
	185	typesafe_qsort_r(node->values, node->values_count, trie_values_cmp, trie);
	186	return 0;
	187	}
	188
	189	static int trie_insert(struct trie trie, struct trie_node node, const char *search,
	190	const char key, const char value,
	191	const char *filename, uint16_t file_priority, uint32_t line_number, bool compat) {
6a34639e YW	192	int r = 0;
6a34639e YW	193
327d8f3a	194	for (size_t i = 0;; i++) {
6a34639e YW	195	size_t p;
	196	uint8_t c;
	197	struct trie_node *child;
	198
	199	for (p = 0; (c = trie->strings->buf[node->prefix_off + p]); p++) {
	200	_cleanup_free_ struct trie_node *new_child = NULL;
	201	_cleanup_free_ char *s = NULL;
	202	ssize_t off;
	203
	204	if (c == search[i + p])
	205	continue;
	206
	207	/* split node */
e3b9fd0a	208	new_child = new(struct trie_node, 1);
6a34639e YW	209	if (!new_child)
	210	return -ENOMEM;
	211
	212	/* move values from parent to child */
e3b9fd0a YW	213	*new_child = (struct trie_node) {
	214	.prefix_off = node->prefix_off + p+1,
	215	.children = node->children,
	216	.children_count = node->children_count,
	217	.values = node->values,
	218	.values_count = node->values_count,
	219	};
6a34639e YW	220
	221	/* update parent; use strdup() because the source gets realloc()d */
	222	s = strndup(trie->strings->buf + node->prefix_off, p);
	223	if (!s)
	224	return -ENOMEM;
	225
	226	off = strbuf_add_string(trie->strings, s, p);
	227	if (off < 0)
	228	return off;
	229
e3b9fd0a YW	230	*node = (struct trie_node) {
	231	.prefix_off = off,
	232	};
6a34639e YW	233	r = node_add_child(trie, node, new_child, c);
	234	if (r < 0)
	235	return r;
	236
	237	new_child = NULL; /* avoid cleanup */
	238	break;
	239	}
	240	i += p;
	241
	242	c = search[i];
	243	if (c == '\0')
	244	return trie_node_add_value(trie, node, key, value, filename, file_priority, line_number, compat);
	245
	246	child = node_lookup(node, c);
	247	if (!child) {
	248	_cleanup_free_ struct trie_node *new_child = NULL;
	249	ssize_t off;
	250
	251	/* new child */
e3b9fd0a	252	new_child = new(struct trie_node, 1);
6a34639e YW	253	if (!new_child)
	254	return -ENOMEM;
	255
	256	off = strbuf_add_string(trie->strings, search + i+1, strlen(search + i+1));
	257	if (off < 0)
	258	return off;
	259
e3b9fd0a YW	260	*new_child = (struct trie_node) {
	261	.prefix_off = off,
	262	};
	263
6a34639e YW	264	r = node_add_child(trie, node, new_child, c);
	265	if (r < 0)
	266	return r;
	267
	268	child = TAKE_PTR(new_child);
	269	return trie_node_add_value(trie, child, key, value, filename, file_priority, line_number, compat);
	270	}
	271
	272	node = child;
6a34639e YW	273	}
	274	}
	275
	276	struct trie_f {
	277	FILE *f;
	278	struct trie *trie;
	279	uint64_t strings_off;
	280
	281	uint64_t nodes_count;
	282	uint64_t children_count;
	283	uint64_t values_count;
	284	};
	285
	286	/* calculate the storage space for the nodes, children arrays, value arrays */
	287	static void trie_store_nodes_size(struct trie_f trie, struct trie_node node, bool compat) {
327d8f3a	288	for (uint64_t i = 0; i < node->children_count; i++)
6a34639e YW	289	trie_store_nodes_size(trie, node->children[i].child, compat);
	290
	291	trie->strings_off += sizeof(struct trie_node_f);
327d8f3a	292	for (uint64_t i = 0; i < node->children_count; i++)
6a34639e	293	trie->strings_off += sizeof(struct trie_child_entry_f);
327d8f3a	294	for (uint64_t i = 0; i < node->values_count; i++)
6a34639e YW	295	trie->strings_off += compat ? sizeof(struct trie_value_entry_f) : sizeof(struct trie_value_entry2_f);
	296	}
	297
	298	static int64_t trie_store_nodes(struct trie_f trie, struct trie_node node, bool compat) {
6a34639e YW	299	struct trie_node_f n = {
	300	.prefix_off = htole64(trie->strings_off + node->prefix_off),
	301	.children_count = node->children_count,
	302	.values_count = htole64(node->values_count),
	303	};
	304	_cleanup_free_ struct trie_child_entry_f *children = NULL;
	305	int64_t node_off;
	306
	307	if (node->children_count) {
	308	children = new(struct trie_child_entry_f, node->children_count);
	309	if (!children)
	310	return -ENOMEM;
	311	}
	312
	313	/* post-order recursion */
327d8f3a	314	for (uint64_t i = 0; i < node->children_count; i++) {
6a34639e YW	315	int64_t child_off;
	316
	317	child_off = trie_store_nodes(trie, node->children[i].child, compat);
	318	if (child_off < 0)
	319	return child_off;
	320
	321	children[i] = (struct trie_child_entry_f) {
	322	.c = node->children[i].c,
	323	.child_off = htole64(child_off),
	324	};
	325	}
	326
	327	/* write node */
	328	node_off = ftello(trie->f);
	329	fwrite(&n, sizeof(struct trie_node_f), 1, trie->f);
	330	trie->nodes_count++;
	331
	332	/* append children array */
	333	if (node->children_count) {
	334	fwrite(children, sizeof(struct trie_child_entry_f), node->children_count, trie->f);
	335	trie->children_count += node->children_count;
	336	}
	337
	338	/* append values array */
327d8f3a	339	for (uint64_t i = 0; i < node->values_count; i++) {
6a34639e YW	340	struct trie_value_entry2_f v = {
	341	.key_off = htole64(trie->strings_off + node->values[i].key_off),
	342	.value_off = htole64(trie->strings_off + node->values[i].value_off),
	343	.filename_off = htole64(trie->strings_off + node->values[i].filename_off),
	344	.line_number = htole32(node->values[i].line_number),
	345	.file_priority = htole16(node->values[i].file_priority),
	346	};
	347
	348	fwrite(&v, compat ? sizeof(struct trie_value_entry_f) : sizeof(struct trie_value_entry2_f), 1, trie->f);
	349	}
	350	trie->values_count += node->values_count;
	351
	352	return node_off;
	353	}
	354
	355	static int trie_store(struct trie trie, const char filename, bool compat) {
	356	struct trie_f t = {
	357	.trie = trie,
	358	};
	359	_cleanup_free_ char *filename_tmp = NULL;
	360	int64_t pos;
	361	int64_t root_off;
	362	int64_t size;
	363	struct trie_header_f h = {
	364	.signature = HWDB_SIG,
a67c318d	365	.tool_version = htole64(PROJECT_VERSION),
6a34639e YW	366	.header_size = htole64(sizeof(struct trie_header_f)),
	367	.node_size = htole64(sizeof(struct trie_node_f)),
	368	.child_entry_size = htole64(sizeof(struct trie_child_entry_f)),
	369	.value_entry_size = htole64(compat ? sizeof(struct trie_value_entry_f) : sizeof(struct trie_value_entry2_f)),
	370	};
	371	int r;
	372
	373	/* calculate size of header, nodes, children entries, value entries */
	374	t.strings_off = sizeof(struct trie_header_f);
	375	trie_store_nodes_size(&t, trie->root, compat);
	376
	377	r = fopen_temporary(filename, &t.f, &filename_tmp);
	378	if (r < 0)
	379	return r;
	380	fchmod(fileno(t.f), 0444);
	381
	382	/* write nodes */
	383	if (fseeko(t.f, sizeof(struct trie_header_f), SEEK_SET) < 0)
	384	goto error_fclose;
	385
	386	root_off = trie_store_nodes(&t, trie->root, compat);
	387	h.nodes_root_off = htole64(root_off);
	388	pos = ftello(t.f);
	389	h.nodes_len = htole64(pos - sizeof(struct trie_header_f));
	390
	391	/* write string buffer */
	392	fwrite(trie->strings->buf, trie->strings->len, 1, t.f);
	393	h.strings_len = htole64(trie->strings->len);
	394
	395	/* write header */
	396	size = ftello(t.f);
	397	h.file_size = htole64(size);
	398	if (fseeko(t.f, 0, SEEK_SET) < 0)
	399	goto error_fclose;
	400	fwrite(&h, sizeof(struct trie_header_f), 1, t.f);
	401
	402	if (ferror(t.f))
	403	goto error_fclose;
	404	if (fflush(t.f) < 0)
	405	goto error_fclose;
	406	if (fsync(fileno(t.f)) < 0)
	407	goto error_fclose;
	408	if (rename(filename_tmp, filename) < 0)
	409	goto error_fclose;
	410
	411	/* write succeeded */
	412	fclose(t.f);
	413
	414	log_debug("=== trie on-disk ===");
	415	log_debug("size: %8"PRIi64" bytes", size);
	416	log_debug("header: %8zu bytes", sizeof(struct trie_header_f));
	417	log_debug("nodes: %8"PRIu64" bytes (%8"PRIu64")",
	418	t.nodes_count * sizeof(struct trie_node_f), t.nodes_count);
	419	log_debug("child pointers: %8"PRIu64" bytes (%8"PRIu64")",
	420	t.children_count * sizeof(struct trie_child_entry_f), t.children_count);
	421	log_debug("value pointers: %8"PRIu64" bytes (%8"PRIu64")",
	422	t.values_count * (compat ? sizeof(struct trie_value_entry_f) : sizeof(struct trie_value_entry2_f)), t.values_count);
	423	log_debug("string store: %8zu bytes", trie->strings->len);
	424	log_debug("strings start: %8"PRIu64, t.strings_off);
	425	return 0;
	426
	427	error_fclose:
	428	r = -errno;
	429	fclose(t.f);
6990fb6b	430	(void) unlink(filename_tmp);
6a34639e YW	431	return r;
	432	}
	433
	434	static int insert_data(struct trie trie, char match_list, char line, const char *filename,
	435	uint16_t file_priority, uint32_t line_number, bool compat) {
	436	char value, *entry;
	437
	438	assert(line[0] == ' ');
	439
	440	value = strchr(line, '=');
	441	if (!value)
d6bd2bb4	442	return log_syntax(NULL, LOG_WARNING, filename, line_number, SYNTHETIC_ERRNO(EINVAL),
327d8f3a	443	"Key-value pair expected but got \"%s\", ignoring.", line);
6a34639e YW	444
	445	value[0] = '\0';
	446	value++;
	447
	448	/* Replace multiple leading spaces by a single space */
	449	while (isblank(line[0]) && isblank(line[1]))
	450	line++;
	451
afe87974	452	if (isempty(line + 1))
d6bd2bb4	453	return log_syntax(NULL, LOG_WARNING, filename, line_number, SYNTHETIC_ERRNO(EINVAL),
327d8f3a	454	"Empty key in \"%s=%s\", ignoring.",
6a34639e YW	455	line, value);
	456
	457	STRV_FOREACH(entry, match_list)
	458	trie_insert(trie, trie->root, *entry, line, value, filename, file_priority, line_number, compat);
	459
	460	return 0;
	461	}
	462
	463	static int import_file(struct trie trie, const char filename, uint16_t file_priority, bool compat) {
	464	enum {
	465	HW_NONE,
	466	HW_MATCH,
	467	HW_DATA,
	468	} state = HW_NONE;
	469	_cleanup_fclose_ FILE *f = NULL;
6a34639e YW	470	_cleanup_strv_free_ char **match_list = NULL;
6a34639e YW	471	uint32_t line_number = 0;
6d95e7d9	472	int r, err;
6a34639e YW	473
	474	f = fopen(filename, "re");
	475	if (!f)
	476	return -errno;
	477
32d621e4 LP	478	for (;;) {
32d621e4 LP	479	_cleanup_free_ char *line = NULL;
6a34639e YW	480	size_t len;
	481	char *pos;
	482
648ba0ee	483	r = read_line_full(f, LONG_LINE_MAX, READ_LINE_NOT_A_TTY, &line);
32d621e4 LP	484	if (r < 0)
	485	return r;
	486	if (r == 0)
	487	break;
	488
327d8f3a	489	line_number ++;
6a34639e YW	490
	491	/* comment line */
	492	if (line[0] == '#')
	493	continue;
	494
	495	/* strip trailing comment */
	496	pos = strchr(line, '#');
	497	if (pos)
	498	pos[0] = '\0';
	499
	500	/* strip trailing whitespace */
	501	len = strlen(line);
	502	while (len > 0 && isspace(line[len-1]))
	503	len--;
	504	line[len] = '\0';
	505
	506	switch (state) {
	507	case HW_NONE:
	508	if (len == 0)
	509	break;
	510
	511	if (line[0] == ' ') {
d6bd2bb4	512	r = log_syntax(NULL, LOG_WARNING, filename, line_number, SYNTHETIC_ERRNO(EINVAL),
327d8f3a	513	"Match expected but got indented property \"%s\", ignoring line.", line);
6a34639e YW	514	break;
	515	}
	516
	517	/* start of record, first match */
	518	state = HW_MATCH;
	519
2aecc668	520	err = strv_extend(&match_list, line);
6a34639e YW	521	if (err < 0)
	522	return err;
	523
	524	break;
	525
	526	case HW_MATCH:
	527	if (len == 0) {
d6bd2bb4	528	r = log_syntax(NULL, LOG_WARNING, filename, line_number, SYNTHETIC_ERRNO(EINVAL),
327d8f3a	529	"Property expected, ignoring record with no properties.");
6a34639e	530	state = HW_NONE;
2e5180d3	531	match_list = strv_free(match_list);
6a34639e YW	532	break;
	533	}
	534
	535	if (line[0] != ' ') {
	536	/* another match */
2aecc668	537	err = strv_extend(&match_list, line);
6a34639e YW	538	if (err < 0)
	539	return err;
	540
	541	break;
	542	}
	543
	544	/* first data */
	545	state = HW_DATA;
	546	err = insert_data(trie, match_list, line, filename, file_priority, line_number, compat);
	547	if (err < 0)
	548	r = err;
	549	break;
	550
	551	case HW_DATA:
	552	if (len == 0) {
	553	/* end of record */
	554	state = HW_NONE;
2e5180d3	555	match_list = strv_free(match_list);
6a34639e YW	556	break;
	557	}
	558
	559	if (line[0] != ' ') {
d6bd2bb4	560	r = log_syntax(NULL, LOG_WARNING, filename, line_number, SYNTHETIC_ERRNO(EINVAL),
327d8f3a	561	"Property or empty line expected, got \"%s\", ignoring record.", line);
6a34639e	562	state = HW_NONE;
2e5180d3	563	match_list = strv_free(match_list);
6a34639e YW	564	break;
	565	}
	566
	567	err = insert_data(trie, match_list, line, filename, file_priority, line_number, compat);
	568	if (err < 0)
	569	r = err;
	570	break;
	571	};
	572	}
	573
	574	if (state == HW_MATCH)
d6bd2bb4	575	log_syntax(NULL, LOG_WARNING, filename, line_number, 0,
327d8f3a	576	"Property expected, ignoring record with no properties.");
6a34639e YW	577
	578	return r;
	579	}
	580
	581	int hwdb_update(const char root, const char hwdb_bin_dir, bool strict, bool compat) {
	582	_cleanup_free_ char *hwdb_bin = NULL;
	583	_cleanup_(trie_freep) struct trie *trie = NULL;
	584	_cleanup_strv_free_ char **files = NULL;
	585	char **f;
	586	uint16_t file_priority = 1;
	587	int r = 0, err;
	588
	589	/* The argument 'compat' controls the format version of database. If false, then hwdb.bin will be created with
	590	* additional information such that priority, line number, and filename of database source. If true, then hwdb.bin
	591	* will be created without the information. systemd-hwdb command should set the argument false, and 'udevadm hwdb'
	592	* command should set it true. */
	593
	594	trie = new0(struct trie, 1);
	595	if (!trie)
	596	return -ENOMEM;
	597
	598	/* string store */
	599	trie->strings = strbuf_new();
	600	if (!trie->strings)
	601	return -ENOMEM;
	602
	603	/* index */
	604	trie->root = new0(struct trie_node, 1);
	605	if (!trie->root)
	606	return -ENOMEM;
	607
	608	trie->nodes_count++;
	609
	610	err = conf_files_list_strv(&files, ".hwdb", root, 0, conf_file_dirs);
	611	if (err < 0)
	612	return log_error_errno(err, "Failed to enumerate hwdb files: %m");
	613
	614	STRV_FOREACH(f, files) {
	615	log_debug("Reading file \"%s\"", *f);
	616	err = import_file(trie, *f, file_priority++, compat);
	617	if (err < 0 && strict)
	618	r = err;
	619	}
	620
	621	strbuf_complete(trie->strings);
	622
	623	log_debug("=== trie in-memory ===");
	624	log_debug("nodes: %8zu bytes (%8zu)",
	625	trie->nodes_count * sizeof(struct trie_node), trie->nodes_count);
	626	log_debug("children arrays: %8zu bytes (%8zu)",
	627	trie->children_count * sizeof(struct trie_child_entry), trie->children_count);
	628	log_debug("values arrays: %8zu bytes (%8zu)",
	629	trie->values_count * sizeof(struct trie_value_entry), trie->values_count);
	630	log_debug("strings: %8zu bytes",
	631	trie->strings->len);
	632	log_debug("strings incoming: %8zu bytes (%8zu)",
	633	trie->strings->in_len, trie->strings->in_count);
	634	log_debug("strings dedup'ed: %8zu bytes (%8zu)",
	635	trie->strings->dedup_len, trie->strings->dedup_count);
	636
	637	hwdb_bin = path_join(root, hwdb_bin_dir ?: default_hwdb_bin_dir, "hwdb.bin");
	638	if (!hwdb_bin)
	639	return -ENOMEM;
	640
641	mkdir_parents_label(hwdb_bin, 0755);
642	err = trie_store(trie, hwdb_bin, compat);
643	if (err < 0)
644	return log_error_errno(err, "Failed to write database %s: %m", hwdb_bin);
645
646	err = label_fix(hwdb_bin, 0);
647	if (err < 0)
648	return err;
649
650	return r;
651	}
d6609f82 YW	652
	653	int hwdb_query(const char *modalias) {
	654	_cleanup_(sd_hwdb_unrefp) sd_hwdb *hwdb = NULL;
	655	const char key, value;
	656	int r;
	657
	658	assert(modalias);
	659
	660	r = sd_hwdb_new(&hwdb);
	661	if (r < 0)
	662	return r;
	663
	664	SD_HWDB_FOREACH_PROPERTY(hwdb, modalias, key, value)
	665	printf("%s=%s\n", key, value);
	666
	667	return 0;
	668	}