diff options
Diffstat (limited to 'src/libsystemd/sd-hwdb')
| -rw-r--r-- | src/libsystemd/sd-hwdb/hwdb-internal.h | 65 | ||||
| -rw-r--r-- | src/libsystemd/sd-hwdb/hwdb-util.c | 686 | ||||
| -rw-r--r-- | src/libsystemd/sd-hwdb/hwdb-util.h | 10 | ||||
| -rw-r--r-- | src/libsystemd/sd-hwdb/sd-hwdb.c | 468 |
4 files changed, 1229 insertions, 0 deletions
diff --git a/src/libsystemd/sd-hwdb/hwdb-internal.h b/src/libsystemd/sd-hwdb/hwdb-internal.h new file mode 100644 index 0000000..d82b8c1 --- /dev/null +++ b/src/libsystemd/sd-hwdb/hwdb-internal.h @@ -0,0 +1,65 @@ +/* SPDX-License-Identifier: LGPL-2.1+ */ +#pragma once + +#include <stdint.h> + +#include "sparse-endian.h" + +#define HWDB_SIG { 'K', 'S', 'L', 'P', 'H', 'H', 'R', 'H' } + +/* on-disk trie objects */ +struct trie_header_f { + uint8_t signature[8]; + + /* version of tool which created the file */ + le64_t tool_version; + le64_t file_size; + + /* size of structures to allow them to grow */ + le64_t header_size; + le64_t node_size; + le64_t child_entry_size; + le64_t value_entry_size; + + /* offset of the root trie node */ + le64_t nodes_root_off; + + /* size of the nodes and string section */ + le64_t nodes_len; + le64_t strings_len; +} _packed_; + +struct trie_node_f { + /* prefix of lookup string, shared by all children */ + le64_t prefix_off; + /* size of children entry array appended to the node */ + uint8_t children_count; + uint8_t padding[7]; + /* size of value entry array appended to the node */ + le64_t values_count; +} _packed_; + +/* array of child entries, follows directly the node record */ +struct trie_child_entry_f { + /* index of the child node */ + uint8_t c; + uint8_t padding[7]; + /* offset of the child node */ + le64_t child_off; +} _packed_; + +/* array of value entries, follows directly the node record/child array */ +struct trie_value_entry_f { + le64_t key_off; + le64_t value_off; +} _packed_; + +/* v2 extends v1 with filename and line-number */ +struct trie_value_entry2_f { + le64_t key_off; + le64_t value_off; + le64_t filename_off; + le32_t line_number; + le16_t file_priority; + le16_t padding; +} _packed_; diff --git a/src/libsystemd/sd-hwdb/hwdb-util.c b/src/libsystemd/sd-hwdb/hwdb-util.c new file mode 100644 index 0000000..f852967 --- /dev/null +++ b/src/libsystemd/sd-hwdb/hwdb-util.c @@ -0,0 +1,686 @@ +/* SPDX-License-Identifier: LGPL-2.1+ */ + +#include <ctype.h> +#include <stdio.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 "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) { + size_t i; + + if (!node) + return; + + for (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) { + size_t i = 0; + int r = 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_ 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; + 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, bool compat) { + uint64_t i; + + for (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 (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 += 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) { + 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), + }; + _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 (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 (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); + 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, 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) || isempty(value)) + return log_syntax(NULL, LOG_WARNING, filename, line_number, EINVAL, + "Empty %s in \"%s=%s\", ignoring", + isempty(line + 1) ? "key" : "value", + 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; + char *match = NULL; + int r = 0, err; + + f = fopen(filename, "re"); + if (!f) + return -errno; + + for (;;) { + _cleanup_free_ char *line = NULL; + size_t len; + char *pos; + + r = read_line(f, LONG_LINE_MAX, &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] == ' ') { + log_syntax(NULL, LOG_WARNING, filename, line_number, EINVAL, + "Match expected but got indented property \"%s\", ignoring line", line); + r = -EINVAL; + break; + } + + /* start of record, first match */ + state = HW_MATCH; + + match = strdup(line); + if (!match) + return -ENOMEM; + + err = strv_consume(&match_list, match); + if (err < 0) + return err; + + break; + + case HW_MATCH: + if (len == 0) { + log_syntax(NULL, LOG_WARNING, filename, line_number, EINVAL, + "Property expected, ignoring record with no properties"); + r = -EINVAL; + state = HW_NONE; + strv_clear(match_list); + break; + } + + if (line[0] != ' ') { + /* another match */ + match = strdup(line); + if (!match) + return -ENOMEM; + + err = strv_consume(&match_list, match); + 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; + strv_clear(match_list); + break; + } + + if (line[0] != ' ') { + log_syntax(NULL, LOG_WARNING, filename, line_number, EINVAL, + "Property or empty line expected, got \"%s\", ignoring record", line); + r = -EINVAL; + state = HW_NONE; + strv_clear(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, EINVAL, + "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; +} diff --git a/src/libsystemd/sd-hwdb/hwdb-util.h b/src/libsystemd/sd-hwdb/hwdb-util.h new file mode 100644 index 0000000..425b4b3 --- /dev/null +++ b/src/libsystemd/sd-hwdb/hwdb-util.h @@ -0,0 +1,10 @@ +/* SPDX-License-Identifier: LGPL-2.1+ */ +#pragma once + +#include <stdbool.h> + +#include "sd-hwdb.h" + +bool hwdb_validate(sd_hwdb *hwdb); +int hwdb_update(const char *root, const char *hwdb_bin_dir, bool strict, bool compat); +int hwdb_query(const char *modalias); diff --git a/src/libsystemd/sd-hwdb/sd-hwdb.c b/src/libsystemd/sd-hwdb/sd-hwdb.c new file mode 100644 index 0000000..233944c --- /dev/null +++ b/src/libsystemd/sd-hwdb/sd-hwdb.c @@ -0,0 +1,468 @@ +/* SPDX-License-Identifier: LGPL-2.1+ */ +/*** + Copyright © 2008 Alan Jenkins <alan.christopher.jenkins@googlemail.com> +***/ + +#include <errno.h> +#include <fnmatch.h> +#include <inttypes.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <sys/mman.h> + +#include "sd-hwdb.h" + +#include "alloc-util.h" +#include "fd-util.h" +#include "hashmap.h" +#include "hwdb-internal.h" +#include "hwdb-util.h" +#include "refcnt.h" +#include "string-util.h" +#include "util.h" + +struct sd_hwdb { + RefCount n_ref; + + FILE *f; + struct stat st; + union { + struct trie_header_f *head; + const char *map; + }; + + OrderedHashmap *properties; + Iterator properties_iterator; + bool properties_modified; +}; + +struct linebuf { + char bytes[LINE_MAX]; + size_t size; + size_t len; +}; + +static void linebuf_init(struct linebuf *buf) { + buf->size = 0; + buf->len = 0; +} + +static const char *linebuf_get(struct linebuf *buf) { + if (buf->len + 1 >= sizeof(buf->bytes)) + return NULL; + buf->bytes[buf->len] = '\0'; + return buf->bytes; +} + +static bool linebuf_add(struct linebuf *buf, const char *s, size_t len) { + if (buf->len + len >= sizeof(buf->bytes)) + return false; + memcpy(buf->bytes + buf->len, s, len); + buf->len += len; + return true; +} + +static bool linebuf_add_char(struct linebuf *buf, char c) { + if (buf->len + 1 >= sizeof(buf->bytes)) + return false; + buf->bytes[buf->len++] = c; + return true; +} + +static void linebuf_rem(struct linebuf *buf, size_t count) { + assert(buf->len >= count); + buf->len -= count; +} + +static void linebuf_rem_char(struct linebuf *buf) { + linebuf_rem(buf, 1); +} + +static const struct trie_child_entry_f *trie_node_child(sd_hwdb *hwdb, const struct trie_node_f *node, size_t idx) { + const char *base = (const char *)node; + + base += le64toh(hwdb->head->node_size); + base += idx * le64toh(hwdb->head->child_entry_size); + return (const struct trie_child_entry_f *)base; +} + +static const struct trie_value_entry_f *trie_node_value(sd_hwdb *hwdb, const struct trie_node_f *node, size_t idx) { + const char *base = (const char *)node; + + base += le64toh(hwdb->head->node_size); + base += node->children_count * le64toh(hwdb->head->child_entry_size); + base += idx * le64toh(hwdb->head->value_entry_size); + return (const struct trie_value_entry_f *)base; +} + +static const struct trie_node_f *trie_node_from_off(sd_hwdb *hwdb, le64_t off) { + return (const struct trie_node_f *)(hwdb->map + le64toh(off)); +} + +static const char *trie_string(sd_hwdb *hwdb, le64_t off) { + return hwdb->map + le64toh(off); +} + +static int trie_children_cmp_f(const void *v1, const void *v2) { + const struct trie_child_entry_f *n1 = v1; + const struct trie_child_entry_f *n2 = v2; + + return n1->c - n2->c; +} + +static const struct trie_node_f *node_lookup_f(sd_hwdb *hwdb, const struct trie_node_f *node, uint8_t c) { + struct trie_child_entry_f *child; + struct trie_child_entry_f search; + + search.c = c; + child = bsearch(&search, (const char *)node + le64toh(hwdb->head->node_size), node->children_count, + le64toh(hwdb->head->child_entry_size), trie_children_cmp_f); + if (child) + return trie_node_from_off(hwdb, child->child_off); + return NULL; +} + +static int hwdb_add_property(sd_hwdb *hwdb, const struct trie_value_entry_f *entry) { + const char *key; + int r; + + assert(hwdb); + + key = trie_string(hwdb, entry->key_off); + + /* + * Silently ignore all properties which do not start with a + * space; future extensions might use additional prefixes. + */ + if (key[0] != ' ') + return 0; + + key++; + + if (le64toh(hwdb->head->value_entry_size) >= sizeof(struct trie_value_entry2_f)) { + const struct trie_value_entry2_f *old, *entry2; + + entry2 = (const struct trie_value_entry2_f *)entry; + old = ordered_hashmap_get(hwdb->properties, key); + if (old) { + /* On duplicates, we order by filename priority and line-number. + * + * v2 of the format had 64 bits for the line number. + * v3 reuses top 32 bits of line_number to store the priority. + * We check the top bits — if they are zero we have v2 format. + * This means that v2 clients will print wrong line numbers with + * v3 data. + * + * For v3 data: we compare the priority (of the source file) + * and the line number. + * + * For v2 data: we rely on the fact that the filenames in the hwdb + * are added in the order of priority (higher later), because they + * are *processed* in the order of priority. So we compare the + * indices to determine which file had higher priority. Comparing + * the strings alphabetically would be useless, because those are + * full paths, and e.g. /usr/lib would sort after /etc, even + * though it has lower priority. This is not reliable because of + * suffix compression, but should work for the most common case of + * /usr/lib/udev/hwbd.d and /etc/udev/hwdb.d, and is better than + * not doing the comparison at all. + */ + bool lower; + + if (entry2->file_priority == 0) + lower = entry2->filename_off < old->filename_off || + (entry2->filename_off == old->filename_off && entry2->line_number < old->line_number); + else + lower = entry2->file_priority < old->file_priority || + (entry2->file_priority == old->file_priority && entry2->line_number < old->line_number); + if (lower) + return 0; + } + } + + r = ordered_hashmap_ensure_allocated(&hwdb->properties, &string_hash_ops); + if (r < 0) + return r; + + r = ordered_hashmap_replace(hwdb->properties, key, (void *)entry); + if (r < 0) + return r; + + hwdb->properties_modified = true; + + return 0; +} + +static int trie_fnmatch_f(sd_hwdb *hwdb, const struct trie_node_f *node, size_t p, + struct linebuf *buf, const char *search) { + size_t len; + size_t i; + const char *prefix; + int err; + + prefix = trie_string(hwdb, node->prefix_off); + len = strlen(prefix + p); + linebuf_add(buf, prefix + p, len); + + for (i = 0; i < node->children_count; i++) { + const struct trie_child_entry_f *child = trie_node_child(hwdb, node, i); + + linebuf_add_char(buf, child->c); + err = trie_fnmatch_f(hwdb, trie_node_from_off(hwdb, child->child_off), 0, buf, search); + if (err < 0) + return err; + linebuf_rem_char(buf); + } + + if (le64toh(node->values_count) && fnmatch(linebuf_get(buf), search, 0) == 0) + for (i = 0; i < le64toh(node->values_count); i++) { + err = hwdb_add_property(hwdb, trie_node_value(hwdb, node, i)); + if (err < 0) + return err; + } + + linebuf_rem(buf, len); + return 0; +} + +static int trie_search_f(sd_hwdb *hwdb, const char *search) { + struct linebuf buf; + const struct trie_node_f *node; + size_t i = 0; + int err; + + linebuf_init(&buf); + + node = trie_node_from_off(hwdb, hwdb->head->nodes_root_off); + while (node) { + const struct trie_node_f *child; + size_t p = 0; + + if (node->prefix_off) { + char c; + + for (; (c = trie_string(hwdb, node->prefix_off)[p]); p++) { + if (IN_SET(c, '*', '?', '[')) + return trie_fnmatch_f(hwdb, node, p, &buf, search + i + p); + if (c != search[i + p]) + return 0; + } + i += p; + } + + child = node_lookup_f(hwdb, node, '*'); + if (child) { + linebuf_add_char(&buf, '*'); + err = trie_fnmatch_f(hwdb, child, 0, &buf, search + i); + if (err < 0) + return err; + linebuf_rem_char(&buf); + } + + child = node_lookup_f(hwdb, node, '?'); + if (child) { + linebuf_add_char(&buf, '?'); + err = trie_fnmatch_f(hwdb, child, 0, &buf, search + i); + if (err < 0) + return err; + linebuf_rem_char(&buf); + } + + child = node_lookup_f(hwdb, node, '['); + if (child) { + linebuf_add_char(&buf, '['); + err = trie_fnmatch_f(hwdb, child, 0, &buf, search + i); + if (err < 0) + return err; + linebuf_rem_char(&buf); + } + + if (search[i] == '\0') { + size_t n; + + for (n = 0; n < le64toh(node->values_count); n++) { + err = hwdb_add_property(hwdb, trie_node_value(hwdb, node, n)); + if (err < 0) + return err; + } + return 0; + } + + child = node_lookup_f(hwdb, node, search[i]); + node = child; + i++; + } + return 0; +} + +static const char hwdb_bin_paths[] = + "/etc/systemd/hwdb/hwdb.bin\0" + "/etc/udev/hwdb.bin\0" + "/usr/lib/systemd/hwdb/hwdb.bin\0" +#if HAVE_SPLIT_USR + "/lib/systemd/hwdb/hwdb.bin\0" +#endif + UDEVLIBEXECDIR "/hwdb.bin\0"; + +_public_ int sd_hwdb_new(sd_hwdb **ret) { + _cleanup_(sd_hwdb_unrefp) sd_hwdb *hwdb = NULL; + const char *hwdb_bin_path; + const char sig[] = HWDB_SIG; + + assert_return(ret, -EINVAL); + + hwdb = new0(sd_hwdb, 1); + if (!hwdb) + return -ENOMEM; + + hwdb->n_ref = REFCNT_INIT; + + /* find hwdb.bin in hwdb_bin_paths */ + NULSTR_FOREACH(hwdb_bin_path, hwdb_bin_paths) { + hwdb->f = fopen(hwdb_bin_path, "re"); + if (hwdb->f) + break; + else if (errno == ENOENT) + continue; + else + return log_debug_errno(errno, "Failed to open %s: %m", hwdb_bin_path); + } + + if (!hwdb->f) { + log_debug("hwdb.bin does not exist, please run 'systemd-hwdb update'"); + return -ENOENT; + } + + if (fstat(fileno(hwdb->f), &hwdb->st) < 0 || + (size_t) hwdb->st.st_size < offsetof(struct trie_header_f, strings_len) + 8) + return log_debug_errno(errno, "Failed to read %s: %m", hwdb_bin_path); + + hwdb->map = mmap(0, hwdb->st.st_size, PROT_READ, MAP_SHARED, fileno(hwdb->f), 0); + if (hwdb->map == MAP_FAILED) + return log_debug_errno(errno, "Failed to map %s: %m", hwdb_bin_path); + + if (memcmp(hwdb->map, sig, sizeof(hwdb->head->signature)) != 0 || + (size_t) hwdb->st.st_size != le64toh(hwdb->head->file_size)) { + log_debug("Failed to recognize the format of %s", hwdb_bin_path); + return -EINVAL; + } + + log_debug("=== trie on-disk ==="); + log_debug("tool version: %"PRIu64, le64toh(hwdb->head->tool_version)); + log_debug("file size: %8"PRIi64" bytes", hwdb->st.st_size); + log_debug("header size %8"PRIu64" bytes", le64toh(hwdb->head->header_size)); + log_debug("strings %8"PRIu64" bytes", le64toh(hwdb->head->strings_len)); + log_debug("nodes %8"PRIu64" bytes", le64toh(hwdb->head->nodes_len)); + + *ret = TAKE_PTR(hwdb); + + return 0; +} + +static sd_hwdb *hwdb_free(sd_hwdb *hwdb) { + assert(hwdb); + + if (hwdb->map) + munmap((void *)hwdb->map, hwdb->st.st_size); + safe_fclose(hwdb->f); + ordered_hashmap_free(hwdb->properties); + return mfree(hwdb); +} + +DEFINE_PUBLIC_ATOMIC_REF_UNREF_FUNC(sd_hwdb, sd_hwdb, hwdb_free) + +bool hwdb_validate(sd_hwdb *hwdb) { + bool found = false; + const char* p; + struct stat st; + + if (!hwdb) + return false; + if (!hwdb->f) + return false; + + /* if hwdb.bin doesn't exist anywhere, we need to update */ + NULSTR_FOREACH(p, hwdb_bin_paths) { + if (stat(p, &st) >= 0) { + found = true; + break; + } + } + if (!found) + return true; + + if (timespec_load(&hwdb->st.st_mtim) != timespec_load(&st.st_mtim)) + return true; + return false; +} + +static int properties_prepare(sd_hwdb *hwdb, const char *modalias) { + assert(hwdb); + assert(modalias); + + ordered_hashmap_clear(hwdb->properties); + hwdb->properties_modified = true; + + return trie_search_f(hwdb, modalias); +} + +_public_ int sd_hwdb_get(sd_hwdb *hwdb, const char *modalias, const char *key, const char **_value) { + const struct trie_value_entry_f *entry; + int r; + + assert_return(hwdb, -EINVAL); + assert_return(hwdb->f, -EINVAL); + assert_return(modalias, -EINVAL); + assert_return(_value, -EINVAL); + + r = properties_prepare(hwdb, modalias); + if (r < 0) + return r; + + entry = ordered_hashmap_get(hwdb->properties, key); + if (!entry) + return -ENOENT; + + *_value = trie_string(hwdb, entry->value_off); + + return 0; +} + +_public_ int sd_hwdb_seek(sd_hwdb *hwdb, const char *modalias) { + int r; + + assert_return(hwdb, -EINVAL); + assert_return(hwdb->f, -EINVAL); + assert_return(modalias, -EINVAL); + + r = properties_prepare(hwdb, modalias); + if (r < 0) + return r; + + hwdb->properties_modified = false; + hwdb->properties_iterator = ITERATOR_FIRST; + + return 0; +} + +_public_ int sd_hwdb_enumerate(sd_hwdb *hwdb, const char **key, const char **value) { + const struct trie_value_entry_f *entry; + const void *k; + + assert_return(hwdb, -EINVAL); + assert_return(key, -EINVAL); + assert_return(value, -EINVAL); + + if (hwdb->properties_modified) + return -EAGAIN; + + ordered_hashmap_iterate(hwdb->properties, &hwdb->properties_iterator, (void **)&entry, &k); + if (!k) + return 0; + + *key = k; + *value = trie_string(hwdb, entry->value_off); + + return 1; +} |