* [PATCH]btrfs: speed up extent_io tree search @ 2010-04-20 9:21 Shaohua Li 2010-04-20 14:39 ` Josef Bacik 0 siblings, 1 reply; 6+ messages in thread From: Shaohua Li @ 2010-04-20 9:21 UTC (permalink / raw) To: linux-btrfs; +Cc: chris.mason searching extent_io_tree is frequently used and tooks a lot of cpu time. We could cache last found extent_state to skip some full search. In my test, the hit rate is from 30% to 70% depending on different workload, which can speed up the search. Signed-off-by: Shaohua Li <shaohua.li@intel.com> diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c index d2d0368..645f00c 100644 --- a/fs/btrfs/extent_io.c +++ b/fs/btrfs/extent_io.c @@ -110,6 +110,7 @@ void extent_io_tree_init(struct extent_io_tree *tree, spin_lock_init(&tree->lock); spin_lock_init(&tree->buffer_lock); tree->mapping = mapping; + tree->cached_state = NULL; } static struct extent_state *alloc_extent_state(gfp_t mask) @@ -135,6 +136,22 @@ static struct extent_state *alloc_extent_state(gfp_t mask) return state; } +static void remove_cached_extent(struct extent_io_tree *tree, + struct extent_state *state) +{ + if (!tree->cached_state) + return; + if (tree->cached_state == state) + tree->cached_state = NULL; +} + +static void merge_cached_extent(struct extent_io_tree *tree, + struct extent_state *first, struct extent_state *last) +{ + if (tree->cached_state == first || tree->cached_state == last) + tree->cached_state = first; +} + static void free_extent_state(struct extent_state *state) { if (!state) @@ -188,6 +205,12 @@ static struct rb_node *__etree_search(struct extent_io_tree *tree, u64 offset, struct rb_node *orig_prev = NULL; struct tree_entry *entry; struct tree_entry *prev_entry = NULL; + struct tree_entry *cached_entry = + (struct tree_entry *)tree->cached_state; + + if (likely(cached_entry && offset >= cached_entry->start && + offset <= cached_entry->end)) + return &cached_entry->rb_node; while (n) { entry = rb_entry(n, struct tree_entry, rb_node); @@ -198,8 +221,10 @@ static struct rb_node *__etree_search(struct extent_io_tree *tree, u64 offset, n = n->rb_left; else if (offset > entry->end) n = n->rb_right; - else + else { + tree->cached_state = (struct extent_state *)entry; return n; + } } if (prev_ret) { @@ -313,6 +338,7 @@ static int merge_state(struct extent_io_tree *tree, merge_cb(tree, state, other); state->start = other->start; other->tree = NULL; + merge_cached_extent(tree, state, other); rb_erase(&other->rb_node, &tree->state); free_extent_state(other); } @@ -325,6 +351,7 @@ static int merge_state(struct extent_io_tree *tree, merge_cb(tree, state, other); other->start = state->start; state->tree = NULL; + merge_cached_extent(tree, other, state); rb_erase(&state->rb_node, &tree->state); free_extent_state(state); state = NULL; @@ -473,6 +500,7 @@ static int clear_state_bit(struct extent_io_tree *tree, wake_up(&state->wq); if (delete || state->state == 0) { if (state->tree) { + remove_cached_extent(tree, state); clear_state_cb(tree, state, state->state); rb_erase(&state->rb_node, &tree->state); state->tree = NULL; diff --git a/fs/btrfs/extent_io.h b/fs/btrfs/extent_io.h index bbab481..e60b367 100644 --- a/fs/btrfs/extent_io.h +++ b/fs/btrfs/extent_io.h @@ -89,6 +89,7 @@ struct extent_io_tree { spinlock_t lock; spinlock_t buffer_lock; struct extent_io_ops *ops; + struct extent_state *cached_state; }; struct extent_state { ^ permalink raw reply related [flat|nested] 6+ messages in thread
* Re: [PATCH]btrfs: speed up extent_io tree search 2010-04-20 9:21 [PATCH]btrfs: speed up extent_io tree search Shaohua Li @ 2010-04-20 14:39 ` Josef Bacik 2010-04-21 1:48 ` Shaohua Li 0 siblings, 1 reply; 6+ messages in thread From: Josef Bacik @ 2010-04-20 14:39 UTC (permalink / raw) To: Shaohua Li; +Cc: linux-btrfs, chris.mason On Tue, Apr 20, 2010 at 05:21:58PM +0800, Shaohua Li wrote: > searching extent_io_tree is frequently used and tooks a lot of cpu time. > We could cache last found extent_state to skip some full search. In my > test, the hit rate is from 30% to 70% depending on different workload, > which can speed up the search. > > Signed-off-by: Shaohua Li <shaohua.li@intel.com> > > diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c > index d2d0368..645f00c 100644 > --- a/fs/btrfs/extent_io.c > +++ b/fs/btrfs/extent_io.c > @@ -110,6 +110,7 @@ void extent_io_tree_init(struct extent_io_tree *tree, > spin_lock_init(&tree->lock); > spin_lock_init(&tree->buffer_lock); > tree->mapping = mapping; > + tree->cached_state = NULL; > } > > static struct extent_state *alloc_extent_state(gfp_t mask) > @@ -135,6 +136,22 @@ static struct extent_state *alloc_extent_state(gfp_t mask) > return state; > } > > +static void remove_cached_extent(struct extent_io_tree *tree, > + struct extent_state *state) > +{ > + if (!tree->cached_state) > + return; > + if (tree->cached_state == state) > + tree->cached_state = NULL; > +} > + > +static void merge_cached_extent(struct extent_io_tree *tree, > + struct extent_state *first, struct extent_state *last) > +{ > + if (tree->cached_state == first || tree->cached_state == last) > + tree->cached_state = first; > +} > + > static void free_extent_state(struct extent_state *state) > { > if (!state) > @@ -188,6 +205,12 @@ static struct rb_node *__etree_search(struct extent_io_tree *tree, u64 offset, > struct rb_node *orig_prev = NULL; > struct tree_entry *entry; > struct tree_entry *prev_entry = NULL; > + struct tree_entry *cached_entry = > + (struct tree_entry *)tree->cached_state; > + > + if (likely(cached_entry && offset >= cached_entry->start && > + offset <= cached_entry->end)) > + return &cached_entry->rb_node; > > while (n) { > entry = rb_entry(n, struct tree_entry, rb_node); > @@ -198,8 +221,10 @@ static struct rb_node *__etree_search(struct extent_io_tree *tree, u64 offset, > n = n->rb_left; > else if (offset > entry->end) > n = n->rb_right; > - else > + else { > + tree->cached_state = (struct extent_state *)entry; > return n; > + } > } > > if (prev_ret) { > @@ -313,6 +338,7 @@ static int merge_state(struct extent_io_tree *tree, > merge_cb(tree, state, other); > state->start = other->start; > other->tree = NULL; > + merge_cached_extent(tree, state, other); > rb_erase(&other->rb_node, &tree->state); > free_extent_state(other); > } > @@ -325,6 +351,7 @@ static int merge_state(struct extent_io_tree *tree, > merge_cb(tree, state, other); > other->start = state->start; > state->tree = NULL; > + merge_cached_extent(tree, other, state); > rb_erase(&state->rb_node, &tree->state); > free_extent_state(state); > state = NULL; > @@ -473,6 +500,7 @@ static int clear_state_bit(struct extent_io_tree *tree, > wake_up(&state->wq); > if (delete || state->state == 0) { > if (state->tree) { > + remove_cached_extent(tree, state); > clear_state_cb(tree, state, state->state); > rb_erase(&state->rb_node, &tree->state); > state->tree = NULL; > diff --git a/fs/btrfs/extent_io.h b/fs/btrfs/extent_io.h > index bbab481..e60b367 100644 > --- a/fs/btrfs/extent_io.h > +++ b/fs/btrfs/extent_io.h > @@ -89,6 +89,7 @@ struct extent_io_tree { > spinlock_t lock; > spinlock_t buffer_lock; > struct extent_io_ops *ops; > + struct extent_state *cached_state; > }; > > struct extent_state { Sorry I saw this earlier but then forgot about it. So instead of doing a per-tree thing, which will end up with misses if somebody else tries to search the tree for a different offset, you will want to do something like this http://git.kernel.org/?p=linux/kernel/git/mason/btrfs-unstable.git;a=commit;h=2ac55d41b5d6bf49e76bc85db5431240617e2f8f So that way _anybody_ who does a search will have a cached state, and so all subsequent searches won't be needed, instead of only working for the first guy who gets their state cached. Thanks, Josef ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH]btrfs: speed up extent_io tree search 2010-04-20 14:39 ` Josef Bacik @ 2010-04-21 1:48 ` Shaohua Li 2010-04-21 2:11 ` Josef Bacik 0 siblings, 1 reply; 6+ messages in thread From: Shaohua Li @ 2010-04-21 1:48 UTC (permalink / raw) To: Josef Bacik; +Cc: linux-btrfs@vger.kernel.org, chris.mason@oracle.com On Tue, Apr 20, 2010 at 10:39:01PM +0800, Josef Bacik wrote: > On Tue, Apr 20, 2010 at 05:21:58PM +0800, Shaohua Li wrote: > > searching extent_io_tree is frequently used and tooks a lot of cpu time. > > We could cache last found extent_state to skip some full search. In my > > test, the hit rate is from 30% to 70% depending on different workload, > > which can speed up the search. > > > > Signed-off-by: Shaohua Li <shaohua.li@intel.com> > > > > diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c > > index d2d0368..645f00c 100644 > > --- a/fs/btrfs/extent_io.c > > +++ b/fs/btrfs/extent_io.c > > @@ -110,6 +110,7 @@ void extent_io_tree_init(struct extent_io_tree *tree, > > spin_lock_init(&tree->lock); > > spin_lock_init(&tree->buffer_lock); > > tree->mapping = mapping; > > + tree->cached_state = NULL; > > } > > > > static struct extent_state *alloc_extent_state(gfp_t mask) > > @@ -135,6 +136,22 @@ static struct extent_state *alloc_extent_state(gfp_t mask) > > return state; > > } > > > > +static void remove_cached_extent(struct extent_io_tree *tree, > > + struct extent_state *state) > > +{ > > + if (!tree->cached_state) > > + return; > > + if (tree->cached_state == state) > > + tree->cached_state = NULL; > > +} > > + > > +static void merge_cached_extent(struct extent_io_tree *tree, > > + struct extent_state *first, struct extent_state *last) > > +{ > > + if (tree->cached_state == first || tree->cached_state == last) > > + tree->cached_state = first; > > +} > > + > > static void free_extent_state(struct extent_state *state) > > { > > if (!state) > > @@ -188,6 +205,12 @@ static struct rb_node *__etree_search(struct extent_io_tree *tree, u64 offset, > > struct rb_node *orig_prev = NULL; > > struct tree_entry *entry; > > struct tree_entry *prev_entry = NULL; > > + struct tree_entry *cached_entry = > > + (struct tree_entry *)tree->cached_state; > > + > > + if (likely(cached_entry && offset >= cached_entry->start && > > + offset <= cached_entry->end)) > > + return &cached_entry->rb_node; > > > > while (n) { > > entry = rb_entry(n, struct tree_entry, rb_node); > > @@ -198,8 +221,10 @@ static struct rb_node *__etree_search(struct extent_io_tree *tree, u64 offset, > > n = n->rb_left; > > else if (offset > entry->end) > > n = n->rb_right; > > - else > > + else { > > + tree->cached_state = (struct extent_state *)entry; > > return n; > > + } > > } > > > > if (prev_ret) { > > @@ -313,6 +338,7 @@ static int merge_state(struct extent_io_tree *tree, > > merge_cb(tree, state, other); > > state->start = other->start; > > other->tree = NULL; > > + merge_cached_extent(tree, state, other); > > rb_erase(&other->rb_node, &tree->state); > > free_extent_state(other); > > } > > @@ -325,6 +351,7 @@ static int merge_state(struct extent_io_tree *tree, > > merge_cb(tree, state, other); > > other->start = state->start; > > state->tree = NULL; > > + merge_cached_extent(tree, other, state); > > rb_erase(&state->rb_node, &tree->state); > > free_extent_state(state); > > state = NULL; > > @@ -473,6 +500,7 @@ static int clear_state_bit(struct extent_io_tree *tree, > > wake_up(&state->wq); > > if (delete || state->state == 0) { > > if (state->tree) { > > + remove_cached_extent(tree, state); > > clear_state_cb(tree, state, state->state); > > rb_erase(&state->rb_node, &tree->state); > > state->tree = NULL; > > diff --git a/fs/btrfs/extent_io.h b/fs/btrfs/extent_io.h > > index bbab481..e60b367 100644 > > --- a/fs/btrfs/extent_io.h > > +++ b/fs/btrfs/extent_io.h > > @@ -89,6 +89,7 @@ struct extent_io_tree { > > spinlock_t lock; > > spinlock_t buffer_lock; > > struct extent_io_ops *ops; > > + struct extent_state *cached_state; > > }; > > > > struct extent_state { > > Sorry I saw this earlier but then forgot about it. So instead of doing a > per-tree thing, which will end up with misses if somebody else tries to search > the tree for a different offset, you will want to do something like this > > http://git.kernel.org/?p=linux/kernel/git/mason/btrfs-unstable.git;a=commit;h=2ac55d41b5d6bf49e76bc85db5431240617e2f8f > > So that way _anybody_ who does a search will have a cached state, and so all > subsequent searches won't be needed, instead of only working for the first guy > who gets their state cached. Thanks, Hmm, the patch you pointed out is already in upstream but I still saw the search takes a lot of CPU. Thanks, Shaohua ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH]btrfs: speed up extent_io tree search 2010-04-21 1:48 ` Shaohua Li @ 2010-04-21 2:11 ` Josef Bacik 2010-04-21 3:10 ` Shaohua Li 0 siblings, 1 reply; 6+ messages in thread From: Josef Bacik @ 2010-04-21 2:11 UTC (permalink / raw) To: Shaohua Li Cc: Josef Bacik, linux-btrfs@vger.kernel.org, chris.mason@oracle.com On Wed, Apr 21, 2010 at 09:48:17AM +0800, Shaohua Li wrote: > On Tue, Apr 20, 2010 at 10:39:01PM +0800, Josef Bacik wrote: > > On Tue, Apr 20, 2010 at 05:21:58PM +0800, Shaohua Li wrote: > > > searching extent_io_tree is frequently used and tooks a lot of cpu time. > > > We could cache last found extent_state to skip some full search. In my > > > test, the hit rate is from 30% to 70% depending on different workload, > > > which can speed up the search. > > > > > > Signed-off-by: Shaohua Li <shaohua.li@intel.com> > > > > > > diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c > > > index d2d0368..645f00c 100644 > > > --- a/fs/btrfs/extent_io.c > > > +++ b/fs/btrfs/extent_io.c > > > @@ -110,6 +110,7 @@ void extent_io_tree_init(struct extent_io_tree *tree, > > > spin_lock_init(&tree->lock); > > > spin_lock_init(&tree->buffer_lock); > > > tree->mapping = mapping; > > > + tree->cached_state = NULL; > > > } > > > > > > static struct extent_state *alloc_extent_state(gfp_t mask) > > > @@ -135,6 +136,22 @@ static struct extent_state *alloc_extent_state(gfp_t mask) > > > return state; > > > } > > > > > > +static void remove_cached_extent(struct extent_io_tree *tree, > > > + struct extent_state *state) > > > +{ > > > + if (!tree->cached_state) > > > + return; > > > + if (tree->cached_state == state) > > > + tree->cached_state = NULL; > > > +} > > > + > > > +static void merge_cached_extent(struct extent_io_tree *tree, > > > + struct extent_state *first, struct extent_state *last) > > > +{ > > > + if (tree->cached_state == first || tree->cached_state == last) > > > + tree->cached_state = first; > > > +} > > > + > > > static void free_extent_state(struct extent_state *state) > > > { > > > if (!state) > > > @@ -188,6 +205,12 @@ static struct rb_node *__etree_search(struct extent_io_tree *tree, u64 offset, > > > struct rb_node *orig_prev = NULL; > > > struct tree_entry *entry; > > > struct tree_entry *prev_entry = NULL; > > > + struct tree_entry *cached_entry = > > > + (struct tree_entry *)tree->cached_state; > > > + > > > + if (likely(cached_entry && offset >= cached_entry->start && > > > + offset <= cached_entry->end)) > > > + return &cached_entry->rb_node; > > > > > > while (n) { > > > entry = rb_entry(n, struct tree_entry, rb_node); > > > @@ -198,8 +221,10 @@ static struct rb_node *__etree_search(struct extent_io_tree *tree, u64 offset, > > > n = n->rb_left; > > > else if (offset > entry->end) > > > n = n->rb_right; > > > - else > > > + else { > > > + tree->cached_state = (struct extent_state *)entry; > > > return n; > > > + } > > > } > > > > > > if (prev_ret) { > > > @@ -313,6 +338,7 @@ static int merge_state(struct extent_io_tree *tree, > > > merge_cb(tree, state, other); > > > state->start = other->start; > > > other->tree = NULL; > > > + merge_cached_extent(tree, state, other); > > > rb_erase(&other->rb_node, &tree->state); > > > free_extent_state(other); > > > } > > > @@ -325,6 +351,7 @@ static int merge_state(struct extent_io_tree *tree, > > > merge_cb(tree, state, other); > > > other->start = state->start; > > > state->tree = NULL; > > > + merge_cached_extent(tree, other, state); > > > rb_erase(&state->rb_node, &tree->state); > > > free_extent_state(state); > > > state = NULL; > > > @@ -473,6 +500,7 @@ static int clear_state_bit(struct extent_io_tree *tree, > > > wake_up(&state->wq); > > > if (delete || state->state == 0) { > > > if (state->tree) { > > > + remove_cached_extent(tree, state); > > > clear_state_cb(tree, state, state->state); > > > rb_erase(&state->rb_node, &tree->state); > > > state->tree = NULL; > > > diff --git a/fs/btrfs/extent_io.h b/fs/btrfs/extent_io.h > > > index bbab481..e60b367 100644 > > > --- a/fs/btrfs/extent_io.h > > > +++ b/fs/btrfs/extent_io.h > > > @@ -89,6 +89,7 @@ struct extent_io_tree { > > > spinlock_t lock; > > > spinlock_t buffer_lock; > > > struct extent_io_ops *ops; > > > + struct extent_state *cached_state; > > > }; > > > > > > struct extent_state { > > > > Sorry I saw this earlier but then forgot about it. So instead of doing a > > per-tree thing, which will end up with misses if somebody else tries to search > > the tree for a different offset, you will want to do something like this > > > > http://git.kernel.org/?p=linux/kernel/git/mason/btrfs-unstable.git;a=commit;h=2ac55d41b5d6bf49e76bc85db5431240617e2f8f > > > > So that way _anybody_ who does a search will have a cached state, and so all > > subsequent searches won't be needed, instead of only working for the first guy > > who gets their state cached. Thanks, > Hmm, the patch you pointed out is already in upstream but I still saw the search > takes a lot of CPU. > I've probably missed some places where we could be using cached extent states, I wasn't terribly thorough when I was checking. It may be good to instrument the cases where we come into test/clear/set bits and we not end up using the cached state to see where the trouble spots are. Thanks, Josef ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH]btrfs: speed up extent_io tree search 2010-04-21 2:11 ` Josef Bacik @ 2010-04-21 3:10 ` Shaohua Li 2010-04-21 13:42 ` Josef Bacik 0 siblings, 1 reply; 6+ messages in thread From: Shaohua Li @ 2010-04-21 3:10 UTC (permalink / raw) To: Josef Bacik; +Cc: linux-btrfs@vger.kernel.org, chris.mason@oracle.com On Wed, Apr 21, 2010 at 10:11:01AM +0800, Josef Bacik wrote: > On Wed, Apr 21, 2010 at 09:48:17AM +0800, Shaohua Li wrote: > > On Tue, Apr 20, 2010 at 10:39:01PM +0800, Josef Bacik wrote: > > > On Tue, Apr 20, 2010 at 05:21:58PM +0800, Shaohua Li wrote: > > > > searching extent_io_tree is frequently used and tooks a lot of cpu time. > > > > We could cache last found extent_state to skip some full search. In my > > > > test, the hit rate is from 30% to 70% depending on different workload, > > > > which can speed up the search. > > > > > > > > Signed-off-by: Shaohua Li <shaohua.li@intel.com> > > > > > > > > diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c > > > > index d2d0368..645f00c 100644 > > > > --- a/fs/btrfs/extent_io.c > > > > +++ b/fs/btrfs/extent_io.c > > > > @@ -110,6 +110,7 @@ void extent_io_tree_init(struct extent_io_tree *tree, > > > > spin_lock_init(&tree->lock); > > > > spin_lock_init(&tree->buffer_lock); > > > > tree->mapping = mapping; > > > > + tree->cached_state = NULL; > > > > } > > > > > > > > static struct extent_state *alloc_extent_state(gfp_t mask) > > > > @@ -135,6 +136,22 @@ static struct extent_state *alloc_extent_state(gfp_t mask) > > > > return state; > > > > } > > > > > > > > +static void remove_cached_extent(struct extent_io_tree *tree, > > > > + struct extent_state *state) > > > > +{ > > > > + if (!tree->cached_state) > > > > + return; > > > > + if (tree->cached_state == state) > > > > + tree->cached_state = NULL; > > > > +} > > > > + > > > > +static void merge_cached_extent(struct extent_io_tree *tree, > > > > + struct extent_state *first, struct extent_state *last) > > > > +{ > > > > + if (tree->cached_state == first || tree->cached_state == last) > > > > + tree->cached_state = first; > > > > +} > > > > + > > > > static void free_extent_state(struct extent_state *state) > > > > { > > > > if (!state) > > > > @@ -188,6 +205,12 @@ static struct rb_node *__etree_search(struct extent_io_tree *tree, u64 offset, > > > > struct rb_node *orig_prev = NULL; > > > > struct tree_entry *entry; > > > > struct tree_entry *prev_entry = NULL; > > > > + struct tree_entry *cached_entry = > > > > + (struct tree_entry *)tree->cached_state; > > > > + > > > > + if (likely(cached_entry && offset >= cached_entry->start && > > > > + offset <= cached_entry->end)) > > > > + return &cached_entry->rb_node; > > > > > > > > while (n) { > > > > entry = rb_entry(n, struct tree_entry, rb_node); > > > > @@ -198,8 +221,10 @@ static struct rb_node *__etree_search(struct extent_io_tree *tree, u64 offset, > > > > n = n->rb_left; > > > > else if (offset > entry->end) > > > > n = n->rb_right; > > > > - else > > > > + else { > > > > + tree->cached_state = (struct extent_state *)entry; > > > > return n; > > > > + } > > > > } > > > > > > > > if (prev_ret) { > > > > @@ -313,6 +338,7 @@ static int merge_state(struct extent_io_tree *tree, > > > > merge_cb(tree, state, other); > > > > state->start = other->start; > > > > other->tree = NULL; > > > > + merge_cached_extent(tree, state, other); > > > > rb_erase(&other->rb_node, &tree->state); > > > > free_extent_state(other); > > > > } > > > > @@ -325,6 +351,7 @@ static int merge_state(struct extent_io_tree *tree, > > > > merge_cb(tree, state, other); > > > > other->start = state->start; > > > > state->tree = NULL; > > > > + merge_cached_extent(tree, other, state); > > > > rb_erase(&state->rb_node, &tree->state); > > > > free_extent_state(state); > > > > state = NULL; > > > > @@ -473,6 +500,7 @@ static int clear_state_bit(struct extent_io_tree *tree, > > > > wake_up(&state->wq); > > > > if (delete || state->state == 0) { > > > > if (state->tree) { > > > > + remove_cached_extent(tree, state); > > > > clear_state_cb(tree, state, state->state); > > > > rb_erase(&state->rb_node, &tree->state); > > > > state->tree = NULL; > > > > diff --git a/fs/btrfs/extent_io.h b/fs/btrfs/extent_io.h > > > > index bbab481..e60b367 100644 > > > > --- a/fs/btrfs/extent_io.h > > > > +++ b/fs/btrfs/extent_io.h > > > > @@ -89,6 +89,7 @@ struct extent_io_tree { > > > > spinlock_t lock; > > > > spinlock_t buffer_lock; > > > > struct extent_io_ops *ops; > > > > + struct extent_state *cached_state; > > > > }; > > > > > > > > struct extent_state { > > > > > > Sorry I saw this earlier but then forgot about it. So instead of doing a > > > per-tree thing, which will end up with misses if somebody else tries to search > > > the tree for a different offset, you will want to do something like this > > > > > > http://git.kernel.org/?p=linux/kernel/git/mason/btrfs-unstable.git;a=commit;h=2ac55d41b5d6bf49e76bc85db5431240617e2f8f > > > > > > So that way _anybody_ who does a search will have a cached state, and so all > > > subsequent searches won't be needed, instead of only working for the first guy > > > who gets their state cached. Thanks, > > Hmm, the patch you pointed out is already in upstream but I still saw the search > > takes a lot of CPU. > > > > I've probably missed some places where we could be using cached extent states, I > wasn't terribly thorough when I was checking. It may be good to instrument the > cases where we come into test/clear/set bits and we not end up using the cached > state to see where the trouble spots are. Thanks, My test basically is in the code path of .readpage/.readpages and .writepage/.writepages. In my first glance of the code, such places look not easily to covert to use your scheme of cached extent states. But I need more check anyway. Thanks, Shaohua ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH]btrfs: speed up extent_io tree search 2010-04-21 3:10 ` Shaohua Li @ 2010-04-21 13:42 ` Josef Bacik 0 siblings, 0 replies; 6+ messages in thread From: Josef Bacik @ 2010-04-21 13:42 UTC (permalink / raw) To: Shaohua Li Cc: Josef Bacik, linux-btrfs@vger.kernel.org, chris.mason@oracle.com On Wed, Apr 21, 2010 at 11:10:46AM +0800, Shaohua Li wrote: > On Wed, Apr 21, 2010 at 10:11:01AM +0800, Josef Bacik wrote: > > On Wed, Apr 21, 2010 at 09:48:17AM +0800, Shaohua Li wrote: > > > On Tue, Apr 20, 2010 at 10:39:01PM +0800, Josef Bacik wrote: > > > > On Tue, Apr 20, 2010 at 05:21:58PM +0800, Shaohua Li wrote: > > > > > searching extent_io_tree is frequently used and tooks a lot of cpu time. > > > > > We could cache last found extent_state to skip some full search. In my > > > > > test, the hit rate is from 30% to 70% depending on different workload, > > > > > which can speed up the search. > > > > > > > > > > Signed-off-by: Shaohua Li <shaohua.li@intel.com> > > > > > > > > > > diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c > > > > > index d2d0368..645f00c 100644 > > > > > --- a/fs/btrfs/extent_io.c > > > > > +++ b/fs/btrfs/extent_io.c > > > > > @@ -110,6 +110,7 @@ void extent_io_tree_init(struct extent_io_tree *tree, > > > > > spin_lock_init(&tree->lock); > > > > > spin_lock_init(&tree->buffer_lock); > > > > > tree->mapping = mapping; > > > > > + tree->cached_state = NULL; > > > > > } > > > > > > > > > > static struct extent_state *alloc_extent_state(gfp_t mask) > > > > > @@ -135,6 +136,22 @@ static struct extent_state *alloc_extent_state(gfp_t mask) > > > > > return state; > > > > > } > > > > > > > > > > +static void remove_cached_extent(struct extent_io_tree *tree, > > > > > + struct extent_state *state) > > > > > +{ > > > > > + if (!tree->cached_state) > > > > > + return; > > > > > + if (tree->cached_state == state) > > > > > + tree->cached_state = NULL; > > > > > +} > > > > > + > > > > > +static void merge_cached_extent(struct extent_io_tree *tree, > > > > > + struct extent_state *first, struct extent_state *last) > > > > > +{ > > > > > + if (tree->cached_state == first || tree->cached_state == last) > > > > > + tree->cached_state = first; > > > > > +} > > > > > + > > > > > static void free_extent_state(struct extent_state *state) > > > > > { > > > > > if (!state) > > > > > @@ -188,6 +205,12 @@ static struct rb_node *__etree_search(struct extent_io_tree *tree, u64 offset, > > > > > struct rb_node *orig_prev = NULL; > > > > > struct tree_entry *entry; > > > > > struct tree_entry *prev_entry = NULL; > > > > > + struct tree_entry *cached_entry = > > > > > + (struct tree_entry *)tree->cached_state; > > > > > + > > > > > + if (likely(cached_entry && offset >= cached_entry->start && > > > > > + offset <= cached_entry->end)) > > > > > + return &cached_entry->rb_node; > > > > > > > > > > while (n) { > > > > > entry = rb_entry(n, struct tree_entry, rb_node); > > > > > @@ -198,8 +221,10 @@ static struct rb_node *__etree_search(struct extent_io_tree *tree, u64 offset, > > > > > n = n->rb_left; > > > > > else if (offset > entry->end) > > > > > n = n->rb_right; > > > > > - else > > > > > + else { > > > > > + tree->cached_state = (struct extent_state *)entry; > > > > > return n; > > > > > + } > > > > > } > > > > > > > > > > if (prev_ret) { > > > > > @@ -313,6 +338,7 @@ static int merge_state(struct extent_io_tree *tree, > > > > > merge_cb(tree, state, other); > > > > > state->start = other->start; > > > > > other->tree = NULL; > > > > > + merge_cached_extent(tree, state, other); > > > > > rb_erase(&other->rb_node, &tree->state); > > > > > free_extent_state(other); > > > > > } > > > > > @@ -325,6 +351,7 @@ static int merge_state(struct extent_io_tree *tree, > > > > > merge_cb(tree, state, other); > > > > > other->start = state->start; > > > > > state->tree = NULL; > > > > > + merge_cached_extent(tree, other, state); > > > > > rb_erase(&state->rb_node, &tree->state); > > > > > free_extent_state(state); > > > > > state = NULL; > > > > > @@ -473,6 +500,7 @@ static int clear_state_bit(struct extent_io_tree *tree, > > > > > wake_up(&state->wq); > > > > > if (delete || state->state == 0) { > > > > > if (state->tree) { > > > > > + remove_cached_extent(tree, state); > > > > > clear_state_cb(tree, state, state->state); > > > > > rb_erase(&state->rb_node, &tree->state); > > > > > state->tree = NULL; > > > > > diff --git a/fs/btrfs/extent_io.h b/fs/btrfs/extent_io.h > > > > > index bbab481..e60b367 100644 > > > > > --- a/fs/btrfs/extent_io.h > > > > > +++ b/fs/btrfs/extent_io.h > > > > > @@ -89,6 +89,7 @@ struct extent_io_tree { > > > > > spinlock_t lock; > > > > > spinlock_t buffer_lock; > > > > > struct extent_io_ops *ops; > > > > > + struct extent_state *cached_state; > > > > > }; > > > > > > > > > > struct extent_state { > > > > > > > > Sorry I saw this earlier but then forgot about it. So instead of doing a > > > > per-tree thing, which will end up with misses if somebody else tries to search > > > > the tree for a different offset, you will want to do something like this > > > > > > > > http://git.kernel.org/?p=linux/kernel/git/mason/btrfs-unstable.git;a=commit;h=2ac55d41b5d6bf49e76bc85db5431240617e2f8f > > > > > > > > So that way _anybody_ who does a search will have a cached state, and so all > > > > subsequent searches won't be needed, instead of only working for the first guy > > > > who gets their state cached. Thanks, > > > Hmm, the patch you pointed out is already in upstream but I still saw the search > > > takes a lot of CPU. > > > > > > > I've probably missed some places where we could be using cached extent states, I > > wasn't terribly thorough when I was checking. It may be good to instrument the > > cases where we come into test/clear/set bits and we not end up using the cached > > state to see where the trouble spots are. Thanks, > My test basically is in the code path of .readpage/.readpages and > .writepage/.writepages. In my first glance of the code, such places look not easily > to covert to use your scheme of cached extent states. But I need more check anyway. > Hmm I see your point. I guess this doesn't mess with anybody that already uses the cached state stuff, and if it helps out in these more complicated cases then I guess thats good enough. Acked-by: Josef Bacik <josef@redhat.com> Thanks, Josef ^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2010-04-21 13:42 UTC | newest] Thread overview: 6+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2010-04-20 9:21 [PATCH]btrfs: speed up extent_io tree search Shaohua Li 2010-04-20 14:39 ` Josef Bacik 2010-04-21 1:48 ` Shaohua Li 2010-04-21 2:11 ` Josef Bacik 2010-04-21 3:10 ` Shaohua Li 2010-04-21 13:42 ` Josef Bacik
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).