sched: Add logic to handle parallel try_to_wake_up() of the same task
PATCH 1/1 sched: Add logic to handle parallel try_to_wake_up() of the same task
This patch adds optimization of try_to_wake_up() function for cases when the system is doing parallel wake_up of the same task on the different cpus. Also it adds accounting the statistics of these situations.
We check the status of the task we want to wake up. If it is TASK_WAKING then the task is manipulated by try_to_wake_up() on another cpu. And after this check it will be a moment when the task is queued and his status is TASK_RUNNING. We just return earlier when we are sure the task will be TASK_RUNNING in the future (maybe right after the check). The profit is we don't loop while we are waiting the spinlock.
There mustn't be any problems connected with we return earlier, besause scheduler allready does the same, when he queues a task in wake_list to be waked up on another cpu.
Parallel wake up is not unreal situation. Here is statistics from my 2-cpu laptop:
~# grep 'nr_wakeups_parallel.*[1-9]' -B100 -h /proc/*/sched | grep 'threads\|parallel\|wakeups ' | sed 's/(.*)//g'
rcu_sched
se.statistics.nr_wakeups : 102
se.statistics.nr_wakeups_parallel : 2
Xorg
se.statistics.nr_wakeups : 36030
se.statistics.nr_wakeups_parallel : 56
gnome-terminal
se.statistics.nr_wakeups : 70573
se.statistics.nr_wakeups_parallel : 55rcu_preempt
se.statistics.nr_wakeups : 68101
se.statistics.nr_wakeups_parallel : 1368
It's the moment after boot (5-10 minutes uptime). Later the ratio goes down:
rcu_sched
se.statistics.nr_wakeups : 102
se.statistics.nr_wakeups_parallel : 2
Xorg
se.statistics.nr_wakeups : 49057
se.statistics.nr_wakeups_parallel : 74
gnome-terminal
se.statistics.nr_wakeups : 1495463
se.statistics.nr_wakeups_parallel : 99rcu_preempt
se.statistics.nr_wakeups : 2015010
se.statistics.nr_wakeups_parallel : 3738
--- include/linux/sched.h | 1 + kernel/sched/core.c | 29 +++++++++++++++++++++++++---- kernel/sched/debug.c | 7 +++++++ kernel/sched/stats.h | 16 ++++++++++++++++ 4 files changed, 49 insertions(+), 4 deletions(-)
include/linux/sched.h +1 -0
@@ -964,6 +964,7 @@ struct sched_statistics {u64 nr_wakeups_affine_attempts;u64 nr_wakeups_passive;u64 nr_wakeups_idle; + atomic_t nr_wakeups_parallel; };#endif
kernel/sched/core.c +25 -4
@@ -1336,6 +1336,11 @@ ttwu_do_wakeup(struct rq *rq, struct task_struct *p, int wake_flags) p->state =TASK_RUNNING ;#ifdef CONFIG_SMP +/* +* Pair bracket with TASK_WAKING check it try_to_wake_up() +*/ +smp_wmb (); +if (p->sched_class->task_woken) p->sched_class->task_woken (rq, p);
@@ -1487,20 +1492,37 @@ static int try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags) { unsigned long flags; -int cpu, success =0 ; +int cpu, success =1 ; +/* +* See commentary for commit 04e2f1741d235ba599037734878d72e57cb302b5. +*/ smp_wmb (); +#ifdef CONFIG_SMP +if (p->state ==TASK_WAKING ) { +/* +* Pairs with sets of p->state: below and in ttwu_do_wakeup(). +*/ +smp_rmb (); +inc_nr_parallel_wakeups (p); +return success; + } +#endif raw_spin_lock_irqsave (&p->pi_lock, flags); -if (!(p->state & state)) +if (!(p->state & state)) { + success =0 ; goto out; + } - success =1 ;/* we're going to change ->state */ cpu =task_cpu (p);if (p->on_rq &&ttwu_remote (p, wake_flags)) goto stat;#ifdef CONFIG_SMP + p->state =TASK_WAKING ; +smp_wmb (); +/* * If the owning (remote) cpu is still in the middle of schedule() with * this task as prev, wait until its done referencing the task.
@@ -1513,7 +1535,6 @@ try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)smp_rmb (); p->sched_contributes_to_load = !!task_contributes_to_load (p); - p->state =TASK_WAKING ;if (p->sched_class->task_waking) p->sched_class->task_waking (p);
kernel/sched/debug.c +7 -0
@@ -542,6 +542,13 @@ void proc_sched_show_task(struct task_struct *p, struct seq_file *m)P (se.statistics.nr_wakeups_idle); { +int nr =get_nr_parallel_wakeups (p); + +SEQ_printf (m,"%-45s:%21d\n" , +"se.statistics.nr_wakeups_parallel" , nr); + } + + {u64 avg_atom, avg_per_cpu; avg_atom = p->se.sum_exec_runtime;
kernel/sched/stats.h +16 -0
@@ -155,6 +155,22 @@ sched_info_switch(struct task_struct *prev, struct task_struct *next)#define sched_info_switch (t, next) do { } while (0)#endif /* CONFIG_SCHEDSTATS || CONFIG_TASK_DELAY_ACCT */ +#if defined(CONFIG_SCHEDSTATS ) && defined(CONFIG_SMP ) +static inline void +inc_nr_parallel_wakeups (struct task_struct *t) +{ +atomic_inc (&t->se.statistics.nr_wakeups_parallel); +} +static inline int +get_nr_parallel_wakeups (struct task_struct *t) +{ +return atomic_read (&t->se.statistics.nr_wakeups_parallel); +} +#else +#define inc_nr_parallel_wakeups (t) do { } while (0) +#define get_nr_parallel_wakeups (t) (0) +#endif /* CONFIG_SCHEDSTATS && CONFIG_SMP */ +/* * The following are functions that support scheduler-internal time accounting. * These functions are generally called at the timer tick. None of this depends
Quoted 5 lines · Kirill Tkhai
This patch adds optimization of
try_to_wake_up()function for cases when the system is doing parallelwake_upof the same task on the different cpus. Also it adds accounting the statistics of these situations.
Quoted 8 lines
We check the status of the task we want to wake up. If it is
TASK_WAKINGthen the task is manipulated bytry_to_wake_up()on another cpu. And after this check it will be a moment when the task is queued and his status isTASK_RUNNING. We just return earlier when we are sure the task will beTASK_RUNNINGin the future (maybe right after the check). The profit is we don't loop while we are waiting the spinlock.
Hm, you're adding cycles to the common case to shave spin cycles in the very rare case, then spending some to note that a collision happened. What makes recording worth even 1 cycle? What am I gonna do with the knowledge that $dinkynum wakeups intersected at a some random task?
-Mike
Peter Zijlstra
maintainerQuoted 11 lines · Kirill Tkhai
--- include/linux/sched.h | 1 + kernel/sched/core.c | 29 +++++++++++++++++++++++++---- kernel/sched/debug.c | 7 +++++++ kernel/sched/stats.h | 16 ++++++++++++++++ 4 files changed, 49 insertions(+), 4 deletions(-)include/linux/sched.h +0
-0
include/linux/sched.h struct sched_statistics { · line 967
Quoted 4 lines
include/linux/sched.h +1
-0@@ -964,6 +964,7 @@ struct sched_statistics {u64 nr_wakeups_affine_attempts;u64 nr_wakeups_passive;u64 nr_wakeups_idle; +atomic_t nr_wakeups_parallel;
bad idea.. atomics are expensive and stats aren't generally _that_ important.
Quoted 8 lines
include/linux/sched.h +0
-0};#endif kernel/sched/core.c +0
-0
kernel/sched/core.c ttwu_do_wakeup(struct rq *rq, struct task_struct *p, int wake_flags) · line 1343
Quoted 8 lines
kernel/sched/core.c +5
-0@@ -1336,6 +1336,11 @@ ttwu_do_wakeup(struct rq *rq, struct task_struct *p, int wake_flags) p->state =TASK_RUNNING ;#ifdef CONFIG_SMP +/* +* Pair bracket with TASK_WAKING check it try_to_wake_up() +*/ +smp_wmb (); +
Like Mike said, you're making the common case more expensive, this is not appreciated.
kernel/sched/core.c static int · line 1498
Quoted 12 lines
kernel/sched/core.c +3
-1if (p->sched_class->task_woken) p->sched_class->task_woken (rq, p);@@ -1487,20 +1492,37 @@ static int try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags) { unsigned long flags; -int cpu, success =0 ; +int cpu, success =1 ; +/* +* See commentary for commit 04e2f1741d235ba599037734878d72e57cb302b5.
That must be the worst barrier comment ever.. If you want it there, just copy/paste the commit log here. It is also completely unrelated to the rest of the patch.
kernel/sched/core.c static int · line 1508
Quoted 10 lines
kernel/sched/core.c +9
-0+*/ smp_wmb (); +#ifdef CONFIG_SMP +if (p->state ==TASK_WAKING ) { +/* +* Pairs with sets of p->state: below and in ttwu_do_wakeup(). +*/ +smp_rmb (); +inc_nr_parallel_wakeups (p); +return success;
This is wrong, you didn't change p->state, therefore returning 1 is not an option. If you want to do something like this, treat it like waking an already running task.
Also, the barrier comments fail to explain the exact problem they're solving.
Quoted 9 lines
kernel/sched/core.c +5
-1+ } +#endif raw_spin_lock_irqsave (&p->pi_lock, flags); -if (!(p->state & state)) +if (!(p->state & state)) { + success =0 ; goto out; + }
kernel/sched/core.c static int · line 1525
Quoted 10 lines
kernel/sched/core.c +3
-1- success =1 ;/* we're going to change ->state */ cpu =task_cpu (p);if (p->on_rq &&ttwu_remote (p, wake_flags)) goto stat;#ifdef CONFIG_SMP + p->state =TASK_WAKING ; +smp_wmb (); +
This too is broken; the loop below needs to be completed first, otherwise we change p->state while the task is still on the CPU and it might read the wrong p->state.
Quoted 11 lines
kernel/sched/core.c +0
-1/* * If the owning (remote) cpu is still in the middle of schedule() with * this task as prev, wait until its done referencing the task. @@ -1513,7 +1535,6 @@ try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)smp_rmb (); p->sched_contributes_to_load = !!task_contributes_to_load (p); - p->state =TASK_WAKING ;if (p->sched_class->task_waking) p->sched_class->task_waking (p);
Hi, Peter,
15.07.2013, 10:32, "Peter Zijlstra" <[email protected]>:
Quoted 91 lines · Kirill Tkhai
Quoted 7 lines
---
include/linux/sched.h | 1 +kernel/sched/core.c| 29 +++++++++++++++++++++++++----kernel/sched/debug.c| 7 +++++++kernel/sched/stats.h| 16 ++++++++++++++++4 files changed, 49 insertions(+), 4 deletions(-)Quoted 9 lines
diff --git
a/include/linux/sched.hb/include/linux/sched.hindex fc09d21..235a466 100644
---a/include/linux/sched.h
+++b/include/linux/sched.h
@@ -964,6 +964,7 @@ structsched_statistics{
u64nr_wakeups_affine_attempts;
u64nr_wakeups_passive;
u64nr_wakeups_idle;
+atomic_tnr_wakeups_parallel;bad idea.. atomics are expensive and stats aren't generally _that_ important.
Quoted 9 lines
};
#endifdiff --git
a/kernel/sched/core.cb/kernel/sched/core.c
index 9d06ad6..1e1475f 100644
---a/kernel/sched/core.c
+++b/kernel/sched/core.c
@@ -1336,6 +1336,11 @@ttwu_do_wakeup(struct rq *rq, struct task_struct *p, int wake_flags)Quoted 7 lines
p->state =
TASK_RUNNING;
#ifdefCONFIG_SMP
+ /*
+ * Pair bracket withTASK_WAKINGcheck ittry_to_wake_up()
+ */
+smp_wmb();
+Like Mike said, you're making the common case more expensive, this is not appreciated.
Quoted 10 lines
if (
p->sched_class->task_woken)p->sched_class->task_woken(rq, p);@@ -1487,20 +1492,37 @@ static int
try_to_wake_up(structtask_struct*p, unsigned int state, intwake_flags) {
unsigned long flags;
- int cpu, success = 0;
+ int cpu, success = 1;Quoted 2 lines
+ /*
+ * See commentary for commit04e2f1741d235ba599037734878d72e57cb302b5.That must be the worst barrier comment ever.. If you want it there, just copy/paste the commit log here. It is also completely unrelated to the rest of the patch.
Quoted 10 lines
+ */
smp_wmb();
+#ifdefCONFIG_SMP
+ if (p->state==TASK_WAKING) {
+ /*
+ * Pairs with sets ofp->state: below and inttwu_do_wakeup().
+ */
+smp_rmb();
+inc_nr_parallel_wakeups(p);
+ return success;This is wrong, you didn't change
p->state, therefore returning 1 is not an option. If you want to do something like this, treat it like waking an already running task.Also, the barrier comments fail to explain the exact problem they're solving.
Quoted 15 lines
+ }
+#endif
raw_spin_lock_irqsave(&p->pi_lock, flags);
- if (!(p->state & state))
+ if (!(p->state & state)) {
+ success = 0;
goto out;
+ }- success = 1; /* we're going to change ->state */ cpu =
task_cpu(p);if (
p->on_rq&&ttwu_remote(p, wake_flags)) goto stat;
Quoted 8 lines
Quoted 4 lines
#ifdef
CONFIG_SMP
+p->state=TASK_WAKING;
+smp_wmb();
+This too is broken; the loop below needs to be completed first, otherwise we change
p->statewhile the task is still on the CPU and it might read the wrongp->state.
This place is below (on_rq && ttwu_remote) check, so the task either 'dequeued and on_cpu == 0'
or it's in the middle of schedule() on arch, which wants unlocked context switch.
Nobody scheduler's probes p->state between prepare_lock_switch() and finish_lock_switch(). Archs with unlocked ctx switch (mips and ia64) don't change or probe state of previous process during context_switch.
The only exception is TASK_DEAD case, but it is handled above in 'p->state & state' check. Nobody passes TASK_DEAD to try_to_wake_up().
p->state might be changed outside from the scheduler. It's ptrace. But, it doesn't look be touched by earlier TASK_WAKING set.
So, I don't see any problem with it. Peter, what do you really mean?
Other problems is easy to be fixed, all except common case overhead. If it's really considerable in terms of scheduler, I'll be account this fact in the future.
Quoted 11 lines
Quoted 11 lines
/*
* If the owning (remote) cpu is still in the middle ofschedule()with
* this task as prev, wait until its done referencing the task.
@@ -1513,7 +1535,6 @@try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)smp_rmb();p->sched_contributes_to_load = !!task_contributes_to_load(p);
-p->state=TASK_WAKING;if (
p->sched_class->task_waking)
p->sched_class->task_waking(p);
Peter Zijlstra
maintainerQuoted 10 lines · Kirill Tkhai
Quoted 9 lines
Quoted 5 lines
#ifdef
CONFIG_SMP
+p->state=TASK_WAKING;
+smp_wmb();
+This too is broken; the loop below needs to be completed first, otherwise we change
p->statewhile the task is still on the CPU and it might read the wrongp->state.
Quoted 8 lines
This place is below (
on_rq&&ttwu_remote) check, so the task either 'dequeued andon_cpu== 0'
or it's in the middle ofschedule()on arch, which wants unlocked context switch.Nobody scheduler's probes
p->statebetweenprepare_lock_switch()andfinish_lock_switch(). Archs with unlocked ctx switch (mips and ia64) don't change or probe state of previous process duringcontext_switch.
It means its after deactivate_task(), but before context_switch(). It so happens that context_switch()->prepare_task_switch()->trace_sched_switch() inspects p->state.
Even if this was not the case, touching a task that is 'life' on another CPU is very _very_ bad practise.
16.07.2013, 00:19, "Peter Zijlstra" <[email protected]>:
Quoted 18 lines · Kirill Tkhai
Quoted 8 lines
Quoted 8 lines
Quoted 5 lines
#ifdef
CONFIG_SMP
+p->state=TASK_WAKING;
+smp_wmb();
+This too is broken; the loop below needs to be completed first, otherwise we change
p->statewhile the task is still on the CPU and it might read the wrongp->state.Quoted 8 lines
This place is below (
on_rq&&ttwu_remote) check, so the task either 'dequeued andon_cpu== 0'
or it's in the middle ofschedule()on arch, which wants unlocked context switch.Nobody scheduler's probes
p->statebetweenprepare_lock_switch()andfinish_lock_switch(). Archs with unlocked ctx switch (mips and ia64) don't change or probe state of previous process duringcontext_switch.
Quoted 7 lines
It means its after
deactivate_task(), but beforecontext_switch(). It so happens that context_switch()->prepare_task_switch()->trace_sched_switch() inspectsp->state.Even if this was not the case, touching a task that is 'life' on another CPU is very _very_ bad practise.
Thanks for the explanation.
Kirill