1 /* SPDX-License-Identifier: LGPL-2.1+ */
3 Copyright © 2012 Kay Sievers <kay@vrfy.org>
4 Copyright © 2008 Alan Jenkins <alan.christopher.jenkins@googlemail.com>
5 Copyright © 2014 Tom Gundersen <teg@jklm.no>
18 #include "alloc-util.h"
21 #include "hwdb-internal.h"
22 #include "hwdb-util.h"
24 #include "string-util.h"
33 struct trie_header_f
*head
;
37 OrderedHashmap
*properties
;
38 Iterator properties_iterator
;
39 bool properties_modified
;
48 static void linebuf_init(struct linebuf
*buf
) {
53 static const char *linebuf_get(struct linebuf
*buf
) {
54 if (buf
->len
+ 1 >= sizeof(buf
->bytes
))
56 buf
->bytes
[buf
->len
] = '\0';
60 static bool linebuf_add(struct linebuf
*buf
, const char *s
, size_t len
) {
61 if (buf
->len
+ len
>= sizeof(buf
->bytes
))
63 memcpy(buf
->bytes
+ buf
->len
, s
, len
);
68 static bool linebuf_add_char(struct linebuf
*buf
, char c
) {
69 if (buf
->len
+ 1 >= sizeof(buf
->bytes
))
71 buf
->bytes
[buf
->len
++] = c
;
75 static void linebuf_rem(struct linebuf
*buf
, size_t count
) {
76 assert(buf
->len
>= count
);
80 static void linebuf_rem_char(struct linebuf
*buf
) {
84 static const struct trie_child_entry_f
*trie_node_child(sd_hwdb
*hwdb
, const struct trie_node_f
*node
, size_t idx
) {
85 const char *base
= (const char *)node
;
87 base
+= le64toh(hwdb
->head
->node_size
);
88 base
+= idx
* le64toh(hwdb
->head
->child_entry_size
);
89 return (const struct trie_child_entry_f
*)base
;
92 static const struct trie_value_entry_f
*trie_node_value(sd_hwdb
*hwdb
, const struct trie_node_f
*node
, size_t idx
) {
93 const char *base
= (const char *)node
;
95 base
+= le64toh(hwdb
->head
->node_size
);
96 base
+= node
->children_count
* le64toh(hwdb
->head
->child_entry_size
);
97 base
+= idx
* le64toh(hwdb
->head
->value_entry_size
);
98 return (const struct trie_value_entry_f
*)base
;
101 static const struct trie_node_f
*trie_node_from_off(sd_hwdb
*hwdb
, le64_t off
) {
102 return (const struct trie_node_f
*)(hwdb
->map
+ le64toh(off
));
105 static const char *trie_string(sd_hwdb
*hwdb
, le64_t off
) {
106 return hwdb
->map
+ le64toh(off
);
109 static int trie_children_cmp_f(const void *v1
, const void *v2
) {
110 const struct trie_child_entry_f
*n1
= v1
;
111 const struct trie_child_entry_f
*n2
= v2
;
113 return n1
->c
- n2
->c
;
116 static const struct trie_node_f
*node_lookup_f(sd_hwdb
*hwdb
, const struct trie_node_f
*node
, uint8_t c
) {
117 struct trie_child_entry_f
*child
;
118 struct trie_child_entry_f search
;
121 child
= bsearch(&search
, (const char *)node
+ le64toh(hwdb
->head
->node_size
), node
->children_count
,
122 le64toh(hwdb
->head
->child_entry_size
), trie_children_cmp_f
);
124 return trie_node_from_off(hwdb
, child
->child_off
);
128 static int hwdb_add_property(sd_hwdb
*hwdb
, const struct trie_value_entry_f
*entry
) {
134 key
= trie_string(hwdb
, entry
->key_off
);
137 * Silently ignore all properties which do not start with a
138 * space; future extensions might use additional prefixes.
145 if (le64toh(hwdb
->head
->value_entry_size
) >= sizeof(struct trie_value_entry2_f
)) {
146 const struct trie_value_entry2_f
*old
, *entry2
;
148 entry2
= (const struct trie_value_entry2_f
*)entry
;
149 old
= ordered_hashmap_get(hwdb
->properties
, key
);
151 /* On duplicates, we order by filename priority and line-number.
154 * v2 of the format had 64 bits for the line number.
155 * v3 reuses top 32 bits of line_number to store the priority.
156 * We check the top bits — if they are zero we have v2 format.
157 * This means that v2 clients will print wrong line numbers with
160 * For v3 data: we compare the priority (of the source file)
161 * and the line number.
163 * For v2 data: we rely on the fact that the filenames in the hwdb
164 * are added in the order of priority (higher later), because they
165 * are *processed* in the order of priority. So we compare the
166 * indices to determine which file had higher priority. Comparing
167 * the strings alphabetically would be useless, because those are
168 * full paths, and e.g. /usr/lib would sort after /etc, even
169 * though it has lower priority. This is not reliable because of
170 * suffix compression, but should work for the most common case of
171 * /usr/lib/udev/hwbd.d and /etc/udev/hwdb.d, and is better than
172 * not doing the comparison at all.
176 if (entry2
->file_priority
== 0)
177 lower
= entry2
->filename_off
< old
->filename_off
||
178 (entry2
->filename_off
== old
->filename_off
&& entry2
->line_number
< old
->line_number
);
180 lower
= entry2
->file_priority
< old
->file_priority
||
181 (entry2
->file_priority
== old
->file_priority
&& entry2
->line_number
< old
->line_number
);
187 r
= ordered_hashmap_ensure_allocated(&hwdb
->properties
, &string_hash_ops
);
191 r
= ordered_hashmap_replace(hwdb
->properties
, key
, (void *)entry
);
195 hwdb
->properties_modified
= true;
200 static int trie_fnmatch_f(sd_hwdb
*hwdb
, const struct trie_node_f
*node
, size_t p
,
201 struct linebuf
*buf
, const char *search
) {
207 prefix
= trie_string(hwdb
, node
->prefix_off
);
208 len
= strlen(prefix
+ p
);
209 linebuf_add(buf
, prefix
+ p
, len
);
211 for (i
= 0; i
< node
->children_count
; i
++) {
212 const struct trie_child_entry_f
*child
= trie_node_child(hwdb
, node
, i
);
214 linebuf_add_char(buf
, child
->c
);
215 err
= trie_fnmatch_f(hwdb
, trie_node_from_off(hwdb
, child
->child_off
), 0, buf
, search
);
218 linebuf_rem_char(buf
);
221 if (le64toh(node
->values_count
) && fnmatch(linebuf_get(buf
), search
, 0) == 0)
222 for (i
= 0; i
< le64toh(node
->values_count
); i
++) {
223 err
= hwdb_add_property(hwdb
, trie_node_value(hwdb
, node
, i
));
228 linebuf_rem(buf
, len
);
232 static int trie_search_f(sd_hwdb
*hwdb
, const char *search
) {
234 const struct trie_node_f
*node
;
240 node
= trie_node_from_off(hwdb
, hwdb
->head
->nodes_root_off
);
242 const struct trie_node_f
*child
;
245 if (node
->prefix_off
) {
248 for (; (c
= trie_string(hwdb
, node
->prefix_off
)[p
]); p
++) {
249 if (IN_SET(c
, '*', '?', '['))
250 return trie_fnmatch_f(hwdb
, node
, p
, &buf
, search
+ i
+ p
);
251 if (c
!= search
[i
+ p
])
257 child
= node_lookup_f(hwdb
, node
, '*');
259 linebuf_add_char(&buf
, '*');
260 err
= trie_fnmatch_f(hwdb
, child
, 0, &buf
, search
+ i
);
263 linebuf_rem_char(&buf
);
266 child
= node_lookup_f(hwdb
, node
, '?');
268 linebuf_add_char(&buf
, '?');
269 err
= trie_fnmatch_f(hwdb
, child
, 0, &buf
, search
+ i
);
272 linebuf_rem_char(&buf
);
275 child
= node_lookup_f(hwdb
, node
, '[');
277 linebuf_add_char(&buf
, '[');
278 err
= trie_fnmatch_f(hwdb
, child
, 0, &buf
, search
+ i
);
281 linebuf_rem_char(&buf
);
284 if (search
[i
] == '\0') {
287 for (n
= 0; n
< le64toh(node
->values_count
); n
++) {
288 err
= hwdb_add_property(hwdb
, trie_node_value(hwdb
, node
, n
));
295 child
= node_lookup_f(hwdb
, node
, search
[i
]);
302 static const char hwdb_bin_paths
[] =
303 "/etc/systemd/hwdb/hwdb.bin\0"
304 "/etc/udev/hwdb.bin\0"
305 "/usr/lib/systemd/hwdb/hwdb.bin\0"
307 "/lib/systemd/hwdb/hwdb.bin\0"
309 UDEVLIBEXECDIR
"/hwdb.bin\0";
311 _public_
int sd_hwdb_new(sd_hwdb
**ret
) {
312 _cleanup_(sd_hwdb_unrefp
) sd_hwdb
*hwdb
= NULL
;
313 const char *hwdb_bin_path
;
314 const char sig
[] = HWDB_SIG
;
316 assert_return(ret
, -EINVAL
);
318 hwdb
= new0(sd_hwdb
, 1);
322 hwdb
->n_ref
= REFCNT_INIT
;
324 /* find hwdb.bin in hwdb_bin_paths */
325 NULSTR_FOREACH(hwdb_bin_path
, hwdb_bin_paths
) {
326 hwdb
->f
= fopen(hwdb_bin_path
, "re");
329 else if (errno
== ENOENT
)
332 return log_debug_errno(errno
, "error reading %s: %m", hwdb_bin_path
);
336 log_debug("hwdb.bin does not exist, please run systemd-hwdb update");
340 if (fstat(fileno(hwdb
->f
), &hwdb
->st
) < 0 ||
341 (size_t)hwdb
->st
.st_size
< offsetof(struct trie_header_f
, strings_len
) + 8)
342 return log_debug_errno(errno
, "error reading %s: %m", hwdb_bin_path
);
344 hwdb
->map
= mmap(0, hwdb
->st
.st_size
, PROT_READ
, MAP_SHARED
, fileno(hwdb
->f
), 0);
345 if (hwdb
->map
== MAP_FAILED
)
346 return log_debug_errno(errno
, "error mapping %s: %m", hwdb_bin_path
);
348 if (memcmp(hwdb
->map
, sig
, sizeof(hwdb
->head
->signature
)) != 0 ||
349 (size_t)hwdb
->st
.st_size
!= le64toh(hwdb
->head
->file_size
)) {
350 log_debug("error recognizing the format of %s", hwdb_bin_path
);
354 log_debug("=== trie on-disk ===");
355 log_debug("tool version: %"PRIu64
, le64toh(hwdb
->head
->tool_version
));
356 log_debug("file size: %8"PRIi64
" bytes", hwdb
->st
.st_size
);
357 log_debug("header size %8"PRIu64
" bytes", le64toh(hwdb
->head
->header_size
));
358 log_debug("strings %8"PRIu64
" bytes", le64toh(hwdb
->head
->strings_len
));
359 log_debug("nodes %8"PRIu64
" bytes", le64toh(hwdb
->head
->nodes_len
));
361 *ret
= TAKE_PTR(hwdb
);
366 _public_ sd_hwdb
*sd_hwdb_ref(sd_hwdb
*hwdb
) {
367 assert_return(hwdb
, NULL
);
369 assert_se(REFCNT_INC(hwdb
->n_ref
) >= 2);
374 _public_ sd_hwdb
*sd_hwdb_unref(sd_hwdb
*hwdb
) {
375 if (hwdb
&& REFCNT_DEC(hwdb
->n_ref
) == 0) {
377 munmap((void *)hwdb
->map
, hwdb
->st
.st_size
);
378 safe_fclose(hwdb
->f
);
379 ordered_hashmap_free(hwdb
->properties
);
386 bool hwdb_validate(sd_hwdb
*hwdb
) {
396 /* if hwdb.bin doesn't exist anywhere, we need to update */
397 NULSTR_FOREACH(p
, hwdb_bin_paths
) {
398 if (stat(p
, &st
) >= 0) {
406 if (timespec_load(&hwdb
->st
.st_mtim
) != timespec_load(&st
.st_mtim
))
411 static int properties_prepare(sd_hwdb
*hwdb
, const char *modalias
) {
415 ordered_hashmap_clear(hwdb
->properties
);
416 hwdb
->properties_modified
= true;
418 return trie_search_f(hwdb
, modalias
);
421 _public_
int sd_hwdb_get(sd_hwdb
*hwdb
, const char *modalias
, const char *key
, const char **_value
) {
422 const struct trie_value_entry_f
*entry
;
425 assert_return(hwdb
, -EINVAL
);
426 assert_return(hwdb
->f
, -EINVAL
);
427 assert_return(modalias
, -EINVAL
);
428 assert_return(_value
, -EINVAL
);
430 r
= properties_prepare(hwdb
, modalias
);
434 entry
= ordered_hashmap_get(hwdb
->properties
, key
);
438 *_value
= trie_string(hwdb
, entry
->value_off
);
443 _public_
int sd_hwdb_seek(sd_hwdb
*hwdb
, const char *modalias
) {
446 assert_return(hwdb
, -EINVAL
);
447 assert_return(hwdb
->f
, -EINVAL
);
448 assert_return(modalias
, -EINVAL
);
450 r
= properties_prepare(hwdb
, modalias
);
454 hwdb
->properties_modified
= false;
455 hwdb
->properties_iterator
= ITERATOR_FIRST
;
460 _public_
int sd_hwdb_enumerate(sd_hwdb
*hwdb
, const char **key
, const char **value
) {
461 const struct trie_value_entry_f
*entry
;
464 assert_return(hwdb
, -EINVAL
);
465 assert_return(key
, -EINVAL
);
466 assert_return(value
, -EINVAL
);
468 if (hwdb
->properties_modified
)
471 ordered_hashmap_iterate(hwdb
->properties
, &hwdb
->properties_iterator
, (void **)&entry
, &k
);
476 *value
= trie_string(hwdb
, entry
->value_off
);