[PATCH 0/6] Turn delayed_nodes_tree into XArray and adjust usages

[PATCH 0/6] Turn delayed_nodes_tree into XArray and adjust usages

[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.

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(-)

-- 
2.35.1

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

[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.

Signed-off-by: Gabriel Niebler <gniebler@suse.com>
---
 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(-)

diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index b7631b88426e..ccd42a1638b1 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -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
diff --git a/fs/btrfs/delayed-inode.c b/fs/btrfs/delayed-inode.c
index 748bf6b0d860..14d95ed62ac3 100644
--- a/fs/btrfs/delayed-inode.c
+++ b/fs/btrfs/delayed-inode.c
@@ -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) {
diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
index b30309f187cf..efe8b37c9504 100644
--- a/fs/btrfs/disk-io.c
+++ b/fs/btrfs/disk-io.c
@@ -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);
 
diff --git a/fs/btrfs/inode.c b/fs/btrfs/inode.c
index 17d5557f98ec..1db667088380 100644
--- a/fs/btrfs/inode.c
+++ b/fs/btrfs/inode.c
@@ -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,
-- 
2.35.1

[PATCH 2/6] btrfs_get_delayed_node: convert to using XArray API

[Gabriel Niebler]

Signed-off-by: Gabriel Niebler <gniebler@suse.com>
---
 fs/btrfs/delayed-inode.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/fs/btrfs/delayed-inode.c b/fs/btrfs/delayed-inode.c
index 14d95ed62ac3..240c11b59098 100644
--- a/fs/btrfs/delayed-inode.c
+++ b/fs/btrfs/delayed-inode.c
@@ -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.
 		 */
-- 
2.35.1

[PATCH 3/6] btrfs_get_or_create_delayed_node: convert to using XArray API

[Gabriel Niebler]

Signed-off-by: Gabriel Niebler <gniebler@suse.com>
---
 fs/btrfs/delayed-inode.c | 16 +++++-----------
 1 file changed, 5 insertions(+), 11 deletions(-)

diff --git a/fs/btrfs/delayed-inode.c b/fs/btrfs/delayed-inode.c
index 240c11b59098..9ee0c446478f 100644
--- a/fs/btrfs/delayed-inode.c
+++ b/fs/btrfs/delayed-inode.c
@@ -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;
 }
-- 
2.35.1

[PATCH 4/6] __btrfs_release_delayed_node: convert to using XArray API

[Gabriel Niebler]

Signed-off-by: Gabriel Niebler <gniebler@suse.com>
---
 fs/btrfs/delayed-inode.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/fs/btrfs/delayed-inode.c b/fs/btrfs/delayed-inode.c
index 9ee0c446478f..a235f0941444 100644
--- a/fs/btrfs/delayed-inode.c
+++ b/fs/btrfs/delayed-inode.c
@@ -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);
 	}
-- 
2.35.1

[PATCH 5/6] btrfs_kill_all_delayed_nodes: convert to using XArray API

[Gabriel Niebler]

Signed-off-by: Gabriel Niebler <gniebler@suse.com>
---
 fs/btrfs/delayed-inode.c | 21 ++++++++++++---------
 1 file changed, 12 insertions(+), 9 deletions(-)

diff --git a/fs/btrfs/delayed-inode.c b/fs/btrfs/delayed-inode.c
index a235f0941444..877ba00fbe83 100644
--- a/fs/btrfs/delayed-inode.c
+++ b/fs/btrfs/delayed-inode.c
@@ -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++) {
-- 
2.35.1

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

[Gabriel Niebler]

Signed-off-by: Gabriel Niebler <gniebler@suse.com>
---
 fs/btrfs/disk-io.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
index efe8b37c9504..c2c7a1e2b3f9 100644
--- a/fs/btrfs/disk-io.c
+++ b/fs/btrfs/disk-io.c
@@ -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);
 
-- 
2.35.1

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

[David Sterba]

On Thu, Apr 07, 2022 at 05:38:49PM +0200, Gabriel Niebler wrote:
> … 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.

> Signed-off-by: Gabriel Niebler <gniebler@suse.com>
> ---
>  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(-)
> 
> diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
> index b7631b88426e..ccd42a1638b1 100644
> --- a/fs/btrfs/ctree.h
> +++ b/fs/btrfs/ctree.h
> @@ -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.

Re: [PATCH 0/6] Turn delayed_nodes_tree into XArray and adjust usages

[David Sterba]

On Thu, Apr 07, 2022 at 05:38:48PM +0200, Gabriel Niebler wrote:
> 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.

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.

> 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: ..."

Re: [PATCH 0/6] Turn delayed_nodes_tree into XArray and adjust usages

[Gabriel Niebler]

Am 07.04.22 um 18:44 schrieb David Sterba:
> On Thu, Apr 07, 2022 at 05:38:48PM +0200, Gabriel Niebler wrote:
>> [...]
>> 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.

> 
>> 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

Re: [PATCH 0/6] Turn delayed_nodes_tree into XArray and adjust usages

[David Sterba]

On Mon, Apr 11, 2022 at 09:41:54AM +0200, Gabriel Niebler wrote:
> Am 07.04.22 um 18:44 schrieb David Sterba:
> > On Thu, Apr 07, 2022 at 05:38:48PM +0200, Gabriel Niebler wrote:
> >> [...]
> >> 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.

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.