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

[Chao Yu]

Well, that's classic algorithm for checking loop in a list, as well as
other one we know, in order to decrease time complexity of these algorithms,
their implementations are a little more complex.

But IMO, the issue we are trying to fix is really a corner case, and the
performance in that path is not such critical, so I just intend to fix it
with fewest codes.

On 2018/2/3 19:36, Gao Xiang via Linux-f2fs-devel wrote:
> 
> 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@xxxxxxxxxx>
>>>> Signed-off-by: Chao Yu <yuchao0@xxxxxxxxxx>
>>>> ---
>>>> Â 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);
>>>
>>
> 
> 
> ------------------------------------------------------------------------------
> Check out the vibrant tech community on one of the world's most
> engaging tech sites, Slashdot.org! http://sdm.link/slashdot
> _______________________________________________
> Linux-f2fs-devel mailing list
> Linux-f2fs-devel@xxxxxxxxxxxxxxxxxxxxx
> https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel