linux-kernel - Re: [PATCH 1/6] rbtree: add rb_find_add

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <ad36347a-14a5-41d4-82d5-f557a0a7f08c@gmx.com>
Date: Tue, 17 Dec 2024 08:43:26 +1030
From: Qu Wenruo <quwenruo.btrfs@....com>
To: Peter Zijlstra <peterz@...radead.org>,
 "Roger L. Beckermeyer III" <beckerlee3@...il.com>
Cc: dsterba@...e.cz, oleg@...hat.com, mhiramat@...nel.org,
 linux-kernel@...r.kernel.org, josef@...icpanda.com,
 linux-btrfs@...r.kernel.org, lkp@...el.com
Subject: Re: [PATCH 1/6] rbtree: add rb_find_add_cached() to rbtree.h



在 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@...icpanda.com>
>> Signed-off-by: Roger L. Beckermeyer III <beckerlee3@...il.com>
>
> Acked-by: Peter Zijlstra (Intel) <peterz@...radead.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
>>
>