* [PATCH] f2fs: more fast lookup for gc_inode list
@ 2014-11-27 9:11 Changman Lee
2014-11-28 4:24 ` [f2fs-dev] " Jaegeuk Kim
0 siblings, 1 reply; 8+ messages in thread
From: Changman Lee @ 2014-11-27 9:11 UTC (permalink / raw)
To: linux-fsdevel, linux-f2fs-devel; +Cc: 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
^ permalink raw reply related [flat|nested] 8+ messages in thread
* Re: [f2fs-dev] [PATCH] f2fs: more fast lookup for gc_inode list
2014-11-27 9:11 [PATCH] f2fs: more fast lookup for gc_inode list Changman Lee
@ 2014-11-28 4:24 ` Jaegeuk Kim
2014-11-28 6:00 ` Changman Lee
0 siblings, 1 reply; 8+ messages in thread
From: Jaegeuk Kim @ 2014-11-28 4:24 UTC (permalink / raw)
To: Changman Lee; +Cc: linux-fsdevel, linux-f2fs-devel
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
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [f2fs-dev] [PATCH] f2fs: more fast lookup for gc_inode list
2014-11-28 4:24 ` [f2fs-dev] " Jaegeuk Kim
@ 2014-11-28 6:00 ` Changman Lee
2014-11-28 7:12 ` [f2fs-dev] [PATCH V2] " Changman Lee
0 siblings, 1 reply; 8+ messages in thread
From: Changman Lee @ 2014-11-28 6:00 UTC (permalink / raw)
To: Jaegeuk Kim; +Cc: linux-fsdevel, linux-f2fs-devel
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
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [f2fs-dev] [PATCH V2] f2fs: more fast lookup for gc_inode list
2014-11-28 6:00 ` Changman Lee
@ 2014-11-28 7:12 ` Changman Lee
2014-12-01 21:55 ` Jaegeuk Kim
0 siblings, 1 reply; 8+ messages in thread
From: Changman Lee @ 2014-11-28 7:12 UTC (permalink / raw)
To: Jaegeuk Kim; +Cc: linux-fsdevel, linux-f2fs-devel
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
^ permalink raw reply related [flat|nested] 8+ messages in thread
* Re: [f2fs-dev] [PATCH V2] f2fs: more fast lookup for gc_inode list
2014-11-28 7:12 ` [f2fs-dev] [PATCH V2] " Changman Lee
@ 2014-12-01 21:55 ` Jaegeuk Kim
2014-12-02 0:38 ` Changman Lee
0 siblings, 1 reply; 8+ messages in thread
From: Jaegeuk Kim @ 2014-12-01 21:55 UTC (permalink / raw)
To: Changman Lee; +Cc: linux-fsdevel, linux-f2fs-devel
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
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [f2fs-dev] [PATCH V2] f2fs: more fast lookup for gc_inode list
2014-12-01 21:55 ` Jaegeuk Kim
@ 2014-12-02 0:38 ` Changman Lee
2014-12-02 9:25 ` Chao Yu
0 siblings, 1 reply; 8+ messages in thread
From: Changman Lee @ 2014-12-02 0:38 UTC (permalink / raw)
To: Jaegeuk Kim; +Cc: linux-fsdevel, linux-f2fs-devel
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
^ permalink raw reply related [flat|nested] 8+ messages in thread
* RE: [f2fs-dev] [PATCH V2] f2fs: more fast lookup for gc_inode list
2014-12-02 0:38 ` Changman Lee
@ 2014-12-02 9:25 ` Chao Yu
2014-12-02 9:56 ` Changman Lee
0 siblings, 1 reply; 8+ messages in thread
From: Chao Yu @ 2014-12-02 9:25 UTC (permalink / raw)
To: 'Changman Lee', 'Jaegeuk Kim'
Cc: linux-fsdevel, linux-f2fs-devel
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]
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: [f2fs-dev] [PATCH V2] f2fs: more fast lookup for gc_inode list
2014-12-02 9:25 ` Chao Yu
@ 2014-12-02 9:56 ` Changman Lee
0 siblings, 0 replies; 8+ messages in thread
From: Changman Lee @ 2014-12-02 9:56 UTC (permalink / raw)
To: Chao Yu; +Cc: 'Jaegeuk Kim', linux-fsdevel, linux-f2fs-devel
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
^ permalink raw reply related [flat|nested] 8+ messages in thread
end of thread, other threads:[~2014-12-02 9:56 UTC | newest]
Thread overview: 8+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2014-11-27 9:11 [PATCH] f2fs: more fast lookup for gc_inode list Changman Lee
2014-11-28 4:24 ` [f2fs-dev] " Jaegeuk Kim
2014-11-28 6:00 ` Changman Lee
2014-11-28 7:12 ` [f2fs-dev] [PATCH V2] " Changman Lee
2014-12-01 21:55 ` Jaegeuk Kim
2014-12-02 0:38 ` Changman Lee
2014-12-02 9:25 ` Chao Yu
2014-12-02 9:56 ` Changman Lee
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).