[next,v4,1/5] minmax: Add umin(a, b) and umax(a, b)

  These can be used when min()/max() errors a signed v unsigned
compare when the signed value is known to be non-negative.

Unlike min_t(some_unsigned_type, a, b) umin() will never
mask off high bits if an inappropriate type is selected.

The '+ 0u + 0ul + 0ull' may look strange.
The '+ 0u' is needed for 'signed int' on 64bit systems.
The '+ 0ul' is needed for 'signed long' on 32bit systems.
The '+ 0ull' is needed for 'signed long long'.

Signed-off-by: David Laight <david.laight@aculab.com>
--
v4: Rename (from min_unsigned) to shorten code lines.
    Suggested by Linus.
v3: No change.
v2: Updated commit message.
---
 include/linux/minmax.h | 17 +++++++++++++++++
 1 file changed, 17 insertions(+)
  

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.

regards,
dan carpenter
  

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.
If the type is __int128 (signed or unsigned) then nothing happens.
(which means you can still get a signed v unsigned error.)
You could add in (__uint128)0 on 64bit systems that support it,
but it is so uncommon it really isn't worth the hassle.

Unlike any kind of cast the arithmetic cannot discard high bits.
I've found a few min_t() with dubious types.
One was a real bug found by someone else at much the same time.

	David

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

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.

regards,
dan carpenter







> If the type is __int128 (signed or unsigned) then nothing happens.
> (which means you can still get a signed v unsigned error.)
> You could add in (__uint128)0 on 64bit systems that support it,
> but it is so uncommon it really isn't worth the hassle.
> 
> Unlike any kind of cast the arithmetic cannot discard high bits.
> I've found a few min_t() with dubious types.
> One was a real bug found by someone else at much the same time.
> 
> 	David
> 
> -
> Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
> Registration No: 1397386 (Wales)
  

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)
  

On Fri, Jan 12, 2024 at 02:26:33PM +0000, David Laight wrote:
> 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.

I'm so confused by this.  To me the big selling point of min_t() was
that it clamps things to between zero and the max.

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

I wasn't saying jump straight to ull.  I was suggesting jump to ul then
ull, but skip uint.  On a 32bit system, you can't allocate ULONG_MAX
bytes, so it still ends up being quite a safe number.

regards,
dan carpenter