From: Qu Wenruo <wqu@suse.com>
To: linux-btrfs@vger.kernel.org
Cc: Josef Bacik <josef@toxicpanda.com>
Subject: [PATCH 09/40] btrfs: relocation: Refactor indirect tree backref processing into its own function
Date: Mon, 23 Mar 2020 18:23:45 +0800 [thread overview]
Message-ID: <20200323102416.112862-10-wqu@suse.com> (raw)
In-Reply-To: <20200323102416.112862-1-wqu@suse.com>
The processing of indirect tree backref (TREE_BLOCK_REF) is the most
complex work.
We need to grab the fs root, do a tree search to locate all its parent
nodes, linking all needed edges, and put all uncached edges to
pending edge list.
This is definitely worthy a helper function.
Signed-off-by: Qu Wenruo <wqu@suse.com>
Reviewed-by: Josef Bacik <josef@toxicpanda.com>
---
fs/btrfs/relocation.c | 295 +++++++++++++++++++++++-------------------
1 file changed, 160 insertions(+), 135 deletions(-)
diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index ea4126d167a8..652476a5cef2 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -773,6 +773,164 @@ static int handle_direct_tree_backref(struct backref_cache *cache,
return 0;
}
+/*
+ * Handle indirect tree backref.
+ *
+ * Indirect tree backref means, we only know which tree the node belongs to.
+ * Need to do a tree search to find out parents. This is for TREE_BLOCK_REF
+ * backref (keyed or inlined).
+ *
+ * @ref_key: The same as @ref_key in handle_direct_tree_backref()
+ * @tree_key: The first key of this tree block.
+ * @path: A clean (released) path, to avoid allocating path everytime
+ * the function get called.
+ */
+static int handle_indirect_tree_backref(struct backref_cache *cache,
+ struct btrfs_path *path,
+ struct btrfs_key *ref_key,
+ struct btrfs_key *tree_key,
+ struct backref_node *cur)
+{
+ struct btrfs_fs_info *fs_info = cache->fs_info;
+ struct backref_node *upper;
+ struct backref_node *lower;
+ struct backref_edge *edge;
+ struct extent_buffer *eb;
+ struct btrfs_root *root;
+ struct rb_node *rb_node;
+ int level;
+ bool need_check = true;
+ int ret;
+
+ root = read_fs_root(fs_info, ref_key->offset);
+ if (IS_ERR(root))
+ return PTR_ERR(root);
+ if (!test_bit(BTRFS_ROOT_REF_COWS, &root->state))
+ cur->cowonly = 1;
+
+ if (btrfs_root_level(&root->root_item) == cur->level) {
+ /* tree root */
+ ASSERT(btrfs_root_bytenr(&root->root_item) ==
+ cur->bytenr);
+ if (should_ignore_root(root)) {
+ btrfs_put_root(root);
+ list_add(&cur->list, &cache->useless_node);
+ } else {
+ cur->root = root;
+ }
+ return 0;
+ }
+
+ level = cur->level + 1;
+
+ /* Search the tree to find parent blocks referring the block. */
+ path->search_commit_root = 1;
+ path->skip_locking = 1;
+ path->lowest_level = level;
+ ret = btrfs_search_slot(NULL, root, tree_key, path, 0, 0);
+ path->lowest_level = 0;
+ if (ret < 0) {
+ btrfs_put_root(root);
+ return ret;
+ }
+ if (ret > 0 && path->slots[level] > 0)
+ path->slots[level]--;
+
+ eb = path->nodes[level];
+ if (btrfs_node_blockptr(eb, path->slots[level]) != cur->bytenr) {
+ btrfs_err(fs_info,
+"couldn't find block (%llu) (level %d) in tree (%llu) with key (%llu %u %llu)",
+ cur->bytenr, level - 1, root->root_key.objectid,
+ tree_key->objectid, tree_key->type, tree_key->offset);
+ btrfs_put_root(root);
+ ret = -ENOENT;
+ goto out;
+ }
+ lower = cur;
+
+ /* Add all nodes and edges in the path */
+ for (; level < BTRFS_MAX_LEVEL; level++) {
+ if (!path->nodes[level]) {
+ ASSERT(btrfs_root_bytenr(&root->root_item) ==
+ lower->bytenr);
+ if (should_ignore_root(root)) {
+ btrfs_put_root(root);
+ list_add(&lower->list, &cache->useless_node);
+ } else {
+ lower->root = root;
+ }
+ break;
+ }
+
+ edge = alloc_backref_edge(cache);
+ if (!edge) {
+ btrfs_put_root(root);
+ ret = -ENOMEM;
+ goto out;
+ }
+
+ eb = path->nodes[level];
+ rb_node = tree_search(&cache->rb_root, eb->start);
+ if (!rb_node) {
+ upper = alloc_backref_node(cache);
+ if (!upper) {
+ btrfs_put_root(root);
+ free_backref_edge(cache, edge);
+ ret = -ENOMEM;
+ goto out;
+ }
+ upper->bytenr = eb->start;
+ upper->owner = btrfs_header_owner(eb);
+ upper->level = lower->level + 1;
+ if (!test_bit(BTRFS_ROOT_REF_COWS, &root->state))
+ upper->cowonly = 1;
+
+ /*
+ * if we know the block isn't shared we can void
+ * checking its backrefs.
+ */
+ if (btrfs_block_can_be_shared(root, eb))
+ upper->checked = 0;
+ else
+ upper->checked = 1;
+
+ /*
+ * add the block to pending list if we need check its
+ * backrefs, we only do this once while walking up a
+ * tree as we will catch anything else later on.
+ */
+ if (!upper->checked && need_check) {
+ need_check = false;
+ list_add_tail(&edge->list[UPPER],
+ &cache->pending_edge);
+ } else {
+ if (upper->checked)
+ need_check = true;
+ INIT_LIST_HEAD(&edge->list[UPPER]);
+ }
+ } else {
+ upper = rb_entry(rb_node, struct backref_node, rb_node);
+ ASSERT(upper->checked);
+ INIT_LIST_HEAD(&edge->list[UPPER]);
+ if (!upper->owner)
+ upper->owner = btrfs_header_owner(eb);
+ }
+ list_add_tail(&edge->list[LOWER], &lower->upper);
+ edge->node[LOWER] = lower;
+ edge->node[UPPER] = upper;
+
+ if (rb_node) {
+ btrfs_put_root(root);
+ break;
+ }
+ lower = upper;
+ upper = NULL;
+ }
+out:
+ btrfs_release_path(path);
+ 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
@@ -795,7 +953,6 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
struct btrfs_backref_iter *iter;
struct backref_cache *cache = &rc->backref_cache;
struct btrfs_path *path; /* For searching parent of TREE_BLOCK_REF */
- struct btrfs_root *root;
struct backref_node *cur;
struct backref_node *upper;
struct backref_node *lower;
@@ -806,7 +963,6 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
int cowonly;
int ret;
int err = 0;
- bool need_check = true;
iter = btrfs_backref_iter_alloc(rc->extent_root->fs_info, GFP_NOFS);
if (!iter)
@@ -936,143 +1092,12 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
* means the root objectid. We need to search the tree to get
* its parent bytenr.
*/
- root = read_fs_root(rc->extent_root->fs_info, key.offset);
- if (IS_ERR(root)) {
- err = PTR_ERR(root);
- goto out;
- }
-
- if (!test_bit(BTRFS_ROOT_REF_COWS, &root->state))
- cur->cowonly = 1;
-
- if (btrfs_root_level(&root->root_item) == cur->level) {
- /* tree root */
- ASSERT(btrfs_root_bytenr(&root->root_item) ==
- cur->bytenr);
- if (should_ignore_root(root)) {
- btrfs_put_root(root);
- list_add(&cur->list, &cache->useless_node);
- } else {
- cur->root = root;
- }
- break;
- }
-
- level = cur->level + 1;
-
- /* Search the tree to find parent blocks referring the block. */
- path->search_commit_root = 1;
- path->skip_locking = 1;
- path->lowest_level = level;
- ret = btrfs_search_slot(NULL, root, node_key, path, 0, 0);
- path->lowest_level = 0;
+ ret = handle_indirect_tree_backref(cache, path, &key, node_key,
+ cur);
if (ret < 0) {
- btrfs_put_root(root);
err = ret;
goto out;
}
- if (ret > 0 && path->slots[level] > 0)
- path->slots[level]--;
-
- eb = path->nodes[level];
- if (btrfs_node_blockptr(eb, path->slots[level]) !=
- cur->bytenr) {
- btrfs_err(root->fs_info,
- "couldn't find block (%llu) (level %d) in tree (%llu) with key (%llu %u %llu)",
- cur->bytenr, level - 1,
- root->root_key.objectid,
- node_key->objectid, node_key->type,
- node_key->offset);
- btrfs_put_root(root);
- err = -ENOENT;
- goto out;
- }
- lower = cur;
- need_check = true;
-
- /* Add all nodes and edges in the path */
- for (; level < BTRFS_MAX_LEVEL; level++) {
- if (!path->nodes[level]) {
- ASSERT(btrfs_root_bytenr(&root->root_item) ==
- lower->bytenr);
- if (should_ignore_root(root)) {
- btrfs_put_root(root);
- list_add(&lower->list,
- &cache->useless_node);
- } else {
- lower->root = root;
- }
- break;
- }
-
- edge = alloc_backref_edge(cache);
- if (!edge) {
- btrfs_put_root(root);
- err = -ENOMEM;
- goto out;
- }
-
- eb = path->nodes[level];
- rb_node = tree_search(&cache->rb_root, eb->start);
- if (!rb_node) {
- upper = alloc_backref_node(cache);
- if (!upper) {
- btrfs_put_root(root);
- free_backref_edge(cache, edge);
- err = -ENOMEM;
- goto out;
- }
- upper->bytenr = eb->start;
- upper->owner = btrfs_header_owner(eb);
- upper->level = lower->level + 1;
- if (!test_bit(BTRFS_ROOT_REF_COWS,
- &root->state))
- upper->cowonly = 1;
-
- /*
- * if we know the block isn't shared
- * we can void checking its backrefs.
- */
- if (btrfs_block_can_be_shared(root, eb))
- upper->checked = 0;
- else
- upper->checked = 1;
-
- /*
- * add the block to pending list if we
- * need check its backrefs, we only do this once
- * while walking up a tree as we will catch
- * anything else later on.
- */
- if (!upper->checked && need_check) {
- need_check = false;
- list_add_tail(&edge->list[UPPER],
- &cache->pending_edge);
- } else {
- if (upper->checked)
- need_check = true;
- INIT_LIST_HEAD(&edge->list[UPPER]);
- }
- } else {
- upper = rb_entry(rb_node, struct backref_node,
- rb_node);
- ASSERT(upper->checked);
- INIT_LIST_HEAD(&edge->list[UPPER]);
- if (!upper->owner)
- upper->owner = btrfs_header_owner(eb);
- }
- list_add_tail(&edge->list[LOWER], &lower->upper);
- edge->node[LOWER] = lower;
- edge->node[UPPER] = upper;
-
- if (rb_node) {
- btrfs_put_root(root);
- break;
- }
- lower = upper;
- upper = NULL;
- }
- btrfs_release_path(path);
}
if (ret < 0) {
err = ret;
--
2.25.2
next prev parent reply other threads:[~2020-03-23 10:24 UTC|newest]
Thread overview: 42+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-03-23 10:23 [PATCH 00/40] btrfs: qgroup: Use backref cache based backref walk for commit roots Qu Wenruo
2020-03-23 10:23 ` [PATCH 01/40] btrfs: backref: Introduce the skeleton of btrfs_backref_iter Qu Wenruo
2020-03-23 12:51 ` Josef Bacik
2020-03-23 10:23 ` [PATCH 02/40] btrfs: backref: Implement btrfs_backref_iter_next() Qu Wenruo
2020-03-23 10:23 ` [PATCH 03/40] btrfs: relocation: Use btrfs_backref_iter infrastructure Qu Wenruo
2020-03-23 10:23 ` [PATCH 04/40] btrfs: relocation: Rename mark_block_processed() and __mark_block_processed() Qu Wenruo
2020-03-23 10:23 ` [PATCH 05/40] btrfs: relocation: Add backref_cache::pending_edge and backref_cache::useless_node members Qu Wenruo
2020-03-23 10:23 ` [PATCH 06/40] btrfs: relocation: Add backref_cache::fs_info member Qu Wenruo
2020-03-23 10:23 ` [PATCH 07/40] btrfs: relocation: Make reloc root search specific for relocation backref cache Qu Wenruo
2020-03-23 10:23 ` [PATCH 08/40] btrfs: relocation: Refactor direct tree backref processing into its own function Qu Wenruo
2020-03-23 10:23 ` Qu Wenruo [this message]
2020-03-23 10:23 ` [PATCH 10/40] btrfs: relocation: Use wrapper to replace open-coded edge linking Qu Wenruo
2020-03-23 10:23 ` [PATCH 11/40] btrfs: relocation: Specify essential members for alloc_backref_node() Qu Wenruo
2020-03-23 10:23 ` [PATCH 12/40] btrfs: relocation: Remove the open-coded goto loop for breadth-first search Qu Wenruo
2020-03-23 10:23 ` [PATCH 13/40] btrfs: relocation: Refactor the finishing part of upper linkage into finish_upper_links() Qu Wenruo
2020-03-23 10:23 ` [PATCH 14/40] btrfs: relocation: Refactor the useless nodes handling into its own function Qu Wenruo
2020-03-23 10:23 ` [PATCH 15/40] btrfs: relocation: Add btrfs_ prefix for backref_node/edge/cache Qu Wenruo
2020-03-23 10:23 ` [PATCH 16/40] btrfs: Move btrfs_backref_(node|edge|cache) structures to backref.h Qu Wenruo
2020-03-23 10:23 ` [PATCH 17/40] btrfs: Rename tree_entry to simple_node and export it Qu Wenruo
2020-03-23 10:23 ` [PATCH 18/40] btrfs: Rename backref_cache_init() to btrfs_backref_cache_init() and move it to backref.c Qu Wenruo
2020-03-23 10:23 ` [PATCH 19/40] btrfs: Rename alloc_backref_node() to btrfs_backref_alloc_node() and move it backref.c Qu Wenruo
2020-03-23 10:23 ` [PATCH 20/40] btrfs: Rename alloc_backref_edge() to btrfs_backref_alloc_edge() " Qu Wenruo
2020-03-23 10:23 ` [PATCH 21/40] btrfs: Rename link_backref_edge() to btrfs_backref_link_edge() and move it backref.h Qu Wenruo
2020-03-23 10:23 ` [PATCH 22/40] btrfs: Rename free_backref_(node|edge) to btrfs_backref_free_(node|edge) and move them to backref.h Qu Wenruo
2020-03-23 10:23 ` [PATCH 23/40] btrfs: Rename drop_backref_node() to btrfs_backref_drop_node() and move its needed facilities " Qu Wenruo
2020-03-23 10:24 ` [PATCH 24/40] btrfs: Rename remove_backref_node() to btrfs_backref_cleanup_node() and move it to backref.c Qu Wenruo
2020-03-23 10:24 ` [PATCH 25/40] btrfs: Rename backref_cache_cleanup() to btrfs_backref_release_cache() " Qu Wenruo
2020-03-23 10:24 ` [PATCH 26/40] btrfs: Rename backref_tree_panic() to btrfs_backref_panic(), " Qu Wenruo
2020-03-23 10:24 ` [PATCH 27/40] btrfs: Rename should_ignore_root() to btrfs_should_ignore_reloc_root() and export it Qu Wenruo
2020-03-23 10:24 ` [PATCH 28/40] btrfs: relocation: Open-code read_fs_root() for handle_indirect_tree_backref() Qu Wenruo
2020-03-23 10:24 ` [PATCH 29/40] btrfs: Rename handle_one_tree_block() to btrfs_backref_add_tree_node() and move it to backref.c Qu Wenruo
2020-03-23 10:24 ` [PATCH 30/40] btrfs: Rename finish_upper_links() to btrfs_backref_finish_upper_links() " Qu Wenruo
2020-03-23 10:24 ` [PATCH 31/40] btrfs: relocation: Move error handling of build_backref_tree() " Qu Wenruo
2020-03-23 10:24 ` [PATCH 32/40] btrfs: relocation: Use btrfs_find_all_leaves() to locate parent tree leaves of a data extent Qu Wenruo
2020-03-23 10:24 ` [PATCH 33/40] btrfs: backref: Only ignore reloc roots for indrect backref resolve if the backref cache is for reloction purpose Qu Wenruo
2020-03-23 10:24 ` [PATCH 34/40] btrfs: qgroup: Introduce qgroup backref cache Qu Wenruo
2020-03-23 10:24 ` [PATCH 35/40] btrfs: qgroup: Introduce qgroup_backref_cache_build() function Qu Wenruo
2020-03-23 10:24 ` [PATCH 36/40] btrfs: qgroup: Introduce a function to iterate through backref_cache to find all parents for specified node Qu Wenruo
2020-03-23 10:24 ` [PATCH 37/40] btrfs: qgroup: Introduce helpers to get needed tree block info Qu Wenruo
2020-03-23 10:24 ` [PATCH 38/40] btrfs: qgroup: Introduce verification for function to ensure old roots ulist matches btrfs_find_all_roots() result Qu Wenruo
2020-03-23 10:24 ` [PATCH 39/40] btrfs: qgroup: Introduce a new function to get old_roots ulist using backref cache Qu Wenruo
2020-03-23 10:24 ` [PATCH 40/40] btrfs: qgroup: Use backref cache to speed up old_roots search Qu Wenruo
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=20200323102416.112862-10-wqu@suse.com \
--to=wqu@suse.com \
--cc=josef@toxicpanda.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 a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox