journal: Invert verify entry <=> data consistency checks

Previously, for each entry in a data object's entry array, we'd check
if one of that entry's entry items referred to the data object.

Instead, when verifying the main entry array, let's check if for each
entry item found by iterating the main entry array, the corresponding
data object's entry array refers to that entry.

This enables us to re-use more code from journal-file and turns out to
be roughly 10s faster when verifying my 4G laptop journal.

When verifying data objects, we still check if every entry in the data
object's entry array also exists in the main entry array so that we ensure
we're not missing any entries when iterating the main entry array.

3 files changed, 56 insertions, 90 deletions

diff --git a/src/libsystemd/sd-journal/journal-file.c b/src/libsystemd/sd-journal/journal-file.c
index efda525c3a0..36141e34f06 100644
--- a/src/libsystemd/sd-journal/journal-file.c
+++ b/src/libsystemd/sd-journal/journal-file.c
@@ -2530,6 +2530,26 @@ _pure_ static int test_object_offset(JournalFile *f, uint64_t p, uint64_t needle
                 return TEST_RIGHT;
 }
 
+int journal_file_move_to_entry_by_offset(
+                JournalFile *f,
+                uint64_t p,
+                direction_t direction,
+                Object **ret,
+                uint64_t *ret_offset) {
+
+        assert(f);
+        assert(f->header);
+
+        return generic_array_bisect(
+                        f,
+                        le64toh(f->header->entry_array_offset),
+                        le64toh(f->header->n_entries),
+                        p,
+                        test_object_offset,
+                        direction,
+                        ret, ret_offset, NULL);
+}
+
 static int test_object_seqnum(JournalFile *f, uint64_t p, uint64_t needle) {
         uint64_t sq;
         Object *o;
diff --git a/src/libsystemd/sd-journal/journal-file.h b/src/libsystemd/sd-journal/journal-file.h
index dc031439e5c..f673e05e72b 100644
--- a/src/libsystemd/sd-journal/journal-file.h
+++ b/src/libsystemd/sd-journal/journal-file.h
@@ -216,6 +216,7 @@ int journal_file_next_entry(JournalFile *f, uint64_t p, direction_t direction, O
 
 int journal_file_next_entry_for_data(JournalFile *f, Object *d, direction_t direction, Object **ret, uint64_t *ret_offset);
 
+int journal_file_move_to_entry_by_offset(JournalFile *f, uint64_t p, direction_t direction, Object **ret, uint64_t *ret_offset);
 int journal_file_move_to_entry_by_seqnum(JournalFile *f, uint64_t seqnum, direction_t direction, Object **ret, uint64_t *ret_offset);
 int journal_file_move_to_entry_by_realtime(JournalFile *f, uint64_t realtime, direction_t direction, Object **ret, uint64_t *ret_offset);
 int journal_file_move_to_entry_by_monotonic(JournalFile *f, sd_id128_t boot_id, uint64_t monotonic, direction_t direction, Object **ret, uint64_t *ret_offset);
diff --git a/src/libsystemd/sd-journal/journal-verify.c b/src/libsystemd/sd-journal/journal-verify.c
index 24d3c6b9e1c..9cdefbcf6a7 100644
--- a/src/libsystemd/sd-journal/journal-verify.c
+++ b/src/libsystemd/sd-journal/journal-verify.c
@@ -422,92 +422,6 @@ static int contains_uint64(MMapFileDescriptor *f, uint64_t n, uint64_t p) {
         return 0;
 }
 
-static int entry_points_to_data(
-                JournalFile *f,
-                MMapFileDescriptor *cache_entry_fd,
-                uint64_t n_entries,
-                uint64_t entry_p,
-                uint64_t data_p) {
-
-        int r;
-        uint64_t i, n, a;
-        Object *o;
-        bool found = false;
-
-        assert(f);
-        assert(cache_entry_fd);
-
-        if (!contains_uint64(cache_entry_fd, n_entries, entry_p)) {
-                error(data_p, "Data object references invalid entry at "OFSfmt, entry_p);
-                return -EBADMSG;
-        }
-
-        r = journal_file_move_to_object(f, OBJECT_ENTRY, entry_p, &o);
-        if (r < 0)
-                return r;
-
-        n = journal_file_entry_n_items(o);
-        for (i = 0; i < n; i++)
-                if (le64toh(o->entry.items[i].object_offset) == data_p) {
-                        found = true;
-                        break;
-                }
-
-        if (!found) {
-                error(entry_p, "Data object at "OFSfmt" not referenced by linked entry", data_p);
-                return -EBADMSG;
-        }
-
-        /* Check if this entry is also in main entry array. Since the
-         * main entry array has already been verified we can rely on
-         * its consistency. */
-
-        i = 0;
-        n = le64toh(f->header->n_entries);
-        a = le64toh(f->header->entry_array_offset);
-
-        while (i < n) {
-                uint64_t m, u;
-
-                r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, a, &o);
-                if (r < 0)
-                        return r;
-
-                m = journal_file_entry_array_n_items(o);
-                u = MIN(n - i, m);
-
-                if (entry_p <= le64toh(o->entry_array.items[u-1])) {
-                        uint64_t x, y, z;
-
-                        x = 0;
-                        y = u;
-
-                        while (x < y) {
-                                z = (x + y) / 2;
-
-                                if (le64toh(o->entry_array.items[z]) == entry_p)
-                                        return 0;
-
-                                if (x + 1 >= y)
-                                        break;
-
-                                if (entry_p < le64toh(o->entry_array.items[z]))
-                                        y = z;
-                                else
-                                        x = z;
-                        }
-
-                        error(entry_p, "Entry object doesn't exist in main entry array");
-                        return -EBADMSG;
-                }
-
-                i += u;
-                a = le64toh(o->entry_array.next_entry_array_offset);
-        }
-
-        return 0;
-}
-
 static int verify_data(
                 JournalFile *f,
                 Object *o, uint64_t p,
@@ -538,9 +452,18 @@ static int verify_data(
         assert(o->data.entry_offset);
 
         last = q = le64toh(o->data.entry_offset);
-        r = entry_points_to_data(f, cache_entry_fd, n_entries, q, p);
+        if (!contains_uint64(cache_entry_fd, n_entries, q)) {
+                error(p, "Data object references invalid entry at "OFSfmt, q);
+                return -EBADMSG;
+        }
+
+        r = journal_file_move_to_entry_by_offset(f, q, DIRECTION_DOWN, NULL, NULL);
         if (r < 0)
                 return r;
+        if (r == 0) {
+                error(q, "Entry object doesn't exist in the main entry array");
+                return -EBADMSG;
+        }
 
         i = 1;
         while (i < n) {
@@ -576,9 +499,18 @@ static int verify_data(
                         }
                         last = q;
 
-                        r = entry_points_to_data(f, cache_entry_fd, n_entries, q, p);
+                        if (!contains_uint64(cache_entry_fd, n_entries, q)) {
+                                error(p, "Data object references invalid entry at "OFSfmt, q);
+                                return -EBADMSG;
+                        }
+
+                        r = journal_file_move_to_entry_by_offset(f, q, DIRECTION_DOWN, NULL, NULL);
                         if (r < 0)
                                 return r;
+                        if (r == 0) {
+                                error(q, "Entry object doesn't exist in the main entry array");
+                                return -EBADMSG;
+                        }
 
                         /* Pointer might have moved, reposition */
                         r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, a, &o);
@@ -703,7 +635,8 @@ static int data_object_in_hash_table(JournalFile *f, uint64_t hash, uint64_t p)
 static int verify_entry(
                 JournalFile *f,
                 Object *o, uint64_t p,
-                MMapFileDescriptor *cache_data_fd, uint64_t n_data) {
+                MMapFileDescriptor *cache_data_fd, uint64_t n_data,
+                bool last) {
 
         uint64_t i, n;
         int r;
@@ -741,6 +674,18 @@ static int verify_entry(
                         error(p, "Data object missing from hash table");
                         return -EBADMSG;
                 }
+
+                r = journal_file_move_to_entry_by_offset_for_data(f, u, p, DIRECTION_DOWN, NULL, NULL);
+                if (r < 0)
+                        return r;
+
+                /* The last entry object has a very high chance of not being referenced as journal files
+                 * almost always run out of space during linking of entry items when trying to add a new
+                 * entry array so let's not error in that scenario. */
+                if (r == 0 && !last) {
+                        error(p, "Entry object not referenced by linked data object at "OFSfmt, q);
+                        return -EBADMSG;
+                }
         }
 
         return 0;
@@ -812,7 +757,7 @@ static int verify_entry_array(
                         if (r < 0)
                                 return r;
 
-                        r = verify_entry(f, o, p, cache_data_fd, n_data);
+                        r = verify_entry(f, o, p, cache_data_fd, n_data, /*last=*/ i + 1 == n);
                         if (r < 0)
                                 return r;