Subject: linux-next: manual merge of the refactor-heap tree with the block tree

From: Stephen Rothwell <[email-masked]>
Date: Thu, 9 May 2024 15:27:45 +1000

Hi all,

Today's linux-next merge of the refactor-heap tree got conflicts in:

  drivers/md/bcache/bset.c
  drivers/md/bcache/bset.h
  drivers/md/bcache/btree.c
  drivers/md/bcache/writeback.c

between commit:

  3a861560ccb3 ("bcache: fix variable length array abuse in btree_iter")

from the block tree and commit:

  afa5721abaaa ("bcache: Remove heap-related macros and switch to generic min_heap")

from the refactor-heap tree.

Ok, these conflicts are too extensive, so I am dropping the refactor-heap
tree for today.  I suggest you all get together and sort something out.

I fixed it up (see above) and can carry the fix as necessary. This
is now fixed as far as linux-next is concerned, but any non trivial
conflicts should be mentioned to your upstream maintainer when your tree
is submitted for merging.  You may also want to consider cooperating
with the maintainer of the conflicting tree to minimise any particularly
complex conflicts.

Here are the conflicts:

diff --cc drivers/md/bcache/bset.c
index 463eb13bd0b2,bd97d8626887..000000000000
--- a/drivers/md/bcache/bset.c
+++ b/drivers/md/bcache/bset.c
@@@ -54,9 -54,11 +54,11 @@@ void bch_dump_bucket(struct btree_keys 
  int __bch_count_data(struct btree_keys *b)
  {
  	unsigned int ret = 0;
 -	struct btree_iter iter;
 +	struct btree_iter_stack iter;
  	struct bkey *k;
  
+ 	min_heap_init(&iter.heap, NULL, MAX_BSETS);
+ 
  	if (b->ops->is_extents)
  		for_each_key(b, k, &iter)
  			ret += KEY_SIZE(k);
@@@ -67,9 -69,11 +69,11 @@@ void __bch_check_keys(struct btree_key
  {
  	va_list args;
  	struct bkey *k, *p = NULL;
 -	struct btree_iter iter;
 +	struct btree_iter_stack iter;
  	const char *err;
  
+ 	min_heap_init(&iter.heap, NULL, MAX_BSETS);
+ 
  	for_each_key(b, k, &iter) {
  		if (b->ops->is_extents) {
  			err = "Keys out of order";
@@@ -1094,24 -1109,30 +1109,35 @@@ static inline bool btree_iter_end(struc
  void bch_btree_iter_push(struct btree_iter *iter, struct bkey *k,
  			 struct bkey *end)
  {
+ 	const struct min_heap_callbacks callbacks = {
+ 		.less = new_btree_iter_cmp,
+ 		.swp = new_btree_iter_swap,
+ 	};
+ 
  	if (k != end)
- 		BUG_ON(!heap_add(iter,
- 				 ((struct btree_iter_set) { k, end }),
- 				 btree_iter_cmp));
+ 		BUG_ON(!min_heap_push(&iter->heap,
+ 				 &((struct btree_iter_set) { k, end }),
+ 				 &callbacks,
+ 				 NULL));
  }
  
 -static struct bkey *__bch_btree_iter_init(struct btree_keys *b,
 -					  struct btree_iter *iter,
 -					  struct bkey *search,
 -					  struct bset_tree *start)
 +static struct bkey *__bch_btree_iter_stack_init(struct btree_keys *b,
 +						struct btree_iter_stack *iter,
 +						struct bkey *search,
 +						struct bset_tree *start)
  {
  	struct bkey *ret = NULL;
  
++<<<<<<< HEAD
 +	iter->iter.size = ARRAY_SIZE(iter->stack_data);
 +	iter->iter.used = 0;
++=======
+ 	iter->heap.size = ARRAY_SIZE(iter->heap.preallocated);
+ 	iter->heap.nr = 0;
++>>>>>>> refactor-heap/refactor-heap
  
  #ifdef CONFIG_BCACHE_DEBUG
 -	iter->b = b;
 +	iter->iter.b = b;
  #endif
  
  	for (; start <= bset_tree_last(b); start++) {
@@@ -1293,10 -1324,11 +1329,15 @@@ void bch_btree_sort_partial(struct btre
  			    struct bset_sort_state *state)
  {
  	size_t order = b->page_order, keys = 0;
 -	struct btree_iter iter;
 +	struct btree_iter_stack iter;
  	int oldsize = bch_count_data(b);
  
++<<<<<<< HEAD
 +	__bch_btree_iter_stack_init(b, &iter, NULL, &b->set[start]);
++=======
+ 	min_heap_init(&iter.heap, NULL, MAX_BSETS);
+ 	__bch_btree_iter_init(b, &iter, NULL, &b->set[start]);
++>>>>>>> refactor-heap/refactor-heap
  
  	if (start) {
  		unsigned int i;
@@@ -1323,11 -1355,13 +1364,17 @@@ void bch_btree_sort_into(struct btree_k
  			 struct bset_sort_state *state)
  {
  	uint64_t start_time = local_clock();
 -	struct btree_iter iter;
 +	struct btree_iter_stack iter;
  
++<<<<<<< HEAD
 +	bch_btree_iter_stack_init(b, &iter, NULL);
++=======
+ 	min_heap_init(&iter.heap, NULL, MAX_BSETS);
+ 
+ 	bch_btree_iter_init(b, &iter, NULL);
++>>>>>>> refactor-heap/refactor-heap
  
 -	btree_mergesort(b, new->set->data, &iter, false, true);
 +	btree_mergesort(b, new->set->data, &iter.iter, false, true);
  
  	bch_time_stats_update(&state->time, start_time);
  
diff --cc drivers/md/bcache/bset.h
index 011f6062c4c0,f79441acd4c1..000000000000
--- a/drivers/md/bcache/bset.h
+++ b/drivers/md/bcache/bset.h
@@@ -318,17 -323,7 +323,20 @@@ struct btree_iter 
  #ifdef CONFIG_BCACHE_DEBUG
  	struct btree_keys *b;
  #endif
++<<<<<<< HEAD
 +	struct btree_iter_set {
 +		struct bkey *k, *end;
 +	} data[];
 +};
 +
 +/* Fixed-size btree_iter that can be allocated on the stack */
 +
 +struct btree_iter_stack {
 +	struct btree_iter iter;
 +	struct btree_iter_set stack_data[MAX_BSETS];
++=======
+ 	MIN_HEAP_PREALLOCATED(struct btree_iter_set, btree_iter_heap, MAX_BSETS) heap;
++>>>>>>> refactor-heap/refactor-heap
  };
  
  typedef bool (*ptr_filter_fn)(struct btree_keys *b, const struct bkey *k);
diff --cc drivers/md/bcache/btree.c
index d011a7154d33,a2bb86d52ad4..000000000000
--- a/drivers/md/bcache/btree.c
+++ b/drivers/md/bcache/btree.c
@@@ -1309,9 -1309,11 +1309,11 @@@ static bool btree_gc_mark_node(struct b
  	uint8_t stale = 0;
  	unsigned int keys = 0, good_keys = 0;
  	struct bkey *k;
 -	struct btree_iter iter;
 +	struct btree_iter_stack iter;
  	struct bset_tree *t;
  
+ 	min_heap_init(&iter.heap, NULL, MAX_BSETS);
+ 
  	gc->nodes++;
  
  	for_each_key_filter(&b->keys, k, &iter, bch_ptr_invalid) {
@@@ -1570,9 -1572,11 +1572,11 @@@ static int btree_gc_rewrite_node(struc
  static unsigned int btree_gc_count_keys(struct btree *b)
  {
  	struct bkey *k;
 -	struct btree_iter iter;
 +	struct btree_iter_stack iter;
  	unsigned int ret = 0;
  
+ 	min_heap_init(&iter.heap, NULL, MAX_BSETS);
+ 
  	for_each_key_filter(&b->keys, k, &iter, bch_ptr_bad)
  		ret += bkey_u64s(k);
  
@@@ -1615,7 -1619,8 +1619,12 @@@ static int btree_gc_recurse(struct btre
  	struct gc_merge_info r[GC_MERGE_NODES];
  	struct gc_merge_info *i, *last = r + ARRAY_SIZE(r) - 1;
  
++<<<<<<< HEAD
 +	bch_btree_iter_stack_init(&b->keys, &iter, &b->c->gc_done);
++=======
+ 	min_heap_init(&iter.heap, NULL, MAX_BSETS);
+ 	bch_btree_iter_init(&b->keys, &iter, &b->c->gc_done);
++>>>>>>> refactor-heap/refactor-heap
  
  	for (i = r; i < r + ARRAY_SIZE(r); i++)
  		i->b = ERR_PTR(-EINTR);
@@@ -1912,8 -1916,10 +1921,10 @@@ static int bch_btree_check_recurse(stru
  {
  	int ret = 0;
  	struct bkey *k, *p = NULL;
 -	struct btree_iter iter;
 +	struct btree_iter_stack iter;
  
+ 	min_heap_init(&iter.heap, NULL, MAX_BSETS);
+ 
  	for_each_key_filter(&b->keys, k, &iter, bch_ptr_invalid)
  		bch_initial_mark_key(b->c, b->level, k);
  
@@@ -1959,9 -1965,11 +1970,11 @@@ static int bch_btree_check_thread(void 
  	cur_idx = prev_idx = 0;
  	ret = 0;
  
+ 	min_heap_init(&iter.heap, NULL, MAX_BSETS);
+ 
  	/* root node keys are checked before thread created */
 -	bch_btree_iter_init(&c->root->keys, &iter, NULL);
 -	k = bch_btree_iter_next_filter(&iter, &c->root->keys, bch_ptr_bad);
 +	bch_btree_iter_stack_init(&c->root->keys, &iter, NULL);
 +	k = bch_btree_iter_next_filter(&iter.iter, &c->root->keys, bch_ptr_bad);
  	BUG_ON(!k);
  
  	p = k;
@@@ -2052,9 -2060,11 +2065,11 @@@ int bch_btree_check(struct cache_set *c
  	int ret = 0;
  	int i;
  	struct bkey *k = NULL;
 -	struct btree_iter iter;
 +	struct btree_iter_stack iter;
  	struct btree_check_state check_state;
  
+ 	min_heap_init(&iter.heap, NULL, MAX_BSETS);
+ 
  	/* check and mark root node keys */
  	for_each_key_filter(&c->root->keys, k, &iter, bch_ptr_invalid)
  		bch_initial_mark_key(c, c->root->level, k);
@@@ -2548,11 -2558,12 +2563,16 @@@ static int bch_btree_map_nodes_recurse(
  
  	if (b->level) {
  		struct bkey *k;
 -		struct btree_iter iter;
 +		struct btree_iter_stack iter;
  
++<<<<<<< HEAD
 +		bch_btree_iter_stack_init(&b->keys, &iter, from);
++=======
+ 		min_heap_init(&iter.heap, NULL, MAX_BSETS);
+ 		bch_btree_iter_init(&b->keys, &iter, from);
++>>>>>>> refactor-heap/refactor-heap
  
 -		while ((k = bch_btree_iter_next_filter(&iter, &b->keys,
 +		while ((k = bch_btree_iter_next_filter(&iter.iter, &b->keys,
  						       bch_ptr_bad))) {
  			ret = bcache_btree(map_nodes_recurse, k, b,
  				    op, from, fn, flags);
@@@ -2581,12 -2592,12 +2601,17 @@@ int bch_btree_map_keys_recurse(struct b
  {
  	int ret = MAP_CONTINUE;
  	struct bkey *k;
 -	struct btree_iter iter;
 +	struct btree_iter_stack iter;
  
++<<<<<<< HEAD
 +	bch_btree_iter_stack_init(&b->keys, &iter, from);
++=======
+ 	min_heap_init(&iter.heap, NULL, MAX_BSETS);
+ 	bch_btree_iter_init(&b->keys, &iter, from);
++>>>>>>> refactor-heap/refactor-heap
  
 -	while ((k = bch_btree_iter_next_filter(&iter, &b->keys, bch_ptr_bad))) {
 +	while ((k = bch_btree_iter_next_filter(&iter.iter, &b->keys,
 +					       bch_ptr_bad))) {
  		ret = !b->level
  			? fn(op, b, k)
  			: bcache_btree(map_keys_recurse, k,
diff --cc drivers/md/bcache/writeback.c
index 792e070ccf38,c1d28e365910..000000000000
--- a/drivers/md/bcache/writeback.c
+++ b/drivers/md/bcache/writeback.c
@@@ -915,8 -915,9 +915,14 @@@ static int bch_dirty_init_thread(void *
  	k = p = NULL;
  	prev_idx = 0;
  
++<<<<<<< HEAD
 +	bch_btree_iter_stack_init(&c->root->keys, &iter, NULL);
 +	k = bch_btree_iter_next_filter(&iter.iter, &c->root->keys, bch_ptr_bad);
++=======
+ 	min_heap_init(&iter.heap, NULL, MAX_BSETS);
+ 	bch_btree_iter_init(&c->root->keys, &iter, NULL);
+ 	k = bch_btree_iter_next_filter(&iter, &c->root->keys, bch_ptr_bad);
++>>>>>>> refactor-heap/refactor-heap
  	BUG_ON(!k);
  
  	p = k;

-- 
Cheers,
Stephen Rothwell