[IDEA+RFC] Possible solution for min()/max() war

[IDEA+RFC] Possible solution for min()/max() war

[Brad Chapman]

Everyone,

	At the risk of igniting another long-drawn-out flamewar over the
min()/max() macros, I have an idea.

	There is a section in the config dialogs labeled "Kernel hacking."
Under it there is the SysRQ option. Why don't we put an entry under that
dialog and label it "Use new min()/max() macros" and make it a y/n field.
Then we can add dozens of warnings to the help dialog about it, and allow
the user/hacker to select the macro they want.

	In any code which uses the macros, you can simply do this:

#include <linux/config.h>
....
#ifdef CONFIG_USE_NEW_MINMAX
	minimum = min(int, number[0], number[1]);
#else
	minimum = min(number[0], number[1]);
#endif

	This way, some hackers can use the two-arg min()/max() inside an #ifdef block,
other hackers can use the three-arg min()/max() inside an #ifdef block, 
and people who don't care can select either.

	Comments, flames, suggestions, anyone? If the output is good, I'll
publish a patch which will add the Config.in option and default it to
CONFIG_USE_NEW_MINMAX=y, since that was the decree of the Great Penguin Overlord ;)

Brad

=====
Brad Chapman

Permanent e-mail: kakadu_croc@yahoo.com
Current e-mail: kakadu@adelphia.net
Alternate e-mail: kakadu@netscape.net

__________________________________________________
Do You Yahoo!?
Make international calls for as low as $.04/minute with Yahoo! Messenger
http://phonecard.yahoo.com/

Re: [IDEA+RFC] Possible solution for min()/max() war

[Ben LaHaise]

On Fri, 24 Aug 2001, Brad Chapman wrote:

> 	This way, some hackers can use the two-arg min()/max() inside an #ifdef block,
> other hackers can use the three-arg min()/max() inside an #ifdef block,
> and people who don't care can select either.

Have you no taste?  Use of #ifdef's should be minimised as much as
possible.  For this kind of construct, the spurious preprocessor usage
just makes me want to vomit.

		-ben

Re: [IDEA+RFC] Possible solution for min()/max() war

[Brad Chapman]

--- Ben LaHaise <bcrl@redhat.com> wrote:
> On Fri, 24 Aug 2001, Brad Chapman wrote:
> 
> > 	This way, some hackers can use the two-arg min()/max() inside an #ifdef block,
> > other hackers can use the three-arg min()/max() inside an #ifdef block,
> > and people who don't care can select either.
> 
> Have you no taste?  Use of #ifdef's should be minimised as much as
> possible.  For this kind of construct, the spurious preprocessor usage
> just makes me want to vomit.
> 
> 		-ben

Mr. LaHaise,

	Eeek! Sorry. That was just a preliminary. As I see it, there are
several ways to wire this up:

	- make everyone use the new macros (some people are thinking :P)

	- make everyone use #ifdef blocks with a config option (you think it's :P)

	- make min()/max() typeof() wrappers for a switch-style stack of comparison 
	  functions which work on the various types, i.e:
	
	  __u8 minimum = min(one, two) -> __u8 minimum = __u8_min(one, two)

	  (this may be too complex and is probably :P)

	- make min()/max() inline functions, cast things to void, and use memcmp()
	  (this might almost be reasonable, but is probably also :P)

	- stay with the old-style macros (:P, :P, :P)

	What do you think, sir?

Brad
	


=====
Brad Chapman

Permanent e-mail: kakadu_croc@yahoo.com
Current e-mail: kakadu@adelphia.net
Alternate e-mail: kakadu@netscape.net

__________________________________________________
Do You Yahoo!?
Make international calls for as low as $.04/minute with Yahoo! Messenger
http://phonecard.yahoo.com/

Re: [IDEA+RFC] Possible solution for min()/max() war

[Brad Chapman]

--- Ben LaHaise <bcrl@redhat.com> wrote:
> On Fri, 24 Aug 2001, Brad Chapman wrote:
> 
> > 	This way, some hackers can use the two-arg min()/max() inside an #ifdef block,
> > other hackers can use the three-arg min()/max() inside an #ifdef block,
> > and people who don't care can select either.
> 
> Have you no taste?  Use of #ifdef's should be minimised as much as
> possible.  For this kind of construct, the spurious preprocessor usage
> just makes me want to vomit.
> 
> 		-ben

Mr. LaHaise,

	Eeek! Sorry. That was just a preliminary. As I see it, there are
several ways to wire this up:

	- make everyone use the new macros (some people are thinking :P)

	- make everyone use #ifdef blocks with a config option (you think it's :P)

	- make min()/max() typeof() wrappers for a switch-style stack of comparison 
	  functions which work on the various types, i.e:
	
	  __u8 minimum = min(one, two) -> __u8 minimum = __u8_min(one, two)

	  (this may be too complex and is probably :P)

	- make min()/max() inline functions, cast things to void, and use memcmp()
	  (this sounds reasonable, but is probably also :P)

	- stay with the old-style macros (:P, :P, :P)

	What do you think, sir?

Brad
	


=====
Brad Chapman

Permanent e-mail: kakadu_croc@yahoo.com
Current e-mail: kakadu@adelphia.net
Alternate e-mail: kakadu@netscape.net

__________________________________________________
Do You Yahoo!?
Make international calls for as low as $.04/minute with Yahoo! Messenger
http://phonecard.yahoo.com/

Re: [IDEA+RFC] Possible solution for min()/max() war

[David S. Miller]

   From: Brad Chapman <kakadu_croc@yahoo.com>
   Date: Fri, 24 Aug 2001 16:59:27 -0700 (PDT)
   
   	- stay with the old-style macros (:P, :P, :P)

I've been trying to stay out of this until Linus returns
and has his word... but I can say with a level of certainty
that this won't sit well with Linus at all.

Later,
David S. Miller
davem@redhat.com

Re: [IDEA+RFC] Possible solution for min()/max() war

[Alexander Viro]

On Fri, 24 Aug 2001, Brad Chapman wrote:

> 	- make everyone use the new macros (some people are thinking :P)
> 
> 	- make everyone use #ifdef blocks with a config option (you think it's :P)
> 
> 	- make min()/max() typeof() wrappers for a switch-style stack of comparison 
> 	  functions which work on the various types, i.e:
> 	
> 	  __u8 minimum = min(one, two) -> __u8 minimum = __u8_min(one, two)
> 
> 	  (this may be too complex and is probably :P)

> 
> 	- make min()/max() inline functions, cast things to void, and use memcmp()
> 	  (this might almost be reasonable, but is probably also :P)
> 
> 	- stay with the old-style macros (:P, :P, :P)
> 
> 	What do you think, sir?

	Use different inline functions for signed and unsigned.
Explicitly.

	Any scheme trying to imitate polymorphism with use of cpp/
GNU extensions/whatever is missing the point.  There is _no_ common
operation to extend on several types.  Choice between signed and
unsigned max should be explicit - they are different operations.

	Trying to hide that is C++itis of the worst kind - false
polymorphism that hides only one thing: subtle bugs.

Re: [IDEA+RFC] Possible solution for min()/max() war

[Brad Chapman]

--- "David S. Miller" <davem@redhat.com> wrote:
>    From: Brad Chapman <kakadu_croc@yahoo.com>
>    Date: Fri, 24 Aug 2001 16:59:27 -0700 (PDT)
>    
>    	- stay with the old-style macros (:P, :P, :P)
> 
> I've been trying to stay out of this until Linus returns
> and has his word... but I can say with a level of certainty
> that this won't sit well with Linus at all.
> 
> Later,
> David S. Miller
> davem@redhat.com

Mr. Miller,

	Ack. When Linus returns, I'm sure he'll give us all very good reasons 
why he thought it needed to be changed.

	BTW, what is your opinion on the various ways I suggested to satisfy 
people over the min()/max() issue? Mr. LaHaise nearly threw up when I suggested 
using #ifdef, so we can safely scratch that one ;-). What do you think, sir?

Brad 


=====
Brad Chapman

Permanent e-mail: kakadu_croc@yahoo.com
Current e-mail: kakadu@adelphia.net
Alternate e-mail: kakadu@netscape.net

__________________________________________________
Do You Yahoo!?
Make international calls for as low as $.04/minute with Yahoo! Messenger
http://phonecard.yahoo.com/

Re: [IDEA+RFC] Possible solution for min()/max() war

[David S. Miller]

   From: Brad Chapman <kakadu_croc@yahoo.com>
   Date: Fri, 24 Aug 2001 17:18:44 -0700 (PDT)
   
   What do you think, sir?

Like I said, I'd like to defer to Linus until he has his word.
I should not have said anything at all... 

Later,
David S. Miller
davem@redhat.com

Re: [IDEA+RFC] Possible solution for min()/max() war

[Brad Chapman]

--- Alexander Viro <viro@math.psu.edu> wrote: 
> On Fri, 24 Aug 2001, Brad Chapman wrote:
> 
> > 	- make everyone use the new macros (some people are thinking :P)
> > 
> > 	- make everyone use #ifdef blocks with a config option (you think it's :P)
> > 
> > 	- make min()/max() typeof() wrappers for a switch-style stack of comparison 
> > 	  functions which work on the various types, i.e:
> > 	
> > 	  __u8 minimum = min(one, two) -> __u8 minimum = __u8_min(one, two)
> > 
> > 	  (this may be too complex and is probably :P) 
> > 
> > 	- make min()/max() inline functions, cast things to void, and use memcmp()
> > 	  (this might almost be reasonable, but is probably also :P)
> > 
> > 	- stay with the old-style macros (:P, :P, :P)
> > 
> > 	What do you think, sir?
> 
> 	Use different inline functions for signed and unsigned.
> Explicitly.

	OK. That sounds reasonable, but do we want to do another forced
change, or do we want to hide it? That seems to be the root of the problem:
keeping the same API but making it work _right_.

> 
> 	Any scheme trying to imitate polymorphism with use of cpp/
> GNU extensions/whatever is missing the point.  There is _no_ common
> operation to extend on several types.  Choice between signed and
> unsigned max should be explicit - they are different operations.

	Well, IIRC I remember someone saying that it was legal to compare
signed/unsigned ints, if you did it in the right order. IMHO that might be
incorrect. And none of the ideas I have suggested use any fancy cpp/GNU rubbish.
The most evil-sounding thing I suggested was #4.

> 
> 	Trying to hide that is C++itis of the worst kind - false
> polymorphism that hides only one thing: subtle bugs.
>

	Ack. (IMHO) I don't like C++ either :P

Brad 


=====
Brad Chapman

Permanent e-mail: kakadu_croc@yahoo.com
Current e-mail: kakadu@adelphia.net
Alternate e-mail: kakadu@netscape.net

__________________________________________________
Do You Yahoo!?
Make international calls for as low as $.04/minute with Yahoo! Messenger
http://phonecard.yahoo.com/

Re: [IDEA+RFC] Possible solution for min()/max() war

[Alexander Viro]

On Fri, 24 Aug 2001, Brad Chapman wrote:

> > > 
> > > 	What do you think, sir?
> > 
> > 	Use different inline functions for signed and unsigned.
> > Explicitly.
> 
> 	OK. That sounds reasonable, but do we want to do another forced
> change, or do we want to hide it? That seems to be the root of the problem:
> keeping the same API but making it work _right_.

Existing API is wrong.  "Hiding" is precisely what's wrong here - we
use the same name for two subtly different functions.

Re: [IDEA+RFC] Possible solution for min()/max() war

[Brad Chapman]

--- Alexander Viro <viro@math.psu.edu> wrote:
> On Fri, 24 Aug 2001, Brad Chapman wrote:
> > > > 	What do you think, sir?
> > > 
> > > 	Use different inline functions for signed and unsigned.
> > > Explicitly.
> > 
> > 	OK. That sounds reasonable, but do we want to do another forced
> > change, or do we want to hide it? That seems to be the root of the problem:
> > keeping the same API but making it work _right_.
> 
> Existing API is wrong.  "Hiding" is precisely what's wrong here - we
> use the same name for two subtly different functions.

Mr. Viro,

	OK. The existing API is wrong and the new min()/max() macros are the
right way to properly compare values. However, we could always add a config 
option to enable a compatibility macro, which would use typeof() on one of the 
two variables and then call the real min()/max(). Something like this (just an
example):

#ifdef CONFIG_ALLOW_COMPAT_MINMAX
#define proper_min(t, a, b)	((t)(a) < (t)(b) ? (a) : (b))
#define proper_max(t, a, b)	((t)(a) > (t)(b) ? (a) : (b))
#define min(a, b)		proper_min(typeof(a), a, b)
#define max(a, b)		proper_max(typeof(a), a, b)
#else
#define min(t, a, b)		((t)(a) < (t)(b) ? (a) : (b))
#define max(t, a, b)		((t)(a) < (t)(b) ? (a) : (b))
#endif

	Unfortunately, this would violate your idea that "hiding" the real
code behind compatibility stuff is C++esque, and, IYO, an Evil Thing(tm). That
just leaves me with one question to everybody: 	

	<rant type="question" intensity="30%">
	Why did Linus change this out of /dev/null and suddenly run off!?
	</rant>

Brad


=====
Brad Chapman

Permanent e-mail: kakadu_croc@yahoo.com
Current e-mail: kakadu@adelphia.net
Alternate e-mail: kakadu@netscape.net

__________________________________________________
Do You Yahoo!?
Make international calls for as low as $.04/minute with Yahoo! Messenger
http://phonecard.yahoo.com/

Re: [IDEA+RFC] Possible solution for min()/max() war

[Alexander Viro]

On Fri, 24 Aug 2001, Brad Chapman wrote:

> 	OK. The existing API is wrong and the new min()/max() macros are the
> right way to properly compare values. However, we could always add a config 
> option to enable a compatibility macro, which would use typeof() on one of the 
> two variables and then call the real min()/max(). Something like this (just an
> example):
> 
> #ifdef CONFIG_ALLOW_COMPAT_MINMAX
> #define proper_min(t, a, b)	((t)(a) < (t)(b) ? (a) : (b))
> #define proper_max(t, a, b)	((t)(a) > (t)(b) ? (a) : (b))
> #define min(a, b)		proper_min(typeof(a), a, b)
> #define max(a, b)		proper_max(typeof(a), a, b)

_THAT_ _IS_ _WRONG_.  Who the fuck said that we always want type of _first_
argument?  Mind you, IMNSHO Dave had been on a seriously bad trip when he
had added that "type" argument - separate names would be cleaner.  And yes,
it'd be better in prepatch instead of 2.4.9-final.

However, no matter which variant you pick, old code with min/max
was broken.  Unless you are carefully giving right types (preferanly -
with casts) it works only by accidents (if it works at all).

"Compatibility option" is exactly the worst thing in such cases.
It's either changing the whole codebase or not bothering at all.

Re: [IDEA+RFC] Possible solution for min()/max() war

[Brad Chapman]

--- Alexander Viro <viro@math.psu.edu> wrote:
> 
> 
> On Fri, 24 Aug 2001, Brad Chapman wrote:
> 
> > 	OK. The existing API is wrong and the new min()/max() macros are the
> > right way to properly compare values. However, we could always add a config 
> > option to enable a compatibility macro, which would use typeof() on one of the 
> > two variables and then call the real min()/max(). Something like this (just an
> > example):
> > 
> > #ifdef CONFIG_ALLOW_COMPAT_MINMAX
> > #define proper_min(t, a, b)	((t)(a) < (t)(b) ? (a) : (b))
> > #define proper_max(t, a, b)	((t)(a) > (t)(b) ? (a) : (b))
> > #define min(a, b)		proper_min(typeof(a), a, b)
> > #define max(a, b)		proper_max(typeof(a), a, b)
> 
> _THAT_ _IS_ _WRONG_.  Who the fuck said that we always want type of _first_
> argument?  Mind you, IMNSHO Dave had been on a seriously bad trip when he
> had added that "type" argument - separate names would be cleaner.  And yes,
> it'd be better in prepatch instead of 2.4.9-final.

	I never said we had to use the _first_ argument. We could always do
the _second_. Or we could scrap the whole idea of compatibility with any of the old,
"broken" type-unsafe code and make everybody use the new macros. Period.

> 
> However, no matter which variant you pick, old code with min/max
> was broken.  Unless you are carefully giving right types (preferanly -
> with casts) it works only by accidents (if it works at all).
> 
> "Compatibility option" is exactly the worst thing in such cases.
> It's either changing the whole codebase or not bothering at all.
>

	Ack. Seems like the best way to fix this is to either make everybody
use the new macros, or wait for Linus to show up ;-)

Brad 


=====
Brad Chapman

Permanent e-mail: kakadu_croc@yahoo.com
Current e-mail: kakadu@adelphia.net
Alternate e-mail: kakadu@netscape.net

__________________________________________________
Do You Yahoo!?
Make international calls for as low as $.04/minute with Yahoo! Messenger
http://phonecard.yahoo.com/

Re: [IDEA+RFC] Possible solution for min()/max() war

[Bill Pringlemeir]

>>>>> "Brad" == Brad Chapman <kakadu_croc@yahoo.com> writes:

 Brad> 	OK. The existing API is wrong and the new min()/max() macros
 Brad> are the right way to properly compare values. However, we could
 Brad> always add a config option to enable a compatibility macro,
 Brad> which would use typeof() on one of the two variables and then
 Brad> call the real min()/max(). Something like this (just an
 Brad> example):

       #ifdef CONFIG_ALLOW_COMPAT_MINMAX
       #define proper_min(t, a, b)	((t)(a) < (t)(b) ? (a) : (b))
       #define proper_max(t, a, b)	((t)(a) > (t)(b) ? (a) : (b))
       #define min(a, b)		proper_min(typeof(a), a, b)
       #define max(a, b)		proper_max(typeof(a), a, b)
       #else
       #define min(t, a, b)		((t)(a) < (t)(b) ? (a) : (b))
       #define max(t, a, b)		((t)(a) < (t)(b) ? (a) : (b))
       #endif

Conditionals are bad.  Casting is bad.  In my opinion the only
semantically correct version would be something like this,

#define min(x,y)                                       \
                                                       \
  ({typeof(x) _x = 0; typeof(y) _y = 0;                \
    if ((_x-1>0 && _y-1<0) || (_x-1<0 && _y-1>0)) {    \
         if((x) < 0 ||  (y) < 0)                       \
                exit(SIGNED_UNSIGNED_CONFLICT);        \
    }                                                  \
        _x = (x), _y = (y); (_x>_y)?_y:_x;             \
   }) 

I think that if you are mixing signed and unsigned you should have had
a check before hand to gaurentee that any casting away of the sign is
ok.  It is ok if the variable is in range, it is not if they are out
of range.  However, this incurs a runtime check which is not
appropriate for kernel level code.

As several other people have noted, the casting is bad from a
maintainability prospective.  This is slapping your best friend in the
face; the compiler.  Also, the three arg macro breaks compatibility
with a long standing `C' min/max macro convention.

Probably we should just shutup for now until Linus can clarify what it
is that he wants to achieve and avoid.  Since there is probably no way
to make a universally correct min/max macro in `C', you need to have
some sort of goal to achieve.

regards,
Bill Pringlemeir.

Re: [IDEA+RFC] Possible solution for min()/max() war

[Rusty Russell]

In message <Pine.GSO.4.21.0108242055410.19796-100000@weyl.math.psu.edu> you wri
te:
> _THAT_ _IS_ _WRONG_.  Who the fuck said that we always want type of _first_
> argument?  Mind you, IMNSHO Dave had been on a seriously bad trip when he
> had added that "type" argument - separate names would be cleaner.  And yes,
> it'd be better in prepatch instead of 2.4.9-final.

We're going in circles.  Linus requested that the explicit type arg be
added.

IIUC Dave's original patch (and I just want to say that Dave is my
hero for pushing this) looked vaguely like the existing code in
include/linux/netfilter.h.  He's mentioned it before but noone
bothered to read it, so I'll quote for you:

/* From arch/i386/kernel/smp.c:
 *
 *	Why isn't this somewhere standard ??
 *
 * Maybe because this procedure is horribly buggy, and does
 * not deserve to live.  Think about signedness issues for five
 * seconds to see why.		- Linus
 */

/* Two signed, return a signed. */
#define SMAX(a,b) ((ssize_t)(a)>(ssize_t)(b) ? (ssize_t)(a) : (ssize_t)(b))
#define SMIN(a,b) ((ssize_t)(a)<(ssize_t)(b) ? (ssize_t)(a) : (ssize_t)(b))

/* Two unsigned, return an unsigned. */
#define UMAX(a,b) ((size_t)(a)>(size_t)(b) ? (size_t)(a) : (size_t)(b))
#define UMIN(a,b) ((size_t)(a)<(size_t)(b) ? (size_t)(a) : (size_t)(b))

/* Two unsigned, return a signed. */
#define SUMAX(a,b) ((size_t)(a)>(size_t)(b) ? (ssize_t)(a) : (ssize_t)(b))
#define SUMIN(a,b) ((size_t)(a)<(size_t)(b) ? (ssize_t)(a) : (ssize_t)(b))

Cheers,
Rusty.
--
Premature optmztion is rt of all evl. --DK

Re: [IDEA+RFC] Possible solution for min()/max() war

[Linus Torvalds]

In article <E15b9rU-0002vE-00@localhost>,
Rusty Russell  <rusty@rustcorp.com.au> wrote:
>In message <Pine.GSO.4.21.0108242055410.19796-100000@weyl.math.psu.edu> you wri
>te:
>> _THAT_ _IS_ _WRONG_.  Who the fuck said that we always want type of _first_
>> argument?  Mind you, IMNSHO Dave had been on a seriously bad trip when he
>> had added that "type" argument - separate names would be cleaner.  And yes,
>> it'd be better in prepatch instead of 2.4.9-final.
>
>We're going in circles.  Linus requested that the explicit type arg be
>added.

Yes. "requested" is a bit too politic.

It was not davem who added the type argument.  It was me who _required_
that min/max be very much explicitly type-aware, as I consider any other
alternative to be inherently buggy. 

Yes, the new Linux min/max macros are different from the ones people are
used to.  Yes, I expected a lot of flamage.  And no, I don't care one
whit.  Unlike EVERY SINGLE other C version of min/max I've ever seen,
the new Linux kernel versions at least have a fighting chance in hell of
generating correct code.  And that's to a large degree because they
force the user to specify what type he _thinks_ the comparison should be
done in. 

I know people don't understand about the difference between signed and
unsigned compares, and people may not even realize that just by doing
the patches David ended up fixing a few real bugs that were uncovered
simply by virtue of having to think about what kind of comparison it was
supposed to be. 

There were a few alternatives that we looked at (or rather, David
implemented, and I ended up rejecting due to various reasons), but they
all boiled down to "how do we sanely generate min/max functions while at
the same time forcing people to understand the types in question".  Some
of the intermediate patches had the type in the macro name, ie things
like "min_uint()" and "min_slong()".  The final version (ie the one in
2.4.9) was deemed to be the most flexible. 

The problem with putting the "type" in the name of the function/macro
is/was that

 - there's a _lot_ of types. David actually had a version for this, and
   there were separate versions for everything ranging from "int" to
   "uint", to "s32" to "u32", to "size_t" etc etc.

 - Some people would _still_ not understand what the advantage of
   explicit typing would be, so we'd have drivers doing their own
   min/max functions, not understanding the issues about signs and C
   type conversion. 

Thus the current "min(type,x,y)" approach, which fixes both problems.

I have one thing to say to people who do not like the new min/max
functions: most of them probably never even _understood_ the multitude
of bugs that are inherent in the classical

	#define min(x,y) ((x) < (y) ? (x) : (y))

but even so I'm somewhat surprised that this is still debated.  I hoped
it would be over by the time I came back ;)

		Linus

Re: [IDEA+RFC] Possible solution for min()/max() war

[Alexander Viro]

On Tue, 28 Aug 2001, Linus Torvalds wrote:

> It was not davem who added the type argument.  It was me who _required_
> that min/max be very much explicitly type-aware, as I consider any other
> alternative to be inherently buggy. 

Sure. Any attempt to keep the old min/max and make them automagically
do the right thing is doomed since there is no _single_ right thing
we want from them and choice should be deliberate and explicit. No
arguments here.

> generating correct code.  And that's to a large degree because they
> force the user to specify what type he _thinks_ the comparison should be
> done in. 

<nod>

> The problem with putting the "type" in the name of the function/macro
> is/was that
> 
>  - there's a _lot_ of types. David actually had a version for this, and
>    there were separate versions for everything ranging from "int" to
>    "uint", to "s32" to "u32", to "size_t" etc etc.

Ugh. I have a serious feeling that most of them would be redundant, but...
OK, I guess that somebody might want "unsigned max of x and y % 256" (x
being unsigned char and y - unsigned long).  Yes, with stuff like that
we'd really need a function for every type, but I would be very surprised
if somebody actually needed that (and I'd rather see it written explicitly,
regardless of the mechanism we use).

>  - Some people would _still_ not understand what the advantage of
>    explicit typing would be, so we'd have drivers doing their own
>    min/max functions, not understanding the issues about signs and C
>    type conversion. 

Well, that's what grep is for.  Bet that we'll see MAX, __max, m4x and
all sorts of similar "workarounds", so grep'n'LART will be needed anyway.

Re: [IDEA+RFC] Possible solution for min()/max() war

[Linus Torvalds]

On Tue, 28 Aug 2001, Alexander Viro wrote:
>
> > The problem with putting the "type" in the name of the function/macro
> > is/was that
> >
> >  - there's a _lot_ of types. David actually had a version for this, and
> >    there were separate versions for everything ranging from "int" to
> >    "uint", to "s32" to "u32", to "size_t" etc etc.
>
> Ugh. I have a serious feeling that most of them would be redundant, but...
> OK, I guess that somebody might want "unsigned max of x and y % 256" (x
> being unsigned char and y - unsigned long).

It doesn't matter if the two things are of a different type - there is
always just one type that the comparison is done in, anyway (and returning
any other type doesn't make any sense to me, at least).

And yes, they _are_ redundant in the sense that "size_t" is obviously the
same as "unsigned int" or "unsigned long" on just about all architectures:
but we obviously don't know that on a source level, so you do end up
needing various different versions.

You could, of course, just always do the type expansion, and really boil
it all down to just "large enough" types, the obvious ones being "unsigned
long" and "signed long". However, that implies either depending on a smart
compiler or accepting an extra type expansion in the resulting binary, and
it also wouldn't work on 64-bit quantities (which NTFS actually _does_
use, for example), so you'd still have to have at least

 - umin()/umax()/smin()/smax() - for "long" and shorter
 - u64min()/u64max()/s64min()s64max() - for "long long" and "u64/s64"

to make sure that the min/max operations do not truncate any bits. Even
so, I'd really want to make sure it gets truncated down too - I'd be
nervous about doing "umax()" on two "char" entities: it's MUCH more clear
what you get from

	x = max(unsigned char, char, char)

than if you have signed chars that are expanded to unsigned long's and
then compared (the compare gets the same result, but how is the final
result of "min()" then expanded, if at all?). It gets worse if one of the
sides is unsigned and the other signed, at which point the "extend to a
larger type" approach doesn't work at all.

In short, I really think you want to have the exact types. And a quick
grep of the 2.4.9 diff shows that at least for "min()" we have at least
the following types already being used: "int" "long" "s64" "u32" "unsigned
int" "unsigned long".

So that's at _least_ 6 different versions of "min()" if you want to make
them different functions.

Or, with the 2.4.9 approach, it's just a single macro (well, and another
one for "max()"). And when somebody needs a new type, he doesn't have to
worry about creating a new instantiation of the macro.

		Linus

Re: [IDEA+RFC] Possible solution for min()/max() war

[Alan Cox]

> Or, with the 2.4.9 approach, it's just a single macro (well, and another
> one for "max()"). And when somebody needs a new type, he doesn't have to
> worry about creating a new instantiation of the macro.

The unfortunate thing is that its min and max as opposed to typed_min and
typed_max (with min/max set up to error), since its now a nightmare to 
maintain compatibility between two allegedly stable releases of the same
kernel, as well as with 2.2

Had it been typed_min(a,b,c) then 2.2 could have stayed compatible and the
glue would have been simple

Re: [IDEA+RFC] Possible solution for min()/max() war

[Roman Zippel]

Hi,

Linus Torvalds wrote:

> I know people don't understand about the difference between signed and
> unsigned compares, and people may not even realize that just by doing
> the patches David ended up fixing a few real bugs that were uncovered
> simply by virtue of having to think about what kind of comparison it was
> supposed to be.

What's wrong with "-Wsign-compare"? You just fixed only a minor amount
of compares.

An explicit type is maintenance problem and cause of other subtle bugs.
When types are changing, the type in the macro is too easily missed and
can cause these funny "but it works on ia32..." errors.

What's wrong with this version?

#define min(a, b) ({            \
        typeof(a) _a = (a);     \
        typeof(b) _b = (b);     \
        _a < _b ? _a : _b;      \
})      

With "-Wsign-compare" the compiler will warn you about wrong usage and
will otherwise automatically do the right thing.

Explicit casts are not good, but such half hidden casts are worse. You
are hiding the problem instead of really fixing it. Why won't you let
the compiler help you?

bye, Roman

Re: [IDEA+RFC] Possible solution for min()/max() war

[Linus Torvalds]

On Tue, 28 Aug 2001, Roman Zippel wrote:
>
> Linus Torvalds wrote:
>
> > I know people don't understand about the difference between signed and
> > unsigned compares, and people may not even realize that just by doing
> > the patches David ended up fixing a few real bugs that were uncovered
> > simply by virtue of having to think about what kind of comparison it was
> > supposed to be.
>
> What's wrong with "-Wsign-compare"? You just fixed only a minor amount
> of compares.

-Wsign-compare is TOTALLY useless.

The problem with signed compares is not just comparing a signed entity
against a unsigned one. It's quite common to have signed quantities on
both sides, but _intending_ a unsigned comparison or vice versa.

This is simply an area where it's better to make people think about the
types, than to magically try to do the "right" thing.

> What's wrong with this version?

[ Standard stupid min() removed ]

You just fixed the "re-use arguments" bug - which is a bug, but doesn't
address the fact that most of the min/max bugs are due to the programmer
_indending_ a unsigned compare because he didn't even think about the
type.

		Linus

Re: [IDEA+RFC] Possible solution for min()/max() war

[Linus Torvalds]

On Tue, 28 Aug 2001, Alan Cox wrote:
>
> The unfortunate thing is that its min and max as opposed to typed_min and
> typed_max (with min/max set up to error), since its now a nightmare to
> maintain compatibility between two allegedly stable releases of the same
> kernel, as well as with 2.2

Note that 2.2.x does not HAVE a "min/max" function, so that cannot be an
issue.

Yes, some drivers and filesystems did their own private version, but if
they are maintained in both 2.2.x and 2.4.x, then it's obviously very easy
for them to change their private version to match the 2.4.x tree, so I
think this particular argument is rather bogus.

		Linus

Re: [IDEA+RFC] Possible solution for min()/max() war

[Roman Zippel]

Hi,

Linus Torvalds wrote:

> The problem with signed compares is not just comparing a signed entity
> against a unsigned one. It's quite common to have signed quantities on
> both sides, but _intending_ a unsigned comparison or vice versa.

Then it's a bug that should _not_ be fixed in the min macro. Unsigned
values should be hold in unsigned variables. If it's that common, please
show me a sane and realistic example.

> This is simply an area where it's better to make people think about the
> types, than to magically try to do the "right" thing.
> 
> > What's wrong with this version?
> 
> [ Standard stupid min() removed ]

It's not stupid, it does the right thing for the majority of the cases.
A cast just hides the problem. If you need a broken min macro to get
people thinking, you have a much bigger problem.

> You just fixed the "re-use arguments" bug - which is a bug, but doesn't
> address the fact that most of the min/max bugs are due to the programmer
> _indending_ a unsigned compare because he didn't even think about the
> type.

You maybe fixed a few bugs, but this new macro will only cause new
problems in the future. If we change only a single type, you have to
scan all min/max users if they possibly need to be changed too. Thanks
to the cast, the compiler won't even remotely help you finding them.

bye, Roman

Re: [IDEA+RFC] Possible solution for min()/max() war

[Linus Torvalds]

On Tue, 28 Aug 2001, Roman Zippel wrote:
>
> Linus Torvalds wrote:
>
> > The problem with signed compares is not just comparing a signed entity
> > against a unsigned one. It's quite common to have signed quantities on
> > both sides, but _intending_ a unsigned comparison or vice versa.
>
> Then it's a bug that should _not_ be fixed in the min macro. Unsigned
> values should be hold in unsigned variables. If it's that common, please
> show me a sane and realistic example.

I'll show you a real example from drivers/acorn/scsi/acornscsi.c:

	min(host->scsi.SCp.this_residual, DMAC_BUFFER_SIZE / 2);

this_residual is "int", and "DMAC_BUFFER_SIZE" is just a #define for
an integer constant. So the above is actually a signed comparison, and
I'll bet you that was not what the author intended.

Now, this_residual is hopefully never negative, so it doesn't matter.

But how many security bugs have you seen where people just didn't even
_think_ of the user giving invalid values?

Think of code like

	#define BUFFER_SIZE (10)

	char buf[BUFFER_SIZE];

	len = min(user_len, BUFFER_SIZE);
	if (copy_from_user(buf, user, len))
		return -EFAULT;

which is not all that broken. Sure, maybe you _should_ have marked
BUFFER_SIZE explicitly unsigned, but face it, how many people actually do
that?

So "BUFFER_SIZE" is actually a signed value (never mind that it is
obviously positive), and if "user_len" is signed too the above doesn't
actually do what the programmer obviously _meant_ to do.

Does code like the above happen? Sure it does. The input can be signed
because often the user interfaces are defined outside the kernel (think of
the arguments to "bind()" or "setsockopt()", and realize that "socklen_t"
is "int" - the programmer may not even SEE the signedness of the arguments
exactly because they are typedefs).

And did you realize, for example, that of the existing "min()"
implementations, some were inline functions that implicitly cast their
arguments to "int" (and one to "unsigned int")? This way we could also
maintain those kinds of local conventions - where the programmer had
originally (at least in the case of the unsigned int) on purpose made all
"min()" functions unsigned.

That, together with different pieces of code really wanting different
semantics. Let me quote something that got removed:

<include/net/sock.h>:

-static __inline__ int min(unsigned int a, unsigned int b)
-{
-       if (a > b)
-               a = b;
-       return a;
-}
-

<net/khttpd/prototypes.h>:

-/* the TCP/IP stack defines a __BROKEN__ set of min/max functions !! */
-/* So we better define our own.                                      */
-
-/* Broken means: working on unsigned data only, which is not acceptable
-                for kHTTPd and probably a lot of other functions. */
-
-#undef min
-#undef max
-#define min(a,b)  ( (a) < (b) ? (a) : (b) )
-#define max(a,b)  ( (a) > (b) ? (a) : (b) )

Now, just _imagine_ the set of bugs implicit in the fact that part of
networking wants "min()" to be unsigned, while another part (that _uses_
the code that depends on the unsigned "min()") re-defines min() to be
"whatever the arguments are".

Now isn't it better to have a nice macro that _can_ be used for all of
this, and that _does_ explicitly handle the issue of signedness that
different parts of the code has very different opinions on, and that
clearly encodes the assumptions that you have at the exact point of use?

		Linus

Re: [IDEA+RFC] Possible solution for min()/max() war

[Henning P. Schmiedehausen]

Linus Torvalds <torvalds@transmeta.com> writes:

>I'll show you a real example from drivers/acorn/scsi/acornscsi.c:

>	min(host->scsi.SCp.this_residual, DMAC_BUFFER_SIZE / 2);

>this_residual is "int", and "DMAC_BUFFER_SIZE" is just a #define for
>an integer constant. So the above is actually a signed comparison, and
>I'll bet you that was not what the author intended.

And the mistake of the author was not to write "unsigned int this_residual".
That's the bug. Not the min() function.

	Regards
		Henning

-- 
Dipl.-Inf. (Univ.) Henning P. Schmiedehausen       -- Geschaeftsfuehrer
INTERMETA - Gesellschaft fuer Mehrwertdienste mbH     hps@intermeta.de

Am Schwabachgrund 22  Fon.: 09131 / 50654-0   info@intermeta.de
D-91054 Buckenhof     Fax.: 09131 / 50654-20   

Re: [IDEA+RFC] Possible solution for min()/max() war

[Russell King]

On Tue, Aug 28, 2001 at 03:44:53PM +0000, Henning P. Schmiedehausen wrote:
> >I'll show you a real example from drivers/acorn/scsi/acornscsi.c:
> >	min(host->scsi.SCp.this_residual, DMAC_BUFFER_SIZE / 2);
> 
> >this_residual is "int", and "DMAC_BUFFER_SIZE" is just a #define for
> >an integer constant. So the above is actually a signed comparison, and
> >I'll bet you that was not what the author intended.
> 
> And the mistake of the author was not to write "unsigned int this_residual".
> That's the bug. Not the min() function.

Hmm, everyone's talking about my code.  And I agree with Henning that
"this_residual" should be unsigned.  Unfortunately, it's defined in the
generic SCSI layer.  I'd really like it to be fixed in the SCSI layer
no matter what the outcome of the min/max debarcle^wdebate is.

--
Russell King (rmk@arm.linux.org.uk)                The developer of ARM Linux
             http://www.arm.linux.org.uk/personal/aboutme.html

Re: [IDEA+RFC] Possible solution for min()/max() war

[Alan Cox]

> >	min(host->scsi.SCp.this_residual, DMAC_BUFFER_SIZE / 2);
> 
> >this_residual is "int", and "DMAC_BUFFER_SIZE" is just a #define for
> >an integer constant. So the above is actually a signed comparison, and
> >I'll bet you that was not what the author intended.
> 
> And the mistake of the author was not to write "unsigned int this_residual".
> That's the bug. Not the min() function.

Or more likely the author knew that this_residual was going to be positive
in all cases anyway. Its just sloppy typing by the scsi layer.

The typing of min() is something I do agree with Linus about (for once 8)),
and making people think about them is a good idea. When DaveM proposed the
original his patches showed up a bug in the older ixj driver immediately.

Alan

Re: [IDEA+RFC] Possible solution for min()/max() war

[Andreas Schwab]

Roman Zippel <zippel@linux-m68k.org> writes:

|> Hi,
|> 
|> Linus Torvalds wrote:
[...]
|> > You just fixed the "re-use arguments" bug - which is a bug, but doesn't
|> > address the fact that most of the min/max bugs are due to the programmer
|> > _indending_ a unsigned compare because he didn't even think about the
|> > type.
|> 
|> You maybe fixed a few bugs, but this new macro will only cause new
|> problems in the future. If we change only a single type, you have to
|> scan all min/max users if they possibly need to be changed too. Thanks
|> to the cast, the compiler won't even remotely help you finding them.

There is no cast in the min/max macros.

Andreas.

-- 
Andreas Schwab                                  "And now for something
SuSE Labs                                        completely different."
Andreas.Schwab@suse.de
SuSE GmbH, Schanzäckerstr. 10, D-90443 Nürnberg
Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5

Re: [IDEA+RFC] Possible solution for min()/max() war

[Roman Zippel]

Hi,

Linus Torvalds wrote:

> I'll show you a real example from drivers/acorn/scsi/acornscsi.c:
> 
>         min(host->scsi.SCp.this_residual, DMAC_BUFFER_SIZE / 2);
> 
> this_residual is "int", and "DMAC_BUFFER_SIZE" is just a #define for
> an integer constant. So the above is actually a signed comparison, and
> I'll bet you that was not what the author intended.
> 
> Now, this_residual is hopefully never negative, so it doesn't matter.

Let's assume it does. Joe Hacker uses the new min macro and uses int
because this_residual is an int. Later he realizes that this_residual
must be an unsigned int. Will he now also automatically change the type
in the min macro?

> But how many security bugs have you seen where people just didn't even
> _think_ of the user giving invalid values?
> 
> Think of code like
> 
>         #define BUFFER_SIZE (10)
> 
>         char buf[BUFFER_SIZE];
> 
>         len = min(user_len, BUFFER_SIZE);
>         if (copy_from_user(buf, user, len))
>                 return -EFAULT;
> 
> which is not all that broken. Sure, maybe you _should_ have marked
> BUFFER_SIZE explicitly unsigned, but face it, how many people actually do
> that?

How does the new macro help here? A negative value is invalid and so
should be tested _explicitly_.

What about code like this:

	if (len > BUFFER_SIZE)
		return -EINVAL;

This is not automagically fixed by this macro. So your new macro fixes a
few problems and hides other problems. I can't call this a solution.

> And did you realize, for example, that of the existing "min()"
> implementations, some were inline functions that implicitly cast their
> arguments to "int" (and one to "unsigned int")? This way we could also
> maintain those kinds of local conventions - where the programmer had
> originally (at least in the case of the unsigned int) on purpose made all
> "min()" functions unsigned.

I'm not arguing against a single (and correct) definition of min/max.
This had to be fixed of course.

> Now isn't it better to have a nice macro that _can_ be used for all of
> this, and that _does_ explicitly handle the issue of signedness that
> different parts of the code has very different opinions on, and that
> clearly encodes the assumptions that you have at the exact point of use?

But this assumption is only encoded once. Are you going to change the
min interface every second release, just to keep people thinking about
the types they're using? Breaking interfaces is fine, but it only works
_once_ and is simply forgotten afterwards. To quote my other argument,
that is still unanswered:

You maybe fixed a few bugs, but this new macro will only cause new
problems in the future. If we change only a single type, you have to
scan all min/max users if they possibly need to be changed too. Thanks
to the cast, the compiler won't even remotely help you finding them.

bye, Roman

Re: [IDEA+RFC] Possible solution for min()/max() war

[Roman Zippel]

Hi,

Andreas Schwab wrote:

> There is no cast in the min/max macros.

Ok, it uses an assignment, but it has almost the same effect (except for
pointer/integer values).

bye, Roman

Re: [IDEA+RFC] Possible solution for min()/max() war

[Roman Zippel]

Hi,

Alan Cox wrote:

> The typing of min() is something I do agree with Linus about (for once 8)),
> and making people think about them is a good idea. When DaveM proposed the
> original his patches showed up a bug in the older ixj driver immediately.

No doubt, that it fixed bugs now. What I'm worried about is whether it
really avoids bugs in the future and isn't a new source of bugs.

bye, Roman

Re: [IDEA+RFC] Possible solution for min()/max() war

[Bill Rugolsky Jr.]

On Tue, Aug 28, 2001 at 06:47:23PM +0200, Roman Zippel wrote:
> Ok, it uses an assignment, but it has almost the same effect (except for
> pointer/integer values).
 
Wrong.  A cast throws away information, making meaningful warnings impossible.
The assignment allows the compiler to apply the usual C integral
promotions and catch narrowing and non-value-preserving conversions,
like unsigned int to int, or an even more common bug, unsigned int to
long, which behaves differently depending on whether long is 32 or 64
bits.

Regards,

   Bill Rugolsky

Re: [IDEA+RFC] Possible solution for min()/max() war

[Roman Zippel]

Hi,

"Bill Rugolsky Jr." wrote:

> > Ok, it uses an assignment, but it has almost the same effect (except for
> > pointer/integer values).
> 
> Wrong.  A cast throws away information, making meaningful warnings impossible.
> The assignment allows the compiler to apply the usual C integral
> promotions and catch narrowing and non-value-preserving conversions,
> like unsigned int to int, or an even more common bug, unsigned int to
> long, which behaves differently depending on whether long is 32 or 64
> bits.

Do you have an example? AFAIK this can only be done for constants and
mosts constants used with min are within usual integer limits.

bye, Roman

Re: [IDEA+RFC] Possible solution for min()/max() war

[Richard B. Johnson]

On 28 Aug 2001, Andreas Schwab wrote:

> Roman Zippel <zippel@linux-m68k.org> writes:
> 
> |> Hi,
> |> 
> |> Linus Torvalds wrote:
> [...]
> |> > You just fixed the "re-use arguments" bug - which is a bug, but doesn't
> |> > address the fact that most of the min/max bugs are due to the programmer
> |> > _indending_ a unsigned compare because he didn't even think about the
> |> > type.


#if 0
If the comparison was made unsigned, cast to the largest natural
value on the target, while keeping the types and sizes of the
input variables the same, this macro does about what 99.9999999 percent
of what everybody wants:
#endif

#include <stdio.h>

#define min(a,b) ((size_t)(a) < (size_t)(b) ? (a) : (b))

int main()
{
    printf("%d\n", min(1,2));
    printf("%d\n", min(-1,2));
    printf("%d\n", min(0xffffffff,3));
    printf("%d\n", min(0x8000,4));
    printf("%d\n", min(0x7fff,5));
    printf("%d\n", min(0x80000000,6));
    printf("%d\n", min(0x7fffffff,7));

    printf("%ld\n", min(1L,2L));
    printf("%ld\n", min(-1L,2L));
    printf("%ld\n", min(0xffffffff,3L));
    printf("%ld\n", min(0x8000,4L));
    printf("%ld\n", min(0x7fff,5L));
    printf("%ld\n", min(0x80000000,6L));
    printf("%ld\n", min(0x7fffffff,7L));

    printf("%lu\n", min(1L,2LU));
    printf("%lu\n", min(-1L,2LU));
    printf("%lu\n", min(0xffffffff,3LU));
    printf("%lu\n", min(0x8000,4LU));
    printf("%lu\n", min(0x7fff,5LU));
    printf("%lu\n", min(0x80000000,6LU));
    printf("%lu\n", min(0x7fffffff,7LU));

    printf("%d\n", min(-1, -2));
    printf("%d\n", min(-1, 0));
    printf("%p\n", min((void *)0x80000000, (void *)0x7fffffff));
    return 0;
}



Cheers,
Dick Johnson

Penguin : Linux version 2.4.1 on an i686 machine (799.53 BogoMips).

    I was going to compile a list of innovations that could be
    attributed to Microsoft. Once I realized that Ctrl-Alt-Del
    was handled in the BIOS, I found that there aren't any.

Re: [IDEA+RFC] Possible solution for min()/max() war

[John Alvord]

On Tue, 28 Aug 2001 12:10:12 +0100 (BST), Alan Cox
<alan@lxorguk.ukuu.org.uk> wrote:

>> Or, with the 2.4.9 approach, it's just a single macro (well, and another
>> one for "max()"). And when somebody needs a new type, he doesn't have to
>> worry about creating a new instantiation of the macro.
>
>The unfortunate thing is that its min and max as opposed to typed_min and
>typed_max (with min/max set up to error), since its now a nightmare to 
>maintain compatibility between two allegedly stable releases of the same
>kernel, as well as with 2.2
>
>Had it been typed_min(a,b,c) then 2.2 could have stayed compatible and the
>glue would have been simple

Does the new min/max definitions hurt portability to and from Linux?

john alvord

Re: [IDEA+RFC] Possible solution for min()/max() war

[Mike Castle]

On Tue, Aug 28, 2001 at 06:39:43PM +0200, Roman Zippel wrote:
> Let's assume it does. Joe Hacker uses the new min macro and uses int
> because this_residual is an int. Later he realizes that this_residual
> must be an unsigned int. Will he now also automatically change the type
> in the min macro?


min (typeof(this_residual), this_residual, foo);

Though I'm not sure this would be accepted into the kernel.  :->

mrc
-- 
     Mike Castle      dalgoda@ix.netcom.com      www.netcom.com/~dalgoda/
    We are all of us living in the shadow of Manhattan.  -- Watchmen
fatal ("You are in a maze of twisty compiler features, all different"); -- gcc

Re: [IDEA+RFC] Possible solution for min()/max() war

[Daniel Phillips]

On August 28, 2001 05:14 pm, Linus Torvalds wrote:
> I'll show you a real example from drivers/acorn/scsi/acornscsi.c:
> 
> 	min(host->scsi.SCp.this_residual, DMAC_BUFFER_SIZE / 2);
> 
> this_residual is "int", and "DMAC_BUFFER_SIZE" is just a #define for
> an integer constant. So the above is actually a signed comparison, and
> I'll bet you that was not what the author intended.
> 
> Now, this_residual is hopefully never negative, so it doesn't matter.

    min(host->scsi.SCp.this_residual, (unsigned) DMAC_BUFFER_SIZE / 2);

--
Daniel

Re: [IDEA+RFC] Possible solution for min()/max() war

[Linus Torvalds]

On Wed, 29 Aug 2001, Daniel Phillips wrote:
>
>     min(host->scsi.SCp.this_residual, (unsigned) DMAC_BUFFER_SIZE / 2);

Sure.

If you put the type information explicitly, you can get it right.

Which is, btw, _exactly_ why the min() function takes the type explicitly.

		Linus

Re: [IDEA+RFC] Possible solution for min()/max() war

[Daniel Phillips]

On August 29, 2001 03:13 am, Linus Torvalds wrote:
> On Wed, 29 Aug 2001, Daniel Phillips wrote:
> >
> >     min(host->scsi.SCp.this_residual, (unsigned) DMAC_BUFFER_SIZE / 2);
> 
> Sure.
> 
> If you put the type information explicitly, you can get it right.
> 
> Which is, btw, _exactly_ why the min() function takes the type explicitly.

My point is that proper programming discipline would have prevented the 
problem from arising in the first place.  It would be far more appropriate 
for kernel programmers to exercise such discpline than to treat them like 
babies, breaking well-known syntax in the process.

It seems trivial to pick up all potential min/max problems with the Stanford 
Checker in the case some programmer has been too clueless to think about 
their code as they write it.  A simple policy statement for users of min/max 
would have avoided this entire mess.

Not that I you're going to back down, it just made me feel better to get this 
off my chest ;-)

--
Daniel

Re: [IDEA+RFC] Possible solution for min()/max() war

[David Lang]

one question that I thought of in context with the other e-mails in this
thread.

when you write a signed/unsigned comparison is it defined in any standard
which type the compiler should generate or is it somethign that could be
different in different compilers (and versions)

(also when comparing different size items same question)

if there are cases that are not defined in a standard and could vary by
compiler/version then we definantly need to have the current version with
the type argument.

David Lang


 On Wed, 29 Aug 2001,
Daniel Phillips wrote:

> Date: Wed, 29 Aug 2001 17:42:39 +0200
> From: Daniel Phillips <phillips@bonn-fries.net>
> To: Linus Torvalds <torvalds@transmeta.com>
> Cc: Roman Zippel <zippel@linux-m68k.org>, linux-kernel@vger.kernel.org
> Subject: Re: [IDEA+RFC] Possible solution for min()/max() war
>
> On August 29, 2001 03:13 am, Linus Torvalds wrote:
> > On Wed, 29 Aug 2001, Daniel Phillips wrote:
> > >
> > >     min(host->scsi.SCp.this_residual, (unsigned) DMAC_BUFFER_SIZE / 2);
> >
> > Sure.
> >
> > If you put the type information explicitly, you can get it right.
> >
> > Which is, btw, _exactly_ why the min() function takes the type explicitly.
>
> My point is that proper programming discipline would have prevented the
> problem from arising in the first place.  It would be far more appropriate
> for kernel programmers to exercise such discpline than to treat them like
> babies, breaking well-known syntax in the process.
>
> It seems trivial to pick up all potential min/max problems with the Stanford
> Checker in the case some programmer has been too clueless to think about
> their code as they write it.  A simple policy statement for users of min/max
> would have avoided this entire mess.
>
> Not that I you're going to back down, it just made me feel better to get this
> off my chest ;-)
>
> --
> Daniel
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
>

Re: [IDEA+RFC] Possible solution for min()/max() war

[Daniel Phillips]

On August 29, 2001 06:02 pm, David Lang wrote:
> one question that I thought of in context with the other e-mails in this
> thread.
> 
> when you write a signed/unsigned comparison is it defined in any standard
> which type the compiler should generate or is it somethign that could be
> different in different compilers (and versions)

Yes, in the signed/unsigned case the comparison generated is always
unsigned.  This is something that all c programmers are supposed to have 
tattoed on the insides of their eyelids, because if you don't know it
there are all kinds of situations that can bite you, not just min and
max.

> (also when comparing different size items same question)

The narrower is expanded to the size of the wider before being compared.

> if there are cases that are not defined in a standard and could vary by
> compiler/version then we definantly need to have the current version with
> the type argument.

No, these cases are defined perfectly clearly and have been at least
since K&R.

> David Lang
> 
> 
>  On Wed, 29 Aug 2001,
> Daniel Phillips wrote:
> 
> > Date: Wed, 29 Aug 2001 17:42:39 +0200
> > From: Daniel Phillips <phillips@bonn-fries.net>
> > To: Linus Torvalds <torvalds@transmeta.com>
> > Cc: Roman Zippel <zippel@linux-m68k.org>, linux-kernel@vger.kernel.org
> > Subject: Re: [IDEA+RFC] Possible solution for min()/max() war
> >
> > On August 29, 2001 03:13 am, Linus Torvalds wrote:
> > > On Wed, 29 Aug 2001, Daniel Phillips wrote:
> > > >
> > > >     min(host->scsi.SCp.this_residual, (unsigned) DMAC_BUFFER_SIZE / 
2);
> > >
> > > Sure.
> > >
> > > If you put the type information explicitly, you can get it right.
> > >
> > > Which is, btw, _exactly_ why the min() function takes the type 
explicitly.
> >
> > My point is that proper programming discipline would have prevented the
> > problem from arising in the first place.  It would be far more appropriate
> > for kernel programmers to exercise such discpline than to treat them like
> > babies, breaking well-known syntax in the process.
> >
> > It seems trivial to pick up all potential min/max problems with the 
Stanford
> > Checker in the case some programmer has been too clueless to think about
> > their code as they write it.  A simple policy statement for users of 
min/max
> > would have avoided this entire mess.
> >
> > Not that I you're going to back down, it just made me feel better to get 
this
> > off my chest ;-)
> >
> > --
> > Daniel
> > -
> > To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> > the body of a message to majordomo@vger.kernel.org
> > More majordomo info at  http://vger.kernel.org/majordomo-info.html
> > Please read the FAQ at  http://www.tux.org/lkml/
> >
> -
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
> 
> 

Re: [IDEA+RFC] Possible solution for min()/max() war

[Bill Rugolsky Jr.]

On Thu, Aug 30, 2001 at 01:49:54AM +0200, Daniel Phillips wrote:
> On August 29, 2001 06:02 pm, David Lang wrote:
> > when you write a signed/unsigned comparison is it defined in any standard
> > which type the compiler should generate or is it somethign that could be
> > different in different compilers (and versions)
> 
> Yes, in the signed/unsigned case the comparison generated is always
> unsigned.  This is something that all c programmers are supposed to have 
> tattoed on the insides of their eyelids, because if you don't know it
> there are all kinds of situations that can bite you, not just min and
> max.
> 
> > (also when comparing different size items same question)
> 
> The narrower is expanded to the size of the wider before being compared.

Careful.  Operands of relational operators undergo "usual arithmetic
conversions," which are value-preserving, so unsigned char and unsigned
short are promoted to int on platforms where int is value-preserving.
Similarly, unsigned int is promoted to long where long is value-preserving,
as I pointed out earlier in this thread.  (This wasn't always the case,
see below.)

The problem here, of course, is that if you don't know the widths of the
operands, you can't determine the type of the compare.  Change the width
of the operand (to steal some bits in a structure, say) and the signedness
of the comparison changes.

> 
> > if there are cases that are not defined in a standard and could vary by
> > compiler/version then we definantly need to have the current version with
> > the type argument.
> 
> No, these cases are defined perfectly clearly and have been at least
> since K&R.

K&R 1st Edition and the UNIX 7th Edition C reference manual specify that
unsigned dominates.  The "value-preserving" language was crafted for
C89, and appears in K&R, 2nd Edition.  C99 introduces the notion of
integer type "rank" to generalize the rules to extended precision types.

Regards,

   Bill Rugolsky

Re: [IDEA+RFC] Possible solution for min()/max() war

[Linus Torvalds]

On Thu, 30 Aug 2001, Daniel Phillips wrote:
>
> Yes, in the signed/unsigned case the comparison generated is always
> unsigned.

Well... No.

If you compare a signed integer with a unsigned char, the char gets
promoted to a _signed_ integer, and the comparison is signed. It is NOT
a unsigned comparison.

And THIS is one example of why it gets complicated.

The C logic for type expansion is just a tad too easy to get wrong, and
the strict type-checking you normally have with well-written ANSI C simply
does not exist for integer types. The compiler will silently just do the
promotion..

Somebody mentioned -Wsign-compare. Try it with the example above. It won't
warn at all, exactly because under C both sides of such a compare have the
_same_ sign, even if one is a "unsigned char", and the other is a "signed
int".

Try it yourself if you don't believe me.

Please guys. The issue of sign in comparisons are a LOT more complicated
than most of you seem to think.

		Linus

Re: [IDEA+RFC] Possible solution for min()/max() war

[Ion Badulescu]

On Wed, 29 Aug 2001 20:28:20 -0700 (PDT), Linus Torvalds <torvalds@transmeta.com> wrote:

> If you compare a signed integer with a unsigned char, the char gets
> promoted to a _signed_ integer, and the comparison is signed. It is NOT
> a unsigned comparison.
> 
[...]
> 
> Somebody mentioned -Wsign-compare. Try it with the example above. It won't
> warn at all, exactly because under C both sides of such a compare have the
> _same_ sign, even if one is a "unsigned char", and the other is a "signed
> int".

And why should the compiler warn at all? The range of "int" completely 
covers the range of "unsigned char", so the result of the comparison will 
always be correct if the types were chosen correctly.

... unless of course the programmer used an unsigned char when what he 
really wanted was a signed char. But in that case even your typed min 
macro won't save him, because what should the forced type be anyway? If 
it's "int", nothing changes; if it's "signed char", you risk truncating 
the int. So you end up with something like

	min(int, a, (char)b)

and I fail to see how this is any better than

	min(a, (char)b)

Ion

-- 
  It is better to keep your mouth shut and be thought a fool,
            than to open it and remove all doubt.

Re: [IDEA+RFC] Possible solution for min()/max() war

[David Woodhouse]

ionut@cs.columbia.edu said:
> ... unless of course the programmer used an unsigned char when what he
>  really wanted was a signed char. But in that case even your typed min
>  macro won't save him, because what should the forced type be anyway?
> If  it's "int", nothing changes; if it's "signed char", you risk
> truncating  the int. So you end up with something like

> 	min(int, a, (char)b) 

If the programmer wrote that when he really wanted a signed char, he has 
more fundamental brokenness to worry about than the min/max fun.

--
dwmw2

Re: [IDEA+RFC] Possible solution for min()/max() war

[Ion Badulescu]

On Thu, 30 Aug 2001, David Woodhouse wrote:

> 
> 
> ionut@cs.columbia.edu said:
> > ... unless of course the programmer used an unsigned char when what he
> >  really wanted was a signed char. But in that case even your typed min
> >  macro won't save him, because what should the forced type be anyway?
> > If  it's "int", nothing changes; if it's "signed char", you risk
> > truncating  the int. So you end up with something like
> 
> > 	min(int, a, (char)b) 
> 
> If the programmer wrote that when he really wanted a signed char, he has 
> more fundamental brokenness to worry about than the min/max fun.

Which is precisely my point, we're in violent agreement here...

Ion

-- 
  It is better to keep your mouth shut and be thought a fool,
            than to open it and remove all doubt.

Re: [IDEA+RFC] Possible solution for min()/max() war

[Roman Zippel]

[-- Attachment #1: Type: text/plain, Size: 1933 bytes --]

Hi,

> Please guys. The issue of sign in comparisons are a LOT more complicated
> than most of you seem to think.

So why won't you let the compiler help you, even if it's not perfect in
every case?

This is my last attempt to get things IMO right. Most of the arguments
for the new macro were about bugs of the past. No question about this,
this had to be fixed, I'm not arguing about this at all.

I'm trying to get your attention to the bugs of the future. I still
don't understand why you think the new macro will be any better. Why do
you think the average kernel hacker will think about the type of the
compare and will come to the correct conclusion? It's far to easy to use
an int as type argument and forget about it. gcc won't warn about this,
so someone first has to hit this bug, before it gets fixed.

Maybe I'm too dumb, but I still fail to see, what sense it should make
to turn a signed compare into an unsigned one. Either one knows both
signed values are only positive, then the sign of the compare and the
destination doesn't matter at all. If the value could be negative,
better test it explicit:

	if (len < 0 || len > MAX)
		len = MAX;

First, it's far more readable and makes the intention so clear, that
even your average kernel hacker understands it. Second, gcc produces
exactly the same code with this, so there is no need to play type tricks
with the min macro.

Just for fun I enabled -Wsign-compare, enabled most of the drivers and I
got this:

$ grep 'comparison between signed and unsigned' make.log | sort | uniq |
wc -l
   3211

So if you want to get people thinking about the types they are using,
here you have at least 3211 chances.

Please reconsider your decision. IMVHO the new macros are a mistake and
will cause only more trouble than they are worth. If you want to keep
the new macros, please apply the attached patch, as I prefer this
version in the source I'm responsible for.

bye, Roman

[-- Attachment #2: affs.diff --]
[-- Type: text/plain, Size: 4223 bytes --]

Index: include/linux/amigaffs.h
===================================================================
RCS file: /cvsroot/linux-apus/2.3/include/linux/amigaffs.h,v
retrieving revision 1.1.1.3
diff -u -r1.1.1.3 amigaffs.h
--- include/linux/amigaffs.h	2001/07/22 23:22:24	1.1.1.3
+++ include/linux/amigaffs.h	2001/08/30 13:38:24
@@ -122,7 +122,7 @@
 }
 
 
-#define MIN(a, b) ({		\
+#define affs_min(a, b) ({	\
 	typeof(a) _a = (a);	\
 	typeof(b) _b = (b);	\
 	_a < _b ? _a : _b;	\
Index: fs/affs/amigaffs.c
===================================================================
RCS file: /cvsroot/linux-apus/2.3/fs/affs/amigaffs.c,v
retrieving revision 1.6
diff -u -r1.6 amigaffs.c
--- fs/affs/amigaffs.c	2001/08/20 13:23:07	1.6
+++ fs/affs/amigaffs.c	2001/08/30 13:38:24
@@ -507,7 +507,7 @@
 int
 affs_copy_name(unsigned char *bstr, struct dentry *dentry)
 {
-	int len = MIN(dentry->d_name.len, 30);
+	int len = affs_min(dentry->d_name.len, 30);
 
 	*bstr++ = len;
 	memcpy(bstr, dentry->d_name.name, len);
Index: fs/affs/dir.c
===================================================================
RCS file: /cvsroot/linux-apus/2.3/fs/affs/dir.c,v
retrieving revision 1.1.1.6
diff -u -r1.1.1.6 dir.c
--- fs/affs/dir.c	2001/07/22 23:18:04	1.1.1.6
+++ fs/affs/dir.c	2001/08/30 13:38:24
@@ -135,7 +135,7 @@
 				goto readdir_done;
 			}
 
-			namelen = MIN(AFFS_TAIL(sb, fh_bh)->name[0], 30);
+			namelen = affs_min(AFFS_TAIL(sb, fh_bh)->name[0], 30);
 			name = AFFS_TAIL(sb, fh_bh)->name + 1;
 			pr_debug("AFFS: readdir(): filldir(\"%.*s\", ino=%u), hash=%d, f_pos=%x\n",
 				 namelen, name, ino, hash_pos, f_pos);
Index: fs/affs/file.c
===================================================================
RCS file: /cvsroot/linux-apus/2.3/fs/affs/file.c,v
retrieving revision 1.1.1.8
diff -u -r1.1.1.8 file.c
--- fs/affs/file.c	2001/08/20 23:44:37	1.1.1.8
+++ fs/affs/file.c	2001/08/30 13:38:25
@@ -528,7 +528,7 @@
 		bh = affs_bread_ino(inode, bidx, 0);
 		if (IS_ERR(bh))
 			return PTR_ERR(bh);
-		tmp = MIN(bsize - boff, from - to);
+		tmp = affs_min(bsize - boff, from - to);
 		memcpy(data + from, AFFS_DATA(bh) + boff, tmp);
 		affs_brelse(bh);
 		bidx++;
@@ -558,7 +558,7 @@
 		bh = affs_bread_ino(inode, bidx, 0);
 		if (IS_ERR(bh))
 			return PTR_ERR(bh);
-		tmp = MIN(bsize - boff, newsize - size);
+		tmp = affs_min(bsize - boff, newsize - size);
 		memset(AFFS_DATA(bh) + boff, 0, tmp);
 		AFFS_DATA_HEAD(bh)->size = cpu_to_be32(be32_to_cpu(AFFS_DATA_HEAD(bh)->size) + tmp);
 		affs_fix_checksum(sb, bh);
@@ -576,7 +576,7 @@
 		bh = affs_getzeroblk_ino(inode, bidx);
 		if (IS_ERR(bh))
 			goto out;
-		tmp = MIN(bsize, newsize - size);
+		tmp = affs_min(bsize, newsize - size);
 		AFFS_DATA_HEAD(bh)->ptype = cpu_to_be32(T_DATA);
 		AFFS_DATA_HEAD(bh)->key = cpu_to_be32(inode->i_ino);
 		AFFS_DATA_HEAD(bh)->sequence = cpu_to_be32(bidx);
@@ -685,7 +685,7 @@
 		bh = affs_bread_ino(inode, bidx, 0);
 		if (IS_ERR(bh))
 			return PTR_ERR(bh);
-		tmp = MIN(bsize - boff, to - from);
+		tmp = affs_min(bsize - boff, to - from);
 		memcpy(AFFS_DATA(bh) + boff, data + from, tmp);
 		AFFS_DATA_HEAD(bh)->size = cpu_to_be32(be32_to_cpu(AFFS_DATA_HEAD(bh)->size) + tmp);
 		affs_fix_checksum(sb, bh);
@@ -731,7 +731,7 @@
 		bh = affs_bread_ino(inode, bidx, 1);
 		if (IS_ERR(bh))
 			goto out;
-		tmp = MIN(bsize, to - from);
+		tmp = affs_min(bsize, to - from);
 		memcpy(AFFS_DATA(bh), data + from, tmp);
 		if (bh->b_state & (1UL << BH_New)) {
 			AFFS_DATA_HEAD(bh)->ptype = cpu_to_be32(T_DATA);
Index: fs/affs/namei.c
===================================================================
RCS file: /cvsroot/linux-apus/2.3/fs/affs/namei.c,v
retrieving revision 1.9
diff -u -r1.9 namei.c
--- fs/affs/namei.c	2001/08/21 17:57:27	1.9
+++ fs/affs/namei.c	2001/08/30 13:38:25
@@ -81,7 +81,7 @@
 		return i;
 
 	hash = init_name_hash();
-	i = MIN(qstr->len, 30);
+	i = affs_min(qstr->len, 30);
 	for (; i > 0; name++, i--)
 		hash = partial_name_hash(toupper(*name), hash);
 	qstr->hash = end_name_hash(hash);
@@ -172,7 +172,7 @@
 	toupper_t toupper = affs_get_toupper(sb);
 	int hash;
 
-	hash = len = MIN(len, 30);
+	hash = len = affs_min(len, 30);
 	for (; len > 0; len--)
 		hash = (hash * 13 + toupper(*name++)) & 0x7ff;
 

Re: [IDEA+RFC] Possible solution for min()/max() war

[Linus Torvalds]

On Thu, 30 Aug 2001, Ion Badulescu wrote:
> >
> > Somebody mentioned -Wsign-compare. Try it with the example above. It won't
> > warn at all, exactly because under C both sides of such a compare have the
> > _same_ sign, even if one is a "unsigned char", and the other is a "signed
> > int".
>
> And why should the compiler warn at all? The range of "int" completely
> covers the range of "unsigned char", so the result of the comparison will
> always be correct if the types were chosen correctly.

You obviously do not understand the issue at all.

It doesn't _matter_ that the int covers the whole space of "unsigned
char".

What if the "int" happens to be negative?

Right. You get _totally_ different results for a unsigned and a signed
compare. For the signed compare, you do obviously get the "logical"
result, that the negative int is smaller than the unsigned char. But if
you're not _aware_ of the signedness, you may not think about the issues.

Basically, when you compare a "long" to a "xxx", and the xxxx is unsigned,
WHAT ARE THE RESULTS?

And the answer is that you simply DO NOT KNOW! If the xxxx is "unsigned
int", the sign of the compare actually depends on whether "int" is smaller
than "long" on the particular architecture you're compiling for. So the
sign of the compare actually ends up being different on an alpha than on a
x86.

Stating the type you compare in explicitly means that you do not get
surprised.

And not getting surprisied is a good thing.

		Linus

Re: [IDEA+RFC] Possible solution for min()/max() war

[Linus Torvalds]

On Thu, 30 Aug 2001, Roman Zippel wrote:
>
> So why won't you let the compiler help you, even if it's not perfect in
> every case?

I considered enabling -Wsign-compare a long time ago, and it's not a
question of being "perfect", but a question of being _so_ broken that it's
not funny.

For example, let's look at this perfectly natural code:

	static int unix_mkname(struct sockaddr_un * sunaddr, int len, unsigned *hashp)
	{
		if (len <= sizeof(short) || len > sizeof(*sunaddr))
			return -EINVAL;
		...

Would you agree that the above is _good_ code, and code that makes
perfect sense, and code that does exactly the right thing in testing its
arguments?

Try to compile it with -Wsign-compare.

You'll get not one, but TWO warnings for code that is totally correct, and
that it would make _no_ sense in writing any other way.

In short, -Wsign-compare (at least with a _lot_ of gcc versions) warns for
totally sane and reasonable code - for code that exists all over the
kernel. The above snippet is in fact directly from the kernel, go look and
see for yourself.

In short, -Wsign-compare is totally useless. The warnings are mostly _so_
bogus that nobody has the energy to even try to figure out which of them
might actually be worthwhile.

Face it, you don't know what you're talking about.

		Linus

Re: [IDEA+RFC] Possible solution for min()/max() war

[Ion Badulescu]

On Thu, 30 Aug 2001, Linus Torvalds wrote:

> You obviously do not understand the issue at all.

No offence, but you obviously assume too much.

> It doesn't _matter_ that the int covers the whole space of "unsigned
> char".
> 
> What if the "int" happens to be negative?

If the "int" happens to be negative, the comparison will say that the
"int" is smaller than the "unsigned char". This is the expected result.
What exactly is wrong with this?

So I have this number, -200, which is stored in an int. I have this other
number, 200, which is stored in an unsigned char. Everybody in his right
mind will agree that -200 is smaller than 200, the compiler will do just
that, yet you disagree???

> Basically, when you compare a "long" to a "xxx", and the xxxx is unsigned,
> WHAT ARE THE RESULTS?

So now you're turning it around. If you compare a long with unsigned char,
there is no issue. If you compare long with unsigned int, you get the
right result on the alpha and a warning on x86. If you compare long with
unsigned long, you get a warning period.

> And the answer is that you simply DO NOT KNOW! If the xxxx is "unsigned
> int", the sign of the compare actually depends on whether "int" is smaller
> than "long" on the particular architecture you're compiling for. So the
> sign of the compare actually ends up being different on an alpha than on a
> x86.

And read above. You get the right result on the alpha and a warning on the 
x86. I don't see the problem with that.

If you want to be 100% paranoid, change the sign-compare warning into an 
error, so people don't ignore it. That's a much better alternative, and 
gcc supports it.

> Stating the type you compare in explicitly means that you do not get
> surprised.

No. It means I suppress the gcc warning before I get a chance to see it. 
It does NOT necessarily mean I (and by "I" I mean your average programmer) 
think about the range issues, I just think Linux min/max are broken.

> And not getting surprisied is a good thing.

Duplicating types all over the place is a bad thing, however.

Ion

-- 
  It is better to keep your mouth shut and be thought a fool,
            than to open it and remove all doubt.

Re: [IDEA+RFC] Possible solution for min()/max() war

[Ben LaHaise]

On Thu, 30 Aug 2001, Linus Torvalds wrote:

> And not getting surprisied is a good thing.

Most of us don't really care about the details of the whole min/max thing
(my only real care is that it should've been called anything other than
min or max, typed_min perhaps, but that's a secondary issue, more relevant
to forwards compatibility of 2.4/2.2/2.0 hybrid drivers).  What we do care
about is the fact that a release was done without a prepatch to look over
to give people a chance to fix any resulting breakage.

		-ben

Re: [IDEA+RFC] Possible solution for min()/max() war

[Peter T. Breuer]

"Linus Torvalds wrote:"
> What if the "int" happens to be negative?

   if sizeof(typeof(a)) != sizeof(typeof(b)) 
       BUG() // sizes differ
   const (typeof(a)) _a = ~(typeof(a))0   
   const (typeof(b)) _b = ~(typeof(b))0   
   if _a < 0 && _b > 0 || _a > 0 && b < 0
       BUG() // one signed, the other unsigned
   standard_max(a,b)


Peter 

Re: [IDEA+RFC] Possible solution for min()/max() war

[Christopher Friesen]

Linus Torvalds wrote:

> For example, let's look at this perfectly natural code:
> 
>         static int unix_mkname(struct sockaddr_un * sunaddr, int len, unsigned *hashp)
>         {
>                 if (len <= sizeof(short) || len > sizeof(*sunaddr))
>                         return -EINVAL;
>                 ...
> 
> Would you agree that the above is _good_ code, and code that makes
> perfect sense, and code that does exactly the right thing in testing its
> arguments?

Wouldn't it have made more sense to make the 'len' parameter an unsigned int? 
Presumably we can't have a negative length for a name.  In this case the
warnings should just go away, no?


-- 
Chris Friesen                    | MailStop: 043/33/F10  
Nortel Networks                  | work: (613) 765-0557
3500 Carling Avenue              | fax:  (613) 765-2986
Nepean, ON K2H 8E9 Canada        | email: cfriesen@nortelnetworks.com

Re: [IDEA+RFC] Possible solution for min()/max() war

[Linus Torvalds]

On Thu, 30 Aug 2001, Christopher Friesen wrote:
>
> Wouldn't it have made more sense to make the 'len' parameter an unsigned int?

Oh yes.

And wouldn't it be nicer if the sky was pink, and God came personally down
to earth and stopped all wrans and made you king?

You do realize that many things are signed, whether you want them to be or
not?

Like "off_t", which on the face of it sounds like it should be unsigned
("offset within a file - oh, that can obviously never be negative").

		Linus

Re: [IDEA+RFC] Possible solution for min()/max() war

[Daniel Phillips]

On August 30, 2001 05:28 am, Linus Torvalds wrote:
> On Thu, 30 Aug 2001, Daniel Phillips wrote:
> >
> > Yes, in the signed/unsigned case the comparison generated is always
> > unsigned.
> 
> Well... No.
> 
> If you compare a signed integer with a unsigned char, the char gets
> promoted to a _signed_ integer, and the comparison is signed. It is NOT
> a unsigned comparison.

Lets not go into how stupid that is.  Yes, things changed between K&R 
editions 1 and 2, in a misguided attempt to make things less "surprising" the 
drafters just introduced additional confusion.

> And THIS is one example of why it gets complicated.
>
> The C logic for type expansion is just a tad too easy to get wrong, and
> the strict type-checking you normally have with well-written ANSI C simply
> does not exist for integer types. The compiler will silently just do the
> promotion..
> 
> Somebody mentioned -Wsign-compare. Try it with the example above. It won't
> warn at all, exactly because under C both sides of such a compare have the
> _same_ sign, even if one is a "unsigned char", and the other is a "signed
> int".
> 
> Try it yourself if you don't believe me.
> 
> Please guys. The issue of sign in comparisons are a LOT more complicated
> than most of you seem to think.

More than anything, it shows that education is needed, not macro patch-ups.
We have exactly the same issues with < and >, should we introduce 
three-argument macros to replace them?

--
Daniel

Re: [IDEA+RFC] Possible solution for min()/max() war

[Peter T. Breuer]

"Daniel Phillips wrote:"
> More than anything, it shows that education is needed, not macro patch-ups.
> We have exactly the same issues with < and >, should we introduce 
> three-argument macros to replace them?

# define le(t,a,b) ({ t _a = a; t _b = b;  min(t,_a,_b) == _a ; })
# define ge(t,a,b) ({ t _a = a; t _b = b;  min(t,_a,_b) == _b ; })

;-)

Peter

Re: [IDEA+RFC] Possible solution for min()/max() war

[Roman Zippel]

Hi,

Linus Torvalds wrote:

>         static int unix_mkname(struct sockaddr_un * sunaddr, int len, unsigned *hashp)
>         {
>                 if (len <= sizeof(short) || len > sizeof(*sunaddr))
>                         return -EINVAL;
>                 ...
> 
> Would you agree that the above is _good_ code, and code that makes
> perfect sense, and code that does exactly the right thing in testing its
> arguments?

Where is the problem to change the type into "unsigned int"?

> Face it, you don't know what you're talking about.

Sorry, but what makes you so sure about it?
Anyway, forget -Wsign-compare, but could you _please_ give me an answer
to my other arguments? Maybe I'm a stupid idiot, but then please
enlighten me and show me the right way. So here is the important part of
my mail again:

This is my last attempt to get things IMO right. Most of the arguments
for the new macro were about bugs of the past. No question about this,
this had to be fixed, I'm not arguing about this at all.

I'm trying to get your attention to the bugs of the future. I still
don't understand why you think the new macro will be any better. Why do
you think the average kernel hacker will think about the type of the
compare and will come to the correct conclusion? It's far too easy to
use an int as type argument and forget about it. gcc won't warn about
this, so someone first has to hit this bug, before it gets fixed.

Maybe I'm too dumb, but I still fail to see, what sense it should make
to turn a signed compare into an unsigned one. Either one knows both
signed values are only positive, then the sign of the compare and the
destination doesn't matter at all. If the value could be negative,
better test it explicit:

        if (len < 0 || len > MAX)
                len = MAX;

First, it's far more readable and makes the intention so clear, that
even your average kernel hacker understands it. Second, gcc produces
exactly the same code with this, so there is no need to play type tricks
with the min macro.

Please reconsider your decision. IMVHO the new macros are a mistake and
will cause only more trouble than they are worth.

bye, Roman

Re: [IDEA+RFC] Possible solution for min()/max() war

[Daniel Phillips]

On August 30, 2001 07:03 pm, Peter T. Breuer wrote:
> "Daniel Phillips wrote:"
> > More than anything, it shows that education is needed, not macro 
patch-ups.
> > We have exactly the same issues with < and >, should we introduce 
> > three-argument macros to replace them?
> 
> # define le(t,a,b) ({ t _a = a; t _b = b;  min(t,_a,_b) == _a ; })
> # define ge(t,a,b) ({ t _a = a; t _b = b;  min(t,_a,_b) == _b ; })

Oh, you are one sick puppy.

For completeness:

# define lt(t,a,b) ({ t _a = a; t _b = b;  min(t,_a,_b) != _b ; })
# define gt(t,a,b) ({ t _a = a; t _b = b;  min(t,_a,_b) != _a ; })

--
Daniel

Re: [IDEA+RFC] Possible solution for min()/max() war

[David Weinehall]

On Thu, Aug 30, 2001 at 06:38:40PM +0200, Peter T. Breuer wrote:
> "Linus Torvalds wrote:"
> > What if the "int" happens to be negative?
> 
>    if sizeof(typeof(a)) != sizeof(typeof(b)) 
>        BUG() // sizes differ
>    const (typeof(a)) _a = ~(typeof(a))0   
>    const (typeof(b)) _b = ~(typeof(b))0   
>    if _a < 0 && _b > 0 || _a > 0 && b < 0
>        BUG() // one signed, the other unsigned
>    standard_max(a,b)

<disgusting vomit-sound>Do you really want code like that in the
kernel (yes, I know that there are code that can compete with it in
ugliness</disgusting vomit-sound>


/David Weinehall
  _                                                                 _
 // David Weinehall <tao@acc.umu.se> /> Northern lights wander      \\
//  Project MCA Linux hacker        //  Dance across the winter sky //
\>  http://www.acc.umu.se/~tao/    </   Full colour fire           </

Re: [IDEA+RFC] Possible solution for min()/max() war

[Peter T. Breuer]

"A month of sundays ago David Weinehall wrote:"
> On Thu, Aug 30, 2001 at 06:38:40PM +0200, Peter T. Breuer wrote:
> > "Linus Torvalds wrote:"
> > > What if the "int" happens to be negative?
> > 
> >    if sizeof(typeof(a)) != sizeof(typeof(b)) 
> >        BUG() // sizes differ
> >    const (typeof(a)) _a = ~(typeof(a))0   
> >    const (typeof(b)) _b = ~(typeof(b))0   
> >    if _a < 0 && _b > 0 || _a > 0 && b < 0
> >        BUG() // one signed, the other unsigned
> >    standard_max(a,b)
> 
> <disgusting vomit-sound>Do you really want code like that in the
> kernel (yes, I know that there are code that can compete with it in

Have you read it? Do you not realize That it optimizes down to BUG() or
the standard min/max? By BUG(), I was hoping that somebody could 
produce some magic that doesn't even compile when it reduces to that,
but maybe that's too much to hope for from gcc.

> ugliness</disgusting vomit-sound>

If that's the limit of the audiences intelligence, I don't think
I'll bother bothering to think next time! I rather hoped instead
for people to pick up the idea and tell me about the problem
left to cover (void* ? what if the arch does not have 2's complement
arithmetic?)

Peter

Re: [IDEA+RFC] Possible solution for min()/max() war

[Daniel Phillips]

On August 30, 2001 09:51 pm, David Weinehall wrote:
> On Thu, Aug 30, 2001 at 06:38:40PM +0200, Peter T. Breuer wrote:
> > "Linus Torvalds wrote:"
> > > What if the "int" happens to be negative?
> > 
> >    if sizeof(typeof(a)) != sizeof(typeof(b)) 
> >        BUG() // sizes differ
> >    const (typeof(a)) _a = ~(typeof(a))0   
> >    const (typeof(b)) _b = ~(typeof(b))0   
> >    if _a < 0 && _b > 0 || _a > 0 && b < 0
> >        BUG() // one signed, the other unsigned
> >    standard_max(a,b)
> 
> <disgusting vomit-sound>Do you really want code like that in the
> kernel (yes, I know that there are code that can compete with it in
> ugliness</disgusting vomit-sound>

Well, loook, if the signedness and widths match all the tests get optimized 
out as constant expressions, if they don't it barfs with BUG and the author 
has to insert specify saner types for the input variables.  It's nice.

This accomplishes what 3arg_min/max set out to do without messing up the 
syntax.

--
Daniel

Re: [IDEA+RFC] Possible solution for min()/max() war

[Graham Murray]

Daniel Phillips <phillips@bonn-fries.net> writes:

> More than anything, it shows that education is needed, not macro patch-ups.
> We have exactly the same issues with < and >, should we introduce 
> three-argument macros to replace them?

Would it not have been much more "obvious" if the rules for
unsigned/signed integer comparisons (irrespective of the widths
involved) were

1) If the signed element is negative then it is always less than the
   unsigned element.

2) If the unsigned element is greater than then maximum positive value
   expressible by the signed one then it is always greater.

3) Only if both values are positive and within the range of the
   smaller element are the actual values compared. 

Re: [IDEA+RFC] Possible solution for min()/max() war

[David Weinehall]

On Thu, Aug 30, 2001 at 09:16:47PM +0000, Graham Murray wrote:
> Daniel Phillips <phillips@bonn-fries.net> writes:
> 
> > More than anything, it shows that education is needed, not macro patch-ups.
> > We have exactly the same issues with < and >, should we introduce 
> > three-argument macros to replace them?
> 
> Would it not have been much more "obvious" if the rules for
> unsigned/signed integer comparisons (irrespective of the widths
> involved) were
> 
> 1) If the signed element is negative then it is always less than the
>    unsigned element.
> 
> 2) If the unsigned element is greater than then maximum positive value
>    expressible by the signed one then it is always greater.
> 
> 3) Only if both values are positive and within the range of the
>    smaller element are the actual values compared. 

Possibly, but changing the C specification is not really an option here...


/David Weinehall
  _                                                                 _
 // David Weinehall <tao@acc.umu.se> /> Northern lights wander      \\
//  Project MCA Linux hacker        //  Dance across the winter sky //
\>  http://www.acc.umu.se/~tao/    </   Full colour fire           </

Re: [IDEA+RFC] Possible solution for min()/max() war

[Patrick J. LoPresti]

Graham Murray <graham@barnowl.demon.co.uk> writes:

> Daniel Phillips <phillips@bonn-fries.net> writes:
> 
> > More than anything, it shows that education is needed, not macro patch-ups.
> > We have exactly the same issues with < and >, should we introduce 
> > three-argument macros to replace them?
> 
> Would it not have been much more "obvious" if the rules for
> unsigned/signed integer comparisons (irrespective of the widths
> involved) were
> 
> 1) If the signed element is negative then it is always less than the
>    unsigned element.
> 
> 2) If the unsigned element is greater than then maximum positive value
>    expressible by the signed one then it is always greater.
> 
> 3) Only if both values are positive and within the range of the
>    smaller element are the actual values compared. 

With infinite-precision arithmetic, yes; of course min() should just
return the smaller value.

But what would the C type of "min" be for comparing, say, signed and
unsigned longs?  The range of possible results does not fit in any
integral type.  (Repeat the question for signed/unsigned "long long"
if "long long" is your answer.)

 - Pat

Re: [IDEA+RFC] Possible solution for min()/max() war

[Patrick J. LoPresti]

"Peter T. Breuer" <ptb@it.uc3m.es> writes:

> "Linus Torvalds wrote:"
> > What if the "int" happens to be negative?
> 
>    if sizeof(typeof(a)) != sizeof(typeof(b)) 
>        BUG() // sizes differ
>    const (typeof(a)) _a = ~(typeof(a))0   
>    const (typeof(b)) _b = ~(typeof(b))0   
>    if _a < 0 && _b > 0 || _a > 0 && b < 0
>        BUG() // one signed, the other unsigned
>    standard_max(a,b)

This is a MUCH nicer solution.  max() is a well-defined mathematical
concept; it is simply the larger of its two arguments, period.  It is
C's *promotion* rules that kill you, especially signed->unsigned
promotion.  So just forbid them, at least when they implicit.

You can argue about whether the "differing sizes" case should be a
BUG(), since the output will still be mathematically correct.  It
depends on how often it is useful to compare (say) unsigned chars
against ints, and on whether the compiler warns about cases where you
try to stuff the return value into a too-small container.  I bet that
just forbidding signed->unsigned promotion would be enough.

In general, types should work for the programmer, not the other way
around.  Force people to "think hard" about their types when they are
making a likely mistake, not *every* time they call max().

Littering all those calls with types is just gross.

 - Pat

Re: [IDEA+RFC] Possible solution for min()/max() war

[Peter T. Breuer]

"A month of sundays ago Patrick J. LoPresti wrote:"
> This is a MUCH nicer solution.  max() is a well-defined mathematical
> concept; it is simply the larger of its two arguments, period.  It is
> C's *promotion* rules that kill you, especially signed->unsigned
> promotion.  So just forbid them, at least when they implicit.
> 
> You can argue about whether the "differing sizes" case should be a
> BUG(), since the output will still be mathematically correct.  It

To give you all something definite to look at, here's some test code:

// standard good 'ol faithful version
#define __MIN(x,y) ({\
   typeof(x) _x = x; \
   typeof(y) _y = y; \
   _x < _y ? _x : _y ; \
 })

// possible implemetation with type sanity checks - alter to taste
#define MIN(x,y) ({\
   const typeof(x) _x = ~(typeof(x))0; \
   const typeof(y) _y = ~(typeof(y))0; \
   void MIN_BUG(); \
   if (sizeof(_x) != sizeof(_y)) \
     MIN_BUG(); \
   if ((_x > 0 && _y < 0) || (_x < 0 && _y > 0)) \
     MIN_BUG(); \
   __MIN(x,y); \
 })

// test code that compiles with no complaints with -O1 -Wall
int main() {
  unsigned i = 1;
  unsigned j = -2;
  return MIN(i,j);
}

// test code that complains at link time (in this version) with ..
//  gcc -o test -O1 -Wall test.c
// /tmp/cczJbwv5.o: In function `main':
// /tmp/cczJbwv5.o(.text+0x7): undefined reference to `MIN_BUG'
// collect2: ld returned 1 exit status
//
int main() {
  unsigned i = 1;
  signed j = -2;
  return MIN(i,j);
}

> depends on how often it is useful to compare (say) unsigned chars
> against ints, and on whether the compiler warns about cases where you
> try to stuff the return value into a too-small container.  I bet that
> just forbidding signed->unsigned promotion would be enough.

Possibly. I have little clue as to the real extent of the problem.

Peter

Re: [IDEA+RFC] Possible solution for min()/max() war

[Linus Torvalds]

On Fri, 31 Aug 2001, Peter T. Breuer wrote:
>
> To give you all something definite to look at, here's some test code:

Hmm.. This might be a good idea, actually. Have you tried whether it finds
something in the existing tree (you could just take the existing macro and
ignore the first argument)?

This would definitely be acceptable to me, and should (assuming no gcc
optimization bugs) work with no run-time overhead.

Thanks,

		Linus

Re: [IDEA+RFC] Possible solution for min()/max() war

[Peter T. Breuer]

"A month of sundays ago Linus Torvalds wrote:"
> 
> On Fri, 31 Aug 2001, Peter T. Breuer wrote:
> >
> > To give you all something definite to look at, here's some test code:
> 
> Hmm.. This might be a good idea, actually. Have you tried whether it finds
> something in the existing tree (you could just take the existing macro and

Yes. I just tried it. The first warning thrown up for 2.4.8 was in
tun.c, when I did a make modules. Obviously it all depends on my
  .config as to what it finds!  I put in a asm(".error_here") instead of
BUG() so the compilation stops at every problem instead of warning and
continuing. Hence I don't kow the total. I can try and see ..

It's very late here (spain) so I don't trust myself to do much
hacking of code right now .. I corrected the tun.c code (it was
harmless) and posted the first bit of output a little while ago.
It should be down your mail client page a bit.

> ignore the first argument)?
> 
> This would definitely be acceptable to me, and should (assuming no gcc
> optimization bugs) work with no run-time overhead.


Peter

Re: [IDEA+RFC] Possible solution for min()/max() war

[Ion Badulescu]

On Thu, 30 Aug 2001 09:21:12 -0700 (PDT), Linus Torvalds <torvalds@transmeta.com> wrote:

> For example, let's look at this perfectly natural code:
> 
>        static int unix_mkname(struct sockaddr_un * sunaddr, int len, unsigned *hashp)
>        {
>                if (len <= sizeof(short) || len > sizeof(*sunaddr))
>                        return -EINVAL;
>                ...
> 
> Would you agree that the above is _good_ code, and code that makes
> perfect sense, and code that does exactly the right thing in testing its
> arguments?

Ugh. I must confess I am disappointed, Linus. I thought you had better taste.

Yes, the above code is correct. And yes, gcc should be more aggressive to
recognize that the above code is unambiguous. But that doesn't change the fact
that the code is UGLY AS HELL. Nor does it change the fact that each comparison
is broken if taken separately.

You make two UNSIGNED comparisons when you clearly mean to make two SIGNED
comparisons, and you call that _good_ code? Hmm.

> Try to compile it with -Wsign-compare.
> 
> You'll get not one, but TWO warnings for code that is totally correct, and
> that it would make _no_ sense in writing any other way.

Really? How so? We _know_ that the result of sizeof() fits confortably within
"int"'s range. So the natural way to write that comparison would be

	if (len <= (int) sizeof(short) || len > (int) sizeof(*sunaddr))

which is 100% correct, 100% obvious, and does not break horribly if you
remove one of the comparisons.

The compiler also _knows_ that. But the compiler can't change the implicit 
cast, because it would make it incompatible with every other compiler on
the planet. Yes, standards suck sometimes. So compiler warns us instead.
I consider that a feature.

Ion

-- 
  It is better to keep your mouth shut and be thought a fool,
            than to open it and remove all doubt.

Re: [IDEA+RFC] Possible solution for min()/max() war

[Linus Torvalds]

On Thu, 30 Aug 2001, Ion Badulescu wrote:
>
> Really? How so? We _know_ that the result of sizeof() fits confortably within
> "int"'s range. So the natural way to write that comparison would be
>
> 	if (len <= (int) sizeof(short) || len > (int) sizeof(*sunaddr))

You're so full of shit that it's incredible.

I'mnot going to argue this, when people call stuff like the above the
"natural way". This is not worth it.

The fact is, the way gcc currently does things, -Wsign-compare is useless.
Anybody who is honest would admit that. In order for the warning to become
useful, gcc would need to do value range analysis - which people have been
talking about, but which is not there yet.

There have been some constructive comments here (the automatic detection
of bad comparisons etc), but yours is just stupid.

		Linus

Re: [IDEA+RFC] Possible solution for min()/max() war

[Kai Henningsen]

phillips@bonn-fries.net (Daniel Phillips)  wrote on 30.08.01 in <20010830171934Z16012-32384+1116@humbolt.nl.linux.org>:

> On August 30, 2001 07:03 pm, Peter T. Breuer wrote:
> > "Daniel Phillips wrote:"
> > > More than anything, it shows that education is needed, not macro
> patch-ups.
> > > We have exactly the same issues with < and >, should we introduce
> > > three-argument macros to replace them?
> >
> > # define le(t,a,b) ({ t _a = a; t _b = b;  min(t,_a,_b) == _a ; })
> > # define ge(t,a,b) ({ t _a = a; t _b = b;  min(t,_a,_b) == _b ; })
>
> Oh, you are one sick puppy.
>
> For completeness:
>
> # define lt(t,a,b) ({ t _a = a; t _b = b;  min(t,_a,_b) != _b ; })
> # define gt(t,a,b) ({ t _a = a; t _b = b;  min(t,_a,_b) != _a ; })

Does it give the right answers for floating point?


MfG Kai

Re: [IDEA+RFC] Possible solution for min()/max() war

[Helge Hafting]

David Weinehall wrote:
> 
> On Thu, Aug 30, 2001 at 09:16:47PM +0000, Graham Murray wrote:
> > Daniel Phillips <phillips@bonn-fries.net> writes:
> >
> > > More than anything, it shows that education is needed, not macro patch-ups.
> > > We have exactly the same issues with < and >, should we introduce
> > > three-argument macros to replace them?
> >
> > Would it not have been much more "obvious" if the rules for
> > unsigned/signed integer comparisons (irrespective of the widths
> > involved) were
> >
> > 1) If the signed element is negative then it is always less than the
> >    unsigned element.
> >
> > 2) If the unsigned element is greater than then maximum positive value
> >    expressible by the signed one then it is always greater.
> >
> > 3) Only if both values are positive and within the range of the
> >    smaller element are the actual values compared.
> 
> Possibly, but changing the C specification is not really an option here...

Even worse: most microprosessors don't do comparisons that way.
They compare either two signed or two unsigned 
items and do that reasonably fast.  This is why C also works this way.

A compiler can be made to use the above standard, but it would generate
slow code for all signed/unsigned compares because now there is
3 tests instead of one.  This is why language designers don't do that.

You can of course do this explicitly in code if you need that
sort of comparison, e.g.

signed a;
unsigned b;
if (a<0) case1() 
   else if (b>MAX_SIGNED) case2()
   else if (a<b) case1() else case2();


A nice feature of C is that ugly time-consuming stuff tends to
look ugly and time-consuming in code too.  So it is easier
to avoid. :-)

Helge Hafting

Re: [IDEA+RFC] Possible solution for min()/max() war

[Roman Zippel]

Hi,

On Fri, 31 Aug 2001, Peter T. Breuer wrote:

>    if (sizeof(_x) != sizeof(_y)) \
>      MIN_BUG(); \

What bug are you trying to fix here?

> int main() {
>   unsigned i = 1;
>   signed j = -2;
>   return MIN(i,j);
> }

Try -Wsign-compare.

bye, Roman

Re: [IDEA+RFC] Possible solution for min()/max() war

[Peter T. Breuer]

"A month of sundays ago Roman Zippel wrote:"
> On Fri, 31 Aug 2001, Peter T. Breuer wrote:
> 
> >    if (sizeof(_x) != sizeof(_y)) \
> >      MIN_BUG(); \
> 
> What bug are you trying to fix here?

Wake up!

> > int main() {
> >   unsigned i = 1;
> >   signed j = -2;
> >   return MIN(i,j);
> > }
> 
> Try -Wsign-compare.

Wake up harder!

Try reading the last 10 days kernel messages. The last 48 hours are
particularly rewarding.

To be honest, nobody has precisely formulated the problem. I'll attempt
a quick summary of the most salient:

  C silently transforms signed int to unsigned int in cross-signed
  comparisons. This results in 1U < -2, and gives rise to all kinds
  of error paths from min/max codes (in particular, but they're not
  all) of the form

     min(unsigned_positive_constant, signed_ok_or_error_value)

  whose authors were expecting to get the error value out when the
  error value went in!

There are apparently more problems too, but nobody has explained them
to me in a manner that I can comprehend. I suspect that nobody knows
the full range of possible faults. I put in the size comparison
that you remarked upon so that people could tell me about it. Tell me
about it.

Linus wants possible mistakes flagged. He specifically does not want
-Wsign-compare because it apparently gives false positives.
  

Peter

Re: [IDEA+RFC] Possible solution for min()/max() war

[Jamie Lokier]

Linus Torvalds wrote:
> > 	if (len <= (int) sizeof(short) || len > (int) sizeof(*sunaddr))
> 
> You're so full of shit that it's incredible.
> 
> I'mnot going to argue this, when people call stuff like the above the
> "natural way". This is not worth it.

While I agree with Linus that the above line is ugly, there is a problem
with the original line:

    if (len <= sizeof(short) || len > sizeof(*sunaddr))

The problem?  Thinking this is natural, suppose you decide you only need
to check len against sizeof(short), perhaps here, perhaps copying this
idea to another part of the program:

    if (len <= sizeof(short))

_This_ code has a bug.  The comparison is unsigned; i.e. len is
converted to unsigned int first, so if the user passes a negative value,
the comparison returns false and the code will break.  It only works in
the original example because the second comparison checks the bogus
results of the first one.

Now, any later use of len should not lead to a buffer overflow or
anything, because you always check against a maximum size for copying,
yes?

No.  Consider this hypothetical code to copy things up to a page at a
time.  len is a signed type s.t. sizeof(len) <= sizeof(size_t):

   if (len <= sizeof(struct thing) || len > MAX_BUFFER_SIZE) {
           printk(KERN_ERR "Sanity check failed!\n");
           goto out;
   }
   memcpy (to, from, len);

Inexperienced C programmers, and sleepy ones, may not see the fault.

cheers,
-- Jamie

Re: [IDEA+RFC] Possible solution for min()/max() war

[Jamie Lokier]

Ion Badulescu wrote:
> So now you're turning it around. If you compare a long with unsigned char,
> there is no issue.

This is _not_ true.  What Linus said about long vs. unsigned int
depending on the architecture also applies to unsigned char, on those
old 32-bit Crays.  It is legitimate for unsigned char to have the same
size as signed long.

> If you compare long with unsigned int, you get the right result on the
> alpha and a warning on x86. If you compare long with unsigned long,
> you get a warning period.

Precisely.  Buggy code (read: architecture-specific bug) is written, and
the bug isn't noticed until somebody compiles that code on a different
architecture.  Far better to have GCC warn even on the alpha.

> And read above. You get the right result on the alpha and a warning on the 
> x86. I don't see the problem with that.
> 
> If you want to be 100% paranoid, change the sign-compare warning into an 
> error, so people don't ignore it. That's a much better alternative, and 
> gcc supports it.

See example with sizeof().  Something similar applies with PAGE_SIZE and
other unsigned constants.

> > Stating the type you compare in explicitly means that you do not get
> > surprised.
> 
> No. It means I suppress the gcc warning before I get a chance to see it. 

I have to agree with Ion here.  The explicit type is very helpful, but
if it reduces argument range, it masks a real bug.  Not that the old
macros were any better.  Ideally, there should be some way to get a
warning out of GCC when a bug is masked in this way.

This is what I see as the closest to ideal:

   1. min/max with type argument, as in new kernels.

   2. Warning added to GCC for casts which reduce argument range, but
      only when explicitly requested by an attribute on the cast...

   3. Warning added to GCC for signed vs. unsigned comparisons
      _regardless_ of type size.  This would also catch erroneous
      unsigned char vs. EOF checks in misuses of stdio.

      However, a type attribute must be provided to make the result of
      sizeof() not return a warning.  (size_t _should_ return a warning,
      though, so it is not that simple).

As you can see, at least the kernel part is done :)

-- Jamie

Re: [IDEA+RFC] Possible solution for min()/max() war

[Roman Zippel]

Hi,

On Fri, 31 Aug 2001, Peter T. Breuer wrote:

> > What bug are you trying to fix here?
>
> Wake up!

I'm trying.

> Try reading the last 10 days kernel messages. The last 48 hours are
> particularly rewarding.

I have, but I only get the feeling, we're hunting here for imaginary bugs.
Real bugs could be found with -Wsign-compare, but nobody wants to use it
because our master doesn't want it...
Please define the bugs first, you're trying to fix! If you don't like
-Wsign-compare, consider defining rules for the Stanford checker. This way
you can check all compares and not just the few uses of min.

>   C silently transforms signed int to unsigned int in cross-signed
>   comparisons. This results in 1U < -2, and gives rise to all kinds
>   of error paths from min/max codes (in particular, but they're not
>   all) of the form

Care to give an example? For the cases I tried gcc gave a warning.

> Linus wants possible mistakes flagged. He specifically does not want
> -Wsign-compare because it apparently gives false positives.

diff -u -r1.1.1.23 Makefile
--- Makefile	16 Aug 2001 20:50:22 -0000	1.1.1.23
+++ Makefile	31 Aug 2001 11:15:21 -0000
@@ -87,7 +87,11 @@

 CPPFLAGS := -D__KERNEL__ -I$(HPATH)

-CFLAGS := $(CPPFLAGS) -Wall -Wstrict-prototypes -Wno-trigraphs -O2 \
+WFLAGS := -Wall -Wstrict-prototypes -Wno-trigraphs
+ifdef CONFIG_EXTRA_WARNINGS
+WFLAGS := $(WFLAGS) -Wsign-compare
+endif
+CFLAGS := $(CPPFLAGS) $(WFLAGS) -O2 \
 	  -fomit-frame-pointer -fno-strict-aliasing -fno-common
 AFLAGS := -D__ASSEMBLY__ $(CPPFLAGS)

diff -u -r1.1.1.15 config.in
--- arch/i386/config.in	21 Jul 2001 12:48:20 -0000	1.1.1.15
+++ arch/i386/config.in	31 Aug 2001 11:12:56 -0000
@@ -390,4 +390,5 @@

 #bool 'Debug kmalloc/kfree' CONFIG_DEBUG_MALLOC
 bool 'Magic SysRq key' CONFIG_MAGIC_SYSRQ
+bool 'Extra compile warnings' CONFIG_EXTRA_WARNINGS
 endmenu
diff -u -r1.1.1.23 Configure.help
--- Documentation/Configure.help	16 Aug 2001 20:55:53 -0000	1.1.1.23
+++ Documentation/Configure.help	31 Aug 2001 11:21:10 -0000
@@ -15766,6 +15766,15 @@
   keys are documented in Documentation/sysrq.txt. Don't say Y unless
   you really know what this hack does.

+Extra compile warnings
+CONFIG_EXTRA_WARNINGS
+  If you say Y here, the compilation will generate lots of extra
+  warnings. Some of them warn about constructions that users generally
+  do not consider questionable, but which occasionally you might wish
+  to check for; others warn about constructions that are necessary or
+  hard to avoid in some cases, and there is no simple way to modify the
+  code to suppress the warning. Unless you look for bugs, say N.
+
 ISDN subsystem
 CONFIG_ISDN
   ISDN ("Integrated Services Digital Networks", called RNIS in France)

bye, Roman

Re: [IDEA+RFC] Possible solution for min()/max() war

[Peter T. Breuer]

"A month of sundays ago Linus Torvalds wrote:"
> 
> On Fri, 31 Aug 2001, Peter T. Breuer wrote:
> >
> > To give you all something definite to look at, here's some test code:
> 
> Hmm.. This might be a good idea, actually. Have you tried whether it finds
> something in the existing tree (you could just take the existing macro and
> ignore the first argument)?

I only have source for 2.4.8 plus xfs 1.0 patches here. 

I removed MIN/min/MAX/max definitions from about a dozen header files
in include/linux, and added an #include <linux/minmax.h> to them. That
file goes below. The test are fairly alarmist.

On doing a make bzImage no errors showed. On make modules, 4 errors
showed, one in tun.c and 3 in pagebuf_io.c (I presume that's from
xfs).

I probably covered about 25% of the kernel code in that trial.

The tun.c one was safe as it was .. the signed value was always
positive at the point where the macro was applied. I'm not
at all sure about the pagebuf_io.c ones because there was deep iovec
and iobuf and skb magic about,  but that's not of interest
to you. I made the comparisons signed and added an if (value out of
signed range) BUG(); just above.

The macros below seem to show up the line number perfectly in the
compiletime error. I guess one can add a __FILE__ to them someway.

One thing that worries me is that these should have triggered on
the signed/unsigned char comparisons that you were worried about in
-Wsigned-compare, and no, they didn't. They did find other
signed/unsigned mixes, but not char.

Peter



#ifndef MINMAX_H
#define MINMAX_H 1


#define __MINMAX_S(x) #x
#define MINMAX_S(x) __MINMAX_S(x)
#define MINMAX_BUG asm(".unsafe_min_or_max_at_line_" MINMAX_S(__LINE__))

#define __MIN(x,y) ({\
   typeof(x) _x = x; \
   typeof(y) _y = y; \
   _x < _y ? _x : _y ; \
 })
#define MIN(x,y) ({\
   const typeof(x) _x = ~(typeof(x))0; \
   const typeof(y) _y = ~(typeof(y))0; \
   if (sizeof(_x) != sizeof(_y)) \
     MINMAX_BUG; \
   if ((_x > (typeof(x))0 && _y < (typeof(y))0) \
   ||  (_x < (typeof(x))0 && _y > (typeof(y))0)) \
     MINMAX_BUG; \
   __MIN(x,y); \
 })
#define __MAX(x,y) ({\
   typeof(x) _x = x; \
   typeof(y) _y = y; \
   _x > _y ? _x : _y ; \
 })
#define MAX(x,y) ({\
   const typeof(x) _x = ~(typeof(x))0; \
   const typeof(y) _y = ~(typeof(y))0; \
   if (sizeof(_x) != sizeof(_y)) \
     MINMAX_BUG; \
   if ((_x > (typeof(x))0 && _y < (typeof(y))0) \
   ||  (_x < (typeof(x))0 && _y > (typeof(y))0)) \
     MINMAX_BUG; \
   __MAX(x,y); \
 })


#ifndef min
#define min(x,y) MIN(x,y)
#endif
#ifndef max
#define max(x,y) MAX(x,y)
#endif


#endif

Re: [IDEA+RFC] Possible solution for min()/max() war

[Peter T. Breuer]

"Roman Zippel wrote:"
> On Fri, 31 Aug 2001, Peter T. Breuer wrote:
> > Try reading the last 10 days kernel messages. The last 48 hours are
> > particularly rewarding.
> 
> I have, but I only get the feeling, we're hunting here for imaginary bugs.

As I said, nobody has been too precise about the bugs to me either! I
just want to provide an alternative to the 3arg min/max that would
otherwise have been imposed. Whether we really need either of these
alternatives is another argument.

> Real bugs could be found with -Wsign-compare, but nobody wants to use it
> because our master doesn't want it...
> Please define the bugs first, you're trying to fix! If you don't like
> -Wsign-compare, consider defining rules for the Stanford checker. This way

Stanford checker? Is that a programmable C type checker? If so, lemmee
at it. Have you a URL, btw?

Peter

Re: [IDEA+RFC] Possible solution for min()/max() war

[Roman Zippel]

Hi,

Jamie Lokier wrote:

>    2. Warning added to GCC for casts which reduce argument range, but
>       only when explicitly requested by an attribute on the cast...

How many false positives will this produce? I think, Linus will hate
this warning even more than -Wsign-compare.

>    3. Warning added to GCC for signed vs. unsigned comparisons
>       _regardless_ of type size.  This would also catch erroneous
>       unsigned char vs. EOF checks in misuses of stdio.

Do you know of such bug in the context of min()?

bye, Roman

Re: [IDEA+RFC] Possible solution for min()/max() war

[Linus Torvalds]

On Fri, 31 Aug 2001, Jamie Lokier wrote:
>
> While I agree with Linus that the above line is ugly, there is a problem
> with the original line:
>
>     if (len <= sizeof(short) || len > sizeof(*sunaddr))
>
> The problem?  Thinking this is natural, suppose you decide you only need
> to check len against sizeof(short), perhaps here, perhaps copying this
> idea to another part of the program:
>
>     if (len <= sizeof(short))
>
> _This_ code has a bug.

I agree.

The difference is subtle, and maybe too subtle.

The fact is, that _ranges_ are "stable" in different types. If a value "x"
is in the range [a,b] in type A, then it will also be in range [a,b] in
type B (assuming, of course, that 'a' and 'b' are valid values in both
types).

This is why range comparisons are different from normal comparisons.

But C doesn't have the notion of a range, which is why you can't write
(while lots of people have _tried_ to write, including in the kernel)

	a < x < b
or
	x in [a,b]

or similar. So you end up having to use a more "complex" setup, where the
individual parts might not be safe even though the totality is safe.

In fact, if gcc never becomes good enough to do that kind of range
checking, I won't be _too_ unhappy. I selected a special example on bad
grounds - it's not actually the most common case of range checking, and
the most common case by far tends to be something like

	if (len < 0)
		return -EINVAL;

	if (len > sizeof(buffer))
		len = sizeof(buffer);

	copy_from_user(buffer, ..., len);

where the operation is safe for _another_ range check reason, namely the
fact that we check that "len" is within the domain of the second check.

Right now gcc will complain about the second comparison, exactly because
gcc does not do range analysis.

Now, the good news is that gcc people have already worked on range
analysis, because it is very useful for other things too (not the least of
which is optimization). So I bet gcc _will_ be able to do a much better
job of this in the future, and if we have to help it by hand in only a few
places, then that will be a good thing.

However, right now gcc complains _way_ too much about perfectly valid and
good code. If it was a few small cases, I'd be happy to fix them in the
kernel. But last time I tried -Wsign-compare, the false positives were
just too damn numerous.

(Now, we may have fixed some of them anyway, and I haven't tried it in a
_loong_ time. If somebody decides to try to see what happens if you try to
clean them up, that would probably not be a bad idea per se. Proving me
wrong is always a good sport ;)

			Linus

Re: [IDEA+RFC] Possible solution for min()/max() war

[Linus Torvalds]

On Fri, 31 Aug 2001, Peter T. Breuer wrote:
>
> On doing a make bzImage no errors showed. On make modules, 4 errors
> showed, one in tun.c and 3 in pagebuf_io.c (I presume that's from
> xfs).
>
> I probably covered about 25% of the kernel code in that trial.

Good. This implies that the test itself is "reasonable and safe" - it
doesn't get nasty false positives, and assuming people en dup being happy
about it never causing surprising sign changes, I think this is a good
idea.

I _would_ suggest that you change the MIN_BUG() thing to the traditional

	#define compile_time_assert(x) \
		do { switch (0) { case 0: case (x) != 0: ; } } while (0)

which gives the error from the compiler, and does not depend on the
assembler.

(Admittedly the error message isn't the nicest in the world, but it gives
file and line number and include depth etc.. )

> The tun.c one was safe as it was .. the signed value was always
> positive at the point where the macro was applied.

Note that a _few_ false positives are fine - we can fix them up, and
people will be happy. The problems happen if the false positives are so
numerous that it makes common code uglier and harder to read because of
work-arounds for checkers.

So adding a cast or using an unsigned constant or whatever is fine.

> One thing that worries me is that these should have triggered on
> the signed/unsigned char comparisons that you were worried about in
> -Wsigned-compare, and no, they didn't. They did find other
> signed/unsigned mixes, but not char.

What I _really_ think might be interesting is a

	-Wsign-promote

warnign that hits outside compares (at any implicit promotion that
changes the sign - ie exactly the cases where K&R v1 and v2 differ), but I
suspect that it will have even _more_ problems than -Wsign-compare in the
sense that it probably really needs the compiler to do range analysis for
any amount of sane output..

		Linus

Re: [IDEA+RFC] Possible solution for min()/max() war

[Roman Zippel]

Hi,

"Peter T. Breuer" wrote:

> As I said, nobody has been too precise about the bugs to me either!

So let's be precise first! Please?
I've asked Linus about examples, so far I've seen only buggy
implementations of min() or an example, where min() shouldn't be used in
first place. Maybe I missed something, then I'm deeply sorry for this,
but all I want to know is, what are we fixing here?

> Stanford checker? Is that a programmable C type checker? If so, lemmee
> at it. Have you a URL, btw?

http://verify.stanford.edu/SVC/
You should search the archive to look for some good examples, how it can
help.

bye, Roman

Re: [IDEA+RFC] Possible solution for min()/max() war

[Peter T. Breuer]

"Roman Zippel wrote:"
> [ptb wrote]
> > Stanford checker? Is that a programmable C type checker? If so, lemmee
> > at it. Have you a URL, btw?
> 
> http://verify.stanford.edu/SVC/
> You should search the archive to look for some good examples, how it can
> help.

Hmm .. it looks like a model checker, and only for 1st order logic
(i.e. not CTL). It seems very primitive. What's the point of using this
instead of the many sphisticated model checkers and theorem provers out
there?

Peter

Re: [IDEA+RFC] Possible solution for min()/max() war

[Peter T. Breuer]

"A month of sundays ago Linus Torvalds wrote:"
> I _would_ suggest that you change the MIN_BUG() thing to the traditional
> 
> 	#define compile_time_assert(x) \
> 		do { switch (0) { case 0: case (x) != 0: ; } } while (0)
> 
> which gives the error from the compiler, and does not depend on the
> assembler.

OK. I did that here (inverting the logic from the if blah then bug form).
It goes just as well. Do you want this made up as a patch for 2.4.9?
Leaving code that thereby becomes non-compiling to its owner's tender
care?

What assertions on the types do you want, btw? People have been
saying that unequal size types are ok, and that it's just signed vs
unsigned that's the problem, and even then only when it's the longer
type that's unsigned and the shorter that's signed. I'd be inclined
to be paranoid and leave the alarms ringing when sizes or signs don't
match exactly.

> What I _really_ think might be interesting is a
> 
> 	-Wsign-promote
> 
> warnign that hits outside compares (at any implicit promotion that
> changes the sign - ie exactly the cases where K&R v1 and v2 differ), but I
> suspect that it will have even _more_ problems than -Wsign-compare in the

Peter

Re: [IDEA+RFC] Possible solution for min()/max() war

[Jamie Lokier]

Roman Zippel wrote:
> >    3. Warning added to GCC for signed vs. unsigned comparisons
> >       _regardless_ of type size.  This would also catch erroneous
> >       unsigned char vs. EOF checks in misuses of stdio.
> 
> Do you know of such bug in the context of min()?

I don't know of an actual example.  This one is made up:

       min (int, len, big_size)

Now if big_size has unsigned type, and does not fit in the range of int,
this expression will return the value of big_size cast to int, i.e. a
negative value.  The suggested warning would catch this potential bug.

I don't know if it would warn for too many other things.  Certainly, a
sizeof() exception (don't warn about signed comparison with sizeof()
result) is essential; perhaps too many other exceptions are required
too.

-- Jamie

Re: [IDEA+RFC] Possible solution for min()/max() war

[Roman Zippel]

Hi,

"Peter T. Breuer" wrote:

> Hmm .. it looks like a model checker, and only for 1st order logic
> (i.e. not CTL). It seems very primitive. What's the point of using this
> instead of the many sphisticated model checkers and theorem provers out
> there?

We already have good experience with it. Feel free to try something
else, the more the better.
Nevertheless you have to define the bug and its context first. The
problem with defining some fancy min macro is you have too little
information about the context, so you can mostly only restrict the use
of min, possibly preventing legal uses of it (signed/unsigned compare is
AFAIK the only exception).

bye, Roman

[PATCH] i386 SA_INTERRUPT logic

[Jonathan Lundell]

Herewith a patch to arch/i386/kernel/irq.c:handle_IRQ_event(). To 
belabor the obvious, the SA_INTERRUPT flag ought to affect just the 
handler it's set (or not) for. The existing code can enable 
interrupts for drivers that don't want them enabled, or disable them 
for drivers that do. We've done cursory testing, but can't test all 
possible cases; it looks straightforward enough, though.

I notice that this is fixed in alpha, broken in arm, cris, ia64, 
mips, ppc, sh. The respective architecture maintainers might like to 
have a closer look.



--- /usr/src/linux-2.4.9/arch/i386/kernel/irq.c	Wed Jun 20 11:06:38 2001
+++ irq.c	Fri Aug 31 14:29:11 2001
@@ -443,17 +443,16 @@

  	status = 1;	/* Force the "do bottom halves" bit */

-	if (!(action->flags & SA_INTERRUPT))
-		__sti();
-
  	do {
  		status |= action->flags;
+		if (!(action->flags & SA_INTERRUPT))
+			__sti();
  		action->handler(irq, action->dev_id, regs);
+		__cli();
  		action = action->next;
  	} while (action);
  	if (status & SA_SAMPLE_RANDOM)
  		add_interrupt_randomness(irq);
-	__cli();

  	irq_exit(cpu, irq);

-- 
/Jonathan Lundell.

Re: [IDEA+RFC] Possible solution for min()/max() war

[Bill Pringlemeir]

>>>>> Peter T Breuer <ptb@it.uc3m.es> writes:

  > To give you all something definite to look at, here's some test
  > code:


  > // standard good 'ol faithful version
  > #define __MIN(x,y) ({\
  >    typeof(x) _x = x; \
  >    typeof(y) _y = y; \
  >    _x < _y ? _x : _y ; \
  >  })

  > // possible implemetation with type sanity checks - alter to taste
  > #define MIN(x,y) ({\
  >    const typeof(x) _x = ~(typeof(x))0; \
  >    const typeof(y) _y = ~(typeof(y))0; \
  >    void MIN_BUG(); \
  >    if (sizeof(_x) != sizeof(_y)) \
  >      MIN_BUG(); \
  >    if ((_x > 0 && _y < 0) || (_x < 0 && _y > 0)) \
  >      MIN_BUG(); \
  >    __MIN(x,y); \
  >  })

[snip]

Sorry, I have been away for a while.  I think that I was talking about
a similar approach when Linus was away and David introduced the 3 arg
min/max.  I just went through 1800 LKML emails and I am not quite
clear what happened.  I have put my code that I posted earlier at the
end of this email.  This was the result of someone's `fanciful comment'
`what if gcc could handle "if(strcmp(typeof(a),typeof(b))!=0)"'.

So here is the important part.  The code Peter has introduced a cast
in the lines "const typeof(x) _x = ~(typeof(x))0;" etc.  I think that
the approach of declaring a variable of the type and initializing to
zero and then comparing "x - 1" _might_ be better.

The version of min() at the end calls the following an error, were
Peter's does not [after removing the sizeof() restriction].

 unsigned char Cx = 1; unsigned int Ix = 1; unsigned long  Lx = 1;
 Ix = min(Cx,Ix); Lx = min(Cx,Lx); 

Here the unsigned char is being promoted to int as discussed before.
I think that this is `more faithful' as what we are try to achieve is
to check the sign that will be used in the min comparison; almost
like applying a proper warned signed selectively to the min/max
macros.

Otherwise, I think we have independently came up with the same thing
and the `error' throwing can of course be changed to whatever.

fwiw,
Bill Pringlemeir.

[start code]

#define bug_paste_chain(a,b) a##b
#define bug_paste(a) bug_paste_chain(BUG_AT_LINE_,a)
#define min(x,y)                                       \
                                                       \
  ({extern void bug_paste(__LINE__) (void);            \
    typeof(x) _x = 0; typeof(y) _y = 0;                \
    if ((_x-1>0 && _y-1<0) || (_x-1<0 && _y-1>0))      \
            bug_paste(__LINE__)();                     \
        _x = (x), _y = (y); (_x>_y)?_y:_x;             \
   }) 

#include <stdio.h>
int main(int argc, char *argv[])
{
      signed char  cx = 1, cy = 2;
      signed short sx = 1, sy = 2;
      signed int   ix = 1, iy = 2;
      signed long  lx = 1, ly = 2;
    unsigned char  Cx = 1, Cy = 2;
    unsigned short Sx = 1, Sy = 2;
    unsigned int   Ix = 1, Iy = 2;
    unsigned long  Lx = 1, Ly = 2;

    cx = min(cx,cy);    Cx = min(Cy,Cx);    sx = min(sx,sy);
    Sx = min(Sx,Sy);    ix = min(iy,ix);    Ix = min(Iy,Ix);
    lx = min(ly,ly);    Lx = min(Lx,Ly);

    /* No warning. */
/*  Lx = (typeof(Lx))min(Lx,&Ly); */

    printf("%d %d %hd %hd %d %d %ld %ld\n", cx, Cx,
           sx,Sx,ix,Ix,lx,Lx);

    cx = -1;    Cx = 0;
    cx = min(cx,cy);    sx = min(cx,sy);
    ix = min(cx,ix);    lx = min(cx,ly);
    Cx = min(Cx,Cx);    Sx = min(Cx,Sy);
    Ix = min(Ly,Ix);    Lx = min(Ix,Ly);

    /* correctly gives warning! */
/*  Ix = min(Cy,Ix);    Lx = min(Cx,Ly); */

    printf("%d %d %hd %hd %d %d %ld %ld\n", cx, Cx,
           sx,Sx,ix,Ix,lx,Lx);

    min((unsigned)ix,sizeof(ix));
/* BUG? printf ("%d\n", min(Iy, 10)); */
    printf ("%d\n", min(cx, 20));

    printf("min(3,4,5) %d\n", min(min(5,4),3));
    
    return 0;
}
/* gcc -Wall -O2 -o test test.c */

[end code]

Re: [IDEA+RFC] Possible solution for min()/max() war

[Peter T. Breuer]

"A month of sundays ago Bill Pringlemeir wrote:"
>   > // possible implemetation with type sanity checks - alter to taste
>   > #define MIN(x,y) ({\
>   >    const typeof(x) _x = ~(typeof(x))0; \
>   >    const typeof(y) _y = ~(typeof(y))0; \
>   >    void MIN_BUG(); \
>   >    if (sizeof(_x) != sizeof(_y)) \
>   >      MIN_BUG(); \
>   >    if ((_x > 0 && _y < 0) || (_x < 0 && _y > 0)) \
>   >      MIN_BUG(); \
>   >    __MIN(x,y); \
>   >  })
> 
> min/max.  I just went through 1800 LKML emails and I am not quite
> clear what happened.  I have put my code that I posted earlier at the

The final version evoked a compile-time error instead of BUG(), and
also was more careful about the kind of zero it compares with! Linus
okayed it in principle and "real life" tests showed that it works
and catches what it's supposed to catch. For me it turned up one
kernel report (in tun.c) and three more in the xfs patches. The
trial covered about a quarter of the kernel.

Some people spotted that the error case can probably be reduced to
large signed versus small unsigned, both of size at least int.

> end of this email.  This was the result of someone's `fanciful comment'
> `what if gcc could handle "if(strcmp(typeof(a),typeof(b))!=0)"'.
> 
> So here is the important part.  The code Peter has introduced a cast
> in the lines "const typeof(x) _x = ~(typeof(x))0;" etc.  I think that
> the approach of declaring a variable of the type and initializing to
> zero and then comparing "x - 1" _might_ be better.

I don't know. I intended only to turn the sign bit on. I'm not sure how
1's complement arithmetic works, so I don't know if it works for 1's
complement arithmetic.

> The version of min() at the end calls the following an error, were
> Peter's does not [after removing the sizeof() restriction].
> 
>  unsigned char Cx = 1; unsigned int Ix = 1; unsigned long  Lx = 1;
>  Ix = min(Cx,Ix); Lx = min(Cx,Lx); 
> 
> Here the unsigned char is being promoted to int as discussed before.
> I think that this is `more faithful' as what we are try to achieve is

When someone states what the problem is exactly, and what portion
of it they want to test for, then the test can be modified to suit.
I intended to show that the test can be performed and a two
arg min thereby retained.

> to check the sign that will be used in the min comparison; almost
> like applying a proper warned signed selectively to the min/max
> macros.
> 
> Otherwise, I think we have independently came up with the same thing
> and the `error' throwing can of course be changed to whatever.

Probably!

Peter

Re: [IDEA+RFC] Possible solution for min()/max() war

[Peter T. Breuer]

"A month of sundays ago Bill Pringlemeir wrote:"
> Otherwise, I think we have independently came up with the same thing
> and the `error' throwing can of course be changed to whatever.

If you are interested, the last version I had is the following. The
compile_time_assert is linus' idea. We had an illegal assembler
statement there originally, containing the line number and the
error statement. One or the other will do until gcc gets the
__builtin_ct_assert() function.

#define compile_time_assert(x) \
                do { switch (0) { case 0: case (x) != 0: ; } } while (0)

#define __MIN(x,y) ({\
   typeof(x) _x = x; \
   typeof(y) _y = y; \
   _x < _y ? _x : _y ; \
 })
#define MIN(x,y) ({\
   const typeof(x) _x = ~(typeof(x))0; \
   const typeof(y) _y = ~(typeof(y))0; \
   compile_time_assert(sizeof(_x) == sizeof(_y));\
   compile_time_assert( (_x > (typeof(x))0 && _y > (typeof(y))0) \
                    ||  (_x < (typeof(x))0 && _y < (typeof(y))0)); \
   __MIN(x,y); \
 })

Peter

Re: [IDEA+RFC] Possible solution for min()/max() war

[Horst von Brand]

"Peter T. Breuer" <ptb@it.uc3m.es> said:

[...]

> I don't know. I intended only to turn the sign bit on. I'm not sure how
> 1's complement arithmetic works, so I don't know if it works for 1's
> complement arithmetic.

C's unsigned arithmetic is 2-complement. Never even seen a 1-complement
machine.
-- 
Dr. Horst H. von Brand                Usuario #22616 counter.li.org
Departamento de Informatica                     Fono: +56 32 654431
Universidad Tecnica Federico Santa Maria              +56 32 654239
Casilla 110-V, Valparaiso, Chile                Fax:  +56 32 797513

Re: [IDEA+RFC] Possible solution for min()/max() war

[Bill Pringlemeir]

>>>>> Peter T Breuer <ptb@it.uc3m.es> writes:

 > If you are interested, the last version I had is the
 > following. The compile_time_assert is linus' idea. We had an
 > illegal assembler statement there originally, containing the line
 > number and the error statement. One or the other will do until gcc
 > gets the __builtin_ct_assert() function.

   #define compile_time_assert(x) \
                   do { switch (0) { case 0: case (x) != 0: ; } } while (0)

   #define __MIN(x,y) ({\
      typeof(x) _x = x; \
      typeof(y) _y = y; \
      _x < _y ? _x : _y ; \
    })
   #define MIN(x,y) ({\
      const typeof(x) _x = ~(typeof(x))0; \
      const typeof(y) _y = ~(typeof(y))0; \
      compile_time_assert(sizeof(_x) == sizeof(_y));\
      compile_time_assert( (_x > (typeof(x))0 && _y > (typeof(y))0) \
                       ||  (_x < (typeof(x))0 && _y < (typeof(y))0)); \
      __MIN(x,y); \
    })

As Horst von Brand noted, most modern machines use 2's complement
arithmetic.  AFAIK, all the Linux targets use 2's complement.  The use
of ones complement, probably pre-dates MMUs.  At any rate, I think
that this might be a little clearer as sign, not complement is what is
being checked.

   #define MIN(x,y) ({\
      const typeof(x) _x = 0; \
      const typeof(y) _y = 0; \
      compile_time_assert(sizeof(_x) == sizeof(_y));\
      compile_time_assert( (_x - 1 > 0 && _y - 1 > 0) \
                       ||  (_x - 1 < 0 && _y - 1 < 0)); \
      __MIN(x,y); \
    })

This should prevent all cases where the __MIN(x,y) macro can screw up
due to sign issues (on that machine).  If you do this, the `sizeof'
check isn't needed.  A MIN(int, long) etc should probably be ok.  The
only caveats are the promotion in the __MIN itself create a sign
mismatch.

However, if the `sizeof' check remains, then you don't have to worry
about this and both versions are equivalent.  Some other things to
worry about is what if the type is already const?  Maybe that works...
What if you try `MIN(x,_x);'.  I think that this is something that
David took care of in the "3 arg min".

regards,
Bill Pringlemeir.

Re: [IDEA+RFC] Possible solution for min()/max() war

[Peter T. Breuer]

"Bill Pringlemeir wrote:"
>       compile_time_assert( (_x - 1 > 0 && _y - 1 > 0) \
>                        ||  (_x - 1 < 0 && _y - 1 < 0)); \
> 
> This should prevent all cases where the __MIN(x,y) macro can screw up
> due to sign issues (on that machine).  If you do this, the `sizeof'

Eh? "0" is a signed integer constant. So your comparisons force promotion
to int when x is smaller size. I'm not sure what type 

     "unsigned foo - signed int"

would have either!  It seems to me that you are making things very
murky, which is precisely what you want to avoid.

> check isn't needed.  A MIN(int, long) etc should probably be ok.  The
> only caveats are the promotion in the __MIN itself create a sign
> mismatch.
> 
> However, if the `sizeof' check remains, then you don't have to worry
> about this and both versions are equivalent.  Some other things to
> worry about is what if the type is already const?  Maybe that works...

No parsum.

> What if you try `MIN(x,_x);'.  I think that this is something that
> David took care of in the "3 arg min".

You can't take care of it. A macro is always vulnerable to name
clashes.


Peter

Re: [IDEA+RFC] Possible solution for min()/max() war

[Mark H. Wood]

On Fri, 7 Sep 2001, Horst von Brand wrote:
[quote snipped]
> C's unsigned arithmetic is 2-complement. Never even seen a 1-complement
> machine.

CDC big iron.  Seymour Cray found he could get a little more speed out of
his design that way.  IIRC SPSS on CDC gear used the -0 value to indicate
a missing case.

-- 
Mark H. Wood, Lead System Programmer   mwood@IUPUI.Edu
Make a good day.