linux-kernel - [PATCH 3.16 094/136] lib/int_sqrt: optimize small argument

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: <lsq.1518323471.871972403@decadent.org.uk>
Date:   Sun, 11 Feb 2018 04:31:11 +0000
From:   Ben Hutchings <ben@...adent.org.uk>
To:     linux-kernel@...r.kernel.org, stable@...r.kernel.org
CC:     akpm@...ux-foundation.org, "Michael Davidson" <md@...gle.com>,
        "Linus Torvalds" <torvalds@...ux-foundation.org>,
        "Will Deacon" <will.deacon@....com>,
        "Matthew Wilcox" <mawilcox@...rosoft.com>,
        "Joe Perches" <joe@...ches.com>,
        "Thomas Gleixner" <tglx@...utronix.de>,
        "Kees Cook" <keescook@...omium.org>,
        "Ingo Molnar" <mingo@...nel.org>,
        "Anshul Garg" <aksgarg1989@...il.com>,
        "Davidlohr Bueso" <dave@...olabs.net>,
        "David Miller" <davem@...emloft.net>,
        "Peter Zijlstra" <peterz@...radead.org>
Subject: [PATCH 3.16 094/136] lib/int_sqrt: optimize small argument

3.16.54-rc1 review patch.  If anyone has any objections, please let me know.

------------------

From: Peter Zijlstra <peterz@...radead.org>

commit 3f3295709edea6268ff1609855f498035286af73 upstream.

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>
Signed-off-by: Ben Hutchings <ben@...adent.org.uk>
---
 lib/int_sqrt.c | 3 +++
 1 file changed, 3 insertions(+)

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