Hacker News Reader

Comment by kibwen | Hacker News Reader

Upvoted for the signed integer overflow example. I'll admit that I actually don't know the most idiomatic, bulletproof way of testing for signed overflow in C; if you google "how to test signed integer overflow in C", the very first result is essentially equivalent to the buggy example in the blog post ( https://www.geeksforgeeks.org/check-for-integer-overflow/ ), and I'm not keen to repeat the legendary case of signed overflow within the PHP interpreter: https://web.archive.org/web/20120412194929/http://use.perl.o...

View on HN

In C you avoid signed integer overflow either by knowing that the result will be in range before applying an operation, or, as a last resort, by testing that the operation is defined before carrying it out. For example, if a and b are ints, then a + b is defined if (a >= 0 && b <= INT_MAX - a) || (a < 0 && b >= INT_MIN - a).

Additionally, some compilers can insert code to detect signed integer overflow at runtime. Clang has the -fsanitize=undefined flag [1].

[1] https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html

Nope, that's the old way. Nowadays you do have access to the (un)signed add with carry (adc) builtins, which are the best way to provide an alternate method on overflow.

That is not portable.

no, gcc and clang do provide portable builtins. previously you had to use inline assembly, now it's trivial.

GCC and clang aren't the only C compilers on the planet.

Portable means being defined in the ISO C standard.

Nope. Practically gcc and clang are available for all platforms, and for the rare cases someone uses another compiler or an old version you ifdef it out with the slow path. even ICC has the add/mult with carry overflow builtins.

The ISO C standard is hopelessly behind for decades. They don't even define a proper (unicode) string API (search, norm, utf8, fc) , constexpr, a memory model, ... and leave everything to the implementors.

I very much doubt that, specially since clang doesn't even cover all gcc supported architectures.

Additionally, being available doesn't mean it is the compiler one is allowed to use.

Apparently you haven't kept up with ISO C, C11 defined the memory model and portable threads. It is unfortunate that compiler vendors, specially your beloved gcc and clang disregard the security Annex K.

beloved gcc? I despise gcc for not being able to provide a proper constexpr in C, making memcpy, memset 2x slower than clang.

Why do you aspire to write "portable" code which you are referring to as code that conforms to the ISO C standard when most widely used compilers do not? What you are suggesting is extremely impractical, it is a matter between theory and practice. Conforming to the standard when the compiler itself does not is impractical. On top of that, these compilers are available on most platforms, and yours seem to be such an edge case that it is negligible, and you can make the necessary adjustments when and if it ever comes to that. It is likely that it will not. If it does, it is just a matter of one or two ifdefs. Personally I write code that conforms to the compiler, because in reality, from a practical point of view, that is all that really matters.

It is not impractical, past experience on doing library projects for mutiple POSIX platforms, where the number one requirement was that they had to be compilable by the system compilers, teached me the right way of writing portable C code.

> system compilers

Such as? Do not get me wrong, I am against using GNU extensions, for example, and I do tend to make my code as portable as possible, but my main issue was with people glorifying the standard to what compilers themselves do not even strictly conform, and sometimes for good reasons. When you write code, you cannot ignore the compiler for obvious practical reasons. It does not matter what the paper says when the compiler does something completely different, or differently. If something goes terrible, you cannot say, "Oops, I was silly. I did not bother checking the documentation of the compiler.".

This reminds me of something like: https://lkml.org/lkml/2018/6/5/769

I'm not sure there is a reliable, generic approach for detecting overflow in conformant C; you probably have to come up with the appropriate proof for the specific operation that you're about to do. OpenBSD does it for multiplication in reallocarray() [1], which was introduced because it was easy to code an integer overflow when doing something like malloc(sizeof(member) * nmembers).

[1] https://github.com/openbsd/src/blob/master/lib/libc/stdlib/r...

It depends on what operation could potentially overflow.

Mozilla has a CheckedInt (C++) type that checks all operations for overflow. You can see examples of how this is actually implemented here: <https://searchfox.org/mozilla-central/source/mfbt/CheckedInt.... You can derive similar C implementations if you work through all of the template magic.

Be warned that the definition of what is undefined, implementation-specific, and well-defined varies depending on the exact version of the C or C++ standard you use.

I'll just say it: that's a clang bug. The assumption being made by the optimizer is wrong, for exactly the reason that overflow exists.

I get very tired of people trying to make this "really" about "undefined behavior" sanity when real compilers are real software with real behavior. And here there is a clearly desired behavior (whether or not it got written into a standard somehwere), and clang implemented something else. That's wrong.

This particular undefined case is a really interesting one; it seems utterly non-obvious why it exists, until you remember one thing...

The most popular architecture today is 64-bit, with ABI specifying that the integer type is 32-bits wide.

So when faced with performing an operation on two 32-bit signed integers, on a 64-bit platform, you have to either:

1) perform the operation in 32-bit registers - if available - and even if available, usually far far far fewer in number thus massive performance & resource penalties to code

2) perform the operation in 64-bit registers, then add code to check the result, and if it would overflow in 32-bit, compute what the overflowed result would have looked like in a 32-bit register, and return that instead - again quite a performance hit

3) perform the operation in 64-bit registers, and just return the lower 32-bits, whatever that might be

The standard declined to pick a choice, which is why we have UB here.

(For unsigned integers, you can just truncate the result and it works every time, which is why the standard defines the result)

Wait a second: both ARM and IA-64 have 32 bit operations.

> 1) ... perform the operation in 32-bit registers - if available - and even if available, usually far far far fewer in number

False for x86-64. There are sixteen 32-bit general-purpose registers: eax, ebx, ..., r8d, ..., r16d. There are sixteen 64-bit registers too: rax, rbx, ..., r8, ..., r16.

On the contrary: if clang assumed that signed integers could overflow by default, then that would be a bug. Why? Because it would result in missed optimizations, and optimizations are the reason why we use an optimizing compiler.

Here's an example of what can happen if the compiler doesn't perform these optimizations: https://gist.github.com/rygorous/e0f055bfb74e3d5f0af20690759...

The loop codegen when the optimization is not performed is pretty atrocious. That is the bug, and solving that bug is the reason why compilers assume signed overflow cannot happen.

If you want to blame something, blame the C language. Compiler developers are just doing their jobs.

Here's an example of what can happen if the compiler doesn't perform these optimizations:

That's a great article, although I don't think it shows the advantage of assuming that undefined behavior will never occur. Rather than assuming "no undefined behavior", wouldn't it be legal (and preferable) for a compiler to just let the overflow (or lack of overflow) occur, and make the same optimization? For me the entire point of contention is the difference between "undefined" and "implementation defined". Maybe I'm wrong about the details here, but I think this is a case where a compiler could be just as fast without the nasal daemons.

It is doing exactly what you say - the code as generated simply lets the "overflow" occur, which is what makes it fast. In particular, if the index variable overflows the size of `int` it will just keep increasing. Effectively, the compiler has replaced int with long under the covers, since the cases where the behavior between int and long differ are exactly the cases where the int has overflowed.

So it's not always the case that the compiler assumes "overflow won't happen" and then _removes code_ - it just compiles code in a way that is ideal for the non overflow case and then what happens in the overflow case just falls out of the generated assembly (usually it does something bad like OOB access, but the same would generally be true of a wrapping overflow also).

You can't make this "implementation defined though", because the behavior is from a C-source point of view, it is effectively: "In the case an int overflows, we silently add 32 more bits and keep incrementing". Obviously you can't support that behavior in general, and even in specific cases it leads to nonsense like ints have non-representable values, etc.

GCC gets those loops optimized correctly without hitting the broken code in the linked article. I don't see that that's particularly responsive. Software is a concrete thing, it has concrete behavior, and problems can be solved there instead of pontificating about what paper standards say.

> If you want to blame something, blame the C language. Compiler developers are just doing their jobs.

Compiler developers are doing a fantastic job, and I absolutely do blame the C language and standard.

For the cases referenced in the article, it seems to me that the preferred solutions would be making int 64-bits and leaning on the restrict keyword rather than the semi-disaster that is strict aliasing (https://blog.regehr.org/archives/1307).

Use the compiler intrinsics (__builtin_add_overflow, etc.): that's what they're there for. They are guaranteed to generate the most efficient code.

With plenty of #ifdef #else #endif, as they aren't portable.

Instead of obfuscating with ifdef's, what's the downside of just using a non-standard but well-supported intrinsic that works for major compilers on common systems? For closed source, you are distributing a binary anyway, and have control of the compiler you choose. For open source, it may fail to compile, but the error message should make it clear what needs to be done (probably linking in a function written in assembly for the unsupported platform).

Well, the way you test are usually: 1) you know the ranges your params belong to and 2) you avoid situations where you might overflow. Usually if you catch the overflow you already lost.

I'm surprised to see that for unsigned ints modular semantics are guaranteed by the spec

"Please tell me again how unsigned ints are broken" It seems this meme seems to be the C version of anti-vaxxers.

"don't know the most idiomatic, bulletproof way of testing for signed overflow in C"

Basically, a great tool for static analysis and/or Frama-C for just the range analysis. Then, a coding style that facilitates such analysis. That should cover analysis. Idiomatic might be a problem because I see so many overflows in C code that it seems idiomatic for it to have them. ;)

With Clang you can use `-fsanitize=undefined` which will try to find out these overflows.

-fwrapv gives you the desired C semantics.

Reply on news.ycombinator.com