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

From: Gao Xiang
Date: Sat Feb 03 2018 - 05:46:04 EST




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