bcache: bkey_prev() -> bkey_prev_all()

And add a bkey_prev() that skips deleted keys

4 files changed, 54 insertions, 22 deletions

diff --git a/drivers/md/bcache/bset.c b/drivers/md/bcache/bset.c
index 88ce99ee2e02..84cf9bfa9b0e 100644
--- a/drivers/md/bcache/bset.c
+++ b/drivers/md/bcache/bset.c
@@ -180,7 +180,7 @@ void bch_verify_key_order(struct btree_keys *b,
 	struct bkey_packed *k, *prev;
 	struct bkey uk, uw = bkey_unpack_key(f, where);
 
-	k = bkey_prev(t, where);
+	k = bkey_prev_all(t, where);
 	BUG_ON(k &&
 	       keys_out_of_order(f, k, where, b->ops->is_extents));
 
@@ -196,11 +196,13 @@ void bch_verify_key_order(struct btree_keys *b,
 		    where < bset_bkey_last(t->data))
 			continue;
 
-		k = bch_btree_node_iter_bset_pos(iter, b, t->data) ?:
-			bkey_prev(t, bset_bkey_last(t->data));
+		k = bch_btree_node_iter_bset_pos(iter, b, t->data);
+
+		if (k == bset_bkey_last(t->data))
+			k = bkey_prev_all(t, k);
 
 		while (bkey_cmp_left_packed(f, k, bkey_start_pos(&uw)) > 0 &&
-		       (prev = bkey_prev(t, k)))
+		       (prev = bkey_prev_all(t, k)))
 			k = prev;
 
 		for (;
@@ -785,7 +787,7 @@ retry:
 }
 EXPORT_SYMBOL(bch_bset_build_written_tree);
 
-struct bkey_packed *bkey_prev(struct bset_tree *t, struct bkey_packed *k)
+static struct bkey_packed *__bkey_prev(struct bset_tree *t, struct bkey_packed *k)
 {
 	struct bkey_packed *p;
 	int j;
@@ -809,12 +811,43 @@ struct bkey_packed *bkey_prev(struct bset_tree *t, struct bkey_packed *k)
 			: table_to_bkey(t, j);
 	} while (p == k);
 
+	return p;
+}
+
+struct bkey_packed *bkey_prev_all(struct bset_tree *t, struct bkey_packed *k)
+{
+	struct bkey_packed *p;
+
+	p = __bkey_prev(t, k);
+	if (!p)
+		return NULL;
+
 	while (bkey_next(p) != k)
 		p = bkey_next(p);
 
 	return p;
 }
 
+struct bkey_packed *bkey_prev(struct bset_tree *t, struct bkey_packed *k)
+{
+	while (1) {
+		struct bkey_packed *p, *i, *ret = NULL;
+
+		p = __bkey_prev(t, k);
+		if (!p)
+			return NULL;
+
+		for (i = p; i != k; i = bkey_next(i))
+			if (!bkey_deleted(i))
+				ret = i;
+
+		if (ret)
+			return ret;
+
+		k = p;
+	}
+}
+
 /* Insert */
 
 /**
@@ -961,8 +994,7 @@ struct bkey_packed *bch_bset_insert(struct btree_keys *b,
 	struct bkey_format *f = &b->format;
 	struct bset_tree *t = bset_tree_last(b);
 	struct bset *i = t->data;
-	struct bkey_packed *where = bch_btree_node_iter_bset_pos(iter, b, i) ?:
-		bset_bkey_last(i);
+	struct bkey_packed *where = bch_btree_node_iter_bset_pos(iter, b, i);
 	struct bkey_packed packed, *src = bkey_to_packed(insert);
 
 	BUG_ON(bset_has_aux_tree(t));
@@ -1212,7 +1244,7 @@ static struct bkey_packed *bch_bset_search(struct btree_keys *b,
 			m = bkey_next(m);
 
 	if (IS_ENABLED(CONFIG_BCACHE_DEBUG)) {
-		struct bkey_packed *prev = bkey_prev(t, m);
+		struct bkey_packed *prev = bkey_prev_all(t, m);
 
 		BUG_ON(prev &&
 		       btree_iter_pos_cmp_p_or_unp(f, search, packed_search,
@@ -1399,7 +1431,7 @@ struct bkey_packed *bch_btree_node_iter_bset_pos(struct btree_node_iter *iter,
 		if (set->end == end)
 			return __btree_node_offset_to_key(b, set->k);
 
-	return NULL;
+	return bset_bkey_last(i);
 }
 
 static inline void btree_node_iter_sift(struct btree_node_iter *iter,
@@ -1489,7 +1521,7 @@ struct bkey_packed *bch_btree_node_iter_prev_all(struct btree_node_iter *iter,
 		k = bset_bkey_last(t->data);
 		i = NULL;
 found:
-		k = bkey_prev(t, k);
+		k = bkey_prev_all(t, k);
 
 		if (k &&
 		    (!prev ||
diff --git a/drivers/md/bcache/bset.h b/drivers/md/bcache/bset.h
index 8208c05eadd8..b93e64f608c3 100644
--- a/drivers/md/bcache/bset.h
+++ b/drivers/md/bcache/bset.h
@@ -383,6 +383,7 @@ static inline struct bkey_packed *bset_bkey_idx(struct bset *i, unsigned idx)
 }
 
 struct bset_tree *bch_bkey_to_bset(struct btree_keys *, struct bkey_packed *);
+struct bkey_packed *bkey_prev_all(struct bset_tree *, struct bkey_packed *);
 struct bkey_packed *bkey_prev(struct bset_tree *, struct bkey_packed *);
 
 /*
diff --git a/drivers/md/bcache/btree_iter.c b/drivers/md/bcache/btree_iter.c
index 74bc00cb3b5a..ae072d7351e8 100644
--- a/drivers/md/bcache/btree_iter.c
+++ b/drivers/md/bcache/btree_iter.c
@@ -204,17 +204,15 @@ static void __bch_btree_iter_verify(struct btree_node_iter *iter,
 	bch_btree_node_iter_verify(iter, &b->keys);
 
 	for (t = b->keys.set; t <= b->keys.set + b->keys.nsets; t++) {
-		k = bkey_prev(t,
-			bch_btree_node_iter_bset_pos(iter, &b->keys, t->data) ?:
-			bset_bkey_last(t->data));
+		k = bch_btree_node_iter_bset_pos(iter, &b->keys, t->data);
 
 		/*
 		 * For interior nodes, the iterator will have skipped past
 		 * deleted keys:
 		 */
-		if (b->level)
-			while (k && bkey_deleted(k))
-				k = bkey_prev(t, k);
+		k = b->level
+			? bkey_prev(t, k)
+			: bkey_prev_all(t, k);
 
 		BUG_ON(k && btree_iter_pos_cmp_packed(f, pos, k,
 						      strictly_greater));
diff --git a/drivers/md/bcache/extents.c b/drivers/md/bcache/extents.c
index 90f3a0fff788..2a4c79dd5769 100644
--- a/drivers/md/bcache/extents.c
+++ b/drivers/md/bcache/extents.c
@@ -1105,12 +1105,11 @@ static void extent_do_insert(struct btree_iter *iter, struct bkey_i *insert,
 	struct bset_tree *t = bset_tree_last(b);
 	struct bset *i = t->data;
 	struct bkey_packed *prev, *where =
-		bch_btree_node_iter_bset_pos(node_iter, b, i) ?:
-		bset_bkey_last(i);
+		bch_btree_node_iter_bset_pos(node_iter, b, i);
 
 	bch_btree_journal_key(iter, insert, res);
 
-	if ((prev = bkey_prev(t, where)) &&
+	if ((prev = bkey_prev_all(t, where)) &&
 	    bch_extent_merge_inline(iter, prev, bkey_to_packed(insert), true))
 		return;
 
@@ -2219,8 +2218,10 @@ do_fixup:
 		 * if we don't find this bset in the iterator we already got to
 		 * the end of that bset, so start searching from the end.
 		 */
-		k = bch_btree_node_iter_bset_pos(node_iter, b, t->data) ?:
-			bkey_prev(t, bset_bkey_last(t->data));
+		k = bch_btree_node_iter_bset_pos(node_iter, b, t->data);
+
+		if (k == bset_bkey_last(t->data))
+			k = bkey_prev_all(t, k);
 
 		if (back_merge) {
 			/*
@@ -2232,7 +2233,7 @@ do_fixup:
 			     k &&
 			     (uk = bkey_unpack_key(f, k),
 			      bkey_cmp(uk.p, bkey_start_pos(m)) > 0);
-			     k = bkey_prev(t, k)) {
+			     k = bkey_prev_all(t, k)) {
 				if (bkey_cmp(uk.p, m->p) >= 0)
 					continue;