linux-kernel - Re: [PATCH] mul_u64_u64_div_u64: avoid undefined shift value

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: <cel6yaebrspena42tv7mewvd7vvnnzycr2pgg4zkh737uwokro@kzxoxatbdodv>
Date: Sat, 13 Jul 2024 14:14:51 +0200
From: Uwe Kleine-König <u.kleine-koenig@...libre.com>
To: Nicolas Pitre <nico@...xnic.net>
Cc: Andrew Morton <akpm@...ux-foundation.org>, 
	linux-kernel@...r.kernel.org
Subject: Re: [PATCH] mul_u64_u64_div_u64: avoid undefined shift value

Hello Nicolas,

On Fri, Jul 12, 2024 at 01:41:46PM -0400, Nicolas Pitre wrote:
> From: Nicolas Pitre <npitre@...libre.com>
> 
> Shifting a value to its type's size or beyond is undefined. This may 
> happen if the product of a * b is not more than 64 bits despite
> ilog2(a) + ilog2(b) being 63 and c having no trailing 0 bits.
> We end up with shift=0 and n_lo >> shift | (n_hi << (64 - shift).
> Take care of that case and add such case to the test module.
> 
> Using __builtin_ctzll() with 0 is also undefined so take care of that
> case too.
> 
> Signed-off-by: Nicolas Pitre <npitre@...libre.com>
> Reported-by: kernel test robot <oliver.sang@...el.com>
> Closes: https://lore.kernel.org/oe-lkp/202407121652.69e657c5-oliver.sang@intel.com
> ---
> 
> Andrew: up to you to fold this in the original or queue it as is.
> 
> diff --git a/lib/math/div64.c b/lib/math/div64.c
> index b7fc752463..5faa29208b 100644
> --- a/lib/math/div64.c
> +++ b/lib/math/div64.c
> @@ -212,11 +212,18 @@ u64 mul_u64_u64_div_u64(u64 a, u64 b, u64 c)
>  
>  #endif
>  
> +	/* make sure c is not zero, trigger exception otherwise */
> +#pragma GCC diagnostic push
> +#pragma GCC diagnostic ignored "-Wdiv-by-zero"
> +	if (unlikely(c == 0))
> +		return 1/0;
> +#pragma GCC diagnostic pop
> +

I wonder if that does the right thing for clang, too.

>  	int shift = __builtin_ctzll(c);
>  
>  	/* try reducing the fraction in case the dividend becomes <= 64 bits */
>  	if ((n_hi >> shift) == 0) {
> -		u64 n = (n_lo >> shift) | (n_hi << (64 - shift));
> +		u64 n = shift ? (n_lo >> shift) | (n_hi << (64 - shift)) : n_lo;

Maybe it's just me, but I'd better understand the following equivalent
assignment:

	u64 n = (n_lo >> shift) | (shift ? n_hi << (64 - shift) : 0)

or maybe even a bit more verbose:

	u64 n = n_lo >> shift;
	/* Shifting by 64 bit is undefined, so only do this operation for shift > 0 */
	if (shift)
		n |= n_hi << (64 - shift);

With or without these suggestions incorporated:

Reviewed-by: Uwe Kleine-König <u.kleine-koenig@...libre.com>

Best regards
Uwe

Download attachment "signature.asc" of type "application/pgp-signature" (489 bytes)