sched/fair: Capacity aware wakeup rework
cover sched/fair: Capacity aware wakeup rework
This series is about replacing the current wakeup logic for asymmetric CPU capacity topologies, i.e. wake_cap().
Details are in patch 1, the TL;DR is that wake_cap() works fine for "legacy" big.LITTLE systems (e.g. Juno), since the Last Level Cache (LLC) domain of a CPU only spans CPUs of the same capacity, but somewhat broken for newer DynamIQ systems (e.g. Dragonboard 845C), since the LLC domain of a CPU can span all CPUs in the system. Both example boards are supported in mainline.
A bit of history
================
Due to the old Energy Model (EM) used until Android Common Kernel v4.14 which grafted itself onto the sched domain hierarchy, mobile topologies have been represented with "phantom domains"; IOW we'd make a DynamIQ topology look like a big.LITTLE one:
actual hardware:
+-------------------+
| L3 |
+----+----+----+----+
| L2 | L2 | L2 | L2 |
+----+----+----+----+
|CPU0|CPU1|CPU2|CPU3|
+----+----+----+----+
^^^^^ ^^^^^
LITTLEs bigsvanilla/mainline topology:
MC [ ]
0 1 2 3
phantom domains topology:
DIE [ ]
MC [ ][ ]
0 1 2 3
With the newer, mainline EM this is no longer required, and wake_cap() is the last sticking point to getting rid of this legacy crud. More details and examples are in patch 1.
Notes
=====
This removes the use of SD_BALANCE_WAKE for asymmetric CPU capacity topologies (which are the last mainline users of that flag), as such it shouldn't be a surprise that this comes with significant improvements to wake-intensive workloads: wakeups no longer go through the select_task_rq_fair() slow-path.
Testing
=======
I've picked sysbench --test=threads to mimic Peter's testing mentioned in
commit 182a85f8a119 ("sched: Disable wakeup balancing")
Sysbench results are the number of events handled in a fixed amount of time, so higher is better. Hackbench results are the usual time taken for the thing, so lower is better.
Note: the 'X%' stats are the percentiles, so 50% is the 50th percentile.
Juno r0 ("legacy" big.LITTLE)
+++++++++++++++++++++++++++++
This is 2 bigs and 4 LITTLEs:
+---------------+ +-------+ | L2 | | L2 | +---+---+---+---+ +---+---+ | L | L | L | L | | B | B | +---+---+---+---+ +---+---+
100 iterations of 'hackbench':
| | -PATCH | +PATCH | DELTA (%) | |-------+----------+----------+-----------| | mean | 0.622300 | 0.613000 | -1.494 | | std | 0.028886 | 0.015178 | -47.456 | | min | 0.579000 | 0.585000 | +1.036 | | 50% | 0.619500 | 0.610000 | -1.533 | | 75% | 0.633250 | 0.621000 | -1.934 | | 99% | 0.680270 | 0.649110 | -4.581 | | max | 0.806000 | 0.660000 | -18.114 |
100 iterations of 'sysbench --max-time=5 --max-requests=-1 --test=threads --num-threads=6 run':
| | -PATCH | +PATCH | DELTA(%) | |-------+--------------+--------------+----------| | mean | 9695.500000 | 12556.930000 | +29.513 | | std | 2897.875263 | 2941.268452 | +1.497 | | min | 7011.000000 | 6800.000000 | -3.010 | | 50% | 8305.000000 | 13636.500000 | +64.196 | | 75% | 11924.500000 | 15273.250000 | +28.083 | | 99% | 15310.140000 | 15558.860000 | +1.625 | | max | 15522.000000 | 15644.000000 | +0.786 |
Pixel3 (DynamIQ)
++++++++++++++++
Ideally I would have used a DB845C but had a few issues with mine, so I went with a mainline-ish Pixel3 instead [1]. It's still the same SoC under the hood (Snapdragon 845), which has 4 bigs and 4 LITTLEs:
+-------------------------------+ | L3 | +---+---+---+---+---+---+---+---+ | L2| L2| L2| L2| L2| L2| L2| L2| +---+---+---+---+---+---+---+---+ | L | L | L | L | B | B | B | B | +---+---+---+---+---+---+---+---+
Default topology (single MC domain)
-----------------------------------
100 iterations of 'hackbench -l 200'
| | -PATCH | +PATCH | DELTA (%) | |-------+----------+----------+-----------| | mean | 1.165010 | 1.116370 | -4.175 | | std | 0.124682 | 0.111952 | -10.210 | | min | 0.962000 | 0.936000 | -2.703 | | 50% | 1.133500 | 1.090000 | -3.838 | | 75% | 1.251500 | 1.186000 | -5.234 | | 99% | 1.483050 | 1.350040 | -8.969 | | max | 1.488000 | 1.354000 | -9.005 |
100 iterations of 'sysbench --max-time=5 --max-requests=-1 --test=threads --num-threads=8 run':
| | -PATCH | +PATCH | DELTA (%) | |-------+-------------+------------+-----------| | mean | 7108.310000 | 8455.97000 | +18.959 | | std | 199.431854 | 248.27939 | +24.493 | | min | 6655.000000 | 7875.00000 | +18.332 | | 50% | 7107.500000 | 8454.50000 | +18.952 | | 75% | 7255.500000 | 8622.50000 | +18.841 | | 99% | 7539.540000 | 8981.21000 | +19.121 | | max | 7593.000000 | 9101.00000 | +19.860 |
Phantom domains (MC + DIE)
--------------------------
This is mostly included for the sake of completeness.
100 iterations of 'sysbench --max-time=5 --max-requests=-1 --test=threads --num-threads=8 run':
| | -PATCH | +PATCH | DELTA (%) | |-------+-------------+-------------+-----------| | mean | 5568.930000 | 7884.180000 | +41.574 | | std | 238.341587 | 218.808407 | -8.195 | | min | 4961.000000 | 7222.000000 | +45.575 | | 50% | 5575.500000 | 7885.500000 | +41.431 | | 75% | 5711.500000 | 8031.250000 | +40.615 | | 99% | 6178.000000 | 8395.670000 | +35.896 | | max | 6178.000000 | 8462.000000 | +36.970 |
[1]: https://git.linaro.org/people/amit.pundir/linux.git/log/?h=blueline-mainline-tracking
Morten Rasmussen (3):
sched/fair: Add asymmetric CPU capacity wakeup scan sched/topology: Remove SD_BALANCE_WAKE on asymmetric capacity systems sched/fair: Kill wake_cap()
kernel/sched/fair.c | 69 +++++++++++++++++++++++------------------ kernel/sched/topology.c | 15 ++------- 2 files changed, 42 insertions(+), 42 deletions(-)
--
2.24.0
PATCH 1/3 sched/fair: Add asymmetric CPU capacity wakeup scan
From: Morten Rasmussen <[email protected]>
On asymmetric CPU capacity topologies, we currently rely on wake_cap() to drive select_task_rq_fair() towards either
- its slow-path (find_idlest_cpu()) if either the previous or current (waking) CPU has too little capacity for the waking task
- its fast-path (select_idle_sibling()) otherwise
Commit 3273163c6775 ("sched/fair: Let asymmetric CPU configurations balance at wake-up") points out that this relies on the assumption that "[...]the CPU capacities within an SD_SHARE_PKG_RESOURCES domain (sd_llc) are homogeneous".
This assumption no longer holds on newer generations of big.LITTLE systems (DynamIQ), which can accommodate CPUs of different compute capacity within a single LLC domain. To hopefully paint a better picture, a regular big.LITTLE topology would look like this:
+---------+ +---------+
| L2 | | L2 |
+----+----+ +----+----+
|CPU0|CPU1| |CPU2|CPU3|
+----+----+ +----+----+
^^^ ^^^
LITTLEs bigswhich would result in the following scheduler topology:
DIE [ ] <- sd_asym_cpucapacity
MC [ ] [ ] <- sd_llc
0 1 2 3
Conversely, a DynamIQ topology could look like:
+-------------------+
| L3 |
+----+----+----+----+
| L2 | L2 | L2 | L2 |
+----+----+----+----+
|CPU0|CPU1|CPU2|CPU3|
+----+----+----+----+
^^^^^ ^^^^^
LITTLEs bigswhich would result in the following scheduler topology:
MC [ ] <- sd_llc, sd_asym_cpucapacity
0 1 2 3
What this means is that, on DynamIQ systems, we could pass the wake_cap() test (IOW presume the waking task fits on the CPU capacities of some LLC domain), thus go through select_idle_sibling().
This function operates on an LLC domain, which here spans both bigs and LITTLEs, so it could very well pick a CPU of too small capacity for the task, despite there being fitting idle CPUs - it very much depends on the CPU iteration order, on which we have absolutely no guarantees capacity-wise.
Introduce yet another select_idle_sibling() helper function that takes CPU capacity into account. The policy is basically to pick the first idle CPU which is big enough for the task (task_util * margin < cpu_capacity).
Unlike other select_idle_sibling() helpers, this one operates on the sd_asym_cpucapacity sched_domain pointer, which is guaranteed to span all known CPU capacities in the system. As such, this will work for both "legacy" big.LITTLE (LITTLEs & bigs split at MC, joined at DIE) and for newer DynamIQ systems (e.g. LITTLEs and bigs in the same MC domain).
--- kernel/sched/fair.c | 39 ++++++++++++++++++++++++++++++++++++++- 1 file changed, 38 insertions(+), 1 deletion(-)
kernel/sched/fair.c +38 -1
@@ -5772,7 +5772,7 @@ void __update_idle_core(struct rq *rq)*/ static int select_idle_core (struct task_struct *p,struct sched_domain *sd,int target) { -struct cpumask *cpus =this_cpu_cpumask_var_ptr (select_idle_mask); +struct cpumask *cpus;int core, cpu;if (!static_branch_likely (&sched_smt_present))
@@ -5781,6 +5781,7 @@ static int select_idle_core(struct task_struct *p, struct sched_domain *sd, intif (!test_idle_cores (target, false))return -1 ; + cpus =this_cpu_cpumask_var_ptr (select_idle_mask);cpumask_and (cpus,sched_domain_span (sd), p->cpus_ptr);for_each_cpu_wrap (core, cpus, target) {
@@ -5894,6 +5895,37 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, int treturn cpu; } +/* +* Scan the asym_capacity domain for idle CPUs; pick the first idle one on which +* the task fits. +*/ +static int select_idle_capacity (struct task_struct *p,int target) +{ +struct cpumask *cpus =this_cpu_cpumask_var_ptr (select_idle_mask); +struct sched_domain *sd; +int cpu; + +if (!static_branch_unlikely (&sched_asym_cpucapacity)) +return -1 ; + + sd =rcu_dereference (per_cpu (sd_asym_cpucapacity, target)); +if (!sd) +return -1 ; + +cpumask_and (cpus,sched_domain_span (sd), p->cpus_ptr); + +for_each_cpu_wrap (cpu, cpus, target) { +if (!available_idle_cpu (cpu)) +continue ; +if (!task_fits_capacity (p,capacity_of (cpu))) +continue ; + +return cpu; + } + +return -1 ; +} +/* * Try and locate an idle core/thread in the LLC cache domain. */
@@ -5902,6 +5934,11 @@ static int select_idle_sibling(struct task_struct *p, int prev, int target)struct sched_domain *sd;int i, recent_used_cpu; +/* For asymmetric capacities, try to be smart about the placement */ + i =select_idle_capacity (p, target); +if ((unsigned )i < nr_cpumask_bits) +return i; +if (available_idle_cpu (target) ||sched_idle_cpu (target))return target;
Signature · 1 line
2.24.0
Re: [PATCH 1/3] sched/fair: Add asymmetric CPU capacity wakeup scan
kernel/sched/fair.c void __update_idle_core(struct rq *rq) · line 5775
Quoted 6 lines · Valentin Schneider
kernel/sched/fair.c +1
-1@@ -5772,7 +5772,7 @@ void __update_idle_core(struct rq *rq)*/ static int select_idle_core (struct task_struct *p,struct sched_domain *sd,int target) { -struct cpumask *cpus =this_cpu_cpumask_var_ptr (select_idle_mask); +struct cpumask *cpus;
ARGH, this is rebase damage and wants to be in select_idle_capacity(). Apologies, let me resend.
Re: [PATCH 1/3] sched/fair: Add asymmetric CPU capacity wakeup scan
In reply to Valentin SchneiderHey Valentin,
Quoted 7 lines · Valentin Schneider
kernel/sched/fair.c +7
-0+/* +* Scan the asym_capacity domain for idle CPUs; pick the first idle one on which +* the task fits. +*/ +static int select_idle_capacity (struct task_struct *p,int target) +{ +struct cpumask *cpus =this_cpu_cpumask_var_ptr (select_idle_mask);
kernel/sched/fair.c static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, int t · line 5914
Quoted 10 lines
kernel/sched/fair.c +10
-0+struct sched_domain *sd; +int cpu; + +if (!static_branch_unlikely (&sched_asym_cpucapacity)) +return -1 ; + + sd =rcu_dereference (per_cpu (sd_asym_cpucapacity, target)); +if (!sd) +return -1 ; +
You might want 'sync_entity_load_avg(&p->se)' here no ? find_idlest_cpu() and wake_cap() need one, but since we're going to use them, you'll want to sync here too I think.
kernel/sched/fair.c static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, int t · line 5924
Quoted 10 lines
kernel/sched/fair.c +10
-0+cpumask_and (cpus,sched_domain_span (sd), p->cpus_ptr); + +for_each_cpu_wrap (cpu, cpus, target) { +if (!available_idle_cpu (cpu)) +continue ; +if (!task_fits_capacity (p,capacity_of (cpu))) +continue ; + +return cpu; + }
If we found an idle CPU, but not one big enough, should we still go ahead and choose it ? Misfit / idle balance will fix that later when a big CPU does become available.
kernel/sched/fair.c static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, int t · line 5925
Quoted 4 lines
kernel/sched/fair.c +4
-0+ +return -1 ; +} +
Thanks,
Quentin
PATCH 2/3 sched/topology: Remove SD_BALANCE_WAKE on asymmetric capacity systems
In reply to Valentin SchneiderFrom: Morten Rasmussen <[email protected]>
SD_BALANCE_WAKE was previously added to lower sched_domain levels on asymmetric CPU capacity systems by commit 9ee1cda5ee25 ("sched/core: Enable SD_BALANCE_WAKE for asymmetric capacity systems") to enable the use of find_idlest_cpu() and friends to find an appropriate CPU for tasks.
That responsibility has now been shifted to select_idle_sibling() and friends, and hence the flag can be removed. Note that this causes asymmetric CPU capacity systems to no longer enter the slow wakeup path (find_idlest_cpu()) on wakeups - only on execs and forks (which is aligned with all other mainline topologies).
--- kernel/sched/topology.c | 15 +++------------ 1 file changed, 3 insertions(+), 12 deletions(-)
kernel/sched/topology.c +3 -12
@@ -1374,18 +1374,9 @@ sd_init(struct sched_domain_topology_level *tl,* Convert topological properties into behaviour. */ -if (sd->flags &SD_ASYM_CPUCAPACITY ) { -struct sched_domain *t = sd; - -/* -* Don't attempt to spread across CPUs of different capacities. -*/ -if (sd->child) - sd->child->flags &= ~SD_PREFER_SIBLING ; - -for_each_lower_domain (t) - t->flags |=SD_BALANCE_WAKE ; - } +/* Don't attempt to spread across CPUs of different capacities. */ +if ((sd->flags &SD_ASYM_CPUCAPACITY ) && sd->child) + sd->child->flags &= ~SD_PREFER_SIBLING ;if (sd->flags &SD_SHARE_CPUCAPACITY ) { sd->imbalance_pct =110 ;
Signature · 1 line
2.24.0
PATCH 3/3 sched/fair: Kill wake_cap()
In reply to Valentin SchneiderFrom: Morten Rasmussen <[email protected]>
Capacity-awareness in the wake-up path previously involved disabling wake_affine in certain scenarios. We have just made select_idle_sibling() capacity-aware, so this isn't needed anymore.
Remove wake_cap() entirely.
--- kernel/sched/fair.c | 30 +----------------------------- 1 file changed, 1 insertion(+), 29 deletions(-)
kernel/sched/fair.c +1 -29
@@ -6124,33 +6124,6 @@ static unsigned long cpu_util_without(int cpu, struct task_struct *p) return min_t(unsigned long, util, capacity_orig_of(cpu)); } -/* -* Disable WAKE_AFFINE in the case where task @p doesn't fit in the -* capacity of either the waking CPU @cpu or the previous CPU @prev_cpu. -* -* In that case WAKE_AFFINE doesn't make sense and we'll let -* BALANCE_WAKE sort things out. -*/ -static int wake_cap (struct task_struct *p,int cpu,int prev_cpu) -{ -long min_cap, max_cap; - -if (!static_branch_unlikely (&sched_asym_cpucapacity)) -return 0 ; - - min_cap =min (capacity_orig_of (prev_cpu),capacity_orig_of (cpu)); - max_cap =cpu_rq (cpu)->rd->max_cpu_capacity; - -/* Minimum capacity is close to max, no need to abort wake_affine */ -if (max_cap - min_cap < max_cap >>3 ) -return 0 ; - -/* Bring task utilization in sync with prev_cpu */ -sync_entity_load_avg (&p->se); - -return !task_fits_capacity (p, min_cap); -} -/* * Predicts what cpu_util(@cpu) would return if @p was migrated (and enqueued) * to @dst_cpu.
@@ -6415,8 +6388,7 @@ select_task_rq_fair(struct task_struct *p, int prev_cpu, int sd_flag, int wake_f new_cpu = prev_cpu; } - want_affine = !wake_wide (p) && !wake_cap (p, cpu, prev_cpu) && -cpumask_test_cpu (cpu, p->cpus_ptr); + want_affine = !wake_wide (p) &&cpumask_test_cpu (cpu, p->cpus_ptr); }rcu_read_lock ();
Signature · 1 line
2.24.0