Re: [PATCH] btrfs: remove some duplicated checks in btrfs_previous_*_item()

[Qu Wenruo <quwenruo.btrfs@gmx.com>]

On 2021/12/14 22:37, Josef Bacik wrote:
> On Tue, Dec 14, 2021 at 03:14:11PM +0800, Qu Wenruo wrote:
>> 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.
>>
>> Signed-off-by: Qu Wenruo <wqu@suse.com>
>> ---
>>   fs/btrfs/ctree.c | 52 +++++++++++++++++++++++++++++++++---------------
>>   1 file changed, 36 insertions(+), 16 deletions(-)
>>
>> diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
>> index 781537692a4a..555345aed84d 100644
>> --- a/fs/btrfs/ctree.c
>> +++ b/fs/btrfs/ctree.c
>> @@ -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]--;
>
> 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,

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
>
> Josef