From 8bf9763656c9209f74cda460225da5a9939494cc Mon Sep 17 00:00:00 2001 From: David Herrmann Date: Wed, 21 Sep 2016 14:56:04 +0200 Subject: sd-hwdb: fix child/value offset calculation It is not legal to use hard-coded types to calculate offsets. We must always use the offsets of the hwdb header to calculate those. Otherwise, we will break horribly if run on hwdb files written by other implementations or written with future extensions. Signed-off-by: David Herrmann --- src/libsystemd/sd-hwdb/sd-hwdb.c | 23 ++++++++++++++--------- 1 file changed, 14 insertions(+), 9 deletions(-) (limited to 'src') diff --git a/src/libsystemd/sd-hwdb/sd-hwdb.c b/src/libsystemd/sd-hwdb/sd-hwdb.c index 062fa97b17..fb9522959f 100644 --- a/src/libsystemd/sd-hwdb/sd-hwdb.c +++ b/src/libsystemd/sd-hwdb/sd-hwdb.c @@ -97,15 +97,20 @@ static void linebuf_rem_char(struct linebuf *buf) { linebuf_rem(buf, 1); } -static const struct trie_child_entry_f *trie_node_children(sd_hwdb *hwdb, const struct trie_node_f *node) { - return (const struct trie_child_entry_f *)((const char *)node + le64toh(hwdb->head->node_size)); +static const struct trie_child_entry_f *trie_node_child(sd_hwdb *hwdb, const struct trie_node_f *node, size_t idx) { + const char *base = (const char *)node; + + base += le64toh(hwdb->head->node_size); + base += idx * le64toh(hwdb->head->child_entry_size); + return (const struct trie_child_entry_f *)base; } -static const struct trie_value_entry_f *trie_node_values(sd_hwdb *hwdb, const struct trie_node_f *node) { +static const struct trie_value_entry_f *trie_node_value(sd_hwdb *hwdb, const struct trie_node_f *node, size_t idx) { const char *base = (const char *)node; base += le64toh(hwdb->head->node_size); base += node->children_count * le64toh(hwdb->head->child_entry_size); + base += idx * le64toh(hwdb->head->value_entry_size); return (const struct trie_value_entry_f *)base; } @@ -129,7 +134,7 @@ static const struct trie_node_f *node_lookup_f(sd_hwdb *hwdb, const struct trie_ struct trie_child_entry_f search; search.c = c; - child = bsearch(&search, trie_node_children(hwdb, node), node->children_count, + child = bsearch(&search, (const char *)node + le64toh(hwdb->head->node_size), node->children_count, le64toh(hwdb->head->child_entry_size), trie_children_cmp_f); if (child) return trie_node_from_off(hwdb, child->child_off); @@ -177,7 +182,7 @@ static int trie_fnmatch_f(sd_hwdb *hwdb, const struct trie_node_f *node, size_t linebuf_add(buf, prefix + p, len); for (i = 0; i < node->children_count; i++) { - const struct trie_child_entry_f *child = &trie_node_children(hwdb, node)[i]; + const struct trie_child_entry_f *child = trie_node_child(hwdb, node, i); linebuf_add_char(buf, child->c); err = trie_fnmatch_f(hwdb, trie_node_from_off(hwdb, child->child_off), 0, buf, search); @@ -188,8 +193,8 @@ static int trie_fnmatch_f(sd_hwdb *hwdb, const struct trie_node_f *node, size_t if (le64toh(node->values_count) && fnmatch(linebuf_get(buf), search, 0) == 0) for (i = 0; i < le64toh(node->values_count); i++) { - err = hwdb_add_property(hwdb, trie_string(hwdb, trie_node_values(hwdb, node)[i].key_off), - trie_string(hwdb, trie_node_values(hwdb, node)[i].value_off)); + err = hwdb_add_property(hwdb, trie_string(hwdb, trie_node_value(hwdb, node, i)->key_off), + trie_string(hwdb, trie_node_value(hwdb, node, i)->value_off)); if (err < 0) return err; } @@ -254,8 +259,8 @@ static int trie_search_f(sd_hwdb *hwdb, const char *search) { size_t n; for (n = 0; n < le64toh(node->values_count); n++) { - err = hwdb_add_property(hwdb, trie_string(hwdb, trie_node_values(hwdb, node)[n].key_off), - trie_string(hwdb, trie_node_values(hwdb, node)[n].value_off)); + err = hwdb_add_property(hwdb, trie_string(hwdb, trie_node_value(hwdb, node, n)->key_off), + trie_string(hwdb, trie_node_value(hwdb, node, n)->value_off)); if (err < 0) return err; } -- cgit v1.2.3-54-g00ecf From 698c5a176ead078e7c86c541be714ccb464dae95 Mon Sep 17 00:00:00 2001 From: David Herrmann Date: Wed, 21 Sep 2016 14:22:49 +0200 Subject: hwdb: store file-name and file-number with properties Extend the hwdb to store the source file-name and file-number for each property. We simply extend the stored value struct with the new information. It is fully backwards compatible and old readers will continue to work. The libudev/sd-hwdb reader is updated in a followup. Signed-off-by: David Herrmann --- src/hwdb/hwdb.c | 56 +++++++++++++++++++++++++--------- src/libsystemd/sd-hwdb/hwdb-internal.h | 8 +++++ 2 files changed, 50 insertions(+), 14 deletions(-) (limited to 'src') diff --git a/src/hwdb/hwdb.c b/src/hwdb/hwdb.c index e12cd93d1c..be4ef5f9e9 100644 --- a/src/hwdb/hwdb.c +++ b/src/hwdb/hwdb.c @@ -85,6 +85,8 @@ struct trie_child_entry { struct trie_value_entry { size_t key_off; size_t value_off; + size_t filename_off; + size_t line_number; }; static int trie_children_cmp(const void *v1, const void *v2) { @@ -157,14 +159,19 @@ static int trie_values_cmp(const void *v1, const void *v2, void *arg) { } static int trie_node_add_value(struct trie *trie, struct trie_node *node, - const char *key, const char *value) { - ssize_t k, v; + const char *key, const char *value, + const char *filename, size_t line_number) { + ssize_t k, v, fn; struct trie_value_entry *val; + int r; k = strbuf_add_string(trie->strings, key, strlen(key)); if (k < 0) return k; v = strbuf_add_string(trie->strings, value, strlen(value)); + if (v < 0) + return v; + fn = strbuf_add_string(trie->strings, filename, strlen(filename)); if (v < 0) return v; @@ -176,8 +183,20 @@ static int trie_node_add_value(struct trie *trie, struct trie_node *node, val = xbsearch_r(&search, node->values, node->values_count, sizeof(struct trie_value_entry), trie_values_cmp, trie); if (val) { + /* + * At this point we have 2 identical properties on the same match-string. We + * strictly order them by filename+line-number, since we know the dynamic + * runtime lookup does the same for multiple matching nodes. + */ + r = strcmp(filename, trie->strings->buf + val->filename_off); + if (r < 0 || + (r == 0 && line_number < val->line_number)) + return 0; + /* replace existing earlier key with new value */ val->value_off = v; + val->filename_off = fn; + val->line_number = line_number; return 0; } } @@ -190,13 +209,16 @@ static int trie_node_add_value(struct trie *trie, struct trie_node *node, node->values = val; node->values[node->values_count].key_off = k; node->values[node->values_count].value_off = v; + node->values[node->values_count].filename_off = fn; + node->values[node->values_count].line_number = line_number; node->values_count++; qsort_r(node->values, node->values_count, sizeof(struct trie_value_entry), trie_values_cmp, trie); return 0; } static int trie_insert(struct trie *trie, struct trie_node *node, const char *search, - const char *key, const char *value) { + const char *key, const char *value, + const char *filename, uint64_t line_number) { size_t i = 0; int err = 0; @@ -250,7 +272,7 @@ static int trie_insert(struct trie *trie, struct trie_node *node, const char *se c = search[i]; if (c == '\0') - return trie_node_add_value(trie, node, key, value); + return trie_node_add_value(trie, node, key, value, filename, line_number); child = node_lookup(node, c); if (!child) { @@ -274,7 +296,7 @@ static int trie_insert(struct trie *trie, struct trie_node *node, const char *se return err; } - return trie_node_add_value(trie, child, key, value); + return trie_node_add_value(trie, child, key, value, filename, line_number); } node = child; @@ -303,7 +325,7 @@ static void trie_store_nodes_size(struct trie_f *trie, struct trie_node *node) { for (i = 0; i < node->children_count; i++) trie->strings_off += sizeof(struct trie_child_entry_f); for (i = 0; i < node->values_count; i++) - trie->strings_off += sizeof(struct trie_value_entry_f); + trie->strings_off += sizeof(struct trie_value_entry2_f); } static int64_t trie_store_nodes(struct trie_f *trie, struct trie_node *node) { @@ -349,12 +371,14 @@ static int64_t trie_store_nodes(struct trie_f *trie, struct trie_node *node) { /* append values array */ for (i = 0; i < node->values_count; i++) { - struct trie_value_entry_f v = { + struct trie_value_entry2_f v = { .key_off = htole64(trie->strings_off + node->values[i].key_off), .value_off = htole64(trie->strings_off + node->values[i].value_off), + .filename_off = htole64(trie->strings_off + node->values[i].filename_off), + .line_number = htole64(node->values[i].line_number), }; - fwrite(&v, sizeof(struct trie_value_entry_f), 1, trie->f); + fwrite(&v, sizeof(struct trie_value_entry2_f), 1, trie->f); trie->values_count++; } @@ -375,7 +399,7 @@ static int trie_store(struct trie *trie, const char *filename) { .header_size = htole64(sizeof(struct trie_header_f)), .node_size = htole64(sizeof(struct trie_node_f)), .child_entry_size = htole64(sizeof(struct trie_child_entry_f)), - .value_entry_size = htole64(sizeof(struct trie_value_entry_f)), + .value_entry_size = htole64(sizeof(struct trie_value_entry2_f)), }; int err; @@ -431,14 +455,15 @@ static int trie_store(struct trie *trie, const char *filename) { log_debug("child pointers: %8"PRIu64" bytes (%8"PRIu64")", t.children_count * sizeof(struct trie_child_entry_f), t.children_count); log_debug("value pointers: %8"PRIu64" bytes (%8"PRIu64")", - t.values_count * sizeof(struct trie_value_entry_f), t.values_count); + t.values_count * sizeof(struct trie_value_entry2_f), t.values_count); log_debug("string store: %8zu bytes", trie->strings->len); log_debug("strings start: %8"PRIu64, t.strings_off); return 0; } -static int insert_data(struct trie *trie, char **match_list, char *line, const char *filename) { +static int insert_data(struct trie *trie, char **match_list, char *line, + const char *filename, size_t line_number) { char *value, **entry; value = strchr(line, '='); @@ -460,7 +485,7 @@ static int insert_data(struct trie *trie, char **match_list, char *line, const c } STRV_FOREACH(entry, match_list) - trie_insert(trie, trie->root, *entry, line, value); + trie_insert(trie, trie->root, *entry, line, value, filename, line_number); return 0; } @@ -474,6 +499,7 @@ static int import_file(struct trie *trie, const char *filename) { _cleanup_fclose_ FILE *f = NULL; char line[LINE_MAX]; _cleanup_strv_free_ char **match_list = NULL; + size_t line_number = 0; char *match = NULL; int r; @@ -485,6 +511,8 @@ static int import_file(struct trie *trie, const char *filename) { size_t len; char *pos; + ++line_number; + /* comment line */ if (line[0] == '#') continue; @@ -546,7 +574,7 @@ static int import_file(struct trie *trie, const char *filename) { /* first data */ state = HW_DATA; - insert_data(trie, match_list, line, filename); + insert_data(trie, match_list, line, filename, line_number); break; case HW_DATA: @@ -564,7 +592,7 @@ static int import_file(struct trie *trie, const char *filename) { break; } - insert_data(trie, match_list, line, filename); + insert_data(trie, match_list, line, filename, line_number); break; }; } diff --git a/src/libsystemd/sd-hwdb/hwdb-internal.h b/src/libsystemd/sd-hwdb/hwdb-internal.h index 8ffb5e5c74..4fff94ec76 100644 --- a/src/libsystemd/sd-hwdb/hwdb-internal.h +++ b/src/libsystemd/sd-hwdb/hwdb-internal.h @@ -70,3 +70,11 @@ struct trie_value_entry_f { le64_t key_off; le64_t value_off; } _packed_; + +/* v2 extends v1 with filename and line-number */ +struct trie_value_entry2_f { + le64_t key_off; + le64_t value_off; + le64_t filename_off; + le64_t line_number; +} _packed_; -- cgit v1.2.3-54-g00ecf From 3a04b789c6f17dff2000a3cdbeaaf86baa604524 Mon Sep 17 00:00:00 2001 From: David Herrmann Date: Wed, 21 Sep 2016 15:16:00 +0200 Subject: sd-hwdb: order properties by origin If we find duplicates in a property-lookup, make sure to order them by their origin. That is, matches defined "later" take precedence over earlier matches. The "later"-order is defined by file-name + line-number combination. That is, if a match is defined below another one in the same hwdb file, it takes precedence, same as if it is defined in a file ordered after another one. Signed-off-by: David Herrmann --- src/libsystemd/sd-hwdb/sd-hwdb.c | 43 ++++++++++++++++++++++++++-------------- 1 file changed, 28 insertions(+), 15 deletions(-) (limited to 'src') diff --git a/src/libsystemd/sd-hwdb/sd-hwdb.c b/src/libsystemd/sd-hwdb/sd-hwdb.c index fb9522959f..488e101ea8 100644 --- a/src/libsystemd/sd-hwdb/sd-hwdb.c +++ b/src/libsystemd/sd-hwdb/sd-hwdb.c @@ -141,12 +141,13 @@ static const struct trie_node_f *node_lookup_f(sd_hwdb *hwdb, const struct trie_ return NULL; } -static int hwdb_add_property(sd_hwdb *hwdb, const char *key, const char *value) { +static int hwdb_add_property(sd_hwdb *hwdb, const struct trie_value_entry_f *entry) { + const char *key; int r; assert(hwdb); - assert(key); - assert(value); + + key = trie_string(hwdb, entry->key_off); /* * Silently ignore all properties which do not start with a @@ -157,11 +158,25 @@ static int hwdb_add_property(sd_hwdb *hwdb, const char *key, const char *value) key++; + if (le64toh(hwdb->head->value_entry_size) >= sizeof(struct trie_value_entry2_f)) { + const struct trie_value_entry2_f *old, *entry2; + + entry2 = (const struct trie_value_entry2_f *)entry; + old = ordered_hashmap_get(hwdb->properties, key); + if (old) { + /* on duplicates, we order by filename and line-number */ + r = strcmp(trie_string(hwdb, entry2->filename_off), trie_string(hwdb, old->filename_off)); + if (r < 0 || + (r == 0 && entry2->line_number < old->line_number)) + return 0; + } + } + r = ordered_hashmap_ensure_allocated(&hwdb->properties, &string_hash_ops); if (r < 0) return r; - r = ordered_hashmap_replace(hwdb->properties, key, (char*)value); + r = ordered_hashmap_replace(hwdb->properties, key, (void *)entry); if (r < 0) return r; @@ -193,8 +208,7 @@ static int trie_fnmatch_f(sd_hwdb *hwdb, const struct trie_node_f *node, size_t if (le64toh(node->values_count) && fnmatch(linebuf_get(buf), search, 0) == 0) for (i = 0; i < le64toh(node->values_count); i++) { - err = hwdb_add_property(hwdb, trie_string(hwdb, trie_node_value(hwdb, node, i)->key_off), - trie_string(hwdb, trie_node_value(hwdb, node, i)->value_off)); + err = hwdb_add_property(hwdb, trie_node_value(hwdb, node, i)); if (err < 0) return err; } @@ -259,8 +273,7 @@ static int trie_search_f(sd_hwdb *hwdb, const char *search) { size_t n; for (n = 0; n < le64toh(node->values_count); n++) { - err = hwdb_add_property(hwdb, trie_string(hwdb, trie_node_value(hwdb, node, n)->key_off), - trie_string(hwdb, trie_node_value(hwdb, node, n)->value_off)); + err = hwdb_add_property(hwdb, trie_node_value(hwdb, node, n)); if (err < 0) return err; } @@ -415,7 +428,7 @@ static int properties_prepare(sd_hwdb *hwdb, const char *modalias) { } _public_ int sd_hwdb_get(sd_hwdb *hwdb, const char *modalias, const char *key, const char **_value) { - const char *value; + const struct trie_value_entry_f *entry; int r; assert_return(hwdb, -EINVAL); @@ -427,11 +440,11 @@ _public_ int sd_hwdb_get(sd_hwdb *hwdb, const char *modalias, const char *key, c if (r < 0) return r; - value = ordered_hashmap_get(hwdb->properties, key); - if (!value) + entry = ordered_hashmap_get(hwdb->properties, key); + if (!entry) return -ENOENT; - *_value = value; + *_value = trie_string(hwdb, entry->value_off); return 0; } @@ -454,8 +467,8 @@ _public_ int sd_hwdb_seek(sd_hwdb *hwdb, const char *modalias) { } _public_ int sd_hwdb_enumerate(sd_hwdb *hwdb, const char **key, const char **value) { + const struct trie_value_entry_f *entry; const void *k; - void *v; assert_return(hwdb, -EINVAL); assert_return(key, -EINVAL); @@ -464,12 +477,12 @@ _public_ int sd_hwdb_enumerate(sd_hwdb *hwdb, const char **key, const char **val if (hwdb->properties_modified) return -EAGAIN; - ordered_hashmap_iterate(hwdb->properties, &hwdb->properties_iterator, &v, &k); + ordered_hashmap_iterate(hwdb->properties, &hwdb->properties_iterator, (void **)&entry, &k); if (!k) return 0; *key = k; - *value = v; + *value = trie_string(hwdb, entry->value_off); return 1; } -- cgit v1.2.3-54-g00ecf