src/udev/udevadm-hwdb.c

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