src/udev/udevadm-hwdb.c

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