lkml.org 
[lkml]   [2023]   [Nov]   [8]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    SubjectRe: [RFC PATCH 00/86] Make the kernel preemptible
    From
    On 07.11.23 22:56, Ankur Arora wrote:
    > Hi,
    >
    > We have two models of preemption: voluntary and full (and RT which is
    > a fuller form of full preemption.) In this series -- which is based
    > on Thomas' PoC (see [1]), we try to unify the two by letting the
    > scheduler enforce policy for the voluntary preemption models as well.
    >
    > (Note that this is about preemption when executing in the kernel.
    > Userspace is always preemptible.)
    >
    > Background
    > ==
    >
    > Why?: both of these preemption mechanisms are almost entirely disjoint.
    > There are four main sets of preemption points in the kernel:
    >
    > 1. return to user
    > 2. explicit preemption points (cond_resched() and its ilk)
    > 3. return to kernel (tick/IPI/irq at irqexit)
    > 4. end of non-preemptible sections at (preempt_count() == preempt_offset)
    >
    > Voluntary preemption uses mechanisms 1 and 2. Full preemption
    > uses 1, 3 and 4. In addition both use cond_resched_{rcu,lock,rwlock*}
    > which can be all things to all people because they internally
    > contain 2, and 4.
    >
    > Now since there's no ideal placement of explicit preemption points,
    > they tend to be randomly spread over code and accumulate over time,
    > as they are are added when latency problems are seen. Plus fear of
    > regressions makes them difficult to remove.
    > (Presumably, asymptotically they would spead out evenly across the
    > instruction stream!)
    >
    > In voluntary models, the scheduler's job is to match the demand
    > side of preemption points (a task that needs to be scheduled) with
    > the supply side (a task which calls cond_resched().)
    >
    > Full preemption models track preemption count so the scheduler can
    > always knows if it is safe to preempt and can drive preemption
    > itself (ex. via dynamic preemption points in 3.)
    >
    > Design
    > ==
    >
    > As Thomas outlines in [1], to unify the preemption models we
    > want to: always have the preempt_count enabled and allow the scheduler
    > to drive preemption policy based on the model in effect.
    >
    > Policies:
    >
    > - preemption=none: run to completion
    > - preemption=voluntary: run to completion, unless a task of higher
    > sched-class awaits
    > - preemption=full: optimized for low-latency. Preempt whenever a higher
    > priority task awaits.
    >
    > To do this add a new flag, TIF_NEED_RESCHED_LAZY which allows the
    > scheduler to mark that a reschedule is needed, but is deferred until
    > the task finishes executing in the kernel -- voluntary preemption
    > as it were.
    >
    > The TIF_NEED_RESCHED flag is evaluated at all three of the preemption
    > points. TIF_NEED_RESCHED_LAZY only needs to be evaluated at ret-to-user.
    >
    > ret-to-user ret-to-kernel preempt_count()
    > none Y N N
    > voluntary Y Y Y
    > full Y Y Y
    >
    >
    > There's just one remaining issue: now that explicit preemption points are
    > gone, processes that spread a long time in the kernel have no way to give
    > up the CPU.
    >
    > For full preemption, that is a non-issue as we always use TIF_NEED_RESCHED.
    >
    > For none/voluntary preemption, we handle that by upgrading to TIF_NEED_RESCHED
    > if a task marked TIF_NEED_RESCHED_LAZY hasn't preempted away by the next tick.
    > (This would cause preemption either at ret-to-kernel, or if the task is in
    > a non-preemptible section, when it exits that section.)
    >
    > Arguably this provides for much more consistent maximum latency (~2 tick
    > lengths + length of non-preemptible section) as compared to the old model
    > where the maximum latency depended on the dynamic distribution of
    > cond_resched() points.
    >
    > (As a bonus it handles code that is preemptible but cannot call cond_resched()
    > completely trivially: ex. long running Xen hypercalls, or this series
    > which started this discussion:
    > https://lore.kernel.org/all/20230830184958.2333078-8-ankur.a.arora@oracle.com/)
    >
    >
    > Status
    > ==
    >
    > What works:
    > - The system seems to keep ticking over with the normal scheduling policies
    > (SCHED_OTHER). The support for the realtime policies is somewhat more
    > half baked.)
    > - The basic performance numbers seem pretty close to 6.6-rc7 baseline
    >
    > What's broken:
    > - ARCH_NO_PREEMPT (See patch-45 "preempt: ARCH_NO_PREEMPT only preempts
    > lazily")
    > - Non-x86 architectures. It's trivial to support other archs (only need
    > to add TIF_NEED_RESCHED_LAZY) but wanted to hold off until I got some
    > comments on the series.
    > (From some testing on arm64, didn't find any surprises.)
    > - livepatch: livepatch depends on using _cond_resched() to provide
    > low-latency patching. That is obviously difficult with cond_resched()
    > gone. We could get a similar effect by using a static_key in
    > preempt_enable() but at least with inline locks, that might be end
    > up bloating the kernel quite a bit.
    > - Documentation/ and comments mention cond_resched()
    > - ftrace support for need-resched-lazy is incomplete
    >
    > What needs more discussion:
    > - Should cond_resched_lock() etc be scheduling out for TIF_NEED_RESCHED
    > only or both TIF_NEED_RESCHED_LAZY as well? (See patch 35 "thread_info:
    > change to tif_need_resched(resched_t)")
    > - Tracking whether a task in userspace or in the kernel (See patch-40
    > "context_tracking: add ct_state_cpu()")
    > - The right model for preempt=voluntary. (See patch 44 "sched: voluntary
    > preemption")
    >
    >
    > Performance
    > ==
    >
    > Expectation:
    >
    > * perf sched bench pipe
    >
    > preemption full none
    >
    > 6.6-rc7 6.68 +- 0.10 6.69 +- 0.07
    > +series 6.69 +- 0.12 6.67 +- 0.10
    >
    > This is rescheduling out of idle which should and does perform identically.
    >
    > * schbench, preempt=none
    >
    > * 1 group, 16 threads each
    >
    > 6.6-rc7 +series
    > (usecs) (usecs)
    > 50.0th: 6 6
    > 90.0th: 8 7
    > 99.0th: 11 11
    > 99.9th: 15 14
    >
    > * 8 groups, 16 threads each
    >
    > 6.6-rc7 +series
    > (usecs) (usecs)
    > 50.0th: 6 6
    > 90.0th: 8 8
    > 99.0th: 12 11
    > 99.9th: 20 21
    >
    >
    > * schbench, preempt=full
    >
    > * 1 group, 16 threads each
    >
    > 6.6-rc7 +series
    > (usecs) (usecs)
    > 50.0th: 6 6
    > 90.0th: 8 7
    > 99.0th: 11 11
    > 99.9th: 14 14
    >
    >
    > * 8 groups, 16 threads each
    >
    > 6.6-rc7 +series
    > (usecs) (usecs)
    > 50.0th: 7 7
    > 90.0th: 9 9
    > 99.0th: 12 12
    > 99.9th: 21 22
    >
    >
    > Not much in it either way.
    >
    > * kernbench, preempt=full
    >
    > * half-load (-j 128)
    >
    > 6.6-rc7 +series
    >
    > wall 149.2 +- 27.2 wall 132.8 +- 0.4
    > utime 8097.1 +- 57.4 utime 8088.5 +- 14.1
    > stime 1165.5 +- 9.4 stime 1159.2 +- 1.9
    > %cpu 6337.6 +- 1072.8 %cpu 6959.6 +- 22.8
    > csw 237618 +- 2190.6 %csw 240343 +- 1386.8
    >
    >
    > * optimal-load (-j 1024)
    >
    > 6.6-rc7 +series
    >
    > wall 137.8 +- 0.0 wall 137.7 +- 0.8
    > utime 11115.0 +- 3306.1 utime 11041.7 +- 3235.0
    > stime 1340.0 +- 191.3 stime 1323.1 +- 179.5
    > %cpu 8846.3 +- 2830.6 %cpu 9101.3 +- 2346.7
    > csw 2099910 +- 2040080.0 csw 2068210 +- 2002450.0
    >
    >
    > The preempt=full path should effectively not see any change in
    > behaviour. The optimal-loads are pretty much identical.
    > For the half-load, however, the +series version does much better but that
    > seems to be because of much higher run to run variability in the 6.6-rc7 load.
    >
    > * kernbench, preempt=none
    >
    > * half-load (-j 128)
    >
    > 6.6-rc7 +series
    >
    > wall 134.5 +- 4.2 wall 133.6 +- 2.7
    > utime 8093.3 +- 39.3 utime 8099.0 +- 38.9
    > stime 1175.7 +- 10.6 stime 1169.1 +- 8.4
    > %cpu 6893.3 +- 233.2 %cpu 6936.3 +- 142.8
    > csw 240723 +- 423.0 %csw 173152 +- 1126.8
    >
    >
    > * optimal-load (-j 1024)
    >
    > 6.6-rc7 +series
    >
    > wall 139.2 +- 0.3 wall 138.8 +- 0.2
    > utime 11161.0 +- 3360.4 utime 11061.2 +- 3244.9
    > stime 1357.6 +- 199.3 stime 1366.6 +- 216.3
    > %cpu 9108.8 +- 2431.4 %cpu 9081.0 +- 2351.1
    > csw 2078599 +- 2013320.0 csw 1970610 +- 1969030.0
    >
    >
    > For both of these the wallclock, utime, stime etc are pretty much
    > identical. The one interesting difference is that the number of
    > context switches are fewer. This intuitively makes sense given that
    > we reschedule threads lazily rather than rescheduling if we encounter
    > a cond_resched() and there's a thread wanting to be scheduled.
    >
    > The max-load numbers (not posted here) also behave similarly.
    >
    >
    > Series
    > ==
    >
    > With that, this is how he series is laid out:
    >
    > - Patches 01-30: revert the PREEMPT_DYNAMIC code. Most of the infrastructure
    > used by that is via static_calls() and this is a simpler approach which
    > doesn't need any of that (and does away with cond_resched().)
    >
    > Some of the commits will be resurrected.
    > 089c02ae2771 ("ftrace: Use preemption model accessors for trace header printout")
    > cfe43f478b79 ("preempt/dynamic: Introduce preemption model accessors")
    > 5693fa74f98a ("kcsan: Use preemption model accessors")
    >
    > - Patches 31-45: contain the scheduler changes to do this. Of these
    > the critical ones are:
    > patch 35 "thread_info: change to tif_need_resched(resched_t)"
    > patch 41 "sched: handle resched policy in resched_curr()"
    > patch 43 "sched: enable PREEMPT_COUNT, PREEMPTION for all preemption models"
    > patch 44 "sched: voluntary preemption"
    > (this needs more work to decide when a higher sched-policy task
    > should preempt a lower sched-policy task)
    > patch 45 "preempt: ARCH_NO_PREEMPT only preempts lazily"
    >
    > - Patches 47-50: contain RCU related changes. RCU now works in both
    > PREEMPT_RCU=y and PREEMPT_RCU=n modes with CONFIG_PREEMPTION.
    > (Until now PREEMPTION=y => PREEMPT_RCU)
    >
    > - Patches 51-56,86: contain cond_resched() related cleanups.
    > patch 54 "sched: add cond_resched_stall()" adds a new cond_resched()
    > interface. Pitchforks?
    >
    > - Patches 57-86: remove cond_resched() from the tree.
    >
    >
    > Also at: github.com/terminus/linux preemption-rfc
    >
    >
    > Please review.
    >
    > Thanks
    > Ankur
    >
    > [1] https://lore.kernel.org/lkml/87jzshhexi.ffs@tglx/
    >
    >
    > Ankur Arora (86):
    > Revert "riscv: support PREEMPT_DYNAMIC with static keys"
    > Revert "sched/core: Make sched_dynamic_mutex static"
    > Revert "ftrace: Use preemption model accessors for trace header
    > printout"
    > Revert "preempt/dynamic: Introduce preemption model accessors"
    > Revert "kcsan: Use preemption model accessors"
    > Revert "entry: Fix compile error in
    > dynamic_irqentry_exit_cond_resched()"
    > Revert "livepatch,sched: Add livepatch task switching to
    > cond_resched()"
    > Revert "arm64: Support PREEMPT_DYNAMIC"
    > Revert "sched/preempt: Add PREEMPT_DYNAMIC using static keys"
    > Revert "sched/preempt: Decouple HAVE_PREEMPT_DYNAMIC from
    > GENERIC_ENTRY"
    > Revert "sched/preempt: Simplify irqentry_exit_cond_resched() callers"
    > Revert "sched/preempt: Refactor sched_dynamic_update()"
    > Revert "sched/preempt: Move PREEMPT_DYNAMIC logic later"
    > Revert "preempt/dynamic: Fix setup_preempt_mode() return value"
    > Revert "preempt: Restore preemption model selection configs"
    > Revert "sched: Provide Kconfig support for default dynamic preempt
    > mode"
    > sched/preempt: remove PREEMPT_DYNAMIC from the build version
    > Revert "preempt/dynamic: Fix typo in macro conditional statement"
    > Revert "sched,preempt: Move preempt_dynamic to debug.c"
    > Revert "static_call: Relax static_call_update() function argument
    > type"
    > Revert "sched/core: Use -EINVAL in sched_dynamic_mode()"
    > Revert "sched/core: Stop using magic values in sched_dynamic_mode()"
    > Revert "sched,x86: Allow !PREEMPT_DYNAMIC"
    > Revert "sched: Harden PREEMPT_DYNAMIC"
    > Revert "sched: Add /debug/sched_preempt"
    > Revert "preempt/dynamic: Support dynamic preempt with preempt= boot
    > option"
    > Revert "preempt/dynamic: Provide irqentry_exit_cond_resched() static
    > call"
    > Revert "preempt/dynamic: Provide preempt_schedule[_notrace]() static
    > calls"
    > Revert "preempt/dynamic: Provide cond_resched() and might_resched()
    > static calls"
    > Revert "preempt: Introduce CONFIG_PREEMPT_DYNAMIC"
    > x86/thread_info: add TIF_NEED_RESCHED_LAZY
    > entry: handle TIF_NEED_RESCHED_LAZY
    > entry/kvm: handle TIF_NEED_RESCHED_LAZY
    > thread_info: accessors for TIF_NEED_RESCHED*
    > thread_info: change to tif_need_resched(resched_t)
    > entry: irqentry_exit only preempts TIF_NEED_RESCHED
    > sched: make test_*_tsk_thread_flag() return bool
    > sched: *_tsk_need_resched() now takes resched_t
    > sched: handle lazy resched in set_nr_*_polling()
    > context_tracking: add ct_state_cpu()
    > sched: handle resched policy in resched_curr()
    > sched: force preemption on tick expiration
    > sched: enable PREEMPT_COUNT, PREEMPTION for all preemption models
    > sched: voluntary preemption
    > preempt: ARCH_NO_PREEMPT only preempts lazily
    > tracing: handle lazy resched
    > rcu: select PREEMPT_RCU if PREEMPT
    > rcu: handle quiescent states for PREEMPT_RCU=n
    > osnoise: handle quiescent states directly
    > rcu: TASKS_RCU does not need to depend on PREEMPTION
    > preempt: disallow !PREEMPT_COUNT or !PREEMPTION
    > sched: remove CONFIG_PREEMPTION from *_needbreak()
    > sched: fixup __cond_resched_*()
    > sched: add cond_resched_stall()
    > xarray: add cond_resched_xas_rcu() and cond_resched_xas_lock_irq()
    > xarray: use cond_resched_xas*()
    > coccinelle: script to remove cond_resched()
    > treewide: x86: remove cond_resched()
    > treewide: rcu: remove cond_resched()
    > treewide: torture: remove cond_resched()
    > treewide: bpf: remove cond_resched()
    > treewide: trace: remove cond_resched()
    > treewide: futex: remove cond_resched()
    > treewide: printk: remove cond_resched()
    > treewide: task_work: remove cond_resched()
    > treewide: kernel: remove cond_resched()
    > treewide: kernel: remove cond_reshed()
    > treewide: mm: remove cond_resched()
    > treewide: io_uring: remove cond_resched()
    > treewide: ipc: remove cond_resched()
    > treewide: lib: remove cond_resched()
    > treewide: crypto: remove cond_resched()
    > treewide: security: remove cond_resched()
    > treewide: fs: remove cond_resched()
    > treewide: virt: remove cond_resched()
    > treewide: block: remove cond_resched()
    > treewide: netfilter: remove cond_resched()
    > treewide: net: remove cond_resched()
    > treewide: net: remove cond_resched()
    > treewide: sound: remove cond_resched()
    > treewide: md: remove cond_resched()
    > treewide: mtd: remove cond_resched()
    > treewide: drm: remove cond_resched()
    > treewide: net: remove cond_resched()
    > treewide: drivers: remove cond_resched()
    > sched: remove cond_resched()

    I'm missing the removal of the Xen parts, which were one of the reasons to start
    this whole work (xen_in_preemptible_hcall etc.).


    Juergen
    [unhandled content-type:application/pgp-keys][unhandled content-type:application/pgp-signature]
    \
     
     \ /
      Last update: 2023-11-20 13:52    [W:4.629 / U:0.028 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site