Skip to contentSkip to conversation

f2fs: various optimization & bugfixing for node management

PATCH In review Haicheng Li 2 participants 11 messages May 6, 2013 – May 8, 2013

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

v2 cover f2fs: various optimization & bugfixing for node management

Found several issues during my code-review of f2fs/node.c, but my orignial patches are based on Kim's linux-f2fs master branch, and they cannot be smoothly applied to latest dev branch.

So rebased and combined these patches into this patchset.

V1->V2: rebase the patches against Kim's linux-f2fs dev branch.

Haicheng Li (4):
f2fs: bugfix for alloc_nid_failed()
f2fs: code cleanup for scan_nat_page() and build_free_nids()
f2fs: optimize scan_nat_page()
f2fs: optimize build_free_nids()

 fs/f2fs/node.c |   31 ++++++++++++++++++++-----------
 1 file changed, 20 insertions(+), 11 deletions(-)
Signature · 1 line
1.7.9.5
#1 lore raw

PATCH v2 1/4 f2fs: bugfix for alloc_nid_failed()

Directly drop the free_nid cache when nm_i->fcnt > 2 * MAX_FREE_NIDS

Since there is NOT nmi->free_nid_list_lock spinlock protection between a sequential calling of alloc_nid() and alloc_nid_failed(), some other threads may already add new free_nid to the free_nid_list during this period.

We need to make sure nmi->fcnt is never > 2 * MAX_FREE_NIDS.

---
 fs/f2fs/node.c |    8 ++++++--
 1 file changed, 6 insertions(+), 2 deletions(-)
fs/f2fs/node.c +6 -2
index 7209d63..532ac57 100644
@@ -1439,8 +1439,12 @@ void alloc_nid_failed(struct f2fs_sb_info *sbi, nid_t nid)
 	spin_lock(&nm_i->free_nid_list_lock);
 	i = __lookup_free_nid_list(nid, &nm_i->free_nid_list);
 	BUG_ON(!i || i->state != NID_ALLOC);
-	i->state = NID_NEW;
-	nm_i->fcnt++;
+	if (nm_i->fcnt > 2 * MAX_FREE_NIDS)
+		__del_from_free_nid_list(i);
+	else {
+		i->state = NID_NEW;
+		nm_i->fcnt++;
+	}
 	spin_unlock(&nm_i->free_nid_list_lock);
 }
 
Signature · 1 line
1.7.9.5
#2 lore raw

PATCH v2 2/4 f2fs: code cleanup for scan_nat_page() and build_free_nids()

In reply to Haicheng Li

This patch does two cleanups:
1. remove unused variable "fcnt" in build_free_nids().
2. make scan_nat_page() as void type and remove useless variable "fcnt".

---
 fs/f2fs/node.c |   10 ++++------
 1 file changed, 4 insertions(+), 6 deletions(-)
fs/f2fs/node.c +4 -6
index 532ac57..1b45dd0 100644
@@ -1292,12 +1292,11 @@ static void remove_free_nid(struct f2fs_nm_info *nm_i, nid_t nid)
 	spin_unlock(&nm_i->free_nid_list_lock);
 }
 
-static int scan_nat_page(struct f2fs_nm_info *nm_i,
+static void scan_nat_page(struct f2fs_nm_info *nm_i,
 			struct page *nat_page, nid_t start_nid)
 {
 	struct f2fs_nat_block *nat_blk = page_address(nat_page);
 	block_t blk_addr;
-	int fcnt = 0;
 	int i;
 
 	i = start_nid % NAT_ENTRY_PER_BLOCK;
@@ -1308,9 +1307,8 @@ static int scan_nat_page(struct f2fs_nm_info *nm_i,
 		blk_addr  = le32_to_cpu(nat_blk->entries[i].block_addr);
 		BUG_ON(blk_addr == NEW_ADDR);
 		if (blk_addr == NULL_ADDR)
-			fcnt += add_free_nid(nm_i, start_nid);
+			add_free_nid(nm_i, start_nid);
 	}
-	return fcnt;
 }
 
 static void build_free_nids(struct f2fs_sb_info *sbi)
@@ -1319,7 +1317,7 @@ static void build_free_nids(struct f2fs_sb_info *sbi)
 	struct f2fs_nm_info *nm_i = NM_I(sbi);
 	struct curseg_info *curseg = CURSEG_I(sbi, CURSEG_HOT_DATA);
 	struct f2fs_summary_block *sum = curseg->sum_blk;
-	int fcnt = 0, i = 0;
+	int i = 0;
 	nid_t nid = nm_i->next_scan_nid;
 
 	/* Enough entries */
@@ -1332,7 +1330,7 @@ static void build_free_nids(struct f2fs_sb_info *sbi)
 	while (1) {
 		struct page *page = get_current_nat_page(sbi, nid);
 
-		fcnt += scan_nat_page(nm_i, page, nid);
+		scan_nat_page(nm_i, page, nid);
 		f2fs_put_page(page, 1);
 
 		nid += (NAT_ENTRY_PER_BLOCK - (nid % NAT_ENTRY_PER_BLOCK));
Signature · 1 line
1.7.9.5
#3 lore raw

PATCH v2 3/4 f2fs: optimize scan_nat_page()

In reply to Haicheng Li

When nm_i->fcnt > 2 * MAX_FREE_NIDS, stop scanning other NAT entries.

---
 fs/f2fs/node.c |   13 +++++++++----
 1 file changed, 9 insertions(+), 4 deletions(-)
fs/f2fs/node.c +9 -4
index 1b45dd0..1fe3fe2 100644
@@ -1254,7 +1254,7 @@ static int add_free_nid(struct f2fs_nm_info *nm_i, nid_t nid)
 	struct free_nid *i;
 
 	if (nm_i->fcnt > 2 * MAX_FREE_NIDS)
-		return 0;
+		return -1;
 
 	/* 0 nid should not be used */
 	if (nid == 0)
@@ -1302,12 +1302,17 @@ static void scan_nat_page(struct f2fs_nm_info *nm_i,
 	i = start_nid % NAT_ENTRY_PER_BLOCK;
 
 	for (; i < NAT_ENTRY_PER_BLOCK; i++, start_nid++) {
+		int cnt;
+
 		if (start_nid >= nm_i->max_nid)
 			break;
-		blk_addr  = le32_to_cpu(nat_blk->entries[i].block_addr);
+		blk_addr = le32_to_cpu(nat_blk->entries[i].block_addr);
 		BUG_ON(blk_addr == NEW_ADDR);
-		if (blk_addr == NULL_ADDR)
-			add_free_nid(nm_i, start_nid);
+		if (blk_addr == NULL_ADDR) {
+			cnt = add_free_nid(nm_i, start_nid);
+			if (cnt < 0)
+				break;
+		}
 	}
 }
 
Signature · 1 line
1.7.9.5
#4 lore raw

Re: [PATCH 3/4] f2fs: optimize scan_nat_page()

Hi,

2013-05-06 (월), 23:15 +0800, Haicheng Li:

Quoted 12 lines

When nm_i->fcnt > 2 * MAX_FREE_NIDS, stop scanning other NAT entries.

---
 fs/f2fs/node.c |   13 +++++++++----
 1 file changed, 9 insertions(+), 4 deletions(-)
fs/f2fs/node.c +0 -0
index 1b45dd0..1fe3fe2 100644

fs/f2fs/node.c static int add_free_nid(struct f2fs_nm_info *nm_i, nid_t nid) · line 1257

Quoted 5 lines
fs/f2fs/node.c +1 -1
@@ -1254,7 +1254,7 @@ static int add_free_nid(struct f2fs_nm_info *nm_i, nid_t nid)
 	struct free_nid *i;
 
 	if (nm_i->fcnt > 2 * MAX_FREE_NIDS)
-		return 0;
+		return -1;

We should check all the handler of add_free_nid(). So, plz see the below modified patch.

Quoted 11 lines
fs/f2fs/node.c +2 -0
 	/* 0 nid should not be used */
 	if (nid == 0)
@@ -1302,12 +1302,17 @@ static void scan_nat_page(struct f2fs_nm_info *nm_i,
 	i = start_nid % NAT_ENTRY_PER_BLOCK;
 
 	for (; i < NAT_ENTRY_PER_BLOCK; i++, start_nid++) {
+		int cnt;
+
 		if (start_nid >= nm_i->max_nid)
 			break;

fs/f2fs/node.c static void scan_nat_page(struct f2fs_nm_info *nm_i, · line 1315

Quoted 10 lines
fs/f2fs/node.c +6 -3
-		blk_addr  = le32_to_cpu(nat_blk->entries[i].block_addr);
+		blk_addr = le32_to_cpu(nat_blk->entries[i].block_addr);
 		BUG_ON(blk_addr == NEW_ADDR);
-		if (blk_addr == NULL_ADDR)
-			add_free_nid(nm_i, start_nid);
+		if (blk_addr == NULL_ADDR) {
+			cnt = add_free_nid(nm_i, start_nid);
+			if (cnt < 0)
+				break;
+		}

Here we need to eliminate cnt.

fs/f2fs/node.c static void scan_nat_page(struct f2fs_nm_info *nm_i, · line 1318

Quoted 3 lines
fs/f2fs/node.c +0 -0
 	}
 }
 

-----
From e2da02f0ba045f792d166ac8215d04474c06f319 Mon Sep 17 00:00:00 2001
From: Haicheng Li <[email protected]>
Date: Mon, 6 May 2013 23:15:43 +0800
Subject: [PATCH] f2fs: optimize scan_nat_page()
Cc: [email protected], [email protected], [email protected]

When nm_i->fcnt > 2 * MAX_FREE_NIDS, stop scanning other NAT entries.

[Jaegeuk Kim: fix handling the return value of add_free_nid()]
---
 fs/f2fs/node.c | 14 +++++++++-----
 1 file changed, 9 insertions(+), 5 deletions(-)
fs/f2fs/node.c +0 -0
index 122200e..e42934e 100644
@@ -1254,7 +1254,7 @@ static int add_free_nid(struct f2fs_nm_info *nm_i,

nid_t nid)
struct free_nid *i;

if (nm_i->fcnt > 2 * MAX_FREE_NIDS)
- return 0;
+ return -1;

/* 0 nid should not be used */
if (nid == 0)
@@ -1302,12 +1302,16 @@ static void scan_nat_page(struct f2fs_nm_info *nm_i,
i = start_nid % NAT_ENTRY_PER_BLOCK;

for (; i < NAT_ENTRY_PER_BLOCK; i++, start_nid++) {
+
if (start_nid >= nm_i->max_nid)
break;
- blk_addr = le32_to_cpu(nat_blk->entries[i].block_addr);
+
+ blk_addr = le32_to_cpu(nat_blk->entries[i].block_addr);
BUG_ON(blk_addr == NEW_ADDR);
- if (blk_addr == NULL_ADDR)
- add_free_nid(nm_i, start_nid);
+ if (blk_addr == NULL_ADDR) {
+ if (add_free_nid(nm_i, start_nid) < 0)
+ break;
+ }
}
}

@@ -1655,7 +1659,7 @@ flush_now:
}

if (nat_get_blkaddr(ne) == NULL_ADDR &&
- !add_free_nid(NM_I(sbi), nid)) {
+ add_free_nid(NM_I(sbi), nid) <= 0) {
write_lock(&nm_i->nat_tree_lock); __del_from_nat_cache(nm_i, ne); write_unlock(&nm_i->nat_tree_lock);

Signature · 9 lines
1.8.1.3.566.gaa39828





-- 
Jaegeuk Kim
Samsung
#5 lore raw

Re: [PATCH 3/4] f2fs: optimize scan_nat_page()

Quoted 8 lines · Jaegeuk Kim

Hi,

2013-05-06 (월), 23:15 +0800, Haicheng Li:

Review

Quoted 3 lines
(quoted diff) +1 -1
 	if (nm_i->fcnt > 2 * MAX_FREE_NIDS)
-		return 0;
+		return -1;

We should check all the handler of add_free_nid().

yes, sorry that I missed double checking it while rebasing this patch from master to dev branch, since there is only one handler on the master branch.

Quoted 8 lines

So, plz see the below modified patch.

Review

Quoted 5 lines
(quoted diff) +5 -0
+		if (blk_addr == NULL_ADDR) {
+			cnt = add_free_nid(nm_i, start_nid);
+			if (cnt < 0)
+				break;
+		}

Here we need to eliminate cnt.

sure, harmless & can reduce the code line.

and the below patch looks good to me. Thanks.

Quoted 64 lines

-----
From e2da02f0ba045f792d166ac8215d04474c06f319 Mon Sep 17 00:00:00 2001
From: Haicheng Li <[email protected]>
Date: Mon, 6 May 2013 23:15:43 +0800
Subject: [PATCH] f2fs: optimize scan_nat_page()
Cc: [email protected], [email protected], [email protected]

When nm_i->fcnt > 2 * MAX_FREE_NIDS, stop scanning other NAT entries.

[Jaegeuk Kim: fix handling the return value of add_free_nid()]
---
 fs/f2fs/node.c | 14 +++++++++-----
 1 file changed, 9 insertions(+), 5 deletions(-)
fs/f2fs/node.c +1 -1
index 122200e..e42934e 100644
@@ -1254,7 +1254,7 @@ static int add_free_nid(struct f2fs_nm_info *nm_i,
 nid_t nid)
 	struct free_nid *i;
 
 	if (nm_i->fcnt > 2 * MAX_FREE_NIDS)
-		return 0;
+		return -1;
 
 	/* 0 nid should not be used */
fs/f2fs/node.c +8 -4
 	if (nid == 0)
@@ -1302,12 +1302,16 @@ static void scan_nat_page(struct f2fs_nm_info
 *nm_i,
 	i = start_nid % NAT_ENTRY_PER_BLOCK;
 
 	for (; i < NAT_ENTRY_PER_BLOCK; i++, start_nid++) {
+
 		if (start_nid >= nm_i->max_nid)
 			break;
-		blk_addr  = le32_to_cpu(nat_blk->entries[i].block_addr);
+
+		blk_addr = le32_to_cpu(nat_blk->entries[i].block_addr);
 		BUG_ON(blk_addr == NEW_ADDR);
-		if (blk_addr == NULL_ADDR)
-			add_free_nid(nm_i, start_nid);
+		if (blk_addr == NULL_ADDR) {
+			if (add_free_nid(nm_i, start_nid) < 0)
+				break;
+		}
 	}
 }
@@ -1655,7 +1659,7 @@ flush_now:
 		}
 
 		if (nat_get_blkaddr(ne) == NULL_ADDR &&
-					!add_free_nid(NM_I(sbi), nid)) {
+				add_free_nid(NM_I(sbi), nid) <= 0) {
 			write_lock(&nm_i->nat_tree_lock);
 			__del_from_nat_cache(nm_i, ne);
 			write_unlock(&nm_i->nat_tree_lock);
Signature · 1 line
1.8.1.3.566.gaa39828
#6 lore raw

PATCH v2 4/4 f2fs: optimize build_free_nids()

In reply to Haicheng Li

When nm_i->fcnt > 2 * MAX_FREE_NIDS, stop scanning other NAT pages.

---
 fs/f2fs/node.c |    2 ++
 1 file changed, 2 insertions(+)
fs/f2fs/node.c +2 -0
index 1fe3fe2..3136224 100644
@@ -1342,6 +1342,8 @@ static void build_free_nids(struct f2fs_sb_info *sbi)
 		if (nid >= nm_i->max_nid)
 			nid = 0;
 
+		if (nm_i->fcnt > 2 * MAX_FREE_NIDS)
+			break;
 		if (i++ == FREE_NID_PAGES)
 			break;
 	}
Signature · 1 line
1.7.9.5
#7 lore raw

Re: [PATCH 4/4] f2fs: optimize build_free_nids()

Hi,

2013-05-06 (월), 23:15 +0800, Haicheng Li:

Quoted 12 lines

When nm_i->fcnt > 2 * MAX_FREE_NIDS, stop scanning other NAT pages.

---
 fs/f2fs/node.c |    2 ++
 1 file changed, 2 insertions(+)
fs/f2fs/node.c +0 -0
index 1fe3fe2..3136224 100644

fs/f2fs/node.c static void build_free_nids(struct f2fs_sb_info *sbi) · line 1346

Quoted 5 lines
fs/f2fs/node.c +2 -0
@@ -1342,6 +1342,8 @@ static void build_free_nids(struct f2fs_sb_info *sbi)
 		if (nid >= nm_i->max_nid)
 			nid = 0;
 
+		if (nm_i->fcnt > 2 * MAX_FREE_NIDS)
+			break;

Could you explain when this can happen?

IMO, this is an unnecessary condition check, since the below condition that includes FREE_NID_PAGES already limits the number of free nids. Thanks,

Quoted 3 lines
fs/f2fs/node.c +0 -0
 		if (i++ == FREE_NID_PAGES)
 			break;
 	}
Signature · 2 lines
Jaegeuk Kim
Samsung
#8 lore raw

Re: [PATCH 4/4] f2fs: optimize build_free_nids()

Quoted 9 lines · Jaegeuk Kim

2013-05-06 (월), 23:15 +0800, Haicheng Li:

Quoted 8 lines
fs/f2fs/node.c +0 -0
index 1fe3fe2..3136224 100644
@@ -1342,6 +1342,8 @@ static void build_free_nids(struct f2fs_sb_info *sbi)
 		if (nid >= nm_i->max_nid)
 			nid = 0;
 
Quoted 4 lines

fs/f2fs/node.c static void build_free_nids(struct f2fs_sb_info *sbi) · line 1346

Quoted 2 lines
fs/f2fs/node.c +2 -0
+		if (nm_i->fcnt > 2 * MAX_FREE_NIDS)
+			break;

Could you explain when this can happen?

I'm thinking of this possible scenario:

as we don't hold any spinlock to protect the context, add_free_nid() could be called by other thread anytime, e.g. by the gc_thread_func() in background.

then nm_i->fcnt could be increased as 2 * MAX_FREE_NIDS while i < FREE_NID_PAGES.

Anything I misconsidered?

Quoted 3 lines

IMO, this is an unnecessary condition check, since the below condition that includes FREE_NID_PAGES already limits the number of free nids. Thanks,

hmm, the pros is that this check may possibly avoid some (< 4) unnecessary while-loop, the cons is that too many checks of (nm_i->fcnt > 2 * MAX_FREE_NIDS) would make the code looking messy and fragmentary...

Quoted 7 lines
Quoted 3 lines
fs/f2fs/node.c +0 -0
 		if (i++ == FREE_NID_PAGES)
 			break;
 	}
Signature · 2 lines
Jaegeuk Kim
Samsung

--
To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

#9 lore raw

Re: [PATCH 4/4] f2fs: optimize build_free_nids()

2013-05-08 (수), 14:24 +0800, Haicheng Li:

Quoted 15 lines · Jaegeuk Kim
Quoted 9 lines

2013-05-06 (월), 23:15 +0800, Haicheng Li:

Quoted 8 lines
fs/f2fs/node.c +0 -0
index 1fe3fe2..3136224 100644
@@ -1342,6 +1342,8 @@ static void build_free_nids(struct f2fs_sb_info *sbi)
 		if (nid >= nm_i->max_nid)
 			nid = 0;
 
Quoted 4 lines

fs/f2fs/node.c static void build_free_nids(struct f2fs_sb_info *sbi) · line 1346

Quoted 2 lines
fs/f2fs/node.c +2 -0
+		if (nm_i->fcnt > 2 * MAX_FREE_NIDS)
+			break;

Could you explain when this can happen?

Quoted 4 lines

I'm thinking of this possible scenario:

as we don't hold any spinlock to protect the context, add_free_nid() could be called by other thread anytime, e.g. by the gc_thread_func() in background.

The gc_thread_func() is not a proper example here though, the buid_free_nids() is covered by nm_i->build_lock, so build_free_nids is entered only one at a time.
In addtion, build_free_nids starts with checking if (nm_i->fcnt > NAT_ENTRY_PER_BLOCK) in order not to be conducted repeatedely.

Quoted 3 lines

then nm_i->fcnt could be increased as 2 * MAX_FREE_NIDS while i < FREE_NID_PAGES. Anything I misconsidered?

Apart from the correctness of this behavior, I'm not sure why we should strictly manage this threshold value.
Should we really need to do this?

Quoted 23 lines
Quoted 4 lines

IMO, this is an unnecessary condition check, since the below condition that includes FREE_NID_PAGES already limits the number of free nids. Thanks,

hmm, the pros is that this check may possibly avoid some (< 4) unnecessary while-loop, the cons is that too many checks of (nm_i->fcnt > 2 * MAX_FREE_NIDS) would make the code looking messy and fragmentary...

Quoted 7 lines
Quoted 3 lines
fs/f2fs/node.c +0 -0
 		if (i++ == FREE_NID_PAGES)
 			break;
 	}
Signature · 2 lines
Jaegeuk Kim
Samsung

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Signature · 2 lines
Jaegeuk Kim
Samsung
#10 lore raw

Re: [PATCH 4/4] f2fs: optimize build_free_nids()

Quoted 4 lines · Jaegeuk Kim
Quoted 4 lines

Could you explain when this can happen?

I'm thinking of this possible scenario:

Quoted 8 lines
Quoted 2 lines

as we don't hold any spinlock to protect the context, add_free_nid() could be called by other thread anytime, e.g. by the gc_thread_func() in background.

The gc_thread_func() is not a proper example here though, the buid_free_nids() is covered by nm_i->build_lock, so build_free_nids is entered only one at a time.
In addtion, build_free_nids starts with checking if (nm_i->fcnt > NAT_ENTRY_PER_BLOCK) in order not to be conducted repeatedely.

surely build_free_nids() itself is under well protection.
but this scenario would happen when gc_thread_func() is running in background:

        f2fs_gc()
                write_checkpoint()
                        flush_nat_entries()
                                add_free_nid()
Quoted 7 lines
Quoted 3 lines

then nm_i->fcnt could be increased as 2 * MAX_FREE_NIDS while i < FREE_NID_PAGES. Anything I misconsidered?

Apart from the correctness of this behavior, I'm not sure why we should strictly manage this threshold value.
Should we really need to do this?

This threshold value itself should have already be well managed in current code.

This patch is just to avoid unecessary while-loop that tries scan_nat_page() even when this threshold has already been reached. But as I mentioned previously, it just possibly avoids "< 4" unecessary tries.

So this patch now becomes a very very trivial optimization because scan_nat_page() itself can detect out the condition.

In such case, You can *ignore* this patch:).
Thanks for the patch review, Jaegeuk!

Quoted 8 lines
Quoted 8 lines

hmm, the pros is that this check may possibly avoid some (< 4) unnecessary while-loop, the cons is that too many checks of (nm_i->fcnt > 2 * MAX_FREE_NIDS) would make the code looking messy and fragmentary...

Quoted 3 lines
Quoted 3 lines
fs/f2fs/node.c +0 -0
 		if (i++ == FREE_NID_PAGES)
 			break;
 	}

-haicheng