scheduler ordering bits -v2
Subsystems (3)
Peter Zijlstra
maintainercover scheduler ordering bits -v2
Hi,
These are updates of the pending scheduler ordering patches, taking (hopefully) all prior comments into consideration.
I've queued them for merging, but please have a careful last look at them.
Thanks!
Peter Zijlstra
maintainerPATCH 1/4 sched: Better document the try_to_wake_up() barriers
Explain how the control dependency and smp_rmb() end up providing ACQUIRE semantics and pair with smp_store_release() in finish_lock_switch().
--- kernel/sched/core.c | 8 +++++++- kernel/sched/sched.h | 3 +++ 2 files changed, 10 insertions(+), 1 deletion(-)
kernel/sched/core.c +7 -1
@@ -1947,7 +1947,13 @@ try_to_wake_up(struct task_struct *p, unwhile (p->on_cpu)cpu_relax ();/* -* Pairs with the smp_wmb() in finish_lock_switch(). +* Combined with the control dependency above, we have an effective +* smp_load_acquire() without the need for full barriers. +* +* Pairs with the smp_store_release() in finish_lock_switch(). +* +* This ensures that tasks getting woken will be fully ordered against +* their previous state and preserve Program Order. */ smp_rmb ();
kernel/sched/sched.h +3 -0
@@ -1073,6 +1073,9 @@ static inline void finish_lock_switch(st* We must ensure this doesn't happen until the switch is completely * finished. * +* In particular, the load of prev->state in finish_task_switch() must +* happen before this. +* * Pairs with the control dependency and rmb in try_to_wake_up(). */ smp_store_release (&prev->on_cpu,0 );
Peter Zijlstra
maintainerPATCH 2/4 sched: Fix a race in try_to_wake_up() vs schedule()
In reply to Peter ZijlstraOleg noticed that its possible to falsely observe p->on_cpu == 0 such that we'll prematurely continue with the wakeup and effectively run p on two CPUs at the same time.
Even though the overlap is very limited; the task is in the middle of being scheduled out; it could still result in corruption of the scheduler data structures.
CPU0 CPU1
set_current_state(...)
<preempt_schedule>
context_switch(X, Y)
prepare_lock_switch(Y)
Y->on_cpu = 1;
finish_lock_switch(X)
store_release(X->on_cpu, 0);
try_to_wake_up(X)
LOCK(p->pi_lock);
t = X->on_cpu; // 0
context_switch(Y, X)
prepare_lock_switch(X)
X->on_cpu = 1;
finish_lock_switch(Y)
store_release(Y->on_cpu, 0);
</preempt_schedule>
schedule();
deactivate_task(X);
X->on_rq = 0;
if (X->on_rq) // false
if (t) while (X->on_cpu)
cpu_relax();
context_switch(X, ..)
finish_lock_switch(X)
store_release(X->on_cpu, 0);Avoid the load of X->on_cpu being hoisted over the X->on_rq load.
--- kernel/sched/core.c | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+)
kernel/sched/core.c +19 -0
@@ -2084,6 +2084,25 @@ try_to_wake_up(struct task_struct *p, un#ifdef CONFIG_SMP /* +* Ensure we load p->on_cpu _after_ p->on_rq, otherwise it would be +* possible to, falsely, observe p->on_cpu == 0. +* +* One must be running (->on_cpu == 1) in order to remove oneself +* from the runqueue. +* +* [S] ->on_cpu = 1; [L] ->on_rq +* UNLOCK rq->lock +* RMB +* LOCK rq->lock +* [S] ->on_rq = 0; [L] ->on_cpu +* +* Pairs with the full barrier implied in the UNLOCK+LOCK on rq->lock +* from the consecutive calls to schedule(); the first switching to our +* task, the second putting it to sleep. +*/ +smp_rmb (); + +/* * If the owning (remote) cpu is still in the middle of schedule() with * this task as prev, wait until its done referencing the task. */
Peter Zijlstra
maintainerPATCH 3/4 locking: Introduce smp_cond_acquire()
In reply to Peter ZijlstraIntroduce smp_cond_acquire() which combines a control dependency and a read barrier to form acquire semantics.
This primitive has two benefits:
- it documents control dependencies,
- its typically cheaper than using smp_load_acquire() in a loop.
--- include/linux/compiler.h | 17 +++++++++++++++++ kernel/locking/qspinlock.c | 3 +-- kernel/sched/core.c | 8 +------- kernel/sched/sched.h | 2 +- 4 files changed, 20 insertions(+), 10 deletions(-)
include/linux/compiler.h +17 -0
@@ -299,6 +299,23 @@ static __always_inline void __write_once __u.__val; \ }) +/** +* smp_cond_acquire() - Spin wait for cond with ACQUIRE ordering +* @cond: boolean expression to wait for +* +* Equivalent to using smp_load_acquire() on the condition variable but employs +* the control dependency of the wait to reduce the barrier on many platforms. +* +* The control dependency provides a LOAD->STORE order, the additional RMB +* provides LOAD->LOAD order, together they provide LOAD->{LOAD,STORE} order, +* aka. ACQUIRE. +*/ +#define smp_cond_acquire(cond) do { \ + while (!(cond)) \ + cpu_relax(); \ + smp_rmb(); /* ctrl + rmb := acquire */ \ +} while (0) +#endif /* __KERNEL__ */ #endif /* __ASSEMBLY__ */
kernel/locking/qspinlock.c +1 -2
@@ -446,8 +446,7 @@ void queued_spin_lock_slowpath(struct qsif ((val =pv_wait_head_or_lock (lock, node))) goto locked; -while ((val =smp_load_acquire (&lock->val.counter)) & _Q_LOCKED_PENDING_MASK) -cpu_relax (); +smp_cond_acquire (!((val =atomic_read (&lock->val)) & _Q_LOCKED_PENDING_MASK)); locked:/*
kernel/sched/core.c +1 -7
@@ -1979,19 +1979,13 @@ try_to_wake_up(struct task_struct *p, un/* * If the owning (remote) cpu is still in the middle of schedule() with * this task as prev, wait until its done referencing the task. -*/ -while (p->on_cpu) -cpu_relax (); -/* -* Combined with the control dependency above, we have an effective -* smp_load_acquire() without the need for full barriers. * * Pairs with the smp_store_release() in finish_lock_switch(). * * This ensures that tasks getting woken will be fully ordered against * their previous state and preserve Program Order. */ -smp_rmb (); +smp_cond_acquire (!p->on_cpu); p->sched_contributes_to_load = !!task_contributes_to_load (p); p->state =TASK_WAKING ;
kernel/sched/sched.h +1 -1
@@ -1079,7 +1079,7 @@ static inline void finish_lock_switch(st* In particular, the load of prev->state in finish_task_switch() must * happen before this. * -* Pairs with the control dependency and rmb in try_to_wake_up(). +* Pairs with the smp_cond_acquire() in try_to_wake_up(). */ smp_store_release (&prev->on_cpu,0 );#endif
Re: [PATCH 3/4] locking: Introduce smp_cond_acquire()
Hi Peter,
Quoted 44 lines · Peter Zijlstra
Introduce
smp_cond_acquire()which combines a control dependency and a read barrier to form acquire semantics.This primitive has two benefits:
- it documents control dependencies,
- its typically cheaper than usingsmp_load_acquire()in a loop.Signed-off-by Peter Zijlstra (Intel) <[email protected]>--- include/linux/compiler.h | 17 +++++++++++++++++ kernel/locking/qspinlock.c | 3 +-- kernel/sched/core.c | 8 +------- kernel/sched/sched.h | 2 +- 4 files changed, 20 insertions(+), 10 deletions(-)include/linux/compiler.h +17
-0@@ -299,6 +299,23 @@ static __always_inline void __write_once __u.__val; \ }) +/** +* smp_cond_acquire() - Spin wait for cond with ACQUIRE ordering +* @cond: boolean expression to wait for +* +* Equivalent to using smp_load_acquire() on the condition variable but employs +* the control dependency of the wait to reduce the barrier on many platforms. +* +* The control dependency provides a LOAD->STORE order, the additional RMB +* provides LOAD->LOAD order, together they provide LOAD->{LOAD,STORE} order, +* aka. ACQUIRE. +*/ +#define smp_cond_acquire(cond) do { \ + while (!(cond)) \ + cpu_relax(); \ + smp_rmb(); /* ctrl + rmb := acquire */ \ +} while (0) +#endif /* __KERNEL__ */ #endif /* __ASSEMBLY__ */
kernel/locking/qspinlock.c void queued_spin_lock_slowpath(struct qs · line 449
Quoted 6 lines
kernel/locking/qspinlock.c +1
-2@@ -446,8 +446,7 @@ void queued_spin_lock_slowpath(struct qsif ((val =pv_wait_head_or_lock (lock, node))) goto locked; -while ((val =smp_load_acquire (&lock->val.counter)) & _Q_LOCKED_PENDING_MASK) -cpu_relax (); +smp_cond_acquire (!((val =atomic_read (&lock->val)) & _Q_LOCKED_PENDING_MASK));
I think we spoke about this before, but what would work really well for arm64 here is if we could override smp_cond_acquire in such a way that the atomic_read could be performed explicitly in the macro. That would allow us to use an LDXR to set the exclusive monitor, which in turn means we can issue a WFE and get a cheap wakeup when lock->val is actually modified.
With the current scheme, there's not enough information expressed in the "cond" parameter to perform this optimisation.
Cheers,
Will
Peter Zijlstra
maintainerRe: [PATCH 3/4] locking: Introduce smp_cond_acquire()
Quoted 15 lines · Will Deacon
include/linux/compiler.h static __always_inline void __write_once
Quoted 7 lines
include/linux/compiler.h +6
-0+#define smp_cond_acquire (cond) do { \ + while (!(cond)) \ + cpu_relax(); \ + smp_rmb();/* ctrl + rmb := acquire */ \ +}while (0 ) +smp_cond_acquire (!((val =atomic_read (&lock->val)) & _Q_LOCKED_PENDING_MASK));I think we spoke about this before, but what would work really well for arm64 here is if we could override
smp_cond_acquirein such a way that theatomic_readcould be performed explicitly in the macro. That would allow us to use an LDXR to set the exclusive monitor, which in turn means we can issue a WFE and get a cheap wakeup whenlock->valis actually modified.
Quoted 2 lines
With the current scheme, there's not enough information expressed in the "cond" parameter to perform this optimisation.
Right, but I'm having a hard time constructing something pretty that can do that. Lambda functions would be lovely, but we don't have those :/
While we can easily pass a pointer to an arbitrary type, we need an expression to evaluate the result of the pointer load to act as our condition.
smp_cond_acquire(&lock->val.counter,
[](int val){ return !(val & _Q_LOCKED_PENDING_MASK); });Would be nice, but alas.
The best we can do is hardcode a variable name; maybe something like:
#define smp_cond_acquire(ptr, expr) do { \
typeof(*ptr) val; \
while ((val = READ_ONCE(*ptr)), expr) \
cpu_relax(); \
smp_rmb(); /* ctrl + rmb := acquire */ \
} while (0)Which would let us write:
smp_cond_acquire(&lock->val.counter, !(val & _Q_LOCKED_PENDING_MASK));
Thoughts?
Peter Zijlstra
maintainerRe: [PATCH 3/4] locking: Introduce smp_cond_acquire()
Quoted 9 lines · Peter Zijlstra
The best we can do is hardcode a variable name; maybe something like:
#define smp_cond_acquire(ptr, expr) do { \ typeof(*ptr) val; \ while ((val = READ_ONCE(*ptr)), expr) \ cpu_relax(); \ smp_rmb(); /* ctrl + rmb := acquire */ \ } while (0)
Quoted 3 lines
Which would let us write:
smp_cond_acquire(&lock->val.counter, !(val & _Q_LOCKED_PENDING_MASK));
So I'm thinking that might still be hard to use for you if the LDXR+WFE has the regular LL/SC constraint of not allowing other loads in.
Re: [PATCH 3/4] locking: Introduce smp_cond_acquire()
In reply to Peter ZijlstraQuoted 40 lines · Peter Zijlstra
Quoted 15 lines · Will Deacon
include/linux/compiler.h static __always_inline void __write_once
Quoted 7 lines
include/linux/compiler.h +6
-0+#define smp_cond_acquire (cond) do { \ + while (!(cond)) \ + cpu_relax(); \ + smp_rmb();/* ctrl + rmb := acquire */ \ +}while (0 ) +smp_cond_acquire (!((val =atomic_read (&lock->val)) & _Q_LOCKED_PENDING_MASK));I think we spoke about this before, but what would work really well for arm64 here is if we could override
smp_cond_acquirein such a way that theatomic_readcould be performed explicitly in the macro. That would allow us to use an LDXR to set the exclusive monitor, which in turn means we can issue a WFE and get a cheap wakeup whenlock->valis actually modified.Quoted 2 lines
With the current scheme, there's not enough information expressed in the "cond" parameter to perform this optimisation.
Right, but I'm having a hard time constructing something pretty that can do that. Lambda functions would be lovely, but we don't have those :/
While we can easily pass a pointer to an arbitrary type, we need an expression to evaluate the result of the pointer load to act as our condition.
smp_cond_acquire(&lock->val.counter,
[](int val){ return !(val & _Q_LOCKED_PENDING_MASK); });Would be nice, but alas.
The best we can do is hardcode a variable name; maybe something like:
#define smp_cond_acquire(ptr, expr) do { \ typeof(*ptr) val; \ while ((val = READ_ONCE(*ptr)), expr) \ cpu_relax(); \ smp_rmb(); /* ctrl + rmb := acquire */ \ } while (0)
Quoted 6 lines
Which would let us write:
smp_cond_acquire(&lock->val.counter, !(val & _Q_LOCKED_PENDING_MASK));Thoughts?
That would certainly work for me, but I appreciate it's not pretty. We could have an extra macro parameter for the name of the temporary variable, if you wanted to make it explicit.
Will
Re: [PATCH 3/4] locking: Introduce smp_cond_acquire()
In reply to Peter ZijlstraQuoted 37 lines · Peter Zijlstra
Quoted 13 lines · Will Deacon
include/linux/compiler.h static __always_inline void __write_once
Quoted 6 lines
include/linux/compiler.h +6
-0+#define smp_cond_acquire (cond) do { \ + while (!(cond)) \ + cpu_relax(); \ + smp_rmb();/* ctrl + rmb := acquire */ \ +}while (0 ) +smp_cond_acquire (!((val =atomic_read (&lock->val))& _Q_LOCKED_PENDING_MASK));I think we spoke about this before, but what would work really well for arm64 here is if we could override
smp_cond_acquirein such a way that theatomic_readcould be performed explicitly in the macro. That would allow us to use an LDXR to set the exclusive monitor, which in turn means we can issue a WFE and get a cheap wakeup whenlock->valis actually modified.Quoted 2 lines
With the current scheme, there's not enough information expressed in the "cond" parameter to perform this optimisation.
Right, but I'm having a hard time constructing something pretty that can do that. Lambda functions would be lovely, but we don't have those :/
While we can easily pass a pointer to an arbitrary type, we need an expression to evaluate the result of the pointer load to act as our condition.
smp_cond_acquire(&lock->val.counter, [](int val){ return !(val& _Q_LOCKED_PENDING_MASK); });Would be nice, but alas.
The best we can do is hardcode a variable name; maybe something like:
#define smp_cond_acquire(ptr, expr) do { \ typeof(*ptr) val; \ while ((val = READ_ONCE(*ptr)), expr) \ cpu_relax(); \ smp_rmb(); /* ctrl + rmb := acquire */ \ } while (0)
Quoted 6 lines
Which would let us write:
smp_cond_acquire(&lock->val.counter, !(val& _Q_LOCKED_PENDING_MASK));Thoughts?
Will the following work?
#define smp_cond_load_acquire(ptr, cond_expr, neg) ({ \
typeof(*ptr) _val; \
while (neg ((_val = READ_ONCE(*ptr)) cond_expr))\
cpu_relax(); \
smp_rmb(); \
_val; \
})val = smp_cond_load_acquire(&lock->val.counter, &
_Q_LOCKED_PENDING_MASK, !);
Cheers,
Longman
Re: [PATCH 3/4] locking: Introduce smp_cond_acquire()
Quoted 2 lines · Waiman Long
Will the following work?
Are we trying to win some obfuscated C contest here?
Just make it do something like (skipping backslashes to make it easier to type and read)
#define smp_cond_load_acquire(ptr, cond_expr) ({
typeof(*ptr) VAL;
for (;;) {
VAL = READ_ONCE(*ptr);
if (cond_expr) break;
cpu_relax();
}
smp_rmb();
VAL;})
and then you'd have it be
val = smp_cond_load_acquire(&lock->val.counter,
!(VAL & _Q_LOCKED_PENDING_MASK));which is at least halfway legible. Not some odd "fragments of expressions" interfaces unless absolutely required, please.
Of course, I suspect we should not use READ_ONCE(), but some architecture-overridable version that just defaults to READ_ONCE(). Same goes for that "smp_rmb()". Because maybe some architectures will just prefer an explicit acquire, and I suspect we do *not* want architectures having to recreate and override that crazy loop.
How much does this all actually end up mattering, btw?
Linus
Re: [PATCH 3/4] locking: Introduce smp_cond_acquire()
Quoted 18 lines · Linus Torvalds
Quoted 1 line · Waiman Long
Will the following work?
Are we trying to win some obfuscated C contest here?
Just make it do something like (skipping backslashes to make it easier to type and read)
#define smp_cond_load_acquire(ptr, cond_expr) ({ typeof(*ptr) VAL; for (;;) { VAL = READ_ONCE(*ptr); if (cond_expr) break; cpu_relax(); } smp_rmb(); VAL; })
Quoted 7 lines
and then you'd have it be
val = smp_cond_load_acquire(&lock->val.counter, !(VAL& _Q_LOCKED_PENDING_MASK));which is at least halfway legible. Not some odd "fragments of expressions" interfaces unless absolutely required, please.
It is just some random thought that I have. I am not saying that it is the right way to go.
Quoted 9 lines
Of course, I suspect we should not use
READ_ONCE(), but some architecture-overridable version that just defaults toREAD_ONCE(). Same goes for that "smp_rmb()". Because maybe some architectures will just prefer an explicit acquire, and I suspect we do *not* want architectures having to recreate and override that crazy loop.How much does this all actually end up mattering, btw?
Linus
I think what Will want to do is to provide an architecture specific replacement for the whole macro, not just part of it. So using READ_ONCE should be fine.
Cheers,
Longman
Peter Zijlstra
maintainerRe: [PATCH 3/4] locking: Introduce smp_cond_acquire()
In reply to Linus TorvaldsQuoted 7 lines · Linus Torvalds
Of course, I suspect we should not use
READ_ONCE(), but some architecture-overridable version that just defaults toREAD_ONCE(). Same goes for that "smp_rmb()". Because maybe some architectures will just prefer an explicit acquire, and I suspect we do *not* want architectures having to recreate and override that crazy loop.How much does this all actually end up mattering, btw?
Not sure, I'll have to let Will quantify that. But the whole reason we're having this discussion is that ARM64 has a MONITOR+MWAIT like construct that they'd like to use to avoid the spinning.
Of course, in order to use that, they _have_ to override the crazy loop.
Now, Will and I spoke earlier today, and the version proposed by me (and you, since that is roughly similar) will indeed work for them in that it would allow them to rewrite the thing something like:
typeof(*ptr) VAL;
for (;;) {
VAL = READ_ONCE(*ptr);
if (expr)
break;
cmp_and_wait(ptr, VAL);
}Where their cmd_and_wait(ptr, val) looks a little like:
asm volatile( " ldxr %w0, %1 \n" " sub %w0, %w0, %2 \n" " cbnz 1f \n" " wfe \n" "1:" : "=&r" (tmp) : "Q" (*ptr), "r" (val) );
(excuse my poor ARM asm foo)
Which sets up a load-exclusive monitor, compares if the value loaded matches what we previously saw, and if so, wait-for-event.
WFE will wake on any event that would've also invalidated a subsequent stxr or store-exclusive.
ARM64 also of course can choose to use load-acquire instead of the READ_ONCE(), or still issue the smp_rmb(), dunno what is best for them. The load-acquire would (potentially) be issued multiple times, vs the rmb only once. I'll let Will sort that.
In any case, WFE is both better for power consumption and lowers the cacheline pressure, ie. nobody keeps trying to pull the line into shared state all the time while you're trying to get a store done.
Re: [PATCH 3/4] locking: Introduce smp_cond_acquire()
Quoted 7 lines · Peter Zijlstra
Quoted 6 lines · Linus Torvalds
Of course, I suspect we should not use
READ_ONCE(), but some architecture-overridable version that just defaults toREAD_ONCE(). Same goes for that "smp_rmb()". Because maybe some architectures will just prefer an explicit acquire, and I suspect we do *not* want architectures having to recreate and override that crazy loop.
Quoted 7 lines
Quoted 1 line
How much does this all actually end up mattering, btw?
Not sure, I'll have to let Will quantify that. But the whole reason we're having this discussion is that ARM64 has a MONITOR+MWAIT like construct that they'd like to use to avoid the spinning.
Of course, in order to use that, they _have_ to override the crazy loop.
Right. This also removes one of the few hurdles standing between us (arm64) and generic locking routines such as qspinlock, where we really don't want busy-wait loops (since cpu_relax doesn't give us the opportuinity to use wfe safely).
Quoted 32 lines
Now, Will and I spoke earlier today, and the version proposed by me (and you, since that is roughly similar) will indeed work for them in that it would allow them to rewrite the thing something like:
typeof(*ptr) VAL; for (;;) { VAL = READ_ONCE(*ptr); if (expr) break; cmp_and_wait(ptr, VAL); }Where their
cmd_and_wait(ptr, val)looks a little like:asm volatile( " ldxr %w0, %1 \n" " sub %w0, %w0, %2 \n" " cbnz 1f \n" " wfe \n" "1:" : "=&r" (tmp) : "Q" (*ptr), "r" (val) );(excuse my poor ARM asm foo)
Which sets up a load-exclusive monitor, compares if the value loaded matches what we previously saw, and if so, wait-for-event.
Quoted 7 lines
WFE will wake on any event that would've also invalidated a subsequent stxr or store-exclusive.
ARM64 also of course can choose to use load-acquire instead of the
READ_ONCE(), or still issue thesmp_rmb(), dunno what is best for them. The load-acquire would (potentially) be issued multiple times, vs the rmb only once. I'll let Will sort that.
Yup. I'll just override the whole thing using something much like what you're suggesting.
Cheers,
Will
Re: [PATCH 3/4] locking: Introduce smp_cond_acquire()
In reply to Peter ZijlstraQuoted 6 lines · Peter Zijlstra
include/linux/compiler.h +6
-0+/** +* smp_cond_acquire() - Spin wait for cond with ACQUIRE ordering +* @cond: boolean expression to wait for +* +* Equivalent to using smp_load_acquire() on the condition variable but employs +* the control dependency of the wait to reduce the barrier on many platforms.
include/linux/compiler.h static __always_inline void __write_once · line 317
Quoted 10 lines
include/linux/compiler.h +10
-0+* +* The control dependency provides a LOAD->STORE order, the additional RMB +* provides LOAD->LOAD order, together they provide LOAD->{LOAD,STORE} order, +* aka. ACQUIRE. +*/ +#define smp_cond_acquire (cond) do { \ + while (!(cond)) \ + cpu_relax(); \ + smp_rmb();/* ctrl + rmb := acquire */ \ +}while (0 )
So this hides the fact that we actually are waiting on the cond, as opposed to conditional acquiring. Could it be renamed to something like smp_waitcond_acquire()?
Thanks,
Davidlohr
Peter Zijlstra
maintainerRe: [PATCH 3/4] locking: Introduce smp_cond_acquire()
Quoted 8 lines · Davidlohr Bueso
include/linux/compiler.h static __always_inline void __write_once · line 317
Quoted 5 lines
include/linux/compiler.h +5
-0+#define smp_cond_acquire (cond) do { \ + while (!(cond)) \ + cpu_relax(); \ + smp_rmb();/* ctrl + rmb := acquire */ \ +}while (0 )So this hides the fact that we actually are waiting on the cond, as opposed to conditional acquiring. Could it be renamed to something like
smp_waitcond_acquire()?
Right, I'm conflicted about that. On the one hand you're right, on the other hand we spin-wait so the next person will want it called smp_spin_wait_cond_acquire(), also it gets terribly long either way :/
bike-shed away I imagine.
Peter Zijlstra
maintainerPATCH 4/4 sched: Document Program-Order guarantees
In reply to Peter ZijlstraThese are some notes on the scheduler locking and how it provides program order guarantees on SMP systems.
--- kernel/sched/core.c | 91 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 91 insertions(+)
kernel/sched/core.c +91 -0
@@ -1916,6 +1916,97 @@ static void ttwu_queue(struct task_strucraw_spin_unlock (&rq->lock); } +/* +* Notes on Program-Order guarantees on SMP systems. +* +* MIGRATION +* +* The basic program-order guarantee on SMP systems is that when a task [t] +* migrates, all its activity on its old cpu [c0] happens-before any subsequent +* execution on its new cpu [c1]. +* +* For migration (of runnable tasks) this is provided by the following means: +* +* A) UNLOCK of the rq(c0)->lock scheduling out task t +* B) migration for t is required to synchronize *both* rq(c0)->lock and +* rq(c1)->lock (if not at the same time, then in that order). +* C) LOCK of the rq(c1)->lock scheduling in task +* +* Transitivity guarantees that B happens after A and C after B. +* Note: we only require RCpc transitivity. +* Note: the cpu doing B need not be c0 or c1 +* +* Example: +* +* CPU0 CPU1 CPU2 +* +* LOCK rq(0)->lock +* sched-out X +* sched-in Y +* UNLOCK rq(0)->lock +* +* LOCK rq(0)->lock // orders against CPU0 +* dequeue X +* UNLOCK rq(0)->lock +* +* LOCK rq(1)->lock +* enqueue X +* UNLOCK rq(1)->lock +* +* LOCK rq(1)->lock // orders against CPU2 +* sched-out Z +* sched-in X +* UNLOCK rq(1)->lock +* +* +* BLOCKING -- aka. SLEEP + WAKEUP +* +* For blocking we (obviously) need to provide the same guarantee as for +* migration. However the means are completely different as there is no lock +* chain to provide order. Instead we do: +* +* 1) smp_store_release(X->on_cpu, 0) +* 2) smp_cond_acquire(!X->on_cpu) +* +* Example: +* +* CPU0 (schedule) CPU1 (try_to_wake_up) CPU2 (schedule) +* +* LOCK rq(0)->lock LOCK X->pi_lock +* dequeue X +* sched-out X +* smp_store_release(X->on_cpu, 0); +* +* smp_cond_acquire(!X->on_cpu); +* X->state = WAKING +* set_task_cpu(X,2) +* +* LOCK rq(2)->lock +* enqueue X +* X->state = RUNNING +* UNLOCK rq(2)->lock +* +* LOCK rq(2)->lock // orders against CPU1 +* sched-out Z +* sched-in X +* UNLOCK rq(1)->lock +* +* UNLOCK X->pi_lock +* UNLOCK rq(0)->lock +* +* +* However; for wakeups there is a second guarantee we must provide, namely we +* must observe the state that lead to our wakeup. That is, not only must our +* task observe its own prior state, it must also observe the stores prior to +* its wakeup. +* +* This means that any means of doing remote wakeups must order the CPU doing +* the wakeup against the CPU the task is going to end up running on. This, +* however, is already required for the regular Program-Order guarantee above, +* since the waking CPU is the one issueing the ACQUIRE (smp_cond_acquire). +* +*/ +/** * try_to_wake_up - wake up a thread * @p: the thread to be awakened
Re: [PATCH 4/4] sched: Document Program-Order guarantees
On Thu, Dec 03, 2015 at 01:40:14PM +0100, Peter Zijlstra wrote:
[snip]
Quoted 13 lines
+ *
+ * CPU0 (schedule) CPU1 (try_to_wake_up) CPU2 (schedule)
+ *+ * LOCK rq(0)->lock LOCK X->pi_lock + * dequeue X + * sched-out X + * smp_store_release(X->on_cpu, 0); + * + * smp_cond_acquire(!X->on_cpu); + * X->state = WAKING + * set_task_cpu(X,2) + * + * LOCK rq(2)->lock
Quoted 8 lines
+ * enqueue X + * X->state = RUNNING + * UNLOCK rq(2)->lock + * + * LOCK rq(2)->lock // orders against CPU1 + * sched-out Z + * sched-in X + * UNLOCK rq(1)->lock
^^^^^^^^^^^^^^^
This is a typo, right? Should be "UNLOCK rq(2)->lock".
Regards,
Boqun
Quoted 5 lines
+ *
+ * UNLOCKX->pi_lock
+ * UNLOCK rq(0)->lock
+ *
+ *
Peter Zijlstra
maintainerRe: [PATCH 4/4] sched: Document Program-Order guarantees
Quoted 23 lines · Boqun Feng
On Thu, Dec 03, 2015 at 01:40:14PM +0100, Peter Zijlstra wrote:
[snip]Quoted 13 lines
+ *
+ * CPU0 (schedule) CPU1 (try_to_wake_up) CPU2 (schedule)
+ *+ * LOCK rq(0)->lock LOCK X->pi_lock + * dequeue X + * sched-out X + * smp_store_release(X->on_cpu, 0); + * + * smp_cond_acquire(!X->on_cpu); + * X->state = WAKING + * set_task_cpu(X,2) + * + * LOCK rq(2)->lockQuoted 8 lines
+ * enqueue X + * X->state = RUNNING + * UNLOCK rq(2)->lock + * + * LOCK rq(2)->lock // orders against CPU1 + * sched-out Z + * sched-in X + * UNLOCK rq(1)->lock
Quoted 3 lines
^^^^^^^^^^^^^^^This is a typo, right? Should be "UNLOCK rq(2)->lock".
Duh, yes. Fixed.
Thanks.