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