On Thu, Apr 30, 2020 at 12:51:02AM -0700, Michel Lespinasse wrote:
> On Thu, Apr 30, 2020 at 12:28 AM Juri Lelli <[email protected]> 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);
}
