diff options
| author | Chao Yu <chao2.yu@samsung.com> | 2015-02-05 11:01:39 +0100 |
|---|---|---|
| committer | Jaegeuk Kim <jaegeuk@kernel.org> | 2015-03-03 18:58:47 +0100 |
| commit | 62c8af651b37490c18a42c02586fa6a4fb39320a (patch) | |
| tree | a86e61b8e2d691f54db3208b6e77d25e25b1ec8b /fs | |
| parent | f2fs: add trace for rb-tree extent cache ops (diff) | |
| download | linux-62c8af651b37490c18a42c02586fa6a4fb39320a.tar.xz linux-62c8af651b37490c18a42c02586fa6a4fb39320a.zip | |
f2fs: support fast lookup in extent cache
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.yu@samsung.com>
Signed-off-by: Jaegeuk Kim <jaegeuk@kernel.org>
Diffstat (limited to 'fs')
| -rw-r--r-- | fs/f2fs/data.c | 19 | ||||
| -rw-r--r-- | 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 d7ff4ca5be18..08a71ae3ab8d 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 85ce9b30b539..08fc7e0d5e4a 100644 --- a/fs/f2fs/f2fs.h +++ b/fs/f2fs/f2fs.h @@ -298,6 +298,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*/ |