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

Signed overflow optimization hazards in the kernel

Posted Aug 16, 2012 14:04 UTC (Thu) by baldrick (subscriber, #4123)
Parent article: Signed overflow optimization hazards in the kernel

> The second example is from mx1_2_set_next_event() in the ARM architecture,
> which is using a variation on this theme to determine whether the
> requested event time really is in the future. Here the actual subtraction
> is unsigned, but the result is cast to an signed integer. Because unsigned
> longs are always positive, the only way that the result can be negative
> (when interpreted as a signed value) is overflow, which the compiler is
> permitted to assume never happens. The compiler is therefore within its
> rights to unconditionally evaluate the test as false and return zero,
> which might fatally disappoint the caller.

As far as I know this is wrong: there is no problem in the second example. The misunderstanding is in "Because unsigned longs are always positive, the only way that the result can be negative (when interpreted as a signed value) is overflow, which the compiler is permitted to assume never happens". Since the numbers have unsigned type, subtracting them always has a well defined result. The fact that when you think of these numbers as being signed you see in your head that a signed overflow must have occurred is of no relevance. The cast to a signed type is also always well defined. In fact I would say the right way to avoid this issue is to copy this example and do something like
(signed) ((unsigned)x - (unsigned)y) < 0
rather than do the baroque comparison recommended by the article.

For more on this kind of thing I recommend http://blog.regehr.org/archives/213

to post comments

Signed overflow optimization hazards in the kernel

Posted Aug 16, 2012 22:46 UTC (Thu) by PaulMcKenney (✭ supporter ✭, #9624) [Link] (7 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);
}

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 2:20 UTC (Fri) by PaulMcKenney (✭ supporter ✭, #9624) [Link]

Though I could make the macros type-generic by (ab)using sizeof(). Not sure it is worth it, though.

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

Signed overflow optimization hazards in the kernel

Posted Aug 17, 2012 6:45 UTC (Fri) by wahern (subscriber, #37304) [Link] (3 responses)

You have that in reverse. Conversion to unsigned is always well defined. Conversion to signed where the value cannot be represented is implemented-defined:

C99 6.3.1.3 Signed and unsigned integers

When a value with integer type is converted to another integer type other than _Bool, if the value can be represented by the new type, it is unchanged.

Otherwise, if the new type is unsigned, the value is converted by repeatedly adding or subtracting one more than the maximum value that can be represented in the new type until the value is in the range of the new type.49)

Otherwise, the new type is signed and the value cannot be represented in it; either the result is implementation-defined or an implementation-defined signal is raised.

Signed overflow optimization hazards in the kernel

Posted Aug 17, 2012 21:57 UTC (Fri) by pdewacht (subscriber, #47633) [Link] (2 responses)

But given that Linux is only intended to be compiled by gcc, we can rely on its implementation-defined behavior:

The result of, or the signal raised by, converting an integer to a signed integer type when the value cannot be represented in an object of that type (C90 6.2.1.2, C99 6.3.1.3).
For conversion to a type of width N, the value is reduced modulo 2^N to be within range of the type; no signal is raised.

(and I don't see how any compiler for a two's complement computer could define different behavior.)

Signed overflow optimization hazards in the kernel

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

True enough!

However, the Linux kernel's code can be legitimately used in any GPLv2 project, including those that might run on systems with non-twos-complement signed integer arithmetic. This sharing of code among compatibly licensed projects is a very good thing, in my view.

Which means in this case, where there is a solution that meets the C standard, and which loses nothing by doing so (at least on x86 and Power), it only makes sense to use that C-standard solution.

Signed overflow optimization hazards in the kernel

Posted Aug 18, 2012 23:58 UTC (Sat) by giraffedata (guest, #1954) [Link]

The result of ... converting an integer to a signed integer type when the value cannot be represented in an object of that type ...
For conversion to a type of width N, the value is reduced modulo 2^N to be within range of the type;

I must be reading that wrongly, because that's not at all what GCC does. With -m32, int is a signed integer type of width 32. UINT_MAX reduced modulo 2^32 is UINT_MAX, which is not within the range of int. So this does not describe what (int)UINT_MAX does.

Rather, what GCC does appears to be the opposite of what the standard requires for conversion from negative number to unsigned integer (add UINT_MAX+1 until it fits): it subtracts UINT_MAX+1 until the value is within the range of int (in this case -1).