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

[Gao Xiang <hsiangkao@aol.com>]

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@huawei.com>
>> Signed-off-by: Chao Yu <yuchao0@huawei.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);
>