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

[Sun Yangkai <sunk67188@gmail.com>]

在 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.
> 
> 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.
> 
> 
> 
>>
>> And then remove the related logic and cleanup the callers.
>>
>> ASSERT(path->slots[0] < btrfs_header_nritems(path->nodes[0]))
>> is enough to make sure that nritems != 0 and slots[0] points to a valid
>> btrfs_item.
>>
>> And getting a `nritems==0` when btrfs_prev_leaf() returns 0 is a logic
>> error because btrfs_pref_leaf() should always
>>
>> 1. either find a non-empty leaf
>> 2. or return 1
>>
>> So we can use ASSERT here.
>>
>> No functional changes.
>>
>> Signed-off-by: Sun YangKai <sunk67188@gmail.com>
>> ---
>>  fs/btrfs/ctree.c | 100 +++++++++--------------------------------------
>>  1 file changed, 19 insertions(+), 81 deletions(-)
>>
>> diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
>> index bb886f9508e2..07e6433cde61 100644
>> --- a/fs/btrfs/ctree.c
>> +++ b/fs/btrfs/ctree.c
>> @@ -2365,12 +2365,9 @@ int btrfs_search_old_slot(struct btrfs_root *root, const struct btrfs_key *key,
>>  static int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
>>  {
>>         struct btrfs_key key;
>> -       struct btrfs_key orig_key;
>> -       struct btrfs_disk_key found_key;
>>         int ret;
>>
>>         btrfs_item_key_to_cpu(path->nodes[0], &key, 0);
>> -       orig_key = key;
>>
>>         if (key.offset > 0) {
>>                 key.offset--;
>> @@ -2390,48 +2387,12 @@ static int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
>>         if (ret <= 0)
>>                 return ret;
>>
>> -       /*
>> -        * Previous key not found. Even if we were at slot 0 of the leaf we had
>> -        * before releasing the path and calling btrfs_search_slot(), we now may
>> -        * be in a slot pointing to the same original key - this can happen if
>> -        * after we released the path, one of more items were moved from a
>> -        * sibling leaf into the front of the leaf we had due to an insertion
>> -        * (see push_leaf_right()).
>> -        * If we hit this case and our slot is > 0 and just decrement the slot
>> -        * so that the caller does not process the same key again, which may or
>> -        * may not break the caller, depending on its logic.
>> -        */
>> -       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;
>> -                       }
>> -                       /*
>> -                        * At slot 0, same key as before, it means orig_key is
>> -                        * the lowest, leftmost, key in the tree. We're done.
>> -                        */
>> -                       return 1;
>> -               }
>> -       }
>> +       /* There's no smaller keys in the whole tree. */
>> +       if (path->slots[0] == 0)
>> +               return 1;
>>
>> -       btrfs_item_key(path->nodes[0], &found_key, 0);
>> -       ret = btrfs_comp_keys(&found_key, &key);
>> -       /*
>> -        * We might have had an item with the previous key in the tree right
>> -        * before we released our path. And after we released our path, that
>> -        * item might have been pushed to the first slot (0) of the leaf we
>> -        * were holding due to a tree balance. Alternatively, an item with the
>> -        * previous key can exist as the only element of a leaf (big fat item).
>> -        * Therefore account for these 2 cases, so that our callers (like
>> -        * btrfs_previous_item) don't miss an existing item with a key matching
>> -        * the previous key we computed above.
>> -        */
>> -       if (ret <= 0)
>> -               return 0;
>> -       return 1;
>> +       path->slots[0]--;
>> +       return 0;
>>  }
>>
>>  /*
>> @@ -2461,19 +2422,10 @@ int btrfs_search_slot_for_read(struct btrfs_root *root,
>>                 if (p->slots[0] >= btrfs_header_nritems(p->nodes[0]))
>>                         return btrfs_next_leaf(root, p);
>>         } else {
>> -               if (p->slots[0] == 0) {
>> -                       ret = btrfs_prev_leaf(root, p);
>> -                       if (ret < 0)
>> -                               return ret;
>> -                       if (!ret) {
>> -                               if (p->slots[0] == btrfs_header_nritems(p->nodes[0]))
>> -                                       p->slots[0]--;
>> -                               return 0;
>> -                       }
>> -                       return 1;
>> -               } else {
>> -                       p->slots[0]--;
>> -               }
>> +               if (p->slots[0] == 0)
>> +                       return btrfs_prev_leaf(root, p);
>> +
>> +               p->slots[0]--;
>>         }
>>         return 0;
>>  }
>> @@ -4957,26 +4909,19 @@ int btrfs_previous_item(struct btrfs_root *root,
>>                         int type)
>>  {
>>         struct btrfs_key found_key;
>> -       struct extent_buffer *leaf;
>> -       u32 nritems;
>>         int ret;
>>
>>         while (1) {
>>                 if (path->slots[0] == 0) {
>>                         ret = btrfs_prev_leaf(root, path);
>> -                       if (ret != 0)
>> +                       if (ret)
>>                                 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)
>> +               } else
>>                         path->slots[0]--;
>>
>> -               btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
>> +               ASSERT(path->slots[0] < btrfs_header_nritems(path->nodes[0]));
>> +
>> +               btrfs_item_key_to_cpu(path->nodes[0], &found_key, path->slots[0]);
>>                 if (found_key.objectid < min_objectid)
>>                         break;
>>                 if (found_key.type == type)
>> @@ -4998,26 +4943,19 @@ int btrfs_previous_extent_item(struct btrfs_root *root,
>>                         struct btrfs_path *path, u64 min_objectid)
>>  {
>>         struct btrfs_key found_key;
>> -       struct extent_buffer *leaf;
>> -       u32 nritems;
>>         int ret;
>>
>>         while (1) {
>>                 if (path->slots[0] == 0) {
>>                         ret = btrfs_prev_leaf(root, path);
>> -                       if (ret != 0)
>> +                       if (ret)
>>                                 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)
>> +               } else
>>                         path->slots[0]--;
>>
>> -               btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
>> +               ASSERT(path->slots[0] < btrfs_header_nritems(path->nodes[0]));
>> +
>> +               btrfs_item_key_to_cpu(path->nodes[0], &found_key, path->slots[0]);
>>                 if (found_key.objectid < min_objectid)
>>                         break;
>>                 if (found_key.type == BTRFS_EXTENT_ITEM_KEY ||
>> --
>> 2.51.2
>>
>>