On Mon, Jul 15, 2024 at 4:21 AM Peter Zijlstra [off-list ref] wrote:

On Fri, Jul 12, 2024 at 01:23:43PM -0700, Andrii Nakryiko wrote:

quoted

On Thu, Jul 11, 2024 at 4:07 AM Peter Zijlstra [off-list ref] wrote:

quoted

Much like latch_tree, add two RCU methods for the regular RB-tree,
which can be used in conjunction with a seqcount to provide lockless
lookups.

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Reviewed-by: Masami Hiramatsu (Google) <mhiramat@kernel.org>
---
 include/linux/rbtree.h |   67 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 67 insertions(+)

--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h

@@ -245,6 +245,42 @@ rb_find_add(struct rb_node *node, struct
 }

 /**
+ * rb_find_add_rcu() - 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
+ *
+ * Adds a Store-Release for link_node.
+ *
+ * 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_rcu(struct rb_node *node, struct rb_root *tree,
+               int (*cmp)(struct rb_node *, const struct rb_node *))

I don't get the point of the RCU version of rb_find_add as RCU itself
doesn't provide enough protection for modification of the tree, right?
So in uprobes code you do rb_find_add_rcu() under uprobes_treelock +
uprobes_seqcount locks. Wouldn't it be just as fine to do plain
non-RCU rb_find_add() in that case? After all, you do plain rb_erase
under the same set of locks.

So what's the point of this one?

The store-release when adding it to the tree. Without that it becomes
possible to find the entry while the entry itself is incomplete.

Eg. something like:

 entry.foo = A
 rb_find_add(&entry->node, &my_tree, my_cmp);

vs

 rcu_read_lock();
 entry = rb_find_rcu(...);
 assert(entry->foo == A);

might fail. Because there is nothing ordering the foo store and the
rb-node add.

Ah, I see, thanks for the explanation. That's what "Adds a
Store-Release for link_node." in the comment means, I see.