fs/bcachefs/journal_seq_blacklist.c - linux - Git at Google

 // 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;
 }
	// 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;
	}