Re: [PATCH v3 5/7] btrfs-progs: lowmem: do missing check of last item after check_inode_item()

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

On 2018/9/18 下午4:01, Su Yue wrote:
> 
> 
> On 9/18/18 1:32 PM, Qu Wenruo wrote:
>>
>>
>> On 2018/9/17 下午9:24, Su Yue wrote:
>>>
>>>
>>> On 2018/9/17 8:53 PM, Qu Wenruo wrote:
>>>>
>>>>
>>>> On 2018/9/17 下午3:28, Su Yue wrote:
>>>>> After call of check_inode_item(), path may point to the last unchecked
>>>>> slot of the leaf. The outer walk_up_tree() always treats the position
>>>>> as checked slot then skips to the next. The last item will never be
>>>>> checked.
>>>>>
>>>>> While checking backrefs, path passed to walk_up_tree() always
>>>>> points to a checked slot.
>>>>> While checking fs trees, path passed to walk_up_tree() always
>>>>> points to an unchecked slot.
>>>>
>>>> Can we unify this behavior?
>>>> I has considered in three ways:
>>> 1) Change logical of the process_one_leaf. After it returns, path
>>> points to the next slot checked.
>>> To unify it, we can use saved key but will cost one search_slot time
>>> during serval nodes(>=1). Or call btrfs_previous_item() after every time
>>> check_inode_items() returns.
>>>
>>> But why? why should we cost some time to swing the path. So I
>>> abandoned 1).
>>>
>>> 2) Change logical of the check_leaf_items(). What does the function
>>> is just traverse all items then returns, which seems quite natural.
>>> So I abandoned it.
>>
>> Well, this can also be interpreted as "it's a pretty good place to
>> change the behavior".
>>
>> IMHO, since check_leaf_items() are just really simple hub functions, it
>> will just need a btrfs_next_item() in its out: tag.
>>
> After sometime thinking, sorry, the idea should not work as expected.
> In fact, backrefs check and fs check walk a little differently.

Just as discussed offline, unfortunately that's the case.

> 
> Backrefs check always do walk nodes one by one, never skip any nodes.
> Fs check will try to skip shared nodes to speed up
Exactly.

> 
> While checking backrefs with your idea,
> If the tree has many levels.
> Assume before calling btrfs_next_item:
> path->slots[0] points to the one past of the last item.
> path->slots[1] points to the last slot of nodes[1].
> path->slots[2] points to the last slot of nodes[2].
> path->slots[3] points to the one *before* last slot of nodes[3].
> 
> After btrfs_next_item():
> path->slots[0] points to the first item of another leaf.
> path->slots[1] points to the first item of another node.
> path->slots[2] points to the first item of another node.
> path->slots[3] points to the a slot of *old* nodes[3].

These info is pretty useful, please consider include them in next version.

It's not that obvious from the code.

And now your patch makes sense.

Thanks,
Qu

> 
> Then walk_up_tree() is in, it thinks the slot is unchecked then
> returns with *level=0. Then walk_down_tree() just walk from level
> to leaf.
> Backrefs of new nodes[1,2] will never be checked, the most
> obvious negative effect is inaccurate account info.
> Although we can do check is slot the first in walk_up_tree(),
> it's a magic and worse than this patch.
> 
> Thanks,
> Su
> 
>> By that we can unify the behavior of them to all points to the next
>> *unchecked* slot.
>> And no need for the extra parameter.
>>
>> Thanks,
>> Qu
>>
>>>
>>>
>>> 3) It's what the patch does. The extra argument may seems strange,
>>> I preferred to this way.
>>>
>>> Maybe we can do something after check_leaf_items() returns, is it
>>> acceptable? I have no idea.
>>>
>>> Thanks,
>>> Su
>>>
>>>> E.g, always points to an unchecked slot.
>>>>
>>>> It would make things easier and no need for the extra parameter.
>>>>
>>>> Thanks,
>>>> Qu
>>>>
>>>>>
>>>>> Solution:
>>>>> Add an argument @is_checked to walk_up_tree() to decide whether
>>>>> to skip current slot.
>>>>>
>>>>> Fixes: 5e2dc770471b ("btrfs-progs: check: skip shared node or leaf
>>>>> check for low_memory mode")
>>>>> Signed-off-by: Su Yue <suy.fnst@cn.fujitsu.com>
>>>>> ---
>>>>>    check/mode-lowmem.c | 37 +++++++++++++++++++++++++++++++++----
>>>>>    1 file changed, 33 insertions(+), 4 deletions(-)
>>>>>
>>>>> diff --git a/check/mode-lowmem.c b/check/mode-lowmem.c
>>>>> index db44456fd85b..612e5e28e45b 100644
>>>>> --- a/check/mode-lowmem.c
>>>>> +++ b/check/mode-lowmem.c
>>>>> @@ -4597,22 +4597,38 @@ static int walk_down_tree(struct btrfs_root
>>>>> *root, struct btrfs_path *path,
>>>>>        return err;
>>>>>    }
>>>>>    +/*
>>>>> + * Walk up throuh the path. Make path point to next slot to be
>>>>> checked.
>>>>> + * walk_down_tree() should be called after this function.
>>>>> + *
>>>>> + * @root:    root of the tree
>>>>> + * @path:    will point to next slot to check for walk_down_tree()
>>>>> + * @level:    returns with level of next node to be checked
>>>>> + * @is_checked:    means is the current node checked or not
>>>>> + *        if false, the slot is unchecked, do not increase the slot
>>>>> + *        if true, means increase the slot of the current node
>>>>> + *
>>>>> + * Returns 0 means success.
>>>>> + * Returns >0 means the whole loop of walk up/down should be broken.
>>>>> + */
>>>>>    static int walk_up_tree(struct btrfs_root *root, struct btrfs_path
>>>>> *path,
>>>>> -            int *level)
>>>>> +            int *level, bool is_checked)
>>>>>    {
>>>>>        int i;
>>>>>        struct extent_buffer *leaf;
>>>>> +    int skip_cur =s_checked ? 1 : 0;
>>>>>          for (i =level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i];
>>>>> i++) {
>>>>>            leaf =ath->nodes[i];
>>>>> -        if (path->slots[i] + 1 < btrfs_header_nritems(leaf)) {
>>>>> -            path->slots[i]++;
>>>>> +        if (path->slots[i] + skip_cur < btrfs_header_nritems(leaf)) {
>>>>> +            path->slots[i] +=kip_cur;
>>>>>                *level =;
>>>>>                return 0;
>>>>>            }
>>>>>            free_extent_buffer(path->nodes[*level]);
>>>>>            path->nodes[*level] =ULL;
>>>>>            *level = + 1;
>>>>> +        skip_cur =;
>>>>>        }
>>>>>        return 1;
>>>>>    }
>>>>> @@ -4815,7 +4831,20 @@ static int check_btrfs_root(struct btrfs_root
>>>>> *root, int check_all)
>>>>>                break;
>>>>>            }
>>>>>    -        ret =alk_up_tree(root, &path, &level);
>>>>> +        /*
>>>>> +         * The logical of walk trees are shared between backrefs
>>>>> +         * check and fs trees check.
>>>>> +         * In checking backrefs(check_all is true), after
>>>>> +         * check_leaf_items() returns, path points to
>>>>> +         * last checked item.
>>>>> +         * In checking fs roots(check_all is false), after
>>>>> +         * process_one_leaf() returns, path points to unchecked item.
>>>>> +         *
>>>>> +         * walk_up_tree() is reponsible to make path point to next
>>>>> +         * slot to be checked, above case is handled in
>>>>> +         * walk_up_tree().
>>>>> +         */
>>>>> +        ret =alk_up_tree(root, &path, &level, check_all);
>>>>>            if (ret !=) {
>>>>>                /* Normal exit, reset ret to err */
>>>>>                ret =rr;
>>>>>
>>
>>
> 
>