Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1353918 > unrolled thread

Migrated CFS task getting an unfair advantage

Back to article view | Back to linux.kernel

Contents

  Migrated CFS task getting an unfair advantage Pavan Kondeti <pkondeti@codeaurora.org> - 2016-03-09 10:30 +0100
    Re: Migrated CFS task getting an unfair advantage Peter Zijlstra <peterz@infradead.org> - 2016-03-09 13:10 +0100
      Re: Migrated CFS task getting an unfair advantage pavankumar kondeti <pavankumar.kondeti@gmail.com> - 2016-03-09 14:10 +0100
        Re: Migrated CFS task getting an unfair advantage Andrew Hunter <ahh@google.com> - 2016-03-09 20:10 +0100
          Re: Migrated CFS task getting an unfair advantage Peter Zijlstra <peterz@infradead.org> - 2016-03-09 20:30 +0100
          Re: Migrated CFS task getting an unfair advantage Byungchul Park <byungchul.park@lge.com> - 2016-03-10 00:50 +0100

#1353918 — Migrated CFS task getting an unfair advantage

Hi

When a CFS task is enqueued during migration (load balance or change in
affinity), its vruntime is normalized before updating the current and
cfs_rq->min_vruntime. If the current entity is a low priority task or
belongs to a cgroup that has lower cpu.shares and it is the only entity
queued, there is a possibility of big update to the cfs_rq->min_vruntime.
As the migrated task is normalized before this update, it gets an unfair
advantage over tasks queued after this point. If the migrated task is
a CPU hogger, the other CFS tasks queued on this CPU gets starved.

This problem can be simulated by running the below workload:

- create NR_CPU low prio CFS tasks affined to each CPU and put them
under a cgroup with cpu.shares = 52 (1024/20). These tasks run forever.
- create another CFS task which runs forever and periodically hops across
all CPUs by changing the affinity.
- We could see the destination CPU's cfs_rq->min_vruntime falls behind
the migrated task by few hundreds of msec after migration.

If we add the migrated task to destination CPU cfs_rq's rb tree before updating
the current in enqueue_entity(), the cfs_rq->min_vruntime does not go beyond
the newly migrated task. Is this an acceptable solution?

Thanks,
Pavan


-- 
Qualcomm India Private Limited, on behalf of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a
Linux Foundation Collaborative Project

[toc] | [next] | [standalone]

#1354062

On Wed, Mar 09, 2016 at 02:52:57PM +0530, Pavan Kondeti wrote:

> When a CFS task is enqueued during migration (load balance or change in
> affinity), its vruntime is normalized before updating the current and
> cfs_rq->min_vruntime.

static void
enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
	/*
	 * Update the normalized vruntime before updating min_vruntime
	 * through calling update_curr().
	 */
	if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_WAKING))
		se->vruntime += cfs_rq->min_vruntime;

	update_curr(cfs_rq);

This, right? Some idiot wrote a comment but forgot to explain why.

> If the current entity is a low priority task or belongs to a cgroup
> that has lower cpu.shares and it is the only entity queued, there is a
> possibility of big update to the cfs_rq->min_vruntime.

> As the migrated task is normalized before this update, it gets an
> unfair advantage over tasks queued after this point. If the migrated
> task is a CPU hogger, the other CFS tasks queued on this CPU gets
> starved.

Because it takes a whole while for the newly placed task to gain on the
previous task, right?

> If we add the migrated task to destination CPU cfs_rq's rb tree before
> updating the current in enqueue_entity(), the cfs_rq->min_vruntime
> does not go beyond the newly migrated task. Is this an acceptable
> solution?

Hurm.. so I'm not sure how that would solve anything. The existing task
would still be shot far into the future.

What you want is to normalize after update_curr()... but we cannot do
that in the case cfs_rq->curr == se (which I suppose is what that
comment is on about).

Does something like the below work?

---
 kernel/sched/fair.c | 20 ++++++++++++++------
 1 file changed, 14 insertions(+), 6 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 33130529e9b5..3c114d971d84 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -3157,17 +3157,25 @@ static inline void check_schedstat_required(void)
 static void
 enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
 {
+	bool renorm = !(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_WAKING);
+	bool curr = cfs_rq->curr == se;
+
 	/*
-	 * Update the normalized vruntime before updating min_vruntime
-	 * through calling update_curr().
+	 * If we're the current task, we must renormalise before calling
+	 * update_curr().
 	 */
-	if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_WAKING))
+	if (renorm && curr)
 		se->vruntime += cfs_rq->min_vruntime;
 
+	update_curr(cfs_rq);
+
 	/*
-	 * Update run-time statistics of the 'current'.
+	 * Otherwise, renormalise after, such that we're placed at the current
+	 * moment in time, instead of some random moment in the past.
 	 */
-	update_curr(cfs_rq);
+	if (renorm && !curr)
+		se->vruntime += cfs_rq->min_vruntime;
+
 	enqueue_entity_load_avg(cfs_rq, se);
 	account_entity_enqueue(cfs_rq, se);
 	update_cfs_shares(cfs_rq);
@@ -3183,7 +3191,7 @@ enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
 		update_stats_enqueue(cfs_rq, se);
 		check_spread(cfs_rq, se);
 	}
-	if (se != cfs_rq->curr)
+	if (!curr)
 		__enqueue_entity(cfs_rq, se);
 	se->on_rq = 1;
 

[toc] | [prev] | [next] | [standalone]

#1354098

Hi Peter,

On Wed, Mar 9, 2016 at 5:34 PM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Wed, Mar 09, 2016 at 02:52:57PM +0530, Pavan Kondeti wrote:
>
>> When a CFS task is enqueued during migration (load balance or change in
>> affinity), its vruntime is normalized before updating the current and
>> cfs_rq->min_vruntime.
>
> static void
> enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
> {
>         /*
>          * Update the normalized vruntime before updating min_vruntime
>          * through calling update_curr().
>          */
>         if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_WAKING))
>                 se->vruntime += cfs_rq->min_vruntime;
>
>         update_curr(cfs_rq);
>
> This, right? Some idiot wrote a comment but forgot to explain why.
>
>> If the current entity is a low priority task or belongs to a cgroup
>> that has lower cpu.shares and it is the only entity queued, there is a
>> possibility of big update to the cfs_rq->min_vruntime.
>
>> As the migrated task is normalized before this update, it gets an
>> unfair advantage over tasks queued after this point. If the migrated
>> task is a CPU hogger, the other CFS tasks queued on this CPU gets
>> starved.
>
> Because it takes a whole while for the newly placed task to gain on the
> previous task, right?
>

Yes. The newly woken up task vruntime is adjusted wrt the cfs_rq->min_vruntime.
The cfs_rq->min_vruntime can potentially be hundreds of msec beyond the
migrated task.

>> If we add the migrated task to destination CPU cfs_rq's rb tree before
>> updating the current in enqueue_entity(), the cfs_rq->min_vruntime
>> does not go beyond the newly migrated task. Is this an acceptable
>> solution?
>
> Hurm.. so I'm not sure how that would solve anything. The existing task
> would still be shot far into the future.
>
In my testing, the problem is gone with this approach.

The update_min_vruntime() called from  update_curr() has a check to make
sure that cfs_rq->min_vruntime  does not go beyond the leftmost entity
(in this case it would be the migrated task) vruntime. so we don't see
the migrated task getting any advantage.

> What you want is to normalize after update_curr()... but we cannot do
> that in the case cfs_rq->curr == se (which I suppose is what that
> comment is on about).
>
> Does something like the below work?
>

Thanks for providing this patch. It solved the problem.

> ---
>  kernel/sched/fair.c | 20 ++++++++++++++------
>  1 file changed, 14 insertions(+), 6 deletions(-)
>
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 33130529e9b5..3c114d971d84 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -3157,17 +3157,25 @@ static inline void check_schedstat_required(void)
>  static void
>  enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
>  {
> +       bool renorm = !(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_WAKING);
> +       bool curr = cfs_rq->curr == se;
> +
>         /*
> -        * Update the normalized vruntime before updating min_vruntime
> -        * through calling update_curr().
> +        * If we're the current task, we must renormalise before calling
> +        * update_curr().
>          */
> -       if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_WAKING))
> +       if (renorm && curr)
>                 se->vruntime += cfs_rq->min_vruntime;
>
> +       update_curr(cfs_rq);
> +
>         /*
> -        * Update run-time statistics of the 'current'.
> +        * Otherwise, renormalise after, such that we're placed at the current
> +        * moment in time, instead of some random moment in the past.
>          */
> -       update_curr(cfs_rq);
> +       if (renorm && !curr)
> +               se->vruntime += cfs_rq->min_vruntime;
> +
>         enqueue_entity_load_avg(cfs_rq, se);
>         account_entity_enqueue(cfs_rq, se);
>         update_cfs_shares(cfs_rq);
> @@ -3183,7 +3191,7 @@ enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
>                 update_stats_enqueue(cfs_rq, se);
>                 check_spread(cfs_rq, se);
>         }
> -       if (se != cfs_rq->curr)
> +       if (!curr)
>                 __enqueue_entity(cfs_rq, se);
>         se->on_rq = 1;
>

[toc] | [prev] | [next] | [standalone]

#1354363

At Google, we essentially reverted 88ec22d and the subsequent tweaks
to it, keeping vruntime absolute always , instead using
task_move_group_fair to change the basis of relative min_vruntime
between cpus.  We found this made it a lot easier to reason about and
work with corss-cpu computations.  I could post the patch if it would
be of interest...

On Wed, Mar 9, 2016 at 5:06 AM, pavankumar kondeti
<pavankumar.kondeti@gmail.com> wrote:
> Hi Peter,
>
> On Wed, Mar 9, 2016 at 5:34 PM, Peter Zijlstra <peterz@infradead.org> wrote:
>> On Wed, Mar 09, 2016 at 02:52:57PM +0530, Pavan Kondeti wrote:
>>
>>> When a CFS task is enqueued during migration (load balance or change in
>>> affinity), its vruntime is normalized before updating the current and
>>> cfs_rq->min_vruntime.
>>
>> static void
>> enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
>> {
>>         /*
>>          * Update the normalized vruntime before updating min_vruntime
>>          * through calling update_curr().
>>          */
>>         if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_WAKING))
>>                 se->vruntime += cfs_rq->min_vruntime;
>>
>>         update_curr(cfs_rq);
>>
>> This, right? Some idiot wrote a comment but forgot to explain why.
>>
>>> If the current entity is a low priority task or belongs to a cgroup
>>> that has lower cpu.shares and it is the only entity queued, there is a
>>> possibility of big update to the cfs_rq->min_vruntime.
>>
>>> As the migrated task is normalized before this update, it gets an
>>> unfair advantage over tasks queued after this point. If the migrated
>>> task is a CPU hogger, the other CFS tasks queued on this CPU gets
>>> starved.
>>
>> Because it takes a whole while for the newly placed task to gain on the
>> previous task, right?
>>
>
> Yes. The newly woken up task vruntime is adjusted wrt the cfs_rq->min_vruntime.
> The cfs_rq->min_vruntime can potentially be hundreds of msec beyond the
> migrated task.
>
>>> If we add the migrated task to destination CPU cfs_rq's rb tree before
>>> updating the current in enqueue_entity(), the cfs_rq->min_vruntime
>>> does not go beyond the newly migrated task. Is this an acceptable
>>> solution?
>>
>> Hurm.. so I'm not sure how that would solve anything. The existing task
>> would still be shot far into the future.
>>
> In my testing, the problem is gone with this approach.
>
> The update_min_vruntime() called from  update_curr() has a check to make
> sure that cfs_rq->min_vruntime  does not go beyond the leftmost entity
> (in this case it would be the migrated task) vruntime. so we don't see
> the migrated task getting any advantage.
>
>> What you want is to normalize after update_curr()... but we cannot do
>> that in the case cfs_rq->curr == se (which I suppose is what that
>> comment is on about).
>>
>> Does something like the below work?
>>
>
> Thanks for providing this patch. It solved the problem.
>
>> ---
>>  kernel/sched/fair.c | 20 ++++++++++++++------
>>  1 file changed, 14 insertions(+), 6 deletions(-)
>>
>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>> index 33130529e9b5..3c114d971d84 100644
>> --- a/kernel/sched/fair.c
>> +++ b/kernel/sched/fair.c
>> @@ -3157,17 +3157,25 @@ static inline void check_schedstat_required(void)
>>  static void
>>  enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
>>  {
>> +       bool renorm = !(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_WAKING);
>> +       bool curr = cfs_rq->curr == se;
>> +
>>         /*
>> -        * Update the normalized vruntime before updating min_vruntime
>> -        * through calling update_curr().
>> +        * If we're the current task, we must renormalise before calling
>> +        * update_curr().
>>          */
>> -       if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_WAKING))
>> +       if (renorm && curr)
>>                 se->vruntime += cfs_rq->min_vruntime;
>>
>> +       update_curr(cfs_rq);
>> +
>>         /*
>> -        * Update run-time statistics of the 'current'.
>> +        * Otherwise, renormalise after, such that we're placed at the current
>> +        * moment in time, instead of some random moment in the past.
>>          */
>> -       update_curr(cfs_rq);
>> +       if (renorm && !curr)
>> +               se->vruntime += cfs_rq->min_vruntime;
>> +
>>         enqueue_entity_load_avg(cfs_rq, se);
>>         account_entity_enqueue(cfs_rq, se);
>>         update_cfs_shares(cfs_rq);
>> @@ -3183,7 +3191,7 @@ enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
>>                 update_stats_enqueue(cfs_rq, se);
>>                 check_spread(cfs_rq, se);
>>         }
>> -       if (se != cfs_rq->curr)
>> +       if (!curr)
>>                 __enqueue_entity(cfs_rq, se);
>>         se->on_rq = 1;
>>

[toc] | [prev] | [next] | [standalone]

#1354374

On Wed, Mar 09, 2016 at 11:00:42AM -0800, Andrew Hunter wrote:
> At Google, we essentially reverted 88ec22d and the subsequent tweaks
> to it, keeping vruntime absolute always , instead using
> task_move_group_fair to change the basis of relative min_vruntime
> between cpus.  We found this made it a lot easier to reason about and
> work with corss-cpu computations.  I could post the patch if it would
> be of interest...

Yes please, Paul said he would many times.

[toc] | [prev] | [next] | [standalone]

#1354676

On Wed, Mar 09, 2016 at 11:00:42AM -0800, Andrew Hunter wrote:
> At Google, we essentially reverted 88ec22d and the subsequent tweaks
> to it, keeping vruntime absolute always , instead using
> task_move_group_fair to change the basis of relative min_vruntime

Hello, Andrew

I am curious about how it can be done with absolute value. :-)

> between cpus.  We found this made it a lot easier to reason about and
> work with corss-cpu computations.  I could post the patch if it would
> be of interest...

I am interested in it.

Thanks,
Byungchul

> 

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web