]>
git.ipfire.org Git - thirdparty/systemd.git/blob - src/udev/udevadm-hwdb.c
1 /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
4 This file is part of systemd.
6 Copyright 2012 Kay Sievers <kay@vrfy.org>
8 systemd is free software; you can redistribute it and/or modify it
9 under the terms of the GNU Lesser General Public License as published by
10 the Free Software Foundation; either version 2.1 of the License, or
11 (at your option) any later version.
13 systemd is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 Lesser General Public License for more details.
18 You should have received a copy of the GNU Lesser General Public License
19 along with systemd; If not, see <http://www.gnu.org/licenses/>.
27 #include "alloc-util.h"
28 #include "conf-files.h"
31 #include "hwdb-internal.h"
32 #include "hwdb-util.h"
34 #include "string-util.h"
39 * Generic udev properties, key/value database based on modalias strings.
40 * Uses a Patricia/radix trie to index all matches for efficient lookup.
43 static const char * const conf_file_dirs
[] = {
45 UDEVLIBEXECDIR
"/hwdb.d",
49 /* in-memory trie objects */
51 struct trie_node
*root
;
52 struct strbuf
*strings
;
55 size_t children_count
;
60 /* prefix, common part for all children of this node */
63 /* sorted array of pointers to children nodes */
64 struct trie_child_entry
*children
;
65 uint8_t children_count
;
67 /* sorted array of key/value pairs */
68 struct trie_value_entry
*values
;
72 /* children array item with char (0-255) index */
73 struct trie_child_entry
{
75 struct trie_node
*child
;
78 /* value array item with key/value pairs */
79 struct trie_value_entry
{
84 static int trie_children_cmp(const void *v1
, const void *v2
) {
85 const struct trie_child_entry
*n1
= v1
;
86 const struct trie_child_entry
*n2
= v2
;
91 static int node_add_child(struct trie
*trie
, struct trie_node
*node
, struct trie_node
*node_child
, uint8_t c
) {
92 struct trie_child_entry
*child
;
94 /* extend array, add new entry, sort for bisection */
95 child
= realloc(node
->children
, (node
->children_count
+ 1) * sizeof(struct trie_child_entry
));
99 node
->children
= child
;
100 trie
->children_count
++;
101 node
->children
[node
->children_count
].c
= c
;
102 node
->children
[node
->children_count
].child
= node_child
;
103 node
->children_count
++;
104 qsort(node
->children
, node
->children_count
, sizeof(struct trie_child_entry
), trie_children_cmp
);
110 static struct trie_node
*node_lookup(const struct trie_node
*node
, uint8_t c
) {
111 struct trie_child_entry
*child
;
112 struct trie_child_entry search
;
115 child
= bsearch(&search
, node
->children
, node
->children_count
, sizeof(struct trie_child_entry
), trie_children_cmp
);
121 static void trie_node_cleanup(struct trie_node
*node
) {
124 for (i
= 0; i
< node
->children_count
; i
++)
125 trie_node_cleanup(node
->children
[i
].child
);
126 free(node
->children
);
131 static int trie_values_cmp(const void *v1
, const void *v2
, void *arg
) {
132 const struct trie_value_entry
*val1
= v1
;
133 const struct trie_value_entry
*val2
= v2
;
134 struct trie
*trie
= arg
;
136 return strcmp(trie
->strings
->buf
+ val1
->key_off
,
137 trie
->strings
->buf
+ val2
->key_off
);
140 static int trie_node_add_value(struct trie
*trie
, struct trie_node
*node
,
141 const char *key
, const char *value
) {
143 struct trie_value_entry
*val
;
145 k
= strbuf_add_string(trie
->strings
, key
, strlen(key
));
148 v
= strbuf_add_string(trie
->strings
, value
, strlen(value
));
152 if (node
->values_count
) {
153 struct trie_value_entry search
= {
158 val
= xbsearch_r(&search
, node
->values
, node
->values_count
, sizeof(struct trie_value_entry
), trie_values_cmp
, trie
);
160 /* replace existing earlier key with new value */
166 /* extend array, add new entry, sort for bisection */
167 val
= realloc(node
->values
, (node
->values_count
+ 1) * sizeof(struct trie_value_entry
));
170 trie
->values_count
++;
172 node
->values
[node
->values_count
].key_off
= k
;
173 node
->values
[node
->values_count
].value_off
= v
;
174 node
->values_count
++;
175 qsort_r(node
->values
, node
->values_count
, sizeof(struct trie_value_entry
), trie_values_cmp
, trie
);
179 static int trie_insert(struct trie
*trie
, struct trie_node
*node
, const char *search
,
180 const char *key
, const char *value
) {
187 struct trie_node
*child
;
189 for (p
= 0; (c
= trie
->strings
->buf
[node
->prefix_off
+ p
]); p
++) {
190 _cleanup_free_
char *s
= NULL
;
192 _cleanup_free_
struct trie_node
*new_child
= NULL
;
194 if (c
== search
[i
+ p
])
198 new_child
= new0(struct trie_node
, 1);
202 /* move values from parent to child */
203 new_child
->prefix_off
= node
->prefix_off
+ p
+1;
204 new_child
->children
= node
->children
;
205 new_child
->children_count
= node
->children_count
;
206 new_child
->values
= node
->values
;
207 new_child
->values_count
= node
->values_count
;
209 /* update parent; use strdup() because the source gets realloc()d */
210 s
= strndup(trie
->strings
->buf
+ node
->prefix_off
, p
);
214 off
= strbuf_add_string(trie
->strings
, s
, p
);
218 node
->prefix_off
= off
;
219 node
->children
= NULL
;
220 node
->children_count
= 0;
222 node
->values_count
= 0;
223 err
= node_add_child(trie
, node
, new_child
, c
);
227 new_child
= NULL
; /* avoid cleanup */
234 return trie_node_add_value(trie
, node
, key
, value
);
236 child
= node_lookup(node
, c
);
241 child
= new0(struct trie_node
, 1);
245 off
= strbuf_add_string(trie
->strings
, search
+ i
+1, strlen(search
+ i
+1));
251 child
->prefix_off
= off
;
252 err
= node_add_child(trie
, node
, child
, c
);
258 return trie_node_add_value(trie
, child
, key
, value
);
269 uint64_t strings_off
;
271 uint64_t nodes_count
;
272 uint64_t children_count
;
273 uint64_t values_count
;
276 /* calculate the storage space for the nodes, children arrays, value arrays */
277 static void trie_store_nodes_size(struct trie_f
*trie
, struct trie_node
*node
) {
280 for (i
= 0; i
< node
->children_count
; i
++)
281 trie_store_nodes_size(trie
, node
->children
[i
].child
);
283 trie
->strings_off
+= sizeof(struct trie_node_f
);
284 for (i
= 0; i
< node
->children_count
; i
++)
285 trie
->strings_off
+= sizeof(struct trie_child_entry_f
);
286 for (i
= 0; i
< node
->values_count
; i
++)
287 trie
->strings_off
+= sizeof(struct trie_value_entry_f
);
290 static int64_t trie_store_nodes(struct trie_f
*trie
, struct trie_node
*node
) {
292 struct trie_node_f n
= {
293 .prefix_off
= htole64(trie
->strings_off
+ node
->prefix_off
),
294 .children_count
= node
->children_count
,
295 .values_count
= htole64(node
->values_count
),
297 struct trie_child_entry_f
*children
= NULL
;
300 if (node
->children_count
) {
301 children
= new0(struct trie_child_entry_f
, node
->children_count
);
306 /* post-order recursion */
307 for (i
= 0; i
< node
->children_count
; i
++) {
310 child_off
= trie_store_nodes(trie
, node
->children
[i
].child
);
315 children
[i
].c
= node
->children
[i
].c
;
316 children
[i
].child_off
= htole64(child_off
);
320 node_off
= ftello(trie
->f
);
321 fwrite(&n
, sizeof(struct trie_node_f
), 1, trie
->f
);
324 /* append children array */
325 if (node
->children_count
) {
326 fwrite(children
, sizeof(struct trie_child_entry_f
), node
->children_count
, trie
->f
);
327 trie
->children_count
+= node
->children_count
;
331 /* append values array */
332 for (i
= 0; i
< node
->values_count
; i
++) {
333 struct trie_value_entry_f v
= {
334 .key_off
= htole64(trie
->strings_off
+ node
->values
[i
].key_off
),
335 .value_off
= htole64(trie
->strings_off
+ node
->values
[i
].value_off
),
338 fwrite(&v
, sizeof(struct trie_value_entry_f
), 1, trie
->f
);
339 trie
->values_count
++;
345 static int trie_store(struct trie
*trie
, const char *filename
) {
349 _cleanup_free_
char *filename_tmp
= NULL
;
353 struct trie_header_f h
= {
354 .signature
= HWDB_SIG
,
355 .tool_version
= htole64(atoi(VERSION
)),
356 .header_size
= htole64(sizeof(struct trie_header_f
)),
357 .node_size
= htole64(sizeof(struct trie_node_f
)),
358 .child_entry_size
= htole64(sizeof(struct trie_child_entry_f
)),
359 .value_entry_size
= htole64(sizeof(struct trie_value_entry_f
)),
363 /* calculate size of header, nodes, children entries, value entries */
364 t
.strings_off
= sizeof(struct trie_header_f
);
365 trie_store_nodes_size(&t
, trie
->root
);
367 err
= fopen_temporary(filename
, &t
.f
, &filename_tmp
);
370 fchmod(fileno(t
.f
), 0444);
373 err
= fseeko(t
.f
, sizeof(struct trie_header_f
), SEEK_SET
);
376 unlink_noerrno(filename_tmp
);
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 err
= fseeko(t
.f
, 0, SEEK_SET
);
394 unlink_noerrno(filename_tmp
);
397 fwrite(&h
, sizeof(struct trie_header_f
), 1, t
.f
);
402 if (err
< 0 || rename(filename_tmp
, filename
) < 0) {
403 unlink_noerrno(filename_tmp
);
404 return err
< 0 ? err
: -errno
;
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
);
422 static int insert_data(struct trie
*trie
, struct udev_list
*match_list
,
423 char *line
, const char *filename
) {
425 struct udev_list_entry
*entry
;
427 value
= strchr(line
, '=');
429 log_error("Error, key/value pair expected but got '%s' in '%s':", line
, filename
);
436 /* libudev requires properties to start with a space */
437 while (isblank(line
[0]) && isblank(line
[1]))
440 if (line
[0] == '\0' || value
[0] == '\0') {
441 log_error("Error, empty key or value '%s' in '%s':", line
, filename
);
445 udev_list_entry_foreach(entry
, udev_list_get_entry(match_list
))
446 trie_insert(trie
, trie
->root
, udev_list_entry_get_name(entry
), line
, value
);
451 static int import_file(struct udev
*udev
, struct trie
*trie
, const char *filename
) {
459 struct udev_list match_list
;
461 udev_list_init(udev
, &match_list
, false);
463 f
= fopen(filename
, "re");
467 while (fgets(line
, sizeof(line
), f
)) {
475 /* strip trailing comment */
476 pos
= strchr(line
, '#');
480 /* strip trailing whitespace */
482 while (len
> 0 && isspace(line
[len
-1]))
491 if (line
[0] == ' ') {
492 log_error("Error, MATCH expected but got '%s' in '%s':", line
, filename
);
496 /* start of record, first match */
498 udev_list_entry_add(&match_list
, line
, NULL
);
503 log_error("Error, DATA expected but got empty line in '%s':", filename
);
505 udev_list_cleanup(&match_list
);
510 if (line
[0] != ' ') {
511 udev_list_entry_add(&match_list
, line
, NULL
);
517 insert_data(trie
, &match_list
, line
, filename
);
524 udev_list_cleanup(&match_list
);
528 if (line
[0] != ' ') {
529 log_error("Error, DATA expected but got '%s' in '%s':", line
, filename
);
531 udev_list_cleanup(&match_list
);
535 insert_data(trie
, &match_list
, line
, filename
);
541 udev_list_cleanup(&match_list
);
545 static void help(void) {
546 printf("Usage: udevadm hwdb OPTIONS\n"
547 " -u,--update update the hardware database\n"
548 " --usr generate in " UDEVLIBEXECDIR
" instead of /etc/udev\n"
549 " -t,--test=MODALIAS query database and print result\n"
550 " -r,--root=PATH alternative root path in the filesystem\n"
554 static int adm_hwdb(struct udev
*udev
, int argc
, char *argv
[]) {
559 static const struct option options
[] = {
560 { "update", no_argument
, NULL
, 'u' },
561 { "usr", no_argument
, NULL
, ARG_USR
},
562 { "test", required_argument
, NULL
, 't' },
563 { "root", required_argument
, NULL
, 'r' },
564 { "help", no_argument
, NULL
, 'h' },
567 const char *test
= NULL
;
568 const char *root
= "";
569 const char *hwdb_bin_dir
= "/etc/udev";
571 struct trie
*trie
= NULL
;
573 int rc
= EXIT_SUCCESS
;
575 while ((c
= getopt_long(argc
, argv
, "ut:r:h", options
, NULL
)) >= 0)
581 hwdb_bin_dir
= UDEVLIBEXECDIR
;
595 assert_not_reached("Unknown option");
598 if (!update
&& !test
) {
599 log_error("Either --update or --test must be used");
605 _cleanup_free_
char *hwdb_bin
= NULL
;
607 trie
= new0(struct trie
, 1);
614 trie
->strings
= strbuf_new();
615 if (!trie
->strings
) {
621 trie
->root
= new0(struct trie_node
, 1);
628 err
= conf_files_list_strv(&files
, ".hwdb", root
, conf_file_dirs
);
630 log_error_errno(err
, "failed to enumerate hwdb files: %m");
634 STRV_FOREACH(f
, files
) {
635 log_debug("reading file '%s'", *f
);
636 import_file(udev
, trie
, *f
);
640 strbuf_complete(trie
->strings
);
642 log_debug("=== trie in-memory ===");
643 log_debug("nodes: %8zu bytes (%8zu)",
644 trie
->nodes_count
* sizeof(struct trie_node
), trie
->nodes_count
);
645 log_debug("children arrays: %8zu bytes (%8zu)",
646 trie
->children_count
* sizeof(struct trie_child_entry
), trie
->children_count
);
647 log_debug("values arrays: %8zu bytes (%8zu)",
648 trie
->values_count
* sizeof(struct trie_value_entry
), trie
->values_count
);
649 log_debug("strings: %8zu bytes",
651 log_debug("strings incoming: %8zu bytes (%8zu)",
652 trie
->strings
->in_len
, trie
->strings
->in_count
);
653 log_debug("strings dedup'ed: %8zu bytes (%8zu)",
654 trie
->strings
->dedup_len
, trie
->strings
->dedup_count
);
656 hwdb_bin
= strjoin(root
, "/", hwdb_bin_dir
, "/hwdb.bin", NULL
);
661 mkdir_parents(hwdb_bin
, 0755);
662 err
= trie_store(trie
, hwdb_bin
);
664 log_error_errno(err
, "Failure writing database %s: %m", hwdb_bin
);
670 _cleanup_(sd_hwdb_unrefp
) sd_hwdb
*hwdb
= NULL
;
673 r
= sd_hwdb_new(&hwdb
);
675 const char *key
, *value
;
677 SD_HWDB_FOREACH_PROPERTY(hwdb
, test
, key
, value
)
678 printf("%s=%s\n", key
, value
);
684 trie_node_cleanup(trie
->root
);
685 strbuf_cleanup(trie
->strings
);
691 const struct udevadm_cmd udevadm_hwdb
= {