[Problem Statement]
For a workload that is doing frequent context switches, the throughput
scales well until the number of instances reaches a peak point. After
that peak point, the throughput drops significantly if the number of
instances continues to increase.
The will-it-scale context_switch1 test case exposes the issue. The
test platform has 112 CPUs per LLC domain. The will-it-scale launches
1, 8, 16 ... 112 instances respectively. Each instance is composed
of 2 tasks, and each pair of tasks would do ping-pong scheduling via
pipe_read() and pipe_write(). No task is bound to any CPU.
It is found that, once the number of instances is higher than
56(112 tasks in total, every CPU has 1 task), the throughput
drops accordingly if the instance number continues to increase:
^
throughput|
| X
| X X X
| X X X
| X X
| X X
| X
| X
| X
| X
|
+-----------------.------------------->
56
number of instances
[Symptom analysis]
The performance downgrading was caused by a high system idle
percentage(around 20% ~ 30%). The CPUs waste a lot of time in
idle and do nothing. As a comparison, if set CPU affinity to
these workloads and stops them from migrating among CPUs,
the idle percentage drops to nearly 0%, and the throughput
increases by about 300%. This indicates room for optimization.
The reason for the high idle percentage is different before/after
commit f3dd3f674555 ("sched: Remove the limitation of WF_ON_CPU
on wakelist if wakee cpu is idle").
[Before the commit]
The bottleneck is the runqueue spinlock.
nr_instance rq lock percentage
1 1.22%
8 1.17%
16 1.20%
24 1.22%
32 1.46%
40 1.61%
48 1.63%
56 1.65%
--------------------------
64 3.77% |
72 5.90% | increase
80 7.95% |
88 9.98% v
96 11.81%
104 13.54%
112 15.13%
And top 2 rq lock hot paths:
(path1):
raw_spin_rq_lock_nested.constprop.0;
try_to_wake_up;
default_wake_function;
autoremove_wake_function;
__wake_up_common;
__wake_up_common_lock;
__wake_up_sync_key;
pipe_write;
new_sync_write;
vfs_write;
ksys_write;
__x64_sys_write;
do_syscall_64;
entry_SYSCALL_64_after_hwframe;write
(path2):
raw_spin_rq_lock_nested.constprop.0;
__sched_text_start;
schedule_idle;
do_idle;
cpu_startup_entry;
start_secondary;
secondary_startup_64_no_verify
task A tries to wake up task B on CPU1, then task A grabs the
runqueue lock of CPU1. If CPU1 is about to quit idle, it needs
to grab its lock which has been taken by someone else. Then
CPU1 takes more time to quit which hurts the performance.
[After the commit]
The cause is the race condition between select_task_rq() and
the task enqueue.
Suppose there are nr_cpus pairs of ping-pong scheduling
tasks. For example, p0' and p0 are ping-pong scheduling,
so do p1' <=> p1, and p2'<=> p2. None of these tasks are
bound to any CPUs. The problem can be summarized as:
more than 1 wakers are stacked on 1 CPU, which slows down
waking up their wakees:
CPU0 CPU1 CPU2
p0' p1' => idle p2'
try_to_wake_up(p0) try_to_wake_up(p2);
CPU1 = select_task_rq(p0); CPU1 = select_task_rq(p2);
ttwu_queue(p0, CPU1); ttwu_queue(p2, CPU1);
__ttwu_queue_wakelist(p0, CPU1); => ttwu_list->p0
quiting cpuidle_idle_call()
ttwu_list->p2->p0 <= __ttwu_queue_wakelist(p2, CPU1);
WRITE_ONCE(CPU1->ttwu_pending, 1); WRITE_ONCE(CPU1->ttwu_pending, 1);
p0' => idle
sched_ttwu_pending()
enqueue_task(p2 and p0)
idle => p2
...
p2 time slice expires
...
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
<=== !!! p2 delays the wake up of p0' !!!
!!! causes long idle on CPU0 !!!
p2 => p0 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
p0 wakes up p0'
idle => p0'
Since there are many waker/wakee pairs in the system, the chain reaction
causes many CPUs to be victims. These idle CPUs wait for their waker to
be scheduled.
Actually Tiancheng has mentioned above issue here[2].
[Proposal]
The root cause is that there is no strict synchronization of select_task_rq()
and the set of ttwu_pending flag among several CPUs. And this might be by
design because the scheduler prefers parallel wakeup.
So avoid this problem indirectly. If a system does not have idle cores,
and if the waker and wakee are both short duration tasks, wake up the wakee on
the same CPU as waker.
The reason is that, if the waker is a short-duration task, it might
relinquish the CPU soon, and the wakee has the chance to be scheduled.
On the other hand, if the wakee is a short duration task, putting it on
non-idle CPU would bring minimal impact to the running task. No idle
core in the system indicates that this mechanism should not inhibit
spreading the tasks if the system have idle core.
[Benchmark results]
The baseline is v6.1-rc6. The test platform has 56 Cores(112 CPUs) per
LLC domain. C-states deeper than C1E are disabled. Turbo is disabled.
CPU frequency governor is performance.
will-it-scale.context_switch1
=============================
+331.13%
hackbench
=========
case load baseline(std%) compare%( std%)
process-pipe 1 group 1.00 ( 1.50) +0.83 ( 0.19)
process-pipe 2 groups 1.00 ( 0.77) +0.82 ( 0.52)
process-pipe 4 groups 1.00 ( 0.20) -2.07 ( 2.91)
process-pipe 8 groups 1.00 ( 0.05) +3.48 ( 0.06)
process-sockets 1 group 1.00 ( 2.90) -11.20 ( 11.99)
process-sockets 2 groups 1.00 ( 5.42) -1.39 ( 1.70)
process-sockets 4 groups 1.00 ( 0.17) -0.20 ( 0.19)
process-sockets 8 groups 1.00 ( 0.03) -0.05 ( 0.11)
threads-pipe 1 group 1.00 ( 2.09) -1.63 ( 0.44)
threads-pipe 2 groups 1.00 ( 0.28) -0.21 ( 1.48)
threads-pipe 4 groups 1.00 ( 0.27) +0.13 ( 0.63)
threads-pipe 8 groups 1.00 ( 0.14) +5.04 ( 0.04)
threads-sockets 1 group 1.00 ( 2.51) -1.86 ( 2.08)
threads-sockets 2 groups 1.00 ( 1.24) -0.60 ( 3.83)
threads-sockets 4 groups 1.00 ( 0.49) +0.07 ( 0.46)
threads-sockets 8 groups 1.00 ( 0.09) -0.04 ( 0.08)
netperf
=======
case load baseline(std%) compare%( std%)
TCP_RR 28 threads 1.00 ( 0.81) -0.13 ( 0.80)
TCP_RR 56 threads 1.00 ( 0.55) +0.03 ( 0.64)
TCP_RR 84 threads 1.00 ( 0.33) +1.74 ( 0.31)
TCP_RR 112 threads 1.00 ( 0.24) +3.71 ( 0.23)
TCP_RR 140 threads 1.00 ( 0.21) +215.10 ( 12.37)
TCP_RR 168 threads 1.00 ( 61.97) +86.15 ( 12.26)
TCP_RR 196 threads 1.00 ( 14.49) +0.71 ( 14.20)
TCP_RR 224 threads 1.00 ( 9.54) +0.68 ( 7.00)
UDP_RR 28 threads 1.00 ( 1.51) +0.25 ( 1.02)
UDP_RR 56 threads 1.00 ( 7.90) +0.57 ( 7.89)
UDP_RR 84 threads 1.00 ( 6.38) +3.66 ( 20.77)
UDP_RR 112 threads 1.00 ( 10.15) +3.16 ( 11.87)
UDP_RR 140 threads 1.00 ( 9.98) +164.29 ( 12.55)
UDP_RR 168 threads 1.00 ( 10.72) +174.41 ( 17.05)
UDP_RR 196 threads 1.00 ( 18.84) +3.92 ( 15.48)
UDP_RR 224 threads 1.00 ( 16.97) +2.98 ( 16.69)
tbench
======
case load baseline(std%) compare%( std%)
loopback 28 threads 1.00 ( 0.12) -0.38 ( 0.35)
loopback 56 threads 1.00 ( 0.17) -0.04 ( 0.19)
loopback 84 threads 1.00 ( 0.03) +0.95 ( 0.07)
loopback 112 threads 1.00 ( 0.03) +162.42 ( 0.05)
loopback 140 threads 1.00 ( 0.14) -2.26 ( 0.14)
loopback 168 threads 1.00 ( 0.49) -2.15 ( 0.54)
loopback 196 threads 1.00 ( 0.06) -2.38 ( 0.22)
loopback 224 threads 1.00 ( 0.20) -1.95 ( 0.30)
schbench
========
case load baseline(std%) compare%( std%)
normal 1 mthread 1.00 ( 1.46) +1.03 ( 0.00)
normal 2 mthreads 1.00 ( 3.82) -5.41 ( 8.37)
normal 4 mthreads 1.00 ( 1.03) +5.11 ( 2.88)
normal 8 mthreads 1.00 ( 2.96) -2.41 ( 0.93)
In summary, overall there is no significant performance regression detected
and there is a big improvement in netperf/tbench in partially-busy cases.
[Limitations]
As Peter said, the criteria of a short duration task is intuitive, but it
seems to be hard to find an accurate criterion to describe this.
This wake up strategy can be viewed as dynamic WF_SYNC. Except that:
1. Some workloads do not have WF_SYNC set.
2. WF_SYNC does not treat non-idle CPU as candidate target CPU.
Peter has suggested[1] comparing task duration with the cost of searching
for an idle CPU. If the latter is higher, then give up the scan, to
achieve better task affine. However, this method does not fit in the case
encountered in this patch. Because there are plenty of idle CPUs in the system,
it will not take too long to find an idle CPU. The bottleneck is caused by the
race condition mentioned above.
[1] https://lore.kernel.org/lkml/Y2O8a%2FOhk1i1l8ao@hirez.programming.kicks-ass.net/
[2] https://lore.kernel.org/lkml/9ed75cad-3718-356f-21ca-1b8ec601f335@linux.alibaba.com/
Suggested-by: Tim Chen <tim.c.chen@intel.com>
Suggested-by: K Prateek Nayak <kprateek.nayak@amd.com>
Tested-by: kernel test robot <yujie.liu@intel.com>
Signed-off-by: Chen Yu <yu.c.chen@intel.com>
---
kernel/sched/fair.c | 10 ++++++++++
1 file changed, 10 insertions(+)
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index a4b314b664f8..3f7361ec1330 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -6246,6 +6246,11 @@ wake_affine_idle(int this_cpu, int prev_cpu, int sync)
if (available_idle_cpu(prev_cpu))
return prev_cpu;
+ /* The only running task is a short duration one. */
+ if (cpu_rq(this_cpu)->nr_running == 1 &&
+ is_short_task((struct task_struct *)cpu_curr(this_cpu)))
+ return this_cpu;
+
return nr_cpumask_bits;
}
@@ -6612,6 +6617,11 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, bool
time = cpu_clock(this);
}
+ if (!has_idle_core && cpu_rq(target)->nr_running == 1 &&
+ is_short_task((struct task_struct *)cpu_curr(target)) &&
+ is_short_task(p))
+ return target;
+
if (sched_feat(SIS_UTIL)) {
sd_share = rcu_dereference(per_cpu(sd_llc_shared, target));
if (sd_share) {
--
2.25.1Hi Chen Yu,
Just some minor questions below.
On 2022/12/1 16:44, Chen Yu wrote:
> [Problem Statement]
> For a workload that is doing frequent context switches, the throughput
> scales well until the number of instances reaches a peak point. After
> that peak point, the throughput drops significantly if the number of
> instances continues to increase.
>
> The will-it-scale context_switch1 test case exposes the issue. The
> test platform has 112 CPUs per LLC domain. The will-it-scale launches
> 1, 8, 16 ... 112 instances respectively. Each instance is composed
> of 2 tasks, and each pair of tasks would do ping-pong scheduling via
> pipe_read() and pipe_write(). No task is bound to any CPU.
> It is found that, once the number of instances is higher than
> 56(112 tasks in total, every CPU has 1 task), the throughput
> drops accordingly if the instance number continues to increase:
>
> ^
> throughput|
> | X
> | X X X
> | X X X
> | X X
> | X X
> | X
> | X
> | X
> | X
> |
> +-----------------.------------------->
> 56
> number of instances
>
> [Symptom analysis]
>
> The performance downgrading was caused by a high system idle
> percentage(around 20% ~ 30%). The CPUs waste a lot of time in
> idle and do nothing. As a comparison, if set CPU affinity to
> these workloads and stops them from migrating among CPUs,
> the idle percentage drops to nearly 0%, and the throughput
> increases by about 300%. This indicates room for optimization.
>
> The reason for the high idle percentage is different before/after
> commit f3dd3f674555 ("sched: Remove the limitation of WF_ON_CPU
> on wakelist if wakee cpu is idle").
>
> [Before the commit]
> The bottleneck is the runqueue spinlock.
>
> nr_instance rq lock percentage
> 1 1.22%
> 8 1.17%
> 16 1.20%
> 24 1.22%
> 32 1.46%
> 40 1.61%
> 48 1.63%
> 56 1.65%
> --------------------------
> 64 3.77% |
> 72 5.90% | increase
> 80 7.95% |
> 88 9.98% v
> 96 11.81%
> 104 13.54%
> 112 15.13%
>
> And top 2 rq lock hot paths:
>
> (path1):
> raw_spin_rq_lock_nested.constprop.0;
> try_to_wake_up;
> default_wake_function;
> autoremove_wake_function;
> __wake_up_common;
> __wake_up_common_lock;
> __wake_up_sync_key;
> pipe_write;
> new_sync_write;
> vfs_write;
> ksys_write;
> __x64_sys_write;
> do_syscall_64;
> entry_SYSCALL_64_after_hwframe;write
>
> (path2):
> raw_spin_rq_lock_nested.constprop.0;
> __sched_text_start;
> schedule_idle;
> do_idle;
> cpu_startup_entry;
> start_secondary;
> secondary_startup_64_no_verify
>
> task A tries to wake up task B on CPU1, then task A grabs the
> runqueue lock of CPU1. If CPU1 is about to quit idle, it needs
> to grab its lock which has been taken by someone else. Then
> CPU1 takes more time to quit which hurts the performance.
>
> [After the commit]
> The cause is the race condition between select_task_rq() and
> the task enqueue.
>
> Suppose there are nr_cpus pairs of ping-pong scheduling
> tasks. For example, p0' and p0 are ping-pong scheduling,
> so do p1' <=> p1, and p2'<=> p2. None of these tasks are
> bound to any CPUs. The problem can be summarized as:
> more than 1 wakers are stacked on 1 CPU, which slows down
> waking up their wakees:
>
> CPU0 CPU1 CPU2
>
> p0' p1' => idle p2'
>
> try_to_wake_up(p0) try_to_wake_up(p2);
> CPU1 = select_task_rq(p0); CPU1 = select_task_rq(p2);
> ttwu_queue(p0, CPU1); ttwu_queue(p2, CPU1);
> __ttwu_queue_wakelist(p0, CPU1); => ttwu_list->p0
> quiting cpuidle_idle_call()
>
> ttwu_list->p2->p0 <= __ttwu_queue_wakelist(p2, CPU1);
>
> WRITE_ONCE(CPU1->ttwu_pending, 1); WRITE_ONCE(CPU1->ttwu_pending, 1);
>
> p0' => idle
> sched_ttwu_pending()
> enqueue_task(p2 and p0)
>
> idle => p2
>
> ...
> p2 time slice expires
> ...
> !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
> <=== !!! p2 delays the wake up of p0' !!!
> !!! causes long idle on CPU0 !!!
> p2 => p0 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
> p0 wakes up p0'
>
> idle => p0'
>
>
>
> Since there are many waker/wakee pairs in the system, the chain reaction
> causes many CPUs to be victims. These idle CPUs wait for their waker to
> be scheduled.
>
> Actually Tiancheng has mentioned above issue here[2].
>
> [Proposal]
> The root cause is that there is no strict synchronization of select_task_rq()
> and the set of ttwu_pending flag among several CPUs. And this might be by
> design because the scheduler prefers parallel wakeup.
>
> So avoid this problem indirectly. If a system does not have idle cores,
> and if the waker and wakee are both short duration tasks, wake up the wakee on
> the same CPU as waker.
>
> The reason is that, if the waker is a short-duration task, it might
> relinquish the CPU soon, and the wakee has the chance to be scheduled.
> On the other hand, if the wakee is a short duration task, putting it on
> non-idle CPU would bring minimal impact to the running task. No idle
> core in the system indicates that this mechanism should not inhibit
> spreading the tasks if the system have idle core.
>
> [Benchmark results]
> The baseline is v6.1-rc6. The test platform has 56 Cores(112 CPUs) per
> LLC domain. C-states deeper than C1E are disabled. Turbo is disabled.
> CPU frequency governor is performance.
>
> will-it-scale.context_switch1
> =============================
> +331.13%
>
> hackbench
> =========
> case load baseline(std%) compare%( std%)
> process-pipe 1 group 1.00 ( 1.50) +0.83 ( 0.19)
> process-pipe 2 groups 1.00 ( 0.77) +0.82 ( 0.52)
> process-pipe 4 groups 1.00 ( 0.20) -2.07 ( 2.91)
> process-pipe 8 groups 1.00 ( 0.05) +3.48 ( 0.06)
> process-sockets 1 group 1.00 ( 2.90) -11.20 ( 11.99)
> process-sockets 2 groups 1.00 ( 5.42) -1.39 ( 1.70)
> process-sockets 4 groups 1.00 ( 0.17) -0.20 ( 0.19)
> process-sockets 8 groups 1.00 ( 0.03) -0.05 ( 0.11)
> threads-pipe 1 group 1.00 ( 2.09) -1.63 ( 0.44)
> threads-pipe 2 groups 1.00 ( 0.28) -0.21 ( 1.48)
> threads-pipe 4 groups 1.00 ( 0.27) +0.13 ( 0.63)
> threads-pipe 8 groups 1.00 ( 0.14) +5.04 ( 0.04)
> threads-sockets 1 group 1.00 ( 2.51) -1.86 ( 2.08)
> threads-sockets 2 groups 1.00 ( 1.24) -0.60 ( 3.83)
> threads-sockets 4 groups 1.00 ( 0.49) +0.07 ( 0.46)
> threads-sockets 8 groups 1.00 ( 0.09) -0.04 ( 0.08)
>
> netperf
> =======
> case load baseline(std%) compare%( std%)
> TCP_RR 28 threads 1.00 ( 0.81) -0.13 ( 0.80)
> TCP_RR 56 threads 1.00 ( 0.55) +0.03 ( 0.64)
> TCP_RR 84 threads 1.00 ( 0.33) +1.74 ( 0.31)
> TCP_RR 112 threads 1.00 ( 0.24) +3.71 ( 0.23)
> TCP_RR 140 threads 1.00 ( 0.21) +215.10 ( 12.37)
> TCP_RR 168 threads 1.00 ( 61.97) +86.15 ( 12.26)
> TCP_RR 196 threads 1.00 ( 14.49) +0.71 ( 14.20)
> TCP_RR 224 threads 1.00 ( 9.54) +0.68 ( 7.00)
> UDP_RR 28 threads 1.00 ( 1.51) +0.25 ( 1.02)
> UDP_RR 56 threads 1.00 ( 7.90) +0.57 ( 7.89)
> UDP_RR 84 threads 1.00 ( 6.38) +3.66 ( 20.77)
> UDP_RR 112 threads 1.00 ( 10.15) +3.16 ( 11.87)
> UDP_RR 140 threads 1.00 ( 9.98) +164.29 ( 12.55)
> UDP_RR 168 threads 1.00 ( 10.72) +174.41 ( 17.05)
> UDP_RR 196 threads 1.00 ( 18.84) +3.92 ( 15.48)
> UDP_RR 224 threads 1.00 ( 16.97) +2.98 ( 16.69)
>
> tbench
> ======
> case load baseline(std%) compare%( std%)
> loopback 28 threads 1.00 ( 0.12) -0.38 ( 0.35)
> loopback 56 threads 1.00 ( 0.17) -0.04 ( 0.19)
> loopback 84 threads 1.00 ( 0.03) +0.95 ( 0.07)
> loopback 112 threads 1.00 ( 0.03) +162.42 ( 0.05)
> loopback 140 threads 1.00 ( 0.14) -2.26 ( 0.14)
> loopback 168 threads 1.00 ( 0.49) -2.15 ( 0.54)
> loopback 196 threads 1.00 ( 0.06) -2.38 ( 0.22)
> loopback 224 threads 1.00 ( 0.20) -1.95 ( 0.30)
>
> schbench
> ========
> case load baseline(std%) compare%( std%)
> normal 1 mthread 1.00 ( 1.46) +1.03 ( 0.00)
> normal 2 mthreads 1.00 ( 3.82) -5.41 ( 8.37)
> normal 4 mthreads 1.00 ( 1.03) +5.11 ( 2.88)
> normal 8 mthreads 1.00 ( 2.96) -2.41 ( 0.93)
>
> In summary, overall there is no significant performance regression detected
> and there is a big improvement in netperf/tbench in partially-busy cases.
>
> [Limitations]
> As Peter said, the criteria of a short duration task is intuitive, but it
> seems to be hard to find an accurate criterion to describe this.
>
> This wake up strategy can be viewed as dynamic WF_SYNC. Except that:
> 1. Some workloads do not have WF_SYNC set.
> 2. WF_SYNC does not treat non-idle CPU as candidate target CPU.
>
> Peter has suggested[1] comparing task duration with the cost of searching
> for an idle CPU. If the latter is higher, then give up the scan, to
> achieve better task affine. However, this method does not fit in the case
> encountered in this patch. Because there are plenty of idle CPUs in the system,
> it will not take too long to find an idle CPU. The bottleneck is caused by the
> race condition mentioned above.
>
> [1] https://lore.kernel.org/lkml/Y2O8a%2FOhk1i1l8ao@hirez.programming.kicks-ass.net/
> [2] https://lore.kernel.org/lkml/9ed75cad-3718-356f-21ca-1b8ec601f335@linux.alibaba.com/
>
> Suggested-by: Tim Chen <tim.c.chen@intel.com>
> Suggested-by: K Prateek Nayak <kprateek.nayak@amd.com>
> Tested-by: kernel test robot <yujie.liu@intel.com>
> Signed-off-by: Chen Yu <yu.c.chen@intel.com>
> ---
> kernel/sched/fair.c | 10 ++++++++++
> 1 file changed, 10 insertions(+)
>
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index a4b314b664f8..3f7361ec1330 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -6246,6 +6246,11 @@ wake_affine_idle(int this_cpu, int prev_cpu, int sync)
> if (available_idle_cpu(prev_cpu))
> return prev_cpu;
>
> + /* The only running task is a short duration one. */
> + if (cpu_rq(this_cpu)->nr_running == 1 &&
> + is_short_task((struct task_struct *)cpu_curr(this_cpu)))
> + return this_cpu;
> +
Is it necessary to check the ttwu pending state here and below?
> return nr_cpumask_bits;
> }
>
> @@ -6612,6 +6617,11 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, bool
> time = cpu_clock(this);
> }
>
> + if (!has_idle_core && cpu_rq(target)->nr_running == 1 &&
> + is_short_task((struct task_struct *)cpu_curr(target)) &&
> + is_short_task(p))
> + return target;
> +
A short running task doesn't means a low utilization (you also mentioned in Patch 1/2).
So should we concern that we may overload the target?
btw, we're doing no scanning here so I may think it'll be more consistent to put this part
in select_idle_siblings(), considering we've already have some similiar judgement for the
prev_cpu, recent_used_cpu, etc. there.
Still doing some test, will reply the results once I get them.
Thanks,
Yicong
> if (sched_feat(SIS_UTIL)) {
> sd_share = rcu_dereference(per_cpu(sd_llc_shared, target));
> if (sd_share) {
>
Hi Yicong,
On 2022-12-06 at 21:02:11 +0800, Yicong Yang wrote:
[...]
> > +++ b/kernel/sched/fair.c
> > @@ -6246,6 +6246,11 @@ wake_affine_idle(int this_cpu, int prev_cpu, int sync)
> > if (available_idle_cpu(prev_cpu))
> > return prev_cpu;
> >
> > + /* The only running task is a short duration one. */
> > + if (cpu_rq(this_cpu)->nr_running == 1 &&
> > + is_short_task((struct task_struct *)cpu_curr(this_cpu)))
> > + return this_cpu;
> > +
>
> Is it necessary to check the ttwu pending state here and below?
>
My understanding is that, ttwu_pending will be set on this_cpu if
1) this_cpu is idle, or
2) waker on another LLC domain wants to wake up the wakee on this_cpu,
see ttwu_queue_cond().
For 1), the nr_running is 1, so it is not idle. For 2) the
chance to do a cross LLC wake up is relatively low with current patch
applied. Besides, I was trying to make this proposal a dynamic version
of WF_SYNC, since the latter does not check ttwu_pending, I did
not add this check as well.(for now)+
> > return nr_cpumask_bits;
> > }
> >
> > @@ -6612,6 +6617,11 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, bool
> > time = cpu_clock(this);
> > }
> >
> > + if (!has_idle_core && cpu_rq(target)->nr_running == 1 &&
> > + is_short_task((struct task_struct *)cpu_curr(target)) &&
> > + is_short_task(p))
> > + return target;
> > +
>
> A short running task doesn't means a low utilization (you also mentioned in Patch 1/2).
> So should we concern that we may overload the target?
>
The overloaded target might be expected in this case IMO. Because for a ping-pong scheduling
pair, we want to saturate the target CPU to eliminate the idle time. And this strategy
only takes effect when !has_idle_core.
> btw, we're doing no scanning here so I may think it'll be more consistent to put this part
> in select_idle_siblings(), considering we've already have some similiar judgement for the
> prev_cpu, recent_used_cpu, etc. there.
>
Got it, I can change it in next version.
> Still doing some test, will reply the results once I get them.
Thanks for the test, we can tune this patch when we have the data.
thanks,
Chenyu
>
> Thanks,
> Yicong
>
> > if (sched_feat(SIS_UTIL)) {
> > sd_share = rcu_dereference(per_cpu(sd_llc_shared, target));
> > if (sd_share) {
> >
Hi Chen.
On 2022/12/1 16:44, Chen Yu wrote:
> [Problem Statement]
> For a workload that is doing frequent context switches, the throughput
> scales well until the number of instances reaches a peak point. After
> that peak point, the throughput drops significantly if the number of
> instances continues to increase.
>
> The will-it-scale context_switch1 test case exposes the issue. The
> test platform has 112 CPUs per LLC domain. The will-it-scale launches
> 1, 8, 16 ... 112 instances respectively. Each instance is composed
> of 2 tasks, and each pair of tasks would do ping-pong scheduling via
> pipe_read() and pipe_write(). No task is bound to any CPU.
> It is found that, once the number of instances is higher than
> 56(112 tasks in total, every CPU has 1 task), the throughput
> drops accordingly if the instance number continues to increase:
>
> ^
> throughput|
> | X
> | X X X
> | X X X
> | X X
> | X X
> | X
> | X
> | X
> | X
> |
> +-----------------.------------------->
> 56
> number of instances
>
> [Symptom analysis]
>
> The performance downgrading was caused by a high system idle
> percentage(around 20% ~ 30%). The CPUs waste a lot of time in
> idle and do nothing. As a comparison, if set CPU affinity to
> these workloads and stops them from migrating among CPUs,
> the idle percentage drops to nearly 0%, and the throughput
> increases by about 300%. This indicates room for optimization.
>
> The reason for the high idle percentage is different before/after
> commit f3dd3f674555 ("sched: Remove the limitation of WF_ON_CPU
> on wakelist if wakee cpu is idle").
>
> [Before the commit]
> The bottleneck is the runqueue spinlock.
>
> nr_instance rq lock percentage
> 1 1.22%
> 8 1.17%
> 16 1.20%
> 24 1.22%
> 32 1.46%
> 40 1.61%
> 48 1.63%
> 56 1.65%
> --------------------------
> 64 3.77% |
> 72 5.90% | increase
> 80 7.95% |
> 88 9.98% v
> 96 11.81%
> 104 13.54%
> 112 15.13%
>
> And top 2 rq lock hot paths:
>
> (path1):
> raw_spin_rq_lock_nested.constprop.0;
> try_to_wake_up;
> default_wake_function;
> autoremove_wake_function;
> __wake_up_common;
> __wake_up_common_lock;
> __wake_up_sync_key;
> pipe_write;
> new_sync_write;
> vfs_write;
> ksys_write;
> __x64_sys_write;
> do_syscall_64;
> entry_SYSCALL_64_after_hwframe;write
>
> (path2):
> raw_spin_rq_lock_nested.constprop.0;
> __sched_text_start;
> schedule_idle;
> do_idle;
> cpu_startup_entry;
> start_secondary;
> secondary_startup_64_no_verify
>
> task A tries to wake up task B on CPU1, then task A grabs the
> runqueue lock of CPU1. If CPU1 is about to quit idle, it needs
> to grab its lock which has been taken by someone else. Then
> CPU1 takes more time to quit which hurts the performance.
>
> [After the commit]
> The cause is the race condition between select_task_rq() and
> the task enqueue.
>
> Suppose there are nr_cpus pairs of ping-pong scheduling
> tasks. For example, p0' and p0 are ping-pong scheduling,
> so do p1' <=> p1, and p2'<=> p2. None of these tasks are
> bound to any CPUs. The problem can be summarized as:
> more than 1 wakers are stacked on 1 CPU, which slows down
> waking up their wakees:
>
> CPU0 CPU1 CPU2
>
> p0' p1' => idle p2'
>
> try_to_wake_up(p0) try_to_wake_up(p2);
> CPU1 = select_task_rq(p0); CPU1 = select_task_rq(p2);
> ttwu_queue(p0, CPU1); ttwu_queue(p2, CPU1);
> __ttwu_queue_wakelist(p0, CPU1); => ttwu_list->p0
> quiting cpuidle_idle_call()
>
> ttwu_list->p2->p0 <= __ttwu_queue_wakelist(p2, CPU1);
>
> WRITE_ONCE(CPU1->ttwu_pending, 1); WRITE_ONCE(CPU1->ttwu_pending, 1);
>
> p0' => idle
> sched_ttwu_pending()
> enqueue_task(p2 and p0)
>
> idle => p2
>
> ...
> p2 time slice expires
> ...
> !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
> <=== !!! p2 delays the wake up of p0' !!!
> !!! causes long idle on CPU0 !!!
> p2 => p0 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
> p0 wakes up p0'
>
> idle => p0'
>
>
>
> Since there are many waker/wakee pairs in the system, the chain reaction
> causes many CPUs to be victims. These idle CPUs wait for their waker to
> be scheduled.
>
> Actually Tiancheng has mentioned above issue here[2].
>
First I want to say that this issue (race condition between selecting idle cpu
and enqueuing task) always exists before or after the commit f3dd3f674555. And I
know this is a big issue so in [2] I only try to fix a small part of it. Of
course I'm glad to see you trying solving this issue too :-)
There may be a bit wrong in your comment about the order.
"WRITE_ONCE(CPU1->ttwu_pending, 1);" on CPU0 is earlier than CPU1 getting
"ttwu_list->p0", right?
Thanks.
On 2022-12-05 at 10:36:25 +0800, Tianchen Ding wrote:
> Hi Chen.
>
> On 2022/12/1 16:44, Chen Yu wrote:
> > [Problem Statement]
> > For a workload that is doing frequent context switches, the throughput
> > scales well until the number of instances reaches a peak point. After
> > that peak point, the throughput drops significantly if the number of
> > instances continues to increase.
> >
> > The will-it-scale context_switch1 test case exposes the issue. The
> > test platform has 112 CPUs per LLC domain. The will-it-scale launches
> > 1, 8, 16 ... 112 instances respectively. Each instance is composed
> > of 2 tasks, and each pair of tasks would do ping-pong scheduling via
> > pipe_read() and pipe_write(). No task is bound to any CPU.
> > It is found that, once the number of instances is higher than
> > 56(112 tasks in total, every CPU has 1 task), the throughput
> > drops accordingly if the instance number continues to increase:
> >
> > ^
> > throughput|
> > | X
> > | X X X
> > | X X X
> > | X X
> > | X X
> > | X
> > | X
> > | X
> > | X
> > |
> > +-----------------.------------------->
> > 56
> > number of instances
> >
> > [Symptom analysis]
> >
> > The performance downgrading was caused by a high system idle
> > percentage(around 20% ~ 30%). The CPUs waste a lot of time in
> > idle and do nothing. As a comparison, if set CPU affinity to
> > these workloads and stops them from migrating among CPUs,
> > the idle percentage drops to nearly 0%, and the throughput
> > increases by about 300%. This indicates room for optimization.
> >
> > The reason for the high idle percentage is different before/after
> > commit f3dd3f674555 ("sched: Remove the limitation of WF_ON_CPU
> > on wakelist if wakee cpu is idle").
> >
> > [Before the commit]
> > The bottleneck is the runqueue spinlock.
> >
> > nr_instance rq lock percentage
> > 1 1.22%
> > 8 1.17%
> > 16 1.20%
> > 24 1.22%
> > 32 1.46%
> > 40 1.61%
> > 48 1.63%
> > 56 1.65%
> > --------------------------
> > 64 3.77% |
> > 72 5.90% | increase
> > 80 7.95% |
> > 88 9.98% v
> > 96 11.81%
> > 104 13.54%
> > 112 15.13%
> >
> > And top 2 rq lock hot paths:
> >
> > (path1):
> > raw_spin_rq_lock_nested.constprop.0;
> > try_to_wake_up;
> > default_wake_function;
> > autoremove_wake_function;
> > __wake_up_common;
> > __wake_up_common_lock;
> > __wake_up_sync_key;
> > pipe_write;
> > new_sync_write;
> > vfs_write;
> > ksys_write;
> > __x64_sys_write;
> > do_syscall_64;
> > entry_SYSCALL_64_after_hwframe;write
> >
> > (path2):
> > raw_spin_rq_lock_nested.constprop.0;
> > __sched_text_start;
> > schedule_idle;
> > do_idle;
> > cpu_startup_entry;
> > start_secondary;
> > secondary_startup_64_no_verify
> >
> > task A tries to wake up task B on CPU1, then task A grabs the
> > runqueue lock of CPU1. If CPU1 is about to quit idle, it needs
> > to grab its lock which has been taken by someone else. Then
> > CPU1 takes more time to quit which hurts the performance.
> >
> > [After the commit]
> > The cause is the race condition between select_task_rq() and
> > the task enqueue.
> >
> > Suppose there are nr_cpus pairs of ping-pong scheduling
> > tasks. For example, p0' and p0 are ping-pong scheduling,
> > so do p1' <=> p1, and p2'<=> p2. None of these tasks are
> > bound to any CPUs. The problem can be summarized as:
> > more than 1 wakers are stacked on 1 CPU, which slows down
> > waking up their wakees:
> >
> > CPU0 CPU1 CPU2
> >
> > p0' p1' => idle p2'
> >
> > try_to_wake_up(p0) try_to_wake_up(p2);
> > CPU1 = select_task_rq(p0); CPU1 = select_task_rq(p2);
> > ttwu_queue(p0, CPU1); ttwu_queue(p2, CPU1);
> > __ttwu_queue_wakelist(p0, CPU1); => ttwu_list->p0
> > quiting cpuidle_idle_call()
> >
> > ttwu_list->p2->p0 <= __ttwu_queue_wakelist(p2, CPU1);
> >
> > WRITE_ONCE(CPU1->ttwu_pending, 1); WRITE_ONCE(CPU1->ttwu_pending, 1);
> >
> > p0' => idle
> > sched_ttwu_pending()
> > enqueue_task(p2 and p0)
> >
> > idle => p2
> >
> > ...
> > p2 time slice expires
> > ...
> > !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
> > <=== !!! p2 delays the wake up of p0' !!!
> > !!! causes long idle on CPU0 !!!
> > p2 => p0 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
> > p0 wakes up p0'
> >
> > idle => p0'
> >
> >
> >
> > Since there are many waker/wakee pairs in the system, the chain reaction
> > causes many CPUs to be victims. These idle CPUs wait for their waker to
> > be scheduled.
> >
> > Actually Tiancheng has mentioned above issue here[2].
> >
>
> First I want to say that this issue (race condition between selecting idle
> cpu and enqueuing task) always exists before or after the commit
> f3dd3f674555. And I know this is a big issue so in [2] I only try to fix a
> small part of it. Of course I'm glad to see you trying solving this issue
> too :-)
>
> There may be a bit wrong in your comment about the order.
> "WRITE_ONCE(CPU1->ttwu_pending, 1);" on CPU0 is earlier than CPU1 getting
> "ttwu_list->p0", right?
>
Yes, you are right, I'll refine the comment.
thanks,
Chenyu
© 2016 - 2025 Red Hat, Inc.