Catching integer overflows in C
fefe.de
fefe.de
It's really the same issue any language would have with the particular backend it uses.
What's different about the D approach, however, is that the user can select which of several behaviors on overflow, and then select which of several responses to overflow, instead of being stuck with just one or two options. The tests we've run shows it generates the same code as if one had done it by hand.
Specifically for
X = a * b
You have to do:
If (b == 0) X = 0 Else if (MAX(type of X) / b >= a) X = a * b Else Handle overflow error
Oof
Just to be able to serve DNS answers.
That’s just so wrong.
GCC and Clang have mostly compatible compiler intrinsics and with those two compilers you can compile your software to almost any platform out there.
If you need to get your code compiled on MSVC or ICC or some niche C compiler, you can work around this by adding some kind of wrapper around them with #ifdefs (not pretty).
With compiler built-ins you get SIMD, atomics, bitops (popcnt, clz, etc) that are portable to almost any CPU instruction set out there. Without them, you have to re-write that code for every instruction set you intend to support.
So your options are:
1) Stick to standard C and write code that compiles to suboptimal output code (such as using division to get multiply-with-overflow)
2) Use compiler built-ins and get portability across different HW at the expense of not supporting other compilers
3) Write wrappers around compiler built-ins with #ifdefs to support all the compilers you want (add fallback to standard C if you need to)
4) Write your code using HW-specific intrinsics or inline assembly
Out of these, option 2) will give you maximum portability with least amount of effort. The other options are more effort and the benefits are arguable. If you think there are other viable options, please do share.
Writing code to two specific compilers (clang and gcc) is NOT portable code.
This is absolutely unacceptable behavior.
But wait, that's not portable to Keil so you cannot use that ;)
The reaction is, if you dislike fast but non standard code, push for standardization of those features, not begrudge developers for doing the right thing and using them.
However, they already work acceptably in GCC and Clang. There are only minor differences (e.g. __builtin_shufflevector) but it's usable with very minimal #ifdeffing.
Example:
typedef float vec4f __attribute__((vector_size(16)));
// initializer
vec4f a = { 1.0, 2.0, 3.0, 4.0 };
// literal expression
vec4f b = a + (vec4f){ 5.0, 6.0, 7.0, 8.0 };
// standard infix operators
vec4f c = -b * (a+b); // with --ffast-math, this will be a mad()
[0] https://gcc.gnu.org/onlinedocs/gcc/Vector-Extensions.html
Trading portability for performance is a trade-off that most developers shouldn’t be willing to make if they are open sourcing their software, because it will prevent someone from running their software on that user’s desired platform, thereby showing the user the middle finger. That’s just wrong.
http://www.pixelbeat.org/programming/gcc/integer_overflow.ht...
Can the programmer express the intent that this will not overflow? i.e. is it possible to coerce the Rust compiler to optimize (x*2)/2 to x? "Cheap hardware traps" cannot substitute for such a compile-time optimization.
> C seems pretty hopeless since there is no way to know whether or not the coder intended on overflow or not.
Well this doesn't matter: if signed arithmetic overflows the code is undefined, regardless of intent.
In practice comments can express intent, and unsigned arithmetic can with some finessing produce most codegen. Explicit operators would be a big improvement though.
LLVM’s constant folding and canonicalization passes will convert (x * 2) / 2 from
%0 = mul i64 %x, i64 2
%1 = div i64 %0, i64 2
to
%0 = shl i64 %x, i64 1
%1 = shr i64 %0, i64 1
Which constant folding will reduce to just %x.
Rust made the right tradeoff here but it is a tradeoff!
For example, a for loop from 0-through-N (N:i32) will execute N times in C, but N-or-infinity times in Rust. That small difference of infinity controls how the loop condition is tested, whether it can be turned into a simple counter or not.
Eh, not quite true. If N is a 64-bit or an unsigned integer but your loop index is a signed 32-bit integer, then you will have this behavior. In Rust, the idiomatic for loop will have the index variable always be the same size as the condition variable, which prevents the infinity case from happening. In C, if you have a 64-bit condition but a 32-bit unsigned loop index variable, you get the N-or-infinity case as well.
In other words, if your language is subtly redesigned to make you jump through hoops to do things like have mismatched integer types in for loops, then the need to rely on undefined behavior to reclaim that performance is lessened.
This seems awfully close to implementation-defined behavior to me…I'm surprised to see something like this, which allows for (IMHO) unsafe behavior, from Rust.
https://huonw.github.io/blog/2016/04/myths-and-legends-about...
This seems like a situation where dropping to assembly to perform the addition and testing the flag makes sense. GCC has a mechanism for inline assembly where you list the variables you read from, you write to, and registers you modify and the optimizer plays nice with you. You could provide it as a function to use instead of doing the addition in C.
It's easy to write, but not so easy to optimize the performance.
Overflow checking creates a dependency in between operations and requires the emission of instructions that didn't have to be there before.
i += 1 <branch if overflow> i += 1 <etc>
Means that you are executing more than twice the number of instructions and are getting further behind on the dependency chain each iteration. Eventually, your branch subsystem is completely overwhelmed by a branch that is taken effectively never.
That said in modern clang and gcc you can (and should) use the overflow builtins which are all essentially:
Bool __builtin_[operation]_overflow(type a, type b, type* out)
if(overflowoperation(x,y,&out)) ...
Produces the platform branch on overflow instructions.
That is not an accurate or fair assessment.
However signed integer overflow being undefined behavior is a bit over the top given modern hardware. I'd like to see the C standard adopt a policy of wrapping for signed overflow, then either add new operators or functions for trapping behavior.
Most reasonable hardware has the instructions to trap or branch if add/sub/mul/div overflows or underflows so the checks are very cheap. Unlike the early days, in this day if C made it part of the standard processor manufacturers would simply stop selling CPUs without those features. Same goes for two's-compliment integer representations. They already did the same for 8-bit char/byte; other sizes are no longer supported.
Obviously there is signed integer overflow, which has resulted in numerous security flaws for questionable performance gains.
Then there are other fun things, like technically it is UB for bzero to skip padding bytes in a struct (because that is UB), which means bzero(&somestruct, siseof(somestruct)) is not technically guaranteed to clear all of the struct, so I hope there’s not any secrets in left over memory.
Punning through unions is well-defined behavior in C99 and C11. In C++11 and newer, it's questionable, but it works in practice.
Aliasing queries in the compiler basically work on a tiered system. There's a simple aliasing pass that first checks for really obvious alias information (such as, it's the same pointer, it's a bitcast of the pointer, it's a simple arithmetic expression of the same pointer), possibly some more advanced Andersen's-style alias passes, and only finally is there a last-ditch strict-aliasing based pass.
If you take the address of a float and cast that to an integer pointer to get at the bits of the float (and don't let either pointer escape the function), it will work, even with "abusive" compilers that have aggressive optimization turned on, even if you modify the lvalue in the intervening code. It's literally more work to make the compiler not realize that the two pointers alias, and there's no benefit to pessimizing a trivial query, so I would be shocked if any compiler actually miscompiled that code.
The definition of UB would allow a type punned union on the stack for instance to be treated as logically a struct - eg changes to the float value would not impact the integer value. While I agree that would not happen in practice today there is no reason it has to continue to work.
The fact that compilers already make sane decisions regarding some UB - evaluation order of parameters used to be unspecified and gcc at least would change evaluation order depending of optimisation level, but all compilers have realized that just insane and so left to right evaluation. Similarly bzero will initialise padding bytes in a struct even though that is technically UB, so could technically be skipped.
Sorry for run on horror sentences I’m typing on my phone :)
And that is effectively a bug in that standard, says Linus, and I agree with him.
https://lkml.org/lkml/2018/6/5/769
"I've said this before, and I'll say it again: a standards paper is just so much toilet paper when it conflicts with reality."
Sadly, the compiler maintainers at some points of time managed to push the real "breaking" changes through (for other UB cases). It seems that the "language lawyerism" is "easier" than the expected approach of the responsible engineers.
Memcpy is a cost. Do it only when you actually need a copy.
I suppose union based type punning makes the intent a little clearer (vis a vis memcpy) but that's a weak argument at best.
How much more explicit can you get than a memcpy?
Eh, the undefined nature of signed overflow in C is a bit of a red herring. The most common overflow bug in practice is actually 100% well-defined and still 100% wrong: multiplying two numbers to feed into a malloc.
In practice, the undefined signed overflow really only comes into play when you're trying to explicitly check for overflow by doing the operation and then seeing if it overflowed. But, as you mention, compilers give you bultins to do this kind of checked overflow which is quite frankly a much easier way to solve the problem, especially since it's more likely to actually get matched to using hardware flag bits to check for overflow.
Which contemporary processors don’t have the C and Z status bits?
Post scriptum, since “Hacker News” is of the opinion that I’m posting too fast:
MIPS does have a status register, and this register does have an overflow bit:
------------------
Addendum addressing your updates:
> MIPS does have a status register, and this register does have an overflow bit:
Yes, it does, but it doesn't function as a simple carry or zero bitfield. In MIPS, there are two instructions for performing addition: add and addu. add generates a trap which you can respond to in an exception handler (which is where you check for this exception code)–as opposed to addu, which overflows silently. Most programs explicitly looking to check for overflow just use addu followed by a sltu (set less than, unsigned).