This patch adds a fast lookup path for rb-tree extent cache.
In this patch we add a recently accessed extent node pointer 'cached_en' in
extent tree. In lookup path of extent cache, we will firstly lookup the last
accessed extent node which cached_en points, if we do not hit in this node,
we will try to lookup extent node in rb-tree.
By this way we can avoid unnecessary slow lookup in rb-tree sometimes.
Note that, side-effect of this patch is that we will increase memory cost,
because we will store a pointer variable in each struct extent tree
additionally.
Signed-off-by: Chao Yu <chao2...@samsung.com>
---
fs/f2fs/data.c | 19 ++++++++++++++++---
fs/f2fs/f2fs.h | 1 +
2 files changed, 17 insertions(+), 3 deletions(-)
diff --git a/fs/f2fs/data.c b/fs/f2fs/data.c
index 4ba1605..112db9c 100644
--- a/fs/f2fs/data.c
+++ b/fs/f2fs/data.c
@@ -395,6 +395,9 @@ static void __detach_extent_node(struct f2fs_sb_info *sbi,
rb_erase(&en->rb_node, &et->root);
et->count--;
atomic_dec(&sbi->total_ext_node);
+
+ if (et->cached_en == en)
+ et->cached_en = NULL;
}
static struct extent_node *__lookup_extent_tree(struct extent_tree *et,
@@ -403,15 +406,24 @@ static struct extent_node *__lookup_extent_tree(struct
extent_tree *et,
struct rb_node *node = et->root.rb_node;
struct extent_node *en;
+ if (et->cached_en) {
+ struct extent_info *cei = &et->cached_en->ei;
+
+ if (cei->fofs <= fofs && cei->fofs + cei->len > fofs)
+ return et->cached_en;
+ }
+
while (node) {
en = rb_entry(node, struct extent_node, rb_node);
- if (fofs < en->ei.fofs)
+ if (fofs < en->ei.fofs) {
node = node->rb_left;
- else if (fofs >= en->ei.fofs + en->ei.len)
+ } else if (fofs >= en->ei.fofs + en->ei.len) {
node = node->rb_right;
- else
+ } else {
+ et->cached_en = en;
return en;
+ }
}
return NULL;
}
@@ -587,6 +599,7 @@ static void f2fs_update_extent_tree(struct inode *inode,
pgoff_t fofs,
memset(et, 0, sizeof(struct extent_tree));
et->ino = ino;
et->root = RB_ROOT;
+ et->cached_en = NULL;
rwlock_init(&et->lock);
atomic_set(&et->refcount, 0);
et->count = 0;
diff --git a/fs/f2fs/f2fs.h b/fs/f2fs/f2fs.h
index 9572f7c..47b30de 100644
--- a/fs/f2fs/f2fs.h
+++ b/fs/f2fs/f2fs.h
@@ -296,6 +296,7 @@ struct extent_node {
struct extent_tree {
nid_t ino; /* inode number */
struct rb_root root; /* root of extent info rb-tree */
+ struct extent_node *cached_en; /* recently accessed extent node */
rwlock_t lock; /* protect extent info rb-tree */
atomic_t refcount; /* reference count of rb-tree */
unsigned int count; /* # of extent node in rb-tree*/
--
2.2.1
------------------------------------------------------------------------------
Dive into the World of Parallel Programming. The Go Parallel Website,
sponsored by Intel and developed in partnership with Slashdot Media, is your
hub for all things parallel software development, from weekly thought
leadership blogs to news, videos, case studies, tutorials and more. Take a
look and join the conversation now. http://goparallel.sourceforge.net/
_______________________________________________
Linux-f2fs-devel mailing list
Linux-f2fs-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/linux-f2fs-devel
