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