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

[John Stultz <jstultz@google.com>]

Hey All,

With some nice progress made recently, I wanted to move on to
sending out the next major component 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) ...

In this chunk, there is more than just sleeping owner handling:
I'm including some core-scheduling fixes from Vasily Gorbik and
K Prateek, as well as an optimization to do chain migration left
over from the last chunk.

But the substantial part of this chunk is the sleeping owner
handling, which addresses what to do when a task is blocked on a
mutex who’s 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 its 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.

Hopefully the earlier patches will be easy to queue, but I
suspect there will be lots of review feedback for me to address
in the last one.  :)

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

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-v30-7.2-rc1/
  https://github.com/johnstultz-work/linux-dev.git proxy-exec-v30-7.2-rc1


New changes to the full patch series in this revision include:
* Rebased on top of Peter’s cleanups and improvements which
  landed in 7.2-rc1

* Added an optimization to the activate_blocked_waiters logic
  which was causing performance impact compared to the !proxy
  case

* Pulled in some of Andrea Righi’s sched_ext + proxy
  compatibility improvements (I’ve unfortunately not had much
  time to focus on this yet, so I’ve not done much testing!)

Issues still to address with the full series:
* Need to do more work integrating and testing Andrea’s
  sched_ext changes

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

* 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: Suleiman is looking at
  pi-futexes, and using proxy for 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 and Suleiman Souhlal 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: kuyo chang <kuyo.chang@mediatek.com>
Cc: hupu <hupu.gm@gmail.com>
Cc: Vasily Gorbik <gor@linux.ibm.com>
Cc: kernel-team@android.com

John Stultz (4):
  sched/core: Avoid migrating blocked_on tasks
  sched: Switch rq->next_class in proxy_reset_donor()
  sched: Break out core of attach_tasks() helper into sched.h
  sched: Migrate whole chain in proxy_migrate_task()

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

Vasily Gorbik (2):
  sched/core: Don't steal a proxy-exec donor
  sched/core: Don't proxy-exec unmatched cookie lock owners

 include/linux/sched.h |   7 +
 init/init_task.c      |   6 +
 kernel/fork.c         |   6 +
 kernel/sched/core.c   | 338 ++++++++++++++++++++++++++++++++++++++----
 kernel/sched/fair.c   |  16 +-
 kernel/sched/sched.h  |  19 +++
 6 files changed, 349 insertions(+), 43 deletions(-)

-- 
2.55.0.rc0.799.gd6f94ed593-goog