bcache: kill btree_node_iter->used

6 files changed, 190 insertions, 86 deletions

diff --git a/drivers/md/bcache/bset.c b/drivers/md/bcache/bset.c
index b76b6b9a2d3e..cae3b1f02f41 100644
--- a/drivers/md/bcache/bset.c
+++ b/drivers/md/bcache/bset.c
@@ -20,6 +20,11 @@
 #include "alloc_types.h"
 #include <trace/events/bcache.h>
 
+static inline bool btree_node_iter_set_cmp(struct btree_node_iter *,
+					   struct btree_keys *,
+					   struct btree_node_iter_set,
+					   struct btree_node_iter_set);
+
 struct bset_tree *bch_bkey_to_bset(struct btree_keys *b, struct bkey_packed *k)
 {
 	struct bset_tree *t;
@@ -162,11 +167,6 @@ static void bch_btree_node_iter_next_check(struct btree_node_iter *iter,
 	}
 }
 
-static inline bool btree_node_iter_cmp(struct btree_node_iter *,
-				       struct btree_keys *,
-				       struct btree_node_iter_set,
-				       struct btree_node_iter_set);
-
 void bch_btree_node_iter_verify(struct btree_node_iter *iter,
 				struct btree_keys *b)
 {
@@ -174,11 +174,10 @@ void bch_btree_node_iter_verify(struct btree_node_iter *iter,
 	struct bset_tree *t;
 	struct bkey_packed *k;
 
-	BUG_ON(iter->used > MAX_BSETS);
-
 	btree_node_iter_for_each(iter, set) {
-		BUG_ON(set + 1 < iter->data + iter->used &&
-		       btree_node_iter_cmp(iter, b, set[0], set[1]));
+		BUG_ON(set + 1 < iter->data + MAX_BSETS &&
+		       set[1].k != set[1].end &&
+		       btree_node_iter_set_cmp(iter, b, set[0], set[1]));
 
 		k = __btree_node_offset_to_key(b, set->k);
 		t = bch_bkey_to_bset(b, k);
@@ -1231,10 +1230,10 @@ static struct bkey_packed *bch_bset_search(struct btree_keys *b,
 
 /* Btree node iterator */
 
-static inline bool __btree_node_iter_cmp(struct btree_node_iter *iter,
-					 struct btree_keys *b,
-					 struct bkey_packed *l,
-					 struct bkey_packed *r)
+static inline bool btree_node_iter_cmp(struct btree_keys *b,
+				       bool is_extents,
+				       struct bkey_packed *l,
+				       struct bkey_packed *r)
 {
 	s64 c = bkey_cmp_packed(&b->format, l, r);
 
@@ -1247,7 +1246,7 @@ static inline bool __btree_node_iter_cmp(struct btree_node_iter *iter,
 	 * deleted keys have to sort last.
 	 */
 	return c ? c > 0
-		: iter->is_extents
+		: is_extents
 		? bkey_deleted(l) > bkey_deleted(r)
 		: bkey_deleted(l) < bkey_deleted(r);
 }
@@ -1255,21 +1254,29 @@ static inline bool __btree_node_iter_cmp(struct btree_node_iter *iter,
 /*
  * Returns true if l > r:
  */
-static inline bool btree_node_iter_cmp(struct btree_node_iter *iter,
-				       struct btree_keys *b,
-				       struct btree_node_iter_set l,
-				       struct btree_node_iter_set r)
+static inline bool btree_node_iter_set_cmp(struct btree_node_iter *iter,
+					   struct btree_keys *b,
+					   struct btree_node_iter_set l,
+					   struct btree_node_iter_set r)
 {
-	return __btree_node_iter_cmp(iter, b,
+	return btree_node_iter_cmp(b, iter->is_extents,
 			__btree_node_offset_to_key(b, l.k),
 			__btree_node_offset_to_key(b, r.k));
 }
 
+#define btree_node_iter_cmp_heap(_l, _r)				\
+	(btree_node_iter_cmp(b, (iter)->is_extents,			\
+			       __btree_node_offset_to_key(b, (_l).k),	\
+			       __btree_node_offset_to_key(b, (_r).k)))
+
 void bch_btree_node_iter_push(struct btree_node_iter *iter,
 			      struct btree_keys *b,
 			      const struct bkey_packed *k,
 			      const struct bkey_packed *end)
 {
+	EBUG_ON(iter->data[MAX_BSETS - 1].k !=
+		iter->data[MAX_BSETS - 1].end);
+
 	if (k != end) {
 		struct btree_node_iter_set *pos, n =
 			((struct btree_node_iter_set) {
@@ -1278,12 +1285,15 @@ void bch_btree_node_iter_push(struct btree_node_iter *iter,
 			 });
 
 		btree_node_iter_for_each(iter, pos)
-		     if (!btree_node_iter_cmp(iter, b, n, *pos))
+		     if (!btree_node_iter_set_cmp(iter, b, n, *pos))
 			     break;
 
-		memmove(pos + 1, pos,
-			(void *) (iter->data + iter->used) - (void *) pos);
-		iter->used++;
+		EBUG_ON(pos >= iter->data + MAX_BSETS);
+
+		memmove(&pos[1],
+			&pos[0],
+			(iter->data + MAX_BSETS - (pos + 1)) *
+			sizeof(struct btree_node_iter_set));
 		*pos = n;
 	}
 }
@@ -1387,8 +1397,6 @@ struct bkey_packed *bch_btree_node_iter_bset_pos(struct btree_node_iter *iter,
 	unsigned end = __btree_node_key_to_offset(b, bset_bkey_last(i));
 	struct btree_node_iter_set *set;
 
-	BUG_ON(iter->used > MAX_BSETS);
-
 	btree_node_iter_for_each(iter, set)
 		if (set->end == end)
 			return __btree_node_offset_to_key(b, set->k);
@@ -1402,11 +1410,10 @@ static inline void btree_node_iter_sift(struct btree_node_iter *iter,
 {
 	unsigned i;
 
-	BUG_ON(iter->used > MAX_BSETS);
-
 	for (i = start;
-	     i + 1 < iter->used &&
-	     btree_node_iter_cmp(iter, b, iter->data[i], iter->data[i + 1]);
+	     i + 1 < MAX_BSETS &&
+	     iter->data[i + 1].k != iter->data[i + 1].end &&
+	     btree_node_iter_set_cmp(iter, b, iter->data[i], iter->data[i + 1]);
 	     i++)
 		swap(iter->data[i], iter->data[i + 1]);
 }
@@ -1416,9 +1423,7 @@ void bch_btree_node_iter_sort(struct btree_node_iter *iter,
 {
 	int i;
 
-	BUG_ON(iter->used > MAX_BSETS);
-
-	for (i = iter->used - 1; i >= 0; --i)
+	for (i = MAX_BSETS - 1; i >= 0; --i)
 		btree_node_iter_sift(iter, b, i);
 }
 EXPORT_SYMBOL(bch_btree_node_iter_sort);
@@ -1436,11 +1441,16 @@ void bch_btree_node_iter_advance(struct btree_node_iter *iter,
 
 	iter->data->k += __bch_btree_node_iter_peek_all(iter, b)->u64s;
 
-	BUG_ON(iter->data->k > iter->data->end);
+	EBUG_ON(iter->data->k > iter->data->end);
 
 	if (iter->data->k == iter->data->end) {
-		BUG_ON(iter->used == 0);
-		iter->data[0] = iter->data[--iter->used];
+		struct btree_node_iter_set tmp = iter->data[0];
+
+		memmove(&iter->data[0],
+			&iter->data[1],
+			sizeof(iter->data[0]) * (MAX_BSETS - 1));
+
+		iter->data[MAX_BSETS - 1] = tmp;
 	}
 
 	btree_node_iter_sift(iter, b, 0);
@@ -1474,7 +1484,7 @@ found:
 
 		if (k &&
 		    (!prev ||
-		     __btree_node_iter_cmp(iter, b, k, prev))) {
+		     btree_node_iter_cmp(b, iter->is_extents, k, prev))) {
 			prev = k;
 			prev_set = i;
 			prev_t = t;
@@ -1507,6 +1517,49 @@ EXPORT_SYMBOL(bch_btree_node_iter_peek_unpack);
 
 /* Mergesort */
 
+void bch_btree_node_iter_large_push(struct btree_node_iter_large *iter,
+				    struct btree_keys *b,
+				    const struct bkey_packed *k,
+				    const struct bkey_packed *end)
+{
+	if (k != end) {
+		struct btree_node_iter_set n =
+			((struct btree_node_iter_set) {
+				 __btree_node_key_to_offset(b, k),
+				 __btree_node_key_to_offset(b, end)
+			 });
+
+		__heap_add(iter, n, btree_node_iter_cmp_heap);
+	}
+}
+
+void bch_btree_node_iter_large_init(struct btree_node_iter_large *iter,
+				    struct btree_keys *b)
+{
+	struct bset_tree *t;
+
+	iter->used = 0;
+
+	for (t = b->set; t <= b->set + b->nsets; t++)
+		bch_btree_node_iter_large_push(iter, b,
+					       t->data->start,
+					       bset_bkey_last(t->data));
+}
+
+void bch_btree_node_iter_large_advance(struct btree_node_iter_large *iter,
+				       struct btree_keys *b)
+{
+	iter->data->k += __btree_node_offset_to_key(b, iter->data->k)->u64s;
+
+	EBUG_ON(!iter->used);
+	EBUG_ON(iter->data->k > iter->data->end);
+
+	if (iter->data->k == iter->data->end)
+		heap_del(iter, 0, btree_node_iter_cmp_heap);
+	else
+		heap_sift(iter, 0, btree_node_iter_cmp_heap);
+}
+
 void bch_bset_sort_state_free(struct bset_sort_state *state)
 {
 	mempool_exit(&state->pool);
@@ -1528,12 +1581,12 @@ EXPORT_SYMBOL(bch_bset_sort_state_init);
 
 /* No repacking: */
 static struct btree_nr_keys btree_mergesort_simple(struct btree_keys *b,
-						   struct bset *bset,
-						   struct btree_node_iter *iter)
+					struct bset *bset,
+					struct btree_node_iter_large *iter)
 {
 	struct bkey_packed *in, *out = bset->start;
 
-	while ((in = bch_btree_node_iter_next_all(iter, b))) {
+	while ((in = bch_btree_node_iter_large_next_all(iter, b))) {
 		if (!bkey_deleted(in)) {
 			/* XXX: need better bkey_copy */
 			memcpy(out, in, bkey_bytes(in));
@@ -1549,7 +1602,7 @@ static struct btree_nr_keys btree_mergesort_simple(struct btree_keys *b,
 static struct btree_nr_keys btree_mergesort(struct btree_keys *dst,
 					    struct bset *dst_set,
 					    struct btree_keys *src,
-					    struct btree_node_iter *iter,
+					    struct btree_node_iter_large *iter,
 					    ptr_filter_fn filter)
 {
 	struct bkey_format *in_f = &src->format;
@@ -1562,7 +1615,7 @@ static struct btree_nr_keys btree_mergesort(struct btree_keys *dst,
 
 	memset(&nr, 0, sizeof(nr));
 
-	while ((in = bch_btree_node_iter_next_all(iter, src))) {
+	while ((in = bch_btree_node_iter_large_next_all(iter, src))) {
 		if (bkey_deleted(in))
 			continue;
 
@@ -1585,10 +1638,10 @@ static struct btree_nr_keys btree_mergesort(struct btree_keys *dst,
 
 /* Sort, repack, and merge extents */
 static struct btree_nr_keys btree_mergesort_extents(struct btree_keys *dst,
-						    struct bset *dst_set,
-						    struct btree_keys *src,
-						    struct btree_node_iter *iter,
-						    ptr_filter_fn filter)
+					struct bset *dst_set,
+					struct btree_keys *src,
+					struct btree_node_iter_large *iter,
+					ptr_filter_fn filter)
 {
 	struct bkey_format *in_f = &src->format;
 	struct bkey_format *out_f = &dst->format;
@@ -1600,7 +1653,7 @@ static struct btree_nr_keys btree_mergesort_extents(struct btree_keys *dst,
 
 	memset(&nr, 0, sizeof(nr));
 
-	while ((k = bch_btree_node_iter_next_all(iter, src))) {
+	while ((k = bch_btree_node_iter_large_next_all(iter, src))) {
 		if (bkey_deleted(k))
 			continue;
 
@@ -1652,22 +1705,21 @@ static struct btree_nr_keys btree_mergesort_extents(struct btree_keys *dst,
 }
 
 struct btree_nr_keys bch_sort_bsets(struct bset *dst, struct btree_keys *b,
-				    unsigned from, struct btree_node_iter *iter,
-				    btree_keys_sort_fn sort,
-				    struct bset_sort_state *state)
+			unsigned from, struct btree_node_iter_large *iter,
+			btree_keys_sort_fn sort, struct bset_sort_state *state)
 {
 	u64 start_time = local_clock();
-	struct btree_node_iter _iter;
+	struct btree_node_iter_large _iter;
 	struct btree_nr_keys nr;
 
 	if (!iter) {
 		struct bset_tree *t;
 
 		iter = &_iter;
-		__bch_btree_node_iter_init(iter, b);
+		__bch_btree_node_iter_large_init(iter, b);
 
 		for (t = b->set + from; t <= b->set + b->nsets; t++)
-			bch_btree_node_iter_push(iter, b,
+			bch_btree_node_iter_large_push(iter, b,
 						 t->data->start,
 						 bset_bkey_last(t->data));
 	}
@@ -1702,10 +1754,10 @@ void bch_btree_sort_into(struct btree_keys *dst,
 			 struct bset_sort_state *state)
 {
 	u64 start_time = local_clock();
-	struct btree_node_iter iter;
+	struct btree_node_iter_large iter;
 	struct btree_nr_keys nr;
 
-	bch_btree_node_iter_init_from_start(&iter, src);
+	bch_btree_node_iter_large_init(&iter, src);
 
 	if (!dst->ops->is_extents)
 		nr = btree_mergesort(dst, dst->set->data,
diff --git a/drivers/md/bcache/bset.h b/drivers/md/bcache/bset.h
index 46798c19e4bf..df13473506ab 100644
--- a/drivers/md/bcache/bset.h
+++ b/drivers/md/bcache/bset.h
@@ -443,7 +443,6 @@ static inline enum bch_extent_overlap bch_extent_overlap(const struct bkey *k,
 
 struct btree_node_iter {
 	u8		is_extents;
-	u16		used;
 
 	struct btree_node_iter_set {
 		u16	k, end;
@@ -453,8 +452,8 @@ struct btree_node_iter {
 static inline void __bch_btree_node_iter_init(struct btree_node_iter *iter,
 					      struct btree_keys *b)
 {
-	iter->used = 0;
 	iter->is_extents = b->ops->is_extents;
+	memset(iter->data, 0, sizeof(iter->data));
 }
 
 void bch_btree_node_iter_push(struct btree_node_iter *, struct btree_keys *,
@@ -473,12 +472,13 @@ void bch_btree_node_iter_advance(struct btree_node_iter *, struct btree_keys *);
 
 #define btree_node_iter_for_each(_iter, _set)			\
 	for (_set = (_iter)->data;				\
-	     _set < (_iter)->data + (_iter)->used;		\
+	     _set < (_iter)->data + MAX_BSETS &&		\
+	     _set->k != _set->end;				\
 	     _set++)
 
 static inline bool bch_btree_node_iter_end(struct btree_node_iter *iter)
 {
-	return !iter->used;
+	return iter->data[0].k == iter->data[0].end;
 }
 
 static inline u16
@@ -558,6 +558,55 @@ struct bkey_s_c bch_btree_node_iter_peek_unpack(struct btree_node_iter *,
 
 /* Sorting */
 
+struct btree_node_iter_large {
+	u8		is_extents;
+	u16		used;
+
+	struct btree_node_iter_set data[MAX_BSETS];
+};
+
+static inline void
+__bch_btree_node_iter_large_init(struct btree_node_iter_large *iter,
+				 struct btree_keys *b)
+{
+	iter->used = 0;
+	iter->is_extents = b->ops->is_extents;
+}
+
+void bch_btree_node_iter_large_advance(struct btree_node_iter_large *,
+				       struct btree_keys *);
+
+void bch_btree_node_iter_large_push(struct btree_node_iter_large *,
+			struct btree_keys *,
+			const struct bkey_packed *,
+			const struct bkey_packed *);
+
+static inline bool bch_btree_node_iter_large_end(struct btree_node_iter_large *iter)
+{
+	return !iter->used;
+}
+
+static inline struct bkey_packed *
+bch_btree_node_iter_large_peek_all(struct btree_node_iter_large *iter,
+				   struct btree_keys *b)
+{
+	return bch_btree_node_iter_large_end(iter)
+		? NULL
+		: __btree_node_offset_to_key(b, iter->data->k);
+}
+
+static inline struct bkey_packed *
+bch_btree_node_iter_large_next_all(struct btree_node_iter_large *iter,
+				   struct btree_keys *b)
+{
+	struct bkey_packed *ret = bch_btree_node_iter_large_peek_all(iter, b);
+
+	if (ret)
+		bch_btree_node_iter_large_advance(iter, b);
+
+	return ret;
+}
+
 struct bset_sort_state {
 	mempool_t		pool;
 
@@ -568,15 +617,14 @@ struct bset_sort_state {
 };
 
 typedef struct btree_nr_keys (*btree_keys_sort_fn)(struct btree_keys *,
-						   struct bset *,
-						   struct btree_node_iter *);
+				struct bset *, struct btree_node_iter_large *);
 
 void bch_bset_sort_state_free(struct bset_sort_state *);
 int bch_bset_sort_state_init(struct bset_sort_state *, unsigned,
 			     struct time_stats *times);
 
 struct btree_nr_keys bch_sort_bsets(struct bset *, struct btree_keys *,
-				    unsigned, struct btree_node_iter *,
+				    unsigned, struct btree_node_iter_large *,
 				    btree_keys_sort_fn,
 				    struct bset_sort_state *);
 
diff --git a/drivers/md/bcache/btree_io.c b/drivers/md/bcache/btree_io.c
index 57c283e5d371..2e362003a44d 100644
--- a/drivers/md/bcache/btree_io.c
+++ b/drivers/md/bcache/btree_io.c
@@ -17,7 +17,7 @@
 
 static void btree_node_sort(struct cache_set *c, struct btree *b,
 			    struct btree_iter *iter, unsigned from,
-			    struct btree_node_iter *node_iter,
+			    struct btree_node_iter_large *node_iter,
 			    btree_keys_sort_fn sort, bool is_write_locked)
 {
 	struct btree_node *out;
@@ -262,12 +262,12 @@ void bch_btree_node_read_done(struct cache_set *c, struct btree *b,
 {
 	struct btree_node_entry *bne;
 	struct bset *i = &b->data->keys;
-	struct btree_node_iter *iter;
+	struct btree_node_iter_large *iter;
 	const char *err;
 	int ret;
 
 	iter = mempool_alloc(&c->fill_iter, GFP_NOIO);
-	__bch_btree_node_iter_init(iter, &b->keys);
+	__bch_btree_node_iter_large_init(iter, &b->keys);
 
 	err = "dynamic fault";
 	if (bch_meta_read_fault("btree"))
@@ -354,8 +354,8 @@ void bch_btree_node_read_done(struct cache_set *c, struct btree *b,
 		if (ret)
 			continue;
 
-		bch_btree_node_iter_push(iter, &b->keys,
-					 i->start, bset_bkey_last(i));
+		bch_btree_node_iter_large_push(iter, &b->keys,
+					       i->start, bset_bkey_last(i));
 	}
 
 	err = "corrupted btree";
diff --git a/drivers/md/bcache/extents.c b/drivers/md/bcache/extents.c
index d8b2f7797a70..10ce62fb673b 100644
--- a/drivers/md/bcache/extents.c
+++ b/drivers/md/bcache/extents.c
@@ -23,7 +23,7 @@
 
 static bool __bch_extent_normalize(struct cache_set *, struct bkey_s, bool);
 
-static void sort_key_next(struct btree_node_iter *iter,
+static void sort_key_next(struct btree_node_iter_large *iter,
 			  struct btree_keys *b,
 			  struct btree_node_iter_set *i)
 {
@@ -49,7 +49,7 @@ static void sort_key_next(struct btree_node_iter *iter,
 	_c ? _c > 0 : (l).k > (r).k;					\
 })
 
-static inline bool should_drop_next_key(struct btree_node_iter *iter,
+static inline bool should_drop_next_key(struct btree_node_iter_large *iter,
 					struct btree_keys *b)
 {
 	const struct bkey_format *f = &b->format;
@@ -76,8 +76,8 @@ static inline bool should_drop_next_key(struct btree_node_iter *iter,
 }
 
 struct btree_nr_keys bch_key_sort_fix_overlapping(struct btree_keys *b,
-						  struct bset *bset,
-						  struct btree_node_iter *iter)
+					struct bset *bset,
+					struct btree_node_iter_large *iter)
 {
 	struct bkey_packed *out = bset->start;
 	struct btree_nr_keys nr;
@@ -86,7 +86,7 @@ struct btree_nr_keys bch_key_sort_fix_overlapping(struct btree_keys *b,
 
 	heap_resort(iter, key_sort_cmp);
 
-	while (!bch_btree_node_iter_end(iter)) {
+	while (!bch_btree_node_iter_large_end(iter)) {
 		if (!should_drop_next_key(iter, b)) {
 			struct bkey_packed *k =
 				__btree_node_offset_to_key(b, iter->data->k);
@@ -679,13 +679,13 @@ static void extent_save(struct btree_keys *b, struct btree_node_iter *iter,
 	_c ? _c > 0 : (l).k < (r).k;					\
 })
 
-static inline void extent_sort_sift(struct btree_node_iter *iter,
+static inline void extent_sort_sift(struct btree_node_iter_large *iter,
 				    struct btree_keys *b, size_t i)
 {
 	heap_sift(iter, i, extent_sort_cmp);
 }
 
-static inline void extent_sort_next(struct btree_node_iter *iter,
+static inline void extent_sort_next(struct btree_node_iter_large *iter,
 				    struct btree_keys *b,
 				    struct btree_node_iter_set *i)
 {
@@ -723,7 +723,7 @@ static struct bkey_packed *extent_sort_append(struct btree_keys *b,
 
 struct btree_nr_keys bch_extent_sort_fix_overlapping(struct btree_keys *b,
 					struct bset *bset,
-					struct btree_node_iter *iter)
+					struct btree_node_iter_large *iter)
 {
 	struct bkey_format *f = &b->format;
 	struct btree_node_iter_set *_l = iter->data, *_r;
@@ -736,7 +736,7 @@ struct btree_nr_keys bch_extent_sort_fix_overlapping(struct btree_keys *b,
 
 	heap_resort(iter, extent_sort_cmp);
 
-	while (!bch_btree_node_iter_end(iter)) {
+	while (!bch_btree_node_iter_large_end(iter)) {
 		lk = __btree_node_offset_to_key(b, _l->k);
 
 		if (iter->used == 1) {
diff --git a/drivers/md/bcache/extents.h b/drivers/md/bcache/extents.h
index ee74bfeea3a5..eab98760cd9c 100644
--- a/drivers/md/bcache/extents.h
+++ b/drivers/md/bcache/extents.h
@@ -12,11 +12,11 @@ struct btree_insert_trans;
 struct btree_trans_entry;
 
 struct btree_nr_keys bch_key_sort_fix_overlapping(struct btree_keys *,
-						  struct bset *,
-						  struct btree_node_iter *);
+					struct bset *,
+					struct btree_node_iter_large *);
 struct btree_nr_keys bch_extent_sort_fix_overlapping(struct btree_keys *,
-						     struct bset *,
-						     struct btree_node_iter *);
+					struct bset *,
+					struct btree_node_iter_large *);
 
 enum btree_insert_ret
 bch_insert_fixup_key(struct btree_insert_trans *,
diff --git a/drivers/md/bcache/util.h b/drivers/md/bcache/util.h
index 188630b418ed..82e5f3ef6048 100644
--- a/drivers/md/bcache/util.h
+++ b/drivers/md/bcache/util.h
@@ -116,16 +116,20 @@ do {									\
 	}								\
 } while (0)
 
+#define __heap_add(h, d, cmp)						\
+do {									\
+	size_t _i = (h)->used++;					\
+	(h)->data[_i] = d;						\
+									\
+	heap_sift_down(h, _i, cmp);					\
+	heap_sift(h, _i, cmp);						\
+} while (0)
+
 #define heap_add(h, d, cmp)						\
 ({									\
 	bool _r = !heap_full(h);					\
-	if (_r) {							\
-		size_t _i = (h)->used++;				\
-		(h)->data[_i] = d;					\
-									\
-		heap_sift_down(h, _i, cmp);				\
-		heap_sift(h, _i, cmp);					\
-	}								\
+	if (_r)								\
+		__heap_add(h, d, cmp);					\
 	_r;								\
 })