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

[Chao Yu <chao@kernel.org>]

On 2023/6/14 17:27, Chunhai Guo wrote:
> Hi Jaegeuk,
> 
> Could you please help to confirm if this patch has been merged? I cannot
> see the patch in the dev-test or dev branch.
> 
> Thanks.
> 
> On 2023/5/24 10:42, 郭纯海 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>
>> ---
>> v7 -> v8 : Reformat the code to reduce indention.
>> v6 -> v7 : Correct logic error to handle is_detecting return by
>> 	find_node_blk_fast().
>> v5 -> v6 : Simplify the code by removing unnecessary retry logic.
>> v4 -> v5 : Use IS_INODE() to make the code more clear.
>> v3 -> v4 : Set c.bug_on with ASSERT_MSG() when issue is detected and fix
>> 	it only if c.fix_on is 1.
>> v2 -> v3 : Write inode with write_inode() to avoid chksum being broken.
>> v1 -> v2 : Fix looped node chain directly after it is detected.
>> ---
>>    fsck/mount.c | 127 +++++++++++++++++++++++++++++++++++++++++++++------
>>    1 file changed, 112 insertions(+), 15 deletions(-)
>>
>> diff --git a/fsck/mount.c b/fsck/mount.c
>> index 4c7488840c7c..9d6a222a055c 100644
>> --- a/fsck/mount.c
>> +++ b/fsck/mount.c
>> @@ -3518,22 +3518,90 @@ 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 (IS_INODE(node_blk))
>> +		err = write_inode(node_blk, blkaddr_tmp);
>> +	else
>> +		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);
>> +
>>    	/* 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;
>> @@ -3564,19 +3632,48 @@ 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));
>> +		blkaddr = next_blkaddr_of_node(node_blk);
>> +
>> +		/* 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,
>> +				node_blk_fast, &is_detecting);
>> +		if (err)
>> +			break;
>> +
>> +		if (!is_detecting)
>> +			continue;
>> +
>> +		if (blkaddr_fast != blkaddr)
>> +			continue;
>> +
>> +		ASSERT_MSG("\tdetect looped node chain, blkaddr:%u\n",
>> +				blkaddr);
>> +
>> +		if (!c.fix_on) {
>>    			err = -1;
>>    			break;
>>    		}
>>    
>> -		blkaddr = next_blkaddr_of_node(node_blk);
>> +		err = loop_node_chain_fix(sbi,
>> +				NEXT_FREE_BLKADDR(sbi, curseg),
>> +				node_blk_fast, blkaddr, node_blk);
>> +		if (err)
>> +			break;
>> +
>> +		/* 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;

Hi Chunhai,

What about cleaning up above logic like we did in kernel side?

Thanks,

>>    	}
>>    
>> +	free(node_blk_fast);
>>    	free(node_blk);
>>    	return err;
>>    }


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