[PATCH v2 00/35] PREEMPT_AUTO: support lazy rescheduling

Ankur Arora
2024-05-28T00:36:00Z

Hi,

This series adds a new scheduling model PREEMPT_AUTO, which like
PREEMPT_DYNAMIC allows dynamic switching between a none/voluntary/full
preemption model. Unlike, PREEMPT_DYNAMIC, it doesn't depend
on explicit preemption points for the voluntary models.

The series is based on Thomas' original proposal which he outlined
in [1], [2] and in his PoC [3].

v2 mostly reworks v1, with one of the main changes having less
noisy need-resched-lazy related interfaces.
More details in the changelog below.

The v1 of the series is at [4] and the RFC at [5].

Design
==

PREEMPT_AUTO works by always enabling CONFIG_PREEMPTION (and thus
PREEMPT_COUNT). This means that the scheduler can always safely
preempt. (This is identical to CONFIG_PREEMPT.)

Having that, the next step is to make the rescheduling policy dependent
on the chosen scheduling model. Currently, the scheduler uses a single
need-resched bit (TIF_NEED_RESCHED) which it uses to state that a
reschedule is needed.
PREEMPT_AUTO extends this by adding an additional need-resched bit
(TIF_NEED_RESCHED_LAZY) which, with TIF_NEED_RESCHED now allows the
scheduler to express two kinds of rescheduling intent: schedule at
the earliest opportunity (TIF_NEED_RESCHED), or express a need for
rescheduling while allowing the task on the runqueue to run to
timeslice completion (TIF_NEED_RESCHED_LAZY).

The scheduler decides which need-resched bits are chosen based on
the preemption model in use:

TIF_NEED_RESCHED TIF_NEED_RESCHED_LAZY

none never always [*]
voluntary higher sched class other tasks [*]
full always never

[*] some details elided.

The last part of the puzzle is, when does preemption happen, or
alternately stated, when are the need-resched bits checked:

exit-to-user ret-to-kernel preempt_count()

NEED_RESCHED_LAZY Y N N
NEED_RESCHED Y Y Y

Using NEED_RESCHED_LAZY allows for run-to-completion semantics when
none/voluntary preemption policies are in effect. And eager semantics
under full preemption.

In addition, since this is driven purely by the scheduler (not
depending on cond_resched() placement and the like), there is enough
flexibility in the scheduler to cope with edge cases -- ex. a kernel
task not relinquishing CPU under NEED_RESCHED_LAZY can be handled by
simply upgrading to a full NEED_RESCHED which can use more coercive
instruments like resched IPI to induce a context-switch.

Performance
==
The performance in the basic tests (perf bench sched messaging, kernbench,
cyclictest) matches or improves what we see under PREEMPT_DYNAMIC.
(See patches
"sched: support preempt=none under PREEMPT_AUTO"
"sched: support preempt=full under PREEMPT_AUTO"
"sched: handle preempt=voluntary under PREEMPT_AUTO")

For a macro test, a colleague in Oracle's Exadata team tried two
OLTP benchmarks (on a 5.4.17 based Oracle kernel, with the v1 series
backported.)

In both tests the data was cached on remote nodes (cells), and the
database nodes (compute) served client queries, with clients being
local in the first test and remote in the second.

Compute node: Oracle E5, dual socket AMD EPYC 9J14, KVM guest (380 CPUs)
Cells (11 nodes): Oracle E5, dual socket AMD EPYC 9334, 128 CPUs

PREEMPT_VOLUNTARY PREEMPT_AUTO
(preempt=voluntary)
============================== =============================
clients throughput cpu-usage throughput cpu-usage Gain
(tx/min) (utime %/stime %) (tx/min) (utime %/stime %)
------- ---------- ----------------- ---------- ----------------- -------

OLTP 384 9,315,653 25/ 6 9,253,252 25/ 6 -0.7%
benchmark 1536 13,177,565 50/10 13,657,306 50/10 +3.6%
(local clients) 3456 14,063,017 63/12 14,179,706 64/12 +0.8%

OLTP 96 8,973,985 17/ 2 8,924,926 17/ 2 -0.5%
benchmark 384 22,577,254 60/ 8 22,211,419 59/ 8 -1.6%
(remote clients, 2304 25,882,857 82/11 25,536,100 82/11 -1.3%
90/10 RW ratio)

(Both sets of tests have a fair amount of NW traffic since the query
tables etc are cached on the cells. Additionally, the first set,
given the local clients, stress the scheduler a bit more than the
second.)

The comparative performance for both the tests is fairly close,
more or less within a margin of error.

Raghu KT also tested v1 on an AMD Milan (2 node, 256 cpu, 512GB RAM):

"
a) Base kernel (6.7),
b) v1, PREEMPT_AUTO, preempt=voluntary
c) v1, PREEMPT_DYNAMIC, preempt=voluntary
d) v1, PREEMPT_AUTO=y, preempt=voluntary, PREEMPT_RCU = y

Workloads I tested and their %gain,
case b case c case d
NAS +2.7% +1.9% +2.1%
Hashjoin, +0.0% +0.0% +0.0%
Graph500, -6.0% +0.0% +0.0%
XSBench +1.7% +0.0% +1.2%

(Note about the Graph500 numbers at [8].)

Did kernbench etc test from Mel's mmtests suite also. Did not notice
much difference.
"

One case where there is a significant performance drop is on powerpc,
seen running hackbench on a 320 core system (a test on a smaller system is
fine.) In theory there's no reason for this to only happen on powerpc
since most of the code is common, but I haven't been able to reproduce
it on x86 so far.

All in all, I think the tests above show that this scheduling model has legs.
However, the none/voluntary models under PREEMPT_AUTO are conceptually
different enough from the current none/voluntary models that there
likely are workloads where performance would be subpar. That needs more
extensive testing to figure out the weak points.

Series layout
==

Patches 1,2
"sched/core: Move preempt_model_*() helpers from sched.h to preempt.h"
"sched/core: Drop spinlocks on contention iff kernel is preemptible"
condition spin_needbreak() on the dynamic preempt_model_*().
Not really required but a useful bugfix for PREEMPT_DYNAMIC and PREEMPT_AUTO.

Patch 3
"sched: make test_*_tsk_thread_flag() return bool"
is a minor cleanup.

Patch 4,
"preempt: introduce CONFIG_PREEMPT_AUTO"
introduces the new scheduling model.

Patch 5-7,
"thread_info: selector for TIF_NEED_RESCHED[_LAZY]"
"thread_info: define __tif_need_resched(resched_t)"
"sched: define *_tsk_need_resched_lazy() helpers"

introduce new thread_info/task helper interfaces or make changes to
pre-existing ones that will be used in the rest of the series.

Patches 8-11,
"entry: handle lazy rescheduling at user-exit"
"entry/kvm: handle lazy rescheduling at guest-entry"
"entry: irqentry_exit only preempts for TIF_NEED_RESCHED"
"sched: __schedule_loop() doesn't need to check for need_resched_lazy()"

make changes/document the rescheduling points.

Patches 12-13,
"sched: separate PREEMPT_DYNAMIC config logic"
"sched: allow runtime config for PREEMPT_AUTO"

reuse the PREEMPT_DYNAMIC runtime configuration logic.

Patch 14-18,

"rcu: limit PREEMPT_RCU to full preemption under PREEMPT_AUTO"
"rcu: fix header guard for rcu_all_qs()"
"preempt,rcu: warn on PREEMPT_RCU=n, preempt=full"
"rcu: handle quiescent states for PREEMPT_RCU=n, PREEMPT_COUNT=y"
"rcu: force context-switch for PREEMPT_RCU=n, PREEMPT_COUNT=y"

add changes needed for RCU.

Patch 19-20,
"x86/thread_info: define TIF_NEED_RESCHED_LAZY"
"powerpc: add support for PREEMPT_AUTO"

adds x86, powerpc support.

Patches 21-24,
"sched: prepare for lazy rescheduling in resched_curr()"
"sched: default preemption policy for PREEMPT_AUTO"
"sched: handle idle preemption for PREEMPT_AUTO"
"sched: schedule eagerly in resched_cpu()"

are preparatory patches for adding PREEMPT_AUTO. Among other things
they add the default need-resched policy for !PREEMPT_AUTO,
PREEMPT_AUTO, and the idle task.

Patches 25-26,
"sched/fair: refactor update_curr(), entity_tick()",
"sched/fair: handle tick expiry under lazy preemption"

handle the 'hog' problem, where a kernel task does not voluntarily
schedule out.

And, finally patches 27-29,
"sched: support preempt=none under PREEMPT_AUTO"
"sched: support preempt=full under PREEMPT_AUTO"
"sched: handle preempt=voluntary under PREEMPT_AUTO"

add support for the three preemption models.

Patch 30-33,
"sched: latency warn for TIF_NEED_RESCHED_LAZY",
"tracing: support lazy resched",
"Documentation: tracing: add TIF_NEED_RESCHED_LAZY",
"osnoise: handle quiescent states for PREEMPT_RCU=n, PREEMPTION=y"

handles remaining bits and pieces to do with TIF_NEED_RESCHED_LAZY.

And, finally patches 34-35

"kconfig: decompose ARCH_NO_PREEMPT"
"arch: decompose ARCH_NO_PREEMPT"

decompose ARCH_NO_PREEMPT which might make it easier to support
CONFIG_PREEMPTION on some architectures.

Changelog
==
v2: rebased to v6.9, addreses review comments, folds some other patches.

- the lazy interfaces are less noisy now: the current interfaces stay
unchanged so non-scheduler code doesn't need to change.
This also means that the lazy preemption becomes a scheduler detail
which works well with the core idea of lazy scheduling.
(Mark Rutland, Thomas Gleixner)

- preempt=none model now respects the leftmost deadline (Juri Lelli)
- Add need-resched flag combination state in tracing headers (Steven Rostedt)
- Decompose ARCH_NO_PREEMPT
- Changes for RCU (and TASKS_RCU) will go in separately [6]

- spin_needbreak() should be conditioned on preempt_model_*() at
runtime (patches from Sean Christopherson [7])
- powerpc support from Shrikanth Hegde

RFC:
- Addresses review comments and is generally a more focused
version of the RFC.
- Lots of code reorganization.
- Bugfixes all over.
- need_resched() now only checks for TIF_NEED_RESCHED instead
of TIF_NEED_RESCHED|TIF_NEED_RESCHED_LAZY.
- set_nr_if_polling() now does not check for TIF_NEED_RESCHED_LAZY.
- Tighten idle related checks.
- RCU changes to force context-switches when a quiescent state is
urgently needed.
- Does not break live-patching anymore

Also at: github.com/terminus/linux preempt-v2

Please review.

Thanks
Ankur

Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Raghavendra K T <raghavendra.kt@amd.com>
Cc: Shrikanth Hegde <sshegde@linux.ibm.com>

[1] https://lore.kernel.org/lkml/87cyyfxd4k.ffs@tglx/
[2] https://lore.kernel.org/lkml/87led2wdj0.ffs@tglx/
[3] https://lore.kernel.org/lkml/87jzshhexi.ffs@tglx/
[4] https://lore.kernel.org/lkml/20240213055554.1802415-1-ankur.a.arora@oracle.com/
[5] https://lore.kernel.org/lkml/20231107215742.363031-1-ankur.a.arora@oracle.com/
[6] https://lore.kernel.org/lkml/20240507093530.3043-1-urezki@gmail.com/
[7] https://lore.kernel.org/lkml/20240312193911.1796717-1-seanjc@google.com/
[8] https://lore.kernel.org/lkml/af122806-8325-4302-991f-9c0dc1857bfe@amd.com/
[9] https://lore.kernel.org/lkml/17cc54c4-2e75-4964-9155-84db081ce209@linux.ibm.com/

Ankur Arora (32):
sched: make test_*_tsk_thread_flag() return bool
preempt: introduce CONFIG_PREEMPT_AUTO
thread_info: selector for TIF_NEED_RESCHED[_LAZY]
thread_info: define __tif_need_resched(resched_t)
sched: define *_tsk_need_resched_lazy() helpers
entry: handle lazy rescheduling at user-exit
entry/kvm: handle lazy rescheduling at guest-entry
entry: irqentry_exit only preempts for TIF_NEED_RESCHED
sched: __schedule_loop() doesn't need to check for need_resched_lazy()
sched: separate PREEMPT_DYNAMIC config logic
sched: allow runtime config for PREEMPT_AUTO
rcu: limit PREEMPT_RCU to full preemption under PREEMPT_AUTO
rcu: fix header guard for rcu_all_qs()
preempt,rcu: warn on PREEMPT_RCU=n, preempt=full
rcu: handle quiescent states for PREEMPT_RCU=n, PREEMPT_COUNT=y
rcu: force context-switch for PREEMPT_RCU=n, PREEMPT_COUNT=y
x86/thread_info: define TIF_NEED_RESCHED_LAZY
sched: prepare for lazy rescheduling in resched_curr()
sched: default preemption policy for PREEMPT_AUTO
sched: handle idle preemption for PREEMPT_AUTO
sched: schedule eagerly in resched_cpu()
sched/fair: refactor update_curr(), entity_tick()
sched/fair: handle tick expiry under lazy preemption
sched: support preempt=none under PREEMPT_AUTO
sched: support preempt=full under PREEMPT_AUTO
sched: handle preempt=voluntary under PREEMPT_AUTO
sched: latency warn for TIF_NEED_RESCHED_LAZY
tracing: support lazy resched
Documentation: tracing: add TIF_NEED_RESCHED_LAZY
osnoise: handle quiescent states for PREEMPT_RCU=n, PREEMPTION=y
kconfig: decompose ARCH_NO_PREEMPT
arch: decompose ARCH_NO_PREEMPT

Sean Christopherson (2):
sched/core: Move preempt_model_*() helpers from sched.h to preempt.h
sched/core: Drop spinlocks on contention iff kernel is preemptible

Shrikanth Hegde (1):
powerpc: add support for PREEMPT_AUTO

.../admin-guide/kernel-parameters.txt | 5 +-
Documentation/trace/ftrace.rst | 6 +-
arch/Kconfig | 7 +
arch/alpha/Kconfig | 3 +-
arch/hexagon/Kconfig | 3 +-
arch/m68k/Kconfig | 3 +-
arch/powerpc/Kconfig | 1 +
arch/powerpc/include/asm/thread_info.h | 5 +-
arch/powerpc/kernel/interrupt.c | 5 +-
arch/um/Kconfig | 3 +-
arch/x86/Kconfig | 1 +
arch/x86/include/asm/thread_info.h | 6 +-
include/linux/entry-common.h | 2 +-
include/linux/entry-kvm.h | 2 +-
include/linux/preempt.h | 43 ++-
include/linux/rcutree.h | 2 +-
include/linux/sched.h | 101 +++---
include/linux/spinlock.h | 14 +-
include/linux/thread_info.h | 71 +++-
include/linux/trace_events.h | 6 +-
init/Makefile | 1 +
kernel/Kconfig.preempt | 37 ++-
kernel/entry/common.c | 16 +-
kernel/entry/kvm.c | 4 +-
kernel/rcu/Kconfig | 2 +-
kernel/rcu/tree.c | 13 +-
kernel/rcu/tree_plugin.h | 11 +-
kernel/sched/core.c | 311 ++++++++++++------
kernel/sched/deadline.c | 9 +-
kernel/sched/debug.c | 13 +-
kernel/sched/fair.c | 56 ++--
kernel/sched/rt.c | 6 +-
kernel/sched/sched.h | 27 +-
kernel/trace/trace.c | 30 +-
kernel/trace/trace_osnoise.c | 22 +-
kernel/trace/trace_output.c | 16 +-
36 files changed, 598 insertions(+), 265 deletions(-)

--
2.31.1