btrfs: Turn delayed_nodes_tree into an XArray
PATCH v2 1/1 btrfs: Turn delayed_nodes_tree into an XArray
… in the btrfs_root struct. Also adjust all usages of this object to use the XArray API.
---
Notes:
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 in several places. This patch only converts the delayed_nodes_tree member of the btrfs_root struct.
It survived a complete fstests run.
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(-)
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;/* * 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 +22 -26
105 lines not on this page · raw message
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 ); +xa_init_flags (&root->delayed_nodes,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 the 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
Quoted 46 lines · Gabriel Niebler
… in the
btrfs_rootstruct. Also adjust all usages of this object to use the XArray API.Signed-off-by Gabriel Niebler <[email protected]>---
Notes:
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 in several places. This patch only converts the
delayed_nodes_treemember of thebtrfs_rootstruct.It survived a complete fstests run.
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(-)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;/* * 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 +0
-0
fs/btrfs/delayed-inode.c static struct btrfs_delayed_node *btrfs_get_delayed_node( · line 81
Quoted 5 lines
fs/btrfs/delayed-inode.c +1
-1@@ -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 =xa_load (&root->delayed_nodes, (unsigned long )ino);
Isn't this problematic, because you'd be truncating the ino in case we have a number which is larger than unsigned long. For architectures which use long as a 64 bit type this cast is a noop since u64 is defined as unsigned long (via typedef unsigned long __u64; typedef __u64 u64). But on arches which use long long for their 64bit type then this would truncate the ino number, so I think this cast is redundant. In any case the code is broken for u64 for arches which use long long and as the author of xarray put it just now:
<willy> yup. It's not a great data structure for storing u64s in
However, looking at the existing radix_tree_insert the index is also an unsigned long. TLDR is remove the cast.
Quoted 3 lines
fs/btrfs/delayed-inode.c +0
-0if (node) {if (btrfs_inode->delayed_node) {
<snip>
Quoted 2 lines
return node; }
<snip>
Quoted 16 lines
fs/btrfs/delayed-inode.c +2
-5@@ -1870,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_tree, - (void **)delayed_nodes, inode_id, -ARRAY_SIZE (delayed_nodes)); -if (!n) {
fs/btrfs/delayed-inode.c void btrfs_kill_delayed_inode_items(struct btrfs_inode *inode) · line 1880
Quoted 10 lines
fs/btrfs/delayed-inode.c +4
-2+if (xa_empty (&root->delayed_nodes)) {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, index, + delayed_node, index) {
Here index is used not only as the index of the current entry but also as the "start from this index". But you are not actually initializing it so index has garbage on the first iteration. If you want to start from the 0th index then you should initialize it when defining it.
fs/btrfs/delayed-inode.c void btrfs_kill_delayed_inode_items(struct btrfs_inode *inode) · line 1886
Quoted 8 lines
fs/btrfs/delayed-inode.c +2
-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 (&delayed_node->refs)) + delayed_nodes[n] =NULL ;
This is broken. What the original code did was query up to 8 delayed nodes at a time and and then for every node which got written into the delayed_nodes array it incremented the refcount so that later the nodes can be destroyed outside of spin_unlock. In your code you don't write the node into the local delayed_nodes array, meaning the for() loop never frees anything.
Quoted 8 lines
fs/btrfs/delayed-inode.c +4
-0+ n++; +if (n >=ARRAY_SIZE (delayed_nodes)) +break ; } + index++;spin_unlock (&root->inode_lock);for (i =0 ; i < n; i++) {
<snip>
Am 13.04.22 um 15:34 schrieb Nikolay Borisov:
Quoted 15 lines · Gabriel Niebler
fs/btrfs/delayed-inode.c static struct btrfs_delayed_node · line 81
Quoted 11 lines
[…]
fs/btrfs/delayed-inode.c +1
-1@@ -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 = xa_load(&root->delayed_nodes, (unsigned long)ino);Isn't this problematic, because you'd be truncating the ino in case we have a number which is larger than unsigned long. For architectures which use long as a 64 bit type this cast is a noop since u64 is defined as unsigned long (via typedef unsigned long
__u64; typedef__u64u64). But on arches which use long long for their 64bit type then this would truncate the ino number, so I think this cast is redundant. In any case the code is broken for u64 for arches which use long long and as the author of xarray put it just now:
Quoted 3 lines
<willy> yup. It's not a great data structure for storing u64s in
However, looking at the existing
radix_tree_insertthe index is also an unsigned long. TLDR is remove the cast.
Right. This is something I wasn't too sure of myself and I lacked the deeper understanding to make a better informed decision here, so thank you for your insight. I will remove the cast.
In particular, the fact that radix trees already have this problem was something I missed (even though it's kind of clear that they must, as it's the same data structure under the hood, but I didn't look too closely at the functions and the fact they take an unsigned long in the same places as the XArray equivalents).
This will also play a role in upcoming patches where I often did the same cast, but now I know that I don't need it. If it worked before, it will work after.
Quoted 18 lines
Quoted 18 lines
fs/btrfs/delayed-inode.c +3
-5@@ -1870,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_tree, - (void **)delayed_nodes, inode_id, - ARRAY_SIZE(delayed_nodes)); - if (!n) { + if (xa_empty(&root->delayed_nodes)) { spin_unlock(&root->inode_lock); break;
Quoted 8 lines
fs/btrfs/delayed-inode.c void btrfs_kill_delayed_inode_items(struct btrfs_inode *inode) · line 1880
Quoted 6 lines
fs/btrfs/delayed-inode.c +3
-2} - inode_id = delayed_nodes[n - 1]->inode_id + 1; - for (i = 0; i < n; i++) { + n = 0; + xa_for_each_start(&root->delayed_nodes, index, + delayed_node, index) {Here index is used not only as the index of the current entry but also as the "start from this index". But you are not actually initializing it so index has garbage on the first iteration. If you want to start from the 0th index then you should initialize it when defining it.
Whoops, what an oversight. Good catch! Thanks for pointing this out! Will fix.
Quoted 10 lines
fs/btrfs/delayed-inode.c void btrfs_kill_delayed_inode_items(struct btrfs_inode *inode) · line 1886
Quoted 8 lines
fs/btrfs/delayed-inode.c +2
-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(&delayed_node->refs)) + delayed_nodes[n] = NULL;This is broken. What the original code did was query up to 8 delayed nodes at a time and and then for every node which got written into the
delayed_nodesarray it incremented the refcount so that later the nodes can be destroyed outside ofspin_unlock. In your code you don't write the node into the localdelayed_nodesarray, meaning thefor()loop never frees anything.
You're right, of course. All that's missing is a
delayed_nodes[n] = delayed_node;
before the if, but without that it doesn't work. I don't know how I missed that one. Again, thanks for noticing! Will fix.
Quoted 13 lines · Gabriel Niebler
… in the
btrfs_rootstruct. Also adjust all usages of this object to use the XArray API.Signed-off-by Gabriel Niebler <[email protected]>---
Notes:
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 2 lines
The btrfs code uses radix trees in several places. This patch only converts the
delayed_nodes_treemember of thebtrfs_rootstruct.
You've put this under the --- marker which means this is not supposed to be in the changelog (as we do for various patch revision commments) but then there would be basically no useful changelog left. That the conversion is done is clear, maybe there are some useful notes or comments what changed and how, eg. the locking.
Am 13.04.22 um 16:14 schrieb David Sterba:
Quoted 11 lines · Gabriel Niebler
Quoted 10 lines
[...]
---Notes:
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 5 lines
Quoted 2 lines
The btrfs code uses radix trees in several places. This patch only converts the
delayed_nodes_treemember of thebtrfs_rootstruct.You've put this under the --- marker which means this is not supposed to be in the changelog (as we do for various patch revision commments) [...]
I did, because I thought that my general waffling about XArrays is not something we need to have in the kernel changelog forerver, however...
Quoted 2 lines
[...] but
then there would be basically no useful changelog left. [...]
That's a good point. I kind of forgot that a good commit message is supposed to say *why* something was done and not just *what* was done, as that's obvious from the diff.
Quoted 3 lines
[...] That the
conversion is done is clear, maybe there are some useful notes or comments what changed and how, eg. the locking.
I'll try to come up with something more satisfying, yet not too verbose.