Message-ID: <20240710145320.GA27299@noisy.programming.kicks-ass.net>
Date: Wed, 10 Jul 2024 16:53:20 +0200
From: Peter Zijlstra <peterz@...radead.org>
To: K Prateek Nayak <kprateek.nayak@....com>
Cc: Ingo Molnar <mingo@...hat.com>, Juri Lelli <juri.lelli@...hat.com>,
	Vincent Guittot <vincent.guittot@...aro.org>,
	linux-kernel@...r.kernel.org,
	Dietmar Eggemann <dietmar.eggemann@....com>,
	Steven Rostedt <rostedt@...dmis.org>,
	Ben Segall <bsegall@...gle.com>, Mel Gorman <mgorman@...e.de>,
	Daniel Bristot de Oliveira <bristot@...hat.com>,
	Valentin Schneider <vschneid@...hat.com>,
	"Paul E. McKenney" <paulmck@...nel.org>,
	Imran Khan <imran.f.khan@...cle.com>,
	Leonardo Bras <leobras@...hat.com>, Guo Ren <guoren@...nel.org>,
	Rik van Riel <riel@...riel.com>, Tejun Heo <tj@...nel.org>,
	Cruz Zhao <CruzZhao@...ux.alibaba.com>,
	Lai Jiangshan <jiangshanlai@...il.com>,
	Joel Fernandes <joel@...lfernandes.org>,
	Zqiang <qiang.zhang1211@...il.com>,
	Julia Lawall <julia.lawall@...ia.fr>,
	"Gautham R. Shenoy" <gautham.shenoy@....com>
Subject: Re: [PATCH 1/3] sched/core: Remove the unnecessary need_resched()
 check in nohz_csd_func()

On Wed, Jul 10, 2024 at 09:02:08AM +0000, K Prateek Nayak wrote:
> The need_resched() check currently in nohz_csd_func() can be tracked
> to have been added in scheduler_ipi() back in 2011 via commit
> ca38062e57e9 ("sched: Use resched IPI to kick off the nohz idle balance")
> 
> Since then, it has travelled quite a bit but it seems like an idle_cpu()
> check currently is sufficient to detect the need to bail out from an
> idle load balancing. To justify this removal, consider all the following
> case where an idle load balancing could race with a task wakeup:
> 
> o Since commit f3dd3f674555b ("sched: Remove the limitation of WF_ON_CPU
>   on wakelist if wakee cpu is idle") a target perceived to be idle
>   (target_rq->nr_running == 0) will return true for
>   ttwu_queue_cond(target) which will offload the task wakeup to the idle
>   target via an IPI.
> 
>   In all such cases target_rq->ttwu_pending will be set to 1 before
>   queuing the wake function.
> 
>   If an idle load balance races here, following scenarios are possible:
> 
>   - The CPU is not in TIF_POLLING_NRFLAG mode in which case an actual
>     IPI is sent to the CPU to wake it out of idle. If the
>     nohz_csd_func() queues before sched_ttwu_pending(), the idle load
>     balance will bail out since idle_cpu(target) returns 0 since
>     target_rq->ttwu_pending is 1. If the nohz_csd_func() is queued after
>     sched_ttwu_pending() it should see rq->nr_running to be non-zero and
>     bail out of idle load balancing.
> 
>   - The CPU is in TIF_POLLING_NRFLAG mode and instead of an actual IPI,
>     the sender will simply set TIF_NEED_RESCHED for the target to put it
>     out of idle and flush_smp_call_function_queue() in do_idle() will
>     execute the call function. Depending on the ordering of the queuing
>     of nohz_csd_func() and sched_ttwu_pending(), the idle_cpu() check in
>     nohz_csd_func() should either see target_rq->ttwu_pending = 1 or
>     target_rq->nr_running to be non-zero if there is a genuine task
>     wakeup racing with the idle load balance kick.

For completion sake, we should also consider the !TTWU_QUEUE case, this
configuration is default for PREEMPT_RT, where the wake_list is a source
of non-determinism.

In quick reading I think that case should be fine, since we directly
enqueue remotely and ->nr_running adjusts accordingly, but it is late in
the day and I'm easily mistaken.

> o The waker CPU perceives the target CPU to be busy
>   (targer_rq->nr_running != 0) but the CPU is in fact going idle and due
>   to a series of unfortunate events, the system reaches a case where the
>   waker CPU decides to perform the wakeup by itself in ttwu_queue() on
>   the target CPU but target is concurrently selected for idle load
>   balance (Can this happen? I'm not sure, but we'll consider its
>   possibility to estimate the worst case scenario).
> 
>   ttwu_do_activate() calls enqueue_task() which would increment
>   "rq->nr_running" post which it calls wakeup_preempt() which is
>   responsible for setting TIF_NEED_RESCHED (via a resched IPI or by
>   setting TIF_NEED_RESCHED on a TIF_POLLING_NRFLAG idle CPU) The key
>   thing to note in this case is that rq->nr_running is already non-zero
>   in case of a wakeup before TIF_NEED_RESCHED is set which would
>   lead to idle_cpu() check returning false.
> 
> In all cases, it seems that need_resched() check is unnecessary when
> checking for idle_cpu() first since an impending wakeup racing with idle
> load balancer will either set the "rq->ttwu_pending" or indicate a newly
> woken task via "rq->nr_running".

Right.

> Chasing the reason why this check might have existed in the first place,
> I came across  Peter's suggestion on the fist iteration of Suresh's
> patch from 2011 [1] where the condition to raise the SCHED_SOFTIRQ was:
> 
> 	sched_ttwu_do_pending(list);
> 
> 	if (unlikely((rq->idle == current) &&
> 	    rq->nohz_balance_kick &&
> 	    !need_resched()))
> 		raise_softirq_irqoff(SCHED_SOFTIRQ);
> 
> However, since this was preceded by sched_ttwu_do_pending() which is
> equivalent of sched_ttwu_pending() in the current upstream kernel, the
> need_resched() check was necessary to catch a newly queued task. Peter
> suggested modifying it to:
> 
> 	if (idle_cpu() && rq->nohz_balance_kick && !need_resched())
> 		raise_softirq_irqoff(SCHED_SOFTIRQ);
> 
> where idle_cpu() seems to have replaced "rq->idle == current" check.
> However, even back then, the idle_cpu() check would have been sufficient
> to have caught the enqueue of a new task and since commit b2a02fc43a1f
> ("smp: Optimize send_call_function_single_ipi()") overloads the
> interpretation of TIF_NEED_RESCHED for TIF_POLLING_NRFLAG idling, remove
> the need_resched() check in nohz_csd_func() to raise SCHED_SOFTIRQ based
> on Peter's suggestion.

... sooo many years ago :-)

> Link: https://lore.kernel.org/all/1317670590.20367.38.camel@twins/ [1]
> Link: https://lore.kernel.org/lkml/20240615014521.GR8774@noisy.programming.kicks-ass.net/
> Fixes: b2a02fc43a1f ("smp: Optimize send_call_function_single_ipi()")
> Suggested-by: Peter Zijlstra <peterz@...radead.org>
> Signed-off-by: K Prateek Nayak <kprateek.nayak@....com>
> ---
>  kernel/sched/core.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> index 0935f9d4bb7b..1e0c77eac65a 100644
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -1205,7 +1205,7 @@ static void nohz_csd_func(void *info)
>  	WARN_ON(!(flags & NOHZ_KICK_MASK));
>  
>  	rq->idle_balance = idle_cpu(cpu);
> -	if (rq->idle_balance && !need_resched()) {
> +	if (rq->idle_balance) {
>  		rq->nohz_idle_balance = flags;
>  		raise_softirq_irqoff(SCHED_SOFTIRQ);
>  	}
> -- 
> 2.34.1
> 

Powered by blists - more mailing lists