linux-kernel - Re: [BACKPORT 4.4.y 24/25] lib/int

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 for Android: free password hash cracker in your pocket

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

Date:   Tue, 26 Mar 2019 10:36:07 +0900
From:   Greg KH <gregkh@...uxfoundation.org>
To:     Arnd Bergmann <arnd@...db.de>
Cc:     stable@...r.kernel.org, Will Deacon <will.deacon@....com>,
        Florian La Roche <florian.laroche@...glemail.com>,
        Peter Zijlstra <peterz@...radead.org>,
        Anshul Garg <aksgarg1989@...il.com>,
        Linus Torvalds <torvalds@...ux-foundation.org>,
        Davidlohr Bueso <dave@...olabs.net>,
        Thomas Gleixner <tglx@...utronix.de>,
        Ingo Molnar <mingo@...nel.org>, Joe Perches <joe@...ches.com>,
        David Miller <davem@...emloft.net>,
        Matthew Wilcox <mawilcox@...rosoft.com>,
        Kees Cook <keescook@...omium.org>,
        Michael Davidson <md@...gle.com>,
        Andrew Morton <akpm@...ux-foundation.org>,
        linux-kernel@...r.kernel.org
Subject: Re: [BACKPORT 4.4.y 24/25] lib/int_sqrt: optimize small argument

On Fri, Mar 22, 2019 at 04:44:15PM +0100, Arnd Bergmann wrote:
> From: Peter Zijlstra <peterz@...radead.org>
> 
> The current int_sqrt() computation is sub-optimal for the case of small
> @x.  Which is the interesting case when we're going to do cumulative
> distribution functions on idle times, which we assume to be a random
> variable, where the target residency of the deepest idle state gives an
> upper bound on the variable (5e6ns on recent Intel chips).
> 
> In the case of small @x, the compute loop:
> 
> 	while (m != 0) {
> 		b = y + m;
> 		y >>= 1;
> 
> 		if (x >= b) {
> 			x -= b;
> 			y += m;
> 		}
> 		m >>= 2;
> 	}
> 
> can be reduced to:
> 
> 	while (m > x)
> 		m >>= 2;
> 
> Because y==0, b==m and until x>=m y will remain 0.
> 
> And while this is computationally equivalent, it runs much faster
> because there's less code, in particular less branches.
> 
>       cycles:                 branches:              branch-misses:
> 
> OLD:
> 
> hot:   45.109444 +- 0.044117  44.333392 +- 0.002254  0.018723 +- 0.000593
> cold: 187.737379 +- 0.156678  44.333407 +- 0.002254  6.272844 +- 0.004305
> 
> PRE:
> 
> hot:   67.937492 +- 0.064124  66.999535 +- 0.000488  0.066720 +- 0.001113
> cold: 232.004379 +- 0.332811  66.999527 +- 0.000488  6.914634 +- 0.006568
> 
> POST:
> 
> hot:   43.633557 +- 0.034373  45.333132 +- 0.002277  0.023529 +- 0.000681
> cold: 207.438411 +- 0.125840  45.333132 +- 0.002277  6.976486 +- 0.004219
> 
> Averages computed over all values <128k using a LFSR to generate order.
> Cold numbers have a LFSR based branch trace buffer 'confuser' ran between
> each int_sqrt() invocation.
> 
> Link: http://lkml.kernel.org/r/20171020164644.876503355@infradead.org
> Fixes: 30493cc9dddb ("lib/int_sqrt.c: optimize square root algorithm")
> Signed-off-by: Peter Zijlstra (Intel) <peterz@...radead.org>
> Suggested-by: Anshul Garg <aksgarg1989@...il.com>
> Acked-by: Linus Torvalds <torvalds@...ux-foundation.org>
> Cc: Davidlohr Bueso <dave@...olabs.net>
> Cc: Thomas Gleixner <tglx@...utronix.de>
> Cc: Ingo Molnar <mingo@...nel.org>
> Cc: Will Deacon <will.deacon@....com>
> Cc: Joe Perches <joe@...ches.com>
> Cc: David Miller <davem@...emloft.net>
> Cc: Matthew Wilcox <mawilcox@...rosoft.com>
> Cc: Kees Cook <keescook@...omium.org>
> Cc: Michael Davidson <md@...gle.com>
> Signed-off-by: Andrew Morton <akpm@...ux-foundation.org>
> Signed-off-by: Linus Torvalds <torvalds@...ux-foundation.org>
> (cherry picked from commit 3f3295709edea6268ff1609855f498035286af73)
> Signed-off-by: Arnd Bergmann <arnd@...db.de>
> ---
>  lib/int_sqrt.c | 3 +++
>  1 file changed, 3 insertions(+)

Also added to 4.14.y and 4.9.y