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

Nikolay Borisov
2020-03-04T14:24:29Z

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;
> + }
> }
>
> /*
>