Skip to contentSkip to conversation

sched/fair: A bit of a cgroup/PELT overhaul (again)..

RFC PATCH In review Peter Zijlstra 4 participants 24 messages May 12, 2017 – Sep 29, 2017 Scheduler

lore
Share & tools
lore

Peter Zijlstra

author maintainer
#0 lore raw

cover sched/fair: A bit of a cgroup/PELT overhaul (again)..

Hi all,

So after staring at all that PELT stuff and working my way through it again:

https://lkml.kernel.org/r/[email protected]

I started doing some patches to fix some of the identified broken.

So here are a few too many patches that do:

- fix 'reweight_entity' to instantly propagate the change in se->load.weight.

- rewrite/fix the propagate on migrate (attach/detach)

- introduce the hierarchical runnable_load_avg, as proposed by Tejun.

- synchronous detach for runnable migrates

- aligns the PELT windows between a cfs_rq and all its se's

- deals with random fallout from the above (some of this needs folding back and reordering, but its all well past the point I should post this anyway).

IIRC pjt recently mentioned the reweight_entity thing, and I have very vague memories he once talked about the window alignment thing -- which I only remembered after (very painfully) having discovered I really needed that.

In any case, the reason I did the reweight_entity thing first, is because I feel that is the right place to also propagate the hierarchical runnable_load, as that is the natural place where a group's cfs_rq is coupled to its sched_entity.

And the hierachical runnable_load needs that coupling. TJ did it by hijacking the attach/detach migrate code, which I didn't much like. In any case, all that got me looking at said attach/detach migrate code and find pain. So I went and fixed that too.

Much thanks to Vincent and Dietmar for poking at early versions and reporting failure and comments.

This still hasn't had a lot of testing, but its not obviously insane anymore for the few tests we did do on it. Thread carefully though, a lot of code changed.

This can also be found here:

git://git.kernel.org/pub/scm/linux/kernel/git/peterz/queue.git sched/experimental

(my git tree is unsable and gets rebased a _lot_)

---
 include/linux/sched.h |    3 
 kernel/sched/debug.c  |   18 -
 kernel/sched/fair.c   |  811 +++++++++++++++++++++++++++++++-------------------
 kernel/sched/sched.h  |   19 -
 4 files changed, 547 insertions(+), 304 deletions(-)
author maintainer
#1 lore raw

RFC PATCH 1/14 sched/fair: Clean up calc_cfs_shares()

For consistencies sake, we should have only a single reading of tg->shares.

---
 kernel/sched/fair.c |   31 ++++++++++++-------------------
 1 file changed, 12 insertions(+), 19 deletions(-)
kernel/sched/fair.c +12 -19
@@ -2633,9 +2633,12 @@ account_entity_dequeue(struct cfs_rq *cf
 
 #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)
 {
-	long tg_weight, load, shares;
+	long tg_weight, tg_shares, load, shares;
+	struct task_group *tg = cfs_rq->tg;
+
+	tg_shares = READ_ONCE(tg->shares);
 
 	/*
 	 * This really should be: cfs_rq->avg.load_avg, but instead we use
@@ -2650,7 +2653,7 @@ static long calc_cfs_shares(struct cfs_r
 	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;
 
@@ -2666,17 +2669,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;
-}
-# 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 */
 
@@ -2701,7 +2694,6 @@ static inline int throttled_hierarchy(st
 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)
@@ -2710,13 +2702,14 @@ static void update_cfs_shares(struct sch
 	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);
 #endif
-	shares = calc_cfs_shares(cfs_rq, tg);
 
 	reweight_entity(cfs_rq_of(se), se, shares);
 }
author maintainer
#3 lore raw

RFC PATCH 2/14 sched/fair: Add comment to calc_cfs_shares()

In reply to Peter Zijlstra

Explain the magic equation in calc_cfs_shares() a bit better.

---
 kernel/sched/fair.c |   61 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 61 insertions(+)
kernel/sched/fair.c +61 -0
@@ -2633,6 +2633,67 @@ account_entity_dequeue(struct cfs_rq *cf
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
 # ifdef CONFIG_SMP
+/*
+ * All this does is approximate the hierarchical proportion which includes that
+ * global sum we all love to hate.
+ *
+ * That is, the weight of a group entity, is the proportional share of the
+ * group weight based on the group runqueue weights. That is:
+ *
+ *                     tg->weight * grq->load.weight
+ *   ge->load.weight = -----------------------------               (1)
+ *       		  \Sum grq->load.weight
+ *
+ * Now, because computing that sum is prohibitively expensive to compute (been
+ * there, done that) we approximate it with this average stuff. The average
+ * moves slower and therefore the approximation is cheaper and more stable.
+ *
+ * So instead of the above, we substitute:
+ *
+ *   grq->load.weight -> grq->avg.load_avg                         (2)
+ *
+ * which yields the following:
+ *
+ *                     tg->weight * grq->avg.load_avg
+ *   ge->load.weight = ------------------------------              (3)
+ *       		      tg->load_avg
+ *
+ * Where: tg->load_avg ~= \Sum grq->avg.load_avg
+ *
+ * That is shares_avg, and it is right (given the approximation (2)).
+ *
+ * The problem with it is that because the average is slow -- it was designed
+ * to be exactly that of course -- this leads to transients in boundary
+ * conditions. In specific, the case where the group was idle and we start the
+ * one task. It takes time for our CPU's grq->avg.load_avg to build up,
+ * yielding bad latency etc..
+ *
+ * Now, in that special case (1) reduces to:
+ *
+ *                     tg->weight * grq->load.weight
+ *   ge->load.weight = ----------------------------- = tg>weight   (4)
+ *       		  grp->load.weight
+ *
+ * That is, the sum collapses because all other CPUs are idle; the UP scenario.
+ *
+ * So what we do is modify our approximation (3) to approach (4) in the (near)
+ * UP case, like:
+ *
+ *   ge->load.weight =
+ *
+ *              tg->weight * grq->load.weight
+ *     ---------------------------------------------------         (5)
+ *     tg->load_avg - grq->avg.load_avg + grq->load.weight
+ *
+ *
+ * And that is shares_weight and is icky. In the (near) UP case it approaches
+ * (4) while in the normal case it approaches (3). It consistently
+ * overestimates the ge->load.weight and therefore:
+ *
+ *   \Sum ge->load.weight >= tg->weight
+ *
+ * hence icky!
+ */
 static long calc_cfs_shares(struct cfs_rq *cfs_rq)
 {
 	long tg_weight, tg_shares, load, shares;
author maintainer
#4 lore raw

RFC PATCH 3/14 sched/fair: Remove se->load.weight from se->avg.load_sum

In reply to Peter Zijlstra

Remove the load from the load_sum for sched_entities, basically turning load_sum into runnable_sum. This prepares for better reweighting of group entities.

Since we now have different rules for computing load_avg, split ___update_load_avg() into two parts, ___update_load_sum() and ___update_load_avg().

So for se:

___update_load_sum(.weight = 1)
___upate_load_avg(.weight = se->load.weight)

and for cfs_rq:

___update_load_sum(.weight = cfs_rq->load.weight) ___upate_load_avg(.weight = 1)

Since the primary consumable is load_avg, most things will not be affected. Only those few sites that initialize/modify load_sum need attention.

---
 kernel/sched/fair.c |   91 ++++++++++++++++++++++++++++++++++++----------------
 1 file changed, 64 insertions(+), 27 deletions(-)
kernel/sched/fair.c +64 -27
@@ -744,7 +744,7 @@ void init_entity_runnable_average(struct
 	 */
 	if (entity_is_task(se))
 		sa->load_avg = scale_load_down(se->load.weight);
-	sa->load_sum = sa->load_avg * LOAD_AVG_MAX;
+	sa->load_sum = LOAD_AVG_MAX;
 	/*
 	 * At this point, util_avg won't be used in select_task_rq_fair anyway
 	 */
@@ -1967,7 +1967,7 @@ static u64 numa_get_avg_runtime(struct t
 		delta = runtime - p->last_sum_exec_runtime;
 		*period = now - p->last_task_numa_placement;
 	} else {
-		delta = p->se.avg.load_sum / p->se.load.weight;
+		delta = p->se.avg.load_sum;
 		*period = LOAD_AVG_MAX;
 	}
 
@@ -2872,8 +2872,8 @@ accumulate_sum(u64 delta, int cpu, struc
  *            = u_0 + u_1*y + u_2*y^2 + ... [re-labeling u_i --> u_{i+1}]
  */
 static __always_inline int
-___update_load_avg(u64 now, int cpu, struct sched_avg *sa,
-		  unsigned long weight, int running, struct cfs_rq *cfs_rq)
+___update_load_sum(u64 now, int cpu, struct sched_avg *sa,
+		   unsigned long weight, int running, struct cfs_rq *cfs_rq)
 {
 	u64 delta;
 
@@ -2907,39 +2907,80 @@ ___update_load_avg(u64 now, int cpu, str
 	if (!accumulate_sum(delta, cpu, sa, weight, running, cfs_rq))
 		return 0;
 
+	return 1;
+}
+
+static __always_inline void
+___update_load_avg(struct sched_avg *sa, unsigned long weight, struct cfs_rq *cfs_rq)
+{
+	u32 divider = LOAD_AVG_MAX - 1024 + sa->period_contrib;
+
 	/*
 	 * Step 2: update *_avg.
 	 */
-	sa->load_avg = div_u64(sa->load_sum, LOAD_AVG_MAX - 1024 + sa->period_contrib);
+	sa->load_avg = div_u64(weight * sa->load_sum, divider);
 	if (cfs_rq) {
 		cfs_rq->runnable_load_avg =
-			div_u64(cfs_rq->runnable_load_sum, LOAD_AVG_MAX - 1024 + sa->period_contrib);
+			div_u64(cfs_rq->runnable_load_sum, divider);
 	}
-	sa->util_avg = sa->util_sum / (LOAD_AVG_MAX - 1024 + sa->period_contrib);
+	sa->util_avg = sa->util_sum / divider;
+}
 
-	return 1;
+/*
+ * XXX we want to get rid of this helper and use the full load resolution.
+ */
+static inline long se_weight(struct sched_entity *se)
+{
+	return scale_load_down(se->load.weight);
 }
 
+/*
+ * sched_entity:
+ *
+ *   load_sum := runnable_sum
+ *   load_avg = se_weight(se) * runnable_avg
+ *
+ * cfq_rs:
+ *
+ *   load_sum = \Sum se_weight(se) * se->avg.load_sum
+ *   load_avg = \Sum se->avg.load_avg
+ */
+
 static int
 __update_load_avg_blocked_se(u64 now, int cpu, struct sched_entity *se)
 {
-	return ___update_load_avg(now, cpu, &se->avg, 0, 0, NULL);
+	if (___update_load_sum(now, cpu, &se->avg, 0, 0, NULL)) {
+		___update_load_avg(&se->avg, se_weight(se), NULL);
+		return 1;
+	}
+
+	return 0;
 }
 
 static int
 __update_load_avg_se(u64 now, int cpu, struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
-	return ___update_load_avg(now, cpu, &se->avg,
-				  se->on_rq * scale_load_down(se->load.weight),
-				  cfs_rq->curr == se, NULL);
+	if (___update_load_sum(now, cpu, &se->avg, !!se->on_rq,
+				cfs_rq->curr == se, NULL)) {
+
+		___update_load_avg(&se->avg, se_weight(se), NULL);
+		return 1;
+	}
+
+	return 0;
 }
 
 static int
 __update_load_avg_cfs_rq(u64 now, int cpu, struct cfs_rq *cfs_rq)
 {
-	return ___update_load_avg(now, cpu, &cfs_rq->avg,
-			scale_load_down(cfs_rq->load.weight),
-			cfs_rq->curr != NULL, cfs_rq);
+	if (___update_load_sum(now, cpu, &cfs_rq->avg,
+				scale_load_down(cfs_rq->load.weight),
+				cfs_rq->curr != NULL, cfs_rq)) {
+		___update_load_avg(&cfs_rq->avg, 1, cfs_rq);
+		return 1;
+	}
+
+	return 0;
 }
 
 /*
@@ -3110,7 +3151,7 @@ update_tg_cfs_load(struct cfs_rq *cfs_rq
 
 	/* Set new sched_entity's load */
 	se->avg.load_avg = load;
-	se->avg.load_sum = se->avg.load_avg * LOAD_AVG_MAX;
+	se->avg.load_sum = LOAD_AVG_MAX;
 
 	/* Update parent cfs_rq load */
 	add_positive(&cfs_rq->avg.load_avg, delta);
@@ -3340,7 +3381,7 @@ static void attach_entity_load_avg(struc
 {
 	se->avg.last_update_time = cfs_rq->avg.last_update_time;
 	cfs_rq->avg.load_avg += se->avg.load_avg;
-	cfs_rq->avg.load_sum += se->avg.load_sum;
+	cfs_rq->avg.load_sum += se_weight(se) * se->avg.load_sum;
 	cfs_rq->avg.util_avg += se->avg.util_avg;
 	cfs_rq->avg.util_sum += se->avg.util_sum;
 	set_tg_cfs_propagate(cfs_rq);
@@ -3360,7 +3401,7 @@ static void detach_entity_load_avg(struc
 {
 
 	sub_positive(&cfs_rq->avg.load_avg, se->avg.load_avg);
-	sub_positive(&cfs_rq->avg.load_sum, se->avg.load_sum);
+	sub_positive(&cfs_rq->avg.load_sum, se_weight(se) * se->avg.load_sum);
 	sub_positive(&cfs_rq->avg.util_avg, se->avg.util_avg);
 	sub_positive(&cfs_rq->avg.util_sum, se->avg.util_sum);
 	set_tg_cfs_propagate(cfs_rq);
@@ -3372,12 +3413,10 @@ static void detach_entity_load_avg(struc
 static inline void
 enqueue_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
-	struct sched_avg *sa = &se->avg;
-
-	cfs_rq->runnable_load_avg += sa->load_avg;
-	cfs_rq->runnable_load_sum += sa->load_sum;
+	cfs_rq->runnable_load_avg += se->avg.load_avg;
+	cfs_rq->runnable_load_sum += se_weight(se) * se->avg.load_sum;
 
-	if (!sa->last_update_time) {
+	if (!se->avg.last_update_time) {
 		attach_entity_load_avg(cfs_rq, se);
 		update_tg_load_avg(cfs_rq, 0);
 	}
@@ -3387,10 +3426,8 @@ enqueue_entity_load_avg(struct cfs_rq *c
 static inline void
 dequeue_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
-	cfs_rq->runnable_load_avg =
-		max_t(long, cfs_rq->runnable_load_avg - se->avg.load_avg, 0);
-	cfs_rq->runnable_load_sum =
-		max_t(s64,  cfs_rq->runnable_load_sum - se->avg.load_sum, 0);
+	sub_positive(&cfs_rq->runnable_load_avg, se->avg.load_avg);
+	sub_positive(&cfs_rq->runnable_load_sum, se_weight(se) * se->avg.load_sum);
 }
 
 #ifndef CONFIG_64BIT
maintainer
#5 lore raw

Re: [RFC][PATCH 03/14] sched/fair: Remove se->load.weight from se->avg.load_sum

Hi Peter,

Quoted 13 lines · Peter Zijlstra

Remove the load from the load_sum for sched_entities, basically turning load_sum into runnable_sum. This prepares for better reweighting of group entities.

Since we now have different rules for computing load_avg, split ___update_load_avg() into two parts, ___update_load_sum() and ___update_load_avg().

So for se:

___update_load_sum(.weight = 1)
___upate_load_avg(.weight = se->load.weight)

Quoted 8 lines

and for cfs_rq:

___update_load_sum(.weight = cfs_rq->load.weight) ___upate_load_avg(.weight = 1)

Since the primary consumable is load_avg, most things will not be affected. Only those few sites that initialize/modify load_sum need attention.

I wonder if there is a problem with this new way to compute se's load_avg and cfs_rq's load_avg when a task changes is nice prio before migrating to another CPU.

se load_avg is now: runnable x current weight
but cfs_rq load_avg keeps the history of the previous weight of the se When we detach se, we will remove an up to date se's load_avg from cfs_rq which doesn't have the up to date load_avg in its own load_avg. So if se's prio decreases just before migrating, some load_avg stays in prev cfs_rq and if se's prio increases, we will remove too much load_avg and possibly make the cfs_rq load_avg null whereas other tasks are running.

Thought ?

I'm able to reproduce the problem with a simple rt-app use case (after adding a new feature in rt-app)

Vincent

Quoted 187 lines
---
 kernel/sched/fair.c |   91 ++++++++++++++++++++++++++++++++++++----------------
 1 file changed, 64 insertions(+), 27 deletions(-)
kernel/sched/fair.c +64 -27
@@ -744,7 +744,7 @@ void init_entity_runnable_average(struct
         */
        if (entity_is_task(se))
                sa->load_avg = scale_load_down(se->load.weight);
-       sa->load_sum = sa->load_avg * LOAD_AVG_MAX;
+       sa->load_sum = LOAD_AVG_MAX;
        /*
         * At this point, util_avg won't be used in select_task_rq_fair anyway
         */
@@ -1967,7 +1967,7 @@ static u64 numa_get_avg_runtime(struct t
                delta = runtime - p->last_sum_exec_runtime;
                *period = now - p->last_task_numa_placement;
        } else {
-               delta = p->se.avg.load_sum / p->se.load.weight;
+               delta = p->se.avg.load_sum;
                *period = LOAD_AVG_MAX;
        }
 
@@ -2872,8 +2872,8 @@ accumulate_sum(u64 delta, int cpu, struc
  *            = u_0 + u_1*y + u_2*y^2 + ... [re-labeling u_i --> u_{i+1}]
  */
 static __always_inline int
-___update_load_avg(u64 now, int cpu, struct sched_avg *sa,
-                 unsigned long weight, int running, struct cfs_rq *cfs_rq)
+___update_load_sum(u64 now, int cpu, struct sched_avg *sa,
+                  unsigned long weight, int running, struct cfs_rq *cfs_rq)
 {
        u64 delta;
 
@@ -2907,39 +2907,80 @@ ___update_load_avg(u64 now, int cpu, str
        if (!accumulate_sum(delta, cpu, sa, weight, running, cfs_rq))
                return 0;
 
+       return 1;
+}
+
+static __always_inline void
+___update_load_avg(struct sched_avg *sa, unsigned long weight, struct cfs_rq *cfs_rq)
+{
+       u32 divider = LOAD_AVG_MAX - 1024 + sa->period_contrib;
+
        /*
         * Step 2: update *_avg.
         */
-       sa->load_avg = div_u64(sa->load_sum, LOAD_AVG_MAX - 1024 + sa->period_contrib);
+       sa->load_avg = div_u64(weight * sa->load_sum, divider);
        if (cfs_rq) {
                cfs_rq->runnable_load_avg =
-                       div_u64(cfs_rq->runnable_load_sum, LOAD_AVG_MAX - 1024 + sa->period_contrib);
+                       div_u64(cfs_rq->runnable_load_sum, divider);
        }
-       sa->util_avg = sa->util_sum / (LOAD_AVG_MAX - 1024 + sa->period_contrib);
+       sa->util_avg = sa->util_sum / divider;
+}
 
-       return 1;
+/*
+ * XXX we want to get rid of this helper and use the full load resolution.
+ */
+static inline long se_weight(struct sched_entity *se)
+{
+       return scale_load_down(se->load.weight);
 }
 
+/*
+ * sched_entity:
+ *
+ *   load_sum := runnable_sum
+ *   load_avg = se_weight(se) * runnable_avg
+ *
+ * cfq_rs:
+ *
+ *   load_sum = \Sum se_weight(se) * se->avg.load_sum
+ *   load_avg = \Sum se->avg.load_avg
+ */
+
 static int
 __update_load_avg_blocked_se(u64 now, int cpu, struct sched_entity *se)
 {
-       return ___update_load_avg(now, cpu, &se->avg, 0, 0, NULL);
+       if (___update_load_sum(now, cpu, &se->avg, 0, 0, NULL)) {
+               ___update_load_avg(&se->avg, se_weight(se), NULL);
+               return 1;
+       }
+
+       return 0;
 }
 
 static int
 __update_load_avg_se(u64 now, int cpu, struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
-       return ___update_load_avg(now, cpu, &se->avg,
-                                 se->on_rq * scale_load_down(se->load.weight),
-                                 cfs_rq->curr == se, NULL);
+       if (___update_load_sum(now, cpu, &se->avg, !!se->on_rq,
+                               cfs_rq->curr == se, NULL)) {
+
+               ___update_load_avg(&se->avg, se_weight(se), NULL);
+               return 1;
+       }
+
+       return 0;
 }
 
 static int
 __update_load_avg_cfs_rq(u64 now, int cpu, struct cfs_rq *cfs_rq)
 {
-       return ___update_load_avg(now, cpu, &cfs_rq->avg,
-                       scale_load_down(cfs_rq->load.weight),
-                       cfs_rq->curr != NULL, cfs_rq);
+       if (___update_load_sum(now, cpu, &cfs_rq->avg,
+                               scale_load_down(cfs_rq->load.weight),
+                               cfs_rq->curr != NULL, cfs_rq)) {
+               ___update_load_avg(&cfs_rq->avg, 1, cfs_rq);
+               return 1;
+       }
+
+       return 0;
 }
 
 /*
@@ -3110,7 +3151,7 @@ update_tg_cfs_load(struct cfs_rq *cfs_rq
 
        /* Set new sched_entity's load */
        se->avg.load_avg = load;
-       se->avg.load_sum = se->avg.load_avg * LOAD_AVG_MAX;
+       se->avg.load_sum = LOAD_AVG_MAX;
 
        /* Update parent cfs_rq load */
        add_positive(&cfs_rq->avg.load_avg, delta);
@@ -3340,7 +3381,7 @@ static void attach_entity_load_avg(struc
 {
        se->avg.last_update_time = cfs_rq->avg.last_update_time;
        cfs_rq->avg.load_avg += se->avg.load_avg;
-       cfs_rq->avg.load_sum += se->avg.load_sum;
+       cfs_rq->avg.load_sum += se_weight(se) * se->avg.load_sum;
        cfs_rq->avg.util_avg += se->avg.util_avg;
        cfs_rq->avg.util_sum += se->avg.util_sum;
        set_tg_cfs_propagate(cfs_rq);
@@ -3360,7 +3401,7 @@ static void detach_entity_load_avg(struc
 {
 
        sub_positive(&cfs_rq->avg.load_avg, se->avg.load_avg);
-       sub_positive(&cfs_rq->avg.load_sum, se->avg.load_sum);
+       sub_positive(&cfs_rq->avg.load_sum, se_weight(se) * se->avg.load_sum);
        sub_positive(&cfs_rq->avg.util_avg, se->avg.util_avg);
        sub_positive(&cfs_rq->avg.util_sum, se->avg.util_sum);
        set_tg_cfs_propagate(cfs_rq);
@@ -3372,12 +3413,10 @@ static void detach_entity_load_avg(struc
 static inline void
 enqueue_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
-       struct sched_avg *sa = &se->avg;
-
-       cfs_rq->runnable_load_avg += sa->load_avg;
-       cfs_rq->runnable_load_sum += sa->load_sum;
+       cfs_rq->runnable_load_avg += se->avg.load_avg;
+       cfs_rq->runnable_load_sum += se_weight(se) * se->avg.load_sum;
 
-       if (!sa->last_update_time) {
+       if (!se->avg.last_update_time) {
                attach_entity_load_avg(cfs_rq, se);
                update_tg_load_avg(cfs_rq, 0);
        }
@@ -3387,10 +3426,8 @@ enqueue_entity_load_avg(struct cfs_rq *c
 static inline void
 dequeue_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
-       cfs_rq->runnable_load_avg =
-               max_t(long, cfs_rq->runnable_load_avg - se->avg.load_avg, 0);
-       cfs_rq->runnable_load_sum =
-               max_t(s64,  cfs_rq->runnable_load_sum - se->avg.load_sum, 0);
+       sub_positive(&cfs_rq->runnable_load_avg, se->avg.load_avg);
+       sub_positive(&cfs_rq->runnable_load_sum, se_weight(se) * se->avg.load_sum);
 }
 
 #ifndef CONFIG_64BIT
maintainer
#6 lore raw

Re: [RFC][PATCH 03/14] sched/fair: Remove se->load.weight from se->avg.load_sum

Quoted 38 lines · Vincent Guittot

Hi Peter,

Quoted 13 lines · Peter Zijlstra

Remove the load from the load_sum for sched_entities, basically turning load_sum into runnable_sum. This prepares for better reweighting of group entities.

Since we now have different rules for computing load_avg, split ___update_load_avg() into two parts, ___update_load_sum() and ___update_load_avg().

So for se:

___update_load_sum(.weight = 1)
___upate_load_avg(.weight = se->load.weight)

Quoted 8 lines

and for cfs_rq:

___update_load_sum(.weight = cfs_rq->load.weight) ___upate_load_avg(.weight = 1)

Since the primary consumable is load_avg, most things will not be affected. Only those few sites that initialize/modify load_sum need attention.

I wonder if there is a problem with this new way to compute se's load_avg and cfs_rq's load_avg when a task changes is nice prio before migrating to another CPU.

se load_avg is now: runnable x current weight
but cfs_rq load_avg keeps the history of the previous weight of the se When we detach se, we will remove an up to date se's load_avg from cfs_rq which doesn't have the up to date load_avg in its own load_avg. So if se's prio decreases just before migrating, some load_avg stays in prev cfs_rq and if se's prio increases, we will remove too much load_avg and possibly make the cfs_rq load_avg null whereas other tasks are running.

Quoted 7 lines

Thought ?

I'm able to reproduce the problem with a simple rt-app use case (after adding a new feature in rt-app)

Vincent

The hack below fixes the problem I mentioned above. It applies on task what is done when updating group_entity's weight

---
 kernel/sched/core.c | 26 +++++++++++++++++++-------
 kernel/sched/fair.c | 20 ++++++++++++++++++++
 2 files changed, 39 insertions(+), 7 deletions(-)
kernel/sched/core.c +19 -7
index 09e0996..f327ab6 100644
@@ -732,7 +732,9 @@ int tg_nop(struct task_group *tg, void *data)
 }
 #endif
 
-static void set_load_weight(struct task_struct *p)
+extern void reweight_task(struct task_struct *p, int prio);
+
+static void set_load_weight(struct task_struct *p, bool update_load)
 {
 	int prio = p->static_prio - MAX_RT_PRIO;
 	struct load_weight *load = &p->se.load;
@@ -746,8 +748,18 @@ static void set_load_weight(struct task_struct *p)
 		return;
 	}
 
-	load->weight = scale_load(sched_prio_to_weight[prio]);
-	load->inv_weight = sched_prio_to_wmult[prio];
+	/*
+	 * SCHED_OTHER tasks have to update their load when changing their
+	 * weight
+	 */
+	if (update_load) {
+		reweight_task(p, prio);
+	} else {
+		load->weight = scale_load(sched_prio_to_weight[prio]);
+		load->inv_weight = sched_prio_to_wmult[prio];
+	}
+
+
 }
 
 static inline void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
@@ -2373,7 +2385,7 @@ int sched_fork(unsigned long clone_flags, struct task_struct *p)
 			p->static_prio = NICE_TO_PRIO(0);
 
 		p->prio = p->normal_prio = __normal_prio(p);
-		set_load_weight(p);
+		set_load_weight(p, false);
 
 		/*
 		 * We don't need the reset flag anymore after the fork. It has
@@ -3854,7 +3866,7 @@ void set_user_nice(struct task_struct *p, long nice)
 		put_prev_task(rq, p);
 
 	p->static_prio = NICE_TO_PRIO(nice);
-	set_load_weight(p);
+	set_load_weight(p, true);
 	old_prio = p->prio;
 	p->prio = effective_prio(p);
 	delta = p->prio - old_prio;
@@ -4051,7 +4063,7 @@ static void __setscheduler_params(struct task_struct *p,
 	 */
 	p->rt_priority = attr->sched_priority;
 	p->normal_prio = normal_prio(p);
-	set_load_weight(p);
+	set_load_weight(p, fair_policy(policy));
 }
 
 /* Actually do priority change: must hold pi & rq lock. */
@@ -6152,7 +6164,7 @@ void __init sched_init(void)
 		atomic_set(&rq->nr_iowait, 0);
 	}
 
-	set_load_weight(&init_task);
+	set_load_weight(&init_task, false);
 
 	/*
 	 * The boot idle thread does lazy MMU switching as well:
kernel/sched/fair.c +20 -0
index bd2f9f5..3853e34 100644
@@ -2825,6 +2825,26 @@ __sub_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
 	sub_positive(&cfs_rq->avg.load_sum, se_weight(se) * se->avg.load_sum);
 }
 
+void reweight_task(struct task_struct *p, int prio)
+{
+	struct sched_entity *se = &p->se;
+	struct cfs_rq *cfs_rq = cfs_rq_of(se);
+	struct load_weight *load = &p->se.load;
+
+	u32 divider = LOAD_AVG_MAX - 1024 + se->avg.period_contrib;
+
+	__sub_load_avg(cfs_rq, se);
+
+	load->weight = scale_load(sched_prio_to_weight[prio]);
+	load->inv_weight = sched_prio_to_wmult[prio];
+
+	se->avg.load_avg = div_u64(se_weight(se) * se->avg.load_sum, divider);
+	se->avg.runnable_load_avg =
+		div_u64(se_runnable(se) * se->avg.runnable_load_sum, divider);
+
+	__add_load_avg(cfs_rq, se);
+}
+
 static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
 			    unsigned long weight, unsigned long runnable)
 {
author maintainer
#7 lore raw

Re: [RFC][PATCH 03/14] sched/fair: Remove se->load.weight from se->avg.load_sum

Quoted 17 lines · Vincent Guittot
Quoted 15 lines · Vincent Guittot

I wonder if there is a problem with this new way to compute se's load_avg and cfs_rq's load_avg when a task changes is nice prio before migrating to another CPU.

se load_avg is now: runnable x current weight
but cfs_rq load_avg keeps the history of the previous weight of the se When we detach se, we will remove an up to date se's load_avg from cfs_rq which doesn't have the up to date load_avg in its own load_avg. So if se's prio decreases just before migrating, some load_avg stays in prev cfs_rq and if se's prio increases, we will remove too much load_avg and possibly make the cfs_rq load_avg null whereas other tasks are running.

Thought ?

Quoted 8 lines
Quoted 5 lines

I'm able to reproduce the problem with a simple rt-app use case (after adding a new feature in rt-app)

Vincent

The hack below fixes the problem I mentioned above. It applies on task what is done when updating group_entity's weight

Right. I didn't think people much used nice so I skipped it for now. Yes your patch looks about right for that.

I'll include it, thanks!

#8 lore raw

[tip:sched/core] sched/fair: Use reweight_entity() for set_user_nice()

In reply to Vincent Guittot
sched/fair: Use reweight_entity() for set_user_nice()
Commit-ID:  9059393e4ec1c8c6623a120b405ef2c90b968d80
Gitweb:     https://git.kernel.org/tip/9059393e4ec1c8c6623a120b405ef2c90b968d80
Author:     Vincent Guittot <[email protected]>
AuthorDate: Wed, 17 May 2017 11:50:45 +0200
Committer:  Ingo Molnar <[email protected]>
CommitDate: Fri, 29 Sep 2017 19:35:14 +0200

sched/fair: Use reweight_entity() for set_user_nice()

Now that we directly change load_avg and propagate that change into the sums, sys_nice() and co should do the same, otherwise its possible to confuse load accounting when we migrate near the weight change.

---
 kernel/sched/core.c  | 22 ++++++++++++------
 kernel/sched/fair.c  | 63 ++++++++++++++++++++++++++++++----------------------
 kernel/sched/sched.h |  2 ++
 3 files changed, 54 insertions(+), 33 deletions(-)
kernel/sched/core.c +15 -7
index d17c5da..2288a14 100644
@@ -733,7 +733,7 @@ int tg_nop(struct task_group *tg, void *data)
 }
 #endif
 
-static void set_load_weight(struct task_struct *p)
+static void set_load_weight(struct task_struct *p, bool update_load)
 {
 	int prio = p->static_prio - MAX_RT_PRIO;
 	struct load_weight *load = &p->se.load;
@@ -747,8 +747,16 @@ static void set_load_weight(struct task_struct *p)
 		return;
 	}
 
-	load->weight = scale_load(sched_prio_to_weight[prio]);
-	load->inv_weight = sched_prio_to_wmult[prio];
+	/*
+	 * SCHED_OTHER tasks have to update their load when changing their
+	 * weight
+	 */
+	if (update_load && p->sched_class == &fair_sched_class) {
+		reweight_task(p, prio);
+	} else {
+		load->weight = scale_load(sched_prio_to_weight[prio]);
+		load->inv_weight = sched_prio_to_wmult[prio];
+	}
 }
 
 static inline void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
@@ -2358,7 +2366,7 @@ int sched_fork(unsigned long clone_flags, struct task_struct *p)
 			p->static_prio = NICE_TO_PRIO(0);
 
 		p->prio = p->normal_prio = __normal_prio(p);
-		set_load_weight(p);
+		set_load_weight(p, false);
 
 		/*
 		 * We don't need the reset flag anymore after the fork. It has
@@ -3805,7 +3813,7 @@ void set_user_nice(struct task_struct *p, long nice)
 		put_prev_task(rq, p);
 
 	p->static_prio = NICE_TO_PRIO(nice);
-	set_load_weight(p);
+	set_load_weight(p, true);
 	old_prio = p->prio;
 	p->prio = effective_prio(p);
 	delta = p->prio - old_prio;
@@ -3962,7 +3970,7 @@ static void __setscheduler_params(struct task_struct *p,
 	 */
 	p->rt_priority = attr->sched_priority;
 	p->normal_prio = normal_prio(p);
-	set_load_weight(p);
+	set_load_weight(p, true);
 }
 
 /* Actually do priority change: must hold pi & rq lock. */
@@ -5933,7 +5941,7 @@ void __init sched_init(void)
 		atomic_set(&rq->nr_iowait, 0);
 	}
 
-	set_load_weight(&init_task);
+	set_load_weight(&init_task, false);
 
 	/*
 	 * The boot idle thread does lazy MMU switching as well:
kernel/sched/fair.c +37 -26

75 lines not on this page · raw message

kernel/sched/sched.h +2 -0
index 14db76c..a5d9746 100644
@@ -1529,6 +1529,8 @@ extern void init_sched_dl_class(void);
 extern void init_sched_rt_class(void);
 extern void init_sched_fair_class(void);
 
+extern void reweight_task(struct task_struct *p, int prio);
+
 extern void resched_curr(struct rq *rq);
 extern void resched_cpu(int cpu);
 
author maintainer
#9 lore raw

RFC PATCH 4/14 sched/fair: More accurate reweight_entity()

In reply to Peter Zijlstra

When a (group) entity changes it's weight we should instantly change its load_avg and propagate that change into the sums it is part of. Because we use these values to predict future behaviour and are not interested in its historical value.

Without this change, the change in load would need to propagate through the average, by which time it could again have changed etc.. always chasing itself.

With this change, the cfs_rq load_avg sum will more accurately reflect the current runnable and expected return of blocked load.

---
 kernel/sched/fair.c |   75 +++++++++++++++++++++++++++++++---------------------
 1 file changed, 46 insertions(+), 29 deletions(-)
kernel/sched/fair.c +46 -29
@@ -2673,9 +2673,41 @@ static long calc_cfs_shares(struct cfs_r
 }
 # endif /* CONFIG_SMP */
 
+/*
+ * Signed add 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 add_positive(_ptr, _val) do {                           \
+	typeof(_ptr) ptr = (_ptr);                              \
+	typeof(_val) val = (_val);                              \
+	typeof(*ptr) res, var = READ_ONCE(*ptr);                \
+								\
+	res = var + val;                                        \
+								\
+	if (val < 0 && res > var)                               \
+		res = 0;                                        \
+								\
+	WRITE_ONCE(*ptr, res);                                  \
+} while (0)
+
+/*
+ * XXX we want to get rid of this helper and use the full load resolution.
+ */
+static inline long se_weight(struct sched_entity *se)
+{
+	return scale_load_down(se->load.weight);
+}
+
 static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
 			    unsigned long weight)
 {
+	unsigned long se_load_avg = se->avg.load_avg;
+	u64 se_load_sum = se_weight(se) * se->avg.load_sum;
+	u64 new_load_sum = scale_load_down(weight) * se->avg.load_sum;
+
 	if (se->on_rq) {
 		/* commit outstanding execution time */
 		if (cfs_rq->curr == se)
@@ -2683,10 +2715,23 @@ static void reweight_entity(struct cfs_r
 		account_entity_dequeue(cfs_rq, se);
 	}
 
+	se->avg.load_avg = div_u64(new_load_sum,
+			LOAD_AVG_MAX - 1024 + se->avg.period_contrib);
+
 	update_load_set(&se->load, weight);
 
-	if (se->on_rq)
+	if (se->on_rq) {
 		account_entity_enqueue(cfs_rq, se);
+		add_positive(&cfs_rq->runnable_load_avg,
+				(long)(se->avg.load_avg - se_load_avg));
+		add_positive(&cfs_rq->runnable_load_sum,
+				(s64)(new_load_sum - se_load_sum));
+	}
+
+	add_positive(&cfs_rq->avg.load_avg,
+			(long)(se->avg.load_avg - se_load_avg));
+	add_positive(&cfs_rq->avg.load_sum,
+			(s64)(new_load_sum - se_load_sum));
 }
 
 static inline int throttled_hierarchy(struct cfs_rq *cfs_rq);
@@ -2927,14 +2972,6 @@ ___update_load_avg(struct sched_avg *sa,
 }
 
 /*
- * XXX we want to get rid of this helper and use the full load resolution.
- */
-static inline long se_weight(struct sched_entity *se)
-{
-	return scale_load_down(se->load.weight);
-}
-
-/*
  * sched_entity:
  *
  *   load_sum := runnable_sum
@@ -2983,26 +3020,6 @@ __update_load_avg_cfs_rq(u64 now, int cp
 	return 0;
 }
 
-/*
- * Signed add 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 add_positive(_ptr, _val) do {                           \
-	typeof(_ptr) ptr = (_ptr);                              \
-	typeof(_val) val = (_val);                              \
-	typeof(*ptr) res, var = READ_ONCE(*ptr);                \
-								\
-	res = var + val;                                        \
-								\
-	if (val < 0 && res > var)                               \
-		res = 0;                                        \
-								\
-	WRITE_ONCE(*ptr, res);                                  \
-} while (0)
-
 #ifdef CONFIG_FAIR_GROUP_SCHED
 /**
  * update_tg_load_avg - update the tg's load avg
author maintainer
#10 lore raw

RFC PATCH 5/14 sched/fair: Change update_load_avg() arguments

In reply to Peter Zijlstra

Most call sites of update_load_avg() already have cfs_rq_of(se) available, pass it down instead of recomputing it.

---
 kernel/sched/fair.c |   31 +++++++++++++++----------------
 1 file changed, 15 insertions(+), 16 deletions(-)
kernel/sched/fair.c +15 -16
@@ -3349,9 +3349,8 @@ update_cfs_rq_load_avg(u64 now, struct c
 #define SKIP_AGE_LOAD	0x2
 
 /* Update task and its cfs_rq load average */
-static inline void update_load_avg(struct sched_entity *se, int flags)
+static inline void update_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
 {
-	struct cfs_rq *cfs_rq = cfs_rq_of(se);
 	u64 now = cfs_rq_clock_task(cfs_rq);
 	struct rq *rq = rq_of(cfs_rq);
 	int cpu = cpu_of(rq);
@@ -3512,9 +3511,9 @@ update_cfs_rq_load_avg(u64 now, struct c
 #define UPDATE_TG	0x0
 #define SKIP_AGE_LOAD	0x0
 
-static inline void update_load_avg(struct sched_entity *se, int not_used1)
+static inline void update_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se, int not_used1)
 {
-	cpufreq_update_util(rq_of(cfs_rq_of(se)), 0);
+	cpufreq_update_util(rq_of(cfs_rq), 0);
 }
 
 static inline void
@@ -3665,7 +3664,7 @@ enqueue_entity(struct cfs_rq *cfs_rq, st
 	 *     its group cfs_rq
 	 *   - Add its new weight to cfs_rq->load.weight
 	 */
-	update_load_avg(se, UPDATE_TG);
+	update_load_avg(cfs_rq, se, UPDATE_TG);
 	enqueue_entity_load_avg(cfs_rq, se);
 	update_cfs_shares(se);
 	account_entity_enqueue(cfs_rq, se);
@@ -3749,7 +3748,7 @@ dequeue_entity(struct cfs_rq *cfs_rq, st
 	 *   - For group entity, update its weight to reflect the new share
 	 *     of its group cfs_rq.
 	 */
-	update_load_avg(se, UPDATE_TG);
+	update_load_avg(cfs_rq, se, UPDATE_TG);
 	dequeue_entity_load_avg(cfs_rq, se);
 
 	update_stats_dequeue(cfs_rq, se, flags);
@@ -3837,7 +3836,7 @@ set_next_entity(struct cfs_rq *cfs_rq, s
 		 */
 		update_stats_wait_end(cfs_rq, se);
 		__dequeue_entity(cfs_rq, se);
-		update_load_avg(se, UPDATE_TG);
+		update_load_avg(cfs_rq, se, UPDATE_TG);
 	}
 
 	update_stats_curr_start(cfs_rq, se);
@@ -3939,7 +3938,7 @@ static void put_prev_entity(struct cfs_r
 		/* Put 'current' back into the tree. */
 		__enqueue_entity(cfs_rq, prev);
 		/* in !on_rq case, update occurred at dequeue */
-		update_load_avg(prev, 0);
+		update_load_avg(cfs_rq, prev, 0);
 	}
 	cfs_rq->curr = NULL;
 }
@@ -3955,7 +3954,7 @@ entity_tick(struct cfs_rq *cfs_rq, struc
 	/*
 	 * Ensure that runnable average is periodically updated.
 	 */
-	update_load_avg(curr, UPDATE_TG);
+	update_load_avg(cfs_rq, curr, UPDATE_TG);
 	update_cfs_shares(curr);
 
 #ifdef CONFIG_SCHED_HRTICK
@@ -4873,7 +4872,7 @@ enqueue_task_fair(struct rq *rq, struct
 		if (cfs_rq_throttled(cfs_rq))
 			break;
 
-		update_load_avg(se, UPDATE_TG);
+		update_load_avg(cfs_rq, se, UPDATE_TG);
 		update_cfs_shares(se);
 	}
 
@@ -4932,7 +4931,7 @@ static void dequeue_task_fair(struct rq
 		if (cfs_rq_throttled(cfs_rq))
 			break;
 
-		update_load_avg(se, UPDATE_TG);
+		update_load_avg(cfs_rq, se, UPDATE_TG);
 		update_cfs_shares(se);
 	}
 
@@ -7030,7 +7029,7 @@ static void update_blocked_averages(int
 		/* Propagate pending load changes to the parent, if any: */
 		se = cfs_rq->tg->se[cpu];
 		if (se && !skip_blocked_update(se))
-			update_load_avg(se, 0);
+			update_load_avg(cfs_rq_of(se), se, 0);
 
 		/*
 		 * There can be a lot of idle CPU cgroups.  Don't let fully
@@ -9159,7 +9158,7 @@ static void propagate_entity_cfs_rq(stru
 		if (cfs_rq_throttled(cfs_rq))
 			break;
 
-		update_load_avg(se, UPDATE_TG);
+		update_load_avg(cfs_rq, se, UPDATE_TG);
 	}
 }
 #else
@@ -9171,7 +9170,7 @@ static void detach_entity_cfs_rq(struct
 	struct cfs_rq *cfs_rq = cfs_rq_of(se);
 
 	/* Catch up with the cfs_rq and remove our load when we leave */
-	update_load_avg(se, 0);
+	update_load_avg(cfs_rq, se, 0);
 	detach_entity_load_avg(cfs_rq, se);
 	update_tg_load_avg(cfs_rq, false);
 	propagate_entity_cfs_rq(se);
@@ -9190,7 +9189,7 @@ static void attach_entity_cfs_rq(struct
 #endif
 
 	/* Synchronize entity with its cfs_rq */
-	update_load_avg(se, sched_feat(ATTACH_AGE_LOAD) ? 0 : SKIP_AGE_LOAD);
+	update_load_avg(cfs_rq, se, sched_feat(ATTACH_AGE_LOAD) ? 0 : SKIP_AGE_LOAD);
 	attach_entity_load_avg(cfs_rq, se);
 	update_tg_load_avg(cfs_rq, false);
 	propagate_entity_cfs_rq(se);
@@ -9474,7 +9473,7 @@ int sched_group_set_shares(struct task_g
 		rq_lock_irqsave(rq, &rf);
 		update_rq_clock(rq);
 		for_each_sched_entity(se) {
-			update_load_avg(se, UPDATE_TG);
+			update_load_avg(cfs_rq_of(se), se, UPDATE_TG);
 			update_cfs_shares(se);
 		}
 		rq_unlock_irqrestore(rq, &rf);
author maintainer
#12 lore raw

RFC PATCH 6/14 sched/fair: Move enqueue migrate handling

In reply to Peter Zijlstra

Move the entity migrate handling from enqueue_entity_load_avg() to update_load_avg(). This has two benefits:

- {en,de}queue_entity_load_avg() will become purely about managing runnable_load

- we can avoid a double update_tg_load_avg() and reduce pressure on the global tg->shares cacheline

The reason we do this is so that we can change update_cfs_shares() to change both weight and (future) runnable_weight. For this to work we need to have the cfs_rq averages up-to-date (which means having done the attach), but we need the cfs_rq->avg.runnable_avg to not yet include the se's contribution (since se->on_rq == 0).

---
 kernel/sched/fair.c |   70 ++++++++++++++++++++++++++--------------------------
 1 file changed, 36 insertions(+), 34 deletions(-)
kernel/sched/fair.c +36 -34
@@ -3418,34 +3418,6 @@ update_cfs_rq_load_avg(u64 now, struct c
 	return decayed || removed_load;
 }
 
-/*
- * Optional action to be done while updating the load average
- */
-#define UPDATE_TG	0x1
-#define SKIP_AGE_LOAD	0x2
-
-/* Update task and its cfs_rq load average */
-static inline void update_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
-{
-	u64 now = cfs_rq_clock_task(cfs_rq);
-	struct rq *rq = rq_of(cfs_rq);
-	int cpu = cpu_of(rq);
-	int decayed;
-
-	/*
-	 * 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_se(now, cpu, cfs_rq, se);
-
-	decayed  = update_cfs_rq_load_avg(now, cfs_rq, true);
-	decayed |= propagate_entity_load_avg(se);
-
-	if (decayed && (flags & UPDATE_TG))
-		update_tg_load_avg(cfs_rq, 0);
-}
-
 /**
  * attach_entity_load_avg - attach this entity to its cfs_rq load avg
  * @cfs_rq: cfs_rq to attach to
@@ -3486,17 +3458,46 @@ static void detach_entity_load_avg(struc
 	cfs_rq_util_change(cfs_rq);
 }
 
+/*
+ * Optional action to be done while updating the load average
+ */
+#define UPDATE_TG	0x1
+#define SKIP_AGE_LOAD	0x2
+#define DO_ATTACH	0x4
+
+/* Update task and its cfs_rq load average */
+static inline void update_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
+{
+	u64 now = cfs_rq_clock_task(cfs_rq);
+	struct rq *rq = rq_of(cfs_rq);
+	int cpu = cpu_of(rq);
+	int decayed;
+
+	/*
+	 * 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_se(now, cpu, cfs_rq, se);
+
+	decayed  = update_cfs_rq_load_avg(now, cfs_rq, true);
+	decayed |= propagate_entity_load_avg(se);
+
+	if (!se->avg.last_update_time && (flags & DO_ATTACH)) {
+
+		attach_entity_load_avg(cfs_rq, se);
+		update_tg_load_avg(cfs_rq, 0);
+
+	} else if (decayed && (flags & UPDATE_TG))
+		update_tg_load_avg(cfs_rq, 0);
+}
+
 /* Add the load generated by se into cfs_rq's load average */
 static inline void
 enqueue_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
 	cfs_rq->runnable_load_avg += se->avg.load_avg;
 	cfs_rq->runnable_load_sum += se_weight(se) * se->avg.load_sum;
-
-	if (!se->avg.last_update_time) {
-		attach_entity_load_avg(cfs_rq, se);
-		update_tg_load_avg(cfs_rq, 0);
-	}
 }
 
 /* Remove the runnable load generated by se from cfs_rq's runnable load average */
@@ -3586,6 +3587,7 @@ update_cfs_rq_load_avg(u64 now, struct c
 
 #define UPDATE_TG	0x0
 #define SKIP_AGE_LOAD	0x0
+#define DO_ATTACH	0x0
 
 static inline void update_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se, int not_used1)
 {
@@ -3740,7 +3742,7 @@ enqueue_entity(struct cfs_rq *cfs_rq, st
 	 *     its group cfs_rq
 	 *   - Add its new weight to cfs_rq->load.weight
 	 */
-	update_load_avg(cfs_rq, se, UPDATE_TG);
+	update_load_avg(cfs_rq, se, UPDATE_TG | DO_ATTACH);
 	enqueue_entity_load_avg(cfs_rq, se);
 	update_cfs_shares(se);
 	account_entity_enqueue(cfs_rq, se);
maintainer Acked-by on v1 6/14
#13 lore raw

Re: [RFC][PATCH 06/14] sched/fair: Move enqueue migrate handling

Quoted 9 lines · Peter Zijlstra

Move the entity migrate handling from enqueue_entity_load_avg() to update_load_avg(). This has two benefits:

- {en,de}queue_entity_load_avg() will become purely about managing runnable_load

- we can avoid a double update_tg_load_avg() and reduce pressure on the global tg->shares cacheline

Quoted 7 lines

The reason we do this is so that we can change update_cfs_shares() to change both weight and (future) runnable_weight. For this to work we need to have the cfs_rq averages up-to-date (which means having done the attach), but we need the cfs_rq->avg.runnable_avg to not yet include the se's contribution (since se->on_rq == 0).

Quoted 112 lines
---
 kernel/sched/fair.c |   70 ++++++++++++++++++++++++++--------------------------
 1 file changed, 36 insertions(+), 34 deletions(-)
kernel/sched/fair.c +36 -34
@@ -3418,34 +3418,6 @@ update_cfs_rq_load_avg(u64 now, struct c
        return decayed || removed_load;
 }
 
-/*
- * Optional action to be done while updating the load average
- */
-#define UPDATE_TG      0x1
-#define SKIP_AGE_LOAD  0x2
-
-/* Update task and its cfs_rq load average */
-static inline void update_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
-{
-       u64 now = cfs_rq_clock_task(cfs_rq);
-       struct rq *rq = rq_of(cfs_rq);
-       int cpu = cpu_of(rq);
-       int decayed;
-
-       /*
-        * 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_se(now, cpu, cfs_rq, se);
-
-       decayed  = update_cfs_rq_load_avg(now, cfs_rq, true);
-       decayed |= propagate_entity_load_avg(se);
-
-       if (decayed && (flags & UPDATE_TG))
-               update_tg_load_avg(cfs_rq, 0);
-}
-
 /**
  * attach_entity_load_avg - attach this entity to its cfs_rq load avg
  * @cfs_rq: cfs_rq to attach to
@@ -3486,17 +3458,46 @@ static void detach_entity_load_avg(struc
        cfs_rq_util_change(cfs_rq);
 }
 
+/*
+ * Optional action to be done while updating the load average
+ */
+#define UPDATE_TG      0x1
+#define SKIP_AGE_LOAD  0x2
+#define DO_ATTACH      0x4
+
+/* Update task and its cfs_rq load average */
+static inline void update_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
+{
+       u64 now = cfs_rq_clock_task(cfs_rq);
+       struct rq *rq = rq_of(cfs_rq);
+       int cpu = cpu_of(rq);
+       int decayed;
+
+       /*
+        * 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_se(now, cpu, cfs_rq, se);
+
+       decayed  = update_cfs_rq_load_avg(now, cfs_rq, true);
+       decayed |= propagate_entity_load_avg(se);
+
+       if (!se->avg.last_update_time && (flags & DO_ATTACH)) {
+
+               attach_entity_load_avg(cfs_rq, se);
+               update_tg_load_avg(cfs_rq, 0);
+
+       } else if (decayed && (flags & UPDATE_TG))
+               update_tg_load_avg(cfs_rq, 0);
+}
+
 /* Add the load generated by se into cfs_rq's load average */
 static inline void
 enqueue_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
        cfs_rq->runnable_load_avg += se->avg.load_avg;
        cfs_rq->runnable_load_sum += se_weight(se) * se->avg.load_sum;
-
-       if (!se->avg.last_update_time) {
-               attach_entity_load_avg(cfs_rq, se);
-               update_tg_load_avg(cfs_rq, 0);
-       }
 }
 
 /* Remove the runnable load generated by se from cfs_rq's runnable load average */
@@ -3586,6 +3587,7 @@ update_cfs_rq_load_avg(u64 now, struct c
 
 #define UPDATE_TG      0x0
 #define SKIP_AGE_LOAD  0x0
+#define DO_ATTACH      0x0
 
 static inline void update_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se, int not_used1)
 {
@@ -3740,7 +3742,7 @@ enqueue_entity(struct cfs_rq *cfs_rq, st
         *     its group cfs_rq
         *   - Add its new weight to cfs_rq->load.weight
         */
-       update_load_avg(cfs_rq, se, UPDATE_TG);
+       update_load_avg(cfs_rq, se, UPDATE_TG | DO_ATTACH);
        enqueue_entity_load_avg(cfs_rq, se);
        update_cfs_shares(se);
        account_entity_enqueue(cfs_rq, se);
author maintainer
#14 lore raw

RFC PATCH 7/14 sched/fair: Rewrite cfs_rq->removed_*avg

In reply to Peter Zijlstra

Since on wakeup migration we don't hold the rq->lock for the old CPU we cannot update its state. Instead we add the removed 'load' to an atomic variable and have the next update on that CPU collect and process it.

Currently we have 2 atomic variables; which already have the issue that they can be read out-of-sync. Also, two atomic ops on a single cacheline is already more expensive than an uncontended lock.

Since we want to add more, convert the thing over to an explicit cacheline with a lock in.

---
 kernel/sched/debug.c |    8 ++++----
 kernel/sched/fair.c  |   51 +++++++++++++++++++++++++++++++++++----------------
 kernel/sched/sched.h |   13 +++++++++----
 3 files changed, 48 insertions(+), 24 deletions(-)
kernel/sched/debug.c +4 -4
@@ -519,10 +519,10 @@ void print_cfs_rq(struct seq_file *m, in
 			cfs_rq->runnable_load_avg);
 	SEQ_printf(m, "  .%-30s: %lu\n", "util_avg",
 			cfs_rq->avg.util_avg);
-	SEQ_printf(m, "  .%-30s: %ld\n", "removed_load_avg",
-			atomic_long_read(&cfs_rq->removed_load_avg));
-	SEQ_printf(m, "  .%-30s: %ld\n", "removed_util_avg",
-			atomic_long_read(&cfs_rq->removed_util_avg));
+	SEQ_printf(m, "  .%-30s: %ld\n", "removed.load_avg",
+			cfs_rq->removed.load_avg);
+	SEQ_printf(m, "  .%-30s: %ld\n", "removed.util_avg",
+			cfs_rq->removed.util_avg);
 #ifdef CONFIG_FAIR_GROUP_SCHED
 	SEQ_printf(m, "  .%-30s: %lu\n", "tg_load_avg_contrib",
 			cfs_rq->tg_load_avg_contrib);
kernel/sched/fair.c +35 -16

96 lines not on this page · raw message

kernel/sched/sched.h +9 -4
@@ -424,14 +424,19 @@ struct cfs_rq {
 	struct sched_avg avg;
 	u64 runnable_load_sum;
 	unsigned long runnable_load_avg;
+#ifndef CONFIG_64BIT
+	u64 load_last_update_time_copy;
+#endif
 #ifdef CONFIG_FAIR_GROUP_SCHED
 	unsigned long tg_load_avg_contrib;
 	unsigned long propagate_avg;
 #endif
-	atomic_long_t removed_load_avg, removed_util_avg;
-#ifndef CONFIG_64BIT
-	u64 load_last_update_time_copy;
-#endif
+	struct {
+		raw_spinlock_t	lock ____cacheline_aligned;
+		int		nr;
+		unsigned long	load_avg;
+		unsigned long	util_avg;
+	} removed;
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
 	/*
author maintainer
#15 lore raw

RFC PATCH 8/14 sched/fair: Rewrite PELT migration propagation

In reply to Peter Zijlstra

When an entity migrates in (or out) of a runqueue, we need to add (or remove) its contribution from the entire PELT hierarchy, because even non-runnable entities are included in the load average sums.

In order to do this we have some propagation logic that updates the PELT tree, however the way it 'propagates' the runnable (or load) change is (more or less):

                     tg->weight * grq->avg.load_avg
  ge->avg.load_avg = ------------------------------
                               tg->load_avg

But that is the expression for ge->weight, and per the definition of load_avg:

ge->avg.load_avg := ge->weight * ge->avg.runnable_avg

That destroys the runnable_avg (by setting it to 1) we wanted to propagate.

Instead directly propagate runnable_sum.

---
 kernel/sched/debug.c |    2 
 kernel/sched/fair.c  |  186 ++++++++++++++++++++++++++++-----------------------
 kernel/sched/sched.h |    9 +-
 3 files changed, 112 insertions(+), 85 deletions(-)
kernel/sched/debug.c +2 -0
@@ -523,6 +523,8 @@ void print_cfs_rq(struct seq_file *m, in
 			cfs_rq->removed.load_avg);
 	SEQ_printf(m, "  .%-30s: %ld\n", "removed.util_avg",
 			cfs_rq->removed.util_avg);
+	SEQ_printf(m, "  .%-30s: %ld\n", "removed.runnable_sum",
+			cfs_rq->removed.runnable_sum);
 #ifdef CONFIG_FAIR_GROUP_SCHED
 	SEQ_printf(m, "  .%-30s: %lu\n", "tg_load_avg_contrib",
 			cfs_rq->tg_load_avg_contrib);
kernel/sched/fair.c +105 -81

281 lines not on this page · raw message

kernel/sched/sched.h +5 -4
@@ -427,18 +427,19 @@ struct cfs_rq {
 #ifndef CONFIG_64BIT
 	u64 load_last_update_time_copy;
 #endif
-#ifdef CONFIG_FAIR_GROUP_SCHED
-	unsigned long tg_load_avg_contrib;
-	unsigned long propagate_avg;
-#endif
 	struct {
 		raw_spinlock_t	lock ____cacheline_aligned;
 		int		nr;
 		unsigned long	load_avg;
 		unsigned long	util_avg;
+		unsigned long	runnable_sum;
 	} removed;
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
+	unsigned long tg_load_avg_contrib;
+	long propagate;
+	long prop_runnable_sum;
+
 	/*
 	 *   h_load = weight * f(tg)
 	 *
author maintainer
#16 lore raw

RFC PATCH 9/14 sched/fair: Propagate an effective runnable_load_avg

In reply to Peter Zijlstra

The load balancer uses runnable_load_avg as load indicator. For !cgroup this is:

runnable_load_avg = \Sum se->avg.load_avg ; where se->on_rq

That is, a direct sum of all runnable tasks on that runqueue. As opposed to load_avg, which is a sum of all tasks on the runqueue, which includes a blocked component.

However, in the cgroup case, this comes apart since the group entities are always runnable, even if most of their constituent entities are blocked.

Therefore introduce a runnable_weight which for task entities is the same as the regular weight, but for group entities is a fraction of the entity weight and represents the runnable part of the group runqueue.

Then propagate this load through the PELT hierarchy to arrive at an effective runnable load avgerage -- which we should not confuse with the canonical runnable load average.

---
 include/linux/sched.h |    3 
 kernel/sched/debug.c  |    8 +
 kernel/sched/fair.c   |  228 ++++++++++++++++++++++++++++++--------------------
 kernel/sched/sched.h  |    3 
 4 files changed, 150 insertions(+), 92 deletions(-)
include/linux/sched.h +3 -0
@@ -314,9 +314,11 @@ struct load_weight {
 struct sched_avg {
 	u64				last_update_time;
 	u64				load_sum;
+	u64				runnable_load_sum;
 	u32				util_sum;
 	u32				period_contrib;
 	unsigned long			load_avg;
+	unsigned long			runnable_load_avg;
 	unsigned long			util_avg;
 };
 
@@ -359,6 +361,7 @@ struct sched_statistics {
 struct sched_entity {
 	/* For load-balancing: */
 	struct load_weight		load;
+	unsigned long			runnable_weight;
 	struct rb_node			run_node;
 	struct list_head		group_node;
 	unsigned int			on_rq;
kernel/sched/debug.c +7 -1
@@ -396,9 +396,11 @@ static void print_cfs_group_stats(struct
 		P_SCHEDSTAT(se->statistics.wait_count);
 	}
 	P(se->load.weight);
+	P(se->runnable_weight);
 #ifdef CONFIG_SMP
 	P(se->avg.load_avg);
 	P(se->avg.util_avg);
+	P(se->avg.runnable_load_avg);
 #endif
 
 #undef PN_SCHEDSTAT
@@ -513,10 +515,11 @@ void print_cfs_rq(struct seq_file *m, in
 	SEQ_printf(m, "  .%-30s: %d\n", "nr_running", cfs_rq->nr_running);
 	SEQ_printf(m, "  .%-30s: %ld\n", "load", cfs_rq->load.weight);
 #ifdef CONFIG_SMP
+	SEQ_printf(m, "  .%-30s: %ld\n", "runnable_weight", cfs_rq->runnable_weight);
 	SEQ_printf(m, "  .%-30s: %lu\n", "load_avg",
 			cfs_rq->avg.load_avg);
 	SEQ_printf(m, "  .%-30s: %lu\n", "runnable_load_avg",
-			cfs_rq->runnable_load_avg);
+			cfs_rq->avg.runnable_load_avg);
 	SEQ_printf(m, "  .%-30s: %lu\n", "util_avg",
 			cfs_rq->avg.util_avg);
 	SEQ_printf(m, "  .%-30s: %ld\n", "removed.load_avg",
@@ -947,10 +950,13 @@ void proc_sched_show_task(struct task_st
 		   "nr_involuntary_switches", (long long)p->nivcsw);
 
 	P(se.load.weight);
+	P(se.runnable_weight);
 #ifdef CONFIG_SMP
 	P(se.avg.load_sum);
+	P(se.avg.runnable_load_sum);
 	P(se.avg.util_sum);
 	P(se.avg.load_avg);
+	P(se.avg.runnable_load_avg);
 	P(se.avg.util_avg);
 	P(se.avg.last_update_time);
 #endif
kernel/sched/fair.c +139 -89

433 lines not on this page · raw message

kernel/sched/sched.h +1 -2
@@ -396,6 +396,7 @@ struct cfs_bandwidth { };
 /* CFS-related fields in a runqueue */
 struct cfs_rq {
 	struct load_weight load;
+	unsigned long runnable_weight;
 	unsigned int nr_running, h_nr_running;
 
 	u64 exec_clock;
@@ -422,8 +423,6 @@ struct cfs_rq {
 	 * CFS load tracking
 	 */
 	struct sched_avg avg;
-	u64 runnable_load_sum;
-	unsigned long runnable_load_avg;
 #ifndef CONFIG_64BIT
 	u64 load_last_update_time_copy;
 #endif
author maintainer
#17 lore raw

RFC PATCH 10/14 sched/fair: more obvious

In reply to Peter Zijlstra

one mult worse, but more obvious code

---
 kernel/sched/fair.c |   57 +++++++++++++++++++++++++++-------------------------
 1 file changed, 30 insertions(+), 27 deletions(-)
kernel/sched/fair.c +30 -27
@@ -2786,7 +2786,7 @@ static inline long se_runnable(struct sc
 }
 
 static inline void
-enqueue_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
+enqueue_runnable_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
 	cfs_rq->runnable_weight += se->runnable_weight;
 
@@ -2795,7 +2795,7 @@ enqueue_entity_load_avg(struct cfs_rq *c
 }
 
 static inline void
-dequeue_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
+dequeue_runnable_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
 	cfs_rq->runnable_weight -= se->runnable_weight;
 
@@ -2804,12 +2804,23 @@ dequeue_entity_load_avg(struct cfs_rq *c
 		     se_runnable(se) * se->avg.runnable_load_sum);
 }
 
+static inline void
+__add_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
+{
+	cfs_rq->avg.load_avg += se->avg.load_avg;
+	cfs_rq->avg.load_sum += se_weight(se) * se->avg.load_sum;
+}
+
+static inline void
+__sub_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
+{
+	sub_positive(&cfs_rq->avg.load_avg, se->avg.load_avg);
+	sub_positive(&cfs_rq->avg.load_sum, se_weight(se) * se->avg.load_sum);
+}
+
 static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
 			    unsigned long weight, unsigned long runnable)
 {
-	unsigned long se_load_avg = se->avg.load_avg;
-	u64 se_load_sum = se_weight(se) * se->avg.load_sum;
-	u64 new_load_sum = scale_load_down(weight) * se->avg.load_sum;
 	u32 divider = LOAD_AVG_MAX - 1024 + se->avg.period_contrib;
 
 	if (se->on_rq) {
@@ -2818,27 +2829,22 @@ static void reweight_entity(struct cfs_r
 			update_curr(cfs_rq);
 
 		account_entity_dequeue(cfs_rq, se);
-		dequeue_entity_load_avg(cfs_rq, se);
+		dequeue_runnable_load_avg(cfs_rq, se);
 	}
-
-	se->avg.load_avg = div_u64(new_load_sum, divider);
-	se->avg.runnable_load_avg =
-		div_u64(scale_load_down(runnable) * se->avg.runnable_load_sum, divider);
+	__sub_load_avg(cfs_rq, se);
 
 	se->runnable_weight = runnable;
 	update_load_set(&se->load, weight);
 
-	if (se->on_rq) {
-		/* XXX delta accounting for these */
+	se->avg.load_avg = div_u64(se_weight(se) * se->avg.load_sum, divider);
+	se->avg.runnable_load_avg =
+		div_u64(se_runnable(se) * se->avg.runnable_load_sum, divider);
 
+	__add_load_avg(cfs_rq, se);
+	if (se->on_rq) {
 		account_entity_enqueue(cfs_rq, se);
-		enqueue_entity_load_avg(cfs_rq, se);
+		enqueue_runnable_load_avg(cfs_rq, se);
 	}
-
-	add_positive(&cfs_rq->avg.load_avg,
-			(long)(se->avg.load_avg - se_load_avg));
-	add_positive(&cfs_rq->avg.load_sum,
-			(s64)(new_load_sum - se_load_sum));
 }
 
 static inline int throttled_hierarchy(struct cfs_rq *cfs_rq);
@@ -3523,8 +3529,7 @@ update_cfs_rq_load_avg(u64 now, struct c
 static void attach_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
 	se->avg.last_update_time = cfs_rq->avg.last_update_time;
-	cfs_rq->avg.load_avg += se->avg.load_avg;
-	cfs_rq->avg.load_sum += se_weight(se) * se->avg.load_sum;
+	__add_load_avg(cfs_rq, se);
 	cfs_rq->avg.util_avg += se->avg.util_avg;
 	cfs_rq->avg.util_sum += se->avg.util_sum;
 
@@ -3543,9 +3548,7 @@ static void attach_entity_load_avg(struc
  */
 static void detach_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
-
-	sub_positive(&cfs_rq->avg.load_avg, se->avg.load_avg);
-	sub_positive(&cfs_rq->avg.load_sum, se_weight(se) * se->avg.load_sum);
+	__sub_load_avg(cfs_rq, se);
 	sub_positive(&cfs_rq->avg.util_avg, se->avg.util_avg);
 	sub_positive(&cfs_rq->avg.util_sum, se->avg.util_sum);
 
@@ -3685,9 +3688,9 @@ static inline void update_load_avg(struc
 }
 
 static inline void
-enqueue_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se) {}
+enqueue_runnable_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se) {}
 static inline void
-dequeue_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se) {}
+dequeue_runnable_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se) {}
 static inline void remove_entity_load_avg(struct sched_entity *se) {}
 
 static inline void
@@ -3834,7 +3837,7 @@ enqueue_entity(struct cfs_rq *cfs_rq, st
 	 */
 	update_load_avg(cfs_rq, se, UPDATE_TG | DO_ATTACH);
 	update_cfs_group(se);
-	enqueue_entity_load_avg(cfs_rq, se);
+	enqueue_runnable_load_avg(cfs_rq, se);
 	account_entity_enqueue(cfs_rq, se);
 
 	if (flags & ENQUEUE_WAKEUP)
@@ -3917,7 +3920,7 @@ dequeue_entity(struct cfs_rq *cfs_rq, st
 	 *     of its group cfs_rq.
 	 */
 	update_load_avg(cfs_rq, se, UPDATE_TG);
-	dequeue_entity_load_avg(cfs_rq, se);
+	dequeue_runnable_load_avg(cfs_rq, se);
 
 	update_stats_dequeue(cfs_rq, se, flags);
 
author maintainer
#18 lore raw

RFC PATCH 11/14 sched/fair: Synchonous PELT detach on load-balance migrate

In reply to Peter Zijlstra

Vincent wondered why his self migrating task had a roughly 50% dip in load_avg when landing on the new CPU. This is because we uncondionally take the asynchronous detatch_entity route, which can lead to the attach on the new CPU still seeing the old CPU's contribution to tg->load_avg, effectively halving the new CPU's shares.

While in general this is something we have to live with, there is the special case of runnable migration where we can do better.

---
 kernel/sched/fair.c |   33 +++++++++++++++++++++------------
 1 file changed, 21 insertions(+), 12 deletions(-)
kernel/sched/fair.c +21 -12
@@ -3649,10 +3649,6 @@ void remove_entity_load_avg(struct sched
 	 * Similarly for groups, they will have passed through
 	 * post_init_entity_util_avg() before unregister_sched_fair_group()
 	 * calls this.
-	 *
-	 * XXX in case entity_is_task(se) && task_of(se)->on_rq == MIGRATING
-	 * we could actually get the right time, since we're called with
-	 * rq->lock held, see detach_task().
 	 */
 
 	sync_entity_load_avg(se);
@@ -6251,6 +6247,8 @@ select_task_rq_fair(struct task_struct *
 	return new_cpu;
 }
 
+static void detach_entity_cfs_rq(struct sched_entity *se);
+
 /*
  * Called immediately before a task is migrated to a new cpu; task_cpu(p) and
  * cfs_rq_of(p) references at time of call are still valid and identify the
@@ -6284,14 +6282,25 @@ static void migrate_task_rq_fair(struct
 		se->vruntime -= min_vruntime;
 	}
 
-	/*
-	 * We are supposed to update the task to "current" time, then its up to date
-	 * and ready to go to new CPU/cfs_rq. But we have difficulty in getting
-	 * what current time is, so simply throw away the out-of-date time. This
-	 * will result in the wakee task is less decayed, but giving the wakee more
-	 * load sounds not bad.
-	 */
-	remove_entity_load_avg(&p->se);
+	if (p->on_rq == TASK_ON_RQ_MIGRATING) {
+		/*
+		 * In case of TASK_ON_RQ_MIGRATING we in fact hold the 'old'
+		 * rq->lock and can modify state directly.
+		 */
+		lockdep_assert_held(&task_rq(p)->lock);
+		detach_entity_cfs_rq(&p->se);
+
+	} else {
+		/*
+		 * We are supposed to update the task to "current" time, then
+		 * its up to date and ready to go to new CPU/cfs_rq. But we
+		 * have difficulty in getting what current time is, so simply
+		 * throw away the out-of-date time. This will result in the
+		 * wakee task is less decayed, but giving the wakee more load
+		 * sounds not bad.
+		 */
+		remove_entity_load_avg(&p->se);
+	}
 
 	/* Tell new CPU we are migrated */
 	p->se.avg.last_update_time = 0;
author maintainer
#19 lore raw

RFC PATCH 12/14 sched/fair: Cure calc_cfs_shares() vs reweight_entity()

In reply to Peter Zijlstra

Vincent reported that when running in a cgroup, his root cfs_rq->avg.load_avg dropped to 0 on task idle.

This is because reweight_entity() will now immediately propagate the weight change of the group entity to its cfs_rq, and as it happens, our approxmation (5) for calc_cfs_shares() results in 0 when the group is idle.

Avoid this by using the correct (3) as a lower bound on (5). This way the empty cgroup will slowly decay instead of instantly drop to 0.

---
 kernel/sched/fair.c |    7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)
kernel/sched/fair.c +3 -4
@@ -2703,11 +2703,10 @@ static long calc_cfs_shares(struct cfs_r
 	tg_shares = READ_ONCE(tg->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.
+	 * Because (5) drops to 0 when the cfs_rq is idle, we need to use (3)
+	 * as a lower bound.
 	 */
-	load = scale_load_down(cfs_rq->load.weight);
+	load = max(scale_load_down(cfs_rq->load.weight), cfs_rq->avg.load_avg);
 
 	tg_weight = atomic_long_read(&tg->load_avg);
 
author maintainer
#20 lore raw

RFC PATCH 13/14 sched/fair: Align PELT windows between cfs_rq and its se

In reply to Peter Zijlstra

The PELT _sum values are a saw-tooth function, dropping on the decay edge and then growing back up again during the window.

When these window-edges are not aligned between cfs_rq and se, we can have the situation where, for example, on dequeue, the se decays first.

Its _sum values will be small(er), while the cfs_rq _sum values will still be on their way up. Because of this, the subtraction:
cfs_rq->avg._sum -= se->avg._sum will result in a positive value. This will then, once the cfs_rq reaches an edge, translate into its _avg value jumping up.

This is especially visible with the runnable_load bits, since they get added/subtracted a lot.

---
 kernel/sched/fair.c |   45 +++++++++++++++++++++++++++++++--------------
 1 file changed, 31 insertions(+), 14 deletions(-)
kernel/sched/fair.c +31 -14
@@ -729,13 +729,8 @@ void init_entity_runnable_average(struct
 {
 	struct sched_avg *sa = &se->avg;
 
-	sa->last_update_time = 0;
-	/*
-	 * sched_avg's period_contrib should be strictly less then 1024, so
-	 * we give it 1023 to make sure it is almost a period (1024us), and
-	 * will definitely be update (after enqueue).
-	 */
-	sa->period_contrib = 1023;
+	memset(sa, 0, sizeof(*sa));
+
 	/*
 	 * Tasks are intialized with full load to be seen as heavy tasks until
 	 * they get a chance to stabilize to their real load level.
@@ -744,13 +739,9 @@ void init_entity_runnable_average(struct
 	 */
 	if (entity_is_task(se))
 		sa->runnable_load_avg = sa->load_avg = scale_load_down(se->load.weight);
-	sa->runnable_load_sum = sa->load_sum = LOAD_AVG_MAX;
 
-	/*
-	 * At this point, util_avg won't be used in select_task_rq_fair anyway
-	 */
-	sa->util_avg = 0;
-	sa->util_sum = 0;
+	se->runnable_weight = se->load.weight;
+
 	/* when this task enqueue'ed, it will contribute to its cfs_rq's load_avg */
 }
 
@@ -798,7 +789,6 @@ void post_init_entity_util_avg(struct sc
 		} else {
 			sa->util_avg = cap;
 		}
-		sa->util_sum = sa->util_avg * LOAD_AVG_MAX;
 	}
 
 	if (entity_is_task(se)) {
@@ -3527,7 +3517,34 @@ update_cfs_rq_load_avg(u64 now, struct c
  */
 static void attach_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
+	u32 divider = LOAD_AVG_MAX - 1024 + cfs_rq->avg.period_contrib;
+
+	/*
+	 * When we attach the @se to the @cfs_rq, we must align the decay
+	 * window because without that, really weird and wonderful things can
+	 * happen.
+	 *
+	 * XXX illustrate
+	 */
 	se->avg.last_update_time = cfs_rq->avg.last_update_time;
+	se->avg.period_contrib = cfs_rq->avg.period_contrib;
+
+	/*
+	 * Hell(o) Nasty stuff.. we need to recompute _sum based on the new
+	 * period_contrib. This isn't strictly correct, but since we're
+	 * entirely outside of the PELT hierarchy, nobody cares if we truncate
+	 * _sum a little.
+	 */
+	se->avg.util_sum = se->avg.util_avg * divider;
+
+	se->avg.load_sum = divider;
+	if (se_weight(se)) {
+		se->avg.load_sum =
+			div_u64(se->avg.load_avg * se->avg.load_sum, se_weight(se));
+	}
+
+	se->avg.runnable_load_sum = se->avg.load_sum;
+
 	__add_load_avg(cfs_rq, se);
 	cfs_rq->avg.util_avg += se->avg.util_avg;
 	cfs_rq->avg.util_sum += se->avg.util_sum;
author maintainer
#21 lore raw

RFC PATCH 14/14 sched/fair: More accurate async detach

In reply to Peter Zijlstra

The problem with the overestimate is that it will subtract too big a value from the load_sum, thereby pushing it down further than it ought to go. Since runnable_load_avg is not subject to a similar 'force', this results in the occasional 'runnable_load > load' situation.

---
 kernel/sched/fair.c |    9 +++------
 1 file changed, 3 insertions(+), 6 deletions(-)
kernel/sched/fair.c +3 -6
@@ -3469,6 +3469,7 @@ update_cfs_rq_load_avg(u64 now, struct c
 
 	if (cfs_rq->removed.nr) {
 		unsigned long r;
+		u32 divider = LOAD_AVG_MAX - 1024 + sa->period_contrib;
 
 		raw_spin_lock(&cfs_rq->removed.lock);
 		swap(cfs_rq->removed.util_avg, removed_util);
@@ -3477,17 +3478,13 @@ update_cfs_rq_load_avg(u64 now, struct c
 		cfs_rq->removed.nr = 0;
 		raw_spin_unlock(&cfs_rq->removed.lock);
 
-		/*
-		 * The LOAD_AVG_MAX for _sum is a slight over-estimate,
-		 * which is safe due to sub_positive() clipping at 0.
-		 */
 		r = removed_load;
 		sub_positive(&sa->load_avg, r);
-		sub_positive(&sa->load_sum, r * LOAD_AVG_MAX);
+		sub_positive(&sa->load_sum, r * divider);
 
 		r = removed_util;
 		sub_positive(&sa->util_avg, r);
-		sub_positive(&sa->util_sum, r * LOAD_AVG_MAX);
+		sub_positive(&sa->util_sum, r * divider);
 
 		add_tg_cfs_propagate(cfs_rq, -(long)removed_runnable_sum);
 
#22 lore raw
In reply to Peter Zijlstra

Hello,

Quoted 15 lines · Peter Zijlstra

Hi all,

So after staring at all that PELT stuff and working my way through it again:

https://lkml.kernel.org/r/[email protected]

I started doing some patches to fix some of the identified broken.

So here are a few too many patches that do:

- fix 'reweight_entity' to instantly propagate the change in se->load.weight.

- rewrite/fix the propagate on migrate (attach/detach)

Quoted 8 lines

- introduce the hierarchical runnable_load_avg, as proposed by Tejun.

- synchronous detach for runnable migrates

- aligns the PELT windows between a cfs_rq and all its se's

- deals with random fallout from the above (some of this needs folding back and reordering, but its all well past the point I should post this anyway).

The schbench results look good here. I'll put it under more realistic test tomorrow and see how it performs.

Thanks.

Signature · 1 line
tejun
author maintainer
#23 lore raw
Quoted 22 lines · Tejun Heo

Hello,

Quoted 19 lines · Peter Zijlstra

Hi all,

So after staring at all that PELT stuff and working my way through it again:

https://lkml.kernel.org/r/[email protected]

I started doing some patches to fix some of the identified broken.

So here are a few too many patches that do:

- fix 'reweight_entity' to instantly propagate the change in se->load.weight.

- rewrite/fix the propagate on migrate (attach/detach)

- introduce the hierarchical runnable_load_avg, as proposed by Tejun.

- synchronous detach for runnable migrates

Quoted 7 lines
Quoted 4 lines

- aligns the PELT windows between a cfs_rq and all its se's

- deals with random fallout from the above (some of this needs folding back and reordering, but its all well past the point I should post this anyway).

The schbench results look good here. I'll put it under more realistic test tomorrow and see how it performs.

Josef reported some problems with these patches and narrowed it down to:

"sched/fair: Remove se->load.weight from se->avg.load_sum"

I'm currently stuck chasing a regression in other code, but I'll try and get back to this shortly.