Skip to contentSkip to conversation

f2fs: add core functions for rb-tree extent cache

RFC PATCH Superseded Chao Yu 4 participants 9 messages Jan 12, 2015 – Jan 26, 2015 F2FS file system

v1 of 3 Superseded Latest is v3 →

lore
Share & tools
lore

Chao Yu

author
#0 lore raw

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
index 4f5b871e..bf8c5eb 100644
@@ -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
index d7c1436..387017f 100644
@@ -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
#1 lore raw

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/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 +0 -0
index 4f5b871e..bf8c5eb 100644

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/

author
#2 lore raw

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 cache

Hi 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/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.

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
index 4f5b871e..bf8c5eb 100644
@@ -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 using f2fs_kmem_cache_alloc and f2fs_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_tree to free extent_node that list_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 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.

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,
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/

#3 lore raw
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 cache

Hi 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/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.

Quoted 7 lines
Quoted 3 lines
Quoted 3 lines

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
index 4f5b871e..bf8c5eb 100644
@@ -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 using f2fs_kmem_cache_alloc and f2fs_radix_tree_insert ?

Quoted 5 lines

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.

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_tree to free extent_node that list_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 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.

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,
Yu

Quoted 49 lines

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/

author
#4 lore raw

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 cache

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 cache

Hi 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/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.

Quoted 7 lines
Quoted 3 lines
Quoted 3 lines

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
index 4f5b871e..bf8c5eb 100644
@@ -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 7 lines
Quoted 5 lines

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.

I see. If so, let's use cond_resched() in front of goto retry after up_write.

Ah, yes, I will do that.

Quoted 1 line

And also look into kmem_cache_alloc in __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_tree to free extent_node that list_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 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.

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,
Yu

Quoted 49 lines

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/

maintainer
#5 lore raw
In reply to Chao Yu
Quoted 71 lines · 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.

---
 fs/f2fs/data.c | 458 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 fs/f2fs/node.c |   9 +-
 2 files changed, 466 insertions(+), 1 deletion(-)
fs/f2fs/data.c +37 -0
index 4f5b871e..bf8c5eb 100644
@@ -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
index d7c1436..387017f 100644
@@ -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
author
#6 lore raw

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 cache

Quoted 77 lines · 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.

---
 fs/f2fs/data.c | 458 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 fs/f2fs/node.c |   9 +-
 2 files changed, 466 insertions(+), 1 deletion(-)
fs/f2fs/data.c +43 -0
index 4f5b871e..bf8c5eb 100644
@@ -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]

maintainer
#7 lore raw
Quoted 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 cache

Quoted 11 lines · 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.

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(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;
}
Quoted 7 lines

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);
}

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() 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.

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_lock for 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_tree and __lookup_extent_tree are 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_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.

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,
Yu

Quoted 2 lines

Thanks,

[snip]

author
#8 lore raw

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 cache

Quoted 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 cache

Quoted 11 lines · 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.

[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_lock for 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.

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 is rw_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_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.

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?

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_cnt in Patch #10. :)

OK, let's move it. :)

Thanks,

Quoted 13 lines

Thanks,

Quoted 10 lines

Thanks for your review! :)

Regards,
Yu

Quoted 2 lines

Thanks,

[snip]