Skip to contentSkip to conversation

sched: Add logic to handle parallel try_to_wake_up() of the same task

PATCH In review Kirill Tkhai 3 participants 6 messages Jul 13, 2013 – Jul 15, 2013 Scheduler

lore
Share & tools
lore
#0 lore raw

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 : 55
rcu_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 : 99
rcu_preempt
se.statistics.nr_wakeups : 2015010
se.statistics.nr_wakeups_parallel : 3738

CC Steven Rostedt <[email protected]>
CC Ingo Molnar <[email protected]>
CC Peter Zijlstra <[email protected]>
---
 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
index fc09d21..235a466 100644
@@ -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
index 9d06ad6..1e1475f 100644
@@ -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
index e076bdd..f18736d 100644
@@ -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
index 5aef494..dbbc6e9 100644
@@ -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
#1 lore raw
Quoted 5 lines · Kirill Tkhai

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.

Quoted 8 lines

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.

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

maintainer
#2 lore raw
In reply to Kirill Tkhai
Quoted 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
index fc09d21..235a466 100644

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
index 9d06ad6..1e1475f 100644

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 -1
 	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.

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);
#3 lore raw

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.h b/include/linux/sched.h index fc09d21..235a466 100644
 --- a/include/linux/sched.h
 +++ b/include/linux/sched.h
 @@ -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 9 lines

  };
  #endif

 diff --git a/kernel/sched/core.c b/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;
  #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.

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(struct task_struct *p, unsigned int state, int wake_flags) {
          unsigned long flags;
 - int cpu, success = 0;
 + int cpu, success = 1;

Quoted 2 lines

 + /*
 + * 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.

Quoted 10 lines

 + */
          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 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->state while the task is still on the CPU and it might read the wrong p->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 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);

maintainer
#4 lore raw
Quoted 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->state while the task is still on the CPU and it might read the wrong p->state.

Quoted 8 lines

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.

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.

#5 lore raw

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->state while the task is still on the CPU and it might read the wrong p->state.

Quoted 8 lines

 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.

Quoted 7 lines

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.

Thanks for the explanation.

Kirill