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

Groups > linux.kernel > #1656606 > unrolled thread

[PATCH V4 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

  [PATCH V4 1/2] sched/fair: Fix load_balance() affinity redo path Jeffrey Hugo <jhugo@codeaurora.org> - 2017-06-03 00:30 +0200
    Re: [PATCH V4 1/2] sched/fair: Fix load_balance() affinity redo path Jeffrey Hugo <jhugo@codeaurora.org> - 2017-06-05 19:30 +0200
      Re: [PATCH V4 1/2] sched/fair: Fix load_balance() affinity redo path Jeffrey Hugo <jhugo@codeaurora.org> - 2017-06-05 20:40 +0200
    Re: [PATCH V4 1/2] sched/fair: Fix load_balance() affinity redo path Peter Zijlstra <peterz@infradead.org> - 2017-06-06 14:40 +0200
      Re: [PATCH V4 1/2] sched/fair: Fix load_balance() affinity redo path Jeffrey Hugo <jhugo@codeaurora.org> - 2017-06-06 18:00 +0200
      Re: [PATCH V4 1/2] sched/fair: Fix load_balance() affinity redo path Peter Zijlstra <peterz@infradead.org> - 2017-06-06 18:40 +0200

#1656606 — [PATCH V4 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.

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 | 22 ++++++++++------------
 1 file changed, 10 insertions(+), 12 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index d711093..84255ab 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, sched_domain_span(sd), cpu_active_mask);
 
 	schedstat_inc(sd->lb_count[idle]);
 
@@ -8220,7 +8213,12 @@ 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)) {
+			/*
+			 * Go back to "redo" iff the load-balance cpumask
+			 * contains other potential busiest cpus for the
+			 * current sched domain.
+			 */
+			if (!cpumask_subset(cpus, env.dst_grpmask)) {
 				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]

#1658020

On 6/2/2017 4:27 PM, Jeffrey Hugo wrote:
> 
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index d711093..84255ab 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;

Self NACK.  This breaks active_load_balance_cpu_stop().  Looks like 
env->idle == CPU_IDLE, but env->dst_grpmask is uninitialized, so it can 
be NULL, which causes a null pointer dereference a few lines later.

I'm still having a look to see what makes sense to address the issue.


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

#1658061

On 6/5/2017 11:23 AM, Jeffrey Hugo wrote:
> On 6/2/2017 4:27 PM, Jeffrey Hugo wrote:
>>
>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>> index d711093..84255ab 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;
> 
> Self NACK.  This breaks active_load_balance_cpu_stop().  Looks like 
> env->idle == CPU_IDLE, but env->dst_grpmask is uninitialized, so it can 
> be NULL, which causes a null pointer dereference a few lines later.
> 
> I'm still having a look to see what makes sense to address the issue.
> 
> 

As far as I can see, there appears to be two options to resolve the issue -

1. Update active_load_balance_cpu_stop() to initialize dst_grpmask to a 
sane value

2. Undo the proposed changes in load_balance() to "ensure" dst_grpmask 
is valid, and calculate the value on demand when checking to see if the 
redo path needs to be done.

The downside to #1 is that dst_grpmask is not needed in the 
active_load_balance_cpu_stop() path, and the loop to calculate a new 
dst_cpu will be used.  Extra code is evaluated, but there appears to be 
no side effects.

The downside to #2 is that dst_grpmask is valid the majority of the time 
in load_balance(), so calculating it on demand is redundant most of the 
time, but again there appears to be no side effects.

It somewhat feels like a choice of which option is less bad.

Peter/Dietmar, any preferences?

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

#1658737

On Fri, Jun 02, 2017 at 04:27:11PM -0600, Jeffrey Hugo wrote:
> 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 | 22 ++++++++++------------
>  1 file changed, 10 insertions(+), 12 deletions(-)
> 
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index d711093..84255ab 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, sched_domain_span(sd), cpu_active_mask);
>  
>  	schedstat_inc(sd->lb_count[idle]);
>  
> @@ -8220,7 +8213,12 @@ 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)) {
> +			/*
> +			 * Go back to "redo" iff the load-balance cpumask
> +			 * contains other potential busiest cpus for the
> +			 * current sched domain.
> +			 */
> +			if (!cpumask_subset(cpus, env.dst_grpmask)) {
>  				env.loop = 0;
>  				env.loop_break = sched_nr_migrate_break;
>  				goto redo;

So I was struggling with that subset condition. You want to ensure there
are CPUs outside of dst_grpmask left, otherwise balancing at this SD
level doesn't make sense anymore, right?

I think you might want to spell that out a little in that comment.
Currently the comment only explains what it does, which is something we
can read from the code. Comments should explain _why_ we do things and
its failing there.


So with that the problem is that active_load_balance_cpu_stop() calls
into can_migrate_task() with ->idle = CPU_IDLE and !dst_grpmask, which
then goes *bang*. Now active_load_balance_cpu_stop() doesn't need to
re-evaluate anything, so ideally it would just skip this entirely,
right?

So why not do #3:

---
 kernel/sched/fair.c | 7 +++++++
 1 file changed, 7 insertions(+)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 47a0c552c77b..fd639d32fa4c 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -8523,6 +8523,13 @@ static int active_load_balance_cpu_stop(void *data)
 			.src_cpu	= busiest_rq->cpu,
 			.src_rq		= busiest_rq,
 			.idle		= CPU_IDLE,
+			/*
+			 * can_migrate_task() doesn't need to compute new_dst_cpu
+			 * for active balancing. Since we have CPU_IDLE, but no
+			 * @dst_grpmask we need to make that test go away with lying
+			 * about DST_PINNED.
+			 */
+			.flags		= LBF_DST_PINNED,
 		};
 
 		schedstat_inc(sd->alb_count);

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

#1658887

On 6/6/2017 6:30 AM, Peter Zijlstra wrote:
> On Fri, Jun 02, 2017 at 04:27:11PM -0600, Jeffrey Hugo wrote:
>> 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 | 22 ++++++++++------------
>>   1 file changed, 10 insertions(+), 12 deletions(-)
>>
>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>> index d711093..84255ab 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, sched_domain_span(sd), cpu_active_mask);
>>   
>>   	schedstat_inc(sd->lb_count[idle]);
>>   
>> @@ -8220,7 +8213,12 @@ 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)) {
>> +			/*
>> +			 * Go back to "redo" iff the load-balance cpumask
>> +			 * contains other potential busiest cpus for the
>> +			 * current sched domain.
>> +			 */
>> +			if (!cpumask_subset(cpus, env.dst_grpmask)) {
>>   				env.loop = 0;
>>   				env.loop_break = sched_nr_migrate_break;
>>   				goto redo;
> 
> So I was struggling with that subset condition. You want to ensure there
> are CPUs outside of dst_grpmask left, otherwise balancing at this SD
> level doesn't make sense anymore, right?

Correct.

> 
> I think you might want to spell that out a little in that comment.
> Currently the comment only explains what it does, which is something we
> can read from the code. Comments should explain _why_ we do things and
> its failing there.

Agreed.  We will attempt to improve the comment in the next version.

> 
> 
> So with that the problem is that active_load_balance_cpu_stop() calls
> into can_migrate_task() with ->idle = CPU_IDLE and !dst_grpmask, which
> then goes *bang*. Now active_load_balance_cpu_stop() doesn't need to
> re-evaluate anything, so ideally it would just skip this entirely,
> right?

Correct.  Your #3 option below would also work based on our 
understanding, and seems cleaner.  We will validate it as a solution, 
and incorporate into the next version.

Thanks

> 
> So why not do #3:
> 
> ---
>   kernel/sched/fair.c | 7 +++++++
>   1 file changed, 7 insertions(+)
> 
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 47a0c552c77b..fd639d32fa4c 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -8523,6 +8523,13 @@ static int active_load_balance_cpu_stop(void *data)
>   			.src_cpu	= busiest_rq->cpu,
>   			.src_rq		= busiest_rq,
>   			.idle		= CPU_IDLE,
> +			/*
> +			 * can_migrate_task() doesn't need to compute new_dst_cpu
> +			 * for active balancing. Since we have CPU_IDLE, but no
> +			 * @dst_grpmask we need to make that test go away with lying
> +			 * about DST_PINNED.
> +			 */
> +			.flags		= LBF_DST_PINNED,
>   		};
>   
>   		schedstat_inc(sd->alb_count);
> 


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

#1658933

On Tue, Jun 06, 2017 at 02:30:11PM +0200, Peter Zijlstra wrote:

> So with that the problem is that active_load_balance_cpu_stop() calls
> into can_migrate_task() with ->idle = CPU_IDLE and !dst_grpmask, which
> then goes *bang*. Now active_load_balance_cpu_stop() doesn't need to
> re-evaluate anything, so ideally it would just skip this entirely,
> right?
> 
> So why not do #3:
> 
> ---
>  kernel/sched/fair.c | 7 +++++++
>  1 file changed, 7 insertions(+)
> 
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 47a0c552c77b..fd639d32fa4c 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -8523,6 +8523,13 @@ static int active_load_balance_cpu_stop(void *data)
>  			.src_cpu	= busiest_rq->cpu,
>  			.src_rq		= busiest_rq,
>  			.idle		= CPU_IDLE,

So I realized that setting CPU_NEW_IDLE here does the 'same' thing.
Except that would be a 'visible' change in the schedstat output (not
sure anybody really cares about that).

> +			/*
> +			 * can_migrate_task() doesn't need to compute new_dst_cpu
> +			 * for active balancing. Since we have CPU_IDLE, but no
> +			 * @dst_grpmask we need to make that test go away with lying
> +			 * about DST_PINNED.
> +			 */
> +			.flags		= LBF_DST_PINNED,

But given this is trivial and doesn't have any visible side effects,
this seems 'better'.

>  		};
>  
>  		schedstat_inc(sd->alb_count);

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web