linux-kernel - Re: [PATCH] sched: fix inv

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Thu, 01 May 2008 10:54:59 -0600
From:	"Gregory Haskins" <ghaskins@...ell.com>
To:	"Peter Zijlstra" <peterz@...radead.org>
Cc:	"Ingo Molnar" <mingo@...e.hu>, "David Bahi" <DBahi@...ell.com>,
	<linux-kernel@...r.kernel.org>
Subject: Re: [PATCH] sched: fix inv_weight calc

(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@...py>,
Peter Zijlstra <peterz@...radead.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@...llo.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



--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/