[PATCH 1/2] sched: load_balance: Prevent reselect prev dst_cpu if some pinned

[PATCH 1/2] sched: load_balance: Prevent reselect prev dst_cpu if some pinned

[Vladimir Davydov]

Currently new_dst_cpu is prevented from being reselected actually, not
dst_cpu. This can result in attempting to pull tasks to this_cpu twice.

Signed-off-by: Vladimir Davydov <vdavydov@parallels.com>
---
 kernel/sched/fair.c |    6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 9b3fe1c..cd59640 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -5269,15 +5269,15 @@ more_balance:
 		 */
 		if ((env.flags & LBF_SOME_PINNED) && env.imbalance > 0) {
 
+			/* Prevent to re-select dst_cpu via env's cpus */
+			cpumask_clear_cpu(env.dst_cpu, env.cpus);
+
 			env.dst_rq	 = cpu_rq(env.new_dst_cpu);
 			env.dst_cpu	 = env.new_dst_cpu;
 			env.flags	&= ~LBF_SOME_PINNED;
 			env.loop	 = 0;
 			env.loop_break	 = sched_nr_migrate_break;
 
-			/* Prevent to re-select dst_cpu via env's cpus */
-			cpumask_clear_cpu(env.dst_cpu, env.cpus);
-
 			/*
 			 * Go back to "more_balance" rather than "redo" since we
 			 * need to continue with same src_cpu.
-- 
1.7.10.4

[PATCH 2/2] sched: load_balance: Reset env when going to redo due to all pinned

[Vladimir Davydov]

Firstly, reset env.dst_cpu/dst_rq to this_cpu/this_rq, because it could
have changed in 'some pinned' case. Otherwise, should_we_balance() can
stop balancing beforehand.

Secondly, reset env.flags, because it can have LBF_SOME_PINNED set.

Thirdly, reset env.dst_grpmask cpus in env.cpus to allow handling 'some
pinned' case when pulling tasks from a new busiest cpu.

Signed-off-by: Vladimir Davydov <vdavydov@parallels.com>
---
 kernel/sched/fair.c |   12 ++++++++++--
 1 file changed, 10 insertions(+), 2 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index cd59640..d840e51 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -5289,8 +5289,16 @@ more_balance:
 		if (unlikely(env.flags & LBF_ALL_PINNED)) {
 			cpumask_clear_cpu(cpu_of(busiest), cpus);
 			if (!cpumask_empty(cpus)) {
-				env.loop = 0;
-				env.loop_break = sched_nr_migrate_break;
+				env.dst_cpu	= this_cpu;
+				env.dst_rq	= this_rq;
+				env.flags	= 0;
+				env.loop	= 0;
+				env.loop_break	= sched_nr_migrate_break;
+
+				/* Reset cpus cleared in LBF_SOME_PINNED case */
+				if (env.dst_grpmask)
+					cpumask_or(cpus, cpus, env.dst_grpmask);
+
 				goto redo;
 			}
 			goto out_balanced;
-- 
1.7.10.4

Re: [PATCH 2/2] sched: load_balance: Reset env when going to redo due to all pinned

[Peter Zijlstra]

On Sun, Sep 15, 2013 at 09:30:14PM +0400, Vladimir Davydov wrote:
> Firstly, reset env.dst_cpu/dst_rq to this_cpu/this_rq, because it could
> have changed in 'some pinned' case. Otherwise, should_we_balance() can
> stop balancing beforehand.
> 
> Secondly, reset env.flags, because it can have LBF_SOME_PINNED set.
> 
> Thirdly, reset env.dst_grpmask cpus in env.cpus to allow handling 'some
> pinned' case when pulling tasks from a new busiest cpu.

Did you actually run into any problems because of this?

> Signed-off-by: Vladimir Davydov <vdavydov@parallels.com>
> ---
>  kernel/sched/fair.c |   12 ++++++++++--
>  1 file changed, 10 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index cd59640..d840e51 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -5289,8 +5289,16 @@ more_balance:
>  		if (unlikely(env.flags & LBF_ALL_PINNED)) {
>  			cpumask_clear_cpu(cpu_of(busiest), cpus);
>  			if (!cpumask_empty(cpus)) {
> -				env.loop = 0;
> -				env.loop_break = sched_nr_migrate_break;
> +				env.dst_cpu	= this_cpu;
> +				env.dst_rq	= this_rq;
> +				env.flags	= 0;
> +				env.loop	= 0;
> +				env.loop_break	= sched_nr_migrate_break;
> +
> +				/* Reset cpus cleared in LBF_SOME_PINNED case */
> +				if (env.dst_grpmask)
> +					cpumask_or(cpus, cpus, env.dst_grpmask);
> +
>  				goto redo;
>  			}
>  			goto out_balanced;

So the problem I have with this is that it removes the bound on the
number of iterations we do. Currently we're limited by the bits in cpus,
but by resetting those we can do on and on and on...

Re: [PATCH 1/2] sched: load_balance: Prevent reselect prev dst_cpu if some pinned

[Peter Zijlstra]

On Sun, Sep 15, 2013 at 09:30:13PM +0400, Vladimir Davydov wrote:
> Currently new_dst_cpu is prevented from being reselected actually, not
> dst_cpu. This can result in attempting to pull tasks to this_cpu twice.
> 
> Signed-off-by: Vladimir Davydov <vdavydov@parallels.com>
> ---
>  kernel/sched/fair.c |    6 +++---
>  1 file changed, 3 insertions(+), 3 deletions(-)
> 
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 9b3fe1c..cd59640 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -5269,15 +5269,15 @@ more_balance:
>  		 */
>  		if ((env.flags & LBF_SOME_PINNED) && env.imbalance > 0) {
>  
> +			/* Prevent to re-select dst_cpu via env's cpus */
> +			cpumask_clear_cpu(env.dst_cpu, env.cpus);
> +
>  			env.dst_rq	 = cpu_rq(env.new_dst_cpu);
>  			env.dst_cpu	 = env.new_dst_cpu;
>  			env.flags	&= ~LBF_SOME_PINNED;
>  			env.loop	 = 0;
>  			env.loop_break	 = sched_nr_migrate_break;
>  
> -			/* Prevent to re-select dst_cpu via env's cpus */
> -			cpumask_clear_cpu(env.dst_cpu, env.cpus);
> -
>  			/*
>  			 * Go back to "more_balance" rather than "redo" since we
>  			 * need to continue with same src_cpu.

FWIW please submit patches against tip/master (or at the very least
against tip/sched/core).

I currently picked up:

vladimir_davydov-2_sched-fix_small_imbalance__fix_local-_avg_load___busiest-_avg_load_case.patch
vladimir_davydov-sched-fix_task_h_load_calculation.patch
vladimir_davydov-1_sched-load_balance__prevent_reselect_prev_dst_cpu_if_some_pinned.patch

So I've two patches still outstanding.. one on the <= vs < issue and the
other for loosing the bound on the load-balance passes.

Re: [PATCH 2/2] sched: load_balance: Reset env when going to redo due to all pinned

[Vladimir Davydov]

On 09/16/2013 09:43 AM, Peter Zijlstra wrote:
> On Sun, Sep 15, 2013 at 09:30:14PM +0400, Vladimir Davydov wrote:
>> Firstly, reset env.dst_cpu/dst_rq to this_cpu/this_rq, because it could
>> have changed in 'some pinned' case. Otherwise, should_we_balance() can
>> stop balancing beforehand.
>>
>> Secondly, reset env.flags, because it can have LBF_SOME_PINNED set.
>>
>> Thirdly, reset env.dst_grpmask cpus in env.cpus to allow handling 'some
>> pinned' case when pulling tasks from a new busiest cpu.
> Did you actually run into any problems because of this?

IRL no, and now I see that catching 'all pinned' after 'some pinned' 
case can only happen if a task changes its affinity mask or gets 
throttled during load balance run, which is very unlikely. So this patch 
is rather for sanity and can be safely dropped.

>> Signed-off-by: Vladimir Davydov<vdavydov@parallels.com>
>> ---
>>   kernel/sched/fair.c |   12 ++++++++++--
>>   1 file changed, 10 insertions(+), 2 deletions(-)
>>
>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>> index cd59640..d840e51 100644
>> --- a/kernel/sched/fair.c
>> +++ b/kernel/sched/fair.c
>> @@ -5289,8 +5289,16 @@ more_balance:
>>   		if (unlikely(env.flags & LBF_ALL_PINNED)) {
>>   			cpumask_clear_cpu(cpu_of(busiest), cpus);
>>   			if (!cpumask_empty(cpus)) {
>> -				env.loop = 0;
>> -				env.loop_break = sched_nr_migrate_break;
>> +				env.dst_cpu	= this_cpu;
>> +				env.dst_rq	= this_rq;
>> +				env.flags	= 0;
>> +				env.loop	= 0;
>> +				env.loop_break	= sched_nr_migrate_break;
>> +
>> +				/* Reset cpus cleared in LBF_SOME_PINNED case */
>> +				if (env.dst_grpmask)
>> +					cpumask_or(cpus, cpus, env.dst_grpmask);
>> +
>>   				goto redo;
>>   			}
>>   			goto out_balanced;
> So the problem I have with this is that it removes the bound on the
> number of iterations we do. Currently we're limited by the bits in cpus,
> but by resetting those we can do on and on and on...

find_busiest_group() never selects the local group, doesn't it? So none 
of env.dst_grpmask, which is initialized to 
sched_group_cpus(this_rq->sd), can be selected for the source cpu. That 
said, resetting env.dst_grpmask bits in the cpus bitmask actually 
doesn't affect the number of balance iterations.

Re: [PATCH 2/2] sched: load_balance: Reset env when going to redo due to all pinned

[Peter Zijlstra]

On Mon, Sep 16, 2013 at 12:08:59PM +0400, Vladimir Davydov wrote:
> >>Signed-off-by: Vladimir Davydov<vdavydov@parallels.com>
> >>---
> >>  kernel/sched/fair.c |   12 ++++++++++--
> >>  1 file changed, 10 insertions(+), 2 deletions(-)
> >>
> >>diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> >>index cd59640..d840e51 100644
> >>--- a/kernel/sched/fair.c
> >>+++ b/kernel/sched/fair.c
> >>@@ -5289,8 +5289,16 @@ more_balance:
> >>  		if (unlikely(env.flags & LBF_ALL_PINNED)) {
> >>  			cpumask_clear_cpu(cpu_of(busiest), cpus);
> >>  			if (!cpumask_empty(cpus)) {
> >>-				env.loop = 0;
> >>-				env.loop_break = sched_nr_migrate_break;
> >>+				env.dst_cpu	= this_cpu;
> >>+				env.dst_rq	= this_rq;
> >>+				env.flags	= 0;
> >>+				env.loop	= 0;
> >>+				env.loop_break	= sched_nr_migrate_break;
> >>+
> >>+				/* Reset cpus cleared in LBF_SOME_PINNED case */
> >>+				if (env.dst_grpmask)
> >>+					cpumask_or(cpus, cpus, env.dst_grpmask);
> >>+
> >>  				goto redo;
> >>  			}
> >>  			goto out_balanced;
> >So the problem I have with this is that it removes the bound on the
> >number of iterations we do. Currently we're limited by the bits in cpus,
> >but by resetting those we can do on and on and on...
> 
> find_busiest_group() never selects the local group, doesn't it? So none of
> env.dst_grpmask, which is initialized to sched_group_cpus(this_rq->sd), can
> be selected for the source cpu. That said, resetting env.dst_grpmask bits in
> the cpus bitmask actually doesn't affect the number of balance iterations.

Going by e02e60c10 the bits in cpus are what limit the DST_PINNED
(formerly SOME_PINNED) retry loop.

But yes, as you said, the entire scenario is entirely unlikely. I'll
drop this patch for now.

[tip:sched/core] sched/balancing: Prevent the reselection of a previous env.dst_cpu if some tasks are pinned

[tip-bot for Vladimir Davydov]

Commit-ID:  7aff2e3a56b724b79fa2d5abd10d8231ef8fb0c5
Gitweb:     http://git.kernel.org/tip/7aff2e3a56b724b79fa2d5abd10d8231ef8fb0c5
Author:     Vladimir Davydov <vdavydov@parallels.com>
AuthorDate: Sun, 15 Sep 2013 21:30:13 +0400
Committer:  Ingo Molnar <mingo@kernel.org>
CommitDate: Fri, 20 Sep 2013 12:02:20 +0200

sched/balancing: Prevent the reselection of a previous env.dst_cpu if some tasks are pinned

Currently new_dst_cpu is prevented from being reselected actually, not
dst_cpu. This can result in attempting to pull tasks to this_cpu twice.

Signed-off-by: Vladimir Davydov <vdavydov@parallels.com>
Signed-off-by: Peter Zijlstra <peterz@infradead.org>
Link: http://lkml.kernel.org/r/281f59b6e596c718dd565ad267fc38f5b8e5c995.1379265590.git.vdavydov@parallels.com
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 kernel/sched/fair.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 71c6ef5..0784ab6 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -5261,15 +5261,15 @@ more_balance:
 		 */
 		if ((env.flags & LBF_DST_PINNED) && env.imbalance > 0) {
 
+			/* Prevent to re-select dst_cpu via env's cpus */
+			cpumask_clear_cpu(env.dst_cpu, env.cpus);
+
 			env.dst_rq	 = cpu_rq(env.new_dst_cpu);
 			env.dst_cpu	 = env.new_dst_cpu;
 			env.flags	&= ~LBF_DST_PINNED;
 			env.loop	 = 0;
 			env.loop_break	 = sched_nr_migrate_break;
 
-			/* Prevent to re-select dst_cpu via env's cpus */
-			cpumask_clear_cpu(env.dst_cpu, env.cpus);
-
 			/*
 			 * Go back to "more_balance" rather than "redo" since we
 			 * need to continue with same src_cpu.