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