[PATCH 0/9] Extent tree search cleanups

[PATCH 0/9] Extent tree search cleanups

[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.

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(-)

-- 
2.36.1

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

[David Sterba]

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.

Signed-off-by: David Sterba <dsterba@suse.com>
---
 fs/btrfs/extent_io.c | 28 ++++++++++++++++++++++------
 1 file changed, 22 insertions(+), 6 deletions(-)

diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
index 9fd114683027..c39f8674b6ce 100644
--- a/fs/btrfs/extent_io.c
+++ b/fs/btrfs/extent_io.c
@@ -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;
 }
 
-- 
2.36.1

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

[David Sterba]

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

Signed-off-by: David Sterba <dsterba@suse.com>
---
 fs/btrfs/extent_io.c | 80 ++++++++++++++++++--------------------------
 1 file changed, 33 insertions(+), 47 deletions(-)

diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
index c39f8674b6ce..429096fc8899 100644
--- a/fs/btrfs/extent_io.c
+++ b/fs/btrfs/extent_io.c
@@ -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;
 }
-- 
2.36.1

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

[David Sterba]

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

Signed-off-by: David Sterba <dsterba@suse.com>
---
 fs/btrfs/extent_io.c | 33 +++++++++++++++------------------
 1 file changed, 15 insertions(+), 18 deletions(-)

diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
index 429096fc8899..1411286e5ef2 100644
--- a/fs/btrfs/extent_io.c
+++ b/fs/btrfs/extent_io.c
@@ -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);
-- 
2.36.1

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

[Nikolay Borisov]

On 8.06.22 г. 19:43 ч., David Sterba wrote:
> Let callers of insert_state to set up the extent state to allow further
> simplifications of the parameters.
> 
> Signed-off-by: David Sterba <dsterba@suse.com>
> ---
>   fs/btrfs/extent_io.c | 33 +++++++++++++++------------------
>   1 file changed, 15 insertions(+), 18 deletions(-)
> 
> diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
> index 429096fc8899..1411286e5ef2 100644
> --- a/fs/btrfs/extent_io.c
> +++ b/fs/btrfs/extent_io.c
> @@ -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;

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>

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

[David Sterba]

On Wed, Jun 15, 2022 at 05:17:13PM +0300, Nikolay Borisov wrote:
> 
> 
> On 8.06.22 г. 19:43 ч., David Sterba wrote:
> > Let callers of insert_state to set up the extent state to allow further
> > simplifications of the parameters.
> > 
> > Signed-off-by: David Sterba <dsterba@suse.com>
> > ---
> >   fs/btrfs/extent_io.c | 33 +++++++++++++++------------------
> >   1 file changed, 15 insertions(+), 18 deletions(-)
> > 
> > diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
> > index 429096fc8899..1411286e5ef2 100644
> > --- a/fs/btrfs/extent_io.c
> > +++ b/fs/btrfs/extent_io.c
> > @@ -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;
> 
> 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.

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

[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.

Signed-off-by: David Sterba <dsterba@suse.com>
---
 fs/btrfs/ctree.h     |  4 ++--
 fs/btrfs/extent_io.c | 46 +++++++++++++++++++++-----------------------
 fs/btrfs/inode.c     | 24 +++++++++++------------
 3 files changed, 36 insertions(+), 38 deletions(-)

diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index f7afdfd0bae7..13d74948c542 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -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,
diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
index 1411286e5ef2..9b1dfe4363c9 100644
--- a/fs/btrfs/extent_io.c
+++ b/fs/btrfs/extent_io.c
@@ -510,7 +510,7 @@ static void merge_state(struct extent_io_tree *tree,
 }
 
 static void set_state_bits(struct extent_io_tree *tree,
-			   struct extent_state *state, u32 *bits,
+			   struct extent_state *state, u32 bits,
 			   struct extent_changeset *changeset);
 
 /*
@@ -527,7 +527,7 @@ 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)
+			u32 bits, struct extent_changeset *changeset)
 {
 	struct rb_node **node;
 	struct rb_node *parent;
@@ -639,11 +639,11 @@ static struct extent_state *next_state(struct extent_state *state)
  */
 static struct extent_state *clear_state_bit(struct extent_io_tree *tree,
 					    struct extent_state *state,
-					    u32 *bits, int wake,
+					    u32 bits, int wake,
 					    struct extent_changeset *changeset)
 {
 	struct extent_state *next;
-	u32 bits_to_clear = *bits & ~EXTENT_CTLBITS;
+	u32 bits_to_clear = bits & ~EXTENT_CTLBITS;
 	int ret;
 
 	if ((bits_to_clear & EXTENT_DIRTY) && (state->state & EXTENT_DIRTY)) {
@@ -805,8 +805,7 @@ int __clear_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
 		if (err)
 			goto out;
 		if (state->end <= end) {
-			state = clear_state_bit(tree, state, &bits, wake,
-						changeset);
+			state = clear_state_bit(tree, state, bits, wake, changeset);
 			goto next;
 		}
 		goto search_again;
@@ -827,13 +826,13 @@ int __clear_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
 		if (wake)
 			wake_up(&state->wq);
 
-		clear_state_bit(tree, prealloc, &bits, wake, changeset);
+		clear_state_bit(tree, prealloc, bits, wake, changeset);
 
 		prealloc = NULL;
 		goto out;
 	}
 
-	state = clear_state_bit(tree, state, &bits, wake, changeset);
+	state = clear_state_bit(tree, state, bits, wake, changeset);
 next:
 	if (last_end == (u64)-1)
 		goto out;
@@ -924,9 +923,9 @@ static void wait_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
 
 static void set_state_bits(struct extent_io_tree *tree,
 			   struct extent_state *state,
-			   u32 *bits, struct extent_changeset *changeset)
+			   u32 bits, struct extent_changeset *changeset)
 {
-	u32 bits_to_set = *bits & ~EXTENT_CTLBITS;
+	u32 bits_to_set = bits & ~EXTENT_CTLBITS;
 	int ret;
 
 	if (tree->private_data && is_data_inode(tree->private_data))
@@ -1022,7 +1021,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);
+		err = insert_state(tree, prealloc, &p, &parent, bits, changeset);
 		if (err)
 			extent_io_tree_panic(tree, err);
 
@@ -1048,7 +1047,7 @@ int set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, u32 bits,
 			goto out;
 		}
 
-		set_state_bits(tree, state, &bits, changeset);
+		set_state_bits(tree, state, bits, changeset);
 		cache_state(state, cached_state);
 		merge_state(tree, state);
 		if (last_end == (u64)-1)
@@ -1104,7 +1103,7 @@ int set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, u32 bits,
 		if (err)
 			goto out;
 		if (state->end <= end) {
-			set_state_bits(tree, state, &bits, changeset);
+			set_state_bits(tree, state, bits, changeset);
 			cache_state(state, cached_state);
 			merge_state(tree, state);
 			if (last_end == (u64)-1)
@@ -1140,7 +1139,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, NULL, NULL, bits, changeset);
 		if (err)
 			extent_io_tree_panic(tree, err);
 
@@ -1168,7 +1167,7 @@ int set_extent_bit(struct extent_io_tree *tree, u64 start, u64 end, u32 bits,
 		if (err)
 			extent_io_tree_panic(tree, err);
 
-		set_state_bits(tree, prealloc, &bits, changeset);
+		set_state_bits(tree, prealloc, bits, changeset);
 		cache_state(prealloc, cached_state);
 		merge_state(tree, prealloc);
 		prealloc = NULL;
@@ -1265,7 +1264,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);
+		err = insert_state(tree, prealloc, &p, &parent, bits, NULL);
 		if (err)
 			extent_io_tree_panic(tree, err);
 		cache_state(prealloc, cached_state);
@@ -1284,9 +1283,9 @@ int convert_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
 	 * Just lock what we found and keep going
 	 */
 	if (state->start == start && state->end <= end) {
-		set_state_bits(tree, state, &bits, NULL);
+		set_state_bits(tree, state, bits, NULL);
 		cache_state(state, cached_state);
-		state = clear_state_bit(tree, state, &clear_bits, 0, NULL);
+		state = clear_state_bit(tree, state, clear_bits, 0, NULL);
 		if (last_end == (u64)-1)
 			goto out;
 		start = last_end + 1;
@@ -1325,10 +1324,9 @@ int convert_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
 		if (err)
 			goto out;
 		if (state->end <= end) {
-			set_state_bits(tree, state, &bits, NULL);
+			set_state_bits(tree, state, bits, NULL);
 			cache_state(state, cached_state);
-			state = clear_state_bit(tree, state, &clear_bits, 0,
-						NULL);
+			state = clear_state_bit(tree, state, clear_bits, 0, NULL);
 			if (last_end == (u64)-1)
 				goto out;
 			start = last_end + 1;
@@ -1364,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, NULL, NULL, bits, NULL);
 		if (err)
 			extent_io_tree_panic(tree, err);
 		cache_state(prealloc, cached_state);
@@ -1389,9 +1387,9 @@ int convert_extent_bit(struct extent_io_tree *tree, u64 start, u64 end,
 		if (err)
 			extent_io_tree_panic(tree, err);
 
-		set_state_bits(tree, prealloc, &bits, NULL);
+		set_state_bits(tree, prealloc, bits, NULL);
 		cache_state(prealloc, cached_state);
-		clear_state_bit(tree, prealloc, &clear_bits, 0, NULL);
+		clear_state_bit(tree, prealloc, clear_bits, 0, NULL);
 		prealloc = NULL;
 		goto out;
 	}
diff --git a/fs/btrfs/inode.c b/fs/btrfs/inode.c
index 7a54f964ff37..33ba4d22e143 100644
--- a/fs/btrfs/inode.c
+++ b/fs/btrfs/inode.c
@@ -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);
 	}
-- 
2.36.1

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

[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.

Signed-off-by: David Sterba <dsterba@suse.com>
---
 fs/btrfs/extent_io.c | 24 +++++++++++++++++-------
 1 file changed, 17 insertions(+), 7 deletions(-)

diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
index 9b1dfe4363c9..00a6a2d0b112 100644
--- a/fs/btrfs/extent_io.c
+++ b/fs/btrfs/extent_io.c
@@ -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;
-- 
2.36.1

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

[Nikolay Borisov]

On 8.06.22 г. 19:43 ч., David Sterba wrote:
> 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.
> 
> Signed-off-by: David Sterba <dsterba@suse.com>
> ---
>   fs/btrfs/extent_io.c | 24 +++++++++++++++++-------
>   1 file changed, 17 insertions(+), 7 deletions(-)
> 
> diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
> index 9b1dfe4363c9..00a6a2d0b112 100644
> --- a/fs/btrfs/extent_io.c
> +++ b/fs/btrfs/extent_io.c
> @@ -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>

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

[David Sterba]

On Wed, Jun 15, 2022 at 05:19:31PM +0300, Nikolay Borisov wrote:
> 
> 
> On 8.06.22 г. 19:43 ч., David Sterba wrote:
> > 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.
> > 
> > Signed-off-by: David Sterba <dsterba@suse.com>
> > ---
> >   fs/btrfs/extent_io.c | 24 +++++++++++++++++-------
> >   1 file changed, 17 insertions(+), 7 deletions(-)
> > 
> > diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
> > index 9b1dfe4363c9..00a6a2d0b112 100644
> > --- a/fs/btrfs/extent_io.c
> > +++ b/fs/btrfs/extent_io.c
> > @@ -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?

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

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

[David Sterba]

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

Signed-off-by: David Sterba <dsterba@suse.com>
---
 fs/btrfs/extent_io.c | 14 ++------------
 1 file changed, 2 insertions(+), 12 deletions(-)

diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
index 00a6a2d0b112..b7d6f2dc4706 100644
--- a/fs/btrfs/extent_io.c
+++ b/fs/btrfs/extent_io.c
@@ -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);
-- 
2.36.1

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

[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.

Signed-off-by: David Sterba <dsterba@suse.com>
---
 fs/btrfs/extent_io.c | 31 ++++++++++++++++++++++++++++---
 1 file changed, 28 insertions(+), 3 deletions(-)

diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
index b7d6f2dc4706..de0bd32d99e0 100644
--- a/fs/btrfs/extent_io.c
+++ b/fs/btrfs/extent_io.c
@@ -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;
 }
 
 /*
-- 
2.36.1

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

[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.

Signed-off-by: David Sterba <dsterba@suse.com>
---
 fs/btrfs/extent_io.c | 27 +++++++++++++--------------
 1 file changed, 13 insertions(+), 14 deletions(-)

diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
index de0bd32d99e0..ae27b7a5e56c 100644
--- a/fs/btrfs/extent_io.c
+++ b/fs/btrfs/extent_io.c
@@ -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
-- 
2.36.1

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

[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.

Signed-off-by: David Sterba <dsterba@suse.com>
---
 fs/btrfs/extent_io.c | 113 ++++++++++++++++++++++---------------------
 1 file changed, 57 insertions(+), 56 deletions(-)

diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
index ae27b7a5e56c..48c5432a7c8f 100644
--- a/fs/btrfs/extent_io.c
+++ b/fs/btrfs/extent_io.c
@@ -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
-- 
2.36.1

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

[Nikolay Borisov]

On 8.06.22 г. 19:43 ч., David Sterba wrote:
> 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.
> 
> Signed-off-by: David Sterba <dsterba@suse.com>
> ---
>   fs/btrfs/extent_io.c | 113 ++++++++++++++++++++++---------------------
>   1 file changed, 57 insertions(+), 56 deletions(-)
> 
> diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
> index ae27b7a5e56c..48c5432a7c8f 100644
> --- a/fs/btrfs/extent_io.c
> +++ b/fs/btrfs/extent_io.c
> @@ -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.
>    */

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>

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

[David Sterba]

On Thu, Jun 16, 2022 at 12:51:50PM +0300, Nikolay Borisov wrote:
> 
> 
> On 8.06.22 г. 19:43 ч., David Sterba wrote:
> > 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.
> > 
> > Signed-off-by: David Sterba <dsterba@suse.com>
> > ---
> >   fs/btrfs/extent_io.c | 113 ++++++++++++++++++++++---------------------
> >   1 file changed, 57 insertions(+), 56 deletions(-)
> > 
> > diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
> > index ae27b7a5e56c..48c5432a7c8f 100644
> > --- a/fs/btrfs/extent_io.c
> > +++ b/fs/btrfs/extent_io.c
> > @@ -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.
> >    */
> 
> 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.

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.

Re: [PATCH 0/9] Extent tree search cleanups

[David Sterba]

On Wed, Jun 08, 2022 at 06:43:19PM +0200, David Sterba wrote:
> 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

Added to misc-next.