[PATCH v32 0/2] Sleeping Owner Handling for Proxy Execution (v32)

[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) chain level balancing
7) proxy rwsems
8) ...

Peter kindly picked up most of the simpler patches I had
submitted in the last iteration, so this mainly leaves 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.

Atul Kumar Pant, K Prateek and Peter and all provided feedback
on the last set that I’ve tried to work into this one.

Additionally, K Prateek sent out his own take on this change
here, which is very interesting:
https://lore.kernel.org/lkml/20260826062901.2137-1-kprateek.nayak@amd.com/

There are definite benefits to his approach, but the patch
series needs a bit more polish and it feels a bit more subtle to
understand. So I figured I’d iterate again on my approach and
send it out. 

Peter: Hopefully you can provide some input as to which approach
you’d prefer?

I did include one of K Prateek's fixes from his approach in this
series, as it looks like it should go upstream regardless.

I'd love to get further feedback on any place where these
patches are confusing, or could use additional clarifications.

New in v32 of this set:
* Rebased on current -tip/sched/core

* Added K Prateek’s “Activate blocked donor when no owner is
  found” patch

* Add fix suggested by Atul Kumar Pant to double check is_blocked
  in do_activate_blocked_waiter()

* Integrated a number of style/formatting changes to utilize
  guard() sent by Peter

* Fixed potential race in proxy_remove_from_sleeping_owner()
  with owner changing, as found by Peter

* Dropped extraneous call to activate_blocked_waiters() noted by
  Peter

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-v32-7.3-rc-tip-sched-core/
  https://github.com/johnstultz-work/linux-dev.git proxy-exec-v32-7.3-rc-tip-sched-core

New changes to the full patch series in this revision include:
* Integrated Suleiman’s proxy-enabled FUTEX_PING patch series,
  recently sent to the list.

* Updated to include v13 of Andrea’s sched_ext + proxy-exec
  patches

Issues still to address with the full series:
* After the nr_wait imbalance was addressed, 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: Joel Fernandes <joelagnelf@nvidia.com>
Cc: Qais Yousef <qyousef@layalina.io>
Cc: Ingo Molnar <mingo@redhat.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Juri Lelli <juri.lelli@redhat.com>
Cc: Vincent Guittot <vincent.guittot@linaro.org>
Cc: Dietmar Eggemann <dietmar.eggemann@arm.com>
Cc: Valentin Schneider <vschneid@redhat.com>
Cc: Steven Rostedt <rostedt@goodmis.org>
Cc: Ben Segall <bsegall@google.com>
Cc: Zimuzo Ezeozue <zezeozue@google.com>
Cc: Will Deacon <will@kernel.org>
Cc: Waiman Long <longman@redhat.com>
Cc: Boqun Feng <boqun.feng@gmail.com>
Cc: "Paul E. McKenney" <paulmck@kernel.org>
Cc: Metin Kaya <Metin.Kaya@arm.com>
Cc: Xuewen Yan <xuewen.yan94@gmail.com>
Cc: K Prateek Nayak <kprateek.nayak@amd.com>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Daniel Lezcano <daniel.lezcano@linaro.org>
Cc: Suleiman Souhlal <suleiman@google.com>
Cc: Andrea Righi <arighi@nvidia.com>
Cc: kuyo chang <kuyo.chang@mediatek.com>
Cc: hupu <hupu.gm@gmail.com>
Cc: kernel-team@android.com


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

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

 include/linux/sched.h      |   7 +
 include/linux/sched/task.h |   1 +
 init/init_task.c           |   6 +
 kernel/fork.c              |   6 +
 kernel/sched/core.c        | 342 ++++++++++++++++++++++++++++++++++---
 5 files changed, 338 insertions(+), 24 deletions(-)

-- 
2.55.0.1082.g2b9226bbc0-goog