Skip to contentSkip to conversation

sched: Rewrite per entity runnable load average tracking

PATCH Superseded Yuyang Du 3 participants 8 messages Jul 14, 2014 – Jul 16, 2014 Scheduler

v2 of 10 Superseded Latest is v10 →

lore
Share & tools
lore

Yuyang Du

author
#0 lore raw

v2 cover sched: Rewrite per entity runnable load average tracking

This patchset is really imbalanced in size.

The 1/2 patch is not simply resending, but for two reasons: 1) this rewrite does not include rq's runnable load_avg, and 2) more importantly, I want to reduce the size of the 2/2 patch, this is the only way I know how.

The 2/2 patch is very big. Sorry for that, but as this patch is a rewrite, I can only do it in an all-or-nothing manner. Splitting it will not make each small one compile or correctly function.

I'd like to thank PeterZ and Ben for their help in fixing the issues and improving the quality in this version. And Fengguang and his 0Day in finding compile errors in different configurations.

v2 changes:

- Batch update the tg->load_avg, making sure it is up-to-date before update_cfs_shares
- Remove migrating task from the old CPU/cfs_rq, and do so with atomic operations
- Retrack lod_avg of group's entities (if any), since we need it in task_h_load calc, and do it along with its own cfs_rq's update
- Fix 32bit overflow issue of cfs_rq's load_avg, now it is 64bit, should be safe
- Change load.weight in effective_load which uses runnable load_avg consistently

Yuyang Du (2):
sched: Remove update_rq_runnable_avg
sched: Rewrite per entity runnable load average tracking

 include/linux/sched.h |   13 +-
 kernel/sched/debug.c  |   32 +--
 kernel/sched/fair.c   |  644 ++++++++++++++++++++-----------------------------
 kernel/sched/proc.c   |    2 +-
 kernel/sched/sched.h  |   34 +--
 5 files changed, 287 insertions(+), 438 deletions(-)
Signature · 1 line
1.7.9.5
author
#1 lore raw

PATCH v2 1/2 sched: Remove update_rq_runnable_avg

The current rq->avg is not made use of anywhere, and the code is in fair scheduler's critical path, so remove it.

---
 kernel/sched/debug.c |    8 --------
 kernel/sched/fair.c  |   24 ++++--------------------
 kernel/sched/sched.h |    2 --
 3 files changed, 4 insertions(+), 30 deletions(-)
kernel/sched/debug.c +0 -8
index 695f977..4b864c7 100644
@@ -68,14 +68,6 @@ static void print_cfs_group_stats(struct seq_file *m, int cpu, struct task_group
 #define PN(F) \
 	SEQ_printf(m, "  .%-30s: %lld.%06ld\n", #F, SPLIT_NS((long long)F))
 
-	if (!se) {
-		struct sched_avg *avg = &cpu_rq(cpu)->avg;
-		P(avg->runnable_avg_sum);
-		P(avg->runnable_avg_period);
-		return;
-	}
-
-
 	PN(se->exec_start);
 	PN(se->vruntime);
 	PN(se->sum_exec_runtime);
kernel/sched/fair.c +4 -20
index fea7d33..1a2d04f 100644
@@ -2430,18 +2430,12 @@ static inline void __update_group_entity_contrib(struct sched_entity *se)
 	}
 }
 
-static inline void update_rq_runnable_avg(struct rq *rq, int runnable)
-{
-	__update_entity_runnable_avg(rq_clock_task(rq), &rq->avg, runnable);
-	__update_tg_runnable_avg(&rq->avg, &rq->cfs);
-}
 #else /* CONFIG_FAIR_GROUP_SCHED */
 static inline void __update_cfs_rq_tg_load_contrib(struct cfs_rq *cfs_rq,
 						 int force_update) {}
 static inline void __update_tg_runnable_avg(struct sched_avg *sa,
 						  struct cfs_rq *cfs_rq) {}
 static inline void __update_group_entity_contrib(struct sched_entity *se) {}
-static inline void update_rq_runnable_avg(struct rq *rq, int runnable) {}
 #endif /* CONFIG_FAIR_GROUP_SCHED */
 
 static inline void __update_task_entity_contrib(struct sched_entity *se)
@@ -2614,7 +2608,6 @@ static inline void dequeue_entity_load_avg(struct cfs_rq *cfs_rq,
  */
 void idle_enter_fair(struct rq *this_rq)
 {
-	update_rq_runnable_avg(this_rq, 1);
 }
 
 /*
@@ -2624,7 +2617,6 @@ void idle_enter_fair(struct rq *this_rq)
  */
 void idle_exit_fair(struct rq *this_rq)
 {
-	update_rq_runnable_avg(this_rq, 0);
 }
 
 static int idle_balance(struct rq *this_rq);
@@ -2633,7 +2625,6 @@ static int idle_balance(struct rq *this_rq);
 
 static inline void update_entity_load_avg(struct sched_entity *se,
 					  int update_cfs_rq) {}
-static inline void update_rq_runnable_avg(struct rq *rq, int runnable) {}
 static inline void enqueue_entity_load_avg(struct cfs_rq *cfs_rq,
 					   struct sched_entity *se,
 					   int wakeup) {}
@@ -3936,10 +3927,9 @@ enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
 		update_entity_load_avg(se, 1);
 	}
 
-	if (!se) {
-		update_rq_runnable_avg(rq, rq->nr_running);
+	if (!se)
 		add_nr_running(rq, 1);
-	}
+
 	hrtick_update(rq);
 }
 
@@ -3997,10 +3987,9 @@ static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags)
 		update_entity_load_avg(se, 1);
 	}
 
-	if (!se) {
+	if (!se)
 		sub_nr_running(rq, 1);
-		update_rq_runnable_avg(rq, 1);
-	}
+
 	hrtick_update(rq);
 }
 
@@ -5437,9 +5426,6 @@ static void __update_blocked_averages_cpu(struct task_group *tg, int cpu)
 		 */
 		if (!se->avg.runnable_avg_sum && !cfs_rq->nr_running)
 			list_del_leaf_cfs_rq(cfs_rq);
-	} else {
-		struct rq *rq = rq_of(cfs_rq);
-		update_rq_runnable_avg(rq, rq->nr_running);
 	}
 }
 
@@ -7352,8 +7338,6 @@ static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
 
 	if (numabalancing_enabled)
 		task_tick_numa(rq, curr);
-
-	update_rq_runnable_avg(rq, 1);
 }
 
 /*
kernel/sched/sched.h +0 -2
index 31cc02e..a147571 100644
@@ -542,8 +542,6 @@ struct rq {
 #ifdef CONFIG_FAIR_GROUP_SCHED
 	/* list of leaf cfs_rq on this cpu: */
 	struct list_head leaf_cfs_rq_list;
-
-	struct sched_avg avg;
 #endif /* CONFIG_FAIR_GROUP_SCHED */
 
 	/*
Signature · 1 line
1.7.9.5
author
#2 lore raw

PATCH v2 2/2 sched: Rewrite per entity runnable load average tracking

In reply to Yuyang Du

The idea of per entity runnable load average (let runnable time contribute to load weight) was proposed by Paul Turner, and it is still followed by this rewrite. This rewrite is done due to the following ends:

1. cfs_rq's load average (namely runnable_load_avg and blocked_load_avg) is updated at the granularity of one entity at one time, which results in the cfs_rq load average is partially updated or asynchronous across its entities: at any time, only one entity is up to date and contributes to the cfs_rq, all other entities are effectively lagging behind.

2. cfs_rq load average is different between top rq->cfs_rq and other task_group's per CPU cfs_rqs in whether or not blocked_load_average contributes to the load.

3. How task_group's load is calculated is complex.

This rewrite tackles these by:

1. Combine runnable and blocked load averages for cfs_rq. And track cfs_rq's load average as a whole.

2. Track task entity load average for carrying it between CPUs in migration, cfs_rq and its own entity load averages are tracked together.

3. All task, cfs_rq/group_entity, and task_group have a consistent and synchronized load_avg.

This rewrite in principle is equivalent to the previous in functionality, but significantly reduces code coplexity and hence increases efficiency and clarity.

In addition, the new load_avg is much more smooth/continuous (no abrupt jumping ups and downs) and decayed/updated more quickly and synchronously to reflect the load dynamic.

---
 include/linux/sched.h |   13 +-
 kernel/sched/debug.c  |   24 +-
 kernel/sched/fair.c   |  620 ++++++++++++++++++++-----------------------------
 kernel/sched/proc.c   |    2 +-
 kernel/sched/sched.h  |   32 +--
 5 files changed, 283 insertions(+), 408 deletions(-)
include/linux/sched.h +5 -8
index 306f4f0..7abdd13 100644
@@ -1069,14 +1069,11 @@ struct load_weight {
 
 struct sched_avg {
 	/*
-	 * These sums represent an infinite geometric series and so are bound
-	 * above by 1024/(1-y).  Thus we only need a u32 to store them for all
-	 * choices of y < 1-2^(-32)*1024.
+	 * The load_avg represents an infinite geometric series.
 	 */
-	u32 runnable_avg_sum, runnable_avg_period;
-	u64 last_runnable_update;
-	s64 decay_count;
-	unsigned long load_avg_contrib;
+	u32 load_avg;
+	u32 period_contrib;
+	u64 last_update_time;
 };
 
 #ifdef CONFIG_SCHEDSTATS
@@ -1142,7 +1139,7 @@ struct sched_entity {
 #endif
 
 #ifdef CONFIG_SMP
-	/* Per-entity load-tracking */
+	/* Per task load tracking */
 	struct sched_avg	avg;
 #endif
 };
kernel/sched/debug.c +5 -19
index 4b864c7..8e2fada 100644
@@ -85,10 +85,7 @@ static void print_cfs_group_stats(struct seq_file *m, int cpu, struct task_group
 #endif
 	P(se->load.weight);
 #ifdef CONFIG_SMP
-	P(se->avg.runnable_avg_sum);
-	P(se->avg.runnable_avg_period);
-	P(se->avg.load_avg_contrib);
-	P(se->avg.decay_count);
+	P(se->my_q->avg.load_avg);
 #endif
 #undef PN
 #undef P
@@ -205,19 +202,11 @@ void print_cfs_rq(struct seq_file *m, int cpu, struct cfs_rq *cfs_rq)
 	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_load_avg",
-			cfs_rq->runnable_load_avg);
-	SEQ_printf(m, "  .%-30s: %ld\n", "blocked_load_avg",
-			cfs_rq->blocked_load_avg);
+	SEQ_printf(m, "  .%-30s: %llu\n", "load_avg",
+			cfs_rq->avg.load_avg);
 #ifdef CONFIG_FAIR_GROUP_SCHED
-	SEQ_printf(m, "  .%-30s: %ld\n", "tg_load_contrib",
-			cfs_rq->tg_load_contrib);
-	SEQ_printf(m, "  .%-30s: %d\n", "tg_runnable_contrib",
-			cfs_rq->tg_runnable_contrib);
 	SEQ_printf(m, "  .%-30s: %ld\n", "tg_load_avg",
-			atomic_long_read(&cfs_rq->tg->load_avg));
-	SEQ_printf(m, "  .%-30s: %d\n", "tg->runnable_avg",
-			atomic_read(&cfs_rq->tg->runnable_avg));
+			atomic64_read(&cfs_rq->tg->load_avg));
 #endif
 #endif
 #ifdef CONFIG_CFS_BANDWIDTH
@@ -624,10 +613,7 @@ void proc_sched_show_task(struct task_struct *p, struct seq_file *m)
 
 	P(se.load.weight);
 #ifdef CONFIG_SMP
-	P(se.avg.runnable_avg_sum);
-	P(se.avg.runnable_avg_period);
-	P(se.avg.load_avg_contrib);
-	P(se.avg.decay_count);
+	P(se.avg.load_avg);
 #endif
 	P(policy);
 	P(prio);
kernel/sched/fair.c +254 -366

903 lines not on this page · raw message

kernel/sched/proc.c +1 -1
index 16f5a30..8f547fe 100644
@@ -504,7 +504,7 @@ static void __update_cpu_load(struct rq *this_rq, unsigned long this_load,
 #ifdef CONFIG_SMP
 static inline unsigned long get_rq_runnable_load(struct rq *rq)
 {
-	return rq->cfs.runnable_load_avg;
+	return rq->cfs.avg.load_avg;
 }
 #else
 static inline unsigned long get_rq_runnable_load(struct rq *rq)
kernel/sched/sched.h +18 -14
index a147571..7cf0c75 100644
@@ -209,8 +209,7 @@ struct task_group {
 	unsigned long shares;
 
 #ifdef	CONFIG_SMP
-	atomic_long_t load_avg;
-	atomic_t runnable_avg;
+	atomic64_t load_avg;
 #endif
 #endif
 
@@ -305,6 +304,19 @@ struct cfs_bandwidth { };
 
 #endif	/* CONFIG_CGROUP_SCHED */
 
+#ifdef CONFIG_SMP
+struct sched_avg_cfs_rq {
+	/*
+	 * The load_avg represents an infinite geometric series. The 64 bit
+	 * load_avg can afford 4353082796 (=2^64/47742/88761) entities with
+	 * the highest weight (=88761) always runnable, we should not overflow
+	 */
+	u64 load_avg;
+	u32 period_contrib;
+	u64 last_update_time;
+};
+#endif
+
 /* CFS-related fields in a runqueue */
 struct cfs_rq {
 	struct load_weight load;
@@ -331,21 +343,13 @@ struct cfs_rq {
 
 #ifdef CONFIG_SMP
 	/*
-	 * CFS Load tracking
-	 * Under CFS, load is tracked on a per-entity basis and aggregated up.
-	 * This allows for the description of both thread and group usage (in
-	 * the FAIR_GROUP_SCHED case).
+	 * CFS load tracking
 	 */
-	unsigned long runnable_load_avg, blocked_load_avg;
-	atomic64_t decay_counter;
-	u64 last_decay;
-	atomic_long_t removed_load;
+	struct sched_avg_cfs_rq avg;
+	u64 tg_load_avg_contrib;
+	atomic_long_t removed_load_avg;
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
-	/* Required to track per-cpu representation of a task_group */
-	u32 tg_runnable_contrib;
-	unsigned long tg_load_contrib;
-
 	/*
 	 *   h_load = weight * f(tg)
 	 *
Signature · 1 line
1.7.9.5
#3 lore raw
Quoted 6 lines · Yuyang Du
include/linux/sched.h +0 -0
@@ -1069,14 +1069,11 @@ struct load_weight {
 
 struct sched_avg {
 	/*

include/linux/sched.h struct load_weight { · line 1074

Quoted 10 lines
include/linux/sched.h +2 -7
-	 * These sums represent an infinite geometric series and so are bound
-	 * above by 1024/(1-y).  Thus we only need a u32 to store them for all
-	 * choices of y < 1-2^(-32)*1024.
+	 * The load_avg represents an infinite geometric series.
 	 */
-	u32 runnable_avg_sum, runnable_avg_period;
-	u64 last_runnable_update;
-	s64 decay_count;
-	unsigned long load_avg_contrib;
+	u32 load_avg;

This should probably be unsigned long (it can still overflow on 32-bit if the user picks ~90000 as a cgroup weight, but so it goes).

Quoted 13 lines
kernel/sched/fair.c +0 -3
@@ -282,9 +282,6 @@ static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
 	return grp->my_q;
 }
 
-static void update_cfs_rq_blocked_load(struct cfs_rq *cfs_rq,
-				       int force_update);
-
 static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
 {
 	if (!cfs_rq->on_list) {

kernel/sched/fair.c static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq) · line 308

Quoted 5 lines
kernel/sched/fair.c +0 -2
@@ -304,8 +301,6 @@ static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
 		}
 
 		cfs_rq->on_list = 1;
-		/* We should have no load, but we need to update last_decay. */
-		update_cfs_rq_blocked_load(cfs_rq, 0);

AFAICT this call was nonsense before your change, yes (it gets called by enqueue_entity_load_avg)?

Quoted 8 lines
kernel/sched/fair.c +0 -1
 	}
 }
 
@@ -667,18 +662,17 @@ static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)
 #ifdef CONFIG_SMP
 static unsigned long task_h_load(struct task_struct *p);
 
-static inline void __update_task_entity_contrib(struct sched_entity *se);

kernel/sched/fair.c static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se) · line 672

Quoted 10 lines
kernel/sched/fair.c +3 -2
-
 /* Give new task start runnable values to heavy its load in infant time */
 void init_task_runnable_average(struct task_struct *p)
 {
 	u32 slice;
+	struct sched_avg *sa = &p->se.avg;
 
-	p->se.avg.decay_count = 0;
+	sa->last_update_time = 0;
+	sa->period_contrib = 0;

sa->period_contrib = slice;

Quoted 16 lines
kernel/sched/fair.c +3 -5
 	slice = sched_slice(task_cfs_rq(p), &p->se) >> 10;
-	p->se.avg.runnable_avg_sum = slice;
-	p->se.avg.runnable_avg_period = slice;
-	__update_task_entity_contrib(&p->se);
+	sa->load_avg = slice * p->se.load.weight;
+	/* when this task enqueue'ed, it will contribute to its cfs_rq's load_avg */
 }
 #else
 void init_task_runnable_average(struct task_struct *p)
@@ -1504,8 +1498,17 @@ static u64 numa_get_avg_runtime(struct task_struct *p, u64 *period)
 		delta = runtime - p->last_sum_exec_runtime;
 		*period = now - p->last_task_numa_placement;
 	} else {
-		delta = p->se.avg.runnable_avg_sum;
-		*period = p->se.avg.runnable_avg_period;
+		/*

kernel/sched/fair.c static u64 numa_get_avg_runtime(struct task_struct *p, u64 *period) · line 1511

Quoted 10 lines
kernel/sched/fair.c +10 -0
+		 * XXX previous runnable_avg_sum and runnable_avg_period are
+		 * only used here. May find a way to better suit NUMA here.
+		 */
+
+		delta = p->se.avg.load_avg / p->se.load.weight;
+#ifndef LOAD_AVG_MAX
+#define LOAD_AVG_MAX 47742
+		*period = LOAD_AVG_MAX;
+#undef LOAD_AVG_MAX
+#endif

#ifdef LOAD_AVG_MAX
*period = LOAD_AVG_MAX
#else
*period = 47742
#endif

Quoted 6 lines
kernel/sched/fair.c +0 -0
 	}
 
 	p->last_sum_exec_runtime = runtime;
@@ -2071,13 +2074,9 @@ static inline long calc_tg_weight(struct task_group *tg, struct cfs_rq *cfs_rq)
 	long tg_weight;
 

kernel/sched/fair.c static inline long calc_tg_weight(struct task_group *tg, struct cfs_rq *cfs_rq) · line 2079

Quoted 10 lines
kernel/sched/fair.c +2 -6
 	/*
-	 * Use this CPU's actual weight instead of the last load_contribution
-	 * to gain a more accurate current total weight. See
-	 * update_cfs_rq_load_contribution().
+	 * Use this CPU's load average instead of actual weight
 	 */
-	tg_weight = atomic_long_read(&tg->load_avg);
-	tg_weight -= cfs_rq->tg_load_contrib;
-	tg_weight += cfs_rq->load.weight;
+	tg_weight = atomic64_read(&tg->load_avg);

You could do the load_contrib thing again. Also while you made tg->load_avg 64-bit, this is still a long, so you still lose.

Quoted 17 lines
kernel/sched/fair.c +2 -1
 	return tg_weight;
 }
@@ -2087,7 +2086,7 @@ static long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
 	long tg_weight, load, shares;
 
 	tg_weight = calc_tg_weight(tg, cfs_rq);
-	load = cfs_rq->load.weight;
+	load = cfs_rq->avg.load_avg;
 
 	shares = (tg->shares * load);
 	if (tg_weight)
@@ -2210,6 +2209,28 @@ static __always_inline u64 decay_load(u64 val, u64 n)
 	return val >> 32;
 }
 
+static __always_inline u64 decay_load64(u64 val, u64 n)

kernel/sched/fair.c static __always_inline u64 decay_load(u64 val, u64 n) · line 2222

Quoted 10 lines
kernel/sched/fair.c +10 -0
+{
+	if (likely(val <= UINT_MAX))
+		val = decay_load(val, n);
+	else {
+		/*
+		 * LOAD_AVG_MAX can last ~500ms (=log_2(LOAD_AVG_MAX)*32ms).
+		 * Since we have so big runnable load_avg, it is impossible
+		 * load_avg has not been updated for such a long time. So
+		 * LOAD_AVG_MAX is enough here.
+		 */

I mean, LOAD_AVG_MAX is irrelevant - the constant could just as well be 1<<20, or whatever, yes? In fact, if you're going to then turn it into a fraction of 1<<10, just do (with whatever temporaries you find most tasteful):

val *= (u32) decay_load(1 << 10, n);
val >>= 10;

Quoted 9 lines
kernel/sched/fair.c +9 -0
+		u32 factor = decay_load(LOAD_AVG_MAX, n);
+
+		factor <<= 10;
+		factor /= LOAD_AVG_MAX;
+		val *= factor;
+		val >>= 10;
+	}
+
+	return val;

kernel/sched/fair.c static __always_inline u64 decay_load(u64 val, u64 n)

Quoted 10 lines
kernel/sched/fair.c +7 -0
+}
 
[...]
 
+/*
+ * Strictly, this se should use its parent cfs_rq's clock_task, but
+ * here we use its own cfs_rq's for performance matter. But on load_avg
+ * update, what we really care about is "the difference between two regular
+ * clock reads", not absolute time, so the variation should be neglectable.
+ */

Yes, but the difference between two clock reads can differ vastly depending on which clock you read - if cfs_rq was throttled, but parent_cfs_rq was not, reading cfs_rq's clock will give you no time passing. That said I think that's probably what you want for cfs_rq's load_avg, but is wrong for the group se, which probably needs to use its parent's.

Quoted 1 line

+static __always_inline void __update_cfs_rq_load_avg(u64 now, struct cfs_rq *cfs_rq)

Massive code duplication here makes me sad, although it's not clear how to avoid it without doing unnecessary u64 math on se load_avgs.

Quoted 7 lines
kernel/sched/fair.c +5 -0
+/* Update task and its cfs_rq load average */
+static inline void update_load_avg(struct sched_entity *se, int update_tg)
 {
+	struct cfs_rq *cfs_rq = cfs_rq_of(se);
+	u64 now = cfs_rq_clock_task(cfs_rq);
+
 	/*

kernel/sched/fair.c static __always_inline int __update_entity_runnable_avg(u64 now, · line 2506

Quoted 10 lines
kernel/sched/fair.c +6 -0
+	 * Track task load average for carrying it to new CPU after migrated
 	 */
+	if (entity_is_task(se))
+		__update_load_avg(now, &se->avg, se->on_rq * se->load.weight);
 
+	update_cfs_rq_load_avg(now, cfs_rq);
 
+	if (update_tg)
+		update_tg_load_avg(cfs_rq);
 }

I personally find this very confusing, in that update_load_avg is doing more to se->cfs_rq, and in fact on anything other than a task, it isn't touching the se at all (instead, it touches _se->parent_ even).

Quoted 44 lines
kernel/sched/proc.c +4 -4
index 16f5a30..8f547fe 100644
@@ -504,7 +504,7 @@ static void __update_cpu_load(struct rq *this_rq, unsigned long this_load,
 #ifdef CONFIG_SMP
 static inline unsigned long get_rq_runnable_load(struct rq *rq)
 {
-	return rq->cfs.runnable_load_avg;
+	return rq->cfs.avg.load_avg;
 }
 #else
 static inline unsigned long get_rq_runnable_load(struct rq *rq)
@@ -3997,7 +3918,7 @@ static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags)
 /* Used instead of source_load when we know the type == 0 */
 static unsigned long weighted_cpuload(const int cpu)
 {
-	return cpu_rq(cpu)->cfs.runnable_load_avg;
+	return cpu_rq(cpu)->cfs.avg.load_avg;
 }
 
 /*
@@ -4042,7 +3963,7 @@ static unsigned long cpu_avg_load_per_task(int cpu)
 {
 	struct rq *rq = cpu_rq(cpu);
 	unsigned long nr_running = ACCESS_ONCE(rq->nr_running);
-	unsigned long load_avg = rq->cfs.runnable_load_avg;
+	unsigned long load_avg = rq->cfs.avg.load_avg;
 
 	if (nr_running)
 		return load_avg / nr_running;
@@ -4161,7 +4082,7 @@ static long effective_load(struct task_group *tg, int cpu, long wl, long wg)
 		/*
 		 * w = rw_i + @wl
 		 */
-		w = se->my_q->load.weight + wl;
+		w = se->my_q->avg.load_avg + wl;
 		/*
 		 * Recursively apply this logic to all parent groups to compute
@@ -4256,14 +4177,14 @@ static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync)
 	 */
 	if (sync) {
 		tg = task_group(current);

kernel/sched/proc.c static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync) · line 4187

Quoted 10 lines
kernel/sched/proc.c +2 -2
-		weight = current->se.load.weight;
+		weight = current->se.avg.load_avg;
 
 		this_load += effective_load(tg, this_cpu, -weight, -weight);
 		load += effective_load(tg, prev_cpu, 0, -weight);
 	}
 
 	tg = task_group(p);
-	weight = p->se.load.weight;
+	weight = p->se.avg.load_avg;

These all lose bits on 32-bit (weighted_cpuload did that already too), and it is likely a pain to fix them all.

Quoted 10 lines
kernel/sched/proc.c +0 -3
 	/*
 	 * In low-load situations, where prev_cpu is idle and this_cpu is idle
@@ -4553,16 +4474,20 @@ migrate_task_rq_fair(struct task_struct *p, int next_cpu)
 	struct cfs_rq *cfs_rq = cfs_rq_of(se);
 
 	/*
-	 * Load tracking: accumulate removed load so that it can be processed
-	 * when we next update owning cfs_rq under rq->lock.  Tasks contribute
-	 * to blocked load iff they have a positive decay-count.  It can never

kernel/sched/proc.c migrate_task_rq_fair(struct task_struct *p, int next_cpu) · line 4480

Quoted 10 lines
kernel/sched/proc.c +3 -6
-	 * be negative here since on-rq tasks have decay-count == 0.
+	 * Task on old CPU catches up with its old cfs_rq, and subtract itself from
+	 * the cfs_rq (task must be off the queue now).
 	 */
-	if (se->avg.decay_count) {
-		se->avg.decay_count = -__synchronize_entity_decay(se);
-		atomic_long_add(se->avg.load_avg_contrib,
-						&cfs_rq->removed_load);
-	}
+	__update_load_avg(cfs_rq->avg.last_update_time, &se->avg, 0);

This read of last_update_time needs to do the min_vruntime_copy trick on 32-bit.

Quoted 5 lines
kernel/sched/proc.c +0 -1
@@ -5477,14 +5372,14 @@ static void update_cfs_rq_h_load(struct cfs_rq *cfs_rq)
 	}
 
 	if (!se) {
-		cfs_rq->h_load = cfs_rq->runnable_load_avg;

kernel/sched/proc.c static void update_cfs_rq_h_load(struct cfs_rq *cfs_rq) · line 5382

Quoted 10 lines
kernel/sched/proc.c +3 -2
+		cfs_rq->h_load = cfs_rq->avg.load_avg;
 		cfs_rq->last_h_load_update = now;
 	}
 
 	while ((se = cfs_rq->h_load_next) != NULL) {
 		load = cfs_rq->h_load;
-		load = div64_ul(load * se->avg.load_avg_contrib,
-				cfs_rq->runnable_load_avg + 1);
+		load = div64_ul(load * se->avg.load_avg,
+				cfs_rq->avg.load_avg + 1);

This needs to be div64_u64 now (the prior one was actually kinda wrong in that it wasn't even a 64-bit multiply on 32-bit, and you might as well fix that too).

kernel/sched/proc.c static unsigned long task_h_load(struct task_struct *p) · line 5395

Quoted 11 lines
kernel/sched/proc.c +2 -2
 		cfs_rq = group_cfs_rq(se);
 		cfs_rq->h_load = load;
 		cfs_rq->last_h_load_update = now;
@@ -5496,8 +5391,8 @@ static unsigned long task_h_load(struct task_struct *p)
 	struct cfs_rq *cfs_rq = task_cfs_rq(p);
 
 	update_cfs_rq_h_load(cfs_rq);
-	return div64_ul(p->se.avg.load_avg_contrib * cfs_rq->h_load,
-			cfs_rq->runnable_load_avg + 1);
+	return div64_ul(p->se.avg.load_avg * cfs_rq->h_load,
+			cfs_rq->avg.load_avg + 1);

Same.

Quoted 5 lines
kernel/sched/proc.c +1 -0
@@ -7547,14 +7438,11 @@ static void task_move_group_fair(struct task_struct *p, int on_rq)
 	if (!on_rq) {
 		cfs_rq = cfs_rq_of(se);
 		se->vruntime += cfs_rq->min_vruntime;
+

kernel/sched/proc.c static void task_move_group_fair(struct task_struct *p, int on_rq) · line 7444

Quoted 10 lines
kernel/sched/proc.c +2 -7
 #ifdef CONFIG_SMP
-		/*
-		 * migrate_task_rq_fair() will have removed our previous
-		 * contribution, but we must synchronize for ongoing future
-		 * decay.
-		 */
-		se->avg.decay_count = atomic64_read(&cfs_rq->decay_counter);
-		cfs_rq->blocked_load_avg += se->avg.load_avg_contrib;
+		/* synchronize task with its new cfs_rq */
+		__update_load_avg(cfs_rq->avg.last_update_time, &p->se.avg, 0);

This will incorrectly decay for any time delta between groups, it should just be a set of last_update_time.

author
#4 lore raw

Thanks, Ben.

Quoted 15 lines · On Mon, Jul 14, 2014 at 12:33:53PM -0700, [email protected] wrote:
Quoted 15 lines
kernel/sched/fair.c +0 -3
@@ -282,9 +282,6 @@ static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
 	return grp->my_q;
 }
 
-static void update_cfs_rq_blocked_load(struct cfs_rq *cfs_rq,
-				       int force_update);
-
 static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
 {
 	if (!cfs_rq->on_list) {
@@ -304,8 +301,6 @@ static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
 		}
 
Quoted 7 lines

kernel/sched/fair.c static inline void list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq) · line 308

Quoted 3 lines
kernel/sched/fair.c +0 -2
 		cfs_rq->on_list = 1;
-		/* We should have no load, but we need to update last_decay. */
-		update_cfs_rq_blocked_load(cfs_rq, 0);

AFAICT this call was nonsense before your change, yes (it gets called by enqueue_entity_load_avg)?

Yes, I think so.

Quoted 12 lines
Quoted 12 lines
kernel/sched/fair.c +1 -2
@@ -667,18 +662,17 @@ static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)
 #ifdef CONFIG_SMP
 static unsigned long task_h_load(struct task_struct *p);
 
-static inline void __update_task_entity_contrib(struct sched_entity *se);
-
 /* Give new task start runnable values to heavy its load in infant time */
 void init_task_runnable_average(struct task_struct *p)
 {
 	u32 slice;
+	struct sched_avg *sa = &p->se.avg;
 
Quoted 5 lines

kernel/sched/fair.c static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se) · line 672

Quoted 3 lines
kernel/sched/fair.c +2 -1
-	p->se.avg.decay_count = 0;
+	sa->last_update_time = 0;
+	sa->period_contrib = 0;

sa->period_contrib = slice;

period_contrib should be strictly < 1024. I suppose sched_slice does not guarantee that. So here I will give it 1023 to heavy the load.

Quoted 16 lines

kernel/sched/fair.c static __always_inline u64 decay_load(u64 val, u64 n) · line 2222

Quoted 11 lines
kernel/sched/fair.c +11 -0
+static __always_inline u64 decay_load64(u64 val, u64 n)
+{
+	if (likely(val <= UINT_MAX))
+		val = decay_load(val, n);
+	else {
+		/*
+		 * LOAD_AVG_MAX can last ~500ms (=log_2(LOAD_AVG_MAX)*32ms).
+		 * Since we have so big runnable load_avg, it is impossible
+		 * load_avg has not been updated for such a long time. So
+		 * LOAD_AVG_MAX is enough here.
+		 */

I mean, LOAD_AVG_MAX is irrelevant - the constant could just as well be 1<<20, or whatever, yes? In fact, if you're going to then turn it into a fraction of 1<<10, just do (with whatever temporaries you find most tasteful):

Quoted 3 lines

val *= (u32) decay_load(1 << 10, n);
val >>= 10;

LOAD_AVG_MAX is selected on purpose. The val arriving here specifies that it is really big. So the decay_load may not decay it to 0 even period n is not small. If we use 1<<10 here, n=10*32 will decay it to 0, but val (larger than 1<<32) can survive.

But if even LOAD_AVG_MAX will decay to 0, it means in the current code, any runnable_avg_sum will not survive, sicne LOAD_AVG_MAX is the upperbound.

Quoted 7 lines
Quoted 6 lines

+/*
+ * Strictly, this se should use its parent cfs_rq's clock_task, but
+ * here we use its own cfs_rq's for performance matter. But on load_avg
+ * update, what we really care about is "the difference between two regular
+ * clock reads", not absolute time, so the variation should be neglectable.
+ */

Quoted 6 lines

Yes, but the difference between two clock reads can differ vastly depending on which clock you read - if cfs_rq was throttled, but parent_cfs_rq was not, reading cfs_rq's clock will give you no time passing. That said I think that's probably what you want for cfs_rq's load_avg, but is wrong for the group se, which probably needs to use its parent's.

Yes, then I think I may have to fall back to track group se load_avg alone.

Quoted 14 lines
Quoted 14 lines
kernel/sched/fair.c +9 -0
+/* Update task and its cfs_rq load average */
+static inline void update_load_avg(struct sched_entity *se, int update_tg)
 {
+	struct cfs_rq *cfs_rq = cfs_rq_of(se);
+	u64 now = cfs_rq_clock_task(cfs_rq);
+
 	/*
+	 * Track task load average for carrying it to new CPU after migrated
 	 */
+	if (entity_is_task(se))
+		__update_load_avg(now, &se->avg, se->on_rq * se->load.weight);
 
+	update_cfs_rq_load_avg(now, cfs_rq);
Quoted 7 lines

kernel/sched/fair.c static __always_inline int __update_entity_runnable_avg(u64 now, · line 2506

Quoted 3 lines
kernel/sched/fair.c +2 -0
+	if (update_tg)
+		update_tg_load_avg(cfs_rq);
 }

I personally find this very confusing, in that update_load_avg is doing more to se->cfs_rq, and in fact on anything other than a task, it isn't touching the se at all (instead, it touches _se->parent_ even).

What is confusing? The naming?

About the overflow problem, maybe I can just fall back to do load_avg / 47742 for every update, then everything would be in nature the same range with the current code.

#5 lore raw
Quoted 12 lines · Yuyang Du
Quoted 12 lines
Quoted 12 lines
kernel/sched/fair.c +1 -2
@@ -667,18 +662,17 @@ static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)
 #ifdef CONFIG_SMP
 static unsigned long task_h_load(struct task_struct *p);
 
-static inline void __update_task_entity_contrib(struct sched_entity *se);
-
 /* Give new task start runnable values to heavy its load in infant time */
 void init_task_runnable_average(struct task_struct *p)
 {
 	u32 slice;
+	struct sched_avg *sa = &p->se.avg;
 
Quoted 8 lines
Quoted 5 lines

kernel/sched/fair.c static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se) · line 672

Quoted 3 lines
kernel/sched/fair.c +2 -1
-	p->se.avg.decay_count = 0;
+	sa->last_update_time = 0;
+	sa->period_contrib = 0;

sa->period_contrib = slice;

period_contrib should be strictly < 1024. I suppose sched_slice does not guarantee that. So here I will give it 1023 to heavy the load.

Oh right, ignore that then.

Quoted 17 lines
Quoted 17 lines

kernel/sched/fair.c static __always_inline u64 decay_load(u64 val, u64 n) · line 2222

Quoted 12 lines
kernel/sched/fair.c +11 -0
+static __always_inline u64 decay_load64(u64 val, u64 n)
+{
+	if (likely(val <= UINT_MAX))
+		val = decay_load(val, n);
+	else {
+		/*
+		 * LOAD_AVG_MAX can last ~500ms (=log_2(LOAD_AVG_MAX)*32ms).
+		 * Since we have so big runnable load_avg, it is impossible
+		 * load_avg has not been updated for such a long time. So
+		 * LOAD_AVG_MAX is enough here.
+		 */

I mean, LOAD_AVG_MAX is irrelevant - the constant could just as well be 1<<20, or whatever, yes? In fact, if you're going to then turn it into a fraction of 1<<10, just do (with whatever temporaries you find most tasteful):

Quoted 8 lines
Quoted 3 lines

val *= (u32) decay_load(1 << 10, n);
val >>= 10;

LOAD_AVG_MAX is selected on purpose. The val arriving here specifies that it is really big. So the decay_load may not decay it to 0 even period n is not small. If we use 1<<10 here, n=10*32 will decay it to 0, but val (larger than 1<<32) can
survive.

But when you do *1024 / LOAD_AVG_MAX it will go back to zero. In general the code you have now is exactly equivalent to factor = decay_load(1<<10,n) ignoring possible differences in rounding.

Quoted 22 lines
Quoted 14 lines
Quoted 14 lines
kernel/sched/fair.c +9 -0
+/* Update task and its cfs_rq load average */
+static inline void update_load_avg(struct sched_entity *se, int update_tg)
 {
+	struct cfs_rq *cfs_rq = cfs_rq_of(se);
+	u64 now = cfs_rq_clock_task(cfs_rq);
+
 	/*
+	 * Track task load average for carrying it to new CPU after migrated
 	 */
+	if (entity_is_task(se))
+		__update_load_avg(now, &se->avg, se->on_rq * se->load.weight);
 
+	update_cfs_rq_load_avg(now, cfs_rq);
Quoted 7 lines

kernel/sched/fair.c static __always_inline int __update_entity_runnable_avg(u64 now, · line 2506

Quoted 3 lines
kernel/sched/fair.c +2 -0
+	if (update_tg)
+		update_tg_load_avg(cfs_rq);
 }

I personally find this very confusing, in that update_load_avg is doing more to se->cfs_rq, and in fact on anything other than a task, it isn't touching the se at all (instead, it touches _se->parent_ even).

Quoted 1 line

What is confusing? The naming?

The fact that it sounds like it is operating on three things (se, cfs_rq_of(se) and se->parent) but looks like it is only operating on se. In particular, half/most of the time it isn't even operating on se at all.

Quoted 4 lines

About the overflow problem, maybe I can just fall back to do load_avg / 47742 for every update, then everything would be in nature the same range with the current code.

Hmm, that might work.

It would still be good to see pipe_test numbers at various cgroup depths.

author
#6 lore raw
Quoted 21 lines · On Tue, Jul 15, 2014 at 10:27:45AM -0700, [email protected] wrote:
Quoted 21 lines
Quoted 20 lines

kernel/sched/fair.c static __always_inline u64 decay_load(u64 val, u64 n) · line 2222

Quoted 12 lines
kernel/sched/fair.c +11 -0
+static __always_inline u64 decay_load64(u64 val, u64 n)
+{
+	if (likely(val <= UINT_MAX))
+		val = decay_load(val, n);
+	else {
+		/*
+		 * LOAD_AVG_MAX can last ~500ms (=log_2(LOAD_AVG_MAX)*32ms).
+		 * Since we have so big runnable load_avg, it is impossible
+		 * load_avg has not been updated for such a long time. So
+		 * LOAD_AVG_MAX is enough here.
+		 */

I mean, LOAD_AVG_MAX is irrelevant - the constant could just as well be 1<<20, or whatever, yes? In fact, if you're going to then turn it into a fraction of 1<<10, just do (with whatever temporaries you find most tasteful):

val *= (u32) decay_load(1 << 10, n);
val >>= 10;

Quoted 9 lines
Quoted 4 lines

LOAD_AVG_MAX is selected on purpose. The val arriving here specifies that it is really big. So the decay_load may not decay it to 0 even period n is not small. If we use 1<<10 here, n=10*32 will decay it to 0, but val (larger than 1<<32) can
survive.

But when you do *1024 / LOAD_AVG_MAX it will go back to zero. In general the code you have now is exactly equivalent to factor = decay_load(1<<10,n) ignoring possible differences in rounding.

Oh, yes...., I did not go to that deep.

Then to avoid this, maybe should first val*factor, then val/LOAD_AVG_MAX, but then risk overflow again... Ok, I will do:

val *= (u32) decay_load(1 << 10, n);
val >>= 10;

if not enough, I believe decay_load(1 << 15, n) should be safe too.

Thanks a lot,
Yuyang

#7 lore raw
In reply to [email protected]
Quoted 1 line · On Tue, 2014-07-15 at 10:27 -0700, [email protected] wrote:

It would still be good to see pipe_test numbers at various cgroup depths.

My t^Hcrusty ole box seems to be saying..

cgexec -g cpu:a pipe-test 1
3.16.0-default 5.016373 usecs/loop -- avg 5.021115 398.3 KHz
3.16.0-default+tim 5.003933 usecs/loop -- avg 4.986591 401.1 KHz

cgexec -g cpu:a/b pipe-test 1
3.16.0-default 5.543566 usecs/loop -- avg 5.565475 359.4 KHz
3.16.0-default+tim 5.663404 usecs/loop -- avg 5.647020 354.2 KHz

cgexec -g cpu:a/b/c pipe-test 1
3.16.0-default 6.092256 usecs/loop -- avg 6.094186 328.2 KHz
3.16.0-default+tim 6.311192 usecs/loop -- avg 6.299077 317.5 KHz

..that 0 KHz will become easier to achieve.