HALF ECHO LEARN / REFERENCE COLLECTION

v262.2

src/libsystemd/sd-journal/journal-file.c

178,971 bytesGit mode 100644Download original fileLGPL-2.1-or-later

Git blob: bed0c812a6957f446f48f2101888a46dca5a6bca

Lines 3001–4000 of 4,786

                         * b) *right == *left or *left + 1, and we are going to downwards:
                         *    In that case, the (i-1)-th object has been already tested in the previous call,
                         *    which returned TEST_LEFT. See below. So, there is no matching entry in this
                         *    array nor in the whole entry array chain. */
                        assert(i == 0 || (*right - *left <= 1 && direction == DIRECTION_DOWN));
                        return TEST_GOTO_PREVIOUS;
                }
 
                /* Otherwise, cutting the array short. So, here we limit the number of elements we will see
                 * in this array, and set the right boundary to the last possibly non-corrupted object. */
                *m = i;
                *right = i - 1;
                return TEST_RIGHT;
        }
        if (r < 0)
                return r;
 
        if (r == TEST_FOUND)
                /* There may be multiple entries that match with the needle. When the direction is down, we
                 * need to find the first matching entry, hence the right boundary can be moved, but the left
                 * one cannot. Similarly, when the direction is up, we need to find the last matching entry,
                 * hence the left boundary can be moved, but the right one cannot. */
                r = direction == DIRECTION_DOWN ? TEST_RIGHT : TEST_LEFT;
 
        if (r == TEST_RIGHT) {
                /* Currently, left --- needle --- i --- right, hence we can move the right boundary to i.  */
                if (direction == DIRECTION_DOWN)
                        *right = i;
                else {
                        if (i == 0)
                                return TEST_GOTO_PREVIOUS;
                        *right = i - 1;
                }
        } else {
                /* Currently, left --- i --- needle --- right, hence we can move the left boundary to i. */
                if (direction == DIRECTION_DOWN) {
                        /* Note, here *m is always positive, as by the assertions at the beginning, we have
                         * 0 <= *left <= i <= *right < m */
                        if (i == *m - 1)
                                return TEST_GOTO_NEXT;
 
                        *left = i + 1;
                } else
                        *left = i;
        }
 
        return r;
}
 
static int generic_array_bisect(
                JournalFile *f,
                uint64_t first,  /* The offset of the first entry array object in the chain. */
                uint64_t n,      /* The total number of elements in the chain of the entry array. */
                uint64_t needle, /* The target value (e.g. seqnum, monotonic, realtime, ...). */
                int (*test_object)(JournalFile *f,
                                   uint64_t p, /* the offset of the (data or entry) object that will be tested. */
                                   uint64_t needle),
                direction_t direction,
                Object **ret_object,  /* The found object. */
                uint64_t *ret_offset, /* The offset of the found object. */
                uint64_t *ret_idx) {  /* The index of the found object counted from the beginning of the entry array chain. */
 
        /* Given an entry array chain, this function finds the object "closest" to the given needle in the
         * chain, taking into account the provided direction. A function can be provided to determine how
         * an object is matched against the given needle.
         *
         * Given a journal file, the offset of an object and the needle, the test_object() function should
         * return TEST_RIGHT if the needle is located earlier in the entry array chain, TEST_LEFT if the
         * needle is located later in the entry array chain, and TEST_FOUND if the object matches the needle.
         * If test_object() returns TEST_FOUND for a specific object, that object's information will be used
         * to populate the return values of this function. If test_object() never returns TEST_FOUND, the
         * return values are populated with the details of one of the objects closest to the needle. If the
         * direction is DIRECTION_UP, the earlier object is used. Otherwise, the later object is used.
         * If there are multiple objects that test_object() return TEST_FOUND for, then the first matching
         * object returned when direction is DIRECTION_DOWN. Otherwise the last object is returned. */
 
        uint64_t a, p, t = 0, i, last_index = UINT64_MAX;
        ChainCacheItem *ci;
        Object *array;
        int r;
 
        assert(f);
        assert(test_object);
 
        if (n <= 0)
                return 0;
 
        /* Start with the first array in the chain */
        a = first;
 
        ci = ordered_hashmap_get(f->chain_cache, &first);
        if (ci && n > ci->total && ci->begin != 0) {
                /* Ah, we have iterated this bisection array chain previously! Let's see if we can skip ahead
                 * in the chain, as far as the last time. But we can't jump backwards in the chain, so let's
                 * check that first. */
 
                r = test_object(f, ci->begin, needle);
                if (IN_SET(r, -EBADMSG, -EADDRNOTAVAIL))
                        log_debug_errno(r, "Cached entry is corrupted, ignoring: %m");
                else if (r < 0)
                        return r;
                else if (r == TEST_LEFT) {
                        /* OK, what we are looking for is right of the begin of this EntryArray, so let's
                         * jump straight to previously cached array in the chain */
 
                        a = ci->array;
                        n -= ci->total;
                        t = ci->total;
                        last_index = ci->last_index;
                }
        }
 
        while (a > 0) {
                uint64_t left, right, k, m, m_original;
 
                r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, a, &array);
                if (chain_tail_lost(f, r, a, OBJECT_ENTRY_ARRAY)) {
                        r = TEST_GOTO_PREVIOUS;
                        goto previous;
                }
                if (r < 0)
                        return r;
 
                k = journal_file_entry_array_n_items(f, array);
                m = m_original = MIN(k, n);
                if (m <= 0)
                        return 0;
 
                left = 0;
                right = m - 1;
 
                if (direction == DIRECTION_UP && left < right) {
                        /* If we're going upwards, the last entry of the previous array may pass the test,
                         * and the first entry of the current array may not pass. In that case, the last
                         * entry of the previous array must be returned. Hence, we need to test the first
                         * entry of the current array. */
                        r = generic_array_bisect_step(f, array, 0, needle, test_object, direction, &m, &left, &right);
                        if (r < 0)
                                return r;
                        if (r == TEST_GOTO_PREVIOUS)
                                goto previous;
                }
 
                /* Test the last entry of this array, to determine if we should go to the next array. */
                r = generic_array_bisect_step(f, array, right, needle, test_object, direction, &m, &left, &right);
                if (r < 0)
                        return r;
                if (r == TEST_GOTO_PREVIOUS)
                        goto previous;
 
                /* The expected entry should be in this array, (or the last entry of the previous array). */
                if (r == TEST_RIGHT) {
 
                        /* If we cached the last index we looked at, let's try to not to jump too wildly
                         * around and see if we can limit the range to look at early to the immediate
                         * neighbors of the last index we looked at. */
 
                        if (last_index > 0 && left < last_index - 1 && last_index - 1 < right) {
                                r = generic_array_bisect_step(f, array, last_index - 1, needle, test_object, direction, &m, &left, &right);
                                if (r < 0)
                                        return r;
                                if (r == TEST_GOTO_PREVIOUS)
                                        goto previous;
                        }
 
                        if (last_index < UINT64_MAX && left < last_index + 1 && last_index + 1 < right) {
                                r = generic_array_bisect_step(f, array, last_index + 1, needle, test_object, direction, &m, &left, &right);
                                if (r < 0)
                                        return r;
                                if (r == TEST_GOTO_PREVIOUS)
                                        goto previous;
                        }
 
                        for (;;) {
                                if (left == right) {
                                        /* We found one or more corrupted entries in generic_array_bisect_step().
                                         * In that case, the entry pointed by 'right' may not be tested.
                                         *
                                         * When we are going to downwards, the entry object pointed by 'left'
                                         * has not been tested yet, Hence, even if left == right, we still
                                         * have to check the final entry to see if it actually matches.
                                         *
                                         * On the other hand, when we are going to upwards, the entry pointed
                                         * by 'left' is always tested, So, it is not necessary to test the
                                         * final entry again. */
                                        if (m != m_original && direction == DIRECTION_DOWN) {
                                                r = generic_array_bisect_step(f, array, left, needle, test_object, direction, &m, &left, &right);
                                                if (r < 0)
                                                        return r;
                                                if (IN_SET(r, TEST_GOTO_PREVIOUS, TEST_GOTO_NEXT))
                                                        return 0; /* The entry does not pass the test, or is corrupted */
 
                                                assert(TEST_RIGHT);
                                                assert(left == right);
                                        }
 
                                        i = left;
                                        goto found;
                                }
 
                                assert(left < right);
                                i = (left + right + (direction == DIRECTION_UP)) / 2;
 
                                r = generic_array_bisect_step(f, array, i, needle, test_object, direction, &m, &left, &right);
                                if (r < 0)
                                        return r;
                                if (r == TEST_GOTO_PREVIOUS)
                                        goto previous;
                                if (r == TEST_GOTO_NEXT)
                                        return 0; /* Found a corrupt entry, and the array was cut short. */
                        }
                }
 
                /* Not found in this array (or the last entry of this array should be returned), go to the next array. */
                assert(r == (direction == DIRECTION_DOWN ? TEST_GOTO_NEXT : TEST_LEFT));
 
                if (k >= n) {
                        if (direction == DIRECTION_UP) {
                                assert(n > 0);
                                i = n - 1;
                                goto found;
                        }
 
                        return 0;
                }
 
                n -= k;
                t += k;
                last_index = UINT64_MAX;
                a = le64toh(array->entry_array.next_entry_array_offset);
        }
 
        return 0;
 
previous:
        /* Not found in the current array, return the last entry of the previous array. */
        assert(r == TEST_GOTO_PREVIOUS);
 
        /* The current array is the first in the chain. no previous array. */
        if (t == 0)
                return 0;
 
        /* When we are going downwards, there is no matching entries in the previous array. */
        if (direction == DIRECTION_DOWN)
                return 0;
 
        /* Get the last entry of the previous array. */
        r = bump_entry_array(f, NULL, a, first, DIRECTION_UP, &a);
        if (r <= 0)
                return r;
 
        r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, a, &array);
        if (r < 0)
                return r;
 
        p = journal_file_entry_array_n_items(f, array);
        if (p == 0 || t < p)
                return -EBADMSG;
 
        t -= p;
        i = p - 1;
 
found:
        p = journal_file_entry_array_item(f, array, 0);
        if (p <= 0)
                return -EBADMSG;
 
        /* Let's cache this item for the next invocation */
        chain_cache_put(f, ci, first, a, p, t, i);
 
        p = journal_file_entry_array_item(f, array, i);
        if (p == 0)
                return -EBADMSG;
 
        if (ret_object) {
                r = journal_file_move_to_object(f, OBJECT_ENTRY, p, ret_object);
                if (r < 0)
                        return r;
        }
 
        if (ret_offset)
                *ret_offset = p;
 
        if (ret_idx)
                *ret_idx = t + i;
 
        return 1;
}
 
static int generic_array_bisect_for_data(
                JournalFile *f,
                Object *d,
                uint64_t needle,
                int (*test_object)(JournalFile *f, uint64_t p, uint64_t needle),
                direction_t direction,
                Object **ret_object,
                uint64_t *ret_offset) {
 
        uint64_t extra, first, n;
        int r;
 
        assert(f);
        assert(d);
        assert(test_object);
 
        if (d->object.type != OBJECT_DATA)
                return -EBADMSG;
 
        n = le64toh(d->data.n_entries);
        if (n <= 0)
                return 0;
        n--; /* n_entries is the number of entries linked to the data object, including the 'extra' entry. */
 
        extra = le64toh(d->data.entry_offset);
        first = le64toh(d->data.entry_array_offset);
 
        /* This bisects the array in object 'first', but first checks an extra. */
        r = test_object(f, extra, needle);
        if (r < 0)
                return r;
 
        if (direction == DIRECTION_DOWN) {
                /* If we are going downwards, then we need to return the first object that passes the test.
                 * When there is no object that passes the test, we need to return the first object that
                 * test_object() returns TEST_RIGHT for. */
                if (IN_SET(r,
                           TEST_FOUND,  /* The 'extra' object passes the test. Hence, this is the first
                                         * object that passes the test. */
                           TEST_RIGHT)) /* The 'extra' object is the first object that test_object() returns
                                         * TEST_RIGHT for, and no object exists even in the chained arrays
                                         * that passes the test. */
                        goto use_extra; /* The 'extra' object is exactly the one we are looking for. It is
                                         * not necessary to bisect the chained arrays. */
 
                /* Otherwise, the 'extra' object is not the one we are looking for. Search in the arrays. */
 
        } else {
                /* If we are going upwards, then we need to return the last object that passes the test.
                 * When there is no object that passes the test, we need to return the last object that
                 * test_object() returns TEST_LEFT for. */
                if (r == TEST_RIGHT)
                        return 0; /* Not only the 'extra' object, but also all objects in the chained arrays
                                   * will never get TEST_FOUND or TEST_LEFT. The object we are looking for
                                   * does not exist. */
 
                /* Even if the 'extra' object passes the test, there may be multiple objects in the arrays
                 * that also pass the test. Hence, we need to bisect the arrays for finding the last matching
                 * object. */
        }
 
        r = generic_array_bisect(f, first, n, needle, test_object, direction, ret_object, ret_offset, NULL);
        if (r != 0)
                return r; /* When > 0, the found object is the first (or last, when DIRECTION_UP) object.
                           * Hence, return the found object now. */
 
        /* No matching object found in the chained arrays.
         * DIRECTION_DOWN : the 'extra' object neither matches the condition. There is no matching object.
         * DIRECTION_UP   : the 'extra' object matches the condition. So, return it. */
        if (direction == DIRECTION_DOWN)
                return 0;
 
use_extra:
        if (ret_object) {
                r = journal_file_move_to_object(f, OBJECT_ENTRY, extra, ret_object);
                if (r < 0)
                        return r;
        }
 
        if (ret_offset)
                *ret_offset = extra;
 
        return 1;
}
 
static int test_object_offset(JournalFile *f, uint64_t p, uint64_t needle) {
        assert(f);
 
        if (p <= 0)
                return -EBADMSG;
 
        if (p == needle)
                return TEST_FOUND;
        else if (p < needle)
                return TEST_LEFT;
        else
                return TEST_RIGHT;
}
 
int journal_file_move_to_entry_by_offset(
                JournalFile *f,
                uint64_t p,
                direction_t direction,
                Object **ret_object,
                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_object, ret_offset, NULL);
}
 
static int test_object_seqnum(JournalFile *f, uint64_t p, uint64_t needle) {
        uint64_t sq;
        Object *o;
        int r;
 
        assert(f);
 
        r = journal_file_move_to_object(f, OBJECT_ENTRY, p, &o);
        if (r < 0)
                return r;
 
        sq = le64toh(READ_NOW(o->entry.seqnum));
        if (sq == needle)
                return TEST_FOUND;
        else if (sq < needle)
                return TEST_LEFT;
        else
                return TEST_RIGHT;
}
 
int journal_file_move_to_entry_by_seqnum(
                JournalFile *f,
                uint64_t seqnum,
                direction_t direction,
                Object **ret_object,
                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),
                        seqnum,
                        test_object_seqnum,
                        direction,
                        ret_object, ret_offset, NULL);
}
 
static int test_object_realtime(JournalFile *f, uint64_t p, uint64_t needle) {
        Object *o;
        uint64_t rt;
        int r;
 
        assert(f);
 
        r = journal_file_move_to_object(f, OBJECT_ENTRY, p, &o);
        if (r < 0)
                return r;
 
        rt = le64toh(READ_NOW(o->entry.realtime));
        if (rt == needle)
                return TEST_FOUND;
        else if (rt < needle)
                return TEST_LEFT;
        else
                return TEST_RIGHT;
}
 
int journal_file_move_to_entry_by_realtime(
                JournalFile *f,
                uint64_t realtime,
                direction_t direction,
                Object **ret_object,
                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),
                        realtime,
                        test_object_realtime,
                        direction,
                        ret_object, ret_offset, NULL);
}
 
static int test_object_monotonic(JournalFile *f, uint64_t p, uint64_t needle) {
        Object *o;
        uint64_t m;
        int r;
 
        assert(f);
 
        r = journal_file_move_to_object(f, OBJECT_ENTRY, p, &o);
        if (r < 0)
                return r;
 
        m = le64toh(READ_NOW(o->entry.monotonic));
        if (m == needle)
                return TEST_FOUND;
        else if (m < needle)
                return TEST_LEFT;
        else
                return TEST_RIGHT;
}
 
static int find_data_object_by_boot_id(
                JournalFile *f,
                sd_id128_t boot_id,
                Object **ret_object,
                uint64_t *ret_offset) {
 
        char t[STRLEN("_BOOT_ID=") + 32 + 1] = "_BOOT_ID=";
 
        assert(f);
 
        sd_id128_to_string(boot_id, t + 9);
        return journal_file_find_data_object(f, t, sizeof(t) - 1, ret_object, 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_object,
                uint64_t *ret_offset) {
 
        Object *o;
        int r;
 
        assert(f);
 
        r = find_data_object_by_boot_id(f, boot_id, &o, NULL);
        if (r <= 0)
                return r;
 
        return generic_array_bisect_for_data(
                        f,
                        o,
                        monotonic,
                        test_object_monotonic,
                        direction,
                        ret_object, ret_offset);
}
 
void journal_file_reset_location(JournalFile *f) {
        assert(f);
 
        f->location_type = LOCATION_HEAD;
        f->current_offset = 0;
        f->current_seqnum = 0;
        f->current_realtime = 0;
        f->current_monotonic = 0;
        zero(f->current_boot_id);
        f->current_xor_hash = 0;
 
        /* Also reset the previous reading direction. Otherwise, next_beyond_location() may wrongly handle we
         * already hit EOF. See issue #29216. */
        f->last_direction = _DIRECTION_INVALID;
}
 
void journal_file_save_location(JournalFile *f, Object *o, uint64_t offset) {
        assert(f);
        assert(o);
 
        f->location_type = LOCATION_SEEK;
        f->current_offset = offset;
        f->current_seqnum = le64toh(o->entry.seqnum);
        f->current_realtime = le64toh(o->entry.realtime);
        f->current_monotonic = le64toh(o->entry.monotonic);
        f->current_boot_id = o->entry.boot_id;
        f->current_xor_hash = le64toh(o->entry.xor_hash);
}
 
static bool check_properly_ordered(uint64_t new_offset, uint64_t old_offset, direction_t direction) {
 
        /* Consider it an error if any of the two offsets is uninitialized */
        if (old_offset == 0 || new_offset == 0)
                return false;
 
        /* If we go down, the new offset must be larger than the old one. */
        return direction == DIRECTION_DOWN ?
                new_offset > old_offset  :
                new_offset < old_offset;
}
 
int journal_file_next_entry(
                JournalFile *f,
                uint64_t p,
                direction_t direction,
                Object **ret_object,
                uint64_t *ret_offset) {
 
        uint64_t i, n, q;
        Object *o;
        int r;
 
        assert(f);
        assert(f->header);
 
        /* FIXME: fix return value assignment. */
 
        n = le64toh(READ_NOW(f->header->n_entries));
        if (n <= 0)
                return 0;
 
        /* When the input offset 'p' is zero, return the first (or last on DIRECTION_UP) entry. */
        if (p == 0)
                return generic_array_get(f,
                                         le64toh(f->header->entry_array_offset),
                                         direction == DIRECTION_DOWN ? 0 : n - 1,
                                         direction,
                                         ret_object, ret_offset);
 
        /* Otherwise, first find the nearest entry object. */
        r = generic_array_bisect(f,
                                 le64toh(f->header->entry_array_offset),
                                 le64toh(f->header->n_entries),
                                 p,
                                 test_object_offset,
                                 direction,
                                 NULL, &q, &i); /* Here, do not read entry object, as the result object
                                                 * may not be the one we want, and it may be broken. */
        if (r <= 0)
                return r;
 
        assert(direction == DIRECTION_DOWN ? p <= q : q <= p);
 
        /* If the input offset 'p' points to an entry object, generic_array_bisect() should provides
         * the same offset, and the index needs to be shifted. Otherwise, use the found object as is,
         * as it is the nearest entry object from the input offset 'p'. */
 
        if (p == q) {
                r = bump_array_index(&i, direction, n);
                if (r <= 0)
                        return r;
        }
 
        /* And jump to it */
        r = generic_array_get(f, le64toh(f->header->entry_array_offset), i, direction, ret_object ? &o : NULL, &q);
        if (r <= 0)
                return r;
 
        /* Ensure our array is properly ordered. */
        if (!check_properly_ordered(q, p, direction))
                return log_debug_errno(SYNTHETIC_ERRNO(EBADMSG),
                                       "%s: entry array not properly ordered at entry index %" PRIu64,
                                       f->path, i);
 
        if (ret_object)
                *ret_object = o;
        if (ret_offset)
                *ret_offset = q;
 
        return 1;
}
 
int journal_file_move_to_entry_for_data(
                JournalFile *f,
                Object *d,
                direction_t direction,
                Object **ret_object,
                uint64_t *ret_offset) {
 
        uint64_t extra, first, n;
        int r = 0;
 
        assert(f);
        assert(d);
        assert(IN_SET(direction, DIRECTION_DOWN, DIRECTION_UP));
 
        if (d->object.type != OBJECT_DATA)
                return -EBADMSG;
 
        /* FIXME: fix return value assignment. */
 
        /* This returns the first (when the direction is down, otherwise the last) entry linked to the
         * specified data object. */
 
        n = le64toh(d->data.n_entries);
        if (n <= 0)
                return 0;
        n--; /* n_entries is the number of entries linked to the data object, including the 'extra' entry. */
 
        extra = le64toh(d->data.entry_offset);
        first = le64toh(d->data.entry_array_offset);
 
        if (direction == DIRECTION_DOWN && extra > 0) {
                /* When we are going downwards, first try to read the extra entry. */
                r = journal_file_move_to_object(f, OBJECT_ENTRY, extra, ret_object);
                if (r >= 0)
                        goto use_extra;
                if (!IN_SET(r, -EADDRNOTAVAIL, -EBADMSG))
                        return r;
        }
 
        if (n > 0) {
                /* DIRECTION_DOWN : The extra entry is broken, falling back to the entries in the array.
                 * DIRECTION_UP   : Try to find a valid entry in the array from the tail. */
                r = generic_array_get(f,
                                      first,
                                      direction == DIRECTION_DOWN ? 0 : n - 1,
                                      direction,
                                      ret_object, ret_offset);
                if (!IN_SET(r, 0, -EADDRNOTAVAIL, -EBADMSG))
                        return r; /* found or critical error. */
        }
 
        if (direction == DIRECTION_UP && extra > 0) {
                /* No valid entry exists in the chained array, falling back to the extra entry. */
                r = journal_file_move_to_object(f, OBJECT_ENTRY, extra, ret_object);
                if (r >= 0)
                        goto use_extra;
        }
 
        return r;
 
use_extra:
        if (ret_offset)
                *ret_offset = extra;
 
        return 1;
}
 
int journal_file_move_to_entry_by_offset_for_data(
                JournalFile *f,
                Object *d,
                uint64_t p,
                direction_t direction,
                Object **ret, uint64_t *ret_offset) {
 
        assert(f);
        assert(d);
 
        if (d->object.type != OBJECT_DATA)
                return -EBADMSG;
 
        return generic_array_bisect_for_data(
                        f,
                        d,
                        p,
                        test_object_offset,
                        direction,
                        ret, ret_offset);
}
 
int journal_file_move_to_entry_by_monotonic_for_data(
                JournalFile *f,
                Object *d,
                sd_id128_t boot_id,
                uint64_t monotonic,
                direction_t direction,
                Object **ret_object,
                uint64_t *ret_offset) {
 
        Object *o, *entry;
        uint64_t z;
        int r;
 
        assert(f);
        assert(d);
 
        if (d->object.type != OBJECT_DATA)
                return -EBADMSG;
 
        /* First, pin the given data object, before reading the _BOOT_ID= data object below. */
        r = journal_file_pin_object(f, d);
        if (r < 0)
                return r;
 
        /* Then, read a data object for _BOOT_ID= and seek by time. */
        r = find_data_object_by_boot_id(f, boot_id, &o, NULL);
        if (r <= 0)
                return r;
 
        r = generic_array_bisect_for_data(f,
                                          o,
                                          monotonic,
                                          test_object_monotonic,
                                          direction,
                                          NULL, &z);
        if (r <= 0)
                return r;
 
        /* And now, continue seeking until we find an entry that exists in both bisection arrays. */
        for (;;) {
                uint64_t p;
 
                /* The journal entry found by the above bisect_plus_one() may not have the specified data,
                 * that is, it may not be linked in the data object. So, we need to check that. */
 
                r = journal_file_move_to_entry_by_offset_for_data(
                                f, d, z, direction, ret_object ? &entry : NULL, &p);
                if (r <= 0)
                        return r;
                if (p == z)
                        break; /* The journal entry has the specified data. Yay! */
 
                /* If the entry does not have the data, then move to the next (or previous, depends on the
                 * 'direction') entry linked to the data object. But, the next entry may be in another boot.
                 * So, we need to check that the entry has the matching boot ID. */
 
                r = journal_file_move_to_entry_by_offset_for_data(
                                f, o, p, direction, ret_object ? &entry : NULL, &z);
                if (r <= 0)
                        return r;
                if (p == z)
                        break; /* The journal entry has the specified boot ID. Yay! */
 
                /* If not, let's try to the next entry... */
        }
 
        if (ret_object)
                *ret_object = entry;
        if (ret_offset)
                *ret_offset = z;
        return 1;
}
 
int journal_file_move_to_entry_by_seqnum_for_data(
                JournalFile *f,
                Object *d,
                uint64_t seqnum,
                direction_t direction,
                Object **ret_object,
                uint64_t *ret_offset) {
 
        assert(f);
        assert(d);
 
        if (d->object.type != OBJECT_DATA)
                return -EBADMSG;
 
        return generic_array_bisect_for_data(
                        f,
                        d,
                        seqnum,
                        test_object_seqnum,
                        direction,
                        ret_object, ret_offset);
}
 
int journal_file_move_to_entry_by_realtime_for_data(
                JournalFile *f,
                Object *d,
                uint64_t realtime,
                direction_t direction,
                Object **ret, uint64_t *ret_offset) {
 
        assert(f);
        assert(d);
 
        if (d->object.type != OBJECT_DATA)
                return -EBADMSG;
 
        return generic_array_bisect_for_data(
                        f,
                        d,
                        realtime,
                        test_object_realtime,
                        direction,
                        ret, ret_offset);
}
 
void journal_file_dump(JournalFile *f) {
        Object *o;
        uint64_t p;
        int r;
 
        assert(f);
        assert(f->header);
 
        journal_file_print_header(f);
 
        p = le64toh(READ_NOW(f->header->header_size));
        while (p != 0) {
                const char *s;
                Compression c;
 
                r = journal_file_move_to_object(f, OBJECT_UNUSED, p, &o);
                if (r < 0)
                        goto fail;
 
                s = journal_object_type_to_string(o->object.type);
 
                switch (o->object.type) {
 
                case OBJECT_ENTRY:
                        assert(s);
 
                        log_info("Type: %s seqnum=%"PRIu64" monotonic=%"PRIu64" realtime=%"PRIu64"\n",
                                 s,
                                 le64toh(o->entry.seqnum),
                                 le64toh(o->entry.monotonic),
                                 le64toh(o->entry.realtime));
                        break;
 
                case OBJECT_TAG:
                        assert(s);
 
                        log_info("Type: %s seqnum=%"PRIu64" epoch=%"PRIu64"\n",
                                 s,
                                 le64toh(o->tag.seqnum),
                                 le64toh(o->tag.epoch));
                        break;
 
                default:
                        if (s)
                                log_info("Type: %s \n", s);
                        else
                                log_info("Type: unknown (%i)", o->object.type);
                }
 
                c = COMPRESSION_FROM_OBJECT(o);
                if (c > COMPRESSION_NONE)
                        log_info("Flags: %s\n",
                                 compression_to_string(c));
 
                if (p == le64toh(f->header->tail_object_offset))
                        p = 0;
                else
                        p += ALIGN64(le64toh(o->object.size));
        }
 
        return;
fail:
        log_error("File corrupt");
}
 
/* Note: the lifetime of the compound literal is the immediately surrounding block. */
#define FORMAT_TIMESTAMP_SAFE(t) (FORMAT_TIMESTAMP(t) ?: " --- ")
 
void journal_file_print_header(JournalFile *f) {
        struct stat st;
 
        assert(f);
        assert(f->header);
 
        printf("File path: %s\n"
               "File ID: %s\n"
               "Machine ID: %s\n"
               "Boot ID: %s\n"
               "Sequential number ID: %s\n"
               "State: %s\n"
               "Compatible flags:%s%s%s%s\n"
               "Incompatible flags:%s%s%s%s%s%s\n"
               "Header size: %"PRIu64"\n"
               "Arena size: %"PRIu64"\n"
               "Data hash table size: %"PRIu64"\n"
               "Field hash table size: %"PRIu64"\n"
               "Rotate suggested: %s\n"
               "Head sequential number: %"PRIu64" (%"PRIx64")\n"
               "Tail sequential number: %"PRIu64" (%"PRIx64")\n"
               "Head realtime timestamp: %s (%"PRIx64")\n"
               "Tail realtime timestamp: %s (%"PRIx64")\n"
               "Tail monotonic timestamp: %s (%"PRIx64")\n"
               "Objects: %"PRIu64"\n"
               "Entry objects: %"PRIu64"\n",
               f->path,
               SD_ID128_TO_STRING(f->header->file_id),
               SD_ID128_TO_STRING(f->header->machine_id),
               SD_ID128_TO_STRING(f->header->tail_entry_boot_id),
               SD_ID128_TO_STRING(f->header->seqnum_id),
               f->header->state == STATE_OFFLINE ? "OFFLINE" :
               f->header->state == STATE_ONLINE ? "ONLINE" :
               f->header->state == STATE_ARCHIVED ? "ARCHIVED" : "UNKNOWN",
               JOURNAL_HEADER_SEALED(f->header) ? " SEALED" : "",
               JOURNAL_HEADER_SEALED_CONTINUOUS(f->header) ? " SEALED_CONTINUOUS" : "",
               JOURNAL_HEADER_TAIL_ENTRY_BOOT_ID(f->header) ? " TAIL_ENTRY_BOOT_ID" : "",
               (le32toh(f->header->compatible_flags) & ~HEADER_COMPATIBLE_ANY) ? " ???" : "",
               JOURNAL_HEADER_COMPRESSED_XZ(f->header) ? " COMPRESSED-XZ" : "",
               JOURNAL_HEADER_COMPRESSED_LZ4(f->header) ? " COMPRESSED-LZ4" : "",
               JOURNAL_HEADER_COMPRESSED_ZSTD(f->header) ? " COMPRESSED-ZSTD" : "",
               JOURNAL_HEADER_KEYED_HASH(f->header) ? " KEYED-HASH" : "",
               JOURNAL_HEADER_COMPACT(f->header) ? " COMPACT" : "",
               (le32toh(f->header->incompatible_flags) & ~HEADER_INCOMPATIBLE_ANY) ? " ???" : "",
               le64toh(f->header->header_size),
               le64toh(f->header->arena_size),
               le64toh(f->header->data_hash_table_size) / sizeof(HashItem),
               le64toh(f->header->field_hash_table_size) / sizeof(HashItem),
               yes_no(journal_file_rotate_suggested(f, 0, LOG_DEBUG)),
               le64toh(f->header->head_entry_seqnum), le64toh(f->header->head_entry_seqnum),
               le64toh(f->header->tail_entry_seqnum), le64toh(f->header->tail_entry_seqnum),
               FORMAT_TIMESTAMP_SAFE(le64toh(f->header->head_entry_realtime)), le64toh(f->header->head_entry_realtime),
               FORMAT_TIMESTAMP_SAFE(le64toh(f->header->tail_entry_realtime)), le64toh(f->header->tail_entry_realtime),
               FORMAT_TIMESPAN(le64toh(f->header->tail_entry_monotonic), USEC_PER_MSEC), le64toh(f->header->tail_entry_monotonic),
               le64toh(f->header->n_objects),
               le64toh(f->header->n_entries));
 
        if (JOURNAL_HEADER_CONTAINS(f->header, n_data)) {
                size_t n_data_items = le64toh(f->header->data_hash_table_size) / sizeof(HashItem);
                printf("Data objects: %"PRIu64"\n"
                       "Data hash table fill: %.1f%%\n",
                       le64toh(f->header->n_data),
                       100.0 * (double) le64toh(f->header->n_data) / (double) n_data_items);
        }