linux-kernel - Re: RFC: documentation of the autogroup feature [v2]

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: <20161125161336.GJ3174@twins.programming.kicks-ass.net>
Date:   Fri, 25 Nov 2016 17:13:36 +0100
From:   Peter Zijlstra <peterz@...radead.org>
To:     "Michael Kerrisk (man-pages)" <mtk.manpages@...il.com>
Cc:     Mike Galbraith <efault@....de>, Ingo Molnar <mingo@...nel.org>,
        linux-man <linux-man@...r.kernel.org>,
        lkml <linux-kernel@...r.kernel.org>,
        Thomas Gleixner <tglx@...utronix.de>
Subject: Re: RFC: documentation of the autogroup feature [v2]

On Fri, Nov 25, 2016 at 05:04:56PM +0100, Peter Zijlstra wrote:
> That is; the whole thing
> becomes, where l denotes the level in the hierarchy and i an
> entity on that level:
> 
>                  l      w_g,i
>   dt_l,i = dt \Prod  ----------
>                 g=0  \Sum w_g,j
> 
> 
> Or more concretely, for E:
> 
>                       w_E
>   dt_1,E = dt_0,C -----------
>                   (w_E + w_F)
> 
>                         w_C               w_E
>          = dt ----------------------- -----------
>               (w_A + w_B + w_C + w_D) (w_E + w_F)
> 

And this also immediately shows one of the 'problems' with it. Since we
don't have floating point in kernel, these fractions are evaluated with
fixed-point arithmetic. Traditionally (and on 32bit) we use 10bit fixed
point, recently we switched to 20bit for 64bit machines.

That change is what bit you on the nice testing.

But it also means that once we run out of fractional bits things go
wobbly. The fractions, as per the above, increase the deeper the group
hierarchy goes but are also affected by the number of CPUs in the system
(not immediately represented in that equation).

Not to mention that many scheduler operations become O(depth) in cost,
which also hurts. An obvious example being task selection, we pick a
runnable entity for each level, until the resulting entity has no
further children (iow. is a task).