Update bcachefs sources to e02a6a521ba0 bcachefs: Faster checking for missing journal entries

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

4 files changed, 58 insertions, 15 deletions

diff --git a/.bcachefs_revision b/.bcachefs_revision
index fead5af0..dd8323f9 100644
--- a/.bcachefs_revision
+++ b/.bcachefs_revision
@@ -1 +1 @@
-48d506769bc069535664f7527de7dc439d74e40f
+e02a6a521ba07a404c589f2873fcd9cb8189c76e
diff --git a/libbcachefs/journal_io.c b/libbcachefs/journal_io.c
index 1d4c7e0a..3f06c4b2 100644
--- a/libbcachefs/journal_io.c
+++ b/libbcachefs/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/libbcachefs/journal_seq_blacklist.c b/libbcachefs/journal_seq_blacklist.c
index af4fe416..6361809b 100644
--- a/libbcachefs/journal_seq_blacklist.c
+++ b/libbcachefs/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/libbcachefs/journal_seq_blacklist.h b/libbcachefs/journal_seq_blacklist.h
index f06942cc..389b789b 100644
--- a/libbcachefs/journal_seq_blacklist.h
+++ b/libbcachefs/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);