[PATCH v2 0/3] sched/fair: Capacity aware wakeup rework

[PATCH v2 0/3] sched/fair: Capacity aware wakeup rework

[Valentin Schneider]

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    bigs

vanilla/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

[Valentin Schneider]

From: Morten Rasmussen <morten.rasmussen@arm.com>

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      bigs

which 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    bigs

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

Co-authored-by: Valentin Schneider <valentin.schneider@arm.com>
Signed-off-by: Morten Rasmussen <morten.rasmussen@arm.com>
Signed-off-by: Valentin Schneider <valentin.schneider@arm.com>
---
 kernel/sched/fair.c | 37 +++++++++++++++++++++++++++++++++++++
 1 file changed, 37 insertions(+)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index fe4e0d7753756..c44b135f61ad0 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -5894,6 +5894,38 @@ static int select_idle_cpu(struct task_struct *p, struct sched_domain *sd, int t
 	return 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;
 
-- 
2.24.0

[PATCH v2 2/3] sched/topology: Remove SD_BALANCE_WAKE on asymmetric capacity systems

[Valentin Schneider]

From: Morten Rasmussen <morten.rasmussen@arm.com>

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

Signed-off-by: Morten Rasmussen <morten.rasmussen@arm.com>
[Changelog tweaks]
Signed-off-by: Valentin Schneider <valentin.schneider@arm.com>
---
 kernel/sched/topology.c | 15 +++------------
 1 file changed, 3 insertions(+), 12 deletions(-)

diff --git a/kernel/sched/topology.c b/kernel/sched/topology.c
index dfb64c08a407a..00911884b7e7a 100644
--- a/kernel/sched/topology.c
+++ b/kernel/sched/topology.c
@@ -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;
-- 
2.24.0

[PATCH v2 3/3] sched/fair: Kill wake_cap()

[Valentin Schneider]

From: Morten Rasmussen <morten.rasmussen@arm.com>

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.

Signed-off-by: Morten Rasmussen <morten.rasmussen@arm.com>
[Changelog tweaks]
Signed-off-by: Valentin Schneider <valentin.schneider@arm.com>
---
 kernel/sched/fair.c | 30 +-----------------------------
 1 file changed, 1 insertion(+), 29 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index c44b135f61ad0..8097a279ee7dd 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -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();
-- 
2.24.0

Re: [PATCH v2 1/3] sched/fair: Add asymmetric CPU capacity wakeup scan

[Valentin Schneider]

(copied over from the v1 thread)

On 24/01/2020 12:59, Quentin Perret wrote:
> Hey Valentin,
> 
> On Friday 24 Jan 2020 at 12:42:53 (+0000), Valentin Schneider wrote:
>> +/*
>> + * 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;
>> +
> 
> 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.
> 

Yeah, I think you're right, it's the exact same scenario here.

>> +	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;
> 
> 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

[Quentin Perret]

On Friday 24 Jan 2020 at 14:14:47 (+0000), Valentin Schneider wrote:
> 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.

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

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

[Valentin Schneider]

On 24/01/2020 15:11, Quentin Perret wrote:
>> 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.
> 
> 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.
> 

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

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

> Thanks,
> Quentin
>