* [f2fs-dev] [PATCH] fsck.f2fs: Detect looped node chain more efficiently.
@ 2023-05-04 3:30 Chunhai Guo via Linux-f2fs-devel
2023-05-05 12:07 ` Chao Yu
0 siblings, 1 reply; 2+ messages in thread
From: Chunhai Guo via Linux-f2fs-devel @ 2023-05-04 3:30 UTC (permalink / raw)
To: jaegeuk; +Cc: Chunhai Guo, linux-f2fs-devel, frank.li
Now we 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 it more efficient.
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 | 57 ++++++++++++++++++++++++++++++++++++++++++----------
1 file changed, 46 insertions(+), 11 deletions(-)
diff --git a/fsck/mount.c b/fsck/mount.c
index df0314d..2e919d9 100644
--- a/fsck/mount.c
+++ b/fsck/mount.c
@@ -3394,22 +3394,48 @@ 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 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;
/* get node pages in the current segment */
curseg = CURSEG_I(sbi, CURSEG_WARM_NODE);
blkaddr = NEXT_FREE_BLKADDR(sbi, curseg);
+ blkaddr_fast = blkaddr;
node_blk = calloc(F2FS_BLKSIZE, 1);
- ASSERT(node_blk);
+ node_blk_fast = calloc(F2FS_BLKSIZE, 1);
+ ASSERT(node_blk && node_blk_fast);
while (1) {
struct fsync_inode_entry *entry;
@@ -3424,6 +3450,16 @@ static int find_fsync_inode(struct f2fs_sb_info *sbi, struct list_head *head)
if (!is_recoverable_dnode(sbi, node_blk))
break;
+ /* Here we use Floyd's cycle detection algorithm to detect
+ * looped node chain more effeciently.
+ */
+ if (is_detecting) {
+ err = find_node_blk_fast(sbi, &blkaddr_fast,
+ node_blk_fast, &is_detecting);
+ if (err)
+ break;
+ }
+
if (!is_fsync_dnode(node_blk))
goto next;
@@ -3441,11 +3477,9 @@ static int find_fsync_inode(struct f2fs_sb_info *sbi, struct list_head *head)
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));
+ if (is_detecting && (blkaddr_fast == blkaddr)) {
+ MSG(0, "\tdetect looped node chain, blkaddr:%u\n",
+ blkaddr);
err = -1;
break;
}
@@ -3453,6 +3487,7 @@ next:
blkaddr = next_blkaddr_of_node(node_blk);
}
+ free(node_blk_fast);
free(node_blk);
return err;
}
--
2.25.1
_______________________________________________
Linux-f2fs-devel mailing list
Linux-f2fs-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel
^ permalink raw reply related [flat|nested] 2+ messages in thread
* Re: [f2fs-dev] [PATCH] fsck.f2fs: Detect looped node chain more efficiently.
2023-05-04 3:30 [f2fs-dev] [PATCH] fsck.f2fs: Detect looped node chain more efficiently Chunhai Guo via Linux-f2fs-devel
@ 2023-05-05 12:07 ` Chao Yu
0 siblings, 0 replies; 2+ messages in thread
From: Chao Yu @ 2023-05-05 12:07 UTC (permalink / raw)
To: Chunhai Guo, jaegeuk; +Cc: linux-f2fs-devel, frank.li
On 2023/5/4 11:30, Chunhai Guo wrote:
> Now we 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 it more efficient.
>
> 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>
The patch is clean, but as it is fsck, so any way to fix this issue if we
want to keep fsynced data rather than dropping them w/ norecovery during
mount.
Thanks,
> ---
> fsck/mount.c | 57 ++++++++++++++++++++++++++++++++++++++++++----------
> 1 file changed, 46 insertions(+), 11 deletions(-)
>
> diff --git a/fsck/mount.c b/fsck/mount.c
> index df0314d..2e919d9 100644
> --- a/fsck/mount.c
> +++ b/fsck/mount.c
> @@ -3394,22 +3394,48 @@ 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 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;
>
> /* get node pages in the current segment */
> curseg = CURSEG_I(sbi, CURSEG_WARM_NODE);
> blkaddr = NEXT_FREE_BLKADDR(sbi, curseg);
> + blkaddr_fast = blkaddr;
>
> node_blk = calloc(F2FS_BLKSIZE, 1);
> - ASSERT(node_blk);
> + node_blk_fast = calloc(F2FS_BLKSIZE, 1);
> + ASSERT(node_blk && node_blk_fast);
>
> while (1) {
> struct fsync_inode_entry *entry;
> @@ -3424,6 +3450,16 @@ static int find_fsync_inode(struct f2fs_sb_info *sbi, struct list_head *head)
> if (!is_recoverable_dnode(sbi, node_blk))
> break;
>
> + /* Here we use Floyd's cycle detection algorithm to detect
> + * looped node chain more effeciently.
> + */
> + if (is_detecting) {
> + err = find_node_blk_fast(sbi, &blkaddr_fast,
> + node_blk_fast, &is_detecting);
> + if (err)
> + break;
> + }
> +
> if (!is_fsync_dnode(node_blk))
> goto next;
>
> @@ -3441,11 +3477,9 @@ static int find_fsync_inode(struct f2fs_sb_info *sbi, struct list_head *head)
> 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));
> + if (is_detecting && (blkaddr_fast == blkaddr)) {
> + MSG(0, "\tdetect looped node chain, blkaddr:%u\n",
> + blkaddr);
> err = -1;
> break;
> }
> @@ -3453,6 +3487,7 @@ next:
> blkaddr = next_blkaddr_of_node(node_blk);
> }
>
> + 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
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2023-05-05 12:08 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-05-04 3:30 [f2fs-dev] [PATCH] fsck.f2fs: Detect looped node chain more efficiently Chunhai Guo via Linux-f2fs-devel
2023-05-05 12:07 ` Chao Yu
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).