[PATCH v2 0/3] sched: sync a se with its cfs_rq when attaching and dettaching

[PATCH v2 0/3] sched: sync a se with its cfs_rq when attaching and dettaching

[byungchul.park]

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

change from v1 to v2
* introduce two functions for adjusting vruntime and load when attaching
  and detaching.
* call the introduced functions instead of switched_from(to)_fair() directly
  in task_move_group_fair().
* add decaying logic for a se which has detached from a cfs_rq.

Byungchul Park (3):
  sched: sync a se with its cfs_rq when attaching and dettaching
  sched: introduce functions for attaching(detaching) a task to cfs_rq
  sched: decay a detached se when it's attached to its cfs_rq

 kernel/sched/fair.c |  210 ++++++++++++++++++++++++++-------------------------
 1 file changed, 109 insertions(+), 101 deletions(-)

-- 
1.7.9.5

[PATCH v2 1/3] sched: sync a se with its cfs_rq when attaching and dettaching

[byungchul.park]

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

current code is wrong with cfs_rq's avg loads when changing a task's
cfs_rq to another. i tested with "echo pid > cgroup" and found that
e.g. cfs_rq->avg.load_avg became larger and larger whenever i changed
a cgroup to another again and again. we have to sync se's avg loads
with both *prev* cfs_rq and next cfs_rq when changing its group.

not only for changing cgroup, but also for changing sched class, we
also need to sync a se with its cfs_rq, that is, when leaving from
fair class and returning back to fair class.

in addition, i introduced two functions for attaching/detaching a se
from/to its cfs_rq, and let them use those functions. and i place
that function call to where a se is attached/detached to/from cfs_rq.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 kernel/sched/fair.c |   82 ++++++++++++++++++++++++++++++---------------------
 1 file changed, 48 insertions(+), 34 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 4d5f97b..fc6b39c 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -2709,6 +2709,31 @@ static inline void update_load_avg(struct sched_entity *se, int update_tg)
 		update_tg_load_avg(cfs_rq, 0);
 }
 
+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->avg.load_sum;
+	cfs_rq->avg.util_avg += se->avg.util_avg;
+	cfs_rq->avg.util_sum += se->avg.util_sum;
+}
+
+static void detach_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
+{
+	__update_load_avg(cfs_rq->avg.last_update_time, cpu_of(rq_of(cfs_rq)),
+			&se->avg, se->on_rq * scale_load_down(se->load.weight),
+			cfs_rq->curr == se, NULL);
+
+	cfs_rq->avg.load_avg =
+		max_t(long, cfs_rq->avg.load_avg - se->avg.load_avg, 0);
+	cfs_rq->avg.load_sum =
+		max_t(s64, cfs_rq->avg.load_sum - se->avg.load_sum, 0);
+	cfs_rq->avg.util_avg =
+		max_t(long, cfs_rq->avg.util_avg - se->avg.util_avg, 0);
+	cfs_rq->avg.util_sum =
+		max_t(s32, cfs_rq->avg.util_sum - se->avg.util_sum, 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)
@@ -2717,27 +2742,20 @@ enqueue_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
 	u64 now = cfs_rq_clock_task(cfs_rq);
 	int migrated = 0, decayed;
 
-	if (sa->last_update_time == 0) {
-		sa->last_update_time = now;
+	if (sa->last_update_time == 0)
 		migrated = 1;
-	}
-	else {
+	else
 		__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);
-	}
+				se->on_rq * scale_load_down(se->load.weight),
+				cfs_rq->curr == se, NULL);
 
 	decayed = update_cfs_rq_load_avg(now, cfs_rq);
 
 	cfs_rq->runnable_load_avg += sa->load_avg;
 	cfs_rq->runnable_load_sum += sa->load_sum;
 
-	if (migrated) {
-		cfs_rq->avg.load_avg += sa->load_avg;
-		cfs_rq->avg.load_sum += sa->load_sum;
-		cfs_rq->avg.util_avg += sa->util_avg;
-		cfs_rq->avg.util_sum += sa->util_sum;
-	}
+	if (migrated)
+		attach_entity_load_avg(cfs_rq, se);
 
 	if (decayed || migrated)
 		update_tg_load_avg(cfs_rq, 0);
@@ -7911,17 +7929,7 @@ static void switched_from_fair(struct rq *rq, struct task_struct *p)
 
 #ifdef CONFIG_SMP
 	/* Catch up with the cfs_rq and remove our load when we leave */
-	__update_load_avg(cfs_rq->avg.last_update_time, cpu_of(rq), &se->avg,
-		se->on_rq * scale_load_down(se->load.weight), cfs_rq->curr == se, NULL);
-
-	cfs_rq->avg.load_avg =
-		max_t(long, cfs_rq->avg.load_avg - se->avg.load_avg, 0);
-	cfs_rq->avg.load_sum =
-		max_t(s64, cfs_rq->avg.load_sum - se->avg.load_sum, 0);
-	cfs_rq->avg.util_avg =
-		max_t(long, cfs_rq->avg.util_avg - se->avg.util_avg, 0);
-	cfs_rq->avg.util_sum =
-		max_t(s32, cfs_rq->avg.util_sum - se->avg.util_sum, 0);
+	detach_entity_load_avg(cfs_rq, se);
 #endif
 }
 
@@ -7940,6 +7948,11 @@ static void switched_to_fair(struct rq *rq, struct task_struct *p)
 	se->depth = se->parent ? se->parent->depth + 1 : 0;
 #endif
 
+#ifdef CONFIG_SMP
+	/* synchronize task with its cfs_rq */
+	attach_entity_load_avg(cfs_rq_of(&p->se), &p->se);
+#endif
+
 	if (!task_on_rq_queued(p)) {
 
 		/*
@@ -8032,23 +8045,24 @@ static void task_move_group_fair(struct task_struct *p, int queued)
 	if (!queued && (!se->sum_exec_runtime || p->state == TASK_WAKING))
 		queued = 1;
 
+	cfs_rq = cfs_rq_of(se);
 	if (!queued)
-		se->vruntime -= cfs_rq_of(se)->min_vruntime;
+		se->vruntime -= cfs_rq->min_vruntime;
+
+#ifdef CONFIG_SMP
+	/* synchronize task with its prev cfs_rq */
+	detach_entity_load_avg(cfs_rq, se);
+#endif
 	set_task_rq(p, task_cpu(p));
 	se->depth = se->parent ? se->parent->depth + 1 : 0;
-	if (!queued) {
-		cfs_rq = cfs_rq_of(se);
+	cfs_rq = cfs_rq_of(se);
+	if (!queued)
 		se->vruntime += cfs_rq->min_vruntime;
 
 #ifdef CONFIG_SMP
-		/* Virtually synchronize task with its new cfs_rq */
-		p->se.avg.last_update_time = cfs_rq->avg.last_update_time;
-		cfs_rq->avg.load_avg += p->se.avg.load_avg;
-		cfs_rq->avg.load_sum += p->se.avg.load_sum;
-		cfs_rq->avg.util_avg += p->se.avg.util_avg;
-		cfs_rq->avg.util_sum += p->se.avg.util_sum;
+	/* Virtually synchronize task with its new cfs_rq */
+	attach_entity_load_avg(cfs_rq, se);
 #endif
-	}
 }
 
 void free_fair_sched_group(struct task_group *tg)
-- 
1.7.9.5

[PATCH v2 2/3] sched: introduce functions for attaching(detaching) a task to cfs_rq

[byungchul.park]

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

two functions are introduced for attaching(detaching) a task to a cfs_rq.
it does mainly adjusting its vruntime and load avg with the cfs_rq.
switched_from_fair(), switched_to_fair() and task_move_group_fair() can
use these functions, now.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 kernel/sched/fair.c |  143 +++++++++++++++++++++++----------------------------
 1 file changed, 63 insertions(+), 80 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index fc6b39c..346f2a6 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -7904,21 +7904,29 @@ prio_changed_fair(struct rq *rq, struct task_struct *p, int oldprio)
 		check_preempt_curr(rq, p, 0);
 }
 
-static void switched_from_fair(struct rq *rq, struct task_struct *p)
+static void detach_task_cfs_rq(struct task_struct *p, int queued)
 {
 	struct sched_entity *se = &p->se;
 	struct cfs_rq *cfs_rq = cfs_rq_of(se);
 
 	/*
-	 * Ensure the task's vruntime is normalized, so that when it's
-	 * switched back to the fair class the enqueue_entity(.flags=0) will
-	 * do the right thing.
+	 * Ensure the task's vruntime is normalized, so that when attaching
+	 * it to a cfs_rq the enqueue_entity(.flags=0) will do the right thing.
 	 *
 	 * If it's queued, then the dequeue_entity(.flags=0) will already
 	 * have normalized the vruntime, if it's !queued, then only when
-	 * the task is sleeping will it still have non-normalized vruntime.
+	 * the task is sleeping it still has a non-normalized vruntime.
+	 *
+	 * When !queued, vruntime of the task has usually NOT been normalized.
+	 * But there are some cases where it has already been normalized:
+	 *
+	 * - Moving a forked child which is waiting for being woken up by
+	 *   wake_up_new_task().
+	 * - Moving a task which has been woken up by try_to_wake_up() and
+	 *   waiting for actually being woken up by sched_ttwu_pending().
 	 */
-	if (!task_on_rq_queued(p) && p->state != TASK_RUNNING) {
+	if (!queued && p->state != TASK_RUNNING &&
+	    se->sum_exec_runtime && p->state != TASK_WAKING) {
 		/*
 		 * Fix up our vruntime so that the current sleep doesn't
 		 * cause 'unlimited' sleep bonus.
@@ -7933,12 +7941,10 @@ static void switched_from_fair(struct rq *rq, struct task_struct *p)
 #endif
 }
 
-/*
- * We switched to the sched_fair class.
- */
-static void switched_to_fair(struct rq *rq, struct task_struct *p)
+static void attach_task_cfs_rq(struct task_struct *p, int queued)
 {
 	struct sched_entity *se = &p->se;
+	struct cfs_rq *cfs_rq = cfs_rq_of(se);
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
 	/*
@@ -7950,34 +7956,57 @@ static void switched_to_fair(struct rq *rq, struct task_struct *p)
 
 #ifdef CONFIG_SMP
 	/* synchronize task with its cfs_rq */
-	attach_entity_load_avg(cfs_rq_of(&p->se), &p->se);
+	attach_entity_load_avg(cfs_rq, se);
 #endif
 
-	if (!task_on_rq_queued(p)) {
+	/*
+	 * Ensure the task has a non-normalized vruntime when attaching it
+	 * to a cfs_rq with !queued, so that enqueue_entity() at wake-up time
+	 * will do the right thing.
+	 *
+	 * If it's queued, then the enqueue_entity(.flags=0) makes the task
+	 * has non-normalized vruntime, if it's !queued, then it still has
+	 * a normalized vruntime.
+	 *
+	 * When !queued, a task usually should have a non-normalized vruntime
+	 * after being attached to a cfs_rq. But there are some cases where
+	 * we should keep it normalized:
+	 *
+	 * - Moving a forked child which is waiting for being woken up by
+	 *   wake_up_new_task().
+	 * - Moving a task which has been woken up by try_to_wake_up() and
+	 *   waiting for actually being woken up by sched_ttwu_pending().
+	 */
+	if (!queued && p->state != TASK_RUNNING &&
+	    se->sum_exec_runtime && p->state != TASK_WAKING)
+		se->vruntime += cfs_rq->min_vruntime;
+}
+
+static void switched_from_fair(struct rq *rq, struct task_struct *p)
+{
+	detach_task_cfs_rq(p, task_on_rq_queued(p));
+}
 
+/*
+ * We switched to the sched_fair class.
+ */
+static void switched_to_fair(struct rq *rq, struct task_struct *p)
+{
+	int queued = task_on_rq_queued(p);
+
+	attach_task_cfs_rq(p, queued);
+
+	if (queued) {
 		/*
-		 * Ensure the task has a non-normalized vruntime when it is switched
-		 * back to the fair class with !queued, so that enqueue_entity() at
-		 * wake-up time will do the right thing.
-		 *
-		 * If it's queued, then the enqueue_entity(.flags=0) makes the task
-		 * has non-normalized vruntime, if it's !queued, then it still has
-		 * normalized vruntime.
+		 * We were most likely switched from sched_rt, so
+		 * kick off the schedule if running, otherwise just see
+		 * if we can still preempt the current task.
 		 */
-		if (p->state != TASK_RUNNING)
-			se->vruntime += cfs_rq_of(se)->min_vruntime;
-		return;
+		if (rq->curr == p)
+			resched_curr(rq);
+		else
+			check_preempt_curr(rq, p, 0);
 	}
-
-	/*
-	 * We were most likely switched from sched_rt, so
-	 * kick off the schedule if running, otherwise just see
-	 * if we can still preempt the current task.
-	 */
-	if (rq->curr == p)
-		resched_curr(rq);
-	else
-		check_preempt_curr(rq, p, 0);
 }
 
 /* Account for a task changing its policy or group.
@@ -8014,55 +8043,9 @@ void init_cfs_rq(struct cfs_rq *cfs_rq)
 #ifdef CONFIG_FAIR_GROUP_SCHED
 static void task_move_group_fair(struct task_struct *p, int queued)
 {
-	struct sched_entity *se = &p->se;
-	struct cfs_rq *cfs_rq;
-
-	/*
-	 * If the task was not on the rq at the time of this cgroup movement
-	 * it must have been asleep, sleeping tasks keep their ->vruntime
-	 * absolute on their old rq until wakeup (needed for the fair sleeper
-	 * bonus in place_entity()).
-	 *
-	 * If it was on the rq, we've just 'preempted' it, which does convert
-	 * ->vruntime to a relative base.
-	 *
-	 * Make sure both cases convert their relative position when migrating
-	 * to another cgroup's rq. This does somewhat interfere with the
-	 * fair sleeper stuff for the first placement, but who cares.
-	 */
-	/*
-	 * When !queued, vruntime of the task has usually NOT been normalized.
-	 * But there are some cases where it has already been normalized:
-	 *
-	 * - Moving a forked child which is waiting for being woken up by
-	 *   wake_up_new_task().
-	 * - Moving a task which has been woken up by try_to_wake_up() and
-	 *   waiting for actually being woken up by sched_ttwu_pending().
-	 *
-	 * To prevent boost or penalty in the new cfs_rq caused by delta
-	 * min_vruntime between the two cfs_rqs, we skip vruntime adjustment.
-	 */
-	if (!queued && (!se->sum_exec_runtime || p->state == TASK_WAKING))
-		queued = 1;
-
-	cfs_rq = cfs_rq_of(se);
-	if (!queued)
-		se->vruntime -= cfs_rq->min_vruntime;
-
-#ifdef CONFIG_SMP
-	/* synchronize task with its prev cfs_rq */
-	detach_entity_load_avg(cfs_rq, se);
-#endif
+	detach_task_cfs_rq(p, queued);
 	set_task_rq(p, task_cpu(p));
-	se->depth = se->parent ? se->parent->depth + 1 : 0;
-	cfs_rq = cfs_rq_of(se);
-	if (!queued)
-		se->vruntime += cfs_rq->min_vruntime;
-
-#ifdef CONFIG_SMP
-	/* Virtually synchronize task with its new cfs_rq */
-	attach_entity_load_avg(cfs_rq, se);
-#endif
+	attach_task_cfs_rq(p, queued);
 }
 
 void free_fair_sched_group(struct task_group *tg)
-- 
1.7.9.5

[PATCH v2 3/3] sched: decay a detached se when it's attached to its cfs_rq

[byungchul.park]

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

se's load can be valuable just after being detached from cfs_rq, however
it will become useless over time, e.g. in case of switching to another
sched class and switching back to fair class.

therefore even in case where se is already detached from cfs, decaying
its load is necessary when it gets attached back to cfs_rq.

Signed-off-by: Byungchul Park <byungchul.park@lge.com>
---
 kernel/sched/fair.c |   11 +++++++++++
 1 file changed, 11 insertions(+)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 346f2a6..554c9b7 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -2711,6 +2711,14 @@ static inline void update_load_avg(struct sched_entity *se, int update_tg)
 
 static void attach_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
+	/*
+	 * in case of migration and cgroup-change, cfs_rq has been changed.
+	 * therfore, updating load should be already performed before.
+	 */
+	if (se->avg.last_update_time)
+		__update_load_avg(cfs_rq->avg.last_update_time, cpu_of(rq_of(cfs_rq)),
+				&se->avg, 0, 0, NULL);
+
 	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;
@@ -8045,6 +8053,9 @@ static void task_move_group_fair(struct task_struct *p, int queued)
 {
 	detach_task_cfs_rq(p, queued);
 	set_task_rq(p, task_cpu(p));
+
+	/* Tell cfs_rq has been changed */
+	p->se.avg.last_update_time = 0;
 	attach_task_cfs_rq(p, queued);
 }
 
-- 
1.7.9.5

Re: [PATCH v2 0/3] sched: sync a se with its cfs_rq when attaching and dettaching

[Byungchul Park]

On Mon, Aug 17, 2015 at 04:45:49PM +0900, byungchul.park@lge.com wrote:
> From: Byungchul Park <byungchul.park@lge.com>

i am very sorry for ugly versioning..

while i proposed several indivisual patches and was feedbacked, i felt
that i needed to pack some patches into one series.

thanks,
byungchul

> 
> change from v1 to v2
> * introduce two functions for adjusting vruntime and load when attaching
>   and detaching.
> * call the introduced functions instead of switched_from(to)_fair() directly
>   in task_move_group_fair().
> * add decaying logic for a se which has detached from a cfs_rq.
> 
> Byungchul Park (3):
>   sched: sync a se with its cfs_rq when attaching and dettaching
>   sched: introduce functions for attaching(detaching) a task to cfs_rq
>   sched: decay a detached se when it's attached to its cfs_rq
> 
>  kernel/sched/fair.c |  210 ++++++++++++++++++++++++++-------------------------
>  1 file changed, 109 insertions(+), 101 deletions(-)
> 
> -- 
> 1.7.9.5
> 
> --
> 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/3] sched: sync a se with its cfs_rq when attaching and dettaching

[T. Zhou]

Hi,

On Mon, Aug 17, 2015 at 04:45:50PM +0900, byungchul.park@lge.com wrote:
> From: Byungchul Park <byungchul.park@lge.com>
> 
> current code is wrong with cfs_rq's avg loads when changing a task's
> cfs_rq to another. i tested with "echo pid > cgroup" and found that
> e.g. cfs_rq->avg.load_avg became larger and larger whenever i changed
> a cgroup to another again and again. we have to sync se's avg loads
> with both *prev* cfs_rq and next cfs_rq when changing its group.
> 

my simple think about above, may be nothing or wrong, just ignore it.

if a load balance migration happened just before cgroup change, prev
cfs_rq and next cfs_rq will be on different cpu. migrate_task_rq_fair()
and update_cfs_rq_load_avg() will sync and remove se's load avg from
prev cfs_rq. whether or not queued, well done. dequeue_task() decay se
and pre_cfs before calling task_move_group_fair(). after set cfs_rq in
task_move_group_fair(), if queued, se's load avg do not add to next
cfs_rq(try set last_update_time to 0 like migration to add), if !queued,
also need to add se's load avg to next cfs_rq.

if no load balance migration happened when change cgroup. prev cfs_rq
and next cfs_rq may be on same cpu(not sure), this time, need to remove
se's load avg by ourself, also need to add se's load avg on next cfs_rq.

thinks,
-- 
Tao

Re: [PATCH v2 1/3] sched: sync a se with its cfs_rq when attaching and dettaching

[Byungchul Park]

On Wed, Aug 19, 2015 at 12:32:43AM +0800, T. Zhou wrote:
> Hi,
> 
> On Mon, Aug 17, 2015 at 04:45:50PM +0900, byungchul.park@lge.com wrote:
> > From: Byungchul Park <byungchul.park@lge.com>
> > 
> > current code is wrong with cfs_rq's avg loads when changing a task's
> > cfs_rq to another. i tested with "echo pid > cgroup" and found that
> > e.g. cfs_rq->avg.load_avg became larger and larger whenever i changed
> > a cgroup to another again and again. we have to sync se's avg loads
> > with both *prev* cfs_rq and next cfs_rq when changing its group.
> > 
> 
> my simple think about above, may be nothing or wrong, just ignore it.
> 
> if a load balance migration happened just before cgroup change, prev
> cfs_rq and next cfs_rq will be on different cpu. migrate_task_rq_fair()

hello,

two oerations, migration and cgroup change, are protected by lock.
therefore it would never happen. :)

thanks,
byungchul

> and update_cfs_rq_load_avg() will sync and remove se's load avg from
> prev cfs_rq. whether or not queued, well done. dequeue_task() decay se
> and pre_cfs before calling task_move_group_fair(). after set cfs_rq in
> task_move_group_fair(), if queued, se's load avg do not add to next
> cfs_rq(try set last_update_time to 0 like migration to add), if !queued,
> also need to add se's load avg to next cfs_rq.
> 
> if no load balance migration happened when change cgroup. prev cfs_rq
> and next cfs_rq may be on same cpu(not sure), this time, need to remove
> se's load avg by ourself, also need to add se's load avg on next cfs_rq.
> 
> thinks,
> -- 
> Tao
> --
> 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/