From patchwork Tue Apr 20 09:21:58 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Shaohua Li X-Patchwork-Id: 93638 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by demeter.kernel.org (8.14.3/8.14.3) with ESMTP id o3K9MAOj018664 for ; Tue, 20 Apr 2010 09:22:10 GMT Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754172Ab0DTJWD (ORCPT ); Tue, 20 Apr 2010 05:22:03 -0400 Received: from mga01.intel.com ([192.55.52.88]:61974 "EHLO mga01.intel.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754153Ab0DTJWA (ORCPT ); Tue, 20 Apr 2010 05:22:00 -0400 Received: from fmsmga002.fm.intel.com ([10.253.24.26]) by fmsmga101.fm.intel.com with ESMTP; 20 Apr 2010 02:20:45 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="4.52,241,1270450800"; d="scan'208";a="559616450" Received: from sli10-conroe.sh.intel.com (HELO sli10-desk.sh.intel.com) ([10.239.36.56]) by fmsmga002.fm.intel.com with ESMTP; 20 Apr 2010 02:21:38 -0700 Received: from david by sli10-desk.sh.intel.com with local (Exim 4.69) (envelope-from ) id 1O49eY-0002rc-TK; Tue, 20 Apr 2010 17:21:58 +0800 Date: Tue, 20 Apr 2010 17:21:58 +0800 From: Shaohua Li To: linux-btrfs@vger.kernel.org Cc: chris.mason@oracle.com Subject: [PATCH]btrfs: speed up extent_io tree search Message-ID: <20100420092158.GA5873@sli10-desk.sh.intel.com> MIME-Version: 1.0 Content-Disposition: inline User-Agent: Mutt/1.5.20 (2009-06-14) Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org X-Greylist: IP, sender and recipient auto-whitelisted, not delayed by milter-greylist-4.2.3 (demeter.kernel.org [140.211.167.41]); Tue, 20 Apr 2010 09:22:10 +0000 (UTC) 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 {