sched: Better document ttwu()
Peter Zijlstra
maintainerRFC PATCH 1/1 sched: Better document ttwu()
Dave hit the problem fixed by commit:
b6e13e85829f ("sched/core: Fix ttwu() race")
and failed to understand much of the code involved. Per his request a few comments to (hopefully) clarify things.
--- include/linux/sched.h | 12 ++-- kernel/sched/core.c | 195 +++++++++++++++++++++++++++++++++++++++++++------- kernel/sched/sched.h | 11 +++ 3 files changed, 187 insertions(+), 31 deletions(-)
include/linux/sched.h +6 -6
@@ -158,24 +158,24 @@ struct task_group;* * for (;;) { * set_current_state(TASK_UNINTERRUPTIBLE); -* if (!need_sleep) -* break; +* if (CONDITION) +* break; * * schedule(); * } * __set_current_state(TASK_RUNNING); * * If the caller does not need such serialisation (because, for instance, the -* condition test and condition change and wakeup are under the same lock) then +* CONDITION test and condition change and wakeup are under the same lock) then * use __set_current_state(). * * The above is typically ordered against the wakeup, which does: * -* need_sleep = false; +* CONDITION = 1; * wake_up_state(p, TASK_UNINTERRUPTIBLE); * -* where wake_up_state() executes a full memory barrier before accessing the -* task state. +* where wake_up_state()/try_to_wake_up() executes a full memory barrier before +* accessing p->state. * * Wakeup will do: if (@state & p->state) p->state = TASK_RUNNING, that is, * once it observes the TASK_UNINTERRUPTIBLE store the waking CPU can issue a
kernel/sched/core.c +170 -25
281 lines not on this page · raw message
kernel/sched/sched.h +11 -0
@@ -1197,6 +1197,17 @@ struct rq_flags {#endif }; +/* +* Lockdep annotation that avoid accidental unlock; any +* raw_spin_unlock(&rq->lock) without preceding rq_unpin_lock() with the +* correct cookie will result in a WARN. +* +* This avoids code that has access to 'struct rq *rq' (basically everything in +* the scheduler) from accidentally unlocking the rq if they do not also have a +* copy of the (on-stack) 'struct rq_flags rf'. +* +* Also see Documentation/locking/lockdep-design.rst. +*/ static inline void rq_pin_lock (struct rq *rq,struct rq_flags *rf) { rf->cookie =lockdep_pin_lock (&rq->lock);
Hi Peter,
Quoted 110 lines · On Thu, Jul 02, 2020 at 02:52:11PM +0200 Peter Zijlstra wrote:
Dave hit the problem fixed by commit:
b6e13e85829f("sched/core: Fixttwu()race")and failed to understand much of the code involved. Per his request a few comments to (hopefully) clarify things.
Requested-by Dave Chinner <[email protected]>Signed-off-by Peter Zijlstra (Intel) <[email protected]>--- include/linux/sched.h | 12 ++-- kernel/sched/core.c | 195 +++++++++++++++++++++++++++++++++++++++++++------- kernel/sched/sched.h | 11 +++ 3 files changed, 187 insertions(+), 31 deletions(-)include/linux/sched.h +6
-6@@ -158,24 +158,24 @@ struct task_group;* * for (;;) { * set_current_state(TASK_UNINTERRUPTIBLE); -* if (!need_sleep) -* break; +* if (CONDITION) +* break; * * schedule(); * } * __set_current_state(TASK_RUNNING); * * If the caller does not need such serialisation (because, for instance, the -* condition test and condition change and wakeup are under the same lock) then +* CONDITION test and condition change and wakeup are under the same lock) then * use __set_current_state(). * * The above is typically ordered against the wakeup, which does: * -* need_sleep = false; +* CONDITION = 1; * wake_up_state(p, TASK_UNINTERRUPTIBLE); * -* where wake_up_state() executes a full memory barrier before accessing the -* task state. +* where wake_up_state()/try_to_wake_up() executes a full memory barrier before +* accessing p->state. * * Wakeup will do: if (@state & p->state) p->state = TASK_RUNNING, that is, * once it observes the TASK_UNINTERRUPTIBLE store the waking CPU can issue a kernel/sched/core.c +51
-0@@ -77,6 +77,97 @@ __read_mostly int scheduler_running;*/ int sysctl_sched_rt_runtime =950000 ; + +/* +* Serialization rules: +* +* Lock order: +* +* p->pi_lock +* rq->lock +* hrtimer_cpu_base->lock (hrtimer_start() for bandwidth controls) +* +* rq1->lock +* rq2->lock where: rq1 < rq2 +* +* Regular state: +* +* Normal scheduling state is serialized by rq->lock. __schedule() takes the +* local CPU's rq->lock, it optionally removes the task from the runqueue and +* always looks at the local rq data structures to find the most elegible task +* to run next. +* +* Task enqueue is also under rq->lock, possibly taken from another CPU. +* Wakeups from another LLC domain might use an IPI to transfer the enqueue to +* the local CPU to avoid bouncing the runqueue state around [ see +* ttwu_queue_wakelist() ] +* +* Task wakeup, specifically wakeups that involve migration, are horribly +* complicated to avoid having to take two rq->locks. +* +* Special state: +* +* System-calls and anything external will use task_rq_lock() which acquires +* both p->lock and rq->lock. As a consequence the state they change is stable +* while holding either lock: +* +* - sched_setaffinity(): p->cpus_ptr +* - set_user_nice(): p->se.load, p->static_prio +* - __sched_setscheduler(): p->sched_class, p->policy, p->*prio, p->se.load, +* p->dl.dl_{runtime, deadline, period, flags, bw, density} +* - sched_setnuma(): p->numa_preferred_nid +* - sched_move_task()/ +* cpu_cgroup_fork(): p->sched_task_group +* +* p->state <- TASK_*: +* +* is changed locklessly using set_current_state(), __set_current_state() or +* set_special_state(), see their respective comments, or by +* try_to_wake_up(). This latter uses p->pi_lock to serialize against +* concurrent self. +* +* p->on_rq <- { 0, 1 = TASK_ON_RQ_QUEUED, 2 = TASK_ON_RQ_MIGRATING }: +*
kernel/sched/core.c __read_mostly int scheduler_running; · line 140
Quoted 10 lines
kernel/sched/core.c +10
-0+* is set by activate_task() and cleared by deactivate_task(), under +* rq->lock. Non-zero indicates the task is runnable, the special +* ON_RQ_MIGRATING state is used for migration without holding both +* rq->locks. It indicates task_cpu() is not stable, see task_rq_lock(). +* +* p->on_cpu <- { 0, 1 }: +* +* is set by prepare_task() and cleared by finish_task() such that it will be +* set before p is scheduled-in and cleared after p is scheduled-out, both +* under rq->lock. Non-zero indicates the task is running on it's CPU.
s/it's/its/
Quoted 134 lines
kernel/sched/core.c +68
-14+* +* [ The astute reader will observe that it is possible for two tasks on one +* CPU to have ->on_cpu = 1 at the same time. ] +* +* task_cpu(p): is changed by set_task_cpu(), the rules are: +* +* - Don't call set_task_cpu() on a blocked task: +* +* We don't care what CPU we're not running on, this simplifies hotplug, +* the CPU assignment of blocked tasks isn't required to be valid. +* +* - for try_to_wake_up(), called under p->pi_lock: +* +* This allows try_to_wake_up() to only take one rq->lock, see its comment. +* +* - for migration called under rq->lock: +* [ see task_on_rq_migrating() in task_rq_lock() ] +* +* o move_queued_task() +* o __migrate_swap_task() +* o detach_task() +* +* - for migration called under double_rq_lock(): +* +* o push_rt_task() / pull_rt_task() +* o push_dl_task() / pull_dl_task() +* o dl_task_offline_migration() +* +*/ +/* * __task_rq_lock - lock the rq @p resides on. */ @@ -1466,8 +1557,7 @@ static struct rq *move_queued_task(struct rq *rq, struct rq_flags *rf, {lockdep_assert_held (&rq->lock); -WRITE_ONCE (p->on_rq,TASK_ON_RQ_MIGRATING ); -dequeue_task (rq, p,DEQUEUE_NOCLOCK ); +deactivate_task (rq, p,DEQUEUE_NOCLOCK );set_task_cpu (p, new_cpu);rq_unlock (rq, rf);@@ -1475,8 +1565,7 @@ static struct rq *move_queued_task(struct rq *rq, struct rq_flags *rf,rq_lock (rq, rf);BUG_ON (task_cpu (p) != new_cpu); -enqueue_task (rq, p,0 ); - p->on_rq =TASK_ON_RQ_QUEUED ; +activate_task (rq, p,0 );check_preempt_curr (rq, p,0 );return rq;@@ -2241,12 +2330,31 @@ ttwu_do_activate(struct rq *rq, struct task_struct *p, int wake_flags, }/* -* Called in case the task @p isn't fully descheduled from its runqueue, -* in this case we must do a remote wakeup. Its a 'light' wakeup though, -* since all we need to do is flip p->state to TASK_RUNNING, since -* the task is still ->on_rq. +* Consider @p being inside a wait loop: +* +* for (;;) { +* set_current_state(TASK_UNINTERRUPTIBLE); +* +* if (CONDITION) +* break; +* +* schedule(); +* } +* __set_current_state(TASK_RUNNING); +* +* between set_current_state() and schedule(). In this case @p is still +* runnable, so all that needs doing is change p->state back to TASK_RUNNING in +* an atomic manner. +* +* By taking task_rq(p)->lock we serialize against schedule(), if @p->on_rq +* then schedule() must still happen and p->state can be changed to +* TASK_RUNNING. Otherwise we lost the race, schedule() has happened, and we +* need to do a full wakeup with enqueue. +* +* Returns: %true when the wakeup is done, +* %false otherwise. */ -static int ttwu_remote (struct task_struct *p,int wake_flags) +static int ttwu_runnable (struct task_struct *p,int wake_flags) {struct rq_flags rf;struct rq *rq;@@ -2387,6 +2495,14 @@ static bool ttwu_queue_wakelist(struct task_struct *p, int cpu, int wake_flags) return false; } + +#else /* !CONFIG_SMP */ + +static inline bool ttwu_queue_wakelist (struct task_struct *p,int cpu,int wake_flags) +{ +return false; +} +#endif /* CONFIG_SMP */ static void ttwu_queue (struct task_struct *p,int cpu,int wake_flags)@@ -2394,10 +2510,8 @@ static void ttwu_queue(struct task_struct *p, int cpu, int wake_flags)struct rq *rq =cpu_rq (cpu);struct rq_flags rf; -#if defined(CONFIG_SMP )if (ttwu_queue_wakelist (p, cpu, wake_flags))return ; -#endif rq_lock (rq, &rf);update_rq_clock (rq);@@ -2453,8 +2567,8 @@ static void ttwu_queue(struct task_struct *p, int cpu, int wake_flags)* 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_load_acquire(!X->on_cpu) +* 1) smp_store_release(X->on_cpu, 0) -- finish_task() +* 2) smp_cond_load_acquire(!X->on_cpu) -- try_to_wake_up() * * Example: * @@ -2494,15 +2608,41 @@ static void ttwu_queue(struct task_struct *p, int cpu, int wake_flags)* @state: the mask of task states that can be woken * @wake_flags: wake modifier flags (WF_*) * -* If (@state & @p->state) @p->state = TASK_RUNNING. +* Conceptually does: +*
kernel/sched/core.c static void ttwu_queue(struct task_struct *p, int cpu, int wake_flags) · line 2620
Quoted 10 lines
kernel/sched/core.c +5
-2+* If (@state & @p->state) @p->state = TASK_RUNNING. * * If the task was not queued/runnable, also place it back on a runqueue. * -* Atomic against schedule() which would dequeue a task, also see -* set_current_state(). +* This function: +* - is atomic against schedule() which would dequeue the task; +* - issues a full memory barrier before accessing @p->state. +* See the comment with set_current_state().
I think these two above should not be " - " indented to match the other partial sentences below (or all the ones below should be bullets, but I think that is messier). But this is just a style quibble :)
Quoted 60 lines
kernel/sched/core.c +28
-6+* +* Uses p->pi_lock to serialize against concurrent wake-ups. +* +* Relies on p->pi_lock stabilizing: +* - p->sched_class +* - p->cpus_ptr +* - p->sched_task_group +* in order to do migration, see its use of select_task_rq()/set_task_cpu(). * -* This function executes a full memory barrier before accessing the task -* state; see set_current_state(). +* Tries really hard to only take one task_rq(p)->lock for performance. +* Takes rq->lock in: +* - ttwu_runnable() -- old rq, unavoidable, see comment there; +* - ttwu_queue() -- new rq, for enqueue of the task; +* - psi_ttwu_dequeue() -- much sadness :-( accounting will kill us. +* +* As a concequence we race really badly with just about everything. See the +* many memory barriers and their comments for details. The basic order of +* reading things is: +* +* LOAD p->state +* RMB +* LOAD p->on_rq +* RMB +* LOAD-ACQUIRE p->on_cpu +* LOAD task_cpu() * * Return: %true if @p->state changes (an actual wakeup was done), * %false otherwise. @@ -2518,7 +2658,7 @@ try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)/* * We're waking current, this means 'p->on_rq' and 'task_cpu(p) * == smp_processor_id()'. Together this means we can special -* case the whole 'p->on_rq && ttwu_remote()' case below +* case the whole 'p->on_rq && ttwu_runnable()' case below * without taking any locks. * * In particular: @@ -2539,8 +2679,8 @@ try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)/* * If we are going to wake up a thread waiting for CONDITION we * need to ensure that CONDITION=1 done by the caller can not be -* reordered with p->state check below. This pairs with mb() in -* set_current_state() the waiting thread does. +* reordered with p->state check below. This pairs with smp_store_mb() +* in set_current_state() that the waiting thread does. */ raw_spin_lock_irqsave (&p->pi_lock, flags);smp_mb__after_spinlock ();@@ -2575,7 +2715,7 @@ try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)* A similar smb_rmb() lives in try_invoke_on_locked_down_task(). */ smp_rmb (); -if (p->on_rq &&ttwu_remote (p, wake_flags)) +if (p->on_rq &&ttwu_runnable (p, wake_flags)) goto unlock;if (p->in_iowait) {
kernel/sched/core.c static inline void prepare_task(struct task_struct *next) · line 3282
Quoted 10 lines
kernel/sched/core.c +5
-1@@ -3134,8 +3274,12 @@ static inline void prepare_task(struct task_struct *next)/* * Claim the task as running, we do this before switching to it * such that any running task will have this set. +* +* __schedule()'s rq->lock and smp_mb__after_spin_lock() orders this +* store against prior state change of @next, also see +* try_to_wake_up(), specifically smp_load_acquire(&p->on_cpu). */ - next->on_cpu =1 ; +WRITE_ONCE (next->on_cpu,1 );
This is more than a documentation change.
Beyond that this looks good. I've got to read it again in context to digest it fully. Thank you for doing this. Very helpful.
Cheers,
Phil
Quoted 38 lines
kernel/sched/core.c +3
-2#endif }@@ -3143,8 +3287,9 @@ static inline void finish_task(struct task_struct *prev) {#ifdef CONFIG_SMP /* -* After ->on_cpu is cleared, the task can be moved to a different CPU. -* We must ensure this doesn't happen until the switch is completely +* This must be the very last reference to @prev from this CPU. After +* p->on_cpu is cleared, the task can be moved to a different CPU. 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 kernel/sched/sched.h +11
-0@@ -1197,6 +1197,17 @@ struct rq_flags {#endif }; +/* +* Lockdep annotation that avoid accidental unlock; any +* raw_spin_unlock(&rq->lock) without preceding rq_unpin_lock() with the +* correct cookie will result in a WARN. +* +* This avoids code that has access to 'struct rq *rq' (basically everything in +* the scheduler) from accidentally unlocking the rq if they do not also have a +* copy of the (on-stack) 'struct rq_flags rf'. +* +* Also see Documentation/locking/lockdep-design.rst. +*/ static inline void rq_pin_lock (struct rq *rq,struct rq_flags *rf) { rf->cookie =lockdep_pin_lock (&rq->lock);
Peter Zijlstra
maintainerQuoted 9 lines · Phil Auld
Quoted 5 lines · On Thu, Jul 02, 2020 at 02:52:11PM +0200 Peter Zijlstra wrote:
+ *
p->on_cpu<- { 0, 1 }:
+ *+ * is set by prepare_task() and cleared by finish_task() such that it will be + * set before p is scheduled-in and cleared after p is scheduled-out, both + * under rq->lock. Non-zero indicates the task is running on it's CPU.s/it's/its/
Fixed.
Quoted 13 lines
Quoted 13 lines
kernel/sched/core.c +3
-3@@ -2494,15 +2608,41 @@ static void ttwu_queue(struct task_struct *p, int cpu, int wake_flags)* @state: the mask of task states that can be woken * @wake_flags: wake modifier flags (WF_*) * -* If (@state & @p->state) @p->state = TASK_RUNNING. +* Conceptually does: +* +* If (@state & @p->state) @p->state = TASK_RUNNING. * * If the task was not queued/runnable, also place it back on a runqueue. * -* Atomic against schedule() which would dequeue a task, also see -* set_current_state().
Quoted 8 lines
kernel/sched/core.c static void ttwu_queue(struct task_struct *p, int cpu, int wake_flags) · line 2620
Quoted 4 lines
kernel/sched/core.c +4
-0+* This function: +* - is atomic against schedule() which would dequeue the task; +* - issues a full memory barrier before accessing @p->state. +* See the comment with set_current_state(). I think these two above should not be " - " indented to match the other partial sentences below (or all the ones below should be bullets, but I think that is messier). But this is just a style quibble :)
Fair enough; I'll go rework that.
Quoted 5 lines
Quoted 5 lines
kernel/sched/core.c +1
-0@@ -3134,8 +3274,12 @@ static inline void prepare_task(struct task_struct *next)/* * Claim the task as running, we do this before switching to it * such that any running task will have this set. +*
Quoted 8 lines
kernel/sched/core.c static inline void prepare_task(struct task_struct *next) · line 3282
Quoted 6 lines
kernel/sched/core.c +4
-1+* __schedule()'s rq->lock and smp_mb__after_spin_lock() orders this +* store against prior state change of @next, also see +* try_to_wake_up(), specifically smp_load_acquire(&p->on_cpu). */ - next->on_cpu =1 ; +WRITE_ONCE (next->on_cpu,1 );This is more than a documentation change.
It had better be an effective no-change though; as documented we only ever write 0 or 1, so even if the compiler is evil and tears our write, it is impossible to get this wrong.
The reason I made it WRITE_ONCE() is because the other write is smp_store_release() and the two loads are smp_load_acquire(), so a plain store is 'weird'.
Hi,
Quoted 7 lines · Peter Zijlstra
Dave hit the problem fixed by commit:
b6e13e85829f("sched/core: Fixttwu()race")and failed to understand much of the code involved. Per his request a few comments to (hopefully) clarify things.
All of the below is already tremendously helpful! I remember it took me quite some time to figure out e.g. how we could observe p->on_cpu && !p->on_rq and why we cared about it in ttwu(). On the bright side, I'm happy that my notes aren't completely off - there may be hope for me yet.
Have some small comments below.
Quoted 12 lines
Requested-by Dave Chinner <[email protected]>Signed-off-by Peter Zijlstra (Intel) <[email protected]>--- include/linux/sched.h | 12 ++-- kernel/sched/core.c | 195 +++++++++++++++++++++++++++++++++++++++++++------- kernel/sched/sched.h | 11 +++ 3 files changed, 187 insertions(+), 31 deletions(-)include/linux/sched.h +0
-0
[...]
Quoted 10 lines
+ * Special state:
+ *
+ * System-calls and anything external will usetask_rq_lock()which acquires
+ * bothp->lockandrq->lock. As a consequence the state they change is stable
+ * while holding either lock:
+ *+ * - sched_setaffinity(): p->cpus_ptr + * - set_user_nice(): p->se.load, p->static_prio + * - __sched_setscheduler(): p->sched_class, p->policy, p->*prio, p->se.load,+ * p->dl.dl_{runtime, deadline, period, flags, bw, density}
Only extra thing that comes to mind is p->uclamp*; dunno how exhaustive you want this list to be.
Quoted 23 lines
+ * -
sched_setnuma():p->numa_preferred_nid
+ * - sched_move_task()/
+ *cpu_cgroup_fork():p->sched_task_group
+ *
+ *p->state<- TASK_*:
+ *+ * is changed locklessly using set_current_state(), __set_current_state() or + * set_special_state(), see their respective comments, or by + * try_to_wake_up(). This latter uses p->pi_lock to serialize against + * concurrent self. + * + * p->on_rq <- { 0, 1 = TASK_ON_RQ_QUEUED, 2 = TASK_ON_RQ_MIGRATING }: + * + * is set by activate_task() and cleared by deactivate_task(), under + * rq->lock. Non-zero indicates the task is runnable, the special + * ON_RQ_MIGRATING state is used for migration without holding both + * rq->locks. It indicates task_cpu() is not stable, see task_rq_lock(). + * + * p->on_cpu <- { 0, 1 }: + * + * is set by prepare_task() and cleared by finish_task() such that it will be + * set before p is scheduled-in and cleared after p is scheduled-out, both + * under rq->lock. Non-zero indicates the task is running on it's CPU.
Quoted 11 lines
+ *
+ * [ The astute reader will observe that it is possible for two tasks on one
+ * CPU to have ->on_cpu = 1 at the same time. ]
+ *
+ *task_cpu(p): is changed byset_task_cpu(), the rules are:
+ *
+ * - Don't callset_task_cpu()on a blocked task:
+ *
+ * We don't care what CPU we're not running on, this simplifies hotplug,
+ * the CPU assignment of blocked tasks isn't required to be valid.
+ *
That's more of a good practice rather than a hard rule, right? We do that with proxy execution (the whole migrate to owner's rq thing), at least in its current shape.
Quoted 9 lines
+ * - for
try_to_wake_up(), called underp->pi_lock:
+ *
+ * This allowstry_to_wake_up()to only take onerq->lock, see its comment.
+ *
+ * - for migration called underrq->lock:
+ * [ seetask_on_rq_migrating()intask_rq_lock()]
+ *
+ * omove_queued_task()
+ * o__migrate_swap_task()
Isn't that one under double_rq_lock()?
Quoted 13 lines
+ * o
detach_task()
+ *
+ * - for migration called underdouble_rq_lock():
+ *+ * o push_rt_task() / pull_rt_task() + * o push_dl_task() / pull_dl_task() + * o dl_task_offline_migration()+ *
+ */
+
/*
*__task_rq_lock- lock the rq @p resides on.
*/
[...]
Quoted 14 lines
}
/*
- * Called in case the task @p isn't fully descheduled from its runqueue,
- * in this case we must do a remote wakeup. Its a 'light' wakeup though,
- * since all we need to do is flipp->statetoTASK_RUNNING, since
- * the task is still ->on_rq.
+ * Consider @p being inside a wait loop:
+ *
+ * for (;;) {
+ *set_current_state(TASK_UNINTERRUPTIBLE);
+ *
+ * if (CONDITION)
+ * break;
For some reason the alignment is off in my mail view, but looks okay once applied.
Quoted 9 lines
+ *
+ *schedule();
+ * }
+ *__set_current_state(TASK_RUNNING);
+ *
+ * betweenset_current_state()andschedule(). In this case @p is still
+ * runnable, so all that needs doing is changep->stateback toTASK_RUNNINGin
+ * an atomic manner.
+ *
Sorry if I'm being dense; don't you mean "running" here? If it stops being current inbetween set_current_state() and schedule(), __schedule() will deactivate() it, so AFAICT it can only be either running or deactivated.
Quoted 13 lines
+ * By taking task_rq(p)->lock we serialize against
schedule(), if @p->on_rq
+ * thenschedule()must still happen andp->statecan be changed to
+ *TASK_RUNNING. Otherwise we lost the race,schedule()has happened, and we
+ * need to do a full wakeup with enqueue.
+ *
+ * Returns: %true when the wakeup is done,
+ * %false otherwise.
*/include/linux/sched.h +1
-1-static int ttwu_remote (struct task_struct *p,int wake_flags) +static int ttwu_runnable (struct task_struct *p,int wake_flags) {struct rq_flags rf;struct rq *rq;
[...]
Quoted 25 lines
include/linux/sched.h +15
-3@@ -2494,15 +2608,41 @@ static void ttwu_queue(struct task_struct *p, int cpu, int wake_flags)* @state: the mask of task states that can be woken * @wake_flags: wake modifier flags (WF_*) * -* If (@state & @p->state) @p->state = TASK_RUNNING. +* Conceptually does: +* +* If (@state & @p->state) @p->state = TASK_RUNNING. * * If the task was not queued/runnable, also place it back on a runqueue. * -* Atomic against schedule() which would dequeue a task, also see -* set_current_state(). +* This function: +* - is atomic against schedule() which would dequeue the task; +* - issues a full memory barrier before accessing @p->state. +* See the comment with set_current_state(). +* +* Uses p->pi_lock to serialize against concurrent wake-ups. +* +* Relies on p->pi_lock stabilizing: +* - p->sched_class +* - p->cpus_ptr +* - p->sched_task_group +* in order to do migration, see its use of select_task_rq()/set_task_cpu().
include/linux/sched.h static void ttwu_queue(struct task_struct *p, int cpu, int wake_flags) · line 2636
Quoted 10 lines
include/linux/sched.h +7
-2* -* This function executes a full memory barrier before accessing the task -* state; see set_current_state(). +* Tries really hard to only take one task_rq(p)->lock for performance. +* Takes rq->lock in: +* - ttwu_runnable() -- old rq, unavoidable, see comment there; +* - ttwu_queue() -- new rq, for enqueue of the task; +* - psi_ttwu_dequeue() -- much sadness :-( accounting will kill us. +* +* As a concequence we race really badly with just about everything. See the
s/concequence/consequence/
Quoted 42 lines
include/linux/sched.h +13
-4+* many memory barriers and their comments for details. The basic order of +* reading things is: +* +* LOAD p->state +* RMB +* LOAD p->on_rq +* RMB +* LOAD-ACQUIRE p->on_cpu +* LOAD task_cpu() * * Return: %true if @p->state changes (an actual wakeup was done), * %false otherwise. @@ -2518,7 +2658,7 @@ try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)/* * We're waking current, this means 'p->on_rq' and 'task_cpu(p) * == smp_processor_id()'. Together this means we can special -* case the whole 'p->on_rq && ttwu_remote()' case below +* case the whole 'p->on_rq && ttwu_runnable()' case below * without taking any locks. * * In particular: @@ -2539,8 +2679,8 @@ try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)/* * If we are going to wake up a thread waiting for CONDITION we * need to ensure that CONDITION=1 done by the caller can not be -* reordered with p->state check below. This pairs with mb() in -* set_current_state() the waiting thread does. +* reordered with p->state check below. This pairs with smp_store_mb() +* in set_current_state() that the waiting thread does. */ raw_spin_lock_irqsave (&p->pi_lock, flags);smp_mb__after_spinlock ();@@ -2575,7 +2715,7 @@ try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)* A similar smb_rmb() lives in try_invoke_on_locked_down_task(). */ smp_rmb (); -if (p->on_rq &&ttwu_remote (p, wake_flags)) +if (p->on_rq &&ttwu_runnable (p, wake_flags)) goto unlock;if (p->in_iowait) {
include/linux/sched.h static inline void prepare_task(struct task_struct *next) · line 3280
Quoted 7 lines
include/linux/sched.h +4
-0@@ -3134,8 +3274,12 @@ static inline void prepare_task(struct task_struct *next)/* * Claim the task as running, we do this before switching to it * such that any running task will have this set. +* +* __schedule()'s rq->lock and smp_mb__after_spin_lock() orders this +* store against prior state change of @next, also see +* try_to_wake_up(), specifically smp_load_acquire(&p->on_cpu).
smp_*cond*_load_acquire(&p->on_cpu, <blah>)
Quoted 23 lines
include/linux/sched.h +4
-3*/ - next->on_cpu =1 ; +WRITE_ONCE (next->on_cpu,1 );#endif }@@ -3143,8 +3287,9 @@ static inline void finish_task(struct task_struct *prev) {#ifdef CONFIG_SMP /* -* After ->on_cpu is cleared, the task can be moved to a different CPU. -* We must ensure this doesn't happen until the switch is completely +* This must be the very last reference to @prev from this CPU. After +* p->on_cpu is cleared, the task can be moved to a different CPU. 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 kernel/sched/sched.h +0
-0
kernel/sched/sched.h struct rq_flags { · line 1204
Quoted 8 lines
kernel/sched/sched.h +5
-0@@ -1197,6 +1197,17 @@ struct rq_flags {#endif }; +/* +* Lockdep annotation that avoid accidental unlock; any +* raw_spin_unlock(&rq->lock) without preceding rq_unpin_lock() with the +* correct cookie will result in a WARN. +*
ISTR that being described (by yourself?) as a "sticky/continuous lockdep_assert_held()", which I think gets the point across.
Quoted 9 lines
kernel/sched/sched.h +6
-0+* This avoids code that has access to 'struct rq *rq' (basically everything in +* the scheduler) from accidentally unlocking the rq if they do not also have a +* copy of the (on-stack) 'struct rq_flags rf'. +* +* Also see Documentation/locking/lockdep-design.rst. +*/ static inline void rq_pin_lock (struct rq *rq,struct rq_flags *rf) { rf->cookie =lockdep_pin_lock (&rq->lock);
Peter Zijlstra
maintainerQuoted 11 lines · Valentin Schneider
Quoted 10 lines
+ * Special state:
+ *
+ * System-calls and anything external will usetask_rq_lock()which acquires
+ * bothp->lockandrq->lock. As a consequence the state they change is stable
+ * while holding either lock:
+ *+ * - sched_setaffinity(): p->cpus_ptr + * - set_user_nice(): p->se.load, p->static_prio + * - __sched_setscheduler(): p->sched_class, p->policy, p->*prio, p->se.load,+ * p->dl.dl_{runtime, deadline, period, flags, bw, density}
Quoted 2 lines
Only extra thing that comes to mind is p->uclamp*; dunno how exhaustive you want this list to be.
Indeed, I seem to have missed that one.
Quoted 13 lines
Quoted 5 lines
+ * -
sched_setnuma():p->numa_preferred_nid
+ * - sched_move_task()/
+ *cpu_cgroup_fork():p->sched_task_group
+ *Quoted 7 lines
+ *
task_cpu(p): is changed byset_task_cpu(), the rules are:
+ *
+ * - Don't callset_task_cpu()on a blocked task:
+ *
+ * We don't care what CPU we're not running on, this simplifies hotplug,
+ * the CPU assignment of blocked tasks isn't required to be valid.
+ *
Quoted 3 lines
That's more of a good practice rather than a hard rule, right? We do that with proxy execution (the whole migrate to owner's rq thing), at least in its current shape.
Yeah, but all of that isn't upstream yet. That said; the distinguishing feature there is that we create a class of blocked tasks that will still be 'runnable'. And as such we'll care about their placement.
Quoted 11 lines
Quoted 9 lines
+ * - for
try_to_wake_up(), called underp->pi_lock:
+ *
+ * This allowstry_to_wake_up()to only take onerq->lock, see its comment.
+ *
+ * - for migration called underrq->lock:
+ * [ seetask_on_rq_migrating()intask_rq_lock()]
+ *
+ * omove_queued_task()
+ * o__migrate_swap_task()Isn't that one under
double_rq_lock()?
Indeed, /me moves.
Quoted 23 lines
Quoted 10 lines
+ * o
detach_task()
+ *
+ * - for migration called underdouble_rq_lock():
+ *+ * o push_rt_task() / pull_rt_task() + * o push_dl_task() / pull_dl_task() + * o dl_task_offline_migration()+ *
+ */Quoted 12 lines
/*
- * Called in case the task @p isn't fully descheduled from its runqueue,
- * in this case we must do a remote wakeup. Its a 'light' wakeup though,
- * since all we need to do is flipp->statetoTASK_RUNNING, since
- * the task is still ->on_rq.
+ * Consider @p being inside a wait loop:
+ *
+ * for (;;) {
+ *set_current_state(TASK_UNINTERRUPTIBLE);
+ *
+ * if (CONDITION)
+ * break;
Quoted 2 lines
For some reason the alignment is off in my mail view, but looks okay once applied.
I'll go eradicate tabstops :-)
Quoted 10 lines
Quoted 9 lines
+ *
+ *schedule();
+ * }
+ *__set_current_state(TASK_RUNNING);
+ *
+ * betweenset_current_state()andschedule(). In this case @p is still
+ * runnable, so all that needs doing is changep->stateback toTASK_RUNNINGin
+ * an atomic manner.
+ *
Quoted 3 lines
Sorry if I'm being dense; don't you mean "running" here? If it stops being current inbetween
set_current_state()andschedule(),__schedule()willdeactivate()it, so AFAICT it can only be either running or deactivated.
Runnable, the task could be preempted. At this point we don't care if it is actually running or not.
Quoted 23 lines
Quoted 12 lines
+ * By taking task_rq(p)->lock we serialize against
schedule(), if @p->on_rq
+ * thenschedule()must still happen andp->statecan be changed to
+ *TASK_RUNNING. Otherwise we lost the race,schedule()has happened, and we
+ * need to do a full wakeup with enqueue.
+ *
+ * Returns: %true when the wakeup is done,
+ * %false otherwise.
*/kernel/sched/core.c +1
-1-static int ttwu_remote (struct task_struct *p,int wake_flags) +static int ttwu_runnable (struct task_struct *p,int wake_flags) {struct rq_flags rf;kernel/sched/core.c static void ttwu_queue(struct task_struct *p, int cpu, int wake_flags) · line 2636
Quoted 10 lines
kernel/sched/core.c +7
-0struct rq *rq; + * Tries really hard to only take one task_rq(p)->lock for performance. + * Takes rq->lock in: + * - ttwu_runnable() -- old rq, unavoidable, see comment there; + * - ttwu_queue() -- new rq, for enqueue of the task; + * - psi_ttwu_dequeue() -- much sadness :-( accounting will kill us. + * + * As a concequence we race really badly with just about everything. See the
Quoted 1 line
s/concequence/consequence/
ta!
Quoted 10 lines
kernel/sched/core.c static inline void prepare_task(struct task_struct *next) · line 3280
Quoted 8 lines
kernel/sched/core.c +4
-0@@ -3134,8 +3274,12 @@ static inline void prepare_task(struct task_struct *next)/* * Claim the task as running, we do this before switching to it * such that any running task will have this set. +* +* __schedule()'s rq->lock and smp_mb__after_spin_lock() orders this +* store against prior state change of @next, also see +* try_to_wake_up(), specifically smp_load_acquire(&p->on_cpu). smp_*cond*_load_acquire(&p->on_cpu, <blah>)
Both, but yeah.. arguably the cond one is the more important one.
Quoted 7 lines
Quoted 6 lines
kernel/sched/core.c +1
-1*/ - next->on_cpu =1 ; +WRITE_ONCE (next->on_cpu,1 );#endif }
Quoted 8 lines
kernel/sched/sched.h struct rq_flags { · line 1204
Quoted 5 lines
kernel/sched/sched.h +5
-0+/* +* Lockdep annotation that avoid accidental unlock; any +* raw_spin_unlock(&rq->lock) without preceding rq_unpin_lock() with the +* correct cookie will result in a WARN. +* ISTR that being described (by yourself?) as a "sticky/continuous
lockdep_assert_held()", which I think gets the point across.
Ah indeed! Clever of my past self :-) I'll go reword it.
Peter Zijlstra
maintainerQuoted 12 lines · Peter Zijlstra
Quoted 10 lines · Valentin Schneider
kernel/sched/core.c static inline void prepare_task(struct task_struct *next) · line 3280
Quoted 8 lines
kernel/sched/core.c +4
-0@@ -3134,8 +3274,12 @@ static inline void prepare_task(struct task_struct *next)/* * Claim the task as running, we do this before switching to it * such that any running task will have this set. +* +* __schedule()'s rq->lock and smp_mb__after_spin_lock() orders this +* store against prior state change of @next, also see +* try_to_wake_up(), specifically smp_load_acquire(&p->on_cpu). smp_*cond*_load_acquire(&p->on_cpu, <blah>)
Quoted 1 line
Both, but yeah.. arguably the cond one is the more important one.
Ah no, this one really want to match the WF_ON_CPU case. I'll clarify non-the-less.
Dietmar Eggemann
reviewerQuoted 10 lines · Peter Zijlstra
Dave hit the problem fixed by commit:
b6e13e85829f("sched/core: Fixttwu()race")and failed to understand much of the code involved. Per his request a few comments to (hopefully) clarify things.
Requested-by Dave Chinner <[email protected]>Signed-off-by Peter Zijlstra (Intel) <[email protected]>
LGTM. Just a couple of nitpicks below.
[...]
Quoted 4 lines
+ * Special state:
+ *
+ * System-calls and anything external will usetask_rq_lock()which acquires
+ * bothp->lockandrq->lock. As a consequence the state they change is stable
s/p->lock/p->pi_lock ?
Quoted 4 lines
+ * while holding either lock:
+ *
+ * -sched_setaffinity():p->cpus_ptr
+ * -set_user_nice():p->se.load,p->static_prio
Doesn't set_user_nice() also change p->prio and p->normal_prio, so p->*prio ?
Quoted 2 lines
+ * -
__sched_setscheduler():p->sched_class,p->policy, p->*prio,p->se.load,
+ * p->dl.dl_{runtime, deadline, period, flags, bw, density}
p->rt_priority ?
Quoted 3 lines
+ * -
sched_setnuma():p->numa_preferred_nid
+ * - sched_move_task()/
+ *cpu_cgroup_fork():p->sched_task_group
maybe also: set_cpus_allowed_ptr() -> __set_cpus_allowed_ptr() (like sched_setaffinity()) ?
[...]
kernel/sched/core.c static inline void prepare_task(struct task_struct *next) · line 3280
Quoted 8 lines
kernel/sched/core.c +4
-0@@ -3134,8 +3274,12 @@ static inline void prepare_task(struct task_struct *next)/* * Claim the task as running, we do this before switching to it * such that any running task will have this set. +* +* __schedule()'s rq->lock and smp_mb__after_spin_lock() orders this +* store against prior state change of @next, also see +* try_to_wake_up(), specifically smp_load_acquire(&p->on_cpu).
s/smp_load_acquire/smp_cond_load_acquire ?
[...]
Vincent Guittot
maintainerHi Peter,
Quoted 11 lines · Peter Zijlstra
Dave hit the problem fixed by commit:
b6e13e85829f("sched/core: Fixttwu()race")and failed to understand much of the code involved. Per his request a few comments to (hopefully) clarify things.
Requested-by Dave Chinner <[email protected]>Signed-off-by Peter Zijlstra (Intel) <[email protected]>
LGTM
I don't have any comment/nit that has not been already mentioned by others
Quoted 361 lines
--- include/linux/sched.h | 12 ++-- kernel/sched/core.c | 195 +++++++++++++++++++++++++++++++++++++++++++------- kernel/sched/sched.h | 11 +++ 3 files changed, 187 insertions(+), 31 deletions(-)include/linux/sched.h +6
-6@@ -158,24 +158,24 @@ struct task_group;* * for (;;) { * set_current_state(TASK_UNINTERRUPTIBLE); -* if (!need_sleep) -* break; +* if (CONDITION) +* break; * * schedule(); * } * __set_current_state(TASK_RUNNING); * * If the caller does not need such serialisation (because, for instance, the -* condition test and condition change and wakeup are under the same lock) then +* CONDITION test and condition change and wakeup are under the same lock) then * use __set_current_state(). * * The above is typically ordered against the wakeup, which does: * -* need_sleep = false; +* CONDITION = 1; * wake_up_state(p, TASK_UNINTERRUPTIBLE); * -* where wake_up_state() executes a full memory barrier before accessing the -* task state. +* where wake_up_state()/try_to_wake_up() executes a full memory barrier before +* accessing p->state. * * Wakeup will do: if (@state & p->state) p->state = TASK_RUNNING, that is, * once it observes the TASK_UNINTERRUPTIBLE store the waking CPU can issue a kernel/sched/core.c +170
-25@@ -77,6 +77,97 @@ __read_mostly int scheduler_running;*/ int sysctl_sched_rt_runtime =950000 ; + +/* +* Serialization rules: +* +* Lock order: +* +* p->pi_lock +* rq->lock +* hrtimer_cpu_base->lock (hrtimer_start() for bandwidth controls) +* +* rq1->lock +* rq2->lock where: rq1 < rq2 +* +* Regular state: +* +* Normal scheduling state is serialized by rq->lock. __schedule() takes the +* local CPU's rq->lock, it optionally removes the task from the runqueue and +* always looks at the local rq data structures to find the most elegible task +* to run next. +* +* Task enqueue is also under rq->lock, possibly taken from another CPU. +* Wakeups from another LLC domain might use an IPI to transfer the enqueue to +* the local CPU to avoid bouncing the runqueue state around [ see +* ttwu_queue_wakelist() ] +* +* Task wakeup, specifically wakeups that involve migration, are horribly +* complicated to avoid having to take two rq->locks. +* +* Special state: +* +* System-calls and anything external will use task_rq_lock() which acquires +* both p->lock and rq->lock. As a consequence the state they change is stable +* while holding either lock: +* +* - sched_setaffinity(): p->cpus_ptr +* - set_user_nice(): p->se.load, p->static_prio +* - __sched_setscheduler(): p->sched_class, p->policy, p->*prio, p->se.load, +* p->dl.dl_{runtime, deadline, period, flags, bw, density} +* - sched_setnuma(): p->numa_preferred_nid +* - sched_move_task()/ +* cpu_cgroup_fork(): p->sched_task_group +* +* p->state <- TASK_*: +* +* is changed locklessly using set_current_state(), __set_current_state() or +* set_special_state(), see their respective comments, or by +* try_to_wake_up(). This latter uses p->pi_lock to serialize against +* concurrent self. +* +* p->on_rq <- { 0, 1 = TASK_ON_RQ_QUEUED, 2 = TASK_ON_RQ_MIGRATING }: +* +* is set by activate_task() and cleared by deactivate_task(), under +* rq->lock. Non-zero indicates the task is runnable, the special +* ON_RQ_MIGRATING state is used for migration without holding both +* rq->locks. It indicates task_cpu() is not stable, see task_rq_lock(). +* +* p->on_cpu <- { 0, 1 }: +* +* is set by prepare_task() and cleared by finish_task() such that it will be +* set before p is scheduled-in and cleared after p is scheduled-out, both +* under rq->lock. Non-zero indicates the task is running on it's CPU. +* +* [ The astute reader will observe that it is possible for two tasks on one +* CPU to have ->on_cpu = 1 at the same time. ] +* +* task_cpu(p): is changed by set_task_cpu(), the rules are: +* +* - Don't call set_task_cpu() on a blocked task: +* +* We don't care what CPU we're not running on, this simplifies hotplug, +* the CPU assignment of blocked tasks isn't required to be valid. +* +* - for try_to_wake_up(), called under p->pi_lock: +* +* This allows try_to_wake_up() to only take one rq->lock, see its comment. +* +* - for migration called under rq->lock: +* [ see task_on_rq_migrating() in task_rq_lock() ] +* +* o move_queued_task() +* o __migrate_swap_task() +* o detach_task() +* +* - for migration called under double_rq_lock(): +* +* o push_rt_task() / pull_rt_task() +* o push_dl_task() / pull_dl_task() +* o dl_task_offline_migration() +* +*/ +/* * __task_rq_lock - lock the rq @p resides on. */ @@ -1466,8 +1557,7 @@ static struct rq *move_queued_task(struct rq *rq, struct rq_flags *rf, {lockdep_assert_held (&rq->lock); -WRITE_ONCE (p->on_rq,TASK_ON_RQ_MIGRATING ); -dequeue_task (rq, p,DEQUEUE_NOCLOCK ); +deactivate_task (rq, p,DEQUEUE_NOCLOCK );set_task_cpu (p, new_cpu);rq_unlock (rq, rf);@@ -1475,8 +1565,7 @@ static struct rq *move_queued_task(struct rq *rq, struct rq_flags *rf,rq_lock (rq, rf);BUG_ON (task_cpu (p) != new_cpu); -enqueue_task (rq, p,0 ); - p->on_rq =TASK_ON_RQ_QUEUED ; +activate_task (rq, p,0 );check_preempt_curr (rq, p,0 );return rq;@@ -2241,12 +2330,31 @@ ttwu_do_activate(struct rq *rq, struct task_struct *p, int wake_flags, }/* -* Called in case the task @p isn't fully descheduled from its runqueue, -* in this case we must do a remote wakeup. Its a 'light' wakeup though, -* since all we need to do is flip p->state to TASK_RUNNING, since -* the task is still ->on_rq. +* Consider @p being inside a wait loop: +* +* for (;;) { +* set_current_state(TASK_UNINTERRUPTIBLE); +* +* if (CONDITION) +* break; +* +* schedule(); +* } +* __set_current_state(TASK_RUNNING); +* +* between set_current_state() and schedule(). In this case @p is still +* runnable, so all that needs doing is change p->state back to TASK_RUNNING in +* an atomic manner. +* +* By taking task_rq(p)->lock we serialize against schedule(), if @p->on_rq +* then schedule() must still happen and p->state can be changed to +* TASK_RUNNING. Otherwise we lost the race, schedule() has happened, and we +* need to do a full wakeup with enqueue. +* +* Returns: %true when the wakeup is done, +* %false otherwise. */ -static int ttwu_remote (struct task_struct *p,int wake_flags) +static int ttwu_runnable (struct task_struct *p,int wake_flags) {struct rq_flags rf;struct rq *rq;@@ -2387,6 +2495,14 @@ static bool ttwu_queue_wakelist(struct task_struct *p, int cpu, int wake_flags) return false; } + +#else /* !CONFIG_SMP */ + +static inline bool ttwu_queue_wakelist (struct task_struct *p,int cpu,int wake_flags) +{ +return false; +} +#endif /* CONFIG_SMP */ static void ttwu_queue (struct task_struct *p,int cpu,int wake_flags)@@ -2394,10 +2510,8 @@ static void ttwu_queue(struct task_struct *p, int cpu, int wake_flags)struct rq *rq =cpu_rq (cpu);struct rq_flags rf; -#if defined(CONFIG_SMP )if (ttwu_queue_wakelist (p, cpu, wake_flags))return ; -#endif rq_lock (rq, &rf);update_rq_clock (rq);@@ -2453,8 +2567,8 @@ static void ttwu_queue(struct task_struct *p, int cpu, int wake_flags)* 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_load_acquire(!X->on_cpu) +* 1) smp_store_release(X->on_cpu, 0) -- finish_task() +* 2) smp_cond_load_acquire(!X->on_cpu) -- try_to_wake_up() * * Example: * @@ -2494,15 +2608,41 @@ static void ttwu_queue(struct task_struct *p, int cpu, int wake_flags)* @state: the mask of task states that can be woken * @wake_flags: wake modifier flags (WF_*) * -* If (@state & @p->state) @p->state = TASK_RUNNING. +* Conceptually does: +* +* If (@state & @p->state) @p->state = TASK_RUNNING. * * If the task was not queued/runnable, also place it back on a runqueue. * -* Atomic against schedule() which would dequeue a task, also see -* set_current_state(). +* This function: +* - is atomic against schedule() which would dequeue the task; +* - issues a full memory barrier before accessing @p->state. +* See the comment with set_current_state(). +* +* Uses p->pi_lock to serialize against concurrent wake-ups. +* +* Relies on p->pi_lock stabilizing: +* - p->sched_class +* - p->cpus_ptr +* - p->sched_task_group +* in order to do migration, see its use of select_task_rq()/set_task_cpu(). * -* This function executes a full memory barrier before accessing the task -* state; see set_current_state(). +* Tries really hard to only take one task_rq(p)->lock for performance. +* Takes rq->lock in: +* - ttwu_runnable() -- old rq, unavoidable, see comment there; +* - ttwu_queue() -- new rq, for enqueue of the task; +* - psi_ttwu_dequeue() -- much sadness :-( accounting will kill us. +* +* As a concequence we race really badly with just about everything. See the +* many memory barriers and their comments for details. The basic order of +* reading things is: +* +* LOAD p->state +* RMB +* LOAD p->on_rq +* RMB +* LOAD-ACQUIRE p->on_cpu +* LOAD task_cpu() * * Return: %true if @p->state changes (an actual wakeup was done), * %false otherwise. @@ -2518,7 +2658,7 @@ try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)/* * We're waking current, this means 'p->on_rq' and 'task_cpu(p) * == smp_processor_id()'. Together this means we can special -* case the whole 'p->on_rq && ttwu_remote()' case below +* case the whole 'p->on_rq && ttwu_runnable()' case below * without taking any locks. * * In particular: @@ -2539,8 +2679,8 @@ try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)/* * If we are going to wake up a thread waiting for CONDITION we * need to ensure that CONDITION=1 done by the caller can not be -* reordered with p->state check below. This pairs with mb() in -* set_current_state() the waiting thread does. +* reordered with p->state check below. This pairs with smp_store_mb() +* in set_current_state() that the waiting thread does. */ raw_spin_lock_irqsave (&p->pi_lock, flags);smp_mb__after_spinlock ();@@ -2575,7 +2715,7 @@ try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)* A similar smb_rmb() lives in try_invoke_on_locked_down_task(). */ smp_rmb (); -if (p->on_rq &&ttwu_remote (p, wake_flags)) +if (p->on_rq &&ttwu_runnable (p, wake_flags)) goto unlock;if (p->in_iowait) {@@ -3134,8 +3274,12 @@ static inline void prepare_task(struct task_struct *next)/* * Claim the task as running, we do this before switching to it * such that any running task will have this set. +* +* __schedule()'s rq->lock and smp_mb__after_spin_lock() orders this +* store against prior state change of @next, also see +* try_to_wake_up(), specifically smp_load_acquire(&p->on_cpu). */ - next->on_cpu =1 ; +WRITE_ONCE (next->on_cpu,1 );#endif }@@ -3143,8 +3287,9 @@ static inline void finish_task(struct task_struct *prev) {#ifdef CONFIG_SMP /* -* After ->on_cpu is cleared, the task can be moved to a different CPU. -* We must ensure this doesn't happen until the switch is completely +* This must be the very last reference to @prev from this CPU. After +* p->on_cpu is cleared, the task can be moved to a different CPU. 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 kernel/sched/sched.h +11
-0@@ -1197,6 +1197,17 @@ struct rq_flags {#endif }; +/* +* Lockdep annotation that avoid accidental unlock; any +* raw_spin_unlock(&rq->lock) without preceding rq_unpin_lock() with the +* correct cookie will result in a WARN. +* +* This avoids code that has access to 'struct rq *rq' (basically everything in +* the scheduler) from accidentally unlocking the rq if they do not also have a +* copy of the (on-stack) 'struct rq_flags rf'. +* +* Also see Documentation/locking/lockdep-design.rst. +*/ static inline void rq_pin_lock (struct rq *rq,struct rq_flags *rf) { rf->cookie =lockdep_pin_lock (&rq->lock);
The following commit has been merged into the sched/core branch of tip:
The following commit has been merged into the sched/core branch of tip:
Commit-ID: 58877d347b58c9e971112df5eb311c13bb0acb28 Gitweb: https://git.kernel.org/tip/58877d347b58c9e971112df5eb311c13bb0acb28 Author: Peter Zijlstra <[email protected]> AuthorDate: Thu, 02 Jul 2020 14:52:11 +02:00 Committer: Peter Zijlstra <[email protected]> CommitterDate: Wed, 22 Jul 2020 10:22:03 +02:00
sched: Better document ttwu()
Dave hit the problem fixed by commit:
b6e13e85829f ("sched/core: Fix ttwu() race")
and failed to understand much of the code involved. Per his request a few comments to (hopefully) clarify things.
--- include/linux/sched.h | 12 +-- kernel/sched/core.c | 188 +++++++++++++++++++++++++++++++++++------ kernel/sched/sched.h | 10 ++- 3 files changed, 179 insertions(+), 31 deletions(-)
include/linux/sched.h +6 -6
@@ -154,24 +154,24 @@ struct task_group;* * for (;;) { * set_current_state(TASK_UNINTERRUPTIBLE); -* if (!need_sleep) -* break; +* if (CONDITION) +* break; * * schedule(); * } * __set_current_state(TASK_RUNNING); * * If the caller does not need such serialisation (because, for instance, the -* condition test and condition change and wakeup are under the same lock) then +* CONDITION test and condition change and wakeup are under the same lock) then * use __set_current_state(). * * The above is typically ordered against the wakeup, which does: * -* need_sleep = false; +* CONDITION = 1; * wake_up_state(p, TASK_UNINTERRUPTIBLE); * -* where wake_up_state() executes a full memory barrier before accessing the -* task state. +* where wake_up_state()/try_to_wake_up() executes a full memory barrier before +* accessing p->state. * * Wakeup will do: if (@state & p->state) p->state = TASK_RUNNING, that is, * once it observes the TASK_UNINTERRUPTIBLE store the waking CPU can issue a
kernel/sched/core.c +163 -25
274 lines not on this page · raw message
kernel/sched/sched.h +10 -0
@@ -1203,6 +1203,16 @@ struct rq_flags {#endif }; +/* +* Lockdep annotation that avoids accidental unlocks; it's like a +* sticky/continuous lockdep_assert_held(). +* +* This avoids code that has access to 'struct rq *rq' (basically everything in +* the scheduler) from accidentally unlocking the rq if they do not also have a +* copy of the (on-stack) 'struct rq_flags rf'. +* +* Also see Documentation/locking/lockdep-design.rst. +*/ static inline void rq_pin_lock (struct rq *rq,struct rq_flags *rf) { rf->cookie =lockdep_pin_lock (&rq->lock);