bcachefs: kill btree_node_iter->used

Another patch will remove btree_node_iter->is_extents, which will let us
reduce sizeof(struct btree_iter) by 32 bytes, which will be imortant for
snapshot support.

9 files changed, 210 insertions, 93 deletions

diff --git a/fs/bcachefs/bset.c b/fs/bcachefs/bset.c
index a07d554092f7..92046ae4915c 100644
--- a/fs/bcachefs/bset.c
+++ b/fs/bcachefs/bset.c
@@ -174,13 +174,11 @@ static void bch2_btree_node_iter_next_check(struct btree_node_iter *iter,
 void bch2_btree_node_iter_verify(struct btree_node_iter *iter,
 				struct btree *b)
 {
-	struct btree_node_iter_set *set;
+	struct btree_node_iter_set *set, *prev = NULL;
 	struct bset_tree *t;
 	struct bkey_packed *k, *first;
 
-	BUG_ON(iter->used > MAX_BSETS);
-
-	if (!iter->used)
+	if (bch2_btree_node_iter_end(iter))
 		return;
 
 	btree_node_iter_for_each(iter, set) {
@@ -190,8 +188,10 @@ void bch2_btree_node_iter_verify(struct btree_node_iter *iter,
 		BUG_ON(__btree_node_offset_to_key(b, set->end) !=
 		       btree_bkey_last(b, t));
 
-		BUG_ON(set + 1 < iter->data + iter->used &&
-		       btree_node_iter_cmp(iter, b, set[0], set[1]) > 0);
+		BUG_ON(prev &&
+		       btree_node_iter_cmp(iter, b, *prev, *set) > 0);
+
+		prev = set;
 	}
 
 	first = __btree_node_offset_to_key(b, iter->data[0].k);
@@ -1463,22 +1463,8 @@ void bch2_btree_node_iter_push(struct btree_node_iter *iter,
 			       const struct bkey_packed *k,
 			       const struct bkey_packed *end)
 {
-	if (k != end) {
-		struct btree_node_iter_set *pos, n =
-			((struct btree_node_iter_set) {
-				 __btree_node_key_to_offset(b, k),
-				 __btree_node_key_to_offset(b, end)
-			 });
-
-		btree_node_iter_for_each(iter, pos)
-			if (btree_node_iter_cmp(iter, b, n, *pos) <= 0)
-				break;
-
-		memmove(pos + 1, pos,
-			(void *) (iter->data + iter->used) - (void *) pos);
-		iter->used++;
-		*pos = n;
-	}
+	__bch2_btree_node_iter_push(iter, b, k, end);
+	bch2_btree_node_iter_sort(iter, b);
 }
 
 noinline __flatten __attribute__((cold))
@@ -1595,8 +1581,6 @@ struct bkey_packed *bch2_btree_node_iter_bset_pos(struct btree_node_iter *iter,
 {
 	struct btree_node_iter_set *set;
 
-	EBUG_ON(iter->used > MAX_BSETS);
-
 	btree_node_iter_for_each(iter, set)
 		if (set->end == t->end_offset)
 			return __btree_node_offset_to_key(b, set->k);
@@ -1604,47 +1588,67 @@ struct bkey_packed *bch2_btree_node_iter_bset_pos(struct btree_node_iter *iter,
 	return btree_bkey_last(b, t);
 }
 
-static inline void btree_node_iter_sift(struct btree_node_iter *iter,
-					struct btree *b,
-					unsigned start)
-{
-	unsigned i;
-
-	EBUG_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]) > 0;
-	     i++)
-		swap(iter->data[i], iter->data[i + 1]);
-}
-
-static inline void btree_node_iter_sort_two(struct btree_node_iter *iter,
+static inline bool btree_node_iter_sort_two(struct btree_node_iter *iter,
 					    struct btree *b,
 					    unsigned first)
 {
-	if (btree_node_iter_cmp(iter, b,
-				iter->data[first],
-				iter->data[first + 1]) > 0)
+	bool ret;
+
+	if ((ret = (btree_node_iter_cmp(iter, b,
+					iter->data[first],
+					iter->data[first + 1]) > 0)))
 		swap(iter->data[first], iter->data[first + 1]);
+	return ret;
 }
 
 void bch2_btree_node_iter_sort(struct btree_node_iter *iter,
 			       struct btree *b)
 {
-	EBUG_ON(iter->used > 3);
-
 	/* unrolled bubble sort: */
 
-	if (iter->used > 2) {
+	if (!__btree_node_iter_set_end(iter, 2)) {
 		btree_node_iter_sort_two(iter, b, 0);
 		btree_node_iter_sort_two(iter, b, 1);
 	}
 
-	if (iter->used > 1)
+	if (!__btree_node_iter_set_end(iter, 1))
 		btree_node_iter_sort_two(iter, b, 0);
 }
 
+void bch2_btree_node_iter_set_drop(struct btree_node_iter *iter,
+				   struct btree_node_iter_set *set)
+{
+	struct btree_node_iter_set *last =
+		iter->data + ARRAY_SIZE(iter->data) - 1;
+
+	memmove(&set[0], &set[1], (void *) last - (void *) set);
+	*last = (struct btree_node_iter_set) { 0, 0 };
+}
+
+static inline void __bch2_btree_node_iter_advance(struct btree_node_iter *iter,
+						  struct btree *b)
+{
+	iter->data->k += __bch2_btree_node_iter_peek_all(iter, b)->u64s;
+
+	EBUG_ON(iter->data->k > iter->data->end);
+
+	if (unlikely(__btree_node_iter_set_end(iter, 0))) {
+		bch2_btree_node_iter_set_drop(iter, iter->data);
+		return;
+	}
+
+	if (__btree_node_iter_set_end(iter, 1))
+		return;
+
+	if (!btree_node_iter_sort_two(iter, b, 0))
+		return;
+
+	if (__btree_node_iter_set_end(iter, 2))
+		return;
+
+	btree_node_iter_sort_two(iter, b, 1);
+}
+
 /**
  * bch_btree_node_iter_advance - advance @iter by one key
  *
@@ -1656,21 +1660,22 @@ void bch2_btree_node_iter_advance(struct btree_node_iter *iter,
 {
 #ifdef CONFIG_BCACHEFS_DEBUG
 	struct bkey_packed *k = bch2_btree_node_iter_peek_all(iter, b);
-#endif
-	iter->data->k += __bch2_btree_node_iter_peek_all(iter, b)->u64s;
 
-	EBUG_ON(iter->data->k > iter->data->end);
+	__bch2_btree_node_iter_advance(iter, b);
+	bch2_btree_node_iter_next_check(iter, b, k);
+#else
+	__bch2_btree_node_iter_advance(iter, b);
+#endif
+}
 
-	if (iter->data->k == iter->data->end) {
-		EBUG_ON(iter->used == 0);
-		iter->data[0] = iter->data[--iter->used];
-	}
+static inline bool __btree_node_iter_used(struct btree_node_iter *iter)
+{
+	unsigned n = ARRAY_SIZE(iter->data);
 
-	btree_node_iter_sift(iter, b, 0);
+	while (n && __btree_node_iter_set_end(iter, n - 1))
+		--n;
 
-#ifdef CONFIG_BCACHEFS_DEBUG
-	bch2_btree_node_iter_next_check(iter, b, k);
-#endif
+	return n;
 }
 
 /*
@@ -1683,7 +1688,7 @@ struct bkey_packed *bch2_btree_node_iter_prev_all(struct btree_node_iter *iter,
 	struct btree_node_iter_set *set;
 	struct bset_tree *t;
 	struct bset_tree *prev_t;
-	unsigned end;
+	unsigned end, used;
 
 	bch2_btree_node_iter_verify(iter, b);
 
@@ -1715,10 +1720,12 @@ struct bkey_packed *bch2_btree_node_iter_prev_all(struct btree_node_iter *iter,
 			goto out;
 		}
 
+	used = __btree_node_iter_used(iter);
+	BUG_ON(used >= ARRAY_SIZE(iter->data));
+
 	memmove(&iter->data[1],
 		&iter->data[0],
-		(void *) &iter->data[iter->used] - (void *) &iter->data[0]);
-	iter->used++;
+		(void *) &iter->data[used] - (void *) &iter->data[0]);
 out:
 	iter->data[0].k = __btree_node_key_to_offset(b, prev);
 	iter->data[0].end = end;
diff --git a/fs/bcachefs/bset.h b/fs/bcachefs/bset.h
index f5a844817b1d..cc4ea5d87e4b 100644
--- a/fs/bcachefs/bset.h
+++ b/fs/bcachefs/bset.h
@@ -422,7 +422,6 @@ static inline enum bch_extent_overlap bch2_extent_overlap(const struct bkey *k,
 
 struct btree_node_iter {
 	u8		is_extents;
-	u16		used;
 
 	struct btree_node_iter_set {
 		u16	k, end;
@@ -432,8 +431,8 @@ struct btree_node_iter {
 static inline void __bch2_btree_node_iter_init(struct btree_node_iter *iter,
 					      bool is_extents)
 {
-	iter->used = 0;
 	iter->is_extents = is_extents;
+	memset(iter->data, 0, sizeof(iter->data));
 }
 
 void bch2_btree_node_iter_push(struct btree_node_iter *, struct btree *,
@@ -448,16 +447,25 @@ struct bkey_packed *bch2_btree_node_iter_bset_pos(struct btree_node_iter *,
 						 struct bset_tree *);
 
 void bch2_btree_node_iter_sort(struct btree_node_iter *, struct btree *);
+void bch2_btree_node_iter_set_drop(struct btree_node_iter *,
+				   struct btree_node_iter_set *);
 void bch2_btree_node_iter_advance(struct btree_node_iter *, struct btree *);
 
-#define btree_node_iter_for_each(_iter, _set)			\
-	for (_set = (_iter)->data;				\
-	     _set < (_iter)->data + (_iter)->used;		\
+#define btree_node_iter_for_each(_iter, _set)				\
+	for (_set = (_iter)->data;					\
+	     _set < (_iter)->data + ARRAY_SIZE((_iter)->data) &&	\
+	     (_set)->k != (_set)->end;					\
 	     _set++)
 
+static inline bool __btree_node_iter_set_end(struct btree_node_iter *iter,
+					     unsigned i)
+{
+	return iter->data[i].k == iter->data[i].end;
+}
+
 static inline bool bch2_btree_node_iter_end(struct btree_node_iter *iter)
 {
-	return !iter->used;
+	return __btree_node_iter_set_end(iter, 0);
 }
 
 static inline int __btree_node_iter_cmp(bool is_extents,
@@ -493,11 +501,18 @@ static inline void __bch2_btree_node_iter_push(struct btree_node_iter *iter,
 			      const struct bkey_packed *k,
 			      const struct bkey_packed *end)
 {
-	if (k != end)
-		iter->data[iter->used++] = (struct btree_node_iter_set) {
+	if (k != end) {
+		struct btree_node_iter_set *pos;
+
+		btree_node_iter_for_each(iter, pos)
+			;
+
+		BUG_ON(pos >= iter->data + ARRAY_SIZE(iter->data));
+		*pos = (struct btree_node_iter_set) {
 			__btree_node_key_to_offset(b, k),
 			__btree_node_key_to_offset(b, end)
 		};
+	}
 }
 
 static inline struct bkey_packed *
diff --git a/fs/bcachefs/btree_io.c b/fs/bcachefs/btree_io.c
index d805fb41886b..99b50f8960f9 100644
--- a/fs/bcachefs/btree_io.c
+++ b/fs/bcachefs/btree_io.c
@@ -18,6 +18,43 @@
 
 #include <trace/events/bcachefs.h>
 
+/* btree_node_iter_large: */
+
+#define btree_node_iter_cmp_heap(h, _l, _r)				\
+	__btree_node_iter_cmp((iter)->is_extents, b,			\
+			       __btree_node_offset_to_key(b, (_l).k),	\
+			       __btree_node_offset_to_key(b, (_r).k))
+
+void bch2_btree_node_iter_large_push(struct btree_node_iter_large *iter,
+				     struct btree *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 bch2_btree_node_iter_large_advance(struct btree_node_iter_large *iter,
+					struct btree *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_down(iter, 0, btree_node_iter_cmp_heap);
+}
+
 static void verify_no_dups(struct btree *b,
 			   struct bkey_packed *start,
 			   struct bkey_packed *end)
@@ -1108,7 +1145,7 @@ fsck_err:
 int bch2_btree_node_read_done(struct bch_fs *c, struct btree *b, bool have_retry)
 {
 	struct btree_node_entry *bne;
-	struct btree_node_iter *iter;
+	struct btree_node_iter_large *iter;
 	struct btree_node *sorted;
 	struct bkey_packed *k;
 	struct bset *i;
@@ -1117,7 +1154,7 @@ int bch2_btree_node_read_done(struct bch_fs *c, struct btree *b, bool have_retry
 	int ret, retry_read = 0, write = READ;
 
 	iter = mempool_alloc(&c->fill_iter, GFP_NOIO);
-	__bch2_btree_node_iter_init(iter, btree_node_is_extents(b));
+	__bch2_btree_node_iter_large_init(iter, btree_node_is_extents(b));
 
 	if (bch2_meta_read_fault("btree"))
 		btree_err(BTREE_ERR_MUST_RETRY, c, b, NULL,
@@ -1202,11 +1239,11 @@ int bch2_btree_node_read_done(struct bch_fs *c, struct btree *b, bool have_retry
 				continue;
 		}
 
-		__bch2_btree_node_iter_push(iter, b,
+		bch2_btree_node_iter_large_push(iter, b,
 					   i->start,
 					   vstruct_idx(i, whiteout_u64s));
 
-		__bch2_btree_node_iter_push(iter, b,
+		bch2_btree_node_iter_large_push(iter, b,
 					   vstruct_idx(i, whiteout_u64s),
 					   vstruct_last(i));
 	}
diff --git a/fs/bcachefs/btree_io.h b/fs/bcachefs/btree_io.h
index f27907168629..01df817d3eeb 100644
--- a/fs/bcachefs/btree_io.h
+++ b/fs/bcachefs/btree_io.h
@@ -1,6 +1,7 @@
 #ifndef _BCACHEFS_BTREE_IO_H
 #define _BCACHEFS_BTREE_IO_H
 
+#include "bset.h"
 #include "extents.h"
 #include "io_types.h"
 
@@ -141,4 +142,55 @@ void bch2_btree_flush_all_writes(struct bch_fs *);
 void bch2_btree_verify_flushed(struct bch_fs *);
 ssize_t bch2_dirty_btree_nodes_print(struct bch_fs *, char *);
 
+/* Sorting */
+
+struct btree_node_iter_large {
+	u8		is_extents;
+	u16		used;
+
+	struct btree_node_iter_set data[MAX_BSETS];
+};
+
+static inline void
+__bch2_btree_node_iter_large_init(struct btree_node_iter_large *iter,
+				  bool is_extents)
+{
+	iter->used = 0;
+	iter->is_extents = is_extents;
+}
+
+void bch2_btree_node_iter_large_advance(struct btree_node_iter_large *,
+					struct btree *);
+
+void bch2_btree_node_iter_large_push(struct btree_node_iter_large *,
+				     struct btree *,
+				     const struct bkey_packed *,
+				     const struct bkey_packed *);
+
+static inline bool bch2_btree_node_iter_large_end(struct btree_node_iter_large *iter)
+{
+	return !iter->used;
+}
+
+static inline struct bkey_packed *
+bch2_btree_node_iter_large_peek_all(struct btree_node_iter_large *iter,
+				    struct btree *b)
+{
+	return bch2_btree_node_iter_large_end(iter)
+		? NULL
+		: __btree_node_offset_to_key(b, iter->data->k);
+}
+
+static inline struct bkey_packed *
+bch2_btree_node_iter_large_next_all(struct btree_node_iter_large *iter,
+				    struct btree *b)
+{
+	struct bkey_packed *ret = bch2_btree_node_iter_large_peek_all(iter, b);
+
+	if (ret)
+		bch2_btree_node_iter_large_advance(iter, b);
+
+	return ret;
+}
+
 #endif /* _BCACHEFS_BTREE_IO_H */
diff --git a/fs/bcachefs/btree_iter.c b/fs/bcachefs/btree_iter.c
index 21a6cbc2d7c7..cc5bcbb28a50 100644
--- a/fs/bcachefs/btree_iter.c
+++ b/fs/bcachefs/btree_iter.c
@@ -382,7 +382,7 @@ found:
 	} else if (set->k < offset + clobber_u64s) {
 		set->k = offset + new_u64s;
 		if (set->k == set->end)
-			*set = node_iter->data[--node_iter->used];
+			bch2_btree_node_iter_set_drop(node_iter, set);
 	} else {
 		set->k = (int) set->k + shift;
 		goto iter_current_key_not_modified;
diff --git a/fs/bcachefs/extents.c b/fs/bcachefs/extents.c
index 37470f86e588..9fbc642cf532 100644
--- a/fs/bcachefs/extents.c
+++ b/fs/bcachefs/extents.c
@@ -28,7 +28,7 @@
 static enum merge_result bch2_extent_merge(struct bch_fs *, struct btree *,
 					   struct bkey_i *, struct bkey_i *);
 
-static void sort_key_next(struct btree_node_iter *iter,
+static void sort_key_next(struct btree_node_iter_large *iter,
 			  struct btree *b,
 			  struct btree_node_iter_set *i)
 {
@@ -54,7 +54,7 @@ static void sort_key_next(struct btree_node_iter *iter,
 	?: (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 *b)
 {
 	struct btree_node_iter_set *l = iter->data, *r = iter->data + 1;
@@ -81,8 +81,8 @@ static inline bool should_drop_next_key(struct btree_node_iter *iter,
 }
 
 struct btree_nr_keys bch2_key_sort_fix_overlapping(struct bset *dst,
-						  struct btree *b,
-						  struct btree_node_iter *iter)
+					struct btree *b,
+					struct btree_node_iter_large *iter)
 {
 	struct bkey_packed *out = dst->start;
 	struct btree_nr_keys nr;
@@ -91,7 +91,7 @@ struct btree_nr_keys bch2_key_sort_fix_overlapping(struct bset *dst,
 
 	heap_resort(iter, key_sort_cmp);
 
-	while (!bch2_btree_node_iter_end(iter)) {
+	while (!bch2_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);
@@ -890,13 +890,13 @@ static void extent_save(struct btree *b, struct btree_node_iter *iter,
 		 bkey_start_pos(&_ur)) ?: (r).k - (l).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 *b, size_t i)
 {
 	heap_sift_down(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 *b,
 				    struct btree_node_iter_set *i)
 {
@@ -938,7 +938,7 @@ static void extent_sort_append(struct bch_fs *c,
 struct btree_nr_keys bch2_extent_sort_fix_overlapping(struct bch_fs *c,
 					struct bset *dst,
 					struct btree *b,
-					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;
@@ -951,7 +951,7 @@ struct btree_nr_keys bch2_extent_sort_fix_overlapping(struct bch_fs *c,
 
 	heap_resort(iter, extent_sort_cmp);
 
-	while (!bch2_btree_node_iter_end(iter)) {
+	while (!bch2_btree_node_iter_large_end(iter)) {
 		lk = __btree_node_offset_to_key(b, _l->k);
 
 		if (iter->used == 1) {
diff --git a/fs/bcachefs/extents.h b/fs/bcachefs/extents.h
index 83c0f24db588..1ce0d38d278a 100644
--- a/fs/bcachefs/extents.h
+++ b/fs/bcachefs/extents.h
@@ -8,6 +8,7 @@
 struct bch_fs;
 struct journal_res;
 struct btree_node_iter;
+struct btree_node_iter_large;
 struct btree_insert;
 struct btree_insert_entry;
 struct extent_insert_hook;
@@ -16,11 +17,11 @@ union bch_extent_crc;
 
 struct btree_nr_keys bch2_key_sort_fix_overlapping(struct bset *,
 						  struct btree *,
-						  struct btree_node_iter *);
+						  struct btree_node_iter_large *);
 struct btree_nr_keys bch2_extent_sort_fix_overlapping(struct bch_fs *c,
 						     struct bset *,
 						     struct btree *,
-						     struct btree_node_iter *);
+						     struct btree_node_iter_large *);
 
 extern const struct bkey_ops bch2_bkey_btree_ops;
 extern const struct bkey_ops bch2_bkey_extent_ops;
diff --git a/fs/bcachefs/super.c b/fs/bcachefs/super.c
index 567b217cc528..77670ea6e077 100644
--- a/fs/bcachefs/super.c
+++ b/fs/bcachefs/super.c
@@ -586,7 +586,8 @@ static struct bch_fs *bch2_fs_alloc(struct bch_sb *sb, struct bch_opts opts)
 	if (bch2_fs_init_fault("fs_alloc"))
 		goto err;
 
-	iter_size = (btree_blocks(c) + 1) * 2 *
+	iter_size = sizeof(struct btree_node_iter_large) +
+		(btree_blocks(c) + 1) * 2 *
 		sizeof(struct btree_node_iter_set);
 
 	if (!(c->wq = alloc_workqueue("bcachefs",
diff --git a/fs/bcachefs/util.h b/fs/bcachefs/util.h
index d475f986ad30..cc89da1f8d9c 100644
--- a/fs/bcachefs/util.h
+++ b/fs/bcachefs/util.h
@@ -181,15 +181,19 @@ do {									\
 	}								\
 } while (0)
 
-#define heap_add(h, new, cmp)						\
+#define __heap_add(h, d, cmp)						\
+do {									\
+	size_t _i = (h)->used++;					\
+	(h)->data[_i] = d;						\
+									\
+	heap_sift_up(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] = new;					\
-									\
-		heap_sift_up(h, _i, cmp);				\
-	}								\
+	if (_r)								\
+		__heap_add(h, d, cmp);					\
 	_r;								\
 })