mirror of https://lore.kernel.org/lkml/
 help / color / mirror / Atom feed
From: Peng Huang <penghuang@google.com>
To: Peter Zijlstra <peterz@infradead.org>,
	Ingo Molnar <mingo@redhat.com>,  Will Deacon <will@kernel.org>,
	Boqun Feng <boqun@kernel.org>, Waiman Long <longman@redhat.com>,
	 Juri Lelli <juri.lelli@redhat.com>,
	Vincent Guittot <vincent.guittot@linaro.org>
Cc: Dietmar Eggemann <dietmar.eggemann@arm.com>,
	Steven Rostedt <rostedt@goodmis.org>,
	 Ben Segall <bsegall@google.com>, Mel Gorman <mgorman@suse.de>,
	 Valentin Schneider <vschneid@redhat.com>,
	K Prateek Nayak <kprateek.nayak@amd.com>,
	 linux-kernel@vger.kernel.org, Peng Huang <penghuang@google.com>
Subject: [RFC PATCH 0/3] rwsem: priority boost for holders blocking high-priority waiters
Date: Thu, 19 Nov 2026 14:49:51 -0800	[thread overview]
Message-ID: <20261119224954.196990-1-penghuang@google.com> (raw)

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


             reply	other threads:[~2026-11-19 22:49 UTC|newest]

Thread overview: 4+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2026-11-19 22:49 Peng Huang [this message]
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

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20261119224954.196990-1-penghuang@google.com \
    --to=penghuang@google.com \
    --cc=boqun@kernel.org \
    --cc=bsegall@google.com \
    --cc=dietmar.eggemann@arm.com \
    --cc=juri.lelli@redhat.com \
    --cc=kprateek.nayak@amd.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=longman@redhat.com \
    --cc=mgorman@suse.de \
    --cc=mingo@redhat.com \
    --cc=peterz@infradead.org \
    --cc=rostedt@goodmis.org \
    --cc=vincent.guittot@linaro.org \
    --cc=vschneid@redhat.com \
    --cc=will@kernel.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
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®