Re: [PATCH] sched/deadline: Fix priority inheritance with multiple scheduling classes

From: Valentin Schneider
Date: Thu Nov 05 2020 - 10:49:30 EST



Hi Juri,

On 05/11/20 07:50, Juri Lelli wrote:
> He also provided a simple reproducer creating the situation below:
>
> So the execution order of locking steps are the following
> (N1 and N2 are non-deadline tasks. D1 is a deadline task. M1 and M2
> are mutexes that are enabled * with priority inheritance.)
>
> Time moves forward as this timeline goes down:
>
> N1 N2 D1
> | | |
> | | |
> Lock(M1) | |
> | | |
> | Lock(M2) |
> | | |
> | | Lock(M2)
> | | |
> | Lock(M1) |
> | (!!bug triggered!) |
>
> Daniel reported a similar situation as well, by just letting ksoftirqd
> run with DEADLINE (and eventually block on a mutex).
>
> Problem is that boosted entities (Priority Inheritance) use static
> DEADLINE parameters of the top priority waiter. However, there might be
> cases where top waiter could be a non-DEADLINE entity that is currently
> boosted by a DEADLINE entity from a different lock chain (i.e., nested
> priority chains involving entities of non-DEADLINE classes). In this
> case, top waiter static DEADLINE parameters could be null (initialized
> to 0 at fork()) and replenish_dl_entity() would hit a BUG().
>

IIUC, rt_mutex_get_top_task(N1) == N2, and N2->dl->deadline = 0, which
makes enqueue_task_dl() unhappy. And that happens because, unlike p->prio,
DL parameters aren't properly propagated through the chain(s).

> Fix this by keeping track of the original donor and using its parameters
> when a task is boosted.
>
> Reported-by: Glenn Elliott <glenn@xxxxxxxxxxx>
> Reported-by: Daniel Bristot de Oliveira <bristot@xxxxxxxxxx>
> Signed-off-by: Juri Lelli <juri.lelli@xxxxxxxxxx>
>
> ---
>
> This is actually a v2 attempt (didn't keep $SUBJECT since it's quite
> different than v1 [1]) to fix this problem.
>
> v1 was admittedly pretty ugly. Hope this looks slightly better (even
> though there is of course overhead associated to the additional
> pointer).
>
> Again, the proper way to fix this is by proxy execution. But, I don't
> think we are yet there and this problem needs a quick band-aid.
>
> One could probably also think to complicate the present approach and
> actually perform accounting using donor's dynamic parameters, but I fear
> it would be of little benefit since it would still bring all the
> problems associated to affinities. So, I'd propose let's try to fix all
> this properly with proxy and just avoid crashes in the meantime.
>

For my own sake, what affinity problems are you thinking of?

With proxy exec we have this "funny" dance of shoving the entire blocked-on
chain on a single runqueue to get the right selection out of
pick_next_task(), and that needs to deal with affinity (i.e. move the task
back to a sensible rq once it becomes runnable).

With the current PI, the waiting tasks are blocked and enqueued in the
pi_waiters tree, so as I see it affinity shouldn't matter; what am I
missing / not seeing? Is that related to bandwidth handling?

> 1 - 20191112075056.19971-1-juri.lelli@xxxxxxxxxx
> ---
> include/linux/sched.h | 9 +++++
> kernel/sched/core.c | 13 ++++++--
> kernel/sched/deadline.c | 74 ++++++++++++++++++++---------------------
> 3 files changed, 56 insertions(+), 40 deletions(-)
>
> diff --git a/include/linux/sched.h b/include/linux/sched.h
> index 063cd120b459..db29ab492181 100644
> --- a/include/linux/sched.h
> +++ b/include/linux/sched.h
> @@ -571,6 +571,15 @@ struct sched_dl_entity {
> * time.
> */
> struct hrtimer inactive_timer;
> +
> +#ifdef CONFIG_RT_MUTEXES
> + /*
> + * Priority Inheritance. When a DEADLINE scheduling entity is boosted
> + * pi_se points to the donor, otherwise points to the dl_se it belongs
> + * to (the original one/itself).
> + */
> + struct sched_dl_entity *pi_se;
> +#endif
> };
>
> #ifdef CONFIG_UCLAMP_TASK
> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> index 6f533bb7d3b9..e10aba6c363d 100644
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -4908,19 +4908,26 @@ void rt_mutex_setprio(struct task_struct *p, struct task_struct *pi_task)
> (pi_task && dl_prio(pi_task->prio) &&
> dl_entity_preempt(&pi_task->dl, &p->dl))) {
> p->dl.dl_boosted = 1;
> + p->dl.pi_se = pi_task->dl.pi_se;
> queue_flag |= ENQUEUE_REPLENISH;
> - } else
> + } else {
> p->dl.dl_boosted = 0;
> + p->dl.pi_se = &p->dl;
> + }
> p->sched_class = &dl_sched_class;
> } else if (rt_prio(prio)) {
> - if (dl_prio(oldprio))
> + if (dl_prio(oldprio)) {
> p->dl.dl_boosted = 0;
> + p->dl.pi_se = &p->dl;
> + }
> if (oldprio < prio)
> queue_flag |= ENQUEUE_HEAD;
> p->sched_class = &rt_sched_class;
> } else {
> - if (dl_prio(oldprio))
> + if (dl_prio(oldprio)) {
> p->dl.dl_boosted = 0;
> + p->dl.pi_se = &p->dl;
> + }

With this change, do we still need sched_dl_entity.dl_boosted? AIUI this
could become

bool is_dl_boosted(struct sched_dl_entity *dl_se)
{
return pi_of(dl_se) != dl_se;
}

> if (rt_prio(oldprio))
> p->rt.timeout = 0;
> p->sched_class = &fair_sched_class;