Signed overflow optimization hazards in the kernel [LWN.net]

Signed overflow optimization hazards in the kernel

Posted Aug 16, 2012 22:46 UTC (Thu) by PaulMcKenney (✭ supporter ✭, #9624)
In reply to: Signed overflow optimization hazards in the kernel by baldrick
Parent article: Signed overflow optimization hazards in the kernel

Hmmm... If I compile the following with gcc 4.6.1 with -O2:

unsigned long long signed_cast(unsigned long long a, unsigned long long b)
{
        return (signed)((unsigned)a - (unsigned)b);
}

The following x86 object code is generated:

 120:   8b 54 24 04             mov    0x4(%esp),%edx
 124:   2b 54 24 0c             sub    0xc(%esp),%edx
 128:   89 d0                   mov    %edx,%eax
 12a:   c1 fa 1f                sar    $0x1f,%edx
 12d:   c3                      ret

This is a 32-bit subtraction on 64-bit quantities. And when I plugged 2^32=4294967296 for a and 2^31-1=2147483647 for b, a-b evaluated to 2147483649 (as expected), but signed_cast(a, b) evaluated to -2147483647.

So unless I misunderstood what you are suggesting, I will be sticking with the baroque comparisons for RCU.

Signed overflow optimization hazards in the kernel

Posted Aug 17, 2012 5:05 UTC (Fri) by jimparis (guest, #38647) [Link] (3 responses)

Hmmm... If I compile the following with gcc 4.6.1 with -O2:
unsigned long long signed_cast(unsigned long long a, unsigned long long b)
{
        return (signed)((unsigned)a - (unsigned)b);
}
...
This is a 32-bit subtraction on 64-bit quantities.

Well, yeah, that's because "(signed)" is casting 32-bit when compiled with -m32. I might be misunderstanding your issue here but it seems you wanted:

unsigned long long signed_cast(unsigned long long a, unsigned long long b)
{
        return (signed long long)((unsigned long long)a - (unsigned long long)b);
}

Signed overflow optimization hazards in the kernel

Posted Aug 18, 2012 18:07 UTC (Sat) by ppisa (subscriber, #67307) [Link] (2 responses)

I hope that behavior of unsigned to signed conversion stays defined (at least for GCC and GCC replacement compilers - LLVM, Intel atc.). GCC defines behavior in current manual version

http://gcc.gnu.org/onlinedocs/gcc/Integers-implementation...

I use ((signed type)((unsigned type)a - (unsigned type)b) > 0) often in our embedded code and in the fact I am probably author/coauthor of that MX1 example - if that line was not not rewritten by somebody.

Paul's example behavior is correct according to my knowledge (unsigned) is equivalent to (unsigned int) ie on 32 bit target 32 bit subtraction is evaluated and then sign is extended to 64 bits when conversion to (signed it) and then 64 bit signed type is required.

What is common trap is that plain

(unsigned type) a - (unsigned type) b

is not considered (type) nor (signed type). It is signed but interpreted as so big signed to hold additional bit if it is compared with zero. So additional cast to signed type same or smaller than both inputs (a and b) has to be used.

I use next mechanism to allow cyclic comparison between different
hardware, position, time, state generation counters etc in our code.

http://ulan.git.sourceforge.net/git/gitweb.cgi?p=ulan/ulut;...

Library is licensed GPL, LGPL, MPL, but code fragment can be taken as public domain, if it helps somebody.

#ifndef ul_cyclic_gt
#define ul_cyclic_gt(x,y) \
((sizeof(x)>=sizeof(long long))&&(sizeof(y)>=sizeof(long long))? \
(long long)((unsigned long long)(x)-(unsigned long long)(y))>0: \
(sizeof(x)>=sizeof(long))&&(sizeof(y)>=sizeof(long))? \
(long)((unsigned long)(x)-(unsigned long)(y))>0: \
(sizeof(x)>=sizeof(int))&&(sizeof(y)>=sizeof(int))? \
(int)((unsigned int)(x)-(unsigned int)(y))>0: \
(sizeof(x)>=sizeof(short))&&(sizeof(y)>=sizeof(short))? \
(short)((unsigned short)(x)-(unsigned short)(y))>0: \
(signed char)((unsigned char)(x)-(unsigned char)(y))>0 \
)
#endif /*ul_cyclic_gt*/

#ifndef ul_cyclic_ge
#define ul_cyclic_ge(x,y) \
((sizeof(x)>=sizeof(long long))&&(sizeof(y)>=sizeof(long long))? \
(long long)((unsigned long long)(x)-(unsigned long long)(y))>=0: \
(sizeof(x)>=sizeof(long))&&(sizeof(y)>=sizeof(long))? \
(long)((unsigned long)(x)-(unsigned long)(y))>=0: \
(sizeof(x)>=sizeof(int))&&(sizeof(y)>=sizeof(int))? \
(int)((unsigned int)(x)-(unsigned int)(y))>=0: \
(sizeof(x)>=sizeof(short))&&(sizeof(y)>=sizeof(short))? \
(short)((unsigned short)(x)-(unsigned short)(y))>=0: \
(signed char)((unsigned char)(x)-(unsigned char)(y))>=0 \
)
#endif /*ul_cyclic_ge*/

Please, if you know about some target, compiler or intention to break assumption (at least hopefully current GCC version guarantee) that unsigned to signed conversion reinterprets MSB as a sign. As for correctness of the code, there could be problem if target specifies some basic arithmetic type with some bits unused. It short 16 bit but stored in 32 bit entity. But none of our targets has that problem.

Code is used in many targets, some of safety grade class applications so notice of possible (even future) breakage is critical for me and users.

Signed overflow optimization hazards in the kernel

Posted Aug 18, 2012 19:02 UTC (Sat) by PaulMcKenney (✭ supporter ✭, #9624) [Link] (1 responses)

Cool, that was the sort of thing I was thinking of with my "sizeof()" earlier, though I still do feel more comfortable with using the constants than relying on casting.

But why the casts to unsigned integral types? I would instead have expected a requirement that the caller's cyclic arithmetic be carried out in unsigned integers, so that the casts were unnecessary.

Signed overflow optimization hazards in the kernel

Posted Aug 18, 2012 22:34 UTC (Sat) by ppisa (subscriber, #67307) [Link]

Hmm, cast to unsigned used to work even for signed types and in practice works still. a+=20 is translated into single add instruction on all targets I know. The other reason for casting is, that sometimes you can strore in object only shorter part of time stamp or generation counter, if you know, that live period is small enough or if you only check for change. Casting both to smaller of the two makes subtraction possibly cheaper, the result has to be casted to smaller one anyway.

But main reason for casting to ensure thing works on existing code
with signed types.

Best wishes,

Pavel

Signed overflow optimization hazards in the kernel

Posted Aug 19, 2012 17:00 UTC (Sun) by baldrick (subscriber, #4123) [Link] (1 responses)

By "signed" I meant "signed integer type of the same size" and by "unsigned" I meant "unsigned integer type of the same size". The "same size" means: the same number of bits as the original integer type, so in the case of example 2 this means "signed long long" and "unsigned long long". Sorry for not being clear.

Signed overflow optimization hazards in the kernel

Posted Aug 20, 2012 0:44 UTC (Mon) by PaulMcKenney (✭ supporter ✭, #9624) [Link]

No problem!

I must admit that it would be nice if "(signed typeof(a))" and (unsigned typeof(b))" flipped the signedness of "a" and "b", but my version of gcc really doesn't like either variant. ;-)