| Message ID | 20230516142722.18931-1-guochunhai@vivo.com (mailing list archive) |
|---|---|
| State | Superseded |
| Headers | show |
| Series | [f2fs-dev,v2] fsck.f2fs: Detect and fix looped node chain efficiently | expand |
On 2023/5/16 22:27, Chunhai Guo wrote: > find_fsync_inode() detect the looped node chain by comparing the loop > counter with free blocks. While it may take tens of seconds to quit when > the free blocks are large enough. We can use Floyd's cycle detection > algorithm to make the detection more efficient, and fix the issue by > filling a NULL address in the last node of the chain. > > Below is the log we encounter on a 256GB UFS storage and it takes about > 25 seconds to detect looped node chain. After changing the algorithm, it > takes about 20ms to finish the same job. > > [ 10.822904] fsck.f2fs: Info: version timestamp cur: 17, prev: 430 > [ 10.822949] fsck.f2fs: [update_superblock: 762] Info: Done to > update superblock > [ 10.822953] fsck.f2fs: Info: superblock features = 1499 : > encrypt verity extra_attr project_quota quota_ino casefold > [ 10.822956] fsck.f2fs: Info: superblock encrypt level = 0, salt = > 00000000000000000000000000000000 > [ 10.822960] fsck.f2fs: Info: total FS sectors = 59249811 (231444 > MB) > [ 35.852827] fsck.f2fs: detect looped node chain, > blkaddr:1114802, next:1114803 > [ 35.852842] fsck.f2fs: [f2fs_do_mount:3846] record_fsync_data > failed > [ 35.856106] fsck.f2fs: fsck.f2fs terminated by exit(255) > > Signed-off-by: Chunhai Guo <guochunhai@vivo.com> > --- > fsck/mount.c | 122 +++++++++++++++++++++++++++++++++++++++++++-------- > 1 file changed, 104 insertions(+), 18 deletions(-) > > diff --git a/fsck/mount.c b/fsck/mount.c > index df0314d57caf..478043035c95 100644 > --- a/fsck/mount.c > +++ b/fsck/mount.c > @@ -3394,22 +3394,89 @@ static void destroy_fsync_dnodes(struct list_head *head) > del_fsync_inode(entry); > } > > +static int find_node_blk_fast(struct f2fs_sb_info *sbi, block_t *blkaddr_fast, > + struct f2fs_node *node_blk_fast, bool *is_detecting) > +{ > + int i, err; > + > + for (i = 0; i < 2; i++) { > + if (!f2fs_is_valid_blkaddr(sbi, *blkaddr_fast, META_POR)) { > + *is_detecting = false; > + return 0; > + } > + > + err = dev_read_block(node_blk_fast, *blkaddr_fast); > + if (err) > + return err; > + > + if (!is_recoverable_dnode(sbi, node_blk_fast)) { > + *is_detecting = false; > + return 0; > + } > + > + *blkaddr_fast = next_blkaddr_of_node(node_blk_fast); > + } > + > + return 0; > +} > + > +static int loop_node_chain_fix(struct f2fs_sb_info *sbi, > + block_t blkaddr_fast, struct f2fs_node *node_blk_fast, > + block_t blkaddr, struct f2fs_node *node_blk) > +{ > + block_t blkaddr_entry, blkaddr_tmp; > + int err; > + > + /* find the entry point of the looped node chain */ > + while (blkaddr_fast != blkaddr) { > + err = dev_read_block(node_blk_fast, blkaddr_fast); > + if (err) > + return err; > + blkaddr_fast = next_blkaddr_of_node(node_blk_fast); > + > + err = dev_read_block(node_blk, blkaddr); > + if (err) > + return err; > + blkaddr = next_blkaddr_of_node(node_blk); > + } > + blkaddr_entry = blkaddr; > + > + /* find the last node of the chain */ > + do { > + blkaddr_tmp = blkaddr; > + err = dev_read_block(node_blk, blkaddr); > + if (err) > + return err; > + blkaddr = next_blkaddr_of_node(node_blk); > + } while (blkaddr != blkaddr_entry); > + > + /* fix the blkaddr of last node with NULL_ADDR. */ > + node_blk->footer.next_blkaddr = NULL_ADDR; If node_blk is inode block, the change will break its chksum. Or we can record blkaddr_tmp into f2fs_configuration? And break the loop once we traverse to the blkaddr during find_fsync_inode() and traverse_dnodes()? > + err = dev_write_block(node_blk, blkaddr_tmp); > + if (!err) > + FIX_MSG("Fix looped node chain on blkaddr %u\n", > + blkaddr_tmp); > + > + return err; > +} > + > static int find_fsync_inode(struct f2fs_sb_info *sbi, struct list_head *head) > { > struct curseg_info *curseg; > - struct f2fs_node *node_blk; > - block_t blkaddr; > - unsigned int loop_cnt = 0; > - unsigned int free_blocks = MAIN_SEGS(sbi) * sbi->blocks_per_seg - > - sbi->total_valid_block_count; > + struct f2fs_node *node_blk, *node_blk_fast; > + block_t blkaddr, blkaddr_fast; > + bool is_detecting = true; > int err = 0; > > + node_blk = calloc(F2FS_BLKSIZE, 1); > + node_blk_fast = calloc(F2FS_BLKSIZE, 1); > + ASSERT(node_blk && node_blk_fast); > + > +retry: > /* get node pages in the current segment */ > curseg = CURSEG_I(sbi, CURSEG_WARM_NODE); > blkaddr = NEXT_FREE_BLKADDR(sbi, curseg); > - > - node_blk = calloc(F2FS_BLKSIZE, 1); > - ASSERT(node_blk); > + blkaddr_fast = blkaddr; > > while (1) { > struct fsync_inode_entry *entry; > @@ -3440,19 +3507,38 @@ static int find_fsync_inode(struct f2fs_sb_info *sbi, struct list_head *head) > if (IS_INODE(node_blk) && is_dent_dnode(node_blk)) > entry->last_dentry = blkaddr; > next: > - /* sanity check in order to detect looped node chain */ > - if (++loop_cnt >= free_blocks || > - blkaddr == next_blkaddr_of_node(node_blk)) { > - MSG(0, "\tdetect looped node chain, blkaddr:%u, next:%u\n", > - blkaddr, > - next_blkaddr_of_node(node_blk)); > - err = -1; > - break; > - } > - > blkaddr = next_blkaddr_of_node(node_blk); > + > + /* sanity check to detect looped node chain with Floyd's cycle > + * detection algorithm > + */ > + if (is_detecting) { > + err = find_node_blk_fast(sbi, &blkaddr_fast, node_blk_fast, > + &is_detecting); > + if (err) > + break; > + > + if (blkaddr_fast == blkaddr) { if (blkaddr_fast != blkaddr) continue; err = loop_node_chain_fix() if (err) break; To avoid too many indentions. Thanks, > + MSG(0, "\tdetect looped node chain, blkaddr:%u\n", > + blkaddr); > + > + err = loop_node_chain_fix(sbi, > + NEXT_FREE_BLKADDR(sbi, curseg), > + node_blk_fast, blkaddr, node_blk); > + if (!err) { > + /* after fixing the looped node chain, > + * retry agian. > + */ > + is_detecting = false; > + destroy_fsync_dnodes(head); > + goto retry; > + } else > + break; > + } > + } > } > > + free(node_blk_fast); > free(node_blk); > return err; > }
diff --git a/fsck/mount.c b/fsck/mount.c index df0314d57caf..478043035c95 100644 --- a/fsck/mount.c +++ b/fsck/mount.c @@ -3394,22 +3394,89 @@ static void destroy_fsync_dnodes(struct list_head *head) del_fsync_inode(entry); } +static int find_node_blk_fast(struct f2fs_sb_info *sbi, block_t *blkaddr_fast, + struct f2fs_node *node_blk_fast, bool *is_detecting) +{ + int i, err; + + for (i = 0; i < 2; i++) { + if (!f2fs_is_valid_blkaddr(sbi, *blkaddr_fast, META_POR)) { + *is_detecting = false; + return 0; + } + + err = dev_read_block(node_blk_fast, *blkaddr_fast); + if (err) + return err; + + if (!is_recoverable_dnode(sbi, node_blk_fast)) { + *is_detecting = false; + return 0; + } + + *blkaddr_fast = next_blkaddr_of_node(node_blk_fast); + } + + return 0; +} + +static int loop_node_chain_fix(struct f2fs_sb_info *sbi, + block_t blkaddr_fast, struct f2fs_node *node_blk_fast, + block_t blkaddr, struct f2fs_node *node_blk) +{ + block_t blkaddr_entry, blkaddr_tmp; + int err; + + /* find the entry point of the looped node chain */ + while (blkaddr_fast != blkaddr) { + err = dev_read_block(node_blk_fast, blkaddr_fast); + if (err) + return err; + blkaddr_fast = next_blkaddr_of_node(node_blk_fast); + + err = dev_read_block(node_blk, blkaddr); + if (err) + return err; + blkaddr = next_blkaddr_of_node(node_blk); + } + blkaddr_entry = blkaddr; + + /* find the last node of the chain */ + do { + blkaddr_tmp = blkaddr; + err = dev_read_block(node_blk, blkaddr); + if (err) + return err; + blkaddr = next_blkaddr_of_node(node_blk); + } while (blkaddr != blkaddr_entry); + + /* fix the blkaddr of last node with NULL_ADDR. */ + node_blk->footer.next_blkaddr = NULL_ADDR; + err = dev_write_block(node_blk, blkaddr_tmp); + if (!err) + FIX_MSG("Fix looped node chain on blkaddr %u\n", + blkaddr_tmp); + + return err; +} + static int find_fsync_inode(struct f2fs_sb_info *sbi, struct list_head *head) { struct curseg_info *curseg; - struct f2fs_node *node_blk; - block_t blkaddr; - unsigned int loop_cnt = 0; - unsigned int free_blocks = MAIN_SEGS(sbi) * sbi->blocks_per_seg - - sbi->total_valid_block_count; + struct f2fs_node *node_blk, *node_blk_fast; + block_t blkaddr, blkaddr_fast; + bool is_detecting = true; int err = 0; + node_blk = calloc(F2FS_BLKSIZE, 1); + node_blk_fast = calloc(F2FS_BLKSIZE, 1); + ASSERT(node_blk && node_blk_fast); + +retry: /* get node pages in the current segment */ curseg = CURSEG_I(sbi, CURSEG_WARM_NODE); blkaddr = NEXT_FREE_BLKADDR(sbi, curseg); - - node_blk = calloc(F2FS_BLKSIZE, 1); - ASSERT(node_blk); + blkaddr_fast = blkaddr; while (1) { struct fsync_inode_entry *entry; @@ -3440,19 +3507,38 @@ static int find_fsync_inode(struct f2fs_sb_info *sbi, struct list_head *head) if (IS_INODE(node_blk) && is_dent_dnode(node_blk)) entry->last_dentry = blkaddr; next: - /* sanity check in order to detect looped node chain */ - if (++loop_cnt >= free_blocks || - blkaddr == next_blkaddr_of_node(node_blk)) { - MSG(0, "\tdetect looped node chain, blkaddr:%u, next:%u\n", - blkaddr, - next_blkaddr_of_node(node_blk)); - err = -1; - break; - } - blkaddr = next_blkaddr_of_node(node_blk); + + /* sanity check to detect looped node chain with Floyd's cycle + * detection algorithm + */ + if (is_detecting) { + err = find_node_blk_fast(sbi, &blkaddr_fast, node_blk_fast, + &is_detecting); + if (err) + break; + + if (blkaddr_fast == blkaddr) { + MSG(0, "\tdetect looped node chain, blkaddr:%u\n", + blkaddr); + + err = loop_node_chain_fix(sbi, + NEXT_FREE_BLKADDR(sbi, curseg), + node_blk_fast, blkaddr, node_blk); + if (!err) { + /* after fixing the looped node chain, + * retry agian. + */ + is_detecting = false; + destroy_fsync_dnodes(head); + goto retry; + } else + break; + } + } } + free(node_blk_fast); free(node_blk); return err; }
find_fsync_inode() detect the looped node chain by comparing the loop counter with free blocks. While it may take tens of seconds to quit when the free blocks are large enough. We can use Floyd's cycle detection algorithm to make the detection more efficient, and fix the issue by filling a NULL address in the last node of the chain. Below is the log we encounter on a 256GB UFS storage and it takes about 25 seconds to detect looped node chain. After changing the algorithm, it takes about 20ms to finish the same job. [ 10.822904] fsck.f2fs: Info: version timestamp cur: 17, prev: 430 [ 10.822949] fsck.f2fs: [update_superblock: 762] Info: Done to update superblock [ 10.822953] fsck.f2fs: Info: superblock features = 1499 : encrypt verity extra_attr project_quota quota_ino casefold [ 10.822956] fsck.f2fs: Info: superblock encrypt level = 0, salt = 00000000000000000000000000000000 [ 10.822960] fsck.f2fs: Info: total FS sectors = 59249811 (231444 MB) [ 35.852827] fsck.f2fs: detect looped node chain, blkaddr:1114802, next:1114803 [ 35.852842] fsck.f2fs: [f2fs_do_mount:3846] record_fsync_data failed [ 35.856106] fsck.f2fs: fsck.f2fs terminated by exit(255) Signed-off-by: Chunhai Guo <guochunhai@vivo.com> --- fsck/mount.c | 122 +++++++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 104 insertions(+), 18 deletions(-)