summaryrefslogtreecommitdiff
path: root/src/journal
diff options
context:
space:
mode:
authorLennart Poettering <lennart@poettering.net>2012-08-21 15:32:51 +0200
committerLennart Poettering <lennart@poettering.net>2012-08-21 15:32:51 +0200
commit369f0589218a874a88bc69c5481d8f90f987b7dd (patch)
treec8d6fc5a0bbc83e016f67d1d19d2bb69ea0bf5e1 /src/journal
parenta228a22fda4faa9ecb7c5a5e499980c8ae5d2a08 (diff)
verify: optimize entry search a bit by using bisection
Diffstat (limited to 'src/journal')
-rw-r--r--src/journal/journal-verify.c34
1 files changed, 29 insertions, 5 deletions
diff --git a/src/journal/journal-verify.c b/src/journal/journal-verify.c
index 8604b6e7cb..90739a66c2 100644
--- a/src/journal/journal-verify.c
+++ b/src/journal/journal-verify.c
@@ -309,22 +309,46 @@ static int entry_points_to_data(
* 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);
- i = 0;
while (i < n) {
- uint64_t m, j;
+ 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);
- for (j = 0; i < n && j < m; i++, j++)
- if (le64toh(o->entry_array.items[j]) == entry_p)
- return 0;
+ 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;
+ }
+
+ log_error("Entry object doesn't exist in main entry array at %llu", (unsigned long long) entry_p);
+ return -EBADMSG;
+ }
+ i += u;
a = le64toh(o->entry_array.next_entry_array_offset);
}