[PATCH 1/3] f2fs: avoid unneeded free nid building

[PATCH 1/3] f2fs: avoid unneeded free nid building

[Chao Yu]

This patch adds nm_i::valid_bitmap_count to count current valid free
nid bitmap, with it we can skip running into __build_free_nids more
early.

Signed-off-by: Chao Yu <yuchao0@huawei.com>
---
 fs/f2fs/f2fs.h |  1 +
 fs/f2fs/node.c | 14 ++++++++++++++
 2 files changed, 15 insertions(+)

diff --git a/fs/f2fs/f2fs.h b/fs/f2fs/f2fs.h
index f08e0feb38c1..fd9c8d1bffd5 100644
--- a/fs/f2fs/f2fs.h
+++ b/fs/f2fs/f2fs.h
@@ -730,6 +730,7 @@ struct f2fs_nm_info {
 	unsigned char *nat_block_bitmap;
 	unsigned short *free_nid_count;	/* free nid count of NAT block */
 	unsigned int available_free_nids;	/* available free nid count in bitmaps */
+	unsigned int valid_bitmap_count;	/* valid bitmap count */
 
 	/* for checkpoint */
 	char *nat_bitmap;		/* NAT bitmap pointer */
diff --git a/fs/f2fs/node.c b/fs/f2fs/node.c
index d2c9dcb0cbf8..4c758747980c 100644
--- a/fs/f2fs/node.c
+++ b/fs/f2fs/node.c
@@ -1882,6 +1882,7 @@ static void scan_nat_page(struct f2fs_sb_info *sbi, nid_t nid)
 	nat_blk = page_address(page);
 
 	__set_bit_le(nat_ofs, nm_i->nat_block_bitmap);
+	nm_i->valid_bitmap_count++;
 
 	i = nid % NAT_ENTRY_PER_BLOCK;
 
@@ -1969,6 +1970,16 @@ static void __build_free_nids(struct f2fs_sb_info *sbi, bool mount)
 
 void build_free_nids(struct f2fs_sb_info *sbi, bool mount)
 {
+	/*
+	 * do not try to load nid bitmap from NAT blocks if all nid
+	 * bitmaps are available now.
+	 */
+	if (NM_I(sbi)->valid_bitmap_count >= NM_I(sbi)->nat_blocks) {
+		if (!mount)
+			cond_resched();
+		return;
+	}
+
 	mutex_lock(&NM_I(sbi)->build_lock);
 	__build_free_nids(sbi, mount);
 	mutex_unlock(&NM_I(sbi)->build_lock);
@@ -2489,6 +2500,7 @@ static inline void load_free_nid_bitmap(struct f2fs_sb_info *sbi)
 			break;
 
 		__set_bit_le(i, nm_i->nat_block_bitmap);
+		nm_i->valid_bitmap_count++;
 
 		nid = i * NAT_ENTRY_PER_BLOCK;
 		last_nid = nid + NAT_ENTRY_PER_BLOCK;
@@ -2505,6 +2517,7 @@ static inline void load_free_nid_bitmap(struct f2fs_sb_info *sbi)
 			break;
 
 		__set_bit_le(i, nm_i->nat_block_bitmap);
+		nm_i->valid_bitmap_count++;
 	}
 
 	scan_curseg_cache(sbi, 0, nm_i->max_nid);
@@ -2529,6 +2542,7 @@ static int init_node_manager(struct f2fs_sb_info *sbi)
 	nm_i->available_nids = nm_i->max_nid - sbi->total_valid_node_count -
 				sbi->nquota_files - F2FS_RESERVED_NODE_NUM;
 	nm_i->available_free_nids = 0;
+	nm_i->valid_bitmap_count = 0;
 	nm_i->nat_cnt = 0;
 	nm_i->ram_thresh = DEF_RAM_THRESHOLD;
 	nm_i->ra_nid_pages = DEF_RA_NID_PAGES;
-- 
2.15.0.55.gc2ece9dc4de6

[PATCH 2/3] f2fs: refactor __build_free_nids

[Chao Yu]

Previously, in __build_free_nids we try to load bitmap from
next_scan_nid pointed NAT block, but actually, due to nat_bits
bitmap, current NAT blocks readed can be already ran out, so
it makes __build_free_nids low efficiency.

This patch refactors __build_free_nids a bit to search
nat_block_bitmap first to find out which NAT blocks have not been
loaded yet, and then do loading bitmaps.

Signed-off-by: Chao Yu <yuchao0@huawei.com>
---
 fs/f2fs/node.c | 54 ++++++++++++++++++++++++++++++++++--------------------
 1 file changed, 34 insertions(+), 20 deletions(-)

diff --git a/fs/f2fs/node.c b/fs/f2fs/node.c
index 4c758747980c..fb52622727ea 100644
--- a/fs/f2fs/node.c
+++ b/fs/f2fs/node.c
@@ -1865,13 +1865,13 @@ static void scan_curseg_cache(struct f2fs_sb_info *sbi, nid_t start_nid,
 	up_read(&curseg->journal_rwsem);
 }
 
-static void scan_nat_page(struct f2fs_sb_info *sbi, nid_t nid)
+static void scan_nat_page(struct f2fs_sb_info *sbi, unsigned int nat_ofs)
 {
 	struct f2fs_nm_info *nm_i = NM_I(sbi);
 	struct page *page;
 	struct f2fs_nat_block *nat_blk;
 	block_t blk_addr;
-	unsigned int nat_ofs = NAT_BLOCK_OFFSET(nid);
+	nid_t nid = nat_ofs * NAT_ENTRY_PER_BLOCK;
 	nid_t start_nid = nid;
 	int i;
 
@@ -1935,37 +1935,51 @@ static nid_t lookup_free_nid_bitmap(struct f2fs_sb_info *sbi)
 static void __build_free_nids(struct f2fs_sb_info *sbi, bool mount)
 {
 	struct f2fs_nm_info *nm_i = NM_I(sbi);
-	int i = 0;
-	nid_t nid = nm_i->next_scan_nid;
+	unsigned int pos, start, end, max_cnt = nm_i->nat_blocks;
+	bool sync_ra = true;
 
-	if (unlikely(nid >= nm_i->max_nid))
-		nid = 0;
+	if (unlikely(nm_i->next_scan_nid >= nm_i->max_nid))
+		nm_i->next_scan_nid = 0;
 
 	/* Enough entries */
 	if (!mount && nm_i->available_free_nids >= NAT_ENTRY_PER_BLOCK)
 		return;
 
-	/* readahead nat pages to be scanned */
-	ra_meta_pages(sbi, NAT_BLOCK_OFFSET(nid), FREE_NID_PAGES,
-							META_NAT, true);
+	start = NAT_BLOCK_OFFSET(nm_i->next_scan_nid);
 
-	down_read(&nm_i->nat_tree_lock);
+readahead:
+	/* search unloaded bitmap in range of [start, max] */
+	pos = find_next_zero_bit_le(nm_i->nat_block_bitmap, max_cnt, start);
+	if (pos >= max_cnt) {
+		if (!start)
+			return;
+		/* search unloaded bitmap in range of [0, start] */
+		pos = find_next_zero_bit_le(nm_i->nat_block_bitmap, start, 0);
+		if (pos >= start)
+			return;
+	}
 
-	do {
-		scan_nat_page(sbi, nid);
+	end = find_next_bit_le(nm_i->nat_block_bitmap, max_cnt, pos);
+	end = min(end, start + FREE_NID_PAGES);
 
-		nid += (NAT_ENTRY_PER_BLOCK - (nid % NAT_ENTRY_PER_BLOCK));
-		if (unlikely(nid >= nm_i->max_nid))
-			nid = 0;
-	} while (++i < FREE_NID_PAGES);
+	/* readahead nat pages to be scanned */
+	ra_meta_pages(sbi, pos, end - pos, META_NAT, sync_ra);
 
-	/* go to the next free nat pages to find free nids abundantly */
-	nm_i->next_scan_nid = nid;
+	if (!sync_ra)
+		return;
 
+	down_read(&nm_i->nat_tree_lock);
+	for (; pos < end; pos++)
+		scan_nat_page(sbi, pos);
 	up_read(&nm_i->nat_tree_lock);
 
-	ra_meta_pages(sbi, NAT_BLOCK_OFFSET(nm_i->next_scan_nid),
-					nm_i->ra_nid_pages, META_NAT, false);
+	/* go to the next free nat pages to find free nids abundantly */
+	nm_i->next_scan_nid = end * NAT_ENTRY_PER_BLOCK;
+
+	/* do async readahead for continual nid allocation */
+	start = NAT_BLOCK_OFFSET(nm_i->next_scan_nid);
+	sync_ra = false;
+	goto readahead;
 }
 
 void build_free_nids(struct f2fs_sb_info *sbi, bool mount)
-- 
2.15.0.55.gc2ece9dc4de6

[PATCH 3/3] f2fs: allocate full free nat block in prior

[Chao Yu]

In this patch, during alloc_nid, we start to allocate free nid from
nat block which contains the most free nids, it will make all dirty
nat entries locating in the same nat block, result in reducing nat
writes during checkpoint.

Signed-off-by: Chao Yu <yuchao0@huawei.com>
---
 fs/f2fs/f2fs.h |  2 ++
 fs/f2fs/node.c | 62 +++++++++++++++++++++++++++++++++++++++++++++++-----------
 2 files changed, 53 insertions(+), 11 deletions(-)

diff --git a/fs/f2fs/f2fs.h b/fs/f2fs/f2fs.h
index fd9c8d1bffd5..83d1f697388b 100644
--- a/fs/f2fs/f2fs.h
+++ b/fs/f2fs/f2fs.h
@@ -731,6 +731,8 @@ struct f2fs_nm_info {
 	unsigned short *free_nid_count;	/* free nid count of NAT block */
 	unsigned int available_free_nids;	/* available free nid count in bitmaps */
 	unsigned int valid_bitmap_count;	/* valid bitmap count */
+	unsigned int current_nat_block;	/* current nat block in allocation */
+	unsigned int next_free_nid_pos;	/* next free nid position */
 
 	/* for checkpoint */
 	char *nat_bitmap;		/* NAT bitmap pointer */
diff --git a/fs/f2fs/node.c b/fs/f2fs/node.c
index fb52622727ea..528e3af13070 100644
--- a/fs/f2fs/node.c
+++ b/fs/f2fs/node.c
@@ -1905,30 +1905,68 @@ static void scan_nat_page(struct f2fs_sb_info *sbi, unsigned int nat_ofs)
 	scan_curseg_cache(sbi, start_nid, start_nid + NAT_ENTRY_PER_BLOCK);
 }
 
-static nid_t lookup_free_nid_bitmap(struct f2fs_sb_info *sbi)
+static nid_t lookup_in_target_bitmap(struct f2fs_sb_info *sbi)
+{
+	struct f2fs_nm_info *nm_i = NM_I(sbi);
+	unsigned int nat_ofs = nm_i->current_nat_block;
+	unsigned int next_pos = nm_i->next_free_nid_pos;
+
+	if (test_bit_le(next_pos, nm_i->free_nid_bitmap[nat_ofs]))
+		goto got_it;
+
+	next_pos = find_next_bit_le(nm_i->free_nid_bitmap[nat_ofs],
+					NAT_ENTRY_PER_BLOCK, next_pos);
+	if (next_pos < NAT_ENTRY_PER_BLOCK)
+		goto got_it;
+
+	next_pos = find_next_bit_le(nm_i->free_nid_bitmap[nat_ofs],
+							next_pos, 0);
+	if (next_pos < NAT_ENTRY_PER_BLOCK)
+		goto got_it;
+
+	f2fs_bug_on(sbi, 1);
+	return 0;
+got_it:
+	nm_i->next_free_nid_pos = next_pos + 1;
+	return nat_ofs * NAT_ENTRY_PER_BLOCK + next_pos;
+}
+
+static void find_target_bitmap(struct f2fs_sb_info *sbi)
 {
 	struct f2fs_nm_info *nm_i = NM_I(sbi);
 	unsigned int i;
-	nid_t nid = 0;
+	unsigned int max_count = 0;
 
 	for (i = 0; i < nm_i->nat_blocks; i++) {
-		unsigned int idx = 0;
-
 		if (!test_bit_le(i, nm_i->nat_block_bitmap))
 			continue;
 		if (!nm_i->free_nid_count[i])
 			continue;
+		if (nm_i->free_nid_count[i] == NAT_ENTRY_PER_BLOCK) {
+			nm_i->current_nat_block = i;
+			break;
+		}
+		if (nm_i->free_nid_count[i] > max_count) {
+			max_count = nm_i->free_nid_count[i];
+			nm_i->current_nat_block = i;
+		}
+	}
 
-		idx = find_next_bit_le(nm_i->free_nid_bitmap[i],
-					NAT_ENTRY_PER_BLOCK, idx);
-		if (idx >= NAT_ENTRY_PER_BLOCK)
-			continue;
+	nm_i->next_free_nid_pos = 0;
+}
 
-		nid = i * NAT_ENTRY_PER_BLOCK + idx;
-		break;
-	}
+static nid_t lookup_free_nid_bitmap(struct f2fs_sb_info *sbi)
+{
+	struct f2fs_nm_info *nm_i = NM_I(sbi);
+	unsigned int nat_ofs = nm_i->current_nat_block;
+	nid_t nid = 0;
+
+	if (nat_ofs == nm_i->nat_blocks || !nm_i->free_nid_count[nat_ofs])
+		find_target_bitmap(sbi);
 
+	nid = lookup_in_target_bitmap(sbi);
 	f2fs_bug_on(sbi, !nid);
+
 	return nid;
 }
 
@@ -2557,6 +2595,8 @@ static int init_node_manager(struct f2fs_sb_info *sbi)
 				sbi->nquota_files - F2FS_RESERVED_NODE_NUM;
 	nm_i->available_free_nids = 0;
 	nm_i->valid_bitmap_count = 0;
+	nm_i->current_nat_block = nm_i->nat_blocks;
+	nm_i->next_free_nid_pos = 0;
 	nm_i->nat_cnt = 0;
 	nm_i->ram_thresh = DEF_RAM_THRESHOLD;
 	nm_i->ra_nid_pages = DEF_RA_NID_PAGES;
-- 
2.15.0.55.gc2ece9dc4de6