Re: [PATCH] mul_u64_u64_div_u64: avoid undefined shift value

[Uwe Kleine-König]

Hello Nicolas,

On Fri, Jul 12, 2024 at 01:41:46PM -0400, Nicolas Pitre wrote:
> From: Nicolas Pitre <npitre@xxxxxxxxxxxx>
> 
> 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@xxxxxxxxxxxx>
> Reported-by: kernel test robot <oliver.sang@xxxxxxxxx>
> Closes: https://lore.kernel.org/oe-lkp/202407121652.69e657c5-oliver.sang@xxxxxxxxx
> ---
> 
> 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@xxxxxxxxxxxx>

Best regards
Uwe

Attachment: signature.asc
Description: PGP signature