// SPDX-License-Identifier: GPL-2.0
#include "bcachefs.h"
#include "eytzinger.h"
#include "journal.h"
#include "journal_seq_blacklist.h"
#include "super-io.h"
/*
* journal_seq_blacklist machinery:
*
* To guarantee order of btree updates after a crash, we need to detect when a
* btree node entry (bset) is newer than the newest journal entry that was
* successfully written, and ignore it - effectively ignoring any btree updates
* that didn't make it into the journal.
*
* If we didn't do this, we might have two btree nodes, a and b, both with
* updates that weren't written to the journal yet: if b was updated after a,
* but b was flushed and not a - oops; on recovery we'll find that the updates
* to b happened, but not the updates to a that happened before it.
*
* Ignoring bsets that are newer than the newest journal entry is always safe,
* because everything they contain will also have been journalled - and must
* still be present in the journal on disk until a journal entry has been
* written _after_ that bset was written.
*
* To accomplish this, bsets record the newest journal sequence number they
* contain updates for; then, on startup, the btree code queries the journal
* code to ask "Is this sequence number newer than the newest journal entry? If
* so, ignore it."
*
* When this happens, we must blacklist that journal sequence number: the
* journal must not write any entries with that sequence number, and it must
* record that it was blacklisted so that a) on recovery we don't think we have
* missing journal entries and b) so that the btree code continues to ignore
* that bset, until that btree node is rewritten.
*/
static unsigned sb_blacklist_u64s(unsigned nr)
{
struct bch_sb_field_journal_seq_blacklist *bl;
return (sizeof(*bl) + sizeof(bl->start[0]) * nr) / sizeof(u64);
}
int bch2_journal_seq_blacklist_add(struct bch_fs *c, u64 start, u64 end)
{
struct bch_sb_field_journal_seq_blacklist *bl;
unsigned i = 0, nr;
int ret = 0;
mutex_lock(&c->sb_lock);
bl = bch2_sb_field_get(c->disk_sb.sb, journal_seq_blacklist);
nr = blacklist_nr_entries(bl);
while (i < nr) {
struct journal_seq_blacklist_entry *e =
bl->start + i;
if (end < le64_to_cpu(e->start))
break;
if (start > le64_to_cpu(e->end)) {
i++;
continue;
}
/*
* Entry is contiguous or overlapping with new entry: merge it
* with new entry, and delete:
*/
start = min(start, le64_to_cpu(e->start));
end = max(end, le64_to_cpu(e->end));
array_remove_item(bl->start, nr, i);
}
bl = bch2_sb_field_resize(&c->disk_sb, journal_seq_blacklist,
sb_blacklist_u64s(nr + 1));
if (!bl) {
ret = -BCH_ERR_ENOSPC_sb_journal_seq_blacklist;
goto out;
}
array_insert_item(bl->start, nr, i, ((struct journal_seq_blacklist_entry) {
.start = cpu_to_le64(start),
.end = cpu_to_le64(end),
}));
c->disk_sb.sb->features[0] |= cpu_to_le64(1ULL << BCH_FEATURE_journal_seq_blacklist_v3);
ret = bch2_write_super(c);
out:
mutex_unlock(&c->sb_lock);
return ret ?: bch2_blacklist_table_initialize(c);
}
static int journal_seq_blacklist_table_cmp(const void *_l, const void *_r)
{
const struct journal_seq_blacklist_table_entry *l = _l;
const struct journal_seq_blacklist_table_entry *r = _r;
return cmp_int(l->start, r->start);
}
bool bch2_journal_seq_is_blacklisted(struct bch_fs *c, u64 seq,
bool dirty)
{
struct journal_seq_blacklist_table *t = c->journal_seq_blacklist_table;
struct journal_seq_blacklist_table_entry search = { .start = seq };
int idx;
if (!t)
return false;
idx = eytzinger0_find_le(t->entries, t->nr,
sizeof(t->entries[0]),
journal_seq_blacklist_table_cmp,
&search);
if (idx < 0)
return false;
BUG_ON(t->entries[idx].start > seq);
if (seq >= t->entries[idx].end)
return false;
if (dirty)
t->entries[idx].dirty = true;
return true;
}
int bch2_blacklist_table_initialize(struct bch_fs *c)
{
struct bch_sb_field_journal_seq_blacklist *bl =
bch2_sb_field_get(c->disk_sb.sb, journal_seq_blacklist);
struct journal_seq_blacklist_table *t;
unsigned i, nr = blacklist_nr_entries(bl);
if (!bl)
return 0;
t = kzalloc(struct_size(t, entries, nr), GFP_KERNEL);
if (!t)
return -BCH_ERR_ENOMEM_blacklist_table_init;
t->nr = nr;
for (i = 0; i < nr; i++) {
t->entries[i].start = le64_to_cpu(bl->start[i].start);
t->entries[i].end = le64_to_cpu(bl->start[i].end);
}
eytzinger0_sort(t->entries,
t->nr,
sizeof(t->entries[0]),
journal_seq_blacklist_table_cmp,
NULL);
kfree(c->journal_seq_blacklist_table);
c->journal_seq_blacklist_table = t;
return 0;
}
static int bch2_sb_journal_seq_blacklist_validate(struct bch_sb *sb, struct bch_sb_field *f,
enum bch_validate_flags flags, struct printbuf *err)
{
struct bch_sb_field_journal_seq_blacklist *bl =
field_to_type(f, journal_seq_blacklist);
unsigned i, nr = blacklist_nr_entries(bl);
for (i = 0; i < nr; i++) {
struct journal_seq_blacklist_entry *e = bl->start + i;
if (le64_to_cpu(e->start) >=
le64_to_cpu(e->end)) {
prt_printf(err, "entry %u start >= end (%llu >= %llu)",
i, le64_to_cpu(e->start), le64_to_cpu(e->end));
return -BCH_ERR_invalid_sb_journal_seq_blacklist;
}
if (i + 1 < nr &&
le64_to_cpu(e[0].end) >
le64_to_cpu(e[1].start)) {
prt_printf(err, "entry %u out of order with next entry (%llu > %llu)",
i + 1, le64_to_cpu(e[0].end), le64_to_cpu(e[1].start));
return -BCH_ERR_invalid_sb_journal_seq_blacklist;
}
}
return 0;
}
static void bch2_sb_journal_seq_blacklist_to_text(struct printbuf *out,
struct bch_sb *sb,
struct bch_sb_field *f)
{
struct bch_sb_field_journal_seq_blacklist *bl =
field_to_type(f, journal_seq_blacklist);
struct journal_seq_blacklist_entry *i;
unsigned nr = blacklist_nr_entries(bl);
for (i = bl->start; i < bl->start + nr; i++) {
if (i != bl->start)
prt_printf(out, " ");
prt_printf(out, "%llu-%llu",
le64_to_cpu(i->start),
le64_to_cpu(i->end));
}
prt_newline(out);
}
const struct bch_sb_field_ops bch_sb_field_ops_journal_seq_blacklist = {
.validate = bch2_sb_journal_seq_blacklist_validate,
.to_text = bch2_sb_journal_seq_blacklist_to_text
};
bool bch2_blacklist_entries_gc(struct bch_fs *c)
{
struct journal_seq_blacklist_entry *src, *dst;
struct bch_sb_field_journal_seq_blacklist *bl =
bch2_sb_field_get(c->disk_sb.sb, journal_seq_blacklist);
if (!bl)
return false;
unsigned nr = blacklist_nr_entries(bl);
dst = bl->start;
struct journal_seq_blacklist_table *t = c->journal_seq_blacklist_table;
BUG_ON(nr != t->nr);
unsigned i;
for (src = bl->start, i = t->nr == 0 ? 0 : eytzinger0_first(t->nr);
src < bl->start + nr;
src++, i = eytzinger0_next(i, nr)) {
BUG_ON(t->entries[i].start != le64_to_cpu(src->start));
BUG_ON(t->entries[i].end != le64_to_cpu(src->end));
if (t->entries[i].dirty || t->entries[i].end >= c->journal.oldest_seq_found_ondisk)
*dst++ = *src;
}
unsigned new_nr = dst - bl->start;
if (new_nr == nr)
return false;
bch_verbose(c, "nr blacklist entries was %u, now %u", nr, new_nr);
bl = bch2_sb_field_resize(&c->disk_sb, journal_seq_blacklist,
new_nr ? sb_blacklist_u64s(new_nr) : 0);
BUG_ON(new_nr && !bl);
return true;
}
Codebase Browser
linux