From 796b06c21b62d13c9021e2fbd9c58a5c6edb2764 Mon Sep 17 00:00:00 2001 From: Kay Sievers Date: Mon, 22 Oct 2012 18:23:08 +0200 Subject: udev: add hardware database support --- src/tmpfiles/tmpfiles.c | 5 +- src/udev/udev-builtin-hwdb.c | 476 +++++++++++++++++++++++-------------- src/udev/udev-builtin.c | 5 +- src/udev/udev-hwdb.h | 69 ++++++ src/udev/udev.h | 7 +- src/udev/udevadm-hwdb.c | 548 +++++++++++++++++++++++++++++++++++++++++++ src/udev/udevadm.c | 3 +- 7 files changed, 928 insertions(+), 185 deletions(-) create mode 100644 src/udev/udev-hwdb.h create mode 100644 src/udev/udevadm-hwdb.c (limited to 'src') diff --git a/src/tmpfiles/tmpfiles.c b/src/tmpfiles/tmpfiles.c index bf900fa3d9..c32cbd1aea 100644 --- a/src/tmpfiles/tmpfiles.c +++ b/src/tmpfiles/tmpfiles.c @@ -1365,7 +1365,7 @@ int main(int argc, char *argv[]) { for (j = optind; j < argc; j++) { char *fragment; - fragment = resolve_fragment(argv[j], (const char**) conf_file_dirs); + fragment = resolve_fragment(argv[j], (const char **)conf_file_dirs); if (!fragment) { log_error("Failed to find a %s file: %m", argv[j]); r = EXIT_FAILURE; @@ -1379,8 +1379,7 @@ int main(int argc, char *argv[]) { } else { char **files, **f; - r = conf_files_list_strv(&files, ".conf", - (const char **) conf_file_dirs); + r = conf_files_list_strv(&files, ".conf", (const char **)conf_file_dirs); if (r < 0) { log_error("Failed to enumerate tmpfiles.d files: %s", strerror(-r)); r = EXIT_FAILURE; diff --git a/src/udev/udev-builtin-hwdb.c b/src/udev/udev-builtin-hwdb.c index 0db21641b1..5ccd06df04 100644 --- a/src/udev/udev-builtin-hwdb.c +++ b/src/udev/udev-builtin-hwdb.c @@ -1,22 +1,22 @@ -/* - * usb-db, pci-db - lookup vendor/product database - * - * Copyright (C) 2009 Lennart Poettering - * Copyright (C) 2011 Kay Sievers - * - * This program is free software: you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation, either version 2 of the License, or - * (at your option) any later version. - * - * This program 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 General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program. If not, see . - */ +/*** + This file is part of systemd. + + Copyright 2012 Kay Sievers + Copyright 2008 Alan Jenkins + + 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 . +***/ #include #include @@ -24,224 +24,352 @@ #include #include #include +#include +#include +#include #include "udev.h" +#include "udev-hwdb.h" -static int get_id_attr( - struct udev_device *parent, - const char *name, - uint16_t *value) { +struct linebuf { + char bytes[LINE_MAX]; + size_t size; + size_t len; +}; - const char *t; - unsigned u; +static void linebuf_init(struct linebuf *buf) { + buf->size = 0; + buf->len = 0; +} - if (!(t = udev_device_get_sysattr_value(parent, name))) { - fprintf(stderr, "%s lacks %s.\n", udev_device_get_syspath(parent), name); - return -1; - } +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; +} - if (startswith(t, "0x")) - t += 2; +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; +} - if (sscanf(t, "%04x", &u) != 1 || u > 0xFFFFU) { - fprintf(stderr, "Failed to parse %s on %s.\n", name, udev_device_get_syspath(parent)); - return -1; - } +static void linebuf_rem(struct linebuf *buf, size_t count) { + assert(buf->len >= count); + buf->len -= count; +} - *value = (uint16_t) u; - return 0; +static void linebuf_rem_char(struct linebuf *buf) { + linebuf_rem(buf, 1); } -static int get_vid_pid( - struct udev_device *parent, - const char *vendor_attr, - const char *product_attr, - uint16_t *vid, - uint16_t *pid) { +struct trie_f { + struct udev_device *dev; + bool test; + FILE *f; + uint64_t file_time_usec; + union { + struct trie_header_f *head; + const char *map; + }; + size_t map_size; +}; - if (get_id_attr(parent, vendor_attr, vid) < 0) - return -1; - else if (*vid <= 0) { - fprintf(stderr, "Invalid vendor id.\n"); - return -1; - } +static const struct trie_child_entry_f *trie_node_children(struct trie_f *trie, const struct trie_node_f *node) { + return (const struct trie_child_entry_f *)((const char *)node + le64toh(trie->head->node_size)); +} - if (get_id_attr(parent, product_attr, pid) < 0) - return -1; +static const struct trie_value_entry_f *trie_node_values(struct trie_f *trie, const struct trie_node_f *node) { + const char *base = (const char *)node; - return 0; + base += le64toh(trie->head->node_size); + base += node->children_count * le64toh(trie->head->child_entry_size); + return (const struct trie_value_entry_f *)base; } -static void rstrip(char *n) { - size_t i; +static const struct trie_node_f *trie_node_from_off(struct trie_f *trie, le64_t off) { + return (const struct trie_node_f *)(trie->map + le64toh(off)); +} - for (i = strlen(n); i > 0 && isspace(n[i-1]); i--) - n[i-1] = 0; +static const char *trie_string(struct trie_f *trie, le64_t off) { + return trie->map + le64toh(off); } -#define HEXCHARS "0123456789abcdefABCDEF" -#define WHITESPACE " \t\n\r" -static int lookup_vid_pid(const char *database, - uint16_t vid, uint16_t pid, - char **vendor, char **product) -{ +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; - FILE *f; - int ret = -1; - int found_vendor = 0; - char *line = NULL; + return n1->c - n2->c; +} - *vendor = *product = NULL; +static const struct trie_node_f *node_lookup_f(struct trie_f *trie, const struct trie_node_f *node, uint8_t c) { + struct trie_child_entry_f *child; + struct trie_child_entry_f search; - if (!(f = fopen(database, "rme"))) { - fprintf(stderr, "Failed to open database file '%s': %s\n", database, strerror(errno)); - return -1; - } + search.c = c; + child = bsearch(&search, trie_node_children(trie, node), node->children_count, + le64toh(trie->head->child_entry_size), trie_children_cmp_f); + if (child) + return trie_node_from_off(trie, child->child_off); + return NULL; +} - for (;;) { - size_t n; +static void trie_fnmatch_f(struct trie_f *trie, const struct trie_node_f *node, size_t p, + struct linebuf *buf, const char *search, + void (*cb)(struct trie_f *trie, const char *key, const char *value)) { + size_t len; + size_t i; + const char *prefix; - if (getline(&line, &n, f) < 0) - break; + prefix = trie_string(trie, node->prefix_off); + len = strlen(prefix + p); + linebuf_add(buf, prefix + p, len); - rstrip(line); + for (i = 0; i < node->children_count; i++) { + const struct trie_child_entry_f *child = &trie_node_children(trie, node)[i]; - if (line[0] == '#' || line[0] == 0) - continue; + linebuf_add_char(buf, child->c); + trie_fnmatch_f(trie, trie_node_from_off(trie, child->child_off), 0, buf, search, cb); + linebuf_rem_char(buf); + } - if (strspn(line, HEXCHARS) == 4) { - unsigned u; + if (node->values_count && fnmatch(linebuf_get(buf), search, 0) == 0) + for (i = 0; i < node->values_count; i++) + cb(trie, trie_string(trie, trie_node_values(trie, node)[i].key_off), + trie_string(trie, trie_node_values(trie, node)[i].value_off)); - if (found_vendor) - break; + linebuf_rem(buf, len); +} - if (sscanf(line, "%04x", &u) == 1 && u == vid) { - char *t; +static void trie_search_f(struct trie_f *trie, const char *search, + void (*cb)(struct trie_f *trie, const char *key, const char *value)) { + struct linebuf buf; + const struct trie_node_f *node; + size_t i = 0; - t = line+4; - t += strspn(t, WHITESPACE); + linebuf_init(&buf); - if (!(*vendor = strdup(t))) { - fprintf(stderr, "Out of memory.\n"); - goto finish; - } + node = trie_node_from_off(trie, trie->head->nodes_root_off); + while (node) { + const struct trie_node_f *child; + size_t p = 0; - found_vendor = 1; - } + if (node->prefix_off) { + uint8_t c; - continue; + for (; (c = trie_string(trie, node->prefix_off)[p]); p++) { + if (c == '*' || c == '?' || c == '[') { + trie_fnmatch_f(trie, node, p, &buf, search + i + p, cb); + return; + } + if (c != search[i + p]) + return; + } + i += p; } - if (found_vendor && line[0] == '\t' && strspn(line+1, HEXCHARS) == 4) { - unsigned u; + child = node_lookup_f(trie, node, '*'); + if (child) { + linebuf_add_char(&buf, '*'); + trie_fnmatch_f(trie, child, 0, &buf, search + i, cb); + linebuf_rem_char(&buf); + } - if (sscanf(line+1, "%04x", &u) == 1 && u == pid) { - char *t; + child = node_lookup_f(trie, node, '?'); + if (child) { + linebuf_add_char(&buf, '?'); + trie_fnmatch_f(trie, child, 0, &buf, search + i, cb); + linebuf_rem_char(&buf); + } - t = line+5; - t += strspn(t, WHITESPACE); + child = node_lookup_f(trie, node, '['); + if (child) { + linebuf_add_char(&buf, '['); + trie_fnmatch_f(trie, child, 0, &buf, search + i, cb); + linebuf_rem_char(&buf); + } - if (!(*product = strdup(t))) { - fprintf(stderr, "Out of memory.\n"); - goto finish; - } + if (search[i] == '\0') { + size_t n; - break; - } + for (n = 0; n < node->values_count; n++) + cb(trie, trie_string(trie, trie_node_values(trie, node)[n].key_off), + trie_string(trie, trie_node_values(trie, node)[n].value_off)); + return; } + + child = node_lookup_f(trie, node, search[i]); + node = child; + i++; } +} - ret = 0; +static void value_cb(struct trie_f *trie, const char *key, const char *value) { + /* TODO: add sub-matches (+) against DMI data */ + if (key[0] == ' ') + udev_builtin_add_property(trie->dev, trie->test, key + 1, value); +} -finish: - free(line); - fclose(f); +static struct trie_f trie; - if (ret < 0) { - free(*product); - free(*vendor); +static int hwdb_lookup(struct udev_device *dev, const char *subsys) { + struct udev_device *d; + const char *modalias; + char str[UTIL_NAME_SIZE]; + int rc = EXIT_SUCCESS; - *product = *vendor = NULL; - } + /* search the first parent device with a modalias */ + for (d = dev; d; d = udev_device_get_parent(d)) { + const char *dsubsys = udev_device_get_subsystem(d); - return ret; -} + /* look only at devices of a specific subsystem */ + if (subsys && dsubsys && !streq(dsubsys, subsys)) + continue; -static struct udev_device *find_device(struct udev_device *dev, const char *subsys, const char *devtype) -{ - const char *str; - - str = udev_device_get_subsystem(dev); - if (str == NULL) - goto try_parent; - if (strcmp(str, subsys) != 0) - goto try_parent; - - if (devtype != NULL) { - str = udev_device_get_devtype(dev); - if (str == NULL) - goto try_parent; - if (strcmp(str, devtype) != 0) - goto try_parent; + modalias = udev_device_get_property_value(d, "MODALIAS"); + if (modalias) + break; + + /* the usb_device does not have modalias, compose one */ + if (dsubsys && streq(dsubsys, "usb")) { + const char *v, *p; + int vn, pn; + + v = udev_device_get_sysattr_value(d, "idVendor"); + if (!v) + continue; + p = udev_device_get_sysattr_value(d, "idProduct"); + if (!p) + continue; + vn = strtol(v, NULL, 16); + if (vn <= 0) + continue; + pn = strtol(p, NULL, 16); + if (pn <= 0) + continue; + snprintf(str, sizeof(str), "usb:v%04Xp%04X*", vn, pn); + modalias = str; + break; + } } - return dev; -try_parent: - return udev_device_get_parent_with_subsystem_devtype(dev, subsys, devtype); + if (!modalias) + return EXIT_FAILURE; + + trie_search_f(&trie, modalias, value_cb); + return rc; } +static int builtin_hwdb(struct udev_device *dev, int argc, char *argv[], bool test) { + static const struct option options[] = { + { "subsystem", required_argument, NULL, 's' }, + {} + }; + const char *subsys = NULL; -static int builtin_db(struct udev_device *dev, bool test, - const char *database, - const char *vendor_attr, const char *product_attr, - const char *subsys, const char *devtype) -{ - struct udev_device *parent; - uint16_t vid = 0, pid = 0; - char *vendor = NULL, *product = NULL; - - parent = find_device(dev, subsys, devtype); - if (!parent) { - fprintf(stderr, "Failed to find device.\n"); - goto finish; + for (;;) { + int option; + + option = getopt_long(argc, argv, "s", options, NULL); + if (option == -1) + break; + + switch (option) { + case 's': + subsys = optarg; + break; + } } - if (get_vid_pid(parent, vendor_attr, product_attr, &vid, &pid) < 0) - goto finish; + trie.dev = dev; + trie.test = test; + if (hwdb_lookup(dev, subsys) < 0) + return EXIT_FAILURE; + return EXIT_SUCCESS; +} - if (lookup_vid_pid(database, vid, pid, &vendor, &product) < 0) - goto finish; +/* called at udev startup and reload */ +static int builtin_hwdb_init(struct udev *udev) +{ + struct stat st; + const char sig[] = HWDB_SIG; + + trie.f = fopen(SYSCONFDIR "/udev/hwdb.bin", "re"); + if (!trie.f) + return -errno; + + if (fstat(fileno(trie.f), &st) < 0 || (size_t)st.st_size < offsetof(struct trie_header_f, strings_len) + 8) { + log_error("Error reading '%s'.", SYSCONFDIR "/udev/hwdb.bin: %m"); + fclose(trie.f); + zero(trie); + return -EINVAL; + } - if (vendor) - udev_builtin_add_property(dev, test, "ID_VENDOR_FROM_DATABASE", vendor); - if (product) - udev_builtin_add_property(dev, test, "ID_MODEL_FROM_DATABASE", product); + trie.map = mmap(0, st.st_size, PROT_READ, MAP_SHARED, fileno(trie.f), 0); + if (trie.map == MAP_FAILED) { + log_error("Error mapping '%s'.", SYSCONFDIR "/udev/hwdb.bin: %m"); + fclose(trie.f); + return -EINVAL; + } + trie.file_time_usec = ts_usec(&st.st_mtim); + trie.map_size = st.st_size; + + if (memcmp(trie.map, sig, sizeof(trie.head->signature)) != 0 || (size_t)st.st_size != le64toh(trie.head->file_size)) { + log_error("Unable to recognize the format of '%s'.", SYSCONFDIR "/udev/hwdb.bin"); + log_error("Please try 'udevadm hwdb --update' to re-create it."); + munmap((void *)trie.map, st.st_size); + fclose(trie.f); + zero(trie); + return EINVAL; + } -finish: - free(vendor); - free(product); + log_debug("=== trie on-disk ===\n"); + log_debug("tool version: %llu", (unsigned long long)le64toh(trie.head->tool_version)); + log_debug("file size: %8zi bytes\n", st.st_size); + log_debug("header size %8zu bytes\n", (size_t)le64toh(trie.head->header_size)); + log_debug("strings %8zu bytes\n", (size_t)le64toh(trie.head->strings_len)); + log_debug("nodes %8zu bytes\n", (size_t)le64toh(trie.head->nodes_len)); return 0; } -static int builtin_usb_db(struct udev_device *dev, int argc, char *argv[], bool test) +/* called on udev shutdown and reload request */ +static void builtin_hwdb_exit(struct udev *udev) { - return builtin_db(dev, test, USB_DATABASE, "idVendor", "idProduct", "usb", "usb_device"); + if (!trie.f) + return; + munmap((void *)trie.map, trie.map_size); + fclose(trie.f); + zero(trie); } -static int builtin_pci_db(struct udev_device *dev, int argc, char *argv[], bool test) +/* called every couple of seconds during event activity; 'true' if config has changed */ +static bool builtin_hwdb_validate(struct udev *udev) { - return builtin_db(dev, test, PCI_DATABASE, "vendor", "device", "pci", NULL); -} + struct stat st; -const struct udev_builtin udev_builtin_usb_db = { - .name = "usb-db", - .cmd = builtin_usb_db, - .help = "USB vendor/product database", - .run_once = true, -}; + if (fstat(fileno(trie.f), &st) < 0) + return true; + if (trie.file_time_usec != ts_usec(&st.st_mtim)) + return true; + return false; +} -const struct udev_builtin udev_builtin_pci_db = { - .name = "pci-db", - .cmd = builtin_pci_db, - .help = "PCI vendor/product database", +const struct udev_builtin udev_builtin_hwdb = { + .name = "hwdb", + .cmd = builtin_hwdb, + .init = builtin_hwdb_init, + .exit = builtin_hwdb_exit, + .validate = builtin_hwdb_validate, + .help = "hardware database", .run_once = true, }; diff --git a/src/udev/udev-builtin.c b/src/udev/udev-builtin.c index b632edaae1..18fc3df274 100644 --- a/src/udev/udev-builtin.c +++ b/src/udev/udev-builtin.c @@ -31,11 +31,10 @@ static const struct udev_builtin *builtins[] = { [UDEV_BUILTIN_BLKID] = &udev_builtin_blkid, [UDEV_BUILTIN_BTRFS] = &udev_builtin_btrfs, [UDEV_BUILTIN_FIRMWARE] = &udev_builtin_firmware, + [UDEV_BUILTIN_HWDB] = &udev_builtin_hwdb, [UDEV_BUILTIN_INPUT_ID] = &udev_builtin_input_id, [UDEV_BUILTIN_KMOD] = &udev_builtin_kmod, [UDEV_BUILTIN_PATH_ID] = &udev_builtin_path_id, - [UDEV_BUILTIN_PCI_DB] = &udev_builtin_pci_db, - [UDEV_BUILTIN_USB_DB] = &udev_builtin_usb_db, [UDEV_BUILTIN_USB_ID] = &udev_builtin_usb_id, #ifdef HAVE_ACL [UDEV_BUILTIN_UACCESS] = &udev_builtin_uaccess, @@ -128,7 +127,7 @@ int udev_builtin_run(struct udev_device *dev, enum udev_builtin_cmd cmd, const c int argc; char *argv[128]; - optind = 0; + optind = 1; util_strscpy(arg, sizeof(arg), command); udev_build_argv(udev_device_get_udev(dev), arg, &argc, argv); return builtins[cmd]->cmd(dev, argc, argv, test); diff --git a/src/udev/udev-hwdb.h b/src/udev/udev-hwdb.h new file mode 100644 index 0000000000..8a9955eb60 --- /dev/null +++ b/src/udev/udev-hwdb.h @@ -0,0 +1,69 @@ +/*** + This file is part of systemd. + + Copyright 2012 Kay Sievers + + 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 . +***/ + +#include "sparse-endian.h" + +#define HWDB_SIG { 'K', 'S', 'L', 'P', 'H', 'H', 'R', 'H' } + +/* on-disk trie objects */ +_packed_ 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; +}; + +/* array of child entries, follows directly the node record */ +_packed_ 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; +}; + +/* array of value entries, follows directly the node record/child array */ +_packed_ struct trie_value_entry_f { + le64_t key_off; + le64_t value_off; +}; diff --git a/src/udev/udev.h b/src/udev/udev.h index d160a86dfb..a2c84f6aeb 100644 --- a/src/udev/udev.h +++ b/src/udev/udev.h @@ -137,11 +137,10 @@ enum udev_builtin_cmd { UDEV_BUILTIN_BLKID, UDEV_BUILTIN_BTRFS, UDEV_BUILTIN_FIRMWARE, + UDEV_BUILTIN_HWDB, UDEV_BUILTIN_INPUT_ID, UDEV_BUILTIN_KMOD, UDEV_BUILTIN_PATH_ID, - UDEV_BUILTIN_PCI_DB, - UDEV_BUILTIN_USB_DB, UDEV_BUILTIN_USB_ID, #ifdef HAVE_ACL UDEV_BUILTIN_UACCESS, @@ -160,11 +159,10 @@ struct udev_builtin { extern const struct udev_builtin udev_builtin_blkid; extern const struct udev_builtin udev_builtin_btrfs; extern const struct udev_builtin udev_builtin_firmware; +extern const struct udev_builtin udev_builtin_hwdb; extern const struct udev_builtin udev_builtin_input_id; extern const struct udev_builtin udev_builtin_kmod; extern const struct udev_builtin udev_builtin_path_id; -extern const struct udev_builtin udev_builtin_pci_db; -extern const struct udev_builtin udev_builtin_usb_db; extern const struct udev_builtin udev_builtin_usb_id; extern const struct udev_builtin udev_builtin_uaccess; int udev_builtin_init(struct udev *udev); @@ -194,6 +192,7 @@ extern const struct udevadm_cmd udevadm_trigger; extern const struct udevadm_cmd udevadm_settle; extern const struct udevadm_cmd udevadm_control; extern const struct udevadm_cmd udevadm_monitor; +extern const struct udevadm_cmd udevadm_hwdb; extern const struct udevadm_cmd udevadm_test; extern const struct udevadm_cmd udevadm_test_builtin; #endif diff --git a/src/udev/udevadm-hwdb.c b/src/udev/udevadm-hwdb.c new file mode 100644 index 0000000000..52fe1d4ebc --- /dev/null +++ b/src/udev/udevadm-hwdb.c @@ -0,0 +1,548 @@ +/*** + This file is part of systemd. + + Copyright 2012 Kay Sievers + + 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 . +***/ + +#include +#include +#include +#include + +#include "util.h" +#include "strbuf.h" +#include "conf-files.h" + +#include "udev.h" +#include "udev-hwdb.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[] = { + SYSCONFDIR "/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; + int err = 0; + + /* extend array, add new entry, sort for bisection */ + child = realloc(node->children, (node->children_count + 1) * sizeof(struct trie_child_entry)); + if (!child) { + err = -ENOMEM; + goto out; + } + 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++; +out: + return err; +} + +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) { + size_t k, v; + struct trie_value_entry *val; + struct trie_value_entry search; + + k = strbuf_add_string(trie->strings, key, strlen(key)); + v = strbuf_add_string(trie->strings, value, strlen(value)); + + /* replace existing earlier key with new value */ + search.value_off = k; + val = xbsearch_r(&search, node->values, node->values_count, sizeof(struct trie_value_entry), trie_values_cmp, trie); + if (val) { + 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++) { + char *s; + ssize_t off; + + if (c == search[i + p]) + continue; + + /* split node */ + child = calloc(sizeof(struct trie_node), 1); + if (!child) { + err = -ENOMEM; + goto out; + } + + /* move values from parent to child */ + child->prefix_off = node->prefix_off + p+1; + child->children = node->children; + child->children_count = node->children_count; + child->values = node->values; + 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) { + err = -ENOMEM; + goto out; + } + off = strbuf_add_string(trie->strings, s, p); + free(s); + if (off < 0) { + err = off; + goto out; + } + node->prefix_off = off; + node->children = NULL; + node->children_count = 0; + node->values = NULL; + node->values_count = 0; + err = node_add_child(trie, node, child, c); + if (err) + goto out; + 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 = calloc(sizeof(struct trie_node), 1); + if (!child) { + err = -ENOMEM; + goto out; + } + off = strbuf_add_string(trie->strings, search + i+1, strlen(search + i+1)); + if (off < 0) { + err = off; + goto out; + } + child->prefix_off = off; + err = node_add_child(trie, node, child, c); + if (err) + goto out; + return trie_node_add_value(trie, child, key, value); + } + + node = child; + i++; + } +out: + return err; +} + +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; + 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) + 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, + }; + char *filename_tmp; + 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 */ + fseeko(t.f, sizeof(struct trie_header_f), SEEK_SET); + root_off = trie_store_nodes(&t, trie->root); + h.nodes_root_off = htole64(root_off); + pos = ftello(t.f); + h.nodes_len = htole64(pos - sizeof(struct trie_header_f)); + + /* write string buffer */ + fwrite(trie->strings->buf, trie->strings->len, 1, t.f); + h.strings_len = htole64(trie->strings->len); + + /* write header */ + size = ftello(t.f); + h.file_size = htole64(size); + fseeko(t.f, 0, SEEK_SET); + fwrite(&h, sizeof(struct trie_header_f), 1, t.f); + err = ferror(t.f); + if (err) + err = -errno; + fclose(t.f); + if (err < 0 || rename(filename_tmp, filename) < 0) { + unlink(filename_tmp); + goto out; + } + + log_debug("=== trie on-disk ===\n"); + log_debug("size: %8zi bytes\n", size); + log_debug("header: %8zu bytes\n", sizeof(struct trie_header_f)); + log_debug("nodes: %8zu bytes (%8zi)\n", t.nodes_count * sizeof(struct trie_node_f), t.nodes_count); + log_debug("child pointers: %8zu bytes (%8zi)\n", t.children_count * sizeof(struct trie_child_entry_f), t.children_count); + log_debug("value pointers: %8zu bytes (%8zi)\n", t.values_count * sizeof(struct trie_value_entry_f), t.values_count); + log_debug("string store: %8zu bytes\n", trie->strings->len); + log_debug("strings start: %8llu\n", (unsigned long long) t.strings_off); +out: + free(filename_tmp); + return err; +} + +static int import_file(struct trie *trie, const char *filename) { + FILE *f; + char line[LINE_MAX]; + char match[LINE_MAX]; + + f = fopen(filename, "re"); + if (f == NULL) + return -errno; + + match[0] = '\0'; + while (fgets(line, sizeof(line), f)) { + size_t len; + + if (line[0] == '#') + continue; + + /* new line, new record */ + if (line[0] == '\n') { + match[0] = '\0'; + continue; + } + + /* remove newline */ + len = strlen(line); + if (len < 2) + continue; + line[len-1] = '\0'; + + /* start of new record */ + if (match[0] == '\0') { + strcpy(match, line); + continue; + } + + /* value lines */ + if (line[0] == ' ') { + char *value; + + value = strchr(line, '='); + if (!value) + continue; + value[0] = '\0'; + value++; + trie_insert(trie, trie->root, match, line, value); + } + } + fclose(f); + return 0; +} + +static void help(void) { + printf("Usage: udevadm hwdb [--create] [--help]\n" + " --update update the hardware database\n" + " --help\n\n"); +} + +static int adm_hwdb(struct udev *udev, int argc, char *argv[]) { + static const struct option options[] = { + { "update", no_argument, NULL, 'u' }, + { "help", no_argument, NULL, 'h' }, + {} + }; + bool update = false; + struct trie *trie; + char **files, **f; + int err; + int rc = EXIT_SUCCESS; + + for (;;) { + int option; + + option = getopt_long(argc, argv, "ch", options, NULL); + if (option == -1) + break; + + switch (option) { + case 'u': + update = true; + break; + case 'h': + help(); + return EXIT_SUCCESS; + } + } + + if (!update) { + help(); + return EXIT_SUCCESS; + } + + trie = calloc(sizeof(struct trie), 1); + if (!trie) { + rc = EXIT_FAILURE; + goto out; + } + + /* string store */ + trie->strings = strbuf_new(); + if (!trie->strings) { + rc = EXIT_FAILURE; + goto out; + } + + /* index */ + trie->root = calloc(sizeof(struct trie_node), 1); + if (!trie->root) { + rc = EXIT_FAILURE; + goto out; + } + trie->nodes_count++; + + err = conf_files_list_strv(&files, ".hwdb", (const char **)conf_file_dirs); + if (err < 0) { + log_error("failed to enumerate hwdb files: %s\n", strerror(-err)); + rc = EXIT_FAILURE; + goto out; + } + STRV_FOREACH(f, files) { + log_debug("reading file '%s'", *f); + import_file(trie, *f); + } + strv_free(files); + + strbuf_complete(trie->strings); + + log_debug("=== trie in-memory ===\n"); + log_debug("nodes: %8zu bytes (%8zu)\n", trie->nodes_count * sizeof(struct trie_node), trie->nodes_count); + log_debug("children arrays: %8zu bytes (%8zu)\n", trie->children_count * sizeof(struct trie_child_entry), trie->children_count); + log_debug("values arrays: %8zu bytes (%8zu)\n", trie->values_count * sizeof(struct trie_value_entry), trie->values_count); + log_debug("strings: %8zu bytes\n", trie->strings->len); + log_debug("strings incoming: %8zu bytes (%8zu)\n", trie->strings->in_len, trie->strings->in_count); + log_debug("strings dedup'ed: %8zu bytes (%8zu)\n", trie->strings->dedup_len, trie->strings->dedup_count); + + mkdir_parents(SYSCONFDIR "/udev/hwdb.bin", 0755); + err = trie_store(trie, SYSCONFDIR "/udev/hwdb.bin"); + if (err < 0) { + log_error("Failure writing hardware database '%s': %s", SYSCONFDIR "/udev/hwdb.bin", strerror(-err)); + rc = EXIT_FAILURE; + } + +out: + if (trie->root) + trie_node_cleanup(trie->root); + strbuf_cleanup(trie->strings); + free(trie); + return rc; +} + +const struct udevadm_cmd udevadm_hwdb = { + .name = "hwdb", + .cmd = adm_hwdb, + .help = "maintain the hardware database index", +}; diff --git a/src/udev/udevadm.c b/src/udev/udevadm.c index 818edee38f..d1e9756b2e 100644 --- a/src/udev/udevadm.c +++ b/src/udev/udevadm.c @@ -56,6 +56,7 @@ static const struct udevadm_cmd *udevadm_cmds[] = { &udevadm_settle, &udevadm_control, &udevadm_monitor, + &udevadm_hwdb, &udevadm_test, &udevadm_test_builtin, &udevadm_version, @@ -133,7 +134,7 @@ int main(int argc, char *argv[]) if (strcmp(udevadm_cmds[i]->name, command) == 0) { argc -= optind; argv += optind; - optind = 0; + optind = 1; rc = run_command(udev, udevadm_cmds[i], argc, argv); goto out; } -- cgit v1.2.3-54-g00ecf