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