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

Groups > linux.kernel > #1640618 > unrolled thread

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

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

  [RFC 1/2] sched/fair: Fix load_balance() affinity redo path Jeffrey Hugo <jhugo@codeaurora.org> - 2017-05-12 19:10 +0200
    Re: [RFC 1/2] sched/fair: Fix load_balance() affinity redo path Jeffrey Hugo <jhugo@codeaurora.org> - 2017-05-12 19:30 +0200
      Re: [RFC 1/2] sched/fair: Fix load_balance() affinity redo path Peter Zijlstra <peterz@infradead.org> - 2017-05-12 22:50 +0200
        Re: [RFC 1/2] sched/fair: Fix load_balance() affinity redo path Jeffrey Hugo <jhugo@codeaurora.org> - 2017-05-12 23:00 +0200
    Re: [RFC 1/2] sched/fair: Fix load_balance() affinity redo path Peter Zijlstra <peterz@infradead.org> - 2017-05-12 19:30 +0200
    Re: [RFC 1/2] sched/fair: Fix load_balance() affinity redo path Peter Zijlstra <peterz@infradead.org> - 2017-05-12 22:50 +0200
      Re: [RFC 1/2] sched/fair: Fix load_balance() affinity redo path Jeffrey Hugo <jhugo@codeaurora.org> - 2017-05-12 23:00 +0200
        Re: [RFC 1/2] sched/fair: Fix load_balance() affinity redo path Dietmar Eggemann <dietmar.eggemann@arm.com> - 2017-05-15 17:00 +0200
          Re: [RFC 1/2] sched/fair: Fix load_balance() affinity redo path Jeffrey Hugo <jhugo@codeaurora.org> - 2017-05-18 16:40 +0200

#1640618 — [RFC 1/2] sched/fair: Fix load_balance() affinity redo path

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.

Signed-off-by: Austin Christ <austinwc@codeaurora.org>
Signed-off-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 | 13 ++++++++++++-
 1 file changed, 12 insertions(+), 1 deletion(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index d711093..8f783ba 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -8219,8 +8219,19 @@ 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)) {
+			struct cpumask tmp;
+
+			/* Cpumask of all initially possible busiest cpus. */
+			cpumask_copy(&tmp, sched_domain_span(env.sd));
+			cpumask_clear_cpu(env.dst_cpu, &tmp);
+
 			cpumask_clear_cpu(cpu_of(busiest), cpus);
-			if (!cpumask_empty(cpus)) {
+			/*
+			 * Go back to "redo" iff the load-balance cpumask
+			 * contains other potential busiest cpus for the
+			 * current sched domain.
+			 */
+			if (cpumask_intersects(cpus, &tmp)) {
 				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]

#1640629

On 5/12/2017 11:23 AM, Peter Zijlstra wrote:
> On Fri, May 12, 2017 at 11:01:37AM -0600, Jeffrey Hugo wrote:
> 
>> Signed-off-by: Austin Christ <austinwc@codeaurora.org>
>> Signed-off-by: Dietmar Eggemann <dietmar.eggemann@arm.com>
>> Signed-off-by: Jeffrey Hugo <jhugo@codeaurora.org>
> 
> So per that Chain Austin wrote the patch, who handed it to Dietmar, who
> handed it to you. Except I don't see a From: Austin on.
> 
> What gives?
> 

Austin and I did the investigations and wrote the initial version.  We 
discussed it with Dietmar, who suggested some significant rewrites which 
we felt added to the readability of the code.  The current version 
posted on the list you've seen was basically written by all three of us, 
so I listed the authors in alphabetical order to properly give credit to 
all involved.

Is there a better way to handle patches which have authorship from 
multiple people?

-- 
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] | [next] | [standalone]

#1640740

On Fri, May 12, 2017 at 11:29:05AM -0600, Jeffrey Hugo wrote:
> On 5/12/2017 11:23 AM, Peter Zijlstra wrote:
> >On Fri, May 12, 2017 at 11:01:37AM -0600, Jeffrey Hugo wrote:
> >
> >>Signed-off-by: Austin Christ <austinwc@codeaurora.org>
> >>Signed-off-by: Dietmar Eggemann <dietmar.eggemann@arm.com>
> >>Signed-off-by: Jeffrey Hugo <jhugo@codeaurora.org>
> >
> >So per that Chain Austin wrote the patch, who handed it to Dietmar, who
> >handed it to you. Except I don't see a From: Austin on.
> >
> >What gives?
> >
> 
> Austin and I did the investigations and wrote the initial version.  We
> discussed it with Dietmar, who suggested some significant rewrites which we
> felt added to the readability of the code.  The current version posted on
> the list you've seen was basically written by all three of us, so I listed
> the authors in alphabetical order to properly give credit to all involved.
> 
> Is there a better way to handle patches which have authorship from multiple
> people?

Well, Signed-off-by is only a chain of custody thing. It says who
handled the patches and that they have the right to publish and that
sorts of thing. We have a document describing this.

It does _NOT_ however imply any kind of authorship what so ever. Of
course, the author must be the first in the custody chain, how else
could the patch 'escape'.

Authorship comes from the Author: header, and there's only 1 of those.

Just mention the people by name in the Changelog or something.

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

#1640748

On 5/12/2017 2:44 PM, Peter Zijlstra wrote:
> On Fri, May 12, 2017 at 11:29:05AM -0600, Jeffrey Hugo wrote:
>> On 5/12/2017 11:23 AM, Peter Zijlstra wrote:
>>> On Fri, May 12, 2017 at 11:01:37AM -0600, Jeffrey Hugo wrote:
>>>
>>>> Signed-off-by: Austin Christ <austinwc@codeaurora.org>
>>>> Signed-off-by: Dietmar Eggemann <dietmar.eggemann@arm.com>
>>>> Signed-off-by: Jeffrey Hugo <jhugo@codeaurora.org>
>>>
>>> So per that Chain Austin wrote the patch, who handed it to Dietmar, who
>>> handed it to you. Except I don't see a From: Austin on.
>>>
>>> What gives?
>>>
>>
>> Austin and I did the investigations and wrote the initial version.  We
>> discussed it with Dietmar, who suggested some significant rewrites which we
>> felt added to the readability of the code.  The current version posted on
>> the list you've seen was basically written by all three of us, so I listed
>> the authors in alphabetical order to properly give credit to all involved.
>>
>> Is there a better way to handle patches which have authorship from multiple
>> people?
> 
> Well, Signed-off-by is only a chain of custody thing. It says who
> handled the patches and that they have the right to publish and that
> sorts of thing. We have a document describing this.
> 
> It does _NOT_ however imply any kind of authorship what so ever. Of
> course, the author must be the first in the custody chain, how else
> could the patch 'escape'.
> 
> Authorship comes from the Author: header, and there's only 1 of those.
> 
> Just mention the people by name in the Changelog or something.
> 

I'm not entirely sure I agree with that assessment, but I'll discuss it 
with the folks offline and see what we want to roll into the next patch 
version after seeing what the other comments are.

-- 
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] | [next] | [standalone]

#1640646

On Fri, May 12, 2017 at 11:01:37AM -0600, Jeffrey Hugo wrote:

> Signed-off-by: Austin Christ <austinwc@codeaurora.org>
> Signed-off-by: Dietmar Eggemann <dietmar.eggemann@arm.com>
> Signed-off-by: Jeffrey Hugo <jhugo@codeaurora.org>

So per that Chain Austin wrote the patch, who handed it to Dietmar, who
handed it to you. Except I don't see a From: Austin on.

What gives?

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

#1640739

On Fri, May 12, 2017 at 11:01:37AM -0600, Jeffrey Hugo wrote:
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index d711093..8f783ba 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -8219,8 +8219,19 @@ 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)) {
> +			struct cpumask tmp;

You cannot have cpumask's on stack.

> +
> +			/* Cpumask of all initially possible busiest cpus. */
> +			cpumask_copy(&tmp, sched_domain_span(env.sd));
> +			cpumask_clear_cpu(env.dst_cpu, &tmp);

You forgot to mask with cpu_active_mask.

> +
>  			cpumask_clear_cpu(cpu_of(busiest), cpus);
> -			if (!cpumask_empty(cpus)) {
> +			/*
> +			 * Go back to "redo" iff the load-balance cpumask
> +			 * contains other potential busiest cpus for the
> +			 * current sched domain.
> +			 */
> +			if (cpumask_intersects(cpus, &tmp)) {
>  				env.loop = 0;
>  				env.loop_break = sched_nr_migrate_break;
>  				goto redo;

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

#1640749

On 5/12/2017 2:47 PM, Peter Zijlstra wrote:
> On Fri, May 12, 2017 at 11:01:37AM -0600, Jeffrey Hugo wrote:
>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>> index d711093..8f783ba 100644
>> --- a/kernel/sched/fair.c
>> +++ b/kernel/sched/fair.c
>> @@ -8219,8 +8219,19 @@ 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)) {
>> +			struct cpumask tmp;
> 
> You cannot have cpumask's on stack.

Well, we need a temp variable to store the intermediate values since the 
cpumask_* operations are somewhat limited, and require a "storage" 
parameter.

Do you have any suggestions to meet all of these requirements?

> 
>> +
>> +			/* Cpumask of all initially possible busiest cpus. */
>> +			cpumask_copy(&tmp, sched_domain_span(env.sd));
>> +			cpumask_clear_cpu(env.dst_cpu, &tmp);
> 
> You forgot to mask with cpu_active_mask.

cpus == cpu_active_mask, which we compare against below in just a few 
lines with the cpumask_intersects check.  So, no, I don't think we did 
forget to mask with cpu_active_mask.

> 
>> +
>>   			cpumask_clear_cpu(cpu_of(busiest), cpus);
>> -			if (!cpumask_empty(cpus)) {
>> +			/*
>> +			 * Go back to "redo" iff the load-balance cpumask
>> +			 * contains other potential busiest cpus for the
>> +			 * current sched domain.
>> +			 */
>> +			if (cpumask_intersects(cpus, &tmp)) {
>>   				env.loop = 0;
>>   				env.loop_break = sched_nr_migrate_break;
>>   				goto redo;


-- 
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] | [next] | [standalone]

#1641782

On 12/05/17 21:57, Jeffrey Hugo wrote:
> On 5/12/2017 2:47 PM, Peter Zijlstra wrote:
>> On Fri, May 12, 2017 at 11:01:37AM -0600, Jeffrey Hugo wrote:
>>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>>> index d711093..8f783ba 100644
>>> --- a/kernel/sched/fair.c
>>> +++ b/kernel/sched/fair.c
>>> @@ -8219,8 +8219,19 @@ 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)) {
>>> +            struct cpumask tmp;
>>
>> You cannot have cpumask's on stack.
> 
> Well, we need a temp variable to store the intermediate values since the
> cpumask_* operations are somewhat limited, and require a "storage"
> parameter.
> 
> Do you have any suggestions to meet all of these requirements?

What about we use env.dst_grpmask and check if cpus is an improper
subset of env.dst_grpmask? In this case we have to get rid of
setting env.dst_grpmask = NULL in case of CPU_NEWLY_IDLE which is
IMHO not an issue since it's idle is passed via env into
can_migrate_task().
And cpus has to be and'ed with sched_domain_span(env.sd).

I'm not sure if this will work with 'not fully connected NUMA' (SD_OVERLAP)
though ...

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index a903276fcb62..2ede4c1c9db8 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -6737,10 +6737,10 @@ int can_migrate_task(struct task_struct *p, struct lb_env *env)
                 * our sched_group. We may want to revisit it if we couldn't
                 * meet load balance goals by pulling other tasks on src_cpu.
                 *
-                * Also avoid computing new_dst_cpu if we have already computed
-                * one in current iteration.
+                * Avoid computing new_dst_cpu for NEWLY_IDLE or if we have
+                * already computed one in current iteration.
                 */
-               if (!env->dst_grpmask || (env->flags & LBF_DST_PINNED))
+               if (env->idle == CPU_NEWLY_IDLE || (env->flags & LBF_DST_PINNED))
                        return 0;
 
                /* Prevent to re-select dst_cpu via env's cpus */
@@ -8091,14 +8091,7 @@ static int load_balance(int this_cpu, struct rq *this_rq,
                .tasks          = LIST_HEAD_INIT(env.tasks),
        };
 
-       /*
-        * For NEWLY_IDLE load_balancing, we don't need to consider
-        * other cpus in our group
-        */
-       if (idle == CPU_NEWLY_IDLE)
-               env.dst_grpmask = NULL;
-
-       cpumask_copy(cpus, cpu_active_mask);
+       cpumask_and(cpus, cpu_active_mask, sched_domain_span(env.sd));
 
        schedstat_inc(sd->lb_count[idle]);
 
@@ -8220,7 +8213,7 @@ 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)) {
+                       if (!cpumask_subset(cpus, env.dst_grpmask)) {
                                env.loop = 0;
                                env.loop_break = sched_nr_migrate_break;
                                goto redo;

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

#1644603

On 5/15/2017 8:56 AM, Dietmar Eggemann wrote:
> On 12/05/17 21:57, Jeffrey Hugo wrote:
>> On 5/12/2017 2:47 PM, Peter Zijlstra wrote:
>>> On Fri, May 12, 2017 at 11:01:37AM -0600, Jeffrey Hugo wrote:
>>>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>>>> index d711093..8f783ba 100644
>>>> --- a/kernel/sched/fair.c
>>>> +++ b/kernel/sched/fair.c
>>>> @@ -8219,8 +8219,19 @@ 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)) {
>>>> +            struct cpumask tmp;
>>>
>>> You cannot have cpumask's on stack.
>>
>> Well, we need a temp variable to store the intermediate values since the
>> cpumask_* operations are somewhat limited, and require a "storage"
>> parameter.
>>
>> Do you have any suggestions to meet all of these requirements?
> 
> What about we use env.dst_grpmask and check if cpus is an improper
> subset of env.dst_grpmask? In this case we have to get rid of
> setting env.dst_grpmask = NULL in case of CPU_NEWLY_IDLE which is
> IMHO not an issue since it's idle is passed via env into
> can_migrate_task().
> And cpus has to be and'ed with sched_domain_span(env.sd).
> 
> I'm not sure if this will work with 'not fully connected NUMA' (SD_OVERLAP)
> though ...

Hmm.  I follow the idea, but I'm not too confident in the SD_OVERLAP 
case, and looking at your proposed code, it seems invasive to me - 
changes are needed in what would otherwise be unrelated sections of 
code.  I'd prefer not to go in that direction.  Also, it appears that 
the dst_cpu is still considered as a source for load.

We've got a different idea to address the stack issue, and still keep 
the change "contained", which I'll roll into a V2 today or tomorrow.

-- 
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