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

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

[Chao Yu]

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);
 	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);
-- 
2.15.0.55.gc2ece9dc4de6


------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most
engaging tech sites, Slashdot.org! http://sdm.link/slashdot

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

[Gao Xiang]

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".
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)....

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);

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

[Gao Xiang]

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);
>

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

[Gao Xiang]

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@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);
>>
>

Re: [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@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);
>>>
>>
> 
> 
> ------------------------------------------------------------------------------
> 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@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel

------------------------------------------------------------------------------
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@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel