Skip to contentSkip to conversation

sched: make sync affine wakeups work

PATCH In review Rik van Riel 7 participants 46 messages May 2, 2014 – May 22, 2014 1 message not in the archive Scheduler

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 sched: make sync affine wakeups work

Currently sync wakeups from the wake_affine code cannot work as designed, because the task doing the sync wakeup from the target cpu will block its wakee from selecting that cpu.

This is despite the fact that whether or not the wakeup is sync determines whether or not we want to do an affine wakeup...

This patch allows sync wakeups to pick the waker's cpu.

Whether or not this is the right thing to do remains to be seen, but it does allow us to verify whether or not the wake_affine strategy of always doing affine wakeups and only disabling them in a specific circumstance is sound, or needs rethinking...

Not-yet-signed-off-by Rik van Riel <[email protected]>
---
 kernel/sched/fair.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)
kernel/sched/fair.c +3 -3
index 7570dd9..7f8fe16 100644
@@ -4358,13 +4358,13 @@ find_idlest_cpu(struct sched_group *group, struct task_struct *p, int this_cpu)
 /*
  * Try and locate an idle CPU in the sched_domain.
  */
-static int select_idle_sibling(struct task_struct *p, int target)
+static int select_idle_sibling(struct task_struct *p, int target, int sync)
 {
 	struct sched_domain *sd;
 	struct sched_group *sg;
 	int i = task_cpu(p);
 
-	if (idle_cpu(target))
+	if (idle_cpu(target) || (sync && cpu_rq(target)->nr_running == 1))
 		return target;
 
 	/*
@@ -4453,7 +4453,7 @@ select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_f
 		if (cpu != prev_cpu && wake_affine(affine_sd, p, sync))
 			prev_cpu = cpu;
 
-		new_cpu = select_idle_sibling(p, prev_cpu);
+		new_cpu = select_idle_sibling(p, prev_cpu, sync);
 		goto unlock;
 	}
 

.

#1 lore raw
Quoted 6 lines · Rik van Riel

Currently sync wakeups from the wake_affine code cannot work as designed, because the task doing the sync wakeup from the target cpu will block its wakee from selecting that cpu.

This is despite the fact that whether or not the wakeup is sync determines whether or not we want to do an affine wakeup...

If the sync hint really did mean we ARE going to schedule RSN, waking local would be a good thing. It is all too often a big fat lie.

-Mike

#2 lore raw
Quoted 10 lines · Mike Galbraith
Quoted 6 lines · Rik van Riel

Currently sync wakeups from the wake_affine code cannot work as designed, because the task doing the sync wakeup from the target cpu will block its wakee from selecting that cpu.

This is despite the fact that whether or not the wakeup is sync determines whether or not we want to do an affine wakeup...

If the sync hint really did mean we ARE going to schedule RSN, waking local would be a good thing. It is all too often a big fat lie.

BTW, we used to have avg_overlap and a sync less heuristic to improve the accuracy of the sync wakeup hint, but I ripped it out because it was dead wrong far too often. You can try reviving it, but preemption among other things break it. You'll have better luck with a simple context switch rate heuristic, but that's less than perfect too.

-Mike

#3 lore raw
In reply to Mike Galbraith
Quoted 10 lines · Mike Galbraith
Quoted 6 lines · Rik van Riel

Currently sync wakeups from the wake_affine code cannot work as designed, because the task doing the sync wakeup from the target cpu will block its wakee from selecting that cpu.

This is despite the fact that whether or not the wakeup is sync determines whether or not we want to do an affine wakeup...

If the sync hint really did mean we ARE going to schedule RSN, waking local would be a good thing. It is all too often a big fat lie.

One example of that is say pgbench. The mother of all work (server thread) for that load wakes with sync hint. Let the server wake the first of a small herd CPU affine, and that first wakee then preempt the server (mother of all work) that drives the entire load.

Byebye throughput.

When there's only one wakee, and there's really not enough overlap to at least break even, waking CPU affine is a great idea. Even when your wakees only run for a short time, if you wake/get_preempted repeat, the load will serialize.

-Mike

#4 lore raw
Quoted 17 lines · Mike Galbraith
Quoted 10 lines · Mike Galbraith
Quoted 6 lines · Rik van Riel

Currently sync wakeups from the wake_affine code cannot work as designed, because the task doing the sync wakeup from the target cpu will block its wakee from selecting that cpu.

This is despite the fact that whether or not the wakeup is sync determines whether or not we want to do an affine wakeup...

If the sync hint really did mean we ARE going to schedule RSN, waking local would be a good thing. It is all too often a big fat lie.

One example of that is say pgbench. The mother of all work (server thread) for that load wakes with sync hint. Let the server wake the first of a small herd CPU affine, and that first wakee then preempt the server (mother of all work) that drives the entire load.

Quoted 6 lines

Byebye throughput.

When there's only one wakee, and there's really not enough overlap to at least break even, waking CPU affine is a great idea. Even when your wakees only run for a short time, if you wake/get_preempted repeat, the load will serialize.

I see a similar issue with specjbb2013, with 4 backend and 4 frontend JVMs on a 4 node NUMA system.

The NUMA balancing code nicely places the memory of each JVM on one NUMA node, but then the wake_affine code will happily run all of the threads anywhere on the system, totally ruining memory locality.

The front end and back end only exchange a few hundred messages a second, over loopback tcp, so the switching rate between threads is quite low...

I wonder if it would make sense for wake_affine to be off by default, and only switch on when the right conditions are detected, instead of having it on by default like we have now?

I have some ideas on that, but I should probably catch some sleep before trying to code them up :)

Meanwhile, the test patch that I posted may help us figure out whether the "sync" option in the current wake_affine code does anything useful.

Signature · 1 line
All rights reversed
#5 lore raw
Quoted 25 lines · Rik van Riel
Quoted 17 lines · Mike Galbraith
Quoted 10 lines · Mike Galbraith
Quoted 6 lines · Rik van Riel

Currently sync wakeups from the wake_affine code cannot work as designed, because the task doing the sync wakeup from the target cpu will block its wakee from selecting that cpu.

This is despite the fact that whether or not the wakeup is sync determines whether or not we want to do an affine wakeup...

If the sync hint really did mean we ARE going to schedule RSN, waking local would be a good thing. It is all too often a big fat lie.

One example of that is say pgbench. The mother of all work (server thread) for that load wakes with sync hint. Let the server wake the first of a small herd CPU affine, and that first wakee then preempt the server (mother of all work) that drives the entire load.

Quoted 6 lines

Byebye throughput.

When there's only one wakee, and there's really not enough overlap to at least break even, waking CPU affine is a great idea. Even when your wakees only run for a short time, if you wake/get_preempted repeat, the load will serialize.

Quoted 7 lines

I see a similar issue with specjbb2013, with 4 backend and 4 frontend JVMs on a 4 node NUMA system.

The NUMA balancing code nicely places the memory of each JVM on one NUMA node, but then the wake_affine code will happily run all of the threads anywhere on the system, totally ruining memory locality.

Hm, I thought numasched got excessive pull crap under control. For steady hefty loads, you want to kill all but periodic load balancing once the thing gets cranked up. The less you move tasks, the better the load will perform. Bursty loads exist too though, damn the bad luck.

Quoted 7 lines

The front end and back end only exchange a few hundred messages a second, over loopback tcp, so the switching rate between threads is quite low...

I wonder if it would make sense for wake_affine to be off by default, and only switch on when the right conditions are detected, instead of having it on by default like we have now?

Not IMHO, but I have seen situations where that was exactly what I recommended to fix the throughput problem the user was having.

Reason why is that case was on a box where FAIR_SLEEPERS is disabled by default, meaning there is no such thing as wakeup preemption. Guess what happens when you don't have shared LLC for a fast/light wakee to escape to when the waker is a pig. The worst thing possible in that case is to wake affine. Leave the poor thing wherever it was, else it will take a latency hit that need not have been.

Quoted 2 lines

I have some ideas on that, but I should probably catch some sleep before trying to code them up :)

Yeah, there are many aspects to ponder.

Quoted 3 lines

Meanwhile, the test patch that I posted may help us figure out whether the "sync" option in the current wake_affine code does anything useful.

If I had a NAK stamp and digital ink pad, that patch wouldn't be readable, much less applicable ;-)

-Mike

#6 lore raw
Quoted 6 lines · Mike Galbraith

Reason why is that case was on a box where FAIR_SLEEPERS is disabled by default, meaning there is no such thing as wakeup preemption. Guess what happens when you don't have shared LLC for a fast/light wakee to escape to when the waker is a pig. The worst thing possible in that case is to wake affine. Leave the poor thing wherever it was, else it will take a latency hit that need not have been.

Oh yeah, and you'll see similar issues playing with kvm. No escape routes are available, as no llc domain exists. Globally do a sync wakeup CPU affine, and for some loads that will induce massive wreckage where as If select_isle_sibling() had been there to save the day, all would have been peachy. Is it good, or is it evil... depends.

-Mike

#7 lore raw
In reply to Rik van Riel
Quoted 4 lines · Rik van Riel

Whether or not this is the right thing to do remains to be seen, but it does allow us to verify whether or not the wake_affine strategy of always doing affine wakeups and only disabling them in a specific circumstance is sound, or needs rethinking...

Yes, it needs rethinking.

I know why you want to try this, yes, select_idle_sibling() is very much a two faced little bitch. NOHZ doesn't help, my kernels throttle it.

-Mike

#8 lore raw
Quoted 11 lines · Mike Galbraith
Quoted 4 lines · Rik van Riel

Whether or not this is the right thing to do remains to be seen, but it does allow us to verify whether or not the wake_affine strategy of always doing affine wakeups and only disabling them in a specific circumstance is sound, or needs rethinking...

Yes, it needs rethinking.

I know why you want to try this, yes, select_idle_sibling() is very much a two faced little bitch.

My biggest problem with select_idle_sibling and wake_affine in general is that it will override NUMA placement, even when processes only wake each other up infrequently...

Signature · 1 line
All rights reversed
#9 lore raw
Quoted 8 lines · Rik van Riel
Quoted 7 lines · Mike Galbraith
Quoted 4 lines · Rik van Riel

Whether or not this is the right thing to do remains to be seen, but it does allow us to verify whether or not the wake_affine strategy of always doing affine wakeups and only disabling them in a specific circumstance is sound, or needs rethinking...

Quoted 8 lines
Quoted 4 lines

Yes, it needs rethinking.

I know why you want to try this, yes, select_idle_sibling() is very much a two faced little bitch.

My biggest problem with select_idle_sibling and wake_affine in general is that it will override NUMA placement, even when processes only wake each other up infrequently...

Hm, seems the thing to do would be to tell select_task_rq_fair() to keep it's mitts off of tasks that the numasched stuff has placed rather than decapitating select_idle_sibling() or some other drastic measure.

-Mike

#10 lore raw
Quoted 14 lines · Mike Galbraith
Quoted 13 lines · Rik van Riel
Quoted 11 lines · Mike Galbraith
Quoted 4 lines · Rik van Riel

Whether or not this is the right thing to do remains to be seen, but it does allow us to verify whether or not the wake_affine strategy of always doing affine wakeups and only disabling them in a specific circumstance is sound, or needs rethinking...

Yes, it needs rethinking.

I know why you want to try this, yes, select_idle_sibling() is very much a two faced little bitch.

Quoted 7 lines
Quoted 3 lines

My biggest problem with select_idle_sibling and wake_affine in general is that it will override NUMA placement, even when processes only wake each other up infrequently...

Hm, seems the thing to do would be to tell select_task_rq_fair() to keep it's mitts off of tasks that the numasched stuff has placed rather than decapitating select_idle_sibling() or some other drastic measure.

Thing is, if tasks are waking each other up frequently enough, we probably DO want to place them near each other with select_idle_sibling.

We just cannot afford to have it as the default behaviour for casual wakeup activity, because it will mess up other things.

Signature · 1 line
All rights reversed
#11 lore raw
Quoted 19 lines · Rik van Riel
Quoted 18 lines · Mike Galbraith
Quoted 16 lines · Rik van Riel
Quoted 11 lines · Mike Galbraith
Quoted 4 lines · Rik van Riel

Whether or not this is the right thing to do remains to be seen, but it does allow us to verify whether or not the wake_affine strategy of always doing affine wakeups and only disabling them in a specific circumstance is sound, or needs rethinking...

Yes, it needs rethinking.

I know why you want to try this, yes, select_idle_sibling() is very much a two faced little bitch.

My biggest problem with select_idle_sibling and wake_affine in general is that it will override NUMA placement, even when processes only wake each other up infrequently...

Quoted 6 lines
Quoted 3 lines

Hm, seems the thing to do would be to tell select_task_rq_fair() to keep it's mitts off of tasks that the numasched stuff has placed rather than decapitating select_idle_sibling() or some other drastic measure.

Thing is, if tasks are waking each other up frequently enough, we probably DO want to place them near each other with select_idle_sibling.

Right. I'm thinking you could perhaps create a sched feature like NUMA_ME_HARDER or such so you can tell it to go away if you find that your load performs best when movement is left entirely up to the NUMA placement code.

Quoted 2 lines

We just cannot afford to have it as the default behaviour for casual wakeup activity, because it will mess up other things.

I think it is generally good, but yes, it has its bad it's bad side, why we have tweakables.

-Mike

#12 lore raw
Quoted 32 lines · Mike Galbraith
Quoted 19 lines · Rik van Riel
Quoted 18 lines · Mike Galbraith
Quoted 16 lines · Rik van Riel
Quoted 11 lines · Mike Galbraith
Quoted 4 lines · Rik van Riel

Whether or not this is the right thing to do remains to be seen, but it does allow us to verify whether or not the wake_affine strategy of always doing affine wakeups and only disabling them in a specific circumstance is sound, or needs rethinking...

Yes, it needs rethinking.

I know why you want to try this, yes, select_idle_sibling() is very much a two faced little bitch.

My biggest problem with select_idle_sibling and wake_affine in general is that it will override NUMA placement, even when processes only wake each other up infrequently...

Quoted 6 lines
Quoted 3 lines

Hm, seems the thing to do would be to tell select_task_rq_fair() to keep it's mitts off of tasks that the numasched stuff has placed rather than decapitating select_idle_sibling() or some other drastic measure.

Thing is, if tasks are waking each other up frequently enough, we probably DO want to place them near each other with select_idle_sibling.

Right. I'm thinking you could perhaps create a sched feature like NUMA_ME_HARDER or such so you can tell it to go away if you find that your load performs best when movement is left entirely up to the NUMA placement code.

Quoted 5 lines
Quoted 2 lines

We just cannot afford to have it as the default behaviour for casual wakeup activity, because it will mess up other things.

I think it is generally good, but yes, it has its bad it's bad side, why we have tweakables.

Slightly garbled (multitasking).

To make that a little clearer, generally, trying to bring waker and wakee together is a good thing. I think changing the default to avoid doing the generally good thing is wrong. Box drivers should be given whatever knobs they need to adjust as required, and use them, because there is no one correct answer.

-Mike

A message that is not in the archive (sent off-list or not yet received): [email protected]

maintainer
#14 lore raw
Quoted 3 lines · Rik van Riel

As an aside, it also looks like SD_BALANCE_WAKE is set on all domains of a NUMA system by default, so even the non-affine wakeup will end up looking for the lowest load NUMA node to start up on.

I can't find it being set on anything by default.

#15 lore raw
Quoted 6 lines · Peter Zijlstra
Quoted 3 lines · Rik van Riel

As an aside, it also looks like SD_BALANCE_WAKE is set on all domains of a NUMA system by default, so even the non-affine wakeup will end up looking for the lowest load NUMA node to start up on.

I can't find it being set on anything by default.

                .flags                  = 1*SD_LOAD_BALANCE
                                        | 1*SD_BALANCE_NEWIDLE
                                        | 0*SD_BALANCE_EXEC
                                        | 0*SD_BALANCE_FORK
                                        | 0*SD_BALANCE_WAKE
                                        | 0*SD_WAKE_AFFINE
                                        | 0*SD_SHARE_CPUPOWER
                                        | 0*SD_SHARE_PKG_RESOURCES
                                        | 1*SD_SERIALIZE
                                        | 0*SD_PREFER_SIBLING
                                        | 1*SD_NUMA
                                        | sd_local_flags(level)

static inline int sd_local_flags(int level)

{
        if (sched_domains_numa_distance[level] > RECLAIM_DISTANCE)
                return 0;

        return SD_BALANCE_EXEC | SD_BALANCE_FORK | SD_WAKE_AFFINE;
}
Signature · 1 line
All rights reversed
maintainer
#16 lore raw
Quoted 3 lines · Rik van Riel
Quoted 2 lines · Peter Zijlstra
Quoted 1 line · Rik van Riel

As an aside, it also looks like SD_BALANCE_WAKE is set on all domains

                                     ^^^^^^^^^^^^^^^
Quoted 10 lines
Quoted 4 lines
Quoted 2 lines

of a NUMA system by default, so even the non-affine wakeup will end up looking for the lowest load NUMA node to start up on.

I can't find it being set on anything by default.

                .flags                  = 1*SD_LOAD_BALANCE
                                        | 1*SD_BALANCE_NEWIDLE
                                        | 0*SD_BALANCE_EXEC
                                        | 0*SD_BALANCE_FORK
                                        | 0*SD_BALANCE_WAKE
                                            ^

last time I checked 0*x was still 0.

Quoted 9 lines
                                        | 0*SD_WAKE_AFFINE
                                        | 0*SD_SHARE_CPUPOWER
                                        | 0*SD_SHARE_PKG_RESOURCES
                                        | 1*SD_SERIALIZE
                                        | 0*SD_PREFER_SIBLING
                                        | 1*SD_NUMA
                                        | sd_local_flags(level)
Quoted 7 lines

static inline int sd_local_flags(int level)

{
        if (sched_domains_numa_distance[level] > RECLAIM_DISTANCE)
                return 0;

        return SD_BALANCE_EXEC | SD_BALANCE_FORK | SD_WAKE_AFFINE;
}

No BALANCE_WAKE there

#17 lore raw
Quoted 11 lines · Peter Zijlstra
Quoted 3 lines · Rik van Riel
Quoted 2 lines · Peter Zijlstra
Quoted 1 line · Rik van Riel

As an aside, it also looks like SD_BALANCE_WAKE is set on all domains

                                     ^^^^^^^^^^^^^^^
Quoted 5 lines

static inline int sd_local_flags(int level)
{
if (sched_domains_numa_distance[level] > RECLAIM_DISTANCE)
return 0;

Quoted 4 lines
Quoted 2 lines
        return SD_BALANCE_EXEC | SD_BALANCE_FORK | SD_WAKE_AFFINE;
}

No BALANCE_WAKE there

Yeah you're right, I typoed in my earlier email and didn't pick up on it later. Doh.

Signature · 1 line
All rights reversed
#18 lore raw
In reply to Peter Zijlstra
Quoted 7 lines · Peter Zijlstra
Quoted 3 lines · Rik van Riel
Quoted 2 lines · Peter Zijlstra
Quoted 1 line · Rik van Riel

As an aside, it also looks like SD_BALANCE_WAKE is set on all domains

                                     ^^^^^^^^^^^^^^^

No BALANCE_WAKE there

Looks like SD_BALANCE_WAKE is not gotten from the sd flags at all, but passed into select_task_rq by try_to_wake_up, as a hard coded sd_flags argument.

static int
try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags) {
...

        cpu = select_task_rq(p, p->wake_cpu, SD_BALANCE_WAKE, wake_flags);

...

static inline
int select_task_rq(struct task_struct *p, int cpu, int sd_flags, int wake_flags)

{
        cpu = p->sched_class->select_task_rq(p, cpu, sd_flags, wake_flags);

...

static int
select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_flags)
{
...

        if (sd_flag & SD_BALANCE_WAKE) {
                if (cpumask_test_cpu(cpu, tsk_cpus_allowed(p)))
                        want_affine = 1;
                new_cpu = prev_cpu;
        }

Should we do that, if SD_WAKE_BALANCE is not set for any sched domain?

Signature · 1 line
All rights reversed
#19 lore raw

PATCH 1/1 sched: wake up task on prev_cpu if not in SD_WAKE_AFFINE domain with cpu

Quoted 5 lines · On Thu, 08 May 2014 22:20:25 -0400 Rik van Riel <[email protected]> wrote:

Looks like SD_BALANCE_WAKE is not gotten from the sd flags at all, but passed into select_task_rq by try_to_wake_up, as a hard coded sd_flags argument.

Should we do that, if SD_WAKE_BALANCE is not set for any sched domain?

I answered my own question. The sd_flag SD_WAKE_BALANCE simply means "this is a wakeup of a previously existing task, please place it properly".

However, it appears that the current code will fall back to the large loop with select_idlest_group and friends, if prev_cpu and cpu are not part of the same SD_WAKE_AFFINE sched domain. That is a bug...

---8<---

Subject: sched: wake up task on prev_cpu if not in SD_WAKE_AFFINE domain with cpu

If prev_cpu and cpu are not part of the same SD_WAKE_AFFINE domain, the current code will fall back to the select_idlest_group CPU selection mechanism, instead of trying to wake up the task on a CPU near its previous CPU.

Fix that by always calling select_idle_sibling when doing an SD_BALANCE_WAKE wakeup.

---
 kernel/sched/fair.c | 2 ++
 1 file changed, 2 insertions(+)
kernel/sched/fair.c +2 -0
index 7570dd9..5d33fb1b 100644
@@ -4452,7 +4452,9 @@ select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_f
 	if (affine_sd) {
 		if (cpu != prev_cpu && wake_affine(affine_sd, p, sync))
 			prev_cpu = cpu;
+	}
 
+	if (sd_flag & SD_BALANCE_WAKE) {
 		new_cpu = select_idle_sibling(p, prev_cpu);
 		goto unlock;
 	}
#20 lore raw

PATCH 1/1 sched: clean up select_task_rq_fair conditionals and indentation

This cleanup goes on top of the previous patch. We could also skip the whole domain iteration if !want_affine, but that doesn't fit nicely in 80 columns and may have to be done in yet another patch (breaking that bit of the code out into its own function?)

---8<---

Subject: sched: clean up select_task_rq_fair conditionals and indentation

The whole top half of select_task_rq_fair is only run if sd_flag & SD_BALANCE_WAKE. The code should probably reflect that.

Also remove the useless new_cpu = prev_cpu assignment, as the value of new_cpu is not actually used.

---
 kernel/sched/fair.c | 47 ++++++++++++++++++++++++-----------------------
 1 file changed, 24 insertions(+), 23 deletions(-)
kernel/sched/fair.c +24 -23
index 5d33fb1b..844807b 100644
@@ -4424,37 +4424,38 @@ select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_f
 	if (p->nr_cpus_allowed == 1)
 		return prev_cpu;
 
+	rcu_read_lock();
 	if (sd_flag & SD_BALANCE_WAKE) {
 		if (cpumask_test_cpu(cpu, tsk_cpus_allowed(p)))
 			want_affine = 1;
-		new_cpu = prev_cpu;
-	}
 
-	rcu_read_lock();
-	for_each_domain(cpu, tmp) {
-		if (!(tmp->flags & SD_LOAD_BALANCE))
-			continue;
+		for_each_domain(cpu, tmp) {
+			if (!cpumask_test_cpu(cpu, tsk_cpus_allowed(p)))
+				break;
 
-		/*
-		 * If both cpu and prev_cpu are part of this domain,
-		 * cpu is a valid SD_WAKE_AFFINE target.
-		 */
-		if (want_affine && (tmp->flags & SD_WAKE_AFFINE) &&
-		    cpumask_test_cpu(prev_cpu, sched_domain_span(tmp))) {
-			affine_sd = tmp;
-			break;
-		}
+			if (!(tmp->flags & SD_LOAD_BALANCE))
+				continue;
 
-		if (tmp->flags & sd_flag)
-			sd = tmp;
-	}
+			/*
+			 * If both cpu and prev_cpu are part of this domain,
+			 * cpu is a valid SD_WAKE_AFFINE target.
+			 */
+			if (want_affine && (tmp->flags & SD_WAKE_AFFINE) &&
+			    cpumask_test_cpu(prev_cpu,
+					     sched_domain_span(tmp))) {
+				affine_sd = tmp;
+				break;
+			}
 
-	if (affine_sd) {
-		if (cpu != prev_cpu && wake_affine(affine_sd, p, sync))
-			prev_cpu = cpu;
-	}
+			if (tmp->flags & sd_flag)
+				sd = tmp;
+		}
+
+		if (affine_sd) {
+			if (cpu != prev_cpu && wake_affine(affine_sd, p, sync))
+				prev_cpu = cpu;
+		}
 
-	if (sd_flag & SD_BALANCE_WAKE) {
 		new_cpu = select_idle_sibling(p, prev_cpu);
 		goto unlock;
 	}
#21 lore raw

Re: [PATCH] sched: wake up task on prev_cpu if not in SD_WAKE_AFFINE domain with cpu

In reply to Rik van Riel
Quoted 9 lines · Rik van Riel
Quoted 5 lines · On Thu, 08 May 2014 22:20:25 -0400 Rik van Riel <[email protected]> wrote:

Looks like SD_BALANCE_WAKE is not gotten from the sd flags at all, but passed into select_task_rq by try_to_wake_up, as a hard coded sd_flags argument.

Should we do that, if SD_WAKE_BALANCE is not set for any sched domain?

Quoted 7 lines

I answered my own question. The sd_flag SD_WAKE_BALANCE simply means "this is a wakeup of a previously existing task, please place it properly".

However, it appears that the current code will fall back to the large loop with select_idlest_group and friends, if prev_cpu and cpu are not part of the same SD_WAKE_AFFINE sched domain. That is a bug...

ttwu(): cpu = select_task_rq(p, p->wake_cpu, SD_BALANCE_WAKE, wake_flags);

We pass SD_BALANCE_WAKE for a normal wakeup, so sd will only be set if we encounter a domain during traversal where Joe User has told us to do (expensive) wake balancing before we hit a domain shared by waker/wakee.

The user can turn SD_WAKE_AFFINE off beyond socket, and we'll not pull cross node on wakeup.

Or, you could create an override button to say despite SD_WAKE_AFFINE perhaps having been set during domain construction (because of some pseudo-random numbers), don't do that if we have a preferred node, or just make that automatically part of having numa scheduling enabled, and don't bother wasting cycles if preferred && this != preferred.

-Mike

#22 lore raw

Re: [PATCH] sched: wake up task on prev_cpu if not in SD_WAKE_AFFINE domain with cpu

Quoted 24 lines · Mike Galbraith
Quoted 9 lines · Rik van Riel
Quoted 5 lines · On Thu, 08 May 2014 22:20:25 -0400 Rik van Riel <[email protected]> wrote:

Looks like SD_BALANCE_WAKE is not gotten from the sd flags at all, but passed into select_task_rq by try_to_wake_up, as a hard coded sd_flags argument.

Should we do that, if SD_WAKE_BALANCE is not set for any sched domain?

Quoted 7 lines

I answered my own question. The sd_flag SD_WAKE_BALANCE simply means "this is a wakeup of a previously existing task, please place it properly".

However, it appears that the current code will fall back to the large loop with select_idlest_group and friends, if prev_cpu and cpu are not part of the same SD_WAKE_AFFINE sched domain. That is a bug...

ttwu(): cpu = select_task_rq(p, p->wake_cpu, SD_BALANCE_WAKE, wake_flags);

We pass SD_BALANCE_WAKE for a normal wakeup, so sd will only be set if we encounter a domain during traversal where Joe User has told us to do (expensive) wake balancing before we hit a domain shared by waker/wakee.

Quoted 8 lines

The user can turn SD_WAKE_AFFINE off beyond socket, and we'll not pull cross node on wakeup.

Or, you could create an override button to say despite SD_WAKE_AFFINE perhaps having been set during domain construction (because of some pseudo-random numbers), don't do that if we have a preferred node, or just make that automatically part of having numa scheduling enabled, and don't bother wasting cycles if preferred && this != preferred.

That's not the problem.

The problem is that if we do not do an affine wakeup, due to SD_WAKE_AFFINE not being set on a top level domain, we will not try to run p on prev_cpu, but we will fall through into the loop with find_idlest_group, etc...

Signature · 1 line
All rights reversed
#23 lore raw

Re: [PATCH] sched: wake up task on prev_cpu if not in SD_WAKE_AFFINE domain with cpu

Quoted 34 lines · Rik van Riel
Quoted 24 lines · Mike Galbraith
Quoted 9 lines · Rik van Riel
Quoted 5 lines · On Thu, 08 May 2014 22:20:25 -0400 Rik van Riel <[email protected]> wrote:

Looks like SD_BALANCE_WAKE is not gotten from the sd flags at all, but passed into select_task_rq by try_to_wake_up, as a hard coded sd_flags argument.

Should we do that, if SD_WAKE_BALANCE is not set for any sched domain?

Quoted 7 lines

I answered my own question. The sd_flag SD_WAKE_BALANCE simply means "this is a wakeup of a previously existing task, please place it properly".

However, it appears that the current code will fall back to the large loop with select_idlest_group and friends, if prev_cpu and cpu are not part of the same SD_WAKE_AFFINE sched domain. That is a bug...

ttwu(): cpu = select_task_rq(p, p->wake_cpu, SD_BALANCE_WAKE, wake_flags);

We pass SD_BALANCE_WAKE for a normal wakeup, so sd will only be set if we encounter a domain during traversal where Joe User has told us to do (expensive) wake balancing before we hit a domain shared by waker/wakee.

Quoted 8 lines

The user can turn SD_WAKE_AFFINE off beyond socket, and we'll not pull cross node on wakeup.

Or, you could create an override button to say despite SD_WAKE_AFFINE perhaps having been set during domain construction (because of some pseudo-random numbers), don't do that if we have a preferred node, or just make that automatically part of having numa scheduling enabled, and don't bother wasting cycles if preferred && this != preferred.

Quoted 6 lines

That's not the problem.

The problem is that if we do not do an affine wakeup, due to SD_WAKE_AFFINE not being set on a top level domain, we will not try to run p on prev_cpu, but we will fall through into the loop with find_idlest_group, etc...

If no ->flags & SD_BALANCE_WAKE is encountered during traversal, sd remains NULL, we fall through to return prev_cpu.

-Mike

#24 lore raw

Re: [PATCH] sched: wake up task on prev_cpu if not in SD_WAKE_AFFINE domain with cpu

Quoted 37 lines · Mike Galbraith
Quoted 36 lines · Rik van Riel
Quoted 24 lines · Mike Galbraith
Quoted 9 lines · Rik van Riel
Quoted 5 lines · On Thu, 08 May 2014 22:20:25 -0400 Rik van Riel <[email protected]> wrote:

Looks like SD_BALANCE_WAKE is not gotten from the sd flags at all, but passed into select_task_rq by try_to_wake_up, as a hard coded sd_flags argument.

Should we do that, if SD_WAKE_BALANCE is not set for any sched domain?

Quoted 7 lines

I answered my own question. The sd_flag SD_WAKE_BALANCE simply means "this is a wakeup of a previously existing task, please place it properly".

However, it appears that the current code will fall back to the large loop with select_idlest_group and friends, if prev_cpu and cpu are not part of the same SD_WAKE_AFFINE sched domain. That is a bug...

ttwu(): cpu = select_task_rq(p, p->wake_cpu, SD_BALANCE_WAKE, wake_flags);

We pass SD_BALANCE_WAKE for a normal wakeup, so sd will only be set if we encounter a domain during traversal where Joe User has told us to do (expensive) wake balancing before we hit a domain shared by waker/wakee.

Quoted 8 lines

The user can turn SD_WAKE_AFFINE off beyond socket, and we'll not pull cross node on wakeup.

Or, you could create an override button to say despite SD_WAKE_AFFINE perhaps having been set during domain construction (because of some pseudo-random numbers), don't do that if we have a preferred node, or just make that automatically part of having numa scheduling enabled, and don't bother wasting cycles if preferred && this != preferred.

That's not the problem.

Quoted 7 lines
Quoted 4 lines

The problem is that if we do not do an affine wakeup, due to SD_WAKE_AFFINE not being set on a top level domain, we will not try to run p on prev_cpu, but we will fall through into the loop with find_idlest_group, etc...

If no ->flags & SD_BALANCE_WAKE is encountered during traversal, sd remains NULL, we fall through to return prev_cpu.

We do fall through, but into this loop:

        while (sd) {
                struct sched_group *group;
                int weight;

                if (!(sd->flags & sd_flag)) {
                        sd = sd->child;
                        continue;
                }

                group = find_idlest_group(sd, p, cpu, sd_flag);
                if (!group) {
                        sd = sd->child;
                        continue;
                }

                new_cpu = find_idlest_cpu(group, p, cpu);
                if (new_cpu == -1 || new_cpu == cpu) {
                        /* Now try balancing at a lower domain level of 
cpu */
                        sd = sd->child;
                        continue;
                }

                /* Now try balancing at a lower domain level of new_cpu */
                cpu = new_cpu;
                weight = sd->span_weight;
                sd = NULL;
                for_each_domain(cpu, tmp) {
                        if (weight <= tmp->span_weight)
                                break;
                        if (tmp->flags & sd_flag)
                                sd = tmp;
                }
                /* while loop will break here if sd == NULL */
        }
#25 lore raw

Re: [PATCH] sched: wake up task on prev_cpu if not in SD_WAKE_AFFINE domain with cpu

Quoted 4 lines · Rik van Riel
Quoted 2 lines · Mike Galbraith

If no ->flags & SD_BALANCE_WAKE is encountered during traversal, sd remains NULL, we fall through to return prev_cpu.

    ^^^^^^^^^^^^ 
Quoted 3 lines

We do fall through, but into this loop:

         while (sd) {
#26 lore raw

Re: [PATCH] sched: wake up task on prev_cpu if not in SD_WAKE_AFFINE domain with cpu

Quoted 10 lines · Mike Galbraith
Quoted 4 lines · Rik van Riel
Quoted 2 lines · Mike Galbraith

If no ->flags & SD_BALANCE_WAKE is encountered during traversal, sd remains NULL, we fall through to return prev_cpu.

     ^^^^^^^^^^^^
Quoted 3 lines

We do fall through, but into this loop:

          while (sd) {

You are right. That code is a little hard to follow...

That leaves the big question: do we want to fall back to prev_cpu if it is not idle, and it has an idle sibling, or would it be better to find an idle sibling of prev_cpu when we wake up a task?

#27 lore raw

Re: [PATCH] sched: wake up task on prev_cpu if not in SD_WAKE_AFFINE domain with cpu

Quoted 4 lines · Rik van Riel

That leaves the big question: do we want to fall back to prev_cpu if it is not idle, and it has an idle sibling, or would it be better to find an idle sibling of prev_cpu when we wake up a task?

Yes. If there was A correct answer, this stuff would be a lot easier.

-Mike

#28 lore raw

Re: [PATCH] sched: wake up task on prev_cpu if not in SD_WAKE_AFFINE domain with cpu

Quoted 8 lines · Mike Galbraith
Quoted 4 lines · Rik van Riel

That leaves the big question: do we want to fall back to prev_cpu if it is not idle, and it has an idle sibling, or would it be better to find an idle sibling of prev_cpu when we wake up a task?

Yes. If there was A correct answer, this stuff would be a lot easier.

OK, after doing some other NUMA stuff, and then looking at the scheduler again with a fresh mind, I have drawn some more conclusions about what the scheduler does, and how it breaks NUMA locality :)

1) If the node_distance between nodes on a NUMA system is <= RECLAIM_DISTANCE, we will call select_idle_sibling for a wakeup of a previously existing task (SD_BALANCE_WAKE)

2) If the node distance exceeds RECLAIM_DISTANCE, we will wake up a task on prev_cpu, even if it is not currently idle

This behaviour only happens on certain large NUMA systems, and is different from the behaviour on small systems. I suspect we will want to call select_idle_sibling with prev_cpu in case target and prev_cpu are not in the same SD_WAKE_AFFINE domain.

3) If wake_wide is false, we call select_idle_sibling with the CPU number of the code that is waking up the task

4) If wake_wide is true, we call select_idle_sibling with the CPU number the task was previously running on (prev_cpu)

In effect, the "wake task on waking task's CPU" behaviour is the default, regardless of how frequently a task wakes up its wakee, and regardless of impact on NUMA locality.

This may need to be changed.

5) select_idle_sibling will place the task on (3) or (4) only if the CPU is actually idle. If task A communicates with task B through a pipe or a socket, and does a sync wakeup, task B will never be placed on task A's CPU (not idle yet), and it will only be placed on its own previous CPU if it is currently idle.

6) If neither CPU is idle, select_idle_sibling will walk all the CPUs in the SD_SHARE_PKG_RESOURCES SD of the target. This looks correct to me, though it could result in more work by the load balancing code later on, since it does not take load into account at all. It is unclear if this needs any changes.

Am I overlooking anything?

What benchmarks should I run to test any changes I make?

Are there particular system types people want me to run tests with?

Signature · 1 line
All rights reversed
#29 lore raw

Re: [PATCH] sched: wake up task on prev_cpu if not in SD_WAKE_AFFINE domain with cpu

Quoted 12 lines · Rik van Riel

OK, after doing some other NUMA stuff, and then looking at the scheduler again with a fresh mind, I have drawn some more conclusions about what the scheduler does, and how it breaks NUMA locality :)

1) If the node_distance between nodes on a NUMA system is <= RECLAIM_DISTANCE, we will call select_idle_sibling for a wakeup of a previously existing task (SD_BALANCE_WAKE)

2) If the node distance exceeds RECLAIM_DISTANCE, we will wake up a task on prev_cpu, even if it is not currently idle

Quoted 5 lines

This behaviour only happens on certain large NUMA systems, and is different from the behaviour on small systems. I suspect we will want to call select_idle_sibling with prev_cpu in case target and prev_cpu are not in the same SD_WAKE_AFFINE domain.

Sometimes. It's the same can of worms remote as it is local.. latency gain may or may not outweigh cache miss pain.

Quoted 11 lines

3) If wake_wide is false, we call select_idle_sibling with the CPU number of the code that is waking up the task

4) If wake_wide is true, we call select_idle_sibling with the CPU number the task was previously running on (prev_cpu)

In effect, the "wake task on waking task's CPU" behaviour is the default, regardless of how frequently a task wakes up its wakee, and regardless of impact on NUMA locality.

This may need to be changed.

That behavior also improves the odds of communicating tasks sharing a cache though.

Quoted 1 line

Am I overlooking anything?

No, I think you're seeing where the worms live.

Quoted 1 line

What benchmarks should I run to test any changes I make?

Mixed bag, it'll affects all, bursty, static, ramp up/down.

-Mike

#30 lore raw

PATCH 1/1 sched: call select_idle_sibling when not affine_sd

Quoted 10 lines · On Wed, 14 May 2014 06:08:09 +0200 Mike Galbraith <[email protected]>…
Quoted 8 lines · Rik van Riel

1) If the node_distance between nodes on a NUMA system is <= RECLAIM_DISTANCE, we will call select_idle_sibling for a wakeup of a previously existing task (SD_BALANCE_WAKE)

2) If the node distance exceeds RECLAIM_DISTANCE, we will wake up a task on prev_cpu, even if it is not currently idle

Quoted 8 lines
Quoted 5 lines

This behaviour only happens on certain large NUMA systems, and is different from the behaviour on small systems. I suspect we will want to call select_idle_sibling with prev_cpu in case target and prev_cpu are not in the same SD_WAKE_AFFINE domain.

Sometimes. It's the same can of worms remote as it is local.. latency gain may or may not outweigh cache miss pain.

Ahh, but it is a DIFFERENT can of worms. If the distance between cpu and prev_cpu exceeds RECLAIM_DISTANCE, we will not look for an idle sibling in the same LLC domain as prev_cpu.

If the distance is smaller, and we decide not to do an affine wakeup, then we do look for an idle sibling of prev_cpu.

This patch makes sure that both types of systems have the same can of worms :)

---8<---

Subject: sched: call select_idle_sibling when not affine_sd

On smaller systems, the top level sched domain will be an affine domain, and select_idle_sibling is invoked for every SD_WAKE_AFFINE wakeup. This seems to be working well.

On larger systems, with the node distance between far away NUMA nodes being > RECLAIM_DISTANCE, select_idle_sibling is only called if the waker and the wakee are on nodes less than RECLAIM_DISTANCE apart.

This patch leaves in place the policy of not pulling the task across nodes on such systems, while fixing the issue that select_idle_sibling is not called at all in certain circumstances.

The code will look for an idle CPU in the same CPU package as the CPU where the task ran previously.

---
 kernel/sched/fair.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)
kernel/sched/fair.c +3 -3
index 39b63d0..1e58159 100644
@@ -4423,10 +4423,10 @@ select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_f
 			sd = tmp;
 	}
 
-	if (affine_sd) {
-		if (cpu != prev_cpu && wake_affine(affine_sd, p, sync))
-			prev_cpu = cpu;
+	if (affine_sd && cpu != prev_cpu && wake_affine(affine_sd, p, sync))
+		prev_cpu = cpu;
 
+	if (sd_flag & SD_WAKE_AFFINE) {
 		new_cpu = select_idle_sibling(p, prev_cpu);
 		goto unlock;
 	}
maintainer
#31 lore raw

Re: [PATCH] sched: call select_idle_sibling when not affine_sd

Quoted 27 lines · Rik van Riel

Subject: sched: call select_idle_sibling when not affine_sd

On smaller systems, the top level sched domain will be an affine domain, and select_idle_sibling is invoked for every SD_WAKE_AFFINE wakeup. This seems to be working well.

On larger systems, with the node distance between far away NUMA nodes being > RECLAIM_DISTANCE, select_idle_sibling is only called if the waker and the wakee are on nodes less than RECLAIM_DISTANCE apart.

This patch leaves in place the policy of not pulling the task across nodes on such systems, while fixing the issue that select_idle_sibling is not called at all in certain circumstances.

The code will look for an idle CPU in the same CPU package as the CPU where the task ran previously.

---
 kernel/sched/fair.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)
kernel/sched/fair.c +0 -0
index 39b63d0..1e58159 100644

kernel/sched/fair.c select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_f · line 4429

Quoted 10 lines
kernel/sched/fair.c +3 -3
@@ -4423,10 +4423,10 @@ select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_f
 			sd = tmp;
 	}
 
-	if (affine_sd) {
-		if (cpu != prev_cpu && wake_affine(affine_sd, p, sync))
-			prev_cpu = cpu;
+	if (affine_sd && cpu != prev_cpu && wake_affine(affine_sd, p, sync))
+		prev_cpu = cpu;
 
+	if (sd_flag & SD_WAKE_AFFINE) {

I think you meant SD_BALANCE_WAKE?

Quoted 3 lines
kernel/sched/fair.c +0 -0
 		new_cpu = select_idle_sibling(p, prev_cpu);
 		goto unlock;
 	}
#32 lore raw

[tip:sched/core] sched: call select_idle_sibling when not affine_sd

In reply to Rik van Riel
sched: call select_idle_sibling when not affine_sd
Commit-ID:  b45cf72cf7e1dd3b4a95947f85659cfdc01dbdad
Gitweb:     http://git.kernel.org/tip/b45cf72cf7e1dd3b4a95947f85659cfdc01dbdad
Author:     Rik van Riel <[email protected]>
AuthorDate: Wed, 14 May 2014 11:40:37 -0400
Committer:  Thomas Gleixner <[email protected]>
CommitDate: Mon, 19 May 2014 22:02:40 +0900

sched: call select_idle_sibling when not affine_sd

On smaller systems, the top level sched domain will be an affine domain, and select_idle_sibling is invoked for every SD_WAKE_AFFINE wakeup. This seems to be working well.

On larger systems, with the node distance between far away NUMA nodes being > RECLAIM_DISTANCE, select_idle_sibling is only called if the waker and the wakee are on nodes less than RECLAIM_DISTANCE apart.

This patch leaves in place the policy of not pulling the task across nodes on such systems, while fixing the issue that select_idle_sibling is not called at all in certain circumstances.

The code will look for an idle CPU in the same CPU package as the CPU where the task ran previously.

---
 kernel/sched/fair.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)
kernel/sched/fair.c +3 -3
index dd3fa14..429164d 100644
@@ -4473,10 +4473,10 @@ select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_f
 			sd = tmp;
 	}
 
-	if (affine_sd) {
-		if (cpu != prev_cpu && wake_affine(affine_sd, p, sync))
-			prev_cpu = cpu;
+	if (affine_sd && cpu != prev_cpu && wake_affine(affine_sd, p, sync))
+		prev_cpu = cpu;
 
+	if (sd_flag & SD_BALANCE_WAKE) {
 		new_cpu = select_idle_sibling(p, prev_cpu);
 		goto unlock;
 	}
#33 lore raw

[tip:sched/core] sched: Call select_idle_sibling() when not affine_sd

In reply to Rik van Riel
sched: Call select_idle_sibling() when not affine_sd
Commit-ID:  8bf21433f38b020c3d8a3805d1d7fb73d7b40c01
Gitweb:     http://git.kernel.org/tip/8bf21433f38b020c3d8a3805d1d7fb73d7b40c01
Author:     Rik van Riel <[email protected]>
AuthorDate: Wed, 14 May 2014 11:40:37 -0400
Committer:  Ingo Molnar <[email protected]>
CommitDate: Thu, 22 May 2014 11:16:28 +0200

sched: Call select_idle_sibling() when not affine_sd

On smaller systems, the top level sched domain will be an affine domain, and select_idle_sibling is invoked for every SD_WAKE_AFFINE wakeup. This seems to be working well.

On larger systems, with the node distance between far away NUMA nodes being > RECLAIM_DISTANCE, select_idle_sibling is only called if the waker and the wakee are on nodes less than RECLAIM_DISTANCE apart.

This patch leaves in place the policy of not pulling the task across nodes on such systems, while fixing the issue that select_idle_sibling is not called at all in certain circumstances.

The code will look for an idle CPU in the same CPU package as the CPU where the task ran previously.

---
 kernel/sched/fair.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)
kernel/sched/fair.c +3 -3
index dd3fa14..429164d 100644
@@ -4473,10 +4473,10 @@ select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_f
 			sd = tmp;
 	}
 
-	if (affine_sd) {
-		if (cpu != prev_cpu && wake_affine(affine_sd, p, sync))
-			prev_cpu = cpu;
+	if (affine_sd && cpu != prev_cpu && wake_affine(affine_sd, p, sync))
+		prev_cpu = cpu;
 
+	if (sd_flag & SD_BALANCE_WAKE) {
 		new_cpu = select_idle_sibling(p, prev_cpu);
 		goto unlock;
 	}
#34 lore raw
In reply to Rik van Riel

Hi Rik, Mike

Quoted 8 lines · Rik van Riel
Quoted 7 lines · Mike Galbraith
Quoted 4 lines · Rik van Riel

Whether or not this is the right thing to do remains to be seen, but it does allow us to verify whether or not the wake_affine strategy of always doing affine wakeups and only disabling them in a specific circumstance is sound, or needs rethinking...

Quoted 8 lines
Quoted 4 lines

Yes, it needs rethinking.

I know why you want to try this, yes, select_idle_sibling() is very much a two faced little bitch.

My biggest problem with select_idle_sibling and wake_affine in general is that it will override NUMA placement, even when processes only wake each other up infrequently...

As far as my understanding goes, the logic in select_task_rq_fair() does wake_affine() or calls select_idle_sibling() only at those levels of sched domains where the flag SD_WAKE_AFFINE is set. This flag is not set at the numa domain and hence they will not be balancing across numa nodes. So I don't understand how *these functions* are affecting NUMA placements.

The wake_affine() and select_idle_sibling() will shuttle tasks within a NUMA node as far as I can see.i.e. if the cpu that the task previously ran on and the waker cpu belong to the same node. Else they are not called.

If the prev_cpu and the waker cpu are on different NUMA nodes then naturally the tasks will get shuttled across NUMA nodes but the culprits are the find_idlest* functions.
They do a top-down search for the idlest group and cpu, starting
at the NUMA domain *attached to the waker and not the prev_cpu*. This means that the task will end up on a different NUMA node. Looks to me that the problem lies here and not in the wake_affine() and select_idle_siblings().

Regards
Preeti U Murthy

Quoted 8 lines

--
All rights reversed
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

#35 lore raw
Quoted 20 lines · Preeti Murthy

Hi Rik, Mike

Quoted 8 lines · Rik van Riel
Quoted 7 lines · Mike Galbraith
Quoted 4 lines · Rik van Riel

Whether or not this is the right thing to do remains to be seen, but it does allow us to verify whether or not the wake_affine strategy of always doing affine wakeups and only disabling them in a specific circumstance is sound, or needs rethinking...

Quoted 8 lines
Quoted 4 lines

Yes, it needs rethinking.

I know why you want to try this, yes, select_idle_sibling() is very much a two faced little bitch.

My biggest problem with select_idle_sibling and wake_affine in general is that it will override NUMA placement, even when processes only wake each other up infrequently...

Quoted 6 lines

As far as my understanding goes, the logic in select_task_rq_fair() does wake_affine() or calls select_idle_sibling() only at those levels of sched domains where the flag SD_WAKE_AFFINE is set. This flag is not set at the numa domain and hence they will not be balancing across numa nodes. So I don't understand how *these functions* are affecting NUMA placements.

Depends on how far away node yonder is I suppose.

static inline int sd_local_flags(int level)

{
        if (sched_domains_numa_distance[level] > RECLAIM_DISTANCE)
                return 0;

        return SD_BALANCE_EXEC | SD_BALANCE_FORK | SD_WAKE_AFFINE;
}
#36 lore raw
Quoted 30 lines · Mike Galbraith
Quoted 20 lines · Preeti Murthy

Hi Rik, Mike

Quoted 8 lines · Rik van Riel
Quoted 7 lines · Mike Galbraith
Quoted 4 lines · Rik van Riel

Whether or not this is the right thing to do remains to be seen, but it does allow us to verify whether or not the wake_affine strategy of always doing affine wakeups and only disabling them in a specific circumstance is sound, or needs rethinking...

Quoted 8 lines
Quoted 4 lines

Yes, it needs rethinking.

I know why you want to try this, yes, select_idle_sibling() is very much a two faced little bitch.

My biggest problem with select_idle_sibling and wake_affine in general is that it will override NUMA placement, even when processes only wake each other up infrequently...

Quoted 6 lines

As far as my understanding goes, the logic in select_task_rq_fair() does wake_affine() or calls select_idle_sibling() only at those levels of sched domains where the flag SD_WAKE_AFFINE is set. This flag is not set at the numa domain and hence they will not be balancing across numa nodes. So I don't understand how *these functions* are affecting NUMA placements.

Depends on how far away node yonder is I suppose.

Quoted 9 lines

static inline int sd_local_flags(int level)

{
        if (sched_domains_numa_distance[level] > RECLAIM_DISTANCE)
                return 0;

        return SD_BALANCE_EXEC | SD_BALANCE_FORK | SD_WAKE_AFFINE;
}

Hmm thanks Mike, I totally missed this!

Regards
Preeti U Murthy

#37 lore raw
In reply to Preeti Murthy
Quoted 20 lines · Preeti Murthy

Hi Rik, Mike

Quoted 8 lines · Rik van Riel
Quoted 7 lines · Mike Galbraith
Quoted 4 lines · Rik van Riel

Whether or not this is the right thing to do remains to be seen, but it does allow us to verify whether or not the wake_affine strategy of always doing affine wakeups and only disabling them in a specific circumstance is sound, or needs rethinking...

Quoted 8 lines
Quoted 4 lines

Yes, it needs rethinking.

I know why you want to try this, yes, select_idle_sibling() is very much a two faced little bitch.

My biggest problem with select_idle_sibling and wake_affine in general is that it will override NUMA placement, even when processes only wake each other up infrequently...

Quoted 6 lines

As far as my understanding goes, the logic in select_task_rq_fair() does wake_affine() or calls select_idle_sibling() only at those levels of sched domains where the flag SD_WAKE_AFFINE is set. This flag is not set at the numa domain and hence they will not be balancing across numa nodes. So I don't understand how *these functions* are affecting NUMA placements.

Even on 8-node DL980 systems, the NUMA distance in the SLIT table is less than RECLAIM_DISTANCE, and we will do wake_affine across the entire system.

Quoted 4 lines

The wake_affine() and select_idle_sibling() will shuttle tasks within a NUMA node as far as I can see.i.e. if the cpu that the task previously ran on and the waker cpu belong to the same node. Else they are not called.

That is what I first hoped, too. I was wrong.

Quoted 8 lines

If the prev_cpu and the waker cpu are on different NUMA nodes then naturally the tasks will get shuttled across NUMA nodes but the culprits are the find_idlest* functions.
They do a top-down search for the idlest group and cpu, starting
at the NUMA domain *attached to the waker and not the prev_cpu*. This means that the task will end up on a different NUMA node. Looks to me that the problem lies here and not in the wake_affine() and select_idle_siblings().

I have a patch for find_idlest_group that takes the NUMA distance between each group and the task's preferred node into account.

However, as long as the wake_affine stuff still gets to override it, that does not make much difference :)

Signature · 1 line
All rights reversed
#38 lore raw
Quoted 48 lines · Rik van Riel
Quoted 20 lines · Preeti Murthy

Hi Rik, Mike

Quoted 8 lines · Rik van Riel
Quoted 7 lines · Mike Galbraith
Quoted 4 lines · Rik van Riel

Whether or not this is the right thing to do remains to be seen, but it does allow us to verify whether or not the wake_affine strategy of always doing affine wakeups and only disabling them in a specific circumstance is sound, or needs rethinking...

Quoted 8 lines
Quoted 4 lines

Yes, it needs rethinking.

I know why you want to try this, yes, select_idle_sibling() is very much a two faced little bitch.

My biggest problem with select_idle_sibling and wake_affine in general is that it will override NUMA placement, even when processes only wake each other up infrequently...

Quoted 6 lines

As far as my understanding goes, the logic in select_task_rq_fair() does wake_affine() or calls select_idle_sibling() only at those levels of sched domains where the flag SD_WAKE_AFFINE is set. This flag is not set at the numa domain and hence they will not be balancing across numa nodes. So I don't understand how *these functions* are affecting NUMA placements.

Even on 8-node DL980 systems, the NUMA distance in the SLIT table is less than RECLAIM_DISTANCE, and we will do wake_affine across the entire system.

Quoted 4 lines

The wake_affine() and select_idle_sibling() will shuttle tasks within a NUMA node as far as I can see.i.e. if the cpu that the task previously ran on and the waker cpu belong to the same node. Else they are not called.

That is what I first hoped, too. I was wrong.

Quoted 8 lines

If the prev_cpu and the waker cpu are on different NUMA nodes then naturally the tasks will get shuttled across NUMA nodes but the culprits are the find_idlest* functions.
They do a top-down search for the idlest group and cpu, starting
at the NUMA domain *attached to the waker and not the prev_cpu*. This means that the task will end up on a different NUMA node. Looks to me that the problem lies here and not in the wake_affine() and select_idle_siblings().

Quoted 7 lines

I have a patch for find_idlest_group that takes the NUMA distance between each group and the task's preferred node into account.

However, as long as the wake_affine stuff still gets to override it, that does not make much difference :)

Yeah now I see it. But I still feel wake_affine() and select_idle_sibling() are not at fault primarily because when they were introduced, I don't think it was foreseen that the cpu topology would grow to the extent it is now.

select_idle_sibling() for instance scans the cpus within the purview of the last level cache of a cpu and this was a small set. Hence there was no overhead. Now with many cpus sharing the L3 cache, we see an overhead. wake_affine() probably did not expect the NUMA nodes to come under its governance as well and hence it sees no harm in waking up tasks close to the waker because it still believes that it will be within a node.

What has changed is the code around these two functions I feel. Take this problem for instance. We ourselves are saying in sd_local_flags() that this specific domain is fit for wake affine balance. So naturally the logic in wake_affine and select_idle_sibling() will follow.
My point is the peripheral code is seeing the negative affect of these
two functions because they pushed themselves under its ambit.

Don't you think we should go conservative on the value of RECLAIM_DISTANCE in arch specific code at-least? On powerpc we set it to
10. Besides, the git log does not tell us the basis on which this value was set to a default of 30. Maybe this needs re-thought?

Regards
Preeti U Murthy

#39 lore raw
Quoted 77 lines · Preeti U Murthy
Quoted 48 lines · Rik van Riel
Quoted 20 lines · Preeti Murthy

Hi Rik, Mike

Quoted 8 lines · Rik van Riel
Quoted 7 lines · Mike Galbraith
Quoted 4 lines · Rik van Riel

Whether or not this is the right thing to do remains to be seen, but it does allow us to verify whether or not the wake_affine strategy of always doing affine wakeups and only disabling them in a specific circumstance is sound, or needs rethinking...

Quoted 8 lines
Quoted 4 lines

Yes, it needs rethinking.

I know why you want to try this, yes, select_idle_sibling() is very much a two faced little bitch.

My biggest problem with select_idle_sibling and wake_affine in general is that it will override NUMA placement, even when processes only wake each other up infrequently...

Quoted 6 lines

As far as my understanding goes, the logic in select_task_rq_fair() does wake_affine() or calls select_idle_sibling() only at those levels of sched domains where the flag SD_WAKE_AFFINE is set. This flag is not set at the numa domain and hence they will not be balancing across numa nodes. So I don't understand how *these functions* are affecting NUMA placements.

Even on 8-node DL980 systems, the NUMA distance in the SLIT table is less than RECLAIM_DISTANCE, and we will do wake_affine across the entire system.

Quoted 4 lines

The wake_affine() and select_idle_sibling() will shuttle tasks within a NUMA node as far as I can see.i.e. if the cpu that the task previously ran on and the waker cpu belong to the same node. Else they are not called.

That is what I first hoped, too. I was wrong.

Quoted 8 lines

If the prev_cpu and the waker cpu are on different NUMA nodes then naturally the tasks will get shuttled across NUMA nodes but the culprits are the find_idlest* functions.
They do a top-down search for the idlest group and cpu, starting
at the NUMA domain *attached to the waker and not the prev_cpu*. This means that the task will end up on a different NUMA node. Looks to me that the problem lies here and not in the wake_affine() and select_idle_siblings().

Quoted 7 lines

I have a patch for find_idlest_group that takes the NUMA distance between each group and the task's preferred node into account.

However, as long as the wake_affine stuff still gets to override it, that does not make much difference :)

Yeah now I see it. But I still feel wake_affine() and select_idle_sibling() are not at fault primarily because when they were introduced, I don't think it was foreseen that the cpu topology would grow to the extent it is now.

select_idle_sibling() for instance scans the cpus within the purview of the last level cache of a cpu and this was a small set. Hence there was no overhead. Now with many cpus sharing the L3 cache, we see an overhead. wake_affine() probably did not expect the NUMA nodes to come under its governance as well and hence it sees no harm in waking up tasks close to the waker because it still believes that it will be within a node.

What has changed is the code around these two functions I feel. Take this problem for instance. We ourselves are saying in sd_local_flags() that this specific domain is fit for wake affine balance. So naturally the logic in wake_affine and select_idle_sibling() will follow.
My point is the peripheral code is seeing the negative affect of these
two functions because they pushed themselves under its ambit.

Quoted 4 lines

Don't you think we should go conservative on the value of RECLAIM_DISTANCE in arch specific code at-least? On powerpc we set it to
10. Besides, the git log does not tell us the basis on which this value was set to a default of 30. Maybe this needs re-thought?

Sorry I overlooked this. Commit 32e45ff43eaf5c17f5a increased the value to 30 and the reason is also clearly mentioned. It is mentioned that the value was arbitrarily chosen. I don't know if this will help this discussion but I thought I would point it out.

Thanks

Regards
Preeti U Murthy

Quoted 4 lines

Regards
Preeti U Murthy

#40 lore raw
In reply to Preeti U Murthy
Quoted 4 lines · Preeti U Murthy

Yeah now I see it. But I still feel wake_affine() and select_idle_sibling() are not at fault primarily because when they were introduced, I don't think it was foreseen that the cpu topology would grow to the extent it is now.

It's not about "fault", it is about the fact that on current large NUMA systems they are broken, and could stand some improvement :)

Quoted 7 lines

select_idle_sibling() for instance scans the cpus within the purview of the last level cache of a cpu and this was a small set. Hence there was no overhead. Now with many cpus sharing the L3 cache, we see an overhead. wake_affine() probably did not expect the NUMA nodes to come under its governance as well and hence it sees no harm in waking up tasks close to the waker because it still believes that it will be within a node.

If two tasks truly are related to each other, I think we will want to have the wake_affine logic pull them towards each other, all the way across a giant NUMA system if needs be.

The problem is that the current wake_affine logic starts in the ON position, and only switches off in a few very specific scenarios.

I suspect we would be better off with the reverse, starting with wake_affine in the off position, and switching it on when we detect it makes sense to do so.

Signature · 1 line
All rights reversed
maintainer
#41 lore raw
In reply to Preeti U Murthy
Quoted 4 lines · Preeti U Murthy

Don't you think we should go conservative on the value of RECLAIM_DISTANCE in arch specific code at-least? On powerpc we set it to
10. Besides, the git log does not tell us the basis on which this value was set to a default of 30. Maybe this needs re-thought?

See my last email on how all this is entirely pointless :-(

maintainer
#42 lore raw
In reply to Rik van Riel
Quoted 3 lines · Rik van Riel

Even on 8-node DL980 systems, the NUMA distance in the SLIT table is less than RECLAIM_DISTANCE, and we will do wake_affine across the entire system.

Yeah, so the problem is that (AFAIK) ACPI doesn't actually specify a metric for the SLIT distance. This (in as far as BIOS people would care to stick to specs anyhow) has lead to the 'fun' situation where BIOS engineers tweak SLIT table values to make OSes behave as they thing it should.

So if the BIOS engineer finds that this system should have < RECLAIM_DISTANCE it will simply make the table such that the max SLIT value is below that.

And yes, I've seen this :-(

#43 lore raw
Quoted 11 lines · Peter Zijlstra
Quoted 3 lines · Rik van Riel

Even on 8-node DL980 systems, the NUMA distance in the SLIT table is less than RECLAIM_DISTANCE, and we will do wake_affine across the entire system.

Yeah, so the problem is that (AFAIK) ACPI doesn't actually specify a metric for the SLIT distance. This (in as far as BIOS people would care to stick to specs anyhow) has lead to the 'fun' situation where BIOS engineers tweak SLIT table values to make OSes behave as they thing it should.

Quoted 5 lines

So if the BIOS engineer finds that this system should have < RECLAIM_DISTANCE it will simply make the table such that the max SLIT value is below that.

And yes, I've seen this :-(

It appears to be the case on the vast majority of the NUMA systems that are actually in use.

To me, this suggests that we should probably deal with it.

Signature · 1 line
All rights reversed
maintainer
#44 lore raw
Quoted 16 lines · Rik van Riel
Quoted 15 lines · Peter Zijlstra
Quoted 3 lines · Rik van Riel

Even on 8-node DL980 systems, the NUMA distance in the SLIT table is less than RECLAIM_DISTANCE, and we will do wake_affine across the entire system.

Yeah, so the problem is that (AFAIK) ACPI doesn't actually specify a metric for the SLIT distance. This (in as far as BIOS people would care to stick to specs anyhow) has lead to the 'fun' situation where BIOS engineers tweak SLIT table values to make OSes behave as they thing it should.

So if the BIOS engineer finds that this system should have < RECLAIM_DISTANCE it will simply make the table such that the max SLIT value is below that.

Quoted 6 lines
Quoted 1 line

And yes, I've seen this :-(

It appears to be the case on the vast majority of the NUMA systems that are actually in use.

To me, this suggests that we should probably deal with it.

What we could do is redefine this distance in hops, that'll force them to lie more blatantly and actually miss represent the topology.

#45 lore raw
Quoted 19 lines · Peter Zijlstra
Quoted 18 lines · Rik van Riel
Quoted 16 lines · Peter Zijlstra
Quoted 3 lines · Rik van Riel

Even on 8-node DL980 systems, the NUMA distance in the SLIT table is less than RECLAIM_DISTANCE, and we will do wake_affine across the entire system.

Yeah, so the problem is that (AFAIK) ACPI doesn't actually specify a metric for the SLIT distance. This (in as far as BIOS people would care to stick to specs anyhow) has lead to the 'fun' situation where BIOS engineers tweak SLIT table values to make OSes behave as they thing it should.

So if the BIOS engineer finds that this system should have < RECLAIM_DISTANCE it will simply make the table such that the max SLIT value is below that.

And yes, I've seen this :-(

Quoted 7 lines
Quoted 4 lines

It appears to be the case on the vast majority of the NUMA systems that are actually in use.

To me, this suggests that we should probably deal with it.

What we could do is redefine this distance in hops, that'll force them to lie more blatantly and actually miss represent the topology.

and we should make sure we reduce any graph they represent, so that they can lie only through very heavy misrepresentation of the topology (i.e. not just weight tweaks) which will bite them in other areas (like the mm).

Thanks,

Ingo

maintainer
#46 lore raw
In reply to Preeti Murthy
Quoted 6 lines · Preeti Murthy

As far as my understanding goes, the logic in select_task_rq_fair() does wake_affine() or calls select_idle_sibling() only at those levels of sched domains where the flag SD_WAKE_AFFINE is set. This flag is not set at the numa domain and hence they will not be balancing across numa nodes. So I don't understand how *these functions* are affecting NUMA placements.

It _is_ set at NUMA domains, just not on those > RECLAIM_DISTANCE. That means you typically need a non-fully connected system and then the top numa tier will not get wake affine.