Skip to contentSkip to conversation

Generic RB-tree helpers

RFC PATCH Superseded Peter Zijlstra 4 participants 16 messages Apr 29, 2020 – Apr 30, 2020

Subsystems (6)

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore

Peter Zijlstra

author maintainer
#0 lore raw

cover Generic RB-tree helpers

An attempt to reduce the rb-tree boiler place..

author maintainer
#1 lore raw

RFC PATCH 1/7 rbtree: Add generic add and find helpers

I've always been bothered by the endless (fragile) boilerplate for rbtree, and I recently wrote some rbtree helpers for objtool and figured I should lift them into the kernel and use them more widely.

Provide:

partial-order; less() based:
- rb_add(): add a new entry to the rbtree
- rb_add_cached(): like rb_add(), but for a rb_root_cached

total-order; cmp() based:
- rb_find(): find an entry in an rbtree
- rb_find_first(): find the first (leftmost) matching entry
- rb_next_match(): continue from rb_find_first()
- rb_for_each(): for loop with rb_find_first() / rb_next_match()

Also make rb_add_cached() / rb_erase_cached() return true when leftmost.

Inlining and constant propagation should see the compiler inline the whole thing, including the various compare functions.

---
 include/linux/rbtree.h       |  127 +++++++++++++++++++++++++++++++++++++++++-
 tools/include/linux/rbtree.h |  129 ++++++++++++++++++++++++++++++++++++++++++-
 tools/objtool/elf.c          |   63 ++-------------------
 3 files changed, 257 insertions(+), 62 deletions(-)
include/linux/rbtree.h +125 -2
@@ -141,12 +141,18 @@ static inline void rb_insert_color_cache
 	rb_insert_color(node, &root->rb_root);
 }
 
-static inline void rb_erase_cached(struct rb_node *node,
+static inline bool rb_erase_cached(struct rb_node *node,
 				   struct rb_root_cached *root)
 {
-	if (root->rb_leftmost == node)
+	bool leftmost = false;
+
+	if (root->rb_leftmost == node) {
 		root->rb_leftmost = rb_next(node);
+		leftmost = true;
+	}
 	rb_erase(node, &root->rb_root);
+
+	return leftmost;
 }
 
 static inline void rb_replace_node_cached(struct rb_node *victim,
@@ -158,4 +164,121 @@ static inline void rb_replace_node_cache
 	rb_replace_node(victim, new, &root->rb_root);
 }
 
+static inline bool rb_add_cached(struct rb_root_cached *tree, struct rb_node *node,
+				 bool (*less)(struct rb_node *, const struct rb_node *))
+{
+	struct rb_node **link = &tree->rb_root.rb_node;
+	struct rb_node *parent = NULL;
+	bool leftmost = true;
+
+	while (*link) {
+		parent = *link;
+		if (less(node, parent)) {
+			link = &parent->rb_left;
+		} else {
+			link = &parent->rb_right;
+			leftmost = false;
+		}
+	}
+
+	rb_link_node(node, parent, link);
+	rb_insert_color_cached(node, tree, leftmost);
+
+	return leftmost;
+}
+
+static inline void rb_add(struct rb_root *tree, struct rb_node *node,
+			  bool (*less)(struct rb_node *, const struct rb_node *))
+{
+	struct rb_node **link = &tree->rb_node;
+	struct rb_node *parent = NULL;
+
+	while (*link) {
+		parent = *link;
+		if (less(node, parent))
+			link = &parent->rb_left;
+		else
+			link = &parent->rb_right;
+	}
+
+	rb_link_node(node, parent, link);
+	rb_insert_color(node, tree);
+}
+
+static inline struct rb_node *rb_find_add(struct rb_root *tree, struct rb_node *node,
+			  int (*cmp)(struct rb_node *, const struct rb_node *))
+{
+	struct rb_node **link = &tree->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;
+		else
+			return parent;
+	}
+
+	rb_link_node(node, parent, link);
+	rb_insert_color(node, tree);
+	return NULL;
+}
+
+static inline struct rb_node *rb_find(struct rb_root *tree, const void *key,
+				      int (*cmp)(const void *key, const struct rb_node *))
+{
+	struct rb_node *node = tree->rb_node;
+
+	while (node) {
+		int c = cmp(key, node);
+		if (c < 0) {
+			node = node->rb_left;
+		} else if (c > 0) {
+			node = node->rb_right;
+		} else
+			return node;
+	}
+
+	return NULL;
+}
+
+static inline struct rb_node *rb_find_first(struct rb_root *tree, const void *key,
+					    int (*cmp)(const void *key, const struct rb_node *))
+{
+	struct rb_node *node = tree->rb_node;
+	struct rb_node *match = NULL;
+
+	while (node) {
+		int c = cmp(key, node);
+		if (c <= 0) {
+			if (!c)
+				match = node;
+			node = node->rb_left;
+		} else if (c > 0) {
+			node = node->rb_right;
+		}
+	}
+
+	return match;
+}
+
+static inline struct rb_node *rb_next_match(struct rb_node *node, const void *key,
+					    int (*cmp)(const void *key, const struct rb_node *))
+{
+	node = rb_next(node);
+	if (node && cmp(key, node))
+		node = NULL;
+	return node;
+}
+
+#define rb_for_each(tree, node, key, cmp) \
+	for ((node) = rb_find_first((tree), (key), (cmp)); \
+	     (node); (node) = rb_next_match((node), (key), (cmp)))
+
+
 #endif	/* _LINUX_RBTREE_H */
tools/include/linux/rbtree.h +126 -3

142 lines not on this page · raw message

tools/objtool/elf.c +6 -57

81 lines not on this page · raw message

Reviewed-by on v1 1/7
#2 lore raw

Re: [RFC][PATCH 1/7] rbtree: Add generic add and find helpers

Hi Peter,

Quoted 16 lines · Peter Zijlstra

I've always been bothered by the endless (fragile) boilerplate for rbtree, and I recently wrote some rbtree helpers for objtool and figured I should lift them into the kernel and use them more widely.

Provide:

partial-order; less() based:
- rb_add(): add a new entry to the rbtree
- rb_add_cached(): like rb_add(), but for a rb_root_cached

total-order; cmp() based:
- rb_find(): find an entry in an rbtree
- rb_find_first(): find the first (leftmost) matching entry
- rb_next_match(): continue from rb_find_first()
- rb_for_each(): for loop with rb_find_first() / rb_next_match()

Quoted 5 lines

Also make rb_add_cached() / rb_erase_cached() return true when leftmost.

Inlining and constant propagation should see the compiler inline the whole thing, including the various compare functions.

I really like the idea of this change. Also,I think it opens avenues for converting some users which had previously been avoiding raw rbtrees seemingly only because they didn't want to write this boilerplate.

Few questions:

- Adding the rb_add_cached() / rb_erase_cached() return value looks like it almost belongs to a separate patch. Is this only used in patch 3/7 (sched/deadline) or did I miss other uses ? Not objecting to it, but it wasn't obvious to me when reading the patch what the return value was for.

- Have you considered passing a cmp() function to rb_add() and rb_add_cached(), and having these test cmp() < 0 rather than less() ? I figure every user will need to have a cmp() function, so it'd be nicer if they didn't also need a less() function, if the generated code is similar (if you checked and rejected it because of bad code, please just say so).

I also looked at the other commits in the series, making use of the helpers, and they seem very reasonable but I did not give them as thorough a look at this one.

Quoted 385 lines
---
 include/linux/rbtree.h       |  127 +++++++++++++++++++++++++++++++++++++++++-
 tools/include/linux/rbtree.h |  129 ++++++++++++++++++++++++++++++++++++++++++-
 tools/objtool/elf.c          |   63 ++-------------------
 3 files changed, 257 insertions(+), 62 deletions(-)
include/linux/rbtree.h +125 -2
@@ -141,12 +141,18 @@ static inline void rb_insert_color_cache
 	rb_insert_color(node, &root->rb_root);
 }
 
-static inline void rb_erase_cached(struct rb_node *node,
+static inline bool rb_erase_cached(struct rb_node *node,
 				   struct rb_root_cached *root)
 {
-	if (root->rb_leftmost == node)
+	bool leftmost = false;
+
+	if (root->rb_leftmost == node) {
 		root->rb_leftmost = rb_next(node);
+		leftmost = true;
+	}
 	rb_erase(node, &root->rb_root);
+
+	return leftmost;
 }
 
 static inline void rb_replace_node_cached(struct rb_node *victim,
@@ -158,4 +164,121 @@ static inline void rb_replace_node_cache
 	rb_replace_node(victim, new, &root->rb_root);
 }
 
+static inline bool rb_add_cached(struct rb_root_cached *tree, struct rb_node *node,
+				 bool (*less)(struct rb_node *, const struct rb_node *))
+{
+	struct rb_node **link = &tree->rb_root.rb_node;
+	struct rb_node *parent = NULL;
+	bool leftmost = true;
+
+	while (*link) {
+		parent = *link;
+		if (less(node, parent)) {
+			link = &parent->rb_left;
+		} else {
+			link = &parent->rb_right;
+			leftmost = false;
+		}
+	}
+
+	rb_link_node(node, parent, link);
+	rb_insert_color_cached(node, tree, leftmost);
+
+	return leftmost;
+}
+
+static inline void rb_add(struct rb_root *tree, struct rb_node *node,
+			  bool (*less)(struct rb_node *, const struct rb_node *))
+{
+	struct rb_node **link = &tree->rb_node;
+	struct rb_node *parent = NULL;
+
+	while (*link) {
+		parent = *link;
+		if (less(node, parent))
+			link = &parent->rb_left;
+		else
+			link = &parent->rb_right;
+	}
+
+	rb_link_node(node, parent, link);
+	rb_insert_color(node, tree);
+}
+
+static inline struct rb_node *rb_find_add(struct rb_root *tree, struct rb_node *node,
+			  int (*cmp)(struct rb_node *, const struct rb_node *))
+{
+	struct rb_node **link = &tree->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;
+		else
+			return parent;
+	}
+
+	rb_link_node(node, parent, link);
+	rb_insert_color(node, tree);
+	return NULL;
+}
+
+static inline struct rb_node *rb_find(struct rb_root *tree, const void *key,
+				      int (*cmp)(const void *key, const struct rb_node *))
+{
+	struct rb_node *node = tree->rb_node;
+
+	while (node) {
+		int c = cmp(key, node);
+		if (c < 0) {
+			node = node->rb_left;
+		} else if (c > 0) {
+			node = node->rb_right;
+		} else
+			return node;
+	}
+
+	return NULL;
+}
+
+static inline struct rb_node *rb_find_first(struct rb_root *tree, const void *key,
+					    int (*cmp)(const void *key, const struct rb_node *))
+{
+	struct rb_node *node = tree->rb_node;
+	struct rb_node *match = NULL;
+
+	while (node) {
+		int c = cmp(key, node);
+		if (c <= 0) {
+			if (!c)
+				match = node;
+			node = node->rb_left;
+		} else if (c > 0) {
+			node = node->rb_right;
+		}
+	}
+
+	return match;
+}
+
+static inline struct rb_node *rb_next_match(struct rb_node *node, const void *key,
+					    int (*cmp)(const void *key, const struct rb_node *))
+{
+	node = rb_next(node);
+	if (node && cmp(key, node))
+		node = NULL;
+	return node;
+}
+
+#define rb_for_each(tree, node, key, cmp) \
+	for ((node) = rb_find_first((tree), (key), (cmp)); \
+	     (node); (node) = rb_next_match((node), (key), (cmp)))
+
+
 #endif	/* _LINUX_RBTREE_H */
tools/include/linux/rbtree.h +126 -3
@@ -135,12 +135,18 @@ static inline void rb_insert_color_cache
 	rb_insert_color(node, &root->rb_root);
 }
 
-static inline void rb_erase_cached(struct rb_node *node,
+static inline bool rb_erase_cached(struct rb_node *node,
 				   struct rb_root_cached *root)
 {
-	if (root->rb_leftmost == node)
+	bool leftmost = false;
+
+	if (root->rb_leftmost == node) {
 		root->rb_leftmost = rb_next(node);
+		leftmost = true;
+	}
 	rb_erase(node, &root->rb_root);
+
+	return leftmost;
 }
 
 static inline void rb_replace_node_cached(struct rb_node *victim,
@@ -152,4 +158,121 @@ static inline void rb_replace_node_cache
 	rb_replace_node(victim, new, &root->rb_root);
 }
 
-#endif /* __TOOLS_LINUX_PERF_RBTREE_H */
+static inline bool rb_add_cached(struct rb_root_cached *tree, struct rb_node *node,
+				 bool (*less)(struct rb_node *, const struct rb_node *))
+{
+	struct rb_node **link = &tree->rb_root.rb_node;
+	struct rb_node *parent = NULL;
+	bool leftmost = true;
+
+	while (*link) {
+		parent = *link;
+		if (less(node, parent)) {
+			link = &parent->rb_left;
+		} else {
+			link = &parent->rb_right;
+			leftmost = false;
+		}
+	}
+
+	rb_link_node(node, parent, link);
+	rb_insert_color_cached(node, tree, leftmost);
+
+	return leftmost;
+}
+
+static inline void rb_add(struct rb_root *tree, struct rb_node *node,
+			  bool (*less)(struct rb_node *, const struct rb_node *))
+{
+	struct rb_node **link = &tree->rb_node;
+	struct rb_node *parent = NULL;
+
+	while (*link) {
+		parent = *link;
+		if (less(node, parent))
+			link = &parent->rb_left;
+		else
+			link = &parent->rb_right;
+	}
+
+	rb_link_node(node, parent, link);
+	rb_insert_color(node, tree);
+}
+
+static inline struct rb_node *rb_find_add(struct rb_root *tree, struct rb_node *node,
+			  int (*cmp)(struct rb_node *, const struct rb_node *))
+{
+	struct rb_node **link = &tree->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;
+		else
+			return parent;
+	}
+
+	rb_link_node(node, parent, link);
+	rb_insert_color(node, tree);
+	return NULL;
+}
+
+static inline struct rb_node *rb_find(struct rb_root *tree, const void *key,
+				      int (*cmp)(const void *key, const struct rb_node *))
+{
+	struct rb_node *node = tree->rb_node;
+
+	while (node) {
+		int c = cmp(key, node);
+		if (c < 0) {
+			node = node->rb_left;
+		} else if (c > 0) {
+			node = node->rb_right;
+		} else
+			return node;
+	}
+
+	return NULL;
+}
+
+static inline struct rb_node *rb_find_first(struct rb_root *tree, const void *key,
+					    int (*cmp)(const void *key, const struct rb_node *))
+{
+	struct rb_node *node = tree->rb_node;
+	struct rb_node *match = NULL;
+
+	while (node) {
+		int c = cmp(key, node);
+		if (c <= 0) {
+			if (!c)
+				match = node;
+			node = node->rb_left;
+		} else if (c > 0) {
+			node = node->rb_right;
+		}
+	}
+
+	return match;
+}
+
+static inline struct rb_node *rb_next_match(struct rb_node *node, const void *key,
+					    int (*cmp)(const void *key, const struct rb_node *))
+{
+	node = rb_next(node);
+	if (node && cmp(key, node))
+		node = NULL;
+	return node;
+}
+
+#define rb_for_each(tree, node, key, cmp) \
+	for ((node) = rb_find_first((tree), (key), (cmp)); \
+	     (node); (node) = rb_next_match((node), (key), (cmp)))
+
+
+#endif	/* _LINUX_RBTREE_H */
tools/objtool/elf.c +6 -57
@@ -43,75 +43,24 @@ static void elf_hash_init(struct hlist_h
 #define elf_hash_for_each_possible(name, obj, member, key)			\
 	hlist_for_each_entry(obj, &name[hash_min(key, elf_hash_bits())], member)
 
-static void rb_add(struct rb_root *tree, struct rb_node *node,
-		   int (*cmp)(struct rb_node *, const struct rb_node *))
-{
-	struct rb_node **link = &tree->rb_node;
-	struct rb_node *parent = NULL;
-
-	while (*link) {
-		parent = *link;
-		if (cmp(node, parent) < 0)
-			link = &parent->rb_left;
-		else
-			link = &parent->rb_right;
-	}
-
-	rb_link_node(node, parent, link);
-	rb_insert_color(node, tree);
-}
-
-static struct rb_node *rb_find_first(struct rb_root *tree, const void *key,
-			       int (*cmp)(const void *key, const struct rb_node *))
-{
-	struct rb_node *node = tree->rb_node;
-	struct rb_node *match = NULL;
-
-	while (node) {
-		int c = cmp(key, node);
-		if (c <= 0) {
-			if (!c)
-				match = node;
-			node = node->rb_left;
-		} else if (c > 0) {
-			node = node->rb_right;
-		}
-	}
-
-	return match;
-}
-
-static struct rb_node *rb_next_match(struct rb_node *node, const void *key,
-				    int (*cmp)(const void *key, const struct rb_node *))
-{
-	node = rb_next(node);
-	if (node && cmp(key, node))
-		node = NULL;
-	return node;
-}
-
-#define rb_for_each(tree, node, key, cmp) \
-	for ((node) = rb_find_first((tree), (key), (cmp)); \
-	     (node); (node) = rb_next_match((node), (key), (cmp)))
-
-static int symbol_to_offset(struct rb_node *a, const struct rb_node *b)
+static bool symbol_to_offset(struct rb_node *a, const struct rb_node *b)
 {
 	struct symbol *sa = rb_entry(a, struct symbol, node);
 	struct symbol *sb = rb_entry(b, struct symbol, node);
 
 	if (sa->offset < sb->offset)
-		return -1;
+		return true;
 	if (sa->offset > sb->offset)
-		return 1;
+		return false;
 
 	if (sa->len < sb->len)
-		return -1;
+		return true;
 	if (sa->len > sb->len)
-		return 1;
+		return false;
 
 	sa->alias = sb;
 
-	return 0;
+	return false;
 }
 
 static int symbol_by_offset(const void *key, const struct rb_node *node)
Signature · 2 lines
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.
author maintainer
#3 lore raw

Re: [RFC][PATCH 1/7] rbtree: Add generic add and find helpers

Quoted 18 lines · Michel Lespinasse

Hi Peter,

Quoted 15 lines · Peter Zijlstra

I've always been bothered by the endless (fragile) boilerplate for rbtree, and I recently wrote some rbtree helpers for objtool and figured I should lift them into the kernel and use them more widely.

Provide:

partial-order; less() based:
- rb_add(): add a new entry to the rbtree
- rb_add_cached(): like rb_add(), but for a rb_root_cached

total-order; cmp() based:
- rb_find(): find an entry in an rbtree
- rb_find_first(): find the first (leftmost) matching entry
- rb_next_match(): continue from rb_find_first()
- rb_for_each(): for loop with rb_find_first() / rb_next_match()

I appear to have failed to mention rb_find_add(), which is a bit of a specialty, but I could imagine there being more like it the many rbtree users out there (I count 300+ rb_link_node occurences).

Quoted 10 lines
Quoted 6 lines

Also make rb_add_cached() / rb_erase_cached() return true when leftmost.

Inlining and constant propagation should see the compiler inline the whole thing, including the various compare functions.

I really like the idea of this change. Also,I think it opens avenues for converting some users which had previously been avoiding raw rbtrees seemingly only because they didn't want to write this boilerplate.

Yeah; our current interface mandates you _understand_ binary trees, I can imagine that's a step too far for some (sadly).

Quoted 7 lines

Few questions:

- Adding the rb_add_cached() / rb_erase_cached() return value looks like it almost belongs to a separate patch. Is this only used in patch 3/7 (sched/deadline) or did I miss other uses ? Not objecting to it, but it wasn't obvious to me when reading the patch what the return value was for.

I can certainly add it in a separate patch; as might be evident from the (lack) of changelogs on the whole, I basically split and posted the thing the moment it booted. I figured I shouldn't sink more time into it if people were going to hate it ;-)

Quoted 6 lines

- Have you considered passing a cmp() function to rb_add() and rb_add_cached(), and having these test cmp() < 0 rather than less() ? I figure every user will need to have a cmp() function, so it'd be nicer if they didn't also need a less() function, if the generated code is similar (if you checked and rejected it because of bad code, please just say so).

I did consider it; in fact I my original helpers had that.

The reaosn I went with less() over cmp() is that the add() vs find() function signatures:

  bool (*less)(struct rb_node *, const struct rb_node *);
  int (*cmp)(const void *, const struct rb_node *);

differ anyway in the left-hand argument; this is 'fixable' when you use an (on-stack) dummy object for find (as uprobes does), but that doesn't always work, esp. when the object is big. And given you need two functions anyway, I figured it was useful to name them differently.

If you've looked at the other patches a bit, you'll see I've implemented both functions as 'trivial' wrappers around a single compare function in many cases.

Quoted 1 line

Thanks, I suppose I'll go brush this up a bit more then.

author maintainer
#4 lore raw

Re: [RFC][PATCH 1/7] rbtree: Add generic add and find helpers

Quoted 17 lines · Peter Zijlstra
Quoted 6 lines · Michel Lespinasse

- Have you considered passing a cmp() function to rb_add() and rb_add_cached(), and having these test cmp() < 0 rather than less() ? I figure every user will need to have a cmp() function, so it'd be nicer if they didn't also need a less() function, if the generated code is similar (if you checked and rejected it because of bad code, please just say so).

I did consider it; in fact I my original helpers had that.

The reaosn I went with less() over cmp() is that the add() vs find() function signatures:

  bool (*less)(struct rb_node *, const struct rb_node *);
  int (*cmp)(const void *, const struct rb_node *);
Quoted 8 lines

differ anyway in the left-hand argument; this is 'fixable' when you use an (on-stack) dummy object for find (as uprobes does), but that doesn't always work, esp. when the object is big. And given you need two functions anyway, I figured it was useful to name them differently.

If you've looked at the other patches a bit, you'll see I've implemented both functions as 'trivial' wrappers around a single compare function in many cases.

I just realized I'd already done all this at some point ;-) See rbtree_latch.h. Clearly I failed to realize the full potential back when I did that.

maintainer
#5 lore raw

Re: [RFC][PATCH 1/7] rbtree: Add generic add and find helpers

In reply to Peter Zijlstra

Hi,

Quoted 34 lines · Peter Zijlstra

I've always been bothered by the endless (fragile) boilerplate for rbtree, and I recently wrote some rbtree helpers for objtool and figured I should lift them into the kernel and use them more widely.

Provide:

partial-order; less() based:
- rb_add(): add a new entry to the rbtree
- rb_add_cached(): like rb_add(), but for a rb_root_cached

total-order; cmp() based:
- rb_find(): find an entry in an rbtree
- rb_find_first(): find the first (leftmost) matching entry
- rb_next_match(): continue from rb_find_first()
- rb_for_each(): for loop with rb_find_first() / rb_next_match()

Also make rb_add_cached() / rb_erase_cached() return true when leftmost.

Inlining and constant propagation should see the compiler inline the whole thing, including the various compare functions.

---
 include/linux/rbtree.h       |  127 +++++++++++++++++++++++++++++++++++++++++-
 tools/include/linux/rbtree.h |  129 ++++++++++++++++++++++++++++++++++++++++++-
 tools/objtool/elf.c          |   63 ++-------------------
 3 files changed, 257 insertions(+), 62 deletions(-)
include/linux/rbtree.h +0 -0
@@ -141,12 +141,18 @@ static inline void rb_insert_color_cache
 	rb_insert_color(node, &root->rb_root);
 }

include/linux/rbtree.h static inline void rb_insert_color_cache · line 150

Quoted 10 lines
include/linux/rbtree.h +4 -2
 
-static inline void rb_erase_cached(struct rb_node *node,
+static inline bool rb_erase_cached(struct rb_node *node,
 				   struct rb_root_cached *root)
 {
-	if (root->rb_leftmost == node)
+	bool leftmost = false;
+
+	if (root->rb_leftmost == node) {
 		root->rb_leftmost = rb_next(node);

Think we need

if (root->rb_leftmost)

include/linux/rbtree.h static inline void rb_insert_color_cache · line 151

Quoted 1 line
include/linux/rbtree.h +1 -0
+		leftmost = true;

DEADLINE crashes w/o that.

include/linux/rbtree.h static inline void rb_insert_color_cache · line 156

Quoted 5 lines
include/linux/rbtree.h +3 -0
+	}
 	rb_erase(node, &root->rb_root);
+
+	return leftmost;
 }

The rest looks good to me.

Thanks,

Juri

#6 lore raw

Re: [RFC][PATCH 1/7] rbtree: Add generic add and find helpers

Quoted 18 lines · Juri Lelli
Quoted 5 lines
include/linux/rbtree.h +0 -0
@@ -141,12 +141,18 @@ static inline void rb_insert_color_cache
      rb_insert_color(node, &root->rb_root);
 }

include/linux/rbtree.h static inline void rb_insert_color_cache · line 150

Quoted 10 lines
include/linux/rbtree.h +4 -2
 
-static inline void rb_erase_cached(struct rb_node *node,
+static inline bool rb_erase_cached(struct rb_node *node,
                                 struct rb_root_cached *root)
 {
-     if (root->rb_leftmost == node)
+     bool leftmost = false;
+
+     if (root->rb_leftmost == node) {
              root->rb_leftmost = rb_next(node);

Think we need

Quoted 5 lines

if (root->rb_leftmost)

include/linux/rbtree.h static inline void rb_insert_color_cache · line 151

Quoted 1 line
include/linux/rbtree.h +1 -0
+             leftmost = true;

DEADLINE crashes w/o that.

I think Peter's code is correct; after removing the only node in an rbtree rb_leftmost should be NULL.

The issue appears to be in dequeue_pushable_dl_task unconditionally dereferencing the pointer returned by rb_first_cached(), which may be NULL. I'm not sure what the correct behavior is though, i.e. what dl_rq->earliest_dl.next should be set to if the rbtree ends up empty. Current code (before Peter's changes) preserves the existing dl_rq->earliest_dl.next value in that case, which seems very weird to me (and worthy of a comment if it's correct).

maintainer
#7 lore raw

Re: [RFC][PATCH 1/7] rbtree: Add generic add and find helpers

Quoted 19 lines · Michel Lespinasse
Quoted 18 lines · Juri Lelli
Quoted 5 lines
include/linux/rbtree.h +0 -0
@@ -141,12 +141,18 @@ static inline void rb_insert_color_cache
      rb_insert_color(node, &root->rb_root);
 }

include/linux/rbtree.h static inline void rb_insert_color_cache · line 150

Quoted 10 lines
include/linux/rbtree.h +4 -2
 
-static inline void rb_erase_cached(struct rb_node *node,
+static inline bool rb_erase_cached(struct rb_node *node,
                                 struct rb_root_cached *root)
 {
-     if (root->rb_leftmost == node)
+     bool leftmost = false;
+
+     if (root->rb_leftmost == node) {
              root->rb_leftmost = rb_next(node);

Think we need

Quoted 8 lines
Quoted 5 lines

if (root->rb_leftmost)

include/linux/rbtree.h static inline void rb_insert_color_cache · line 151

Quoted 1 line
include/linux/rbtree.h +1 -0
+             leftmost = true;

DEADLINE crashes w/o that.

I think Peter's code is correct; after removing the only node in an rbtree rb_leftmost should be NULL.

Indeed, I've only got the idea that Peter was thinking of using rb_erase_cached return value as an indication that new rb_leftmost is not NULL (and for example perform an update in DEADLINE earliest_dl).

I also had the impression that DEADLINE is actually the only consumer of that return value and so we were able to define its semantic.

Quoted 7 lines

The issue appears to be in dequeue_pushable_dl_task unconditionally dereferencing the pointer returned by rb_first_cached(), which may be NULL. I'm not sure what the correct behavior is though, i.e. what dl_rq->earliest_dl.next should be set to if the rbtree ends up empty. Current code (before Peter's changes) preserves the existing dl_rq->earliest_dl.next value in that case, which seems very weird to me (and worthy of a comment if it's correct).

But, yeah. Fixing things in DEADLINE code works for me as well. We could reset it to 0 (initial value), but I now actually wonder if places where that is consumed are actually OK. Different discussion, though. :-)

Thanks,

Juri

author maintainer
#8 lore raw

Re: [RFC][PATCH 1/7] rbtree: Add generic add and find helpers

In reply to Michel Lespinasse
Quoted 19 lines · Michel Lespinasse
Quoted 18 lines · Juri Lelli
Quoted 5 lines
include/linux/rbtree.h +0 -0
@@ -141,12 +141,18 @@ static inline void rb_insert_color_cache
      rb_insert_color(node, &root->rb_root);
 }

include/linux/rbtree.h static inline void rb_insert_color_cache · line 150

Quoted 10 lines
include/linux/rbtree.h +4 -2
 
-static inline void rb_erase_cached(struct rb_node *node,
+static inline bool rb_erase_cached(struct rb_node *node,
                                 struct rb_root_cached *root)
 {
-     if (root->rb_leftmost == node)
+     bool leftmost = false;
+
+     if (root->rb_leftmost == node) {
              root->rb_leftmost = rb_next(node);

Think we need

Quoted 5 lines
Quoted 5 lines

if (root->rb_leftmost)

include/linux/rbtree.h static inline void rb_insert_color_cache · line 151

Quoted 1 line
include/linux/rbtree.h +1 -0
+             leftmost = true;

DEADLINE crashes w/o that.

Clearly boot testing doesn't cover that..

Quoted 6 lines

I think Peter's code is correct; after removing the only node in an rbtree rb_leftmost should be NULL.

The issue appears to be in dequeue_pushable_dl_task unconditionally dereferencing the pointer returned by rb_first_cached(), which may be NULL.

Oh right.. silly me.

So yes, those rb_add_cached() / rb_erase_cached() return values are (currently) only used by deadline. Deadline keeps a leftmost based value cache and 'needs' this signal to update it; I can imagine there being others, I didn't look at the many (~70) other users of rb_erase_cached().

I briefly considered having rb_erase_cached() return the 'struct rb_node *' of the new leftmost; that would naturally return NULL for the empty tree. Maybe I should still do that -- see below.

Another thing I noticed is that I'm inconsistend with argument order; rb_erase_cached(node, tree) vs rb_add_cached(tree, node). I'll go make the new stuff use the 'wrong' order stuff too.

---

include/linux/rbtree.h +7 -6
@@ -141,8 +141,8 @@ static inline void rb_insert_color_cache
 	rb_insert_color(node, &root->rb_root);
 }
 
-static inline bool rb_erase_cached(struct rb_node *node,
-				   struct rb_root_cached *root)
+static inline struct rb_node *
+rb_erase_cached(struct rb_node *node, struct rb_root_cached *root)
 {
 	bool leftmost = false;
 
@@ -152,7 +152,7 @@ static inline bool rb_erase_cached(struc
 	}
 	rb_erase(node, &root->rb_root);
 
-	return leftmost;
+	return leftmost ? root->rb_leftmost : NULL;
 }
 
 static inline void rb_replace_node_cached(struct rb_node *victim,
@@ -164,8 +164,9 @@ static inline void rb_replace_node_cache
 	rb_replace_node(victim, new, &root->rb_root);
 }
 
-static inline bool rb_add_cached(struct rb_root_cached *tree, struct rb_node *node,
-				 bool (*less)(struct rb_node *, const struct rb_node *))
+static inline struct rb_node *
+rb_add_cached(struct rb_root_cached *tree, struct rb_node *node, bool
+	      (*less)(struct rb_node *, const struct rb_node *))
 {
 	struct rb_node **link = &tree->rb_root.rb_node;
 	struct rb_node *parent = NULL;
@@ -184,7 +185,7 @@ static inline bool rb_add_cached(struct
 	rb_link_node(node, parent, link);
 	rb_insert_color_cached(node, tree, leftmost);
 
-	return leftmost;
+	return leftmost ? node : NULL;
 }
 
 static inline void rb_add(struct rb_root *tree, struct rb_node *node,
kernel/sched/deadline.c +10 -4
@@ -454,10 +454,14 @@ static inline bool __pushable_less(struc
  */
 static void enqueue_pushable_dl_task(struct rq *rq, struct task_struct *p)
 {
+	struct rb_node *leftmost;
+
 	BUG_ON(!RB_EMPTY_NODE(&p->pushable_dl_tasks));
 
-	if (rb_add_cached(&rq->dl.pushable_dl_tasks_root, &p->pushable_dl_tasks,
-			  __pushable_less))
+	leftmost = rb_add_cached(&rq->dl.pushable_dl_tasks_root,
+				 &p->pushable_dl_tasks,
+				 __pushable_less);
+	if (leftmost)
 		rq->dl.earliest_dl.next = p->dl.deadline;
 }
 
@@ -465,12 +469,14 @@ static void dequeue_pushable_dl_task(str
 {
 	struct dl_rq *dl_rq = &rq->dl;
 	struct rb_root_cached *root = &dl_rq->pushable_dl_tasks_root;
+	struct rb_node *leftmost;
 
 	if (RB_EMPTY_NODE(&p->pushable_dl_tasks))
 		return;
 
-	if (rb_erase_cached(&p->pushable_dl_tasks, root))
-		dl_rq->earliest_dl.next = __node_2_pdl(rb_first_cached(root))->dl.deadline;
+	leftmost = rb_erase_cached(&p->pushable_dl_tasks, root);
+	if (leftmost)
+		dl_rq->earliest_dl.next = __node_2_pdl(leftmost)->dl.deadline;
 
 	RB_CLEAR_NODE(&p->pushable_dl_tasks);
 }
author maintainer
#9 lore raw

RFC PATCH 2/7 rbtree, sched/fair: Use rb_add_cached()

In reply to Peter Zijlstra
---
 kernel/sched/fair.c |   46 ++++++++++++++--------------------------------
 1 file changed, 14 insertions(+), 32 deletions(-)
kernel/sched/fair.c +14 -32
@@ -533,12 +533,15 @@ static inline u64 min_vruntime(u64 min_v
 	return min_vruntime;
 }
 
-static inline int entity_before(struct sched_entity *a,
+static inline bool entity_before(struct sched_entity *a,
 				struct sched_entity *b)
 {
 	return (s64)(a->vruntime - b->vruntime) < 0;
 }
 
+#define __node_2_se(node) \
+	rb_entry((node), struct sched_entity, run_node)
+
 static void update_min_vruntime(struct cfs_rq *cfs_rq)
 {
 	struct sched_entity *curr = cfs_rq->curr;
@@ -554,8 +557,7 @@ static void update_min_vruntime(struct c
 	}
 
 	if (leftmost) { /* non-empty tree */
-		struct sched_entity *se;
-		se = rb_entry(leftmost, struct sched_entity, run_node);
+		struct sched_entity *se = __node_2_se(leftmost);
 
 		if (!curr)
 			vruntime = se->vruntime;
@@ -571,37 +573,17 @@ static void update_min_vruntime(struct c
 #endif
 }
 
+static inline bool __entity_less(struct rb_node *a, const struct rb_node *b)
+{
+	return entity_before(__node_2_se(a), __node_2_se(b));
+}
+
 /*
  * Enqueue an entity into the rb-tree:
  */
 static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
-	struct rb_node **link = &cfs_rq->tasks_timeline.rb_root.rb_node;
-	struct rb_node *parent = NULL;
-	struct sched_entity *entry;
-	bool leftmost = true;
-
-	/*
-	 * Find the right place in the rbtree:
-	 */
-	while (*link) {
-		parent = *link;
-		entry = rb_entry(parent, struct sched_entity, run_node);
-		/*
-		 * We dont care about collisions. Nodes with
-		 * the same key stay together.
-		 */
-		if (entity_before(se, entry)) {
-			link = &parent->rb_left;
-		} else {
-			link = &parent->rb_right;
-			leftmost = false;
-		}
-	}
-
-	rb_link_node(&se->run_node, parent, link);
-	rb_insert_color_cached(&se->run_node,
-			       &cfs_rq->tasks_timeline, leftmost);
+	rb_add_cached(&cfs_rq->tasks_timeline, &se->run_node, __entity_less);
 }
 
 static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
@@ -616,7 +598,7 @@ struct sched_entity *__pick_first_entity
 	if (!left)
 		return NULL;
 
-	return rb_entry(left, struct sched_entity, run_node);
+	return __node_2_se(left);
 }
 
 static struct sched_entity *__pick_next_entity(struct sched_entity *se)
@@ -626,7 +608,7 @@ static struct sched_entity *__pick_next_
 	if (!next)
 		return NULL;
 
-	return rb_entry(next, struct sched_entity, run_node);
+	return __node_2_se(next);
 }
 
 #ifdef CONFIG_SCHED_DEBUG
@@ -637,7 +619,7 @@ struct sched_entity *__pick_last_entity(
 	if (!last)
 		return NULL;
 
-	return rb_entry(last, struct sched_entity, run_node);
+	return __node_2_se(last);
 }
 
 /**************************************************************
author maintainer
#10 lore raw

RFC PATCH 3/7 rbtree, sched/deadline: Use rb_add_cached()

In reply to Peter Zijlstra
---
 kernel/sched/deadline.c |   75 +++++++++++++++---------------------------------
 1 file changed, 24 insertions(+), 51 deletions(-)
kernel/sched/deadline.c +24 -51
@@ -440,58 +440,38 @@ static void dec_dl_migration(struct sche
 	update_dl_migration(dl_rq);
 }
 
+#define __node_2_pdl(node) \
+	rb_entry((node), struct task_struct, pushable_dl_tasks)
+
+static inline bool __pushable_less(struct rb_node *a, const struct rb_node *b)
+{
+	return dl_entity_preempt(&__node_2_pdl(a)->dl, &__node_2_pdl(b)->dl);
+}
+
 /*
  * The list of pushable -deadline task is not a plist, like in
  * sched_rt.c, it is an rb-tree with tasks ordered by deadline.
  */
 static void enqueue_pushable_dl_task(struct rq *rq, struct task_struct *p)
 {
-	struct dl_rq *dl_rq = &rq->dl;
-	struct rb_node **link = &dl_rq->pushable_dl_tasks_root.rb_root.rb_node;
-	struct rb_node *parent = NULL;
-	struct task_struct *entry;
-	bool leftmost = true;
-
 	BUG_ON(!RB_EMPTY_NODE(&p->pushable_dl_tasks));
 
-	while (*link) {
-		parent = *link;
-		entry = rb_entry(parent, struct task_struct,
-				 pushable_dl_tasks);
-		if (dl_entity_preempt(&p->dl, &entry->dl))
-			link = &parent->rb_left;
-		else {
-			link = &parent->rb_right;
-			leftmost = false;
-		}
-	}
-
-	if (leftmost)
-		dl_rq->earliest_dl.next = p->dl.deadline;
-
-	rb_link_node(&p->pushable_dl_tasks, parent, link);
-	rb_insert_color_cached(&p->pushable_dl_tasks,
-			       &dl_rq->pushable_dl_tasks_root, leftmost);
+	if (rb_add_cached(&rq->dl.pushable_dl_tasks_root, &p->pushable_dl_tasks,
+			  __pushable_less))
+		rq->dl.earliest_dl.next = p->dl.deadline;
 }
 
 static void dequeue_pushable_dl_task(struct rq *rq, struct task_struct *p)
 {
 	struct dl_rq *dl_rq = &rq->dl;
+	struct rb_root_cached *root = &dl_rq->pushable_dl_tasks_root;
 
 	if (RB_EMPTY_NODE(&p->pushable_dl_tasks))
 		return;
 
-	if (dl_rq->pushable_dl_tasks_root.rb_leftmost == &p->pushable_dl_tasks) {
-		struct rb_node *next_node;
+	if (rb_erase_cached(&p->pushable_dl_tasks, root))
+		dl_rq->earliest_dl.next = __node_2_pdl(rb_first_cached(root))->dl.deadline;
 
-		next_node = rb_next(&p->pushable_dl_tasks);
-		if (next_node) {
-			dl_rq->earliest_dl.next = rb_entry(next_node,
-				struct task_struct, pushable_dl_tasks)->dl.deadline;
-		}
-	}
-
-	rb_erase_cached(&p->pushable_dl_tasks, &dl_rq->pushable_dl_tasks_root);
 	RB_CLEAR_NODE(&p->pushable_dl_tasks);
 }
 
@@ -1401,29 +1381,21 @@ void dec_dl_tasks(struct sched_dl_entity
 	dec_dl_migration(dl_se, dl_rq);
 }
 
+#define __node_2_dle(node) \
+	rb_entry((node), struct sched_dl_entity, rb_node)
+
+static inline bool __dl_less(struct rb_node *a, const struct rb_node *b)
+{
+	return dl_time_before(__node_2_dle(a)->deadline, __node_2_dle(b)->deadline);
+}
+
 static void __enqueue_dl_entity(struct sched_dl_entity *dl_se)
 {
 	struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
-	struct rb_node **link = &dl_rq->root.rb_root.rb_node;
-	struct rb_node *parent = NULL;
-	struct sched_dl_entity *entry;
-	int leftmost = 1;
 
 	BUG_ON(!RB_EMPTY_NODE(&dl_se->rb_node));
 
-	while (*link) {
-		parent = *link;
-		entry = rb_entry(parent, struct sched_dl_entity, rb_node);
-		if (dl_time_before(dl_se->deadline, entry->deadline))
-			link = &parent->rb_left;
-		else {
-			link = &parent->rb_right;
-			leftmost = 0;
-		}
-	}
-
-	rb_link_node(&dl_se->rb_node, parent, link);
-	rb_insert_color_cached(&dl_se->rb_node, &dl_rq->root, leftmost);
+	rb_add_cached(&dl_rq->root, &dl_se->rb_node, __dl_less);
 
 	inc_dl_tasks(dl_se, dl_rq);
 }
@@ -1436,6 +1408,7 @@ static void __dequeue_dl_entity(struct s
 		return;
 
 	rb_erase_cached(&dl_se->rb_node, &dl_rq->root);
+
 	RB_CLEAR_NODE(&dl_se->rb_node);
 
 	dec_dl_tasks(dl_se, dl_rq);
author maintainer
#11 lore raw

RFC PATCH 4/7 rbtree, perf: Use new rbtree helpers

In reply to Peter Zijlstra
---
 kernel/events/core.c |  178 +++++++++++++++++++++++----------------------------
 1 file changed, 81 insertions(+), 97 deletions(-)
kernel/events/core.c +81 -97
@@ -1581,44 +1581,84 @@ static void perf_event_groups_init(struc
  * Implements complex key that first sorts by CPU and then by virtual index
  * which provides ordering when rotating groups for the same CPU.
  */
-static bool
-perf_event_groups_less(struct perf_event *left, struct perf_event *right)
-{
-	if (left->cpu < right->cpu)
-		return true;
-	if (left->cpu > right->cpu)
-		return false;
+static __always_inline int
+perf_event_groups_cmp(const int left_cpu, const struct cgroup *left_cgroup,
+		      const u64 left_group_index, const struct perf_event *right)
+{
+	if (left_cpu < right->cpu)
+		return -1;
+	if (left_cpu > right->cpu)
+		return 1;
 
 #ifdef CONFIG_CGROUP_PERF
-	if (left->cgrp != right->cgrp) {
-		if (!left->cgrp || !left->cgrp->css.cgroup) {
+	{
+	struct cgroup *right_cgroup = right->cgrp ? right->cgrp->css.cgroup : NULL;
+
+	if (left_cgroup != right_cgroup) {
+		if (!left_cgroup) {
 			/*
 			 * Left has no cgroup but right does, no cgroups come
 			 * first.
 			 */
-			return true;
+			return -1;
 		}
-		if (!right->cgrp || !right->cgrp->css.cgroup) {
+		if (!right->cgroup) {
 			/*
 			 * Right has no cgroup but left does, no cgroups come
 			 * first.
 			 */
-			return false;
+			return 1;
 		}
 		/* Two dissimilar cgroups, order by id. */
-		if (left->cgrp->css.cgroup->kn->id < right->cgrp->css.cgroup->kn->id)
-			return true;
+		if (cgroup_id(left_cgroup) < cgroup_id(right_cgroup))
+			return -1;
 
-		return false;
+		return 1;
+	}
 	}
 #endif
 
-	if (left->group_index < right->group_index)
-		return true;
-	if (left->group_index > right->group_index)
-		return false;
+	if (left_group_index < right->group_index)
+		return -1;
+	if (left_group_index > right->group_index)
+		return 1;
 
-	return false;
+	return 0;
+}
+
+static inline struct cgroup *event_cgroup(struct perf_event *event)
+{
+	struct cgroup *cgroup = NULL;
+
+#ifdef CONFIG_CGROUP_PERF
+	if (event->cgrp)
+		cgroup = event->cgrp->css.cgroup;
+#endif
+
+	return cgroup;
+}
+
+#define __node_2_pe(node) \
+	rb_entry((node), struct perf_event, group_node)
+
+static inline bool __group_less(struct rb_node *a, const struct rb_node *b)
+{
+	struct perf_event *e = __node_2_pe(a);
+	return perf_event_groups_cmp(e->cpu, event_cgroup(e), e->group_index,
+				     __node_2_pe(b)) < 0;
+}
+
+struct __group_key {
+	int cpu;
+	struct cgroup *cgroup;
+};
+
+static inline int __group_cmp(const void *key, const struct rb_node *node)
+{
+	const struct __group_key *a = key;
+	const struct perf_event *b = __node_2_pe(node);
+
+	return perf_event_groups_cmp(a->cpu, a->cgroup, b->group_index, b);
 }
 
 /*
@@ -1630,27 +1670,9 @@ static void
 perf_event_groups_insert(struct perf_event_groups *groups,
 			 struct perf_event *event)
 {
-	struct perf_event *node_event;
-	struct rb_node *parent;
-	struct rb_node **node;
-
 	event->group_index = ++groups->index;
 
-	node = &groups->tree.rb_node;
-	parent = *node;
-
-	while (*node) {
-		parent = *node;
-		node_event = container_of(*node, struct perf_event, group_node);
-
-		if (perf_event_groups_less(event, node_event))
-			node = &parent->rb_left;
-		else
-			node = &parent->rb_right;
-	}
-
-	rb_link_node(&event->group_node, parent, node);
-	rb_insert_color(&event->group_node, &groups->tree);
+	rb_add(&groups->tree, &event->group_node, __group_less);
 }
 
 /*
@@ -1698,45 +1720,17 @@ static struct perf_event *
 perf_event_groups_first(struct perf_event_groups *groups, int cpu,
 			struct cgroup *cgrp)
 {
-	struct perf_event *node_event = NULL, *match = NULL;
-	struct rb_node *node = groups->tree.rb_node;
-#ifdef CONFIG_CGROUP_PERF
-	u64 node_cgrp_id, cgrp_id = 0;
-
-	if (cgrp)
-		cgrp_id = cgrp->kn->id;
-#endif
-
-	while (node) {
-		node_event = container_of(node, struct perf_event, group_node);
+	struct __group_key key = {
+		.cpu = cpu,
+		.cgroup = cgrp,
+	};
+	struct rb_node *node;
+
+	node = rb_find_first(&groups->tree, &key, __group_cmp);
+	if (node)
+		return __node_2_pe(node);
 
-		if (cpu < node_event->cpu) {
-			node = node->rb_left;
-			continue;
-		}
-		if (cpu > node_event->cpu) {
-			node = node->rb_right;
-			continue;
-		}
-#ifdef CONFIG_CGROUP_PERF
-		node_cgrp_id = 0;
-		if (node_event->cgrp && node_event->cgrp->css.cgroup)
-			node_cgrp_id = node_event->cgrp->css.cgroup->kn->id;
-
-		if (cgrp_id < node_cgrp_id) {
-			node = node->rb_left;
-			continue;
-		}
-		if (cgrp_id > node_cgrp_id) {
-			node = node->rb_right;
-			continue;
-		}
-#endif
-		match = node_event;
-		node = node->rb_left;
-	}
-
-	return match;
+	return NULL;
 }
 
 /*
@@ -1745,27 +1739,17 @@ perf_event_groups_first(struct perf_even
 static struct perf_event *
 perf_event_groups_next(struct perf_event *event)
 {
-	struct perf_event *next;
-#ifdef CONFIG_CGROUP_PERF
-	u64 curr_cgrp_id = 0;
-	u64 next_cgrp_id = 0;
-#endif
+	struct __group_key key = {
+		.cpu = event->cpu,
+		.cgroup = event_cgroup(event),
+	};
+	struct rb_node *next;
+
+	next = rb_next_match(&event->group_node, &key, __group_cmp);
+	if (next)
+		return __node_2_pe(next);
 
-	next = rb_entry_safe(rb_next(&event->group_node), typeof(*event), group_node);
-	if (next == NULL || next->cpu != event->cpu)
-		return NULL;
-
-#ifdef CONFIG_CGROUP_PERF
-	if (event->cgrp && event->cgrp->css.cgroup)
-		curr_cgrp_id = event->cgrp->css.cgroup->kn->id;
-
-	if (next->cgrp && next->cgrp->css.cgroup)
-		next_cgrp_id = next->cgrp->css.cgroup->kn->id;
-
-	if (curr_cgrp_id != next_cgrp_id)
-		return NULL;
-#endif
-	return next;
+	return NULL;
 }
 
 /*
#12 lore raw

Re: [RFC][PATCH 4/7] rbtree, perf: Use new rbtree helpers

[if your patch is applied to the wrong git tree, please drop us a note to help improve the system. BTW, we also suggest to use '--base' option to specify the base tree in git format-patch, please…

Hi Peter,

[FYI, it's a private test report for your RFC patch.]
[auto build test ERROR on next-20200429]
[cannot apply to tip/sched/core tip/perf/core linus/master linux/master v5.7-rc3 v5.7-rc2 v5.7-rc1 v5.7-rc3] [if your patch is applied to the wrong git tree, please drop us a note to help
improve the system. BTW, we also suggest to use '--base' option to specify the
base tree in git format-patch, please see https://stackoverflow.com/a/37406982]

url:    https://github.com/0day-ci/linux/commits/Peter-Zijlstra/Generic-RB-tree-helpers/20200430-042905
base:    861978d1331b7e988e0295a2275c669c767fa3f1
config: arm64-randconfig-a001-20200429 (attached as .config)
compiler: clang version 11.0.0 (https://github.com/llvm/llvm-project f30416fdde922eaa655934e050026930fefbd260)

reproduce:
wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross chmod +x ~/bin/make.cross
# install arm64 cross compiling tool for clang build
# apt-get install binutils-aarch64-linux-gnu
# save the attached .config to linux build tree
COMPILER_INSTALL_PATH=$HOME/0day COMPILER=clang make.cross ARCH=arm64

If you fix the issue, kindly add following tag as appropriate

All errors (new ones prefixed by >>):

>> kernel/events/core.c:1603:15: error: no member named 'cgroup' in 'struct perf_event'; did you mean 'cgrp'?
                   if (!right->cgroup) {
                               ^~~~~~
                               cgrp
   include/linux/perf_event.h:758:23: note: 'cgrp' declared here
           struct perf_cgroup              *cgrp; /* cgroup event is attach to */
                                            ^
>> kernel/events/core.c:1611:17: error: passing 'const struct cgroup *' to parameter of type 'struct cgroup *' discards qualifiers [-Werror,-Wincompatible-pointer-types-discards-qualifiers]
                   if (cgroup_id(left_cgroup) < cgroup_id(right_cgroup))
                                 ^~~~~~~~~~~
   include/linux/cgroup.h:310:44: note: passing argument to parameter 'cgrp' here
   static inline u64 cgroup_id(struct cgroup *cgrp)
                                              ^

2 errors generated.

vim +1603 kernel/events/core.c

1575
1576 /*
1577 * Compare function for event groups;
1578 *
1579 * Implements complex key that first sorts by CPU and then by virtual index
1580 * which provides ordering when rotating groups for the same CPU.
1581 */
1582 static __always_inline int
1583 perf_event_groups_cmp(const int left_cpu, const struct cgroup *left_cgroup,
1584 const u64 left_group_index, const struct perf_event *right)
1585 {
1586 if (left_cpu < right->cpu)
1587 return -1;
1588 if (left_cpu > right->cpu)
1589 return 1;
1590
1591 #ifdef CONFIG_CGROUP_PERF
1592 {
1593 struct cgroup *right_cgroup = right->cgrp ? right->cgrp->css.cgroup : NULL;
1594
1595 if (left_cgroup != right_cgroup) {
1596 if (!left_cgroup) {
1597 /*
1598 * Left has no cgroup but right does, no cgroups come
1599 * first.
1600 */
1601 return -1;
1602 }

> 1603			if (!right->cgroup) {
  1604				/*
  1605				 * Right has no cgroup but left does, no cgroups come
  1606				 * first.
  1607				 */
  1608				return 1;
  1609			}
  1610			/* Two dissimilar cgroups, order by id. */
> 1611			if (cgroup_id(left_cgroup) < cgroup_id(right_cgroup))

1612 return -1;
1613
1614 return 1;
1615 }
1616 }
1617 #endif
1618
1619 if (left_group_index < right->group_index)
1620 return -1;
1621 if (left_group_index > right->group_index)
1622 return 1;
1623
1624 return 0;
1625 }
1626

---
0-DAY CI Kernel Test Service, Intel Corporation
https://lists.01.org/hyperkitty/list/kbuild-all(a)lists.01.org

author maintainer
#13 lore raw

RFC PATCH 5/7 rbtree, uprobes: Use rbtree helpers

In reply to Peter Zijlstra
---
 kernel/events/uprobes.c  |   82 ++++++++++++++++++++++-------------------------
 kernel/locking/rtmutex.c |   54 ++++++++++--------------------
 2 files changed, 58 insertions(+), 78 deletions(-)
kernel/events/uprobes.c +40 -42
@@ -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(&uprobes_tree, &key, __uprobe_cmp_key);
+
+	if (node)
+		return __node_2_uprobe(node);
 
-	while (n) {
-		uprobe = rb_entry(n, struct uprobe, rb_node);
-		match = match_uprobe(&u, 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 = &uprobes_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 = &parent->rb_left;
-		else
-			p = &parent->rb_right;
+	struct rb_node *node;
 
-	}
+	node = rb_find_add(&uprobes_tree, &uprobe->rb_node, __uprobe_cmp);
+	if (node)
+		return get_uprobe(__node_2_uprobe(node));
 
-	u = NULL;
-	rb_link_node(&uprobe->rb_node, parent, p);
-	rb_insert_color(&uprobe->rb_node, &uprobes_tree);
 	/* get access + creation ref */
 	refcount_set(&uprobe->ref, 2);
-
-	return u;
+	return NULL;
 }
 
 /*
author maintainer
#14 lore raw

RFC PATCH 6/7 rbtree, rtmutex: Use rb_add_cached()

In reply to Peter Zijlstra
---
 kernel/locking/rtmutex.c |   54 +++++++++++++++--------------------------------
 1 file changed, 18 insertions(+), 36 deletions(-)
kernel/locking/rtmutex.c +18 -36
@@ -267,27 +267,18 @@ rt_mutex_waiter_equal(struct rt_mutex_wa
 	return 1;
 }
 
+#define __node_2_waiter(node) \
+	rb_entry((node), struct rt_mutex_waiter, tree_entry)
+
+static inline bool __waiter_less(struct rb_node *a, const struct rb_node *b)
+{
+	return rt_mutex_waiter_less(__node_2_waiter(a), __node_2_waiter(b));
+}
+
 static void
 rt_mutex_enqueue(struct rt_mutex *lock, struct rt_mutex_waiter *waiter)
 {
-	struct rb_node **link = &lock->waiters.rb_root.rb_node;
-	struct rb_node *parent = NULL;
-	struct rt_mutex_waiter *entry;
-	bool leftmost = true;
-
-	while (*link) {
-		parent = *link;
-		entry = rb_entry(parent, struct rt_mutex_waiter, tree_entry);
-		if (rt_mutex_waiter_less(waiter, entry)) {
-			link = &parent->rb_left;
-		} else {
-			link = &parent->rb_right;
-			leftmost = false;
-		}
-	}
-
-	rb_link_node(&waiter->tree_entry, parent, link);
-	rb_insert_color_cached(&waiter->tree_entry, &lock->waiters, leftmost);
+	rb_add_cached(&lock->waiters, &waiter->tree_entry, __waiter_less);
 }
 
 static void
@@ -300,27 +291,18 @@ rt_mutex_dequeue(struct rt_mutex *lock,
 	RB_CLEAR_NODE(&waiter->tree_entry);
 }
 
+#define __node_2_pi_waiter(node) \
+	rb_entry((node), struct rt_mutex_waiter, pi_tree_entry)
+
+static inline bool __pi_waiter_less(struct rb_node *a, const struct rb_node *b)
+{
+	return rt_mutex_waiter_less(__node_2_pi_waiter(a), __node_2_pi_waiter(b));
+}
+
 static void
 rt_mutex_enqueue_pi(struct task_struct *task, struct rt_mutex_waiter *waiter)
 {
-	struct rb_node **link = &task->pi_waiters.rb_root.rb_node;
-	struct rb_node *parent = NULL;
-	struct rt_mutex_waiter *entry;
-	bool leftmost = true;
-
-	while (*link) {
-		parent = *link;
-		entry = rb_entry(parent, struct rt_mutex_waiter, pi_tree_entry);
-		if (rt_mutex_waiter_less(waiter, entry)) {
-			link = &parent->rb_left;
-		} else {
-			link = &parent->rb_right;
-			leftmost = false;
-		}
-	}
-
-	rb_link_node(&waiter->pi_tree_entry, parent, link);
-	rb_insert_color_cached(&waiter->pi_tree_entry, &task->pi_waiters, leftmost);
+	rb_add_cached(&task->pi_waiters, &waiter->pi_tree_entry, __pi_waiter_less);
 }
 
 static void
author maintainer
#15 lore raw

RFC PATCH 7/7 rbtree, timerqueue: Use rb_add_cached()

In reply to Peter Zijlstra
---
 lib/timerqueue.c |   28 +++++++++-------------------
 1 file changed, 9 insertions(+), 19 deletions(-)
lib/timerqueue.c +9 -19
@@ -14,6 +14,14 @@
 #include <linux/rbtree.h>
 #include <linux/export.h>
 
+#define __node_2_tq(_n) \
+	rb_entry((_n), struct timerqueue_node, node)
+
+static inline bool __timerqueue_less(struct rb_node *a, const struct rb_node *b)
+{
+	return __node_2_tq(a)->expires < __node_2_tq(b)->expires;
+}
+
 /**
  * timerqueue_add - Adds timer to timerqueue.
  *
@@ -26,28 +34,10 @@
  */
 bool timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node)
 {
-	struct rb_node **p = &head->rb_root.rb_root.rb_node;
-	struct rb_node *parent = NULL;
-	struct timerqueue_node *ptr;
-	bool leftmost = true;
-
 	/* Make sure we don't add nodes that are already added */
 	WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node));
 
-	while (*p) {
-		parent = *p;
-		ptr = rb_entry(parent, struct timerqueue_node, node);
-		if (node->expires < ptr->expires) {
-			p = &(*p)->rb_left;
-		} else {
-			p = &(*p)->rb_right;
-			leftmost = false;
-		}
-	}
-	rb_link_node(&node->node, parent, p);
-	rb_insert_color_cached(&node->node, &head->rb_root, leftmost);
-
-	return leftmost;
+	return rb_add_cached(&head->rb_root, &node->node, __timerqueue_less);
 }
 EXPORT_SYMBOL_GPL(timerqueue_add);