Convert btrfs_root::delayed_nodes_tree to xarray
David Sterba
maintainerv2 cover Convert btrfs_root::delayed_nodes_tree to xarray
v2:
- rework it so we can still use GFP_NOFS for allocation, emulating the preload mechanism with the xarray API, no changes to locking needed
- tested with error injections instead of xa_reserve()
v1:
This restarts the radix-tree to xarray conversion that we had to revert. There are two more structures to convert, possibly with also spinlock to mutex conversions needed (buffer_radix and fs_roots_radix), but for the buffer radix I don't want to do now as we have the folio conversion ongoing. The fs_roots will most likely need the lock conversion so that's a change that I want to take the whole dev cycle, planned for 6.9.
David Sterba (1):
btrfs: switch btrfs_root::delayed_nodes_tree to xarray from radix-tree
fs/btrfs/ctree.h | 6 ++-- fs/btrfs/delayed-inode.c | 64 ++++++++++++++++++++++------------------ fs/btrfs/disk-io.c | 3 +- fs/btrfs/inode.c | 2 +- 4 files changed, 41 insertions(+), 34 deletions(-)
Signature · 1 line
2.42.1
David Sterba
maintainerPATCH v2 1/1 btrfs: switch btrfs_root::delayed_nodes_tree to xarray from radix-tree
The radix-tree has been superseded by the xarray
(https://lwn.net/Articles/745073), this patch converts the btrfs_root::delayed_nodes, the APIs are used in a simple way.
First idea is to do xa_insert() but this would require GFP_ATOMIC allocation which we want to avoid if possible. The preload mechanism of radix-tree can be emulated within the xarray API.
- xa_reserve() with GFP_NOFS outside of the lock, the reserved entry is inserted atomically at most once
- xa_store() under a lock, in case something races in we can detect that and xa_load() returns a valid pointer
All uses of xa_load() must check for a valid pointer in case they manage to get between the xa_reserve() and xa_store(), this is handled in btrfs_get_delayed_node().
Otherwise the functionality is equivalent, xarray implements the radix-tree and there should be no performance difference.
The patch continues the efforts started in 253bf57555e451 ("btrfs: turn delayed_nodes_tree into an XArray") and fixes the problems with locking and GFP flags 088aea3b97e0ae ("Revert "btrfs: turn delayed_nodes_tree into an XArray"").
--- fs/btrfs/ctree.h | 6 ++-- fs/btrfs/delayed-inode.c | 64 ++++++++++++++++++++++------------------ fs/btrfs/disk-io.c | 3 +- fs/btrfs/inode.c | 2 +- 4 files changed, 41 insertions(+), 34 deletions(-)
fs/btrfs/ctree.h +3 -3
@@ -227,10 +227,10 @@ struct btrfs_root {struct rb_root inode_tree;/* -* radix tree that keeps track of delayed nodes of every inode, -* protected by inode_lock +* 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;/* * 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 +35 -29
132 lines not on this page · raw message
fs/btrfs/disk-io.c +2 -1
@@ -655,7 +655,8 @@ 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 ); +/* GFP flags are compatible with XA_FLAGS_*. */ +xa_init_flags (&root->delayed_nodes,GFP_ATOMIC );btrfs_init_root_block_rsv (root);
fs/btrfs/inode.c +1 -1
@@ -3805,7 +3805,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 the delayed_nodes xarray. */ if (BTRFS_I (inode)->last_trans ==btrfs_get_fs_generation (fs_info)) set_bit(BTRFS_INODE_NEEDS_FULL_SYNC,
Signature · 1 line
2.42.1
Re: [PATCH 1/1 v2] btrfs: switch btrfs_root::delayed_nodes_tree to xarray from radix-tree
Quoted 173 lines · David Sterba
The radix-tree has been superseded by the xarray
(https://lwn.net/Articles/745073), this patch converts thebtrfs_root::delayed_nodes, the APIs are used in a simple way.First idea is to do
xa_insert()but this would requireGFP_ATOMICallocation which we want to avoid if possible. The preload mechanism of radix-tree can be emulated within the xarray API.-
xa_reserve()withGFP_NOFSoutside of the lock, the reserved entry is inserted atomically at most once-
xa_store()under a lock, in case something races in we can detect that andxa_load()returns a valid pointerAll uses of
xa_load()must check for a valid pointer in case they manage to get between thexa_reserve()andxa_store(), this is handled inbtrfs_get_delayed_node().Otherwise the functionality is equivalent, xarray implements the radix-tree and there should be no performance difference.
The patch continues the efforts started in
253bf57555e451("btrfs: turndelayed_nodes_treeinto an XArray") and fixes the problems with locking and GFP flags088aea3b97e0ae("Revert "btrfs: turndelayed_nodes_treeinto an XArray"").Signed-off-by David Sterba <[email protected]>--- fs/btrfs/ctree.h | 6 ++-- fs/btrfs/delayed-inode.c | 64 ++++++++++++++++++++++------------------ fs/btrfs/disk-io.c | 3 +- fs/btrfs/inode.c | 2 +- 4 files changed, 41 insertions(+), 34 deletions(-)fs/btrfs/ctree.h +3
-3@@ -227,10 +227,10 @@ struct btrfs_root {struct rb_root inode_tree;/* -* radix tree that keeps track of delayed nodes of every inode, -* protected by inode_lock +* 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;/* * 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 +27
-24@@ -71,7 +71,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 =xa_load (&root->delayed_nodes, ino);if (node) {if (btrfs_inode->delayed_node) {@@ -83,9 +83,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 @@ -93,7 +93,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. */ @@ -120,6 +120,7 @@ static struct btrfs_delayed_node *btrfs_get_or_create_delayed_node(struct btrfs_root *root = btrfs_inode->root;u64 ino =btrfs_ino (btrfs_inode);int ret; +void *ptr; again: node =btrfs_get_delayed_node (btrfs_inode);@@ -131,26 +132,30 @@ static struct btrfs_delayed_node *btrfs_get_or_create_delayed_node(return ERR_PTR (-ENOMEM );btrfs_init_delayed_node (node, root, ino); -/* cached in the btrfs inode and can be accessed */ +/* Cached in the inode and can be accessed. */ refcount_set (&node->refs,2 ); - ret =radix_tree_preload (GFP_NOFS ); -if (ret) { +/* Allocate and reserve the slot, from now it can return a NULL on xa_load(). */ + ret =xa_reserve (&root->delayed_nodes, ino,GFP_NOFS ); +if (ret == -ENOMEM ) {kmem_cache_free (delayed_node_cache, node); -return ERR_PTR (ret); +return ERR_PTR (-ENOMEM ); } -spin_lock (&root->inode_lock); - ret =radix_tree_insert (&root->delayed_nodes_tree, ino, node); -if (ret == -EEXIST ) { + ptr =xa_load (&root->delayed_nodes, ino); +if (ptr) { +/* Somebody inserted it, go back and read it. */ spin_unlock (&root->inode_lock);kmem_cache_free (delayed_node_cache, node); -radix_tree_preload_end (); + node =NULL ; goto again; } + ptr =xa_store (&root->delayed_nodes, ino, node,GFP_ATOMIC ); +ASSERT (xa_err (ptr) != -EINVAL ); +ASSERT (xa_err (ptr) != -ENOMEM ); +ASSERT (ptr ==NULL ); btrfs_inode->delayed_node = node;spin_unlock (&root->inode_lock); -radix_tree_preload_end ();return node; }@@ -269,8 +274,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, - delayed_node->inode_id); +xa_erase (&root->delayed_nodes, delayed_node->inode_id);spin_unlock (&root->inode_lock);kmem_cache_free (delayed_node_cache, delayed_node); }@@ -2038,34 +2042,36 @@ 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 =0 ;struct btrfs_delayed_node *delayed_nodes[8 ]; -int i, n;while (1 ) { +struct btrfs_delayed_node *node; +int count; +spin_lock (&root->inode_lock); - n =radix_tree_gang_lookup (&root->delayed_nodes_tree, - (void **)delayed_nodes, inode_id, -ARRAY_SIZE (delayed_nodes)); -if (!n) { +if (xa_empty (&root->delayed_nodes)) {spin_unlock (&root->inode_lock); -break ; +return ; } - inode_id = delayed_nodes[n -1 ]->inode_id +1 ; -for (i =0 ; i < n; i++) { + count =0 ; +xa_for_each_start (&root->delayed_nodes, index, node, index) {
fs/btrfs/delayed-inode.c void btrfs_kill_delayed_inode_items(struct btrfs_inode *inode) · line 2067
Quoted 10 lines
fs/btrfs/delayed-inode.c +4
-2/* * 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 (&node->refs)) { + delayed_nodes[count] = node; + count++; + }
So before each xa_for_each_start() call, the delayed_nodes array should be zeroed (make all entries point to NULL).
As it is we're leaving stale pointers in it in case we find any with a zero refcount.
This was not a problem before, because the radix_tree_gang_lookup() took the array as an argument and did that.
Otherwise the changes look good.
Thanks.
Quoted 44 lines
fs/btrfs/delayed-inode.c +4
-3+if (count >=ARRAY_SIZE (delayed_nodes)) +break ; }spin_unlock (&root->inode_lock); + index++; -for (i =0 ; i < n; i++) { -if (!delayed_nodes[i]) -continue ; +for (int i =0 ; i < count; i++) {__btrfs_kill_delayed_node (delayed_nodes[i]);btrfs_release_delayed_node (delayed_nodes[i]); }fs/btrfs/disk-io.c +2
-1@@ -655,7 +655,8 @@ 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 ); +/* GFP flags are compatible with XA_FLAGS_*. */ +xa_init_flags (&root->delayed_nodes,GFP_ATOMIC );btrfs_init_root_block_rsv (root);fs/btrfs/inode.c +1
-2@@ -3805,7 +3805,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 the delayed_nodes xarray. */ if (BTRFS_I (inode)->last_trans ==btrfs_get_fs_generation (fs_info)) set_bit(BTRFS_INODE_NEEDS_FULL_SYNC, --2.42.1
Filipe Manana
Reviewed-byRe: [PATCH 1/1 v2] btrfs: switch btrfs_root::delayed_nodes_tree to xarray from radix-tree
Quoted 184 lines · Filipe Manana
Quoted 182 lines · David Sterba
The radix-tree has been superseded by the xarray
(https://lwn.net/Articles/745073), this patch converts thebtrfs_root::delayed_nodes, the APIs are used in a simple way.First idea is to do
xa_insert()but this would requireGFP_ATOMICallocation which we want to avoid if possible. The preload mechanism of radix-tree can be emulated within the xarray API.-
xa_reserve()withGFP_NOFSoutside of the lock, the reserved entry is inserted atomically at most once-
xa_store()under a lock, in case something races in we can detect that andxa_load()returns a valid pointerAll uses of
xa_load()must check for a valid pointer in case they manage to get between thexa_reserve()andxa_store(), this is handled inbtrfs_get_delayed_node().Otherwise the functionality is equivalent, xarray implements the radix-tree and there should be no performance difference.
The patch continues the efforts started in
253bf57555e451("btrfs: turndelayed_nodes_treeinto an XArray") and fixes the problems with locking and GFP flags088aea3b97e0ae("Revert "btrfs: turndelayed_nodes_treeinto an XArray"").Signed-off-by David Sterba <[email protected]>--- fs/btrfs/ctree.h | 6 ++-- fs/btrfs/delayed-inode.c | 64 ++++++++++++++++++++++------------------ fs/btrfs/disk-io.c | 3 +- fs/btrfs/inode.c | 2 +- 4 files changed, 41 insertions(+), 34 deletions(-)fs/btrfs/ctree.h +3
-3@@ -227,10 +227,10 @@ struct btrfs_root {struct rb_root inode_tree;/* -* radix tree that keeps track of delayed nodes of every inode, -* protected by inode_lock +* 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;/* * 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 +30
-26@@ -71,7 +71,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 =xa_load (&root->delayed_nodes, ino);if (node) {if (btrfs_inode->delayed_node) {@@ -83,9 +83,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 @@ -93,7 +93,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. */ @@ -120,6 +120,7 @@ static struct btrfs_delayed_node *btrfs_get_or_create_delayed_node(struct btrfs_root *root = btrfs_inode->root;u64 ino =btrfs_ino (btrfs_inode);int ret; +void *ptr; again: node =btrfs_get_delayed_node (btrfs_inode);@@ -131,26 +132,30 @@ static struct btrfs_delayed_node *btrfs_get_or_create_delayed_node(return ERR_PTR (-ENOMEM );btrfs_init_delayed_node (node, root, ino); -/* cached in the btrfs inode and can be accessed */ +/* Cached in the inode and can be accessed. */ refcount_set (&node->refs,2 ); - ret =radix_tree_preload (GFP_NOFS ); -if (ret) { +/* Allocate and reserve the slot, from now it can return a NULL on xa_load(). */ + ret =xa_reserve (&root->delayed_nodes, ino,GFP_NOFS ); +if (ret == -ENOMEM ) {kmem_cache_free (delayed_node_cache, node); -return ERR_PTR (ret); +return ERR_PTR (-ENOMEM ); } -spin_lock (&root->inode_lock); - ret =radix_tree_insert (&root->delayed_nodes_tree, ino, node); -if (ret == -EEXIST ) { + ptr =xa_load (&root->delayed_nodes, ino); +if (ptr) { +/* Somebody inserted it, go back and read it. */ spin_unlock (&root->inode_lock);kmem_cache_free (delayed_node_cache, node); -radix_tree_preload_end (); + node =NULL ; goto again; } + ptr =xa_store (&root->delayed_nodes, ino, node,GFP_ATOMIC ); +ASSERT (xa_err (ptr) != -EINVAL ); +ASSERT (xa_err (ptr) != -ENOMEM ); +ASSERT (ptr ==NULL ); btrfs_inode->delayed_node = node;spin_unlock (&root->inode_lock); -radix_tree_preload_end ();return node; }@@ -269,8 +274,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, - delayed_node->inode_id); +xa_erase (&root->delayed_nodes, delayed_node->inode_id);spin_unlock (&root->inode_lock);kmem_cache_free (delayed_node_cache, delayed_node); }@@ -2038,34 +2042,36 @@ 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 =0 ;struct btrfs_delayed_node *delayed_nodes[8 ]; -int i, n;while (1 ) { +struct btrfs_delayed_node *node; +int count; +spin_lock (&root->inode_lock); - n =radix_tree_gang_lookup (&root->delayed_nodes_tree, - (void **)delayed_nodes, inode_id, -ARRAY_SIZE (delayed_nodes)); -if (!n) { +if (xa_empty (&root->delayed_nodes)) {spin_unlock (&root->inode_lock); -break ; +return ; } - inode_id = delayed_nodes[n -1 ]->inode_id +1 ; -for (i =0 ; i < n; i++) { + count =0 ; +xa_for_each_start (&root->delayed_nodes, index, 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 (&node->refs)) { + delayed_nodes[count] = node; + count++;
Quoted 8 lines
fs/btrfs/delayed-inode.c void btrfs_kill_delayed_inode_items(struct btrfs_inode *inode) · line 2067
Quoted 1 line
fs/btrfs/delayed-inode.c +1
-0+ }So before each
xa_for_each_start()call, thedelayed_nodesarray should be zeroed (make all entries point to NULL).
As it is we're leaving stale pointers in it in case we find any with a zero refcount.
This was not a problem before, because theradix_tree_gang_lookup()took the array as an argument and did that.
Nevermind, got confused at the diff due to different array indexes before and after the patch.
Looks good, thanks.
Quoted 50 lines
Otherwise the changes look good.
Thanks.
Quoted 44 lines
fs/btrfs/delayed-inode.c +4
-3+if (count >=ARRAY_SIZE (delayed_nodes)) +break ; }spin_unlock (&root->inode_lock); + index++; -for (i =0 ; i < n; i++) { -if (!delayed_nodes[i]) -continue ; +for (int i =0 ; i < count; i++) {__btrfs_kill_delayed_node (delayed_nodes[i]);btrfs_release_delayed_node (delayed_nodes[i]); }fs/btrfs/disk-io.c +2
-1@@ -655,7 +655,8 @@ 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 ); +/* GFP flags are compatible with XA_FLAGS_*. */ +xa_init_flags (&root->delayed_nodes,GFP_ATOMIC );btrfs_init_root_block_rsv (root);fs/btrfs/inode.c +1
-2@@ -3805,7 +3805,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 the delayed_nodes xarray. */ if (BTRFS_I (inode)->last_trans ==btrfs_get_fs_generation (fs_info)) set_bit(BTRFS_INODE_NEEDS_FULL_SYNC, --2.42.1