1 /* SPDX-License-Identifier: LGPL-2.1+ */
3 This file is part of systemd.
5 Copyright 2012 Kay Sievers <kay@vrfy.org>
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.
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.
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/>.
26 #include "alloc-util.h"
27 #include "conf-files.h"
30 #include "hwdb-internal.h"
31 #include "hwdb-util.h"
35 #include "string-util.h"
37 #include "udevadm-util.h"
41 * Generic udev properties, key/value database based on modalias strings.
42 * Uses a Patricia/radix trie to index all matches for efficient lookup.
45 static const char * const conf_file_dirs
[] = {
47 UDEVLIBEXECDIR
"/hwdb.d",
51 /* in-memory trie objects */
53 struct trie_node
*root
;
54 struct strbuf
*strings
;
57 size_t children_count
;
62 /* prefix, common part for all children of this node */
65 /* sorted array of pointers to children nodes */
66 struct trie_child_entry
*children
;
67 uint8_t children_count
;
69 /* sorted array of key/value pairs */
70 struct trie_value_entry
*values
;
74 /* children array item with char (0-255) index */
75 struct trie_child_entry
{
77 struct trie_node
*child
;
80 /* value array item with key/value pairs */
81 struct trie_value_entry
{
86 static int trie_children_cmp(const void *v1
, const void *v2
) {
87 const struct trie_child_entry
*n1
= v1
;
88 const struct trie_child_entry
*n2
= v2
;
93 static int node_add_child(struct trie
*trie
, struct trie_node
*node
, struct trie_node
*node_child
, uint8_t c
) {
94 struct trie_child_entry
*child
;
96 /* extend array, add new entry, sort for bisection */
97 child
= reallocarray(node
->children
, node
->children_count
+ 1, sizeof(struct trie_child_entry
));
101 node
->children
= child
;
102 trie
->children_count
++;
103 node
->children
[node
->children_count
].c
= c
;
104 node
->children
[node
->children_count
].child
= node_child
;
105 node
->children_count
++;
106 qsort(node
->children
, node
->children_count
, sizeof(struct trie_child_entry
), trie_children_cmp
);
112 static struct trie_node
*node_lookup(const struct trie_node
*node
, uint8_t c
) {
113 struct trie_child_entry
*child
;
114 struct trie_child_entry search
;
117 child
= bsearch(&search
, node
->children
, node
->children_count
, sizeof(struct trie_child_entry
), trie_children_cmp
);
123 static void trie_node_cleanup(struct trie_node
*node
) {
126 for (i
= 0; i
< node
->children_count
; i
++)
127 trie_node_cleanup(node
->children
[i
].child
);
128 free(node
->children
);
133 static int trie_values_cmp(const void *v1
, const void *v2
, void *arg
) {
134 const struct trie_value_entry
*val1
= v1
;
135 const struct trie_value_entry
*val2
= v2
;
136 struct trie
*trie
= arg
;
138 return strcmp(trie
->strings
->buf
+ val1
->key_off
,
139 trie
->strings
->buf
+ val2
->key_off
);
142 static int trie_node_add_value(struct trie
*trie
, struct trie_node
*node
,
143 const char *key
, const char *value
) {
145 struct trie_value_entry
*val
;
147 k
= strbuf_add_string(trie
->strings
, key
, strlen(key
));
150 v
= strbuf_add_string(trie
->strings
, value
, strlen(value
));
154 if (node
->values_count
) {
155 struct trie_value_entry search
= {
160 val
= xbsearch_r(&search
, node
->values
, node
->values_count
, sizeof(struct trie_value_entry
), trie_values_cmp
, trie
);
162 /* replace existing earlier key with new value */
168 /* extend array, add new entry, sort for bisection */
169 val
= reallocarray(node
->values
, node
->values_count
+ 1, sizeof(struct trie_value_entry
));
172 trie
->values_count
++;
174 node
->values
[node
->values_count
].key_off
= k
;
175 node
->values
[node
->values_count
].value_off
= v
;
176 node
->values_count
++;
177 qsort_r(node
->values
, node
->values_count
, sizeof(struct trie_value_entry
), trie_values_cmp
, trie
);
181 static int trie_insert(struct trie
*trie
, struct trie_node
*node
, const char *search
,
182 const char *key
, const char *value
) {
189 struct trie_node
*child
;
191 for (p
= 0; (c
= trie
->strings
->buf
[node
->prefix_off
+ p
]); p
++) {
192 _cleanup_free_
char *s
= NULL
;
194 _cleanup_free_
struct trie_node
*new_child
= NULL
;
196 if (c
== search
[i
+ p
])
200 new_child
= new0(struct trie_node
, 1);
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
;
211 /* update parent; use strdup() because the source gets realloc()d */
212 s
= strndup(trie
->strings
->buf
+ node
->prefix_off
, p
);
216 off
= strbuf_add_string(trie
->strings
, s
, p
);
220 node
->prefix_off
= off
;
221 node
->children
= NULL
;
222 node
->children_count
= 0;
224 node
->values_count
= 0;
225 err
= node_add_child(trie
, node
, new_child
, c
);
229 new_child
= NULL
; /* avoid cleanup */
236 return trie_node_add_value(trie
, node
, key
, value
);
238 child
= node_lookup(node
, c
);
243 child
= new0(struct trie_node
, 1);
247 off
= strbuf_add_string(trie
->strings
, search
+ i
+1, strlen(search
+ i
+1));
253 child
->prefix_off
= off
;
254 err
= node_add_child(trie
, node
, child
, c
);
260 return trie_node_add_value(trie
, child
, key
, value
);
271 uint64_t strings_off
;
273 uint64_t nodes_count
;
274 uint64_t children_count
;
275 uint64_t values_count
;
278 /* calculate the storage space for the nodes, children arrays, value arrays */
279 static void trie_store_nodes_size(struct trie_f
*trie
, struct trie_node
*node
) {
282 for (i
= 0; i
< node
->children_count
; i
++)
283 trie_store_nodes_size(trie
, node
->children
[i
].child
);
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
);
292 static int64_t trie_store_nodes(struct trie_f
*trie
, struct trie_node
*node
) {
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
),
299 struct trie_child_entry_f
*children
= NULL
;
302 if (node
->children_count
) {
303 children
= new0(struct trie_child_entry_f
, node
->children_count
);
308 /* post-order recursion */
309 for (i
= 0; i
< node
->children_count
; i
++) {
312 child_off
= trie_store_nodes(trie
, node
->children
[i
].child
);
317 children
[i
].c
= node
->children
[i
].c
;
318 children
[i
].child_off
= htole64(child_off
);
322 node_off
= ftello(trie
->f
);
323 fwrite(&n
, sizeof(struct trie_node_f
), 1, trie
->f
);
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
;
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
),
340 fwrite(&v
, sizeof(struct trie_value_entry_f
), 1, trie
->f
);
341 trie
->values_count
++;
347 static int trie_store(struct trie
*trie
, const char *filename
) {
351 _cleanup_free_
char *filename_tmp
= NULL
;
355 struct trie_header_f h
= {
356 .signature
= HWDB_SIG
,
357 .tool_version
= htole64(atoi(PACKAGE_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
)),
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
);
369 err
= fopen_temporary(filename
, &t
.f
, &filename_tmp
);
372 fchmod(fileno(t
.f
), 0444);
375 if (fseeko(t
.f
, sizeof(struct trie_header_f
), SEEK_SET
) < 0)
377 root_off
= trie_store_nodes(&t
, trie
->root
);
378 h
.nodes_root_off
= htole64(root_off
);
380 h
.nodes_len
= htole64(pos
- sizeof(struct trie_header_f
));
382 /* write string buffer */
383 fwrite(trie
->strings
->buf
, trie
->strings
->len
, 1, t
.f
);
384 h
.strings_len
= htole64(trie
->strings
->len
);
388 h
.file_size
= htole64(size
);
389 if (fseeko(t
.f
, 0, SEEK_SET
< 0))
391 fwrite(&h
, sizeof(struct trie_header_f
), 1, t
.f
);
397 if (fsync(fileno(t
.f
)) < 0)
399 if (rename(filename_tmp
, filename
) < 0)
402 /* write succeeded */
405 log_debug("=== trie on-disk ===");
406 log_debug("size: %8"PRIi64
" bytes", size
);
407 log_debug("header: %8zu bytes", sizeof(struct trie_header_f
));
408 log_debug("nodes: %8"PRIu64
" bytes (%8"PRIu64
")",
409 t
.nodes_count
* sizeof(struct trie_node_f
), t
.nodes_count
);
410 log_debug("child pointers: %8"PRIu64
" bytes (%8"PRIu64
")",
411 t
.children_count
* sizeof(struct trie_child_entry_f
), t
.children_count
);
412 log_debug("value pointers: %8"PRIu64
" bytes (%8"PRIu64
")",
413 t
.values_count
* sizeof(struct trie_value_entry_f
), t
.values_count
);
414 log_debug("string store: %8zu bytes", trie
->strings
->len
);
415 log_debug("strings start: %8"PRIu64
, t
.strings_off
);
422 unlink(filename_tmp
);
426 static int insert_data(struct trie
*trie
, struct udev_list
*match_list
,
427 char *line
, const char *filename
) {
429 struct udev_list_entry
*entry
;
431 value
= strchr(line
, '=');
433 log_error("Error, key/value pair expected but got '%s' in '%s':", line
, filename
);
440 /* libudev requires properties to start with a space */
441 while (isblank(line
[0]) && isblank(line
[1]))
444 if (line
[0] == '\0' || value
[0] == '\0') {
445 log_error("Error, empty key or value '%s' in '%s':", line
, filename
);
449 udev_list_entry_foreach(entry
, udev_list_get_entry(match_list
))
450 trie_insert(trie
, trie
->root
, udev_list_entry_get_name(entry
), line
, value
);
455 static int import_file(struct udev
*udev
, struct trie
*trie
, const char *filename
) {
463 struct udev_list match_list
;
465 udev_list_init(udev
, &match_list
, false);
467 f
= fopen(filename
, "re");
471 while (fgets(line
, sizeof(line
), f
)) {
479 /* strip trailing comment */
480 pos
= strchr(line
, '#');
484 /* strip trailing whitespace */
486 while (len
> 0 && isspace(line
[len
-1]))
495 if (line
[0] == ' ') {
496 log_error("Error, MATCH expected but got '%s' in '%s':", line
, filename
);
500 /* start of record, first match */
502 udev_list_entry_add(&match_list
, line
, NULL
);
507 log_error("Error, DATA expected but got empty line in '%s':", filename
);
509 udev_list_cleanup(&match_list
);
514 if (line
[0] != ' ') {
515 udev_list_entry_add(&match_list
, line
, NULL
);
521 insert_data(trie
, &match_list
, line
, filename
);
528 udev_list_cleanup(&match_list
);
532 if (line
[0] != ' ') {
533 log_error("Error, DATA expected but got '%s' in '%s':", line
, filename
);
535 udev_list_cleanup(&match_list
);
539 insert_data(trie
, &match_list
, line
, filename
);
545 udev_list_cleanup(&match_list
);
549 static void help(void) {
550 printf("%s hwdb [OPTIONS]\n\n"
551 " -h --help Print this message\n"
552 " -V --version Print version of the program\n"
553 " -u --update Update the hardware database\n"
554 " --usr Generate in " UDEVLIBEXECDIR
" instead of /etc/udev\n"
555 " -t --test=MODALIAS Query database and print result\n"
556 " -r --root=PATH Alternative root path in the filesystem\n\n"
558 "The sub-command 'hwdb' is deprecated, and is left for backwards compatibility.\n"
559 "Please use systemd-hwdb instead.\n"
560 , program_invocation_short_name
);
563 static int adm_hwdb(struct udev
*udev
, int argc
, char *argv
[]) {
568 static const struct option options
[] = {
569 { "update", no_argument
, NULL
, 'u' },
570 { "usr", no_argument
, NULL
, ARG_USR
},
571 { "test", required_argument
, NULL
, 't' },
572 { "root", required_argument
, NULL
, 'r' },
573 { "version", no_argument
, NULL
, 'V' },
574 { "help", no_argument
, NULL
, 'h' },
577 const char *test
= NULL
;
578 const char *root
= "";
579 const char *hwdb_bin_dir
= "/etc/udev";
581 struct trie
*trie
= NULL
;
583 int rc
= EXIT_SUCCESS
;
585 while ((c
= getopt_long(argc
, argv
, "ut:r:Vh", options
, NULL
)) >= 0)
591 hwdb_bin_dir
= UDEVLIBEXECDIR
;
608 assert_not_reached("Unknown option");
611 if (!update
&& !test
) {
612 log_error("Either --update or --test must be used");
618 _cleanup_free_
char *hwdb_bin
= NULL
;
620 trie
= new0(struct trie
, 1);
627 trie
->strings
= strbuf_new();
628 if (!trie
->strings
) {
634 trie
->root
= new0(struct trie_node
, 1);
641 err
= conf_files_list_strv(&files
, ".hwdb", root
, 0, conf_file_dirs
);
643 log_error_errno(err
, "failed to enumerate hwdb files: %m");
647 STRV_FOREACH(f
, files
) {
648 log_debug("reading file '%s'", *f
);
649 import_file(udev
, trie
, *f
);
653 strbuf_complete(trie
->strings
);
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",
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
);
669 hwdb_bin
= strjoin(root
, "/", hwdb_bin_dir
, "/hwdb.bin");
675 mkdir_parents_label(hwdb_bin
, 0755);
677 err
= trie_store(trie
, hwdb_bin
);
679 log_error_errno(err
, "Failure writing database %s: %m", hwdb_bin
);
683 label_fix(hwdb_bin
, false, false);
687 _cleanup_(sd_hwdb_unrefp
) sd_hwdb
*hwdb
= NULL
;
690 r
= sd_hwdb_new(&hwdb
);
692 const char *key
, *value
;
694 SD_HWDB_FOREACH_PROPERTY(hwdb
, test
, key
, value
)
695 printf("%s=%s\n", key
, value
);
701 trie_node_cleanup(trie
->root
);
702 strbuf_cleanup(trie
->strings
);
708 const struct udevadm_cmd udevadm_hwdb
= {