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] [day] [month] [year] [list]

Message-ID: <950n497s-1933-5s8q-2138-52oq50npr4s4@syhkavp.arg>
Date: Sat, 13 Jul 2024 21:49:15 -0400 (EDT)
From: Nicolas Pitre <nico@...xnic.net>
To: Uwe Kleine-König <u.kleine-koenig@...libre.com>
cc: Andrew Morton <akpm@...ux-foundation.org>, linux-kernel@...r.kernel.org
Subject: Re: [PATCH] mul_u64_u64_div_u64: avoid undefined shift value

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@...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.> 

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@...libre.com>
> 
> Best regards
> Uwe
>