fix scheduler regression from "sched/fair: Rework load_balance()"
PATCH 1/1 fix scheduler regression from "sched/fair: Rework load_balance()"
Hi everyone,
We’re validating a new kernel in the fleet, and compared with v5.2, performance is ~2-3% lower for some of our workloads. After some digging, Johannes found that our involuntary context switch rate was ~2x higher, and we were leaving a CPU idle a higher percentage of the time, even though the workload was trying to saturate the system.
We were able to reproduce the problem with schbench, and Johannes bisected down to:
commit 0b0695f2b34a4afa3f6e9aa1ff0e5336d8dad912
Author: Vincent Guittot <[email protected]> Date: Fri Oct 18 15:26:31 2019 +0200
sched/fair: Rework load_balance()
Our working theory is the load balancing changes are leaving processes behind busy CPUs instead of moving them onto idle ones. I made a few schbench modifications to make this easier to demonstrate:
https://git.kernel.org/pub/scm/linux/kernel/git/mason/schbench.git/
My VM has 40 cpus (20 cores, 2 threads per core), and my schbench command line is:
schbench -t 20 -r 0 -c 1000000 -s 1000 -i 30 -z 120
This has two message threads, and 20 workers per message thread. Once woken up, the workers think for a full second, which means you’ll have some long latencies if you’re stuck behind one of these workers in the runqueue. The message thread does a little bit of work and then sleeps, so we end up with 40 threads hammering full blast on the CPU and 2 threads popping in and out of idle.
schbench times the delay from when a message thread wakes a worker to when the worker runs. On a good kernel, the output looks like this:
Latency percentiles (usec) runtime 1290 (s) (3280 total samples)
50.0th: 155 (1653 samples)
75.0th: 189 (808 samples)
90.0th: 216 (501 samples)
95.0th: 227 (163 samples)
*99.0th: 256 (123 samples)
99.5th: 1510 (16 samples)
99.9th: 3132 (13 samples)
min=21, max=3286With 0b0695f2b34a, we get this:
Latency percentiles (usec) runtime 1440 (s) (4480 total samples)
50.0th: 147 (2261 samples)
75.0th: 182 (1116 samples)
90.0th: 205 (671 samples)
95.0th: 224 (215 samples)
*99.0th: 12240 (173 samples) <—— much higher p99 and up
99.5th: 12752 (22 samples)
99.9th: 13104 (18 samples)
min=21, max=13172Since the idea is to fully load the machine with schbench, use schbench -t <your_num_cpus/2>, and make sure the box doesn’t have other stuff running in the background. I used a VM because it ended up giving more consistent results on our kernel test machines, which have some periodic noise running in the background.
We’ve tried a few different approaches, but don’t quite have a solid fix yet. I thought I’d kick off the discussion with my most useful hunks so far:
kernel/sched/fair.c +0 -0
-chris
Vincent Guittot
maintainerHi Chris
Quoted 4 lines · Chris Mason
Hi everyone,
We’re validating a new kernel in the fleet, and compared with v5.2,
Which version are you using ?
several improvements have been added since v5.5 and the rework of load_balance
Quoted 14 lines
performance is ~2-3% lower for some of our workloads. After some digging, Johannes found that our involuntary context switch rate was ~2x higher, and we were leaving a CPU idle a higher percentage of the time, even though the workload was trying to saturate the system.
We were able to reproduce the problem with schbench, and Johannes bisected down to:
commit
0b0695f2b34a4afa3f6e9aa1ff0e5336d8dad912Author: Vincent Guittot <[email protected]> Date: Fri Oct 18 15:26:31 2019 +0200sched/fair: Rework
load_balance()
Quoted 8 lines
Our working theory is the load balancing changes are leaving processes behind busy CPUs instead of moving them onto idle ones. I made a few schbench modifications to make this easier to demonstrate:
https://git.kernel.org/pub/scm/linux/kernel/git/mason/schbench.git/
My VM has 40 cpus (20 cores, 2 threads per core), and my schbench command line is:
What is the topology ? are they all part of the same LLC ?
Quoted 50 lines
schbench -t 20 -r 0 -c 1000000 -s 1000 -i 30 -z 120
This has two message threads, and 20 workers per message thread. Once woken up, the workers think for a full second, which means you’ll have some long latencies if you’re stuck behind one of these workers in the runqueue. The message thread does a little bit of work and then sleeps, so we end up with 40 threads hammering full blast on the CPU and 2 threads popping in and out of idle.
schbench times the delay from when a message thread wakes a worker to when the worker runs. On a good kernel, the output looks like this:
Latency percentiles (usec) runtime 1290 (s) (3280 total samples)
50.0th: 155 (1653 samples) 75.0th: 189 (808 samples) 90.0th: 216 (501 samples) 95.0th: 227 (163 samples) *99.0th: 256 (123 samples) 99.5th: 1510 (16 samples) 99.9th: 3132 (13 samples) min=21, max=3286With
0b0695f2b34a, we get this:Latency percentiles (usec) runtime 1440 (s) (4480 total samples)
50.0th: 147 (2261 samples) 75.0th: 182 (1116 samples) 90.0th: 205 (671 samples) 95.0th: 224 (215 samples) *99.0th: 12240 (173 samples) <—— much higher p99 and up 99.5th: 12752 (22 samples) 99.9th: 13104 (18 samples) min=21, max=13172Since the idea is to fully load the machine with schbench, use schbench -t <your_num_cpus/2>, and make sure the box doesn’t have other stuff running in the background. I used a VM because it ended up giving more consistent results on our kernel test machines, which have some periodic noise running in the background.
We’ve tried a few different approaches, but don’t quite have a solid fix yet. I thought I’d kick off the discussion with my most useful hunks so far:
diff
a/kernel/sched/fair.cb/kernel/sched/fair.ckernel/sched/fair.c +0
-1-chris
Quoted 10 lines · Vincent Guittot
Hi Chris
Quoted 4 lines · Chris Mason
Hi everyone,
We’re validating a new kernel in the fleet, and compared with v5.2,
Which version are you using ?
several improvements have been added since v5.5 and the rework ofload_balance
We’re validating v5.6, but all of the numbers referenced in this patch are against v5.9. I usually try to back port my way to victory on this kind of thing, but mainline seems to behave exactly the same as 0b0695f2b34a wrt this benchmark.
Quoted 19 lines
Quoted 19 lines
performance is ~2-3% lower for some of our workloads. After some digging, Johannes found that our involuntary context switch rate was ~2x higher, and we were leaving a CPU idle a higher percentage of the time, even though the workload was trying to saturate the system.
We were able to reproduce the problem with schbench, and Johannes bisected down to:
commit
0b0695f2b34a4afa3f6e9aa1ff0e5336d8dad912Author: Vincent Guittot <[email protected]> Date: Fri Oct 18 15:26:31 2019 +0200sched/fair: Rework
load_balance()Our working theory is the load balancing changes are leaving processes behind busy CPUs instead of moving them onto idle ones. I made a few schbench modifications to make this easier to demonstrate:
Quoted 6 lines
Quoted 4 lines
https://git.kernel.org/pub/scm/linux/kernel/git/mason/schbench.git/
My VM has 40 cpus (20 cores, 2 threads per core), and my schbench command line is:
What is the topology ? are they all part of the same LLC ?
We’ve seen the regression on both single socket and dual socket bare metal intel systems. On the VM I reproduced with, I saw similar latencies with and without siblings configured into the topology.
-chris
Vincent Guittot
maintainerQuoted 10 lines · Chris Mason
Quoted 8 lines · Vincent Guittot
Hi Chris
Quoted 4 lines · Chris Mason
Hi everyone,
We’re validating a new kernel in the fleet, and compared with v5.2,
Quoted 8 lines
Quoted 3 lines
Which version are you using ?
several improvements have been added since v5.5 and the rework ofload_balanceWe’re validating v5.6, but all of the numbers referenced in this patch are against v5.9. I usually try to back port my way to victory on this kind of thing, but mainline seems to behave exactly the same as
0b0695f2b34awrt this benchmark.
ok. Thanks for the confirmation
I have been able to reproduce the problem on my setup.
Could you try the fix below ?
kernel/sched/fair.c +2 -1
@@ -9049,7 +9049,8 @@ static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *s* emptying busiest. */ if (local->group_type == group_has_spare) { -if (busiest->group_type > group_fully_busy) { +if ((busiest->group_type > group_fully_busy) && + (busiest->group_weight >1 )) {/* * If busiest is overloaded, try to fill spare * capacity. This might end up creating spare capacity
When we calculate an imbalance at te smallest level, ie between CPUs (group_weight == 1), we should try to spread tasks on cpus instead of trying to fill spare capacity.
Quoted 35 lines
Quoted 23 lines
Quoted 23 lines
performance is ~2-3% lower for some of our workloads. After some digging, Johannes found that our involuntary context switch rate was ~2x
higher, and we were leaving a CPU idle a higher percentage of the time,
even though the workload was trying to saturate the system.We were able to reproduce the problem with schbench, and Johannes bisected down to:
commit
0b0695f2b34a4afa3f6e9aa1ff0e5336d8dad912Author: Vincent Guittot <[email protected]> Date: Fri Oct 18 15:26:31 2019 +0200sched/fair: Rework
load_balance()Our working theory is the load balancing changes are leaving processes
behind busy CPUs instead of moving them onto idle ones. I made a few schbench modifications to make this easier to demonstrate:Quoted 6 lines
Quoted 4 lines
https://git.kernel.org/pub/scm/linux/kernel/git/mason/schbench.git/
My VM has 40 cpus (20 cores, 2 threads per core), and my schbench command line is:
What is the topology ? are they all part of the same LLC ?
We’ve seen the regression on both single socket and dual socket bare metal intel systems. On the VM I reproduced with, I saw similar latencies with and without siblings configured into the topology.
-chris
Quoted 46 lines · Vincent Guittot
Quoted 14 lines · Chris Mason
Quoted 11 lines · Vincent Guittot
Hi Chris
Quoted 4 lines · Chris Mason
Hi everyone,
We’re validating a new kernel in the fleet, and compared with v5.2,
Which version are you using ?
several improvements have been added since v5.5 and the rework ofload_balanceQuoted 7 lines
We’re validating v5.6, but all of the numbers referenced in this patch are
against v5.9. I usually try to back port my way to victory on this kind of
thing, but mainline seems to behave exactly the same as0b0695f2b34awrt
this benchmark.ok. Thanks for the confirmation
I have been able to reproduce the problem on my setup.
Could you try the fix below ?
kernel/sched/fair.c +0
-0@@ -9049,7 +9049,8 @@ static inline void calculate_imbalance(struct
lb_env*env, structsd_lb_stats*s* emptying busiest. */ if (local->group_type == group_has_spare) {kernel/sched/fair.c +2
-1-if (busiest->group_type > group_fully_busy) { +if ((busiest->group_type > group_fully_busy) && + (busiest->group_weight >1 )) {/* * If busiest is overloaded, try to fill spare
* capacity. This might end up creating spare
capacity
Quoted 4 lines
When we calculate an imbalance at te smallest level, ie between CPUs (
group_weight== 1),
we should try to spread tasks on cpus instead of trying to fill spare capacity.
Should we also spread tasks when balancing between multi-threaded CPU cores on the same socket?
Say we have groups of CPUs
(0, 2) and CPUs (1, 3),
with CPU 2 idle, and 3 tasks spread between CPUs 1 & 3.
Since they are all on the same LLC, and the task wakeup code has absolutely no hesitation in moving them around, should the load balancer also try to keep tasks within a socket spread across all CPUs?
Signature · 1 line
All Rights Reversed.
Vincent Guittot
maintainerQuoted 48 lines · Rik van Riel
Quoted 46 lines · Vincent Guittot
Quoted 14 lines · Chris Mason
Quoted 11 lines · Vincent Guittot
Hi Chris
Quoted 4 lines · Chris Mason
Hi everyone,
We’re validating a new kernel in the fleet, and compared with v5.2,
Which version are you using ?
several improvements have been added since v5.5 and the rework ofload_balanceQuoted 7 lines
We’re validating v5.6, but all of the numbers referenced in this patch are
against v5.9. I usually try to back port my way to victory on this kind of
thing, but mainline seems to behave exactly the same as0b0695f2b34awrt
this benchmark.ok. Thanks for the confirmation
I have been able to reproduce the problem on my setup.
Could you try the fix below ?
kernel/sched/fair.c +0
-0@@ -9049,7 +9049,8 @@ static inline void calculate_imbalance(struct
lb_env*env, structsd_lb_stats*s* emptying busiest. */ if (local->group_type == group_has_spare) {kernel/sched/fair.c +2
-1-if (busiest->group_type > group_fully_busy) { +if ((busiest->group_type > group_fully_busy) && + (busiest->group_weight >1 )) {/* * If busiest is overloaded, try to fill spare
* capacity. This might end up creating spare
capacity
Quoted 7 lines
Quoted 4 lines
When we calculate an imbalance at te smallest level, ie between CPUs (
group_weight== 1),
we should try to spread tasks on cpus instead of trying to fill spare capacity.Should we also spread tasks when balancing between multi-threaded CPU cores on the same socket?
My explanation is probably misleading. In fact we already try to spread tasks. we just use spare capacity instead of nr_running when there is more than 1 CPU in the group and the group is overloaded. Using spare capacity is a bit more conservative because it tries to not pull more utilization than spare capacity
Quoted 13 lines
Say we have groups of CPUs
(0, 2) and CPUs (1, 3),
with CPU 2 idle, and 3 tasks spread between CPUs 1 & 3.Since they are all on the same LLC, and the task wakeup code has absolutely no hesitation in moving them around, should the load balancer also try to keep tasks within a socket spread across all CPUs?
--
All Rights Reversed.
Quoted 64 lines · Vincent Guittot
Quoted 53 lines · Rik van Riel
Quoted 52 lines · Vincent Guittot
Quoted 16 lines · Chris Mason
Quoted 5 lines · Vincent Guittot
Hi Chris
Quoted 2 lines · Chris Mason
Hi everyone,
Quoted 8 lines
Quoted 3 lines
We’re validating a new kernel in the fleet, and compared with
v5.2,Which version are you using ?
several improvements have been added since v5.5 and the rework ofload_balanceQuoted 9 lines
We’re validating v5.6, but all of the numbers referenced in this
patch are
against v5.9. I usually try to back port my way to victory on this
kind of
thing, but mainline seems to behave exactly the same as0b0695f2b34awrt
this benchmark.ok. Thanks for the confirmation
I have been able to reproduce the problem on my setup.
Could you try the fix below ?
kernel/sched/fair.c +0
-0@@ -9049,7 +9049,8 @@ static inline voidcalculate_imbalance(struct
lb_env*env, structsd_lb_stats*s* emptying busiest. */ if (local->group_type == group_has_spare) {kernel/sched/fair.c +2
-1-if (busiest->group_type > group_fully_busy) { +if ((busiest->group_type > group_fully_busy) && + (busiest->group_weight >1 )) {/* * If busiest is overloaded, try to fill spare
* capacity. This might end up creating
spare
capacityQuoted 9 lines
Quoted 6 lines
When we calculate an imbalance at te smallest level, ie between CPUs
(group_weight== 1),
we should try to spread tasks on cpus instead of trying to fill spare
capacity.Should we also spread tasks when balancing between multi-threaded CPU cores on the same socket?
Quoted 5 lines
My explanation is probably misleading. In fact we already try to spread tasks. we just use spare capacity instead of
nr_runningwhen there is more than 1 CPU in the group and the group is overloaded. Using spare capacity is a bit more conservative because it tries to not pull more utilization than spare capacity
Could utilization estimates be off, either lagging or simply having a wrong estimate for a task, resulting in no task getting pulled sometimes, while doing a migrate_task imbalance always moves over something?
Within an LLC we might not need to worry too much about spare capacity, considering select_idle_sibling doesn't give a hoot about capacity, either.
Signature · 1 line
All Rights Reversed.
Vincent Guittot
maintainerQuoted 72 lines · Rik van Riel
Quoted 64 lines · Vincent Guittot
Quoted 53 lines · Rik van Riel
Quoted 52 lines · Vincent Guittot
Quoted 16 lines · Chris Mason
Quoted 5 lines · Vincent Guittot
Hi Chris
Quoted 2 lines · Chris Mason
Hi everyone,
Quoted 8 lines
Quoted 3 lines
We’re validating a new kernel in the fleet, and compared with
v5.2,Which version are you using ?
several improvements have been added since v5.5 and the rework ofload_balanceQuoted 9 lines
We’re validating v5.6, but all of the numbers referenced in this
patch are
against v5.9. I usually try to back port my way to victory on this
kind of
thing, but mainline seems to behave exactly the same as0b0695f2b34awrt
this benchmark.ok. Thanks for the confirmation
I have been able to reproduce the problem on my setup.
Could you try the fix below ?
kernel/sched/fair.c +0
-0@@ -9049,7 +9049,8 @@ static inline voidcalculate_imbalance(struct
lb_env*env, structsd_lb_stats*s* emptying busiest. */ if (local->group_type == group_has_spare) {kernel/sched/fair.c +2
-1-if (busiest->group_type > group_fully_busy) { +if ((busiest->group_type > group_fully_busy) && + (busiest->group_weight >1 )) {/* * If busiest is overloaded, try to fill spare
* capacity. This might end up creating
spare
capacityQuoted 9 lines
Quoted 6 lines
When we calculate an imbalance at te smallest level, ie between CPUs
(group_weight== 1),
we should try to spread tasks on cpus instead of trying to fill spare
capacity.Should we also spread tasks when balancing between multi-threaded CPU cores on the same socket?
Quoted 5 lines
My explanation is probably misleading. In fact we already try to spread tasks. we just use spare capacity instead of
nr_runningwhen there is more than 1 CPU in the group and the group is overloaded. Using spare capacity is a bit more conservative because it tries to not pull more utilization than spare capacity
Quoted 4 lines
Could utilization estimates be off, either lagging or simply having a wrong estimate for a task, resulting in no task getting pulled sometimes, while doing a
migrate_taskimbalance always moves over something?
task and cpu utilization are not always up to fully synced and may lag a bit which explains that sometimes LB can fail to migrate for a small diff
Quoted 7 lines
Within an LLC we might not need to worry too much about spare capacity, considering
select_idle_siblingdoesn't give a hoot about capacity, either.--
All Rights Reversed.
Vincent Guittot
maintainerQuoted 74 lines · Vincent Guittot
Quoted 72 lines · Rik van Riel
Quoted 69 lines · Vincent Guittot
Quoted 53 lines · Rik van Riel
Quoted 52 lines · Vincent Guittot
Quoted 16 lines · Chris Mason
Quoted 5 lines · Vincent Guittot
Hi Chris
Quoted 2 lines · Chris Mason
Hi everyone,
Quoted 8 lines
Quoted 3 lines
We’re validating a new kernel in the fleet, and compared with
v5.2,Which version are you using ?
several improvements have been added since v5.5 and the rework ofload_balanceQuoted 9 lines
We’re validating v5.6, but all of the numbers referenced in this
patch are
against v5.9. I usually try to back port my way to victory on this
kind of
thing, but mainline seems to behave exactly the same as0b0695f2b34awrt
this benchmark.ok. Thanks for the confirmation
I have been able to reproduce the problem on my setup.
Could you try the fix below ?
kernel/sched/fair.c +0
-0@@ -9049,7 +9049,8 @@ static inline voidcalculate_imbalance(struct
lb_env*env, structsd_lb_stats*s* emptying busiest. */ if (local->group_type == group_has_spare) {kernel/sched/fair.c +2
-1-if (busiest->group_type > group_fully_busy) { +if ((busiest->group_type > group_fully_busy) && + (busiest->group_weight >1 )) {/* * If busiest is overloaded, try to fill spare
* capacity. This might end up creating
spare
capacityQuoted 9 lines
Quoted 6 lines
When we calculate an imbalance at te smallest level, ie between CPUs
(group_weight== 1),
we should try to spread tasks on cpus instead of trying to fill spare
capacity.Should we also spread tasks when balancing between multi-threaded CPU cores on the same socket?
My explanation is probably misleading. In fact we already try to spread tasks. we just use spare capacity instead of
nr_runningwhen there is more than 1 CPU in the group and the group is overloaded. Using spare capacity is a bit more conservative because it tries to not pull more utilization than spare capacity
Quoted 8 lines
Quoted 4 lines
Could utilization estimates be off, either lagging or simply having a wrong estimate for a task, resulting in no task getting pulled sometimes, while doing a
migrate_taskimbalance always moves over something?task and cpu utilization are not always up to fully synced and may lag a bit which explains that sometimes LB can fail to migrate for a small diff
And also from util_est which reports the max utilization of the task to be sure that LB migrates a task on a cpu that will have enough available capacity
Quoted 8 lines
Quoted 8 lines
Within an LLC we might not need to worry too much about spare capacity, considering
select_idle_siblingdoesn't give a hoot about capacity, either.--
All Rights Reversed.
Quoted 10 lines · On Mon, 26 Oct 2020 16:42:14 +0100 Vincent Guittot…
Quoted 4 lines · Rik van Riel
Could utilization estimates be off, either lagging or simply having a wrong estimate for a task, resulting in no task getting pulled sometimes, while doing a
migrate_taskimbalance always moves over something?task and cpu utilization are not always up to fully synced and may lag a bit which explains that sometimes LB can fail to migrate for a small diff
OK, running with this little snippet below, I see latencies improve back to near where they used to be:
Latency percentiles (usec) runtime 150 (s)
50.0th: 13
75.0th: 31
90.0th: 69
95.0th: 90
*99.0th: 761
99.5th: 2268
99.9th: 9104
min=1, max=16158I suspect the right/cleaner approach might be to use migrate_task more in !CPU_NOT_IDLE cases?
Running a task to an idle CPU immediately, instead of refusing to have the load balancer move it, improves latencies for fairly obvious reasons.
I am not entirely clear on why the load balancer should need to be any more conservative about moving tasks than the wakeup path is in eg. select_idle_sibling.
kernel/sched/fair.c +1 -1
@@ -7415,7 +7415,7 @@ static int detach_tasks(struct lb_env *env)case migrate_util: util =task_util_est (p); -if (util > env->imbalance) +if (util > env->imbalance && env->idle ==CPU_NOT_IDLE ) goto next; env->imbalance -= util;
Vincent Guittot
maintainerQuoted 29 lines · Rik van Riel
Quoted 10 lines · On Mon, 26 Oct 2020 16:42:14 +0100 Vincent Guittot…
Quoted 4 lines · Rik van Riel
Could utilization estimates be off, either lagging or simply having a wrong estimate for a task, resulting in no task getting pulled sometimes, while doing a
migrate_taskimbalance always moves over something?task and cpu utilization are not always up to fully synced and may lag a bit which explains that sometimes LB can fail to migrate for a small diff
OK, running with this little snippet below, I see latencies improve back to near where they used to be:
Latency percentiles (usec) runtime 150 (s)
50.0th: 13 75.0th: 31 90.0th: 69 95.0th: 90 *99.0th: 761 99.5th: 2268 99.9th: 9104 min=1, max=16158I suspect the right/cleaner approach might be to use
migrate_taskmore in !CPU_NOT_IDLE cases?
Quoted 7 lines
Running a task to an idle CPU immediately, instead of refusing to have the load balancer move it, improves latencies for fairly obvious reasons.
I am not entirely clear on why the load balancer should need to be any more conservative about moving tasks than the wakeup path is in eg.
select_idle_sibling.
what you are suggesting is something like:
kernel/sched/fair.c +2 -1
@@ -9156,7 +9156,8 @@ static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *s* emptying busiest. */ if (local->group_type == group_has_spare) { -if (busiest->group_type > group_fully_busy) { +if ((busiest->group_type > group_fully_busy) && + !(env->sd->flags &SD_SHARE_PKG_RESOURCES )) {/* * If busiest is overloaded, try to fill spare * capacity. This might end up creating spare capacity
which also fixes the problem for me and alignes LB with wakeup path regarding the migration in the LLC
kernel/sched/fair.c static int detach_tasks(struct lb_env *env) · line 7418
Quoted 12 lines
kernel/sched/fair.c +1
-1@@ -7415,7 +7415,7 @@ static int detach_tasks(struct lb_env *env)case migrate_util: util =task_util_est (p); -if (util > env->imbalance) +if (util > env->imbalance && env->idle ==CPU_NOT_IDLE )
we don't want to be so agressive outside LLC and such bypass will defeat the purpose of using utilization instead of nr_running.
Quoted 3 lines
kernel/sched/fair.c +0
-0goto next; env->imbalance -= util;
Quoted 57 lines · Vincent Guittot
Quoted 29 lines · Rik van Riel
Quoted 10 lines · On Mon, 26 Oct 2020 16:42:14 +0100 Vincent Guittot…
Quoted 4 lines · Rik van Riel
Could utilization estimates be off, either lagging or simply having a wrong estimate for a task, resulting in no task getting pulled sometimes, while doing a
migrate_taskimbalance always moves over something?task and cpu utilization are not always up to fully synced and may lag a bit which explains that sometimes LB can fail to migrate for a small diff
OK, running with this little snippet below, I see latencies improve back to near where they used to be:
Latency percentiles (usec) runtime 150 (s)
50.0th: 13 75.0th: 31 90.0th: 69 95.0th: 90 *99.0th: 761 99.5th: 2268 99.9th: 9104 min=1, max=16158I suspect the right/cleaner approach might be to use
migrate_taskmore in !CPU_NOT_IDLE cases?Quoted 7 lines
Running a task to an idle CPU immediately, instead of refusing to have the load balancer move it, improves latencies for fairly obvious reasons.
I am not entirely clear on why the load balancer should need to be any more conservative about moving tasks than the wakeup path is in eg.
select_idle_sibling.what you are suggesting is something like:
kernel/sched/fair.c +0
-0@@ -9156,7 +9156,8 @@ static inline void calculate_imbalance(struct
lb_env*env, structsd_lb_stats*s* emptying busiest. */ if (local->group_type == group_has_spare) {kernel/sched/fair.c +2
-1-if (busiest->group_type > group_fully_busy) { +if ((busiest->group_type > group_fully_busy) && + !(env->sd->flags &SD_SHARE_PKG_RESOURCES )) {/* * If busiest is overloaded, try to fill spare * capacity. This might end up creating spare capacity
Quoted 2 lines
which also fixes the problem for me and alignes LB with wakeup path regarding the migration in the LLC
Vincent’s patch on top of 5.10-rc1 looks pretty great:
Latency percentiles (usec) runtime 90 (s) (3320 total samples)
50.0th: 161 (1687 samples)
75.0th: 200 (817 samples)
90.0th: 228 (488 samples)
95.0th: 254 (164 samples)
*99.0th: 314 (131 samples)
99.5th: 330 (17 samples)
99.9th: 356 (13 samples)
min=29, max=358Next we test in prod, which probably won’t have answers until tomorrow. Thanks again Vincent!
-chris
Vincent Guittot
maintainerQuoted 78 lines · Chris Mason
Quoted 59 lines · Vincent Guittot
Quoted 31 lines · Rik van Riel
Quoted 7 lines · On Mon, 26 Oct 2020 16:42:14 +0100 Vincent Guittot…
Quoted 4 lines · Rik van Riel
Could utilization estimates be off, either lagging or simply having a wrong estimate for a task, resulting in no task getting pulled sometimes, while doing a
migrate_taskimbalance always moves over something?Quoted 5 lines
task and cpu utilization are not always up to fully synced and may lag
a bit which explains that sometimes LB can fail to migrate for a small
diffOK, running with this little snippet below, I see latencies improve back to near where they used to be:
Latency percentiles (usec) runtime 150 (s)
50.0th: 13 75.0th: 31 90.0th: 69 95.0th: 90 *99.0th: 761 99.5th: 2268 99.9th: 9104 min=1, max=16158I suspect the right/cleaner approach might be to use
migrate_taskmore in !CPU_NOT_IDLE cases?Quoted 7 lines
Running a task to an idle CPU immediately, instead of refusing to have the load balancer move it, improves latencies for fairly obvious reasons.
I am not entirely clear on why the load balancer should need to be any more conservative about moving tasks than the wakeup path is in eg.
select_idle_sibling.what you are suggesting is something like:
kernel/sched/fair.c +0
-0@@ -9156,7 +9156,8 @@ static inline void calculate_imbalance(struct
lb_env*env, structsd_lb_stats*s* emptying busiest. */ if (local->group_type == group_has_spare) {kernel/sched/fair.c +2
-1-if (busiest->group_type > group_fully_busy) { +if ((busiest->group_type > group_fully_busy) && + !(env->sd->flags &SD_SHARE_PKG_RESOURCES )) {/* * If busiest is overloaded, try to fill spare * capacity. This might end up creating spare capacity
Quoted 3 lines
which also fixes the problem for me and alignes LB with wakeup path regarding the migration
in the LLCVincent’s patch on top of 5.10-rc1 looks pretty great:
Latency percentiles (usec) runtime 90 (s) (3320 total samples)
50.0th: 161 (1687 samples) 75.0th: 200 (817 samples) 90.0th: 228 (488 samples) 95.0th: 254 (164 samples) *99.0th: 314 (131 samples) 99.5th: 330 (17 samples) 99.9th: 356 (13 samples) min=29, max=358
Quoted 2 lines
Next we test in prod, which probably won’t have answers until tomorrow. Thanks again Vincent!
Great !
I'm going to run more tests on my setup as well to make sure that it doesn't generate unexpected side effects on other kinds of use cases.
Quoted 2 lines
-chris
Quoted 41 lines · Vincent Guittot
Quoted 40 lines · Chris Mason
Quoted 21 lines · Vincent Guittot
what you are suggesting is something like:
kernel/sched/fair.c +0
-0@@ -9156,7 +9156,8 @@ static inline voidcalculate_imbalance(struct
lb_env*env, structsd_lb_stats*s* emptying busiest. */ if (local->group_type == group_has_spare) {kernel/sched/fair.c +2
-1-if (busiest->group_type > group_fully_busy) { +if ((busiest->group_type > group_fully_busy) && + !(env->sd->flags &SD_SHARE_PKG_RESOURCES )) {/* * If busiest is overloaded, try to fill spare
* capacity. This might end up creating
spare
capacityQuoted 4 lines
which also fixes the problem for me and alignes LB with wakeup path
regarding the migration
in the LLCVincent’s patch on top of 5.10-rc1 looks pretty great:
Latency percentiles (usec) runtime 90 (s) (3320 total samples)
50.0th: 161 (1687 samples) 75.0th: 200 (817 samples) 90.0th: 228 (488 samples) 95.0th: 254 (164 samples) *99.0th: 314 (131 samples) 99.5th: 330 (17 samples) 99.9th: 356 (13 samples) min=29, max=358
Quoted 7 lines
Quoted 2 lines
Next we test in prod, which probably won’t have answers until tomorrow. Thanks again Vincent!
Great !
I'm going to run more tests on my setup as well to make sure that it doesn't generate unexpected side effects on other kinds of use cases.
We have tested the patch with several pretty demanding workloads for the past several days, and it seems to do the trick!
With all the current scheduler code from the Linus tree, plus this patch on top, performance is as good as it ever was before with one workload, and slightly better with the other.
Signature · 1 line
All Rights Reversed.
Vincent Guittot
maintainerQuoted 51 lines · Rik van Riel
Quoted 41 lines · Vincent Guittot
Quoted 40 lines · Chris Mason
Quoted 21 lines · Vincent Guittot
what you are suggesting is something like:
kernel/sched/fair.c +0
-0@@ -9156,7 +9156,8 @@ static inline voidcalculate_imbalance(struct
lb_env*env, structsd_lb_stats*s* emptying busiest. */ if (local->group_type == group_has_spare) {kernel/sched/fair.c +2
-1-if (busiest->group_type > group_fully_busy) { +if ((busiest->group_type > group_fully_busy) && + !(env->sd->flags &SD_SHARE_PKG_RESOURCES )) {/* * If busiest is overloaded, try to fill spare
* capacity. This might end up creating
spare
capacityQuoted 4 lines
which also fixes the problem for me and alignes LB with wakeup path
regarding the migration
in the LLCVincent’s patch on top of 5.10-rc1 looks pretty great:
Latency percentiles (usec) runtime 90 (s) (3320 total samples)
50.0th: 161 (1687 samples) 75.0th: 200 (817 samples) 90.0th: 228 (488 samples) 95.0th: 254 (164 samples) *99.0th: 314 (131 samples) 99.5th: 330 (17 samples) 99.9th: 356 (13 samples) min=29, max=358Quoted 7 lines
Quoted 2 lines
Next we test in prod, which probably won’t have answers until tomorrow. Thanks again Vincent!
Great !
I'm going to run more tests on my setup as well to make sure that it doesn't generate unexpected side effects on other kinds of use cases.
Quoted 8 lines
We have tested the patch with several pretty demanding workloads for the past several days, and it seems to do the trick!
With all the current scheduler code from the Linus tree, plus this patch on top, performance is as good as it ever was before with one workload, and slightly better with the other.
Thanks for the test results.
I still have a few tests to run on my systems but current results look good for me too.
Quoted 3 lines
--
All Rights Reversed.
Quoted 15 lines · Vincent Guittot
Quoted 14 lines · Chris Mason
Quoted 11 lines · Vincent Guittot
Hi Chris
Quoted 4 lines · Chris Mason
Hi everyone,
We’re validating a new kernel in the fleet, and compared with v5.2,
Which version are you using ?
several improvements have been added since v5.5 and the rework ofload_balance
Quoted 8 lines
Quoted 4 lines
We’re validating v5.6, but all of the numbers referenced in this patch are against v5.9. I usually try to back port my way to victory on this kind of thing, but mainline seems to behave exactly the same as
0b0695f2b34awrt this benchmark.ok. Thanks for the confirmation
I have been able to reproduce the problem on my setup.
Thanks for taking a look! Can I ask what parameters you used on schbench, and what kind of results you saw? Mostly I’m trying to make sure it’s a useful tool, but also the patch didn’t change things here.
Quoted 19 lines
Could you try the fix below ?
kernel/sched/fair.c +0
-0@@ -9049,7 +9049,8 @@ static inline void calculate_imbalance(struct
lb_env*env, structsd_lb_stats*s* emptying busiest. */ if (local->group_type == group_has_spare) {kernel/sched/fair.c +2
-1-if (busiest->group_type > group_fully_busy) { +if ((busiest->group_type > group_fully_busy) && + (busiest->group_weight >1 )) {/* * If busiest is overloaded, try to fill spare * capacity. This might end up creating spare capacity
Quoted 2 lines
When we calculate an imbalance at te smallest level, ie between CPUs (
group_weight== 1), we should try to spread tasks on cpus instead of trying to fill spare capacity.
With this patch on top of v5.9, my latencies are unchanged. I’m building against current Linus now just in case I’m missing other fixes.
-chris
Vincent Guittot
maintainerQuoted 28 lines · Chris Mason
Quoted 24 lines · Vincent Guittot
Quoted 22 lines · Chris Mason
Quoted 4 lines · Vincent Guittot
Hi Chris
Quoted 1 line · Chris Mason
Quoted 8 lines
Quoted 4 lines
Hi everyone,
We’re validating a new kernel in the fleet, and compared with v5.2,
Which version are you using ?
several improvements have been added since v5.5 and the rework ofload_balanceWe’re validating v5.6, but all of the numbers referenced in this patch are
against v5.9. I usually try to back port my way to victory on this kind of
thing, but mainline seems to behave exactly the same as0b0695f2b34awrt
this benchmark.
Quoted 8 lines
Quoted 3 lines
ok. Thanks for the confirmation
I have been able to reproduce the problem on my setup.
Thanks for taking a look! Can I ask what parameters you used on schbench, and what kind of results you saw? Mostly I’m trying to make sure it’s a useful tool, but also the patch didn’t change things here.
with latest tip/sched/core on my dual quad cores:
schbench -t 4 -r 10 -c 1000000 -s 1000
Latency percentiles (usec)
50.0th: 16
75.0th: 23
90.0th: 32
95.0th: 41
*99.0th: 15120
99.5th: 15120
99.9th: 15120
min=0, max=15130
with the patch :
schbench -t 4 -r 10 -c 1000000 -s 1000
Latency percentiles (usec)
50.0th: 28
75.0th: 32
90.0th: 36
95.0th: 56
*99.0th: 1310
99.5th: 1310
99.9th: 1310
min=0, max=1309
Quoted 19 lines
Quoted 19 lines
Could you try the fix below ?
kernel/sched/fair.c +0
-0@@ -9049,7 +9049,8 @@ static inline void calculate_imbalance(struct
lb_env*env, structsd_lb_stats*s* emptying busiest. */ if (local->group_type == group_has_spare) {kernel/sched/fair.c +2
-1-if (busiest->group_type > group_fully_busy) { +if ((busiest->group_type > group_fully_busy) && + (busiest->group_weight >1 )) {/* * If busiest is overloaded, try to fill spare * capacity. This might end up creating spare capacity
Quoted 8 lines
Quoted 4 lines
When we calculate an imbalance at te smallest level, ie between CPUs (
group_weight== 1),
we should try to spread tasks on cpus instead of trying to fill spare capacity.With this patch on top of v5.9, my latencies are unchanged. I’m building against current Linus now just in case I’m missing other fixes.
I can't remember any changes in mainline that would make a difference
I had another way to fix it but it could impact more other UC and the improvement was smaller
--- kernel/sched/fair.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/sched/fair.c +1 -1
@@ -7707,7 +7707,7 @@ static int detach_tasks(struct lb_env *env)case migrate_util: util =task_util_est (p); -if (util > env->imbalance) +if ((util >> env->sd->nr_balance_failed) > env->imbalance) goto next; env->imbalance -= util;
--
Quoted 2 lines
-chris
Quoted 22 lines · Chris Mason
Quoted 20 lines · Vincent Guittot
Could you try the fix below ?
kernel/sched/fair.c +0
-0@@ -9049,7 +9049,8 @@ static inline void calculate_imbalance(struct
lb_env*env, structsd_lb_stats*s* emptying busiest. */ if (local->group_type == group_has_spare) {kernel/sched/fair.c +2
-1-if (busiest->group_type > group_fully_busy) { +if ((busiest->group_type > group_fully_busy) && + (busiest->group_weight >1 )) {/* * If busiest is overloaded, try to fill spare
* capacity. This might end up creating spare
capacity
Quoted 5 lines
Quoted 2 lines
When we calculate an imbalance at te smallest level, ie between CPUs (
group_weight== 1), we should try to spread tasks on cpus instead of trying to fill spare capacity.With this patch on top of v5.9, my latencies are unchanged. I’m building against current Linus now just in case I’m missing other fixes.
I reran things to make sure the nothing changed on my test box this weekend:
5.4.0-rc1-00009-gfcf0553db6f4 (last good kernel) Latency percentiles (usec) runtime 30 (s) (1000 total samples)
50.0th: 180 (502 samples)
75.0th: 227 (251 samples)
90.0th: 268 (147 samples)
95.0th: 300 (50 samples)
*99.0th: 338 (41 samples)
99.5th: 344 (4 samples)
99.9th: 1186 (5 samples)
min=25, max=11855.4.0-rc1-00010-g0b0695f2b34a (first bad kernel) Latency percentiles (usec) runtime 150 (s) (960 total samples)
50.0th: 166 (488 samples)
75.0th: 210 (232 samples)
90.0th: 254 (145 samples)
95.0th: 299 (47 samples)
*99.0th: 12688 (39 samples)
99.5th: 13008 (5 samples)
99.9th: 13104 (4 samples)
min=24, max=131003650b228f83adda7e5ee532e2b90429c03f7b9ec (v5.10-rc1) + your patch
Latency percentiles (usec) runtime 30 (s) (1000 total samples)
50.0th: 169 (505 samples)
75.0th: 210 (246 samples)
90.0th: 267 (151 samples)
95.0th: 305 (48 samples)
*99.0th: 12656 (40 samples)
99.5th: 12944 (5 samples)
99.9th: 13168 (5 samples)
min=44, max=13155-chris