diff mbox

[v2,00/14] Introducing TIF_NOTIFY_IPI flag

Message ID 20240613181613.4329-1-kprateek.nayak@amd.com
State New
Headers show

Commit Message

K Prateek Nayak June 13, 2024, 6:15 p.m. UTC
Hello everyone,

Before jumping into the issue, let me clarify the Cc list. Everyone have
been cc'ed on Patch 0 through Patch 3. Respective arch maintainers,
reviewers, and committers returned by scripts/get_maintainer.pl have
been cc'ed on the respective arch side changes. Scheduler and CPU Idle
maintainers and reviewers have been included for the entire series. If I
have missed anyone, please do add them. If you would like to be dropped
from the cc list, wholly or partially, for the future iterations, please
do let me know.

As long as the first three patches are applied in-order, the arch
specific enablement can be applied independently and out-of-order since
the TIF_NOTIFY_IPI flag is not used until Patch 3 and Patch 2 preps the
complete tree to handle a break out of TIF_POLLING_NRFLAG state with the
setting of either TIF_NOTIFY_IPI or TIF_NEED_RESCHED.

Quick changelog and addressing concerns from v1
===============================================

v1: https://lore.kernel.org/lkml/20240220171457.703-1-kprateek.nayak@amd.com/

v1..v2:

o Rebased the series on latest tip:sched/core at commit c793a62823d1
  ("sched/core: Drop spinlocks on contention iff kernel is preemptible")
  Fixed a conflict with commit edc8fc01f608 ("x86: Fix
  CPUIDLE_FLAG_IRQ_ENABLE leaking timer reprogram") that touched
  mwait_idle_with_hints() in arch/x86/include/asm/mwait.h

o Dropping the ARM results since I never got my hands on the ARM64
  system I used in my last testing. If I do manage to get my hands on it
  again, I'll rerun the experiments and share the results on the thread.
  To test the case where TIF_NOTIFY_IPI is not enabled for a particular
  architecture, I applied the series only until Patch 3 and tested the
  same on my x86 machine with a WARN_ON_ONCE() in do_idle() to check if
  tif_notify_ipi() ever return true and then repeated the same with
  Patch 4 applied.

o Updated benchmark results based on the latest base.

o Collected the Ack from Guo Ren for CSKY enablement.

o Dropped the RFC tag.

o Unfortunately, the series does not solve the issue highlighted by
  Julia Lawall w.r.t. NUMA Balancing in [0] based on her testing of v1.
  However, she did highlight a possible regression last time around
  where compiling a single file took much longer with the series but I
  could not reproduce it on my end. For sanity, I did rerun the same
  experiment this time around and I could not see any difference.
  Following are the numbers for

  $ make clean
  $ time make kernel/sched/core.o

  ---> tip:sched/core
  
    -j1
    
    real    0m32.734s
    user    0m25.158s
    sys     0m6.750s
    
    -j256
    
    real    0m7.181s
    user    0m27.509s
    sys     0m7.876s
    
  --> tip:sched/core + TIF_NOTIFY_IPI
  
    -j1
    
    real    0m32.408s
    user    0m24.826s
    sys     0m6.767s
    
    -j256
    
    real    0m7.187s
    user    0m27.556s
    sys     0m7.602s

  [0] https://lore.kernel.org/lkml/alpine.DEB.2.22.394.2310032059060.3220@hadrien/

Individual patches have their own changelog to help with review.

With those details out of the way ...

Problem statement
=================

When measuring IPI throughput using a modified version of Anton
Blanchard's ipistorm benchmark [1], configured to measure time taken to
perform a fixed number of smp_call_function_single() (with wait set to
1), an increase in benchmark time was observed between v5.7 and the
upstream release v6.7-rc6 (this was the latest upstream kernel at the
time of encountering the issue). The issue persists on v6.10-rc1 as
well.

Bisection pointed to commit b2a02fc43a1f ("smp: Optimize
send_call_function_single_ipi()") as the reason behind this increase in
runtime.


Experiments
===========

Since the commit cannot be cleanly reverted on top of the current
tip:sched/core, the effects of the optimizations were reverted by:

1. Removing the check for call_function_single_prep_ipi() in
   send_call_function_single_ipi(). With this change
   send_call_function_single_ipi() always calls
   arch_send_call_function_single_ipi()

2. Removing the call to flush_smp_call_function_queue() in do_idle()
   since every smp_call_function, with (1.), would unconditionally send
   an IPI to an idle CPU in TIF_POLLING mode.

Following is the diff of the above described changes which will be
henceforth referred to as the "revert":

--

With the revert, the time taken to complete a fixed set of IPIs using
ipistorm improves significantly. Following are the numbers from a dual
socket 3rd Generation EPYC system (2 x 64C/128T) (boost on, C2 disabled)
running ipistorm between CPU8 and CPU16:

cmdline: insmod ipistorm.ko numipi=100000 single=1 offset=8 cpulist=8 wait=1

(tip:sched/core was at commit c793a62823d1 ("sched/core: Drop spinlocks
 on contention iff kernel is preemptible") for all the test data
 presented below)

  ==================================================================
  Test          : ipistorm (modified)
  Units         : Normalized runtime
  Interpretation: Lower is better
  Statistic     : AMean
  ==================================================================
  kernel:			time [pct imp]
  tip:sched/core		1.00 [00.00]
  tip:sched/core + revert	0.41 [60.00]

Although the revert improves ipistorm performance, it also regresses
tbench and netperf, supporting the validity of the optimization.
Following are the tbench numbers from the same machine comparing vanilla
tip:sched/core and the revert applied on top:

  ==================================================================
  Test          : tbench
  Units         : Normalized throughput
  Interpretation: Higher is better
  Statistic     : AMean
  ==================================================================
  Clients:     tip (CV)          revert (CV) [pct imp]
     1        1.00 (0.60)         0.90 (0.08) [-10%]
     2        1.00 (0.27)         0.90 (0.76) [-10%]
     4        1.00 (0.42)         0.90 (0.52) [-10%]
     8        1.00 (0.78)         0.91 (0.54) [ -9%]
    16        1.00 (1.70)         0.92 (0.39) [ -8%]
    32        1.00 (1.73)         0.91 (1.39) [ -9%]
    64        1.00 (1.09)         0.92 (1.60) [ -8%]
   128        1.00 (1.45)         0.95 (0.52) [ -5%]
   256        1.00 (0.96)         1.01 (0.28) [  1%]
   512        1.00 (0.32)         1.01 (0.20) [  1%]
  1024        1.00 (0.06)         1.01 (0.03) [  1%]

Since a simple revert is not a viable solution, we delved deeper into
the changes in the execution path with call_function_single_prep_ipi()
check.


Effects of call_function_single_prep_ipi()
==========================================

To pull a TIF_POLLING thread out of idle to process an IPI, the sender
sets the TIF_NEED_RESCHED bit in the idle task's thread info in
call_function_single_prep_ipi() and avoids sending an actual IPI to the
target. As a result, the scheduler expects a task to be enqueued when
exiting the idle path. This is not the case with non-polling idle states
where the idle CPU exits the non-polling idle state to process the
interrupt, and since need_resched() returns false, soon goes back to
idle again.

When TIF_NEED_RESCHED flag is set, do_idle() will call schedule_idle(),
a large part of which runs with local IRQ disabled. In case of ipistorm,
when measuring IPI throughput, this large IRQ disabled section delays
processing of IPIs. Further auditing revealed that in absence of any
runnable tasks, pick_next_task_fair(), which is called from the
pick_next_task() fast path, will always call newidle_balance() in this
scenario, further increasing the time spent in the IRQ disabled section.

Following is the crude visualization of the problem with relevant
functions expanded:
--
CPU0							CPU1
====							====
							do_idle() {
								__current_set_polling();
								...
								monitor(addr);
								if (!need_resched())
									mwait() {
									/* Waiting */
smp_call_function_single(CPU1, func, wait = 1) {				...
	...									...
	set_nr_if_polling(CPU1) {						...
		/* Realizes CPU1 is polling */					...
		try_cmpxchg(addr,						...
			    &val,						...
			    val | _TIF_NEED_RESCHED);				...
	} /* Does not send an IPI */						...
	...								} /* mwait exit due to write at addr */
	csd_lock_wait() {					} 
	/* Waiting */						preempt_set_need_resched();
		...						__current_clr_polling();
		...						flush_smp_call_function_queue() {
		...							func();
	} /* End of wait */					}
}								schedule_idle() {
									...
									local_irq_disable();
smp_call_function_single(CPU1, func, wait = 1) {			...
	...								...
	arch_send_call_function_single_ipi(CPU1);			...
						\			...
						 \			newidle_balance() {
						  \				...
					      /* Delay */			...
						    \			}
					     	     \			...
						      \-------------->	local_irq_enable();
									/* Processes the IPI */
--


Skipping newidle_balance()
==========================

In an earlier attempt to solve the challenge of the long IRQ disabled
section, newidle_balance() was skipped when a CPU waking up from idle
was found to have no runnable tasks, and was transitioning back to
idle [2]. Tim [3] and David [4] had pointed out that newidle_balance()
may be viable for CPUs that are idling with tick enabled, where the
newidle_balance() has the opportunity to pull tasks onto the idle CPU.

Vincent [5] pointed out a case where the idle load kick will fail to
run on an idle CPU since the IPI handler launching the ILB will check
for need_resched(). In such cases, the idle CPU relies on
newidle_balance() to pull tasks towards itself.

Using an alternate flag instead of NEED_RESCHED to indicate a pending
IPI was suggested as the correct approach to solve this problem on the
same thread.


Proposed solution: TIF_NOTIFY_IPI
=================================

Instead of reusing TIF_NEED_RESCHED bit to pull an TIF_POLLING CPU out
of idle, TIF_NOTIFY_IPI is a newly introduced flag that
call_function_single_prep_ipi() sets on a target TIF_POLLING CPU to
indicate a pending IPI, which the idle CPU promises to process soon.

On architectures that do not support the TIF_NOTIFY_IPI flag (this
series only adds support for x86 and ARM processors for now),
call_function_single_prep_ipi() will fallback to setting
TIF_NEED_RESCHED bit to pull the TIF_POLLING CPU out of idle.

Since the pending IPI handlers are processed before the call to
schedule_idle() in do_idle(), schedule_idle() will only be called if the
IPI handler have woken / migrated a new task on the idle CPU and has set
TIF_NEED_RESCHED bit to indicate the same. This avoids running into the
long IRQ disabled section in schedule_idle() unnecessarily, and any
need_resched() check within a call function will accurately notify if a
task is waiting for CPU time on the CPU handling the IPI.

Following is the crude visualization of how the situation changes with
the newly introduced TIF_NOTIFY_IPI flag:
--
CPU0							CPU1
====							====
							do_idle() {
								__current_set_polling();
								...
								monitor(addr);
								if (!need_resched_or_ipi())
									mwait() {
									/* Waiting */
smp_call_function_single(CPU1, func, wait = 1) {				...
	...									...
	set_nr_if_polling(CPU1) {						...
		/* Realizes CPU1 is polling */					...
		try_cmpxchg(addr,						...
			    &val,						...
			    val | _TIF_NOTIFY_IPI);				...
	} /* Does not send an IPI */						...
	...								} /* mwait exit due to write at addr */
	csd_lock_wait() {					... 
	/* Waiting */						preempt_fold_need_resched(); /* fold if NEED_RESCHED */
		...						__current_clr_polling();
		...						flush_smp_call_function_queue() {
		...							func(); /* Will set NEED_RESCHED if sched_ttwu_pending() */
	} /* End of wait */					}
}								if (need_resched()) {
									schedule_idle();
smp_call_function_single(CPU1, func, wait = 1) {		}
	...							... /* IRQs remain enabled */
	arch_send_call_function_single_ipi(CPU1); ----------->  /* Processes the IPI */
--

Results
=======

With the TIF_NOTIFY_IPI, the time taken to complete a fixed set of IPIs
using ipistorm improves drastically and is closer the numbers same with
the revert. Following are the numbers from the same dual socket 3rd
Generation EPYC system (2 x 64C/128T) (boost on, C2 disabled) running
ipistorm between CPU8 and CPU16:

cmdline: insmod ipistorm.ko numipi=100000 single=1 offset=8 cpulist=8 wait=1

  ==================================================================
  Test          : ipistorm (modified)
  Units         : Normalized runtime
  Interpretation: Lower is better
  Statistic     : AMean
  ==================================================================
  kernel:				time [pct imp]
  tip:sched/core			1.00 [baseline]
  tip:sched/core + revert		0.40 [60.26]
  tip:sched/core + TIF_NOTIFY_IPI	0.46 [54.88]

netperf and tbench results with the patch match the results on tip on
the dual socket 3rd Generation AMD system (2 x 64C/128T). Additionally,
hackbench, stream, and schbench too were tested, with results from the
patched kernel matching that of the tip.


Additional benefits
===================

In nohz_csd_func(), the need_resched() check returns true when an idle
CPU in TIF_POLLING mode is woken up to do an idle load balance which
leads to the idle load balance bailing out early today since
send_call_function_single_ipi() ends up setting the TIF_NEED_RESCHED
flag to put the CPU out of idle and the flag is not cleared until
__schedule() is called much later in the call path.

With TIF_NOTIFY_IPI, this is no longer the case since TIF_NEED_RESCHED
is only set if there is a genuine need to call schedule() and not used
in an overloaded manner to notify a pending IPI.

Links
=====

[1] https://github.com/antonblanchard/ipistorm
[2] https://lore.kernel.org/lkml/20240119084548.2788-1-kprateek.nayak@amd.com/
[3] https://lore.kernel.org/lkml/b4f5ac150685456cf45a342e3bb1f28cdd557a53.camel@linux.intel.com/
[4] https://lore.kernel.org/lkml/20240123211756.GA221793@maniforge/
[5] https://lore.kernel.org/lkml/CAKfTPtC446Lo9CATPp7PExdkLhHQFoBuY-JMGC7agOHY4hs-Pw@mail.gmail.com/

This series is based on tip:sched/core at commit c793a62823d1
("sched/core: Drop spinlocks on contention iff kernel is preemptible")
--
Gautham R. Shenoy (4):
  thread_info: Add helpers to test and clear TIF_NOTIFY_IPI
  sched: Define a need_resched_or_ipi() helper and use it treewide
  sched/core: Use TIF_NOTIFY_IPI to notify an idle CPU in TIF_POLLING
    mode of pending IPI
  x86/thread_info: Introduce TIF_NOTIFY_IPI flag

K Prateek Nayak (10):
  arm/thread_info: Introduce TIF_NOTIFY_IPI flag
  alpha/thread_info: Introduce TIF_NOTIFY_IPI flag
  openrisc/thread_info: Introduce TIF_NOTIFY_IPI flag
  powerpc/thread_info: Introduce TIF_NOTIFY_IPI flag
  sh/thread_info: Introduce TIF_NOTIFY_IPI flag
  sparc/thread_info: Introduce TIF_NOTIFY_IPI flag
  csky/thread_info: Introduce TIF_NOTIFY_IPI flag
  parisc/thread_info: Introduce TIF_NOTIFY_IPI flag
  nios2/thread_info: Introduce TIF_NOTIFY_IPI flag
  microblaze/thread_info: Introduce TIF_NOTIFY_IPI flag
--
Cc: Richard Henderson <richard.henderson@linaro.org>
Cc: Ivan Kokshaysky <ink@jurassic.park.msu.ru>
Cc: Matt Turner <mattst88@gmail.com>
Cc: Russell King <linux@armlinux.org.uk>
Cc: Guo Ren <guoren@kernel.org>
Cc: Michal Simek <monstr@monstr.eu>
Cc: Dinh Nguyen <dinguyen@kernel.org>
Cc: Jonas Bonn <jonas@southpole.se>
Cc: Stefan Kristiansson <stefan.kristiansson@saunalahti.fi>
Cc: Stafford Horne <shorne@gmail.com>
Cc: "James E.J. Bottomley" <James.Bottomley@HansenPartnership.com>
Cc: Helge Deller <deller@gmx.de>
Cc: Michael Ellerman <mpe@ellerman.id.au>
Cc: Nicholas Piggin <npiggin@gmail.com>
Cc: Christophe Leroy <christophe.leroy@csgroup.eu>
Cc: "Naveen N. Rao" <naveen.n.rao@linux.ibm.com>
Cc: Yoshinori Sato <ysato@users.sourceforge.jp>
Cc: Rich Felker <dalias@libc.org>
Cc: John Paul Adrian Glaubitz <glaubitz@physik.fu-berlin.de>
Cc: "David S. Miller" <davem@davemloft.net>
Cc: Andreas Larsson <andreas@gaisler.com>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Ingo Molnar <mingo@redhat.com>
Cc: Borislav Petkov <bp@alien8.de>
Cc: Dave Hansen <dave.hansen@linux.intel.com>
Cc: "H. Peter Anvin" <hpa@zytor.com>
Cc: "Rafael J. Wysocki" <rafael@kernel.org>
Cc: Daniel Lezcano <daniel.lezcano@linaro.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Juri Lelli <juri.lelli@redhat.com>
Cc: Vincent Guittot <vincent.guittot@linaro.org>
Cc: Dietmar Eggemann <dietmar.eggemann@arm.com>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Ben Segall <bsegall@google.com>
Cc: Mel Gorman <mgorman@suse.de>
Cc: Daniel Bristot de Oliveira <bristot@redhat.com>
Cc: Valentin Schneider <vschneid@redhat.com>
Cc: Andrew Donnellan <ajd@linux.ibm.com>
Cc: Benjamin Gray <bgray@linux.ibm.com>
Cc: Frederic Weisbecker <frederic@kernel.org>
Cc: Xin Li <xin3.li@intel.com>
Cc: Kees Cook <keescook@chromium.org>
Cc: Rick Edgecombe <rick.p.edgecombe@intel.com>
Cc: Tony Battersby <tonyb@cybernetics.com>
Cc: Bjorn Helgaas <bhelgaas@google.com>
Cc: Brian Gerst <brgerst@gmail.com>
Cc: Leonardo Bras <leobras@redhat.com>
Cc: Imran Khan <imran.f.khan@oracle.com>
Cc: "Paul E. McKenney" <paulmck@kernel.org>
Cc: Rik van Riel <riel@surriel.com>
Cc: Tim Chen <tim.c.chen@linux.intel.com>
Cc: David Vernet <void@manifault.com>
Cc: Julia Lawall <julia.lawall@inria.fr>
Cc: linux-alpha@vger.kernel.org
Cc: linux-kernel@vger.kernel.org
Cc: linux-arm-kernel@lists.infradead.org
Cc: linux-csky@vger.kernel.org
Cc: linux-openrisc@vger.kernel.org
Cc: linux-parisc@vger.kernel.org
Cc: linuxppc-dev@lists.ozlabs.org
Cc: linux-sh@vger.kernel.org
Cc: sparclinux@vger.kernel.org
Cc: linux-pm@vger.kernel.org
Cc: x86@kernel.org
--
 arch/alpha/include/asm/thread_info.h      |  2 ++
 arch/arm/include/asm/thread_info.h        |  3 ++
 arch/csky/include/asm/thread_info.h       |  2 ++
 arch/microblaze/include/asm/thread_info.h |  2 ++
 arch/nios2/include/asm/thread_info.h      |  2 ++
 arch/openrisc/include/asm/thread_info.h   |  2 ++
 arch/parisc/include/asm/thread_info.h     |  2 ++
 arch/powerpc/include/asm/thread_info.h    |  2 ++
 arch/sh/include/asm/thread_info.h         |  2 ++
 arch/sparc/include/asm/thread_info_32.h   |  2 ++
 arch/sparc/include/asm/thread_info_64.h   |  2 ++
 arch/x86/include/asm/mwait.h              |  2 +-
 arch/x86/include/asm/thread_info.h        |  2 ++
 arch/x86/kernel/process.c                 |  2 +-
 drivers/cpuidle/cpuidle-powernv.c         |  2 +-
 drivers/cpuidle/cpuidle-pseries.c         |  2 +-
 drivers/cpuidle/poll_state.c              |  2 +-
 include/linux/sched.h                     |  5 +++
 include/linux/sched/idle.h                | 12 +++----
 include/linux/thread_info.h               | 43 +++++++++++++++++++++++
 kernel/sched/core.c                       | 41 ++++++++++++++++-----
 kernel/sched/idle.c                       | 23 ++++++++----
 22 files changed, 133 insertions(+), 26 deletions(-)

Comments

Peter Zijlstra June 14, 2024, 9:28 a.m. UTC | #1
On Thu, Jun 13, 2024 at 06:15:59PM +0000, K Prateek Nayak wrote:
> Effects of call_function_single_prep_ipi()
> ==========================================
> 
> To pull a TIF_POLLING thread out of idle to process an IPI, the sender
> sets the TIF_NEED_RESCHED bit in the idle task's thread info in
> call_function_single_prep_ipi() and avoids sending an actual IPI to the
> target. As a result, the scheduler expects a task to be enqueued when
> exiting the idle path. This is not the case with non-polling idle states
> where the idle CPU exits the non-polling idle state to process the
> interrupt, and since need_resched() returns false, soon goes back to
> idle again.
> 
> When TIF_NEED_RESCHED flag is set, do_idle() will call schedule_idle(),
> a large part of which runs with local IRQ disabled. In case of ipistorm,
> when measuring IPI throughput, this large IRQ disabled section delays
> processing of IPIs. Further auditing revealed that in absence of any
> runnable tasks, pick_next_task_fair(), which is called from the
> pick_next_task() fast path, will always call newidle_balance() in this
> scenario, further increasing the time spent in the IRQ disabled section.
> 
> Following is the crude visualization of the problem with relevant
> functions expanded:
> --
> CPU0							CPU1
> ====							====
> 							do_idle() {
> 								__current_set_polling();
> 								...
> 								monitor(addr);
> 								if (!need_resched())
> 									mwait() {
> 									/* Waiting */
> smp_call_function_single(CPU1, func, wait = 1) {				...
> 	...									...
> 	set_nr_if_polling(CPU1) {						...
> 		/* Realizes CPU1 is polling */					...
> 		try_cmpxchg(addr,						...
> 			    &val,						...
> 			    val | _TIF_NEED_RESCHED);				...
> 	} /* Does not send an IPI */						...
> 	...								} /* mwait exit due to write at addr */
> 	csd_lock_wait() {					} 
> 	/* Waiting */						preempt_set_need_resched();
> 		...						__current_clr_polling();
> 		...						flush_smp_call_function_queue() {
> 		...							func();
> 	} /* End of wait */					}
> }								schedule_idle() {
> 									...
> 									local_irq_disable();
> smp_call_function_single(CPU1, func, wait = 1) {			...
> 	...								...
> 	arch_send_call_function_single_ipi(CPU1);			...
> 						\			...
> 						 \			newidle_balance() {
> 						  \				...
> 					      /* Delay */			...
> 						    \			}
> 					     	     \			...
> 						      \-------------->	local_irq_enable();
> 									/* Processes the IPI */
> --
> 
> 
> Skipping newidle_balance()
> ==========================
> 
> In an earlier attempt to solve the challenge of the long IRQ disabled
> section, newidle_balance() was skipped when a CPU waking up from idle
> was found to have no runnable tasks, and was transitioning back to
> idle [2]. Tim [3] and David [4] had pointed out that newidle_balance()
> may be viable for CPUs that are idling with tick enabled, where the
> newidle_balance() has the opportunity to pull tasks onto the idle CPU.

I don't think we should be relying on this in any way shape or form.
NOHZ can kill that tick at any time.

Also, semantically, calling newidle from the idle thread is just daft.
You're really not newly idle in that case.

> Vincent [5] pointed out a case where the idle load kick will fail to
> run on an idle CPU since the IPI handler launching the ILB will check
> for need_resched(). In such cases, the idle CPU relies on
> newidle_balance() to pull tasks towards itself.

Is this the need_resched() in _nohz_idle_balance() ? Should we change
this to 'need_resched() && (rq->nr_running || rq->ttwu_pending)' or
something long those lines?

I mean, it's fairly trivial to figure out if there really is going to be
work there.

> Using an alternate flag instead of NEED_RESCHED to indicate a pending
> IPI was suggested as the correct approach to solve this problem on the
> same thread.

So adding per-arch changes for this seems like something we shouldn't
unless there really is no other sane options.

That is, I really think we should start with something like the below
and then fix any fallout from that.

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 0935f9d4bb7b..cfa45338ae97 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -5799,7 +5800,7 @@ static inline struct task_struct *
 __pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 {
 	const struct sched_class *class;
-	struct task_struct *p;
+	struct task_struct *p = NULL;
 
 	/*
 	 * Optimization: we know that if all tasks are in the fair class we can
@@ -5810,9 +5811,11 @@ __pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
 	if (likely(!sched_class_above(prev->sched_class, &fair_sched_class) &&
 		   rq->nr_running == rq->cfs.h_nr_running)) {
 
-		p = pick_next_task_fair(rq, prev, rf);
-		if (unlikely(p == RETRY_TASK))
-			goto restart;
+		if (rq->nr_running) {
+			p = pick_next_task_fair(rq, prev, rf);
+			if (unlikely(p == RETRY_TASK))
+				goto restart;
+		}
 
 		/* Assume the next prioritized class is idle_sched_class */
 		if (!p) {
Vincent Guittot June 14, 2024, 10:48 a.m. UTC | #2
On Fri, 14 Jun 2024 at 11:28, Peter Zijlstra <peterz@infradead.org> wrote:
>
> On Thu, Jun 13, 2024 at 06:15:59PM +0000, K Prateek Nayak wrote:
> > Effects of call_function_single_prep_ipi()
> > ==========================================
> >
> > To pull a TIF_POLLING thread out of idle to process an IPI, the sender
> > sets the TIF_NEED_RESCHED bit in the idle task's thread info in
> > call_function_single_prep_ipi() and avoids sending an actual IPI to the
> > target. As a result, the scheduler expects a task to be enqueued when
> > exiting the idle path. This is not the case with non-polling idle states
> > where the idle CPU exits the non-polling idle state to process the
> > interrupt, and since need_resched() returns false, soon goes back to
> > idle again.
> >
> > When TIF_NEED_RESCHED flag is set, do_idle() will call schedule_idle(),
> > a large part of which runs with local IRQ disabled. In case of ipistorm,
> > when measuring IPI throughput, this large IRQ disabled section delays
> > processing of IPIs. Further auditing revealed that in absence of any
> > runnable tasks, pick_next_task_fair(), which is called from the
> > pick_next_task() fast path, will always call newidle_balance() in this
> > scenario, further increasing the time spent in the IRQ disabled section.
> >
> > Following is the crude visualization of the problem with relevant
> > functions expanded:
> > --
> > CPU0                                                  CPU1
> > ====                                                  ====
> >                                                       do_idle() {
> >                                                               __current_set_polling();
> >                                                               ...
> >                                                               monitor(addr);
> >                                                               if (!need_resched())
> >                                                                       mwait() {
> >                                                                       /* Waiting */
> > smp_call_function_single(CPU1, func, wait = 1) {                              ...
> >       ...                                                                     ...
> >       set_nr_if_polling(CPU1) {                                               ...
> >               /* Realizes CPU1 is polling */                                  ...
> >               try_cmpxchg(addr,                                               ...
> >                           &val,                                               ...
> >                           val | _TIF_NEED_RESCHED);                           ...
> >       } /* Does not send an IPI */                                            ...
> >       ...                                                             } /* mwait exit due to write at addr */
> >       csd_lock_wait() {                                       }
> >       /* Waiting */                                           preempt_set_need_resched();
> >               ...                                             __current_clr_polling();
> >               ...                                             flush_smp_call_function_queue() {
> >               ...                                                     func();
> >       } /* End of wait */                                     }
> > }                                                             schedule_idle() {
> >                                                                       ...
> >                                                                       local_irq_disable();
> > smp_call_function_single(CPU1, func, wait = 1) {                      ...
> >       ...                                                             ...
> >       arch_send_call_function_single_ipi(CPU1);                       ...
> >                                               \                       ...
> >                                                \                      newidle_balance() {
> >                                                 \                             ...
> >                                             /* Delay */                       ...
> >                                                   \                   }
> >                                                    \                  ...
> >                                                     \-------------->  local_irq_enable();
> >                                                                       /* Processes the IPI */
> > --
> >
> >
> > Skipping newidle_balance()
> > ==========================
> >
> > In an earlier attempt to solve the challenge of the long IRQ disabled
> > section, newidle_balance() was skipped when a CPU waking up from idle
> > was found to have no runnable tasks, and was transitioning back to
> > idle [2]. Tim [3] and David [4] had pointed out that newidle_balance()
> > may be viable for CPUs that are idling with tick enabled, where the
> > newidle_balance() has the opportunity to pull tasks onto the idle CPU.
>
> I don't think we should be relying on this in any way shape or form.
> NOHZ can kill that tick at any time.
>
> Also, semantically, calling newidle from the idle thread is just daft.
> You're really not newly idle in that case.
>
> > Vincent [5] pointed out a case where the idle load kick will fail to
> > run on an idle CPU since the IPI handler launching the ILB will check
> > for need_resched(). In such cases, the idle CPU relies on
> > newidle_balance() to pull tasks towards itself.
>
> Is this the need_resched() in _nohz_idle_balance() ? Should we change
> this to 'need_resched() && (rq->nr_running || rq->ttwu_pending)' or
> something long those lines?

It's not only this but also in do_idle() as well which exits the loop
to look for tasks to schedule

>
> I mean, it's fairly trivial to figure out if there really is going to be
> work there.
>
> > Using an alternate flag instead of NEED_RESCHED to indicate a pending
> > IPI was suggested as the correct approach to solve this problem on the
> > same thread.
>
> So adding per-arch changes for this seems like something we shouldn't
> unless there really is no other sane options.
>
> That is, I really think we should start with something like the below
> and then fix any fallout from that.

The main problem is that need_resched becomes somewhat meaningless
because it doesn't  only mean "I need to resched a task" and we have
to add more tests around even for those not using polling

>
> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> index 0935f9d4bb7b..cfa45338ae97 100644
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -5799,7 +5800,7 @@ static inline struct task_struct *
>  __pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
>  {
>         const struct sched_class *class;
> -       struct task_struct *p;
> +       struct task_struct *p = NULL;
>
>         /*
>          * Optimization: we know that if all tasks are in the fair class we can
> @@ -5810,9 +5811,11 @@ __pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
>         if (likely(!sched_class_above(prev->sched_class, &fair_sched_class) &&
>                    rq->nr_running == rq->cfs.h_nr_running)) {
>
> -               p = pick_next_task_fair(rq, prev, rf);
> -               if (unlikely(p == RETRY_TASK))
> -                       goto restart;
> +               if (rq->nr_running) {

How do you make the diff between a spurious need_resched() because of
polling and a cpu becoming idle ? isn't rq->nr_running null in both
cases ?
In the later case, we need to call sched_balance_newidle() but not in the former

> +                       p = pick_next_task_fair(rq, prev, rf);
> +                       if (unlikely(p == RETRY_TASK))
> +                               goto restart;
> +               }
>
>                 /* Assume the next prioritized class is idle_sched_class */
>                 if (!p) {
Chen Yu June 14, 2024, 4:31 p.m. UTC | #3
On 2024-06-14 at 12:48:37 +0200, Vincent Guittot wrote:
> On Fri, 14 Jun 2024 at 11:28, Peter Zijlstra <peterz@infradead.org> wrote:
> >
> > On Thu, Jun 13, 2024 at 06:15:59PM +0000, K Prateek Nayak wrote:
> > > Effects of call_function_single_prep_ipi()
> > > ==========================================
> > >
> > > To pull a TIF_POLLING thread out of idle to process an IPI, the sender
> > > sets the TIF_NEED_RESCHED bit in the idle task's thread info in
> > > call_function_single_prep_ipi() and avoids sending an actual IPI to the
> > > target. As a result, the scheduler expects a task to be enqueued when
> > > exiting the idle path. This is not the case with non-polling idle states
> > > where the idle CPU exits the non-polling idle state to process the
> > > interrupt, and since need_resched() returns false, soon goes back to
> > > idle again.
> > >
> > > When TIF_NEED_RESCHED flag is set, do_idle() will call schedule_idle(),
> > > a large part of which runs with local IRQ disabled. In case of ipistorm,
> > > when measuring IPI throughput, this large IRQ disabled section delays
> > > processing of IPIs. Further auditing revealed that in absence of any
> > > runnable tasks, pick_next_task_fair(), which is called from the
> > > pick_next_task() fast path, will always call newidle_balance() in this
> > > scenario, further increasing the time spent in the IRQ disabled section.
> > >
> > > Following is the crude visualization of the problem with relevant
> > > functions expanded:
> > > --
> > > CPU0                                                  CPU1
> > > ====                                                  ====
> > >                                                       do_idle() {
> > >                                                               __current_set_polling();
> > >                                                               ...
> > >                                                               monitor(addr);
> > >                                                               if (!need_resched())
> > >                                                                       mwait() {
> > >                                                                       /* Waiting */
> > > smp_call_function_single(CPU1, func, wait = 1) {                              ...
> > >       ...                                                                     ...
> > >       set_nr_if_polling(CPU1) {                                               ...
> > >               /* Realizes CPU1 is polling */                                  ...
> > >               try_cmpxchg(addr,                                               ...
> > >                           &val,                                               ...
> > >                           val | _TIF_NEED_RESCHED);                           ...
> > >       } /* Does not send an IPI */                                            ...
> > >       ...                                                             } /* mwait exit due to write at addr */
> > >       csd_lock_wait() {                                       }
> > >       /* Waiting */                                           preempt_set_need_resched();
> > >               ...                                             __current_clr_polling();
> > >               ...                                             flush_smp_call_function_queue() {
> > >               ...                                                     func();
> > >       } /* End of wait */                                     }
> > > }                                                             schedule_idle() {
> > >                                                                       ...
> > >                                                                       local_irq_disable();
> > > smp_call_function_single(CPU1, func, wait = 1) {                      ...
> > >       ...                                                             ...
> > >       arch_send_call_function_single_ipi(CPU1);                       ...
> > >                                               \                       ...
> > >                                                \                      newidle_balance() {
> > >                                                 \                             ...
> > >                                             /* Delay */                       ...
> > >                                                   \                   }
> > >                                                    \                  ...
> > >                                                     \-------------->  local_irq_enable();
> > >                                                                       /* Processes the IPI */
> > > --
> > >
> > >
> > > Skipping newidle_balance()
> > > ==========================
> > >
> > > In an earlier attempt to solve the challenge of the long IRQ disabled
> > > section, newidle_balance() was skipped when a CPU waking up from idle
> > > was found to have no runnable tasks, and was transitioning back to
> > > idle [2]. Tim [3] and David [4] had pointed out that newidle_balance()
> > > may be viable for CPUs that are idling with tick enabled, where the
> > > newidle_balance() has the opportunity to pull tasks onto the idle CPU.
> >
> > I don't think we should be relying on this in any way shape or form.
> > NOHZ can kill that tick at any time.
> >
> > Also, semantically, calling newidle from the idle thread is just daft.
> > You're really not newly idle in that case.
> >
> > > Vincent [5] pointed out a case where the idle load kick will fail to
> > > run on an idle CPU since the IPI handler launching the ILB will check
> > > for need_resched(). In such cases, the idle CPU relies on
> > > newidle_balance() to pull tasks towards itself.
> >
> > Is this the need_resched() in _nohz_idle_balance() ? Should we change
> > this to 'need_resched() && (rq->nr_running || rq->ttwu_pending)' or
> > something long those lines?
> 
> It's not only this but also in do_idle() as well which exits the loop
> to look for tasks to schedule
> 
> >
> > I mean, it's fairly trivial to figure out if there really is going to be
> > work there.
> >
> > > Using an alternate flag instead of NEED_RESCHED to indicate a pending
> > > IPI was suggested as the correct approach to solve this problem on the
> > > same thread.
> >
> > So adding per-arch changes for this seems like something we shouldn't
> > unless there really is no other sane options.
> >
> > That is, I really think we should start with something like the below
> > and then fix any fallout from that.
> 
> The main problem is that need_resched becomes somewhat meaningless
> because it doesn't  only mean "I need to resched a task" and we have
> to add more tests around even for those not using polling
> 
> >
> > diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> > index 0935f9d4bb7b..cfa45338ae97 100644
> > --- a/kernel/sched/core.c
> > +++ b/kernel/sched/core.c
> > @@ -5799,7 +5800,7 @@ static inline struct task_struct *
> >  __pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
> >  {
> >         const struct sched_class *class;
> > -       struct task_struct *p;
> > +       struct task_struct *p = NULL;
> >
> >         /*
> >          * Optimization: we know that if all tasks are in the fair class we can
> > @@ -5810,9 +5811,11 @@ __pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
> >         if (likely(!sched_class_above(prev->sched_class, &fair_sched_class) &&
> >                    rq->nr_running == rq->cfs.h_nr_running)) {
> >
> > -               p = pick_next_task_fair(rq, prev, rf);
> > -               if (unlikely(p == RETRY_TASK))
> > -                       goto restart;
> > +               if (rq->nr_running) {
> 
> How do you make the diff between a spurious need_resched() because of
> polling and a cpu becoming idle ? isn't rq->nr_running null in both
> cases ?
> In the later case, we need to call sched_balance_newidle() but not in the former
>

Not sure if I understand correctly, if the goal of smp_call_function_single() is to
kick the idle CPU and do not force it to launch the schedule()->sched_balance_newidle(),
can we set the _TIF_POLLING_NRFLAG rather than _TIF_NEED_RESCHED in set_nr_if_polling()?
I think writing any value to the monitor address would wakeup the idle CPU. And _TIF_POLLING_NRFLAG
will be cleared once that idle CPU exit the idle loop, so we don't introduce arch-wide flag.

thanks,
Chenyu
 
> > +                       p = pick_next_task_fair(rq, prev, rf);
> > +                       if (unlikely(p == RETRY_TASK))
> > +                               goto restart;
> > +               }
> >
> >                 /* Assume the next prioritized class is idle_sched_class */
> >                 if (!p) {
Peter Zijlstra June 15, 2024, 1:28 a.m. UTC | #4
On Fri, Jun 14, 2024 at 12:48:37PM +0200, Vincent Guittot wrote:
> On Fri, 14 Jun 2024 at 11:28, Peter Zijlstra <peterz@infradead.org> wrote:

> > > Vincent [5] pointed out a case where the idle load kick will fail to
> > > run on an idle CPU since the IPI handler launching the ILB will check
> > > for need_resched(). In such cases, the idle CPU relies on
> > > newidle_balance() to pull tasks towards itself.
> >
> > Is this the need_resched() in _nohz_idle_balance() ? Should we change
> > this to 'need_resched() && (rq->nr_running || rq->ttwu_pending)' or
> > something long those lines?
> 
> It's not only this but also in do_idle() as well which exits the loop
> to look for tasks to schedule

Is that really a problem? Reading the initial email the problem seems to
be newidle balance, not hitting schedule. Schedule should be fairly
quick if there's nothing to do, no?

> > I mean, it's fairly trivial to figure out if there really is going to be
> > work there.
> >
> > > Using an alternate flag instead of NEED_RESCHED to indicate a pending
> > > IPI was suggested as the correct approach to solve this problem on the
> > > same thread.
> >
> > So adding per-arch changes for this seems like something we shouldn't
> > unless there really is no other sane options.
> >
> > That is, I really think we should start with something like the below
> > and then fix any fallout from that.
> 
> The main problem is that need_resched becomes somewhat meaningless
> because it doesn't  only mean "I need to resched a task" and we have
> to add more tests around even for those not using polling

True, however we already had some of that by having the wakeup list,
that made nr_running less 'reliable'.

The thing is, most architectures seem to have the TIF_POLLING_NRFLAG
bit, even if their main idle routine isn't actually using it, much of
the idle loop until it hits the arch idle will be having it set and will
thus tickle these cases *sometimes*.

> > diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> > index 0935f9d4bb7b..cfa45338ae97 100644
> > --- a/kernel/sched/core.c
> > +++ b/kernel/sched/core.c
> > @@ -5799,7 +5800,7 @@ static inline struct task_struct *
> >  __pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
> >  {
> >         const struct sched_class *class;
> > -       struct task_struct *p;
> > +       struct task_struct *p = NULL;
> >
> >         /*
> >          * Optimization: we know that if all tasks are in the fair class we can
> > @@ -5810,9 +5811,11 @@ __pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
> >         if (likely(!sched_class_above(prev->sched_class, &fair_sched_class) &&
> >                    rq->nr_running == rq->cfs.h_nr_running)) {
> >
> > -               p = pick_next_task_fair(rq, prev, rf);
> > -               if (unlikely(p == RETRY_TASK))
> > -                       goto restart;
> > +               if (rq->nr_running) {
> 
> How do you make the diff between a spurious need_resched() because of
> polling and a cpu becoming idle ? isn't rq->nr_running null in both
> cases ?

Bah, true. It should also check current being idle, which then makes a
mess of things again. Still, we shouldn't be calling newidle from idle,
that's daft.

I should probably not write code at 3am, but the below horror is what
I came up with.

---

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 0935f9d4bb7b..cfe8d3350819 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -6343,19 +6344,12 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
  * Constants for the sched_mode argument of __schedule().
  *
  * The mode argument allows RT enabled kernels to differentiate a
- * preemption from blocking on an 'sleeping' spin/rwlock. Note that
- * SM_MASK_PREEMPT for !RT has all bits set, which allows the compiler to
- * optimize the AND operation out and just check for zero.
+ * preemption from blocking on an 'sleeping' spin/rwlock.
  */
-#define SM_NONE			0x0
-#define SM_PREEMPT		0x1
-#define SM_RTLOCK_WAIT		0x2
-
-#ifndef CONFIG_PREEMPT_RT
-# define SM_MASK_PREEMPT	(~0U)
-#else
-# define SM_MASK_PREEMPT	SM_PREEMPT
-#endif
+#define SM_IDLE			(-1)
+#define SM_NONE			0
+#define SM_PREEMPT		1
+#define SM_RTLOCK_WAIT		2
 
 /*
  * __schedule() is the main scheduler function.
@@ -6396,11 +6390,12 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
  *
  * WARNING: must be called with preemption disabled!
  */
-static void __sched notrace __schedule(unsigned int sched_mode)
+static void __sched notrace __schedule(int sched_mode)
 {
 	struct task_struct *prev, *next;
 	unsigned long *switch_count;
 	unsigned long prev_state;
+	bool preempt = sched_mode > 0;
 	struct rq_flags rf;
 	struct rq *rq;
 	int cpu;
@@ -6409,13 +6404,13 @@ static void __sched notrace __schedule(unsigned int sched_mode)
 	rq = cpu_rq(cpu);
 	prev = rq->curr;
 
-	schedule_debug(prev, !!sched_mode);
+	schedule_debug(prev, preempt);
 
 	if (sched_feat(HRTICK) || sched_feat(HRTICK_DL))
 		hrtick_clear(rq);
 
 	local_irq_disable();
-	rcu_note_context_switch(!!sched_mode);
+	rcu_note_context_switch(preempt);
 
 	/*
 	 * Make sure that signal_pending_state()->signal_pending() below
@@ -6449,7 +6444,12 @@ static void __sched notrace __schedule(unsigned int sched_mode)
 	 * that we form a control dependency vs deactivate_task() below.
 	 */
 	prev_state = READ_ONCE(prev->__state);
-	if (!(sched_mode & SM_MASK_PREEMPT) && prev_state) {
+	if (sched_mode == SM_IDLE) {
+		if (!rq->nr_running) {
+			next = prev;
+			goto picked;
+		}
+	} else if (!preempt && prev_state) {
 		if (signal_pending_state(prev_state, prev)) {
 			WRITE_ONCE(prev->__state, TASK_RUNNING);
 		} else {
@@ -6483,6 +6483,7 @@ static void __sched notrace __schedule(unsigned int sched_mode)
 	}
 
 	next = pick_next_task(rq, prev, &rf);
+picked:
 	clear_tsk_need_resched(prev);
 	clear_preempt_need_resched();
 #ifdef CONFIG_SCHED_DEBUG
@@ -6521,9 +6522,9 @@ static void __sched notrace __schedule(unsigned int sched_mode)
 		++*switch_count;
 
 		migrate_disable_switch(rq, prev);
 		psi_sched_switch(prev, next, !task_on_rq_queued(prev));
 
-		trace_sched_switch(sched_mode & SM_MASK_PREEMPT, prev, next, prev_state);
+		trace_sched_switch(preempt, prev, next, prev_state);
 
 		/* Also unlocks the rq: */
 		rq = context_switch(rq, prev, next, &rf);
@@ -6599,7 +6601,7 @@ static void sched_update_worker(struct task_struct *tsk)
 	}
 }
 
-static __always_inline void __schedule_loop(unsigned int sched_mode)
+static __always_inline void __schedule_loop(int sched_mode)
 {
 	do {
 		preempt_disable();
@@ -6644,7 +6646,7 @@ void __sched schedule_idle(void)
 	 */
 	WARN_ON_ONCE(current->__state);
 	do {
-		__schedule(SM_NONE);
+		__schedule(SM_IDLE);
 	} while (need_resched());
 }
Peter Zijlstra June 15, 2024, 1:42 a.m. UTC | #5
On Fri, Jun 14, 2024 at 12:48:37PM +0200, Vincent Guittot wrote:

> The main problem is that need_resched becomes somewhat meaningless
> because it doesn't  only mean "I need to resched a task" and we have
> to add more tests around even for those not using polling

The converse problem is that you're adding a bunch of atomic ops that
might be avoided.

It might now need to set both the RESCHED and IPI flags -- and clear
them again.
Peter Zijlstra June 15, 2024, 1:45 a.m. UTC | #6
On Sat, Jun 15, 2024 at 03:28:14AM +0200, Peter Zijlstra wrote:
> On Fri, Jun 14, 2024 at 12:48:37PM +0200, Vincent Guittot wrote:

> > The main problem is that need_resched becomes somewhat meaningless
> > because it doesn't  only mean "I need to resched a task" and we have
> > to add more tests around even for those not using polling
> 
> True, however we already had some of that by having the wakeup list,
> that made nr_running less 'reliable'.

Doesn't using !idle_cpu() instead of need_resched() in those balance
paths already do the right thing?

Checking need_resched() as an indicator of it getting work is already a
bit an assumption.

Also, Ingo, idle_cpu() and friends don't really belong in syscalls.c...
Russell King (Oracle) June 15, 2024, 2:26 p.m. UTC | #7
On Thu, Jun 13, 2024 at 06:15:59PM +0000, K Prateek Nayak wrote:
> o Dropping the ARM results since I never got my hands on the ARM64
>   system I used in my last testing. If I do manage to get my hands on it
>   again, I'll rerun the experiments and share the results on the thread.
>   To test the case where TIF_NOTIFY_IPI is not enabled for a particular
>   architecture, I applied the series only until Patch 3 and tested the
>   same on my x86 machine with a WARN_ON_ONCE() in do_idle() to check if
>   tif_notify_ipi() ever return true and then repeated the same with
>   Patch 4 applied.

Confused. ARM (32-bit) or ARM64? You patch 32-bit ARM, but you don't
touch 64-bit Arm. "ARM" on its own in the context above to me suggests
32-bit, since you refer to ARM64 later.
Vincent Guittot June 16, 2024, 2:57 p.m. UTC | #8
On Sat, 15 Jun 2024 at 03:28, Peter Zijlstra <peterz@infradead.org> wrote:
>
> On Fri, Jun 14, 2024 at 12:48:37PM +0200, Vincent Guittot wrote:
> > On Fri, 14 Jun 2024 at 11:28, Peter Zijlstra <peterz@infradead.org> wrote:
>
> > > > Vincent [5] pointed out a case where the idle load kick will fail to
> > > > run on an idle CPU since the IPI handler launching the ILB will check
> > > > for need_resched(). In such cases, the idle CPU relies on
> > > > newidle_balance() to pull tasks towards itself.
> > >
> > > Is this the need_resched() in _nohz_idle_balance() ? Should we change
> > > this to 'need_resched() && (rq->nr_running || rq->ttwu_pending)' or
> > > something long those lines?
> >
> > It's not only this but also in do_idle() as well which exits the loop
> > to look for tasks to schedule
>
> Is that really a problem? Reading the initial email the problem seems to
> be newidle balance, not hitting schedule. Schedule should be fairly
> quick if there's nothing to do, no?

There are 2 problems:
- Because of NEED_RESCHED being set, we go through the full schedule
path for no reason and we finally do a sched_balance_newidle()
- Because of need_resched being set o wake up the cpu, we will not
kick the softirq to run the nohz idle load balance and get a chance to
pull a task on an idle CPU

>
> > > I mean, it's fairly trivial to figure out if there really is going to be
> > > work there.
> > >
> > > > Using an alternate flag instead of NEED_RESCHED to indicate a pending
> > > > IPI was suggested as the correct approach to solve this problem on the
> > > > same thread.
> > >
> > > So adding per-arch changes for this seems like something we shouldn't
> > > unless there really is no other sane options.
> > >
> > > That is, I really think we should start with something like the below
> > > and then fix any fallout from that.
> >
> > The main problem is that need_resched becomes somewhat meaningless
> > because it doesn't  only mean "I need to resched a task" and we have
> > to add more tests around even for those not using polling
>
> True, however we already had some of that by having the wakeup list,
> that made nr_running less 'reliable'.
>
> The thing is, most architectures seem to have the TIF_POLLING_NRFLAG
> bit, even if their main idle routine isn't actually using it, much of

Yes, I'm surprised that Arm arch has the TIF_POLLING_NRFLAG whereas it
has never been supported by the arch

> the idle loop until it hits the arch idle will be having it set and will
> thus tickle these cases *sometimes*.
>
> > > diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> > > index 0935f9d4bb7b..cfa45338ae97 100644
> > > --- a/kernel/sched/core.c
> > > +++ b/kernel/sched/core.c
> > > @@ -5799,7 +5800,7 @@ static inline struct task_struct *
> > >  __pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
> > >  {
> > >         const struct sched_class *class;
> > > -       struct task_struct *p;
> > > +       struct task_struct *p = NULL;
> > >
> > >         /*
> > >          * Optimization: we know that if all tasks are in the fair class we can
> > > @@ -5810,9 +5811,11 @@ __pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
> > >         if (likely(!sched_class_above(prev->sched_class, &fair_sched_class) &&
> > >                    rq->nr_running == rq->cfs.h_nr_running)) {
> > >
> > > -               p = pick_next_task_fair(rq, prev, rf);
> > > -               if (unlikely(p == RETRY_TASK))
> > > -                       goto restart;
> > > +               if (rq->nr_running) {
> >
> > How do you make the diff between a spurious need_resched() because of
> > polling and a cpu becoming idle ? isn't rq->nr_running null in both
> > cases ?
>
> Bah, true. It should also check current being idle, which then makes a
> mess of things again. Still, we shouldn't be calling newidle from idle,
> that's daft.
>
> I should probably not write code at 3am, but the below horror is what
> I came up with.
>
> ---
>
> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> index 0935f9d4bb7b..cfe8d3350819 100644
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -6343,19 +6344,12 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
>   * Constants for the sched_mode argument of __schedule().
>   *
>   * The mode argument allows RT enabled kernels to differentiate a
> - * preemption from blocking on an 'sleeping' spin/rwlock. Note that
> - * SM_MASK_PREEMPT for !RT has all bits set, which allows the compiler to
> - * optimize the AND operation out and just check for zero.
> + * preemption from blocking on an 'sleeping' spin/rwlock.
>   */
> -#define SM_NONE                        0x0
> -#define SM_PREEMPT             0x1
> -#define SM_RTLOCK_WAIT         0x2
> -
> -#ifndef CONFIG_PREEMPT_RT
> -# define SM_MASK_PREEMPT       (~0U)
> -#else
> -# define SM_MASK_PREEMPT       SM_PREEMPT
> -#endif
> +#define SM_IDLE                        (-1)
> +#define SM_NONE                        0
> +#define SM_PREEMPT             1
> +#define SM_RTLOCK_WAIT         2
>
>  /*
>   * __schedule() is the main scheduler function.
> @@ -6396,11 +6390,12 @@ pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
>   *
>   * WARNING: must be called with preemption disabled!
>   */
> -static void __sched notrace __schedule(unsigned int sched_mode)
> +static void __sched notrace __schedule(int sched_mode)
>  {
>         struct task_struct *prev, *next;
>         unsigned long *switch_count;
>         unsigned long prev_state;
> +       bool preempt = sched_mode > 0;
>         struct rq_flags rf;
>         struct rq *rq;
>         int cpu;
> @@ -6409,13 +6404,13 @@ static void __sched notrace __schedule(unsigned int sched_mode)
>         rq = cpu_rq(cpu);
>         prev = rq->curr;
>
> -       schedule_debug(prev, !!sched_mode);
> +       schedule_debug(prev, preempt);
>
>         if (sched_feat(HRTICK) || sched_feat(HRTICK_DL))
>                 hrtick_clear(rq);
>
>         local_irq_disable();
> -       rcu_note_context_switch(!!sched_mode);
> +       rcu_note_context_switch(preempt);
>
>         /*
>          * Make sure that signal_pending_state()->signal_pending() below
> @@ -6449,7 +6444,12 @@ static void __sched notrace __schedule(unsigned int sched_mode)
>          * that we form a control dependency vs deactivate_task() below.
>          */
>         prev_state = READ_ONCE(prev->__state);
> -       if (!(sched_mode & SM_MASK_PREEMPT) && prev_state) {
> +       if (sched_mode == SM_IDLE) {
> +               if (!rq->nr_running) {
> +                       next = prev;
> +                       goto picked;
> +               }
> +       } else if (!preempt && prev_state) {
>                 if (signal_pending_state(prev_state, prev)) {
>                         WRITE_ONCE(prev->__state, TASK_RUNNING);
>                 } else {
> @@ -6483,6 +6483,7 @@ static void __sched notrace __schedule(unsigned int sched_mode)
>         }
>
>         next = pick_next_task(rq, prev, &rf);
> +picked:
>         clear_tsk_need_resched(prev);
>         clear_preempt_need_resched();
>  #ifdef CONFIG_SCHED_DEBUG
> @@ -6521,9 +6522,9 @@ static void __sched notrace __schedule(unsigned int sched_mode)
>                 ++*switch_count;
>
>                 migrate_disable_switch(rq, prev);
>                 psi_sched_switch(prev, next, !task_on_rq_queued(prev));
>
> -               trace_sched_switch(sched_mode & SM_MASK_PREEMPT, prev, next, prev_state);
> +               trace_sched_switch(preempt, prev, next, prev_state);
>
>                 /* Also unlocks the rq: */
>                 rq = context_switch(rq, prev, next, &rf);
> @@ -6599,7 +6601,7 @@ static void sched_update_worker(struct task_struct *tsk)
>         }
>  }
>
> -static __always_inline void __schedule_loop(unsigned int sched_mode)
> +static __always_inline void __schedule_loop(int sched_mode)
>  {
>         do {
>                 preempt_disable();
> @@ -6644,7 +6646,7 @@ void __sched schedule_idle(void)
>          */
>         WARN_ON_ONCE(current->__state);
>         do {
> -               __schedule(SM_NONE);
> +               __schedule(SM_IDLE);
>         } while (need_resched());
>  }
>
K Prateek Nayak June 17, 2024, 4:35 a.m. UTC | #9
Hello Russell,

On 6/15/2024 7:56 PM, Russell King (Oracle) wrote:
> On Thu, Jun 13, 2024 at 06:15:59PM +0000, K Prateek Nayak wrote:
>> o Dropping the ARM results since I never got my hands on the ARM64
>>    system I used in my last testing. If I do manage to get my hands on it
>>    again, I'll rerun the experiments and share the results on the thread.
>>    To test the case where TIF_NOTIFY_IPI is not enabled for a particular
>>    architecture, I applied the series only until Patch 3 and tested the
>>    same on my x86 machine with a WARN_ON_ONCE() in do_idle() to check if
>>    tif_notify_ipi() ever return true and then repeated the same with
>>    Patch 4 applied.
> 
> Confused. ARM (32-bit) or ARM64? You patch 32-bit ARM, but you don't
> touch 64-bit Arm. "ARM" on its own in the context above to me suggests
> 32-bit, since you refer to ARM64 later.
> 

In my first RFC posting, I had shared the results for ipistorm on an
ARM64 server [1]. Vincent and Linus Walleij brought to my attention that
ARM32 and ARM64 do not share the thread info flags and I probably saw a
one-off behavior during my testing. Since then, it has been slightly
challenging to get my hands on that machine again in a stable condition
to see if there was any scenario that I might have missed but I tried a
bunch of things on my x86 machine to confirm that an arch that does not
define the TIF_NOTIFY_IPI would not hit these changes.

Rest assured, Patch 5 is for ARM32 machines that currently define
TIF_POLLING_NRFLAG

[1] https://lore.kernel.org/lkml/20240220171457.703-6-kprateek.nayak@amd.com/
K Prateek Nayak June 17, 2024, 5:52 a.m. UTC | #10
Hello Vincent, Peter,

On 6/16/2024 8:27 PM, Vincent Guittot wrote:
> On Sat, 15 Jun 2024 at 03:28, Peter Zijlstra <peterz@infradead.org> wrote:
>>
>> On Fri, Jun 14, 2024 at 12:48:37PM +0200, Vincent Guittot wrote:
>>> On Fri, 14 Jun 2024 at 11:28, Peter Zijlstra <peterz@infradead.org> wrote:
>>
>>>>> Vincent [5] pointed out a case where the idle load kick will fail to
>>>>> run on an idle CPU since the IPI handler launching the ILB will check
>>>>> for need_resched(). In such cases, the idle CPU relies on
>>>>> newidle_balance() to pull tasks towards itself.
>>>>
>>>> Is this the need_resched() in _nohz_idle_balance() ? Should we change
>>>> this to 'need_resched() && (rq->nr_running || rq->ttwu_pending)' or
>>>> something long those lines?
>>>
>>> It's not only this but also in do_idle() as well which exits the loop
>>> to look for tasks to schedule
>>
>> Is that really a problem? Reading the initial email the problem seems to
>> be newidle balance, not hitting schedule. Schedule should be fairly
>> quick if there's nothing to do, no?
> 
> There are 2 problems:
> - Because of NEED_RESCHED being set, we go through the full schedule
> path for no reason and we finally do a sched_balance_newidle()

Peter's patch up in the thread seems to improve the above case by
speeding up the schedule() loop similar to the very first solution
I tried with
https://lore.kernel.org/lkml/20240119084548.2788-1-kprateek.nayak@amd.com/

I do see same level of improvements (if not better) with Peter's
SM_IDLE solution:

   ==================================================================
   Test          : ipistorm (modified)
   Units         : Normalized runtime
   Interpretation: Lower is better
   Statistic     : AMean
   ==================================================================
   kernel:				time [pct imp]
   tip:sched/core			1.00 [baseline]
   tip:sched/core + revert		0.40 [60.26%]
   tip:sched/core + TIF_NOTIFY_IPI	0.46 [54.88%]
   tip:sched/core + SM_IDLE		0.38 [72.64%]

> - Because of need_resched being set o wake up the cpu, we will not
> kick the softirq to run the nohz idle load balance and get a chance to
> pull a task on an idle CPU

However, this issues with need_resched() still remains. Any
need_resched() check within an interrupt context will return true if the
target CPU is perceived to be in a polling idle state by the sender as a
result of the optimization in commit b2a02fc43a1f ("smp: Optimize
send_call_function_single_ipi()").

If TIF_POLLING_NRFLAG is defined by an arch, do_idle() will set the
flag until the path hits call_cpuidle() where the flag is cleared just
before handing off the state entry to the cpuidle driver. An incoming
interrupt in this window will allow the idle path to bail early and
return before calling the driver specific routine since it'll be
indicated by TIF_NEED_RESCHED being set in the idle task's thread info.
Beyond that point, the cpuidle driver handles the idle entry.

I think an arch may define TIF_POLLING_NRFLAG just to utilize this
optimization in the generic idle path to answer Vincent's observation
on ARM32 having TIF_POLLING_NRFLAG.

> 
>>
>>>> I mean, it's fairly trivial to figure out if there really is going to be
>>>> work there.
>>>>
>>>>> Using an alternate flag instead of NEED_RESCHED to indicate a pending
>>>>> IPI was suggested as the correct approach to solve this problem on the
>>>>> same thread.
>>>>
>>>> So adding per-arch changes for this seems like something we shouldn't
>>>> unless there really is no other sane options.
>>>>
>>>> That is, I really think we should start with something like the below
>>>> and then fix any fallout from that.
>>>
>>> The main problem is that need_resched becomes somewhat meaningless
>>> because it doesn't  only mean "I need to resched a task" and we have
>>> to add more tests around even for those not using polling
>>
>> True, however we already had some of that by having the wakeup list,
>> that made nr_running less 'reliable'.
>>
>> The thing is, most architectures seem to have the TIF_POLLING_NRFLAG
>> bit, even if their main idle routine isn't actually using it, much of
> 
> Yes, I'm surprised that Arm arch has the TIF_POLLING_NRFLAG whereas it
> has never been supported by the arch
> 
>> the idle loop until it hits the arch idle will be having it set and will
>> thus tickle these cases *sometimes*.
>> [..snip..]
K Prateek Nayak June 17, 2024, 8:33 a.m. UTC | #11
Hello Chenyu,

On 6/14/2024 10:01 PM, Chen Yu wrote:
> On 2024-06-14 at 12:48:37 +0200, Vincent Guittot wrote:
>> On Fri, 14 Jun 2024 at 11:28, Peter Zijlstra <peterz@infradead.org> wrote:
>>>
>>> On Thu, Jun 13, 2024 at 06:15:59PM +0000, K Prateek Nayak wrote:
>>>> Effects of call_function_single_prep_ipi()
>>>> ==========================================
>>>>
>>>> To pull a TIF_POLLING thread out of idle to process an IPI, the sender
>>>> sets the TIF_NEED_RESCHED bit in the idle task's thread info in
>>>> call_function_single_prep_ipi() and avoids sending an actual IPI to the
>>>> target. As a result, the scheduler expects a task to be enqueued when
>>>> exiting the idle path. This is not the case with non-polling idle states
>>>> where the idle CPU exits the non-polling idle state to process the
>>>> interrupt, and since need_resched() returns false, soon goes back to
>>>> idle again.
>>>>
>>>> When TIF_NEED_RESCHED flag is set, do_idle() will call schedule_idle(),
>>>> a large part of which runs with local IRQ disabled. In case of ipistorm,
>>>> when measuring IPI throughput, this large IRQ disabled section delays
>>>> processing of IPIs. Further auditing revealed that in absence of any
>>>> runnable tasks, pick_next_task_fair(), which is called from the
>>>> pick_next_task() fast path, will always call newidle_balance() in this
>>>> scenario, further increasing the time spent in the IRQ disabled section.
>>>>
>>>> Following is the crude visualization of the problem with relevant
>>>> functions expanded:
>>>> --
>>>> CPU0                                                  CPU1
>>>> ====                                                  ====
>>>>                                                        do_idle() {
>>>>                                                                __current_set_polling();
>>>>                                                                ...
>>>>                                                                monitor(addr);
>>>>                                                                if (!need_resched())
>>>>                                                                        mwait() {
>>>>                                                                        /* Waiting */
>>>> smp_call_function_single(CPU1, func, wait = 1) {                              ...
>>>>        ...                                                                     ...
>>>>        set_nr_if_polling(CPU1) {                                               ...
>>>>                /* Realizes CPU1 is polling */                                  ...
>>>>                try_cmpxchg(addr,                                               ...
>>>>                            &val,                                               ...
>>>>                            val | _TIF_NEED_RESCHED);                           ...
>>>>        } /* Does not send an IPI */                                            ...
>>>>        ...                                                             } /* mwait exit due to write at addr */
>>>>        csd_lock_wait() {                                       }
>>>>        /* Waiting */                                           preempt_set_need_resched();
>>>>                ...                                             __current_clr_polling();
>>>>                ...                                             flush_smp_call_function_queue() {
>>>>                ...                                                     func();
>>>>        } /* End of wait */                                     }
>>>> }                                                             schedule_idle() {
>>>>                                                                        ...
>>>>                                                                        local_irq_disable();
>>>> smp_call_function_single(CPU1, func, wait = 1) {                      ...
>>>>        ...                                                             ...
>>>>        arch_send_call_function_single_ipi(CPU1);                       ...
>>>>                                                \                       ...
>>>>                                                 \                      newidle_balance() {
>>>>                                                  \                             ...
>>>>                                              /* Delay */                       ...
>>>>                                                    \                   }
>>>>                                                     \                  ...
>>>>                                                      \-------------->  local_irq_enable();
>>>>                                                                        /* Processes the IPI */
>>>> --
>>>>
>>>>
>>>> Skipping newidle_balance()
>>>> ==========================
>>>>
>>>> In an earlier attempt to solve the challenge of the long IRQ disabled
>>>> section, newidle_balance() was skipped when a CPU waking up from idle
>>>> was found to have no runnable tasks, and was transitioning back to
>>>> idle [2]. Tim [3] and David [4] had pointed out that newidle_balance()
>>>> may be viable for CPUs that are idling with tick enabled, where the
>>>> newidle_balance() has the opportunity to pull tasks onto the idle CPU.
>>>
>>> I don't think we should be relying on this in any way shape or form.
>>> NOHZ can kill that tick at any time.
>>>
>>> Also, semantically, calling newidle from the idle thread is just daft.
>>> You're really not newly idle in that case.
>>>
>>>> Vincent [5] pointed out a case where the idle load kick will fail to
>>>> run on an idle CPU since the IPI handler launching the ILB will check
>>>> for need_resched(). In such cases, the idle CPU relies on
>>>> newidle_balance() to pull tasks towards itself.
>>>
>>> Is this the need_resched() in _nohz_idle_balance() ? Should we change
>>> this to 'need_resched() && (rq->nr_running || rq->ttwu_pending)' or
>>> something long those lines?
>>
>> It's not only this but also in do_idle() as well which exits the loop
>> to look for tasks to schedule
>>
>>>
>>> I mean, it's fairly trivial to figure out if there really is going to be
>>> work there.
>>>
>>>> Using an alternate flag instead of NEED_RESCHED to indicate a pending
>>>> IPI was suggested as the correct approach to solve this problem on the
>>>> same thread.
>>>
>>> So adding per-arch changes for this seems like something we shouldn't
>>> unless there really is no other sane options.
>>>
>>> That is, I really think we should start with something like the below
>>> and then fix any fallout from that.
>>
>> The main problem is that need_resched becomes somewhat meaningless
>> because it doesn't  only mean "I need to resched a task" and we have
>> to add more tests around even for those not using polling
>>
>>>
>>> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
>>> index 0935f9d4bb7b..cfa45338ae97 100644
>>> --- a/kernel/sched/core.c
>>> +++ b/kernel/sched/core.c
>>> @@ -5799,7 +5800,7 @@ static inline struct task_struct *
>>>   __pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
>>>   {
>>>          const struct sched_class *class;
>>> -       struct task_struct *p;
>>> +       struct task_struct *p = NULL;
>>>
>>>          /*
>>>           * Optimization: we know that if all tasks are in the fair class we can
>>> @@ -5810,9 +5811,11 @@ __pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
>>>          if (likely(!sched_class_above(prev->sched_class, &fair_sched_class) &&
>>>                     rq->nr_running == rq->cfs.h_nr_running)) {
>>>
>>> -               p = pick_next_task_fair(rq, prev, rf);
>>> -               if (unlikely(p == RETRY_TASK))
>>> -                       goto restart;
>>> +               if (rq->nr_running) {
>>
>> How do you make the diff between a spurious need_resched() because of
>> polling and a cpu becoming idle ? isn't rq->nr_running null in both
>> cases ?
>> In the later case, we need to call sched_balance_newidle() but not in the former
>>
> 
> Not sure if I understand correctly, if the goal of smp_call_function_single() is to
> kick the idle CPU and do not force it to launch the schedule()->sched_balance_newidle(),
> can we set the _TIF_POLLING_NRFLAG rather than _TIF_NEED_RESCHED in set_nr_if_polling()?
> I think writing any value to the monitor address would wakeup the idle CPU. And _TIF_POLLING_NRFLAG
> will be cleared once that idle CPU exit the idle loop, so we don't introduce arch-wide flag.
Although this might work for MWAIT, there is no way for the generic idle
path to know if there is a pending interrupt within a TIF_POLLING_NRFLAG
section. do_idle() sets TIF_POLLING_NRFLAG and relies on a bunch of
need_resched() checks along the way to bail early until finally doing a
current_clr_polling_and_test() before handing off to the cpuidle driver
in call_cpuidle(). I believe this section will necessarily need the sender
to indicate a pending interrupt via TIF_NEED_RESCHED flag to enable the
early bail out before going into the cpuidle driver since this case cannot
be considered the same as a break from MWAIT.

On x86, there seems to be a possibility of missing an interrupt if
someone writes _TIF_POLLING_NRFLAG to thread info between the target
executing MONTOR and MWAIT. AMD64 Architecture Programmer’s Manual
Volume 3: "General-Purpose and System Instructions", Chapter 4. "System
Instruction Reference", section "MWAIT" carries the following note in
the coding requirements:

"MWAIT must be conditionally executed only if the awaited store has not
already occurred. (This prevents a race condition between the MONITOR
instruction arming the monitoring hardware and the store intended to
trigger the monitoring hardware.)"

There exists a similar note in the "Example" section for "MWAIT" in
Intel 64 and IA-32 Architectures Software Developer’s Manual, Vol 2B
Chapter 4.3 "Instructions (M-U)"

I'm not sure if one can use use _TIF_POLLING_NRFLAG alone and cover
all the cases but there might be some clever trick to make it all
work :)

> 
> thanks,
> Chenyu
>   
>>> +                       p = pick_next_task_fair(rq, prev, rf);
>>> +                       if (unlikely(p == RETRY_TASK))
>>> +                               goto restart;
>>> +               }
>>>
>>>                  /* Assume the next prioritized class is idle_sched_class */
>>>                  if (!p) {
Chen Yu June 18, 2024, 7:49 a.m. UTC | #12
On 2024-06-17 at 14:03:41 +0530, K Prateek Nayak wrote:
> Hello Chenyu,
> 
> On 6/14/2024 10:01 PM, Chen Yu wrote:
> > On 2024-06-14 at 12:48:37 +0200, Vincent Guittot wrote:
> > > On Fri, 14 Jun 2024 at 11:28, Peter Zijlstra <peterz@infradead.org> wrote:
> > > > 
> > > > On Thu, Jun 13, 2024 at 06:15:59PM +0000, K Prateek Nayak wrote:
> > > > > Effects of call_function_single_prep_ipi()
> > > > > ==========================================
> > > > > 
> > > > > To pull a TIF_POLLING thread out of idle to process an IPI, the sender
> > > > > sets the TIF_NEED_RESCHED bit in the idle task's thread info in
> > > > > call_function_single_prep_ipi() and avoids sending an actual IPI to the
> > > > > target. As a result, the scheduler expects a task to be enqueued when
> > > > > exiting the idle path. This is not the case with non-polling idle states
> > > > > where the idle CPU exits the non-polling idle state to process the
> > > > > interrupt, and since need_resched() returns false, soon goes back to
> > > > > idle again.
> > > > > 
> > > > > When TIF_NEED_RESCHED flag is set, do_idle() will call schedule_idle(),
> > > > > a large part of which runs with local IRQ disabled. In case of ipistorm,
> > > > > when measuring IPI throughput, this large IRQ disabled section delays
> > > > > processing of IPIs. Further auditing revealed that in absence of any
> > > > > runnable tasks, pick_next_task_fair(), which is called from the
> > > > > pick_next_task() fast path, will always call newidle_balance() in this
> > > > > scenario, further increasing the time spent in the IRQ disabled section.
> > > > > 
> > > > > Following is the crude visualization of the problem with relevant
> > > > > functions expanded:
> > > > > --
> > > > > CPU0                                                  CPU1
> > > > > ====                                                  ====
> > > > >                                                        do_idle() {
> > > > >                                                                __current_set_polling();
> > > > >                                                                ...
> > > > >                                                                monitor(addr);
> > > > >                                                                if (!need_resched())
> > > > >                                                                        mwait() {
> > > > >                                                                        /* Waiting */
> > > > > smp_call_function_single(CPU1, func, wait = 1) {                              ...
> > > > >        ...                                                                     ...
> > > > >        set_nr_if_polling(CPU1) {                                               ...
> > > > >                /* Realizes CPU1 is polling */                                  ...
> > > > >                try_cmpxchg(addr,                                               ...
> > > > >                            &val,                                               ...
> > > > >                            val | _TIF_NEED_RESCHED);                           ...
> > > > >        } /* Does not send an IPI */                                            ...
> > > > >        ...                                                             } /* mwait exit due to write at addr */
> > > > >        csd_lock_wait() {                                       }
> > > > >        /* Waiting */                                           preempt_set_need_resched();
> > > > >                ...                                             __current_clr_polling();
> > > > >                ...                                             flush_smp_call_function_queue() {
> > > > >                ...                                                     func();
> > > > >        } /* End of wait */                                     }
> > > > > }                                                             schedule_idle() {
> > > > >                                                                        ...
> > > > >                                                                        local_irq_disable();
> > > > > smp_call_function_single(CPU1, func, wait = 1) {                      ...
> > > > >        ...                                                             ...
> > > > >        arch_send_call_function_single_ipi(CPU1);                       ...
> > > > >                                                \                       ...
> > > > >                                                 \                      newidle_balance() {
> > > > >                                                  \                             ...
> > > > >                                              /* Delay */                       ...
> > > > >                                                    \                   }
> > > > >                                                     \                  ...
> > > > >                                                      \-------------->  local_irq_enable();
> > > > >                                                                        /* Processes the IPI */
> > > > > --
> > > > > 
> > > > > 
> > > > > Skipping newidle_balance()
> > > > > ==========================
> > > > > 
> > > > > In an earlier attempt to solve the challenge of the long IRQ disabled
> > > > > section, newidle_balance() was skipped when a CPU waking up from idle
> > > > > was found to have no runnable tasks, and was transitioning back to
> > > > > idle [2]. Tim [3] and David [4] had pointed out that newidle_balance()
> > > > > may be viable for CPUs that are idling with tick enabled, where the
> > > > > newidle_balance() has the opportunity to pull tasks onto the idle CPU.
> > > > 
> > > > I don't think we should be relying on this in any way shape or form.
> > > > NOHZ can kill that tick at any time.
> > > > 
> > > > Also, semantically, calling newidle from the idle thread is just daft.
> > > > You're really not newly idle in that case.
> > > > 
> > > > > Vincent [5] pointed out a case where the idle load kick will fail to
> > > > > run on an idle CPU since the IPI handler launching the ILB will check
> > > > > for need_resched(). In such cases, the idle CPU relies on
> > > > > newidle_balance() to pull tasks towards itself.
> > > > 
> > > > Is this the need_resched() in _nohz_idle_balance() ? Should we change
> > > > this to 'need_resched() && (rq->nr_running || rq->ttwu_pending)' or
> > > > something long those lines?
> > > 
> > > It's not only this but also in do_idle() as well which exits the loop
> > > to look for tasks to schedule
> > > 
> > > > 
> > > > I mean, it's fairly trivial to figure out if there really is going to be
> > > > work there.
> > > > 
> > > > > Using an alternate flag instead of NEED_RESCHED to indicate a pending
> > > > > IPI was suggested as the correct approach to solve this problem on the
> > > > > same thread.
> > > > 
> > > > So adding per-arch changes for this seems like something we shouldn't
> > > > unless there really is no other sane options.
> > > > 
> > > > That is, I really think we should start with something like the below
> > > > and then fix any fallout from that.
> > > 
> > > The main problem is that need_resched becomes somewhat meaningless
> > > because it doesn't  only mean "I need to resched a task" and we have
> > > to add more tests around even for those not using polling
> > > 
> > > > 
> > > > diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> > > > index 0935f9d4bb7b..cfa45338ae97 100644
> > > > --- a/kernel/sched/core.c
> > > > +++ b/kernel/sched/core.c
> > > > @@ -5799,7 +5800,7 @@ static inline struct task_struct *
> > > >   __pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
> > > >   {
> > > >          const struct sched_class *class;
> > > > -       struct task_struct *p;
> > > > +       struct task_struct *p = NULL;
> > > > 
> > > >          /*
> > > >           * Optimization: we know that if all tasks are in the fair class we can
> > > > @@ -5810,9 +5811,11 @@ __pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
> > > >          if (likely(!sched_class_above(prev->sched_class, &fair_sched_class) &&
> > > >                     rq->nr_running == rq->cfs.h_nr_running)) {
> > > > 
> > > > -               p = pick_next_task_fair(rq, prev, rf);
> > > > -               if (unlikely(p == RETRY_TASK))
> > > > -                       goto restart;
> > > > +               if (rq->nr_running) {
> > > 
> > > How do you make the diff between a spurious need_resched() because of
> > > polling and a cpu becoming idle ? isn't rq->nr_running null in both
> > > cases ?
> > > In the later case, we need to call sched_balance_newidle() but not in the former
> > > 
> > 
> > Not sure if I understand correctly, if the goal of smp_call_function_single() is to
> > kick the idle CPU and do not force it to launch the schedule()->sched_balance_newidle(),
> > can we set the _TIF_POLLING_NRFLAG rather than _TIF_NEED_RESCHED in set_nr_if_polling()?
> > I think writing any value to the monitor address would wakeup the idle CPU. And _TIF_POLLING_NRFLAG
> > will be cleared once that idle CPU exit the idle loop, so we don't introduce arch-wide flag.
> Although this might work for MWAIT, there is no way for the generic idle
> path to know if there is a pending interrupt within a TIF_POLLING_NRFLAG
> section. do_idle() sets TIF_POLLING_NRFLAG and relies on a bunch of
> need_resched() checks along the way to bail early until finally doing a
> current_clr_polling_and_test() before handing off to the cpuidle driver
> in call_cpuidle(). I believe this section will necessarily need the sender
> to indicate a pending interrupt via TIF_NEED_RESCHED flag to enable the
> early bail out before going into the cpuidle driver since this case cannot
> be considered the same as a break from MWAIT.
>

I see, this is a good point. So you mean with only TIF_POLLING_NRFLAG there is
possibility that the 'ipi kick CPU out of idle' is lost after the CPU enters
do_idle() and before finally entering the idle state. While setting _TIF_NEED_RESCHED
could help the do_idle() loop to detect pending request easier. BTW, before the
commit b2a02fc43a1f ("smp: Optimize send_call_function_single_ipi()"), the
lost of ipi after entering do_idle() and before entering driver idle state
is also possible, right(the local irq is disabled)?
 
> On x86, there seems to be a possibility of missing an interrupt if
> someone writes _TIF_POLLING_NRFLAG to thread info between the target
> executing MONTOR and MWAIT. AMD64 Architecture Programmer’s Manual
> Volume 3: "General-Purpose and System Instructions", Chapter 4. "System
> Instruction Reference", section "MWAIT" carries the following note in
> the coding requirements:
> 
> "MWAIT must be conditionally executed only if the awaited store has not
> already occurred. (This prevents a race condition between the MONITOR
> instruction arming the monitoring hardware and the store intended to
> trigger the monitoring hardware.)"
> 
> There exists a similar note in the "Example" section for "MWAIT" in
> Intel 64 and IA-32 Architectures Software Developer’s Manual, Vol 2B
> Chapter 4.3 "Instructions (M-U)"
> 

Thanks for the explaination of this race condition in detail.

thanks,
Chenyu
K Prateek Nayak June 18, 2024, 6:33 p.m. UTC | #13
Hello Chenyu,

On 6/18/2024 1:19 PM, Chen Yu wrote:
> [..snip..]
>>>>>
>>>>>> Vincent [5] pointed out a case where the idle load kick will fail to
>>>>>> run on an idle CPU since the IPI handler launching the ILB will check
>>>>>> for need_resched(). In such cases, the idle CPU relies on
>>>>>> newidle_balance() to pull tasks towards itself.
>>>>>
>>>>> Is this the need_resched() in _nohz_idle_balance() ? Should we change
>>>>> this to 'need_resched() && (rq->nr_running || rq->ttwu_pending)' or
>>>>> something long those lines?
>>>>
>>>> It's not only this but also in do_idle() as well which exits the loop
>>>> to look for tasks to schedule
>>>>
>>>>>
>>>>> I mean, it's fairly trivial to figure out if there really is going to be
>>>>> work there.
>>>>>
>>>>>> Using an alternate flag instead of NEED_RESCHED to indicate a pending
>>>>>> IPI was suggested as the correct approach to solve this problem on the
>>>>>> same thread.
>>>>>
>>>>> So adding per-arch changes for this seems like something we shouldn't
>>>>> unless there really is no other sane options.
>>>>>
>>>>> That is, I really think we should start with something like the below
>>>>> and then fix any fallout from that.
>>>>
>>>> The main problem is that need_resched becomes somewhat meaningless
>>>> because it doesn't  only mean "I need to resched a task" and we have
>>>> to add more tests around even for those not using polling
>>>>
>>>>>
>>>>> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
>>>>> index 0935f9d4bb7b..cfa45338ae97 100644
>>>>> --- a/kernel/sched/core.c
>>>>> +++ b/kernel/sched/core.c
>>>>> @@ -5799,7 +5800,7 @@ static inline struct task_struct *
>>>>>    __pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
>>>>>    {
>>>>>           const struct sched_class *class;
>>>>> -       struct task_struct *p;
>>>>> +       struct task_struct *p = NULL;
>>>>>
>>>>>           /*
>>>>>            * Optimization: we know that if all tasks are in the fair class we can
>>>>> @@ -5810,9 +5811,11 @@ __pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
>>>>>           if (likely(!sched_class_above(prev->sched_class, &fair_sched_class) &&
>>>>>                      rq->nr_running == rq->cfs.h_nr_running)) {
>>>>>
>>>>> -               p = pick_next_task_fair(rq, prev, rf);
>>>>> -               if (unlikely(p == RETRY_TASK))
>>>>> -                       goto restart;
>>>>> +               if (rq->nr_running) {
>>>>
>>>> How do you make the diff between a spurious need_resched() because of
>>>> polling and a cpu becoming idle ? isn't rq->nr_running null in both
>>>> cases ?
>>>> In the later case, we need to call sched_balance_newidle() but not in the former
>>>>
>>>
>>> Not sure if I understand correctly, if the goal of smp_call_function_single() is to
>>> kick the idle CPU and do not force it to launch the schedule()->sched_balance_newidle(),
>>> can we set the _TIF_POLLING_NRFLAG rather than _TIF_NEED_RESCHED in set_nr_if_polling()?
>>> I think writing any value to the monitor address would wakeup the idle CPU. And _TIF_POLLING_NRFLAG
>>> will be cleared once that idle CPU exit the idle loop, so we don't introduce arch-wide flag.
>> Although this might work for MWAIT, there is no way for the generic idle
>> path to know if there is a pending interrupt within a TIF_POLLING_NRFLAG
>> section. do_idle() sets TIF_POLLING_NRFLAG and relies on a bunch of
>> need_resched() checks along the way to bail early until finally doing a
>> current_clr_polling_and_test() before handing off to the cpuidle driver
>> in call_cpuidle(). I believe this section will necessarily need the sender
>> to indicate a pending interrupt via TIF_NEED_RESCHED flag to enable the
>> early bail out before going into the cpuidle driver since this case cannot
>> be considered the same as a break from MWAIT.
>>
> 
> I see, this is a good point. So you mean with only TIF_POLLING_NRFLAG there is
> possibility that the 'ipi kick CPU out of idle' is lost after the CPU enters
> do_idle() and before finally entering the idle state. While setting _TIF_NEED_RESCHED
> could help the do_idle() loop to detect pending request easier.

Yup, that is correct.

> BTW, before the
> commit b2a02fc43a1f ("smp: Optimize send_call_function_single_ipi()"), the
> lost of ipi after entering do_idle() and before entering driver idle state
> is also possible, right(the local irq is disabled)?

 From what I understand, the IPI remains pending until the interrupts
are enabled again. Before the optimization, the interrupts would be
disabled all the way until the instruction that is used to put the CPU
to sleep which is what __sti_mwait() and native_safe_halt() does. The
CPU would have received the IPI then and broke out of idle before
Peter's optimization went in. There is an elaborate comment on this in
do_idle() function above the call to local_irq_disable(). In  commit
edc8fc01f608 ("x86: Fix CPUIDLE_FLAG_IRQ_ENABLE leaking timer
reprogram") Peter describes a case of actually missing the break from
an interrupt as the driver enabled interrupts much earlier than
executing the sleep instruction.

Since the CPU was in TIF_POLLING_NRFLAG state, one could simply get away
by setting TIF_NEED_RESCHED and not sending an actual IPI which the
need_resched() checks in the idle path would catch and the
flush_smp_call_function_queue() on the exit path would have serviced the
call function.

MWAIT with Interrupt Break extension (CPUID 0x5 ECX[IBE]) can break out
on pending interrupts even if interrupts are disabled  which is why
"mwait_idle_with_hints()" now checks "ecx" to choose between "__mwait()"
and "__mwait_sti()". The APM describes the extension to "allows
interrupts to wake MWAIT, even when eFLAGS.IF = 0". (Vol. 3.
"General-Purpose and System Instructions", Chapter 4. "System Instruction
Reference", Section "MWAIT")

I do hope someone corrects me if I'm wrong :)

>   
>> On x86, there seems to be a possibility of missing an interrupt if
>> someone writes _TIF_POLLING_NRFLAG to thread info between the target
>> executing MONTOR and MWAIT. AMD64 Architecture Programmer’s Manual
>> Volume 3: "General-Purpose and System Instructions", Chapter 4. "System
>> Instruction Reference", section "MWAIT" carries the following note in
>> the coding requirements:
>>
>> "MWAIT must be conditionally executed only if the awaited store has not
>> already occurred. (This prevents a race condition between the MONITOR
>> instruction arming the monitoring hardware and the store intended to
>> trigger the monitoring hardware.)"
>>
>> There exists a similar note in the "Example" section for "MWAIT" in
>> Intel 64 and IA-32 Architectures Software Developer’s Manual, Vol 2B
>> Chapter 4.3 "Instructions (M-U)"
>>
> 
> Thanks for the explaination of this race condition in detail.
> 
> thanks,
> Chenyu
Chen Yu June 20, 2024, 7:30 a.m. UTC | #14
On 2024-06-19 at 00:03:30 +0530, K Prateek Nayak wrote:
> Hello Chenyu,
> 
> On 6/18/2024 1:19 PM, Chen Yu wrote:
> > [..snip..]
> > > > > > 
> > > > > > > Vincent [5] pointed out a case where the idle load kick will fail to
> > > > > > > run on an idle CPU since the IPI handler launching the ILB will check
> > > > > > > for need_resched(). In such cases, the idle CPU relies on
> > > > > > > newidle_balance() to pull tasks towards itself.
> > > > > > 
> > > > > > Is this the need_resched() in _nohz_idle_balance() ? Should we change
> > > > > > this to 'need_resched() && (rq->nr_running || rq->ttwu_pending)' or
> > > > > > something long those lines?
> > > > > 
> > > > > It's not only this but also in do_idle() as well which exits the loop
> > > > > to look for tasks to schedule
> > > > > 
> > > > > > 
> > > > > > I mean, it's fairly trivial to figure out if there really is going to be
> > > > > > work there.
> > > > > > 
> > > > > > > Using an alternate flag instead of NEED_RESCHED to indicate a pending
> > > > > > > IPI was suggested as the correct approach to solve this problem on the
> > > > > > > same thread.
> > > > > > 
> > > > > > So adding per-arch changes for this seems like something we shouldn't
> > > > > > unless there really is no other sane options.
> > > > > > 
> > > > > > That is, I really think we should start with something like the below
> > > > > > and then fix any fallout from that.
> > > > > 
> > > > > The main problem is that need_resched becomes somewhat meaningless
> > > > > because it doesn't  only mean "I need to resched a task" and we have
> > > > > to add more tests around even for those not using polling
> > > > > 
> > > > > > 
> > > > > > diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> > > > > > index 0935f9d4bb7b..cfa45338ae97 100644
> > > > > > --- a/kernel/sched/core.c
> > > > > > +++ b/kernel/sched/core.c
> > > > > > @@ -5799,7 +5800,7 @@ static inline struct task_struct *
> > > > > >    __pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
> > > > > >    {
> > > > > >           const struct sched_class *class;
> > > > > > -       struct task_struct *p;
> > > > > > +       struct task_struct *p = NULL;
> > > > > > 
> > > > > >           /*
> > > > > >            * Optimization: we know that if all tasks are in the fair class we can
> > > > > > @@ -5810,9 +5811,11 @@ __pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
> > > > > >           if (likely(!sched_class_above(prev->sched_class, &fair_sched_class) &&
> > > > > >                      rq->nr_running == rq->cfs.h_nr_running)) {
> > > > > > 
> > > > > > -               p = pick_next_task_fair(rq, prev, rf);
> > > > > > -               if (unlikely(p == RETRY_TASK))
> > > > > > -                       goto restart;
> > > > > > +               if (rq->nr_running) {
> > > > > 
> > > > > How do you make the diff between a spurious need_resched() because of
> > > > > polling and a cpu becoming idle ? isn't rq->nr_running null in both
> > > > > cases ?
> > > > > In the later case, we need to call sched_balance_newidle() but not in the former
> > > > > 
> > > > 
> > > > Not sure if I understand correctly, if the goal of smp_call_function_single() is to
> > > > kick the idle CPU and do not force it to launch the schedule()->sched_balance_newidle(),
> > > > can we set the _TIF_POLLING_NRFLAG rather than _TIF_NEED_RESCHED in set_nr_if_polling()?
> > > > I think writing any value to the monitor address would wakeup the idle CPU. And _TIF_POLLING_NRFLAG
> > > > will be cleared once that idle CPU exit the idle loop, so we don't introduce arch-wide flag.
> > > Although this might work for MWAIT, there is no way for the generic idle
> > > path to know if there is a pending interrupt within a TIF_POLLING_NRFLAG
> > > section. do_idle() sets TIF_POLLING_NRFLAG and relies on a bunch of
> > > need_resched() checks along the way to bail early until finally doing a
> > > current_clr_polling_and_test() before handing off to the cpuidle driver
> > > in call_cpuidle(). I believe this section will necessarily need the sender
> > > to indicate a pending interrupt via TIF_NEED_RESCHED flag to enable the
> > > early bail out before going into the cpuidle driver since this case cannot
> > > be considered the same as a break from MWAIT.
> > > 
> > 
> > I see, this is a good point. So you mean with only TIF_POLLING_NRFLAG there is
> > possibility that the 'ipi kick CPU out of idle' is lost after the CPU enters
> > do_idle() and before finally entering the idle state. While setting _TIF_NEED_RESCHED
> > could help the do_idle() loop to detect pending request easier.
> 
> Yup, that is correct.
> 
> > BTW, before the
> > commit b2a02fc43a1f ("smp: Optimize send_call_function_single_ipi()"), the
> > lost of ipi after entering do_idle() and before entering driver idle state
> > is also possible, right(the local irq is disabled)?
> 
> From what I understand, the IPI remains pending until the interrupts
> are enabled again. Before the optimization, the interrupts would be
> disabled all the way until the instruction that is used to put the CPU
> to sleep which is what __sti_mwait() and native_safe_halt() does. The
> CPU would have received the IPI then and broke out of idle before
> Peter's optimization went in.

I see, once local irq is enabled, the pending ipi will be served.

> There is an elaborate comment on this in
> do_idle() function above the call to local_irq_disable(). In  commit
> edc8fc01f608 ("x86: Fix CPUIDLE_FLAG_IRQ_ENABLE leaking timer
> reprogram") Peter describes a case of actually missing the break from
> an interrupt as the driver enabled interrupts much earlier than
> executing the sleep instruction.
>

Yup, the commit edc8fc01f608 deals with delay of the timer handling. If
a timer queues the callback after local irq enabled and before mwait,
the long sleep time after mwait might delay the handling of the callback.

> Since the CPU was in TIF_POLLING_NRFLAG state, one could simply get away
> by setting TIF_NEED_RESCHED and not sending an actual IPI which the
> need_resched() checks in the idle path would catch and the
> flush_smp_call_function_queue() on the exit path would have serviced the
> call function.
> 
> MWAIT with Interrupt Break extension (CPUID 0x5 ECX[IBE]) can break out
> on pending interrupts even if interrupts are disabled  which is why
> "mwait_idle_with_hints()" now checks "ecx" to choose between "__mwait()"
> and "__mwait_sti()". The APM describes the extension to "allows
> interrupts to wake MWAIT, even when eFLAGS.IF = 0". (Vol. 3.
> "General-Purpose and System Instructions", Chapter 4. "System Instruction
> Reference", Section "MWAIT")
> 
> I do hope someone corrects me if I'm wrong :)
>

You are right, and thanks for the description.

thanks,
Chenyu
diff mbox

Patch

diff --git a/kernel/sched/idle.c b/kernel/sched/idle.c
index 31231925f1ec..735184d98c0f 100644
--- a/kernel/sched/idle.c
+++ b/kernel/sched/idle.c
@@ -332,11 +332,6 @@  static void do_idle(void)
	 */
	smp_mb__after_atomic();
 
-	/*
-	 * RCU relies on this call to be done outside of an RCU read-side
-	 * critical section.
-	 */
-	flush_smp_call_function_queue();
	schedule_idle();
 
	if (unlikely(klp_patch_pending(current)))
diff --git a/kernel/smp.c b/kernel/smp.c
index f085ebcdf9e7..2ff100c41885 100644
--- a/kernel/smp.c
+++ b/kernel/smp.c
@@ -111,11 +111,9 @@  void __init call_function_init(void)
 static __always_inline void
 send_call_function_single_ipi(int cpu)
 {
-	if (call_function_single_prep_ipi(cpu)) {
-		trace_ipi_send_cpu(cpu, _RET_IP_,
-				   generic_smp_call_function_single_interrupt);
-		arch_send_call_function_single_ipi(cpu);
-	}
+	trace_ipi_send_cpu(cpu, _RET_IP_,
+			   generic_smp_call_function_single_interrupt);
+	arch_send_call_function_single_ipi(cpu);
 }
 
 static __always_inline void