2
This file is part of systemd.
4
Copyright 2012 Kay Sievers <kay@vrfy.org>
6
systemd is free software; you can redistribute it and/or modify it
7
under the terms of the GNU Lesser General Public License as published by
8
the Free Software Foundation; either version 2.1 of the License, or
9
(at your option) any later version.
11
systemd is distributed in the hope that it will be useful, but
12
WITHOUT ANY WARRANTY; without even the implied warranty of
13
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14
Lesser General Public License for more details.
16
You should have received a copy of the GNU Lesser General Public License
17
along with systemd; If not, see <http://www.gnu.org/licenses/>.
27
#include "conf-files.h"
30
#include "libudev-hwdb-def.h"
33
* Generic udev properties, key/value database based on modalias strings.
34
* Uses a Patricia/radix trie to index all matches for efficient lookup.
37
static const char * const conf_file_dirs[] = {
39
UDEVLIBEXECDIR "/hwdb.d",
43
/* in-memory trie objects */
45
struct trie_node *root;
46
struct strbuf *strings;
49
size_t children_count;
54
/* prefix, common part for all children of this node */
57
/* sorted array of pointers to children nodes */
58
struct trie_child_entry *children;
59
uint8_t children_count;
61
/* sorted array of key/value pairs */
62
struct trie_value_entry *values;
66
/* children array item with char (0-255) index */
67
struct trie_child_entry {
69
struct trie_node *child;
72
/* value array item with key/value pairs */
73
struct trie_value_entry {
78
static int trie_children_cmp(const void *v1, const void *v2) {
79
const struct trie_child_entry *n1 = v1;
80
const struct trie_child_entry *n2 = v2;
85
static int node_add_child(struct trie *trie, struct trie_node *node, struct trie_node *node_child, uint8_t c) {
86
struct trie_child_entry *child;
88
/* extend array, add new entry, sort for bisection */
89
child = realloc(node->children, (node->children_count + 1) * sizeof(struct trie_child_entry));
93
node->children = child;
94
trie->children_count++;
95
node->children[node->children_count].c = c;
96
node->children[node->children_count].child = node_child;
97
node->children_count++;
98
qsort(node->children, node->children_count, sizeof(struct trie_child_entry), trie_children_cmp);
104
static struct trie_node *node_lookup(const struct trie_node *node, uint8_t c) {
105
struct trie_child_entry *child;
106
struct trie_child_entry search;
109
child = bsearch(&search, node->children, node->children_count, sizeof(struct trie_child_entry), trie_children_cmp);
115
static void trie_node_cleanup(struct trie_node *node) {
118
for (i = 0; i < node->children_count; i++)
119
trie_node_cleanup(node->children[i].child);
120
free(node->children);
125
static int trie_values_cmp(const void *v1, const void *v2, void *arg) {
126
const struct trie_value_entry *val1 = v1;
127
const struct trie_value_entry *val2 = v2;
128
struct trie *trie = arg;
130
return strcmp(trie->strings->buf + val1->key_off,
131
trie->strings->buf + val2->key_off);
134
static int trie_node_add_value(struct trie *trie, struct trie_node *node,
135
const char *key, const char *value) {
137
struct trie_value_entry *val;
139
k = strbuf_add_string(trie->strings, key, strlen(key));
142
v = strbuf_add_string(trie->strings, value, strlen(value));
146
if (node->values_count) {
147
struct trie_value_entry search = {
152
val = xbsearch_r(&search, node->values, node->values_count, sizeof(struct trie_value_entry), trie_values_cmp, trie);
154
/* replace existing earlier key with new value */
160
/* extend array, add new entry, sort for bisection */
161
val = realloc(node->values, (node->values_count + 1) * sizeof(struct trie_value_entry));
164
trie->values_count++;
166
node->values[node->values_count].key_off = k;
167
node->values[node->values_count].value_off = v;
168
node->values_count++;
169
qsort_r(node->values, node->values_count, sizeof(struct trie_value_entry), trie_values_cmp, trie);
173
static int trie_insert(struct trie *trie, struct trie_node *node, const char *search,
174
const char *key, const char *value) {
181
struct trie_node *child;
183
for (p = 0; (c = trie->strings->buf[node->prefix_off + p]); p++) {
184
_cleanup_free_ char *s = NULL;
186
_cleanup_free_ struct trie_node *new_child = NULL;
188
if (c == search[i + p])
192
new_child = calloc(sizeof(struct trie_node), 1);
196
/* move values from parent to child */
197
new_child->prefix_off = node->prefix_off + p+1;
198
new_child->children = node->children;
199
new_child->children_count = node->children_count;
200
new_child->values = node->values;
201
new_child->values_count = node->values_count;
203
/* update parent; use strdup() because the source gets realloc()d */
204
s = strndup(trie->strings->buf + node->prefix_off, p);
208
off = strbuf_add_string(trie->strings, s, p);
212
node->prefix_off = off;
213
node->children = NULL;
214
node->children_count = 0;
216
node->values_count = 0;
217
err = node_add_child(trie, node, new_child, c);
221
new_child = NULL; /* avoid cleanup */
228
return trie_node_add_value(trie, node, key, value);
230
child = node_lookup(node, c);
235
child = calloc(sizeof(struct trie_node), 1);
239
off = strbuf_add_string(trie->strings, search + i+1, strlen(search + i+1));
245
child->prefix_off = off;
246
err = node_add_child(trie, node, child, c);
252
return trie_node_add_value(trie, child, key, value);
263
uint64_t strings_off;
265
uint64_t nodes_count;
266
uint64_t children_count;
267
uint64_t values_count;
270
/* calculate the storage space for the nodes, children arrays, value arrays */
271
static void trie_store_nodes_size(struct trie_f *trie, struct trie_node *node) {
274
for (i = 0; i < node->children_count; i++)
275
trie_store_nodes_size(trie, node->children[i].child);
277
trie->strings_off += sizeof(struct trie_node_f);
278
for (i = 0; i < node->children_count; i++)
279
trie->strings_off += sizeof(struct trie_child_entry_f);
280
for (i = 0; i < node->values_count; i++)
281
trie->strings_off += sizeof(struct trie_value_entry_f);
284
static int64_t trie_store_nodes(struct trie_f *trie, struct trie_node *node) {
286
struct trie_node_f n = {
287
.prefix_off = htole64(trie->strings_off + node->prefix_off),
288
.children_count = node->children_count,
289
.values_count = htole64(node->values_count),
291
struct trie_child_entry_f *children = NULL;
294
if (node->children_count) {
295
children = new0(struct trie_child_entry_f, node->children_count);
300
/* post-order recursion */
301
for (i = 0; i < node->children_count; i++) {
304
child_off = trie_store_nodes(trie, node->children[i].child);
307
children[i].c = node->children[i].c;
308
children[i].child_off = htole64(child_off);
312
node_off = ftello(trie->f);
313
fwrite(&n, sizeof(struct trie_node_f), 1, trie->f);
316
/* append children array */
317
if (node->children_count) {
318
fwrite(children, sizeof(struct trie_child_entry_f), node->children_count, trie->f);
319
trie->children_count += node->children_count;
323
/* append values array */
324
for (i = 0; i < node->values_count; i++) {
325
struct trie_value_entry_f v = {
326
.key_off = htole64(trie->strings_off + node->values[i].key_off),
327
.value_off = htole64(trie->strings_off + node->values[i].value_off),
330
fwrite(&v, sizeof(struct trie_value_entry_f), 1, trie->f);
331
trie->values_count++;
337
static int trie_store(struct trie *trie, const char *filename) {
345
struct trie_header_f h = {
346
.signature = HWDB_SIG,
347
.tool_version = htole64(atoi(VERSION)),
348
.header_size = htole64(sizeof(struct trie_header_f)),
349
.node_size = htole64(sizeof(struct trie_node_f)),
350
.child_entry_size = htole64(sizeof(struct trie_child_entry_f)),
351
.value_entry_size = htole64(sizeof(struct trie_value_entry_f)),
355
/* calculate size of header, nodes, children entries, value entries */
356
t.strings_off = sizeof(struct trie_header_f);
357
trie_store_nodes_size(&t, trie->root);
359
err = fopen_temporary(filename , &t.f, &filename_tmp);
362
fchmod(fileno(t.f), 0444);
365
fseeko(t.f, sizeof(struct trie_header_f), SEEK_SET);
366
root_off = trie_store_nodes(&t, trie->root);
367
h.nodes_root_off = htole64(root_off);
369
h.nodes_len = htole64(pos - sizeof(struct trie_header_f));
371
/* write string buffer */
372
fwrite(trie->strings->buf, trie->strings->len, 1, t.f);
373
h.strings_len = htole64(trie->strings->len);
377
h.file_size = htole64(size);
378
fseeko(t.f, 0, SEEK_SET);
379
fwrite(&h, sizeof(struct trie_header_f), 1, t.f);
384
if (err < 0 || rename(filename_tmp, filename) < 0) {
385
unlink(filename_tmp);
389
log_debug("=== trie on-disk ===\n");
390
log_debug("size: %8llu bytes\n", (unsigned long long)size);
391
log_debug("header: %8zu bytes\n", sizeof(struct trie_header_f));
392
log_debug("nodes: %8llu bytes (%8llu)\n",
393
(unsigned long long)t.nodes_count * sizeof(struct trie_node_f), (unsigned long long)t.nodes_count);
394
log_debug("child pointers: %8llu bytes (%8llu)\n",
395
(unsigned long long)t.children_count * sizeof(struct trie_child_entry_f), (unsigned long long)t.children_count);
396
log_debug("value pointers: %8llu bytes (%8llu)\n",
397
(unsigned long long)t.values_count * sizeof(struct trie_value_entry_f), (unsigned long long)t.values_count);
398
log_debug("string store: %8llu bytes\n", (unsigned long long)trie->strings->len);
399
log_debug("strings start: %8llu\n", (unsigned long long) t.strings_off);
405
static int import_file(struct trie *trie, const char *filename) {
408
char match[LINE_MAX];
411
f = fopen(filename, "re");
417
while (fgets(line, sizeof(line), f)) {
423
/* new line, new record */
424
if (line[0] == '\n') {
436
/* start of new record */
437
if (match[0] == '\0') {
443
if (line[0] == '+') {
448
/* TODO: support +; skip the entire record until we support it */
453
if (line[0] == ' ') {
456
value = strchr(line, '=');
461
trie_insert(trie, trie->root, match, line, value);
468
static void help(void) {
469
printf("Usage: udevadm hwdb OPTIONS\n"
470
" --update update the hardware database\n"
471
" --test=<modalias> query database and print result\n"
472
" --root=<path> alternative root path in the filesystem\n"
476
static int adm_hwdb(struct udev *udev, int argc, char *argv[]) {
477
static const struct option options[] = {
478
{ "update", no_argument, NULL, 'u' },
479
{ "root", required_argument, NULL, 'r' },
480
{ "test", required_argument, NULL, 't' },
481
{ "help", no_argument, NULL, 'h' },
484
const char *test = NULL;
485
const char *root = "";
487
struct trie *trie = NULL;
489
int rc = EXIT_SUCCESS;
494
option = getopt_long(argc, argv, "ut:r:h", options, NULL);
514
if (!update && !test) {
521
_cleanup_free_ char *hwdb_bin = NULL;
523
trie = calloc(sizeof(struct trie), 1);
530
trie->strings = strbuf_new();
531
if (!trie->strings) {
537
trie->root = calloc(sizeof(struct trie_node), 1);
544
err = conf_files_list_strv(&files, ".hwdb", root, conf_file_dirs);
546
log_error("failed to enumerate hwdb files: %s\n", strerror(-err));
550
STRV_FOREACH(f, files) {
551
log_debug("reading file '%s'", *f);
552
import_file(trie, *f);
556
strbuf_complete(trie->strings);
558
log_debug("=== trie in-memory ===\n");
559
log_debug("nodes: %8zu bytes (%8zu)\n",
560
trie->nodes_count * sizeof(struct trie_node), trie->nodes_count);
561
log_debug("children arrays: %8zu bytes (%8zu)\n",
562
trie->children_count * sizeof(struct trie_child_entry), trie->children_count);
563
log_debug("values arrays: %8zu bytes (%8zu)\n",
564
trie->values_count * sizeof(struct trie_value_entry), trie->values_count);
565
log_debug("strings: %8zu bytes\n",
567
log_debug("strings incoming: %8zu bytes (%8zu)\n",
568
trie->strings->in_len, trie->strings->in_count);
569
log_debug("strings dedup'ed: %8zu bytes (%8zu)\n",
570
trie->strings->dedup_len, trie->strings->dedup_count);
572
if (asprintf(&hwdb_bin, "%s/etc/udev/hwdb.bin", root) < 0) {
576
mkdir_parents(hwdb_bin, 0755);
577
err = trie_store(trie, hwdb_bin);
579
log_error("Failure writing database %s: %s", hwdb_bin, strerror(-err));
585
struct udev_hwdb *hwdb = udev_hwdb_new(udev);
588
struct udev_list_entry *entry;
590
udev_list_entry_foreach(entry, udev_hwdb_get_properties_list_entry(hwdb, test, 0))
591
printf("%s=%s\n", udev_list_entry_get_name(entry), udev_list_entry_get_value(entry));
592
hwdb = udev_hwdb_unref(hwdb);
598
trie_node_cleanup(trie->root);
599
strbuf_cleanup(trie->strings);
605
const struct udevadm_cmd udevadm_hwdb = {
608
.help = "maintain the hardware database index",