[f2fs-dev] [PATCH v2 04/10] f2fs: introduce universal lookup/update interface of extent cache

2015-01-25 Thread Chao Yu
In this patch, we do these jobs:
1. rename {check,update}_extent_cache to {lookup,update}_extent_info;
2. introduce universal lookup/update interface of extent cache:
f2fs_{lookup,update}_extent_cache including above two real functions, then
export them to function callers.

So after above cleanup, we can add new rb-tree based extent cache into exported
interfaces.

v2:
 o remove f2fs_ for inner function {lookup,update}_extent_info suggested by
   Jaegeuk Kim.

Signed-off-by: Chao Yu chao2...@samsung.com
---
 fs/f2fs/data.c | 66 +-
 fs/f2fs/f2fs.h |  2 +-
 fs/f2fs/file.c |  2 +-
 fs/f2fs/inline.c   |  2 +-
 fs/f2fs/recovery.c |  2 +-
 5 files changed, 44 insertions(+), 30 deletions(-)

diff --git a/fs/f2fs/data.c b/fs/f2fs/data.c
index 09e1e36..69b0781 100644
--- a/fs/f2fs/data.c
+++ b/fs/f2fs/data.c
@@ -263,20 +263,20 @@ static void f2fs_map_bh(struct super_block *sb, pgoff_t 
pgofs,
bh_result-b_size = UINT_MAX;
 }
 
-static int check_extent_cache(struct inode *inode, pgoff_t pgofs,
-   struct extent_info *ei)
+static bool lookup_extent_info(struct inode *inode, pgoff_t pgofs,
+   struct extent_info *ei)
 {
struct f2fs_inode_info *fi = F2FS_I(inode);
pgoff_t start_fofs, end_fofs;
block_t start_blkaddr;
 
if (is_inode_flag_set(fi, FI_NO_EXTENT))
-   return 0;
+   return false;
 
read_lock(fi-ext_lock);
if (fi-ext.len == 0) {
read_unlock(fi-ext_lock);
-   return 0;
+   return false;
}
 
stat_inc_total_hit(inode-i_sb);
@@ -289,29 +289,22 @@ static int check_extent_cache(struct inode *inode, 
pgoff_t pgofs,
*ei = fi-ext;
stat_inc_read_hit(inode-i_sb);
read_unlock(fi-ext_lock);
-   return 1;
+   return true;
}
read_unlock(fi-ext_lock);
-   return 0;
+   return false;
 }
 
-void update_extent_cache(struct dnode_of_data *dn)
+static bool update_extent_info(struct inode *inode, pgoff_t fofs,
+   block_t blkaddr)
 {
-   struct f2fs_inode_info *fi = F2FS_I(dn-inode);
-   pgoff_t fofs, start_fofs, end_fofs;
+   struct f2fs_inode_info *fi = F2FS_I(inode);
+   pgoff_t start_fofs, end_fofs;
block_t start_blkaddr, end_blkaddr;
int need_update = true;
 
-   f2fs_bug_on(F2FS_I_SB(dn-inode), dn-data_blkaddr == NEW_ADDR);
-
-   /* Update the page address in the parent node */
-   __set_data_blkaddr(dn);
-
if (is_inode_flag_set(fi, FI_NO_EXTENT))
-   return;
-
-   fofs = start_bidx_of_node(ofs_of_node(dn-node_page), fi) +
-   dn-ofs_in_node;
+   return false;
 
write_lock(fi-ext_lock);
 
@@ -326,16 +319,16 @@ void update_extent_cache(struct dnode_of_data *dn)
 
/* Initial extent */
if (fi-ext.len == 0) {
-   if (dn-data_blkaddr != NULL_ADDR) {
+   if (blkaddr != NULL_ADDR) {
fi-ext.fofs = fofs;
-   fi-ext.blk = dn-data_blkaddr;
+   fi-ext.blk = blkaddr;
fi-ext.len = 1;
}
goto end_update;
}
 
/* Front merge */
-   if (fofs == start_fofs - 1  dn-data_blkaddr == start_blkaddr - 1) {
+   if (fofs == start_fofs - 1  blkaddr == start_blkaddr - 1) {
fi-ext.fofs--;
fi-ext.blk--;
fi-ext.len++;
@@ -343,7 +336,7 @@ void update_extent_cache(struct dnode_of_data *dn)
}
 
/* Back merge */
-   if (fofs == end_fofs + 1  dn-data_blkaddr == end_blkaddr + 1) {
+   if (fofs == end_fofs + 1  blkaddr == end_blkaddr + 1) {
fi-ext.len++;
goto end_update;
}
@@ -370,9 +363,30 @@ void update_extent_cache(struct dnode_of_data *dn)
}
 end_update:
write_unlock(fi-ext_lock);
-   if (need_update)
+   return need_update;
+}
+
+static bool f2fs_lookup_extent_cache(struct inode *inode, pgoff_t pgofs,
+   struct extent_info *ei)
+{
+   return lookup_extent_info(inode, pgofs, ei);
+}
+
+void f2fs_update_extent_cache(struct dnode_of_data *dn)
+{
+   struct f2fs_inode_info *fi = F2FS_I(dn-inode);
+   pgoff_t fofs;
+
+   f2fs_bug_on(F2FS_I_SB(dn-inode), dn-data_blkaddr == NEW_ADDR);
+
+   /* Update the page address in the parent node */
+   __set_data_blkaddr(dn);
+
+   fofs = start_bidx_of_node(ofs_of_node(dn-node_page), fi) +
+   dn-ofs_in_node;
+
+   if (update_extent_info(dn-inode, fofs, dn-data_blkaddr))

[f2fs-dev] [PATCH v2 03/10] f2fs: introduce f2fs_map_bh to simplify codes of check_extent_cache

2015-01-25 Thread Chao Yu
This patch introduces f2fs_map_bh to simplify codes of check_extent_cache.

v2:
 o clean up f2fs_map_bh pointed out by Jaegeuk Kim.

Signed-off-by: Chao Yu chao2...@samsung.com
---
 fs/f2fs/data.c | 35 +--
 1 file changed, 21 insertions(+), 14 deletions(-)

diff --git a/fs/f2fs/data.c b/fs/f2fs/data.c
index 935a23b..09e1e36 100644
--- a/fs/f2fs/data.c
+++ b/fs/f2fs/data.c
@@ -248,8 +248,23 @@ int f2fs_reserve_block(struct dnode_of_data *dn, pgoff_t 
index)
return err;
 }
 
+static void f2fs_map_bh(struct super_block *sb, pgoff_t pgofs,
+   struct extent_info *ei, struct buffer_head *bh_result)
+{
+   unsigned int blkbits = sb-s_blocksize_bits;
+   size_t count;
+
+   clear_buffer_new(bh_result);
+   map_bh(bh_result, sb, ei-blk + pgofs - ei-fofs);
+   count = ei-fofs + ei-len - pgofs;
+   if (count  (UINT_MAX  blkbits))
+   bh_result-b_size = (count  blkbits);
+   else
+   bh_result-b_size = UINT_MAX;
+}
+
 static int check_extent_cache(struct inode *inode, pgoff_t pgofs,
-   struct buffer_head *bh_result)
+   struct extent_info *ei)
 {
struct f2fs_inode_info *fi = F2FS_I(inode);
pgoff_t start_fofs, end_fofs;
@@ -271,18 +286,7 @@ static int check_extent_cache(struct inode *inode, pgoff_t 
pgofs,
start_blkaddr = fi-ext.blk;
 
if (pgofs = start_fofs  pgofs = end_fofs) {
-   unsigned int blkbits = inode-i_sb-s_blocksize_bits;
-   size_t count;
-
-   clear_buffer_new(bh_result);
-   map_bh(bh_result, inode-i_sb,
-   start_blkaddr + pgofs - start_fofs);
-   count = end_fofs - pgofs + 1;
-   if (count  (UINT_MAX  blkbits))
-   bh_result-b_size = (count  blkbits);
-   else
-   bh_result-b_size = UINT_MAX;
-
+   *ei = fi-ext;
stat_inc_read_hit(inode-i_sb);
read_unlock(fi-ext_lock);
return 1;
@@ -608,13 +612,16 @@ static int __get_data_block(struct inode *inode, sector_t 
iblock,
int mode = create ? ALLOC_NODE : LOOKUP_NODE_RA;
pgoff_t pgofs, end_offset;
int err = 0, ofs = 1;
+   struct extent_info ei;
bool allocated = false;
 
/* Get the page offset from the block offset(iblock) */
pgofs = (pgoff_t)(iblock  (PAGE_CACHE_SHIFT - blkbits));
 
-   if (check_extent_cache(inode, pgofs, bh_result))
+   if (check_extent_cache(inode, pgofs, ei)) {
+   f2fs_map_bh(inode-i_sb, pgofs, ei, bh_result);
goto out;
+   }
 
if (create) {
f2fs_balance_fs(F2FS_I_SB(inode));
-- 
2.2.1



--
Dive into the World of Parallel Programming. The Go Parallel Website,
sponsored by Intel and developed in partnership with Slashdot Media, is your
hub for all things parallel software development, from weekly thought
leadership blogs to news, videos, case studies, tutorials and more. Take a
look and join the conversation now. http://goparallel.sourceforge.net/
___
Linux-f2fs-devel mailing list
Linux-f2fs-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel


[f2fs-dev] [PATCH v2 01/10] f2fs: move ext_lock out of struct extent_info

2015-01-25 Thread Chao Yu
Move ext_lock out of struct extent_info, then in the following patches we can
use variables with struct extent_info type as a parameter to pass pure data.

Signed-off-by: Chao Yu chao2...@samsung.com
---
 fs/f2fs/data.c  | 12 ++--
 fs/f2fs/f2fs.h  |  6 +-
 fs/f2fs/inode.c |  7 +++
 fs/f2fs/super.c |  2 +-
 4 files changed, 15 insertions(+), 12 deletions(-)

diff --git a/fs/f2fs/data.c b/fs/f2fs/data.c
index a7b905c..fece5cc 100644
--- a/fs/f2fs/data.c
+++ b/fs/f2fs/data.c
@@ -258,9 +258,9 @@ static int check_extent_cache(struct inode *inode, pgoff_t 
pgofs,
if (is_inode_flag_set(fi, FI_NO_EXTENT))
return 0;
 
-   read_lock(fi-ext.ext_lock);
+   read_lock(fi-ext_lock);
if (fi-ext.len == 0) {
-   read_unlock(fi-ext.ext_lock);
+   read_unlock(fi-ext_lock);
return 0;
}
 
@@ -284,10 +284,10 @@ static int check_extent_cache(struct inode *inode, 
pgoff_t pgofs,
bh_result-b_size = UINT_MAX;
 
stat_inc_read_hit(inode-i_sb);
-   read_unlock(fi-ext.ext_lock);
+   read_unlock(fi-ext_lock);
return 1;
}
-   read_unlock(fi-ext.ext_lock);
+   read_unlock(fi-ext_lock);
return 0;
 }
 
@@ -309,7 +309,7 @@ void update_extent_cache(struct dnode_of_data *dn)
fofs = start_bidx_of_node(ofs_of_node(dn-node_page), fi) +
dn-ofs_in_node;
 
-   write_lock(fi-ext.ext_lock);
+   write_lock(fi-ext_lock);
 
start_fofs = fi-ext.fofs;
end_fofs = fi-ext.fofs + fi-ext.len - 1;
@@ -366,7 +366,7 @@ void update_extent_cache(struct dnode_of_data *dn)
need_update = true;
}
 end_update:
-   write_unlock(fi-ext.ext_lock);
+   write_unlock(fi-ext_lock);
if (need_update)
sync_inode_page(dn);
return;
diff --git a/fs/f2fs/f2fs.h b/fs/f2fs/f2fs.h
index 1795ce2..f1452a3 100644
--- a/fs/f2fs/f2fs.h
+++ b/fs/f2fs/f2fs.h
@@ -271,7 +271,6 @@ enum {
 #define F2FS_MIN_EXTENT_LEN16  /* minimum extent length */
 
 struct extent_info {
-   rwlock_t ext_lock;  /* rwlock for consistency */
unsigned int fofs;  /* start offset in a file */
u32 blk_addr;   /* start block address of the extent */
unsigned int len;   /* length of the extent */
@@ -303,6 +302,7 @@ struct f2fs_inode_info {
nid_t i_xattr_nid;  /* node id that contains xattrs */
unsigned long long xattr_ver;   /* cp version of xattr modification */
struct extent_info ext; /* in-memory extent cache entry */
+   rwlock_t ext_lock;  /* rwlock for single extent cache */
struct inode_entry *dirty_dir;  /* the pointer of dirty dir */
 
struct radix_tree_root inmem_root;  /* radix tree for inmem pages */
@@ -313,21 +313,17 @@ struct f2fs_inode_info {
 static inline void get_extent_info(struct extent_info *ext,
struct f2fs_extent i_ext)
 {
-   write_lock(ext-ext_lock);
ext-fofs = le32_to_cpu(i_ext.fofs);
ext-blk_addr = le32_to_cpu(i_ext.blk_addr);
ext-len = le32_to_cpu(i_ext.len);
-   write_unlock(ext-ext_lock);
 }
 
 static inline void set_raw_extent(struct extent_info *ext,
struct f2fs_extent *i_ext)
 {
-   read_lock(ext-ext_lock);
i_ext-fofs = cpu_to_le32(ext-fofs);
i_ext-blk_addr = cpu_to_le32(ext-blk_addr);
i_ext-len = cpu_to_le32(ext-len);
-   read_unlock(ext-ext_lock);
 }
 
 struct f2fs_nm_info {
diff --git a/fs/f2fs/inode.c b/fs/f2fs/inode.c
index 2d002e3..28dd26a 100644
--- a/fs/f2fs/inode.c
+++ b/fs/f2fs/inode.c
@@ -130,7 +130,10 @@ static int do_read_inode(struct inode *inode)
fi-i_pino = le32_to_cpu(ri-i_pino);
fi-i_dir_level = ri-i_dir_level;
 
+   write_lock(fi-ext_lock);
get_extent_info(fi-ext, ri-i_ext);
+   write_unlock(fi-ext_lock);
+
get_inline_info(fi, ri);
 
/* check data exist */
@@ -220,7 +223,11 @@ void update_inode(struct inode *inode, struct page 
*node_page)
ri-i_links = cpu_to_le32(inode-i_nlink);
ri-i_size = cpu_to_le64(i_size_read(inode));
ri-i_blocks = cpu_to_le64(inode-i_blocks);
+
+   read_lock(F2FS_I(inode)-ext_lock);
set_raw_extent(F2FS_I(inode)-ext, ri-i_ext);
+   read_unlock(F2FS_I(inode)-ext_lock);
+
set_raw_inline(F2FS_I(inode), ri);
 
ri-i_atime = cpu_to_le64(inode-i_atime.tv_sec);
diff --git a/fs/f2fs/super.c b/fs/f2fs/super.c
index 0d627f2..5706c17 100644
--- a/fs/f2fs/super.c
+++ b/fs/f2fs/super.c
@@ -382,7 +382,7 @@ static struct inode *f2fs_alloc_inode(struct super_block 
*sb)
atomic_set(fi-dirty_pages, 0);
fi-i_current_depth = 1;
fi-i_advise = 0;
-   rwlock_init(fi-ext.ext_lock);
+   rwlock_init(fi-ext_lock);

[f2fs-dev] [PATCH v2 02/10] f2fs: simplfy a field name in struct f2fs_extent, extent_info

2015-01-25 Thread Chao Yu
Rename a filed name from 'blk_addr' to 'blk' in struct {f2fs_extent,extent_info}
as annotation of this field descripts its meaning well to us.

By this way, we can avoid long statement in code of following patches.

Signed-off-by: Chao Yu chao2...@samsung.com
---
 fs/f2fs/data.c  | 13 ++---
 fs/f2fs/f2fs.h  |  6 +++---
 include/linux/f2fs_fs.h |  2 +-
 3 files changed, 10 insertions(+), 11 deletions(-)

diff --git a/fs/f2fs/data.c b/fs/f2fs/data.c
index fece5cc..935a23b 100644
--- a/fs/f2fs/data.c
+++ b/fs/f2fs/data.c
@@ -268,7 +268,7 @@ static int check_extent_cache(struct inode *inode, pgoff_t 
pgofs,
 
start_fofs = fi-ext.fofs;
end_fofs = fi-ext.fofs + fi-ext.len - 1;
-   start_blkaddr = fi-ext.blk_addr;
+   start_blkaddr = fi-ext.blk;
 
if (pgofs = start_fofs  pgofs = end_fofs) {
unsigned int blkbits = inode-i_sb-s_blocksize_bits;
@@ -313,8 +313,8 @@ void update_extent_cache(struct dnode_of_data *dn)
 
start_fofs = fi-ext.fofs;
end_fofs = fi-ext.fofs + fi-ext.len - 1;
-   start_blkaddr = fi-ext.blk_addr;
-   end_blkaddr = fi-ext.blk_addr + fi-ext.len - 1;
+   start_blkaddr = fi-ext.blk;
+   end_blkaddr = fi-ext.blk + fi-ext.len - 1;
 
/* Drop and initialize the matched extent */
if (fi-ext.len == 1  fofs == start_fofs)
@@ -324,7 +324,7 @@ void update_extent_cache(struct dnode_of_data *dn)
if (fi-ext.len == 0) {
if (dn-data_blkaddr != NULL_ADDR) {
fi-ext.fofs = fofs;
-   fi-ext.blk_addr = dn-data_blkaddr;
+   fi-ext.blk = dn-data_blkaddr;
fi-ext.len = 1;
}
goto end_update;
@@ -333,7 +333,7 @@ void update_extent_cache(struct dnode_of_data *dn)
/* Front merge */
if (fofs == start_fofs - 1  dn-data_blkaddr == start_blkaddr - 1) {
fi-ext.fofs--;
-   fi-ext.blk_addr--;
+   fi-ext.blk--;
fi-ext.len++;
goto end_update;
}
@@ -351,8 +351,7 @@ void update_extent_cache(struct dnode_of_data *dn)
fi-ext.len = fofs - start_fofs;
} else {
fi-ext.fofs = fofs + 1;
-   fi-ext.blk_addr = start_blkaddr +
-   fofs - start_fofs + 1;
+   fi-ext.blk = start_blkaddr + fofs - start_fofs + 1;
fi-ext.len -= fofs - start_fofs + 1;
}
} else {
diff --git a/fs/f2fs/f2fs.h b/fs/f2fs/f2fs.h
index f1452a3..f67efec 100644
--- a/fs/f2fs/f2fs.h
+++ b/fs/f2fs/f2fs.h
@@ -272,7 +272,7 @@ enum {
 
 struct extent_info {
unsigned int fofs;  /* start offset in a file */
-   u32 blk_addr;   /* start block address of the extent */
+   u32 blk;/* start block address of the extent */
unsigned int len;   /* length of the extent */
 };
 
@@ -314,7 +314,7 @@ static inline void get_extent_info(struct extent_info *ext,
struct f2fs_extent i_ext)
 {
ext-fofs = le32_to_cpu(i_ext.fofs);
-   ext-blk_addr = le32_to_cpu(i_ext.blk_addr);
+   ext-blk = le32_to_cpu(i_ext.blk);
ext-len = le32_to_cpu(i_ext.len);
 }
 
@@ -322,7 +322,7 @@ static inline void set_raw_extent(struct extent_info *ext,
struct f2fs_extent *i_ext)
 {
i_ext-fofs = cpu_to_le32(ext-fofs);
-   i_ext-blk_addr = cpu_to_le32(ext-blk_addr);
+   i_ext-blk = cpu_to_le32(ext-blk);
i_ext-len = cpu_to_le32(ext-len);
 }
 
diff --git a/include/linux/f2fs_fs.h b/include/linux/f2fs_fs.h
index e993b0b..295acfa 100644
--- a/include/linux/f2fs_fs.h
+++ b/include/linux/f2fs_fs.h
@@ -148,7 +148,7 @@ struct f2fs_orphan_block {
  */
 struct f2fs_extent {
__le32 fofs;/* start file offset of the extent */
-   __le32 blk_addr;/* start block address of the extent */
+   __le32 blk; /* start block address of the extent */
__le32 len; /* lengh of the extent */
 } __packed;
 
-- 
2.2.1



--
Dive into the World of Parallel Programming. The Go Parallel Website,
sponsored by Intel and developed in partnership with Slashdot Media, is your
hub for all things parallel software development, from weekly thought
leadership blogs to news, videos, case studies, tutorials and more. Take a
look and join the conversation now. http://goparallel.sourceforge.net/
___
Linux-f2fs-devel mailing list
Linux-f2fs-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel


[f2fs-dev] [PATCH v2 08/10] f2fs: enable rb-tree extent cache

2015-01-25 Thread Chao Yu
This patch enables rb-tree based extent cache in f2fs.

When we mount with -o extent_cache, f2fs will try to add recently accessed
page-block mappings into rb-tree based extent cache as much as possible, instead
of original one extent info cache.

By this way, f2fs can support more effective cache between dnode page cache and
disk. It will supply high hit ratio in the cache with fewer memory when dnode
page cache are reclaimed in environment of low memory.

Extent Cache Hit Ratio:
1.write file (size: 64M);
2.write file (offset: 32M, size: 1M);
3.write file (offset: 16M, size: 1M);
4.write file (offset: 48M, size: 1M);
5.echo 3  /proc/sys/vm/drop_caches
6.read file

originalpatched
Hit Ratio   61 / 264264 / 264

Signed-off-by: Chao Yu chao2...@samsung.com
---
 fs/f2fs/data.c| 13 +
 fs/f2fs/f2fs.h|  5 +
 fs/f2fs/inode.c   |  1 +
 fs/f2fs/segment.c |  3 +++
 fs/f2fs/super.c   |  9 -
 5 files changed, 30 insertions(+), 1 deletion(-)

diff --git a/fs/f2fs/data.c b/fs/f2fs/data.c
index 7ba2df9..2325b1c 100644
--- a/fs/f2fs/data.c
+++ b/fs/f2fs/data.c
@@ -665,6 +665,9 @@ void f2fs_shrink_extent_tree(struct f2fs_sb_info *sbi, int 
nr_shrink)
void **slot;
unsigned int found;
 
+   if (!test_opt(sbi, EXTENT_CACHE))
+   return;
+
if (available_free_memory(sbi, EXTENT_CACHE))
return;
 
@@ -713,6 +716,9 @@ void f2fs_destroy_extent_tree(struct inode *inode)
struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
struct extent_tree *et;
 
+   if (!test_opt(sbi, EXTENT_CACHE))
+   return;
+
down_read(sbi-extent_tree_lock);
et = radix_tree_lookup(sbi-extent_tree_root, inode-i_ino);
if (!et) {
@@ -748,6 +754,9 @@ out:
 static bool f2fs_lookup_extent_cache(struct inode *inode, pgoff_t pgofs,
struct extent_info *ei)
 {
+   if (test_opt(F2FS_I_SB(inode), EXTENT_CACHE))
+   return f2fs_lookup_extent_tree(inode, pgofs, ei);
+
return lookup_extent_info(inode, pgofs, ei);
 }
 
@@ -764,6 +773,10 @@ void f2fs_update_extent_cache(struct dnode_of_data *dn)
fofs = start_bidx_of_node(ofs_of_node(dn-node_page), fi) +
dn-ofs_in_node;
 
+   if (test_opt(F2FS_I_SB(dn-inode), EXTENT_CACHE))
+   return f2fs_update_extent_tree(dn-inode, fofs,
+   dn-data_blkaddr);
+
if (update_extent_info(dn-inode, fofs, dn-data_blkaddr))
sync_inode_page(dn);
 }
diff --git a/fs/f2fs/f2fs.h b/fs/f2fs/f2fs.h
index fe74286..c96f451 100644
--- a/fs/f2fs/f2fs.h
+++ b/fs/f2fs/f2fs.h
@@ -1532,12 +1532,17 @@ void f2fs_submit_page_mbio(struct f2fs_sb_info *, 
struct page *,
struct f2fs_io_info *);
 int reserve_new_block(struct dnode_of_data *);
 int f2fs_reserve_block(struct dnode_of_data *, pgoff_t);
+void f2fs_shrink_extent_tree(struct f2fs_sb_info *, int);
+void f2fs_destroy_extent_tree(struct inode *);
 void f2fs_update_extent_cache(struct dnode_of_data *);
 struct page *find_data_page(struct inode *, pgoff_t, bool);
 struct page *get_lock_data_page(struct inode *, pgoff_t);
 struct page *get_new_data_page(struct inode *, struct page *, pgoff_t, bool);
 int do_write_data_page(struct page *, struct f2fs_io_info *);
 int f2fs_fiemap(struct inode *inode, struct fiemap_extent_info *, u64, u64);
+void init_extent_cache_info(struct f2fs_sb_info *);
+int __init create_extent_cache(void);
+void destroy_extent_cache(void);
 
 /*
  * gc.c
diff --git a/fs/f2fs/inode.c b/fs/f2fs/inode.c
index 28dd26a..b508744 100644
--- a/fs/f2fs/inode.c
+++ b/fs/f2fs/inode.c
@@ -335,6 +335,7 @@ void f2fs_evict_inode(struct inode *inode)
 no_delete:
stat_dec_inline_dir(inode);
stat_dec_inline_inode(inode);
+   f2fs_destroy_extent_tree(inode);
invalidate_mapping_pages(NODE_MAPPING(sbi), inode-i_ino, inode-i_ino);
if (xnid)
invalidate_mapping_pages(NODE_MAPPING(sbi), xnid, xnid);
diff --git a/fs/f2fs/segment.c b/fs/f2fs/segment.c
index 31c4e57..d8be623 100644
--- a/fs/f2fs/segment.c
+++ b/fs/f2fs/segment.c
@@ -277,6 +277,9 @@ void f2fs_balance_fs(struct f2fs_sb_info *sbi)
 
 void f2fs_balance_fs_bg(struct f2fs_sb_info *sbi)
 {
+   /* try to shrink extent cache when there is no enough memory */
+   f2fs_shrink_extent_tree(sbi, EXTENT_CACHE_SHRINK_NUMBER);
+
/* check the # of cached NAT entries and prefree segments */
if (try_to_free_nats(sbi, NAT_ENTRY_PER_BLOCK) ||
excess_prefree_segs(sbi) ||
diff --git a/fs/f2fs/super.c b/fs/f2fs/super.c
index 1b88b59..8271b8c 100644
--- a/fs/f2fs/super.c
+++ b/fs/f2fs/super.c
@@ -1062,6 +1062,8 @@ try_onemore:
INIT_LIST_HEAD(sbi-dir_inode_list);
spin_lock_init(sbi-dir_inode_lock);
 
+   

[f2fs-dev] [PATCH v2 07/10] f2fs: add a mount option for rb-tree extent cache

2015-01-25 Thread Chao Yu
This patch adds a mount option 'extent_cache' in f2fs.

It tries to use a rb-tree based extent cache to cache more mapping information
with less memory if this option is set, otherwise we will use the original one
extent info cache.

Suggested-by: Changman Lee cm224@samsung.com
Signed-off-by: Chao Yu chao2...@samsung.com
---
 Documentation/filesystems/f2fs.txt | 4 
 fs/f2fs/f2fs.h | 1 +
 fs/f2fs/super.c| 7 +++
 3 files changed, 12 insertions(+)

diff --git a/Documentation/filesystems/f2fs.txt 
b/Documentation/filesystems/f2fs.txt
index e0950c4..87ae1a2 100644
--- a/Documentation/filesystems/f2fs.txt
+++ b/Documentation/filesystems/f2fs.txt
@@ -138,6 +138,10 @@ nobarrier  This option can be used if 
underlying storage guarantees
 fastboot   This option is used when a system wants to reduce mount
time as much as possible, even though normal performance
   can be sacrificed.
+extent_cache   Enable an extent cache based on rb-tree, it can cache
+   as many as extent which map between contiguous logical
+   address and physical address per inode, resulting in
+   increasing the cache hit ratio.
 
 

 DEBUGFS ENTRIES
diff --git a/fs/f2fs/f2fs.h b/fs/f2fs/f2fs.h
index a77b30f..fe74286 100644
--- a/fs/f2fs/f2fs.h
+++ b/fs/f2fs/f2fs.h
@@ -50,6 +50,7 @@
 #define F2FS_MOUNT_FLUSH_MERGE 0x0400
 #define F2FS_MOUNT_NOBARRIER   0x0800
 #define F2FS_MOUNT_FASTBOOT0x1000
+#define F2FS_MOUNT_EXTENT_CACHE0x2000
 
 #define clear_opt(sbi, option) (sbi-mount_opt.opt = ~F2FS_MOUNT_##option)
 #define set_opt(sbi, option)   (sbi-mount_opt.opt |= F2FS_MOUNT_##option)
diff --git a/fs/f2fs/super.c b/fs/f2fs/super.c
index 5706c17..1b88b59 100644
--- a/fs/f2fs/super.c
+++ b/fs/f2fs/super.c
@@ -56,6 +56,7 @@ enum {
Opt_flush_merge,
Opt_nobarrier,
Opt_fastboot,
+   Opt_extent_cache,
Opt_err,
 };
 
@@ -76,6 +77,7 @@ static match_table_t f2fs_tokens = {
{Opt_flush_merge, flush_merge},
{Opt_nobarrier, nobarrier},
{Opt_fastboot, fastboot},
+   {Opt_extent_cache, extent_cache},
{Opt_err, NULL},
 };
 
@@ -357,6 +359,9 @@ static int parse_options(struct super_block *sb, char 
*options)
case Opt_fastboot:
set_opt(sbi, FASTBOOT);
break;
+   case Opt_extent_cache:
+   set_opt(sbi, EXTENT_CACHE);
+   break;
default:
f2fs_msg(sb, KERN_ERR,
Unrecognized mount option \%s\ or missing 
value,
@@ -589,6 +594,8 @@ static int f2fs_show_options(struct seq_file *seq, struct 
dentry *root)
seq_puts(seq, ,nobarrier);
if (test_opt(sbi, FASTBOOT))
seq_puts(seq, ,fastboot);
+   if (test_opt(sbi, EXTENT_CACHE))
+   seq_puts(seq, ,extent_cache);
seq_printf(seq, ,active_logs=%u, sbi-active_logs);
 
return 0;
-- 
2.2.1



--
Dive into the World of Parallel Programming. The Go Parallel Website,
sponsored by Intel and developed in partnership with Slashdot Media, is your
hub for all things parallel software development, from weekly thought
leadership blogs to news, videos, case studies, tutorials and more. Take a
look and join the conversation now. http://goparallel.sourceforge.net/
___
Linux-f2fs-devel mailing list
Linux-f2fs-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel


[f2fs-dev] [PATCH v2 10/10] f2fs: add trace for rb-tree extent cache ops

2015-01-25 Thread Chao Yu
This patch adds trace for lookup/update/shrink/destroy ops in rb-tree extent 
cache.

Signed-off-by: Chao Yu chao2...@samsung.com
---
 fs/f2fs/data.c  |  16 +-
 include/trace/events/f2fs.h | 134 
 2 files changed, 148 insertions(+), 2 deletions(-)

diff --git a/fs/f2fs/data.c b/fs/f2fs/data.c
index 2325b1c..aff497e 100644
--- a/fs/f2fs/data.c
+++ b/fs/f2fs/data.c
@@ -533,6 +533,8 @@ static bool f2fs_lookup_extent_tree(struct inode *inode, 
pgoff_t pgofs,
if (is_inode_flag_set(F2FS_I(inode), FI_NO_EXTENT))
return false;
 
+   trace_f2fs_lookup_extent_tree_start(inode, pgofs);
+
down_read(sbi-extent_tree_lock);
et = radix_tree_lookup(sbi-extent_tree_root, inode-i_ino);
if (!et) {
@@ -555,6 +557,8 @@ static bool f2fs_lookup_extent_tree(struct inode *inode, 
pgoff_t pgofs,
stat_inc_total_hit(sbi-sb);
read_unlock(et-lock);
 
+   trace_f2fs_lookup_extent_tree_end(inode, pgofs, en);
+
atomic_dec(et-refcount);
return en ? true : false;
 }
@@ -573,6 +577,8 @@ static void f2fs_update_extent_tree(struct inode *inode, 
pgoff_t fofs,
if (is_inode_flag_set(F2FS_I(inode), FI_NO_EXTENT))
return;
 
+   trace_f2fs_update_extent_tree(inode, fofs, blkaddr);
+
down_write(sbi-extent_tree_lock);
et = radix_tree_lookup(sbi-extent_tree_root, ino);
if (!et) {
@@ -664,6 +670,7 @@ void f2fs_shrink_extent_tree(struct f2fs_sb_info *sbi, int 
nr_shrink)
struct radix_tree_iter iter;
void **slot;
unsigned int found;
+   unsigned int node_cnt = 0, tree_cnt = 0;
 
if (!test_opt(sbi, EXTENT_CACHE))
return;
@@ -690,7 +697,7 @@ void f2fs_shrink_extent_tree(struct f2fs_sb_info *sbi, int 
nr_shrink)
 
atomic_inc(et-refcount);
write_lock(et-lock);
-   __free_extent_tree(sbi, et, false);
+   node_cnt += __free_extent_tree(sbi, et, false);
write_unlock(et-lock);
atomic_dec(et-refcount);
}
@@ -706,15 +713,19 @@ void f2fs_shrink_extent_tree(struct f2fs_sb_info *sbi, 
int nr_shrink)
radix_tree_delete(sbi-extent_tree_root, et-ino);
kmem_cache_free(extent_tree_slab, et);
sbi-total_ext_tree--;
+   tree_cnt++;
}
}
up_write(sbi-extent_tree_lock);
+
+   trace_f2fs_shrink_extent_tree(sbi, node_cnt, tree_cnt);
 }
 
 void f2fs_destroy_extent_tree(struct inode *inode)
 {
struct f2fs_sb_info *sbi = F2FS_I_SB(inode);
struct extent_tree *et;
+   unsigned int node_cnt = 0;
 
if (!test_opt(sbi, EXTENT_CACHE))
return;
@@ -730,7 +741,7 @@ void f2fs_destroy_extent_tree(struct inode *inode)
 
/* free all extent info belong to this extent tree */
write_lock(et-lock);
-   __free_extent_tree(sbi, et, true);
+   node_cnt = __free_extent_tree(sbi, et, true);
write_unlock(et-lock);
 
atomic_dec(et-refcount);
@@ -748,6 +759,7 @@ void f2fs_destroy_extent_tree(struct inode *inode)
sbi-total_ext_tree--;
up_write(sbi-extent_tree_lock);
 out:
+   trace_f2fs_destroy_extent_tree(inode, node_cnt);
return;
 }
 
diff --git a/include/trace/events/f2fs.h b/include/trace/events/f2fs.h
index 13992f3..8f53fda 100644
--- a/include/trace/events/f2fs.h
+++ b/include/trace/events/f2fs.h
@@ -1009,6 +1009,140 @@ TRACE_EVENT(f2fs_issue_flush,
__entry-nobarrier ? skip (nobarrier) : issue,
__entry-flush_merge ?  with flush_merge : )
 );
+
+TRACE_EVENT(f2fs_lookup_extent_tree_start,
+
+   TP_PROTO(struct inode *inode, unsigned int pgofs),
+
+   TP_ARGS(inode, pgofs),
+
+   TP_STRUCT__entry(
+   __field(dev_t,  dev)
+   __field(ino_t,  ino)
+   __field(unsigned int, pgofs)
+   ),
+
+   TP_fast_assign(
+   __entry-dev = inode-i_sb-s_dev;
+   __entry-ino = inode-i_ino;
+   __entry-pgofs = pgofs;
+   ),
+
+   TP_printk(dev = (%d,%d), ino = %lu, pgofs = %u,
+   show_dev_ino(__entry),
+   __entry-pgofs)
+);
+
+TRACE_EVENT_CONDITION(f2fs_lookup_extent_tree_end,
+
+   TP_PROTO(struct inode *inode, unsigned int pgofs,
+   struct extent_node *en),
+
+   TP_ARGS(inode, pgofs, en),
+
+   TP_CONDITION(en),
+
+   TP_STRUCT__entry(
+   __field(dev_t,  dev)
+   __field(ino_t,  ino)
+   __field(unsigned int, pgofs)
+   __field(unsigned int, fofs)
+   __field(u32, blk)
+   __field(unsigned int, len)
+   ),
+
+   TP_fast_assign(
+   __entry-dev = inode-i_sb-s_dev;
+   

[f2fs-dev] [PATCH v2 09/10] f2fs: show extent tree, node stat info in debugfs

2015-01-25 Thread Chao Yu
This patch adds and shows stat info of total memory footprint for extent tree,
node in debugfs.

Signed-off-by: Chao Yu chao2...@samsung.com
---
 fs/f2fs/debug.c | 7 +++
 fs/f2fs/f2fs.h  | 2 +-
 2 files changed, 8 insertions(+), 1 deletion(-)

diff --git a/fs/f2fs/debug.c b/fs/f2fs/debug.c
index 0f721f6..031dc61 100644
--- a/fs/f2fs/debug.c
+++ b/fs/f2fs/debug.c
@@ -35,6 +35,8 @@ static void update_general_status(struct f2fs_sb_info *sbi)
/* validation check of the segment numbers */
si-hit_ext = sbi-read_hit_ext;
si-total_ext = sbi-total_hit_ext;
+   si-ext_tree = sbi-total_ext_tree;
+   si-ext_node = atomic_read(sbi-total_ext_node);
si-ndirty_node = get_pages(sbi, F2FS_DIRTY_NODES);
si-ndirty_dent = get_pages(sbi, F2FS_DIRTY_DENTS);
si-ndirty_dirs = sbi-n_dirty_dirs;
@@ -183,6 +185,9 @@ get_cache:
si-cache_mem += sbi-n_dirty_dirs * sizeof(struct inode_entry);
for (i = 0; i = UPDATE_INO; i++)
si-cache_mem += sbi-im[i].ino_num * sizeof(struct ino_entry);
+   si-cache_mem += sbi-total_ext_tree * sizeof(struct extent_tree);
+   si-cache_mem += atomic_read(sbi-total_ext_node) *
+   sizeof(struct extent_node);
 
si-page_mem = 0;
npages = NODE_MAPPING(sbi)-nrpages;
@@ -265,6 +270,8 @@ static int stat_show(struct seq_file *s, void *v)
seq_printf(s,   - node blocks : %d\n, si-node_blks);
seq_printf(s, \nExtent Hit Ratio: %d / %d\n,
   si-hit_ext, si-total_ext);
+   seq_printf(s, \nExtent Tree Count: %d\n, si-ext_tree);
+   seq_printf(s, \nExtent Node Count: %d\n, si-ext_node);
seq_puts(s, \nBalancing F2FS Async:\n);
seq_printf(s,   - inmem: %4d\n,
   si-inmem_pages);
diff --git a/fs/f2fs/f2fs.h b/fs/f2fs/f2fs.h
index c96f451..3329367 100644
--- a/fs/f2fs/f2fs.h
+++ b/fs/f2fs/f2fs.h
@@ -1568,7 +1568,7 @@ struct f2fs_stat_info {
struct f2fs_sb_info *sbi;
int all_area_segs, sit_area_segs, nat_area_segs, ssa_area_segs;
int main_area_segs, main_area_sections, main_area_zones;
-   int hit_ext, total_ext;
+   int hit_ext, total_ext, ext_tree, ext_node;
int ndirty_node, ndirty_dent, ndirty_dirs, ndirty_meta;
int nats, dirty_nats, sits, dirty_sits, fnids;
int total_count, utilization;
-- 
2.2.1



--
Dive into the World of Parallel Programming. The Go Parallel Website,
sponsored by Intel and developed in partnership with Slashdot Media, is your
hub for all things parallel software development, from weekly thought
leadership blogs to news, videos, case studies, tutorials and more. Take a
look and join the conversation now. http://goparallel.sourceforge.net/
___
Linux-f2fs-devel mailing list
Linux-f2fs-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel


[f2fs-dev] [PATCH v2 05/10] f2fs: introduce infra macro and data structure of rb-tree extent cache

2015-01-25 Thread Chao Yu
Introduce infra macro and data structure for rb-tree based extent cache:

Macros:
 * EXT_TREE_VEC_SIZE: indicate vector size for gang lookup in extent tree.
 * F2FS_MIN_EXTENT_LEN: indicate minimum length of extent managed in cache.
 * EXTENT_CACHE_SHRINK_NUMBER: indicate number of extent in cache will be 
shrunk.

Basic data structures for extent cache:
 * struct extent_tree: extent tree entry per inode.
 * struct extent_node: extent info node linked in extent tree.

Besides, adding new extent cache related fields in f2fs_sb_info.

Signed-off-by: Chao Yu chao2...@samsung.com
Signed-off-by: Jaegeuk Kim jaeg...@kernel.org
Signed-off-by: Changman Lee cm224@samsung.com
---
 fs/f2fs/f2fs.h | 36 
 fs/f2fs/node.h |  1 +
 2 files changed, 33 insertions(+), 4 deletions(-)

diff --git a/fs/f2fs/f2fs.h b/fs/f2fs/f2fs.h
index 8e1d78d..63edc22 100644
--- a/fs/f2fs/f2fs.h
+++ b/fs/f2fs/f2fs.h
@@ -267,13 +267,33 @@ enum {
 
 #define MAX_DIR_RA_PAGES   4   /* maximum ra pages of dir */
 
+/* vector size for gang look-up from extent cache that consists of radix tree 
*/
+#define EXT_TREE_VEC_SIZE  64
+
 /* for in-memory extent cache entry */
-#define F2FS_MIN_EXTENT_LEN16  /* minimum extent length */
+#define F2FS_MIN_EXTENT_LEN64  /* minimum extent length */
+
+/* number of extent info in extent cache we try to shrink */
+#define EXTENT_CACHE_SHRINK_NUMBER 128
 
 struct extent_info {
-   unsigned int fofs;  /* start offset in a file */
-   u32 blk;/* start block address of the extent */
-   unsigned int len;   /* length of the extent */
+   unsigned int fofs;  /* start offset in a file */
+   u32 blk;/* start block address of the extent */
+   unsigned int len;   /* length of the extent */
+};
+
+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 {
+   nid_t ino;  /* inode number */
+   struct rb_root root;/* root of extent info rb-tree */
+   rwlock_t lock;  /* protect extent info rb-tree */
+   atomic_t refcount;  /* reference count of rb-tree */
+   unsigned int count; /* # of extent node in rb-tree*/
 };
 
 /*
@@ -553,6 +573,14 @@ struct f2fs_sb_info {
struct list_head dir_inode_list;/* dir inode list */
spinlock_t dir_inode_lock;  /* for dir inode list lock */
 
+   /* for extent tree cache */
+   struct radix_tree_root extent_tree_root;/* cache extent cache entries */
+   struct rw_semaphore extent_tree_lock;   /* locking extent radix tree */
+   struct list_head extent_list;   /* lru list for shrinker */
+   spinlock_t extent_lock; /* locking extent lru list */
+   int total_ext_tree; /* extent tree count */
+   atomic_t total_ext_node;/* extent info count */
+
/* basic filesystem units */
unsigned int log_sectors_per_block; /* log2 sectors per block */
unsigned int log_blocksize; /* log2 block size */
diff --git a/fs/f2fs/node.h b/fs/f2fs/node.h
index f405bbf..c56026f 100644
--- a/fs/f2fs/node.h
+++ b/fs/f2fs/node.h
@@ -120,6 +120,7 @@ enum mem_type {
NAT_ENTRIES,/* indicates the cached nat entry */
DIRTY_DENTS,/* indicates dirty dentry pages */
INO_ENTRIES,/* indicates inode entries */
+   EXTENT_CACHE,   /* indicates extent cache */
BASE_CHECK, /* check kernel status */
 };
 
-- 
2.2.1



--
Dive into the World of Parallel Programming. The Go Parallel Website,
sponsored by Intel and developed in partnership with Slashdot Media, is your
hub for all things parallel software development, from weekly thought
leadership blogs to news, videos, case studies, tutorials and more. Take a
look and join the conversation now. http://goparallel.sourceforge.net/
___
Linux-f2fs-devel mailing list
Linux-f2fs-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel


[f2fs-dev] [PATCH v2 06/10] f2fs: add core functions for rb-tree extent cache

2015-01-25 Thread Chao Yu
This patch adds core functions including slab cache init function and
init/lookup/update/shrink/destroy function for rb-tree based extent cache.

Thank Jaegeuk Kim and Changman Lee as they gave much suggestion about detail
design and implementation of extent cache.

Todo:
 * add a cached_ei into struct extent_tree for a quick recent cache.
 * register rb-based extent cache shrink with mm shrink interface.
 * disable dir inode's extent cache.

v2:
 o move set_extent_info and __is_{extent,back,front}_mergeable into f2fs.h.
 o introduce __{attach,detach}_extent_node for code readability.
 o use f2fs_kmem_cache_alloc/f2fs_radix_tree_insert for code readability.
 o fix some coding style and typo issues.
 o get rid of node/tree count stat in f2fs_{shrink,destroy}_extent_tree.

Signed-off-by: Chao Yu chao2...@samsung.com
Signed-off-by: Jaegeuk Kim jaeg...@kernel.org
Signed-off-by: Changman Lee cm224@samsung.com
---
 fs/f2fs/data.c | 410 +
 fs/f2fs/f2fs.h |  27 
 fs/f2fs/node.c |   9 +-
 3 files changed, 445 insertions(+), 1 deletion(-)

diff --git a/fs/f2fs/data.c b/fs/f2fs/data.c
index 69b0781..7ba2df9 100644
--- a/fs/f2fs/data.c
+++ b/fs/f2fs/data.c
@@ -25,6 +25,9 @@
 #include trace.h
 #include trace/events/f2fs.h
 
+struct kmem_cache *extent_tree_slab;
+struct kmem_cache *extent_node_slab;
+
 static void f2fs_read_end_io(struct bio *bio, int err)
 {
struct bio_vec *bvec;
@@ -366,6 +369,382 @@ end_update:
return need_update;
 }
 
+struct extent_node *__attach_extent_node(struct f2fs_sb_info *sbi,
+   struct extent_tree *et, struct extent_info *ei,
+   struct rb_node *parent, struct rb_node **p)
+{
+   struct extent_node *en;
+
+   en = kmem_cache_alloc(extent_node_slab, GFP_ATOMIC);
+   if (!en)
+   return NULL;
+
+   en-ei = *ei;
+   INIT_LIST_HEAD(en-list);
+
+   rb_link_node(en-rb_node, parent, p);
+   rb_insert_color(en-rb_node, et-root);
+   et-count++;
+   atomic_inc(sbi-total_ext_node);
+   return en;
+}
+
+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);
+   et-count--;
+   atomic_dec(sbi-total_ext_node);
+}
+
+static struct extent_node *__lookup_extent_tree(struct extent_tree *et,
+   unsigned int fofs)
+{
+   struct rb_node *node = et-root.rb_node;
+   struct extent_node *en;
+
+   while (node) {
+   en = rb_entry(node, struct extent_node, rb_node);
+
+   if (fofs  en-ei.fofs)
+   node = node-rb_left;
+   else if (fofs = en-ei.fofs + en-ei.len)
+   node = node-rb_right;
+   else
+   return en;
+   }
+   return NULL;
+}
+
+static struct extent_node *__try_back_merge(struct f2fs_sb_info *sbi,
+   struct extent_tree *et, struct extent_node *en)
+{
+   struct extent_node *prev;
+   struct rb_node *node;
+
+   node = rb_prev(en-rb_node);
+   if (!node)
+   return NULL;
+
+   prev = rb_entry(node, struct extent_node, rb_node);
+   if (__is_back_mergeable(en-ei, prev-ei)) {
+   en-ei.fofs = prev-ei.fofs;
+   en-ei.blk = prev-ei.blk;
+   en-ei.len += prev-ei.len;
+   __detach_extent_node(sbi, et, prev);
+   return prev;
+   }
+   return NULL;
+}
+
+static struct extent_node *__try_front_merge(struct f2fs_sb_info *sbi,
+   struct extent_tree *et, struct extent_node *en)
+{
+   struct extent_node *next;
+   struct rb_node *node;
+
+   node = rb_next(en-rb_node);
+   if (!node)
+   return NULL;
+
+   next = rb_entry(node, struct extent_node, rb_node);
+   if (__is_front_mergeable(en-ei, next-ei)) {
+   en-ei.len += next-ei.len;
+   __detach_extent_node(sbi, et, next);
+   return next;
+   }
+   return NULL;
+}
+
+static struct extent_node *__insert_extent_tree(struct f2fs_sb_info *sbi,
+   struct extent_tree *et, struct extent_info *ei,
+   struct extent_node **den)
+{
+   struct rb_node **p = et-root.rb_node;
+   struct rb_node *parent = NULL;
+   struct extent_node *en;
+
+   while (*p) {
+   parent = *p;
+   en = rb_entry(parent, struct extent_node, rb_node);
+
+   if (ei-fofs  en-ei.fofs) {
+   if (__is_front_mergeable(ei, en-ei)) {
+   f2fs_bug_on(sbi, !den);
+   en-ei.fofs = ei-fofs;
+   en-ei.blk = ei-blk;
+   en-ei.len += ei-len;
+