* [f2fs-dev] [PATCH v2] f2fs: Detect looped node chain efficiently
@ 2023-05-26 9:08 Chunhai Guo via Linux-f2fs-devel
2023-05-27 0:43 ` Chao Yu
0 siblings, 1 reply; 2+ messages in thread
From: Chunhai Guo via Linux-f2fs-devel @ 2023-05-26 9:08 UTC (permalink / raw)
To: chao; +Cc: jaegeuk, linux-f2fs-devel, Chunhai Guo, frank.li
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;
}
+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);
+ 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;
}
--
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 v2] f2fs: Detect looped node chain efficiently
2023-05-26 9:08 [f2fs-dev] [PATCH v2] f2fs: Detect looped node chain efficiently Chunhai Guo via Linux-f2fs-devel
@ 2023-05-27 0:43 ` Chao Yu
0 siblings, 0 replies; 2+ messages in thread
From: Chao Yu @ 2023-05-27 0:43 UTC (permalink / raw)
To: Chunhai Guo; +Cc: jaegeuk, linux-f2fs-devel, frank.li
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
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2023-05-27 0:43 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2023-05-26 9:08 [f2fs-dev] [PATCH v2] f2fs: Detect looped node chain efficiently Chunhai Guo via Linux-f2fs-devel
2023-05-27 0:43 ` 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).