Re: [PATCH v2 08/10] btrfs: relocation: Remove the open-coded goto loop for breadth-first search

[Nikolay Borisov <nborisov@suse.com>]

On 2.03.20 г. 11:45 ч., Qu Wenruo wrote:
> build_backref_tree() uses "goto again;" to implement a breadth-first
> search to build backref cache.
> 
> This patch will extract most of its work into a wrapper,
> handle_one_tree_block(), and use a while() loop to implement the same
> thing.
> 
> Signed-off-by: Qu Wenruo <wqu@suse.com>
> ---
>  fs/btrfs/relocation.c | 167 +++++++++++++++++++++++-------------------
>  1 file changed, 91 insertions(+), 76 deletions(-)
> 
> diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
> index 67a4a61eb86a..26089694b3b5 100644
> --- a/fs/btrfs/relocation.c
> +++ b/fs/btrfs/relocation.c
> @@ -892,65 +892,21 @@ static int handle_one_tree_backref(struct reloc_control *rc,
>  	return ret;
>  }
>  
> -/*
> - * build backref tree for a given tree block. root of the backref tree
> - * corresponds the tree block, leaves of the backref tree correspond
> - * roots of b-trees that reference the tree block.
> - *
> - * the basic idea of this function is check backrefs of a given block
> - * to find upper level blocks that reference the block, and then check
> - * backrefs of these upper level blocks recursively. the recursion stop
> - * when tree root is reached or backrefs for the block is cached.
> - *
> - * NOTE: if we find backrefs for a block are cached, we know backrefs
> - * for all upper level blocks that directly/indirectly reference the
> - * block are also cached.
> - */
> -static noinline_for_stack
> -struct backref_node *build_backref_tree(struct reloc_control *rc,
> -					struct btrfs_key *node_key,
> -					int level, u64 bytenr)
> +static int handle_one_tree_block(struct reloc_control *rc,
> +				 struct list_head *useless_node,
> +				 struct list_head *pending_edge,
> +				 struct btrfs_path *path,
> +				 struct btrfs_backref_iter *iter,
> +				 struct btrfs_key *node_key,
> +				 struct backref_node *cur)
>  {
> -	struct btrfs_backref_iter *iter;
> -	struct backref_cache *cache = &rc->backref_cache;
> -	struct btrfs_path *path; /* For searching parent of TREE_BLOCK_REF */
> -	struct backref_node *cur;
> -	struct backref_node *upper;
> -	struct backref_node *lower;
> -	struct backref_node *node = NULL;
> -	struct backref_node *exist = NULL;
>  	struct backref_edge *edge;
> -	struct rb_node *rb_node;
> -	LIST_HEAD(list); /* Pending edge list, upper node needs to be checked */
> -	LIST_HEAD(useless);
> -	int cowonly;
> +	struct backref_node *exist;
>  	int ret;
> -	int err = 0;
> -
> -	iter = btrfs_backref_iter_alloc(rc->extent_root->fs_info, GFP_NOFS);
> -	if (!iter)
> -		return ERR_PTR(-ENOMEM);
> -	path = btrfs_alloc_path();
> -	if (!path) {
> -		err = -ENOMEM;
> -		goto out;
> -	}
> -	path->reada = READA_FORWARD;
> -
> -	node = alloc_backref_node(cache, bytenr, level);
> -	if (!node) {
> -		err = -ENOMEM;
> -		goto out;
> -	}
>  
> -	node->lowest = 1;
> -	cur = node;
> -again:
>  	ret = btrfs_backref_iter_start(iter, cur->bytenr);
> -	if (ret < 0) {
> -		err = ret;
> -		goto out;
> -	}
> +	if (ret < 0)
> +		return ret;
>  
>  	/*
>  	 * We skip the first btrfs_tree_block_info, as we don't use the key
> @@ -958,13 +914,11 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
>  	 */
>  	if (btrfs_backref_has_tree_block_info(iter)) {
>  		ret = btrfs_backref_iter_next(iter);
> -		if (ret < 0) {
> -			err = ret;
> +		if (ret < 0)
>  			goto out;
> -		}
>  		/* No extra backref? This means the tree block is corrupted */
>  		if (ret > 0) {
> -			err = -EUCLEAN;
> +			ret = -EUCLEAN;
>  			goto out;
>  		}
>  	}
> @@ -984,7 +938,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
>  		 * check its backrefs
>  		 */
>  		if (!exist->checked)
> -			list_add_tail(&edge->list[UPPER], &list);
> +			list_add_tail(&edge->list[UPPER], pending_edge);
>  	} else {
>  		exist = NULL;
>  	}
> @@ -1006,7 +960,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
>  			type = btrfs_get_extent_inline_ref_type(eb, iref,
>  							BTRFS_REF_TYPE_BLOCK);
>  			if (type == BTRFS_REF_TYPE_INVALID) {
> -				err = -EUCLEAN;
> +				ret = -EUCLEAN;
>  				goto out;
>  			}
>  			key.type = type;
> @@ -1029,29 +983,90 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
>  			continue;
>  		}
>  
> -		ret = handle_one_tree_backref(rc, &useless, &list, path, &key,
> -					      node_key, cur);
> -		if (ret < 0) {
> -			err = ret;
> +		ret = handle_one_tree_backref(rc, useless_node, pending_edge, path,
> +					      &key, node_key, cur);
> +		if (ret < 0)
>  			goto out;
> -		}
>  	}
> -	if (ret < 0) {
> -		err = ret;
> +	if (ret < 0)
>  		goto out;
> -	}
>  	ret = 0;
> -	btrfs_backref_iter_release(iter);
> -
>  	cur->checked = 1;
>  	WARN_ON(exist);
> +out:
> +	btrfs_backref_iter_release(iter);
> +	return ret;
> +}
>  
> -	/* the pending list isn't empty, take the first block to process */
> -	if (!list_empty(&list)) {
> -		edge = list_entry(list.next, struct backref_edge, list[UPPER]);
> -		list_del_init(&edge->list[UPPER]);
> -		cur = edge->node[UPPER];
> -		goto again;
> +/*
> + * build backref tree for a given tree block. root of the backref tree
> + * corresponds the tree block, leaves of the backref tree correspond
> + * roots of b-trees that reference the tree block.
> + *
> + * the basic idea of this function is check backrefs of a given block
> + * to find upper level blocks that reference the block, and then check
> + * backrefs of these upper level blocks recursively. the recursion stop
> + * when tree root is reached or backrefs for the block is cached.
> + *
> + * NOTE: if we find backrefs for a block are cached, we know backrefs
> + * for all upper level blocks that directly/indirectly reference the
> + * block are also cached.
> + */
> +static noinline_for_stack
> +struct backref_node *build_backref_tree(struct reloc_control *rc,
> +					struct btrfs_key *node_key,
> +					int level, u64 bytenr)
> +{
> +	struct btrfs_backref_iter *iter;
> +	struct backref_cache *cache = &rc->backref_cache;
> +	struct btrfs_path *path; /* For searching parent of TREE_BLOCK_REF */
> +	struct backref_node *cur;
> +	struct backref_node *upper;
> +	struct backref_node *lower;
> +	struct backref_node *node = NULL;
> +	struct backref_edge *edge;
> +	struct rb_node *rb_node;
> +	LIST_HEAD(list); /* Pending edge list, upper node needs to be checked */
> +	LIST_HEAD(useless);
> +	int cowonly;
> +	int ret;
> +	int err = 0;
> +
> +	iter = btrfs_backref_iter_alloc(rc->extent_root->fs_info, GFP_NOFS);
> +	if (!iter)
> +		return ERR_PTR(-ENOMEM);

This iterator can be made private to handle_one_tree_block as I don't see it being used outside of that function. 

> +	path = btrfs_alloc_path();
> +	if (!path) {
> +		err = -ENOMEM;
> +		goto out;
> +	}

Same thing with this path. Overall this will reduce the argument to handle_one_tree_block by 2.

> +	path->reada = READA_FORWARD;
> +
> +	node = alloc_backref_node(cache, bytenr, level);
> +	if (!node) {
> +		err = -ENOMEM;
> +		goto out;
> +	}
> +
> +	node->lowest = 1;
> +	cur = node;
> +
> +	/* Breadth-first search to build backref cache */
> +	while (1) {
> +		ret = handle_one_tree_block(rc, &useless, &list, path, iter,
> +					    node_key, cur);
> +		if (ret < 0) {
> +			err = ret;
> +			goto out;
> +		}
> +		/* the pending list isn't empty, take the first block to process */
> +		if (!list_empty(&list)) {
> +			edge = list_entry(list.next, struct backref_edge, list[UPPER]);

Use list_first_entry_or_null or it would become: 

edge = list_first_entry_or_null();
if (edge) {
list_del_init(&edge->list[UPPER]);
cur = edge->node[UPPER]
} else {
breakl
}

or simply if (!edge)
break;

Also this loop can be rewritten as a do {} while() and it will look:

        /* Breadth-first search to build backref cache */                       
        do {                                                                    
                ret = handle_one_tree_block(rc, &useless, &list, path, iter,    
                                            node_key, cur);                     
                if (ret < 0) {                                                  
                        err = ret;                                              
                        goto out;                                               
                }                                                               
                edge = list_first_entry_or_null(&list, struct backref_edge,     
                                                list[UPPER]);                   
                /* the pending list isn't empty, take the first block to process */
                if (edge) {                                                     
                        list_del_init(&edge->list[UPPER]);                      
                        cur = edge->node[UPPER];                                
                }                                                               
        } while (edge)

IMO this is shorter than the original version and it's very expicit about it's terminating conditions:
a). handle_one_tree_block returns an error
b) list becomes empty. 

Alternatively list being empty is really a proxy for "is cur a valid inode". We know it's always
valid on the first iteration since it's passed form the caller, subsequent iterations assign cur 
to edge->node[UPPER] so it could even be 

while(cur) {} 

In my opinion reducing while(1) loops where it makes sense (as in this case) is preferable. 

NB: I've only compile-tested it. 

> +			list_del_init(&edge->list[UPPER]);
> +			cur = edge->node[UPPER];
> +		} else {
> +			break;
> +		}
>  	}
>  
>  	/*
>