Messages in this thread | | | Date | Mon, 20 Mar 2023 23:37:08 +0000 | Subject | [PATCH v2 00/12] Reviving the Proxy Execution Series v2 | From | John Stultz <> |
| |
Hey All,
I’ve recently picked up the proxy execution effort, so I wanted to send this out to share the current state of the patch series.
So first of all, this Proxy Execution series has a long history. Starting from initial patches from Peter Zijlstra, then extended with lots of work by Juri Lelli, Valentin Schneider, and Connor O'Brien.
So all the credit for this series really is due to the developers above, while the mistakes are likely mine. :) I wanted to particularly appreciate Connor’s recent efforts, as I worked closely with him and it’s only due to his knowledge, patience, and clear explanations of the changes and issues that I was able to come to my current understanding of the series so quickly.
Overview: --------- I like to think of Proxy Execution as a generalized form of priority inheritance. Classic priority inheritance works well for real-time tasks where there is a straight forward priority order to how things are run. But it breaks down when used between CFS tasks, as there are lots of parameters involved outside of just the task’s nice value when selecting the next task to run (via pick_next_task()). So ideally we want to imbue the mutex holder with all the scheduler attributes of the waiting task.
Proxy Execution tries to do this via a few changes: * Keeping tasks that are blocked on a mutex *on* the runqueue * Keeping additional tracking of which mutex a task is blocked on, and which task holds a specific mutex. * Special handling for when we select a blocked task to run, so that we instead run the mutex holder.
The first of these is the most difficult to grasp (I do get the mental friction here: blocked tasks on the *run*queue sounds like nonsense! Personally I like to think of the runqueue in this model more like a “task-selection queue”).
By leaving blocked tasks on the runqueue, we allow pick_next_task() to choose the task that should run next (even if it’s blocked waiting on a mutex). If we do select a blocked task, we look at the task’s blocked_on mutex and from there look at the mutex’s owner task. And in the simple case, the task which owns the mutex is what we then run, allowing it to release the mutex.
This means that instead of just tracking “curr”, the scheduler needs to track both the scheduler context (what was picked and all the state used for scheduling decisions), and the execution context (what we’re running)
In this way, the mutex owner is run “on behalf” of the blocked task that was picked to run, essentially inheriting the scheduler context of the blocked task.
As Connor outlined in a previous submission[1] of this patch series, this raises a number of complicated situations: The mutex owner might itself be blocked on another mutex, or it could be sleeping, running on a different CPU, in the process of migrating between CPUs, etc.
But the functionality provided is useful, as in Android we have a number of cases where we are seeing priority inversion (not unbounded, but longer than we’d like) between “foreground” and “background” SCHED_NORMAL applications, so having a generalized solution would be great.
Issues still to address: ------------------------ The last time this patch series was submitted, a number of issues were identified that need to be addressed: * cputime accounting is a little unintuitive, as time used by the proxy was being charged to the blocked task. Connor began work to address this but it was not complete, so it is not included in this version of the series. * RT/DL load balancing. There is a scheduling invariant that we always need to run the top N highest priority RT tasks across the N cpus. However keeping blocked tasks on the runqueue greatly complicates the load balancing for this. Connor took an initial stab at this with “chain level balancing” included in this series. Feedback on this would be appreciated! * CFS load balancing. Blocked tasks may carry forward load (PELT) to the lock owner's CPU, so CPU may look like it is overloaded. * Terminology/BikeShedding: I think much of the terminology makes these changes harder to reason about. - As noted above, blocked-tasks on the run-queue breaks some mental models - The “proxy” relationship seems a bit inverted. Peter’s “Split scheduler execution context” describes the proxy as the scheduler context, and curr being the execution context (the blocked task being the “scheduler proxy” for the lock-holder). Personally, I think of proxies as those who do-on-others-behalf, so to me it would make more sense to have rq_curr() be the selected task (scheduler context) and rq_proxy() be the run task (execution context), as its running on behalf of the selected but blocked task. Unless folks object, I’ll likely change this in a future submission. - Also, the rq_curr() and rq_proxy() distinction is easily confused. I think it’s sane to try to keep close to the existing curr based logic, but swapping rq_proxy in for some cases makes the change smaller, but the resulting code less clear. I worry folks focused on the !CONFIG_PROXY_EXEC case might easily mix up which to use when creating new logic. * Resolving open questions in comments: I’ve left these in for now, but I hope to review and try to make some choices where there are open questions. If folks have specific feedback or suggestions here, it would be great!
Performance: ------------ With the current patch series the mutexes are handed off, instead of using optimistic spinning. This is a potential concern where locks are under high contention. However, so far in our performance analysis (on both x86 and mobile devices) we’ve not seen any major regressions.
Changes since Connor’s last submission: --------------------------------------- * Connor took a swing at addressing the RT/DL load balancing issue * Connor fixed a number of issues found in testing * I added rq_curr() and rq_proxy() accessors to abstract rq->curr and rq->proxy references (so it collapses in the !CONFIG_PROXY_EXECUTION case) * I’ve gone through the series trying to split up the larger functions and better conditionalize the logic on CONFIG_PROXY_EXECUTION * I’ve broken out some of the logic in larger patches into separate patches, as well as split out small prep changes to the logic so the patches are easier to review. * I’ve also found and addressed a few edge cases in locking and mutex owner handling. * I dropped the patch changing mutex::wait_lock to always save/restore irq flags (as Joel raised a concern that the patch wasn’t actually necessary). * I’ve folded a number of fixes down into the relevant patches.
For the most part, my changes have been mechanical reworking of the logic, avoiding any changes in behavior. Though after this, I’ll likely start trying to rework some of the logic further.
So while there is still more to do, I wanted to send this series out so folks could see work is continuing, and be able to get some additional review on recent changes. Review and feedback would be greatly appreciated!
If folks find it easier to test/tinker with, this patch series can also be found here: https://github.com/johnstultz-work/linux-dev.git proxy-exec-v2-6.3-rc
Thanks so much! -john
[1] https://lore.kernel.org/lkml/20221003214501.2050087-1-connoro@google.com/
Cc: Joel Fernandes <joelaf@google.com> Cc: Qais Yousef <qyousef@google.com> 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: Mel Gorman <mgorman@suse.de> Cc: Daniel Bristot de Oliveira <bristot@redhat.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: kernel-team@android.com
Connor O'Brien (1): sched: Attempt to fix rt/dl load balancing via chain level balance
John Stultz (2): sched: Replace rq->curr access w/ rq_curr(rq) sched: Unnest ttwu_runnable in prep for proxy-execution
Juri Lelli (1): locking/mutex: Expose mutex_owner()
Peter Zijlstra (6): locking/ww_mutex: Remove wakeups from under mutex::wait_lock locking/mutex: Rework task_struct::blocked_on locking/mutex: Add task_struct::blocked_lock to serialize changes to the blocked_on state sched: Unify runtime accounting across classes sched: Split scheduler execution context sched: Add proxy execution
Valentin Schneider (2): locking/mutex: Add p->blocked_on wrappers sched/rt: Fix proxy/current (push,pull)ability
include/linux/mutex.h | 2 + include/linux/sched.h | 24 +- include/linux/ww_mutex.h | 3 + init/Kconfig | 7 + init/init_task.c | 1 + kernel/Kconfig.locks | 2 +- kernel/fork.c | 6 +- kernel/locking/mutex-debug.c | 9 +- kernel/locking/mutex.c | 103 ++++- kernel/locking/ww_mutex.h | 10 +- kernel/sched/core.c | 787 ++++++++++++++++++++++++++++++++--- kernel/sched/core_sched.c | 2 +- kernel/sched/cpudeadline.c | 12 +- kernel/sched/cpudeadline.h | 3 +- kernel/sched/cpupri.c | 29 +- kernel/sched/cpupri.h | 6 +- kernel/sched/deadline.c | 213 ++++++---- kernel/sched/debug.c | 2 +- kernel/sched/fair.c | 109 +++-- kernel/sched/membarrier.c | 8 +- kernel/sched/pelt.h | 2 +- kernel/sched/rt.c | 301 +++++++++----- kernel/sched/sched.h | 286 ++++++++++++- kernel/sched/stop_task.c | 13 +- 24 files changed, 1599 insertions(+), 341 deletions(-)
-- 2.40.0.rc1.284.g88254d51c5-goog
| |