1 /* SPDX-License-Identifier: LGPL-2.1-or-later */
2 /***
3 Copyright © 2008 Alan Jenkins <alan.christopher.jenkins@googlemail.com>
4 ***/
5
6 #include <errno.h>
7 #include <fnmatch.h>
8 #include <inttypes.h>
9 #include <stdio.h>
10 #include <stdlib.h>
11 #include <sys/mman.h>
12 #include <sys/stat.h>
13
14 #include "sd-hwdb.h"
15
16 #include "alloc-util.h"
17 #include "fd-util.h"
18 #include "fileio.h"
19 #include "hashmap.h"
20 #include "hwdb-internal.h"
21 #include "nulstr-util.h"
22 #include "string-util.h"
23 #include "time-util.h"
24
25 struct linebuf {
26 char bytes[LINE_MAX];
27 size_t size;
28 size_t len;
29 };
30
linebuf_init(struct linebuf * buf)31 static void linebuf_init(struct linebuf *buf) {
32 buf->size = 0;
33 buf->len = 0;
34 }
35
linebuf_get(struct linebuf * buf)36 static const char *linebuf_get(struct linebuf *buf) {
37 if (buf->len + 1 >= sizeof(buf->bytes))
38 return NULL;
39 buf->bytes[buf->len] = '\0';
40 return buf->bytes;
41 }
42
linebuf_add(struct linebuf * buf,const char * s,size_t len)43 static bool linebuf_add(struct linebuf *buf, const char *s, size_t len) {
44 if (buf->len + len >= sizeof(buf->bytes))
45 return false;
46 memcpy(buf->bytes + buf->len, s, len);
47 buf->len += len;
48 return true;
49 }
50
linebuf_add_char(struct linebuf * buf,char c)51 static bool linebuf_add_char(struct linebuf *buf, char c) {
52 if (buf->len + 1 >= sizeof(buf->bytes))
53 return false;
54 buf->bytes[buf->len++] = c;
55 return true;
56 }
57
linebuf_rem(struct linebuf * buf,size_t count)58 static void linebuf_rem(struct linebuf *buf, size_t count) {
59 assert(buf->len >= count);
60 buf->len -= count;
61 }
62
linebuf_rem_char(struct linebuf * buf)63 static void linebuf_rem_char(struct linebuf *buf) {
64 linebuf_rem(buf, 1);
65 }
66
trie_node_child(sd_hwdb * hwdb,const struct trie_node_f * node,size_t idx)67 static const struct trie_child_entry_f *trie_node_child(sd_hwdb *hwdb, const struct trie_node_f *node, size_t idx) {
68 const char *base = (const char *)node;
69
70 base += le64toh(hwdb->head->node_size);
71 base += idx * le64toh(hwdb->head->child_entry_size);
72 return (const struct trie_child_entry_f *)base;
73 }
74
trie_node_value(sd_hwdb * hwdb,const struct trie_node_f * node,size_t idx)75 static const struct trie_value_entry_f *trie_node_value(sd_hwdb *hwdb, const struct trie_node_f *node, size_t idx) {
76 const char *base = (const char *)node;
77
78 base += le64toh(hwdb->head->node_size);
79 base += node->children_count * le64toh(hwdb->head->child_entry_size);
80 base += idx * le64toh(hwdb->head->value_entry_size);
81 return (const struct trie_value_entry_f *)base;
82 }
83
trie_node_from_off(sd_hwdb * hwdb,le64_t off)84 static const struct trie_node_f *trie_node_from_off(sd_hwdb *hwdb, le64_t off) {
85 return (const struct trie_node_f *)(hwdb->map + le64toh(off));
86 }
87
trie_string(sd_hwdb * hwdb,le64_t off)88 static const char *trie_string(sd_hwdb *hwdb, le64_t off) {
89 return hwdb->map + le64toh(off);
90 }
91
trie_children_cmp_f(const void * v1,const void * v2)92 static int trie_children_cmp_f(const void *v1, const void *v2) {
93 const struct trie_child_entry_f *n1 = v1;
94 const struct trie_child_entry_f *n2 = v2;
95
96 return n1->c - n2->c;
97 }
98
node_lookup_f(sd_hwdb * hwdb,const struct trie_node_f * node,uint8_t c)99 static const struct trie_node_f *node_lookup_f(sd_hwdb *hwdb, const struct trie_node_f *node, uint8_t c) {
100 struct trie_child_entry_f *child;
101 struct trie_child_entry_f search;
102
103 search.c = c;
104 child = bsearch(&search, (const char *)node + le64toh(hwdb->head->node_size), node->children_count,
105 le64toh(hwdb->head->child_entry_size), trie_children_cmp_f);
106 if (child)
107 return trie_node_from_off(hwdb, child->child_off);
108 return NULL;
109 }
110
hwdb_add_property(sd_hwdb * hwdb,const struct trie_value_entry_f * entry)111 static int hwdb_add_property(sd_hwdb *hwdb, const struct trie_value_entry_f *entry) {
112 const char *key;
113 int r;
114
115 assert(hwdb);
116
117 key = trie_string(hwdb, entry->key_off);
118
119 /*
120 * Silently ignore all properties which do not start with a
121 * space; future extensions might use additional prefixes.
122 */
123 if (key[0] != ' ')
124 return 0;
125
126 key++;
127
128 if (le64toh(hwdb->head->value_entry_size) >= sizeof(struct trie_value_entry2_f)) {
129 const struct trie_value_entry2_f *old, *entry2;
130
131 entry2 = (const struct trie_value_entry2_f *)entry;
132 old = ordered_hashmap_get(hwdb->properties, key);
133 if (old) {
134 /* On duplicates, we order by filename priority and line-number.
135 *
136 * v2 of the format had 64 bits for the line number.
137 * v3 reuses top 32 bits of line_number to store the priority.
138 * We check the top bits — if they are zero we have v2 format.
139 * This means that v2 clients will print wrong line numbers with
140 * v3 data.
141 *
142 * For v3 data: we compare the priority (of the source file)
143 * and the line number.
144 *
145 * For v2 data: we rely on the fact that the filenames in the hwdb
146 * are added in the order of priority (higher later), because they
147 * are *processed* in the order of priority. So we compare the
148 * indices to determine which file had higher priority. Comparing
149 * the strings alphabetically would be useless, because those are
150 * full paths, and e.g. /usr/lib would sort after /etc, even
151 * though it has lower priority. This is not reliable because of
152 * suffix compression, but should work for the most common case of
153 * /usr/lib/udev/hwbd.d and /etc/udev/hwdb.d, and is better than
154 * not doing the comparison at all.
155 */
156 bool lower;
157
158 if (entry2->file_priority == 0)
159 lower = entry2->filename_off < old->filename_off ||
160 (entry2->filename_off == old->filename_off && entry2->line_number < old->line_number);
161 else
162 lower = entry2->file_priority < old->file_priority ||
163 (entry2->file_priority == old->file_priority && entry2->line_number < old->line_number);
164 if (lower)
165 return 0;
166 }
167 }
168
169 r = ordered_hashmap_ensure_allocated(&hwdb->properties, &string_hash_ops);
170 if (r < 0)
171 return r;
172
173 r = ordered_hashmap_replace(hwdb->properties, key, (void *)entry);
174 if (r < 0)
175 return r;
176
177 hwdb->properties_modified = true;
178
179 return 0;
180 }
181
trie_fnmatch_f(sd_hwdb * hwdb,const struct trie_node_f * node,size_t p,struct linebuf * buf,const char * search)182 static int trie_fnmatch_f(sd_hwdb *hwdb, const struct trie_node_f *node, size_t p,
183 struct linebuf *buf, const char *search) {
184 size_t len;
185 size_t i;
186 const char *prefix;
187 int err;
188
189 prefix = trie_string(hwdb, node->prefix_off);
190 len = strlen(prefix + p);
191 linebuf_add(buf, prefix + p, len);
192
193 for (i = 0; i < node->children_count; i++) {
194 const struct trie_child_entry_f *child = trie_node_child(hwdb, node, i);
195
196 linebuf_add_char(buf, child->c);
197 err = trie_fnmatch_f(hwdb, trie_node_from_off(hwdb, child->child_off), 0, buf, search);
198 if (err < 0)
199 return err;
200 linebuf_rem_char(buf);
201 }
202
203 if (le64toh(node->values_count) && fnmatch(linebuf_get(buf), search, 0) == 0)
204 for (i = 0; i < le64toh(node->values_count); i++) {
205 err = hwdb_add_property(hwdb, trie_node_value(hwdb, node, i));
206 if (err < 0)
207 return err;
208 }
209
210 linebuf_rem(buf, len);
211 return 0;
212 }
213
trie_search_f(sd_hwdb * hwdb,const char * search)214 static int trie_search_f(sd_hwdb *hwdb, const char *search) {
215 struct linebuf buf;
216 const struct trie_node_f *node;
217 size_t i = 0;
218 int err;
219
220 linebuf_init(&buf);
221
222 node = trie_node_from_off(hwdb, hwdb->head->nodes_root_off);
223 while (node) {
224 const struct trie_node_f *child;
225 size_t p = 0;
226
227 if (node->prefix_off) {
228 char c;
229
230 for (; (c = trie_string(hwdb, node->prefix_off)[p]); p++) {
231 if (IN_SET(c, '*', '?', '['))
232 return trie_fnmatch_f(hwdb, node, p, &buf, search + i + p);
233 if (c != search[i + p])
234 return 0;
235 }
236 i += p;
237 }
238
239 child = node_lookup_f(hwdb, node, '*');
240 if (child) {
241 linebuf_add_char(&buf, '*');
242 err = trie_fnmatch_f(hwdb, child, 0, &buf, search + i);
243 if (err < 0)
244 return err;
245 linebuf_rem_char(&buf);
246 }
247
248 child = node_lookup_f(hwdb, node, '?');
249 if (child) {
250 linebuf_add_char(&buf, '?');
251 err = trie_fnmatch_f(hwdb, child, 0, &buf, search + i);
252 if (err < 0)
253 return err;
254 linebuf_rem_char(&buf);
255 }
256
257 child = node_lookup_f(hwdb, node, '[');
258 if (child) {
259 linebuf_add_char(&buf, '[');
260 err = trie_fnmatch_f(hwdb, child, 0, &buf, search + i);
261 if (err < 0)
262 return err;
263 linebuf_rem_char(&buf);
264 }
265
266 if (search[i] == '\0') {
267 size_t n;
268
269 for (n = 0; n < le64toh(node->values_count); n++) {
270 err = hwdb_add_property(hwdb, trie_node_value(hwdb, node, n));
271 if (err < 0)
272 return err;
273 }
274 return 0;
275 }
276
277 child = node_lookup_f(hwdb, node, search[i]);
278 node = child;
279 i++;
280 }
281 return 0;
282 }
283
sd_hwdb_new(sd_hwdb ** ret)284 _public_ int sd_hwdb_new(sd_hwdb **ret) {
285 _cleanup_(sd_hwdb_unrefp) sd_hwdb *hwdb = NULL;
286 const char *hwdb_bin_path;
287 const char sig[] = HWDB_SIG;
288
289 assert_return(ret, -EINVAL);
290
291 hwdb = new0(sd_hwdb, 1);
292 if (!hwdb)
293 return -ENOMEM;
294
295 hwdb->n_ref = 1;
296
297 /* find hwdb.bin in hwdb_bin_paths */
298 NULSTR_FOREACH(hwdb_bin_path, hwdb_bin_paths) {
299 log_debug("Trying to open \"%s\"...", hwdb_bin_path);
300 hwdb->f = fopen(hwdb_bin_path, "re");
301 if (hwdb->f)
302 break;
303 if (errno != ENOENT)
304 return log_debug_errno(errno, "Failed to open %s: %m", hwdb_bin_path);
305 }
306
307 if (!hwdb->f)
308 return log_debug_errno(SYNTHETIC_ERRNO(ENOENT),
309 "hwdb.bin does not exist, please run 'systemd-hwdb update'");
310
311 if (fstat(fileno(hwdb->f), &hwdb->st) < 0)
312 return log_debug_errno(errno, "Failed to stat %s: %m", hwdb_bin_path);
313 if (hwdb->st.st_size < (off_t) offsetof(struct trie_header_f, strings_len) + 8)
314 return log_debug_errno(SYNTHETIC_ERRNO(EIO),
315 "File %s is too short: %m", hwdb_bin_path);
316 if (file_offset_beyond_memory_size(hwdb->st.st_size))
317 return log_debug_errno(SYNTHETIC_ERRNO(EFBIG),
318 "File %s is too long: %m", hwdb_bin_path);
319
320 hwdb->map = mmap(0, hwdb->st.st_size, PROT_READ, MAP_SHARED, fileno(hwdb->f), 0);
321 if (hwdb->map == MAP_FAILED)
322 return log_debug_errno(errno, "Failed to map %s: %m", hwdb_bin_path);
323
324 if (memcmp(hwdb->map, sig, sizeof(hwdb->head->signature)) != 0 ||
325 (size_t) hwdb->st.st_size != le64toh(hwdb->head->file_size))
326 return log_debug_errno(SYNTHETIC_ERRNO(EINVAL),
327 "Failed to recognize the format of %s",
328 hwdb_bin_path);
329
330 log_debug("=== trie on-disk ===");
331 log_debug("tool version: %"PRIu64, le64toh(hwdb->head->tool_version));
332 log_debug("file size: %8"PRIi64" bytes", hwdb->st.st_size);
333 log_debug("header size %8"PRIu64" bytes", le64toh(hwdb->head->header_size));
334 log_debug("strings %8"PRIu64" bytes", le64toh(hwdb->head->strings_len));
335 log_debug("nodes %8"PRIu64" bytes", le64toh(hwdb->head->nodes_len));
336
337 *ret = TAKE_PTR(hwdb);
338
339 return 0;
340 }
341
hwdb_free(sd_hwdb * hwdb)342 static sd_hwdb *hwdb_free(sd_hwdb *hwdb) {
343 assert(hwdb);
344
345 if (hwdb->map)
346 munmap((void *)hwdb->map, hwdb->st.st_size);
347 safe_fclose(hwdb->f);
348 ordered_hashmap_free(hwdb->properties);
349 return mfree(hwdb);
350 }
351
DEFINE_PUBLIC_TRIVIAL_REF_UNREF_FUNC(sd_hwdb,sd_hwdb,hwdb_free)352 DEFINE_PUBLIC_TRIVIAL_REF_UNREF_FUNC(sd_hwdb, sd_hwdb, hwdb_free)
353
354 static int properties_prepare(sd_hwdb *hwdb, const char *modalias) {
355 assert(hwdb);
356 assert(modalias);
357
358 ordered_hashmap_clear(hwdb->properties);
359 hwdb->properties_modified = true;
360
361 return trie_search_f(hwdb, modalias);
362 }
363
sd_hwdb_get(sd_hwdb * hwdb,const char * modalias,const char * key,const char ** _value)364 _public_ int sd_hwdb_get(sd_hwdb *hwdb, const char *modalias, const char *key, const char **_value) {
365 const struct trie_value_entry_f *entry;
366 int r;
367
368 assert_return(hwdb, -EINVAL);
369 assert_return(hwdb->f, -EINVAL);
370 assert_return(modalias, -EINVAL);
371 assert_return(_value, -EINVAL);
372
373 r = properties_prepare(hwdb, modalias);
374 if (r < 0)
375 return r;
376
377 entry = ordered_hashmap_get(hwdb->properties, key);
378 if (!entry)
379 return -ENOENT;
380
381 *_value = trie_string(hwdb, entry->value_off);
382
383 return 0;
384 }
385
sd_hwdb_seek(sd_hwdb * hwdb,const char * modalias)386 _public_ int sd_hwdb_seek(sd_hwdb *hwdb, const char *modalias) {
387 int r;
388
389 assert_return(hwdb, -EINVAL);
390 assert_return(hwdb->f, -EINVAL);
391 assert_return(modalias, -EINVAL);
392
393 r = properties_prepare(hwdb, modalias);
394 if (r < 0)
395 return r;
396
397 hwdb->properties_modified = false;
398 hwdb->properties_iterator = ITERATOR_FIRST;
399
400 return 0;
401 }
402
sd_hwdb_enumerate(sd_hwdb * hwdb,const char ** key,const char ** value)403 _public_ int sd_hwdb_enumerate(sd_hwdb *hwdb, const char **key, const char **value) {
404 const struct trie_value_entry_f *entry;
405 const void *k;
406
407 assert_return(hwdb, -EINVAL);
408 assert_return(key, -EINVAL);
409 assert_return(value, -EINVAL);
410
411 if (hwdb->properties_modified)
412 return -EAGAIN;
413
414 if (!ordered_hashmap_iterate(hwdb->properties, &hwdb->properties_iterator, (void **)&entry, &k))
415 return 0;
416
417 *key = k;
418 *value = trie_string(hwdb, entry->value_off);
419
420 return 1;
421 }
422