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]

Message-Id: <1209581148.6433.47.camel@lappy>
Date:	Wed, 30 Apr 2008 20:45:48 +0200
From:	Peter Zijlstra <peterz@...radead.org>
To:	Gregory Haskins <ghaskins@...ell.com>
Cc:	Ingo Molnar <mingo@...e.hu>, David Bahi <dbahi@...ell.com>,
	linux-kernel@...r.kernel.org
Subject: Re: [PATCH] sched: fix inv_weight calc

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.

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@...ell.com>
> CC: David Bahi <dbahi@...ell.com>
> CC: Ingo Molnar <mingo@...e.hu>
> CC: Peter Zijlstra <peterz@...radead.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);
> 

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