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

[Chao Yu <chao@kernel.org>]

On 2023/5/18 17:10, Chao Yu wrote:
> On 2023/5/18 12:11, 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 extr\x02a_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 | 128 +++++++++++++++++++++++++++++++++++++++++++--------
>>   1 file changed, 110 insertions(+), 18 deletions(-)
>>
>> diff --git a/fsck/mount.c b/fsck/mount.c
>> index df0314d57caf..755b659f0c27 100644
>> --- a/fsck/mount.c
>> +++ b/fsck/mount.c
>> @@ -3394,22 +3394,91 @@ 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->footer.nid == node_blk->footer.ino)
> 
> if (le32_to_cpu(node_blk->footer.nid) == le32_to_cpu(node_blk->footer.ino))

Oh, we can use IS_INODE() here?

Thanks,

> 
> Otherwise, it looks good to me.
> 
> Thanks,
> 
>> +        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);
>> +
>> +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 +3509,42 @@ 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)
>> +                continue;
>> +
>> +            ASSERT_MSG("\tdetect looped node chain, blkaddr:%u\n",
>> +                    blkaddr);
>> +
>> +            if (!c.fix_on) {
>> +                err = -1;
>> +                break;
>> +            }
>> +
>> +            err = loop_node_chain_fix(sbi,
>> +                    NEXT_FREE_BLKADDR(sbi, curseg),
>> +                    node_blk_fast, blkaddr, node_blk);
>> +            if (err)
>> +                break;
>> +
>> +            /* After fixing the looped node chain, retry agian. */
>> +            is_detecting = false;
>> +            destroy_fsync_dnodes(head);
>> +            goto retry;
>> +        }
>>       }
>> +    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


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