[PATCH 08/13] sched: Drafted deadline inheritance logic

From: Peter Zijlstra
Date: Tue Dec 17 2013 - 07:49:16 EST

From: Dario Faggioli <raistlin@xxxxxxxx>

Some method to deal with rt-mutexes and make sched_dl interact with
the current PI-coded is needed, raising all but trivial issues, that
needs (according to us) to be solved with some restructuring of
the pi-code (i.e., going toward a proxy execution-ish implementation).

This is under development, in the meanwhile, as a temporary solution,
what this commits does is:
- ensure a pi-lock owner with waiters is never throttled down. Instead,
when it runs out of runtime, it immediately gets replenished and it's
deadline is postponed;
- the scheduling parameters (relative deadline and default runtime)
used for that replenishments --during the whole period it holds the
pi-lock-- are the ones of the waiting task with earliest deadline.

Acting this way, we provide some kind of boosting to the lock-owner,
still by using the existing (actually, slightly modified by the previous
commit) pi-architecture.

We would stress the fact that this is only a surely needed, all but
clean solution to the problem. In the end it's only a way to re-start
discussion within the community. So, as always, comments, ideas, rants,
etc.. are welcome! :-)

Cc: liming.wang@xxxxxxxxxxxxx
Cc: oleg@xxxxxxxxxx
Cc: tommaso.cucinotta@xxxxxxxx
Cc: dhaval.giani@xxxxxxxxx
Cc: luca.abeni@xxxxxxxx
Cc: paulmck@xxxxxxxxxxxxxxxxxx
Cc: fchecconi@xxxxxxxxx
Cc: fweisbec@xxxxxxxxx
Cc: harald.gustafsson@xxxxxxxxxxxx
Cc: hgu1972@xxxxxxxxx
Cc: vincent.guittot@xxxxxxxxxx
Cc: insop.song@xxxxxxxxx
Cc: michael@xxxxxxxxxxxxxxxxxxxx
Cc: p.faure@xxxxxxxxxx
Cc: bruce.ashfield@xxxxxxxxxxxxx
Cc: jkacur@xxxxxxxxxx
Cc: mingo@xxxxxxxxxx
Cc: rostedt@xxxxxxxxxxx
Cc: claudio@xxxxxxxxxxxxxxx
Cc: johan.eker@xxxxxxxxxxxx
Cc: nicola.manica@xxxxxxxxxxxxx
Cc: tglx@xxxxxxxxxxxxx
Cc: darren@xxxxxxxxxx
Signed-off-by: Dario Faggioli <raistlin@xxxxxxxx>
Signed-off-by: Juri Lelli <juri.lelli@xxxxxxxxx>
Signed-off-by: Peter Zijlstra <peterz@xxxxxxxxxxxxx>
---
include/linux/sched.h | 8 ++-
include/linux/sched/rt.h | 1
kernel/fork.c | 1
kernel/locking/rtmutex.c | 31 +++++++++---
kernel/locking/rtmutex_common.h | 1
kernel/sched/core.c | 36 ++++++++++++---
kernel/sched/deadline.c | 91 ++++++++++++++++++++++----------------
kernel/sched/sched.h | 14 +++++
kernel/trace/trace_sched_wakeup.c | 1
9 files changed, 130 insertions(+), 54 deletions(-)

--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -1116,8 +1116,12 @@ struct sched_dl_entity {
* @dl_new tells if a new instance arrived. If so we must
* start executing it with full runtime and reset its absolute
* deadline;
+ *
+ * @dl_boosted tells if we are boosted due to DI. If so we are
+ * outside bandwidth enforcement mechanism (but only until we
+ * exit the critical section).
*/
- int dl_throttled, dl_new;
+ int dl_throttled, dl_new, dl_boosted;

/*
* Bandwidth enforcement timer. Each -deadline task has its
@@ -1351,6 +1355,8 @@ struct task_struct {
struct rb_node *pi_waiters_leftmost;
/* Deadlock detection and priority inheritance handling */
struct rt_mutex_waiter *pi_blocked_on;
+ /* Top pi_waiters task */
+ struct task_struct *pi_top_task;
#endif

#ifdef CONFIG_DEBUG_MUTEXES
--- a/include/linux/sched/rt.h
+++ b/include/linux/sched/rt.h
@@ -35,6 +35,7 @@ static inline int rt_task(struct task_st
#ifdef CONFIG_RT_MUTEXES
extern int rt_mutex_getprio(struct task_struct *p);
extern void rt_mutex_setprio(struct task_struct *p, int prio);
+extern struct task_struct *rt_mutex_get_top_task(struct task_struct *task);
extern void rt_mutex_adjust_pi(struct task_struct *p);
static inline bool tsk_is_pi_blocked(struct task_struct *tsk)
{
--- a/kernel/fork.c
+++ b/kernel/fork.c
@@ -1089,6 +1089,7 @@ static void rt_mutex_init_task(struct ta
p->pi_waiters = RB_ROOT;
p->pi_waiters_leftmost = NULL;
p->pi_blocked_on = NULL;
+ p->pi_top_task = NULL;
#endif
}

--- a/kernel/locking/rtmutex.c
+++ b/kernel/locking/rtmutex.c
@@ -96,13 +96,16 @@ static inline int
rt_mutex_waiter_less(struct rt_mutex_waiter *left,
struct rt_mutex_waiter *right)
{
- if (left->task->prio < right->task->prio)
+ if (left->prio < right->prio)
return 1;

/*
- * If both tasks are dl_task(), we check their deadlines.
+ * If both waiters have dl_prio(), we check the deadlines of the
+ * associated tasks.
+ * If left waiter has a dl_prio(), and we didn't return 1 above,
+ * then right waiter has a dl_prio() too.
*/
- if (dl_prio(left->task->prio) && dl_prio(right->task->prio))
+ if (dl_prio(left->prio))
return (left->task->dl.deadline < right->task->dl.deadline);

return 0;
@@ -197,10 +200,18 @@ int rt_mutex_getprio(struct task_struct
if (likely(!task_has_pi_waiters(task)))
return task->normal_prio;

- return min(task_top_pi_waiter(task)->task->prio,
+ return min(task_top_pi_waiter(task)->prio,
task->normal_prio);
}

+struct task_struct *rt_mutex_get_top_task(struct task_struct *task)
+{
+ if (likely(!task_has_pi_waiters(task)))
+ return NULL;
+
+ return task_top_pi_waiter(task)->task;
+}
+
/*
* Adjust the priority of a task, after its pi_waiters got modified.
*
@@ -210,7 +221,7 @@ static void __rt_mutex_adjust_prio(struc
{
int prio = rt_mutex_getprio(task);

- if (task->prio != prio)
+ if (task->prio != prio || dl_prio(prio))
rt_mutex_setprio(task, prio);
}

@@ -328,7 +339,7 @@ static int rt_mutex_adjust_prio_chain(st
* When deadlock detection is off then we check, if further
* priority adjustment is necessary.
*/
- if (!detect_deadlock && waiter->task->prio == task->prio)
+ if (!detect_deadlock && waiter->prio == task->prio)
goto out_unlock_pi;

lock = waiter->lock;
@@ -350,7 +361,7 @@ static int rt_mutex_adjust_prio_chain(st

/* Requeue the waiter */
rt_mutex_dequeue(lock, waiter);
- waiter->task->prio = task->prio;
+ waiter->prio = task->prio;
rt_mutex_enqueue(lock, waiter);

/* Release the task */
@@ -448,7 +459,7 @@ static int try_to_take_rt_mutex(struct r
* 3) it is top waiter
*/
if (rt_mutex_has_waiters(lock)) {
- if (task->prio >= rt_mutex_top_waiter(lock)->task->prio) {
+ if (task->prio >= rt_mutex_top_waiter(lock)->prio) {
if (!waiter || waiter != rt_mutex_top_waiter(lock))
return 0;
}
@@ -508,6 +519,7 @@ static int task_blocks_on_rt_mutex(struc
__rt_mutex_adjust_prio(task);
waiter->task = task;
waiter->lock = lock;
+ waiter->prio = task->prio;

/* Get the top priority waiter on the lock */
if (rt_mutex_has_waiters(lock))
@@ -653,7 +665,8 @@ void rt_mutex_adjust_pi(struct task_stru
raw_spin_lock_irqsave(&task->pi_lock, flags);

waiter = task->pi_blocked_on;
- if (!waiter || waiter->task->prio == task->prio) {
+ if (!waiter || (waiter->prio == task->prio &&
+ !dl_prio(task->prio))) {
raw_spin_unlock_irqrestore(&task->pi_lock, flags);
return;
}
--- a/kernel/locking/rtmutex_common.h
+++ b/kernel/locking/rtmutex_common.h
@@ -54,6 +54,7 @@ struct rt_mutex_waiter {
struct pid *deadlock_task_pid;
struct rt_mutex *deadlock_lock;
#endif
+ int prio;
};

/*
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -947,7 +947,7 @@ static inline void check_class_changed(s
if (prev_class->switched_from)
prev_class->switched_from(rq, p);
p->sched_class->switched_to(rq, p);
- } else if (oldprio != p->prio)
+ } else if (oldprio != p->prio || dl_task(p))
p->sched_class->prio_changed(rq, p, oldprio);
}

@@ -2780,7 +2780,7 @@ EXPORT_SYMBOL(sleep_on_timeout);
*/
void rt_mutex_setprio(struct task_struct *p, int prio)
{
- int oldprio, on_rq, running;
+ int oldprio, on_rq, running, enqueue_flag = 0;
struct rq *rq;
const struct sched_class *prev_class;

@@ -2807,6 +2807,7 @@ void rt_mutex_setprio(struct task_struct
}

trace_sched_pi_setprio(p, prio);
+ p->pi_top_task = rt_mutex_get_top_task(p);
oldprio = p->prio;
prev_class = p->sched_class;
on_rq = p->on_rq;
@@ -2816,19 +2817,42 @@ void rt_mutex_setprio(struct task_struct
if (running)
p->sched_class->put_prev_task(rq, p);

- if (dl_prio(prio))
+ /*
+ * Boosting condition are:
+ * 1. -rt task is running and holds mutex A
+ * --> -dl task blocks on mutex A
+ *
+ * 2. -dl task is running and holds mutex A
+ * --> -dl task blocks on mutex A and could preempt the
+ * running task
+ */
+ if (dl_prio(prio)) {
+ if (!dl_prio(p->normal_prio) || (p->pi_top_task &&
+ dl_entity_preempt(&p->pi_top_task->dl, &p->dl))) {
+ p->dl.dl_boosted = 1;
+ p->dl.dl_throttled = 0;
+ enqueue_flag = ENQUEUE_REPLENISH;
+ } else
+ p->dl.dl_boosted = 0;
p->sched_class = &dl_sched_class;
- else if (rt_prio(prio))
+ } else if (rt_prio(prio)) {
+ if (dl_prio(oldprio))
+ p->dl.dl_boosted = 0;
+ if (oldprio < prio)
+ enqueue_flag = ENQUEUE_HEAD;
p->sched_class = &rt_sched_class;
- else
+ } else {
+ if (dl_prio(oldprio))
+ p->dl.dl_boosted = 0;
p->sched_class = &fair_sched_class;
+ }

p->prio = prio;

if (running)
p->sched_class->set_curr_task(rq);
if (on_rq)
- enqueue_task(rq, p, oldprio < prio ? ENQUEUE_HEAD : 0);
+ enqueue_task(rq, p, enqueue_flag);

check_class_changed(rq, p, prev_class, oldprio);
out_unlock:
--- a/kernel/sched/deadline.c
+++ b/kernel/sched/deadline.c
@@ -16,20 +16,6 @@
*/
#include "sched.h"

-static inline int dl_time_before(u64 a, u64 b)
-{
- return (s64)(a - b) < 0;
-}
-
-/*
- * Tells if entity @a should preempt entity @b.
- */
-static inline
-int dl_entity_preempt(struct sched_dl_entity *a, struct sched_dl_entity *b)
-{
- return dl_time_before(a->deadline, b->deadline);
-}
-
static inline struct task_struct *dl_task_of(struct sched_dl_entity *dl_se)
{
return container_of(dl_se, struct task_struct, dl);
@@ -242,7 +228,8 @@ static void check_preempt_curr_dl(struct
* one, and to (try to!) reconcile itself with its own scheduling
* parameters.
*/
-static inline void setup_new_dl_entity(struct sched_dl_entity *dl_se)
+static inline void setup_new_dl_entity(struct sched_dl_entity *dl_se,
+ struct sched_dl_entity *pi_se)
{
struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
struct rq *rq = rq_of_dl_rq(dl_rq);
@@ -254,8 +241,8 @@ static inline void setup_new_dl_entity(s
* future; in fact, we must consider execution overheads (time
* spent on hardirq context, etc.).
*/
- dl_se->deadline = rq_clock(rq) + dl_se->dl_deadline;
- dl_se->runtime = dl_se->dl_runtime;
+ dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
+ dl_se->runtime = pi_se->dl_runtime;
dl_se->dl_new = 0;
}

@@ -277,11 +264,23 @@ static inline void setup_new_dl_entity(s
* could happen are, typically, a entity voluntarily trying to overcome its
* runtime, or it just underestimated it during sched_setscheduler_ex().
*/
-static void replenish_dl_entity(struct sched_dl_entity *dl_se)
+static void replenish_dl_entity(struct sched_dl_entity *dl_se,
+ struct sched_dl_entity *pi_se)
{
struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
struct rq *rq = rq_of_dl_rq(dl_rq);

+ BUG_ON(pi_se->dl_runtime <= 0);
+
+ /*
+ * This could be the case for a !-dl task that is boosted.
+ * Just go with full inherited parameters.
+ */
+ if (dl_se->dl_deadline == 0) {
+ dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
+ dl_se->runtime = pi_se->dl_runtime;
+ }
+
/*
* We keep moving the deadline away until we get some
* available runtime for the entity. This ensures correct
@@ -289,8 +288,8 @@ static void replenish_dl_entity(struct s
* arbitrary large.
*/
while (dl_se->runtime <= 0) {
- dl_se->deadline += dl_se->dl_period;
- dl_se->runtime += dl_se->dl_runtime;
+ dl_se->deadline += pi_se->dl_period;
+ dl_se->runtime += pi_se->dl_runtime;
}

/*
@@ -309,8 +308,8 @@ static void replenish_dl_entity(struct s
lag_once = true;
printk_sched("sched: DL replenish lagged to much\n");
}
- dl_se->deadline = rq_clock(rq) + dl_se->dl_deadline;
- dl_se->runtime = dl_se->dl_runtime;
+ dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
+ dl_se->runtime = pi_se->dl_runtime;
}
}

@@ -337,7 +336,8 @@ static void replenish_dl_entity(struct s
* task with deadline equal to period this is the same of using
* dl_deadline instead of dl_period in the equation above.
*/
-static bool dl_entity_overflow(struct sched_dl_entity *dl_se, u64 t)
+static bool dl_entity_overflow(struct sched_dl_entity *dl_se,
+ struct sched_dl_entity *pi_se, u64 t)
{
u64 left, right;

@@ -359,8 +359,8 @@ static bool dl_entity_overflow(struct sc
* of anything below microseconds resolution is actually fiction
* (but still we want to give the user that illusion >;).
*/
- left = (dl_se->dl_period >> 10) * (dl_se->runtime >> 10);
- right = ((dl_se->deadline - t) >> 10) * (dl_se->dl_runtime >> 10);
+ left = (pi_se->dl_period >> 10) * (dl_se->runtime >> 10);
+ right = ((dl_se->deadline - t) >> 10) * (pi_se->dl_runtime >> 10);

return dl_time_before(right, left);
}
@@ -374,7 +374,8 @@ static bool dl_entity_overflow(struct sc
* - using the remaining runtime with the current deadline would make
* the entity exceed its bandwidth.
*/
-static void update_dl_entity(struct sched_dl_entity *dl_se)
+static void update_dl_entity(struct sched_dl_entity *dl_se,
+ struct sched_dl_entity *pi_se)
{
struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
struct rq *rq = rq_of_dl_rq(dl_rq);
@@ -384,14 +385,14 @@ static void update_dl_entity(struct sche
* the actual scheduling parameters have to be "renewed".
*/
if (dl_se->dl_new) {
- setup_new_dl_entity(dl_se);
+ setup_new_dl_entity(dl_se, pi_se);
return;
}

if (dl_time_before(dl_se->deadline, rq_clock(rq)) ||
- dl_entity_overflow(dl_se, rq_clock(rq))) {
- dl_se->deadline = rq_clock(rq) + dl_se->dl_deadline;
- dl_se->runtime = dl_se->dl_runtime;
+ dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) {
+ dl_se->deadline = rq_clock(rq) + pi_se->dl_deadline;
+ dl_se->runtime = pi_se->dl_runtime;
}
}

@@ -405,7 +406,7 @@ static void update_dl_entity(struct sche
* actually started or not (i.e., the replenishment instant is in
* the future or in the past).
*/
-static int start_dl_timer(struct sched_dl_entity *dl_se)
+static int start_dl_timer(struct sched_dl_entity *dl_se, bool boosted)
{
struct dl_rq *dl_rq = dl_rq_of_se(dl_se);
struct rq *rq = rq_of_dl_rq(dl_rq);
@@ -414,6 +415,8 @@ static int start_dl_timer(struct sched_d
unsigned long range;
s64 delta;

+ if (boosted)
+ return 0;
/*
* We want the timer to fire at the deadline, but considering
* that it is actually coming from rq->clock and not from
@@ -573,7 +576,7 @@ static void update_curr_dl(struct rq *rq
dl_se->runtime -= delta_exec;
if (dl_runtime_exceeded(rq, dl_se)) {
__dequeue_task_dl(rq, curr, 0);
- if (likely(start_dl_timer(dl_se)))
+ if (likely(start_dl_timer(dl_se, curr->dl.dl_boosted)))
dl_se->dl_throttled = 1;
else
enqueue_task_dl(rq, curr, ENQUEUE_REPLENISH);
@@ -728,7 +731,8 @@ static void __dequeue_dl_entity(struct s
}

static void
-enqueue_dl_entity(struct sched_dl_entity *dl_se, int flags)
+enqueue_dl_entity(struct sched_dl_entity *dl_se,
+ struct sched_dl_entity *pi_se, int flags)
{
BUG_ON(on_dl_rq(dl_se));

@@ -738,9 +742,9 @@ enqueue_dl_entity(struct sched_dl_entity
* we want a replenishment of its runtime.
*/
if (!dl_se->dl_new && flags & ENQUEUE_REPLENISH)
- replenish_dl_entity(dl_se);
+ replenish_dl_entity(dl_se, pi_se);
else
- update_dl_entity(dl_se);
+ update_dl_entity(dl_se, pi_se);

__enqueue_dl_entity(dl_se);
}
@@ -752,6 +756,18 @@ static void dequeue_dl_entity(struct sch

static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags)
{
+ struct task_struct *pi_task = p->pi_top_task;
+ struct sched_dl_entity *pi_se = &p->dl;
+
+ /*
+ * Use the scheduling parameters of the top pi-waiter
+ * task if we have one and its (relative) deadline is
+ * smaller than our one... OTW we keep our runtime and
+ * deadline.
+ */
+ if (pi_task && p->dl.dl_boosted && dl_prio(pi_task->normal_prio))
+ pi_se = &pi_task->dl;
+
/*
* If p is throttled, we do nothing. In fact, if it exhausted
* its budget it needs a replenishment and, since it now is on
@@ -761,7 +777,7 @@ static void enqueue_task_dl(struct rq *r
if (p->dl.dl_throttled)
return;

- enqueue_dl_entity(&p->dl, flags);
+ enqueue_dl_entity(&p->dl, pi_se, flags);

if (!task_current(rq, p) && p->nr_cpus_allowed > 1)
enqueue_pushable_dl_task(rq, p);
@@ -985,8 +1001,7 @@ static void task_dead_dl(struct task_str
{
struct hrtimer *timer = &p->dl.dl_timer;

- if (hrtimer_active(timer))
- hrtimer_try_to_cancel(timer);
+ hrtimer_cancel(timer);
}

static void set_curr_task_dl(struct rq *rq)
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -106,6 +106,20 @@ static inline int task_has_dl_policy(str
return dl_policy(p->policy);
}

+static inline int dl_time_before(u64 a, u64 b)
+{
+ return (s64)(a - b) < 0;
+}
+
+/*
+ * Tells if entity @a should preempt entity @b.
+ */
+static inline
+int dl_entity_preempt(struct sched_dl_entity *a, struct sched_dl_entity *b)
+{
+ return dl_time_before(a->deadline, b->deadline);
+}
+
/*
* This is the priority-queue data structure of the RT scheduling class:
*/
--- a/kernel/trace/trace_sched_wakeup.c
+++ b/kernel/trace/trace_sched_wakeup.c
@@ -16,6 +16,7 @@
#include <linux/uaccess.h>
#include <linux/ftrace.h>
#include <linux/sched/rt.h>
+#include <linux/sched/deadline.h>
#include <trace/events/sched.h>
#include "trace.h"



--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/