Towards implementing proxy execution
Subsystems (4)
Juri Lelli
maintainercover Towards implementing proxy execution
Hi all,
Proxy Execution (also goes under several other names) isn't a new concept, it has been mentioned already in the past to this community (both in email discussions and at conferences [1, 2]), but no actual implementation that applies to a fairly recent kernel exists as of today (of which I'm aware of at least - happy to be proven wrong).
Very broadly speaking, more info below, proxy execution enables a task to run using the context of some other task that is "willing" to participate in the mechanism, as this helps both tasks to improve performance (w.r.t. the latter task not participating to proxy execution).
This RFD/proof of concept aims at starting a discussion about how we can get proxy execution in mainline. But, first things first, why do we even care about it?
I'm pretty confident with saying that the line of development that is mainly interested in this at the moment is the one that might benefit in allowing non privileged processes to use deadline scheduling [3]. The main missing bit before we can safely relax the root privileges constraint is a proper priority inheritance mechanism, which translates to bandwidth inheritance [4, 5] for deadline scheduling, or to some sort of interpretation of the concept of running a task holding a (rt_)mutex within the bandwidth allotment of some other task that is blocked on the same (rt_)mutex.
The concept itself is pretty general however, and it is not hard to foresee possible applications in other scenarios (say for example nice values/shares across co-operating CFS tasks or clamping values [6]). But I'm already digressing, so let's get back to the code that comes with this cover letter.
One can define the scheduling context of a task as all the information in task_struct that the scheduler needs to implement a policy and the execution contex as all the state required to actually "run" the task. An example of scheduling context might be the information contained in task_struct se, rt and dl fields; affinity pertains instead to execution context (and I guess decideing what pertains to what is actually up for discussion as well ;-). Patch 04/08 implements such distinction.
As implemented in this set, a link between scheduling contexts of different tasks might be established when a task blocks on a mutex held by some other task (blocked_on relation). In this case the former task starts to be considered a potential proxy for the latter (mutex owner). One key change in how mutexes work made in here is that waiters don't really sleep: they are not dequeued, so they can be picked up by the scheduler when it runs. If a waiter (potential proxy) task is selected by the scheduler, the blocked_on relation is used to find the mutex owner and put that to run on the CPU, using the proxy task scheduling context.
Follow the blocked-on relation:
,-> task <- proxy, picked by scheduler
| | blocked-on
| v
blocked-task | mutex
| | owner
| v
`-- task <- gets to run using proxy info
Now, the situation is (of course) more tricky than depicted so far because we have to deal with all sort of possible states the mutex owner might be in while a potential proxy is selected by the scheduler, e.g. owner might be sleeping, running on a different CPU, blocked on another mutex itself... so, I'd kindly refer people to have a look at 05/08 proxy() implementation and comments.
Peter kindly shared his WIP patches with us (me, Luca, Tommaso, Claudio, Daniel, the Pisa gang) a while ago, but I could seriously have a decent look at them only recently (thanks a lot to the other guys for giving a first look at this way before me!). This set is thus composed of Peter's original patches (which I rebased on tip/sched/core as of today, commented and hopefully duly reported in changelogs what have I possibly broke) plus a bunch of additional changes that seemed required to make all this boot "successfully" on a virtual machine. So be advised! This is good only for fun ATM (I actually really hope this is good enough for discussion), pretty far from production I'm afraid. Share early, share often, right? :-)
The main concerns I have with the current approach is that, being based on mutex.c, it's both
- not linked with futexes
- not involving "legacy" priority inheritance (rt_mutex.c)
I believe one of the main reasons Peter started this on mutexes is to have better coverage of potential problems (which I can assure everybody it had). I'm not yet sure what should we do moving forward, and this is exactly what I'd be pleased to hear your opinions on.
https://github.com/jlelli/linux.git experimental/deadline/proxy-rfc-v1
Thanks a lot in advance!
- Juri
1 - https://wiki.linuxfoundation.org/_media/realtime/events/rt-summit2017/proxy-execution_peter-zijlstra.pdf
2 - https://lwn.net/Articles/397422/ which "points" to https://goo.gl/3VrLza
3 - https://marc.info/?l=linux-rt-users&m=153450086400459&w=2
4 - https://ieeexplore.ieee.org/document/5562902
5 - http://retis.sssup.it/~lipari/papers/rtlws2013.pdf
6 - https://lore.kernel.org/lkml/[email protected]/
Juri Lelli (3):
locking/mutex: make mutex::wait_lock irq safe
sched: Ensure blocked_on is always guarded by blocked_lock
sched: Fixup task CPUs for potential proxies.
Peter Zijlstra (5):
locking/mutex: Convert mutex::wait_lock to raw_spinlock_t locking/mutex: Removes wakeups from under mutex::wait_lock locking/mutex: Rework task_struct::blocked_on
sched: Split scheduler execution context
sched: Add proxy execution
include/linux/mutex.h | 4 +- include/linux/sched.h | 8 +- init/Kconfig | 4 + init/init_task.c | 1 + kernel/Kconfig.locks | 2 +- kernel/fork.c | 8 +- kernel/locking/mutex-debug.c | 12 +- kernel/locking/mutex.c | 127 +++++++-- kernel/sched/core.c | 510 +++++++++++++++++++++++++++++++++-- kernel/sched/deadline.c | 2 +- kernel/sched/fair.c | 7 + kernel/sched/rt.c | 2 +- kernel/sched/sched.h | 30 ++- 13 files changed, 642 insertions(+), 75 deletions(-)
Signature · 1 line
2.17.1
Juri Lelli
maintainerPATCH 1/8 locking/mutex: Convert mutex::wait_lock to raw_spinlock_t
From: Peter Zijlstra <[email protected]>
In preparation to nest mutex::wait_lock under rq::lock it needs to be raw_spinlock_t.
--- include/linux/mutex.h | 4 ++-- kernel/locking/mutex-debug.c | 4 ++-- kernel/locking/mutex.c | 22 +++++++++++----------- 3 files changed, 15 insertions(+), 15 deletions(-)
include/linux/mutex.h +2 -2
@@ -52,7 +52,7 @@ struct ww_acquire_ctx;*/ struct mutex {atomic_long_t owner; -spinlock_t wait_lock; +raw_spinlock_t wait_lock;#ifdef CONFIG_MUTEX_SPIN_ON_OWNER struct optimistic_spin_queue osq;/* Spinner MCS lock */ #endif
@@ -127,7 +127,7 @@ do { \#define __MUTEX_INITIALIZER (lockname) \ { .owner = ATOMIC_LONG_INIT(0) \ - , .wait_lock = __SPIN_LOCK_UNLOCKED(lockname.wait_lock) \ + , .wait_lock = __RAW_SPIN_LOCK_UNLOCKED(lockname.wait_lock) \ , .wait_list = LIST_HEAD_INIT(lockname.wait_list) \ __DEBUG_MUTEX_INITIALIZER(lockname) \ __DEP_MAP_MUTEX_INITIALIZER(lockname) }
kernel/locking/mutex-debug.c +2 -2
@@ -36,7 +36,7 @@ void debug_mutex_lock_common(struct mutex *lock, struct mutex_waiter *waiter)void debug_mutex_wake_waiter (struct mutex *lock,struct mutex_waiter *waiter) { -SMP_DEBUG_LOCKS_WARN_ON (!spin_is_locked (&lock->wait_lock)); +SMP_DEBUG_LOCKS_WARN_ON (!raw_spin_is_locked (&lock->wait_lock));DEBUG_LOCKS_WARN_ON (list_empty (&lock->wait_list));DEBUG_LOCKS_WARN_ON (waiter->magic != waiter);DEBUG_LOCKS_WARN_ON (list_empty (&waiter->list));
@@ -51,7 +51,7 @@ void debug_mutex_free_waiter(struct mutex_waiter *waiter)void debug_mutex_add_waiter (struct mutex *lock,struct mutex_waiter *waiter,struct task_struct *task) { -SMP_DEBUG_LOCKS_WARN_ON (!spin_is_locked (&lock->wait_lock)); +SMP_DEBUG_LOCKS_WARN_ON (!raw_spin_is_locked (&lock->wait_lock));/* Mark the current thread as blocked on the lock: */ task->blocked_on = waiter;
kernel/locking/mutex.c +11 -11
@@ -39,7 +39,7 @@ void __mutex_init(struct mutex *lock, const char *name, struct lock_class_key *key) { atomic_long_set(&lock->owner, 0); -spin_lock_init (&lock->wait_lock); +raw_spin_lock_init (&lock->wait_lock);INIT_LIST_HEAD (&lock->wait_list);#ifdef CONFIG_MUTEX_SPIN_ON_OWNER osq_lock_init (&lock->osq);
@@ -464,9 +464,9 @@ ww_mutex_set_context_fastpath(struct ww_mutex *lock, struct ww_acquire_ctx *ctx)* Uh oh, we raced in fastpath, check if any of the waiters need to * die or wound us. */ -spin_lock (&lock->base.wait_lock); +raw_spin_lock (&lock->base.wait_lock);__ww_mutex_check_waiters (&lock->base, ctx); -spin_unlock (&lock->base.wait_lock); +raw_spin_unlock (&lock->base.wait_lock); }#ifdef CONFIG_MUTEX_SPIN_ON_OWNER
@@ -934,7 +934,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,return 0 ; } -spin_lock (&lock->wait_lock); +raw_spin_lock (&lock->wait_lock);/* * After waiting to acquire the wait_lock, try again. */
@@ -998,7 +998,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, goto err; } -spin_unlock (&lock->wait_lock); +raw_spin_unlock (&lock->wait_lock);schedule_preempt_disabled ();/*
@@ -1021,9 +1021,9 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, (first && mutex_optimistic_spin(lock, ww_ctx, use_ww_ctx, &waiter))) break; -spin_lock (&lock->wait_lock); +raw_spin_lock (&lock->wait_lock); } -spin_lock (&lock->wait_lock); +raw_spin_lock (&lock->wait_lock); acquired:__set_current_state (TASK_RUNNING );
@@ -1050,7 +1050,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,if (use_ww_ctx && ww_ctx)ww_mutex_lock_acquired (ww, ww_ctx); -spin_unlock (&lock->wait_lock); +raw_spin_unlock (&lock->wait_lock);preempt_enable ();return 0 ;
@@ -1058,7 +1058,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,__set_current_state (TASK_RUNNING );mutex_remove_waiter (lock, &waiter, current); err_early_kill: -spin_unlock (&lock->wait_lock); +raw_spin_unlock (&lock->wait_lock);debug_mutex_free_waiter (&waiter);mutex_release (&lock->dep_map,1 , ip);preempt_enable ();
@@ -1227,7 +1227,7 @@ static noinline void __sched __mutex_unlock_slowpath(struct mutex *lock, unsigne owner = old; } -spin_lock (&lock->wait_lock); +raw_spin_lock (&lock->wait_lock);debug_mutex_unlock (lock);if (!list_empty (&lock->wait_list)) {/* get the first entry from the wait-list: */
@@ -1244,7 +1244,7 @@ static noinline void __sched __mutex_unlock_slowpath(struct mutex *lock, unsigneif (owner &MUTEX_FLAG_HANDOFF )__mutex_handoff (lock, next); -spin_unlock (&lock->wait_lock); +raw_spin_unlock (&lock->wait_lock);wake_up_q (&wake_q); }
Signature · 1 line
2.17.1
Juri Lelli
maintainerPATCH 2/8 locking/mutex: Removes wakeups from under mutex::wait_lock
In reply to Juri LelliFrom: Peter Zijlstra <[email protected]>
In preparation to nest mutex::wait_lock under rq::lock we need to remove wakeups from under it.
[Heavily changed after 55f036ca7e74 ("locking: WW mutex cleanup") and 08295b3b5bee ("locking: Implement an algorithm choice for Wound-Wait mutexes")]
--- kernel/locking/mutex.c | 43 +++++++++++++++++++++++++++--------------- 1 file changed, 28 insertions(+), 15 deletions(-)
kernel/locking/mutex.c +28 -15
@@ -338,7 +338,7 @@ __ww_ctx_stamp_after(struct ww_acquire_ctx *a, struct ww_acquire_ctx *b)*/ static bool __sched__ww_mutex_die (struct mutex *lock,struct mutex_waiter *waiter, -struct ww_acquire_ctx *ww_ctx) +struct ww_acquire_ctx *ww_ctx,struct wake_q_head *wake_q) {if (!ww_ctx->is_wait_die)return false;
@@ -346,7 +346,7 @@ __ww_mutex_die(struct mutex *lock, struct mutex_waiter *waiter,if (waiter->ww_ctx->acquired >0 &&__ww_ctx_stamp_after (waiter->ww_ctx, ww_ctx)) {debug_mutex_wake_waiter (lock, waiter); -wake_up_process (waiter->task); +wake_q_add (wake_q, waiter->task);// XXX }return true;
@@ -361,7 +361,8 @@ __ww_mutex_die(struct mutex *lock, struct mutex_waiter *waiter,*/ static bool __ww_mutex_wound (struct mutex *lock,struct ww_acquire_ctx *ww_ctx, -struct ww_acquire_ctx *hold_ctx) +struct ww_acquire_ctx *hold_ctx, +struct wake_q_head *wake_q) {struct task_struct *owner =__mutex_owner (lock);
@@ -393,7 +394,7 @@ static bool __ww_mutex_wound(struct mutex *lock,* wakeup pending to re-read the wounded state. */ if (owner != current) -wake_up_process (owner); +wake_q_add (wake_q, owner);// XXX return true; }
@@ -414,7 +415,9 @@ static bool __ww_mutex_wound(struct mutex *lock,* The current task must not be on the wait list. */ static void __sched -__ww_mutex_check_waiters (struct mutex *lock,struct ww_acquire_ctx *ww_ctx) +__ww_mutex_check_waiters (struct mutex *lock, +struct ww_acquire_ctx *ww_ctx, +struct wake_q_head *wake_q) {struct mutex_waiter *cur;
@@ -424,8 +427,8 @@ __ww_mutex_check_waiters(struct mutex *lock, struct ww_acquire_ctx *ww_ctx)if (!cur->ww_ctx)continue ; -if (__ww_mutex_die (lock, cur, ww_ctx) || -__ww_mutex_wound (lock, cur->ww_ctx, ww_ctx)) +if (__ww_mutex_die (lock, cur, ww_ctx, wake_q) || +__ww_mutex_wound (lock, cur->ww_ctx, ww_ctx, wake_q))break ; } }
@@ -437,6 +440,8 @@ __ww_mutex_check_waiters(struct mutex *lock, struct ww_acquire_ctx *ww_ctx) static __always_inline voidww_mutex_set_context_fastpath (struct ww_mutex *lock,struct ww_acquire_ctx *ctx) { +DEFINE_WAKE_Q (wake_q); +ww_mutex_lock_acquired (lock, ctx);/*
@@ -465,8 +470,10 @@ ww_mutex_set_context_fastpath(struct ww_mutex *lock, struct ww_acquire_ctx *ctx)* die or wound us. */ raw_spin_lock (&lock->base.wait_lock); -__ww_mutex_check_waiters (&lock->base, ctx); +__ww_mutex_check_waiters (&lock->base, ctx, &wake_q);raw_spin_unlock (&lock->base.wait_lock); + +wake_up_q (&wake_q); }#ifdef CONFIG_MUTEX_SPIN_ON_OWNER
@@ -824,7 +831,8 @@ __ww_mutex_check_kill(struct mutex *lock, struct mutex_waiter *waiter, static inline int __sched__ww_mutex_add_waiter (struct mutex_waiter *waiter,struct mutex *lock, -struct ww_acquire_ctx *ww_ctx) +struct ww_acquire_ctx *ww_ctx, +struct wake_q_head *wake_q) {struct mutex_waiter *cur;struct list_head *pos;
@@ -868,7 +876,7 @@ __ww_mutex_add_waiter(struct mutex_waiter *waiter, pos = &cur->list;/* Wait-Die: ensure younger waiters die. */ -__ww_mutex_die (lock, cur, ww_ctx); +__ww_mutex_die (lock, cur, ww_ctx, wake_q); }__mutex_add_waiter (lock, waiter, pos);
@@ -886,7 +894,7 @@ __ww_mutex_add_waiter(struct mutex_waiter *waiter,* such that either we or the fastpath will wound @ww->ctx. */ smp_mb (); -__ww_mutex_wound (lock, ww_ctx, ww->ctx); +__ww_mutex_wound (lock, ww_ctx, ww->ctx, wake_q); }return 0 ;
@@ -900,6 +908,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, struct lockdep_map *nest_lock, unsigned long ip, struct ww_acquire_ctx *ww_ctx, const bool use_ww_ctx) { +DEFINE_WAKE_Q (wake_q );struct mutex_waiter waiter;bool first = false;struct ww_mutex *ww;
@@ -940,7 +949,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,*/ if (__mutex_trylock (lock)) {if (use_ww_ctx && ww_ctx) -__ww_mutex_check_waiters (lock, ww_ctx); +__ww_mutex_check_waiters (lock, ww_ctx, &wake_q); goto skip_wait; }
@@ -962,7 +971,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,* Add in stamp order, waking up waiters that must kill * themselves. */ - ret =__ww_mutex_add_waiter (&waiter, lock, ww_ctx); + ret =__ww_mutex_add_waiter (&waiter, lock, ww_ctx, &wake_q);if (ret) goto err_early_kill;
@@ -1034,7 +1043,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,*/ if (!ww_ctx->is_wait_die && !__mutex_waiter_is_first (lock, &waiter)) -__ww_mutex_check_waiters (lock, ww_ctx); +__ww_mutex_check_waiters (lock, ww_ctx, &wake_q); }mutex_remove_waiter (lock, &waiter, current);
@@ -1051,6 +1060,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,ww_mutex_lock_acquired (ww, ww_ctx);raw_spin_unlock (&lock->wait_lock); +wake_up_q (&wake_q);preempt_enable ();return 0 ;
@@ -1061,6 +1071,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,raw_spin_unlock (&lock->wait_lock);debug_mutex_free_waiter (&waiter);mutex_release (&lock->dep_map,1 , ip); +wake_up_q (&wake_q);preempt_enable ();return ret; }
@@ -1244,9 +1255,11 @@ static noinline void __sched __mutex_unlock_slowpath(struct mutex *lock, unsigneif (owner &MUTEX_FLAG_HANDOFF )__mutex_handoff (lock, next); +preempt_disable ();// XXX unlock->wakeup inversion like raw_spin_unlock (&lock->wait_lock); -wake_up_q (&wake_q); +wake_up_q (&wake_q);// XXX must force resched on proxy +preempt_enable (); }#ifndef CONFIG_DEBUG_LOCK_ALLOC
Signature · 1 line
2.17.1
Juri Lelli
maintainerPATCH 3/8 locking/mutex: Rework task_struct::blocked_on
In reply to Juri LelliFrom: Peter Zijlstra <[email protected]>
Track the blocked-on relation for mutexes, this allows following this relation at schedule time. Add blocked_task to track the inverse relation.
,-> task
| | blocked-on
| v
blocked-task | mutex
| | owner
| v
`-- taskThis patch only enables blocked-on relation, blocked-task will be enabled in a later patch implementing proxy().
--- include/linux/sched.h | 6 ++---- kernel/fork.c | 6 +++--- kernel/locking/mutex-debug.c | 7 +++---- kernel/locking/mutex.c | 3 +++ 4 files changed, 11 insertions(+), 11 deletions(-)
include/linux/sched.h +2 -4
@@ -907,10 +907,8 @@ struct task_struct {struct rt_mutex_waiter *pi_blocked_on;#endif -#ifdef CONFIG_DEBUG_MUTEXES -/* Mutex deadlock detection: */ -struct mutex_waiter *blocked_on; -#endif +struct task_struct *blocked_task;/* task that's boosting us */ +struct mutex *blocked_on;/* lock we're blocked on */ #ifdef CONFIG_TRACE_IRQFLAGS unsigned int irq_events;
kernel/fork.c +3 -3
@@ -1827,9 +1827,9 @@ static __latent_entropy struct task_struct *copy_process(lockdep_init_task (p);#endif -#ifdef CONFIG_DEBUG_MUTEXES - p->blocked_on =NULL ;/* not blocked yet */ -#endif + p->blocked_task =NULL ;/* nobody is boosting us yet*/ + p->blocked_on =NULL ;/* not blocked yet */ +#ifdef CONFIG_BCACHE p->sequential_io =0 ; p->sequential_io_avg =0 ;
kernel/locking/mutex-debug.c +3 -4
@@ -53,8 +53,8 @@ void debug_mutex_add_waiter(struct mutex *lock, struct mutex_waiter *waiter, {SMP_DEBUG_LOCKS_WARN_ON (!raw_spin_is_locked (&lock->wait_lock)); -/* Mark the current thread as blocked on the lock: */ - task->blocked_on = waiter; +/* Current thread can't be alredy blocked (since it's executing!) */ +DEBUG_LOCKS_WARN_ON (task->blocked_on); } void mutex_remove_waiter(struct mutex *lock, struct mutex_waiter *waiter,
@@ -62,8 +62,7 @@ void mutex_remove_waiter(struct mutex *lock, struct mutex_waiter *waiter, {DEBUG_LOCKS_WARN_ON (list_empty (&waiter->list));DEBUG_LOCKS_WARN_ON (waiter->task != task); -DEBUG_LOCKS_WARN_ON (task->blocked_on != waiter); - task->blocked_on =NULL ; +DEBUG_LOCKS_WARN_ON (task->blocked_on != lock);list_del_init (&waiter->list); waiter->task =NULL ;
kernel/locking/mutex.c +3 -0
@@ -979,6 +979,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, } waiter.task = current; + current->blocked_on = lock;set_current_state (state);for (;;) {
@@ -1047,6 +1048,8 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, }mutex_remove_waiter (lock, &waiter, current); + current->blocked_on =NULL ; +if (likely (list_empty (&lock->wait_list)))__mutex_clear_flag (lock,MUTEX_FLAGS );
Signature · 1 line
2.17.1
Re: [RFD/RFC PATCH 3/8] locking/mutex: Rework task_struct::blocked_on
Hi,
Quoted 6 lines · On Tue, 9 Oct 2018 11:24:29 +0200 Juri Lelli <[email protected]> wrote:
From: Peter Zijlstra <[email protected]>
Track the blocked-on relation for mutexes, this allows following this relation at schedule time. Add
blocked_taskto track the inverse relation.
Quoted 7 lines
,-> task
| | blocked-on
| vblocked-task | mutex | | owner | v `-- task
I was a little bit confused by this description, because (if I understand the code well) blocked_task does not actually track the inverse of the "blocked_on" relationship, but just points to the task that is _currently_ acting as a proxy for a given task.
In theory, we could have multiple tasks blocked on "mutex" (which is owned by "task"), so if "blocked_task" tracked the inverse of "blocked_on" it should have been a list (or a data structure containing pointers to multiple task structures), no?
I would propose to change "blocked_task" into something like "current_proxy", or similar, which should be more clear (unless I completely misunderstood this stuff... In that case, sorry about the noise)
Also, I suspect that this "blocked_task" (or "current_proxy") field should be introcuced in patch 5 (same for the "task_is_blocked()" function from patch 4... Should it go in patch 5?)
Luca
Quoted 96 lines
This patch only enables blocked-on relation, blocked-task will be enabled in a later patch implementing
proxy().Signed-off-by Peter Zijlstra (Intel) <[email protected]>[minor changes while rebasing]Signed-off-by Juri Lelli <[email protected]>--- include/linux/sched.h | 6 ++---- kernel/fork.c | 6 +++--- kernel/locking/mutex-debug.c | 7 +++---- kernel/locking/mutex.c | 3 +++ 4 files changed, 11 insertions(+), 11 deletions(-)include/linux/sched.h +1
-4@@ -907,10 +907,8 @@ struct task_struct {struct rt_mutex_waiter *pi_blocked_on;#endif -#ifdef CONFIG_DEBUG_MUTEXES -/* Mutex deadlock detection: */ -struct mutex_waiter *blocked_on; -#endif +struct task_struct *blocked_task;/* task that's boosting us */
include/linux/sched.h +1
-0+struct mutex *blocked_on;/* lock we're blocked on */
#ifdefCONFIG_TRACE_IRQFLAGSinclude/linux/sched.h +0
-0unsigned int irq_events;kernel/fork.c +3
-3@@ -1827,9 +1827,9 @@ static __latent_entropy struct task_struct *copy_process( lockdep_init_task(p);#endif -#ifdef CONFIG_DEBUG_MUTEXES - p->blocked_on =NULL ;/* not blocked yet */ -#endif + p->blocked_task =NULL ;/* nobody is boosting us yet*/ + p->blocked_on =NULL ;/* not blocked yet */ +#ifdef CONFIG_BCACHE p->sequential_io =0 ; p->sequential_io_avg =0 ;(quoted diff) +0
-0
b/kernel/locking/mutex-debug.cindexa660d38b6c29..6605e083a3e9100644kernel/locking/mutex-debug.c +1
-2@@ -53,8 +53,8 @@ void debug_mutex_add_waiter(struct mutex *lock, struct mutex_waiter *waiter, {SMP_DEBUG_LOCKS_WARN_ON (!raw_spin_is_locked (&lock->wait_lock)); -/* Mark the current thread as blocked on the lock: */ - task->blocked_on = waiter; +/* Current thread can't be alredy blocked (since it's executing!) */
kernel/locking/mutex-debug.c +1
-0+DEBUG_LOCKS_WARN_ON (task->blocked_on); } void mutex_remove_waiter(struct mutex *lock, struct mutex_waiter*waiter, @@ -62,8 +62,7 @@ void mutex_remove_waiter(struct mutex *lock, struct
mutex_waiter*waiter, {kernel/locking/mutex-debug.c +1
-2DEBUG_LOCKS_WARN_ON (list_empty (&waiter->list));DEBUG_LOCKS_WARN_ON (waiter->task != task); -DEBUG_LOCKS_WARN_ON (task->blocked_on != waiter); - task->blocked_on =NULL ; +DEBUG_LOCKS_WARN_ON (task->blocked_on != lock);list_del_init (&waiter->list); waiter->task =NULL ;kernel/locking/mutex.c +3
-0@@ -979,6 +979,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, } waiter.task = current; + current->blocked_on = lock;set_current_state (state);for (;;) {@@ -1047,6 +1048,8 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, }mutex_remove_waiter (lock, &waiter, current); + current->blocked_on =NULL ; +if (likely (list_empty (&lock->wait_list)))__mutex_clear_flag (lock,MUTEX_FLAGS );
Juri Lelli
maintainerRe: [RFD/RFC PATCH 3/8] locking/mutex: Rework task_struct::blocked_on
Quoted 29 lines · luca abeni
Hi,
Quoted 6 lines · On Tue, 9 Oct 2018 11:24:29 +0200 Juri Lelli <[email protected]> wrote:
From: Peter Zijlstra <[email protected]>
Track the blocked-on relation for mutexes, this allows following this relation at schedule time. Add
blocked_taskto track the inverse relation.Quoted 7 lines
,-> task
| | blocked-on
| vblocked-task | mutex | | owner | v `-- taskI was a little bit confused by this description, because (if I understand the code well)
blocked_taskdoes not actually track the inverse of the "blocked_on" relationship, but just points to the task that is _currently_ acting as a proxy for a given task.In theory, we could have multiple tasks blocked on "mutex" (which is owned by "task"), so if "
blocked_task" tracked the inverse of "blocked_on" it should have been a list (or a data structure containing pointers to multiple task structures), no?
Quoted 4 lines
I would propose to change "
blocked_task" into something like "current_proxy", or similar, which should be more clear (unless I completely misunderstood this stuff... In that case, sorry about the noise)
Makes sense to me. It looks also closer to what comment says.
Quoted 3 lines
Also, I suspect that this "
blocked_task" (or "current_proxy") field should be introcuced in patch 5 (same for the "task_is_blocked()" function from patch 4... Should it go in patch 5?)
Sure. I believe I might have wrongly split things while rebasing. Will fix.
Thanks,
- Juri
Juri Lelli
maintainerPATCH 4/8 sched: Split scheduler execution context
In reply to Juri LelliFrom: Peter Zijlstra <[email protected]>
Lets define the scheduling context as all the scheduler state in task_struct and the execution context as all state required to run the task.
Currently both are intertwined in task_struct. We want to logically split these such that we can run the execution context of one task with the scheduling context of another.
To this purpose introduce rq::proxy to point to the task_struct used for scheduler state and preserve rq::curr to denote the execution context.
--- kernel/sched/core.c | 62 ++++++++++++++++++++++++++++++++++---------- kernel/sched/fair.c | 4 +++ kernel/sched/sched.h | 30 ++++++++++++++++++++- 3 files changed, 82 insertions(+), 14 deletions(-)
kernel/sched/core.c +49 -13
@@ -224,12 +224,13 @@ static enum hrtimer_restart hrtick(struct hrtimer *timer) { struct rq *rq = container_of(timer, struct rq, hrtick_timer);struct rq_flags rf; +struct task_struct *curr = rq->proxy;WARN_ON_ONCE (cpu_of (rq) !=smp_processor_id ());rq_lock (rq, &rf);update_rq_clock (rq); - rq->curr->sched_class->task_tick (rq, rq->curr,1 ); + curr->sched_class->task_tick (rq, curr,1 );rq_unlock (rq, &rf);return HRTIMER_NORESTART ;
@@ -836,13 +837,18 @@ static inline void check_class_changed(struct rq *rq, struct task_struct *p,void check_preempt_curr (struct rq *rq,struct task_struct *p,int flags) { +struct task_struct *curr = rq->proxy;const struct sched_class *class; -if (p->sched_class == rq->curr->sched_class) { - rq->curr->sched_class->check_preempt_curr (rq, p, flags); +if (p->sched_class == curr->sched_class) { +/* +* XXX check_preempt_curr will check rq->curr against p, looks +* like we want to check rq->proxy against p though? +*/ + curr->sched_class->check_preempt_curr (rq, p, flags); }else {for_each_class (class) { -if (class == rq->curr->sched_class) +if (class == curr->sched_class)break ;if (class == p->sched_class) {resched_curr (rq);
@@ -855,7 +861,7 @@ void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags)* A queue event has occurred, and we're going to schedule. In * this case, we can save a useless back to back clock update. */ -if (task_on_rq_queued (rq->curr) &&test_tsk_need_resched (rq->curr)) +if (task_on_rq_queued (curr) &&test_tsk_need_resched (rq->curr))rq_clock_skip_update (rq); }
@@ -1016,7 +1022,11 @@ void do_set_cpus_allowed(struct task_struct *p, const struct cpumask *new_mask)lockdep_assert_held (&p->pi_lock); queued =task_on_rq_queued (p); - running =task_current (rq, p); +/* +* XXX is changing affinity of a proxy a problem? +* Consider for example put_prev_ set_curr_ below... +*/ + running =task_current_proxy (rq, p);if (queued) {/*
@@ -3021,7 +3031,7 @@ unsigned long long task_sched_runtime(struct task_struct *p)* project cycles that may never be accounted to this * thread, breaking clock_gettime(). */ -if (task_current (rq, p) &&task_on_rq_queued (p)) { +if (task_current_proxy (rq, p) &&task_on_rq_queued (p)) {prefetch_curr_exec_start (p);update_rq_clock (rq); p->sched_class->update_curr (rq);
@@ -3040,8 +3050,9 @@ void scheduler_tick(void) {int cpu =smp_processor_id ();struct rq *rq =cpu_rq (cpu); -struct task_struct *curr = rq->curr;struct rq_flags rf; +/* accounting goes to the proxy task */ +struct task_struct *curr = rq->proxy;sched_clock_tick ();
@@ -3096,6 +3107,13 @@ static void sched_tick_remote(struct work_struct *work)if (is_idle_task (curr)) goto out_unlock; +/* +* XXX don't we need to account to rq->proxy? +* Maybe, since this is a remote tick for full dynticks mode, we are +* always sure that there is no proxy (only a single task is running. +*/ +SCHED_WARN_ON (rq->curr != rq->proxy); +update_rq_clock (rq); delta =rq_clock_task (rq) - curr->se.exec_start;
@@ -3804,7 +3822,10 @@ void rt_mutex_setprio(struct task_struct *p, struct task_struct *pi_task) prev_class = p->sched_class; queued =task_on_rq_queued (p); - running =task_current (rq, p); +/* +* XXX how does (proxy exec) mutexes and RT_mutexes work together?! +*/ + running =task_current_proxy (rq, p);if (queued)dequeue_task (rq, p, queue_flag);if (running)
@@ -3891,7 +3912,10 @@ void set_user_nice(struct task_struct *p, long nice) goto out_unlock; } queued =task_on_rq_queued (p); - running =task_current (rq, p); +/* +* XXX see concerns about do_set_cpus_allowed, rt_mutex_prio & Co. +*/ + running =task_current_proxy (rq, p);if (queued)dequeue_task (rq, p,DEQUEUE_SAVE |DEQUEUE_NOCLOCK );if (running)
@@ -4318,7 +4342,10 @@ static int __sched_setscheduler(struct task_struct *p, } queued =task_on_rq_queued (p); - running =task_current (rq, p); +/* +* XXX and again, how is this safe w.r.t. proxy exec? +*/ + running =task_current_proxy (rq, p);if (queued)dequeue_task (rq, p, queue_flags);if (running)
@@ -4938,6 +4965,11 @@ static void do_sched_yield(void)rq_lock (rq, &rf);schedstat_inc (rq->yld_count); +/* +* XXX how about proxy exec? +* If a task currently proxied by some other task yields, should we +* apply the proxy or the current yield "behaviour" ? +*/ current->sched_class->yield_task (rq);/*
@@ -5044,6 +5076,10 @@ EXPORT_SYMBOL(yield);*/ int __sched yield_to(struct task_struct *p, bool preempt) { +/* +* XXX what about current being proxied? +* Should we use proxy->sched_class methods in this case? +*/ struct task_struct *curr = current;struct rq *rq, *p_rq;unsigned long flags;
@@ -5502,7 +5538,7 @@ void sched_setnuma(struct task_struct *p, int nid) rq =task_rq_lock (p, &rf); queued =task_on_rq_queued (p); - running =task_current (rq, p); + running =task_current_proxy (rq, p);if (queued)dequeue_task (rq, p,DEQUEUE_SAVE );
@@ -6351,7 +6387,7 @@ void sched_move_task(struct task_struct *tsk) rq =task_rq_lock (tsk, &rf);update_rq_clock (rq); - running =task_current (rq, tsk); + running =task_current_proxy (rq, tsk); queued =task_on_rq_queued (tsk);if (queued)
kernel/sched/fair.c +4 -0
@@ -9721,6 +9721,10 @@ static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)entity_tick (cfs_rq, se, queued); } +/* +* XXX need to use execution context (rq->curr) for task_tick_numa and +* update_misfit_status? +*/ if (static_branch_unlikely (&sched_numa_balancing))task_tick_numa (rq, curr);
kernel/sched/sched.h +29 -1
@@ -824,7 +824,8 @@ struct rq {*/ unsigned long nr_uninterruptible; -struct task_struct *curr; +struct task_struct *curr;/* Execution context */ +struct task_struct *proxy;/* Scheduling context (policy) */ struct task_struct *idle;struct task_struct *stop;unsigned long next_balance;
@@ -1421,11 +1422,38 @@ static inline u64 global_rt_runtime(void)return (u64 )sysctl_sched_rt_runtime *NSEC_PER_USEC ; } +/* +* Is p the current execution context? +*/ static inline int task_current (struct rq *rq,struct task_struct *p) {return rq->curr == p; } +/* +* Is p the current scheduling context? +* +* Note that it might be the current execution context at the same time if +* rq->curr == rq->proxy == p. +*/ +static inline int task_current_proxy (struct rq *rq,struct task_struct *p) +{ +return rq->proxy == p; +} + +#ifdef CONFIG_PROXY_EXEC +static inline bool task_is_blocked (struct task_struct *p) +{ +return !!p->blocked_on; +} +#else /* !PROXY_EXEC */ +static inline bool task_is_blocked (struct task_struct *p) +{ +return false; +} + +#endif /* PROXY_EXEC */ +static inline int task_running (struct rq *rq,struct task_struct *p) {#ifdef CONFIG_SMP
Signature · 1 line
2.17.1
Re: [RFD/RFC PATCH 4/8] sched: Split scheduler execution context
Dear Juri,
just a small comment for the next round of patches (I guess after OSPM)...
Quoted 28 lines · Juri Lelli
From: Peter Zijlstra <[email protected]>
Lets define the scheduling context as all the scheduler state in
task_structand the execution context as all state required to run the task.Currently both are intertwined in
task_struct. We want to logically split these such that we can run the execution context of one task with the scheduling context of another.To this purpose introduce
rq::proxyto point to thetask_structused for scheduler state and preserverq::currto denote the execution context.Signed-off-by Peter Zijlstra (Intel) <[email protected]>[added lot of comments/questions - identifiable by XXX]Signed-off-by Juri Lelli <[email protected]>--- kernel/sched/core.c | 62 ++++++++++++++++++++++++++++++++++---------- kernel/sched/fair.c | 4 +++ kernel/sched/sched.h | 30 ++++++++++++++++++++- 3 files changed, 82 insertions(+), 14 deletions(-)kernel/sched/core.c +0
-0
kernel/sched/core.c static enum hrtimer_restart hrtick(struct hrtimer *timer) · line 227
Quoted 4 lines
kernel/sched/core.c +1
-0@@ -224,12 +224,13 @@ static enum hrtimer_restart hrtick(struct hrtimer *timer) { struct rq *rq = container_of(timer, struct rq, hrtick_timer);struct rq_flags rf; +struct task_struct *curr = rq->proxy;
You may want to use a different naming for these local variables (e.g. "proxy") to help the reader in not confusing curr (i.e. scheduling ctx) with rq::curr (i.e. execution ctx).
Best regards,
Claudio
Juri Lelli
maintainerPATCH 5/8 sched: Add proxy execution
In reply to Juri LelliFrom: Peter Zijlstra <[email protected]>
A task currently holding a mutex (executing a critical section) might find benefit in using scheduling contexts of other tasks blocked on the same mutex if they happen to have higher priority of the current owner (e.g., to prevent priority inversions).
Proxy execution lets a task do exactly that: if a mutex owner has waiters, it can use waiters' scheduling context to potentially continue running if preempted.
The basic mechanism is implemented by this patch, the core of which resides in the proxy() function. Potential proxies (i.e., tasks blocked on a mutex) are not dequeued, so, if one of them is actually selected by schedule() as the next task to be put to run on a CPU, proxy() is used to walk the blocked_on relation and find which task (mutex owner) might be able to use the proxy's scheduling context.
Here come the tricky bits. In fact, owner task might be in all sort of states when a proxy is found (blocked, executing on a different CPU, etc.). Details on how to handle different situations are to be found in proxy() code comments.
--- include/linux/sched.h | 2 + init/Kconfig | 4 + init/init_task.c | 1 + kernel/Kconfig.locks | 2 +- kernel/fork.c | 2 + kernel/locking/mutex.c | 47 ++++- kernel/sched/core.c | 408 ++++++++++++++++++++++++++++++++++++++-- kernel/sched/deadline.c | 2 +- kernel/sched/fair.c | 3 + kernel/sched/rt.c | 2 +- 10 files changed, 455 insertions(+), 18 deletions(-)
include/linux/sched.h +2 -0
@@ -909,6 +909,8 @@ struct task_struct {struct task_struct *blocked_task;/* task that's boosting us */ struct mutex *blocked_on;/* lock we're blocked on */ +struct list_head blocked_entry;/* tasks blocked on us */ +raw_spinlock_t blocked_lock;#ifdef CONFIG_TRACE_IRQFLAGS unsigned int irq_events;
init/Kconfig +4 -0
@@ -667,6 +667,10 @@ config NUMA_BALANCING_DEFAULT_ENABLED If set, automatic NUMA balancing will be enabled if running on a NUMA machine. +config PROXY_EXEC + bool "Proxy Execution" + default n + menuconfig CGROUPS bool "Control Group support" select KERNFS
init/init_task.c +1 -0
@@ -117,6 +117,7 @@ struct task_struct init_task .journal_info = NULL,INIT_CPU_TIMERS (init_task) .pi_lock =__RAW_SPIN_LOCK_UNLOCKED (init_task.pi_lock), + .blocked_lock = __RAW_SPIN_LOCK_UNLOCKED(init_task.blocked_lock), .timer_slack_ns = 50000, /* 50 usec default slack */ .thread_pid = &init_struct_pid, .thread_group = LIST_HEAD_INIT(init_task.thread_group),
kernel/Kconfig.locks +1 -1
@@ -225,7 +225,7 @@ config ARCH_SUPPORTS_ATOMIC_RMW config MUTEX_SPIN_ON_OWNER def_bool y - depends on SMP && ARCH_SUPPORTS_ATOMIC_RMW + depends on SMP && ARCH_SUPPORTS_ATOMIC_RMW && !PROXY_EXEC config RWSEM_SPIN_ON_OWNER def_bool y
kernel/fork.c +2 -0
@@ -1723,6 +1723,7 @@ static __latent_entropy struct task_struct *copy_process(ftrace_graph_init_task (p);rt_mutex_init_task (p); +raw_spin_lock_init (&p->blocked_lock);#ifdef CONFIG_PROVE_LOCKING DEBUG_LOCKS_WARN_ON (!p->hardirqs_enabled);
@@ -1829,6 +1830,7 @@ static __latent_entropy struct task_struct *copy_process( p->blocked_task =NULL ;/* nobody is boosting us yet*/ p->blocked_on =NULL ;/* not blocked yet */ +INIT_LIST_HEAD (&p->blocked_entry);#ifdef CONFIG_BCACHE p->sequential_io =0 ;
kernel/locking/mutex.c +45 -2
77 lines not on this page · raw message
kernel/sched/core.c +395 -13
447 lines not on this page · raw message
kernel/sched/deadline.c +1 -1
@@ -1499,7 +1499,7 @@ static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags)enqueue_dl_entity (&p->dl, pi_se, flags); -if (!task_current (rq, p) && p->nr_cpus_allowed >1 ) +if (!task_current (rq, p) && p->nr_cpus_allowed >1 && !task_is_blocked (p))enqueue_pushable_dl_task (rq, p); }
kernel/sched/fair.c +3 -0
@@ -7043,6 +7043,9 @@ int can_migrate_task(struct task_struct *p, struct lb_env *env)lockdep_assert_held (&env->src_rq->lock); +if (task_is_blocked (p)) +return 0 ; +/* * We do not migrate tasks that are: * 1) throttled_lb_pair, or
kernel/sched/rt.c +1 -1
@@ -1334,7 +1334,7 @@ enqueue_task_rt(struct rq *rq, struct task_struct *p, int flags)enqueue_rt_entity (rt_se, flags); -if (!task_current (rq, p) && p->nr_cpus_allowed >1 ) +if (!task_current (rq, p) && p->nr_cpus_allowed >1 && !task_is_blocked (p))enqueue_pushable_task (rq, p); }
Signature · 1 line
2.17.1
Re: [RFD/RFC PATCH 5/8] sched: Add proxy execution
Hi,
On Tue, 9 Oct 2018 11:24:31 +0200
Juri Lelli <[email protected]> wrote:
[...]
Quoted 1 line
+migrate_task:
[...]
kernel/sched/core.c pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) · line 3578
Quoted 11 lines
kernel/sched/core.c +6
-0+put_prev_task (rq, next); +if (rq->curr != rq->idle) { + rq->proxy = rq->idle; +set_tsk_need_resched (rq->idle); +/* +* XXX [juril] don't we still need to migrate @next to
kernel/sched/core.c +4
-0+* @owner's CPU? +*/ +return rq->idle; + }
If I understand well, this code ends up migrating the task only if the CPU was previously idle? (scheduling the idle task if the CPU was not previously idle)
Out of curiosity (I admit this is my ignorance), why is this needed? If I understand well, after scheduling the idle task the scheduler will be invoked again (because of the set_tsk_need_resched(rq->idle)) but I do not understand why it is not possible to migrate task "p" immediately (I would just check "rq->curr != p", to avoid migrating the currently scheduled task).
Thanks,
Luca
Quoted 273 lines
kernel/sched/core.c +12
-0+ rq->proxy = &fake_task; + +for (; p; p = p->blocked_task) { +int wake_cpu = p->wake_cpu; + +WARN_ON (p == rq->curr); + + p->on_rq =TASK_ON_RQ_MIGRATING ; +dequeue_task (rq, p,0 ); +set_task_cpu (p, that_cpu); +/* +* We can abuse blocked_entry to migrate the thing, because @p is
kernel/sched/core.c +6
-0+* still on the rq. +*/ +list_add (&p->blocked_entry, &migrate_list); + +/* +* Preserve p->wake_cpu, such that we can tell where it
kernel/sched/core.c +11
-0+* used to run later. +*/ + p->wake_cpu = wake_cpu; + } + +rq_unpin_lock (rq, rf); +raw_spin_unlock (&rq->lock); +raw_spin_lock (&that_rq->lock); + +while (!list_empty (&migrate_list)) { + p = list_first_entry(&migrate_list, struct
task_struct,blocked_entry);kernel/sched/core.c +33
-0+list_del_init (&p->blocked_entry); + +enqueue_task (that_rq, p,0 ); +check_preempt_curr (that_rq, p,0 ); + p->on_rq =TASK_ON_RQ_QUEUED ; +resched_curr (that_rq); + } + +raw_spin_unlock (&that_rq->lock); +raw_spin_lock (&rq->lock); +rq_repin_lock (rq, rf); + +return NULL ;/* Retry task selection on _this_ CPU. */ + +owned_task: +/* +* Its possible we interleave with mutex_unlock like: +* +* lock(&rq->lock); +* proxy() +* mutex_unlock() +* lock(&wait_lock); +* next(owner) = current->blocked_task; +* unlock(&wait_lock); +* +* wake_up_q(); +* ... +* ttwu_remote() +* __task_rq_lock() +* lock(&wait_lock); +* owner == p +* +* Which leaves us to finish the ttwu_remote() and make it go.
kernel/sched/core.c +3
-0+* +* XXX is this happening in case of an HANDOFF to p? +* In any case, reading of the owner in
__mutex_unlock_slowpathis(quoted diff) +1
-0+ * done atomically outside wait_lock (only adding waiters to
wake_qis(quoted diff) +2
-0+ * done inside the critical section). + * Does this means we can get to proxy _w/o an owner_ ifthat was
(quoted diff) +1
-0+ * cleared before grabbing wait_lock? Do we account for thiscase?
(quoted diff) +1
-0+ * OK we actually do (see PROXY_EXEC ifdeffery in unlockfunction).
kernel/sched/core.c +30
-0+*/ + +/* +* Finish wakeup, will make the contending ttwu do a +* _spurious_ wakeup, but all code should be able to +* deal with that. +*/ + owner->blocked_on =NULL ; + owner->state =TASK_RUNNING ; +// XXX task_woken + +/* +* If @owner/@p is allowed to run on this CPU, make it go. +*/ +if (cpumask_test_cpu (this_cpu, &owner->cpus_allowed)) { +raw_spin_unlock (&mutex->wait_lock); +return owner; + } + +/* +* We have to let ttwu fix things up, because we +* can't restore the affinity. So dequeue. +*/ + owner->on_rq =0 ; +deactivate_task (rq, p,DEQUEUE_SLEEP ); + goto blocked_task; + +blocked_task: +/* +* If !@owner->on_rq, holding @rq->lock will not pin the task,
(quoted diff) +1
-0+ * so we cannot drop @mutex->wait_lock until we're sure itsa blocked
kernel/sched/core.c +3
-0+* task on this rq. +* +* We use @owner->blocked_lock to serialize against
ttwu_activate().(quoted diff) +1
-0+ * Either we see its new owner->on_rq or it will see our
list_add().kernel/sched/core.c +5
-0+*/ +raw_spin_lock (&owner->blocked_lock); + +/* +* If we became runnable while waiting for blocked_lock, retry.
kernel/sched/core.c +4
-0+*/ +if (owner->on_rq) { +/* +* If we see the new on->rq, we must also see the new
task_cpu().kernel/sched/core.c +7
-0+*/ +raw_spin_unlock (&owner->blocked_lock); + goto retry_owner; + } + +/* +* Walk back up the blocked_task relation and enqueue them all on @owner
(quoted diff) +2
-0+ * + * ttwu_activate() will pick them up and place them onwhatever rq
kernel/sched/core.c +27
-6+* @owner will run next. +*/ +for (; p; p = p->blocked_task) { + p->on_rq =0 ; +deactivate_task (rq, p,DEQUEUE_SLEEP ); +list_add (&p->blocked_entry, &owner->blocked_entry); + } +raw_spin_unlock (&owner->blocked_lock); +raw_spin_unlock (&mutex->wait_lock); + + return NULL; /* retry task selection */ +} +#else /* PROXY_EXEC */ +static struct task_struct * +proxy (struct rq *rq,struct task_struct *next,struct rq_flags *rf) +{ +return next; +} +#endif /* PROXY_EXEC */ +/* * __schedule() is the main scheduler function. * @@ -3439,12 +3798,19 @@ static void __sched notrace __schedule(bool preempt) if (unlikely(signal_pending_state(prev->state, prev))) { prev->state =TASK_RUNNING ; }else { -deactivate_task (rq, prev,DEQUEUE_SLEEP | DEQUEUE_NOCLOCK); - prev->on_rq =0 ; - -if (prev->in_iowait) { -atomic_inc (&rq->nr_iowait); -delayacct_blkio_start (); +if (!task_is_blocked (prev)) { + prev->on_rq =0 ; +deactivate_task (rq, prev,DEQUEUE_SLEEP |DEQUEUE_NOCLOCK ); + }else { +/* +* XXX +* Let's make this task, which is blocked on
(quoted diff) +2
-0+ * a mutex, (push/pull)able (RT/DL). + * Unfortunately we can only dealwith that by
(quoted diff) +1
-0+ * means of a dequeue/enqueuecycle. :-/
kernel/sched/core.c +6
-1+*/ +dequeue_task (rq, prev,0 ); +enqueue_task (rq, prev,0 ); }/* @@ -3463,7 +3829,23 @@ static void __sched notrace __schedule(bool preempt) switch_count = &prev->nvcsw; } - next =pick_next_task (rq, prev, &rf); +pick_again: +/* +* If picked task is actually blocked it means that it can act as a
(quoted diff) +1
-0+ * proxy for the task that is holding the mutex picked taskis blocked
(quoted diff) +1
-0+ * on. Get a reference to the blocked (going to be proxy)task here.
(quoted diff) +1
-0+ * Note that if next isn't actually blocked we will have
rq->proxy==(quoted diff) +1
-0+ * rq->curr == next in the end, which is intended and meansthat proxy
kernel/sched/core.c +11
-1+* execution is currently "not in use". +*/ + rq->proxy = next =pick_next_task (rq, rq->proxy, &rf); + next->blocked_task =NULL ; +if (unlikely (task_is_blocked (next))) { + next =proxy (rq, next, &rf); +if (!next) + goto pick_again; + } +clear_tsk_need_resched (prev);clear_preempt_need_resched ();@@ -5441,7 +5823,7 @@ void init_idle(struct task_struct *idle, int cpu) __set_task_cpu(idle, cpu);rcu_read_unlock (); - rq->curr = rq->idle = idle; + rq->curr = rq->proxy = rq->idle = idle; idle->on_rq =TASK_ON_RQ_QUEUED ;#ifdef CONFIG_SMP idle->on_cpu =1 ;kernel/sched/deadline.c +1
-1@@ -1499,7 +1499,7 @@ static void enqueue_task_dl(struct rq *rq, struct task_struct *p, int flags) enqueue_dl_entity(&p->dl, pi_se, flags); -if (!task_current (rq, p) && p->nr_cpus_allowed >1 ) +if (!task_current (rq, p) && p->nr_cpus_allowed >1 && !task_is_blocked (p))enqueue_pushable_dl_task (rq, p); }kernel/sched/fair.c +3
-0@@ -7043,6 +7043,9 @@ int can_migrate_task(struct task_struct *p, struct lb_env *env) lockdep_assert_held(&env->src_rq->lock); +if (task_is_blocked (p)) +return 0 ; +/* * We do not migrate tasks that are: * 1) throttled_lb_pair, or kernel/sched/rt.c +1
-1@@ -1334,7 +1334,7 @@ enqueue_task_rt(struct rq *rq, struct task_struct *p, int flags)enqueue_rt_entity (rt_se ,flags ); -if (!task_current (rq, p) && p->nr_cpus_allowed >1 ) +if (!task_current (rq, p) && p->nr_cpus_allowed >1 && !task_is_blocked (p))enqueue_pushable_task (rq, p); }
Juri Lelli
maintainerRe: [RFD/RFC PATCH 5/8] sched: Add proxy execution
Hi Luca,
Quoted 23 lines · luca abeni
Hi,
On Tue, 9 Oct 2018 11:24:31 +0200
Juri Lelli <[email protected]> wrote:
[...]Quoted 1 line
+migrate_task:
[...]
kernel/sched/core.c pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) · line 3578
Quoted 11 lines
kernel/sched/core.c +6
-0+put_prev_task (rq, next); +if (rq->curr != rq->idle) { + rq->proxy = rq->idle; +set_tsk_need_resched (rq->idle); +/* +* XXX [juril] don't we still need to migrate @next to
kernel/sched/core.c +4
-0+* @owner's CPU? +*/ +return rq->idle; + }If I understand well, this code ends up migrating the task only if the CPU was previously idle? (scheduling the idle task if the CPU was not previously idle)
Quoted 6 lines
Out of curiosity (I admit this is my ignorance), why is this needed? If I understand well, after scheduling the idle task the scheduler will be invoked again (because of the
set_tsk_need_resched(rq->idle)) but I do not understand why it is not possible to migrate task "p" immediately (I would just check "rq->curr!= p", to avoid migrating the currently scheduled task).
As the comment suggests, I was also puzzled by this bit.
I'd be inclined to agree with you, it seems that the only case in which we want to "temporarily" schedule the idle task is if the proxy was executing (so it just blocked on the mutex and being scheduled out).
If it wasn't we should be able to let the current "curr" continue executing, in this case returning it as next will mean that schedule takes the else branch and there isn't an actual context switch.
Quoted 1 line
kernel/sched/core.c pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) · line 3579
Quoted 1 line
kernel/sched/core.c +1
-0+ rq->proxy = &fake_task;
[...]
We can maybe also rq->proxy = rq->curr and return rq->curr in such a case, instead of the below?
Quoted 1 line
kernel/sched/core.c pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) · line 3620
Quoted 1 line
kernel/sched/core.c +1
-0+return NULL ;/* Retry task selection on _this_ CPU. */
Peter, what are we missing? :-)
Peter Zijlstra
maintainerRe: [RFD/RFC PATCH 5/8] sched: Add proxy execution
Quoted 47 lines · Juri Lelli
Hi Luca,
Quoted 23 lines · luca abeni
Hi,
On Tue, 9 Oct 2018 11:24:31 +0200
Juri Lelli <[email protected]> wrote:
[...]Quoted 1 line
+migrate_task:
[...]
kernel/sched/core.c pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) · line 3578
Quoted 11 lines
kernel/sched/core.c +6
-0+put_prev_task (rq, next); +if (rq->curr != rq->idle) { + rq->proxy = rq->idle; +set_tsk_need_resched (rq->idle); +/* +* XXX [juril] don't we still need to migrate @next to
kernel/sched/core.c +4
-0+* @owner's CPU? +*/ +return rq->idle; + }If I understand well, this code ends up migrating the task only if the CPU was previously idle? (scheduling the idle task if the CPU was not previously idle)
Quoted 6 lines
Out of curiosity (I admit this is my ignorance), why is this needed? If I understand well, after scheduling the idle task the scheduler will be invoked again (because of the
set_tsk_need_resched(rq->idle)) but I do not understand why it is not possible to migrate task "p" immediately (I would just check "rq->curr!= p", to avoid migrating the currently scheduled task).As the comment suggests, I was also puzzled by this bit.
I'd be inclined to agree with you, it seems that the only case in which we want to "temporarily" schedule the idle task is if the proxy was executing (so it just blocked on the mutex and being scheduled out).
If it wasn't we should be able to let the current "curr" continue executing, in this case returning it as next will mean that schedule takes the else branch and there isn't an actual context switch.
Quoted 1 line
Quoted 1 line
kernel/sched/core.c +1
-0+ rq->proxy = &fake_task;[...]
Quoted 6 lines
We can maybe also
rq->proxy=rq->currand returnrq->currin such a case, instead of the below?Quoted 1 line
kernel/sched/core.c pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) · line 3620
Quoted 1 line
kernel/sched/core.c +1
-0+return NULL ;/* Retry task selection on _this_ CPU. */ Peter, what are we missing? :-)
I think it was the safe and simple choice; note that we're not migrating just a single @p, but a whole chain of @p. rq->curr must not be any of the possible @p's. rq->idle, is per definition not one of the @p's.
Does that make sense?
Juri Lelli
maintainerRe: [RFD/RFC PATCH 5/8] sched: Add proxy execution
On 11/10/18 14:53, Peter Zijlstra wrote:
[...]
Quoted 5 lines
I think it was the safe and simple choice; note that we're not migrating just a single @p, but a whole chain of @p.
rq->currmust not be any of the possible @p's.rq->idle, is per definition not one of the @p's.Does that make sense?
It does, and I guess is most probably the safest choice indeed. But, just to put together a proper comment for next version..
The chain we are migrating is composed of blocked_task(s), so tasks that blocked on a mutex owned by @p. Now, if such a chain has been built, it means that proxy() has been called "for" @p previously, and @p might be curr while one of its waiters might be proxy. So, none of the blocked_ task(s) should be rq->curr (even if one of their scheduling context might be in use)?
Re: [RFD/RFC PATCH 5/8] sched: Add proxy execution
In reply to Peter ZijlstraOn Thu, 11 Oct 2018 14:53:25 +0200
Peter Zijlstra <[email protected]> wrote:
[...]
Quoted 22 lines
Quoted 22 lines
Quoted 22 lines
kernel/sched/core.c pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) · line 3578
Quoted 10 lines
kernel/sched/core.c +5
-0+if (rq->curr != rq->idle) { + rq->proxy = rq->idle; +set_tsk_need_resched (rq->idle); +/* +* XXX [juril] don't we still need to migrate @next to
kernel/sched/core.c +4
-0+* @owner's CPU? +*/ +return rq->idle; + }If I understand well, this code ends up migrating the task only if the CPU was previously idle? (scheduling the idle task if the CPU was not previously idle)
Out of curiosity (I admit this is my ignorance), why is this needed? If I understand well, after scheduling the idle task the scheduler will be invoked again (because of the
set_tsk_need_resched(rq->idle)) but I do not understand why it is not possible to migrate task "p" immediately (I would just check "rq->curr!= p", to avoid migrating the currently scheduled task).
[...]
Quoted 2 lines
I think it was the safe and simple choice; note that we're not migrating just a single @p, but a whole chain of @p.
Ah, that's the point I was missing... Thanks for explaining, now everything looks more clear!
But... Here is my next dumb question: once the tasks are migrated to the other runqueue, what prevents the scheduler from migrating them back? In particular, task p: if it is (for example) a fixed priority task an is on this runqueue, it is probably because the FP invariant wants this... So, the push mechanism might end up migrating p back to this runqueue soon... No?
Another doubt: if I understand well, when a task p "blocks" on a mutex the proxy mechanism migrates it (and the whole chain of blocked tasks) to the owner's core... Right?
Now, I understand why this is simpler to implement, but from the schedulability point of view shouldn't we migrate the owner to p's core instead?
Thanks,
Luca
Quoted 5 lines
rq->currmust
not be any of the possible @p's.rq->idle, is per definition not one of the @p's.Does that make sense?
Juri Lelli
maintainerRe: [RFD/RFC PATCH 5/8] sched: Add proxy execution
Quoted 34 lines · luca abeni
On Thu, 11 Oct 2018 14:53:25 +0200
Peter Zijlstra <[email protected]> wrote:[...]
Quoted 22 lines
Quoted 22 lines
Quoted 22 lines
kernel/sched/core.c pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) · line 3578
Quoted 10 lines
kernel/sched/core.c +5
-0+if (rq->curr != rq->idle) { + rq->proxy = rq->idle; +set_tsk_need_resched (rq->idle); +/* +* XXX [juril] don't we still need to migrate @next to
kernel/sched/core.c +4
-0+* @owner's CPU? +*/ +return rq->idle; + }If I understand well, this code ends up migrating the task only if the CPU was previously idle? (scheduling the idle task if the CPU was not previously idle)
Out of curiosity (I admit this is my ignorance), why is this needed? If I understand well, after scheduling the idle task the scheduler will be invoked again (because of the
set_tsk_need_resched(rq->idle)) but I do not understand why it is not possible to migrate task "p" immediately (I would just check "rq->curr!= p", to avoid migrating the currently scheduled task).[...]
Quoted 2 lines
I think it was the safe and simple choice; note that we're not migrating just a single @p, but a whole chain of @p.
Ah, that's the point I was missing... Thanks for explaining, now everything looks more clear!
Quoted 6 lines
But... Here is my next dumb question: once the tasks are migrated to the other runqueue, what prevents the scheduler from migrating them back? In particular, task p: if it is (for example) a fixed priority task an is on this runqueue, it is probably because the FP invariant wants this... So, the push mechanism might end up migrating p back to this runqueue soon... No?
Not if p is going to be proxying for owner on owner's rq. OTOH, I guess we might have counter-migrations generated by push/pull decisions. Maybe we should remove potential proxies from pushable? We'd still have the same problem for FAIR though.
In general it seems to make sense to me the fact that potential proxies shouldn't participate to load balancing while waiting to be activated by the mutex owner; they are basically sleeping, even if they are not.
Quoted 6 lines
Another doubt: if I understand well, when a task p "blocks" on a mutex the proxy mechanism migrates it (and the whole chain of blocked tasks) to the owner's core... Right?
Now, I understand why this is simpler to implement, but from the schedulability point of view shouldn't we migrate the owner to p's core instead?
Guess the most important reason is that we need to respect owner's affinity, p (and the rest of the list) might have affinity mask that doesn't work well with owner's.
Juri Lelli
maintainerPATCH 6/8 locking/mutex: make mutex::wait_lock irq safe
In reply to Juri Lellimutex::wait_lock might be nested under rq->lock.
Make it irq safe then.
--- kernel/locking/mutex.c | 23 +++++++++++++---------- 1 file changed, 13 insertions(+), 10 deletions(-)
kernel/locking/mutex.c +13 -10
@@ -444,6 +444,7 @@ __ww_mutex_check_waiters(struct mutex *lock, static __always_inline voidww_mutex_set_context_fastpath (struct ww_mutex *lock,struct ww_acquire_ctx *ctx) { +unsigned long flags;DEFINE_WAKE_Q (wake_q);ww_mutex_lock_acquired (lock, ctx);
@@ -473,9 +474,9 @@ ww_mutex_set_context_fastpath(struct ww_mutex *lock, struct ww_acquire_ctx *ctx)* Uh oh, we raced in fastpath, check if any of the waiters need to * die or wound us. */ -raw_spin_lock (&lock->base.wait_lock); +raw_spin_lock_irqsave (&lock->base.wait_lock, flags);__ww_mutex_check_waiters (&lock->base, ctx, &wake_q); -raw_spin_unlock (&lock->base.wait_lock); +raw_spin_unlock_irqrestore (&lock->base.wait_lock, flags);wake_up_q (&wake_q); }
@@ -917,6 +918,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,bool first = false;struct ww_mutex *ww;int ret; +unsigned long flags;might_sleep ();
@@ -947,7 +949,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,return 0 ; } -raw_spin_lock (&lock->wait_lock); +raw_spin_lock_irqsave (&lock->wait_lock, flags);/* * After waiting to acquire the wait_lock, try again. */
@@ -1012,7 +1014,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, goto err; } -raw_spin_unlock (&lock->wait_lock); +raw_spin_unlock_irqrestore (&lock->wait_lock, flags);schedule_preempt_disabled ();/*
@@ -1039,9 +1041,9 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, (first && mutex_optimistic_spin(lock, ww_ctx, use_ww_ctx, &waiter))) break; -raw_spin_lock (&lock->wait_lock); +raw_spin_lock_irqsave (&lock->wait_lock, flags); } -raw_spin_lock (&lock->wait_lock); +raw_spin_lock_irqsave (&lock->wait_lock, flags); acquired:__set_current_state (TASK_RUNNING );
@@ -1070,7 +1072,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,if (use_ww_ctx && ww_ctx)ww_mutex_lock_acquired (ww, ww_ctx); -raw_spin_unlock (&lock->wait_lock); +raw_spin_unlock_irqrestore (&lock->wait_lock, flags);wake_up_q (&wake_q);preempt_enable ();return 0 ;
@@ -1079,7 +1081,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,__set_current_state (TASK_RUNNING );mutex_remove_waiter (lock, &waiter, current); err_early_kill: -raw_spin_unlock (&lock->wait_lock); +raw_spin_unlock_irqrestore (&lock->wait_lock, flags);debug_mutex_free_waiter (&waiter);mutex_release (&lock->dep_map,1 , ip);wake_up_q (&wake_q);
@@ -1220,6 +1222,7 @@ static noinline void __sched __mutex_unlock_slowpath(struct mutex *lock, unsigne* conditional on having proxy exec configured in? */ unsigned long owner =MUTEX_FLAG_HANDOFF ; +unsigned long flags;mutex_release (&lock->dep_map,1 , ip);
@@ -1261,7 +1264,7 @@ static noinline void __sched __mutex_unlock_slowpath(struct mutex *lock, unsigne }#endif -raw_spin_lock (&lock->wait_lock); +raw_spin_lock_irqsave (&lock->wait_lock, flags);debug_mutex_unlock (lock);#ifdef CONFIG_PROXY_EXEC
@@ -1302,7 +1305,7 @@ static noinline void __sched __mutex_unlock_slowpath(struct mutex *lock, unsigne__mutex_handoff (lock, next);preempt_disable ();// XXX unlock->wakeup inversion like -raw_spin_unlock (&lock->wait_lock); +raw_spin_unlock_irqrestore (&lock->wait_lock, flags);wake_up_q (&wake_q);// XXX must force resched on proxy preempt_enable ();
Signature · 1 line
2.17.1
Juri Lelli
maintainerPATCH 7/8 sched: Ensure blocked_on is always guarded by blocked_lock
In reply to Juri Lelliblocked_on pointer might be concurrently modified by schedule() (when proxy() is called) and by wakeup path, so we need to guard changes.
Ensure blocked_lock is always held before updating blocked_on pointer.
--- kernel/locking/mutex-debug.c | 1 + kernel/locking/mutex.c | 13 ++++++++++--- kernel/sched/core.c | 31 ++++++++++++++++++++++++++++++- 3 files changed, 41 insertions(+), 4 deletions(-)
kernel/locking/mutex-debug.c +1 -0
@@ -62,6 +62,7 @@ void mutex_remove_waiter(struct mutex *lock, struct mutex_waiter *waiter, {DEBUG_LOCKS_WARN_ON (list_empty (&waiter->list));DEBUG_LOCKS_WARN_ON (waiter->task != task); +DEBUG_LOCKS_WARN_ON (task->blocked_on ==NULL );DEBUG_LOCKS_WARN_ON (task->blocked_on != lock);list_del_init (&waiter->list);
kernel/locking/mutex.c +10 -3
@@ -950,6 +950,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, }raw_spin_lock_irqsave (&lock->wait_lock, flags); +raw_spin_lock (¤t->blocked_lock);/* * After waiting to acquire the wait_lock, try again. */
@@ -1014,6 +1015,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass, goto err; } +raw_spin_unlock (¤t->blocked_lock);raw_spin_unlock_irqrestore (&lock->wait_lock, flags);schedule_preempt_disabled ();
@@ -1027,6 +1029,8 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,__mutex_set_flag (lock,MUTEX_FLAG_HANDOFF ); } +raw_spin_lock_irqsave (&lock->wait_lock, flags); +raw_spin_lock (¤t->blocked_lock);/* * Gets reset by ttwu_remote(). */
@@ -1040,10 +1044,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,if (__mutex_trylock (lock) || (first &&mutex_optimistic_spin (lock, ww_ctx, use_ww_ctx, &waiter)))break ; - -raw_spin_lock_irqsave (&lock->wait_lock, flags); } -raw_spin_lock_irqsave (&lock->wait_lock, flags); acquired:__set_current_state (TASK_RUNNING );
@@ -1072,6 +1073,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,if (use_ww_ctx && ww_ctx)ww_mutex_lock_acquired (ww, ww_ctx); +raw_spin_unlock (¤t->blocked_lock);raw_spin_unlock_irqrestore (&lock->wait_lock, flags);wake_up_q (&wake_q);preempt_enable ();
@@ -1081,6 +1083,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,__set_current_state (TASK_RUNNING );mutex_remove_waiter (lock, &waiter, current); err_early_kill: +raw_spin_unlock (¤t->blocked_lock);raw_spin_unlock_irqrestore (&lock->wait_lock, flags);debug_mutex_free_waiter (&waiter);mutex_release (&lock->dep_map,1 , ip);
@@ -1268,6 +1271,7 @@ static noinline void __sched __mutex_unlock_slowpath(struct mutex *lock, unsignedebug_mutex_unlock (lock);#ifdef CONFIG_PROXY_EXEC +raw_spin_lock (¤t->blocked_lock);/* * If we have a task boosting us, and that task was boosting us through * this lock, hand the lock that that task, as that is the highest
@@ -1305,6 +1309,9 @@ static noinline void __sched __mutex_unlock_slowpath(struct mutex *lock, unsigne__mutex_handoff (lock, next);preempt_disable ();// XXX unlock->wakeup inversion like +#ifdef CONFIG_PROXY_EXEC +raw_spin_unlock (¤t->blocked_lock); +#endif raw_spin_unlock_irqrestore (&lock->wait_lock, flags);wake_up_q (&wake_q);// XXX must force resched on proxy
kernel/sched/core.c +30 -1
@@ -1761,7 +1761,15 @@ static int ttwu_remote(struct task_struct *p, int wake_flags)* trigger the on_rq_queued() clause for them. */ if (task_is_blocked (p)) { - p->blocked_on =NULL ;/* let it run again */ +raw_spin_lock (&p->blocked_lock); + +if (task_is_blocked (p)) { + p->blocked_on =NULL ;/* let it run again */ + }else { +raw_spin_unlock (&p->blocked_lock); + goto out_wakeup; + } +if (!cpumask_test_cpu (cpu_of (rq), &p->cpus_allowed)) {/* * proxy stuff moved us outside of the affinity mask
@@ -1771,6 +1779,7 @@ static int ttwu_remote(struct task_struct *p, int wake_flags) p->on_rq =0 ;/* XXX [juril] SLEEP|NOCLOCK ? */ deactivate_task (rq, p,DEQUEUE_SLEEP ); +raw_spin_unlock (&p->blocked_lock); goto out_unlock; }
@@ -1779,8 +1788,10 @@ static int ttwu_remote(struct task_struct *p, int wake_flags)* executing context might not be the most elegible anymore. */ resched_curr (rq); +raw_spin_unlock (&p->blocked_lock); } +out_wakeup:ttwu_do_wakeup (rq, p, wake_flags, &rf); ret =1 ;
@@ -3464,12 +3475,26 @@ proxy(struct rq *rq, struct task_struct *next, struct rq_flags *rf)*/ for (p = next; p->blocked_on; p = owner) { mutex = p->blocked_on; +if (!mutex) +return NULL ;/* * By taking mutex->wait_lock we hold off concurrent mutex_unlock() * and ensure @owner sticks around. */ raw_spin_lock (&mutex->wait_lock); +raw_spin_lock (&p->blocked_lock); + +/* Check again that p is blocked with blocked_lock held */ +if (task_is_blocked (p)) { +BUG_ON (mutex != p->blocked_on); + }else { +/* Something changed in the blocked_on chain */ +raw_spin_unlock (&p->blocked_lock); +raw_spin_unlock (&mutex->wait_lock); +return NULL ; + } + owner =__mutex_owner (mutex);/* * XXX can't this be 0|FLAGS? See __mutex_unlock_slowpath for(;;)
@@ -3491,6 +3516,7 @@ proxy(struct rq *rq, struct task_struct *next, struct rq_flags *rf)* on this rq, therefore holding @rq->lock is sufficient to * guarantee its existence, as per ttwu_remote(). */ +raw_spin_unlock (&p->blocked_lock);raw_spin_unlock (&mutex->wait_lock); owner->blocked_task = p;
@@ -3537,6 +3563,7 @@ proxy(struct rq *rq, struct task_struct *next, struct rq_flags *rf)* @owner can disappear, simply migrate to @that_cpu and leave that CPU * to sort things out. */ +raw_spin_unlock (&p->blocked_lock);raw_spin_unlock (&mutex->wait_lock);/*
@@ -3661,6 +3688,7 @@ proxy(struct rq *rq, struct task_struct *next, struct rq_flags *rf)* If @owner/@p is allowed to run on this CPU, make it go. */ if (cpumask_test_cpu (this_cpu, &owner->cpus_allowed)) { +raw_spin_unlock (&p->blocked_lock);raw_spin_unlock (&mutex->wait_lock);return owner; }
@@ -3682,6 +3710,7 @@ proxy(struct rq *rq, struct task_struct *next, struct rq_flags *rf)* We use @owner->blocked_lock to serialize against ttwu_activate(). * Either we see its new owner->on_rq or it will see our list_add(). */ +raw_spin_unlock (&p->blocked_lock);raw_spin_lock (&owner->blocked_lock);/*
Signature · 1 line
2.17.1
Juri Lelli
maintainerPATCH 8/8 sched: Fixup task CPUs for potential proxies.
In reply to Juri LelliWhen a mutex owner with potential proxies wakes up those proxies are activated as well, on the same CPU of the owner. They might have been sleeping on a different CPU however.
Fixup potential proxies CPU at wakeup time before activating them (or they get woken up with a wrong CPU reference).
--- kernel/sched/core.c | 11 ++++++++++- 1 file changed, 10 insertions(+), 1 deletion(-)
kernel/sched/core.c +10 -1
@@ -1664,6 +1664,14 @@ static inline void ttwu_activate(struct rq *rq, struct task_struct *p, int en_fl blocked_entry);list_del_init (&pp->blocked_entry); +/* XXX can't call set_task_cpu() because we are not holding +* neither pp->pi_lock nor task's rq lock. This should however +* be fine as this task can't be woken up as it is blocked on +* this mutex atm. +* A problem however might be that __set_task_cpu() calls +* set_task_rq() which deals with groups and such... +*/ +__set_task_cpu (pp,cpu_of (rq));activate_task (rq, pp, en_flags); pp->on_rq =TASK_ON_RQ_QUEUED ;resched_curr (rq);
@@ -3847,7 +3855,8 @@ static void __sched notrace __schedule(bool preempt)* whether it wants to wake up a task to maintain * concurrency. */ -if (prev->flags &PF_WQ_WORKER ) { +if ((prev->flags &PF_WQ_WORKER ) && + !task_is_blocked (prev)) {struct task_struct *to_wakeup; to_wakeup =wq_worker_sleeping (prev);
Signature · 1 line
2.17.1
Peter Zijlstra
maintainerQuoted 10 lines · Juri Lelli
The main concerns I have with the current approach is that, being based on
mutex.c, it's both- not linked with futexes
- not involving "legacy" priority inheritance (rt_mutex.c)I believe one of the main reasons Peter started this on mutexes is to have better coverage of potential problems (which I can assure everybody it had). I'm not yet sure what should we do moving forward, and this is exactly what I'd be pleased to hear your opinions on.
Well that, and mutex was 'simple', I didn't have to go rip out all the legacy PI crud.
If this all ends up working well, the solution is 'simple' and we can simply copy mutex to rt_mutex or something along those lines if we want to keep the distinction between them. Alternatively we simply delete rt_mutex.
Thanks for reviving this.. it's been an 'interesting' year and a half since I wrote all this and I've really not had time to work on it.
Juri Lelli
maintainerQuoted 7 lines · Peter Zijlstra
Quoted 6 lines · Juri Lelli
The main concerns I have with the current approach is that, being based on
mutex.c, it's both- not linked with futexes
- not involving "legacy" priority inheritance (rt_mutex.c)
Quoted 7 lines
Quoted 4 lines
I believe one of the main reasons Peter started this on mutexes is to have better coverage of potential problems (which I can assure everybody it had). I'm not yet sure what should we do moving forward, and this is exactly what I'd be pleased to hear your opinions on.
Well that, and mutex was 'simple', I didn't have to go rip out all the legacy PI crud.
Indeed.
Quoted 4 lines
If this all ends up working well, the solution is 'simple' and we can simply copy mutex to
rt_mutexor something along those lines if we want to keep the distinction between them. Alternatively we simply deletert_mutex.
Ah.. right.. sounds *scary*, but I guess it might be an option after all.
Quoted 2 lines
Thanks for reviving this.. it's been an 'interesting' year and a half since I wrote all this and I've really not had time to work on it.
n/p, it has been a long standing thing to look at for me as well. Thanks again for sharing your patches!
Quoted 10 lines · Juri Lelli
The main concerns I have with the current approach is that, being based on
mutex.c, it's both- not linked with futexes
- not involving "legacy" priority inheritance (rt_mutex.c)I believe one of the main reasons Peter started this on mutexes is to have better coverage of potential problems (which I can assure everybody it had). I'm not yet sure what should we do moving forward, and this is exactly what I'd be pleased to hear your opinions on.
wasn't the idea that once it works to get rid of rt_mutex?
Sebastian
Quoted 11 lines · Sebastian Andrzej Siewior
Quoted 10 lines
The main concerns I have with the current approach is that, being based on
mutex.c, it's both- not linked with futexes
- not involving "legacy" priority inheritance (rt_mutex.c)I believe one of the main reasons Peter started this on mutexes is to have better coverage of potential problems (which I can assure everybody it had). I'm not yet sure what should we do moving forward, and this is exactly what I'd be pleased to hear your opinions on.
wasn't the idea that once it works to get rid of
rt_mutex?
As far as I know, it is. But there are some additional complexity involving a -rt version of this patch, for instance:
What should the protocol do if the thread migrating is with migration disabled?
The side effects of, for instance, ignoring the migrate_disable() would add noise for the initial implementation... too much complexity at once.
IMHO, once it works in the non-rt, it will be easier to do the changes needed to integrate it with -rt.
Thoughts?
-- Daniel
Juri Lelli
maintainerQuoted 4 lines · Daniel Bristot de Oliveira
Quoted 3 lines · Sebastian Andrzej Siewior
Quoted 3 lines
The main concerns I have with the current approach is that, being based on
mutex.c, it's both
Quoted 8 lines
Quoted 8 lines
Quoted 7 lines
- not linked with futexes
- not involving "legacy" priority inheritance (rt_mutex.c)I believe one of the main reasons Peter started this on mutexes is to have better coverage of potential problems (which I can assure everybody it had). I'm not yet sure what should we do moving forward, and this is exactly what I'd be pleased to hear your opinions on.
wasn't the idea that once it works to get rid of
rt_mutex?
Looks like it was (see Peter's reply).
Quoted 6 lines
As far as I know, it is. But there are some additional complexity involving a -rt version of this patch, for instance:
What should the protocol do if the thread migrating is with migration disabled?
Quoted 7 lines
The side effects of, for instance, ignoring the
migrate_disable()would add noise for the initial implementation... too much complexity at once.IMHO, once it works in the non-rt, it will be easier to do the changes needed to integrate it with -rt.
Thoughts?
Makes sense to me. Maybe we should just still keep in mind eventual integration, so that we don't take decisions we would regret.
Hi all,
Quoted 8 lines · On Tue, 9 Oct 2018 11:24:26 +0200 Juri Lelli <[email protected]> wrote:
Hi all,
Proxy Execution (also goes under several other names) isn't a new concept, it has been mentioned already in the past to this community (both in email discussions and at conferences [1, 2]), but no actual implementation that applies to a fairly recent kernel exists as of today (of which I'm aware of at least - happy to be proven wrong).
Quoted 5 lines
Very broadly speaking, more info below, proxy execution enables a task to run using the context of some other task that is "willing" to participate in the mechanism, as this helps both tasks to improve performance (w.r.t. the latter task not participating to proxy execution).
First of all, thanks to Juri for working on this!
I am looking at the patchset, and I have some questions / comments (maybe some of my questions are really stupid, I do not know... :)
To begin, I have a very high-level comment about proxy execution: I believe proxy execution is a very powerful concept, that can be used in many cases, not only to do inheritance on mutual exclusion (think, for example, about pipelines of tasks: a task implementing a stage of the pipeline can act as a proxy for the task implementing the previous stage).
So, I would propose to make the proxy() function of patch more generic, and not strictly bound to mutexes. Maybe a task structure can contain a list of tasks for which the task can act as a proxy, and we can have a function like "I want to act as a proxy for task T" to be invoked when a task blocks?
Luca
Peter Zijlstra
maintainerQuoted 5 lines · luca abeni
So, I would propose to make the
proxy()function of patch more generic, and not strictly bound to mutexes. Maybe a task structure can contain a list of tasks for which the task can act as a proxy, and we can have a function like "I want to act as a proxy for task T" to be invoked when a task blocks?
Certainly possible, but that's something I'd prefer to look at after it all 'works'. The mutex blocking thing doesn't require external interfaces etc..
Quoted 9 lines · On Wed, 10 Oct 2018 12:57:10 +0200 Peter Zijlstra <[email protected]> wrote:
Quoted 5 lines · luca abeni
So, I would propose to make the
proxy()function of patch more generic, and not strictly bound to mutexes. Maybe a task structure can contain a list of tasks for which the task can act as a proxy, and we can have a function like "I want to act as a proxy for task T" to be invoked when a task blocks?Certainly possible, but that's something I'd prefer to look at after it all 'works'.
Of course :)
I was mentioning this idea because maybe it can have some impact on the design.
BTW, here is another "interesting" issue I had in the past with changes like this one: how do we check if the patchset works as expected?
"No crashes" is surely a requirement, but I think we also need some kind of testcase that fails if the inheritance mechanism is not working properly, and is successful if the inheritance works.
Maybe we can develop some testcase based on rt-app (if noone has such a testcase already)
Thanks,
Luca
Quoted 2 lines
The mutex blocking thing doesn't require external
interfaces etc..
Peter Zijlstra
maintainerQuoted 20 lines · luca abeni
Quoted 9 lines · On Wed, 10 Oct 2018 12:57:10 +0200 Peter Zijlstra <[email protected]> wrote:
Quoted 5 lines · luca abeni
So, I would propose to make the
proxy()function of patch more generic, and not strictly bound to mutexes. Maybe a task structure can contain a list of tasks for which the task can act as a proxy, and we can have a function like "I want to act as a proxy for task T" to be invoked when a task blocks?Certainly possible, but that's something I'd prefer to look at after it all 'works'.
Of course :)
I was mentioning this idea because maybe it can have some impact on the design.BTW, here is another "interesting" issue I had in the past with changes like this one: how do we check if the patchset works as expected?
Quoted 6 lines
"No crashes" is surely a requirement, but I think we also need some kind of testcase that fails if the inheritance mechanism is not working properly, and is successful if the inheritance works.
Maybe we can develop some testcase based on rt-app (if noone has such a testcase already)
Indeed; IIRC there is a test suite that mostly covers the FIFO-PI stuff, that should obviously still pass. Steve, do you know where that lives?
For the extended DL stuff, we'd need new tests.
Juri Lelli
maintainerQuoted 25 lines · Peter Zijlstra
Quoted 24 lines · luca abeni
Quoted 9 lines · On Wed, 10 Oct 2018 12:57:10 +0200 Peter Zijlstra <[email protected]> wrote:
Quoted 5 lines · luca abeni
So, I would propose to make the
proxy()function of patch more generic, and not strictly bound to mutexes. Maybe a task structure can contain a list of tasks for which the task can act as a proxy, and we can have a function like "I want to act as a proxy for task T" to be invoked when a task blocks?Certainly possible, but that's something I'd prefer to look at after it all 'works'.
Of course :)
I was mentioning this idea because maybe it can have some impact on the design.BTW, here is another "interesting" issue I had in the past with changes like this one: how do we check if the patchset works as expected?
"No crashes" is surely a requirement, but I think we also need some kind of testcase that fails if the inheritance mechanism is not working properly, and is successful if the inheritance works.
Quoted 7 lines
Quoted 2 lines
Maybe we can develop some testcase based on rt-app (if noone has such a testcase already)
Indeed; IIRC there is a test suite that mostly covers the FIFO-PI stuff, that should obviously still pass. Steve, do you know where that lives?
For the extended DL stuff, we'd need new tests.
This one, right?
It looks like it supports DEADLINE as well.. although I'll have to check again what it does for the DEADLINE case.
Quoted 1 line · Juri Lelli
Hi all,
Hi, nice series, I have a lot of details to grok, but I like the idea of PE
Quoted 11 lines
Proxy Execution (also goes under several other names) isn't a new concept, it has been mentioned already in the past to this community (both in email discussions and at conferences [1, 2]), but no actual implementation that applies to a fairly recent kernel exists as of today (of which I'm aware of at least - happy to be proven wrong).
Very broadly speaking, more info below, proxy execution enables a task to run using the context of some other task that is "willing" to participate in the mechanism, as this helps both tasks to improve performance (w.r.t. the latter task not participating to proxy execution).
From what I remember, PEP was originally proposed for a global EDF, and as far as my head has been able to read this series, this implementation is planned for not only deadline, but eventuall also for sched_(rr|fifo|other)
- is that correct?
I have a bit of concern when it comes to affinities and and where the lock owner will actually execute while in the context of the proxy, especially when you run into the situation where you have disjoint CPU affinities for _rr tasks to ensure the deadlines.
I believe there were some papers circulated last year that looked at something similar to this when you had overlapping or completely disjoint CPUsets I think it would be nice to drag into the discussion. Has this been considered? (if so, sorry for adding line-noise!)
Let me know if my attempt at translating brainlanguage into semi-coherent english failed and I'll do another attempt
Quoted 20 lines
This RFD/proof of concept aims at starting a discussion about how we can get proxy execution in mainline. But, first things first, why do we even care about it?
I'm pretty confident with saying that the line of development that is mainly interested in this at the moment is the one that might benefit in allowing non privileged processes to use deadline scheduling [3]. The main missing bit before we can safely relax the root privileges constraint is a proper priority inheritance mechanism, which translates to bandwidth inheritance [4, 5] for deadline scheduling, or to some sort of interpretation of the concept of running a task holding a (rt_)mutex within the bandwidth allotment of some other task that is blocked on the same (rt_)mutex.
The concept itself is pretty general however, and it is not hard to foresee possible applications in other scenarios (say for example nice values/shares across co-operating CFS tasks or clamping values [6]). But I'm already digressing, so let's get back to the code that comes with this cover letter.
Quoted 7 lines
One can define the scheduling context of a task as all the information in
task_structthat the scheduler needs to implement a policy and the execution contex as all the state required to actually "run" the task. An example of scheduling context might be the information contained intask_structse, rt and dl fields; affinity pertains instead to execution context (and I guess decideing what pertains to what is actually up for discussion as well ;-). Patch 04/08 implements such distinction.
I really like the idea of splitting scheduling ctx and execution context!
Quoted 21 lines
As implemented in this set, a link between scheduling contexts of different tasks might be established when a task blocks on a mutex held by some other task (
blocked_onrelation). In this case the former task starts to be considered a potential proxy for the latter (mutex owner). One key change in how mutexes work made in here is that waiters don't really sleep: they are not dequeued, so they can be picked up by the scheduler when it runs. If a waiter (potential proxy) task is selected by the scheduler, theblocked_onrelation is used to find the mutex owner and put that to run on the CPU, using the proxy task scheduling context.Follow the blocked-on relation:
,-> task <- proxy, picked by scheduler
| | blocked-on
| v
blocked-task | mutex
| | owner
| v
`-- task <- gets to run using proxy info
Quoted 6 lines
Now, the situation is (of course) more tricky than depicted so far because we have to deal with all sort of possible states the mutex owner might be in while a potential proxy is selected by the scheduler, e.g. owner might be sleeping, running on a different CPU, blocked on another mutex itself... so, I'd kindly refer people to have a look at 05/08
proxy()implementation and comments.
My head hurt already.. :)
Quoted 11 lines
Peter kindly shared his WIP patches with us (me, Luca, Tommaso, Claudio, Daniel, the Pisa gang) a while ago, but I could seriously have a decent look at them only recently (thanks a lot to the other guys for giving a first look at this way before me!). This set is thus composed of Peter's original patches (which I rebased on tip/sched/core as of today, commented and hopefully duly reported in changelogs what have I possibly broke) plus a bunch of additional changes that seemed required to make all this boot "successfully" on a virtual machine. So be advised! This is good only for fun ATM (I actually really hope this is good enough for discussion), pretty far from production I'm afraid. Share early, share often, right? :-)
I'll give it a spin and see if it boots, then I probably have a ton of extra questions :)
Thanks for sharing!
-Henrik
Peter Zijlstra
maintainerQuoted 17 lines · Henrik Austad
Quoted 1 line · Juri Lelli
Hi all,
Hi, nice series, I have a lot of details to grok, but I like the idea of PE
Quoted 11 lines
Proxy Execution (also goes under several other names) isn't a new concept, it has been mentioned already in the past to this community (both in email discussions and at conferences [1, 2]), but no actual implementation that applies to a fairly recent kernel exists as of today (of which I'm aware of at least - happy to be proven wrong).
Very broadly speaking, more info below, proxy execution enables a task to run using the context of some other task that is "willing" to participate in the mechanism, as this helps both tasks to improve performance (w.r.t. the latter task not participating to proxy execution).
Quoted 4 lines
From what I remember, PEP was originally proposed for a global EDF, and as far as my head has been able to read this series, this implementation is planned for not only deadline, but eventuall also for
sched_(rr|fifo|other)
- is that correct?
This implementation covers every scheduling class unconditionally. It directly uses the scheduling function to order things; where PI re-implements the FIFO scheduling function to order the blocked lists.
Quoted 4 lines
I have a bit of concern when it comes to affinities and and where the lock owner will actually execute while in the context of the proxy, especially when you run into the situation where you have disjoint CPU affinities for
_rrtasks to ensure the deadlines.
The affinities of execution contexts are respected.
Quoted 4 lines
I believe there were some papers circulated last year that looked at something similar to this when you had overlapping or completely disjoint CPUsets I think it would be nice to drag into the discussion. Has this been considered? (if so, sorry for adding line-noise!)
Hurm, was that one of Bjorn's papers? Didn't that deal with AC of disjoint/overlapping sets?
Quoted 9 lines
Quoted 7 lines
One can define the scheduling context of a task as all the information in
task_structthat the scheduler needs to implement a policy and the execution contex as all the state required to actually "run" the task. An example of scheduling context might be the information contained intask_structse, rt and dl fields; affinity pertains instead to execution context (and I guess decideing what pertains to what is actually up for discussion as well ;-). Patch 04/08 implements such distinction.I really like the idea of splitting scheduling ctx and execution context!
Right; so this whole thing relies on 'violating' affinities for scheduling contexts, but respects affinities for execution contexts.
The basic observation is that affinities only matter when you execute code.
This then also gives a fairly clear definition of what an execution context is.
Quoted 7 lines · Peter Zijlstra
Quoted 4 lines
I believe there were some papers circulated last year that looked at something similar to this when you had overlapping or completely disjoint CPUsets I think it would be nice to drag into the discussion. Has this been considered? (if so, sorry for adding line-noise!)
Hurm, was that one of Bjorn's papers? Didn't that deal with AC of disjoint/overlapping sets?
This paper:
https://people.mpi-sws.org/~bbb/papers/pdf/rtsj14.pdf
But, unless I am wrong, there were findings after this paper that shows some imprecision on it.
Anyway, it does not analyse the locking properties, only scheduler of independent tasks - it is a start, but far from what we do here.
(btw this paper is really complex...)
The locking problem for such case: APA with the nesting of different locks in the locking implementation (we use raw spin lock on this, and this method could also be used in the rw lock/sem in the future, nesting rw_lock(mutex_proxy(raw_spinlock())) is an open problem from the academic point of view.
I explained these things (nested lock and the need of APA for locking) as "Open Problems" at the RTSOPs (part of the ECRTS) earlier this year:
http://rtsops2018.loria.fr/wp-content/uploads/2018/07/RTSOPS18_proceedings_final.pdf
Bjorn were there, but not only him... Baruah, Davis, Alan Burns were there.
There are some works being done for more complex locking in academy, like:
https://www.cs.unc.edu/~jarretc/papers/ecrts18b_long.pdf
But still, the task model used on these implementations are not the Linux one.
-- Daniel
Juri Lelli
maintainerQuoted 17 lines · Henrik Austad
Quoted 1 line · Juri Lelli
Hi all,
Hi, nice series, I have a lot of details to grok, but I like the idea of PE
Quoted 11 lines
Proxy Execution (also goes under several other names) isn't a new concept, it has been mentioned already in the past to this community (both in email discussions and at conferences [1, 2]), but no actual implementation that applies to a fairly recent kernel exists as of today (of which I'm aware of at least - happy to be proven wrong).
Very broadly speaking, more info below, proxy execution enables a task to run using the context of some other task that is "willing" to participate in the mechanism, as this helps both tasks to improve performance (w.r.t. the latter task not participating to proxy execution).
Quoted 4 lines
From what I remember, PEP was originally proposed for a global EDF, and as far as my head has been able to read this series, this implementation is planned for not only deadline, but eventuall also for
sched_(rr|fifo|other)
- is that correct?
Correct, this is cross class.
Quoted 4 lines
I have a bit of concern when it comes to affinities and and where the lock owner will actually execute while in the context of the proxy, especially when you run into the situation where you have disjoint CPU affinities for
_rrtasks to ensure the deadlines.
Well, it's the (scheduler context) of the proxy that is potentially moved around. Lock owner stays inside its affinity.
Quoted 4 lines
I believe there were some papers circulated last year that looked at something similar to this when you had overlapping or completely disjoint CPUsets I think it would be nice to drag into the discussion. Has this been considered? (if so, sorry for adding line-noise!)
I think you refer to BBB work. Not sure if it applies here, though (considering what above).
Quoted 2 lines
Let me know if my attempt at translating brainlanguage into semi-coherent english failed and I'll do another attempt
You succeeded! (that's assuming that I got your questions right of course :)
Quoted 52 lines
Quoted 21 lines
This RFD/proof of concept aims at starting a discussion about how we can get proxy execution in mainline. But, first things first, why do we even care about it?
I'm pretty confident with saying that the line of development that is mainly interested in this at the moment is the one that might benefit in allowing non privileged processes to use deadline scheduling [3]. The main missing bit before we can safely relax the root privileges constraint is a proper priority inheritance mechanism, which translates to bandwidth inheritance [4, 5] for deadline scheduling, or to some sort of interpretation of the concept of running a task holding a (rt_)mutex within the bandwidth allotment of some other task that is blocked on the same (rt_)mutex.
The concept itself is pretty general however, and it is not hard to foresee possible applications in other scenarios (say for example nice values/shares across co-operating CFS tasks or clamping values [6]). But I'm already digressing, so let's get back to the code that comes with this cover letter.
Quoted 7 lines
One can define the scheduling context of a task as all the information in
task_structthat the scheduler needs to implement a policy and the execution contex as all the state required to actually "run" the task. An example of scheduling context might be the information contained intask_structse, rt and dl fields; affinity pertains instead to execution context (and I guess decideing what pertains to what is actually up for discussion as well ;-). Patch 04/08 implements such distinction.I really like the idea of splitting scheduling ctx and execution context!
Quoted 21 lines
As implemented in this set, a link between scheduling contexts of different tasks might be established when a task blocks on a mutex held by some other task (
blocked_onrelation). In this case the former task starts to be considered a potential proxy for the latter (mutex owner). One key change in how mutexes work made in here is that waiters don't really sleep: they are not dequeued, so they can be picked up by the scheduler when it runs. If a waiter (potential proxy) task is selected by the scheduler, theblocked_onrelation is used to find the mutex owner and put that to run on the CPU, using the proxy task scheduling context.Follow the blocked-on relation:
,-> task <- proxy, picked by scheduler
| | blocked-on
| v
blocked-task | mutex
| | owner
| v
`-- task <- gets to run using proxy info
Quoted 8 lines
Quoted 6 lines
Now, the situation is (of course) more tricky than depicted so far because we have to deal with all sort of possible states the mutex owner might be in while a potential proxy is selected by the scheduler, e.g. owner might be sleeping, running on a different CPU, blocked on another mutex itself... so, I'd kindly refer people to have a look at 05/08
proxy()implementation and comments.My head hurt already.. :)
Eh. I was wondering about putting even more details in the cover. But then I thought that it might have been enough info already for this first spin. Guess we'll have to create proper docs (after how to properly implement this has been agreed upon?).
Quoted 12 lines
Quoted 11 lines
Peter kindly shared his WIP patches with us (me, Luca, Tommaso, Claudio, Daniel, the Pisa gang) a while ago, but I could seriously have a decent look at them only recently (thanks a lot to the other guys for giving a first look at this way before me!). This set is thus composed of Peter's original patches (which I rebased on tip/sched/core as of today, commented and hopefully duly reported in changelogs what have I possibly broke) plus a bunch of additional changes that seemed required to make all this boot "successfully" on a virtual machine. So be advised! This is good only for fun ATM (I actually really hope this is good enough for discussion), pretty far from production I'm afraid. Share early, share often, right? :-)
Quoted 2 lines
I'll give it a spin and see if it boots, then I probably have a ton of extra questions :)
Thanks! (I honestly expect sparks.. but it'll give us clues what needs to be fixing)
Thanks a lot for looking at this.
Best,
- Juri