Re: [f2fs-dev] [PATCH] f2fs: Detect and fix looped node chain efficiently

[Chao Yu <chao@kernel.org>]

On 2023/5/24 16:33, Chunhai Guo wrote:
> find_fsync_dnodes() 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.
> 
> Signed-off-by: Chunhai Guo <guochunhai@vivo.com>
> ---
>   fs/f2fs/recovery.c | 135 ++++++++++++++++++++++++++++++++++++++-------
>   1 file changed, 116 insertions(+), 19 deletions(-)
> 
> diff --git a/fs/f2fs/recovery.c b/fs/f2fs/recovery.c
> index 58c1a0096f7d..1b94078947cb 100644
> --- a/fs/f2fs/recovery.c
> +++ b/fs/f2fs/recovery.c
> @@ -360,21 +360,98 @@ static unsigned int adjust_por_ra_blocks(struct f2fs_sb_info *sbi,
>   	return ra_blocks;
>   }
>   
> +static int find_node_blk_fast(struct f2fs_sb_info *sbi, block_t *blkaddr_fast,
> +		bool *is_detecting)
> +{
> +	unsigned int ra_blocks = RECOVERY_MAX_RA_BLOCKS;
> +	struct page *page = NULL;
> +	int i;
> +
> +	for (i = 0; i < 2; i++) {
> +		if (!f2fs_is_valid_blkaddr(sbi, *blkaddr_fast, META_POR)) {
> +			*is_detecting = false;
> +			return 0;
> +		}
> +
> +		page = f2fs_get_tmp_page(sbi, *blkaddr_fast);
> +		if (IS_ERR(page))
> +			return PTR_ERR(page);
> +
> +		if (!is_recoverable_dnode(page)) {
> +			f2fs_put_page(page, 1);
> +			*is_detecting = false;
> +			return 0;
> +		}
> +
> +		ra_blocks = adjust_por_ra_blocks(sbi, ra_blocks, *blkaddr_fast,
> +						next_blkaddr_of_node(page));
> +
> +		*blkaddr_fast = next_blkaddr_of_node(page);
> +		f2fs_put_page(page, 1);
> +
> +		f2fs_ra_meta_pages_cond(sbi, *blkaddr_fast, ra_blocks);
> +	}
> +
> +	return 0;
> +}
> +
> +static int loop_node_chain_fix(struct f2fs_sb_info *sbi, block_t blkaddr_fast,
> +		block_t blkaddr)
> +{
> +	struct page *page = NULL;
> +	block_t blkaddr_entry, blkaddr_tmp;
> +	struct f2fs_node *rn;
> +
> +	/* find the entry point of the looped node chain */
> +	while (blkaddr_fast != blkaddr) {
> +		page = f2fs_get_tmp_page(sbi, blkaddr_fast);
> +		if (IS_ERR(page))
> +			return PTR_ERR(page);
> +		blkaddr_fast = next_blkaddr_of_node(page);
> +		f2fs_put_page(page, 1);
> +
> +		page = f2fs_get_tmp_page(sbi, blkaddr);
> +		if (IS_ERR(page))
> +			return PTR_ERR(page);
> +		blkaddr = next_blkaddr_of_node(page);
> +		f2fs_put_page(page, 1);
> +	}
> +	blkaddr_entry = blkaddr;
> +
> +	/* find the last node of the chain */
> +	do {
> +		blkaddr_tmp = blkaddr;
> +		page = f2fs_get_tmp_page(sbi, blkaddr);
> +		if (IS_ERR(page))
> +			return PTR_ERR(page);
> +		blkaddr = next_blkaddr_of_node(page);
> +		if (blkaddr != blkaddr_entry)
> +			f2fs_put_page(page, 1);
> +	} while (blkaddr != blkaddr_entry);
> +
> +	/* fix the blkaddr of last node with NULL_ADDR. */
> +	rn = F2FS_NODE(page);
> +	rn->footer.next_blkaddr = NULL_ADDR;
> +	f2fs_inode_chksum_set(sbi, page);
> +	set_page_dirty(page);
> +	f2fs_put_page(page, 1);
> +	f2fs_notice(sbi, "Fix looped node chain on blkaddr %u\n", blkaddr_tmp);
> +	return 0;
> +}
> +
>   static int find_fsync_dnodes(struct f2fs_sb_info *sbi, struct list_head *head,
>   				bool check_only)
>   {
>   	struct curseg_info *curseg;
>   	struct page *page = NULL;
> -	block_t blkaddr;
> -	unsigned int loop_cnt = 0;
> -	unsigned int ra_blocks = RECOVERY_MAX_RA_BLOCKS;
> -	unsigned int free_blocks = MAIN_SEGS(sbi) * sbi->blocks_per_seg -
> -						valid_user_blocks(sbi);
> +	block_t blkaddr, blkaddr_fast;
> +	bool is_detecting = true;
>   	int err = 0;
>   
>   	/* get node pages in the current segment */
>   	curseg = CURSEG_I(sbi, CURSEG_WARM_NODE);
>   	blkaddr = NEXT_FREE_BLKADDR(sbi, curseg);
> +	blkaddr_fast = blkaddr;
>   
>   	while (1) {
>   		struct fsync_inode_entry *entry;
> @@ -431,25 +508,45 @@ 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_notice(sbi, "%s: detect looped node chain, blkaddr:%u, next:%u",
> -				    __func__, blkaddr,
> -				    next_blkaddr_of_node(page));
> -			f2fs_put_page(page, 1);
> +		/* check next segment */
> +		blkaddr = next_blkaddr_of_node(page);
> +		f2fs_put_page(page, 1);
> +
> +		/* Below we will detect looped node chain with Floyd's cycle
> +		 * detection algorithm.
> +		 */
> +		if (!is_detecting)
> +			continue;
> +
> +		err = find_node_blk_fast(sbi, &blkaddr_fast, &is_detecting);
> +		if (err)
> +			break;
> +
> +		if (!is_detecting)
> +			continue;
> +
> +		if (blkaddr_fast != blkaddr)
> +			continue;
> +
> +		f2fs_notice(sbi, "%s: detect looped node chain, blkaddr:%u",
> +				__func__, blkaddr);
> +
> +		if (check_only) {
>   			err = -EINVAL;
>   			break;
>   		}
>   
> -		ra_blocks = adjust_por_ra_blocks(sbi, ra_blocks, blkaddr,
> -						next_blkaddr_of_node(page));

What about just bailing out if there is a loop in chain and do repair in fsck?

Thanks,

> -
> -		/* check next segment */
> -		blkaddr = next_blkaddr_of_node(page);
> -		f2fs_put_page(page, 1);
> +		err = loop_node_chain_fix(sbi, blkaddr,
> +				NEXT_FREE_BLKADDR(sbi, curseg));
> +		if (err)
> +			break;
>   
> -		f2fs_ra_meta_pages_cond(sbi, blkaddr, ra_blocks);
> +		/* Since we call get_fsync_inode() to ensure there are
> +		 * no duplicate inodes in the inode_list even if there
> +		 * are duplicate blkaddr, we can continue running
> +		 * after fixing the looped node chain.
> +		 */
> +		is_detecting = false;
>   	}
>   	return err;
>   }


_______________________________________________
Linux-f2fs-devel mailing list
Linux-f2fs-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel