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, and fix the issue by
filling a NULL address in the last node of the chain.
Signed-off-by: Chunhai Guo <guochun...@vivo.com>
---
fs/f2fs/recovery.c | 135 ++++++++++++++++++++++++++++++++++++++-------
1 file changed, 116 insertions(+), 19 deletions(-)
diff --git a/fs/f2fs/recovery.c b/fs/f2fs/recovery.c
index 58c1a0096f7d..1b94078947cb 100644
--- a/fs/f2fs/recovery.c
+++ b/fs/f2fs/recovery.c
@@ -360,21 +360,98 @@ 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 loop_node_chain_fix(struct f2fs_sb_info *sbi, block_t blkaddr_fast,
+ block_t blkaddr)
+{
+ struct page *page = NULL;
+ block_t blkaddr_entry, blkaddr_tmp;
+ struct f2fs_node *rn;
+
+ /* find the entry point of the looped node chain */
+ while (blkaddr_fast != blkaddr) {
+ page = f2fs_get_tmp_page(sbi, blkaddr_fast);
+ if (IS_ERR(page))
+ return PTR_ERR(page);
+ blkaddr_fast = next_blkaddr_of_node(page);
+ f2fs_put_page(page, 1);
+
+ page = f2fs_get_tmp_page(sbi, blkaddr);
+ if (IS_ERR(page))
+ return PTR_ERR(page);
+ blkaddr = next_blkaddr_of_node(page);
+ f2fs_put_page(page, 1);
+ }
+ blkaddr_entry = blkaddr;
+
+ /* find the last node of the chain */
+ do {
+ blkaddr_tmp = blkaddr;
+ page = f2fs_get_tmp_page(sbi, blkaddr);
+ if (IS_ERR(page))
+ return PTR_ERR(page);
+ blkaddr = next_blkaddr_of_node(page);
+ if (blkaddr != blkaddr_entry)
+ f2fs_put_page(page, 1);
+ } while (blkaddr != blkaddr_entry);
+
+ /* fix the blkaddr of last node with NULL_ADDR. */
+ rn = F2FS_NODE(page);
+ rn->footer.next_blkaddr = NULL_ADDR;
+ f2fs_inode_chksum_set(sbi, page);
+ set_page_dirty(page);
+ f2fs_put_page(page, 1);
+ f2fs_notice(sbi, "Fix looped node chain on blkaddr %u\n", blkaddr_tmp);
+ 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 +508,45 @@ 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);
+ /* check next segment */
+ blkaddr = next_blkaddr_of_node(page);
+ f2fs_put_page(page, 1);
+
+ /* 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)
+ continue;
+
+ f2fs_notice(sbi, "%s: detect looped node chain, blkaddr:%u",
+ __func__, blkaddr);
+
+ if (check_only) {
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);
+ err = loop_node_chain_fix(sbi, blkaddr,
+ NEXT_FREE_BLKADDR(sbi, curseg));
+ if (err)
+ break;
- f2fs_ra_meta_pages_cond(sbi, blkaddr, ra_blocks);
+ /* 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;
}
return err;
}
--
2.25.1
