linux-kernel - RE: [PATCH next v4 1/5] minmax: Add umin(a, b) and umax(a, b)

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 for Android: free password hash cracker in your pocket

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

Message-ID: <d05f91a308174cf0b3e5707625a212bc@AcuMS.aculab.com>
Date: Fri, 12 Jan 2024 14:26:33 +0000
From: David Laight <David.Laight@...LAB.COM>
To: 'Dan Carpenter' <dan.carpenter@...aro.org>
CC: "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>, "Linus
 Torvalds" <torvalds@...ux-foundation.org>, 'Andy Shevchenko'
	<andriy.shevchenko@...ux.intel.com>, 'Andrew Morton'
	<akpm@...ux-foundation.org>, "'Matthew Wilcox (Oracle)'"
	<willy@...radead.org>, 'Christoph Hellwig' <hch@...radead.org>, "'Jason A.
 Donenfeld'" <Jason@...c4.com>
Subject: RE: [PATCH next v4 1/5] minmax: Add umin(a, b) and umax(a, b)

From: Dan Carpenter
> Sent: 12 January 2024 14:03
> 
> On Fri, Jan 12, 2024 at 01:40:30PM +0000, David Laight wrote:
> > From: Dan Carpenter
> > > Sent: 12 January 2024 12:50
> > >
> > > On Mon, Sep 18, 2023 at 08:16:30AM +0000, David Laight wrote:
> > > > +/**
> > > > + * umin - return minimum of two non-negative values
> > > > + *   Signed types are zero extended to match a larger unsigned type.
> > > > + * @x: first value
> > > > + * @y: second value
> > > > + */
> > > > +#define umin(x, y)	\
> > > > +	__careful_cmp((x) + 0u + 0ul + 0ull, (y) + 0u + 0ul + 0ull, <)
> > >
> > > Why do we match "a larger unsigned type" instead of ULL_MAX?  Presumably
> > > it helps performance somehow...  I agree that it's probably fine but I
> > > would be more comfortable if it skipped UINT_MAX and jumped directly to
> > > ULONG_MAX.  These days 4 gigs is small potatoes.  The vmalloc() function
> > > can allocate 4G so we've had integer overflow bugs with this before.
> >
> > The '+ 0ul*' carefully zero extend signed values without changing
> > unsigned values.
> > The compiler detects when it has zero-extended both sides and
> > uses the smaller compare.
> > In essence:
> > 	x + 0u converts 'int' to 'unsigned int'.
> > 		Avoids the sign extension adding 0ul on 64bit.
> > 	x + 0ul converts a 'long' to 'unsigned long'.
> > 		Avoids the sign extension adding 0ull on 32bit
> > 	x + 0ull converts a 'long long' to 'unsigned long long'.
> > You need all three to avoid sign extensions and get an unsigned
> > compare.
> 
> So unsigned int compares are faster than unsigned long compares?
> 
> It's just sort of weird how it works.
> 
> 	min_t(unsigned long, -1, 10000000000)); => 10000000000
> 	umin(umin(-1, 10000000000)); => UINT_MAX
> 
> UINT_MAX is just kind of a random value.  I would have prefered
> ULONG_MAX, it's equally random but it's more safe because nothing can
> allocate ULONG_MAX bytes.

umin() is only defined for non-negative values.
So that example is really outside the domain of the function.

Consider:
	int x = some_positive_value;
	unsigned long long y;
then:
	min_t(unsigned long long, x, y);
	Does (unsigned long long)x which is (unsigned long long)(long long)x
	and requires that x be sign extended to 64bits.
	On 32bit that is quite horrid.
whereas:
	umin(x, y);
	Only has to zero extend x.
	So is compiled as:
		y:hi || y:lo > x ? x ; y

If both values are 32bit the compiler generates a 32bit compare
(even on 64bit).

	David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)