Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

How expensive is integer-overflow trapping in C++?

lemire.me

Post reply on HN
Print view View original

111–120 of 198 posts

Re: How expensive is integer-overflow trapping in C++?

#111

Post by bregma »

The big thing that isn't talked about is the fact that the problem with forcing a vendor-specific definition on the undefined behaviour of signed integer overflow is that significant optimization opportunities are lost.

The danger of signed integer overflow in C++ is not that your less-than-zero comparison is not working in a reverse for-loop (although, to be fair, that's a danger encountered by newbies). The big problem is that the compiler will optimize away huge chunks of code when it detects a possible signed integer overflow resulting in weird and unexpected behaviour at runtime. It's not really an exploitable security issue so much as a massive cost issue from stretched out development time or increased support costs (depending on how well your code gets tested before release).

Re: How expensive is integer-overflow trapping in C++?

#112

Post by gpderetta »

jojobas wrote: post #3

From GCC documentation, >The compiler will attempt to use hardware instructions to implement these built-in functions where possible, like conditional jump on overflow after addition, conditional jump on carry etc. I suspect something's not exactly right with compiler flags. Then again, how much of your program is integer arithmetic? 12x slowdown on 0.1% is 1.2%.

IIRC -ftrap is basically unmaintained in GCC and you are supposed to use ubsan instead.

edit: and it seems that ubsan does generate a simple jo:

  https://godbolt.org/z/88dE5G
Don't use -ftrap I guess.

Re: How expensive is integer-overflow trapping in C++?

#113

Post by jandrewrogers »

pjc50 wrote: post #91
amelius wrote: post #69

Earlier quoted context omitted.

We probably need different integer types to express the differences. Perhaps whether or not we check for overflow can be encoded in the type of the integer.

Yes. For some time I've wondered about doing a programming language for conservative arithmetic, in which you don't ask for "integer" but specify "32-bit signed, exception on overflow" or "16-bit, do not exception immediately but set a flag which I can check at the end of the function" or "8-bit, use saturation arithmetic". The exact opposite of the scripting language "everything is just a thing and you can add numbe…

People have written C++ libraries for integer type generation that allow you to specify many properties including various types of arithmetic and runtime behavior. It is pretty transparent to the programmer and efficient.

However, there is real complexity, in terms of library implementation, in figuring out how this zoo of exotic integer types interact with each other consistently and correctly. Doubly so if you want the safety of these interactions to be verified at compile-time to the extent possible.

Re: How expensive is integer-overflow trapping in C++?

#114

Post by tom_mellior »

xpressvideoz wrote: post #90
zeotroph wrote: post #82

Earlier quoted context omitted.

Is there a reason to not add a new instruction to x86-64 which does interrupt the program on an integer operation overflow so no branching happens in the program? And can this instruction be made just as fast as the unchecked ones?

Having a mode that makes all existing arithmetic instructions interrupt sounds plausible, though there must be something I overlooked.

That wouldn't work well for C since signed overflow is undefined, but unsigned overflow is well-defined, with wrapping semantics. Making all existing arithmetic instructions trapping would mean paying trapping costs for well-defined unsigned overflow.

Re: How expensive is integer-overflow trapping in C++?

#115

Post by brohee »

bleepblorp wrote: post #15

It's worth mentioning that x86 CPUs had a single instruction overflow test that would raise a hardware interrupt in response to an integer overflow. This allowed for extremely low cost integer overflow tests. Unfortunately, this capability was deleted from x86-64 and we're now stuck with either accepting the risks of integer overflows or suffering a performance hit to test for them by using multiple instructions. Ano…

It's also IMHO a failure of RISC-V. "We did not include special instruction set support for overflow checks on integer arithmetic operations in the base instruction set, as many overflow checks can be cheaply implemented using RISC-V branches"

Cheaply is not freely.

Re: How expensive is integer-overflow trapping in C++?

#116

Post by tom_mellior »

fluffy87 wrote: post #103
lytigas wrote: post #6

Earlier quoted context omitted.

Rust wraps in release mode and traps in debug mode[0][1]. All large projects that I know of ship in release mode. Though I'd be interested to see a source for it not pessimizing badly. [0] https://play.rust-lang.org/?version=stable&mode=release&edit... [1] https://github.com/rust-lang/rfcs/pull/560

See my reply to masklin in this thread for why this is incorrect. In release mode, the behavior of integer overflow in Rust is not UB/cannot happen, but modulo two arithmetic. These two are not the same thing.

Huh? Parent wrote:

>> Rust wraps in release mode and traps in debug mode

You wrote:

> In release mode, the behavior of integer overflow in Rust is not UB/cannot happen, but modulo two arithmetic.

The parent didn't claim or imply that overflow is UB. The parent wrote that it "wraps", which is equivalent to your "modulo two arithmetic". You are not in disagreement, so why are you disagreeing?

Re: How expensive is integer-overflow trapping in C++?

#117

Post by tom_mellior »

loa_in_ wrote: post #63
quietbritishjim wrote: post #59

> adding two large integers can result in an integer that cannot be represented in the integer type. We often refer to such error conditions as overflows. There's a subtlety here that's missed in the article: In C and C++ this is only called "overflow" for signed integers. That's because that word specifically refers to the case where the behaviour is undefined, and for unsigned integers the result is always well def…

So overflow means overflow, but underflow as well, while underflow means precision loss. What a bad case of misnomers.

Overflow doesn't mean underflow. Overflow means overflow. You can use "negative overflow" for the special case of overflow where a negative number's magnitude is too big. Though why would you care about the difference between positive and negative overflow, really?

Re: How expensive is integer-overflow trapping in C++?

#118

Post by UncleMeat »

MaxBarraclough wrote: post #55
asveikau wrote: post #8

Aborting the program on integer overflow seems so drastic. Say you do that in a server program. Then convincing it to overflow an integer somewhere (possibly somewhere where it is harmless) causes denial of service and all unrelated connections in the process die? I guess languages with support for exceptions have a more natural action for this, that could be caught somewhere in a server's processing loop to not affe…

> Aborting the program on integer overflow seems so drastic. Disagree. Overflowing of a signed integer type is undefined behaviour, which deserves to be taken seriously. I was surprised to see that the article doesn't mention the signed/unsigned distinction, or undefined behaviour. Overflowing of a unsigned integer type is not a problem, it's defined to wrap around, and may be done intentionally.

> Overflowing of a unsigned integer type is not a problem, it's defined to wrap around, and may be done intentionally.

It is not a problem for the language, but it may be a problem for your program. Unsigned overflow can happily introduce vulns into your bounds checks.

Re: How expensive is integer-overflow trapping in C++?

#119

Post by zeotroph »

tom_mellior wrote: post #114
xpressvideoz wrote: post #90

Earlier quoted context omitted.

Having a mode that makes all existing arithmetic instructions interrupt sounds plausible, though there must be something I overlooked.

That wouldn't work well for C since signed overflow is undefined, but unsigned overflow is well-defined, with wrapping semantics. Making all existing arithmetic instructions trapping would mean paying trapping costs for well-defined unsigned overflow.

I think this would be a per-thread state which you toggle, defaulting to "off". Then instead of checking and branching after each operation you flip it on/off depending on the type of arithmetic you want. The trick would be to get to the minimal number of toggles and not do the "safe" thing and set it to on/off for each operation.

Re: How expensive is integer-overflow trapping in C++?

#120

Post by dathinab »

brohee wrote: post #115
bleepblorp wrote: post #15

It's worth mentioning that x86 CPUs had a single instruction overflow test that would raise a hardware interrupt in response to an integer overflow. This allowed for extremely low cost integer overflow tests. Unfortunately, this capability was deleted from x86-64 and we're now stuck with either accepting the risks of integer overflows or suffering a performance hit to test for them by using multiple instructions. Ano…

It's also IMHO a failure of RISC-V. "We did not include special instruction set support for overflow checks on integer arithmetic operations in the base instruction set, as many overflow checks can be cheaply implemented using RISC-V branches" Cheaply is not freely.

The question is how much more expensive then a overflow checked add, which is mostly likely not as cheap as a non checked add.

I mean in the end both do a non checked add and then branch on the carry. One does it implicitly and branches to an interrupt and one does it explicitly and branches however you like it.

(Slightly) Increased chip complexity should be included in the choice, too.

I guess the main difference would/could be if used with some form of branch prediction.

Post reply on HN