Skip to contentSkip to conversation

sched/fair: NOHZ cleanups and misfit improvement

PATCH Superseded Valentin Schneider 3 participants 17 messages Jan 17, 2019 – Feb 11, 2019 Scheduler

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore
#0 lore raw

cover sched/fair: NOHZ cleanups and misfit improvement

In

commit 5fbdfae5221a ("sched/fair: Kick nohz balance if rq->misfit_task_load")

was added a trigger for nohz kicks, which is required to offload misfit tasks from LITTLE to big CPUs. However, those kicks could be issued a lot more frequently than what is strictly needed.

This patch-set brings some unrelated nohz code cleanups, and tunes down unneeded nohz kicks.

- Patches [1-3] do some cleaning up of the current nohz code
- Patches [4-5] tweak the nohz kick conditions for asymmetric systems

* Testing
** kick_ilb() hits
This causes a large reduction in calls to kick_ilb() (and thus subsequent rescheduling interrupts & useless nohz balance calls) in most scenarios.

The "best case" one is running NR_BIG_CPUS big tasks, which I tested with 4 50% periodic tasks running for 5 seconds on my HiKey960 (4x4 big.LITTLE):

  | CPU | hits (baseline) | hits (patchset) |
  |-----+-----------------+-----------------|
  |   0 |              31 |              41 |
  |   1 |              21 |               3 |
  |   2 |              35 |               2 |
  |   3 |               9 |               4 |
  |-----+-----------------+-----------------|
  |   4 |             170 |               4 |
  |   5 |             573 |               4 |
  |   6 |             544 |               4 |
  |   7 |             579 |               4 |

Something a bit less idealistic with NR_CPUS-1 big tasks still shows some improvements (7 100% tasks running for 5 seconds on my HiKey960):

  | CPU | hits (baseline) | hits (patchset) |
  |-----+-----------------+-----------------|
  |   0 |              14 |             122 |
  |   1 |              47 |             162 |
  |   2 |              11 |             156 |
  |   3 |               9 |               3 |
  |-----+-----------------+-----------------|
  |   4 |              53 |               6 |
  |   5 |             276 |              13 |
  |   6 |             312 |               7 |
  |   7 |             250 |              11 |

I was surprised to see such an increase in calls to kick_ilb() from LITTLE CPUs ([0-3]), but after a bit of investigation it turns out that the big CPUs would always run nohz_balancer_kick() a jiffy before the LITTLEs, so the LITTLEs would always bail out because nohz.next_balance had just been updated before they called nohz_balancer_kick(). IOW,

time_before(now, nohz.next_balance)

would always be true on CPUs [0-3] during my workload. Quieting the kicks issued by the big CPUs allowed the LITTLEs to execute nohz_balancer_kick() past that condition, explaining the higher number of kicks issued from LITTLE CPUs.

** misfit behaviour
For good measure I also ran the usual misfit tests [1] which showed no particular change.

* Notes

Since patch 05 introduces yet another label in kick_nohz_balancer(), I benchmarked splitting its "slowpath" (all of the rcu derefs) into its own function and didn't find any real overhead. If folks don't hate the idea I can add it to a v2 or post it separately.

[1]: https://github.com/ARM-software/lisa/blob/next/lisa/tests/kernel/scheduler/misfit.py

Valentin Schneider (5):
sched/fair: Use for_each_cpu_and for asym-packing nohz kicks sched/fair: Explain LLC nohz kick condition sched/fair: Prune nohz_balancer_kick() comment block sched/fair: Tune down misfit nohz kicks sched/fair: Skip LLC nohz logic for asymmetric systems

 kernel/sched/fair.c | 62 ++++++++++++++++++++++++++++++++-------------
 1 file changed, 44 insertions(+), 18 deletions(-)

--
2.20.1

#1 lore raw

PATCH 1/5 sched/fair: Use for_each_cpu_and for asym-packing nohz kicks

Calling 'nohz_balance_exit_idle(rq)' will always clear 'rq->cpu' from 'nohz.idle_cpus_mask' if it is set. Since it is called at the top of 'nohz_balancer_kick()', 'rq->cpu' will never be set in 'nohz.idle_cpus_mask' if it is accessed in the rest of the function.

"And" the 'sched_domain_span()' with 'nohz.idle_cpus_mask' and drop the '(i == cpu)' check since 'rq->cpu' will never be iterated over.

While at it, clean up a condition alignment.

---
 kernel/sched/fair.c | 8 ++------
 1 file changed, 2 insertions(+), 6 deletions(-)
kernel/sched/fair.c +2 -6
index ca469646ebe1..380a72e42678 100644
@@ -9557,7 +9557,7 @@ static void nohz_balancer_kick(struct rq *rq)
 	sd = rcu_dereference(rq->sd);
 	if (sd) {
 		if ((rq->cfs.h_nr_running >= 1) &&
-				check_cpu_capacity(rq, sd)) {
+		    check_cpu_capacity(rq, sd)) {
 			flags = NOHZ_KICK_MASK;
 			goto unlock;
 		}
@@ -9565,11 +9565,7 @@ static void nohz_balancer_kick(struct rq *rq)
 
 	sd = rcu_dereference(per_cpu(sd_asym_packing, cpu));
 	if (sd) {
-		for_each_cpu(i, sched_domain_span(sd)) {
-			if (i == cpu ||
-			    !cpumask_test_cpu(i, nohz.idle_cpus_mask))
-				continue;
-
+		for_each_cpu_and(i, sched_domain_span(sd), nohz.idle_cpus_mask) {
 			if (sched_asym_prefer(i, cpu)) {
 				flags = NOHZ_KICK_MASK;
 				goto unlock;
Signature · 1 line
2.20.1
#2 lore raw

[tip:sched/core] sched/fair: Simplify nohz_balancer_kick()

sched/fair: Simplify nohz_balancer_kick()
Commit-ID:  7edab78d7400ea0997f8e2e971004d824b5bb511
Gitweb:     https://git.kernel.org/tip/7edab78d7400ea0997f8e2e971004d824b5bb511
Author:     Valentin Schneider <[email protected]>
AuthorDate: Thu, 17 Jan 2019 15:34:07 +0000
Committer:  Ingo Molnar <[email protected]>
CommitDate: Mon, 11 Feb 2019 08:02:16 +0100

sched/fair: Simplify nohz_balancer_kick()

Calling 'nohz_balance_exit_idle(rq)' will always clear 'rq->cpu' from 'nohz.idle_cpus_mask' if it is set. Since it is called at the top of 'nohz_balancer_kick()', 'rq->cpu' will never be set in 'nohz.idle_cpus_mask' if it is accessed in the rest of the function.

Combine the 'sched_domain_span()' with 'nohz.idle_cpus_mask' and drop the '(i == cpu)' check since 'rq->cpu' will never be iterated over.

While at it, clean up a condition alignment.

---
 kernel/sched/fair.c | 8 ++------
 1 file changed, 2 insertions(+), 6 deletions(-)
kernel/sched/fair.c +2 -6
index 58edbbdeb661..0692c8ff6ff6 100644
@@ -9615,7 +9615,7 @@ static void nohz_balancer_kick(struct rq *rq)
 	sd = rcu_dereference(rq->sd);
 	if (sd) {
 		if ((rq->cfs.h_nr_running >= 1) &&
-				check_cpu_capacity(rq, sd)) {
+		    check_cpu_capacity(rq, sd)) {
 			flags = NOHZ_KICK_MASK;
 			goto unlock;
 		}
@@ -9623,11 +9623,7 @@ static void nohz_balancer_kick(struct rq *rq)
 
 	sd = rcu_dereference(per_cpu(sd_asym_packing, cpu));
 	if (sd) {
-		for_each_cpu(i, sched_domain_span(sd)) {
-			if (i == cpu ||
-			    !cpumask_test_cpu(i, nohz.idle_cpus_mask))
-				continue;
-
+		for_each_cpu_and(i, sched_domain_span(sd), nohz.idle_cpus_mask) {
 			if (sched_asym_prefer(i, cpu)) {
 				flags = NOHZ_KICK_MASK;
 				goto unlock;
#3 lore raw

PATCH 2/5 sched/fair: Explain LLC nohz kick condition

In reply to Valentin Schneider

Provide a comment explaining the LLC related nohz kick in nohz_balancer_kick().

---
 kernel/sched/fair.c | 9 +++++++--
 1 file changed, 7 insertions(+), 2 deletions(-)
kernel/sched/fair.c +7 -2
index 380a72e42678..62f6aead7e73 100644
@@ -9543,8 +9543,13 @@ static void nohz_balancer_kick(struct rq *rq)
 	sds = rcu_dereference(per_cpu(sd_llc_shared, cpu));
 	if (sds) {
 		/*
-		 * XXX: write a coherent comment on why we do this.
-		 * See also: http://lkml.kernel.org/r/[email protected]
+		 * If there is an imbalance between LLC domains (IOW we could
+		 * increase the overall cache use), we need some less-loaded LLC
+		 * domain to pull some load. Likewise, we may need to spread
+		 * load within the current LLC domain (e.g. packed SMT cores but
+		 * other CPUs are idle). We can't really know from here how busy
+		 * the others are - so just get a nohz balance going if it looks
+		 * like this LLC domain has tasks we could move.
 		 */
 		nr_busy = atomic_read(&sds->nr_busy_cpus);
 		if (nr_busy > 1) {
Signature · 1 line
2.20.1
#4 lore raw

[tip:sched/core] sched/fair: Explain LLC nohz kick condition

sched/fair: Explain LLC nohz kick condition
Commit-ID:  892d59c22208be820a5463b5f74eb7f0b7f2b03a
Gitweb:     https://git.kernel.org/tip/892d59c22208be820a5463b5f74eb7f0b7f2b03a
Author:     Valentin Schneider <[email protected]>
AuthorDate: Thu, 17 Jan 2019 15:34:08 +0000
Committer:  Ingo Molnar <[email protected]>
CommitDate: Mon, 11 Feb 2019 08:02:17 +0100

sched/fair: Explain LLC nohz kick condition

Provide a comment explaining the LLC related nohz kick in nohz_balancer_kick().

---
 kernel/sched/fair.c | 9 +++++++--
 1 file changed, 7 insertions(+), 2 deletions(-)
kernel/sched/fair.c +7 -2
index 0692c8ff6ff6..ac6b52d8c79e 100644
@@ -9601,8 +9601,13 @@ static void nohz_balancer_kick(struct rq *rq)
 	sds = rcu_dereference(per_cpu(sd_llc_shared, cpu));
 	if (sds) {
 		/*
-		 * XXX: write a coherent comment on why we do this.
-		 * See also: http://lkml.kernel.org/r/[email protected]
+		 * If there is an imbalance between LLC domains (IOW we could
+		 * increase the overall cache use), we need some less-loaded LLC
+		 * domain to pull some load. Likewise, we may need to spread
+		 * load within the current LLC domain (e.g. packed SMT cores but
+		 * other CPUs are idle). We can't really know from here how busy
+		 * the others are - so just get a nohz balance going if it looks
+		 * like this LLC domain has tasks we could move.
 		 */
 		nr_busy = atomic_read(&sds->nr_busy_cpus);
 		if (nr_busy > 1) {
#5 lore raw

PATCH 3/5 sched/fair: Prune nohz_balancer_kick() comment block

In reply to Valentin Schneider

The comment block for that function lists the heuristics for triggering a nohz kick, but the most recent ones (blocked load updates, misfit) aren't included, and some of them (LLC nohz logic, asym packing) are no longer in sync with the code.

The conditions are either simple enough or properly commented, so get rid of that list instead of letting it grow.

---
 kernel/sched/fair.c | 11 ++---------
 1 file changed, 2 insertions(+), 9 deletions(-)
kernel/sched/fair.c +2 -9
index 62f6aead7e73..7658f9d76a9a 100644
@@ -9493,15 +9493,8 @@ static void kick_ilb(unsigned int flags)
 }
 
 /*
- * Current heuristic for kicking the idle load balancer in the presence
- * of an idle cpu in the system.
- *   - This rq has more than one task.
- *   - This rq has at least one CFS task and the capacity of the CPU is
- *     significantly reduced because of RT tasks or IRQs.
- *   - At parent of LLC scheduler domain level, this cpu's scheduler group has
- *     multiple busy cpu.
- *   - For SD_ASYM_PACKING, if the lower numbered cpu's in the scheduler
- *     domain span are idle.
+ * Current decision point for kicking the idle load balancer in the presence
+ * of idle CPUs in the system.
  */
 static void nohz_balancer_kick(struct rq *rq)
 {
Signature · 1 line
2.20.1
#6 lore raw

[tip:sched/core] sched/fair: Prune, fix and simplify the nohz_balancer_kick() comment block

sched/fair: Prune, fix and simplify the nohz_balancer_kick() comment block
Commit-ID:  9f132742d5c4146397fef0c5b09fe220576a5bb2
Gitweb:     https://git.kernel.org/tip/9f132742d5c4146397fef0c5b09fe220576a5bb2
Author:     Valentin Schneider <[email protected]>
AuthorDate: Thu, 17 Jan 2019 15:34:09 +0000
Committer:  Ingo Molnar <[email protected]>
CommitDate: Mon, 11 Feb 2019 08:02:18 +0100

sched/fair: Prune, fix and simplify the nohz_balancer_kick() comment block

The comment block for that function lists the heuristics for triggering a nohz kick, but the most recent ones (blocked load updates, misfit) aren't included, and some of them (LLC nohz logic, asym packing) are no longer in sync with the code.

The conditions are either simple enough or properly commented, so get rid of that list instead of letting it grow.

---
 kernel/sched/fair.c | 11 ++---------
 1 file changed, 2 insertions(+), 9 deletions(-)
kernel/sched/fair.c +2 -9
index ac6b52d8c79e..f44da9b491ff 100644
@@ -9551,15 +9551,8 @@ static void kick_ilb(unsigned int flags)
 }
 
 /*
- * Current heuristic for kicking the idle load balancer in the presence
- * of an idle cpu in the system.
- *   - This rq has more than one task.
- *   - This rq has at least one CFS task and the capacity of the CPU is
- *     significantly reduced because of RT tasks or IRQs.
- *   - At parent of LLC scheduler domain level, this cpu's scheduler group has
- *     multiple busy cpu.
- *   - For SD_ASYM_PACKING, if the lower numbered cpu's in the scheduler
- *     domain span are idle.
+ * Current decision point for kicking the idle load balancer in the presence
+ * of idle CPUs in the system.
  */
 static void nohz_balancer_kick(struct rq *rq)
 {
#7 lore raw

PATCH 4/5 sched/fair: Tune down misfit nohz kicks

In reply to Valentin Schneider

In

commmit 3b1baa6496e6 ("sched/fair: Add 'group_misfit_task' load-balance type")

we set rq->misfit_task_load whenever the current running task has a utilization greater than 80% of rq->cpu_capacity. A non-zero value in this field enables misfit load balancing.

However, if the task being looked at is already running on a CPU of highest capacity, there's nothing more we can do for it. We can currently spot this in update_sd_pick_busiest(), which prevents us from selecting a sched_group of group_type == group_misfit_task as the busiest group, but we don't do any of that in nohz_balancer_kick().

This means that we could repeatedly kick nohz CPUs when there's no improvements in terms of load balance to be done.

Introduce a check_misfit_status() helper that returns true iff there is a CPU in the system that could give more CPU capacity to a rq's misfit task - IOW, there exists a CPU of higher capacity_orig or the rq's CPU is severely pressured by rt/IRQ.

---
 kernel/sched/fair.c | 22 +++++++++++++++++++++-
 1 file changed, 21 insertions(+), 1 deletion(-)
kernel/sched/fair.c +21 -1
index 7658f9d76a9a..291dfdb0183f 100644
@@ -8012,6 +8012,18 @@ check_cpu_capacity(struct rq *rq, struct sched_domain *sd)
 				(rq->cpu_capacity_orig * 100));
 }
 
+/*
+ * Check whether a rq has a misfit task and if it looks like we can actually
+ * help that task: we can migrate the task to a CPU of higher capacity, or
+ * the task's current CPU is heavily pressured.
+ */
+static inline int check_misfit_status(struct rq *rq, struct sched_domain *sd)
+{
+	return rq->misfit_task_load &&
+		(rq->cpu_capacity_orig < rq->rd->max_cpu_capacity ||
+		 check_cpu_capacity(rq, sd));
+}
+
 /*
  * Group imbalance indicates (and tries to solve) the problem where balancing
  * groups is inadequate due to ->cpus_allowed constraints.
@@ -9527,7 +9539,7 @@ static void nohz_balancer_kick(struct rq *rq)
 	if (time_before(now, nohz.next_balance))
 		goto out;
 
-	if (rq->nr_running >= 2 || rq->misfit_task_load) {
+	if (rq->nr_running >= 2) {
 		flags = NOHZ_KICK_MASK;
 		goto out;
 	}
@@ -9561,6 +9573,14 @@ static void nohz_balancer_kick(struct rq *rq)
 		}
 	}
 
+	sd = rcu_dereference(per_cpu(sd_asym_cpucapacity, cpu));
+	if (sd) {
+		if (check_misfit_status(rq, sd)) {
+			flags = NOHZ_KICK_MASK;
+			goto unlock;
+		}
+	}
+
 	sd = rcu_dereference(per_cpu(sd_asym_packing, cpu));
 	if (sd) {
 		for_each_cpu_and(i, sched_domain_span(sd), nohz.idle_cpus_mask) {
Signature · 1 line
2.20.1
maintainer
#8 lore raw

Re: [PATCH 4/5] sched/fair: Tune down misfit nohz kicks

Review static void nohz_balancer_kick(struct rq *rq)

Quoted 42 lines · Valentin Schneider

In

commmit 3b1baa6496e6 ("sched/fair: Add 'group_misfit_task' load-balance type")

we set rq->misfit_task_load whenever the current running task has a utilization greater than 80% of rq->cpu_capacity. A non-zero value in this field enables misfit load balancing.

However, if the task being looked at is already running on a CPU of highest capacity, there's nothing more we can do for it. We can currently spot this in update_sd_pick_busiest(), which prevents us from selecting a sched_group of group_type == group_misfit_task as the busiest group, but we don't do any of that in nohz_balancer_kick().

This means that we could repeatedly kick nohz CPUs when there's no improvements in terms of load balance to be done.

Introduce a check_misfit_status() helper that returns true iff there is a CPU in the system that could give more CPU capacity to a rq's misfit task - IOW, there exists a CPU of higher capacity_orig or the rq's CPU is severely pressured by rt/IRQ.

(quoted diff) +7 -1
+static inline int check_misfit_status(struct rq *rq, struct sched_domain *sd)
+{
+	return rq->misfit_task_load &&
+		(rq->cpu_capacity_orig < rq->rd->max_cpu_capacity ||
+		 check_cpu_capacity(rq, sd));
+}
@@ -9527,7 +9539,7 @@ static void nohz_balancer_kick(struct rq *rq)
 	if (time_before(now, nohz.next_balance))
 		goto out;
 
-	if (rq->nr_running >= 2 || rq->misfit_task_load) {
+	if (rq->nr_running >= 2) {
 		flags = NOHZ_KICK_MASK;
 		goto out;
 	}
@@ -9561,6 +9573,14 @@ static void nohz_balancer_kick(struct rq *rq)
	sd = rcu_dereference(rq->sd);
	if (sd) {
		if ((rq->cfs.h_nr_running >= 1) &&
		    check_cpu_capacity(rq, sd)) {
			flags = NOHZ_KICK_MASK;
			goto unlock;

Review static void nohz_balancer_kick(struct rq *rq) · line 9582

Quoted 10 lines
(quoted diff) +7 -0
 		}
 	}
 
+	sd = rcu_dereference(per_cpu(sd_asym_cpucapacity, cpu));
+	if (sd) {
+		if (check_misfit_status(rq, sd)) {
+			flags = NOHZ_KICK_MASK;
+			goto unlock;
+		}
+	}

So while the exact @sd to use for check_cpu_capacity() likely doesn't matter; this is a 'implicit' test for actually having asym_capacity.

Fair enough I suppose. However, now that you wrote such a nice comment for the sd_llc_shared case, these other two cases are sad to not have a comment.

So how about you add something like:

kernel/sched/fair.c +14 -2
@@ -9589,8 +9589,12 @@ static void nohz_balancer_kick(struct rq
 
 	sd = rcu_dereference(rq->sd);
 	if (sd) {
-		if ((rq->cfs.h_nr_running >= 1) &&
-		    check_cpu_capacity(rq, sd)) {
+		/*
+		 * If there's a CFS task and the current CPU has reduced
+		 * capacity; kick the ILB to see if there's a better CPU to run
+		 * on.
+		 */
+		if (rq->cfs.h_nr_running >= 1 && check_cpu_capacity(rq, sd)) {
 			flags = NOHZ_KICK_MASK;
 			goto unlock;
 		}
@@ -9598,6 +9602,10 @@ static void nohz_balancer_kick(struct rq
 
 	sd = rcu_dereference(per_cpu(sd_asym_cpucapacity, cpu));
 	if (sd) {
+		/*
+		 * When ASYM_CAPACITY; see if there's a higher capacity CPU to
+		 * run the misfit task on.
+		 */
 		if (check_misfit_status(rq, sd)) {
 			flags = NOHZ_KICK_MASK;
 			goto unlock;
@@ -9606,6 +9614,10 @@ static void nohz_balancer_kick(struct rq
 
 	sd = rcu_dereference(per_cpu(sd_asym_packing, cpu));
 	if (sd) {
+		/*
+		 * When ASYM_PACKING; see if there's a more preferred CPU going
+		 * idle; in which case, kick the ILB to move tasks around.
+		 */
 		for_each_cpu_and(i, sched_domain_span(sd), nohz.idle_cpus_mask) {
 			if (sched_asym_prefer(i, cpu)) {
 				flags = NOHZ_KICK_MASK;
#9 lore raw

Re: [PATCH 4/5] sched/fair: Tune down misfit nohz kicks

Hi,

On 06/02/2019 16:04, Peter Zijlstra wrote:
[...]

Quoted 11 lines

Review static void nohz_balancer_kick(struct rq *rq)

Quoted 1 line
(quoted diff) +0 -0
@@ -9561,6 +9573,14 @@ static void nohz_balancer_kick(struct rq *rq)
	sd = rcu_dereference(rq->sd);
	if (sd) {
		if ((rq->cfs.h_nr_running >= 1) &&
		    check_cpu_capacity(rq, sd)) {
			flags = NOHZ_KICK_MASK;
			goto unlock;
Quoted 3 lines
(quoted diff) +0 -0
 		}
 	}
 
Quoted 11 lines

Review static void nohz_balancer_kick(struct rq *rq) · line 9582

Quoted 7 lines
(quoted diff) +7 -0
+	sd = rcu_dereference(per_cpu(sd_asym_cpucapacity, cpu));
+	if (sd) {
+		if (check_misfit_status(rq, sd)) {
+			flags = NOHZ_KICK_MASK;
+			goto unlock;
+		}
+	}

So while the exact @sd to use for check_cpu_capacity() likely doesn't matter; this is a 'implicit' test for actually having asym_capacity.

I did feel compelled to use the "right" @sd to have a coherent imbalance_pct being used - on big.LITTLE, the @sd above this hunk would be MC (117 imbalance_pct) whereas the sd_asym_cpucapacity one would be DIE (125 imbalance_pct).

Quoted 35 lines

Fair enough I suppose. However, now that you wrote such a nice comment for the sd_llc_shared case, these other two cases are sad to not have a comment.

So how about you add something like:

kernel/sched/fair.c +10 -2
@@ -9589,8 +9589,12 @@ static void nohz_balancer_kick(struct rq
 
 	sd = rcu_dereference(rq->sd);
 	if (sd) {
-		if ((rq->cfs.h_nr_running >= 1) &&
-		    check_cpu_capacity(rq, sd)) {
+		/*
+		 * If there's a CFS task and the current CPU has reduced
+		 * capacity; kick the ILB to see if there's a better CPU to run
+		 * on.
+		 */
+		if (rq->cfs.h_nr_running >= 1 && check_cpu_capacity(rq, sd)) {
 			flags = NOHZ_KICK_MASK;
 			goto unlock;
 		}
@@ -9598,6 +9602,10 @@ static void nohz_balancer_kick(struct rq
 
 	sd = rcu_dereference(per_cpu(sd_asym_cpucapacity, cpu));
 	if (sd) {
+		/*
+		 * When ASYM_CAPACITY; see if there's a higher capacity CPU to
+		 * run the misfit task on.
+		 */
 		if (check_misfit_status(rq, sd)) {
 			flags = NOHZ_KICK_MASK;
 			goto unlock;

kernel/sched/fair.c static void nohz_balancer_kick(struct rq · line 9620

Quoted 7 lines
kernel/sched/fair.c +4 -0
@@ -9606,6 +9614,10 @@ static void nohz_balancer_kick(struct rq
 
 	sd = rcu_dereference(per_cpu(sd_asym_packing, cpu));
 	if (sd) {
+		/*
+		 * When ASYM_PACKING; see if there's a more preferred CPU going
+		 * idle; in which case, kick the ILB to move tasks around.
+		 */

s/going idle/currently idle/, no?

Quoted 4 lines
kernel/sched/fair.c +0 -0
 		for_each_cpu_and(i, sched_domain_span(sd), nohz.idle_cpus_mask) {
 			if (sched_asym_prefer(i, cpu)) {
 				flags = NOHZ_KICK_MASK;
maintainer
#10 lore raw

Re: [PATCH 4/5] sched/fair: Tune down misfit nohz kicks

Quoted 27 lines · Valentin Schneider

Hi,

On 06/02/2019 16:04, Peter Zijlstra wrote:
[...]

Quoted 11 lines

Review static void nohz_balancer_kick(struct rq *rq)

Quoted 1 line
(quoted diff) +0 -0
@@ -9561,6 +9573,14 @@ static void nohz_balancer_kick(struct rq *rq)
	sd = rcu_dereference(rq->sd);
	if (sd) {
		if ((rq->cfs.h_nr_running >= 1) &&
		    check_cpu_capacity(rq, sd)) {
			flags = NOHZ_KICK_MASK;
			goto unlock;
Quoted 3 lines
(quoted diff) +0 -0
 		}
 	}
 
Quoted 11 lines

Review static void nohz_balancer_kick(struct rq *rq) · line 9582

Quoted 7 lines
(quoted diff) +7 -0
+	sd = rcu_dereference(per_cpu(sd_asym_cpucapacity, cpu));
+	if (sd) {
+		if (check_misfit_status(rq, sd)) {
+			flags = NOHZ_KICK_MASK;
+			goto unlock;
+		}
+	}

So while the exact @sd to use for check_cpu_capacity() likely doesn't matter; this is a 'implicit' test for actually having asym_capacity.

Quoted 4 lines

I did feel compelled to use the "right" @sd to have a coherent imbalance_pct being used - on big.LITTLE, the @sd above this hunk would be MC (117 imbalance_pct) whereas the sd_asym_cpucapacity one would be DIE (125 imbalance_pct).

Fair enough.

Quoted 10 lines

kernel/sched/fair.c static void nohz_balancer_kick(struct rq · line 9620

Quoted 8 lines
kernel/sched/fair.c +4 -0
@@ -9606,6 +9614,10 @@ static void nohz_balancer_kick(struct rq
 
 	sd = rcu_dereference(per_cpu(sd_asym_packing, cpu));
 	if (sd) {
+		/*
+		 * When ASYM_PACKING; see if there's a more preferred CPU going
+		 * idle; in which case, kick the ILB to move tasks around.
+		 */

s/going idle/currently idle/, no?

Yah.. D'0h..

Quoted 4 lines
Quoted 4 lines
kernel/sched/fair.c +0 -0
 		for_each_cpu_and(i, sched_domain_span(sd), nohz.idle_cpus_mask) {
 			if (sched_asym_prefer(i, cpu)) {
 				flags = NOHZ_KICK_MASK;
#11 lore raw

PATCH 5/5 sched/fair: Skip LLC nohz logic for asymmetric systems

In reply to Valentin Schneider

The LLC nohz condition will become true as soon as >=2 CPUs in a single LLC domain are busy. On big.LITTLE systems, this translates to two or more CPUs of a "cluster" (big or LITTLE) being busy.

Issuing a nohz kick in these conditions isn't desired for asymmetric systems, as if the busy CPUs can provide enough compute capacity to the running tasks, then we can leave the nohz CPUs in peace.

Skip the LLC nohz condition for asymmetric systems, and rely on nr_running & capacity checks to trigger nohz kicks when the system actually needs them.

---
 kernel/sched/fair.c | 12 ++++++++++++
 1 file changed, 12 insertions(+)
kernel/sched/fair.c +12 -0
index 291dfdb0183f..ff27bf56e8d4 100644
@@ -9545,6 +9545,17 @@ static void nohz_balancer_kick(struct rq *rq)
 	}
 
 	rcu_read_lock();
+
+	if (static_branch_unlikely(&sched_asym_cpucapacity))
+		/*
+		 * For asymmetric systems, we do not want to nicely balance
+		 * cache use, instead we want to embrace asymmetry and only
+		 * ensure tasks have enough CPU capacity.
+		 *
+		 * Skip the LLC logic because it's not relevant in that case.
+		 */
+		goto check_capacity;
+
 	sds = rcu_dereference(per_cpu(sd_llc_shared, cpu));
 	if (sds) {
 		/*
@@ -9564,6 +9575,7 @@ static void nohz_balancer_kick(struct rq *rq)
 
 	}
 
+check_capacity:
 	sd = rcu_dereference(rq->sd);
 	if (sd) {
 		if ((rq->cfs.h_nr_running >= 1) &&
Signature · 1 line
2.20.1
maintainer
#12 lore raw

Re: [PATCH 5/5] sched/fair: Skip LLC nohz logic for asymmetric systems

Quoted 30 lines · Valentin Schneider

The LLC nohz condition will become true as soon as >=2 CPUs in a single LLC domain are busy. On big.LITTLE systems, this translates to two or more CPUs of a "cluster" (big or LITTLE) being busy.

Issuing a nohz kick in these conditions isn't desired for asymmetric systems, as if the busy CPUs can provide enough compute capacity to the running tasks, then we can leave the nohz CPUs in peace.

Skip the LLC nohz condition for asymmetric systems, and rely on nr_running & capacity checks to trigger nohz kicks when the system actually needs them.

---
 kernel/sched/fair.c | 12 ++++++++++++
 1 file changed, 12 insertions(+)
kernel/sched/fair.c +4 -0
index 291dfdb0183f..ff27bf56e8d4 100644
@@ -9545,6 +9545,17 @@ static void nohz_balancer_kick(struct rq *rq)
 	}
 
 	rcu_read_lock();
+
+	if (static_branch_unlikely(&sched_asym_cpucapacity))
+		/*
+		 * For asymmetric systems, we do not want to nicely balance

kernel/sched/fair.c static void nohz_balancer_kick(struct rq *rq) · line 9561

Quoted 10 lines
kernel/sched/fair.c +7 -0
+		 * cache use, instead we want to embrace asymmetry and only
+		 * ensure tasks have enough CPU capacity.
+		 *
+		 * Skip the LLC logic because it's not relevant in that case.
+		 */
+		goto check_capacity;
+
 	sds = rcu_dereference(per_cpu(sd_llc_shared, cpu));
 	if (sds) {
 		/*

Since (before this) the actual order of the various tests doesn't matter, it's a logical cascade of conditions for which to KICK_MASK.

We can easily reorder and short-circuit the cascase like so, no?

The only concern is if sd_llc_shared < sd_asym_capacity; in which case we just lost a balance opportunity. Not sure how to best retain that though.

kernel/sched/fair.c +38 -28
@@ -9568,25 +9568,6 @@ static void nohz_balancer_kick(struct rq
 	}
 
 	rcu_read_lock();
-	sds = rcu_dereference(per_cpu(sd_llc_shared, cpu));
-	if (sds) {
-		/*
-		 * If there is an imbalance between LLC domains (IOW we could
-		 * increase the overall cache use), we need some less-loaded LLC
-		 * domain to pull some load. Likewise, we may need to spread
-		 * load within the current LLC domain (e.g. packed SMT cores but
-		 * other CPUs are idle). We can't really know from here how busy
-		 * the others are - so just get a nohz balance going if it looks
-		 * like this LLC domain has tasks we could move.
-		 */
-		nr_busy = atomic_read(&sds->nr_busy_cpus);
-		if (nr_busy > 1) {
-			flags = NOHZ_KICK_MASK;
-			goto unlock;
-		}
-
-	}
-
 	sd = rcu_dereference(rq->sd);
 	if (sd) {
 		/*
@@ -9600,6 +9581,20 @@ static void nohz_balancer_kick(struct rq
 		}
 	}
 
+	sd = rcu_dereference(per_cpu(sd_asym_packing, cpu));
+	if (sd) {
+		/*
+		 * When ASYM_PACKING; see if there's a more preferred CPU going
+		 * idle; in which case, kick the ILB to move tasks around.
+		 */
+		for_each_cpu_and(i, sched_domain_span(sd), nohz.idle_cpus_mask) {
+			if (sched_asym_prefer(i, cpu)) {
+				flags = NOHZ_KICK_MASK;
+				goto unlock;
+			}
+		}
+	}
+
 	sd = rcu_dereference(per_cpu(sd_asym_cpucapacity, cpu));
 	if (sd) {
 		/*
@@ -9610,21 +9605,36 @@ static void nohz_balancer_kick(struct rq
 			flags = NOHZ_KICK_MASK;
 			goto unlock;
 		}
+
+		/*
+		 * For asymmetric systems, we do not want to nicely balance
+		 * cache use, instead we want to embrace asymmetry and only
+		 * ensure tasks have enough CPU capacity.
+		 *
+		 * Skip the LLC logic because it's not relevant in that case.
+		 */
+		goto unlock;
 	}
 
-	sd = rcu_dereference(per_cpu(sd_asym_packing, cpu));
-	if (sd) {
+	sds = rcu_dereference(per_cpu(sd_llc_shared, cpu));
+	if (sds) {
 		/*
-		 * When ASYM_PACKING; see if there's a more preferred CPU going
-		 * idle; in which case, kick the ILB to move tasks around.
+		 * If there is an imbalance between LLC domains (IOW we could
+		 * increase the overall cache use), we need some less-loaded LLC
+		 * domain to pull some load. Likewise, we may need to spread
+		 * load within the current LLC domain (e.g. packed SMT cores but
+		 * other CPUs are idle). We can't really know from here how busy
+		 * the others are - so just get a nohz balance going if it looks
+		 * like this LLC domain has tasks we could move.
 		 */
-		for_each_cpu_and(i, sched_domain_span(sd), nohz.idle_cpus_mask) {
-			if (sched_asym_prefer(i, cpu)) {
-				flags = NOHZ_KICK_MASK;
-				goto unlock;
-			}
+		nr_busy = atomic_read(&sds->nr_busy_cpus);
+		if (nr_busy > 1) {
+			flags = NOHZ_KICK_MASK;
+			goto unlock;
 		}
+
 	}
+
 unlock:
 	rcu_read_unlock();
 out:
#13 lore raw

Re: [PATCH 5/5] sched/fair: Skip LLC nohz logic for asymmetric systems

Hi,

On 06/02/2019 16:14, Peter Zijlstra wrote:
[...]

Quoted 13 lines
Quoted 13 lines
kernel/sched/fair.c +9 -0
@@ -9545,6 +9545,17 @@ static void nohz_balancer_kick(struct rq *rq)
 	}
 
 	rcu_read_lock();
+
+	if (static_branch_unlikely(&sched_asym_cpucapacity))
+		/*
+		 * For asymmetric systems, we do not want to nicely balance
+		 * cache use, instead we want to embrace asymmetry and only
+		 * ensure tasks have enough CPU capacity.
+		 *
+		 * Skip the LLC logic because it's not relevant in that case.
+		 */
Quoted 9 lines

Review static void nohz_balancer_kick(struct rq *rq) · line 9561

Quoted 5 lines
(quoted diff) +2 -0
+		goto check_capacity;
+
 	sds = rcu_dereference(per_cpu(sd_llc_shared, cpu));
 	if (sds) {
 		/*

Since (before this) the actual order of the various tests doesn't matter, it's a logical cascade of conditions for which to KICK_MASK.

Ah, I assumed the order did matter somewhat with the "cheaper" LLC check first and the more costly loops further down in case we are still looking for a reason to do a kick.

Quoted 6 lines

We can easily reorder and short-circuit the cascase like so, no?

The only concern is if sd_llc_shared < sd_asym_capacity; in which case we just lost a balance opportunity. Not sure how to best retain that though.

I'm afraid I don't follow - we don't lose a balance opportunity with the below change (compared to the original patch), do we?

Quoted 96 lines
kernel/sched/fair.c +38 -28
@@ -9568,25 +9568,6 @@ static void nohz_balancer_kick(struct rq
 	}
 
 	rcu_read_lock();
-	sds = rcu_dereference(per_cpu(sd_llc_shared, cpu));
-	if (sds) {
-		/*
-		 * If there is an imbalance between LLC domains (IOW we could
-		 * increase the overall cache use), we need some less-loaded LLC
-		 * domain to pull some load. Likewise, we may need to spread
-		 * load within the current LLC domain (e.g. packed SMT cores but
-		 * other CPUs are idle). We can't really know from here how busy
-		 * the others are - so just get a nohz balance going if it looks
-		 * like this LLC domain has tasks we could move.
-		 */
-		nr_busy = atomic_read(&sds->nr_busy_cpus);
-		if (nr_busy > 1) {
-			flags = NOHZ_KICK_MASK;
-			goto unlock;
-		}
-
-	}
-
 	sd = rcu_dereference(rq->sd);
 	if (sd) {
 		/*
@@ -9600,6 +9581,20 @@ static void nohz_balancer_kick(struct rq
 		}
 	}
 
+	sd = rcu_dereference(per_cpu(sd_asym_packing, cpu));
+	if (sd) {
+		/*
+		 * When ASYM_PACKING; see if there's a more preferred CPU going
+		 * idle; in which case, kick the ILB to move tasks around.
+		 */
+		for_each_cpu_and(i, sched_domain_span(sd), nohz.idle_cpus_mask) {
+			if (sched_asym_prefer(i, cpu)) {
+				flags = NOHZ_KICK_MASK;
+				goto unlock;
+			}
+		}
+	}
+
 	sd = rcu_dereference(per_cpu(sd_asym_cpucapacity, cpu));
 	if (sd) {
 		/*
@@ -9610,21 +9605,36 @@ static void nohz_balancer_kick(struct rq
 			flags = NOHZ_KICK_MASK;
 			goto unlock;
 		}
+
+		/*
+		 * For asymmetric systems, we do not want to nicely balance
+		 * cache use, instead we want to embrace asymmetry and only
+		 * ensure tasks have enough CPU capacity.
+		 *
+		 * Skip the LLC logic because it's not relevant in that case.
+		 */
+		goto unlock;
 	}
 
-	sd = rcu_dereference(per_cpu(sd_asym_packing, cpu));
-	if (sd) {
+	sds = rcu_dereference(per_cpu(sd_llc_shared, cpu));
+	if (sds) {
 		/*
-		 * When ASYM_PACKING; see if there's a more preferred CPU going
-		 * idle; in which case, kick the ILB to move tasks around.
+		 * If there is an imbalance between LLC domains (IOW we could
+		 * increase the overall cache use), we need some less-loaded LLC
+		 * domain to pull some load. Likewise, we may need to spread
+		 * load within the current LLC domain (e.g. packed SMT cores but
+		 * other CPUs are idle). We can't really know from here how busy
+		 * the others are - so just get a nohz balance going if it looks
+		 * like this LLC domain has tasks we could move.
 		 */
-		for_each_cpu_and(i, sched_domain_span(sd), nohz.idle_cpus_mask) {
-			if (sched_asym_prefer(i, cpu)) {
-				flags = NOHZ_KICK_MASK;
-				goto unlock;
-			}
+		nr_busy = atomic_read(&sds->nr_busy_cpus);
+		if (nr_busy > 1) {
+			flags = NOHZ_KICK_MASK;
+			goto unlock;
 		}
+
 	}
+
 unlock:
 	rcu_read_unlock();
 out:
maintainer
#14 lore raw

Re: [PATCH 5/5] sched/fair: Skip LLC nohz logic for asymmetric systems

Quoted 27 lines · Valentin Schneider

Hi,

On 06/02/2019 16:14, Peter Zijlstra wrote:
[...]

Quoted 13 lines
Quoted 13 lines
kernel/sched/fair.c +9 -0
@@ -9545,6 +9545,17 @@ static void nohz_balancer_kick(struct rq *rq)
 	}
 
 	rcu_read_lock();
+
+	if (static_branch_unlikely(&sched_asym_cpucapacity))
+		/*
+		 * For asymmetric systems, we do not want to nicely balance
+		 * cache use, instead we want to embrace asymmetry and only
+		 * ensure tasks have enough CPU capacity.
+		 *
+		 * Skip the LLC logic because it's not relevant in that case.
+		 */
Quoted 9 lines

Review static void nohz_balancer_kick(struct rq *rq) · line 9561

Quoted 5 lines
(quoted diff) +2 -0
+		goto check_capacity;
+
 	sds = rcu_dereference(per_cpu(sd_llc_shared, cpu));
 	if (sds) {
 		/*

Since (before this) the actual order of the various tests doesn't matter, it's a logical cascade of conditions for which to KICK_MASK.

Quoted 3 lines

Ah, I assumed the order did matter somewhat with the "cheaper" LLC check first and the more costly loops further down in case we are still looking for a reason to do a kick.

I did not in fact consider that; I only looked at the logical structure of the thing. You might want to double check :-)

Quoted 9 lines
Quoted 6 lines

We can easily reorder and short-circuit the cascase like so, no?

The only concern is if sd_llc_shared < sd_asym_capacity; in which case we just lost a balance opportunity. Not sure how to best retain that though.

I'm afraid I don't follow - we don't lose a balance opportunity with the below change (compared to the original patch), do we?

What if each big/little cluster would have multiple cache domains? Would we not want to spread the cache usage inside the big/little resp. ?

#15 lore raw

Re: [PATCH 5/5] sched/fair: Skip LLC nohz logic for asymmetric systems

On 07/02/2019 09:56, Peter Zijlstra wrote:
[...]

Quoted 6 lines
Quoted 2 lines

I'm afraid I don't follow - we don't lose a balance opportunity with the below change (compared to the original patch), do we?

What if each big/little cluster would have multiple cache domains? Would we not want to spread the cache usage inside the big/little resp. ?

Ah I see - somewhat, yes. And we kindof already hit that issue - on regular big.LITTLE each "cluster" (big & LITTLE) will have their own L2, but there's no L3 to share. That means

- sd_llc == MC
- sd_asym_cpucapacity == DIE

(which I believe is what you meant by sd_llc_shared < sd_asym_capacity)

However the LLC nohz kick condition is way too broad and will keep kicking if we just have 2 busy LITTLEs with 1 task each, which could be a correct placement if they were just running some small background task.

I'd argue that since we don't have SMT, <=1 task per CPU means we can't do anything better to spread cache use within the "cluster", and we have to rely on the other conditions (mostly rq->nr_running and misfit) to move things around when we really need to.

The extra kicks are there on non asymmetric topologies as well, so we could imagine an additional gate for the LLC kick that would look like:

/* If SMT, <=1 task per CPU can be suboptimal
* If we have a parent (and thus a sibling), we may need to move some tasks to
* our sibling.
* If we have asymmetry, asymmetric placement can be fine so just rely on the
* other kick conditions
*/
if (static_key_likely(&sched_smt_present) ||

      (!static_key_unlikely(&sched_asym_cpucapacity) && sd->parent)) {
	  // LLC kick stuff here

}

but I'd argue the extra nohz kicks have more impact on asymmetric systems.

#16 lore raw
In reply to Valentin Schneider

Hi,

On 17/01/2019 15:34, Valentin Schneider wrote:
[...]

Quoted 10 lines

Valentin Schneider (5):
sched/fair: Use for_each_cpu_and for asym-packing nohz kicks sched/fair: Explain LLC nohz kick condition sched/fair: Prune nohz_balancer_kick() comment block sched/fair: Tune down misfit nohz kicks sched/fair: Skip LLC nohz logic for asymmetric systems

 kernel/sched/fair.c | 62 ++++++++++++++++++++++++++++++++-------------
 1 file changed, 44 insertions(+), 18 deletions(-)

Gentle ping

Quoted 3 lines

--
2.20.1