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