btrfs: fix nonzero lowest level handling in btrfs_search_forward()
PATCH v2 1/1 btrfs: fix nonzero lowest level handling in btrfs_search_forward()
Commit 323ac95bce44 ("Btrfs: don't read leaf blocks containing only checksums during truncate") changed the condition from level == 0 to level == path->lowest_level, while its origional purpose is just to do some leaf nodes handling (calling btrfs_item_key_to_cpu()) and skip some code that doesn't fit leaf nodes.
After changing the condition, the code path
1. also handle the non-leaf nodes when path->lowest_level is nonzero, which is wrong. However, it seems that btrfs_search_forward() is never called with a nonzero path->lowest_level, which makes this bug not found before.
2. makes the later if block with the same condition, which is origionally used to handle non-leaf node (calling btrfs_node_key_to_cpu()) when lowest_level is not zero, dead code.
So Use if conditions to skip the non-leaf handling code instead of using goto to make it more clear, and handle both leaf and non-leaf node in the lowest_level loop exit logic.
This changes the behavior when btrfs_search_forward() is called with nonzero path->lowest_level. But this never happens in the current code base, and the previous behavior is wrong. So the change of behavior will not be a problem.
Fix: commit 323ac95bce44 ("Btrfs: don't read leaf blocks containing only checksums during truncate")
--- fs/btrfs/ctree.c | 44 +++++++++++++++++++------------------------- 1 file changed, 19 insertions(+), 25 deletions(-)
fs/btrfs/ctree.c +19 -25
@@ -4636,38 +4636,28 @@ int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key, goto out; } -/* at the lowest level, we're done, setup the path and exit */ -if (level == path->lowest_level) { -if (slot >= nritems) - goto find_next_key; - ret =0 ; - path->slots[level] = slot; -/* Save our key for returning back. */ -btrfs_item_key_to_cpu (cur, min_key, slot); - goto out; - } -if (sret && slot >0 ) +/* +* Not at the lowest level and not a perfect match, +* go back a slot if possible to search lower level. +*/ +if (sret && slot >0 && level > path->lowest_level) slot--;/* -* check this node pointer against the min_trans parameters. +* Check this node pointer against the min_trans parameters. * If it is too old, skip to the next one. */ -while (slot < nritems) { -u64 gen; - - gen =btrfs_node_ptr_generation (cur, slot); -if (gen < min_trans) { +if (level >0 ) { +while (slot < nritems) { +if (btrfs_node_ptr_generation (cur, slot) >= min_trans) +break ; slot++; -continue ; } -break ; } -find_next_key: + path->slots[level] = slot;/* -* we didn't find a candidate key in this node, walk forward -* and find another one +* We didn't find a candidate key in this node, walk forward +* and find another one. */ - path->slots[level] = slot;if (slot >= nritems) { sret =btrfs_find_next_key (root, path, min_key, level, min_trans);
@@ -4678,12 +4668,16 @@ int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key, goto out; } } +/* At the lowest level, we're done. Set the key and exit. */ if (level == path->lowest_level) { ret =0 ; -/* Save our key for returning back. */ -btrfs_node_key_to_cpu (cur, min_key, slot); +if (level ==0 ) +btrfs_item_key_to_cpu (cur, min_key, slot); +else +btrfs_node_key_to_cpu (cur, min_key, slot); goto out; } +/* Search down to a lower level. */ cur =btrfs_read_node_slot (cur, slot);if (IS_ERR (cur)) { ret =PTR_ERR (cur);
Signature · 1 line
2.49.0
Hi maintainers and community,
I'd like to request some feedback on this issue.
Is this behavior not considered a bug, or does it require further work?
Given that this issue never seems to be triggered in the current code base, perhaps we could consider cleaning up and removing the lowest_level related logic altogether?
Quoted 9 lines · Sun YangKai
Hi maintainers and community,
I'd like to request some feedback on this issue.
Is this behavior not considered a bug, or does it require further work?
Given that this issue never seems to be triggered in the current code base, perhaps we could consider cleaning up and removing the
lowest_levelrelated logic altogether?
I've looked at this a few times and I'm not decided what to do. It's an old code and works given that we haven't seen any problems so removing dead code makes sense. OTOH that one function does not pass some values of parameters does not mean want to remove the implementation completely. At least some assertions should be added to handle the case(s) for the removed code if there's a new use.
A message that is not in the archive (sent off-list or not yet received): 6048084.MhkbZ0Pkbq@saltykitkat
Quoted 48 lines
Quoted 13 lines · Sun YangKai
Quoted 11 lines
Hi maintainers and community,
I'd like to request some feedback on this issue.
Is this behavior not considered a bug, or does it require further work?
Given that this issue never seems to be triggered in the current code base,
perhaps we could consider cleaning up and removing thelowest_levelrelated
logic altogether?Quoted 6 lines
I've looked at this a few times and I'm not decided what to do. It's an old code and works given that we haven't seen any problems so removing dead code makes sense. OTOH that one function does not pass some values of parameters does not mean want to remove the implementation completely. At least some assertions should be added to handle the case(s) for the removed code if there's a new use.
Thank you for your kind reply.
The current implementation contains misleading functionality regarding non- zero
lowest_levelvalues. While the code appears to support customized path-Quoted 1 line
lowest_levelcases, the actual handling of non-zerolowest_levelvaluescontains critical flaws. This creates a false impression that the function can operate correctly under these conditions when in reality the implementation is invalid. The presence of this obsolete code path risks user confusion and potential misuse.
So I come up with some options about what we can do:
1. (this is what this patch trying to do) Try to fix the wrong code and make this function work well on non-zero
path->lowest_level. But since the non- zerolowest_levelcodepath is never used, maybe this just changes some dead code to prevent potential errors that may occur in the future.2. Since this function has never been called with non-zero
path->lowest_level, we can safely eliminate the associated validation, permanently disregard the parameter, and explicitly document this behavior (always searching down to level 0) in comments. This simplifies the logic by removing obsolete dead code.3. Remove the dead code like 2, but add assertions when this function is called with a non-zero
path->lowest_path. This can also prevent potential errors.
Quoted 6 lines
4. Leave the code untouched, add a comment saying that never call this with a non-zero
path->lowest_level.Given its legacy status, there's no foreseeable requirement to retain non-zero level search capabilities in this code. So maybe option 2 is good enough.
Sorry I just found that I forget to cc the mail list in the last reply.
I will send a new patch later, maybe this version is better.
YangKai
PATCH v3 1/1 btrfs: remove nonzero lowest level handling in btrfs_search_forward()
Commit 323ac95bce44 ("Btrfs: don't read leaf blocks containing only checksums during truncate") changed the condition from level == 0 to level == path->lowest_level, while its origional purpose is just to do some leaf nodes handling (calling btrfs_item_key_to_cpu()) and skip some code that doesn't fit leaf nodes.
After changing the condition, the code path
1. also handle the non-leaf nodes when path->lowest_level is nonzero, which is wrong. However, it seems that btrfs_search_forward() is never called with a nonzero path->lowest_level, which makes this bug not found before.
2. makes the later if block with the same condition, which is origionally used to handle non-leaf node (calling btrfs_node_key_to_cpu()) when lowest_level is not zero, dead code.
Considering this function is never called with a nonzero path->lowest_path for years and the code handling this case is wrongly implemented, the path->lowest_level related logic is fully removed.
Related dead codes are also removed, and related goto logic is replaced with if conditions, which makes the code easier to read for new comers.
This changes the behavior when btrfs_search_forward() is called with nonzero path->lowest_level: now we will get a warning, and still use 0 as lowest_level. But since this never happens in the current codebase, and the previous behavior is wrong. So the behavior change of behavior will not be a problem.
The bevavior of the function called with a zero path->lowest_level, which is acturally how this function is used in current codebase, should be the same with previous version.
Fix: commit 323ac95bce44 ("Btrfs: don't read leaf blocks containing only checksums during truncate")
--- fs/btrfs/ctree.c | 58 ++++++++++++++++++++++-------------------------- 1 file changed, 26 insertions(+), 32 deletions(-)
fs/btrfs/ctree.c +26 -32
@@ -4592,8 +4592,9 @@ int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,* into min_key, so you can call btrfs_search_slot with cow=1 on the * key and get a writable path. * -* This honors path->lowest_level to prevent descent past a given level -* of the tree. +* This does not honor path->lowest_level any more because this +* function is never called with a nonzero path->lowest_level and the +* implementation of handling it in this function is broken for years. * * min_trans indicates the oldest transaction that you are interested * in walking through. Any nodes or leaves older than min_trans are
@@ -4615,6 +4616,7 @@ int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key,int keep_locks = path->keep_locks;ASSERT (!path->nowait); +WARN_ON (path->lowest_level >0 ); path->keep_locks =1 ; again: cur =btrfs_read_lock_root_node (root);
@@ -4636,38 +4638,29 @@ int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key, goto out; } -/* at the lowest level, we're done, setup the path and exit */ -if (level == path->lowest_level) { -if (slot >= nritems) - goto find_next_key; - ret =0 ; - path->slots[level] = slot; -/* Save our key for returning back. */ -btrfs_item_key_to_cpu (cur, min_key, slot); - goto out; - } -if (sret && slot >0 ) - slot--; -/* -* check this node pointer against the min_trans parameters. -* If it is too old, skip to the next one. -*/ -while (slot < nritems) { -u64 gen; - - gen =btrfs_node_ptr_generation (cur, slot); -if (gen < min_trans) { +if (level >0 ) { +/* +* Not at the lowest level and not a perfect match, +* go one slot back if possible to search lower level. +*/ +if (sret && slot >0 ) + slot--; +/* +* Check this node pointer against the min_trans parameters. +* If it is too old, skip to the next one. +*/ +while (slot < nritems) { +if (btrfs_node_ptr_generation (cur, slot) >= min_trans) +break ; slot++; -continue ; } -break ; } -find_next_key: + + path->slots[level] = slot;/* -* we didn't find a candidate key in this node, walk forward -* and find another one +* We didn't find a candidate key in this node, walk forward +* and find another one. */ - path->slots[level] = slot;if (slot >= nritems) { sret =btrfs_find_next_key (root, path, min_key, level, min_trans);
@@ -4678,12 +4671,13 @@ int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key, goto out; } } -if (level == path->lowest_level) { +/* At the lowest level, we're done. Set the key and exit. */ +if (level ==0 ) { ret =0 ; -/* Save our key for returning back. */ -btrfs_node_key_to_cpu (cur, min_key, slot); +btrfs_item_key_to_cpu (cur, min_key, slot); goto out; } +/* Search down to a lower level. */ cur =btrfs_read_node_slot (cur, slot);if (IS_ERR (cur)) { ret =PTR_ERR (cur);
Signature · 1 line
2.49.0
Re: [PATCH v3] btrfs: remove nonzero lowest level handling in btrfs_search_forward()
Quoted 46 lines · Sun YangKai
Commit
323ac95bce44("Btrfs: don't read leaf blocks containing only checksums during truncate") changed the condition fromlevel == 0tolevel == path->lowest_level, while its origional purpose is just to do some leaf nodes handling (callingbtrfs_item_key_to_cpu()) and skip some code that doesn't fit leaf nodes.After changing the condition, the code path
1. also handle the non-leaf nodes whenpath->lowest_levelis nonzero, which is wrong. However, it seems thatbtrfs_search_forward()is never called with a nonzeropath->lowest_level, which makes this bug not found before.
2. makes the later if block with the same condition, which is origionally used to handle non-leaf node (callingbtrfs_node_key_to_cpu()) whenlowest_levelis not zero, dead code.Considering this function is never called with a nonzero
path->lowest_pathfor years and the code handling this case is wrongly implemented, thepath->lowest_levelrelated logic is fully removed.Related dead codes are also removed, and related goto logic is replaced with if conditions, which makes the code easier to read for new comers.
This changes the behavior when
btrfs_search_forward()is called with nonzeropath->lowest_level: now we will get a warning, and still use 0 aslowest_level. But since this never happens in the current codebase, and the previous behavior is wrong. So the behavior change of behavior will not be a problem.The bevavior of the function called with a zero
path->lowest_level, which is acturally how this function is used in current codebase, should be the same with previous version.Fix: commit
323ac95bce44("Btrfs: don't read leaf blocks containing only checksums during truncate")Signed-off-by Sun YangKai <[email protected]>--- fs/btrfs/ctree.c | 58 ++++++++++++++++++++++-------------------------- 1 file changed, 26 insertions(+), 32 deletions(-)fs/btrfs/ctree.c +0
-0
fs/btrfs/ctree.c int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root, · line 4597
Quoted 8 lines
fs/btrfs/ctree.c +3
-2@@ -4592,8 +4592,9 @@ int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,* into min_key, so you can call btrfs_search_slot with cow=1 on the * key and get a writable path. * -* This honors path->lowest_level to prevent descent past a given level -* of the tree. +* This does not honor path->lowest_level any more because this +* function is never called with a nonzero path->lowest_level and the +* implementation of handling it in this function is broken for years.
This part is not helpful.
Saying something like "path->lowest_level must be 0" is more than enough.
fs/btrfs/ctree.c int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key, · line 4619
Quoted 8 lines
fs/btrfs/ctree.c +1
-0* * min_trans indicates the oldest transaction that you are interested * in walking through. Any nodes or leaves older than min_trans are @@ -4615,6 +4616,7 @@ int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key,int keep_locks = path->keep_locks;ASSERT (!path->nowait); +WARN_ON (path->lowest_level >0 );
For sanity check, ASSERT() is more useful, it crashes debug kernels early for developers.
And of course, you have to run full fstests with CONFIG_BTRFS_ASSERT enbaled to make sure the new ASSERT() is not triggered.
fs/btrfs/ctree.c int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key, · line 4640
Quoted 9 lines
fs/btrfs/ctree.c +0
-2path->keep_locks =1 ; again: cur =btrfs_read_lock_root_node (root);@@ -4636,38 +4638,29 @@ int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key, goto out; } -/* at the lowest level, we're done, setup the path and exit */ -if (level == path->lowest_level) {
Why not just change path->lowest_level to 0 here?
You now put the (level > 0) handling into a more complex block, which doesn't make much sense to me, as your purpose is to reject non-zero lowest_level for this function.
The diff looks way more complex than it should be.
If you want to further cleanup the code, please send out a dedicated patch after adding the ASSERT() and simple "path->lowest_level"->"0" change (and remove the "level == path->lowest_level" check after find_next_key: tag).
Thanks,
Qu
Quoted 68 lines
fs/btrfs/ctree.c +22
-28-if (slot >= nritems) - goto find_next_key; - ret =0 ; - path->slots[level] = slot; -/* Save our key for returning back. */ -btrfs_item_key_to_cpu (cur, min_key, slot); - goto out; - } -if (sret && slot >0 ) - slot--; -/* -* check this node pointer against the min_trans parameters. -* If it is too old, skip to the next one. -*/ -while (slot < nritems) { -u64 gen; - - gen =btrfs_node_ptr_generation (cur, slot); -if (gen < min_trans) { +if (level >0 ) { +/* +* Not at the lowest level and not a perfect match, +* go one slot back if possible to search lower level. +*/ +if (sret && slot >0 ) + slot--; +/* +* Check this node pointer against the min_trans parameters. +* If it is too old, skip to the next one. +*/ +while (slot < nritems) { +if (btrfs_node_ptr_generation (cur, slot) >= min_trans) +break ; slot++; -continue ; } -break ; } -find_next_key: + + path->slots[level] = slot;/* -* we didn't find a candidate key in this node, walk forward -* and find another one +* We didn't find a candidate key in this node, walk forward +* and find another one. */ - path->slots[level] = slot;if (slot >= nritems) { sret =btrfs_find_next_key (root, path, min_key, level, min_trans);@@ -4678,12 +4671,13 @@ int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key, goto out; } } -if (level == path->lowest_level) { +/* At the lowest level, we're done. Set the key and exit. */ +if (level ==0 ) { ret =0 ; -/* Save our key for returning back. */ -btrfs_node_key_to_cpu (cur, min_key, slot); +btrfs_item_key_to_cpu (cur, min_key, slot); goto out; } +/* Search down to a lower level. */ cur =btrfs_read_node_slot (cur, slot);if (IS_ERR (cur)) { ret =PTR_ERR (cur);
A message that is not in the archive (sent off-list or not yet received): 12674804.O9o76ZdvQC@saltykitkat
A message that is not in the archive (sent off-list or not yet received): [email protected]
A message that is not in the archive (sent off-list or not yet received): 5890818.DvuYhMxLoT@saltykitkat
Re: [PATCH v3] btrfs: remove nonzero lowest level handling in btrfs_search_forward()
Quoted 45 lines · Sun YangKai
Quoted 45 lines · Sun YangKai
[...]
Quoted 1 line
Thank you for your reply. I'll fix it and split this into smaller patches.
I don't think you need to split, unless you really have a strong reason to do extra refactor.
Something like this will be enough (not yet tested):
```
fs/btrfs/ctree.c +1
-0@@ -4615,6 +4615,7 @@ int btrfs_search_forward(struct btrfs_root *root,struct btrfs_key *min_key, int keep_locks = path->keep_locks;ASSERT (!path->nowait); +ASSERT (path->lowest_level ==0 ); path->keep_locks =1 ; again:cur = btrfs_read_lock_root_node(root);fs/btrfs/ctree.c +0
-0@@ -4637,7 +4638,7 @@ int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key, }/* at the lowest level, we're done, setup the path and exit */
fs/btrfs/ctree.c +1
-6-if (level == path->lowest_level) { +if (level ==0 ) {if (slot >= nritems) goto find_next_key; ret =0 ;@@ -4678,12 +4679,6 @@ int btrfs_search_forward(struct btrfs_root *root,struct btrfs_key *min_key, goto out; } } -if (level == path->lowest_level) { - ret =0 ; -/* Save our key for returning back. */ -btrfs_node_key_to_cpu (cur, min_key, slot); - goto out;
Quoted 8 lines
Quoted 5 lines
fs/btrfs/ctree.c +0
-1- } cur =btrfs_read_node_slot (cur, slot);if (IS_ERR (cur)) {ret = PTR_ERR(cur);```
Yep! This is exactly what I want. Actually I was doing changes with different purposes so that make things totally messed up :(
And this one is now properly tested too.
Thanks,
Qu