bcachefs: Fix journal_keys_search() overhead

Previously, on every btree_iter_peek() operation we were searching the
journal keys, doing a full binary search - which was slow.

This patch fixes that by saving our position in the journal keys, so
that we only do a full binary search when moving our position backwards
or a large jump forwards.

Signed-off-by: Kent Overstreet <kent.overstreet@gmail.com>

5 files changed, 67 insertions, 26 deletions

diff --git a/fs/bcachefs/btree_iter.c b/fs/bcachefs/btree_iter.c
index ab116c16c036..b951fbc73f27 100644
--- a/fs/bcachefs/btree_iter.c
+++ b/fs/bcachefs/btree_iter.c
@@ -2249,14 +2249,38 @@ static inline struct bkey_i *btree_trans_peek_updates(struct btree_trans *trans,
 	return NULL;
 }
 
+struct bkey_i *bch2_btree_journal_peek(struct btree_trans *trans,
+				       struct btree_iter *iter,
+				       struct bpos start_pos,
+				       struct bpos end_pos)
+{
+	struct bkey_i *k;
+
+	if (bpos_cmp(start_pos, iter->journal_pos) < 0)
+		iter->journal_idx = 0;
+
+	k = bch2_journal_keys_peek_upto(trans->c, iter->btree_id, 0,
+					start_pos, end_pos,
+					&iter->journal_idx);
+
+	iter->journal_pos = k ? k->k.p : end_pos;
+	return k;
+}
+
+struct bkey_i *bch2_btree_journal_peek_slot(struct btree_trans *trans,
+					    struct btree_iter *iter,
+					    struct bpos pos)
+{
+	return bch2_btree_journal_peek(trans, iter, pos, pos);
+}
+
 static noinline
 struct bkey_s_c btree_trans_peek_journal(struct btree_trans *trans,
 					 struct btree_iter *iter,
 					 struct bkey_s_c k)
 {
 	struct bkey_i *next_journal =
-		bch2_journal_keys_peek_upto(trans->c, iter->btree_id, 0,
-				iter->path->pos,
+		bch2_btree_journal_peek(trans, iter, iter->path->pos,
 				k.k ? k.k->p : iter->path->l[0].b->key.k.p);
 
 	if (next_journal) {
@@ -2805,10 +2829,8 @@ struct bkey_s_c bch2_btree_iter_peek_slot(struct btree_iter *iter)
 		}
 
 		if (unlikely(iter->flags & BTREE_ITER_WITH_JOURNAL) &&
-		    (next_update = bch2_journal_keys_peek_slot(trans->c,
-					iter->btree_id,
-					iter->path->level,
-					iter->pos))) {
+		    (next_update = bch2_btree_journal_peek_slot(trans,
+					iter, iter->pos))) {
 			iter->k = next_update->k;
 			k = bkey_i_to_s_c(next_update);
 			goto out;
@@ -3075,6 +3097,8 @@ static void __bch2_trans_iter_init(struct btree_trans *trans,
 	iter->k.type	= KEY_TYPE_deleted;
 	iter->k.p	= pos;
 	iter->k.size	= 0;
+	iter->journal_idx = 0;
+	iter->journal_pos = POS_MIN;
 #ifdef CONFIG_BCACHEFS_DEBUG
 	iter->ip_allocated = ip;
 #endif
diff --git a/fs/bcachefs/btree_iter.h b/fs/bcachefs/btree_iter.h
index dad05ea00357..f2b302c8150c 100644
--- a/fs/bcachefs/btree_iter.h
+++ b/fs/bcachefs/btree_iter.h
@@ -138,6 +138,9 @@ struct btree_path *bch2_path_get(struct btree_trans *, enum btree_id, struct bpo
 				 unsigned, unsigned, unsigned, unsigned long);
 inline struct bkey_s_c bch2_btree_path_peek_slot(struct btree_path *, struct bkey *);
 
+struct bkey_i *bch2_btree_journal_peek_slot(struct btree_trans *,
+					struct btree_iter *, struct bpos);
+
 #ifdef CONFIG_BCACHEFS_DEBUG
 void bch2_trans_verify_paths(struct btree_trans *);
 void bch2_trans_verify_locks(struct btree_trans *);
diff --git a/fs/bcachefs/btree_types.h b/fs/bcachefs/btree_types.h
index e4ed46a4f870..73fe02587fd5 100644
--- a/fs/bcachefs/btree_types.h
+++ b/fs/bcachefs/btree_types.h
@@ -292,6 +292,10 @@ struct btree_iter {
 	 * bch2_btree_iter_next_slot() can correctly advance pos.
 	 */
 	struct bkey		k;
+
+	/* BTREE_ITER_WITH_JOURNAL: */
+	size_t			journal_idx;
+	struct bpos		journal_pos;
 #ifdef CONFIG_BCACHEFS_DEBUG
 	unsigned long		ip_allocated;
 #endif
diff --git a/fs/bcachefs/recovery.c b/fs/bcachefs/recovery.c
index e26408be7500..04afe2453b0b 100644
--- a/fs/bcachefs/recovery.c
+++ b/fs/bcachefs/recovery.c
@@ -86,9 +86,9 @@ static inline struct journal_key *idx_to_key(struct journal_keys *keys, size_t i
 	return keys->d + idx_to_pos(keys, idx);
 }
 
-size_t bch2_journal_key_search(struct journal_keys *keys,
-			       enum btree_id id, unsigned level,
-			       struct bpos pos)
+static size_t bch2_journal_key_search(struct journal_keys *keys,
+				      enum btree_id id, unsigned level,
+				      struct bpos pos)
 {
 	size_t l = 0, r = keys->nr, m;
 
@@ -111,21 +111,31 @@ size_t bch2_journal_key_search(struct journal_keys *keys,
 
 struct bkey_i *bch2_journal_keys_peek_upto(struct bch_fs *c, enum btree_id btree_id,
 					   unsigned level, struct bpos pos,
-					   struct bpos end_pos)
+					   struct bpos end_pos, size_t *idx)
 {
 	struct journal_keys *keys = &c->journal_keys;
-	size_t idx = bch2_journal_key_search(keys, btree_id, level, pos);
-
-	while (idx < keys->size &&
-	       keys->d[idx].btree_id == btree_id &&
-	       keys->d[idx].level == level &&
-	       bpos_cmp(keys->d[idx].k->k.p, end_pos) <= 0) {
-		if (!keys->d[idx].overwritten)
-			return keys->d[idx].k;
-
-		idx++;
-		if (idx == keys->gap)
-			idx += keys->size - keys->nr;
+	unsigned iters = 0;
+search:
+	if (!*idx)
+		*idx = bch2_journal_key_search(keys, btree_id, level, pos);
+
+	while (*idx < keys->size &&
+	       keys->d[*idx].btree_id == btree_id &&
+	       keys->d[*idx].level == level &&
+	       bpos_cmp(keys->d[*idx].k->k.p, end_pos) <= 0) {
+		if (bpos_cmp(keys->d[*idx].k->k.p, pos) >= 0 &&
+		    !keys->d[*idx].overwritten)
+			return keys->d[*idx].k;
+
+		(*idx)++;
+		if (*idx == keys->gap)
+			*idx += keys->size - keys->nr;
+
+		iters++;
+		if (iters == 10) {
+			*idx = 0;
+			goto search;
+		}
 	}
 
 	return NULL;
@@ -134,7 +144,9 @@ struct bkey_i *bch2_journal_keys_peek_upto(struct bch_fs *c, enum btree_id btree
 struct bkey_i *bch2_journal_keys_peek_slot(struct bch_fs *c, enum btree_id btree_id,
 					   unsigned level, struct bpos pos)
 {
-	return bch2_journal_keys_peek_upto(c, btree_id, level, pos, pos);
+	size_t idx = 0;
+
+	return bch2_journal_keys_peek_upto(c, btree_id, level, pos, pos, &idx);
 }
 
 static void journal_iters_fix(struct bch_fs *c)
diff --git a/fs/bcachefs/recovery.h b/fs/bcachefs/recovery.h
index e05aac64185d..52db06b29310 100644
--- a/fs/bcachefs/recovery.h
+++ b/fs/bcachefs/recovery.h
@@ -28,10 +28,8 @@ struct btree_and_journal_iter {
 	}			last;
 };
 
-size_t bch2_journal_key_search(struct journal_keys *, enum btree_id,
-			       unsigned, struct bpos);
 struct bkey_i *bch2_journal_keys_peek_upto(struct bch_fs *, enum btree_id,
-					   unsigned, struct bpos, struct bpos);
+				unsigned, struct bpos, struct bpos, size_t *);
 struct bkey_i *bch2_journal_keys_peek_slot(struct bch_fs *, enum btree_id,
 					   unsigned, struct bpos);