From: Nicolas Pitre <npitre@baylibre.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@baylibre.com>
Reported-by: kernel test robot <oliver.sang@intel.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
+
 	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;
 
 		return div64_u64(n, c >> shift);
 		/*
diff --git a/lib/math/test_mul_u64_u64_div_u64.c b/lib/math/test_mul_u64_u64_div_u64.c
index a25640d349..58d058de4e 100644
--- a/lib/math/test_mul_u64_u64_div_u64.c
+++ b/lib/math/test_mul_u64_u64_div_u64.c
@@ -23,6 +23,7 @@ static test_params test_values[] = {
 {        0x1ffffffff,        0x1ffffffff,                0x4, 0xffffffff00000000 },
 { 0xffff000000000000, 0xffff000000000000, 0xffff000000000001, 0xfffeffffffffffff },
 { 0x3333333333333333, 0x3333333333333333, 0x5555555555555555, 0x1eb851eb851eb851 },
+{ 0x7fffffffffffffff,                0x2,                0x3, 0x5555555555555554 },
 { 0xffffffffffffffff,                0x2, 0x8000000000000000,                0x3 },
 { 0xffffffffffffffff,                0x2, 0xc000000000000000,                0x2 },
 { 0xffffffffffffffff, 0x4000000000000004, 0x8000000000000000, 0x8000000000000007 },

Hello Nicolas,

On Fri, Jul 12, 2024 at 01:41:46PM -0400, Nicolas Pitre wrote:
> From: Nicolas Pitre <npitre@baylibre.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@baylibre.com>
> Reported-by: kernel test robot <oliver.sang@intel.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@baylibre.com>

Best regards
Uwe

On Sat, 13 Jul 2024, Uwe Kleine-König wrote:

> Hello Nicolas,
> 
> On Fri, Jul 12, 2024 at 01:41:46PM -0400, Nicolas Pitre wrote:
> > From: Nicolas Pitre <npitre@baylibre.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@baylibre.com>
> > Reported-by: kernel test robot <oliver.sang@intel.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.> 

Yes, I tested it, and inspected assembly output of both gcc and clang.

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

Well... admitedly my version comes from how I think the compiler would 
generate the assembly. Given that a conditional is unavoidable, better 
skip the useless shift by 0 as well.

Admitedly I try to be reasonable and not go on a whim rewriting it all 
in assembly like I did in the past:
https://github.com/gcc-mirror/gcc/blob/master/libgcc/config/arm/ieee754-df.S

> With or without these suggestions incorporated:
> 
> Reviewed-by: Uwe Kleine-König <u.kleine-koenig@baylibre.com>
> 
> Best regards
> Uwe
>