[PATCH v2] btrfs: fix nonzero lowest level handling in btrfs_search_forward()

[PATCH v2] btrfs: fix nonzero lowest level handling in btrfs_search_forward()

[Sun YangKai]

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")
Signed-off-by: Sun YangKai <sunk67188@gmail.com>
---
 fs/btrfs/ctree.c | 44 +++++++++++++++++++-------------------------
 1 file changed, 19 insertions(+), 25 deletions(-)

diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
index a2e7979372cc..3e69e705b5dc 100644
--- a/fs/btrfs/ctree.c
+++ b/fs/btrfs/ctree.c
@@ -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);
-- 
2.49.0

Re: [PATCH v2] btrfs: fix nonzero lowest level handling in btrfs_search_forward()

[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_level related 
logic altogether?

Re: [PATCH v2] btrfs: fix nonzero lowest level handling in btrfs_search_forward()

[David Sterba]

On Tue, Apr 29, 2025 at 02:57:02PM +0800, Sun YangKai wrote:
> 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?

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.

Re: [PATCH v2] btrfs: fix nonzero lowest level handling in btrfs_search_forward()

[Sun YangKai]

> > On Tue, Apr 29, 2025 at 02:57:02PM +0800, Sun YangKai wrote:
> > > 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?
> > 
> > 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_level values. While the code appears to support customized path-
> >lowest_level cases, the actual handling of non-zero lowest_level values
> 
> contains 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- zero lowest_level codepath 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.
> 
> 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] btrfs: remove nonzero lowest level handling in btrfs_search_forward()

[Sun YangKai]

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")
Signed-off-by: Sun YangKai <sunk67188@gmail.com>
---
 fs/btrfs/ctree.c | 58 ++++++++++++++++++++++--------------------------
 1 file changed, 26 insertions(+), 32 deletions(-)

diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
index a2e7979372cc..32844277f2cd 100644
--- a/fs/btrfs/ctree.c
+++ b/fs/btrfs/ctree.c
@@ -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);
-- 
2.49.0

Re: [PATCH v3] btrfs: remove nonzero lowest level handling in btrfs_search_forward()

[Qu Wenruo]

在 2025/5/17 23:17, Sun YangKai 写道:
> 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")
> Signed-off-by: Sun YangKai <sunk67188@gmail.com>
> ---
>   fs/btrfs/ctree.c | 58 ++++++++++++++++++++++--------------------------
>   1 file changed, 26 insertions(+), 32 deletions(-)
> 
> diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
> index a2e7979372cc..32844277f2cd 100644
> --- a/fs/btrfs/ctree.c
> +++ b/fs/btrfs/ctree.c
> @@ -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.

>    *
>    * 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.


>   	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) {

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

> -			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);

Re: [PATCH v3] btrfs: remove nonzero lowest level handling in btrfs_search_forward()

[Qu Wenruo]

在 2025/5/19 10:01, Sun YangKai 写道:
>> 在 2025/5/19 09:07, Sun YangKai 写道:
>> [...]
>>
>>> 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):
>>
>> ```
>> diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
>> index a2e7979372cc..ca63e0dad499 100644
>> --- a/fs/btrfs/ctree.c
>> +++ b/fs/btrfs/ctree.c
>> @@ -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);
>> @@ -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 */
>> -               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;
>> -               }
>>                   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