Skip to contentSkip to conversation

Btrfs: more efficient split extent state insertion

PATCH Superseded Filipe David Borba Manana 1 participant 2 messages Feb 12, 2014 – Feb 24, 2014 Btrfs file system

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 Btrfs: more efficient split extent state insertion

When we split an extent state there's no need to start the rbtree search from the root node - we can start it from the original extent state node, since we would end up in its subtree if we do the search starting at the root node anyway.

---
 fs/btrfs/extent_io.c |   13 ++++++++-----
 1 file changed, 8 insertions(+), 5 deletions(-)
fs/btrfs/extent_io.c +8 -5
index fbe501d..f01993b 100644
@@ -229,12 +229,14 @@ void free_extent_state(struct extent_state *state)
 	}
 }
 
-static struct rb_node *tree_insert(struct rb_root *root, u64 offset,
+static struct rb_node *tree_insert(struct rb_root *root,
+				   struct rb_node *search_start,
+				   u64 offset,
 				   struct rb_node *node,
 				   struct rb_node ***p_in,
 				   struct rb_node **parent_in)
 {
-	struct rb_node **p = &root->rb_node;
+	struct rb_node **p = &search_start;
 	struct rb_node *parent = NULL;
 	struct tree_entry *entry;
 
@@ -430,7 +432,8 @@ static int insert_state(struct extent_io_tree *tree,
 
 	set_state_bits(tree, state, bits);
 
-	node = tree_insert(&tree->state, end, &state->rb_node, p, parent);
+	node = tree_insert(&tree->state, tree->state.rb_node, end,
+			   &state->rb_node, p, parent);
 	if (node) {
 		struct extent_state *found;
 		found = rb_entry(node, struct extent_state, rb_node);
@@ -477,8 +480,8 @@ static int split_state(struct extent_io_tree *tree, struct extent_state *orig,
 	prealloc->state = orig->state;
 	orig->start = split;
 
-	node = tree_insert(&tree->state, prealloc->end, &prealloc->rb_node,
-			   NULL, NULL);
+	node = tree_insert(&tree->state, &orig->rb_node, prealloc->end,
+			   &prealloc->rb_node, NULL, NULL);
 	if (node) {
 		free_extent_state(prealloc);
 		return -EEXIST;
Signature · 1 line
1.7.9.5
#1 lore raw

PATCH v2 1/1 Btrfs: more efficient split extent state insertion

When we split an extent state there's no need to start the rbtree search from the root node - we can start it from the original extent state node, since we would end up in its subtree if we do the search starting at the root node anyway.

---

V2: Made the intention more clear, that it works only if the tree is not
empty (which is always the case when spliting extent states).

 fs/btrfs/extent_io.c |   13 ++++++++-----
 1 file changed, 8 insertions(+), 5 deletions(-)
fs/btrfs/extent_io.c +8 -5
index fbe501d..eb465e9 100644
@@ -229,12 +229,14 @@ void free_extent_state(struct extent_state *state)
 	}
 }
 
-static struct rb_node *tree_insert(struct rb_root *root, u64 offset,
+static struct rb_node *tree_insert(struct rb_root *root,
+				   struct rb_node *search_start,
+				   u64 offset,
 				   struct rb_node *node,
 				   struct rb_node ***p_in,
 				   struct rb_node **parent_in)
 {
-	struct rb_node **p = &root->rb_node;
+	struct rb_node **p;
 	struct rb_node *parent = NULL;
 	struct tree_entry *entry;
 
@@ -244,6 +246,7 @@ static struct rb_node *tree_insert(struct rb_root *root, u64 offset,
 		goto do_insert;
 	}
 
+	p = search_start ? &search_start : &root->rb_node;
 	while (*p) {
 		parent = *p;
 		entry = rb_entry(parent, struct tree_entry, rb_node);
@@ -430,7 +433,7 @@ static int insert_state(struct extent_io_tree *tree,
 
 	set_state_bits(tree, state, bits);
 
-	node = tree_insert(&tree->state, end, &state->rb_node, p, parent);
+	node = tree_insert(&tree->state, NULL, end, &state->rb_node, p, parent);
 	if (node) {
 		struct extent_state *found;
 		found = rb_entry(node, struct extent_state, rb_node);
@@ -477,8 +480,8 @@ static int split_state(struct extent_io_tree *tree, struct extent_state *orig,
 	prealloc->state = orig->state;
 	orig->start = split;
 
-	node = tree_insert(&tree->state, prealloc->end, &prealloc->rb_node,
-			   NULL, NULL);
+	node = tree_insert(&tree->state, &orig->rb_node, prealloc->end,
+			   &prealloc->rb_node, NULL, NULL);
 	if (node) {
 		free_extent_state(prealloc);
 		return -EEXIST;
Signature · 1 line
1.7.9.5