GCC undefined behaviors are getting wild(blog.pkh.me)
blog.pkh.me
GCC undefined behaviors are getting wild
http://blog.pkh.me/p/37-gcc-undefined-behaviors-are-getting-wild.html
349 comments
Somewhat unfortunately this is valid behavior according to the standard. Having to go through walls of text in a standard to prevent the compiler from deleting your security checks because of how you multiplied two integers seems a bit silly.
Having said that I’m of split feelings here. I work in a very performance sensitive industry and on one hand welcomes the ability of compilers to use the knowledge that certain things “can’t happen” to optimize, without me having to always do these optimizations be hand.
On the other hand, there seem to be so many cases like this one where the “undefined behavior code deleter goes brrrrrr” really overextends its usefulness. The “lalalalala standard say I can do this can’t hear you” finger in your ears attitude from compiler maintainers doesn’t help at all either.
I understand that the way much of this works, propagating “poison/impossible values”, can hide the root cause, so you can’t just say “please do the good undefined behavior optimizations but not the bad, so there’s no easy answer. The outcome in the blog post doesn’t feel like a local optimum though, and it’s not the only place I’ve felt that your options are “potentially slow code” or “pray you were perfect enough to not have your program deleted”
Having said that I’m of split feelings here. I work in a very performance sensitive industry and on one hand welcomes the ability of compilers to use the knowledge that certain things “can’t happen” to optimize, without me having to always do these optimizations be hand.
On the other hand, there seem to be so many cases like this one where the “undefined behavior code deleter goes brrrrrr” really overextends its usefulness. The “lalalalala standard say I can do this can’t hear you” finger in your ears attitude from compiler maintainers doesn’t help at all either.
I understand that the way much of this works, propagating “poison/impossible values”, can hide the root cause, so you can’t just say “please do the good undefined behavior optimizations but not the bad, so there’s no easy answer. The outcome in the blog post doesn’t feel like a local optimum though, and it’s not the only place I’ve felt that your options are “potentially slow code” or “pray you were perfect enough to not have your program deleted”
GCC's UBSan catches it,
> runtime error: signed integer overflow: 50000000 * 511 cannot be represented in type 'int'
https://godbolt.org/z/oz9vvj5YM
Another heads up of the dangers of UB optimizations, and why using static analysis is a requirement for C derived languages.
If you aren't using all warnings turned on as errors, disabled implicit conversions and at very least have static analysis on the CI/CD pipeline, you're up for a couple of surprises.
From CppCon 2022, "Purging Undefined Behavior & Intel Assumptions in a Legacy C++ Codebase"
https://www.youtube.com/watch?v=vEtGtphI3lc
> runtime error: signed integer overflow: 50000000 * 511 cannot be represented in type 'int'
https://godbolt.org/z/oz9vvj5YM
Another heads up of the dangers of UB optimizations, and why using static analysis is a requirement for C derived languages.
If you aren't using all warnings turned on as errors, disabled implicit conversions and at very least have static analysis on the CI/CD pipeline, you're up for a couple of surprises.
From CppCon 2022, "Purging Undefined Behavior & Intel Assumptions in a Legacy C++ Codebase"
https://www.youtube.com/watch?v=vEtGtphI3lc
Since the author and GCC disagree about whether this behaviour is useful, it is likely that insufficient requirements analysis has taken place. Is GCC supposed to behave this way? This depends on what goals it is supposed to reach. The GCC authors would say that the C standard allows such compiler behavior, and what is allowed by the C standard doesn't need to be justified by other means. The article author would argue that usability towards the programmer leads to less bugs and is needed, at least partially, as a justification.
Going a step further, this places the article author outside GCC's main intended user group. It raises the question: Who are GCC's main intended users? And is there a way to more clearly advertise that the article author isn't part of them? This would probably help other potential GCC users to decide whether GCC is the right tool for them at all.
I don't really get the discussion about the C standard and UB in the other threads here. The standard and UB are only a tiny pixel in the big picture.
Going a step further, this places the article author outside GCC's main intended user group. It raises the question: Who are GCC's main intended users? And is there a way to more clearly advertise that the article author isn't part of them? This would probably help other potential GCC users to decide whether GCC is the right tool for them at all.
I don't really get the discussion about the C standard and UB in the other threads here. The standard and UB are only a tiny pixel in the big picture.
This has nothing to do with undefined behavior. Switch the code to unsigned integers, where overflow is perfectly defined as wrapping, and the result is exactly the same.
The compiler, to avoid the division, compares x * 0x1ff with 512 * 0xffff instead of x * 0x1ff / 0xffff with 512. This comparison is obviously bunk, since it doesn't take the uppermost bits of the multiplication into account. But so is the original comparison!
You see the same thing happen in Rust -- https://rust.godbolt.org/z/xf67rM77T -- the difference being that there's a second language-level bounds-check inserted at the lookup site.
The compiler, to avoid the division, compares x * 0x1ff with 512 * 0xffff instead of x * 0x1ff / 0xffff with 512. This comparison is obviously bunk, since it doesn't take the uppermost bits of the multiplication into account. But so is the original comparison!
You see the same thing happen in Rust -- https://rust.godbolt.org/z/xf67rM77T -- the difference being that there's a second language-level bounds-check inserted at the lookup site.
If this kind of optimization is unacceptably risky for your use case, you need a different programming language, not a different C compiler.
But that code code is wrong in the first place with defined overflow.
If x == 0x804021 then x * 0x1FF yields 0x1DF, and then proceeed to access tab[0]. This is very probably NOT what the author wanted.
- Defined overflow doesn't help at all, in fact the compiler would preserve what is wrong in the first place
- overflow trap is a little bit better, at least you would get the occasion to think about it
Even if the compiler doesn't act on the UB the code is still wrong.
If x == 0x804021 then x * 0x1FF yields 0x1DF, and then proceeed to access tab[0]. This is very probably NOT what the author wanted.
- Defined overflow doesn't help at all, in fact the compiler would preserve what is wrong in the first place
- overflow trap is a little bit better, at least you would get the occasion to think about it
Even if the compiler doesn't act on the UB the code is still wrong.
The root of all these problems is that C doesn't guarantee two's complement behavior when compiled for two's complement machines, as far as I understand.
But why is that? Why are integer operations not defined as implementation-defined?
I get that the C standard cannot guarantee two's complement when C code can be compiled for other architectures. But looking at the list of supported architectures ( https://gcc.gnu.org/backends.html ), even exotic architectures like vax and microblaze seem to be two's complement.
Does gcc even support one's complement machines or those with CHAR_BIT != 8 ? If not, all those optimizations are utterly ridiculous. Basically an adversarial competition between compiler writers and users.
I get that the C standard cannot guarantee two's complement when C code can be compiled for other architectures. But looking at the list of supported architectures ( https://gcc.gnu.org/backends.html ), even exotic architectures like vax and microblaze seem to be two's complement.
Does gcc even support one's complement machines or those with CHAR_BIT != 8 ? If not, all those optimizations are utterly ridiculous. Basically an adversarial competition between compiler writers and users.
This is why undefined behaviour is insidious: if a tiny part of your code is undefined behaviour, the behaviour of your entire programme is.
In addition to the points that other posts have made: it's also not especially new behavior. E.g. I see it at O2 gcc version 9.3.0 on i386. The optimization isn't performed by gcc 4.9.2 at O2 on i386. If I had to guess it probably shows up around GCC 5, but I don't seem to have any i386 vm's with gcc between 4.9.2 and 9.3 handy at the moment.
And 4.9 absolutely will do similar in other cases: fwrapv has existed since GCC 3.3 and fno-strict-overflow was introduced in GCC 4.2, which are flags to defeat these optimizations (and either of which avoids the crash on GCC 9.3)-- both introduced in response to increasingly effective optimization in prior GCC versions exposing errors like this. 4.9.2 just misses the optimization in this specific case.
And 4.9 absolutely will do similar in other cases: fwrapv has existed since GCC 3.3 and fno-strict-overflow was introduced in GCC 4.2, which are flags to defeat these optimizations (and either of which avoids the crash on GCC 9.3)-- both introduced in response to increasingly effective optimization in prior GCC versions exposing errors like this. 4.9.2 just misses the optimization in this specific case.
Hmm, I had expected more from the article given the title.
This is about the least surprising UB. It didn't even travel backwards in time.
This is about the least surprising UB. It didn't even travel backwards in time.
I think the lesson here is to stop using signed integer as an index into an array.
I am on split here. Signed overflow is UB and it is pretty well known, yet author is writing code that depends on such overflow.
But is there are a reason for `i >= 0` not raising a warning if it can't happen? Or is there a warning that was not enabled? I think `i >= 0 cant be false` would save a lot of headache
edit: one post mentions macros. Which makes sense in that case I think. You can easily write such impossible conditions with macros, so making it a warning would add a lot of warnings I guess
Although there are warnings for `if (true)/if (false)` "this condition is always true/false"
But is there are a reason for `i >= 0` not raising a warning if it can't happen? Or is there a warning that was not enabled? I think `i >= 0 cant be false` would save a lot of headache
edit: one post mentions macros. Which makes sense in that case I think. You can easily write such impossible conditions with macros, so making it a warning would add a lot of warnings I guess
Although there are warnings for `if (true)/if (false)` "this condition is always true/false"
While I have been a member of the "unsigned counting variable" minority for a long time, this kinda drives the nails into the coffin for a lot of signed array index / offset use. It's just too big a risk to accidentally have the compiler go YOLO on you for some minor detail you missed.
Also, this UB optimization train has gone way too far and needs to back up a few stations.
I'm gonna say there needs to be a switch to make signed overflow not be UB. Maybe that already exists? starts checking docs
Also, this UB optimization train has gone way too far and needs to back up a few stations.
I'm gonna say there needs to be a switch to make signed overflow not be UB. Maybe that already exists? starts checking docs
I compile all my C code with -fno-strict-overflow and -fno-strict-aliasing, and I recommend you to do so as well. C standard committee and GCC and Clang are being stupid, but that does not mean you should suffer their stupidity.
I am sort of uneasy with what the optimizing doing in here.
But I would not ever write something like this:
But I would not ever write something like this:
int32_t i = x * 0x1ff / 0xffff;
D solved this particular problem by defining arithmetic as being 2-s complement, including wraparound behavior.
In gcc you can use the -ftrapv or -fwrapv compiler options to get defined signed integer overflow arithmetic.
There’s no reason to expect the result of integer overflow to be negative, or any particular value at all. It is undefined.
So after checking that x > o there is no way for i (a product and ratio of positive numbers) to become negative.
The only reason this is surprising is that there is an expectation of wrapping on overflow. But this is simply not the behavior of the C virtual machine.
(Maybe today it makes sense to have even C wrap in a two’s-complement way? C is used in many places though, maybe there are still platforms in use that aren’t two’s-complement?)
So after checking that x > o there is no way for i (a product and ratio of positive numbers) to become negative.
The only reason this is surprising is that there is an expectation of wrapping on overflow. But this is simply not the behavior of the C virtual machine.
(Maybe today it makes sense to have even C wrap in a two’s-complement way? C is used in many places though, maybe there are still platforms in use that aren’t two’s-complement?)
I think it was a mistake when CPU and language designers decided to make overflow in arithmetic operations not an error. This is wrong. Overflow can produce invalid data, which can break something elsewhere. Overflow has been a reason for security vulnerabilities.
For example, you don't want to have an overflow when calculating a total cost of ordered goods or size of an allocated memory block.
One could argue that it is a developer's responsibility to make sure overflow doesn't happen, but the history shows that developers usually fail to protect the program from such kind of errors. We have memory protection, why cannot we have overflow protection?
In my opinion, an overflow should cause an exception unless the program explicitly asks to ignore it. Of course this means that every addition now becomes a (very unlikely) conditional branch, but I guess this can be optimized by static prediction. Every memory access is already a conditional branch, and it doesn't cause problems.
But CPUs and programming languages seems to make writing overflow-safe code more difficult than unsafe. In assembly, you have to insert additional branch instructions, and in business-oriented languages like Java you have to write long sentences like Math.addExact(). If you write a complicated formula this way, it becomes unreadable.
Sadly, modern languages like Rust haven't fixed the mistake and also penalize writing safe code.
The only language I know with overflow protection is Swift: an overflow causes an exception there. Well done, Apple, you are lightyears ahead of open source software.
For example, you don't want to have an overflow when calculating a total cost of ordered goods or size of an allocated memory block.
One could argue that it is a developer's responsibility to make sure overflow doesn't happen, but the history shows that developers usually fail to protect the program from such kind of errors. We have memory protection, why cannot we have overflow protection?
In my opinion, an overflow should cause an exception unless the program explicitly asks to ignore it. Of course this means that every addition now becomes a (very unlikely) conditional branch, but I guess this can be optimized by static prediction. Every memory access is already a conditional branch, and it doesn't cause problems.
But CPUs and programming languages seems to make writing overflow-safe code more difficult than unsafe. In assembly, you have to insert additional branch instructions, and in business-oriented languages like Java you have to write long sentences like Math.addExact(). If you write a complicated formula this way, it becomes unreadable.
Sadly, modern languages like Rust haven't fixed the mistake and also penalize writing safe code.
The only language I know with overflow protection is Swift: an overflow causes an exception there. Well done, Apple, you are lightyears ahead of open source software.
C standards fault. GCC has intrinsics that let you do arithmetic safely with overflow checks
Just use them
https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins...
Just use them
https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins...
There is an old german proverb that fits here, "Es kann nicht sein, was nicht sein darf", mocking lords and judges who purposefully mixed up things that are physically impossible to happen and things that ought not to happen by policy and made their life awfully easy that way.
People already weren't fond of that kind of logic a hundred years ago.
I think HTML5 sets a good example of how to do it instead: A large part of the standard is about defining behaviour for functionality the standard explicitly deprecates and disallows in compliant documents - all just so "legacy" HTML documents don't end up with "undefined behaviour".
People already weren't fond of that kind of logic a hundred years ago.
I think HTML5 sets a good example of how to do it instead: A large part of the standard is about defining behaviour for functionality the standard explicitly deprecates and disallows in compliant documents - all just so "legacy" HTML documents don't end up with "undefined behaviour".
This probably just an example, but why are they using a signed int for indexing???
> I'm expecting this article to make the rust crew go in a crusade again, and I think I might be with them this time.
I think he makes a good point. By having overflow be undefined you leave yourself open to all sorts of issues.
I think he makes a good point. By having overflow be undefined you leave yourself open to all sorts of issues.
I think this article makes a far better case than the college hyperbole of "once you invoke undefined behavior it is allowed to format your drive and kill your cat."
As chance would have it, I am actually arguing with another team today about introducing undefined behavior into our code-base. They're arguing "well it works so its fine." I used this article to argue that it doesn't matter and we're inviting really insidious errors to come in later down the road.
As chance would have it, I am actually arguing with another team today about introducing undefined behavior into our code-base. They're arguing "well it works so its fine." I used this article to argue that it doesn't matter and we're inviting really insidious errors to come in later down the road.
I knew rust had to be mentioned. But this is a optimization bug. I break my code several times while optimizing thinking a minor change wont matter then end up undoing it all.
Well, that's undefined behaviour. It could have inserted system("rm -rf /*"); instead and be right about that.
I'm not so sure it's that wild. Signed overflow is UB so it makes perfect sense it's not possible to check overflow happened. You need to make sure overflow doesn't happen.
Similarly it's invalid to check if an access to an array is out of bounds after you have accessed it.
Similarly it's invalid to check if an access to an array is out of bounds after you have accessed it.
It's rude to spam bug reports like that. GCC has a mailing list, if a discussion is what you want.
Why did GCC change x < 0 to -1 < x? I guess it is faster - but why? x >=0 would have also been a valid transformation to archive the same flow
This has caused a Linux kernel exploit in the past [1], with GCC removing a null pointer check after a pointer had been dereferenced. Null pointer dereferences are UB, thus GCC was allowed to remove the following check against null. In the kernel, accessing a null ptr is technically fine, so the Linux kernel is now compiled with -fno-delete-null-pointer-checks, extending the list of differences between standard C and Linux kernel C.
[1]: https://lwn.net/Articles/342330/