Skip to contentSkip to conversation

Turn delayed_nodes_tree into XArray and adjust usages

PATCH In review Gabriel Niebler 2 participants 11 messages Apr 7, 2022 – Apr 11, 2022 Btrfs file system

lore
Share & tools
lore
#0 lore raw

cover Turn delayed_nodes_tree into XArray and adjust usages

XArrays offer a somewhat nicer API than radix trees and were implemented specifically to replace the latter. They utilize the exact same underlying data structure, but their API is notionally easier to use, as it provides array semantics to the user of radix trees. The higher level API also takes care of locking, adding even more ease of use.

The btrfs code uses radix trees directly in several places, such as for the delayed_nodes_radix member of the btrfs_root struct.

This patchset converts delayed_nodes_radix into an XArray, renames it accordingly and adjusts all usages of this object to the XArray API. It survived a complete fstests run.

Gabriel Niebler (6):
Turn delayed_nodes_tree into delayed_nodes_xarray in btrfs_root
btrfs_get_delayed_node: convert to using XArray API btrfs_get_or_create_delayed_node: convert to using XArray API __btrfs_release_delayed_node: convert to using XArray API btrfs_kill_all_delayed_nodes: convert to using XArray API __setup_root: convert to using XArray API for delayed_nodes_xarray

 fs/btrfs/ctree.h         |  4 ++--
 fs/btrfs/delayed-inode.c | 48 ++++++++++++++++++----------------------
 fs/btrfs/disk-io.c       |  2 +-
 fs/btrfs/inode.c         |  2 +-
 4 files changed, 26 insertions(+), 30 deletions(-)
Signature · 1 line
2.35.1
#1 lore raw

PATCH 1/6 Turn delayed_nodes_tree into delayed_nodes_xarray in btrfs_root

… but don't use the XArray API yet.

This works, since the radix_tree_root struct has already been turned into an xarray behind the scenes, via a macro.

---
 fs/btrfs/ctree.h         | 4 ++--
 fs/btrfs/delayed-inode.c | 8 ++++----
 fs/btrfs/disk-io.c       | 2 +-
 fs/btrfs/inode.c         | 2 +-
 4 files changed, 8 insertions(+), 8 deletions(-)
fs/btrfs/ctree.h +2 -2
index b7631b88426e..ccd42a1638b1 100644
@@ -1224,10 +1224,10 @@ struct btrfs_root {
 	struct rb_root inode_tree;
 
 	/*
-	 * radix tree that keeps track of delayed nodes of every inode,
+	 * XArray that keeps track of delayed nodes of every inode,
 	 * protected by inode_lock
 	 */
-	struct radix_tree_root delayed_nodes_tree;
+	struct xarray delayed_nodes_xarray;
 	/*
 	 * right now this just gets used so that a root has its own devid
 	 * for stat.  It may be used for more later
fs/btrfs/delayed-inode.c +4 -4
index 748bf6b0d860..14d95ed62ac3 100644
@@ -78,7 +78,7 @@ static struct btrfs_delayed_node *btrfs_get_delayed_node(
 	}
 
 	spin_lock(&root->inode_lock);
-	node = radix_tree_lookup(&root->delayed_nodes_tree, ino);
+	node = radix_tree_lookup(&root->delayed_nodes_xarray, ino);
 
 	if (node) {
 		if (btrfs_inode->delayed_node) {
@@ -148,7 +148,7 @@ static struct btrfs_delayed_node *btrfs_get_or_create_delayed_node(
 	}
 
 	spin_lock(&root->inode_lock);
-	ret = radix_tree_insert(&root->delayed_nodes_tree, ino, node);
+	ret = radix_tree_insert(&root->delayed_nodes_xarray, ino, node);
 	if (ret == -EEXIST) {
 		spin_unlock(&root->inode_lock);
 		kmem_cache_free(delayed_node_cache, node);
@@ -276,7 +276,7 @@ static void __btrfs_release_delayed_node(
 		 * back up.  We can delete it now.
 		 */
 		ASSERT(refcount_read(&delayed_node->refs) == 0);
-		radix_tree_delete(&root->delayed_nodes_tree,
+		radix_tree_delete(&root->delayed_nodes_xarray,
 				  delayed_node->inode_id);
 		spin_unlock(&root->inode_lock);
 		kmem_cache_free(delayed_node_cache, delayed_node);
@@ -1876,7 +1876,7 @@ void btrfs_kill_all_delayed_nodes(struct btrfs_root *root)
 
 	while (1) {
 		spin_lock(&root->inode_lock);
-		n = radix_tree_gang_lookup(&root->delayed_nodes_tree,
+		n = radix_tree_gang_lookup(&root->delayed_nodes_xarray,
 					   (void **)delayed_nodes, inode_id,
 					   ARRAY_SIZE(delayed_nodes));
 		if (!n) {
fs/btrfs/disk-io.c +1 -1
index b30309f187cf..efe8b37c9504 100644
@@ -1164,7 +1164,7 @@ static void __setup_root(struct btrfs_root *root, struct btrfs_fs_info *fs_info,
 	root->nr_delalloc_inodes = 0;
 	root->nr_ordered_extents = 0;
 	root->inode_tree = RB_ROOT;
-	INIT_RADIX_TREE(&root->delayed_nodes_tree, GFP_ATOMIC);
+	INIT_RADIX_TREE(&root->delayed_nodes_xarray, GFP_ATOMIC);
 
 	btrfs_init_root_block_rsv(root);
 
fs/btrfs/inode.c +1 -1
index 17d5557f98ec..1db667088380 100644
@@ -3827,7 +3827,7 @@ static int btrfs_read_locked_inode(struct inode *inode,
 	 * cache.
 	 *
 	 * This is required for both inode re-read from disk and delayed inode
-	 * in delayed_nodes_tree.
+	 * in delayed_nodes_xarray.
 	 */
 	if (BTRFS_I(inode)->last_trans == fs_info->generation)
 		set_bit(BTRFS_INODE_NEEDS_FULL_SYNC,
Signature · 1 line
2.35.1
#2 lore raw

Re: [PATCH 1/6] Turn delayed_nodes_tree into delayed_nodes_xarray in btrfs_root

Quoted 3 lines · Gabriel Niebler

… but don't use the XArray API yet.

This works, since the radix_tree_root struct has already been turned into an xarray behind the scenes, via a macro.

Please align the text to 74 chars.

Quoted 13 lines
---
 fs/btrfs/ctree.h         | 4 ++--
 fs/btrfs/delayed-inode.c | 8 ++++----
 fs/btrfs/disk-io.c       | 2 +-
 fs/btrfs/inode.c         | 2 +-
 4 files changed, 8 insertions(+), 8 deletions(-)
fs/btrfs/ctree.h +0 -0
index b7631b88426e..ccd42a1638b1 100644

fs/btrfs/ctree.h struct btrfs_root { · line 1230

Quoted 9 lines
fs/btrfs/ctree.h +2 -2
@@ -1224,10 +1224,10 @@ struct btrfs_root {
 	struct rb_root inode_tree;
 
 	/*
-	 * radix tree that keeps track of delayed nodes of every inode,
+	 * XArray that keeps track of delayed nodes of every inode,
 	 * protected by inode_lock
 	 */
-	struct radix_tree_root delayed_nodes_tree;
+	struct xarray delayed_nodes_xarray;

I'd rather not rename the variable, it's an implementation detail and maybe dropping the _tree completely is a better idea.

#3 lore raw

PATCH 2/6 btrfs_get_delayed_node: convert to using XArray API

In reply to Gabriel Niebler
---
 fs/btrfs/delayed-inode.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)
fs/btrfs/delayed-inode.c +4 -4
index 14d95ed62ac3..240c11b59098 100644
@@ -78,7 +78,7 @@ static struct btrfs_delayed_node *btrfs_get_delayed_node(
 	}
 
 	spin_lock(&root->inode_lock);
-	node = radix_tree_lookup(&root->delayed_nodes_xarray, ino);
+	node = xa_load(&root->delayed_nodes_xarray, (unsigned long)ino);
 
 	if (node) {
 		if (btrfs_inode->delayed_node) {
@@ -90,9 +90,9 @@ static struct btrfs_delayed_node *btrfs_get_delayed_node(
 
 		/*
 		 * It's possible that we're racing into the middle of removing
-		 * this node from the radix tree.  In this case, the refcount
+		 * this node from the XArray.  In this case, the refcount
 		 * was zero and it should never go back to one.  Just return
-		 * NULL like it was never in the radix at all; our release
+		 * NULL like it was never in the XArray at all; our release
 		 * function is in the process of removing it.
 		 *
 		 * Some implementations of refcount_inc refuse to bump the
@@ -100,7 +100,7 @@ static struct btrfs_delayed_node *btrfs_get_delayed_node(
 		 * here, refcount_inc() may decide to just WARN_ONCE() instead
 		 * of actually bumping the refcount.
 		 *
-		 * If this node is properly in the radix, we want to bump the
+		 * If this node is properly in the XArray, we want to bump the
 		 * refcount twice, once for the inode and once for this get
 		 * operation.
 		 */
Signature · 1 line
2.35.1
#4 lore raw

PATCH 3/6 btrfs_get_or_create_delayed_node: convert to using XArray API

In reply to Gabriel Niebler
---
 fs/btrfs/delayed-inode.c | 16 +++++-----------
 1 file changed, 5 insertions(+), 11 deletions(-)
fs/btrfs/delayed-inode.c +5 -11
index 240c11b59098..9ee0c446478f 100644
@@ -141,23 +141,17 @@ static struct btrfs_delayed_node *btrfs_get_or_create_delayed_node(
 	/* cached in the btrfs inode and can be accessed */
 	refcount_set(&node->refs, 2);
 
-	ret = radix_tree_preload(GFP_NOFS);
-	if (ret) {
-		kmem_cache_free(delayed_node_cache, node);
-		return ERR_PTR(ret);
-	}
-
 	spin_lock(&root->inode_lock);
-	ret = radix_tree_insert(&root->delayed_nodes_xarray, ino, node);
-	if (ret == -EEXIST) {
+	ret = xa_insert(&root->delayed_nodes_xarray, ino, node, GFP_NOFS);
+	if (ret) {
 		spin_unlock(&root->inode_lock);
 		kmem_cache_free(delayed_node_cache, node);
-		radix_tree_preload_end();
-		goto again;
+		if (ret == -EBUSY)
+			goto again;
+		return ERR_PTR(ret);
 	}
 	btrfs_inode->delayed_node = node;
 	spin_unlock(&root->inode_lock);
-	radix_tree_preload_end();
 
 	return node;
 }
Signature · 1 line
2.35.1
#5 lore raw

PATCH 4/6 __btrfs_release_delayed_node: convert to using XArray API

In reply to Gabriel Niebler
---
 fs/btrfs/delayed-inode.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)
fs/btrfs/delayed-inode.c +1 -2
index 9ee0c446478f..a235f0941444 100644
@@ -270,8 +270,7 @@ static void __btrfs_release_delayed_node(
 		 * back up.  We can delete it now.
 		 */
 		ASSERT(refcount_read(&delayed_node->refs) == 0);
-		radix_tree_delete(&root->delayed_nodes_xarray,
-				  delayed_node->inode_id);
+		xa_erase(&root->delayed_nodes_xarray, delayed_node->inode_id);
 		spin_unlock(&root->inode_lock);
 		kmem_cache_free(delayed_node_cache, delayed_node);
 	}
Signature · 1 line
2.35.1
#6 lore raw

PATCH 5/6 btrfs_kill_all_delayed_nodes: convert to using XArray API

In reply to Gabriel Niebler
---
 fs/btrfs/delayed-inode.c | 21 ++++++++++++---------
 1 file changed, 12 insertions(+), 9 deletions(-)
fs/btrfs/delayed-inode.c +12 -9
index a235f0941444..877ba00fbe83 100644
@@ -1863,29 +1863,32 @@ void btrfs_kill_delayed_inode_items(struct btrfs_inode *inode)
 
 void btrfs_kill_all_delayed_nodes(struct btrfs_root *root)
 {
-	u64 inode_id = 0;
+	unsigned long index;
+	struct btrfs_delayed_node *delayed_node;
 	struct btrfs_delayed_node *delayed_nodes[8];
 	int i, n;
 
 	while (1) {
 		spin_lock(&root->inode_lock);
-		n = radix_tree_gang_lookup(&root->delayed_nodes_xarray,
-					   (void **)delayed_nodes, inode_id,
-					   ARRAY_SIZE(delayed_nodes));
-		if (!n) {
+		if (xa_empty(&root->delayed_nodes_xarray)) {
 			spin_unlock(&root->inode_lock);
 			break;
 		}
 
-		inode_id = delayed_nodes[n - 1]->inode_id + 1;
-		for (i = 0; i < n; i++) {
+		n = 0;
+		xa_for_each_start(&root->delayed_nodes_xarray, index,
+				  delayed_node, index) {
 			/*
 			 * Don't increase refs in case the node is dead and
 			 * about to be removed from the tree in the loop below
 			 */
-			if (!refcount_inc_not_zero(&delayed_nodes[i]->refs))
-				delayed_nodes[i] = NULL;
+			if (!refcount_inc_not_zero(&delayed_node->refs))
+				delayed_nodes[n] = NULL;
+			n++;
+			if (n >= ARRAY_SIZE(delayed_nodes))
+				break;
 		}
+		index++;
 		spin_unlock(&root->inode_lock);
 
 		for (i = 0; i < n; i++) {
Signature · 1 line
2.35.1
#7 lore raw

PATCH 6/6 __setup_root: convert to using XArray API for delayed_nodes_xarray

In reply to Gabriel Niebler
---
 fs/btrfs/disk-io.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
fs/btrfs/disk-io.c +1 -1
index efe8b37c9504..c2c7a1e2b3f9 100644
@@ -1164,7 +1164,7 @@ static void __setup_root(struct btrfs_root *root, struct btrfs_fs_info *fs_info,
 	root->nr_delalloc_inodes = 0;
 	root->nr_ordered_extents = 0;
 	root->inode_tree = RB_ROOT;
-	INIT_RADIX_TREE(&root->delayed_nodes_xarray, GFP_ATOMIC);
+	xa_init_flags(&root->delayed_nodes_xarray, GFP_ATOMIC);
 
 	btrfs_init_root_block_rsv(root);
 
Signature · 1 line
2.35.1
#8 lore raw
In reply to Gabriel Niebler
Quoted 6 lines · Gabriel Niebler

XArrays offer a somewhat nicer API than radix trees and were implemented specifically to replace the latter. They utilize the exact same underlying data structure, but their API is notionally easier to use, as it provides array semantics to the user of radix trees. The higher level API also takes care of locking, adding even more ease of use.

Quoted 6 lines

The btrfs code uses radix trees directly in several places, such as for the delayed_nodes_radix member of the btrfs_root struct.

This patchset converts delayed_nodes_radix into an XArray, renames it accordingly and adjusts all usages of this object to the XArray API. It survived a complete fstests run.

So it converts just one structure, it would be better do it in one patch otherwise it leaves the conversion half way and it's confusing to see xarray structure in the radix-tree API.

Quoted 7 lines

Gabriel Niebler (6):
Turn delayed_nodes_tree into delayed_nodes_xarray in btrfs_root
btrfs_get_delayed_node: convert to using XArray API btrfs_get_or_create_delayed_node: convert to using XArray API __btrfs_release_delayed_node: convert to using XArray API btrfs_kill_all_delayed_nodes: convert to using XArray API __setup_root: convert to using XArray API for delayed_nodes_xarray

The subject(s) should start with "btrfs: ..."

#9 lore raw

Am 07.04.22 um 18:44 schrieb David Sterba:

Quoted 9 lines · Gabriel Niebler
Quoted 4 lines

[...]
This patchset converts delayed_nodes_radix into an XArray, renames it accordingly and adjusts all usages of this object to the XArray API. It survived a complete fstests run.

So it converts just one structure, it would be better do it in one patch otherwise it leaves the conversion half way and it's confusing to see xarray structure in the radix-tree API.

Yes, I figured that converting each structure separately is easier to achieve for me, since the changes in this patch set are done, but changes to other structures are not (yet).

As for splitting the changes, as I did: My thought was that it's easier to review this way, patch-by-patch and that the important thing is that the conversion be done by the end of the patch set. But I do see the point that - even in a patch set - each patch should stand on its own and that does leave the code in an inconsistent (albeit working) state. Folding it all into one commit is not a problem and I will do that for resubmission.

Quoted 11 lines
Quoted 8 lines

Gabriel Niebler (6):
Turn delayed_nodes_tree into delayed_nodes_xarray in btrfs_root
btrfs_get_delayed_node: convert to using XArray API btrfs_get_or_create_delayed_node: convert to using XArray API __btrfs_release_delayed_node: convert to using XArray API btrfs_kill_all_delayed_nodes: convert to using XArray API __setup_root: convert to using XArray API for delayed_nodes_xarray

The subject(s) should start with "btrfs: ..."

OK, will fix.

I will also take the suggestions from the response to patch 1/6 on board.

Best,
gabe

#10 lore raw
Quoted 11 lines · Gabriel Niebler

Am 07.04.22 um 18:44 schrieb David Sterba:

Quoted 9 lines · Gabriel Niebler
Quoted 4 lines

[...]
This patchset converts delayed_nodes_radix into an XArray, renames it accordingly and adjusts all usages of this object to the XArray API. It survived a complete fstests run.

So it converts just one structure, it would be better do it in one patch otherwise it leaves the conversion half way and it's confusing to see xarray structure in the radix-tree API.

Quoted 7 lines

Yes, I figured that converting each structure separately is easier to achieve for me, since the changes in this patch set are done, but changes to other structures are not (yet).

As for splitting the changes, as I did: My thought was that it's easier to review this way, patch-by-patch and that the important thing is that the conversion be done by the end of the patch set.

The change splitting should be on the logical level and with focus on a selected context, but there's no universal advice. In this case the scope is one structure per patch, all actions with the structure are the context that often remains same for all the API calls, splitting that per patch does not help the review. Switching all structures in one patch would mean that each call site is using a different structure so the context is changing too often and that's adding to the congnitive load. Which leads to oversights and review quality goes down.