[RESEND][PATCH v31 0/9] Sleeping Owner Handling for Proxy Execution (v31)

Hey All,

Didn’t get much feedback last round, as a number of folks were
on vacation, so I wanted to re-send out the v31 iteration of 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 actually is more than just sleeping owner
handling: I’m including some core-scheduling fixes from Vasily
Gorbik and K Prateek, a DL fix from Christian, as well as an
optimization to 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 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.

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 two.  :)

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

New in v31 of this set:
* Included Christian's patch to return early from
  yield_task_dl() when we are proxying

* K Prateek's noticed a potential race where if a sleeping owner
  is woken in parallel with the waiter enqueuing itself on the
  sleeping owner, the waiting task could get stuck on that owner
  until it sleeps and is woken up again. So a fix for this has
  been made.

* Maria Yu and Tengfei Fan reported an issue with rq->nr_iowait
  values getting out of balance, and provided a helpful
  reproducer. I’ve adjusted the logic in
  do_activate_blocked_waiter() to correct the imbalance.

* Included changes from Andrea Righi to adapt the sleeping owner
  handling with his recent series to make sched_ext and
  proxy-exec work together (his series and my series are fully
  independent - I only have a two-line patch from Andrea that
  will be needed if both changes land in parallel).


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

In the full series, there's been quite a lot of exciting
changes, particularly three really interesting chunks of work
from Andrea, K Prateek and Suleiman!

New changes to the full patch series in this revision include:
* Included Andrea’s sched_ext changes to support sched_ext
  with proxy-exec (along with a lot of pending sched_ext changes
  his work is built on top of)!

* Included K Prateek’s deeper fixes to core-scheduling issues
  with proxy-exec!

* Included first pass of Suleiman Souhlal’s efforts to get
  proxy-enabled futexes working!

* Fixed a very subtle reported proxy-rwsems race with
  rwsem_mark_wake(), which could cause the task::blocked_on
  state checks to trip warnings, even when proxy-exec was
  disabled.

* Updated test-ww_mutex patches from Håkon Bugge

* Also, I've added a small build fix at the end of the larger
  series branch that Håkon Bugge reported since v31 was first
  sent out.


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.

* Take a stab at lock-owner-count optimization idea from
  K Prateek

* 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: Suleiman's draft work on
  pi-futexes is ongoing, 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, 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 <[email protected]>
Cc: Qais Yousef <[email protected]>
Cc: Ingo Molnar <[email protected]>
Cc: Peter Zijlstra <[email protected]>
Cc: Juri Lelli <[email protected]>
Cc: Vincent Guittot <[email protected]>
Cc: Dietmar Eggemann <[email protected]>
Cc: Valentin Schneider <[email protected]>
Cc: Steven Rostedt <[email protected]>
Cc: Ben Segall <[email protected]>
Cc: Zimuzo Ezeozue <[email protected]>
Cc: Will Deacon <[email protected]>
Cc: Waiman Long <[email protected]>
Cc: Boqun Feng <[email protected]>
Cc: "Paul E. McKenney" <[email protected]>
Cc: Metin Kaya <[email protected]>
Cc: Xuewen Yan <[email protected]>
Cc: K Prateek Nayak <[email protected]>
Cc: Thomas Gleixner <[email protected]>
Cc: Daniel Lezcano <[email protected]>
Cc: Suleiman Souhlal <[email protected]>
Cc: kuyo chang <[email protected]>
Cc: hupu <[email protected]>
Cc: [email protected]

Andrea Righi (1):
  sched: Distinguish proxy activations from wakeups

Christian Loehle (1):
  sched/deadline: Ignore proxy-exec sched_yield()

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     | 350 ++++++++++++++++++++++++++++++++++++----
 kernel/sched/deadline.c |   3 +
 kernel/sched/ext/ext.c  |   8 +
 kernel/sched/fair.c     |  16 +-
 kernel/sched/sched.h    |  21 +++
 8 files changed, 374 insertions(+), 43 deletions(-)

-- 
2.55.0.654.g21b8a5bc05-goog