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@xxxxxxxxxx> 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);
 }