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