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