Re: [PATCH 4/4] btrfs: ctree: cleanup btrfs_prev_leaf()

[Sun YangKai <sunk67188@gmail.com>]

On 2025/12/9 20:27, Sun Yangkai wrote:
> 
> 
> 在 2025/12/9 20:05, Filipe Manana 写道:
>> On Tue, Dec 9, 2025 at 3:38 AM Sun YangKai <sunk67188@gmail.com> wrote:
>>>
>>> There's a common parttern in callers of btrfs_prev_leaf:
>>> p->slots[0]-- if p->slots[0] points to a slot with invalid item(nritem).
>>>
>>> So just make btrfs_prev_leaf() ensure that path->slots[0] points to a
>>> valid slot and cleanup its over complex logic.
>>>
>>> Reading and comparing keys in btrfs_prev_leaf() is unnecessary because
>>> when got a ret>0 from btrfs_search_slot(), slots[0] points to where we
>>> should insert the key.
>>
>> Hell no! path->slots[0] can end up pointing to the original key, which is what
>> should be the location for the computed previous key, and the
>> comments there explain how that can happen.
>>
>>> So just slots[0]-- is enough to get the previous
>>> item.
>>
>> All that logic in btrfs_prev_leaf() is necessary.
>>
>> We release the path and then do a btrfs_search_slot() for the computed
>> previous key, but after the release and before the search, the
>> structure of the tree may have changed, keys moved between leaves, new
>> keys added, previous keys removed, and so on.
> 
> Thanks for your reply. Here's my thoughts about this:
> 
> My assumption is that there's not a key between the computed previous key and
> the original key. So...
> 
> 1) When searching for the computed previous key, we may get ret==1 and
> p->slots[0] points to the original key. In this case,
> 
> if (p->slots[0] == 0) // we're the lowest key in the tree.
> 	return 1;
> 
> p->slots[0]--; // move to the previous item.
> return 0;
> 
> is exactly what we want if I understand it correctly. I don't understand why
> it's a special case.
> 
> 2) And if there's an item matches the computed previous key, we will get ret==0
> from btrfs_search_slot() and we will early return after calling
> btrfs_search_slot(). If there's no such an item, then we'll never get an item
> whose key is lower than the key we give to btrfs_search_slot().
> So the second comment block is also not a special case.
> 
> These two cases are not related with how the items moved, added or deleted
> before we call btrfs_search_slot().
> 
> Please correct me if I got anything wrong.
> 
> Thanks.

After reviewing this patch several times, I cannot find anything wrong 
with it. I'd glad to learn a special case which will break the new code.

My assumption is that let's say we have leaf A with key range [100, 180] 
and leaf B with key range [200, ...] at search time (and we don't care 
how those keys distribute before we release path), when searching for 
key 199, we'll always get to leaf A and pointing to the position next to 
the last item of leaf A. Please correct me if my assumption is wrong :)

Let's see the origin code:

	if (path->slots[0] < btrfs_header_nritems(path->nodes[0])) {
		btrfs_item_key(path->nodes[0], &found_key, path->slots[0]);
		ret = btrfs_comp_keys(&found_key, &orig_key);
		if (ret == 0) {
			if (path->slots[0] > 0) {
				path->slots[0]--;
				return 0; // case 1
			}
			return 1; // case 2
		}
	}

	btrfs_item_key(path->nodes[0], &found_key, 0);
	ret = btrfs_comp_keys(&found_key, &key);
	if (ret <= 0)
		return 0; // case 3
	return 1; // case 4

And the new code:

	if (path->slots[0] == 0)
		return 1; // case A

	path->slots[0]--;
	return 0; // case B

For all the origin return branches:

- Case 1: it will go to case B now, the same behavior;
- Case 2: it will go to case A now, the same behavior;
- Case 3: if ret == 0, then the found key matches the key,
	  btrfs_search_slot will return 0 and we'll not get to case 3.
	  So ret must less than 0, and the key of the item at slot 0 is
	  less than the search key so path->slots[0] is greater than
	  0 and we'll go to case B now. The behavior is different,
	  but we make sure pointing to the previous item in new code.
- Case 4: the key of item at slot 0 is larger than the key we give to
	  btrfs_search_slot(). In this case path->slot[0] must be 0 and
	  we'll go to case A now.

The original code's complexity (comparing keys) was an attempt to verify 
if we landed exactly where we started, but this is unnecessary and I 
don't think the previous search result and the release path things 
matter because we're starting a brand new tree search and 
btrfs_search_slot is the source of truth for the current tree structure.
As long as we treat all the things as a brand new search, looking for 
the item with key=(origin_key - 1) or the previous item if it doesn't 
exist, it will be very simple and clear :)

Thanks.

>>
>> I left all such cases commented in detail in btrfs_prev_leaf() for a reason...
>>
>> Removing that logic is just wrong and there's no explanation here for it.
>>
>> Thanks.
>>
>>
>>