Re: [PATCH v2 5/7] rbtree, uprobes: Use rbtree helpers

[Davidlohr Bueso]

On Mon, 25 Jan 2021, Peter Zijlstra wrote:


Reduce rbtree boilerplate by using the new helpers.


This reminds me of:

https://lore.kernel.org/lkml/20200207180305.11092-6-d...@stgolabs.net/

Would a walk optimization (list+rbtree) serve here? Not sure how big
the uprobes_trees gets.

Thanks,
Davidlohr

Re: [PATCH v2 5/7] rbtree, uprobes: Use rbtree helpers

[Peter Zijlstra]

On Mon, Jan 25, 2021 at 09:59:49PM -0800, Davidlohr Bueso wrote:
> On Mon, 25 Jan 2021, Peter Zijlstra wrote:
> 
> > Reduce rbtree boilerplate by using the new helpers.
> 
> This reminds me of:
> 
> https://lore.kernel.org/lkml/20200207180305.11092-6-d...@stgolabs.net/
> 
> Would a walk optimization (list+rbtree) serve here? Not sure how big
> the uprobes_trees gets.

Oh, that's patch set is horrible.. You can do a linked list with the
unused node pointers directly.

  https://en.wikipedia.org/wiki/Threaded_binary_tree

So instead of using NULL for the empty rb_{left,right} pointers, use
pointers with the LSB set to differentiate them from regular leaf
pointers.

Other than that, threaded rb-trees would be awesome. I've meant to
implement them a number of times but never had the time to do the
tree-wide clean up of the rb_tree API to enable them.

[PATCH v2 5/7] rbtree, uprobes: Use rbtree helpers

[Peter Zijlstra]

Reduce rbtree boilerplate by using the new helpers.

Signed-off-by: Peter Zijlstra (Intel) 
---
 kernel/events/uprobes.c |   82 +++-
 1 file changed, 40 insertions(+), 42 deletions(-)

--- a/kernel/events/uprobes.c
+++ b/kernel/events/uprobes.c
@@ -619,41 +619,56 @@ static void put_uprobe(struct uprobe *up
}
 }
 
-static int match_uprobe(struct uprobe *l, struct uprobe *r)
+static __always_inline
+int uprobe_cmp(const struct inode *l_inode, const loff_t l_offset,
+  const struct uprobe *r)
 {
-   if (l->inode < r->inode)
+   if (l_inode < r->inode)
return -1;
 
-   if (l->inode > r->inode)
+   if (l_inode > r->inode)
return 1;
 
-   if (l->offset < r->offset)
+   if (l_offset < r->offset)
return -1;
 
-   if (l->offset > r->offset)
+   if (l_offset > r->offset)
return 1;
 
return 0;
 }
 
+#define __node_2_uprobe(node) \
+   rb_entry((node), struct uprobe, rb_node)
+
+struct __uprobe_key {
+   struct inode *inode;
+   loff_t offset;
+};
+
+static inline int __uprobe_cmp_key(const void *key, const struct rb_node *b)
+{
+   const struct __uprobe_key *a = key;
+   return uprobe_cmp(a->inode, a->offset, __node_2_uprobe(b));
+}
+
+static inline int __uprobe_cmp(struct rb_node *a, const struct rb_node *b)
+{
+   struct uprobe *u = __node_2_uprobe(a);
+   return uprobe_cmp(u->inode, u->offset, __node_2_uprobe(b));
+}
+
 static struct uprobe *__find_uprobe(struct inode *inode, loff_t offset)
 {
-   struct uprobe u = { .inode = inode, .offset = offset };
-   struct rb_node *n = uprobes_tree.rb_node;
-   struct uprobe *uprobe;
-   int match;
+   struct __uprobe_key key = {
+   .inode = inode,
+   .offset = offset,
+   };
+   struct rb_node *node = rb_find(, _tree, __uprobe_cmp_key);
+
+   if (node)
+   return __node_2_uprobe(node);
 
-   while (n) {
-   uprobe = rb_entry(n, struct uprobe, rb_node);
-   match = match_uprobe(, uprobe);
-   if (!match)
-   return get_uprobe(uprobe);
-
-   if (match < 0)
-   n = n->rb_left;
-   else
-   n = n->rb_right;
-   }
return NULL;
 }
 
@@ -674,32 +689,15 @@ static struct uprobe *find_uprobe(struct
 
 static struct uprobe *__insert_uprobe(struct uprobe *uprobe)
 {
-   struct rb_node **p = _tree.rb_node;
-   struct rb_node *parent = NULL;
-   struct uprobe *u;
-   int match;
-
-   while (*p) {
-   parent = *p;
-   u = rb_entry(parent, struct uprobe, rb_node);
-   match = match_uprobe(uprobe, u);
-   if (!match)
-   return get_uprobe(u);
-
-   if (match < 0)
-   p = >rb_left;
-   else
-   p = >rb_right;
+   struct rb_node *node;
 
-   }
+   node = rb_find_add(>rb_node, _tree, __uprobe_cmp);
+   if (node)
+   return get_uprobe(__node_2_uprobe(node));
 
-   u = NULL;
-   rb_link_node(>rb_node, parent, p);
-   rb_insert_color(>rb_node, _tree);
/* get access + creation ref */
refcount_set(>ref, 2);
-
-   return u;
+   return NULL;
 }
 
 /*