[PATCH 00/10] btrfs: backref cache cleanups

[PATCH 00/10] btrfs: backref cache cleanups

[Josef Bacik]

Hello,

This is the followup to the relocation fix that I sent out earlier.  This series
cleans up a lot of the complicated things that exist in backref cache because we
were keeping track of changes to the file system during relocation.  Now that we
do not do this we can simplify a lot of the code and make it easier to
understand.  I've tested this with the horror show of a relocation test I was
using to trigger the original problem.  I'm running fstests now via the CI, but
this seems solid.  Hopefully this makes the relocation code a bit easier to
understand.  Thanks,

Josef

Josef Bacik (10):
  btrfs: convert BUG_ON in btrfs_reloc_cow_block to proper error
    handling
  btrfs: remove the changed list for backref cache
  btrfs: add a comment for new_bytenr in bacref_cache_node
  btrfs: cleanup select_reloc_root
  btrfs: remove clone_backref_node
  btrfs: don't build backref tree for cowonly blocks
  btrfs: do not handle non-shareable roots in backref cache
  btrfs: simplify btrfs_backref_release_cache
  btrfs: remove the ->lowest and ->leaves members from backref cache
  btrfs: remove detached list from btrfs_backref_cache

 fs/btrfs/backref.c    | 105 +++++-------
 fs/btrfs/backref.h    |  16 +-
 fs/btrfs/relocation.c | 362 +++++++++++++++++-------------------------
 3 files changed, 192 insertions(+), 291 deletions(-)

-- 
2.43.0

[PATCH 01/10] btrfs: convert BUG_ON in btrfs_reloc_cow_block to proper error handling

[Josef Bacik]

This BUG_ON is meant to catch backref cache problems, but these can
arise from either bugs in the backref cache or corruption in the extent
tree.  Fix it to be a proper error and change it to an ASSERT() so that
developers notice problems.

Signed-off-by: Josef Bacik <josef@toxicpanda.com>
---
 fs/btrfs/relocation.c | 16 ++++++++++++++--
 1 file changed, 14 insertions(+), 2 deletions(-)

diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index f3834f8d26b4..3c89e79d0259 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -4399,8 +4399,20 @@ int btrfs_reloc_cow_block(struct btrfs_trans_handle *trans,
 		WARN_ON(!first_cow && level == 0);
 
 		node = rc->backref_cache.path[level];
-		BUG_ON(node->bytenr != buf->start &&
-		       node->new_bytenr != buf->start);
+
+		/*
+		 * If node->bytenr != buf->start and node->new_bytenr !=
+		 * buf->start then we've got the wrong backref node for what we
+		 * expected to see here and the cache is incorrect.
+		 */
+		if (node->bytenr != buf->start &&
+		    node->new_bytenr != buf->start) {
+			btrfs_err(fs_info,
+"bytenr %llu was found but our backref cache was expecting %llu or %llu",
+				  buf->start, node->bytenr, node->new_bytenr);
+			ASSERT(0);
+			return -EUCLEAN;
+		}
 
 		btrfs_backref_drop_node_buffer(node);
 		atomic_inc(&cow->refs);
-- 
2.43.0

Re: [PATCH 01/10] btrfs: convert BUG_ON in btrfs_reloc_cow_block to proper error handling

[David Sterba]

On Thu, Oct 03, 2024 at 11:43:03AM -0400, Josef Bacik wrote:
> This BUG_ON is meant to catch backref cache problems, but these can
> arise from either bugs in the backref cache or corruption in the extent
> tree.  Fix it to be a proper error and change it to an ASSERT() so that
> developers notice problems.
> 
> Signed-off-by: Josef Bacik <josef@toxicpanda.com>
> ---
>  fs/btrfs/relocation.c | 16 ++++++++++++++--
>  1 file changed, 14 insertions(+), 2 deletions(-)
> 
> diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
> index f3834f8d26b4..3c89e79d0259 100644
> --- a/fs/btrfs/relocation.c
> +++ b/fs/btrfs/relocation.c
> @@ -4399,8 +4399,20 @@ int btrfs_reloc_cow_block(struct btrfs_trans_handle *trans,
>  		WARN_ON(!first_cow && level == 0);
>  
>  		node = rc->backref_cache.path[level];
> -		BUG_ON(node->bytenr != buf->start &&
> -		       node->new_bytenr != buf->start);
> +
> +		/*
> +		 * If node->bytenr != buf->start and node->new_bytenr !=
> +		 * buf->start then we've got the wrong backref node for what we
> +		 * expected to see here and the cache is incorrect.
> +		 */
> +		if (node->bytenr != buf->start &&
> +		    node->new_bytenr != buf->start) {
> +			btrfs_err(fs_info,
> +"bytenr %llu was found but our backref cache was expecting %llu or %llu",
> +				  buf->start, node->bytenr, node->new_bytenr);
> +			ASSERT(0);

Please don't add the assert(0), the error message and EUCLEAN should be
sufficient. The caller btrfs_force_cow_block() aborts if it fails so
this will be noticealbe. Syzbot is good at hitting strange assertions so
we'll eventually get a report and have to fix it by removing the
assert(0) again.

[PATCH 02/10] btrfs: remove the changed list for backref cache

[Josef Bacik]

Now that we're not updating the backref cache when we switch transids we
can remove the changed list.

We're going to keep the new_bytenr field because it serves as a good
sanity check for the backref cache and relocation, and can prevent us
from making extent tree corruption worse.

Signed-off-by: Josef Bacik <josef@toxicpanda.com>
---
 fs/btrfs/backref.c    |  2 --
 fs/btrfs/backref.h    |  2 --
 fs/btrfs/relocation.c | 22 ++++++++--------------
 3 files changed, 8 insertions(+), 18 deletions(-)

diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index f8e1d5b2c512..881bb5600b55 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -3021,7 +3021,6 @@ void btrfs_backref_init_cache(struct btrfs_fs_info *fs_info,
 	cache->rb_root = RB_ROOT;
 	for (i = 0; i < BTRFS_MAX_LEVEL; i++)
 		INIT_LIST_HEAD(&cache->pending[i]);
-	INIT_LIST_HEAD(&cache->changed);
 	INIT_LIST_HEAD(&cache->detached);
 	INIT_LIST_HEAD(&cache->leaves);
 	INIT_LIST_HEAD(&cache->pending_edge);
@@ -3189,7 +3188,6 @@ void btrfs_backref_release_cache(struct btrfs_backref_cache *cache)
 	}
 	ASSERT(list_empty(&cache->pending_edge));
 	ASSERT(list_empty(&cache->useless_node));
-	ASSERT(list_empty(&cache->changed));
 	ASSERT(list_empty(&cache->detached));
 	ASSERT(RB_EMPTY_ROOT(&cache->rb_root));
 	ASSERT(!cache->nr_nodes);
diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h
index e8c22cccb5c1..a810253d7b8a 100644
--- a/fs/btrfs/backref.h
+++ b/fs/btrfs/backref.h
@@ -393,8 +393,6 @@ struct btrfs_backref_cache {
 	struct list_head pending[BTRFS_MAX_LEVEL];
 	/* List of backref nodes with no child node */
 	struct list_head leaves;
-	/* List of blocks that have been COWed in current transaction */
-	struct list_head changed;
 	/* List of detached backref node. */
 	struct list_head detached;
 
diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index 3c89e79d0259..ac3658dce6a3 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -2113,14 +2113,13 @@ struct btrfs_root *select_reloc_root(struct btrfs_trans_handle *trans,
 		if (next->new_bytenr != root->node->start) {
 			/*
 			 * We just created the reloc root, so we shouldn't have
-			 * ->new_bytenr set and this shouldn't be in the changed
-			 *  list.  If it is then we have multiple roots pointing
-			 *  at the same bytenr which indicates corruption, or
-			 *  we've made a mistake in the backref walking code.
+			 * ->new_bytenr set yet. If it is then we have multiple
+			 *  roots pointing at the same bytenr which indicates
+			 *  corruption, or we've made a mistake in the backref
+			 *  walking code.
 			 */
 			ASSERT(next->new_bytenr == 0);
-			ASSERT(list_empty(&next->list));
-			if (next->new_bytenr || !list_empty(&next->list)) {
+			if (next->new_bytenr) {
 				btrfs_err(trans->fs_info,
 	"bytenr %llu possibly has multiple roots pointing at the same bytenr %llu",
 					  node->bytenr, next->bytenr);
@@ -2131,8 +2130,6 @@ struct btrfs_root *select_reloc_root(struct btrfs_trans_handle *trans,
 			btrfs_put_root(next->root);
 			next->root = btrfs_grab_root(root);
 			ASSERT(next->root);
-			list_add_tail(&next->list,
-				      &rc->backref_cache.changed);
 			mark_block_processed(rc, next);
 			break;
 		}
@@ -2442,7 +2439,7 @@ static int do_relocation(struct btrfs_trans_handle *trans,
 
 	if (!ret && node->pending) {
 		btrfs_backref_drop_node_buffer(node);
-		list_move_tail(&node->list, &rc->backref_cache.changed);
+		list_del_init(&node->list);
 		node->pending = 0;
 	}
 
@@ -2605,8 +2602,7 @@ static int relocate_tree_block(struct btrfs_trans_handle *trans,
 			/*
 			 * This block was the root block of a root, and this is
 			 * the first time we're processing the block and thus it
-			 * should not have had the ->new_bytenr modified and
-			 * should have not been included on the changed list.
+			 * should not have had the ->new_bytenr modified.
 			 *
 			 * However in the case of corruption we could have
 			 * multiple refs pointing to the same block improperly,
@@ -2616,8 +2612,7 @@ static int relocate_tree_block(struct btrfs_trans_handle *trans,
 			 * normal user in the case of corruption.
 			 */
 			ASSERT(node->new_bytenr == 0);
-			ASSERT(list_empty(&node->list));
-			if (node->new_bytenr || !list_empty(&node->list)) {
+			if (node->new_bytenr) {
 				btrfs_err(root->fs_info,
 				  "bytenr %llu has improper references to it",
 					  node->bytenr);
@@ -2640,7 +2635,6 @@ static int relocate_tree_block(struct btrfs_trans_handle *trans,
 			btrfs_put_root(node->root);
 			node->root = btrfs_grab_root(root);
 			ASSERT(node->root);
-			list_add_tail(&node->list, &rc->backref_cache.changed);
 		} else {
 			path->lowest_level = node->level;
 			if (root == root->fs_info->chunk_root)
-- 
2.43.0

[PATCH 03/10] btrfs: add a comment for new_bytenr in bacref_cache_node

[Josef Bacik]

Add a comment for this field so we know what it is used for.  Previously
we used it to update the backref cache, so people may mistakenly think
it is useless, but in fact exists to make sure the backref cache makes
sense.

Signed-off-by: Josef Bacik <josef@toxicpanda.com>
---
 fs/btrfs/backref.h | 6 ++++++
 1 file changed, 6 insertions(+)

diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h
index a810253d7b8a..754c71bdc9ce 100644
--- a/fs/btrfs/backref.h
+++ b/fs/btrfs/backref.h
@@ -318,6 +318,12 @@ struct btrfs_backref_node {
 		u64 bytenr;
 	}; /* Use rb_simple_node for search/insert */
 
+	/*
+	 * This is a sanity check, whenever we cow a block we will update
+	 * new_bytenr with it's current location, and we will check this in
+	 * various places to validate that the cache makes sense, it shouldn't
+	 * be used for anything else.
+	 */
 	u64 new_bytenr;
 	/* Objectid of tree block owner, can be not uptodate */
 	u64 owner;
-- 
2.43.0

Re: [PATCH 03/10] btrfs: add a comment for new_bytenr in bacref_cache_node

[Boris Burkov]

On Thu, Oct 03, 2024 at 11:43:05AM -0400, Josef Bacik wrote:

s/bacref/backref/
in the commit title

> Add a comment for this field so we know what it is used for.  Previously
> we used it to update the backref cache, so people may mistakenly think
> it is useless, but in fact exists to make sure the backref cache makes
> sense.
> 
> Signed-off-by: Josef Bacik <josef@toxicpanda.com>
> ---
>  fs/btrfs/backref.h | 6 ++++++
>  1 file changed, 6 insertions(+)
> 
> diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h
> index a810253d7b8a..754c71bdc9ce 100644
> --- a/fs/btrfs/backref.h
> +++ b/fs/btrfs/backref.h
> @@ -318,6 +318,12 @@ struct btrfs_backref_node {
>  		u64 bytenr;
>  	}; /* Use rb_simple_node for search/insert */
>  
> +	/*
> +	 * This is a sanity check, whenever we cow a block we will update
> +	 * new_bytenr with it's current location, and we will check this in
> +	 * various places to validate that the cache makes sense, it shouldn't
> +	 * be used for anything else.
> +	 */
>  	u64 new_bytenr;
>  	/* Objectid of tree block owner, can be not uptodate */
>  	u64 owner;
> -- 
> 2.43.0
> 

[PATCH 04/10] btrfs: cleanup select_reloc_root

[Josef Bacik]

We have this setup as a loop, but in reality we will never walk back up
the backref tree, if we do then it's a bug.  Get rid of the loop and
handle the case where we have node->new_bytenr set at all.  Previous the
check was only if node->new_bytenr != root->node->start, but if it did
then we would hit the WARN_ON() and walk back up the tree.

Instead we want to just freak out if ->new_bytenr is set, and then do
the normal updating of the node for the reloc root and carry on.

Signed-off-by: Josef Bacik <josef@toxicpanda.com>
---
 fs/btrfs/relocation.c | 144 ++++++++++++++++++------------------------
 1 file changed, 61 insertions(+), 83 deletions(-)

diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index ac3658dce6a3..6b2308671d83 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -2058,97 +2058,75 @@ struct btrfs_root *select_reloc_root(struct btrfs_trans_handle *trans,
 	int index = 0;
 	int ret;
 
-	next = node;
-	while (1) {
-		cond_resched();
-		next = walk_up_backref(next, edges, &index);
-		root = next->root;
+	next = walk_up_backref(node, edges, &index);
+	root = next->root;
 
-		/*
-		 * If there is no root, then our references for this block are
-		 * incomplete, as we should be able to walk all the way up to a
-		 * block that is owned by a root.
-		 *
-		 * This path is only for SHAREABLE roots, so if we come upon a
-		 * non-SHAREABLE root then we have backrefs that resolve
-		 * improperly.
-		 *
-		 * Both of these cases indicate file system corruption, or a bug
-		 * in the backref walking code.
-		 */
-		if (!root) {
-			ASSERT(0);
-			btrfs_err(trans->fs_info,
-		"bytenr %llu doesn't have a backref path ending in a root",
-				  node->bytenr);
-			return ERR_PTR(-EUCLEAN);
-		}
-		if (!test_bit(BTRFS_ROOT_SHAREABLE, &root->state)) {
-			ASSERT(0);
-			btrfs_err(trans->fs_info,
-	"bytenr %llu has multiple refs with one ending in a non-shareable root",
-				  node->bytenr);
-			return ERR_PTR(-EUCLEAN);
-		}
+	/*
+	 * If there is no root, then our references for this block are
+	 * incomplete, as we should be able to walk all the way up to a block
+	 * that is owned by a root.
+	 *
+	 * This path is only for SHAREABLE roots, so if we come upon a
+	 * non-SHAREABLE root then we have backrefs that resolve improperly.
+	 *
+	 * Both of these cases indicate file system corruption, or a bug in the
+	 * backref walking code.
+	 */
+	if (!root) {
+		ASSERT(0);
+		btrfs_err(trans->fs_info,
+			  "bytenr %llu doesn't have a backref path ending in a root",
+			  node->bytenr);
+		return ERR_PTR(-EUCLEAN);
+	}
+	if (!test_bit(BTRFS_ROOT_SHAREABLE, &root->state)) {
+		ASSERT(0);
+		btrfs_err(trans->fs_info,
+			  "bytenr %llu has multiple refs with one ending in a non-shareable root",
+			  node->bytenr);
+		return ERR_PTR(-EUCLEAN);
+	}
 
-		if (btrfs_root_id(root) == BTRFS_TREE_RELOC_OBJECTID) {
-			ret = record_reloc_root_in_trans(trans, root);
-			if (ret)
-				return ERR_PTR(ret);
-			break;
-		}
-
-		ret = btrfs_record_root_in_trans(trans, root);
+	if (btrfs_root_id(root) == BTRFS_TREE_RELOC_OBJECTID) {
+		ret = record_reloc_root_in_trans(trans, root);
 		if (ret)
 			return ERR_PTR(ret);
-		root = root->reloc_root;
-
-		/*
-		 * We could have raced with another thread which failed, so
-		 * root->reloc_root may not be set, return ENOENT in this case.
-		 */
-		if (!root)
-			return ERR_PTR(-ENOENT);
-
-		if (next->new_bytenr != root->node->start) {
-			/*
-			 * We just created the reloc root, so we shouldn't have
-			 * ->new_bytenr set yet. If it is then we have multiple
-			 *  roots pointing at the same bytenr which indicates
-			 *  corruption, or we've made a mistake in the backref
-			 *  walking code.
-			 */
-			ASSERT(next->new_bytenr == 0);
-			if (next->new_bytenr) {
-				btrfs_err(trans->fs_info,
-	"bytenr %llu possibly has multiple roots pointing at the same bytenr %llu",
-					  node->bytenr, next->bytenr);
-				return ERR_PTR(-EUCLEAN);
-			}
-
-			next->new_bytenr = root->node->start;
-			btrfs_put_root(next->root);
-			next->root = btrfs_grab_root(root);
-			ASSERT(next->root);
-			mark_block_processed(rc, next);
-			break;
-		}
-
-		WARN_ON(1);
-		root = NULL;
-		next = walk_down_backref(edges, &index);
-		if (!next || next->level <= node->level)
-			break;
+		goto found;
 	}
-	if (!root) {
-		/*
-		 * This can happen if there's fs corruption or if there's a bug
-		 * in the backref lookup code.
-		 */
-		ASSERT(0);
+
+	ret = btrfs_record_root_in_trans(trans, root);
+	if (ret)
+		return ERR_PTR(ret);
+	root = root->reloc_root;
+
+	/*
+	 * We could have raced with another thread which failed, so
+	 * root->reloc_root may not be set, return ENOENT in this case.
+	 */
+	if (!root)
 		return ERR_PTR(-ENOENT);
+
+	if (next->new_bytenr) {
+		/*
+		 * We just created the reloc root, so we shouldn't have
+		 * ->new_bytenr set yet. If it is then we have multiple
+		 * roots pointing at the same bytenr which indicates
+		 * corruption, or we've made a mistake in the backref
+		 * walking code.
+		 */
+		ASSERT(next->new_bytenr == 0);
+		btrfs_err(trans->fs_info,
+			  "bytenr %llu possibly has multiple roots pointing at the same bytenr %llu",
+			  node->bytenr, next->bytenr);
+		return ERR_PTR(-EUCLEAN);
 	}
 
+	next->new_bytenr = root->node->start;
+	btrfs_put_root(next->root);
+	next->root = btrfs_grab_root(root);
+	ASSERT(next->root);
+	mark_block_processed(rc, next);
+found:
 	next = node;
 	/* setup backref node path for btrfs_reloc_cow_block */
 	while (1) {
-- 
2.43.0

Re: [PATCH 04/10] btrfs: cleanup select_reloc_root

[Boris Burkov]

On Thu, Oct 03, 2024 at 11:43:06AM -0400, Josef Bacik wrote:
> We have this setup as a loop, but in reality we will never walk back up
> the backref tree, if we do then it's a bug.  Get rid of the loop and
> handle the case where we have node->new_bytenr set at all.  Previous the
> check was only if node->new_bytenr != root->node->start, but if it did
> then we would hit the WARN_ON() and walk back up the tree.
> 
> Instead we want to just freak out if ->new_bytenr is set, and then do
> the normal updating of the node for the reloc root and carry on.
> 
> Signed-off-by: Josef Bacik <josef@toxicpanda.com>
> ---
>  fs/btrfs/relocation.c | 144 ++++++++++++++++++------------------------
>  1 file changed, 61 insertions(+), 83 deletions(-)
> 
> diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
> index ac3658dce6a3..6b2308671d83 100644
> --- a/fs/btrfs/relocation.c
> +++ b/fs/btrfs/relocation.c

I think this (and most other functions in backref caching) could really
benefit from some description of their invariants. I think that will pay
its weight in gold if we ever have to read this code again in 10
years...

> @@ -2058,97 +2058,75 @@ struct btrfs_root *select_reloc_root(struct btrfs_trans_handle *trans,
>  	int index = 0;
>  	int ret;
>  
> -	next = node;
> -	while (1) {
> -		cond_resched();
> -		next = walk_up_backref(next, edges, &index);
> -		root = next->root;
> +	next = walk_up_backref(node, edges, &index);
> +	root = next->root;
>  
> -		/*
> -		 * If there is no root, then our references for this block are
> -		 * incomplete, as we should be able to walk all the way up to a
> -		 * block that is owned by a root.
> -		 *
> -		 * This path is only for SHAREABLE roots, so if we come upon a
> -		 * non-SHAREABLE root then we have backrefs that resolve
> -		 * improperly.
> -		 *
> -		 * Both of these cases indicate file system corruption, or a bug
> -		 * in the backref walking code.
> -		 */
> -		if (!root) {
> -			ASSERT(0);
> -			btrfs_err(trans->fs_info,
> -		"bytenr %llu doesn't have a backref path ending in a root",
> -				  node->bytenr);
> -			return ERR_PTR(-EUCLEAN);
> -		}
> -		if (!test_bit(BTRFS_ROOT_SHAREABLE, &root->state)) {
> -			ASSERT(0);
> -			btrfs_err(trans->fs_info,
> -	"bytenr %llu has multiple refs with one ending in a non-shareable root",
> -				  node->bytenr);
> -			return ERR_PTR(-EUCLEAN);
> -		}
> +	/*
> +	 * If there is no root, then our references for this block are
> +	 * incomplete, as we should be able to walk all the way up to a block
> +	 * that is owned by a root.
> +	 *
> +	 * This path is only for SHAREABLE roots, so if we come upon a
> +	 * non-SHAREABLE root then we have backrefs that resolve improperly.
> +	 *
> +	 * Both of these cases indicate file system corruption, or a bug in the
> +	 * backref walking code.
> +	 */
> +	if (!root) {
> +		ASSERT(0);
> +		btrfs_err(trans->fs_info,
> +			  "bytenr %llu doesn't have a backref path ending in a root",
> +			  node->bytenr);
> +		return ERR_PTR(-EUCLEAN);
> +	}
> +	if (!test_bit(BTRFS_ROOT_SHAREABLE, &root->state)) {
> +		ASSERT(0);
> +		btrfs_err(trans->fs_info,
> +			  "bytenr %llu has multiple refs with one ending in a non-shareable root",
> +			  node->bytenr);
> +		return ERR_PTR(-EUCLEAN);
> +	}
>  
> -		if (btrfs_root_id(root) == BTRFS_TREE_RELOC_OBJECTID) {
> -			ret = record_reloc_root_in_trans(trans, root);
> -			if (ret)
> -				return ERR_PTR(ret);
> -			break;
> -		}
> -
> -		ret = btrfs_record_root_in_trans(trans, root);
> +	if (btrfs_root_id(root) == BTRFS_TREE_RELOC_OBJECTID) {
> +		ret = record_reloc_root_in_trans(trans, root);
>  		if (ret)
>  			return ERR_PTR(ret);
> -		root = root->reloc_root;
> -
> -		/*
> -		 * We could have raced with another thread which failed, so
> -		 * root->reloc_root may not be set, return ENOENT in this case.
> -		 */
> -		if (!root)
> -			return ERR_PTR(-ENOENT);
> -
> -		if (next->new_bytenr != root->node->start) {
> -			/*
> -			 * We just created the reloc root, so we shouldn't have
> -			 * ->new_bytenr set yet. If it is then we have multiple
> -			 *  roots pointing at the same bytenr which indicates
> -			 *  corruption, or we've made a mistake in the backref
> -			 *  walking code.
> -			 */
> -			ASSERT(next->new_bytenr == 0);
> -			if (next->new_bytenr) {
> -				btrfs_err(trans->fs_info,
> -	"bytenr %llu possibly has multiple roots pointing at the same bytenr %llu",
> -					  node->bytenr, next->bytenr);
> -				return ERR_PTR(-EUCLEAN);
> -			}
> -
> -			next->new_bytenr = root->node->start;
> -			btrfs_put_root(next->root);
> -			next->root = btrfs_grab_root(root);
> -			ASSERT(next->root);
> -			mark_block_processed(rc, next);
> -			break;
> -		}
> -
> -		WARN_ON(1);
> -		root = NULL;
> -		next = walk_down_backref(edges, &index);
> -		if (!next || next->level <= node->level)
> -			break;
> +		goto found;
>  	}
> -	if (!root) {
> -		/*
> -		 * This can happen if there's fs corruption or if there's a bug
> -		 * in the backref lookup code.
> -		 */
> -		ASSERT(0);
> +
> +	ret = btrfs_record_root_in_trans(trans, root);
> +	if (ret)
> +		return ERR_PTR(ret);
> +	root = root->reloc_root;
> +
> +	/*
> +	 * We could have raced with another thread which failed, so
> +	 * root->reloc_root may not be set, return ENOENT in this case.
> +	 */
> +	if (!root)
>  		return ERR_PTR(-ENOENT);
> +
> +	if (next->new_bytenr) {
> +		/*
> +		 * We just created the reloc root, so we shouldn't have
> +		 * ->new_bytenr set yet. If it is then we have multiple
> +		 * roots pointing at the same bytenr which indicates
> +		 * corruption, or we've made a mistake in the backref
> +		 * walking code.
> +		 */
> +		ASSERT(next->new_bytenr == 0);
> +		btrfs_err(trans->fs_info,
> +			  "bytenr %llu possibly has multiple roots pointing at the same bytenr %llu",
> +			  node->bytenr, next->bytenr);
> +		return ERR_PTR(-EUCLEAN);
>  	}
>  
> +	next->new_bytenr = root->node->start;
> +	btrfs_put_root(next->root);
> +	next->root = btrfs_grab_root(root);
> +	ASSERT(next->root);
> +	mark_block_processed(rc, next);
> +found:
>  	next = node;
>  	/* setup backref node path for btrfs_reloc_cow_block */
>  	while (1) {
> -- 
> 2.43.0
> 

[PATCH 05/10] btrfs: remove clone_backref_node

[Josef Bacik]

Since we no longer maintain backref cache across transactions, and this
is only called when we're creating the reloc root for a newly created
snapshot in the transaction critical section, we will end up doing a
bunch of work that will just get thrown away when we start the
transaction in the relocation loop.  Delete this code as it no longer
does anything for us.

Signed-off-by: Josef Bacik <josef@toxicpanda.com>
---
 fs/btrfs/relocation.c | 91 +------------------------------------------
 1 file changed, 1 insertion(+), 90 deletions(-)

diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index 6b2308671d83..7de94e55234c 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -469,92 +469,6 @@ static noinline_for_stack struct btrfs_backref_node *build_backref_tree(
 	return node;
 }
 
-/*
- * helper to add backref node for the newly created snapshot.
- * the backref node is created by cloning backref node that
- * corresponds to root of source tree
- */
-static int clone_backref_node(struct btrfs_trans_handle *trans,
-			      struct reloc_control *rc,
-			      const struct btrfs_root *src,
-			      struct btrfs_root *dest)
-{
-	struct btrfs_root *reloc_root = src->reloc_root;
-	struct btrfs_backref_cache *cache = &rc->backref_cache;
-	struct btrfs_backref_node *node = NULL;
-	struct btrfs_backref_node *new_node;
-	struct btrfs_backref_edge *edge;
-	struct btrfs_backref_edge *new_edge;
-	struct rb_node *rb_node;
-
-	rb_node = rb_simple_search(&cache->rb_root, src->commit_root->start);
-	if (rb_node) {
-		node = rb_entry(rb_node, struct btrfs_backref_node, rb_node);
-		if (node->detached)
-			node = NULL;
-		else
-			BUG_ON(node->new_bytenr != reloc_root->node->start);
-	}
-
-	if (!node) {
-		rb_node = rb_simple_search(&cache->rb_root,
-					   reloc_root->commit_root->start);
-		if (rb_node) {
-			node = rb_entry(rb_node, struct btrfs_backref_node,
-					rb_node);
-			BUG_ON(node->detached);
-		}
-	}
-
-	if (!node)
-		return 0;
-
-	new_node = btrfs_backref_alloc_node(cache, dest->node->start,
-					    node->level);
-	if (!new_node)
-		return -ENOMEM;
-
-	new_node->lowest = node->lowest;
-	new_node->checked = 1;
-	new_node->root = btrfs_grab_root(dest);
-	ASSERT(new_node->root);
-
-	if (!node->lowest) {
-		list_for_each_entry(edge, &node->lower, list[UPPER]) {
-			new_edge = btrfs_backref_alloc_edge(cache);
-			if (!new_edge)
-				goto fail;
-
-			btrfs_backref_link_edge(new_edge, edge->node[LOWER],
-						new_node, LINK_UPPER);
-		}
-	} else {
-		list_add_tail(&new_node->lower, &cache->leaves);
-	}
-
-	rb_node = rb_simple_insert(&cache->rb_root, new_node->bytenr,
-				   &new_node->rb_node);
-	if (rb_node)
-		btrfs_backref_panic(trans->fs_info, new_node->bytenr, -EEXIST);
-
-	if (!new_node->lowest) {
-		list_for_each_entry(new_edge, &new_node->lower, list[UPPER]) {
-			list_add_tail(&new_edge->list[LOWER],
-				      &new_edge->node[LOWER]->upper);
-		}
-	}
-	return 0;
-fail:
-	while (!list_empty(&new_node->lower)) {
-		new_edge = list_entry(new_node->lower.next,
-				      struct btrfs_backref_edge, list[UPPER]);
-		list_del(&new_edge->list[UPPER]);
-		btrfs_backref_free_edge(cache, new_edge);
-	}
-	btrfs_backref_free_node(cache, new_node);
-	return -ENOMEM;
-}
-
 /*
  * helper to add 'address of tree root -> reloc tree' mapping
  */
@@ -4484,10 +4398,7 @@ int btrfs_reloc_post_snapshot(struct btrfs_trans_handle *trans,
 		return ret;
 	}
 	new_root->reloc_root = btrfs_grab_root(reloc_root);
-
-	if (rc->create_reloc_tree)
-		ret = clone_backref_node(trans, rc, root, reloc_root);
-	return ret;
+	return 0;
 }
 
 /*
-- 
2.43.0

[PATCH 06/10] btrfs: don't build backref tree for cowonly blocks

[Josef Bacik]

We already determine the owner for any blocks we find when we're
relocating, and for cowonly blocks (and the data reloc tree) we cow down
to the block and call it good enough.  However we still build a whole
backref tree for them, even though we're not going to use it, and then
just don't put these blocks in the cache.

Rework the code to check if the block belongs to a cowonly root or the
data reloc root, and then just cow down to the block, skipping the
backref cache generation.

Signed-off-by: Josef Bacik <josef@toxicpanda.com>
---
 fs/btrfs/relocation.c | 89 ++++++++++++++++++++++++++++++++++---------
 1 file changed, 70 insertions(+), 19 deletions(-)

diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index 7de94e55234c..db5f6bda93c9 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -2136,17 +2136,11 @@ static noinline_for_stack u64 calcu_metadata_size(struct reloc_control *rc,
 	return num_bytes;
 }
 
-static int reserve_metadata_space(struct btrfs_trans_handle *trans,
-				  struct reloc_control *rc,
-				  struct btrfs_backref_node *node)
+static int refill_metadata_space(struct btrfs_trans_handle *trans,
+				 struct reloc_control *rc, u64 num_bytes)
 {
-	struct btrfs_root *root = rc->extent_root;
-	struct btrfs_fs_info *fs_info = root->fs_info;
-	u64 num_bytes;
+	struct btrfs_fs_info *fs_info = trans->fs_info;
 	int ret;
-	u64 tmp;
-
-	num_bytes = calcu_metadata_size(rc, node) * 2;
 
 	trans->block_rsv = rc->block_rsv;
 	rc->reserved_bytes += num_bytes;
@@ -2159,7 +2153,7 @@ static int reserve_metadata_space(struct btrfs_trans_handle *trans,
 	ret = btrfs_block_rsv_refill(fs_info, rc->block_rsv, num_bytes,
 				     BTRFS_RESERVE_FLUSH_LIMIT);
 	if (ret) {
-		tmp = fs_info->nodesize * RELOCATION_RESERVED_NODES;
+		u64 tmp = fs_info->nodesize * RELOCATION_RESERVED_NODES;
 		while (tmp <= rc->reserved_bytes)
 			tmp <<= 1;
 		/*
@@ -2177,6 +2171,16 @@ static int reserve_metadata_space(struct btrfs_trans_handle *trans,
 	return 0;
 }
 
+static int reserve_metadata_space(struct btrfs_trans_handle *trans,
+				  struct reloc_control *rc,
+				  struct btrfs_backref_node *node)
+{
+	u64 num_bytes;
+
+	num_bytes = calcu_metadata_size(rc, node) * 2;
+	return refill_metadata_space(trans, rc, num_bytes);
+}
+
 /*
  * relocate a block tree, and then update pointers in upper level
  * blocks that reference the block to point to the new location.
@@ -2528,15 +2532,11 @@ static int relocate_tree_block(struct btrfs_trans_handle *trans,
 			node->root = btrfs_grab_root(root);
 			ASSERT(node->root);
 		} else {
-			path->lowest_level = node->level;
-			if (root == root->fs_info->chunk_root)
-				btrfs_reserve_chunk_metadata(trans, false);
-			ret = btrfs_search_slot(trans, root, key, path, 0, 1);
-			btrfs_release_path(path);
-			if (root == root->fs_info->chunk_root)
-				btrfs_trans_release_chunk_metadata(trans);
-			if (ret > 0)
-				ret = 0;
+			btrfs_err(root->fs_info,
+				  "bytenr %llu resolved to a non-shareable root",
+				  node->bytenr);
+			ret = -EUCLEAN;
+			goto out;
 		}
 		if (!ret)
 			update_processed_blocks(rc, node);
@@ -2549,6 +2549,43 @@ static int relocate_tree_block(struct btrfs_trans_handle *trans,
 	return ret;
 }
 
+static noinline_for_stack
+int relocate_cowonly_block(struct btrfs_trans_handle *trans,
+			   struct reloc_control *rc, struct tree_block *block,
+			   struct btrfs_path *path)
+{
+	struct btrfs_fs_info *fs_info = trans->fs_info;
+	struct btrfs_root *root;
+	u64 num_bytes;
+	int nr_levels;
+	int ret;
+
+	root = btrfs_get_fs_root(fs_info, block->owner, true);
+	if (IS_ERR(root))
+		return PTR_ERR(root);
+
+	nr_levels = max(btrfs_header_level(root->node) - block->level, 0) + 1;
+
+	num_bytes = fs_info->nodesize * nr_levels;
+	ret = refill_metadata_space(trans, rc, num_bytes);
+	if (ret) {
+		btrfs_put_root(root);
+		return ret;
+	}
+	path->lowest_level = block->level;
+	if (root == root->fs_info->chunk_root)
+		btrfs_reserve_chunk_metadata(trans, false);
+	ret = btrfs_search_slot(trans, root, &block->key, path, 0, 1);
+	path->lowest_level = 0;
+	btrfs_release_path(path);
+	if (root == root->fs_info->chunk_root)
+		btrfs_trans_release_chunk_metadata(trans);
+	if (ret > 0)
+		ret = 0;
+	btrfs_put_root(root);
+	return ret;
+}
+
 /*
  * relocate a list of blocks
  */
@@ -2588,6 +2625,20 @@ int relocate_tree_blocks(struct btrfs_trans_handle *trans,
 
 	/* Do tree relocation */
 	rbtree_postorder_for_each_entry_safe(block, next, blocks, rb_node) {
+		/*
+		 * For cowonly blocks, or the data reloc tree, we only need to
+		 * cow down to the block, there's no need to generate a backref
+		 * tree.
+		 */
+		if (block->owner &&
+		    (!is_fstree(block->owner) ||
+		     block->owner == BTRFS_DATA_RELOC_TREE_OBJECTID)) {
+			ret = relocate_cowonly_block(trans, rc, block, path);
+			if (ret)
+				break;
+			continue;
+		}
+
 		node = build_backref_tree(trans, rc, &block->key,
 					  block->level, block->bytenr);
 		if (IS_ERR(node)) {
-- 
2.43.0

Re: [PATCH 06/10] btrfs: don't build backref tree for cowonly blocks

[Boris Burkov]

On Thu, Oct 03, 2024 at 11:43:08AM -0400, Josef Bacik wrote:
> We already determine the owner for any blocks we find when we're
> relocating, and for cowonly blocks (and the data reloc tree) we cow down
> to the block and call it good enough.  However we still build a whole
> backref tree for them, even though we're not going to use it, and then
> just don't put these blocks in the cache.
> 
> Rework the code to check if the block belongs to a cowonly root or the
> data reloc root, and then just cow down to the block, skipping the
> backref cache generation.
> 
> Signed-off-by: Josef Bacik <josef@toxicpanda.com>
> ---
>  fs/btrfs/relocation.c | 89 ++++++++++++++++++++++++++++++++++---------
>  1 file changed, 70 insertions(+), 19 deletions(-)
> 
> diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
> index 7de94e55234c..db5f6bda93c9 100644
> --- a/fs/btrfs/relocation.c
> +++ b/fs/btrfs/relocation.c
> @@ -2136,17 +2136,11 @@ static noinline_for_stack u64 calcu_metadata_size(struct reloc_control *rc,
>  	return num_bytes;
>  }
>  
> -static int reserve_metadata_space(struct btrfs_trans_handle *trans,
> -				  struct reloc_control *rc,
> -				  struct btrfs_backref_node *node)
> +static int refill_metadata_space(struct btrfs_trans_handle *trans,
> +				 struct reloc_control *rc, u64 num_bytes)
>  {
> -	struct btrfs_root *root = rc->extent_root;
> -	struct btrfs_fs_info *fs_info = root->fs_info;
> -	u64 num_bytes;
> +	struct btrfs_fs_info *fs_info = trans->fs_info;
>  	int ret;
> -	u64 tmp;
> -
> -	num_bytes = calcu_metadata_size(rc, node) * 2;
>  
>  	trans->block_rsv = rc->block_rsv;
>  	rc->reserved_bytes += num_bytes;
> @@ -2159,7 +2153,7 @@ static int reserve_metadata_space(struct btrfs_trans_handle *trans,
>  	ret = btrfs_block_rsv_refill(fs_info, rc->block_rsv, num_bytes,
>  				     BTRFS_RESERVE_FLUSH_LIMIT);
>  	if (ret) {
> -		tmp = fs_info->nodesize * RELOCATION_RESERVED_NODES;
> +		u64 tmp = fs_info->nodesize * RELOCATION_RESERVED_NODES;
>  		while (tmp <= rc->reserved_bytes)
>  			tmp <<= 1;
>  		/*
> @@ -2177,6 +2171,16 @@ static int reserve_metadata_space(struct btrfs_trans_handle *trans,
>  	return 0;
>  }
>  
> +static int reserve_metadata_space(struct btrfs_trans_handle *trans,
> +				  struct reloc_control *rc,
> +				  struct btrfs_backref_node *node)
> +{
> +	u64 num_bytes;
> +
> +	num_bytes = calcu_metadata_size(rc, node) * 2;
> +	return refill_metadata_space(trans, rc, num_bytes);
> +}
> +
>  /*
>   * relocate a block tree, and then update pointers in upper level
>   * blocks that reference the block to point to the new location.
> @@ -2528,15 +2532,11 @@ static int relocate_tree_block(struct btrfs_trans_handle *trans,
>  			node->root = btrfs_grab_root(root);
>  			ASSERT(node->root);
>  		} else {
> -			path->lowest_level = node->level;
> -			if (root == root->fs_info->chunk_root)
> -				btrfs_reserve_chunk_metadata(trans, false);
> -			ret = btrfs_search_slot(trans, root, key, path, 0, 1);
> -			btrfs_release_path(path);
> -			if (root == root->fs_info->chunk_root)
> -				btrfs_trans_release_chunk_metadata(trans);
> -			if (ret > 0)
> -				ret = 0;
> +			btrfs_err(root->fs_info,
> +				  "bytenr %llu resolved to a non-shareable root",
> +				  node->bytenr);
> +			ret = -EUCLEAN;
> +			goto out;
>  		}
>  		if (!ret)
>  			update_processed_blocks(rc, node);
> @@ -2549,6 +2549,43 @@ static int relocate_tree_block(struct btrfs_trans_handle *trans,
>  	return ret;
>  }
>  
> +static noinline_for_stack
> +int relocate_cowonly_block(struct btrfs_trans_handle *trans,
> +			   struct reloc_control *rc, struct tree_block *block,
> +			   struct btrfs_path *path)
> +{
> +	struct btrfs_fs_info *fs_info = trans->fs_info;
> +	struct btrfs_root *root;
> +	u64 num_bytes;
> +	int nr_levels;
> +	int ret;
> +
> +	root = btrfs_get_fs_root(fs_info, block->owner, true);
> +	if (IS_ERR(root))
> +		return PTR_ERR(root);
> +
> +	nr_levels = max(btrfs_header_level(root->node) - block->level, 0) + 1;
> +
> +	num_bytes = fs_info->nodesize * nr_levels;
> +	ret = refill_metadata_space(trans, rc, num_bytes);
> +	if (ret) {
> +		btrfs_put_root(root);
> +		return ret;
> +	}
> +	path->lowest_level = block->level;
> +	if (root == root->fs_info->chunk_root)
> +		btrfs_reserve_chunk_metadata(trans, false);
> +	ret = btrfs_search_slot(trans, root, &block->key, path, 0, 1);
> +	path->lowest_level = 0;
> +	btrfs_release_path(path);
> +	if (root == root->fs_info->chunk_root)
> +		btrfs_trans_release_chunk_metadata(trans);
> +	if (ret > 0)
> +		ret = 0;
> +	btrfs_put_root(root);
> +	return ret;
> +}
> +
>  /*
>   * relocate a list of blocks
>   */
> @@ -2588,6 +2625,20 @@ int relocate_tree_blocks(struct btrfs_trans_handle *trans,
>  
>  	/* Do tree relocation */
>  	rbtree_postorder_for_each_entry_safe(block, next, blocks, rb_node) {
> +		/*
> +		 * For cowonly blocks, or the data reloc tree, we only need to
> +		 * cow down to the block, there's no need to generate a backref
> +		 * tree.
> +		 */
> +		if (block->owner &&
> +		    (!is_fstree(block->owner) ||
> +		     block->owner == BTRFS_DATA_RELOC_TREE_OBJECTID)) {

would it make sense to capture this (and probably other conditions using
roots instead of backref cache blocks) into a named cowonly concept?

> +			ret = relocate_cowonly_block(trans, rc, block, path);
> +			if (ret)
> +				break;
> +			continue;
> +		}
> +
>  		node = build_backref_tree(trans, rc, &block->key,
>  					  block->level, block->bytenr);
>  		if (IS_ERR(node)) {
> -- 
> 2.43.0
> 

[PATCH 07/10] btrfs: do not handle non-shareable roots in backref cache

[Josef Bacik]

Now that we handle relocation for non-shareable roots without using the
backref cache, remove the ->cowonly field from the backref nodes and
update the handling to throw an ASSERT()/error.

Signed-off-by: Josef Bacik <josef@toxicpanda.com>
---
 fs/btrfs/backref.c    | 62 ++++++++++++++++++++++++-------------------
 fs/btrfs/backref.h    |  2 --
 fs/btrfs/relocation.c |  2 +-
 3 files changed, 36 insertions(+), 30 deletions(-)

diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index 881bb5600b55..9c011ccd7209 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -3313,8 +3313,16 @@ static int handle_indirect_tree_backref(struct btrfs_trans_handle *trans,
 	root = btrfs_get_fs_root(fs_info, ref_key->offset, false);
 	if (IS_ERR(root))
 		return PTR_ERR(root);
-	if (!test_bit(BTRFS_ROOT_SHAREABLE, &root->state))
-		cur->cowonly = 1;
+
+	/*
+	 * We shouldn't be using backref cache for non shareable roots, ASSERT
+	 * for developers, return -EUCLEAN for users.
+	 */
+	if (!test_bit(BTRFS_ROOT_SHAREABLE, &root->state)) {
+		btrfs_put_root(root);
+		ASSERT(0);
+		return -EUCLEAN;
+	}
 
 	if (btrfs_root_level(&root->root_item) == cur->level) {
 		/* Tree root */
@@ -3400,8 +3408,20 @@ static int handle_indirect_tree_backref(struct btrfs_trans_handle *trans,
 				goto out;
 			}
 			upper->owner = btrfs_header_owner(eb);
-			if (!test_bit(BTRFS_ROOT_SHAREABLE, &root->state))
-				upper->cowonly = 1;
+
+			/*
+			 * We shouldn't be using backref cache for non shareable
+			 * roots, ASSERT for developers, return -EUCLEAN for
+			 * users.
+			 */
+			if (!test_bit(BTRFS_ROOT_SHAREABLE, &root->state)) {
+				btrfs_put_root(root);
+				btrfs_backref_free_edge(cache, edge);
+				btrfs_backref_free_node(cache, upper);
+				ASSERT(0);
+				ret = -EUCLEAN;
+				goto out;
+			}
 
 			/*
 			 * If we know the block isn't shared we can avoid
@@ -3592,15 +3612,12 @@ int btrfs_backref_finish_upper_links(struct btrfs_backref_cache *cache,
 
 	ASSERT(start->checked);
 
-	/* Insert this node to cache if it's not COW-only */
-	if (!start->cowonly) {
-		rb_node = rb_simple_insert(&cache->rb_root, start->bytenr,
-					   &start->rb_node);
-		if (rb_node)
-			btrfs_backref_panic(cache->fs_info, start->bytenr,
-					    -EEXIST);
-		list_add_tail(&start->lower, &cache->leaves);
-	}
+	rb_node = rb_simple_insert(&cache->rb_root, start->bytenr,
+				   &start->rb_node);
+	if (rb_node)
+		btrfs_backref_panic(cache->fs_info, start->bytenr,
+				    -EEXIST);
+	list_add_tail(&start->lower, &cache->leaves);
 
 	/*
 	 * Use breadth first search to iterate all related edges.
@@ -3654,23 +3671,14 @@ int btrfs_backref_finish_upper_links(struct btrfs_backref_cache *cache,
 			return -EUCLEAN;
 		}
 
-		/* Sanity check, COW-only node has non-COW-only parent */
-		if (start->cowonly != upper->cowonly) {
-			ASSERT(0);
+		rb_node = rb_simple_insert(&cache->rb_root, upper->bytenr,
+					   &upper->rb_node);
+		if (rb_node) {
+			btrfs_backref_panic(cache->fs_info,
+					    upper->bytenr, -EEXIST);
 			return -EUCLEAN;
 		}
 
-		/* Only cache non-COW-only (subvolume trees) tree blocks */
-		if (!upper->cowonly) {
-			rb_node = rb_simple_insert(&cache->rb_root, upper->bytenr,
-						   &upper->rb_node);
-			if (rb_node) {
-				btrfs_backref_panic(cache->fs_info,
-						upper->bytenr, -EEXIST);
-				return -EUCLEAN;
-			}
-		}
-
 		list_add_tail(&edge->list[UPPER], &upper->lower);
 
 		/*
diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h
index 754c71bdc9ce..6c27c070025a 100644
--- a/fs/btrfs/backref.h
+++ b/fs/btrfs/backref.h
@@ -341,8 +341,6 @@ struct btrfs_backref_node {
 	struct extent_buffer *eb;
 	/* Level of the tree block */
 	unsigned int level:8;
-	/* Is the block in a non-shareable tree */
-	unsigned int cowonly:1;
 	/* 1 if no child node is in the cache */
 	unsigned int lowest:1;
 	/* Is the extent buffer locked */
diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index db5f6bda93c9..507fcc3f56e6 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -2544,7 +2544,7 @@ static int relocate_tree_block(struct btrfs_trans_handle *trans,
 		ret = do_relocation(trans, rc, node, key, path, 1);
 	}
 out:
-	if (ret || node->level == 0 || node->cowonly)
+	if (ret || node->level == 0)
 		btrfs_backref_cleanup_node(&rc->backref_cache, node);
 	return ret;
 }
-- 
2.43.0

[PATCH 08/10] btrfs: simplify btrfs_backref_release_cache

[Josef Bacik]

We rely on finding all our nodes on the various lists in the backref
cache, when they are all also in the rbtree.  Instead just search
through the rbtree and free everything.

Signed-off-by: Josef Bacik <josef@toxicpanda.com>
---
 fs/btrfs/backref.c | 22 ++--------------------
 1 file changed, 2 insertions(+), 20 deletions(-)

diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index 9c011ccd7209..a7462d7f2531 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -3164,32 +3164,14 @@ void btrfs_backref_cleanup_node(struct btrfs_backref_cache *cache,
 void btrfs_backref_release_cache(struct btrfs_backref_cache *cache)
 {
 	struct btrfs_backref_node *node;
-	int i;
 
-	while (!list_empty(&cache->detached)) {
-		node = list_entry(cache->detached.next,
-				  struct btrfs_backref_node, list);
+	while ((node = rb_entry_safe(rb_first(&cache->rb_root),
+				     struct btrfs_backref_node, rb_node)))
 		btrfs_backref_cleanup_node(cache, node);
-	}
 
-	while (!list_empty(&cache->leaves)) {
-		node = list_entry(cache->leaves.next,
-				  struct btrfs_backref_node, lower);
-		btrfs_backref_cleanup_node(cache, node);
-	}
-
-	for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
-		while (!list_empty(&cache->pending[i])) {
-			node = list_first_entry(&cache->pending[i],
-						struct btrfs_backref_node,
-						list);
-			btrfs_backref_cleanup_node(cache, node);
-		}
-	}
 	ASSERT(list_empty(&cache->pending_edge));
 	ASSERT(list_empty(&cache->useless_node));
 	ASSERT(list_empty(&cache->detached));
-	ASSERT(RB_EMPTY_ROOT(&cache->rb_root));
 	ASSERT(!cache->nr_nodes);
 	ASSERT(!cache->nr_edges);
 }
-- 
2.43.0

[PATCH 09/10] btrfs: remove the ->lowest and ->leaves members from backref cache

[Josef Bacik]

Before we were keeping all of our nodes on various lists in order to
make sure everything got cleaned up correctly.  We used node->lowest to
indicate that node->lower was linked into the cache->leaves list.  Now
that we do cleanup based on the rb tree both the list and the flag are
useless, so delete them both.

Signed-off-by: Josef Bacik <josef@toxicpanda.com>
---
 fs/btrfs/backref.c    | 19 -------------------
 fs/btrfs/backref.h    |  4 ----
 fs/btrfs/relocation.c |  7 -------
 3 files changed, 30 deletions(-)

diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index a7462d7f2531..5e7d41a8efdb 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -3022,7 +3022,6 @@ void btrfs_backref_init_cache(struct btrfs_fs_info *fs_info,
 	for (i = 0; i < BTRFS_MAX_LEVEL; i++)
 		INIT_LIST_HEAD(&cache->pending[i]);
 	INIT_LIST_HEAD(&cache->detached);
-	INIT_LIST_HEAD(&cache->leaves);
 	INIT_LIST_HEAD(&cache->pending_edge);
 	INIT_LIST_HEAD(&cache->useless_node);
 	cache->fs_info = fs_info;
@@ -3130,29 +3129,17 @@ void btrfs_backref_drop_node(struct btrfs_backref_cache *tree,
 void btrfs_backref_cleanup_node(struct btrfs_backref_cache *cache,
 				struct btrfs_backref_node *node)
 {
-	struct btrfs_backref_node *upper;
 	struct btrfs_backref_edge *edge;
 
 	if (!node)
 		return;
 
-	BUG_ON(!node->lowest && !node->detached);
 	while (!list_empty(&node->upper)) {
 		edge = list_entry(node->upper.next, struct btrfs_backref_edge,
 				  list[LOWER]);
-		upper = edge->node[UPPER];
 		list_del(&edge->list[LOWER]);
 		list_del(&edge->list[UPPER]);
 		btrfs_backref_free_edge(cache, edge);
-
-		/*
-		 * Add the node to leaf node list if no other child block
-		 * cached.
-		 */
-		if (list_empty(&upper->lower)) {
-			list_add_tail(&upper->lower, &cache->leaves);
-			upper->lowest = 1;
-		}
 	}
 
 	btrfs_backref_drop_node(cache, node);
@@ -3599,7 +3586,6 @@ int btrfs_backref_finish_upper_links(struct btrfs_backref_cache *cache,
 	if (rb_node)
 		btrfs_backref_panic(cache->fs_info, start->bytenr,
 				    -EEXIST);
-	list_add_tail(&start->lower, &cache->leaves);
 
 	/*
 	 * Use breadth first search to iterate all related edges.
@@ -3638,11 +3624,6 @@ int btrfs_backref_finish_upper_links(struct btrfs_backref_cache *cache,
 		 * parents have already been linked.
 		 */
 		if (!RB_EMPTY_NODE(&upper->rb_node)) {
-			if (upper->lowest) {
-				list_del_init(&upper->lower);
-				upper->lowest = 0;
-			}
-
 			list_add_tail(&edge->list[UPPER], &upper->lower);
 			continue;
 		}
diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h
index 6c27c070025a..13c9bc33095a 100644
--- a/fs/btrfs/backref.h
+++ b/fs/btrfs/backref.h
@@ -341,8 +341,6 @@ struct btrfs_backref_node {
 	struct extent_buffer *eb;
 	/* Level of the tree block */
 	unsigned int level:8;
-	/* 1 if no child node is in the cache */
-	unsigned int lowest:1;
 	/* Is the extent buffer locked */
 	unsigned int locked:1;
 	/* Has the block been processed */
@@ -395,8 +393,6 @@ struct btrfs_backref_cache {
 	 * level blocks may not reflect the new location
 	 */
 	struct list_head pending[BTRFS_MAX_LEVEL];
-	/* List of backref nodes with no child node */
-	struct list_head leaves;
 	/* List of detached backref node. */
 	struct list_head detached;
 
diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index 507fcc3f56e6..7fb021dd0e67 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -342,12 +342,6 @@ static bool handle_useless_nodes(struct reloc_control *rc,
 		if (cur == node)
 			ret = true;
 
-		/* The node is the lowest node */
-		if (cur->lowest) {
-			list_del_init(&cur->lower);
-			cur->lowest = 0;
-		}
-
 		/* Cleanup the lower edges */
 		while (!list_empty(&cur->lower)) {
 			struct btrfs_backref_edge *edge;
@@ -426,7 +420,6 @@ static noinline_for_stack struct btrfs_backref_node *build_backref_tree(
 		goto out;
 	}
 
-	node->lowest = 1;
 	cur = node;
 
 	/* Breadth-first search to build backref cache */
-- 
2.43.0

[PATCH 10/10] btrfs: remove detached list from btrfs_backref_cache

[Josef Bacik]

We don't ever look at this list, remove it.

Signed-off-by: Josef Bacik <josef@toxicpanda.com>
---
 fs/btrfs/backref.c    | 2 --
 fs/btrfs/backref.h    | 2 --
 fs/btrfs/relocation.c | 1 -
 3 files changed, 5 deletions(-)

diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index 5e7d41a8efdb..a8257755e1d0 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -3021,7 +3021,6 @@ void btrfs_backref_init_cache(struct btrfs_fs_info *fs_info,
 	cache->rb_root = RB_ROOT;
 	for (i = 0; i < BTRFS_MAX_LEVEL; i++)
 		INIT_LIST_HEAD(&cache->pending[i]);
-	INIT_LIST_HEAD(&cache->detached);
 	INIT_LIST_HEAD(&cache->pending_edge);
 	INIT_LIST_HEAD(&cache->useless_node);
 	cache->fs_info = fs_info;
@@ -3158,7 +3157,6 @@ void btrfs_backref_release_cache(struct btrfs_backref_cache *cache)
 
 	ASSERT(list_empty(&cache->pending_edge));
 	ASSERT(list_empty(&cache->useless_node));
-	ASSERT(list_empty(&cache->detached));
 	ASSERT(!cache->nr_nodes);
 	ASSERT(!cache->nr_edges);
 }
diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h
index 13c9bc33095a..2317380d2b1c 100644
--- a/fs/btrfs/backref.h
+++ b/fs/btrfs/backref.h
@@ -393,8 +393,6 @@ struct btrfs_backref_cache {
 	 * level blocks may not reflect the new location
 	 */
 	struct list_head pending[BTRFS_MAX_LEVEL];
-	/* List of detached backref node. */
-	struct list_head detached;
 
 	u64 last_trans;
 
diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index 7fb021dd0e67..bd86769de66a 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -367,7 +367,6 @@ static bool handle_useless_nodes(struct reloc_control *rc,
 		 * cache to avoid unnecessary backref lookup.
 		 */
 		if (cur->level > 0) {
-			list_add(&cur->list, &cache->detached);
 			cur->detached = 1;
 		} else {
 			rb_erase(&cur->rb_node, &cache->rb_root);
-- 
2.43.0

Re: [PATCH 00/10] btrfs: backref cache cleanups

[Boris Burkov]

On Thu, Oct 03, 2024 at 11:43:02AM -0400, Josef Bacik wrote:
> Hello,
> 
> This is the followup to the relocation fix that I sent out earlier.  This series
> cleans up a lot of the complicated things that exist in backref cache because we
> were keeping track of changes to the file system during relocation.  Now that we
> do not do this we can simplify a lot of the code and make it easier to
> understand.  I've tested this with the horror show of a relocation test I was
> using to trigger the original problem.  I'm running fstests now via the CI, but
> this seems solid.  Hopefully this makes the relocation code a bit easier to
> understand.  Thanks,
> 
> Josef

Sent a few minor comments inline, but all the patches look good to me.
The only ones I would say I didn't deeply understand were 6 and 7 for
the cowonly changes, in case you feel you need a closer look at those.

One high level request (also raised inline on one of them) is just to
add more high level documentation of the functions and general
algorithm design, while it's fresh. The doc covering the backref
cache data structure itself that we have in our dev doc repo is great,
but doesn't do enough to explain the actual relocation operations
carried out with the help of the backref cache.

With that said, thanks for following up (!!) and you can add

Reviewed-by: Boris Burkov <boris@bur.io>

> 
> Josef Bacik (10):
>   btrfs: convert BUG_ON in btrfs_reloc_cow_block to proper error
>     handling
>   btrfs: remove the changed list for backref cache
>   btrfs: add a comment for new_bytenr in bacref_cache_node
>   btrfs: cleanup select_reloc_root
>   btrfs: remove clone_backref_node
>   btrfs: don't build backref tree for cowonly blocks
>   btrfs: do not handle non-shareable roots in backref cache
>   btrfs: simplify btrfs_backref_release_cache
>   btrfs: remove the ->lowest and ->leaves members from backref cache
>   btrfs: remove detached list from btrfs_backref_cache
> 
>  fs/btrfs/backref.c    | 105 +++++-------
>  fs/btrfs/backref.h    |  16 +-
>  fs/btrfs/relocation.c | 362 +++++++++++++++++-------------------------
>  3 files changed, 192 insertions(+), 291 deletions(-)
> 
> -- 
> 2.43.0
> 

Re: [PATCH 00/10] btrfs: backref cache cleanups

[David Sterba]

On Thu, Oct 03, 2024 at 11:43:02AM -0400, Josef Bacik wrote:
> Hello,
> 
> This is the followup to the relocation fix that I sent out earlier.  This series
> cleans up a lot of the complicated things that exist in backref cache because we
> were keeping track of changes to the file system during relocation.  Now that we
> do not do this we can simplify a lot of the code and make it easier to
> understand.  I've tested this with the horror show of a relocation test I was
> using to trigger the original problem.  I'm running fstests now via the CI, but
> this seems solid.  Hopefully this makes the relocation code a bit easier to
> understand.  Thanks,
> 
> Josef
> 
> Josef Bacik (10):
>   btrfs: convert BUG_ON in btrfs_reloc_cow_block to proper error
>     handling
>   btrfs: remove the changed list for backref cache
>   btrfs: add a comment for new_bytenr in bacref_cache_node
>   btrfs: cleanup select_reloc_root
>   btrfs: remove clone_backref_node
>   btrfs: don't build backref tree for cowonly blocks
>   btrfs: do not handle non-shareable roots in backref cache
>   btrfs: simplify btrfs_backref_release_cache
>   btrfs: remove the ->lowest and ->leaves members from backref cache
>   btrfs: remove detached list from btrfs_backref_cache

The patches have been in misc-next as I've been expecting an update. We
want the cleanups so I've applied the series to for-next. I've removed
th ASSERT(0) callls, we need proper macros/functions in case you really
want to see something fail during development. As the errors are EUCLEAN
they'll bubble up eventually with some noisy message so I hope we're not
losing much.

Re: [PATCH 00/10] btrfs: backref cache cleanups

[Josef Bacik]

On Fri, Dec 06, 2024 at 08:38:54PM +0100, David Sterba wrote:
> On Thu, Oct 03, 2024 at 11:43:02AM -0400, Josef Bacik wrote:
> > Hello,
> > 
> > This is the followup to the relocation fix that I sent out earlier.  This series
> > cleans up a lot of the complicated things that exist in backref cache because we
> > were keeping track of changes to the file system during relocation.  Now that we
> > do not do this we can simplify a lot of the code and make it easier to
> > understand.  I've tested this with the horror show of a relocation test I was
> > using to trigger the original problem.  I'm running fstests now via the CI, but
> > this seems solid.  Hopefully this makes the relocation code a bit easier to
> > understand.  Thanks,
> > 
> > Josef
> > 
> > Josef Bacik (10):
> >   btrfs: convert BUG_ON in btrfs_reloc_cow_block to proper error
> >     handling
> >   btrfs: remove the changed list for backref cache
> >   btrfs: add a comment for new_bytenr in bacref_cache_node
> >   btrfs: cleanup select_reloc_root
> >   btrfs: remove clone_backref_node
> >   btrfs: don't build backref tree for cowonly blocks
> >   btrfs: do not handle non-shareable roots in backref cache
> >   btrfs: simplify btrfs_backref_release_cache
> >   btrfs: remove the ->lowest and ->leaves members from backref cache
> >   btrfs: remove detached list from btrfs_backref_cache
> 
> The patches have been in misc-next as I've been expecting an update. We
> want the cleanups so I've applied the series to for-next. I've removed
> th ASSERT(0) callls, we need proper macros/functions in case you really
> want to see something fail during development. As the errors are EUCLEAN
> they'll bubble up eventually with some noisy message so I hope we're not
> losing much.

Sorry Dave, I let this one fall through the cracks, thanks for picking it up for
me.

As for replacing ASSERT(0) I agree this is a blunt tool.  Maybe we could have a
macro that we put around EUCLEAN, at least in these cases where it also
indicates we might have broken something?  Something like

#ifdef CONFIG_BTRFS_DEBUG
#define BTRRFS_EUCLEAN ({ WARN_ON(1); -EUCLEAN; })
#else
#define BTRFS_EUCLEAN -EUCLEAN
#endif

And then we can just use BTRFS_EUCLEAN to replace the ASSERT(0) calls.  Thanks,

Josef

Re: [PATCH 00/10] btrfs: backref cache cleanups

[David Sterba]

On Mon, Dec 09, 2024 at 09:01:14AM -0500, Josef Bacik wrote:
> On Fri, Dec 06, 2024 at 08:38:54PM +0100, David Sterba wrote:
> > On Thu, Oct 03, 2024 at 11:43:02AM -0400, Josef Bacik wrote:
> > > Hello,
> > > 
> > > This is the followup to the relocation fix that I sent out earlier.  This series
> > > cleans up a lot of the complicated things that exist in backref cache because we
> > > were keeping track of changes to the file system during relocation.  Now that we
> > > do not do this we can simplify a lot of the code and make it easier to
> > > understand.  I've tested this with the horror show of a relocation test I was
> > > using to trigger the original problem.  I'm running fstests now via the CI, but
> > > this seems solid.  Hopefully this makes the relocation code a bit easier to
> > > understand.  Thanks,
> > > 
> > > Josef
> > > 
> > > Josef Bacik (10):
> > >   btrfs: convert BUG_ON in btrfs_reloc_cow_block to proper error
> > >     handling
> > >   btrfs: remove the changed list for backref cache
> > >   btrfs: add a comment for new_bytenr in bacref_cache_node
> > >   btrfs: cleanup select_reloc_root
> > >   btrfs: remove clone_backref_node
> > >   btrfs: don't build backref tree for cowonly blocks
> > >   btrfs: do not handle non-shareable roots in backref cache
> > >   btrfs: simplify btrfs_backref_release_cache
> > >   btrfs: remove the ->lowest and ->leaves members from backref cache
> > >   btrfs: remove detached list from btrfs_backref_cache
> > 
> > The patches have been in misc-next as I've been expecting an update. We
> > want the cleanups so I've applied the series to for-next. I've removed
> > th ASSERT(0) callls, we need proper macros/functions in case you really
> > want to see something fail during development. As the errors are EUCLEAN
> > they'll bubble up eventually with some noisy message so I hope we're not
> > losing much.
> 
> Sorry Dave, I let this one fall through the cracks, thanks for picking it up for
> me.
> 
> As for replacing ASSERT(0) I agree this is a blunt tool.  Maybe we could have a
> macro that we put around EUCLEAN, at least in these cases where it also
> indicates we might have broken something?  Something like
> 
> #ifdef CONFIG_BTRFS_DEBUG
> #define BTRRFS_EUCLEAN ({ WARN_ON(1); -EUCLEAN; })
> #else
> #define BTRFS_EUCLEAN -EUCLEAN
> #endif
> 
> And then we can just use BTRFS_EUCLEAN to replace the ASSERT(0) calls.  Thanks,

Something like that, though I'd prefer a standalone macro and name it
like WARN_DEBUG or WARN_EUCLEAN for this particular error, not to
override an error code. We don't want to print a stack for each instance
of EUCLEAN, this is meant to be selective for new code or something
you'd really like to debug or know about once it happens.