]>
git.ipfire.org Git - thirdparty/systemd.git/blob - src/libsystemd/sd-hwdb/hwdb-util.c
1 /* SPDX-License-Identifier: LGPL-2.1+ */
5 #include "alloc-util.h"
6 #include "conf-files.h"
10 #include "hwdb-internal.h"
11 #include "hwdb-util.h"
14 #include "path-util.h"
16 #include "string-util.h"
19 static const char *default_hwdb_bin_dir
= "/etc/udev";
20 static const char * const conf_file_dirs
[] = {
22 UDEVLIBEXECDIR
"/hwdb.d",
27 * Generic udev properties, key-value database based on modalias strings.
28 * Uses a Patricia/radix trie to index all matches for efficient lookup.
31 /* in-memory trie objects */
33 struct trie_node
*root
;
34 struct strbuf
*strings
;
37 size_t children_count
;
42 /* prefix, common part for all children of this node */
45 /* sorted array of pointers to children nodes */
46 struct trie_child_entry
*children
;
47 uint8_t children_count
;
49 /* sorted array of key-value pairs */
50 struct trie_value_entry
*values
;
54 /* children array item with char (0-255) index */
55 struct trie_child_entry
{
57 struct trie_node
*child
;
60 /* value array item with key-value pairs */
61 struct trie_value_entry
{
66 uint16_t file_priority
;
69 static int trie_children_cmp(const struct trie_child_entry
*a
, const struct trie_child_entry
*b
) {
70 return CMP(a
->c
, b
->c
);
73 static int node_add_child(struct trie
*trie
, struct trie_node
*node
, struct trie_node
*node_child
, uint8_t c
) {
74 struct trie_child_entry
*child
;
76 /* extend array, add new entry, sort for bisection */
77 child
= reallocarray(node
->children
, node
->children_count
+ 1, sizeof(struct trie_child_entry
));
81 node
->children
= child
;
82 trie
->children_count
++;
83 node
->children
[node
->children_count
].c
= c
;
84 node
->children
[node
->children_count
].child
= node_child
;
85 node
->children_count
++;
86 typesafe_qsort(node
->children
, node
->children_count
, trie_children_cmp
);
92 static struct trie_node
*node_lookup(const struct trie_node
*node
, uint8_t c
) {
93 struct trie_child_entry
*child
;
94 struct trie_child_entry search
;
97 child
= typesafe_bsearch(&search
, node
->children
, node
->children_count
, trie_children_cmp
);
103 static void trie_node_cleanup(struct trie_node
*node
) {
109 for (i
= 0; i
< node
->children_count
; i
++)
110 trie_node_cleanup(node
->children
[i
].child
);
111 free(node
->children
);
116 static void trie_free(struct trie
*trie
) {
120 trie_node_cleanup(trie
->root
);
121 strbuf_cleanup(trie
->strings
);
125 DEFINE_TRIVIAL_CLEANUP_FUNC(struct trie
*, trie_free
);
127 static int trie_values_cmp(const struct trie_value_entry
*a
, const struct trie_value_entry
*b
, struct trie
*trie
) {
128 return strcmp(trie
->strings
->buf
+ a
->key_off
,
129 trie
->strings
->buf
+ b
->key_off
);
132 static int trie_node_add_value(struct trie
*trie
, struct trie_node
*node
,
133 const char *key
, const char *value
,
134 const char *filename
, uint16_t file_priority
, uint32_t line_number
, bool compat
) {
136 struct trie_value_entry
*val
;
138 k
= strbuf_add_string(trie
->strings
, key
, strlen(key
));
141 v
= strbuf_add_string(trie
->strings
, value
, strlen(value
));
146 fn
= strbuf_add_string(trie
->strings
, filename
, strlen(filename
));
151 if (node
->values_count
) {
152 struct trie_value_entry search
= {
157 val
= typesafe_bsearch_r(&search
, node
->values
, node
->values_count
, trie_values_cmp
, trie
);
159 /* At this point we have 2 identical properties on the same match-string.
160 * Since we process files in order, we just replace the previous value. */
162 val
->filename_off
= fn
;
163 val
->file_priority
= file_priority
;
164 val
->line_number
= line_number
;
169 /* extend array, add new entry, sort for bisection */
170 val
= reallocarray(node
->values
, node
->values_count
+ 1, sizeof(struct trie_value_entry
));
173 trie
->values_count
++;
175 node
->values
[node
->values_count
] = (struct trie_value_entry
) {
179 .file_priority
= file_priority
,
180 .line_number
= line_number
,
182 node
->values_count
++;
183 typesafe_qsort_r(node
->values
, node
->values_count
, trie_values_cmp
, trie
);
187 static int trie_insert(struct trie
*trie
, struct trie_node
*node
, const char *search
,
188 const char *key
, const char *value
,
189 const char *filename
, uint16_t file_priority
, uint32_t line_number
, bool compat
) {
196 struct trie_node
*child
;
198 for (p
= 0; (c
= trie
->strings
->buf
[node
->prefix_off
+ p
]); p
++) {
199 _cleanup_free_
struct trie_node
*new_child
= NULL
;
200 _cleanup_free_
char *s
= NULL
;
203 if (c
== search
[i
+ p
])
207 new_child
= new(struct trie_node
, 1);
211 /* move values from parent to child */
212 *new_child
= (struct trie_node
) {
213 .prefix_off
= node
->prefix_off
+ p
+1,
214 .children
= node
->children
,
215 .children_count
= node
->children_count
,
216 .values
= node
->values
,
217 .values_count
= node
->values_count
,
220 /* update parent; use strdup() because the source gets realloc()d */
221 s
= strndup(trie
->strings
->buf
+ node
->prefix_off
, p
);
225 off
= strbuf_add_string(trie
->strings
, s
, p
);
229 *node
= (struct trie_node
) {
232 r
= node_add_child(trie
, node
, new_child
, c
);
236 new_child
= NULL
; /* avoid cleanup */
243 return trie_node_add_value(trie
, node
, key
, value
, filename
, file_priority
, line_number
, compat
);
245 child
= node_lookup(node
, c
);
247 _cleanup_free_
struct trie_node
*new_child
= NULL
;
251 new_child
= new(struct trie_node
, 1);
255 off
= strbuf_add_string(trie
->strings
, search
+ i
+1, strlen(search
+ i
+1));
259 *new_child
= (struct trie_node
) {
263 r
= node_add_child(trie
, node
, new_child
, c
);
267 child
= TAKE_PTR(new_child
);
268 return trie_node_add_value(trie
, child
, key
, value
, filename
, file_priority
, line_number
, compat
);
279 uint64_t strings_off
;
281 uint64_t nodes_count
;
282 uint64_t children_count
;
283 uint64_t values_count
;
286 /* calculate the storage space for the nodes, children arrays, value arrays */
287 static void trie_store_nodes_size(struct trie_f
*trie
, struct trie_node
*node
, bool compat
) {
290 for (i
= 0; i
< node
->children_count
; i
++)
291 trie_store_nodes_size(trie
, node
->children
[i
].child
, compat
);
293 trie
->strings_off
+= sizeof(struct trie_node_f
);
294 for (i
= 0; i
< node
->children_count
; i
++)
295 trie
->strings_off
+= sizeof(struct trie_child_entry_f
);
296 for (i
= 0; i
< node
->values_count
; i
++)
297 trie
->strings_off
+= compat
? sizeof(struct trie_value_entry_f
) : sizeof(struct trie_value_entry2_f
);
300 static int64_t trie_store_nodes(struct trie_f
*trie
, struct trie_node
*node
, bool compat
) {
302 struct trie_node_f n
= {
303 .prefix_off
= htole64(trie
->strings_off
+ node
->prefix_off
),
304 .children_count
= node
->children_count
,
305 .values_count
= htole64(node
->values_count
),
307 _cleanup_free_
struct trie_child_entry_f
*children
= NULL
;
310 if (node
->children_count
) {
311 children
= new(struct trie_child_entry_f
, node
->children_count
);
316 /* post-order recursion */
317 for (i
= 0; i
< node
->children_count
; i
++) {
320 child_off
= trie_store_nodes(trie
, node
->children
[i
].child
, compat
);
324 children
[i
] = (struct trie_child_entry_f
) {
325 .c
= node
->children
[i
].c
,
326 .child_off
= htole64(child_off
),
331 node_off
= ftello(trie
->f
);
332 fwrite(&n
, sizeof(struct trie_node_f
), 1, trie
->f
);
335 /* append children array */
336 if (node
->children_count
) {
337 fwrite(children
, sizeof(struct trie_child_entry_f
), node
->children_count
, trie
->f
);
338 trie
->children_count
+= node
->children_count
;
341 /* append values array */
342 for (i
= 0; i
< node
->values_count
; i
++) {
343 struct trie_value_entry2_f v
= {
344 .key_off
= htole64(trie
->strings_off
+ node
->values
[i
].key_off
),
345 .value_off
= htole64(trie
->strings_off
+ node
->values
[i
].value_off
),
346 .filename_off
= htole64(trie
->strings_off
+ node
->values
[i
].filename_off
),
347 .line_number
= htole32(node
->values
[i
].line_number
),
348 .file_priority
= htole16(node
->values
[i
].file_priority
),
351 fwrite(&v
, compat
? sizeof(struct trie_value_entry_f
) : sizeof(struct trie_value_entry2_f
), 1, trie
->f
);
353 trie
->values_count
+= node
->values_count
;
358 static int trie_store(struct trie
*trie
, const char *filename
, bool compat
) {
362 _cleanup_free_
char *filename_tmp
= NULL
;
366 struct trie_header_f h
= {
367 .signature
= HWDB_SIG
,
368 .tool_version
= htole64(atoi(PACKAGE_VERSION
)),
369 .header_size
= htole64(sizeof(struct trie_header_f
)),
370 .node_size
= htole64(sizeof(struct trie_node_f
)),
371 .child_entry_size
= htole64(sizeof(struct trie_child_entry_f
)),
372 .value_entry_size
= htole64(compat
? sizeof(struct trie_value_entry_f
) : sizeof(struct trie_value_entry2_f
)),
376 /* calculate size of header, nodes, children entries, value entries */
377 t
.strings_off
= sizeof(struct trie_header_f
);
378 trie_store_nodes_size(&t
, trie
->root
, compat
);
380 r
= fopen_temporary(filename
, &t
.f
, &filename_tmp
);
383 fchmod(fileno(t
.f
), 0444);
386 if (fseeko(t
.f
, sizeof(struct trie_header_f
), SEEK_SET
) < 0)
389 root_off
= trie_store_nodes(&t
, trie
->root
, compat
);
390 h
.nodes_root_off
= htole64(root_off
);
392 h
.nodes_len
= htole64(pos
- sizeof(struct trie_header_f
));
394 /* write string buffer */
395 fwrite(trie
->strings
->buf
, trie
->strings
->len
, 1, t
.f
);
396 h
.strings_len
= htole64(trie
->strings
->len
);
400 h
.file_size
= htole64(size
);
401 if (fseeko(t
.f
, 0, SEEK_SET
) < 0)
403 fwrite(&h
, sizeof(struct trie_header_f
), 1, t
.f
);
409 if (fsync(fileno(t
.f
)) < 0)
411 if (rename(filename_tmp
, filename
) < 0)
414 /* write succeeded */
417 log_debug("=== trie on-disk ===");
418 log_debug("size: %8"PRIi64
" bytes", size
);
419 log_debug("header: %8zu bytes", sizeof(struct trie_header_f
));
420 log_debug("nodes: %8"PRIu64
" bytes (%8"PRIu64
")",
421 t
.nodes_count
* sizeof(struct trie_node_f
), t
.nodes_count
);
422 log_debug("child pointers: %8"PRIu64
" bytes (%8"PRIu64
")",
423 t
.children_count
* sizeof(struct trie_child_entry_f
), t
.children_count
);
424 log_debug("value pointers: %8"PRIu64
" bytes (%8"PRIu64
")",
425 t
.values_count
* (compat
? sizeof(struct trie_value_entry_f
) : sizeof(struct trie_value_entry2_f
)), t
.values_count
);
426 log_debug("string store: %8zu bytes", trie
->strings
->len
);
427 log_debug("strings start: %8"PRIu64
, t
.strings_off
);
433 unlink(filename_tmp
);
437 static int insert_data(struct trie
*trie
, char **match_list
, char *line
, const char *filename
,
438 uint16_t file_priority
, uint32_t line_number
, bool compat
) {
439 char *value
, **entry
;
441 assert(line
[0] == ' ');
443 value
= strchr(line
, '=');
445 return log_syntax(NULL
, LOG_WARNING
, filename
, line_number
, EINVAL
,
446 "Key-value pair expected but got \"%s\", ignoring", line
);
451 /* Replace multiple leading spaces by a single space */
452 while (isblank(line
[0]) && isblank(line
[1]))
455 if (isempty(line
+ 1) || isempty(value
))
456 return log_syntax(NULL
, LOG_WARNING
, filename
, line_number
, EINVAL
,
457 "Empty %s in \"%s=%s\", ignoring",
458 isempty(line
+ 1) ? "key" : "value",
461 STRV_FOREACH(entry
, match_list
)
462 trie_insert(trie
, trie
->root
, *entry
, line
, value
, filename
, file_priority
, line_number
, compat
);
467 static int import_file(struct trie
*trie
, const char *filename
, uint16_t file_priority
, bool compat
) {
473 _cleanup_fclose_
FILE *f
= NULL
;
475 _cleanup_strv_free_
char **match_list
= NULL
;
476 uint32_t line_number
= 0;
480 f
= fopen(filename
, "re");
484 while (fgets(line
, sizeof(line
), f
)) {
494 /* strip trailing comment */
495 pos
= strchr(line
, '#');
499 /* strip trailing whitespace */
501 while (len
> 0 && isspace(line
[len
-1]))
510 if (line
[0] == ' ') {
511 log_syntax(NULL
, LOG_WARNING
, filename
, line_number
, EINVAL
,
512 "Match expected but got indented property \"%s\", ignoring line", line
);
517 /* start of record, first match */
520 match
= strdup(line
);
524 err
= strv_consume(&match_list
, match
);
532 log_syntax(NULL
, LOG_WARNING
, filename
, line_number
, EINVAL
,
533 "Property expected, ignoring record with no properties");
536 strv_clear(match_list
);
540 if (line
[0] != ' ') {
542 match
= strdup(line
);
546 err
= strv_consume(&match_list
, match
);
555 err
= insert_data(trie
, match_list
, line
, filename
, file_priority
, line_number
, compat
);
564 strv_clear(match_list
);
568 if (line
[0] != ' ') {
569 log_syntax(NULL
, LOG_WARNING
, filename
, line_number
, EINVAL
,
570 "Property or empty line expected, got \"%s\", ignoring record", line
);
573 strv_clear(match_list
);
577 err
= insert_data(trie
, match_list
, line
, filename
, file_priority
, line_number
, compat
);
584 if (state
== HW_MATCH
)
585 log_syntax(NULL
, LOG_WARNING
, filename
, line_number
, EINVAL
,
586 "Property expected, ignoring record with no properties");
591 int hwdb_update(const char *root
, const char *hwdb_bin_dir
, bool strict
, bool compat
) {
592 _cleanup_free_
char *hwdb_bin
= NULL
;
593 _cleanup_(trie_freep
) struct trie
*trie
= NULL
;
594 _cleanup_strv_free_
char **files
= NULL
;
596 uint16_t file_priority
= 1;
599 /* The argument 'compat' controls the format version of database. If false, then hwdb.bin will be created with
600 * additional information such that priority, line number, and filename of database source. If true, then hwdb.bin
601 * will be created without the information. systemd-hwdb command should set the argument false, and 'udevadm hwdb'
602 * command should set it true. */
604 trie
= new0(struct trie
, 1);
609 trie
->strings
= strbuf_new();
614 trie
->root
= new0(struct trie_node
, 1);
620 err
= conf_files_list_strv(&files
, ".hwdb", root
, 0, conf_file_dirs
);
622 return log_error_errno(err
, "Failed to enumerate hwdb files: %m");
624 STRV_FOREACH(f
, files
) {
625 log_debug("Reading file \"%s\"", *f
);
626 err
= import_file(trie
, *f
, file_priority
++, compat
);
627 if (err
< 0 && strict
)
631 strbuf_complete(trie
->strings
);
633 log_debug("=== trie in-memory ===");
634 log_debug("nodes: %8zu bytes (%8zu)",
635 trie
->nodes_count
* sizeof(struct trie_node
), trie
->nodes_count
);
636 log_debug("children arrays: %8zu bytes (%8zu)",
637 trie
->children_count
* sizeof(struct trie_child_entry
), trie
->children_count
);
638 log_debug("values arrays: %8zu bytes (%8zu)",
639 trie
->values_count
* sizeof(struct trie_value_entry
), trie
->values_count
);
640 log_debug("strings: %8zu bytes",
642 log_debug("strings incoming: %8zu bytes (%8zu)",
643 trie
->strings
->in_len
, trie
->strings
->in_count
);
644 log_debug("strings dedup'ed: %8zu bytes (%8zu)",
645 trie
->strings
->dedup_len
, trie
->strings
->dedup_count
);
647 hwdb_bin
= path_join(root
, hwdb_bin_dir
?: default_hwdb_bin_dir
, "hwdb.bin");
651 mkdir_parents_label(hwdb_bin
, 0755);
652 err
= trie_store(trie
, hwdb_bin
, compat
);
654 return log_error_errno(err
, "Failed to write database %s: %m", hwdb_bin
);
656 err
= label_fix(hwdb_bin
, 0);