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.

2 files changed, 35 insertions, 5 deletions

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;
                 }
         }