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 PHC | |
Open Source and information security mailing list archives
| ||
|
Date: Fri, 22 Mar 2019 16:44:15 +0100 From: Arnd Bergmann <arnd@...db.de> To: stable@...r.kernel.org, Will Deacon <will.deacon@....com>, Florian La Roche <florian.laroche@...glemail.com> Cc: 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>, Arnd Bergmann <arnd@...db.de>, linux-kernel@...r.kernel.org Subject: [BACKPORT 4.4.y 24/25] lib/int_sqrt: optimize small argument 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(+) diff --git a/lib/int_sqrt.c b/lib/int_sqrt.c index 1ef4cc344977..1afb545a37c5 100644 --- a/lib/int_sqrt.c +++ b/lib/int_sqrt.c @@ -22,6 +22,9 @@ unsigned long int_sqrt(unsigned long x) return x; m = 1UL << (BITS_PER_LONG - 2); + while (m > x) + m >>= 2; + while (m != 0) { b = y + m; y >>= 1; -- 2.20.0
Powered by blists - more mailing lists