journal: optimize iteration: skip files that cannot improve current candidate entry

Suppose that while iterating we have already looked into a journal file
and got a candidate for the next entry. And we are considering to look
into another journal file because it may contain an entry that is nearer
to the current location than the candidate.

We should skip the whole journal file if we can tell by looking at its
header that none of its entries can precede the candidate.

Before:
$ time ./journalctl --since=2014-06-01 --until=2014-07-01 > /dev/null

real    0m20.518s
user    0m19.989s
sys     0m0.328s

After:
$ time ./journalctl --since=2014-06-01 --until=2014-07-01 > /dev/null

real    0m9.445s
user    0m9.228s
sys     0m0.213s

1 files changed, 24 insertions, 0 deletions

diff --git a/src/journal/sd-journal.c b/src/journal/sd-journal.c
index b937daf5e4..5e2da99126 100644
--- a/src/journal/sd-journal.c
+++ b/src/journal/sd-journal.c
@@ -517,6 +517,27 @@ static bool whole_file_precedes_location(JournalFile *f, Location *l, direction_
         return false;
 }
 
+static bool file_may_have_preceding_entry(JournalFile *f, JournalFile *of, uint64_t op, direction_t direction) {
+        Object *o;
+        int r;
+
+        assert(f);
+        assert(of);
+
+        r = journal_file_move_to_object(of, OBJECT_ENTRY, op, &o);
+        if (r < 0)
+                return true;
+
+        if (sd_id128_equal(f->header->seqnum_id, of->header->seqnum_id))
+                return direction == DIRECTION_DOWN ?
+                        le64toh(o->entry.seqnum) >= le64toh(f->header->head_entry_seqnum) :
+                        le64toh(o->entry.seqnum) <= le64toh(f->header->tail_entry_seqnum);
+
+        return direction == DIRECTION_DOWN ?
+                le64toh(o->entry.realtime) >= le64toh(f->header->head_entry_realtime) :
+                le64toh(o->entry.realtime) <= le64toh(f->header->tail_entry_realtime);
+}
+
 _pure_ static int compare_with_location(JournalFile *af, Object *ao, Location *l) {
         uint64_t a;
 
@@ -905,6 +926,9 @@ static int real_journal_next(sd_journal *j, direction_t direction) {
                 if (whole_file_precedes_location(f, &j->current_location, direction))
                         continue;
 
+                if (new_file && !file_may_have_preceding_entry(f, new_file, new_offset, direction))
+                        continue;
+
                 r = next_beyond_location(j, f, direction, &o, &p);
                 if (r < 0) {
                         log_debug_errno(r, "Can't iterate through %s, ignoring: %m", f->path);