btrfs: Turn delayed_nodes_tree into an XArray
PATCH v5 1/1 btrfs: Turn delayed_nodes_tree into an XArray
… in the btrfs_root struct and adjust all usages of this object to use the XArray API, because it is notionally easier to use and unserstand, as it provides array semantics, and also takes care of locking for us, further simplifying the code.
Also use the opportunity to do some light refactoring.
---
Changes from v4:
- Fixed breaking syntax error
Changes from v3:
- Replaced goto-label construct with do-while loop (Nikolay)
- Replaced break with equivalent return for better understandability (Nikolay)
- Made use of delayed_nodes array more efficient (Nikolay)
Changes from v2:
- Fixed uninitialised index variable (Nikolay)
- Fixed missing storage of node in array (Nikolay)
- Improved commit message to motivate patch (David)
Changes from v1:
- Reworked patch set into single patch (David)
- New member name delayed_nodes is independent of data strutcture used (David)
- Shortened commit message and made it start with 'btrfs:' (David)
--- fs/btrfs/ctree.h | 4 +- fs/btrfs/delayed-inode.c | 79 +++++++++++++++++++--------------------- fs/btrfs/disk-io.c | 2 +- fs/btrfs/inode.c | 2 +- 4 files changed, 42 insertions(+), 45 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 +38 -41
134 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
@@ -3826,7 +3826,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
fs/btrfs/delayed-inode.c static struct btrfs_delayed_node *btrfs_get_or_create_delayed_node( · line 131
Quoted 2 lines · On Tue, 19 Apr 2022 17:57:21 +0200 Gabriel Niebler <[email protected]> wrote:
fs/btrfs/delayed-inode.c +1
-1-btrfs_init_delayed_node (node, root, ino); + do {
The "do" line appears one character off to the right for me, and upon examination that's because it uses spaces for indentation instead of TABs like all other lines. Did not check if this is the only place.
There is "checkpatch.pl" which would catch issues like this:
https://www.kernel.org/doc/html/latest/dev-tools/checkpatch.html
Signature · 2 lines
With respect, Roman
Quoted 9 lines · Roman Mamedov
fs/btrfs/delayed-inode.c static struct btrfs_delayed_node *btrfs_get_or_create_delayed_node( · line 131
Quoted 2 lines · On Tue, 19 Apr 2022 17:57:21 +0200 Gabriel Niebler <[email protected]> wrote:
fs/btrfs/delayed-inode.c +1
-1-btrfs_init_delayed_node (node, root, ino); + do {The "do" line appears one character off to the right for me, and upon examination that's because it uses spaces for indentation instead of TABs like all other lines. Did not check if this is the only place.
Thanks for catching it, git am did not complain about that so I checked it manually, there was one more place, now fixed in my local copy.
Quoted 11 lines · David Sterba
Quoted 9 lines · Roman Mamedov
fs/btrfs/delayed-inode.c static struct btrfs_delayed_node *btrfs_get_or_create_delayed_node( · line 131
Quoted 2 lines · On Tue, 19 Apr 2022 17:57:21 +0200 Gabriel Niebler <[email protected]> wrote:
fs/btrfs/delayed-inode.c +1
-1-btrfs_init_delayed_node (node, root, ino); + do {The "do" line appears one character off to the right for me, and upon examination that's because it uses spaces for indentation instead of TABs like all other lines. Did not check if this is the only place.
Quoted 3 lines
Thanks for catching it, git am did not complain about that so I checked it manually, there was one more place, now fixed in my local copy.
checkpatch actually found some other stuff as well:
ERROR:CODE_INDENT: code indent should use tabs where possible #65: FILE: fs/btrfs/delayed-inode.c:131:
+ do {$
WARNING:LEADING_SPACE: please, no spaces at the start of a line #65: FILE: fs/btrfs/delayed-inode.c:131:
+ do {$
ERROR:CODE_INDENT: code indent should use tabs where possible #100: FILE: fs/btrfs/delayed-inode.c:151:
+ }$
WARNING:LEADING_SPACE: please, no spaces at the start of a line #100: FILE: fs/btrfs/delayed-inode.c:151:
+ }$
ERROR:CODE_INDENT: code indent should use tabs where possible #154: FILE: fs/btrfs/delayed-inode.c:1888:
+ }$
WARNING:LEADING_SPACE: please, no spaces at the start of a line #154: FILE: fs/btrfs/delayed-inode.c:1888:
+ }$
Quoted 10 lines · Gabriel Niebler
… in the
btrfs_rootstruct and adjust all usages of this object to use the XArray API, because it is notionally easier to use and unserstand, as it provides array semantics, and also takes care of locking for us, further simplifying the code.Also use the opportunity to do some light refactoring.
Signed-off-by Gabriel Niebler <[email protected]>---
<snip>
fs/btrfs/delayed-inode.c void btrfs_kill_delayed_inode_items(struct btrfs_inode *inode) · line 1868
Quoted 8 lines
fs/btrfs/delayed-inode.c +2
-1@@ -1870,29 +1863,33 @@ 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_node;struct btrfs_delayed_node *delayed_nodes[8 ];
Actually in order for the new code to be correct this array needs to be zero-initialized upon every iteration of the while() loop. That's because as it stands ATM delayed_nodes would retain the value from the previous iteration. What this could lead to is on the last iteration we potentially have 8 nodes in delayed_nodes which have been freed, so if in the last iteration of the xa_for_each_start we copy only 3 nodes the array would still have 8 nodes in total - 3 from the last iteration and 5 stale from the previous since they haven't been cleared out. So the final for() loop which does the freeing would incur a double free on the 5 already-freed entries.
To fix this you either need to clear delayed_nodes[i] in the final for loop, so simply define it inside the while() like so:
struct btrfs_delayed_node *delayed_nodes[8] = {};
That would ensure that on every iteration of the while() loop only those entries which have been poopulated by the inner xa_for_each are non-null when the final for loop executes.
Quoted 36 lines
fs/btrfs/delayed-inode.c +12
-9int 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 ; +return ; } - 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) {/* * 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] = delayed_node; + n++; + } +if (n >=ARRAY_SIZE (delayed_nodes)) +break ; } + index++;spin_unlock (&root->inode_lock);for (i =0 ; i < n; i++) {
<snip>
Am 20.04.22 um 09:09 schrieb Nikolay Borisov:
Quoted 11 lines · Gabriel Niebler
fs/btrfs/delayed-inode.c void btrfs_kill_delayed_inode_items(struct · line 1868
Quoted 8 lines
fs/btrfs/delayed-inode.c +2
-1@@ -1870,29 +1863,33 @@ 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_node; struct btrfs_delayed_node *delayed_nodes[8];Actually in order for the new code to be correct this array needs to be zero-initialized upon every iteration of the
while()loop. That's because as it stands ATMdelayed_nodeswould retain the value from the previous iteration. What this could lead to is on the last iteration we potentially have 8 nodes indelayed_nodeswhich have been freed, so if in the last iteration of thexa_for_each_startwe copy only 3 nodes the array would still have 8 nodes in total - 3 from the last iteration and 5 stale from the previous since they haven't been cleared out. So the finalfor()loop which does the freeing would incur a double free on the 5 already-freed entries.
Oh, you're right! I must not have thought about the *last* iteration, but yeah: that's a problem!
Quoted 3 lines
To fix this you either need to clear delayed_nodes[i] in the final for loop, so simply define it inside the
while()like so:struct
btrfs_delayed_node*delayed_nodes[8] = {};
I will do that. Thanks for introducing me to this neat trick how to initialise an array to all NULLs, BTW. I admit I had to look it up, but now it'll save me from writing another loop...
<snip>
I'll also use the opportunity to fix the whitespace issues.
Sorry for the delay, BTW, don't know why I didn't see the message earlier.
I looked at this again, to see how this obvious problem could have slipped by me, and found something interesting...
Am 20.04.22 um 09:09 schrieb Nikolay Borisov:
Quoted 14 lines · Gabriel Niebler
Quoted 10 lines
… in the
btrfs_rootstruct and adjust all usages of this object to use the XArray API, because it is notionally easier to use and unserstand, as it provides array semantics, and also takes care of locking for us, further simplifying the code.Also use the opportunity to do some light refactoring.
Signed-off-by Gabriel Niebler <[email protected]>---
<snip>
Quoted 10 lines
fs/btrfs/delayed-inode.c void btrfs_kill_delayed_inode_items(struct · line 1868
Quoted 8 lines
fs/btrfs/delayed-inode.c +2
-1@@ -1870,29 +1863,33 @@ 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_node; struct btrfs_delayed_node *delayed_nodes[8];Actually in order for the new code to be correct this array needs to be zero-initialized upon every iteration of the
while()loop. That's because as it stands ATMdelayed_nodeswould retain the value from the previous iteration.
That is correct.
Quoted 1 line
What this could lead to is on the last iteration we potentially have 8 nodes in
delayed_nodeswhich have been freed, so if in the last iteration of thexa_for_each_startwe copy only 3 nodes the array would still have 8 nodes in total - 3 from the last iteration and 5 stale from the previous since they haven't been cleared out.
Still correct and a similar situation could occur when there are fewer than 8 delayed nodes in the array to begin with. Then the uninitialised entries in the array would contain garbage...
Quoted 1 line
So the final
for()loop which does the freeing would incur a double free on the 5 already-freed entries.
Except that it never gets there, because it only goes up to 'n' and n will have the value of the highest *actual* entry in _this_ iteration of the enclosing while-loop.
<snip>
Quoted 25 lines
Quoted 25 lines
fs/btrfs/delayed-inode.c +7
-9int 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; + return; } - 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) { /* * 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] = delayed_node;
Quoted 8 lines
fs/btrfs/delayed-inode.c void btrfs_kill_delayed_inode_items(struct btrfs_inode *inode) · line 1895
Quoted 8 lines
fs/btrfs/delayed-inode.c +5
-0+ n++; + } + if (n >= ARRAY_SIZE(delayed_nodes)) + break; } + index++; spin_unlock(&root->inode_lock); for (i = 0; i < n; i++) {
There it is. This loop will never encounter old (already freed) or uninitialised entries, AFAICS.
I'd say that there actually isn't a problem with this code.
Now the question is whether the change should still be done. Declaring and initialising the array for each iteration incurs a little overhead, though, so I don't really see why it should be.
And if not, should I then resubmit purely for the whitespace changes?
Quoted 92 lines · Gabriel Niebler
I looked at this again, to see how this obvious problem could have slipped by me, and found something interesting...
Am 20.04.22 um 09:09 schrieb Nikolay Borisov:
Quoted 15 lines · Gabriel Niebler
Quoted 11 lines
… in the
btrfs_rootstruct and adjust all usages of this object to use the
XArray API, because it is notionally easier to use and unserstand, as it provides array semantics, and also takes care of locking for us, further simplifying the code.Also use the opportunity to do some light refactoring.
Signed-off-by Gabriel Niebler <[email protected]>---
<snip>
Quoted 13 lines
fs/btrfs/delayed-inode.c void btrfs_kill_delayed_inode_items(struct · line 1868
Quoted 8 lines
fs/btrfs/delayed-inode.c +2
-1@@ -1870,29 +1863,33 @@ 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_node; struct btrfs_delayed_node *delayed_nodes[8];Actually in order for the new code to be correct this array needs to be zero-initialized upon every iteration of the
while()loop. That's because as it stands ATMdelayed_nodeswould retain the value from the previous iteration.That is correct.
Quoted 5 lines
What this could lead to is on the last iteration we potentially have 8 nodes in
delayed_nodeswhich have been freed, so if in the last iteration of thexa_for_each_startwe copy only 3 nodes the array would still have 8 nodes in total - 3 from the last iteration and 5 stale from the previous since they haven't been cleared out.Still correct and a similar situation could occur when there are fewer than 8 delayed nodes in the array to begin with. Then the uninitialised entries in the array would contain garbage...
Quoted 3 lines
So the
finalfor()loop which does the freeing would incur a double free on the 5 already-freed entries.Except that it never gets there, because it only goes up to 'n' and n will have the value of the highest *actual* entry in _this_ iteration of the enclosing while-loop.
<snip>
Quoted 25 lines
Quoted 25 lines
fs/btrfs/delayed-inode.c +7
-9int 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; + return; } - 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) { /* * 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] = delayed_node;Quoted 8 lines
fs/btrfs/delayed-inode.c void btrfs_kill_delayed_inode_items(struct btrfs_inode *inode) · line 1895
Quoted 8 lines
fs/btrfs/delayed-inode.c +5
-0+ n++; + } + if (n >= ARRAY_SIZE(delayed_nodes)) + break; } + index++; spin_unlock(&root->inode_lock); for (i = 0; i < n; i++) {There it is. This loop will never encounter old (already freed) or uninitialised entries, AFAICS.
Quoted 7 lines
I'd say that there actually isn't a problem with this code.
Now the question is whether the change should still be done. Declaring and initialising the array for each iteration incurs a little overhead, though, so I don't really see why it should be.
And if not, should I then resubmit purely for the whitespace changes?
Please resend, there are several changes, thanks.
Nikolay Borisov
Reviewed-byOn 25.04.22 г. 12:28 ч., Gabriel Niebler wrote:
<snip>
Quoted 35 lines
Quoted 26 lines
Quoted 26 lines
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;
+ return;
}
-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) {
/*
* 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] =delayed_node;Quoted 8 lines
Quoted 8 lines
+ n++;
+ }
+ if (n >=ARRAY_SIZE(delayed_nodes))
+ break;
}
+ index++;
spin_unlock(&root->inode_lock);
for (i = 0; i < n; i++) {
Quoted 3 lines
There it is. This loop will never encounter old (already freed) or uninitialised entries, AFAICS.
I'd say that there actually isn't a problem with this code.
You are right, the code as-is is correct. I have 2 more suggestions but at this point they can be considered "bike shed" so you might as well disregard them in which case it's only the whitespace issue that remains and David could probably fix this. Here are the suggestions:
1. The 'n' variable could be defined inside the while() loop:
int n = 0;
That makes it obvious its lifetime is within the loop and it's always initialized to 0.
2. The kernel now moved to using -std=gnu11 (starting with e8c07082a810 ("Kbuild: move to -std=gnu11")) meaning variables can now be defined inside for() loop bodies like:
for (int i = 0; i < n; i++)
IMO it would be good if we gradually start moving code to using this.
Again I consider those 2 minor and the patch as-is is good to go so it's up to David to decide if they are worth it.
Thanks for sticking with it.
<snip>
Am 26.04.22 um 09:40 schrieb Nikolay Borisov:
Quoted 7 lines
[...]
You are right, the code as-is is correct. I have 2 more suggestions but at this point they can be considered "bike shed" so you might as well disregard them in which case it's only the whitespace issue that remains and David could probably fix this. Here are the suggestions:1. The 'n' variable could be defined inside the
while()loop:int n = 0;
Quoted 7 lines
That makes it obvious its lifetime is within the loop and it's always initialized to 0.
2. The kernel now moved to using -std=gnu11 (starting with
e8c07082a810("Kbuild: move to -std=gnu11")) meaning variables can now be defined insidefor()loop bodies like:for (int i = 0; i < n; i++)
IMO it would be good if we gradually start moving code to using this.
I like both of these suggestions and will implement them.
Quoted 1 line
Again I consider those 2 minor and the patch as-is is good to go so it's up to David to decide if they are worth it.
David has already asked me to resubmit with the whitespace fixes in place, so I will just do that with your suggestions added in.
Quoted 1 line
Thanks for sticking with it.
My pleasure.
Quoted 7 lines · Nikolay Borisov
2. The kernel now moved to using -std=gnu11 (starting with
e8c07082a810("Kbuild: move to -std=gnu11")) meaning variables can now be defined insidefor()loop bodies like:for (int i = 0; i < n; i++)
IMO it would be good if we gradually start moving code to using this.
OK, I'm not aware of any problems we'd run into, the minimum compiler version is old enough for all who care and fixups to change it back to pre-C11 is easy.
We'd have to select a subset of the allowed features as not all of them are free of controversy. The variable definition inside for() is OK.