src/udev/udevadm-hwdb.c

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