f2fs: remove vlist in extent node

PATCH In review Chao Yu 2 participants 4 messages Jan 27, 2016 – Jan 28, 2016 F2FS file system

Share & tools

Chao Yu

author

2016-01-27 10:04 UTC #0 lore raw

PATCH 1/1 f2fs: remove vlist in extent node

For speeding up shrinking extent nodes from lru list, we introduced additional list node named 'vlist' for each extent node, in order to link them into victim list and then do the shrink job by traversing the list, but it makes memory footprint overhead for extent cache.

We change the policy of lru list shrinking to:
1) lock lru list's lock
2) trylock extent tree's lock
3) remove extent node from lru list
4) unlock lru list's lock
5) do shrink
6) repeat 1) to 5)

extent node size:
32-bit machine: decrease from 44 bytes to 36 bytes 64-bit machine: decrease from 80 bytes to 64 bytes

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

---
 fs/f2fs/extent_cache.c | 59 ++++++++++++++++++++------------------------------
 fs/f2fs/f2fs.h         |  1 -
 2 files changed, 24 insertions(+), 36 deletions(-)

fs/f2fs/extent_cache.c +24 ~~-35~~

index cf949bb..0cfd13c 100644
@@ -33,7 +33,6 @@ static struct extent_node *__attach_extent_node(struct f2fs_sb_info *sbi,
 
 	en->ei = *ei;
 	INIT_LIST_HEAD(&en->list);
-	INIT_LIST_HEAD(&en->vlist);
 	en->et = et;
 
 	rb_link_node(&en->rb_node, parent, p);

@@ -47,6 +46,9 @@ static void __detach_extent_node(struct f2fs_sb_info *sbi,
 				struct extent_tree *et, struct extent_node *en)
 {
 	rb_erase(&en->rb_node, &et->root);
+	atomic_dec(&et->node_cnt);
+	atomic_dec(&sbi->total_ext_node);
+	kmem_cache_free(extent_node_slab, en);
 
 	if (et->cached_en == en)
 		et->cached_en = NULL;

@@ -61,21 +63,12 @@ static void __detach_extent_node(struct f2fs_sb_info *sbi,
 static void __release_extent_node(struct f2fs_sb_info *sbi,
 			struct extent_tree *et, struct extent_node *en)
 {
-	bool need_free = false;
-
 	spin_lock(&sbi->extent_lock);
-	if (!list_empty(&en->list)) {
-		list_del_init(&en->list);
-		need_free = true;
-	}
+	f2fs_bug_on(sbi, list_empty(&en->list));
+	list_del_init(&en->list);
 	spin_unlock(&sbi->extent_lock);
 
 	__detach_extent_node(sbi, et, en);
-	if (need_free) {
-		atomic_dec(&et->node_cnt);
-		atomic_dec(&sbi->total_ext_node);
-		kmem_cache_free(extent_node_slab, en);
-	}
 }
 
 static struct extent_tree *__grab_extent_tree(struct inode *inode)

@@ -214,8 +207,6 @@ bool f2fs_init_extent_tree(struct inode *inode, struct f2fs_extent *i_ext)
 	en = __init_extent_tree(sbi, et, &ei);
 	if (en) {
 		spin_lock(&sbi->extent_lock);
-		f2fs_bug_on(sbi, !list_empty(&en->list) ||
-				!list_empty(&en->vlist));
 		list_add_tail(&en->list, &sbi->extent_list);
 		spin_unlock(&sbi->extent_lock);
 	}

@@ -251,7 +242,6 @@ static bool f2fs_lookup_extent_tree(struct inode *inode, pgoff_t pgofs,
 		*ei = en->ei;
 		spin_lock(&sbi->extent_lock);
 		if (!list_empty(&en->list)) {
-			f2fs_bug_on(sbi, !list_empty(&en->vlist));
 			list_move_tail(&en->list, &sbi->extent_list);
 			et->cached_en = en;
 		}

@@ -376,7 +366,6 @@ static struct extent_node *__try_merge_extent_node(struct f2fs_sb_info *sbi,
 
 	spin_lock(&sbi->extent_lock);
 	if (!list_empty(&en->list)) {
-		f2fs_bug_on(sbi, !list_empty(&en->vlist));
 		list_move_tail(&en->list, &sbi->extent_list);
 		et->cached_en = en;
 	}

@@ -419,7 +408,6 @@ do_insert:
 
 	/* update in global extent list */
 	spin_lock(&sbi->extent_lock);
-	f2fs_bug_on(sbi, !list_empty(&en->list) || !list_empty(&en->vlist));
 	list_add_tail(&en->list, &sbi->extent_list);
 	et->cached_en = en;
 	spin_unlock(&sbi->extent_lock);

@@ -552,11 +540,9 @@ static unsigned int f2fs_update_extent_tree_range(struct inode *inode,
 unsigned int f2fs_shrink_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink)
 {
 	struct extent_tree *et, *next;
-	struct extent_node *en, *tmp;
+	struct extent_node *en;
 	unsigned int node_cnt = 0, tree_cnt = 0;
 	int remained;
-	bool do_free = false;
-	LIST_HEAD(victim_extent_node_list);
 
 	if (!test_opt(sbi, EXTENT_CACHE))
 		return 0;

@@ -596,28 +582,31 @@ free_node:
 	remained = nr_shrink - (node_cnt + tree_cnt);
 
 	spin_lock(&sbi->extent_lock);
-	list_for_each_entry_safe(en, tmp, &sbi->extent_list, list) {
-		if (!remained--)
+	for (; remained > 0; remained--) {
+		if (list_empty(&sbi->extent_list))
 			break;
+		en = list_first_entry(&sbi->extent_list,
+					struct extent_node, list);
+		et = en->et;
+		if (!write_trylock(&et->lock)) {
+			/* refresh this extent node's position in extent list */
+			list_move_tail(&en->list, &sbi->extent_list);
+			continue;
+		}
+
 		list_del_init(&en->list);
-		list_move_tail(&en->vlist, &victim_extent_node_list);
-		do_free = true;
-	}
-	spin_unlock(&sbi->extent_lock);
+		spin_unlock(&sbi->extent_lock);
 
-	if (do_free == false)
-		goto unlock_out;
+		__detach_extent_node(sbi, et, en);
 
-	list_for_each_entry_safe(en, tmp, &victim_extent_node_list, vlist) {
-		write_lock(&en->et->lock);
-		__detach_extent_node(sbi, en->et, en);
-		atomic_dec(&en->et->node_cnt);
-		atomic_dec(&sbi->total_ext_node);
-		write_unlock(&en->et->lock);
-		kmem_cache_free(extent_node_slab, en);
+		write_unlock(&et->lock);
 		node_cnt++;
+
 		cond_resched();
+		spin_lock(&sbi->extent_lock);
 	}
+	spin_unlock(&sbi->extent_lock);
+
 unlock_out:
 	up_write(&sbi->extent_tree_lock);
 out:

fs/f2fs/f2fs.h +0 -1

index 4812c47..4e7eab9 100644
@@ -353,7 +353,6 @@ struct extent_info {
 struct extent_node {
 	struct rb_node rb_node;		/* rb node located in rb-tree */
 	struct list_head list;		/* node in global extent list of sbi */
-	struct list_head vlist;		/* node in local victim list */
 	struct extent_info ei;		/* extent info */
 	struct extent_tree *et;		/* extent tree pointer */
 };

Signature · 1 line

2.7.0.2.g1b0b6dd

Jaegeuk Kim

maintainer

2016-01-27 21:38 UTC #1 lore raw

Hi Chao,

Hmm. The original patch was just going under testing, and we couldn't post them since there is a kernel panic issue.
This patch seems quite better approach, so I think we can integrate both of the patches together.

So, how about this patch?
Hope you don't mind this.

Thanks,

Quoted 1 line

From a7844e0438db9ea9d12b7c0c40b655c3371bd6c9 Mon Sep 17 00:00:00 2001

From: Hou Pengyang <[email protected]>
Date: Tue, 26 Jan 2016 12:56:26 +0000
Subject: [PATCH] f2fs: improve shrink performance of extent nodes

On the worst case, we need to scan the whole radix tree and every rb-tree to free the victimed extent_nodes when shrinking.

Pengyang initially introduced a victim_list to record the victimed extent_nodes, and free these extent_nodes by just scanning a list.

Later, Chao Yu enhances the original patch to improve memory footprint by removing victim list.

The policy of lru list shrinking becomes:
1) lock lru list's lock
2) trylock extent tree's lock
3) remove extent node from lru list
4) unlock lru list's lock
5) do shrink
6) repeat 1) to 5)

Signed-off-by Hou Pengyang <[email protected]>

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

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

---
 fs/f2fs/extent_cache.c | 87 +++++++++++++++++++++-----------------------------
 fs/f2fs/f2fs.h         |  1 +
 2 files changed, 37 insertions(+), 51 deletions(-)

fs/f2fs/extent_cache.c +36 ~~-51~~

index aae99f2..759b1b1 100644
@@ -33,6 +33,7 @@ static struct extent_node *__attach_extent_node(struct f2fs_sb_info *sbi,
 
 	en->ei = *ei;
 	INIT_LIST_HEAD(&en->list);
+	en->et = et;
 
 	rb_link_node(&en->rb_node, parent, p);
 	rb_insert_color(&en->rb_node, &et->root);

@@ -63,8 +64,8 @@ static void __release_extent_node(struct f2fs_sb_info *sbi,
 			struct extent_tree *et, struct extent_node *en)
 {
 	spin_lock(&sbi->extent_lock);
-	if (!list_empty(&en->list))
-		list_del_init(&en->list);
+	f2fs_bug_on(sbi, list_empty(&en->list));
+	list_del_init(&en->list);
 	spin_unlock(&sbi->extent_lock);
 
 	__detach_extent_node(sbi, et, en);

@@ -147,7 +148,7 @@ static struct extent_node *__init_extent_tree(struct f2fs_sb_info *sbi,
 }
 
 static unsigned int __free_extent_tree(struct f2fs_sb_info *sbi,
-					struct extent_tree *et, bool free_all)
+					struct extent_tree *et)
 {
 	struct rb_node *node, *next;
 	struct extent_node *en;

@@ -157,11 +158,7 @@ static unsigned int __free_extent_tree(struct f2fs_sb_info *sbi,
 	while (node) {
 		next = rb_next(node);
 		en = rb_entry(node, struct extent_node, rb_node);
-
-		if (free_all)
-			__release_extent_node(sbi, et, en);
-		else if (list_empty(&en->list))
-			__detach_extent_node(sbi, et, en);
+		__release_extent_node(sbi, et, en);
 		node = next;
 	}

@@ -532,7 +529,7 @@ static unsigned int f2fs_update_extent_tree_range(struct inode *inode,
 	}
 
 	if (is_inode_flag_set(F2FS_I(inode), FI_NO_EXTENT))
-		__free_extent_tree(sbi, et, true);
+		__free_extent_tree(sbi, et);
 
 	write_unlock(&et->lock);

@@ -541,14 +538,10 @@ static unsigned int f2fs_update_extent_tree_range(struct inode *inode,
 
 unsigned int f2fs_shrink_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink)
 {
-	struct extent_tree *treevec[EXT_TREE_VEC_SIZE];
 	struct extent_tree *et, *next;
-	struct extent_node *en, *tmp;
-	unsigned long ino = F2FS_ROOT_INO(sbi);
-	unsigned int found;
+	struct extent_node *en;
 	unsigned int node_cnt = 0, tree_cnt = 0;
 	int remained;
-	bool do_free = false;
 
 	if (!test_opt(sbi, EXTENT_CACHE))
 		return 0;

@@ -561,11 +554,11 @@ unsigned int f2fs_shrink_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink)
 
 	/* 1. remove unreferenced extent tree */
 	list_for_each_entry_safe(et, next, &sbi->zombie_list, list) {
-		if (atomic_read(&et->node_cnt)) {
-			write_lock(&et->lock);
-			node_cnt += __free_extent_tree(sbi, et, true);
-			write_unlock(&et->lock);
-		}
+		write_lock(&et->lock);
+		node_cnt += __free_extent_tree(sbi, et);
+		write_unlock(&et->lock);
+		if (atomic_read(&et->node_cnt) > 0)
+			goto unlock_out;
 
 		list_del_init(&et->list);
 		radix_tree_delete(&sbi->extent_tree_root, et->ino);

@@ -587,42 +580,29 @@ free_node:
 	remained = nr_shrink - (node_cnt + tree_cnt);
 
 	spin_lock(&sbi->extent_lock);
-	list_for_each_entry_safe(en, tmp, &sbi->extent_list, list) {
-		if (!remained--)
+	for (; remained > 0; remained--) {
+		if (list_empty(&sbi->extent_list))
 			break;
-		list_del_init(&en->list);
-		do_free = true;
-	}
-	spin_unlock(&sbi->extent_lock);
-
-	if (do_free == false)
-		goto unlock_out;
-
-	/*
-	 * reset ino for searching victims from beginning of global extent tree.
-	 */
-	ino = F2FS_ROOT_INO(sbi);
-
-	while ((found = radix_tree_gang_lookup(&sbi->extent_tree_root,
-				(void **)treevec, ino, EXT_TREE_VEC_SIZE))) {
-		unsigned i;
-
-		ino = treevec[found - 1]->ino + 1;
-		for (i = 0; i < found; i++) {
-			struct extent_tree *et = treevec[i];
+		en = list_first_entry(&sbi->extent_list,
+					struct extent_node, list);
+		et = en->et;
+		if (!write_trylock(&et->lock)) {
+			/* refresh this extent node's position in extent list */
+			list_move_tail(&en->list, &sbi->extent_list);
+			continue;
+		}
 
-			if (!atomic_read(&et->node_cnt))
-				continue;
+		list_del_init(&en->list);
+		spin_unlock(&sbi->extent_lock);
 
-			if (write_trylock(&et->lock)) {
-				node_cnt += __free_extent_tree(sbi, et, false);
-				write_unlock(&et->lock);
-			}
+		__detach_extent_node(sbi, et, en);
 
-			if (node_cnt + tree_cnt >= nr_shrink)
-				goto unlock_out;
-		}
+		write_unlock(&et->lock);
+		node_cnt++;
+		spin_lock(&sbi->extent_lock);
 	}
+	spin_unlock(&sbi->extent_lock);
+
 unlock_out:
 	up_write(&sbi->extent_tree_lock);
 out:

@@ -641,7 +621,7 @@ unsigned int f2fs_destroy_extent_node(struct inode *inode)
 		return 0;
 
 	write_lock(&et->lock);
-	node_cnt = __free_extent_tree(sbi, et, true);
+	node_cnt = __free_extent_tree(sbi, et);
 	write_unlock(&et->lock);
 
 	return node_cnt;

@@ -666,10 +646,15 @@ void f2fs_destroy_extent_tree(struct inode *inode)
 	}
 
 	/* free all extent info belong to this extent tree */
+free_more:
 	node_cnt = f2fs_destroy_extent_node(inode);
 
 	/* delete extent tree entry in radix tree */
 	down_write(&sbi->extent_tree_lock);
+	if (atomic_read(&et->node_cnt) > 0) {
+		up_write(&sbi->extent_tree_lock);
+		goto free_more;
+	}
 	f2fs_bug_on(sbi, atomic_read(&et->node_cnt));
 	radix_tree_delete(&sbi->extent_tree_root, inode->i_ino);
 	kmem_cache_free(extent_tree_slab, et);

fs/f2fs/f2fs.h +1 -0

index c4e723b..4e7eab9 100644
@@ -354,6 +354,7 @@ struct extent_node {
 	struct rb_node rb_node;		/* rb node located in rb-tree */
 	struct list_head list;		/* node in global extent list of sbi */
 	struct extent_info ei;		/* extent info */
+	struct extent_tree *et;		/* extent tree pointer */
 };
 
 struct extent_tree {

Signature · 9 lines

2.6.3


------------------------------------------------------------------------------
Site24x7 APM Insight: Get Deep Visibility into Application Performance
APM + Mobile APM + RUM: Monitor 3 App instances at just $35/Month
Monitor end-to-end web transactions and take corrective actions now
Troubleshoot faster and improve end-user experience. Signup Now!
http://pubads.g.doubleclick.net/gampad/clk?id=267308311&iu=/4140

Chao Yu

author

2016-01-28 01:36 UTC #2 lore raw

Hi Jaegeuk,

Quoted 9 lines

-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
Sent: Thursday, January 28, 2016 5:38 AM
To: Chao Yu
Cc: [email protected]; [email protected]
Subject: Re: [PATCH] f2fs: remove vlist in extent node
Hi Chao,

Quoted 7 lines

Hmm. The original patch was just going under testing, and we couldn't post them since there is a kernel panic issue.
This patch seems quite better approach, so I think we can integrate both of the patches together.
So, how about this patch?
Hope you don't mind this.

No objection. :)

Quoted 104 lines

Thanks,

From a7844e0438db9ea9d12b7c0c40b655c3371bd6c9 Mon Sep 17 00:00:00 2001
From: Hou Pengyang <[email protected]>
Date: Tue, 26 Jan 2016 12:56:26 +0000
Subject: [PATCH] f2fs: improve shrink performance of extent nodes

On the worst case, we need to scan the whole radix tree and every rb-tree to free the victimed extent_nodes when shrinking.

Pengyang initially introduced a victim_list to record the victimed extent_nodes, and free these extent_nodes by just scanning a list.

Later, Chao Yu enhances the original patch to improve memory footprint by removing victim list.

The policy of lru list shrinking becomes:
1) lock lru list's lock
2) trylock extent tree's lock
3) remove extent node from lru list
4) unlock lru list's lock
5) do shrink
6) repeat 1) to 5)

Signed-off-by Hou Pengyang <[email protected]>

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

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

---
 fs/f2fs/extent_cache.c | 87 +++++++++++++++++++++-----------------------------
 fs/f2fs/f2fs.h         |  1 +
 2 files changed, 37 insertions(+), 51 deletions(-)

fs/f2fs/extent_cache.c +7 ~~-14~~

index aae99f2..759b1b1 100644
@@ -33,6 +33,7 @@ static struct extent_node *__attach_extent_node(struct f2fs_sb_info *sbi,
 
 	en->ei = *ei;
 	INIT_LIST_HEAD(&en->list);
+	en->et = et;
 
 	rb_link_node(&en->rb_node, parent, p);
 	rb_insert_color(&en->rb_node, &et->root);

@@ -63,8 +64,8 @@ static void __release_extent_node(struct f2fs_sb_info *sbi,
 			struct extent_tree *et, struct extent_node *en)
 {
 	spin_lock(&sbi->extent_lock);
-	if (!list_empty(&en->list))
-		list_del_init(&en->list);
+	f2fs_bug_on(sbi, list_empty(&en->list));
+	list_del_init(&en->list);
 	spin_unlock(&sbi->extent_lock);
 
 	__detach_extent_node(sbi, et, en);

@@ -147,7 +148,7 @@ static struct extent_node *__init_extent_tree(struct f2fs_sb_info *sbi,
 }
 
 static unsigned int __free_extent_tree(struct f2fs_sb_info *sbi,
-					struct extent_tree *et, bool free_all)
+					struct extent_tree *et)
 {
 	struct rb_node *node, *next;
 	struct extent_node *en;

@@ -157,11 +158,7 @@ static unsigned int __free_extent_tree(struct f2fs_sb_info *sbi,
 	while (node) {
 		next = rb_next(node);
 		en = rb_entry(node, struct extent_node, rb_node);
-
-		if (free_all)
-			__release_extent_node(sbi, et, en);
-		else if (list_empty(&en->list))
-			__detach_extent_node(sbi, et, en);
+		__release_extent_node(sbi, et, en);
 		node = next;
 	}

@@ -532,7 +529,7 @@ static unsigned int f2fs_update_extent_tree_range(struct inode *inode,
 	}
 
 	if (is_inode_flag_set(F2FS_I(inode), FI_NO_EXTENT))
-		__free_extent_tree(sbi, et, true);
+		__free_extent_tree(sbi, et);
 
 	write_unlock(&et->lock);

@@ -541,14 +538,10 @@ static unsigned int f2fs_update_extent_tree_range(struct inode *inode,
 
 unsigned int f2fs_shrink_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink)
 {
-	struct extent_tree *treevec[EXT_TREE_VEC_SIZE];
 	struct extent_tree *et, *next;
-	struct extent_node *en, *tmp;
-	unsigned long ino = F2FS_ROOT_INO(sbi);
-	unsigned int found;
+	struct extent_node *en;
 	unsigned int node_cnt = 0, tree_cnt = 0;
 	int remained;
-	bool do_free = false;
 
 	if (!test_opt(sbi, EXTENT_CACHE))
 		return 0;

fs/f2fs/extent_cache.c unsigned int f2fs_shrink_extent_tree(struct f2fs_sb_info *sbi, int · line 565

Quoted 5 lines

fs/f2fs/extent_cache.c +0 -1

@@ -561,11 +554,11 @@ unsigned int f2fs_shrink_extent_tree(struct f2fs_sb_info *sbi, int
 nr_shrink)
 
 	/* 1. remove unreferenced extent tree */
 	list_for_each_entry_safe(et, next, &sbi->zombie_list, list) {
-		if (atomic_read(&et->node_cnt)) {

This is used to avoid lock overhead if there are no nodes in the tree. Why should we change this?

Quoted 85 lines

fs/f2fs/extent_cache.c +5 -4

-			write_lock(&et->lock);
-			node_cnt += __free_extent_tree(sbi, et, true);
-			write_unlock(&et->lock);
-		}
+		write_lock(&et->lock);
+		node_cnt += __free_extent_tree(sbi, et);
+		write_unlock(&et->lock);
+		if (atomic_read(&et->node_cnt) > 0)
+			goto unlock_out;
 
 		list_del_init(&et->list);

fs/f2fs/extent_cache.c +19 ~~-32~~

 		radix_tree_delete(&sbi->extent_tree_root, et->ino);

@@ -587,42 +580,29 @@ free_node:
 	remained = nr_shrink - (node_cnt + tree_cnt);
 
 	spin_lock(&sbi->extent_lock);
-	list_for_each_entry_safe(en, tmp, &sbi->extent_list, list) {
-		if (!remained--)
+	for (; remained > 0; remained--) {
+		if (list_empty(&sbi->extent_list))
 			break;
-		list_del_init(&en->list);
-		do_free = true;
-	}
-	spin_unlock(&sbi->extent_lock);
-
-	if (do_free == false)
-		goto unlock_out;
-
-	/*
-	 * reset ino for searching victims from beginning of global extent tree.
-	 */
-	ino = F2FS_ROOT_INO(sbi);
-
-	while ((found = radix_tree_gang_lookup(&sbi->extent_tree_root,
-				(void **)treevec, ino, EXT_TREE_VEC_SIZE))) {
-		unsigned i;
-
-		ino = treevec[found - 1]->ino + 1;
-		for (i = 0; i < found; i++) {
-			struct extent_tree *et = treevec[i];
+		en = list_first_entry(&sbi->extent_list,
+					struct extent_node, list);
+		et = en->et;
+		if (!write_trylock(&et->lock)) {
+			/* refresh this extent node's position in extent list */
+			list_move_tail(&en->list, &sbi->extent_list);
+			continue;
+		}
 
-			if (!atomic_read(&et->node_cnt))
-				continue;
+		list_del_init(&en->list);
+		spin_unlock(&sbi->extent_lock);
 
-			if (write_trylock(&et->lock)) {
-				node_cnt += __free_extent_tree(sbi, et, false);
-				write_unlock(&et->lock);
-			}
+		__detach_extent_node(sbi, et, en);
 
-			if (node_cnt + tree_cnt >= nr_shrink)
-				goto unlock_out;
-		}
+		write_unlock(&et->lock);
+		node_cnt++;
+		spin_lock(&sbi->extent_lock);
 	}
+	spin_unlock(&sbi->extent_lock);
+
 unlock_out:
 	up_write(&sbi->extent_tree_lock);
 out:

@@ -641,7 +621,7 @@ unsigned int f2fs_destroy_extent_node(struct inode *inode)
 		return 0;
 
 	write_lock(&et->lock);
-	node_cnt = __free_extent_tree(sbi, et, true);
+	node_cnt = __free_extent_tree(sbi, et);
 	write_unlock(&et->lock);
 
 	return node_cnt;

@@ -666,10 +646,15 @@ void f2fs_destroy_extent_tree(struct inode *inode)
 	}

fs/f2fs/extent_cache.c void f2fs_destroy_extent_tree(struct inode *inode) · line 657

Quoted 10 lines

fs/f2fs/extent_cache.c +5 -0

 	/* free all extent info belong to this extent tree */
+free_more:
 	node_cnt = f2fs_destroy_extent_node(inode);
 
 	/* delete extent tree entry in radix tree */
 	down_write(&sbi->extent_tree_lock);
+	if (atomic_read(&et->node_cnt) > 0) {
+		up_write(&sbi->extent_tree_lock);
+		goto free_more;
+	}

If I understand correctly here, there is no race condition between shrinker and destroyer, so it would be safe to usef2fs_bug_on(, et->node_cnt)?

Thanks,

Quoted 17 lines

fs/f2fs/extent_cache.c +0 -0

 	f2fs_bug_on(sbi, atomic_read(&et->node_cnt));
 	radix_tree_delete(&sbi->extent_tree_root, inode->i_ino);
 	kmem_cache_free(extent_tree_slab, et);

fs/f2fs/f2fs.h +1 -1

index c4e723b..4e7eab9 100644
@@ -354,6 +354,7 @@ struct extent_node {
 	struct rb_node rb_node;		/* rb node located in rb-tree */
 	struct list_head list;		/* node in global extent list of sbi */
 	struct extent_info ei;		/* extent info */
+	struct extent_tree *et;		/* extent tree pointer */
 };
 
 struct extent_tree {
--

2.6.3

Jaegeuk Kim

maintainer

2016-01-28 02:31 UTC #3 lore raw

Hi Chao,

Quoted 16 lines · Chao Yu

Hi Jaegeuk,
Quoted 14 lines
-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
Sent: Thursday, January 28, 2016 5:38 AM
To: Chao Yu
Cc: [email protected]; [email protected]
Subject: Re: [PATCH] f2fs: remove vlist in extent node
Hi Chao,
Hmm. The original patch was just going under testing, and we couldn't post them since there is a kernel panic issue.
This patch seems quite better approach, so I think we can integrate both of the patches together.

Quoted 4 lines

Quoted 2 lines
So, how about this patch?
Hope you don't mind this.
No objection. :)

Cool. :)

Let me double check your comments below.

Thanks,

Quoted 233 lines

Quoted 105 lines

Thanks,

On the worst case, we need to scan the whole radix tree and every rb-tree to free the victimed extent_nodes when shrinking.

Pengyang initially introduced a victim_list to record the victimed extent_nodes, and free these extent_nodes by just scanning a list.

Later, Chao Yu enhances the original patch to improve memory footprint by removing victim list.

The policy of lru list shrinking becomes:
1) lock lru list's lock
2) trylock extent tree's lock
3) remove extent node from lru list
4) unlock lru list's lock
5) do shrink
6) repeat 1) to 5)

Signed-off-by Hou Pengyang <[email protected]>

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

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

---
 fs/f2fs/extent_cache.c | 87 +++++++++++++++++++++-----------------------------
 fs/f2fs/f2fs.h         |  1 +
 2 files changed, 37 insertions(+), 51 deletions(-)

fs/f2fs/extent_cache.c +7 ~~-14~~

index aae99f2..759b1b1 100644
@@ -33,6 +33,7 @@ static struct extent_node *__attach_extent_node(struct f2fs_sb_info *sbi,
 
 	en->ei = *ei;
 	INIT_LIST_HEAD(&en->list);
+	en->et = et;
 
 	rb_link_node(&en->rb_node, parent, p);
 	rb_insert_color(&en->rb_node, &et->root);

@@ -63,8 +64,8 @@ static void __release_extent_node(struct f2fs_sb_info *sbi,
 			struct extent_tree *et, struct extent_node *en)
 {
 	spin_lock(&sbi->extent_lock);
-	if (!list_empty(&en->list))
-		list_del_init(&en->list);
+	f2fs_bug_on(sbi, list_empty(&en->list));
+	list_del_init(&en->list);
 	spin_unlock(&sbi->extent_lock);
 
 	__detach_extent_node(sbi, et, en);

@@ -147,7 +148,7 @@ static struct extent_node *__init_extent_tree(struct f2fs_sb_info *sbi,
 }
 
 static unsigned int __free_extent_tree(struct f2fs_sb_info *sbi,
-					struct extent_tree *et, bool free_all)
+					struct extent_tree *et)
 {
 	struct rb_node *node, *next;
 	struct extent_node *en;

@@ -157,11 +158,7 @@ static unsigned int __free_extent_tree(struct f2fs_sb_info *sbi,
 	while (node) {
 		next = rb_next(node);
 		en = rb_entry(node, struct extent_node, rb_node);
-
-		if (free_all)
-			__release_extent_node(sbi, et, en);
-		else if (list_empty(&en->list))
-			__detach_extent_node(sbi, et, en);
+		__release_extent_node(sbi, et, en);
 		node = next;
 	}

@@ -532,7 +529,7 @@ static unsigned int f2fs_update_extent_tree_range(struct inode *inode,
 	}
 
 	if (is_inode_flag_set(F2FS_I(inode), FI_NO_EXTENT))
-		__free_extent_tree(sbi, et, true);
+		__free_extent_tree(sbi, et);
 
 	write_unlock(&et->lock);

@@ -541,14 +538,10 @@ static unsigned int f2fs_update_extent_tree_range(struct inode *inode,
 
 unsigned int f2fs_shrink_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink)
 {
-	struct extent_tree *treevec[EXT_TREE_VEC_SIZE];
 	struct extent_tree *et, *next;
-	struct extent_node *en, *tmp;
-	unsigned long ino = F2FS_ROOT_INO(sbi);
-	unsigned int found;
+	struct extent_node *en;
 	unsigned int node_cnt = 0, tree_cnt = 0;
 	int remained;
-	bool do_free = false;
 
 	if (!test_opt(sbi, EXTENT_CACHE))
 		return 0;

fs/f2fs/extent_cache.c unsigned int f2fs_shrink_extent_tree(struct f2fs_sb_info *sbi, int · line 565

Quoted 5 lines

fs/f2fs/extent_cache.c +0 -1

@@ -561,11 +554,11 @@ unsigned int f2fs_shrink_extent_tree(struct f2fs_sb_info *sbi, int
 nr_shrink)
 
 	/* 1. remove unreferenced extent tree */
 	list_for_each_entry_safe(et, next, &sbi->zombie_list, list) {
-		if (atomic_read(&et->node_cnt)) {

This is used to avoid lock overhead if there are no nodes in the tree. Why should we change this?

Quoted 85 lines

fs/f2fs/extent_cache.c +5 -4

-			write_lock(&et->lock);
-			node_cnt += __free_extent_tree(sbi, et, true);
-			write_unlock(&et->lock);
-		}
+		write_lock(&et->lock);
+		node_cnt += __free_extent_tree(sbi, et);
+		write_unlock(&et->lock);
+		if (atomic_read(&et->node_cnt) > 0)
+			goto unlock_out;
 
 		list_del_init(&et->list);

fs/f2fs/extent_cache.c +19 ~~-32~~

 		radix_tree_delete(&sbi->extent_tree_root, et->ino);

@@ -587,42 +580,29 @@ free_node:
 	remained = nr_shrink - (node_cnt + tree_cnt);
 
 	spin_lock(&sbi->extent_lock);
-	list_for_each_entry_safe(en, tmp, &sbi->extent_list, list) {
-		if (!remained--)
+	for (; remained > 0; remained--) {
+		if (list_empty(&sbi->extent_list))
 			break;
-		list_del_init(&en->list);
-		do_free = true;
-	}
-	spin_unlock(&sbi->extent_lock);
-
-	if (do_free == false)
-		goto unlock_out;
-
-	/*
-	 * reset ino for searching victims from beginning of global extent tree.
-	 */
-	ino = F2FS_ROOT_INO(sbi);
-
-	while ((found = radix_tree_gang_lookup(&sbi->extent_tree_root,
-				(void **)treevec, ino, EXT_TREE_VEC_SIZE))) {
-		unsigned i;
-
-		ino = treevec[found - 1]->ino + 1;
-		for (i = 0; i < found; i++) {
-			struct extent_tree *et = treevec[i];
+		en = list_first_entry(&sbi->extent_list,
+					struct extent_node, list);
+		et = en->et;
+		if (!write_trylock(&et->lock)) {
+			/* refresh this extent node's position in extent list */
+			list_move_tail(&en->list, &sbi->extent_list);
+			continue;
+		}
 
-			if (!atomic_read(&et->node_cnt))
-				continue;
+		list_del_init(&en->list);
+		spin_unlock(&sbi->extent_lock);
 
-			if (write_trylock(&et->lock)) {
-				node_cnt += __free_extent_tree(sbi, et, false);
-				write_unlock(&et->lock);
-			}
+		__detach_extent_node(sbi, et, en);
 
-			if (node_cnt + tree_cnt >= nr_shrink)
-				goto unlock_out;
-		}
+		write_unlock(&et->lock);
+		node_cnt++;
+		spin_lock(&sbi->extent_lock);
 	}
+	spin_unlock(&sbi->extent_lock);
+
 unlock_out:
 	up_write(&sbi->extent_tree_lock);
 out:

@@ -641,7 +621,7 @@ unsigned int f2fs_destroy_extent_node(struct inode *inode)
 		return 0;
 
 	write_lock(&et->lock);
-	node_cnt = __free_extent_tree(sbi, et, true);
+	node_cnt = __free_extent_tree(sbi, et);
 	write_unlock(&et->lock);
 
 	return node_cnt;

@@ -666,10 +646,15 @@ void f2fs_destroy_extent_tree(struct inode *inode)
 	}

fs/f2fs/extent_cache.c void f2fs_destroy_extent_tree(struct inode *inode) · line 657

Quoted 10 lines

fs/f2fs/extent_cache.c +5 -0

 	/* free all extent info belong to this extent tree */
+free_more:
 	node_cnt = f2fs_destroy_extent_node(inode);
 
 	/* delete extent tree entry in radix tree */
 	down_write(&sbi->extent_tree_lock);
+	if (atomic_read(&et->node_cnt) > 0) {
+		up_write(&sbi->extent_tree_lock);
+		goto free_more;
+	}

If I understand correctly here, there is no race condition between shrinker and destroyer, so it would be safe to usef2fs_bug_on(, et->node_cnt)?

Thanks,

Quoted 17 lines

fs/f2fs/extent_cache.c +0 -0

 	f2fs_bug_on(sbi, atomic_read(&et->node_cnt));
 	radix_tree_delete(&sbi->extent_tree_root, inode->i_ino);
 	kmem_cache_free(extent_tree_slab, et);

fs/f2fs/f2fs.h +1 -1

index c4e723b..4e7eab9 100644
@@ -354,6 +354,7 @@ struct extent_node {
 	struct rb_node rb_node;		/* rb node located in rb-tree */
 	struct list_head list;		/* node in global extent list of sbi */
 	struct extent_info ei;		/* extent info */
+	struct extent_tree *et;		/* extent tree pointer */
 };
 
 struct extent_tree {
--

2.6.3