Skip to contentSkip to conversation

sched: minimalist select_idle_sibling() bouncing cow syndrome fix

PATCH In review Mike Galbraith 2 participants 6 messages Jan 27, 2013 – Feb 4, 2013 Scheduler

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 sched: minimalist select_idle_sibling() bouncing cow syndrome fix

If the previous CPU is cache affine and idle, select it.

---
 kernel/sched/fair.c |   21 +++++++--------------
 1 file changed, 7 insertions(+), 14 deletions(-)
kernel/sched/fair.c +7 -14
@@ -3270,25 +3270,18 @@ find_idlest_cpu(struct sched_group *grou
  */
 static int select_idle_sibling(struct task_struct *p, int target)
 {
-	int cpu = smp_processor_id();
-	int prev_cpu = task_cpu(p);
 	struct sched_domain *sd;
 	struct sched_group *sg;
-	int i;
+	int i = task_cpu(p);
 
-	/*
-	 * If the task is going to be woken-up on this cpu and if it is
-	 * already idle, then it is the right target.
-	 */
-	if (target == cpu && idle_cpu(cpu))
-		return cpu;
+	if (idle_cpu(target))
+		return target;
 
 	/*
-	 * If the task is going to be woken-up on the cpu where it previously
-	 * ran and if it is currently idle, then it the right target.
+	 * If the prevous cpu is cache affine and idle, don't be stupid.
 	 */
-	if (target == prev_cpu && idle_cpu(prev_cpu))
-		return prev_cpu;
+	if (i != target && cpus_share_cache(i, target) && idle_cpu(i))
+		return i;
 
 	/*
 	 * Otherwise, iterate the domains and find an elegible idle cpu.
@@ -3302,7 +3295,7 @@ static int select_idle_sibling(struct ta
 				goto next;
 
 			for_each_cpu(i, sched_group_cpus(sg)) {
-				if (!idle_cpu(i))
+				if (i == target || !idle_cpu(i))
 					goto next;
 			}
 
#1 lore raw
Quoted 1 line · Mike Galbraith

If the previous CPU is cache affine and idle, select it.

No objections in principle - but would be nice to have a changelog with numbers, % of improvement included and so?

Thanks,

Ingo

#2 lore raw
Quoted 6 lines · Ingo Molnar
Quoted 1 line · Mike Galbraith

If the previous CPU is cache affine and idle, select it.

No objections in principle - but would be nice to have a changelog with numbers, % of improvement included and so?

Well, that like was my changelog, guess it needs improvement.

Take 2.

sched: minimalist select_idle_sibling() bouncing cow syndrome fix

If the previous CPU is cache affine and idle, select it.

The current implementation simply traverses the sd_llc domain, taking the first idle CPU encountered, which walks buddy pairs hand in hand over the package, inflicting excruciating pain.

1 tbench pair (worst case) in a 10 core + SMT package:

pre 15.22 MB/sec 1 procs
post 252.01 MB/sec 1 procs

---
 kernel/sched/fair.c |   21 +++++++--------------
 1 file changed, 7 insertions(+), 14 deletions(-)
kernel/sched/fair.c +7 -14
@@ -3270,25 +3270,18 @@ find_idlest_cpu(struct sched_group *grou
  */
 static int select_idle_sibling(struct task_struct *p, int target)
 {
-	int cpu = smp_processor_id();
-	int prev_cpu = task_cpu(p);
 	struct sched_domain *sd;
 	struct sched_group *sg;
-	int i;
+	int i = task_cpu(p);
 
-	/*
-	 * If the task is going to be woken-up on this cpu and if it is
-	 * already idle, then it is the right target.
-	 */
-	if (target == cpu && idle_cpu(cpu))
-		return cpu;
+	if (idle_cpu(target))
+		return target;
 
 	/*
-	 * If the task is going to be woken-up on the cpu where it previously
-	 * ran and if it is currently idle, then it the right target.
+	 * If the prevous cpu is cache affine and idle, don't be stupid.
 	 */
-	if (target == prev_cpu && idle_cpu(prev_cpu))
-		return prev_cpu;
+	if (i != target && cpus_share_cache(i, target) && idle_cpu(i))
+		return i;
 
 	/*
 	 * Otherwise, iterate the domains and find an elegible idle cpu.
@@ -3302,7 +3295,7 @@ static int select_idle_sibling(struct ta
 				goto next;
 
 			for_each_cpu(i, sched_group_cpus(sg)) {
-				if (!idle_cpu(i))
+				if (i == target || !idle_cpu(i))
 					goto next;
 			}
 
#3 lore raw
Quoted 16 lines · Mike Galbraith
Quoted 6 lines · Ingo Molnar
Quoted 1 line · Mike Galbraith

If the previous CPU is cache affine and idle, select it.

No objections in principle - but would be nice to have a changelog with numbers, % of improvement included and so?

Well, that like was my changelog, guess it needs improvement.

Take 2.

sched: minimalist select_idle_sibling() bouncing cow syndrome fix

If the previous CPU is cache affine and idle, select it.

Quoted 8 lines

The current implementation simply traverses the sd_llc domain, taking the first idle CPU encountered, which walks buddy pairs hand in hand over the package, inflicting excruciating pain.

1 tbench pair (worst case) in a 10 core + SMT package:

pre 15.22 MB/sec 1 procs
post 252.01 MB/sec 1 procs

Drool ... :-)

What would be a 'contrarian' test - i.e. a test where this could hurt most?

Thanks,

Ingo

#4 lore raw
Quoted 22 lines · Ingo Molnar
Quoted 20 lines · Mike Galbraith
Quoted 6 lines · Ingo Molnar
Quoted 1 line · Mike Galbraith

If the previous CPU is cache affine and idle, select it.

No objections in principle - but would be nice to have a changelog with numbers, % of improvement included and so?

Well, that like was my changelog, guess it needs improvement.

Take 2.

sched: minimalist select_idle_sibling() bouncing cow syndrome fix

If the previous CPU is cache affine and idle, select it.

The current implementation simply traverses the sd_llc domain, taking the first idle CPU encountered, which walks buddy pairs hand in hand over the package, inflicting excruciating pain.

Quoted 6 lines
Quoted 4 lines

1 tbench pair (worst case) in a 10 core + SMT package:

pre 15.22 MB/sec 1 procs
post 252.01 MB/sec 1 procs

Drool ... :-)

Yeah, it really is _that_ fugly as is.

Quoted 2 lines

What would be a 'contrarian' test - i.e. a test where this could hurt most?

There is none. It cuts off no preemption escape routes for pgbench, still has both good and evil faces for all to see, and some to turn to stone ;-) It only does one thing, don't do the unspeakable.

-Mike

#5 lore raw

[tip:sched/core] sched: Fix select_idle_sibling() bouncing cow syndrome

In reply to Mike Galbraith
Commit-ID:  e0a79f529d5ba2507486d498b25da40911d95cf6
Gitweb:     http://git.kernel.org/tip/e0a79f529d5ba2507486d498b25da40911d95cf6
Author:     Mike Galbraith <[email protected]>
AuthorDate: Mon, 28 Jan 2013 12:19:25 +0100
Committer:  Ingo Molnar <[email protected]>
CommitDate: Mon, 4 Feb 2013 20:07:24 +0100

sched: Fix select_idle_sibling() bouncing cow syndrome

If the previous CPU is cache affine and idle, select it.

The current implementation simply traverses the sd_llc domain, taking the first idle CPU encountered, which walks buddy pairs hand in hand over the package, inflicting excruciating pain.

1 tbench pair (worst case) in a 10 core + SMT package:

pre 15.22 MB/sec 1 procs
post 252.01 MB/sec 1 procs

---
 kernel/sched/fair.c | 21 +++++++--------------
 1 file changed, 7 insertions(+), 14 deletions(-)
kernel/sched/fair.c +7 -14
index 8dbee9f..ed18c74 100644
@@ -3252,25 +3252,18 @@ find_idlest_cpu(struct sched_group *group, struct task_struct *p, int this_cpu)
  */
 static int select_idle_sibling(struct task_struct *p, int target)
 {
-	int cpu = smp_processor_id();
-	int prev_cpu = task_cpu(p);
 	struct sched_domain *sd;
 	struct sched_group *sg;
-	int i;
+	int i = task_cpu(p);
 
-	/*
-	 * If the task is going to be woken-up on this cpu and if it is
-	 * already idle, then it is the right target.
-	 */
-	if (target == cpu && idle_cpu(cpu))
-		return cpu;
+	if (idle_cpu(target))
+		return target;
 
 	/*
-	 * If the task is going to be woken-up on the cpu where it previously
-	 * ran and if it is currently idle, then it the right target.
+	 * If the prevous cpu is cache affine and idle, don't be stupid.
 	 */
-	if (target == prev_cpu && idle_cpu(prev_cpu))
-		return prev_cpu;
+	if (i != target && cpus_share_cache(i, target) && idle_cpu(i))
+		return i;
 
 	/*
 	 * Otherwise, iterate the domains and find an elegible idle cpu.
@@ -3284,7 +3277,7 @@ static int select_idle_sibling(struct task_struct *p, int target)
 				goto next;
 
 			for_each_cpu(i, sched_group_cpus(sg)) {
-				if (!idle_cpu(i))
+				if (i == target || !idle_cpu(i))
 					goto next;
 			}