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