From: Qu Wenruo <wqu@suse.com>
To: linux-btrfs@vger.kernel.org
Cc: Josef Bacik <josef@toxicpanda.com>
Subject: [PATCH 05/40] btrfs: relocation: Add backref_cache::pending_edge and backref_cache::useless_node members
Date: Mon, 23 Mar 2020 18:23:41 +0800 [thread overview]
Message-ID: <20200323102416.112862-6-wqu@suse.com> (raw)
In-Reply-To: <20200323102416.112862-1-wqu@suse.com>
These two new members will act the same as the existing local lists,
@useless and @list in build_backref_tree().
Currently build_backref_tree() is only executed serially, thus moving
such local list into backref_cache is still safe.
Also since we're here, use list_first_entry() to replace a lot of
list_entry() calls after !list_empty().
Signed-off-by: Qu Wenruo <wqu@suse.com>
Reviewed-by: Josef Bacik <josef@toxicpanda.com>
---
fs/btrfs/relocation.c | 74 +++++++++++++++++++++++++++----------------
1 file changed, 46 insertions(+), 28 deletions(-)
diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index ad7724d846b7..0ba441bb8554 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -157,6 +157,12 @@ struct backref_cache {
int nr_nodes;
int nr_edges;
+
+ /* The list of unchecked backref edges during backref cache build */
+ struct list_head pending_edge;
+
+ /* The list of useless backref nodes during backref cache build */
+ struct list_head useless_node;
};
/*
@@ -268,6 +274,8 @@ static void backref_cache_init(struct backref_cache *cache)
INIT_LIST_HEAD(&cache->changed);
INIT_LIST_HEAD(&cache->detached);
INIT_LIST_HEAD(&cache->leaves);
+ INIT_LIST_HEAD(&cache->pending_edge);
+ INIT_LIST_HEAD(&cache->useless_node);
}
static void backref_cache_cleanup(struct backref_cache *cache)
@@ -291,6 +299,8 @@ static void backref_cache_cleanup(struct backref_cache *cache)
for (i = 0; i < BTRFS_MAX_LEVEL; i++)
ASSERT(list_empty(&cache->pending[i]));
+ ASSERT(list_empty(&cache->pending_edge));
+ ASSERT(list_empty(&cache->useless_node));
ASSERT(list_empty(&cache->changed));
ASSERT(list_empty(&cache->detached));
ASSERT(RB_EMPTY_ROOT(&cache->rb_root));
@@ -697,8 +707,6 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
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;
int ret;
int err = 0;
@@ -763,7 +771,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], &cache->pending_edge);
} else {
exist = NULL;
}
@@ -841,7 +849,8 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
* backrefs for the upper level block isn't
* cached, add the block to pending list
*/
- list_add_tail(&edge->list[UPPER], &list);
+ list_add_tail(&edge->list[UPPER],
+ &cache->pending_edge);
} else {
upper = rb_entry(rb_node, struct backref_node,
rb_node);
@@ -883,7 +892,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
cur->bytenr);
if (should_ignore_root(root)) {
btrfs_put_root(root);
- list_add(&cur->list, &useless);
+ list_add(&cur->list, &cache->useless_node);
} else {
cur->root = root;
}
@@ -929,7 +938,8 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
lower->bytenr);
if (should_ignore_root(root)) {
btrfs_put_root(root);
- list_add(&lower->list, &useless);
+ list_add(&lower->list,
+ &cache->useless_node);
} else {
lower->root = root;
}
@@ -978,7 +988,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
if (!upper->checked && need_check) {
need_check = false;
list_add_tail(&edge->list[UPPER],
- &list);
+ &cache->pending_edge);
} else {
if (upper->checked)
need_check = true;
@@ -1016,8 +1026,9 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
WARN_ON(exist);
/* 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]);
+ if (!list_empty(&cache->pending_edge)) {
+ edge = list_entry(cache->pending_edge.next,
+ struct backref_edge, list[UPPER]);
list_del_init(&edge->list[UPPER]);
cur = edge->node[UPPER];
goto again;
@@ -1038,10 +1049,11 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
}
list_for_each_entry(edge, &node->upper, list[LOWER])
- list_add_tail(&edge->list[UPPER], &list);
+ list_add_tail(&edge->list[UPPER], &cache->pending_edge);
- while (!list_empty(&list)) {
- edge = list_entry(list.next, struct backref_edge, list[UPPER]);
+ while (!list_empty(&cache->pending_edge)) {
+ edge = list_first_entry(&cache->pending_edge,
+ struct backref_edge, list[UPPER]);
list_del_init(&edge->list[UPPER]);
upper = edge->node[UPPER];
if (upper->detached) {
@@ -1049,7 +1061,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
lower = edge->node[LOWER];
free_backref_edge(cache, edge);
if (list_empty(&lower->upper))
- list_add(&lower->list, &useless);
+ list_add(&lower->list, &cache->useless_node);
continue;
}
@@ -1089,7 +1101,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
list_add_tail(&edge->list[UPPER], &upper->lower);
list_for_each_entry(edge, &upper->upper, list[LOWER])
- list_add_tail(&edge->list[UPPER], &list);
+ list_add_tail(&edge->list[UPPER], &cache->pending_edge);
}
/*
* process useless backref nodes. backref nodes for tree leaves
@@ -1097,8 +1109,9 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
* tree blocks are left in the cache to avoid unnecessary backref
* lookup.
*/
- while (!list_empty(&useless)) {
- upper = list_entry(useless.next, struct backref_node, list);
+ while (!list_empty(&cache->useless_node)) {
+ upper = list_first_entry(&cache->useless_node,
+ struct backref_node, list);
list_del_init(&upper->list);
ASSERT(list_empty(&upper->upper));
if (upper == node)
@@ -1108,7 +1121,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
upper->lowest = 0;
}
while (!list_empty(&upper->lower)) {
- edge = list_entry(upper->lower.next,
+ edge = list_first_entry(&upper->lower,
struct backref_edge, list[UPPER]);
list_del(&edge->list[UPPER]);
list_del(&edge->list[LOWER]);
@@ -1116,7 +1129,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
free_backref_edge(cache, edge);
if (list_empty(&lower->upper))
- list_add(&lower->list, &useless);
+ list_add(&lower->list, &cache->useless_node);
}
mark_block_processed(rc, upper);
if (upper->level > 0) {
@@ -1131,14 +1144,14 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
btrfs_backref_iter_free(iter);
btrfs_free_path(path);
if (err) {
- while (!list_empty(&useless)) {
- lower = list_entry(useless.next,
+ while (!list_empty(&cache->useless_node)) {
+ lower = list_first_entry(&cache->useless_node,
struct backref_node, list);
list_del_init(&lower->list);
}
- while (!list_empty(&list)) {
- edge = list_first_entry(&list, struct backref_edge,
- list[UPPER]);
+ while (!list_empty(&cache->pending_edge)) {
+ edge = list_first_entry(&cache->pending_edge,
+ struct backref_edge, list[UPPER]);
list_del(&edge->list[UPPER]);
list_del(&edge->list[LOWER]);
lower = edge->node[LOWER];
@@ -1151,20 +1164,21 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
*/
if (list_empty(&lower->upper) &&
RB_EMPTY_NODE(&lower->rb_node))
- list_add(&lower->list, &useless);
+ list_add(&lower->list, &cache->useless_node);
if (!RB_EMPTY_NODE(&upper->rb_node))
continue;
/* Add this guy's upper edges to the list to process */
list_for_each_entry(edge, &upper->upper, list[LOWER])
- list_add_tail(&edge->list[UPPER], &list);
+ list_add_tail(&edge->list[UPPER],
+ &cache->pending_edge);
if (list_empty(&upper->upper))
- list_add(&upper->list, &useless);
+ list_add(&upper->list, &cache->useless_node);
}
- while (!list_empty(&useless)) {
- lower = list_entry(useless.next,
+ while (!list_empty(&cache->useless_node)) {
+ lower = list_first_entry(&cache->useless_node,
struct backref_node, list);
list_del_init(&lower->list);
if (lower == node)
@@ -1173,9 +1187,13 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
}
free_backref_node(cache, node);
+ ASSERT(list_empty(&cache->useless_node) &&
+ list_empty(&cache->pending_edge));
return ERR_PTR(err);
}
ASSERT(!node || !node->detached);
+ ASSERT(list_empty(&cache->useless_node) &&
+ list_empty(&cache->pending_edge));
return node;
}
--
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 ` Qu Wenruo [this message]
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 ` [PATCH 09/40] btrfs: relocation: Refactor indirect " Qu Wenruo
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-6-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