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 2001–3000 of 4,786

                int r;
 
                if (field) {
                        r = decompress_startswith_journal(compression, payload, size, &f->compress_buffer, field,
                                                  field_length, '=');
                        if (r < 0)
                                return log_debug_errno(r,
                                                       "Cannot decompress %s object of length %" PRIu64 ": %m",
                                                       compression_to_string(compression),
                                                       size);
                        if (r == 0) {
                                if (ret_data)
                                        *ret_data = NULL;
                                if (ret_size)
                                        *ret_size = 0;
                                return 0;
                        }
 
                        /* Caller only wants to check field existence, skip full decompression */
                        if (!ret_data && !ret_size)
                                return 1;
                }
 
                r = decompress_blob_journal(compression, payload, size, &f->compress_buffer, &rsize, DATA_SIZE_MAX);
                if (r < 0)
                        return r;
 
                if (ret_data)
                        *ret_data = f->compress_buffer;
                if (ret_size)
                        *ret_size = rsize;
#else
                return -EPROTONOSUPPORT;
#endif
        } else {
                if (field && (size < field_length + 1 || memcmp(payload, field, field_length) != 0 || payload[field_length] != '=')) {
                        if (ret_data)
                                *ret_data = NULL;
                        if (ret_size)
                                *ret_size = 0;
                        return 0;
                }
 
                if (ret_data)
                        *ret_data = payload;
                if (ret_size)
                        *ret_size = (size_t) size;
        }
 
        return 1;
}
 
int journal_file_data_payload(
                JournalFile *f,
                Object *o,
                uint64_t offset,
                const char *field,
                size_t field_length,
                size_t data_threshold,
                const void **ret_data,
                size_t *ret_size) {
 
        uint64_t size;
        Compression c;
        int r;
 
        assert(f);
        assert(!field == (field_length == 0)); /* These must be specified together. */
 
        if (!o) {
                r = journal_file_move_to_object(f, OBJECT_DATA, offset, &o);
                if (r < 0)
                        return r;
        }
 
        size = le64toh(READ_NOW(o->object.size));
        if (size < journal_file_data_payload_offset(f))
                return -EBADMSG;
 
        size -= journal_file_data_payload_offset(f);
 
        c = COMPRESSION_FROM_OBJECT(o);
        if (c < 0)
                return -EPROTONOSUPPORT;
 
        return maybe_decompress_payload(f, journal_file_data_payload_field(f, o), size, c, field,
                                        field_length, data_threshold, ret_data, ret_size);
}
 
uint64_t journal_file_entry_n_items(JournalFile *f, Object *o) {
        uint64_t sz;
 
        assert(f);
        assert(o);
 
        if (o->object.type != OBJECT_ENTRY)
                return 0;
 
        sz = le64toh(READ_NOW(o->object.size));
        if (sz < offsetof(Object, entry.items))
                return 0;
 
        return (sz - offsetof(Object, entry.items)) / journal_file_entry_item_size(f);
}
 
uint64_t journal_file_entry_array_n_items(JournalFile *f, Object *o) {
        uint64_t sz;
 
        assert(f);
        assert(o);
 
        if (o->object.type != OBJECT_ENTRY_ARRAY)
                return 0;
 
        sz = le64toh(READ_NOW(o->object.size));
        if (sz < offsetof(Object, entry_array.items))
                return 0;
 
        return (sz - offsetof(Object, entry_array.items)) / journal_file_entry_array_item_size(f);
}
 
uint64_t journal_file_hash_table_n_items(Object *o) {
        uint64_t sz;
 
        assert(o);
 
        if (!IN_SET(o->object.type, OBJECT_DATA_HASH_TABLE, OBJECT_FIELD_HASH_TABLE))
                return 0;
 
        sz = le64toh(READ_NOW(o->object.size));
        if (sz < offsetof(Object, hash_table.items))
                return 0;
 
        return (sz - offsetof(Object, hash_table.items)) / sizeof(HashItem);
}
 
static void write_entry_array_item(JournalFile *f, Object *o, uint64_t i, uint64_t p) {
        assert(f);
        assert(o);
 
        if (JOURNAL_HEADER_COMPACT(f->header)) {
                assert(p <= UINT32_MAX);
                o->entry_array.items.compact[i] = htole32(p);
        } else
                o->entry_array.items.regular[i] = htole64(p);
}
 
static int link_entry_into_array(
                JournalFile *f,
                le64_t *first,
                le64_t *idx,
                le32_t *tail,
                le32_t *tidx,
                uint64_t p) {
 
        uint64_t n = 0, ap = 0, q, i, a, hidx;
        Object *o;
        int r;
 
        assert(f);
        assert(f->header);
        assert(first);
        assert(idx);
        POINTER_MAY_BE_NULL(tail);
        POINTER_MAY_BE_NULL(tidx);
        assert(p > 0);
 
        a = tail ? le32toh(*tail) : le64toh(*first);
        hidx = le64toh(READ_NOW(*idx));
        i = tidx ? le32toh(READ_NOW(*tidx)) : hidx;
 
        while (a > 0) {
                r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, a, &o);
                if (r < 0)
                        return r;
 
                n = journal_file_entry_array_n_items(f, o);
                if (i < n) {
                        write_entry_array_item(f, o, i, p);
                        *idx = htole64(hidx + 1);
                        if (tidx)
                                *tidx = htole32(le32toh(*tidx) + 1);
                        return 0;
                }
 
                i -= n;
                ap = a;
                a = le64toh(o->entry_array.next_entry_array_offset);
        }
 
        if (hidx > n)
                n = (hidx+1) * 2;
        else
                n = n * 2;
 
        if (n < 4)
                n = 4;
 
        r = journal_file_append_object(f, OBJECT_ENTRY_ARRAY,
                                       offsetof(Object, entry_array.items) + n * journal_file_entry_array_item_size(f),
                                       &o, &q);
        if (r < 0)
                return r;
 
        r = journal_file_auth_put_object(f, OBJECT_ENTRY_ARRAY, o, q);
        if (r < 0)
                return r;
 
        write_entry_array_item(f, o, i, p);
 
        if (ap == 0)
                *first = htole64(q);
        else {
                r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, ap, &o);
                if (r < 0)
                        return r;
 
                o->entry_array.next_entry_array_offset = htole64(q);
        }
 
        if (tail)
                *tail = htole32(q);
 
        if (JOURNAL_HEADER_CONTAINS(f->header, n_entry_arrays))
                f->header->n_entry_arrays = htole64(le64toh(f->header->n_entry_arrays) + 1);
 
        *idx = htole64(hidx + 1);
        if (tidx)
                *tidx = htole32(1);
 
        return 0;
}
 
static int link_entry_into_array_plus_one(
                JournalFile *f,
                le64_t *extra,
                le64_t *first,
                le64_t *idx,
                le32_t *tail,
                le32_t *tidx,
                uint64_t p) {
 
        uint64_t hidx;
        int r;
 
        assert(f);
        assert(extra);
        assert(first);
        assert(idx);
        assert(p > 0);
 
        hidx = le64toh(READ_NOW(*idx));
        if (hidx == UINT64_MAX)
                return -EBADMSG;
        if (hidx == 0)
                *extra = htole64(p);
        else {
                le64_t i;
 
                i = htole64(hidx - 1);
                r = link_entry_into_array(f, first, &i, tail, tidx, p);
                if (r < 0)
                        return r;
        }
 
        *idx = htole64(hidx + 1);
        return 0;
}
 
static int journal_file_link_entry_item(JournalFile *f, uint64_t offset, uint64_t p) {
        Object *o;
        int r;
 
        assert(f);
        assert(offset > 0);
 
        r = journal_file_move_to_object(f, OBJECT_DATA, p, &o);
        if (r < 0)
                return r;
 
        return link_entry_into_array_plus_one(f,
                                              &o->data.entry_offset,
                                              &o->data.entry_array_offset,
                                              &o->data.n_entries,
                                              JOURNAL_HEADER_COMPACT(f->header) ? &o->data.compact.tail_entry_array_offset : NULL,
                                              JOURNAL_HEADER_COMPACT(f->header) ? &o->data.compact.tail_entry_array_n_entries : NULL,
                                              offset);
}
 
static int journal_file_link_entry(
                JournalFile *f,
                const Object *o,
                uint64_t offset,
                const EntryItem items[],
                size_t n_items) {
 
        int r;
 
        assert(f);
        assert(f->header);
        assert(o);
        assert(offset > 0);
 
        if (o->object.type != OBJECT_ENTRY)
                return -EBADMSG;
 
        __atomic_thread_fence(__ATOMIC_SEQ_CST);
 
        /* Link up the entry itself */
        r = link_entry_into_array(f,
                                  &f->header->entry_array_offset,
                                  &f->header->n_entries,
                                  JOURNAL_HEADER_CONTAINS(f->header, tail_entry_array_offset) ? &f->header->tail_entry_array_offset : NULL,
                                  JOURNAL_HEADER_CONTAINS(f->header, tail_entry_array_n_entries) ? &f->header->tail_entry_array_n_entries : NULL,
                                  offset);
        if (r < 0)
                return r;
 
        /* log_debug("=> %s seqnr=%"PRIu64" n_entries=%"PRIu64, f->path, o->entry.seqnum, f->header->n_entries); */
 
        if (f->header->head_entry_realtime == 0)
                f->header->head_entry_realtime = o->entry.realtime;
 
        f->header->tail_entry_realtime = o->entry.realtime;
        f->header->tail_entry_monotonic = o->entry.monotonic;
        if (JOURNAL_HEADER_CONTAINS(f->header, tail_entry_offset))
                f->header->tail_entry_offset = htole64(offset);
 
        /* Link up the items */
        for (uint64_t i = 0; i < n_items; i++) {
                int k;
 
                /* If we fail to link an entry item because we can't allocate a new entry array, don't fail
                 * immediately but try to link the other entry items since it might still be possible to link
                 * those if they don't require a new entry array to be allocated. */
 
                k = journal_file_link_entry_item(f, offset, items[i].object_offset);
                if (k == -E2BIG)
                        r = k;
                else if (k < 0)
                        return k;
        }
 
        return r;
}
 
static void write_entry_item(JournalFile *f, Object *o, uint64_t i, const EntryItem *item) {
        assert(f);
        assert(o);
        assert(item);
 
        if (JOURNAL_HEADER_COMPACT(f->header)) {
                assert(item->object_offset <= UINT32_MAX);
                o->entry.items.compact[i].object_offset = htole32(item->object_offset);
        } else {
                o->entry.items.regular[i].object_offset = htole64(item->object_offset);
                o->entry.items.regular[i].hash = htole64(item->hash);
        }
}
 
static int journal_file_append_entry_internal(
                JournalFile *f,
                const dual_timestamp *ts,
                const sd_id128_t *boot_id,
                const sd_id128_t *machine_id,
                uint64_t xor_hash,
                const EntryItem items[],
                size_t n_items,
                uint64_t *seqnum,
                sd_id128_t *seqnum_id,
                Object **ret_object,
                uint64_t *ret_offset) {
 
        uint64_t np;
        uint64_t osize;
        Object *o;
        int r;
 
        assert(f);
        assert(f->header);
        assert(ts);
        assert(boot_id);
        assert(!sd_id128_is_null(*boot_id));
        assert(items || n_items == 0);
 
        if (f->strict_order) {
                /* If requested be stricter with ordering in this journal file, to make searching via
                 * bisection fully deterministic. This is an optional feature, so that if desired journal
                 * files can be written where the ordering is not strictly enforced (in which case bisection
                 * will yield *a* result, but not the *only* result, when searching for points in
                 * time). Strict ordering mode is enabled when journald originally writes the files, but
                 * might not necessarily be if other tools (the remoting tools for example) write journal
                 * files from combined sources.
                 *
                 * Typically, if any of the errors generated here are seen journald will just rotate the
                 * journal files and start anew. */
 
                if (ts->realtime < le64toh(f->header->tail_entry_realtime))
                        return log_debug_errno(SYNTHETIC_ERRNO(EREMCHG),
                                               "Realtime timestamp %" PRIu64 " smaller than previous realtime "
                                               "timestamp %" PRIu64 ", refusing entry.",
                                               ts->realtime, le64toh(f->header->tail_entry_realtime));
 
                if (sd_id128_equal(*boot_id, f->header->tail_entry_boot_id) &&
                    ts->monotonic < le64toh(f->header->tail_entry_monotonic))
                        return log_debug_errno(
                                        SYNTHETIC_ERRNO(ENOTNAM),
                                        "Monotonic timestamp %" PRIu64
                                        " smaller than previous monotonic timestamp %" PRIu64
                                        " while having the same boot ID, refusing entry.",
                                        ts->monotonic,
                                        le64toh(f->header->tail_entry_monotonic));
        }
 
        if (seqnum_id) {
                /* Settle the passed in sequence number ID */
 
                if (sd_id128_is_null(*seqnum_id))
                        *seqnum_id = f->header->seqnum_id; /* Caller has none assigned, then copy the one from the file */
                else if (!sd_id128_equal(*seqnum_id, f->header->seqnum_id)) {
                        /* Different seqnum IDs? We can't allow entries from multiple IDs end up in the same journal. */
                        if (le64toh(f->header->n_entries) == 0)
                                f->header->seqnum_id = *seqnum_id; /* Caller has one, and file so far has no entries, then copy the one from the caller */
                        else
                                return log_debug_errno(SYNTHETIC_ERRNO(EILSEQ),
                                                       "Sequence number IDs don't match, refusing entry.");
                }
        }
 
        if (machine_id && sd_id128_is_null(f->header->machine_id))
                /* Initialize machine ID when not set yet */
                f->header->machine_id = *machine_id;
 
        osize = offsetof(Object, entry.items) + (n_items * journal_file_entry_item_size(f));
 
        r = journal_file_append_object(f, OBJECT_ENTRY, osize, &o, &np);
        if (r < 0)
                return r;
 
        o->entry.seqnum = htole64(journal_file_entry_seqnum(f, seqnum));
        o->entry.realtime = htole64(ts->realtime);
        o->entry.monotonic = htole64(ts->monotonic);
        o->entry.xor_hash = htole64(xor_hash);
        o->entry.boot_id = f->header->tail_entry_boot_id = *boot_id;
 
        for (size_t i = 0; i < n_items; i++)
                write_entry_item(f, o, i, &items[i]);
 
        r = journal_file_auth_put_object(f, OBJECT_ENTRY, o, np);
        if (r < 0)
                return r;
 
        r = journal_file_link_entry(f, o, np, items, n_items);
        if (r < 0)
                return r;
 
        if (ret_object)
                *ret_object = o;
 
        if (ret_offset)
                *ret_offset = np;
 
        return r;
}
 
void journal_file_post_change(JournalFile *f) {
        assert(f);
 
        if (f->fd < 0)
                return;
 
        /* inotify() does not receive IN_MODIFY events from file
         * accesses done via mmap(). After each access we hence
         * trigger IN_MODIFY by truncating the journal file to its
         * current size which triggers IN_MODIFY. */
 
        __atomic_thread_fence(__ATOMIC_SEQ_CST);
 
        if (ftruncate(f->fd, f->last_stat.st_size) < 0)
                log_debug_errno(errno, "Failed to truncate file to its own size: %m");
}
 
static int post_change_thunk(sd_event_source *timer, uint64_t usec, void *userdata) {
        assert(userdata);
 
        journal_file_post_change(userdata);
 
        return 1;
}
 
static void schedule_post_change(JournalFile *f) {
        sd_event *e;
        int r;
 
        assert(f);
        assert(f->post_change_timer);
 
        assert_se(e = sd_event_source_get_event(f->post_change_timer));
 
        /* If we are already going down, post the change immediately. */
        if (IN_SET(sd_event_get_state(e), SD_EVENT_EXITING, SD_EVENT_FINISHED))
                goto fail;
 
        r = sd_event_source_get_enabled(f->post_change_timer, NULL);
        if (r < 0) {
                log_debug_errno(r, "Failed to get ftruncate timer state: %m");
                goto fail;
        }
        if (r > 0)
                return;
 
        r = sd_event_source_set_time_relative(f->post_change_timer, f->post_change_timer_period);
        if (r < 0) {
                log_debug_errno(r, "Failed to set time for scheduling ftruncate: %m");
                goto fail;
        }
 
        r = sd_event_source_set_enabled(f->post_change_timer, SD_EVENT_ONESHOT);
        if (r < 0) {
                log_debug_errno(r, "Failed to enable scheduled ftruncate: %m");
                goto fail;
        }
 
        return;
 
fail:
        /* On failure, let's simply post the change immediately. */
        journal_file_post_change(f);
}
 
/* Enable coalesced change posting in a timer on the provided sd_event instance */
int journal_file_enable_post_change_timer(JournalFile *f, sd_event *e, usec_t t) {
        _cleanup_(sd_event_source_unrefp) sd_event_source *timer = NULL;
        int r;
 
        assert(f);
        assert_return(!f->post_change_timer, -EINVAL);
        assert(e);
        assert(t);
 
        /* If we are already going down, we cannot install the timer.
         * In such case, the caller needs to call journal_file_post_change() explicitly. */
        if (IN_SET(sd_event_get_state(e), SD_EVENT_EXITING, SD_EVENT_FINISHED))
                return 0;
 
        r = sd_event_add_time(e, &timer, CLOCK_MONOTONIC, 0, 0, post_change_thunk, f);
        if (r < 0)
                return r;
 
        r = sd_event_source_set_enabled(timer, SD_EVENT_OFF);
        if (r < 0)
                return r;
 
        f->post_change_timer = TAKE_PTR(timer);
        f->post_change_timer_period = t;
 
        return 1;
}
 
static int entry_item_cmp(const EntryItem *a, const EntryItem *b) {
        return CMP(ASSERT_PTR(a)->object_offset, ASSERT_PTR(b)->object_offset);
}
 
static size_t remove_duplicate_entry_items(EntryItem items[], size_t n) {
        size_t j = 1;
 
        assert(items || n == 0);
 
        if (n <= 1)
                return n;
 
        for (size_t i = 1; i < n; i++)
                if (items[i].object_offset != items[j - 1].object_offset)
                        items[j++] = items[i];
 
        return j;
}
 
int journal_file_append_entry(
                JournalFile *f,
                const dual_timestamp *ts,
                const sd_id128_t *boot_id,
                const struct iovec iovec[],
                size_t n_iovec,
                uint64_t *seqnum,
                sd_id128_t *seqnum_id,
                Object **ret_object,
                uint64_t *ret_offset) {
 
        _cleanup_free_ EntryItem *items_alloc = NULL;
        EntryItem *items;
        uint64_t xor_hash = 0;
        struct dual_timestamp _ts;
        sd_id128_t _boot_id, _machine_id, *machine_id;
        int r;
 
        assert(f);
        assert(f->header);
        assert(iovec);
        assert(n_iovec > 0);
 
        if (ts) {
                if (!VALID_REALTIME(ts->realtime))
                        return log_debug_errno(SYNTHETIC_ERRNO(EBADMSG),
                                               "Invalid realtime timestamp %" PRIu64 ", refusing entry.",
                                               ts->realtime);
                if (!VALID_MONOTONIC(ts->monotonic))
                        return log_debug_errno(SYNTHETIC_ERRNO(EBADMSG),
                                               "Invalid monotonic timestamp %" PRIu64 ", refusing entry.",
                                               ts->monotonic);
        } else {
                dual_timestamp_now(&_ts);
                ts = &_ts;
        }
 
        if (boot_id) {
                if (sd_id128_is_null(*boot_id))
                        return log_debug_errno(SYNTHETIC_ERRNO(EBADMSG), "Empty boot ID, refusing entry.");
        } else {
                r = sd_id128_get_boot(&_boot_id);
                if (r < 0)
                        return r;
 
                boot_id = &_boot_id;
        }
 
        r = sd_id128_get_machine(&_machine_id);
        if (ERRNO_IS_NEG_MACHINE_ID_UNSET(r))
                /* Gracefully handle the machine ID not being initialized yet */
                machine_id = NULL;
        else if (r < 0)
                return r;
        else
                machine_id = &_machine_id;
 
        r = journal_file_auth_append_tag_maybe(f, ts->realtime);
        if (r < 0)
                return r;
 
        if (n_iovec < ALLOCA_MAX / sizeof(EntryItem) / 2)
                items = newa(EntryItem, n_iovec);
        else {
                items_alloc = new(EntryItem, n_iovec);
                if (!items_alloc)
                        return -ENOMEM;
 
                items = items_alloc;
        }
 
        for (size_t i = 0; i < n_iovec; i++) {
                uint64_t p;
                Object *o;
 
                r = journal_file_append_data(f, iovec[i].iov_base, iovec[i].iov_len, &o, &p);
                if (r < 0)
                        return r;
 
                /* When calculating the XOR hash field, we need to take special care if the "keyed-hash"
                 * journal file flag is on. We use the XOR hash field to quickly determine the identity of a
                 * specific record, and give records with otherwise identical position (i.e. match in seqno,
                 * timestamp, …) a stable ordering. But for that we can't have it that the hash of the
                 * objects in each file is different since they are keyed. Hence let's calculate the Jenkins
                 * hash here for that. This also has the benefit that cursors for old and new journal files
                 * are completely identical (they include the XOR hash after all). For classic Jenkins-hash
                 * files things are easier, we can just take the value from the stored record directly. */
 
                if (JOURNAL_HEADER_KEYED_HASH(f->header))
                        xor_hash ^= jenkins_hash64(iovec[i].iov_base, iovec[i].iov_len);
                else
                        xor_hash ^= le64toh(o->data.hash);
 
                items[i] = (EntryItem) {
                        .object_offset = p,
                        .hash = le64toh(o->data.hash),
                };
        }
 
        /* Order by the position on disk, in order to improve seek
         * times for rotating media. */
        typesafe_qsort(items, n_iovec, entry_item_cmp);
        n_iovec = remove_duplicate_entry_items(items, n_iovec);
 
        r = journal_file_append_entry_internal(
                        f,
                        ts,
                        boot_id,
                        machine_id,
                        xor_hash,
                        items,
                        n_iovec,
                        seqnum,
                        seqnum_id,
                        ret_object,
                        ret_offset);
 
        /* If the memory mapping triggered a SIGBUS then we return an
         * IO error and ignore the error code passed down to us, since
         * it is very likely just an effect of a nullified replacement
         * mapping page */
 
        if (mmap_cache_fd_got_sigbus(f->cache_fd))
                r = -EIO;
 
        if (f->post_change_timer)
                schedule_post_change(f);
        else
                journal_file_post_change(f);
 
        return r;
}
 
typedef struct ChainCacheItem {
        uint64_t first; /* The offset of the entry array object at the beginning of the chain,
                         * i.e., le64toh(f->header->entry_array_offset), or le64toh(o->data.entry_offset). */
        uint64_t array; /* The offset of the cached entry array object. */
        uint64_t begin; /* The offset of the first item in the cached array. */
        uint64_t total; /* The total number of items in all arrays before the cached one in the chain. */
        uint64_t last_index; /* The last index we looked at in the cached array, to optimize locality when bisecting. */
} ChainCacheItem;
 
static void chain_cache_put(
                JournalFile *f,
                ChainCacheItem *ci,
                uint64_t first,
                uint64_t array,
                uint64_t begin,
                uint64_t total,
                uint64_t last_index) {
 
        assert(f);
 
        if (!ci) {
                /* If the chain item to cache for this chain is the
                 * first one it's not worth caching anything */
                if (array == first)
                        return;
 
                if (ordered_hashmap_size(f->chain_cache) >= CHAIN_CACHE_MAX) {
                        ci = ordered_hashmap_steal_first(f->chain_cache);
                        assert(ci);
                } else {
                        ci = new(ChainCacheItem, 1);
                        if (!ci)
                                return;
                }
 
                ci->first = first;
 
                if (ordered_hashmap_ensure_put(&f->chain_cache, &uint64_hash_ops_value_free, &ci->first, ci) < 0) {
                        free(ci);
                        return;
                }
        } else
                assert(ci->first == first);
 
        ci->array = array;
        ci->begin = begin;
        ci->total = total;
        ci->last_index = last_index;
}
 
static int bump_array_index(uint64_t *i, direction_t direction, uint64_t n) {
        assert(i);
 
        /* Increase or decrease the specified index, in the right direction. */
 
        if (direction == DIRECTION_DOWN) {
                if (*i >= n - 1)
                        return 0;
 
                (*i)++;
        } else {
                if (*i <= 0)
                        return 0;
 
                (*i)--;
        }
 
        return 1;
}
 
static int bump_entry_array(
                JournalFile *f,
                Object *o,       /* the current entry array object. */
                uint64_t offset, /* the offset of the entry array object. */
                uint64_t first,  /* The offset of the first entry array object in the chain. */
                direction_t direction,
                uint64_t *ret) {
 
        int r;
 
        assert(f);
        assert(ret);
 
        if (direction == DIRECTION_DOWN) {
                assert(o);
 
                if (o->object.type != OBJECT_ENTRY_ARRAY)
                        return -EBADMSG;
 
                *ret = le64toh(o->entry_array.next_entry_array_offset);
        } else {
 
                /* Entry array chains are a singly linked list, so to find the previous array in the chain, we have
                 * to start iterating from the top. */
 
                assert(offset > 0);
 
                uint64_t p = first, q = 0;
                while (p > 0 && p != offset) {
                        r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, p, &o);
                        if (r < 0)
                                return r;
 
                        q = p;
                        p = le64toh(o->entry_array.next_entry_array_offset);
                }
 
                /* If we can't find the previous entry array in the entry array chain, we're likely dealing with a
                 * corrupted journal file. */
                if (p == 0)
                        return -EBADMSG;
 
                *ret = q;
        }
 
        return *ret > 0;
}
 
static int generic_array_get(
                JournalFile *f,
                uint64_t first,         /* The offset of the first entry array object in the chain. */
                uint64_t i,             /* The index of the target object counted from the beginning of the entry array chain. */
                direction_t direction,
                Object **ret_object,    /* The found object. */
                uint64_t *ret_offset) { /* The offset of the found object. */
 
        uint64_t a, t = 0, k = 0; /* Explicit initialization of k to appease gcc */
        ChainCacheItem *ci;
        Object *o = NULL;
        int r;
 
        assert(f);
 
        /* FIXME: fix return value assignment on success. */
 
        a = first;
 
        /* Try the chain cache first */
        ci = ordered_hashmap_get(f->chain_cache, &first);
        if (ci && i > ci->total) {
                a = ci->array;
                i -= ci->total;
                t = ci->total;
        }
 
        while (a > 0) {
                r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, a, &o);
                if (IN_SET(r, -EBADMSG, -EADDRNOTAVAIL)) {
                        /* If there's corruption and we're going downwards, let's pretend we reached the
                         * final entry in the entry array chain. */
 
                        if (direction == DIRECTION_DOWN)
                                return 0;
 
                        /* If there's corruption and we're going upwards, move back to the previous entry
                         * array and start iterating entries from there. */
 
                        i = UINT64_MAX;
                        break;
                }
                if (r < 0)
                        return r;
 
                k = journal_file_entry_array_n_items(f, o);
                if (k == 0)
                        return 0;
 
                if (i < k)
                        break;
 
                /* The index is larger than the number of elements in the array. Let's move to the next array. */
                i -= k;
                t += k;
                a = le64toh(o->entry_array.next_entry_array_offset);
        }
 
        /* If we've found the right location, now look for the first non-corrupt entry object (in the right
         * direction). */
 
        while (a > 0) {
                if (i == UINT64_MAX) {
                        r = bump_entry_array(f, o, a, first, direction, &a);
                        if (r <= 0)
                                return r;
 
                        r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, a, &o);
                        if (r < 0)
                                return r;
 
                        k = journal_file_entry_array_n_items(f, o);
                        if (k == 0)
                                break;
 
                        if (direction == DIRECTION_DOWN)
                                i = 0;
                        else {
                                /* We moved to the previous array. The total must be decreased. */
                                if (t < k)
                                        return -EBADMSG; /* chain cache is broken ? */
 
                                i = k - 1;
                                t -= k;
                        }
                }
 
                do {
                        uint64_t p;
 
                        p = journal_file_entry_array_item(f, o, i);
 
                        r = journal_file_move_to_object(f, OBJECT_ENTRY, p, ret_object);
                        if (r >= 0) {
                                /* Let's cache this item for the next invocation */
                                chain_cache_put(f, ci, first, a, journal_file_entry_array_item(f, o, 0), t, i);
 
                                if (ret_offset)
                                        *ret_offset = p;
 
                                return 1;
                        }
                        if (!IN_SET(r, -EADDRNOTAVAIL, -EBADMSG))
                                return r;
 
                        /* OK, so this entry is borked. Most likely some entry didn't get synced to
                         * disk properly, let's see if the next one might work for us instead. */
                        log_debug_errno(r, "Entry item %" PRIu64 " is bad, skipping over it.", i);
 
                } while (bump_array_index(&i, direction, k) > 0);
 
                /* All entries tried in the above do-while loop are broken. Let's move to the next (or previous) array. */
 
                if (direction == DIRECTION_DOWN)
                        /* We are going to the next array, the total must be incremented. */
                        t += k;
 
                i = UINT64_MAX;
        }
 
        return 0;
}
 
enum {
        TEST_FOUND,         /* The current object passes the test. */
        TEST_LEFT,          /* The current object is in an earlier position, and the object we are looking
                             * for should exist in a later position. */
        TEST_RIGHT,         /* The current object is in a later position, and the object we are looking for
                             * should exist in an earlier position. */
        TEST_GOTO_NEXT,     /* No matching object exists in this array and earlier arrays, go to the next array. */
        TEST_GOTO_PREVIOUS, /* No matching object exists in this array and later arrays, go to the previous array. */
};
 
static int generic_array_bisect_step(
                JournalFile *f,
                Object *array,     /* entry array object */
                uint64_t i,        /* index of the entry item in the array we will test. */
                uint64_t needle,
                int (*test_object)(JournalFile *f, uint64_t p, uint64_t needle),
                direction_t direction,
                uint64_t *m,       /* The maximum number of the entries we will check in the array. */
                uint64_t *left,    /* The index of the left boundary in the array. */
                uint64_t *right) { /* The index of the right boundary in the array. */
 
        uint64_t p;
        int r;
 
        assert(f);
        assert(array);
        assert(test_object);
        assert(m);
        assert(left);
        assert(right);
        assert(*left <= i);
        assert(i <= *right);
        assert(*right < *m);
 
        p = journal_file_entry_array_item(f, array, i);
        if (p <= 0)
                r = -EBADMSG;
        else
                r = test_object(f, p, needle);
        if (IN_SET(r, -EBADMSG, -EADDRNOTAVAIL)) {
                log_debug_errno(r, "Encountered invalid entry while bisecting, cutting algorithm short.");
 
                if (i == *left) {
                        /* This happens on two situations:
                         *
                         * a) i == 0 (hence, *left == 0):
                         *    The first entry in the array is corrupted, let's go back to the previous array.
                         *