Re: [f2fs-dev] [PATCH] f2fs: fix to handle looped node chain during recovery
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
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
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
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