Re: [PATCH] 2.4.22pre10: {,un}likely_p() macros for pointers

Re: [PATCH] 2.4.22pre10: {,un}likely_p() macros for pointers

[Albert Cahalan]

Chip Salzenberg writes:

> GCC is warning about a pointer-to-int conversion when
> the likely() and unlikely() macros are used with pointer
> values.  So, for architectures where pointers are larger
> than 'int', I suggest this patch.
...
> -#define likely(x) __builtin_expect((x),1)
> -#define unlikely(x) __builtin_expect((x),0)
> +#define likely(x) __builtin_expect((x),      1)
> +#define likely_p(x) __builtin_expect((x) != 0, 1)
> +#define unlikely(x) __builtin_expect((x)      ,0)
> +#define unlikely_p(x) __builtin_expect((x) != 0 ,0)

That's ugly, plus the "_p" suffix is kind of a
standard for "predicate". (__builtin_constant_p, etc.)

I'm using these in the procps project:

// tell gcc what to expect:   if(unlikely(err)) die(err);
#define likely(x)       __builtin_expect(!!(x),1)
#define unlikely(x)     __builtin_expect(!!(x),0)
#define expected(x,y)   __builtin_expect((x),(y))

That makes a slight change to the meaning, since the
original value is no longer available. I've not
found that to be any trouble at all; if it is then
you could work around it using a statement-expression
with a variable, cast, and/or __typeof__.

Something like this:

#define likely(x) ({   \
__typeof__ (x) _tmp;    \
__builtin_expect(!!_tmp,1); \
_tmp; \
})

Re: [PATCH] 2.4.22pre10: {,un}likely_p() macros for pointers

[Jamie Lokier]

Albert Cahalan wrote:
> // tell gcc what to expect:   if(unlikely(err)) die(err);
> #define likely(x)       __builtin_expect(!!(x),1)
> #define unlikely(x)     __builtin_expect(!!(x),0)
> #define expected(x,y)   __builtin_expect((x),(y))

You may want to check that GCC generates the same code as for

	#define likely(x)	__builtin_expect((x),1)
	#define unlikely(x)	__builtin_expect((x),0)

I tried this once, and I don't recall the precise result but I do
recall it generating different code (i.e. not optimal for one of the
definitions).

-- Jamie

Re: [PATCH] 2.4.22pre10: {,un}likely_p() macros for pointers

[Willy Tarreau]

On Sat, Aug 09, 2003 at 01:21:17AM +0100, Jamie Lokier wrote:
> Albert Cahalan wrote:
> > // tell gcc what to expect:   if(unlikely(err)) die(err);
> > #define likely(x)       __builtin_expect(!!(x),1)
> > #define unlikely(x)     __builtin_expect(!!(x),0)
> > #define expected(x,y)   __builtin_expect((x),(y))
> 
> You may want to check that GCC generates the same code as for
> 
> 	#define likely(x)	__builtin_expect((x),1)
> 	#define unlikely(x)	__builtin_expect((x),0)
> 
> I tried this once, and I don't recall the precise result but I do
> recall it generating different code (i.e. not optimal for one of the
> definitions).

anyway, in __builtin_expect(!!(x),0) there is a useless conversion, because
it's totally equivalent to __builtin_expect((x),0) (how could !!x be 0 if x
isn't ?), but I'm pretty sure that the compiler will add the test.

Willy

Re: [PATCH] 2.4.22pre10: {,un}likely_p() macros for pointers

[David S. Miller]

On Sat, 9 Aug 2003 10:13:46 +0200
Willy Tarreau <willy@w.ods.org> wrote:

> (how could !!x be 0 if x isn't ?)

I believe the C language allows for systems where the NULL pointer is
not zero.

I can't think of any reason why the NULL macro exists otherwise.

However, even if I'm right, I dread the guy who has to make other
people's code work on such a platform.  Using normal boolean tests for
NULL pointer checks is just too common.

Re: [PATCH] 2.4.22pre10: {,un}likely_p() macros for pointers

[Jamie Lokier]

David S. Miller wrote:
> On Sat, 9 Aug 2003 10:13:46 +0200 Willy Tarreau <willy@w.ods.org> wrote:
> 
> > (how could !!x be 0 if x isn't ?)
> 
> I believe the C language allows for systems where the NULL pointer is
> not zero.

That is irrelevant.  The GCC manual says you can't use a pointer as
the argument to __builtin_expect anyway:

     Since you are limited to integral expressions for EXP, you should
     use constructions such as

          if (__builtin_expect (ptr != NULL, 1))
            error ();

     when testing pointer or floating-point values

-- Jamie

Re: [PATCH] 2.4.22pre10: {,un}likely_p() macros for pointers

[Herbert Xu]

David S. Miller <davem@redhat.com> wrote:
> 
> I believe the C language allows for systems where the NULL pointer is
> not zero.

It does.  However it also says that whenever a pointer is compared
with the integer constant 0 it must be equal if and only if it is
a NULL pointer.

    An integer constant expression with the value 0, or such an expression
    cast to type void *, is called a null pointer constant.
-- 
Debian GNU/Linux 3.0 is out! ( http://www.debian.org/ )
Email:  Herbert Xu ~{PmV>HI~} <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH] 2.4.22pre10: {,un}likely_p() macros for pointers

[Alan Cox]

On Sad, 2003-08-09 at 09:51, David S. Miller wrote:
> I believe the C language allows for systems where the NULL pointer is
> not zero.

Its a fudge for some systems. However NULL == 0 is always true.

> I can't think of any reason why the NULL macro exists otherwise.

<OldFart>
NULL is really important in K&R C because you don't have prototypes and
sizeof(foo *) may not be the same as sizeof(int). This leads to very
nasty problems that people nowdays forget about.
</OldFart>

Re: [PATCH] 2.4.22pre10: {,un}likely_p() macros for pointers

[Jamie Lokier]

Alan Cox wrote:
> > I believe the C language allows for systems where the NULL pointer is
> > not zero.

The representation is not zero, however in the C language (since ANSI,
not sure about K&R), 0 is a valid name for the NULL pointer whatever
its representation.

> > I can't think of any reason why the NULL macro exists otherwise.
> 
> <OldFart>
> NULL is really important in K&R C because you don't have prototypes and
> sizeof(foo *) may not be the same as sizeof(int). This leads to very
> nasty problems that people nowdays forget about.
> </OldFart>

Not just K&R.  These are different because of varargs:

	printf ("%p", NULL);
	printf ("%p", 0);

-- Jamie

NULL. Again. (was Re: [PATCH] 2.4.22pre10: {,un}likely_p())

[Chip Salzenberg]

According to Jamie Lokier:
> Not just K&R.  These are different because of varargs:
> 	printf ("%p", NULL);
> 	printf ("%p", 0);

*SIGH*  I thought incorrect folk wisdom about NULL and zero and pointer
conversions had long since died out.  More fool I.  Please, *please*,
_no_one_else_ argue about NULL/zero/false etc. until after reading this:

  ===[[  http://www.eskimo.com/~scs/C-faq/s5.html  ]]===

I thank you, and linux users everywhere thank you.
-- 
Chip Salzenberg               - a.k.a. -               <chip@pobox.com>
"I wanted to play hopscotch with the impenetrable mystery of existence,
    but he stepped in a wormhole and had to go in early."  // MST3K

Re: NULL. Again. (was Re: [PATCH] 2.4.22pre10: {,un}likely_p())

[Sean Neakums]

Chip Salzenberg <chip@pobox.com> writes:

> According to Jamie Lokier:
>> Not just K&R.  These are different because of varargs:
>> 	printf ("%p", NULL);
>> 	printf ("%p", 0);
>
> *SIGH*  I thought incorrect folk wisdom about NULL and zero and pointer
> conversions had long since died out.  More fool I.  Please, *please*,
> _no_one_else_ argue about NULL/zero/false etc. until after reading this:
>
>   ===[[  http://www.eskimo.com/~scs/C-faq/s5.html  ]]===
>
> I thank you, and linux users everywhere thank you.

I had thought that the need for writing NULL where a pointer is
expected in varags functions was because the machine may have
different sizes for pointers and int.  In the case of the second
printf call above, if pointers are 64-bit and integers are 32-bit,
printf will read eight bytes from the stack, and only four will have
been occupied by the integer 0.

Re: NULL. Again. (was Re: [PATCH] 2.4.22pre10: {,un}likely_p())

[Jamie Lokier]

Chip Salzenberg wrote:
> According to Jamie Lokier:
> > Not just K&R.  These are different because of varargs:
> > 	printf ("%p", NULL);
> > 	printf ("%p", 0);
> 
> *SIGH*  I thought incorrect folk wisdom about NULL and zero and pointer
> conversions had long since died out.  More fool I.  Please, *please*,
> _no_one_else_ argue about NULL/zero/false etc. until after reading this:
> 
>   ===[[  http://www.eskimo.com/~scs/C-faq/s5.html  ]]===

Thanks Chip; I am much enlightened.  That is a fine URL.

To onlookers: neither of those printf statements is portable :)

-- Jamie

Re: NULL. Again. (was Re: [PATCH] 2.4.22pre10: {,un}likely_p())

[Jamie Lokier]

Sean Neakums wrote:
> I had thought that the need for writing NULL where a pointer is
> expected in varags functions was because the machine may have
> different sizes for pointers and int.  In the case of the second
> printf call above, if pointers are 64-bit and integers are 32-bit,
> printf will read eight bytes from the stack, and only four will have
> been occupied by the integer 0.

It is incorrect to write NULL as a varargs argument.  It won't
necessarily pass a pointer because:

   1. a valid definition of NULL is "0".

If you want to pass a pointer to varargs, you might have considered
writing "(void *) 0", but that doesn't work because:

   2. a machine may have different sizes for different pointer types.

You must write "(type) 0" or "(type) NULL", using the correct pointer type.

-- Jamie

Re: NULL. Again. (was Re: [PATCH] 2.4.22pre10: {,un}likely_p())

[Timothy Miller]

Sean Neakums wrote:
> Chip Salzenberg <chip@pobox.com> writes:
> 
> 
>>According to Jamie Lokier:
>>
>>>Not just K&R.  These are different because of varargs:
>>>	printf ("%p", NULL);
>>>	printf ("%p", 0);
>>
>>*SIGH*  I thought incorrect folk wisdom about NULL and zero and pointer
>>conversions had long since died out.  More fool I.  Please, *please*,
>>_no_one_else_ argue about NULL/zero/false etc. until after reading this:
>>
>>  ===[[  http://www.eskimo.com/~scs/C-faq/s5.html  ]]===
>>
>>I thank you, and linux users everywhere thank you.
> 
> 
> I had thought that the need for writing NULL where a pointer is
> expected in varags functions was because the machine may have
> different sizes for pointers and int.  In the case of the second
> printf call above, if pointers are 64-bit and integers are 32-bit,
> printf will read eight bytes from the stack, and only four will have
> been occupied by the integer 0.
> 

Yes, but you're leaving information out.  If you read the FAQ, you'll 
find that NULL would not be the right thing to use in some cases.  For 
instance, (char *)0 may be a different value from (void *)0, so it's 
best to cast the pointer when passing to printf or something which uses 
varargs.

Re: [PATCH] 2.4.22pre10: {,un}likely_p() macros for pointers

[Jamie Lokier]

Albert Cahalan wrote:
> > Being a simple soul, I prefer __builtin_expect((x) != 0, 1).
> 
> That's much harder to read. The !! is a nice
> neat idiom. The other way requires a bit of thought.
> (is that == or !=, a 0 or 1, and what does that
> compute to?)
> 
> The !! is visually distinctive. It has only one use.
> When you see it, you instantly know that a value is
> being converted to the pure boolean form.

Dear Albert,

I have to tell you your are totally wrong :)

Most C programmers will find "!!x" less clear than "x != 0", simply
because "!!x" isn't used all that much.

If you require significant thought to parse "x != 0" you are going to
have trouble with more complex idioms.

Like "x && 1" and "x || 0", which are obvious to anyone :)

-- Jamie

Re: [PATCH] 2.4.22pre10: {,un}likely_p() macros for pointers

[Albert Cahalan]

On Mon, 2003-08-11 at 14:55, Andrew Morton wrote:
> Albert Cahalan <albert@users.sourceforge.net> wrote:
> >
> > -#define likely(x)	__builtin_expect((x),1)
> > -#define unlikely(x)	__builtin_expect((x),0)
> > +#define likely(x)	__builtin_expect(!!(x),1)
> > +#define unlikely(x)	__builtin_expect(!!(x),0)
> 
> Odd.  I thought we fixed that ages ago.
> 
> Being a simple soul, I prefer __builtin_expect((x) != 0, 1).

That's much harder to read. The !! is a nice
neat idiom. The other way requires a bit of thought.
(is that == or !=, a 0 or 1, and what does that
compute to?)

The !! is visually distinctive. It has only one use.
When you see it, you instantly know that a value is
being converted to the pure boolean form.

Re: [PATCH] 2.4.22pre10: {,un}likely_p() macros for pointers

[Andrew Morton]

Albert Cahalan <albert@users.sourceforge.net> wrote:
>
> -#define likely(x)	__builtin_expect((x),1)
> -#define unlikely(x)	__builtin_expect((x),0)
> +#define likely(x)	__builtin_expect(!!(x),1)
> +#define unlikely(x)	__builtin_expect(!!(x),0)

Odd.  I thought we fixed that ages ago.

Being a simple soul, I prefer __builtin_expect((x) != 0, 1).

Re: [PATCH] 2.4.22pre10: {,un}likely_p() macros for pointers

[Albert Cahalan]

On Mon, 2003-08-11 at 01:42, Jamie Lokier wrote:
> Willy Tarreau wrote:
> > So in any case, the !!(x) construct should be valid.
> 
> Yes, either of these is fine for pointers and integers alike:
> 
> 	#define likely(x)	__builtin_expect ((x) != 0, 1)
> 	#define unlikely(x)	__builtin_expect ((x) != 0, 0)
> 
> 	#define likely(x)	__builtin_expect (!!(x), 1)
> 	#define unlikely(x)	__builtin_expect (!!(x), 0)

Choosing the more familiar idiom for booleanizing a value, here we go:

diff -Naurd old/include/linux/compiler.h new/include/linux/compiler.h
--- old/include/linux/compiler.h	2003-08-11 09:02:18.000000000 -0400
+++ new/include/linux/compiler.h	2003-08-11 09:04:58.000000000 -0400
@@ -24,8 +24,8 @@
 #define __builtin_expect(x, expected_value) (x)
 #endif
 
-#define likely(x)	__builtin_expect((x),1)
-#define unlikely(x)	__builtin_expect((x),0)
+#define likely(x)	__builtin_expect(!!(x),1)
+#define unlikely(x)	__builtin_expect(!!(x),0)
 
 /*
  * Allow us to mark functions as 'deprecated' and have gcc emit a nice

Re: [PATCH] 2.4.22pre10: {,un}likely_p() macros for pointers

[Jamie Lokier]

Willy Tarreau wrote:
> So in any case, the !!(x) construct should be valid.

Yes, either of these is fine for pointers and integers alike:

	#define likely(x)	__builtin_expect ((x) != 0, 1)
	#define unlikely(x)	__builtin_expect ((x) != 0, 0)

	#define likely(x)	__builtin_expect (!!(x), 1)
	#define unlikely(x)	__builtin_expect (!!(x), 0)

-- Jamie

Re: [PATCH] 2.4.22pre10: {,un}likely_p() macros for pointers

[Jamie Lokier]

Willy Tarreau wrote:
> It may well be when you use it in boolean constructs. The following functions
> return exactly the same result with different code :
> 
> int test1(int u, int v, int x, int y) {
>    return (u > v) || (x > y);
> }
> 
> int test2(int u, int v, int x, int y) {
>    return !!(u > v) | !!(x > y);
> }

Yes, it sounds familiar.  Although my code was not as contrived :) it
was from a real program.  Also, try "x != 0" instead of "!!x" and see
if you get different results.

-- Jamie

Re: [PATCH] 2.4.22pre10: {,un}likely_p() macros for pointers

[Willy Tarreau]

On Sun, Aug 10, 2003 at 10:39:12PM -0400, Chip Salzenberg wrote:
 
> Both parameters of __builtin_expect() are long ints.  On an
> architecture where there's a pointer type larger than long[1],
> __builtin_expect() won't just warn, it'll *fail*.  Also, on an
> architecture where a conversion of a null pointer to long results in
> a non-zero value[2], it'll *fail*.  That makes it non-portable twice
> over.  Wouldn't you agree?

Hmmm Chip, on the document you suggested us to read, I remember a statement
about (!x) <=> (x == 0) which implied it's legal even if x is a pointer because
the compiler will automatically do the comparison between x and NULL and not
(int)x and 0. Perhaps I have dreamed, but I'm sure I read this. So in any case,
the !!(x) construct should be valid.

Cheers,
Willy

Re: [PATCH] 2.4.22pre10: {,un}likely_p() macros for pointers

[Willy Tarreau]

On Mon, Aug 11, 2003 at 05:55:31AM +0100, Jamie Lokier wrote:
> Willy Tarreau wrote:
> > > I looked at the assembly (ppc, gcc 3.2.3) and didn't
> > > see any overhead.
> > 
> > same here on x86, gcc-2.95.3 and gcc-3.3.1. The compiler is smart enough not
> > to add several intermediate tests for !!(x).
> 
> What I recall is no additional tests, but the different forms affected
> the compilers choice of instructions on x86, making one form better
> than another.  Unfortunately I don't recall what that was, or what
> test it showed up in :(

It may well be when you use it in boolean constructs. The following functions
return exactly the same result with different code :

int test1(int u, int v, int x, int y) {
   return (u > v) || (x > y);
}

int test2(int u, int v, int x, int y) {
   return !!(u > v) | !!(x > y);
}

test1() uses 2 jumps on x86 while test2 uses only test-and-set and should be
faster. This also allows to easily write the boolean XOR BTW :

int test3(int u, int v, int x, int y) {
   return !!(u > v) ^ !!(x > y);
}

Cheers,
Willy

Re: [PATCH] 2.4.22pre10: {,un}likely_p() macros for pointers

[Jamie Lokier]

Willy Tarreau wrote:
> > I looked at the assembly (ppc, gcc 3.2.3) and didn't
> > see any overhead.
> 
> same here on x86, gcc-2.95.3 and gcc-3.3.1. The compiler is smart enough not
> to add several intermediate tests for !!(x).

What I recall is no additional tests, but the different forms affected
the compilers choice of instructions on x86, making one form better
than another.  Unfortunately I don't recall what that was, or what
test it showed up in :(

> I agree (I didn't think about pointers, BTW). But what I meant is that we
> don't need the result to be precisely 1, but we need it to be something the
> compiler interpretes as different from zero, to match the condition. So it
> should be cleaner to always check against 0 which is also OK for pointers,
> whatever their type (according to Chip's link) :
> 
>   likely => __builtin_expect(!(x), 0)

This will break "if (likely(p)) { ... }"

> unlikely => __builtin_expect((x), 0)

This will give a warning with "if (unlikely(p)) { ... }"

-- Jamie

Re: [PATCH] 2.4.22pre10: {,un}likely_p() macros for pointers

[Jamie Lokier]

Chip Salzenberg wrote:
> > It's portable as long as the compiler is GCC :)
> No; wrong; please pay attention.

I was being facetious :)

> Both parameters of __builtin_expect() are long ints.

So it is broken if passed a "long long"?  The documentation says "you
are limited to integral expressions".

...You're right.  The documentation is wrong.  It's strictly takes
"long int" arguments and returns a long.

> On an architecture where there's a pointer type larger than long[1],
> __builtin_expect() won't just warn, it'll *fail*.

A pointer really should fail on all architectures.
Fortunately you do get a warning.

> Also, on an architecture where a conversion of a null pointer to
> long results in a non-zero value[2], it'll *fail*.  That makes it
> non-portable twice over.  Wouldn't you agree?

[2] - I don't believe such architectures are supported by GCC, hence
the facetious comment.

>    Since you are limited to integral expressions for exp, you should use constructions such as
> 
>         if (__builtin_expect (ptr != NULL, 1))
>           error ();
> 
>    when testing pointer or floating-point values.

I think we all agree with this.

-- Jamie

Re: [PATCH] 2.4.22pre10: {,un}likely_p() macros for pointers

[Albert Cahalan]

On Sun, 2003-08-10 at 22:39, Chip Salzenberg wrote:
> According to Jamie Lokier:
> > Chip Salzenberg wrote:
> > > According to Willy Tarreau:
> > > >   likely => __builtin_expect(!(x), 0)
> > > > unlikely => __builtin_expect((x), 0)
> > > 
> > > Well, I'm not sure about the polarity, but that unlikely() macro isn't
> > > good -- it the same old problem that first prompted my message, namely
> > > that it's nonportable when (x) has a pointer type.
> > 
> > It's portable as long as the compiler is GCC :)
> 
> No; wrong; please pay attention.
> 
> Both parameters of __builtin_expect() are long ints.

They are, so you must do something to convert
pointers into integers.

>   On an
> architecture where there's a pointer type larger than long[1],

Linux will absolutely not work in this case.
(No way, never, no can do, end of story, & give up now)

When you port to Win64 and MS-DOS "huge" model,
you can consider this problem.

You do realize that __builtin_expect() is a
non-portable gcc extension, don't you?

> __builtin_expect() won't just warn, it'll *fail*.  Also, on an
> architecture where a conversion of a null pointer to long results in
> a non-zero value[2], it'll *fail*.

I once worked on an OS for such a machine.
We used the word-addressed SHARC DSP with a
hacked-up gcc to allow for byte pointers.
Casting was a nightmare. Once again:

Linux will absolutely not work in this case.
(No way, never, no can do, end of story, & give up now)

> That makes it non-portable twice
> over.  Wouldn't you agree?
> 
> Allow me to quote gcc's documentation:
> 
>    Since you are limited to integral expressions for exp, you should use constructions such as
> 
>         if (__builtin_expect (ptr != NULL, 1))
>           error ();
> 
>    when testing pointer or floating-point values.
> 
> Could you please believe the docs?

No, because NULL could be "(void*)0". This would
make the unlikely() macro fail for integers!
Change that NULL to a 0 and it might be OK though.

The procps code works great:

#define likely(x)       __builtin_expect(!!(x),1)
#define unlikely(x)     __builtin_expect(!!(x),0)

The goal is to turn any pointer or integer type
into a plain 0 or 1, so that the input can match
the constants provided in the macro. We like the
double "!" for ease of use.

The ?: operator could be used, but !! is a nice
idiom for booleanizing a value.

At this point, I might as well post my rules for
semi-portable code. News flash: Linux isn't completely
portable, and we don't care! In theory, theory and
practice are the same, but in practice they are not.
(whereupon Larry McVoy will flame me I'm sure)
Some of you may remember this from June 2000; it's
been patched a bit to cut down on confusion.

--------------- the rules -----------------

In anticipation of flames, I have the damn 1999 ISO C draft.
I know full well that a "legal" compiler can put 42 chars of
padding after everything and, just for fun, make every type
be 101 bits wide.

Moderately portable code assumes a sane compiler and sane hardware.
You may assume:

1. The "char" type is 8 bits. It might be unsigned though. :-/
2. sizeof(short) == 2
3. sizeof(int) == 4      (for real Linux, not the 8088 hack)
4. sizeof(long) == sizeof(void *)
5. (sizeof(long) == 4) | (sizeof(long) == 8)
6. sizeof(long long) == 8       (good for 10 years at least)
7. You can freely cast between any two pointer types [note #1]
8. You can freely cast between long and any pointer type
9. (long)(int*)(long)foo == (long)(char*)(int*)(long)foo
10. signed integers are represented in two's complement form
11. all integers wrap around instead of causing faults
12. assuming "good" struct layout, padding only occurs at the end
13. ... that padding won't happen if you supply a multiple of 16 bytes
14. The binary representation of NULL is all zero bits
15. The hardware is either big-endian or little-endian.
16. Assignment to "int", "long" or a pointer is atomic

Note #1: I only said you could do the cast. That is,
you won't get an exception during the cast. You should
still satisfy alignment requirements... although Linux
supposedly has exception handlers to hide the problem
in kernel code. You'll also need to be aware of type
aliasing, unless the cast involves (char*) or you specify
-fno-strict-aliasing as the kernel build system does.

One can define "good" struct layout as being an order that puts
items with the largest natural alignments first. For example, an
array of 6 shorts has a natural alignment of 4 bytes. I suppose
you could define natural alignment as gcd(16,sizeof(foo)).

I used to work with a system that violates rule 9.
>From experience, I assure you that it is a mess to deal with.
Casting gets really nasty. There is no hope of porting Linux
to this system.

Compiler wish list:

1. -Wstruct-padding    warn if compiler added padding
2. __bag__             like a struct, but the compiler chooses order

(and no, -Wpadded isn't good; padding at the end of a
struct or added with __attribute__ should only cause a
warning when sizeof is used, if even then, and the compiler
shouldn't spew warnings about its own built-in structures)
--------------------------------------------------------

Re: [PATCH] 2.4.22pre10: {,un}likely_p() macros for pointers

[Chip Salzenberg]

According to Jamie Lokier:
> Chip Salzenberg wrote:
> > According to Willy Tarreau:
> > >   likely => __builtin_expect(!(x), 0)
> > > unlikely => __builtin_expect((x), 0)
> > 
> > Well, I'm not sure about the polarity, but that unlikely() macro isn't
> > good -- it the same old problem that first prompted my message, namely
> > that it's nonportable when (x) has a pointer type.
> 
> It's portable as long as the compiler is GCC :)

No; wrong; please pay attention.

Both parameters of __builtin_expect() are long ints.  On an
architecture where there's a pointer type larger than long[1],
__builtin_expect() won't just warn, it'll *fail*.  Also, on an
architecture where a conversion of a null pointer to long results in
a non-zero value[2], it'll *fail*.  That makes it non-portable twice
over.  Wouldn't you agree?

Allow me to quote gcc's documentation:

   Since you are limited to integral expressions for exp, you should use constructions such as

        if (__builtin_expect (ptr != NULL, 1))
          error ();

   when testing pointer or floating-point values.

Could you please believe the docs?

[1] Yes, they exit.
[2] I don't know if they exist, but they're allowed by ANSI C.
-- 
Chip Salzenberg               - a.k.a. -               <chip@pobox.com>
"I wanted to play hopscotch with the impenetrable mystery of existence,
    but he stepped in a wormhole and had to go in early."  // MST3K

Re: [PATCH] 2.4.22pre10: {,un}likely_p() macros for pointers

[Jamie Lokier]

Chip Salzenberg wrote:
> According to Willy Tarreau:
> >   likely => __builtin_expect(!(x), 0)
> > unlikely => __builtin_expect((x), 0)
> 
> Well, I'm not sure about the polarity, but that unlikely() macro isn't
> good -- it the same old problem that first prompted my message, namely
> that it's nonportable when (x) has a pointer type.

It's portable as long as the compiler is GCC :)

-- Jamie

Re: [PATCH] 2.4.22pre10: {,un}likely_p() macros for pointers

[Chip Salzenberg]

According to Willy Tarreau:
>   likely => __builtin_expect(!(x), 0)
> unlikely => __builtin_expect((x), 0)

Well, I'm not sure about the polarity, but that unlikely() macro isn't
good -- it the same old problem that first prompted my message, namely
that it's nonportable when (x) has a pointer type.
-- 
Chip Salzenberg               - a.k.a. -               <chip@pobox.com>
"I wanted to play hopscotch with the impenetrable mystery of existence,
    but he stepped in a wormhole and had to go in early."  // MST3K

Re: [PATCH] 2.4.22pre10: {,un}likely_p() macros for pointers

[Willy Tarreau]

On Sun, Aug 10, 2003 at 09:29:45AM +0200, Willy Tarreau wrote:
>   likely => __builtin_expect(!(x), 0)

hmmm silly me, forget it, it will return the opposite. We should use !!(x),1.

Willy

Re: [PATCH] 2.4.22pre10: {,un}likely_p() macros for pointers

[Willy Tarreau]

Hi Albert,

On Sun, Aug 10, 2003 at 12:03:54AM -0400, Albert Cahalan wrote:
> I looked at the assembly (ppc, gcc 3.2.3) and didn't
> see any overhead.

same here on x86, gcc-2.95.3 and gcc-3.3.1. The compiler is smart enough not
to add several intermediate tests for !!(x).
 
> The !!x gives you a 0 or 1 while converting the type.
> So a (char*)0xfda9c80300000000ull will become a 1 of
> an acceptable type, allowing the macro to work as desired.

I agree (I didn't think about pointers, BTW). But what I meant is that we
don't need the result to be precisely 1, but we need it to be something the
compiler interpretes as different from zero, to match the condition. So it
should be cleaner to always check against 0 which is also OK for pointers,
whatever their type (according to Chip's link) :

  likely => __builtin_expect(!(x), 0)
unlikely => __builtin_expect((x), 0)

Cheers,
Willy

Re: [PATCH] 2.4.22pre10: {,un}likely_p() macros for pointers

[Albert Cahalan]

Willy Tarreau writes:
>On Sat, Aug 09, 2003 at 01:21:17AM +0100, Jamie Lokier wrote:
>> Albert Cahalan wrote:

>>> // tell gcc what to expect:   if(unlikely(err)) die(err);
>>> #define likely(x)       __builtin_expect(!!(x),1)
>>> #define unlikely(x)     __builtin_expect(!!(x),0)
>>> #define expected(x,y)   __builtin_expect((x),(y))
>>
>> You may want to check that GCC generates the same code as for
>>
>>  #define likely(x) __builtin_expect((x),1)
>>  #define unlikely(x) __builtin_expect((x),0)
>>
>> I tried this once, and I don't recall the precise result
>> but I do recall it generating different code (i.e. not
>> optimal for one of the definitions).

I looked at the assembly (ppc, gcc 3.2.3) and didn't
see any overhead.

Note that the kernel code is broken for the likely()
macro, since 42 is a perfectly good truth value in C.

> anyway, in __builtin_expect(!!(x),0) there is a useless
> conversion, because it's totally equivalent to
> __builtin_expect((x),0) (how could !!x be 0 if x isn't ?),
> but I'm pretty sure that the compiler will add the test.

The !!x gives you a 0 or 1 while converting the type.
So a (char*)0xfda9c80300000000ull will become a 1 of
an acceptable type, allowing the macro to work as desired.

[PATCH] 2.4.22pre10: {,un}likely_p() macros for pointers

[Chip Salzenberg]

GCC is warning about a pointer-to-int conversion when the likely() and
unlikely() macros are used with pointer values.  So, for architectures
where pointers are larger than 'int', I suggest this patch.

PS: This patch was made against 2.4.22pre10 plus many patches from the
'aa' kernel series, so it should be considered an example of the patch
that might be required in other kernel versions.

Index: linux/include/linux/compiler.h
--- linux/include/linux/compiler.h.old	2001-09-18 17:12:45.000000000 -0400
+++ linux/include/linux/compiler.h	2003-08-04 12:24:15.000000000 -0400
@@ -11,6 +11,8 @@
 #endif
 
-#define likely(x)	__builtin_expect((x),1)
-#define unlikely(x)	__builtin_expect((x),0)
+#define likely(x)	__builtin_expect((x),      1)
+#define likely_p(x)	__builtin_expect((x) != 0, 1)
+#define unlikely(x)	__builtin_expect((x)      ,0)
+#define unlikely_p(x)	__builtin_expect((x) != 0 ,0)
 
 #endif /* __LINUX_COMPILER_H */

Index: linux/kernel/sched.c
--- linux/kernel/sched.c.old	2003-08-04 12:09:47.000000000 -0400
+++ linux/kernel/sched.c	2003-08-04 12:25:44.000000000 -0400
@@ -477,5 +477,5 @@
 	if (unlikely(!prev->mm)) {
 		prev->active_mm = NULL;
-		if (unlikely(rq->prev_mm)) {
+		if (unlikely_p(rq->prev_mm)) {
 			printk(KERN_ERR "rq->prev_mm was %p set to %p - %s\n", rq->prev_mm, oldmm, current->comm);
 			dump_stack();

Index: linux/mm/filemap.c
--- linux/mm/filemap.c.old	2003-08-04 12:09:41.000000000 -0400
+++ linux/mm/filemap.c	2003-08-04 12:27:07.000000000 -0400
@@ -3749,5 +3749,5 @@
 		pr_debug("attempting to read %lu\n", page->index);
 		io->did_read = 1;
-		if (likely(page->mapping)) {
+		if (likely_p(page->mapping)) {
 			locked = 0;
 			io->err = page->mapping->a_ops->readpage(io->file, page);
@@ -3813,5 +3813,5 @@
 		 */
 		if (!TryLockPage(page)) {
-			if (likely(page->mapping)) {
+			if (likely_p(page->mapping)) {
 				int ret = readpage(io->file, page);
 				if (ret)



-- 
Chip Salzenberg               - a.k.a. -               <chip@pobox.com>
"I wanted to play hopscotch with the impenetrable mystery of existence,
    but he stepped in a wormhole and had to go in early."  // MST3K