hwdb, sd-hwdb: rework priority comparison when loading properties

We cannot compare filenames directly, because paths are not sortable
lexicographically, e.g. /etc/udev is "later" (has higher priority)
than /usr/lib/udev.

The on-disk format is changed to have a separate field for "file priority",
which is stored when writing the binary file, and then loaded and used in
comparisons. For data in the previous format (as generated by systemd 232),
this information is not available, and we use a trick where the offset into the
string table is used as a proxy for priority. Most of the time strings are
stored in the order in which the files were processed. This is not entirely
reliable, but is good enough to properly order /usr/lib and /etc/, which are
the two most common cases. This hack is included because it allows proper
parsing of files until the binary hwdb is regenerated.

Instead of adding a new field, I reduced the size of line_number from 64 to 32
bits, and added a 16 bit priority field, and 16 bits of padding. Adding a new
field of 16 bytes would significantly screw up alignment and increase file
size, and line number realistically don't need more than ~20 bits.

Fixes #4750.

3 files changed, 53 insertions, 18 deletions

diff --git a/src/hwdb/hwdb.c b/src/hwdb/hwdb.c
index af31578e11..41f74ad133 100644
--- a/src/hwdb/hwdb.c
+++ b/src/hwdb/hwdb.c
@@ -86,7 +86,8 @@ struct trie_value_entry {
         size_t key_off;
         size_t value_off;
         size_t filename_off;
-        size_t line_number;
+        uint32_t line_number;
+        uint16_t file_priority;
 };
 
 static int trie_children_cmp(const void *v1, const void *v2) {
@@ -160,7 +161,7 @@ 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,
-                               const char *filename, size_t line_number) {
+                               const char *filename, uint16_t file_priority, uint32_t line_number) {
         ssize_t k, v, fn;
         struct trie_value_entry *val;
 
@@ -187,6 +188,7 @@ static int trie_node_add_value(struct trie *trie, struct trie_node *node,
                          */
                         val->value_off = v;
                         val->filename_off = fn;
+                        val->file_priority = file_priority;
                         val->line_number = line_number;
                         return 0;
                 }
@@ -201,6 +203,7 @@ static int trie_node_add_value(struct trie *trie, struct trie_node *node,
         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].file_priority = file_priority;
         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);
@@ -209,7 +212,7 @@ static int trie_node_add_value(struct trie *trie, struct trie_node *node,
 
 static int trie_insert(struct trie *trie, struct trie_node *node, const char *search,
                        const char *key, const char *value,
-                       const char *filename, uint64_t line_number) {
+                       const char *filename, uint16_t file_priority, uint32_t line_number) {
         size_t i = 0;
         int err = 0;
 
@@ -263,7 +266,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, filename, line_number);
+                        return trie_node_add_value(trie, node, key, value, filename, file_priority, line_number);
 
                 child = node_lookup(node, c);
                 if (!child) {
@@ -287,7 +290,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, filename, line_number);
+                        return trie_node_add_value(trie, child, key, value, filename, file_priority, line_number);
                 }
 
                 node = child;
@@ -366,7 +369,8 @@ static int64_t trie_store_nodes(struct trie_f *trie, struct trie_node *node) {
                         .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),
+                        .line_number = htole32(node->values[i].line_number),
+                        .file_priority = htole16(node->values[i].file_priority),
                 };
 
                 fwrite(&v, sizeof(struct trie_value_entry2_f), 1, trie->f);
@@ -454,7 +458,7 @@ static int trie_store(struct trie *trie, const char *filename) {
 }
 
 static int insert_data(struct trie *trie, char **match_list, char *line,
-                       const char *filename, size_t line_number) {
+                       const char *filename, uint16_t file_priority, uint32_t line_number) {
         char *value, **entry;
 
         value = strchr(line, '=');
@@ -476,12 +480,12 @@ static int insert_data(struct trie *trie, char **match_list, char *line,
         }
 
         STRV_FOREACH(entry, match_list)
-                trie_insert(trie, trie->root, *entry, line, value, filename, line_number);
+                trie_insert(trie, trie->root, *entry, line, value, filename, file_priority, line_number);
 
         return 0;
 }
 
-static int import_file(struct trie *trie, const char *filename) {
+static int import_file(struct trie *trie, const char *filename, uint16_t file_priority) {
         enum {
                 HW_NONE,
                 HW_MATCH,
@@ -490,7 +494,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;
+        uint32_t line_number = 0;
         char *match = NULL;
         int r;
 
@@ -565,7 +569,7 @@ static int import_file(struct trie *trie, const char *filename) {
 
                         /* first data */
                         state = HW_DATA;
-                        insert_data(trie, match_list, line, filename, line_number);
+                        insert_data(trie, match_list, line, filename, file_priority, line_number);
                         break;
 
                 case HW_DATA:
@@ -583,7 +587,7 @@ static int import_file(struct trie *trie, const char *filename) {
                                 break;
                         }
 
-                        insert_data(trie, match_list, line, filename, line_number);
+                        insert_data(trie, match_list, line, filename, file_priority, line_number);
                         break;
                 };
         }
@@ -616,6 +620,7 @@ static int hwdb_update(int argc, char *argv[], void *userdata) {
         _cleanup_free_ char *hwdb_bin = NULL;
         _cleanup_(trie_freep) struct trie *trie = NULL;
         char **files, **f;
+        uint16_t file_priority = 1;
         int r;
 
         trie = new0(struct trie, 1);
@@ -640,7 +645,7 @@ static int hwdb_update(int argc, char *argv[], void *userdata) {
 
         STRV_FOREACH(f, files) {
                 log_debug("reading file '%s'", *f);
-                import_file(trie, *f);
+                import_file(trie, *f, file_priority++);
         }
         strv_free(files);
 
diff --git a/src/libsystemd/sd-hwdb/hwdb-internal.h b/src/libsystemd/sd-hwdb/hwdb-internal.h
index 4fff94ec76..2f4934ae8b 100644
--- a/src/libsystemd/sd-hwdb/hwdb-internal.h
+++ b/src/libsystemd/sd-hwdb/hwdb-internal.h
@@ -76,5 +76,7 @@ struct trie_value_entry2_f {
         le64_t key_off;
         le64_t value_off;
         le64_t filename_off;
-        le64_t line_number;
+        le32_t line_number;
+        le16_t file_priority;
+        le16_t padding;
 } _packed_;
diff --git a/src/libsystemd/sd-hwdb/sd-hwdb.c b/src/libsystemd/sd-hwdb/sd-hwdb.c
index 811a60f0c3..a8c6376302 100644
--- a/src/libsystemd/sd-hwdb/sd-hwdb.c
+++ b/src/libsystemd/sd-hwdb/sd-hwdb.c
@@ -164,10 +164,38 @@ static int hwdb_add_property(sd_hwdb *hwdb, const struct trie_value_entry_f *ent
                 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))
+                        /* On duplicates, we order by filename priority and line-number.
+                         *
+                         *
+                         * v2 of the format had 64 bits for the line number.
+                         * v3 reuses top 32 bits of line_number to store the priority.
+                         * We check the top bits — if they are zero we have v2 format.
+                         * This means that v2 clients will print wrong line numbers with
+                         * v3 data.
+                         *
+                         * For v3 data: we compare the priority (of the source file)
+                         * and the line number.
+                         *
+                         * For v2 data: we rely on the fact that the filenames in the hwdb
+                         * are added in the order of priority (higher later), because they
+                         * are *processed* in the order of priority. So we compare the
+                         * indices to determine which file had higher priority. Comparing
+                         * the strings alphabetically would be useless, because those are
+                         * full paths, and e.g. /usr/lib would sort after /etc, even
+                         * though it has lower priority. This is not reliable because of
+                         * suffix compression, but should work for the most common case of
+                         * /usr/lib/udev/hwbd.d and /etc/udev/hwdb.d, and is better than
+                         * not doing the comparison at all.
+                         */
+                        bool lower;
+
+                        if (entry2->file_priority == 0)
+                                lower = entry2->filename_off < old->filename_off ||
+                                        (entry2->filename_off == old->filename_off && entry2->line_number < old->line_number);
+                        else
+                                lower = entry2->file_priority < old->file_priority ||
+                                        (entry2->file_priority == old->file_priority && entry2->line_number < old->line_number);
+                        if (lower)
                                 return 0;
                 }
         }