The min() (etc) functions in minmax.h require that the arguments have
exactly the same types. This was probably added after an 'accident'
where a negative value got converted to a large unsigned value.

However when the type check fails, rather than look at the types and
fix the type of a variable/constant, everyone seems to jump on min_t().
In reality min_t() ought to be rare - when something unusual is being
done, not normality.

A quick grep shows 5734 min() and 4597 min_t().
Having the casts on almost half of the calls shows that something
is clearly wrong.

If the wrong type is picked (and it is far too easy to pick the type
of the result instead of the larger input) then significant bits can
get discarded.
Pretty much the worst example is in the derfved clamp_val(), consider:
        unsigned char x = 200u;
        y = clamp_val(x, 10u, 300u);

I also suspect that many of the min_t(u16, ...) are actually wrong.
For example copy_data() in printk_ringbuffer.c contains:
        data_size = min_t(u16, buf_size, len);
Here buf_size is 'unsigned int' and len 'u16', pass a 64k buffer
(can you prove that doesn't happen?) and no data is returned.

The only reason that most of the min_t() are 'fine' is that pretty
much all the values in the kernel are between 0 and INT_MAX.

Patch 1 adds min_unsigned(), this uses integer promotions to convert
both arguments to 'unsigned long long'. It can be used to compare a
signed type that is known to contain a non-negative value with an
unsigned type. The compiler typically optimises it all away.
Added first so that it can be referred to in patch 2.

Patch 2 replaces the 'same type' check with a 'same signedness' one.
This makes min(unsigned_int_var, sizeof()) be ok.
The error message is also improved and will contain the expanded
form of both arguments (useful for seeing how constants are defined).

Patch 3 just fixes some whitespace.

Patch 4 allows comparisons of 'unsigned char' and 'unsigned short'
to signed types. The integer promotion rules convert them both
to 'signed int' prior to the comparison so they can never cause
a negative value be converted to a large positive one.

Patch 5 is slightly more contentious (Linus may not like it!)
effectively adds an (int) cast to all constants between 0 and MAX_INT.
This makes min(signed_int_var, sizeof()) be ok.

With all the patches applied pretty much all the min_t() could be
replaced by min(), and most of the rest by min_unsigned().
However they all need careful inspection due to code like:
        sz = min_t(unsigned char, sz - 1, LIM - 1) + 1;
which converts 0 to LIM.

v3 Fix more issues found by the build robot
v2 Fixes some issues found by the kernel build robot.
No functional changes.

David Laight (5):
  minmax: Add min_unsigned(a, b) and max_unsigned(a, b)
  minmax: Allow min()/max()/clamp() if the arguments have the same
    signedness.
  Fix indentation of __cmp_once() and __clamp_once()
  Allow comparisons of 'int' against 'unsigned char/short'.
  Relax check to allow comparison between int and small unsigned
    constants.

 include/linux/minmax.h | 103 +++++++++++++++++++++++++++--------------
 1 file changed, 68 insertions(+), 35 deletions(-)

-- 
2.17.1

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

On Fri, Aug 04, 2023 at 10:50:59AM +0000, David Laight wrote:
> [...]
> I also suspect that many of the min_t(u16, ...) are actually wrong.
> For example copy_data() in printk_ringbuffer.c contains:
>         data_size = min_t(u16, buf_size, len);
> Here buf_size is 'unsigned int' and len 'u16', pass a 64k buffer
> (can you prove that doesn't happen?) and no data is returned.

Stars aligning... this exact bug (as you saw in the other thread[1]) got
hit. And in the analysis, I came to the same conclusion: min_t() is a
serious foot-gun, and we should be able to make min() Just Work in the
most common situations.

It seems like the existing type_max/type_min macros could be used to
figure out that the args are safe to appropriately automatically cast,
etc. e.g. type_max(u16) <= type_max(unsigned int) && type_min(u16) >=
type_min(unsigned int) ...

-Kees

[1] https://lore.kernel.org/all/20230811054528.never.165-kees@kernel.org/

-- 
Kees Cook

From: Kees Cook
> Sent: 14 August 2023 22:21
> 
> On Fri, Aug 04, 2023 at 10:50:59AM +0000, David Laight wrote:
> > [...]
> > I also suspect that many of the min_t(u16, ...) are actually wrong.
> > For example copy_data() in printk_ringbuffer.c contains:
> >         data_size = min_t(u16, buf_size, len);
> > Here buf_size is 'unsigned int' and len 'u16', pass a 64k buffer
> > (can you prove that doesn't happen?) and no data is returned.
> 
> Stars aligning... this exact bug (as you saw in the other thread[1]) got
> hit. And in the analysis, I came to the same conclusion: min_t() is a
> serious foot-gun, and we should be able to make min() Just Work in the
> most common situations.

It is all a question of what 'work' means.
To my mind (but Linus disagrees!) the only problematic case
is where a negative signed value gets converted to a large
unsigned value.
This snippet from do_tcp_getsockopt() shows what I mean:

	copy_from_user(&len,...)
	len = min_t(unsigned int, len, sizeof(int));

	if (len < 0)
		return -EINVAL;

That can clearly never return -EINVAL.
That has actually been broken since the test was added in 2.4.4.
That predates min_t() in 2.4.10 (renamed from min() in 2.4.9
when the 'strict typecheck' version on min() was added).
So min_t() actually predates min()!

> It seems like the existing type_max/type_min macros could be used to
> figure out that the args are safe to appropriately automatically cast,
> etc. e.g. type_max(u16) <= type_max(unsigned int) && type_min(u16) >=
> type_min(unsigned int) ...

That doesn't really help; min(a,b) is ok if any of:
1) is_signed(a) == is_signed(b).
2) is_signed(a + 0) == is_signed(b + 0)  // Converts char/short to int.
3) a or b is a constant between 0 and MAXINT and is cast to int.

The one you found passes (1) - both types are unsigned.
min(len, sizeof (int)) passes (3) and is converted to
min(len, (int)sizeof (int)) and can still return the expected negatives.

(Clearly that getsockopt code only works for len != 4 on LE.)

	David

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

On Tue, Aug 15, 2023 at 08:55:55AM +0000, David Laight wrote:
> From: Kees Cook
> > Sent: 14 August 2023 22:21
> > 
> > On Fri, Aug 04, 2023 at 10:50:59AM +0000, David Laight wrote:
> > > [...]
> > > I also suspect that many of the min_t(u16, ...) are actually wrong.
> > > For example copy_data() in printk_ringbuffer.c contains:
> > >         data_size = min_t(u16, buf_size, len);
> > > Here buf_size is 'unsigned int' and len 'u16', pass a 64k buffer
> > > (can you prove that doesn't happen?) and no data is returned.
> > 
> > Stars aligning... this exact bug (as you saw in the other thread[1]) got
> > hit. And in the analysis, I came to the same conclusion: min_t() is a
> > serious foot-gun, and we should be able to make min() Just Work in the
> > most common situations.
> 
> It is all a question of what 'work' means.
> To my mind (but Linus disagrees!) the only problematic case
> is where a negative signed value gets converted to a large
> unsigned value.
> This snippet from do_tcp_getsockopt() shows what I mean:
> 
> 	copy_from_user(&len,...)
> 	len = min_t(unsigned int, len, sizeof(int));
> 
> 	if (len < 0)
> 		return -EINVAL;
> 
> That can clearly never return -EINVAL.
> That has actually been broken since the test was added in 2.4.4.
> That predates min_t() in 2.4.10 (renamed from min() in 2.4.9
> when the 'strict typecheck' version on min() was added).
> So min_t() actually predates min()!
> 
> > It seems like the existing type_max/type_min macros could be used to
> > figure out that the args are safe to appropriately automatically cast,
> > etc. e.g. type_max(u16) <= type_max(unsigned int) && type_min(u16) >=
> > type_min(unsigned int) ...
> 
> That doesn't really help; min(a,b) is ok if any of:
> 1) is_signed(a) == is_signed(b).
> 2) is_signed(a + 0) == is_signed(b + 0)  // Converts char/short to int.
> 3) a or b is a constant between 0 and MAXINT and is cast to int.
> 
> The one you found passes (1) - both types are unsigned.
> min(len, sizeof (int)) passes (3) and is converted to
> min(len, (int)sizeof (int)) and can still return the expected negatives.

It seems like the foot-gun problems are when a value gets clamped by the
imposed type. Can't we just warn about those cases?

For example:

	int a = ...;
	unsigned int b = ...;
	int c = min_t(unsigned int, a, b);

This is goes bad when "a < 0". And it violates your case (1) above.

But this is also unsafe:

	unsigned int a = ...;
        u16 b = ...;
	unsigned int c = min_t(u16, a, b);

Both are unsigned, but "a > U16_MAX" still goes sideways.

I worry that weakening the min/max() type checking gets into silent errors:

	unsigned int a = ...;
        u16 b = ...;
	u16 c = max(a, b);

when "a > U16_MAX".

Looking at warning about clamped types on min_t(), though I see tons of
int vs unsigned int issue. (e.g. dealing with PAGE_SIZE vs an int).

-Kees

-- 
Kees Cook

From: Kees Cook <keescook@chromium.org>
> Sent: Monday, August 21, 2023 7:24 PM
....
> > > It seems like the existing type_max/type_min macros could be used to
> > > figure out that the args are safe to appropriately automatically cast,
> > > etc. e.g. type_max(u16) <= type_max(unsigned int) && type_min(u16) >=
> > > type_min(unsigned int) ...
> >
> > That doesn't really help; min(a,b) is ok if any of:
> > 1) is_signed(a) == is_signed(b).
> > 2) is_signed(a + 0) == is_signed(b + 0)  // Converts char/short to int.
> > 3) a or b is a constant between 0 and MAXINT and is cast to int.
> >
> > The one you found passes (1) - both types are unsigned.
> > min(len, sizeof (int)) passes (3) and is converted to
> > min(len, (int)sizeof (int)) and can still return the expected negatives.
> 
> It seems like the foot-gun problems are when a value gets clamped by the
> imposed type. Can't we just warn about those cases?

Also when -1 gets converted to 0xffffffff.

...
> But this is also unsafe:
> 
> 	unsigned int a = ...;
>         u16 b = ...;
> 	unsigned int c = min_t(u16, a, b);
> 
> Both are unsigned, but "a > U16_MAX" still goes sideways.

Right, this is one reason why min_t() is broken.
If min() allowed that - no reason why it shouldn't - then it wouldn't
get written in the first place.

> I worry that weakening the min/max() type checking gets into silent errors:
> 
> 	unsigned int a = ...;
>         u16 b = ...;
> 	u16 c = max(a, b);
> 
> when "a > U16_MAX".

Nothing can be done on the RHS to detect invalid narrowing in assignments.
And you don't want the compiler to complain because that will just cause
explicit casts be added making the code harder to read and (probably)
adding more bugs.

> Looking at warning about clamped types on min_t(), though I see tons of
> int vs unsigned int issue. (e.g. dealing with PAGE_SIZE vs an int).

Linus doesn't like me silently converting unsigned constants
to signed.

	David

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

On Wed, 23 Aug 2023 at 01:52, David Laight <David.Laight@aculab.com> wrote:
>
> Linus doesn't like me silently converting unsigned constants
> to signed.

Note that my dislike is more about changing the sign of the
*comparison*, and not warning about it.

It's not the constant conversion itself that ends up being the
problem, but the downstream issues it causes.

Having grepped for those annoying "min_t(size_t..)" uses, lots of them
seem to have perfectly fine signedness, and the 'size_t' is literally
just due to different sizes of unsigned values. In fact, several of
them seem to be due to the unfortunate fact that 'size_t' can be
'unsigned int' on 32-bit architectures, so mixing 'size_t' and
'unsigned long' will sadly warn without it.

So we literally have the issue that 'min(a,b)' will warn even if 'a'
and 'b' have the same signedness *and* the same size, because 'size_t'
and 'unsigned long' are different types.

Your patch 2/5 will fix that. And then I'd certainly be ok with a
"comparing an unsigned value to a signed positive constant" thing
(just not the other way around: "comparing a signed value to an
unsigned positive constant" is wrong)

That might get rid of a number of the more annoying cases.

            Linus

From: Linus Torvalds
> Sent: Wednesday, August 23, 2023 4:32 PM
...
> That might get rid of a number of the more annoying cases.

The one it leaves is code like:

	int length = get_length(...);
	if (length <= 0)
		return error:
	do {
		frag_len = some_min_function(length, PAGE_SIZE);
		...
	} while ((length -= frag_len) != 0);

As written it is ok for all reasonable some_min_function().

But if the (length <= 0) test is missing it really doesn't
matter what some_min_function() returns because the code
isn't going to do anything sensible - and may just loop.

About the only thing you could do is add a run-time check
and then BUG() if negative.
But that is horrid...

	David

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

On Mon, 21 Aug 2023 at 11:24, Kees Cook <keescook@chromium.org> wrote:
>
> It seems like the foot-gun problems are when a value gets clamped by the
> imposed type. Can't we just warn about those cases?

I think that the problem with min_t() is that it is used as a random
"when min() warns about different types", and that it basically just
adds a cast without any semantic meaning.

End result: we currently have 4500+ of those cases (and another 1300
uses of 'max_t') and I bet that several of them are the narrowing
kind. And some are probably valid.

And if we tighten up "min_t()" type rules, we'll just hit the *next*
problem in the series, namely "what are people going to do now?"

We don't want to just keep pushing the problem down.

So I actually mostly liked all the *other* patches in David's series:
using 'min_unsigned()' and friends adds a nice *semantic* layer, not
just a cast. And relaxing the checking of min/max doesn't cause the
same the "push problems down" issue, as long as the relaxing is
reasonable.

(Side note: I'm not convinced 'min_unsigned()' is the right syntax.
While I like the concept, I think 'min()' is often used as a part of
other expressions, and 'min_unsigned()' ends up making for a very
illegible long and complex thing. I think we might as well use
'umin()/umax()', matching our type system).

It's just that I very much don't think it's reasonable to relax "20u"
(or - more commonly - sizeof) to be any random constant signed
integer, and it should *not* compare well with signed integers and not
silently become a signed compare.

(But I do think that it's very ok to go the other way: compare a
_unsigned_ value with a "signed" constant integer like 20. The two
cases are not symmetrical: '20' can be a perfectly fine unsigned
value, but '20u' cannot be treated signed).

And while I don't like David's patch to silently turn unsigned
constant signed, I do acknowledge that very often the *source* of the
unsignedness is a 'sizeof()' expression, and then you have an integer
that gets compared to a size, and you end up using 'min_t()'. But I do
*NOT* want to fix those cases by ignoring the signedness.

Just a quick grep of

    git grep 'min_t(size_t' | wc

shows that quite a lot of the 'min_t()' cases are this exact issue.
But I absolutely do *not* think the solution is to relax 'min()'.

I suspect the fix to those cases is to much more eagerly use
'clamp()'. Almost every single time you do a "compare to a size", it
really is "make sure the integer is within the size range". So while

    int val
   ...
    x = min(val,sizeof(xyz));

is horrendously wrong and *should* warn, I think doing

   x = clamp(val, 0, sizeof(xyz));

is a *much* nicer model, and should not warn even if "val" and the
upper bound do not agree. In the above kind of situation, suddenly it
*is* ok to treat the 'sizeof()' as a signed integer, but only because
we have that explicit lower bound too.

In other words: we should not "try to fix the types". That was what
caused the problem in the first place, with "min_t()" just trying to
fix the type mismatch with a cast. Casts are wrong, and we should have
known that. The end result is horrendous, and I do agree with David on
that too.

I think we should strive to fix it with "semantic" fixes instead. Like
the above "use clamp() instead of min(), and the fundamental
signedness problem simply goes away because it has enough semantic
meaning to be well-defined".

Hmm?

                  Linus

From: Linus Torvalds
> Sent: Tuesday, August 22, 2023 6:36 PM
> 
> On Mon, 21 Aug 2023 at 11:24, Kees Cook <keescook@chromium.org> wrote:
> >
> > It seems like the foot-gun problems are when a value gets clamped by the
> > imposed type. Can't we just warn about those cases?
> 
> I think that the problem with min_t() is that it is used as a random
> "when min() warns about different types", and that it basically just
> adds a cast without any semantic meaning.
> 
> End result: we currently have 4500+ of those cases (and another 1300
> uses of 'max_t') and I bet that several of them are the narrowing
> kind. And some are probably valid.
> 
> And if we tighten up "min_t()" type rules, we'll just hit the *next*
> problem in the series, namely "what are people going to do now?"
> 
> We don't want to just keep pushing the problem down.
> 
> So I actually mostly liked all the *other* patches in David's series:
> using 'min_unsigned()' and friends adds a nice *semantic* layer, not
> just a cast. And relaxing the checking of min/max doesn't cause the
> same the "push problems down" issue, as long as the relaxing is
> reasonable.
> 
> (Side note: I'm not convinced 'min_unsigned()' is the right syntax.
> While I like the concept, I think 'min()' is often used as a part of
> other expressions, and 'min_unsigned()' ends up making for a very
> illegible long and complex thing. I think we might as well use
> 'umin()/umax()', matching our type system).

Picking a name is like painting the bike-shed :-)

> It's just that I very much don't think it's reasonable to relax "20u"
> (or - more commonly - sizeof) to be any random constant signed
> integer, and it should *not* compare well with signed integers and not
> silently become a signed compare.
> 
> (But I do think that it's very ok to go the other way: compare a
> _unsigned_ value with a "signed" constant integer like 20. The two
> cases are not symmetrical: '20' can be a perfectly fine unsigned
> value, but '20u' cannot be treated signed).

I'll rebase the patch after the next -rc1 is out with that removed. 

> And while I don't like David's patch to silently turn unsigned
> constant signed, I do acknowledge that very often the *source* of the
> unsignedness is a 'sizeof()' expression, and then you have an integer
> that gets compared to a size, and you end up using 'min_t()'. But I do
> *NOT* want to fix those cases by ignoring the signedness.
> 
> Just a quick grep of
> 
>     git grep 'min_t(size_t' | wc
> 
> shows that quite a lot of the 'min_t()' cases are this exact issue.
> But I absolutely do *not* think the solution is to relax 'min()'.

size_t is actually a problem with unsigned constants.
It is 'unsigned int' on 32bit and 'unsigned long' on 64bit.
Making it hard to use a literal.

> I suspect the fix to those cases is to much more eagerly use
> 'clamp()'. Almost every single time you do a "compare to a size", it
> really is "make sure the integer is within the size range". So while
> 
>     int val
>    ...
>     x = min(val,sizeof(xyz));
> 
> is horrendously wrong and *should* warn,

The difficulty is getting people to correct it by changing
the type on 'val' to be unsigned.
Sometimes it is just a local variable.
Often it just can't ever be negative, or there is an immediately
preceding check.

Indeed if it is negative that is probably a bug.
(eg a missing error check from an earlier call.)
No amount of compile-time checking is going to help.
About the only thing that would help would be a run-time
check and a 'goto label' if negative.

There are plenty of places where a (short) buffer length is
passed to a function as 'int' - even though negative values
are completely invalid.
In reality the type change needs 'chasing back' through to
all the callers.

> I think doing
> 
>    x = clamp(val, 0, sizeof(xyz));
> 
> is a *much* nicer model, and should not warn even if "val" and the
> upper bound do not agree. In the above kind of situation, suddenly it
> *is* ok to treat the 'sizeof()' as a signed integer, but only because
> we have that explicit lower bound too.

That would require major rework on clamp() :-)

It would also be nice to get clamp(unsigned_var, 0u, 20u) to
compile without the annoying warning from the compiler.
I think you have to use:
	builtin_choose_expr(x, var, 0) >= builtin_choose_expr(x, low, 0)

> In other words: we should not "try to fix the types". That was what
> caused the problem in the first place, with "min_t()" just trying to
> fix the type mismatch with a cast. Casts are wrong, and we should have
> known that. The end result is horrendous, and I do agree with David on
> that too.

Some of the worst casts are the ones that are only there for sparse.
The compiler sees '(force __be32)var' as '(uint)var' rather than 'var'.
That really ought to always have been 'force(__be32, var)' so that
it can be made transparent to the compiler.

> I think we should strive to fix it with "semantic" fixes instead. Like
> the above "use clamp() instead of min(), and the fundamental
> signedness problem simply goes away because it has enough semantic
> meaning to be well-defined".

Unfortunately it adds an extra compare and branch to get mis-predicted.

	David

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