Turn delayed_nodes_tree into XArray and adjust usages
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
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
@@ -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
@@ -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
@@ -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
@@ -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
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_rootstruct has already been turned into an xarray behind the scenes, via a macro.
Please align the text to 74 chars.
Quoted 13 lines
Signed-off-by Gabriel Niebler <[email protected]>--- 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
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.
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
@@ -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
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
@@ -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
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
@@ -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
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
@@ -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
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
@@ -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
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_radixmember of thebtrfs_rootstruct.This patchset converts
delayed_nodes_radixinto 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):
Turndelayed_nodes_treeintodelayed_nodes_xarrayinbtrfs_root
btrfs_get_delayed_node: convert to using XArray APIbtrfs_get_or_create_delayed_node: convert to using XArray API__btrfs_release_delayed_node: convert to using XArray APIbtrfs_kill_all_delayed_nodes: convert to using XArray API__setup_root: convert to using XArray API fordelayed_nodes_xarray
The subject(s) should start with "btrfs: ..."
Am 07.04.22 um 18:44 schrieb David Sterba:
Quoted 9 lines · Gabriel Niebler
Quoted 4 lines
[...]
This patchset convertsdelayed_nodes_radixinto 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):
Turndelayed_nodes_treeintodelayed_nodes_xarrayinbtrfs_root
btrfs_get_delayed_node: convert to using XArray APIbtrfs_get_or_create_delayed_node: convert to using XArray API__btrfs_release_delayed_node: convert to using XArray APIbtrfs_kill_all_delayed_nodes: convert to using XArray API__setup_root: convert to using XArray API fordelayed_nodes_xarrayThe 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
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 convertsdelayed_nodes_radixinto 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.