From 369f0589218a874a88bc69c5481d8f90f987b7dd Mon Sep 17 00:00:00 2001 From: Lennart Poettering Date: Tue, 21 Aug 2012 15:32:51 +0200 Subject: [PATCH] verify: optimize entry search a bit by using bisection --- src/journal/journal-verify.c | 34 +++++++++++++++++++++++++++++----- 1 file changed, 29 insertions(+), 5 deletions(-) diff --git a/src/journal/journal-verify.c b/src/journal/journal-verify.c index 8604b6e7c..90739a66c 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); } -- 2.30.2