* [PATCH] f2fs: fix to handle looped node chain during recovery @ 2018-02-03 9:44 Chao Yu 2018-02-03 10:35 ` [f2fs-dev] " Gao Xiang 0 siblings, 1 reply; 5+ messages in thread From: Chao Yu @ 2018-02-03 9:44 UTC (permalink / raw) To: jaegeuk; +Cc: Yunlei He, linux-kernel, linux-f2fs-devel 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 ^ permalink raw reply related [flat|nested] 5+ messages in thread
* Re: [f2fs-dev] [PATCH] f2fs: fix to handle looped node chain during recovery 2018-02-03 9:44 [PATCH] f2fs: fix to handle looped node chain during recovery Chao Yu @ 2018-02-03 10:35 ` Gao Xiang 2018-02-03 10:45 ` Gao Xiang 0 siblings, 1 reply; 5+ messages in thread From: Gao Xiang @ 2018-02-03 10:35 UTC (permalink / raw) To: Chao Yu, jaegeuk, Yunlei He; +Cc: linux-kernel, 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 <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); ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [f2fs-dev] [PATCH] f2fs: fix to handle looped node chain during recovery 2018-02-03 10:35 ` [f2fs-dev] " Gao Xiang @ 2018-02-03 10:45 ` Gao Xiang 2018-02-03 11:36 ` Gao Xiang 0 siblings, 1 reply; 5+ messages in thread From: Gao Xiang @ 2018-02-03 10:45 UTC (permalink / raw) To: Chao Yu, jaegeuk, Yunlei He Cc: linux-kernel, linux-f2fs-devel, linux-fsdevel@vger.kernel.org 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); > ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [f2fs-dev] [PATCH] f2fs: fix to handle looped node chain during recovery 2018-02-03 10:45 ` Gao Xiang @ 2018-02-03 11:36 ` Gao Xiang 2018-02-04 15:14 ` Chao Yu 0 siblings, 1 reply; 5+ messages in thread From: Gao Xiang @ 2018-02-03 11:36 UTC (permalink / raw) To: Chao Yu, jaegeuk, Yunlei He Cc: linux-kernel, linux-f2fs-devel, linux-fsdevel@vger.kernel.org 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); >> > ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH] f2fs: fix to handle looped node chain during recovery 2018-02-03 11:36 ` Gao Xiang @ 2018-02-04 15:14 ` Chao Yu 0 siblings, 0 replies; 5+ messages in thread From: Chao Yu @ 2018-02-04 15:14 UTC (permalink / raw) To: Gao Xiang, Chao Yu, jaegeuk, Yunlei He Cc: linux-fsdevel@vger.kernel.org, linux-kernel, linux-f2fs-devel 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 ^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2018-02-04 15:14 UTC | newest] Thread overview: 5+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2018-02-03 9:44 [PATCH] f2fs: fix to handle looped node chain during recovery Chao Yu 2018-02-03 10:35 ` [f2fs-dev] " Gao Xiang 2018-02-03 10:45 ` Gao Xiang 2018-02-03 11:36 ` Gao Xiang 2018-02-04 15:14 ` Chao Yu
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).