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_safe(&search
,
118 node
->children
, node
->children_count
, sizeof(struct trie_child_entry
),
125 static void trie_node_cleanup(struct trie_node
*node
) {
128 for (i
= 0; i
< node
->children_count
; i
++)
129 trie_node_cleanup(node
->children
[i
].child
);
130 free(node
->children
);
135 static int trie_values_cmp(const void *v1
, const void *v2
, void *arg
) {
136 const struct trie_value_entry
*val1
= v1
;
137 const struct trie_value_entry
*val2
= v2
;
138 struct trie
*trie
= arg
;
140 return strcmp(trie
->strings
->buf
+ val1
->key_off
,
141 trie
->strings
->buf
+ val2
->key_off
);
144 static int trie_node_add_value(struct trie
*trie
, struct trie_node
*node
,
145 const char *key
, const char *value
) {
147 struct trie_value_entry
*val
;
149 k
= strbuf_add_string(trie
->strings
, key
, strlen(key
));
152 v
= strbuf_add_string(trie
->strings
, value
, strlen(value
));
156 if (node
->values_count
) {
157 struct trie_value_entry search
= {
162 val
= xbsearch_r(&search
, node
->values
, node
->values_count
, sizeof(struct trie_value_entry
), trie_values_cmp
, trie
);
164 /* replace existing earlier key with new value */
170 /* extend array, add new entry, sort for bisection */
171 val
= reallocarray(node
->values
, node
->values_count
+ 1, sizeof(struct trie_value_entry
));
174 trie
->values_count
++;
176 node
->values
[node
->values_count
].key_off
= k
;
177 node
->values
[node
->values_count
].value_off
= v
;
178 node
->values_count
++;
179 qsort_r(node
->values
, node
->values_count
, sizeof(struct trie_value_entry
), trie_values_cmp
, trie
);
183 static int trie_insert(struct trie
*trie
, struct trie_node
*node
, const char *search
,
184 const char *key
, const char *value
) {
191 struct trie_node
*child
;
193 for (p
= 0; (c
= trie
->strings
->buf
[node
->prefix_off
+ p
]); p
++) {
194 _cleanup_free_
char *s
= NULL
;
196 _cleanup_free_
struct trie_node
*new_child
= NULL
;
198 if (c
== search
[i
+ p
])
202 new_child
= new0(struct trie_node
, 1);
206 /* move values from parent to child */
207 new_child
->prefix_off
= node
->prefix_off
+ p
+1;
208 new_child
->children
= node
->children
;
209 new_child
->children_count
= node
->children_count
;
210 new_child
->values
= node
->values
;
211 new_child
->values_count
= node
->values_count
;
213 /* update parent; use strdup() because the source gets realloc()d */
214 s
= strndup(trie
->strings
->buf
+ node
->prefix_off
, p
);
218 off
= strbuf_add_string(trie
->strings
, s
, p
);
222 node
->prefix_off
= off
;
223 node
->children
= NULL
;
224 node
->children_count
= 0;
226 node
->values_count
= 0;
227 err
= node_add_child(trie
, node
, new_child
, c
);
231 new_child
= NULL
; /* avoid cleanup */
238 return trie_node_add_value(trie
, node
, key
, value
);
240 child
= node_lookup(node
, c
);
245 child
= new0(struct trie_node
, 1);
249 off
= strbuf_add_string(trie
->strings
, search
+ i
+1, strlen(search
+ i
+1));
255 child
->prefix_off
= off
;
256 err
= node_add_child(trie
, node
, child
, c
);
262 return trie_node_add_value(trie
, child
, key
, value
);
273 uint64_t strings_off
;
275 uint64_t nodes_count
;
276 uint64_t children_count
;
277 uint64_t values_count
;
280 /* calculate the storage space for the nodes, children arrays, value arrays */
281 static void trie_store_nodes_size(struct trie_f
*trie
, struct trie_node
*node
) {
284 for (i
= 0; i
< node
->children_count
; i
++)
285 trie_store_nodes_size(trie
, node
->children
[i
].child
);
287 trie
->strings_off
+= sizeof(struct trie_node_f
);
288 for (i
= 0; i
< node
->children_count
; i
++)
289 trie
->strings_off
+= sizeof(struct trie_child_entry_f
);
290 for (i
= 0; i
< node
->values_count
; i
++)
291 trie
->strings_off
+= sizeof(struct trie_value_entry_f
);
294 static int64_t trie_store_nodes(struct trie_f
*trie
, struct trie_node
*node
) {
296 struct trie_node_f n
= {
297 .prefix_off
= htole64(trie
->strings_off
+ node
->prefix_off
),
298 .children_count
= node
->children_count
,
299 .values_count
= htole64(node
->values_count
),
301 struct trie_child_entry_f
*children
= NULL
;
304 if (node
->children_count
) {
305 children
= new0(struct trie_child_entry_f
, node
->children_count
);
310 /* post-order recursion */
311 for (i
= 0; i
< node
->children_count
; i
++) {
314 child_off
= trie_store_nodes(trie
, node
->children
[i
].child
);
319 children
[i
].c
= node
->children
[i
].c
;
320 children
[i
].child_off
= htole64(child_off
);
324 node_off
= ftello(trie
->f
);
325 fwrite(&n
, sizeof(struct trie_node_f
), 1, trie
->f
);
328 /* append children array */
329 if (node
->children_count
) {
330 fwrite(children
, sizeof(struct trie_child_entry_f
), node
->children_count
, trie
->f
);
331 trie
->children_count
+= node
->children_count
;
335 /* append values array */
336 for (i
= 0; i
< node
->values_count
; i
++) {
337 struct trie_value_entry_f v
= {
338 .key_off
= htole64(trie
->strings_off
+ node
->values
[i
].key_off
),
339 .value_off
= htole64(trie
->strings_off
+ node
->values
[i
].value_off
),
342 fwrite(&v
, sizeof(struct trie_value_entry_f
), 1, trie
->f
);
343 trie
->values_count
++;
349 static int trie_store(struct trie
*trie
, const char *filename
) {
353 _cleanup_free_
char *filename_tmp
= NULL
;
357 struct trie_header_f h
= {
358 .signature
= HWDB_SIG
,
359 .tool_version
= htole64(atoi(PACKAGE_VERSION
)),
360 .header_size
= htole64(sizeof(struct trie_header_f
)),
361 .node_size
= htole64(sizeof(struct trie_node_f
)),
362 .child_entry_size
= htole64(sizeof(struct trie_child_entry_f
)),
363 .value_entry_size
= htole64(sizeof(struct trie_value_entry_f
)),
367 /* calculate size of header, nodes, children entries, value entries */
368 t
.strings_off
= sizeof(struct trie_header_f
);
369 trie_store_nodes_size(&t
, trie
->root
);
371 err
= fopen_temporary(filename
, &t
.f
, &filename_tmp
);
374 fchmod(fileno(t
.f
), 0444);
377 if (fseeko(t
.f
, sizeof(struct trie_header_f
), SEEK_SET
) < 0)
379 root_off
= trie_store_nodes(&t
, trie
->root
);
380 h
.nodes_root_off
= htole64(root_off
);
382 h
.nodes_len
= htole64(pos
- sizeof(struct trie_header_f
));
384 /* write string buffer */
385 fwrite(trie
->strings
->buf
, trie
->strings
->len
, 1, t
.f
);
386 h
.strings_len
= htole64(trie
->strings
->len
);
390 h
.file_size
= htole64(size
);
391 if (fseeko(t
.f
, 0, SEEK_SET
< 0))
393 fwrite(&h
, sizeof(struct trie_header_f
), 1, t
.f
);
399 if (fsync(fileno(t
.f
)) < 0)
401 if (rename(filename_tmp
, filename
) < 0)
404 /* write succeeded */
407 log_debug("=== trie on-disk ===");
408 log_debug("size: %8"PRIi64
" bytes", size
);
409 log_debug("header: %8zu bytes", sizeof(struct trie_header_f
));
410 log_debug("nodes: %8"PRIu64
" bytes (%8"PRIu64
")",
411 t
.nodes_count
* sizeof(struct trie_node_f
), t
.nodes_count
);
412 log_debug("child pointers: %8"PRIu64
" bytes (%8"PRIu64
")",
413 t
.children_count
* sizeof(struct trie_child_entry_f
), t
.children_count
);
414 log_debug("value pointers: %8"PRIu64
" bytes (%8"PRIu64
")",
415 t
.values_count
* sizeof(struct trie_value_entry_f
), t
.values_count
);
416 log_debug("string store: %8zu bytes", trie
->strings
->len
);
417 log_debug("strings start: %8"PRIu64
, t
.strings_off
);
424 unlink(filename_tmp
);
428 static int insert_data(struct trie
*trie
, struct udev_list
*match_list
,
429 char *line
, const char *filename
) {
431 struct udev_list_entry
*entry
;
433 value
= strchr(line
, '=');
435 log_error("Error, key/value pair expected but got '%s' in '%s':", line
, filename
);
442 /* libudev requires properties to start with a space */
443 while (isblank(line
[0]) && isblank(line
[1]))
446 if (line
[0] == '\0' || value
[0] == '\0') {
447 log_error("Error, empty key or value '%s' in '%s':", line
, filename
);
451 udev_list_entry_foreach(entry
, udev_list_get_entry(match_list
))
452 trie_insert(trie
, trie
->root
, udev_list_entry_get_name(entry
), line
, value
);
457 static int import_file(struct udev
*udev
, struct trie
*trie
, const char *filename
) {
465 struct udev_list match_list
;
467 udev_list_init(udev
, &match_list
, false);
469 f
= fopen(filename
, "re");
473 while (fgets(line
, sizeof(line
), f
)) {
481 /* strip trailing comment */
482 pos
= strchr(line
, '#');
486 /* strip trailing whitespace */
488 while (len
> 0 && isspace(line
[len
-1]))
497 if (line
[0] == ' ') {
498 log_error("Error, MATCH expected but got '%s' in '%s':", line
, filename
);
502 /* start of record, first match */
504 udev_list_entry_add(&match_list
, line
, NULL
);
509 log_error("Error, DATA expected but got empty line in '%s':", filename
);
511 udev_list_cleanup(&match_list
);
516 if (line
[0] != ' ') {
517 udev_list_entry_add(&match_list
, line
, NULL
);
523 insert_data(trie
, &match_list
, line
, filename
);
530 udev_list_cleanup(&match_list
);
534 if (line
[0] != ' ') {
535 log_error("Error, DATA expected but got '%s' in '%s':", line
, filename
);
537 udev_list_cleanup(&match_list
);
541 insert_data(trie
, &match_list
, line
, filename
);
547 udev_list_cleanup(&match_list
);
551 static void help(void) {
552 printf("%s hwdb [OPTIONS]\n\n"
553 " -h --help Print this message\n"
554 " -V --version Print version of the program\n"
555 " -u --update Update the hardware database\n"
556 " --usr Generate in " UDEVLIBEXECDIR
" instead of /etc/udev\n"
557 " -t --test=MODALIAS Query database and print result\n"
558 " -r --root=PATH Alternative root path in the filesystem\n\n"
560 "The sub-command 'hwdb' is deprecated, and is left for backwards compatibility.\n"
561 "Please use systemd-hwdb instead.\n"
562 , program_invocation_short_name
);
565 static int adm_hwdb(struct udev
*udev
, int argc
, char *argv
[]) {
570 static const struct option options
[] = {
571 { "update", no_argument
, NULL
, 'u' },
572 { "usr", no_argument
, NULL
, ARG_USR
},
573 { "test", required_argument
, NULL
, 't' },
574 { "root", required_argument
, NULL
, 'r' },
575 { "version", no_argument
, NULL
, 'V' },
576 { "help", no_argument
, NULL
, 'h' },
579 const char *test
= NULL
;
580 const char *root
= "";
581 const char *hwdb_bin_dir
= "/etc/udev";
583 struct trie
*trie
= NULL
;
585 int rc
= EXIT_SUCCESS
;
587 while ((c
= getopt_long(argc
, argv
, "ut:r:Vh", options
, NULL
)) >= 0)
593 hwdb_bin_dir
= UDEVLIBEXECDIR
;
610 assert_not_reached("Unknown option");
613 if (!update
&& !test
) {
614 log_error("Either --update or --test must be used");
620 _cleanup_free_
char *hwdb_bin
= NULL
;
622 trie
= new0(struct trie
, 1);
629 trie
->strings
= strbuf_new();
630 if (!trie
->strings
) {
636 trie
->root
= new0(struct trie_node
, 1);
643 err
= conf_files_list_strv(&files
, ".hwdb", root
, 0, conf_file_dirs
);
645 log_error_errno(err
, "failed to enumerate hwdb files: %m");
649 STRV_FOREACH(f
, files
) {
650 log_debug("reading file '%s'", *f
);
651 import_file(udev
, trie
, *f
);
655 strbuf_complete(trie
->strings
);
657 log_debug("=== trie in-memory ===");
658 log_debug("nodes: %8zu bytes (%8zu)",
659 trie
->nodes_count
* sizeof(struct trie_node
), trie
->nodes_count
);
660 log_debug("children arrays: %8zu bytes (%8zu)",
661 trie
->children_count
* sizeof(struct trie_child_entry
), trie
->children_count
);
662 log_debug("values arrays: %8zu bytes (%8zu)",
663 trie
->values_count
* sizeof(struct trie_value_entry
), trie
->values_count
);
664 log_debug("strings: %8zu bytes",
666 log_debug("strings incoming: %8zu bytes (%8zu)",
667 trie
->strings
->in_len
, trie
->strings
->in_count
);
668 log_debug("strings dedup'ed: %8zu bytes (%8zu)",
669 trie
->strings
->dedup_len
, trie
->strings
->dedup_count
);
671 hwdb_bin
= strjoin(root
, "/", hwdb_bin_dir
, "/hwdb.bin");
677 mkdir_parents_label(hwdb_bin
, 0755);
679 err
= trie_store(trie
, hwdb_bin
);
681 log_error_errno(err
, "Failure writing database %s: %m", hwdb_bin
);
685 (void) label_fix(hwdb_bin
, 0);
689 _cleanup_(sd_hwdb_unrefp
) sd_hwdb
*hwdb
= NULL
;
692 r
= sd_hwdb_new(&hwdb
);
694 const char *key
, *value
;
696 SD_HWDB_FOREACH_PROPERTY(hwdb
, test
, key
, value
)
697 printf("%s=%s\n", key
, value
);
703 trie_node_cleanup(trie
->root
);
704 strbuf_cleanup(trie
->strings
);
710 const struct udevadm_cmd udevadm_hwdb
= {