bcachefs: Faster checking for missing journal entries

Previously, we would do a linear search over journal entry gaps,
checking for entries that aren't actually missing beacuse the sequence
number was blacklisted.

But multi device filesystems can have massive gaps in journal entry
sequence numbers, and the linear search then becomes quite painful.

Fix this with two new helpers for iterating over the blacklist table:

  bch2_journal_seq_next_blacklisted()
  bch2_journal_seq_next_nonblacklisted()

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>

3 files changed, 57 insertions, 14 deletions

diff --git a/fs/bcachefs/journal_io.c b/fs/bcachefs/journal_io.c
index 1d4c7e0a0240..3f06c4b29552 100644
--- a/fs/bcachefs/journal_io.c
+++ b/fs/bcachefs/journal_io.c
@@ -1279,20 +1279,14 @@ struct u64_range bch2_journal_entry_missing_range(struct bch_fs *c, u64 start, u
 	if (start == end)
 		return (struct u64_range) {};
 
-	while (start < end &&
-	       bch2_journal_seq_is_blacklisted(c, start, false))
-		start++;
-
-	if (start == end)
+	start = bch2_journal_seq_next_nonblacklisted(c, start);
+	if (start >= end)
 		return (struct u64_range) {};
 
-	struct u64_range missing = { .start = start };
-
-	while (start < end &&
-	       !bch2_journal_seq_is_blacklisted(c, start, false))
-		start++;
-
-	missing.end = start - 1;
+	struct u64_range missing = {
+		.start	= start,
+		.end	= min(end, bch2_journal_seq_next_blacklisted(c, start)),
+	};
 
 	if (missing.start == missing.end)
 		return (struct u64_range) {};
@@ -1324,7 +1318,7 @@ static int bch2_journal_check_for_missing(struct bch_fs *c, u64 start_seq, u64 e
 		while ((missing = bch2_journal_entry_missing_range(c, seq, le64_to_cpu(i->j.seq))).start) {
 			printbuf_reset(&buf);
 			prt_printf(&buf, "journal entries %llu-%llu missing! (replaying %llu-%llu)",
-				   missing.start, missing.end,
+				   missing.start, missing.end - 1,
 				   start_seq, end_seq);
 
 			if (prev) {
@@ -1339,7 +1333,7 @@ static int bch2_journal_check_for_missing(struct bch_fs *c, u64 start_seq, u64 e
 
 			fsck_err(c, journal_entries_missing, "%s", buf.buf);
 
-			seq = missing.end + 1;
+			seq = missing.end;
 		}
 
 		prev = i;
diff --git a/fs/bcachefs/journal_seq_blacklist.c b/fs/bcachefs/journal_seq_blacklist.c
index af4fe416d9ec..6361809b5e2e 100644
--- a/fs/bcachefs/journal_seq_blacklist.c
+++ b/fs/bcachefs/journal_seq_blacklist.c
@@ -103,6 +103,52 @@ static int journal_seq_blacklist_table_cmp(const void *_l, const void *_r)
 	return cmp_int(l->start, r->start);
 }
 
+static int journal_seq_blacklist_table_end_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->end, r->end);
+}
+
+u64 bch2_journal_seq_next_blacklisted(struct bch_fs *c, u64 seq)
+{
+	struct journal_seq_blacklist_table *t = c->journal_seq_blacklist_table;
+
+	if (!t)
+		return U64_MAX;
+
+	struct journal_seq_blacklist_table_entry search = { .end = seq };
+	int idx = eytzinger0_find_gt(t->entries, t->nr,
+				     sizeof(t->entries[0]),
+				     journal_seq_blacklist_table_end_cmp,
+				     &search);
+	if (idx < 0)
+		return U64_MAX;
+
+	return max(seq, t->entries[idx].start);
+}
+
+u64 bch2_journal_seq_next_nonblacklisted(struct bch_fs *c, u64 seq)
+{
+	struct journal_seq_blacklist_table *t = c->journal_seq_blacklist_table;
+
+	if (!t)
+		return seq;
+
+	while (true) {
+		struct journal_seq_blacklist_table_entry search = { .start = seq };
+		int idx = eytzinger0_find_le(t->entries, t->nr,
+					     sizeof(t->entries[0]),
+					     journal_seq_blacklist_table_cmp,
+					     &search);
+		if (idx < 0 || t->entries[idx].end <= seq)
+			return seq;
+
+		seq = t->entries[idx].end;
+	}
+}
+
 bool bch2_journal_seq_is_blacklisted(struct bch_fs *c, u64 seq,
 				     bool dirty)
 {
diff --git a/fs/bcachefs/journal_seq_blacklist.h b/fs/bcachefs/journal_seq_blacklist.h
index f06942ccfcdd..389b789b26f4 100644
--- a/fs/bcachefs/journal_seq_blacklist.h
+++ b/fs/bcachefs/journal_seq_blacklist.h
@@ -11,6 +11,9 @@ blacklist_nr_entries(struct bch_sb_field_journal_seq_blacklist *bl)
 		: 0;
 }
 
+u64 bch2_journal_seq_next_blacklisted(struct bch_fs *, u64);
+u64 bch2_journal_seq_next_nonblacklisted(struct bch_fs *, u64);
+
 bool bch2_journal_seq_is_blacklisted(struct bch_fs *, u64, bool);
 u64 bch2_journal_last_blacklisted_seq(struct bch_fs *);
 int bch2_journal_seq_blacklist_add(struct bch_fs *c, u64, u64);