[PATCH] sched: fix inv_weight calc

[PATCH] sched: fix inv_weight calc

[Gregory Haskins]

We currently have a bug in sched-devel where the system will fail to
balance tasks if CONFIG_FAIR_GROUP_SCHED=n.  To reproduce, simply launch
a workload with multiple tasks and observe (either via top or
/proc/sched_debug) that the tasks do not distribute much (if at all)
around to all available cores. Instead, they tend to clump on one processor
while the other cores are idle.

Bisecting, we found the culprit to be:

	commit 1b9552e878a5db3388eba8660e8d8400020a07e9
	Author: Peter Zijlstra <a.p.zijlstra@chello.nl>
	Date:   Tue Apr 29 13:47:36 2008 +0200
	Subject: sched: higher granularity load on 64bit systems

Once we identified this patch as the problem, I studied what possible
effect it could have with FAIR_GROUP_SCHED=n vs y.  Most of the code in
1b9552e8 would be compiled out if we disable group-scheduling, but there
is one particular logic change in calc_delta_mine() that affects both modes
that looked suspicious.  It changes the computation of the inverse-weight
from:

    inv_weight = (WMULT_CONST-weight/2)/(weight+1)

to

    inv_weight = 1+(WMULT_CONST-weight/2)/(weight+1)

This patch restores the algorithm to its original logic, and seems to solve
the regression for me.  I can't really wrap my head around the original
intent of the "+1" change, or whether reverting the change will cause a
ripple effect somewhere else.  All I can confirm is that the system will
once again balance load with this logic reverted to its previous form.

Thanks to my colleage, David Bahi, for doing all the legwork on the bisect.
And thanks to Peter Zijlstra for guiding me on all things CFS as I stuggle
to come up to speed on the non-RT portions of the scheduler.

Signed-off-by: Gregory Haskins <ghaskins@novell.com>
CC: David Bahi <dbahi@novell.com>
CC: Ingo Molnar <mingo@elte.hu>
CC: Peter Zijlstra <peterz@infradead.org>
---

 kernel/sched.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/kernel/sched.c b/kernel/sched.c
index 32ef6c8..8326e20 100644
--- a/kernel/sched.c
+++ b/kernel/sched.c
@@ -1562,7 +1562,7 @@ calc_delta_mine(unsigned long delta_exec, unsigned long weight,
 	if (unlikely(!lw->inv_weight)) {
 		unsigned long inv_wls = inv_WLS(lw->weight);
 
-		lw->inv_weight = 1 + (WMULT_CONST-inv_wls/2) / (inv_wls+1);
+		lw->inv_weight = (WMULT_CONST-inv_wls/2) / (inv_wls+1);
 	}
 
 	tmp = inv_WLS((u64)delta_exec * weight);

Re: [PATCH] sched: fix inv_weight calc

[Peter Zijlstra]

On Wed, 2008-04-30 at 13:15 -0400, Gregory Haskins wrote:
> We currently have a bug in sched-devel where the system will fail to
> balance tasks if CONFIG_FAIR_GROUP_SCHED=n.  To reproduce, simply launch
> a workload with multiple tasks and observe (either via top or
> /proc/sched_debug) that the tasks do not distribute much (if at all)
> around to all available cores. Instead, they tend to clump on one processor
> while the other cores are idle.
> 
> Bisecting, we found the culprit to be:
> 
> 	commit 1b9552e878a5db3388eba8660e8d8400020a07e9
> 	Author: Peter Zijlstra <a.p.zijlstra@chello.nl>
> 	Date:   Tue Apr 29 13:47:36 2008 +0200
> 	Subject: sched: higher granularity load on 64bit systems
> 
> Once we identified this patch as the problem, I studied what possible
> effect it could have with FAIR_GROUP_SCHED=n vs y.  Most of the code in
> 1b9552e8 would be compiled out if we disable group-scheduling, but there
> is one particular logic change in calc_delta_mine() that affects both modes
> that looked suspicious.  It changes the computation of the inverse-weight
> from:
> 
>     inv_weight = (WMULT_CONST-weight/2)/(weight+1)
> 
> to
> 
>     inv_weight = 1+(WMULT_CONST-weight/2)/(weight+1)
> 
> This patch restores the algorithm to its original logic, and seems to solve
> the regression for me.  I can't really wrap my head around the original
> intent of the "+1" change, or whether reverting the change will cause a
> ripple effect somewhere else.  All I can confirm is that the system will
> once again balance load with this logic reverted to its previous form.

I didn't intend that change to sneak into this patch - but it was
sort-of intentional. My rationale was, a normal rounding division does:

  (x + y/2) / y

Since our 'x' is at the upper end of our modulo space we can't add to it
for it would wrap and end up small. Therefore we do:

 (x - y/2) / y

Which would result in 1 less than expected, hence I added that 1 back.

Now I'm equally puzzled on its effect. Nor do I mind its removal, but I
would like to understand why it has such drastic effects.

> Thanks to my colleage, David Bahi, for doing all the legwork on the bisect.
> And thanks to Peter Zijlstra for guiding me on all things CFS as I stuggle
> to come up to speed on the non-RT portions of the scheduler.
> 
> Signed-off-by: Gregory Haskins <ghaskins@novell.com>
> CC: David Bahi <dbahi@novell.com>
> CC: Ingo Molnar <mingo@elte.hu>
> CC: Peter Zijlstra <peterz@infradead.org>
> ---
> 
>  kernel/sched.c |    2 +-
>  1 files changed, 1 insertions(+), 1 deletions(-)
> 
> diff --git a/kernel/sched.c b/kernel/sched.c
> index 32ef6c8..8326e20 100644
> --- a/kernel/sched.c
> +++ b/kernel/sched.c
> @@ -1562,7 +1562,7 @@ calc_delta_mine(unsigned long delta_exec, unsigned long weight,
>  	if (unlikely(!lw->inv_weight)) {
>  		unsigned long inv_wls = inv_WLS(lw->weight);
>  
> -		lw->inv_weight = 1 + (WMULT_CONST-inv_wls/2) / (inv_wls+1);
> +		lw->inv_weight = (WMULT_CONST-inv_wls/2) / (inv_wls+1);
>  	}
>  
>  	tmp = inv_WLS((u64)delta_exec * weight);
> 

Re: [PATCH] sched: fix inv_weight calc

[Gregory Haskins]

(Peter and I have been discussing this on IRC, but thought we should take some new findings to a wider audience)....

>>> On Wed, Apr 30, 2008 at  2:45 PM, in message <1209581148.6433.47.camel@lappy>,
Peter Zijlstra <peterz@infradead.org> wrote: 
> On Wed, 2008-04-30 at 13:15 -0400, Gregory Haskins wrote:
>> We currently have a bug in sched-devel where the system will fail to
>> balance tasks if CONFIG_FAIR_GROUP_SCHED=n.  To reproduce, simply launch
>> a workload with multiple tasks and observe (either via top or
>> /proc/sched_debug) that the tasks do not distribute much (if at all)
>> around to all available cores. Instead, they tend to clump on one processor
>> while the other cores are idle.
>> 
>> Bisecting, we found the culprit to be:
>> 
>> 	commit 1b9552e878a5db3388eba8660e8d8400020a07e9
>> 	Author: Peter Zijlstra <a.p.zijlstra@chello.nl>
>> 	Date:   Tue Apr 29 13:47:36 2008 +0200
>> 	Subject: sched: higher granularity load on 64bit systems
>> 
>> Once we identified this patch as the problem, I studied what possible
>> effect it could have with FAIR_GROUP_SCHED=n vs y.  Most of the code in
>> 1b9552e8 would be compiled out if we disable group-scheduling, but there
>> is one particular logic change in calc_delta_mine() that affects both modes
>> that looked suspicious.  It changes the computation of the inverse-weight
>> from:
>> 
>>     inv_weight = (WMULT_CONST-weight/2)/(weight+1)
>> 
>> to
>> 
>>     inv_weight = 1+(WMULT_CONST-weight/2)/(weight+1)
>> 
>> This patch restores the algorithm to its original logic, and seems to solve
>> the regression for me.  I can't really wrap my head around the original
>> intent of the "+1" change, or whether reverting the change will cause a
>> ripple effect somewhere else.  All I can confirm is that the system will
>> once again balance load with this logic reverted to its previous form.
> 
> I didn't intend that change to sneak into this patch - but it was
> sort-of intentional. My rationale was, a normal rounding division does:
> 
>   (x + y/2) / y
> 
> Since our 'x' is at the upper end of our modulo space we can't add to it
> for it would wrap and end up small. Therefore we do:
> 
>  (x - y/2) / y
> 
> Which would result in 1 less than expected, hence I added that 1 back.

Ah, yes.  That makes sense.

> 
> Now I'm equally puzzled on its effect. Nor do I mind its removal, but I
> would like to understand why it has such drastic effects.

Nevermind my patch, its bogus.  I was mistaken earlier in thinking it was better with the "+1" removed.  Subsequent testing has demonstrated that the issue is still present, even with my "fix" applied.  The root issue seems to be real, but I cant spy it in the code via visual inspection.  Reverting the patch outright does seem to restore proper balancer behavior.  (Note that the commit-id for Peter's patch has since changed...probably due to a recent rebase in sched-devel).  Perhaps someone with a better understanding of the load calculation will see it.

Regards,
-Greg

Re: [PATCH] sched: fix inv_weight calc

[Peter Zijlstra]

On Thu, 2008-05-01 at 10:54 -0600, Gregory Haskins wrote:
> (Peter and I have been discussing this on IRC, but thought we should
> take some new findings to a wider audience)....
> 
> >>> On Wed, Apr 30, 2008 at  2:45 PM, in message <1209581148.6433.47.camel@lappy>,
> Peter Zijlstra <peterz@infradead.org> wrote: 
> > On Wed, 2008-04-30 at 13:15 -0400, Gregory Haskins wrote:
> >> We currently have a bug in sched-devel where the system will fail to
> >> balance tasks if CONFIG_FAIR_GROUP_SCHED=n.  To reproduce, simply launch
> >> a workload with multiple tasks and observe (either via top or
> >> /proc/sched_debug) that the tasks do not distribute much (if at all)
> >> around to all available cores. Instead, they tend to clump on one processor
> >> while the other cores are idle.
> >> 
> >> Bisecting, we found the culprit to be:
> >> 
> >> 	commit 1b9552e878a5db3388eba8660e8d8400020a07e9
> >> 	Author: Peter Zijlstra <a.p.zijlstra@chello.nl>
> >> 	Date:   Tue Apr 29 13:47:36 2008 +0200
> >> 	Subject: sched: higher granularity load on 64bit systems
> >> 
> >> Once we identified this patch as the problem, I studied what possible
> >> effect it could have with FAIR_GROUP_SCHED=n vs y.  Most of the code in
> >> 1b9552e8 would be compiled out if we disable group-scheduling, but there
> >> is one particular logic change in calc_delta_mine() that affects both modes
> >> that looked suspicious.  It changes the computation of the inverse-weight
> >> from:
> >> 
> >>     inv_weight = (WMULT_CONST-weight/2)/(weight+1)
> >> 
> >> to
> >> 
> >>     inv_weight = 1+(WMULT_CONST-weight/2)/(weight+1)
> >> 
> >> This patch restores the algorithm to its original logic, and seems to solve
> >> the regression for me.  I can't really wrap my head around the original
> >> intent of the "+1" change, or whether reverting the change will cause a
> >> ripple effect somewhere else.  All I can confirm is that the system will
> >> once again balance load with this logic reverted to its previous form.
> > 
> > I didn't intend that change to sneak into this patch - but it was
> > sort-of intentional. My rationale was, a normal rounding division does:
> > 
> >   (x + y/2) / y
> > 
> > Since our 'x' is at the upper end of our modulo space we can't add to it
> > for it would wrap and end up small. Therefore we do:
> > 
> >  (x - y/2) / y
> > 
> > Which would result in 1 less than expected, hence I added that 1 back.
> 
> Ah, yes.  That makes sense.
> 
> > 
> > Now I'm equally puzzled on its effect. Nor do I mind its removal, but I
> > would like to understand why it has such drastic effects.
> 
> Nevermind my patch, its bogus.  I was mistaken earlier in thinking it
> was better with the "+1" removed.  Subsequent testing has demonstrated
> that the issue is still present, even with my "fix" applied.  The root
> issue seems to be real, but I cant spy it in the code via visual
> inspection.  Reverting the patch outright does seem to restore proper
> balancer behavior.  (Note that the commit-id for Peter's patch has
> since changed...probably due to a recent rebase in sched-devel).
> Perhaps someone with a better understanding of the load calculation
> will see it.


Ingo, can you drop this patch for now? - it seems to cause grief to
several people. I'll keep it around in my tree in the hope of figuring
out why such a seemingly simple patch breaks so much.