f2fs: add extent cache base on rb-tree

Now f2fs have page-block mapping cache which can cache only one extent mapping between contiguous logical address and physical address. Normally, this design will work well because f2fs will expand coverage area of the mapping extent when we write forward sequentially. But when we write data randomly in Out-Place-Update mode, the extent will be shorten and hardly be expanded for most time as following reasons:
1.The short part of extent will be discarded if we break contiguous mapping in the middle of extent.
2.The new mapping will be added into mapping cache only at head or tail of the extent.
3.We will drop the extent cache when the extent became very fragmented. 4.We will not update the extent with mapping which we get from readpages or readpage.

To solve above problems, this patch adds extent cache base on rb-tree like other filesystems (e.g.: ext4/btrfs) in f2fs. By this way, f2fs can support another more effective cache between dnode page cache and disk. It will supply high hit ratio in the cache with fewer memory when dnode page cache are reclaimed in environment of low memory.

Todo:
*introduce mount option for extent cache.
*add shrink ability for extent cache.

Signed-off-by Chao Yu <[email protected]>

---
 fs/f2fs/data.c  | 348 +++++++++++++++++++++++++++++++++++++++++---------------
 fs/f2fs/debug.c |   2 +
 fs/f2fs/f2fs.h  |  49 ++++----
 fs/f2fs/inode.c |   5 +-
 fs/f2fs/super.c |  11 +-
 5 files changed, 291 insertions(+), 124 deletions(-)

fs/f2fs/data.c +54 -30

index 7ec697b..20592e2 100644
@@ -24,6 +24,8 @@
 #include "segment.h"
 #include <trace/events/f2fs.h>
 
+struct kmem_cache *extent_info_cache;
+
 static void f2fs_read_end_io(struct bio *bio, int err)
 {
 	struct bio_vec *bvec;

@@ -247,126 +249,264 @@ int f2fs_reserve_block(struct dnode_of_data *dn, pgoff_t index)
 	return err;
 }
 
-static int check_extent_cache(struct inode *inode, pgoff_t pgofs,
-					struct buffer_head *bh_result)
+static struct extent_info *__insert_extent_cache(struct inode *inode,
+				unsigned int fofs, unsigned int len, u32 blk)
 {
-	struct f2fs_inode_info *fi = F2FS_I(inode);
-	pgoff_t start_fofs, end_fofs;
-	block_t start_blkaddr;
-
-	if (is_inode_flag_set(fi, FI_NO_EXTENT))
-		return 0;
-
-	read_lock(&fi->ext.ext_lock);
-	if (fi->ext.len == 0) {
-		read_unlock(&fi->ext.ext_lock);
-		return 0;
+	struct rb_root *root = &F2FS_I(inode)->ei_tree.root;
+	struct rb_node *p = root->rb_node;
+	struct rb_node *parent = NULL;
+	struct extent_info *ei;
+
+	while (p) {
+		parent = p;
+		ei = rb_entry(parent, struct extent_info, rb_node);
+
+		if (fofs < ei->fofs)
+			p = p->rb_left;
+		else if (fofs >= ei->fofs + ei->len)
+			p = p->rb_right;
+		else
+			f2fs_bug_on(F2FS_I_SB(inode), 1);
 	}
 
-	stat_inc_total_hit(inode->i_sb);
+	ei = kmem_cache_alloc(extent_info_cache, GFP_ATOMIC);
+	ei->fofs = fofs;
+	ei->blk = blk;
+	ei->len = len;
+
+	rb_link_node(&ei->rb_node, parent, &p);
+	rb_insert_color(&ei->rb_node, root);
+	stat_inc_extent_count(inode->i_sb);
+	return ei;
+}
 
-	start_fofs = fi->ext.fofs;
-	end_fofs = fi->ext.fofs + fi->ext.len - 1;
-	start_blkaddr = fi->ext.blk_addr;
+static bool __remove_extent_cache(struct inode *inode, unsigned int fofs,
+							struct extent_info *cei)
+{
+	struct rb_root *root = &F2FS_I(inode)->ei_tree.root;
+	struct rb_node *p = root->rb_node;
+	struct extent_info *ei;
 
-	if (pgofs >= start_fofs && pgofs <= end_fofs) {
-		unsigned int blkbits = inode->i_sb->s_blocksize_bits;
-		size_t count;
+	while (p) {
+		ei = rb_entry(p, struct extent_info, rb_node);
 
-		clear_buffer_new(bh_result);
-		map_bh(bh_result, inode->i_sb,
-				start_blkaddr + pgofs - start_fofs);
-		count = end_fofs - pgofs + 1;
-		if (count < (UINT_MAX >> blkbits))
-			bh_result->b_size = (count << blkbits);
+		if (fofs < ei->fofs)
+			p = p->rb_left;
+		else if (fofs >= ei->fofs + ei->len)
+			p = p->rb_right;
 		else
-			bh_result->b_size = UINT_MAX;
+			goto found;
+	}
+	return true;
+found:
+	ei = rb_entry(p, struct extent_info, rb_node);
+	cei->fofs = ei->fofs;
+	cei->blk = ei->blk;
+	cei->len = ei->len;
+	rb_erase(&ei->rb_node, root);
+	kmem_cache_free(extent_info_cache, ei);
+	stat_dec_extent_count(inode->i_sb);
+	return false;
+}
 
-		stat_inc_read_hit(inode->i_sb);
-		read_unlock(&fi->ext.ext_lock);
-		return 1;

fs/f2fs/data.c +190 -64

+			ei->fofs = pei->fofs;
+			ei->blk = pei->blk;
+			ei->len += pei->len;
+			rb_erase(&pei->rb_node, root);
+			kmem_cache_free(extent_info_cache, pei);
+			stat_dec_extent_count(inode->i_sb);
+		}
+	}
+
+	node = rb_next(&ei->rb_node);
+	if (node) {
+		pei = rb_entry(node, struct extent_info, rb_node);
+		if (ei->blk + 1 == pei->blk) {
+			ei->len += pei->len;
+			rb_erase(&pei->rb_node, root);
+			kmem_cache_free(extent_info_cache, pei);
+			stat_dec_extent_count(inode->i_sb);
+		}
 	}
-	read_unlock(&fi->ext.ext_lock);
-	return 0;
 }
 
-void update_extent_cache(block_t blk_addr, struct dnode_of_data *dn)
+inline void get_extent_info(struct inode *inode, struct f2fs_extent *i_ext)
 {
-	struct f2fs_inode_info *fi = F2FS_I(dn->inode);
-	pgoff_t fofs, start_fofs, end_fofs;
-	block_t start_blkaddr, end_blkaddr;
-	int need_update = true;
+	struct f2fs_ei_tree *tree = &F2FS_I(inode)->ei_tree;
+	struct extent_info *ei;
+
+	write_lock(&tree->ei_lock);
+	ei = __insert_extent_cache(inode, le32_to_cpu(i_ext->fofs),
+			le32_to_cpu(i_ext->len), le32_to_cpu(i_ext->blk_addr));
+	tree->cached_ei = ei;
+	write_unlock(&tree->ei_lock);
+}
 
-	f2fs_bug_on(F2FS_I_SB(dn->inode), blk_addr == NEW_ADDR);
-	fofs = start_bidx_of_node(ofs_of_node(dn->node_page), fi) +
-							dn->ofs_in_node;
+inline void set_raw_extent(struct f2fs_ei_tree *tree,
+					struct f2fs_extent *i_ext)
+{
+	struct extent_info *ei = tree->cached_ei;
 
-	/* Update the page address in the parent node */
-	__set_data_blkaddr(dn, blk_addr);
+	read_lock(&tree->ei_lock);
+	if (ei) {
+		i_ext->fofs = cpu_to_le32(ei->fofs);
+		i_ext->blk_addr = cpu_to_le32(ei->blk);
+		i_ext->len = cpu_to_le32(ei->len);
+	}
+	read_unlock(&tree->ei_lock);
+}
 
-	if (is_inode_flag_set(fi, FI_NO_EXTENT))
-		return;
+bool f2fs_lookup_extent_cache(struct inode *inode, pgoff_t pgofs,
+							struct extent_info *ei)
+{
+	struct f2fs_ei_tree *tree = &F2FS_I(inode)->ei_tree;
+	struct rb_node *node;
+	struct extent_info *pei;
 
-	write_lock(&fi->ext.ext_lock);
+	if (is_inode_flag_set(F2FS_I(inode), FI_NO_EXTENT))
+		return false;
 
-	start_fofs = fi->ext.fofs;
-	end_fofs = fi->ext.fofs + fi->ext.len - 1;
-	start_blkaddr = fi->ext.blk_addr;
-	end_blkaddr = fi->ext.blk_addr + fi->ext.len - 1;
+	read_lock(&tree->ei_lock);
 
-	/* Drop and initialize the matched extent */
-	if (fi->ext.len == 1 && fofs == start_fofs)
-		fi->ext.len = 0;
+	stat_inc_total_hit(inode->i_sb);
 
-	/* Initial extent */
-	if (fi->ext.len == 0) {
-		if (blk_addr != NULL_ADDR) {
-			fi->ext.fofs = fofs;
-			fi->ext.blk_addr = blk_addr;
-			fi->ext.len = 1;
-		}
-		goto end_update;
+	/* #1: find recently accessed extent info firstly */
+	if (tree->cached_ei) {
+		pei = tree->cached_ei;
+		if (pgofs >= pei->fofs && pgofs < pei->fofs + pei->len)
+			goto found;
 	}
 
-	/* Front merge */
-	if (fofs == start_fofs - 1 && blk_addr == start_blkaddr - 1) {
-		fi->ext.fofs--;
-		fi->ext.blk_addr--;
-		fi->ext.len++;
-		goto end_update;
+	/* #2: find in rb tree */
+	node = tree->root.rb_node;
+	while (node) {
+		pei = rb_entry(node, struct extent_info, rb_node);
+		if (pgofs < pei->fofs)
+			node = node->rb_left;
+		else if (pgofs >= pei->fofs + pei->len)
+			node = node->rb_right;
+		else
+			goto found;
 	}
 
-	/* Back merge */
-	if (fofs == end_fofs + 1 && blk_addr == end_blkaddr + 1) {
-		fi->ext.len++;
-		goto end_update;
-	}
+	read_unlock(&tree->ei_lock);
+	return false;
+found:
+	ei->fofs = pei->fofs;
+	ei->blk = pei->blk;
+	ei->len = pei->len;
+	stat_inc_read_hit(inode->i_sb);
+	read_unlock(&tree->ei_lock);
+	return true;
+}
 
-	/* Split the existing extent */
-	if (fi->ext.len > 1 &&
-		fofs >= start_fofs && fofs <= end_fofs) {
-		if ((end_fofs - fofs) < (fi->ext.len >> 1)) {
-			fi->ext.len = fofs - start_fofs;
-		} else {
-			fi->ext.fofs = fofs + 1;
-			fi->ext.blk_addr = start_blkaddr +
-					fofs - start_fofs + 1;
-			fi->ext.len -= fofs - start_fofs + 1;
-		}
-	} else {
-		need_update = false;
+void f2fs_update_extent_cache(struct inode *inode, pgoff_t fofs,
+							block_t blk_addr)
+{
+	struct f2fs_ei_tree *tree = &F2FS_I(inode)->ei_tree;
+	struct extent_info ei;
+	struct extent_info *pei = NULL;
+	unsigned int endofs;
+
+	if (is_inode_flag_set(F2FS_I(inode), FI_NO_EXTENT))
+		return;
+
+	if (blk_addr == NEW_ADDR)
+		return;
+
+	write_lock(&tree->ei_lock);
+
+	/* update old extent mapping */
+	if (__remove_extent_cache(inode, fofs, &ei))
+		goto add_extent;
+	if (ei.len == 1)
+		goto add_extent;
+
+	if (ei.fofs < fofs)
+		__insert_extent_cache(inode, ei.fofs, fofs - ei.fofs, ei.blk);
+
+	endofs = ei.fofs + ei.len - 1;
+	if (endofs > fofs)
+		__insert_extent_cache(inode, fofs + 1, endofs - fofs,
+						fofs - ei.fofs + ei.blk);
+
+add_extent:
+	/* insert new mapping extent to rb tree */
+	if (blk_addr) {
+		pei = __insert_extent_cache(inode, fofs, 1, blk_addr);
+		__try_merge_extent(inode, pei);
 	}
 
-	/* Finally, if the extent is very fragmented, let's drop the cache. */
-	if (fi->ext.len < F2FS_MIN_EXTENT_LEN) {
-		fi->ext.len = 0;
-		set_inode_flag(fi, FI_NO_EXTENT);
-		need_update = true;
+	if (pei)
+		tree->cached_ei = pei;
+
+	write_unlock(&tree->ei_lock);
+}
+
+void f2fs_free_extent_cache(struct inode *inode)
+{
+	struct f2fs_ei_tree *tree = &F2FS_I(inode)->ei_tree;
+	struct rb_node *node, *next;
+	struct extent_info *ei;
+
+	write_lock(&tree->ei_lock);
+	node = rb_first(&tree->root);
+	while (node) {
+		next = rb_next(node);
+		ei = rb_entry(node, struct extent_info, rb_node);
+		rb_erase(node, &tree->root);
+		kmem_cache_free(extent_info_cache, ei);
+		stat_dec_extent_count(inode->i_sb);
+		node = next;
 	}
-end_update:
-	write_unlock(&fi->ext.ext_lock);
-	if (need_update)
-		sync_inode_page(dn);
+	write_unlock(&tree->ei_lock);
+}
+
+static void f2fs_map_bh(struct inode *inode, pgoff_t pgofs,
+			struct extent_info *ei, struct buffer_head *bh_result)
+{
+	unsigned int blkbits = inode->i_sb->s_blocksize_bits;
+	pgoff_t start_fofs, end_fofs;
+	block_t start_blkaddr;
+	size_t count;
+
+	start_fofs = ei->fofs;
+	end_fofs = ei->fofs + ei->len - 1;
+	start_blkaddr = ei->blk;
+
+	clear_buffer_new(bh_result);
+	map_bh(bh_result, inode->i_sb,
+			start_blkaddr + pgofs - start_fofs);
+	count = end_fofs - pgofs + 1;
+	if (count < (UINT_MAX >> blkbits))
+		bh_result->b_size = (count << blkbits);
+	else
+		bh_result->b_size = UINT_MAX;
+}
+
+void update_extent_cache(block_t blk_addr, struct dnode_of_data *dn)
+{
+	struct f2fs_inode_info *fi = F2FS_I(dn->inode);
+	pgoff_t fofs;
+
+	f2fs_bug_on(F2FS_I_SB(dn->inode), blk_addr == NEW_ADDR);
+	fofs = start_bidx_of_node(ofs_of_node(dn->node_page), fi) +
+							dn->ofs_in_node;
+
+	/* Update the page address in the parent node */
+	__set_data_blkaddr(dn, blk_addr);
+
+	f2fs_update_extent_cache(dn->inode, fofs, blk_addr);
 	return;
 }
 

@@ -603,12 +743,15 @@ static int __get_data_block(struct inode *inode, sector_t iblock,
 	pgoff_t pgofs, end_offset;
 	int err = 0, ofs = 1;
 	bool allocated = false;
+	struct extent_info ei;
 
 	/* Get the page offset from the block offset(iblock) */
 	pgofs =	(pgoff_t)(iblock >> (PAGE_CACHE_SHIFT - blkbits));
 
-	if (check_extent_cache(inode, pgofs, bh_result))
+	if (f2fs_lookup_extent_cache(inode, pgofs, &ei)) {
+		f2fs_map_bh(inode, pgofs, &ei, bh_result);
 		goto out;
+	}
 
 	if (create) {
 		f2fs_balance_fs(F2FS_I_SB(inode));

@@ -628,6 +771,7 @@ static int __get_data_block(struct inode *inode, sector_t iblock,
 
 	if (dn.data_blkaddr != NULL_ADDR) {
 		map_bh(bh_result, inode->i_sb, dn.data_blkaddr);
+		f2fs_update_extent_cache(inode, pgofs, dn.data_blkaddr);
 	} else if (create) {
 		err = __allocate_data_block(&dn);
 		if (err)

@@ -672,6 +816,8 @@ get_next:
 			allocated = true;
 			blkaddr = dn.data_blkaddr;
 		}
+		if (!allocated)
+			f2fs_update_extent_cache(inode, pgofs, blkaddr);
 		/* Give more consecutive addresses for the readahead */
 		if (blkaddr == (bh_result->b_blocknr + ofs)) {
 			ofs++;

@@ -1160,6 +1306,20 @@ static sector_t f2fs_bmap(struct address_space *mapping, sector_t block)
 	return generic_block_bmap(mapping, block, get_data_block);
 }
 
+int __init create_extent_cache(void)
+{
+	extent_info_cache = f2fs_kmem_cache_create("f2fs_extent_info_cache",
+			sizeof(struct extent_info));
+	if (!extent_info_cache)
+		return -ENOMEM;
+	return 0;
+}
+
+void destroy_extent_cache(void)
+{
+	kmem_cache_destroy(extent_info_cache);
+}
+
 const struct address_space_operations f2fs_dblock_aops = {
 	.readpage	= f2fs_read_data_page,
 	.readpages	= f2fs_read_data_pages,

fs/f2fs/debug.c +2 -0

index 91e8f69..115cec0 100644
@@ -35,6 +35,7 @@ static void update_general_status(struct f2fs_sb_info *sbi)
 	/* validation check of the segment numbers */
 	si->hit_ext = sbi->read_hit_ext;
 	si->total_ext = sbi->total_hit_ext;
+	si->ext_count = sbi->total_ext_count;
 	si->ndirty_node = get_pages(sbi, F2FS_DIRTY_NODES);
 	si->ndirty_dent = get_pages(sbi, F2FS_DIRTY_DENTS);
 	si->ndirty_dirs = sbi->n_dirty_dirs;

@@ -249,6 +250,7 @@ static int stat_show(struct seq_file *s, void *v)
 		seq_printf(s, "  - node blocks : %d\n", si->node_blks);
 		seq_printf(s, "\nExtent Hit Ratio: %d / %d\n",
 			   si->hit_ext, si->total_ext);
+		seq_printf(s, "\nExtent Node Count: %d\n", si->ext_count);
 		seq_puts(s, "\nBalancing F2FS Async:\n");
 		seq_printf(s, "  - inmem: %4d\n",
 			   si->inmem_pages);

fs/f2fs/f2fs.h +23 -26

index ec58bb2..dab6fdb 100644
@@ -263,10 +263,16 @@ enum {
 #define F2FS_MIN_EXTENT_LEN	16	/* minimum extent length */
 
 struct extent_info {
-	rwlock_t ext_lock;	/* rwlock for consistency */
-	unsigned int fofs;	/* start offset in a file */
-	u32 blk_addr;		/* start block address of the extent */
-	unsigned int len;	/* length of the extent */
+	struct rb_node rb_node;		/* rb node located in rb-tree */
+	unsigned int fofs;		/* start offset in a file */
+	u32 blk;			/* start block address of the extent */
+	unsigned int len;		/* length of the extent */
+};
+
+struct f2fs_ei_tree {
+	struct rb_root root;		/* root of extent info rb-tree */
+	struct extent_info *cached_ei;	/* recently accessed extent */
+	rwlock_t ei_lock;		/* rwlock for consistency */
 };
 
 /*

@@ -294,7 +300,8 @@ struct f2fs_inode_info {
 	unsigned int clevel;		/* maximum level of given file name */
 	nid_t i_xattr_nid;		/* node id that contains xattrs */
 	unsigned long long xattr_ver;	/* cp version of xattr modification */
-	struct extent_info ext;		/* in-memory extent cache entry */
+	struct extent_info ext;
+	struct f2fs_ei_tree ei_tree;	/* in-memory extent cache entry */
 	struct dir_inode_entry *dirty_dir;	/* the pointer of dirty dir */
 
 	struct radix_tree_root inmem_root;	/* radix tree for inmem pages */

@@ -302,26 +309,6 @@ struct f2fs_inode_info {
 	struct mutex inmem_lock;	/* lock for inmemory pages */
 };
 
-static inline void get_extent_info(struct extent_info *ext,
-					struct f2fs_extent i_ext)
-{
-	write_lock(&ext->ext_lock);
-	ext->fofs = le32_to_cpu(i_ext.fofs);
-	ext->blk_addr = le32_to_cpu(i_ext.blk_addr);
-	ext->len = le32_to_cpu(i_ext.len);
-	write_unlock(&ext->ext_lock);
-}
-
-static inline void set_raw_extent(struct extent_info *ext,
-					struct f2fs_extent *i_ext)
-{
-	read_lock(&ext->ext_lock);
-	i_ext->fofs = cpu_to_le32(ext->fofs);
-	i_ext->blk_addr = cpu_to_le32(ext->blk_addr);
-	i_ext->len = cpu_to_le32(ext->len);
-	read_unlock(&ext->ext_lock);
-}
-
 struct f2fs_nm_info {
 	block_t nat_blkaddr;		/* base disk address of NAT */
 	nid_t max_nid;			/* maximum possible node ids */

@@ -590,6 +577,7 @@ struct f2fs_sb_info {
 	unsigned int segment_count[2];		/* # of allocated segments */
 	unsigned int block_count[2];		/* # of allocated blocks */
 	int total_hit_ext, read_hit_ext;	/* extent cache hit ratio */
+	int total_ext_count;                    /* extent cache node count */
 	atomic_t inline_inode;			/* # of inline_data inodes */
 	atomic_t inline_dir;			/* # of inline_dentry inodes */
 	int bg_gc;				/* background gc calls */

@@ -1462,12 +1450,17 @@ void f2fs_submit_page_mbio(struct f2fs_sb_info *, struct page *, block_t,
 						struct f2fs_io_info *);
 int reserve_new_block(struct dnode_of_data *);
 int f2fs_reserve_block(struct dnode_of_data *, pgoff_t);
+void set_raw_extent(struct f2fs_ei_tree *, struct f2fs_extent *);
+void get_extent_info(struct inode *, struct f2fs_extent *);
+void f2fs_free_extent_cache(struct inode *);
 void update_extent_cache(block_t, struct dnode_of_data *);
 struct page *find_data_page(struct inode *, pgoff_t, bool);
 struct page *get_lock_data_page(struct inode *, pgoff_t);
 struct page *get_new_data_page(struct inode *, struct page *, pgoff_t, bool);
 int do_write_data_page(struct page *, struct f2fs_io_info *);
 int f2fs_fiemap(struct inode *inode, struct fiemap_extent_info *, u64, u64);
+int __init create_extent_cache(void);
+void destroy_extent_cache(void);
 
 /*
  * gc.c

@@ -1495,7 +1488,7 @@ struct f2fs_stat_info {
 	struct f2fs_sb_info *sbi;
 	int all_area_segs, sit_area_segs, nat_area_segs, ssa_area_segs;
 	int main_area_segs, main_area_sections, main_area_zones;
-	int hit_ext, total_ext;
+	int hit_ext, total_ext, ext_count;
 	int ndirty_node, ndirty_dent, ndirty_dirs, ndirty_meta;
 	int nats, sits, fnids;
 	int total_count, utilization;

@@ -1529,6 +1522,8 @@ static inline struct f2fs_stat_info *F2FS_STAT(struct f2fs_sb_info *sbi)
 #define stat_dec_dirty_dir(sbi)		((sbi)->n_dirty_dirs--)
 #define stat_inc_total_hit(sb)		((F2FS_SB(sb))->total_hit_ext++)
 #define stat_inc_read_hit(sb)		((F2FS_SB(sb))->read_hit_ext++)
+#define stat_inc_extent_count(sb)	((F2FS_SB(sb))->total_ext_count++)
+#define stat_dec_extent_count(sb)	((F2FS_SB(sb))->total_ext_count--)
 #define stat_inc_inline_inode(inode)					\
 	do {								\
 		if (f2fs_has_inline_data(inode))			\

@@ -1593,6 +1588,8 @@ void f2fs_destroy_root_stats(void);
 #define stat_dec_dirty_dir(sbi)
 #define stat_inc_total_hit(sb)
 #define stat_inc_read_hit(sb)
+#define stat_inc_extent_count(sb)
+#define stat_dec_extent_count(sb)
 #define stat_inc_inline_inode(inode)
 #define stat_dec_inline_inode(inode)
 #define stat_inc_inline_dir(inode)

fs/f2fs/inode.c +3 -2

index 196cc78..ae0dd9b 100644
@@ -137,7 +137,7 @@ static int do_read_inode(struct inode *inode)
 	fi->i_pino = le32_to_cpu(ri->i_pino);
 	fi->i_dir_level = ri->i_dir_level;
 
-	get_extent_info(&fi->ext, ri->i_ext);
+	get_extent_info(inode, &ri->i_ext);
 	get_inline_info(fi, ri);
 
 	/* check data exist */

@@ -227,7 +227,7 @@ void update_inode(struct inode *inode, struct page *node_page)
 	ri->i_links = cpu_to_le32(inode->i_nlink);
 	ri->i_size = cpu_to_le64(i_size_read(inode));
 	ri->i_blocks = cpu_to_le64(inode->i_blocks);
-	set_raw_extent(&F2FS_I(inode)->ext, &ri->i_ext);
+	set_raw_extent(&F2FS_I(inode)->ei_tree, &ri->i_ext);
 	set_raw_inline(F2FS_I(inode), ri);
 
 	ri->i_atime = cpu_to_le64(inode->i_atime.tv_sec);

@@ -335,6 +335,7 @@ void f2fs_evict_inode(struct inode *inode)
 no_delete:
 	stat_dec_inline_dir(inode);
 	stat_dec_inline_inode(inode);
+	f2fs_free_extent_cache(inode);
 	invalidate_mapping_pages(NODE_MAPPING(sbi), inode->i_ino, inode->i_ino);
 	if (xnid)
 		invalidate_mapping_pages(NODE_MAPPING(sbi), xnid, xnid);

fs/f2fs/super.c +9 -2

index f71421d..f205493 100644
@@ -381,7 +381,9 @@ static struct inode *f2fs_alloc_inode(struct super_block *sb)
 	atomic_set(&fi->dirty_pages, 0);
 	fi->i_current_depth = 1;
 	fi->i_advise = 0;
-	rwlock_init(&fi->ext.ext_lock);
+	fi->ei_tree.root = RB_ROOT;
+	fi->ei_tree.cached_ei = NULL;
+	rwlock_init(&fi->ei_tree.ei_lock);
 	init_rwsem(&fi->i_sem);
 	INIT_RADIX_TREE(&fi->inmem_root, GFP_NOFS);
 	INIT_LIST_HEAD(&fi->inmem_pages);

@@ -1235,10 +1237,13 @@ static int __init init_f2fs_fs(void)
 	err = create_checkpoint_caches();
 	if (err)
 		goto free_gc_caches;
+	err = create_extent_cache();
+	if (err)
+		goto free_checkpoint_caches;
 	f2fs_kset = kset_create_and_add("f2fs", NULL, fs_kobj);
 	if (!f2fs_kset) {
 		err = -ENOMEM;
-		goto free_checkpoint_caches;
+		goto free_extent_cache;
 	}
 	err = register_filesystem(&f2fs_fs_type);
 	if (err)

@@ -1249,6 +1254,8 @@ static int __init init_f2fs_fs(void)
 
 free_kset:
 	kset_unregister(f2fs_kset);
+free_extent_cache:
+	destroy_extent_cache();
 free_checkpoint_caches:
 	destroy_checkpoint_caches();
 free_gc_caches:

Signature · 1 line

2.1.2

-----Original Message-----
From: Changman Lee [mailto:[email protected]]
Sent: Monday, December 22, 2014 10:03 AM
To: Chao Yu
Cc: Jaegeuk Kim; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi Yu,

Good approach.

As you know, however, f2fs breaks extent itself due to COW.

Unlike other filesystem like btrfs, minimum extent of f2fs could have 4KB granularity. So we would have lots of extents per inode and it could lead to overhead to manage extents.

Anyway, mount option could be alternative for this patch.

Quoted 26 lines

Now f2fs have page-block mapping cache which can cache only one extent mapping between contiguous logical address and physical address. Normally, this design will work well because f2fs will expand coverage area of the mapping extent when we write forward sequentially. But when we write data randomly in Out-Place-Update mode, the extent will be shorten and hardly be expanded for most time as following reasons:
1.The short part of extent will be discarded if we break contiguous mapping in the middle of extent.
2.The new mapping will be added into mapping cache only at head or tail of the extent.
3.We will drop the extent cache when the extent became very fragmented. 4.We will not update the extent with mapping which we get from readpages or readpage.

To solve above problems, this patch adds extent cache base on rb-tree like other filesystems (e.g.: ext4/btrfs) in f2fs. By this way, f2fs can support another more effective cache between dnode page cache and disk. It will supply high hit ratio in the cache with fewer memory when dnode page cache are reclaimed in environment of low memory.

Todo:
*introduce mount option for extent cache.
*add shrink ability for extent cache.

Signed-off-by Chao Yu <[email protected]>

---

Hi Changman,

Quoted 10 lines

-----Original Message-----
From: Changman Lee [mailto:[email protected]]
Sent: Monday, December 22, 2014 10:03 AM
To: Chao Yu
Cc: Jaegeuk Kim; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi Yu,

Good approach.

Thank you. :)

Quoted 1 line

As you know, however, f2fs breaks extent itself due to COW.

Yes, and sometimes f2fs use IPU when override writing, in this condition, by using this approach we can cache more contiguous mapping extent for better performance.

Quoted 4 lines

Unlike other filesystem like btrfs, minimum extent of f2fs could have 4KB granularity. So we would have lots of extents per inode and it could lead to overhead to manage extents.

Agree, the more number of extents are growing in one inode, the more memory pressure and longer latency operating in rb-tree we are facing.
IMO, to solve this problem, we'd better to add limitation or shrink ability into extent cache:
1.limit extent number per inode with the value set from sysfs and discard extent from inode's extent lru list if we touch the limitation; (e.g. in FAT, max number of mapping extent per inode is fixed: 8)
2.add all extents of inodes into a global lru list, we will try to shrink this list if we're facing memory pressure.

How do you think? or any better ideas are welcome. :)

Quoted 3 lines

Anyway, mount option could be alternative for this patch.

Yes, will do.

Thanks,
Yu

Quoted 28 lines · Chao Yu

Quoted 26 lines

Now f2fs have page-block mapping cache which can cache only one extent mapping between contiguous logical address and physical address. Normally, this design will work well because f2fs will expand coverage area of the mapping extent when we write forward sequentially. But when we write data randomly in Out-Place-Update mode, the extent will be shorten and hardly be expanded for most time as following reasons:
1.The short part of extent will be discarded if we break contiguous mapping in the middle of extent.
2.The new mapping will be added into mapping cache only at head or tail of the extent.
3.We will drop the extent cache when the extent became very fragmented. 4.We will not update the extent with mapping which we get from readpages or readpage.

To solve above problems, this patch adds extent cache base on rb-tree like other filesystems (e.g.: ext4/btrfs) in f2fs. By this way, f2fs can support another more effective cache between dnode page cache and disk. It will supply high hit ratio in the cache with fewer memory when dnode page cache are reclaimed in environment of low memory.

Todo:
*introduce mount option for extent cache.
*add shrink ability for extent cache.

Signed-off-by Chao Yu <[email protected]>

---

-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
Sent: Tuesday, December 23, 2014 7:16 AM
To: Chao Yu
Cc: 'Changman Lee'; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi Chao,

Quoted 15 lines · Chao Yu

Hi Changman,

Quoted 10 lines

-----Original Message-----
From: Changman Lee [mailto:[email protected]]
Sent: Monday, December 22, 2014 10:03 AM
To: Chao Yu
Cc: Jaegeuk Kim; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi Yu,

Good approach.

Thank you. :)

Quoted 5 lines

Quoted 1 line

As you know, however, f2fs breaks extent itself due to COW.

Yes, and sometimes f2fs use IPU when override writing, in this condition, by using this approach we can cache more contiguous mapping extent for better performance.

Hmm. When f2fs faces with this case, there is no chance to make an extent itself at all.

Quoted 16 lines

Quoted 5 lines

Unlike other filesystem like btrfs, minimum extent of f2fs could have 4KB granularity. So we would have lots of extents per inode and it could lead to overhead to manage extents.

Agree, the more number of extents are growing in one inode, the more memory pressure and longer latency operating in rb-tree we are facing.
IMO, to solve this problem, we'd better to add limitation or shrink ability into extent cache:
1.limit extent number per inode with the value set from sysfs and discard extent from inode's extent lru list if we touch the limitation; (e.g. in FAT, max number of mapping extent per inode is fixed: 8)
2.add all extents of inodes into a global lru list, we will try to shrink this list if we're facing memory pressure.

Quoted 1 line

How do you think? or any better ideas are welcome. :)

Historically, the reason that I added only one small extent cache is that I wanted to avoid additional data structures having any overhead in critical data write path.

Instead, I intended to use a well operating node page cache.

We need to consider what would be the benefit when using extent cache rather than existing node page cache.

Thanks,

Quoted 37 lines

Quoted 3 lines

Anyway, mount option could be alternative for this patch.

Yes, will do.

Thanks,
Yu

Quoted 28 lines · Chao Yu

Quoted 26 lines

Now f2fs have page-block mapping cache which can cache only one extent mapping between contiguous logical address and physical address. Normally, this design will work well because f2fs will expand coverage area of the mapping extent when we write forward sequentially. But when we write data randomly in Out-Place-Update mode, the extent will be shorten and hardly be expanded for most time as following reasons:
1.The short part of extent will be discarded if we break contiguous mapping in the middle of extent.
2.The new mapping will be added into mapping cache only at head or tail of the extent.
3.We will drop the extent cache when the extent became very fragmented. 4.We will not update the extent with mapping which we get from readpages or readpage.

To solve above problems, this patch adds extent cache base on rb-tree like other filesystems (e.g.: ext4/btrfs) in f2fs. By this way, f2fs can support another more effective cache between dnode page cache and disk. It will supply high hit ratio in the cache with fewer memory when dnode page cache are reclaimed in environment of low memory.

Todo:
*introduce mount option for extent cache.
*add shrink ability for extent cache.

Signed-off-by Chao Yu <[email protected]>

---

Hi Jaegeuk,

Quoted 27 lines

-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
Sent: Tuesday, December 23, 2014 7:16 AM
To: Chao Yu
Cc: 'Changman Lee'; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi Chao,

Quoted 17 lines · Chao Yu

Hi Changman,

Quoted 10 lines

-----Original Message-----
From: Changman Lee [mailto:[email protected]]
Sent: Monday, December 22, 2014 10:03 AM
To: Chao Yu
Cc: Jaegeuk Kim; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi Yu,

Good approach.

Thank you. :)

Quoted 1 line

As you know, however, f2fs breaks extent itself due to COW.

Quoted 6 lines

Quoted 3 lines

Yes, and sometimes f2fs use IPU when override writing, in this condition, by using this approach we can cache more contiguous mapping extent for better performance.

Hmm. When f2fs faces with this case, there is no chance to make an extent itself at all.

With new implementation of this patch f2fs will build extent cache when readpage/readpages.

Quoted 17 lines

Quoted 17 lines

Quoted 6 lines

Unlike other filesystem like btrfs, minimum extent of f2fs could have 4KB granularity. So we would have lots of extents per inode and it could lead to overhead to manage extents.

Agree, the more number of extents are growing in one inode, the more memory pressure and longer latency operating in rb-tree we are facing.
IMO, to solve this problem, we'd better to add limitation or shrink ability into extent cache:
1.limit extent number per inode with the value set from sysfs and discard extent from inode's extent lru list if we touch the limitation; (e.g. in FAT, max number of mapping extent per inode is fixed: 8)
2.add all extents of inodes into a global lru list, we will try to shrink this list if we're facing memory pressure.

Quoted 5 lines

Quoted 1 line

How do you think? or any better ideas are welcome. :)

Historically, the reason that I added only one small extent cache is that I wanted to avoid additional data structures having any overhead in critical data write path.

Thank you for telling me the history of original extent cache.

Quoted 2 lines

Instead, I intended to use a well operating node page cache.

Quoted 2 lines

We need to consider what would be the benefit when using extent cache rather than existing node page cache.

IMO, node page cache belongs to system level cache, filesystem sub system can not control it completely, cached uptodate node page will be invalidated by using drop_caches from sysfs, or reclaimer of mm, result in more IO when we need these node page next time.

New extent cache belongs to filesystem level cache, it is completely controlled by filesystem itself. What we can profit is: on the one hand, it is used as first level cache above the node page cache, which can also increase the cache hit ratio.

On the other hand, it is more instable and controllable than node page cache.

Thanks,
Yu

Quoted 40 lines

Thanks,

Quoted 37 lines

Quoted 3 lines

Anyway, mount option could be alternative for this patch.

Yes, will do.

Thanks,
Yu

Quoted 28 lines · Chao Yu

Quoted 26 lines

Now f2fs have page-block mapping cache which can cache only one extent mapping between contiguous logical address and physical address. Normally, this design will work well because f2fs will expand coverage area of the mapping extent when we write forward sequentially. But when we write data randomly in Out-Place-Update mode, the extent will be shorten and hardly be expanded for most time as following reasons:
1.The short part of extent will be discarded if we break contiguous mapping in the middle of extent.
2.The new mapping will be added into mapping cache only at head or tail of the extent.
3.We will drop the extent cache when the extent became very fragmented. 4.We will not update the extent with mapping which we get from readpages or readpage.

To solve above problems, this patch adds extent cache base on rb-tree like other filesystems (e.g.: ext4/btrfs) in f2fs. By this way, f2fs can support another more effective cache between dnode page cache and disk. It will supply high hit ratio in the cache with fewer memory when dnode page cache are reclaimed in environment of low memory.

Todo:
*introduce mount option for extent cache.
*add shrink ability for extent cache.

Signed-off-by Chao Yu <[email protected]>

---

Hi Chao,

Quoted 29 lines · Chao Yu

Hi Jaegeuk,

Quoted 27 lines

-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
Sent: Tuesday, December 23, 2014 7:16 AM
To: Chao Yu
Cc: 'Changman Lee'; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi Chao,

Quoted 17 lines · Chao Yu

Hi Changman,

Quoted 10 lines

-----Original Message-----
From: Changman Lee [mailto:[email protected]]
Sent: Monday, December 22, 2014 10:03 AM
To: Chao Yu
Cc: Jaegeuk Kim; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi Yu,

Good approach.

Thank you. :)

Quoted 1 line

As you know, however, f2fs breaks extent itself due to COW.

Quoted 8 lines

Quoted 6 lines

Quoted 3 lines

Yes, and sometimes f2fs use IPU when override writing, in this condition, by using this approach we can cache more contiguous mapping extent for better performance.

Hmm. When f2fs faces with this case, there is no chance to make an extent itself at all.

With new implementation of this patch f2fs will build extent cache when readpage/readpages.

I don't understand your points exactly. :(
If there are no on-disk extents, it doesn't matter when the caches are built. Could you define what scenarios you're looking at?

Quoted 27 lines

Quoted 17 lines

Quoted 17 lines

Quoted 6 lines

Unlike other filesystem like btrfs, minimum extent of f2fs could have 4KB granularity. So we would have lots of extents per inode and it could lead to overhead to manage extents.

Agree, the more number of extents are growing in one inode, the more memory pressure and longer latency operating in rb-tree we are facing.
IMO, to solve this problem, we'd better to add limitation or shrink ability into extent cache:
1.limit extent number per inode with the value set from sysfs and discard extent from inode's extent lru list if we touch the limitation; (e.g. in FAT, max number of mapping extent per inode is fixed: 8)
2.add all extents of inodes into a global lru list, we will try to shrink this list if we're facing memory pressure.

Quoted 5 lines

Quoted 1 line

How do you think? or any better ideas are welcome. :)

Historically, the reason that I added only one small extent cache is that I wanted to avoid additional data structures having any overhead in critical data write path.

Thank you for telling me the history of original extent cache.

Quoted 2 lines

Instead, I intended to use a well operating node page cache.

Quoted 7 lines

Quoted 2 lines

We need to consider what would be the benefit when using extent cache rather than existing node page cache.

IMO, node page cache belongs to system level cache, filesystem sub system can not control it completely, cached uptodate node page will be invalidated by using drop_caches from sysfs, or reclaimer of mm, result in more IO when we need these node page next time.

Yes, that's exactly what I wanted.

Quoted 4 lines

New extent cache belongs to filesystem level cache, it is completely controlled by filesystem itself. What we can profit is: on the one hand, it is used as first level cache above the node page cache, which can also increase the cache hit ratio.

I don't think so. The hit ratio depends on the cache policy. The node page cache is managed globally by kernel in LRU manner, so I think this can show affordable hit ratio.

Quoted 2 lines

On the other hand, it is more instable and controllable than node page cache.

It depends on how you can control the extent cache. But, I'm not sure that would be better than page cache managed by MM.

So, my concerns are:

1. Redundant memory overhead
: The extent cache is likely on top of the node page cache, which will consume memory redundantly.

2. CPU overhead
: In every block address updates, it needs to traverse extent cache entries.

3. Effectiveness
: We have a node page cache that is managed by MM in LRU order. I think this provides good hit ratio, system-wide memory relciaming algorithms, and well- defined locking mechanism.

4. Cache reclaiming policy
a. global approach: it needs to consider lock contention, CPU overhead, and
shrinker. I don't think it is better than page cache.
b. local approach: there still exists cold misses at the initial read
operations. After then, how does the extent cache increase hit ratio more than giving node page cache?

For example, in the case of pretty normal scenario like open -> read -> close -> open -> read ..., we can't get benefits form locally-managed extent cache, while node page cache serves many block addresses.

This is my initial thought on the extent cache. Definitely, it is worth to discuss further in more details.

Thanks,

Quoted 44 lines

Thanks,
Yu

Quoted 40 lines

Thanks,

Quoted 37 lines

Quoted 3 lines

Anyway, mount option could be alternative for this patch.

Yes, will do.

Thanks,
Yu

Quoted 28 lines · Chao Yu

Quoted 26 lines

Now f2fs have page-block mapping cache which can cache only one extent mapping between contiguous logical address and physical address. Normally, this design will work well because f2fs will expand coverage area of the mapping extent when we write forward sequentially. But when we write data randomly in Out-Place-Update mode, the extent will be shorten and hardly be expanded for most time as following reasons:
1.The short part of extent will be discarded if we break contiguous mapping in the middle of extent.
2.The new mapping will be added into mapping cache only at head or tail of the extent.
3.We will drop the extent cache when the extent became very fragmented. 4.We will not update the extent with mapping which we get from readpages or readpage.

To solve above problems, this patch adds extent cache base on rb-tree like other filesystems (e.g.: ext4/btrfs) in f2fs. By this way, f2fs can support another more effective cache between dnode page cache and disk. It will supply high hit ratio in the cache with fewer memory when dnode page cache are reclaimed in environment of low memory.

Todo:
*introduce mount option for extent cache.
*add shrink ability for extent cache.

Signed-off-by Chao Yu <[email protected]>

---

-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
Sent: Tuesday, December 23, 2014 3:36 PM
To: Chao Yu
Cc: 'Changman Lee'; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi Chao,

Quoted 33 lines · Chao Yu

Hi Jaegeuk,

Quoted 31 lines

-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
Sent: Tuesday, December 23, 2014 7:16 AM
To: Chao Yu
Cc: 'Changman Lee'; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi Chao,

Quoted 20 lines · Chao Yu

Hi Changman,

Quoted 10 lines

-----Original Message-----
From: Changman Lee [mailto:[email protected]]
Sent: Monday, December 22, 2014 10:03 AM
To: Chao Yu
Cc: Jaegeuk Kim; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi Yu,

Good approach.

Thank you. :)

Quoted 1 line

As you know, however, f2fs breaks extent itself due to COW.

Yes, and sometimes f2fs use IPU when override writing, in this condition, by using this approach we can cache more contiguous mapping extent for better performance.

Quoted 4 lines

Quoted 2 lines

Hmm. When f2fs faces with this case, there is no chance to make an extent itself at all.

With new implementation of this patch f2fs will build extent cache when readpage/readpages.

I don't understand your points exactly. :(
If there are no on-disk extents, it doesn't matter when the caches are built. Could you define what scenarios you're looking at?

Quoted 31 lines

Quoted 18 lines

Quoted 18 lines

Quoted 7 lines

Unlike other filesystem like btrfs, minimum extent of f2fs could have 4KB granularity. So we would have lots of extents per inode and it could lead to overhead to manage extents.

Agree, the more number of extents are growing in one inode, the more memory pressure and longer latency operating in rb-tree we are facing.
IMO, to solve this problem, we'd better to add limitation or shrink ability into extent cache:
1.limit extent number per inode with the value set from sysfs and discard extent from inode's extent lru list if we touch the limitation; (e.g. in FAT, max number of mapping extent per inode is fixed: 8)
2.add all extents of inodes into a global lru list, we will try to shrink this list if we're facing memory pressure.

Quoted 5 lines

Quoted 1 line

How do you think? or any better ideas are welcome. :)

Historically, the reason that I added only one small extent cache is that I wanted to avoid additional data structures having any overhead in critical data write path.

Thank you for telling me the history of original extent cache.

Quoted 4 lines

Instead, I intended to use a well operating node page cache.

We need to consider what would be the benefit when using extent cache rather than existing node page cache.

Quoted 4 lines

IMO, node page cache belongs to system level cache, filesystem sub system can not control it completely, cached uptodate node page will be invalidated by using drop_caches from sysfs, or reclaimer of mm, result in more IO when we need these node page next time.

Yes, that's exactly what I wanted.

Quoted 5 lines

New extent cache belongs to filesystem level cache, it is completely controlled by filesystem itself. What we can profit is: on the one hand, it is used as first level cache above the node page cache, which can also increase the cache hit ratio.

I don't think so. The hit ratio depends on the cache policy. The node page cache is managed globally by kernel in LRU manner, so I think this can show affordable hit ratio.

Quoted 3 lines

On the other hand, it is more instable and controllable than node page cache.

It depends on how you can control the extent cache. But, I'm not sure that would be better than page cache managed by MM.

So, my concerns are:

1. Redundant memory overhead
: The extent cache is likely on top of the node page cache, which will consume memory redundantly.

2. CPU overhead
: In every block address updates, it needs to traverse extent cache entries.

3. Effectiveness
: We have a node page cache that is managed by MM in LRU order. I think this provides good hit ratio, system-wide memory relciaming algorithms, and well- defined locking mechanism.

4. Cache reclaiming policy
a. global approach: it needs to consider lock contention, CPU overhead, and
shrinker. I don't think it is better than page cache.
b. local approach: there still exists cold misses at the initial read
operations. After then, how does the extent cache increase hit ratio more than giving node page cache?

For example, in the case of pretty normal scenario like open -> read -> close -> open -> read ..., we can't get benefits form locally-managed extent cache, while node page cache serves many block addresses.

This is my initial thought on the extent cache. Definitely, it is worth to discuss further in more details.

Thanks,

Quoted 44 lines

Thanks,
Yu

Quoted 40 lines

Thanks,

Quoted 37 lines

Quoted 3 lines

Anyway, mount option could be alternative for this patch.

Yes, will do.

Thanks,
Yu

Quoted 28 lines · Chao Yu

Quoted 26 lines

Now f2fs have page-block mapping cache which can cache only one extent mapping between contiguous logical address and physical address. Normally, this design will work well because f2fs will expand coverage area of the mapping extent when we write forward sequentially. But when we write data randomly in Out-Place-Update mode, the extent will be shorten and hardly be expanded for most time as following reasons:
1.The short part of extent will be discarded if we break contiguous mapping in the middle of extent.
2.The new mapping will be added into mapping cache only at head or tail of the extent.
3.We will drop the extent cache when the extent became very fragmented. 4.We will not update the extent with mapping which we get from readpages or readpage.

To solve above problems, this patch adds extent cache base on rb-tree like other filesystems (e.g.: ext4/btrfs) in f2fs. By this way, f2fs can support another more effective cache between dnode page cache and disk. It will supply high hit ratio in the cache with fewer memory when dnode page cache are reclaimed in environment of low memory.

Todo:
*introduce mount option for extent cache.
*add shrink ability for extent cache.

Signed-off-by Chao Yu <[email protected]>

---

Hi Jaegeuk,

Quoted 43 lines

-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
Sent: Tuesday, December 23, 2014 3:36 PM
To: Chao Yu
Cc: 'Changman Lee'; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi Chao,

Quoted 33 lines · Chao Yu

Hi Jaegeuk,

Quoted 31 lines

-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
Sent: Tuesday, December 23, 2014 7:16 AM
To: Chao Yu
Cc: 'Changman Lee'; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi Chao,

Quoted 20 lines · Chao Yu

Hi Changman,

Quoted 10 lines

-----Original Message-----
From: Changman Lee [mailto:[email protected]]
Sent: Monday, December 22, 2014 10:03 AM
To: Chao Yu
Cc: Jaegeuk Kim; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi Yu,

Good approach.

Thank you. :)

Quoted 1 line

As you know, however, f2fs breaks extent itself due to COW.

Yes, and sometimes f2fs use IPU when override writing, in this condition, by using this approach we can cache more contiguous mapping extent for better performance.

Quoted 8 lines

Quoted 4 lines

Quoted 2 lines

Hmm. When f2fs faces with this case, there is no chance to make an extent itself at all.

With new implementation of this patch f2fs will build extent cache when readpage/readpages.

I don't understand your points exactly. :(
If there are no on-disk extents, it doesn't matter when the caches are built. Could you define what scenarios you're looking at?

What I mean is that IPU will not split the exist extent in extent cache; and this exist extent cache was been built when we init cache with last accessed extent (the only on-disk extent) which was stored in inode, or be built when we invoke get_data_block in readpage/readpages in IPU mode. So there is a chance to make extent in this scenario.

Quoted 6 lines

Quoted 4 lines

IMO, node page cache belongs to system level cache, filesystem sub system can not control it completely, cached uptodate node page will be invalidated by using drop_caches from sysfs, or reclaimer of mm, result in more IO when we need these node page next time.

Yes, that's exactly what I wanted.

IMO, cost is expensive when we read node page again if these pages are invalidated by MM. In the worst case, we will read 3 ind-node blocks + 1 dnode block + 3 NAT blocks from disk for one blkaddr.

Quoted 10 lines

Quoted 6 lines

New extent cache belongs to filesystem level cache, it is completely controlled by filesystem itself. What we can profit is: on the one hand, it is used as first level cache above the node page cache, which can also increase the cache hit ratio.

I don't think so. The hit ratio depends on the cache policy. The node page cache is managed globally by kernel in LRU manner, so I think this can show affordable hit ratio.

As I test, in this scenario we can have higher ratio hit in new extent cache than original extent cache:
1.write a large file
2.write randomly in this file
3.drop cache through drop_caches entry (or reclaim by MM)
4.read this large file

We cache all segregated extents in inode, so our ratio hit is 100% in above scenario. If we add cache policy in extent cache, our hit ratio will drop. But added policy can provide us more choose for different hit ratio (may affect IO count) requirement of users.

Quoted 8 lines

Quoted 4 lines

On the other hand, it is more instable and controllable than node page cache.

It depends on how you can control the extent cache. But, I'm not sure that would be better than page cache managed by MM.

Quoted 8 lines

So, my concerns are:

1. Redundant memory overhead
: The extent cache is likely on top of the node page cache, which will consume memory redundantly.

2. CPU overhead
: In every block address updates, it needs to traverse extent cache entries.

As I mentioned above, if extent cache has the ability of limitation and shrink, overhead of memory and CPU can be controlled.

Quoted 5 lines

3. Effectiveness
: We have a node page cache that is managed by MM in LRU order. I think this provides good hit ratio, system-wide memory relciaming algorithms, and well- defined locking mechanism.

The effectiveness of new extent cache is the key point we should discuss.

IMO, hit ratio of extent cache and memory/CPU cost can be tradeoff. For example:
1.if limitation is on, max value is 1; shrink is off:
our extent cache will be the same as original extent cache.
2.if limitation is off, shrink is off:
our extent cache can provide high hit ratio when node page cache is invalid but there is more memory/CPU overhead.
3.there are more status between label 1 and label 2 as limitation and shrink is set to different value.
So we just develop our extent cache for more functionality and selective.

Another point is that, now size of struct extent_info is 24 bytes which is much smaller than 4096 of node page size (ind-node page size is not calced), it's cost-efficient to use small memory to store contiguous mapping. (This is pointed out by Changman also)

Quoted 8 lines

4. Cache reclaiming policy
a. global approach: it needs to consider lock contention, CPU overhead, and
shrinker. I don't think it is better than page cache.
b. local approach: there still exists cold misses at the initial read
operations. After then, how does the extent cache increase hit ratio more than giving node page cache?

Quoted 4 lines

For example, in the case of pretty normal scenario like open -> read -> close -> open -> read ..., we can't get benefits form locally-managed extent cache, while node page cache serves many block addresses.

If this case should be covered, how about remembering these recently accessed extent in a global list when evict, recovering extent cache from list when re-open?

Thanks,
Yu

Quoted 50 lines

This is my initial thought on the extent cache. Definitely, it is worth to discuss further in more details.

Thanks,

Quoted 44 lines

Thanks,
Yu

Quoted 40 lines

Thanks,

Quoted 37 lines

Quoted 3 lines

Anyway, mount option could be alternative for this patch.

Yes, will do.

Thanks,
Yu

Quoted 28 lines · Chao Yu

Quoted 26 lines

Now f2fs have page-block mapping cache which can cache only one extent mapping between contiguous logical address and physical address. Normally, this design will work well because f2fs will expand coverage area of the mapping extent when we write forward sequentially. But when we write data randomly in Out-Place-Update mode, the extent will be shorten and hardly be expanded for most time as following reasons:
1.The short part of extent will be discarded if we break contiguous mapping in the middle of extent.
2.The new mapping will be added into mapping cache only at head or tail of the extent.
3.We will drop the extent cache when the extent became very fragmented. 4.We will not update the extent with mapping which we get from readpages or readpage.

To solve above problems, this patch adds extent cache base on rb-tree like other filesystems (e.g.: ext4/btrfs) in f2fs. By this way, f2fs can support another more effective cache between dnode page cache and disk. It will supply high hit ratio in the cache with fewer memory when dnode page cache are reclaimed in environment of low memory.

Todo:
*introduce mount option for extent cache.
*add shrink ability for extent cache.

Signed-off-by Chao Yu <[email protected]>

---

-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
Sent: Thursday, December 25, 2014 4:35 PM
To: Chao Yu
Cc: 'Changman Lee'; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi Chao,

Quoted 19 lines · Chao Yu

Hi Jaegeuk,

Quoted 17 lines

-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
Sent: Tuesday, December 23, 2014 3:36 PM
To: Chao Yu
Cc: 'Changman Lee'; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi Chao,

Quoted 7 lines · Chao Yu

Hi Jaegeuk,

Quoted 5 lines

-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
Sent: Tuesday, December 23, 2014 7:16 AM
To: Chao Yu
Cc: 'Changman Lee'; [email protected];

[email protected]

Quoted 4 lines

Quoted 4 lines

Quoted 4 lines

Quoted 4 lines

Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi Chao,

Quoted 8 lines

Quoted 8 lines

Quoted 8 lines

Quoted 8 lines · Chao Yu

Quoted 7 lines

Hi Changman,

Quoted 5 lines

-----Original Message-----
From: Changman Lee [mailto:[email protected]]
Sent: Monday, December 22, 2014 10:03 AM
To: Chao Yu
Cc: Jaegeuk Kim; [email protected];

[email protected]

Quoted 23 lines

Quoted 14 lines

Quoted 14 lines

Quoted 14 lines

Quoted 13 lines

Quoted 5 lines

Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi Yu,

Good approach.

Thank you. :)

Quoted 1 line

As you know, however, f2fs breaks extent itself due to COW.

Yes, and sometimes f2fs use IPU when override writing, in this condition, by using this approach we can cache more contiguous mapping extent for better performance.

Quoted 8 lines

Quoted 4 lines

Quoted 2 lines

Hmm. When f2fs faces with this case, there is no chance to make an extent itself at all.

With new implementation of this patch f2fs will build extent cache when readpage/readpages.

I don't understand your points exactly. :(
If there are no on-disk extents, it doesn't matter when the caches are built. Could you define what scenarios you're looking at?

Quoted 5 lines

What I mean is that IPU will not split the exist extent in extent cache; and this exist extent cache was been built when we init cache with last accessed extent (the only on-disk extent) which was stored in inode, or be built when we invoke get_data_block in readpage/readpages in IPU mode. So there is a chance to make extent in this scenario.

As long as I can understand your point, IPU can mitigate data fragmentation, resulting in more extents, but current IPU policies except FORCE are activated only when partition was already fragmented a lot such as high utilization or SSR modes. That's why I said IPU is actually not helping extent caches.

[snip]

Quoted 7 lines

Quoted 6 lines

Quoted 4 lines

IMO, node page cache belongs to system level cache, filesystem sub system can not control it completely, cached uptodate node page will be invalidated by using drop_caches from sysfs, or reclaimer of mm, result in more IO when we need these node page next time.

Yes, that's exactly what I wanted.

Quoted 3 lines

IMO, cost is expensive when we read node page again if these pages are invalidated by MM. In the worst case, we will read 3 ind-node blocks + 1 dnode block + 3 NAT blocks from disk for one blkaddr.

My point is who should control this sort of caches.
At least, we should focus on the hit ratio, not the worst case comparison. In the worst case, extent cache has more overhead than node page cache alone.

Quoted 19 lines

Quoted 11 lines

Quoted 7 lines

New extent cache belongs to filesystem level cache, it is completely controlled by filesystem itself. What we can profit is: on the one hand, it is used as first level cache above the node page cache, which can also increase the cache hit ratio.

I don't think so. The hit ratio depends on the cache policy. The node page cache is managed globally by kernel in LRU manner, so I think this can show affordable hit ratio.

As I test, in this scenario we can have higher ratio hit in new extent cache than original extent cache:
1.write a large file
2.write randomly in this file
3.drop cache through drop_caches entry (or reclaim by MM)
4.read this large file

Quoted 4 lines

We cache all segregated extents in inode, so our ratio hit is 100% in above scenario. If we add cache policy in extent cache, our hit ratio will drop. But added policy can provide us more choose for different hit ratio (may affect IO count) requirement of users.

Of course! Even though system wants to get more memory, you're trying to grab in-house memory for extents.
Or, new shrinker reclaims some of them, but it will drop hit raio obviously.

Please see below as a summary.

Quoted 52 lines

Quoted 8 lines

Quoted 4 lines

On the other hand, it is more instable and controllable than node page cache.

It depends on how you can control the extent cache. But, I'm not sure that would be better than page cache managed by MM.

Quoted 8 lines

So, my concerns are:

1. Redundant memory overhead
: The extent cache is likely on top of the node page cache, which will consume memory redundantly.

2. CPU overhead
: In every block address updates, it needs to traverse extent cache entries.

As I mentioned above, if extent cache has the ability of limitation and shrink, overhead of memory and CPU can be controlled.

Quoted 5 lines

3. Effectiveness
: We have a node page cache that is managed by MM in LRU order. I think this provides good hit ratio, system-wide memory relciaming algorithms, and well- defined locking mechanism.

The effectiveness of new extent cache is the key point we should discuss.

IMO, hit ratio of extent cache and memory/CPU cost can be tradeoff. For example:
1.if limitation is on, max value is 1; shrink is off:
our extent cache will be the same as original extent cache.
2.if limitation is off, shrink is off:
our extent cache can provide high hit ratio when node page cache is invalid but there is more memory/CPU overhead.
3.there are more status between label 1 and label 2 as limitation and shrink is set to different value.
So we just develop our extent cache for more functionality and selective.

Another point is that, now size of struct extent_info is 24 bytes which is much smaller than 4096 of node page size (ind-node page size is not calced), it's cost-efficient to use small memory to store contiguous mapping. (This is pointed out by Changman also)

Quoted 8 lines

4. Cache reclaiming policy
a. global approach: it needs to consider lock contention, CPU overhead, and
shrinker. I don't think it is better than page cache.
b. local approach: there still exists cold misses at the initial read
operations. After then, how does the extent cache increase hit ratio more than giving node page cache?

Quoted 7 lines

Quoted 4 lines

For example, in the case of pretty normal scenario like open -> read -> close -> open -> read ..., we can't get benefits form locally-managed extent cache, while node page cache serves many block addresses.

If this case should be covered, how about remembering these recently accessed extent in a global list when evict, recovering extent cache from list when re-open?

Oh, surely, this example is from the local approach, not existing in the global one. :)

I guess you've understood my concerns enoughly. So, could you share a detailed design for all these stuffs?

For the design, I think these must be addressed seriously.
1. decide one of global or local management
2. should add a shrinker
3. reduce lock contention and critical region

Please, limit this feature to consume memory as less as possible, since it will increase memory footprint definitely.

Thanks,

Quoted 54 lines

Thanks,
Yu

Quoted 50 lines

This is my initial thought on the extent cache. Definitely, it is worth to discuss further in more details.

Thanks,

Quoted 44 lines

Thanks,
Yu

Quoted 40 lines

Thanks,

Quoted 37 lines

Quoted 3 lines

Anyway, mount option could be alternative for this patch.

Yes, will do.

Thanks,
Yu

Quoted 28 lines · Chao Yu

Quoted 26 lines

Now f2fs have page-block mapping cache which can cache only one extent mapping between contiguous logical address and physical address. Normally, this design will work well because f2fs will expand coverage area of the mapping extent when we write forward sequentially. But when we write data randomly in Out-Place-Update mode, the extent will be shorten and hardly be expanded for most time as following reasons:
1.The short part of extent will be discarded if we break contiguous mapping in the middle of extent.
2.The new mapping will be added into mapping cache only at head or tail of the extent.
3.We will drop the extent cache when the extent became very fragmented. 4.We will not update the extent with mapping which we get from readpages or readpage.

To solve above problems, this patch adds extent cache base on rb-tree like other filesystems (e.g.: ext4/btrfs) in f2fs. By this way, f2fs can support another more effective cache between dnode page cache and disk. It will supply high hit ratio in the cache with fewer memory when dnode page cache are reclaimed in environment of low memory.

Todo:
*introduce mount option for extent cache.
*add shrink ability for extent cache.

Signed-off-by Chao Yu <[email protected]>

---

Please see the draft below.

1) Extent management:
If we use global management that managing all extents which are from different inodes in sbi, we will face with serious lock contention when we access these extents belong to different inodes concurrently, the loss may outweights the gain.

So we choose a local management for extent which means all extents are managed by inode itself to avoid above lock contention. Addtionlly, we manage all extents globally by linking all inode into a global lru list for extent cache shrinker.
Approach:
a) build extent tree/rwlock/lru list/extent count in each inode.

*extent tree: link all extent in rb-tree;
*rwlock: protect fields when accessing extent cache concurrently; *lru list: sort all extents in accessing time order; *extent count: record total count of extents in cache.
b) use lru shrink list in sbi to manage all inode which cached extents. *inode will be added or repostioned in this global list whenever extent is being access in this inode.
*use spinlock to protect this shrink list.

2) Limitation:
In one inode, as we split or add extent in extent cache when read/write, extent number will enlarge, so memory and CPU overhead will increase.
In order to control the overhead of memory and CPU, we try to set a upper bound number to limit total extent number in each inode, This number is global configuration which is visable to all inode. This number will be exported to sysfs for configuring according to requirement of user. By default, designed number is 8.

3) Shrinker:
There are two shrink paths:
a) one is triggered when extent count has exceed the upper bound of inode's extent cache. We will try to release extent(s) from head of inode's inner extent lru list until extent count is equal to upper bound. This operation could be in f2fs_update_extent_cache().
b) the other one is triggered when memory util exceed threshold, we try get inode from head of global lru list(s), and release extent(s) with fixed number (by default: 64 extents) in inode one by one. This operation could be in f2fs_balance_fs_bg().

4) Revalidation:
In ->evict(), extent cache will be released, in order to reuse extent cache of inode when reopen for high hit ratio, a proper way is to add cached extent tree into a hash table (could be radix tree), revalidate extent tree and recover it to inode when reopen.
Besides, a global lru list is needed here for shrinker.

5) Readahead:
Expand extent cache by readaheading when we call get_dnode_of_data in non-emergency path. Note, ra can affect lock contention for both ->rwlock in extent cache and ->lock of global shrink list.

Hi Chao,

On Mon, Dec 29, 2014 at 03:19:18PM +0800, Chao Yu wrote:

[snip]

Nice draft. :)

Quoted 8 lines

Please see the draft below.

1) Extent management:
If we use global management that managing all extents which are from different inodes in sbi, we will face with serious lock contention when we access these extents belong to different inodes concurrently, the loss may outweights the gain.

Agreed.

Quoted 6 lines

So we choose a local management for extent which means all extents are managed by inode itself to avoid above lock contention. Addtionlly, we manage all extents globally by linking all inode into a global lru list for extent cache shrinker.
Approach:
a) build extent tree/rwlock/lru list/extent count in each inode.

Quoted 8 lines

*extent tree: link all extent in rb-tree;
*rwlock: protect fields when accessing extent cache concurrently; *lru list: sort all extents in accessing time order; *extent count: record total count of extents in cache.
b) use lru shrink list in sbi to manage all inode which cached extents. *inode will be added or repostioned in this global list whenever extent is being access in this inode.
*use spinlock to protect this shrink list.

1. How about adding a data structure with inode number instead of referring inode pointer?

2. How about managing extent entries globally and setting an upper bound to the number of extent entries instead of limiting them per each inode? (The rb-tree will handle many extents per inode.)

3. It needs to set a minimum length for the candidate of extent cache. (e.g., 64)

So, for example,

struct ino_entry_for_extents {
	inode number;
	rb_tree for extent_entry objects;
	rwlock;
};

struct extent_entry {
	blkaddr, len;
	list_head *;
};

Something like this.

[A, B, C, ... are extent entry]

The sbi has
1. an extent_list: (LRU) A -> B -> C -> D -> E -> F -> G (MRU)
2. radix_tree: ino_entry_for_extents (#10) has D, B in rb-tree ` ino_entry_for_extents (#11) has A, C in rb-tree
` ino_entry_for_extents (#12) has F in rb-tree
` ino_entry_for_extents (#13) has G, E in rb-tree

In f2fs_update_extent_cache and __get_data_block for #10,
ino_entry_for_extents (#10) was founded and updated D or B. Then, updated entries are moved to MRU.

In f2fs_evict_inode for #11, A and C are moved to LRU.
But, if this inode is unlinked, all the A, C, and ino_entry_for_extens (#11) should be released.

In f2fs_balance_fs_bg, some LRU extents are released according to the amount of consumed memory. Then, it frees any ino_entry_for_extents having no extent.

IMO, we don't need to consider readahead for this, since get_data_block will be called by VFS readahead.

Furthermore, we need to think about whether LRU is really best or not. IMO, the extent cache aims to improve second access speed, rather than initial cold misses. So, maybe MRU or another algorithms would be better.

Thanks,

Quoted 10 lines

2) Limitation:
In one inode, as we split or add extent in extent cache when read/write, extent number will enlarge, so memory and CPU overhead will increase.
In order to control the overhead of memory and CPU, we try to set a upper bound number to limit total extent number in each inode, This number is global configuration which is visable to all inode. This number will be exported to sysfs for configuring according to requirement of user. By default, designed number is 8.

Quoted 11 lines

3) Shrinker:
There are two shrink paths:
a) one is triggered when extent count has exceed the upper bound of inode's extent cache. We will try to release extent(s) from head of inode's inner extent lru list until extent count is equal to upper bound. This operation could be in f2fs_update_extent_cache().
b) the other one is triggered when memory util exceed threshold, we try get inode from head of global lru list(s), and release extent(s) with fixed number (by default: 64 extents) in inode one by one. This operation could be in f2fs_balance_fs_bg().

Quoted 12 lines

4) Revalidation:
In ->evict(), extent cache will be released, in order to reuse extent cache of inode when reopen for high hit ratio, a proper way is to add cached extent tree into a hash table (could be radix tree), revalidate extent tree and recover it to inode when reopen.
Besides, a global lru list is needed here for shrinker.

5) Readahead:
Expand extent cache by readaheading when we call get_dnode_of_data in non-emergency path. Note, ra can affect lock contention for both ->rwlock in extent cache and ->lock of global shrink list.

-----Original Message-----
From: Changman Lee [mailto:[email protected]]
Sent: Tuesday, December 30, 2014 8:32 AM
To: Jaegeuk Kim
Cc: Chao Yu; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi all,

Quoted 37 lines · Jaegeuk Kim

Hi Chao,

On Mon, Dec 29, 2014 at 03:19:18PM +0800, Chao Yu wrote:

[snip]

Nice draft. :)

Quoted 8 lines

Please see the draft below.

1) Extent management:
If we use global management that managing all extents which are from different inodes in sbi, we will face with serious lock contention when we access these extents belong to different inodes concurrently, the loss may outweights the gain.

Agreed.

Quoted 6 lines

So we choose a local management for extent which means all extents are managed by inode itself to avoid above lock contention. Addtionlly, we manage all extents globally by linking all inode into a global lru list for extent cache shrinker.
Approach:
a) build extent tree/rwlock/lru list/extent count in each inode.

Quoted 8 lines

*extent tree: link all extent in rb-tree;
*rwlock: protect fields when accessing extent cache concurrently; *lru list: sort all extents in accessing time order; *extent count: record total count of extents in cache.
b) use lru shrink list in sbi to manage all inode which cached extents. *inode will be added or repostioned in this global list whenever extent is being access in this inode.
*use spinlock to protect this shrink list.

1. How about adding a data structure with inode number instead of referring inode pointer?

Quoted 7 lines

2. How about managing extent entries globally and setting an upper bound to the number of extent entries instead of limiting them per each inode? (The rb-tree will handle many extents per inode.)

3. It needs to set a minimum length for the candidate of extent cache. (e.g., 64)

Agreed.

Quoted 34 lines

So, for example,

struct ino_entry_for_extents {
	inode number;
	rb_tree for extent_entry objects;
	rwlock;
};

struct extent_entry {
	blkaddr, len;
	list_head *;
};

Something like this.

[A, B, C, ... are extent entry]

The sbi has
1. an extent_list: (LRU) A -> B -> C -> D -> E -> F -> G (MRU)
2. radix_tree: ino_entry_for_extents (#10) has D, B in rb-tree ` ino_entry_for_extents (#11) has A, C in rb-tree
` ino_entry_for_extents (#12) has F in rb-tree
` ino_entry_for_extents (#13) has G, E in rb-tree

In f2fs_update_extent_cache and __get_data_block for #10,
ino_entry_for_extents (#10) was founded and updated D or B. Then, updated entries are moved to MRU.

In f2fs_evict_inode for #11, A and C are moved to LRU.
But, if this inode is unlinked, all the A, C, and ino_entry_for_extens (#11) should be released.

In f2fs_balance_fs_bg, some LRU extents are released according to the amount of consumed memory. Then, it frees any ino_entry_for_extents having no extent.

Quoted 7 lines

IMO, we don't need to consider readahead for this, since get_data_block will be called by VFS readahead.

Furthermore, we need to think about whether LRU is really best or not. IMO, the extent cache aims to improve second access speed, rather than initial cold misses. So, maybe MRU or another algorithms would be better.

Right. It's very comflicated to judge which is better.
In read or write path, extents could be made every time. At that time, we should decide which extent evicts instead of new extents if we set upper bound.
In update, one extent could be seperated into 3. It requires 3 insertion and 1 deletion. So if update happends frequently, we could give up extent management for some ranges. And we need to bring ideas from vm managemnt. For example,
active/inactive list and second chance to promotion, or batch work for insertion/deletion

I thought suddenly 'Simple is best'.
Let's think about better ideas together.

Quoted 13 lines

Thanks,

Quoted 10 lines

2) Limitation:
In one inode, as we split or add extent in extent cache when read/write, extent number will enlarge, so memory and CPU overhead will increase.
In order to control the overhead of memory and CPU, we try to set a upper bound number to limit total extent number in each inode, This number is global configuration which is visable to all inode. This number will be exported to sysfs for configuring according to requirement of user. By default, designed number is 8.

Chao,
It's better which # of extent are controlled globally rather than limit extents per inode as Jaegeuk said to reduce extent management overhead.

Quoted 12 lines

Quoted 12 lines

3) Shrinker:
There are two shrink paths:
a) one is triggered when extent count has exceed the upper bound of inode's extent cache. We will try to release extent(s) from head of inode's inner extent lru list until extent count is equal to upper bound. This operation could be in f2fs_update_extent_cache().
b) the other one is triggered when memory util exceed threshold, we try get inode from head of global lru list(s), and release extent(s) with fixed number (by default: 64 extents) in inode one by one. This operation could be in f2fs_balance_fs_bg().

Let's consider to use register_shrinker which is called by vm when memory pressure happens.

Quoted 13 lines

Quoted 13 lines

4) Revalidation:
In ->evict(), extent cache will be released, in order to reuse extent cache of inode when reopen for high hit ratio, a proper way is to add cached extent tree into a hash table (could be radix tree), revalidate extent tree and recover it to inode when reopen.
Besides, a global lru list is needed here for shrinker.

5) Readahead:
Expand extent cache by readaheading when we call get_dnode_of_data in non-emergency path. Note, ra can affect lock contention for both ->rwlock in extent cache and ->lock of global shrink list.

Hi Changman,

Sorry for replying late!

Quoted 107 lines

-----Original Message-----
From: Changman Lee [mailto:[email protected]]
Sent: Tuesday, December 30, 2014 8:32 AM
To: Jaegeuk Kim
Cc: Chao Yu; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi all,

Quoted 37 lines · Jaegeuk Kim

Hi Chao,

On Mon, Dec 29, 2014 at 03:19:18PM +0800, Chao Yu wrote:

[snip]

Nice draft. :)

Quoted 8 lines

Please see the draft below.

1) Extent management:
If we use global management that managing all extents which are from different inodes in sbi, we will face with serious lock contention when we access these extents belong to different inodes concurrently, the loss may outweights the gain.

Agreed.

Quoted 6 lines

So we choose a local management for extent which means all extents are managed by inode itself to avoid above lock contention. Addtionlly, we manage all extents globally by linking all inode into a global lru list for extent cache shrinker.
Approach:
a) build extent tree/rwlock/lru list/extent count in each inode.

Quoted 8 lines

*extent tree: link all extent in rb-tree;
*rwlock: protect fields when accessing extent cache concurrently; *lru list: sort all extents in accessing time order; *extent count: record total count of extents in cache.
b) use lru shrink list in sbi to manage all inode which cached extents. *inode will be added or repostioned in this global list whenever extent is being access in this inode.
*use spinlock to protect this shrink list.

1. How about adding a data structure with inode number instead of referring inode pointer?

Quoted 7 lines

2. How about managing extent entries globally and setting an upper bound to the number of extent entries instead of limiting them per each inode? (The rb-tree will handle many extents per inode.)

3. It needs to set a minimum length for the candidate of extent cache. (e.g., 64)

Agreed.

Quoted 34 lines

So, for example,

struct ino_entry_for_extents {
	inode number;
	rb_tree for extent_entry objects;
	rwlock;
};

struct extent_entry {
	blkaddr, len;
	list_head *;
};

Something like this.

[A, B, C, ... are extent entry]

The sbi has
1. an extent_list: (LRU) A -> B -> C -> D -> E -> F -> G (MRU)
2. radix_tree: ino_entry_for_extents (#10) has D, B in rb-tree ` ino_entry_for_extents (#11) has A, C in rb-tree
` ino_entry_for_extents (#12) has F in rb-tree
` ino_entry_for_extents (#13) has G, E in rb-tree

In f2fs_update_extent_cache and __get_data_block for #10,
ino_entry_for_extents (#10) was founded and updated D or B. Then, updated entries are moved to MRU.

In f2fs_evict_inode for #11, A and C are moved to LRU.
But, if this inode is unlinked, all the A, C, and ino_entry_for_extens (#11) should be released.

In f2fs_balance_fs_bg, some LRU extents are released according to the amount of consumed memory. Then, it frees any ino_entry_for_extents having no extent.

Quoted 7 lines

IMO, we don't need to consider readahead for this, since get_data_block will be called by VFS readahead.

Furthermore, we need to think about whether LRU is really best or not. IMO, the extent cache aims to improve second access speed, rather than initial cold misses. So, maybe MRU or another algorithms would be better.

Right. It's very comflicated to judge which is better.
In read or write path, extents could be made every time. At that time, we should decide which extent evicts instead of new extents if we set upper bound.
In update, one extent could be seperated into 3. It requires 3 insertion and 1 deletion. So if update happends frequently, we could give up extent management for some ranges. And we need to bring ideas from vm managemnt. For example,
active/inactive list and second chance to promotion, or batch work for insertion/deletion

Quoted 2 lines

I thought suddenly 'Simple is best'.
Let's think about better ideas together.

Yeah, how about using an opposite way to the way of page cache manager?

for example:
node page A,B,C,D is in page cache;
extent a,b,c,d is in extent cache;
extent a is built from page A, ..., d is built from page D. page cache: LRU A -> B -> C -> D MRU
extent cache: LRU a -> b -> c -> d MRU

If we use
1) the same way LRU, cache pair A-a, B-b, ... may be reclaimed in the same time as OOM.
2) the opposite way, maybe A,B in page cache and d,c in extent cache will be reclaimed, but we still can hit whole cache in combination of page cache and extent cache.

So by the way '2)' we can increase the total coverage area of page cache + extent cache.

Quoted 15 lines

Quoted 14 lines

Thanks,

Quoted 10 lines

2) Limitation:
In one inode, as we split or add extent in extent cache when read/write, extent number will enlarge, so memory and CPU overhead will increase.
In order to control the overhead of memory and CPU, we try to set a upper bound number to limit total extent number in each inode, This number is global configuration which is visable to all inode. This number will be exported to sysfs for configuring according to requirement of user. By default, designed number is 8.

Quoted 3 lines

Chao,
It's better which # of extent are controlled globally rather than limit extents per inode as Jaegeuk said to reduce extent management overhead.

It's OK.

Quoted 13 lines

Quoted 12 lines

Quoted 12 lines

3) Shrinker:
There are two shrink paths:
a) one is triggered when extent count has exceed the upper bound of inode's extent cache. We will try to release extent(s) from head of inode's inner extent lru list until extent count is equal to upper bound. This operation could be in f2fs_update_extent_cache().
b) the other one is triggered when memory util exceed threshold, we try get inode from head of global lru list(s), and release extent(s) with fixed number (by default: 64 extents) in inode one by one. This operation could be in f2fs_balance_fs_bg().

Quoted 2 lines

Let's consider to use register_shrinker which is called by vm when memory pressure happens.

Great, thanks for your reminding! :-)

Thanks,
Yu

Quoted 13 lines

Quoted 13 lines

Quoted 13 lines

4) Revalidation:
In ->evict(), extent cache will be released, in order to reuse extent cache of inode when reopen for high hit ratio, a proper way is to add cached extent tree into a hash table (could be radix tree), revalidate extent tree and recover it to inode when reopen.
Besides, a global lru list is needed here for shrinker.

5) Readahead:
Expand extent cache by readaheading when we call get_dnode_of_data in non-emergency path. Note, ra can affect lock contention for both ->rwlock in extent cache and ->lock of global shrink list.

-----Original Message-----
From: Changman Lee [mailto:[email protected]]
Sent: Wednesday, January 07, 2015 7:17 PM
To: Chao Yu
Cc: 'Jaegeuk Kim'; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi Chao,

Quoted 128 lines · Chao Yu

Hi Changman,

Sorry for replying late!

Quoted 107 lines

-----Original Message-----
From: Changman Lee [mailto:[email protected]]
Sent: Tuesday, December 30, 2014 8:32 AM
To: Jaegeuk Kim
Cc: Chao Yu; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi all,

Quoted 37 lines · Jaegeuk Kim

Hi Chao,

On Mon, Dec 29, 2014 at 03:19:18PM +0800, Chao Yu wrote:

[snip]

Nice draft. :)

Quoted 8 lines

Please see the draft below.

1) Extent management:
If we use global management that managing all extents which are from different inodes in sbi, we will face with serious lock contention when we access these extents belong to different inodes concurrently, the loss may outweights the gain.

Agreed.

Quoted 6 lines

So we choose a local management for extent which means all extents are managed by inode itself to avoid above lock contention. Addtionlly, we manage all extents globally by linking all inode into a global lru list for extent cache shrinker.
Approach:
a) build extent tree/rwlock/lru list/extent count in each inode.

Quoted 8 lines

*extent tree: link all extent in rb-tree;
*rwlock: protect fields when accessing extent cache concurrently; *lru list: sort all extents in accessing time order; *extent count: record total count of extents in cache.
b) use lru shrink list in sbi to manage all inode which cached extents. *inode will be added or repostioned in this global list whenever extent is being access in this inode.
*use spinlock to protect this shrink list.

1. How about adding a data structure with inode number instead of referring inode pointer?

Quoted 7 lines

2. How about managing extent entries globally and setting an upper bound to the number of extent entries instead of limiting them per each inode? (The rb-tree will handle many extents per inode.)

3. It needs to set a minimum length for the candidate of extent cache. (e.g., 64)

Agreed.

Quoted 34 lines

So, for example,

struct ino_entry_for_extents {
	inode number;
	rb_tree for extent_entry objects;
	rwlock;
};

struct extent_entry {
	blkaddr, len;
	list_head *;
};

Something like this.

[A, B, C, ... are extent entry]

The sbi has
1. an extent_list: (LRU) A -> B -> C -> D -> E -> F -> G (MRU)
2. radix_tree: ino_entry_for_extents (#10) has D, B in rb-tree ` ino_entry_for_extents (#11) has A, C in rb-tree
` ino_entry_for_extents (#12) has F in rb-tree
` ino_entry_for_extents (#13) has G, E in rb-tree

In f2fs_update_extent_cache and __get_data_block for #10,
ino_entry_for_extents (#10) was founded and updated D or B. Then, updated entries are moved to MRU.

In f2fs_evict_inode for #11, A and C are moved to LRU.
But, if this inode is unlinked, all the A, C, and ino_entry_for_extens (#11) should be released.

In f2fs_balance_fs_bg, some LRU extents are released according to the amount of consumed memory. Then, it frees any ino_entry_for_extents having no extent.

Quoted 7 lines

IMO, we don't need to consider readahead for this, since get_data_block will be called by VFS readahead.

Furthermore, we need to think about whether LRU is really best or not. IMO, the extent cache aims to improve second access speed, rather than initial cold misses. So, maybe MRU or another algorithms would be better.

Right. It's very comflicated to judge which is better.
In read or write path, extents could be made every time. At that time, we should decide which extent evicts instead of new extents if we set upper bound.
In update, one extent could be seperated into 3. It requires 3 insertion and 1 deletion. So if update happends frequently, we could give up extent management for some ranges. And we need to bring ideas from vm managemnt. For example,
active/inactive list and second chance to promotion, or batch work for insertion/deletion

Quoted 2 lines

I thought suddenly 'Simple is best'.
Let's think about better ideas together.

Yeah, how about using an opposite way to the way of page cache manager?

for example:
node page A,B,C,D is in page cache;
extent a,b,c,d is in extent cache;
extent a is built from page A, ..., d is built from page D. page cache: LRU A -> B -> C -> D MRU
extent cache: LRU a -> b -> c -> d MRU

If we use
1) the same way LRU, cache pair A-a, B-b, ... may be reclaimed in the same time as OOM.
2) the opposite way, maybe A,B in page cache and d,c in extent cache will be reclaimed, but we still can hit whole cache in combination of page cache and extent cache.

Quoted 1 line

So by the way '2)' we can increase the total coverage area of page cache + extent cache.

Good idea. :)
If we decide which one is better between global lru and per inode lru, it's expected that f2fs read performance will be more improved. I'll wait your patch.

Thanks,

Quoted 55 lines

Quoted 15 lines

Quoted 14 lines

Thanks,

Quoted 10 lines

2) Limitation:
In one inode, as we split or add extent in extent cache when read/write, extent number will enlarge, so memory and CPU overhead will increase.
In order to control the overhead of memory and CPU, we try to set a upper bound number to limit total extent number in each inode, This number is global configuration which is visable to all inode. This number will be exported to sysfs for configuring according to requirement of user. By default, designed number is 8.

Quoted 3 lines

Chao,
It's better which # of extent are controlled globally rather than limit extents per inode as Jaegeuk said to reduce extent management overhead.

It's OK.

Quoted 13 lines

Quoted 12 lines

Quoted 12 lines

3) Shrinker:
There are two shrink paths:
a) one is triggered when extent count has exceed the upper bound of inode's extent cache. We will try to release extent(s) from head of inode's inner extent lru list until extent count is equal to upper bound. This operation could be in f2fs_update_extent_cache().
b) the other one is triggered when memory util exceed threshold, we try get inode from head of global lru list(s), and release extent(s) with fixed number (by default: 64 extents) in inode one by one. This operation could be in f2fs_balance_fs_bg().

Quoted 2 lines

Let's consider to use register_shrinker which is called by vm when memory pressure happens.

Great, thanks for your reminding! :-)

Thanks,
Yu

Quoted 13 lines

Quoted 13 lines

Quoted 13 lines

4) Revalidation:
In ->evict(), extent cache will be released, in order to reuse extent cache of inode when reopen for high hit ratio, a proper way is to add cached extent tree into a hash table (could be radix tree), revalidate extent tree and recover it to inode when reopen.
Besides, a global lru list is needed here for shrinker.

5) Readahead:
Expand extent cache by readaheading when we call get_dnode_of_data in non-emergency path. Note, ra can affect lock contention for both ->rwlock in extent cache and ->lock of global shrink list.

-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
Sent: Tuesday, December 30, 2014 5:23 AM
To: Chao Yu
Cc: 'Changman Lee'; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi Chao,

On Mon, Dec 29, 2014 at 03:19:18PM +0800, Chao Yu wrote:

[snip]

Nice draft. :)

Quoted 9 lines

Please see the draft below.

1) Extent management:
If we use global management that managing all extents which are from different inodes in sbi, we will face with serious lock contention when we access these extents belong to different inodes concurrently, the loss may outweights the gain.

Agreed.

Quoted 6 lines

So we choose a local management for extent which means all extents are managed by inode itself to avoid above lock contention. Addtionlly, we manage all extents globally by linking all inode into a global lru list for extent cache shrinker.
Approach:
a) build extent tree/rwlock/lru list/extent count in each inode.

Quoted 8 lines

*extent tree: link all extent in rb-tree;
*rwlock: protect fields when accessing extent cache concurrently; *lru list: sort all extents in accessing time order; *extent count: record total count of extents in cache.
b) use lru shrink list in sbi to manage all inode which cached extents. *inode will be added or repostioned in this global list whenever extent is being access in this inode.
*use spinlock to protect this shrink list.

1. How about adding a data structure with inode number instead of referring inode pointer?

2. How about managing extent entries globally and setting an upper bound to the number of extent entries instead of limiting them per each inode? (The rb-tree will handle many extents per inode.)

3. It needs to set a minimum length for the candidate of extent cache. (e.g., 64)

So, for example,

struct ino_entry_for_extents {
	inode number;
	rb_tree for extent_entry objects;
	rwlock;
};

struct extent_entry {
	blkaddr, len;
	list_head *;

};

Something like this.

[A, B, C, ... are extent entry]

The sbi has
1. an extent_list: (LRU) A -> B -> C -> D -> E -> F -> G (MRU)
2. radix_tree: ino_entry_for_extents (#10) has D, B in rb-tree ` ino_entry_for_extents (#11) has A, C in rb-tree
` ino_entry_for_extents (#12) has F in rb-tree
` ino_entry_for_extents (#13) has G, E in rb-tree

In f2fs_update_extent_cache and __get_data_block for #10,
ino_entry_for_extents (#10) was founded and updated D or B. Then, updated entries are moved to MRU.

In f2fs_evict_inode for #11, A and C are moved to LRU.
But, if this inode is unlinked, all the A, C, and ino_entry_for_extens (#11) should be released.

In f2fs_balance_fs_bg, some LRU extents are released according to the amount of consumed memory. Then, it frees any ino_entry_for_extents having no extent.

IMO, we don't need to consider readahead for this, since get_data_block will be called by VFS readahead.

Furthermore, we need to think about whether LRU is really best or not. IMO, the extent cache aims to improve second access speed, rather than initial cold misses. So, maybe MRU or another algorithms would be better.

Thanks,

Quoted 33 lines

2) Limitation:
In one inode, as we split or add extent in extent cache when read/write, extent number will enlarge, so memory and CPU overhead will increase.
In order to control the overhead of memory and CPU, we try to set a upper bound number to limit total extent number in each inode, This number is global configuration which is visable to all inode. This number will be exported to sysfs for configuring according to requirement of user. By default, designed number is 8.

3) Shrinker:
There are two shrink paths:
a) one is triggered when extent count has exceed the upper bound of inode's extent cache. We will try to release extent(s) from head of inode's inner extent lru list until extent count is equal to upper bound. This operation could be in f2fs_update_extent_cache().
b) the other one is triggered when memory util exceed threshold, we try get inode from head of global lru list(s), and release extent(s) with fixed number (by default: 64 extents) in inode one by one. This operation could be in f2fs_balance_fs_bg().

4) Revalidation:
In ->evict(), extent cache will be released, in order to reuse extent cache of inode when reopen for high hit ratio, a proper way is to add cached extent tree into a hash table (could be radix tree), revalidate extent tree and recover it to inode when reopen.
Besides, a global lru list is needed here for shrinker.

5) Readahead:
Expand extent cache by readaheading when we call get_dnode_of_data in non-emergency path. Note, ra can affect lock contention for both ->rwlock in extent cache and ->lock of global shrink list.

Hi Jaegeuk,

Quoted 7 lines

-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
Sent: Tuesday, December 30, 2014 5:23 AM
To: Chao Yu
Cc: 'Changman Lee'; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Quoted 7 lines

Hi Chao,

On Mon, Dec 29, 2014 at 03:19:18PM +0800, Chao Yu wrote:

[snip]

Nice draft. :)

Thanks! :)

Quoted 27 lines

Quoted 9 lines

Please see the draft below.

1) Extent management:
If we use global management that managing all extents which are from different inodes in sbi, we will face with serious lock contention when we access these extents belong to different inodes concurrently, the loss may outweights the gain.

Agreed.

Quoted 6 lines

So we choose a local management for extent which means all extents are managed by inode itself to avoid above lock contention. Addtionlly, we manage all extents globally by linking all inode into a global lru list for extent cache shrinker.
Approach:
a) build extent tree/rwlock/lru list/extent count in each inode.

Quoted 8 lines

*extent tree: link all extent in rb-tree;
*rwlock: protect fields when accessing extent cache concurrently; *lru list: sort all extents in accessing time order; *extent count: record total count of extents in cache.
b) use lru shrink list in sbi to manage all inode which cached extents. *inode will be added or repostioned in this global list whenever extent is being access in this inode.
*use spinlock to protect this shrink list.

Quoted 6 lines

1. How about adding a data structure with inode number instead of referring inode pointer?

2. How about managing extent entries globally and setting an upper bound to the number of extent entries instead of limiting them per each inode? (The rb-tree will handle many extents per inode.)

[assumption]
Approach A: global lru list;
Approach B: lru list per inode.

I have considered Approach A before writing the draft, although Approach A could provide us higher ratio hit due to global lru, it may make lock contention more intensively and has more memory overhead descripted below. So I choose more conservative Approach B.
1) as extent_entry will split in Cow, we may lock extent_list more times when move these separated extent entries in extent_list, unless we have batch mode interface.
2) lock overhead between shrinker and lookuper and updater.
e.g. extent_list: (LRU) A -> B -> C -> D -> E -> F -> G (MRU)
(#1) has A, C, E, G in rb-tree
(#2) has B, D, F in rb-tree
shrinker op: lock list -> trylock #1 -> unlock list -> free A -> unlock #1

	lock list -> trylock #2 -> unlock list -> free B -> unlock #2
	lock list -> trylock #1 -> unlock list -> free C -> unlock #1
	...

*trylock/unlock* for all free extent entries belong to one inode will be separated to lots of parts, resulting in more contention.
3) it has more memory overhead in each extent entry:
Approach A: need add inode number for backref and list_head *

Approach B: need add list_head *

Or maybe it's not a problem because we can afford all these above.

Anyway, I'm not against.

Quoted 3 lines

3. It needs to set a minimum length for the candidate of extent cache. (e.g., 64)

Is this used for shrinker? Can you please explain more about this minimum length?

Quoted 11 lines

So, for example,

struct ino_entry_for_extents {
	inode number;
	rb_tree for extent_entry objects;
	rwlock;
};

struct extent_entry {
	blkaddr, len;
	list_head *;

We should add one other field 'inode number' here, as through it we can get rb-tree root from ino_entry_for_extents for rb_erase when we free the extent entry in shrinker.

Quoted 24 lines

};

Something like this.

[A, B, C, ... are extent entry]

The sbi has
1. an extent_list: (LRU) A -> B -> C -> D -> E -> F -> G (MRU)
2. radix_tree: ino_entry_for_extents (#10) has D, B in rb-tree ` ino_entry_for_extents (#11) has A, C in rb-tree
` ino_entry_for_extents (#12) has F in rb-tree
` ino_entry_for_extents (#13) has G, E in rb-tree

In f2fs_update_extent_cache and __get_data_block for #10,
ino_entry_for_extents (#10) was founded and updated D or B. Then, updated entries are moved to MRU.

In f2fs_evict_inode for #11, A and C are moved to LRU.
But, if this inode is unlinked, all the A, C, and ino_entry_for_extens (#11) should be released.

In f2fs_balance_fs_bg, some LRU extents are released according to the amount of consumed memory. Then, it frees any ino_entry_for_extents having no extent.

Quoted 2 lines

IMO, we don't need to consider readahead for this, since get_data_block will be called by VFS readahead.

In get_data_block we can cache only one blkaddr once after get_dnode_of_data returned, it seems less efficient. So why not readahead selectively more contiguous valid blkaddr in get_dnode_of_data once?

Quoted 5 lines

Furthermore, we need to think about whether LRU is really best or not. IMO, the extent cache aims to improve second access speed, rather than initial cold misses. So, maybe MRU or another algorithms would be better.

Agree, let's rethink about this. :)

Thanks,

Quoted 36 lines

Thanks,

Quoted 33 lines

2) Limitation:
In one inode, as we split or add extent in extent cache when read/write, extent number will enlarge, so memory and CPU overhead will increase.
In order to control the overhead of memory and CPU, we try to set a upper bound number to limit total extent number in each inode, This number is global configuration which is visable to all inode. This number will be exported to sysfs for configuring according to requirement of user. By default, designed number is 8.

3) Shrinker:
There are two shrink paths:
a) one is triggered when extent count has exceed the upper bound of inode's extent cache. We will try to release extent(s) from head of inode's inner extent lru list until extent count is equal to upper bound. This operation could be in f2fs_update_extent_cache().
b) the other one is triggered when memory util exceed threshold, we try get inode from head of global lru list(s), and release extent(s) with fixed number (by default: 64 extents) in inode one by one. This operation could be in f2fs_balance_fs_bg().

4) Revalidation:
In ->evict(), extent cache will be released, in order to reuse extent cache of inode when reopen for high hit ratio, a proper way is to add cached extent tree into a hash table (could be radix tree), revalidate extent tree and recover it to inode when reopen.
Besides, a global lru list is needed here for shrinker.

5) Readahead:
Expand extent cache by readaheading when we call get_dnode_of_data in non-emergency path. Note, ra can affect lock contention for both ->rwlock in extent cache and ->lock of global shrink list.

-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
Sent: Wednesday, December 31, 2014 4:26 PM
To: Chao Yu
Cc: 'Changman Lee'; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi Chao,

Quoted 69 lines · Chao Yu

Hi Jaegeuk,

Quoted 7 lines

-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
Sent: Tuesday, December 30, 2014 5:23 AM
To: Chao Yu
Cc: 'Changman Lee'; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Quoted 7 lines

Hi Chao,

On Mon, Dec 29, 2014 at 03:19:18PM +0800, Chao Yu wrote:

[snip]

Nice draft. :)

Thanks! :)

Quoted 27 lines

Quoted 9 lines

Please see the draft below.

1) Extent management:
If we use global management that managing all extents which are from different inodes in sbi, we will face with serious lock contention when we access these extents belong to different inodes concurrently, the loss may outweights the gain.

Agreed.

Quoted 6 lines

So we choose a local management for extent which means all extents are managed by inode itself to avoid above lock contention. Addtionlly, we manage all extents globally by linking all inode into a global lru list for extent cache shrinker.
Approach:
a) build extent tree/rwlock/lru list/extent count in each inode.

Quoted 8 lines

*extent tree: link all extent in rb-tree;
*rwlock: protect fields when accessing extent cache concurrently; *lru list: sort all extents in accessing time order; *extent count: record total count of extents in cache.
b) use lru shrink list in sbi to manage all inode which cached extents. *inode will be added or repostioned in this global list whenever extent is being access in this inode.
*use spinlock to protect this shrink list.

Quoted 6 lines

1. How about adding a data structure with inode number instead of referring inode pointer?

2. How about managing extent entries globally and setting an upper bound to the number of extent entries instead of limiting them per each inode? (The rb-tree will handle many extents per inode.)

[assumption]
Approach A: global lru list;
Approach B: lru list per inode.

I have considered Approach A before writing the draft, although Approach A could provide us higher ratio hit due to global lru, it may make lock contention more intensively and has more memory overhead descripted below. So I choose more conservative Approach B.
1) as extent_entry will split in Cow, we may lock extent_list more times when move these separated extent entries in extent_list, unless we have batch mode interface.
2) lock overhead between shrinker and lookuper and updater.
e.g. extent_list: (LRU) A -> B -> C -> D -> E -> F -> G (MRU)
(#1) has A, C, E, G in rb-tree
(#2) has B, D, F in rb-tree
shrinker op: lock list -> trylock #1 -> unlock list -> free A -> unlock #1

Quoted 3 lines

	lock list -> trylock #2 -> unlock list -> free B -> unlock #2
	lock list -> trylock #1 -> unlock list -> free C -> unlock #1
	...

lock_list -> list_del(A) -> unlock_list -> lock #1 -> remove_tree(A) -> unlock #1 -> free A.

Or,
lock_list -> list_del(A, B, C) -> unlock_list -> lock #1 -> remove_tree(A, C) -> unlock #1 -> free A, C -> lock #2 -> remove_tree(B) -> unlock #2

I think a couple of list operations do not cause severe lock contention.

And, if we assing minimum length for extent caches, the contention would be distributed.

This means that, it needs to manage each of all the extents in the cache should have the length larger than minimum value.

Quoted 5 lines

*trylock/unlock* for all free extent entries belong to one inode will be separated to lots of parts, resulting in more contention.
3) it has more memory overhead in each extent entry:
Approach A: need add inode number for backref and list_head *

It doesn't need to add ino. Just remain them, and shrinker can remove empty ino_entry_for_extents periodically.

Quoted 56 lines

Approach B: need add list_head *

Or maybe it's not a problem because we can afford all these above.

Anyway, I'm not against.

Quoted 3 lines

3. It needs to set a minimum length for the candidate of extent cache. (e.g., 64)

Is this used for shrinker? Can you please explain more about this minimum length?

Quoted 11 lines

So, for example,

struct ino_entry_for_extents {
	inode number;
	rb_tree for extent_entry objects;
	rwlock;
};

struct extent_entry {
	blkaddr, len;
	list_head *;

We should add one other field 'inode number' here, as through it we can get rb-tree root from ino_entry_for_extents for rb_erase when we free the extent entry in shrinker.

Quoted 26 lines

};

Something like this.

[A, B, C, ... are extent entry]

The sbi has
1. an extent_list: (LRU) A -> B -> C -> D -> E -> F -> G (MRU)
2. radix_tree: ino_entry_for_extents (#10) has D, B in rb-tree ` ino_entry_for_extents (#11) has A, C in rb-tree
` ino_entry_for_extents (#12) has F in rb-tree
` ino_entry_for_extents (#13) has G, E in rb-tree

In f2fs_update_extent_cache and __get_data_block for #10,
ino_entry_for_extents (#10) was founded and updated D or B. Then, updated entries are moved to MRU.

In f2fs_evict_inode for #11, A and C are moved to LRU.
But, if this inode is unlinked, all the A, C, and ino_entry_for_extens (#11) should be released.

In f2fs_balance_fs_bg, some LRU extents are released according to the amount of consumed memory. Then, it frees any ino_entry_for_extents having no extent.

IMO, we don't need to consider readahead for this, since get_data_block will be called by VFS readahead.

Quoted 3 lines

In get_data_block we can cache only one blkaddr once after get_dnode_of_data returned, it seems less efficient. So why not readahead selectively more contiguous valid blkaddr in get_dnode_of_data once?

Why do you think only one blkaddr? get_data_block searches extents as many as possible.

Thanks,

Quoted 46 lines

Quoted 5 lines

Furthermore, we need to think about whether LRU is really best or not. IMO, the extent cache aims to improve second access speed, rather than initial cold misses. So, maybe MRU or another algorithms would be better.

Agree, let's rethink about this. :)

Thanks,

Quoted 36 lines

Thanks,

Quoted 33 lines

2) Limitation:
In one inode, as we split or add extent in extent cache when read/write, extent number will enlarge, so memory and CPU overhead will increase.
In order to control the overhead of memory and CPU, we try to set a upper bound number to limit total extent number in each inode, This number is global configuration which is visable to all inode. This number will be exported to sysfs for configuring according to requirement of user. By default, designed number is 8.

3) Shrinker:
There are two shrink paths:
a) one is triggered when extent count has exceed the upper bound of inode's extent cache. We will try to release extent(s) from head of inode's inner extent lru list until extent count is equal to upper bound. This operation could be in f2fs_update_extent_cache().
b) the other one is triggered when memory util exceed threshold, we try get inode from head of global lru list(s), and release extent(s) with fixed number (by default: 64 extents) in inode one by one. This operation could be in f2fs_balance_fs_bg().

4) Revalidation:
In ->evict(), extent cache will be released, in order to reuse extent cache of inode when reopen for high hit ratio, a proper way is to add cached extent tree into a hash table (could be radix tree), revalidate extent tree and recover it to inode when reopen.
Besides, a global lru list is needed here for shrinker.

5) Readahead:
Expand extent cache by readaheading when we call get_dnode_of_data in non-emergency path. Note, ra can affect lock contention for both ->rwlock in extent cache and ->lock of global shrink list.

Hi Jaegeuk,

Quoted 83 lines

-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
Sent: Wednesday, December 31, 2014 4:26 PM
To: Chao Yu
Cc: 'Changman Lee'; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi Chao,

Quoted 69 lines · Chao Yu

Hi Jaegeuk,

Quoted 7 lines

-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
Sent: Tuesday, December 30, 2014 5:23 AM
To: Chao Yu
Cc: 'Changman Lee'; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Quoted 7 lines

Hi Chao,

On Mon, Dec 29, 2014 at 03:19:18PM +0800, Chao Yu wrote:

[snip]

Nice draft. :)

Thanks! :)

Quoted 27 lines

Quoted 9 lines

Please see the draft below.

1) Extent management:
If we use global management that managing all extents which are from different inodes in sbi, we will face with serious lock contention when we access these extents belong to different inodes concurrently, the loss may outweights the gain.

Agreed.

Quoted 6 lines

So we choose a local management for extent which means all extents are managed by inode itself to avoid above lock contention. Addtionlly, we manage all extents globally by linking all inode into a global lru list for extent cache shrinker.
Approach:
a) build extent tree/rwlock/lru list/extent count in each inode.

Quoted 8 lines

*extent tree: link all extent in rb-tree;
*rwlock: protect fields when accessing extent cache concurrently; *lru list: sort all extents in accessing time order; *extent count: record total count of extents in cache.
b) use lru shrink list in sbi to manage all inode which cached extents. *inode will be added or repostioned in this global list whenever extent is being access in this inode.
*use spinlock to protect this shrink list.

Quoted 6 lines

1. How about adding a data structure with inode number instead of referring inode pointer?

2. How about managing extent entries globally and setting an upper bound to the number of extent entries instead of limiting them per each inode? (The rb-tree will handle many extents per inode.)

[assumption]
Approach A: global lru list;
Approach B: lru list per inode.

I have considered Approach A before writing the draft, although Approach A could provide us higher ratio hit due to global lru, it may make lock contention more intensively and has more memory overhead descripted below. So I choose more conservative Approach B.
1) as extent_entry will split in Cow, we may lock extent_list more times when move these separated extent entries in extent_list, unless we have batch mode interface.
2) lock overhead between shrinker and lookuper and updater.
e.g. extent_list: (LRU) A -> B -> C -> D -> E -> F -> G (MRU)
(#1) has A, C, E, G in rb-tree
(#2) has B, D, F in rb-tree
shrinker op: lock list -> trylock #1 -> unlock list -> free A -> unlock #1

Quoted 3 lines

	lock list -> trylock #2 -> unlock list -> free B -> unlock #2
	lock list -> trylock #1 -> unlock list -> free C -> unlock #1
	...

Quoted 2 lines

lock_list -> list_del(A) -> unlock_list -> lock #1 -> remove_tree(A) -> unlock #1 -> free A.

If unlock_list before lock #1, (A) could be modified by other thread between ->unlock_list and lock #1, so one more "lookup_tree(A)" is needed under lock #1:
lock #1 -> lookup_tree(A) -> remove_tree(A) -> unlock #1

Quoted 4 lines

Or,
lock_list -> list_del(A, B, C) -> unlock_list -> lock #1 -> remove_tree(A, C) -> unlock #1 -> free A, C -> lock #2 -> remove_tree(B) -> unlock #2

ditto.
To avoid unneeded lookup_tree(A), maybe we can use this series:

lock list -> get A from head -> trylock #1 -> try to get more node(C, E, G) of #1 in list -> unlock list -> remove_tree&free(A, C, E, G) -> unlock #1

Quoted 2 lines

I think a couple of list operations do not cause severe lock contention.

Yeah, batch operation is better.
But sometimes random write break extent into everywhere in shrinker's list, so batch operation can gain less in this condition.

Quoted 5 lines

And, if we assing minimum length for extent caches, the contention would be distributed.

This means that, it needs to manage each of all the extents in the cache should have the length larger than minimum value.

If I do not misunderstand, what you mean is that if extent number in one inode cache is bigger than minimum value, then, we will start to add all extents of this inode into shrinker's list, and reposition them in the list when f2fs_{lookup,update}_extent_cache?

Quoted 6 lines

Quoted 5 lines

*trylock/unlock* for all free extent entries belong to one inode will be separated to lots of parts, resulting in more contention.
3) it has more memory overhead in each extent entry:
Approach A: need add inode number for backref and list_head *

Quoted 2 lines

It doesn't need to add ino. Just remain them, and shrinker can remove empty ino_entry_for_extents periodically.

I do not understand why we don't need ino, :(.
Without ino, how can we get the rb-tree root pointer for rb_erase(node, root)?

Quoted 57 lines

Quoted 57 lines

Approach B: need add list_head *

Or maybe it's not a problem because we can afford all these above.

Anyway, I'm not against.

Quoted 3 lines

3. It needs to set a minimum length for the candidate of extent cache. (e.g., 64)

Is this used for shrinker? Can you please explain more about this minimum length?

Quoted 11 lines

So, for example,

struct ino_entry_for_extents {
	inode number;
	rb_tree for extent_entry objects;
	rwlock;
};

struct extent_entry {
	blkaddr, len;
	list_head *;

We should add one other field 'inode number' here, as through it we can get rb-tree root from ino_entry_for_extents for rb_erase when we free the extent entry in shrinker.

Quoted 26 lines

};

Something like this.

[A, B, C, ... are extent entry]

The sbi has
1. an extent_list: (LRU) A -> B -> C -> D -> E -> F -> G (MRU)
2. radix_tree: ino_entry_for_extents (#10) has D, B in rb-tree ` ino_entry_for_extents (#11) has A, C in rb-tree
` ino_entry_for_extents (#12) has F in rb-tree
` ino_entry_for_extents (#13) has G, E in rb-tree

In f2fs_update_extent_cache and __get_data_block for #10,
ino_entry_for_extents (#10) was founded and updated D or B. Then, updated entries are moved to MRU.

In f2fs_evict_inode for #11, A and C are moved to LRU.
But, if this inode is unlinked, all the A, C, and ino_entry_for_extens (#11) should be released.

In f2fs_balance_fs_bg, some LRU extents are released according to the amount of consumed memory. Then, it frees any ino_entry_for_extents having no extent.

IMO, we don't need to consider readahead for this, since get_data_block will be called by VFS readahead.

Quoted 6 lines

Quoted 3 lines

In get_data_block we can cache only one blkaddr once after get_dnode_of_data returned, it seems less efficient. So why not readahead selectively more contiguous valid blkaddr in get_dnode_of_data once?

Why do you think only one blkaddr? get_data_block searches extents as many as possible.

Surely not one blkaddr.

Actually, what I mean is that:
->get_dnode_of_data
->f2fs_ra_extent_cache()

f2fs_ra_extent_cache(node_page, offset) {
	for (i = offset; i < max; i++) {
		if (is_valid() && is_contiguous())
			len++;
	}
	f2fs_update_extent_cache(inode, fofs, blk_addr, len)
}

But not:
->__get_data_block
->get_dnode_of_data ->f2fs_update_extent_cache(inode, fofs, blk_addr, 1);

Thanks,
Yu

Quoted 49 lines

Thanks,

Quoted 46 lines

Quoted 5 lines

Furthermore, we need to think about whether LRU is really best or not. IMO, the extent cache aims to improve second access speed, rather than initial cold misses. So, maybe MRU or another algorithms would be better.

Agree, let's rethink about this. :)

Thanks,

Quoted 36 lines

Thanks,

Quoted 33 lines

2) Limitation:
In one inode, as we split or add extent in extent cache when read/write, extent number will enlarge, so memory and CPU overhead will increase.
In order to control the overhead of memory and CPU, we try to set a upper bound number to limit total extent number in each inode, This number is global configuration which is visable to all inode. This number will be exported to sysfs for configuring according to requirement of user. By default, designed number is 8.

3) Shrinker:
There are two shrink paths:
a) one is triggered when extent count has exceed the upper bound of inode's extent cache. We will try to release extent(s) from head of inode's inner extent lru list until extent count is equal to upper bound. This operation could be in f2fs_update_extent_cache().
b) the other one is triggered when memory util exceed threshold, we try get inode from head of global lru list(s), and release extent(s) with fixed number (by default: 64 extents) in inode one by one. This operation could be in f2fs_balance_fs_bg().

4) Revalidation:
In ->evict(), extent cache will be released, in order to reuse extent cache of inode when reopen for high hit ratio, a proper way is to add cached extent tree into a hash table (could be radix tree), revalidate extent tree and recover it to inode when reopen.
Besides, a global lru list is needed here for shrinker.

5) Readahead:
Expand extent cache by readaheading when we call get_dnode_of_data in non-emergency path. Note, ra can affect lock contention for both ->rwlock in extent cache and ->lock of global shrink list.

-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
Sent: Wednesday, January 07, 2015 7:01 AM
To: Chao Yu
Cc: 'Changman Lee'; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi Chao,

Quoted 19 lines · Chao Yu

Hi Jaegeuk,

Quoted 17 lines

-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
Sent: Wednesday, December 31, 2014 4:26 PM
To: Chao Yu
Cc: 'Changman Lee'; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi Chao,

Quoted 7 lines · Chao Yu

Hi Jaegeuk,

Quoted 5 lines

-----Original Message-----
From: Jaegeuk Kim [mailto:[email protected]]
Sent: Tuesday, December 30, 2014 5:23 AM
To: Chao Yu
Cc: 'Changman Lee'; [email protected];

[email protected]

Quoted 107 lines

Quoted 66 lines

Quoted 62 lines

Quoted 9 lines

Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi Chao,

On Mon, Dec 29, 2014 at 03:19:18PM +0800, Chao Yu wrote:

[snip]

Nice draft. :)

Thanks! :)

Quoted 27 lines

Quoted 9 lines

Please see the draft below.

1) Extent management:
If we use global management that managing all extents which are from different inodes in sbi, we will face with serious lock contention when we access these extents belong to different inodes concurrently, the loss may outweights the gain.

Agreed.

Quoted 6 lines

So we choose a local management for extent which means all extents are managed by inode itself to avoid above lock contention. Addtionlly, we manage all extents globally by linking all inode into a global lru list for extent cache shrinker.
Approach:
a) build extent tree/rwlock/lru list/extent count in each inode.

Quoted 8 lines

*extent tree: link all extent in rb-tree;
*rwlock: protect fields when accessing extent cache concurrently; *lru list: sort all extents in accessing time order; *extent count: record total count of extents in cache.
b) use lru shrink list in sbi to manage all inode which cached extents. *inode will be added or repostioned in this global list whenever extent is being access in this inode.
*use spinlock to protect this shrink list.

Quoted 6 lines

1. How about adding a data structure with inode number instead of referring inode pointer?

2. How about managing extent entries globally and setting an upper bound to the number of extent entries instead of limiting them per each inode? (The rb-tree will handle many extents per inode.)

[assumption]
Approach A: global lru list;
Approach B: lru list per inode.

I have considered Approach A before writing the draft, although Approach A could provide us higher ratio hit due to global lru, it may make lock contention more intensively and has more memory overhead descripted below. So I choose more conservative Approach B.
1) as extent_entry will split in Cow, we may lock extent_list more times when move these separated extent entries in extent_list, unless we have batch mode interface.
2) lock overhead between shrinker and lookuper and updater.
e.g. extent_list: (LRU) A -> B -> C -> D -> E -> F -> G (MRU)
(#1) has A, C, E, G in rb-tree
(#2) has B, D, F in rb-tree
shrinker op: lock list -> trylock #1 -> unlock list -> free A -> unlock #1

Quoted 3 lines

	lock list -> trylock #2 -> unlock list -> free B -> unlock #2
	lock list -> trylock #1 -> unlock list -> free C -> unlock #1
	...

Quoted 2 lines

lock_list -> list_del(A) -> unlock_list -> lock #1 -> remove_tree(A) -> unlock #1 -> free A.

If unlock_list before lock #1, (A) could be modified by other thread between ->unlock_list and lock #1, so one more "lookup_tree(A)" is needed under lock #1:
lock #1 -> lookup_tree(A) -> remove_tree(A) -> unlock #1

Quoted 4 lines

Or,
lock_list -> list_del(A, B, C) -> unlock_list -> lock #1 -> remove_tree(A, C) -> unlock #1 -> free A, C -> lock #2 -> remove_tree(B) -> unlock #2

ditto.
To avoid unneeded lookup_tree(A), maybe we can use this series:

lock list -> get A from head -> trylock #1 -> try to get more node(C, E, G) of #1 in list -> unlock list -> remove_tree&free(A, C, E, G) -> unlock #1

Quoted 2 lines

I think a couple of list operations do not cause severe lock contention.

Yeah, batch operation is better.
But sometimes random write break extent into everywhere in shrinker's list, so batch operation can gain less in this condition.

Quoted 5 lines

And, if we assing minimum length for extent caches, the contention would be distributed.

This means that, it needs to manage each of all the extents in the cache should have the length larger than minimum value.

If I do not misunderstand, what you mean is that if extent number in one inode cache is bigger than minimum value, then, we will start to add all extents of this inode into shrinker's list, and reposition them in the list when f2fs_{lookup,update}_extent_cache?

Quoted 6 lines

Quoted 5 lines

*trylock/unlock* for all free extent entries belong to one inode will be separated to lots of parts, resulting in more contention.
3) it has more memory overhead in each extent entry:
Approach A: need add inode number for backref and list_head *

Quoted 5 lines

Quoted 2 lines

It doesn't need to add ino. Just remain them, and shrinker can remove empty ino_entry_for_extents periodically.

I do not understand why we don't need ino, :(.
Without ino, how can we get the rb-tree root pointer for rb_erase(node, root)?

Let me describe in more detail.

For example,

- global radix tree in sbi
--> ino #1 --> rb_tree (rb_tree, rb_tree_lock, refcount=0) --> ino #2 --> rb_tree
--> ino #3 --> rb_tree

                    `-> extent A
		    `-> extent B (fofs, blkaddr, length, *list_head=empty)

- global extent list in sbi

extent_list: (LRU) A -> B -> C -> D -> E -> F -> G (MRU) (#1) has A, C, E, G in rb-tree
(#2) has B, D, F in rb-tree

1) update extents (#1)

- lock_radix_tree

     if (notfound #1)
         allocate #1;
     #1's refcount++;

- unlock_radix_tree

- lock_rb_tree (#1)

     update A
     rb_delete E, if E->length is smaller than MIN_LEN.
     allocate & rb_add K, if K->length is larget than MIN_LEN.

     list_lock
     list_move(A)
     list_del(E)
     list_add_tail(K)
     list_unlock

- unlock_rb_tree (#1)

- #1's rafcount--;

2) shrinker

- list_lock

     list_del A, B, C, ...

- list_unlock

- gang_look_up_radix_tree_with_lock {

     #N's refcount++;

     lock_rb_tree (#N)
         for_each_rb_node {
             if (list_empty(extent->list_head)) {
                 remove_rb_node(extent);
                 free(extent);
             }
	 }
     unlock_rb_tree (#N)

     #N's refcount--;

- }

 - for_each_radix_tree_with_lock {
     if (radix_node->refcount == 0 && rb_tree_is_empty)
         free(radix_node);

- }

3) lookup extents (#1)

- lock_radix_tree

     if (notfound #1)
         goto out;
     #1's refcount++;

- unlock_radix_tree

- lock_rb_tree (#1)
found extent A

list_lock
list_move(A)
list_unlock
- unlock_rb_tree (#1)

- #1's rafcount--;

Hi Changman,

Quoted 10 lines

-----Original Message-----
From: Changman Lee [mailto:[email protected]]
Sent: Monday, December 22, 2014 10:03 AM
To: Chao Yu
Cc: Jaegeuk Kim; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi Yu,

Good approach.

Thank you. :)

Quoted 1 line

As you know, however, f2fs breaks extent itself due to COW.

Yes, and sometimes f2fs use IPU when override writing, in this condition, by using this approach we can cache more contiguous mapping extent for better performance.

Quoted 3 lines

Unlike other filesystem like btrfs, minimum extent of f2fs could have 4KB granularity. So we would have lots of extents per inode and it could lead to overhead to manage extents.

Agree, the more number of extents are growing in one inode, the more memory pressure and longer latency operating in rb-tree we are facing.
IMO, to solve this problem, we'd better to add limitation or shrink ability into extent cache:
1.limit extent number per inode with the value set from sysfs and discard extent from inode's extent lru list if we touch the limitation; (e.g. in FAT, max number of mapping extent per inode is fixed: 8)
2.add all extents of inodes into a global lru list, we will try to shrink this list if we're facing memory pressure.

How do you think? or any better ideas are welcome. :)

Quoted 2 lines

Anyway, mount option could be alternative for this patch.

Yes, will do.

Thanks,
Yu

Quoted 28 lines · Chao Yu

Quoted 26 lines

Now f2fs have page-block mapping cache which can cache only one extent mapping between contiguous logical address and physical address. Normally, this design will work well because f2fs will expand coverage area of the mapping extent when we write forward sequentially. But when we write data randomly in Out-Place-Update mode, the extent will be shorten and hardly be expanded for most time as following reasons:
1.The short part of extent will be discarded if we break contiguous mapping in the middle of extent.
2.The new mapping will be added into mapping cache only at head or tail of the extent.
3.We will drop the extent cache when the extent became very fragmented. 4.We will not update the extent with mapping which we get from readpages or readpage.

To solve above problems, this patch adds extent cache base on rb-tree like other filesystems (e.g.: ext4/btrfs) in f2fs. By this way, f2fs can support another more effective cache between dnode page cache and disk. It will supply high hit ratio in the cache with fewer memory when dnode page cache are reclaimed in environment of low memory.

Todo:
*introduce mount option for extent cache.
*add shrink ability for extent cache.

Signed-off-by Chao Yu <[email protected]>

---

-----Original Message-----
From: Changman Lee [mailto:[email protected]]
Sent: Tuesday, December 23, 2014 12:31 PM
To: Chao Yu
Cc: 'Jaegeuk Kim'; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi,

Quoted 35 lines · Chao Yu

Hi Changman,

Quoted 10 lines

-----Original Message-----
From: Changman Lee [mailto:[email protected]]
Sent: Monday, December 22, 2014 10:03 AM
To: Chao Yu
Cc: Jaegeuk Kim; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi Yu,

Good approach.

Thank you. :)

Quoted 1 line

As you know, however, f2fs breaks extent itself due to COW.

Yes, and sometimes f2fs use IPU when override writing, in this condition, by using this approach we can cache more contiguous mapping extent for better performance.

Quoted 3 lines

Unlike other filesystem like btrfs, minimum extent of f2fs could have 4KB granularity. So we would have lots of extents per inode and it could lead to overhead to manage extents.

Agree, the more number of extents are growing in one inode, the more memory pressure and longer latency operating in rb-tree we are facing.
IMO, to solve this problem, we'd better to add limitation or shrink ability into extent cache:
1.limit extent number per inode with the value set from sysfs and discard extent from inode's extent lru list if we touch the limitation; (e.g. in FAT, max number of mapping extent per inode is fixed: 8)
2.add all extents of inodes into a global lru list, we will try to shrink this list if we're facing memory pressure.

Quoted 2 lines

How do you think? or any better ideas are welcome. :)

I think both of them are considerable options.
How about adding extent to inode selected by user using ioctl or xattr? In the case of read most files having large size, user could get a benefit surely although they are seperated some pieces.

Thanks,

Quoted 37 lines

Quoted 2 lines

Anyway, mount option could be alternative for this patch.

Yes, will do.

Thanks,
Yu

Quoted 28 lines · Chao Yu

Quoted 26 lines

Now f2fs have page-block mapping cache which can cache only one extent mapping between contiguous logical address and physical address. Normally, this design will work well because f2fs will expand coverage area of the mapping extent when we write forward sequentially. But when we write data randomly in Out-Place-Update mode, the extent will be shorten and hardly be expanded for most time as following reasons:
1.The short part of extent will be discarded if we break contiguous mapping in the middle of extent.
2.The new mapping will be added into mapping cache only at head or tail of the extent.
3.We will drop the extent cache when the extent became very fragmented. 4.We will not update the extent with mapping which we get from readpages or readpage.

To solve above problems, this patch adds extent cache base on rb-tree like other filesystems (e.g.: ext4/btrfs) in f2fs. By this way, f2fs can support another more effective cache between dnode page cache and disk. It will supply high hit ratio in the cache with fewer memory when dnode page cache are reclaimed in environment of low memory.

Todo:
*introduce mount option for extent cache.
*add shrink ability for extent cache.

Signed-off-by Chao Yu <[email protected]>

---

Hi Changman,

Quoted 45 lines

-----Original Message-----
From: Changman Lee [mailto:[email protected]]
Sent: Tuesday, December 23, 2014 12:31 PM
To: Chao Yu
Cc: 'Jaegeuk Kim'; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi,

Quoted 35 lines · Chao Yu

Hi Changman,

Quoted 10 lines

-----Original Message-----
From: Changman Lee [mailto:[email protected]]
Sent: Monday, December 22, 2014 10:03 AM
To: Chao Yu
Cc: Jaegeuk Kim; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi Yu,

Good approach.

Thank you. :)

Quoted 1 line

As you know, however, f2fs breaks extent itself due to COW.

Yes, and sometimes f2fs use IPU when override writing, in this condition, by using this approach we can cache more contiguous mapping extent for better performance.

Quoted 3 lines

Unlike other filesystem like btrfs, minimum extent of f2fs could have 4KB granularity. So we would have lots of extents per inode and it could lead to overhead to manage extents.

Agree, the more number of extents are growing in one inode, the more memory pressure and longer latency operating in rb-tree we are facing.
IMO, to solve this problem, we'd better to add limitation or shrink ability into extent cache:
1.limit extent number per inode with the value set from sysfs and discard extent from inode's extent lru list if we touch the limitation; (e.g. in FAT, max number of mapping extent per inode is fixed: 8)
2.add all extents of inodes into a global lru list, we will try to shrink this list if we're facing memory pressure.

Quoted 7 lines

Quoted 2 lines

How do you think? or any better ideas are welcome. :)

I think both of them are considerable options.
How about adding extent to inode selected by user using ioctl or xattr? In the case of read most files having large size, user could get a benefit surely although they are seperated some pieces.

Yes, I agree, I prefer ioctl more than xattr, as xattr will take over some extra space of inode, and also new added xattr name may conflict with exist extent xattr.

Anyway, this will provide more flexible management of extent cache to users of f2fs.

Thank you for your idea!

Regards,
Yu

Quoted 40 lines

Thanks,

Quoted 37 lines

Quoted 2 lines

Anyway, mount option could be alternative for this patch.

Yes, will do.

Thanks,
Yu

Quoted 28 lines · Chao Yu

Quoted 26 lines

Now f2fs have page-block mapping cache which can cache only one extent mapping between contiguous logical address and physical address. Normally, this design will work well because f2fs will expand coverage area of the mapping extent when we write forward sequentially. But when we write data randomly in Out-Place-Update mode, the extent will be shorten and hardly be expanded for most time as following reasons:
1.The short part of extent will be discarded if we break contiguous mapping in the middle of extent.
2.The new mapping will be added into mapping cache only at head or tail of the extent.
3.We will drop the extent cache when the extent became very fragmented. 4.We will not update the extent with mapping which we get from readpages or readpage.

To solve above problems, this patch adds extent cache base on rb-tree like other filesystems (e.g.: ext4/btrfs) in f2fs. By this way, f2fs can support another more effective cache between dnode page cache and disk. It will supply high hit ratio in the cache with fewer memory when dnode page cache are reclaimed in environment of low memory.

Todo:
*introduce mount option for extent cache.
*add shrink ability for extent cache.

Signed-off-by Chao Yu <[email protected]>

---

-----Original Message-----
From: Changman Lee [mailto:[email protected]]
Sent: Monday, December 22, 2014 10:03 AM
To: Chao Yu
Cc: Jaegeuk Kim; [email protected]; [email protected]
Subject: Re: [RFC PATCH] f2fs: add extent cache base on rb-tree

Hi Yu,

Good approach.
As you know, however, f2fs breaks extent itself due to COW.
Unlike other filesystem like btrfs, minimum extent of f2fs could have 4KB granularity. So we would have lots of extents per inode and it could lead to overhead to manage extents.

Anyway, mount option could be alternative for this patch.

Quoted 25 lines · Chao Yu

Now f2fs have page-block mapping cache which can cache only one extent mapping between contiguous logical address and physical address. Normally, this design will work well because f2fs will expand coverage area of the mapping extent when we write forward sequentially. But when we write data randomly in Out-Place-Update mode, the extent will be shorten and hardly be expanded for most time as following reasons:
1.The short part of extent will be discarded if we break contiguous mapping in the middle of extent.
2.The new mapping will be added into mapping cache only at head or tail of the extent.
3.We will drop the extent cache when the extent became very fragmented. 4.We will not update the extent with mapping which we get from readpages or readpage.

To solve above problems, this patch adds extent cache base on rb-tree like other filesystems (e.g.: ext4/btrfs) in f2fs. By this way, f2fs can support another more effective cache between dnode page cache and disk. It will supply high hit ratio in the cache with fewer memory when dnode page cache are reclaimed in environment of low memory.

Todo:
*introduce mount option for extent cache.
*add shrink ability for extent cache.

Signed-off-by Chao Yu <[email protected]>

Quoted 5 lines

fs/f2fs/data.c +5 -0

+static void __try_merge_extent(struct inode *inode, struct extent_info *ei)
+{
+	struct rb_root *root = &F2FS_I(inode)->ei_tree.root;
+	struct extent_info *pei = NULL;
+	struct rb_node *node;

fs/f2fs/data.c int f2fs_reserve_block(struct dnode_of_data *dn, pgoff_t index) · line 321

Quoted 5 lines

fs/f2fs/data.c +5 -0

+
+	node = rb_prev(&ei->rb_node);
+	if (node) {
+		pei = rb_entry(node, struct extent_info, rb_node);
+		if (ei->blk == pei->blk + pei->len) {

Shouldn't we check below together, too?
if (ei->fofs == pei->fofs + pei->len)