Skip to contentSkip to conversation

f2fs: split free nid list

PATCH Applied Chao Yu 3 participants 15 messages Oct 11, 2016 – Oct 13, 2016 F2FS file system

lore
Share & tools
lore

Chao Yu

author maintainer
#0 lore raw

PATCH 1/7 f2fs: split free nid list

From: Chao Yu <[email protected]>

During free nid allocation, in order to do preallocation, we will tag free nid entry as allocated one and still leave it in free nid list, for other allocators who want to grab free nids, it needs to traverse the free nid list for lookup. It becomes overhead in scenario of allocating free nid intensively by multithreads.

This patch splits free nid list to two list: {free,alloc}_nid_list, to keep free nids and preallocated free nids separately, after that, traverse latency will be gone.

Signed-off-by Chao Yu <[email protected]>
---
 fs/f2fs/debug.c    |  5 +++--
 fs/f2fs/f2fs.h     |  4 +++-
 fs/f2fs/node.c     | 56 ++++++++++++++++++++++++++++++++----------------------
 fs/f2fs/node.h     |  2 +-
 fs/f2fs/shrinker.c |  4 ++--
 5 files changed, 42 insertions(+), 29 deletions(-)
fs/f2fs/debug.c +3 -2
index fb245bd..9789138 100644
@@ -74,7 +74,7 @@ static void update_general_status(struct f2fs_sb_info *sbi)
 	si->dirty_nats = NM_I(sbi)->dirty_nat_cnt;
 	si->sits = MAIN_SEGS(sbi);
 	si->dirty_sits = SIT_I(sbi)->dirty_sentries;
-	si->fnids = NM_I(sbi)->fcnt;
+	si->fnids = NM_I(sbi)->free_nid_cnt;
 	si->bg_gc = sbi->bg_gc;
 	si->util_free = (int)(free_user_blocks(sbi) >> sbi->log_blocks_per_seg)
 		* 100 / (int)(sbi->user_block_count >> sbi->log_blocks_per_seg)

@@ -194,7 +194,8 @@ get_cache:
 		si->cache_mem += sizeof(struct flush_cmd_control);
 
 	/* free nids */
-	si->cache_mem += NM_I(sbi)->fcnt * sizeof(struct free_nid);
+	si->cache_mem += (NM_I(sbi)->free_nid_cnt + NM_I(sbi)->alloc_nid_cnt) *
+							sizeof(struct free_nid);
 	si->cache_mem += NM_I(sbi)->nat_cnt * sizeof(struct nat_entry);
 	si->cache_mem += NM_I(sbi)->dirty_nat_cnt *
 					sizeof(struct nat_entry_set);
fs/f2fs/f2fs.h +3 -1
index d868175..d6dff15 100644
@@ -543,8 +543,10 @@ struct f2fs_nm_info {
 	/* free node ids management */
 	struct radix_tree_root free_nid_root;/* root of the free_nid cache */
 	struct list_head free_nid_list;	/* a list for free nids */
+	struct list_head alloc_nid_list;/* a list for allocating nids */
 	spinlock_t free_nid_list_lock;	/* protect free nid list */
-	unsigned int fcnt;		/* the number of free node id */
+	unsigned int free_nid_cnt;	/* the number of free node id */
+	unsigned int alloc_nid_cnt;	/* the number of allocating node id */
 	struct mutex build_lock;	/* lock for build free nids */
 
 	/* for checkpoint */
fs/f2fs/node.c +33 -23

167 lines not on this page · raw message

fs/f2fs/node.h +1 -1
index 868bec6..66928d7 100644
@@ -170,7 +170,7 @@ static inline void next_free_nid(struct f2fs_sb_info *sbi, nid_t *nid)
 	struct free_nid *fnid;
 
 	spin_lock(&nm_i->free_nid_list_lock);
-	if (nm_i->fcnt <= 0) {
+	if (nm_i->free_nid_cnt <= 0) {
 		spin_unlock(&nm_i->free_nid_list_lock);
 		return;
 	}
fs/f2fs/shrinker.c +2 -2
index 46c9154..8b0a112 100644
@@ -26,8 +26,8 @@ static unsigned long __count_nat_entries(struct f2fs_sb_info *sbi)
 
 static unsigned long __count_free_nids(struct f2fs_sb_info *sbi)
 {
-	if (NM_I(sbi)->fcnt > MAX_FREE_NIDS)
-		return NM_I(sbi)->fcnt - MAX_FREE_NIDS;
+	if (NM_I(sbi)->free_nid_cnt > MAX_FREE_NIDS)
+		return NM_I(sbi)->free_nid_cnt - MAX_FREE_NIDS;
 	return 0;
 }
Signature · 1 line
2.10.1
author maintainer
#1 lore raw

PATCH 2/7 f2fs: clean up nid list operation

From: Chao Yu <[email protected]>

Introduce new help __insert_nid_to_list and __remove_nid_from_list to clean up nid list related codes.

Signed-off-by Chao Yu <[email protected]>
---
 fs/f2fs/node.c | 66 ++++++++++++++++++++++++++++++++++++++++------------------
 fs/f2fs/node.h |  5 +++++
 2 files changed, 51 insertions(+), 20 deletions(-)
fs/f2fs/node.c +46 -20
index a1725a9..ea9ff8c 100644
@@ -1698,10 +1698,40 @@ static struct free_nid *__lookup_free_nid_list(struct f2fs_nm_info *nm_i,
 static void __del_from_free_nid_list(struct f2fs_nm_info *nm_i,
 						struct free_nid *i)
 {
-	list_del(&i->list);
 	radix_tree_delete(&nm_i->free_nid_root, i->nid);
 }
 
+static void __insert_nid_to_list(struct f2fs_sb_info *sbi,
+					struct free_nid *i, enum nid_list list)
+{
+	struct f2fs_nm_info *nm_i = NM_I(sbi);
+
+	if (list == FREE_NID_LIST) {
+		f2fs_bug_on(sbi, i->state != NID_NEW);
+		nm_i->free_nid_cnt++;
+		list_add_tail(&i->list, &nm_i->free_nid_list);
+	} else {
+		f2fs_bug_on(sbi, i->state != NID_ALLOC);
+		nm_i->alloc_nid_cnt++;
+		list_add_tail(&i->list, &nm_i->alloc_nid_list);
+	}
+}
+
+static void __remove_nid_from_list(struct f2fs_sb_info *sbi,
+					struct free_nid *i, enum nid_list list)
+{
+	struct f2fs_nm_info *nm_i = NM_I(sbi);
+
+	if (list == FREE_NID_LIST) {
+		f2fs_bug_on(sbi, i->state != NID_NEW);
+		nm_i->free_nid_cnt--;
+	} else {
+		f2fs_bug_on(sbi, i->state != NID_ALLOC);
+		nm_i->alloc_nid_cnt--;
+	}
+	list_del(&i->list);
+}
+
 static int add_free_nid(struct f2fs_sb_info *sbi, nid_t nid, bool build)
 {
 	struct f2fs_nm_info *nm_i = NM_I(sbi);

@@ -1739,8 +1769,7 @@ static int add_free_nid(struct f2fs_sb_info *sbi, nid_t nid, bool build)
 		kmem_cache_free(free_nid_slab, i);
 		return 0;
 	}
-	list_add_tail(&i->list, &nm_i->free_nid_list);
-	nm_i->free_nid_cnt++;
+	__insert_nid_to_list(sbi, i, FREE_NID_LIST);
 	spin_unlock(&nm_i->free_nid_list_lock);
 	radix_tree_preload_end();
 	return 1;

@@ -1755,8 +1784,8 @@ static void remove_free_nid(struct f2fs_sb_info *sbi, nid_t nid)
 	spin_lock(&nm_i->free_nid_list_lock);
 	i = __lookup_free_nid_list(nm_i, nid);
 	if (i && i->state == NID_NEW) {
+		__remove_nid_from_list(sbi, i, FREE_NID_LIST);
 		__del_from_free_nid_list(nm_i, i);
-		nm_i->free_nid_cnt--;
 		need_free = true;
 	}
 	spin_unlock(&nm_i->free_nid_list_lock);

@@ -1867,12 +1896,11 @@ retry:
 		f2fs_bug_on(sbi, list_empty(&nm_i->free_nid_list));
 		i = list_first_entry(&nm_i->free_nid_list,
 					struct free_nid, list);
-		f2fs_bug_on(sbi, i->state != NID_NEW);
 		*nid = i->nid;
+
+		__remove_nid_from_list(sbi, i, FREE_NID_LIST);
 		i->state = NID_ALLOC;
-		nm_i->free_nid_cnt--;
-		nm_i->alloc_nid_cnt++;
-		list_move_tail(&i->list, &nm_i->alloc_nid_list);
+		__insert_nid_to_list(sbi, i, ALLOC_NID_LIST);
 		spin_unlock(&nm_i->free_nid_list_lock);
 		return true;
 	}

@@ -1895,9 +1923,9 @@ void alloc_nid_done(struct f2fs_sb_info *sbi, nid_t nid)
 
 	spin_lock(&nm_i->free_nid_list_lock);
 	i = __lookup_free_nid_list(nm_i, nid);
-	f2fs_bug_on(sbi, !i || i->state != NID_ALLOC);
+	f2fs_bug_on(sbi, !i);
+	__remove_nid_from_list(sbi, i, ALLOC_NID_LIST);
 	__del_from_free_nid_list(nm_i, i);
-	nm_i->alloc_nid_cnt--;
 	spin_unlock(&nm_i->free_nid_list_lock);
 
 	kmem_cache_free(free_nid_slab, i);

@@ -1917,16 +1945,16 @@ 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(nm_i, nid);
-	f2fs_bug_on(sbi, !i || i->state != NID_ALLOC);
+	f2fs_bug_on(sbi, !i);
+
+	__remove_nid_from_list(sbi, i, ALLOC_NID_LIST);
+
 	if (!available_free_memory(sbi, FREE_NIDS)) {
-		nm_i->alloc_nid_cnt--;
 		__del_from_free_nid_list(nm_i, i);
 		need_free = true;
 	} else {
 		i->state = NID_NEW;
-		nm_i->free_nid_cnt++;
-		nm_i->alloc_nid_cnt--;
-		list_move_tail(&i->list, &nm_i->free_nid_list);
+		__insert_nid_to_list(sbi, i, FREE_NID_LIST);
 	}
 	spin_unlock(&nm_i->free_nid_list_lock);
 

@@ -1951,11 +1979,10 @@ int try_to_free_nids(struct f2fs_sb_info *sbi, int nr_shrink)
 		if (nr_shrink <= 0 || nm_i->free_nid_cnt <= MAX_FREE_NIDS)
 			break;
 
-		f2fs_bug_on(sbi, i->state == NID_ALLOC);
-
+		__remove_nid_from_list(sbi, i, FREE_NID_LIST);
 		__del_from_free_nid_list(nm_i, i);
+
 		kmem_cache_free(free_nid_slab, i);
-		nm_i->free_nid_cnt--;
 		nr_shrink--;
 	}
 	spin_unlock(&nm_i->free_nid_list_lock);

@@ -2340,9 +2367,8 @@ void destroy_node_manager(struct f2fs_sb_info *sbi)
 	/* destroy free nid list */
 	spin_lock(&nm_i->free_nid_list_lock);
 	list_for_each_entry_safe(i, next_i, &nm_i->free_nid_list, list) {
-		f2fs_bug_on(sbi, i->state == NID_ALLOC);
+		__remove_nid_from_list(sbi, i, FREE_NID_LIST);
 		__del_from_free_nid_list(nm_i, i);
-		nm_i->free_nid_cnt--;
 		spin_unlock(&nm_i->free_nid_list_lock);
 		kmem_cache_free(free_nid_slab, i);
 		spin_lock(&nm_i->free_nid_list_lock);
fs/f2fs/node.h +5 -0
index 66928d7..a4ee774 100644
@@ -158,6 +158,11 @@ enum nid_state {
 	NID_ALLOC	/* it is allocated */
 };
 
+enum nid_list {
+	FREE_NID_LIST,
+	ALLOC_NID_LIST
+};
+
 struct free_nid {
 	struct list_head list;	/* for free node id list */
 	nid_t nid;		/* node id */
Signature · 1 line
2.10.1
author maintainer
#2 lore raw

PATCH 3/7 f2fs: rename free nid cache operation

In reply to Chao Yu

From: Chao Yu <[email protected]>

Rename free nid cache operation for readability, no functionality change.

Signed-off-by Chao Yu <[email protected]>
---
 fs/f2fs/node.c | 28 +++++++++++++++++-----------
 1 file changed, 17 insertions(+), 11 deletions(-)
fs/f2fs/node.c +17 -11
index ea9ff8c..92c9aa4 100644
@@ -1689,13 +1689,19 @@ const struct address_space_operations f2fs_node_aops = {
 #endif
 };
 
-static struct free_nid *__lookup_free_nid_list(struct f2fs_nm_info *nm_i,
+static struct free_nid *__lookup_free_nid_cache(struct f2fs_nm_info *nm_i,
 						nid_t n)
 {
 	return radix_tree_lookup(&nm_i->free_nid_root, n);
 }
 
-static void __del_from_free_nid_list(struct f2fs_nm_info *nm_i,
+static int __insert_to_free_nid_cache(struct f2fs_nm_info *nm_i,
+						struct free_nid *i)
+{
+	return radix_tree_insert(&nm_i->free_nid_root, i->nid, i);
+}
+
+static void __del_from_free_nid_cache(struct f2fs_nm_info *nm_i,
 						struct free_nid *i)
 {
 	radix_tree_delete(&nm_i->free_nid_root, i->nid);

@@ -1763,7 +1769,7 @@ static int add_free_nid(struct f2fs_sb_info *sbi, nid_t nid, bool build)
 	}
 
 	spin_lock(&nm_i->free_nid_list_lock);
-	if (radix_tree_insert(&nm_i->free_nid_root, i->nid, i)) {
+	if (__insert_to_free_nid_cache(nm_i, i)) {
 		spin_unlock(&nm_i->free_nid_list_lock);
 		radix_tree_preload_end();
 		kmem_cache_free(free_nid_slab, i);

@@ -1782,10 +1788,10 @@ static void remove_free_nid(struct f2fs_sb_info *sbi, nid_t nid)
 	bool need_free = false;
 
 	spin_lock(&nm_i->free_nid_list_lock);
-	i = __lookup_free_nid_list(nm_i, nid);
+	i = __lookup_free_nid_cache(nm_i, nid);
 	if (i && i->state == NID_NEW) {
 		__remove_nid_from_list(sbi, i, FREE_NID_LIST);
-		__del_from_free_nid_list(nm_i, i);
+		__del_from_free_nid_cache(nm_i, i);
 		need_free = true;
 	}
 	spin_unlock(&nm_i->free_nid_list_lock);

@@ -1922,10 +1928,10 @@ void alloc_nid_done(struct f2fs_sb_info *sbi, nid_t nid)
 	struct free_nid *i;
 
 	spin_lock(&nm_i->free_nid_list_lock);
-	i = __lookup_free_nid_list(nm_i, nid);
+	i = __lookup_free_nid_cache(nm_i, nid);
 	f2fs_bug_on(sbi, !i);
 	__remove_nid_from_list(sbi, i, ALLOC_NID_LIST);
-	__del_from_free_nid_list(nm_i, i);
+	__del_from_free_nid_cache(nm_i, i);
 	spin_unlock(&nm_i->free_nid_list_lock);
 
 	kmem_cache_free(free_nid_slab, i);

@@ -1944,13 +1950,13 @@ void alloc_nid_failed(struct f2fs_sb_info *sbi, nid_t nid)
 		return;
 
 	spin_lock(&nm_i->free_nid_list_lock);
-	i = __lookup_free_nid_list(nm_i, nid);
+	i = __lookup_free_nid_cache(nm_i, nid);
 	f2fs_bug_on(sbi, !i);
 
 	__remove_nid_from_list(sbi, i, ALLOC_NID_LIST);
 
 	if (!available_free_memory(sbi, FREE_NIDS)) {
-		__del_from_free_nid_list(nm_i, i);
+		__del_from_free_nid_cache(nm_i, i);
 		need_free = true;
 	} else {
 		i->state = NID_NEW;

@@ -1980,7 +1986,7 @@ int try_to_free_nids(struct f2fs_sb_info *sbi, int nr_shrink)
 			break;
 
 		__remove_nid_from_list(sbi, i, FREE_NID_LIST);
-		__del_from_free_nid_list(nm_i, i);
+		__del_from_free_nid_cache(nm_i, i);
 
 		kmem_cache_free(free_nid_slab, i);
 		nr_shrink--;

@@ -2368,7 +2374,7 @@ void destroy_node_manager(struct f2fs_sb_info *sbi)
 	spin_lock(&nm_i->free_nid_list_lock);
 	list_for_each_entry_safe(i, next_i, &nm_i->free_nid_list, list) {
 		__remove_nid_from_list(sbi, i, FREE_NID_LIST);
-		__del_from_free_nid_list(nm_i, i);
+		__del_from_free_nid_cache(nm_i, i);
 		spin_unlock(&nm_i->free_nid_list_lock);
 		kmem_cache_free(free_nid_slab, i);
 		spin_lock(&nm_i->free_nid_list_lock);
Signature · 1 line
2.10.1
maintainer
#3 lore raw

Re: [PATCH 3/7] f2fs: rename free nid cache operation

Hi Chao,

Quoted 3 lines · Chao Yu

From: Chao Yu <[email protected]>

Rename free nid cache operation for readability, no functionality change.

Well, I don't think this can be a *cache*, since there is no cache-related operations such as reordering by cache hit, whereas it is more likely to be a singled one-way list.

Thanks,

Quoted 103 lines
Signed-off-by Chao Yu <[email protected]>
---
 fs/f2fs/node.c | 28 +++++++++++++++++-----------
 1 file changed, 17 insertions(+), 11 deletions(-)
fs/f2fs/node.c +17 -11
index ea9ff8c..92c9aa4 100644
@@ -1689,13 +1689,19 @@ const struct address_space_operations f2fs_node_aops = {
 #endif
 };
 
-static struct free_nid *__lookup_free_nid_list(struct f2fs_nm_info *nm_i,
+static struct free_nid *__lookup_free_nid_cache(struct f2fs_nm_info *nm_i,
 						nid_t n)
 {
 	return radix_tree_lookup(&nm_i->free_nid_root, n);
 }
 
-static void __del_from_free_nid_list(struct f2fs_nm_info *nm_i,
+static int __insert_to_free_nid_cache(struct f2fs_nm_info *nm_i,
+						struct free_nid *i)
+{
+	return radix_tree_insert(&nm_i->free_nid_root, i->nid, i);
+}
+
+static void __del_from_free_nid_cache(struct f2fs_nm_info *nm_i,
 						struct free_nid *i)
 {
 	radix_tree_delete(&nm_i->free_nid_root, i->nid);

@@ -1763,7 +1769,7 @@ static int add_free_nid(struct f2fs_sb_info *sbi, nid_t nid, bool build)
 	}
 
 	spin_lock(&nm_i->free_nid_list_lock);
-	if (radix_tree_insert(&nm_i->free_nid_root, i->nid, i)) {
+	if (__insert_to_free_nid_cache(nm_i, i)) {
 		spin_unlock(&nm_i->free_nid_list_lock);
 		radix_tree_preload_end();
 		kmem_cache_free(free_nid_slab, i);

@@ -1782,10 +1788,10 @@ static void remove_free_nid(struct f2fs_sb_info *sbi, nid_t nid)
 	bool need_free = false;
 
 	spin_lock(&nm_i->free_nid_list_lock);
-	i = __lookup_free_nid_list(nm_i, nid);
+	i = __lookup_free_nid_cache(nm_i, nid);
 	if (i && i->state == NID_NEW) {
 		__remove_nid_from_list(sbi, i, FREE_NID_LIST);
-		__del_from_free_nid_list(nm_i, i);
+		__del_from_free_nid_cache(nm_i, i);
 		need_free = true;
 	}
 	spin_unlock(&nm_i->free_nid_list_lock);

@@ -1922,10 +1928,10 @@ void alloc_nid_done(struct f2fs_sb_info *sbi, nid_t nid)
 	struct free_nid *i;
 
 	spin_lock(&nm_i->free_nid_list_lock);
-	i = __lookup_free_nid_list(nm_i, nid);
+	i = __lookup_free_nid_cache(nm_i, nid);
 	f2fs_bug_on(sbi, !i);
 	__remove_nid_from_list(sbi, i, ALLOC_NID_LIST);
-	__del_from_free_nid_list(nm_i, i);
+	__del_from_free_nid_cache(nm_i, i);
 	spin_unlock(&nm_i->free_nid_list_lock);
 
 	kmem_cache_free(free_nid_slab, i);

@@ -1944,13 +1950,13 @@ void alloc_nid_failed(struct f2fs_sb_info *sbi, nid_t nid)
 		return;
 
 	spin_lock(&nm_i->free_nid_list_lock);
-	i = __lookup_free_nid_list(nm_i, nid);
+	i = __lookup_free_nid_cache(nm_i, nid);
 	f2fs_bug_on(sbi, !i);
 
 	__remove_nid_from_list(sbi, i, ALLOC_NID_LIST);
 
 	if (!available_free_memory(sbi, FREE_NIDS)) {
-		__del_from_free_nid_list(nm_i, i);
+		__del_from_free_nid_cache(nm_i, i);
 		need_free = true;
 	} else {
 		i->state = NID_NEW;

@@ -1980,7 +1986,7 @@ int try_to_free_nids(struct f2fs_sb_info *sbi, int nr_shrink)
 			break;
 
 		__remove_nid_from_list(sbi, i, FREE_NID_LIST);
-		__del_from_free_nid_list(nm_i, i);
+		__del_from_free_nid_cache(nm_i, i);
 
 		kmem_cache_free(free_nid_slab, i);
 		nr_shrink--;

@@ -2368,7 +2374,7 @@ void destroy_node_manager(struct f2fs_sb_info *sbi)
 	spin_lock(&nm_i->free_nid_list_lock);
 	list_for_each_entry_safe(i, next_i, &nm_i->free_nid_list, list) {
 		__remove_nid_from_list(sbi, i, FREE_NID_LIST);
-		__del_from_free_nid_list(nm_i, i);
+		__del_from_free_nid_cache(nm_i, i);
 		spin_unlock(&nm_i->free_nid_list_lock);
 		kmem_cache_free(free_nid_slab, i);
 		spin_lock(&nm_i->free_nid_list_lock);
Signature · 1 line
2.10.1

------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most engaging tech sites, SlashDot.org! http://sdm.link/slashdot

author maintainer
#4 lore raw

Re: [PATCH 3/7] f2fs: rename free nid cache operation

Hi Jaegeuk,

Quoted 9 lines · Jaegeuk Kim

Hi Chao,

Quoted 3 lines · Chao Yu

From: Chao Yu <[email protected]>

Rename free nid cache operation for readability, no functionality change.

Well, I don't think this can be a *cache*, since there is no cache-related operations such as reordering by cache hit, whereas it is more likely to

This is because we do not record any nids which has been allocated to node blocks, otherwise we will recored the status of nid in the cache and also it can be hitted during lookup.

In original patches, free_nid_list is split to two separate lists: free_nid_list and alloc_nid_list, __lookup_free_nid_list looks like just search the first one, so in order to avoid misunderstanding, I proposal this change.

Anyway, what about using __{lookup,insert_to,remove_from}_nid_list instead?

Thanks,

Quoted 94 lines

be a singled one-way list.

Thanks,

Quoted 90 lines
Signed-off-by Chao Yu <[email protected]>
---
 fs/f2fs/node.c | 28 +++++++++++++++++-----------
 1 file changed, 17 insertions(+), 11 deletions(-)
fs/f2fs/node.c +16 -10
index ea9ff8c..92c9aa4 100644
@@ -1689,13 +1689,19 @@ const struct address_space_operations f2fs_node_aops = {
 #endif
 };
 
-static struct free_nid *__lookup_free_nid_list(struct f2fs_nm_info *nm_i,
+static struct free_nid *__lookup_free_nid_cache(struct f2fs_nm_info *nm_i,
 						nid_t n)
 {
 	return radix_tree_lookup(&nm_i->free_nid_root, n);
 }
 
-static void __del_from_free_nid_list(struct f2fs_nm_info *nm_i,
+static int __insert_to_free_nid_cache(struct f2fs_nm_info *nm_i,
+						struct free_nid *i)
+{
+	return radix_tree_insert(&nm_i->free_nid_root, i->nid, i);
+}
+
+static void __del_from_free_nid_cache(struct f2fs_nm_info *nm_i,
 						struct free_nid *i)
 {
 	radix_tree_delete(&nm_i->free_nid_root, i->nid);

@@ -1763,7 +1769,7 @@ static int add_free_nid(struct f2fs_sb_info *sbi, nid_t nid, bool build)
 	}
 
 	spin_lock(&nm_i->free_nid_list_lock);
-	if (radix_tree_insert(&nm_i->free_nid_root, i->nid, i)) {
+	if (__insert_to_free_nid_cache(nm_i, i)) {
 		spin_unlock(&nm_i->free_nid_list_lock);
 		radix_tree_preload_end();
 		kmem_cache_free(free_nid_slab, i);

@@ -1782,10 +1788,10 @@ static void remove_free_nid(struct f2fs_sb_info *sbi, nid_t nid)
 	bool need_free = false;
 
 	spin_lock(&nm_i->free_nid_list_lock);
-	i = __lookup_free_nid_list(nm_i, nid);
+	i = __lookup_free_nid_cache(nm_i, nid);
 	if (i && i->state == NID_NEW) {
 		__remove_nid_from_list(sbi, i, FREE_NID_LIST);
-		__del_from_free_nid_list(nm_i, i);
+		__del_from_free_nid_cache(nm_i, i);
 		need_free = true;
 	}
 	spin_unlock(&nm_i->free_nid_list_lock);

@@ -1922,10 +1928,10 @@ void alloc_nid_done(struct f2fs_sb_info *sbi, nid_t nid)
 	struct free_nid *i;
 
 	spin_lock(&nm_i->free_nid_list_lock);
-	i = __lookup_free_nid_list(nm_i, nid);
+	i = __lookup_free_nid_cache(nm_i, nid);
 	f2fs_bug_on(sbi, !i);
 	__remove_nid_from_list(sbi, i, ALLOC_NID_LIST);
-	__del_from_free_nid_list(nm_i, i);
+	__del_from_free_nid_cache(nm_i, i);
 	spin_unlock(&nm_i->free_nid_list_lock);
 
 	kmem_cache_free(free_nid_slab, i);

@@ -1944,13 +1950,13 @@ void alloc_nid_failed(struct f2fs_sb_info *sbi, nid_t nid)
 		return;
 
 	spin_lock(&nm_i->free_nid_list_lock);
-	i = __lookup_free_nid_list(nm_i, nid);
+	i = __lookup_free_nid_cache(nm_i, nid);
 	f2fs_bug_on(sbi, !i);
 
 	__remove_nid_from_list(sbi, i, ALLOC_NID_LIST);
 
 	if (!available_free_memory(sbi, FREE_NIDS)) {
-		__del_from_free_nid_list(nm_i, i);
+		__del_from_free_nid_cache(nm_i, i);
 		need_free = true;
 	} else {
 		i->state = NID_NEW;

@@ -1980,7 +1986,7 @@ int try_to_free_nids(struct f2fs_sb_info *sbi, int nr_shrink)
 			break;
 
 		__remove_nid_from_list(sbi, i, FREE_NID_LIST);
-		__del_from_free_nid_list(nm_i, i);
+		__del_from_free_nid_cache(nm_i, i);
Quoted 13 lines
Quoted 13 lines
fs/f2fs/node.c +1 -1
 		kmem_cache_free(free_nid_slab, i);
 		nr_shrink--;

@@ -2368,7 +2374,7 @@ void destroy_node_manager(struct f2fs_sb_info *sbi)
 	spin_lock(&nm_i->free_nid_list_lock);
 	list_for_each_entry_safe(i, next_i, &nm_i->free_nid_list, list) {
 		__remove_nid_from_list(sbi, i, FREE_NID_LIST);
-		__del_from_free_nid_list(nm_i, i);
+		__del_from_free_nid_cache(nm_i, i);
 		spin_unlock(&nm_i->free_nid_list_lock);
 		kmem_cache_free(free_nid_slab, i);
 		spin_lock(&nm_i->free_nid_list_lock);
Signature · 1 line
2.10.1

------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most engaging tech sites, SlashDot.org! http://sdm.link/slashdot

maintainer
#5 lore raw

Re: [PATCH 3/7] f2fs: rename free nid cache operation

Quoted 17 lines · Chao Yu

Hi Jaegeuk,

Quoted 9 lines · Jaegeuk Kim

Hi Chao,

Quoted 3 lines · Chao Yu

From: Chao Yu <[email protected]>

Rename free nid cache operation for readability, no functionality change.

Well, I don't think this can be a *cache*, since there is no cache-related operations such as reordering by cache hit, whereas it is more likely to

This is because we do not record any nids which has been allocated to node blocks, otherwise we will recored the status of nid in the cache and also it can be hitted during lookup.

Quoted 5 lines

In original patches, free_nid_list is split to two separate lists: free_nid_list and alloc_nid_list, __lookup_free_nid_list looks like just search the first one, so in order to avoid misunderstanding, I proposal this change.

Anyway, what about using __{lookup,insert_to,remove_from}_nid_list instead?

Then, how about this one?

Quoted 1 line

From 4f4b48de34ffaf94baa2065bcd5d44566f8d25b9 Mon Sep 17 00:00:00 2001

From: Jaegeuk Kim <[email protected]>
Date: Wed, 12 Oct 2016 10:09:59 -0700
Subject: [PATCH] f2fs: clean up free nid list operations

This patch cleans up to use consistent free nid list ops.

Signed-off-by Jaegeuk Kim <[email protected]>
---
 fs/f2fs/node.c | 56 ++++++++++++++++++++++++++------------------------------
 1 file changed, 26 insertions(+), 30 deletions(-)
fs/f2fs/node.c +26 -30
index 54d1c49..3d2e259 100644
@@ -1698,25 +1698,26 @@ static struct free_nid *__lookup_free_nid_list(struct f2fs_nm_info *nm_i,
 	return radix_tree_lookup(&nm_i->free_nid_root, n);
 }
 
-static void __del_from_free_nid_list(struct f2fs_nm_info *nm_i,
-						struct free_nid *i)
-{
-	radix_tree_delete(&nm_i->free_nid_root, i->nid);
-}
-
-static void __insert_nid_to_list(struct f2fs_sb_info *sbi,
-					struct free_nid *i, enum nid_list list)
+static int __insert_nid_to_list(struct f2fs_sb_info *sbi,
+			struct free_nid *i, enum nid_list list, bool new)
 {
 	struct f2fs_nm_info *nm_i = NM_I(sbi);
 
+	if (new) {
+		int err = radix_tree_insert(&nm_i->free_nid_root, i->nid, i);
+		if (err)
+			return err;
+	}
+
 	f2fs_bug_on(sbi, list == FREE_NID_LIST ? i->state != NID_NEW :
 						i->state != NID_ALLOC);
 	nm_i->nid_cnt[list]++;
 	list_add_tail(&i->list, &nm_i->nid_list[list]);
+	return 0;
 }
 
 static void __remove_nid_from_list(struct f2fs_sb_info *sbi,
-					struct free_nid *i, enum nid_list list)
+			struct free_nid *i, enum nid_list list, bool reuse)
 {
 	struct f2fs_nm_info *nm_i = NM_I(sbi);
 

@@ -1724,6 +1725,8 @@ static void __remove_nid_from_list(struct f2fs_sb_info *sbi,
 						i->state != NID_ALLOC);
 	nm_i->nid_cnt[list]--;
 	list_del(&i->list);
+	if (!reuse)
+		radix_tree_delete(&nm_i->free_nid_root, i->nid);
 }
 
 static int add_free_nid(struct f2fs_sb_info *sbi, nid_t nid, bool build)

@@ -1731,6 +1734,7 @@ static int add_free_nid(struct f2fs_sb_info *sbi, nid_t nid, bool build)
 	struct f2fs_nm_info *nm_i = NM_I(sbi);
 	struct free_nid *i;
 	struct nat_entry *ne;
+	int err;
 
 	if (!available_free_memory(sbi, FREE_NIDS))
 		return -1;

@@ -1757,15 +1761,13 @@ static int add_free_nid(struct f2fs_sb_info *sbi, nid_t nid, bool build)
 	}
 
 	spin_lock(&nm_i->nid_list_lock);
-	if (radix_tree_insert(&nm_i->free_nid_root, i->nid, i)) {
-		spin_unlock(&nm_i->nid_list_lock);
-		radix_tree_preload_end();
+	err = __insert_nid_to_list(sbi, i, FREE_NID_LIST, true);
+	spin_unlock(&nm_i->nid_list_lock);
+	radix_tree_preload_end();
+	if (err) {
 		kmem_cache_free(free_nid_slab, i);
 		return 0;
 	}
-	__insert_nid_to_list(sbi, i, FREE_NID_LIST);
-	spin_unlock(&nm_i->nid_list_lock);
-	radix_tree_preload_end();
 	return 1;
 }
 

@@ -1778,8 +1780,7 @@ static void remove_free_nid(struct f2fs_sb_info *sbi, nid_t nid)
 	spin_lock(&nm_i->nid_list_lock);
 	i = __lookup_free_nid_list(nm_i, nid);
 	if (i && i->state == NID_NEW) {
-		__remove_nid_from_list(sbi, i, FREE_NID_LIST);
-		__del_from_free_nid_list(nm_i, i);
+		__remove_nid_from_list(sbi, i, FREE_NID_LIST, false);
 		need_free = true;
 	}
 	spin_unlock(&nm_i->nid_list_lock);

@@ -1899,9 +1900,9 @@ retry:
 					struct free_nid, list);
 		*nid = i->nid;
 
-		__remove_nid_from_list(sbi, i, FREE_NID_LIST);
+		__remove_nid_from_list(sbi, i, FREE_NID_LIST, true);
 		i->state = NID_ALLOC;
-		__insert_nid_to_list(sbi, i, ALLOC_NID_LIST);
+		__insert_nid_to_list(sbi, i, ALLOC_NID_LIST, false);
 		spin_unlock(&nm_i->nid_list_lock);
 		return true;
 	}

@@ -1923,8 +1924,7 @@ void alloc_nid_done(struct f2fs_sb_info *sbi, nid_t nid)
 	spin_lock(&nm_i->nid_list_lock);
 	i = __lookup_free_nid_list(nm_i, nid);
 	f2fs_bug_on(sbi, !i);
-	__remove_nid_from_list(sbi, i, ALLOC_NID_LIST);
-	__del_from_free_nid_list(nm_i, i);
+	__remove_nid_from_list(sbi, i, ALLOC_NID_LIST, false);
 	spin_unlock(&nm_i->nid_list_lock);
 
 	kmem_cache_free(free_nid_slab, i);

@@ -1946,14 +1946,13 @@ void alloc_nid_failed(struct f2fs_sb_info *sbi, nid_t nid)
 	i = __lookup_free_nid_list(nm_i, nid);
 	f2fs_bug_on(sbi, !i);
 
-	__remove_nid_from_list(sbi, i, ALLOC_NID_LIST);
-
 	if (!available_free_memory(sbi, FREE_NIDS)) {
-		__del_from_free_nid_list(nm_i, i);
+		__remove_nid_from_list(sbi, i, ALLOC_NID_LIST, false);
 		need_free = true;
 	} else {
+		__remove_nid_from_list(sbi, i, ALLOC_NID_LIST, true);
 		i->state = NID_NEW;
-		__insert_nid_to_list(sbi, i, FREE_NID_LIST);
+		__insert_nid_to_list(sbi, i, FREE_NID_LIST, false);
 	}
 	spin_unlock(&nm_i->nid_list_lock);
 

@@ -1980,9 +1979,7 @@ int try_to_free_nids(struct f2fs_sb_info *sbi, int nr_shrink)
 				nm_i->nid_cnt[FREE_NID_LIST] <= MAX_FREE_NIDS)
 			break;
 
-		__remove_nid_from_list(sbi, i, FREE_NID_LIST);
-		__del_from_free_nid_list(nm_i, i);
-
+		__remove_nid_from_list(sbi, i, FREE_NID_LIST, false);
 		kmem_cache_free(free_nid_slab, i);
 		nr_shrink--;
 	}

@@ -2369,8 +2366,7 @@ void destroy_node_manager(struct f2fs_sb_info *sbi)
 	spin_lock(&nm_i->nid_list_lock);
 	list_for_each_entry_safe(i, next_i, &nm_i->nid_list[FREE_NID_LIST],
 									list) {
-		__remove_nid_from_list(sbi, i, FREE_NID_LIST);
-		__del_from_free_nid_list(nm_i, i);
+		__remove_nid_from_list(sbi, i, FREE_NID_LIST, false);
 		spin_unlock(&nm_i->nid_list_lock);
 		kmem_cache_free(free_nid_slab, i);
 		spin_lock(&nm_i->nid_list_lock);
Signature · 6 lines
2.8.3


------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most 
engaging tech sites, SlashDot.org! http://sdm.link/slashdot
Reviewed-by
#6 lore raw

Re: [PATCH 3/7] f2fs: rename free nid cache operation

Quoted 10 lines · Jaegeuk Kim

Then, how about this one?

Quoted 1 line

From 4f4b48de34ffaf94baa2065bcd5d44566f8d25b9 Mon Sep 17 00:00:00 2001

From: Jaegeuk Kim <[email protected]>
Date: Wed, 12 Oct 2016 10:09:59 -0700
Subject: [PATCH] f2fs: clean up free nid list operations

This patch cleans up to use consistent free nid list ops.

Signed-off-by Jaegeuk Kim <[email protected]>
Reviewed-by Chao Yu <[email protected]>

Thanks,

------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most engaging tech sites, SlashDot.org! http://sdm.link/slashdot

author maintainer
#7 lore raw

PATCH 4/7 f2fs: show pending allocated nids count in debugfs

In reply to Chao Yu

From: Chao Yu <[email protected]>

Add to show pending allocated nids count in debugfs.

Signed-off-by Chao Yu <[email protected]>
---
 fs/f2fs/debug.c | 7 ++++---
 fs/f2fs/f2fs.h  | 2 +-
 2 files changed, 5 insertions(+), 4 deletions(-)
fs/f2fs/debug.c +4 -3
index 9789138..05a70b4 100644
@@ -74,7 +74,8 @@ static void update_general_status(struct f2fs_sb_info *sbi)
 	si->dirty_nats = NM_I(sbi)->dirty_nat_cnt;
 	si->sits = MAIN_SEGS(sbi);
 	si->dirty_sits = SIT_I(sbi)->dirty_sentries;
-	si->fnids = NM_I(sbi)->free_nid_cnt;
+	si->free_nids = NM_I(sbi)->free_nid_cnt;
+	si->alloc_nids = NM_I(sbi)->alloc_nid_cnt;
 	si->bg_gc = sbi->bg_gc;
 	si->util_free = (int)(free_user_blocks(sbi) >> sbi->log_blocks_per_seg)
 		* 100 / (int)(sbi->user_block_count >> sbi->log_blocks_per_seg)

@@ -325,8 +326,8 @@ static int stat_show(struct seq_file *s, void *v)
 			   si->ndirty_imeta);
 		seq_printf(s, "  - NATs: %9d/%9d\n  - SITs: %9d/%9d\n",
 			   si->dirty_nats, si->nats, si->dirty_sits, si->sits);
-		seq_printf(s, "  - free_nids: %9d\n",
-			   si->fnids);
+		seq_printf(s, "  - free_nids: %9d, alloc_nids: %9d\n",
+			   si->free_nids, si->alloc_nids);
 		seq_puts(s, "\nDistribution of User Blocks:");
 		seq_puts(s, " [ valid | invalid | free ]\n");
 		seq_puts(s, "  [");
fs/f2fs/f2fs.h +1 -1
index d6dff15..a726e47 100644
@@ -2206,7 +2206,7 @@ struct f2fs_stat_info {
 	s64 ndirty_node, ndirty_dent, ndirty_meta, ndirty_data, ndirty_imeta;
 	s64 inmem_pages;
 	unsigned int ndirty_dirs, ndirty_files, ndirty_all;
-	int nats, dirty_nats, sits, dirty_sits, fnids;
+	int nats, dirty_nats, sits, dirty_sits, free_nids, alloc_nids;
 	int total_count, utilization;
 	int bg_gc, wb_bios;
 	int inline_xattr, inline_inode, inline_dir, orphans;
Signature · 1 line
2.10.1
maintainer
#8 lore raw

Re: [PATCH 4/7] f2fs: show pending allocated nids count in debugfs

Hi Chao,

This must be merged into original split patch (maybe representing a list array).

Thanks,

Quoted 50 lines · Chao Yu

From: Chao Yu <[email protected]>

Add to show pending allocated nids count in debugfs.

Signed-off-by Chao Yu <[email protected]>
---
 fs/f2fs/debug.c | 7 ++++---
 fs/f2fs/f2fs.h  | 2 +-
 2 files changed, 5 insertions(+), 4 deletions(-)
fs/f2fs/debug.c +4 -3
index 9789138..05a70b4 100644
@@ -74,7 +74,8 @@ static void update_general_status(struct f2fs_sb_info *sbi)
 	si->dirty_nats = NM_I(sbi)->dirty_nat_cnt;
 	si->sits = MAIN_SEGS(sbi);
 	si->dirty_sits = SIT_I(sbi)->dirty_sentries;
-	si->fnids = NM_I(sbi)->free_nid_cnt;
+	si->free_nids = NM_I(sbi)->free_nid_cnt;
+	si->alloc_nids = NM_I(sbi)->alloc_nid_cnt;
 	si->bg_gc = sbi->bg_gc;
 	si->util_free = (int)(free_user_blocks(sbi) >> sbi->log_blocks_per_seg)
 		* 100 / (int)(sbi->user_block_count >> sbi->log_blocks_per_seg)

@@ -325,8 +326,8 @@ static int stat_show(struct seq_file *s, void *v)
 			   si->ndirty_imeta);
 		seq_printf(s, "  - NATs: %9d/%9d\n  - SITs: %9d/%9d\n",
 			   si->dirty_nats, si->nats, si->dirty_sits, si->sits);
-		seq_printf(s, "  - free_nids: %9d\n",
-			   si->fnids);
+		seq_printf(s, "  - free_nids: %9d, alloc_nids: %9d\n",
+			   si->free_nids, si->alloc_nids);
 		seq_puts(s, "\nDistribution of User Blocks:");
 		seq_puts(s, " [ valid | invalid | free ]\n");
 		seq_puts(s, "  [");
fs/f2fs/f2fs.h +1 -1
index d6dff15..a726e47 100644
@@ -2206,7 +2206,7 @@ struct f2fs_stat_info {
 	s64 ndirty_node, ndirty_dent, ndirty_meta, ndirty_data, ndirty_imeta;
 	s64 inmem_pages;
 	unsigned int ndirty_dirs, ndirty_files, ndirty_all;
-	int nats, dirty_nats, sits, dirty_sits, fnids;
+	int nats, dirty_nats, sits, dirty_sits, free_nids, alloc_nids;
 	int total_count, utilization;
 	int bg_gc, wb_bios;
 	int inline_xattr, inline_inode, inline_dir, orphans;
Signature · 1 line
2.10.1
author maintainer
#9 lore raw

PATCH 5/7 f2fs: exclude free nids building and allocation

In reply to Chao Yu

From: Chao Yu <[email protected]>

During nid allocation, it needs to exclude building and allocating flow of free nids, this is because while building free nid cache, there are two
steps: a) load free nids from unused nat entries in NAT pages, b) update free nid cache by checking nat journal. The two steps should be atomical, otherwise an used nid can be allocated as free one after a) and before b).

This patch adds missing lock which covers build_free_nids in unlock_operation and f2fs_balance_fs_bg to avoid that.

Signed-off-by Chao Yu <[email protected]>
---
 fs/f2fs/node.c | 11 ++++++++---
 1 file changed, 8 insertions(+), 3 deletions(-)
fs/f2fs/node.c +8 -3
index 92c9aa4..c68e92d 100644
@@ -1824,7 +1824,7 @@ static void scan_nat_page(struct f2fs_sb_info *sbi,
 	}
 }
 
-void build_free_nids(struct f2fs_sb_info *sbi)
+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);

@@ -1878,6 +1878,13 @@ void build_free_nids(struct f2fs_sb_info *sbi)
 					nm_i->ra_nid_pages, META_NAT, false);
 }
 
+void build_free_nids(struct f2fs_sb_info *sbi)
+{
+	mutex_lock(&NM_I(sbi)->build_lock);
+	__build_free_nids(sbi);
+	mutex_unlock(&NM_I(sbi)->build_lock);
+}
+
 /*
  * If this function returns success, caller can obtain a new nid
  * from second parameter of this function.

@@ -1913,9 +1920,7 @@ retry:
 	spin_unlock(&nm_i->free_nid_list_lock);
 
 	/* Let's scan nat pages and its caches to get free nids */
-	mutex_lock(&nm_i->build_lock);
 	build_free_nids(sbi);
-	mutex_unlock(&nm_i->build_lock);
 	goto retry;
 }
Signature · 1 line
2.10.1
maintainer Applied
#10 lore raw

Re: [PATCH 5/7] f2fs: exclude free nids building and allocation

Applied.

Thanks,

Quoted 55 lines · Chao Yu

From: Chao Yu <[email protected]>

During nid allocation, it needs to exclude building and allocating flow of free nids, this is because while building free nid cache, there are two
steps: a) load free nids from unused nat entries in NAT pages, b) update free nid cache by checking nat journal. The two steps should be atomical, otherwise an used nid can be allocated as free one after a) and before b).

This patch adds missing lock which covers build_free_nids in unlock_operation and f2fs_balance_fs_bg to avoid that.

Signed-off-by Chao Yu <[email protected]>
---
 fs/f2fs/node.c | 11 ++++++++---
 1 file changed, 8 insertions(+), 3 deletions(-)
fs/f2fs/node.c +8 -3
index 92c9aa4..c68e92d 100644
@@ -1824,7 +1824,7 @@ static void scan_nat_page(struct f2fs_sb_info *sbi,
 	}
 }
 
-void build_free_nids(struct f2fs_sb_info *sbi)
+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);

@@ -1878,6 +1878,13 @@ void build_free_nids(struct f2fs_sb_info *sbi)
 					nm_i->ra_nid_pages, META_NAT, false);
 }
 
+void build_free_nids(struct f2fs_sb_info *sbi)
+{
+	mutex_lock(&NM_I(sbi)->build_lock);
+	__build_free_nids(sbi);
+	mutex_unlock(&NM_I(sbi)->build_lock);
+}
+
 /*
  * If this function returns success, caller can obtain a new nid
  * from second parameter of this function.

@@ -1913,9 +1920,7 @@ retry:
 	spin_unlock(&nm_i->free_nid_list_lock);
 
 	/* Let's scan nat pages and its caches to get free nids */
-	mutex_lock(&nm_i->build_lock);
 	build_free_nids(sbi);
-	mutex_unlock(&nm_i->build_lock);
 	goto retry;
 }
Signature · 1 line
2.10.1

------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most engaging tech sites, SlashDot.org! http://sdm.link/slashdot

author maintainer
#11 lore raw

PATCH 6/7 f2fs: don't interrupt free nids building during nid allocation

In reply to Chao Yu

From: Chao Yu <[email protected]>

Let build_free_nids support sync/async methods, in allocation flow of nids, we use synchronuous method, so that we can avoid looping in alloc_nid when free memory is low; in unblock_operations and f2fs_balance_fs_bg we use asynchronuous method in where low memory condition can interrupt us.

Signed-off-by Chao Yu <[email protected]>
---
 fs/f2fs/checkpoint.c |  2 +-
 fs/f2fs/f2fs.h       |  2 +-
 fs/f2fs/node.c       | 22 ++++++++++------------
 fs/f2fs/segment.c    |  2 +-
 4 files changed, 13 insertions(+), 15 deletions(-)
fs/f2fs/checkpoint.c +1 -1
index 7e9b504..eacc697 100644
@@ -987,7 +987,7 @@ static void unblock_operations(struct f2fs_sb_info *sbi)
 {
 	up_write(&sbi->node_write);
 
-	build_free_nids(sbi);
+	build_free_nids(sbi, false);
 	f2fs_unlock_all(sbi);
 }
fs/f2fs/f2fs.h +1 -1
index a726e47..ce34b5f 100644
@@ -2056,7 +2056,7 @@ void move_node_page(struct page *, int);
 int fsync_node_pages(struct f2fs_sb_info *, struct inode *,
 			struct writeback_control *, bool);
 int sync_node_pages(struct f2fs_sb_info *, struct writeback_control *);
-void build_free_nids(struct f2fs_sb_info *);
+void build_free_nids(struct f2fs_sb_info *, bool);
 bool alloc_nid(struct f2fs_sb_info *, nid_t *);
 void alloc_nid_done(struct f2fs_sb_info *, nid_t);
 void alloc_nid_failed(struct f2fs_sb_info *, nid_t);
fs/f2fs/node.c +10 -12
index c68e92d..0a9692e 100644
@@ -1744,9 +1744,6 @@ static int add_free_nid(struct f2fs_sb_info *sbi, nid_t nid, bool build)
 	struct free_nid *i;
 	struct nat_entry *ne;
 
-	if (!available_free_memory(sbi, FREE_NIDS))
-		return -1;
-
 	/* 0 nid should not be used */
 	if (unlikely(nid == 0))
 		return 0;

@@ -1817,14 +1814,12 @@ static void scan_nat_page(struct f2fs_sb_info *sbi,
 
 		blk_addr = le32_to_cpu(nat_blk->entries[i].block_addr);
 		f2fs_bug_on(sbi, blk_addr == NEW_ADDR);
-		if (blk_addr == NULL_ADDR) {
-			if (add_free_nid(sbi, start_nid, true) < 0)
-				break;
-		}
+		if (blk_addr == NULL_ADDR)
+			add_free_nid(sbi, start_nid, true);
 	}
 }
 
-void __build_free_nids(struct f2fs_sb_info *sbi)
+void __build_free_nids(struct f2fs_sb_info *sbi, bool sync)
 {
 	struct f2fs_nm_info *nm_i = NM_I(sbi);
 	struct curseg_info *curseg = CURSEG_I(sbi, CURSEG_HOT_DATA);

@@ -1836,6 +1831,9 @@ void __build_free_nids(struct f2fs_sb_info *sbi)
 	if (nm_i->free_nid_cnt >= NAT_ENTRY_PER_BLOCK)
 		return;
 
+	if (!sync && !available_free_memory(sbi, FREE_NIDS))
+		return;
+
 	/* readahead nat pages to be scanned */
 	ra_meta_pages(sbi, NAT_BLOCK_OFFSET(nid), FREE_NID_PAGES,
 							META_NAT, true);

@@ -1878,10 +1876,10 @@ void __build_free_nids(struct f2fs_sb_info *sbi)
 					nm_i->ra_nid_pages, META_NAT, false);
 }
 
-void build_free_nids(struct f2fs_sb_info *sbi)
+void build_free_nids(struct f2fs_sb_info *sbi, bool sync)
 {
 	mutex_lock(&NM_I(sbi)->build_lock);
-	__build_free_nids(sbi);
+	__build_free_nids(sbi, sync);
 	mutex_unlock(&NM_I(sbi)->build_lock);
 }
 

@@ -1920,7 +1918,7 @@ retry:
 	spin_unlock(&nm_i->free_nid_list_lock);
 
 	/* Let's scan nat pages and its caches to get free nids */
-	build_free_nids(sbi);
+	build_free_nids(sbi, true);
 	goto retry;
 }
 

@@ -2359,7 +2357,7 @@ int build_node_manager(struct f2fs_sb_info *sbi)
 	if (err)
 		return err;
 
-	build_free_nids(sbi);
+	build_free_nids(sbi, true);
 	return 0;
 }
fs/f2fs/segment.c +1 -1
index fc886f0..7f62dd0 100644
@@ -380,7 +380,7 @@ void f2fs_balance_fs_bg(struct f2fs_sb_info *sbi)
 	if (!available_free_memory(sbi, FREE_NIDS))
 		try_to_free_nids(sbi, MAX_FREE_NIDS);
 	else
-		build_free_nids(sbi);
+		build_free_nids(sbi, false);
 
 	/* checkpoint is the only way to shrink partial cached entries */
 	if (!available_free_memory(sbi, NAT_ENTRIES) ||
Signature · 1 line
2.10.1
author maintainer
#12 lore raw

PATCH 7/7 f2fs: avoid casted negative value as shrink count

In reply to Chao Yu

From: Chao Yu <[email protected]>

This patch makes sure it returns a positive value instead of a probable casted negative value as shrink count.

Signed-off-by Chao Yu <[email protected]>
---
 fs/f2fs/shrinker.c | 10 ++++++----
 1 file changed, 6 insertions(+), 4 deletions(-)
fs/f2fs/shrinker.c +6 -4
index 8b0a112..e1220f2 100644
@@ -21,14 +21,16 @@ static unsigned int shrinker_run_no;
 
 static unsigned long __count_nat_entries(struct f2fs_sb_info *sbi)
 {
-	return NM_I(sbi)->nat_cnt - NM_I(sbi)->dirty_nat_cnt;
+	long count = NM_I(sbi)->nat_cnt - NM_I(sbi)->dirty_nat_cnt;
+
+	return count > 0 ? count : 0;
 }
 
 static unsigned long __count_free_nids(struct f2fs_sb_info *sbi)
 {
-	if (NM_I(sbi)->free_nid_cnt > MAX_FREE_NIDS)
-		return NM_I(sbi)->free_nid_cnt - MAX_FREE_NIDS;
-	return 0;
+	long count = NM_I(sbi)->free_nid_cnt - MAX_FREE_NIDS;
+
+	return count > 0 ? count : 0;
 }
 
 static unsigned long __count_extent_cache(struct f2fs_sb_info *sbi)
Signature · 6 lines
2.10.1


------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most 
engaging tech sites, SlashDot.org! http://sdm.link/slashdot
maintainer
#13 lore raw
In reply to Chao Yu

Hi Chao,

Quoted 11 lines · Chao Yu

From: Chao Yu <[email protected]>

During free nid allocation, in order to do preallocation, we will tag free nid entry as allocated one and still leave it in free nid list, for other allocators who want to grab free nids, it needs to traverse the free nid list for lookup. It becomes overhead in scenario of allocating free nid intensively by multithreads.

This patch splits free nid list to two list: {free,alloc}_nid_list, to keep free nids and preallocated free nids separately, after that, traverse latency will be gone.

How about adding a list array like this?

enum {
ALLOC_NID_LIST,
FREE_NID_LIST,
MAX_NID_LIST,
};

struct list_head nid_list[MAX_NID_LIST];

Oh, there is another clean-up patch which defines this enum. IMO, it'd be good to write one patch including split and clean-up together.

Thanks,

Quoted 265 lines
Signed-off-by Chao Yu <[email protected]>
---
 fs/f2fs/debug.c    |  5 +++--
 fs/f2fs/f2fs.h     |  4 +++-
 fs/f2fs/node.c     | 56 ++++++++++++++++++++++++++++++++----------------------
 fs/f2fs/node.h     |  2 +-
 fs/f2fs/shrinker.c |  4 ++--
 5 files changed, 42 insertions(+), 29 deletions(-)
fs/f2fs/debug.c +3 -2
index fb245bd..9789138 100644
@@ -74,7 +74,7 @@ static void update_general_status(struct f2fs_sb_info *sbi)
 	si->dirty_nats = NM_I(sbi)->dirty_nat_cnt;
 	si->sits = MAIN_SEGS(sbi);
 	si->dirty_sits = SIT_I(sbi)->dirty_sentries;
-	si->fnids = NM_I(sbi)->fcnt;
+	si->fnids = NM_I(sbi)->free_nid_cnt;
 	si->bg_gc = sbi->bg_gc;
 	si->util_free = (int)(free_user_blocks(sbi) >> sbi->log_blocks_per_seg)
 		* 100 / (int)(sbi->user_block_count >> sbi->log_blocks_per_seg)

@@ -194,7 +194,8 @@ get_cache:
 		si->cache_mem += sizeof(struct flush_cmd_control);
 
 	/* free nids */
-	si->cache_mem += NM_I(sbi)->fcnt * sizeof(struct free_nid);
+	si->cache_mem += (NM_I(sbi)->free_nid_cnt + NM_I(sbi)->alloc_nid_cnt) *
+							sizeof(struct free_nid);
 	si->cache_mem += NM_I(sbi)->nat_cnt * sizeof(struct nat_entry);
 	si->cache_mem += NM_I(sbi)->dirty_nat_cnt *
 					sizeof(struct nat_entry_set);
fs/f2fs/f2fs.h +3 -1
index d868175..d6dff15 100644
@@ -543,8 +543,10 @@ struct f2fs_nm_info {
 	/* free node ids management */
 	struct radix_tree_root free_nid_root;/* root of the free_nid cache */
 	struct list_head free_nid_list;	/* a list for free nids */
+	struct list_head alloc_nid_list;/* a list for allocating nids */
 	spinlock_t free_nid_list_lock;	/* protect free nid list */
-	unsigned int fcnt;		/* the number of free node id */
+	unsigned int free_nid_cnt;	/* the number of free node id */
+	unsigned int alloc_nid_cnt;	/* the number of allocating node id */
 	struct mutex build_lock;	/* lock for build free nids */
 
 	/* for checkpoint */
fs/f2fs/node.c +33 -23
index 8831035..a1725a9 100644
@@ -45,7 +45,7 @@ bool available_free_memory(struct f2fs_sb_info *sbi, int type)
 	 * give 25%, 25%, 50%, 50%, 50% memory for each components respectively
 	 */
 	if (type == FREE_NIDS) {
-		mem_size = (nm_i->fcnt * sizeof(struct free_nid)) >>
+		mem_size = (nm_i->free_nid_cnt * sizeof(struct free_nid)) >>
 							PAGE_SHIFT;
 		res = mem_size < ((avail_ram * nm_i->ram_thresh / 100) >> 2);
 	} else if (type == NAT_ENTRIES) {

@@ -1740,14 +1740,15 @@ static int add_free_nid(struct f2fs_sb_info *sbi, nid_t nid, bool build)
 		return 0;
 	}
 	list_add_tail(&i->list, &nm_i->free_nid_list);
-	nm_i->fcnt++;
+	nm_i->free_nid_cnt++;
 	spin_unlock(&nm_i->free_nid_list_lock);
 	radix_tree_preload_end();
 	return 1;
 }
 
-static void remove_free_nid(struct f2fs_nm_info *nm_i, nid_t nid)
+static void remove_free_nid(struct f2fs_sb_info *sbi, nid_t nid)
 {
+	struct f2fs_nm_info *nm_i = NM_I(sbi);
 	struct free_nid *i;
 	bool need_free = false;
 

@@ -1755,7 +1756,7 @@ static void remove_free_nid(struct f2fs_nm_info *nm_i, nid_t nid)
 	i = __lookup_free_nid_list(nm_i, nid);
 	if (i && i->state == NID_NEW) {
 		__del_from_free_nid_list(nm_i, i);
-		nm_i->fcnt--;
+		nm_i->free_nid_cnt--;
 		need_free = true;
 	}
 	spin_unlock(&nm_i->free_nid_list_lock);

@@ -1797,7 +1798,7 @@ void build_free_nids(struct f2fs_sb_info *sbi)
 	nid_t nid = nm_i->next_scan_nid;
 
 	/* Enough entries */
-	if (nm_i->fcnt >= NAT_ENTRY_PER_BLOCK)
+	if (nm_i->free_nid_cnt >= NAT_ENTRY_PER_BLOCK)
 		return;
 
 	/* readahead nat pages to be scanned */

@@ -1833,7 +1834,7 @@ void build_free_nids(struct f2fs_sb_info *sbi)
 		if (addr == NULL_ADDR)
 			add_free_nid(sbi, nid, true);
 		else
-			remove_free_nid(nm_i, nid);
+			remove_free_nid(sbi, nid);
 	}
 	up_read(&curseg->journal_rwsem);
 	up_read(&nm_i->nat_tree_lock);

@@ -1862,16 +1863,16 @@ retry:
 	spin_lock(&nm_i->free_nid_list_lock);
 
 	/* We should not use stale free nids created by build_free_nids */
-	if (nm_i->fcnt && !on_build_free_nids(nm_i)) {
+	if (nm_i->free_nid_cnt && !on_build_free_nids(nm_i)) {
 		f2fs_bug_on(sbi, list_empty(&nm_i->free_nid_list));
-		list_for_each_entry(i, &nm_i->free_nid_list, list)
-			if (i->state == NID_NEW)
-				break;
-
+		i = list_first_entry(&nm_i->free_nid_list,
+					struct free_nid, list);
 		f2fs_bug_on(sbi, i->state != NID_NEW);
 		*nid = i->nid;
 		i->state = NID_ALLOC;
-		nm_i->fcnt--;
+		nm_i->free_nid_cnt--;
+		nm_i->alloc_nid_cnt++;
+		list_move_tail(&i->list, &nm_i->alloc_nid_list);
 		spin_unlock(&nm_i->free_nid_list_lock);
 		return true;
 	}

@@ -1896,6 +1897,7 @@ void alloc_nid_done(struct f2fs_sb_info *sbi, nid_t nid)
 	i = __lookup_free_nid_list(nm_i, nid);
 	f2fs_bug_on(sbi, !i || i->state != NID_ALLOC);
 	__del_from_free_nid_list(nm_i, i);
+	nm_i->alloc_nid_cnt--;
 	spin_unlock(&nm_i->free_nid_list_lock);
 
 	kmem_cache_free(free_nid_slab, i);

@@ -1917,11 +1919,14 @@ void alloc_nid_failed(struct f2fs_sb_info *sbi, nid_t nid)
 	i = __lookup_free_nid_list(nm_i, nid);
 	f2fs_bug_on(sbi, !i || i->state != NID_ALLOC);
 	if (!available_free_memory(sbi, FREE_NIDS)) {
+		nm_i->alloc_nid_cnt--;
 		__del_from_free_nid_list(nm_i, i);
 		need_free = true;
 	} else {
 		i->state = NID_NEW;
-		nm_i->fcnt++;
+		nm_i->free_nid_cnt++;
+		nm_i->alloc_nid_cnt--;
+		list_move_tail(&i->list, &nm_i->free_nid_list);
 	}
 	spin_unlock(&nm_i->free_nid_list_lock);
 

@@ -1935,7 +1940,7 @@ int try_to_free_nids(struct f2fs_sb_info *sbi, int nr_shrink)
 	struct free_nid *i, *next;
 	int nr = nr_shrink;
 
-	if (nm_i->fcnt <= MAX_FREE_NIDS)
+	if (nm_i->free_nid_cnt <= MAX_FREE_NIDS)
 		return 0;
 
 	if (!mutex_trylock(&nm_i->build_lock))

@@ -1943,13 +1948,14 @@ int try_to_free_nids(struct f2fs_sb_info *sbi, int nr_shrink)
 
 	spin_lock(&nm_i->free_nid_list_lock);
 	list_for_each_entry_safe(i, next, &nm_i->free_nid_list, list) {
-		if (nr_shrink <= 0 || nm_i->fcnt <= MAX_FREE_NIDS)
+		if (nr_shrink <= 0 || nm_i->free_nid_cnt <= MAX_FREE_NIDS)
 			break;
-		if (i->state == NID_ALLOC)
-			continue;
+
+		f2fs_bug_on(sbi, i->state == NID_ALLOC);
+
 		__del_from_free_nid_list(nm_i, i);
 		kmem_cache_free(free_nid_slab, i);
-		nm_i->fcnt--;
+		nm_i->free_nid_cnt--;
 		nr_shrink--;
 	}
 	spin_unlock(&nm_i->free_nid_list_lock);

@@ -2008,7 +2014,7 @@ recover_xnid:
 	if (unlikely(!inc_valid_node_count(sbi, inode)))
 		f2fs_bug_on(sbi, 1);
 
-	remove_free_nid(NM_I(sbi), new_xnid);
+	remove_free_nid(sbi, new_xnid);
 	get_node_info(sbi, new_xnid, &ni);
 	ni.ino = inode->i_ino;
 	set_node_addr(sbi, &ni, NEW_ADDR, false);

@@ -2038,7 +2044,7 @@ retry:
 	}
 
 	/* Should not use this inode from free nid list */
-	remove_free_nid(NM_I(sbi), ino);
+	remove_free_nid(sbi, ino);
 
 	if (!PageUptodate(ipage))
 		SetPageUptodate(ipage);

@@ -2272,7 +2278,8 @@ static int init_node_manager(struct f2fs_sb_info *sbi)
 
 	/* not used nids: 0, node, meta, (and root counted as valid node) */
 	nm_i->available_nids = nm_i->max_nid - F2FS_RESERVED_NODE_NUM;
-	nm_i->fcnt = 0;
+	nm_i->free_nid_cnt = 0;
+	nm_i->alloc_nid_cnt = 0;
 	nm_i->nat_cnt = 0;
 	nm_i->ram_thresh = DEF_RAM_THRESHOLD;
 	nm_i->ra_nid_pages = DEF_RA_NID_PAGES;

@@ -2280,6 +2287,7 @@ static int init_node_manager(struct f2fs_sb_info *sbi)
 
 	INIT_RADIX_TREE(&nm_i->free_nid_root, GFP_ATOMIC);
 	INIT_LIST_HEAD(&nm_i->free_nid_list);
+	INIT_LIST_HEAD(&nm_i->alloc_nid_list);
 	INIT_RADIX_TREE(&nm_i->nat_root, GFP_NOIO);
 	INIT_RADIX_TREE(&nm_i->nat_set_root, GFP_NOIO);
 	INIT_LIST_HEAD(&nm_i->nat_entries);

@@ -2334,12 +2342,14 @@ void destroy_node_manager(struct f2fs_sb_info *sbi)
 	list_for_each_entry_safe(i, next_i, &nm_i->free_nid_list, list) {
 		f2fs_bug_on(sbi, i->state == NID_ALLOC);
 		__del_from_free_nid_list(nm_i, i);
-		nm_i->fcnt--;
+		nm_i->free_nid_cnt--;
 		spin_unlock(&nm_i->free_nid_list_lock);
 		kmem_cache_free(free_nid_slab, i);
 		spin_lock(&nm_i->free_nid_list_lock);
 	}
-	f2fs_bug_on(sbi, nm_i->fcnt);
+	f2fs_bug_on(sbi, nm_i->free_nid_cnt);
+	f2fs_bug_on(sbi, nm_i->alloc_nid_cnt);
+	f2fs_bug_on(sbi, !list_empty(&nm_i->alloc_nid_list));
 	spin_unlock(&nm_i->free_nid_list_lock);
 
 	/* destroy nat cache */
fs/f2fs/node.h +1 -1
index 868bec6..66928d7 100644
@@ -170,7 +170,7 @@ static inline void next_free_nid(struct f2fs_sb_info *sbi, nid_t *nid)
 	struct free_nid *fnid;
 
 	spin_lock(&nm_i->free_nid_list_lock);
-	if (nm_i->fcnt <= 0) {
+	if (nm_i->free_nid_cnt <= 0) {
 		spin_unlock(&nm_i->free_nid_list_lock);
 		return;
 	}
fs/f2fs/shrinker.c +2 -2
index 46c9154..8b0a112 100644
@@ -26,8 +26,8 @@ static unsigned long __count_nat_entries(struct f2fs_sb_info *sbi)
 
 static unsigned long __count_free_nids(struct f2fs_sb_info *sbi)
 {
-	if (NM_I(sbi)->fcnt > MAX_FREE_NIDS)
-		return NM_I(sbi)->fcnt - MAX_FREE_NIDS;
+	if (NM_I(sbi)->free_nid_cnt > MAX_FREE_NIDS)
+		return NM_I(sbi)->free_nid_cnt - MAX_FREE_NIDS;
 	return 0;
 }
Signature · 1 line
2.10.1

------------------------------------------------------------------------------
Check out the vibrant tech community on one of the world's most engaging tech sites, SlashDot.org! http://sdm.link/slashdot

#14 lore raw

Hi Jaegeuk,

Quoted 23 lines · Jaegeuk Kim

Hi Chao,

Quoted 11 lines · Chao Yu

From: Chao Yu <[email protected]>

During free nid allocation, in order to do preallocation, we will tag free nid entry as allocated one and still leave it in free nid list, for other allocators who want to grab free nids, it needs to traverse the free nid list for lookup. It becomes overhead in scenario of allocating free nid intensively by multithreads.

This patch splits free nid list to two list: {free,alloc}_nid_list, to keep free nids and preallocated free nids separately, after that, traverse latency will be gone.

How about adding a list array like this?

enum {
ALLOC_NID_LIST,
FREE_NID_LIST,
MAX_NID_LIST,
};

Quoted 4 lines

struct list_head nid_list[MAX_NID_LIST];

Oh, there is another clean-up patch which defines this enum. IMO, it'd be good to write one patch including split and clean-up together.

OK, let me merge those patches as you reminded.

thanks,