[PATCH v2 0/2] sched: account fair load avg consistently

[PATCH v2 0/2] sched: account fair load avg consistently

[byungchul.park]

From: Byungchul Park <byungchul.park@lge.com>

* change from v1 to v2
- make set_task_rq() do that role instead of migration callback
- make set_task_rq() do that role instead of move group callback
- remove the dependancy between last_update_time and check for migration

Byungchul Park (2):
  sched: make each sched class handle its rq assignment in their own
    class
  sched: make it possible to account fair class load avg consistently

 include/linux/sched.h |    3 ++
 kernel/sched/core.c   |    1 +
 kernel/sched/fair.c   |   77 ++++++++++++++++++++++---------
 kernel/sched/rt.c     |   14 ++++++
 kernel/sched/sched.h  |  121 ++++++++++++++++++++++++-------------------------
 5 files changed, 132 insertions(+), 84 deletions(-)

-- 
1.7.9.5

[PATCH v2 1/2] sched: make each sched class handle its rq assignment in their own class

[byungchul.park]

From: Byungchul Park <byungchul.park@lge.com>

set_task_rq() which is a commonly used function regardless of sched class
is currently assigning both cfs_rq for fair class and rt_rq for rt class
to a task. but it would be better that a class related operation is done
by its own class respectively. additionally, this patch moves some code's
position to refer for_each_class() macro.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 kernel/sched/fair.c  |    9 ++++
 kernel/sched/rt.c    |   14 ++++++
 kernel/sched/sched.h |  120 ++++++++++++++++++++++++--------------------------
 3 files changed, 80 insertions(+), 63 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 077076f..07882c2 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -8088,6 +8088,14 @@ static void task_move_group_fair(struct task_struct *p)
 	attach_task_cfs_rq(p);
 }
 
+static void set_task_rq_fair(struct task_struct *p, unsigned int cpu)
+{
+	struct task_group *tg = task_group(p);
+
+	p->se.cfs_rq = tg->cfs_rq[cpu];
+	p->se.parent = tg->se[cpu];
+}
+
 void free_fair_sched_group(struct task_group *tg)
 {
 	int i;
@@ -8306,6 +8314,7 @@ const struct sched_class fair_sched_class = {
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
 	.task_move_group	= task_move_group_fair,
+	.set_task_rq		= set_task_rq_fair,
 #endif
 };
 
diff --git a/kernel/sched/rt.c b/kernel/sched/rt.c
index e3cc163..f1a1320 100644
--- a/kernel/sched/rt.c
+++ b/kernel/sched/rt.c
@@ -2143,6 +2143,16 @@ static void switched_to_rt(struct rq *rq, struct task_struct *p)
 	}
 }
 
+#ifdef CONFIG_RT_GROUP_SCHED
+static void set_task_rq_rt(struct task_struct *p, unsigned int cpu)
+{
+	struct task_group *tg = task_group(p);
+
+	p->rt.rt_rq  = tg->rt_rq[cpu];
+	p->rt.parent = tg->rt_se[cpu];
+}
+#endif
+
 /*
  * Priority of the task has changed. This may cause
  * us to initiate a push or pull.
@@ -2290,6 +2300,10 @@ const struct sched_class rt_sched_class = {
 	.switched_to		= switched_to_rt,
 
 	.update_curr		= update_curr_rt,
+
+#ifdef CONFIG_RT_GROUP_SCHED
+	.set_task_rq		= set_task_rq_rt,
+#endif
 };
 
 #ifdef CONFIG_SCHED_DEBUG
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index af6f252..7f73e89 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -905,69 +905,6 @@ static inline void sched_ttwu_pending(void) { }
 #include "stats.h"
 #include "auto_group.h"
 
-#ifdef CONFIG_CGROUP_SCHED
-
-/*
- * Return the group to which this tasks belongs.
- *
- * We cannot use task_css() and friends because the cgroup subsystem
- * changes that value before the cgroup_subsys::attach() method is called,
- * therefore we cannot pin it and might observe the wrong value.
- *
- * The same is true for autogroup's p->signal->autogroup->tg, the autogroup
- * core changes this before calling sched_move_task().
- *
- * Instead we use a 'copy' which is updated from sched_move_task() while
- * holding both task_struct::pi_lock and rq::lock.
- */
-static inline struct task_group *task_group(struct task_struct *p)
-{
-	return p->sched_task_group;
-}
-
-/* Change a task's cfs_rq and parent entity if it moves across CPUs/groups */
-static inline void set_task_rq(struct task_struct *p, unsigned int cpu)
-{
-#if defined(CONFIG_FAIR_GROUP_SCHED) || defined(CONFIG_RT_GROUP_SCHED)
-	struct task_group *tg = task_group(p);
-#endif
-
-#ifdef CONFIG_FAIR_GROUP_SCHED
-	p->se.cfs_rq = tg->cfs_rq[cpu];
-	p->se.parent = tg->se[cpu];
-#endif
-
-#ifdef CONFIG_RT_GROUP_SCHED
-	p->rt.rt_rq  = tg->rt_rq[cpu];
-	p->rt.parent = tg->rt_se[cpu];
-#endif
-}
-
-#else /* CONFIG_CGROUP_SCHED */
-
-static inline void set_task_rq(struct task_struct *p, unsigned int cpu) { }
-static inline struct task_group *task_group(struct task_struct *p)
-{
-	return NULL;
-}
-
-#endif /* CONFIG_CGROUP_SCHED */
-
-static inline void __set_task_cpu(struct task_struct *p, unsigned int cpu)
-{
-	set_task_rq(p, cpu);
-#ifdef CONFIG_SMP
-	/*
-	 * After ->cpu is set up to a new value, task_rq_lock(p, ...) can be
-	 * successfuly executed on another CPU. We must ensure that updates of
-	 * per-task data have been completed by this moment.
-	 */
-	smp_wmb();
-	task_thread_info(p)->cpu = cpu;
-	p->wake_cpu = cpu;
-#endif
-}
-
 /*
  * Tunables that become constants when CONFIG_SCHED_DEBUG is off:
  */
@@ -1222,6 +1159,8 @@ struct sched_class {
 #ifdef CONFIG_FAIR_GROUP_SCHED
 	void (*task_move_group) (struct task_struct *p);
 #endif
+
+	void (*set_task_rq) (struct task_struct *p, unsigned int cpu);
 };
 
 static inline void put_prev_task(struct rq *rq, struct task_struct *prev)
@@ -1239,6 +1178,61 @@ extern const struct sched_class rt_sched_class;
 extern const struct sched_class fair_sched_class;
 extern const struct sched_class idle_sched_class;
 
+#ifdef CONFIG_CGROUP_SCHED
+
+/*
+ * Return the group to which this tasks belongs.
+ *
+ * We cannot use task_css() and friends because the cgroup subsystem
+ * changes that value before the cgroup_subsys::attach() method is called,
+ * therefore we cannot pin it and might observe the wrong value.
+ *
+ * The same is true for autogroup's p->signal->autogroup->tg, the autogroup
+ * core changes this before calling sched_move_task().
+ *
+ * Instead we use a 'copy' which is updated from sched_move_task() while
+ * holding both task_struct::pi_lock and rq::lock.
+ */
+static inline struct task_group *task_group(struct task_struct *p)
+{
+	return p->sched_task_group;
+}
+
+/* Change a task's cfs_rq and parent entity if it moves across CPUs/groups */
+static inline void set_task_rq(struct task_struct *p, unsigned int cpu)
+{
+	const struct sched_class *class;
+
+	for_each_class(class) {
+		if (class->set_task_rq)
+			class->set_task_rq(p, cpu);
+	}
+}
+
+#else /* CONFIG_CGROUP_SCHED */
+
+static inline void set_task_rq(struct task_struct *p, unsigned int cpu) { }
+static inline struct task_group *task_group(struct task_struct *p)
+{
+	return NULL;
+}
+
+#endif /* CONFIG_CGROUP_SCHED */
+
+static inline void __set_task_cpu(struct task_struct *p, unsigned int cpu)
+{
+	set_task_rq(p, cpu);
+#ifdef CONFIG_SMP
+	/*
+	 * After ->cpu is set up to a new value, task_rq_lock(p, ...) can be
+	 * successfuly executed on another CPU. We must ensure that updates of
+	 * per-task data have been completed by this moment.
+	 */
+	smp_wmb();
+	task_thread_info(p)->cpu = cpu;
+	p->wake_cpu = cpu;
+#endif
+}
 
 #ifdef CONFIG_SMP
 
-- 
1.7.9.5

Re: [PATCH v2 1/2] sched: make each sched class handle its rq assignment in their own class

[Peter Zijlstra]

On Wed, Oct 14, 2015 at 05:42:09PM +0900, byungchul.park@lge.com wrote:
> +static inline void set_task_rq(struct task_struct *p, unsigned int cpu)
> +{
> +	const struct sched_class *class;
> +
> +	for_each_class(class) {
> +		if (class->set_task_rq)
> +			class->set_task_rq(p, cpu);
> +	}
> +}

So I worry about this, because the class structures are not all in the
same translation unit, GCC cannot (without -fwhole-program) optimize
that all away.

This means we'll do 5 cacheline loads and 2 indirect calls, on _every_
cpu migration.

Re: [PATCH v2 1/2] sched: make each sched class handle its rq assignment in their own class

[Byungchul Park]

On Wed, Oct 14, 2015 at 11:00:16AM +0200, Peter Zijlstra wrote:
> On Wed, Oct 14, 2015 at 05:42:09PM +0900, byungchul.park@lge.com wrote:
> > +static inline void set_task_rq(struct task_struct *p, unsigned int cpu)
> > +{
> > +	const struct sched_class *class;
> > +
> > +	for_each_class(class) {
> > +		if (class->set_task_rq)
> > +			class->set_task_rq(p, cpu);
> > +	}
> > +}
> 
> So I worry about this, because the class structures are not all in the
> same translation unit, GCC cannot (without -fwhole-program) optimize
> that all away.

i wondered if it was so, and it was.

> 
> This means we'll do 5 cacheline loads and 2 indirect calls, on _every_
> cpu migration.

i agree with your this concern. to avoid this concern, it can be done by
hard coding as current code.. but we will lose code flexability. i thought
migration overhead was not so important since it hardly happens.

> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH v2 1/2] sched: make each sched class handle its rq assignment in their own class

[Peter Zijlstra]

On Wed, Oct 14, 2015 at 06:26:30PM +0900, Byungchul Park wrote:
> On Wed, Oct 14, 2015 at 11:00:16AM +0200, Peter Zijlstra wrote:
> > On Wed, Oct 14, 2015 at 05:42:09PM +0900, byungchul.park@lge.com wrote:
> > > +static inline void set_task_rq(struct task_struct *p, unsigned int cpu)
> > > +{
> > > +	const struct sched_class *class;
> > > +
> > > +	for_each_class(class) {
> > > +		if (class->set_task_rq)
> > > +			class->set_task_rq(p, cpu);
> > > +	}
> > > +}
> > 
> > So I worry about this, because the class structures are not all in the
> > same translation unit, GCC cannot (without -fwhole-program) optimize
> > that all away.
> 
> i wondered if it was so, and it was.

--combine might be enough, and might make sense for all the
kernel/sched/ file, but that too is not something we currently do.

> > This means we'll do 5 cacheline loads and 2 indirect calls, on _every_
> > cpu migration.
> 
> i agree with your this concern. to avoid this concern, it can be done by
> hard coding as current code.. but we will lose code flexability. i thought
> migration overhead was not so important since it hardly happens.

It happens quite a lot, just not _as_ often as regular context
switching.

Re: [PATCH v2 1/2] sched: make each sched class handle its rq assignment in their own class

[Byungchul Park]

On Wed, Oct 14, 2015 at 11:30:24AM +0200, Peter Zijlstra wrote:
> On Wed, Oct 14, 2015 at 06:26:30PM +0900, Byungchul Park wrote:
> > On Wed, Oct 14, 2015 at 11:00:16AM +0200, Peter Zijlstra wrote:
> > > On Wed, Oct 14, 2015 at 05:42:09PM +0900, byungchul.park@lge.com wrote:
> > > > +static inline void set_task_rq(struct task_struct *p, unsigned int cpu)
> > > > +{
> > > > +	const struct sched_class *class;
> > > > +
> > > > +	for_each_class(class) {
> > > > +		if (class->set_task_rq)
> > > > +			class->set_task_rq(p, cpu);
> > > > +	}
> > > > +}
> > > 
> > > So I worry about this, because the class structures are not all in the
> > > same translation unit, GCC cannot (without -fwhole-program) optimize
> > > that all away.
> > 
> > i wondered if it was so, and it was.
> 
> --combine might be enough, and might make sense for all the
> kernel/sched/ file, but that too is not something we currently do.
> 
> > > This means we'll do 5 cacheline loads and 2 indirect calls, on _every_
> > > cpu migration.
> > 
> > i agree with your this concern. to avoid this concern, it can be done by
> > hard coding as current code.. but we will lose code flexability. i thought
> > migration overhead was not so important since it hardly happens.
> 
> It happens quite a lot, just not _as_ often as regular context
> switching.

ok, i will take the optimization into account in the migration case.

thanks,
byungchul

> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/

[PATCH v2 2/2] sched: make it possible to account fair class load avg consistently

[byungchul.park]

From: Byungchul Park <byungchul.park@lge.com>

Current code can account fair class load avg for time the task was on
other class e.g. rt or dl thanks to ATTACH_AGE_LOAD. However, it does
not work in the case that either migration or group change happened in
the other classes.

This patch introduces more general solution so that load avg of fair
class will be considered consistently, and removed a weird coupling
between se->avg.last_update_time and the condition checking for
migration.

Additionally, cleaned up code a little bit.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 include/linux/sched.h |    3 +++
 kernel/sched/core.c   |    1 +
 kernel/sched/fair.c   |   72 +++++++++++++++++++++++++++++++++----------------
 kernel/sched/sched.h  |    1 +
 4 files changed, 54 insertions(+), 23 deletions(-)

diff --git a/include/linux/sched.h b/include/linux/sched.h
index 699228b..a104c72 100644
--- a/include/linux/sched.h
+++ b/include/linux/sched.h
@@ -1379,6 +1379,9 @@ struct task_struct {
 #endif
 	int on_rq;
 
+	/* For indicating if a migration has happened. */
+	int migrated;
+
 	int prio, static_prio, normal_prio;
 	unsigned int rt_priority;
 	const struct sched_class *sched_class;
diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index a91df61..57f4300 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -2068,6 +2068,7 @@ void __dl_clear_params(struct task_struct *p)
 static void __sched_fork(unsigned long clone_flags, struct task_struct *p)
 {
 	p->on_rq			= 0;
+	p->migrated			= 0;
 
 	p->se.on_rq			= 0;
 	p->se.exec_start		= 0;
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 07882c2..52e7d85 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -2771,14 +2771,15 @@ static void detach_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *s
 
 /* 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)
+enqueue_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
 {
 	struct sched_avg *sa = &se->avg;
 	u64 now = cfs_rq_clock_task(cfs_rq);
-	int migrated, decayed;
+	int decayed;
+	int migrated = flags & ENQUEUE_MIGRATED;
+	int created = !(sa->last_update_time);
 
-	migrated = !sa->last_update_time;
-	if (!migrated) {
+	if (!migrated && !created) {
 		__update_load_avg(now, cpu_of(rq_of(cfs_rq)), sa,
 			se->on_rq * scale_load_down(se->load.weight),
 			cfs_rq->curr == se, NULL);
@@ -2789,10 +2790,10 @@ enqueue_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
 	cfs_rq->runnable_load_avg += sa->load_avg;
 	cfs_rq->runnable_load_sum += sa->load_sum;
 
-	if (migrated)
+	if (migrated || created)
 		attach_entity_load_avg(cfs_rq, se);
 
-	if (decayed || migrated)
+	if (decayed || migrated || created)
 		update_tg_load_avg(cfs_rq, 0);
 }
 
@@ -2808,15 +2809,10 @@ dequeue_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
 		max_t(s64,  cfs_rq->runnable_load_sum - se->avg.load_sum, 0);
 }
 
-/*
- * Task first catches up with cfs_rq, and then subtract
- * itself from the cfs_rq (task must be off the queue now).
- */
-void remove_entity_load_avg(struct sched_entity *se)
+/* This function is useful for the case that rq->lock may not be held */
+static inline u64 get_last_update_time(struct cfs_rq *cfs_rq)
 {
-	struct cfs_rq *cfs_rq = cfs_rq_of(se);
 	u64 last_update_time;
-
 #ifndef CONFIG_64BIT
 	u64 last_update_time_copy;
 
@@ -2828,6 +2824,17 @@ void remove_entity_load_avg(struct sched_entity *se)
 #else
 	last_update_time = cfs_rq->avg.last_update_time;
 #endif
+	return last_update_time;
+}
+
+/*
+ * Task first catches up with cfs_rq, and then subtract
+ * itself from the cfs_rq (task must be off the queue now).
+ */
+void remove_entity_load_avg(struct sched_entity *se)
+{
+	struct cfs_rq *cfs_rq = cfs_rq_of(se);
+	u64 last_update_time = get_last_update_time(cfs_rq);
 
 	__update_load_avg(last_update_time, cpu_of(rq_of(cfs_rq)), &se->avg, 0, 0, NULL);
 	atomic_long_add(se->avg.load_avg, &cfs_rq->removed_load_avg);
@@ -2868,7 +2875,7 @@ static int idle_balance(struct rq *this_rq);
 
 static inline void update_load_avg(struct sched_entity *se, int update_tg) {}
 static inline void
-enqueue_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se) {}
+enqueue_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags) {}
 static inline void
 dequeue_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se) {}
 static inline void remove_entity_load_avg(struct sched_entity *se) {}
@@ -3008,7 +3015,7 @@ enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
 	 * Update run-time statistics of the 'current'.
 	 */
 	update_curr(cfs_rq);
-	enqueue_entity_load_avg(cfs_rq, se);
+	enqueue_entity_load_avg(cfs_rq, se, flags);
 	account_entity_enqueue(cfs_rq, se);
 	update_cfs_shares(cfs_rq);
 
@@ -4136,6 +4143,7 @@ enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
 	struct cfs_rq *cfs_rq;
 	struct sched_entity *se = &p->se;
 
+	flags = flags | (xchg(&p->migrated, 0) ? ENQUEUE_MIGRATED : 0);
 	for_each_sched_entity(se) {
 		if (se->on_rq)
 			break;
@@ -5021,7 +5029,7 @@ static void migrate_task_rq_fair(struct task_struct *p, int next_cpu)
 	remove_entity_load_avg(&p->se);
 
 	/* Tell new CPU we are migrated */
-	p->se.avg.last_update_time = 0;
+	p->migrated = 1;
 
 	/* We have migrated, no longer consider this task hot */
 	p->se.exec_start = 0;
@@ -8080,20 +8088,38 @@ static void task_move_group_fair(struct task_struct *p)
 {
 	detach_task_cfs_rq(p);
 	set_task_rq(p, task_cpu(p));
-
-#ifdef CONFIG_SMP
-	/* Tell se's cfs_rq has been changed -- migrated */
-	p->se.avg.last_update_time = 0;
-#endif
 	attach_task_cfs_rq(p);
 }
 
+/*
+ * Called immediately before a task is set to a new cpu; task_cpu(p) and
+ * cfs_rq_of(p) references at time of call are still valid and identify the
+ * previous cpu.  However, the caller only guarantees p->pi_lock is held; no
+ * other assumptions, including the state of rq->lock, should be made.
+ */
 static void set_task_rq_fair(struct task_struct *p, unsigned int cpu)
 {
 	struct task_group *tg = task_group(p);
+	struct sched_entity *se = &p->se;
+
+	/*
+	 * Now that the base cfs_rq for aging or decaying is about to be
+	 * changed, we perform the aging or decaying here with the old
+	 * cfs_rq, as the cfs_rq is not changed yet.
+	 */
+	if (se->avg.last_update_time)
+		__update_load_avg(get_last_update_time(cfs_rq_of(se)), task_cpu(p), &se->avg,
+				  se->on_rq * scale_load_down(se->load.weight),
+				  cfs_rq_of(se)->curr == se, NULL);
+
+	se->cfs_rq = tg->cfs_rq[cpu];
+	se->parent = tg->se[cpu];
 
-	p->se.cfs_rq = tg->cfs_rq[cpu];
-	p->se.parent = tg->se[cpu];
+	/*
+	 * Now that se's cfs_rq was changed, we need to also change its
+	 * base time for aging or decaying.
+	 */
+	se->avg.last_update_time = get_last_update_time(cfs_rq_of(se));
 }
 
 void free_fair_sched_group(struct task_group *tg)
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 7f73e89..1897c85 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -1095,6 +1095,7 @@ static const u32 prio_to_wmult[40] = {
 #define ENQUEUE_WAKING		0
 #endif
 #define ENQUEUE_REPLENISH	8
+#define ENQUEUE_MIGRATED	16
 
 #define DEQUEUE_SLEEP		1
 
-- 
1.7.9.5