[PATCH 0/3] btrfs: relocation: build_backref_cache() refactor part 2

[PATCH 0/3] btrfs: relocation: build_backref_cache() refactor part 2

[Qu Wenruo]

This patchset can be fetched from:
https://github.com/adam900710/linux/tree/backref_cache_new

Since it is based on previous btrfs_backref_iter facility, it's
recommended to fetch from above repo.

This patchset mostly refactors the backref handling code out of the bit
loop in build_backref_cache().

Now build_backref_tree() can be easily divided into 4 small parts:
- Basic structure allocation
- Breadth-first search for backrefs
- Handling edges of upper nodes
- Removing useless nodes

Qu Wenruo (3):
  btrfs: relocation: Use wrapper to replace open-coded edge linking
  btrfs: relocation: Specify essential members for alloc_backref_node()
  btrfs: relocation: Remove the open-coded goto loop for breadth-first
    search

 fs/btrfs/relocation.c | 241 ++++++++++++++++++++++++------------------
 1 file changed, 138 insertions(+), 103 deletions(-)

-- 
2.25.1

[PATCH 1/3] btrfs: relocation: Use wrapper to replace open-coded edge linking

[Qu Wenruo]

Since backref_edge is used to connect upper and lower backref nodes, and
need to access both nodes, some code can look pretty nasty:

		list_add_tail(&edge->list[LOWER], &cur->upper);

The above code will link @cur to the LOWER side of the edge, while both
"LOWER" and "upper" words show up.
This can sometimes be very confusing for reader to grasp.

This patch introduce a new wrapper, link_backref_edge(), to handle the
linking behavior.
Which also has extra ASSERT() to ensure caller won't pass wrong nodes
in.

Also, this updates the comment of related lists of backref_node and
backref_edge, to make it more clear that each list points to what.

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 fs/btrfs/relocation.c | 53 ++++++++++++++++++++++++++++++-------------
 1 file changed, 37 insertions(+), 16 deletions(-)

diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index 812562e69315..660f4884fed4 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -44,10 +44,12 @@ struct backref_node {
 	u64 owner;
 	/* link to pending, changed or detached list */
 	struct list_head list;
-	/* list of upper level blocks reference this block */
+
+	/* List of upper level edges, which links this node to its parent(s) */
 	struct list_head upper;
-	/* list of child blocks in the cache */
+	/* 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 */
@@ -76,17 +78,26 @@ struct backref_node {
 	unsigned int detached:1;
 };
 
+#define LOWER	0
+#define UPPER	1
+#define RELOCATION_RESERVED_NODES	256
 /*
- * present a block pointer in the backref cache
+ * 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];
 };
 
-#define LOWER	0
-#define UPPER	1
-#define RELOCATION_RESERVED_NODES	256
 
 struct backref_cache {
 	/* red black tree of all backref nodes in the cache */
@@ -297,6 +308,22 @@ static struct backref_edge *alloc_backref_edge(struct backref_cache *cache)
 	return edge;
 }
 
+#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)
 {
@@ -693,9 +720,7 @@ static int handle_one_tree_backref(struct reloc_control *rc,
 			ASSERT(upper->checked);
 			INIT_LIST_HEAD(&edge->list[UPPER]);
 		}
-		list_add_tail(&edge->list[LOWER], &cur->upper);
-		edge->node[LOWER] = cur;
-		edge->node[UPPER] = upper;
+		link_backref_edge(edge, cur, upper, LINK_LOWER);
 		return 0;
 	}
 
@@ -806,9 +831,7 @@ static int handle_one_tree_backref(struct reloc_control *rc,
 			if (!upper->owner)
 				upper->owner = btrfs_header_owner(eb);
 		}
-		list_add_tail(&edge->list[LOWER], &lower->upper);
-		edge->node[LOWER] = lower;
-		edge->node[UPPER] = upper;
+		link_backref_edge(edge, lower, upper, LINK_LOWER);
 
 		if (rb_node)
 			break;
@@ -1199,10 +1222,8 @@ static int clone_backref_node(struct btrfs_trans_handle *trans,
 			if (!new_edge)
 				goto fail;
 
-			new_edge->node[UPPER] = new_node;
-			new_edge->node[LOWER] = edge->node[LOWER];
-			list_add_tail(&new_edge->list[UPPER],
-				      &new_node->lower);
+			link_backref_edge(new_edge, edge->node[LOWER], new_node,
+					  LINK_UPPER);
 		}
 	} else {
 		list_add_tail(&new_node->lower, &cache->leaves);
-- 
2.25.1

Re: [PATCH 1/3] btrfs: relocation: Use wrapper to replace open-coded edge linking

[Josef Bacik]

On 2/24/20 1:01 AM, Qu Wenruo wrote:
> Since backref_edge is used to connect upper and lower backref nodes, and
> need to access both nodes, some code can look pretty nasty:
> 
> 		list_add_tail(&edge->list[LOWER], &cur->upper);
> 
> The above code will link @cur to the LOWER side of the edge, while both
> "LOWER" and "upper" words show up.
> This can sometimes be very confusing for reader to grasp.
> 
> This patch introduce a new wrapper, link_backref_edge(), to handle the
> linking behavior.
> Which also has extra ASSERT() to ensure caller won't pass wrong nodes
> in.
> 
> Also, this updates the comment of related lists of backref_node and
> backref_edge, to make it more clear that each list points to what.
> 
> Signed-off-by: Qu Wenruo <wqu@suse.com>

Reviewed-by: Josef Bacik <josef@toxicpanda.com>

Thanks,

Josef

[PATCH 2/3] btrfs: relocation: Specify essential members for alloc_backref_node()

[Qu Wenruo]

Bytenr and level are essential parameters for backref_node, thus it
makes sense to initial them at alloc time.

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 fs/btrfs/relocation.c | 25 ++++++++++++-------------
 1 file changed, 12 insertions(+), 13 deletions(-)

diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index 660f4884fed4..f072d075a202 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -274,10 +274,12 @@ static void backref_cache_cleanup(struct backref_cache *cache)
 	ASSERT(!cache->nr_edges);
 }
 
-static struct backref_node *alloc_backref_node(struct backref_cache *cache)
+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);
@@ -285,6 +287,9 @@ static struct backref_node *alloc_backref_node(struct backref_cache *cache)
 		INIT_LIST_HEAD(&node->lower);
 		RB_CLEAR_NODE(&node->rb_node);
 		cache->nr_nodes++;
+
+		node->level = level;
+		node->bytenr = bytenr;
 	}
 	return node;
 }
@@ -701,13 +706,12 @@ static int handle_one_tree_backref(struct reloc_control *rc,
 		rb_node = tree_search(&cache->rb_root, ref_key->offset);
 		if (!rb_node) {
 			/* Parent node not yet cached */
-			upper = alloc_backref_node(cache);
+			upper = alloc_backref_node(cache, ref_key->offset,
+						   cur->level + 1);
 			if (!upper) {
 				free_backref_edge(cache, edge);
 				return -ENOMEM;
 			}
-			upper->bytenr = ref_key->offset;
-			upper->level = cur->level + 1;
 
 			/*
 			 *  backrefs for the upper level block isn't
@@ -788,15 +792,14 @@ static int handle_one_tree_backref(struct reloc_control *rc,
 		eb = path->nodes[level];
 		rb_node = tree_search(&cache->rb_root, eb->start);
 		if (!rb_node) {
-			upper = alloc_backref_node(cache);
+			upper = alloc_backref_node(cache, eb->start,
+						   lower->level + 1);
 			if (!upper) {
 				free_backref_edge(cache, edge);
 				ret = -ENOMEM;
 				goto out;
 			}
-			upper->bytenr = eb->start;
 			upper->owner = btrfs_header_owner(eb);
-			upper->level = lower->level + 1;
 			if (!test_bit(BTRFS_ROOT_REF_COWS,
 				      &root->state))
 				upper->cowonly = 1;
@@ -888,14 +891,12 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 	}
 	path->reada = READA_FORWARD;
 
-	node = alloc_backref_node(cache);
+	node = alloc_backref_node(cache, bytenr, level);
 	if (!node) {
 		err = -ENOMEM;
 		goto out;
 	}
 
-	node->bytenr = bytenr;
-	node->level = level;
 	node->lowest = 1;
 	cur = node;
 again:
@@ -1206,12 +1207,10 @@ static int clone_backref_node(struct btrfs_trans_handle *trans,
 	if (!node)
 		return 0;
 
-	new_node = alloc_backref_node(cache);
+	new_node = alloc_backref_node(cache, dest->node->start, node->level);
 	if (!new_node)
 		return -ENOMEM;
 
-	new_node->bytenr = dest->node->start;
-	new_node->level = node->level;
 	new_node->lowest = node->lowest;
 	new_node->checked = 1;
 	new_node->root = dest;
-- 
2.25.1

Re: [PATCH 2/3] btrfs: relocation: Specify essential members for alloc_backref_node()

[Josef Bacik]

On 2/24/20 1:01 AM, Qu Wenruo wrote:
> Bytenr and level are essential parameters for backref_node, thus it
> makes sense to initial them at alloc time.
> 
> Signed-off-by: Qu Wenruo <wqu@suse.com>

Reviewed-by: Josef Bacik <josef@toxicpanda.com>

Thanks,

Josef

[PATCH 3/3] btrfs: relocation: Remove the open-coded goto loop for breadth-first search

[Qu Wenruo]

build_backref_tree() uses "goto again;" to implement a breadth-first
search to build backref cache.

This patch will extract most of its work into a wrapper,
handle_one_tree_block(), and use a while() loop to implement the same
thing.

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 fs/btrfs/relocation.c | 165 +++++++++++++++++++++++-------------------
 1 file changed, 90 insertions(+), 75 deletions(-)

diff --git a/fs/btrfs/relocation.c b/fs/btrfs/relocation.c
index f072d075a202..13eadbb1c552 100644
--- a/fs/btrfs/relocation.c
+++ b/fs/btrfs/relocation.c
@@ -846,65 +846,21 @@ static int handle_one_tree_backref(struct reloc_control *rc,
 	return ret;
 }
 
-/*
- * build backref tree for a given tree block. root of the backref tree
- * corresponds the tree block, leaves of the backref tree correspond
- * roots of b-trees that reference the tree block.
- *
- * the basic idea of this function is check backrefs of a given block
- * to find upper level blocks that reference the block, and then check
- * backrefs of these upper level blocks recursively. the recursion stop
- * when tree root is reached or backrefs for the block is cached.
- *
- * NOTE: if we find backrefs for a block are cached, we know backrefs
- * for all upper level blocks that directly/indirectly reference the
- * block are also cached.
- */
-static noinline_for_stack
-struct backref_node *build_backref_tree(struct reloc_control *rc,
-					struct btrfs_key *node_key,
-					int level, u64 bytenr)
+static int handle_one_tree_block(struct reloc_control *rc,
+				 struct list_head *useless_node,
+				 struct list_head *pending_edge,
+				 struct btrfs_path *path,
+				 struct btrfs_backref_iter *iter,
+				 struct btrfs_key *node_key,
+				 struct backref_node *cur)
 {
-	struct btrfs_backref_iter *iter;
-	struct backref_cache *cache = &rc->backref_cache;
-	struct btrfs_path *path; /* For searching parent of TREE_BLOCK_REF */
-	struct backref_node *cur;
-	struct backref_node *upper;
-	struct backref_node *lower;
-	struct backref_node *node = NULL;
-	struct backref_node *exist = NULL;
 	struct backref_edge *edge;
-	struct rb_node *rb_node;
-	LIST_HEAD(list); /* Pending edge list, upper node needs to be checked */
-	LIST_HEAD(useless);
-	int cowonly;
+	struct backref_node *exist;
 	int ret;
-	int err = 0;
-
-	iter = btrfs_backref_iter_alloc(rc->extent_root->fs_info, GFP_NOFS);
-	if (!iter)
-		return ERR_PTR(-ENOMEM);
-	path = btrfs_alloc_path();
-	if (!path) {
-		err = -ENOMEM;
-		goto out;
-	}
-	path->reada = READA_FORWARD;
-
-	node = alloc_backref_node(cache, bytenr, level);
-	if (!node) {
-		err = -ENOMEM;
-		goto out;
-	}
 
-	node->lowest = 1;
-	cur = node;
-again:
 	ret = btrfs_backref_iter_start(iter, cur->bytenr);
-	if (ret < 0) {
-		err = ret;
-		goto out;
-	}
+	if (ret < 0)
+		return ret;
 
 	/*
 	 * We skip the first btrfs_tree_block_info, as we don't use the key
@@ -912,13 +868,11 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 	 */
 	if (btrfs_backref_has_tree_block_info(iter)) {
 		ret = btrfs_backref_iter_next(iter);
-		if (ret < 0) {
-			err = ret;
+		if (ret < 0)
 			goto out;
-		}
 		/* No extra backref? This means the tree block is corrupted */
 		if (ret > 0) {
-			err = -EUCLEAN;
+			ret = -EUCLEAN;
 			goto out;
 		}
 	}
@@ -938,7 +892,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 		 * check its backrefs
 		 */
 		if (!exist->checked)
-			list_add_tail(&edge->list[UPPER], &list);
+			list_add_tail(&edge->list[UPPER], pending_edge);
 	} else {
 		exist = NULL;
 	}
@@ -960,7 +914,7 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 			type = btrfs_get_extent_inline_ref_type(eb, iref,
 							BTRFS_REF_TYPE_BLOCK);
 			if (type == BTRFS_REF_TYPE_INVALID) {
-				err = -EUCLEAN;
+				ret = -EUCLEAN;
 				goto out;
 			}
 			key.type = type;
@@ -983,29 +937,90 @@ struct backref_node *build_backref_tree(struct reloc_control *rc,
 			continue;
 		}
 
-		ret = handle_one_tree_backref(rc, &useless, &list, path,
+		ret = handle_one_tree_backref(rc, useless_node, pending_edge, path,
 					      &key, node_key, cur);
-		if (ret < 0) {
-			err = ret;
+		if (ret < 0)
 			goto out;
-		}
 	}
-	if (ret < 0) {
-		err = ret;
+	if (ret < 0)
 		goto out;
-	}
 	ret = 0;
-	btrfs_backref_iter_release(iter);
-
 	cur->checked = 1;
 	WARN_ON(exist);
+out:
+	btrfs_backref_iter_release(iter);
+	return ret;
+}
 
-	/* the pending list isn't empty, take the first block to process */
-	if (!list_empty(&list)) {
-		edge = list_entry(list.next, struct backref_edge, list[UPPER]);
-		list_del_init(&edge->list[UPPER]);
-		cur = edge->node[UPPER];
-		goto again;
+/*
+ * build backref tree for a given tree block. root of the backref tree
+ * corresponds the tree block, leaves of the backref tree correspond
+ * roots of b-trees that reference the tree block.
+ *
+ * the basic idea of this function is check backrefs of a given block
+ * to find upper level blocks that reference the block, and then check
+ * backrefs of these upper level blocks recursively. the recursion stop
+ * when tree root is reached or backrefs for the block is cached.
+ *
+ * NOTE: if we find backrefs for a block are cached, we know backrefs
+ * for all upper level blocks that directly/indirectly reference the
+ * block are also cached.
+ */
+static noinline_for_stack
+struct backref_node *build_backref_tree(struct reloc_control *rc,
+					struct btrfs_key *node_key,
+					int level, u64 bytenr)
+{
+	struct btrfs_backref_iter *iter;
+	struct backref_cache *cache = &rc->backref_cache;
+	struct btrfs_path *path; /* For searching parent of TREE_BLOCK_REF */
+	struct backref_node *cur;
+	struct backref_node *upper;
+	struct backref_node *lower;
+	struct backref_node *node = NULL;
+	struct backref_edge *edge;
+	struct rb_node *rb_node;
+	LIST_HEAD(list); /* Pending edge list, upper node needs to be checked */
+	LIST_HEAD(useless);
+	int cowonly;
+	int ret;
+	int err = 0;
+
+	iter = btrfs_backref_iter_alloc(rc->extent_root->fs_info, GFP_NOFS);
+	if (!iter)
+		return ERR_PTR(-ENOMEM);
+	path = btrfs_alloc_path();
+	if (!path) {
+		err = -ENOMEM;
+		goto out;
+	}
+	path->reada = READA_FORWARD;
+
+	node = alloc_backref_node(cache, bytenr, level);
+	if (!node) {
+		err = -ENOMEM;
+		goto out;
+	}
+
+	node->lowest = 1;
+	cur = node;
+
+	/* Breadth-first search to build backref cache */
+	while (1) {
+		ret = handle_one_tree_block(rc, &useless, &list, path, iter,
+					    node_key, cur);
+		if (ret < 0) {
+			err = ret;
+			goto out;
+		}
+		/* the pending list isn't empty, take the first block to process */
+		if (!list_empty(&list)) {
+			edge = list_entry(list.next, struct backref_edge, list[UPPER]);
+			list_del_init(&edge->list[UPPER]);
+			cur = edge->node[UPPER];
+		} else {
+			break;
+		}
 	}
 
 	/*
-- 
2.25.1

Re: [PATCH 3/3] btrfs: relocation: Remove the open-coded goto loop for breadth-first search

[Josef Bacik]

On 2/24/20 1:02 AM, Qu Wenruo wrote:
> build_backref_tree() uses "goto again;" to implement a breadth-first
> search to build backref cache.
> 
> This patch will extract most of its work into a wrapper,
> handle_one_tree_block(), and use a while() loop to implement the same
> thing.
> 
> Signed-off-by: Qu Wenruo <wqu@suse.com>

Do you have this in a tree somewhere that I can look at it?  I tried applying 
these but they don't apply cleanly to anything I have, and it's hard to review 
this one without seeing how the code ends up after your diff.  Thanks,

Josef

Re: [PATCH 3/3] btrfs: relocation: Remove the open-coded goto loop for breadth-first search

[Qu Wenruo]

[-- Attachment #1.1: Type: text/plain, Size: 925 bytes --]



On 2020/2/28 上午3:51, Josef Bacik wrote:
> On 2/24/20 1:02 AM, Qu Wenruo wrote:
>> build_backref_tree() uses "goto again;" to implement a breadth-first
>> search to build backref cache.
>>
>> This patch will extract most of its work into a wrapper,
>> handle_one_tree_block(), and use a while() loop to implement the same
>> thing.
>>
>> Signed-off-by: Qu Wenruo <wqu@suse.com>
> 
> Do you have this in a tree somewhere that I can look at it?  I tried
> applying these but they don't apply cleanly to anything I have, and it's
> hard to review this one without seeing how the code ends up after your
> diff.  Thanks,

Sure, here you go:
https://github.com/adam900710/linux/tree/backref_cache_new

But please ignore the latest 1 or 2 commits, as they are still under
development.

Every submitted patches will not undergo any extra modification in that
branch.

Thanks,
Qu

> 
> Josef


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [PATCH 3/3] btrfs: relocation: Remove the open-coded goto loop for breadth-first search

[Qu Wenruo]

[-- Attachment #1.1: Type: text/plain, Size: 1228 bytes --]



On 2020/2/28 上午8:08, Qu Wenruo wrote:
> 
> 
> On 2020/2/28 上午3:51, Josef Bacik wrote:
>> On 2/24/20 1:02 AM, Qu Wenruo wrote:
>>> build_backref_tree() uses "goto again;" to implement a breadth-first
>>> search to build backref cache.
>>>
>>> This patch will extract most of its work into a wrapper,
>>> handle_one_tree_block(), and use a while() loop to implement the same
>>> thing.
>>>
>>> Signed-off-by: Qu Wenruo <wqu@suse.com>
>>
>> Do you have this in a tree somewhere that I can look at it?  I tried
>> applying these but they don't apply cleanly to anything I have, and it's
>> hard to review this one without seeing how the code ends up after your
>> diff.  Thanks,
> 
> Sure, here you go:
> https://github.com/adam900710/linux/tree/backref_cache_new
> 
> But please ignore the latest 1 or 2 commits, as they are still under
> development.
> 
> Every submitted patches will not undergo any extra modification in that
> branch.

Except this commit,  "btrfs: relocation: Rename mark_block_processed()
and __mark_block_processed()", Nikolay had some pretty good advice on
it, and it's updated to address his comment.

Thanks,
Qu
> 
> Thanks,
> Qu
> 
>>
>> Josef
> 


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]