src/udev/udevadm-hwdb.c

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