Hi, On 24/10/16 16:06, Luca Abeni wrote: > This patch implements a more theoretically sound algorithm for > thracking the active utilisation: instead of decreasing it when a
s/thracking/tracking/ s/the// > task blocks, use a timer (the "inactive timer", named after the > "Inactive" task state of the GRUB algorithm) to decrease the > active utilisaation at the so called "0-lag time". s/utilisaation/utilisation/ > > Signed-off-by: Luca Abeni <[email protected]> > --- > include/linux/sched.h | 1 + > kernel/sched/core.c | 1 + > kernel/sched/deadline.c | 139 > ++++++++++++++++++++++++++++++++++++++++++------ > kernel/sched/sched.h | 1 + > 4 files changed, 126 insertions(+), 16 deletions(-) > > diff --git a/include/linux/sched.h b/include/linux/sched.h > index 348f51b..22543c6 100644 > --- a/include/linux/sched.h > +++ b/include/linux/sched.h > @@ -1433,6 +1433,7 @@ struct sched_dl_entity { > * own bandwidth to be enforced, thus we need one timer per task. > */ > struct hrtimer dl_timer; > + struct hrtimer inactive_timer; > }; > > union rcu_special { > diff --git a/kernel/sched/core.c b/kernel/sched/core.c > index 94732d1..664c618 100644 > --- a/kernel/sched/core.c > +++ b/kernel/sched/core.c > @@ -2217,6 +2217,7 @@ static void __sched_fork(unsigned long clone_flags, > struct task_struct *p) > > RB_CLEAR_NODE(&p->dl.rb_node); > init_dl_task_timer(&p->dl); > + init_inactive_task_timer(&p->dl); > __dl_clear_params(p); > > INIT_LIST_HEAD(&p->rt.run_list); > diff --git a/kernel/sched/deadline.c b/kernel/sched/deadline.c > index 3d95c1d..80d1541 100644 > --- a/kernel/sched/deadline.c > +++ b/kernel/sched/deadline.c > @@ -47,6 +47,7 @@ static void add_running_bw(struct sched_dl_entity *dl_se, > struct dl_rq *dl_rq) > { > u64 se_bw = dl_se->dl_bw; > > + lockdep_assert_held(&(rq_of_dl_rq(dl_rq))->lock); This and the one below go in 1/6. > dl_rq->running_bw += se_bw; > } > > @@ -54,11 +55,52 @@ static void sub_running_bw(struct sched_dl_entity *dl_se, > struct dl_rq *dl_rq) > { > u64 se_bw = dl_se->dl_bw; > > + lockdep_assert_held(&(rq_of_dl_rq(dl_rq))->lock); > dl_rq->running_bw -= se_bw; > if (WARN_ON(dl_rq->running_bw < 0)) > dl_rq->running_bw = 0; > } > > +static void task_go_inactive(struct task_struct *p) > +{ > + struct sched_dl_entity *dl_se = &p->dl; > + struct hrtimer *timer = &dl_se->inactive_timer; > + struct dl_rq *dl_rq = dl_rq_of_se(dl_se); > + struct rq *rq = rq_of_dl_rq(dl_rq); > + s64 zerolag_time; > + > + WARN_ON(dl_se->dl_runtime == 0); > + > + /* If the inactive timer is already armed, return immediately */ > + if (hrtimer_active(&dl_se->inactive_timer)) > + return; > + > + zerolag_time = dl_se->deadline - > + div64_long((dl_se->runtime * dl_se->dl_period), > + dl_se->dl_runtime); > + > + /* > + * Using relative times instead of the absolute "0-lag time" > + * allows to simplify the code > + */ > + zerolag_time -= rq_clock(rq); > + > + /* > + * If the "0-lag time" already passed, decrease the active > + * utilization now, instead of starting a timer > + */ > + if (zerolag_time < 0) { > + sub_running_bw(dl_se, dl_rq); > + if (!dl_task(p)) > + __dl_clear_params(p); > + > + return; > + } > + > + get_task_struct(p); > + hrtimer_start(timer, ns_to_ktime(zerolag_time), HRTIMER_MODE_REL); > +} > + > static inline int is_leftmost(struct task_struct *p, struct dl_rq *dl_rq) > { > struct sched_dl_entity *dl_se = &p->dl; > @@ -514,7 +556,20 @@ static void update_dl_entity(struct sched_dl_entity > *dl_se, > struct dl_rq *dl_rq = dl_rq_of_se(dl_se); > struct rq *rq = rq_of_dl_rq(dl_rq); > > - add_running_bw(dl_se, dl_rq); > + if (hrtimer_is_queued(&dl_se->inactive_timer)) { > + hrtimer_try_to_cancel(&dl_se->inactive_timer); Why we are OK with just trying to cancel the inactive timer? > + WARN_ON(dl_task_of(dl_se)->nr_cpus_allowed > 1); What's wrong with nr_cpus_allowed > 1 tasks? > + } else { > + /* > + * The "inactive timer" has been cancelled in > + * select_task_rq_dl() (and the acvive utilisation has > + * been decreased). So, increase the active utilisation. > + * If select_task_rq_dl() could not cancel the timer, > + * inactive_task_timer() will * find the task state as > + * TASK_RUNNING, and will do nothing, so we are still safe. > + */ > + add_running_bw(dl_se, dl_rq); > + } > > if (dl_time_before(dl_se->deadline, rq_clock(rq)) || > dl_entity_overflow(dl_se, pi_se, rq_clock(rq))) { > @@ -602,14 +657,8 @@ static enum hrtimer_restart dl_task_timer(struct hrtimer > *timer) > > rq = task_rq_lock(p, &rf); > > - /* > - * The task might have changed its scheduling policy to something > - * different than SCHED_DEADLINE (through switched_fromd_dl()). > - */ > - if (!dl_task(p)) { > - __dl_clear_params(p); > + if (!dl_task(p)) > goto unlock; > - } > > /* > * The task might have been boosted by someone else and might be in the > @@ -796,6 +845,44 @@ static void update_curr_dl(struct rq *rq) > } > } > > +static enum hrtimer_restart inactive_task_timer(struct hrtimer *timer) > +{ > + struct sched_dl_entity *dl_se = container_of(timer, > + struct sched_dl_entity, > + inactive_timer); > + struct task_struct *p = dl_task_of(dl_se); > + struct rq_flags rf; > + struct rq *rq; > + > + rq = task_rq_lock(p, &rf); > + > + if (!dl_task(p)) { > + __dl_clear_params(p); > + > + goto unlock; > + } > + if (p->state == TASK_RUNNING) > + goto unlock; > + > + sched_clock_tick(); > + update_rq_clock(rq); > + > + sub_running_bw(dl_se, &rq->dl); > +unlock: > + task_rq_unlock(rq, p, &rf); > + put_task_struct(p); > + > + return HRTIMER_NORESTART; > +} > + > +void init_inactive_task_timer(struct sched_dl_entity *dl_se) > +{ > + struct hrtimer *timer = &dl_se->inactive_timer; > + > + hrtimer_init(timer, CLOCK_MONOTONIC, HRTIMER_MODE_REL); > + timer->function = inactive_task_timer; > +} > + > #ifdef CONFIG_SMP > > static void inc_dl_deadline(struct dl_rq *dl_rq, u64 deadline) > @@ -1000,7 +1087,7 @@ static void dequeue_task_dl(struct rq *rq, struct > task_struct *p, int flags) > sub_running_bw(&p->dl, &rq->dl); > > if (flags & DEQUEUE_SLEEP) > - sub_running_bw(&p->dl, &rq->dl); > + task_go_inactive(p); > } > > /* > @@ -1074,6 +1161,14 @@ select_task_rq_dl(struct task_struct *p, int cpu, int > sd_flag, int flags) > } > rcu_read_unlock(); > > + rq = task_rq(p); > + raw_spin_lock(&rq->lock); > + if (hrtimer_active(&p->dl.inactive_timer)) { > + sub_running_bw(&p->dl, &rq->dl); > + hrtimer_try_to_cancel(&p->dl.inactive_timer); Can't we subtract twice if it happens that after we grabbed rq_lock the timer fired, so it's now waiting for that lock and it goes ahead and sub_running_bw again after we release the lock? > + } > + raw_spin_unlock(&rq->lock); > + > out: > return cpu; > } > @@ -1244,6 +1339,11 @@ static void task_dead_dl(struct task_struct *p) > /* XXX we should retain the bw until 0-lag */ > dl_b->total_bw -= p->dl.dl_bw; > raw_spin_unlock_irq(&dl_b->lock); > + if (hrtimer_active(&p->dl.inactive_timer)) { > + raw_spin_lock_irq(&task_rq(p)->lock); > + sub_running_bw(&p->dl, dl_rq_of_se(&p->dl)); Don't we still need to wait for the 0-lag? Or maybe since the task is dying we can release it's bw instantaneously? In this case I'd add a comment about it. > + raw_spin_unlock_irq(&task_rq(p)->lock); > + } > } > > static void set_curr_task_dl(struct rq *rq) > @@ -1720,15 +1820,22 @@ void __init init_sched_dl_class(void) > static void switched_from_dl(struct rq *rq, struct task_struct *p) > { > /* > - * Start the deadline timer; if we switch back to dl before this we'll > - * continue consuming our current CBS slice. If we stay outside of > - * SCHED_DEADLINE until the deadline passes, the timer will reset the > - * task. > + * task_go_inactive() can start the "inactive timer" (if the 0-lag > + * time is in the future). If the task switches back to dl before > + * the "inactive timer" fires, it can continue to consume its current > + * runtime using its current deadline. If it stays outside of > + * SCHED_DEADLINE until the 0-lag time passes, inactive_task_timer() > + * will reset the task parameters. > */ > - if (!start_dl_timer(p)) > - __dl_clear_params(p); > + if (task_on_rq_queued(p) && p->dl.dl_runtime) > + task_go_inactive(p); > > - if (task_on_rq_queued(p)) > + /* > + * We cannot use inactive_task_timer() to invoke sub_running_bw() > + * at the 0-lag time, because the task could have been migrated > + * while SCHED_OTHER in the meanwhile. But, from a theoretical pow, we very much should, right? Is this taken care of in next patch? > + */ > + if (hrtimer_is_queued(&p->dl.inactive_timer)) > sub_running_bw(&p->dl, &rq->dl); > Thanks, - Juri
