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"
31 #include "hwdb-internal.h"
32 #include "hwdb-util.h"
35 #include "path-util.h"
36 #include "selinux-util.h"
38 #include "string-util.h"
44 * Generic udev properties, key-value database based on modalias strings.
45 * Uses a Patricia/radix trie to index all matches for efficient lookup.
48 static const char *arg_hwdb_bin_dir
= "/etc/udev";
49 static const char *arg_root
= "";
51 static const char * const conf_file_dirs
[] = {
53 UDEVLIBEXECDIR
"/hwdb.d",
57 /* in-memory trie objects */
59 struct trie_node
*root
;
60 struct strbuf
*strings
;
63 size_t children_count
;
68 /* prefix, common part for all children of this node */
71 /* sorted array of pointers to children nodes */
72 struct trie_child_entry
*children
;
73 uint8_t children_count
;
75 /* sorted array of key-value pairs */
76 struct trie_value_entry
*values
;
80 /* children array item with char (0-255) index */
81 struct trie_child_entry
{
83 struct trie_node
*child
;
86 /* value array item with key-value pairs */
87 struct trie_value_entry
{
92 uint16_t file_priority
;
95 static int trie_children_cmp(const void *v1
, const void *v2
) {
96 const struct trie_child_entry
*n1
= v1
;
97 const struct trie_child_entry
*n2
= v2
;
102 static int node_add_child(struct trie
*trie
, struct trie_node
*node
, struct trie_node
*node_child
, uint8_t c
) {
103 struct trie_child_entry
*child
;
105 /* extend array, add new entry, sort for bisection */
106 child
= reallocarray(node
->children
, node
->children_count
+ 1, sizeof(struct trie_child_entry
));
110 node
->children
= child
;
111 trie
->children_count
++;
112 node
->children
[node
->children_count
].c
= c
;
113 node
->children
[node
->children_count
].child
= node_child
;
114 node
->children_count
++;
115 qsort(node
->children
, node
->children_count
, sizeof(struct trie_child_entry
), trie_children_cmp
);
121 static struct trie_node
*node_lookup(const struct trie_node
*node
, uint8_t c
) {
122 struct trie_child_entry
*child
;
123 struct trie_child_entry search
;
126 child
= bsearch_safe(&search
, node
->children
, node
->children_count
, sizeof(struct trie_child_entry
), trie_children_cmp
);
132 static void trie_node_cleanup(struct trie_node
*node
) {
135 for (i
= 0; i
< node
->children_count
; i
++)
136 trie_node_cleanup(node
->children
[i
].child
);
137 free(node
->children
);
142 static void trie_free(struct trie
*trie
) {
147 trie_node_cleanup(trie
->root
);
149 strbuf_cleanup(trie
->strings
);
153 DEFINE_TRIVIAL_CLEANUP_FUNC(struct trie
*, trie_free
);
155 static int trie_values_cmp(const void *v1
, const void *v2
, void *arg
) {
156 const struct trie_value_entry
*val1
= v1
;
157 const struct trie_value_entry
*val2
= v2
;
158 struct trie
*trie
= arg
;
160 return strcmp(trie
->strings
->buf
+ val1
->key_off
,
161 trie
->strings
->buf
+ val2
->key_off
);
164 static int trie_node_add_value(struct trie
*trie
, struct trie_node
*node
,
165 const char *key
, const char *value
,
166 const char *filename
, uint16_t file_priority
, uint32_t line_number
) {
168 struct trie_value_entry
*val
;
170 k
= strbuf_add_string(trie
->strings
, key
, strlen(key
));
173 v
= strbuf_add_string(trie
->strings
, value
, strlen(value
));
176 fn
= strbuf_add_string(trie
->strings
, filename
, strlen(filename
));
180 if (node
->values_count
) {
181 struct trie_value_entry search
= {
186 val
= xbsearch_r(&search
, node
->values
, node
->values_count
, sizeof(struct trie_value_entry
), trie_values_cmp
, trie
);
188 /* At this point we have 2 identical properties on the same match-string.
189 * Since we process files in order, we just replace the previous value.
192 val
->filename_off
= fn
;
193 val
->file_priority
= file_priority
;
194 val
->line_number
= line_number
;
199 /* extend array, add new entry, sort for bisection */
200 val
= reallocarray(node
->values
, node
->values_count
+ 1, sizeof(struct trie_value_entry
));
203 trie
->values_count
++;
205 node
->values
[node
->values_count
].key_off
= k
;
206 node
->values
[node
->values_count
].value_off
= v
;
207 node
->values
[node
->values_count
].filename_off
= fn
;
208 node
->values
[node
->values_count
].file_priority
= file_priority
;
209 node
->values
[node
->values_count
].line_number
= line_number
;
210 node
->values_count
++;
211 qsort_r(node
->values
, node
->values_count
, sizeof(struct trie_value_entry
), trie_values_cmp
, trie
);
215 static int trie_insert(struct trie
*trie
, struct trie_node
*node
, const char *search
,
216 const char *key
, const char *value
,
217 const char *filename
, uint16_t file_priority
, uint32_t line_number
) {
224 struct trie_node
*child
;
226 for (p
= 0; (c
= trie
->strings
->buf
[node
->prefix_off
+ p
]); p
++) {
227 _cleanup_free_
char *s
= NULL
;
229 _cleanup_free_
struct trie_node
*new_child
= NULL
;
231 if (c
== search
[i
+ p
])
235 new_child
= new0(struct trie_node
, 1);
239 /* move values from parent to child */
240 new_child
->prefix_off
= node
->prefix_off
+ p
+1;
241 new_child
->children
= node
->children
;
242 new_child
->children_count
= node
->children_count
;
243 new_child
->values
= node
->values
;
244 new_child
->values_count
= node
->values_count
;
246 /* update parent; use strdup() because the source gets realloc()d */
247 s
= strndup(trie
->strings
->buf
+ node
->prefix_off
, p
);
251 off
= strbuf_add_string(trie
->strings
, s
, p
);
255 node
->prefix_off
= off
;
256 node
->children
= NULL
;
257 node
->children_count
= 0;
259 node
->values_count
= 0;
260 r
= node_add_child(trie
, node
, new_child
, c
);
264 new_child
= NULL
; /* avoid cleanup */
271 return trie_node_add_value(trie
, node
, key
, value
, filename
, file_priority
, line_number
);
273 child
= node_lookup(node
, c
);
278 child
= new0(struct trie_node
, 1);
282 off
= strbuf_add_string(trie
->strings
, search
+ i
+1, strlen(search
+ i
+1));
288 child
->prefix_off
= off
;
289 r
= node_add_child(trie
, node
, child
, c
);
295 return trie_node_add_value(trie
, child
, key
, value
, filename
, file_priority
, line_number
);
306 uint64_t strings_off
;
308 uint64_t nodes_count
;
309 uint64_t children_count
;
310 uint64_t values_count
;
313 /* calculate the storage space for the nodes, children arrays, value arrays */
314 static void trie_store_nodes_size(struct trie_f
*trie
, struct trie_node
*node
) {
317 for (i
= 0; i
< node
->children_count
; i
++)
318 trie_store_nodes_size(trie
, node
->children
[i
].child
);
320 trie
->strings_off
+= sizeof(struct trie_node_f
);
321 for (i
= 0; i
< node
->children_count
; i
++)
322 trie
->strings_off
+= sizeof(struct trie_child_entry_f
);
323 for (i
= 0; i
< node
->values_count
; i
++)
324 trie
->strings_off
+= sizeof(struct trie_value_entry2_f
);
327 static int64_t trie_store_nodes(struct trie_f
*trie
, struct trie_node
*node
) {
329 struct trie_node_f n
= {
330 .prefix_off
= htole64(trie
->strings_off
+ node
->prefix_off
),
331 .children_count
= node
->children_count
,
332 .values_count
= htole64(node
->values_count
),
334 _cleanup_free_
struct trie_child_entry_f
*children
= NULL
;
337 if (node
->children_count
) {
338 children
= new(struct trie_child_entry_f
, node
->children_count
);
343 /* post-order recursion */
344 for (i
= 0; i
< node
->children_count
; i
++) {
347 child_off
= trie_store_nodes(trie
, node
->children
[i
].child
);
351 children
[i
] = (struct trie_child_entry_f
) {
352 .c
= node
->children
[i
].c
,
353 .child_off
= htole64(child_off
),
358 node_off
= ftello(trie
->f
);
359 fwrite(&n
, sizeof(struct trie_node_f
), 1, trie
->f
);
362 /* append children array */
363 if (node
->children_count
) {
364 fwrite(children
, sizeof(struct trie_child_entry_f
), node
->children_count
, trie
->f
);
365 trie
->children_count
+= node
->children_count
;
368 /* append values array */
369 for (i
= 0; i
< node
->values_count
; i
++) {
370 struct trie_value_entry2_f v
= {
371 .key_off
= htole64(trie
->strings_off
+ node
->values
[i
].key_off
),
372 .value_off
= htole64(trie
->strings_off
+ node
->values
[i
].value_off
),
373 .filename_off
= htole64(trie
->strings_off
+ node
->values
[i
].filename_off
),
374 .line_number
= htole32(node
->values
[i
].line_number
),
375 .file_priority
= htole16(node
->values
[i
].file_priority
),
378 fwrite(&v
, sizeof(struct trie_value_entry2_f
), 1, trie
->f
);
380 trie
->values_count
+= node
->values_count
;
385 static int trie_store(struct trie
*trie
, const char *filename
) {
389 _cleanup_free_
char *filename_tmp
= NULL
;
393 struct trie_header_f h
= {
394 .signature
= HWDB_SIG
,
395 .tool_version
= htole64(atoi(PACKAGE_VERSION
)),
396 .header_size
= htole64(sizeof(struct trie_header_f
)),
397 .node_size
= htole64(sizeof(struct trie_node_f
)),
398 .child_entry_size
= htole64(sizeof(struct trie_child_entry_f
)),
399 .value_entry_size
= htole64(sizeof(struct trie_value_entry2_f
)),
403 /* calculate size of header, nodes, children entries, value entries */
404 t
.strings_off
= sizeof(struct trie_header_f
);
405 trie_store_nodes_size(&t
, trie
->root
);
407 r
= fopen_temporary(filename
, &t
.f
, &filename_tmp
);
410 fchmod(fileno(t
.f
), 0444);
413 if (fseeko(t
.f
, sizeof(struct trie_header_f
), SEEK_SET
) < 0)
416 root_off
= trie_store_nodes(&t
, trie
->root
);
417 h
.nodes_root_off
= htole64(root_off
);
419 h
.nodes_len
= htole64(pos
- sizeof(struct trie_header_f
));
421 /* write string buffer */
422 fwrite(trie
->strings
->buf
, trie
->strings
->len
, 1, t
.f
);
423 h
.strings_len
= htole64(trie
->strings
->len
);
427 h
.file_size
= htole64(size
);
428 if (fseeko(t
.f
, 0, SEEK_SET
) < 0)
430 fwrite(&h
, sizeof(struct trie_header_f
), 1, t
.f
);
436 if (fsync(fileno(t
.f
)) < 0)
438 if (rename(filename_tmp
, filename
) < 0)
441 /* write succeeded */
444 log_debug("=== trie on-disk ===");
445 log_debug("size: %8"PRIi64
" bytes", size
);
446 log_debug("header: %8zu bytes", sizeof(struct trie_header_f
));
447 log_debug("nodes: %8"PRIu64
" bytes (%8"PRIu64
")",
448 t
.nodes_count
* sizeof(struct trie_node_f
), t
.nodes_count
);
449 log_debug("child pointers: %8"PRIu64
" bytes (%8"PRIu64
")",
450 t
.children_count
* sizeof(struct trie_child_entry_f
), t
.children_count
);
451 log_debug("value pointers: %8"PRIu64
" bytes (%8"PRIu64
")",
452 t
.values_count
* sizeof(struct trie_value_entry2_f
), t
.values_count
);
453 log_debug("string store: %8zu bytes", trie
->strings
->len
);
454 log_debug("strings start: %8"PRIu64
, t
.strings_off
);
460 unlink(filename_tmp
);
464 static int insert_data(struct trie
*trie
, char **match_list
, char *line
,
465 const char *filename
, uint16_t file_priority
, uint32_t line_number
) {
466 char *value
, **entry
;
468 assert(line
[0] == ' ');
470 value
= strchr(line
, '=');
472 return log_syntax(NULL
, LOG_WARNING
, filename
, line_number
, EINVAL
,
473 "Key-value pair expected but got \"%s\", ignoring", line
);
478 /* Replace multiple leading spaces by a single space */
479 while (isblank(line
[0]) && isblank(line
[1]))
482 if (isempty(line
+ 1) || isempty(value
))
483 return log_syntax(NULL
, LOG_WARNING
, filename
, line_number
, EINVAL
,
484 "Empty %s in \"%s=%s\", ignoring",
485 isempty(line
+ 1) ? "key" : "value",
488 STRV_FOREACH(entry
, match_list
)
489 trie_insert(trie
, trie
->root
, *entry
, line
, value
, filename
, file_priority
, line_number
);
494 static int import_file(struct trie
*trie
, const char *filename
, uint16_t file_priority
) {
500 _cleanup_fclose_
FILE *f
= NULL
;
502 _cleanup_strv_free_
char **match_list
= NULL
;
503 uint32_t line_number
= 0;
507 f
= fopen(filename
, "re");
511 while (fgets(line
, sizeof(line
), f
)) {
521 /* strip trailing comment */
522 pos
= strchr(line
, '#');
526 /* strip trailing whitespace */
528 while (len
> 0 && isspace(line
[len
-1]))
537 if (line
[0] == ' ') {
538 log_syntax(NULL
, LOG_WARNING
, filename
, line_number
, EINVAL
,
539 "Match expected but got indented property \"%s\", ignoring line", line
);
543 /* start of record, first match */
546 match
= strdup(line
);
550 r
= strv_consume(&match_list
, match
);
558 log_syntax(NULL
, LOG_WARNING
, filename
, line_number
, EINVAL
,
559 "Property expected, ignoring record with no properties");
562 strv_clear(match_list
);
566 if (line
[0] != ' ') {
568 match
= strdup(line
);
572 r
= strv_consume(&match_list
, match
);
581 insert_data(trie
, match_list
, line
, filename
, file_priority
, line_number
);
588 strv_clear(match_list
);
592 if (line
[0] != ' ') {
593 log_syntax(NULL
, LOG_WARNING
, filename
, line_number
, EINVAL
,
594 "Property or empty line expected, got \"%s\", ignoring record", line
);
596 strv_clear(match_list
);
600 insert_data(trie
, match_list
, line
, filename
, file_priority
, line_number
);
605 if (state
== HW_MATCH
)
606 log_syntax(NULL
, LOG_WARNING
, filename
, line_number
, EINVAL
,
607 "Property expected, ignoring record with no properties");
612 static int hwdb_query(int argc
, char *argv
[], void *userdata
) {
613 _cleanup_(sd_hwdb_unrefp
) sd_hwdb
*hwdb
= NULL
;
614 const char *key
, *value
;
615 const char *modalias
;
623 r
= sd_hwdb_new(&hwdb
);
627 SD_HWDB_FOREACH_PROPERTY(hwdb
, modalias
, key
, value
)
628 printf("%s=%s\n", key
, value
);
633 static int hwdb_update(int argc
, char *argv
[], void *userdata
) {
634 _cleanup_free_
char *hwdb_bin
= NULL
;
635 _cleanup_(trie_freep
) struct trie
*trie
= NULL
;
636 _cleanup_strv_free_
char **files
= NULL
;
638 uint16_t file_priority
= 1;
641 trie
= new0(struct trie
, 1);
646 trie
->strings
= strbuf_new();
651 trie
->root
= new0(struct trie_node
, 1);
657 r
= conf_files_list_strv(&files
, ".hwdb", arg_root
, 0, conf_file_dirs
);
659 return log_error_errno(r
, "Failed to enumerate hwdb files: %m");
661 STRV_FOREACH(f
, files
) {
662 log_debug("Reading file \"%s\"", *f
);
663 import_file(trie
, *f
, file_priority
++);
666 strbuf_complete(trie
->strings
);
668 log_debug("=== trie in-memory ===");
669 log_debug("nodes: %8zu bytes (%8zu)",
670 trie
->nodes_count
* sizeof(struct trie_node
), trie
->nodes_count
);
671 log_debug("children arrays: %8zu bytes (%8zu)",
672 trie
->children_count
* sizeof(struct trie_child_entry
), trie
->children_count
);
673 log_debug("values arrays: %8zu bytes (%8zu)",
674 trie
->values_count
* sizeof(struct trie_value_entry
), trie
->values_count
);
675 log_debug("strings: %8zu bytes",
677 log_debug("strings incoming: %8zu bytes (%8zu)",
678 trie
->strings
->in_len
, trie
->strings
->in_count
);
679 log_debug("strings dedup'ed: %8zu bytes (%8zu)",
680 trie
->strings
->dedup_len
, trie
->strings
->dedup_count
);
682 hwdb_bin
= path_join(arg_root
, arg_hwdb_bin_dir
, "hwdb.bin");
686 mkdir_parents_label(hwdb_bin
, 0755);
687 r
= trie_store(trie
, hwdb_bin
);
689 return log_error_errno(r
, "Failure writing database %s: %m", hwdb_bin
);
691 return label_fix(hwdb_bin
, 0);
694 static void help(void) {
695 printf("Usage: %s OPTIONS COMMAND\n\n"
696 "Update or query the hardware database.\n\n"
697 " -h --help Show this help\n"
698 " --version Show package version\n"
699 " --usr Generate in " UDEVLIBEXECDIR
" instead of /etc/udev\n"
700 " -r --root=PATH Alternative root path in the filesystem\n\n"
702 " update Update the hwdb database\n"
703 " query MODALIAS Query database and print result\n",
704 program_invocation_short_name
);
707 static int parse_argv(int argc
, char *argv
[]) {
713 static const struct option options
[] = {
714 { "help", no_argument
, NULL
, 'h' },
715 { "version", no_argument
, NULL
, ARG_VERSION
},
716 { "usr", no_argument
, NULL
, ARG_USR
},
717 { "root", required_argument
, NULL
, 'r' },
726 while ((c
= getopt_long(argc
, argv
, "ut:r:h", options
, NULL
)) >= 0) {
737 arg_hwdb_bin_dir
= UDEVLIBEXECDIR
;
748 assert_not_reached("Unknown option");
755 static int hwdb_main(int argc
, char *argv
[]) {
756 static const Verb verbs
[] = {
757 { "update", 1, 1, 0, hwdb_update
},
758 { "query", 2, 2, 0, hwdb_query
},
762 return dispatch_verb(argc
, argv
, verbs
, NULL
);
765 int main (int argc
, char *argv
[]) {
768 log_parse_environment();
771 r
= parse_argv(argc
, argv
);
777 r
= hwdb_main(argc
, argv
);
780 return r
< 0 ? EXIT_FAILURE
: EXIT_SUCCESS
;