1 /* SPDX-License-Identifier: LGPL-2.1+ */
3 This file is part of systemd.
5 Copyright 2012 Kay Sievers <kay@vrfy.org>
6 Copyright 2008 Alan Jenkins <alan.christopher.jenkins@googlemail.com>
7 Copyright 2014 Tom Gundersen <teg@jklm.no>
20 #include "alloc-util.h"
23 #include "hwdb-internal.h"
24 #include "hwdb-util.h"
26 #include "string-util.h"
35 struct trie_header_f
*head
;
39 OrderedHashmap
*properties
;
40 Iterator properties_iterator
;
41 bool properties_modified
;
50 static void linebuf_init(struct linebuf
*buf
) {
55 static const char *linebuf_get(struct linebuf
*buf
) {
56 if (buf
->len
+ 1 >= sizeof(buf
->bytes
))
58 buf
->bytes
[buf
->len
] = '\0';
62 static bool linebuf_add(struct linebuf
*buf
, const char *s
, size_t len
) {
63 if (buf
->len
+ len
>= sizeof(buf
->bytes
))
65 memcpy(buf
->bytes
+ buf
->len
, s
, len
);
70 static bool linebuf_add_char(struct linebuf
*buf
, char c
) {
71 if (buf
->len
+ 1 >= sizeof(buf
->bytes
))
73 buf
->bytes
[buf
->len
++] = c
;
77 static void linebuf_rem(struct linebuf
*buf
, size_t count
) {
78 assert(buf
->len
>= count
);
82 static void linebuf_rem_char(struct linebuf
*buf
) {
86 static const struct trie_child_entry_f
*trie_node_child(sd_hwdb
*hwdb
, const struct trie_node_f
*node
, size_t idx
) {
87 const char *base
= (const char *)node
;
89 base
+= le64toh(hwdb
->head
->node_size
);
90 base
+= idx
* le64toh(hwdb
->head
->child_entry_size
);
91 return (const struct trie_child_entry_f
*)base
;
94 static const struct trie_value_entry_f
*trie_node_value(sd_hwdb
*hwdb
, const struct trie_node_f
*node
, size_t idx
) {
95 const char *base
= (const char *)node
;
97 base
+= le64toh(hwdb
->head
->node_size
);
98 base
+= node
->children_count
* le64toh(hwdb
->head
->child_entry_size
);
99 base
+= idx
* le64toh(hwdb
->head
->value_entry_size
);
100 return (const struct trie_value_entry_f
*)base
;
103 static const struct trie_node_f
*trie_node_from_off(sd_hwdb
*hwdb
, le64_t off
) {
104 return (const struct trie_node_f
*)(hwdb
->map
+ le64toh(off
));
107 static const char *trie_string(sd_hwdb
*hwdb
, le64_t off
) {
108 return hwdb
->map
+ le64toh(off
);
111 static int trie_children_cmp_f(const void *v1
, const void *v2
) {
112 const struct trie_child_entry_f
*n1
= v1
;
113 const struct trie_child_entry_f
*n2
= v2
;
115 return n1
->c
- n2
->c
;
118 static const struct trie_node_f
*node_lookup_f(sd_hwdb
*hwdb
, const struct trie_node_f
*node
, uint8_t c
) {
119 struct trie_child_entry_f
*child
;
120 struct trie_child_entry_f search
;
123 child
= bsearch(&search
, (const char *)node
+ le64toh(hwdb
->head
->node_size
), node
->children_count
,
124 le64toh(hwdb
->head
->child_entry_size
), trie_children_cmp_f
);
126 return trie_node_from_off(hwdb
, child
->child_off
);
130 static int hwdb_add_property(sd_hwdb
*hwdb
, const struct trie_value_entry_f
*entry
) {
136 key
= trie_string(hwdb
, entry
->key_off
);
139 * Silently ignore all properties which do not start with a
140 * space; future extensions might use additional prefixes.
147 if (le64toh(hwdb
->head
->value_entry_size
) >= sizeof(struct trie_value_entry2_f
)) {
148 const struct trie_value_entry2_f
*old
, *entry2
;
150 entry2
= (const struct trie_value_entry2_f
*)entry
;
151 old
= ordered_hashmap_get(hwdb
->properties
, key
);
153 /* On duplicates, we order by filename priority and line-number.
156 * v2 of the format had 64 bits for the line number.
157 * v3 reuses top 32 bits of line_number to store the priority.
158 * We check the top bits — if they are zero we have v2 format.
159 * This means that v2 clients will print wrong line numbers with
162 * For v3 data: we compare the priority (of the source file)
163 * and the line number.
165 * For v2 data: we rely on the fact that the filenames in the hwdb
166 * are added in the order of priority (higher later), because they
167 * are *processed* in the order of priority. So we compare the
168 * indices to determine which file had higher priority. Comparing
169 * the strings alphabetically would be useless, because those are
170 * full paths, and e.g. /usr/lib would sort after /etc, even
171 * though it has lower priority. This is not reliable because of
172 * suffix compression, but should work for the most common case of
173 * /usr/lib/udev/hwbd.d and /etc/udev/hwdb.d, and is better than
174 * not doing the comparison at all.
178 if (entry2
->file_priority
== 0)
179 lower
= entry2
->filename_off
< old
->filename_off
||
180 (entry2
->filename_off
== old
->filename_off
&& entry2
->line_number
< old
->line_number
);
182 lower
= entry2
->file_priority
< old
->file_priority
||
183 (entry2
->file_priority
== old
->file_priority
&& entry2
->line_number
< old
->line_number
);
189 r
= ordered_hashmap_ensure_allocated(&hwdb
->properties
, &string_hash_ops
);
193 r
= ordered_hashmap_replace(hwdb
->properties
, key
, (void *)entry
);
197 hwdb
->properties_modified
= true;
202 static int trie_fnmatch_f(sd_hwdb
*hwdb
, const struct trie_node_f
*node
, size_t p
,
203 struct linebuf
*buf
, const char *search
) {
209 prefix
= trie_string(hwdb
, node
->prefix_off
);
210 len
= strlen(prefix
+ p
);
211 linebuf_add(buf
, prefix
+ p
, len
);
213 for (i
= 0; i
< node
->children_count
; i
++) {
214 const struct trie_child_entry_f
*child
= trie_node_child(hwdb
, node
, i
);
216 linebuf_add_char(buf
, child
->c
);
217 err
= trie_fnmatch_f(hwdb
, trie_node_from_off(hwdb
, child
->child_off
), 0, buf
, search
);
220 linebuf_rem_char(buf
);
223 if (le64toh(node
->values_count
) && fnmatch(linebuf_get(buf
), search
, 0) == 0)
224 for (i
= 0; i
< le64toh(node
->values_count
); i
++) {
225 err
= hwdb_add_property(hwdb
, trie_node_value(hwdb
, node
, i
));
230 linebuf_rem(buf
, len
);
234 static int trie_search_f(sd_hwdb
*hwdb
, const char *search
) {
236 const struct trie_node_f
*node
;
242 node
= trie_node_from_off(hwdb
, hwdb
->head
->nodes_root_off
);
244 const struct trie_node_f
*child
;
247 if (node
->prefix_off
) {
250 for (; (c
= trie_string(hwdb
, node
->prefix_off
)[p
]); p
++) {
251 if (IN_SET(c
, '*', '?', '['))
252 return trie_fnmatch_f(hwdb
, node
, p
, &buf
, search
+ i
+ p
);
253 if (c
!= search
[i
+ p
])
259 child
= node_lookup_f(hwdb
, node
, '*');
261 linebuf_add_char(&buf
, '*');
262 err
= trie_fnmatch_f(hwdb
, child
, 0, &buf
, search
+ i
);
265 linebuf_rem_char(&buf
);
268 child
= node_lookup_f(hwdb
, node
, '?');
270 linebuf_add_char(&buf
, '?');
271 err
= trie_fnmatch_f(hwdb
, child
, 0, &buf
, search
+ i
);
274 linebuf_rem_char(&buf
);
277 child
= node_lookup_f(hwdb
, node
, '[');
279 linebuf_add_char(&buf
, '[');
280 err
= trie_fnmatch_f(hwdb
, child
, 0, &buf
, search
+ i
);
283 linebuf_rem_char(&buf
);
286 if (search
[i
] == '\0') {
289 for (n
= 0; n
< le64toh(node
->values_count
); n
++) {
290 err
= hwdb_add_property(hwdb
, trie_node_value(hwdb
, node
, n
));
297 child
= node_lookup_f(hwdb
, node
, search
[i
]);
304 static const char hwdb_bin_paths
[] =
305 "/etc/systemd/hwdb/hwdb.bin\0"
306 "/etc/udev/hwdb.bin\0"
307 "/usr/lib/systemd/hwdb/hwdb.bin\0"
309 "/lib/systemd/hwdb/hwdb.bin\0"
311 UDEVLIBEXECDIR
"/hwdb.bin\0";
313 _public_
int sd_hwdb_new(sd_hwdb
**ret
) {
314 _cleanup_(sd_hwdb_unrefp
) sd_hwdb
*hwdb
= NULL
;
315 const char *hwdb_bin_path
;
316 const char sig
[] = HWDB_SIG
;
318 assert_return(ret
, -EINVAL
);
320 hwdb
= new0(sd_hwdb
, 1);
324 hwdb
->n_ref
= REFCNT_INIT
;
326 /* find hwdb.bin in hwdb_bin_paths */
327 NULSTR_FOREACH(hwdb_bin_path
, hwdb_bin_paths
) {
328 hwdb
->f
= fopen(hwdb_bin_path
, "re");
331 else if (errno
== ENOENT
)
334 return log_debug_errno(errno
, "error reading %s: %m", hwdb_bin_path
);
338 log_debug("hwdb.bin does not exist, please run systemd-hwdb update");
342 if (fstat(fileno(hwdb
->f
), &hwdb
->st
) < 0 ||
343 (size_t)hwdb
->st
.st_size
< offsetof(struct trie_header_f
, strings_len
) + 8)
344 return log_debug_errno(errno
, "error reading %s: %m", hwdb_bin_path
);
346 hwdb
->map
= mmap(0, hwdb
->st
.st_size
, PROT_READ
, MAP_SHARED
, fileno(hwdb
->f
), 0);
347 if (hwdb
->map
== MAP_FAILED
)
348 return log_debug_errno(errno
, "error mapping %s: %m", hwdb_bin_path
);
350 if (memcmp(hwdb
->map
, sig
, sizeof(hwdb
->head
->signature
)) != 0 ||
351 (size_t)hwdb
->st
.st_size
!= le64toh(hwdb
->head
->file_size
)) {
352 log_debug("error recognizing the format of %s", hwdb_bin_path
);
356 log_debug("=== trie on-disk ===");
357 log_debug("tool version: %"PRIu64
, le64toh(hwdb
->head
->tool_version
));
358 log_debug("file size: %8"PRIi64
" bytes", hwdb
->st
.st_size
);
359 log_debug("header size %8"PRIu64
" bytes", le64toh(hwdb
->head
->header_size
));
360 log_debug("strings %8"PRIu64
" bytes", le64toh(hwdb
->head
->strings_len
));
361 log_debug("nodes %8"PRIu64
" bytes", le64toh(hwdb
->head
->nodes_len
));
363 *ret
= TAKE_PTR(hwdb
);
368 _public_ sd_hwdb
*sd_hwdb_ref(sd_hwdb
*hwdb
) {
369 assert_return(hwdb
, NULL
);
371 assert_se(REFCNT_INC(hwdb
->n_ref
) >= 2);
376 _public_ sd_hwdb
*sd_hwdb_unref(sd_hwdb
*hwdb
) {
377 if (hwdb
&& REFCNT_DEC(hwdb
->n_ref
) == 0) {
379 munmap((void *)hwdb
->map
, hwdb
->st
.st_size
);
380 safe_fclose(hwdb
->f
);
381 ordered_hashmap_free(hwdb
->properties
);
388 bool hwdb_validate(sd_hwdb
*hwdb
) {
398 /* if hwdb.bin doesn't exist anywhere, we need to update */
399 NULSTR_FOREACH(p
, hwdb_bin_paths
) {
400 if (stat(p
, &st
) >= 0) {
408 if (timespec_load(&hwdb
->st
.st_mtim
) != timespec_load(&st
.st_mtim
))
413 static int properties_prepare(sd_hwdb
*hwdb
, const char *modalias
) {
417 ordered_hashmap_clear(hwdb
->properties
);
418 hwdb
->properties_modified
= true;
420 return trie_search_f(hwdb
, modalias
);
423 _public_
int sd_hwdb_get(sd_hwdb
*hwdb
, const char *modalias
, const char *key
, const char **_value
) {
424 const struct trie_value_entry_f
*entry
;
427 assert_return(hwdb
, -EINVAL
);
428 assert_return(hwdb
->f
, -EINVAL
);
429 assert_return(modalias
, -EINVAL
);
430 assert_return(_value
, -EINVAL
);
432 r
= properties_prepare(hwdb
, modalias
);
436 entry
= ordered_hashmap_get(hwdb
->properties
, key
);
440 *_value
= trie_string(hwdb
, entry
->value_off
);
445 _public_
int sd_hwdb_seek(sd_hwdb
*hwdb
, const char *modalias
) {
448 assert_return(hwdb
, -EINVAL
);
449 assert_return(hwdb
->f
, -EINVAL
);
450 assert_return(modalias
, -EINVAL
);
452 r
= properties_prepare(hwdb
, modalias
);
456 hwdb
->properties_modified
= false;
457 hwdb
->properties_iterator
= ITERATOR_FIRST
;
462 _public_
int sd_hwdb_enumerate(sd_hwdb
*hwdb
, const char **key
, const char **value
) {
463 const struct trie_value_entry_f
*entry
;
466 assert_return(hwdb
, -EINVAL
);
467 assert_return(key
, -EINVAL
);
468 assert_return(value
, -EINVAL
);
470 if (hwdb
->properties_modified
)
473 ordered_hashmap_iterate(hwdb
->properties
, &hwdb
->properties_iterator
, (void **)&entry
, &k
);
478 *value
= trie_string(hwdb
, entry
->value_off
);