linux-kernel - Re: [f2fs-dev] [PATCH] f2fs: fix to handle looped node chain during recovery

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <34884138-31e6-566d-5be3-d62f61a3416e@aol.com>
Date:   Sat, 3 Feb 2018 19:36:19 +0800
From:   Gao Xiang <hsiangkao@....com>
To:     Chao Yu <yuchao0@...wei.com>, jaegeuk@...nel.org,
        Yunlei He <heyunlei@...wei.com>
Cc:     linux-kernel@...r.kernel.org,
        linux-f2fs-devel@...ts.sourceforge.net,
        "linux-fsdevel@...r.kernel.org" <linux-fsdevel@...r.kernel.org>
Subject: Re: [f2fs-dev] [PATCH] f2fs: fix to handle looped node chain during
 recovery


Sorry, I saw the related code entirely, please ignore these replies.


On 2018/2/3 18:45, Gao Xiang wrote:
>
>
> On 2018/2/3 18:35, Gao Xiang wrote:
>> Hi Chao and YunLei,
>>
>>
>> On 2018/2/3 17:44, Chao Yu wrote:
>>> There is no checksum in node block now, so bit-transition from hardware
>>> can make node_footer.next_blkaddr being corrupted w/o any detection,
>>> result in node chain becoming looped one.
>>>
>>> For this condition, during recovery, in order to avoid running into 
>>> dead
>>> loop, let's detect it and just skip out.
>>>
>>> Signed-off-by: Yunlei He <heyunlei@...wei.com>
>>> Signed-off-by: Chao Yu <yuchao0@...wei.com>
>>> ---
>>>   fs/f2fs/recovery.c | 14 ++++++++++++++
>>>   1 file changed, 14 insertions(+)
>>>
>>> diff --git a/fs/f2fs/recovery.c b/fs/f2fs/recovery.c
>>> index b6d1ec620a8c..60dd0cee4820 100644
>>> --- a/fs/f2fs/recovery.c
>>> +++ b/fs/f2fs/recovery.c
>>> @@ -243,6 +243,9 @@ static int find_fsync_dnodes(struct f2fs_sb_info 
>>> *sbi, struct list_head *head,
>>>       struct curseg_info *curseg;
>>>       struct page *page = NULL;
>>>       block_t blkaddr;
>>> +    unsigned int loop_cnt = 0;
>>> +    unsigned int free_blocks = sbi->user_block_count -
>>> +                    valid_user_blocks(sbi);
>> There exists another way to detect loop more faster but only using 
>> two variables.
>> The algorithm is described as simply "B goes forward a steps only A 
>> goes forwards 2 steps".
> "B goes forward a step only when A goes forward 2(or constant x, more 
> than 1) steps".
>
>> For example:
>> 1)
>>    1   2  3  4   5   6     7
>>    |             \             /
>>    |                \------/
>>   A, B
>> 2)
>>    1  2  3  4   5   6     7
>>     |   |        \             /
>>    B   A        \------/
>>  3)
>>    1  2  3  4   5   6     7
>>        |    |     \             /
>>       B   A      \------/
>>   4)
>>    1  2  3  4   5   6     7
>>        |       |\             /
>>       B      A \------/
>> 5)....
>>
>
>
> Sorry, it seems the encoded diagram is in a mess, I try again.
> 1)
>    1 -> 2 -> 3 -> 4 -> 5 ->  6 -> 7
>    |               \             /
>    |                \-----<-----/
>   A, B
> 2)
>    1 -> 2 -> 3 -> 4 -> 5 ->  6 -> 7
>    |    |          \             /
>    |    |           \-----<-----/
>    B    A
> 3)
>    1 -> 2 -> 3 -> 4 -> 5 ->  6 -> 7
>         |    |     \             /
>         |    |      \-----<-----/
>         B    A
> 4)
>    1 -> 2 -> 3 -> 4 -> 5 ->  6 -> 7
>         |         |\             /
>         |         | \-----<-----/
>         B         A
> 5)....
> if B catchs up A, there exists a cycle.
>
>
> Thanks,
>> B will equal A or beyoud A if and only if there has a cycle.
>> It's a more faster algorithm. :D
>>
>> Thanks,
>>
>>>       int err = 0;
>>>         /* get node pages in the current segment */
>>> @@ -295,6 +298,17 @@ static int find_fsync_dnodes(struct 
>>> f2fs_sb_info *sbi, struct list_head *head,
>>>           if (IS_INODE(page) && is_dent_dnode(page))
>>>               entry->last_dentry = blkaddr;
>>>   next:
>>> +        /* sanity check in order to detect looped node chain */
>>> +        if (++loop_cnt >= free_blocks ||
>>> +            blkaddr == next_blkaddr_of_node(page)) {
>>> +            f2fs_msg(sbi->sb, KERN_NOTICE,
>>> +                "%s: detect looped node chain, "
>>> +                "blkaddr:%u, next:%u",
>>> +                __func__, blkaddr, next_blkaddr_of_node(page));
>>> +            err = -EINVAL;
>>> +            break;
>>> +        }
>>> +
>>>           /* check next segment */
>>>           blkaddr = next_blkaddr_of_node(page);
>>>           f2fs_put_page(page, 1);
>>
>