f2fs: add core functions for rb-tree extent cache
RFC PATCH 6/10 f2fs: add core functions for rb-tree extent cache
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.
--- fs/f2fs/data.c | 458 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ fs/f2fs/node.c | 9 +- 2 files changed, 466 insertions(+), 1 deletion(-)
fs/f2fs/data.c +458 -0
@@ -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;
@@ -373,6 +376,430 @@ end_update:return need_update; } +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 inline void set_extent_info (struct extent_info *ei,unsigned int fofs, +u32 blk,unsigned int len) +{ + ei->fofs = fofs; + ei->blk = blk; + ei->len = len; +} + +static inline bool __is_extent_mergeable (struct extent_info *back, +struct extent_info *front) +{ +return (back->fofs + back->len == front->fofs && + back->blk + back->len == front->blk); +} + +static bool __is_back_mergeable (struct extent_info *cur, +struct extent_info *back) +{ +return __is_extent_mergeable (back, cur); +} + +static bool __is_front_mergeable (struct extent_info *cur, +struct extent_info *front) +{ +return __is_extent_mergeable (cur, front); +} + +static struct extent_node *__try_back_merge (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; +rb_erase (&prev->rb_node, &et->root); + et->count--; +return prev; + } +return NULL ; +} + +static struct extent_node *__try_front_merge (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; +rb_erase (&next->rb_node, &et->root); + et->count--; +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; + *den =__try_back_merge (et, en); +return en; + } + p = &(*p)->rb_left; + }else if (ei->fofs >= en->ei.fofs + en->ei.len) { +if (__is_back_mergeable (ei, &en->ei)) { +f2fs_bug_on (sbi, !den); + en->ei.len += ei->len; + *den =__try_front_merge (et, en); +return en; + } + p = &(*p)->rb_right; + }else +f2fs_bug_on (F2FS_I_SB (inode),1 ); + } + + en =kmem_cache_alloc (extent_node_slab,GFP_ATOMIC ); + en->ei = *ei; +INIT_LIST_HEAD (&en->list); + +rb_link_node (&en->rb_node, parent, p); +rb_insert_color (&en->rb_node, &et->root); +atomic_inc (&sbi->total_ext_node); + et->count++; + +return en; +} + +static struct extent_node *__remove_extent_tree (struct extent_tree *et, +unsigned int fofs) +{ +struct rb_node *p = et->root.rb_node; +struct extent_node *en; + +while (p) { + en = rb_entry(p, struct extent_node, rb_node); + +if (fofs < en->ei.fofs) + p = p->rb_left; +else if (fofs >= en->ei.fofs + en->ei.len) + p = p->rb_right; +else { +rb_erase (&en->rb_node, &et->root); + et->count--; +return en; + } + } +return NULL ; +} + +static unsigned int __free_extent_tree (struct f2fs_sb_info *sbi, +struct extent_tree *et,bool free_all) +{ +struct rb_node *node, *next; +struct extent_node *en; +unsigned int count = et->count; + + node =rb_first (&et->root); +while (node) { + next =rb_next (node); + en = rb_entry(node, struct extent_node, rb_node); + +if (free_all) { +spin_lock (&sbi->extent_lock); +if (!list_empty (&en->list)) +list_del_init (&en->list); +spin_unlock (&sbi->extent_lock); + } + +if (free_all ||list_empty (&en->list)) { +rb_erase (node, &et->root); +kmem_cache_free (extent_node_slab, en); +atomic_dec (&sbi->total_ext_node); + et->count--; + } + node = next; + } + +return count - et->count; +} + +static bool f2fs_lookup_extent_tree (struct inode *inode,pgoff_t pgofs, +struct extent_info *ei) +{ +struct f2fs_sb_info *sbi =F2FS_I_SB (inode); +struct extent_tree *et; +struct extent_node *en; + +if (is_inode_flag_set (F2FS_I (inode),FI_NO_EXTENT )) +return false; + +down_read (&sbi->extent_tree_lock); + et =radix_tree_lookup (&sbi->extent_tree_root, inode->i_ino); +if (!et) { +up_read (&sbi->extent_tree_lock); +return false; + } +atomic_inc (&et->refcount); +up_read (&sbi->extent_tree_lock); + +read_lock (&et->lock); + en =__lookup_extent_tree (et, pgofs); +if (en) { + *ei = en->ei; +spin_lock (&sbi->extent_lock); +if (!list_empty (&en->list)) +list_move_tail (&en->list, &sbi->extent_list); +spin_unlock (&sbi->extent_lock); +stat_inc_read_hit (sbi->sb); + } +stat_inc_total_hit (sbi->sb); +read_unlock (&et->lock); + +atomic_dec (&et->refcount); +return en ? true : false; +} + +static void f2fs_update_extent_tree (struct inode *inode,pgoff_t fofs, +block_t blkaddr) +{ +struct f2fs_sb_info *sbi =F2FS_I_SB (inode); +nid_t ino = inode->i_ino; +struct extent_tree *et; +struct extent_node *en =NULL , *en1 =NULL , *en2 =NULL , *en3 =NULL ; +struct extent_node *den =NULL ; +struct extent_info *pei; +struct extent_info ei; +unsigned int endofs; + +if (is_inode_flag_set (F2FS_I (inode),FI_NO_EXTENT )) +return ; + +retry: +down_write (&sbi->extent_tree_lock); + et =radix_tree_lookup (&sbi->extent_tree_root, ino); +if (!et) { + et =kmem_cache_alloc (extent_tree_slab,GFP_ATOMIC ); +if (!et) { +up_write (&sbi->extent_tree_lock); + goto retry; + } +if (radix_tree_insert (&sbi->extent_tree_root, ino, et)) { +up_write (&sbi->extent_tree_lock); +kmem_cache_free (extent_tree_slab, et); + goto retry; + } +memset (et,0 ,sizeof (struct extent_tree )); + et->ino = ino; + et->root =RB_ROOT ; +rwlock_init (&et->lock); +atomic_set (&et->refcount,0 ); + et->count =0 ; + sbi->total_ext_tree++; + } +atomic_inc (&et->refcount); +up_write (&sbi->extent_tree_lock); + +write_lock (&et->lock); + +/* 1. lookup and remove exist extent info in cache */ + en =__remove_extent_tree (et, fofs); +if (!en) + goto update_extent; + + pei = &en->ei; +/* 2. if extent can be split more, split and insert the left part */ +if (pei->len >1 ) { +/* insert left part of split extent into cache */ +if (pei->fofs < fofs) { +set_extent_info (&ei, pei->fofs, pei->blk, + fofs - pei->fofs); + en1 =__insert_extent_tree (sbi, et, &ei,NULL ); + } + +/* insert right part of split extent into cache */ + endofs = pei->fofs + pei->len -1 ; +if (endofs > fofs) { +set_extent_info (&ei, fofs +1 , + fofs - pei->fofs + pei->blk, endofs - fofs); + en2 =__insert_extent_tree (sbi, et, &ei,NULL ); + } + } + +update_extent: +/* 3. update extent in extent cache */ +if (blkaddr) { +set_extent_info (&ei, fofs, blkaddr,1 ); + en3 =__insert_extent_tree (sbi, et, &ei, &den); + } + +/* 4. update in global extent list */ +spin_lock (&sbi->extent_lock); +if (en && !list_empty (&en->list)) +list_del_init (&en->list); +/* +* en1 and en2 split from en, they will become more and more smaller +* fragments after splitting several times. So if the length is smaller +* than F2FS_MIN_EXTENT_LEN, we will not add them into extent_list, +* but just waiting shrinker to free them for reclaiming when OOM. +*/ +if (en1 && en1->ei.len >=F2FS_MIN_EXTENT_LEN ) +list_add_tail (&en1->list, &sbi->extent_list); +if (en2 && en2->ei.len >=F2FS_MIN_EXTENT_LEN ) +list_add_tail (&en2->list, &sbi->extent_list); +if (en3) { +if (list_empty (&en3->list)) +list_add_tail (&en3->list, &sbi->extent_list); +else +list_move_tail (&en3->list, &sbi->extent_list); + } +if (den && !list_empty (&den->list)) +list_del_init (&den->list); +spin_unlock (&sbi->extent_lock); + +if (en) { +kmem_cache_free (extent_node_slab, en); +atomic_dec (&sbi->total_ext_node); + } +if (den) { +kmem_cache_free (extent_node_slab, den); +atomic_dec (&sbi->total_ext_node); + } + +write_unlock (&et->lock); +atomic_dec (&et->refcount); +} + +void f2fs_shrink_extent_tree (struct f2fs_sb_info *sbi,int nr_shrink) +{ +struct extent_tree *treevec[EXT_TREE_VEC_SIZE ]; +struct extent_node *en, *tmp; +unsigned long ino =F2FS_ROOT_INO (sbi); +struct radix_tree_iter iter; +void **slot; +unsigned int found; +unsigned int node_cnt =0 , tree_cnt =0 ; + +if (available_free_memory (sbi,EXTENT_CACHE )) +return ; + +spin_lock (&sbi->extent_lock); +list_for_each_entry_safe (en, tmp, &sbi->extent_list, list) { +if (!nr_shrink--) +break ; +list_del_init (&en->list); + } +spin_unlock (&sbi->extent_lock); + +down_read (&sbi->extent_tree_lock); +while ((found =radix_tree_gang_lookup (&sbi->extent_tree_root, + (void **)treevec, ino,EXT_TREE_VEC_SIZE ))) { +unsigned i; + + ino = treevec[found -1 ]->ino +1 ; +for (i =0 ; i < found; i++) { +struct extent_tree *et = treevec[i]; + +atomic_inc (&et->refcount); +write_lock (&et->lock); + node_cnt +=__free_extent_tree (sbi, et, false); +write_unlock (&et->lock); +atomic_dec (&et->refcount); + } + } +up_read (&sbi->extent_tree_lock); + +down_write (&sbi->extent_tree_lock); +radix_tree_for_each_slot (slot, &sbi->extent_tree_root, &iter, +F2FS_ROOT_INO (sbi)) { +struct extent_tree *et = (struct extent_tree *)*slot; + +if (!atomic_read (&et->refcount) && !et->count) { +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); +} + +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 ; + +down_read (&sbi->extent_tree_lock); + et =radix_tree_lookup (&sbi->extent_tree_root, inode->i_ino); +if (!et) { +up_read (&sbi->extent_tree_lock); + goto out; + } +atomic_inc (&et->refcount); +up_read (&sbi->extent_tree_lock); + +/* free all extent info belong to this extent tree */ +write_lock (&et->lock); + node_cnt =__free_extent_tree (sbi, et, true); +write_unlock (&et->lock); + +atomic_dec (&et->refcount); + +/* try to find and delete extent tree entry in radix tree */ +down_write (&sbi->extent_tree_lock); + et =radix_tree_lookup (&sbi->extent_tree_root, inode->i_ino); +if (!et) { +up_write (&sbi->extent_tree_lock); + goto out; + } +f2fs_bug_on (sbi,atomic_read (&et->refcount) || et->count); +radix_tree_delete (&sbi->extent_tree_root, inode->i_ino); +kmem_cache_free (extent_tree_slab, et); + sbi->total_ext_tree--; +up_write (&sbi->extent_tree_lock); +out: +return ; +} +static bool f2fs_lookup_extent_cache (struct inode *inode,pgoff_t pgofs,struct extent_info *ei) {
@@ -1198,6 +1625,37 @@ static sector_t f2fs_bmap(struct address_space *mapping, sector_t block)return generic_block_bmap (mapping, block, get_data_block); } +void init_extent_cache_info (struct f2fs_sb_info *sbi) +{ +INIT_RADIX_TREE (&sbi->extent_tree_root,GFP_NOFS ); +init_rwsem (&sbi->extent_tree_lock); +INIT_LIST_HEAD (&sbi->extent_list); +spin_lock_init (&sbi->extent_lock); + sbi->total_ext_tree =0 ; +atomic_set (&sbi->total_ext_node,0 ); +} + +int __init create_extent_cache (void ) +{ + extent_tree_slab =f2fs_kmem_cache_create ("f2fs_extent_tree" , +sizeof (struct extent_tree )); +if (!extent_tree_slab) +return -ENOMEM ; + extent_node_slab =f2fs_kmem_cache_create ("f2fs_extent_node" , +sizeof (struct extent_node )); +if (!extent_node_slab) { +kmem_cache_destroy (extent_tree_slab); +return -ENOMEM ; + } +return 0 ; +} + +void destroy_extent_cache (void ) +{ +kmem_cache_destroy (extent_node_slab); +kmem_cache_destroy (extent_tree_slab); +} +const struct address_space_operations f2fs_dblock_aops = { .readpage = f2fs_read_data_page, .readpages = f2fs_read_data_pages,
fs/f2fs/node.c +8 -1
@@ -41,7 +41,9 @@ bool available_free_memory(struct f2fs_sb_info *sbi, int type)/* only uses low memory */ avail_ram = val.totalram - val.totalhigh; -/* give 25%, 25%, 50%, 50% memory for each components respectively */ +/* +* give 25%, 25%, 50%, 50%, 50% memory for each components respectively +*/ if (type ==FREE_NIDS ) { mem_size = (nm_i->fcnt *sizeof (struct free_nid )) >>PAGE_CACHE_SHIFT ;
@@ -62,6 +64,11 @@ bool available_free_memory(struct f2fs_sb_info *sbi, int type) mem_size += (sbi->im[i].ino_num *sizeof (struct ino_entry )) >>PAGE_CACHE_SHIFT ; res = mem_size < ((avail_ram * nm_i->ram_thresh /100 ) >>1 ); + }else if (type ==EXTENT_CACHE ) { + mem_size = (sbi->total_ext_tree *sizeof (struct extent_tree ) + +atomic_read (&sbi->total_ext_node) * +sizeof (struct extent_node )) >>PAGE_CACHE_SHIFT ; + res = mem_size < ((avail_ram * nm_i->ram_thresh /100 ) >>1 ); }else {if (sbi->sb->s_bdi->dirty_exceeded)return false;
Signature · 1 line
2.2.1
Hi Chao,
Great works. :)
2015-01-12 16:14 GMT+09:00 Chao Yu <[email protected]>:
Quoted 24 lines
This patch adds core functions including slab cache init function and
init/lookup/update/shrink/destroyfunction 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 acached_eiinto structextent_treefor a quick recent cache.
* register rb-based extent cache shrink with mm shrink interface.
* disable dir inode's extent cache.Signed-off-by Chao Yu <[email protected]>Signed-off-by Jaegeuk Kim <[email protected]>Signed-off-by Changman Lee <[email protected]>--- fs/f2fs/data.c | 458 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ fs/f2fs/node.c | 9 +- 2 files changed, 466 insertions(+), 1 deletion(-)fs/f2fs/data.c +0
-0
fs/f2fs/data.c line 27
Quoted 3 lines
fs/f2fs/data.c +0
-0@@ -25,6 +25,9 @@#include "trace.h" #include <trace/events/f2fs.h>
~ snip ~
Quoted 10 lines
fs/f2fs/data.c +10
-0+ +static void f2fs_update_extent_tree (struct inode *inode,pgoff_t fofs, +block_t blkaddr) +{ +struct f2fs_sb_info *sbi =F2FS_I_SB (inode); +nid_t ino = inode->i_ino; +struct extent_tree *et; +struct extent_node *en =NULL , *en1 =NULL , *en2 =NULL , *en3 =NULL ; +struct extent_node *den =NULL ; +struct extent_info *pei;
fs/f2fs/data.c end_update: · line 619
Quoted 10 lines
fs/f2fs/data.c +10
-0+struct extent_info ei; +unsigned int endofs; + +if (is_inode_flag_set (F2FS_I (inode),FI_NO_EXTENT )) +return ; + +retry: +down_write (&sbi->extent_tree_lock); + et =radix_tree_lookup (&sbi->extent_tree_root, ino); +if (!et) {
We've already made some useful functions.
How about using f2fs_kmem_cache_alloc and f2fs_radix_tree_insert ?
Quoted 11 lines
fs/f2fs/data.c +11
-0+ et =kmem_cache_alloc (extent_tree_slab,GFP_ATOMIC ); +if (!et) { +up_write (&sbi->extent_tree_lock); + goto retry; + } +if (radix_tree_insert (&sbi->extent_tree_root, ino, et)) { +up_write (&sbi->extent_tree_lock); +kmem_cache_free (extent_tree_slab, et); + goto retry; + } +memset (et,0 ,sizeof (struct extent_tree ));
fs/f2fs/data.c end_update: · line 640
Quoted 10 lines
fs/f2fs/data.c +10
-0+ et->ino = ino; + et->root =RB_ROOT ; +rwlock_init (&et->lock); +atomic_set (&et->refcount,0 ); + et->count =0 ; + sbi->total_ext_tree++; + } +atomic_inc (&et->refcount); +up_write (&sbi->extent_tree_lock); +
~ snip ~
Quoted 16 lines
fs/f2fs/data.c +16
-0+ +write_unlock (&et->lock); +atomic_dec (&et->refcount); +} + +void f2fs_shrink_extent_tree (struct f2fs_sb_info *sbi,int nr_shrink) +{ +struct extent_tree *treevec[EXT_TREE_VEC_SIZE ]; +struct extent_node *en, *tmp; +unsigned long ino =F2FS_ROOT_INO (sbi); +struct radix_tree_iter iter; +void **slot; +unsigned int found; +unsigned int node_cnt =0 , tree_cnt =0 ; + +if (available_free_memory (sbi,EXTENT_CACHE ))
fs/f2fs/data.c end_update: · line 731
Quoted 10 lines
fs/f2fs/data.c +10
-0+return ; + +spin_lock (&sbi->extent_lock); +list_for_each_entry_safe (en, tmp, &sbi->extent_list, list) { +if (!nr_shrink--) +break ; +list_del_init (&en->list); + } +spin_unlock (&sbi->extent_lock); +
IMHO, it's expensive to retrieve all extent_tree to free extent_node that list_empty() is true.
Is there any idea to improve this?
For example, if each extent_node has its extent_root, it would be more fast by not to retrieve all trees.
Of course, however, it uses more memory.
But, I think that your patchset might just as well be merged because patches are well made and it's clearly separated with mount option. In the next time, we could improve this.
Regards,
Changman
Quoted 23 lines
fs/f2fs/data.c +23
-0+down_read (&sbi->extent_tree_lock); +while ((found =radix_tree_gang_lookup (&sbi->extent_tree_root, + (void **)treevec, ino,EXT_TREE_VEC_SIZE ))) { +unsigned i; + + ino = treevec[found -1 ]->ino +1 ; +for (i =0 ; i < found; i++) { +struct extent_tree *et = treevec[i]; + +atomic_inc (&et->refcount); +write_lock (&et->lock); + node_cnt +=__free_extent_tree (sbi, et, false); +write_unlock (&et->lock); +atomic_dec (&et->refcount); + } + } +up_read (&sbi->extent_tree_lock); + +down_write (&sbi->extent_tree_lock); +radix_tree_for_each_slot (slot, &sbi->extent_tree_root, &iter, +F2FS_ROOT_INO (sbi)) { +struct extent_tree *et = (struct extent_tree *)*slot; +
fs/f2fs/data.c end_update: · line 764
Quoted 10 lines
fs/f2fs/data.c +10
-0+if (!atomic_read (&et->refcount) && !et->count) { +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); +} +
~ snip ~
Quoted 9 lines
--
2.2.1--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Hi Changman,
Quoted 11 lines
-----Original Message-----
From: Changman Lee [mailto:[email protected]]
Sent: Tuesday, January 20, 2015 11:06 PM
To: Chao Yu
Cc: Jaegeuk Kim; Changman Lee; [email protected]; [email protected]
Subject: Re: [f2fs-dev][RFC PATCH 06/10] f2fs: add core functions for rb-tree extent cacheHi Chao,
Great works. :)
Thanks! :)
Quoted 16 lines
2015-01-12 16:14 GMT+09:00 Chao Yu <[email protected]>:
Quoted 14 lines
This patch adds core functions including slab cache init function and
init/lookup/update/shrink/destroyfunction 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 acached_eiinto structextent_treefor a quick recent cache.
* register rb-based extent cache shrink with mm shrink interface.
* disable dir inode's extent cache.Signed-off-by Chao Yu <[email protected]>Signed-off-by Jaegeuk Kim <[email protected]>Signed-off-by Changman Lee <[email protected]>
If you do not object, I'd like to keep this as lots of details and ideas are from you and Jaegeuk.
Quoted 31 lines
fs/f2fs/data.c line 27
Quoted 13 lines
--- fs/f2fs/data.c | 458 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ fs/f2fs/node.c | 9 +- 2 files changed, 466 insertions(+), 1 deletion(-)fs/f2fs/data.c +0
-0@@ -25,6 +25,9 @@#include "trace.h" #include <trace/events/f2fs.h> ~ snip ~
Quoted 15 lines
fs/f2fs/data.c +15
-0+ +static void f2fs_update_extent_tree (struct inode *inode,pgoff_t fofs, +block_t blkaddr) +{ +struct f2fs_sb_info *sbi =F2FS_I_SB (inode); +nid_t ino = inode->i_ino; +struct extent_tree *et; +struct extent_node *en =NULL , *en1 =NULL , *en2 =NULL , *en3 =NULL ; +struct extent_node *den =NULL ; +struct extent_info *pei; +struct extent_info ei; +unsigned int endofs; + +if (is_inode_flag_set (F2FS_I (inode),FI_NO_EXTENT )) +return ;
Quoted 8 lines
fs/f2fs/data.c end_update: · line 619
Quoted 5 lines
fs/f2fs/data.c +5
-0+ +retry: +down_write (&sbi->extent_tree_lock); + et =radix_tree_lookup (&sbi->extent_tree_root, ino); +if (!et) {We've already made some useful functions.
How about usingf2fs_kmem_cache_allocandf2fs_radix_tree_insert?
IMO, we'd better to use original function kmem_cache_alloc and radix_tree_insert, because if we use f2fs_{kmem_cache_alloc, radix_tree_insert}, we may loop in these functions without releasing extent_tree_lock lock when OOM, so it will block lock grabbers for long time which we do not wish to see.
Quoted 46 lines
Quoted 12 lines
fs/f2fs/data.c +11
-0+ et =kmem_cache_alloc (extent_tree_slab,GFP_ATOMIC ); +if (!et) { +up_write (&sbi->extent_tree_lock); + goto retry; + } +if (radix_tree_insert (&sbi->extent_tree_root, ino, et)) { +up_write (&sbi->extent_tree_lock); +kmem_cache_free (extent_tree_slab, et); + goto retry; + } +memset (et,0 ,sizeof (struct extent_tree ));fs/f2fs/data.c end_update: · line 640
Quoted 10 lines
fs/f2fs/data.c +10
-0+ et->ino = ino; + et->root =RB_ROOT ; +rwlock_init (&et->lock); +atomic_set (&et->refcount,0 ); + et->count =0 ; + sbi->total_ext_tree++; + } +atomic_inc (&et->refcount); +up_write (&sbi->extent_tree_lock); +~ snip ~
Quoted 21 lines
fs/f2fs/data.c +21
-0+ +write_unlock (&et->lock); +atomic_dec (&et->refcount); +} + +void f2fs_shrink_extent_tree (struct f2fs_sb_info *sbi,int nr_shrink) +{ +struct extent_tree *treevec[EXT_TREE_VEC_SIZE ]; +struct extent_node *en, *tmp; +unsigned long ino =F2FS_ROOT_INO (sbi); +struct radix_tree_iter iter; +void **slot; +unsigned int found; +unsigned int node_cnt =0 , tree_cnt =0 ; + +if (available_free_memory (sbi,EXTENT_CACHE )) +return ; + +spin_lock (&sbi->extent_lock); +list_for_each_entry_safe (en, tmp, &sbi->extent_list, list) { +if (!nr_shrink--)
Quoted 8 lines
fs/f2fs/data.c end_update: · line 731
Quoted 5 lines
fs/f2fs/data.c +5
-0+break ; +list_del_init (&en->list); + } +spin_unlock (&sbi->extent_lock); +IMHO, it's expensive to retrieve all
extent_treeto freeextent_nodethatlist_empty()is true.
Yes, it will cause heavy overhead to release extent_node in extent cache which has huge number of extent_node.
Quoted 4 lines
Is there any idea to improve this?
For example, if eachextent_nodehas itsextent_root, it would be more fast by not to retrieve all trees.
Of course, however, it uses more memory.
I think your solution is a good way to improve the performance.
Quoted 3 lines
But, I think that your patchset might just as well be merged because patches are well made and it's clearly separated with mount option.
I hope so.
Quoted 1 line
In the next time, we could improve this.
There are also some thoughts in *todo* list, these can be added to developing list if this patch set is applied.
Thanks for your review and suggestion! :)
Regards,
Yu
Quoted 49 lines
Regards,
ChangmanQuoted 23 lines
fs/f2fs/data.c +23
-0+down_read (&sbi->extent_tree_lock); +while ((found =radix_tree_gang_lookup (&sbi->extent_tree_root, + (void **)treevec, ino,EXT_TREE_VEC_SIZE ))) { +unsigned i; + + ino = treevec[found -1 ]->ino +1 ; +for (i =0 ; i < found; i++) { +struct extent_tree *et = treevec[i]; + +atomic_inc (&et->refcount); +write_lock (&et->lock); + node_cnt +=__free_extent_tree (sbi, et, false); +write_unlock (&et->lock); +atomic_dec (&et->refcount); + } + } +up_read (&sbi->extent_tree_lock); + +down_write (&sbi->extent_tree_lock); +radix_tree_for_each_slot (slot, &sbi->extent_tree_root, &iter, +F2FS_ROOT_INO (sbi)) { +struct extent_tree *et = (struct extent_tree *)*slot; +fs/f2fs/data.c end_update: · line 764
Quoted 10 lines
fs/f2fs/data.c +10
-0+if (!atomic_read (&et->refcount) && !et->count) { +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); +} +~ snip ~
Quoted 9 lines
--
2.2.1--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Quoted 29 lines · Chao Yu
Hi Changman,
Quoted 11 lines
-----Original Message-----
From: Changman Lee [mailto:[email protected]]
Sent: Tuesday, January 20, 2015 11:06 PM
To: Chao Yu
Cc: Jaegeuk Kim; Changman Lee; [email protected]; [email protected]
Subject: Re: [f2fs-dev][RFC PATCH 06/10] f2fs: add core functions for rb-tree extent cacheHi Chao,
Great works. :)
Thanks! :)
Quoted 13 lines
2015-01-12 16:14 GMT+09:00 Chao Yu <[email protected]>:
Quoted 11 lines
This patch adds core functions including slab cache init function and
init/lookup/update/shrink/destroyfunction 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 acached_eiinto structextent_treefor a quick recent cache.
* register rb-based extent cache shrink with mm shrink interface.
* disable dir inode's extent cache.
Quoted 7 lines
Quoted 3 lines
Quoted 3 lines
Signed-off-by Chao Yu <[email protected]>Signed-off-by Jaegeuk Kim <[email protected]>Signed-off-by Changman Lee <[email protected]>If you do not object, I'd like to keep this as lots of details and ideas are from you and Jaegeuk.
I have no objection.
Quoted 40 lines
Quoted 31 lines
fs/f2fs/data.c line 27
Quoted 13 lines
--- fs/f2fs/data.c | 458 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ fs/f2fs/node.c | 9 +- 2 files changed, 466 insertions(+), 1 deletion(-)fs/f2fs/data.c +0
-0@@ -25,6 +25,9 @@#include "trace.h" #include <trace/events/f2fs.h> ~ snip ~
Quoted 15 lines
fs/f2fs/data.c +15
-0+ +static void f2fs_update_extent_tree (struct inode *inode,pgoff_t fofs, +block_t blkaddr) +{ +struct f2fs_sb_info *sbi =F2FS_I_SB (inode); +nid_t ino = inode->i_ino; +struct extent_tree *et; +struct extent_node *en =NULL , *en1 =NULL , *en2 =NULL , *en3 =NULL ; +struct extent_node *den =NULL ; +struct extent_info *pei; +struct extent_info ei; +unsigned int endofs; + +if (is_inode_flag_set (F2FS_I (inode),FI_NO_EXTENT )) +return ;Quoted 8 lines
fs/f2fs/data.c end_update: · line 619
Quoted 5 lines
fs/f2fs/data.c +5
-0+ +retry: +down_write (&sbi->extent_tree_lock); + et =radix_tree_lookup (&sbi->extent_tree_root, ino); +if (!et) {We've already made some useful functions.
How about usingf2fs_kmem_cache_allocandf2fs_radix_tree_insert?
Quoted 5 lines
IMO, we'd better to use original function
kmem_cache_allocandradix_tree_insert, because if we use f2fs_{kmem_cache_alloc,radix_tree_insert}, we may loop in these functions without releasingextent_tree_locklock when OOM, so it will block lock grabbers for long time which we do not wish to see.
I see. If so, let's use cond_resched() in front of goto retry after up_write. And also look into kmem_cache_alloc in __insert_extent_tree, please.
Quoted 69 lines
Quoted 46 lines
Quoted 12 lines
fs/f2fs/data.c +11
-0+ et =kmem_cache_alloc (extent_tree_slab,GFP_ATOMIC ); +if (!et) { +up_write (&sbi->extent_tree_lock); + goto retry; + } +if (radix_tree_insert (&sbi->extent_tree_root, ino, et)) { +up_write (&sbi->extent_tree_lock); +kmem_cache_free (extent_tree_slab, et); + goto retry; + } +memset (et,0 ,sizeof (struct extent_tree ));fs/f2fs/data.c end_update: · line 640
Quoted 10 lines
fs/f2fs/data.c +10
-0+ et->ino = ino; + et->root =RB_ROOT ; +rwlock_init (&et->lock); +atomic_set (&et->refcount,0 ); + et->count =0 ; + sbi->total_ext_tree++; + } +atomic_inc (&et->refcount); +up_write (&sbi->extent_tree_lock); +~ snip ~
Quoted 21 lines
fs/f2fs/data.c +21
-0+ +write_unlock (&et->lock); +atomic_dec (&et->refcount); +} + +void f2fs_shrink_extent_tree (struct f2fs_sb_info *sbi,int nr_shrink) +{ +struct extent_tree *treevec[EXT_TREE_VEC_SIZE ]; +struct extent_node *en, *tmp; +unsigned long ino =F2FS_ROOT_INO (sbi); +struct radix_tree_iter iter; +void **slot; +unsigned int found; +unsigned int node_cnt =0 , tree_cnt =0 ; + +if (available_free_memory (sbi,EXTENT_CACHE )) +return ; + +spin_lock (&sbi->extent_lock); +list_for_each_entry_safe (en, tmp, &sbi->extent_list, list) { +if (!nr_shrink--)Quoted 8 lines
fs/f2fs/data.c end_update: · line 731
Quoted 5 lines
fs/f2fs/data.c +5
-0+break ; +list_del_init (&en->list); + } +spin_unlock (&sbi->extent_lock); +IMHO, it's expensive to retrieve all
extent_treeto freeextent_nodethatlist_empty()is true.Yes, it will cause heavy overhead to release
extent_nodein extent cache which has huge number ofextent_node.Quoted 4 lines
Is there any idea to improve this?
For example, if eachextent_nodehas itsextent_root, it would be more fast by not to retrieve all trees.
Of course, however, it uses more memory.I think your solution is a good way to improve the performance.
Quoted 3 lines
But, I think that your patchset might just as well be merged because patches are well made and it's clearly separated with mount option.
Quoted 6 lines
I hope so.
Quoted 1 line
In the next time, we could improve this.
There are also some thoughts in *todo* list, these can be added to developing list if this patch set is applied.
Cheers,
Changman
Quoted 55 lines
Thanks for your review and suggestion! :)
Regards,
YuQuoted 49 lines
Regards,
ChangmanQuoted 23 lines
fs/f2fs/data.c +23
-0+down_read (&sbi->extent_tree_lock); +while ((found =radix_tree_gang_lookup (&sbi->extent_tree_root, + (void **)treevec, ino,EXT_TREE_VEC_SIZE ))) { +unsigned i; + + ino = treevec[found -1 ]->ino +1 ; +for (i =0 ; i < found; i++) { +struct extent_tree *et = treevec[i]; + +atomic_inc (&et->refcount); +write_lock (&et->lock); + node_cnt +=__free_extent_tree (sbi, et, false); +write_unlock (&et->lock); +atomic_dec (&et->refcount); + } + } +up_read (&sbi->extent_tree_lock); + +down_write (&sbi->extent_tree_lock); +radix_tree_for_each_slot (slot, &sbi->extent_tree_root, &iter, +F2FS_ROOT_INO (sbi)) { +struct extent_tree *et = (struct extent_tree *)*slot; +fs/f2fs/data.c end_update: · line 764
Quoted 10 lines
fs/f2fs/data.c +10
-0+if (!atomic_read (&et->refcount) && !et->count) { +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); +} +~ snip ~
Quoted 9 lines
--
2.2.1--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Hi Changman,
Quoted 88 lines
-----Original Message-----
From: Changman Lee [mailto:[email protected]]
Sent: Thursday, January 22, 2015 6:26 AM
To: Chao Yu
Cc: 'Changman Lee'; 'Jaegeuk Kim'; [email protected]; [email protected]
Subject: Re: [f2fs-dev][RFC PATCH 06/10] f2fs: add core functions for rb-tree extent cacheQuoted 29 lines · Chao Yu
Hi Changman,
Quoted 11 lines
-----Original Message-----
From: Changman Lee [mailto:[email protected]]
Sent: Tuesday, January 20, 2015 11:06 PM
To: Chao Yu
Cc: Jaegeuk Kim; Changman Lee; [email protected]; [email protected]
Subject: Re: [f2fs-dev][RFC PATCH 06/10] f2fs: add core functions for rb-tree extent cacheHi Chao,
Great works. :)
Thanks! :)
Quoted 13 lines
2015-01-12 16:14 GMT+09:00 Chao Yu <[email protected]>:
Quoted 11 lines
This patch adds core functions including slab cache init function and
init/lookup/update/shrink/destroyfunction 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 acached_eiinto structextent_treefor a quick recent cache.
* register rb-based extent cache shrink with mm shrink interface.
* disable dir inode's extent cache.Quoted 7 lines
Quoted 3 lines
Quoted 3 lines
Signed-off-by Chao Yu <[email protected]>Signed-off-by Jaegeuk Kim <[email protected]>Signed-off-by Changman Lee <[email protected]>If you do not object, I'd like to keep this as lots of details and ideas are from you and Jaegeuk.
I have no objection.
Quoted 40 lines
Quoted 39 lines
fs/f2fs/data.c line 27
Quoted 13 lines
--- fs/f2fs/data.c | 458 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ fs/f2fs/node.c | 9 +- 2 files changed, 466 insertions(+), 1 deletion(-)fs/f2fs/data.c +0
-0@@ -25,6 +25,9 @@#include "trace.h" #include <trace/events/f2fs.h> ~ snip ~
Quoted 10 lines
fs/f2fs/data.c +10
-0+ +static void f2fs_update_extent_tree (struct inode *inode,pgoff_t fofs, +block_t blkaddr) +{ +struct f2fs_sb_info *sbi =F2FS_I_SB (inode); +nid_t ino = inode->i_ino; +struct extent_tree *et; +struct extent_node *en =NULL , *en1 =NULL , *en2 =NULL , *en3 =NULL ; +struct extent_node *den =NULL ; +struct extent_info *pei;fs/f2fs/data.c end_update: · line 619
Quoted 10 lines
fs/f2fs/data.c +10
-0+struct extent_info ei; +unsigned int endofs; + +if (is_inode_flag_set (F2FS_I (inode),FI_NO_EXTENT )) +return ; + +retry: +down_write (&sbi->extent_tree_lock); + et =radix_tree_lookup (&sbi->extent_tree_root, ino); +if (!et) {We've already made some useful functions.
How about usingf2fs_kmem_cache_allocandf2fs_radix_tree_insert?
Quoted 7 lines
Quoted 5 lines
IMO, we'd better to use original function
kmem_cache_allocandradix_tree_insert, because if we use f2fs_{kmem_cache_alloc,radix_tree_insert}, we may loop in these functions without releasingextent_tree_locklock when OOM, so it will block lock grabbers for long time which we do not wish to see.I see. If so, let's use
cond_resched()in front of goto retry afterup_write.
Ah, yes, I will do that.
Quoted 1 line
And also look into
kmem_cache_allocin__insert_extent_tree, please.
I notice the problem, I'd like return NULL in __insert_extent_tree if we fail to alloc extent_node space with extent_node_slab.
Thank you for reminding me this!
Regards,
Yu
Quoted 135 lines
Quoted 70 lines
Quoted 47 lines
Quoted 13 lines
fs/f2fs/data.c +11
-0+ et =kmem_cache_alloc (extent_tree_slab,GFP_ATOMIC ); +if (!et) { +up_write (&sbi->extent_tree_lock); + goto retry; + } +if (radix_tree_insert (&sbi->extent_tree_root, ino, et)) { +up_write (&sbi->extent_tree_lock); +kmem_cache_free (extent_tree_slab, et); + goto retry; + } +memset (et,0 ,sizeof (struct extent_tree ));fs/f2fs/data.c end_update: · line 640
Quoted 10 lines
fs/f2fs/data.c +10
-0+ et->ino = ino; + et->root =RB_ROOT ; +rwlock_init (&et->lock); +atomic_set (&et->refcount,0 ); + et->count =0 ; + sbi->total_ext_tree++; + } +atomic_inc (&et->refcount); +up_write (&sbi->extent_tree_lock); +~ snip ~
Quoted 21 lines
fs/f2fs/data.c +21
-0+ +write_unlock (&et->lock); +atomic_dec (&et->refcount); +} + +void f2fs_shrink_extent_tree (struct f2fs_sb_info *sbi,int nr_shrink) +{ +struct extent_tree *treevec[EXT_TREE_VEC_SIZE ]; +struct extent_node *en, *tmp; +unsigned long ino =F2FS_ROOT_INO (sbi); +struct radix_tree_iter iter; +void **slot; +unsigned int found; +unsigned int node_cnt =0 , tree_cnt =0 ; + +if (available_free_memory (sbi,EXTENT_CACHE )) +return ; + +spin_lock (&sbi->extent_lock); +list_for_each_entry_safe (en, tmp, &sbi->extent_list, list) { +if (!nr_shrink--)Quoted 8 lines
fs/f2fs/data.c end_update: · line 731
Quoted 5 lines
fs/f2fs/data.c +5
-0+break ; +list_del_init (&en->list); + } +spin_unlock (&sbi->extent_lock); +IMHO, it's expensive to retrieve all
extent_treeto freeextent_nodethatlist_empty()is true.Yes, it will cause heavy overhead to release
extent_nodein extent cache which has huge number ofextent_node.Quoted 4 lines
Is there any idea to improve this?
For example, if eachextent_nodehas itsextent_root, it would be more fast by not to retrieve all trees.
Of course, however, it uses more memory.I think your solution is a good way to improve the performance.
Quoted 3 lines
But, I think that your patchset might just as well be merged because patches are well made and it's clearly separated with mount option.
Quoted 6 lines
I hope so.
Quoted 1 line
In the next time, we could improve this.
There are also some thoughts in *todo* list, these can be added to developing list if this patch set is applied.
Cheers,
ChangmanQuoted 55 lines
Thanks for your review and suggestion! :)
Regards,
YuQuoted 49 lines
Regards,
ChangmanQuoted 23 lines
fs/f2fs/data.c +23
-0+down_read (&sbi->extent_tree_lock); +while ((found =radix_tree_gang_lookup (&sbi->extent_tree_root, + (void **)treevec, ino,EXT_TREE_VEC_SIZE ))) { +unsigned i; + + ino = treevec[found -1 ]->ino +1 ; +for (i =0 ; i < found; i++) { +struct extent_tree *et = treevec[i]; + +atomic_inc (&et->refcount); +write_lock (&et->lock); + node_cnt +=__free_extent_tree (sbi, et, false); +write_unlock (&et->lock); +atomic_dec (&et->refcount); + } + } +up_read (&sbi->extent_tree_lock); + +down_write (&sbi->extent_tree_lock); +radix_tree_for_each_slot (slot, &sbi->extent_tree_root, &iter, +F2FS_ROOT_INO (sbi)) { +struct extent_tree *et = (struct extent_tree *)*slot; +fs/f2fs/data.c end_update: · line 764
Quoted 10 lines
fs/f2fs/data.c +10
-0+if (!atomic_read (&et->refcount) && !et->count) { +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); +} +~ snip ~
Quoted 9 lines
--
2.2.1--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Jaegeuk Kim
maintainerQuoted 71 lines · Chao Yu
This patch adds core functions including slab cache init function and
init/lookup/update/shrink/destroyfunction 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 acached_eiinto structextent_treefor a quick recent cache.
* register rb-based extent cache shrink with mm shrink interface.
* disable dir inode's extent cache.Signed-off-by Chao Yu <[email protected]>Signed-off-by Jaegeuk Kim <[email protected]>Signed-off-by Changman Lee <[email protected]>--- fs/f2fs/data.c | 458 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ fs/f2fs/node.c | 9 +- 2 files changed, 466 insertions(+), 1 deletion(-)fs/f2fs/data.c +37
-0@@ -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;@@ -373,6 +376,430 @@ end_update:return need_update; } +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 inline void set_extent_info (struct extent_info *ei,unsigned int fofs, +u32 blk,unsigned int len) +{ + ei->fofs = fofs; + ei->blk = blk; + ei->len = len; +} + +static inline bool __is_extent_mergeable (struct extent_info *back, +struct extent_info *front) +{ +return (back->fofs + back->len == front->fofs && + back->blk + back->len == front->blk); +} + +static bool __is_back_mergeable(struct extent_info *cur,
fs/f2fs/data.c end_update: · line 422
Quoted 10 lines
fs/f2fs/data.c +10
-0+ struct extent_info *back) +{ +return __is_extent_mergeable (back, cur); +} + +static bool __is_front_mergeable (struct extent_info *cur, +struct extent_info *front) +{ +return __is_extent_mergeable (cur, front); +}
How about declaring these four functions as inline ones and locating them inside f2fs.h?
Quoted 65 lines
fs/f2fs/data.c +65
-0+ +static struct extent_node *__try_back_merge (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; +rb_erase (&prev->rb_node, &et->root); + et->count--; +return prev; + } +return NULL ; +} + +static struct extent_node *__try_front_merge (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; +rb_erase (&next->rb_node, &et->root); + et->count--; +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; + *den =__try_back_merge (et, en); +return en; + } + p = &(*p)->rb_left;
fs/f2fs/data.c end_update: · line 497
Quoted 10 lines
fs/f2fs/data.c +10
-0+ }else if (ei->fofs >= en->ei.fofs + en->ei.len) { +if (__is_back_mergeable (ei, &en->ei)) { +f2fs_bug_on (sbi, !den); + en->ei.len += ei->len; + *den =__try_front_merge (et, en); +return en; + } + p = &(*p)->rb_right; + }else +f2fs_bug_on (F2FS_I_SB (inode),1 );
Coding style.
} else {
...
}fs/f2fs/data.c end_update: · line 498
Quoted 1 line
fs/f2fs/data.c +1
-0+ }
How about adding __attach_extent_node()?
{
fs/f2fs/data.c end_update: · line 500
Quoted 2 lines
fs/f2fs/data.c +2
-0+ + en =kmem_cache_alloc (extent_node_slab,GFP_ATOMIC );
en = f2fs_kmem_cache_alloc(.., GFP_ATOMIC);
fs/f2fs/data.c end_update: · line 507
Quoted 7 lines
fs/f2fs/data.c +7
-0+ en->ei = *ei; +INIT_LIST_HEAD (&en->list); + +rb_link_node (&en->rb_node, parent, p); +rb_insert_color (&en->rb_node, &et->root); +atomic_inc (&sbi->total_ext_node); + et->count++;
}
fs/f2fs/data.c end_update: · line 513
Quoted 6 lines
fs/f2fs/data.c +6
-0+ +return en; +} + +static struct extent_node *__remove_extent_tree (struct extent_tree *et, +unsigned int fofs)
This is __detach_extent_node()?
fs/f2fs/data.c end_update: · line 522
Quoted 9 lines
fs/f2fs/data.c +9
-0+{ +struct rb_node *p = et->root.rb_node; +struct extent_node *en; + +while (p) { + en = rb_entry(p, struct extent_node, rb_node); + +if (fofs < en->ei.fofs) + p = p->rb_left;
Coding style.
if () {
} else {
}
fs/f2fs/data.c end_update: · line 527
Quoted 5 lines
fs/f2fs/data.c +5
-0+else if (fofs >= en->ei.fofs + en->ei.len) + p = p->rb_right; +else { +rb_erase (&en->rb_node, &et->root); + et->count--;
Add here?
atomic_dec(&sbi->total_ext_node);
Quoted 83 lines
fs/f2fs/data.c +83
-0+return en; + } + } +return NULL ; +} + +static unsigned int __free_extent_tree (struct f2fs_sb_info *sbi, +struct extent_tree *et,bool free_all) +{ +struct rb_node *node, *next; +struct extent_node *en; +unsigned int count = et->count; + + node =rb_first (&et->root); +while (node) { + next =rb_next (node); + en = rb_entry(node, struct extent_node, rb_node); + +if (free_all) { +spin_lock (&sbi->extent_lock); +if (!list_empty (&en->list)) +list_del_init (&en->list); +spin_unlock (&sbi->extent_lock); + } + +if (free_all ||list_empty (&en->list)) { +rb_erase (node, &et->root); +kmem_cache_free (extent_node_slab, en); +atomic_dec (&sbi->total_ext_node); + et->count--; + } + node = next; + } + +return count - et->count; +} + +static bool f2fs_lookup_extent_tree (struct inode *inode,pgoff_t pgofs, +struct extent_info *ei) +{ +struct f2fs_sb_info *sbi =F2FS_I_SB (inode); +struct extent_tree *et; +struct extent_node *en; + +if (is_inode_flag_set (F2FS_I (inode),FI_NO_EXTENT )) +return false; + +down_read (&sbi->extent_tree_lock); + et =radix_tree_lookup (&sbi->extent_tree_root, inode->i_ino); +if (!et) { +up_read (&sbi->extent_tree_lock); +return false; + } +atomic_inc (&et->refcount); +up_read (&sbi->extent_tree_lock); + +read_lock (&et->lock); + en =__lookup_extent_tree (et, pgofs); +if (en) { + *ei = en->ei; +spin_lock (&sbi->extent_lock); +if (!list_empty (&en->list)) +list_move_tail (&en->list, &sbi->extent_list); +spin_unlock (&sbi->extent_lock); +stat_inc_read_hit (sbi->sb); + } +stat_inc_total_hit (sbi->sb); +read_unlock (&et->lock); + +atomic_dec (&et->refcount); +return en ? true : false; +} + +static void f2fs_update_extent_tree (struct inode *inode,pgoff_t fofs, +block_t blkaddr) +{ +struct f2fs_sb_info *sbi =F2FS_I_SB (inode); +nid_t ino = inode->i_ino; +struct extent_tree *et; +struct extent_node *en =NULL , *en1 =NULL , *en2 =NULL , *en3 =NULL ; +struct extent_node *den =NULL ; +struct extent_info *pei; +struct extent_info ei;
fs/f2fs/data.c end_update: · line 620
Quoted 10 lines
fs/f2fs/data.c +10
-0+unsigned int endofs; + +if (is_inode_flag_set (F2FS_I (inode),FI_NO_EXTENT )) +return ; + +retry: +down_write (&sbi->extent_tree_lock); + et =radix_tree_lookup (&sbi->extent_tree_root, ino); +if (!et) { + et =kmem_cache_alloc (extent_tree_slab,GFP_ATOMIC );
et = f2fs_kmem_cache_alloc(.., GFP_ATOMIC);
Quoted 13 lines
fs/f2fs/data.c +13
-0+if (!et) { +up_write (&sbi->extent_tree_lock); + goto retry; + } +if (radix_tree_insert (&sbi->extent_tree_root, ino, et)) { +up_write (&sbi->extent_tree_lock); +kmem_cache_free (extent_tree_slab, et); + goto retry; + } +memset (et,0 ,sizeof (struct extent_tree )); + et->ino = ino; + et->root =RB_ROOT ; +rwlock_init (&et->lock);
fs/f2fs/data.c end_update: · line 643
Quoted 10 lines
fs/f2fs/data.c +10
-0+atomic_set (&et->refcount,0 ); + et->count =0 ; + sbi->total_ext_tree++; + } +atomic_inc (&et->refcount); +up_write (&sbi->extent_tree_lock); + +write_lock (&et->lock); + +/* 1. lookup and remove exist extent info in cache */
existing
fs/f2fs/data.c end_update: · line 644
Quoted 1 line
fs/f2fs/data.c +1
-0+ en =__remove_extent_tree (et, fofs);
en = __detach_extent_node();?
Quoted 29 lines
fs/f2fs/data.c +29
-0+if (!en) + goto update_extent; + + pei = &en->ei; +/* 2. if extent can be split more, split and insert the left part */ +if (pei->len >1 ) { +/* insert left part of split extent into cache */ +if (pei->fofs < fofs) { +set_extent_info (&ei, pei->fofs, pei->blk, + fofs - pei->fofs); + en1 =__insert_extent_tree (sbi, et, &ei,NULL ); + } + +/* insert right part of split extent into cache */ + endofs = pei->fofs + pei->len -1 ; +if (endofs > fofs) { +set_extent_info (&ei, fofs +1 , + fofs - pei->fofs + pei->blk, endofs - fofs); + en2 =__insert_extent_tree (sbi, et, &ei,NULL ); + } + } + +update_extent: +/* 3. update extent in extent cache */ +if (blkaddr) { +set_extent_info (&ei, fofs, blkaddr,1 ); + en3 =__insert_extent_tree (sbi, et, &ei, &den); + } +
fs/f2fs/data.c end_update: · line 683
Quoted 10 lines
fs/f2fs/data.c +10
-0+/* 4. update in global extent list */ +spin_lock (&sbi->extent_lock); +if (en && !list_empty (&en->list)) +list_del_init (&en->list); +/* +* en1 and en2 split from en, they will become more and more smaller +* fragments after splitting several times. So if the length is smaller +* than F2FS_MIN_EXTENT_LEN, we will not add them into extent_list, +* but just waiting shrinker to free them for reclaiming when OOM. +*/
Can we just remove en1 and en2 in __insert_extent_tree?
Quoted 7 lines
fs/f2fs/data.c +7
-0+if (en1 && en1->ei.len >=F2FS_MIN_EXTENT_LEN ) +list_add_tail (&en1->list, &sbi->extent_list); +if (en2 && en2->ei.len >=F2FS_MIN_EXTENT_LEN ) +list_add_tail (&en2->list, &sbi->extent_list); +if (en3) { +if (list_empty (&en3->list)) +list_add_tail (&en3->list, &sbi->extent_list);
fs/f2fs/data.c end_update: · line 700
Quoted 10 lines
fs/f2fs/data.c +10
-0+else +list_move_tail (&en3->list, &sbi->extent_list); + } +if (den && !list_empty (&den->list)) +list_del_init (&den->list); +spin_unlock (&sbi->extent_lock); + +if (en) { +kmem_cache_free (extent_node_slab, en); +atomic_dec (&sbi->total_ext_node);
--> move into __detach_extent_node().
Quoted 49 lines
fs/f2fs/data.c +49
-0+ } +if (den) { +kmem_cache_free (extent_node_slab, den); +atomic_dec (&sbi->total_ext_node); + } + +write_unlock (&et->lock); +atomic_dec (&et->refcount); +} + +void f2fs_shrink_extent_tree (struct f2fs_sb_info *sbi,int nr_shrink) +{ +struct extent_tree *treevec[EXT_TREE_VEC_SIZE ]; +struct extent_node *en, *tmp; +unsigned long ino =F2FS_ROOT_INO (sbi); +struct radix_tree_iter iter; +void **slot; +unsigned int found; +unsigned int node_cnt =0 , tree_cnt =0 ; + +if (available_free_memory (sbi,EXTENT_CACHE )) +return ; + +spin_lock (&sbi->extent_lock); +list_for_each_entry_safe (en, tmp, &sbi->extent_list, list) { +if (!nr_shrink--) +break ; +list_del_init (&en->list); + } +spin_unlock (&sbi->extent_lock); + +down_read (&sbi->extent_tree_lock); +while ((found =radix_tree_gang_lookup (&sbi->extent_tree_root, + (void **)treevec, ino,EXT_TREE_VEC_SIZE ))) { +unsigned i; + + ino = treevec[found -1 ]->ino +1 ; +for (i =0 ; i < found; i++) { +struct extent_tree *et = treevec[i]; + +atomic_inc (&et->refcount); +write_lock (&et->lock); + node_cnt +=__free_extent_tree (sbi, et, false); +write_unlock (&et->lock); +atomic_dec (&et->refcount); + } + } +up_read (&sbi->extent_tree_lock); +
fs/f2fs/data.c end_update: · line 759
Quoted 10 lines
fs/f2fs/data.c +10
-0+down_write (&sbi->extent_tree_lock); +radix_tree_for_each_slot (slot, &sbi->extent_tree_root, &iter, +F2FS_ROOT_INO (sbi)) { +struct extent_tree *et = (struct extent_tree *)*slot; + +if (!atomic_read (&et->refcount) && !et->count) { +radix_tree_delete (&sbi->extent_tree_root, et->ino); +kmem_cache_free (extent_tree_slab, et); + sbi->total_ext_tree--; + tree_cnt++;
No use of tree_cnt.
Thanks,
Quoted 113 lines
fs/f2fs/data.c +74
-0+ } + } +up_write (&sbi->extent_tree_lock); +} + +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 ; + +down_read (&sbi->extent_tree_lock); + et =radix_tree_lookup (&sbi->extent_tree_root, inode->i_ino); +if (!et) { +up_read (&sbi->extent_tree_lock); + goto out; + } +atomic_inc (&et->refcount); +up_read (&sbi->extent_tree_lock); + +/* free all extent info belong to this extent tree */ +write_lock (&et->lock); + node_cnt =__free_extent_tree (sbi, et, true); +write_unlock (&et->lock); + +atomic_dec (&et->refcount); + +/* try to find and delete extent tree entry in radix tree */ +down_write (&sbi->extent_tree_lock); + et =radix_tree_lookup (&sbi->extent_tree_root, inode->i_ino); +if (!et) { +up_write (&sbi->extent_tree_lock); + goto out; + } +f2fs_bug_on (sbi,atomic_read (&et->refcount) || et->count); +radix_tree_delete (&sbi->extent_tree_root, inode->i_ino); +kmem_cache_free (extent_tree_slab, et); + sbi->total_ext_tree--; +up_write (&sbi->extent_tree_lock); +out: +return ; +} +static bool f2fs_lookup_extent_cache (struct inode *inode,pgoff_t pgofs,struct extent_info *ei) {@@ -1198,6 +1625,37 @@ static sector_t f2fs_bmap(struct address_space *mapping, sector_t block)return generic_block_bmap (mapping, block, get_data_block); } +void init_extent_cache_info (struct f2fs_sb_info *sbi) +{ +INIT_RADIX_TREE (&sbi->extent_tree_root,GFP_NOFS ); +init_rwsem (&sbi->extent_tree_lock); +INIT_LIST_HEAD (&sbi->extent_list); +spin_lock_init (&sbi->extent_lock); + sbi->total_ext_tree =0 ; +atomic_set (&sbi->total_ext_node,0 ); +} + +int __init create_extent_cache (void ) +{ + extent_tree_slab =f2fs_kmem_cache_create ("f2fs_extent_tree" , +sizeof (struct extent_tree )); +if (!extent_tree_slab) +return -ENOMEM ; + extent_node_slab =f2fs_kmem_cache_create ("f2fs_extent_node" , +sizeof (struct extent_node )); +if (!extent_node_slab) { +kmem_cache_destroy (extent_tree_slab); +return -ENOMEM ; + } +return 0 ; +} + +void destroy_extent_cache (void ) +{ +kmem_cache_destroy (extent_node_slab); +kmem_cache_destroy (extent_tree_slab); +} +const struct address_space_operations f2fs_dblock_aops = { .readpage = f2fs_read_data_page, .readpages = f2fs_read_data_pages,fs/f2fs/node.c +8
-1@@ -41,7 +41,9 @@ bool available_free_memory(struct f2fs_sb_info *sbi, int type)/* only uses low memory */ avail_ram = val.totalram - val.totalhigh; -/* give 25%, 25%, 50%, 50% memory for each components respectively */ +/* +* give 25%, 25%, 50%, 50%, 50% memory for each components respectively +*/ if (type ==FREE_NIDS ) { mem_size = (nm_i->fcnt *sizeof (struct free_nid )) >>PAGE_CACHE_SHIFT ;@@ -62,6 +64,11 @@ bool available_free_memory(struct f2fs_sb_info *sbi, int type) mem_size += (sbi->im[i].ino_num *sizeof (struct ino_entry )) >>PAGE_CACHE_SHIFT ; res = mem_size < ((avail_ram * nm_i->ram_thresh /100 ) >>1 ); + }else if (type ==EXTENT_CACHE ) { + mem_size = (sbi->total_ext_tree *sizeof (struct extent_tree ) + +atomic_read (&sbi->total_ext_node) * +sizeof (struct extent_node )) >>PAGE_CACHE_SHIFT ; + res = mem_size < ((avail_ram * nm_i->ram_thresh /100 ) >>1 ); }else {if (sbi->sb->s_bdi->dirty_exceeded)return false;Signature · 1 line
2.2.1
Hi Jaegeuk,
Quoted 85 lines
-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
Sent: Friday, January 23, 2015 9:48 AM
To: Chao Yu
Cc: Changman Lee; [email protected]; [email protected]
Subject: Re: [f2fs-dev][RFC PATCH 06/10] f2fs: add core functions for rb-tree extent cacheQuoted 77 lines · Chao Yu
This patch adds core functions including slab cache init function and
init/lookup/update/shrink/destroyfunction 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 acached_eiinto structextent_treefor a quick recent cache.
* register rb-based extent cache shrink with mm shrink interface.
* disable dir inode's extent cache.Signed-off-by Chao Yu <[email protected]>Signed-off-by Jaegeuk Kim <[email protected]>Signed-off-by Changman Lee <[email protected]>--- fs/f2fs/data.c | 458 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ fs/f2fs/node.c | 9 +- 2 files changed, 466 insertions(+), 1 deletion(-)fs/f2fs/data.c +43
-0@@ -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;@@ -373,6 +376,430 @@ end_update:return need_update; } +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 inline void set_extent_info (struct extent_info *ei,unsigned int fofs, +u32 blk,unsigned int len) +{ + ei->fofs = fofs; + ei->blk = blk; + ei->len = len; +} + +static inline bool __is_extent_mergeable (struct extent_info *back, +struct extent_info *front) +{ +return (back->fofs + back->len == front->fofs && + back->blk + back->len == front->blk); +} + +static bool __is_back_mergeable (struct extent_info *cur, +struct extent_info *back) +{ +return __is_extent_mergeable (back, cur); +} + +static bool __is_front_mergeable(struct extent_info *cur,
Quoted 8 lines
fs/f2fs/data.c end_update: · line 422
Quoted 4 lines
fs/f2fs/data.c +4
-0+ struct extent_info *front) +{ +return __is_extent_mergeable (cur, front); +}How about declaring these four functions as inline ones and locating them inside
f2fs.h?
Good idea! Will do.
Quoted 79 lines
Quoted 66 lines
fs/f2fs/data.c +65
-0+ +static struct extent_node *__try_back_merge (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; +rb_erase (&prev->rb_node, &et->root); + et->count--; +return prev; + } +return NULL ; +} + +static struct extent_node *__try_front_merge (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; +rb_erase (&next->rb_node, &et->root); + et->count--; +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; + *den =__try_back_merge (et, en); +return en; + } + p = &(*p)->rb_left;fs/f2fs/data.c end_update: · line 497
Quoted 10 lines
fs/f2fs/data.c +10
-0+ }else if (ei->fofs >= en->ei.fofs + en->ei.len) { +if (__is_back_mergeable (ei, &en->ei)) { +f2fs_bug_on (sbi, !den); + en->ei.len += ei->len; + *den =__try_front_merge (et, en); +return en; + } + p = &(*p)->rb_right; + }else +f2fs_bug_on (F2FS_I_SB (inode),1 );Coding style.
Quoted 3 lines
} else {
...
}will fix.
Quoted 4 lines
fs/f2fs/data.c end_update: · line 498
Quoted 2 lines
fs/f2fs/data.c +1
-0+ }How about adding
__attach_extent_node()?
That's more readable.
How do you think of the following functions:
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);
}Quoted 5 lines
{
fs/f2fs/data.c end_update: · line 500
Quoted 2 lines
fs/f2fs/data.c +2
-0+ + en =kmem_cache_alloc (extent_node_slab,GFP_ATOMIC );en = f2fs_kmem_cache_alloc(.., GFP_ATOMIC);
We should avoid cond_resched() in f2fs_kmem_cache_alloc when we are holding write_lock.
IMO, it's better to return NULL if we fail to alloc extent_node here. Otherwise we'd better alloc extent_node before write_lock.
Quoted 32 lines
fs/f2fs/data.c end_update: · line 507
Quoted 8 lines
fs/f2fs/data.c +7
-0+ en->ei = *ei; +INIT_LIST_HEAD (&en->list); + +rb_link_node (&en->rb_node, parent, p); +rb_insert_color (&en->rb_node, &et->root); +atomic_inc (&sbi->total_ext_node); + et->count++;}
fs/f2fs/data.c end_update: · line 513
Quoted 6 lines
fs/f2fs/data.c +6
-0+ +return en; +} + +static struct extent_node *__remove_extent_tree (struct extent_tree *et, +unsigned int fofs)This is
__detach_extent_node()?fs/f2fs/data.c end_update: · line 522
Quoted 9 lines
fs/f2fs/data.c +9
-0+{ +struct rb_node *p = et->root.rb_node; +struct extent_node *en; + +while (p) { + en = rb_entry(p, struct extent_node, rb_node); + +if (fofs < en->ei.fofs) + p = p->rb_left;Coding style.
Quoted 3 lines
if () {
} else {
}
will fix.
Quoted 9 lines
fs/f2fs/data.c end_update: · line 527
Quoted 6 lines
fs/f2fs/data.c +5
-0+else if (fofs >= en->ei.fofs + en->ei.len) + p = p->rb_right; +else { +rb_erase (&en->rb_node, &et->root); + et->count--;Add here?
atomic_dec(&sbi->total_ext_node);
Agree, see __detach_extent_node() implementation above.
Quoted 88 lines
Quoted 88 lines
fs/f2fs/data.c +87
-0+return en; + } + } +return NULL ; +} + +static unsigned int __free_extent_tree (struct f2fs_sb_info *sbi, +struct extent_tree *et,bool free_all) +{ +struct rb_node *node, *next; +struct extent_node *en; +unsigned int count = et->count; + + node =rb_first (&et->root); +while (node) { + next =rb_next (node); + en = rb_entry(node, struct extent_node, rb_node); + +if (free_all) { +spin_lock (&sbi->extent_lock); +if (!list_empty (&en->list)) +list_del_init (&en->list); +spin_unlock (&sbi->extent_lock); + } + +if (free_all ||list_empty (&en->list)) { +rb_erase (node, &et->root); +kmem_cache_free (extent_node_slab, en); +atomic_dec (&sbi->total_ext_node); + et->count--; + } + node = next; + } + +return count - et->count; +} + +static bool f2fs_lookup_extent_tree (struct inode *inode,pgoff_t pgofs, +struct extent_info *ei) +{ +struct f2fs_sb_info *sbi =F2FS_I_SB (inode); +struct extent_tree *et; +struct extent_node *en; + +if (is_inode_flag_set (F2FS_I (inode),FI_NO_EXTENT )) +return false; + +down_read (&sbi->extent_tree_lock); + et =radix_tree_lookup (&sbi->extent_tree_root, inode->i_ino); +if (!et) { +up_read (&sbi->extent_tree_lock); +return false; + } +atomic_inc (&et->refcount); +up_read (&sbi->extent_tree_lock); + +read_lock (&et->lock); + en =__lookup_extent_tree (et, pgofs); +if (en) { + *ei = en->ei; +spin_lock (&sbi->extent_lock); +if (!list_empty (&en->list)) +list_move_tail (&en->list, &sbi->extent_list); +spin_unlock (&sbi->extent_lock); +stat_inc_read_hit (sbi->sb); + } +stat_inc_total_hit (sbi->sb); +read_unlock (&et->lock); + +atomic_dec (&et->refcount); +return en ? true : false; +} + +static void f2fs_update_extent_tree (struct inode *inode,pgoff_t fofs, +block_t blkaddr) +{ +struct f2fs_sb_info *sbi =F2FS_I_SB (inode); +nid_t ino = inode->i_ino; +struct extent_tree *et; +struct extent_node *en =NULL , *en1 =NULL , *en2 =NULL , *en3 =NULL ; +struct extent_node *den =NULL ; +struct extent_info *pei; +struct extent_info ei; +unsigned int endofs; + +if (is_inode_flag_set (F2FS_I (inode),FI_NO_EXTENT )) +return ;
Quoted 8 lines
fs/f2fs/data.c end_update: · line 620
Quoted 6 lines
fs/f2fs/data.c +6
-0+ +retry: +down_write (&sbi->extent_tree_lock); + et =radix_tree_lookup (&sbi->extent_tree_root, ino); +if (!et) { + et =kmem_cache_alloc (extent_tree_slab,GFP_ATOMIC );et =
f2fs_kmem_cache_alloc(.., GFP_ATOMIC);
How about modifying as below to avoid holding extent_tree_lock for long time?
et = kmem_cache_alloc(extent_tree_slab, GFP_ATOMIC);
if (!et) {
up_write(&sbi->extent_tree_lock);
cond_resched();
goto retry;
}Quoted 8 lines
fs/f2fs/data.c end_update: · line 627
Quoted 8 lines
fs/f2fs/data.c +7
-0+if (!et) { +up_write (&sbi->extent_tree_lock); + goto retry; + } +if (radix_tree_insert (&sbi->extent_tree_root, ino, et)) { +up_write (&sbi->extent_tree_lock); +kmem_cache_free (extent_tree_slab, et);
cond_resched()?
Quoted 10 lines
Quoted 10 lines
fs/f2fs/data.c +10
-0+ goto retry; + } +memset (et,0 ,sizeof (struct extent_tree )); + et->ino = ino; + et->root =RB_ROOT ; +rwlock_init (&et->lock); +atomic_set (&et->refcount,0 ); + et->count =0 ; + sbi->total_ext_tree++; + }
Quoted 8 lines
fs/f2fs/data.c end_update: · line 643
Quoted 6 lines
fs/f2fs/data.c +6
-0+atomic_inc (&et->refcount); +up_write (&sbi->extent_tree_lock); + +write_lock (&et->lock); + +/* 1. lookup and remove exist extent info in cache */ existing
got it.
Quoted 4 lines
fs/f2fs/data.c end_update: · line 644
Quoted 2 lines
fs/f2fs/data.c +1
-0+ en =__remove_extent_tree (et, fofs);en =
__detach_extent_node();?
OK, it seems that most codes of __remove_extent_tree and __lookup_extent_tree are the same, so here I want to remove extent node like this:
en = __lookup_extent_tree(et, fofs); if (!en) goto update_extent; dei = en->ei; __detach_extent_node(sbi, et, en);
How do you think?
Quoted 34 lines
Quoted 34 lines
fs/f2fs/data.c +33
-0+if (!en) + goto update_extent; + + pei = &en->ei; +/* 2. if extent can be split more, split and insert the left part */ +if (pei->len >1 ) { +/* insert left part of split extent into cache */ +if (pei->fofs < fofs) { +set_extent_info (&ei, pei->fofs, pei->blk, + fofs - pei->fofs); + en1 =__insert_extent_tree (sbi, et, &ei,NULL ); + } + +/* insert right part of split extent into cache */ + endofs = pei->fofs + pei->len -1 ; +if (endofs > fofs) { +set_extent_info (&ei, fofs +1 , + fofs - pei->fofs + pei->blk, endofs - fofs); + en2 =__insert_extent_tree (sbi, et, &ei,NULL ); + } + } + +update_extent: +/* 3. update extent in extent cache */ +if (blkaddr) { +set_extent_info (&ei, fofs, blkaddr,1 ); + en3 =__insert_extent_tree (sbi, et, &ei, &den); + } + +/* 4. update in global extent list */ +spin_lock (&sbi->extent_lock); +if (en && !list_empty (&en->list)) +list_del_init (&en->list);
Quoted 8 lines
fs/f2fs/data.c end_update: · line 683
Quoted 6 lines
fs/f2fs/data.c +6
-0+/* +* en1 and en2 split from en, they will become more and more smaller +* fragments after splitting several times. So if the length is smaller +* than F2FS_MIN_EXTENT_LEN, we will not add them into extent_list, +* but just waiting shrinker to free them for reclaiming when OOM. +*/ Can we just remove en1 and en2 in
__insert_extent_tree?
en1 and en2 is newly added, in __attach_extent_node we do not add en1 and en2 into lru list, so if you do not want to keep split part in lru list, let's just remove the below codes.
Quoted 12 lines
Quoted 12 lines
fs/f2fs/data.c +11
-0+if (en1 && en1->ei.len >=F2FS_MIN_EXTENT_LEN ) +list_add_tail (&en1->list, &sbi->extent_list); +if (en2 && en2->ei.len >=F2FS_MIN_EXTENT_LEN ) +list_add_tail (&en2->list, &sbi->extent_list); +if (en3) { +if (list_empty (&en3->list)) +list_add_tail (&en3->list, &sbi->extent_list); +else +list_move_tail (&en3->list, &sbi->extent_list); + } +if (den && !list_empty (&den->list))
Quoted 8 lines
fs/f2fs/data.c end_update: · line 700
Quoted 6 lines
fs/f2fs/data.c +6
-0+list_del_init (&den->list); +spin_unlock (&sbi->extent_lock); + +if (en) { +kmem_cache_free (extent_node_slab, en); +atomic_dec (&sbi->total_ext_node);--> move into __detach_extent_node().
will do.
Quoted 54 lines
Quoted 54 lines
fs/f2fs/data.c +53
-0+ } +if (den) { +kmem_cache_free (extent_node_slab, den); +atomic_dec (&sbi->total_ext_node); + } + +write_unlock (&et->lock); +atomic_dec (&et->refcount); +} + +void f2fs_shrink_extent_tree (struct f2fs_sb_info *sbi,int nr_shrink) +{ +struct extent_tree *treevec[EXT_TREE_VEC_SIZE ]; +struct extent_node *en, *tmp; +unsigned long ino =F2FS_ROOT_INO (sbi); +struct radix_tree_iter iter; +void **slot; +unsigned int found; +unsigned int node_cnt =0 , tree_cnt =0 ; + +if (available_free_memory (sbi,EXTENT_CACHE )) +return ; + +spin_lock (&sbi->extent_lock); +list_for_each_entry_safe (en, tmp, &sbi->extent_list, list) { +if (!nr_shrink--) +break ; +list_del_init (&en->list); + } +spin_unlock (&sbi->extent_lock); + +down_read (&sbi->extent_tree_lock); +while ((found =radix_tree_gang_lookup (&sbi->extent_tree_root, + (void **)treevec, ino,EXT_TREE_VEC_SIZE ))) { +unsigned i; + + ino = treevec[found -1 ]->ino +1 ; +for (i =0 ; i < found; i++) { +struct extent_tree *et = treevec[i]; + +atomic_inc (&et->refcount); +write_lock (&et->lock); + node_cnt +=__free_extent_tree (sbi, et, false); +write_unlock (&et->lock); +atomic_dec (&et->refcount); + } + } +up_read (&sbi->extent_tree_lock); + +down_write (&sbi->extent_tree_lock); +radix_tree_for_each_slot (slot, &sbi->extent_tree_root, &iter, +F2FS_ROOT_INO (sbi)) { +struct extent_tree *et = (struct extent_tree *)*slot;
Quoted 8 lines
fs/f2fs/data.c end_update: · line 759
Quoted 6 lines
fs/f2fs/data.c +6
-0+ +if (!atomic_read (&et->refcount) && !et->count) { +radix_tree_delete (&sbi->extent_tree_root, et->ino); +kmem_cache_free (extent_tree_slab, et); + sbi->total_ext_tree--; + tree_cnt++;No use of
tree_cnt.
This is used by trace function in RFC PATCH 10/10.
Thanks for your review! :)
Regards,
Yu
Quoted 2 lines
Thanks,
[snip]
Jaegeuk Kim
maintainerQuoted 21 lines · Chao Yu
Hi Jaegeuk,
Quoted 19 lines
-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
Sent: Friday, January 23, 2015 9:48 AM
To: Chao Yu
Cc: Changman Lee; [email protected]; [email protected]
Subject: Re: [f2fs-dev][RFC PATCH 06/10] f2fs: add core functions for rb-tree extent cacheQuoted 11 lines · Chao Yu
This patch adds core functions including slab cache init function and
init/lookup/update/shrink/destroyfunction 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 acached_eiinto structextent_treefor a quick recent cache.
* register rb-based extent cache shrink with mm shrink interface.
* disable dir inode's extent cache.
snip
Quoted 30 lines
Quoted 5 lines
Review
Quoted 3 lines
(quoted diff) +1
-0+ }How about adding
__attach_extent_node()?That's more readable.
How do you think of the following functions:
struct
extent_node*__attach_extent_node(structf2fs_sb_info*sbi,
structextent_tree*et, structextent_info*ei, structrb_node*parent, structrb_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; }
Quoted 7 lines
static void __detach_extent_node(struct
f2fs_sb_info*sbi,
structextent_tree*et, structextent_node*en){ rb_erase(&en->rb_node, &et->root); et->count--; atomic_dec(&sbi->total_ext_node); }
Looks good to me.
Quoted 11 lines
Quoted 6 lines
{
Review
Quoted 2 lines
(quoted diff) +2
-0+ + en = kmem_cache_alloc(extent_node_slab, GFP_ATOMIC);en = f2fs_kmem_cache_alloc(.., GFP_ATOMIC);We should avoid
cond_resched()inf2fs_kmem_cache_allocwhen we are holdingwrite_lock.IMO, it's better to return NULL if we fail to alloc
extent_nodehere. Otherwise we'd better allocextent_nodebeforewrite_lock.
Oh, it's write_lock. Okay.
Quoted 148 lines
Quoted 33 lines
fs/f2fs/data.c end_update: · line 507
Quoted 9 lines
fs/f2fs/data.c +7
-0+ en->ei = *ei; +INIT_LIST_HEAD (&en->list); + +rb_link_node (&en->rb_node, parent, p); +rb_insert_color (&en->rb_node, &et->root); +atomic_inc (&sbi->total_ext_node); + et->count++;}
fs/f2fs/data.c end_update: · line 513
Quoted 6 lines
fs/f2fs/data.c +6
-0+ +return en; +} + +static struct extent_node *__remove_extent_tree (struct extent_tree *et, +unsigned int fofs)This is
__detach_extent_node()?fs/f2fs/data.c end_update: · line 522
Quoted 9 lines
fs/f2fs/data.c +9
-0+{ +struct rb_node *p = et->root.rb_node; +struct extent_node *en; + +while (p) { + en = rb_entry(p, struct extent_node, rb_node); + +if (fofs < en->ei.fofs) + p = p->rb_left;Coding style.
Quoted 3 lines
if () {
} else {
}will fix.
Quoted 9 lines
fs/f2fs/data.c end_update: · line 527
Quoted 6 lines
fs/f2fs/data.c +5
-0+else if (fofs >= en->ei.fofs + en->ei.len) + p = p->rb_right; +else { +rb_erase (&en->rb_node, &et->root); + et->count--;Add here?
atomic_dec(&sbi->total_ext_node);Agree, see
__detach_extent_node()implementation above.Quoted 88 lines
Quoted 88 lines
fs/f2fs/data.c +87
-0+return en; + } + } +return NULL ; +} + +static unsigned int __free_extent_tree (struct f2fs_sb_info *sbi, +struct extent_tree *et,bool free_all) +{ +struct rb_node *node, *next; +struct extent_node *en; +unsigned int count = et->count; + + node =rb_first (&et->root); +while (node) { + next =rb_next (node); + en = rb_entry(node, struct extent_node, rb_node); + +if (free_all) { +spin_lock (&sbi->extent_lock); +if (!list_empty (&en->list)) +list_del_init (&en->list); +spin_unlock (&sbi->extent_lock); + } + +if (free_all ||list_empty (&en->list)) { +rb_erase (node, &et->root); +kmem_cache_free (extent_node_slab, en); +atomic_dec (&sbi->total_ext_node); + et->count--; + } + node = next; + } + +return count - et->count; +} + +static bool f2fs_lookup_extent_tree (struct inode *inode,pgoff_t pgofs, +struct extent_info *ei) +{ +struct f2fs_sb_info *sbi =F2FS_I_SB (inode); +struct extent_tree *et; +struct extent_node *en; + +if (is_inode_flag_set (F2FS_I (inode),FI_NO_EXTENT )) +return false; + +down_read (&sbi->extent_tree_lock); + et =radix_tree_lookup (&sbi->extent_tree_root, inode->i_ino); +if (!et) { +up_read (&sbi->extent_tree_lock); +return false; + } +atomic_inc (&et->refcount); +up_read (&sbi->extent_tree_lock); + +read_lock (&et->lock); + en =__lookup_extent_tree (et, pgofs); +if (en) { + *ei = en->ei; +spin_lock (&sbi->extent_lock); +if (!list_empty (&en->list)) +list_move_tail (&en->list, &sbi->extent_list); +spin_unlock (&sbi->extent_lock); +stat_inc_read_hit (sbi->sb); + } +stat_inc_total_hit (sbi->sb); +read_unlock (&et->lock); + +atomic_dec (&et->refcount); +return en ? true : false; +} + +static void f2fs_update_extent_tree (struct inode *inode,pgoff_t fofs, +block_t blkaddr) +{ +struct f2fs_sb_info *sbi =F2FS_I_SB (inode); +nid_t ino = inode->i_ino; +struct extent_tree *et; +struct extent_node *en =NULL , *en1 =NULL , *en2 =NULL , *en3 =NULL ; +struct extent_node *den =NULL ; +struct extent_info *pei; +struct extent_info ei; +unsigned int endofs; + +if (is_inode_flag_set (F2FS_I (inode),FI_NO_EXTENT )) +return ;Quoted 8 lines
fs/f2fs/data.c end_update: · line 620
Quoted 6 lines
fs/f2fs/data.c +6
-0+ +retry: +down_write (&sbi->extent_tree_lock); + et =radix_tree_lookup (&sbi->extent_tree_root, ino); +if (!et) { + et =kmem_cache_alloc (extent_tree_slab,GFP_ATOMIC );et =
f2fs_kmem_cache_alloc(.., GFP_ATOMIC);
Quoted 1 line
How about modifying as below to avoid holding
extent_tree_lockfor long time?
Hmm. I don't think it doesn't take such the long time. It's GFP_ATOMIC.
Moreover, for radix_tree, I prefer to use f2fs_radix_tree_insert with GFP_NOIO. Since, we actually don't need to call kmem_cache_free.
Quoted 9 lines
et =
kmem_cache_alloc(extent_tree_slab, GFP_ATOMIC);if (!et) { up_write(&sbi->extent_tree_lock); cond_resched(); goto retry; }Quoted 1 line
Quoted 9 lines
Quoted 7 lines
fs/f2fs/data.c end_update: · line 627
Quoted 7 lines
fs/f2fs/data.c +7
-0+if (!et) { +up_write (&sbi->extent_tree_lock); + goto retry; + } +if (radix_tree_insert (&sbi->extent_tree_root, ino, et)) { +up_write (&sbi->extent_tree_lock); +kmem_cache_free (extent_tree_slab, et);
cond_resched()?
I'm not sure why this should be needed.
There is rw_semaphore, so we have already a rescheduling point.
Quoted 30 lines
Quoted 11 lines
Quoted 11 lines
fs/f2fs/data.c +10
-0+ goto retry; + } +memset (et,0 ,sizeof (struct extent_tree )); + et->ino = ino; + et->root =RB_ROOT ; +rwlock_init (&et->lock); +atomic_set (&et->refcount,0 ); + et->count =0 ; + sbi->total_ext_tree++; + }Quoted 8 lines
fs/f2fs/data.c end_update: · line 643
Quoted 6 lines
fs/f2fs/data.c +6
-0+atomic_inc (&et->refcount); +up_write (&sbi->extent_tree_lock); + +write_lock (&et->lock); + +/* 1. lookup and remove exist extent info in cache */ existing
got it.
Quoted 4 lines
fs/f2fs/data.c end_update: · line 644
Quoted 2 lines
fs/f2fs/data.c +1
-0+ en =__remove_extent_tree (et, fofs);en =
__detach_extent_node();?OK, it seems that most codes of
__remove_extent_treeand__lookup_extent_treeare the same, so here I want to remove extent node like this:
Quoted 8 lines
en = __lookup_extent_tree(et, fofs); if (!en) goto update_extent; dei = en->ei; __detach_extent_node(sbi, et, en);How do you think?
Looks good to me.
Quoted 44 lines
Quoted 35 lines
Quoted 35 lines
fs/f2fs/data.c +33
-0+if (!en) + goto update_extent; + + pei = &en->ei; +/* 2. if extent can be split more, split and insert the left part */ +if (pei->len >1 ) { +/* insert left part of split extent into cache */ +if (pei->fofs < fofs) { +set_extent_info (&ei, pei->fofs, pei->blk, + fofs - pei->fofs); + en1 =__insert_extent_tree (sbi, et, &ei,NULL ); + } + +/* insert right part of split extent into cache */ + endofs = pei->fofs + pei->len -1 ; +if (endofs > fofs) { +set_extent_info (&ei, fofs +1 , + fofs - pei->fofs + pei->blk, endofs - fofs); + en2 =__insert_extent_tree (sbi, et, &ei,NULL ); + } + } + +update_extent: +/* 3. update extent in extent cache */ +if (blkaddr) { +set_extent_info (&ei, fofs, blkaddr,1 ); + en3 =__insert_extent_tree (sbi, et, &ei, &den); + } + +/* 4. update in global extent list */ +spin_lock (&sbi->extent_lock); +if (en && !list_empty (&en->list)) +list_del_init (&en->list);Quoted 8 lines
fs/f2fs/data.c end_update: · line 683
Quoted 6 lines
fs/f2fs/data.c +6
-0+/* +* en1 and en2 split from en, they will become more and more smaller +* fragments after splitting several times. So if the length is smaller +* than F2FS_MIN_EXTENT_LEN, we will not add them into extent_list, +* but just waiting shrinker to free them for reclaiming when OOM. +*/ Can we just remove en1 and en2 in
__insert_extent_tree?
Quoted 3 lines
en1 and en2 is newly added, in
__attach_extent_nodewe do not add en1 and en2 into lru list, so if you do not want to keep split part in lru list, let's just remove the below codes.
What I meant was, how about avoiding attaching en1 and en2, if they are splits whose lens are less than F2FS_MIN_EXTENT_LEN in advance?
Quoted 87 lines
Quoted 13 lines
Quoted 13 lines
fs/f2fs/data.c +11
-0+if (en1 && en1->ei.len >=F2FS_MIN_EXTENT_LEN ) +list_add_tail (&en1->list, &sbi->extent_list); +if (en2 && en2->ei.len >=F2FS_MIN_EXTENT_LEN ) +list_add_tail (&en2->list, &sbi->extent_list); +if (en3) { +if (list_empty (&en3->list)) +list_add_tail (&en3->list, &sbi->extent_list); +else +list_move_tail (&en3->list, &sbi->extent_list); + } +if (den && !list_empty (&den->list))Quoted 8 lines
fs/f2fs/data.c end_update: · line 700
Quoted 6 lines
fs/f2fs/data.c +6
-0+list_del_init (&den->list); +spin_unlock (&sbi->extent_lock); + +if (en) { +kmem_cache_free (extent_node_slab, en); +atomic_dec (&sbi->total_ext_node);--> move into __detach_extent_node().will do.
Quoted 54 lines
Quoted 54 lines
fs/f2fs/data.c +53
-0+ } +if (den) { +kmem_cache_free (extent_node_slab, den); +atomic_dec (&sbi->total_ext_node); + } + +write_unlock (&et->lock); +atomic_dec (&et->refcount); +} + +void f2fs_shrink_extent_tree (struct f2fs_sb_info *sbi,int nr_shrink) +{ +struct extent_tree *treevec[EXT_TREE_VEC_SIZE ]; +struct extent_node *en, *tmp; +unsigned long ino =F2FS_ROOT_INO (sbi); +struct radix_tree_iter iter; +void **slot; +unsigned int found; +unsigned int node_cnt =0 , tree_cnt =0 ; + +if (available_free_memory (sbi,EXTENT_CACHE )) +return ; + +spin_lock (&sbi->extent_lock); +list_for_each_entry_safe (en, tmp, &sbi->extent_list, list) { +if (!nr_shrink--) +break ; +list_del_init (&en->list); + } +spin_unlock (&sbi->extent_lock); + +down_read (&sbi->extent_tree_lock); +while ((found =radix_tree_gang_lookup (&sbi->extent_tree_root, + (void **)treevec, ino,EXT_TREE_VEC_SIZE ))) { +unsigned i; + + ino = treevec[found -1 ]->ino +1 ; +for (i =0 ; i < found; i++) { +struct extent_tree *et = treevec[i]; + +atomic_inc (&et->refcount); +write_lock (&et->lock); + node_cnt +=__free_extent_tree (sbi, et, false); +write_unlock (&et->lock); +atomic_dec (&et->refcount); + } + } +up_read (&sbi->extent_tree_lock); + +down_write (&sbi->extent_tree_lock); +radix_tree_for_each_slot (slot, &sbi->extent_tree_root, &iter, +F2FS_ROOT_INO (sbi)) { +struct extent_tree *et = (struct extent_tree *)*slot;Quoted 8 lines
fs/f2fs/data.c end_update: · line 759
Quoted 6 lines
fs/f2fs/data.c +6
-0+ +if (!atomic_read (&et->refcount) && !et->count) { +radix_tree_delete (&sbi->extent_tree_root, et->ino); +kmem_cache_free (extent_tree_slab, et); + sbi->total_ext_tree--; + tree_cnt++;No use of
tree_cnt.
Quoted 1 line
This is used by trace function in RFC PATCH 10/10.
Well, then, it needs to add tree_cnt in Patch #10. :)
Thanks,
Quoted 10 lines
Thanks for your review! :)
Regards,
YuQuoted 2 lines
Thanks,
[snip]
Hi Jaegeuk,
Quoted 30 lines
-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
Sent: Saturday, January 24, 2015 3:43 AM
To: Chao Yu
Cc: 'Changman Lee'; [email protected]; [email protected]
Subject: Re: [f2fs-dev][RFC PATCH 06/10] f2fs: add core functions for rb-tree extent cacheQuoted 21 lines · Chao Yu
Hi Jaegeuk,
Quoted 19 lines
-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
Sent: Friday, January 23, 2015 9:48 AM
To: Chao Yu
Cc: Changman Lee; [email protected]; [email protected]
Subject: Re: [f2fs-dev][RFC PATCH 06/10] f2fs: add core functions for rb-tree extent cacheQuoted 11 lines · Chao Yu
This patch adds core functions including slab cache init function and
init/lookup/update/shrink/destroyfunction 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 acached_eiinto structextent_treefor a quick recent cache.
* register rb-based extent cache shrink with mm shrink interface.
* disable dir inode's extent cache.
[snip]
Quoted 23 lines
Quoted 23 lines
Quoted 22 lines
Quoted 10 lines
fs/f2fs/data.c +10
-0+static void f2fs_update_extent_tree (struct inode *inode,pgoff_t fofs, +block_t blkaddr) +{ +struct f2fs_sb_info *sbi =F2FS_I_SB (inode); +nid_t ino = inode->i_ino; +struct extent_tree *et; +struct extent_node *en =NULL , *en1 =NULL , *en2 =NULL , *en3 =NULL ; +struct extent_node *den =NULL ; +struct extent_info *pei; +struct extent_info ei;fs/f2fs/data.c end_update: · line 620
Quoted 10 lines
fs/f2fs/data.c +10
-0+unsigned int endofs; + +if (is_inode_flag_set (F2FS_I (inode),FI_NO_EXTENT )) +return ; + +retry: +down_write (&sbi->extent_tree_lock); + et =radix_tree_lookup (&sbi->extent_tree_root, ino); +if (!et) { + et =kmem_cache_alloc (extent_tree_slab,GFP_ATOMIC );et =
f2fs_kmem_cache_alloc(.., GFP_ATOMIC);
Quoted 7 lines
Quoted 1 line
How about modifying as below to avoid holding
extent_tree_lockfor long time?Hmm. I don't think it doesn't take such the long time. It's
GFP_ATOMIC.Moreover, for
radix_tree, I prefer to usef2fs_radix_tree_insertwithGFP_NOIO. Since, we actually don't need to callkmem_cache_free.
How about use following code?
f2fs_kmem_cache_alloc(extent_tree_slab, GFP_NOFS); f2fs_radix_tree_insert(&sbi->extent_tree_root, ino, et);
in init_extent_cache_info()
INIT_RADIX_TREE(&sbi->extent_tree_root, GFP_NOIO);
Quoted 23 lines
Quoted 10 lines
et =
kmem_cache_alloc(extent_tree_slab, GFP_ATOMIC);if (!et) { up_write(&sbi->extent_tree_lock); cond_resched(); goto retry; }Quoted 1 line
Quoted 9 lines
Quoted 7 lines
fs/f2fs/data.c end_update: · line 627
Quoted 7 lines
fs/f2fs/data.c +7
-0+if (!et) { +up_write (&sbi->extent_tree_lock); + goto retry; + } +if (radix_tree_insert (&sbi->extent_tree_root, ino, et)) { +up_write (&sbi->extent_tree_lock); +kmem_cache_free (extent_tree_slab, et);
cond_resched()?I'm not sure why this should be needed.
There isrw_semaphore, so we have already a rescheduling point.
[snip]
Quoted 8 lines
Quoted 5 lines
Quoted 1 line
Can we just remove en1 and en2 in
__insert_extent_tree?en1 and en2 is newly added, in
__attach_extent_nodewe do not add en1 and en2 into lru list, so if you do not want to keep split part in lru list, let's just remove the below codes.What I meant was, how about avoiding attaching en1 and en2, if they are splits whose lens are less than
F2FS_MIN_EXTENT_LENin advance?
Oh, it's better, I will do it.
[snip]
Quoted 5 lines
Quoted 3 lines
Quoted 1 line
No use of
tree_cnt.This is used by trace function in RFC PATCH 10/10.
Well, then, it needs to add
tree_cntin Patch #10. :)
OK, let's move it. :)
Thanks,
Quoted 13 lines
Thanks,
Quoted 10 lines
Thanks for your review! :)
Regards,
YuQuoted 2 lines
Thanks,
[snip]