[PATCH v27 00/10] Optimized Donor Migration for Proxy Execution

[John Stultz]

Hey All,

Since Peter queued my last chunk of the Proxy Execution series
(simple donor migration) I wanted to send out the next chunk of
the series for discussion: Optimized Donor Migration.

This is just the next step for Proxy Execution, allowing
proxy-return-migration to occur from the try_to_wake_up()
callpath. This however introduces some complexity as it means
the rq->donor can change from a try_to_wake_up() call, and thus
there are further changes needed to make this safe.

As always, I’m trying to submit this larger work in smallish
digestible pieces, so in this portion of the series, I’m only
submitting for review and consideration these patches which
minimize the use of passing “prev” (ie: the rq->donor) down
through the class schedulers since this cached value can become
invalid across runqueue lock drops. From there there are some
fixups to yield and the deadline class scheduler to avoid issues
when the donor changes, then the actual patch to do return
migration from ttwu() followed by some optimization patches so
we migrate the entire task chain in proxy_migrate_task().

I really want to share my appreciation for recent feedback and
changes provided by Peter, Steven, and K Prateek! 

New in this iteration:
* Major late rework, getting rid of proxy_force_return() and
  handling all of the return migrations from try_to_wake_up
  suggested by Peter along with help from K Prateek. This is a
  pretty significant change, but it’s survived some initial
  testing but I still need to run more thorough testing to make
  sure we haven’t introduced any troubles.

* Integrate simplifications to proxy_needs_return() suggested by
  K Prateek

* Rework ttwu_runnable to align with
  ACQUIRE(__task_rq_lock, guard)(p) usage as suggested by Peter

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 (based on current tip/sched/core):
  https://github.com/johnstultz-work/linux-dev/commits/proxy-exec-v27-7.0-rc6-tip-sched-core/
  https://github.com/johnstultz-work/linux-dev.git proxy-exec-v27-7.0-rc6-tip-sched-core


Issues still to address with the full series:
* Continue testing with the recent ttwu rework to ensure the
  whole stack is working as intended.

* Continue working to get sched_ext to be ok with Proxy
  Execution enabled.

* 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: Figuring out pi-futexes
  would be good, 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@xxxxxxxxxx>
Cc: Qais Yousef <qyousef@xxxxxxxxxxx>
Cc: Ingo Molnar <mingo@xxxxxxxxxx>
Cc: Peter Zijlstra <peterz@xxxxxxxxxxxxx>
Cc: Juri Lelli <juri.lelli@xxxxxxxxxx>
Cc: Vincent Guittot <vincent.guittot@xxxxxxxxxx>
Cc: Dietmar Eggemann <dietmar.eggemann@xxxxxxx>
Cc: Valentin Schneider <vschneid@xxxxxxxxxx>
Cc: Steven Rostedt <rostedt@xxxxxxxxxxx>
Cc: Ben Segall <bsegall@xxxxxxxxxx>
Cc: Zimuzo Ezeozue <zezeozue@xxxxxxxxxx>
Cc: Mel Gorman <mgorman@xxxxxxx>
Cc: Will Deacon <will@xxxxxxxxxx>
Cc: Waiman Long <longman@xxxxxxxxxx>
Cc: Boqun Feng <boqun.feng@xxxxxxxxx>
Cc: "Paul E. McKenney" <paulmck@xxxxxxxxxx>
Cc: Metin Kaya <Metin.Kaya@xxxxxxx>
Cc: Xuewen Yan <xuewen.yan94@xxxxxxxxx>
Cc: K Prateek Nayak <kprateek.nayak@xxxxxxx>
Cc: Thomas Gleixner <tglx@xxxxxxxxxxxxx>
Cc: Daniel Lezcano <daniel.lezcano@xxxxxxxxxx>
Cc: Suleiman Souhlal <suleiman@xxxxxxxxxx>
Cc: kuyo chang <kuyo.chang@xxxxxxxxxxxx>
Cc: hupu <hupu.gm@xxxxxxxxx>
Cc: kernel-team@xxxxxxxxxxx

John Stultz (8):
  sched: Rework pick_next_task() and prev_balance() to avoid stale prev
    references
  sched: Avoid donor->sched_class->yield_task() null traversal
  sched: deadline: Add some helper variables to cleanup deadline logic
  sched: deadline: Add dl_rq->curr pointer to address issues with Proxy
    Exec
  sched: Rework block_task so it can be directly called
  sched: Have try_to_wake_up() handle return-migration for PROXY_WAKING
    case
  sched: Break out core of attach_tasks() helper into sched.h
  sched: Migrate whole chain in proxy_migrate_task()

K Prateek Nayak (1):
  sched/core: Reset the donor to current task when donor is woken

Peter Zijlstra (1):
  sched: Add blocked_donor link to task for smarter mutex handoffs

 include/linux/sched.h    |   3 +-
 init/init_task.c         |   1 +
 kernel/fork.c            |   1 +
 kernel/locking/mutex.c   |  44 +++++-
 kernel/sched/core.c      | 315 +++++++++++++++++++++------------------
 kernel/sched/deadline.c  |  44 ++++--
 kernel/sched/fair.c      |  25 +---
 kernel/sched/idle.c      |   2 +-
 kernel/sched/rt.c        |   8 +-
 kernel/sched/sched.h     |  30 +++-
 kernel/sched/stop_task.c |   2 +-
 kernel/sched/syscalls.c  |   3 +-
 12 files changed, 291 insertions(+), 187 deletions(-)

-- 
2.53.0.1213.gd9a14994de-goog