* [PATCH 00/19] btrfs: Move generic backref cache build functions to backref.c
@ 2020-03-03 7:13 Qu Wenruo
2020-03-03 7:13 ` [PATCH 01/19] btrfs: Move backref node/edge/cache structure to backref.h Qu Wenruo
` (20 more replies)
0 siblings, 21 replies; 25+ messages in thread
From: Qu Wenruo @ 2020-03-03 7:13 UTC (permalink / raw
To: linux-btrfs
The patchset is based on previous backref_cache_refactor branch, which
is further based on misc-next.
The whole series can be fetched from github:
https://github.com/adam900710/linux/tree/backref_cache_code_move
All the patches in previous branch is not touched at all, thus they are
not re-sent in this patchset.
Currently there are 3 major parts of build_backref_tree():
- ITERATION
This will do a breadth-first search, starts from the target bytenr,
and queue all parents into the backref cache.
The result is a temporary map, which is only single-directional, and
involved new backref nodes are not yet inserted into the cache.
- WEAVING
Finish the map to make it bi-directional, and insert new nodes into
the cache.
- CLEANUP
Cleanup the useless nodes, either remove it completely or add them
into the cache as detached.
For the ITERATION part, there are only limited locations coupled with
relocation.
And WEAVING part is completely independent from relocation.
While the CLEANUP part, although it has some relocation related code,
it's not a big hunk of code after all.
So, this patchset will move the ITERATION part, extracted as
backref_cache_add_one_tree_block(), and the WEAVING part, extracted as
backref_cache_finish_upper_links(), to backref.c, as the basis for later
reuse of backref_cache.
Qu Wenruo (19):
btrfs: Move backref node/edge/cache structure to backref.h
btrfs: Rename tree_entry to simple_node and export it
btrfs: relocation: Make reloc root search specific for relocation
backref cache
btrfs: relocation: Add backref_cache::pending_edge and
backref_cache::useless_node members
btrfs: relocation: Add backref_cache::fs_info member
btrfs: Move backref_cache_init() to backref.c
btrfs: Move alloc_backref_node() to backref.c
btrfs: Move alloc_backref_edge() to backref.c
btrfs: Move link_backref_edge() to backref.c
btrfs: Move free_backref_node() and free_backref_edge() to backref.h
btrfs: Move drop_backref_node() and needed facilities to backref.h
btrfs: Rename remove_backref_node() to cleanup_backref_node() and move
it to backref.c
btrfs: Move backref_cache_cleanup() to backref.c
btrfs: Rename backref_tree_panic() to backref_cache_panic(), and move
it to backref.c
btrfs: Rename should_ignore_root() to should_ignore_reloc_root() and
export it
btrfs: relocation: Open-code read_fs_root() for
handle_one_tree_backref()
btrfs: Rename handle_one_tree_block() to
backref_cache_add_one_tree_block() and move it to backref.c
btrfs: relocation: Move the target backref node insert code into
finish_upper_links()
btrfs: Rename finish_upper_links() to
backref_cache_finish_upper_links() and move it to backref.c
fs/btrfs/backref.c | 534 ++++++++++++++++++++++++++
fs/btrfs/backref.h | 226 +++++++++++
fs/btrfs/ctree.h | 3 +
fs/btrfs/misc.h | 54 +++
fs/btrfs/relocation.c | 870 ++++--------------------------------------
5 files changed, 892 insertions(+), 795 deletions(-)
--
2.25.1
^ permalink raw reply [flat|nested] 25+ messages in thread
* [PATCH 01/19] btrfs: Move backref node/edge/cache structure to backref.h
2020-03-03 7:13 [PATCH 00/19] btrfs: Move generic backref cache build functions to backref.c Qu Wenruo
@ 2020-03-03 7:13 ` Qu Wenruo
2020-03-03 7:13 ` [PATCH 02/19] btrfs: Rename tree_entry to simple_node and export it Qu Wenruo
` (19 subsequent siblings)
20 siblings, 0 replies; 25+ messages in thread
From: Qu Wenruo @ 2020-03-03 7:13 UTC (permalink / raw
To: linux-btrfs
These 3 structures are the main part of backref cache, move them to
backref.h to build the basis for later reuse.
Signed-off-by: Qu Wenruo <wqu@suse.com>
---
fs/btrfs/backref.h | 98 +++++++++++++++++++++++++++++++++++++++++++
fs/btrfs/relocation.c | 93 +---------------------------------------
2 files changed, 100 insertions(+), 91 deletions(-)
diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h
index 42fd76dfe553..3cf79fafdf07 100644
--- a/fs/btrfs/backref.h
+++ b/fs/btrfs/backref.h
@@ -168,4 +168,102 @@ btrfs_backref_iter_release(struct btrfs_backref_iter *iter)
memset(&iter->cur_key, 0, sizeof(iter->cur_key));
}
+/*
+ * Backref cache related structures.
+ *
+ * The whole objective of backref_cache is to build a bi-directional map
+ * of tree blocks (represented by backref_node) and all their parents.
+ */
+
+/*
+ * present a tree block in the backref cache
+ */
+struct backref_node {
+ struct rb_node rb_node;
+ u64 bytenr;
+
+ u64 new_bytenr;
+ /* objectid of tree block owner, can be not uptodate */
+ u64 owner;
+ /* link to pending, changed or detached list */
+ struct list_head list;
+
+ /* List of upper level edges, which links this node to its parent(s) */
+ struct list_head upper;
+ /* List of lower level edges, which links this node to its child(ren) */
+ struct list_head lower;
+
+ /* NULL if this node is not tree root */
+ struct btrfs_root *root;
+ /* extent buffer got by COW the block */
+ struct extent_buffer *eb;
+ /* level of tree block */
+ unsigned int level:8;
+ /* is the block in non-reference counted tree */
+ unsigned int cowonly:1;
+ /* 1 if no child node in the cache */
+ unsigned int lowest:1;
+ /* is the extent buffer locked */
+ unsigned int locked:1;
+ /* has the block been processed */
+ unsigned int processed:1;
+ /* have backrefs of this block been checked */
+ unsigned int checked:1;
+ /*
+ * 1 if corresponding block has been cowed but some upper
+ * level block pointers may not point to the new location
+ */
+ unsigned int pending:1;
+ /*
+ * 1 if the backref node isn't connected to any other
+ * backref node.
+ */
+ unsigned int detached:1;
+};
+
+#define LOWER 0
+#define UPPER 1
+
+/*
+ * present an edge connecting upper and lower backref nodes.
+ */
+struct backref_edge {
+ /*
+ * list[LOWER] is linked to backref_node::upper of lower level node,
+ * and list[UPPER] is linked to backref_node::lower of upper level node.
+ *
+ * Also, build_backref_tree() uses list[UPPER] for pending edges, before
+ * linking list[UPPER] to its upper level nodes.
+ */
+ struct list_head list[2];
+
+ /* Two related nodes */
+ struct backref_node *node[2];
+};
+
+
+struct backref_cache {
+ /* red black tree of all backref nodes in the cache */
+ struct rb_root rb_root;
+ /* for passing backref nodes to btrfs_reloc_cow_block */
+ struct backref_node *path[BTRFS_MAX_LEVEL];
+ /*
+ * list of blocks that have been cowed but some block
+ * pointers in upper level blocks may not reflect the
+ * new location
+ */
+ struct list_head pending[BTRFS_MAX_LEVEL];
+ /* list of backref nodes with no child node */
+ struct list_head leaves;
+ /* list of blocks that have been cowed in current transaction */
+ struct list_head changed;
+ /* list of detached backref node. */
+ struct list_head detached;
+
+ u64 last_trans;
+
+ int nr_nodes;
+ int nr_edges;
+};
+
#endif
diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index 93364eb07a61..8d939c7837c8 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -24,6 +24,8 @@
#include "block-group.h"
#include "backref.h"
+#define RELOCATION_RESERVED_NODES 256
+
/*
* Relocation overview
*
@@ -79,97 +81,6 @@ struct tree_entry {
u64 bytenr;
};
-/*
- * present a tree block in the backref cache
- */
-struct backref_node {
- struct rb_node rb_node;
- u64 bytenr;
-
- u64 new_bytenr;
- /* objectid of tree block owner, can be not uptodate */
- u64 owner;
- /* link to pending, changed or detached list */
- struct list_head list;
-
- /* List of upper level edges, which links this node to its parent(s) */
- struct list_head upper;
- /* List of lower level edges, which links this node to its child(ren) */
- struct list_head lower;
-
- /* NULL if this node is not tree root */
- struct btrfs_root *root;
- /* extent buffer got by COW the block */
- struct extent_buffer *eb;
- /* level of tree block */
- unsigned int level:8;
- /* is the block in non-reference counted tree */
- unsigned int cowonly:1;
- /* 1 if no child node in the cache */
- unsigned int lowest:1;
- /* is the extent buffer locked */
- unsigned int locked:1;
- /* has the block been processed */
- unsigned int processed:1;
- /* have backrefs of this block been checked */
- unsigned int checked:1;
- /*
- * 1 if corresponding block has been cowed but some upper
- * level block pointers may not point to the new location
- */
- unsigned int pending:1;
- /*
- * 1 if the backref node isn't connected to any other
- * backref node.
- */
- unsigned int detached:1;
-};
-
-#define LOWER 0
-#define UPPER 1
-#define RELOCATION_RESERVED_NODES 256
-/*
- * present an edge connecting upper and lower backref nodes.
- */
-struct backref_edge {
- /*
- * list[LOWER] is linked to backref_node::upper of lower level node,
- * and list[UPPER] is linked to backref_node::lower of upper level node.
- *
- * Also, build_backref_tree() uses list[UPPER] for pending edges, before
- * linking list[UPPER] to its upper level nodes.
- */
- struct list_head list[2];
-
- /* Two related nodes */
- struct backref_node *node[2];
-};
-
-
-struct backref_cache {
- /* red black tree of all backref nodes in the cache */
- struct rb_root rb_root;
- /* for passing backref nodes to btrfs_reloc_cow_block */
- struct backref_node *path[BTRFS_MAX_LEVEL];
- /*
- * list of blocks that have been cowed but some block
- * pointers in upper level blocks may not reflect the
- * new location
- */
- struct list_head pending[BTRFS_MAX_LEVEL];
- /* list of backref nodes with no child node */
- struct list_head leaves;
- /* list of blocks that have been cowed in current transaction */
- struct list_head changed;
- /* list of detached backref node. */
- struct list_head detached;
-
- u64 last_trans;
-
- int nr_nodes;
- int nr_edges;
-};
-
/*
* map address of tree root to tree
*/
--
2.25.1
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH 02/19] btrfs: Rename tree_entry to simple_node and export it
2020-03-03 7:13 [PATCH 00/19] btrfs: Move generic backref cache build functions to backref.c Qu Wenruo
2020-03-03 7:13 ` [PATCH 01/19] btrfs: Move backref node/edge/cache structure to backref.h Qu Wenruo
@ 2020-03-03 7:13 ` Qu Wenruo
2020-03-03 7:13 ` [PATCH 03/19] btrfs: relocation: Make reloc root search specific for relocation backref cache Qu Wenruo
` (18 subsequent siblings)
20 siblings, 0 replies; 25+ messages in thread
From: Qu Wenruo @ 2020-03-03 7:13 UTC (permalink / raw
To: linux-btrfs
Structure tree_entry provides a very simple rb_tree which only uses
bytenr as search index.
That tree_entry is used in 3 structures: backref_node, mapping_node and
tree_block.
Since we're going to make backref_node independnt from relocation, it's
a good time to extract the tree_entry into simple_node, and export it
into misc.h.
Signed-off-by: Qu Wenruo <wqu@suse.com>
---
fs/btrfs/backref.h | 6 ++-
fs/btrfs/misc.h | 54 +++++++++++++++++++++
fs/btrfs/relocation.c | 109 ++++++++++++++----------------------------
3 files changed, 94 insertions(+), 75 deletions(-)
diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h
index 3cf79fafdf07..923788fa03ef 100644
--- a/fs/btrfs/backref.h
+++ b/fs/btrfs/backref.h
@@ -179,8 +179,10 @@ btrfs_backref_iter_release(struct btrfs_backref_iter *iter)
* present a tree block in the backref cache
*/
struct backref_node {
- struct rb_node rb_node;
- u64 bytenr;
+ struct {
+ struct rb_node rb_node;
+ u64 bytenr;
+ }; /* Use simple_node for search/insert */
u64 new_bytenr;
/* objectid of tree block owner, can be not uptodate */
diff --git a/fs/btrfs/misc.h b/fs/btrfs/misc.h
index 72bab64ecf60..d199bfdb210e 100644
--- a/fs/btrfs/misc.h
+++ b/fs/btrfs/misc.h
@@ -6,6 +6,7 @@
#include <linux/sched.h>
#include <linux/wait.h>
#include <asm/div64.h>
+#include <linux/rbtree.h>
#define in_range(b, first, len) ((b) >= (first) && (b) < (first) + (len))
@@ -58,4 +59,57 @@ static inline bool has_single_bit_set(u64 n)
return is_power_of_two_u64(n);
}
+/*
+ * Simple bytenr based rb_tree relate structures
+ *
+ * Any structure wants to use bytenr as single search index should have their
+ * structure start with these members.
+ */
+struct simple_node {
+ struct rb_node rb_node;
+ u64 bytenr;
+};
+
+static inline struct rb_node *simple_search(struct rb_root *root, u64 bytenr)
+{
+ struct rb_node *n = root->rb_node;
+ struct simple_node *entry;
+
+ while (n) {
+ entry = rb_entry(n, struct simple_node, rb_node);
+
+ if (bytenr < entry->bytenr)
+ n = n->rb_left;
+ else if (bytenr > entry->bytenr)
+ n = n->rb_right;
+ else
+ return n;
+ }
+ return NULL;
+}
+
+static inline struct rb_node *simple_insert(struct rb_root *root, u64 bytenr,
+ struct rb_node *node)
+{
+ struct rb_node **p = &root->rb_node;
+ struct rb_node *parent = NULL;
+ struct simple_node *entry;
+
+ while (*p) {
+ parent = *p;
+ entry = rb_entry(parent, struct simple_node, rb_node);
+
+ if (bytenr < entry->bytenr)
+ p = &(*p)->rb_left;
+ else if (bytenr > entry->bytenr)
+ p = &(*p)->rb_right;
+ else
+ return parent;
+ }
+
+ rb_link_node(node, parent, p);
+ rb_insert_color(node, root);
+ return NULL;
+}
+
#endif
diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index 8d939c7837c8..50348a58bb43 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -23,6 +23,7 @@
#include "delalloc-space.h"
#include "block-group.h"
#include "backref.h"
+#include "misc.h"
#define RELOCATION_RESERVED_NODES 256
@@ -85,8 +86,10 @@ struct tree_entry {
* map address of tree root to tree
*/
struct mapping_node {
- struct rb_node rb_node;
- u64 bytenr;
+ struct {
+ struct rb_node rb_node;
+ u64 bytenr;
+ }; /* Use simle_node for search_insert */
void *data;
};
@@ -99,8 +102,10 @@ struct mapping_tree {
* present a tree block to process
*/
struct tree_block {
- struct rb_node rb_node;
- u64 bytenr;
+ struct {
+ struct rb_node rb_node;
+ u64 bytenr;
+ }; /* Use simple_node for search/insert */
struct btrfs_key key;
unsigned int level:8;
unsigned int key_ready:1;
@@ -284,48 +289,6 @@ static void free_backref_edge(struct backref_cache *cache,
}
}
-static struct rb_node *tree_insert(struct rb_root *root, u64 bytenr,
- struct rb_node *node)
-{
- struct rb_node **p = &root->rb_node;
- struct rb_node *parent = NULL;
- struct tree_entry *entry;
-
- while (*p) {
- parent = *p;
- entry = rb_entry(parent, struct tree_entry, rb_node);
-
- if (bytenr < entry->bytenr)
- p = &(*p)->rb_left;
- else if (bytenr > entry->bytenr)
- p = &(*p)->rb_right;
- else
- return parent;
- }
-
- rb_link_node(node, parent, p);
- rb_insert_color(node, root);
- return NULL;
-}
-
-static struct rb_node *tree_search(struct rb_root *root, u64 bytenr)
-{
- struct rb_node *n = root->rb_node;
- struct tree_entry *entry;
-
- while (n) {
- entry = rb_entry(n, struct tree_entry, rb_node);
-
- if (bytenr < entry->bytenr)
- n = n->rb_left;
- else if (bytenr > entry->bytenr)
- n = n->rb_right;
- else
- return n;
- }
- return NULL;
-}
-
static void backref_tree_panic(struct rb_node *rb_node, int errno, u64 bytenr)
{
@@ -464,7 +427,7 @@ static void update_backref_node(struct backref_cache *cache,
struct rb_node *rb_node;
rb_erase(&node->rb_node, &cache->rb_root);
node->bytenr = bytenr;
- rb_node = tree_insert(&cache->rb_root, node->bytenr, &node->rb_node);
+ rb_node = simple_insert(&cache->rb_root, node->bytenr, &node->rb_node);
if (rb_node)
backref_tree_panic(rb_node, -EEXIST, bytenr);
}
@@ -588,7 +551,7 @@ static struct btrfs_root *find_reloc_root(struct reloc_control *rc,
struct btrfs_root *root = NULL;
spin_lock(&rc->reloc_root_tree.lock);
- rb_node = tree_search(&rc->reloc_root_tree.rb_root, bytenr);
+ rb_node = simple_search(&rc->reloc_root_tree.rb_root, bytenr);
if (rb_node) {
node = rb_entry(rb_node, struct mapping_node, rb_node);
root = (struct btrfs_root *)node->data;
@@ -649,7 +612,7 @@ static int handle_one_tree_backref(struct reloc_control *rc,
if (!edge)
return -ENOMEM;
- rb_node = tree_search(&cache->rb_root, ref_key->offset);
+ rb_node = simple_search(&cache->rb_root, ref_key->offset);
if (!rb_node) {
/* Parent node not yet cached */
upper = alloc_backref_node(cache, ref_key->offset,
@@ -746,7 +709,7 @@ static int handle_one_tree_backref(struct reloc_control *rc,
}
eb = path->nodes[level];
- rb_node = tree_search(&cache->rb_root, eb->start);
+ rb_node = simple_search(&cache->rb_root, eb->start);
if (!rb_node) {
upper = alloc_backref_node(cache, eb->start,
lower->level + 1);
@@ -988,8 +951,8 @@ static int finish_upper_links(struct backref_cache *cache,
/* Only cache non-cowonly (subvolume trees) tree blocks */
if (!upper->cowonly) {
- rb_node = tree_insert(&cache->rb_root, upper->bytenr,
- &upper->rb_node);
+ rb_node = simple_insert(&cache->rb_root, upper->bytenr,
+ &upper->rb_node);
if (rb_node) {
backref_tree_panic(rb_node, -EEXIST,
upper->bytenr);
@@ -1158,8 +1121,8 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
*/
ASSERT(node->checked);
if (!node->cowonly) {
- rb_node = tree_insert(&cache->rb_root, node->bytenr,
- &node->rb_node);
+ rb_node = simple_insert(&cache->rb_root, node->bytenr,
+ &node->rb_node);
if (rb_node)
backref_tree_panic(rb_node, -EEXIST, node->bytenr);
list_add_tail(&node->lower, &cache->leaves);
@@ -1247,7 +1210,7 @@ static int clone_backref_node(struct btrfs_trans_handle *trans,
if (cache->last_trans > 0)
update_backref_cache(trans, cache);
- rb_node = tree_search(&cache->rb_root, src->commit_root->start);
+ rb_node = simple_search(&cache->rb_root, src->commit_root->start);
if (rb_node) {
node = rb_entry(rb_node, struct backref_node, rb_node);
if (node->detached)
@@ -1257,8 +1220,8 @@ static int clone_backref_node(struct btrfs_trans_handle *trans,
}
if (!node) {
- rb_node = tree_search(&cache->rb_root,
- reloc_root->commit_root->start);
+ rb_node = simple_search(&cache->rb_root,
+ reloc_root->commit_root->start);
if (rb_node) {
node = rb_entry(rb_node, struct backref_node,
rb_node);
@@ -1291,8 +1254,8 @@ static int clone_backref_node(struct btrfs_trans_handle *trans,
list_add_tail(&new_node->lower, &cache->leaves);
}
- rb_node = tree_insert(&cache->rb_root, new_node->bytenr,
- &new_node->rb_node);
+ rb_node = simple_insert(&cache->rb_root, new_node->bytenr,
+ &new_node->rb_node);
if (rb_node)
backref_tree_panic(rb_node, -EEXIST, new_node->bytenr);
@@ -1332,8 +1295,8 @@ static int __must_check __add_reloc_root(struct btrfs_root *root)
node->data = root;
spin_lock(&rc->reloc_root_tree.lock);
- rb_node = tree_insert(&rc->reloc_root_tree.rb_root,
- node->bytenr, &node->rb_node);
+ rb_node = simple_insert(&rc->reloc_root_tree.rb_root,
+ node->bytenr, &node->rb_node);
spin_unlock(&rc->reloc_root_tree.lock);
if (rb_node) {
btrfs_panic(fs_info, -EEXIST,
@@ -1358,8 +1321,8 @@ static void __del_reloc_root(struct btrfs_root *root)
if (rc && root->node) {
spin_lock(&rc->reloc_root_tree.lock);
- rb_node = tree_search(&rc->reloc_root_tree.rb_root,
- root->node->start);
+ rb_node = simple_search(&rc->reloc_root_tree.rb_root,
+ root->node->start);
if (rb_node) {
node = rb_entry(rb_node, struct mapping_node, rb_node);
rb_erase(&node->rb_node, &rc->reloc_root_tree.rb_root);
@@ -1388,8 +1351,8 @@ static int __update_reloc_root(struct btrfs_root *root, u64 new_bytenr)
struct reloc_control *rc = fs_info->reloc_ctl;
spin_lock(&rc->reloc_root_tree.lock);
- rb_node = tree_search(&rc->reloc_root_tree.rb_root,
- root->node->start);
+ rb_node = simple_search(&rc->reloc_root_tree.rb_root,
+ root->node->start);
if (rb_node) {
node = rb_entry(rb_node, struct mapping_node, rb_node);
rb_erase(&node->rb_node, &rc->reloc_root_tree.rb_root);
@@ -1402,8 +1365,8 @@ static int __update_reloc_root(struct btrfs_root *root, u64 new_bytenr)
spin_lock(&rc->reloc_root_tree.lock);
node->bytenr = new_bytenr;
- rb_node = tree_insert(&rc->reloc_root_tree.rb_root,
- node->bytenr, &node->rb_node);
+ rb_node = simple_insert(&rc->reloc_root_tree.rb_root,
+ node->bytenr, &node->rb_node);
spin_unlock(&rc->reloc_root_tree.lock);
if (rb_node)
backref_tree_panic(rb_node, -EEXIST, node->bytenr);
@@ -3490,7 +3453,7 @@ static int add_tree_block(struct reloc_control *rc,
block->level = level;
block->key_ready = 0;
- rb_node = tree_insert(blocks, block->bytenr, &block->rb_node);
+ rb_node = simple_insert(blocks, block->bytenr, &block->rb_node);
if (rb_node)
backref_tree_panic(rb_node, -EEXIST, block->bytenr);
@@ -3513,7 +3476,7 @@ static int __add_tree_block(struct reloc_control *rc,
if (tree_block_processed(bytenr, rc))
return 0;
- if (tree_search(blocks, bytenr))
+ if (simple_search(blocks, bytenr))
return 0;
path = btrfs_alloc_path();
@@ -3717,7 +3680,7 @@ static int find_data_references(struct reloc_control *rc,
counted = 0;
else
counted = 1;
- rb_node = tree_search(blocks, leaf->start);
+ rb_node = simple_search(blocks, leaf->start);
if (rb_node) {
if (counted)
added = 1;
@@ -3743,7 +3706,7 @@ static int find_data_references(struct reloc_control *rc,
counted = 0;
else
counted = 1;
- rb_node = tree_search(blocks, leaf->start);
+ rb_node = simple_search(blocks, leaf->start);
if (rb_node) {
if (counted)
added = 1;
@@ -3787,8 +3750,8 @@ static int find_data_references(struct reloc_control *rc,
btrfs_item_key_to_cpu(leaf, &block->key, 0);
block->level = 0;
block->key_ready = 1;
- rb_node = tree_insert(blocks, block->bytenr,
- &block->rb_node);
+ rb_node = simple_insert(blocks, block->bytenr,
+ &block->rb_node);
if (rb_node)
backref_tree_panic(rb_node, -EEXIST,
block->bytenr);
--
2.25.1
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH 03/19] btrfs: relocation: Make reloc root search specific for relocation backref cache
2020-03-03 7:13 [PATCH 00/19] btrfs: Move generic backref cache build functions to backref.c Qu Wenruo
2020-03-03 7:13 ` [PATCH 01/19] btrfs: Move backref node/edge/cache structure to backref.h Qu Wenruo
2020-03-03 7:13 ` [PATCH 02/19] btrfs: Rename tree_entry to simple_node and export it Qu Wenruo
@ 2020-03-03 7:13 ` Qu Wenruo
2020-03-03 7:13 ` [PATCH 04/19] btrfs: relocation: Add backref_cache::pending_edge and backref_cache::useless_node members Qu Wenruo
` (17 subsequent siblings)
20 siblings, 0 replies; 25+ messages in thread
From: Qu Wenruo @ 2020-03-03 7:13 UTC (permalink / raw
To: linux-btrfs
find_reloc_root() searches reloc_control::reloc_root_tree to find the
reloc root.
This behavior is only useful for relocation backref cache.
For the incoming more generic purposed backref cache, we don't care
about who owns the reloc root, but only care if it's a reloc root.
So this patch makes the following modifications to make the reloc root
search more specific to relocation backref:
- Add backref_node::is_reloc_root
This will be an extra indicator for generic purposed backref cache.
User doesn't need to read root key from backref_node::root to
determine if it's a reloc root.
- Add backref_cache::is_reloc
This will allow backref cache code to do different behavior for
generic purposed backref cache and relocation backref cache.
- Make find_reloc_root() to accept fs_info
Just a personal taste.
- Export find_reloc_root()
So backref.c can utilize this function.
Signed-off-by: Qu Wenruo <wqu@suse.com>
---
fs/btrfs/backref.h | 14 ++++++++++++++
fs/btrfs/ctree.h | 2 ++
fs/btrfs/relocation.c | 23 +++++++++++++++--------
3 files changed, 31 insertions(+), 8 deletions(-)
diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h
index 923788fa03ef..fbb08b5429ca 100644
--- a/fs/btrfs/backref.h
+++ b/fs/btrfs/backref.h
@@ -221,6 +221,12 @@ struct backref_node {
* backref node.
*/
unsigned int detached:1;
+
+ /*
+ * For generic purpose backref cache, where we only care if it's a reloc
+ * root, doesn't care the source subvolid.
+ */
+ unsigned int is_reloc_root:1;
};
#define LOWER 0
@@ -266,6 +272,14 @@ struct backref_cache {
int nr_nodes;
int nr_edges;
+
+ /*
+ * Whether this cache is for relocation
+ *
+ * Reloction backref cache require more info for reloc root compared
+ * to generic backref cache.
+ */
+ unsigned int is_reloc;
};
#endif
diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index ea5d0675465a..b57bb3e5f1f2 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -3381,6 +3381,8 @@ void btrfs_reloc_pre_snapshot(struct btrfs_pending_snapshot *pending,
u64 *bytes_to_reserve);
int btrfs_reloc_post_snapshot(struct btrfs_trans_handle *trans,
struct btrfs_pending_snapshot *pending);
+struct btrfs_root *find_reloc_root(struct btrfs_fs_info *fs_info,
+ u64 bytenr);
/* scrub.c */
int btrfs_scrub_dev(struct btrfs_fs_info *fs_info, u64 devid, u64 start,
diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index 50348a58bb43..374efb117387 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -185,7 +185,7 @@ static void mapping_tree_init(struct mapping_tree *tree)
spin_lock_init(&tree->lock);
}
-static void backref_cache_init(struct backref_cache *cache)
+static void backref_cache_init(struct backref_cache *cache, int is_reloc)
{
int i;
cache->rb_root = RB_ROOT;
@@ -194,6 +194,7 @@ static void backref_cache_init(struct backref_cache *cache)
INIT_LIST_HEAD(&cache->changed);
INIT_LIST_HEAD(&cache->detached);
INIT_LIST_HEAD(&cache->leaves);
+ cache->is_reloc = is_reloc;
}
static void backref_cache_cleanup(struct backref_cache *cache)
@@ -543,13 +544,15 @@ static int should_ignore_root(struct btrfs_root *root)
/*
* find reloc tree by address of tree root
*/
-static struct btrfs_root *find_reloc_root(struct reloc_control *rc,
- u64 bytenr)
+struct btrfs_root *find_reloc_root(struct btrfs_fs_info *fs_info,
+ u64 bytenr)
{
+ struct reloc_control *rc = fs_info->reloc_ctl;
struct rb_node *rb_node;
struct mapping_node *node;
struct btrfs_root *root = NULL;
+ ASSERT(rc);
spin_lock(&rc->reloc_root_tree.lock);
rb_node = simple_search(&rc->reloc_root_tree.rb_root, bytenr);
if (rb_node) {
@@ -601,10 +604,14 @@ static int handle_one_tree_backref(struct reloc_control *rc,
/* Only reloc root uses backref pointing to itself */
if (ref_key->objectid == ref_key->offset) {
- root = find_reloc_root(rc, cur->bytenr);
- if (WARN_ON(!root))
- return -ENOENT;
- cur->root = root;
+ cur->is_reloc_root = 1;
+ /* Only reloc backref cache cares exact root */
+ if (cache->is_reloc) {
+ root = find_reloc_root(fs_info, cur->bytenr);
+ if (WARN_ON(!root))
+ return -ENOENT;
+ cur->root = root;
+ }
return 0;
}
@@ -4292,7 +4299,7 @@ static struct reloc_control *alloc_reloc_control(struct btrfs_fs_info *fs_info)
INIT_LIST_HEAD(&rc->reloc_roots);
INIT_LIST_HEAD(&rc->dirty_subvol_roots);
- backref_cache_init(&rc->backref_cache);
+ backref_cache_init(&rc->backref_cache, 1);
mapping_tree_init(&rc->reloc_root_tree);
extent_io_tree_init(fs_info, &rc->processed_blocks,
IO_TREE_RELOC_BLOCKS, NULL);
--
2.25.1
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH 04/19] btrfs: relocation: Add backref_cache::pending_edge and backref_cache::useless_node members
2020-03-03 7:13 [PATCH 00/19] btrfs: Move generic backref cache build functions to backref.c Qu Wenruo
` (2 preceding siblings ...)
2020-03-03 7:13 ` [PATCH 03/19] btrfs: relocation: Make reloc root search specific for relocation backref cache Qu Wenruo
@ 2020-03-03 7:13 ` Qu Wenruo
2020-03-03 7:13 ` [PATCH 05/19] btrfs: relocation: Add backref_cache::fs_info member Qu Wenruo
` (16 subsequent siblings)
20 siblings, 0 replies; 25+ messages in thread
From: Qu Wenruo @ 2020-03-03 7:13 UTC (permalink / raw
To: linux-btrfs
These two new members will act the same as the existing local lists,
@useless and @list in build_backref_tree().
This would kill two parameters for handle_one_tree_backref(),
handle_one_tree_block(), finish_upper_links() and
handle_useless_nodes().
Currently build_backref_tree() is only executed serially, thus moving
such local list into backref_cache is still safe.
Signed-off-by: Qu Wenruo <wqu@suse.com>
---
fs/btrfs/backref.h | 6 ++++
fs/btrfs/relocation.c | 64 ++++++++++++++++++++++++-------------------
2 files changed, 42 insertions(+), 28 deletions(-)
diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h
index fbb08b5429ca..4ad1193c78e0 100644
--- a/fs/btrfs/backref.h
+++ b/fs/btrfs/backref.h
@@ -280,6 +280,12 @@ struct backref_cache {
* to generic backref cache.
*/
unsigned int is_reloc;
+
+ /* 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;
};
#endif
diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index 374efb117387..413a83d1d9f1 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -195,6 +195,8 @@ static void backref_cache_init(struct backref_cache *cache, int is_reloc)
INIT_LIST_HEAD(&cache->detached);
INIT_LIST_HEAD(&cache->leaves);
cache->is_reloc = is_reloc;
+ INIT_LIST_HEAD(&cache->pending_edge);
+ INIT_LIST_HEAD(&cache->useless_node);
}
static void backref_cache_cleanup(struct backref_cache *cache)
@@ -218,6 +220,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));
@@ -576,8 +580,6 @@ static struct btrfs_root *read_fs_root(struct btrfs_fs_info *fs_info,
}
static int handle_one_tree_backref(struct reloc_control *rc,
- struct list_head *useless_node,
- struct list_head *pending_edge,
struct btrfs_path *path,
struct btrfs_key *ref_key,
struct btrfs_key *tree_key,
@@ -585,6 +587,8 @@ static int handle_one_tree_backref(struct reloc_control *rc,
{
struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;
struct backref_cache *cache = &rc->backref_cache;
+ struct list_head *useless_node = &cache->useless_node;
+ struct list_head *pending_edge = &cache->pending_edge;
struct backref_node *upper;
struct backref_node *lower;
struct backref_edge *edge;
@@ -774,13 +778,12 @@ static int handle_one_tree_backref(struct reloc_control *rc,
}
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 backref_cache *cache = &rc->backref_cache;
struct backref_edge *edge;
struct backref_node *exist;
int ret;
@@ -819,7 +822,7 @@ static int handle_one_tree_block(struct reloc_control *rc,
* check its backrefs
*/
if (!exist->checked)
- list_add_tail(&edge->list[UPPER], pending_edge);
+ list_add_tail(&edge->list[UPPER], &cache->pending_edge);
} else {
exist = NULL;
}
@@ -864,8 +867,7 @@ static int handle_one_tree_block(struct reloc_control *rc,
continue;
}
- ret = handle_one_tree_backref(rc, useless_node, pending_edge, path,
- &key, node_key, cur);
+ ret = handle_one_tree_backref(rc, path, &key, node_key, cur);
if (ret < 0)
goto out;
}
@@ -891,9 +893,9 @@ static int handle_one_tree_block(struct reloc_control *rc,
* 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)
+ struct backref_node *start)
{
+ struct list_head *useless_node = &cache->useless_node;
struct backref_edge *edge;
LIST_HEAD(pending_edge);
@@ -992,10 +994,10 @@ static int finish_upper_links(struct backref_cache *cache,
* Return true if @node is in the @useless_nodes list.
*/
static bool handle_useless_nodes(struct reloc_control *rc,
- struct list_head *useless_nodes,
struct backref_node *node)
{
struct backref_cache *cache = &rc->backref_cache;
+ struct list_head *useless_nodes = &cache->useless_node;
bool ret = false;
while (!list_empty(useless_nodes)) {
@@ -1080,11 +1082,12 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
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 ret;
int err = 0;
+ ASSERT(list_empty(&cache->useless_node) &&
+ list_empty(&cache->pending_edge));
+
iter = btrfs_backref_iter_alloc(rc->extent_root->fs_info, GFP_NOFS);
if (!iter)
return ERR_PTR(-ENOMEM);
@@ -1106,15 +1109,15 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
/* Breadth-first search to build backref cache */
while (1) {
- ret = handle_one_tree_block(rc, &useless, &list, path, iter,
- node_key, cur);
+ ret = handle_one_tree_block(rc, 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]);
+ 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];
} else {
@@ -1136,26 +1139,26 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
}
/* Finish the upper linkage of newly added edges/nodes */
- ret = finish_upper_links(cache, node, &useless);
+ ret = finish_upper_links(cache, node);
if (ret < 0) {
err = ret;
goto out;
}
- if (handle_useless_nodes(rc, &useless, node))
+ if (handle_useless_nodes(rc, node))
node = NULL;
out:
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];
@@ -1168,20 +1171,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_entry(cache->useless_node.next,
struct backref_node, list);
list_del_init(&lower->list);
if (lower == node)
@@ -1190,9 +1194,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.1
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH 05/19] btrfs: relocation: Add backref_cache::fs_info member
2020-03-03 7:13 [PATCH 00/19] btrfs: Move generic backref cache build functions to backref.c Qu Wenruo
` (3 preceding siblings ...)
2020-03-03 7:13 ` [PATCH 04/19] btrfs: relocation: Add backref_cache::pending_edge and backref_cache::useless_node members Qu Wenruo
@ 2020-03-03 7:13 ` Qu Wenruo
2020-03-03 7:13 ` [PATCH 06/19] btrfs: Move backref_cache_init() to backref.c Qu Wenruo
` (15 subsequent siblings)
20 siblings, 0 replies; 25+ messages in thread
From: Qu Wenruo @ 2020-03-03 7:13 UTC (permalink / raw
To: linux-btrfs
Add this member so that we can grab fs_info without the help from
reloc_control.
Signed-off-by: Qu Wenruo <wqu@suse.com>
---
fs/btrfs/backref.h | 2 ++
fs/btrfs/relocation.c | 18 +++++++++---------
2 files changed, 11 insertions(+), 9 deletions(-)
diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h
index 4ad1193c78e0..e1438425cf59 100644
--- a/fs/btrfs/backref.h
+++ b/fs/btrfs/backref.h
@@ -286,6 +286,8 @@ struct backref_cache {
/* The list of useless backref nodes during backref cache build */
struct list_head useless_node;
+
+ struct btrfs_fs_info *fs_info;
};
#endif
diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index 413a83d1d9f1..0fb9ceb2665e 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -185,10 +185,12 @@ static void mapping_tree_init(struct mapping_tree *tree)
spin_lock_init(&tree->lock);
}
-static void backref_cache_init(struct backref_cache *cache, int is_reloc)
+static void backref_cache_init(struct btrfs_fs_info *fs_info,
+ struct backref_cache *cache, int is_reloc)
{
int i;
cache->rb_root = RB_ROOT;
+ cache->fs_info = fs_info;
for (i = 0; i < BTRFS_MAX_LEVEL; i++)
INIT_LIST_HEAD(&cache->pending[i]);
INIT_LIST_HEAD(&cache->changed);
@@ -579,14 +581,13 @@ static struct btrfs_root *read_fs_root(struct btrfs_fs_info *fs_info,
return btrfs_get_fs_root(fs_info, &key, false);
}
-static int handle_one_tree_backref(struct reloc_control *rc,
+static int handle_one_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 = rc->extent_root->fs_info;
- struct backref_cache *cache = &rc->backref_cache;
+ struct btrfs_fs_info *fs_info = cache->fs_info;
struct list_head *useless_node = &cache->useless_node;
struct list_head *pending_edge = &cache->pending_edge;
struct backref_node *upper;
@@ -777,13 +778,12 @@ static int handle_one_tree_backref(struct reloc_control *rc,
return ret;
}
-static int handle_one_tree_block(struct reloc_control *rc,
+static int handle_one_tree_block(struct backref_cache *cache,
struct btrfs_path *path,
struct btrfs_backref_iter *iter,
struct btrfs_key *node_key,
struct backref_node *cur)
{
- struct backref_cache *cache = &rc->backref_cache;
struct backref_edge *edge;
struct backref_node *exist;
int ret;
@@ -867,7 +867,7 @@ static int handle_one_tree_block(struct reloc_control *rc,
continue;
}
- ret = handle_one_tree_backref(rc, path, &key, node_key, cur);
+ ret = handle_one_tree_backref(cache, path, &key, node_key, cur);
if (ret < 0)
goto out;
}
@@ -1109,7 +1109,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
/* Breadth-first search to build backref cache */
while (1) {
- ret = handle_one_tree_block(rc, path, iter, node_key, cur);
+ ret = handle_one_tree_block(cache, path, iter, node_key, cur);
if (ret < 0) {
err = ret;
goto out;
@@ -4307,7 +4307,7 @@ static struct reloc_control *alloc_reloc_control(struct btrfs_fs_info *fs_info)
INIT_LIST_HEAD(&rc->reloc_roots);
INIT_LIST_HEAD(&rc->dirty_subvol_roots);
- backref_cache_init(&rc->backref_cache, 1);
+ backref_cache_init(fs_info, &rc->backref_cache, 1);
mapping_tree_init(&rc->reloc_root_tree);
extent_io_tree_init(fs_info, &rc->processed_blocks,
IO_TREE_RELOC_BLOCKS, NULL);
--
2.25.1
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH 06/19] btrfs: Move backref_cache_init() to backref.c
2020-03-03 7:13 [PATCH 00/19] btrfs: Move generic backref cache build functions to backref.c Qu Wenruo
` (4 preceding siblings ...)
2020-03-03 7:13 ` [PATCH 05/19] btrfs: relocation: Add backref_cache::fs_info member Qu Wenruo
@ 2020-03-03 7:13 ` Qu Wenruo
2020-03-03 7:13 ` [PATCH 07/19] btrfs: Move alloc_backref_node() " Qu Wenruo
` (14 subsequent siblings)
20 siblings, 0 replies; 25+ messages in thread
From: Qu Wenruo @ 2020-03-03 7:13 UTC (permalink / raw
To: linux-btrfs
Signed-off-by: Qu Wenruo <wqu@suse.com>
---
fs/btrfs/backref.c | 16 ++++++++++++++++
fs/btrfs/backref.h | 2 ++
fs/btrfs/relocation.c | 16 ----------------
3 files changed, 18 insertions(+), 16 deletions(-)
diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index 01674be3beaa..8fc1d520695e 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -2444,3 +2444,19 @@ int btrfs_backref_iter_next(struct btrfs_backref_iter *iter)
path->slots[0]);
return 0;
}
+
+void backref_cache_init(struct btrfs_fs_info *fs_info,
+ struct backref_cache *cache, int is_reloc)
+{
+ int i;
+ cache->rb_root = RB_ROOT;
+ cache->fs_info = fs_info;
+ for (i = 0; i < BTRFS_MAX_LEVEL; i++)
+ INIT_LIST_HEAD(&cache->pending[i]);
+ INIT_LIST_HEAD(&cache->changed);
+ INIT_LIST_HEAD(&cache->detached);
+ INIT_LIST_HEAD(&cache->leaves);
+ cache->is_reloc = is_reloc;
+ INIT_LIST_HEAD(&cache->pending_edge);
+ INIT_LIST_HEAD(&cache->useless_node);
+}
diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h
index e1438425cf59..65e886fb2008 100644
--- a/fs/btrfs/backref.h
+++ b/fs/btrfs/backref.h
@@ -290,4 +290,6 @@ struct backref_cache {
struct btrfs_fs_info *fs_info;
};
+void backref_cache_init(struct btrfs_fs_info *fs_info,
+ struct backref_cache *cache, int is_reloc);
#endif
diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index 0fb9ceb2665e..4ec2946f95ae 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -185,22 +185,6 @@ static void mapping_tree_init(struct mapping_tree *tree)
spin_lock_init(&tree->lock);
}
-static void backref_cache_init(struct btrfs_fs_info *fs_info,
- struct backref_cache *cache, int is_reloc)
-{
- int i;
- cache->rb_root = RB_ROOT;
- cache->fs_info = fs_info;
- for (i = 0; i < BTRFS_MAX_LEVEL; i++)
- INIT_LIST_HEAD(&cache->pending[i]);
- INIT_LIST_HEAD(&cache->changed);
- INIT_LIST_HEAD(&cache->detached);
- INIT_LIST_HEAD(&cache->leaves);
- cache->is_reloc = is_reloc;
- INIT_LIST_HEAD(&cache->pending_edge);
- INIT_LIST_HEAD(&cache->useless_node);
-}
-
static void backref_cache_cleanup(struct backref_cache *cache)
{
struct backref_node *node;
--
2.25.1
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH 07/19] btrfs: Move alloc_backref_node() to backref.c
2020-03-03 7:13 [PATCH 00/19] btrfs: Move generic backref cache build functions to backref.c Qu Wenruo
` (5 preceding siblings ...)
2020-03-03 7:13 ` [PATCH 06/19] btrfs: Move backref_cache_init() to backref.c Qu Wenruo
@ 2020-03-03 7:13 ` Qu Wenruo
2020-03-03 7:13 ` [PATCH 08/19] btrfs: Move alloc_backref_edge() " Qu Wenruo
` (13 subsequent siblings)
20 siblings, 0 replies; 25+ messages in thread
From: Qu Wenruo @ 2020-03-03 7:13 UTC (permalink / raw
To: linux-btrfs
Signed-off-by: Qu Wenruo <wqu@suse.com>
---
fs/btrfs/backref.c | 20 ++++++++++++++++++++
fs/btrfs/backref.h | 2 ++
fs/btrfs/relocation.c | 20 --------------------
3 files changed, 22 insertions(+), 20 deletions(-)
diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index 8fc1d520695e..b6183cb7c60b 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -2460,3 +2460,23 @@ void backref_cache_init(struct btrfs_fs_info *fs_info,
INIT_LIST_HEAD(&cache->pending_edge);
INIT_LIST_HEAD(&cache->useless_node);
}
+
+struct backref_node *alloc_backref_node(struct backref_cache *cache,
+ u64 bytenr, int level)
+{
+ struct backref_node *node;
+
+ ASSERT(level >= 0 && level < BTRFS_MAX_LEVEL);
+ node = kzalloc(sizeof(*node), GFP_NOFS);
+ if (node) {
+ INIT_LIST_HEAD(&node->list);
+ INIT_LIST_HEAD(&node->upper);
+ INIT_LIST_HEAD(&node->lower);
+ RB_CLEAR_NODE(&node->rb_node);
+ cache->nr_nodes++;
+
+ node->level = level;
+ node->bytenr = bytenr;
+ }
+ return node;
+}
diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h
index 65e886fb2008..b7aad5f116ae 100644
--- a/fs/btrfs/backref.h
+++ b/fs/btrfs/backref.h
@@ -292,4 +292,6 @@ struct backref_cache {
void backref_cache_init(struct btrfs_fs_info *fs_info,
struct backref_cache *cache, int is_reloc);
+struct backref_node *alloc_backref_node(struct backref_cache *cache,
+ u64 bytenr, int level);
#endif
diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index 4ec2946f95ae..f97ff88dba21 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -215,26 +215,6 @@ static void backref_cache_cleanup(struct backref_cache *cache)
ASSERT(!cache->nr_edges);
}
-static struct backref_node *alloc_backref_node(struct backref_cache *cache,
- u64 bytenr, int level)
-{
- struct backref_node *node;
-
- ASSERT(level >= 0 && level < BTRFS_MAX_LEVEL);
- node = kzalloc(sizeof(*node), GFP_NOFS);
- if (node) {
- INIT_LIST_HEAD(&node->list);
- INIT_LIST_HEAD(&node->upper);
- INIT_LIST_HEAD(&node->lower);
- RB_CLEAR_NODE(&node->rb_node);
- cache->nr_nodes++;
-
- node->level = level;
- node->bytenr = bytenr;
- }
- return node;
-}
-
static void free_backref_node(struct backref_cache *cache,
struct backref_node *node)
{
--
2.25.1
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH 08/19] btrfs: Move alloc_backref_edge() to backref.c
2020-03-03 7:13 [PATCH 00/19] btrfs: Move generic backref cache build functions to backref.c Qu Wenruo
` (6 preceding siblings ...)
2020-03-03 7:13 ` [PATCH 07/19] btrfs: Move alloc_backref_node() " Qu Wenruo
@ 2020-03-03 7:13 ` Qu Wenruo
2020-03-03 7:13 ` [PATCH 09/19] btrfs: Move link_backref_edge() " Qu Wenruo
` (12 subsequent siblings)
20 siblings, 0 replies; 25+ messages in thread
From: Qu Wenruo @ 2020-03-03 7:13 UTC (permalink / raw
To: linux-btrfs
Signed-off-by: Qu Wenruo <wqu@suse.com>
---
fs/btrfs/backref.c | 10 ++++++++++
fs/btrfs/backref.h | 1 +
fs/btrfs/relocation.c | 10 ----------
3 files changed, 11 insertions(+), 10 deletions(-)
diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index b6183cb7c60b..7511ce8447e8 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -2480,3 +2480,13 @@ struct backref_node *alloc_backref_node(struct backref_cache *cache,
}
return node;
}
+
+struct backref_edge *alloc_backref_edge(struct backref_cache *cache)
+{
+ struct backref_edge *edge;
+
+ edge = kzalloc(sizeof(*edge), GFP_NOFS);
+ if (edge)
+ cache->nr_edges++;
+ return edge;
+}
diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h
index b7aad5f116ae..04efc9d44bb8 100644
--- a/fs/btrfs/backref.h
+++ b/fs/btrfs/backref.h
@@ -294,4 +294,5 @@ void backref_cache_init(struct btrfs_fs_info *fs_info,
struct backref_cache *cache, int is_reloc);
struct backref_node *alloc_backref_node(struct backref_cache *cache,
u64 bytenr, int level);
+struct backref_edge *alloc_backref_edge(struct backref_cache *cache);
#endif
diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index f97ff88dba21..1f4fccd973d1 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -225,16 +225,6 @@ static void free_backref_node(struct backref_cache *cache,
}
}
-static struct backref_edge *alloc_backref_edge(struct backref_cache *cache)
-{
- struct backref_edge *edge;
-
- edge = kzalloc(sizeof(*edge), GFP_NOFS);
- if (edge)
- cache->nr_edges++;
- return edge;
-}
-
#define LINK_LOWER (1 << 0)
#define LINK_UPPER (1 << 1)
static inline void link_backref_edge(struct backref_edge *edge,
--
2.25.1
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH 09/19] btrfs: Move link_backref_edge() to backref.c
2020-03-03 7:13 [PATCH 00/19] btrfs: Move generic backref cache build functions to backref.c Qu Wenruo
` (7 preceding siblings ...)
2020-03-03 7:13 ` [PATCH 08/19] btrfs: Move alloc_backref_edge() " Qu Wenruo
@ 2020-03-03 7:13 ` Qu Wenruo
2020-03-03 7:14 ` [PATCH 10/19] btrfs: Move free_backref_node() and free_backref_edge() to backref.h Qu Wenruo
` (11 subsequent siblings)
20 siblings, 0 replies; 25+ messages in thread
From: Qu Wenruo @ 2020-03-03 7:13 UTC (permalink / raw
To: linux-btrfs
Signed-off-by: Qu Wenruo <wqu@suse.com>
---
fs/btrfs/backref.h | 16 ++++++++++++++++
fs/btrfs/relocation.c | 16 ----------------
2 files changed, 16 insertions(+), 16 deletions(-)
diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h
index 04efc9d44bb8..431c8a15c5f9 100644
--- a/fs/btrfs/backref.h
+++ b/fs/btrfs/backref.h
@@ -295,4 +295,20 @@ void backref_cache_init(struct btrfs_fs_info *fs_info,
struct backref_node *alloc_backref_node(struct backref_cache *cache,
u64 bytenr, int level);
struct backref_edge *alloc_backref_edge(struct backref_cache *cache);
+
+#define LINK_LOWER (1 << 0)
+#define LINK_UPPER (1 << 1)
+static inline void link_backref_edge(struct backref_edge *edge,
+ struct backref_node *lower,
+ struct backref_node *upper,
+ int link_which)
+{
+ ASSERT(upper && lower && upper->level == lower->level + 1);
+ edge->node[LOWER] = lower;
+ edge->node[UPPER] = upper;
+ if (link_which & LINK_LOWER)
+ list_add_tail(&edge->list[LOWER], &lower->upper);
+ if (link_which & LINK_UPPER)
+ list_add_tail(&edge->list[UPPER], &upper->lower);
+}
#endif
diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index 1f4fccd973d1..dfcedd7824bc 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -225,22 +225,6 @@ static void free_backref_node(struct backref_cache *cache,
}
}
-#define LINK_LOWER (1 << 0)
-#define LINK_UPPER (1 << 1)
-static inline void link_backref_edge(struct backref_edge *edge,
- struct backref_node *lower,
- struct backref_node *upper,
- int link_which)
-{
- ASSERT(upper && lower && upper->level == lower->level + 1);
- edge->node[LOWER] = lower;
- edge->node[UPPER] = upper;
- if (link_which & LINK_LOWER)
- list_add_tail(&edge->list[LOWER], &lower->upper);
- if (link_which & LINK_UPPER)
- list_add_tail(&edge->list[UPPER], &upper->lower);
-}
-
static void free_backref_edge(struct backref_cache *cache,
struct backref_edge *edge)
{
--
2.25.1
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH 10/19] btrfs: Move free_backref_node() and free_backref_edge() to backref.h
2020-03-03 7:13 [PATCH 00/19] btrfs: Move generic backref cache build functions to backref.c Qu Wenruo
` (8 preceding siblings ...)
2020-03-03 7:13 ` [PATCH 09/19] btrfs: Move link_backref_edge() " Qu Wenruo
@ 2020-03-03 7:14 ` Qu Wenruo
2020-03-03 7:14 ` [PATCH 11/19] btrfs: Move drop_backref_node() and needed facilities " Qu Wenruo
` (10 subsequent siblings)
20 siblings, 0 replies; 25+ messages in thread
From: Qu Wenruo @ 2020-03-03 7:14 UTC (permalink / raw
To: linux-btrfs
Signed-off-by: Qu Wenruo <wqu@suse.com>
---
fs/btrfs/backref.h | 20 ++++++++++++++++++++
fs/btrfs/relocation.c | 19 -------------------
2 files changed, 20 insertions(+), 19 deletions(-)
diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h
index 431c8a15c5f9..d8492846a961 100644
--- a/fs/btrfs/backref.h
+++ b/fs/btrfs/backref.h
@@ -8,6 +8,7 @@
#include <linux/btrfs.h>
#include "ulist.h"
+#include "disk-io.h"
#include "extent_io.h"
struct inode_fs_paths {
@@ -311,4 +312,23 @@ static inline void link_backref_edge(struct backref_edge *edge,
if (link_which & LINK_UPPER)
list_add_tail(&edge->list[UPPER], &upper->lower);
}
+static inline void free_backref_node(struct backref_cache *cache,
+ struct backref_node *node)
+{
+ if (node) {
+ cache->nr_nodes--;
+ btrfs_put_root(node->root);
+ kfree(node);
+ }
+}
+
+static inline void free_backref_edge(struct backref_cache *cache,
+ struct backref_edge *edge)
+{
+ if (edge) {
+ cache->nr_edges--;
+ kfree(edge);
+ }
+}
+
#endif
diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index dfcedd7824bc..43b1bab2f51f 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -215,25 +215,6 @@ static void backref_cache_cleanup(struct backref_cache *cache)
ASSERT(!cache->nr_edges);
}
-static void free_backref_node(struct backref_cache *cache,
- struct backref_node *node)
-{
- if (node) {
- cache->nr_nodes--;
- btrfs_put_root(node->root);
- kfree(node);
- }
-}
-
-static void free_backref_edge(struct backref_cache *cache,
- struct backref_edge *edge)
-{
- if (edge) {
- cache->nr_edges--;
- kfree(edge);
- }
-}
-
static void backref_tree_panic(struct rb_node *rb_node, int errno, u64 bytenr)
{
--
2.25.1
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH 11/19] btrfs: Move drop_backref_node() and needed facilities to backref.h
2020-03-03 7:13 [PATCH 00/19] btrfs: Move generic backref cache build functions to backref.c Qu Wenruo
` (9 preceding siblings ...)
2020-03-03 7:14 ` [PATCH 10/19] btrfs: Move free_backref_node() and free_backref_edge() to backref.h Qu Wenruo
@ 2020-03-03 7:14 ` Qu Wenruo
2020-03-03 7:14 ` [PATCH 12/19] btrfs: Rename remove_backref_node() to cleanup_backref_node() and move it to backref.c Qu Wenruo
` (9 subsequent siblings)
20 siblings, 0 replies; 25+ messages in thread
From: Qu Wenruo @ 2020-03-03 7:14 UTC (permalink / raw
To: linux-btrfs
With extra comment for drop_backref_node() as it has some similarity
with remove_backref_node(), thus we need extra comment explaining the
difference.
Signed-off-by: Qu Wenruo <wqu@suse.com>
---
fs/btrfs/backref.h | 37 +++++++++++++++++++++++++++++++++++++
fs/btrfs/relocation.c | 31 -------------------------------
2 files changed, 37 insertions(+), 31 deletions(-)
diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h
index d8492846a961..7b8bf4e13d99 100644
--- a/fs/btrfs/backref.h
+++ b/fs/btrfs/backref.h
@@ -331,4 +331,41 @@ static inline void free_backref_edge(struct backref_cache *cache,
}
}
+static inline void unlock_node_buffer(struct backref_node *node)
+{
+ if (node->locked) {
+ btrfs_tree_unlock(node->eb);
+ node->locked = 0;
+ }
+}
+
+static inline void drop_node_buffer(struct backref_node *node)
+{
+ if (node->eb) {
+ unlock_node_buffer(node);
+ free_extent_buffer(node->eb);
+ node->eb = NULL;
+ }
+}
+
+/*
+ * Drop the backref node from cache without cleaning up its children
+ * edges.
+ *
+ * This can only be called on node without parent edges.
+ * The children edges are still kept as is.
+ */
+static inline void drop_backref_node(struct backref_cache *tree,
+ struct backref_node *node)
+{
+ BUG_ON(!list_empty(&node->upper));
+
+ drop_node_buffer(node);
+ list_del(&node->list);
+ list_del(&node->lower);
+ if (!RB_EMPTY_NODE(&node->rb_node))
+ rb_erase(&node->rb_node, &tree->rb_root);
+ free_backref_node(tree, node);
+}
+
#endif
diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index 43b1bab2f51f..1c038428990c 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -275,37 +275,6 @@ static struct backref_node *walk_down_backref(struct backref_edge *edges[],
*index = 0;
return NULL;
}
-
-static void unlock_node_buffer(struct backref_node *node)
-{
- if (node->locked) {
- btrfs_tree_unlock(node->eb);
- node->locked = 0;
- }
-}
-
-static void drop_node_buffer(struct backref_node *node)
-{
- if (node->eb) {
- unlock_node_buffer(node);
- free_extent_buffer(node->eb);
- node->eb = NULL;
- }
-}
-
-static void drop_backref_node(struct backref_cache *tree,
- struct backref_node *node)
-{
- BUG_ON(!list_empty(&node->upper));
-
- drop_node_buffer(node);
- list_del(&node->list);
- list_del(&node->lower);
- if (!RB_EMPTY_NODE(&node->rb_node))
- rb_erase(&node->rb_node, &tree->rb_root);
- free_backref_node(tree, node);
-}
-
/*
* remove a backref node from the backref cache
*/
--
2.25.1
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH 12/19] btrfs: Rename remove_backref_node() to cleanup_backref_node() and move it to backref.c
2020-03-03 7:13 [PATCH 00/19] btrfs: Move generic backref cache build functions to backref.c Qu Wenruo
` (10 preceding siblings ...)
2020-03-03 7:14 ` [PATCH 11/19] btrfs: Move drop_backref_node() and needed facilities " Qu Wenruo
@ 2020-03-03 7:14 ` Qu Wenruo
2020-03-03 7:14 ` [PATCH 13/19] btrfs: Move backref_cache_cleanup() " Qu Wenruo
` (8 subsequent siblings)
20 siblings, 0 replies; 25+ messages in thread
From: Qu Wenruo @ 2020-03-03 7:14 UTC (permalink / raw
To: linux-btrfs
Also add comment explaining the cleanup progress, to differ it from
drop_backref_node().
Signed-off-by: Qu Wenruo <wqu@suse.com>
---
fs/btrfs/backref.c | 38 ++++++++++++++++++++++++++++++++
fs/btrfs/backref.h | 9 ++++++++
fs/btrfs/relocation.c | 51 ++++---------------------------------------
3 files changed, 51 insertions(+), 47 deletions(-)
diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index 7511ce8447e8..4f0e8ab1d9cf 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -2490,3 +2490,41 @@ struct backref_edge *alloc_backref_edge(struct backref_cache *cache)
cache->nr_edges++;
return edge;
}
+
+void cleanup_backref_node(struct backref_cache *cache,
+ struct backref_node *node)
+{
+ struct backref_node *upper;
+ struct backref_edge *edge;
+
+ if (!node)
+ return;
+
+ BUG_ON(!node->lowest && !node->detached);
+ while (!list_empty(&node->upper)) {
+ edge = list_entry(node->upper.next, struct backref_edge,
+ list[LOWER]);
+ upper = edge->node[UPPER];
+ list_del(&edge->list[LOWER]);
+ list_del(&edge->list[UPPER]);
+ free_backref_edge(cache, edge);
+
+ if (RB_EMPTY_NODE(&upper->rb_node)) {
+ BUG_ON(!list_empty(&node->upper));
+ drop_backref_node(cache, node);
+ node = upper;
+ node->lowest = 1;
+ continue;
+ }
+ /*
+ * add the node to leaf node list if no other
+ * child block cached.
+ */
+ if (list_empty(&upper->lower)) {
+ list_add_tail(&upper->lower, &cache->leaves);
+ upper->lowest = 1;
+ }
+ }
+
+ drop_backref_node(cache, node);
+}
diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h
index 7b8bf4e13d99..1c34a8dbee2f 100644
--- a/fs/btrfs/backref.h
+++ b/fs/btrfs/backref.h
@@ -368,4 +368,13 @@ static inline void drop_backref_node(struct backref_cache *tree,
free_backref_node(tree, node);
}
+/*
+ * Drop the backref node from cache, also cleaning up all its
+ * upper edges and any uncached nodes in the path.
+ *
+ * This cleanup happens bottom up, thus the node should either
+ * be the lowest node in the cache or detached node.
+ */
+void cleanup_backref_node(struct backref_cache *cache,
+ struct backref_node *node);
#endif
diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index 1c038428990c..2050414884fb 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -161,9 +161,6 @@ struct reloc_control {
#define MOVE_DATA_EXTENTS 0
#define UPDATE_DATA_PTRS 1
-static void remove_backref_node(struct backref_cache *cache,
- struct backref_node *node);
-
static void mark_block_processed(struct reloc_control *rc,
struct backref_node *node)
{
@@ -193,13 +190,13 @@ static void backref_cache_cleanup(struct backref_cache *cache)
while (!list_empty(&cache->detached)) {
node = list_entry(cache->detached.next,
struct backref_node, list);
- remove_backref_node(cache, node);
+ cleanup_backref_node(cache, node);
}
while (!list_empty(&cache->leaves)) {
node = list_entry(cache->leaves.next,
struct backref_node, lower);
- remove_backref_node(cache, node);
+ cleanup_backref_node(cache, node);
}
cache->last_trans = 0;
@@ -275,46 +272,6 @@ static struct backref_node *walk_down_backref(struct backref_edge *edges[],
*index = 0;
return NULL;
}
-/*
- * remove a backref node from the backref cache
- */
-static void remove_backref_node(struct backref_cache *cache,
- struct backref_node *node)
-{
- struct backref_node *upper;
- struct backref_edge *edge;
-
- if (!node)
- return;
-
- BUG_ON(!node->lowest && !node->detached);
- while (!list_empty(&node->upper)) {
- edge = list_entry(node->upper.next, struct backref_edge,
- list[LOWER]);
- upper = edge->node[UPPER];
- list_del(&edge->list[LOWER]);
- list_del(&edge->list[UPPER]);
- free_backref_edge(cache, edge);
-
- if (RB_EMPTY_NODE(&upper->rb_node)) {
- BUG_ON(!list_empty(&node->upper));
- drop_backref_node(cache, node);
- node = upper;
- node->lowest = 1;
- continue;
- }
- /*
- * add the node to leaf node list if no other
- * child block cached.
- */
- if (list_empty(&upper->lower)) {
- list_add_tail(&upper->lower, &cache->leaves);
- upper->lowest = 1;
- }
- }
-
- drop_backref_node(cache, node);
-}
static void update_backref_node(struct backref_cache *cache,
struct backref_node *node, u64 bytenr)
@@ -352,7 +309,7 @@ static int update_backref_cache(struct btrfs_trans_handle *trans,
while (!list_empty(&cache->detached)) {
node = list_entry(cache->detached.next,
struct backref_node, list);
- remove_backref_node(cache, node);
+ cleanup_backref_node(cache, node);
}
while (!list_empty(&cache->changed)) {
@@ -2989,7 +2946,7 @@ static int relocate_tree_block(struct btrfs_trans_handle *trans,
}
out:
if (ret || node->level == 0 || node->cowonly)
- remove_backref_node(&rc->backref_cache, node);
+ cleanup_backref_node(&rc->backref_cache, node);
return ret;
}
--
2.25.1
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH 13/19] btrfs: Move backref_cache_cleanup() to backref.c
2020-03-03 7:13 [PATCH 00/19] btrfs: Move generic backref cache build functions to backref.c Qu Wenruo
` (11 preceding siblings ...)
2020-03-03 7:14 ` [PATCH 12/19] btrfs: Rename remove_backref_node() to cleanup_backref_node() and move it to backref.c Qu Wenruo
@ 2020-03-03 7:14 ` Qu Wenruo
2020-03-03 7:14 ` [PATCH 14/19] btrfs: Rename backref_tree_panic() to backref_cache_panic(), and move it " Qu Wenruo
` (7 subsequent siblings)
20 siblings, 0 replies; 25+ messages in thread
From: Qu Wenruo @ 2020-03-03 7:14 UTC (permalink / raw
To: linux-btrfs
Signed-off-by: Qu Wenruo <wqu@suse.com>
---
fs/btrfs/backref.c | 30 ++++++++++++++++++++++++++++++
fs/btrfs/backref.h | 1 +
fs/btrfs/relocation.c | 30 ------------------------------
3 files changed, 31 insertions(+), 30 deletions(-)
diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index 4f0e8ab1d9cf..02455b3bbc35 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -2528,3 +2528,33 @@ void cleanup_backref_node(struct backref_cache *cache,
drop_backref_node(cache, node);
}
+
+void backref_cache_cleanup(struct backref_cache *cache)
+{
+ struct backref_node *node;
+ int i;
+
+ while (!list_empty(&cache->detached)) {
+ node = list_entry(cache->detached.next,
+ struct backref_node, list);
+ cleanup_backref_node(cache, node);
+ }
+
+ while (!list_empty(&cache->leaves)) {
+ node = list_entry(cache->leaves.next,
+ struct backref_node, lower);
+ cleanup_backref_node(cache, node);
+ }
+
+ cache->last_trans = 0;
+
+ 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));
+ ASSERT(!cache->nr_nodes);
+ ASSERT(!cache->nr_edges);
+}
diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h
index 1c34a8dbee2f..2fb854b1d5f0 100644
--- a/fs/btrfs/backref.h
+++ b/fs/btrfs/backref.h
@@ -377,4 +377,5 @@ static inline void drop_backref_node(struct backref_cache *tree,
*/
void cleanup_backref_node(struct backref_cache *cache,
struct backref_node *node);
+void backref_cache_cleanup(struct backref_cache *cache);
#endif
diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index 2050414884fb..71df172b70bb 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -182,36 +182,6 @@ static void mapping_tree_init(struct mapping_tree *tree)
spin_lock_init(&tree->lock);
}
-static void backref_cache_cleanup(struct backref_cache *cache)
-{
- struct backref_node *node;
- int i;
-
- while (!list_empty(&cache->detached)) {
- node = list_entry(cache->detached.next,
- struct backref_node, list);
- cleanup_backref_node(cache, node);
- }
-
- while (!list_empty(&cache->leaves)) {
- node = list_entry(cache->leaves.next,
- struct backref_node, lower);
- cleanup_backref_node(cache, node);
- }
-
- cache->last_trans = 0;
-
- 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));
- ASSERT(!cache->nr_nodes);
- ASSERT(!cache->nr_edges);
-}
-
static void backref_tree_panic(struct rb_node *rb_node, int errno, u64 bytenr)
{
--
2.25.1
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH 14/19] btrfs: Rename backref_tree_panic() to backref_cache_panic(), and move it to backref.c
2020-03-03 7:13 [PATCH 00/19] btrfs: Move generic backref cache build functions to backref.c Qu Wenruo
` (12 preceding siblings ...)
2020-03-03 7:14 ` [PATCH 13/19] btrfs: Move backref_cache_cleanup() " Qu Wenruo
@ 2020-03-03 7:14 ` Qu Wenruo
2020-03-03 7:14 ` [PATCH 15/19] btrfs: Rename should_ignore_root() to should_ignore_reloc_root() and export it Qu Wenruo
` (6 subsequent siblings)
20 siblings, 0 replies; 25+ messages in thread
From: Qu Wenruo @ 2020-03-03 7:14 UTC (permalink / raw
To: linux-btrfs
Also change the parameter, since all callers can easily grab an fs_info,
there is no need for all the dancing.
Signed-off-by: Qu Wenruo <wqu@suse.com>
---
fs/btrfs/backref.h | 8 ++++++++
fs/btrfs/relocation.c | 33 +++++++++++----------------------
2 files changed, 19 insertions(+), 22 deletions(-)
diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h
index 2fb854b1d5f0..4a4c9070a38b 100644
--- a/fs/btrfs/backref.h
+++ b/fs/btrfs/backref.h
@@ -378,4 +378,12 @@ static inline void drop_backref_node(struct backref_cache *tree,
void cleanup_backref_node(struct backref_cache *cache,
struct backref_node *node);
void backref_cache_cleanup(struct backref_cache *cache);
+
+static inline void backref_cache_panic(struct btrfs_fs_info *fs_info,
+ u64 bytenr, int errno)
+{
+ btrfs_panic(fs_info, errno,
+ "Inconsistency in backref cache found at offset %llu",
+ bytenr);
+}
#endif
diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index 71df172b70bb..349e8e761e8d 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -182,19 +182,6 @@ static void mapping_tree_init(struct mapping_tree *tree)
spin_lock_init(&tree->lock);
}
-static void backref_tree_panic(struct rb_node *rb_node, int errno, u64 bytenr)
-{
-
- struct btrfs_fs_info *fs_info = NULL;
- struct backref_node *bnode = rb_entry(rb_node, struct backref_node,
- rb_node);
- if (bnode->root)
- fs_info = bnode->root->fs_info;
- btrfs_panic(fs_info, errno,
- "Inconsistency in backref cache found at offset %llu",
- bytenr);
-}
-
/*
* walk up backref nodes until reach node presents tree root
*/
@@ -251,7 +238,7 @@ static void update_backref_node(struct backref_cache *cache,
node->bytenr = bytenr;
rb_node = simple_insert(&cache->rb_root, node->bytenr, &node->rb_node);
if (rb_node)
- backref_tree_panic(rb_node, -EEXIST, bytenr);
+ backref_cache_panic(cache->fs_info, bytenr, -EEXIST);
}
/*
@@ -778,8 +765,8 @@ static int finish_upper_links(struct backref_cache *cache,
rb_node = simple_insert(&cache->rb_root, upper->bytenr,
&upper->rb_node);
if (rb_node) {
- backref_tree_panic(rb_node, -EEXIST,
- upper->bytenr);
+ backref_cache_panic(cache->fs_info,
+ upper->bytenr, -EEXIST);
return -EUCLEAN;
}
}
@@ -949,7 +936,8 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
rb_node = simple_insert(&cache->rb_root, node->bytenr,
&node->rb_node);
if (rb_node)
- backref_tree_panic(rb_node, -EEXIST, node->bytenr);
+ backref_cache_panic(cache->fs_info, node->bytenr,
+ -EEXIST);
list_add_tail(&node->lower, &cache->leaves);
}
@@ -1087,7 +1075,7 @@ static int clone_backref_node(struct btrfs_trans_handle *trans,
rb_node = simple_insert(&cache->rb_root, new_node->bytenr,
&new_node->rb_node);
if (rb_node)
- backref_tree_panic(rb_node, -EEXIST, new_node->bytenr);
+ backref_cache_panic(trans->fs_info, new_node->bytenr, -EEXIST);
if (!new_node->lowest) {
list_for_each_entry(new_edge, &new_node->lower, list[UPPER]) {
@@ -1199,7 +1187,7 @@ static int __update_reloc_root(struct btrfs_root *root, u64 new_bytenr)
node->bytenr, &node->rb_node);
spin_unlock(&rc->reloc_root_tree.lock);
if (rb_node)
- backref_tree_panic(rb_node, -EEXIST, node->bytenr);
+ backref_cache_panic(fs_info, node->bytenr, -EEXIST);
return 0;
}
@@ -3285,7 +3273,8 @@ static int add_tree_block(struct reloc_control *rc,
rb_node = simple_insert(blocks, block->bytenr, &block->rb_node);
if (rb_node)
- backref_tree_panic(rb_node, -EEXIST, block->bytenr);
+ backref_cache_panic(rc->extent_root->fs_info, block->bytenr,
+ -EEXIST);
return 0;
}
@@ -3583,8 +3572,8 @@ static int find_data_references(struct reloc_control *rc,
rb_node = simple_insert(blocks, block->bytenr,
&block->rb_node);
if (rb_node)
- backref_tree_panic(rb_node, -EEXIST,
- block->bytenr);
+ backref_cache_panic(fs_info, block->bytenr,
+ -EEXIST);
}
if (counted)
added = 1;
--
2.25.1
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH 15/19] btrfs: Rename should_ignore_root() to should_ignore_reloc_root() and export it
2020-03-03 7:13 [PATCH 00/19] btrfs: Move generic backref cache build functions to backref.c Qu Wenruo
` (13 preceding siblings ...)
2020-03-03 7:14 ` [PATCH 14/19] btrfs: Rename backref_tree_panic() to backref_cache_panic(), and move it " Qu Wenruo
@ 2020-03-03 7:14 ` Qu Wenruo
2020-03-03 7:14 ` [PATCH 16/19] btrfs: relocation: Open-code read_fs_root() for handle_one_tree_backref() Qu Wenruo
` (5 subsequent siblings)
20 siblings, 0 replies; 25+ messages in thread
From: Qu Wenruo @ 2020-03-03 7:14 UTC (permalink / raw
To: linux-btrfs
This function is mostly single purpose to relocation backref cache, but
since we're moving the main part of backref cache to backref.c, we need
to export such function.
And to avoid confusing, rename the function to
should_ignore_reloc_root() make the name a little more clear.
Signed-off-by: Qu Wenruo <wqu@suse.com>
---
fs/btrfs/ctree.h | 1 +
fs/btrfs/relocation.c | 9 +++++----
2 files changed, 6 insertions(+), 4 deletions(-)
diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index b57bb3e5f1f2..e45aad90b45e 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -3383,6 +3383,7 @@ int btrfs_reloc_post_snapshot(struct btrfs_trans_handle *trans,
struct btrfs_pending_snapshot *pending);
struct btrfs_root *find_reloc_root(struct btrfs_fs_info *fs_info,
u64 bytenr);
+int should_ignore_reloc_root(struct btrfs_root *root);
/* scrub.c */
int btrfs_scrub_dev(struct btrfs_fs_info *fs_info, u64 devid, u64 start,
diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index 349e8e761e8d..2230ea8a3698 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -312,7 +312,7 @@ static bool reloc_root_is_dead(struct btrfs_root *root)
*
* Reloc tree after swap is considered dead, thus not considered as valid.
* This is enough for most callers, as they don't distinguish dead reloc root
- * from no reloc root. But should_ignore_root() below is a special case.
+ * from no reloc root. But should_ignore_reloc_root() below is a special case.
*/
static bool have_reloc_root(struct btrfs_root *root)
{
@@ -323,7 +323,7 @@ static bool have_reloc_root(struct btrfs_root *root)
return true;
}
-static int should_ignore_root(struct btrfs_root *root)
+int should_ignore_reloc_root(struct btrfs_root *root)
{
struct btrfs_root *reloc_root;
@@ -349,6 +349,7 @@ static int should_ignore_root(struct btrfs_root *root)
*/
return 1;
}
+
/*
* find reloc tree by address of tree root
*/
@@ -465,7 +466,7 @@ static int handle_one_tree_backref(struct backref_cache *cache,
/* tree root */
ASSERT(btrfs_root_bytenr(&root->root_item) ==
cur->bytenr);
- if (should_ignore_root(root)) {
+ if (should_ignore_reloc_root(root)) {
btrfs_put_root(root);
list_add(&cur->list, useless_node);
} else {
@@ -506,7 +507,7 @@ static int handle_one_tree_backref(struct backref_cache *cache,
if (!path->nodes[level]) {
ASSERT(btrfs_root_bytenr(&root->root_item) ==
lower->bytenr);
- if (should_ignore_root(root)) {
+ if (should_ignore_reloc_root(root)) {
btrfs_put_root(root);
list_add(&lower->list, useless_node);
} else {
--
2.25.1
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH 16/19] btrfs: relocation: Open-code read_fs_root() for handle_one_tree_backref()
2020-03-03 7:13 [PATCH 00/19] btrfs: Move generic backref cache build functions to backref.c Qu Wenruo
` (14 preceding siblings ...)
2020-03-03 7:14 ` [PATCH 15/19] btrfs: Rename should_ignore_root() to should_ignore_reloc_root() and export it Qu Wenruo
@ 2020-03-03 7:14 ` Qu Wenruo
2020-03-03 7:14 ` [PATCH 17/19] btrfs: Rename handle_one_tree_block() to backref_cache_add_one_tree_block() and move it to backref.c Qu Wenruo
` (4 subsequent siblings)
20 siblings, 0 replies; 25+ messages in thread
From: Qu Wenruo @ 2020-03-03 7:14 UTC (permalink / raw
To: linux-btrfs
The backref code is going to be moved to backref.c, and read_fs_root()
is just a simple wrapper, open-code it to prepare to the incoming code
move.
Signed-off-by: Qu Wenruo <wqu@suse.com>
---
fs/btrfs/relocation.c | 6 +++++-
1 file changed, 5 insertions(+), 1 deletion(-)
diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index 2230ea8a3698..441d2b28d8e7 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -397,6 +397,7 @@ static int handle_one_tree_backref(struct backref_cache *cache,
struct backref_node *lower;
struct backref_edge *edge;
struct extent_buffer *eb;
+ struct btrfs_key root_key;
struct btrfs_root *root;
struct rb_node *rb_node;
bool need_check = true;
@@ -456,7 +457,10 @@ static int handle_one_tree_backref(struct backref_cache *cache,
* ref_key.type == BTRFS_TREE_BLOCK_REF_KEY, ref_key->offset means the
* root objectid. We need to search the tree to get its parent bytenr.
*/
- root = read_fs_root(fs_info, ref_key->offset);
+ root_key.objectid = ref_key->offset;
+ root_key.type = BTRFS_ROOT_ITEM_KEY;
+ root_key.offset = (u64)-1;
+ root = btrfs_get_fs_root(fs_info, &root_key, false);
if (IS_ERR(root))
return PTR_ERR(root);
if (!test_bit(BTRFS_ROOT_REF_COWS, &root->state))
--
2.25.1
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH 17/19] btrfs: Rename handle_one_tree_block() to backref_cache_add_one_tree_block() and move it to backref.c
2020-03-03 7:13 [PATCH 00/19] btrfs: Move generic backref cache build functions to backref.c Qu Wenruo
` (15 preceding siblings ...)
2020-03-03 7:14 ` [PATCH 16/19] btrfs: relocation: Open-code read_fs_root() for handle_one_tree_backref() Qu Wenruo
@ 2020-03-03 7:14 ` Qu Wenruo
2020-03-03 7:14 ` [PATCH 18/19] btrfs: relocation: Move the target backref node insert code into finish_upper_links() Qu Wenruo
` (3 subsequent siblings)
20 siblings, 0 replies; 25+ messages in thread
From: Qu Wenruo @ 2020-03-03 7:14 UTC (permalink / raw
To: linux-btrfs
This function is the major part of backref cache build process, move it
to backref.c so we can reuse it later.
Signed-off-by: Qu Wenruo <wqu@suse.com>
---
fs/btrfs/backref.c | 305 +++++++++++++++++++++++++++++++++++++++++
fs/btrfs/backref.h | 6 +
fs/btrfs/relocation.c | 307 +-----------------------------------------
3 files changed, 313 insertions(+), 305 deletions(-)
diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index 02455b3bbc35..e1a271c1e9f3 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -13,6 +13,7 @@
#include "transaction.h"
#include "delayed-ref.h"
#include "locking.h"
+#include "misc.h"
/* Just an arbitrary number so we can be sure this happened */
#define BACKREF_FOUND_SHARED 6
@@ -2558,3 +2559,307 @@ void backref_cache_cleanup(struct backref_cache *cache)
ASSERT(!cache->nr_nodes);
ASSERT(!cache->nr_edges);
}
+
+static int handle_one_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 list_head *useless_node = &cache->useless_node;
+ struct list_head *pending_edge = &cache->pending_edge;
+ struct backref_node *upper;
+ struct backref_node *lower;
+ struct backref_edge *edge;
+ struct extent_buffer *eb;
+ struct btrfs_key root_key;
+ struct btrfs_root *root;
+ struct rb_node *rb_node;
+ bool need_check = true;
+ int level;
+ int ret = 0;
+
+ if (ref_key->type != BTRFS_TREE_BLOCK_REF_KEY &&
+ ref_key->type != BTRFS_SHARED_BLOCK_REF_KEY)
+ return -EUCLEAN;
+
+ /* SHARED_BLOCK_REF means key.offset is the parent bytenr */
+ if (ref_key->type == BTRFS_SHARED_BLOCK_REF_KEY) {
+
+ /* Only reloc root uses backref pointing to itself */
+ if (ref_key->objectid == ref_key->offset) {
+ cur->is_reloc_root = 1;
+ /* Only reloc backref cache cares exact root */
+ if (cache->is_reloc) {
+ root = find_reloc_root(fs_info, cur->bytenr);
+ if (WARN_ON(!root))
+ return -ENOENT;
+ cur->root = root;
+ }
+ return 0;
+ }
+
+ edge = alloc_backref_edge(cache);
+ if (!edge)
+ return -ENOMEM;
+
+ rb_node = simple_search(&cache->rb_root, ref_key->offset);
+ if (!rb_node) {
+ /* Parent node not yet cached */
+ upper = alloc_backref_node(cache, ref_key->offset,
+ cur->level + 1);
+ if (!upper) {
+ free_backref_edge(cache, edge);
+ return -ENOMEM;
+ }
+
+ /*
+ * backrefs for the upper level block isn't
+ * cached, add the block to pending list
+ */
+ list_add_tail(&edge->list[UPPER], pending_edge);
+ } else {
+ /* Parent node already cached */
+ upper = rb_entry(rb_node, struct backref_node,
+ rb_node);
+ ASSERT(upper->checked);
+ INIT_LIST_HEAD(&edge->list[UPPER]);
+ }
+ link_backref_edge(edge, cur, upper, LINK_LOWER);
+ return 0;
+ }
+ /*
+ * ref_key.type == BTRFS_TREE_BLOCK_REF_KEY, ref_key->offset means the
+ * root objectid. We need to search the tree to get its parent bytenr.
+ */
+ root_key.objectid = ref_key->offset;
+ root_key.type = BTRFS_ROOT_ITEM_KEY;
+ root_key.offset = (u64)-1;
+ root = btrfs_get_fs_root(fs_info, &root_key, false);
+ 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_reloc_root(root)) {
+ btrfs_put_root(root);
+ list_add(&cur->list, 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_reloc_root(root)) {
+ btrfs_put_root(root);
+ list_add(&lower->list, 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 = simple_search(&cache->rb_root, eb->start);
+ if (!rb_node) {
+ upper = alloc_backref_node(cache, eb->start,
+ lower->level + 1);
+ if (!upper) {
+ btrfs_put_root(root);
+ free_backref_edge(cache, edge);
+ ret = -ENOMEM;
+ goto out;
+ }
+ upper->owner = btrfs_header_owner(eb);
+ 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], 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);
+ }
+ link_backref_edge(edge, lower, upper, LINK_LOWER);
+
+ if (rb_node) {
+ btrfs_put_root(root);
+ break;
+ }
+ lower = upper;
+ upper = NULL;
+ }
+out:
+ btrfs_release_path(path);
+ return ret;
+}
+
+int backref_cache_add_one_tree_block(struct backref_cache *cache,
+ struct btrfs_path *path,
+ struct btrfs_backref_iter *iter,
+ struct btrfs_key *node_key,
+ struct backref_node *cur)
+{
+ struct backref_edge *edge;
+ struct backref_node *exist;
+ int ret;
+
+ ret = btrfs_backref_iter_start(iter, cur->bytenr);
+ if (ret < 0)
+ return ret;
+
+ /*
+ * We skip the first btrfs_tree_block_info, as we don't use the key
+ * stored in it, but fetch it from the tree block.
+ */
+ if (btrfs_backref_has_tree_block_info(iter)) {
+ ret = btrfs_backref_iter_next(iter);
+ if (ret < 0)
+ goto out;
+ /* No extra backref? This means the tree block is corrupted */
+ if (ret > 0) {
+ ret = -EUCLEAN;
+ goto out;
+ }
+ }
+ WARN_ON(cur->checked);
+ if (!list_empty(&cur->upper)) {
+ /*
+ * the backref was added previously when processing
+ * backref of type BTRFS_TREE_BLOCK_REF_KEY
+ */
+ ASSERT(list_is_singular(&cur->upper));
+ edge = list_entry(cur->upper.next, struct backref_edge,
+ list[LOWER]);
+ ASSERT(list_empty(&edge->list[UPPER]));
+ exist = edge->node[UPPER];
+ /*
+ * add the upper level block to pending list if we need
+ * check its backrefs
+ */
+ if (!exist->checked)
+ list_add_tail(&edge->list[UPPER], &cache->pending_edge);
+ } else {
+ exist = NULL;
+ }
+
+ for (; ret == 0; ret = btrfs_backref_iter_next(iter)) {
+ struct extent_buffer *eb;
+ struct btrfs_key key;
+ int type;
+
+ cond_resched();
+ eb = btrfs_backref_get_eb(iter);
+
+ key.objectid = iter->bytenr;
+ if (btrfs_backref_iter_is_inline_ref(iter)) {
+ struct btrfs_extent_inline_ref *iref;
+
+ /* update key for inline back ref */
+ iref = (struct btrfs_extent_inline_ref *)iter->cur_ptr;
+ type = btrfs_get_extent_inline_ref_type(eb, iref,
+ BTRFS_REF_TYPE_BLOCK);
+ if (type == BTRFS_REF_TYPE_INVALID) {
+ ret = -EUCLEAN;
+ goto out;
+ }
+ key.type = type;
+ key.offset = btrfs_extent_inline_ref_offset(eb, iref);
+ } else {
+ key.type = iter->cur_key.type;
+ key.offset = iter->cur_key.offset;
+ }
+
+ /*
+ * Parent node found and matches current inline ref, no need to
+ * rebuild this node for this inline ref.
+ */
+ if (exist &&
+ ((key.type == BTRFS_TREE_BLOCK_REF_KEY &&
+ exist->owner == key.offset) ||
+ (key.type == BTRFS_SHARED_BLOCK_REF_KEY &&
+ exist->bytenr == key.offset))) {
+ exist = NULL;
+ continue;
+ }
+
+ ret = handle_one_tree_backref(cache, path, &key, node_key, cur);
+ if (ret < 0)
+ goto out;
+ }
+ if (ret < 0)
+ goto out;
+ ret = 0;
+ cur->checked = 1;
+ WARN_ON(exist);
+out:
+ btrfs_backref_iter_release(iter);
+ return ret;
+}
diff --git a/fs/btrfs/backref.h b/fs/btrfs/backref.h
index 4a4c9070a38b..6b8b48bf6958 100644
--- a/fs/btrfs/backref.h
+++ b/fs/btrfs/backref.h
@@ -386,4 +386,10 @@ static inline void backref_cache_panic(struct btrfs_fs_info *fs_info,
"Inconsistency in backref cache found at offset %llu",
bytenr);
}
+
+int backref_cache_add_one_tree_block(struct backref_cache *cache,
+ struct btrfs_path *path,
+ struct btrfs_backref_iter *iter,
+ struct btrfs_key *node_key,
+ struct backref_node *cur);
#endif
diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index 441d2b28d8e7..4cb61165d852 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -384,310 +384,6 @@ static struct btrfs_root *read_fs_root(struct btrfs_fs_info *fs_info,
return btrfs_get_fs_root(fs_info, &key, false);
}
-static int handle_one_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 list_head *useless_node = &cache->useless_node;
- struct list_head *pending_edge = &cache->pending_edge;
- struct backref_node *upper;
- struct backref_node *lower;
- struct backref_edge *edge;
- struct extent_buffer *eb;
- struct btrfs_key root_key;
- struct btrfs_root *root;
- struct rb_node *rb_node;
- bool need_check = true;
- int level;
- int ret = 0;
-
- if (ref_key->type != BTRFS_TREE_BLOCK_REF_KEY &&
- ref_key->type != BTRFS_SHARED_BLOCK_REF_KEY)
- return -EUCLEAN;
-
- /* SHARED_BLOCK_REF means key.offset is the parent bytenr */
- if (ref_key->type == BTRFS_SHARED_BLOCK_REF_KEY) {
-
- /* Only reloc root uses backref pointing to itself */
- if (ref_key->objectid == ref_key->offset) {
- cur->is_reloc_root = 1;
- /* Only reloc backref cache cares exact root */
- if (cache->is_reloc) {
- root = find_reloc_root(fs_info, cur->bytenr);
- if (WARN_ON(!root))
- return -ENOENT;
- cur->root = root;
- }
- return 0;
- }
-
- edge = alloc_backref_edge(cache);
- if (!edge)
- return -ENOMEM;
-
- rb_node = simple_search(&cache->rb_root, ref_key->offset);
- if (!rb_node) {
- /* Parent node not yet cached */
- upper = alloc_backref_node(cache, ref_key->offset,
- cur->level + 1);
- if (!upper) {
- free_backref_edge(cache, edge);
- return -ENOMEM;
- }
-
- /*
- * backrefs for the upper level block isn't
- * cached, add the block to pending list
- */
- list_add_tail(&edge->list[UPPER], pending_edge);
- } else {
- /* Parent node already cached */
- upper = rb_entry(rb_node, struct backref_node,
- rb_node);
- ASSERT(upper->checked);
- INIT_LIST_HEAD(&edge->list[UPPER]);
- }
- link_backref_edge(edge, cur, upper, LINK_LOWER);
- return 0;
- }
- /*
- * ref_key.type == BTRFS_TREE_BLOCK_REF_KEY, ref_key->offset means the
- * root objectid. We need to search the tree to get its parent bytenr.
- */
- root_key.objectid = ref_key->offset;
- root_key.type = BTRFS_ROOT_ITEM_KEY;
- root_key.offset = (u64)-1;
- root = btrfs_get_fs_root(fs_info, &root_key, false);
- 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_reloc_root(root)) {
- btrfs_put_root(root);
- list_add(&cur->list, 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_reloc_root(root)) {
- btrfs_put_root(root);
- list_add(&lower->list, 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 = simple_search(&cache->rb_root, eb->start);
- if (!rb_node) {
- upper = alloc_backref_node(cache, eb->start,
- lower->level + 1);
- if (!upper) {
- btrfs_put_root(root);
- free_backref_edge(cache, edge);
- ret = -ENOMEM;
- goto out;
- }
- upper->owner = btrfs_header_owner(eb);
- 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], 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);
- }
- link_backref_edge(edge, lower, upper, LINK_LOWER);
-
- if (rb_node) {
- btrfs_put_root(root);
- break;
- }
- lower = upper;
- upper = NULL;
- }
-out:
- btrfs_release_path(path);
- return ret;
-}
-
-static int handle_one_tree_block(struct backref_cache *cache,
- struct btrfs_path *path,
- struct btrfs_backref_iter *iter,
- struct btrfs_key *node_key,
- struct backref_node *cur)
-{
- struct backref_edge *edge;
- struct backref_node *exist;
- int ret;
-
- ret = btrfs_backref_iter_start(iter, cur->bytenr);
- if (ret < 0)
- return ret;
-
- /*
- * We skip the first btrfs_tree_block_info, as we don't use the key
- * stored in it, but fetch it from the tree block.
- */
- if (btrfs_backref_has_tree_block_info(iter)) {
- ret = btrfs_backref_iter_next(iter);
- if (ret < 0)
- goto out;
- /* No extra backref? This means the tree block is corrupted */
- if (ret > 0) {
- ret = -EUCLEAN;
- goto out;
- }
- }
- WARN_ON(cur->checked);
- if (!list_empty(&cur->upper)) {
- /*
- * the backref was added previously when processing
- * backref of type BTRFS_TREE_BLOCK_REF_KEY
- */
- ASSERT(list_is_singular(&cur->upper));
- edge = list_entry(cur->upper.next, struct backref_edge,
- list[LOWER]);
- ASSERT(list_empty(&edge->list[UPPER]));
- exist = edge->node[UPPER];
- /*
- * add the upper level block to pending list if we need
- * check its backrefs
- */
- if (!exist->checked)
- list_add_tail(&edge->list[UPPER], &cache->pending_edge);
- } else {
- exist = NULL;
- }
-
- for (; ret == 0; ret = btrfs_backref_iter_next(iter)) {
- struct extent_buffer *eb;
- struct btrfs_key key;
- int type;
-
- cond_resched();
- eb = btrfs_backref_get_eb(iter);
-
- key.objectid = iter->bytenr;
- if (btrfs_backref_iter_is_inline_ref(iter)) {
- struct btrfs_extent_inline_ref *iref;
-
- /* update key for inline back ref */
- iref = (struct btrfs_extent_inline_ref *)iter->cur_ptr;
- type = btrfs_get_extent_inline_ref_type(eb, iref,
- BTRFS_REF_TYPE_BLOCK);
- if (type == BTRFS_REF_TYPE_INVALID) {
- ret = -EUCLEAN;
- goto out;
- }
- key.type = type;
- key.offset = btrfs_extent_inline_ref_offset(eb, iref);
- } else {
- key.type = iter->cur_key.type;
- key.offset = iter->cur_key.offset;
- }
-
- /*
- * Parent node found and matches current inline ref, no need to
- * rebuild this node for this inline ref.
- */
- if (exist &&
- ((key.type == BTRFS_TREE_BLOCK_REF_KEY &&
- exist->owner == key.offset) ||
- (key.type == BTRFS_SHARED_BLOCK_REF_KEY &&
- exist->bytenr == key.offset))) {
- exist = NULL;
- continue;
- }
-
- ret = handle_one_tree_backref(cache, path, &key, node_key, cur);
- if (ret < 0)
- goto out;
- }
- if (ret < 0)
- goto out;
- ret = 0;
- cur->checked = 1;
- WARN_ON(exist);
-out:
- btrfs_backref_iter_release(iter);
- return ret;
-}
-
/*
* In handle_one_tree_backref(), we have only linked the lower node to the edge,
* but the upper node hasn't been linked to the edge.
@@ -916,7 +612,8 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
/* Breadth-first search to build backref cache */
while (1) {
- ret = handle_one_tree_block(cache, path, iter, node_key, cur);
+ ret = backref_cache_add_one_tree_block(cache, path, iter,
+ node_key, cur);
if (ret < 0) {
err = ret;
goto out;
--
2.25.1
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH 18/19] btrfs: relocation: Move the target backref node insert code into finish_upper_links()
2020-03-03 7:13 [PATCH 00/19] btrfs: Move generic backref cache build functions to backref.c Qu Wenruo
` (16 preceding siblings ...)
2020-03-03 7:14 ` [PATCH 17/19] btrfs: Rename handle_one_tree_block() to backref_cache_add_one_tree_block() and move it to backref.c Qu Wenruo
@ 2020-03-03 7:14 ` Qu Wenruo
2020-03-03 7:14 ` [PATCH 19/19] btrfs: Rename finish_upper_links() to backref_cache_finish_upper_links() and move it to backref.c Qu Wenruo
` (2 subsequent siblings)
20 siblings, 0 replies; 25+ messages in thread
From: Qu Wenruo @ 2020-03-03 7:14 UTC (permalink / raw
To: linux-btrfs
The snippet of code can be easily merged into finish_upper_links(), thus
make related code more reuseable.
Signed-off-by: Qu Wenruo <wqu@suse.com>
---
fs/btrfs/relocation.c | 30 +++++++++++++++---------------
1 file changed, 15 insertions(+), 15 deletions(-)
diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index 4cb61165d852..ac3ac0c7ac9e 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -400,8 +400,23 @@ static int finish_upper_links(struct backref_cache *cache,
{
struct list_head *useless_node = &cache->useless_node;
struct backref_edge *edge;
+ struct rb_node *rb_node;
LIST_HEAD(pending_edge);
+ /*
+ * everything goes well, connect backref nodes and insert backref nodes
+ * into the cache.
+ */
+ ASSERT(start->checked);
+ 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.
*
@@ -584,7 +599,6 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
struct backref_node *lower;
struct backref_node *node = NULL;
struct backref_edge *edge;
- struct rb_node *rb_node;
int ret;
int err = 0;
@@ -629,20 +643,6 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
}
}
- /*
- * everything goes well, connect backref nodes and insert backref nodes
- * into the cache.
- */
- ASSERT(node->checked);
- if (!node->cowonly) {
- rb_node = simple_insert(&cache->rb_root, node->bytenr,
- &node->rb_node);
- if (rb_node)
- backref_cache_panic(cache->fs_info, node->bytenr,
- -EEXIST);
- list_add_tail(&node->lower, &cache->leaves);
- }
-
/* Finish the upper linkage of newly added edges/nodes */
ret = finish_upper_links(cache, node);
if (ret < 0) {
--
2.25.1
^ permalink raw reply related [flat|nested] 25+ messages in thread
* [PATCH 19/19] btrfs: Rename finish_upper_links() to backref_cache_finish_upper_links() and move it to backref.c
2020-03-03 7:13 [PATCH 00/19] btrfs: Move generic backref cache build functions to backref.c Qu Wenruo
` (17 preceding siblings ...)
2020-03-03 7:14 ` [PATCH 18/19] btrfs: relocation: Move the target backref node insert code into finish_upper_links() Qu Wenruo
@ 2020-03-03 7:14 ` Qu Wenruo
2020-03-03 16:30 ` [PATCH 00/19] btrfs: Move generic backref cache build functions " David Sterba
2020-03-03 21:22 ` Josef Bacik
20 siblings, 0 replies; 25+ messages in thread
From: Qu Wenruo @ 2020-03-03 7:14 UTC (permalink / raw
To: linux-btrfs
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 | 115 +++++++++++++++++++++++++++++++++++++++++
fs/btrfs/backref.h | 2 +
fs/btrfs/relocation.c | 117 +-----------------------------------------
3 files changed, 118 insertions(+), 116 deletions(-)
diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c
index e1a271c1e9f3..db0d9bc8d7b6 100644
--- a/fs/btrfs/backref.c
+++ b/fs/btrfs/backref.c
@@ -2863,3 +2863,118 @@ int backref_cache_add_one_tree_block(struct backref_cache *cache,
btrfs_backref_iter_release(iter);
return ret;
}
+
+/*
+ * In handle_one_tree_backref(), 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);
+
+ /*
+ * everything goes well, connect backref nodes and insert backref nodes
+ * into the cache.
+ */
+ ASSERT(start->checked);
+ 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_entry(pending_edge.next, 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 6b8b48bf6958..99d61922bf6c 100644
--- a/fs/btrfs/backref.h
+++ b/fs/btrfs/backref.h
@@ -392,4 +392,6 @@ int backref_cache_add_one_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 ac3ac0c7ac9e..67691c56ce99 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -384,121 +384,6 @@ static struct btrfs_root *read_fs_root(struct btrfs_fs_info *fs_info,
return btrfs_get_fs_root(fs_info, &key, false);
}
-/*
- * In handle_one_tree_backref(), 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);
-
- /*
- * everything goes well, connect backref nodes and insert backref nodes
- * into the cache.
- */
- ASSERT(start->checked);
- 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_entry(pending_edge.next, 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
@@ -644,7 +529,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
}
/* 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
^ permalink raw reply related [flat|nested] 25+ messages in thread
* Re: [PATCH 00/19] btrfs: Move generic backref cache build functions to backref.c
2020-03-03 7:13 [PATCH 00/19] btrfs: Move generic backref cache build functions to backref.c Qu Wenruo
` (18 preceding siblings ...)
2020-03-03 7:14 ` [PATCH 19/19] btrfs: Rename finish_upper_links() to backref_cache_finish_upper_links() and move it to backref.c Qu Wenruo
@ 2020-03-03 16:30 ` David Sterba
2020-03-05 5:28 ` Qu Wenruo
2020-03-03 21:22 ` Josef Bacik
20 siblings, 1 reply; 25+ messages in thread
From: David Sterba @ 2020-03-03 16:30 UTC (permalink / raw
To: Qu Wenruo; +Cc: linux-btrfs
On Tue, Mar 03, 2020 at 03:13:50PM +0800, Qu Wenruo wrote:
> The patchset is based on previous backref_cache_refactor branch, which
> is further based on misc-next.
>
> The whole series can be fetched from github:
> https://github.com/adam900710/linux/tree/backref_cache_code_move
>
> All the patches in previous branch is not touched at all, thus they are
> not re-sent in this patchset.
The patches are cleanups and code moving, please fix the coding style
issues you find.
* missing lines between declarations and statements
* exported functions need btrfs_ prefix
* comments should start with an upper case letter unless it's an
identifier, formatted to 80 columns
As this patchset depends on another one I'm not sure if it's right time
to update it now, before the other one is merged as I think the same
code is touched and this would cause extra work.
Overall it makes sensed to add more to backref.[hc] and export that as
an internal API.
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH 00/19] btrfs: Move generic backref cache build functions to backref.c
2020-03-03 7:13 [PATCH 00/19] btrfs: Move generic backref cache build functions to backref.c Qu Wenruo
` (19 preceding siblings ...)
2020-03-03 16:30 ` [PATCH 00/19] btrfs: Move generic backref cache build functions " David Sterba
@ 2020-03-03 21:22 ` Josef Bacik
2020-03-04 4:54 ` Qu Wenruo
20 siblings, 1 reply; 25+ messages in thread
From: Josef Bacik @ 2020-03-03 21:22 UTC (permalink / raw
To: Qu Wenruo, linux-btrfs
On 3/3/20 2:13 AM, Qu Wenruo wrote:
> The patchset is based on previous backref_cache_refactor branch, which
> is further based on misc-next.
>
> The whole series can be fetched from github:
> https://github.com/adam900710/linux/tree/backref_cache_code_move
>
> All the patches in previous branch is not touched at all, thus they are
> not re-sent in this patchset.
>
>
> Currently there are 3 major parts of build_backref_tree():
> - ITERATION
> This will do a breadth-first search, starts from the target bytenr,
> and queue all parents into the backref cache.
> The result is a temporary map, which is only single-directional, and
> involved new backref nodes are not yet inserted into the cache.
>
> - WEAVING
> Finish the map to make it bi-directional, and insert new nodes into
> the cache.
>
> - CLEANUP
> Cleanup the useless nodes, either remove it completely or add them
> into the cache as detached.
>
I've found a bunch of bugs in the backref code while fixing Zygo's problem, you
are probably going to want to wait for my patches to go in before you start
moving things around, because it's going to conflict a bunch. Thanks,
Josef
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH 00/19] btrfs: Move generic backref cache build functions to backref.c
2020-03-03 21:22 ` Josef Bacik
@ 2020-03-04 4:54 ` Qu Wenruo
2020-03-04 13:40 ` David Sterba
0 siblings, 1 reply; 25+ messages in thread
From: Qu Wenruo @ 2020-03-04 4:54 UTC (permalink / raw
To: Josef Bacik, Qu Wenruo, linux-btrfs
[-- Attachment #1.1: Type: text/plain, Size: 1436 bytes --]
On 2020/3/4 上午5:22, Josef Bacik wrote:
> On 3/3/20 2:13 AM, Qu Wenruo wrote:
>> The patchset is based on previous backref_cache_refactor branch, which
>> is further based on misc-next.
>>
>> The whole series can be fetched from github:
>> https://github.com/adam900710/linux/tree/backref_cache_code_move
>>
>> All the patches in previous branch is not touched at all, thus they are
>> not re-sent in this patchset.
>>
>>
>> Currently there are 3 major parts of build_backref_tree():
>> - ITERATION
>> This will do a breadth-first search, starts from the target bytenr,
>> and queue all parents into the backref cache.
>> The result is a temporary map, which is only single-directional, and
>> involved new backref nodes are not yet inserted into the cache.
>>
>> - WEAVING
>> Finish the map to make it bi-directional, and insert new nodes into
>> the cache.
>>
>> - CLEANUP
>> Cleanup the useless nodes, either remove it completely or add them
>> into the cache as detached.
>>
>
> I've found a bunch of bugs in the backref code while fixing Zygo's
> problem, you are probably going to want to wait for my patches to go in
> before you start moving things around, because it's going to conflict a
> bunch. Thanks,
No problem, it's expected to have some comments even for previous patchset.
So rebasing is expected.
Thanks,
Qu
>
> Josef
[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH 00/19] btrfs: Move generic backref cache build functions to backref.c
2020-03-04 4:54 ` Qu Wenruo
@ 2020-03-04 13:40 ` David Sterba
0 siblings, 0 replies; 25+ messages in thread
From: David Sterba @ 2020-03-04 13:40 UTC (permalink / raw
To: Qu Wenruo; +Cc: Josef Bacik, Qu Wenruo, linux-btrfs
On Wed, Mar 04, 2020 at 12:54:24PM +0800, Qu Wenruo wrote:
>
>
> On 2020/3/4 上午5:22, Josef Bacik wrote:
> > On 3/3/20 2:13 AM, Qu Wenruo wrote:
> >> The patchset is based on previous backref_cache_refactor branch, which
> >> is further based on misc-next.
> >>
> >> The whole series can be fetched from github:
> >> https://github.com/adam900710/linux/tree/backref_cache_code_move
> >>
> >> All the patches in previous branch is not touched at all, thus they are
> >> not re-sent in this patchset.
> >>
> >>
> >> Currently there are 3 major parts of build_backref_tree():
> >> - ITERATION
> >> This will do a breadth-first search, starts from the target bytenr,
> >> and queue all parents into the backref cache.
> >> The result is a temporary map, which is only single-directional, and
> >> involved new backref nodes are not yet inserted into the cache.
> >>
> >> - WEAVING
> >> Finish the map to make it bi-directional, and insert new nodes into
> >> the cache.
> >>
> >> - CLEANUP
> >> Cleanup the useless nodes, either remove it completely or add them
> >> into the cache as detached.
> >>
> >
> > I've found a bunch of bugs in the backref code while fixing Zygo's
> > problem, you are probably going to want to wait for my patches to go in
> > before you start moving things around, because it's going to conflict a
> > bunch. Thanks,
>
> No problem, it's expected to have some comments even for previous patchset.
>
> So rebasing is expected.
The fixes get merged first so they can be applied to older stable trees,
the cleanups that move code are best done as the last thing in the patch
queue. So this depends on timing and the amount of conflicts but we have
like 2 rcs to go.
^ permalink raw reply [flat|nested] 25+ messages in thread
* Re: [PATCH 00/19] btrfs: Move generic backref cache build functions to backref.c
2020-03-03 16:30 ` [PATCH 00/19] btrfs: Move generic backref cache build functions " David Sterba
@ 2020-03-05 5:28 ` Qu Wenruo
0 siblings, 0 replies; 25+ messages in thread
From: Qu Wenruo @ 2020-03-05 5:28 UTC (permalink / raw
To: dsterba, Qu Wenruo, linux-btrfs
[-- Attachment #1.1: Type: text/plain, Size: 1343 bytes --]
On 2020/3/4 上午12:30, David Sterba wrote:
> On Tue, Mar 03, 2020 at 03:13:50PM +0800, Qu Wenruo wrote:
>> The patchset is based on previous backref_cache_refactor branch, which
>> is further based on misc-next.
>>
>> The whole series can be fetched from github:
>> https://github.com/adam900710/linux/tree/backref_cache_code_move
>>
>> All the patches in previous branch is not touched at all, thus they are
>> not re-sent in this patchset.
>
> The patches are cleanups and code moving, please fix the coding style
> issues you find.
>
> * missing lines between declarations and statements
> * exported functions need btrfs_ prefix
I have some question about this.
Sometimes the "btrfs_" prefix requirement looks too mechanical.
Some functions, like backref_cache_init() is very obvious related to
backref cache.
I can't see any special benefit from adding a "btrfs_" prefix.
Thanks,
Qu
> * comments should start with an upper case letter unless it's an
> identifier, formatted to 80 columns
>
> As this patchset depends on another one I'm not sure if it's right time
> to update it now, before the other one is merged as I think the same
> code is touched and this would cause extra work.
>
> Overall it makes sensed to add more to backref.[hc] and export that as
> an internal API.
>
[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]
^ permalink raw reply [flat|nested] 25+ messages in thread
end of thread, other threads:[~2020-03-05 5:28 UTC | newest]
Thread overview: 25+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2020-03-03 7:13 [PATCH 00/19] btrfs: Move generic backref cache build functions to backref.c Qu Wenruo
2020-03-03 7:13 ` [PATCH 01/19] btrfs: Move backref node/edge/cache structure to backref.h Qu Wenruo
2020-03-03 7:13 ` [PATCH 02/19] btrfs: Rename tree_entry to simple_node and export it Qu Wenruo
2020-03-03 7:13 ` [PATCH 03/19] btrfs: relocation: Make reloc root search specific for relocation backref cache Qu Wenruo
2020-03-03 7:13 ` [PATCH 04/19] btrfs: relocation: Add backref_cache::pending_edge and backref_cache::useless_node members Qu Wenruo
2020-03-03 7:13 ` [PATCH 05/19] btrfs: relocation: Add backref_cache::fs_info member Qu Wenruo
2020-03-03 7:13 ` [PATCH 06/19] btrfs: Move backref_cache_init() to backref.c Qu Wenruo
2020-03-03 7:13 ` [PATCH 07/19] btrfs: Move alloc_backref_node() " Qu Wenruo
2020-03-03 7:13 ` [PATCH 08/19] btrfs: Move alloc_backref_edge() " Qu Wenruo
2020-03-03 7:13 ` [PATCH 09/19] btrfs: Move link_backref_edge() " Qu Wenruo
2020-03-03 7:14 ` [PATCH 10/19] btrfs: Move free_backref_node() and free_backref_edge() to backref.h Qu Wenruo
2020-03-03 7:14 ` [PATCH 11/19] btrfs: Move drop_backref_node() and needed facilities " Qu Wenruo
2020-03-03 7:14 ` [PATCH 12/19] btrfs: Rename remove_backref_node() to cleanup_backref_node() and move it to backref.c Qu Wenruo
2020-03-03 7:14 ` [PATCH 13/19] btrfs: Move backref_cache_cleanup() " Qu Wenruo
2020-03-03 7:14 ` [PATCH 14/19] btrfs: Rename backref_tree_panic() to backref_cache_panic(), and move it " Qu Wenruo
2020-03-03 7:14 ` [PATCH 15/19] btrfs: Rename should_ignore_root() to should_ignore_reloc_root() and export it Qu Wenruo
2020-03-03 7:14 ` [PATCH 16/19] btrfs: relocation: Open-code read_fs_root() for handle_one_tree_backref() Qu Wenruo
2020-03-03 7:14 ` [PATCH 17/19] btrfs: Rename handle_one_tree_block() to backref_cache_add_one_tree_block() and move it to backref.c Qu Wenruo
2020-03-03 7:14 ` [PATCH 18/19] btrfs: relocation: Move the target backref node insert code into finish_upper_links() Qu Wenruo
2020-03-03 7:14 ` [PATCH 19/19] btrfs: Rename finish_upper_links() to backref_cache_finish_upper_links() and move it to backref.c Qu Wenruo
2020-03-03 16:30 ` [PATCH 00/19] btrfs: Move generic backref cache build functions " David Sterba
2020-03-05 5:28 ` Qu Wenruo
2020-03-03 21:22 ` Josef Bacik
2020-03-04 4:54 ` Qu Wenruo
2020-03-04 13:40 ` David Sterba
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.