[PATCH v33 0/7] Sleeping Owner Handling for Proxy Execution (v33)

[John Stultz <jstultz@google.com>]

Hey All,
  Just wanted to send out this next iteration of Proxy
Execution: Sleeping Owner Handling.

As always, I’m trying to submit this larger work in smallish
digestible pieces. A quick overview of the journey so far:
 1) Prep patches
 2) Single rq proxying
 3) Simple donor migration
 4) Optimized donor migration
 5) Sleeping owner handling  <---- We are here!
 6) K Prateek’s core-sched fixes
 7) Connor's chain level balancing
 8) Suleiman’s proxy rwsems
 9) Suleiman’s proxy futexes
10) ...

The main feature in this series is the sleeping owner handling
patch, which addresses what to do when a task is blocked on a
mutex whose owner is sleeping. Since there is nothing we can do
to boost the sleeping owner at that point, we instead deactivate
and queue the waiter on a list attached to the owner. Then when
the owner wakes up, we will activate the waiters on the same
runqueue, so they can then boost the owner to run.

But since the simple sounding things hide subtlety, this ends up
being a pretty complex bit of logic. You can effectively get
trees of waiters, and it's possible to have tasks in the middle
of the tree be woken up. Then handling wakeups as they cascade
down the tree properly is also a bit complex, as there are extra
lists to manage the recursive style work without actually
recursing.

K Prateek sent an interesting alternative approach:
  https://lore.kernel.org/lkml/20260826062901.2137-1-kprateek.nayak@amd.com/

But after talking with Peter on this at LPC, we agreed to start
with the “relatively simpler”(ha!) approach first, and then take
a later swing at using K Prateek’s approach to optimize it.

In this series (against linus' HEAD) I’ve also aggregated fixes
from K Prateek, Shubhang Kaushik, as well as included some
initial proxy-chain cycle detection logic combining parallel
efforts from Zhidao Su and Hui Su. Additionally there have been
issues fixed in the sleeping-owner-enqueuing change, reported
by David Stevens as well as other partners.

Thank you to everyone for contributing bug reports, fixes and
improvements! I really appreciate it!

New in v32 of this set:
 * Fixes to PSI flag handling logic that proxy-exec could break.

 * Fix from Shubhang to use rq->donor for sched_tick_remote().

 * Extended K Prateek’s optimization to activate on NULL owner
   to do the same for null mutex/blocked_on.

 * Fix to set TASK_RUNNING when we shortcut return-migration to
   immediately run a task.

 * Fixed chain depth limit for find_proxy_task() to avoid
   deadlocks if there were a lock cycle, from Zhidao Su.

 * Further chain cycle-detection logic, using Brent’s algorithm
   to catch cycles faster from Hui Su.

 * Additional fixes to activate_blocked_waiters() to avoid PSI
   state problems

 * Fix for a potential crasher caused when the call to
   do_activate_blocked_waiter() is significantly delayed, which
   could cause proxy activations to the previous owner’s cpu,
   even if the task had been otherwise woken and then went back
   to sleep - potentially allowing execution outside of the smp
   affinity mask.

Additionally I’d appreciate any testing or comments that folks
have with the full Proxy Execution series! You can find the full
Proxy Exec series here:
  https://github.com/johnstultz-work/linux-dev/commits/proxy-exec-v33-7.4-pre-rc1/
  https://github.com/johnstultz-work/linux-dev.git proxy-exec-v33-7.4-pre-rc1

New changes to the full patch series in this revision include:
 * Small fix for Suleiman’s FUTEX_LOCK_PING logic

Issues still to address with the full series:
 * Address and integrate feedback from v1 RFC of Proxy enabled
   futexes

 * Maria Yu raised a subtle difference in how the nr_iowait
   counting might be attributed with proxy-exec: potentially
   proxy-migrated donors that become blocked on sleeping owners
   could increment/decrement the value on the owners cpu rq,
   instead of on the donor’s original cpu rq. It’s unclear to
   me what the impact of this would be, if at all, but it is
   potentially an observable difference with proxy-exec, so
   I’m going to take a swing at addressing it.

 * Reevaluate performance regression K Prateek Nayak found with
   the full series earlier.

 * The chain migration functionality needs further iterations
   and better validation to ensure it truly maintains the RT/DL
   load balancing invariants (despite this being broken in
   vanilla upstream with RT_PUSH_IPI currently)

Future work:
 * Expand to more locking primitives: Binder PI is something
   else we’re exploring.

 * Eventually: Work to replace rt_mutexes and get things happy
   with PREEMPT_RT


Credit/Disclaimer:
—--------------------
As always, this Proxy Execution series has a long history with
lots of developers that deserve credit: 

First described in a paper[1] by Watkins, Straub, Niehaus, then
from patches from Peter Zijlstra, extended with lots of work by
Juri Lelli, Valentin Schneider, and Connor O'Brien. (and thank
you to Steven Rostedt for providing additional details here!).
Thanks also to Joel Fernandes, Dietmar Eggemann, Metin Kaya,
K Prateek Nayak, Suleiman Souhlal, Christian Loehle, and
Andrea Righi for their substantial review, suggestion, and patch
contributions.

So again, many thanks to those above, as all the credit for this
series really is due to them - while the mistakes are surely mine.

Thanks so much!
-john

[1] https://static.lwn.net/images/conf/rtlws11/papers/proc/p38.pdf

Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Ingo Molnar <mingo@redhat.com>
Cc: K Prateek Nayak <kprateek.nayak@amd.com>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Juri Lelli <juri.lelli@redhat.com>
Cc: Vincent Guittot <vincent.guittot@linaro.org>
Cc: Valentin Schneider <vschneid@redhat.com>
Cc: Suleiman Souhlal <suleiman@google.com>
Cc: Andrea Righi <arighi@nvidia.com>
Cc: Metin Kaya <Metin.Kaya@arm.com>
Cc: Dietmar Eggemann <dietmar.eggemann@arm.com>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Zimuzo Ezeozue <zezeozue@google.com>
Cc: Waiman Long <longman@redhat.com>
Cc: Boqun Feng <boqun.feng@gmail.com>
Cc: "Paul E. McKenney" <paulmck@kernel.org>
Cc: Joel Fernandes <joelagnelf@nvidia.com>
Cc: Qais Yousef <qyousef@layalina.io>
Cc: Xuewen Yan <xuewen.yan94@gmail.com>
Cc: kuyo chang <kuyo.chang@mediatek.com>
Cc: hupu <hupu.gm@gmail.com>
Cc: Zhan Xusheng <zhanxusheng@xiaomi.com>
Cc: zhidao su (Xiaomi) <soolaugust@gmail.com>
Cc: Hui Su <sh_def@163.com>
Cc: Shubhang Kaushik (Ampere) <sh@gentwo.org>
Cc: kernel-team@android.com


Hui Su (1):
  sched/proxy: Detect cycles in proxy walks earlier

John Stultz (2):
  sched/psi: Preserve sleep-persistent PSI flags on off-CPU sleeping
    dequeues
  sched/proxy: Set TASK_RUNNING when shortcuting return migration

K Prateek Nayak (1):
  sched/core: Activate blocked donor when no owner is found

Peter Zijlstra (1):
  sched/proxy: Add deactivated (sleeping) owner handling to
    find_proxy_task()

Shubhang Kaushik (Ampere) (1):
  sched/core: Use the scheduling context for remote ticks

zhidao su (Xiaomi) (1):
  sched/proxy: Break cyclic proxy chains by deactivating blocked tasks

 include/linux/sched.h      |   7 +
 include/linux/sched/task.h |   1 +
 init/init_task.c           |   6 +
 kernel/fork.c              |   6 +
 kernel/sched/core.c        | 404 +++++++++++++++++++++++++++++++++----
 kernel/sched/stats.h       |  24 ++-
 6 files changed, 407 insertions(+), 41 deletions(-)

-- 
2.56.0.257.gf7497c7d27-goog