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>
9 systemd is free software; you can redistribute it and/or modify it
10 under the terms of the GNU Lesser General Public License as published by
11 the Free Software Foundation; either version 2.1 of the License, or
12 (at your option) any later version.
14 systemd is distributed in the hope that it will be useful, but
15 WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
17 Lesser General Public License for more details.
19 You should have received a copy of the GNU Lesser General Public License
20 along with systemd; If not, see <http://www.gnu.org/licenses/>.
33 #include "alloc-util.h"
36 #include "hwdb-internal.h"
37 #include "hwdb-util.h"
39 #include "string-util.h"
48 struct trie_header_f
*head
;
52 OrderedHashmap
*properties
;
53 Iterator properties_iterator
;
54 bool properties_modified
;
63 static void linebuf_init(struct linebuf
*buf
) {
68 static const char *linebuf_get(struct linebuf
*buf
) {
69 if (buf
->len
+ 1 >= sizeof(buf
->bytes
))
71 buf
->bytes
[buf
->len
] = '\0';
75 static bool linebuf_add(struct linebuf
*buf
, const char *s
, size_t len
) {
76 if (buf
->len
+ len
>= sizeof(buf
->bytes
))
78 memcpy(buf
->bytes
+ buf
->len
, s
, len
);
83 static bool linebuf_add_char(struct linebuf
*buf
, char c
) {
84 if (buf
->len
+ 1 >= sizeof(buf
->bytes
))
86 buf
->bytes
[buf
->len
++] = c
;
90 static void linebuf_rem(struct linebuf
*buf
, size_t count
) {
91 assert(buf
->len
>= count
);
95 static void linebuf_rem_char(struct linebuf
*buf
) {
99 static const struct trie_child_entry_f
*trie_node_child(sd_hwdb
*hwdb
, const struct trie_node_f
*node
, size_t idx
) {
100 const char *base
= (const char *)node
;
102 base
+= le64toh(hwdb
->head
->node_size
);
103 base
+= idx
* le64toh(hwdb
->head
->child_entry_size
);
104 return (const struct trie_child_entry_f
*)base
;
107 static const struct trie_value_entry_f
*trie_node_value(sd_hwdb
*hwdb
, const struct trie_node_f
*node
, size_t idx
) {
108 const char *base
= (const char *)node
;
110 base
+= le64toh(hwdb
->head
->node_size
);
111 base
+= node
->children_count
* le64toh(hwdb
->head
->child_entry_size
);
112 base
+= idx
* le64toh(hwdb
->head
->value_entry_size
);
113 return (const struct trie_value_entry_f
*)base
;
116 static const struct trie_node_f
*trie_node_from_off(sd_hwdb
*hwdb
, le64_t off
) {
117 return (const struct trie_node_f
*)(hwdb
->map
+ le64toh(off
));
120 static const char *trie_string(sd_hwdb
*hwdb
, le64_t off
) {
121 return hwdb
->map
+ le64toh(off
);
124 static int trie_children_cmp_f(const void *v1
, const void *v2
) {
125 const struct trie_child_entry_f
*n1
= v1
;
126 const struct trie_child_entry_f
*n2
= v2
;
128 return n1
->c
- n2
->c
;
131 static const struct trie_node_f
*node_lookup_f(sd_hwdb
*hwdb
, const struct trie_node_f
*node
, uint8_t c
) {
132 struct trie_child_entry_f
*child
;
133 struct trie_child_entry_f search
;
136 child
= bsearch(&search
, (const char *)node
+ le64toh(hwdb
->head
->node_size
), node
->children_count
,
137 le64toh(hwdb
->head
->child_entry_size
), trie_children_cmp_f
);
139 return trie_node_from_off(hwdb
, child
->child_off
);
143 static int hwdb_add_property(sd_hwdb
*hwdb
, const struct trie_value_entry_f
*entry
) {
149 key
= trie_string(hwdb
, entry
->key_off
);
152 * Silently ignore all properties which do not start with a
153 * space; future extensions might use additional prefixes.
160 if (le64toh(hwdb
->head
->value_entry_size
) >= sizeof(struct trie_value_entry2_f
)) {
161 const struct trie_value_entry2_f
*old
, *entry2
;
163 entry2
= (const struct trie_value_entry2_f
*)entry
;
164 old
= ordered_hashmap_get(hwdb
->properties
, key
);
166 /* On duplicates, we order by filename priority and line-number.
169 * v2 of the format had 64 bits for the line number.
170 * v3 reuses top 32 bits of line_number to store the priority.
171 * We check the top bits — if they are zero we have v2 format.
172 * This means that v2 clients will print wrong line numbers with
175 * For v3 data: we compare the priority (of the source file)
176 * and the line number.
178 * For v2 data: we rely on the fact that the filenames in the hwdb
179 * are added in the order of priority (higher later), because they
180 * are *processed* in the order of priority. So we compare the
181 * indices to determine which file had higher priority. Comparing
182 * the strings alphabetically would be useless, because those are
183 * full paths, and e.g. /usr/lib would sort after /etc, even
184 * though it has lower priority. This is not reliable because of
185 * suffix compression, but should work for the most common case of
186 * /usr/lib/udev/hwbd.d and /etc/udev/hwdb.d, and is better than
187 * not doing the comparison at all.
191 if (entry2
->file_priority
== 0)
192 lower
= entry2
->filename_off
< old
->filename_off
||
193 (entry2
->filename_off
== old
->filename_off
&& entry2
->line_number
< old
->line_number
);
195 lower
= entry2
->file_priority
< old
->file_priority
||
196 (entry2
->file_priority
== old
->file_priority
&& entry2
->line_number
< old
->line_number
);
202 r
= ordered_hashmap_ensure_allocated(&hwdb
->properties
, &string_hash_ops
);
206 r
= ordered_hashmap_replace(hwdb
->properties
, key
, (void *)entry
);
210 hwdb
->properties_modified
= true;
215 static int trie_fnmatch_f(sd_hwdb
*hwdb
, const struct trie_node_f
*node
, size_t p
,
216 struct linebuf
*buf
, const char *search
) {
222 prefix
= trie_string(hwdb
, node
->prefix_off
);
223 len
= strlen(prefix
+ p
);
224 linebuf_add(buf
, prefix
+ p
, len
);
226 for (i
= 0; i
< node
->children_count
; i
++) {
227 const struct trie_child_entry_f
*child
= trie_node_child(hwdb
, node
, i
);
229 linebuf_add_char(buf
, child
->c
);
230 err
= trie_fnmatch_f(hwdb
, trie_node_from_off(hwdb
, child
->child_off
), 0, buf
, search
);
233 linebuf_rem_char(buf
);
236 if (le64toh(node
->values_count
) && fnmatch(linebuf_get(buf
), search
, 0) == 0)
237 for (i
= 0; i
< le64toh(node
->values_count
); i
++) {
238 err
= hwdb_add_property(hwdb
, trie_node_value(hwdb
, node
, i
));
243 linebuf_rem(buf
, len
);
247 static int trie_search_f(sd_hwdb
*hwdb
, const char *search
) {
249 const struct trie_node_f
*node
;
255 node
= trie_node_from_off(hwdb
, hwdb
->head
->nodes_root_off
);
257 const struct trie_node_f
*child
;
260 if (node
->prefix_off
) {
263 for (; (c
= trie_string(hwdb
, node
->prefix_off
)[p
]); p
++) {
264 if (IN_SET(c
, '*', '?', '['))
265 return trie_fnmatch_f(hwdb
, node
, p
, &buf
, search
+ i
+ p
);
266 if (c
!= search
[i
+ p
])
272 child
= node_lookup_f(hwdb
, node
, '*');
274 linebuf_add_char(&buf
, '*');
275 err
= trie_fnmatch_f(hwdb
, child
, 0, &buf
, search
+ i
);
278 linebuf_rem_char(&buf
);
281 child
= node_lookup_f(hwdb
, node
, '?');
283 linebuf_add_char(&buf
, '?');
284 err
= trie_fnmatch_f(hwdb
, child
, 0, &buf
, search
+ i
);
287 linebuf_rem_char(&buf
);
290 child
= node_lookup_f(hwdb
, node
, '[');
292 linebuf_add_char(&buf
, '[');
293 err
= trie_fnmatch_f(hwdb
, child
, 0, &buf
, search
+ i
);
296 linebuf_rem_char(&buf
);
299 if (search
[i
] == '\0') {
302 for (n
= 0; n
< le64toh(node
->values_count
); n
++) {
303 err
= hwdb_add_property(hwdb
, trie_node_value(hwdb
, node
, n
));
310 child
= node_lookup_f(hwdb
, node
, search
[i
]);
317 static const char hwdb_bin_paths
[] =
318 "/etc/systemd/hwdb/hwdb.bin\0"
319 "/etc/udev/hwdb.bin\0"
320 "/usr/lib/systemd/hwdb/hwdb.bin\0"
322 "/lib/systemd/hwdb/hwdb.bin\0"
324 UDEVLIBEXECDIR
"/hwdb.bin\0";
326 _public_
int sd_hwdb_new(sd_hwdb
**ret
) {
327 _cleanup_(sd_hwdb_unrefp
) sd_hwdb
*hwdb
= NULL
;
328 const char *hwdb_bin_path
;
329 const char sig
[] = HWDB_SIG
;
331 assert_return(ret
, -EINVAL
);
333 hwdb
= new0(sd_hwdb
, 1);
337 hwdb
->n_ref
= REFCNT_INIT
;
339 /* find hwdb.bin in hwdb_bin_paths */
340 NULSTR_FOREACH(hwdb_bin_path
, hwdb_bin_paths
) {
341 hwdb
->f
= fopen(hwdb_bin_path
, "re");
344 else if (errno
== ENOENT
)
347 return log_debug_errno(errno
, "error reading %s: %m", hwdb_bin_path
);
351 log_debug("hwdb.bin does not exist, please run systemd-hwdb update");
355 if (fstat(fileno(hwdb
->f
), &hwdb
->st
) < 0 ||
356 (size_t)hwdb
->st
.st_size
< offsetof(struct trie_header_f
, strings_len
) + 8)
357 return log_debug_errno(errno
, "error reading %s: %m", hwdb_bin_path
);
359 hwdb
->map
= mmap(0, hwdb
->st
.st_size
, PROT_READ
, MAP_SHARED
, fileno(hwdb
->f
), 0);
360 if (hwdb
->map
== MAP_FAILED
)
361 return log_debug_errno(errno
, "error mapping %s: %m", hwdb_bin_path
);
363 if (memcmp(hwdb
->map
, sig
, sizeof(hwdb
->head
->signature
)) != 0 ||
364 (size_t)hwdb
->st
.st_size
!= le64toh(hwdb
->head
->file_size
)) {
365 log_debug("error recognizing the format of %s", hwdb_bin_path
);
369 log_debug("=== trie on-disk ===");
370 log_debug("tool version: %"PRIu64
, le64toh(hwdb
->head
->tool_version
));
371 log_debug("file size: %8"PRIi64
" bytes", hwdb
->st
.st_size
);
372 log_debug("header size %8"PRIu64
" bytes", le64toh(hwdb
->head
->header_size
));
373 log_debug("strings %8"PRIu64
" bytes", le64toh(hwdb
->head
->strings_len
));
374 log_debug("nodes %8"PRIu64
" bytes", le64toh(hwdb
->head
->nodes_len
));
382 _public_ sd_hwdb
*sd_hwdb_ref(sd_hwdb
*hwdb
) {
383 assert_return(hwdb
, NULL
);
385 assert_se(REFCNT_INC(hwdb
->n_ref
) >= 2);
390 _public_ sd_hwdb
*sd_hwdb_unref(sd_hwdb
*hwdb
) {
391 if (hwdb
&& REFCNT_DEC(hwdb
->n_ref
) == 0) {
393 munmap((void *)hwdb
->map
, hwdb
->st
.st_size
);
394 safe_fclose(hwdb
->f
);
395 ordered_hashmap_free(hwdb
->properties
);
402 bool hwdb_validate(sd_hwdb
*hwdb
) {
412 /* if hwdb.bin doesn't exist anywhere, we need to update */
413 NULSTR_FOREACH(p
, hwdb_bin_paths
) {
414 if (stat(p
, &st
) >= 0) {
422 if (timespec_load(&hwdb
->st
.st_mtim
) != timespec_load(&st
.st_mtim
))
427 static int properties_prepare(sd_hwdb
*hwdb
, const char *modalias
) {
431 ordered_hashmap_clear(hwdb
->properties
);
432 hwdb
->properties_modified
= true;
434 return trie_search_f(hwdb
, modalias
);
437 _public_
int sd_hwdb_get(sd_hwdb
*hwdb
, const char *modalias
, const char *key
, const char **_value
) {
438 const struct trie_value_entry_f
*entry
;
441 assert_return(hwdb
, -EINVAL
);
442 assert_return(hwdb
->f
, -EINVAL
);
443 assert_return(modalias
, -EINVAL
);
444 assert_return(_value
, -EINVAL
);
446 r
= properties_prepare(hwdb
, modalias
);
450 entry
= ordered_hashmap_get(hwdb
->properties
, key
);
454 *_value
= trie_string(hwdb
, entry
->value_off
);
459 _public_
int sd_hwdb_seek(sd_hwdb
*hwdb
, const char *modalias
) {
462 assert_return(hwdb
, -EINVAL
);
463 assert_return(hwdb
->f
, -EINVAL
);
464 assert_return(modalias
, -EINVAL
);
466 r
= properties_prepare(hwdb
, modalias
);
470 hwdb
->properties_modified
= false;
471 hwdb
->properties_iterator
= ITERATOR_FIRST
;
476 _public_
int sd_hwdb_enumerate(sd_hwdb
*hwdb
, const char **key
, const char **value
) {
477 const struct trie_value_entry_f
*entry
;
480 assert_return(hwdb
, -EINVAL
);
481 assert_return(key
, -EINVAL
);
482 assert_return(value
, -EINVAL
);
484 if (hwdb
->properties_modified
)
487 ordered_hashmap_iterate(hwdb
->properties
, &hwdb
->properties_iterator
, (void **)&entry
, &k
);
492 *value
= trie_string(hwdb
, entry
->value_off
);