Skip to contentSkip to conversation

sched/fair: select idle cpu from idle cpumask for task wakeup

RFC PATCH Superseded Aubrey Li 4 participants 22 messages Dec 9, 2020 – Dec 14, 2020 Scheduler

v7 of 8 Superseded Latest is v8 →

lore
Share & tools
lore

Aubrey Li

author
#0 lore raw

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.

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]>
---
 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
index 820511289857..b47b85163607 100644
@@ -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
index c4da7e17b906..c4c51ff3402a 100644
@@ -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
index f324dc36fc43..2c517d6a061a 100644
@@ -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
index 8d1ca65db3b0..2167ca48f3aa 100644
@@ -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
index 1bd7e3af904f..541bd3a7de4d 100644
@@ -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
maintainer
#1 lore raw
Quoted 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 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.

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]>
---
 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
index 820511289857..b47b85163607 100644
@@ -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
index c4da7e17b906..c4c51ff3402a 100644

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 -0
 	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
index c0c4d9ad7da8..7306f8886120 100644
@@ -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
index f324dc36fc43..2c517d6a061a 100644
@@ -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
index 8d1ca65db3b0..2167ca48f3aa 100644
@@ -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
index 1bd7e3af904f..541bd3a7de4d 100644
@@ -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
author
#2 lore raw
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 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.

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]>
---
 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
index 820511289857..b47b85163607 100644
@@ -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
index c4da7e17b906..c4c51ff3402a 100644
@@ -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_balance here instead of adding the test in update_idle_cpumask which 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

maintainer
#3 lore raw
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 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.

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]>
---
 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
index 820511289857..b47b85163607 100644
@@ -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
index c4da7e17b906..c4c51ff3402a 100644
@@ -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_balance here instead of adding the test in update_idle_cpumask which is only relevant for this situation.

Quoted 6 lines

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?

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

author
#4 lore raw
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 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.

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]>
---
 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
index 820511289857..b47b85163607 100644
@@ -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
index c4da7e17b906..c4c51ff3402a 100644
@@ -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_balance here instead of adding the test in update_idle_cpumask which is only relevant for this situation.

Quoted 6 lines

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?

I don't like having a tick specific condition in a generic function. rq->idle_balance is only relevant in this case

Quoted 7 lines

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

I see, will come up with a v8 soon.

Thanks,
-Aubrey

#5 lore raw
In reply to Aubrey Li
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.57

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.

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
author
#6 lore raw

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.57
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?

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-3

stage 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-3

stage 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-3

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: 

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-3

stage 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-3

In 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

#7 lore raw
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_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-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_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-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() 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).

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
author
#8 lore raw
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.57

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.

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_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-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_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-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: 
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() 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).

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.

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

#9 lore raw
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_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-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_span then 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_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.

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
maintainer
#10 lore raw
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_mask was 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 cp
 
 static 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(struct
 static 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_s
 
 	cpumask_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 ta
 	if (!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;
 }
 
#11 lore raw
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_mask was 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
index 637f610c7059..260592d143d8 100644
@@ -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 t
 
 	for_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
maintainer
#12 lore raw
Quoted 3 lines · Mel Gorman

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.

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_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.

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_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).

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_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.

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.

#13 lore raw
Quoted 7 lines · Peter Zijlstra
Quoted 3 lines · Mel Gorman

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.

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_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.

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_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).

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_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.

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_STREAM and UDP_RR around 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-v1r3

Duration 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
maintainer
#14 lore raw
Quoted 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, not select_idle_mask so it can return an idle candidate that is not in p->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 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_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.

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_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).

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_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.

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_STREAM and UDP_RR around 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-v1r3

Duration 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

--
Mel Gorman
SUSE Labs

maintainer
#15 lore raw
Quoted 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 c
 
 static 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_s
 
 	cpumask_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);
 	}
#16 lore raw
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_cores crud), which brings core scanning under SIS_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
maintainer
#17 lore raw
Quoted 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.

maintainer
#18 lore raw
In reply to Mel Gorman
Quoted 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_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.

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_smt is 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.

maintainer
#19 lore raw
In reply to Peter Zijlstra
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_mask was 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 cp
 
 static 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(struct
 static 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_s
 
        cpumask_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 ta
        if (!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;
 }
 
#20 lore raw
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_mask was 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 smt

    hackbench -l 2000 -g 128

tip 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 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

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
author
#21 lore raw
In reply to Mel Gorman
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