Re: [RFC][PATCH 08/10] sched/fair: Implement delayed dequeue

Luis Machado
2024-04-15T17:08:01Z

Hi Peter,

On 4/5/24 11:28, Peter Zijlstra wrote:
> Extend / fix 86bfbb7ce4f6 ("sched/fair: Add lag based placement") by
> noting that lag is fundamentally a temporal measure. It should not be
> carried around indefinitely.
>
> OTOH it should also not be instantly discarded, doing so will allow a
> task to game the system by purposefully (micro) sleeping at the end of
> its time quantum.
>
> Since lag is intimately tied to the virtual time base, a wall-time
> based decay is also insufficient, notably competition is required for
> any of this to make sense.
>
> Instead, delay the dequeue and keep the 'tasks' on the runqueue,
> competing until they are eligible.
>
> Strictly speaking, we only care about keeping them until the 0-lag
> point, but that is a difficult proposition, instead carry them around
> until they get picked again, and dequeue them at that point.
>
> Since we should have dequeued them at the 0-lag point, truncate lag
> (eg. don't let them earn positive lag).
>
> XXX test the cfs-throttle stuff
>
> Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>

Playing around with a Pixel 6 running a 6.6-based kernel with this
series backported on top, I spotted a noticeable performance improvement
on the speedometer benchmark:

- m6.6-stock-* is the 6.6 mainline Android kernel unmodified.

- m6.6-eevdf-complete-* is the 6.6 mainline Android kernel with
this series applied on top (along with a few required backported
patches).

+-------------------+-----------------------+-----------+
| metric | tag | perc_diff |
+-------------------+-----------------------+-----------+
| Speedometer Score | m6.6-stock-1 | 0.0% |
| Speedometer Score | m6.6-stock-2 | 1.23% |
| Speedometer Score | m6.6-stock-3 | -0.22% |
| Speedometer Score | m6.6-eevdf-complete-1 | 4.54% |
| Speedometer Score | m6.6-eevdf-complete-2 | 4.95% |
| Speedometer Score | m6.6-eevdf-complete-3 | 6.07% |
+-------------------+-----------------------+-----------+

Also some interesting improvements in terms of frame timing for the
uibenchjanktests benchmark. In particular the metrics of missed
deadlines and jank (late) frames, which seems to indicate better
latencies.

+-----------------------+-----------------------+-----------+
| metric | tag | perc_diff |
+-----------------------+-----------------------+-----------+
| gfx-avg-frame-time-50 | m6.6-stock-1 | 0.0 |
| gfx-avg-frame-time-90 | m6.6-stock-1 | 0.0 |
| gfx-avg-frame-time-95 | m6.6-stock-1 | 0.0 |
| gfx-avg-frame-time-99 | m6.6-stock-1 | 0.0 |
| gfx-avg-frame-time-50 | m6.6-stock-2 | 3.46 |
| gfx-avg-frame-time-90 | m6.6-stock-2 | 1.19 |
| gfx-avg-frame-time-95 | m6.6-stock-2 | 0.24 |
| gfx-avg-frame-time-99 | m6.6-stock-2 | 0.48 |
| gfx-avg-frame-time-50 | m6.6-eevdf-complete-1 | -30.45 |
| gfx-avg-frame-time-90 | m6.6-eevdf-complete-1 | -48.44 |
| gfx-avg-frame-time-95 | m6.6-eevdf-complete-1 | -51.32 |
| gfx-avg-frame-time-99 | m6.6-eevdf-complete-1 | -52.48 |
| gfx-avg-frame-time-50 | m6.6-eevdf-complete-2 | -30.32 |
| gfx-avg-frame-time-90 | m6.6-eevdf-complete-2 | -48.16 |
| gfx-avg-frame-time-95 | m6.6-eevdf-complete-2 | -51.08 |
| gfx-avg-frame-time-99 | m6.6-eevdf-complete-2 | -51.7 |
+-----------------------+-----------------------+-----------+

+-----------------------------------+-----------------------+-----------+
| metric | tag | perc_diff |
+-----------------------------------+-----------------------+-----------+
| gfx-avg-num-frame-deadline-missed | m6.6-stock-1 | 0.0 |
| gfx-max-num-frame-deadline-missed | m6.6-stock-1 | 0.0 |
| gfx-avg-num-frame-deadline-missed | m6.6-stock-2 | -3.21 |
| gfx-max-num-frame-deadline-missed | m6.6-stock-2 | -3.21 |
| gfx-avg-num-frame-deadline-missed | m6.6-eevdf-complete-1 | -85.29 |
| gfx-max-num-frame-deadline-missed | m6.6-eevdf-complete-1 | -85.29 |
| gfx-avg-num-frame-deadline-missed | m6.6-eevdf-complete-2 | -84.8 |
| gfx-max-num-frame-deadline-missed | m6.6-eevdf-complete-2 | -84.8 |
+-----------------------------------+-----------------------+-----------+

+----------------------------+-----------------------+-----------+
| metric | tag | perc_diff |
+----------------------------+-----------------------+-----------+
| gfx-avg-high-input-latency | m6.6-stock-1 | 0.0 |
| gfx-max-high-input-latency | m6.6-stock-1 | 0.0 |
| gfx-avg-high-input-latency | m6.6-stock-2 | 0.93 |
| gfx-max-high-input-latency | m6.6-stock-2 | 0.93 |
| gfx-avg-high-input-latency | m6.6-eevdf-complete-1 | -18.35 |
| gfx-max-high-input-latency | m6.6-eevdf-complete-1 | -18.35 |
| gfx-avg-high-input-latency | m6.6-eevdf-complete-2 | -18.05 |
| gfx-max-high-input-latency | m6.6-eevdf-complete-2 | -18.05 |
+----------------------------+-----------------------+-----------+

+--------------+-----------------------+-----------+
| metric | tag | perc_diff |
+--------------+-----------------------+-----------+
| gfx-avg-jank | m6.6-stock-1 | 0.0 |
| gfx-max-jank | m6.6-stock-1 | 0.0 |
| gfx-avg-jank | m6.6-stock-2 | 1.56 |
| gfx-max-jank | m6.6-stock-2 | 1.56 |
| gfx-avg-jank | m6.6-eevdf-complete-1 | -82.81 |
| gfx-max-jank | m6.6-eevdf-complete-1 | -82.81 |
| gfx-avg-jank | m6.6-eevdf-complete-2 | -78.12 |
| gfx-max-jank | m6.6-eevdf-complete-2 | -78.12 |
+--------------+-----------------------+-----------+

Bisecting through the patches in this series, I ended up with patch 08/10
as the one that improved things overall for these benchmarks.

I'd like to investigate this further to understand the reason behind some of
these dramatic improvements.

> ---
> include/linux/sched.h | 1
> kernel/sched/core.c | 22 +++++--
> kernel/sched/fair.c | 148 +++++++++++++++++++++++++++++++++++++++++++-----
> kernel/sched/features.h | 12 +++
> kernel/sched/sched.h | 2
> 5 files changed, 167 insertions(+), 18 deletions(-)
>
> --- a/include/linux/sched.h
> +++ b/include/linux/sched.h
> @@ -542,6 +542,7 @@ struct sched_entity {
>
> struct list_head group_node;
> unsigned int on_rq;
> + unsigned int sched_delayed;
>
> u64 exec_start;
> u64 sum_exec_runtime;
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -2154,10 +2154,14 @@ void activate_task(struct rq *rq, struct
>
> void deactivate_task(struct rq *rq, struct task_struct *p, int flags)
> {
> - WRITE_ONCE(p->on_rq, (flags & DEQUEUE_SLEEP) ? 0 : TASK_ON_RQ_MIGRATING);
> - ASSERT_EXCLUSIVE_WRITER(p->on_rq);
> + bool sleep = flags & DEQUEUE_SLEEP;
>
> - dequeue_task(rq, p, flags);
> + if (dequeue_task(rq, p, flags)) {
> + WRITE_ONCE(p->on_rq, sleep ? 0 : TASK_ON_RQ_MIGRATING);
> + ASSERT_EXCLUSIVE_WRITER(p->on_rq);
> + } else {
> + SCHED_WARN_ON(!sleep); /* only sleep can fail */
> + }
> }
>
> static inline int __normal_prio(int policy, int rt_prio, int nice)
> @@ -3858,12 +3862,17 @@ static int ttwu_runnable(struct task_str
>
> rq = __task_rq_lock(p, &rf);
> if (task_on_rq_queued(p)) {
> + update_rq_clock(rq);
> + if (p->se.sched_delayed) {
> + /* mustn't run a delayed task */
> + SCHED_WARN_ON(task_on_cpu(rq, p));
> + enqueue_task(rq, p, ENQUEUE_DELAYED);
> + }
> if (!task_on_cpu(rq, p)) {
> /*
> * When on_rq && !on_cpu the task is preempted, see if
> * it should preempt the task that is current now.
> */
> - update_rq_clock(rq);
> wakeup_preempt(rq, p, wake_flags);
> }
> ttwu_do_wakeup(p);
> @@ -4243,11 +4252,16 @@ int try_to_wake_up(struct task_struct *p
> * case the whole 'p->on_rq && ttwu_runnable()' case below
> * without taking any locks.
> *
> + * Specifically, given current runs ttwu() we must be before
> + * schedule()'s deactivate_task(), as such this must not
> + * observe sched_delayed.
> + *
> * In particular:
> * - we rely on Program-Order guarantees for all the ordering,
> * - we're serialized against set_special_state() by virtue of
> * it disabling IRQs (this allows not taking ->pi_lock).
> */
> + SCHED_WARN_ON(p->se.sched_delayed);
> if (!ttwu_state_match(p, state, &success))
> goto out;
>
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -5270,6 +5270,10 @@ static inline int cfs_rq_throttled(struc
> static inline bool cfs_bandwidth_used(void);
>
> static void
> +requeue_delayed_entity(struct sched_entity *se);
> +
> +/* XXX bool and pull in the requeue_delayed_entity thing */
> +static void
> enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
> {
> bool curr = cfs_rq->curr == se;
> @@ -5356,18 +5360,33 @@ static void clear_buddies(struct cfs_rq
>
> static __always_inline void return_cfs_rq_runtime(struct cfs_rq *cfs_rq);
>
> -static void
> +static bool
> dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
> {
> - int action = UPDATE_TG;
> -
> - if (entity_is_task(se) && task_on_rq_migrating(task_of(se)))
> - action |= DO_DETACH;
> -
> /*
> * Update run-time statistics of the 'current'.
> */
> - update_curr(cfs_rq);
> + if (flags & DEQUEUE_DELAYED) {
> + SCHED_WARN_ON(!se->sched_delayed);
> + se->sched_delayed = 0;
> + } else {
> + bool sleep = flags & DEQUEUE_SLEEP;
> +
> + SCHED_WARN_ON(sleep && se->sched_delayed);
> + update_curr(cfs_rq);
> +
> + if (sched_feat(DELAY_DEQUEUE) && sleep &&
> + !entity_eligible(cfs_rq, se)) {
> + if (cfs_rq->next == se)
> + cfs_rq->next = NULL;
> + se->sched_delayed = 1;
> + return false;
> + }
> + }
> +
> + int action = UPDATE_TG;
> + if (entity_is_task(se) && task_on_rq_migrating(task_of(se)))
> + action |= DO_DETACH;
>
> /*
> * When dequeuing a sched_entity, we must:
> @@ -5407,6 +5426,8 @@ dequeue_entity(struct cfs_rq *cfs_rq, st
>
> if (cfs_rq->nr_running == 0)
> update_idle_cfs_rq_clock_pelt(cfs_rq);
> +
> + return true;
> }
>
> static void
> @@ -5432,6 +5453,7 @@ set_next_entity(struct cfs_rq *cfs_rq, s
> }
>
> update_stats_curr_start(cfs_rq, se);
> + SCHED_WARN_ON(cfs_rq->curr);
> cfs_rq->curr = se;
>
> /*
> @@ -5452,6 +5474,8 @@ set_next_entity(struct cfs_rq *cfs_rq, s
> se->prev_sum_exec_runtime = se->sum_exec_runtime;
> }
>
> +static int dequeue_entities(struct rq *rq, struct sched_entity *se, int flags);
> +
> /*
> * Pick the next process, keeping these things in mind, in this order:
> * 1) keep things fair between processes/task groups
> @@ -5460,16 +5484,29 @@ set_next_entity(struct cfs_rq *cfs_rq, s
> * 4) do not run the "skip" process, if something else is available
> */
> static struct sched_entity *
> -pick_next_entity(struct cfs_rq *cfs_rq)
> +pick_next_entity(struct rq *rq, struct cfs_rq *cfs_rq)
> {
> /*
> * Enabling NEXT_BUDDY will affect latency but not fairness.
> */
> if (sched_feat(NEXT_BUDDY) &&
> - cfs_rq->next && entity_eligible(cfs_rq, cfs_rq->next))
> + cfs_rq->next && entity_eligible(cfs_rq, cfs_rq->next)) {
> + /* ->next will never be delayed */
> + SCHED_WARN_ON(cfs_rq->next->sched_delayed);
> return cfs_rq->next;
> + }
>
> - return pick_eevdf(cfs_rq);
> + struct sched_entity *se = pick_eevdf(cfs_rq);
> + if (se->sched_delayed) {
> + dequeue_entities(rq, se, DEQUEUE_SLEEP | DEQUEUE_DELAYED);
> + SCHED_WARN_ON(se->sched_delayed);
> + SCHED_WARN_ON(se->on_rq);
> + if (sched_feat(DELAY_ZERO) && se->vlag > 0)
> + se->vlag = 0;
> +
> + return NULL;
> + }
> + return se;
> }
>
> static bool check_cfs_rq_runtime(struct cfs_rq *cfs_rq);
> @@ -5493,6 +5530,7 @@ static void put_prev_entity(struct cfs_r
> /* in !on_rq case, update occurred at dequeue */
> update_load_avg(cfs_rq, prev, 0);
> }
> + SCHED_WARN_ON(cfs_rq->curr != prev);
> cfs_rq->curr = NULL;
> }
>
> @@ -5793,6 +5831,10 @@ static bool throttle_cfs_rq(struct cfs_r
> if (!se->on_rq)
> goto done;
>
> + /*
> + * XXX should be fine vs sched_delay; if won't run after this.
> + * Either pick dequeues it, or unthrottle. Double check!!
> + */
> dequeue_entity(qcfs_rq, se, DEQUEUE_SLEEP);
>
> if (cfs_rq_is_idle(group_cfs_rq(se)))
> @@ -5882,8 +5924,11 @@ void unthrottle_cfs_rq(struct cfs_rq *cf
> for_each_sched_entity(se) {
> struct cfs_rq *qcfs_rq = cfs_rq_of(se);
>
> - if (se->on_rq)
> + if (se->on_rq) {
> + if (se->sched_delayed)
> + requeue_delayed_entity(se);
> break;
> + }
> enqueue_entity(qcfs_rq, se, ENQUEUE_WAKEUP);
>
> if (cfs_rq_is_idle(group_cfs_rq(se)))
> @@ -6729,6 +6774,40 @@ static int sched_idle_cpu(int cpu)
> }
> #endif
>
> +static void
> +requeue_delayed_entity(struct sched_entity *se)
> +{
> + struct cfs_rq *cfs_rq = cfs_rq_of(se);
> +
> + /*
> + * se->sched_delayed should imply both: se->on_rq == 1 and
> + * cfs_rq->curr != se. Because a delayed entity is one that is still on
> + * the runqueue competing until elegibility.
> + *
> + * Except for groups, consider current going idle and newidle pulling a
> + * task in the same group -- in that case 'cfs_rq->curr == se'.
> + */
> + SCHED_WARN_ON(!se->sched_delayed);
> + SCHED_WARN_ON(!se->on_rq);
> + SCHED_WARN_ON(entity_is_task(se) && cfs_rq->curr == se);
> +
> + if (sched_feat(DELAY_ZERO)) {
> + update_entity_lag(cfs_rq, se);
> + if (se->vlag > 0) {
> + cfs_rq->nr_running--;
> + if (se != cfs_rq->curr)
> + __dequeue_entity(cfs_rq, se);
> + se->vlag = 0;
> + place_entity(cfs_rq, se, 0);
> + if (se != cfs_rq->curr)
> + __enqueue_entity(cfs_rq, se);
> + cfs_rq->nr_running++;
> + }
> + }
> +
> + se->sched_delayed = 0;
> +}
> +
> /*
> * The enqueue_task method is called before nr_running is
> * increased. Here we update the fair scheduling stats and
> @@ -6742,6 +6821,11 @@ enqueue_task_fair(struct rq *rq, struct
> int idle_h_nr_running = task_has_idle_policy(p);
> int task_new = !(flags & ENQUEUE_WAKEUP);
>
> + if (flags & ENQUEUE_DELAYED) {
> + requeue_delayed_entity(se);
> + return;
> + }
> +
> /*
> * The code below (indirectly) updates schedutil which looks at
> * the cfs_rq utilization to select a frequency.
> @@ -6759,8 +6843,11 @@ enqueue_task_fair(struct rq *rq, struct
> cpufreq_update_util(rq, SCHED_CPUFREQ_IOWAIT);
>
> for_each_sched_entity(se) {
> - if (se->on_rq)
> + if (se->on_rq) {
> + if (se->sched_delayed)
> + requeue_delayed_entity(se);
> break;
> + }
> cfs_rq = cfs_rq_of(se);
> enqueue_entity(cfs_rq, se, flags);
>
> @@ -6836,6 +6923,7 @@ static int dequeue_entities(struct rq *r
> {
> bool was_sched_idle = sched_idle_rq(rq);
> bool task_sleep = flags & DEQUEUE_SLEEP;
> + bool task_delayed = flags & DEQUEUE_DELAYED;
> struct task_struct *p = NULL;
> struct cfs_rq *cfs_rq;
> int idle_h_nr_running;
> @@ -6849,7 +6937,13 @@ static int dequeue_entities(struct rq *r
>
> for_each_sched_entity(se) {
> cfs_rq = cfs_rq_of(se);
> - dequeue_entity(cfs_rq, se, flags);
> +
> + if (!dequeue_entity(cfs_rq, se, flags)) {
> + if (p && &p->se == se)
> + return -1;
> +
> + break;
> + }
>
> /* h_nr_running is the hierachical count of tasks */
> if (p) {
> @@ -6877,6 +6971,7 @@ static int dequeue_entities(struct rq *r
> break;
> }
> flags |= DEQUEUE_SLEEP;
> + flags &= ~DEQUEUE_DELAYED;
> }
>
> for_each_sched_entity(se) {
> @@ -6906,6 +7001,18 @@ static int dequeue_entities(struct rq *r
> /* balance early to pull high priority tasks */
> if (unlikely(!was_sched_idle && sched_idle_rq(rq)))
> rq->next_balance = jiffies;
> +
> + if (task_delayed) {
> + SCHED_WARN_ON(!task_sleep);
> + SCHED_WARN_ON(p->on_rq != 1);
> +
> + /* Fix-up what dequeue_task_fair() skipped */
> + util_est_update(&rq->cfs, p, task_sleep);
> + hrtick_update(rq);
> +
> + /* Fix-up what deactivate_task() skipped. */
> + WRITE_ONCE(p->on_rq, 0);
> + }
> }
>
> return 1;
> @@ -6923,6 +7030,10 @@ static bool dequeue_task_fair(struct rq
> if (dequeue_entities(rq, &p->se, flags) < 0)
> return false;
>
> + /*
> + * It doesn't make sense to update util_est for the delayed dequeue
> + * case where ttwu will make it appear the sleep never happened.
> + */
> util_est_update(&rq->cfs, p, flags & DEQUEUE_SLEEP);
> hrtick_update(rq);
> return true;
> @@ -8463,7 +8574,9 @@ static struct task_struct *pick_task_fai
> if (unlikely(check_cfs_rq_runtime(cfs_rq)))
> goto again;
>
> - se = pick_next_entity(cfs_rq);
> + se = pick_next_entity(rq, cfs_rq);
> + if (!se)
> + goto again;
> cfs_rq = group_cfs_rq(se);
> } while (cfs_rq);
>
> @@ -12803,10 +12916,17 @@ static void attach_task_cfs_rq(struct ta
> static void switched_from_fair(struct rq *rq, struct task_struct *p)
> {
> detach_task_cfs_rq(p);
> + // XXX think harder on this
> + // this could actually be handled correctly I suppose; keep the whole
> + // se enqueued while boosted. horrible complexity though
> + p->se.sched_delayed = 0;
> + // XXX also vlag ?!?
> }
>
> static void switched_to_fair(struct rq *rq, struct task_struct *p)
> {
> + SCHED_WARN_ON(p->se.sched_delayed);
> +
> attach_task_cfs_rq(p);
>
> set_task_max_allowed_capacity(p);
> --- a/kernel/sched/features.h
> +++ b/kernel/sched/features.h
> @@ -29,6 +29,18 @@ SCHED_FEAT(NEXT_BUDDY, false)
> SCHED_FEAT(CACHE_HOT_BUDDY, true)
>
> /*
> + * Delay dequeueing tasks until they get selected or woken.
> + *
> + * By delaying the dequeue for non-eligible tasks, they remain in the
> + * competition and can burn off their negative lag. When they get selected
> + * they'll have positive lag by definition.
> + *
> + * DELAY_ZERO clips the lag on dequeue (or wakeup) to 0.
> + */
> +SCHED_FEAT(DELAY_DEQUEUE, true)
> +SCHED_FEAT(DELAY_ZERO, true)
> +
> +/*
> * Allow wakeup-time preemption of the current task:
> */
> SCHED_FEAT(WAKEUP_PREEMPTION, true)
> --- a/kernel/sched/sched.h
> +++ b/kernel/sched/sched.h
> @@ -2245,6 +2245,7 @@ extern const u32 sched_prio_to_wmult[40
> #define DEQUEUE_MOVE 0x04 /* Matches ENQUEUE_MOVE */
> #define DEQUEUE_NOCLOCK 0x08 /* Matches ENQUEUE_NOCLOCK */
> #define DEQUEUE_MIGRATING 0x100 /* Matches ENQUEUE_MIGRATING */
> +#define DEQUEUE_DELAYED 0x200 /* Matches ENQUEUE_DELAYED */
>
> #define ENQUEUE_WAKEUP 0x01
> #define ENQUEUE_RESTORE 0x02
> @@ -2260,6 +2261,7 @@ extern const u32 sched_prio_to_wmult[40
> #endif
> #define ENQUEUE_INITIAL 0x80
> #define ENQUEUE_MIGRATING 0x100
> +#define ENQUEUE_DELAYED 0x200
>
> #define RETRY_TASK ((void *)-1UL)
>
>
>
>