[PATCH v2] f2fs: combine nat_bits and free_nid_bitmap cache

[PATCH v2] f2fs: combine nat_bits and free_nid_bitmap cache

[Chao Yu]

Both nat_bits cache and free_nid_bitmap cache provide same functionality
as a intermediate cache between free nid cache and disk, but with
different granularity of indicating free nid range, and different
persistence policy. nat_bits cache provides better persistence ability,
and free_nid_bitmap provides better granularity.

In this patch we combine advantage of both caches, so finally policy of
the intermediate cache would be:
- init: load free nid status from nat_bits into free_nid_bitmap
- lookup: scan free_nid_bitmap before load NAT blocks
- update: update free_nid_bitmap in real-time
- persistence: udpate and persist nat_bits in checkpoint

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

diff --git a/fs/f2fs/node.c b/fs/f2fs/node.c
index 1a759d45b7e4..625b46bc55ad 100644
--- a/fs/f2fs/node.c
+++ b/fs/f2fs/node.c
@@ -338,9 +338,6 @@ static void set_node_addr(struct f2fs_sb_info *sbi, struct node_info *ni,
 		set_nat_flag(e, IS_CHECKPOINTED, false);
 	__set_nat_cache_dirty(nm_i, e);
 
-	if (enabled_nat_bits(sbi, NULL) && new_blkaddr == NEW_ADDR)
-		clear_bit_le(NAT_BLOCK_OFFSET(ni->nid), nm_i->empty_nat_bits);
-
 	/* update fsync_mark if its inode nat entry is still alive */
 	if (ni->nid != ni->ino)
 		e = __lookup_nat_cache(nm_i, ni->ino);
@@ -1920,58 +1917,6 @@ static void scan_free_nid_bits(struct f2fs_sb_info *sbi)
 	up_read(&nm_i->nat_tree_lock);
 }
 
-static int scan_nat_bits(struct f2fs_sb_info *sbi)
-{
-	struct f2fs_nm_info *nm_i = NM_I(sbi);
-	struct page *page;
-	unsigned int i = 0;
-	nid_t nid;
-
-	if (!enabled_nat_bits(sbi, NULL))
-		return -EAGAIN;
-
-	down_read(&nm_i->nat_tree_lock);
-check_empty:
-	i = find_next_bit_le(nm_i->empty_nat_bits, nm_i->nat_blocks, i);
-	if (i >= nm_i->nat_blocks) {
-		i = 0;
-		goto check_partial;
-	}
-
-	for (nid = i * NAT_ENTRY_PER_BLOCK; nid < (i + 1) * NAT_ENTRY_PER_BLOCK;
-									nid++) {
-		if (unlikely(nid >= nm_i->max_nid))
-			break;
-		add_free_nid(sbi, nid, true);
-	}
-
-	if (nm_i->nid_cnt[FREE_NID_LIST] >= MAX_FREE_NIDS)
-		goto out;
-	i++;
-	goto check_empty;
-
-check_partial:
-	i = find_next_zero_bit_le(nm_i->full_nat_bits, nm_i->nat_blocks, i);
-	if (i >= nm_i->nat_blocks) {
-		disable_nat_bits(sbi, true);
-		up_read(&nm_i->nat_tree_lock);
-		return -EINVAL;
-	}
-
-	nid = i * NAT_ENTRY_PER_BLOCK;
-	page = get_current_nat_page(sbi, nid);
-	scan_nat_page(sbi, page, nid);
-	f2fs_put_page(page, 1);
-
-	if (nm_i->nid_cnt[FREE_NID_LIST] < MAX_FREE_NIDS) {
-		i++;
-		goto check_partial;
-	}
-out:
-	up_read(&nm_i->nat_tree_lock);
-	return 0;
-}
-
 static void __build_free_nids(struct f2fs_sb_info *sbi, bool sync, bool mount)
 {
 	struct f2fs_nm_info *nm_i = NM_I(sbi);
@@ -1993,21 +1938,6 @@ static void __build_free_nids(struct f2fs_sb_info *sbi, bool sync, bool mount)
 
 		if (nm_i->nid_cnt[FREE_NID_LIST])
 			return;
-
-		/* try to find free nids with nat_bits */
-		if (!scan_nat_bits(sbi) && nm_i->nid_cnt[FREE_NID_LIST])
-			return;
-	}
-
-	/* find next valid candidate */
-	if (enabled_nat_bits(sbi, NULL)) {
-		int idx = find_next_zero_bit_le(nm_i->full_nat_bits,
-					nm_i->nat_blocks, 0);
-
-		if (idx >= nm_i->nat_blocks)
-			set_sbi_flag(sbi, SBI_NEED_FSCK);
-		else
-			nid = idx * NAT_ENTRY_PER_BLOCK;
 	}
 
 	/* readahead nat pages to be scanned */
@@ -2590,6 +2520,38 @@ static int __get_nat_bitmaps(struct f2fs_sb_info *sbi)
 	return 0;
 }
 
+inline void load_free_nid_bitmap(struct f2fs_sb_info *sbi)
+{
+	struct f2fs_nm_info *nm_i = NM_I(sbi);
+	unsigned int i = 0;
+	nid_t nid, last_nid;
+
+	if (!enabled_nat_bits(sbi, NULL))
+		return;
+
+	for (i = 0; i < nm_i->nat_blocks; i++) {
+		i = find_next_bit_le(nm_i->empty_nat_bits, nm_i->nat_blocks, i);
+		if (i >= nm_i->nat_blocks)
+			break;
+
+		__set_bit_le(i, nm_i->nat_block_bitmap);
+
+		nid = i * NAT_ENTRY_PER_BLOCK;
+		last_nid = (i + 1) * NAT_ENTRY_PER_BLOCK;
+
+		for (; nid < last_nid; nid++)
+			update_free_nid_bitmap(sbi, nid, true, true);
+	}
+
+	for (i = 0; i < nm_i->nat_blocks; i++) {
+		i = find_next_bit_le(nm_i->full_nat_bits, nm_i->nat_blocks, i);
+		if (i >= nm_i->nat_blocks)
+			break;
+
+		__set_bit_le(i, nm_i->nat_block_bitmap);
+	}
+}
+
 static int init_node_manager(struct f2fs_sb_info *sbi)
 {
 	struct f2fs_super_block *sb_raw = F2FS_RAW_SUPER(sbi);
@@ -2691,6 +2653,9 @@ int build_node_manager(struct f2fs_sb_info *sbi)
 	if (err)
 		return err;
 
+	/* load free nid status from nat_bits table */
+	load_free_nid_bitmap(sbi);
+
 	build_free_nids(sbi, true, true);
 	return 0;
 }
-- 
2.8.2.295.g3f1c1d0

Re: [PATCH v2] f2fs: combine nat_bits and free_nid_bitmap cache

[Jaegeuk Kim]

Hi Chao,

There were two reasons for slow down; one is set_bit_le and the other was 
spin_lock calls.

I think it would'b good to merge this patch in yours as well.
Let me know. I'm ready to integrate together and test them.

Signed-off-by: Jaegeuk Kim <jaegeuk@kernel.org>
---
 fs/f2fs/node.c | 22 +++++++++++++---------
 1 file changed, 13 insertions(+), 9 deletions(-)

diff --git a/fs/f2fs/node.c b/fs/f2fs/node.c
index 3377a512e299..0a1ea59c9d31 100644
--- a/fs/f2fs/node.c
+++ b/fs/f2fs/node.c
@@ -1815,7 +1815,7 @@ static void remove_free_nid(struct f2fs_sb_info *sbi, nid_t nid)
 }
 
 void update_free_nid_bitmap(struct f2fs_sb_info *sbi, nid_t nid,
-							bool set, bool build)
+			bool set, bool build, bool locked)
 {
 	struct f2fs_nm_info *nm_i = NM_I(sbi);
 	unsigned int nat_ofs = NAT_BLOCK_OFFSET(nid);
@@ -1829,12 +1829,14 @@ void update_free_nid_bitmap(struct f2fs_sb_info *sbi, nid_t nid,
 	else
 		__clear_bit_le(nid_ofs, nm_i->free_nid_bitmap[nat_ofs]);
 
-	spin_lock(&nm_i->free_nid_lock);
+	if (!locked)
+		spin_lock(&nm_i->free_nid_lock);
 	if (set)
 		nm_i->free_nid_count[nat_ofs]++;
 	else if (!build)
 		nm_i->free_nid_count[nat_ofs]--;
-	spin_unlock(&nm_i->free_nid_lock);
+	if (!locked)
+		spin_unlock(&nm_i->free_nid_lock);
 }
 
 static void scan_nat_page(struct f2fs_sb_info *sbi,
@@ -1863,7 +1865,7 @@ static void scan_nat_page(struct f2fs_sb_info *sbi,
 		f2fs_bug_on(sbi, blk_addr == NEW_ADDR);
 		if (blk_addr == NULL_ADDR)
 			freed = add_free_nid(sbi, start_nid, true);
-		update_free_nid_bitmap(sbi, start_nid, freed, true);
+		update_free_nid_bitmap(sbi, start_nid, freed, true, false);
 	}
 }
 
@@ -2018,7 +2020,7 @@ bool alloc_nid(struct f2fs_sb_info *sbi, nid_t *nid)
 		__insert_nid_to_list(sbi, i, ALLOC_NID_LIST, false);
 		nm_i->available_nids--;
 
-		update_free_nid_bitmap(sbi, *nid, false, false);
+		update_free_nid_bitmap(sbi, *nid, false, false, false);
 
 		spin_unlock(&nm_i->nid_list_lock);
 		return true;
@@ -2074,7 +2076,7 @@ void alloc_nid_failed(struct f2fs_sb_info *sbi, nid_t nid)
 
 	nm_i->available_nids++;
 
-	update_free_nid_bitmap(sbi, nid, true, false);
+	update_free_nid_bitmap(sbi, nid, true, false, false);
 
 	spin_unlock(&nm_i->nid_list_lock);
 
@@ -2404,11 +2406,11 @@ static void __flush_nat_entry_set(struct f2fs_sb_info *sbi,
 			add_free_nid(sbi, nid, false);
 			spin_lock(&NM_I(sbi)->nid_list_lock);
 			NM_I(sbi)->available_nids++;
-			update_free_nid_bitmap(sbi, nid, true, false);
+			update_free_nid_bitmap(sbi, nid, true, false, false);
 			spin_unlock(&NM_I(sbi)->nid_list_lock);
 		} else {
 			spin_lock(&NM_I(sbi)->nid_list_lock);
-			update_free_nid_bitmap(sbi, nid, false, false);
+			update_free_nid_bitmap(sbi, nid, false, false, false);
 			spin_unlock(&NM_I(sbi)->nid_list_lock);
 		}
 	}
@@ -2533,8 +2535,10 @@ inline void load_free_nid_bitmap(struct f2fs_sb_info *sbi)
 		nid = i * NAT_ENTRY_PER_BLOCK;
 		last_nid = (i + 1) * NAT_ENTRY_PER_BLOCK;
 
+		spin_lock(&nm_i->free_nid_lock);
 		for (; nid < last_nid; nid++)
-			update_free_nid_bitmap(sbi, nid, true, true);
+			update_free_nid_bitmap(sbi, nid, true, true, true);
+		spin_unlock(&nm_i->free_nid_lock);
 	}
 
 	for (i = 0; i < nm_i->nat_blocks; i++) {
-- 
2.11.0


On 03/06, Chao Yu wrote:
> Both nat_bits cache and free_nid_bitmap cache provide same functionality
> as a intermediate cache between free nid cache and disk, but with
> different granularity of indicating free nid range, and different
> persistence policy. nat_bits cache provides better persistence ability,
> and free_nid_bitmap provides better granularity.
> 
> In this patch we combine advantage of both caches, so finally policy of
> the intermediate cache would be:
> - init: load free nid status from nat_bits into free_nid_bitmap
> - lookup: scan free_nid_bitmap before load NAT blocks
> - update: update free_nid_bitmap in real-time
> - persistence: udpate and persist nat_bits in checkpoint
> 
> Signed-off-by: Chao Yu <yuchao0@huawei.com>
> ---
>  fs/f2fs/node.c | 105 +++++++++++++++++++--------------------------------------
>  1 file changed, 35 insertions(+), 70 deletions(-)
> 
> diff --git a/fs/f2fs/node.c b/fs/f2fs/node.c
> index 1a759d45b7e4..625b46bc55ad 100644
> --- a/fs/f2fs/node.c
> +++ b/fs/f2fs/node.c
> @@ -338,9 +338,6 @@ static void set_node_addr(struct f2fs_sb_info *sbi, struct node_info *ni,
>  		set_nat_flag(e, IS_CHECKPOINTED, false);
>  	__set_nat_cache_dirty(nm_i, e);
>  
> -	if (enabled_nat_bits(sbi, NULL) && new_blkaddr == NEW_ADDR)
> -		clear_bit_le(NAT_BLOCK_OFFSET(ni->nid), nm_i->empty_nat_bits);
> -
>  	/* update fsync_mark if its inode nat entry is still alive */
>  	if (ni->nid != ni->ino)
>  		e = __lookup_nat_cache(nm_i, ni->ino);
> @@ -1920,58 +1917,6 @@ static void scan_free_nid_bits(struct f2fs_sb_info *sbi)
>  	up_read(&nm_i->nat_tree_lock);
>  }
>  
> -static int scan_nat_bits(struct f2fs_sb_info *sbi)
> -{
> -	struct f2fs_nm_info *nm_i = NM_I(sbi);
> -	struct page *page;
> -	unsigned int i = 0;
> -	nid_t nid;
> -
> -	if (!enabled_nat_bits(sbi, NULL))
> -		return -EAGAIN;
> -
> -	down_read(&nm_i->nat_tree_lock);
> -check_empty:
> -	i = find_next_bit_le(nm_i->empty_nat_bits, nm_i->nat_blocks, i);
> -	if (i >= nm_i->nat_blocks) {
> -		i = 0;
> -		goto check_partial;
> -	}
> -
> -	for (nid = i * NAT_ENTRY_PER_BLOCK; nid < (i + 1) * NAT_ENTRY_PER_BLOCK;
> -									nid++) {
> -		if (unlikely(nid >= nm_i->max_nid))
> -			break;
> -		add_free_nid(sbi, nid, true);
> -	}
> -
> -	if (nm_i->nid_cnt[FREE_NID_LIST] >= MAX_FREE_NIDS)
> -		goto out;
> -	i++;
> -	goto check_empty;
> -
> -check_partial:
> -	i = find_next_zero_bit_le(nm_i->full_nat_bits, nm_i->nat_blocks, i);
> -	if (i >= nm_i->nat_blocks) {
> -		disable_nat_bits(sbi, true);
> -		up_read(&nm_i->nat_tree_lock);
> -		return -EINVAL;
> -	}
> -
> -	nid = i * NAT_ENTRY_PER_BLOCK;
> -	page = get_current_nat_page(sbi, nid);
> -	scan_nat_page(sbi, page, nid);
> -	f2fs_put_page(page, 1);
> -
> -	if (nm_i->nid_cnt[FREE_NID_LIST] < MAX_FREE_NIDS) {
> -		i++;
> -		goto check_partial;
> -	}
> -out:
> -	up_read(&nm_i->nat_tree_lock);
> -	return 0;
> -}
> -
>  static void __build_free_nids(struct f2fs_sb_info *sbi, bool sync, bool mount)
>  {
>  	struct f2fs_nm_info *nm_i = NM_I(sbi);
> @@ -1993,21 +1938,6 @@ static void __build_free_nids(struct f2fs_sb_info *sbi, bool sync, bool mount)
>  
>  		if (nm_i->nid_cnt[FREE_NID_LIST])
>  			return;
> -
> -		/* try to find free nids with nat_bits */
> -		if (!scan_nat_bits(sbi) && nm_i->nid_cnt[FREE_NID_LIST])
> -			return;
> -	}
> -
> -	/* find next valid candidate */
> -	if (enabled_nat_bits(sbi, NULL)) {
> -		int idx = find_next_zero_bit_le(nm_i->full_nat_bits,
> -					nm_i->nat_blocks, 0);
> -
> -		if (idx >= nm_i->nat_blocks)
> -			set_sbi_flag(sbi, SBI_NEED_FSCK);
> -		else
> -			nid = idx * NAT_ENTRY_PER_BLOCK;
>  	}
>  
>  	/* readahead nat pages to be scanned */
> @@ -2590,6 +2520,38 @@ static int __get_nat_bitmaps(struct f2fs_sb_info *sbi)
>  	return 0;
>  }
>  
> +inline void load_free_nid_bitmap(struct f2fs_sb_info *sbi)
> +{
> +	struct f2fs_nm_info *nm_i = NM_I(sbi);
> +	unsigned int i = 0;
> +	nid_t nid, last_nid;
> +
> +	if (!enabled_nat_bits(sbi, NULL))
> +		return;
> +
> +	for (i = 0; i < nm_i->nat_blocks; i++) {
> +		i = find_next_bit_le(nm_i->empty_nat_bits, nm_i->nat_blocks, i);
> +		if (i >= nm_i->nat_blocks)
> +			break;
> +
> +		__set_bit_le(i, nm_i->nat_block_bitmap);
> +
> +		nid = i * NAT_ENTRY_PER_BLOCK;
> +		last_nid = (i + 1) * NAT_ENTRY_PER_BLOCK;
> +
> +		for (; nid < last_nid; nid++)
> +			update_free_nid_bitmap(sbi, nid, true, true);
> +	}
> +
> +	for (i = 0; i < nm_i->nat_blocks; i++) {
> +		i = find_next_bit_le(nm_i->full_nat_bits, nm_i->nat_blocks, i);
> +		if (i >= nm_i->nat_blocks)
> +			break;
> +
> +		__set_bit_le(i, nm_i->nat_block_bitmap);
> +	}
> +}
> +
>  static int init_node_manager(struct f2fs_sb_info *sbi)
>  {
>  	struct f2fs_super_block *sb_raw = F2FS_RAW_SUPER(sbi);
> @@ -2691,6 +2653,9 @@ int build_node_manager(struct f2fs_sb_info *sbi)
>  	if (err)
>  		return err;
>  
> +	/* load free nid status from nat_bits table */
> +	load_free_nid_bitmap(sbi);
> +
>  	build_free_nids(sbi, true, true);
>  	return 0;
>  }
> -- 
> 2.8.2.295.g3f1c1d0

Re: [PATCH v2] f2fs: combine nat_bits and free_nid_bitmap cache

[Chao Yu]

Hi Jaegeuk,

On 2017/3/8 6:27, Jaegeuk Kim wrote:
> Hi Chao,
> 
> There were two reasons for slow down; one is set_bit_le and the other was 
> spin_lock calls.
> 
> I think it would'b good to merge this patch in yours as well.
> Let me know. I'm ready to integrate together and test them.

The change looks good to me. ;)

Anyway I will send last updated patch which you have merged in order to tracking
others' comments if there will be.

Thanks,

> 
> Signed-off-by: Jaegeuk Kim <jaegeuk@kernel.org>
> ---
>  fs/f2fs/node.c | 22 +++++++++++++---------
>  1 file changed, 13 insertions(+), 9 deletions(-)
> 
> diff --git a/fs/f2fs/node.c b/fs/f2fs/node.c
> index 3377a512e299..0a1ea59c9d31 100644
> --- a/fs/f2fs/node.c
> +++ b/fs/f2fs/node.c
> @@ -1815,7 +1815,7 @@ static void remove_free_nid(struct f2fs_sb_info *sbi, nid_t nid)
>  }
>  
>  void update_free_nid_bitmap(struct f2fs_sb_info *sbi, nid_t nid,
> -							bool set, bool build)
> +			bool set, bool build, bool locked)
>  {
>  	struct f2fs_nm_info *nm_i = NM_I(sbi);
>  	unsigned int nat_ofs = NAT_BLOCK_OFFSET(nid);
> @@ -1829,12 +1829,14 @@ void update_free_nid_bitmap(struct f2fs_sb_info *sbi, nid_t nid,
>  	else
>  		__clear_bit_le(nid_ofs, nm_i->free_nid_bitmap[nat_ofs]);
>  
> -	spin_lock(&nm_i->free_nid_lock);
> +	if (!locked)
> +		spin_lock(&nm_i->free_nid_lock);
>  	if (set)
>  		nm_i->free_nid_count[nat_ofs]++;
>  	else if (!build)
>  		nm_i->free_nid_count[nat_ofs]--;
> -	spin_unlock(&nm_i->free_nid_lock);
> +	if (!locked)
> +		spin_unlock(&nm_i->free_nid_lock);
>  }
>  
>  static void scan_nat_page(struct f2fs_sb_info *sbi,
> @@ -1863,7 +1865,7 @@ static void scan_nat_page(struct f2fs_sb_info *sbi,
>  		f2fs_bug_on(sbi, blk_addr == NEW_ADDR);
>  		if (blk_addr == NULL_ADDR)
>  			freed = add_free_nid(sbi, start_nid, true);
> -		update_free_nid_bitmap(sbi, start_nid, freed, true);
> +		update_free_nid_bitmap(sbi, start_nid, freed, true, false);
>  	}
>  }
>  
> @@ -2018,7 +2020,7 @@ bool alloc_nid(struct f2fs_sb_info *sbi, nid_t *nid)
>  		__insert_nid_to_list(sbi, i, ALLOC_NID_LIST, false);
>  		nm_i->available_nids--;
>  
> -		update_free_nid_bitmap(sbi, *nid, false, false);
> +		update_free_nid_bitmap(sbi, *nid, false, false, false);
>  
>  		spin_unlock(&nm_i->nid_list_lock);
>  		return true;
> @@ -2074,7 +2076,7 @@ void alloc_nid_failed(struct f2fs_sb_info *sbi, nid_t nid)
>  
>  	nm_i->available_nids++;
>  
> -	update_free_nid_bitmap(sbi, nid, true, false);
> +	update_free_nid_bitmap(sbi, nid, true, false, false);
>  
>  	spin_unlock(&nm_i->nid_list_lock);
>  
> @@ -2404,11 +2406,11 @@ static void __flush_nat_entry_set(struct f2fs_sb_info *sbi,
>  			add_free_nid(sbi, nid, false);
>  			spin_lock(&NM_I(sbi)->nid_list_lock);
>  			NM_I(sbi)->available_nids++;
> -			update_free_nid_bitmap(sbi, nid, true, false);
> +			update_free_nid_bitmap(sbi, nid, true, false, false);
>  			spin_unlock(&NM_I(sbi)->nid_list_lock);
>  		} else {
>  			spin_lock(&NM_I(sbi)->nid_list_lock);
> -			update_free_nid_bitmap(sbi, nid, false, false);
> +			update_free_nid_bitmap(sbi, nid, false, false, false);
>  			spin_unlock(&NM_I(sbi)->nid_list_lock);
>  		}
>  	}
> @@ -2533,8 +2535,10 @@ inline void load_free_nid_bitmap(struct f2fs_sb_info *sbi)
>  		nid = i * NAT_ENTRY_PER_BLOCK;
>  		last_nid = (i + 1) * NAT_ENTRY_PER_BLOCK;
>  
> +		spin_lock(&nm_i->free_nid_lock);
>  		for (; nid < last_nid; nid++)
> -			update_free_nid_bitmap(sbi, nid, true, true);
> +			update_free_nid_bitmap(sbi, nid, true, true, true);
> +		spin_unlock(&nm_i->free_nid_lock);
>  	}
>  
>  	for (i = 0; i < nm_i->nat_blocks; i++) {
>