1 /* SPDX-License-Identifier: LGPL-2.1+ */
3 Copyright © 2008 Alan Jenkins <alan.christopher.jenkins@googlemail.com>
16 #include "alloc-util.h"
19 #include "hwdb-internal.h"
20 #include "hwdb-util.h"
22 #include "string-util.h"
30 struct trie_header_f
*head
;
34 OrderedHashmap
*properties
;
35 Iterator properties_iterator
;
36 bool properties_modified
;
45 static void linebuf_init(struct linebuf
*buf
) {
50 static const char *linebuf_get(struct linebuf
*buf
) {
51 if (buf
->len
+ 1 >= sizeof(buf
->bytes
))
53 buf
->bytes
[buf
->len
] = '\0';
57 static bool linebuf_add(struct linebuf
*buf
, const char *s
, size_t len
) {
58 if (buf
->len
+ len
>= sizeof(buf
->bytes
))
60 memcpy(buf
->bytes
+ buf
->len
, s
, len
);
65 static bool linebuf_add_char(struct linebuf
*buf
, char c
) {
66 if (buf
->len
+ 1 >= sizeof(buf
->bytes
))
68 buf
->bytes
[buf
->len
++] = c
;
72 static void linebuf_rem(struct linebuf
*buf
, size_t count
) {
73 assert(buf
->len
>= count
);
77 static void linebuf_rem_char(struct linebuf
*buf
) {
81 static const struct trie_child_entry_f
*trie_node_child(sd_hwdb
*hwdb
, const struct trie_node_f
*node
, size_t idx
) {
82 const char *base
= (const char *)node
;
84 base
+= le64toh(hwdb
->head
->node_size
);
85 base
+= idx
* le64toh(hwdb
->head
->child_entry_size
);
86 return (const struct trie_child_entry_f
*)base
;
89 static const struct trie_value_entry_f
*trie_node_value(sd_hwdb
*hwdb
, const struct trie_node_f
*node
, size_t idx
) {
90 const char *base
= (const char *)node
;
92 base
+= le64toh(hwdb
->head
->node_size
);
93 base
+= node
->children_count
* le64toh(hwdb
->head
->child_entry_size
);
94 base
+= idx
* le64toh(hwdb
->head
->value_entry_size
);
95 return (const struct trie_value_entry_f
*)base
;
98 static const struct trie_node_f
*trie_node_from_off(sd_hwdb
*hwdb
, le64_t off
) {
99 return (const struct trie_node_f
*)(hwdb
->map
+ le64toh(off
));
102 static const char *trie_string(sd_hwdb
*hwdb
, le64_t off
) {
103 return hwdb
->map
+ le64toh(off
);
106 static int trie_children_cmp_f(const void *v1
, const void *v2
) {
107 const struct trie_child_entry_f
*n1
= v1
;
108 const struct trie_child_entry_f
*n2
= v2
;
110 return n1
->c
- n2
->c
;
113 static const struct trie_node_f
*node_lookup_f(sd_hwdb
*hwdb
, const struct trie_node_f
*node
, uint8_t c
) {
114 struct trie_child_entry_f
*child
;
115 struct trie_child_entry_f search
;
118 child
= bsearch(&search
, (const char *)node
+ le64toh(hwdb
->head
->node_size
), node
->children_count
,
119 le64toh(hwdb
->head
->child_entry_size
), trie_children_cmp_f
);
121 return trie_node_from_off(hwdb
, child
->child_off
);
125 static int hwdb_add_property(sd_hwdb
*hwdb
, const struct trie_value_entry_f
*entry
) {
131 key
= trie_string(hwdb
, entry
->key_off
);
134 * Silently ignore all properties which do not start with a
135 * space; future extensions might use additional prefixes.
142 if (le64toh(hwdb
->head
->value_entry_size
) >= sizeof(struct trie_value_entry2_f
)) {
143 const struct trie_value_entry2_f
*old
, *entry2
;
145 entry2
= (const struct trie_value_entry2_f
*)entry
;
146 old
= ordered_hashmap_get(hwdb
->properties
, key
);
148 /* On duplicates, we order by filename priority and line-number.
150 * v2 of the format had 64 bits for the line number.
151 * v3 reuses top 32 bits of line_number to store the priority.
152 * We check the top bits — if they are zero we have v2 format.
153 * This means that v2 clients will print wrong line numbers with
156 * For v3 data: we compare the priority (of the source file)
157 * and the line number.
159 * For v2 data: we rely on the fact that the filenames in the hwdb
160 * are added in the order of priority (higher later), because they
161 * are *processed* in the order of priority. So we compare the
162 * indices to determine which file had higher priority. Comparing
163 * the strings alphabetically would be useless, because those are
164 * full paths, and e.g. /usr/lib would sort after /etc, even
165 * though it has lower priority. This is not reliable because of
166 * suffix compression, but should work for the most common case of
167 * /usr/lib/udev/hwbd.d and /etc/udev/hwdb.d, and is better than
168 * not doing the comparison at all.
172 if (entry2
->file_priority
== 0)
173 lower
= entry2
->filename_off
< old
->filename_off
||
174 (entry2
->filename_off
== old
->filename_off
&& entry2
->line_number
< old
->line_number
);
176 lower
= entry2
->file_priority
< old
->file_priority
||
177 (entry2
->file_priority
== old
->file_priority
&& entry2
->line_number
< old
->line_number
);
183 r
= ordered_hashmap_ensure_allocated(&hwdb
->properties
, &string_hash_ops
);
187 r
= ordered_hashmap_replace(hwdb
->properties
, key
, (void *)entry
);
191 hwdb
->properties_modified
= true;
196 static int trie_fnmatch_f(sd_hwdb
*hwdb
, const struct trie_node_f
*node
, size_t p
,
197 struct linebuf
*buf
, const char *search
) {
203 prefix
= trie_string(hwdb
, node
->prefix_off
);
204 len
= strlen(prefix
+ p
);
205 linebuf_add(buf
, prefix
+ p
, len
);
207 for (i
= 0; i
< node
->children_count
; i
++) {
208 const struct trie_child_entry_f
*child
= trie_node_child(hwdb
, node
, i
);
210 linebuf_add_char(buf
, child
->c
);
211 err
= trie_fnmatch_f(hwdb
, trie_node_from_off(hwdb
, child
->child_off
), 0, buf
, search
);
214 linebuf_rem_char(buf
);
217 if (le64toh(node
->values_count
) && fnmatch(linebuf_get(buf
), search
, 0) == 0)
218 for (i
= 0; i
< le64toh(node
->values_count
); i
++) {
219 err
= hwdb_add_property(hwdb
, trie_node_value(hwdb
, node
, i
));
224 linebuf_rem(buf
, len
);
228 static int trie_search_f(sd_hwdb
*hwdb
, const char *search
) {
230 const struct trie_node_f
*node
;
236 node
= trie_node_from_off(hwdb
, hwdb
->head
->nodes_root_off
);
238 const struct trie_node_f
*child
;
241 if (node
->prefix_off
) {
244 for (; (c
= trie_string(hwdb
, node
->prefix_off
)[p
]); p
++) {
245 if (IN_SET(c
, '*', '?', '['))
246 return trie_fnmatch_f(hwdb
, node
, p
, &buf
, search
+ i
+ p
);
247 if (c
!= search
[i
+ p
])
253 child
= node_lookup_f(hwdb
, node
, '*');
255 linebuf_add_char(&buf
, '*');
256 err
= trie_fnmatch_f(hwdb
, child
, 0, &buf
, search
+ i
);
259 linebuf_rem_char(&buf
);
262 child
= node_lookup_f(hwdb
, node
, '?');
264 linebuf_add_char(&buf
, '?');
265 err
= trie_fnmatch_f(hwdb
, child
, 0, &buf
, search
+ i
);
268 linebuf_rem_char(&buf
);
271 child
= node_lookup_f(hwdb
, node
, '[');
273 linebuf_add_char(&buf
, '[');
274 err
= trie_fnmatch_f(hwdb
, child
, 0, &buf
, search
+ i
);
277 linebuf_rem_char(&buf
);
280 if (search
[i
] == '\0') {
283 for (n
= 0; n
< le64toh(node
->values_count
); n
++) {
284 err
= hwdb_add_property(hwdb
, trie_node_value(hwdb
, node
, n
));
291 child
= node_lookup_f(hwdb
, node
, search
[i
]);
298 static const char hwdb_bin_paths
[] =
299 "/etc/systemd/hwdb/hwdb.bin\0"
300 "/etc/udev/hwdb.bin\0"
301 "/usr/lib/systemd/hwdb/hwdb.bin\0"
303 "/lib/systemd/hwdb/hwdb.bin\0"
305 UDEVLIBEXECDIR
"/hwdb.bin\0";
307 _public_
int sd_hwdb_new(sd_hwdb
**ret
) {
308 _cleanup_(sd_hwdb_unrefp
) sd_hwdb
*hwdb
= NULL
;
309 const char *hwdb_bin_path
;
310 const char sig
[] = HWDB_SIG
;
312 assert_return(ret
, -EINVAL
);
314 hwdb
= new0(sd_hwdb
, 1);
318 hwdb
->n_ref
= REFCNT_INIT
;
320 /* find hwdb.bin in hwdb_bin_paths */
321 NULSTR_FOREACH(hwdb_bin_path
, hwdb_bin_paths
) {
322 hwdb
->f
= fopen(hwdb_bin_path
, "re");
325 else if (errno
== ENOENT
)
328 return log_debug_errno(errno
, "error reading %s: %m", hwdb_bin_path
);
332 log_debug("hwdb.bin does not exist, please run systemd-hwdb update");
336 if (fstat(fileno(hwdb
->f
), &hwdb
->st
) < 0 ||
337 (size_t)hwdb
->st
.st_size
< offsetof(struct trie_header_f
, strings_len
) + 8)
338 return log_debug_errno(errno
, "error reading %s: %m", hwdb_bin_path
);
340 hwdb
->map
= mmap(0, hwdb
->st
.st_size
, PROT_READ
, MAP_SHARED
, fileno(hwdb
->f
), 0);
341 if (hwdb
->map
== MAP_FAILED
)
342 return log_debug_errno(errno
, "error mapping %s: %m", hwdb_bin_path
);
344 if (memcmp(hwdb
->map
, sig
, sizeof(hwdb
->head
->signature
)) != 0 ||
345 (size_t)hwdb
->st
.st_size
!= le64toh(hwdb
->head
->file_size
)) {
346 log_debug("error recognizing the format of %s", hwdb_bin_path
);
350 log_debug("=== trie on-disk ===");
351 log_debug("tool version: %"PRIu64
, le64toh(hwdb
->head
->tool_version
));
352 log_debug("file size: %8"PRIi64
" bytes", hwdb
->st
.st_size
);
353 log_debug("header size %8"PRIu64
" bytes", le64toh(hwdb
->head
->header_size
));
354 log_debug("strings %8"PRIu64
" bytes", le64toh(hwdb
->head
->strings_len
));
355 log_debug("nodes %8"PRIu64
" bytes", le64toh(hwdb
->head
->nodes_len
));
357 *ret
= TAKE_PTR(hwdb
);
362 _public_ sd_hwdb
*sd_hwdb_ref(sd_hwdb
*hwdb
) {
363 assert_return(hwdb
, NULL
);
365 assert_se(REFCNT_INC(hwdb
->n_ref
) >= 2);
370 _public_ sd_hwdb
*sd_hwdb_unref(sd_hwdb
*hwdb
) {
371 if (hwdb
&& REFCNT_DEC(hwdb
->n_ref
) == 0) {
373 munmap((void *)hwdb
->map
, hwdb
->st
.st_size
);
374 safe_fclose(hwdb
->f
);
375 ordered_hashmap_free(hwdb
->properties
);
382 bool hwdb_validate(sd_hwdb
*hwdb
) {
392 /* if hwdb.bin doesn't exist anywhere, we need to update */
393 NULSTR_FOREACH(p
, hwdb_bin_paths
) {
394 if (stat(p
, &st
) >= 0) {
402 if (timespec_load(&hwdb
->st
.st_mtim
) != timespec_load(&st
.st_mtim
))
407 static int properties_prepare(sd_hwdb
*hwdb
, const char *modalias
) {
411 ordered_hashmap_clear(hwdb
->properties
);
412 hwdb
->properties_modified
= true;
414 return trie_search_f(hwdb
, modalias
);
417 _public_
int sd_hwdb_get(sd_hwdb
*hwdb
, const char *modalias
, const char *key
, const char **_value
) {
418 const struct trie_value_entry_f
*entry
;
421 assert_return(hwdb
, -EINVAL
);
422 assert_return(hwdb
->f
, -EINVAL
);
423 assert_return(modalias
, -EINVAL
);
424 assert_return(_value
, -EINVAL
);
426 r
= properties_prepare(hwdb
, modalias
);
430 entry
= ordered_hashmap_get(hwdb
->properties
, key
);
434 *_value
= trie_string(hwdb
, entry
->value_off
);
439 _public_
int sd_hwdb_seek(sd_hwdb
*hwdb
, const char *modalias
) {
442 assert_return(hwdb
, -EINVAL
);
443 assert_return(hwdb
->f
, -EINVAL
);
444 assert_return(modalias
, -EINVAL
);
446 r
= properties_prepare(hwdb
, modalias
);
450 hwdb
->properties_modified
= false;
451 hwdb
->properties_iterator
= ITERATOR_FIRST
;
456 _public_
int sd_hwdb_enumerate(sd_hwdb
*hwdb
, const char **key
, const char **value
) {
457 const struct trie_value_entry_f
*entry
;
460 assert_return(hwdb
, -EINVAL
);
461 assert_return(key
, -EINVAL
);
462 assert_return(value
, -EINVAL
);
464 if (hwdb
->properties_modified
)
467 ordered_hashmap_iterate(hwdb
->properties
, &hwdb
->properties_iterator
, (void **)&entry
, &k
);
472 *value
= trie_string(hwdb
, entry
->value_off
);