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

41–50 of 198 posts

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

#41

Post by [deleted] »

raverbashing wrote: post #39
bleepblorp wrote: post #34

Earlier quoted context omitted.

INTO. It signals int 0x04 if the instruction is executed while the overflow flag is set due to a prior signed arithmetic operation wrapping. It seems I misspoke somewhat; there is somewhat equivalent functionality in x64 in the JO instructions, but they're six bytes rather than one and the extra size could have cache and/or memory bandwidth impacts under demanding circumstances.

Causing an interrupt is much more expensive than having a jump that won't be taken most of the time

[deleted]

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

#42

Post by saagarjha »

alblue wrote: post #22
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…

This is essentially Swift’s problem on the server. If you have a service running and serving hundreds of clients, then any one of those threads can cause a trivial panic if there’s an overflow and take the entire service down. As a result, a number of use cases for swift on the server actually use heavyweight out of process threads (i.e. one process per client) so that the failure of one of them doesn’t take down the…

I’m curious if one could use a mildly-modified Swift compiler that converts all the different ways to abort execution into some sort of panic handler you can override would help work around this issue.

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

#43

Post by saagarjha »

formerly_proven wrote: post #32
olliej wrote: post #24

The problem with integer overflow, in the general context of UB, isn't that it's expensive to trap. The problem is that the C (and C++) specs insist on overflow being undefined behavior. Then compilers insist on abusing the UB as meaning that they get to do whatever they want. This particular case is only partially the compiler's fault, as the various specs should not be defining well specified behavior as being unde…

Integer overflow should have been implementation-defined behavior from day one, because that's what it actually is.

Implementation defined means that the behavior is defined. This is patently not what the existing behavior of compilers in the face of integer overflow is.

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

#44

Post by rightbyte »

raverbashing wrote: post #39
bleepblorp wrote: post #34

Earlier quoted context omitted.

INTO. It signals int 0x04 if the instruction is executed while the overflow flag is set due to a prior signed arithmetic operation wrapping. It seems I misspoke somewhat; there is somewhat equivalent functionality in x64 in the JO instructions, but they're six bytes rather than one and the extra size could have cache and/or memory bandwidth impacts under demanding circumstances.

Causing an interrupt is much more expensive than having a jump that won't be taken most of the time

Usually you don't really care that much about the overflow cost if it is an error right?

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

#45

Post by saagarjha »

olliej wrote: post #24

The problem with integer overflow, in the general context of UB, isn't that it's expensive to trap. The problem is that the C (and C++) specs insist on overflow being undefined behavior. Then compilers insist on abusing the UB as meaning that they get to do whatever they want. This particular case is only partially the compiler's fault, as the various specs should not be defining well specified behavior as being unde…

Measuring this is tricky for a macrobenchmark because most codebases tend to split into “give me -fwrapv or give me death” or “I care about avoiding undefined behavior so I insert checks myself”. You can’t change any compiler flags to change during benchmarking this for either because for the first one you may break the program and for the second those checks will prevent wrapping for occurring regardless.

For what it’s worth, the usually argument given for overflow being undefined is that it makes loop analysis much easier and as a result it allows for better hoisting and strength reduction and autovectorization.

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

#46

Post by nly »

olliej wrote: post #24

The problem with integer overflow, in the general context of UB, isn't that it's expensive to trap. The problem is that the C (and C++) specs insist on overflow being undefined behavior. Then compilers insist on abusing the UB as meaning that they get to do whatever they want. This particular case is only partially the compiler's fault, as the various specs should not be defining well specified behavior as being unde…

I've never bought this argument. If wrapping signed arithmetic (-fwrapv) were the default, and an overflow occurred, then most programs would still not function as intended.

Basically your argument is that programmers should be implementing:

https://wiki.sei.cmu.edu/confluence/display/c/INT30-C.+Ensur...

instead of:

https://wiki.sei.cmu.edu/confluence/display/c/INT32-C.+Ensur...

Both of these solutions are garbage, and blaming the compiler because your language (C) is too weak to help you out is shrugging off responsibility.

In places where overflow is likely to matter from a security perspective (parameters derived from user input for example), what mode is used is irrelevant. It's actually easier for a programmer to check for overflow using a safe compiler intrinsic[0] (or in C++ use a checked[1] or multiprecision[2] integer library) than it to correctly implement their own checks.

[0] https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins...

[1] https://www.boost.org/doc/libs/1_74_0/libs/safe_numerics/doc...

[2] https://www.boost.org/doc/libs/1_74_0/libs/multiprecision/do...

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

#47

Post by wahern »

alblue wrote: post #22
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…

This is essentially Swift’s problem on the server. If you have a service running and serving hundreds of clients, then any one of those threads can cause a trivial panic if there’s an overflow and take the entire service down. As a result, a number of use cases for swift on the server actually use heavyweight out of process threads (i.e. one process per client) so that the failure of one of them doesn’t take down the…

This reminds me of Rust unconditionally ignoring SIGPIPE. Except in this case there's a non-trivial amount of pre-existing (and even future) code that assumes a process will be terminated if it attempts to write to a closed pipe. One of Rust's selling points is ease of FFI, so it's largely irrelevant that Rust APIs wouldn't let you ignore write errors. Rust breaks the environment for libraries that rely on the behavior.

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

#48

Post by kazinator »

olliej wrote: post #24

The problem with integer overflow, in the general context of UB, isn't that it's expensive to trap. The problem is that the C (and C++) specs insist on overflow being undefined behavior. Then compilers insist on abusing the UB as meaning that they get to do whatever they want. This particular case is only partially the compiler's fault, as the various specs should not be defining well specified behavior as being unde…

C compilers should assume that every bit of code is necessary. The only dead code is that which is predicated on a compile-time constant, as in:

  if (0) {
     /* safe to ptimize this away */
  }
Code which tests a run-time condition must always be assumed to be doing that for a reason.

Just provide excellent code generation: great peephole optimizations, jump threading, instruction selection: all the "classics". Try to put local variables into registers nicely. Treat every pointer dereference as a load or store.

No fucking bullshit like, "oh, this pointer was dereferenced four lines up from here so this null pointer check can be removed".

Because, like, maybe that dereference is a simple mistake, and not an iron-clad logical proposition asserted by an infallible programmer.

C was originally designed as a language in which optimizations were up to the programmer. If you wrote clever code like while (* d++ = * s++); to copy a string, that was not just for brevity; it produced better code. That was the idea. The compiler was dumb, and so the fact that in that entire expression, s and d appear only one time meant that they were only accessed one time in the generated code. The programmer was the optimizer. Terse code stuffing multiple effects into a single expression ran faster. And by that same token, no pun intended, code that was less terse was safer. It made all the memory accesses and evaluations that it looked like it was doing, in the order it was doing them.

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

#49

Post by wahern »

ot wrote: post #10

This blog post has a much more in-depth analysis of the cost of overflow checking: https://blog.regehr.org/archives/1384 The tl;dr is that (on x86-64) the additional branch to trap has almost negligible cost (processor already sets the flag on overflow, jump is always predicted), but it completely breaks vectorization and loop optimizations, which significantly impacts certain benchmarks.

But see "Sentinels can be faster", https://lemire.me/blog/2020/09/03/sentinels-can-be-faster/. HN discussion: https://news.ycombinator.com/item?id=24402763.

I once worked on a project that compiled Perl-compatible regular expressions to C code using Ragel + custom modifications that could switch to NFA machines for subexpressions as required. The generated NFA machines required simple stack operations (push and pop of NFA state) on a preallocated array. Originally the PoC attempted no bounds checking, and so could theoretically overflow the array, possibly (likely) corrupting the heap. When I added bounds checking to each generated push operation (a simple test + goto), throughput plummeted by something very significant--two- or three-digit, not single-digit percentages. So I allocated the array with mmap and a guard page. And rather than pick a magic number and call it a day, on SIGSEGV (or SIGBUS?) I would longjmp back to a point where I could grow the array and restart match execution from the beginning. Performance returned to where it was originally.

Fortunately, nothing in the code that might trigger SIGSEV could leave behind inconsistent state or orphaned resources that might need to be collected. The longjmp from the signal handler was perfectly safe and obeyed all relevant constraints; it didn't implicate undefined behavior.

Unfortunately, neither POSIX nor Linux (nor any Unix, AFAIK) supports per-thread signal handlers, only a global handler per signal. And you can't safely access thread-local storage from a signal handler, anyhow.[1] To distinguish an expected SIGSEGV from an unexpected SIGSEGV, and to support multiple threads, I used sigaltstack. The SIGSEGV handler would query the alt stack. If there was no alt stack, it aborted. If there was an alt stack, it would derive a per-thread data structure stored in a page beyond the top of the stack with an intervening guard page of its own. (sigaltstack is per-thread.) The guard page stored the jmp_buf structure needed for the longjmp, and the array boundaries needed to distinguish NFA state overflow from a real bug. The siginfo_t reference passed to the signal handler provided the fault address.

This was an interesting little subproject because it showed just how performant hardware-based exceptions could be (I never did much kernel or assembly programming), as well as how detrimental conditional branching could be to performance. And it was almost certainly the only time I'll have a truly legitimate reason to catch SIGSEGV, as opposed to previous cases I've seen in some other projects that had the horrible idea of attempting to recover from a truly invalid and uncontrolled memory access.

[1] POSIX doesn't permit it, though in practice it depends on the libc. musl supports it because it preallocates all TLS when creating a thread, but it's unsafe on glibc as glibc lazily allocates TLS. We were using glibc, and while theoretically I could have induced TLS slot initialization, thread-safe reentrancy of internal machinery was an area where glibc actually had (and has, last time I checked) quite a few open bugs, so I wasn't about to play games there.

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

#50

Post by raverbashing »

rightbyte wrote: post #44
raverbashing wrote: post #39

Earlier quoted context omitted.

Causing an interrupt is much more expensive than having a jump that won't be taken most of the time

Usually you don't really care that much about the overflow cost if it is an error right?

True but do you care for all sums/muls in your code?

Might be better to check where exactly can you have the overflows and test in the code for those cases. I think checking for overflows over the entire code is useful for testing/validation purposes but not really useful in production.

Or use bigger data types if you're hitting overflows frequently.

Post reply on HN