[PATCH] sched/fair: Only increment deadline once on yield

[PATCH] sched/fair: Only increment deadline once on yield

[Fernand Sieber]

If a task yields, the scheduler may decide to pick it again. The task in
turn may decide to yield immediately or shortly after, leading to a tight
loop of yields.

If there's another runnable task as this point, the deadline will be
increased by the slice at each loop. This can cause the deadline to runaway
pretty quickly, and subsequent elevated run delays later on as the task
doesn't get picked again. The reason the scheduler can pick the same task
again and again despite its deadline increasing is because it may be the
only eligible task at that point.

Fix this by updating the deadline only to one slice ahead.

Note, we might want to consider iterating on the implementation of yield as
follow up:
* the yielding task could be forfeiting its remaining slice by
  incrementing its vruntime correspondingly
* in case of yield_to the yielding task could be donating its remaining
  slice to the target task

Signed-off-by: Fernand Sieber <sieberf@amazon.com>
---
 kernel/sched/fair.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index e43993a4e580..c1eff68d8ffc 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -9024,7 +9024,7 @@ static void yield_task_fair(struct rq *rq)
 	 */
 	rq_clock_skip_update(rq);

-	se->deadline += calc_delta_fair(se->slice, se);
+	se->deadline = se->vruntime + calc_delta_fair(se->slice, se);
 }

 static bool yield_to_task_fair(struct rq *rq, struct task_struct *p)
--
2.47.1




Amazon Development Centre (South Africa) (Proprietary) Limited
29 Gogosoa Street, Observatory, Cape Town, Western Cape, 7925, South Africa
Registration Number: 2004 / 034463 / 07

Re: [PATCH] sched/fair: Only increment deadline once on yield

[Madadi Vineeth Reddy]

Hi Fernand,

On 01/04/25 18:06, Fernand Sieber wrote:
> If a task yields, the scheduler may decide to pick it again. The task in
> turn may decide to yield immediately or shortly after, leading to a tight
> loop of yields.
> 
> If there's another runnable task as this point, the deadline will be
> increased by the slice at each loop. This can cause the deadline to runaway
> pretty quickly, and subsequent elevated run delays later on as the task
> doesn't get picked again. The reason the scheduler can pick the same task
> again and again despite its deadline increasing is because it may be the
> only eligible task at that point.
> 
> Fix this by updating the deadline only to one slice ahead.
> 
> Note, we might want to consider iterating on the implementation of yield as
> follow up:
> * the yielding task could be forfeiting its remaining slice by
>   incrementing its vruntime correspondingly
> * in case of yield_to the yielding task could be donating its remaining
>   slice to the target task
> 
> Signed-off-by: Fernand Sieber <sieberf@amazon.com>
> ---
>  kernel/sched/fair.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index e43993a4e580..c1eff68d8ffc 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -9024,7 +9024,7 @@ static void yield_task_fair(struct rq *rq)
>  	 */
>  	rq_clock_skip_update(rq);
> 
> -	se->deadline += calc_delta_fair(se->slice, se);
> +	se->deadline = se->vruntime + calc_delta_fair(se->slice, se);
>  }

Makes sense. Deadline would be rapidly incremented in the scenario of
having other tasks not eligible and the current task calls yield
repeatedly for a very short run time.

Reviewed-by: Madadi Vineeth Reddy <vineethr@linux.ibm.com>

Thanks,
Madadi Vineeth Reddy

> 
>  static bool yield_to_task_fair(struct rq *rq, struct task_struct *p)
> --
> 2.47.1
> 
> 
> 
> 
> Amazon Development Centre (South Africa) (Proprietary) Limited
> 29 Gogosoa Street, Observatory, Cape Town, Western Cape, 7925, South Africa
> Registration Number: 2004 / 034463 / 07
> 

Re: [PATCH] sched/fair: Only increment deadline once on yield

[Alexander Graf]

On 01.04.25 14:36, Fernand Sieber wrote:
> If a task yields, the scheduler may decide to pick it again. The task in
> turn may decide to yield immediately or shortly after, leading to a tight
> loop of yields.
>
> If there's another runnable task as this point, the deadline will be
> increased by the slice at each loop. This can cause the deadline to runaway
> pretty quickly, and subsequent elevated run delays later on as the task
> doesn't get picked again. The reason the scheduler can pick the same task
> again and again despite its deadline increasing is because it may be the
> only eligible task at that point.
>
> Fix this by updating the deadline only to one slice ahead.
>
> Note, we might want to consider iterating on the implementation of yield as
> follow up:
> * the yielding task could be forfeiting its remaining slice by
>    incrementing its vruntime correspondingly
> * in case of yield_to the yielding task could be donating its remaining
>    slice to the target task
>
> Signed-off-by: Fernand Sieber <sieberf@amazon.com>


IMHO it's worth noting that this is not a theoretical issue. We have 
seen this in real life: A KVM virtual machine's vCPU which runs into a 
busy guest spin lock calls kvm_vcpu_yield_to() which eventually ends up 
in the yield_task_fair() function. We have seen such spin locks due to 
guest contention rather than host overcommit, which means we go into a 
loop of vCPU execution and spin loop exit, which results in an 
undesirable increase in the vCPU thread's deadline.

Given this impacts real workloads and is a bug present since the 
introduction of EEVDF, I would say it warrants a

Fixes: 147f3efaa24182 ("sched/fair: Implement an EEVDF-like scheduling 
policy")

tag.


Alex

[PATCH] Re: [PATCH] sched/fair: Only increment deadline once on yield

[Wang Tao]

>> On 01/04/25 18:06, Fernand Sieber wrote:
>> If a task yields, the scheduler may decide to pick it again. The task in
>> turn may decide to yield immediately or shortly after, leading to a tight
>> loop of yields.
>>
>> If there's another runnable task as this point, the deadline will be
>> increased by the slice at each loop. This can cause the deadline to runaway
>> pretty quickly, and subsequent elevated run delays later on as the task
>> doesn't get picked again. The reason the scheduler can pick the same task
>> again and again despite its deadline increasing is because it may be the
>> only eligible task at that point.
>>
>> Fix this by updating the deadline only to one slice ahead.
>>
>> Note, we might want to consider iterating on the implementation of yield as
>> follow up:
>> * the yielding task could be forfeiting its remaining slice by
>>    incrementing its vruntime correspondingly
>> * in case of yield_to the yielding task could be donating its remaining
>>    slice to the target task
>>
>> Signed-off-by: Fernand Sieber <sieberf@amazon.com>


>IMHO it's worth noting that this is not a theoretical issue. We have 
>seen this in real life: A KVM virtual machine's vCPU which runs into a 
>busy guest spin lock calls kvm_vcpu_yield_to() which eventually ends up 
>in the yield_task_fair() function. We have seen such spin locks due to 
>guest contention rather than host overcommit, which means we go into a 
>loop of vCPU execution and spin loop exit, which results in an 
>undesirable increase in the vCPU thread's deadline.

>Given this impacts real workloads and is a bug present since the 
>introduction of EEVDF, I would say it warrants a

>Fixes: 147f3efaa24182 ("sched/fair: Implement an EEVDF-like scheduling 
>policy")

>tag.


>Alex

Actually, as Alex described, we encountered the same issue in this 
testing scenario: starting qemu, binding cores to the cpuset group, 
setting cpuset.cpus=1-3 for stress testing in qemu, 
running taskset -c 1-3 ./stress-ng -c 20, and then encountering an error where qemu freezes, 
reporting a soft lockup issue in qemu. After applying this patch, the problem was resolved.
Do we have plans to merge this patch into the mainline?

Re: [PATCH] sched/fair: Only increment deadline once on yield

[Wang Tao]

Picking up this dead thread again.

Has this patch been applied to the mainline or other branch? 

Thanks.

Re: [PATCH] sched/fair: Only increment deadline once on yield

[Fernand Sieber]

Hi Tao,

The patch hasn't been merged yet.
I have resent this patch with fixes tag and additional maintainers in Cc.
Please review on the following thread:

Link: https://lore.kernel.org/lkml/20250911095113.203439-1-sieberf@amazon.com

Thanks,
Fernand



Amazon Development Centre (South Africa) (Proprietary) Limited
29 Gogosoa Street, Observatory, Cape Town, Western Cape, 7925, South Africa
Registration Number: 2004 / 034463 / 07

Re: [PATCH 3/3] sched: Update ->next_balance correctly during newidle balance

[Joel Fernandes]

Getting to this pretty late, sorry, see below.

On Tue, Nov 14, 2023 at 04:43:12PM +0100, Vincent Guittot wrote:
> Le jeudi 09 nov. 2023 à 10:02:54 (+0000), Joel Fernandes a écrit :
> > Hi Vincent,
> > 
> > Sorry for late reply, I was in Tokyo all these days and was waiting to get to
> > writing a proper reply. See my replies below:
> > 
> > On Thu, Oct 26, 2023 at 04:23:35PM +0200, Vincent Guittot wrote:
> > > On Sun, 22 Oct 2023 at 02:28, Joel Fernandes <joel@joelfernandes.org> wrote:
> > > >
> > > > On Fri, Oct 20, 2023 at 03:40:14PM +0200, Vincent Guittot wrote:
> > > > > On Fri, 20 Oct 2023 at 03:40, Joel Fernandes (Google)
> > > > > <joel@joelfernandes.org> wrote:
> > > > > >
> > > > > > From: "Vineeth Pillai (Google)" <vineeth@bitbyteword.org>
> > > > > >
> > > > > > When newidle balancing triggers, we see that it constantly clobbers
> > > > > > rq->next_balance even when there is no newidle balance happening due to
> > > > > > the cost estimates.  Due to this, we see that periodic load balance
> > > > > > (rebalance_domains) may trigger way more often when the CPU is going in
> > > > > > and out of idle at a high rate but is no really idle. Repeatedly
> > > > > > triggering load balance there is a bad idea as it is a heavy operation.
> > > > > > It also causes increases in softirq.
> > > > >
> > > > > we have 2 balance intervals:
> > > > > - one when idle based on the sd->balance_interval = sd_weight
> > > > > - one when busy which increases the period by multiplying it with
> > > > > busy_factor = 16
> > > >
> > > > On my production system I see load balance triggering every 4 jiffies! In a
> > > 
> > > Which kind of system do you have? sd->balance_interval is in ms
> > 
> > Yes, sorry I meant it triggers every jiffies which is extreme sometimes. It
> > is an ADL SoC (12th gen Intel, 4 P cores 8 E cores) get_sd_balance_interval()
> > returns 4 jiffies there. On my Qemu system, I see 8 jiffies.
> 
> Do you have details about the sched_domain  hierarchy ?
> That could be part of your problem (see below)

The hierarchy is pretty simple:

$ cat /sys/kernel/debug/sched/domains/cpu*/domain0/name
MC
MC
MC
MC

I boot qemu like this by passing "-smp cpus=4,threads=1,sockets=1"

> > 
> > [...]
> > > > > > Another issue is ->last_balance is not updated after newidle balance
> > > > > > causing mistakes in the ->next_balance calculations.
> > > > >
> > > > > newly idle load balance is not equal to idle load balance. It's a
> > > > > light load balance trying to pull one  task and you can't really
> > > > > consider it to the normal load balance
> > > >
> > > > True. However the point is that it is coupled with the other load balance
> > > > mechanism and the two are not independent. As you can see below, modifying
> > > > rq->next_balance in newidle also causes the periodic balance to happen more
> > > > aggressively as well if there is a high transition from busy to idle and
> > > > viceversa.
> > > 
> > > As mentioned, rq->next_balance is updated whenever cpu enters idle
> > > (i.e. in newidle_balance() but it's not related with doing a newly
> > > idle load balance.
> > 
> > Yes, I understand that. But my point was that the update of rq->next_balance
> > from the newidle path is itself buggy and interferes with the load balance
> > happening from the tick (trigger_load_balance -> run_rebalance_domains).
> 
> Newidle path is not buggy. It only uses sd->last_balance + interval to
> estimate the next balance  which is the correct thing to do. Your problem
> comes from the update of sd->last_balance which never happens and remains
> in the past whereas you call run_rebalance_domains() which should
> run load_balance for all domains with a sd->last_balance + interval in the
> past.
> Your problem most probably comes from the should_we_balance which always or
> "almost always" returns false in your use case for some sched_domain and
> prevents to updat sd->last_balance. Could you try the patch below ?
> It should fix your problem of trying to rebalance every tick whereas
> rebalance_domain is called.
> At least this should show if it's your problem but I'm not sure it's the right
> things to do all the time ...

I tried your diff below. It did not make a difference to the problem. Only
this patch series made a ~10-20x softirq reduction.

> 
> ---
>  kernel/sched/fair.c | 18 ++++++------------
>  1 file changed, 6 insertions(+), 12 deletions(-)
> 
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 3745ca289240..9ea1f42e5362 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -11568,17 +11568,6 @@ static void rebalance_domains(struct rq *rq, enum cpu_idle_type idle)
>  		need_decay = update_newidle_cost(sd, 0);
>  		max_cost += sd->max_newidle_lb_cost;
> 
> -		/*
> -		 * Stop the load balance at this level. There is another
> -		 * CPU in our sched group which is doing load balancing more
> -		 * actively.
> -		 */
> -		if (!continue_balancing) {
> -			if (need_decay)
> -				continue;
> -			break;
> -		}
> -
>  		interval = get_sd_balance_interval(sd, busy);
> 
>  		need_serialize = sd->flags & SD_SERIALIZE;
> @@ -11588,7 +11577,12 @@ static void rebalance_domains(struct rq *rq, enum cpu_idle_type idle)
>  		}
> 
>  		if (time_after_eq(jiffies, sd->last_balance + interval)) {
> -			if (load_balance(cpu, rq, sd, idle, &continue_balancing)) {
> +			/*
> +			 * Stop the load balance at this level. There is another
> +			 * CPU in our sched group which is doing load balancing more
> +			 * actively.
> +			 */
> +			if (continue_balancing && load_balance(cpu, rq, sd, idle, &continue_balancing)) {

This diff did not solve the problem. Let me go see what other paths are not
updating sd->last_balance in the run_rebalance_domains()..

thanks,

 - Joel

Re: [PATCH] sched/fair: Only increment deadline once on yield

[Wang Tao]

Picking up this dead thread again.

Recently, we have also encountered issues with sending a large number of IPI interrupts 
and would like to try this patch to see if it can resolve the problem. 
Are there any updates to this series of patches?

Thanks.