* [RFC PATCH 0/2] Prioritize idle cpus over SCHED_IDLE ones
@ 2025-03-10 7:40 Abel Wu
2025-03-10 7:40 ` [RFC PATCH 1/2] Revert "sched/fair: Make sched-idle CPU selection consistent throughout" Abel Wu
` (3 more replies)
0 siblings, 4 replies; 15+ messages in thread
From: Abel Wu @ 2025-03-10 7:40 UTC (permalink / raw)
To: K Prateek Nayak, Ingo Molnar, Peter Zijlstra, Juri Lelli,
Vincent Guittot, Dietmar Eggemann, Steven Rostedt, Ben Segall,
Mel Gorman, Valentin Schneider, Josh Don, Tianchen Ding
Cc: Abel Wu, open list:SCHEDULER
Since commit
17346452b25b ("sched/fair: Make sched-idle CPU selection consistent")
the SCHED_IDLE cpus are given equal or more preference over idle ones in
fast- and slow-path of select_task_rq_fair(). This works well in flattened
cgroup hierarchy, e.g. all tasks running inside root cgroup, but may not
ideal in a deeper hierarchy where SCHED_IDLE doesn't mean anything between
entities whose parents are different. Hence a SCHED_IDLE cpu does NOT
necessarily implies any of the following:
- It is a less loaded cpu (since the parent of its topmost idle
ancestor could be a 'giant' entity with large cpu.weight).
- It can be expected to be preempted by a newly woken task soon
enough (which actually depends on their ancestors who have
common parent).
As a less loaded cpu probably has better ability to serve the newly
woken task, which also applies to the SCHED_IDLE cpus that less loaded
SCHED_IDLE cpu might be easier and faster preempted, let's not special
case SCHED_IDLE cpus at least in slowpath when selecting.
[ Plan to try the same in SIS, that is selecting a less loaded cpu
and get rid of ambiguous sched_idle_cpu(). Comments and suggests
are really appreciated. ]
Some benchmarks are tested in a Intel(R) Xeon(R) CPU E5-2650 v4 machine
based on tip/master ec3106906cbf, and are tested in following two setup:
(t1) (t2)
root root
/ \\ / \
benchmark noise benchmark X
\\
noise
where noise comes from a SCHED_IDLE cgroup. I didn't see an obvious diff
in hackbench or tbench, but not schbench.
vanilla-t1 patched-t1
Lat 50.0th-qrtle-1 8.00 ( 0.00%) 8.00 ( 0.00%)
Lat 90.0th-qrtle-1 13.00 ( 0.00%) 13.00 ( 0.00%)
Lat 99.0th-qrtle-1 19.00 ( 0.00%) 18.00 ( 5.26%)
Lat 99.9th-qrtle-1 22.00 ( 0.00%) 22.00 ( 0.00%)
Lat 20.0th-qrtle-1 257.00 ( 0.00%) 259.00 ( -0.78%)
Lat 50.0th-qrtle-2 8.00 ( 0.00%) 9.00 ( -12.50%)
Lat 90.0th-qrtle-2 13.00 ( 0.00%) 13.00 ( 0.00%)
Lat 99.0th-qrtle-2 19.00 ( 0.00%) 19.00 ( 0.00%)
Lat 99.9th-qrtle-2 23.00 ( 0.00%) 24.00 ( -4.35%)
Lat 20.0th-qrtle-2 484.00 ( 0.00%) 434.00 ( 10.33%)
Lat 50.0th-qrtle-4 9.00 ( 0.00%) 9.00 ( 0.00%)
Lat 90.0th-qrtle-4 14.00 ( 0.00%) 14.00 ( 0.00%)
Lat 99.0th-qrtle-4 19.00 ( 0.00%) 19.00 ( 0.00%)
Lat 99.9th-qrtle-4 25.00 ( 0.00%) 24.00 ( 4.00%)
Lat 20.0th-qrtle-4 877.00 ( 0.00%) 857.00 ( 2.28%)
Lat 50.0th-qrtle-8 9.00 ( 0.00%) 9.00 ( 0.00%)
Lat 90.0th-qrtle-8 14.00 ( 0.00%) 15.00 ( -7.14%)
Lat 99.0th-qrtle-8 20.00 ( 0.00%) 21.00 ( -5.00%)
Lat 99.9th-qrtle-8 26.00 ( 0.00%) 26.00 ( 0.00%)
Lat 20.0th-qrtle-8 1698.00 ( 0.00%) 1598.00 ( 5.89%)
Lat 50.0th-qrtle-16 10.00 ( 0.00%) 10.00 ( 0.00%)
Lat 90.0th-qrtle-16 15.00 ( 0.00%) 15.00 ( 0.00%)
Lat 99.0th-qrtle-16 20.00 ( 0.00%) 20.00 ( 0.00%)
Lat 99.9th-qrtle-16 28.00 ( 0.00%) 27.00 ( 3.57%)
Lat 20.0th-qrtle-16 2900.00 ( 0.00%) 2860.00 ( 1.38%)
Lat 50.0th-qrtle-23 9.00 ( 0.00%) 9.00 ( 0.00%)
Lat 90.0th-qrtle-23 15.00 ( 0.00%) 15.00 ( 0.00%)
Lat 99.0th-qrtle-23 49.00 ( 0.00%) 28.00 ( 42.86%)
Lat 99.9th-qrtle-23 1602.00 ( 0.00%) 1458.00 ( 8.99%)
Lat 20.0th-qrtle-23 3796.00 ( 0.00%) 3804.00 ( -0.21%)
vanilla-t2 patched-t2
Lat 50.0th-qrtle-1 10.00 ( 0.00%) 9.00 ( 10.00%)
Lat 90.0th-qrtle-1 271.00 ( 0.00%) 272.00 ( -0.37%)
Lat 99.0th-qrtle-1 1013.00 ( 0.00%) 793.00 ( 21.72%)
Lat 99.9th-qrtle-1 1998.00 ( 0.00%) 1642.00 ( 17.82%)
Lat 20.0th-qrtle-1 262.00 ( 0.00%) 262.00 ( 0.00%)
Lat 50.0th-qrtle-2 10.00 ( 0.00%) 9.00 ( 10.00%)
Lat 90.0th-qrtle-2 531.00 ( 0.00%) 510.00 ( 3.95%)
Lat 99.0th-qrtle-2 1034.00 ( 0.00%) 933.00 ( 9.77%)
Lat 99.9th-qrtle-2 1846.00 ( 0.00%) 1614.00 ( 12.57%)
Lat 20.0th-qrtle-2 517.00 ( 0.00%) 517.00 ( 0.00%)
Lat 50.0th-qrtle-4 10.00 ( 0.00%) 10.00 ( 0.00%)
Lat 90.0th-qrtle-4 523.00 ( 0.00%) 494.00 ( 5.54%)
Lat 99.0th-qrtle-4 973.00 ( 0.00%) 901.00 ( 7.40%)
Lat 99.9th-qrtle-4 1618.00 ( 0.00%) 1606.00 ( 0.74%)
Lat 20.0th-qrtle-4 1015.00 ( 0.00%) 1001.00 ( 1.38%)
Lat 50.0th-qrtle-8 11.00 ( 0.00%) 10.00 ( 9.09%)
Lat 90.0th-qrtle-8 527.00 ( 0.00%) 454.00 ( 13.85%)
Lat 99.0th-qrtle-8 931.00 ( 0.00%) 901.00 ( 3.22%)
Lat 99.9th-qrtle-8 1598.00 ( 0.00%) 1582.00 ( 1.00%)
Lat 20.0th-qrtle-8 1738.00 ( 0.00%) 1666.00 ( 4.14%)
Lat 50.0th-qrtle-16 9.00 ( 0.00%) 9.00 ( 0.00%)
Lat 90.0th-qrtle-16 410.00 ( 0.00%) 243.00 ( 40.73%)
Lat 99.0th-qrtle-16 979.00 ( 0.00%) 891.00 ( 8.99%)
Lat 99.9th-qrtle-16 1486.00 ( 0.00%) 1470.00 ( 1.08%)
Lat 20.0th-qrtle-16 2708.00 ( 0.00%) 2708.00 ( 0.00%)
Lat 50.0th-qrtle-23 8.00 ( 0.00%) 9.00 ( -12.50%)
Lat 90.0th-qrtle-23 454.00 ( 0.00%) 303.00 ( 33.26%)
Lat 99.0th-qrtle-23 3228.00 ( 0.00%) 2564.00 ( 20.57%)
Lat 99.9th-qrtle-23 5496.00 ( 0.00%) 5304.00 ( 3.49%)
Lat 20.0th-qrtle-23 3132.00 ( 0.00%) 3156.00 ( -0.77%)
Abel Wu (2):
Revert "sched/fair: Make sched-idle CPU selection consistent throughout"
sched/fair: Do not specialcase SCHED_IDLE cpus in select slowpath
kernel/sched/fair.c | 40 ++++++++++++++++++++++++----------------
1 file changed, 24 insertions(+), 16 deletions(-)
--
2.37.3
^ permalink raw reply [flat|nested] 15+ messages in thread
* [RFC PATCH 1/2] Revert "sched/fair: Make sched-idle CPU selection consistent throughout"
2025-03-10 7:40 [RFC PATCH 0/2] Prioritize idle cpus over SCHED_IDLE ones Abel Wu
@ 2025-03-10 7:40 ` Abel Wu
2025-03-11 16:58 ` Vincent Guittot
2025-03-10 7:40 ` [RFC PATCH 2/2] sched/fair: Do not specialcase SCHED_IDLE cpus in select slowpath Abel Wu
` (2 subsequent siblings)
3 siblings, 1 reply; 15+ messages in thread
From: Abel Wu @ 2025-03-10 7:40 UTC (permalink / raw)
To: K Prateek Nayak, Ingo Molnar, Peter Zijlstra, Juri Lelli,
Vincent Guittot, Dietmar Eggemann, Steven Rostedt, Ben Segall,
Mel Gorman, Valentin Schneider, Josh Don, Tianchen Ding
Cc: Abel Wu, open list:SCHEDULER
This reverts commit 17346452b25b98acfb395d2a82ec2e4ad0cb7a01.
The above commit tried to unify selection policy between idle cpus
and SCHED_IDLE ones in fast- and slow-path of select_task_rq_fair()
by treating them equally (although the SCHED_IDLE cpus are turned
to be given more preference in slowpath). The test results seemed
solid, but the setup didn't take cgroup hierarchy into account,
which actually made some of our important services get affected.
The cgroup hierarchy in our production environment looks like below,
which might be common in modern containerized setup:
root
/ \
kubepods system.slice
/ \\ \
guaranteed besteffort containerd
(where 'X=A' means A is SCHED_IDLE cgroup)
The cpu is treated as SCHED_IDLE if only besteffort is running, which
is given at least equal preference as the idle cpus when deciding where
to run a newly woken task. But the SCHED_IDLE cpus do not necessarily
mean they can be preempted soon enough to start serving the wakee, and
containerd and other services under system.slice are the case that have
to wait in runqueue since they can not preempt kubepods, while idle cpus
are possible out there untouched.
So prioritize idle cpus over SCHED_IDLE ones to avoid undesired delay
like orchestration operations as much as possible.
Signed-off-by: Abel Wu <wuyun.abel@bytedance.com>
---
kernel/sched/fair.c | 49 +++++++++++++++++++++++++++------------------
1 file changed, 30 insertions(+), 19 deletions(-)
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index ae0350088ac1..379764bd2795 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -7446,7 +7446,7 @@ sched_balance_find_dst_group_cpu(struct sched_group *group, struct task_struct *
unsigned int min_exit_latency = UINT_MAX;
u64 latest_idle_timestamp = 0;
int least_loaded_cpu = this_cpu;
- int shallowest_idle_cpu = -1;
+ int shallowest_idle_cpu = -1, si_cpu = -1;
int i;
/* Check if we have any choice: */
@@ -7460,9 +7460,6 @@ sched_balance_find_dst_group_cpu(struct sched_group *group, struct task_struct *
if (!sched_core_cookie_match(rq, p))
continue;
- if (sched_idle_cpu(i))
- return i;
-
if (available_idle_cpu(i)) {
struct cpuidle_state *idle = idle_get_state(rq);
if (idle && idle->exit_latency < min_exit_latency) {
@@ -7484,7 +7481,12 @@ sched_balance_find_dst_group_cpu(struct sched_group *group, struct task_struct *
latest_idle_timestamp = rq->idle_stamp;
shallowest_idle_cpu = i;
}
- } else if (shallowest_idle_cpu == -1) {
+ } else if (shallowest_idle_cpu == -1 && si_cpu == -1) {
+ if (sched_idle_cpu(i)) {
+ si_cpu = i;
+ continue;
+ }
+
load = cpu_load(cpu_rq(i));
if (load < min_load) {
min_load = load;
@@ -7493,7 +7495,11 @@ sched_balance_find_dst_group_cpu(struct sched_group *group, struct task_struct *
}
}
- return shallowest_idle_cpu != -1 ? shallowest_idle_cpu : least_loaded_cpu;
+ if (shallowest_idle_cpu != -1)
+ return shallowest_idle_cpu;
+ if (si_cpu != -1)
+ return si_cpu;
+ return least_loaded_cpu;
}
static inline int sched_balance_find_dst_cpu(struct sched_domain *sd, struct task_struct *p,
@@ -7549,11 +7555,14 @@ static inline int sched_balance_find_dst_cpu(struct sched_domain *sd, struct tas
return new_cpu;
}
-static inline int __select_idle_cpu(int cpu, struct task_struct *p)
+static inline int __select_idle_cpu(int cpu, struct task_struct *p, int *si_cpu)
{
- if ((available_idle_cpu(cpu) || sched_idle_cpu(cpu)) &&
- sched_cpu_cookie_match(cpu_rq(cpu), p))
+ if (!sched_cpu_cookie_match(cpu_rq(cpu), p))
+ return -1;
+ if (available_idle_cpu(cpu))
return cpu;
+ if (*si_cpu == -1 && sched_idle_cpu(cpu))
+ *si_cpu = cpu;
return -1;
}
@@ -7649,7 +7658,7 @@ static int select_idle_core(struct task_struct *p, int core, struct cpumask *cpu
*/
static int select_idle_smt(struct task_struct *p, struct sched_domain *sd, int target)
{
- int cpu;
+ int cpu, si_cpu = -1;
for_each_cpu_and(cpu, cpu_smt_mask(target), p->cpus_ptr) {
if (cpu == target)
@@ -7660,11 +7669,13 @@ static int select_idle_smt(struct task_struct *p, struct sched_domain *sd, int t
*/
if (!cpumask_test_cpu(cpu, sched_domain_span(sd)))
continue;
- if (available_idle_cpu(cpu) || sched_idle_cpu(cpu))
+ if (available_idle_cpu(cpu))
return cpu;
+ if (si_cpu == -1 && sched_idle_cpu(cpu))
+ si_cpu = cpu;
}
- return -1;
+ return si_cpu;
}
#else /* CONFIG_SCHED_SMT */
@@ -7680,7 +7691,7 @@ static inline bool test_idle_cores(int cpu)
static inline int select_idle_core(struct task_struct *p, int core, struct cpumask *cpus, int *idle_cpu)
{
- return __select_idle_cpu(core, p);
+ return __select_idle_cpu(core, p, idle_cpu);
}
static inline int select_idle_smt(struct task_struct *p, struct sched_domain *sd, int target)
@@ -7728,10 +7739,10 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, bool
return i;
} else {
if (--nr <= 0)
- return -1;
- idle_cpu = __select_idle_cpu(cpu, p);
- if ((unsigned int)idle_cpu < nr_cpumask_bits)
return idle_cpu;
+ i = __select_idle_cpu(cpu, p, &idle_cpu);
+ if ((unsigned int)i < nr_cpumask_bits)
+ return i;
}
}
cpumask_andnot(cpus, cpus, sched_group_span(sg));
@@ -7746,9 +7757,9 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, bool
} else {
if (--nr <= 0)
- return -1;
- idle_cpu = __select_idle_cpu(cpu, p);
- if ((unsigned int)idle_cpu < nr_cpumask_bits)
+ return idle_cpu;
+ i = __select_idle_cpu(cpu, p, &idle_cpu);
+ if ((unsigned int)i < nr_cpumask_bits)
break;
}
}
--
2.37.3
^ permalink raw reply [flat|nested] 15+ messages in thread
* [RFC PATCH 2/2] sched/fair: Do not specialcase SCHED_IDLE cpus in select slowpath
2025-03-10 7:40 [RFC PATCH 0/2] Prioritize idle cpus over SCHED_IDLE ones Abel Wu
2025-03-10 7:40 ` [RFC PATCH 1/2] Revert "sched/fair: Make sched-idle CPU selection consistent throughout" Abel Wu
@ 2025-03-10 7:40 ` Abel Wu
2025-03-10 22:38 ` Josh Don
2025-03-10 8:25 ` [RFC PATCH 0/2] Prioritize idle cpus over SCHED_IDLE ones Abel Wu
2025-03-19 6:52 ` Abel Wu
3 siblings, 1 reply; 15+ messages in thread
From: Abel Wu @ 2025-03-10 7:40 UTC (permalink / raw)
To: K Prateek Nayak, Ingo Molnar, Peter Zijlstra, Juri Lelli,
Vincent Guittot, Dietmar Eggemann, Steven Rostedt, Ben Segall,
Mel Gorman, Valentin Schneider, Josh Don, Tianchen Ding
Cc: Abel Wu, open list:SCHEDULER
The SCHED_IDLE cgroups whose cpu.idle equals to 1, only mean something
to their siblings due to cgroup hierarchical behavior. So a SCHED_IDLE
cpu does NOT necessarily implies any of the following:
- It is a less loaded cpu (since the parent of its topmost idle
ancestor could be a 'giant' entity with large cpu.weight).
- It can be expected to be preempted by a newly woken task soon
enough (which actually depends on their ancestors who have
common parent).
As a less loaded cpu probably has better ability to serve the newly
woken task, which also applies to the SCHED_IDLE cpus that less loaded
SCHED_IDLE cpu might be easier and faster preempted, let's not special
case SCHED_IDLE cpus at least in slowpath when selecting.
Signed-off-by: Abel Wu <wuyun.abel@bytedance.com>
---
kernel/sched/fair.c | 21 +++++++++------------
1 file changed, 9 insertions(+), 12 deletions(-)
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 379764bd2795..769505cf519b 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -7446,7 +7446,7 @@ sched_balance_find_dst_group_cpu(struct sched_group *group, struct task_struct *
unsigned int min_exit_latency = UINT_MAX;
u64 latest_idle_timestamp = 0;
int least_loaded_cpu = this_cpu;
- int shallowest_idle_cpu = -1, si_cpu = -1;
+ int shallowest_idle_cpu = -1;
int i;
/* Check if we have any choice: */
@@ -7481,12 +7481,13 @@ sched_balance_find_dst_group_cpu(struct sched_group *group, struct task_struct *
latest_idle_timestamp = rq->idle_stamp;
shallowest_idle_cpu = i;
}
- } else if (shallowest_idle_cpu == -1 && si_cpu == -1) {
- if (sched_idle_cpu(i)) {
- si_cpu = i;
- continue;
- }
-
+ } else if (shallowest_idle_cpu == -1) {
+ /*
+ * The SCHED_IDLE cpus do not necessarily means anything
+ * to @p due to the cgroup hierarchical behavior. But it
+ * is almost certain that the wakee will get better served
+ * if the cpu is less loaded.
+ */
load = cpu_load(cpu_rq(i));
if (load < min_load) {
min_load = load;
@@ -7495,11 +7496,7 @@ sched_balance_find_dst_group_cpu(struct sched_group *group, struct task_struct *
}
}
- if (shallowest_idle_cpu != -1)
- return shallowest_idle_cpu;
- if (si_cpu != -1)
- return si_cpu;
- return least_loaded_cpu;
+ return shallowest_idle_cpu != -1 ? shallowest_idle_cpu : least_loaded_cpu;
}
static inline int sched_balance_find_dst_cpu(struct sched_domain *sd, struct task_struct *p,
--
2.37.3
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [RFC PATCH 0/2] Prioritize idle cpus over SCHED_IDLE ones
2025-03-10 7:40 [RFC PATCH 0/2] Prioritize idle cpus over SCHED_IDLE ones Abel Wu
2025-03-10 7:40 ` [RFC PATCH 1/2] Revert "sched/fair: Make sched-idle CPU selection consistent throughout" Abel Wu
2025-03-10 7:40 ` [RFC PATCH 2/2] sched/fair: Do not specialcase SCHED_IDLE cpus in select slowpath Abel Wu
@ 2025-03-10 8:25 ` Abel Wu
2025-03-19 6:52 ` Abel Wu
3 siblings, 0 replies; 15+ messages in thread
From: Abel Wu @ 2025-03-10 8:25 UTC (permalink / raw)
To: K Prateek Nayak, Ingo Molnar, Peter Zijlstra, Juri Lelli,
Vincent Guittot, Dietmar Eggemann, Steven Rostedt, Ben Segall,
Mel Gorman, Valentin Schneider, Josh Don, Tianchen Ding,
Viresh Kumar
Cc: open list:SCHEDULER
loop Viresh Kumar
On 3/10/25 3:40 PM, Abel Wu wrote:
> Since commit
>
> 17346452b25b ("sched/fair: Make sched-idle CPU selection consistent")
>
> the SCHED_IDLE cpus are given equal or more preference over idle ones in
> fast- and slow-path of select_task_rq_fair(). This works well in flattened
> cgroup hierarchy, e.g. all tasks running inside root cgroup, but may not
> ideal in a deeper hierarchy where SCHED_IDLE doesn't mean anything between
> entities whose parents are different. Hence a SCHED_IDLE cpu does NOT
> necessarily implies any of the following:
>
> - It is a less loaded cpu (since the parent of its topmost idle
> ancestor could be a 'giant' entity with large cpu.weight).
>
> - It can be expected to be preempted by a newly woken task soon
> enough (which actually depends on their ancestors who have
> common parent).
>
> As a less loaded cpu probably has better ability to serve the newly
> woken task, which also applies to the SCHED_IDLE cpus that less loaded
> SCHED_IDLE cpu might be easier and faster preempted, let's not special
> case SCHED_IDLE cpus at least in slowpath when selecting.
>
> [ Plan to try the same in SIS, that is selecting a less loaded cpu
> and get rid of ambiguous sched_idle_cpu(). Comments and suggests
> are really appreciated. ]
>
> Some benchmarks are tested in a Intel(R) Xeon(R) CPU E5-2650 v4 machine
> based on tip/master ec3106906cbf, and are tested in following two setup:
>
> (t1) (t2)
> root root
> / \\ / \
> benchmark noise benchmark X
> \\
> noise
>
> where noise comes from a SCHED_IDLE cgroup. I didn't see an obvious diff
> in hackbench or tbench, but not schbench.
>
> vanilla-t1 patched-t1
> Lat 50.0th-qrtle-1 8.00 ( 0.00%) 8.00 ( 0.00%)
> Lat 90.0th-qrtle-1 13.00 ( 0.00%) 13.00 ( 0.00%)
> Lat 99.0th-qrtle-1 19.00 ( 0.00%) 18.00 ( 5.26%)
> Lat 99.9th-qrtle-1 22.00 ( 0.00%) 22.00 ( 0.00%)
> Lat 20.0th-qrtle-1 257.00 ( 0.00%) 259.00 ( -0.78%)
> Lat 50.0th-qrtle-2 8.00 ( 0.00%) 9.00 ( -12.50%)
> Lat 90.0th-qrtle-2 13.00 ( 0.00%) 13.00 ( 0.00%)
> Lat 99.0th-qrtle-2 19.00 ( 0.00%) 19.00 ( 0.00%)
> Lat 99.9th-qrtle-2 23.00 ( 0.00%) 24.00 ( -4.35%)
> Lat 20.0th-qrtle-2 484.00 ( 0.00%) 434.00 ( 10.33%)
> Lat 50.0th-qrtle-4 9.00 ( 0.00%) 9.00 ( 0.00%)
> Lat 90.0th-qrtle-4 14.00 ( 0.00%) 14.00 ( 0.00%)
> Lat 99.0th-qrtle-4 19.00 ( 0.00%) 19.00 ( 0.00%)
> Lat 99.9th-qrtle-4 25.00 ( 0.00%) 24.00 ( 4.00%)
> Lat 20.0th-qrtle-4 877.00 ( 0.00%) 857.00 ( 2.28%)
> Lat 50.0th-qrtle-8 9.00 ( 0.00%) 9.00 ( 0.00%)
> Lat 90.0th-qrtle-8 14.00 ( 0.00%) 15.00 ( -7.14%)
> Lat 99.0th-qrtle-8 20.00 ( 0.00%) 21.00 ( -5.00%)
> Lat 99.9th-qrtle-8 26.00 ( 0.00%) 26.00 ( 0.00%)
> Lat 20.0th-qrtle-8 1698.00 ( 0.00%) 1598.00 ( 5.89%)
> Lat 50.0th-qrtle-16 10.00 ( 0.00%) 10.00 ( 0.00%)
> Lat 90.0th-qrtle-16 15.00 ( 0.00%) 15.00 ( 0.00%)
> Lat 99.0th-qrtle-16 20.00 ( 0.00%) 20.00 ( 0.00%)
> Lat 99.9th-qrtle-16 28.00 ( 0.00%) 27.00 ( 3.57%)
> Lat 20.0th-qrtle-16 2900.00 ( 0.00%) 2860.00 ( 1.38%)
> Lat 50.0th-qrtle-23 9.00 ( 0.00%) 9.00 ( 0.00%)
> Lat 90.0th-qrtle-23 15.00 ( 0.00%) 15.00 ( 0.00%)
> Lat 99.0th-qrtle-23 49.00 ( 0.00%) 28.00 ( 42.86%)
> Lat 99.9th-qrtle-23 1602.00 ( 0.00%) 1458.00 ( 8.99%)
> Lat 20.0th-qrtle-23 3796.00 ( 0.00%) 3804.00 ( -0.21%)
>
> vanilla-t2 patched-t2
> Lat 50.0th-qrtle-1 10.00 ( 0.00%) 9.00 ( 10.00%)
> Lat 90.0th-qrtle-1 271.00 ( 0.00%) 272.00 ( -0.37%)
> Lat 99.0th-qrtle-1 1013.00 ( 0.00%) 793.00 ( 21.72%)
> Lat 99.9th-qrtle-1 1998.00 ( 0.00%) 1642.00 ( 17.82%)
> Lat 20.0th-qrtle-1 262.00 ( 0.00%) 262.00 ( 0.00%)
> Lat 50.0th-qrtle-2 10.00 ( 0.00%) 9.00 ( 10.00%)
> Lat 90.0th-qrtle-2 531.00 ( 0.00%) 510.00 ( 3.95%)
> Lat 99.0th-qrtle-2 1034.00 ( 0.00%) 933.00 ( 9.77%)
> Lat 99.9th-qrtle-2 1846.00 ( 0.00%) 1614.00 ( 12.57%)
> Lat 20.0th-qrtle-2 517.00 ( 0.00%) 517.00 ( 0.00%)
> Lat 50.0th-qrtle-4 10.00 ( 0.00%) 10.00 ( 0.00%)
> Lat 90.0th-qrtle-4 523.00 ( 0.00%) 494.00 ( 5.54%)
> Lat 99.0th-qrtle-4 973.00 ( 0.00%) 901.00 ( 7.40%)
> Lat 99.9th-qrtle-4 1618.00 ( 0.00%) 1606.00 ( 0.74%)
> Lat 20.0th-qrtle-4 1015.00 ( 0.00%) 1001.00 ( 1.38%)
> Lat 50.0th-qrtle-8 11.00 ( 0.00%) 10.00 ( 9.09%)
> Lat 90.0th-qrtle-8 527.00 ( 0.00%) 454.00 ( 13.85%)
> Lat 99.0th-qrtle-8 931.00 ( 0.00%) 901.00 ( 3.22%)
> Lat 99.9th-qrtle-8 1598.00 ( 0.00%) 1582.00 ( 1.00%)
> Lat 20.0th-qrtle-8 1738.00 ( 0.00%) 1666.00 ( 4.14%)
> Lat 50.0th-qrtle-16 9.00 ( 0.00%) 9.00 ( 0.00%)
> Lat 90.0th-qrtle-16 410.00 ( 0.00%) 243.00 ( 40.73%)
> Lat 99.0th-qrtle-16 979.00 ( 0.00%) 891.00 ( 8.99%)
> Lat 99.9th-qrtle-16 1486.00 ( 0.00%) 1470.00 ( 1.08%)
> Lat 20.0th-qrtle-16 2708.00 ( 0.00%) 2708.00 ( 0.00%)
> Lat 50.0th-qrtle-23 8.00 ( 0.00%) 9.00 ( -12.50%)
> Lat 90.0th-qrtle-23 454.00 ( 0.00%) 303.00 ( 33.26%)
> Lat 99.0th-qrtle-23 3228.00 ( 0.00%) 2564.00 ( 20.57%)
> Lat 99.9th-qrtle-23 5496.00 ( 0.00%) 5304.00 ( 3.49%)
> Lat 20.0th-qrtle-23 3132.00 ( 0.00%) 3156.00 ( -0.77%)
>
> Abel Wu (2):
> Revert "sched/fair: Make sched-idle CPU selection consistent throughout"
> sched/fair: Do not specialcase SCHED_IDLE cpus in select slowpath
>
> kernel/sched/fair.c | 40 ++++++++++++++++++++++++----------------
> 1 file changed, 24 insertions(+), 16 deletions(-)
>
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [RFC PATCH 2/2] sched/fair: Do not specialcase SCHED_IDLE cpus in select slowpath
2025-03-10 7:40 ` [RFC PATCH 2/2] sched/fair: Do not specialcase SCHED_IDLE cpus in select slowpath Abel Wu
@ 2025-03-10 22:38 ` Josh Don
2025-03-11 16:43 ` Abel Wu
0 siblings, 1 reply; 15+ messages in thread
From: Josh Don @ 2025-03-10 22:38 UTC (permalink / raw)
To: Abel Wu
Cc: K Prateek Nayak, Ingo Molnar, Peter Zijlstra, Juri Lelli,
Vincent Guittot, Dietmar Eggemann, Steven Rostedt, Ben Segall,
Mel Gorman, Valentin Schneider, Tianchen Ding,
open list:SCHEDULER
Thanks Abel,
> @@ -7481,12 +7481,13 @@ sched_balance_find_dst_group_cpu(struct sched_group *group, struct task_struct *
> latest_idle_timestamp = rq->idle_stamp;
> shallowest_idle_cpu = i;
> }
> - } else if (shallowest_idle_cpu == -1 && si_cpu == -1) {
> - if (sched_idle_cpu(i)) {
> - si_cpu = i;
> - continue;
> - }
> -
> + } else if (shallowest_idle_cpu == -1) {
> + /*
> + * The SCHED_IDLE cpus do not necessarily means anything
> + * to @p due to the cgroup hierarchical behavior. But it
> + * is almost certain that the wakee will get better served
> + * if the cpu is less loaded.
> + */
> load = cpu_load(cpu_rq(i));
> if (load < min_load) {
> min_load = load;
This seems reasonable due to the case you describe. However, I'm
wondering if you considered any heuristics here to help identify when
a target cpu should really be considered sched_idle from the
perspective of the incoming task. For example, in your cgroup
hierarchy, if you have a cpu currently only running tasks in your
besteffort container (and all cpus in the system are busy running
something), then that cpu should be considered as a good target for a
waking task in the "guaranteed" container, and not a good target for a
waking task in the "containerd" container. A simple way to do this
would be to do a find_matching_se on the incoming task and the current
on_cpu task. That does have a drawback of cgroup pointer chasing in a
hot wakeup path, so I don't love it.
In any case, I'm fine with the change as-is, mostly curious if you
gave any additional thought to the case mentioned above.
Best,
Josh
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: Re: [RFC PATCH 2/2] sched/fair: Do not specialcase SCHED_IDLE cpus in select slowpath
2025-03-10 22:38 ` Josh Don
@ 2025-03-11 16:43 ` Abel Wu
2025-03-12 19:24 ` Josh Don
0 siblings, 1 reply; 15+ messages in thread
From: Abel Wu @ 2025-03-11 16:43 UTC (permalink / raw)
To: Josh Don
Cc: K Prateek Nayak, Ingo Molnar, Peter Zijlstra, Juri Lelli,
Vincent Guittot, Dietmar Eggemann, Steven Rostedt, Ben Segall,
Mel Gorman, Valentin Schneider, Tianchen Ding,
open list:SCHEDULER, Viresh Kumar
Hi Josh,
On 3/11/25 6:38 AM, Josh Don wrote:
> Thanks Abel,
>
>> @@ -7481,12 +7481,13 @@ sched_balance_find_dst_group_cpu(struct sched_group *group, struct task_struct *
>> latest_idle_timestamp = rq->idle_stamp;
>> shallowest_idle_cpu = i;
>> }
>> - } else if (shallowest_idle_cpu == -1 && si_cpu == -1) {
>> - if (sched_idle_cpu(i)) {
>> - si_cpu = i;
>> - continue;
>> - }
>> -
>> + } else if (shallowest_idle_cpu == -1) {
>> + /*
>> + * The SCHED_IDLE cpus do not necessarily means anything
>> + * to @p due to the cgroup hierarchical behavior. But it
>> + * is almost certain that the wakee will get better served
>> + * if the cpu is less loaded.
>> + */
>> load = cpu_load(cpu_rq(i));
>> if (load < min_load) {
>> min_load = load;
>
> This seems reasonable due to the case you describe. However, I'm
> wondering if you considered any heuristics here to help identify when
> a target cpu should really be considered sched_idle from the
> perspective of the incoming task. For example, in your cgroup
> hierarchy, if you have a cpu currently only running tasks in your
> besteffort container (and all cpus in the system are busy running
> something), then that cpu should be considered as a good target for a
> waking task in the "guaranteed" container, and not a good target for a
> waking task in the "containerd" container. A simple way to do this
Yes, it actually did cost me several days trying hard to figure out
whether there is a proper way to achieve what you're suggesting.
Solution A
----------
Mark all the hierarchically idle task_groups by assigning a unique
prime, and define a tree walk starts from @n to root that contains
all the preemptable nodes.
struct task_group {
/*
* Set to a unique prime if at least 1 ancestor is idle,
* otherwise set to 1.
*/
u64 prime;
u64 mul;
};
/* Called by sched_group_set_idle() */
static void calculate_mul(struct task_group *tg)
{
struct task_group *curr, *iter;
lockdep_assert_held(&shares_mutex);
for (curr = tg; curr->parent; curr = curr->parent) {
list_for_each_entry(iter, &curr->parent->children, siblings) {
/* Can't preempt non-idle siblings */
if (!iter->idle)
continue;
/*
* For each node in the subtree rooted at @iter do:
* tg->mul *= node->prime;
*/
traverse_subtree(tg, iter);
}
}
}
int sched_idle_cpu(int cpu, struct task_struct *p)
{
/* rq::cached_mul caches rq->donor's tg::mul */
return p->sched_task_group.mul % cpu_rq(cpu)->cached_mul == 0;
}
With this we even can drop find_matching_se(), since it's quite easy
to know whether or not a sched_entity can preempt another. But sadly
task_group::mul will quickly get overflowed.
Solution B
----------
Since we do not require 100% accurate, solution A can be shifted to
using bloom filters.
struct task_group {
u64 key; /* A random number used for hashing */
u64 filter;
};
/* Called by sched_group_set_idle() */
static void calculate_filter(struct task_group *tg)
{
struct task_group *curr, *iter;
lockdep_assert_held(&shares_mutex);
for (curr = tg; curr->parent; curr = curr->parent) {
list_for_each_entry(iter, &curr->parent->children, siblings) {
/* Can't preempt non-idle siblings */
if (!iter->idle)
continue;
/*
* For each node in the subtree rooted at @iter do:
* set_bit(bloom_hash(node->key), &tg->filter);
*/
traverse_subtree(tg, iter);
}
}
}
int sched_idle_cpu(int cpu, struct task_struct *p)
{
u64 filter = p->sched_task_group.filter;
u64 cached = cpu_rq(cpu)->cached_filter;
return filter & cached == cached;
}
False positives are possible, but the possibility can be reduced by
optimizing blooming setup.
I chose the simplest way for now to workaround the issue we encountered,
while I am still trying to do something to get rid of sched_idle_cpu().
Thoughts?
> would be to do a find_matching_se on the incoming task and the current
> on_cpu task. That does have a drawback of cgroup pointer chasing in a
> hot wakeup path, so I don't love it.
Neither do I. But if we go through find_matching_se(), I think we need
this rq locked.
>
> In any case, I'm fine with the change as-is, mostly curious if you
> gave any additional thought to the case mentioned above.
Thanks!
Abel
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [RFC PATCH 1/2] Revert "sched/fair: Make sched-idle CPU selection consistent throughout"
2025-03-10 7:40 ` [RFC PATCH 1/2] Revert "sched/fair: Make sched-idle CPU selection consistent throughout" Abel Wu
@ 2025-03-11 16:58 ` Vincent Guittot
2025-03-13 7:17 ` Abel Wu
0 siblings, 1 reply; 15+ messages in thread
From: Vincent Guittot @ 2025-03-11 16:58 UTC (permalink / raw)
To: Abel Wu
Cc: K Prateek Nayak, Ingo Molnar, Peter Zijlstra, Juri Lelli,
Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
Valentin Schneider, Josh Don, Tianchen Ding, open list:SCHEDULER
On Mon, 10 Mar 2025 at 08:41, Abel Wu <wuyun.abel@bytedance.com> wrote:
>
> This reverts commit 17346452b25b98acfb395d2a82ec2e4ad0cb7a01.
>
> The above commit tried to unify selection policy between idle cpus
> and SCHED_IDLE ones in fast- and slow-path of select_task_rq_fair()
> by treating them equally (although the SCHED_IDLE cpus are turned
> to be given more preference in slowpath). The test results seemed
> solid, but the setup didn't take cgroup hierarchy into account,
> which actually made some of our important services get affected.
>
> The cgroup hierarchy in our production environment looks like below,
> which might be common in modern containerized setup:
>
> root
> / \
> kubepods system.slice
> / \\ \
> guaranteed besteffort containerd
>
> (where 'X=A' means A is SCHED_IDLE cgroup)
>
> The cpu is treated as SCHED_IDLE if only besteffort is running, which
> is given at least equal preference as the idle cpus when deciding where
> to run a newly woken task. But the SCHED_IDLE cpus do not necessarily
> mean they can be preempted soon enough to start serving the wakee, and
Could you give us more details why the SCHED_IDLE cpu which runs only
besteffort can't be preempted soon enough ?
because kubepods vs system.slice is not sched_idle when comparing the
entities ? some maybe the definition of sched_idle_cpu should be fixed
instead
a sched_idle_cpu should be preempted immediately otherwise it's not a
sched idle cpu and the definition is meaningless
> containerd and other services under system.slice are the case that have
> to wait in runqueue since they can not preempt kubepods, while idle cpus
> are possible out there untouched.
>
> So prioritize idle cpus over SCHED_IDLE ones to avoid undesired delay
> like orchestration operations as much as possible.
>
> Signed-off-by: Abel Wu <wuyun.abel@bytedance.com>
> ---
> kernel/sched/fair.c | 49 +++++++++++++++++++++++++++------------------
> 1 file changed, 30 insertions(+), 19 deletions(-)
>
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index ae0350088ac1..379764bd2795 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -7446,7 +7446,7 @@ sched_balance_find_dst_group_cpu(struct sched_group *group, struct task_struct *
> unsigned int min_exit_latency = UINT_MAX;
> u64 latest_idle_timestamp = 0;
> int least_loaded_cpu = this_cpu;
> - int shallowest_idle_cpu = -1;
> + int shallowest_idle_cpu = -1, si_cpu = -1;
> int i;
>
> /* Check if we have any choice: */
> @@ -7460,9 +7460,6 @@ sched_balance_find_dst_group_cpu(struct sched_group *group, struct task_struct *
> if (!sched_core_cookie_match(rq, p))
> continue;
>
> - if (sched_idle_cpu(i))
> - return i;
> -
> if (available_idle_cpu(i)) {
> struct cpuidle_state *idle = idle_get_state(rq);
> if (idle && idle->exit_latency < min_exit_latency) {
> @@ -7484,7 +7481,12 @@ sched_balance_find_dst_group_cpu(struct sched_group *group, struct task_struct *
> latest_idle_timestamp = rq->idle_stamp;
> shallowest_idle_cpu = i;
> }
> - } else if (shallowest_idle_cpu == -1) {
> + } else if (shallowest_idle_cpu == -1 && si_cpu == -1) {
> + if (sched_idle_cpu(i)) {
> + si_cpu = i;
> + continue;
> + }
> +
> load = cpu_load(cpu_rq(i));
> if (load < min_load) {
> min_load = load;
> @@ -7493,7 +7495,11 @@ sched_balance_find_dst_group_cpu(struct sched_group *group, struct task_struct *
> }
> }
>
> - return shallowest_idle_cpu != -1 ? shallowest_idle_cpu : least_loaded_cpu;
> + if (shallowest_idle_cpu != -1)
> + return shallowest_idle_cpu;
> + if (si_cpu != -1)
> + return si_cpu;
> + return least_loaded_cpu;
> }
>
> static inline int sched_balance_find_dst_cpu(struct sched_domain *sd, struct task_struct *p,
> @@ -7549,11 +7555,14 @@ static inline int sched_balance_find_dst_cpu(struct sched_domain *sd, struct tas
> return new_cpu;
> }
>
> -static inline int __select_idle_cpu(int cpu, struct task_struct *p)
> +static inline int __select_idle_cpu(int cpu, struct task_struct *p, int *si_cpu)
> {
> - if ((available_idle_cpu(cpu) || sched_idle_cpu(cpu)) &&
> - sched_cpu_cookie_match(cpu_rq(cpu), p))
> + if (!sched_cpu_cookie_match(cpu_rq(cpu), p))
> + return -1;
> + if (available_idle_cpu(cpu))
> return cpu;
> + if (*si_cpu == -1 && sched_idle_cpu(cpu))
> + *si_cpu = cpu;
>
> return -1;
> }
> @@ -7649,7 +7658,7 @@ static int select_idle_core(struct task_struct *p, int core, struct cpumask *cpu
> */
> static int select_idle_smt(struct task_struct *p, struct sched_domain *sd, int target)
> {
> - int cpu;
> + int cpu, si_cpu = -1;
>
> for_each_cpu_and(cpu, cpu_smt_mask(target), p->cpus_ptr) {
> if (cpu == target)
> @@ -7660,11 +7669,13 @@ static int select_idle_smt(struct task_struct *p, struct sched_domain *sd, int t
> */
> if (!cpumask_test_cpu(cpu, sched_domain_span(sd)))
> continue;
> - if (available_idle_cpu(cpu) || sched_idle_cpu(cpu))
> + if (available_idle_cpu(cpu))
> return cpu;
> + if (si_cpu == -1 && sched_idle_cpu(cpu))
> + si_cpu = cpu;
> }
>
> - return -1;
> + return si_cpu;
> }
>
> #else /* CONFIG_SCHED_SMT */
> @@ -7680,7 +7691,7 @@ static inline bool test_idle_cores(int cpu)
>
> static inline int select_idle_core(struct task_struct *p, int core, struct cpumask *cpus, int *idle_cpu)
> {
> - return __select_idle_cpu(core, p);
> + return __select_idle_cpu(core, p, idle_cpu);
> }
>
> static inline int select_idle_smt(struct task_struct *p, struct sched_domain *sd, int target)
> @@ -7728,10 +7739,10 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, bool
> return i;
> } else {
> if (--nr <= 0)
> - return -1;
> - idle_cpu = __select_idle_cpu(cpu, p);
> - if ((unsigned int)idle_cpu < nr_cpumask_bits)
> return idle_cpu;
> + i = __select_idle_cpu(cpu, p, &idle_cpu);
> + if ((unsigned int)i < nr_cpumask_bits)
> + return i;
> }
> }
> cpumask_andnot(cpus, cpus, sched_group_span(sg));
> @@ -7746,9 +7757,9 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, bool
>
> } else {
> if (--nr <= 0)
> - return -1;
> - idle_cpu = __select_idle_cpu(cpu, p);
> - if ((unsigned int)idle_cpu < nr_cpumask_bits)
> + return idle_cpu;
> + i = __select_idle_cpu(cpu, p, &idle_cpu);
> + if ((unsigned int)i < nr_cpumask_bits)
> break;
> }
> }
> --
> 2.37.3
>
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: Re: [RFC PATCH 2/2] sched/fair: Do not specialcase SCHED_IDLE cpus in select slowpath
2025-03-11 16:43 ` Abel Wu
@ 2025-03-12 19:24 ` Josh Don
2025-03-13 7:41 ` Abel Wu
0 siblings, 1 reply; 15+ messages in thread
From: Josh Don @ 2025-03-12 19:24 UTC (permalink / raw)
To: Abel Wu
Cc: K Prateek Nayak, Ingo Molnar, Peter Zijlstra, Juri Lelli,
Vincent Guittot, Dietmar Eggemann, Steven Rostedt, Ben Segall,
Mel Gorman, Valentin Schneider, Tianchen Ding,
open list:SCHEDULER, Viresh Kumar
On Tue, Mar 11, 2025 at 9:43 AM Abel Wu <wuyun.abel@bytedance.com> wrote:
[snip]
> False positives are possible, but the possibility can be reduced by
> optimizing blooming setup.
An interesting approach, thanks for sharing. Not that it matters
(given that we're not pursuing this now), but just to call out that
this has poor scaling with large cgroup hierarchies and updates to
cgroup idle state, so in an actual implementation it would be ideal to
do the updates asynchronously from sched_group_set_idle (ie. via a
kworker).
We could also greatly simplify this down if we assume certain
contrived setups, for example if we assume we primarily care about
sched_idle cpu preemption against only root-level sched_idle cgroups
(as everything inside a root-level sched_idle cgroup is trivially
preemptible by a task from another hierarchy). But obviously your
cgroup setup doesn't fall under this category, so it is not very
useful.
> I chose the simplest way for now to workaround the issue we encountered,
> while I am still trying to do something to get rid of sched_idle_cpu().
> Thoughts?
That sounds reasonable to me.
Reviewed-by: Josh Don <joshdon@google.com>
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: Re: [RFC PATCH 1/2] Revert "sched/fair: Make sched-idle CPU selection consistent throughout"
2025-03-11 16:58 ` Vincent Guittot
@ 2025-03-13 7:17 ` Abel Wu
2025-03-19 9:17 ` Vincent Guittot
0 siblings, 1 reply; 15+ messages in thread
From: Abel Wu @ 2025-03-13 7:17 UTC (permalink / raw)
To: Vincent Guittot
Cc: K Prateek Nayak, Ingo Molnar, Peter Zijlstra, Juri Lelli,
Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
Valentin Schneider, Josh Don, Tianchen Ding, Viresh Kumar,
open list:SCHEDULER
Hi Vincent,
On 3/12/25 12:58 AM, Vincent Guittot wrote:
> On Mon, 10 Mar 2025 at 08:41, Abel Wu <wuyun.abel@bytedance.com> wrote:
>>
>> This reverts commit 17346452b25b98acfb395d2a82ec2e4ad0cb7a01.
>>
>> The above commit tried to unify selection policy between idle cpus
>> and SCHED_IDLE ones in fast- and slow-path of select_task_rq_fair()
>> by treating them equally (although the SCHED_IDLE cpus are turned
>> to be given more preference in slowpath). The test results seemed
>> solid, but the setup didn't take cgroup hierarchy into account,
>> which actually made some of our important services get affected.
>>
>> The cgroup hierarchy in our production environment looks like below,
>> which might be common in modern containerized setup:
>>
>> root
>> / \
>> kubepods system.slice
>> / \\ \
>> guaranteed besteffort containerd
>>
>> (where 'X=A' means A is SCHED_IDLE cgroup)
>>
>> The cpu is treated as SCHED_IDLE if only besteffort is running, which
>> is given at least equal preference as the idle cpus when deciding where
>> to run a newly woken task. But the SCHED_IDLE cpus do not necessarily
>> mean they can be preempted soon enough to start serving the wakee, and
>
> Could you give us more details why the SCHED_IDLE cpu which runs only
> besteffort can't be preempted soon enough ?
>
> because kubepods vs system.slice is not sched_idle when comparing the
Yes, exactly. What's worse is that kubepods.weight is the sum of all its
children and can easily reach ~3000, while system.weight is default to
100. The weight configuration can be optimized, but it's another topic.
> entities ? some maybe the definition of sched_idle_cpu should be fixed
> instead
Yes, there are at least two ways to fix it:
1) Let sched_idle_cpu() depends on a specific task, just like Josh
mentioned in the reply of 2nd patch. So if sched_idle_cpu(cpu, p)
returns true, then
a) this rq only contains hierarchical idle tasks, and
b) p can preempt current immediately
Please see my reply to Josh to check the details.
2) Or get rid of sched_idle_cpu() entirely. This needs some careful
rework. Now the users of cfs_rq::h_nr_idle are two parts:
a) select_task_rq, including sched_balance_find_dst_group_cpu()
and select_idle_*(). The former is handled by this series by
simply ignoring sched_idle_cpus, which should be safe since
sched_idle_cpus do not always follow the goal of the slowpath
to find a least loaded cpu to help load balancing. While the
latter is roughly designed as following:
- Must search within target LLC domain, since L3$ miss is
much more costly than L1/L2$
- To use cache more wisely, start searching from the L1/L2$
cache hot cpus like prev/recent_used/..
- Cheers if found an idle cpu that can preempt immediately.
This helps maximize using cpu bandwidth, hence improving
total throughput
- (?)
- Return target anyway, at least it might be cache hot
It could be less optimal if simply remove sched_idle_cpu and
return @target if no idle cpu available, because @target can
be heavy loaded and the cache may not hot any longer when the
wakee finally hit cpu. So in order not to fight with the load
balancing, shall we tiebreak on cpu_load() for the non-idle
cpus?
b) load balance: sched_balance_domains() and dequeue_entities().
We could leave this as-is, but I would propose using h_idle
instead: if the on_cpu task is hierarchically idle when
triggering normal load balancing, then we guess it's a less
loaded cpu and can reduce balance interval. The rationale
behind is that the idle entities usually get very limited
bandwidth if any hierarchically non-idle tasks available.
The heuristics may have false positives which can generally
be divided into 3 cases:
(The numbers represents hierarchical shares%)
C
A B / \
/ \\ / \\ 80 20
99 1 50 50 // \
100 (X)
- Case A) The hierarchical share of h_idle tasks is indeed
small. So in this case they are just get scheduled to take
some breath, and the possibility of false positive is low
enough to be safely ignored.
- Case B) The h_idle & !h_idle tasks equally share bandwidth
which usually means the !h_idle part becomes less loaded
and pulling some load might be preferred.
- Case C) The hierarchical share of h_idle tasks dominates
which usually means their !h_idle parents are allowed to
use a big portion of bandwidth. In this case speedup the
balance is still fine because we could pull some !h_idle
tasks for the most 'important' cgroup.
So the heuristics of using rq->curr's h_idle to judge the need
of pulling (load balancing) seems fine.
And as a result cfs_rq::h_nr_idle can be removed and its maintenance
cost in hotpath can be saved.
Which way do you prefer? It would be much appreciated if you can shed some
light on this.
>
> a sched_idle_cpu should be preempted immediately otherwise it's not a
> sched idle cpu and the definition is meaningless
Agree.
Thanks!
Abel
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: Re: [RFC PATCH 2/2] sched/fair: Do not specialcase SCHED_IDLE cpus in select slowpath
2025-03-12 19:24 ` Josh Don
@ 2025-03-13 7:41 ` Abel Wu
0 siblings, 0 replies; 15+ messages in thread
From: Abel Wu @ 2025-03-13 7:41 UTC (permalink / raw)
To: Josh Don
Cc: K Prateek Nayak, Ingo Molnar, Peter Zijlstra, Juri Lelli,
Vincent Guittot, Dietmar Eggemann, Steven Rostedt, Ben Segall,
Mel Gorman, Valentin Schneider, Tianchen Ding,
open list:SCHEDULER, Viresh Kumar
On 3/13/25 3:24 AM, Josh Don wrote:
> On Tue, Mar 11, 2025 at 9:43 AM Abel Wu <wuyun.abel@bytedance.com> wrote:
> [snip]
>> False positives are possible, but the possibility can be reduced by
>> optimizing blooming setup.
>
> An interesting approach, thanks for sharing. Not that it matters
> (given that we're not pursuing this now), but just to call out that
> this has poor scaling with large cgroup hierarchies and updates to
> cgroup idle state, so in an actual implementation it would be ideal to
> do the updates asynchronously from sched_group_set_idle (ie. via a
> kworker).
Good idea. Async update makes sense since sched_idle_cpu() is not
required 100% correct, and with this we also can join several updates
into one.
>
> We could also greatly simplify this down if we assume certain
> contrived setups, for example if we assume we primarily care about
> sched_idle cpu preemption against only root-level sched_idle cgroups
> (as everything inside a root-level sched_idle cgroup is trivially
> preemptible by a task from another hierarchy). But obviously your
> cgroup setup doesn't fall under this category, so it is not very
> useful.
>
>> I chose the simplest way for now to workaround the issue we encountered,
>> while I am still trying to do something to get rid of sched_idle_cpu().
>> Thoughts?
>
> That sounds reasonable to me.
>
> Reviewed-by: Josh Don <joshdon@google.com>
Thanks!
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: [RFC PATCH 0/2] Prioritize idle cpus over SCHED_IDLE ones
2025-03-10 7:40 [RFC PATCH 0/2] Prioritize idle cpus over SCHED_IDLE ones Abel Wu
` (2 preceding siblings ...)
2025-03-10 8:25 ` [RFC PATCH 0/2] Prioritize idle cpus over SCHED_IDLE ones Abel Wu
@ 2025-03-19 6:52 ` Abel Wu
3 siblings, 0 replies; 15+ messages in thread
From: Abel Wu @ 2025-03-19 6:52 UTC (permalink / raw)
To: K Prateek Nayak, Ingo Molnar, Peter Zijlstra, Juri Lelli,
Vincent Guittot, Dietmar Eggemann, Steven Rostedt, Ben Segall,
Mel Gorman, Valentin Schneider, Josh Don, Tianchen Ding,
Viresh Kumar
Cc: open list:SCHEDULER
Ping :)
On 3/10/25 3:40 PM, Abel Wu wrote:
> Since commit
>
> 17346452b25b ("sched/fair: Make sched-idle CPU selection consistent")
>
> the SCHED_IDLE cpus are given equal or more preference over idle ones in
> fast- and slow-path of select_task_rq_fair(). This works well in flattened
> cgroup hierarchy, e.g. all tasks running inside root cgroup, but may not
> ideal in a deeper hierarchy where SCHED_IDLE doesn't mean anything between
> entities whose parents are different. Hence a SCHED_IDLE cpu does NOT
> necessarily implies any of the following:
>
> - It is a less loaded cpu (since the parent of its topmost idle
> ancestor could be a 'giant' entity with large cpu.weight).
>
> - It can be expected to be preempted by a newly woken task soon
> enough (which actually depends on their ancestors who have
> common parent).
>
> As a less loaded cpu probably has better ability to serve the newly
> woken task, which also applies to the SCHED_IDLE cpus that less loaded
> SCHED_IDLE cpu might be easier and faster preempted, let's not special
> case SCHED_IDLE cpus at least in slowpath when selecting.
>
> [ Plan to try the same in SIS, that is selecting a less loaded cpu
> and get rid of ambiguous sched_idle_cpu(). Comments and suggests
> are really appreciated. ]
>
> Some benchmarks are tested in a Intel(R) Xeon(R) CPU E5-2650 v4 machine
> based on tip/master ec3106906cbf, and are tested in following two setup:
>
> (t1) (t2)
> root root
> / \\ / \
> benchmark noise benchmark X
> \\
> noise
>
> where noise comes from a SCHED_IDLE cgroup. I didn't see an obvious diff
> in hackbench or tbench, but not schbench.
>
> vanilla-t1 patched-t1
> Lat 50.0th-qrtle-1 8.00 ( 0.00%) 8.00 ( 0.00%)
> Lat 90.0th-qrtle-1 13.00 ( 0.00%) 13.00 ( 0.00%)
> Lat 99.0th-qrtle-1 19.00 ( 0.00%) 18.00 ( 5.26%)
> Lat 99.9th-qrtle-1 22.00 ( 0.00%) 22.00 ( 0.00%)
> Lat 20.0th-qrtle-1 257.00 ( 0.00%) 259.00 ( -0.78%)
> Lat 50.0th-qrtle-2 8.00 ( 0.00%) 9.00 ( -12.50%)
> Lat 90.0th-qrtle-2 13.00 ( 0.00%) 13.00 ( 0.00%)
> Lat 99.0th-qrtle-2 19.00 ( 0.00%) 19.00 ( 0.00%)
> Lat 99.9th-qrtle-2 23.00 ( 0.00%) 24.00 ( -4.35%)
> Lat 20.0th-qrtle-2 484.00 ( 0.00%) 434.00 ( 10.33%)
> Lat 50.0th-qrtle-4 9.00 ( 0.00%) 9.00 ( 0.00%)
> Lat 90.0th-qrtle-4 14.00 ( 0.00%) 14.00 ( 0.00%)
> Lat 99.0th-qrtle-4 19.00 ( 0.00%) 19.00 ( 0.00%)
> Lat 99.9th-qrtle-4 25.00 ( 0.00%) 24.00 ( 4.00%)
> Lat 20.0th-qrtle-4 877.00 ( 0.00%) 857.00 ( 2.28%)
> Lat 50.0th-qrtle-8 9.00 ( 0.00%) 9.00 ( 0.00%)
> Lat 90.0th-qrtle-8 14.00 ( 0.00%) 15.00 ( -7.14%)
> Lat 99.0th-qrtle-8 20.00 ( 0.00%) 21.00 ( -5.00%)
> Lat 99.9th-qrtle-8 26.00 ( 0.00%) 26.00 ( 0.00%)
> Lat 20.0th-qrtle-8 1698.00 ( 0.00%) 1598.00 ( 5.89%)
> Lat 50.0th-qrtle-16 10.00 ( 0.00%) 10.00 ( 0.00%)
> Lat 90.0th-qrtle-16 15.00 ( 0.00%) 15.00 ( 0.00%)
> Lat 99.0th-qrtle-16 20.00 ( 0.00%) 20.00 ( 0.00%)
> Lat 99.9th-qrtle-16 28.00 ( 0.00%) 27.00 ( 3.57%)
> Lat 20.0th-qrtle-16 2900.00 ( 0.00%) 2860.00 ( 1.38%)
> Lat 50.0th-qrtle-23 9.00 ( 0.00%) 9.00 ( 0.00%)
> Lat 90.0th-qrtle-23 15.00 ( 0.00%) 15.00 ( 0.00%)
> Lat 99.0th-qrtle-23 49.00 ( 0.00%) 28.00 ( 42.86%)
> Lat 99.9th-qrtle-23 1602.00 ( 0.00%) 1458.00 ( 8.99%)
> Lat 20.0th-qrtle-23 3796.00 ( 0.00%) 3804.00 ( -0.21%)
>
> vanilla-t2 patched-t2
> Lat 50.0th-qrtle-1 10.00 ( 0.00%) 9.00 ( 10.00%)
> Lat 90.0th-qrtle-1 271.00 ( 0.00%) 272.00 ( -0.37%)
> Lat 99.0th-qrtle-1 1013.00 ( 0.00%) 793.00 ( 21.72%)
> Lat 99.9th-qrtle-1 1998.00 ( 0.00%) 1642.00 ( 17.82%)
> Lat 20.0th-qrtle-1 262.00 ( 0.00%) 262.00 ( 0.00%)
> Lat 50.0th-qrtle-2 10.00 ( 0.00%) 9.00 ( 10.00%)
> Lat 90.0th-qrtle-2 531.00 ( 0.00%) 510.00 ( 3.95%)
> Lat 99.0th-qrtle-2 1034.00 ( 0.00%) 933.00 ( 9.77%)
> Lat 99.9th-qrtle-2 1846.00 ( 0.00%) 1614.00 ( 12.57%)
> Lat 20.0th-qrtle-2 517.00 ( 0.00%) 517.00 ( 0.00%)
> Lat 50.0th-qrtle-4 10.00 ( 0.00%) 10.00 ( 0.00%)
> Lat 90.0th-qrtle-4 523.00 ( 0.00%) 494.00 ( 5.54%)
> Lat 99.0th-qrtle-4 973.00 ( 0.00%) 901.00 ( 7.40%)
> Lat 99.9th-qrtle-4 1618.00 ( 0.00%) 1606.00 ( 0.74%)
> Lat 20.0th-qrtle-4 1015.00 ( 0.00%) 1001.00 ( 1.38%)
> Lat 50.0th-qrtle-8 11.00 ( 0.00%) 10.00 ( 9.09%)
> Lat 90.0th-qrtle-8 527.00 ( 0.00%) 454.00 ( 13.85%)
> Lat 99.0th-qrtle-8 931.00 ( 0.00%) 901.00 ( 3.22%)
> Lat 99.9th-qrtle-8 1598.00 ( 0.00%) 1582.00 ( 1.00%)
> Lat 20.0th-qrtle-8 1738.00 ( 0.00%) 1666.00 ( 4.14%)
> Lat 50.0th-qrtle-16 9.00 ( 0.00%) 9.00 ( 0.00%)
> Lat 90.0th-qrtle-16 410.00 ( 0.00%) 243.00 ( 40.73%)
> Lat 99.0th-qrtle-16 979.00 ( 0.00%) 891.00 ( 8.99%)
> Lat 99.9th-qrtle-16 1486.00 ( 0.00%) 1470.00 ( 1.08%)
> Lat 20.0th-qrtle-16 2708.00 ( 0.00%) 2708.00 ( 0.00%)
> Lat 50.0th-qrtle-23 8.00 ( 0.00%) 9.00 ( -12.50%)
> Lat 90.0th-qrtle-23 454.00 ( 0.00%) 303.00 ( 33.26%)
> Lat 99.0th-qrtle-23 3228.00 ( 0.00%) 2564.00 ( 20.57%)
> Lat 99.9th-qrtle-23 5496.00 ( 0.00%) 5304.00 ( 3.49%)
> Lat 20.0th-qrtle-23 3132.00 ( 0.00%) 3156.00 ( -0.77%)
>
> Abel Wu (2):
> Revert "sched/fair: Make sched-idle CPU selection consistent throughout"
> sched/fair: Do not specialcase SCHED_IDLE cpus in select slowpath
>
> kernel/sched/fair.c | 40 ++++++++++++++++++++++++----------------
> 1 file changed, 24 insertions(+), 16 deletions(-)
>
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: Re: [RFC PATCH 1/2] Revert "sched/fair: Make sched-idle CPU selection consistent throughout"
2025-03-13 7:17 ` Abel Wu
@ 2025-03-19 9:17 ` Vincent Guittot
2025-03-19 10:36 ` Abel Wu
0 siblings, 1 reply; 15+ messages in thread
From: Vincent Guittot @ 2025-03-19 9:17 UTC (permalink / raw)
To: Abel Wu
Cc: K Prateek Nayak, Ingo Molnar, Peter Zijlstra, Juri Lelli,
Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
Valentin Schneider, Josh Don, Tianchen Ding, Viresh Kumar,
open list:SCHEDULER
On Thu, 13 Mar 2025 at 08:18, Abel Wu <wuyun.abel@bytedance.com> wrote:
>
> Hi Vincent,
>
> On 3/12/25 12:58 AM, Vincent Guittot wrote:
> > On Mon, 10 Mar 2025 at 08:41, Abel Wu <wuyun.abel@bytedance.com> wrote:
> >>
> >> This reverts commit 17346452b25b98acfb395d2a82ec2e4ad0cb7a01.
> >>
> >> The above commit tried to unify selection policy between idle cpus
> >> and SCHED_IDLE ones in fast- and slow-path of select_task_rq_fair()
> >> by treating them equally (although the SCHED_IDLE cpus are turned
> >> to be given more preference in slowpath). The test results seemed
> >> solid, but the setup didn't take cgroup hierarchy into account,
> >> which actually made some of our important services get affected.
> >>
> >> The cgroup hierarchy in our production environment looks like below,
> >> which might be common in modern containerized setup:
> >>
> >> root
> >> / \
> >> kubepods system.slice
> >> / \\ \
> >> guaranteed besteffort containerd
> >>
> >> (where 'X=A' means A is SCHED_IDLE cgroup)
> >>
> >> The cpu is treated as SCHED_IDLE if only besteffort is running, which
> >> is given at least equal preference as the idle cpus when deciding where
> >> to run a newly woken task. But the SCHED_IDLE cpus do not necessarily
> >> mean they can be preempted soon enough to start serving the wakee, and
> >
> > Could you give us more details why the SCHED_IDLE cpu which runs only
> > besteffort can't be preempted soon enough ?
> >
> > because kubepods vs system.slice is not sched_idle when comparing the
>
> Yes, exactly. What's worse is that kubepods.weight is the sum of all its
> children and can easily reach ~3000, while system.weight is default to
> 100. The weight configuration can be optimized, but it's another topic.
>
> > entities ? some maybe the definition of sched_idle_cpu should be fixed
> > instead
>
> Yes, there are at least two ways to fix it:
>
> 1) Let sched_idle_cpu() depends on a specific task, just like Josh
> mentioned in the reply of 2nd patch. So if sched_idle_cpu(cpu, p)
> returns true, then
>
> a) this rq only contains hierarchical idle tasks, and
> b) p can preempt current immediately
>
> Please see my reply to Josh to check the details.
yeah, that should be the solution which covers all cases but at the
cost of walking cgroup hierarchy which is far from being ideal
Could we change h_nr_idle to only track fully sched idle tasks; I mean
tasks with a full sched_idle cgroup hierarchy ? so we would be sure to
preempt those sched idle cpus
Then, for other case of sched idle task or sched idle group childs of
a non sched idle group then we don't consider those cpu as sched idle
cpu
>
> 2) Or get rid of sched_idle_cpu() entirely. This needs some careful
> rework. Now the users of cfs_rq::h_nr_idle are two parts:
>
> a) select_task_rq, including sched_balance_find_dst_group_cpu()
> and select_idle_*(). The former is handled by this series by
> simply ignoring sched_idle_cpus, which should be safe since
> sched_idle_cpus do not always follow the goal of the slowpath
> to find a least loaded cpu to help load balancing. While the
> latter is roughly designed as following:
>
> - Must search within target LLC domain, since L3$ miss is
> much more costly than L1/L2$
> - To use cache more wisely, start searching from the L1/L2$
> cache hot cpus like prev/recent_used/..
> - Cheers if found an idle cpu that can preempt immediately.
> This helps maximize using cpu bandwidth, hence improving
> total throughput
> - (?)
> - Return target anyway, at least it might be cache hot
>
> It could be less optimal if simply remove sched_idle_cpu and
> return @target if no idle cpu available, because @target can
> be heavy loaded and the cache may not hot any longer when the
> wakee finally hit cpu. So in order not to fight with the load
> balancing, shall we tiebreak on cpu_load() for the non-idle
> cpus?
>
> b) load balance: sched_balance_domains() and dequeue_entities().
> We could leave this as-is, but I would propose using h_idle
> instead: if the on_cpu task is hierarchically idle when
> triggering normal load balancing, then we guess it's a less
> loaded cpu and can reduce balance interval. The rationale
> behind is that the idle entities usually get very limited
> bandwidth if any hierarchically non-idle tasks available.
> The heuristics may have false positives which can generally
> be divided into 3 cases:
>
> (The numbers represents hierarchical shares%)
>
> C
> A B / \
> / \\ / \\ 80 20
> 99 1 50 50 // \
> 100 (X)
How the sched_idle group in B can have the same share/weight as the
not sched idle one in case B ?
>
> - Case A) The hierarchical share of h_idle tasks is indeed
> small. So in this case they are just get scheduled to take
> some breath, and the possibility of false positive is low
> enough to be safely ignored.
>
> - Case B) The h_idle & !h_idle tasks equally share bandwidth
> which usually means the !h_idle part becomes less loaded
> and pulling some load might be preferred.
>
> - Case C) The hierarchical share of h_idle tasks dominates
> which usually means their !h_idle parents are allowed to
> use a big portion of bandwidth. In this case speedup the
> balance is still fine because we could pull some !h_idle
> tasks for the most 'important' cgroup.
>
> So the heuristics of using rq->curr's h_idle to judge the need
> of pulling (load balancing) seems fine.
>
> And as a result cfs_rq::h_nr_idle can be removed and its maintenance
> cost in hotpath can be saved.
>
> Which way do you prefer? It would be much appreciated if you can shed some
> light on this.
>
> >
> > a sched_idle_cpu should be preempted immediately otherwise it's not a
> > sched idle cpu and the definition is meaningless
>
> Agree.
>
> Thanks!
> Abel
>
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: Re: [RFC PATCH 1/2] Revert "sched/fair: Make sched-idle CPU selection consistent throughout"
2025-03-19 9:17 ` Vincent Guittot
@ 2025-03-19 10:36 ` Abel Wu
2025-03-19 10:58 ` Vincent Guittot
0 siblings, 1 reply; 15+ messages in thread
From: Abel Wu @ 2025-03-19 10:36 UTC (permalink / raw)
To: Vincent Guittot
Cc: K Prateek Nayak, Ingo Molnar, Peter Zijlstra, Juri Lelli,
Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
Valentin Schneider, Josh Don, Tianchen Ding, Viresh Kumar,
open list:SCHEDULER
On 3/19/25 5:17 PM, Vincent Guittot wrote:
> On Thu, 13 Mar 2025 at 08:18, Abel Wu <wuyun.abel@bytedance.com> wrote:
>>
>> Hi Vincent,
>>
>> On 3/12/25 12:58 AM, Vincent Guittot wrote:
>>> On Mon, 10 Mar 2025 at 08:41, Abel Wu <wuyun.abel@bytedance.com> wrote:
>>>>
>>>> This reverts commit 17346452b25b98acfb395d2a82ec2e4ad0cb7a01.
>>>>
>>>> The above commit tried to unify selection policy between idle cpus
>>>> and SCHED_IDLE ones in fast- and slow-path of select_task_rq_fair()
>>>> by treating them equally (although the SCHED_IDLE cpus are turned
>>>> to be given more preference in slowpath). The test results seemed
>>>> solid, but the setup didn't take cgroup hierarchy into account,
>>>> which actually made some of our important services get affected.
>>>>
>>>> The cgroup hierarchy in our production environment looks like below,
>>>> which might be common in modern containerized setup:
>>>>
>>>> root
>>>> / \
>>>> kubepods system.slice
>>>> / \\ \
>>>> guaranteed besteffort containerd
>>>>
>>>> (where 'X=A' means A is SCHED_IDLE cgroup)
>>>>
>>>> The cpu is treated as SCHED_IDLE if only besteffort is running, which
>>>> is given at least equal preference as the idle cpus when deciding where
>>>> to run a newly woken task. But the SCHED_IDLE cpus do not necessarily
>>>> mean they can be preempted soon enough to start serving the wakee, and
>>>
>>> Could you give us more details why the SCHED_IDLE cpu which runs only
>>> besteffort can't be preempted soon enough ?
>>>
>>> because kubepods vs system.slice is not sched_idle when comparing the
>>
>> Yes, exactly. What's worse is that kubepods.weight is the sum of all its
>> children and can easily reach ~3000, while system.weight is default to
>> 100. The weight configuration can be optimized, but it's another topic.
>>
>>> entities ? some maybe the definition of sched_idle_cpu should be fixed
>>> instead
>>
>> Yes, there are at least two ways to fix it:
>>
>> 1) Let sched_idle_cpu() depends on a specific task, just like Josh
>> mentioned in the reply of 2nd patch. So if sched_idle_cpu(cpu, p)
>> returns true, then
>>
>> a) this rq only contains hierarchical idle tasks, and
>> b) p can preempt current immediately
>>
>> Please see my reply to Josh to check the details.
>
> yeah, that should be the solution which covers all cases but at the
> cost of walking cgroup hierarchy which is far from being ideal
Only comparing curr vs wakee doesn't solve the problem. A cpu can be
treated as SCHED_IDLE iff *all* its SCHED_IDLE entities can be preempted
by the wakee.
>
> Could we change h_nr_idle to only track fully sched idle tasks; I mean
> tasks with a full sched_idle cgroup hierarchy ? so we would be sure to
> preempt those sched idle cpus
>
> Then, for other case of sched idle task or sched idle group childs of
> a non sched idle group then we don't consider those cpu as sched idle
> cpu
Ahthough this is correct, I think it would be too much since this kind
of setup is rare to the best of my knowledge.
>
>
>>
>> 2) Or get rid of sched_idle_cpu() entirely. This needs some careful
>> rework. Now the users of cfs_rq::h_nr_idle are two parts:
>>
>> a) select_task_rq, including sched_balance_find_dst_group_cpu()
>> and select_idle_*(). The former is handled by this series by
>> simply ignoring sched_idle_cpus, which should be safe since
>> sched_idle_cpus do not always follow the goal of the slowpath
>> to find a least loaded cpu to help load balancing. While the
>> latter is roughly designed as following:
>>
>> - Must search within target LLC domain, since L3$ miss is
>> much more costly than L1/L2$
>> - To use cache more wisely, start searching from the L1/L2$
>> cache hot cpus like prev/recent_used/..
>> - Cheers if found an idle cpu that can preempt immediately.
>> This helps maximize using cpu bandwidth, hence improving
>> total throughput
>> - (?)
>> - Return target anyway, at least it might be cache hot
>>
>> It could be less optimal if simply remove sched_idle_cpu and
>> return @target if no idle cpu available, because @target can
>> be heavy loaded and the cache may not hot any longer when the
>> wakee finally hit cpu. So in order not to fight with the load
>> balancing, shall we tiebreak on cpu_load() for the non-idle
>> cpus?
What do you think to choose a less loaded cpu if no idle ones available?
So the wakee will probably get better served, and also helps load balance.
>>
>> b) load balance: sched_balance_domains() and dequeue_entities().
>> We could leave this as-is, but I would propose using h_idle
>> instead: if the on_cpu task is hierarchically idle when
>> triggering normal load balancing, then we guess it's a less
>> loaded cpu and can reduce balance interval. The rationale
>> behind is that the idle entities usually get very limited
>> bandwidth if any hierarchically non-idle tasks available.
>> The heuristics may have false positives which can generally
>> be divided into 3 cases:
>>
>> (The numbers represents hierarchical shares%)
>>
>> C
>> A B / \
>> / \\ / \\ 80 20
>> 99 1 50 50 // \
>> 100 (X)
>
>
> How the sched_idle group in B can have the same share/weight as the
> not sched idle one in case B ?
It can't, but theoretically several SCHED_IDLE siblings can be summed up
to match a niced SCHED_NORMAL entity.
B
|
---------------------------------------
| || || || || ||
15 3 3 3 3 3
>
>
>>
>> - Case A) The hierarchical share of h_idle tasks is indeed
>> small. So in this case they are just get scheduled to take
>> some breath, and the possibility of false positive is low
>> enough to be safely ignored.
>>
>> - Case B) The h_idle & !h_idle tasks equally share bandwidth
>> which usually means the !h_idle part becomes less loaded
>> and pulling some load might be preferred.
>>
>> - Case C) The hierarchical share of h_idle tasks dominates
>> which usually means their !h_idle parents are allowed to
>> use a big portion of bandwidth. In this case speedup the
>> balance is still fine because we could pull some !h_idle
>> tasks for the most 'important' cgroup.
>>
>> So the heuristics of using rq->curr's h_idle to judge the need
>> of pulling (load balancing) seems fine.
>>
>> And as a result cfs_rq::h_nr_idle can be removed and its maintenance
>> cost in hotpath can be saved.
>>
>> Which way do you prefer? It would be much appreciated if you can shed some
>> light on this.
>>
>>>
>>> a sched_idle_cpu should be preempted immediately otherwise it's not a
>>> sched idle cpu and the definition is meaningless
>>
>> Agree.
>>
>> Thanks!
>> Abel
>>
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: Re: [RFC PATCH 1/2] Revert "sched/fair: Make sched-idle CPU selection consistent throughout"
2025-03-19 10:36 ` Abel Wu
@ 2025-03-19 10:58 ` Vincent Guittot
2025-03-20 14:35 ` Abel Wu
0 siblings, 1 reply; 15+ messages in thread
From: Vincent Guittot @ 2025-03-19 10:58 UTC (permalink / raw)
To: Abel Wu
Cc: K Prateek Nayak, Ingo Molnar, Peter Zijlstra, Juri Lelli,
Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
Valentin Schneider, Josh Don, Tianchen Ding, Viresh Kumar,
open list:SCHEDULER
On Wed, 19 Mar 2025 at 11:36, Abel Wu <wuyun.abel@bytedance.com> wrote:
>
> On 3/19/25 5:17 PM, Vincent Guittot wrote:
> > On Thu, 13 Mar 2025 at 08:18, Abel Wu <wuyun.abel@bytedance.com> wrote:
> >>
> >> Hi Vincent,
> >>
> >> On 3/12/25 12:58 AM, Vincent Guittot wrote:
> >>> On Mon, 10 Mar 2025 at 08:41, Abel Wu <wuyun.abel@bytedance.com> wrote:
> >>>>
> >>>> This reverts commit 17346452b25b98acfb395d2a82ec2e4ad0cb7a01.
> >>>>
> >>>> The above commit tried to unify selection policy between idle cpus
> >>>> and SCHED_IDLE ones in fast- and slow-path of select_task_rq_fair()
> >>>> by treating them equally (although the SCHED_IDLE cpus are turned
> >>>> to be given more preference in slowpath). The test results seemed
> >>>> solid, but the setup didn't take cgroup hierarchy into account,
> >>>> which actually made some of our important services get affected.
> >>>>
> >>>> The cgroup hierarchy in our production environment looks like below,
> >>>> which might be common in modern containerized setup:
> >>>>
> >>>> root
> >>>> / \
> >>>> kubepods system.slice
> >>>> / \\ \
> >>>> guaranteed besteffort containerd
> >>>>
> >>>> (where 'X=A' means A is SCHED_IDLE cgroup)
> >>>>
> >>>> The cpu is treated as SCHED_IDLE if only besteffort is running, which
> >>>> is given at least equal preference as the idle cpus when deciding where
> >>>> to run a newly woken task. But the SCHED_IDLE cpus do not necessarily
> >>>> mean they can be preempted soon enough to start serving the wakee, and
> >>>
> >>> Could you give us more details why the SCHED_IDLE cpu which runs only
> >>> besteffort can't be preempted soon enough ?
> >>>
> >>> because kubepods vs system.slice is not sched_idle when comparing the
> >>
> >> Yes, exactly. What's worse is that kubepods.weight is the sum of all its
> >> children and can easily reach ~3000, while system.weight is default to
> >> 100. The weight configuration can be optimized, but it's another topic.
> >>
> >>> entities ? some maybe the definition of sched_idle_cpu should be fixed
> >>> instead
> >>
> >> Yes, there are at least two ways to fix it:
> >>
> >> 1) Let sched_idle_cpu() depends on a specific task, just like Josh
> >> mentioned in the reply of 2nd patch. So if sched_idle_cpu(cpu, p)
> >> returns true, then
> >>
> >> a) this rq only contains hierarchical idle tasks, and
> >> b) p can preempt current immediately
> >>
> >> Please see my reply to Josh to check the details.
> >
> > yeah, that should be the solution which covers all cases but at the
> > cost of walking cgroup hierarchy which is far from being ideal
>
> Only comparing curr vs wakee doesn't solve the problem. A cpu can be
> treated as SCHED_IDLE iff *all* its SCHED_IDLE entities can be preempted
> by the wakee.
>
> >
> > Could we change h_nr_idle to only track fully sched idle tasks; I mean
> > tasks with a full sched_idle cgroup hierarchy ? so we would be sure to
> > preempt those sched idle cpus
> >
> > Then, for other case of sched idle task or sched idle group childs of
> > a non sched idle group then we don't consider those cpu as sched idle
> > cpu
>
> Ahthough this is correct, I think it would be too much since this kind
> of setup is rare to the best of my knowledge.
But that's the only case that we are sure
>
> >
> >
> >>
> >> 2) Or get rid of sched_idle_cpu() entirely. This needs some careful
> >> rework. Now the users of cfs_rq::h_nr_idle are two parts:
> >>
> >> a) select_task_rq, including sched_balance_find_dst_group_cpu()
> >> and select_idle_*(). The former is handled by this series by
> >> simply ignoring sched_idle_cpus, which should be safe since
> >> sched_idle_cpus do not always follow the goal of the slowpath
> >> to find a least loaded cpu to help load balancing. While the
> >> latter is roughly designed as following:
> >>
> >> - Must search within target LLC domain, since L3$ miss is
> >> much more costly than L1/L2$
> >> - To use cache more wisely, start searching from the L1/L2$
> >> cache hot cpus like prev/recent_used/..
> >> - Cheers if found an idle cpu that can preempt immediately.
> >> This helps maximize using cpu bandwidth, hence improving
> >> total throughput
> >> - (?)
> >> - Return target anyway, at least it might be cache hot
> >>
> >> It could be less optimal if simply remove sched_idle_cpu and
> >> return @target if no idle cpu available, because @target can
> >> be heavy loaded and the cache may not hot any longer when the
> >> wakee finally hit cpu. So in order not to fight with the load
> >> balancing, shall we tiebreak on cpu_load() for the non-idle
> >> cpus?
>
> What do you think to choose a less loaded cpu if no idle ones available?
> So the wakee will probably get better served, and also helps load balance.
I'm not a fan of adding more than idle selection and we already
compared load in wake_affine.
So we should only look at a cpu that we can preempt immediately: idle
cpus or cpus with full hierarchy sched idle entities
>
> >>
> >> b) load balance: sched_balance_domains() and dequeue_entities().
> >> We could leave this as-is, but I would propose using h_idle
> >> instead: if the on_cpu task is hierarchically idle when
> >> triggering normal load balancing, then we guess it's a less
> >> loaded cpu and can reduce balance interval. The rationale
> >> behind is that the idle entities usually get very limited
> >> bandwidth if any hierarchically non-idle tasks available.
> >> The heuristics may have false positives which can generally
> >> be divided into 3 cases:
> >>
> >> (The numbers represents hierarchical shares%)
> >>
> >> C
> >> A B / \
> >> / \\ / \\ 80 20
> >> 99 1 50 50 // \
> >> 100 (X)
> >
> >
> > How the sched_idle group in B can have the same share/weight as the
> > not sched idle one in case B ?
>
> It can't, but theoretically several SCHED_IDLE siblings can be summed up
> to match a niced SCHED_NORMAL entity.
>
> B
> |
> ---------------------------------------
> | || || || || ||
> 15 3 3 3 3 3
>
> >
> >
> >>
> >> - Case A) The hierarchical share of h_idle tasks is indeed
> >> small. So in this case they are just get scheduled to take
> >> some breath, and the possibility of false positive is low
> >> enough to be safely ignored.
> >>
> >> - Case B) The h_idle & !h_idle tasks equally share bandwidth
> >> which usually means the !h_idle part becomes less loaded
> >> and pulling some load might be preferred.
> >>
> >> - Case C) The hierarchical share of h_idle tasks dominates
> >> which usually means their !h_idle parents are allowed to
> >> use a big portion of bandwidth. In this case speedup the
> >> balance is still fine because we could pull some !h_idle
> >> tasks for the most 'important' cgroup.
> >>
> >> So the heuristics of using rq->curr's h_idle to judge the need
> >> of pulling (load balancing) seems fine.
> >>
> >> And as a result cfs_rq::h_nr_idle can be removed and its maintenance
> >> cost in hotpath can be saved.
> >>
> >> Which way do you prefer? It would be much appreciated if you can shed some
> >> light on this.
> >>
> >>>
> >>> a sched_idle_cpu should be preempted immediately otherwise it's not a
> >>> sched idle cpu and the definition is meaningless
> >>
> >> Agree.
> >>
> >> Thanks!
> >> Abel
> >>
>
^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: Re: [RFC PATCH 1/2] Revert "sched/fair: Make sched-idle CPU selection consistent throughout"
2025-03-19 10:58 ` Vincent Guittot
@ 2025-03-20 14:35 ` Abel Wu
0 siblings, 0 replies; 15+ messages in thread
From: Abel Wu @ 2025-03-20 14:35 UTC (permalink / raw)
To: Vincent Guittot
Cc: K Prateek Nayak, Ingo Molnar, Peter Zijlstra, Juri Lelli,
Dietmar Eggemann, Steven Rostedt, Ben Segall, Mel Gorman,
Valentin Schneider, Josh Don, Tianchen Ding, Viresh Kumar,
open list:SCHEDULER
On 3/19/25 6:58 PM, Vincent Guittot wrote:
> On Wed, 19 Mar 2025 at 11:36, Abel Wu <wuyun.abel@bytedance.com> wrote:
>>
>> What do you think to choose a less loaded cpu if no idle ones available?
>> So the wakee will probably get better served, and also helps load balance.
>
> I'm not a fan of adding more than idle selection and we already
> compared load in wake_affine.
> So we should only look at a cpu that we can preempt immediately: idle
> cpus or cpus with full hierarchy sched idle entities
OK, I will have a try. Thanks!
^ permalink raw reply [flat|nested] 15+ messages in thread
end of thread, other threads:[~2025-03-20 14:35 UTC | newest]
Thread overview: 15+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2025-03-10 7:40 [RFC PATCH 0/2] Prioritize idle cpus over SCHED_IDLE ones Abel Wu
2025-03-10 7:40 ` [RFC PATCH 1/2] Revert "sched/fair: Make sched-idle CPU selection consistent throughout" Abel Wu
2025-03-11 16:58 ` Vincent Guittot
2025-03-13 7:17 ` Abel Wu
2025-03-19 9:17 ` Vincent Guittot
2025-03-19 10:36 ` Abel Wu
2025-03-19 10:58 ` Vincent Guittot
2025-03-20 14:35 ` Abel Wu
2025-03-10 7:40 ` [RFC PATCH 2/2] sched/fair: Do not specialcase SCHED_IDLE cpus in select slowpath Abel Wu
2025-03-10 22:38 ` Josh Don
2025-03-11 16:43 ` Abel Wu
2025-03-12 19:24 ` Josh Don
2025-03-13 7:41 ` Abel Wu
2025-03-10 8:25 ` [RFC PATCH 0/2] Prioritize idle cpus over SCHED_IDLE ones Abel Wu
2025-03-19 6:52 ` Abel Wu
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®