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

Signed overflow optimization hazards in the kernel

Posted Aug 16, 2012 5:32 UTC (Thu) by jmspeex (guest, #51639)
Parent article: Signed overflow optimization hazards in the kernel

> This hazard stems from an annoying aspect of the C11 standard, namely that signed-integer overflow is undefined (Section 3.4.3).

Actually, signed-integer overflow was undefined long before C11. It was definitely undefined in C99 and I'm pretty sure it also was in C89. After all, there *are* machines that handle it in different ways. There's (nearly extinct) one's complement and two's complement, but there's also saturating arithmetic that many DSPs use, where (for 16-bit type), 32767+1 = 32767.

Also, when it comes to undefined arithmetic, there's a lot more to worry about. For example, shifting *by* a negative value is undefined. So is shifting a negative value left (even if the shift is by a positive number of bits). Fortunately, clang now has a feature that can add run-time checks to your source code and detect these undefined arithmetic operations.

to post comments

Signed overflow optimization hazards in the kernel

Posted Aug 16, 2012 21:10 UTC (Thu) by daney (guest, #24551) [Link] (3 responses)

> Actually, signed-integer overflow was undefined long before C11.
> It was definitely undefined in C99 and I'm pretty sure it also was in C89.

The first edition of K & R explicitly states the signed-integer overflow is undefined. This has carried through to the present.

Signed overflow optimization hazards in the kernel

Posted Aug 16, 2012 22:48 UTC (Thu) by PaulMcKenney (✭ supporter ✭, #9624) [Link] (2 responses)

Understood. And when it was suggested within the C11 Standards committee that signed-integer overflow be given twos-complement semantics, the discussion was both emphatic and short. ;-)

Signed overflow optimization hazards in the kernel

Posted Aug 17, 2012 16:07 UTC (Fri) by josh (subscriber, #17465) [Link] (1 responses)

What did the arguments against it say, other than "that would remove compiler optimization possibilities"?

Signed overflow optimization hazards in the kernel

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

One objection was that there really are still non-twos-complement machines in common use. As was noted by the comment to this article discussing saturating adders, where 32767+1==32767. But this would be addressed by "implementation defined" rather than "undefined".

Another objection was that there are systems still in common use that trap on signed integer overflow. If the C standard required wrapping, compilers for such systems would require special edge-case checks on pretty much any signed integer operation.

And there was of course also the objection that signed integer overflow always has been undefined. ;-)

Signed overflow optimization hazards in the kernel

Posted Aug 17, 2012 19:16 UTC (Fri) by gmaxwell (guest, #30048) [Link]

JM, the clang integer overflow checker we've used on our projects isn't part of clang proper, it's a (very useful) patch: http://embed.cs.utah.edu/ioc/

Beyond the optimization possibilities, the existence of tools like this is also a reason for keeping the undefined behavior, e.g. continue using signed values for counters that don't need the extra unsigned range: Most of the time overflow that you didn't expect (and thus couldn't wrap in a casting macro) is a sign of a logic error. By keeping it invalid you gain the possibility of dynamic instrumentation to catch those errors.

(Though I don't know if anyone has managed to get tools like this working with the kernel yet!)