[PATCH] f2fs: more fast lookup for gc_inode list

[PATCH] f2fs: more fast lookup for gc_inode list

[Changman Lee]

If there are many inodes that have data blocks in victim segment,
it takes long time to find a inode in gc_inode list.
Let's use radix_tree to reduce lookup time.

Signed-off-by: Changman Lee <cm224.lee@samsung.com>
---
 fs/f2fs/gc.c | 21 ++++++++++++++-------
 1 file changed, 14 insertions(+), 7 deletions(-)

diff --git a/fs/f2fs/gc.c b/fs/f2fs/gc.c
index 29fc7e5..fc765c1 100644
--- a/fs/f2fs/gc.c
+++ b/fs/f2fs/gc.c
@@ -24,6 +24,7 @@
 #include "gc.h"
 #include <trace/events/f2fs.h>
 
+RADIX_TREE(gc_inode_root, GFP_ATOMIC);
 static struct kmem_cache *winode_slab;
 
 static int gc_thread_func(void *data)
@@ -338,13 +339,13 @@ static const struct victim_selection default_v_ops = {
 	.get_victim = get_victim_by_default,
 };
 
-static struct inode *find_gc_inode(nid_t ino, struct list_head *ilist)
+static struct inode *find_gc_inode(nid_t ino)
 {
 	struct inode_entry *ie;
 
-	list_for_each_entry(ie, ilist, list)
-		if (ie->inode->i_ino == ino)
-			return ie->inode;
+	ie = radix_tree_lookup(&gc_inode_root, ino);
+	if (ie)
+		return ie->inode;
 	return NULL;
 }
 
@@ -352,13 +353,19 @@ static void add_gc_inode(struct inode *inode, struct list_head *ilist)
 {
 	struct inode_entry *new_ie;
 
-	if (inode == find_gc_inode(inode->i_ino, ilist)) {
+	new_ie = radix_tree_lookup(&gc_inode_root, inode->i_ino);
+	if (new_ie) {
 		iput(inode);
 		return;
 	}
 
 	new_ie = f2fs_kmem_cache_alloc(winode_slab, GFP_NOFS);
 	new_ie->inode = inode;
+
+	if (radix_tree_insert(&gc_inode_root, inode->i_ino, new_ie)) {
+		kmem_cache_free(winode_slab, new_ie);
+		return;
+	}
 	list_add_tail(&new_ie->list, ilist);
 }
 
@@ -367,7 +374,7 @@ static void put_gc_inode(struct list_head *ilist)
 	struct inode_entry *ie, *next_ie;
 	list_for_each_entry_safe(ie, next_ie, ilist, list) {
 		iput(ie->inode);
-		list_del(&ie->list);
+		radix_tree_delete(&gc_inode_root, ie->inode->i_ino);
 		kmem_cache_free(winode_slab, ie);
 	}
 }
@@ -614,7 +621,7 @@ next_step:
 		}
 
 		/* phase 3 */
-		inode = find_gc_inode(dni.ino, ilist);
+		inode = find_gc_inode(dni.ino);
 		if (inode) {
 			start_bidx = start_bidx_of_node(nofs,
 							F2FS_I(inode));
-- 
1.9.1

Re: [f2fs-dev] [PATCH] f2fs: more fast lookup for gc_inode list

[Jaegeuk Kim]

Hi,

On Thu, Nov 27, 2014 at 06:11:51PM +0900, Changman Lee wrote:
> If there are many inodes that have data blocks in victim segment,
> it takes long time to find a inode in gc_inode list.
> Let's use radix_tree to reduce lookup time.
> 
> Signed-off-by: Changman Lee <cm224.lee@samsung.com>
> ---
>  fs/f2fs/gc.c | 21 ++++++++++++++-------
>  1 file changed, 14 insertions(+), 7 deletions(-)
> 
> diff --git a/fs/f2fs/gc.c b/fs/f2fs/gc.c
> index 29fc7e5..fc765c1 100644
> --- a/fs/f2fs/gc.c
> +++ b/fs/f2fs/gc.c
> @@ -24,6 +24,7 @@
>  #include "gc.h"
>  #include <trace/events/f2fs.h>
>  
> +RADIX_TREE(gc_inode_root, GFP_ATOMIC);

How about adding a radix tree locally along with ilist?

>  static struct kmem_cache *winode_slab;
>  
>  static int gc_thread_func(void *data)
> @@ -338,13 +339,13 @@ static const struct victim_selection default_v_ops = {
>  	.get_victim = get_victim_by_default,
>  };
>  
> -static struct inode *find_gc_inode(nid_t ino, struct list_head *ilist)
> +static struct inode *find_gc_inode(nid_t ino)
>  {
>  	struct inode_entry *ie;
>  
> -	list_for_each_entry(ie, ilist, list)
> -		if (ie->inode->i_ino == ino)
> -			return ie->inode;
> +	ie = radix_tree_lookup(&gc_inode_root, ino);
> +	if (ie)
> +		return ie->inode;
>  	return NULL;
>  }
>  
> @@ -352,13 +353,19 @@ static void add_gc_inode(struct inode *inode, struct list_head *ilist)
>  {
>  	struct inode_entry *new_ie;
>  
> -	if (inode == find_gc_inode(inode->i_ino, ilist)) {
> +	new_ie = radix_tree_lookup(&gc_inode_root, inode->i_ino);
> +	if (new_ie) {
>  		iput(inode);
>  		return;
>  	}
>  
>  	new_ie = f2fs_kmem_cache_alloc(winode_slab, GFP_NOFS);
>  	new_ie->inode = inode;
> +
> +	if (radix_tree_insert(&gc_inode_root, inode->i_ino, new_ie)) {
> +		kmem_cache_free(winode_slab, new_ie);
> +		return;
> +	}

The add_gc_inode should succeed all the tiem.
It seems that we need a sort of loop to avoid that.

>  	list_add_tail(&new_ie->list, ilist);
>  }
>  
> @@ -367,7 +374,7 @@ static void put_gc_inode(struct list_head *ilist)
>  	struct inode_entry *ie, *next_ie;
>  	list_for_each_entry_safe(ie, next_ie, ilist, list) {
>  		iput(ie->inode);
> -		list_del(&ie->list);

Logically, it'd better remain list_del.

> +		radix_tree_delete(&gc_inode_root, ie->inode->i_ino);

We should not use ie->inode, since it was already put.

>  		kmem_cache_free(winode_slab, ie);
>  	}
>  }
> @@ -614,7 +621,7 @@ next_step:
>  		}
>  
>  		/* phase 3 */
> -		inode = find_gc_inode(dni.ino, ilist);
> +		inode = find_gc_inode(dni.ino);

It needs to pass a local radix tree pointer.

>  		if (inode) {
>  			start_bidx = start_bidx_of_node(nofs,
>  							F2FS_I(inode));
> -- 
> 1.9.1
> 
> 
> ------------------------------------------------------------------------------
> Download BIRT iHub F-Type - The Free Enterprise-Grade BIRT Server
> from Actuate! Instantly Supercharge Your Business Reports and Dashboards
> with Interactivity, Sharing, Native Excel Exports, App Integration & more
> Get technology previously reserved for billion-dollar corporations, FREE
> http://pubads.g.doubleclick.net/gampad/clk?id=157005751&iu=/4140/ostg.clktrk
> _______________________________________________
> Linux-f2fs-devel mailing list
> Linux-f2fs-devel@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel

Re: [f2fs-dev] [PATCH] f2fs: more fast lookup for gc_inode list

[Changman Lee]

Hi,

As you said, I will resend a patch. Thanks for your review.

On Thu, Nov 27, 2014 at 08:24:21PM -0800, Jaegeuk Kim wrote:
> Hi,
> 
> On Thu, Nov 27, 2014 at 06:11:51PM +0900, Changman Lee wrote:
> > If there are many inodes that have data blocks in victim segment,
> > it takes long time to find a inode in gc_inode list.
> > Let's use radix_tree to reduce lookup time.
> > 
> > Signed-off-by: Changman Lee <cm224.lee@samsung.com>
> > ---
> >  fs/f2fs/gc.c | 21 ++++++++++++++-------
> >  1 file changed, 14 insertions(+), 7 deletions(-)
> > 
> > diff --git a/fs/f2fs/gc.c b/fs/f2fs/gc.c
> > index 29fc7e5..fc765c1 100644
> > --- a/fs/f2fs/gc.c
> > +++ b/fs/f2fs/gc.c
> > @@ -24,6 +24,7 @@
> >  #include "gc.h"
> >  #include <trace/events/f2fs.h>
> >  
> > +RADIX_TREE(gc_inode_root, GFP_ATOMIC);
> 
> How about adding a radix tree locally along with ilist?
> 
> >  static struct kmem_cache *winode_slab;
> >  
> >  static int gc_thread_func(void *data)
> > @@ -338,13 +339,13 @@ static const struct victim_selection default_v_ops = {
> >  	.get_victim = get_victim_by_default,
> >  };
> >  
> > -static struct inode *find_gc_inode(nid_t ino, struct list_head *ilist)
> > +static struct inode *find_gc_inode(nid_t ino)
> >  {
> >  	struct inode_entry *ie;
> >  
> > -	list_for_each_entry(ie, ilist, list)
> > -		if (ie->inode->i_ino == ino)
> > -			return ie->inode;
> > +	ie = radix_tree_lookup(&gc_inode_root, ino);
> > +	if (ie)
> > +		return ie->inode;
> >  	return NULL;
> >  }
> >  
> > @@ -352,13 +353,19 @@ static void add_gc_inode(struct inode *inode, struct list_head *ilist)
> >  {
> >  	struct inode_entry *new_ie;
> >  
> > -	if (inode == find_gc_inode(inode->i_ino, ilist)) {
> > +	new_ie = radix_tree_lookup(&gc_inode_root, inode->i_ino);
> > +	if (new_ie) {
> >  		iput(inode);
> >  		return;
> >  	}
> >  
> >  	new_ie = f2fs_kmem_cache_alloc(winode_slab, GFP_NOFS);
> >  	new_ie->inode = inode;
> > +
> > +	if (radix_tree_insert(&gc_inode_root, inode->i_ino, new_ie)) {
> > +		kmem_cache_free(winode_slab, new_ie);
> > +		return;
> > +	}
> 
> The add_gc_inode should succeed all the tiem.
> It seems that we need a sort of loop to avoid that.
> 
> >  	list_add_tail(&new_ie->list, ilist);
> >  }
> >  
> > @@ -367,7 +374,7 @@ static void put_gc_inode(struct list_head *ilist)
> >  	struct inode_entry *ie, *next_ie;
> >  	list_for_each_entry_safe(ie, next_ie, ilist, list) {
> >  		iput(ie->inode);
> > -		list_del(&ie->list);
> 
> Logically, it'd better remain list_del.
> 
> > +		radix_tree_delete(&gc_inode_root, ie->inode->i_ino);
> 
> We should not use ie->inode, since it was already put.
> 
> >  		kmem_cache_free(winode_slab, ie);
> >  	}
> >  }
> > @@ -614,7 +621,7 @@ next_step:
> >  		}
> >  
> >  		/* phase 3 */
> > -		inode = find_gc_inode(dni.ino, ilist);
> > +		inode = find_gc_inode(dni.ino);
> 
> It needs to pass a local radix tree pointer.
> 
> >  		if (inode) {
> >  			start_bidx = start_bidx_of_node(nofs,
> >  							F2FS_I(inode));
> > -- 
> > 1.9.1
> > 
> > 
> > ------------------------------------------------------------------------------
> > Download BIRT iHub F-Type - The Free Enterprise-Grade BIRT Server
> > from Actuate! Instantly Supercharge Your Business Reports and Dashboards
> > with Interactivity, Sharing, Native Excel Exports, App Integration & more
> > Get technology previously reserved for billion-dollar corporations, FREE
> > http://pubads.g.doubleclick.net/gampad/clk?id=157005751&iu=/4140/ostg.clktrk
> > _______________________________________________
> > Linux-f2fs-devel mailing list
> > Linux-f2fs-devel@lists.sourceforge.net
> > https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel

Re: [f2fs-dev] [PATCH V2] f2fs: more fast lookup for gc_inode list

[Changman Lee]

Hi Jaegeuk,

I've modified as you mentioned. Review again, please.

Changes from V1
 o introduce gc_inode_list containing ilist and iradix
 o use local variable
 o call radix_tree_delete before iput
 o retry to add inode into radix_tree
 o call list_del explicitly

Thanks,
Changman

-- >8 --
>From eb1a8f4ddee6c5541d5979e4119ca33245d74c30 Mon Sep 17 00:00:00 2001
From: Changman Lee <cm224.lee@samsung.com>
Date: Fri, 28 Nov 2014 15:49:40 +0000
Subject: [PATCH] f2fs: more fast lookup for gc_inode list

If there are many inodes that have data blocks in victim segment,
it takes long time to find a inode in gc_inode list.
Let's use radix_tree to reduce lookup time.

Signed-off-by: Changman Lee <cm224.lee@samsung.com>
---
 fs/f2fs/gc.c | 56 +++++++++++++++++++++++++++++++++++---------------------
 1 file changed, 35 insertions(+), 21 deletions(-)

diff --git a/fs/f2fs/gc.c b/fs/f2fs/gc.c
index 29fc7e5..e10ed7f 100644
--- a/fs/f2fs/gc.c
+++ b/fs/f2fs/gc.c
@@ -26,6 +26,11 @@
 
 static struct kmem_cache *winode_slab;
 
+struct gc_inode_list {
+	struct list_head ilist;
+	struct radix_tree_root iradix;
+};
+
 static int gc_thread_func(void *data)
 {
 	struct f2fs_sb_info *sbi = data;
@@ -338,34 +343,41 @@ static const struct victim_selection default_v_ops = {
 	.get_victim = get_victim_by_default,
 };
 
-static struct inode *find_gc_inode(nid_t ino, struct list_head *ilist)
+static struct inode *find_gc_inode(struct gc_inode_list *gc_list, nid_t ino)
 {
 	struct inode_entry *ie;
 
-	list_for_each_entry(ie, ilist, list)
-		if (ie->inode->i_ino == ino)
-			return ie->inode;
+	ie = radix_tree_lookup(&gc_list->iradix, ino);
+	if (ie)
+		return ie->inode;
 	return NULL;
 }
 
-static void add_gc_inode(struct inode *inode, struct list_head *ilist)
+static void add_gc_inode(struct gc_inode_list *gc_list, struct inode *inode)
 {
 	struct inode_entry *new_ie;
+	int ret;
+retry:
+	new_ie = f2fs_kmem_cache_alloc(winode_slab, GFP_NOFS);
+	new_ie->inode = inode;
 
-	if (inode == find_gc_inode(inode->i_ino, ilist)) {
+	ret = radix_tree_insert(&gc_list->iradix, inode->i_ino, new_ie);
+	if (ret == -EEXIST) {
+		kmem_cache_free(winode_slab, new_ie);
 		iput(inode);
 		return;
+	} else if (ret) {
+		kmem_cache_free(winode_slab, new_ie);
+		goto retry;
 	}
-
-	new_ie = f2fs_kmem_cache_alloc(winode_slab, GFP_NOFS);
-	new_ie->inode = inode;
-	list_add_tail(&new_ie->list, ilist);
+	list_add_tail(&new_ie->list, &gc_list->ilist);
 }
 
-static void put_gc_inode(struct list_head *ilist)
+static void put_gc_inode(struct gc_inode_list *gc_list)
 {
 	struct inode_entry *ie, *next_ie;
-	list_for_each_entry_safe(ie, next_ie, ilist, list) {
+	list_for_each_entry_safe(ie, next_ie, &gc_list->ilist, list) {
+		radix_tree_delete(&gc_list->iradix, ie->inode->i_ino);
 		iput(ie->inode);
 		list_del(&ie->list);
 		kmem_cache_free(winode_slab, ie);
@@ -551,7 +563,7 @@ out:
  * the victim data block is ignored.
  */
 static void gc_data_segment(struct f2fs_sb_info *sbi, struct f2fs_summary *sum,
-		struct list_head *ilist, unsigned int segno, int gc_type)
+		struct gc_inode_list *gc_list, unsigned int segno, int gc_type)
 {
 	struct super_block *sb = sbi->sb;
 	struct f2fs_summary *entry;
@@ -609,12 +621,12 @@ next_step:
 			}
 
 			f2fs_put_page(data_page, 0);
-			add_gc_inode(inode, ilist);
+			add_gc_inode(gc_list, inode);
 			continue;
 		}
 
 		/* phase 3 */
-		inode = find_gc_inode(dni.ino, ilist);
+		inode = find_gc_inode(gc_list, dni.ino);
 		if (inode) {
 			start_bidx = start_bidx_of_node(nofs,
 							F2FS_I(inode));
@@ -658,7 +670,7 @@ static int __get_victim(struct f2fs_sb_info *sbi, unsigned int *victim,
 }
 
 static void do_garbage_collect(struct f2fs_sb_info *sbi, unsigned int segno,
-				struct list_head *ilist, int gc_type)
+				struct gc_inode_list *gc_list, int gc_type)
 {
 	struct page *sum_page;
 	struct f2fs_summary_block *sum;
@@ -676,7 +688,7 @@ static void do_garbage_collect(struct f2fs_sb_info *sbi, unsigned int segno,
 		gc_node_segment(sbi, sum->entries, segno, gc_type);
 		break;
 	case SUM_TYPE_DATA:
-		gc_data_segment(sbi, sum->entries, ilist, segno, gc_type);
+		gc_data_segment(sbi, sum->entries, gc_list, segno, gc_type);
 		break;
 	}
 	blk_finish_plug(&plug);
@@ -689,16 +701,18 @@ static void do_garbage_collect(struct f2fs_sb_info *sbi, unsigned int segno,
 
 int f2fs_gc(struct f2fs_sb_info *sbi)
 {
-	struct list_head ilist;
 	unsigned int segno, i;
 	int gc_type = BG_GC;
 	int nfree = 0;
 	int ret = -1;
 	struct cp_control cpc;
+	struct gc_inode_list gc_list = {
+		.ilist = LIST_HEAD_INIT(gc_list.ilist),
+		.iradix = RADIX_TREE_INIT(GFP_ATOMIC),
+	};
 
 	cpc.reason = test_opt(sbi, FASTBOOT) ? CP_UMOUNT : CP_SYNC;
 
-	INIT_LIST_HEAD(&ilist);
 gc_more:
 	if (unlikely(!(sbi->sb->s_flags & MS_ACTIVE)))
 		goto stop;
@@ -720,7 +734,7 @@ gc_more:
 								META_SSA);
 
 	for (i = 0; i < sbi->segs_per_sec; i++)
-		do_garbage_collect(sbi, segno + i, &ilist, gc_type);
+		do_garbage_collect(sbi, segno + i, &gc_list, gc_type);
 
 	if (gc_type == FG_GC) {
 		sbi->cur_victim_sec = NULL_SEGNO;
@@ -736,7 +750,7 @@ gc_more:
 stop:
 	mutex_unlock(&sbi->gc_mutex);
 
-	put_gc_inode(&ilist);
+	put_gc_inode(&gc_list);
 	return ret;
 }
 
-- 
1.9.1

Re: [f2fs-dev] [PATCH V2] f2fs: more fast lookup for gc_inode list

[Jaegeuk Kim]

Hi,

On Fri, Nov 28, 2014 at 04:12:50PM +0900, Changman Lee wrote:
> Hi Jaegeuk,
> 
> I've modified as you mentioned. Review again, please.
> 
> Changes from V1
>  o introduce gc_inode_list containing ilist and iradix
>  o use local variable
>  o call radix_tree_delete before iput
>  o retry to add inode into radix_tree
>  o call list_del explicitly
> 
> Thanks,
> Changman
> 
> -- >8 --
> >From eb1a8f4ddee6c5541d5979e4119ca33245d74c30 Mon Sep 17 00:00:00 2001
> From: Changman Lee <cm224.lee@samsung.com>
> Date: Fri, 28 Nov 2014 15:49:40 +0000
> Subject: [PATCH] f2fs: more fast lookup for gc_inode list
> 
> If there are many inodes that have data blocks in victim segment,
> it takes long time to find a inode in gc_inode list.
> Let's use radix_tree to reduce lookup time.
> 
> Signed-off-by: Changman Lee <cm224.lee@samsung.com>
> ---
>  fs/f2fs/gc.c | 56 +++++++++++++++++++++++++++++++++++---------------------
>  1 file changed, 35 insertions(+), 21 deletions(-)
> 
> diff --git a/fs/f2fs/gc.c b/fs/f2fs/gc.c
> index 29fc7e5..e10ed7f 100644
> --- a/fs/f2fs/gc.c
> +++ b/fs/f2fs/gc.c
> @@ -26,6 +26,11 @@
>  
>  static struct kmem_cache *winode_slab;
>  
> +struct gc_inode_list {
> +	struct list_head ilist;
> +	struct radix_tree_root iradix;
> +};

How about replacing iradix with iroot?

Please declare the structure in gc.h.

Thanks,

> +
>  static int gc_thread_func(void *data)
>  {
>  	struct f2fs_sb_info *sbi = data;
> @@ -338,34 +343,41 @@ static const struct victim_selection default_v_ops = {
>  	.get_victim = get_victim_by_default,
>  };
>  
> -static struct inode *find_gc_inode(nid_t ino, struct list_head *ilist)
> +static struct inode *find_gc_inode(struct gc_inode_list *gc_list, nid_t ino)
>  {
>  	struct inode_entry *ie;
>  
> -	list_for_each_entry(ie, ilist, list)
> -		if (ie->inode->i_ino == ino)
> -			return ie->inode;
> +	ie = radix_tree_lookup(&gc_list->iradix, ino);
> +	if (ie)
> +		return ie->inode;
>  	return NULL;
>  }
>  
> -static void add_gc_inode(struct inode *inode, struct list_head *ilist)
> +static void add_gc_inode(struct gc_inode_list *gc_list, struct inode *inode)
>  {
>  	struct inode_entry *new_ie;
> +	int ret;
> +retry:
> +	new_ie = f2fs_kmem_cache_alloc(winode_slab, GFP_NOFS);
> +	new_ie->inode = inode;
>  
> -	if (inode == find_gc_inode(inode->i_ino, ilist)) {
> +	ret = radix_tree_insert(&gc_list->iradix, inode->i_ino, new_ie);
> +	if (ret == -EEXIST) {
> +		kmem_cache_free(winode_slab, new_ie);
>  		iput(inode);
>  		return;
> +	} else if (ret) {
> +		kmem_cache_free(winode_slab, new_ie);
> +		goto retry;
>  	}
> -
> -	new_ie = f2fs_kmem_cache_alloc(winode_slab, GFP_NOFS);
> -	new_ie->inode = inode;
> -	list_add_tail(&new_ie->list, ilist);
> +	list_add_tail(&new_ie->list, &gc_list->ilist);
>  }
>  
> -static void put_gc_inode(struct list_head *ilist)
> +static void put_gc_inode(struct gc_inode_list *gc_list)
>  {
>  	struct inode_entry *ie, *next_ie;
> -	list_for_each_entry_safe(ie, next_ie, ilist, list) {
> +	list_for_each_entry_safe(ie, next_ie, &gc_list->ilist, list) {
> +		radix_tree_delete(&gc_list->iradix, ie->inode->i_ino);
>  		iput(ie->inode);
>  		list_del(&ie->list);
>  		kmem_cache_free(winode_slab, ie);
> @@ -551,7 +563,7 @@ out:
>   * the victim data block is ignored.
>   */
>  static void gc_data_segment(struct f2fs_sb_info *sbi, struct f2fs_summary *sum,
> -		struct list_head *ilist, unsigned int segno, int gc_type)
> +		struct gc_inode_list *gc_list, unsigned int segno, int gc_type)
>  {
>  	struct super_block *sb = sbi->sb;
>  	struct f2fs_summary *entry;
> @@ -609,12 +621,12 @@ next_step:
>  			}
>  
>  			f2fs_put_page(data_page, 0);
> -			add_gc_inode(inode, ilist);
> +			add_gc_inode(gc_list, inode);
>  			continue;
>  		}
>  
>  		/* phase 3 */
> -		inode = find_gc_inode(dni.ino, ilist);
> +		inode = find_gc_inode(gc_list, dni.ino);
>  		if (inode) {
>  			start_bidx = start_bidx_of_node(nofs,
>  							F2FS_I(inode));
> @@ -658,7 +670,7 @@ static int __get_victim(struct f2fs_sb_info *sbi, unsigned int *victim,
>  }
>  
>  static void do_garbage_collect(struct f2fs_sb_info *sbi, unsigned int segno,
> -				struct list_head *ilist, int gc_type)
> +				struct gc_inode_list *gc_list, int gc_type)
>  {
>  	struct page *sum_page;
>  	struct f2fs_summary_block *sum;
> @@ -676,7 +688,7 @@ static void do_garbage_collect(struct f2fs_sb_info *sbi, unsigned int segno,
>  		gc_node_segment(sbi, sum->entries, segno, gc_type);
>  		break;
>  	case SUM_TYPE_DATA:
> -		gc_data_segment(sbi, sum->entries, ilist, segno, gc_type);
> +		gc_data_segment(sbi, sum->entries, gc_list, segno, gc_type);
>  		break;
>  	}
>  	blk_finish_plug(&plug);
> @@ -689,16 +701,18 @@ static void do_garbage_collect(struct f2fs_sb_info *sbi, unsigned int segno,
>  
>  int f2fs_gc(struct f2fs_sb_info *sbi)
>  {
> -	struct list_head ilist;
>  	unsigned int segno, i;
>  	int gc_type = BG_GC;
>  	int nfree = 0;
>  	int ret = -1;
>  	struct cp_control cpc;
> +	struct gc_inode_list gc_list = {
> +		.ilist = LIST_HEAD_INIT(gc_list.ilist),
> +		.iradix = RADIX_TREE_INIT(GFP_ATOMIC),
> +	};
>  
>  	cpc.reason = test_opt(sbi, FASTBOOT) ? CP_UMOUNT : CP_SYNC;
>  
> -	INIT_LIST_HEAD(&ilist);
>  gc_more:
>  	if (unlikely(!(sbi->sb->s_flags & MS_ACTIVE)))
>  		goto stop;
> @@ -720,7 +734,7 @@ gc_more:
>  								META_SSA);
>  
>  	for (i = 0; i < sbi->segs_per_sec; i++)
> -		do_garbage_collect(sbi, segno + i, &ilist, gc_type);
> +		do_garbage_collect(sbi, segno + i, &gc_list, gc_type);
>  
>  	if (gc_type == FG_GC) {
>  		sbi->cur_victim_sec = NULL_SEGNO;
> @@ -736,7 +750,7 @@ gc_more:
>  stop:
>  	mutex_unlock(&sbi->gc_mutex);
>  
> -	put_gc_inode(&ilist);
> +	put_gc_inode(&gc_list);
>  	return ret;
>  }
>  
> -- 
> 1.9.1

Re: [f2fs-dev] [PATCH V2] f2fs: more fast lookup for gc_inode list

[Changman Lee]

Hi Jaeguek,

Thansk for review.

Changes from V2
 o rename iradix to iroot
 o declare gc_inode_list in gc.h

Changes from V1
 o introduce gc_inode_list containing ilist and iradix
 o use local variable
 o call radix_tree_delete before iput
 o retry to add inode into radix_tree
 o call list_del explicitly

Regards,
Changman

--> 8 --
>From 6c32edfc00aa784c47f5018d10fb8f9b5ab54c8b Mon Sep 17 00:00:00 2001
From: Changman Lee <cm224.lee@samsung.com>
Date: Fri, 28 Nov 2014 15:49:40 +0000
Subject: [PATCH] f2fs: more fast lookup for gc_inode list

If there are many inodes that have data blocks in victim segment,
it takes long time to find a inode in gc_inode list.
Let's use radix_tree to reduce lookup time.

Signed-off-by: Changman Lee <cm224.lee@samsung.com>
---
 fs/f2fs/gc.c | 51 ++++++++++++++++++++++++++++++---------------------
 fs/f2fs/gc.h |  5 +++++
 2 files changed, 35 insertions(+), 21 deletions(-)

diff --git a/fs/f2fs/gc.c b/fs/f2fs/gc.c
index 29fc7e5..92f706c 100644
--- a/fs/f2fs/gc.c
+++ b/fs/f2fs/gc.c
@@ -338,34 +338,41 @@ static const struct victim_selection default_v_ops = {
 	.get_victim = get_victim_by_default,
 };
 
-static struct inode *find_gc_inode(nid_t ino, struct list_head *ilist)
+static struct inode *find_gc_inode(struct gc_inode_list *gc_list, nid_t ino)
 {
 	struct inode_entry *ie;
 
-	list_for_each_entry(ie, ilist, list)
-		if (ie->inode->i_ino == ino)
-			return ie->inode;
+	ie = radix_tree_lookup(&gc_list->iroot, ino);
+	if (ie)
+		return ie->inode;
 	return NULL;
 }
 
-static void add_gc_inode(struct inode *inode, struct list_head *ilist)
+static void add_gc_inode(struct gc_inode_list *gc_list, struct inode *inode)
 {
 	struct inode_entry *new_ie;
+	int ret;
+retry:
+	new_ie = f2fs_kmem_cache_alloc(winode_slab, GFP_NOFS);
+	new_ie->inode = inode;
 
-	if (inode == find_gc_inode(inode->i_ino, ilist)) {
+	ret = radix_tree_insert(&gc_list->iroot, inode->i_ino, new_ie);
+	if (ret == -EEXIST) {
+		kmem_cache_free(winode_slab, new_ie);
 		iput(inode);
 		return;
+	} else if (ret) {
+		kmem_cache_free(winode_slab, new_ie);
+		goto retry;
 	}
-
-	new_ie = f2fs_kmem_cache_alloc(winode_slab, GFP_NOFS);
-	new_ie->inode = inode;
-	list_add_tail(&new_ie->list, ilist);
+	list_add_tail(&new_ie->list, &gc_list->ilist);
 }
 
-static void put_gc_inode(struct list_head *ilist)
+static void put_gc_inode(struct gc_inode_list *gc_list)
 {
 	struct inode_entry *ie, *next_ie;
-	list_for_each_entry_safe(ie, next_ie, ilist, list) {
+	list_for_each_entry_safe(ie, next_ie, &gc_list->ilist, list) {
+		radix_tree_delete(&gc_list->iroot, ie->inode->i_ino);
 		iput(ie->inode);
 		list_del(&ie->list);
 		kmem_cache_free(winode_slab, ie);
@@ -551,7 +558,7 @@ out:
  * the victim data block is ignored.
  */
 static void gc_data_segment(struct f2fs_sb_info *sbi, struct f2fs_summary *sum,
-		struct list_head *ilist, unsigned int segno, int gc_type)
+		struct gc_inode_list *gc_list, unsigned int segno, int gc_type)
 {
 	struct super_block *sb = sbi->sb;
 	struct f2fs_summary *entry;
@@ -609,12 +616,12 @@ next_step:
 			}
 
 			f2fs_put_page(data_page, 0);
-			add_gc_inode(inode, ilist);
+			add_gc_inode(gc_list, inode);
 			continue;
 		}
 
 		/* phase 3 */
-		inode = find_gc_inode(dni.ino, ilist);
+		inode = find_gc_inode(gc_list, dni.ino);
 		if (inode) {
 			start_bidx = start_bidx_of_node(nofs,
 							F2FS_I(inode));
@@ -658,7 +665,7 @@ static int __get_victim(struct f2fs_sb_info *sbi, unsigned int *victim,
 }
 
 static void do_garbage_collect(struct f2fs_sb_info *sbi, unsigned int segno,
-				struct list_head *ilist, int gc_type)
+				struct gc_inode_list *gc_list, int gc_type)
 {
 	struct page *sum_page;
 	struct f2fs_summary_block *sum;
@@ -676,7 +683,7 @@ static void do_garbage_collect(struct f2fs_sb_info *sbi, unsigned int segno,
 		gc_node_segment(sbi, sum->entries, segno, gc_type);
 		break;
 	case SUM_TYPE_DATA:
-		gc_data_segment(sbi, sum->entries, ilist, segno, gc_type);
+		gc_data_segment(sbi, sum->entries, gc_list, segno, gc_type);
 		break;
 	}
 	blk_finish_plug(&plug);
@@ -689,16 +696,18 @@ static void do_garbage_collect(struct f2fs_sb_info *sbi, unsigned int segno,
 
 int f2fs_gc(struct f2fs_sb_info *sbi)
 {
-	struct list_head ilist;
 	unsigned int segno, i;
 	int gc_type = BG_GC;
 	int nfree = 0;
 	int ret = -1;
 	struct cp_control cpc;
+	struct gc_inode_list gc_list = {
+		.ilist = LIST_HEAD_INIT(gc_list.ilist),
+		.iroot = RADIX_TREE_INIT(GFP_ATOMIC),
+	};
 
 	cpc.reason = test_opt(sbi, FASTBOOT) ? CP_UMOUNT : CP_SYNC;
 
-	INIT_LIST_HEAD(&ilist);
 gc_more:
 	if (unlikely(!(sbi->sb->s_flags & MS_ACTIVE)))
 		goto stop;
@@ -720,7 +729,7 @@ gc_more:
 								META_SSA);
 
 	for (i = 0; i < sbi->segs_per_sec; i++)
-		do_garbage_collect(sbi, segno + i, &ilist, gc_type);
+		do_garbage_collect(sbi, segno + i, &gc_list, gc_type);
 
 	if (gc_type == FG_GC) {
 		sbi->cur_victim_sec = NULL_SEGNO;
@@ -736,7 +745,7 @@ gc_more:
 stop:
 	mutex_unlock(&sbi->gc_mutex);
 
-	put_gc_inode(&ilist);
+	put_gc_inode(&gc_list);
 	return ret;
 }
 
diff --git a/fs/f2fs/gc.h b/fs/f2fs/gc.h
index 16f0b2b..6ff7ad3 100644
--- a/fs/f2fs/gc.h
+++ b/fs/f2fs/gc.h
@@ -40,6 +40,11 @@ struct inode_entry {
 	struct inode *inode;
 };
 
+struct gc_inode_list {
+	struct list_head ilist;
+	struct radix_tree_root iroot;
+};
+
 /*
  * inline functions
  */
-- 
1.9.1

RE: [f2fs-dev] [PATCH V2] f2fs: more fast lookup for gc_inode list

[Chao Yu]

Hi Changman,

> -----Original Message-----
> From: Changman Lee [mailto:cm224.lee@samsung.com]
> Sent: Tuesday, December 02, 2014 8:38 AM
> To: Jaegeuk Kim
> Cc: linux-fsdevel@vger.kernel.org; linux-f2fs-devel@lists.sourceforge.net
> Subject: Re: [f2fs-dev] [PATCH V2] f2fs: more fast lookup for gc_inode list
> 
> Hi Jaeguek,
> 
> Thansk for review.
> 
> Changes from V2
>  o rename iradix to iroot
>  o declare gc_inode_list in gc.h
> 
> Changes from V1
>  o introduce gc_inode_list containing ilist and iradix
>  o use local variable
>  o call radix_tree_delete before iput
>  o retry to add inode into radix_tree
>  o call list_del explicitly
> 
> Regards,
> Changman
> 
> --> 8 --
> >From 6c32edfc00aa784c47f5018d10fb8f9b5ab54c8b Mon Sep 17 00:00:00 2001
> From: Changman Lee <cm224.lee@samsung.com>
> Date: Fri, 28 Nov 2014 15:49:40 +0000
> Subject: [PATCH] f2fs: more fast lookup for gc_inode list
> 
> If there are many inodes that have data blocks in victim segment,
> it takes long time to find a inode in gc_inode list.
> Let's use radix_tree to reduce lookup time.
> 
> Signed-off-by: Changman Lee <cm224.lee@samsung.com>
> ---
>  fs/f2fs/gc.c | 51 ++++++++++++++++++++++++++++++---------------------
>  fs/f2fs/gc.h |  5 +++++
>  2 files changed, 35 insertions(+), 21 deletions(-)
> 
> diff --git a/fs/f2fs/gc.c b/fs/f2fs/gc.c
> index 29fc7e5..92f706c 100644
> --- a/fs/f2fs/gc.c
> +++ b/fs/f2fs/gc.c
> @@ -338,34 +338,41 @@ static const struct victim_selection default_v_ops = {
>  	.get_victim = get_victim_by_default,
>  };
> 
> -static struct inode *find_gc_inode(nid_t ino, struct list_head *ilist)
> +static struct inode *find_gc_inode(struct gc_inode_list *gc_list, nid_t ino)
>  {
>  	struct inode_entry *ie;
> 
> -	list_for_each_entry(ie, ilist, list)
> -		if (ie->inode->i_ino == ino)
> -			return ie->inode;
> +	ie = radix_tree_lookup(&gc_list->iroot, ino);
> +	if (ie)
> +		return ie->inode;
>  	return NULL;
>  }
> 
> -static void add_gc_inode(struct inode *inode, struct list_head *ilist)
> +static void add_gc_inode(struct gc_inode_list *gc_list, struct inode *inode)
>  {
>  	struct inode_entry *new_ie;
> +	int ret;
> +retry:
> +	new_ie = f2fs_kmem_cache_alloc(winode_slab, GFP_NOFS);
> +	new_ie->inode = inode;
> 
> -	if (inode == find_gc_inode(inode->i_ino, ilist)) {

How about keeping the original code structure like below?
	if find_gc_inode succ
		iput and return;
	else
		alloc and insert a new item;
So we can avoid invoking many unneeded kmem_cache_{alloc, free} when most data blocks
in victim section are belong to the same inode.

Thanks,
Yu

> +	ret = radix_tree_insert(&gc_list->iroot, inode->i_ino, new_ie);
> +	if (ret == -EEXIST) {
> +		kmem_cache_free(winode_slab, new_ie);
>  		iput(inode);
>  		return;
> +	} else if (ret) {
> +		kmem_cache_free(winode_slab, new_ie);
> +		goto retry;
>  	}
> -

[snip]

Re: [f2fs-dev] [PATCH V2] f2fs: more fast lookup for gc_inode list

[Changman Lee]

Hi Yu,

Thanks for your review.

Changes from V3
  o check if entry exists to avoid many kmem_cache_{alloc, free}

Changes from V2
  o rename iradix to iroot
  o declare gc_inode_list in gc.h

 Changes from V1
  o introduce gc_inode_list containing ilist and iradix
  o use local variable
  o call radix_tree_delete before iput
  o retry to add inode into radix_tree
  o call list_del explicitly

--> 8 --
>From 0c2c0d7da997ca90f3101e6195f3ed72fb1940d3 Mon Sep 17 00:00:00 2001
From: Changman Lee <cm224.lee@samsung.com>
Date: Fri, 28 Nov 2014 15:49:40 +0000
Subject: [PATCH] f2fs: more fast lookup for gc_inode list

If there are many inodes that have data blocks in victim segment,
it takes long time to find a inode in gc_inode list.
Let's use radix_tree to reduce lookup time.

Signed-off-by: Changman Lee <cm224.lee@samsung.com>
---
 fs/f2fs/gc.c | 48 +++++++++++++++++++++++++++++-------------------
 fs/f2fs/gc.h |  5 +++++
 2 files changed, 34 insertions(+), 19 deletions(-)

diff --git a/fs/f2fs/gc.c b/fs/f2fs/gc.c
index 29fc7e5..75b1d71 100644
--- a/fs/f2fs/gc.c
+++ b/fs/f2fs/gc.c
@@ -338,34 +338,42 @@ static const struct victim_selection default_v_ops = {
 	.get_victim = get_victim_by_default,
 };
 
-static struct inode *find_gc_inode(nid_t ino, struct list_head *ilist)
+static struct inode *find_gc_inode(struct gc_inode_list *gc_list, nid_t ino)
 {
 	struct inode_entry *ie;
 
-	list_for_each_entry(ie, ilist, list)
-		if (ie->inode->i_ino == ino)
-			return ie->inode;
+	ie = radix_tree_lookup(&gc_list->iroot, ino);
+	if (ie)
+		return ie->inode;
 	return NULL;
 }
 
-static void add_gc_inode(struct inode *inode, struct list_head *ilist)
+static void add_gc_inode(struct gc_inode_list *gc_list, struct inode *inode)
 {
 	struct inode_entry *new_ie;
+	int ret;
 
-	if (inode == find_gc_inode(inode->i_ino, ilist)) {
+	if (inode == find_gc_inode(gc_list, inode->i_ino)) {
 		iput(inode);
 		return;
 	}
-
+retry:
 	new_ie = f2fs_kmem_cache_alloc(winode_slab, GFP_NOFS);
 	new_ie->inode = inode;
-	list_add_tail(&new_ie->list, ilist);
+
+	ret = radix_tree_insert(&gc_list->iroot, inode->i_ino, new_ie);
+	if (ret) {
+		kmem_cache_free(winode_slab, new_ie);
+		goto retry;
+	}
+	list_add_tail(&new_ie->list, &gc_list->ilist);
 }
 
-static void put_gc_inode(struct list_head *ilist)
+static void put_gc_inode(struct gc_inode_list *gc_list)
 {
 	struct inode_entry *ie, *next_ie;
-	list_for_each_entry_safe(ie, next_ie, ilist, list) {
+	list_for_each_entry_safe(ie, next_ie, &gc_list->ilist, list) {
+		radix_tree_delete(&gc_list->iroot, ie->inode->i_ino);
 		iput(ie->inode);
 		list_del(&ie->list);
 		kmem_cache_free(winode_slab, ie);
@@ -551,7 +559,7 @@ out:
  * the victim data block is ignored.
  */
 static void gc_data_segment(struct f2fs_sb_info *sbi, struct f2fs_summary *sum,
-		struct list_head *ilist, unsigned int segno, int gc_type)
+		struct gc_inode_list *gc_list, unsigned int segno, int gc_type)
 {
 	struct super_block *sb = sbi->sb;
 	struct f2fs_summary *entry;
@@ -609,12 +617,12 @@ next_step:
 			}
 
 			f2fs_put_page(data_page, 0);
-			add_gc_inode(inode, ilist);
+			add_gc_inode(gc_list, inode);
 			continue;
 		}
 
 		/* phase 3 */
-		inode = find_gc_inode(dni.ino, ilist);
+		inode = find_gc_inode(gc_list, dni.ino);
 		if (inode) {
 			start_bidx = start_bidx_of_node(nofs,
 							F2FS_I(inode));
@@ -658,7 +666,7 @@ static int __get_victim(struct f2fs_sb_info *sbi, unsigned int *victim,
 }
 
 static void do_garbage_collect(struct f2fs_sb_info *sbi, unsigned int segno,
-				struct list_head *ilist, int gc_type)
+				struct gc_inode_list *gc_list, int gc_type)
 {
 	struct page *sum_page;
 	struct f2fs_summary_block *sum;
@@ -676,7 +684,7 @@ static void do_garbage_collect(struct f2fs_sb_info *sbi, unsigned int segno,
 		gc_node_segment(sbi, sum->entries, segno, gc_type);
 		break;
 	case SUM_TYPE_DATA:
-		gc_data_segment(sbi, sum->entries, ilist, segno, gc_type);
+		gc_data_segment(sbi, sum->entries, gc_list, segno, gc_type);
 		break;
 	}
 	blk_finish_plug(&plug);
@@ -689,16 +697,18 @@ static void do_garbage_collect(struct f2fs_sb_info *sbi, unsigned int segno,
 
 int f2fs_gc(struct f2fs_sb_info *sbi)
 {
-	struct list_head ilist;
 	unsigned int segno, i;
 	int gc_type = BG_GC;
 	int nfree = 0;
 	int ret = -1;
 	struct cp_control cpc;
+	struct gc_inode_list gc_list = {
+		.ilist = LIST_HEAD_INIT(gc_list.ilist),
+		.iroot = RADIX_TREE_INIT(GFP_ATOMIC),
+	};
 
 	cpc.reason = test_opt(sbi, FASTBOOT) ? CP_UMOUNT : CP_SYNC;
 
-	INIT_LIST_HEAD(&ilist);
 gc_more:
 	if (unlikely(!(sbi->sb->s_flags & MS_ACTIVE)))
 		goto stop;
@@ -720,7 +730,7 @@ gc_more:
 								META_SSA);
 
 	for (i = 0; i < sbi->segs_per_sec; i++)
-		do_garbage_collect(sbi, segno + i, &ilist, gc_type);
+		do_garbage_collect(sbi, segno + i, &gc_list, gc_type);
 
 	if (gc_type == FG_GC) {
 		sbi->cur_victim_sec = NULL_SEGNO;
@@ -736,7 +746,7 @@ gc_more:
 stop:
 	mutex_unlock(&sbi->gc_mutex);
 
-	put_gc_inode(&ilist);
+	put_gc_inode(&gc_list);
 	return ret;
 }
 
diff --git a/fs/f2fs/gc.h b/fs/f2fs/gc.h
index 16f0b2b..6ff7ad3 100644
--- a/fs/f2fs/gc.h
+++ b/fs/f2fs/gc.h
@@ -40,6 +40,11 @@ struct inode_entry {
 	struct inode *inode;
 };
 
+struct gc_inode_list {
+	struct list_head ilist;
+	struct radix_tree_root iroot;
+};
+
 /*
  * inline functions
  */
-- 
1.9.1