btrfs: remove some duplicated checks in btrfs_previous_*_item()
PATCH 1/1 btrfs: remove some duplicated checks in btrfs_previous_*_item()
In btrfs_previous_item() and btrfs_previous_extent_item() we check btrfs_header_nritems() in a loop.
But in fact we don't need to do it in a loop at all.
Firstly, if a tree block is empty, the whole tree is empty and nodes[0] is the tree root.
We don't need to do anything and can exit immediately.
Secondly, the only timing we could get a slots[0] >= nritems is when the function get called. After the first slots[0]--, the slot should always be <= nritems.
So this patch will move all the nritems related checks out of the loop by:
- Check nritems of nodes[0] to do a quick exit
- Sanitize path->slots[0] before entering the loop
I doubt if there is any caller setting path->slots[0] beyond nritems + 1 (setting to nritems is possible when item is not found). Sanitize path->slots[0] to nritems won't hurt anyway.
- Unconditionally reduce path->slots[0]
Since we're sure all tree blocks should not be empty, and btrfs_prev_leaf() will return with path->slots[0] == nritems, we can safely reduce slots[0] unconditionally.
Just keep an extra ASSERT() to make sure no tree block is empty.
--- fs/btrfs/ctree.c | 52 +++++++++++++++++++++++++++++++++--------------- 1 file changed, 36 insertions(+), 16 deletions(-)
fs/btrfs/ctree.c +36 -16
@@ -4704,23 +4704,39 @@ int btrfs_previous_item(struct btrfs_root *root, {struct btrfs_key found_key;struct extent_buffer *leaf; -u32 nritems; +const u32 nritems =btrfs_header_nritems (path->nodes[0 ]);int ret; +/* +* Check nritems first, if the tree is empty we exit immediately. +* And if this leave is not empty, none of the tree blocks of this root +* should be empty. +*/ +if (nritems ==0 ) +return 1 ; + +/* +* If we're several slots beyond nritems, we reset slot to nritems, +* and it will be handled properly inside the loop. +*/ +if (unlikely (path->slots[0 ] > nritems)) + path->slots[0 ] = nritems; +while (1 ) {if (path->slots[0 ] ==0 ) { ret =btrfs_prev_leaf (root, path);if (ret !=0 )return ret; - }else { - path->slots[0 ]--; } leaf = path->nodes[0 ]; - nritems =btrfs_header_nritems (leaf); -if (nritems ==0 ) -return 1 ; -if (path->slots[0 ] == nritems) - path->slots[0 ]--; +ASSERT (btrfs_header_nritems (leaf)); +/* +* This is for both regular case and above btrfs_prev_leaf() case. +* As btrfs_prev_leaf() will return with path->slots[0] == nritems, +* and we're sure no tree block is empty, we can go safely +* reduce slots[0] here. +*/ + path->slots[0 ]--;btrfs_item_key_to_cpu (leaf, &found_key, path->slots[0 ]);if (found_key.objectid < min_objectid)
@@ -4745,23 +4761,27 @@ int btrfs_previous_extent_item(struct btrfs_root *root, {struct btrfs_key found_key;struct extent_buffer *leaf; -u32 nritems; +const u32 nritems =btrfs_header_nritems (path->nodes[0 ]);int ret; +/* +* Refer to btrfs_previous_item() for the reason of all nritems related +* checks/modifications. +*/ +if (nritems ==0 ) +return 1 ; +if (unlikely (path->slots[0 ] > nritems)) + path->slots[0 ] = nritems; +while (1 ) {if (path->slots[0 ] ==0 ) { ret =btrfs_prev_leaf (root, path);if (ret !=0 )return ret; - }else { - path->slots[0 ]--; } leaf = path->nodes[0 ]; - nritems =btrfs_header_nritems (leaf); -if (nritems ==0 ) -return 1 ; -if (path->slots[0 ] == nritems) - path->slots[0 ]--; +ASSERT (btrfs_header_nritems (leaf)); + path->slots[0 ]--;btrfs_item_key_to_cpu (leaf, &found_key, path->slots[0 ]);if (found_key.objectid < min_objectid)
Signature · 1 line
2.34.1
Quoted 73 lines · Qu Wenruo
In
btrfs_previous_item()andbtrfs_previous_extent_item()we checkbtrfs_header_nritems()in a loop.But in fact we don't need to do it in a loop at all.
Firstly, if a tree block is empty, the whole tree is empty and nodes[0] is the tree root.
We don't need to do anything and can exit immediately.Secondly, the only timing we could get a slots[0] >= nritems is when the function get called. After the first slots[0]--, the slot should always be <= nritems.
So this patch will move all the nritems related checks out of the loop by:
- Check nritems of nodes[0] to do a quick exit
- Sanitize path->slots[0] before entering the loop
I doubt if there is any caller setting path->slots[0] beyond nritems + 1 (setting to nritems is possible when item is not found). Sanitize path->slots[0] to nritems won't hurt anyway.- Unconditionally reduce path->slots[0]
Since we're sure all tree blocks should not be empty, andbtrfs_prev_leaf()will return with path->slots[0] == nritems, we can safely reduce slots[0] unconditionally.
Just keep an extraASSERT()to make sure no tree block is empty.Signed-off-by Qu Wenruo <[email protected]>--- fs/btrfs/ctree.c | 52 +++++++++++++++++++++++++++++++++--------------- 1 file changed, 36 insertions(+), 16 deletions(-)fs/btrfs/ctree.c +16
-6@@ -4704,23 +4704,39 @@ int btrfs_previous_item(struct btrfs_root *root, {struct btrfs_key found_key;struct extent_buffer *leaf; -u32 nritems; +const u32 nritems =btrfs_header_nritems (path->nodes[0 ]);int ret; +/* +* Check nritems first, if the tree is empty we exit immediately. +* And if this leave is not empty, none of the tree blocks of this root +* should be empty. +*/ +if (nritems ==0 ) +return 1 ; + +/* +* If we're several slots beyond nritems, we reset slot to nritems, +* and it will be handled properly inside the loop. +*/ +if (unlikely (path->slots[0 ] > nritems)) + path->slots[0 ] = nritems; +while (1 ) {if (path->slots[0 ] ==0 ) { ret =btrfs_prev_leaf (root, path);if (ret !=0 )return ret; - }else { - path->slots[0 ]--; } leaf = path->nodes[0 ]; - nritems =btrfs_header_nritems (leaf); -if (nritems ==0 ) -return 1 ;
fs/btrfs/ctree.c int btrfs_previous_item(struct btrfs_root *root, · line 4739
Quoted 10 lines
fs/btrfs/ctree.c +8
-2-if (path->slots[0 ] == nritems) - path->slots[0 ]--; +ASSERT (btrfs_header_nritems (leaf)); +/* +* This is for both regular case and above btrfs_prev_leaf() case. +* As btrfs_prev_leaf() will return with path->slots[0] == nritems, +* and we're sure no tree block is empty, we can go safely +* reduce slots[0] here. +*/ + path->slots[0 ]--;
No, this is wrong.btrfs_prev_leaf() computes the previous key and does a search_slot() for it. With this unconditional decrement we can miss the previous key in 2 ways:
1) The previous key exists, and btrfs_prev_leaf() leaves us in a leaf that has it and the slot is btrfs_header_nritems(prev_leaf) - 1 -> the last key on a leaf;
2) The previous key exists, but after btrfs_prev_leaf() released the path and before it called search_slot(), there was a balance operation and it pushed the previous key in the middle of the leaf we had, or some other leaf, and the slot will be something less than btrfs_header_nritems(), it can even be 0.
That's why we have the call to header_nritems() in the loop, and check if slots[0] is == to nritems before decrementing...
Thanks.
Quoted 42 lines
fs/btrfs/ctree.c +12
-8btrfs_item_key_to_cpu (leaf, &found_key, path->slots[0 ]);if (found_key.objectid < min_objectid)@@ -4745,23 +4761,27 @@ int btrfs_previous_extent_item(struct btrfs_root *root, {struct btrfs_key found_key;struct extent_buffer *leaf; -u32 nritems; +const u32 nritems =btrfs_header_nritems (path->nodes[0 ]);int ret; +/* +* Refer to btrfs_previous_item() for the reason of all nritems related +* checks/modifications. +*/ +if (nritems ==0 ) +return 1 ; +if (unlikely (path->slots[0 ] > nritems)) + path->slots[0 ] = nritems; +while (1 ) {if (path->slots[0 ] ==0 ) { ret =btrfs_prev_leaf (root, path);if (ret !=0 )return ret; - }else { - path->slots[0 ]--; } leaf = path->nodes[0 ]; - nritems =btrfs_header_nritems (leaf); -if (nritems ==0 ) -return 1 ; -if (path->slots[0 ] == nritems) - path->slots[0 ]--; +ASSERT (btrfs_header_nritems (leaf)); + path->slots[0 ]--;btrfs_item_key_to_cpu (leaf, &found_key, path->slots[0 ]);if (found_key.objectid < min_objectid)Signature · 1 line
2.34.1
Quoted 89 lines · Filipe Manana
Quoted 73 lines · Qu Wenruo
In
btrfs_previous_item()andbtrfs_previous_extent_item()we checkbtrfs_header_nritems()in a loop.But in fact we don't need to do it in a loop at all.
Firstly, if a tree block is empty, the whole tree is empty and nodes[0] is the tree root.
We don't need to do anything and can exit immediately.Secondly, the only timing we could get a slots[0] >= nritems is when the function get called. After the first slots[0]--, the slot should always be <= nritems.
So this patch will move all the nritems related checks out of the loop by:
- Check nritems of nodes[0] to do a quick exit
- Sanitize path->slots[0] before entering the loop
I doubt if there is any caller setting path->slots[0] beyond nritems + 1 (setting to nritems is possible when item is not found). Sanitize path->slots[0] to nritems won't hurt anyway.- Unconditionally reduce path->slots[0]
Since we're sure all tree blocks should not be empty, andbtrfs_prev_leaf()will return with path->slots[0] == nritems, we can safely reduce slots[0] unconditionally.
Just keep an extraASSERT()to make sure no tree block is empty.Signed-off-by Qu Wenruo <[email protected]>--- fs/btrfs/ctree.c | 52 +++++++++++++++++++++++++++++++++--------------- 1 file changed, 36 insertions(+), 16 deletions(-)fs/btrfs/ctree.c +16
-6@@ -4704,23 +4704,39 @@ int btrfs_previous_item(struct btrfs_root *root, {struct btrfs_key found_key;struct extent_buffer *leaf; -u32 nritems; +const u32 nritems =btrfs_header_nritems (path->nodes[0 ]);int ret; +/* +* Check nritems first, if the tree is empty we exit immediately. +* And if this leave is not empty, none of the tree blocks of this root +* should be empty. +*/ +if (nritems ==0 ) +return 1 ; + +/* +* If we're several slots beyond nritems, we reset slot to nritems, +* and it will be handled properly inside the loop. +*/ +if (unlikely (path->slots[0 ] > nritems)) + path->slots[0 ] = nritems; +while (1 ) {if (path->slots[0 ] ==0 ) { ret =btrfs_prev_leaf (root, path);if (ret !=0 )return ret; - }else { - path->slots[0 ]--; } leaf = path->nodes[0 ]; - nritems =btrfs_header_nritems (leaf); -if (nritems ==0 ) -return 1 ;fs/btrfs/ctree.c int btrfs_previous_item(struct btrfs_root *root, · line 4739
Quoted 10 lines
fs/btrfs/ctree.c +8
-2-if (path->slots[0 ] == nritems) - path->slots[0 ]--; +ASSERT (btrfs_header_nritems (leaf)); +/* +* This is for both regular case and above btrfs_prev_leaf() case. +* As btrfs_prev_leaf() will return with path->slots[0] == nritems, +* and we're sure no tree block is empty, we can go safely +* reduce slots[0] here. +*/ + path->slots[0 ]--;No, this is wrong.
btrfs_prev_leaf()computes the previous key and does asearch_slot()for it. With this unconditional decrement we can miss the previous key in 2 ways:
Quoted 7 lines
1) The previous key exists, and
btrfs_prev_leaf()leaves us in a leaf that has itand the slot is btrfs_header_nritems(prev_leaf) - 1 -> the last key on a leaf;2) The previous key exists, but after
btrfs_prev_leaf()released the path and before it calledsearch_slot(), there was a balance operation and it pushed the previous key in the middle of the leaf we had, or some other leaf, and the slot will be something less thanbtrfs_header_nritems(), it can even be 0.
You're totally right about both cases.
I totally forget that btrfs_prev_leaf() is using serch_slot() other than going up several levels to find the sibling leaf.
Please discard the patch.
Thanks,
Qu
Quoted 49 lines
That's why we have the call to
header_nritems()in the loop, and check if slots[0] is == to nritems before decrementing...Thanks.
Quoted 42 lines
fs/btrfs/ctree.c +12
-9btrfs_item_key_to_cpu (leaf, &found_key, path->slots[0 ]);if (found_key.objectid < min_objectid)@@ -4745,23 +4761,27 @@ int btrfs_previous_extent_item(struct btrfs_root *root, {struct btrfs_key found_key;struct extent_buffer *leaf; -u32 nritems; +const u32 nritems =btrfs_header_nritems (path->nodes[0 ]);int ret; +/* +* Refer to btrfs_previous_item() for the reason of all nritems related +* checks/modifications. +*/ +if (nritems ==0 ) +return 1 ; +if (unlikely (path->slots[0 ] > nritems)) + path->slots[0 ] = nritems; +while (1 ) {if (path->slots[0 ] ==0 ) { ret =btrfs_prev_leaf (root, path);if (ret !=0 )return ret; - }else { - path->slots[0 ]--; } leaf = path->nodes[0 ]; - nritems =btrfs_header_nritems (leaf); -if (nritems ==0 ) -return 1 ; -if (path->slots[0 ] == nritems) - path->slots[0 ]--; +ASSERT (btrfs_header_nritems (leaf)); + path->slots[0 ]--;btrfs_item_key_to_cpu (leaf, &found_key, path->slots[0 ]);if (found_key.objectid < min_objectid) --2.34.1
Quoted 73 lines · Qu Wenruo
In
btrfs_previous_item()andbtrfs_previous_extent_item()we checkbtrfs_header_nritems()in a loop.But in fact we don't need to do it in a loop at all.
Firstly, if a tree block is empty, the whole tree is empty and nodes[0] is the tree root.
We don't need to do anything and can exit immediately.Secondly, the only timing we could get a slots[0] >= nritems is when the function get called. After the first slots[0]--, the slot should always be <= nritems.
So this patch will move all the nritems related checks out of the loop by:
- Check nritems of nodes[0] to do a quick exit
- Sanitize path->slots[0] before entering the loop
I doubt if there is any caller setting path->slots[0] beyond nritems + 1 (setting to nritems is possible when item is not found). Sanitize path->slots[0] to nritems won't hurt anyway.- Unconditionally reduce path->slots[0]
Since we're sure all tree blocks should not be empty, andbtrfs_prev_leaf()will return with path->slots[0] == nritems, we can safely reduce slots[0] unconditionally.
Just keep an extraASSERT()to make sure no tree block is empty.Signed-off-by Qu Wenruo <[email protected]>--- fs/btrfs/ctree.c | 52 +++++++++++++++++++++++++++++++++--------------- 1 file changed, 36 insertions(+), 16 deletions(-)fs/btrfs/ctree.c +16
-6@@ -4704,23 +4704,39 @@ int btrfs_previous_item(struct btrfs_root *root, {struct btrfs_key found_key;struct extent_buffer *leaf; -u32 nritems; +const u32 nritems =btrfs_header_nritems (path->nodes[0 ]);int ret; +/* +* Check nritems first, if the tree is empty we exit immediately. +* And if this leave is not empty, none of the tree blocks of this root +* should be empty. +*/ +if (nritems ==0 ) +return 1 ; + +/* +* If we're several slots beyond nritems, we reset slot to nritems, +* and it will be handled properly inside the loop. +*/ +if (unlikely (path->slots[0 ] > nritems)) + path->slots[0 ] = nritems; +while (1 ) {if (path->slots[0 ] ==0 ) { ret =btrfs_prev_leaf (root, path);if (ret !=0 )return ret; - }else { - path->slots[0 ]--; } leaf = path->nodes[0 ]; - nritems =btrfs_header_nritems (leaf); -if (nritems ==0 ) -return 1 ;
fs/btrfs/ctree.c int btrfs_previous_item(struct btrfs_root *root, · line 4739
Quoted 10 lines
fs/btrfs/ctree.c +8
-2-if (path->slots[0 ] == nritems) - path->slots[0 ]--; +ASSERT (btrfs_header_nritems (leaf)); +/* +* This is for both regular case and above btrfs_prev_leaf() case. +* As btrfs_prev_leaf() will return with path->slots[0] == nritems, +* and we're sure no tree block is empty, we can go safely +* reduce slots[0] here. +*/ + path->slots[0 ]--;
This requires trusting that the thing on disk was ok. The tree-checker won't complain if we read a block with nritems == 0. I think it would be better to do
if (btrfs_header_nritems(leaf) == 0) {
ASSERT(btrfs_header_nritems(leaf));
return -EUCLEAN;
}so we don't get ourselves in trouble. Thanks,
Josef
Quoted 88 lines · Josef Bacik
Quoted 73 lines · Qu Wenruo
In
btrfs_previous_item()andbtrfs_previous_extent_item()we checkbtrfs_header_nritems()in a loop.But in fact we don't need to do it in a loop at all.
Firstly, if a tree block is empty, the whole tree is empty and nodes[0] is the tree root.
We don't need to do anything and can exit immediately.Secondly, the only timing we could get a slots[0] >= nritems is when the function get called. After the first slots[0]--, the slot should always be <= nritems.
So this patch will move all the nritems related checks out of the loop by:
- Check nritems of nodes[0] to do a quick exit
- Sanitize path->slots[0] before entering the loop
I doubt if there is any caller setting path->slots[0] beyond nritems + 1 (setting to nritems is possible when item is not found). Sanitize path->slots[0] to nritems won't hurt anyway.- Unconditionally reduce path->slots[0]
Since we're sure all tree blocks should not be empty, andbtrfs_prev_leaf()will return with path->slots[0] == nritems, we can safely reduce slots[0] unconditionally.
Just keep an extraASSERT()to make sure no tree block is empty.Signed-off-by Qu Wenruo <[email protected]>--- fs/btrfs/ctree.c | 52 +++++++++++++++++++++++++++++++++--------------- 1 file changed, 36 insertions(+), 16 deletions(-)fs/btrfs/ctree.c +16
-6@@ -4704,23 +4704,39 @@ int btrfs_previous_item(struct btrfs_root *root, {struct btrfs_key found_key;struct extent_buffer *leaf; -u32 nritems; +const u32 nritems =btrfs_header_nritems (path->nodes[0 ]);int ret; +/* +* Check nritems first, if the tree is empty we exit immediately. +* And if this leave is not empty, none of the tree blocks of this root +* should be empty. +*/ +if (nritems ==0 ) +return 1 ; + +/* +* If we're several slots beyond nritems, we reset slot to nritems, +* and it will be handled properly inside the loop. +*/ +if (unlikely (path->slots[0 ] > nritems)) + path->slots[0 ] = nritems; +while (1 ) {if (path->slots[0 ] ==0 ) { ret =btrfs_prev_leaf (root, path);if (ret !=0 )return ret; - }else { - path->slots[0 ]--; } leaf = path->nodes[0 ]; - nritems =btrfs_header_nritems (leaf); -if (nritems ==0 ) -return 1 ;fs/btrfs/ctree.c int btrfs_previous_item(struct btrfs_root *root, · line 4739
Quoted 10 lines
fs/btrfs/ctree.c +8
-2-if (path->slots[0 ] == nritems) - path->slots[0 ]--; +ASSERT (btrfs_header_nritems (leaf)); +/* +* This is for both regular case and above btrfs_prev_leaf() case. +* As btrfs_prev_leaf() will return with path->slots[0] == nritems, +* and we're sure no tree block is empty, we can go safely +* reduce slots[0] here. +*/ + path->slots[0 ]--;This requires trusting that the thing on disk was ok. The tree-checker won't complain if we read a block with nritems == 0. I think it would be better to do
Quoted 6 lines
if (btrfs_header_nritems(leaf) == 0) { ASSERT(btrfs_header_nritems(leaf)); return -EUCLEAN; }so we don't get ourselves in trouble. Thanks,
Please discard the patch completely.
Filipe pointed out that, btrfs_prev_leaf() is a btrfs_search_slot() call in fact, by searching previous key (current leave's first key value - 1).
Which could lead to a search slot hit (ret == 0), thus this patch is completely screwed up.
Thanks,
Qu
Quoted 2 lines
Josef