Merge pull request #4199 from dvdhrm/hwdb-order

hwdb: return conflicts in a well-defined order

3 files changed, 88 insertions, 34 deletions

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,9 +159,11 @@ 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)
@@ -167,6 +171,9 @@ static int trie_node_add_value(struct trie *trie, struct trie_node *node,
         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;
 
         if (node->values_count) {
                 struct trie_value_entry search = {
@@ -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_;
diff --git a/src/libsystemd/sd-hwdb/sd-hwdb.c b/src/libsystemd/sd-hwdb/sd-hwdb.c
index 062fa97b17..488e101ea8 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,19 +134,20 @@ 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);
         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
@@ -152,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;
 
@@ -177,7 +197,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 +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_values(hwdb, node)[i].key_off),
-                                                trie_string(hwdb, trie_node_values(hwdb, node)[i].value_off));
+                        err = hwdb_add_property(hwdb, trie_node_value(hwdb, node, i));
                         if (err < 0)
                                 return err;
                 }
@@ -254,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_values(hwdb, node)[n].key_off),
-                                                        trie_string(hwdb, trie_node_values(hwdb, node)[n].value_off));
+                                err = hwdb_add_property(hwdb, trie_node_value(hwdb, node, n));
                                 if (err < 0)
                                         return err;
                         }
@@ -410,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);
@@ -422,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;
 }
@@ -449,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);
@@ -459,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;
 }