f2fs: refactor shrink flow for extent cache

PATCH In review Chao Yu 3 participants 3 messages Jun 30, 2015 – Jul 2, 2015 F2FS file system

Share & tools

Chao Yu

author

2015-06-30 10:42 UTC #0 lore raw

PATCH 1/2 f2fs: refactor shrink flow for extent cache

For now, in extent cache, we have a global lru list which links all extent node in the cache, and the list is protected by a global spinlock.

If we want to shrink extent cache, we will:
1. delete all target extent node from global lru list under spinlock;
2. traverse all per-inode extent tree in global radix tree;
2.a. traverse all extent node in per-inode extent tree, try to free extent
node if it is not in global lru list already.

This method is inefficient when there is huge number of inode extent tree in global extent tree.

In this patch we introduce a new method for extent cache shrinking:
When we attach a new extent node, we record extent tree pointer in extent node. In shrink flow, we can try to find and lock extent tree of inode directly by this backward pointer, and then detach the extent node from extent tree.

This can help to shrink extent cache more efficiently.

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

---
 fs/f2fs/data.c | 113 ++++++++++++++++++++++++++++++++++-----------------------
 fs/f2fs/f2fs.h |   6 +++
 2 files changed, 73 insertions(+), 46 deletions(-)

fs/f2fs/data.c +67 ~~-46~~

index e90522a..e96916a 100644
@@ -279,6 +279,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);
 	et->count++;

@@ -435,7 +436,7 @@ update_out:
 }
 
 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;

@@ -446,23 +447,42 @@ static unsigned int __free_extent_tree(struct f2fs_sb_info *sbi,
 		next = rb_next(node);
 		en = rb_entry(node, struct extent_node, rb_node);
 
-		if (free_all) {
-			spin_lock(&sbi->extent_lock);
-			if (!list_empty(&en->list))
-				list_del_init(&en->list);
-			spin_unlock(&sbi->extent_lock);
-		}
+		spin_lock(&sbi->extent_lock);
+		if (!list_empty(&en->list))
+			list_del_init(&en->list);
+		spin_unlock(&sbi->extent_lock);
 
-		if (free_all || list_empty(&en->list)) {
-			__detach_extent_node(sbi, et, en);
-			kmem_cache_free(extent_node_slab, en);
-		}
+		__detach_extent_node(sbi, et, en);
+		kmem_cache_free(extent_node_slab, en);
 		node = next;
 	}
 
 	return count - et->count;
 }
 
+static bool __try_free_extent_tree(struct f2fs_sb_info *sbi, nid_t ino)
+{
+	struct extent_tree *et;
+
+	if (!down_write_trylock(&sbi->extent_tree_lock))
+		return false;
+
+	et = radix_tree_lookup(&sbi->extent_tree_root, ino);
+	if (!et)
+		goto out;
+
+	if (__can_free_extent_tree(et)) {
+		radix_tree_delete(&sbi->extent_tree_root, ino);
+		kmem_cache_free(extent_tree_slab, et);
+		sbi->total_ext_tree--;
+		up_write(&sbi->extent_tree_lock);
+		return true;
+	}
+out:
+	up_write(&sbi->extent_tree_lock);
+	return false;
+}
+
 static void __drop_largest_extent(struct inode *inode, pgoff_t fofs)
 {
 	struct extent_info *largest = &F2FS_I(inode)->extent_tree->largest;

@@ -633,7 +653,7 @@ update_extent:
 		kmem_cache_free(extent_node_slab, den);
 
 	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);

@@ -642,48 +662,49 @@ update_extent:
 
 unsigned int f2fs_shrink_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink)
 {
-	struct extent_tree *treevec[EXT_TREE_VEC_SIZE];
-	struct extent_node *en, *tmp;
-	unsigned long ino = F2FS_ROOT_INO(sbi);
-	struct radix_tree_root *root = &sbi->extent_tree_root;
-	unsigned int found;
+	struct extent_tree *et;
+	struct extent_node *en;
 	unsigned int node_cnt = 0, tree_cnt = 0;
 
 	if (!test_opt(sbi, EXTENT_CACHE))
 		return 0;
 
 	spin_lock(&sbi->extent_lock);
-	list_for_each_entry_safe(en, tmp, &sbi->extent_list, list) {
-		if (!nr_shrink--)
-			break;
-		list_del_init(&en->list);
-	}
-	spin_unlock(&sbi->extent_lock);
+	for (; nr_shrink > 0; nr_shrink--) {
+		nid_t ino;
+		bool can_free;
 
-	if (!down_write_trylock(&sbi->extent_tree_lock))
-		goto out;
+		if (list_empty(&sbi->extent_list))
+			break;
+		en = list_first_entry(&sbi->extent_list, struct extent_node,
+								list);
+		et = en->et;
 
-	while ((found = radix_tree_gang_lookup(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];
-
-			write_lock(&et->lock);
-			node_cnt += __free_extent_tree(sbi, et, false);
-			write_unlock(&et->lock);
-			if (!atomic_read(&et->refcount) && !et->count) {
-				radix_tree_delete(root, et->ino);
-				kmem_cache_free(extent_tree_slab, et);
-				sbi->total_ext_tree--;
-				tree_cnt++;
-			}
+		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(&en->list);
+		spin_unlock(&sbi->extent_lock);
+
+		__detach_extent_node(sbi, et, en);
+		kmem_cache_free(extent_node_slab, en);
+
+		ino = et->ino;
+		can_free = __can_free_extent_tree(et);
+		write_unlock(&et->lock);
+
+		node_cnt++;
+
+		if (can_free && __try_free_extent_tree(sbi, ino))
+			tree_cnt++;
+
+		spin_lock(&sbi->extent_lock);
 	}
-	up_write(&sbi->extent_tree_lock);
-out:
+	spin_unlock(&sbi->extent_lock);
+
 	trace_f2fs_shrink_extent_tree(sbi, node_cnt, tree_cnt);
 
 	return node_cnt + tree_cnt;

@@ -699,7 +720,7 @@ void f2fs_destroy_extent_node(struct inode *inode)
 		return;
 
 	write_lock(&et->lock);
-	node_cnt = __free_extent_tree(sbi, et, true);
+	node_cnt = __free_extent_tree(sbi, et);
 	write_unlock(&et->lock);
 }

@@ -723,7 +744,7 @@ void f2fs_destroy_extent_tree(struct inode *inode)
 	/* delete extent tree entry in radix tree */
 	down_write(&sbi->extent_tree_lock);
 	atomic_dec(&et->refcount);
-	f2fs_bug_on(sbi, atomic_read(&et->refcount) || et->count);
+	f2fs_bug_on(sbi, !__can_free_extent_tree(et));
 	radix_tree_delete(&sbi->extent_tree_root, inode->i_ino);
 	kmem_cache_free(extent_tree_slab, et);
 	sbi->total_ext_tree--;

fs/f2fs/f2fs.h +6 -0

index 2baca08..ee4c04a 100644
@@ -343,6 +343,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;         /* backref extent tree for shrinker */
 };
 
 struct extent_tree {

@@ -485,6 +486,11 @@ static inline bool __is_front_mergeable(struct extent_info *cur,
 	return __is_extent_mergeable(cur, front);
 }
 
+static inline bool __can_free_extent_tree(struct extent_tree *et)
+{
+	return (!atomic_read(&et->refcount) && !et->count);
+}
+
 struct f2fs_nm_info {
 	block_t nat_blkaddr;		/* base disk address of NAT */
 	nid_t max_nid;			/* maximum possible node ids */

Signature · 1 line

2.4.2

Jaegeuk Kim

maintainer

2015-07-01 01:25 UTC #1 lore raw

Hi Chao,

Quoted 12 lines · Chao Yu

For now, in extent cache, we have a global lru list which links all extent node in the cache, and the list is protected by a global spinlock.
If we want to shrink extent cache, we will:
1. delete all target extent node from global lru list under spinlock;
2. traverse all per-inode extent tree in global radix tree;
2.a. traverse all extent node in per-inode extent tree, try to free extent
node if it is not in global lru list already.
This method is inefficient when there is huge number of inode extent tree in global extent tree.

Quoted 6 lines

In this patch we introduce a new method for extent cache shrinking:
When we attach a new extent node, we record extent tree pointer in extent node. In shrink flow, we can try to find and lock extent tree of inode directly by this backward pointer, and then detach the extent node from extent tree.
This can help to shrink extent cache more efficiently.

Yes, but as we discussed before, this way will consume 4 bytes per each extent_node. Can it be acceptable?

Instead, IMO, we need to focus on how to increase its hit ratio first. Actually, I wrote a patch for that.
Could you check that first?

Thanks,

Chao Yu

2015-07-02 12:37 UTC #2 lore raw

Hi Jaegeuk,

Quoted 28 lines

-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
Sent: Wednesday, July 01, 2015 9:26 AM
To: Chao Yu; Chao Yu
Cc: [email protected]; [email protected]; [email protected]; [email protected]
Subject: Re: [f2fs-dev] [PATCH 1/2] f2fs: refactor shrink flow for extent cache
Hi Chao,
Quoted 17 lines · Chao Yu
For now, in extent cache, we have a global lru list which links all extent node in the cache, and the list is protected by a global spinlock.
If we want to shrink extent cache, we will:
1. delete all target extent node from global lru list under spinlock;
2. traverse all per-inode extent tree in global radix tree;
2.a. traverse all extent node in per-inode extent tree, try to free extent
node if it is not in global lru list already.
This method is inefficient when there is huge number of inode extent tree in global extent tree.
In this patch we introduce a new method for extent cache shrinking:
When we attach a new extent node, we record extent tree pointer in extent node. In shrink flow, we can try to find and lock extent tree of inode directly by this backward pointer, and then detach the extent node from extent tree.

Quoted 4 lines

Quoted 1 line
This can help to shrink extent cache more efficiently.
Yes, but as we discussed before, this way will consume 4 bytes per each extent_node. Can it be acceptable?

Yes, this method will increase memory overhead obviously.

Maybe there is a better way to reduce lock contention and block time of shrinker maked. I will rethink about it.

What I think now is I should firstly tests on our new shrinker with extreme case to see how bad it shows.

Quoted 4 lines

Instead, IMO, we need to focus on how to increase its hit ratio first. Actually, I wrote a patch for that.
Could you check that first?

Thanks,

Quoted 2 lines

Thanks,

------------------------------------------------------------------------------
Don't Limit Your Business. Reach for the Cloud.
GigeNET's Cloud Solutions provide you with the tools and support that you need to offload your IT needs and focus on growing your business. Configured For All Businesses. Start Your Cloud Today.
https://www.gigenetcloud.com/