Skip to contentSkip to conversation

btrfs: relocation: Use btrfs_find_all_leaves() to locate parent tree leaves of a data extent

PATCH In review Qu Wenruo 3 participants 5 messages Mar 10, 2020 – Mar 13, 2020 Btrfs file system

lore
Share & tools
lore

Qu Wenruo

author
#0 lore raw

PATCH 1/1 btrfs: relocation: Use btrfs_find_all_leaves() to locate parent tree leaves of a data extent

In relocation, we need to locate all parent tree leaves referring one data extent, thus we have a complex mechanism to iterate throught extent tree and subvolume trees to locate related leaves.

However this is already done in backref.c, we have btrfs_find_all_leaves(), which can return a ulist containing all leaves referring to that data extent.

Use btrfs_find_all_leaves() to replace find_data_references().

There is a special handling for v1 space cache data extents, where we need to delete the v1 space cache data extents, to avoid those data extents to hang the data relocation.

In this patch, the special handling is done by re-iterating the root tree leaf.
Although it's a little less efficient than the old handling, considering we can reuse a lot of code, it should be acceptable.

---
This patch is originally in my backref cache branch, but since it's pretty independent from other backref cache code, and straightforward to test/review, it's sent for more comprehensive test/review/merge.

---
 fs/btrfs/backref.c    |   8 +-
 fs/btrfs/backref.h    |   4 +
 fs/btrfs/relocation.c | 314 ++++++++----------------------------------
 3 files changed, 62 insertions(+), 264 deletions(-)
fs/btrfs/backref.c +4 -4
index 327e4480957b..f2728fb3ee8f 100644
@@ -1409,10 +1409,10 @@ static void free_leaf_list(struct ulist *blocks)
  *
  * returns 0 on success, <0 on error
  */
-static int btrfs_find_all_leafs(struct btrfs_trans_handle *trans,
-				struct btrfs_fs_info *fs_info, u64 bytenr,
-				u64 time_seq, struct ulist **leafs,
-				const u64 *extent_item_pos, bool ignore_offset)
+int btrfs_find_all_leafs(struct btrfs_trans_handle *trans,
+			 struct btrfs_fs_info *fs_info, u64 bytenr,
+			 u64 time_seq, struct ulist **leafs,
+			 const u64 *extent_item_pos, bool ignore_offset)
 {
 	int ret;
 
fs/btrfs/backref.h +4 -0
index 777f61dc081e..723d6da99114 100644
@@ -40,6 +40,10 @@ int iterate_inodes_from_logical(u64 logical, struct btrfs_fs_info *fs_info,
 
 int paths_from_inode(u64 inum, struct inode_fs_paths *ipath);
 
+int btrfs_find_all_leafs(struct btrfs_trans_handle *trans,
+			 struct btrfs_fs_info *fs_info, u64 bytenr,
+			 u64 time_seq, struct ulist **leafs,
+			 const u64 *extent_item_pos, bool ignore_offset);
 int btrfs_find_all_roots(struct btrfs_trans_handle *trans,
 			 struct btrfs_fs_info *fs_info, u64 bytenr,
 			 u64 time_seq, struct ulist **roots, bool ignore_offset);
fs/btrfs/relocation.c +54 -260

356 lines not on this page · raw message

Signature · 1 line
2.25.1
#1 lore raw
Quoted 19 lines · Qu Wenruo

In relocation, we need to locate all parent tree leaves referring one data extent, thus we have a complex mechanism to iterate throught extent tree and subvolume trees to locate related leaves.

However this is already done in backref.c, we have btrfs_find_all_leaves(), which can return a ulist containing all leaves referring to that data extent.

Use btrfs_find_all_leaves() to replace find_data_references().

There is a special handling for v1 space cache data extents, where we need to delete the v1 space cache data extents, to avoid those data extents to hang the data relocation.

In this patch, the special handling is done by re-iterating the root tree leaf.
Although it's a little less efficient than the old handling, considering we can reuse a lot of code, it should be acceptable.

Quoted 5 lines

---
This patch is originally in my backref cache branch, but since it's pretty independent from other backref cache code, and straightforward to test/review, it's sent for more comprehensive test/review/merge.

I'll add the patch to for-next, looks a bit scary.

#2 lore raw
Quoted 20 lines · David Sterba
Quoted 19 lines · Qu Wenruo

In relocation, we need to locate all parent tree leaves referring one data extent, thus we have a complex mechanism to iterate throught extent tree and subvolume trees to locate related leaves.

However this is already done in backref.c, we have btrfs_find_all_leaves(), which can return a ulist containing all leaves referring to that data extent.

Use btrfs_find_all_leaves() to replace find_data_references().

There is a special handling for v1 space cache data extents, where we need to delete the v1 space cache data extents, to avoid those data extents to hang the data relocation.

In this patch, the special handling is done by re-iterating the root tree leaf.
Although it's a little less efficient than the old handling, considering we can reuse a lot of code, it should be acceptable.

Quoted 8 lines
Quoted 5 lines

---
This patch is originally in my backref cache branch, but since it's pretty independent from other backref cache code, and straightforward to test/review, it's sent for more comprehensive test/review/merge.

I'll add the patch to for-next, looks a bit scary.

Thanks.

It survives the regular balance/replace/volume groups run.

And any behavior change in the v1 space cache handling would lead to 100% reproducible hang in btrfs/061, so it shouldn't be that scary.

Thanks,
Qu

#3 lore raw
In reply to Qu Wenruo
Quoted 9 lines · Qu Wenruo

In relocation, we need to locate all parent tree leaves referring one data extent, thus we have a complex mechanism to iterate throught extent tree and subvolume trees to locate related leaves.

However this is already done in backref.c, we have btrfs_find_all_leaves(), which can return a ulist containing all leaves referring to that data extent.

Use btrfs_find_all_leaves() to replace find_data_references().

      ^^^^^^^^^^J^^^^^^^^^^

The function is called btrfs_find_all_leafs, which is wrong spelling of leaves, I was tempted to rename it in the same patch but unfortunately ther's one more untouched caller so it's for another one.

Quoted 105 lines

There is a special handling for v1 space cache data extents, where we need to delete the v1 space cache data extents, to avoid those data extents to hang the data relocation.

In this patch, the special handling is done by re-iterating the root tree leaf.
Although it's a little less efficient than the old handling, considering we can reuse a lot of code, it should be acceptable.

---
This patch is originally in my backref cache branch, but since it's pretty independent from other backref cache code, and straightforward to test/review, it's sent for more comprehensive test/review/merge.

---
 fs/btrfs/backref.c    |   8 +-
 fs/btrfs/backref.h    |   4 +
 fs/btrfs/relocation.c | 314 ++++++++----------------------------------
 3 files changed, 62 insertions(+), 264 deletions(-)
fs/btrfs/backref.c +4 -4
index 327e4480957b..f2728fb3ee8f 100644
@@ -1409,10 +1409,10 @@ static void free_leaf_list(struct ulist *blocks)
  *
  * returns 0 on success, <0 on error
  */
-static int btrfs_find_all_leafs(struct btrfs_trans_handle *trans,
-				struct btrfs_fs_info *fs_info, u64 bytenr,
-				u64 time_seq, struct ulist **leafs,
-				const u64 *extent_item_pos, bool ignore_offset)
+int btrfs_find_all_leafs(struct btrfs_trans_handle *trans,
+			 struct btrfs_fs_info *fs_info, u64 bytenr,
+			 u64 time_seq, struct ulist **leafs,
+			 const u64 *extent_item_pos, bool ignore_offset)
 {
 	int ret;
 
fs/btrfs/backref.h +4 -0
index 777f61dc081e..723d6da99114 100644
@@ -40,6 +40,10 @@ int iterate_inodes_from_logical(u64 logical, struct btrfs_fs_info *fs_info,
 
 int paths_from_inode(u64 inum, struct inode_fs_paths *ipath);
 
+int btrfs_find_all_leafs(struct btrfs_trans_handle *trans,
+			 struct btrfs_fs_info *fs_info, u64 bytenr,
+			 u64 time_seq, struct ulist **leafs,
+			 const u64 *extent_item_pos, bool ignore_offset);
 int btrfs_find_all_roots(struct btrfs_trans_handle *trans,
 			 struct btrfs_fs_info *fs_info, u64 bytenr,
 			 u64 time_seq, struct ulist **roots, bool ignore_offset);
fs/btrfs/relocation.c +2 -27
index 02afe294ee2d..319d50c7ada5 100644
@@ -23,6 +23,7 @@
 #include "print-tree.h"
 #include "delalloc-space.h"
 #include "block-group.h"
+#include "backref.h"
 
 /*
  * Relocation overview
@@ -3620,31 +3621,6 @@ static int __add_tree_block(struct reloc_control *rc,
 	return ret;
 }
 
-/*
- * helper to check if the block use full backrefs for pointers in it
- */
-static int block_use_full_backref(struct reloc_control *rc,
-				  struct extent_buffer *eb)
-{
-	u64 flags;
-	int ret;
-
-	if (btrfs_header_flag(eb, BTRFS_HEADER_FLAG_RELOC) ||
-	    btrfs_header_backref_rev(eb) < BTRFS_MIXED_BACKREF_REV)
-		return 1;
-
-	ret = btrfs_lookup_extent_info(NULL, rc->extent_root->fs_info,
-				       eb->start, btrfs_header_level(eb), 1,
-				       NULL, &flags);
-	BUG_ON(ret);
-
-	if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)
-		ret = 1;
-	else
-		ret = 0;
-	return ret;
-}
-
 static int delete_block_group_cache(struct btrfs_fs_info *fs_info,
 				    struct btrfs_block_group *block_group,
 				    struct inode *inode,
@@ -3688,174 +3664,42 @@ static int delete_block_group_cache(struct btrfs_fs_info *fs_info,
 }
 
 /*
- * helper to add tree blocks for backref of type BTRFS_EXTENT_DATA_REF_KEY
- * this function scans fs tree to find blocks reference the data extent
+ * Helper function to locate the free space cache EXTENT_DATA in root tree leaf

fs/btrfs/relocation.c static int delete_block_group_cache(struct btrfs_fs_info *fs_info, · line 3672

Quoted 10 lines
fs/btrfs/relocation.c +4 -5
+ * and delete the cache inode, to avoid free space cache data extent blocking
+ * data relocation.
  */
-static int find_data_references(struct reloc_control *rc,
-				struct btrfs_key *extent_key,
-				struct extent_buffer *leaf,
-				struct btrfs_extent_data_ref *ref,
-				struct rb_root *blocks)
+static int delete_v1_space_cache(struct btrfs_fs_info *fs_info,
+				 struct extent_buffer *leaf,

The fs_info seems to be redundant, so I've replaced it with leaf->fs_info here

Quoted 4 lines
fs/btrfs/relocation.c +3 -0
+	ret = delete_block_group_cache(fs_info, block_group, NULL,
+					space_cache_ino);
+	return ret;
 }
#4 lore raw
Quoted 9 lines · David Sterba
Quoted 8 lines · Qu Wenruo

In relocation, we need to locate all parent tree leaves referring one data extent, thus we have a complex mechanism to iterate throught extent tree and subvolume trees to locate related leaves.

However this is already done in backref.c, we have btrfs_find_all_leaves(), which can return a ulist containing all leaves referring to that data extent.

Quoted 6 lines
Quoted 1 line

Use btrfs_find_all_leaves() to replace find_data_references().

      ^^^^^^^^^^J^^^^^^^^^^

The function is called btrfs_find_all_leafs, which is wrong spelling of leaves, I was tempted to rename it in the same patch but unfortunately ther's one more untouched caller so it's for another one.

Mind me to send the spelling fix?

Quoted 111 lines
Quoted 111 lines

There is a special handling for v1 space cache data extents, where we need to delete the v1 space cache data extents, to avoid those data extents to hang the data relocation.

In this patch, the special handling is done by re-iterating the root tree leaf.
Although it's a little less efficient than the old handling, considering we can reuse a lot of code, it should be acceptable.

---
This patch is originally in my backref cache branch, but since it's pretty independent from other backref cache code, and straightforward to test/review, it's sent for more comprehensive test/review/merge.

---
 fs/btrfs/backref.c    |   8 +-
 fs/btrfs/backref.h    |   4 +
 fs/btrfs/relocation.c | 314 ++++++++----------------------------------
 3 files changed, 62 insertions(+), 264 deletions(-)
fs/btrfs/backref.c +4 -4
index 327e4480957b..f2728fb3ee8f 100644
@@ -1409,10 +1409,10 @@ static void free_leaf_list(struct ulist *blocks)
  *
  * returns 0 on success, <0 on error
  */
-static int btrfs_find_all_leafs(struct btrfs_trans_handle *trans,
-				struct btrfs_fs_info *fs_info, u64 bytenr,
-				u64 time_seq, struct ulist **leafs,
-				const u64 *extent_item_pos, bool ignore_offset)
+int btrfs_find_all_leafs(struct btrfs_trans_handle *trans,
+			 struct btrfs_fs_info *fs_info, u64 bytenr,
+			 u64 time_seq, struct ulist **leafs,
+			 const u64 *extent_item_pos, bool ignore_offset)
 {
 	int ret;
 
fs/btrfs/backref.h +4 -0
index 777f61dc081e..723d6da99114 100644
@@ -40,6 +40,10 @@ int iterate_inodes_from_logical(u64 logical, struct btrfs_fs_info *fs_info,
 
 int paths_from_inode(u64 inum, struct inode_fs_paths *ipath);
 
+int btrfs_find_all_leafs(struct btrfs_trans_handle *trans,
+			 struct btrfs_fs_info *fs_info, u64 bytenr,
+			 u64 time_seq, struct ulist **leafs,
+			 const u64 *extent_item_pos, bool ignore_offset);
 int btrfs_find_all_roots(struct btrfs_trans_handle *trans,
 			 struct btrfs_fs_info *fs_info, u64 bytenr,
 			 u64 time_seq, struct ulist **roots, bool ignore_offset);
fs/btrfs/relocation.c +4 -29
index 02afe294ee2d..319d50c7ada5 100644
@@ -23,6 +23,7 @@
 #include "print-tree.h"
 #include "delalloc-space.h"
 #include "block-group.h"
+#include "backref.h"
 
 /*
  * Relocation overview
@@ -3620,31 +3621,6 @@ static int __add_tree_block(struct reloc_control *rc,
 	return ret;
 }
 
-/*
- * helper to check if the block use full backrefs for pointers in it
- */
-static int block_use_full_backref(struct reloc_control *rc,
-				  struct extent_buffer *eb)
-{
-	u64 flags;
-	int ret;
-
-	if (btrfs_header_flag(eb, BTRFS_HEADER_FLAG_RELOC) ||
-	    btrfs_header_backref_rev(eb) < BTRFS_MIXED_BACKREF_REV)
-		return 1;
-
-	ret = btrfs_lookup_extent_info(NULL, rc->extent_root->fs_info,
-				       eb->start, btrfs_header_level(eb), 1,
-				       NULL, &flags);
-	BUG_ON(ret);
-
-	if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)
-		ret = 1;
-	else
-		ret = 0;
-	return ret;
-}
-
 static int delete_block_group_cache(struct btrfs_fs_info *fs_info,
 				    struct btrfs_block_group *block_group,
 				    struct inode *inode,
@@ -3688,174 +3664,42 @@ static int delete_block_group_cache(struct btrfs_fs_info *fs_info,
 }
 
 /*
- * helper to add tree blocks for backref of type BTRFS_EXTENT_DATA_REF_KEY
- * this function scans fs tree to find blocks reference the data extent
+ * Helper function to locate the free space cache EXTENT_DATA in root tree leaf
+ * and delete the cache inode, to avoid free space cache data extent blocking
+ * data relocation.
  */
-static int find_data_references(struct reloc_control *rc,
-				struct btrfs_key *extent_key,
Quoted 8 lines

fs/btrfs/relocation.c static int delete_block_group_cache(struct btrfs_fs_info *fs_info, · line 3672

Quoted 5 lines
fs/btrfs/relocation.c +2 -3
-				struct extent_buffer *leaf,
-				struct btrfs_extent_data_ref *ref,
-				struct rb_root *blocks)
+static int delete_v1_space_cache(struct btrfs_fs_info *fs_info,
+				 struct extent_buffer *leaf,

The fs_info seems to be redundant, so I've replaced it with leaf->fs_info here

Oh, right. Always forgot that eb::fs_info member.

Thanks,
Qu

Quoted 5 lines
Quoted 5 lines
fs/btrfs/relocation.c +3 -0
+	ret = delete_block_group_cache(fs_info, block_group, NULL,
+					space_cache_ino);
+	return ret;
 }