sched/fair: Capacity aware wakeup rework
v2 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 |
Revisions
=========
v1 -> v2:
Removed unrelated select_idle_core() change
[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 | 67 +++++++++++++++++++++++------------------ kernel/sched/topology.c | 15 ++------- 2 files changed, 41 insertions(+), 41 deletions(-)
--
2.24.0
PATCH v2 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 | 37 +++++++++++++++++++++++++++++++++++++ 1 file changed, 37 insertions(+)
kernel/sched/fair.c +37 -0
@@ -5894,6 +5894,38 @@ 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 sched_domain *sd; +struct cpumask *cpus; +int cpu; + +if (!static_branch_unlikely (&sched_asym_cpucapacity)) +return -1 ; + + sd =rcu_dereference (per_cpu (sd_asym_cpucapacity, target)); +if (!sd) +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 (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 v2 1/3] sched/fair: Add asymmetric CPU capacity wakeup scan
(copied over from the v1 thread)
Quoted 16 lines · Quentin Perret
Hey Valentin,
Quoted 13 lines · Valentin Schneider
kernel/sched/fair.c +13
-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 sched_domain *sd; +struct cpumask *cpus; +int cpu; + +if (!static_branch_unlikely (&sched_asym_cpucapacity)) +return -1 ; +
Quoted 9 lines
kernel/sched/fair.c static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, int t · line 5913
Quoted 4 lines
kernel/sched/fair.c +4
-0+ 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()andwake_cap()need one, but since we're going to use them, you'll want to sync here too I think.
Yeah, I think you're right, it's the exact same scenario here.
Quoted 6 lines
Quoted 6 lines
kernel/sched/fair.c +6
-0+ cpus =this_cpu_cpumask_var_ptr (select_idle_mask); +cpumask_and (cpus,sched_domain_span (sd), p->cpus_ptr); + +for_each_cpu_wrap (cpu, cpus, target) { +if (!available_idle_cpu (cpu)) +continue ;
Quoted 9 lines
kernel/sched/fair.c static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, int t · line 5923
Quoted 4 lines
kernel/sched/fair.c +4
-0+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.
If we fail to find a big enough CPU, we'll just fallback to the rest of select_idle_sibling() which will pick an idle CPU, just without caring about capacity.
Now an alternative here would be to:
- return the first idle CPU on which the task fits (what the above does)
- else, return the biggest idle CPU we found (this could e.g. still steer the task towards a medium on a tri-capacity system)
I think what we were trying to go with here is to not entirely hijack select_idle_sibling(). If we go with the above alternative, topologies with sched_asym_cpucapacity enabled would only ever see select_idle_capacity() and not the rest of select_idle_sibling(). Not sure if it's a bad thing or not, but it's something to ponder over.
Re: [PATCH v2 1/3] sched/fair: Add asymmetric CPU capacity wakeup scan
Quoted 8 lines · Valentin Schneider
If we fail to find a big enough CPU, we'll just fallback to the rest of
select_idle_sibling()which will pick an idle CPU, just without caring about capacity.Now an alternative here would be to:
- return the first idle CPU on which the task fits (what the above does)
- else, return the biggest idle CPU we found (this could e.g. still steer the task towards a medium on a tri-capacity system)
Sounds reasonable to me.
Quoted 5 lines
I think what we were trying to go with here is to not entirely hijack
select_idle_sibling(). If we go with the above alternative, topologies withsched_asym_cpucapacityenabled would only ever seeselect_idle_capacity()and not the rest ofselect_idle_sibling(). Not sure if it's a bad thing or not, but it's something to ponder over.
Right, I would think your suggestion above is a pretty sensible policy for asymmetric systems, and I don't think the rest of select_idle_sibling() will do a much better job on such systems at finding an idle CPU than select_idle_capacity() would do, but I see your point.
Now, not having to re-iterate over the CPUs again might keep the wakeup latency a bit lower -- perhaps something noticeable with hackbench ? Worth a try.
In any case, no strong opinion. With that missing call to sync_entity_load_avg() fixed, the patch looks pretty decent to me.
Thanks,
Quentin
Re: [PATCH v2 1/3] sched/fair: Add asymmetric CPU capacity wakeup scan
Quoted 12 lines · Quentin Perret
Quoted 5 lines
I think what we were trying to go with here is to not entirely hijack
select_idle_sibling(). If we go with the above alternative, topologies withsched_asym_cpucapacityenabled would only ever seeselect_idle_capacity()and not the rest ofselect_idle_sibling(). Not sure if it's a bad thing or not, but it's something to ponder over.Right, I would think your suggestion above is a pretty sensible policy for asymmetric systems, and I don't think the rest of
select_idle_sibling()will do a much better job on such systems at finding an idle CPU thanselect_idle_capacity()would do, but I see your point.
Quoted 4 lines
Now, not having to re-iterate over the CPUs again might keep the wakeup latency a bit lower -- perhaps something noticeable with hackbench ? Worth a try.
Agreed. Removing SD_BALANCE_WAKE causes most of the perf delta here, I'll try to get some statistics on the same versions but with and without the extra select_idle_capacity() policy and see how noticeable it is.
I might still do it if the delta is lost in the noise, just gotta put my brain cells to work. One thing I'm thinking is maybe we're not guaranteed to have sd_asym_cpucapacity being a superset of sd_llc, so we would need to go through select_idle_sibling() to cover for the rest, although I think this falls in the category of topologies we highly recommend *not* to build (or expose, in case of people playing games with cpu-map).
Quoted 3 lines
In any case, no strong opinion. With that missing call to
sync_entity_load_avg()fixed, the patch looks pretty decent to me.
Thanks for having a look!
Quoted 3 lines
Thanks,
Quentin
PATCH v2 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 v2 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