linux-kernel - Re: [PATCH v13 1/3] lib: Add strongly typed 64bit 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: Windows password security audit tool. GUI, reports in PDF.

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

Message-ID: <20180204102043.39516d75@archlinux>
Date:   Sun, 4 Feb 2018 10:20:43 +0000
From:   Jonathan Cameron <jic23@...nel.org>
To:     Crt Mori <cmo@...exis.com>
Cc:     Ingo Molnar <mingo@...nel.org>,
        Andrew Morton <akpm@...ux-foundation.org>,
        Kees Cook <keescook@...omium.org>,
        Rusty Russell <rusty@...tcorp.com.au>,
        Ian Abbott <abbotti@....co.uk>,
        Larry Finger <Larry.Finger@...inger.net>,
        Niklas Soderlund <niklas.soderlund+renesas@...natech.se>,
        Thomas Gleixner <tglx@...utronix.de>,
        Krzysztof Kozlowski <krzk@...nel.org>,
        Masahiro Yamada <yamada.masahiro@...ionext.com>,
        linux-kernel@...r.kernel.org, linux-iio@...r.kernel.org,
        Peter Zijlstra <peterz@...radead.org>,
        Joe Perches <joe@...ches.com>,
        David Laight <David.Laight@...lab.com>
Subject: Re: [PATCH v13 1/3] lib: Add strongly typed 64bit int_sqrt

On Thu, 11 Jan 2018 11:19:57 +0100
Crt Mori <cmo@...exis.com> wrote:

> There is no option to perform 64bit integer sqrt on 32bit platform.
> Added stronger typed int_sqrt64 enables the 64bit calculations to
> be performed on 32bit platforms. Using same algorithm as int_sqrt()
> with strong typing provides enough precision also on 32bit platforms,
> but it sacrifices some performance. In case values are smaller than
> ULONG_MAX the standard int_sqrt is used for calculation to maximize the
> performance due to more native calculations.
> 
> Signed-off-by: Crt Mori <cmo@...exis.com>
Applied to the togreg branch of iio.git and pushed out as testing
for the autobuilders to play with it.

Thanks all for input on this and to Crt for persistence!

Jonathan

> ---
>  include/linux/kernel.h |  9 +++++++++
>  lib/int_sqrt.c         | 31 +++++++++++++++++++++++++++++++
>  2 files changed, 40 insertions(+)
> 
> diff --git a/include/linux/kernel.h b/include/linux/kernel.h
> index 0ad4c3044cf9..e4a3dc64e650 100644
> --- a/include/linux/kernel.h
> +++ b/include/linux/kernel.h
> @@ -460,6 +460,15 @@ extern int func_ptr_is_kernel_text(void *ptr);
>  
>  unsigned long int_sqrt(unsigned long);
>  
> +#if BITS_PER_LONG < 64
> +u32 int_sqrt64(u64 x);
> +#else
> +static inline u32 int_sqrt64(u64 x)
> +{
> +	return (u32)int_sqrt(x);
> +}
> +#endif
> +
>  extern void bust_spinlocks(int yes);
>  extern int oops_in_progress;		/* If set, an oops, panic(), BUG() or die() is in progress */
>  extern int panic_timeout;
> diff --git a/lib/int_sqrt.c b/lib/int_sqrt.c
> index 1ef4cc344977..77386bc611d0 100644
> --- a/lib/int_sqrt.c
> +++ b/lib/int_sqrt.c
> @@ -7,6 +7,7 @@
>  
>  #include <linux/kernel.h>
>  #include <linux/export.h>
> +#include <linux/bitops.h>
>  
>  /**
>   * int_sqrt - rough approximation to sqrt
> @@ -36,3 +37,33 @@ unsigned long int_sqrt(unsigned long x)
>  	return y;
>  }
>  EXPORT_SYMBOL(int_sqrt);
> +
> +#if BITS_PER_LONG < 64
> +/**
> + * int_sqrt64 - strongly typed int_sqrt function when minimum 64 bit input
> + * is expected.
> + * @x: 64bit integer of which to calculate the sqrt
> + */
> +u32 int_sqrt64(u64 x)
> +{
> +	u64 b, m, y = 0;
> +
> +	if (x <= ULONG_MAX)
> +		return int_sqrt((unsigned long) x);
> +
> +	m = 1ULL << (fls64(x) & ~1ULL);
> +	while (m != 0) {
> +		b = y + m;
> +		y >>= 1;
> +
> +		if (x >= b) {
> +			x -= b;
> +			y += m;
> +		}
> +		m >>= 2;
> +	}
> +
> +	return y;
> +}
> +EXPORT_SYMBOL(int_sqrt64);
> +#endif