[PATCH] lib/int_sqrt.c: optimize for small argument values

[PATCH] lib/int_sqrt.c: optimize for small argument values

[Michael Davidson]

int_sqrt() currently takes approximately constant time
regardless of the value of the argument. By using the
magnitude of the operand to set the initial conditions
for the calculation the cost becomes proportional to
log2 of the argument with the worst case behavior not
being measurably slower than it currently is.

Signed-off-by: Michael Davidson <md@google.com>
---
 lib/int_sqrt.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/int_sqrt.c b/lib/int_sqrt.c
index 1ef4cc344977..8394b0dcecd4 100644
--- a/lib/int_sqrt.c
+++ b/lib/int_sqrt.c
@@ -21,7 +21,7 @@ unsigned long int_sqrt(unsigned long x)
 	if (x <= 1)
 		return x;
 
-	m = 1UL << (BITS_PER_LONG - 2);
+	m = 1UL << (__fls(x) & ~1UL);
 	while (m != 0) {
 		b = y + m;
 		y >>= 1;
-- 
2.15.0.rc1.287.g2b38de12cc-goog

Re: [PATCH] lib/int_sqrt.c: optimize for small argument values

[Kees Cook]

On Thu, Oct 19, 2017 at 1:31 PM, Michael Davidson <md@google.com> wrote:
> int_sqrt() currently takes approximately constant time
> regardless of the value of the argument. By using the
> magnitude of the operand to set the initial conditions
> for the calculation the cost becomes proportional to
> log2 of the argument with the worst case behavior not
> being measurably slower than it currently is.

Maybe a stupid question, but is this function ultimately used by any
crypto that expects it to be constant-time for safety?

Also, is there a specific workload that is meaningfully sped up by this change?

-Kees

>
> Signed-off-by: Michael Davidson <md@google.com>
> ---
>  lib/int_sqrt.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
>
> diff --git a/lib/int_sqrt.c b/lib/int_sqrt.c
> index 1ef4cc344977..8394b0dcecd4 100644
> --- a/lib/int_sqrt.c
> +++ b/lib/int_sqrt.c
> @@ -21,7 +21,7 @@ unsigned long int_sqrt(unsigned long x)
>         if (x <= 1)
>                 return x;
>
> -       m = 1UL << (BITS_PER_LONG - 2);
> +       m = 1UL << (__fls(x) & ~1UL);
>         while (m != 0) {
>                 b = y + m;
>                 y >>= 1;
> --
> 2.15.0.rc1.287.g2b38de12cc-goog
>



-- 
Kees Cook
Pixel Security

Re: [PATCH] lib/int_sqrt.c: optimize for small argument values

[Jason A. Donenfeld]

On Thu, Oct 19, 2017 at 10:42 PM, Kees Cook <keescook@chromium.org> wrote:
> Maybe a stupid question, but is this function ultimately used by any
> crypto that expects it to be constant-time for safety?

Indeed constant time functions for crypto are important. But in this
case, it's unlikely this function would ever be used for real crypto,
which usually works over "bigints" -- integers that are much wider
than a single unsigned long. The algorithm here is just for a single
int. (By the way, if you're into fast integer arithmetic, check cut
this amazing Quake-era inverse squareroot algorithm:
https://en.wikipedia.org/wiki/Fast_inverse_square_root )

I haven't analyzed all the other call sites for side channel
potentials, but a quick cursory look indicates it's pretty boring and
likely uneventful.

One use of int_sqrt that caught my eye was lib/prime_numbers.c, which
itself exposes two functions -- is_prime_number, which is unused, and
next_prime_number, which is only used by some selftests in the i915
drm stuff, but not any actual real kernel code. Talk about bloat.

Re: [PATCH] lib/int_sqrt.c: optimize for small argument values

[Kees Cook]

On Thu, Oct 19, 2017 at 1:56 PM, Jason A. Donenfeld <Jason@zx2c4.com> wrote:
> On Thu, Oct 19, 2017 at 10:42 PM, Kees Cook <keescook@chromium.org> wrote:
>> Maybe a stupid question, but is this function ultimately used by any
>> crypto that expects it to be constant-time for safety?
>
> Indeed constant time functions for crypto are important. But in this
> case, it's unlikely this function would ever be used for real crypto,
> which usually works over "bigints" -- integers that are much wider
> than a single unsigned long. The algorithm here is just for a single
> int. (By the way, if you're into fast integer arithmetic, check cut
> this amazing Quake-era inverse squareroot algorithm:
> https://en.wikipedia.org/wiki/Fast_inverse_square_root )

Oh nice; that's a fun read. :) (And on a related note, hey everyone,
go donate to Wikipedia!)

> I haven't analyzed all the other call sites for side channel
> potentials, but a quick cursory look indicates it's pretty boring and
> likely uneventful.

Okay, that was my quick assessment too.

FWIW:

Acked-by: Kees Cook <keescook@chromium.org>

> One use of int_sqrt that caught my eye was lib/prime_numbers.c, which
> itself exposes two functions -- is_prime_number, which is unused, and
> next_prime_number, which is only used by some selftests in the i915
> drm stuff, but not any actual real kernel code. Talk about bloat.

Heh.

-Kees

-- 
Kees Cook
Pixel Security

Re: [PATCH] lib/int_sqrt.c: optimize for small argument values

[Joe Perches]

On Thu, 2017-10-19 at 13:31 -0700, Michael Davidson wrote:
> int_sqrt() currently takes approximately constant time
> regardless of the value of the argument. By using the
> magnitude of the operand to set the initial conditions
> for the calculation the cost becomes proportional to
> log2 of the argument with the worst case behavior not
> being measurably slower than it currently is.

https://lkml.org/lkml/2017/7/24/408

Re: [PATCH] lib/int_sqrt.c: optimize for small argument values

[Kees Cook]

On Thu, Oct 19, 2017 at 11:13 PM, Joe Perches <joe@perches.com> wrote:
> On Thu, 2017-10-19 at 13:31 -0700, Michael Davidson wrote:
>> int_sqrt() currently takes approximately constant time
>> regardless of the value of the argument. By using the
>> magnitude of the operand to set the initial conditions
>> for the calculation the cost becomes proportional to
>> log2 of the argument with the worst case behavior not
>> being measurably slower than it currently is.
>
> https://lkml.org/lkml/2017/7/24/408

Ah! Cool. I don't see this version queued up for -next. Where does
Peter's version stand?

-Kees

-- 
Kees Cook
Pixel Security

Re: [PATCH] lib/int_sqrt.c: optimize for small argument values

[Peter Zijlstra]

On Fri, Oct 20, 2017 at 07:18:51AM -0700, Kees Cook wrote:
> On Thu, Oct 19, 2017 at 11:13 PM, Joe Perches <joe@perches.com> wrote:
> > On Thu, 2017-10-19 at 13:31 -0700, Michael Davidson wrote:
> >> int_sqrt() currently takes approximately constant time
> >> regardless of the value of the argument. By using the
> >> magnitude of the operand to set the initial conditions
> >> for the calculation the cost becomes proportional to
> >> log2 of the argument with the worst case behavior not
> >> being measurably slower than it currently is.
> >
> > https://lkml.org/lkml/2017/7/24/408
> 
> Ah! Cool. I don't see this version queued up for -next. Where does
> Peter's version stand?

Oh, crud, forgot all about it. I'd have to double check I addressed the
concerns Linus had with my Changelogs, but other than that he seemed to
be OK.