bcachefs: improve btree_node_iter_prev()

2 files changed, 66 insertions, 46 deletions

diff --git a/fs/bcachefs/bset.c b/fs/bcachefs/bset.c
index 75e79bc0a471..5c77787214c7 100644
--- a/fs/bcachefs/bset.c
+++ b/fs/bcachefs/bset.c
@@ -1685,67 +1685,66 @@ static inline unsigned __btree_node_iter_used(struct btree_node_iter *iter)
 /*
  * Expensive:
  */
-struct bkey_packed *bch2_btree_node_iter_prev_all(struct btree_node_iter *iter,
-						  struct btree *b)
+struct bkey_packed *bch2_btree_node_iter_prev_filter(struct btree_node_iter *iter,
+						     struct btree *b,
+						     unsigned min_key_type)
 {
 	struct bkey_packed *k, *prev = NULL;
+	struct bkey_packed *orig_pos = bch2_btree_node_iter_peek_all(iter, b);
 	struct btree_node_iter_set *set;
 	struct bset_tree *t;
-	struct bset_tree *prev_t;
-	unsigned end, used;
+	unsigned end;
 
 	bch2_btree_node_iter_verify(iter, b);
 
 	for_each_bset(b, t) {
-		k = bch2_bkey_prev_all(b, t,
-			bch2_btree_node_iter_bset_pos(iter, b, t));
+		k = bch2_bkey_prev_filter(b, t,
+			bch2_btree_node_iter_bset_pos(iter, b, t),
+			min_key_type);
 		if (k &&
 		    (!prev || __btree_node_iter_cmp(iter->is_extents, b,
 						    k, prev) > 0)) {
 			prev = k;
-			prev_t = t;
+			end = t->end_offset;
 		}
 	}
 
 	if (!prev)
-		return NULL;
+		goto out;
 
 	/*
 	 * We're manually memmoving instead of just calling sort() to ensure the
 	 * prev we picked ends up in slot 0 - sort won't necessarily put it
 	 * there because of duplicate deleted keys:
 	 */
-	end = __btree_node_key_to_offset(b, btree_bkey_last(b, prev_t));
 	btree_node_iter_for_each(iter, set)
-		if (set->end == end) {
-			memmove(&iter->data[1],
-				&iter->data[0],
-				(void *) set - (void *) &iter->data[0]);
-			goto out;
-		}
+		if (set->end == end)
+			goto found;
 
-	used = __btree_node_iter_used(iter);
-	BUG_ON(used >= ARRAY_SIZE(iter->data));
+	BUG_ON(set != &iter->data[__btree_node_iter_used(iter)]);
+found:
+	BUG_ON(set >= iter->data + ARRAY_SIZE(iter->data));
 
 	memmove(&iter->data[1],
 		&iter->data[0],
-		(void *) &iter->data[used] - (void *) &iter->data[0]);
-out:
+		(void *) set - (void *) &iter->data[0]);
+
 	iter->data[0].k = __btree_node_key_to_offset(b, prev);
 	iter->data[0].end = end;
-	return prev;
-}
+out:
+	if (IS_ENABLED(CONFIG_BCACHEFS_DEBUG)) {
+		struct btree_node_iter iter2 = *iter;
 
-struct bkey_packed *bch2_btree_node_iter_prev(struct btree_node_iter *iter,
-					      struct btree *b)
-{
-	struct bkey_packed *k;
+		if (prev)
+			bch2_btree_node_iter_advance(&iter2, b);
 
-	do {
-		k = bch2_btree_node_iter_prev_all(iter, b);
-	} while (k && bkey_deleted(k));
+		while ((k = bch2_btree_node_iter_peek_all(&iter2, b)) != orig_pos) {
+			BUG_ON(k->type >= min_key_type);
+			bch2_btree_node_iter_advance(&iter2, b);
+		}
+	}
 
-	return k;
+	return prev;
 }
 
 struct bkey_s_c bch2_btree_node_iter_peek_unpack(struct btree_node_iter *iter,
diff --git a/fs/bcachefs/bset.h b/fs/bcachefs/bset.h
index 2a3b1b6e0b02..5895362e0af3 100644
--- a/fs/bcachefs/bset.h
+++ b/fs/bcachefs/bset.h
@@ -482,9 +482,11 @@ static inline int __btree_node_iter_cmp(bool is_extents,
 	 * For extents, bkey_deleted() is used as a proxy for k->size == 0, so
 	 * deleted keys have to sort last.
 	 */
-	return bkey_cmp_packed(b, l, r) ?: is_extents
-		? (int) bkey_deleted(l) - (int) bkey_deleted(r)
-		: (int) bkey_deleted(r) - (int) bkey_deleted(l);
+	return bkey_cmp_packed(b, l, r)
+		?: (is_extents
+		    ? (int) bkey_deleted(l) - (int) bkey_deleted(r)
+		    : (int) bkey_deleted(r) - (int) bkey_deleted(l))
+		?: (l > r) - (l < r);
 }
 
 static inline int btree_node_iter_cmp(struct btree_node_iter *iter,
@@ -524,24 +526,33 @@ __bch2_btree_node_iter_peek_all(struct btree_node_iter *iter,
 }
 
 static inline struct bkey_packed *
+bch2_btree_node_iter_peek_filter(struct btree_node_iter *iter,
+				 struct btree *b,
+				 unsigned min_key_type)
+{
+	while (!bch2_btree_node_iter_end(iter)) {
+		struct bkey_packed *k = __bch2_btree_node_iter_peek_all(iter, b);
+
+		if (k->type >= min_key_type)
+			return k;
+
+		bch2_btree_node_iter_advance(iter, b);
+	}
+
+	return NULL;
+}
+
+static inline struct bkey_packed *
 bch2_btree_node_iter_peek_all(struct btree_node_iter *iter,
 			      struct btree *b)
 {
-	return bch2_btree_node_iter_end(iter)
-		? NULL
-		: __bch2_btree_node_iter_peek_all(iter, b);
+	return bch2_btree_node_iter_peek_filter(iter, b, 0);
 }
 
 static inline struct bkey_packed *
 bch2_btree_node_iter_peek(struct btree_node_iter *iter, struct btree *b)
 {
-	struct bkey_packed *ret;
-
-	while ((ret = bch2_btree_node_iter_peek_all(iter, b)) &&
-	       bkey_deleted(ret))
-		bch2_btree_node_iter_advance(iter, b);
-
-	return ret;
+	return bch2_btree_node_iter_peek_filter(iter, b, KEY_TYPE_DELETED + 1);
 }
 
 static inline struct bkey_packed *
@@ -555,10 +566,20 @@ bch2_btree_node_iter_next_all(struct btree_node_iter *iter, struct btree *b)
 	return ret;
 }
 
-struct bkey_packed *bch2_btree_node_iter_prev_all(struct btree_node_iter *,
-						 struct btree *);
-struct bkey_packed *bch2_btree_node_iter_prev(struct btree_node_iter *,
-					     struct btree *);
+struct bkey_packed *bch2_btree_node_iter_prev_filter(struct btree_node_iter *,
+						     struct btree *, unsigned);
+
+static inline struct bkey_packed *
+bch2_btree_node_iter_prev_all(struct btree_node_iter *iter, struct btree *b)
+{
+	return bch2_btree_node_iter_prev_filter(iter, b, 0);
+}
+
+static inline struct bkey_packed *
+bch2_btree_node_iter_prev(struct btree_node_iter *iter, struct btree *b)
+{
+	return bch2_btree_node_iter_prev_filter(iter, b, KEY_TYPE_DELETED + 1);
+}
 
 /*
  * Iterates over all _live_ keys - skipping deleted (and potentially