Btrfs: Add a lookup cache to the extent state tree
Signed-off-by: Chris Mason <chris.mason@oracle.com>
diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
index 624aabc..5f2fbf2 100644
--- a/fs/btrfs/extent_io.c
+++ b/fs/btrfs/extent_io.c
@@ -90,6 +90,7 @@
tree->mapping = mapping;
INIT_LIST_HEAD(&tree->buffer_lru);
tree->lru_size = 0;
+ tree->last = NULL;
}
EXPORT_SYMBOL(extent_io_tree_init);
@@ -158,16 +159,23 @@
return NULL;
}
-static struct rb_node *__tree_search(struct rb_root *root, u64 offset,
+static struct rb_node *__etree_search(struct extent_io_tree *tree, u64 offset,
struct rb_node **prev_ret,
struct rb_node **next_ret)
{
+ struct rb_root *root = &tree->state;
struct rb_node * n = root->rb_node;
struct rb_node *prev = NULL;
struct rb_node *orig_prev = NULL;
struct tree_entry *entry;
struct tree_entry *prev_entry = NULL;
+ if (tree->last) {
+ struct extent_state *state;
+ state = tree->last;
+ if (state->start <= offset && offset <= state->end)
+ return &tree->last->rb_node;
+ }
while(n) {
entry = rb_entry(n, struct tree_entry, rb_node);
prev = n;
@@ -177,8 +185,10 @@
n = n->rb_left;
else if (offset > entry->end)
n = n->rb_right;
- else
+ else {
+ tree->last = rb_entry(n, struct extent_state, rb_node);
return n;
+ }
}
if (prev_ret) {
@@ -202,14 +212,20 @@
return NULL;
}
-static inline struct rb_node *tree_search(struct rb_root *root, u64 offset)
+static inline struct rb_node *tree_search(struct extent_io_tree *tree,
+ u64 offset)
{
struct rb_node *prev = NULL;
struct rb_node *ret;
- ret = __tree_search(root, offset, &prev, NULL);
- if (!ret)
+ ret = __etree_search(tree, offset, &prev, NULL);
+ if (!ret) {
+ if (prev) {
+ tree->last = rb_entry(prev, struct extent_state,
+ rb_node);
+ }
return prev;
+ }
return ret;
}
@@ -238,6 +254,8 @@
other->state == state->state) {
state->start = other->start;
other->tree = NULL;
+ if (tree->last == other)
+ tree->last = NULL;
rb_erase(&other->rb_node, &tree->state);
free_extent_state(other);
}
@@ -249,6 +267,8 @@
other->state == state->state) {
other->start = state->start;
state->tree = NULL;
+ if (tree->last == state)
+ tree->last = NULL;
rb_erase(&state->rb_node, &tree->state);
free_extent_state(state);
}
@@ -311,6 +331,7 @@
return -EEXIST;
}
state->tree = tree;
+ tree->last = state;
merge_state(tree, state);
return 0;
}
@@ -375,6 +396,8 @@
wake_up(&state->wq);
if (delete || state->state == 0) {
if (state->tree) {
+ if (tree->last == state)
+ tree->last = NULL;
rb_erase(&state->rb_node, &tree->state);
state->tree = NULL;
free_extent_state(state);
@@ -422,7 +445,7 @@
* this search will find the extents that end after
* our range starts
*/
- node = tree_search(&tree->state, start);
+ node = tree_search(tree, start);
if (!node)
goto out;
state = rb_entry(node, struct extent_state, rb_node);
@@ -533,7 +556,7 @@
* this search will find all the extents that end after
* our range starts
*/
- node = tree_search(&tree->state, start);
+ node = tree_search(tree, start);
if (!node)
break;
@@ -612,7 +635,7 @@
* this search will find all the extents that end after
* our range starts.
*/
- node = tree_search(&tree->state, start);
+ node = tree_search(tree, start);
if (!node) {
err = insert_state(tree, prealloc, start, end, bits);
prealloc = NULL;
@@ -915,7 +938,7 @@
* this search will find all the extents that end after
* our range starts.
*/
- node = tree_search(&tree->state, start);
+ node = tree_search(tree, start);
if (!node || IS_ERR(node)) {
goto out;
}
@@ -953,7 +976,7 @@
* our range starts.
*/
search_again:
- node = tree_search(&tree->state, cur_start);
+ node = tree_search(tree, cur_start);
if (!node || IS_ERR(node)) {
*end = (u64)-1;
goto out;
@@ -1041,7 +1064,7 @@
* this search will find all the extents that end after
* our range starts.
*/
- node = tree_search(&tree->state, cur_start);
+ node = tree_search(tree, cur_start);
if (!node || IS_ERR(node)) {
goto out;
}
@@ -1142,7 +1165,7 @@
* this search will find all the extents that end after
* our range starts.
*/
- node = tree_search(&tree->state, start);
+ node = tree_search(tree, start);
if (!node || IS_ERR(node)) {
ret = -ENOENT;
goto out;
@@ -1169,7 +1192,7 @@
* this search will find all the extents that end after
* our range starts.
*/
- node = tree_search(&tree->state, start);
+ node = tree_search(tree, start);
if (!node || IS_ERR(node)) {
ret = -ENOENT;
goto out;
@@ -1200,7 +1223,7 @@
unsigned long flags;
spin_lock_irqsave(&tree->lock, flags);
- node = tree_search(&tree->state, start);
+ node = tree_search(tree, start);
while (node && start <= end) {
state = rb_entry(node, struct extent_state, rb_node);
@@ -1348,7 +1371,7 @@
spin_lock_irqsave(&tree->lock, flags);
if (!state || state->end != end) {
state = NULL;
- node = __tree_search(&tree->state, start, NULL, NULL);
+ node = __etree_search(tree, start, NULL, NULL);
if (node) {
state = rb_entry(node, struct extent_state,
rb_node);
@@ -1468,7 +1491,7 @@
spin_lock_irqsave(&tree->lock, flags);
if (!state || state->end != end) {
state = NULL;
- node = __tree_search(&tree->state, start, NULL, NULL);
+ node = __etree_search(tree, start, NULL, NULL);
if (node) {
state = rb_entry(node, struct extent_state,
rb_node);
@@ -1631,7 +1654,7 @@
end = start + bvec->bv_len - 1;
spin_lock_irq(&tree->lock);
- node = __tree_search(&tree->state, start, NULL, NULL);
+ node = __etree_search(tree, start, NULL, NULL);
BUG_ON(!node);
state = rb_entry(node, struct extent_state, rb_node);
while(state->end < end) {
diff --git a/fs/btrfs/extent_io.h b/fs/btrfs/extent_io.h
index 6fd5e2c..160da3f 100644
--- a/fs/btrfs/extent_io.h
+++ b/fs/btrfs/extent_io.h
@@ -48,6 +48,7 @@
spinlock_t lru_lock;
struct list_head buffer_lru;
int lru_size;
+ struct extent_state *last;
};
struct extent_state {