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

2018-02-04 Thread 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 
 Signed-off-by: Chao Yu 
 ---
   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

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

2018-02-03 Thread Gao Xiang via Linux-f2fs-devel 


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 
Signed-off-by: Chao Yu 
---
  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

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

2018-02-03 Thread Gao Xiang via Linux-f2fs-devel 



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 
Signed-off-by: Chao Yu 
---
  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

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

2018-02-03 Thread Gao Xiang via Linux-f2fs-devel 

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 
Signed-off-by: Chao Yu 
---
  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);



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