Skip to contentSkip to conversation

Extent tree search cleanups

PATCH In review David Sterba 3 participants 17 messages Jun 8, 2022 – Jun 17, 2022 Btrfs file system

lore
Share & tools
lore

David Sterba

author maintainer
#0 lore raw

cover Extent tree search cleanups

The extent_io_tree search helpers take return parameters and many callers pass just NULL, which are checked and add a conditionals to some paths. Reorganize helpers to suit what callers need and drop unnecessary parameters, open code rbtree search loops and clean up some other parameters.

This could improve performance in some cases but it's mostly micro optimizations and I haven't done any measurements.

David Sterba (9):
btrfs: open code rbtree search into split_state
btrfs: open code rbtree search in insert_state
btrfs: lift start and end parameters to callers of insert_state
btrfs: pass bits by value not pointer for extent_state helpers
btrfs: add fast path for extent_state insertion
btrfs: remove node and parent parameters from insert_state
btrfs: open code inexact rbtree search in tree_search
btrfs: make tree search for insert more generic and use it for
tree_search
btrfs: unify tree search helper returning prev and next nodes

 fs/btrfs/ctree.h     |   4 +-
 fs/btrfs/extent_io.c | 316 +++++++++++++++++++++++--------------------
 fs/btrfs/inode.c     |  24 ++--
 3 files changed, 183 insertions(+), 161 deletions(-)
Signature · 1 line
2.36.1
author maintainer
#1 lore raw

PATCH 1/9 btrfs: open code rbtree search into split_state

Preparatory work to remove tree_insert from extent_io.c, the rbtree search loop is a known and simple so it can be open coded.

---
 fs/btrfs/extent_io.c | 28 ++++++++++++++++++++++------
 1 file changed, 22 insertions(+), 6 deletions(-)
fs/btrfs/extent_io.c +22 -6
index 9fd114683027..c39f8674b6ce 100644
@@ -607,7 +607,8 @@ static int insert_state(struct extent_io_tree *tree,
 static int split_state(struct extent_io_tree *tree, struct extent_state *orig,
 		       struct extent_state *prealloc, u64 split)
 {
-	struct rb_node *node;
+	struct rb_node *parent = NULL;
+	struct rb_node **node;
 
 	if (tree->private_data && is_data_inode(tree->private_data))
 		btrfs_split_delalloc_extent(tree->private_data, orig, split);
@@ -617,12 +618,27 @@ 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, &orig->rb_node, prealloc->end,
-			   &prealloc->rb_node, NULL, NULL);
-	if (node) {
-		free_extent_state(prealloc);
-		return -EEXIST;
+	parent = &orig->rb_node;
+	node = &parent;
+	while (*node) {
+		struct tree_entry *entry;
+
+		parent = *node;
+		entry = rb_entry(parent, struct tree_entry, rb_node);
+
+		if (prealloc->end < entry->start) {
+			node = &(*node)->rb_left;
+		} else if (prealloc->end > entry->end) {
+			node = &(*node)->rb_right;
+		} else {
+			free_extent_state(prealloc);
+			return -EEXIST;
+		}
 	}
+
+	rb_link_node(&prealloc->rb_node, parent, node);
+	rb_insert_color(&prealloc->rb_node, &tree->state);
+
 	return 0;
 }
 
Signature · 1 line
2.36.1
author maintainer
#2 lore raw

PATCH 2/9 btrfs: open code rbtree search in insert_state

In reply to David Sterba

The rbtree search is a known pattern and can be open coded, allowing to remove the tree_insert and further cleanups.

---
 fs/btrfs/extent_io.c | 80 ++++++++++++++++++--------------------------
 1 file changed, 33 insertions(+), 47 deletions(-)
fs/btrfs/extent_io.c +33 -47
index c39f8674b6ce..429096fc8899 100644
@@ -368,42 +368,6 @@ void free_extent_state(struct extent_state *state)
 	}
 }
 
-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;
-	struct rb_node *parent = NULL;
-	struct tree_entry *entry;
-
-	if (p_in && parent_in) {
-		p = *p_in;
-		parent = *parent_in;
-		goto do_insert;
-	}
-
-	p = search_start ? &search_start : &root->rb_node;
-	while (*p) {
-		parent = *p;
-		entry = rb_entry(parent, struct tree_entry, rb_node);
-
-		if (offset < entry->start)
-			p = &(*p)->rb_left;
-		else if (offset > entry->end)
-			p = &(*p)->rb_right;
-		else
-			return parent;
-	}
-
-do_insert:
-	rb_link_node(node, parent, p);
-	rb_insert_color(node, root);
-	return NULL;
-}
-
 /**
  * Search @tree for an entry that contains @offset. Such entry would have
  * entry->start <= offset && entry->end >= offset.
@@ -561,11 +525,12 @@ static void set_state_bits(struct extent_io_tree *tree,
  */
 static int insert_state(struct extent_io_tree *tree,
 			struct extent_state *state, u64 start, u64 end,
-			struct rb_node ***p,
-			struct rb_node **parent,
+			struct rb_node ***node_in,
+			struct rb_node **parent_in,
 			u32 *bits, struct extent_changeset *changeset)
 {
-	struct rb_node *node;
+	struct rb_node **node;
+	struct rb_node *parent;
 
 	if (end < start) {
 		btrfs_err(tree->fs_info,
@@ -577,15 +542,36 @@ static int insert_state(struct extent_io_tree *tree,
 
 	set_state_bits(tree, state, bits, changeset);
 
-	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);
-		btrfs_err(tree->fs_info,
-		       "found node %llu %llu on insert of %llu %llu",
-		       found->start, found->end, start, end);
-		return -EEXIST;
+	/* Caller provides the exact tree location */
+	if (node_in && parent_in) {
+		node = *node_in;
+		parent = *parent_in;
+		goto insert_new;
 	}
+
+	node = &tree->state.rb_node;
+	while (*node) {
+		struct tree_entry *entry;
+
+		parent = *node;
+		entry = rb_entry(parent, struct tree_entry, rb_node);
+
+		if (end < entry->start) {
+			node = &(*node)->rb_left;
+		} else if (end > entry->end) {
+			node = &(*node)->rb_right;
+		} else {
+			btrfs_err(tree->fs_info,
+			       "found node %llu %llu on insert of %llu %llu",
+			       entry->start, entry->end, start, end);
+			return -EEXIST;
+		}
+	}
+
+insert_new:
+	rb_link_node(&state->rb_node, parent, node);
+	rb_insert_color(&state->rb_node, &tree->state);
+
 	merge_state(tree, state);
 	return 0;
 }
Signature · 1 line
2.36.1
author maintainer
#3 lore raw

PATCH 3/9 btrfs: lift start and end parameters to callers of insert_state

In reply to David Sterba

Let callers of insert_state to set up the extent state to allow further simplifications of the parameters.

---
 fs/btrfs/extent_io.c | 33 +++++++++++++++------------------
 1 file changed, 15 insertions(+), 18 deletions(-)
fs/btrfs/extent_io.c +15 -18
index 429096fc8899..1411286e5ef2 100644
@@ -524,21 +524,14 @@ static void set_state_bits(struct extent_io_tree *tree,
  * probably isn't what you want to call (see set/clear_extent_bit).
  */
 static int insert_state(struct extent_io_tree *tree,
-			struct extent_state *state, u64 start, u64 end,
+			struct extent_state *state,
 			struct rb_node ***node_in,
 			struct rb_node **parent_in,
 			u32 *bits, struct extent_changeset *changeset)
 {
 	struct rb_node **node;
 	struct rb_node *parent;
-
-	if (end < start) {
-		btrfs_err(tree->fs_info,
-			"insert state: end < start %llu %llu", end, start);
-		WARN_ON(1);
-	}
-	state->start = start;
-	state->end = end;
+	const u64 end = state->end;
 
 	set_state_bits(tree, state, bits, changeset);
 
@@ -563,7 +556,7 @@ static int insert_state(struct extent_io_tree *tree,
 		} else {
 			btrfs_err(tree->fs_info,
 			       "found node %llu %llu on insert of %llu %llu",
-			       entry->start, entry->end, start, end);
+			       entry->start, entry->end, state->start, end);
 			return -EEXIST;
 		}
 	}
@@ -1027,8 +1020,9 @@ int set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, u32 bits,
 	if (!node) {
 		prealloc = alloc_extent_state_atomic(prealloc);
 		BUG_ON(!prealloc);
-		err = insert_state(tree, prealloc, start, end,
-				   &p, &parent, &bits, changeset);
+		prealloc->start = start;
+		prealloc->end = end;
+		err = insert_state(tree, prealloc, &p, &parent, &bits, changeset);
 		if (err)
 			extent_io_tree_panic(tree, err);
 
@@ -1144,8 +1138,9 @@ int set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, u32 bits,
 		 * Avoid to free 'prealloc' if it can be merged with
 		 * the later extent.
 		 */
-		err = insert_state(tree, prealloc, start, this_end,
-				   NULL, NULL, &bits, changeset);
+		prealloc->start = start;
+		prealloc->end = this_end;
+		err = insert_state(tree, prealloc, NULL, NULL, &bits, changeset);
 		if (err)
 			extent_io_tree_panic(tree, err);
 
@@ -1268,8 +1263,9 @@ int convert_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
 			err = -ENOMEM;
 			goto out;
 		}
-		err = insert_state(tree, prealloc, start, end,
-				   &p, &parent, &bits, NULL);
+		prealloc->start = start;
+		prealloc->end = end;
+		err = insert_state(tree, prealloc, &p, &parent, &bits, NULL);
 		if (err)
 			extent_io_tree_panic(tree, err);
 		cache_state(prealloc, cached_state);
@@ -1366,8 +1362,9 @@ int convert_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
 		 * Avoid to free 'prealloc' if it can be merged with
 		 * the later extent.
 		 */
-		err = insert_state(tree, prealloc, start, this_end,
-				   NULL, NULL, &bits, NULL);
+		prealloc->start = start;
+		prealloc->end = this_end;
+		err = insert_state(tree, prealloc, NULL, NULL, &bits, NULL);
 		if (err)
 			extent_io_tree_panic(tree, err);
 		cache_state(prealloc, cached_state);
Signature · 1 line
2.36.1
author maintainer
#6 lore raw

PATCH 4/9 btrfs: pass bits by value not pointer for extent_state helpers

In reply to David Sterba

The bits are passed to all extent state helpers for not apparent reason, the value only read and never updated so remove the indirection and pass directly. Also unify the type to u32 where needed.

---
 fs/btrfs/ctree.h     |  4 ++--
 fs/btrfs/extent_io.c | 46 +++++++++++++++++++++-----------------------
 fs/btrfs/inode.c     | 24 +++++++++++------------
 3 files changed, 36 insertions(+), 38 deletions(-)
fs/btrfs/ctree.h +2 -2
index f7afdfd0bae7..13d74948c542 100644
@@ -3320,9 +3320,9 @@ void btrfs_new_inode_args_destroy(struct btrfs_new_inode_args *args);
 struct inode *btrfs_new_subvol_inode(struct user_namespace *mnt_userns,
 				     struct inode *dir);
  void btrfs_set_delalloc_extent(struct inode *inode, struct extent_state *state,
-			       unsigned *bits);
+			        u32 bits);
 void btrfs_clear_delalloc_extent(struct inode *inode,
-				 struct extent_state *state, unsigned *bits);
+				 struct extent_state *state, u32 bits);
 void btrfs_merge_delalloc_extent(struct inode *inode, struct extent_state *new,
 				 struct extent_state *other);
 void btrfs_split_delalloc_extent(struct inode *inode,
fs/btrfs/extent_io.c +22 -24

154 lines not on this page · raw message

fs/btrfs/inode.c +12 -12
index 7a54f964ff37..33ba4d22e143 100644
@@ -2274,18 +2274,18 @@ static void btrfs_del_delalloc_inode(struct btrfs_root *root,
  * list of inodes that have pending delalloc work to be done.
  */
 void btrfs_set_delalloc_extent(struct inode *inode, struct extent_state *state,
-			       unsigned *bits)
+			       u32 bits)
 {
 	struct btrfs_fs_info *fs_info = btrfs_sb(inode->i_sb);
 
-	if ((*bits & EXTENT_DEFRAG) && !(*bits & EXTENT_DELALLOC))
+	if ((bits & EXTENT_DEFRAG) && !(bits & EXTENT_DELALLOC))
 		WARN_ON(1);
 	/*
 	 * set_bit and clear bit hooks normally require _irqsave/restore
 	 * but in this case, we are only testing for the DELALLOC
 	 * bit, which is only set or cleared with irqs on
 	 */
-	if (!(state->state & EXTENT_DELALLOC) && (*bits & EXTENT_DELALLOC)) {
+	if (!(state->state & EXTENT_DELALLOC) && (bits & EXTENT_DELALLOC)) {
 		struct btrfs_root *root = BTRFS_I(inode)->root;
 		u64 len = state->end + 1 - state->start;
 		u32 num_extents = count_max_extents(len);
@@ -2303,7 +2303,7 @@ void btrfs_set_delalloc_extent(struct inode *inode, struct extent_state *state,
 					 fs_info->delalloc_batch);
 		spin_lock(&BTRFS_I(inode)->lock);
 		BTRFS_I(inode)->delalloc_bytes += len;
-		if (*bits & EXTENT_DEFRAG)
+		if (bits & EXTENT_DEFRAG)
 			BTRFS_I(inode)->defrag_bytes += len;
 		if (do_list && !test_bit(BTRFS_INODE_IN_DELALLOC_LIST,
 					 &BTRFS_I(inode)->runtime_flags))
@@ -2312,7 +2312,7 @@ void btrfs_set_delalloc_extent(struct inode *inode, struct extent_state *state,
 	}
 
 	if (!(state->state & EXTENT_DELALLOC_NEW) &&
-	    (*bits & EXTENT_DELALLOC_NEW)) {
+	    (bits & EXTENT_DELALLOC_NEW)) {
 		spin_lock(&BTRFS_I(inode)->lock);
 		BTRFS_I(inode)->new_delalloc_bytes += state->end + 1 -
 			state->start;
@@ -2325,14 +2325,14 @@ void btrfs_set_delalloc_extent(struct inode *inode, struct extent_state *state,
  * accounting happens.
  */
 void btrfs_clear_delalloc_extent(struct inode *vfs_inode,
-				 struct extent_state *state, unsigned *bits)
+				 struct extent_state *state, u32 bits)
 {
 	struct btrfs_inode *inode = BTRFS_I(vfs_inode);
 	struct btrfs_fs_info *fs_info = btrfs_sb(vfs_inode->i_sb);
 	u64 len = state->end + 1 - state->start;
 	u32 num_extents = count_max_extents(len);
 
-	if ((state->state & EXTENT_DEFRAG) && (*bits & EXTENT_DEFRAG)) {
+	if ((state->state & EXTENT_DEFRAG) && (bits & EXTENT_DEFRAG)) {
 		spin_lock(&inode->lock);
 		inode->defrag_bytes -= len;
 		spin_unlock(&inode->lock);
@@ -2343,7 +2343,7 @@ void btrfs_clear_delalloc_extent(struct inode *vfs_inode,
 	 * but in this case, we are only testing for the DELALLOC
 	 * bit, which is only set or cleared with irqs on
 	 */
-	if ((state->state & EXTENT_DELALLOC) && (*bits & EXTENT_DELALLOC)) {
+	if ((state->state & EXTENT_DELALLOC) && (bits & EXTENT_DELALLOC)) {
 		struct btrfs_root *root = inode->root;
 		bool do_list = !btrfs_is_free_space_inode(inode);
 
@@ -2356,7 +2356,7 @@ void btrfs_clear_delalloc_extent(struct inode *vfs_inode,
 		 * don't need to call delalloc_release_metadata if there is an
 		 * error.
 		 */
-		if (*bits & EXTENT_CLEAR_META_RESV &&
+		if (bits & EXTENT_CLEAR_META_RESV &&
 		    root != fs_info->tree_root)
 			btrfs_delalloc_release_metadata(inode, len, false);
 
@@ -2366,7 +2366,7 @@ void btrfs_clear_delalloc_extent(struct inode *vfs_inode,
 
 		if (!btrfs_is_data_reloc_root(root) &&
 		    do_list && !(state->state & EXTENT_NORESERVE) &&
-		    (*bits & EXTENT_CLEAR_DATA_RESV))
+		    (bits & EXTENT_CLEAR_DATA_RESV))
 			btrfs_free_reserved_data_space_noquota(fs_info, len);
 
 		percpu_counter_add_batch(&fs_info->delalloc_bytes, -len,
@@ -2381,11 +2381,11 @@ void btrfs_clear_delalloc_extent(struct inode *vfs_inode,
 	}
 
 	if ((state->state & EXTENT_DELALLOC_NEW) &&
-	    (*bits & EXTENT_DELALLOC_NEW)) {
+	    (bits & EXTENT_DELALLOC_NEW)) {
 		spin_lock(&inode->lock);
 		ASSERT(inode->new_delalloc_bytes >= len);
 		inode->new_delalloc_bytes -= len;
-		if (*bits & EXTENT_ADD_INODE_BYTES)
+		if (bits & EXTENT_ADD_INODE_BYTES)
 			inode_add_bytes(&inode->vfs_inode, len);
 		spin_unlock(&inode->lock);
 	}
Signature · 1 line
2.36.1
author maintainer
#7 lore raw

PATCH 5/9 btrfs: add fast path for extent_state insertion

In reply to David Sterba

In two cases the exact location where to insert the extent state is known at the call time so we don't need to pass it to insert_state that takes the fast path.

---
 fs/btrfs/extent_io.c | 24 +++++++++++++++++-------
 1 file changed, 17 insertions(+), 7 deletions(-)
fs/btrfs/extent_io.c +17 -7
index 9b1dfe4363c9..00a6a2d0b112 100644
@@ -569,6 +569,21 @@ static int insert_state(struct extent_io_tree *tree,
 	return 0;
 }
 
+/*
+ * Insert state to the tree to a location given by @p_
+ */
+static void insert_state_fast(struct extent_io_tree *tree,
+			struct extent_state *state,
+			struct rb_node **node,
+			struct rb_node *parent,
+			unsigned bits, struct extent_changeset *changeset)
+{
+	set_state_bits(tree, state, bits, changeset);
+	rb_link_node(&state->rb_node, parent, node);
+	rb_insert_color(&state->rb_node, &tree->state);
+	merge_state(tree, state);
+}
+
 /*
  * split a given extent state struct in two, inserting the preallocated
  * struct 'prealloc' as the newly created second half.  'split' indicates an
@@ -1021,10 +1036,7 @@ int set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, u32 bits,
 		BUG_ON(!prealloc);
 		prealloc->start = start;
 		prealloc->end = end;
-		err = insert_state(tree, prealloc, &p, &parent, bits, changeset);
-		if (err)
-			extent_io_tree_panic(tree, err);
-
+		insert_state_fast(tree, prealloc, p, parent, bits, changeset);
 		cache_state(prealloc, cached_state);
 		prealloc = NULL;
 		goto out;
@@ -1264,9 +1276,7 @@ int convert_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
 		}
 		prealloc->start = start;
 		prealloc->end = end;
-		err = insert_state(tree, prealloc, &p, &parent, bits, NULL);
-		if (err)
-			extent_io_tree_panic(tree, err);
+		insert_state_fast(tree, prealloc, p, parent, bits, NULL);
 		cache_state(prealloc, cached_state);
 		prealloc = NULL;
 		goto out;
Signature · 1 line
2.36.1
author maintainer
#10 lore raw

PATCH 6/9 btrfs: remove node and parent parameters from insert_state

In reply to David Sterba

There's no caller left that would pass valid pointers to insert_state so we can drop them.

---
 fs/btrfs/extent_io.c | 14 ++------------
 1 file changed, 2 insertions(+), 12 deletions(-)
fs/btrfs/extent_io.c +2 -12
index 00a6a2d0b112..b7d6f2dc4706 100644
@@ -525,8 +525,6 @@ static void set_state_bits(struct extent_io_tree *tree,
  */
 static int insert_state(struct extent_io_tree *tree,
 			struct extent_state *state,
-			struct rb_node ***node_in,
-			struct rb_node **parent_in,
 			u32 bits, struct extent_changeset *changeset)
 {
 	struct rb_node **node;
@@ -535,13 +533,6 @@ static int insert_state(struct extent_io_tree *tree,
 
 	set_state_bits(tree, state, bits, changeset);
 
-	/* Caller provides the exact tree location */
-	if (node_in && parent_in) {
-		node = *node_in;
-		parent = *parent_in;
-		goto insert_new;
-	}
-
 	node = &tree->state.rb_node;
 	while (*node) {
 		struct tree_entry *entry;
@@ -561,7 +552,6 @@ static int insert_state(struct extent_io_tree *tree,
 		}
 	}
 
-insert_new:
 	rb_link_node(&state->rb_node, parent, node);
 	rb_insert_color(&state->rb_node, &tree->state);
 
@@ -1151,7 +1141,7 @@ int set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, u32 bits,
 		 */
 		prealloc->start = start;
 		prealloc->end = this_end;
-		err = insert_state(tree, prealloc, NULL, NULL, bits, changeset);
+		err = insert_state(tree, prealloc, bits, changeset);
 		if (err)
 			extent_io_tree_panic(tree, err);
 
@@ -1372,7 +1362,7 @@ int convert_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
 		 */
 		prealloc->start = start;
 		prealloc->end = this_end;
-		err = insert_state(tree, prealloc, NULL, NULL, bits, NULL);
+		err = insert_state(tree, prealloc, bits, NULL);
 		if (err)
 			extent_io_tree_panic(tree, err);
 		cache_state(prealloc, cached_state);
Signature · 1 line
2.36.1
author maintainer
#11 lore raw

PATCH 7/9 btrfs: open code inexact rbtree search in tree_search

In reply to David Sterba

The call chain from

tree_search
tree_search_for_insert
__etree_search

can be open coded and allow further simplifications, here we need a tree search with fallback to the next node in case it's not found. This is represented as __etree_search parameters next_ret=valid, prev_ret=NULL.

---
 fs/btrfs/extent_io.c | 31 ++++++++++++++++++++++++++++---
 1 file changed, 28 insertions(+), 3 deletions(-)
fs/btrfs/extent_io.c +28 -3
index b7d6f2dc4706..de0bd32d99e0 100644
@@ -453,10 +453,35 @@ tree_search_for_insert(struct extent_io_tree *tree,
 	return ret;
 }
 
-static inline struct rb_node *tree_search(struct extent_io_tree *tree,
-					  u64 offset)
+/*
+ * Inexact rb-tree search, return the next entry if @offset is not found
+ */
+static inline struct rb_node *tree_search(struct extent_io_tree *tree, u64 offset)
 {
-	return tree_search_for_insert(tree, offset, NULL, NULL);
+	struct rb_root *root = &tree->state;
+	struct rb_node **node = &root->rb_node;
+	struct rb_node *prev = NULL;
+	struct tree_entry *entry;
+
+	while (*node) {
+		prev = *node;
+		entry = rb_entry(prev, struct tree_entry, rb_node);
+
+		if (offset < entry->start)
+			node = &(*node)->rb_left;
+		else if (offset > entry->end)
+			node = &(*node)->rb_right;
+		else
+			return *node;
+	}
+
+	/* Search neighbors until we find the first one past the end */
+	while (prev && offset > entry->end) {
+		prev = rb_next(prev);
+		entry = rb_entry(prev, struct tree_entry, rb_node);
+	}
+
+	return prev;
 }
 
 /*
Signature · 1 line
2.36.1
author maintainer
#12 lore raw

PATCH 8/9 btrfs: make tree search for insert more generic and use it for tree_search

In reply to David Sterba

With a slight extension of tree_search_for_insert (fill the return node and parent return parameters) we can avoid calling __etree_search from tree_search, that could be removed eventually in followup patches.

---
 fs/btrfs/extent_io.c | 27 +++++++++++++--------------
 1 file changed, 13 insertions(+), 14 deletions(-)
fs/btrfs/extent_io.c +13 -14
index de0bd32d99e0..ae27b7a5e56c 100644
@@ -443,20 +443,6 @@ tree_search_for_insert(struct extent_io_tree *tree,
 		       u64 offset,
 		       struct rb_node ***p_ret,
 		       struct rb_node **parent_ret)
-{
-	struct rb_node *next= NULL;
-	struct rb_node *ret;
-
-	ret = __etree_search(tree, offset, &next, NULL, p_ret, parent_ret);
-	if (!ret)
-		return next;
-	return ret;
-}
-
-/*
- * Inexact rb-tree search, return the next entry if @offset is not found
- */
-static inline struct rb_node *tree_search(struct extent_io_tree *tree, u64 offset)
 {
 	struct rb_root *root = &tree->state;
 	struct rb_node **node = &root->rb_node;
@@ -475,6 +461,11 @@ static inline struct rb_node *tree_search(struct extent_io_tree *tree, u64 offse
 			return *node;
 	}
 
+	if (p_ret)
+		*p_ret = node;
+	if (parent_ret)
+		*parent_ret = prev;
+
 	/* Search neighbors until we find the first one past the end */
 	while (prev && offset > entry->end) {
 		prev = rb_next(prev);
@@ -484,6 +475,14 @@ static inline struct rb_node *tree_search(struct extent_io_tree *tree, u64 offse
 	return prev;
 }
 
+/*
+ * Inexact rb-tree search, return the next entry if @offset is not found
+ */
+static inline struct rb_node *tree_search(struct extent_io_tree *tree, u64 offset)
+{
+	return tree_search_for_insert(tree, offset, NULL, NULL);
+}
+
 /*
  * utility function to look for merge candidates inside a given range.
  * Any extents with matching state are merged together into a single
Signature · 1 line
2.36.1
author maintainer
#13 lore raw

PATCH 9/9 btrfs: unify tree search helper returning prev and next nodes

In reply to David Sterba

Simplify helper to return only next and prev pointers, we don't need all the node/parent/prev/next pointers of __etree_search as there are now other specialized helpers. Rename parameters so they follow the naming.

---
 fs/btrfs/extent_io.c | 113 ++++++++++++++++++++++---------------------
 1 file changed, 57 insertions(+), 56 deletions(-)
fs/btrfs/extent_io.c +57 -56
index ae27b7a5e56c..48c5432a7c8f 100644
@@ -374,9 +374,7 @@ void free_extent_state(struct extent_state *state)
  *
  * @tree:       the tree to search
  * @offset:     offset that should fall within an entry in @tree
- * @next_ret:   pointer to the first entry whose range ends after @offset
- * @prev_ret:   pointer to the first entry whose range begins before @offset
- * @p_ret:      pointer where new node should be anchored (used when inserting an
+ * @node_ret:   pointer where new node should be anchored (used when inserting an
  *	        entry in the tree)
  * @parent_ret: points to entry which would have been the parent of the entry,
  *               containing @offset
@@ -386,69 +384,76 @@ void free_extent_state(struct extent_state *state)
  * pointer arguments to the function are filled, otherwise the found entry is
  * returned and other pointers are left untouched.
  */
-static struct rb_node *__etree_search(struct extent_io_tree *tree, u64 offset,
-				      struct rb_node **next_ret,
-				      struct rb_node **prev_ret,
-				      struct rb_node ***p_ret,
-				      struct rb_node **parent_ret)
+static inline struct rb_node *tree_search_for_insert(struct extent_io_tree *tree,
+					             u64 offset,
+						     struct rb_node ***node_ret,
+						     struct rb_node **parent_ret)
 {
 	struct rb_root *root = &tree->state;
-	struct rb_node **n = &root->rb_node;
+	struct rb_node **node = &root->rb_node;
 	struct rb_node *prev = NULL;
-	struct rb_node *orig_prev = NULL;
 	struct tree_entry *entry;
-	struct tree_entry *prev_entry = NULL;
 
-	while (*n) {
-		prev = *n;
+	while (*node) {
+		prev = *node;
 		entry = rb_entry(prev, struct tree_entry, rb_node);
-		prev_entry = entry;
 
 		if (offset < entry->start)
-			n = &(*n)->rb_left;
+			node = &(*node)->rb_left;
 		else if (offset > entry->end)
-			n = &(*n)->rb_right;
+			node = &(*node)->rb_right;
 		else
-			return *n;
+			return *node;
 	}
 
-	if (p_ret)
-		*p_ret = n;
+	if (node_ret)
+		*node_ret = node;
 	if (parent_ret)
 		*parent_ret = prev;
 
-	if (next_ret) {
-		orig_prev = prev;
-		while (prev && offset > prev_entry->end) {
-			prev = rb_next(prev);
-			prev_entry = rb_entry(prev, struct tree_entry, rb_node);
-		}
-		*next_ret = prev;
-		prev = orig_prev;
+	/* Search neighbors until we find the first one past the end */
+	while (prev && offset > entry->end) {
+		prev = rb_next(prev);
+		entry = rb_entry(prev, struct tree_entry, rb_node);
 	}
 
-	if (prev_ret) {
-		prev_entry = rb_entry(prev, struct tree_entry, rb_node);
-		while (prev && offset < prev_entry->start) {
-			prev = rb_prev(prev);
-			prev_entry = rb_entry(prev, struct tree_entry, rb_node);
-		}
-		*prev_ret = prev;
-	}
-	return NULL;
+	return prev;
+}
+
+/*
+ * Inexact rb-tree search, return the next entry if @offset is not found
+ */
+static inline struct rb_node *tree_search(struct extent_io_tree *tree, u64 offset)
+{
+	return tree_search_for_insert(tree, offset, NULL, NULL);
 }
 
-static inline struct rb_node *
-tree_search_for_insert(struct extent_io_tree *tree,
-		       u64 offset,
-		       struct rb_node ***p_ret,
-		       struct rb_node **parent_ret)
+/**
+ * Search offset in the tree or fill neighbor rbtree node pointers.
+ *
+ * @tree:      the tree to search
+ * @offset:    offset that should fall within an entry in @tree
+ * @next_ret:  pointer to the first entry whose range ends after @offset
+ * @prev_ret:  pointer to the first entry whose range begins before @offset
+ *
+ * Return a pointer to the entry that contains @offset byte address. If no
+ * such entry exists, then return NULL and fill @prev_ret and @next_ret.
+ * Otherwise return the found entry and other pointers are left untouched.
+ */
+static struct rb_node *tree_search_prev_next(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 **node = &root->rb_node;
 	struct rb_node *prev = NULL;
+	struct rb_node *orig_prev = NULL;
 	struct tree_entry *entry;
 
+	ASSERT(prev_ret);
+	ASSERT(next_ret);
+
 	while (*node) {
 		prev = *node;
 		entry = rb_entry(prev, struct tree_entry, rb_node);
@@ -461,26 +466,22 @@ tree_search_for_insert(struct extent_io_tree *tree,
 			return *node;
 	}
 
-	if (p_ret)
-		*p_ret = node;
-	if (parent_ret)
-		*parent_ret = prev;
-
-	/* Search neighbors until we find the first one past the end */
+	orig_prev = prev;
 	while (prev && offset > entry->end) {
 		prev = rb_next(prev);
 		entry = rb_entry(prev, struct tree_entry, rb_node);
 	}
+	*next_ret = prev;
+	prev = orig_prev;
 
-	return prev;
-}
+	entry = rb_entry(prev, struct tree_entry, rb_node);
+	while (prev && offset < entry->start) {
+		prev = rb_prev(prev);
+		entry = rb_entry(prev, struct tree_entry, rb_node);
+	}
+	*prev_ret = prev;
 
-/*
- * Inexact rb-tree search, return the next entry if @offset is not found
- */
-static inline struct rb_node *tree_search(struct extent_io_tree *tree, u64 offset)
-{
-	return tree_search_for_insert(tree, offset, NULL, NULL);
+	return NULL;
 }
 
 /*
@@ -1687,7 +1688,7 @@ void find_first_clear_extent_bit(struct extent_io_tree *tree, u64 start,
 
 	/* Find first extent with bits cleared */
 	while (1) {
-		node = __etree_search(tree, start, &next, &prev, NULL, NULL);
+		node = tree_search_prev_next(tree, start, &prev, &next);
 		if (!node && !next && !prev) {
 			/*
 			 * Tree is completely empty, send full range and let
Signature · 1 line
2.36.1
#16 lore raw
In reply to David Sterba
Quoted 9 lines · David Sterba

The extent_io_tree search helpers take return parameters and many callers pass just NULL, which are checked and add a conditionals to some paths. Reorganize helpers to suit what callers need and drop unnecessary parameters, open code rbtree search loops and clean up some other parameters.

This could improve performance in some cases but it's mostly micro optimizations and I haven't done any measurements.

Quoted 11 lines

David Sterba (9):
btrfs: open code rbtree search into split_state
btrfs: open code rbtree search in insert_state
btrfs: lift start and end parameters to callers of insert_state
btrfs: pass bits by value not pointer for extent_state helpers
btrfs: add fast path for extent_state insertion
btrfs: remove node and parent parameters from insert_state
btrfs: open code inexact rbtree search in tree_search
btrfs: make tree search for insert more generic and use it for
tree_search
btrfs: unify tree search helper returning prev and next nodes

Added to misc-next.

#4 lore raw

Re: [PATCH 3/9] btrfs: lift start and end parameters to callers of insert_state

In reply to David Sterba
Quoted 23 lines · David Sterba

Let callers of insert_state to set up the extent state to allow further simplifications of the parameters.

---
  fs/btrfs/extent_io.c | 33 +++++++++++++++------------------
  1 file changed, 15 insertions(+), 18 deletions(-)
fs/btrfs/extent_io.c +1 -1
index 429096fc8899..1411286e5ef2 100644
@@ -524,21 +524,14 @@ static void set_state_bits(struct extent_io_tree *tree,
   * probably isn't what you want to call (see set/clear_extent_bit).
   */
  static int insert_state(struct extent_io_tree *tree,
-			struct extent_state *state, u64 start, u64 end,
+			struct extent_state *state,
  			struct rb_node ***node_in,
  			struct rb_node **parent_in,
  			u32 *bits, struct extent_changeset *changeset)
  {
  	struct rb_node **node;

fs/btrfs/extent_io.c static void set_state_bits(struct extent_io_tree *tree, · line 534

Quoted 10 lines
fs/btrfs/extent_io.c +1 -8
  	struct rb_node *parent;
-
-	if (end < start) {
-		btrfs_err(tree->fs_info,
-			"insert state: end < start %llu %llu", end, start);
-		WARN_ON(1);
-	}
-	state->start = start;
-	state->end = end;
+	const u64 end = state->end;

Why do you need an explicit end when it's only used in the while loop and any possible changes actually come afterwards in case it's merged?

<snip>

#8 lore raw

Re: [PATCH 5/9] btrfs: add fast path for extent_state insertion

In reply to David Sterba
Quoted 14 lines · David Sterba

In two cases the exact location where to insert the extent state is known at the call time so we don't need to pass it to insert_state that takes the fast path.

---
  fs/btrfs/extent_io.c | 24 +++++++++++++++++-------
  1 file changed, 17 insertions(+), 7 deletions(-)
fs/btrfs/extent_io.c +0 -0
index 9b1dfe4363c9..00a6a2d0b112 100644

fs/btrfs/extent_io.c static int insert_state(struct extent_io_tree *tree, · line 573

Quoted 5 lines
fs/btrfs/extent_io.c +2 -0
@@ -569,6 +569,21 @@ static int insert_state(struct extent_io_tree *tree,
  	return 0;
  }
 
+/*
+ * Insert state to the tree to a location given by @p_

that @p_ seems incomplete?

<snip>

#14 lore raw

Re: [PATCH 9/9] btrfs: unify tree search helper returning prev and next nodes

In reply to David Sterba
Quoted 25 lines · David Sterba

Simplify helper to return only next and prev pointers, we don't need all the node/parent/prev/next pointers of __etree_search as there are now other specialized helpers. Rename parameters so they follow the naming.

---
  fs/btrfs/extent_io.c | 113 ++++++++++++++++++++++---------------------
  1 file changed, 57 insertions(+), 56 deletions(-)
fs/btrfs/extent_io.c +1 -3
index ae27b7a5e56c..48c5432a7c8f 100644
@@ -374,9 +374,7 @@ void free_extent_state(struct extent_state *state)
   *
   * @tree:       the tree to search
   * @offset:     offset that should fall within an entry in @tree
- * @next_ret:   pointer to the first entry whose range ends after @offset
- * @prev_ret:   pointer to the first entry whose range begins before @offset
- * @p_ret:      pointer where new node should be anchored (used when inserting an
+ * @node_ret:   pointer where new node should be anchored (used when inserting an
   *	        entry in the tree)
   * @parent_ret: points to entry which would have been the parent of the entry,
   *               containing @offset

fs/btrfs/extent_io.c void free_extent_state(struct extent_state *state) · line 386

Quoted 3 lines
fs/btrfs/extent_io.c +0 -0
@@ -386,69 +384,76 @@ void free_extent_state(struct extent_state *state)
   * pointer arguments to the function are filled, otherwise the found entry is
   * returned and other pointers are left untouched.
   */

The comment should be changed as it's no longer valid. Currently it states:

If no such entry exists, then NULL is returned and the other
pointer arguments to the function are filled, otherwise the found entry is returned and other pointers are left untouched.

When no such entry exists, the other pointer arguments to the function are indeed filled, however the function now returns the first entry that ends _before_ the offset i.e this function can never return NULL.

So it return either the entry which contains 'offset' or the last entry before offset.

<snip>

#5 lore raw

Re: [PATCH 3/9] btrfs: lift start and end parameters to callers of insert_state

In reply to Nikolay Borisov
Quoted 31 lines · Nikolay Borisov
Quoted 28 lines · David Sterba

Let callers of insert_state to set up the extent state to allow further simplifications of the parameters.

---
  fs/btrfs/extent_io.c | 33 +++++++++++++++------------------
  1 file changed, 15 insertions(+), 18 deletions(-)
fs/btrfs/extent_io.c +1 -5
index 429096fc8899..1411286e5ef2 100644
@@ -524,21 +524,14 @@ static void set_state_bits(struct extent_io_tree *tree,
   * probably isn't what you want to call (see set/clear_extent_bit).
   */
  static int insert_state(struct extent_io_tree *tree,
-			struct extent_state *state, u64 start, u64 end,
+			struct extent_state *state,
  			struct rb_node ***node_in,
  			struct rb_node **parent_in,
  			u32 *bits, struct extent_changeset *changeset)
  {
  	struct rb_node **node;
  	struct rb_node *parent;
-
-	if (end < start) {
-		btrfs_err(tree->fs_info,
-			"insert state: end < start %llu %llu", end, start);
Quoted 8 lines

fs/btrfs/extent_io.c static void set_state_bits(struct extent_io_tree *tree, · line 534

Quoted 5 lines
fs/btrfs/extent_io.c +1 -4
-		WARN_ON(1);
-	}
-	state->start = start;
-	state->end = end;
+	const u64 end = state->end;

Why do you need an explicit end when it's only used in the while loop and any possible changes actually come afterwards in case it's merged?

I think it's to minimize changes in the rest of the funciton, but you're right that end === state->end. Although caching the value in local variable could be a performance optimization for the tree search, I've compared both versions, the value is in a register in both and the non-cached also drops the stack allocation. So, I'll use state->end.

#9 lore raw

Re: [PATCH 5/9] btrfs: add fast path for extent_state insertion

In reply to Nikolay Borisov
Quoted 20 lines · Nikolay Borisov
Quoted 17 lines · David Sterba

In two cases the exact location where to insert the extent state is known at the call time so we don't need to pass it to insert_state that takes the fast path.

---
  fs/btrfs/extent_io.c | 24 +++++++++++++++++-------
  1 file changed, 17 insertions(+), 7 deletions(-)
fs/btrfs/extent_io.c +0 -0
index 9b1dfe4363c9..00a6a2d0b112 100644
@@ -569,6 +569,21 @@ static int insert_state(struct extent_io_tree *tree,
  	return 0;
  }
 
Quoted 4 lines

fs/btrfs/extent_io.c static int insert_state(struct extent_io_tree *tree, · line 573

Quoted 2 lines
fs/btrfs/extent_io.c +2 -0
+/*
+ * Insert state to the tree to a location given by @p_

that @p_ seems incomplete?

That's a typo and the variable got renamed to 'node', fixed.

#15 lore raw

Re: [PATCH 9/9] btrfs: unify tree search helper returning prev and next nodes

In reply to Nikolay Borisov
Quoted 38 lines · Nikolay Borisov
Quoted 25 lines · David Sterba

Simplify helper to return only next and prev pointers, we don't need all the node/parent/prev/next pointers of __etree_search as there are now other specialized helpers. Rename parameters so they follow the naming.

---
  fs/btrfs/extent_io.c | 113 ++++++++++++++++++++++---------------------
  1 file changed, 57 insertions(+), 56 deletions(-)
fs/btrfs/extent_io.c +1 -3
index ae27b7a5e56c..48c5432a7c8f 100644
@@ -374,9 +374,7 @@ void free_extent_state(struct extent_state *state)
   *
   * @tree:       the tree to search
   * @offset:     offset that should fall within an entry in @tree
- * @next_ret:   pointer to the first entry whose range ends after @offset
- * @prev_ret:   pointer to the first entry whose range begins before @offset
- * @p_ret:      pointer where new node should be anchored (used when inserting an
+ * @node_ret:   pointer where new node should be anchored (used when inserting an
   *	        entry in the tree)
   * @parent_ret: points to entry which would have been the parent of the entry,
   *               containing @offset

fs/btrfs/extent_io.c void free_extent_state(struct extent_state *state) · line 386

Quoted 3 lines
fs/btrfs/extent_io.c +0 -0
@@ -386,69 +384,76 @@ void free_extent_state(struct extent_state *state)
   * pointer arguments to the function are filled, otherwise the found entry is
   * returned and other pointers are left untouched.
   */

The comment should be changed as it's no longer valid. Currently it states:

If no such entry exists, then NULL is returned and the other pointer arguments to the function are filled, otherwise the found entry is returned and other pointers are left untouched.

Quoted 6 lines

When no such entry exists, the other pointer arguments to the function are indeed filled, however the function now returns the first entry that ends _before_ the offset i.e this function can never return NULL.

So it return either the entry which contains 'offset' or the last entry before offset.

Updated to:

+  * Return a pointer to the entry that contains @offset byte address and don't change
+  * @node_ret and @parent_ret.
+  *
+  * If no such entry exists, return pointer to entry that ends before @offset
+  * and fill parameters @node_ret and @parent_ret, ie. does not return NULL.