Skip to contentSkip to conversation

sched/fair: fix load balancer behavior when cgroup is in use

RFC PATCH Superseded Tejun Heo 5 participants 69 messages Apr 24, 2017 – May 5, 2017 Scheduler

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore

Tejun Heo

author
#0 lore raw

RFC PATCH 1/1 sched/fair: fix load balancer behavior when cgroup is in use

Hello,

We've noticed scheduling latency spike when cgroup is in use even when the machine is idle enough with moderate scheduling frequency and single level of cgroup nesting. More details are in the patch descriptions but here's a schbench run from the root cgroup.

# ~/schbench -m 2 -t 16 -s 10000 -c 15000 -r 30
Latency percentiles (usec)

	 50.0000th: 26
	 75.0000th: 62
	 90.0000th: 74
	 95.0000th: 86
	 *99.0000th: 887
	 99.5000th: 3692
	 99.9000th: 10832
	 min=0, max=13374

And here's one from inside a first level cgroup.

# ~/schbench -m 2 -t 16 -s 10000 -c 15000 -r 30
Latency percentiles (usec)

	 50.0000th: 31
	 75.0000th: 65
	 90.0000th: 71
	 95.0000th: 91
	 *99.0000th: 7288
	 99.5000th: 10352
	 99.9000th: 12496
	 min=0, max=13023

The p99 latency spike got tracked down to runnable_load_avg not being propagated through nested cfs_rqs and thus load_balance() operating on out-of-sync load information. It ended up picking the wrong CPU as load balance target often enough to significantly impact p99 latency.

This patchset fixes the issue by always propagating runnable_load_avg so that, regardless of nesting, every cfs_rq's runnable_load_avg is the sum of the scaled loads of all tasks queued below it.

As a side effect, this changes the load_avg behavior of sched_entities associated cfs_rq's. It doesn't seem wrong to me and I can't think of a better / cleaner way, but if there is, please let me know.

This patchset is on top of v4.11-rc8 and contains the following two patches.

sched/fair: Fix how load gets propagated from cfs_rq to its sched_entity sched/fair: Always propagate runnable_load_avg

diffstat follows.

 kernel/sched/fair.c |   46 +++++++++++++++++++---------------------------
 1 file changed, 19 insertions(+), 27 deletions(-)

Thanks.

Signature · 1 line
tejun
author
#1 lore raw

PATCH 1/2 sched/fair: Fix how load gets propagated from cfs_rq to its sched_entity

09a43ace1f98 ("sched/fair: Propagate load during synchronous attach/detach") added immediate load propagation from cfs_rq to its sched_entity then to the parent cfs_rq; however, what gets propagated doesn't seem to make sense.

It repeats the tg_weight calculation done in calc_cfs_shares() but only uses it to compensate for shares being out of date. After that, it sets the sched_entity's load_avg to the load_avg of the corresponding cfs_rq.

This doesn't make sense as the cfs_rq's load_avg is some fraction of its total weight, which the sched_entity's weight has nothing to with. For example, if the cfs_rq has a single constant load 1 task the cfs_rq's load_avg would be around 1. If that cfs_rq is the only active sched_entity in the parent cfs_rq which has the maximum weight, the sched_entity's load should be around the maximum weight but update_tg_cfs_load() ends up overriding it to 1.

At the parent's level, the absolute value of load_avg inside a child cfs_rq doesn't mean anything. Only the ratio against its weight is meaningful.

This patch changes update_tg_cfs_load() to normalize the runnable_load_avg of the cfs_rq and then scale it to the matching sched_entity's freshly calculated shares for propagation. Use of runnable_load_avg instead of load_avg is intentional and keeps the parent's runnable_load_avg true to the sum of scaled loads of all tasks queued under it which is critical for the correction operation of load balancer. The next patch will depend on it.

Cc Vincent Guittot <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Mike Galbraith <[email protected]>
Cc Paul Turner <[email protected]>
---
 kernel/sched/fair.c |   46 +++++++++++++++++++---------------------------
 1 file changed, 19 insertions(+), 27 deletions(-)
kernel/sched/fair.c +19 -27
@@ -3078,37 +3078,29 @@ static inline void
 update_tg_cfs_load(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
 	struct cfs_rq *gcfs_rq = group_cfs_rq(se);
-	long delta, load = gcfs_rq->avg.load_avg;
+	long load = 0, delta;
 
 	/*
-	 * If the load of group cfs_rq is null, the load of the
-	 * sched_entity will also be null so we can skip the formula
+	 * A cfs_rq's load avg contribution to the parent should be scaled
+	 * to the sched_entity's weight.  Use freshly calculated shares
+	 * instead of @se->load.weight as the latter may not reflect
+	 * changes from the current scheduling operation.
+	 *
+	 * Note that the propagation source is runnable_load_avg instead of
+	 * load_avg.  This keeps every cfs_rq's runnable_load_avg true to
+	 * the sum of the scaled loads of all tasks queued under it, which
+	 * is important for the correct operation of the load balancer.
+	 *
+	 * This can make the sched_entity's load_avg jumpier but that
+	 * correctly reflects what would happen without cgroups if each
+	 * task's load is scaled across nesting - the load is being
+	 * averaged at the task and each cfs_rq.
 	 */
-	if (load) {
-		long tg_load;
+	if (gcfs_rq->load.weight) {
+		long shares = calc_cfs_shares(gcfs_rq, gcfs_rq->tg);
 
-		/* Get tg's load and ensure tg_load > 0 */
-		tg_load = atomic_long_read(&gcfs_rq->tg->load_avg) + 1;
-
-		/* Ensure tg_load >= load and updated with current load*/
-		tg_load -= gcfs_rq->tg_load_avg_contrib;
-		tg_load += load;
-
-		/*
-		 * We need to compute a correction term in the case that the
-		 * task group is consuming more CPU than a task of equal
-		 * weight. A task with a weight equals to tg->shares will have
-		 * a load less or equal to scale_load_down(tg->shares).
-		 * Similarly, the sched_entities that represent the task group
-		 * at parent level, can't have a load higher than
-		 * scale_load_down(tg->shares). And the Sum of sched_entities'
-		 * load must be <= scale_load_down(tg->shares).
-		 */
-		if (tg_load > scale_load_down(gcfs_rq->tg->shares)) {
-			/* scale gcfs_rq's load into tg's shares*/
-			load *= scale_load_down(gcfs_rq->tg->shares);
-			load /= tg_load;
-		}
+		load = min(gcfs_rq->runnable_load_avg *
+			   shares / gcfs_rq->load.weight, shares);
 	}
 
 	delta = load - se->avg.load_avg;
author
#2 lore raw

PATCH v2 1/2 sched/fair: Fix how load gets propagated from cfs_rq to its sched_entity

09a43ace1f98 ("sched/fair: Propagate load during synchronous attach/detach") added immediate load propagation from cfs_rq to its sched_entity then to the parent cfs_rq; however, what gets propagated doesn't seem to make sense.

It repeats the tg_weight calculation done in calc_cfs_shares() but only uses it to compensate for shares being out of date. After that, it sets the sched_entity's load_avg to the load_avg of the corresponding cfs_rq.

This doesn't make sense as the cfs_rq's load_avg is some fraction of its total weight, which the sched_entity's weight has nothing to with. For example, if the cfs_rq has a single constant load 1 task the cfs_rq's load_avg would be around 1. If that cfs_rq is the only active sched_entity in the parent cfs_rq which has the maximum weight, the sched_entity's load should be around the maximum weight but update_tg_cfs_load() ends up overriding it to 1.

At the parent's level, the absolute value of load_avg inside a child cfs_rq doesn't mean anything. Only the ratio against its weight is meaningful.

This patch changes update_tg_cfs_load() to normalize the runnable_load_avg of the cfs_rq and then scale it to the matching sched_entity's freshly calculated shares for propagation. Use of runnable_load_avg instead of load_avg is intentional and keeps the parent's runnable_load_avg true to the sum of scaled loads of all tasks queued under it which is critical for the correction operation of load balancer. The next patch will depend on it.

v2: Use min_t() to squash a build warning.

Cc Vincent Guittot <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Mike Galbraith <[email protected]>
Cc Paul Turner <[email protected]>
---
 kernel/sched/fair.c |   47 ++++++++++++++++++++---------------------------
 1 file changed, 20 insertions(+), 27 deletions(-)
kernel/sched/fair.c +20 -27
@@ -3078,37 +3078,30 @@ static inline void
 update_tg_cfs_load(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
 	struct cfs_rq *gcfs_rq = group_cfs_rq(se);
-	long delta, load = gcfs_rq->avg.load_avg;
+	long load = 0, delta;
 
 	/*
-	 * If the load of group cfs_rq is null, the load of the
-	 * sched_entity will also be null so we can skip the formula
+	 * A cfs_rq's load avg contribution to the parent should be scaled
+	 * to the sched_entity's weight.  Use freshly calculated shares
+	 * instead of @se->load.weight as the latter may not reflect
+	 * changes from the current scheduling operation.
+	 *
+	 * Note that the propagation source is runnable_load_avg instead of
+	 * load_avg.  This keeps every cfs_rq's runnable_load_avg true to
+	 * the sum of the scaled loads of all tasks queued under it, which
+	 * is important for the correct operation of the load balancer.
+	 *
+	 * This can make the sched_entity's load_avg jumpier but that
+	 * correctly reflects what would happen without cgroups if each
+	 * task's load is scaled across nesting - the load is being
+	 * averaged at the task and each cfs_rq.
 	 */
-	if (load) {
-		long tg_load;
+	if (gcfs_rq->load.weight) {
+		long shares = calc_cfs_shares(gcfs_rq, gcfs_rq->tg);
 
-		/* Get tg's load and ensure tg_load > 0 */
-		tg_load = atomic_long_read(&gcfs_rq->tg->load_avg) + 1;
-
-		/* Ensure tg_load >= load and updated with current load*/
-		tg_load -= gcfs_rq->tg_load_avg_contrib;
-		tg_load += load;
-
-		/*
-		 * We need to compute a correction term in the case that the
-		 * task group is consuming more CPU than a task of equal
-		 * weight. A task with a weight equals to tg->shares will have
-		 * a load less or equal to scale_load_down(tg->shares).
-		 * Similarly, the sched_entities that represent the task group
-		 * at parent level, can't have a load higher than
-		 * scale_load_down(tg->shares). And the Sum of sched_entities'
-		 * load must be <= scale_load_down(tg->shares).
-		 */
-		if (tg_load > scale_load_down(gcfs_rq->tg->shares)) {
-			/* scale gcfs_rq's load into tg's shares*/
-			load *= scale_load_down(gcfs_rq->tg->shares);
-			load /= tg_load;
-		}
+		load = min_t(long, shares,
+			     gcfs_rq->runnable_load_avg *
+			     shares / gcfs_rq->load.weight);
 	}
 
 	delta = load - se->avg.load_avg;
maintainer
#3 lore raw

Re: [PATCH v2 1/2] sched/fair: Fix how load gets propagated from cfs_rq to its sched_entity

This is on my IVB-EP, 2 sockets, 10 cores / socket, 2 threads / core.

workload is constrained to 1 socket.

root@ivb-ep:~/bench/schbench# numactl -N 0 ./schbench -m 2 -t 10 -s 10000 -c 15000 -r 30
Latency percentiles (usec)
        50.0000th: 21
        75.0000th: 30
        90.0000th: 38
        95.0000th: 42
        *99.0000th: 49
        99.5000th: 53
        99.9000th: 15024
        min=0, max=15056
root@ivb-ep:~/bench/schbench# echo NO_FUDGE > /debug/sched_features; echo NO_FUDGE2 > /debug/sched_features ; mkdir /cgroup/ponies; echo $$ > /cgroup/ponies/tasks ; numactl -N 0 ./schbench -m 2 -t 10 -s 10000 -c 15000 -r 30 ; echo $$ > /cgroup/tasks ; rmdir /cgroup/ponies
Latency percentiles (usec)
        50.0000th: 14
        75.0000th: 19
        90.0000th: 24
        95.0000th: 28
        *99.0000th: 57
        99.5000th: 15024
        99.9000th: 15024
        min=0, max=15060
root@ivb-ep:~/bench/schbench# echo NO_FUDGE > /debug/sched_features; echo FUDGE2 > /debug/sched_features ; mkdir /cgroup/ponies; echo $$ > /cgroup/ponies/tasks ; numactl -N 0 ./schbench -m 2 -t 10 -s 10000 -c 15000 -r 30 ; echo $$ > /cgroup/tasks ; rmdir /cgroup/ponies
Latency percentiles (usec)
        50.0000th: 14
        75.0000th: 19
        90.0000th: 24
        95.0000th: 26
        *99.0000th: 38
        99.5000th: 49
        99.9000th: 9648
        min=0, max=15035
root@ivb-ep:~/bench/schbench# echo FUDGE > /debug/sched_features; echo FUDGE2 > /debug/sched_features ; mkdir /cgroup/ponies; echo $$ > /cgroup/ponies/tasks ; numactl -N 0 ./schbench -m 2 -t 10 -s 10000 -c 15000 -r 30 ; echo $$ > /cgroup/tasks ; rmdir /cgroup/ponies
Latency percentiles (usec)
        50.0000th: 14
        75.0000th: 19
        90.0000th: 24
        95.0000th: 27
        *99.0000th: 3060
        99.5000th: 7848
        99.9000th: 15024
        min=0, max=15041
root@ivb-ep:~/bench/schbench# echo 0 > /sys/module/fair/parameters/prop_type
root@ivb-ep:~/bench/schbench# echo FUDGE > /debug/sched_features; echo FUDGE2 > /debug/sched_features ; mkdir /cgroup/ponies; echo $$ > /cgroup/ponies/tasks ; numactl -N 0 ./schbench -m 2 -t 10 -s 10000 -c 15000 -r 30 ; echo $$ > /cgroup/tasks ; rmdir /cgroup/ponies
Latency percentiles (usec)
        50.0000th: 14
        75.0000th: 19
        90.0000th: 24
        95.0000th: 27
        *99.0000th: 52
        99.5000th: 4712
        99.9000th: 14640
        min=0, max=15033

Just FUDGE2 on its own seems to be the best on my system and is a change that makes sense (and something Paul recently pointed out as well).

The implementation isn't particularly pretty or fast, but should illustrate the idea.

Poking at the whole update_tg_cfs_load() thing only makes it worse after that. And while I agree that that code is mind bending; it seems to work OK-ish.

Tejun, Vincent, could you guys have a poke?

The thing is that if we assume se->avg.load_avg is correct, we should already compute a correct cfs_rq->runnable_load_avg, we do all that propagation right.

But because se->avg.load_avg is stuck in the 'past' because it's sum is based on all its old weight, things don't quite work out. If we otoh treat it as a runnable_sum and scale with weight, it seems to work out fine.

Arguably sys_nice and all related crud should do the same, but nobody really uses nice at any frequency, whereas we constantly change the weight of our group entities.

---
 kernel/sched/fair.c     | 184 +++++++++++++++++++++++++++++++-----------------
 kernel/sched/features.h |   2 +
 2 files changed, 122 insertions(+), 64 deletions(-)
kernel/sched/fair.c +120 -64
index cd6c3f9..d6a33e6 100644
@@ -32,6 +32,7 @@
 #include <linux/mempolicy.h>
 #include <linux/migrate.h>
 #include <linux/task_work.h>
+#include <linux/moduleparam.h>
 
 #include <trace/events/sched.h>
 
@@ -2632,16 +2633,39 @@ account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
 # ifdef CONFIG_SMP
-static long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
+
+enum shares_type {
+	shares_runnable,
+	shares_avg,
+	shares_weight,
+};
+
+static long calc_cfs_shares(struct cfs_rq *cfs_rq, enum shares_type shares_type)
 {
-	long tg_weight, load, shares;
+	long tg_weight, tg_shares, load, shares;
+	struct task_group *tg = cfs_rq->tg;
 
-	/*
-	 * This really should be: cfs_rq->avg.load_avg, but instead we use
-	 * cfs_rq->load.weight, which is its upper bound. This helps ramp up
-	 * the shares for small weight interactive tasks.
-	 */
-	load = scale_load_down(cfs_rq->load.weight);
+	tg_shares = READ_ONCE(tg->shares);
+
+	switch (shares_type) {
+	case shares_runnable:
+		load = cfs_rq->runnable_load_avg;
+		break;
+
+	default:
+	case shares_avg:
+		load = cfs_rq->avg.load_avg;
+		break;
+
+	case shares_weight:
+		/*
+		 * This really should be: cfs_rq->avg.load_avg, but instead we
+		 * use cfs_rq->load.weight, which is its upper bound. This
+		 * helps ramp up the shares for small weight interactive tasks.
+		 */
+		load = scale_load_down(cfs_rq->load.weight);
+		break;
+	}
 
 	tg_weight = atomic_long_read(&tg->load_avg);
 
@@ -2665,23 +2689,33 @@ static long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
 	 * case no task is runnable on a CPU MIN_SHARES=2 should be returned
 	 * instead of 0.
 	 */
-	if (shares < MIN_SHARES)
-		shares = MIN_SHARES;
-	if (shares > tg->shares)
-		shares = tg->shares;
-
-	return shares;
-}
-# else /* CONFIG_SMP */
-static inline long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
-{
-	return tg->shares;
+	return clamp_t(long, shares, MIN_SHARES, tg_shares);
 }
 # endif /* CONFIG_SMP */
 
+/*
+ * Unsigned subtract and clamp on underflow.
+ *
+ * Explicitly do a load-store to ensure the intermediate value never hits
+ * memory. This allows lockless observations without ever seeing the negative
+ * values.
+ */
+#define sub_positive(_ptr, _val) do {				\
+	typeof(_ptr) ptr = (_ptr);				\
+	typeof(*ptr) val = (_val);				\
+	typeof(*ptr) res, var = READ_ONCE(*ptr);		\
+	res = var - val;					\
+	if (res > var)						\
+		res = 0;					\
+	WRITE_ONCE(*ptr, res);					\
+} while (0)
+
 static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
 			    unsigned long weight)
 {
+	if (se->load.weight == weight)
+		return;
+
 	if (se->on_rq) {
 		/* commit outstanding execution time */
 		if (cfs_rq->curr == se)
@@ -2689,10 +2723,40 @@ static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
 		account_entity_dequeue(cfs_rq, se);
 	}
 
+	if (sched_feat(FUDGE2)) {
+		unsigned long new_weight = max(scale_load_down(weight), 1UL);
+		unsigned long old_weight = max(scale_load_down(se->load.weight), 1UL);
+
+		sub_positive(&cfs_rq->avg.load_avg, se->avg.load_avg);
+		sub_positive(&cfs_rq->avg.load_sum, se->avg.load_sum);
+
+		if (se->on_rq) {
+			sub_positive(&cfs_rq->runnable_load_avg, se->avg.load_avg);
+			sub_positive(&cfs_rq->runnable_load_sum, se->avg.load_sum);
+		}
+
+		se->avg.load_avg *= new_weight;
+		se->avg.load_sum *= new_weight;
+
+		se->avg.load_avg /= old_weight;
+		se->avg.load_sum /= old_weight;
+	}
+
 	update_load_set(&se->load, weight);
 
-	if (se->on_rq)
+	if (se->on_rq) {
 		account_entity_enqueue(cfs_rq, se);
+	}
+
+	if (sched_feat(FUDGE2)) {
+		cfs_rq->avg.load_avg += se->avg.load_avg;
+		cfs_rq->avg.load_sum += se->avg.load_sum;
+
+		if (se->on_rq) {
+			cfs_rq->runnable_load_avg += se->avg.load_avg;
+			cfs_rq->runnable_load_sum += se->avg.load_sum;
+		}
+	}
 }
 
 static inline int throttled_hierarchy(struct cfs_rq *cfs_rq);
@@ -2700,7 +2764,6 @@ static inline int throttled_hierarchy(struct cfs_rq *cfs_rq);
 static void update_cfs_shares(struct sched_entity *se)
 {
 	struct cfs_rq *cfs_rq = group_cfs_rq(se);
-	struct task_group *tg;
 	long shares;
 
 	if (!cfs_rq)
@@ -2709,13 +2772,14 @@ static void update_cfs_shares(struct sched_entity *se)
 	if (throttled_hierarchy(cfs_rq))
 		return;
 
-	tg = cfs_rq->tg;
-
 #ifndef CONFIG_SMP
-	if (likely(se->load.weight == tg->shares))
+	shares = READ_ONCE(cfs_rq->tg->shares);
+
+	if (likely(se->load.weight == shares))
 		return;
+#else
+	shares = calc_cfs_shares(cfs_rq, shares_weight);
 #endif
-	shares = calc_cfs_shares(cfs_rq, tg);
 
 	reweight_entity(cfs_rq_of(se), se, shares);
 }
@@ -3070,42 +3134,51 @@ update_tg_cfs_util(struct cfs_rq *cfs_rq, struct sched_entity *se)
 	cfs_rq->avg.util_sum = cfs_rq->avg.util_avg * LOAD_AVG_MAX;
 }
 
+static int prop_type = shares_avg;
+
+module_param(prop_type, int, 0644);
+
 /* Take into account change of load of a child task group */
 static inline void
 update_tg_cfs_load(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
 	struct cfs_rq *gcfs_rq = group_cfs_rq(se);
-	long delta, load = gcfs_rq->avg.load_avg;
+	long delta, load;
 
 	/*
 	 * If the load of group cfs_rq is null, the load of the
 	 * sched_entity will also be null so we can skip the formula
 	 */
-	if (load) {
-		long tg_load;
+	if (!sched_feat(FUDGE)) {
+		load = gcfs_rq->avg.load_avg;
+		if (load) {
+			long tg_load;
 
-		/* Get tg's load and ensure tg_load > 0 */
-		tg_load = atomic_long_read(&gcfs_rq->tg->load_avg) + 1;
+			/* Get tg's load and ensure tg_load > 0 */
+			tg_load = atomic_long_read(&gcfs_rq->tg->load_avg) + 1;
 
-		/* Ensure tg_load >= load and updated with current load*/
-		tg_load -= gcfs_rq->tg_load_avg_contrib;
-		tg_load += load;
+			/* Ensure tg_load >= load and updated with current load*/
+			tg_load -= gcfs_rq->tg_load_avg_contrib;
+			tg_load += load;
 
-		/*
-		 * We need to compute a correction term in the case that the
-		 * task group is consuming more CPU than a task of equal
-		 * weight. A task with a weight equals to tg->shares will have
-		 * a load less or equal to scale_load_down(tg->shares).
-		 * Similarly, the sched_entities that represent the task group
-		 * at parent level, can't have a load higher than
-		 * scale_load_down(tg->shares). And the Sum of sched_entities'
-		 * load must be <= scale_load_down(tg->shares).
-		 */
-		if (tg_load > scale_load_down(gcfs_rq->tg->shares)) {
-			/* scale gcfs_rq's load into tg's shares*/
-			load *= scale_load_down(gcfs_rq->tg->shares);
-			load /= tg_load;
+			/*
+			 * We need to compute a correction term in the case that the
+			 * task group is consuming more CPU than a task of equal
+			 * weight. A task with a weight equals to tg->shares will have
+			 * a load less or equal to scale_load_down(tg->shares).
+			 * Similarly, the sched_entities that represent the task group
+			 * at parent level, can't have a load higher than
+			 * scale_load_down(tg->shares). And the Sum of sched_entities'
+			 * load must be <= scale_load_down(tg->shares).
+			 */
+			if (tg_load > scale_load_down(gcfs_rq->tg->shares)) {
+				/* scale gcfs_rq's load into tg's shares*/
+				load *= scale_load_down(gcfs_rq->tg->shares);
+				load /= tg_load;
+			}
 		}
+	} else {
+		load = calc_cfs_shares(gcfs_rq, prop_type);
 	}
 
 	delta = load - se->avg.load_avg;
@@ -3236,23 +3309,6 @@ static inline void cfs_rq_util_change(struct cfs_rq *cfs_rq)
 	}
 }
 
-/*
- * Unsigned subtract and clamp on underflow.
- *
- * Explicitly do a load-store to ensure the intermediate value never hits
- * memory. This allows lockless observations without ever seeing the negative
- * values.
- */
-#define sub_positive(_ptr, _val) do {				\
-	typeof(_ptr) ptr = (_ptr);				\
-	typeof(*ptr) val = (_val);				\
-	typeof(*ptr) res, var = READ_ONCE(*ptr);		\
-	res = var - val;					\
-	if (res > var)						\
-		res = 0;					\
-	WRITE_ONCE(*ptr, res);					\
-} while (0)
-
 /**
  * update_cfs_rq_load_avg - update the cfs_rq's load/util averages
  * @now: current time, as per cfs_rq_clock_task()
kernel/sched/features.h +2 -0
index dc4d148..4c517b4 100644
@@ -80,3 +80,5 @@ SCHED_FEAT(RT_RUNTIME_SHARE, true)
 SCHED_FEAT(LB_MIN, false)
 SCHED_FEAT(ATTACH_AGE_LOAD, true)
 
+SCHED_FEAT(FUDGE, true)
+SCHED_FEAT(FUDGE2, true)
author
#4 lore raw

Re: [PATCH v2 1/2] sched/fair: Fix how load gets propagated from cfs_rq to its sched_entity

Hello, Peter.

Quoted 11 lines · Peter Zijlstra

Just FUDGE2 on its own seems to be the best on my system and is a change that makes sense (and something Paul recently pointed out as well).

The implementation isn't particularly pretty or fast, but should illustrate the idea.

Poking at the whole update_tg_cfs_load() thing only makes it worse after that. And while I agree that that code is mind bending; it seems to work OK-ish.

Tejun, Vincent, could you guys have a poke?

So, just preliminary testing.

FUDGE: Does cut down the number of wrong picks by about 70% and p99
latency by about half; however, the resulting p99 is still worse by 5 - 10 times compared to !cgroup case.

FUDGE2: Changes things a lot (load values go wild) but only because
it's missing scale_load_down(). After adding scale_load_down(), it doesn't do much. For this to work, it needs to be always propagated, which btw shouldn't be prohibitively expensive given other operations which are performed at the same time.

Thanks.

Signature · 1 line
tejun
maintainer
#5 lore raw

Re: [PATCH v2 1/2] sched/fair: Fix how load gets propagated from cfs_rq to its sched_entity

Quoted 6 lines · Tejun Heo

FUDGE2: Changes things a lot (load values go wild) but only because
it's missing scale_load_down(). After adding scale_load_down(), it doesn't do much. For this to work, it needs to be always propagated, which btw shouldn't be prohibitively expensive given other operations which are performed at the same time.

Urgh, and my numbers were so pretty :/

Maybe I need to wake up, but I'm not immediately seeing where the scale_load_down() went missing for FUDGE2.

FUDGE does indeed appear to have one missing.

maintainer
#6 lore raw

Re: [PATCH v2 1/2] sched/fair: Fix how load gets propagated from cfs_rq to its sched_entity

Quoted 1 line · Peter Zijlstra

Urgh, and my numbers were so pretty :/

Just to clarify on how to run schbench, I limited to a single socket (as that is what you have) and set -t to the number of cores in the socket (not the number of threads).

Furthermore, my machine is _idle_, if I don't do anything, it doesn't do _anything_.

#7 lore raw

Re: [PATCH v2 1/2] sched/fair: Fix how load gets propagated from cfs_rq to its sched_entity

Quoted 11 lines · Peter Zijlstra
Quoted 1 line · Peter Zijlstra

Urgh, and my numbers were so pretty :/

Just to clarify on how to run schbench, I limited to a single socket (as that is what you have) and set -t to the number of cores in the socket (not the number of threads).

Furthermore, my machine is _idle_, if I don't do anything, it doesn't do _anything_.

I can't recreate this problem running 'numactl -N 0 ./schbench -m 2 -t 10 -s 10000 -c 15000 -r 30' on my E5-2690 v2 (IVB-EP, 2 sockets, 10 cores / socket, 2 threads / core)

I tried tip/sched/core comparing running in 'cpu:/' and 'cpu:/foo' and

using your patch on top with all the combinations of {NO_}FUDGE, {NO_}FUDGE2 with prop_type=shares_avg or prop_type_runnable.

Where you able to see the issue on tip/sched/core w/o your patch on your machine?

The workload of n 60% periodic tasks on n logical cpus always creates a very stable task distribution for me.

maintainer
#8 lore raw

Re: [PATCH v2 1/2] sched/fair: Fix how load gets propagated from cfs_rq to its sched_entity

Quoted 13 lines · Dietmar Eggemann
Quoted 11 lines · Peter Zijlstra
Quoted 1 line · Peter Zijlstra

Urgh, and my numbers were so pretty :/

Just to clarify on how to run schbench, I limited to a single socket (as that is what you have) and set -t to the number of cores in the socket (not the number of threads).

Furthermore, my machine is _idle_, if I don't do anything, it doesn't do _anything_.

Quoted 5 lines

I can't recreate this problem running 'numactl -N 0 ./schbench -m 2 -t 10 -s 10000 -c 15000 -r 30' on my E5-2690 v2 (IVB-EP, 2 sockets, 10 cores / socket, 2 threads / core)

I tried tip/sched/core comparing running in 'cpu:/' and 'cpu:/foo' and

I'm running tip/master (I think, possibly with the numa topology fixes in, which should be no-op on the EP).

Also, I run debian sysvinit, so nobody creating cgroups I don't know about.

Quoted 5 lines

using your patch on top with all the combinations of {NO_}FUDGE, {NO_}FUDGE2 with prop_type=shares_avg or prop_type_runnable.

Where you able to see the issue on tip/sched/core w/o your patch on your machine?

I see the 99.5th percentile shoot up when I run it in a cgroup. With FUDGE2 its all good again like not using cgroups.

But yes, last time I played with schbench (when prodding at select_idle_sibling) the thing was finicky too, I never quite got the same numbers Chris did. But in the end we found something that worked at both ends.

author
#9 lore raw

Re: [PATCH v2 1/2] sched/fair: Fix how load gets propagated from cfs_rq to its sched_entity

In reply to Dietmar Eggemann

Hello, Dietmar.

Quoted 19 lines · Dietmar Eggemann
Quoted 11 lines · Peter Zijlstra
Quoted 1 line · Peter Zijlstra

Urgh, and my numbers were so pretty :/

Just to clarify on how to run schbench, I limited to a single socket (as that is what you have) and set -t to the number of cores in the socket (not the number of threads).

Furthermore, my machine is _idle_, if I don't do anything, it doesn't do _anything_.

I can't recreate this problem running 'numactl -N 0 ./schbench -m 2 -t 10 -s 10000 -c 15000 -r 30' on my E5-2690 v2 (IVB-EP, 2 sockets, 10 cores / socket, 2 threads / core)

I tried tip/sched/core comparing running in 'cpu:/' and 'cpu:/foo' and

Quoted 8 lines

using your patch on top with all the combinations of {NO_}FUDGE, {NO_}FUDGE2 with prop_type=shares_avg or prop_type_runnable.

Where you able to see the issue on tip/sched/core w/o your patch on your machine?

The workload of n 60% periodic tasks on n logical cpus always creates a very stable task distribution for me.

It depends heavily on what else is going on in the system. On the test systems that I'm using, there's always something not-too-heavy going on. The pattern over time isn't too varied and the latency results are usually stable and the grouping of results is very clear as the difference between the load balancer working properly and not shows up as upto an order of magnitude difference in p99 latencies.

For these differences to matter, you need to push the machine so that it's right at the point of saturation - e.g. increase duty cycle till p99 starts to deteriorate w/o cgroup.

Thanks.

Signature · 1 line
tejun
#10 lore raw

Re: [PATCH v2 1/2] sched/fair: Fix how load gets propagated from cfs_rq to its sched_entity

Hi Tejun,

Quoted 5 lines · Tejun Heo

Hello, Dietmar.

Quoted 2 lines · Dietmar Eggemann
Quoted 1 line · Peter Zijlstra

On Thu, May 04, 2017 at 07:51:29AM +0200, Peter Zijlstra wrote:

[...]

Quoted 16 lines
Quoted 7 lines

I can't recreate this problem running 'numactl -N 0 ./schbench -m 2 -t 10 -s 10000 -c 15000 -r 30' on my E5-2690 v2 (IVB-EP, 2 sockets, 10 cores / socket, 2 threads / core)

I tried tip/sched/core comparing running in 'cpu:/' and 'cpu:/foo' and

Quoted 8 lines

using your patch on top with all the combinations of {NO_}FUDGE, {NO_}FUDGE2 with prop_type=shares_avg or prop_type_runnable.

Where you able to see the issue on tip/sched/core w/o your patch on your machine?

The workload of n 60% periodic tasks on n logical cpus always creates a very stable task distribution for me.

Quoted 6 lines

It depends heavily on what else is going on in the system. On the test systems that I'm using, there's always something not-too-heavy going on. The pattern over time isn't too varied and the latency results are usually stable and the grouping of results is very clear as the difference between the load balancer working properly and not shows up as upto an order of magnitude difference in p99 latencies.

OK, that make sense. You do need the light (independent from schbench) background noise to create work for the load balancer.

I switched to my Hikey board (hot-plugged out the 2. cluster, so 4 remaining cores with performance governor) because we should see the effect regardless of the topology. There is no background noise on my debian fs.

That's why I don't see any effect if I increase the C/S (cputime/sleeptime) ratio when running 'schbench -m 2 -t 2 -s S -c C -r 30'. The only source of disturbance are some additional schbench threads which sometimes force one of the worker threads to get co-scheduled with another worker thread.

https://drive.google.com/file/d/0B2f-ZAwV_YnmTDhWUk5ZRHdBRUU/view shows such a case where the additional schbench thread 'schbench-2206' (green marker line in picture) forces the worker thread 'schbench-2209' to wakeup migrate from cpu3 to cpu0 where he gets co-scheduled with the worker thread 'schbench-2210' for a while.

Quoted 6 lines

For these differences to matter, you need to push the machine so that it's right at the point of saturation - e.g. increase duty cycle till p99 starts to deteriorate w/o cgroup.

Thanks.

maintainer
#11 lore raw

Re: [PATCH v2 1/2] sched/fair: Fix how load gets propagated from cfs_rq to its sched_entity

In reply to Peter Zijlstra
Quoted 1 line · Peter Zijlstra

[snip]

Quoted 4 lines

Just FUDGE2 on its own seems to be the best on my system and is a change that makes sense (and something Paul recently pointed out as well).

Quoted 8 lines

The implementation isn't particularly pretty or fast, but should illustrate the idea.

Poking at the whole update_tg_cfs_load() thing only makes it worse after that. And while I agree that that code is mind bending; it seems to work OK-ish.

Tejun, Vincent, could you guys have a poke?

I have added below patch on to of your:

kernel/sched/fair.c +1 -1
@@ -3191,7 +3191,7 @@ update_tg_cfs_load(struct cfs_rq *cfs_rq, struct sched_entity *se)
 			}
 		}
 	} else {
-		load = calc_cfs_shares(gcfs_rq, prop_type);
+		load = scale_load_down(calc_cfs_shares(gcfs_rq, prop_type));
 	}
 
 	delta = load - se->avg.load_avg;
Signature · 116 lines
The results for each configurations are :

** Config 1**
linaro@linaro-developer:~/schbench$cat /sys/module/fair/parameters/prop_type
1
linaro@linaro-developer:~/schbench$ sudo cat /sys/kernel/debug/sched_features
GENTLE_FAIR_SLEEPERS START_DEBIT NO_NEXT_BUDDY LAST_BUDDY CACHE_HOT_BUDDY WAKEUP_PREEMPTION NO_HRTICK NO_DOUBLE_TICK LB_BIAS NONTASK_CAPACITY TTWU_QUEUE NO_SIS_AVG_CPU RT_PUSH_IPI NO_FORCE_SD_OVERLAP RT_RUNTIME_SHARE NO_LB_MIN ATTACH_AGE_LOAD NO_FUDGE NO_FUDGE2 

Latency percentiles (usec)
	50.0000th: 252
	75.0000th: 346
	90.0000th: 438
	95.0000th: 485
	*99.0000th: 537
	99.5000th: 581
	99.9000th: 5768
	min=0, max=14202

** Config 2 **
linaro@linaro-developer:~/schbench$ cat /sys/module/fair/parameters/prop_type
1
linaro@linaro-developer:~/schbench$ sudo cat /sys/kernel/debug/sched_features
GENTLE_FAIR_SLEEPERS START_DEBIT NO_NEXT_BUDDY LAST_BUDDY CACHE_HOT_BUDDY WAKEUP_PREEMPTION NO_HRTICK NO_DOUBLE_TICK LB_BIAS NONTASK_CAPACITY TTWU_QUEUE NO_SIS_AVG_CPU RT_PUSH_IPI NO_FORCE_SD_OVERLAP RT_RUNTIME_SHARE NO_LB_MIN ATTACH_AGE_LOAD FUDGE NO_FUDGE2 

Latency percentiles (usec)
	50.0000th: 261
	75.0000th: 374
	90.0000th: 457
	95.0000th: 490
	*99.0000th: 533
	99.5000th: 585
	99.9000th: 9392
	min=0, max=13295

**Config 3**
linaro@linaro-developer:~/schbench$ cat /sys/module/fair/parameters/prop_type
1
linaro@linaro-developer:~/schbench$ sudo cat /sys/kernel/debug/sched_features
GENTLE_FAIR_SLEEPERS START_DEBIT NO_NEXT_BUDDY LAST_BUDDY CACHE_HOT_BUDDY WAKEUP_PREEMPTION NO_HRTICK NO_DOUBLE_TICK LB_BIAS NONTASK_CAPACITY TTWU_QUEUE NO_SIS_AVG_CPU RT_PUSH_IPI NO_FORCE_SD_OVERLAP RT_RUNTIME_SHARE NO_LB_MIN ATTACH_AGE_LOAD NO_FUDGE FUDGE2 

Latency percentiles (usec)
	50.0000th: 233
	75.0000th: 309
	90.0000th: 456
	95.0000th: 498
	*99.0000th: 5272
	99.5000th: 8184
	99.9000th: 12368
	min=0, max=14865

I have run several time the test, few were correct but most of them were like
above

**Config 4**
linaro@linaro-developer:~/schbench$ cat /sys/module/fair/parameters/prop_type
1
linaro@linaro-developer:~/schbench$ sudo cat /sys/kernel/debug/sched_features
GENTLE_FAIR_SLEEPERS START_DEBIT NO_NEXT_BUDDY LAST_BUDDY CACHE_HOT_BUDDY WAKEUP_PREEMPTION NO_HRTICK NO_DOUBLE_TICK LB_BIAS NONTASK_CAPACITY TTWU_QUEUE NO_SIS_AVG_CPU RT_PUSH_IPI NO_FORCE_SD_OVERLAP RT_RUNTIME_SHARE NO_LB_MIN ATTACH_AGE_LOAD FUDGE FUDGE2 

Latency percentiles (usec)
	50.0000th: 211
	75.0000th: 290
	90.0000th: 380
	95.0000th: 451
	*99.0000th: 1778
	99.5000th: 5048
	99.9000th: 12752
	min=0, max=15090

I have run several time the test, few were correct but most of them were like
above

** Config 5 **
linaro@linaro-developer:~/schbench$ cat /sys/module/fair/parameters/prop_type
0
linaro@linaro-developer:~/schbench$ sudo cat /sys/kernel/debug/sched_features
GENTLE_FAIR_SLEEPERS START_DEBIT NO_NEXT_BUDDY LAST_BUDDY CACHE_HOT_BUDDY WAKEUP_PREEMPTION NO_HRTICK NO_DOUBLE_TICK LB_BIAS NONTASK_CAPACITY TTWU_QUEUE NO_SIS_AVG_CPU RT_PUSH_IPI NO_FORCE_SD_OVERLAP RT_RUNTIME_SHARE NO_LB_MIN ATTACH_AGE_LOAD FUDGE FUDGE2

Latency percentiles (usec)
	50.0000th: 216
	75.0000th: 297
	90.0000th: 430
	95.0000th: 487
	*99.0000th: 2748
	99.5000th: 7432
	99.9000th: 12912
	min=0, max=15046

I have run several time the test, few were correct but most of them were like
above

** Config 6 **
linaro@linaro-developer:~/schbench$ cat /sys/module/fair/parameters/prop_type
0
linaro@linaro-developer:~/schbench$ sudo cat /sys/kernel/debug/sched_features
GENTLE_FAIR_SLEEPERS START_DEBIT NO_NEXT_BUDDY LAST_BUDDY CACHE_HOT_BUDDY WAKEUP_PREEMPTION NO_HRTICK NO_DOUBLE_TICK LB_BIAS NONTASK_CAPACITY TTWU_QUEUE NO_SIS_AVG_CPU RT_PUSH_IPI NO_FORCE_SD_OVERLAP RT_RUNTIME_SHARE NO_LB_MIN ATTACH_AGE_LOAD FUDGE NO_FUDGE2 

Latency percentiles (usec)
	50.0000th: 245
	75.0000th: 339
	90.0000th: 444
	95.0000th: 492
	*99.0000th: 3036
	99.5000th: 9104
	99.9000th: 12496
	min=0, max=14098

I have run several time the test, few were correct but most of them were like
above



Config 1 and 2 are the two configuraton which have stable and good results

Regards,
Vincent
maintainer
#12 lore raw

Re: [PATCH 1/2] sched/fair: Fix how load gets propagated from cfs_rq to its sched_entity

In reply to Tejun Heo

Hi Tejun

Quoted 10 lines · Tejun Heo

09a43ace1f98 ("sched/fair: Propagate load during synchronous attach/detach") added immediate load propagation from cfs_rq to its sched_entity then to the parent cfs_rq; however, what gets propagated doesn't seem to make sense.

It repeats the tg_weight calculation done in calc_cfs_shares() but only uses it to compensate for shares being out of date. After that, it sets the sched_entity's load_avg to the load_avg of the corresponding cfs_rq.

Quoted 7 lines

This doesn't make sense as the cfs_rq's load_avg is some fraction of its total weight, which the sched_entity's weight has nothing to with. For example, if the cfs_rq has a single constant load 1 task the cfs_rq's load_avg would be around 1. If that cfs_rq is the only active sched_entity in the parent cfs_rq which has the maximum weight, the sched_entity's load should be around the maximum weight but update_tg_cfs_load() ends up overriding it to 1.

not sure to catch your example:
a task TA with a load_avg = 1 is the only task in a task group GB so the cfs_rq load_avg = 1 too and the group_entity of this cfs_rq has got a weight of 1024 (I use 10bits format for readability) which is the total share of task group GB

Are you saying that the group_entity load_avg should be around 1024 and not 1 ?

I would say it depends of TA weight. I assume that TA weight is the default value (1024) as you don't specify any value in your example

If TA directly runs at parent level, its sched_entity would have a load_avg of 1 so why the group entity load_avg should be 1024 ? it will just temporally show the cfs_rq more loaded than it is really and at the end the group entity load_avg will go back to 1

Quoted 82 lines

At the parent's level, the absolute value of load_avg inside a child cfs_rq doesn't mean anything. Only the ratio against its weight is meaningful.

This patch changes update_tg_cfs_load() to normalize the runnable_load_avg of the cfs_rq and then scale it to the matching sched_entity's freshly calculated shares for propagation. Use of runnable_load_avg instead of load_avg is intentional and keeps the parent's runnable_load_avg true to the sum of scaled loads of all tasks queued under it which is critical for the correction operation of load balancer. The next patch will depend on it.

Cc Vincent Guittot <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Mike Galbraith <[email protected]>
Cc Paul Turner <[email protected]>
---
 kernel/sched/fair.c |   46 +++++++++++++++++++---------------------------
 1 file changed, 19 insertions(+), 27 deletions(-)
kernel/sched/fair.c +19 -27
@@ -3078,37 +3078,29 @@ static inline void
 update_tg_cfs_load(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
        struct cfs_rq *gcfs_rq = group_cfs_rq(se);
-       long delta, load = gcfs_rq->avg.load_avg;
+       long load = 0, delta;
 
        /*
-        * If the load of group cfs_rq is null, the load of the
-        * sched_entity will also be null so we can skip the formula
+        * A cfs_rq's load avg contribution to the parent should be scaled
+        * to the sched_entity's weight.  Use freshly calculated shares
+        * instead of @se->load.weight as the latter may not reflect
+        * changes from the current scheduling operation.
+        *
+        * Note that the propagation source is runnable_load_avg instead of
+        * load_avg.  This keeps every cfs_rq's runnable_load_avg true to
+        * the sum of the scaled loads of all tasks queued under it, which
+        * is important for the correct operation of the load balancer.
+        *
+        * This can make the sched_entity's load_avg jumpier but that
+        * correctly reflects what would happen without cgroups if each
+        * task's load is scaled across nesting - the load is being
+        * averaged at the task and each cfs_rq.
         */
-       if (load) {
-               long tg_load;
+       if (gcfs_rq->load.weight) {
+               long shares = calc_cfs_shares(gcfs_rq, gcfs_rq->tg);
 
-               /* Get tg's load and ensure tg_load > 0 */
-               tg_load = atomic_long_read(&gcfs_rq->tg->load_avg) + 1;
-
-               /* Ensure tg_load >= load and updated with current load*/
-               tg_load -= gcfs_rq->tg_load_avg_contrib;
-               tg_load += load;
-
-               /*
-                * We need to compute a correction term in the case that the
-                * task group is consuming more CPU than a task of equal
-                * weight. A task with a weight equals to tg->shares will have
-                * a load less or equal to scale_load_down(tg->shares).
-                * Similarly, the sched_entities that represent the task group
-                * at parent level, can't have a load higher than
-                * scale_load_down(tg->shares). And the Sum of sched_entities'
-                * load must be <= scale_load_down(tg->shares).
-                */
-               if (tg_load > scale_load_down(gcfs_rq->tg->shares)) {
-                       /* scale gcfs_rq's load into tg's shares*/
-                       load *= scale_load_down(gcfs_rq->tg->shares);
-                       load /= tg_load;
-               }
+               load = min(gcfs_rq->runnable_load_avg *
+                          shares / gcfs_rq->load.weight, shares);
        }
 
        delta = load - se->avg.load_avg;
author
#13 lore raw

Re: [PATCH 1/2] sched/fair: Fix how load gets propagated from cfs_rq to its sched_entity

Hello,

Quoted 5 lines · Vincent Guittot

not sure to catch your example:
a task TA with a load_avg = 1 is the only task in a task group GB so the cfs_rq load_avg = 1 too and the group_entity of this cfs_rq has got a weight of 1024 (I use 10bits format for readability) which is the total share of task group GB

The group_entity (the sched_entity corresponding to the cfs_rq) should behave as if it's a task which has the weight of 1024.

Quoted 1 line

Are you saying that the group_entity load_avg should be around 1024 and not 1 ?

Yes.

Quoted 2 lines

I would say it depends of TA weight. I assume that TA weight is the default value (1024) as you don't specify any value in your example

Please consider the following configuration, where GA is a group entity, and TA and TB are tasks.

	ROOT - GA (weight 1024) - TA (weight 1)
	     \ GB (weight 1   ) - TB (weight 1)

Let's say both TA and TB are running full-tilt. Now let's take out GA and GB.

	ROOT - TA1 (weight 1024)
	     \ TB1 (weight 1   )

GA should behave the same as TA1 and GB TB1. GA's load should match TA1's, and GA's load when seen from ROOT's cfs_rq has nothing to do with how much total absolute weight it has inside it.

	ROOT - GA2 (weight 1024) - TA2 (weight 1   )
	     \ GB2 (weight 1   ) - TB2 (weight 1024)

If TA2 and TB2 are constantly running, GA2 and GB2's in ROOT's cfs_rq should match GA and GB's, respectively.

Quoted 2 lines

If TA directly runs at parent level, its sched_entity would have a load_avg of 1 so why the group entity load_avg should be 1024 ? it

Because then the hierarchical weight configuration doesn't mean anything.

Quoted 2 lines

will just temporally show the cfs_rq more loaded than it is really and at the end the group entity load_avg will go back to 1

It's not temporary. The weight of a group is its shares, which is its load fraction of the configured weight of the group. Assuming UP, if you configure a group to the weight of 1024 and have any task running full-tilt in it, the group will converge to the load of 1024. The problem is that the propagation logic is currently doing something completely different and temporarily push down the load whenever it triggers.

Thanks.

Signature · 1 line
tejun
maintainer
#14 lore raw

Re: [PATCH 1/2] sched/fair: Fix how load gets propagated from cfs_rq to its sched_entity

Quoted 35 lines · Tejun Heo

Hello,

Quoted 5 lines · Vincent Guittot

not sure to catch your example:
a task TA with a load_avg = 1 is the only task in a task group GB so the cfs_rq load_avg = 1 too and the group_entity of this cfs_rq has got a weight of 1024 (I use 10bits format for readability) which is the total share of task group GB

The group_entity (the sched_entity corresponding to the cfs_rq) should behave as if it's a task which has the weight of 1024.

Quoted 1 line

Are you saying that the group_entity load_avg should be around 1024 and not 1 ?

Yes.

Quoted 2 lines

I would say it depends of TA weight. I assume that TA weight is the default value (1024) as you don't specify any value in your example

Please consider the following configuration, where GA is a group entity, and TA and TB are tasks.

	ROOT - GA (weight 1024) - TA (weight 1)
	     \ GB (weight 1   ) - TB (weight 1)

Let's say both TA and TB are running full-tilt. Now let's take out GA and GB.

	ROOT - TA1 (weight 1024)
	     \ TB1 (weight 1   )

GA should behave the same as TA1 and GB TB1. GA's load should match TA1's, and GA's load when seen from ROOT's cfs_rq has nothing to do with how much total absolute weight it has inside it.

Quoted 5 lines
	ROOT - GA2 (weight 1024) - TA2 (weight 1   )
	     \ GB2 (weight 1   ) - TB2 (weight 1024)

If TA2 and TB2 are constantly running, GA2 and GB2's in ROOT's cfs_rq should match GA and GB's, respectively.

Yes I agree

Quoted 10 lines
Quoted 3 lines

If TA directly runs at parent level, its sched_entity would have a load_avg of 1 so why the group entity load_avg should be 1024 ? it

Because then the hierarchical weight configuration doesn't mean anything.

Quoted 2 lines

will just temporally show the cfs_rq more loaded than it is really and at the end the group entity load_avg will go back to 1

Quoted 7 lines

It's not temporary. The weight of a group is its shares, which is its load fraction of the configured weight of the group. Assuming UP, if you configure a group to the weight of 1024 and have any task running full-tilt in it, the group will converge to the load of 1024. The problem is that the propagation logic is currently doing something completely different and temporarily push down the load whenever it triggers.

Ok, I see your point and agree that there is an issue when propagating load_avg of a task group which has tasks with lower weight than the share but your proposal has got issue because it uses runnable_load_avg instead of load_avg and this makes propagation of loadavg_avg incorrect, something like below which keeps using load_avg solve the problem

+ if (gcfs_rq->load.weight) {
+ long shares = scale_load_down(calc_cfs_shares(gcfs_rq, gcfs_rq->tg));
+
+ load = min(gcfs_rq->avg.load_avg *
+ shares / scale_load_down(gcfs_rq->load.weight), shares);

I have run schbench with the change above on v4.11-rc8 and latency are ok

Thanks
Vincent

Quoted 6 lines

Thanks.

Signature · 1 line
tejun
author
#15 lore raw

Re: [PATCH 1/2] sched/fair: Fix how load gets propagated from cfs_rq to its sched_entity

Hello,

Quoted 20 lines · Vincent Guittot
Quoted 7 lines

It's not temporary. The weight of a group is its shares, which is its load fraction of the configured weight of the group. Assuming UP, if you configure a group to the weight of 1024 and have any task running full-tilt in it, the group will converge to the load of 1024. The problem is that the propagation logic is currently doing something completely different and temporarily push down the load whenever it triggers.

Ok, I see your point and agree that there is an issue when propagating load_avg of a task group which has tasks with lower weight than the share but your proposal has got issue because it uses runnable_load_avg instead of load_avg and this makes propagation of loadavg_avg incorrect, something like below which keeps using load_avg solve the problem

(quoted diff) +5 -0
+	if (gcfs_rq->load.weight) {
+		long shares = scale_load_down(calc_cfs_shares(gcfs_rq, gcfs_rq->tg));
+
+		load = min(gcfs_rq->avg.load_avg *
+			   shares / scale_load_down(gcfs_rq->load.weight), shares);
Quoted 1 line

I have run schbench with the change above on v4.11-rc8 and latency are ok

Hmm... so, I'll test this but this wouldn't solve the problem of root's runnable_load_avg being out of sync with the approximate sum of all task loads, which is the cause of the latencies that I'm seeing.

Are you saying that with the above change, you're not seeing the higher latency issue that you reported in the other reply?

Thanks.

Signature · 1 line
tejun
maintainer
#16 lore raw

Re: [PATCH 1/2] sched/fair: Fix how load gets propagated from cfs_rq to its sched_entity

Quoted 23 lines · Tejun Heo

Hello,

Quoted 20 lines · Vincent Guittot
Quoted 7 lines

It's not temporary. The weight of a group is its shares, which is its load fraction of the configured weight of the group. Assuming UP, if you configure a group to the weight of 1024 and have any task running full-tilt in it, the group will converge to the load of 1024. The problem is that the propagation logic is currently doing something completely different and temporarily push down the load whenever it triggers.

Ok, I see your point and agree that there is an issue when propagating load_avg of a task group which has tasks with lower weight than the share but your proposal has got issue because it uses runnable_load_avg instead of load_avg and this makes propagation of loadavg_avg incorrect, something like below which keeps using load_avg solve the problem

(quoted diff) +5 -0
+     if (gcfs_rq->load.weight) {
+             long shares = scale_load_down(calc_cfs_shares(gcfs_rq, gcfs_rq->tg));
+
+             load = min(gcfs_rq->avg.load_avg *
+                        shares / scale_load_down(gcfs_rq->load.weight), shares);
Quoted 8 lines
Quoted 1 line

I have run schbench with the change above on v4.11-rc8 and latency are ok

Hmm... so, I'll test this but this wouldn't solve the problem of root's runnable_load_avg being out of sync with the approximate sum of all task loads, which is the cause of the latencies that I'm seeing.

Are you saying that with the above change, you're not seeing the higher latency issue that you reported in the other reply?

yes I don't have any latency regression like v4.11-rc8 with the above change that uses load_avg but fix the propagation for of a task with a lower weight than task group share.

Quoted 5 lines

Thanks.

--
tejun

maintainer
#17 lore raw

Re: [PATCH 1/2] sched/fair: Fix how load gets propagated from cfs_rq to its sched_entity

In reply to Vincent Guittot

Hi,

sorry for being late to the party, trying to catch-up..

Review

Quoted 12 lines · Vincent Guittot

Ok, I see your point and agree that there is an issue when propagating load_avg of a task group which has tasks with lower weight than the share but your proposal has got issue because it uses runnable_load_avg instead of load_avg and this makes propagation of loadavg_avg incorrect, something like below which keeps using load_avg solve the problem

(quoted diff) +5 -0
+	if (gcfs_rq->load.weight) {
+		long shares = scale_load_down(calc_cfs_shares(gcfs_rq, gcfs_rq->tg));
+
+		load = min(gcfs_rq->avg.load_avg *
+			   shares / scale_load_down(gcfs_rq->load.weight), shares);

So this here does:

( tg->load_avg = \Sum cfs_rq->load_avg )

load = cfs_rq->load.weight

tg_weight = tg->load_avg - cfs_rq->contrib + load

           tg->shares * load
  shares = -----------------
               tg_weight


                        cfs_rq->load_avg
  avg_shares = shares * ----------------
                              load

	       tg->shares * cfs_rq->load_avg
             = -----------------------------
                      tg_weight

( se->load.weight = shares )

  se->load_avg = min(shares, avg_shares);

So where shares (and se->load.weight) are an upper bound (due to using cfs_rq->load.weight, see calc_cfs_shares), avg_shares is supposedly a more accurate representation based on our PELT averages.

This looks OK; and I agree with Vincent that we should use cfs_rq->avg.load_avg, not cfs_rq->runnable_load_avg, since tg->load_avg is a sum of the former, not the latter.

Also, arguably calculating the above avg_shares directly (using the second equation) might be more precise; but I doubt it makes much of a difference, however since we do min(), we should at least clamp against MIN_SHARES again.

Furthermore, it appears to me we want a different tg_weight value for the avg_shares, something like:

tg_weight = tg->load_avg - cfs_rq->contrib + cfs_rq->avg.load_avg

To better match with the numerator's units, otherwise it will have a tendency to push avg_shares down further than it needs to be.

(All assuming it actually works of course.. compile tested only)

kernel/sched/fair.c +61 -32
@@ -2634,7 +2634,9 @@ account_entity_dequeue(struct cfs_rq *cf
 # ifdef CONFIG_SMP
 static long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
 {
-	long tg_weight, load, shares;
+	long tg_weight, tg_shares, load, shares;
+
+	tg_shares = READ_ONCE(tg->shares);
 
 	/*
 	 * This really should be: cfs_rq->avg.load_avg, but instead we use
@@ -2665,12 +2667,7 @@ static long calc_cfs_shares(struct cfs_r
 	 * case no task is runnable on a CPU MIN_SHARES=2 should be returned
 	 * instead of 0.
 	 */
-	if (shares < MIN_SHARES)
-		shares = MIN_SHARES;
-	if (shares > tg->shares)
-		shares = tg->shares;
-
-	return shares;
+	return clamp_t(long, shares, MIN_SHARES, tg_shares);
 }
 # else /* CONFIG_SMP */
 static inline long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
@@ -3075,37 +3072,69 @@ static inline void
 update_tg_cfs_load(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
 	struct cfs_rq *gcfs_rq = group_cfs_rq(se);
-	long delta, load = gcfs_rq->avg.load_avg;
+	long load = 0, delta;
 
 	/*
-	 * If the load of group cfs_rq is null, the load of the
-	 * sched_entity will also be null so we can skip the formula
+	 * If there is load in our group cfs_rq (@gcfs_rq), then update its
+	 * corresponding group se (@se) load value to reflect any change in
+	 * weights.
+	 *
+	 * Also see effective_load(), where we do something similar.
+	 *
+	 *   ( tg->load_avg = \Sum cfs_rq->load_avg )
+	 *   
+	 *   tg_weight = tg->load_avg - cfs_rq->contrib
+	 *   
+	 *   
+	 *            tg->shares * cfs_rq->weight
+	 *   shares = ---------------------------
+	 *            tg_weight  + cfs_rq->weight
+	 *   
+	 *   
+	 *		  tg->shares * cfs_rq->load_avg
+	 *   avg_shares = -----------------------------
+	 *                tg_weight  + cfs_rq->load_avg
+	 *   
+	 *   
+	 *   ( se->load.weight = shares )
+	 *   
+	 *   se->load_avg = min(shares, avg_shares);
+	 *
+	 * Where @shares is an upper bound to @avg_shares, see the comments
+	 * in calc_cfs_shares().
 	 */
-	if (load) {
-		long tg_load;
-
-		/* Get tg's load and ensure tg_load > 0 */
-		tg_load = atomic_long_read(&gcfs_rq->tg->load_avg) + 1;
-
-		/* Ensure tg_load >= load and updated with current load*/
-		tg_load -= gcfs_rq->tg_load_avg_contrib;
-		tg_load += load;
+	if (gcfs_rq->load.weight) {
+		long tg_weight1, tg_weight2, tg_shares, shares, avg_shares;
+		struct task_group *tg = gcfs_rq->tg;
 
 		/*
-		 * We need to compute a correction term in the case that the
-		 * task group is consuming more CPU than a task of equal
-		 * weight. A task with a weight equals to tg->shares will have
-		 * a load less or equal to scale_load_down(tg->shares).
-		 * Similarly, the sched_entities that represent the task group
-		 * at parent level, can't have a load higher than
-		 * scale_load_down(tg->shares). And the Sum of sched_entities'
-		 * load must be <= scale_load_down(tg->shares).
+		 * This open-codes calc_cfs_shares(), in order to ensure
+		 * we use consistent values for @shares and @avg_shares,
+		 * as well as make sure we clip the result properly.
 		 */
-		if (tg_load > scale_load_down(gcfs_rq->tg->shares)) {
-			/* scale gcfs_rq's load into tg's shares*/
-			load *= scale_load_down(gcfs_rq->tg->shares);
-			load /= tg_load;
-		}
+
+		tg_shares = READ_ONCE(tg->shares);
+
+		load = scale_load_down(gcfs_rq->load.weight);
+
+		tg_weight1 = atomic_long_read(&tg->load_avg);
+		tg_weight2 = (tg_weight1 -= cfs_rq->tg_load_avg_contrib);
+		tg_weight1 += load;
+
+		shares = tg_shares * load;
+		if (tg_weight1)
+			shares /= tg_weight1;
+
+
+		load = READ_ONCE(gcfs_rq->avg.load_avg);
+
+		tg_weight2 += load;
+
+		avg_shares = tg_shares * load;
+		if (tg_weight2)
+			avg_shares /= tg_weight2;
+
+		load = clamp_t(long, min(shares, avg_shares), MIN_SHARES, tg_shares);
 	}
 
 	delta = load - se->avg.load_avg;
maintainer
#18 lore raw

Re: [PATCH 1/2] sched/fair: Fix how load gets propagated from cfs_rq to its sched_entity

Quoted 23 lines · Peter Zijlstra

So this here does:

( tg->load_avg = \Sum cfs_rq->load_avg )

load = cfs_rq->load.weight

tg_weight = tg->load_avg - cfs_rq->contrib + load

           tg->shares * load
  shares = -----------------
               tg_weight


                        cfs_rq->load_avg
  avg_shares = shares * ----------------
                              load

	       tg->shares * cfs_rq->load_avg
             = -----------------------------
                      tg_weight
Quoted 3 lines

( se->load.weight = shares )

  se->load_avg = min(shares, avg_shares);

I wonder though; do we really need the min() ? Can't we simply use avg_shares all the time?

author
#19 lore raw

Re: [PATCH 1/2] sched/fair: Fix how load gets propagated from cfs_rq to its sched_entity

In reply to Peter Zijlstra

Hello, Peter.

Quoted 28 lines · Peter Zijlstra

So this here does:

( tg->load_avg = \Sum cfs_rq->load_avg )

load = cfs_rq->load.weight

tg_weight = tg->load_avg - cfs_rq->contrib + load

           tg->shares * load
  shares = -----------------
               tg_weight


                        cfs_rq->load_avg
  avg_shares = shares * ----------------
                              load

	       tg->shares * cfs_rq->load_avg
             = -----------------------------
                      tg_weight

( se->load.weight = shares )

  se->load_avg = min(shares, avg_shares);
Quoted 7 lines

So where shares (and se->load.weight) are an upper bound (due to using cfs_rq->load.weight, see calc_cfs_shares), avg_shares is supposedly a more accurate representation based on our PELT averages.

This looks OK; and I agree with Vincent that we should use cfs_rq->avg.load_avg, not cfs_rq->runnable_load_avg, since tg->load_avg is a sum of the former, not the latter.

With this, we end up using a different metric for picking the busiest queue depending on whether there are nested cfs_rq's or not. The root's runnable_load_avg ends up including blocked load avgs queued behind nested cfs_rq's because we lose the resolution across threads across nesting.

Quoted 8 lines

Also, arguably calculating the above avg_shares directly (using the second equation) might be more precise; but I doubt it makes much of a difference, however since we do min(), we should at least clamp against MIN_SHARES again.

Furthermore, it appears to me we want a different tg_weight value for the avg_shares, something like:

Quoted 7 lines

tg_weight = tg->load_avg - cfs_rq->contrib + cfs_rq->avg.load_avg

To better match with the numerator's units, otherwise it will have a tendency to push avg_shares down further than it needs to be.

(All assuming it actually works of course.. compile tested only)

So, if changing gcfs_rq se->load_avg.avg to match the gcfs_rq's runnable_load_avg is icky, and I can see why that would be, we can simply introduce a separate channel of propagation so that runnable_load_avg gets propagated independently from se->load_avg propagation, so that for all every cfs_rq, its runnable_load_avg is the sum of all active load_avgs queued on itself and its descendents, which is the number we want for load balancing anyway. I'll try to spin a patch which does that.

I still wonder what gcfs_rq se->load_avg.avg is good for tho? It's nice to keep the value in line but is it actually used anywhere? The parent cfs_rq's values are independently calculated and, AFAICS, the only time the value is used is to propagate into the parent's runnable_load_sum, which has to use a different value, as explained above.

Thanks.

Signature · 1 line
tejun
maintainer
#20 lore raw

Re: [PATCH 1/2] sched/fair: Fix how load gets propagated from cfs_rq to its sched_entity

Quoted 2 lines · Tejun Heo

I still wonder what gcfs_rq se->load_avg.avg is good for tho? It's nice to keep the value in line but is it actually used anywhere?

Its used to manage its parent's cfs_rq sums boundary conditions. When we enqueue the group se to the parent group, we do:

enqueue_entity()

    enqueue_entity_load_avg()
      // update runnable
      // add se.avg to cfs_rq.avg if 'migrated'

Now obviously group se's never actually migrate between CPUs, but they still pass through that code. I think the 'migrate' condition also triggers for new entities for example, they 'migrate' into the system.

Similar for dequeue, that should trigger when groups entities get destroyed, they 'migrate' out of the system.

But I get what you're saying. They're not overly useful as such.

Quoted 3 lines

So, if changing gcfs_rq se->load_avg.avg to match the gcfs_rq's runnable_load_avg is icky, and I can see why that would be, we can simply introduce a separate channel of propagation ...

Can you have a play with something like the below? I suspect 'shares_runnable' might work for you here.

Its still 'icky', but not more so than calc_cfs_shares() was to begin with. When many CPUs are involved the global sum (tg_shares) is still dominated by avg_load and the division will have a downward bias, but given the purpose that might not be too bad.

---
 kernel/sched/fair.c | 62 +++++++++++++++++++++++++++++++++++++----------------
 1 file changed, 44 insertions(+), 18 deletions(-)
kernel/sched/fair.c +44 -18
index a903276fcb62..7d1fb5f421bc 100644
@@ -2630,26 +2630,56 @@ static inline void account_numa_dequeue(struct rq *rq, struct task_struct *p)
 	cfs_rq->nr_running--;
 }
 
+enum shares_type {
+	shares_runnable,
+	shares_avg,
+	shares_weight,
+};
+
 #ifdef CONFIG_FAIR_GROUP_SCHED
 # ifdef CONFIG_SMP
-static long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
+static long
+calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg, enum shares_type)
 {
-	long tg_weight, load, shares;
+	long tg_weight, tg_shares, load, shares;
 
-	/*
-	 * This really should be: cfs_rq->avg.load_avg, but instead we use
-	 * cfs_rq->load.weight, which is its upper bound. This helps ramp up
-	 * the shares for small weight interactive tasks.
-	 */
-	load = scale_load_down(cfs_rq->load.weight);
+	tg_shares = READ_ONCE(tg->shares);
+
+	switch (shares_type) {
+	case shares_runnable:
+		/*
+		 * Instead of the correct cfs_rq->avg.load_avg we use
+		 * cfs_rq->runnable_load_avg, which does not include the
+		 * blocked load.
+		 */
+		load = cfs_rq->runnable_load_avg;
+		break;
+
+	case shares_avg:
+		load = cfs_rq->avg.load_avg;
+		break;
+
+	case shares_weight:
+		/*
+		 * Instead of the correct cfs_rq->avg.load_avg we use
+		 * cfs_rq->load.weight, which is its upper bound. This helps
+		 * ramp up the shares for small weight interactive tasks.
+		 */
+		load = scale_load_down(cfs_rq->load.weight);
+		break;
+	}
 
 	tg_weight = atomic_long_read(&tg->load_avg);
 
-	/* Ensure tg_weight >= load */
+	/*
+	 * This ensures the sum is up-to-date for this CPU, in case of the other
+	 * two approximations it biases the sum towards their value and in case
+	 * of (near) UP ensures the division ends up <= 1.
+	 */
 	tg_weight -= cfs_rq->tg_load_avg_contrib;
 	tg_weight += load;
 
-	shares = (tg->shares * load);
+	shares = (tg_shares * load);
 	if (tg_weight)
 		shares /= tg_weight;
 
@@ -2665,15 +2695,11 @@ static long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
 	 * case no task is runnable on a CPU MIN_SHARES=2 should be returned
 	 * instead of 0.
 	 */
-	if (shares < MIN_SHARES)
-		shares = MIN_SHARES;
-	if (shares > tg->shares)
-		shares = tg->shares;
-
-	return shares;
+	return clamp_t(long, shares, MIN_SHARES, tg_shares);
 }
 # else /* CONFIG_SMP */
-static inline long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
+static inline long
+calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg, enum shares_type)
 {
 	return tg->shares;
 }
@@ -2715,7 +2741,7 @@ static void update_cfs_shares(struct sched_entity *se)
 	if (likely(se->load.weight == tg->shares))
 		return;
 #endif
-	shares = calc_cfs_shares(cfs_rq, tg);
+	shares = calc_cfs_shares(cfs_rq, tg, shares_weight);
 
 	reweight_entity(cfs_rq_of(se), se, shares);
 }
maintainer
#21 lore raw

Re: [PATCH 1/2] sched/fair: Fix how load gets propagated from cfs_rq to its sched_entity

Quoted 6 lines · Peter Zijlstra

Can you have a play with something like the below? I suspect 'shares_runnable' might work for you here.

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

So something like so on top I suppose...

kernel/sched/fair.c +1 -32
@@ -3101,38 +3101,7 @@ static inline void
 update_tg_cfs_load(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
 	struct cfs_rq *gcfs_rq = group_cfs_rq(se);
-	long delta, load = gcfs_rq->avg.load_avg;
-
-	/*
-	 * If the load of group cfs_rq is null, the load of the
-	 * sched_entity will also be null so we can skip the formula
-	 */
-	if (load) {
-		long tg_load;
-
-		/* Get tg's load and ensure tg_load > 0 */
-		tg_load = atomic_long_read(&gcfs_rq->tg->load_avg) + 1;
-
-		/* Ensure tg_load >= load and updated with current load*/
-		tg_load -= gcfs_rq->tg_load_avg_contrib;
-		tg_load += load;
-
-		/*
-		 * We need to compute a correction term in the case that the
-		 * task group is consuming more CPU than a task of equal
-		 * weight. A task with a weight equals to tg->shares will have
-		 * a load less or equal to scale_load_down(tg->shares).
-		 * Similarly, the sched_entities that represent the task group
-		 * at parent level, can't have a load higher than
-		 * scale_load_down(tg->shares). And the Sum of sched_entities'
-		 * load must be <= scale_load_down(tg->shares).
-		 */
-		if (tg_load > scale_load_down(gcfs_rq->tg->shares)) {
-			/* scale gcfs_rq's load into tg's shares*/
-			load *= scale_load_down(gcfs_rq->tg->shares);
-			load /= tg_load;
-		}
-	}
+	long delta, load = calc_cfs_shares(gcfs_rq, gcfs_rq->tg, shares_runnable);
 
 	delta = load - se->avg.load_avg;
 
author
#22 lore raw

Re: [PATCH 1/2] sched/fair: Fix how load gets propagated from cfs_rq to its sched_entity

Hello, Peter.

Your changes need the following fix patch. With the fix and "sched/fair: Always propagate runnable_load_avg" applied, it seems to work fine. The propagated number is a bit different but I don't see noticeable difference in behavior and the new number seems to better represent what we need.

Thanks.

---
 kernel/sched/fair.c |    7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)
kernel/sched/fair.c +4 -3
@@ -2645,7 +2645,8 @@ enum shares_type {
 #ifdef CONFIG_FAIR_GROUP_SCHED
 # ifdef CONFIG_SMP
 static long
-calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg, enum shares_type)
+calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg,
+		enum shares_type shares_type)
 {
 	long tg_weight, tg_shares, load, shares;
 
@@ -2705,7 +2706,7 @@ calc_cfs_shares(struct cfs_rq *cfs_rq, s
 }
 # else /* CONFIG_SMP */
 static inline long
-calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg, enum shares_type)
+calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg, enum shares_type shares_type)
 {
 	return tg->shares;
 }
@@ -3104,7 +3105,7 @@ static inline void
 update_tg_cfs_load(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
 	struct cfs_rq *gcfs_rq = group_cfs_rq(se);
-	long delta, load = calc_cfs_shares(gcfs_rq, gcfs_rq->tg, shares_runnable);
+	long delta, load = scale_load_down(calc_cfs_shares(gcfs_rq, gcfs_rq->tg, shares_runnable));
 
 	delta = load - se->avg.load_avg;
 
maintainer
#23 lore raw

Re: [PATCH 1/2] sched/fair: Fix how load gets propagated from cfs_rq to its sched_entity

Quoted 3 lines · Tejun Heo

Hello, Peter.

Your changes need the following fix patch.

D'0h, so much for not running my patches through a compiler ;-)

Quoted 5 lines

With the fix and
"sched/fair: Always propagate runnable_load_avg" applied, it seems to work fine. The propagated number is a bit different but I don't see noticeable difference in behavior and the new number seems to better represent what we need.

Right. Let me stare at that always propagate thing a bit. My instant worry is overhead, but yeah, we need something to make this work.

maintainer
#24 lore raw

Re: [PATCH 1/2] sched/fair: Fix how load gets propagated from cfs_rq to its sched_entity

In reply to Tejun Heo
Quoted 86 lines · Tejun Heo

09a43ace1f98 ("sched/fair: Propagate load during synchronous attach/detach") added immediate load propagation from cfs_rq to its sched_entity then to the parent cfs_rq; however, what gets propagated doesn't seem to make sense.

It repeats the tg_weight calculation done in calc_cfs_shares() but only uses it to compensate for shares being out of date. After that, it sets the sched_entity's load_avg to the load_avg of the corresponding cfs_rq.

This doesn't make sense as the cfs_rq's load_avg is some fraction of its total weight, which the sched_entity's weight has nothing to with. For example, if the cfs_rq has a single constant load 1 task the cfs_rq's load_avg would be around 1. If that cfs_rq is the only active sched_entity in the parent cfs_rq which has the maximum weight, the sched_entity's load should be around the maximum weight but update_tg_cfs_load() ends up overriding it to 1.

At the parent's level, the absolute value of load_avg inside a child cfs_rq doesn't mean anything. Only the ratio against its weight is meaningful.

This patch changes update_tg_cfs_load() to normalize the runnable_load_avg of the cfs_rq and then scale it to the matching sched_entity's freshly calculated shares for propagation. Use of runnable_load_avg instead of load_avg is intentional and keeps the parent's runnable_load_avg true to the sum of scaled loads of all tasks queued under it which is critical for the correction operation of load balancer. The next patch will depend on it.

Cc Vincent Guittot <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Mike Galbraith <[email protected]>
Cc Paul Turner <[email protected]>
---
 kernel/sched/fair.c |   46 +++++++++++++++++++---------------------------
 1 file changed, 19 insertions(+), 27 deletions(-)
kernel/sched/fair.c +17 -19
@@ -3078,37 +3078,29 @@ static inline void
 update_tg_cfs_load(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
        struct cfs_rq *gcfs_rq = group_cfs_rq(se);
-       long delta, load = gcfs_rq->avg.load_avg;
+       long load = 0, delta;
 
        /*
-        * If the load of group cfs_rq is null, the load of the
-        * sched_entity will also be null so we can skip the formula
+        * A cfs_rq's load avg contribution to the parent should be scaled
+        * to the sched_entity's weight.  Use freshly calculated shares
+        * instead of @se->load.weight as the latter may not reflect
+        * changes from the current scheduling operation.
+        *
+        * Note that the propagation source is runnable_load_avg instead of
+        * load_avg.  This keeps every cfs_rq's runnable_load_avg true to
+        * the sum of the scaled loads of all tasks queued under it, which
+        * is important for the correct operation of the load balancer.
+        *
+        * This can make the sched_entity's load_avg jumpier but that
+        * correctly reflects what would happen without cgroups if each
+        * task's load is scaled across nesting - the load is being
+        * averaged at the task and each cfs_rq.
         */
-       if (load) {
-               long tg_load;
+       if (gcfs_rq->load.weight) {
+               long shares = calc_cfs_shares(gcfs_rq, gcfs_rq->tg);
 
-               /* Get tg's load and ensure tg_load > 0 */
-               tg_load = atomic_long_read(&gcfs_rq->tg->load_avg) + 1;
-
-               /* Ensure tg_load >= load and updated with current load*/
-               tg_load -= gcfs_rq->tg_load_avg_contrib;
-               tg_load += load;
-
-               /*
-                * We need to compute a correction term in the case that the
-                * task group is consuming more CPU than a task of equal
-                * weight. A task with a weight equals to tg->shares will have
-                * a load less or equal to scale_load_down(tg->shares).
-                * Similarly, the sched_entities that represent the task group
-                * at parent level, can't have a load higher than

kernel/sched/fair.c static inline void · line 3103

Quoted 10 lines
kernel/sched/fair.c +2 -8
-                * scale_load_down(tg->shares). And the Sum of sched_entities'
-                * load must be <= scale_load_down(tg->shares).
-                */
-               if (tg_load > scale_load_down(gcfs_rq->tg->shares)) {
-                       /* scale gcfs_rq's load into tg's shares*/
-                       load *= scale_load_down(gcfs_rq->tg->shares);
-                       load /= tg_load;
-               }
+               load = min(gcfs_rq->runnable_load_avg *
+                          shares / gcfs_rq->load.weight, shares);

There is a unit problem above:
runnable_load_avg and shares are not in the same range but runnable_load_avg and scale_load_down(gcfs_rq->load.weight) are so you should use
gcfs_rq->runnable_load_avg * scale_load_down(shares) / scale_load_down(gcfs_rq->load.weight).
Hopefully both scale_load_down cancel between them
But the min should be then tested with scale_load_down(shares) and not only shares

Quoted 3 lines
kernel/sched/fair.c +0 -0
        }
 
        delta = load - se->avg.load_avg;
author
#25 lore raw

Re: [PATCH 1/2] sched/fair: Fix how load gets propagated from cfs_rq to its sched_entity

Hello, Vincent.

Quoted 6 lines · Vincent Guittot

kernel/sched/fair.c static inline void · line 3103

Quoted 5 lines
kernel/sched/fair.c +4 -0
+       if (gcfs_rq->load.weight) {
+               long shares = calc_cfs_shares(gcfs_rq, gcfs_rq->tg);
 
+               load = min(gcfs_rq->runnable_load_avg *
+                          shares / gcfs_rq->load.weight, shares);
Quoted 6 lines

There is a unit problem above:
runnable_load_avg and shares are not in the same range but runnable_load_avg and scale_load_down(gcfs_rq->load.weight) are so you should use
gcfs_rq->runnable_load_avg * scale_load_down(shares) / scale_load_down(gcfs_rq->load.weight).

But the only difference there is that we lose accuracy in calculation; otherwise, the end results are the same, no?

Quoted 3 lines

Hopefully both scale_load_down cancel between them
But the min should be then tested with scale_load_down(shares) and not only shares

Ah, that's right. The min should be against scaled down shares.

Thanks.

Signature · 1 line
tejun
maintainer
#26 lore raw

Re: [PATCH 1/2] sched/fair: Fix how load gets propagated from cfs_rq to its sched_entity

Quoted 16 lines · Tejun Heo

Hello, Vincent.

Quoted 6 lines · Vincent Guittot

kernel/sched/fair.c static inline void · line 3103

Quoted 5 lines
kernel/sched/fair.c +4 -0
+       if (gcfs_rq->load.weight) {
+               long shares = calc_cfs_shares(gcfs_rq, gcfs_rq->tg);
 
+               load = min(gcfs_rq->runnable_load_avg *
+                          shares / gcfs_rq->load.weight, shares);
Quoted 6 lines

There is a unit problem above:
runnable_load_avg and shares are not in the same range but runnable_load_avg and scale_load_down(gcfs_rq->load.weight) are so you should use
gcfs_rq->runnable_load_avg * scale_load_down(shares) / scale_load_down(gcfs_rq->load.weight).

Quoted 2 lines

But the only difference there is that we lose accuracy in calculation; otherwise, the end results are the same, no?

Yes the end result is the same, it was mainly to point out the range difference and explain why we need scale_load_down(shares) for the 2nd argument of min.
This should also explain the warning issue you mentioned earlier

Quoted 11 lines
Quoted 4 lines

Hopefully both scale_load_down cancel between them
But the min should be then tested with scale_load_down(shares) and not only shares

Ah, that's right. The min should be against scaled down shares.

Thanks.

--
tejun

author
#27 lore raw

Re: [PATCH 1/2] sched/fair: Fix how load gets propagated from cfs_rq to its sched_entity

Hello, Vincent.

Quoted 7 lines · Vincent Guittot
Quoted 2 lines

But the only difference there is that we lose accuracy in calculation; otherwise, the end results are the same, no?

Yes the end result is the same, it was mainly to point out the range difference and explain why we need scale_load_down(shares) for the 2nd argument of min.
This should also explain the warning issue you mentioned earlier

I'm not sure this makes sense. Practically, we're doing more shifts just to lose calculation accuracy. Even conceptually, what we're doing is

             C
	A * ---
             B

Where A is in a different scale while B and C are in the same. What you're suggesting is

             scale_down(C)
	A * ---------------
	     scale_down(B)

I can't see why this is better in any way.

Thanks.

Signature · 1 line
tejun
maintainer
#28 lore raw

Re: [PATCH 1/2] sched/fair: Fix how load gets propagated from cfs_rq to its sched_entity

Quoted 19 lines · Tejun Heo

Hello, Vincent.

Quoted 7 lines · Vincent Guittot
Quoted 2 lines

But the only difference there is that we lose accuracy in calculation; otherwise, the end results are the same, no?

Yes the end result is the same, it was mainly to point out the range difference and explain why we need scale_load_down(shares) for the 2nd argument of min.
This should also explain the warning issue you mentioned earlier

I'm not sure this makes sense. Practically, we're doing more shifts just to lose calculation accuracy. Even conceptually, what we're doing is

             C
        A * ---
             B
Quoted 8 lines

Where A is in a different scale while B and C are in the same. What you're suggesting is

             scale_down(C)
        A * ---------------
             scale_down(B)

I can't see why this is better in any way.

i'm not saying it's netter, i'm saying that it might be the cause of the build warning you mentioned because you are mixing u64 and unsigned long

Quoted 5 lines

Thanks.

--
tejun

author
#29 lore raw

PATCH 2/2 sched/fair: Always propagate runnable_load_avg

In reply to Tejun Heo

We noticed that with cgroup CPU controller in use, the scheduling latency gets wonky regardless of nesting level or weight configuration. This is easily reproducible with Chris Mason's schbench[1].

All tests are run on a single socket, 16 cores, 32 threads machine. While the machine is mostly idle, it isn't completey. There's always some variable management load going on. The command used is

schbench -m 2 -t 16 -s 10000 -c 15000 -r 30

which measures scheduling latency with 32 threads each of which repeatedly runs for 15ms and then sleeps for 10ms. Here's a representative result when running from the root cgroup.

# ~/schbench -m 2 -t 16 -s 10000 -c 15000 -r 30
Latency percentiles (usec)

	 50.0000th: 26
	 75.0000th: 62
	 90.0000th: 74
	 95.0000th: 86
	 *99.0000th: 887
	 99.5000th: 3692
	 99.9000th: 10832
	 min=0, max=13374

The following is inside a first level CPU cgroup with the maximum weight.

# ~/schbench -m 2 -t 16 -s 10000 -c 15000 -r 30
Latency percentiles (usec)

	 50.0000th: 31
	 75.0000th: 65
	 90.0000th: 71
	 95.0000th: 91
	 *99.0000th: 7288
	 99.5000th: 10352
	 99.9000th: 12496
	 min=0, max=13023

Note the drastic increase in p99 scheduling latency. After investigation, it turned out that the update_sd_lb_stats(), which is used by load_balance() to pick the most loaded group, was often picking the wrong group. A CPU which has one schbench running and another queued wouldn't report the correspondingly higher weighted_cpuload() and get looked over as the target of load balancing.

weighted_cpuload() is the root cfs_rq's runnable_load_avg which is the sum of the load_avg of all queued sched_entities. Without cgroups or at the root cgroup, each task's load_avg contributes directly to the sum. When a task wakes up or goes to sleep, the change is immediately reflected on runnable_load_avg which in turn affects load balancing.

However, when CPU cgroup is in use, a nesting cfs_rq blocks this immediate reflection. When a task wakes up inside a cgroup, the nested cfs_rq's runnable_load_avg is updated but doesn't get propagated to the parent. It only affects the matching sched_entity's load_avg over time which then gets propagated to the runnable_load_avg at that level. This makes weighted_cpuload() often temporarily out of sync leading to suboptimal behavior of load_balance() and increase in scheduling latencies as shown above.

This patch fixes the issue by updating propagate_entity_load_avg() to always propagate to the parent's runnable_load_avg. Combined with the previous patch, this keeps a cfs_rq's runnable_load_avg always the sum of the scaled loads of all tasks queued below removing the artifacts from nesting cfs_rqs. The following is from inside three levels of nesting with the patch applied.

# ~/schbench -m 2 -t 16 -s 10000 -c 15000 -r 30
Latency percentiles (usec)

	 50.0000th: 40
	 75.0000th: 71
	 90.0000th: 89
	 95.0000th: 108
	 *99.0000th: 679
	 99.5000th: 3500
	 99.9000th: 10960
	 min=0, max=13790

[1] git://git.kernel.org/pub/scm/linux/kernel/git/mason/schbench.git

Cc Vincent Guittot <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Mike Galbraith <[email protected]>
Cc Paul Turner <[email protected]>
Cc Chris Mason <[email protected]>
---
 kernel/sched/fair.c |   34 +++++++++++++++++++++-------------
 1 file changed, 21 insertions(+), 13 deletions(-)
kernel/sched/fair.c +21 -13
@@ -3075,7 +3075,8 @@ update_tg_cfs_util(struct cfs_rq *cfs_rq
 
 /* Take into account change of load of a child task group */
 static inline void
-update_tg_cfs_load(struct cfs_rq *cfs_rq, struct sched_entity *se)
+update_tg_cfs_load(struct cfs_rq *cfs_rq, struct sched_entity *se,
+		   bool propagate_avg)
 {
 	struct cfs_rq *gcfs_rq = group_cfs_rq(se);
 	long load = 0, delta;
@@ -3113,9 +3114,11 @@ update_tg_cfs_load(struct cfs_rq *cfs_rq
 	se->avg.load_avg = load;
 	se->avg.load_sum = se->avg.load_avg * LOAD_AVG_MAX;
 
-	/* Update parent cfs_rq load */
-	add_positive(&cfs_rq->avg.load_avg, delta);
-	cfs_rq->avg.load_sum = cfs_rq->avg.load_avg * LOAD_AVG_MAX;
+	if (propagate_avg) {
+		/* Update parent cfs_rq load */
+		add_positive(&cfs_rq->avg.load_avg, delta);
+		cfs_rq->avg.load_sum = cfs_rq->avg.load_avg * LOAD_AVG_MAX;
+	}
 
 	/*
 	 * If the sched_entity is already enqueued, we also have to update the
@@ -3147,22 +3150,27 @@ static inline int test_and_clear_tg_cfs_
 /* Update task and its cfs_rq load average */
 static inline int propagate_entity_load_avg(struct sched_entity *se)
 {
-	struct cfs_rq *cfs_rq;
+	struct cfs_rq *cfs_rq = cfs_rq_of(se);
+	bool propagate_avg;
 
 	if (entity_is_task(se))
 		return 0;
 
-	if (!test_and_clear_tg_cfs_propagate(se))
-		return 0;
-
-	cfs_rq = cfs_rq_of(se);
+	propagate_avg = test_and_clear_tg_cfs_propagate(se);
 
-	set_tg_cfs_propagate(cfs_rq);
+	/*
+	 * We want to keep @cfs_rq->runnable_load_avg always in sync so
+	 * that the load balancer can accurately determine the busiest CPU
+	 * regardless of cfs_rq nesting.
+	 */
+	update_tg_cfs_load(cfs_rq, se, propagate_avg);
 
-	update_tg_cfs_util(cfs_rq, se);
-	update_tg_cfs_load(cfs_rq, se);
+	if (propagate_avg) {
+		set_tg_cfs_propagate(cfs_rq);
+		update_tg_cfs_util(cfs_rq, se);
+	}
 
-	return 1;
+	return propagate_avg;
 }
 
 #else /* CONFIG_FAIR_GROUP_SCHED */
maintainer
#30 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

Quoted 63 lines · Tejun Heo

We noticed that with cgroup CPU controller in use, the scheduling latency gets wonky regardless of nesting level or weight configuration. This is easily reproducible with Chris Mason's schbench[1].

All tests are run on a single socket, 16 cores, 32 threads machine. While the machine is mostly idle, it isn't completey. There's always some variable management load going on. The command used is

schbench -m 2 -t 16 -s 10000 -c 15000 -r 30

which measures scheduling latency with 32 threads each of which repeatedly runs for 15ms and then sleeps for 10ms. Here's a representative result when running from the root cgroup.

# ~/schbench -m 2 -t 16 -s 10000 -c 15000 -r 30
Latency percentiles (usec)

         50.0000th: 26
         75.0000th: 62
         90.0000th: 74
         95.0000th: 86
         *99.0000th: 887
         99.5000th: 3692
         99.9000th: 10832
         min=0, max=13374

The following is inside a first level CPU cgroup with the maximum weight.

# ~/schbench -m 2 -t 16 -s 10000 -c 15000 -r 30
Latency percentiles (usec)

         50.0000th: 31
         75.0000th: 65
         90.0000th: 71
         95.0000th: 91
         *99.0000th: 7288
         99.5000th: 10352
         99.9000th: 12496
         min=0, max=13023

Note the drastic increase in p99 scheduling latency. After investigation, it turned out that the update_sd_lb_stats(), which is used by load_balance() to pick the most loaded group, was often picking the wrong group. A CPU which has one schbench running and another queued wouldn't report the correspondingly higher weighted_cpuload() and get looked over as the target of load balancing.

weighted_cpuload() is the root cfs_rq's runnable_load_avg which is the sum of the load_avg of all queued sched_entities. Without cgroups or at the root cgroup, each task's load_avg contributes directly to the sum. When a task wakes up or goes to sleep, the change is immediately reflected on runnable_load_avg which in turn affects load balancing.

However, when CPU cgroup is in use, a nesting cfs_rq blocks this immediate reflection. When a task wakes up inside a cgroup, the nested cfs_rq's runnable_load_avg is updated but doesn't get propagated to the parent. It only affects the matching sched_entity's load_avg over time which then gets propagated to the runnable_load_avg at that level. This makes weighted_cpuload() often temporarily out of sync leading to suboptimal behavior of load_balance() and increase in scheduling latencies as shown above.

Quoted 6 lines

This patch fixes the issue by updating propagate_entity_load_avg() to always propagate to the parent's runnable_load_avg. Combined with the previous patch, this keeps a cfs_rq's runnable_load_avg always the sum of the scaled loads of all tasks queued below removing the artifacts from nesting cfs_rqs. The following is from inside three levels of nesting with the patch applied.

So you are changing the purpose of propagate_entity_load_avg which aims to propagate load_avg/util_avg changes only when a task migrate and you also want to propagate the enqueue/dequeue in the parent cfs_rq->runnable_load_avg

Quoted 89 lines

# ~/schbench -m 2 -t 16 -s 10000 -c 15000 -r 30
Latency percentiles (usec)

         50.0000th: 40
         75.0000th: 71
         90.0000th: 89
         95.0000th: 108
         *99.0000th: 679
         99.5000th: 3500
         99.9000th: 10960
         min=0, max=13790

[1] git://git.kernel.org/pub/scm/linux/kernel/git/mason/schbench.git

Cc Vincent Guittot <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Mike Galbraith <[email protected]>
Cc Paul Turner <[email protected]>
Cc Chris Mason <[email protected]>
---
 kernel/sched/fair.c |   34 +++++++++++++++++++++-------------
 1 file changed, 21 insertions(+), 13 deletions(-)
kernel/sched/fair.c +21 -13
@@ -3075,7 +3075,8 @@ update_tg_cfs_util(struct cfs_rq *cfs_rq
 
 /* Take into account change of load of a child task group */
 static inline void
-update_tg_cfs_load(struct cfs_rq *cfs_rq, struct sched_entity *se)
+update_tg_cfs_load(struct cfs_rq *cfs_rq, struct sched_entity *se,
+                  bool propagate_avg)
 {
        struct cfs_rq *gcfs_rq = group_cfs_rq(se);
        long load = 0, delta;
@@ -3113,9 +3114,11 @@ update_tg_cfs_load(struct cfs_rq *cfs_rq
        se->avg.load_avg = load;
        se->avg.load_sum = se->avg.load_avg * LOAD_AVG_MAX;
 
-       /* Update parent cfs_rq load */
-       add_positive(&cfs_rq->avg.load_avg, delta);
-       cfs_rq->avg.load_sum = cfs_rq->avg.load_avg * LOAD_AVG_MAX;
+       if (propagate_avg) {
+               /* Update parent cfs_rq load */
+               add_positive(&cfs_rq->avg.load_avg, delta);
+               cfs_rq->avg.load_sum = cfs_rq->avg.load_avg * LOAD_AVG_MAX;
+       }
 
        /*
         * If the sched_entity is already enqueued, we also have to update the
@@ -3147,22 +3150,27 @@ static inline int test_and_clear_tg_cfs_
 /* Update task and its cfs_rq load average */
 static inline int propagate_entity_load_avg(struct sched_entity *se)
 {
-       struct cfs_rq *cfs_rq;
+       struct cfs_rq *cfs_rq = cfs_rq_of(se);
+       bool propagate_avg;
 
        if (entity_is_task(se))
                return 0;
 
-       if (!test_and_clear_tg_cfs_propagate(se))
-               return 0;
-
-       cfs_rq = cfs_rq_of(se);
+       propagate_avg = test_and_clear_tg_cfs_propagate(se);
 
-       set_tg_cfs_propagate(cfs_rq);
+       /*
+        * We want to keep @cfs_rq->runnable_load_avg always in sync so
+        * that the load balancer can accurately determine the busiest CPU
+        * regardless of cfs_rq nesting.
+        */
+       update_tg_cfs_load(cfs_rq, se, propagate_avg);
 
-       update_tg_cfs_util(cfs_rq, se);
-       update_tg_cfs_load(cfs_rq, se);
+       if (propagate_avg) {
+               set_tg_cfs_propagate(cfs_rq);
+               update_tg_cfs_util(cfs_rq, se);
+       }
 
-       return 1;
+       return propagate_avg;
 }
 
 #else /* CONFIG_FAIR_GROUP_SCHED */
maintainer
#31 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

Quoted 71 lines · Vincent Guittot
Quoted 63 lines · Tejun Heo

We noticed that with cgroup CPU controller in use, the scheduling latency gets wonky regardless of nesting level or weight configuration. This is easily reproducible with Chris Mason's schbench[1].

All tests are run on a single socket, 16 cores, 32 threads machine. While the machine is mostly idle, it isn't completey. There's always some variable management load going on. The command used is

schbench -m 2 -t 16 -s 10000 -c 15000 -r 30

which measures scheduling latency with 32 threads each of which repeatedly runs for 15ms and then sleeps for 10ms. Here's a representative result when running from the root cgroup.

# ~/schbench -m 2 -t 16 -s 10000 -c 15000 -r 30
Latency percentiles (usec)

         50.0000th: 26
         75.0000th: 62
         90.0000th: 74
         95.0000th: 86
         *99.0000th: 887
         99.5000th: 3692
         99.9000th: 10832
         min=0, max=13374

The following is inside a first level CPU cgroup with the maximum weight.

# ~/schbench -m 2 -t 16 -s 10000 -c 15000 -r 30
Latency percentiles (usec)

         50.0000th: 31
         75.0000th: 65
         90.0000th: 71
         95.0000th: 91
         *99.0000th: 7288
         99.5000th: 10352
         99.9000th: 12496
         min=0, max=13023

Note the drastic increase in p99 scheduling latency. After investigation, it turned out that the update_sd_lb_stats(), which is used by load_balance() to pick the most loaded group, was often picking the wrong group. A CPU which has one schbench running and another queued wouldn't report the correspondingly higher weighted_cpuload() and get looked over as the target of load balancing.

weighted_cpuload() is the root cfs_rq's runnable_load_avg which is the sum of the load_avg of all queued sched_entities. Without cgroups or at the root cgroup, each task's load_avg contributes directly to the sum. When a task wakes up or goes to sleep, the change is immediately reflected on runnable_load_avg which in turn affects load balancing.

However, when CPU cgroup is in use, a nesting cfs_rq blocks this immediate reflection. When a task wakes up inside a cgroup, the nested cfs_rq's runnable_load_avg is updated but doesn't get propagated to the parent. It only affects the matching sched_entity's load_avg over time which then gets propagated to the runnable_load_avg at that level. This makes weighted_cpuload() often temporarily out of sync leading to suboptimal behavior of load_balance() and increase in scheduling latencies as shown above.

Quoted 6 lines

This patch fixes the issue by updating propagate_entity_load_avg() to always propagate to the parent's runnable_load_avg. Combined with the previous patch, this keeps a cfs_rq's runnable_load_avg always the sum of the scaled loads of all tasks queued below removing the artifacts from nesting cfs_rqs. The following is from inside three levels of nesting with the patch applied.

Quoted 4 lines

So you are changing the purpose of propagate_entity_load_avg which aims to propagate load_avg/util_avg changes only when a task migrate and you also want to propagate the enqueue/dequeue in the parent cfs_rq->runnable_load_avg

In fact you want that sched_entity load_avg reflects cfs_rq->runnable_load_avg and not cfs_rq->avg.load_avg

Quoted 90 lines
Quoted 90 lines

# ~/schbench -m 2 -t 16 -s 10000 -c 15000 -r 30
Latency percentiles (usec)

         50.0000th: 40
         75.0000th: 71
         90.0000th: 89
         95.0000th: 108
         *99.0000th: 679
         99.5000th: 3500
         99.9000th: 10960
         min=0, max=13790

[1] git://git.kernel.org/pub/scm/linux/kernel/git/mason/schbench.git

Cc Vincent Guittot <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Mike Galbraith <[email protected]>
Cc Paul Turner <[email protected]>
Cc Chris Mason <[email protected]>
---
 kernel/sched/fair.c |   34 +++++++++++++++++++++-------------
 1 file changed, 21 insertions(+), 13 deletions(-)
kernel/sched/fair.c +21 -13
@@ -3075,7 +3075,8 @@ update_tg_cfs_util(struct cfs_rq *cfs_rq
 
 /* Take into account change of load of a child task group */
 static inline void
-update_tg_cfs_load(struct cfs_rq *cfs_rq, struct sched_entity *se)
+update_tg_cfs_load(struct cfs_rq *cfs_rq, struct sched_entity *se,
+                  bool propagate_avg)
 {
        struct cfs_rq *gcfs_rq = group_cfs_rq(se);
        long load = 0, delta;
@@ -3113,9 +3114,11 @@ update_tg_cfs_load(struct cfs_rq *cfs_rq
        se->avg.load_avg = load;
        se->avg.load_sum = se->avg.load_avg * LOAD_AVG_MAX;
 
-       /* Update parent cfs_rq load */
-       add_positive(&cfs_rq->avg.load_avg, delta);
-       cfs_rq->avg.load_sum = cfs_rq->avg.load_avg * LOAD_AVG_MAX;
+       if (propagate_avg) {
+               /* Update parent cfs_rq load */
+               add_positive(&cfs_rq->avg.load_avg, delta);
+               cfs_rq->avg.load_sum = cfs_rq->avg.load_avg * LOAD_AVG_MAX;
+       }
 
        /*
         * If the sched_entity is already enqueued, we also have to update the
@@ -3147,22 +3150,27 @@ static inline int test_and_clear_tg_cfs_
 /* Update task and its cfs_rq load average */
 static inline int propagate_entity_load_avg(struct sched_entity *se)
 {
-       struct cfs_rq *cfs_rq;
+       struct cfs_rq *cfs_rq = cfs_rq_of(se);
+       bool propagate_avg;
 
        if (entity_is_task(se))
                return 0;
 
-       if (!test_and_clear_tg_cfs_propagate(se))
-               return 0;
-
-       cfs_rq = cfs_rq_of(se);
+       propagate_avg = test_and_clear_tg_cfs_propagate(se);
 
-       set_tg_cfs_propagate(cfs_rq);
+       /*
+        * We want to keep @cfs_rq->runnable_load_avg always in sync so
+        * that the load balancer can accurately determine the busiest CPU
+        * regardless of cfs_rq nesting.
+        */
+       update_tg_cfs_load(cfs_rq, se, propagate_avg);
 
-       update_tg_cfs_util(cfs_rq, se);
-       update_tg_cfs_load(cfs_rq, se);
+       if (propagate_avg) {
+               set_tg_cfs_propagate(cfs_rq);
+               update_tg_cfs_util(cfs_rq, se);
+       }
 
-       return 1;
+       return propagate_avg;
 }
 
 #else /* CONFIG_FAIR_GROUP_SCHED */
maintainer
#32 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

Quoted 72 lines · Vincent Guittot
Quoted 71 lines · Vincent Guittot
Quoted 69 lines · Tejun Heo

We noticed that with cgroup CPU controller in use, the scheduling latency gets wonky regardless of nesting level or weight configuration. This is easily reproducible with Chris Mason's schbench[1].

All tests are run on a single socket, 16 cores, 32 threads machine. While the machine is mostly idle, it isn't completey. There's always some variable management load going on. The command used is

schbench -m 2 -t 16 -s 10000 -c 15000 -r 30

which measures scheduling latency with 32 threads each of which repeatedly runs for 15ms and then sleeps for 10ms. Here's a representative result when running from the root cgroup.

# ~/schbench -m 2 -t 16 -s 10000 -c 15000 -r 30
Latency percentiles (usec)

         50.0000th: 26
         75.0000th: 62
         90.0000th: 74
         95.0000th: 86
         *99.0000th: 887
         99.5000th: 3692
         99.9000th: 10832
         min=0, max=13374

The following is inside a first level CPU cgroup with the maximum weight.

# ~/schbench -m 2 -t 16 -s 10000 -c 15000 -r 30
Latency percentiles (usec)

         50.0000th: 31
         75.0000th: 65
         90.0000th: 71
         95.0000th: 91
         *99.0000th: 7288
         99.5000th: 10352
         99.9000th: 12496
         min=0, max=13023

Note the drastic increase in p99 scheduling latency. After investigation, it turned out that the update_sd_lb_stats(), which is used by load_balance() to pick the most loaded group, was often picking the wrong group. A CPU which has one schbench running and another queued wouldn't report the correspondingly higher weighted_cpuload() and get looked over as the target of load balancing.

weighted_cpuload() is the root cfs_rq's runnable_load_avg which is the sum of the load_avg of all queued sched_entities. Without cgroups or at the root cgroup, each task's load_avg contributes directly to the sum. When a task wakes up or goes to sleep, the change is immediately reflected on runnable_load_avg which in turn affects load balancing.

However, when CPU cgroup is in use, a nesting cfs_rq blocks this immediate reflection. When a task wakes up inside a cgroup, the nested cfs_rq's runnable_load_avg is updated but doesn't get propagated to the parent. It only affects the matching sched_entity's load_avg over time which then gets propagated to the runnable_load_avg at that level. This makes weighted_cpuload() often temporarily out of sync leading to suboptimal behavior of load_balance() and increase in scheduling latencies as shown above.

This patch fixes the issue by updating propagate_entity_load_avg() to always propagate to the parent's runnable_load_avg. Combined with the previous patch, this keeps a cfs_rq's runnable_load_avg always the sum of the scaled loads of all tasks queued below removing the artifacts from nesting cfs_rqs. The following is from inside three levels of nesting with the patch applied.

Quoted 7 lines
Quoted 4 lines

So you are changing the purpose of propagate_entity_load_avg which aims to propagate load_avg/util_avg changes only when a task migrate and you also want to propagate the enqueue/dequeue in the parent cfs_rq->runnable_load_avg

In fact you want that sched_entity load_avg reflects cfs_rq->runnable_load_avg and not cfs_rq->avg.load_avg

I have run a quick test with your patches and schbench on my platform. I haven't been able to reproduce your regression but my platform is quite different from yours (only 8 cores without SMT)
But most importantly, the parent cfs_rq->runnable_load_avg never reaches 0 (or almost 0) when it is idle. Instead, it still has a runnable_load_avg (this is not due to rounding computation) whereas runnable_load_avg should be 0

Just to be curious, Is your regression still there if you disable SMT/hyperthreading on your paltform?

Regards,
Vincent

Quoted 91 lines
Quoted 91 lines
Quoted 91 lines

# ~/schbench -m 2 -t 16 -s 10000 -c 15000 -r 30
Latency percentiles (usec)

         50.0000th: 40
         75.0000th: 71
         90.0000th: 89
         95.0000th: 108
         *99.0000th: 679
         99.5000th: 3500
         99.9000th: 10960
         min=0, max=13790

[1] git://git.kernel.org/pub/scm/linux/kernel/git/mason/schbench.git

Cc Vincent Guittot <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Mike Galbraith <[email protected]>
Cc Paul Turner <[email protected]>
Cc Chris Mason <[email protected]>
---
 kernel/sched/fair.c |   34 +++++++++++++++++++++-------------
 1 file changed, 21 insertions(+), 13 deletions(-)
kernel/sched/fair.c +21 -13
@@ -3075,7 +3075,8 @@ update_tg_cfs_util(struct cfs_rq *cfs_rq
 
 /* Take into account change of load of a child task group */
 static inline void
-update_tg_cfs_load(struct cfs_rq *cfs_rq, struct sched_entity *se)
+update_tg_cfs_load(struct cfs_rq *cfs_rq, struct sched_entity *se,
+                  bool propagate_avg)
 {
        struct cfs_rq *gcfs_rq = group_cfs_rq(se);
        long load = 0, delta;
@@ -3113,9 +3114,11 @@ update_tg_cfs_load(struct cfs_rq *cfs_rq
        se->avg.load_avg = load;
        se->avg.load_sum = se->avg.load_avg * LOAD_AVG_MAX;
 
-       /* Update parent cfs_rq load */
-       add_positive(&cfs_rq->avg.load_avg, delta);
-       cfs_rq->avg.load_sum = cfs_rq->avg.load_avg * LOAD_AVG_MAX;
+       if (propagate_avg) {
+               /* Update parent cfs_rq load */
+               add_positive(&cfs_rq->avg.load_avg, delta);
+               cfs_rq->avg.load_sum = cfs_rq->avg.load_avg * LOAD_AVG_MAX;
+       }
 
        /*
         * If the sched_entity is already enqueued, we also have to update the
@@ -3147,22 +3150,27 @@ static inline int test_and_clear_tg_cfs_
 /* Update task and its cfs_rq load average */
 static inline int propagate_entity_load_avg(struct sched_entity *se)
 {
-       struct cfs_rq *cfs_rq;
+       struct cfs_rq *cfs_rq = cfs_rq_of(se);
+       bool propagate_avg;
 
        if (entity_is_task(se))
                return 0;
 
-       if (!test_and_clear_tg_cfs_propagate(se))
-               return 0;
-
-       cfs_rq = cfs_rq_of(se);
+       propagate_avg = test_and_clear_tg_cfs_propagate(se);
 
-       set_tg_cfs_propagate(cfs_rq);
+       /*
+        * We want to keep @cfs_rq->runnable_load_avg always in sync so
+        * that the load balancer can accurately determine the busiest CPU
+        * regardless of cfs_rq nesting.
+        */
+       update_tg_cfs_load(cfs_rq, se, propagate_avg);
 
-       update_tg_cfs_util(cfs_rq, se);
-       update_tg_cfs_load(cfs_rq, se);
+       if (propagate_avg) {
+               set_tg_cfs_propagate(cfs_rq);
+               update_tg_cfs_util(cfs_rq, se);
+       }
 
-       return 1;
+       return propagate_avg;
 }
 
 #else /* CONFIG_FAIR_GROUP_SCHED */
author
#33 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

Hello,

Quoted 4 lines · Vincent Guittot
Quoted 4 lines
Quoted 4 lines

So you are changing the purpose of propagate_entity_load_avg which aims to propagate load_avg/util_avg changes only when a task migrate and you also want to propagate the enqueue/dequeue in the parent cfs_rq->runnable_load_avg

Yeah, it always propagates runnable_load_avg and load_avg/util_avg too on migrations.

Quoted 2 lines
Quoted 2 lines

In fact you want that sched_entity load_avg reflects cfs_rq->runnable_load_avg and not cfs_rq->avg.load_avg

Yes, that's how it gets changed. The load balancer assumes that the root's runnable_load_avg is the total sum of all currently active tasks. Nesting cfs_rq's shouldn't change that and how it should be mapped is clearly defined (scaled recursively till it reaches the root), which is what the code calculates. The change in cfs_rq->avg.load_avg's behavior is to reflect that immediate propagation as load_avg and runnable_load_avg are tightly coupled.

While it does change a nested cfs_rq's load_avg behavior. It sheds of the extra layer of averaging and directly reflects the scaled load avgs of its members, which are already time averaged. I could have missed something but couldn't spot anything which can break from this.

Quoted 7 lines

I have run a quick test with your patches and schbench on my platform. I haven't been able to reproduce your regression but my platform is quite different from yours (only 8 cores without SMT)
But most importantly, the parent cfs_rq->runnable_load_avg never reaches 0 (or almost 0) when it is idle. Instead, it still has a runnable_load_avg (this is not due to rounding computation) whereas runnable_load_avg should be 0

Heh, let me try that out. Probably a silly mistake somewhere.

Quoted 2 lines

Just to be curious, Is your regression still there if you disable SMT/hyperthreading on your paltform?

Will try that too. I can't see why HT would change it because I see single CPU queues misevaluated. Just in case, you need to tune the test params so that it doesn't load the machine too much and that there are some non-CPU intensive workloads going on to purturb things a bit. Anyways, I'm gonna try disabling HT.

Thanks.

Signature · 1 line
tejun
author
#34 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

Quoted 5 lines · Tejun Heo

Will try that too. I can't see why HT would change it because I see single CPU queues misevaluated. Just in case, you need to tune the test params so that it doesn't load the machine too much and that there are some non-CPU intensive workloads going on to purturb things a bit. Anyways, I'm gonna try disabling HT.

It's finickier but after changing the duty cycle a bit, it reproduces w/ HT off. I think the trick is setting the number of threads to the number of logical CPUs and tune -s/-c so that p99 starts climbing up. The following is from the root cgroup.

~/schbench -m 2 -t 8 -s 15000 -c 10000 -r 30
Latency percentiles (usec)

	 50.0000th: 51
	 75.0000th: 62
	 90.0000th: 67
	 95.0000th: 70
	 *99.0000th: 1482
	 99.5000th: 5048
	 99.9000th: 9008
	 min=0, max=10066

And the following is from a first-level cgroup with maximum CPU weight.

# ~/schbench -m 2 -t 8 -s 15000 -c 10000 -r 30
Latency percentiles (usec)

	 50.0000th: 51
	 75.0000th: 62
	 90.0000th: 71
	 95.0000th: 84
	 *99.0000th: 10064
	 99.5000th: 10064
	 99.9000th: 10064
	 min=0, max=10089

It's interesting that p99 ends up aligned on the CPU burn duration. It looks like some threads end up wating for full durations.

The following is with the patches applied in the same cgroup setup.

# ~/schbench -m 2 -t 8 -s 15000 -c 10000 -r 30
Latency percentiles (usec)

	 50.0000th: 64
	 75.0000th: 73
	 90.0000th: 102
	 95.0000th: 111
	 *99.0000th: 1954
	 99.5000th: 5432
	 99.9000th: 9520
	 min=0, max=10012

The numbers fluctuate quite a bit between runs but the pattern is still very clear - e.g. 10ms p99 never shows up in the root cgroup or on the patched kernel.

Thanks.

Signature · 1 line
tejun
#35 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

Quoted 11 lines · Tejun Heo
Quoted 5 lines · Tejun Heo

Will try that too. I can't see why HT would change it because I see single CPU queues misevaluated. Just in case, you need to tune the test params so that it doesn't load the machine too much and that there are some non-CPU intensive workloads going on to purturb things a bit. Anyways, I'm gonna try disabling HT.

It's finickier but after changing the duty cycle a bit, it reproduces w/ HT off. I think the trick is setting the number of threads to the number of logical CPUs and tune -s/-c so that p99 starts climbing up. The following is from the root cgroup.

Since it's only measuring wakeup latency, schbench is best at exposing problems when the machine is just barely below saturated. At saturation, everyone has to wait for the CPUs, and if we're relatively idle there's always a CPU to be found

There's schbench -a to try and find this magic tipping point, but I haven't found a great way to automate for every kind of machine yet (sorry).

-chris

author
#36 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

In reply to Tejun Heo
Quoted 9 lines · Tejun Heo
Quoted 7 lines

I have run a quick test with your patches and schbench on my platform. I haven't been able to reproduce your regression but my platform is quite different from yours (only 8 cores without SMT)
But most importantly, the parent cfs_rq->runnable_load_avg never reaches 0 (or almost 0) when it is idle. Instead, it still has a runnable_load_avg (this is not due to rounding computation) whereas runnable_load_avg should be 0

Heh, let me try that out. Probably a silly mistake somewhere.

This is from the follow-up patch. I was confused. Because we don't propagate decays, we still should decay the runnable_load_avg; otherwise, we end up accumulating errors in the counter. I'll drop the last patch.

Thanks.

Signature · 1 line
tejun
maintainer
#37 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

Quoted 9 lines · Tejun Heo
Quoted 8 lines · Tejun Heo
Quoted 7 lines

I have run a quick test with your patches and schbench on my platform. I haven't been able to reproduce your regression but my platform is quite different from yours (only 8 cores without SMT)
But most importantly, the parent cfs_rq->runnable_load_avg never reaches 0 (or almost 0) when it is idle. Instead, it still has a runnable_load_avg (this is not due to rounding computation) whereas runnable_load_avg should be 0

Quoted 6 lines
Quoted 1 line

Heh, let me try that out. Probably a silly mistake somewhere.

This is from the follow-up patch. I was confused. Because we don't propagate decays, we still should decay the runnable_load_avg; otherwise, we end up accumulating errors in the counter. I'll drop the last patch.

Ok, the runnable_load_avg goes back to 0 when I drop patch 3. But i see runnable_load_avg sometimes significantly higher than load_avg which is normally not possible as load_avg = runnable_load_avg + sleeping task's load_avg

Then, I just have the opposite behavior on my platform. I see a increase of latency at p99 with your patches.
My platform is a hikey : 2x4 cores ARM and I have used schbench -m 2 -t 4 -s 10000 -c 15000 -r 30 so I have 1 worker thread per CPU which is similar to what you are doing on your platform

With v4.11-rc8. I have run 10 times the test and get consistent results schbench -m 2 -t 4 -s 10000 -c 15000 -r 30
Latency percentiles (usec)
50.0000th: 255
75.0000th: 350
90.0000th: 454
95.0000th: 489
*99.0000th: 539
99.5000th: 585
99.9000th: 10224
min=0, max=13567

With your patches i see an increase of the latency for p99. I run 10 times the test too and half tests show latency increase like below schbench$ ./schbench -m 2 -t 4 -s 10000 -c 15000 -r 30 Latency percentiles (usec)
50.0000th: 216
75.0000th: 295
90.0000th: 395
95.0000th: 444
*99.0000th: 2034
99.5000th: 5960
99.9000th: 12240
min=0, max=14744

Quoted 5 lines

Thanks.

--
tejun

author
#38 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

Hello, Vincent.

Quoted 9 lines · Vincent Guittot
Quoted 4 lines

This is from the follow-up patch. I was confused. Because we don't propagate decays, we still should decay the runnable_load_avg; otherwise, we end up accumulating errors in the counter. I'll drop the last patch.

Ok, the runnable_load_avg goes back to 0 when I drop patch 3. But i see runnable_load_avg sometimes significantly higher than load_avg which is normally not possible as load_avg = runnable_load_avg + sleeping task's load_avg

So, while load_avg would eventually converge on runnable_load_avg + blocked load_avg given stable enough workload for long enough, runnable_load_avg jumping above load avg temporarily is expected, AFAICS. That's the whole point of it, a sum closely tracking what's currently on the cpu so that we can pick the cpu which has the most on it now. It doesn't make sense to try to pick threads off of a cpu which is generally loaded but doesn't have much going on right now, after all.

Quoted 7 lines

Then, I just have the opposite behavior on my platform. I see a increase of latency at p99 with your patches.
My platform is a hikey : 2x4 cores ARM and I have used schbench -m 2 -t 4 -s 10000 -c 15000 -r 30 so I have 1 worker thread per CPU which is similar to what you are doing on your platform

With v4.11-rc8. I have run 10 times the test and get consistent results

...

Quoted 1 line

*99.0000th: 539

...

Quoted 2 lines

With your patches i see an increase of the latency for p99. I run 10 *99.0000th: 2034

I see. This is surprising given that at least the purpose of the patch is restoring cgroup behavior to match !cgroup one. I could have totally messed it up tho. Hmm... there are several ways forward I guess.

* Can you please double check that the higher latencies w/ the patch is reliably reproducible? The test machines that I use have variable management load. They never dominate the machine but are enough to disturb the results so that to drawing out a reliable pattern takes a lot of repeated runs. I'd really appreciate if you could double check that the pattern is reliable with different run patterns (ie. instead of 10 consecutive runs after another, interleaved).

* Is the board something easily obtainable? It'd be the eaisest for me to set up the same environment and reproduce the problem. I looked up hikey boards on amazon but couldn't easily find 2x4 core ones. If there's something I can easily buy, please point me to it. If there's something I can loan, that'd be great too.

* If not, I'll try to clean up the debug patches I have and send them your way to get more visiblity but given these things tend to be very iterative, it might take quite a few back and forth.

Thanks!

Signature · 1 line
tejun
maintainer
#39 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

Quoted 8 lines · Tejun Heo

Hello, Vincent.

Quoted 5 lines · Vincent Guittot
Quoted 4 lines

This is from the follow-up patch. I was confused. Because we don't propagate decays, we still should decay the runnable_load_avg; otherwise, we end up accumulating errors in the counter. I'll drop the last patch.

Quoted 8 lines
Quoted 4 lines

Ok, the runnable_load_avg goes back to 0 when I drop patch 3. But i see runnable_load_avg sometimes significantly higher than load_avg which is normally not possible as load_avg = runnable_load_avg + sleeping task's load_avg

So, while load_avg would eventually converge on runnable_load_avg + blocked load_avg given stable enough workload for long enough, runnable_load_avg jumping above load avg temporarily is expected,

No, it's not. Look at load_avg/runnable_avg at root domain when only task are involved, runnable_load_avg will never be higher than load_avg because
load_avg = /sum load_avg of tasks attached to the cfs_rq runnable_load_avg = /sum load_avg of tasks attached and enqueued
to the cfs_rq
load_avg = runnable_load_avg + blocked tasks and as a result runnable_load_avg is always lower than load_avg.
And with the propagate load/util_avg patchset, we can even reflect task migration directly at root domain whereas we had to wait for the util/load_avg and runnable_load_avg to converge to the new value before

Just to confirm one of my assumption, the latency regression was already there in previous kernel versions and is not a result of propagate load/util_avg patchset, isn't it ?

Quoted 5 lines

AFAICS. That's the whole point of it, a sum closely tracking what's currently on the cpu so that we can pick the cpu which has the most on it now. It doesn't make sense to try to pick threads off of a cpu which is generally loaded but doesn't have much going on right now, after all.

The only interest of runnable_load_avg is to be null when a cfs_rq is idle whereas load_avg is not but not to be higher than load_avg. The root cause is that load_balance only looks at "load" but not number of task currently running and that's probably the main problem:
runnable_load_avg has been added because load_balance fails to filter idle group and idle rq. We should better add a new type in group_classify to tag group that are idle and the same in find_busiest_queue more.

Quoted 19 lines
Quoted 8 lines

Then, I just have the opposite behavior on my platform. I see a increase of latency at p99 with your patches.
My platform is a hikey : 2x4 cores ARM and I have used schbench -m 2 -t 4 -s 10000 -c 15000 -r 30 so I have 1 worker thread per CPU which is similar to what you are doing on your platform

With v4.11-rc8. I have run 10 times the test and get consistent results

...

Quoted 1 line

*99.0000th: 539

...

Quoted 2 lines

With your patches i see an increase of the latency for p99. I run 10 *99.0000th: 2034

I see. This is surprising given that at least the purpose of the patch is restoring cgroup behavior to match !cgroup one. I could have totally messed it up tho. Hmm... there are several ways forward I guess.

Quoted 8 lines

* Can you please double check that the higher latencies w/ the patch is reliably reproducible? The test machines that I use have variable management load. They never dominate the machine but are enough to disturb the results so that to drawing out a reliable pattern takes a lot of repeated runs. I'd really appreciate if you could double check that the pattern is reliable with different run patterns (ie. instead of 10 consecutive runs after another, interleaved).

I always let time between 2 consecutive run and the 10 consecutive runs take around 2min to execute

Then I have run several time these 10 consecutive test and results stay the same

Quoted 4 lines

* Is the board something easily obtainable? It'd be the eaisest for me to set up the same environment and reproduce the problem. I looked up hikey boards on amazon but couldn't easily find 2x4 core

It is often named hikey octo cores but I use 2x4 cores just to point out that there are 2 clusters which is important for scheduler topology and behavior

Quoted 2 lines

ones. If there's something I can easily buy, please point me to it. If there's something I can loan, that'd be great too.

It looks like most of web site are currently out of stock

Quoted 4 lines

* If not, I'll try to clean up the debug patches I have and send them your way to get more visiblity but given these things tend to be very iterative, it might take quite a few back and forth.

Yes, that could be usefull. Even a trace of regression could be useful

I can also push on my git tree the debug patch that i use for tracking load metrics if you want. It's ugly but it does the job

Thanks

Quoted 5 lines

Thanks!

--
tejun

author
#40 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

Hello, Vincent.

Quoted 18 lines · Vincent Guittot
Quoted 8 lines · Tejun Heo

Hello, Vincent.

Quoted 5 lines · Vincent Guittot
Quoted 4 lines

This is from the follow-up patch. I was confused. Because we don't propagate decays, we still should decay the runnable_load_avg; otherwise, we end up accumulating errors in the counter. I'll drop the last patch.

Quoted 8 lines
Quoted 4 lines

Ok, the runnable_load_avg goes back to 0 when I drop patch 3. But i see runnable_load_avg sometimes significantly higher than load_avg which is normally not possible as load_avg = runnable_load_avg + sleeping task's load_avg

So, while load_avg would eventually converge on runnable_load_avg + blocked load_avg given stable enough workload for long enough, runnable_load_avg jumping above load avg temporarily is expected,

Quoted 8 lines

No, it's not. Look at load_avg/runnable_avg at root domain when only task are involved, runnable_load_avg will never be higher than load_avg because
load_avg = /sum load_avg of tasks attached to the cfs_rq runnable_load_avg = /sum load_avg of tasks attached and enqueued
to the cfs_rq
load_avg = runnable_load_avg + blocked tasks and as a result runnable_load_avg is always lower than load_avg.

We don't actually calculate that tho, but yeah, given the calculations we do, runnable shouldn't be significantly higher than load_avg. I see runable going above load_avg by a bit often but the margins are small. I wonder whether you're seeing the errors accumulating from the incorrect min() capping.

Quoted 8 lines

And with the propagate load/util_avg patchset, we can even reflect task migration directly at root domain whereas we had to wait for the util/load_avg and runnable_load_avg to converge to the new value before

Just to confirm one of my assumption, the latency regression was already there in previous kernel versions and is not a result of propagate load/util_avg patchset, isn't it ?

Yeah, the latency problem is independent of the propagation logic. It's really the meaning of the top level running_avg_load being different w/ and w/o cgroups.

Quoted 6 lines
Quoted 5 lines

AFAICS. That's the whole point of it, a sum closely tracking what's currently on the cpu so that we can pick the cpu which has the most on it now. It doesn't make sense to try to pick threads off of a cpu which is generally loaded but doesn't have much going on right now, after all.

Quoted 8 lines

The only interest of runnable_load_avg is to be null when a cfs_rq is idle whereas load_avg is not but not to be higher than load_avg. The root cause is that load_balance only looks at "load" but not number of task currently running and that's probably the main problem:
runnable_load_avg has been added because load_balance fails to filter idle group and idle rq. We should better add a new type in group_classify to tag group that are idle and the same in find_busiest_queue more.

I'll follow up in the other subthread but there really is fundamental difference in how we calculate runnable_avg w/ and w/o cgroups. Indepndent of whether we can improve the load balancer further, it is an existing bug.

Quoted 9 lines
Quoted 8 lines

* Can you please double check that the higher latencies w/ the patch is reliably reproducible? The test machines that I use have variable management load. They never dominate the machine but are enough to disturb the results so that to drawing out a reliable pattern takes a lot of repeated runs. I'd really appreciate if you could double check that the pattern is reliable with different run patterns (ie. instead of 10 consecutive runs after another, interleaved).

Quoted 4 lines

I always let time between 2 consecutive run and the 10 consecutive runs take around 2min to execute

Then I have run several time these 10 consecutive test and results stay the same

Can you please try the patch at the end of this message? I'm wondering whether you're seeing the errors accumulating from the wrong min().

Quoted 4 lines
Quoted 2 lines

ones. If there's something I can easily buy, please point me to it. If there's something I can loan, that'd be great too.

It looks like most of web site are currently out of stock

:(

Quoted 5 lines
Quoted 3 lines

* If not, I'll try to clean up the debug patches I have and send them your way to get more visiblity but given these things tend to be very iterative, it might take quite a few back and forth.

Yes, that could be usefull. Even a trace of regression could be useful

Yeah, will clean it up a bit and post. Will also post some traces.

And here's the updated patch. I didn't add the suggested scale_down()'s. I'll follow up on that in the other subthread. Thanks.

 kernel/sched/fair.c |   47 ++++++++++++++++++++---------------------------
 1 file changed, 20 insertions(+), 27 deletions(-)
kernel/sched/fair.c +20 -27
@@ -3078,37 +3078,30 @@ static inline void
 update_tg_cfs_load(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
 	struct cfs_rq *gcfs_rq = group_cfs_rq(se);
-	long delta, load = gcfs_rq->avg.load_avg;
+	long load = 0, delta;
 
 	/*
-	 * If the load of group cfs_rq is null, the load of the
-	 * sched_entity will also be null so we can skip the formula
+	 * A cfs_rq's load avg contribution to the parent should be scaled
+	 * to the sched_entity's weight.  Use freshly calculated shares
+	 * instead of @se->load.weight as the latter may not reflect
+	 * changes from the current scheduling operation.
+	 *
+	 * Note that the propagation source is runnable_load_avg instead of
+	 * load_avg.  This keeps every cfs_rq's runnable_load_avg true to
+	 * the sum of the scaled loads of all tasks queued under it, which
+	 * is important for the correct operation of the load balancer.
+	 *
+	 * This can make the sched_entity's load_avg jumpier but that
+	 * correctly reflects what would happen without cgroups if each
+	 * task's load is scaled across nesting - the load is being
+	 * averaged at the task and each cfs_rq.
 	 */
-	if (load) {
-		long tg_load;
+	if (gcfs_rq->load.weight) {
+		long shares = calc_cfs_shares(gcfs_rq, gcfs_rq->tg);
 
-		/* Get tg's load and ensure tg_load > 0 */
-		tg_load = atomic_long_read(&gcfs_rq->tg->load_avg) + 1;
-
-		/* Ensure tg_load >= load and updated with current load*/
-		tg_load -= gcfs_rq->tg_load_avg_contrib;
-		tg_load += load;
-
-		/*
-		 * We need to compute a correction term in the case that the
-		 * task group is consuming more CPU than a task of equal
-		 * weight. A task with a weight equals to tg->shares will have
-		 * a load less or equal to scale_load_down(tg->shares).
-		 * Similarly, the sched_entities that represent the task group
-		 * at parent level, can't have a load higher than
-		 * scale_load_down(tg->shares). And the Sum of sched_entities'
-		 * load must be <= scale_load_down(tg->shares).
-		 */
-		if (tg_load > scale_load_down(gcfs_rq->tg->shares)) {
-			/* scale gcfs_rq's load into tg's shares*/
-			load *= scale_load_down(gcfs_rq->tg->shares);
-			load /= tg_load;
-		}
+		load = min_t(long, scale_load_down(shares),
+			     gcfs_rq->runnable_load_avg *
+			     shares / gcfs_rq->load.weight);
 	}
 
 	delta = load - se->avg.load_avg;
maintainer
#41 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

Quoted 12 lines · Tejun Heo

Hello, Vincent.

Quoted 9 lines

The only interest of runnable_load_avg is to be null when a cfs_rq is idle whereas load_avg is not but not to be higher than load_avg. The root cause is that load_balance only looks at "load" but not number of task currently running and that's probably the main problem:
runnable_load_avg has been added because load_balance fails to filter idle group and idle rq. We should better add a new type in group_classify to tag group that are idle and the same in find_busiest_queue more.

Quoted 4 lines

I'll follow up in the other subthread but there really is fundamental difference in how we calculate runnable_avg w/ and w/o cgroups. Indepndent of whether we can improve the load balancer further, it is an existing bug.

I'd like to weight that a bit.
The runnable_load_avg works correctly as it is because it reflects correctly the load of runnable entity at root domain
If you start to propagate the runnable_load_avg on the load_avg of the group entity, the load will become unstable. runnable_load_avg has been added to fix load_balance being unable to select the right busiest rq. So the goal is to use more and more load_avg not the opposite

Quoted 10 lines
Quoted 10 lines
Quoted 9 lines

* Can you please double check that the higher latencies w/ the patch is reliably reproducible? The test machines that I use have variable management load. They never dominate the machine but are enough to disturb the results so that to drawing out a reliable pattern takes a lot of repeated runs. I'd really appreciate if you could double check that the pattern is reliable with different run patterns (ie. instead of 10 consecutive runs after another, interleaved).

Quoted 8 lines
Quoted 4 lines

I always let time between 2 consecutive run and the 10 consecutive runs take around 2min to execute

Then I have run several time these 10 consecutive test and results stay the same

Can you please try the patch at the end of this message? I'm wondering whether you're seeing the errors accumulating from the wrong min().

I still have the regression with the patch below.
The regression comes from the use runnable_load_avg to propagate. As load_avg becomes null at some point, it break the computation of share and the load_avg stay very low

Quoted 83 lines
Quoted 5 lines
Quoted 3 lines

ones. If there's something I can easily buy, please point me to it. If there's something I can loan, that'd be great too.

It looks like most of web site are currently out of stock

:(

Quoted 5 lines
Quoted 3 lines

* If not, I'll try to clean up the debug patches I have and send them your way to get more visiblity but given these things tend to be very iterative, it might take quite a few back and forth.

Yes, that could be usefull. Even a trace of regression could be useful

Yeah, will clean it up a bit and post. Will also post some traces.

And here's the updated patch. I didn't add the suggested scale_down()'s. I'll follow up on that in the other subthread. Thanks.

 kernel/sched/fair.c |   47 ++++++++++++++++++++---------------------------
 1 file changed, 20 insertions(+), 27 deletions(-)
kernel/sched/fair.c +20 -27
@@ -3078,37 +3078,30 @@ static inline void
 update_tg_cfs_load(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
        struct cfs_rq *gcfs_rq = group_cfs_rq(se);
-       long delta, load = gcfs_rq->avg.load_avg;
+       long load = 0, delta;
 
        /*
-        * If the load of group cfs_rq is null, the load of the
-        * sched_entity will also be null so we can skip the formula
+        * A cfs_rq's load avg contribution to the parent should be scaled
+        * to the sched_entity's weight.  Use freshly calculated shares
+        * instead of @se->load.weight as the latter may not reflect
+        * changes from the current scheduling operation.
+        *
+        * Note that the propagation source is runnable_load_avg instead of
+        * load_avg.  This keeps every cfs_rq's runnable_load_avg true to
+        * the sum of the scaled loads of all tasks queued under it, which
+        * is important for the correct operation of the load balancer.
+        *
+        * This can make the sched_entity's load_avg jumpier but that
+        * correctly reflects what would happen without cgroups if each
+        * task's load is scaled across nesting - the load is being
+        * averaged at the task and each cfs_rq.
         */
-       if (load) {
-               long tg_load;
+       if (gcfs_rq->load.weight) {
+               long shares = calc_cfs_shares(gcfs_rq, gcfs_rq->tg);
 
-               /* Get tg's load and ensure tg_load > 0 */
-               tg_load = atomic_long_read(&gcfs_rq->tg->load_avg) + 1;
-
-               /* Ensure tg_load >= load and updated with current load*/
-               tg_load -= gcfs_rq->tg_load_avg_contrib;
-               tg_load += load;
-
-               /*
-                * We need to compute a correction term in the case that the
-                * task group is consuming more CPU than a task of equal
-                * weight. A task with a weight equals to tg->shares will have
-                * a load less or equal to scale_load_down(tg->shares).
-                * Similarly, the sched_entities that represent the task group
-                * at parent level, can't have a load higher than
-                * scale_load_down(tg->shares). And the Sum of sched_entities'
-                * load must be <= scale_load_down(tg->shares).
-                */
-               if (tg_load > scale_load_down(gcfs_rq->tg->shares)) {
-                       /* scale gcfs_rq's load into tg's shares*/
-                       load *= scale_load_down(gcfs_rq->tg->shares);
-                       load /= tg_load;
-               }
+               load = min_t(long, scale_load_down(shares),
+                            gcfs_rq->runnable_load_avg *
+                            shares / gcfs_rq->load.weight);
        }
 
        delta = load - se->avg.load_avg;
author
#42 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

Hello, Vincent.

Quoted 6 lines · Vincent Guittot
Quoted 4 lines · Tejun Heo

I'll follow up in the other subthread but there really is fundamental difference in how we calculate runnable_avg w/ and w/o cgroups. Indepndent of whether we can improve the load balancer further, it is an existing bug.

Quoted 8 lines

I'd like to weight that a bit.
The runnable_load_avg works correctly as it is because it reflects correctly the load of runnable entity at root domain
If you start to propagate the runnable_load_avg on the load_avg of the group entity, the load will become unstable. runnable_load_avg has been added to fix load_balance being unable to select the right busiest rq. So the goal is to use more and more load_avg not the opposite

I have a hard time understanding what you're trying to say here.

Without cgroup, the load balancer uses the sum of load_avgs of the running tasks on the queue. As shown by the debug trace, the load balancer repeatedly ends up picking the wrong CPU when cgroup is involved because it ends up including the load_avgs of nested blocked tasks into runnable_load_avg of root - we lose the distinction between running and blocked load_avgs when we pass through a nested cfs_rq.

We can further improve the load balancer all we want, for example, right now, we would end up picking a CPU with one task which has a really high weight over another CPU with two normal weight tasks even, which isn't ideal; however, there is something obviously broken in the existing mechanism and we want to fix that first independent of further improvements, and it won't be a good idea to paper over an existing problem with a different mechanism either.

Quoted 5 lines
Quoted 5 lines
Quoted 4 lines

I always let time between 2 consecutive run and the 10 consecutive runs take around 2min to execute

Then I have run several time these 10 consecutive test and results stay the same

Quoted 8 lines
Quoted 3 lines

Can you please try the patch at the end of this message? I'm wondering whether you're seeing the errors accumulating from the wrong min().

I still have the regression with the patch below.
The regression comes from the use runnable_load_avg to propagate. As load_avg becomes null at some point, it break the computation of share and the load_avg stay very low

That's surprising given that what the patch does is bringing the cgroup behavior closer to !cgroup behavior. It'd be great to be able to reproduce the problem and trace it. It looks like the board is pretty standardized. Would the following be equivalent to the one you have?

http://a.co/f3dD1lm

If so, I can just buy it, get your test image and repro it here and trace why the regression is happening with the setup. We might be hitting something else.

Thanks.

Signature · 1 line
tejun
maintainer
#43 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

Quoted 27 lines · Tejun Heo

Hello, Vincent.

Quoted 6 lines · Vincent Guittot
Quoted 4 lines · Tejun Heo

I'll follow up in the other subthread but there really is fundamental difference in how we calculate runnable_avg w/ and w/o cgroups. Indepndent of whether we can improve the load balancer further, it is an existing bug.

Quoted 8 lines

I'd like to weight that a bit.
The runnable_load_avg works correctly as it is because it reflects correctly the load of runnable entity at root domain
If you start to propagate the runnable_load_avg on the load_avg of the group entity, the load will become unstable. runnable_load_avg has been added to fix load_balance being unable to select the right busiest rq. So the goal is to use more and more load_avg not the opposite

I have a hard time understanding what you're trying to say here.

Without cgroup, the load balancer uses the sum of load_avgs of the running tasks on the queue. As shown by the debug trace, the load balancer repeatedly ends up picking the wrong CPU when cgroup is involved because it ends up including the load_avgs of nested blocked tasks into runnable_load_avg of root - we lose the distinction between running and blocked load_avgs when we pass through a nested cfs_rq.

Quoted 7 lines

We can further improve the load balancer all we want, for example, right now, we would end up picking a CPU with one task which has a really high weight over another CPU with two normal weight tasks even, which isn't ideal; however, there is something obviously broken in the existing mechanism and we want to fix that first independent of further improvements, and it won't be a good idea to paper over an existing problem with a different mechanism either.

That's probably where I disagree.
IMO, runnable_load_avg is already a fix to compensate the fact when PELT has been rewritten, the load balance has not been update accordingly and was unable to make the right choice between 2 groups: one group having only 1 task but a higher load and another group with several tasks but a lower load (either because of the blocked load or because a runnable task with far higher load than others). runnable_load_avg has been put back to quickly fix the 1st case but it doesn't fix the other. There were also some issues of propagating load update with task migration but this has been fixed now.
So we have 2 use case with the exact same behavior a group with a higher load (runnable_load_avg or load_avg) but only 1 task and another one with several tasks but a lower load. At now runnable_load_avg can only fix one with the impact of breaking load_avg behavior whereas one fix in the load_balance can fix both withour breaking load_avg behavior.
We should better work on removing runnable_load_avg completely than adding more stuff on it

Quoted 10 lines
Quoted 10 lines
Quoted 9 lines
Quoted 5 lines

I always let time between 2 consecutive run and the 10 consecutive runs take around 2min to execute

Then I have run several time these 10 consecutive test and results stay the same

Can you please try the patch at the end of this message? I'm wondering whether you're seeing the errors accumulating from the wrong min().

Quoted 7 lines
Quoted 4 lines

I still have the regression with the patch below.
The regression comes from the use runnable_load_avg to propagate. As load_avg becomes null at some point, it break the computation of share and the load_avg stay very low

That's surprising given that what the patch does is bringing the cgroup behavior closer to !cgroup behavior. It'd be great to be able

But it's also break load_avg which is used to calculate per cfs_rq share and this change generates the regression on my board

Quoted 5 lines

to reproduce the problem and trace it. It looks like the board is pretty standardized. Would the following be equivalent to the one you have?

http://a.co/f3dD1lm

Yes it's this board i have the previous version but it should not change the behavior

Quoted 4 lines

If so, I can just buy it, get your test image and repro it here and trace why the regression is happening with the setup. We might be hitting something else.

I have pushed my branch which includes v4.11-rc8 + your patches + some debug trace here:
https://git.linaro.org/people/vincent.guittot/kernel.git/log/?h=test-tejun-patches

and uploaded a trace_cmd's trace that shows the regression
http://people.linaro.org/~vincent.guittot/trace-tejun-patches

As an example, we can easily see arounf time stamp 94.826469 sec that cpu5 is idle while CPU2 and CPU3 share their time between several task.
This doesn't happens without your patch

Quoted 5 lines

Thanks.

--
tejun

maintainer
#44 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

Quoted 90 lines · Vincent Guittot
Quoted 27 lines · Tejun Heo

Hello, Vincent.

Quoted 6 lines · Vincent Guittot
Quoted 4 lines · Tejun Heo

I'll follow up in the other subthread but there really is fundamental difference in how we calculate runnable_avg w/ and w/o cgroups. Indepndent of whether we can improve the load balancer further, it is an existing bug.

Quoted 8 lines

I'd like to weight that a bit.
The runnable_load_avg works correctly as it is because it reflects correctly the load of runnable entity at root domain
If you start to propagate the runnable_load_avg on the load_avg of the group entity, the load will become unstable. runnable_load_avg has been added to fix load_balance being unable to select the right busiest rq. So the goal is to use more and more load_avg not the opposite

I have a hard time understanding what you're trying to say here.

Without cgroup, the load balancer uses the sum of load_avgs of the running tasks on the queue. As shown by the debug trace, the load balancer repeatedly ends up picking the wrong CPU when cgroup is involved because it ends up including the load_avgs of nested blocked tasks into runnable_load_avg of root - we lose the distinction between running and blocked load_avgs when we pass through a nested cfs_rq.

Quoted 7 lines

We can further improve the load balancer all we want, for example, right now, we would end up picking a CPU with one task which has a really high weight over another CPU with two normal weight tasks even, which isn't ideal; however, there is something obviously broken in the existing mechanism and we want to fix that first independent of further improvements, and it won't be a good idea to paper over an existing problem with a different mechanism either.

That's probably where I disagree.
IMO, runnable_load_avg is already a fix to compensate the fact when PELT has been rewritten, the load balance has not been update accordingly and was unable to make the right choice between 2 groups: one group having only 1 task but a higher load and another group with several tasks but a lower load (either because of the blocked load or because a runnable task with far higher load than others). runnable_load_avg has been put back to quickly fix the 1st case but it doesn't fix the other. There were also some issues of propagating load update with task migration but this has been fixed now.
So we have 2 use case with the exact same behavior a group with a higher load (runnable_load_avg or load_avg) but only 1 task and another one with several tasks but a lower load. At now runnable_load_avg can only fix one with the impact of breaking load_avg behavior whereas one fix in the load_balance can fix both withour breaking load_avg behavior.
We should better work on removing runnable_load_avg completely than adding more stuff on it

Quoted 10 lines
Quoted 10 lines
Quoted 9 lines
Quoted 5 lines

I always let time between 2 consecutive run and the 10 consecutive runs take around 2min to execute

Then I have run several time these 10 consecutive test and results stay the same

Can you please try the patch at the end of this message? I'm wondering whether you're seeing the errors accumulating from the wrong min().

Quoted 7 lines
Quoted 4 lines

I still have the regression with the patch below.
The regression comes from the use runnable_load_avg to propagate. As load_avg becomes null at some point, it break the computation of share and the load_avg stay very low

That's surprising given that what the patch does is bringing the cgroup behavior closer to !cgroup behavior. It'd be great to be able

But it's also break load_avg which is used to calculate per cfs_rq share and this change generates the regression on my board

Quoted 5 lines

to reproduce the problem and trace it. It looks like the board is pretty standardized. Would the following be equivalent to the one you have?

http://a.co/f3dD1lm

Yes it's this board i have the previous version but it should not change the behavior

Quoted 4 lines

If so, I can just buy it, get your test image and repro it here and trace why the regression is happening with the setup. We might be hitting something else.

Quoted 6 lines

I have pushed my branch which includes v4.11-rc8 + your patches + some debug trace here:
https://git.linaro.org/people/vincent.guittot/kernel.git/log/?h=test-tejun-patches

and uploaded a trace_cmd's trace that shows the regression
http://people.linaro.org/~vincent.guittot/trace-tejun-patches

I have also uploaded the trace withour your patches so you can compare both:
http://people.linaro.org/~vincent.guittot/trace-v4.8-rc11

Quoted 11 lines

As an example, we can easily see arounf time stamp 94.826469 sec that cpu5 is idle while CPU2 and CPU3 share their time between several task.
This doesn't happens without your patch

Quoted 5 lines

Thanks.

--
tejun

maintainer
#45 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

In reply to Tejun Heo
Quoted 6 lines · Tejun Heo

We noticed that with cgroup CPU controller in use, the scheduling

Note the drastic increase in p99 scheduling latency. After investigation, it turned out that the update_sd_lb_stats(), which is used by load_balance() to pick the most loaded group, was often picking the wrong group. A CPU which has one schbench running and

Can the problem be on the load balance side instead ? and more precisely in the wakeup path ?
After looking at the trace, it seems that task placement happens at wake up path and if it fails to select the right idle cpu at wake up, you will have to wait for a load balance which is alreayd too late

Quoted 1 line

another queued wouldn't report the correspondingly higher

It will as load_avg includes the runnable_load_avg so whatever load is in runnable_load_avg will be in load_avg too. But at the contrary, runnable_load_avg will not have the blocked that is going to wake up soon in the case of schbench

One last thing, the load_avg of an idle CPU can stay blocked for a while (until a load balance happens that will update blocked load) and can be seen has "busy" whereas it is not. Could it be a reason of your problem ?

I have an ongoing patch to solve the problem at least partly if this can be a reason

Quoted 11 lines

weighted_cpuload() and get looked over as the target of load balancing.

weighted_cpuload() is the root cfs_rq's runnable_load_avg which is the sum of the load_avg of all queued sched_entities. Without cgroups or at the root cgroup, each task's load_avg contributes directly to the sum. When a task wakes up or goes to sleep, the change is immediately reflected on runnable_load_avg which in turn affects load balancing.

#else /* CONFIG_FAIR_GROUP_SCHED */

author
#46 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

Hello,

Quoted 6 lines · Vincent Guittot

On 24 April 2017 at 22:14, Tejun Heo <[email protected]> wrote:
Can the problem be on the load balance side instead ? and more precisely in the wakeup path ?
After looking at the trace, it seems that task placement happens at wake up path and if it fails to select the right idle cpu at wake up, you will have to wait for a load balance which is alreayd too late

Oh, I was tracing most of scheduler activities and the ratios of wakeups picking idle CPUs were about the same regardless of cgroup membership. I can confidently say that the latency issue that I'm seeing is from load balancer picking the wrong busiest CPU, which is not to say that there can be other problems.

Quoted 6 lines
Quoted 1 line

another queued wouldn't report the correspondingly higher

It will as load_avg includes the runnable_load_avg so whatever load is in runnable_load_avg will be in load_avg too. But at the contrary, runnable_load_avg will not have the blocked that is going to wake up soon in the case of schbench

Decaying contribution of blocked tasks don't affect the busiest CPU selection. Without cgroup, runnable_load_avg is immediately increased and decreased as tasks enter and leave the queue and otherwise we end up with CPUs which are idle when there are threads queued on different CPUs accumulating scheduling latencies.

The patch doesn't change how the busiest CPU is picked. It already uses runnable_load_avg. The change that cgroup causes is that it blocks updates to runnable_load_avg from newly scheduled or sleeping tasks.

The issue isn't about whether runnable_load_avg or load_avg should be used but the unexpected differences in the metrics that the load balancer uses depending on whether cgroup is used or not.

Quoted 4 lines

One last thing, the load_avg of an idle CPU can stay blocked for a while (until a load balance happens that will update blocked load) and can be seen has "busy" whereas it is not. Could it be a reason of your problem ?

AFAICS, the load balancer doesn't use load_avg.

Thanks.

Signature · 1 line
tejun
maintainer
#47 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

Quoted 10 lines · Tejun Heo

Hello,

Quoted 6 lines · Vincent Guittot

On 24 April 2017 at 22:14, Tejun Heo <[email protected]> wrote:
Can the problem be on the load balance side instead ? and more precisely in the wakeup path ?
After looking at the trace, it seems that task placement happens at wake up path and if it fails to select the right idle cpu at wake up, you will have to wait for a load balance which is alreayd too late

Quoted 5 lines

Oh, I was tracing most of scheduler activities and the ratios of wakeups picking idle CPUs were about the same regardless of cgroup membership. I can confidently say that the latency issue that I'm seeing is from load balancer picking the wrong busiest CPU, which is not to say that there can be other problems.

ok. Is there any trace that you can share ? your behavior seems different of mine

Quoted 14 lines
Quoted 7 lines
Quoted 2 lines

another queued wouldn't report the correspondingly higher

It will as load_avg includes the runnable_load_avg so whatever load is in runnable_load_avg will be in load_avg too. But at the contrary, runnable_load_avg will not have the blocked that is going to wake up soon in the case of schbench

Decaying contribution of blocked tasks don't affect the busiest CPU selection. Without cgroup, runnable_load_avg is immediately increased and decreased as tasks enter and leave the queue and otherwise we end up with CPUs which are idle when there are threads queued on different CPUs accumulating scheduling latencies.

Quoted 7 lines

The patch doesn't change how the busiest CPU is picked. It already uses runnable_load_avg. The change that cgroup causes is that it blocks updates to runnable_load_avg from newly scheduled or sleeping tasks.

The issue isn't about whether runnable_load_avg or load_avg should be used but the unexpected differences in the metrics that the load

I think that's the root of the problem. I explain a bit more my view on the other thread

Quoted 13 lines

balancer uses depending on whether cgroup is used or not.

Quoted 4 lines

One last thing, the load_avg of an idle CPU can stay blocked for a while (until a load balance happens that will update blocked load) and can be seen has "busy" whereas it is not. Could it be a reason of your problem ?

AFAICS, the load balancer doesn't use load_avg.

Thanks.

--
tejun

author
#48 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

Hello, Vincent.

Quoted 11 lines · Vincent Guittot
Quoted 10 lines · Tejun Heo

Hello,

Quoted 6 lines · Vincent Guittot

On 24 April 2017 at 22:14, Tejun Heo <[email protected]> wrote:
Can the problem be on the load balance side instead ? and more precisely in the wakeup path ?
After looking at the trace, it seems that task placement happens at wake up path and if it fails to select the right idle cpu at wake up, you will have to wait for a load balance which is alreayd too late

Quoted 8 lines
Quoted 5 lines

Oh, I was tracing most of scheduler activities and the ratios of wakeups picking idle CPUs were about the same regardless of cgroup membership. I can confidently say that the latency issue that I'm seeing is from load balancer picking the wrong busiest CPU, which is not to say that there can be other problems.

ok. Is there any trace that you can share ? your behavior seems different of mine

I'm attaching the debug patch. With your change (avg instead of runnable_avg), the following trace shows why it's wrong.

It's dumping a case where group A has a CPU w/ more than two schbench threads and B doesn't, but the load balancer is determining that B is loaded heavier.

dbg_odd: odd: dst=28 idle=2 brk=32 lbtgt=0-31 type=2
dbg_odd_dump: A: grp=1,17 w=2 avg=7.247 grp=8.337 sum=8.337 pertask=2.779
dbg_odd_dump: A: gcap=1.150 gutil=1.095 run=3 idle=0 gwt=2 type=2 nocap=1
dbg_odd_dump: A: CPU001: run=1 schb=1
dbg_odd_dump: A: Q001-asdf: w=1.000,l=0.525,u=0.513,r=0.527 run=1 hrun=1 tgs=100.000 tgw=17.266
dbg_odd_dump: A: Q001-asdf: schbench(153757C):w=1.000,l=0.527,u=0.514
dbg_odd_dump: A: Q001-/: w=5.744,l=2.522,u=0.520,r=3.067 run=1 hrun=1 tgs=1.000 tgw=0.000
dbg_odd_dump: A: Q001-/: asdf(C):w=5.744,l=3.017,u=0.521
dbg_odd_dump: A: CPU017: run=2 schb=2
dbg_odd_dump: A: Q017-asdf: w=2.000,l=0.989,u=0.966,r=0.988 run=2 hrun=2 tgs=100.000 tgw=17.266
dbg_odd_dump: A: Q017-asdf: schbench(153737C):w=1.000,l=0.493,u=0.482 schbench(153739):w=1.000,l=0.494,u=0.483
dbg_odd_dump: A: Q017-/: w=10.653,l=7.888,u=0.973,r=5.270 run=1 hrun=2 tgs=1.000 tgw=0.000
dbg_odd_dump: A: Q017-/: asdf(C):w=10.653,l=5.269,u=0.966
dbg_odd_dump: B: grp=14,30 w=2 avg=7.666 grp=8.819 sum=8.819 pertask=4.409
dbg_odd_dump: B: gcap=1.150 gutil=1.116 run=2 idle=0 gwt=2 type=2 nocap=1
dbg_odd_dump: B: CPU014: run=1 schb=1
dbg_odd_dump: B: Q014-asdf: w=1.000,l=1.004,u=0.970,r=0.492 run=1 hrun=1 tgs=100.000 tgw=17.266
dbg_odd_dump: B: Q014-asdf: schbench(153760C):w=1.000,l=0.491,u=0.476
dbg_odd_dump: B: Q014-/: w=5.605,l=11.146,u=0.970,r=5.774 run=1 hrun=1 tgs=1.000 tgw=0.000
dbg_odd_dump: B: Q014-/: asdf(C):w=5.605,l=5.766,u=0.970
dbg_odd_dump: B: CPU030: run=1 schb=1
dbg_odd_dump: B: Q030-asdf: w=1.000,l=0.538,u=0.518,r=0.558 run=1 hrun=1 tgs=100.000 tgw=17.266
dbg_odd_dump: B: Q030-asdf: schbench(153747C):w=1.000,l=0.537,u=0.516
dbg_odd_dump: B: Q030-/: w=5.758,l=3.186,u=0.541,r=3.044 run=1 hrun=1 tgs=1.000 tgw=0.000
dbg_odd_dump: B: Q030-/: asdf(C):w=5.758,l=3.092,u=0.516

You can notice that B's pertask weight is 4.409 which is way higher than A's 2.779, and this is from Q014-asdf's contribution to Q014-/ is twice as high as it should be. The root queue's runnable avg should only contain what's currently active but because we're scaling load avg which includes both active and blocked, we're ending up picking group B over A.

This shows up in the total number of times we pick the wrong queue and thus latency. I'm running the following script with the debug patch applied.

#!/bin/bash

date
cat /proc/self/cgroup

echo 1000 > /sys/module/fair/parameters/dbg_odd_nth echo 0 > /sys/module/fair/parameters/dbg_odd_cnt

~/schbench -m 2 -t 16 -s 10000 -c 15000 -r 30

cat /sys/module/fair/parameters/dbg_odd_cnt

With your patch applied, in the root cgroup,

Fri Apr 28 12:48:59 PDT 2017
0::/
Latency percentiles (usec)

	  50.0000th: 26
	  75.0000th: 63
	  90.0000th: 78
	  95.0000th: 88
	  *99.0000th: 707
	  99.5000th: 5096
	  99.9000th: 10352
	  min=0, max=13743

577

In the /asdf cgroup,

Fri Apr 28 13:19:53 PDT 2017
0::/asdf
Latency percentiles (usec)

	  50.0000th: 35
	  75.0000th: 67
	  90.0000th: 81
	  95.0000th: 98
	  *99.0000th: 2212
	  99.5000th: 4536
	  99.9000th: 11024
	  min=0, max=13026

1708

The last line is the number of times the load balancer picked a group w/o more than two schbench threads on a CPU over one w/. Some number of these are expected as there are other threads and there are some plays in all the calculations but propgating avg or not propgating at all significantly increases the count and latency.

Quoted 5 lines
Quoted 2 lines

The issue isn't about whether runnable_load_avg or load_avg should be used but the unexpected differences in the metrics that the load

I think that's the root of the problem. I explain a bit more my view on the other thread

So, when picking the busiest group, the only thing which matters is the queue's runnable_load_avg, which should approximate the sum of all on-queue loads on that CPU.

If we don't propagate or propagate load_avg, we're factoring in blocked avg of descendent cgroups into the root's runnable_load_avg which is obviously wrong.

We can argue whether overriding a cfs_rq se's load_avg to the scaled runnable_load_avg of the cfs_rq is the right way to go or we should introduce a separate channel to propagate runnable_load_avg; however, it's clear that we need to fix runnable_load_avg propagation one way or another.

The thing with cfs_rq se's load_avg is that, it isn't really used anywhere else AFAICS, so overriding it to the cfs_rq's runnable_load_avg isn't prettiest but doesn't really change anything.

Thanks.

Signature · 1 line
tejun
author
#49 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

Here's the debug patch.

The debug condition triggers when the load balancer picks a group w/o more than one schbench threads on a CPU over one w/.

/sys/module/fair/parameters/dbg_odd_cnt: resettable counter /sys/module/fair/parameters/dbg_odd_nth: dump group states on Nth
occurrence via trace_printk()

The load / weights are printed out so that NICE_0_LOAD is 1.000.

Thanks.

---
 kernel/sched/fair.c |  160 +++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 159 insertions(+), 1 deletion(-)
kernel/sched/fair.c +159 -1
@@ -32,11 +32,18 @@
 #include <linux/mempolicy.h>
 #include <linux/migrate.h>
 #include <linux/task_work.h>
+#include <linux/moduleparam.h>
 
 #include <trace/events/sched.h>
 
 #include "sched.h"
 
+static unsigned long dbg_odd_nth;
+static unsigned long dbg_odd_cnt;
+
+module_param(dbg_odd_nth, ulong, 0644);
+module_param(dbg_odd_cnt, ulong, 0644);
+
 /*
  * Targeted preemption latency for CPU-bound tasks:
  *
@@ -7413,6 +7420,149 @@ static inline void update_sg_lb_stats(st
 	sgs->group_type = group_classify(group, sgs);
 }
 
+static int count_schb(struct rq *rq)
+{
+	unsigned long flags;
+	struct task_struct *p;
+	int cnt = 0;
+
+	raw_spin_lock_irqsave(&rq->lock, flags);
+
+	list_for_each_entry(p, &rq->cfs_tasks, se.group_node)
+		if (!strncmp(p->comm, "schbench", 8))
+			cnt++;
+
+	raw_spin_unlock_irqrestore(&rq->lock, flags);
+
+	return cnt;
+}
+
+static bool sg_has_two_schb(struct sched_group *sg)
+{
+	int cpu;
+
+	for_each_cpu(cpu, sched_group_cpus(sg))
+		if (count_schb(cpu_rq(cpu)) >= 2)
+			return true;
+	return false;
+}
+
+static DEFINE_PER_CPU(char [PAGE_SIZE], odd_buf);
+
+#define lbw(x)	(int)((x) / NICE_0_LOAD), (int)(((x) % NICE_0_LOAD) * 1000 / NICE_0_LOAD)
+#define lba(x)	(int)((scale_load(x)) / NICE_0_LOAD), (int)(((scale_load(x)) % NICE_0_LOAD) * 1000 / NICE_0_LOAD)
+
+static int odd_append_se(struct sched_entity *se, const char *postfix,
+			 int cnt, char *buf, size_t size)
+{
+#define odd_append(fmt, args...)	do {				\
+	cnt += scnprintf(buf + cnt, size - cnt, fmt, ##args);		\
+	cnt = min_t(int, cnt, size);					\
+} while (0)
+
+	if (entity_is_task(se)) {
+		struct task_struct *task = task_of(se);
+		odd_append(" %s(%d%s)", task->comm, task->pid, postfix);
+	} else {
+		char nbuf[64];
+		cgroup_name(se->my_q->tg->css.cgroup, nbuf, sizeof(nbuf));
+		odd_append(" %s(%s)", nbuf, postfix);
+	}
+	odd_append(":w=%d.%03d,l=%d.%03d,u=%d.%03d",
+		   lbw(se->load.weight),
+		   lba(se->avg.load_avg),
+		   lba(se->avg.util_avg));
+
+	return cnt;
+}
+
+static void dbg_odd_dump(const char *pref,
+			 struct sched_group *sg, struct sg_lb_stats *sgs)
+{
+	int cpu;
+
+	trace_printk("%sgrp=%*pbl w=%u avg=%d.%03d grp=%d.%03d sum=%d.%03d pertask=%d.%03d\n", pref,
+		     cpumask_pr_args(sched_group_cpus(sg)), sg->group_weight,
+		     lba(sgs->avg_load), lba(sgs->group_load),
+		     lba(sgs->sum_weighted_load), lba(sgs->load_per_task));
+	trace_printk("%sgcap=%d.%03d gutil=%d.%03d run=%u idle=%u gwt=%u type=%d nocap=%d\n",
+		     pref,
+		     lba(sgs->group_capacity), lba(sgs->group_util),
+		     sgs->sum_nr_running, sgs->idle_cpus, sgs->group_weight,
+		     sgs->group_type, sgs->group_no_capacity);
+
+	for_each_cpu(cpu, sched_group_cpus(sg)) {
+		struct task_group *tg;
+		unsigned long flags;
+
+		trace_printk("%sCPU%03d: run=%u schb=%d\n", pref, cpu,
+			     cpu_rq(cpu)->nr_running, count_schb(cpu_rq(cpu)));
+
+		raw_spin_lock_irqsave(&cpu_rq(cpu)->lock, flags);
+
+		list_for_each_entry_rcu(tg, &task_groups, list) {
+			struct cfs_rq *cfs_rq = tg->cfs_rq[cpu];
+			char qname[32] = "root";
+			int depth = 0;
+			long tg_weight = 0, tg_shares = 0;
+			struct sched_entity *se;
+			char *buf = per_cpu_ptr(odd_buf, cpu);
+			int cnt;
+
+			if (!cfs_rq->nr_running)
+				continue;
+
+			if (cfs_rq->tg) {
+				cgroup_name(cfs_rq->tg->css.cgroup, qname, sizeof(qname));
+				if (cfs_rq->tg->se[cpu])
+					depth = cfs_rq->tg->se[cpu]->depth;
+				tg_weight = atomic_long_read(&cfs_rq->tg->load_avg);
+				tg_shares = cfs_rq->tg->shares;
+			}
+
+			trace_printk("%sQ%03d-%s@%d: w=%d.%03d,l=%d.%03d,u=%d.%03d,r=%d.%03d run=%u hrun=%u tgs=%d.%03d tgw=%d.%03d\n",
+				     pref, cpu, qname, depth,
+				     lbw(cfs_rq->load.weight),
+				     lba(cfs_rq->avg.load_avg),
+				     lba(cfs_rq->avg.util_avg),
+				     lba(cfs_rq->runnable_load_avg),
+				     cfs_rq->nr_running, cfs_rq->h_nr_running,
+				     lbw(tg_shares),
+				     lba(tg_weight));
+
+			buf[0] = '\0';
+			cnt = 0;
+
+			if (cfs_rq->curr)
+				cnt = odd_append_se(cfs_rq->curr, "C", cnt, buf, PAGE_SIZE);
+
+			for (se = __pick_first_entity(cfs_rq); se;
+			     se = __pick_next_entity(se))
+				cnt = odd_append_se(se, "", cnt, buf, PAGE_SIZE);
+
+			trace_printk("%sQ%03d-%s@%d: %s\n",
+				     pref, cpu, qname, depth, buf);
+		}
+
+		raw_spin_unlock_irqrestore(&cpu_rq(cpu)->lock, flags);
+	}
+}
+
+/* a has >= 2 dts, b doesn't */
+static void dbg_odd(struct lb_env *env,
+		    struct sched_group *sga, struct sg_lb_stats *sgsa,
+		    struct sched_group *sgb, struct sg_lb_stats *sgsb)
+{
+	if (dbg_odd_nth && (dbg_odd_cnt++ % dbg_odd_nth))
+		return;
+
+	trace_printk("odd: dst=%d idle=%d brk=%u lbtgt=%*pbl type=%d\n",
+		     env->dst_cpu, env->idle, env->loop_break,
+		     cpumask_pr_args(env->cpus), env->fbq_type);
+	dbg_odd_dump("A: ", sga, sgsa);
+	dbg_odd_dump("B: ", sgb, sgsb);
+}
+
 /**
  * update_sd_pick_busiest - return 1 on busiest group
  * @env: The load balancing environment.
@@ -7432,6 +7582,8 @@ static bool update_sd_pick_busiest(struc
 				   struct sg_lb_stats *sgs)
 {
 	struct sg_lb_stats *busiest = &sds->busiest_stat;
+	bool busiest_has_two = sds->busiest && sg_has_two_schb(sds->busiest);
+	bool sg_has_two = sg_has_two_schb(sg);
 
 	if (sgs->group_type > busiest->group_type)
 		return true;
@@ -7439,8 +7591,14 @@ static bool update_sd_pick_busiest(struc
 	if (sgs->group_type < busiest->group_type)
 		return false;
 
-	if (sgs->avg_load <= busiest->avg_load)
+	if (sgs->avg_load <= busiest->avg_load) {
+		if (sg_has_two && !busiest_has_two)
+			dbg_odd(env, sg, sgs, sds->busiest, busiest);
 		return false;
+	}
+
+	if (!sg_has_two && busiest_has_two)
+		dbg_odd(env, sds->busiest, busiest, sg, sgs);
 
 	if (!(env->sd->flags & SD_ASYM_CPUCAPACITY))
 		goto asym_packing;
maintainer
#50 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

In reply to Tejun Heo
Quoted 2 lines · Tejun Heo

I'm attaching the debug patch. With your change (avg instead of runnable_avg), the following trace shows why it's wrong.

Ah, OK. So you really want runnable_avg (and I understand why), which is rather unfortunate, since we have everything on load_avg.

So for shares, load_avg gives a more stable number. This is important since tg->load_avg is a global number, so computing it is expensive (and slow). Therefore more stable numbers are good.

Quoted 3 lines

The thing with cfs_rq se's load_avg is that, it isn't really used anywhere else AFAICS, so overriding it to the cfs_rq's runnable_load_avg isn't prettiest but doesn't really change anything.

You mean, consistently expressing a group's se->load.weight in terms of runnable_load_avg? See the above.

author
#51 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

Hello,

Quoted 11 lines · Peter Zijlstra
Quoted 2 lines · Tejun Heo

I'm attaching the debug patch. With your change (avg instead of runnable_avg), the following trace shows why it's wrong.

Ah, OK. So you really want runnable_avg (and I understand why), which is rather unfortunate, since we have everything on load_avg.

So for shares, load_avg gives a more stable number. This is important since tg->load_avg is a global number, so computing it is expensive (and slow). Therefore more stable numbers are good.

Quoted 6 lines
Quoted 3 lines

The thing with cfs_rq se's load_avg is that, it isn't really used anywhere else AFAICS, so overriding it to the cfs_rq's runnable_load_avg isn't prettiest but doesn't really change anything.

You mean, consistently expressing a group's se->load.weight in terms of runnable_load_avg? See the above.

I think you got this on the other thread but for clarity:

cfs_rq->avg.load_avg is used for share calculation and we want to keep it that way as the calcluation is expensive and rather decoupled across CPUs (the deviation can be quite a bit without the stability). But the group *se*->avg.load_avg is a separate thing which isn't really used anywhere except for as a propagation channel from group cfs_rq to its parent cfs_rq.

Thanks.

Signature · 1 line
tejun
maintainer
#52 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

In reply to Tejun Heo
Quoted 56 lines · Tejun Heo

Hello, Vincent.

Quoted 11 lines · Vincent Guittot
Quoted 10 lines · Tejun Heo

Hello,

Quoted 6 lines · Vincent Guittot

On 24 April 2017 at 22:14, Tejun Heo <[email protected]> wrote:
Can the problem be on the load balance side instead ? and more precisely in the wakeup path ?
After looking at the trace, it seems that task placement happens at wake up path and if it fails to select the right idle cpu at wake up, you will have to wait for a load balance which is alreayd too late

Quoted 8 lines
Quoted 5 lines

Oh, I was tracing most of scheduler activities and the ratios of wakeups picking idle CPUs were about the same regardless of cgroup membership. I can confidently say that the latency issue that I'm seeing is from load balancer picking the wrong busiest CPU, which is not to say that there can be other problems.

ok. Is there any trace that you can share ? your behavior seems different of mine

I'm attaching the debug patch. With your change (avg instead of runnable_avg), the following trace shows why it's wrong.

It's dumping a case where group A has a CPU w/ more than two schbench threads and B doesn't, but the load balancer is determining that B is loaded heavier.

dbg_odd: odd: dst=28 idle=2 brk=32 lbtgt=0-31 type=2
dbg_odd_dump: A: grp=1,17 w=2 avg=7.247 grp=8.337 sum=8.337 pertask=2.779
dbg_odd_dump: A: gcap=1.150 gutil=1.095 run=3 idle=0 gwt=2 type=2 nocap=1
dbg_odd_dump: A: CPU001: run=1 schb=1
dbg_odd_dump: A: Q001-asdf: w=1.000,l=0.525,u=0.513,r=0.527 run=1 hrun=1 tgs=100.000 tgw=17.266
dbg_odd_dump: A: Q001-asdf: schbench(153757C):w=1.000,l=0.527,u=0.514
dbg_odd_dump: A: Q001-/: w=5.744,l=2.522,u=0.520,r=3.067 run=1 hrun=1 tgs=1.000 tgw=0.000
dbg_odd_dump: A: Q001-/: asdf(C):w=5.744,l=3.017,u=0.521
dbg_odd_dump: A: CPU017: run=2 schb=2
dbg_odd_dump: A: Q017-asdf: w=2.000,l=0.989,u=0.966,r=0.988 run=2 hrun=2 tgs=100.000 tgw=17.266
dbg_odd_dump: A: Q017-asdf: schbench(153737C):w=1.000,l=0.493,u=0.482 schbench(153739):w=1.000,l=0.494,u=0.483
dbg_odd_dump: A: Q017-/: w=10.653,l=7.888,u=0.973,r=5.270 run=1 hrun=2 tgs=1.000 tgw=0.000
dbg_odd_dump: A: Q017-/: asdf(C):w=10.653,l=5.269,u=0.966
dbg_odd_dump: B: grp=14,30 w=2 avg=7.666 grp=8.819 sum=8.819 pertask=4.409
dbg_odd_dump: B: gcap=1.150 gutil=1.116 run=2 idle=0 gwt=2 type=2 nocap=1
dbg_odd_dump: B: CPU014: run=1 schb=1
dbg_odd_dump: B: Q014-asdf: w=1.000,l=1.004,u=0.970,r=0.492 run=1 hrun=1 tgs=100.000 tgw=17.266
dbg_odd_dump: B: Q014-asdf: schbench(153760C):w=1.000,l=0.491,u=0.476
dbg_odd_dump: B: Q014-/: w=5.605,l=11.146,u=0.970,r=5.774 run=1 hrun=1 tgs=1.000 tgw=0.000
dbg_odd_dump: B: Q014-/: asdf(C):w=5.605,l=5.766,u=0.970
dbg_odd_dump: B: CPU030: run=1 schb=1
dbg_odd_dump: B: Q030-asdf: w=1.000,l=0.538,u=0.518,r=0.558 run=1 hrun=1 tgs=100.000 tgw=17.266
dbg_odd_dump: B: Q030-asdf: schbench(153747C):w=1.000,l=0.537,u=0.516
dbg_odd_dump: B: Q030-/: w=5.758,l=3.186,u=0.541,r=3.044 run=1 hrun=1 tgs=1.000 tgw=0.000
dbg_odd_dump: B: Q030-/: asdf(C):w=5.758,l=3.092,u=0.516

Quoted 3 lines

You can notice that B's pertask weight is 4.409 which is way higher than A's 2.779, and this is from Q014-asdf's contribution to Q014-/ is twice as high as it should be. The root queue's runnable avg should

Are you sure that this is because of blocked load in group A ? it can be that Q014-asdf has already have to wait before running and its load still increase while runnable but not running .
IIUC your trace, group A has 2 running tasks and group B only one but load_balance selects B because of its sgs->avg_load being higher. But this can also happen even if runnable_load_avg of child cfs_rq was propagated correctly in group entity because we can have situation where a group A has only 1 task with higher load than 2 tasks on groupB and even if blocked load is not taken into account, and load_balance will select A.

IMHO, we should better improve load balance selection. I'm going to add smarter group selection in load_balance. that's something we should have already done but it was difficult without load/util_avg propagation. it should be doable now

Quoted 73 lines

only contain what's currently active but because we're scaling load avg which includes both active and blocked, we're ending up picking group B over A.

This shows up in the total number of times we pick the wrong queue and thus latency. I'm running the following script with the debug patch applied.

#!/bin/bash

date
cat /proc/self/cgroup

echo 1000 > /sys/module/fair/parameters/dbg_odd_nth echo 0 > /sys/module/fair/parameters/dbg_odd_cnt

~/schbench -m 2 -t 16 -s 10000 -c 15000 -r 30

cat /sys/module/fair/parameters/dbg_odd_cnt

With your patch applied, in the root cgroup,

Fri Apr 28 12:48:59 PDT 2017
0::/
Latency percentiles (usec)

          50.0000th: 26
          75.0000th: 63
          90.0000th: 78
          95.0000th: 88
          *99.0000th: 707
          99.5000th: 5096
          99.9000th: 10352
          min=0, max=13743

577

In the /asdf cgroup,

Fri Apr 28 13:19:53 PDT 2017
0::/asdf
Latency percentiles (usec)

          50.0000th: 35
          75.0000th: 67
          90.0000th: 81
          95.0000th: 98
          *99.0000th: 2212
          99.5000th: 4536
          99.9000th: 11024
          min=0, max=13026

1708

The last line is the number of times the load balancer picked a group w/o more than two schbench threads on a CPU over one w/. Some number of these are expected as there are other threads and there are some plays in all the calculations but propgating avg or not propgating at all significantly increases the count and latency.

Quoted 5 lines
Quoted 2 lines

The issue isn't about whether runnable_load_avg or load_avg should be used but the unexpected differences in the metrics that the load

I think that's the root of the problem. I explain a bit more my view on the other thread

So, when picking the busiest group, the only thing which matters is the queue's runnable_load_avg, which should approximate the sum of all on-queue loads on that CPU.

If we don't propagate or propagate load_avg, we're factoring in blocked avg of descendent cgroups into the root's runnable_load_avg which is obviously wrong.

Quoted 5 lines

We can argue whether overriding a cfs_rq se's load_avg to the scaled runnable_load_avg of the cfs_rq is the right way to go or we should introduce a separate channel to propagate runnable_load_avg; however, it's clear that we need to fix runnable_load_avg propagation one way or another.

The minimum would be to not break load_avg

Quoted 4 lines

The thing with cfs_rq se's load_avg is that, it isn't really used anywhere else AFAICS, so overriding it to the cfs_rq's runnable_load_avg isn't prettiest but doesn't really change anything.

load_avg is used for defining the share of each cfs_rq.

Quoted 5 lines

Thanks.

--
tejun

maintainer
#53 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

Hi Tejun,

Quoted 25 lines · Vincent Guittot
Quoted 24 lines · Tejun Heo

Hello, Vincent.

Quoted 19 lines · Vincent Guittot
Quoted 10 lines · Tejun Heo

Hello,

Quoted 6 lines · Vincent Guittot

On 24 April 2017 at 22:14, Tejun Heo <[email protected]> wrote:
Can the problem be on the load balance side instead ? and more precisely in the wakeup path ?
After looking at the trace, it seems that task placement happens at wake up path and if it fails to select the right idle cpu at wake up, you will have to wait for a load balance which is alreayd too late

Quoted 5 lines

Oh, I was tracing most of scheduler activities and the ratios of wakeups picking idle CPUs were about the same regardless of cgroup membership. I can confidently say that the latency issue that I'm seeing is from load balancer picking the wrong busiest CPU, which is not to say that there can be other problems.

ok. Is there any trace that you can share ? your behavior seems different of mine

[ snip]

Quoted 15 lines
Quoted 3 lines

You can notice that B's pertask weight is 4.409 which is way higher than A's 2.779, and this is from Q014-asdf's contribution to Q014-/ is twice as high as it should be. The root queue's runnable avg should

Are you sure that this is because of blocked load in group A ? it can be that Q014-asdf has already have to wait before running and its load still increase while runnable but not running .
IIUC your trace, group A has 2 running tasks and group B only one but load_balance selects B because of its sgs->avg_load being higher. But this can also happen even if runnable_load_avg of child cfs_rq was propagated correctly in group entity because we can have situation where a group A has only 1 task with higher load than 2 tasks on groupB and even if blocked load is not taken into account, and load_balance will select A.

Quoted 4 lines

IMHO, we should better improve load balance selection. I'm going to add smarter group selection in load_balance. that's something we should have already done but it was difficult without load/util_avg propagation. it should be doable now

Could you test the patch in load_balance below ?
If group is not overloaded which means that threads have all runtime they want, we select the cfs_rq according to the number of running threads instead

---
 kernel/sched/fair.c | 22 ++++++++++++++++++++--
 1 file changed, 20 insertions(+), 2 deletions(-)
kernel/sched/fair.c +20 -2
index a903276..87e3b77 100644
@@ -7069,7 +7069,8 @@ static unsigned long task_h_load(struct task_struct *p)
 /********** Helpers for find_busiest_group ************************/
 
 enum group_type {
-	group_other = 0,
+	group_idle = 0,
+	group_other,
 	group_imbalanced,
 	group_overloaded,
 };
@@ -7383,6 +7384,9 @@ group_type group_classify(struct sched_group *group,
 	if (sgs->group_no_capacity)
 		return group_overloaded;
 
+	if (!sgs->sum_nr_running)
+		return group_idle;
+
 	if (sg_imbalanced(group))
 		return group_imbalanced;
 
@@ -7476,8 +7480,19 @@ static bool update_sd_pick_busiest(struct lb_env *env,
 	if (sgs->group_type < busiest->group_type)
 		return false;
 
-	if (sgs->avg_load <= busiest->avg_load)
+	if (sgs->group_type == group_other) {
+		/*
+		 * The groups are not overloaded so there is enough cpu time
+		 * for all threads. In this case, takes the group with the
+		 * highest number of tasks per CPU in order to improve
+		 * scheduling latency
+		 */
+		if ((sgs->sum_nr_running * busiest->group_weight) <=
+				(busiest->sum_nr_running * sgs->group_weight))
+			return false;
+	} if (sgs->avg_load <= busiest->avg_load) {
 		return false;
+	}
 
 	if (!(env->sd->flags & SD_ASYM_CPUCAPACITY))
 		goto asym_packing;
@@ -7969,6 +7984,9 @@ static struct rq *find_busiest_queue(struct lb_env *env,
 		    !check_cpu_capacity(rq, env->sd))
 			continue;
 
+		if (!rq->cfs.h_nr_running)
+			continue;
+
 		/*
 		 * For the load comparisons with the other cpu's, consider
 		 * the weighted_cpuload() scaled with the cpu capacity, so
Signature · 1 line
2.7.4
Quoted 5 lines
Quoted 5 lines

only contain what's currently active but because we're scaling load avg which includes both active and blocked, we're ending up picking group B over A.

author
#54 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

Hello, Vincent.

Quoted 8 lines · Vincent Guittot
Quoted 4 lines

IMHO, we should better improve load balance selection. I'm going to add smarter group selection in load_balance. that's something we should have already done but it was difficult without load/util_avg propagation. it should be doable now

Could you test the patch in load_balance below ?
If group is not overloaded which means that threads have all runtime they want, we select the cfs_rq according to the number of running threads instead

So, this didn't help. Tried also w/ return true added on the else clause but that didn't help either.

Anyways, once debugged, the idea would work for this particular test case and in general we should avoid picking a CPU as the busiest if it doesn't have extra threads to give away; however, this isn't the proper fix for the identified problem and basing load balancing soley on the number of tasks is far more likely to be harmful than the other way around.

Thanks.

Signature · 1 line
tejun
author
#55 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

In reply to Vincent Guittot

Hello,

Quoted 26 lines · Vincent Guittot
Quoted 26 lines

dbg_odd: odd: dst=28 idle=2 brk=32 lbtgt=0-31 type=2
dbg_odd_dump: A: grp=1,17 w=2 avg=7.247 grp=8.337 sum=8.337 pertask=2.779
dbg_odd_dump: A: gcap=1.150 gutil=1.095 run=3 idle=0 gwt=2 type=2 nocap=1
dbg_odd_dump: A: CPU001: run=1 schb=1
dbg_odd_dump: A: Q001-asdf: w=1.000,l=0.525,u=0.513,r=0.527 run=1 hrun=1 tgs=100.000 tgw=17.266
dbg_odd_dump: A: Q001-asdf: schbench(153757C):w=1.000,l=0.527,u=0.514
dbg_odd_dump: A: Q001-/: w=5.744,l=2.522,u=0.520,r=3.067 run=1 hrun=1 tgs=1.000 tgw=0.000
dbg_odd_dump: A: Q001-/: asdf(C):w=5.744,l=3.017,u=0.521
dbg_odd_dump: A: CPU017: run=2 schb=2
dbg_odd_dump: A: Q017-asdf: w=2.000,l=0.989,u=0.966,r=0.988 run=2 hrun=2 tgs=100.000 tgw=17.266
dbg_odd_dump: A: Q017-asdf: schbench(153737C):w=1.000,l=0.493,u=0.482 schbench(153739):w=1.000,l=0.494,u=0.483
dbg_odd_dump: A: Q017-/: w=10.653,l=7.888,u=0.973,r=5.270 run=1 hrun=2 tgs=1.000 tgw=0.000
dbg_odd_dump: A: Q017-/: asdf(C):w=10.653,l=5.269,u=0.966
dbg_odd_dump: B: grp=14,30 w=2 avg=7.666 grp=8.819 sum=8.819 pertask=4.409
dbg_odd_dump: B: gcap=1.150 gutil=1.116 run=2 idle=0 gwt=2 type=2 nocap=1
dbg_odd_dump: B: CPU014: run=1 schb=1
dbg_odd_dump: B: Q014-asdf: w=1.000,l=1.004,u=0.970,r=0.492 run=1 hrun=1 tgs=100.000 tgw=17.266
dbg_odd_dump: B: Q014-asdf: schbench(153760C):w=1.000,l=0.491,u=0.476
dbg_odd_dump: B: Q014-/: w=5.605,l=11.146,u=0.970,r=5.774 run=1 hrun=1 tgs=1.000 tgw=0.000
dbg_odd_dump: B: Q014-/: asdf(C):w=5.605,l=5.766,u=0.970
dbg_odd_dump: B: CPU030: run=1 schb=1
dbg_odd_dump: B: Q030-asdf: w=1.000,l=0.538,u=0.518,r=0.558 run=1 hrun=1 tgs=100.000 tgw=17.266
dbg_odd_dump: B: Q030-asdf: schbench(153747C):w=1.000,l=0.537,u=0.516
dbg_odd_dump: B: Q030-/: w=5.758,l=3.186,u=0.541,r=3.044 run=1 hrun=1 tgs=1.000 tgw=0.000
dbg_odd_dump: B: Q030-/: asdf(C):w=5.758,l=3.092,u=0.516

Quoted 7 lines
Quoted 3 lines

You can notice that B's pertask weight is 4.409 which is way higher than A's 2.779, and this is from Q014-asdf's contribution to Q014-/ is twice as high as it should be. The root queue's runnable avg should

Are you sure that this is because of blocked load in group A ? it can be that Q014-asdf has already have to wait before running and its load still increase while runnable but not running .

This is with propagation enabled, so the only thing contributing to the root queue's runnable_load_avg is the load being propagated from Q014-asdf, which has twice high load avg than runnable. The past history doesn't matter for load balancing and without cgroup this blocked load wouldn't have contributed to root's runnable load avg. I don't think it can get much clearer.

Quoted 7 lines

IIUC your trace, group A has 2 running tasks and group B only one but load_balance selects B because of its sgs->avg_load being higher. But this can also happen even if runnable_load_avg of child cfs_rq was propagated correctly in group entity because we can have situation where a group A has only 1 task with higher load than 2 tasks on groupB and even if blocked load is not taken into account, and load_balance will select A.

Yes, it can happen with tasks w/ different weights. That's clearly not what's happening here. The load balancer is picking the wrong CPU far more frequently because the root queue's runnable load avg incorrectly includes blocked load avgs from nested cfs_rqs.

Quoted 4 lines

IMHO, we should better improve load balance selection. I'm going to add smarter group selection in load_balance. that's something we should have already done but it was difficult without load/util_avg propagation. it should be doable now

That's all well and great but let's fix a bug first; otherwise, we'd be papering over an existing issue with a new mechanism which is a bad idea for any code base which has to last.

Quoted 7 lines
Quoted 5 lines

We can argue whether overriding a cfs_rq se's load_avg to the scaled runnable_load_avg of the cfs_rq is the right way to go or we should introduce a separate channel to propagate runnable_load_avg; however, it's clear that we need to fix runnable_load_avg propagation one way or another.

The minimum would be to not break load_avg

Oh yeah, this I can understand. The proposed change is icky in that it forces group se->load_avg.avg to be runnable_load_avg of the corresponding group cfs_rq. We *can* introduce a separate channel, say, se->group_runnable_load_avg which is used to propagate runnable_load_avg; however, the thing is that we don't really use group se->load_avg.avg anywhere, so we might as well just override it.

I have a preliminary patch to introduce a separate field but it looks sad too because we end up calculating the load_avg and runnable_load_avg to propagate separately without actually using the former value anywhere.

Quoted 5 lines
Quoted 3 lines

The thing with cfs_rq se's load_avg is that, it isn't really used anywhere else AFAICS, so overriding it to the cfs_rq's runnable_load_avg isn't prettiest but doesn't really change anything.

load_avg is used for defining the share of each cfs_rq.

Each cfs_rq calculates its load_avg independently from the weight sum. The queued se's load_avgs don't affect cfs_rq's load_avg in any direct way. The only time the value is used is for propagation during migration; however, group se themselves never get migrated themselves and during propagation only deltas matter so the difference between load_avg and runnable_load_avg isn't gonna matter that much. In short, we don't really use group se's load_avg in any way significant.

Thanks.

Signature · 1 line
tejun
maintainer
#56 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

Hi Tejun,

Quoted 57 lines · Tejun Heo

Hello,

Quoted 26 lines · Vincent Guittot
Quoted 26 lines

dbg_odd: odd: dst=28 idle=2 brk=32 lbtgt=0-31 type=2
dbg_odd_dump: A: grp=1,17 w=2 avg=7.247 grp=8.337 sum=8.337 pertask=2.779
dbg_odd_dump: A: gcap=1.150 gutil=1.095 run=3 idle=0 gwt=2 type=2 nocap=1
dbg_odd_dump: A: CPU001: run=1 schb=1
dbg_odd_dump: A: Q001-asdf: w=1.000,l=0.525,u=0.513,r=0.527 run=1 hrun=1 tgs=100.000 tgw=17.266
dbg_odd_dump: A: Q001-asdf: schbench(153757C):w=1.000,l=0.527,u=0.514
dbg_odd_dump: A: Q001-/: w=5.744,l=2.522,u=0.520,r=3.067 run=1 hrun=1 tgs=1.000 tgw=0.000
dbg_odd_dump: A: Q001-/: asdf(C):w=5.744,l=3.017,u=0.521
dbg_odd_dump: A: CPU017: run=2 schb=2
dbg_odd_dump: A: Q017-asdf: w=2.000,l=0.989,u=0.966,r=0.988 run=2 hrun=2 tgs=100.000 tgw=17.266
dbg_odd_dump: A: Q017-asdf: schbench(153737C):w=1.000,l=0.493,u=0.482 schbench(153739):w=1.000,l=0.494,u=0.483
dbg_odd_dump: A: Q017-/: w=10.653,l=7.888,u=0.973,r=5.270 run=1 hrun=2 tgs=1.000 tgw=0.000
dbg_odd_dump: A: Q017-/: asdf(C):w=10.653,l=5.269,u=0.966
dbg_odd_dump: B: grp=14,30 w=2 avg=7.666 grp=8.819 sum=8.819 pertask=4.409
dbg_odd_dump: B: gcap=1.150 gutil=1.116 run=2 idle=0 gwt=2 type=2 nocap=1
dbg_odd_dump: B: CPU014: run=1 schb=1
dbg_odd_dump: B: Q014-asdf: w=1.000,l=1.004,u=0.970,r=0.492 run=1 hrun=1 tgs=100.000 tgw=17.266
dbg_odd_dump: B: Q014-asdf: schbench(153760C):w=1.000,l=0.491,u=0.476
dbg_odd_dump: B: Q014-/: w=5.605,l=11.146,u=0.970,r=5.774 run=1 hrun=1 tgs=1.000 tgw=0.000
dbg_odd_dump: B: Q014-/: asdf(C):w=5.605,l=5.766,u=0.970
dbg_odd_dump: B: CPU030: run=1 schb=1
dbg_odd_dump: B: Q030-asdf: w=1.000,l=0.538,u=0.518,r=0.558 run=1 hrun=1 tgs=100.000 tgw=17.266
dbg_odd_dump: B: Q030-asdf: schbench(153747C):w=1.000,l=0.537,u=0.516
dbg_odd_dump: B: Q030-/: w=5.758,l=3.186,u=0.541,r=3.044 run=1 hrun=1 tgs=1.000 tgw=0.000
dbg_odd_dump: B: Q030-/: asdf(C):w=5.758,l=3.092,u=0.516

Quoted 7 lines
Quoted 3 lines

You can notice that B's pertask weight is 4.409 which is way higher than A's 2.779, and this is from Q014-asdf's contribution to Q014-/ is twice as high as it should be. The root queue's runnable avg should

Are you sure that this is because of blocked load in group A ? it can be that Q014-asdf has already have to wait before running and its load still increase while runnable but not running .

This is with propagation enabled, so the only thing contributing to the root queue's runnable_load_avg is the load being propagated from Q014-asdf, which has twice high load avg than runnable. The past history doesn't matter for load balancing and without cgroup this blocked load wouldn't have contributed to root's runnable load avg. I don't think it can get much clearer.

Quoted 7 lines

IIUC your trace, group A has 2 running tasks and group B only one but load_balance selects B because of its sgs->avg_load being higher. But this can also happen even if runnable_load_avg of child cfs_rq was propagated correctly in group entity because we can have situation where a group A has only 1 task with higher load than 2 tasks on groupB and even if blocked load is not taken into account, and load_balance will select A.

Yes, it can happen with tasks w/ different weights. That's clearly not what's happening here. The load balancer is picking the wrong CPU far more frequently because the root queue's runnable load avg incorrectly includes blocked load avgs from nested cfs_rqs.

Quoted 8 lines
Quoted 4 lines

IMHO, we should better improve load balance selection. I'm going to add smarter group selection in load_balance. that's something we should have already done but it was difficult without load/util_avg propagation. it should be doable now

That's all well and great but let's fix a bug first; otherwise, we'd be papering over an existing issue with a new mechanism which is a bad idea for any code base which has to last.

runnable_load_avg is already a kind of fix and breaking load_avg seems worse than fixing load_balance

Quoted 7 lines
Quoted 7 lines
Quoted 6 lines

We can argue whether overriding a cfs_rq se's load_avg to the scaled runnable_load_avg of the cfs_rq is the right way to go or we should introduce a separate channel to propagate runnable_load_avg; however, it's clear that we need to fix runnable_load_avg propagation one way or another.

Quoted 8 lines
Quoted 1 line

The minimum would be to not break load_avg

Oh yeah, this I can understand. The proposed change is icky in that it forces group se->load_avg.avg to be runnable_load_avg of the corresponding group cfs_rq. We *can* introduce a separate channel, say, se->group_runnable_load_avg which is used to propagate runnable_load_avg; however, the thing is that we don't really use group se->load_avg.avg anywhere, so we might as well just override it.

We use load_avg for calculating a stable share and we want to use it more and more.
So breaking it because it's easier doesn't seems to be the right way to do IMHO

Quoted 24 lines

I have a preliminary patch to introduce a separate field but it looks sad too because we end up calculating the load_avg and runnable_load_avg to propagate separately without actually using the former value anywhere.

Quoted 5 lines
Quoted 3 lines

The thing with cfs_rq se's load_avg is that, it isn't really used anywhere else AFAICS, so overriding it to the cfs_rq's runnable_load_avg isn't prettiest but doesn't really change anything.

load_avg is used for defining the share of each cfs_rq.

Each cfs_rq calculates its load_avg independently from the weight sum. The queued se's load_avgs don't affect cfs_rq's load_avg in any direct way. The only time the value is used is for propagation during migration; however, group se themselves never get migrated themselves and during propagation only deltas matter so the difference between load_avg and runnable_load_avg isn't gonna matter that much. In short, we don't really use group se's load_avg in any way significant.

Thanks.

--
tejun

maintainer
#57 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

Quoted 3 lines · Vincent Guittot

We use load_avg for calculating a stable share and we want to use it more and more. So breaking it because it's easier doesn't seems to be the right way to do IMHO

So afaict we calculate group se->load.weight (aka shares, see calc_cfs_shares), using cfs_rq->avg.load_avg, which feeds into tg->load_avg through cfs_rq->tg_load_avg_contrib and cfs_rq->load.weight.

And cfs_rq->avg.load_avg is computed from cfs_rq->load.weight, which is \Sum se->load.weight.

OTOH group se->avg.load_avg isn't used much, which is TJ's point.

The only cases where group se->avg.load_avg are relevant to cfs_rq->avg.load are the cases I listed yesterday, group creation and group destruction. There we use the group se->avg.load_avg to manage the boundary conditions.

So with the proposed change to se->avg.load_avg we can have some (temporary) boundary effect when you destroy a lot of (previously active) cgroups.

Of course, it could be I overlooked something, in which case, please tell :-)

That said, I agree it would be nice to entirely get rid of runnable_avg, but that is a much larger change and would require a lot more work. I don't immediately see why we can't fix the thing now and then work on removing runnable_load_avg later.

Of course, we should not regress either, I'll go read up on that part.

maintainer
#58 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

Quoted 22 lines · Peter Zijlstra
Quoted 3 lines · Vincent Guittot

We use load_avg for calculating a stable share and we want to use it more and more. So breaking it because it's easier doesn't seems to be the right way to do IMHO

So afaict we calculate group se->load.weight (aka shares, see calc_cfs_shares), using cfs_rq->avg.load_avg, which feeds into tg->load_avg through cfs_rq->tg_load_avg_contrib and cfs_rq->load.weight.

And cfs_rq->avg.load_avg is computed from cfs_rq->load.weight, which is \Sum se->load.weight.

OTOH group se->avg.load_avg isn't used much, which is TJ's point.

The only cases where group se->avg.load_avg are relevant to cfs_rq->avg.load are the cases I listed yesterday, group creation and group destruction. There we use the group se->avg.load_avg to manage the boundary conditions.

Quoted 7 lines

So with the proposed change to se->avg.load_avg we can have some (temporary) boundary effect when you destroy a lot of (previously active) cgroups.

Of course, it could be I overlooked something, in which case, please tell :-)

That's mainly based on the regression i see on my platform. I haven't find the root cause of the regression but it's there which means that using group_entity's load_avg to propagate child cfs_rq runnable_load_avg breaks something

Quoted 6 lines

That said, I agree it would be nice to entirely get rid of runnable_avg, but that is a much larger change and would require a lot more work. I don't immediately see why we can't fix the thing now and then work on removing runnable_load_avg later.

What propose Tejun is to break the group's load_avg and make it follows child cfs_rq's runnable_load_avg instead of child cfs_rq's load_avg so it will be difficult if not possible to try to move load_balance on load_avg and remove runnable_load_avg later on if load_avg doesn't work anymore as expected. So keeping group's load_avg working correctly seems a key point
Then, we know that we still have wrong behavior with runnable_load_avg when running task's load are really different. so it fixes part of wider problem IMO

Quoted 3 lines

Of course, we should not regress either, I'll go read up on that part.

maintainer
#59 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

Quoted 9 lines · Vincent Guittot
Quoted 2 lines · Peter Zijlstra

Of course, it could be I overlooked something, in which case, please tell :-)

That's mainly based on the regression i see on my platform. I haven't find the root cause of the regression but it's there which means that using group_entity's load_avg to propagate child cfs_rq runnable_load_avg breaks something

(as mentioned on IRC)

Right.. so looking through the code, (group) se->avg.load_avg is used in effective_load() (and thereby wake_affine()) and update_cfs_rq_h_load() (and therefore task_h_load()).

So changing it will affect those two functions, which could well lead to your regression.

author
#60 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

Quoted 11 lines · Peter Zijlstra
Quoted 9 lines · Vincent Guittot
Quoted 2 lines · Peter Zijlstra

Of course, it could be I overlooked something, in which case, please tell :-)

That's mainly based on the regression i see on my platform. I haven't find the root cause of the regression but it's there which means that using group_entity's load_avg to propagate child cfs_rq runnable_load_avg breaks something

Quoted 8 lines

(as mentioned on IRC)

Right.. so looking through the code, (group) se->avg.load_avg is used in effective_load() (and thereby wake_affine()) and update_cfs_rq_h_load() (and therefore task_h_load()).

So changing it will affect those two functions, which could well lead to your regression.

Ah, okay, that makes sense. I'll try to finish the patch to propagate runnable without affecting group se->avg.load_avg. BTW, Vincent, did you boost the weight of the cgroup when you were testing? If you put schbench inside a cgroup and have some base load, it is actually expected to show worse latency. You need to give higher weight to the cgroup matching the number of active threads (to be accruate, scaled by duty cycle but shouldn't matter too much in practice).

Thanks.

Signature · 1 line
tejun
maintainer
#61 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

Quoted 18 lines · Tejun Heo
Quoted 17 lines · Peter Zijlstra
Quoted 9 lines · Vincent Guittot
Quoted 2 lines · Peter Zijlstra

Of course, it could be I overlooked something, in which case, please tell :-)

That's mainly based on the regression i see on my platform. I haven't find the root cause of the regression but it's there which means that using group_entity's load_avg to propagate child cfs_rq runnable_load_avg breaks something

(as mentioned on IRC)

Right.. so looking through the code, (group) se->avg.load_avg is used in effective_load() (and thereby wake_affine()) and update_cfs_rq_h_load() (and therefore task_h_load()).

Quoted 6 lines
Quoted 2 lines

So changing it will affect those two functions, which could well lead to your regression.

Ah, okay, that makes sense. I'll try to finish the patch to propagate runnable without affecting group se->avg.load_avg. BTW, Vincent, did you boost the weight of the cgroup when you were testing? If you put

I use default group weight

Quoted 4 lines

schbench inside a cgroup and have some base load, it is actually expected to show worse latency. You need to give higher weight to the cgroup matching the number of active threads (to be accruate, scaled by duty cycle but shouldn't matter too much in practice).

I don't have to change anything cgroup weight with mainline to get good number which means that the base load which is quite close to null, is probably not the problem

Quoted 5 lines

Thanks.

--
tejun

author
#62 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

Hello,

Quoted 8 lines · Vincent Guittot
Quoted 4 lines

schbench inside a cgroup and have some base load, it is actually expected to show worse latency. You need to give higher weight to the cgroup matching the number of active threads (to be accruate, scaled by duty cycle but shouldn't matter too much in practice).

I don't have to change anything cgroup weight with mainline to get good number which means that the base load which is quite close to null, is probably not the problem

So, while that *could* be the case, it could also be the baseline incorrectly favoring the nested cfs_rqs over other tasks because of the nested runnables being inflated with blocked load avgs. I think it'd be a good idea to test with matching weight to put things on the even ground.

Thanks.

Signature · 1 line
tejun
maintainer
#63 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

Hi Tejun,

Quoted 12 lines · Tejun Heo

Hello,

Quoted 8 lines · Vincent Guittot
Quoted 4 lines

schbench inside a cgroup and have some base load, it is actually expected to show worse latency. You need to give higher weight to the cgroup matching the number of active threads (to be accruate, scaled by duty cycle but shouldn't matter too much in practice).

I don't have to change anything cgroup weight with mainline to get good number which means that the base load which is quite close to null, is probably not the problem

Quoted 5 lines

So, while that *could* be the case, it could also be the baseline incorrectly favoring the nested cfs_rqs over other tasks because of the nested runnables being inflated with blocked load avgs. I think it'd be a good idea to test with matching weight to put things on the even ground.

In the trace i have uploaded, you will see that regressions happen whereas there is no other runnable threads around so it's not a matter of background activities that disturbs schbench

Thanks
Vincent

Quoted 5 lines

Thanks.

--
tejun

author
#64 lore raw

Re: [PATCH 2/2] sched/fair: Always propagate runnable_load_avg

Hello, Vincent.

Quoted 3 lines · Vincent Guittot

In the trace i have uploaded, you will see that regressions happen whereas there is no other runnable threads around so it's not a matter of background activities that disturbs schbench

Understood, yeah, I'm almost done with the patches to propagate runnable w/o disturbing load_avg. Will post them soon.

Thanks.

Signature · 1 line
tejun
author
#65 lore raw

[PATCH 3/2] sched/fair: Skip __update_load_avg() on cfs_rq sched_entities

In reply to Tejun Heo

Now that a cfs_rq sched_entity's load_avg always gets propagated from the associated cfs_rq, there's no point in calling __update_load_avg() on it. The two mechanisms compete with each other and we'd be always using a value close to the propagated one anyway.

Skip __update_load_avg() for cfs_rq sched_entities. Also, relocate propagate_entity_load_avg() to signify that propagation is the counterpart to __update_load_avg() for cfs_rq sched_entities. This puts the propagation before update_cfs_rq_load_avg() which shouldn't disturb anything.

Cc Vincent Guittot <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Mike Galbraith <[email protected]>
Cc Paul Turner <[email protected]>

---
Hello,

A follow-up patch. This removes __update_load_avg() on cfs_rq se's as the value is now constantly kept in sync from cfs_rq. The patch doesn't cause any noticable changes in tets.

Thanks.

 kernel/sched/fair.c |   16 +++++++++-------
 1 file changed, 9 insertions(+), 7 deletions(-)
kernel/sched/fair.c +9 -7
@@ -3293,20 +3293,22 @@ static inline void update_load_avg(struc
 	u64 now = cfs_rq_clock_task(cfs_rq);
 	struct rq *rq = rq_of(cfs_rq);
 	int cpu = cpu_of(rq);
-	int decayed;
+	int decayed = 0;
 
 	/*
 	 * Track task load average for carrying it to new CPU after migrated, and
 	 * track group sched_entity load average for task_h_load calc in migration
 	 */
-	if (se->avg.last_update_time && !(flags & SKIP_AGE_LOAD)) {
-		__update_load_avg(now, cpu, &se->avg,
-			  se->on_rq * scale_load_down(se->load.weight),
-			  cfs_rq->curr == se, NULL);
+	if (entity_is_task(se)) {
+		if (se->avg.last_update_time && !(flags & SKIP_AGE_LOAD))
+			__update_load_avg(now, cpu, &se->avg,
+					  se->on_rq * scale_load_down(se->load.weight),
+					  cfs_rq->curr == se, NULL);
+	} else {
+		decayed |= propagate_entity_load_avg(se);
 	}
 
-	decayed  = update_cfs_rq_load_avg(now, cfs_rq, true);
-	decayed |= propagate_entity_load_avg(se);
+	decayed |= update_cfs_rq_load_avg(now, cfs_rq, true);
 
 	if (decayed && (flags & UPDATE_TG))
 		update_tg_load_avg(cfs_rq, 0);
maintainer
#66 lore raw

Re: [PATCH 3/2] sched/fair: Skip __update_load_avg() on cfs_rq sched_entities

kernel/sched/fair.c static inline void update_load_avg(struc · line 3306

Quoted 9 lines · Tejun Heo
kernel/sched/fair.c +5 -4
-	if (se->avg.last_update_time && !(flags & SKIP_AGE_LOAD)) {
-		__update_load_avg(now, cpu, &se->avg,
-			  se->on_rq * scale_load_down(se->load.weight),
-			  cfs_rq->curr == se, NULL);
+	if (entity_is_task(se)) {
+		if (se->avg.last_update_time && !(flags & SKIP_AGE_LOAD))
+			__update_load_avg(now, cpu, &se->avg,
+					  se->on_rq * scale_load_down(se->load.weight),
+					  cfs_rq->curr == se, NULL);

I've not looked at these patches yet, but you've been patching old code. __update_load_avg() no longer exists (the conversion shouldn't be too hard, its mostly been a restructure/rename thing).

author
#67 lore raw

Re: [PATCH 3/2] sched/fair: Skip __update_load_avg() on cfs_rq sched_entities

Hello, Peter.

Quoted 14 lines · Peter Zijlstra

kernel/sched/fair.c static inline void update_load_avg(struc · line 3306

Quoted 9 lines · Tejun Heo
kernel/sched/fair.c +5 -4
-	if (se->avg.last_update_time && !(flags & SKIP_AGE_LOAD)) {
-		__update_load_avg(now, cpu, &se->avg,
-			  se->on_rq * scale_load_down(se->load.weight),
-			  cfs_rq->curr == se, NULL);
+	if (entity_is_task(se)) {
+		if (se->avg.last_update_time && !(flags & SKIP_AGE_LOAD))
+			__update_load_avg(now, cpu, &se->avg,
+					  se->on_rq * scale_load_down(se->load.weight),
+					  cfs_rq->curr == se, NULL);

I've not looked at these patches yet, but you've been patching old code. __update_load_avg() no longer exists (the conversion shouldn't be too hard, its mostly been a restructure/rename thing).

Ah, sure. The patchset still being RFC, I wanted to post the version I was working with. If you want the patchset refreshed now, please let me know.

Thanks.

Signature · 1 line
tejun
author
#68 lore raw

Re: [PATCH 3/2] sched/fair: Skip __update_load_avg() on cfs_rq sched_entities

In reply to Tejun Heo
Quoted 10 lines · Tejun Heo

Now that a cfs_rq sched_entity's load_avg always gets propagated from the associated cfs_rq, there's no point in calling __update_load_avg() on it. The two mechanisms compete with each other and we'd be always using a value close to the propagated one anyway.

Skip __update_load_avg() for cfs_rq sched_entities. Also, relocate propagate_entity_load_avg() to signify that propagation is the counterpart to __update_load_avg() for cfs_rq sched_entities. This puts the propagation before update_cfs_rq_load_avg() which shouldn't disturb anything.

Please ignore this patch. As we don't propagate on decays, we still need __update_load_avg() on runanble_load_avg so that it can decay on its own.

Thanks.

Signature · 1 line
tejun