6 ms·
Catching integer overflows in C
- phibz 8y agoMost (all?) modern processors have instructions and flags specifically for querying and reacting to integer overflow/carry. 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.
- abenedic 8y agoI have been doing a lot of assembly programming, and I can't help but agree with this. It is crazy how simple x86 assembly language programming makes checking overflow compared to C.
- saagarjha 8y agoThat's the issue: while x86 exposes such operations, not all assembly dialects do. They too have to support C and emulating overflow detection in software would be unreasonable.
- acqq 8y agoIt seems to me that it would not be unreasonable. If you need that detection, you need it at any price, on any platform. If you don't need it, meaning, the code doesn't test it, the compiler has still the right to optimize it away.
- saagarjha 8y agoSo it would be implementation defined behavior. I'm fine with that; personally, I think the standard was too quick to assign "undefined" here. But it can't mandate a certain behavior in the standard across all platforms.
- bsder 8y ago> It is crazy how simple x86 assembly language programming makes checking overflow compared to 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.
- abenedic 8y agoish, you can use cmov for some stuff.
- AstralStorm 8y agoWhere is it available in MIPS?
- snaky 8y ago> cmov's can make a difference. You can use them to avoid polluting your branch prediction tables, you can use them to make code smaller, and you can use them when they simply just fit the problem really well. It's just _not_ the case that they are "obviously better". They simply aren't. https://yarchive.net/comp/linux/cmov.html https://yarchive.net/comp/linux/cmov.html
- Mikhail_Edoshin 8y agoIf the upper bound is known, then we'll just make the check once before the loop, no?
- olliej 8y agoThe issue isn’t what the hardware can do, but rather that the C spec leaves it undefined. Over the last decade have increasingly abused this idea basically making the spec a land mine of UB and then claiming that UB allows them to do whatever they want, even when the programmer intent is obvious. 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) Returning true if the operation overflowed. These produce “ideal” code, e.g if(overflowoperation(x,y,&out)) ... Produces the platform branch on overflow instructions.
- xenadu02 8y ago> Over the last decade have increasingly abused this idea basically making the spec a land mine of UB and then claiming that UB allows them to do whatever they want, even when the programmer intent is obvious. 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.
- olliej 8y agoThere has been an ever increasing creep of undefined behaviour, which has broken existing code - type punning through unions was literally the “correct” mechanism for type coercion, which then became invalid when they established new, questionable, type aliasing rules that rendered it UB. The new type aliasing rules also mean that you can’t implement memcpy/memmove/bzero/memset without hitting UB. That requires hacks in the spec treatment of type aliasing to work around. Hell, even Malloc/free technically is UB due to type aliasing. 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.
- olliej 8y agoThe correct thing to do these days is to use compiler builtins, but assuming you can’t (such misery), the correct thing to do for multiplication involves division (because the performance cost of treating multiplication as fixed width 2s complement is so high ;) ) 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
- Annatar 8y agoUsing compiler built-ins makes one’s code instantly unportable and is therefore unacceptable.
- jchw 8y agoWhen it comes to anything that isn't embedded work, I only care about platforms that support GCC or Clang. I'd happily take an improvement to my development workflow at the cost of dropping support for fringe users. Making truly portable C or C++ code is an exercise in utter pointlessness, and is usually impractical for non-trivial software, be it a desktop application, an operating system kernel, and a lot of things in between. By marketshare an extreme majority of computers and phones in the world can be targeted with Clang alone. Giving up useful compiler extensions to gain compatibility for a platform used by 0.0001% of computer users seems very pointless. I'd rather be concerned with making my software accessible to those with visual impairments or other disabilities, a way, way huger demographic, one that you can't choose to not be a part of.
- Annatar 8y agoWell we disagree vehemently: writing clean C code that compiles with any ANSI C compiler is pretty damn easy. Take BIND for example, a non-trivial piece of software which compiles with any compiler.
- hossbeast 8y agoNot at all. You wrap it in an ifdef macro by platform.
- pixelbeat__ 8y agoI've found int overflow one of the most pernicious issues in C programming, and have been maintaining notes (which reference this article) at: http://www.pixelbeat.org/programming/gcc/integer_overflow.html http://www.pixelbeat.org/programming/gcc/integer_overflow.ht...
- bvinc 8y agoRust decided for overflows to cause panics in debug mode, but continue normally in release mode. They have special function calls for the few times that you actually WANT overflow. This seemed to he the only good option. It allows the programmer to express intent. In the future, if hardware allows for cheap hardware traps in the case of unintentionally overflow, they reserve the right to use them in release mode. C seems pretty hopeless since there is no way to know whether or not the coder intended on overflow or not.
- millstone 8y ago> It allows the programmer to express intent. 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.
- lyinsteve 8y agoI don’t know much about rust specifically, but the overflow traps happen in debug (i.e. -O0) builds, and are not emitted when optimizations are enabled. 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.
- millstone 8y agoWell ok but (x*3)/3 will be a lot worse :)
- Franciscouzo 8y agoNot by a lot, the divide by constant can be optimized to a multiplication, if you're doing it in a loop (why would you care if you do it only once), you can reach a throughput of one multiplication per cycle, so (x*3)/3 would take 2 cycles on average.
- WalterBright 8y agoD has an unusual approach where the characteristics of an integer type can be mixed and matched as needed by the user: https://dlang.org/phobos/std_experimental_checkedint.html https://dlang.org/phobos/std_experimental_checkedint.html
- saagarjha 8y agoInteresting. Does this compile down to the appropriate assembly instructions for checking for overflow, if available, or does it end up emulating it with a couple dozen instructions? That is, is this low-cost or does it have a measurable performance penalty and should only be used in debug builds?
- WalterBright 8y agoIt depends on the implementation, which does what it has to do to work with the backend. If the backend supports intrinsics that efficiently check for these things, then they'll be used. 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.
- Annatar 8y agoThese are all work-arounds: the permanent fix is to expose the processor’s carry and zero flags in C.
- saagarjha 8y agoNot every processor has these flags.
- Annatar 8y agoProcessors had these en masse (6502, Z80, MC68000) since the ‘70’s of the past century. Without those, it’s extremely difficult to implement basic arithmetic with numbers larger than what the processor’s registers support. 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: https://www.doc.ic.ac.uk/lab/secondyear/spim/node10.html https://www.doc.ic.ac.uk/lab/secondyear/spim/node10.html
- saagarjha 8y agoMIPS? ------------------ 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).