sched/fair: select idle cpu from idle cpumask for task wakeup
RFC PATCH v7 1/1 sched/fair: select idle cpu from idle cpumask for task wakeup
Add idle cpumask to track idle cpus in sched domain. Every time a CPU enters idle, the CPU is set in idle cpumask to be a wakeup target. And if the CPU is not in idle, the CPU is cleared in idle cpumask during scheduler tick to ratelimit idle cpumask update.
When a task wakes up to select an idle cpu, scanning idle cpumask has lower cost than scanning all the cpus in last level cache domain, especially when the system is heavily loaded.
Benchmarks including hackbench, schbench, uperf, sysbench mysql and kbuild were tested on a x86 4 socket system with 24 cores per socket and 2 hyperthreads per core, total 192 CPUs, no regression found.
v6->v7:
- place the whole idle cpumask mechanism under CONFIG_SMP.
v5->v6:
- decouple idle cpumask update from stop_tick signal, set idle CPU in idle cpumask every time the CPU enters idle
v4->v5:
- add update_idle_cpumask for s2idle case
- keep the same ordering of tick_nohz_idle_stop_tick() and update_ idle_cpumask() everywhere
v3->v4:
- change setting idle cpumask from every idle entry to tickless idle if cpu driver is available.
- move clearing idle cpumask to scheduler_tick to decouple nohz mode.
v2->v3:
- change setting idle cpumask to every idle entry, otherwise schbench has a regression of 99th percentile latency.
- change clearing idle cpumask to nohz_balancer_kick(), so updating idle cpumask is ratelimited in the idle exiting path.
- set SCHED_IDLE cpu in idle cpumask to allow it as a wakeup target.
v1->v2:
- idle cpumask is updated in the nohz routines, by initializing idle cpumask with sched_domain_span(sd), nohz=off case remains the original behavior.
--- include/linux/sched/topology.h | 13 +++++++++ kernel/sched/core.c | 2 ++ kernel/sched/fair.c | 51 +++++++++++++++++++++++++++++++++- kernel/sched/idle.c | 5 ++++ kernel/sched/sched.h | 4 +++ kernel/sched/topology.c | 3 +- 6 files changed, 76 insertions(+), 2 deletions(-)
include/linux/sched/topology.h +13 -0
@@ -65,8 +65,21 @@ struct sched_domain_shared {atomic_t ref;atomic_t nr_busy_cpus;int has_idle_cores; +/* +* Span of all idle CPUs in this domain. +* +* NOTE: this field is variable length. (Allocated dynamically +* by attaching extra space to the end of the structure, +* depending on how many CPUs the kernel has booted up with) +*/ +unsigned long idle_cpus_span[]; }; +static inline struct cpumask *sds_idle_cpus (struct sched_domain_shared *sds) +{ +return to_cpumask (sds->idle_cpus_span); +} +struct sched_domain {/* These fields must be setup */ struct sched_domain __rcu *parent;/* top domain must be null terminated */
kernel/sched/core.c +2 -0
@@ -4011,6 +4011,7 @@ void scheduler_tick(void)#ifdef CONFIG_SMP rq->idle_balance =idle_cpu (cpu); +update_idle_cpumask (cpu, false);trigger_load_balance (rq);#endif }
@@ -7186,6 +7187,7 @@ void __init sched_init(void) rq->idle_stamp =0 ; rq->avg_idle =2 *sysctl_sched_migration_cost; rq->max_idle_balance_cost = sysctl_sched_migration_cost; + rq->last_idle_state =1 ;INIT_LIST_HEAD (&rq->cfs_tasks);
kernel/sched/fair.c +50 -1
63 lines not on this page · raw message
kernel/sched/idle.c +5 -0
@@ -257,6 +257,11 @@ static void do_idle(void)cpuhp_report_idle_dead ();arch_cpu_idle_dead (); } +/* +* The CPU is about to go idle, set it in idle cpumask +* to be a wake up target. +*/ +update_idle_cpumask (cpu, true);arch_cpu_idle_enter ();
kernel/sched/sched.h +4 -0
@@ -976,6 +976,7 @@ struct rq {unsigned char nohz_idle_balance;unsigned char idle_balance; +unsigned char last_idle_state;unsigned long misfit_task_load;
@@ -1516,6 +1517,8 @@ static inline unsigned int group_first_cpu(struct sched_group *group)extern int group_balance_cpu (struct sched_group *sg); +void update_idle_cpumask (int cpu,bool set_idle); +#if defined(CONFIG_SCHED_DEBUG ) && defined(CONFIG_SYSCTL )void register_sched_domain_sysctl (void );void dirty_sched_domain_sysctl (int cpu);
@@ -1536,6 +1539,7 @@ extern void flush_smp_call_function_from_idle(void);#else /* !CONFIG_SMP: */ static inline void flush_smp_call_function_from_idle (void ) { } +static inline void update_idle_cpumask (int cpu,bool set_idle) { }#endif #include "stats.h"
kernel/sched/topology.c +2 -1
@@ -1407,6 +1407,7 @@ sd_init(struct sched_domain_topology_level *tl, sd->shared = *per_cpu_ptr (sdd->sds, sd_id);atomic_inc (&sd->shared->ref);atomic_set (&sd->shared->nr_busy_cpus, sd_weight); +cpumask_copy (sds_idle_cpus (sd->shared),sched_domain_span (sd)); } sd->private = sdd;
@@ -1769,7 +1770,7 @@ static int __sdt_alloc(const struct cpumask *cpu_map) *per_cpu_ptr (sdd->sd, j) = sd; - sds =kzalloc_node (sizeof (struct sched_domain_shared ), + sds =kzalloc_node (sizeof (struct sched_domain_shared ) +cpumask_size (),GFP_KERNEL ,cpu_to_node (j));if (!sds)return -ENOMEM ;
Signature · 1 line
2.25.1
Vincent Guittot
maintainerQuoted 91 lines · Aubrey Li
Add idle cpumask to track idle cpus in sched domain. Every time a CPU enters idle, the CPU is set in idle cpumask to be a wakeup target. And if the CPU is not in idle, the CPU is cleared in idle cpumask during scheduler tick to ratelimit idle cpumask update.
When a task wakes up to select an idle cpu, scanning idle cpumask has lower cost than scanning all the cpus in last level cache domain, especially when the system is heavily loaded.
Benchmarks including hackbench, schbench, uperf, sysbench mysql and kbuild were tested on a x86 4 socket system with 24 cores per socket and 2 hyperthreads per core, total 192 CPUs, no regression found.
v6->v7:
- place the whole idle cpumask mechanism underCONFIG_SMP.
v5->v6:
- decouple idle cpumask update fromstop_ticksignal, set idle CPU in idle cpumask every time the CPU enters idle
v4->v5:
- addupdate_idle_cpumaskfor s2idle case
- keep the same ordering oftick_nohz_idle_stop_tick()andupdate_idle_cpumask()everywhere
v3->v4:
- change setting idle cpumask from every idle entry to tickless idle if cpu driver is available.
- move clearing idle cpumask toscheduler_tickto decouple nohz mode.
v2->v3:
- change setting idle cpumask to every idle entry, otherwise schbench has a regression of 99th percentile latency.
- change clearing idle cpumask tonohz_balancer_kick(), so updating idle cpumask is ratelimited in the idle exiting path.
- setSCHED_IDLEcpu in idle cpumask to allow it as a wakeup target.
v1->v2:
- idle cpumask is updated in the nohz routines, by initializing idle cpumask withsched_domain_span(sd), nohz=off case remains the original behavior.Cc Peter Zijlstra <[email protected]>Cc Mel Gorman <[email protected]>Cc Vincent Guittot <[email protected]>Cc Qais Yousef <[email protected]>Cc Valentin Schneider <[email protected]>Cc Jiang Biao <[email protected]>Cc Tim Chen <[email protected]>Signed-off-by Aubrey Li <[email protected]>--- include/linux/sched/topology.h | 13 +++++++++ kernel/sched/core.c | 2 ++ kernel/sched/fair.c | 51 +++++++++++++++++++++++++++++++++- kernel/sched/idle.c | 5 ++++ kernel/sched/sched.h | 4 +++ kernel/sched/topology.c | 3 +- 6 files changed, 76 insertions(+), 2 deletions(-)include/linux/sched/topology.h +13
-0@@ -65,8 +65,21 @@ struct sched_domain_shared {atomic_t ref;atomic_t nr_busy_cpus;int has_idle_cores; +/* +* Span of all idle CPUs in this domain. +* +* NOTE: this field is variable length. (Allocated dynamically +* by attaching extra space to the end of the structure, +* depending on how many CPUs the kernel has booted up with) +*/ +unsigned long idle_cpus_span[]; }; +static inline struct cpumask *sds_idle_cpus (struct sched_domain_shared *sds) +{ +return to_cpumask (sds->idle_cpus_span); +} +struct sched_domain {/* These fields must be setup */ struct sched_domain __rcu *parent;/* top domain must be null terminated */ kernel/sched/core.c +0
-0
kernel/sched/core.c void scheduler_tick(void) · line 4014
Quoted 4 lines
kernel/sched/core.c +1
-0@@ -4011,6 +4011,7 @@ void scheduler_tick(void)#ifdef CONFIG_SMP rq->idle_balance =idle_cpu (cpu); +update_idle_cpumask (cpu, false);
Test rq->idle_balance here instead of adding the test in update_idle_cpumask which is only relevant for this situation.
if (!rq->idle_balance)
update_idle_cpumask(cpu, false);
Quoted 149 lines
kernel/sched/core.c +1
-0trigger_load_balance (rq);#endif }@@ -7186,6 +7187,7 @@ void __init sched_init(void) rq->idle_stamp =0 ; rq->avg_idle =2 *sysctl_sched_migration_cost; rq->max_idle_balance_cost = sysctl_sched_migration_cost; + rq->last_idle_state =1 ;INIT_LIST_HEAD (&rq->cfs_tasks);kernel/sched/fair.c +50
-1@@ -6146,7 +6146,12 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, int t time =cpu_clock (this); -cpumask_and (cpus,sched_domain_span (sd), p->cpus_ptr); +/* +* sched_domain_shared is set only at shared cache level, +* this works only because select_idle_cpu is called with +* sd_llc. +*/ +cpumask_and (cpus,sds_idle_cpus (sd->shared), p->cpus_ptr);for_each_cpu_wrap (cpu, cpus, target) {if (!--nr)@@ -6806,6 +6811,50 @@ balance_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf) return newidle_balance(rq, rf) != 0; } + +/* +* Update cpu idle state and record this information +* in sd_llc_shared->idle_cpus_span. +*/ +void update_idle_cpumask (int cpu,bool set_idle) +{ +struct sched_domain *sd; +struct rq *rq =cpu_rq (cpu); +int idle_state; + +/* +* If called from scheduler tick, only update +* idle cpumask if the CPU is busy, as idle +* cpumask is also updated on idle entry. +* +*/ +if (!set_idle && rq->idle_balance) +return ; +/* +* Also set SCHED_IDLE cpu in idle cpumask to +* allow SCHED_IDLE cpu as a wakeup target +*/ + idle_state = set_idle ||sched_idle_cpu (cpu); +/* +* No need to update idle cpumask if the state +* does not change. +*/ +if (rq->last_idle_state == idle_state) +return ; +/* +* Called with irq disabled, rcu_read_lock() is not needed. +*/ + sd =rcu_dereference (per_cpu (sd_llc, cpu)); +if (unlikely (!sd)) +return ; + +if (idle_state) +cpumask_set_cpu (cpu,sds_idle_cpus (sd->shared)); +else +cpumask_clear_cpu (cpu,sds_idle_cpus (sd->shared)); + + rq->last_idle_state = idle_state; +}#endif /* CONFIG_SMP */ static unsigned long wakeup_gran (struct sched_entity *se)kernel/sched/idle.c +5
-0@@ -257,6 +257,11 @@ static void do_idle(void)cpuhp_report_idle_dead ();arch_cpu_idle_dead (); } +/* +* The CPU is about to go idle, set it in idle cpumask +* to be a wake up target. +*/ +update_idle_cpumask (cpu, true);arch_cpu_idle_enter ();kernel/sched/sched.h +4
-0@@ -976,6 +976,7 @@ struct rq {unsigned char nohz_idle_balance;unsigned char idle_balance; +unsigned char last_idle_state;unsigned long misfit_task_load;@@ -1516,6 +1517,8 @@ static inline unsigned int group_first_cpu(struct sched_group *group)extern int group_balance_cpu (struct sched_group *sg); +void update_idle_cpumask (int cpu,bool set_idle); +#if defined(CONFIG_SCHED_DEBUG ) && defined(CONFIG_SYSCTL )void register_sched_domain_sysctl (void );void dirty_sched_domain_sysctl (int cpu);@@ -1536,6 +1539,7 @@ extern void flush_smp_call_function_from_idle(void);#else /* !CONFIG_SMP: */ static inline void flush_smp_call_function_from_idle (void ) { } +static inline void update_idle_cpumask (int cpu,bool set_idle) { }#endif #include "stats.h" kernel/sched/topology.c +2
-1@@ -1407,6 +1407,7 @@ sd_init(struct sched_domain_topology_level *tl, sd->shared = *per_cpu_ptr (sdd->sds, sd_id);atomic_inc (&sd->shared->ref);atomic_set (&sd->shared->nr_busy_cpus, sd_weight); +cpumask_copy (sds_idle_cpus (sd->shared),sched_domain_span (sd)); } sd->private = sdd;@@ -1769,7 +1770,7 @@ static int __sdt_alloc(const struct cpumask *cpu_map) *per_cpu_ptr (sdd->sd, j) = sd; - sds =kzalloc_node (sizeof (struct sched_domain_shared ), + sds =kzalloc_node (sizeof (struct sched_domain_shared ) +cpumask_size (),GFP_KERNEL ,cpu_to_node (j));if (!sds)return -ENOMEM ;Signature · 1 line
2.25.1
Quoted 93 lines · Vincent Guittot
Quoted 92 lines · Aubrey Li
Add idle cpumask to track idle cpus in sched domain. Every time a CPU enters idle, the CPU is set in idle cpumask to be a wakeup target. And if the CPU is not in idle, the CPU is cleared in idle cpumask during scheduler tick to ratelimit idle cpumask update.
When a task wakes up to select an idle cpu, scanning idle cpumask has lower cost than scanning all the cpus in last level cache domain, especially when the system is heavily loaded.
Benchmarks including hackbench, schbench, uperf, sysbench mysql and kbuild were tested on a x86 4 socket system with 24 cores per socket and 2 hyperthreads per core, total 192 CPUs, no regression found.
v6->v7:
- place the whole idle cpumask mechanism underCONFIG_SMP.
v5->v6:
- decouple idle cpumask update fromstop_ticksignal, set idle CPU in idle cpumask every time the CPU enters idle
v4->v5:
- addupdate_idle_cpumaskfor s2idle case
- keep the same ordering oftick_nohz_idle_stop_tick()andupdate_idle_cpumask()everywhere
v3->v4:
- change setting idle cpumask from every idle entry to tickless idle if cpu driver is available.
- move clearing idle cpumask toscheduler_tickto decouple nohz mode.
v2->v3:
- change setting idle cpumask to every idle entry, otherwise schbench has a regression of 99th percentile latency.
- change clearing idle cpumask tonohz_balancer_kick(), so updating idle cpumask is ratelimited in the idle exiting path.
- setSCHED_IDLEcpu in idle cpumask to allow it as a wakeup target.
v1->v2:
- idle cpumask is updated in the nohz routines, by initializing idle cpumask withsched_domain_span(sd), nohz=off case remains the original behavior.Cc Peter Zijlstra <[email protected]>Cc Mel Gorman <[email protected]>Cc Vincent Guittot <[email protected]>Cc Qais Yousef <[email protected]>Cc Valentin Schneider <[email protected]>Cc Jiang Biao <[email protected]>Cc Tim Chen <[email protected]>Signed-off-by Aubrey Li <[email protected]>--- include/linux/sched/topology.h | 13 +++++++++ kernel/sched/core.c | 2 ++ kernel/sched/fair.c | 51 +++++++++++++++++++++++++++++++++- kernel/sched/idle.c | 5 ++++ kernel/sched/sched.h | 4 +++ kernel/sched/topology.c | 3 +- 6 files changed, 76 insertions(+), 2 deletions(-)include/linux/sched/topology.h +13
-0@@ -65,8 +65,21 @@ struct sched_domain_shared {atomic_t ref;atomic_t nr_busy_cpus;int has_idle_cores; +/* +* Span of all idle CPUs in this domain. +* +* NOTE: this field is variable length. (Allocated dynamically +* by attaching extra space to the end of the structure, +* depending on how many CPUs the kernel has booted up with) +*/ +unsigned long idle_cpus_span[]; }; +static inline struct cpumask *sds_idle_cpus (struct sched_domain_shared *sds) +{ +return to_cpumask (sds->idle_cpus_span); +} +struct sched_domain {/* These fields must be setup */ struct sched_domain __rcu *parent;/* top domain must be null terminated */ kernel/sched/core.c +0
-0@@ -4011,6 +4011,7 @@ void scheduler_tick(void)
Quoted 6 lines
kernel/sched/core.c void scheduler_tick(void) · line 4014
Quoted 3 lines
kernel/sched/core.c +1
-0#ifdef CONFIG_SMP rq->idle_balance =idle_cpu (cpu); +update_idle_cpumask (cpu, false);Test
rq->idle_balancehere instead of adding the test inupdate_idle_cpumaskwhich is only relevant for this situation.
If called from idle path, because !set_idle is false, rq->idle_balance won't be tested actually.
if (!set_idle && rq->idle_balance) return;
So is it okay to leave it here to keep scheduler_tick a bit concise?
Thanks,
-Aubrey
Vincent Guittot
maintainerQuoted 102 lines · Aubrey
Quoted 93 lines · Vincent Guittot
Quoted 92 lines · Aubrey Li
Add idle cpumask to track idle cpus in sched domain. Every time a CPU enters idle, the CPU is set in idle cpumask to be a wakeup target. And if the CPU is not in idle, the CPU is cleared in idle cpumask during scheduler tick to ratelimit idle cpumask update.
When a task wakes up to select an idle cpu, scanning idle cpumask has lower cost than scanning all the cpus in last level cache domain, especially when the system is heavily loaded.
Benchmarks including hackbench, schbench, uperf, sysbench mysql and kbuild were tested on a x86 4 socket system with 24 cores per socket and 2 hyperthreads per core, total 192 CPUs, no regression found.
v6->v7:
- place the whole idle cpumask mechanism underCONFIG_SMP.
v5->v6:
- decouple idle cpumask update fromstop_ticksignal, set idle CPU in idle cpumask every time the CPU enters idle
v4->v5:
- addupdate_idle_cpumaskfor s2idle case
- keep the same ordering oftick_nohz_idle_stop_tick()andupdate_idle_cpumask()everywhere
v3->v4:
- change setting idle cpumask from every idle entry to tickless idle if cpu driver is available.
- move clearing idle cpumask toscheduler_tickto decouple nohz mode.
v2->v3:
- change setting idle cpumask to every idle entry, otherwise schbench has a regression of 99th percentile latency.
- change clearing idle cpumask tonohz_balancer_kick(), so updating idle cpumask is ratelimited in the idle exiting path.
- setSCHED_IDLEcpu in idle cpumask to allow it as a wakeup target.
v1->v2:
- idle cpumask is updated in the nohz routines, by initializing idle cpumask withsched_domain_span(sd), nohz=off case remains the original behavior.Cc Peter Zijlstra <[email protected]>Cc Mel Gorman <[email protected]>Cc Vincent Guittot <[email protected]>Cc Qais Yousef <[email protected]>Cc Valentin Schneider <[email protected]>Cc Jiang Biao <[email protected]>Cc Tim Chen <[email protected]>Signed-off-by Aubrey Li <[email protected]>--- include/linux/sched/topology.h | 13 +++++++++ kernel/sched/core.c | 2 ++ kernel/sched/fair.c | 51 +++++++++++++++++++++++++++++++++- kernel/sched/idle.c | 5 ++++ kernel/sched/sched.h | 4 +++ kernel/sched/topology.c | 3 +- 6 files changed, 76 insertions(+), 2 deletions(-)include/linux/sched/topology.h +13
-0@@ -65,8 +65,21 @@ struct sched_domain_shared {atomic_t ref;atomic_t nr_busy_cpus;int has_idle_cores; +/* +* Span of all idle CPUs in this domain. +* +* NOTE: this field is variable length. (Allocated dynamically +* by attaching extra space to the end of the structure, +* depending on how many CPUs the kernel has booted up with) +*/ +unsigned long idle_cpus_span[]; }; +static inline struct cpumask *sds_idle_cpus (struct sched_domain_shared *sds) +{ +return to_cpumask (sds->idle_cpus_span); +} +struct sched_domain {/* These fields must be setup */ struct sched_domain __rcu *parent;/* top domain must be null terminated */ kernel/sched/core.c +0
-0@@ -4011,6 +4011,7 @@ void scheduler_tick(void)Quoted 6 lines
kernel/sched/core.c void scheduler_tick(void) · line 4014
Quoted 3 lines
kernel/sched/core.c +1
-0#ifdef CONFIG_SMP rq->idle_balance =idle_cpu (cpu); +update_idle_cpumask (cpu, false);Test
rq->idle_balancehere instead of adding the test inupdate_idle_cpumaskwhich is only relevant for this situation.
Quoted 6 lines
If called from idle path, because !set_idle is false,
rq->idle_balancewon't be tested actually.if (!set_idle && rq->idle_balance) return;So is it okay to leave it here to keep
scheduler_ticka bit concise?
I don't like having a tick specific condition in a generic function. rq->idle_balance is only relevant in this case
calling update_idle_cpumask(rq->idle_balance) in scheduler_tick() should do the job and we can remove the check of rq->idle_balance in update_idle_cpumask()
In case of scheduler_tick() called when idle , we will only test if (rq->last_idle_state == idle_state) and return
Quoted 3 lines
Thanks,
-Aubrey
Quoted 113 lines · Vincent Guittot
Quoted 102 lines · Aubrey
Quoted 93 lines · Vincent Guittot
Quoted 92 lines · Aubrey Li
Add idle cpumask to track idle cpus in sched domain. Every time a CPU enters idle, the CPU is set in idle cpumask to be a wakeup target. And if the CPU is not in idle, the CPU is cleared in idle cpumask during scheduler tick to ratelimit idle cpumask update.
When a task wakes up to select an idle cpu, scanning idle cpumask has lower cost than scanning all the cpus in last level cache domain, especially when the system is heavily loaded.
Benchmarks including hackbench, schbench, uperf, sysbench mysql and kbuild were tested on a x86 4 socket system with 24 cores per socket and 2 hyperthreads per core, total 192 CPUs, no regression found.
v6->v7:
- place the whole idle cpumask mechanism underCONFIG_SMP.
v5->v6:
- decouple idle cpumask update fromstop_ticksignal, set idle CPU in idle cpumask every time the CPU enters idle
v4->v5:
- addupdate_idle_cpumaskfor s2idle case
- keep the same ordering oftick_nohz_idle_stop_tick()andupdate_idle_cpumask()everywhere
v3->v4:
- change setting idle cpumask from every idle entry to tickless idle if cpu driver is available.
- move clearing idle cpumask toscheduler_tickto decouple nohz mode.
v2->v3:
- change setting idle cpumask to every idle entry, otherwise schbench has a regression of 99th percentile latency.
- change clearing idle cpumask tonohz_balancer_kick(), so updating idle cpumask is ratelimited in the idle exiting path.
- setSCHED_IDLEcpu in idle cpumask to allow it as a wakeup target.
v1->v2:
- idle cpumask is updated in the nohz routines, by initializing idle cpumask withsched_domain_span(sd), nohz=off case remains the original behavior.Cc Peter Zijlstra <[email protected]>Cc Mel Gorman <[email protected]>Cc Vincent Guittot <[email protected]>Cc Qais Yousef <[email protected]>Cc Valentin Schneider <[email protected]>Cc Jiang Biao <[email protected]>Cc Tim Chen <[email protected]>Signed-off-by Aubrey Li <[email protected]>--- include/linux/sched/topology.h | 13 +++++++++ kernel/sched/core.c | 2 ++ kernel/sched/fair.c | 51 +++++++++++++++++++++++++++++++++- kernel/sched/idle.c | 5 ++++ kernel/sched/sched.h | 4 +++ kernel/sched/topology.c | 3 +- 6 files changed, 76 insertions(+), 2 deletions(-)include/linux/sched/topology.h +13
-0@@ -65,8 +65,21 @@ struct sched_domain_shared {atomic_t ref;atomic_t nr_busy_cpus;int has_idle_cores; +/* +* Span of all idle CPUs in this domain. +* +* NOTE: this field is variable length. (Allocated dynamically +* by attaching extra space to the end of the structure, +* depending on how many CPUs the kernel has booted up with) +*/ +unsigned long idle_cpus_span[]; }; +static inline struct cpumask *sds_idle_cpus (struct sched_domain_shared *sds) +{ +return to_cpumask (sds->idle_cpus_span); +} +struct sched_domain {/* These fields must be setup */ struct sched_domain __rcu *parent;/* top domain must be null terminated */ kernel/sched/core.c +0
-0@@ -4011,6 +4011,7 @@ void scheduler_tick(void)Quoted 6 lines
kernel/sched/core.c void scheduler_tick(void) · line 4014
Quoted 3 lines
kernel/sched/core.c +1
-0#ifdef CONFIG_SMP rq->idle_balance =idle_cpu (cpu); +update_idle_cpumask (cpu, false);Test
rq->idle_balancehere instead of adding the test inupdate_idle_cpumaskwhich is only relevant for this situation.Quoted 6 lines
If called from idle path, because !set_idle is false,
rq->idle_balancewon't be tested actually.if (!set_idle && rq->idle_balance) return;So is it okay to leave it here to keep
scheduler_ticka bit concise?I don't like having a tick specific condition in a generic function.
rq->idle_balanceis only relevant in this case
Quoted 7 lines
calling
update_idle_cpumask(rq->idle_balance)inscheduler_tick()should do the job and we can remove the check ofrq->idle_balanceinupdate_idle_cpumask()In case of
scheduler_tick()called when idle , we will only test if (rq->last_idle_state==idle_state) and return
I see, will come up with a v8 soon.
Thanks,
-Aubrey
Quoted 5 lines · Aubrey Li
Add idle cpumask to track idle cpus in sched domain. Every time a CPU enters idle, the CPU is set in idle cpumask to be a wakeup target. And if the CPU is not in idle, the CPU is cleared in idle cpumask during scheduler tick to ratelimit idle cpumask update.
Quoted 9 lines
When a task wakes up to select an idle cpu, scanning idle cpumask has lower cost than scanning all the cpus in last level cache domain, especially when the system is heavily loaded.
Benchmarks including hackbench, schbench, uperf, sysbench mysql and kbuild were tested on a x86 4 socket system with 24 cores per socket and 2 hyperthreads per core, total 192 CPUs, no regression found.
I ran this patch with tbench on top of of the schedstat patches that track SIS efficiency. The tracking adds overhead so it's not a perfect performance comparison but the expectation would be that the patch reduces the number of runqueues that are scanned
tbench4
5.10.0-rc6 5.10.0-rc6
schedstat-v1r1 idlemask-v7r1
Hmean 1 504.76 ( 0.00%) 500.14 * -0.91%*
Hmean 2 1001.22 ( 0.00%) 970.37 * -3.08%*
Hmean 4 1930.56 ( 0.00%) 1880.96 * -2.57%*
Hmean 8 3688.05 ( 0.00%) 3537.72 * -4.08%*
Hmean 16 6352.71 ( 0.00%) 6439.53 * 1.37%*
Hmean 32 10066.37 ( 0.00%) 10124.65 * 0.58%*
Hmean 64 12846.32 ( 0.00%) 11627.27 * -9.49%*
Hmean 128 22278.41 ( 0.00%) 22304.33 * 0.12%*
Hmean 256 21455.52 ( 0.00%) 20900.13 * -2.59%*
Hmean 320 21802.38 ( 0.00%) 21928.81 * 0.58%*Not very optimistic result. The schedstats indicate;
5.10.0-rc6 5.10.0-rc6
schedstat-v1r1 idlemask-v7r1
Ops TTWU Count 5599714302.00 5589495123.00
Ops TTWU Local 2687713250.00 2563662550.00
Ops SIS Search 5596677950.00 5586381168.00
Ops SIS Domain Search 3268344934.00 3229088045.00
Ops SIS Scanned 15909069113.00 16568899405.00
Ops SIS Domain Scanned 13580736097.00 14211606282.00
Ops SIS Failures 2944874939.00 2843113421.00
Ops SIS Core Search 262853975.00 311781774.00
Ops SIS Core Hit 185189656.00 216097102.00
Ops SIS Core Miss 77664319.00 95684672.00
Ops SIS Recent Used Hit 124265515.00 146021086.00
Ops SIS Recent Used Miss 338142547.00 403547579.00
Ops SIS Recent Attempts 462408062.00 549568665.00
Ops SIS Search Efficiency 35.18 33.72
Ops SIS Domain Search Eff 24.07 22.72
Ops SIS Fast Success Rate 41.60 42.20
Ops SIS Success Rate 47.38 49.11
Ops SIS Recent Success Rate 26.87 26.57The field I would expect to decrease is SIS Domain Scanned -- the number of runqueues that were examined but it's actually worse and graphing over time shows it's worse for the client thread counts. select_idle_cpu() is definitely being called because "Domain Search" is 10 times higher than "Core Search" and there "Core Miss" is non-zero.
I suspect the issue is that the mask is only marked busy from the tick context which is a very wide window. If select_idle_cpu() picks an idle CPU from the mask, it's still marked as idle in the mask.
Signature · 2 lines
Mel Gorman SUSE Labs
Hi Mel,
Quoted 16 lines · Mel Gorman
Quoted 5 lines · Aubrey Li
Add idle cpumask to track idle cpus in sched domain. Every time a CPU enters idle, the CPU is set in idle cpumask to be a wakeup target. And if the CPU is not in idle, the CPU is cleared in idle cpumask during scheduler tick to ratelimit idle cpumask update.
Quoted 9 lines
When a task wakes up to select an idle cpu, scanning idle cpumask has lower cost than scanning all the cpus in last level cache domain, especially when the system is heavily loaded.
Benchmarks including hackbench, schbench, uperf, sysbench mysql and kbuild were tested on a x86 4 socket system with 24 cores per socket and 2 hyperthreads per core, total 192 CPUs, no regression found.
Quoted 4 lines
I ran this patch with tbench on top of of the schedstat patches that track SIS efficiency. The tracking adds overhead so it's not a perfect performance comparison but the expectation would be that the patch reduces the number of runqueues that are scanned
Thanks for the measurement! I don't play with tbench so may need a while to digest the data.
Quoted 15 lines
tbench4
5.10.0-rc6 5.10.0-rc6 schedstat-v1r1 idlemask-v7r1 Hmean 1 504.76 ( 0.00%) 500.14 * -0.91%* Hmean 2 1001.22 ( 0.00%) 970.37 * -3.08%* Hmean 4 1930.56 ( 0.00%) 1880.96 * -2.57%* Hmean 8 3688.05 ( 0.00%) 3537.72 * -4.08%* Hmean 16 6352.71 ( 0.00%) 6439.53 * 1.37%* Hmean 32 10066.37 ( 0.00%) 10124.65 * 0.58%* Hmean 64 12846.32 ( 0.00%) 11627.27 * -9.49%* Hmean 128 22278.41 ( 0.00%) 22304.33 * 0.12%* Hmean 256 21455.52 ( 0.00%) 20900.13 * -2.59%* Hmean 320 21802.38 ( 0.00%) 21928.81 * 0.58%*
Quoted 1 line
Not very optimistic result. The schedstats indicate;
How many client threads was the following schedstats collected?
Quoted 22 lines
5.10.0-rc6 5.10.0-rc6
schedstat-v1r1 idlemask-v7r1
Ops TTWU Count 5599714302.00 5589495123.00
Ops TTWU Local 2687713250.00 2563662550.00
Ops SIS Search 5596677950.00 5586381168.00
Ops SIS Domain Search 3268344934.00 3229088045.00
Ops SIS Scanned 15909069113.00 16568899405.00
Ops SIS Domain Scanned 13580736097.00 14211606282.00
Ops SIS Failures 2944874939.00 2843113421.00
Ops SIS Core Search 262853975.00 311781774.00
Ops SIS Core Hit 185189656.00 216097102.00
Ops SIS Core Miss 77664319.00 95684672.00
Ops SIS Recent Used Hit 124265515.00 146021086.00
Ops SIS Recent Used Miss 338142547.00 403547579.00
Ops SIS Recent Attempts 462408062.00 549568665.00
Ops SIS Search Efficiency 35.18 33.72
Ops SIS Domain Search Eff 24.07 22.72
Ops SIS Fast Success Rate 41.60 42.20
Ops SIS Success Rate 47.38 49.11
Ops SIS Recent Success Rate 26.87 26.57Quoted 5 lines
The field I would expect to decrease is SIS Domain Scanned -- the number of runqueues that were examined but it's actually worse and graphing over time shows it's worse for the client thread counts.
select_idle_cpu()is definitely being called because "Domain Search" is 10 times higher than "Core Search" and there "Core Miss" is non-zero.
Why SIS Domain Scanned can be decreased?
I thought SIS Scanned was supposed to be decreased but it seems not on your side.
I printed some trace log on my side by uperf workload, and it looks properly. To make the log easy to read, I started a 4 VCPU VM to run 2-second uperf 8 threads.
stage 1: system idle, update_idle_cpumask is called from idle thread, set cpumask to 0-3
========================================================================================
<idle>-0 [002] d..1 137.408681: update_idle_cpumask: set_idle-1, cpumask: 2
<idle>-0 [000] d..1 137.408713: update_idle_cpumask: set_idle-1, cpumask: 0,2
<idle>-0 [003] d..1 137.408924: update_idle_cpumask: set_idle-1, cpumask: 0,2-3
<idle>-0 [001] d..1 137.409035: update_idle_cpumask: set_idle-1, cpumask: 0-3stage 2: uperf ramp up, cpumask changes back and forth
========================================================
uperf-561 [003] d..3 137.410620: select_task_rq_fair: scanning: 0-3
uperf-560 [000] d..5 137.411384: select_task_rq_fair: scanning: 0-3
kworker/u8:3-110 [000] d..4 137.411436: select_task_rq_fair: scanning: 0-3
uperf-560 [000] d.h1 137.412562: update_idle_cpumask: set_idle-0, cpumask: 1-3
uperf-570 [002] d.h2 137.412580: update_idle_cpumask: set_idle-0, cpumask: 1,3
<idle>-0 [002] d..1 137.412917: update_idle_cpumask: set_idle-1, cpumask: 1-3
<idle>-0 [000] d..1 137.413004: update_idle_cpumask: set_idle-1, cpumask: 0-3
uperf-560 [000] d..5 137.415856: select_task_rq_fair: scanning: 0-3
kworker/u8:3-110 [001] d..4 137.415956: select_task_rq_fair: scanning: 0-3
sshd-504 [003] d.h1 137.416562: update_idle_cpumask: set_idle-0, cpumask: 0-2
uperf-560 [000] d.h1 137.416598: update_idle_cpumask: set_idle-0, cpumask: 1-2
<idle>-0 [003] d..1 137.416638: update_idle_cpumask: set_idle-1, cpumask: 1-3
<idle>-0 [000] d..1 137.417076: update_idle_cpumask: set_idle-1, cpumask: 0-3
tmux: server-528 [001] d.h. 137.448566: update_idle_cpumask: set_idle-0, cpumask: 0,2-3
<idle>-0 [001] d..1 137.448980: update_idle_cpumask: set_idle-1, cpumask: 0-3stage 3: uperf running, select_idle_cpu scan all the CPUs in the scheduler domain at the beginning
===================================================================================================
uperf-560 [000] d..3 138.418494: select_task_rq_fair: scanning: 0-3
uperf-560 [000] d..3 138.418506: select_task_rq_fair: scanning: 0-3
uperf-560 [000] d..3 138.418514: select_task_rq_fair: scanning: 0-3
uperf-560 [000] dN.3 138.418534: select_task_rq_fair: scanning: 0-3
uperf-560 [000] dN.3 138.418543: select_task_rq_fair: scanning: 0-3
uperf-560 [000] dN.3 138.418551: select_task_rq_fair: scanning: 0-3
uperf-561 [003] d..3 138.418577: select_task_rq_fair: scanning: 0-3
uperf-561 [003] d..3 138.418600: select_task_rq_fair: scanning: 0-3
uperf-561 [003] d..3 138.418617: select_task_rq_fair: scanning: 0-3
uperf-561 [003] d..3 138.418640: select_task_rq_fair: scanning: 0-3
uperf-561 [003] d..3 138.418652: select_task_rq_fair: scanning: 0-3
uperf-561 [003] d..3 138.418662: select_task_rq_fair: scanning: 0-3
uperf-561 [003] d..3 138.418672: select_task_rq_fair: scanning: 0-3
uperf-560 [000] d..5 138.418676: select_task_rq_fair: scanning: 0-3
uperf-561 [003] d..3 138.418693: select_task_rq_fair: scanning: 0-3
kworker/u8:3-110 [002] d..4 138.418746: select_task_rq_fair: scanning: 0-3stage 4: scheduler tick comes, update idle cpumask to EMPTY
============================================================
uperf-572 [002] d.h. 139.420568: update_idle_cpumask: set_idle-0, cpumask: 1,3
uperf-574 [000] d.H2 139.420568: update_idle_cpumask: set_idle-0, cpumask: 1,3
uperf-565 [003] d.H6 139.420569: update_idle_cpumask: set_idle-0, cpumask: 1
tmux: server-528 [001] d.h2 139.420572: update_idle_cpumask: set_idle-0, cpumask: stage 5: uperf continue running, select_idle_cpu does not scan idle cpu
========================================================================
<I only run 2 seconds uperf, during this two seconds, no idle cpu in cpumask to scan>
uperf-565 [003] d.sa 139.420587: select_task_rq_fair: scanning:
uperf-572 [002] d.sa 139.420670: select_task_rq_fair: scanning:
............
uperf-561 [003] d..5 141.421620: select_task_rq_fair: scanning:
uperf-571 [001] d.sa 141.421630: select_task_rq_fair: scanning: stage 6: uperf benchmark finished, idle thread switch on
=========================================================
<idle>-0 [002] d..1 141.421631: update_idle_cpumask: set_idle-1, cpumask: 2
<idle>-0 [000] d..1 141.421654: update_idle_cpumask: set_idle-1, cpumask: 0,2
<idle>-0 [001] d..1 141.421665: update_idle_cpumask: set_idle-1, cpumask: 0-2
uperf-561 [003] d..5 141.421712: select_task_rq_fair: scanning: 0-2
<idle>-0 [003] d..1 141.421807: update_idle_cpumask: set_idle-1, cpumask: 0-3stage 7: uperf ramp down
==========================
uperf-560 [000] d..5 141.423075: select_task_rq_fair: scanning: 0-3
uperf-560 [000] d..5 141.423107: select_task_rq_fair: scanning: 0-3
uperf-560 [000] d..5 141.423259: select_task_rq_fair: scanning: 0-3
tmux: server-528 [002] d..5 141.730489: select_task_rq_fair: scanning: 1-3
kworker/u8:1-96 [003] d..4 141.731924: select_task_rq_fair: scanning: 1-3
<idle>-0 [000] d..1 141.734560: update_idle_cpumask: set_idle-1, cpumask: 0-3
tmux: server-528 [002] d.h1 141.736568: update_idle_cpumask: set_idle-0, cpumask: 0-1
uperf.sh-558 [003] d.h. 141.736570: update_idle_cpumask: set_idle-0, cpumask: 0-1
<idle>-0 [002] d..1 141.736718: update_idle_cpumask: set_idle-1, cpumask: 0-2
<idle>-0 [003] d..1 141.738179: update_idle_cpumask: set_idle-1, cpumask: 0-3
pkill-578 [001] d.h1 141.740569: update_idle_cpumask: set_idle-0, cpumask: 0,2-3
<idle>-0 [001] d..1 141.741875: update_idle_cpumask: set_idle-1, cpumask: 0-3
pkill-578 [001] d.h. 141.744570: update_idle_cpumask: set_idle-0, cpumask: 0,2-3
pkill-578 [001] d..6 141.770012: select_task_rq_fair: scanning: 0,2-3
<idle>-0 [001] d..1 141.770938: update_idle_cpumask: set_idle-1, cpumask: 0-3In this case, SIS Scanned should be decreased. I'll apply your schedstat patch to see if the data matches.
Quoted 5 lines
I suspect the issue is that the mask is only marked busy from the tick context which is a very wide window. If
select_idle_cpu()picks an idle CPU from the mask, it's still marked as idle in the mask.
That should be fine because we still check available_idle_cpu() and sched_idle_cpu for the selected CPU. And even if that CPU is marked as idle in the mask, that mask should not be worse(bigger) than the default sched_domain_span(sd).
Thanks,
-Aubrey
Quoted 8 lines · Aubrey
Quoted 4 lines
I ran this patch with tbench on top of of the schedstat patches that track SIS efficiency. The tracking adds overhead so it's not a perfect performance comparison but the expectation would be that the patch reduces the number of runqueues that are scanned
Thanks for the measurement! I don't play with tbench so may need a while to digest the data.
They key point is that it appears the idle mask was mostly equivalent to the full domain mask, at least for this test.
Quoted 15 lines
Quoted 15 lines
tbench4
5.10.0-rc6 5.10.0-rc6 schedstat-v1r1 idlemask-v7r1 Hmean 1 504.76 ( 0.00%) 500.14 * -0.91%* Hmean 2 1001.22 ( 0.00%) 970.37 * -3.08%* Hmean 4 1930.56 ( 0.00%) 1880.96 * -2.57%* Hmean 8 3688.05 ( 0.00%) 3537.72 * -4.08%* Hmean 16 6352.71 ( 0.00%) 6439.53 * 1.37%* Hmean 32 10066.37 ( 0.00%) 10124.65 * 0.58%* Hmean 64 12846.32 ( 0.00%) 11627.27 * -9.49%* Hmean 128 22278.41 ( 0.00%) 22304.33 * 0.12%* Hmean 256 21455.52 ( 0.00%) 20900.13 * -2.59%* Hmean 320 21802.38 ( 0.00%) 21928.81 * 0.58%*
Quoted 4 lines
Quoted 1 line
Not very optimistic result. The schedstats indicate;
How many client threads was the following schedstats collected?
That's the overall summary for all client counts. While proc-schedstat was measured every few seconds over all client counts, presenting that in text format is not easy to parse. However, looking at the graphs over time, it did not appear that scan rates were consistently lower for any client count for tbench.
Quoted 22 lines
Quoted 22 lines
5.10.0-rc6 5.10.0-rc6 schedstat-v1r1 idlemask-v7r1 Ops TTWU Count 5599714302.00 5589495123.00 Ops TTWU Local 2687713250.00 2563662550.00 Ops SIS Search 5596677950.00 5586381168.00 Ops SIS Domain Search 3268344934.00 3229088045.00 Ops SIS Scanned 15909069113.00 16568899405.00 Ops SIS Domain Scanned 13580736097.00 14211606282.00 Ops SIS Failures 2944874939.00 2843113421.00 Ops SIS Core Search 262853975.00 311781774.00 Ops SIS Core Hit 185189656.00 216097102.00 Ops SIS Core Miss 77664319.00 95684672.00 Ops SIS Recent Used Hit 124265515.00 146021086.00 Ops SIS Recent Used Miss 338142547.00 403547579.00 Ops SIS Recent Attempts 462408062.00 549568665.00 Ops SIS Search Efficiency 35.18 33.72 Ops SIS Domain Search Eff 24.07 22.72 Ops SIS Fast Success Rate 41.60 42.20 Ops SIS Success Rate 47.38 49.11 Ops SIS Recent Success Rate 26.87 26.57
Quoted 8 lines
Quoted 5 lines
The field I would expect to decrease is SIS Domain Scanned -- the number of runqueues that were examined but it's actually worse and graphing over time shows it's worse for the client thread counts.
select_idle_cpu()is definitely being called because "Domain Search" is 10 times higher than "Core Search" and there "Core Miss" is non-zero.Why SIS Domain Scanned can be decreased?
Because if idle CPUs are being targetted and its a subset of the entire domain then it follows that fewer runqueues should be examined when scanning the domain.
Quoted 2 lines
I thought SIS Scanned was supposed to be decreased but it seems not on your side.
It *should* have been decreased but it's indicating that more runqueues were scanned with the patch. It should be noted that the scan count is naturally variable because the depth of each individual search is variable.
Quoted 10 lines
I printed some trace log on my side by uperf workload, and it looks properly. To make the log easy to read, I started a 4 VCPU VM to run 2-second uperf 8 threads.
stage 1: system idle,
update_idle_cpumaskis called from idle thread, set cpumask to 0-3
========================================================================================<idle>-0 [002] d..1 137.408681: update_idle_cpumask: set_idle-1, cpumask: 2 <idle>-0 [000] d..1 137.408713: update_idle_cpumask: set_idle-1, cpumask: 0,2 <idle>-0 [003] d..1 137.408924: update_idle_cpumask: set_idle-1, cpumask: 0,2-3 <idle>-0 [001] d..1 137.409035: update_idle_cpumask: set_idle-1, cpumask: 0-3
What's the size of the LLC domain on this machine? If it's 4 then this is indicating that there is little difference between scanning the full domain and targetting idle CPUs via the idle cpumask.
Quoted 19 lines
stage 3: uperf running,
select_idle_cpuscan all the CPUs in the scheduler domain at the beginning
===================================================================================================uperf-560 [000] d..3 138.418494: select_task_rq_fair: scanning: 0-3 uperf-560 [000] d..3 138.418506: select_task_rq_fair: scanning: 0-3 uperf-560 [000] d..3 138.418514: select_task_rq_fair: scanning: 0-3 uperf-560 [000] dN.3 138.418534: select_task_rq_fair: scanning: 0-3 uperf-560 [000] dN.3 138.418543: select_task_rq_fair: scanning: 0-3 uperf-560 [000] dN.3 138.418551: select_task_rq_fair: scanning: 0-3 uperf-561 [003] d..3 138.418577: select_task_rq_fair: scanning: 0-3 uperf-561 [003] d..3 138.418600: select_task_rq_fair: scanning: 0-3 uperf-561 [003] d..3 138.418617: select_task_rq_fair: scanning: 0-3 uperf-561 [003] d..3 138.418640: select_task_rq_fair: scanning: 0-3 uperf-561 [003] d..3 138.418652: select_task_rq_fair: scanning: 0-3 uperf-561 [003] d..3 138.418662: select_task_rq_fair: scanning: 0-3 uperf-561 [003] d..3 138.418672: select_task_rq_fair: scanning: 0-3 uperf-560 [000] d..5 138.418676: select_task_rq_fair: scanning: 0-3 uperf-561 [003] d..3 138.418693: select_task_rq_fair: scanning: 0-3 kworker/u8:3-110 [002] d..4 138.418746: select_task_rq_fair: scanning: 0-3
Quoted 7 lines
stage 4: scheduler tick comes, update idle cpumask to EMPTY
============================================================uperf-572 [002] d.h. 139.420568: update_idle_cpumask: set_idle-0, cpumask: 1,3 uperf-574 [000] d.H2 139.420568: update_idle_cpumask: set_idle-0, cpumask: 1,3 uperf-565 [003] d.H6 139.420569: update_idle_cpumask: set_idle-0, cpumask: 1 tmux: server-528 [001] d.h2 139.420572: update_idle_cpumask: set_idle-0, cpumask:
It's the timing of the clear that may be problematic. For the configurations I use, the tick is every 4 milliseconds which is a very long time in the scheduler for communicating workloads. A simple round-trip of perf pipe where tasks will be entering/exiting rapidly is just 0.004 milliseconds on my desktop.
Quoted 9 lines
Quoted 5 lines
I suspect the issue is that the mask is only marked busy from the tick context which is a very wide window. If
select_idle_cpu()picks an idle CPU from the mask, it's still marked as idle in the mask.That should be fine because we still check
available_idle_cpu()andsched_idle_cpufor the selected CPU. And even if that CPU is marked as idle in the mask, that mask should not be worse(bigger) than the defaultsched_domain_span(sd).
I agree that it should never be worse/bigger but if the idle cpu mask is often the same bits as the sched_domain_span then it's not going to be any better either.
Signature · 2 lines
Mel Gorman SUSE Labs
Quoted 6 lines · Mel Gorman
Quoted 5 lines · Aubrey
Quoted 4 lines
I ran this patch with tbench on top of of the schedstat patches that track SIS efficiency. The tracking adds overhead so it's not a perfect performance comparison but the expectation would be that the patch reduces the number of runqueues that are scanned
Quoted 6 lines
Quoted 3 lines
Thanks for the measurement! I don't play with tbench so may need a while to digest the data.
They key point is that it appears the idle mask was mostly equivalent to the full domain mask, at least for this test.
I'm more interested in how tbench with heavy load behaves.
If the load is heavy enough and idle thread has no chance to switch in, idle cpumask will be empty at the first scheduler tick and remain empty before the load comes down, during this period of heavy load:
- default select_idle_cpu still scan the entire sched domain(or throttled to
4) everytime
- the patched select_idle_cpu does not scan at all
Quoted 55 lines
Quoted 16 lines
Quoted 16 lines
tbench4
5.10.0-rc6 5.10.0-rc6 schedstat-v1r1 idlemask-v7r1 Hmean 1 504.76 ( 0.00%) 500.14 * -0.91%* Hmean 2 1001.22 ( 0.00%) 970.37 * -3.08%* Hmean 4 1930.56 ( 0.00%) 1880.96 * -2.57%* Hmean 8 3688.05 ( 0.00%) 3537.72 * -4.08%* Hmean 16 6352.71 ( 0.00%) 6439.53 * 1.37%* Hmean 32 10066.37 ( 0.00%) 10124.65 * 0.58%* Hmean 64 12846.32 ( 0.00%) 11627.27 * -9.49%* Hmean 128 22278.41 ( 0.00%) 22304.33 * 0.12%* Hmean 256 21455.52 ( 0.00%) 20900.13 * -2.59%* Hmean 320 21802.38 ( 0.00%) 21928.81 * 0.58%*Quoted 4 lines
Quoted 1 line
Not very optimistic result. The schedstats indicate;
How many client threads was the following schedstats collected?
That's the overall summary for all client counts. While proc-schedstat was measured every few seconds over all client counts, presenting that in text format is not easy to parse. However, looking at the graphs over time, it did not appear that scan rates were consistently lower for any client count for tbench.
Quoted 28 lines
Quoted 27 lines
5.10.0-rc6 5.10.0-rc6 schedstat-v1r1 idlemask-v7r1 Ops TTWU Count 5599714302.00 5589495123.00 Ops TTWU Local 2687713250.00 2563662550.00 Ops SIS Search 5596677950.00 5586381168.00 Ops SIS Domain Search 3268344934.00 3229088045.00 Ops SIS Scanned 15909069113.00 16568899405.00 Ops SIS Domain Scanned 13580736097.00 14211606282.00 Ops SIS Failures 2944874939.00 2843113421.00 Ops SIS Core Search 262853975.00 311781774.00 Ops SIS Core Hit 185189656.00 216097102.00 Ops SIS Core Miss 77664319.00 95684672.00 Ops SIS Recent Used Hit 124265515.00 146021086.00 Ops SIS Recent Used Miss 338142547.00 403547579.00 Ops SIS Recent Attempts 462408062.00 549568665.00 Ops SIS Search Efficiency 35.18 33.72 Ops SIS Domain Search Eff 24.07 22.72 Ops SIS Fast Success Rate 41.60 42.20 Ops SIS Success Rate 47.38 49.11 Ops SIS Recent Success Rate 26.87 26.57The field I would expect to decrease is SIS Domain Scanned -- the number of runqueues that were examined but it's actually worse and graphing over time shows it's worse for the client thread counts.
select_idle_cpu()is definitely being called because "Domain Search" is 10 times higher than "Core Search" and there "Core Miss" is non-zero.
Quoted 6 lines
Quoted 2 lines
Why SIS Domain Scanned can be decreased?
Because if idle CPUs are being targetted and its a subset of the entire domain then it follows that fewer runqueues should be examined when scanning the domain.
Sorry, I probably messed up "SIS Domain Scanned" and "SIS Domain Search". How is "SIS Domain Scanned" calculated?
Quoted 7 lines
Quoted 3 lines
I thought SIS Scanned was supposed to be decreased but it seems not on your side.
It *should* have been decreased but it's indicating that more runqueues were scanned with the patch. It should be noted that the scan count is naturally variable because the depth of each individual search is variable.
I'm confused here, I saw 4 places to increase sis_scanned, so what's the difference between "SIS Domain Scanned" and "SIS scanned"?
select_idle_sibling(struct task_struct *p, int prev, int target) ---->schedstat_inc(this_rq()->sis_scanned);
select_idle_core(struct task_struct *p, struct sched_domain *sd, int ---->schedstat_inc(this_rq()->sis_scanned);
static int select_idle_smt(struct task_struct *p, struct sched_domain *sd, int t ---->schedstat_inc(this_rq()->sis_scanned);
select_idle_cpu(struct task_struct *p, struct sched_domain *sd, int t ---->schedstat_inc(this_rq()->sis_scanned);
Quoted 12 lines
Quoted 11 lines
I printed some trace log on my side by uperf workload, and it looks properly. To make the log easy to read, I started a 4 VCPU VM to run 2-second uperf 8 threads.
stage 1: system idle,
update_idle_cpumaskis called from idle thread, set cpumask to 0-3
========================================================================================<idle>-0 [002] d..1 137.408681: update_idle_cpumask: set_idle-1, cpumask: 2 <idle>-0 [000] d..1 137.408713: update_idle_cpumask: set_idle-1, cpumask: 0,2 <idle>-0 [003] d..1 137.408924: update_idle_cpumask: set_idle-1, cpumask: 0,2-3 <idle>-0 [001] d..1 137.409035: update_idle_cpumask: set_idle-1, cpumask: 0-3
Quoted 3 lines
What's the size of the LLC domain on this machine? If it's 4 then this is indicating that there is little difference between scanning the full domain and targetting idle CPUs via the idle cpumask.
But idle cpumask saves 4 loops of scanning runqueue everytime select_idle_cpu().
Quoted 28 lines
Quoted 20 lines
stage 3: uperf running,
select_idle_cpuscan all the CPUs in the scheduler domain at the beginning
===================================================================================================uperf-560 [000] d..3 138.418494: select_task_rq_fair: scanning: 0-3 uperf-560 [000] d..3 138.418506: select_task_rq_fair: scanning: 0-3 uperf-560 [000] d..3 138.418514: select_task_rq_fair: scanning: 0-3 uperf-560 [000] dN.3 138.418534: select_task_rq_fair: scanning: 0-3 uperf-560 [000] dN.3 138.418543: select_task_rq_fair: scanning: 0-3 uperf-560 [000] dN.3 138.418551: select_task_rq_fair: scanning: 0-3 uperf-561 [003] d..3 138.418577: select_task_rq_fair: scanning: 0-3 uperf-561 [003] d..3 138.418600: select_task_rq_fair: scanning: 0-3 uperf-561 [003] d..3 138.418617: select_task_rq_fair: scanning: 0-3 uperf-561 [003] d..3 138.418640: select_task_rq_fair: scanning: 0-3 uperf-561 [003] d..3 138.418652: select_task_rq_fair: scanning: 0-3 uperf-561 [003] d..3 138.418662: select_task_rq_fair: scanning: 0-3 uperf-561 [003] d..3 138.418672: select_task_rq_fair: scanning: 0-3 uperf-560 [000] d..5 138.418676: select_task_rq_fair: scanning: 0-3 uperf-561 [003] d..3 138.418693: select_task_rq_fair: scanning: 0-3 kworker/u8:3-110 [002] d..4 138.418746: select_task_rq_fair: scanning: 0-3Quoted 7 lines
stage 4: scheduler tick comes, update idle cpumask to EMPTY
============================================================uperf-572 [002] d.h. 139.420568: update_idle_cpumask: set_idle-0, cpumask: 1,3 uperf-574 [000] d.H2 139.420568: update_idle_cpumask: set_idle-0, cpumask: 1,3 uperf-565 [003] d.H6 139.420569: update_idle_cpumask: set_idle-0, cpumask: 1 tmux: server-528 [001] d.h2 139.420572: update_idle_cpumask: set_idle-0, cpumask:
Quoted 5 lines
It's the timing of the clear that may be problematic. For the configurations I use, the tick is every 4 milliseconds which is a very long time in the scheduler for communicating workloads. A simple round-trip of perf pipe where tasks will be entering/exiting rapidly is just 0.004 milliseconds on my desktop.
Agreed, but that's not the case this patch targeted. The target of this patch is the system load is heavy enough so that idle thread has no chance to be scheduled.
Quoted 6 lines
Quoted 6 lines
Quoted 6 lines
I suspect the issue is that the mask is only marked busy from the tick context which is a very wide window. If
select_idle_cpu()picks an idle CPU from the mask, it's still marked as idle in the mask.
Quoted 9 lines
Quoted 4 lines
That should be fine because we still check
available_idle_cpu()andsched_idle_cpufor the selected CPU. And even if that CPU is marked as idle in the mask, that mask should not be worse(bigger) than the defaultsched_domain_span(sd).I agree that it should never be worse/bigger but if the idle cpu mask is often the same bits as the
sched_domain_spanthen it's not going to be any better either.
At least on my side, v5 is easier to see the benefit, as rapidly entering and exiting idle will make idle governor to retain the tick, v5 uses stop_tick signal from idle governor to decide if this CPU is added to idle cpumask.
https://lore.kernel.org/lkml/[email protected]/
But as Vincent and Peter concerned, v5 may break the latency sensitive workload. Also the short idle definition need more work.
Thanks,
-Aubrey
Quoted 10 lines · Aubrey
Quoted 10 lines
Quoted 9 lines
Quoted 6 lines
The field I would expect to decrease is SIS Domain Scanned -- the number of runqueues that were examined but it's actually worse and graphing over time shows it's worse for the client thread counts.
select_idle_cpu()is definitely being called because "Domain Search" is 10 times higher than "Core Search" and there "Core Miss" is non-zero.Why SIS Domain Scanned can be decreased?
Quoted 7 lines
Quoted 3 lines
Because if idle CPUs are being targetted and its a subset of the entire domain then it follows that fewer runqueues should be examined when scanning the domain.
Sorry, I probably messed up "SIS Domain Scanned" and "SIS Domain Search". How is "SIS Domain Scanned" calculated?
my $fast_search = $sis_search - $sis_domain_search;
my $domain_scanned = $sis_scanned - $fast_search;The difference is margainal. The "fast" search is the checking of target, prev and recent as described in this hunk
@@ -6246,6 +6249,15 @@ static int select_idle_sibling(struct task_struct *p, int prev, int target)
unsigned long task_util;
int i, recent_used_cpu;+ schedstat_inc(this_rq()->sis_search);
+
+ /*
+ * Checking if prev, target and recent is treated as one scan. A + * perfect hit on one of those is considered 100% efficiency. + * Further scanning impairs efficiency. + */
+ schedstat_inc(this_rq()->sis_scanned);
+
/*
* On asymmetric system, update task utilization because we will check
* that the task fits with cpu's capacity.
For your patch, the fast path is irrelevant. I cared at one point because I was looking at the hit rate for recent_cpu_used so any improvement there would reduce the number of runqueues scanned in select_idle_[core|cpu|smt].
Quoted 10 lines
Quoted 6 lines
Quoted 2 lines
I thought SIS Scanned was supposed to be decreased but it seems not on your side.
It *should* have been decreased but it's indicating that more runqueues were scanned with the patch. It should be noted that the scan count is naturally variable because the depth of each individual search is variable.
I'm confused here, I saw 4 places to increase
sis_scanned, so what's the difference between "SIS Domain Scanned" and "SIS scanned"?
Domain scanned is the scans within select_idle_[core|cpu|smt]. SIS scanned accounts for the checking of prev, target and recent. Your patch does not care about the fast path which is perfectly fine. The fast path is only really relevant when modifying how p->recent_used_cpu is used.
However, there should be some evidence that the patch reduces the amount of scanning even it's workload-specific.
Quoted 11 lines
Quoted 11 lines
Quoted 10 lines
I printed some trace log on my side by uperf workload, and it looks properly. To make the log easy to read, I started a 4 VCPU VM to run 2-second uperf 8 threads.
stage 1: system idle,
update_idle_cpumaskis called from idle thread, set cpumask to 0-3
========================================================================================<idle>-0 [002] d..1 137.408681: update_idle_cpumask: set_idle-1, cpumask: 2 <idle>-0 [000] d..1 137.408713: update_idle_cpumask: set_idle-1, cpumask: 0,2 <idle>-0 [003] d..1 137.408924: update_idle_cpumask: set_idle-1, cpumask: 0,2-3 <idle>-0 [001] d..1 137.409035: update_idle_cpumask: set_idle-1, cpumask: 0-3
Quoted 6 lines
Quoted 3 lines
What's the size of the LLC domain on this machine? If it's 4 then this is indicating that there is little difference between scanning the full domain and targetting idle CPUs via the idle cpumask.
But idle cpumask saves 4 loops of scanning runqueue everytime
select_idle_cpu().
I don't follow. If sds_idle_cpus(sd->shared) == sched_domain_span(sd) then there are no savings.
Quoted 10 lines
Quoted 5 lines
It's the timing of the clear that may be problematic. For the configurations I use, the tick is every 4 milliseconds which is a very long time in the scheduler for communicating workloads. A simple round-trip of perf pipe where tasks will be entering/exiting rapidly is just 0.004 milliseconds on my desktop.
Agreed, but that's not the case this patch targeted. The target of this patch is the system load is heavy enough so that idle thread has no chance to be scheduled.
That's somewhat more marginal as a benefit but fair enough. I took a closer look at the scan rates for 320 clients which loads the machine fairly heavily. mpstat is reported 0% idle time but the domain scanned with or without the patch is almost identical which hints that scans were not avoided. As I write this, hackbench has not executed yet to see if it makes a difference but it's in the queue.
Quoted 5 lines
Quoted 4 lines
I agree that it should never be worse/bigger but if the idle cpu mask is often the same bits as the
sched_domain_spanthen it's not going to be any better either.
Quoted 8 lines
At least on my side, v5 is easier to see the benefit, as rapidly entering and exiting idle will make idle governor to retain the tick, v5 uses
stop_ticksignal from idle governor to decide if this CPU is added to idle cpumask.
https://lore.kernel.org/lkml/[email protected]/But as Vincent and Peter concerned, v5 may break the latency sensitive workload. Also the short idle definition need more work.
Indeed, this is why I was advocating an approach that would use the idle CPU mask as a hint to quickly find idle CPUs but still fall through the scan the rest of the domain if necessary. That would cover the "latency sensitive" workload situation because a deeper scan still happens if necessary. While I'm not 100% certain, they were probably thinking about schbench which favours deep searches for idle CPUs and is latency sensitive.
The prequisite patch to make that approach work was rejected though as on its own, it's not very helpful and Vincent didn't like that the load_balance_mask was abused to make it effective.
Signature · 2 lines
Mel Gorman SUSE Labs
Peter Zijlstra
maintainerQuoted 3 lines · Mel Gorman
The prequisite patch to make that approach work was rejected though as on its own, it's not very helpful and Vincent didn't like that the
load_balance_maskwas abused to make it effective.
So last time I poked at all this, I found that using more masks was a performance issue as well due to added cache misses.
Anyway, I finally found some time to look at all this, and while reading over the whole SiS crud to refresh the brain came up with the below...
It's still naf, but at least it gets rid of a bunch of duplicate scanning and LoC decreases, so it should be awesome. Ofcourse, as always, benchmarks will totally ruin everything, we'll see, I started some.
It goes on top of Mel's first two patches (which is about as far as I got)...
--- fair.c | 124 ++++++++++++++++++++++++----------------------------------------- 1 file changed, 47 insertions(+), 77 deletions(-)
kernel/sched/fair.c +47 -77
@@ -6021,11 +6021,13 @@ static inline void set_idle_cores(int cpstatic inline bool test_idle_cores (int cpu,bool def) { -struct sched_domain_shared *sds; +if (static_branch_likely (&sched_smt_present)) { +struct sched_domain_shared *sds; - sds =rcu_dereference (per_cpu (sd_llc_shared, cpu)); -if (sds) -return READ_ONCE (sds->has_idle_cores); + sds =rcu_dereference (per_cpu (sd_llc_shared, cpu)); +if (sds) +return READ_ONCE (sds->has_idle_cores); + }return def; }
@@ -6059,77 +6061,39 @@ void __update_idle_core(struct rq *rq)rcu_read_unlock (); } -/* -* Scan the entire LLC domain for idle cores; this dynamically switches off if -* there are no idle cores left in the system; tracked through -* sd_llc->shared->has_idle_cores and enabled through update_idle_core() above. -*/ -static int select_idle_core (struct task_struct *p,struct sched_domain *sd,int target) +static int __select_idle_core (int core,struct cpumask *cpus,int *idle_cpu) { -struct cpumask *cpus =this_cpu_cpumask_var_ptr (select_idle_mask); -int core, cpu; - -if (!static_branch_likely (&sched_smt_present)) -return -1 ; - -if (!test_idle_cores (target, false)) -return -1 ; - -cpumask_and (cpus,sched_domain_span (sd), p->cpus_ptr); - -for_each_cpu_wrap (core, cpus, target) { -bool idle = true; +bool idle = true; +int cpu; -for_each_cpu (cpu,cpu_smt_mask (core)) { -if (!available_idle_cpu (cpu)) { - idle = false; -break ; - } +for_each_cpu (cpu,cpu_smt_mask (core)) { +if (!available_idle_cpu (cpu)) { + idle = false; +continue ; } - -if (idle) -return core; - -cpumask_andnot (cpus, cpus,cpu_smt_mask (core)); +if (idle_cpu) + *idle_cpu = cpu; } -/* -* Failed to find an idle core; stop looking for one. -*/ -set_idle_cores (target,0 ); +if (idle) +return core; +cpumask_andnot (cpus, cpus,cpu_smt_mask (core));return -1 ; } -/* -* Scan the local SMT mask for idle CPUs. -*/ -static int select_idle_smt (struct task_struct *p,struct sched_domain *sd,int target) -{ -int cpu; - -if (!static_branch_likely (&sched_smt_present)) -return -1 ; - -for_each_cpu (cpu,cpu_smt_mask (target)) { -if (!cpumask_test_cpu (cpu, p->cpus_ptr) || - !cpumask_test_cpu (cpu,sched_domain_span (sd))) -continue ; -if (available_idle_cpu (cpu) ||sched_idle_cpu (cpu)) -return cpu; - } +#else /* CONFIG_SCHED_SMT */ -return -1 ; +static inline void set_idle_cores (int cpu,int val) +{ } -#else /* CONFIG_SCHED_SMT */ - -static inline int select_idle_core (struct task_struct *p,struct sched_domain *sd,int target) +static inline bool test_idle_cores (int cpu,bool def) { -return -1 ; +return def; } -static inline int select_idle_smt (struct task_struct *p,struct sched_domain *sd,int target) +static inline int __select_idle_core (int core,struct cpumask *cpus,int *idle_cpu) {return -1 ; }
@@ -6144,10 +6108,11 @@ static inline int select_idle_smt(structstatic int select_idle_cpu (struct task_struct *p,struct sched_domain *sd,int target) {struct cpumask *cpus =this_cpu_cpumask_var_ptr (select_idle_mask); +int this =smp_processor_id (); +bool smt =test_idle_cores (this, false); +int i, cpu, idle_cpu =-1 , nr =INT_MAX ;struct sched_domain *this_sd;u64 time; -int this =smp_processor_id (); -int cpu, nr =INT_MAX ; this_sd =rcu_dereference (*this_cpu_ptr (&sd_llc));if (!this_sd)
@@ -6155,7 +6120,7 @@ static int select_idle_cpu(struct task_scpumask_and (cpus,sched_domain_span (sd), p->cpus_ptr); -if (sched_feat (SIS_PROP )) { +if (sched_feat (SIS_PROP ) && !smt) {u64 avg_cost, avg_idle, span_avg;/*
@@ -6175,18 +6140,31 @@ static int select_idle_cpu(struct task_s }for_each_cpu_wrap (cpu, cpus, target) { -if (!--nr) -return -1 ; -if (available_idle_cpu (cpu) ||sched_idle_cpu (cpu)) -break ; +if (smt) { + i =__select_idle_core (cpu, cpus, &idle_cpu); +if ((unsigned )i < nr_cpumask_bits) +return i; + + }else { +if (!--nr) +return -1 ; + +if (available_idle_cpu (cpu) ||sched_idle_cpu (cpu)) { + idle_cpu = cpu; +break ; + } + } } -if (sched_feat (SIS_PROP )) { +if (smt) +set_idle_cores (this, false); + +if (sched_feat (SIS_PROP ) && !smt) { time =cpu_clock (this) - time;update_avg (&this_sd->avg_scan_cost, time); } -return cpu; +return idle_cpu; }/*
@@ -6315,18 +6293,10 @@ static int select_idle_sibling(struct taif (!sd)return target; - i =select_idle_core (p, sd, target); -if ((unsigned )i < nr_cpumask_bits) -return i; - i =select_idle_cpu (p, sd, target);if ((unsigned )i < nr_cpumask_bits)return i; - i =select_idle_smt (p, sd, target); -if ((unsigned )i < nr_cpumask_bits) -return i; -return target; }
Quoted 11 lines · Peter Zijlstra
Quoted 3 lines · Mel Gorman
The prequisite patch to make that approach work was rejected though as on its own, it's not very helpful and Vincent didn't like that the
load_balance_maskwas abused to make it effective.So last time I poked at all this, I found that using more masks was a performance issue as well due to added cache misses.
Anyway, I finally found some time to look at all this, and while reading over the whole SiS crud to refresh the brain came up with the below...
Quoted 8 lines
It's still naf, but at least it gets rid of a bunch of duplicate scanning and LoC decreases, so it should be awesome. Ofcourse, as always, benchmarks will totally ruin everything, we'll see, I started some.
It goes on top of Mel's first two patches (which is about as far as I got)...
It's not free of bugs but it's interesting! The positive aspects are that it does a single scan, inits select_idle_mask once and caches an idle candidate when searching for an idle core but in a far cleaner fashion than what I did.
One bug is in __select_idle_core() though. It's scanning the SMT mask, not select_idle_mask so it can return an idle candidate that is not in p->cpus_ptr.
I queued tests anyway to see what it looks like.
There are some other potential caveats.
This is a single pass so when test_idle_cores() is true, __select_idle_core is used to to check all the siblings even if the core is not idle. That could have been cut short if __select_idle_core checked *idle_cpu == 1 and terminated the SMT scan if an idle candidate had already been found.
Second downside is related. If test_idle_cpus() was true but no idle CPU is found then __select_idle_core has been called enough to scan the entire domain. In this corner case, the new code does *more* work because the old code would have failed select_idle_core() quickly and then select_idle_cpu() would be throttled by SIS_PROP. I think this will only be noticable in the heavily overloaded case but if the corner case hits enough then the new code will be slower than the old code for the over-saturated case (i.e. hackbench with lots of groups).
The third potential downside is that the SMT sibling is not guaranteed to be checked due to SIS_PROP throttling but in the old code, that would have been checked by select_idle_smt(). That might result in premature stacking of runnable tasks on the same CPU. Similarly, as __select_idle_core may find multiple idle candidates, it will not pick the targets SMT sibling if it is idle like select_idle_smt would have.
That said, I am skeptical that select_idle_smt() matters all that often. If select_idle_cpu() has been throttled heavily then the machine is either over-saturated or was over-saturated in the very recent pass. In that situation, the chances of the SMT siblings being free is slim.
Each of the downsides could potentially addressed with this untested mess
kernel/sched/fair.c +7 -5
@@ -6061,7 +6061,7 @@ void __update_idle_core(struct rq *rq)rcu_read_unlock (); } -static int __select_idle_core (int core,struct cpumask *cpus,int *idle_cpu) +static int __select_idle_core (struct task_struct *p,int core,struct cpumask *cpus,int *idle_cpu) {bool idle = true;int cpu;
@@ -6070,9 +6070,11 @@ static int __select_idle_core(int core, struct cpumask *cpus, int *idle_cpu)schedstat_inc (this_rq ()->sis_scanned);if (!available_idle_cpu (cpu)) { idle = false; -continue ; +if (*idle_cpu ==-1 ) +continue ; +break ; } -if (idle_cpu) +if (*idle_cpu ==-1 &&cpumask_test_cpu (cpu, p->cpus_ptr)) *idle_cpu = cpu; }
@@ -6094,7 +6096,7 @@ static inline bool test_idle_cores(int cpu, bool def)return def; } -static inline int __select_idle_core (int core,struct cpumask *cpus,int *idle_cpu) +static inline int __select_idle_core (struct task_struct *p,int core,struct cpumask *cpus,int *idle_cpu) {return -1 ; }
@@ -6142,7 +6144,7 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, int tfor_each_cpu_wrap (cpu, cpus, target) {if (smt) { - i =__select_idle_core (cpu, cpus, &idle_cpu); + i =__select_idle_core (p, cpu, cpus, &idle_cpu);if ((unsigned )i < nr_cpumask_bits)return i;
Signature · 2 lines
Mel Gorman SUSE Labs
Peter Zijlstra
maintainerQuoted 3 lines · Mel Gorman
One bug is in
__select_idle_core()though. It's scanning the SMT mask, notselect_idle_maskso it can return an idle candidate that is not inp->cpus_ptr.
D'0h.. luckily the benchmarks don't hit that :-)
Quoted 6 lines
There are some other potential caveats.
This is a single pass so when
test_idle_cores()is true,__select_idle_coreis used to to check all the siblings even if the core is not idle. That could have been cut short if__select_idle_corechecked*idle_cpu== 1 and terminated the SMT scan if an idle candidate had already been found.
So I did that on purpose, so as to track the last/most-recent idle cpu, with the thinking that that cpu has the higher chance of still being idle vs one we checked earlier/longer-ago.
I suppose we benchmark both and see which is liked best.
Quoted 8 lines
Second downside is related. If
test_idle_cpus()was true but no idle CPU is found then__select_idle_corehas been called enough to scan the entire domain. In this corner case, the new code does *more* work because the old code would have failedselect_idle_core()quickly and thenselect_idle_cpu()would be throttled bySIS_PROP. I think this will only be noticable in the heavily overloaded case but if the corner case hits enough then the new code will be slower than the old code for the over-saturated case (i.e. hackbench with lots of groups).
Right, due to scanning siblings, even if the first inspected thread is not idle, we scan more.
Quoted 8 lines
The third potential downside is that the SMT sibling is not guaranteed to be checked due to
SIS_PROPthrottling but in the old code, that would have been checked byselect_idle_smt(). That might result in premature stacking of runnable tasks on the same CPU. Similarly, as__select_idle_coremay find multiple idle candidates, it will not pick the targets SMT sibling if it is idle likeselect_idle_smtwould have.That said, I am skeptical that
select_idle_smt()matters all that often.
This, I didn't really believe in it either.
The benchmarks I started are mostly noise, with a few wins for TCP_STREAM and UDP_RR around the 50% mark. Although I should run longer variants to make sure.
Quoted 7 lines · Peter Zijlstra
Quoted 3 lines · Mel Gorman
One bug is in
__select_idle_core()though. It's scanning the SMT mask, notselect_idle_maskso it can return an idle candidate that is not inp->cpus_ptr.D'0h.. luckily the benchmarks don't hit that :-)
Yep, neither do mine for the most part which is why I ran it as-is but eventually someone would complain that sched_setscheduler was being ignored.
Trick is whether a failed check should continue searching for an idle core or terminate early and just pick an allowed idle CPU. I tend to favour the latter but it's hard to predict what sort of reasonable workloads would be affected.
Quoted 7 lines
Quoted 6 lines
There are some other potential caveats.
This is a single pass so when
test_idle_cores()is true,__select_idle_coreis used to to check all the siblings even if the core is not idle. That could have been cut short if__select_idle_corechecked*idle_cpu== 1 and terminated the SMT scan if an idle candidate had already been found.
Quoted 6 lines
So I did that on purpose, so as to track the last/most-recent idle cpu, with the thinking that that cpu has the higher chance of still being idle vs one we checked earlier/longer-ago.
I suppose we benchmark both and see which is liked best.
I originally did something like that on purpose too but Vincent called it out so it is worth mentioning now to avoid surprises. That said, I'm at the point where anything SIS-related simply needs excessive exposure because no matter what it does, someone is unhappy with it.
Quoted 9 lines
Quoted 8 lines
Second downside is related. If
test_idle_cpus()was true but no idle CPU is found then__select_idle_corehas been called enough to scan the entire domain. In this corner case, the new code does *more* work because the old code would have failedselect_idle_core()quickly and thenselect_idle_cpu()would be throttled bySIS_PROP. I think this will only be noticable in the heavily overloaded case but if the corner case hits enough then the new code will be slower than the old code for the over-saturated case (i.e. hackbench with lots of groups).
Quoted 3 lines
Right, due to scanning siblings, even if the first inspected thread is not idle, we scan more.
Yep.
Quoted 11 lines
Quoted 8 lines
The third potential downside is that the SMT sibling is not guaranteed to be checked due to
SIS_PROPthrottling but in the old code, that would have been checked byselect_idle_smt(). That might result in premature stacking of runnable tasks on the same CPU. Similarly, as__select_idle_coremay find multiple idle candidates, it will not pick the targets SMT sibling if it is idle likeselect_idle_smtwould have.That said, I am skeptical that
select_idle_smt()matters all that often.This, I didn't really believe in it either.
Good because I think any benefit from select_idle_smt is so marginal that it should be ignored if the full scan is simpler overall.
Quoted 3 lines
The benchmarks I started are mostly noise, with a few wins for
TCP_STREAMandUDP_RRaround the 50% mark. Although I should run longer variants to make sure.
So far I have one benchmark from one machine. It's tbench again because it's a reasonable communicating workload that is trivial to vary the level of utilisation.
80-cpu CascadeLake, 2 sockets, HT enabled
tbench4
5.10.0-rc6 5.10.0-rc6 5.10.0-rc6
baseline-v1r1 singlescan-v1r1 singlescan-v1r3
Hmean 1 503.90 ( 0.00%) 505.19 * 0.26%* 499.20 * -0.93%* Hmean 2 980.80 ( 0.00%) 975.15 * -0.58%* 983.79 * 0.31%* Hmean 4 1912.37 ( 0.00%) 1883.25 * -1.52%* 1923.76 * 0.60%* Hmean 8 3741.47 ( 0.00%) 3568.66 * -4.62%* 3690.60 * -1.36%* Hmean 16 6552.90 ( 0.00%) 6549.97 * -0.04%* 6478.37 * -1.14%* Hmean 32 10217.34 ( 0.00%) 10266.66 * 0.48%* 10291.60 * 0.73%* Hmean 64 13604.93 ( 0.00%) 11240.88 * -17.38%* 12045.87 * -11.46%* Hmean 128 21194.11 ( 0.00%) 21316.08 * 0.58%* 21868.39 * 3.18%* Hmean 256 21163.19 ( 0.00%) 20989.14 * -0.82%* 20831.20 * -1.57%* Hmean 320 20906.29 ( 0.00%) 21024.11 * 0.56%* 20756.88 * -0.71%* Stddev 1 3.14 ( 0.00%) 1.17 ( 62.93%) 1.05 ( 66.61%) Stddev 2 4.44 ( 0.00%) 3.72 ( 16.35%) 2.20 ( 50.56%) Stddev 4 9.09 ( 0.00%) 18.67 (-105.32%) 3.66 ( 59.71%) Stddev 8 12.87 ( 0.00%) 18.96 ( -47.31%) 11.90 ( 7.58%) Stddev 16 8.34 ( 0.00%) 8.77 ( -5.22%) 36.25 (-334.84%) Stddev 32 27.05 ( 0.00%) 20.90 ( 22.74%) 28.57 ( -5.61%) Stddev 64 720.66 ( 0.00%) 20.12 ( 97.21%) 32.10 ( 95.55%) Stddev 128 17.49 ( 0.00%) 52.33 (-199.22%) 137.68 (-687.25%) Stddev 256 57.17 ( 0.00%) 18.87 ( 67.00%) 38.98 ( 31.81%) Stddev 320 29.87 ( 0.00%) 46.49 ( -55.64%) 31.48 ( -5.39%)
5.10.0-rc6 5.10.0-rc6 5.10.0-rc6
baseline-v1r1singlescan-v1r1singlescan-v1r3Duration User 9771.18 9435.64 9353.29
Duration System 34224.28 33829.01 33802.34
Duration Elapsed 2218.87 2218.87 2218.69
baseline is roughly what's in tip for 5.11-rc1 with patches 1-2 from my series like you had.
singlescan-v1r1 is your patch
singlescan-v1r3 is your patch with my "untested" patch on top that enforces p->cpus_ptr and short-cuts corner cases.
Few points of interest
1. 64 clients regresses. With 64 clients, this is roughly the point where test_idle_cores() returns false positives and we hit the worst corner cases. Your patch regresses 17%, mine is only a marginal improvement and still a regression slower.
2. Variations are all over the place. Your patch is great at low utilisation and stabilises overall. After that, your milage varies a lot
3. The system CPu usage summarised over the entire workload drops quite a bit. Whether it's your patch or minor changes on top, there is less work being done within the kernel overall
A wider battery of tests is still running and a second set is queued that adds the debugging schedstats but they take ages to run.
I'm currently on "holidays" so response time will be variable :P
Signature · 2 lines
Mel Gorman SUSE Labs
Vincent Guittot
maintainerQuoted 30 lines · Mel Gorman
Quoted 7 lines · Peter Zijlstra
Quoted 3 lines · Mel Gorman
One bug is in
__select_idle_core()though. It's scanning the SMT mask, notselect_idle_maskso it can return an idle candidate that is not inp->cpus_ptr.D'0h.. luckily the benchmarks don't hit that :-)
Yep, neither do mine for the most part which is why I ran it as-is but eventually someone would complain that
sched_setschedulerwas being ignored.Trick is whether a failed check should continue searching for an idle core or terminate early and just pick an allowed idle CPU. I tend to favour the latter but it's hard to predict what sort of reasonable workloads would be affected.
Quoted 11 lines
Quoted 6 lines
There are some other potential caveats.
This is a single pass so when
test_idle_cores()is true,__select_idle_coreis used to to check all the siblings even if the core is not idle. That could have been cut short if__select_idle_corechecked*idle_cpu== 1 and terminated the SMT scan if an idle candidate had already been found.So I did that on purpose, so as to track the last/most-recent idle cpu, with the thinking that that cpu has the higher chance of still being idle vs one we checked earlier/longer-ago.
Quoted 7 lines
Quoted 2 lines
I suppose we benchmark both and see which is liked best.
I originally did something like that on purpose too but Vincent called it out so it is worth mentioning now to avoid surprises. That said, I'm at the point where anything SIS-related simply needs excessive exposure because no matter what it does, someone is unhappy with it.
Yeah, I don't like extending the idle core search loop for something that is not related to the idle core search. This adds more work out of control of the sis_prop. So I'm still against hiding some idle cpu search in idle core search.
Quoted 100 lines
Quoted 10 lines
Quoted 9 lines
Second downside is related. If
test_idle_cpus()was true but no idle CPU is found then__select_idle_corehas been called enough to scan the entire domain. In this corner case, the new code does *more* work because the old code would have failedselect_idle_core()quickly and thenselect_idle_cpu()would be throttled bySIS_PROP. I think this will only be noticable in the heavily overloaded case but if the corner case hits enough then the new code will be slower than the old code for the over-saturated case (i.e. hackbench with lots of groups).Quoted 3 lines
Right, due to scanning siblings, even if the first inspected thread is not idle, we scan more.
Yep.
Quoted 11 lines
Quoted 8 lines
The third potential downside is that the SMT sibling is not guaranteed to be checked due to
SIS_PROPthrottling but in the old code, that would have been checked byselect_idle_smt(). That might result in premature stacking of runnable tasks on the same CPU. Similarly, as__select_idle_coremay find multiple idle candidates, it will not pick the targets SMT sibling if it is idle likeselect_idle_smtwould have.That said, I am skeptical that
select_idle_smt()matters all that often.This, I didn't really believe in it either.
Good because I think any benefit from
select_idle_smtis so marginal that it should be ignored if the full scan is simpler overall.Quoted 3 lines
The benchmarks I started are mostly noise, with a few wins for
TCP_STREAMandUDP_RRaround the 50% mark. Although I should run longer variants to make sure.So far I have one benchmark from one machine. It's tbench again because it's a reasonable communicating workload that is trivial to vary the level of utilisation.
80-cpu CascadeLake, 2 sockets, HT enabled
tbench4
5.10.0-rc6 5.10.0-rc6 5.10.0-rc6
baseline-v1r1 singlescan-v1r1 singlescan-v1r3Hmean 1 503.90 ( 0.00%) 505.19 * 0.26%* 499.20 * -0.93%* Hmean 2 980.80 ( 0.00%) 975.15 * -0.58%* 983.79 * 0.31%* Hmean 4 1912.37 ( 0.00%) 1883.25 * -1.52%* 1923.76 * 0.60%* Hmean 8 3741.47 ( 0.00%) 3568.66 * -4.62%* 3690.60 * -1.36%* Hmean 16 6552.90 ( 0.00%) 6549.97 * -0.04%* 6478.37 * -1.14%* Hmean 32 10217.34 ( 0.00%) 10266.66 * 0.48%* 10291.60 * 0.73%* Hmean 64 13604.93 ( 0.00%) 11240.88 * -17.38%* 12045.87 * -11.46%* Hmean 128 21194.11 ( 0.00%) 21316.08 * 0.58%* 21868.39 * 3.18%* Hmean 256 21163.19 ( 0.00%) 20989.14 * -0.82%* 20831.20 * -1.57%* Hmean 320 20906.29 ( 0.00%) 21024.11 * 0.56%* 20756.88 * -0.71%* Stddev 1 3.14 ( 0.00%) 1.17 ( 62.93%) 1.05 ( 66.61%) Stddev 2 4.44 ( 0.00%) 3.72 ( 16.35%) 2.20 ( 50.56%) Stddev 4 9.09 ( 0.00%) 18.67 (-105.32%) 3.66 ( 59.71%) Stddev 8 12.87 ( 0.00%) 18.96 ( -47.31%) 11.90 ( 7.58%) Stddev 16 8.34 ( 0.00%) 8.77 ( -5.22%) 36.25 (-334.84%) Stddev 32 27.05 ( 0.00%) 20.90 ( 22.74%) 28.57 ( -5.61%) Stddev 64 720.66 ( 0.00%) 20.12 ( 97.21%) 32.10 ( 95.55%) Stddev 128 17.49 ( 0.00%) 52.33 (-199.22%) 137.68 (-687.25%) Stddev 256 57.17 ( 0.00%) 18.87 ( 67.00%) 38.98 ( 31.81%) Stddev 320 29.87 ( 0.00%) 46.49 ( -55.64%) 31.48 ( -5.39%)5.10.0-rc6 5.10.0-rc6 5.10.0-rc6 baseline-v1r1singlescan-v1r1singlescan-v1r3Duration User 9771.18 9435.64 9353.29
Duration System 34224.28 33829.01 33802.34
Duration Elapsed 2218.87 2218.87 2218.69baseline is roughly what's in tip for 5.11-rc1 with patches 1-2 from my series like you had.
singlescan-v1r1 is your patch
singlescan-v1r3 is your patch with my "untested" patch on top that enforces
p->cpus_ptrand short-cuts corner cases.Few points of interest
1. 64 clients regresses. With 64 clients, this is roughly the point where
test_idle_cores()returns false positives and we hit the worst corner cases. Your patch regresses 17%, mine is only a marginal improvement and still a regression slower.2. Variations are all over the place. Your patch is great at low utilisation and stabilises overall. After that, your milage varies a lot
3. The system CPu usage summarised over the entire workload drops quite a bit. Whether it's your patch or minor changes on top, there is less work being done within the kernel overall
A wider battery of tests is still running and a second set is queued that adds the debugging schedstats but they take ages to run.
I'm currently on "holidays" so response time will be variable :P
--
Mel Gorman
SUSE Labs
Peter Zijlstra
maintainerQuoted 11 lines · Vincent Guittot
Quoted 4 lines · Mel Gorman
I originally did something like that on purpose too but Vincent called it out so it is worth mentioning now to avoid surprises. That said, I'm at the point where anything SIS-related simply needs excessive exposure because no matter what it does, someone is unhappy with it.
Yeah, I don't like extending the idle core search loop for something that is not related to the idle core search. This adds more work out of control of the
sis_prop. So I'm still against hiding some idle cpu search in idle core search.
The idea, of course, is to do less. The current code is pretty crap in that it will do a whole bunch of things multiple times.
Also, a possible follow up, would be something like the below (and remove all the sds->has_idle_cores crud), which brings core scanning under SIS_PROP.
But it all needs lots of benchmarking :/
kernel/sched/fair.c +12 -19
@@ -6095,6 +6095,9 @@ static inline bool test_idle_cores(int cstatic inline int __select_idle_core (int core,struct cpumask *cpus,int *idle_cpu) { +if (idle_cpu && (available_idle_cpu (core) ||sched_idle_cpu (cpu)) + *idle_cpu = core; +return -1 ; }
@@ -6109,7 +6112,6 @@ static int select_idle_cpu(struct task_s {struct cpumask *cpus =this_cpu_cpumask_var_ptr (select_idle_mask);int this =smp_processor_id (); -bool smt =test_idle_cores (this, false);int i, cpu, idle_cpu =-1 , nr =INT_MAX ;struct sched_domain *this_sd;u64 time;
@@ -6120,7 +6122,7 @@ static int select_idle_cpu(struct task_scpumask_and (cpus,sched_domain_span (sd), p->cpus_ptr); -if (sched_feat (SIS_PROP ) && !smt) { +if (sched_feat (SIS_PROP )) {u64 avg_cost, avg_idle, span_avg;/*
@@ -6140,26 +6142,17 @@ static int select_idle_cpu(struct task_s }for_each_cpu_wrap (cpu, cpus, target) { -if (smt) { - i =__select_idle_core (cpu, cpus, &idle_cpu); -if ((unsigned )i < nr_cpumask_bits) -return i; - - }else { -if (!--nr) -return -1 ; - -if (available_idle_cpu (cpu) ||sched_idle_cpu (cpu)) { - idle_cpu = cpu; -break ; - } +if (!--nr) +break ; + + i =__select_idle_core (cpu, cpus, &idle_cpu); +if ((unsigned )i < nr_cpumask_bits) { + idle_cpu = i; +break ; } } -if (smt) -set_idle_cores (this, false); - -if (sched_feat (SIS_PROP ) && !smt) { +if (sched_feat (SIS_PROP )) { time =cpu_clock (this) - time;update_avg (&this_sd->avg_scan_cost, time); }
Quoted 8 lines · Peter Zijlstra
Quoted 7 lines · Vincent Guittot
Quoted 4 lines · Mel Gorman
I originally did something like that on purpose too but Vincent called it out so it is worth mentioning now to avoid surprises. That said, I'm at the point where anything SIS-related simply needs excessive exposure because no matter what it does, someone is unhappy with it.
Quoted 8 lines
Quoted 4 lines
Yeah, I don't like extending the idle core search loop for something that is not related to the idle core search. This adds more work out of control of the
sis_prop. So I'm still against hiding some idle cpu search in idle core search.The idea, of course, is to do less. The current code is pretty crap in that it will do a whole bunch of things multiple times.
^^^ this
While there is some overhead when searching for an idle core to track an idle sibling, it's better than double scanning when test_idle_cores() returns a false positive (or it races with a parallel search that takes the last idle core).
Quoted 4 lines
Also, a possible follow up, would be something like the below (and remove all the
sds->has_idle_corescrud), which brings core scanning underSIS_PROP.
I'm less confident about this this but admit I have no data. test_idle_core becomes critical for hackbench once it saturates the machine as it'll generally return a true positive.
Where test_idle_cores causes problems is when domains are over 50% busy and returns false positives due to races and the work to find an idle core is wasted. The flip side is that updating the has_idle_core information is also expensive in this case as it causes lots of dirty cache line bouncing so maybe in practice it might be ok. It definitely should be a separate patch that is tested on top of your first prototype with the p->cpus_ptr check when picking an idle candidate.
The other side-effect is that with this patch that the scan cost is *always* accounted for. While this makes intuitive sense as it was never clear to me why it was only accounted with scan failures. When I had tested something like this, it was a mix of wins and losses. At minimum, a patch that always accounts for scan cost and one the removes the test_idle_core should be separate patches for bisection purposes at the very least.
This is the current set of results I have for your prototype plus the fixes I suggested on top
http://www.skynet.ie/~mel/postings/peterz-20201214/dashboard.html
It's not a universal win but appears to win more than it loses
The biggest loss is dbench on EPYC 2
http://www.skynet.ie/~mel/postings/peterz-20201214/io-dbench4-async-xfs/romulus/index.html#dbench4
It's not at clear why it was so badly affected but in general, EPYC can be problematic as it has multiple small LLCs. The same machine for specjvm showed large gains.
http://www.skynet.ie/~mel/postings/peterz-20201214/jvm-specjbb2005-multi/romulus/index.html#specjbb
There are a lot of results to trawl through but mostly it shows that it's a mix of wins and losses and it's both workload and machine dependant which is generally true for anything select_idle_sibling related.
As the merge window is open, it's inevitable that this will need to be evaluated against 5.11-rc1 when all the current batch of scheduler code has been merged. Do you mind splitting your prototype into three patches and slap some sort of changlog on them? I'll run them through the grid with p->recent_used_cpu changes on top to use recent_use_cpu as a search hint instead of an idle candidate so that it scans for a core. They'll take a while to run but it's automated and some people are going to be dropping off for holidays relatively soon anyway. I can test on arm too but as it does not have SMT enabled, it'll be less useful.
Signature · 2 lines
Mel Gorman SUSE Labs
Peter Zijlstra
maintainerQuoted 4 lines · Mel Gorman
As the merge window is open, it's inevitable that this will need to be evaluated against 5.11-rc1 when all the current batch of scheduler code has been merged. Do you mind splitting your prototype into three patches and slap some sort of changlog on them?
Sure, I'm afraid it's a little more than 3, but I'll get on it.
Peter Zijlstra
maintainerQuoted 7 lines · Mel Gorman
Quoted 7 lines
Quoted 7 lines
The third potential downside is that the SMT sibling is not guaranteed to be checked due to
SIS_PROPthrottling but in the old code, that would have been checked byselect_idle_smt(). That might result in premature stacking of runnable tasks on the same CPU. Similarly, as__select_idle_coremay find multiple idle candidates, it will not pick the targets SMT sibling if it is idle likeselect_idle_smtwould have.
Quoted 7 lines
Quoted 4 lines
Quoted 1 line
That said, I am skeptical that
select_idle_smt()matters all that often.This, I didn't really believe in it either.
Good because I think any benefit from
select_idle_smtis so marginal that it should be ignored if the full scan is simpler overall.
Perhaps we should start out with a simple patch removing that pass.. That should show, what, if anything, the effect of it is.
Vincent Guittot
maintainerQuoted 12 lines · Peter Zijlstra
Quoted 3 lines · Mel Gorman
The prequisite patch to make that approach work was rejected though as on its own, it's not very helpful and Vincent didn't like that the
load_balance_maskwas abused to make it effective.So last time I poked at all this, I found that using more masks was a performance issue as well due to added cache misses.
Anyway, I finally found some time to look at all this, and while reading over the whole SiS crud to refresh the brain came up with the below...
Quoted 7 lines
It's still naf, but at least it gets rid of a bunch of duplicate scanning and LoC decreases, so it should be awesome. Ofcourse, as always, benchmarks will totally ruin everything, we'll see, I started some.
It goes on top of Mel's first two patches (which is about as far as I got)...
We have several different things that Aubrey and Mel patches are trying to achieve:
Aubrey wants to avoid scanning busy cpus
- patch works well on busy system: I see a significant benefit with hackbench on a lot of group on my 2 nodes * 28 cores * 4 smt
hackbench -l 2000 -g 128
tip 3.334
w/ patch 2.978 (+12%)
- Aubey also tried to not scan the cpus which are idle for a short duration (when a tick not stopped) but there are problems because not stopping a tick doesn't mean a short idle. In fact , something similar to find_idlest_group_cpu() should be done in this case but then it's no more a fast path search
Mel wants to minimize looping over the cpus
-patch 4 is an obvious win on light loaded system because it avoids looping twice the cpus mask when some cpus are idle but no core -But patch 3 generates perf régression
hackbench -l 2000 -g 1
tip 12.293
/w all Mel's patches 15.163 -14%
/w Aubrey + Mel patches minus patch 3 : 12.788 +3.8% But I think that Aubreay's patch doesn't help here. Test without aubrey's patch are running
-he also tried to used load_balance_mask to do something similar to the below
Quoted 52 lines
--- fair.c | 124 ++++++++++++++++++++++++----------------------------------------- 1 file changed, 47 insertions(+), 77 deletions(-)kernel/sched/fair.c +9
-23@@ -6021,11 +6021,13 @@ static inline void set_idle_cores(int cpstatic inline bool test_idle_cores (int cpu,bool def) { -struct sched_domain_shared *sds; +if (static_branch_likely (&sched_smt_present)) { +struct sched_domain_shared *sds; - sds =rcu_dereference (per_cpu (sd_llc_shared, cpu)); -if (sds) -return READ_ONCE (sds->has_idle_cores); + sds =rcu_dereference (per_cpu (sd_llc_shared, cpu)); +if (sds) +return READ_ONCE (sds->has_idle_cores); + }return def; }@@ -6059,77 +6061,39 @@ void __update_idle_core(struct rq *rq)rcu_read_unlock (); } -/* -* Scan the entire LLC domain for idle cores; this dynamically switches off if -* there are no idle cores left in the system; tracked through -* sd_llc->shared->has_idle_cores and enabled through update_idle_core() above. -*/ -static int select_idle_core (struct task_struct *p,struct sched_domain *sd,int target) +static int __select_idle_core (int core,struct cpumask *cpus,int *idle_cpu) { -struct cpumask *cpus =this_cpu_cpumask_var_ptr (select_idle_mask); -int core, cpu; - -if (!static_branch_likely (&sched_smt_present)) -return -1 ; - -if (!test_idle_cores (target, false)) -return -1 ; - -cpumask_and (cpus,sched_domain_span (sd), p->cpus_ptr); - -for_each_cpu_wrap (core, cpus, target) { -bool idle = true; +bool idle = true; +int cpu;
kernel/sched/fair.c void __update_idle_core(struct rq *rq) · line 6072
Quoted 10 lines
kernel/sched/fair.c +4
-5-for_each_cpu (cpu,cpu_smt_mask (core)) { -if (!available_idle_cpu (cpu)) { - idle = false; -break ; - } +for_each_cpu (cpu,cpu_smt_mask (core)) { +if (!available_idle_cpu (cpu)) { + idle = false; +continue ;
By not breaking on the first not idle cpu of the core, you will largely increase the number of loops. On my system, it increases 4 times from 28 up tu 112
Quoted 83 lines
kernel/sched/fair.c +15
-35} - -if (idle) -return core; - -cpumask_andnot (cpus, cpus,cpu_smt_mask (core)); +if (idle_cpu) + *idle_cpu = cpu; } -/* -* Failed to find an idle core; stop looking for one. -*/ -set_idle_cores (target,0 ); +if (idle) +return core; +cpumask_andnot (cpus, cpus,cpu_smt_mask (core));return -1 ; } -/* -* Scan the local SMT mask for idle CPUs. -*/ -static int select_idle_smt (struct task_struct *p,struct sched_domain *sd,int target) -{ -int cpu; - -if (!static_branch_likely (&sched_smt_present)) -return -1 ; - -for_each_cpu (cpu,cpu_smt_mask (target)) { -if (!cpumask_test_cpu (cpu, p->cpus_ptr) || - !cpumask_test_cpu (cpu,sched_domain_span (sd))) -continue ; -if (available_idle_cpu (cpu) ||sched_idle_cpu (cpu)) -return cpu; - } +#else /* CONFIG_SCHED_SMT */ -return -1 ; +static inline void set_idle_cores (int cpu,int val) +{ } -#else /* CONFIG_SCHED_SMT */ - -static inline int select_idle_core (struct task_struct *p,struct sched_domain *sd,int target) +static inline bool test_idle_cores (int cpu,bool def) { -return -1 ; +return def; } -static inline int select_idle_smt (struct task_struct *p,struct sched_domain *sd,int target) +static inline int __select_idle_core (int core,struct cpumask *cpus,int *idle_cpu) {return -1 ; }@@ -6144,10 +6108,11 @@ static inline int select_idle_smt(structstatic int select_idle_cpu (struct task_struct *p,struct sched_domain *sd,int target) {struct cpumask *cpus =this_cpu_cpumask_var_ptr (select_idle_mask); +int this =smp_processor_id (); +bool smt =test_idle_cores (this, false); +int i, cpu, idle_cpu =-1 , nr =INT_MAX ;struct sched_domain *this_sd;u64 time; -int this =smp_processor_id (); -int cpu, nr =INT_MAX ; this_sd =rcu_dereference (*this_cpu_ptr (&sd_llc));if (!this_sd)@@ -6155,7 +6120,7 @@ static int select_idle_cpu(struct task_scpumask_and (cpus,sched_domain_span (sd), p->cpus_ptr); -if (sched_feat (SIS_PROP )) { +if (sched_feat (SIS_PROP ) && !smt) {u64 avg_cost, avg_idle, span_avg;/*
kernel/sched/fair.c static int select_idle_cpu(struct task_s · line 6143
Quoted 8 lines
kernel/sched/fair.c +1
-4@@ -6175,18 +6140,31 @@ static int select_idle_cpu(struct task_s }for_each_cpu_wrap (cpu, cpus, target) { -if (!--nr) -return -1 ; -if (available_idle_cpu (cpu) ||sched_idle_cpu (cpu)) -break ; +if (smt) {
sds->has_idle_core being set doesn't means that there is one idle core which means for the same real HW state (i.e. no idle cores) if sds->has_idle_core is set, we will loop all cpus here and never get a chance to return a sched_idle_cpu()
but if sds->has_idle_core is clear, we will loop on a limited number of cpus and test sched_idle_cpu()
Quoted 48 lines
kernel/sched/fair.c +18
-10+ i =__select_idle_core (cpu, cpus, &idle_cpu); +if ((unsigned )i < nr_cpumask_bits) +return i; + + }else { +if (!--nr) +return -1 ; + +if (available_idle_cpu (cpu) ||sched_idle_cpu (cpu)) { + idle_cpu = cpu; +break ; + } + } } -if (sched_feat (SIS_PROP )) { +if (smt) +set_idle_cores (this, false); + +if (sched_feat (SIS_PROP ) && !smt) { time =cpu_clock (this) - time;update_avg (&this_sd->avg_scan_cost, time); } -return cpu; +return idle_cpu; }/* @@ -6315,18 +6293,10 @@ static int select_idle_sibling(struct taif (!sd)return target; - i =select_idle_core (p, sd, target); -if ((unsigned )i < nr_cpumask_bits) -return i; - i =select_idle_cpu (p, sd, target);if ((unsigned )i < nr_cpumask_bits)return i; - i =select_idle_smt (p, sd, target); -if ((unsigned )i < nr_cpumask_bits) -return i; -return target; }
Quoted 24 lines · Vincent Guittot
Quoted 12 lines · Peter Zijlstra
Quoted 3 lines · Mel Gorman
The prequisite patch to make that approach work was rejected though as on its own, it's not very helpful and Vincent didn't like that the
load_balance_maskwas abused to make it effective.So last time I poked at all this, I found that using more masks was a performance issue as well due to added cache misses.
Anyway, I finally found some time to look at all this, and while reading over the whole SiS crud to refresh the brain came up with the below...
Quoted 7 lines
It's still naf, but at least it gets rid of a bunch of duplicate scanning and LoC decreases, so it should be awesome. Ofcourse, as always, benchmarks will totally ruin everything, we'll see, I started some.
It goes on top of Mel's first two patches (which is about as far as I got)...
We have several different things that Aubrey and Mel patches are trying to achieve:
Quoted 7 lines
Aubrey wants to avoid scanning busy cpus
- patch works well on busy system: I see a significant benefit with hackbench on a lot of group on my 2 nodes * 28 cores * 4 smthackbench -l 2000 -g 128tip 3.334
w/ patch 2.978 (+12%)
It's still the case that Aubrey's work does not conflict with what Peter is doing. All that changes is what mask is applied.
Similarly, the p->recent_used_cpu changes I made initially (but got rejected) reduces scanning. I intend to revisit that to use recent_used_cpu as a search target because one side-effect of the patch was the siblings can be used prematurely.
Quoted 6 lines
- Aubey also tried to not scan the cpus which are idle for a short duration (when a tick not stopped) but there are problems because not stopping a tick doesn't mean a short idle. In fact , something similar to
find_idlest_group_cpu()should be done in this case but then it's no more a fast path search
The crowd most likely to complain about this is Facebook as they have workloads that prefer deep searches to find idle CPUs.
Quoted 3 lines
Mel wants to minimize looping over the cpus
-patch 4 is an obvious win on light loaded system because it avoids looping twice the cpus mask when some cpus are idle but no core
Peter's patch replaces that entirely which I'm fine with.
Quoted 10 lines
-But patch 3 generates perf régression
hackbench -l 2000 -g 1tip 12.293
/w all Mel's patches 15.163 -14%
/w Aubrey + Mel patches minus patch 3 : 12.788 +3.8% But I think that Aubreay's patch doesn't help here. Test without aubrey's patch are running-he also tried to used
load_balance_maskto do something similar to the below
Peter's approach removes load_balance_mask abuse so I think it's a better approach overall to scanning LLC domains in a single pass. It needs refinement and a lot of testing but I think it's promising.
Quoted 19 lines
Quoted 19 lines
kernel/sched/fair.c +3
-14-static int select_idle_core (struct task_struct *p,struct sched_domain *sd,int target) +static int __select_idle_core (int core,struct cpumask *cpus,int *idle_cpu) { -struct cpumask *cpus =this_cpu_cpumask_var_ptr (select_idle_mask); -int core, cpu; - -if (!static_branch_likely (&sched_smt_present)) -return -1 ; - -if (!test_idle_cores (target, false)) -return -1 ; - -cpumask_and (cpus,sched_domain_span (sd), p->cpus_ptr); - -for_each_cpu_wrap (core, cpus, target) { -bool idle = true; +bool idle = true; +int cpu;
Quoted 14 lines
kernel/sched/fair.c void __update_idle_core(struct rq *rq) · line 6072
Quoted 9 lines
kernel/sched/fair.c +4
-5-for_each_cpu (cpu,cpu_smt_mask (core)) { -if (!available_idle_cpu (cpu)) { - idle = false; -break ; - } +for_each_cpu (cpu,cpu_smt_mask (core)) { +if (!available_idle_cpu (cpu)) { + idle = false; +continue ;By not breaking on the first not idle cpu of the core, you will largely increase the number of loops. On my system, it increases 4 times from 28 up tu 112
But breaking early will mean that SMT siblings are used prematurely. However, if SIS_PROP was partially enforced for the idle core scan, it could limit the search for an idle core once an idle candidate was discovered.
Signature · 2 lines
Mel Gorman SUSE Labs
Quoted 6 lines · Mel Gorman
Quoted 5 lines · Aubrey
Quoted 4 lines
I ran this patch with tbench on top of of the schedstat patches that track SIS efficiency. The tracking adds overhead so it's not a perfect performance comparison but the expectation would be that the patch reduces the number of runqueues that are scanned
Quoted 20 lines
Quoted 3 lines
Thanks for the measurement! I don't play with tbench so may need a while to digest the data.
They key point is that it appears the idle mask was mostly equivalent to the full domain mask, at least for this test.
Quoted 13 lines
Quoted 13 lines
tbench4
5.10.0-rc6 5.10.0-rc6 schedstat-v1r1 idlemask-v7r1 Hmean 1 504.76 ( 0.00%) 500.14 * -0.91%* Hmean 2 1001.22 ( 0.00%) 970.37 * -3.08%* Hmean 4 1930.56 ( 0.00%) 1880.96 * -2.57%* Hmean 8 3688.05 ( 0.00%) 3537.72 * -4.08%* Hmean 16 6352.71 ( 0.00%) 6439.53 * 1.37%* Hmean 32 10066.37 ( 0.00%) 10124.65 * 0.58%*Hmean 64 12846.32 ( 0.00%) 11627.27 * -9.49%*
I focused on this case and run it 5 times, and here is the data on my side. 5 times x 600s tbench, thread number is 153(80% x 192(h/w thread num)).
Hmean 153 v5.9.12 v5.9.12
schedstat-v1 idlemask-v8(with schedstat)
Round 1 15717.3 15608.1
Round 2 14856.9 15642.5
Round 3 14856.7 15782.1
Round 4 15408.9 15912.9
Round 5 15436.6 15927.7
From tbench throughput data, bigger is better, it looks like idlemask wins
And here is SIS_scanned data:
Hmean 153 v5.9.12 v5.9.12
schedstat-v1 idlemask-v8(with schedstat)
Round 1 22562490432 21894932302
Round 2 21288529957 21693722629
Round 3 20657521771 21268308377
Round 4 21868486414 22289128955
Round 5 21859614988 22214740417
From SIS_scanned data, less is better, it looks like the default one is better.
But combined with throughput data, this can be explained as bigger throughput performs more SIS_scanned.
So at least, there is no regression of this case.
Thanks,
-Aubrey