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

Groups > linux.kernel > #1644861 > unrolled thread

[PATCH V3 1/2] sched/fair: Fix load_balance() affinity redo path

Started byJeffrey Hugo <jhugo@codeaurora.org>
First post2017-05-18 21:40 +0200
Last post2017-05-24 00:10 +0200
Articles 6 — 3 participants

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  [PATCH V3 1/2] sched/fair: Fix load_balance() affinity redo path Jeffrey Hugo <jhugo@codeaurora.org> - 2017-05-18 21:40 +0200
    Re: [PATCH V3 1/2] sched/fair: Fix load_balance() affinity redo path Dietmar Eggemann <dietmar.eggemann@arm.com> - 2017-05-19 15:40 +0200
      Re: [PATCH V3 1/2] sched/fair: Fix load_balance() affinity redo path Dietmar Eggemann <dietmar.eggemann@arm.com> - 2017-05-22 12:00 +0200
        Re: [PATCH V3 1/2] sched/fair: Fix load_balance() affinity redo path "Christ, Austin" <austinwc@codeaurora.org> - 2017-05-22 22:00 +0200
          Re: [PATCH V3 1/2] sched/fair: Fix load_balance() affinity redo path Dietmar Eggemann <dietmar.eggemann@arm.com> - 2017-05-23 13:50 +0200
            Re: [PATCH V3 1/2] sched/fair: Fix load_balance() affinity redo path Jeffrey Hugo <jhugo@codeaurora.org> - 2017-05-24 00:10 +0200

#1644861 — [PATCH V3 1/2] sched/fair: Fix load_balance() affinity redo path

FromJeffrey Hugo <jhugo@codeaurora.org>
Date2017-05-18 21:40 +0200
Subject[PATCH V3 1/2] sched/fair: Fix load_balance() affinity redo path
Message-ID<tIzrc-7No-15@gated-at.bofh.it>
If load_balance() fails to migrate any tasks because all tasks were
affined, load_balance() removes the source cpu from consideration and
attempts to redo and balance among the new subset of cpus.

There is a bug in this code path where the algorithm considers all active
cpus in the system (minus the source that was just masked out).  This is
not valid for two reasons: some active cpus may not be in the current
scheduling domain and one of the active cpus is dst_cpu. These cpus should
not be considered, as we cannot pull load from them.

Instead of failing out of load_balance(), we may end up redoing the search
with no valid cpus and incorrectly concluding the domain is balanced.
Additionally, if the group_imbalance flag was just set, it may also be
incorrectly unset, thus the flag will not be seen by other cpus in future
load_balance() runs as that algorithm intends.

Fix the check by removing cpus not in the current domain and the dst_cpu
from considertation, thus limiting the evaluation to valid remaining cpus
from which load might be migrated.

Co-authored-by: Austin Christ <austinwc@codeaurora.org>
Co-authored-by: Dietmar Eggemann <dietmar.eggemann@arm.com>
Signed-off-by: Jeffrey Hugo <jhugo@codeaurora.org>
Tested-by: Tyler Baicar <tbaicar@codeaurora.org>
---
 kernel/sched/fair.c | 19 ++++++++++++++++++-
 1 file changed, 18 insertions(+), 1 deletion(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index d711093..a5d41b1 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -8220,7 +8220,24 @@ static int load_balance(int this_cpu, struct rq *this_rq,
 		/* All tasks on this runqueue were pinned by CPU affinity */
 		if (unlikely(env.flags & LBF_ALL_PINNED)) {
 			cpumask_clear_cpu(cpu_of(busiest), cpus);
-			if (!cpumask_empty(cpus)) {
+			/*
+			 * dst_cpu is not a valid busiest cpu in the following
+			 * check since load cannot be pulled from dst_cpu to be
+			 * put on dst_cpu.
+			 */
+			cpumask_clear_cpu(env.dst_cpu, cpus);
+			/*
+			 * Go back to "redo" iff the load-balance cpumask
+			 * contains other potential busiest cpus for the
+			 * current sched domain.
+			 */
+			if (cpumask_intersects(cpus, sched_domain_span(env.sd))) {
+				/*
+				 * Now that the check has passed, reenable
+				 * dst_cpu so that load can be calculated on
+				 * it in the redo path.
+				 */
+				cpumask_set_cpu(env.dst_cpu, cpus);
 				env.loop = 0;
 				env.loop_break = sched_nr_migrate_break;
 				goto redo;
-- 
Qualcomm Datacenter Technologies as an affiliate of Qualcomm Technologies, Inc.
Qualcomm Technologies, Inc. is a member of the
Code Aurora Forum, a Linux Foundation Collaborative Project.

[toc] | [next] | [standalone]

#1645604

FromDietmar Eggemann <dietmar.eggemann@arm.com>
Date2017-05-19 15:40 +0200
Message-ID<tIQil-2MD-7@gated-at.bofh.it>
In reply to#1644861
On 18/05/17 20:36, Jeffrey Hugo wrote:

[...]

> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index d711093..a5d41b1 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -8220,7 +8220,24 @@ static int load_balance(int this_cpu, struct rq *this_rq,
>  		/* All tasks on this runqueue were pinned by CPU affinity */
>  		if (unlikely(env.flags & LBF_ALL_PINNED)) {
>  			cpumask_clear_cpu(cpu_of(busiest), cpus);
> -			if (!cpumask_empty(cpus)) {
> +			/*
> +			 * dst_cpu is not a valid busiest cpu in the following
> +			 * check since load cannot be pulled from dst_cpu to be
> +			 * put on dst_cpu.
> +			 */
> +			cpumask_clear_cpu(env.dst_cpu, cpus);
> +			/*
> +			 * Go back to "redo" iff the load-balance cpumask
> +			 * contains other potential busiest cpus for the
> +			 * current sched domain.
> +			 */
> +			if (cpumask_intersects(cpus, sched_domain_span(env.sd))) {
> +				/*
> +				 * Now that the check has passed, reenable
> +				 * dst_cpu so that load can be calculated on
> +				 * it in the redo path.
> +				 */
> +				cpumask_set_cpu(env.dst_cpu, cpus);

IMHO, this will work nicely and its way easier.

Another idea might be to check if the LBF_ALL_PINNED is set when we
check if we should clean the imbalance flag.

@@ -8307,14 +8307,13 @@ static int load_balance(int this_cpu, struct rq *this_rq,
         * We reach balance although we may have faced some affinity
         * constraints. Clear the imbalance flag if it was set.
         */
-       if (sd_parent) {
+       if (sd_parent && !(env.flags & LBF_ALL_PINNED)) {
                int *group_imbalance = &sd_parent->groups->sgc->imbalance;

                if (*group_imbalance)
                        *group_imbalance = 0;
        }

But I think preventing a needless redo loop is even better ...

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

#1646691

FromDietmar Eggemann <dietmar.eggemann@arm.com>
Date2017-05-22 12:00 +0200
Message-ID<tJSi7-44C-21@gated-at.bofh.it>
In reply to#1645604
On 19/05/17 14:31, Dietmar Eggemann wrote:
> On 18/05/17 20:36, Jeffrey Hugo wrote:
> 
> [...]
> 
>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>> index d711093..a5d41b1 100644
>> --- a/kernel/sched/fair.c
>> +++ b/kernel/sched/fair.c
>> @@ -8220,7 +8220,24 @@ static int load_balance(int this_cpu, struct rq *this_rq,
>>  		/* All tasks on this runqueue were pinned by CPU affinity */
>>  		if (unlikely(env.flags & LBF_ALL_PINNED)) {
>>  			cpumask_clear_cpu(cpu_of(busiest), cpus);
>> -			if (!cpumask_empty(cpus)) {
>> +			/*
>> +			 * dst_cpu is not a valid busiest cpu in the following
>> +			 * check since load cannot be pulled from dst_cpu to be
>> +			 * put on dst_cpu.
>> +			 */
>> +			cpumask_clear_cpu(env.dst_cpu, cpus);
>> +			/*
>> +			 * Go back to "redo" iff the load-balance cpumask
>> +			 * contains other potential busiest cpus for the
>> +			 * current sched domain.
>> +			 */
>> +			if (cpumask_intersects(cpus, sched_domain_span(env.sd))) {
>> +				/*
>> +				 * Now that the check has passed, reenable
>> +				 * dst_cpu so that load can be calculated on
>> +				 * it in the redo path.
>> +				 */
>> +				cpumask_set_cpu(env.dst_cpu, cpus);
> 
> IMHO, this will work nicely and its way easier.

This was too quick ... if we still have other potential dst cpus
available and cpu_of(busiest) is the latest src cpu then this will fail.

It does work on sd with 'group_weight == 1', e.g. your MC sd 'sd->child
== NULL'.

But IMHO 'group_imbalance' propagation has to work on higher sd levels
as well.

> Another idea might be to check if the LBF_ALL_PINNED is set when we
> check if we should clean the imbalance flag.
> 
> @@ -8307,14 +8307,13 @@ static int load_balance(int this_cpu, struct rq *this_rq,
>          * We reach balance although we may have faced some affinity
>          * constraints. Clear the imbalance flag if it was set.
>          */
> -       if (sd_parent) {
> +       if (sd_parent && !(env.flags & LBF_ALL_PINNED)) {
>                 int *group_imbalance = &sd_parent->groups->sgc->imbalance;
> 
>                 if (*group_imbalance)
>                         *group_imbalance = 0;
>         }

[...]

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

#1647316

From"Christ, Austin" <austinwc@codeaurora.org>
Date2017-05-22 22:00 +0200
Message-ID<tK1EJ-1rk-1@gated-at.bofh.it>
In reply to#1646691
Hey Dietmar,


On 5/22/2017 3:48 AM, Dietmar Eggemann wrote:
> On 19/05/17 14:31, Dietmar Eggemann wrote:
>> On 18/05/17 20:36, Jeffrey Hugo wrote:
>>
>> [...]
>>
>>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>>> index d711093..a5d41b1 100644
>>> --- a/kernel/sched/fair.c
>>> +++ b/kernel/sched/fair.c
>>> @@ -8220,7 +8220,24 @@ static int load_balance(int this_cpu, struct rq *this_rq,
>>>   		/* All tasks on this runqueue were pinned by CPU affinity */
>>>   		if (unlikely(env.flags & LBF_ALL_PINNED)) {
>>>   			cpumask_clear_cpu(cpu_of(busiest), cpus);
>>> -			if (!cpumask_empty(cpus)) {
>>> +			/*
>>> +			 * dst_cpu is not a valid busiest cpu in the following
>>> +			 * check since load cannot be pulled from dst_cpu to be
>>> +			 * put on dst_cpu.
>>> +			 */
>>> +			cpumask_clear_cpu(env.dst_cpu, cpus);
>>> +			/*
>>> +			 * Go back to "redo" iff the load-balance cpumask
>>> +			 * contains other potential busiest cpus for the
>>> +			 * current sched domain.
>>> +			 */
>>> +			if (cpumask_intersects(cpus, sched_domain_span(env.sd))) {
>>> +				/*
>>> +				 * Now that the check has passed, reenable
>>> +				 * dst_cpu so that load can be calculated on
>>> +				 * it in the redo path.
>>> +				 */
>>> +				cpumask_set_cpu(env.dst_cpu, cpus);
>> IMHO, this will work nicely and its way easier.
> This was too quick ... if we still have other potential dst cpus
> available and cpu_of(busiest) is the latest src cpu then this will fail.
>
> It does work on sd with 'group_weight == 1', e.g. your MC sd 'sd->child
> == NULL'.
>
> But IMHO 'group_imbalance' propagation has to work on higher sd levels
> as well.
Can you clarify the fail case you are seeing? We are only aware of 
dst_cpu being changed under [1] where a dst_cpu will try to move work to 
one of its sched_group siblings.

I'm also not entirely sure I understand what you mean about the flag 
being propagated to higher sd levels.
>> Another idea might be to check if the LBF_ALL_PINNED is set when we
>> check if we should clean the imbalance flag.
>>
>> @@ -8307,14 +8307,13 @@ static int load_balance(int this_cpu, struct rq *this_rq,
>>           * We reach balance although we may have faced some affinity
>>           * constraints. Clear the imbalance flag if it was set.
>>           */
>> -       if (sd_parent) {
>> +       if (sd_parent && !(env.flags & LBF_ALL_PINNED)) {
>>                  int *group_imbalance = &sd_parent->groups->sgc->imbalance;
>>
>>                  if (*group_imbalance)
>>                          *group_imbalance = 0;
>>          }
> [...]

[1] - 
http://elixir.free-electrons.com/linux/latest/source/kernel/sched/fair.c#L8140

--
Qualcomm Datacenter Technologies as an affiliate of Qualcomm Technologies, Inc.
Qualcomm Technologies, Inc. is a member of the
Code Aurora Forum, a Linux Foundation Collaborative Project.

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

#1647961

FromDietmar Eggemann <dietmar.eggemann@arm.com>
Date2017-05-23 13:50 +0200
Message-ID<tKgu6-2DN-5@gated-at.bofh.it>
In reply to#1647316
Hey Austin,

On 22/05/17 20:57, Christ, Austin wrote:
> Hey Dietmar,
> 
> 
> On 5/22/2017 3:48 AM, Dietmar Eggemann wrote:
>> On 19/05/17 14:31, Dietmar Eggemann wrote:
>>> On 18/05/17 20:36, Jeffrey Hugo wrote:
>>>
>>> [...]
>>>
>>>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>>>> index d711093..a5d41b1 100644
>>>> --- a/kernel/sched/fair.c
>>>> +++ b/kernel/sched/fair.c
>>>> @@ -8220,7 +8220,24 @@ static int load_balance(int this_cpu, struct
>>>> rq *this_rq,
>>>>           /* All tasks on this runqueue were pinned by CPU affinity */
>>>>           if (unlikely(env.flags & LBF_ALL_PINNED)) {
>>>>               cpumask_clear_cpu(cpu_of(busiest), cpus);
>>>> -            if (!cpumask_empty(cpus)) {
>>>> +            /*
>>>> +             * dst_cpu is not a valid busiest cpu in the following
>>>> +             * check since load cannot be pulled from dst_cpu to be
>>>> +             * put on dst_cpu.
>>>> +             */
>>>> +            cpumask_clear_cpu(env.dst_cpu, cpus);
>>>> +            /*
>>>> +             * Go back to "redo" iff the load-balance cpumask
>>>> +             * contains other potential busiest cpus for the
>>>> +             * current sched domain.
>>>> +             */
>>>> +            if (cpumask_intersects(cpus, sched_domain_span(env.sd))) {
>>>> +                /*
>>>> +                 * Now that the check has passed, reenable
>>>> +                 * dst_cpu so that load can be calculated on
>>>> +                 * it in the redo path.
>>>> +                 */
>>>> +                cpumask_set_cpu(env.dst_cpu, cpus);
>>> IMHO, this will work nicely and its way easier.
>> This was too quick ... if we still have other potential dst cpus
>> available and cpu_of(busiest) is the latest src cpu then this will fail.
>>
>> It does work on sd with 'group_weight == 1', e.g. your MC sd 'sd->child
>> == NULL'.
>>
>> But IMHO 'group_imbalance' propagation has to work on higher sd levels
>> as well.
> Can you clarify the fail case you are seeing? We are only aware of
> dst_cpu being changed under [1] where a dst_cpu will try to move work to
> one of its sched_group siblings.
> 
> I'm also not entirely sure I understand what you mean about the flag
> being propagated to higher sd levels.

The propagation of 'imbalance' information should not only happen
between lowest sd (sd->child == NULL) and its parent (MC->DIE in your
example) but between all {sd, sd->parent} pairs.

Imagine your machine had another sd on top of DIE.

I recreated the issue I pointed out on my hikey board (2*4) (w/o this
extra sd on top of DIE), hotplug-ed out cpu 2,3,6,7 so I have a system
with the following DIE sched_groups (sg):

sg1(0,1) and sg2(4,5) <- the DIE level sg's contain more than 1 logical cpu.

As a workload I run 4 25% tasks affine to [0,1]. These tasks are
'SOURCE' PINNED for a DIE lb sg2<-sg1.

With:

if (unlikely(env.flags & LBF_ALL_PINNED)) {
  cpumask_clear_cpu(cpu_of(busiest), cpus);
    if (!cpumask_empty(cpus)) {
      ...

      printk("goto redo: sd=%s dst_cpu=%d src_cpu=%d cpus=%*pbl
              dst_grpmask=%*pbl\n",
              sd->name, env.dst_cpu, cpu_of(busiest),
              cpumask_pr_args(cpus),
              cpumask_pr_args(env.dst_grpmask));

      goto redo;
    }

While running the workload I sometimes get:

...
goto redo: sd=DIE dst_cpu=4 src_cpu=1 cpus=0,4-5 dst_grpmask=4-5
goto redo: sd=DIE dst_cpu=4 src_cpu=0 cpus=4-5 dst_grpmask=4-5
...

So even though 'redo' handling has tried both possible src_cpu's we
would still enter another 'redo' path even you remove dst_cpu=4
temporarily because of cpu=5.

You could replace:

cpumask_clear_cpu(env.dst_cpu, cpus)
cpumask_set_cpu(env.dst_cpu, cpus)

with

cpumask_andnot(cpus, cpus, env.dst_grpmask)
cpumask_or(cpus, cpus, env.dst_grpmask)

but then env.dst_grpmask can't be set to NULL for CPU_NEWLY_IDLE and
you're almost at the snippet I sent out for v1:
https://marc.info/?l=linux-kernel&m=149486020010389&w=2

[...]

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

#1648889

FromJeffrey Hugo <jhugo@codeaurora.org>
Date2017-05-24 00:10 +0200
Message-ID<tKqa7-18X-33@gated-at.bofh.it>
In reply to#1647961
On 5/23/2017 5:45 AM, Dietmar Eggemann wrote:
> Hey Austin,
> 
> On 22/05/17 20:57, Christ, Austin wrote:
>> Hey Dietmar,
>>
>>
>> On 5/22/2017 3:48 AM, Dietmar Eggemann wrote:
>>> On 19/05/17 14:31, Dietmar Eggemann wrote:
>>>> On 18/05/17 20:36, Jeffrey Hugo wrote:
>>>>
>>>> [...]
>>>>
>>>>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>>>>> index d711093..a5d41b1 100644
>>>>> --- a/kernel/sched/fair.c
>>>>> +++ b/kernel/sched/fair.c
>>>>> @@ -8220,7 +8220,24 @@ static int load_balance(int this_cpu, struct
>>>>> rq *this_rq,
>>>>>            /* All tasks on this runqueue were pinned by CPU affinity */
>>>>>            if (unlikely(env.flags & LBF_ALL_PINNED)) {
>>>>>                cpumask_clear_cpu(cpu_of(busiest), cpus);
>>>>> -            if (!cpumask_empty(cpus)) {
>>>>> +            /*
>>>>> +             * dst_cpu is not a valid busiest cpu in the following
>>>>> +             * check since load cannot be pulled from dst_cpu to be
>>>>> +             * put on dst_cpu.
>>>>> +             */
>>>>> +            cpumask_clear_cpu(env.dst_cpu, cpus);
>>>>> +            /*
>>>>> +             * Go back to "redo" iff the load-balance cpumask
>>>>> +             * contains other potential busiest cpus for the
>>>>> +             * current sched domain.
>>>>> +             */
>>>>> +            if (cpumask_intersects(cpus, sched_domain_span(env.sd))) {
>>>>> +                /*
>>>>> +                 * Now that the check has passed, reenable
>>>>> +                 * dst_cpu so that load can be calculated on
>>>>> +                 * it in the redo path.
>>>>> +                 */
>>>>> +                cpumask_set_cpu(env.dst_cpu, cpus);
>>>> IMHO, this will work nicely and its way easier.
>>> This was too quick ... if we still have other potential dst cpus
>>> available and cpu_of(busiest) is the latest src cpu then this will fail.
>>>
>>> It does work on sd with 'group_weight == 1', e.g. your MC sd 'sd->child
>>> == NULL'.
>>>
>>> But IMHO 'group_imbalance' propagation has to work on higher sd levels
>>> as well.
>> Can you clarify the fail case you are seeing? We are only aware of
>> dst_cpu being changed under [1] where a dst_cpu will try to move work to
>> one of its sched_group siblings.
>>
>> I'm also not entirely sure I understand what you mean about the flag
>> being propagated to higher sd levels.
> 
> The propagation of 'imbalance' information should not only happen
> between lowest sd (sd->child == NULL) and its parent (MC->DIE in your
> example) but between all {sd, sd->parent} pairs.
> 
> Imagine your machine had another sd on top of DIE.
> 
> I recreated the issue I pointed out on my hikey board (2*4) (w/o this
> extra sd on top of DIE), hotplug-ed out cpu 2,3,6,7 so I have a system
> with the following DIE sched_groups (sg):
> 
> sg1(0,1) and sg2(4,5) <- the DIE level sg's contain more than 1 logical cpu.
> 
> As a workload I run 4 25% tasks affine to [0,1]. These tasks are
> 'SOURCE' PINNED for a DIE lb sg2<-sg1.
> 
> With:
> 
> if (unlikely(env.flags & LBF_ALL_PINNED)) {
>    cpumask_clear_cpu(cpu_of(busiest), cpus);
>      if (!cpumask_empty(cpus)) {
>        ...
> 
>        printk("goto redo: sd=%s dst_cpu=%d src_cpu=%d cpus=%*pbl
>                dst_grpmask=%*pbl\n",
>                sd->name, env.dst_cpu, cpu_of(busiest),
>                cpumask_pr_args(cpus),
>                cpumask_pr_args(env.dst_grpmask));
> 
>        goto redo;
>      }
> 
> While running the workload I sometimes get:
> 
> ...
> goto redo: sd=DIE dst_cpu=4 src_cpu=1 cpus=0,4-5 dst_grpmask=4-5
> goto redo: sd=DIE dst_cpu=4 src_cpu=0 cpus=4-5 dst_grpmask=4-5
> ...
> 
> So even though 'redo' handling has tried both possible src_cpu's we
> would still enter another 'redo' path even you remove dst_cpu=4
> temporarily because of cpu=5.
> 
> You could replace:
> 
> cpumask_clear_cpu(env.dst_cpu, cpus)
> cpumask_set_cpu(env.dst_cpu, cpus)
> 
> with
> 
> cpumask_andnot(cpus, cpus, env.dst_grpmask)
> cpumask_or(cpus, cpus, env.dst_grpmask)
> 
> but then env.dst_grpmask can't be set to NULL for CPU_NEWLY_IDLE and
> you're almost at the snippet I sent out for v1:
> https://marc.info/?l=linux-kernel&m=149486020010389&w=2
> 
> [...]
> 

I see what you mean.  You are right, our current proposal is flawed in 
this regard.  We'll take a look for a bit and see if we come up with any 
other ideas.

-- 
Jeffrey Hugo
Qualcomm Datacenter Technologies as an affiliate of Qualcomm 
Technologies, Inc.
Qualcomm Technologies, Inc. is a member of the
Code Aurora Forum, a Linux Foundation Collaborative Project.

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web