From: Qu Wenruo <wqu@suse.com>
To: linux-btrfs@vger.kernel.org
Subject: [PATCH 08/10] btrfs: relocation: Remove the open-coded goto loop for breadth-first search
Date: Wed, 26 Feb 2020 13:56:50 +0800 [thread overview]
Message-ID: <20200226055652.24857-9-wqu@suse.com> (raw)
In-Reply-To: <20200226055652.24857-1-wqu@suse.com>
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 | 165 +++++++++++++++++++++++-------------------
1 file changed, 90 insertions(+), 75 deletions(-)
diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index f072d075a202..13eadbb1c552 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -846,65 +846,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
@@ -912,13 +868,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;
}
}
@@ -938,7 +892,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;
}
@@ -960,7 +914,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;
@@ -983,29 +937,90 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
continue;
}
- ret = handle_one_tree_backref(rc, &useless, &list, path,
+ ret = handle_one_tree_backref(rc, useless_node, pending_edge, path,
&key, node_key, cur);
- if (ret < 0) {
- err = ret;
+ 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);
+ 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;
+
+ /* 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]);
+ list_del_init(&edge->list[UPPER]);
+ cur = edge->node[UPPER];
+ } else {
+ break;
+ }
}
/*
--
2.25.1
next prev parent reply other threads:[~2020-02-26 5:57 UTC|newest]
Thread overview: 15+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-02-26 5:56 [PATCH 00/10] btrfs: relocation: Refactor build_backref_tree() Qu Wenruo
2020-02-26 5:56 ` [PATCH 01/10] btrfs: backref: Introduce the skeleton of btrfs_backref_iter Qu Wenruo
2020-02-26 5:56 ` [PATCH 02/10] btrfs: backref: Implement btrfs_backref_iter_next() Qu Wenruo
2020-02-26 5:56 ` [PATCH 03/10] btrfs: relocation: Use btrfs_backref_iter infrastructure Qu Wenruo
2020-02-26 5:56 ` [PATCH 04/10] btrfs: relocation: Rename mark_block_processed() and __mark_block_processed() Qu Wenruo
2020-02-26 13:56 ` Nikolay Borisov
2020-02-26 5:56 ` [PATCH 05/10] btrfs: relocation: Refactor tree backref processing into its own function Qu Wenruo
2020-02-26 5:56 ` [PATCH 06/10] btrfs: relocation: Use wrapper to replace open-coded edge linking Qu Wenruo
2020-02-26 5:56 ` [PATCH 07/10] btrfs: relocation: Specify essential members for alloc_backref_node() Qu Wenruo
2020-02-26 5:56 ` Qu Wenruo [this message]
2020-02-26 5:56 ` [PATCH 09/10] btrfs: relocation: Refactor the finishing part of upper linkage into finish_upper_links() Qu Wenruo
2020-02-26 5:56 ` [PATCH 10/10] btrfs: relocation: Refactor the useless nodes handling into its own function Qu Wenruo
2020-02-28 15:45 ` [PATCH 00/10] btrfs: relocation: Refactor build_backref_tree() David Sterba
2020-02-29 1:00 ` Qu Wenruo
2020-03-02 20:26 ` David Sterba
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20200226055652.24857-9-wqu@suse.com \
--to=wqu@suse.com \
--cc=linux-btrfs@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.