Re: [RFC PATCH v2 4/6] sched/deadline: Introduce deadline servers
From: Juri Lelli
Date: Tue Oct 06 2020 - 05:35:36 EST
On 06/10/20 09:56, luca abeni wrote:
> Hi,
>
> sorry for the late reply... Anyway, I am currently testing this
> patchset (and trying to use it for the "SCHED_DEADLINE-based cgroup
> scheduling" patchset).
> And during my tests I had a doubt:
>
>
>
> On Fri, 7 Aug 2020 11:50:49 +0200
> Juri Lelli <juri.lelli@xxxxxxxxxx> wrote:
>
> > From: Peter Zijlstra <peterz@xxxxxxxxxxxxx>
> >
> > Low priority tasks (e.g., SCHED_OTHER) can suffer starvation if tasks
> > with higher priority (e.g., SCHED_FIFO) monopolize CPU(s).
> [...]
> > @@ -1024,10 +1062,34 @@ static enum hrtimer_restart dl_task_timer(struct hrtimer *timer)
> > struct sched_dl_entity *dl_se = container_of(timer,
> > struct sched_dl_entity,
> > dl_timer);
> > - struct task_struct *p = dl_task_of(dl_se);
> > + struct task_struct *p;
> > struct rq_flags rf;
> > struct rq *rq;
> >
> > + if (dl_server(dl_se)) {
> > + struct rq *rq = rq_of_dl_se(dl_se);
> > + struct rq_flags rf;
> > +
> > + rq_lock(rq, &rf);
> > + if (dl_se->dl_throttled) {
> > + sched_clock_tick();
> > + update_rq_clock(rq);
> > +
> > + if (dl_se->server_has_tasks(dl_se)) {
> > + enqueue_dl_entity(dl_se, dl_se, ENQUEUE_REPLENISH);
> > + resched_curr(rq);
> > + __push_dl_task(rq, &rf);
> > + } else {
> > + replenish_dl_entity(dl_se, dl_se);
>
> I am wondering if here we need a "task_non_contending(dl_se)" after
> "replenish_dl_entity(dl_se, dl_se);"...
>
> Basically, what happened is that all the served tasks blocked while the
> server was throttled... So, now the server should be disabled (so, we
> replenish the dl entity but we do not insert it in runqueue).
> But when the server finished its budget and has been throttled, it has
> not been disabled (so, its utilization is still in running_bw).
Hummm. For CFS, we call dl_server_stop() after the last CFS task blocks
and that calls dequeue_dl(SLEEP), which should be calling
task_non_contending(). That should be happening also while the server is
throttled and CFS tasks are running outside of it, no? Guess I'm missing
something.
> I think that if we do not call task_non_contending() the server's
> utilization is not correctly removed from running_bw (this does not
> happen for regular tasks, because task_non_contending() is invoked when
> they block, even if the dl entity is throttled... But for servers I
> think we have an issue).
>
> What do you think? Do you agree with this change?
>
> I have no easy way to reproduce the issue, but this change fixed some
> strange behaviours I was seeing when using this patch to schedule RT
> cgroups.
>
>
>
> Thanks,
> Luca
> > + }
> > +
> > + }
> > + rq_unlock(rq, &rf);
> > +
> > + return HRTIMER_NORESTART;
> > + }
> > +
> > + p = dl_task_of(dl_se);
> > rq = task_rq_lock(p, &rf);
> >
> > /*
> > @@ -1098,21 +1160,7 @@ static enum hrtimer_restart dl_task_timer(struct hrtimer *timer)
> > else
> > resched_curr(rq);
> >
> > -#ifdef CONFIG_SMP
> > - /*
> > - * Queueing this task back might have overloaded rq, check if we need
> > - * to kick someone away.
> > - */
> > - if (has_pushable_dl_tasks(rq)) {
> > - /*
> > - * Nothing relies on rq->lock after this, so its safe to drop
> > - * rq->lock.
> > - */
> > - rq_unpin_lock(rq, &rf);
> > - push_dl_task(rq);
> > - rq_repin_lock(rq, &rf);
> > - }
> > -#endif
> > + __push_dl_task(rq, &rf);
> >
> > unlock:
> > task_rq_unlock(rq, p, &rf);
> > @@ -1154,12 +1202,11 @@ static void init_dl_task_timer(struct sched_dl_entity *dl_se)
> > */
> > static inline void dl_check_constrained_dl(struct sched_dl_entity *dl_se)
> > {
> > - struct task_struct *p = dl_task_of(dl_se);
> > - struct rq *rq = rq_of_dl_rq(dl_rq_of_se(dl_se));
> > + struct rq *rq = rq_of_dl_se(dl_se);
> >
> > if (dl_time_before(dl_se->deadline, rq_clock(rq)) &&
> > dl_time_before(rq_clock(rq), dl_next_period(dl_se))) {
> > - if (unlikely(dl_se->dl_boosted || !start_dl_timer(p)))
> > + if (unlikely(dl_se->dl_boosted || !start_dl_timer(dl_se)))
> > return;
> > dl_se->dl_throttled = 1;
> > if (dl_se->runtime > 0)
> > @@ -1216,29 +1263,10 @@ static u64 grub_reclaim(u64 delta, struct rq *rq, struct sched_dl_entity *dl_se)
> > return (delta * u_act) >> BW_SHIFT;
> > }
> >
> > -/*
> > - * Update the current task's runtime statistics (provided it is still
> > - * a -deadline task and has not been removed from the dl_rq).
> > - */
> > -static void update_curr_dl(struct rq *rq)
> > +static void update_curr_dl_se(struct rq *rq, struct sched_dl_entity *dl_se, s64 delta_exec)
> > {
> > - struct task_struct *curr = rq->curr;
> > - struct sched_dl_entity *dl_se = &curr->dl;
> > - s64 delta_exec, scaled_delta_exec;
> > - int cpu = cpu_of(rq);
> > + s64 scaled_delta_exec;
> >
> > - if (!dl_task(curr) || !on_dl_rq(dl_se))
> > - return;
> > -
> > - /*
> > - * Consumed budget is computed considering the time as
> > - * observed by schedulable tasks (excluding time spent
> > - * in hardirq context, etc.). Deadlines are instead
> > - * computed using hard walltime. This seems to be the more
> > - * natural solution, but the full ramifications of this
> > - * approach need further study.
> > - */
> > - delta_exec = update_curr_common(rq);
> > if (unlikely(delta_exec <= 0)) {
> > if (unlikely(dl_se->dl_yielded))
> > goto throttle;
> > @@ -1256,10 +1284,9 @@ static void update_curr_dl(struct rq *rq)
> > * according to current frequency and CPU maximum capacity.
> > */
> > if (unlikely(dl_se->flags & SCHED_FLAG_RECLAIM)) {
> > - scaled_delta_exec = grub_reclaim(delta_exec,
> > - rq,
> > - &curr->dl);
> > + scaled_delta_exec = grub_reclaim(delta_exec, rq, dl_se);
> > } else {
> > + int cpu = cpu_of(rq);
> > unsigned long scale_freq = arch_scale_freq_capacity(cpu);
> > unsigned long scale_cpu = arch_scale_cpu_capacity(cpu);
> >
> > @@ -1278,11 +1305,18 @@ static void update_curr_dl(struct rq *rq)
> > (dl_se->flags & SCHED_FLAG_DL_OVERRUN))
> > dl_se->dl_overrun = 1;
> >
> > - __dequeue_task_dl(rq, curr, 0);
> > - if (unlikely(dl_se->dl_boosted || !start_dl_timer(curr)))
> > - enqueue_task_dl(rq, curr, ENQUEUE_REPLENISH);
> > + dequeue_dl_entity(dl_se, 0);
> > + if (!dl_server(dl_se))
> > + dequeue_pushable_dl_task(rq, dl_task_of(dl_se));
> >
> > - if (!is_leftmost(curr, &rq->dl))
> > + if (unlikely(dl_se->dl_boosted || !start_dl_timer(dl_se))) {
> > + if (dl_server(dl_se))
> > + enqueue_dl_entity(dl_se, dl_se, ENQUEUE_REPLENISH);
> > + else
> > + enqueue_task_dl(rq, dl_task_of(dl_se), ENQUEUE_REPLENISH);
> > + }
> > +
> > + if (!is_leftmost(dl_se, &rq->dl))
> > resched_curr(rq);
> > }
> >
> > @@ -1312,20 +1346,82 @@ static void update_curr_dl(struct rq *rq)
> > }
> > }
> >
> > +void dl_server_update(struct sched_dl_entity *dl_se, s64 delta_exec)
> > +{
> > + update_curr_dl_se(dl_se->rq, dl_se, delta_exec);
> > +}
> > +
> > +void dl_server_start(struct sched_dl_entity *dl_se)
> > +{
> > + if (!dl_server(dl_se)) {
> > + dl_se->dl_server = 1;
> > + setup_new_dl_entity(dl_se);
> > + }
> > + enqueue_dl_entity(dl_se, dl_se, ENQUEUE_WAKEUP);
> > +}
> > +
> > +void dl_server_stop(struct sched_dl_entity *dl_se)
> > +{
> > + dequeue_dl_entity(dl_se, DEQUEUE_SLEEP);
> > +}
> > +
> > +void dl_server_init(struct sched_dl_entity *dl_se, struct rq *rq,
> > + dl_server_has_tasks_f has_tasks,
> > + dl_server_pick_f pick)
> > +{
> > + dl_se->rq = rq;
> > + dl_se->server_has_tasks = has_tasks;
> > + dl_se->server_pick = pick;
> > +}
> > +
> > +/*
> > + * Update the current task's runtime statistics (provided it is still
> > + * a -deadline task and has not been removed from the dl_rq).
> > + */
> > +static void update_curr_dl(struct rq *rq)
> > +{
> > + struct task_struct *curr = rq->curr;
> > + struct sched_dl_entity *dl_se = &curr->dl;
> > + s64 delta_exec;
> > +
> > + if (!dl_task(curr) || !on_dl_rq(dl_se))
> > + return;
> > +
> > + /*
> > + * Consumed budget is computed considering the time as
> > + * observed by schedulable tasks (excluding time spent
> > + * in hardirq context, etc.). Deadlines are instead
> > + * computed using hard walltime. This seems to be the more
> > + * natural solution, but the full ramifications of this
> > + * approach need further study.
> > + */
> > + delta_exec = update_curr_common(rq);
> > + update_curr_dl_se(rq, dl_se, delta_exec);
> > +}
> > +
> > 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 task_struct *p = NULL;
> > struct rq_flags rf;
> > struct rq *rq;
> >
> > - rq = task_rq_lock(p, &rf);
> > + if (!dl_server(dl_se)) {
> > + p = dl_task_of(dl_se);
> > + rq = task_rq_lock(p, &rf);
> > + } else {
> > + rq = dl_se->rq;
> > + rq_lock(rq, &rf);
> > + }
> >
> > sched_clock_tick();
> > update_rq_clock(rq);
> >
> > + if (dl_server(dl_se))
> > + goto no_task;
> > +
> > if (!dl_task(p) || p->state == TASK_DEAD) {
> > struct dl_bw *dl_b = dl_bw_of(task_cpu(p));
> >
> > @@ -1342,14 +1438,21 @@ static enum hrtimer_restart inactive_task_timer(struct hrtimer *timer)
> >
> > goto unlock;
> > }
> > +
> > +no_task:
> > if (dl_se->dl_non_contending == 0)
> > goto unlock;
> >
> > sub_running_bw(dl_se, &rq->dl);
> > dl_se->dl_non_contending = 0;
> > unlock:
> > - task_rq_unlock(rq, p, &rf);
> > - put_task_struct(p);
> > +
> > + if (!dl_server(dl_se)) {
> > + task_rq_unlock(rq, p, &rf);
> > + put_task_struct(p);
> > + } else {
> > + rq_unlock(rq, &rf);
> > + }
> >
> > return HRTIMER_NORESTART;
> > }
> > @@ -1402,34 +1505,35 @@ static void dec_dl_deadline(struct dl_rq *dl_rq, u64 deadline)
> > static inline void inc_dl_deadline(struct dl_rq *dl_rq, u64 deadline) {}
> > static inline void dec_dl_deadline(struct dl_rq *dl_rq, u64 deadline) {}
> >
> > +static inline void update_dl_migration(struct dl_rq *dl_rq) {}
> > +
> > #endif /* CONFIG_SMP */
> >
> > static inline
> > void inc_dl_tasks(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
> > {
> > - int prio = dl_task_of(dl_se)->prio;
> > u64 deadline = dl_se->deadline;
> >
> > - WARN_ON(!dl_prio(prio));
> > dl_rq->dl_nr_running++;
> > add_nr_running(rq_of_dl_rq(dl_rq), 1);
> >
> > inc_dl_deadline(dl_rq, deadline);
> > - inc_dl_migration(dl_se, dl_rq);
> > + if (!dl_server(dl_se))
> > + inc_dl_migration(dl_se, dl_rq);
> > + update_dl_migration(dl_rq);
> > }
> >
> > static inline
> > void dec_dl_tasks(struct sched_dl_entity *dl_se, struct dl_rq *dl_rq)
> > {
> > - int prio = dl_task_of(dl_se)->prio;
> > -
> > - WARN_ON(!dl_prio(prio));
> > WARN_ON(!dl_rq->dl_nr_running);
> > dl_rq->dl_nr_running--;
> > sub_nr_running(rq_of_dl_rq(dl_rq), 1);
> >
> > dec_dl_deadline(dl_rq, dl_se->deadline);
> > - dec_dl_migration(dl_se, dl_rq);
> > + if (!dl_server(dl_se))
> > + dec_dl_migration(dl_se, dl_rq);
> > + update_dl_migration(dl_rq);
> > }
> >
> > static void __enqueue_dl_entity(struct sched_dl_entity *dl_se)
> > @@ -1524,8 +1628,7 @@ enqueue_dl_entity(struct sched_dl_entity *dl_se,
> > } else if (flags & ENQUEUE_REPLENISH) {
> > replenish_dl_entity(dl_se, pi_se);
> > } else if ((flags & ENQUEUE_RESTORE) &&
> > - dl_time_before(dl_se->deadline,
> > - rq_clock(rq_of_dl_rq(dl_rq_of_se(dl_se))))) {
> > + dl_time_before(dl_se->deadline, rq_clock(rq_of_dl_se(dl_se)))) {
> > setup_new_dl_entity(dl_se);
> > }
> >
> > @@ -1592,14 +1695,6 @@ static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags)
> > enqueue_pushable_dl_task(rq, p);
> > }
> >
> > -static void __dequeue_task_dl(struct rq *rq, struct task_struct *p, int flags)
> > -{
> > - dequeue_dl_entity(&p->dl, flags);
> > -
> > - if (!p->dl.dl_throttled)
> > - dequeue_pushable_dl_task(rq, p);
> > -}
> > -
> > static void dequeue_task_dl(struct rq *rq, struct task_struct *p, int flags)
> > {
> > update_curr_dl(rq);
> > @@ -1607,7 +1702,9 @@ static void dequeue_task_dl(struct rq *rq, struct task_struct *p, int flags)
> > if (p->on_rq == TASK_ON_RQ_MIGRATING)
> > flags |= DEQUEUE_MIGRATING;
> >
> > - __dequeue_task_dl(rq, p, flags);
> > + dequeue_dl_entity(&p->dl, flags);
> > + if (!p->dl.dl_throttled)
> > + dequeue_pushable_dl_task(rq, p);
> > }
> >
> > /*
> > @@ -1789,12 +1886,12 @@ static void check_preempt_curr_dl(struct rq *rq, struct task_struct *p,
> > }
> >
> > #ifdef CONFIG_SCHED_HRTICK
> > -static void start_hrtick_dl(struct rq *rq, struct task_struct *p)
> > +static void start_hrtick_dl(struct rq *rq, struct sched_dl_entity *dl_se)
> > {
> > - hrtick_start(rq, p->dl.runtime);
> > + hrtick_start(rq, dl_se->runtime);
> > }
> > #else /* !CONFIG_SCHED_HRTICK */
> > -static void start_hrtick_dl(struct rq *rq, struct task_struct *p)
> > +static void start_hrtick_dl(struct rq *rq, struct sched_dl_entity *dl_se)
> > {
> > }
> > #endif
> > @@ -1809,9 +1906,6 @@ static void set_next_task_dl(struct rq *rq, struct task_struct *p, bool first)
> > if (!first)
> > return;
> >
> > - if (hrtick_enabled(rq))
> > - start_hrtick_dl(rq, p);
> > -
> > if (rq->curr->sched_class != &dl_sched_class)
> > update_dl_rq_load_avg(rq_clock_pelt(rq), rq, 0);
> >
> > @@ -1835,13 +1929,30 @@ static struct task_struct *pick_next_task_dl(struct rq *rq)
> > struct dl_rq *dl_rq = &rq->dl;
> > struct task_struct *p;
> >
> > +again:
> > if (!sched_dl_runnable(rq))
> > return NULL;
> >
> > dl_se = pick_next_dl_entity(rq, dl_rq);
> > BUG_ON(!dl_se);
> > - p = dl_task_of(dl_se);
> > - set_next_task_dl(rq, p, true);
> > + if (dl_server(dl_se)) {
> > + p = dl_se->server_pick(dl_se);
> > + if (!p) {
> > + // XXX should not happen, warn?!
> > + dl_se->dl_yielded = 1;
> > + update_curr_dl_se(rq, dl_se, 0);
> > + goto again;
> > + }
> > + p->server = dl_se;
> > + } else {
> > + p = dl_task_of(dl_se);
> > + set_next_task_dl(rq, p, true);
> > + }
> > +
> > + /* XXX not quite right */
> > + if (hrtick_enabled(rq))
> > + start_hrtick_dl(rq, dl_se);
> > +
> > return p;
> > }
> >
> > @@ -1873,8 +1984,8 @@ static void task_tick_dl(struct rq *rq, struct task_struct *p, int queued)
> > * be set and schedule() will start a new hrtick for the next task.
> > */
> > if (hrtick_enabled(rq) && queued && p->dl.runtime > 0 &&
> > - is_leftmost(p, &rq->dl))
> > - start_hrtick_dl(rq, p);
> > + is_leftmost(&p->dl, &rq->dl))
> > + start_hrtick_dl(rq, &p->dl);
> > }
> >
> > static void task_fork_dl(struct task_struct *p)
> > @@ -2771,6 +2882,7 @@ static void __dl_clear_params(struct sched_dl_entity *dl_se)
> > dl_se->dl_yielded = 0;
> > dl_se->dl_non_contending = 0;
> > dl_se->dl_overrun = 0;
> > + dl_se->dl_server = 0;
> > }
> >
> > void init_dl_entity(struct sched_dl_entity *dl_se)
> > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> > index 10a230d85104a..5130239c0e1e5 100644
> > --- a/kernel/sched/fair.c
> > +++ b/kernel/sched/fair.c
> > @@ -868,6 +868,8 @@ s64 update_curr_common(struct rq *rq)
> >
> > account_group_exec_runtime(curr, delta_exec);
> > cgroup_account_cputime(curr, delta_exec);
> > + if (curr->server)
> > + dl_server_update(curr->server, delta_exec);
> >
> > return delta_exec;
> > }
> > @@ -897,6 +899,8 @@ static void update_curr(struct cfs_rq *cfs_rq)
> > trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
> > cgroup_account_cputime(curtask, delta_exec);
> > account_group_exec_runtime(curtask, delta_exec);
> > + if (curtask->server)
> > + dl_server_update(curtask->server, delta_exec);
> > }
> >
> > account_cfs_rq_runtime(cfs_rq, delta_exec);
> > diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
> > index d3db8c7d8b641..f035cd8ccd224 100644
> > --- a/kernel/sched/sched.h
> > +++ b/kernel/sched/sched.h
> > @@ -346,6 +346,35 @@ extern int dl_task_can_attach(struct task_struct *p, const struct cpumask *cs_c
> > extern int dl_cpuset_cpumask_can_shrink(const struct cpumask *cur, const struct cpumask *trial);
> > extern bool dl_cpu_busy(unsigned int cpu);
> >
> > +/*
> > + * SCHED_DEADLINE supports servers (nested scheduling) with the following
> > + * interface:
> > + *
> > + * dl_se::rq -- runqueue we belong to.
> > + *
> > + * dl_se::server_has_tasks() -- used on bandwidth enforcement; we 'stop' the
> > + * server when it runs out of tasks to run.
> > + *
> > + * dl_se::server_pick() -- nested pick_next_task(); we yield the period if this
> > + * returns NULL.
> > + *
> > + * dl_server_update() -- called from update_curr_common(), propagates runtime
> > + * to the server.
> > + *
> > + * dl_server_start()
> > + * dl_server_stop() -- start/stop the server when it has (no) tasks
> > + *
> > + * dl_server_init()
> > + *
> > + * XXX
> > + */
> > +extern void dl_server_update(struct sched_dl_entity *dl_se, s64 delta_exec);
> > +extern void dl_server_start(struct sched_dl_entity *dl_se);
> > +extern void dl_server_stop(struct sched_dl_entity *dl_se);
> > +extern void dl_server_init(struct sched_dl_entity *dl_se, struct rq *rq,
> > + dl_server_has_tasks_f has_tasks,
> > + dl_server_pick_f pick);
> > +
> > #ifdef CONFIG_CGROUP_SCHED
> >
> > #include <linux/cgroup.h>
>