1 /* SPDX-License-Identifier: LGPL-2.1+ */
3 Copyright © 2008 Alan Jenkins <alan.christopher.jenkins@googlemail.com>
17 #include "alloc-util.h"
20 #include "hwdb-internal.h"
21 #include "hwdb-util.h"
22 #include "nulstr-util.h"
23 #include "string-util.h"
24 #include "time-util.h"
32 struct trie_header_f
*head
;
36 OrderedHashmap
*properties
;
37 Iterator properties_iterator
;
38 bool properties_modified
;
47 static void linebuf_init(struct linebuf
*buf
) {
52 static const char *linebuf_get(struct linebuf
*buf
) {
53 if (buf
->len
+ 1 >= sizeof(buf
->bytes
))
55 buf
->bytes
[buf
->len
] = '\0';
59 static bool linebuf_add(struct linebuf
*buf
, const char *s
, size_t len
) {
60 if (buf
->len
+ len
>= sizeof(buf
->bytes
))
62 memcpy(buf
->bytes
+ buf
->len
, s
, len
);
67 static bool linebuf_add_char(struct linebuf
*buf
, char c
) {
68 if (buf
->len
+ 1 >= sizeof(buf
->bytes
))
70 buf
->bytes
[buf
->len
++] = c
;
74 static void linebuf_rem(struct linebuf
*buf
, size_t count
) {
75 assert(buf
->len
>= count
);
79 static void linebuf_rem_char(struct linebuf
*buf
) {
83 static const struct trie_child_entry_f
*trie_node_child(sd_hwdb
*hwdb
, const struct trie_node_f
*node
, size_t idx
) {
84 const char *base
= (const char *)node
;
86 base
+= le64toh(hwdb
->head
->node_size
);
87 base
+= idx
* le64toh(hwdb
->head
->child_entry_size
);
88 return (const struct trie_child_entry_f
*)base
;
91 static const struct trie_value_entry_f
*trie_node_value(sd_hwdb
*hwdb
, const struct trie_node_f
*node
, size_t idx
) {
92 const char *base
= (const char *)node
;
94 base
+= le64toh(hwdb
->head
->node_size
);
95 base
+= node
->children_count
* le64toh(hwdb
->head
->child_entry_size
);
96 base
+= idx
* le64toh(hwdb
->head
->value_entry_size
);
97 return (const struct trie_value_entry_f
*)base
;
100 static const struct trie_node_f
*trie_node_from_off(sd_hwdb
*hwdb
, le64_t off
) {
101 return (const struct trie_node_f
*)(hwdb
->map
+ le64toh(off
));
104 static const char *trie_string(sd_hwdb
*hwdb
, le64_t off
) {
105 return hwdb
->map
+ le64toh(off
);
108 static int trie_children_cmp_f(const void *v1
, const void *v2
) {
109 const struct trie_child_entry_f
*n1
= v1
;
110 const struct trie_child_entry_f
*n2
= v2
;
112 return n1
->c
- n2
->c
;
115 static const struct trie_node_f
*node_lookup_f(sd_hwdb
*hwdb
, const struct trie_node_f
*node
, uint8_t c
) {
116 struct trie_child_entry_f
*child
;
117 struct trie_child_entry_f search
;
120 child
= bsearch(&search
, (const char *)node
+ le64toh(hwdb
->head
->node_size
), node
->children_count
,
121 le64toh(hwdb
->head
->child_entry_size
), trie_children_cmp_f
);
123 return trie_node_from_off(hwdb
, child
->child_off
);
127 static int hwdb_add_property(sd_hwdb
*hwdb
, const struct trie_value_entry_f
*entry
) {
133 key
= trie_string(hwdb
, entry
->key_off
);
136 * Silently ignore all properties which do not start with a
137 * space; future extensions might use additional prefixes.
144 if (le64toh(hwdb
->head
->value_entry_size
) >= sizeof(struct trie_value_entry2_f
)) {
145 const struct trie_value_entry2_f
*old
, *entry2
;
147 entry2
= (const struct trie_value_entry2_f
*)entry
;
148 old
= ordered_hashmap_get(hwdb
->properties
, key
);
150 /* On duplicates, we order by filename priority and line-number.
152 * v2 of the format had 64 bits for the line number.
153 * v3 reuses top 32 bits of line_number to store the priority.
154 * We check the top bits — if they are zero we have v2 format.
155 * This means that v2 clients will print wrong line numbers with
158 * For v3 data: we compare the priority (of the source file)
159 * and the line number.
161 * For v2 data: we rely on the fact that the filenames in the hwdb
162 * are added in the order of priority (higher later), because they
163 * are *processed* in the order of priority. So we compare the
164 * indices to determine which file had higher priority. Comparing
165 * the strings alphabetically would be useless, because those are
166 * full paths, and e.g. /usr/lib would sort after /etc, even
167 * though it has lower priority. This is not reliable because of
168 * suffix compression, but should work for the most common case of
169 * /usr/lib/udev/hwbd.d and /etc/udev/hwdb.d, and is better than
170 * not doing the comparison at all.
174 if (entry2
->file_priority
== 0)
175 lower
= entry2
->filename_off
< old
->filename_off
||
176 (entry2
->filename_off
== old
->filename_off
&& entry2
->line_number
< old
->line_number
);
178 lower
= entry2
->file_priority
< old
->file_priority
||
179 (entry2
->file_priority
== old
->file_priority
&& entry2
->line_number
< old
->line_number
);
185 r
= ordered_hashmap_ensure_allocated(&hwdb
->properties
, &string_hash_ops
);
189 r
= ordered_hashmap_replace(hwdb
->properties
, key
, (void *)entry
);
193 hwdb
->properties_modified
= true;
198 static int trie_fnmatch_f(sd_hwdb
*hwdb
, const struct trie_node_f
*node
, size_t p
,
199 struct linebuf
*buf
, const char *search
) {
205 prefix
= trie_string(hwdb
, node
->prefix_off
);
206 len
= strlen(prefix
+ p
);
207 linebuf_add(buf
, prefix
+ p
, len
);
209 for (i
= 0; i
< node
->children_count
; i
++) {
210 const struct trie_child_entry_f
*child
= trie_node_child(hwdb
, node
, i
);
212 linebuf_add_char(buf
, child
->c
);
213 err
= trie_fnmatch_f(hwdb
, trie_node_from_off(hwdb
, child
->child_off
), 0, buf
, search
);
216 linebuf_rem_char(buf
);
219 if (le64toh(node
->values_count
) && fnmatch(linebuf_get(buf
), search
, 0) == 0)
220 for (i
= 0; i
< le64toh(node
->values_count
); i
++) {
221 err
= hwdb_add_property(hwdb
, trie_node_value(hwdb
, node
, i
));
226 linebuf_rem(buf
, len
);
230 static int trie_search_f(sd_hwdb
*hwdb
, const char *search
) {
232 const struct trie_node_f
*node
;
238 node
= trie_node_from_off(hwdb
, hwdb
->head
->nodes_root_off
);
240 const struct trie_node_f
*child
;
243 if (node
->prefix_off
) {
246 for (; (c
= trie_string(hwdb
, node
->prefix_off
)[p
]); p
++) {
247 if (IN_SET(c
, '*', '?', '['))
248 return trie_fnmatch_f(hwdb
, node
, p
, &buf
, search
+ i
+ p
);
249 if (c
!= search
[i
+ p
])
255 child
= node_lookup_f(hwdb
, node
, '*');
257 linebuf_add_char(&buf
, '*');
258 err
= trie_fnmatch_f(hwdb
, child
, 0, &buf
, search
+ i
);
261 linebuf_rem_char(&buf
);
264 child
= node_lookup_f(hwdb
, node
, '?');
266 linebuf_add_char(&buf
, '?');
267 err
= trie_fnmatch_f(hwdb
, child
, 0, &buf
, search
+ i
);
270 linebuf_rem_char(&buf
);
273 child
= node_lookup_f(hwdb
, node
, '[');
275 linebuf_add_char(&buf
, '[');
276 err
= trie_fnmatch_f(hwdb
, child
, 0, &buf
, search
+ i
);
279 linebuf_rem_char(&buf
);
282 if (search
[i
] == '\0') {
285 for (n
= 0; n
< le64toh(node
->values_count
); n
++) {
286 err
= hwdb_add_property(hwdb
, trie_node_value(hwdb
, node
, n
));
293 child
= node_lookup_f(hwdb
, node
, search
[i
]);
300 static const char hwdb_bin_paths
[] =
301 "/etc/systemd/hwdb/hwdb.bin\0"
302 "/etc/udev/hwdb.bin\0"
303 "/usr/lib/systemd/hwdb/hwdb.bin\0"
305 "/lib/systemd/hwdb/hwdb.bin\0"
307 UDEVLIBEXECDIR
"/hwdb.bin\0";
309 _public_
int sd_hwdb_new(sd_hwdb
**ret
) {
310 _cleanup_(sd_hwdb_unrefp
) sd_hwdb
*hwdb
= NULL
;
311 const char *hwdb_bin_path
;
312 const char sig
[] = HWDB_SIG
;
314 assert_return(ret
, -EINVAL
);
316 hwdb
= new0(sd_hwdb
, 1);
322 /* find hwdb.bin in hwdb_bin_paths */
323 NULSTR_FOREACH(hwdb_bin_path
, hwdb_bin_paths
) {
324 log_debug("Trying to open \"%s\"...", hwdb_bin_path
);
325 hwdb
->f
= fopen(hwdb_bin_path
, "re");
329 return log_debug_errno(errno
, "Failed to open %s: %m", hwdb_bin_path
);
333 return log_debug_errno(SYNTHETIC_ERRNO(ENOENT
),
334 "hwdb.bin does not exist, please run 'systemd-hwdb update'");
336 if (fstat(fileno(hwdb
->f
), &hwdb
->st
) < 0)
337 return log_debug_errno(errno
, "Failed to stat %s: %m", hwdb_bin_path
);
338 if (hwdb
->st
.st_size
< (off_t
) offsetof(struct trie_header_f
, strings_len
) + 8)
339 return log_debug_errno(SYNTHETIC_ERRNO(EIO
),
340 "File %s is too short: %m", hwdb_bin_path
);
342 hwdb
->map
= mmap(0, hwdb
->st
.st_size
, PROT_READ
, MAP_SHARED
, fileno(hwdb
->f
), 0);
343 if (hwdb
->map
== MAP_FAILED
)
344 return log_debug_errno(errno
, "Failed to map %s: %m", hwdb_bin_path
);
346 if (memcmp(hwdb
->map
, sig
, sizeof(hwdb
->head
->signature
)) != 0 ||
347 (size_t) hwdb
->st
.st_size
!= le64toh(hwdb
->head
->file_size
)) {
348 log_debug("Failed to recognize the format of %s", hwdb_bin_path
);
352 log_debug("=== trie on-disk ===");
353 log_debug("tool version: %"PRIu64
, le64toh(hwdb
->head
->tool_version
));
354 log_debug("file size: %8"PRIi64
" bytes", hwdb
->st
.st_size
);
355 log_debug("header size %8"PRIu64
" bytes", le64toh(hwdb
->head
->header_size
));
356 log_debug("strings %8"PRIu64
" bytes", le64toh(hwdb
->head
->strings_len
));
357 log_debug("nodes %8"PRIu64
" bytes", le64toh(hwdb
->head
->nodes_len
));
359 *ret
= TAKE_PTR(hwdb
);
364 static sd_hwdb
*hwdb_free(sd_hwdb
*hwdb
) {
368 munmap((void *)hwdb
->map
, hwdb
->st
.st_size
);
369 safe_fclose(hwdb
->f
);
370 ordered_hashmap_free(hwdb
->properties
);
374 DEFINE_PUBLIC_TRIVIAL_REF_UNREF_FUNC(sd_hwdb
, sd_hwdb
, hwdb_free
)
376 bool hwdb_validate(sd_hwdb
*hwdb
) {
386 /* if hwdb.bin doesn't exist anywhere, we need to update */
387 NULSTR_FOREACH(p
, hwdb_bin_paths
)
388 if (stat(p
, &st
) >= 0) {
395 if (timespec_load(&hwdb
->st
.st_mtim
) != timespec_load(&st
.st_mtim
))
400 static int properties_prepare(sd_hwdb
*hwdb
, const char *modalias
) {
404 ordered_hashmap_clear(hwdb
->properties
);
405 hwdb
->properties_modified
= true;
407 return trie_search_f(hwdb
, modalias
);
410 _public_
int sd_hwdb_get(sd_hwdb
*hwdb
, const char *modalias
, const char *key
, const char **_value
) {
411 const struct trie_value_entry_f
*entry
;
414 assert_return(hwdb
, -EINVAL
);
415 assert_return(hwdb
->f
, -EINVAL
);
416 assert_return(modalias
, -EINVAL
);
417 assert_return(_value
, -EINVAL
);
419 r
= properties_prepare(hwdb
, modalias
);
423 entry
= ordered_hashmap_get(hwdb
->properties
, key
);
427 *_value
= trie_string(hwdb
, entry
->value_off
);
432 _public_
int sd_hwdb_seek(sd_hwdb
*hwdb
, const char *modalias
) {
435 assert_return(hwdb
, -EINVAL
);
436 assert_return(hwdb
->f
, -EINVAL
);
437 assert_return(modalias
, -EINVAL
);
439 r
= properties_prepare(hwdb
, modalias
);
443 hwdb
->properties_modified
= false;
444 hwdb
->properties_iterator
= ITERATOR_FIRST
;
449 _public_
int sd_hwdb_enumerate(sd_hwdb
*hwdb
, const char **key
, const char **value
) {
450 const struct trie_value_entry_f
*entry
;
453 assert_return(hwdb
, -EINVAL
);
454 assert_return(key
, -EINVAL
);
455 assert_return(value
, -EINVAL
);
457 if (hwdb
->properties_modified
)
460 ordered_hashmap_iterate(hwdb
->properties
, &hwdb
->properties_iterator
, (void **)&entry
, &k
);
465 *value
= trie_string(hwdb
, entry
->value_off
);