[PATCH 1/6] rbtree: add rb_find_add_cached() to rbtree.h

[PATCH 1/6] rbtree: add rb_find_add_cached() to rbtree.h

[Roger L. Beckermeyer III]

Adds rb_find_add_cached() as a helper function for use with
red-black trees. Used in btrfs to reduce boilerplate code.

Suggested-by: Josef Bacik <josef@toxicpanda.com>
Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
---
 include/linux/rbtree.h | 37 +++++++++++++++++++++++++++++++++++++
 1 file changed, 37 insertions(+)

diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index 7c173aa64e1e..0d4444c0cfb3 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -210,6 +210,43 @@ rb_add(struct rb_node *node, struct rb_root *tree,
 	rb_insert_color(node, tree);
 }
 
+/**
+ * rb_find_add_cached() - find equivalent @node in @tree, or add @node
+ * @node: node to look-for / insert
+ * @tree: tree to search / modify
+ * @cmp: operator defining the node order
+ *
+ * Returns the rb_node matching @node, or NULL when no match is found and @node
+ * is inserted.
+ */
+static __always_inline struct rb_node *
+rb_find_add_cached(struct rb_node *node, struct rb_root_cached *tree,
+	    int (*cmp)(struct rb_node *, const struct rb_node *))
+{
+	bool leftmost = true;
+	struct rb_node **link = &tree->rb_root.rb_node;
+	struct rb_node *parent = NULL;
+	int c;
+
+	while (*link) {
+		parent = *link;
+		c = cmp(node, parent);
+
+		if (c < 0) {
+			link = &parent->rb_left;
+		} else if (c > 0) {
+			link = &parent->rb_right;
+			leftmost = false;
+		} else {
+			return parent;
+		}
+	}
+
+	rb_link_node(node, parent, link);
+	rb_insert_color_cached(node, tree, leftmost);
+	return NULL;
+}
+
 /**
  * rb_find_add() - find equivalent @node in @tree, or add @node
  * @node: node to look-for / insert
-- 
2.45.2

Re: [PATCH 1/6] rbtree: add rb_find_add_cached() to rbtree.h

[Qu Wenruo]

在 2024/12/13 03:16, Roger L. Beckermeyer III 写道:
> Adds rb_find_add_cached() as a helper function for use with
> red-black trees. Used in btrfs to reduce boilerplate code.

I won't call it boilerplate code though, it's just to utilize the cached
rb tree feature as an optimization.

And since rbtree is a tree-wide infrastructure, you need to be more
persuasive to add a new interface.

Yes, btrfs is utilizing this cached rb tree, but since you're adding a
new tree-wide interface, it will be much better to find another
driver/subsystem that can benefit from the new interface.

>
> Suggested-by: Josef Bacik <josef@toxicpanda.com>
> Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
> ---
>   include/linux/rbtree.h | 37 +++++++++++++++++++++++++++++++++++++
>   1 file changed, 37 insertions(+)
>
> diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
> index 7c173aa64e1e..0d4444c0cfb3 100644
> --- a/include/linux/rbtree.h
> +++ b/include/linux/rbtree.h
> @@ -210,6 +210,43 @@ rb_add(struct rb_node *node, struct rb_root *tree,
>   	rb_insert_color(node, tree);
>   }
>
> +/**
> + * rb_find_add_cached() - find equivalent @node in @tree, or add @node
> + * @node: node to look-for / insert
> + * @tree: tree to search / modify
> + * @cmp: operator defining the node order
> + *
> + * Returns the rb_node matching @node, or NULL when no match is found and @node
> + * is inserted.
> + */
> +static __always_inline struct rb_node *
> +rb_find_add_cached(struct rb_node *node, struct rb_root_cached *tree,
> +	    int (*cmp)(struct rb_node *, const struct rb_node *))

This function is almost the same as rb_add_cached(), the only difference
is the extra handling for the cmp function returning 0.

So I'm wondering if it's possible to enhance rb_add_cached(), or even
refactor it so there can be a shared core function and rb_add_cached()
and rb_find_add_cached() can reuse the same function.

Thanks,
Qu

> +{
> +	bool leftmost = true;
> +	struct rb_node **link = &tree->rb_root.rb_node;
> +	struct rb_node *parent = NULL;
> +	int c;
> +
> +	while (*link) {
> +		parent = *link;
> +		c = cmp(node, parent);
> +
> +		if (c < 0) {
> +			link = &parent->rb_left;
> +		} else if (c > 0) {
> +			link = &parent->rb_right;
> +			leftmost = false;
> +		} else {
> +			return parent;
> +		}
> +	}
> +
> +	rb_link_node(node, parent, link);
> +	rb_insert_color_cached(node, tree, leftmost);
> +	return NULL;
> +}
> +
>   /**
>    * rb_find_add() - find equivalent @node in @tree, or add @node
>    * @node: node to look-for / insert

Re: [PATCH 1/6] rbtree: add rb_find_add_cached() to rbtree.h

[Peter Zijlstra]

On Fri, Dec 13, 2024 at 05:51:44PM +1030, Qu Wenruo wrote:
> 
> 
> 在 2024/12/13 03:16, Roger L. Beckermeyer III 写道:
> > Adds rb_find_add_cached() as a helper function for use with
> > red-black trees. Used in btrfs to reduce boilerplate code.
> 
> I won't call it boilerplate code though, it's just to utilize the cached
> rb tree feature as an optimization.

Nah, all this is boilerplate :-)

> > 
> > Suggested-by: Josef Bacik <josef@toxicpanda.com>
> > Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
> > ---
> >   include/linux/rbtree.h | 37 +++++++++++++++++++++++++++++++++++++
> >   1 file changed, 37 insertions(+)
> > 
> > diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
> > index 7c173aa64e1e..0d4444c0cfb3 100644
> > --- a/include/linux/rbtree.h
> > +++ b/include/linux/rbtree.h
> > @@ -210,6 +210,43 @@ rb_add(struct rb_node *node, struct rb_root *tree,
> >   	rb_insert_color(node, tree);
> >   }
> > 
> > +/**
> > + * rb_find_add_cached() - find equivalent @node in @tree, or add @node
> > + * @node: node to look-for / insert
> > + * @tree: tree to search / modify
> > + * @cmp: operator defining the node order
> > + *
> > + * Returns the rb_node matching @node, or NULL when no match is found and @node
> > + * is inserted.
> > + */
> > +static __always_inline struct rb_node *
> > +rb_find_add_cached(struct rb_node *node, struct rb_root_cached *tree,
> > +	    int (*cmp)(struct rb_node *, const struct rb_node *))
> 
> This function is almost the same as rb_add_cached(), the only difference
> is the extra handling for the cmp function returning 0.
> 
> So I'm wondering if it's possible to enhance rb_add_cached(), or even
> refactor it so there can be a shared core function and rb_add_cached()
> and rb_find_add_cached() can reuse the same function.

Nope, rb_add_cached() can add multiple entries with the same key,
rb_find_add() cannot.

Also, note that all these things are effectively 'templates', they
generate code at the call site. The cmp() function as required for
find_add() is a tri-state return and generates more logic than the
binary less() required for add().

Re: [PATCH 1/6] rbtree: add rb_find_add_cached() to rbtree.h

[Peter Zijlstra]

On Thu, Dec 12, 2024 at 10:46:18AM -0600, Roger L. Beckermeyer III wrote:
> Adds rb_find_add_cached() as a helper function for use with
> red-black trees. Used in btrfs to reduce boilerplate code.
> 
> Suggested-by: Josef Bacik <josef@toxicpanda.com>
> Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>

Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>

> ---
>  include/linux/rbtree.h | 37 +++++++++++++++++++++++++++++++++++++
>  1 file changed, 37 insertions(+)
> 
> diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
> index 7c173aa64e1e..0d4444c0cfb3 100644
> --- a/include/linux/rbtree.h
> +++ b/include/linux/rbtree.h
> @@ -210,6 +210,43 @@ rb_add(struct rb_node *node, struct rb_root *tree,
>  	rb_insert_color(node, tree);
>  }
>  
> +/**
> + * rb_find_add_cached() - find equivalent @node in @tree, or add @node
> + * @node: node to look-for / insert
> + * @tree: tree to search / modify
> + * @cmp: operator defining the node order
> + *
> + * Returns the rb_node matching @node, or NULL when no match is found and @node
> + * is inserted.
> + */
> +static __always_inline struct rb_node *
> +rb_find_add_cached(struct rb_node *node, struct rb_root_cached *tree,
> +	    int (*cmp)(struct rb_node *, const struct rb_node *))
> +{
> +	bool leftmost = true;
> +	struct rb_node **link = &tree->rb_root.rb_node;
> +	struct rb_node *parent = NULL;
> +	int c;
> +
> +	while (*link) {
> +		parent = *link;
> +		c = cmp(node, parent);
> +
> +		if (c < 0) {
> +			link = &parent->rb_left;
> +		} else if (c > 0) {
> +			link = &parent->rb_right;
> +			leftmost = false;
> +		} else {
> +			return parent;
> +		}
> +	}
> +
> +	rb_link_node(node, parent, link);
> +	rb_insert_color_cached(node, tree, leftmost);
> +	return NULL;
> +}
> +
>  /**
>   * rb_find_add() - find equivalent @node in @tree, or add @node
>   * @node: node to look-for / insert
> -- 
> 2.45.2
> 

Re: [PATCH 1/6] rbtree: add rb_find_add_cached() to rbtree.h

[Qu Wenruo]

在 2024/12/13 19:36, Peter Zijlstra 写道:
> On Thu, Dec 12, 2024 at 10:46:18AM -0600, Roger L. Beckermeyer III wrote:
>> Adds rb_find_add_cached() as a helper function for use with
>> red-black trees. Used in btrfs to reduce boilerplate code.
>>
>> Suggested-by: Josef Bacik <josef@toxicpanda.com>
>> Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
>
> Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>

I guess it's fine to merge this change through btrfs tree?


Just curious about the existing cmp() and less() functions, as they only
accept the exist node as const.

I'm wondering if this is intentional to allow the less/cmp() functions
to modify the new node if needed.
As I normally assume such cmp()/less() should never touch any node nor
its entries.

Thanks,
Qu

>
>> ---
>>   include/linux/rbtree.h | 37 +++++++++++++++++++++++++++++++++++++
>>   1 file changed, 37 insertions(+)
>>
>> diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
>> index 7c173aa64e1e..0d4444c0cfb3 100644
>> --- a/include/linux/rbtree.h
>> +++ b/include/linux/rbtree.h
>> @@ -210,6 +210,43 @@ rb_add(struct rb_node *node, struct rb_root *tree,
>>   	rb_insert_color(node, tree);
>>   }
>>
>> +/**
>> + * rb_find_add_cached() - find equivalent @node in @tree, or add @node
>> + * @node: node to look-for / insert
>> + * @tree: tree to search / modify
>> + * @cmp: operator defining the node order
>> + *
>> + * Returns the rb_node matching @node, or NULL when no match is found and @node
>> + * is inserted.
>> + */
>> +static __always_inline struct rb_node *
>> +rb_find_add_cached(struct rb_node *node, struct rb_root_cached *tree,
>> +	    int (*cmp)(struct rb_node *, const struct rb_node *))
>> +{
>> +	bool leftmost = true;
>> +	struct rb_node **link = &tree->rb_root.rb_node;
>> +	struct rb_node *parent = NULL;
>> +	int c;
>> +
>> +	while (*link) {
>> +		parent = *link;
>> +		c = cmp(node, parent);
>> +
>> +		if (c < 0) {
>> +			link = &parent->rb_left;
>> +		} else if (c > 0) {
>> +			link = &parent->rb_right;
>> +			leftmost = false;
>> +		} else {
>> +			return parent;
>> +		}
>> +	}
>> +
>> +	rb_link_node(node, parent, link);
>> +	rb_insert_color_cached(node, tree, leftmost);
>> +	return NULL;
>> +}
>> +
>>   /**
>>    * rb_find_add() - find equivalent @node in @tree, or add @node
>>    * @node: node to look-for / insert
>> --
>> 2.45.2
>>
>

Re: [PATCH 1/6] rbtree: add rb_find_add_cached() to rbtree.h

[Peter Zijlstra]

On Tue, Dec 17, 2024 at 08:43:26AM +1030, Qu Wenruo wrote:
> 
> 
> 在 2024/12/13 19:36, Peter Zijlstra 写道:
> > On Thu, Dec 12, 2024 at 10:46:18AM -0600, Roger L. Beckermeyer III wrote:
> > > Adds rb_find_add_cached() as a helper function for use with
> > > red-black trees. Used in btrfs to reduce boilerplate code.
> > > 
> > > Suggested-by: Josef Bacik <josef@toxicpanda.com>
> > > Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
> > 
> > Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>
> 
> I guess it's fine to merge this change through btrfs tree?

Yeah, I think so. I don't think there's anything else pending for this
file -- its not touched much.

> 
> Just curious about the existing cmp() and less() functions, as they only
> accept the exist node as const.
> 
> I'm wondering if this is intentional to allow the less/cmp() functions
> to modify the new node if needed.
> As I normally assume such cmp()/less() should never touch any node nor
> its entries.

Oh yeah, they probably should not. I think it's just because the
callchain as a whole does not have const on the new node (for obvious
raisins), and I failed to put it on for the comparators.

You could add it (and fix up the whole tree) and see if anything comes
apart.

Re: [PATCH 1/6] rbtree: add rb_find_add_cached() to rbtree.h

[Qu Wenruo]

在 2024/12/17 08:52, Peter Zijlstra 写道:
> On Tue, Dec 17, 2024 at 08:43:26AM +1030, Qu Wenruo wrote:
>>
>>
>> 在 2024/12/13 19:36, Peter Zijlstra 写道:
>>> On Thu, Dec 12, 2024 at 10:46:18AM -0600, Roger L. Beckermeyer III wrote:
>>>> Adds rb_find_add_cached() as a helper function for use with
>>>> red-black trees. Used in btrfs to reduce boilerplate code.
>>>>
>>>> Suggested-by: Josef Bacik <josef@toxicpanda.com>
>>>> Signed-off-by: Roger L. Beckermeyer III <beckerlee3@gmail.com>
>>>
>>> Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>
>>
>> I guess it's fine to merge this change through btrfs tree?
> 
> Yeah, I think so. I don't think there's anything else pending for this
> file -- its not touched much.
> 
>>
>> Just curious about the existing cmp() and less() functions, as they only
>> accept the exist node as const.
>>
>> I'm wondering if this is intentional to allow the less/cmp() functions
>> to modify the new node if needed.
>> As I normally assume such cmp()/less() should never touch any node nor
>> its entries.
> 
> Oh yeah, they probably should not. I think it's just because the
> callchain as a whole does not have const on the new node (for obvious
> raisins), and I failed to put it on for the comparators.
> 
> You could add it (and fix up the whole tree) and see if anything comes
> apart.
> 
Thanks for confirming this.

I'll make the cmp() for the new helper to accept all const parameter, 
and give a try to do a tree-wide cleanup to make existing cmp/less() to 
accept all const parameters. (pretty sure a lot of things will fall 
apart though).

Thanks,
Qu