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

[Chao Yu <chao@kernel.org>]

On 2023/5/26 17:08, 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.
> 
> Signed-off-by: Chunhai Guo <guochunhai@vivo.com>
> ---
> v1 -> v2 : Bail out if a looped is found in a chain and do repair in fsck.
> ---
>   fs/f2fs/recovery.c | 78 ++++++++++++++++++++++++++++++++++------------
>   1 file changed, 58 insertions(+), 20 deletions(-)
> 
> diff --git a/fs/f2fs/recovery.c b/fs/f2fs/recovery.c
> index 58c1a0096f7d..c1dceda54a4f 100644
> --- a/fs/f2fs/recovery.c
> +++ b/fs/f2fs/recovery.c
> @@ -360,21 +360,54 @@ static unsigned int adjust_por_ra_blocks(struct f2fs_sb_info *sbi,
>   	return ra_blocks;
>   }
>   

What about this?

return value:
- 0: continue the loop
- < 0: break and return

static int sanity_check_node_chain(struct f2fs_sb_info *sbi, block_t blkaddr,
				block_t *blkaddr_fast, bool *is_detecting)
{
	if (!is_detecting)
		return 0;

	for (i = 0; i < 2; i++) {
	...
	}

	if (*blkaddr_fast == blkaddr) {
		f2fs_notice();
		return -EINVAL;
	}

	return 0;
}

> +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 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 +464,30 @@ 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);
> -			err = -EINVAL;
> -			break;
> -		}
> -
> -		ra_blocks = adjust_por_ra_blocks(sbi, ra_blocks, blkaddr,
> -						next_blkaddr_of_node(page));
> -
>   		/* check next segment */
>   		blkaddr = next_blkaddr_of_node(page);
>   		f2fs_put_page(page, 1);
>   
> -		f2fs_ra_meta_pages_cond(sbi, blkaddr, ra_blocks);
> +		/* 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);

		/* ... */
		err = sanity_check_node_chain();
		if (err)
			break;

Thanks,

> +		if (err)
> +			break;
> +
> +		if (!is_detecting)
> +			continue;
> +
> +		if (blkaddr_fast == blkaddr) {
> +			f2fs_notice(sbi, "%s: Detect looped node chain on "
> +					"blkaddr:%u. Run fsck to fix it.",
> +					__func__, blkaddr);
> +			err = -EINVAL;
> +			break;
> +		}
>   	}
>   	return err;
>   }


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