From: Qu Wenruo <wqu@suse.com>
To: linux-btrfs@vger.kernel.org
Subject: [PATCH RFC 29/39] btrfs: Rename finish_upper_links() to backref_cache_finish_upper_links() and move it to backref.c
Date: Tue, 17 Mar 2020 16:11:15 +0800 [thread overview]
Message-ID: <20200317081125.36289-30-wqu@suse.com> (raw)
In-Reply-To: <20200317081125.36289-1-wqu@suse.com>
This the the 2nd major part of generic backref cache. Move it to
backref.c so we can reuse it.
Signed-off-by: Qu Wenruo <wqu@suse.com>
---
fs/btrfs/backref.c | 114 +++++++++++++++++++++++++++++++++++++++++
fs/btrfs/backref.h | 2 +
fs/btrfs/relocation.c | 115 +-----------------------------------------
3 files changed, 117 insertions(+), 114 deletions(-)
diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index 013e833bf5bc..0a1cfa4433d3 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -2938,3 +2938,117 @@ int backref_cache_add_tree_block(struct backref_cache *cache,
btrfs_backref_iter_release(iter);
return ret;
}
+
+/*
+ * In backref_cache_add_tree_block(), we have only linked the lower node to the
+ * edge, but the upper node hasn't been linked to the edge.
+ * This means we can only iterate through backref_node::upper to reach parent
+ * edges, but not through backref_node::lower to reach children edges.
+ *
+ * This function will finish the backref_node::lower to related edges, so that
+ * backref cache can be bi-directionally iterated.
+ *
+ * Also, this will add the nodes to backref cache for next run.
+ */
+int backref_cache_finish_upper_links(struct backref_cache *cache,
+ struct backref_node *start)
+{
+ struct list_head *useless_node = &cache->useless_node;
+ struct backref_edge *edge;
+ struct rb_node *rb_node;
+ LIST_HEAD(pending_edge);
+
+ ASSERT(start->checked);
+
+ /* Insert this node to cache if it's not cowonly */
+ if (!start->cowonly) {
+ rb_node = simple_insert(&cache->rb_root, start->bytenr,
+ &start->rb_node);
+ if (rb_node)
+ backref_cache_panic(cache->fs_info, start->bytenr,
+ -EEXIST);
+ list_add_tail(&start->lower, &cache->leaves);
+ }
+
+ /*
+ * Use breadth first search to iterate all related edges.
+ *
+ * The start point is all the edges of this node
+ */
+ list_for_each_entry(edge, &start->upper, list[LOWER])
+ list_add_tail(&edge->list[UPPER], &pending_edge);
+
+ while (!list_empty(&pending_edge)) {
+ struct backref_node *upper;
+ struct backref_node *lower;
+ struct rb_node *rb_node;
+
+ edge = list_first_entry(&pending_edge, struct backref_edge,
+ list[UPPER]);
+ list_del_init(&edge->list[UPPER]);
+ upper = edge->node[UPPER];
+ lower = edge->node[LOWER];
+
+ /* Parent is detached, no need to keep any edges */
+ if (upper->detached) {
+ list_del(&edge->list[LOWER]);
+ free_backref_edge(cache, edge);
+
+ /* Lower node is orphan, queue for cleanup */
+ if (list_empty(&lower->upper))
+ list_add(&lower->list, useless_node);
+ continue;
+ }
+
+ /*
+ * All new nodes added in current build_backref_tree() haven't
+ * been linked to the cache rb tree.
+ * So if we have upper->rb_node populated, this means a cache
+ * hit. We only need to link the edge, as @upper and all its
+ * parent 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;
+ }
+
+ /* Sanity check, we shouldn't have any unchecked nodes */
+ if (!upper->checked) {
+ ASSERT(0);
+ return -EUCLEAN;
+ }
+
+ /* Sanity check, cowonly node has non-cowonly parent */
+ if (start->cowonly != upper->cowonly) {
+ ASSERT(0);
+ return -EUCLEAN;
+ }
+
+ /* Only cache non-cowonly (subvolume trees) tree blocks */
+ if (!upper->cowonly) {
+ rb_node = simple_insert(&cache->rb_root, upper->bytenr,
+ &upper->rb_node);
+ if (rb_node) {
+ backref_cache_panic(cache->fs_info,
+ upper->bytenr, -EEXIST);
+ return -EUCLEAN;
+ }
+ }
+
+ list_add_tail(&edge->list[UPPER], &upper->lower);
+
+ /*
+ * Also queue all the parent edges of this uncached node
+ * to finish the upper linkage
+ */
+ list_for_each_entry(edge, &upper->upper, list[LOWER])
+ list_add_tail(&edge->list[UPPER], &pending_edge);
+ }
+ return 0;
+}
+
diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h
index b17bc8d5411a..c6c9f536c359 100644
--- a/fs/btrfs/backref.h
+++ b/fs/btrfs/backref.h
@@ -371,4 +371,6 @@ int backref_cache_add_tree_block(struct backref_cache *cache,
struct btrfs_backref_iter *iter,
struct btrfs_key *node_key,
struct backref_node *cur);
+int backref_cache_finish_upper_links(struct backref_cache *cache,
+ struct backref_node *start);
#endif
diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index d133a7df90cf..ad3896dcdb48 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -383,119 +383,6 @@ static struct btrfs_root *read_fs_root(struct btrfs_fs_info *fs_info,
return btrfs_get_fs_root(fs_info, &key, false);
}
-/*
- * In backref_cache_add_tree_block(), we have only linked the lower node to the
- * edge, but the upper node hasn't been linked to the edge.
- * This means we can only iterate through backref_node::upper to reach parent
- * edges, but not through backref_node::lower to reach children edges.
- *
- * This function will finish the backref_node::lower to related edges, so that
- * backref cache can be bi-directionally iterated.
- *
- * Also, this will add the nodes to backref cache for next run.
- */
-static int finish_upper_links(struct backref_cache *cache,
- struct backref_node *start)
-{
- struct list_head *useless_node = &cache->useless_node;
- struct backref_edge *edge;
- struct rb_node *rb_node;
- LIST_HEAD(pending_edge);
-
- ASSERT(start->checked);
-
- /* Insert this node to cache if it's not cowonly */
- if (!start->cowonly) {
- rb_node = simple_insert(&cache->rb_root, start->bytenr,
- &start->rb_node);
- if (rb_node)
- backref_cache_panic(cache->fs_info, start->bytenr,
- -EEXIST);
- list_add_tail(&start->lower, &cache->leaves);
- }
-
- /*
- * Use breadth first search to iterate all related edges.
- *
- * The start point is all the edges of this node
- */
- list_for_each_entry(edge, &start->upper, list[LOWER])
- list_add_tail(&edge->list[UPPER], &pending_edge);
-
- while (!list_empty(&pending_edge)) {
- struct backref_node *upper;
- struct backref_node *lower;
- struct rb_node *rb_node;
-
- edge = list_first_entry(&pending_edge, struct backref_edge,
- list[UPPER]);
- list_del_init(&edge->list[UPPER]);
- upper = edge->node[UPPER];
- lower = edge->node[LOWER];
-
- /* Parent is detached, no need to keep any edges */
- if (upper->detached) {
- list_del(&edge->list[LOWER]);
- free_backref_edge(cache, edge);
-
- /* Lower node is orphan, queue for cleanup */
- if (list_empty(&lower->upper))
- list_add(&lower->list, useless_node);
- continue;
- }
-
- /*
- * All new nodes added in current build_backref_tree() haven't
- * been linked to the cache rb tree.
- * So if we have upper->rb_node populated, this means a cache
- * hit. We only need to link the edge, as @upper and all its
- * parent 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;
- }
-
- /* Sanity check, we shouldn't have any unchecked nodes */
- if (!upper->checked) {
- ASSERT(0);
- return -EUCLEAN;
- }
-
- /* Sanity check, cowonly node has non-cowonly parent */
- if (start->cowonly != upper->cowonly) {
- ASSERT(0);
- return -EUCLEAN;
- }
-
- /* Only cache non-cowonly (subvolume trees) tree blocks */
- if (!upper->cowonly) {
- rb_node = simple_insert(&cache->rb_root, upper->bytenr,
- &upper->rb_node);
- if (rb_node) {
- backref_cache_panic(cache->fs_info,
- upper->bytenr, -EEXIST);
- return -EUCLEAN;
- }
- }
-
- list_add_tail(&edge->list[UPPER], &upper->lower);
-
- /*
- * Also queue all the parent edges of this uncached node
- * to finish the upper linkage
- */
- list_for_each_entry(edge, &upper->upper, list[LOWER])
- list_add_tail(&edge->list[UPPER], &pending_edge);
- }
- return 0;
-}
-
/*
* For useless nodes, do two major clean ups:
* - Cleanup the children edges and nodes
@@ -636,7 +523,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
} while (edge);
/* Finish the upper linkage of newly added edges/nodes */
- ret = finish_upper_links(cache, node);
+ ret = backref_cache_finish_upper_links(cache, node);
if (ret < 0) {
err = ret;
goto out;
--
2.25.1
next prev parent reply other threads:[~2020-03-17 8:12 UTC|newest]
Thread overview: 57+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-03-17 8:10 [PATCH RFC 00/39] btrfs: qgroup: Use backref cache based backref walk for commit roots Qu Wenruo
2020-03-17 8:10 ` [PATCH RFC 01/39] btrfs: backref: Introduce the skeleton of btrfs_backref_iter Qu Wenruo
2020-03-19 14:46 ` Josef Bacik
2020-03-17 8:10 ` [PATCH RFC 02/39] btrfs: backref: Implement btrfs_backref_iter_next() Qu Wenruo
2020-03-19 15:05 ` Josef Bacik
2020-03-17 8:10 ` [PATCH RFC 03/39] btrfs: relocation: Use btrfs_backref_iter infrastructure Qu Wenruo
2020-03-19 15:16 ` Josef Bacik
2020-03-17 8:10 ` [PATCH RFC 04/39] btrfs: relocation: Rename mark_block_processed() and __mark_block_processed() Qu Wenruo
2020-03-19 15:18 ` Josef Bacik
2020-03-17 8:10 ` [PATCH RFC 05/39] btrfs: relocation: Add backref_cache::pending_edge and backref_cache::useless_node members Qu Wenruo
2020-03-19 15:21 ` Josef Bacik
2020-03-17 8:10 ` [PATCH RFC 06/39] btrfs: relocation: Add backref_cache::fs_info member Qu Wenruo
2020-03-19 15:21 ` Josef Bacik
2020-03-17 8:10 ` [PATCH RFC 07/39] btrfs: relocation: Make reloc root search specific for relocation backref cache Qu Wenruo
2020-03-19 15:27 ` Josef Bacik
2020-03-19 15:28 ` Josef Bacik
2020-03-19 15:30 ` Josef Bacik
2020-03-17 8:10 ` [PATCH RFC 08/39] btrfs: relocation: Refactor direct tree backref processing into its own function Qu Wenruo
2020-03-19 15:31 ` Josef Bacik
2020-03-17 8:10 ` [PATCH RFC 09/39] btrfs: relocation: Refactor indirect " Qu Wenruo
2020-03-19 15:36 ` Josef Bacik
2020-03-17 8:10 ` [PATCH RFC 10/39] btrfs: relocation: Use wrapper to replace open-coded edge linking Qu Wenruo
2020-03-17 8:10 ` [PATCH RFC 11/39] btrfs: relocation: Specify essential members for alloc_backref_node() Qu Wenruo
2020-03-17 8:10 ` [PATCH RFC 12/39] btrfs: relocation: Remove the open-coded goto loop for breadth-first search Qu Wenruo
2020-03-19 15:42 ` Josef Bacik
2020-03-17 8:10 ` [PATCH RFC 13/39] btrfs: relocation: Refactor the finishing part of upper linkage into finish_upper_links() Qu Wenruo
2020-03-19 17:19 ` Josef Bacik
2020-03-17 8:11 ` [PATCH RFC 14/39] btrfs: relocation: Refactor the useless nodes handling into its own function Qu Wenruo
2020-03-19 17:21 ` Josef Bacik
2020-03-17 8:11 ` [PATCH RFC 15/39] btrfs: Move backref node/edge/cache structure to backref.h Qu Wenruo
2020-03-19 17:26 ` Josef Bacik
2020-03-17 8:11 ` [PATCH RFC 16/39] btrfs: Rename tree_entry to simple_node and export it Qu Wenruo
2020-03-17 8:11 ` [PATCH RFC 17/39] btrfs: Move backref_cache_init() to backref.c Qu Wenruo
2020-03-17 8:11 ` [PATCH RFC 18/39] btrfs: Move alloc_backref_node() " Qu Wenruo
2020-03-17 8:11 ` [PATCH RFC 19/39] btrfs: Move alloc_backref_edge() " Qu Wenruo
2020-03-17 8:11 ` [PATCH RFC 20/39] btrfs: Move link_backref_edge() " Qu Wenruo
2020-03-17 8:11 ` [PATCH RFC 21/39] btrfs: Move free_backref_node() and free_backref_edge() to backref.h Qu Wenruo
2020-03-17 8:11 ` [PATCH RFC 22/39] btrfs: Move drop_backref_node() and needed facilities " Qu Wenruo
2020-03-17 8:11 ` [PATCH RFC 23/39] btrfs: Rename remove_backref_node() to cleanup_backref_node() and move it to backref.c Qu Wenruo
2020-03-17 8:11 ` [PATCH RFC 24/39] btrfs: Rename backref_cache_cleanup() to backref_cache_release() " Qu Wenruo
2020-03-17 8:11 ` [PATCH RFC 25/39] btrfs: Rename backref_tree_panic() to backref_cache_panic(), " Qu Wenruo
2020-03-17 8:11 ` [PATCH RFC 26/39] btrfs: Rename should_ignore_root() to should_ignore_reloc_root() and export it Qu Wenruo
2020-03-17 8:11 ` [PATCH RFC 27/39] btrfs: relocation: Open-code read_fs_root() for handle_indirect_tree_backref() Qu Wenruo
2020-03-17 8:11 ` [PATCH RFC 28/39] btrfs: Rename handle_one_tree_block() to backref_cache_add_one_tree_block() and move it to backref.c Qu Wenruo
2020-03-17 8:11 ` Qu Wenruo [this message]
2020-03-17 8:11 ` [PATCH RFC 30/39] btrfs: relocation: Move error handling of build_backref_tree() " Qu Wenruo
2020-03-17 8:11 ` [PATCH RFC 31/39] btrfs: relocation: Use btrfs_find_all_leaves() to locate parent tree leaves of a data extent Qu Wenruo
2020-03-17 8:11 ` [PATCH RFC 32/39] btrfs: backref: Only ignore reloc roots for indrect backref resolve if the backref cache is for reloction purpose Qu Wenruo
2020-03-17 8:11 ` [PATCH RFC 33/39] btrfs: qgroup: Introduce qgroup backref cache Qu Wenruo
2020-03-17 8:11 ` [PATCH RFC 34/39] btrfs: qgroup: Introduce qgroup_backref_cache_build() function Qu Wenruo
2020-03-17 8:11 ` [PATCH RFC 35/39] btrfs: qgroup: Introduce a function to iterate through backref_cache to find all parents for specified node Qu Wenruo
2020-03-17 8:11 ` [PATCH RFC 36/39] btrfs: qgroup: Introduce helpers to get needed tree block info Qu Wenruo
2020-03-17 8:11 ` [PATCH RFC 37/39] btrfs: qgroup: Introduce verification for function to ensure old roots ulist matches btrfs_find_all_roots() result Qu Wenruo
2020-03-17 8:11 ` [PATCH RFC 38/39] btrfs: qgroup: Introduce a new function to get old_roots ulist using backref cache Qu Wenruo
2020-03-17 8:11 ` [PATCH RFC 39/39] btrfs: qgroup: Use backref cache to speed up old_roots search Qu Wenruo
2020-03-19 17:26 ` [PATCH RFC 00/39] btrfs: qgroup: Use backref cache based backref walk for commit roots Josef Bacik
2020-03-25 18:30 ` 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=20200317081125.36289-30-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 a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).