Skip to contentSkip to conversation

sched/fair: Capacity aware wakeup rework

PATCH Superseded Valentin Schneider 2 participants 7 messages Jan 24, 2020 Scheduler

v2 of 4 Superseded Latest is v4 →

lore
Share & tools
lore
#0 lore raw

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

#1 lore raw

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

---
 kernel/sched/fair.c | 37 +++++++++++++++++++++++++++++++++++++
 1 file changed, 37 insertions(+)
kernel/sched/fair.c +37 -0
index fe4e0d7753756..c44b135f61ad0 100644
@@ -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;
 
Signature · 1 line
2.24.0
#2 lore raw

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

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.

#3 lore raw

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

#4 lore raw

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

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

#5 lore raw

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

In reply to Valentin Schneider

From: 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
index dfb64c08a407a..00911884b7e7a 100644
@@ -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
#6 lore raw

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

In reply to Valentin Schneider

From: 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
index c44b135f61ad0..8097a279ee7dd 100644
@@ -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