[RFC][PATCH 0/7] Generic RB-tree helpers

[RFC][PATCH 0/7] Generic RB-tree helpers

[Peter Zijlstra]

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

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

[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.

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 include/linux/rbtree.h       |  127 +++++++++++++++++++++++++++++++++++++++++-
 tools/include/linux/rbtree.h |  129 ++++++++++++++++++++++++++++++++++++++++++-
 tools/objtool/elf.c          |   63 ++-------------------
 3 files changed, 257 insertions(+), 62 deletions(-)

--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -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 */
--- a/tools/include/linux/rbtree.h
+++ b/tools/include/linux/rbtree.h
@@ -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 */
--- a/tools/objtool/elf.c
+++ b/tools/objtool/elf.c
@@ -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)

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

[Peter Zijlstra]

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 kernel/sched/fair.c |   46 ++++++++++++++--------------------------------
 1 file changed, 14 insertions(+), 32 deletions(-)

--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -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);
 }
 
 /**************************************************************

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

[Peter Zijlstra]

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 kernel/sched/deadline.c |   75 +++++++++++++++---------------------------------
 1 file changed, 24 insertions(+), 51 deletions(-)

--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -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);

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

[Peter Zijlstra]

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 kernel/events/core.c |  178 +++++++++++++++++++++++----------------------------
 1 file changed, 81 insertions(+), 97 deletions(-)

--- a/kernel/events/core.c
+++ b/kernel/events/core.c
@@ -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;
 }
 
 /*

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

[Peter Zijlstra]

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 kernel/events/uprobes.c  |   82 ++++++++++++++++++++++-------------------------
 kernel/locking/rtmutex.c |   54 ++++++++++--------------------
 2 files changed, 58 insertions(+), 78 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(&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;
 }
 
 /*

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

[Peter Zijlstra]

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 kernel/locking/rtmutex.c |   54 +++++++++++++++--------------------------------
 1 file changed, 18 insertions(+), 36 deletions(-)

--- a/kernel/locking/rtmutex.c
+++ b/kernel/locking/rtmutex.c
@@ -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

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

[Peter Zijlstra]

Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
---
 lib/timerqueue.c |   28 +++++++++-------------------
 1 file changed, 9 insertions(+), 19 deletions(-)

--- a/lib/timerqueue.c
+++ b/lib/timerqueue.c
@@ -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);
 

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

[Michel Lespinasse]

Hi Peter,

On Wed, Apr 29, 2020 at 05:32:59PM +0200, Peter Zijlstra wrote:
> 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.

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).

Reviewed-by: Michel Lespinasse <walken@google.com>

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.

> 
> Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
> ---
>  include/linux/rbtree.h       |  127 +++++++++++++++++++++++++++++++++++++++++-
>  tools/include/linux/rbtree.h |  129 ++++++++++++++++++++++++++++++++++++++++++-
>  tools/objtool/elf.c          |   63 ++-------------------
>  3 files changed, 257 insertions(+), 62 deletions(-)
> 
> --- a/include/linux/rbtree.h
> +++ b/include/linux/rbtree.h
> @@ -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 */
> --- a/tools/include/linux/rbtree.h
> +++ b/tools/include/linux/rbtree.h
> @@ -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 */
> --- a/tools/objtool/elf.c
> +++ b/tools/objtool/elf.c
> @@ -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)
> 
> 

-- 
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.

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

[Juri Lelli]

Hi,

On 29/04/20 17:32, Peter Zijlstra wrote:
> 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.
> 
> Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
> ---
>  include/linux/rbtree.h       |  127 +++++++++++++++++++++++++++++++++++++++++-
>  tools/include/linux/rbtree.h |  129 ++++++++++++++++++++++++++++++++++++++++++-
>  tools/objtool/elf.c          |   63 ++-------------------
>  3 files changed, 257 insertions(+), 62 deletions(-)
> 
> --- a/include/linux/rbtree.h
> +++ b/include/linux/rbtree.h
> @@ -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);

Think we need

 if (root->rb_leftmost)

> +		leftmost = true;

DEADLINE crashes w/o that.

> +	}
>  	rb_erase(node, &root->rb_root);
> +
> +	return leftmost;
>  }

The rest looks good to me.

Thanks,

Juri

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

[Michel Lespinasse]

On Thu, Apr 30, 2020 at 12:28 AM Juri Lelli <juri.lelli@redhat.com> wrote:
> > --- a/include/linux/rbtree.h
> > +++ b/include/linux/rbtree.h
> > @@ -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);
>
> Think we need
>
>  if (root->rb_leftmost)
>
> > +             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).

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

[Juri Lelli]

On 30/04/20 00:51, Michel Lespinasse wrote:
> On Thu, Apr 30, 2020 at 12:28 AM Juri Lelli <juri.lelli@redhat.com> wrote:
> > > --- a/include/linux/rbtree.h
> > > +++ b/include/linux/rbtree.h
> > > @@ -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);
> >
> > Think we need
> >
> >  if (root->rb_leftmost)
> >
> > > +             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.

> 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

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

[Peter Zijlstra]

On Thu, Apr 30, 2020 at 12:51:02AM -0700, Michel Lespinasse wrote:
> On Thu, Apr 30, 2020 at 12:28 AM Juri Lelli <juri.lelli@redhat.com> wrote:
> > > --- a/include/linux/rbtree.h
> > > +++ b/include/linux/rbtree.h
> > > @@ -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);
> >
> > Think we need
> >
> >  if (root->rb_leftmost)
> >
> > > +             leftmost = true;
> >
> > DEADLINE crashes w/o that.

Clearly boot testing doesn't cover 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.

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.


---
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -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,
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -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);
 }

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

[Peter Zijlstra]

On Wed, Apr 29, 2020 at 06:04:05PM -0700, Michel Lespinasse wrote:
> Hi Peter,
> 
> On Wed, Apr 29, 2020 at 05:32:59PM +0200, Peter Zijlstra wrote:
> > 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).

> > 
> > 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).

> 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 ;-)

> - 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.

> Reviewed-by: Michel Lespinasse <walken@google.com>

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

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

[Peter Zijlstra]

On Thu, Apr 30, 2020 at 10:46:17AM +0200, Peter Zijlstra wrote:
> On Wed, Apr 29, 2020 at 06:04:05PM -0700, Michel Lespinasse wrote:

> > - 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.

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.