mirror of https://lore.kernel.org/lkml/
 help / color / mirror / Atom feed
* [RFC PATCH 0/3] rwsem: priority boost for holders blocking high-priority waiters
@ 2026-11-19 22:49 Peng Huang
  2026-11-19 22:49 ` [RFC PATCH 1/3] locking/rwsem, sched: track held rwsems and waiter priorities Peng Huang
                   ` (2 more replies)
  0 siblings, 3 replies; 4+ messages in thread
From: Peng Huang @ 2026-11-19 22:49 UTC (permalink / raw)
  To: Peter Zijlstra, Ingo Molnar, Will Deacon, Boqun Feng,
	Waiman Long, Juri Lelli, Vincent Guittot
  Cc: Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
	Valentin Schneider, K Prateek Nayak, linux-kernel, Peng Huang

Hi,

High-priority interactive threads (such as UI/render threads) can stall
for tens to hundreds of milliseconds on shared rw_semaphores like
mm->mmap_lock, inode->i_rwsem, or mapping->i_mmap_rwsem/invalidate_lock
when lower-priority (or SCHED_IDLE) read-owners are preempted on busy
CPUs and block an incoming higher-weight writer. Upstream
CONFIG_SCHED_PROXY_EXEC currently covers mutexes, and out-of-tree rwsem
proxy efforts only track a single write-owner, leaving multi-reader
inversions unaddressed.

This RFC proposes a lightweight priority-inheritance mechanism for CFS
rw_semaphore holders that accelerates stalled readers and writers in
parallel without requiring lock-side reader tracking.

Design rationale
----------------
1. Per-task hold tracking (avoiding lock-side reader lists):
   Because rw_semaphore allows unbounded concurrent readers, storing a
   reader list inside struct rw_semaphore would require dynamic
   allocation or extra locking in the down_read()/up_read() fastpath.
   Instead, each task records up to CONFIG_RWSEM_SCHED_BOOST_SLOTS
   (default 4) rwsem pointers in task_struct under current-only access.
   This supports an unlimited number of concurrent readers per rwsem;
   the slot count only caps simultaneous nested rwsems held by one task.

2. Contended waiter demand (sem->max_waiter_prio):
   Waiters in rwsem_down_{read,write}_slowpath() publish the lowest
   normal prio (i.e. highest nice weight, capped at MAX_RT_PRIO so CFS
   holders never escalate into RT/DL) into sem->max_waiter_prio,
   recalculating without redundant atomic writes as waiters wake/leave.

3. Per-rq runqueue list and parallel boost:
   Runnable CFS tasks holding at least one rwsem are linked onto a
   per-CPU list (rq->held_rwsem_tasks) during enqueue/dequeue/migrate
   under rq_lock, keeping lock/unlock fastpaths list-free. Normal short
   holds never touch rq->held_rwsem_tasks; tasks are only linked if
   preempted, enqueued, or crossing a tick while holding a lock, so tick
   and idle-pull typically exit immediately on an empty list with zero
   iteration or max_waiter_prio lookups. Across wakeup, preemption, tick,
   and idle-balance pull paths, the scheduler checks held locks'
   sem->max_waiter_prio and elevates the holder's effective priority and
   EEVDF weight (preserving static_prio/nice and handling SCHED_IDLE
   separately) down to min(p->prio, max_waiter_prio), restoring cleanly
   on unlock. Runtime/build disablement is provided via
   rwsem_sched_boost=0, CONFIG_RWSEM_SCHED_BOOST_SLOTS=0, or PREEMPT_RT.

4. Model trade-off (Parallel priority spray vs. Proxy Execution):
   Proxy Execution follows task->blocked_on to boost one owner at a
   time on the owner's CPU (entailing cross-CPU proxy migrations and
   requiring a lock-side owner list for readers), while naturally
   propagating transitively across mutex/futex/rwsem chains. By
   contrast, this RFC avoids lock-side reader tracking and lets all
   preempted readers on any CPU boost and drain in parallel once
   contended, at the intentional cost of not propagating transitively
   through mutex/futex chains (e.g. RT -> mutex -> rwsem).

Validation & known trade-offs
-----------------------------
- Included KUnit suite (Patch 3/3, CONFIG_RWSEM_SCHED_BOOST_KUNIT_TEST):
  Reproducible under ARCH=um via kunit.py (10/10 pass incl. SCHED_IDLE
  cap, interleaved unlock, and slot overflow):
  * Preemption inversion (n=3, 4 nice=0 hogs):
    Control mean 1939 ms (max 1970 ms) -> Treatment mean 49 ms (-97.5%)
  * Uncontended fastpath (1,000,000 ops):
    read +2.75 ns/op (21.43 -> 24.18),
    write +1.99 ns/op (20.78 -> 22.77),
    nested2 read +4.31 ns/op (21.20 -> 25.51)
- ARM64 mobile hardware (6.18 backport, asymmetric SMP, user-space
  madvise/mprotect stress reproducer):
  * mmap_lock inversion (nice -10 madvise vs 7 nice 0 mprotect hogs):
    - Unpinned 5-round AB (100 runs): mean 120.22 -> 7.26 ms (-94.0%),
      missed 16ms deadlines 46/100 -> 8/100
    - Mid-cluster pinned 4-round AB/BA (80 runs): mean 281.11 ->
      7.34 ms (-97.4%), max 736.14 -> 50.76 ms, missed 16ms 80/80 -> 4/80
  * Big-core pinned syscall fastpath (big core, 4 rounds x 100k iters):
    madvise 615.8 -> 604.8 ns/op (-1.8%),
    mprotect 857.5 -> 848.5 ns/op (-1.0%)
  * Contended equal-priority non-inversion (4 threads, Mid pinned):
    145.5 -> 162.5 ms (+11.7% throughput trade-off under contention;
    also +10.8% in x86_64 QEMU -smp 4 TCG)
  * Pinned hackbench / pipe ping-pong (Mid+Big):
    hackbench 263.7 -> 243.3 ms (-7.7%),
    pipe 10.81 -> 10.33 us/op (-4.4%)

Request for feedback
--------------------
Before iterating further, feedback is especially welcome on:
- Parallel priority spray (task-slot tracking) vs. extending Proxy
  Execution with lock-side reader tracking, vs. a slowpath/owner-only
  heuristic;
- Using normal prio / nice weight as the demand currency vs. EEVDF
  virtual deadline / lag considerations;
- Struct size impact of adding max_waiter_prio to struct rw_semaphore
  (+8 bytes aligned on 64-bit, 32 -> 40 bytes, embedded in inode/mm);
- Intentional RFC boundaries: 4-slot nested limit per task, boosting
  all concurrent readers equally, idle-pull inspecting only the
  busiest rq (no global CPU scan/cpumask), no cgroup/task_group share
  propagation, and no transitive inheritance across mutex/futex chains.

Per Documentation/process/generated-content.rst: Jetski AI coding
assistance was used for drafting, refactoring discussions, and KUnit /
benchmark verification; all patches and tests have been reviewed and
verified by the author.

Peng Huang (3):
  locking/rwsem, sched: track held rwsems and waiter priorities
  sched: boost rwsem holders with contended high-priority waiters
  locking/rwsem: add KUnit tests for scheduler priority boost

 .../admin-guide/kernel-parameters.txt         |   5 +
 include/linux/rwsem.h                         |  28 +
 include/linux/sched.h                         |  16 +
 init/init_task.c                              |   4 +
 kernel/Kconfig.locks                          |  15 +
 kernel/locking/Makefile                       |   1 +
 kernel/locking/rwsem.c                        | 209 +++++++-
 kernel/locking/rwsem_sched_boost_test.c       | 504 ++++++++++++++++++
 kernel/sched/core.c                           | 211 +++++++-
 kernel/sched/fair.c                           |  51 ++
 kernel/sched/sched.h                          |  70 +++
 kernel/sched/syscalls.c                       |   2 +-
 lib/Kconfig.debug                             |  10 +
 13 files changed, 1101 insertions(+), 25 deletions(-)
 create mode 100644 kernel/locking/rwsem_sched_boost_test.c

-- 
2.56.1.750.gf70dc682cf-goog


^ permalink raw reply	[flat|nested] 4+ messages in thread

end of thread, other threads:[~2026-11-19 22:50 UTC | newest]

Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2026-11-19 22:49 [RFC PATCH 0/3] rwsem: priority boost for holders blocking high-priority waiters Peng Huang
2026-11-19 22:49 ` [RFC PATCH 1/3] locking/rwsem, sched: track held rwsems and waiter priorities Peng Huang
2026-11-19 22:49 ` [RFC PATCH 2/3] sched: boost rwsem holders with contended high-priority waiters Peng Huang
2026-11-19 22:49 ` [RFC PATCH 3/3] locking/rwsem: add KUnit tests for scheduler priority boost Peng Huang

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox

all inboxes | Powered by JetHome®