14 ms·

GCC undefined behaviors are getting wild

156 points by signa11 4y ago

TazeTSchnitzel 4y ago
This is why undefined behaviour is insidious: if a tiny part of your code is undefined behaviour, the behaviour of your entire programme is.
- josephcsible 4y ago
  Nitpick: it's not the behavior of the program that becomes undefined, but of the execution that it occurs in. For example, consider a program that reads argv[3] without making sure there's at least 4 arguments. If you call it with too few arguments, that entire execution is undefined (even stuff that happens before the out-of-bounds access), but if you call it with enough arguments, it is well-defined and the compiler has to emit code that will work.
  - masklinn 4y ago
    Ah but the trap is that if the compiler can reason that UB always occurs (in reality it will reason that code is dead because the constraints it computes don’t allow for its execution) then it can remove the entire thing. See Raymond Chen’s well known “undefined behaviour can result in time travel”.
    - josephcsible 4y ago
      Sure, but if UB always occurs, then every execution is undefined, so doesn't what I said still hold? (And the time travel is what I meant by "even stuff that happens before the out-of-bounds access".)
- eru 4y ago
  Yes. To spell it out: undefined behaviour doesn't just affect specific values nor just the behaviour of your program after triggering UB. It's the entire behaviour of your programme. So UB can 'travel backwards in time'. Fun fact: not closing a string literal is UB. Ending a non-empty source file in anything other than a newline is also UB.
mlindner 4y ago
> 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.
- josefx 4y ago
  Of course with well defined overflow you can still end up with a nonsense result that just happens to be in your valid range of values. If you don't plan to harden your code against integer overflow manually you need a language that actively checks it for you or uses a variable sized integer to be safe.
  - p0nce 4y ago
    Ah someone else spotted it. The author's code is wrong whether signed overflow is well defined or not.
  - ekidd 4y ago
    I've spent a fair bit of time running a fuzzer on Rust code that parses untrustworthy data. And the thing that saved my code time and time again was that Rust has runtime bounds checks. Even if I messed up index calculations, I'd get a controlled panic, not a vulnerability.
  - eru 4y ago
    Ending up with a nonsense result ain't great, but it's still a step up from losing all guarantees about the behaviour of your program. By the way, throwing an error on overflow is also a perfectly valid way to get defined behaviour and not end up with a nonsense value.
  - deleted 4y ago
    [deleted]
  - silon42 4y ago
    He did harden the code by having an explicit range check.
josephcsible 4y ago
If this kind of optimization is unacceptably risky for your use case, you need a different programming language, not a different C compiler.
- turminal 4y ago
  Do you have any specific languages in mind?
  - matkoniecz 4y ago
    Author of linked article mentions Rust
    - turminal 4y ago
      Rust is a good replacement for most use cases, but I think specifically in case where you're looking for a more predictable and less risky implicit behavior, the replacement should be more stable and predictable than Rust is at the moment.
      - matkoniecz 4y ago
        What kind of language is C replacement without UB and better concurrency and more stable/predictable than Rust?
        mlindner 4y ago
        Question, but where do you get the idea that Rust is not stable or predictable? I understand you were asking for something _more_ stable/predictable than Rust, but Rust is already very stable and very predictable (in fact I can't think of any ways that Rust is "unpredictable").
    - JonChesterfield 4y ago
      Fun thing there is rust feeds into the same optimisation pipeline as C or C++, so there's a definite risk of it inheriting some of their semantics via errors in the compiler implementation.
32gbsd 4y ago
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.
- ototot 4y ago
  This is not a bug. This is the model of C. You should blame C not GCC.
  - iforgotpassword 4y ago
    I blame GCC. The C standards committee is some out of touch with reality conglomerate working in a vacuum, taking 50 years of language history into account. I expect my compiler vendor to be on my side, ie produce a compiler that helps me write good software and not get in my way. GCC is doing the opposite, it's deliberately looking to use the standard to fuck me over in the most subtle and unexpected ways. Signed integer overflow is undefined; that gives compiler authors the liberty to make it do anything they want, including well defined things that anyone would expect and find useful. But GCC decides to fuck you over so their devs can give you an arrogant reply and impose their superiority if you show up on their bug tracker.
    - astrange 4y ago
      GCC's developers work for companies that want more optimizations. UB is the way you get these optimizations. But "gcc -fsanitize=undefined" is just as easy to run as "gcc -O3" is.
    - saagarjha 4y ago
      Turns out people get upset when their code goes slower because the the compiler added traps on signed overflow.
      - iforgotpassword 4y ago
        Don't add traps, just let it overflow and don't fuck up any bounds checks the programmer added.
vgatherps 4y ago
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”
- proto_lambda 4y ago
  The problem here is that the thing that "can't happen" isn't actually something that can't happen, it's something that isn't allowed to happen according to a many-hundred-page document that approximately nobody reads. It's not something that can be optimised because the compiler can prove it cannot happen, it is allowed to be optimised because the standard says "dear programmer, if you ever make this happen, god help you".
  - iforgotpassword 4y ago
    It's still braindead and idiotic. Every relevant platform nowadays has well defined overflow for signed ints. A sane C compiler should go with that and base its optimizations on it. GCC has been a pile of garbage in this regard for many years now. Its devs get further removed from reality with every year. Treating signed int overflow as undefined should be hidden behind a flag.
    - 4y ago
FpUser 4y ago
I am sort of uneasy with what the optimizing doing in here. But I would not ever write something like this: int32_t i = x * 0x1ff / 0xffff; Not because I am supersmart and will / can predict how optimizer will fuck it up. It is just that I am paranoid when coding and this type of code just simply hurts my perception for some reason.
- saagarjha 4y ago
  It seems like a perfectly cromulent line of code to me, assuming you have overflow checks somewhere.
  - Karliss 4y ago
    The trap in C is that you can't have overflow checks after the calculations testing if overflow happened by making assumptions about what the UB does. Once the UB has happened it's already too late. What you actually need is input range checks to ensure that following code can perform it's calculations correctly without hitting UB or you need to use helper intrinsics which perform checked math operations.
  - FpUser 4y ago
    As already said it just ruffles my feathers the wrong way. I would not analyze why as I usually have better things to do with my programming time. The best answer I can come up with without thinking is something like this: overflow is an error. I would prefer the code not to create errors unless absolutely needed.
- eru 4y ago
  This is the minimal example. For all we know, the original code might have made more sense in context?
hxhxhrra 4y ago
As others are pointing out, the C standard does allow this. There is no safe way to check for undefined behavior (UB) after it has happened, because the whole program is immediately invalidated. 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/ https://lwn.net/Articles/342330/
- charcircuit 4y ago
  >the C standard does allow this The C standard also allows doing it even when there is no UB. C gives implementations a ton of freedom.
- xeeeeeeeeeeenu 4y ago
  >Linux kernel is now compiled with -fno-delete-null-pointer-checks Like many other large C codebases, it also uses -fno-strict-aliasing and -fno-strict-overflow (which is a synonym for "-fwrapv -fwrapv-pointer").
  - fps_doug 4y ago
    We've got a few components written in C that I'm (partially) responsible for. It's mostly maintenance, but for reasons like this I run that code with -O0 in production, and add all those kinds of flags. I'd be curious to know how much production code today that's written in C is that performance critical, i.e. depends on all those bonkers exploits of UB for optimizations. The Linux kernel seems to do fine without this.
    - NohatCoder 4y ago
      I'm fairly confident in declaring the answer to your question: None. Most programs rarely issue all the instructions that a CPU can handle simultaneously, they are stuck waiting on memory or linear dependencies. An extra compile-out-able conditional typically doesn't touch memory and is off the linear dependency path, which makes it virtually free. So the actual real-world overhead ends up at less than 1%, but in most cases something that is indistinguishable from 0. If you care that much about 1% you are probably already writing the most performance critical parts in Assembly anyway.
Phelinofist 4y ago
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
- proto_lambda 4y ago
  It's just an artifact of decompilation. It's the same operation in machine code (checking the MSB), there's no way to tell which one was used in the original source code.
- stop50 4y ago
  An signed integer uses the leftmost bit for the sign: 00000000 = 0 10000000 = 128 = -128 https://onlinetoolz.net/unsigned-signed#base=2&value=10000000&bits=8 https://onlinetoolz.net/unsigned-signed#base=2&value=1000000...
WirelessGigabit 4y ago
What the purpose of the / 0xffff?
- f1shy 4y ago
  Had the same question. This is the minimal implementation of the error, so there is no clue what was the original purpose. I think as it is, it indexes a table where the first positions return tab[0], the next ffff/1ff will return tab[1] and so on. If I see such a code at work I would reject it in less than 1ms
hddqsb 4y ago
It should be noted that in this particular case it only happens when optimisations are enabled (-O2). With -O2: https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:___c,selection:(endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:'%23include+%3Cstdint.h%3E%0A%23include+%3Cstdio.h%3E%0A%23include+%3Cstdlib.h%3E%0A%0Auint8_t+tab%5B0x1ff+%2B+1%5D%3B%0A%0Auint8_t+f(int32_t+x)%0A%7B%0A++++if+(x+%3C+0)%0A++++++++return+0%3B%0A++++int32_t+i+%3D+x+*+0x1ff+/+0xffff%3B%0A++++if+(i+%3E%3D+0+%26%26+i+%3C+sizeof(tab))+%7B%0A++++++++printf(%22tab%5B%25d%5D+looks+safe+because+%25d+is+between+%5B0%3B%25d%5B%5Cn%22,+i,+i,+(int)sizeof(tab))%3B%0A++++++++return+tab%5Bi%5D%3B%0A++++%7D%0A%0A++++return+0%3B%0A%7D%0A%0Aint+main(int+ac,+char+**av)%0A%7B%0A++++return+f(atoi(av%5B1%5D))%3B%0A%7D'),l:'5',n:'0',o:'C+source+%231',t:'0')),k:50,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:cg122,deviceViewOpen:'1',filters:(b:'0',binary:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'0',libraryCode:'0',trim:'1'),flagsViewOpen:'1',fontScale:14,fontUsePx:'0',j:1,lang:___c,libs:!(),options:'-O2',selection:(endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:1),l:'5',n:'0',o:'+x86-64+gcc+12.2+(Editor+%231)',t:'0')),k:50,l:'4',n:'0',o:'',s:0,t:'0')),l:'2',n:'0',o:'',t:'0')),version:4 https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename... Without -O2: https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:___c,selection:(endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:'%23include+%3Cstdint.h%3E%0A%23include+%3Cstdio.h%3E%0A%23include+%3Cstdlib.h%3E%0A%0Auint8_t+tab%5B0x1ff+%2B+1%5D%3B%0A%0Auint8_t+f(int32_t+x)%0A%7B%0A++++if+(x+%3C+0)%0A++++++++return+0%3B%0A++++int32_t+i+%3D+x+*+0x1ff+/+0xffff%3B%0A++++if+(i+%3E%3D+0+%26%26+i+%3C+sizeof(tab))+%7B%0A++++++++printf(%22tab%5B%25d%5D+looks+safe+because+%25d+is+between+%5B0%3B%25d%5B%5Cn%22,+i,+i,+(int)sizeof(tab))%3B%0A++++++++return+tab%5Bi%5D%3B%0A++++%7D%0A%0A++++return+0%3B%0A%7D%0A%0Aint+main(int+ac,+char+**av)%0A%7B%0A++++return+f(atoi(av%5B1%5D))%3B%0A%7D'),l:'5',n:'0',o:'C+source+%231',t:'0')),k:50,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:cg122,deviceViewOpen:'1',filters:(b:'0',binary:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'0',libraryCode:'0',trim:'1'),flagsViewOpen:'1',fontScale:14,fontUsePx:'0',j:1,lang:___c,libs:!(),options:'',selection:(endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:1),l:'5',n:'0',o:'+x86-64+gcc+12.2+(Editor+%231)',t:'0')),k:50,l:'4',n:'0',o:'',s:0,t:'0')),l:'2',n:'0',o:'',t:'0')),version:4 https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename... [Edited. I originally wrote "It should be noted that this only happens when..." but inserted "in this particular case" after @eru pointed it out.]
t0suj4 4y ago
I think the lesson here is to stop using signed integer as an index into an array.
- eru 4y ago
  The lesson is to only use C when absolutely necessary, and regularly use all the sanitizers and other safety tools you can find. Not just when you suspect something fishy.
- sanxiyn 4y ago
  The lesson is you shouldn't use standard C, until the standard is fixed. Until then, compile with -fno-strict-overflow, like I do.
nly 4y ago
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.html https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins...
- nindalf 4y ago
  If these intrinsics are used can clang or msvc still compile it?
  - latency-guy2 4y ago
    Clang should, MSVC has plans for it but no news since 2018: https://developercommunity.visualstudio.com/t/please-implement-integer-overflow-detection/409051 https://developercommunity.visualstudio.com/t/please-impleme..., so looks like it's a blackhole for now
- saagarjha 4y ago
  The C standard (finally) fixed this in C23, see <stdckdint.h>.
  - codedokode 4y ago
    Sadly the macros they proposed are ugly, long to type and hard to read. People will not use them.
    - saagarjha 4y ago
      They seem reasonable to me? They're similar to the compiler builtins people already know and pretty short (7 characters…). What don't you like about them?
- josephcsible 4y ago
  > C standards fault. I take issue with this sentence, since it makes it sound like there's something wrong with the C standard for it, which isn't the case.
leni536 4y ago
In gcc you can use the -ftrapv or -fwrapv compiler options to get defined signed integer overflow arithmetic.
- sanxiyn 4y ago
  These also work on Clang.
pbsd 4y ago
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 https://rust.godbolt.org/z/xf67rM77T -- the difference being that there's a second language-level bounds-check inserted at the lookup site.
- comex 4y ago
  It doesn’t matter what x is. Without prior undefined behavior, there is no way to justify “if (i >= 0 && i < sizeof(tab))” passing when (as demonstrated by the printf) i is not actually in that range. Edit: Though, incidentally, the comparison does not work the way it was probably intended to work. In `i < sizeof(tab)`, `i` is converted to `size_t`, so an unsigned comparison is performed, making the `i >= 0` part redundant. But the result is the same as what was intended.
  - dathinab 4y ago
    That is not how undefined behavior works in C (or C++). Effects of UB are not temporal or spacial limited to the place where undefined behavior happens. The moment you enter a compilation unit (assuming no link optimizations) with a state which at some point will run into undefined behavior all bets are of. EDIT: Yes, UB can "time travel". Compared to that ignoring an if condition iff the UB code was triggered is harmless. Similar it can also "split realities". E.g. a value produced by UB might at one place have the value 1 and at another place a completely different value. E.g. unsigned int overflow values might for an if condition have one value and for the print statment in the condition another and for the index operation again a different value. EDIT2: Which is why a lot of people which have proper understanding of C++ and don't have a sunken (learn C++) cost fallacy came to the conclusion that using C++ is a bad choice for most use-case.
    - 4y ago
eru 4y ago
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.
pjmlp 4y ago
GCC's UBSan catches it, > runtime error: signed integer overflow: 50000000 * 511 cannot be represented in type 'int' https://godbolt.org/z/oz9vvj5YM 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 https://www.youtube.com/watch?v=vEtGtphI3lc
- saagarjha 4y ago
  Note that UBSan is a dynamic analysis tool.
  - pjmlp 4y ago
    Thanks for the correction, one should use those as well on debug builds for integration tests.
    - saagarjha 4y ago
      Agreed :)
  - eru 4y ago
    Indeed. But still a good idea to run at least your test-suite with it. And also with address sanitizer and clang's memory sanitizer, etc. Whatever you can find.
  - astrange 4y ago
    The static analysis is you compile with it and see if there's any trap instructions emitted by the compiler. (The answer is: yes.)
- yaantc 4y ago
  Yes absolutely, and this is possible today with only open source software. So money is not a barrier. The sanitizers (UB, address, memory, threads) are supported by both Clang and GCC [1]. Yes that's up to 4 different builds and tests runs but with an automated C/I this is not a big deal. The Clang static analyzer, with Z3 enabled as a checker, used through CodeChecker [2] is now very good, so much so that I prefer it to a different commercial product showing too many false alarms. Using it on an embedded GCC cross-compiled code base may still require some workarounds, but nothing too bad and this is improving regularly too. I wouldn't want to do without this. Switching to Rust may not always be possible, and there are big C and C++ code base that will live a long while. Tools like this help and they should be used. [1] https://github.com/google/sanitizers/ https://github.com/google/sanitizers/ [2] https://codechecker.readthedocs.io/en/latest/ https://codechecker.readthedocs.io/en/latest/
symmetricsaurus 4y ago
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?)
- josephcsible 4y ago
  Be careful: it's not just that the result of the multiplication won't be what you expect. The entire execution of the program becomes undefined. For example, if you had an unconditional `puts("hello");` between the multiplication and comparison lines, if the overflow happens, it would be allowed to print "goodbye" instead.
  - symmetricsaurus 4y ago
    Yes, and in particular the compiler can assume that you stay within the defined behavior. That's what's enabling the optimization in removing the i < 0 check.
eqvinox 4y ago
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
- colonwqbang 4y ago
  -fwrapv
- eru 4y ago
  `-fno-strict-overflow`
moring 4y ago
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.
- fisf 4y ago
  There really is no disagreement here. GCC implements a language. The intended users are people programming in that language, which implies some sort of proficiency. The author isn't aware of the pitfalls of said language. This is not about GCC.
  - unsafecast 4y ago
    Oh it is. The fact that you have to remember a (very lengthy) document and every single mention of undefined behavior in it just to be sure that the code that goes out of the compiler will somewhat resemble your mental model of it is, in my opinion, not a reasonable requirement. It really shouldn't be that difficult to wrap all these assumptions into a ‘if (can_exploit_ub)’. Then you can just pass something like -fno-exploit-ub and everybody's happy.
  - moring 4y ago
    That's just saying, "there is no disagreement because one side is clearly right, and the other is clearly wrong". Even if that were true, which is far from certain in this case, it doesn't preclude a disagreement. The argument about proficiency has been bruoght up multiple times already -- but only by one of the parties involved in the discussion, which shows that there is disagreement -- and besides that, makes a visit in literally every single discussion about usability.
avereveard 4y ago
question about the condition removal he's lamenting his code would have gotten an overflow at int32_t i = x * 0x1ff / 0xffff; where it not optimized away so it seems gcc is maintaining the code behaviour, only reporting a wrong debug line for it due code being shifted around.
- shultays 4y ago
  the part that was optimized away is `i >= 0` check. Which can't happen because x >= 0 already holds true
  - avereveard 4y ago
    it also moves the division around
PointyFluff 4y ago
- ranguna 4y ago
  It's free but why so critical? It's a blog, it's not like your handling sensitive information.
  - skozharinov 4y ago
    Because there are internet providers out in the wild that can and will insert some garbage into any unencrypted HTML page, including ads or phishing.
WalterBright 4y ago
D solved this particular problem by defining arithmetic as being 2-s complement, including wraparound behavior.
- eru 4y ago
  `-fno-strict-overflow` give you that behaviour in GCC and clang, too.
shultays 4y ago
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"
nullc 4y ago
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.
sanxiyn 4y ago
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.
rowanG077 4y ago
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.
codedokode 4y ago
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.
- MiguelX413 4y ago
  What's wrong with checked_add() and its friends in Rust?
  - codedokode 4y ago
    They are longer to type than `+`. It is easy to write unsafe code and difficult to write safe code. As a result, while most mathematical operations must be safe, developers use unsafe operations because they are easier to type and more readable. Operators like `+` should be equivalent to checked_add().unwrap(), not to unchecked_add(). Why choose unsafe and rarely used operation as a default? It is a mistake. Swift uses sane defaults. UPD: for example, let's say we need to allocate memory for N elements of size S and a header of size H. Here is the unsafe code: u32 s = N * S + H And here is safe code: u32 s = checked_add(checked_mul(N, S).unwrap(), H).unwrap() And here is safe code in Swift: let s: Uint32 = N * S + H And unsafe code in Swift: let s = N &* S &+ H
anfilt 4y ago
This probably just an example, but why are they using a signed int for indexing???
- mxmlnkn 4y ago
  I would also prefer unsigned indexes but exactly because the compiler may assume that there will be no overflow, signed index access may be a bit faster and therefore preferable.
  - account42 4y ago
    Is there a reason why the language doesn't provide UB-on-overflow (and wrappring overflow) for both unsigned and signed types? It always feels dirty deliberately using a signed type for something you know can never be neagtive just because that signed type has other properties you want.
    - anfilt 4y ago
      The newest C standard will define signed integers as 2's complement. Getting rid of this instance of UB. https://en.wikipedia.org/wiki/C2x https://en.wikipedia.org/wiki/C2x
  - anfilt 4y ago
    On most machines this days there is not really a performance difference between the math done on signed or unsigned integers. The only case would be if your wanting to the compiler to optimize on the fact that UB does exist. So like this in example "impossible things" get optimized out. The author here clearly does not want that.
- astrange 4y ago
  They're correct to do this. Signed integers have more UB, therefore you /should/ use them in all situations when overflow isn't going to happen, because you're not going to need that extra defined behavior. This lets you use UBSan most effectively and it's what the Google style guide says to do. (Exception if you care about micro-performance: * / >> operations can be a little faster on unsigned types IIRC)
Pabloski80 4y ago
Make C Safe Again. UBs in C language are the asleep plague just asking to get triggered into a głos bal disaster. Oops, too late. There is another class of those there, described in some papers for CSmith. Milder but still quite bad. Both got quietly not acted upon, when C++ got made. Lets go back to Pascal/Modula/Oberon.
p0nce 4y ago
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.
dxuh 4y ago
This is why I use unsigned integers for indices (and firmly believe most everyone should).
0x000xca0xfe 4y ago
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 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.
- sanxiyn 4y ago
  As I understand, the only ones' complement architecture in active use is UNIVAC (yes, believe or not UNIVAC is in active use and Unisys provides commercial support). Non-8-bit char is a bit more common, probably the most common is TMS320 C5000, see https://lists.llvm.org/pipermail/llvm-dev/2009-September/026027.html https://lists.llvm.org/pipermail/llvm-dev/2009-September/026... for an example. As far as I know there is no GCC port, but it could very well have one, after all TMS320 C6000 port is upstream in GCC. (It is c6x in your table.)
  - 0x000xca0xfe 4y ago
    Interesting, thanks. So the c5x (if it would be in the list) has 16-bit bytes and the c6x the usual 8-bit bytes. Do you happen to know what compiler/language the UNIVAC folks use?
    - sanxiyn 4y ago
      Wikipedia has pointers here: https://en.wikipedia.org/wiki/Unisys_OS_2200_programming_languages https://en.wikipedia.org/wiki/Unisys_OS_2200_programming_lan.... It seems links are now broken, but googling e.g. "Unisys publication 7831 0448" etc. should lead you to correct documents.
nsajko 4y ago
It's rude to spam bug reports like that. GCC has a mailing list, if a discussion is what you want.
skozharinov 4y ago
Well, that's undefined behaviour. It could have inserted system("rm -rf /*"); instead and be right about that.
xg15 4y ago
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".
ohdannyboy 4y ago
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.

156 points by signa11 4y ago

This is why undefined behaviour is insidious: if a tiny part of your code is undefined behaviour, the behaviour of your entire programme is.

josephcsible 4y ago
Nitpick: it's not the behavior of the program that becomes undefined, but of the execution that it occurs in. For example, consider a program that reads argv[3] without making sure there's at least 4 arguments. If you call it with too few arguments, that entire execution is undefined (even stuff that happens before the out-of-bounds access), but if you call it with enough arguments, it is well-defined and the compiler has to emit code that will work.
- masklinn 4y ago
  Ah but the trap is that if the compiler can reason that UB always occurs (in reality it will reason that code is dead because the constraints it computes don’t allow for its execution) then it can remove the entire thing. See Raymond Chen’s well known “undefined behaviour can result in time travel”.
  - josephcsible 4y ago
    Sure, but if UB always occurs, then every execution is undefined, so doesn't what I said still hold? (And the time travel is what I meant by "even stuff that happens before the out-of-bounds access".)
eru 4y ago
Yes. To spell it out: undefined behaviour doesn't just affect specific values nor just the behaviour of your program after triggering UB. It's the entire behaviour of your programme. So UB can 'travel backwards in time'. Fun fact: not closing a string literal is UB. Ending a non-empty source file in anything other than a newline is also UB.

mlindner 4y ago

> 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.

josefx 4y ago
Of course with well defined overflow you can still end up with a nonsense result that just happens to be in your valid range of values. If you don't plan to harden your code against integer overflow manually you need a language that actively checks it for you or uses a variable sized integer to be safe.
- p0nce 4y ago
  Ah someone else spotted it. The author's code is wrong whether signed overflow is well defined or not.
- ekidd 4y ago
  I've spent a fair bit of time running a fuzzer on Rust code that parses untrustworthy data. And the thing that saved my code time and time again was that Rust has runtime bounds checks. Even if I messed up index calculations, I'd get a controlled panic, not a vulnerability.
- eru 4y ago
  Ending up with a nonsense result ain't great, but it's still a step up from losing all guarantees about the behaviour of your program. By the way, throwing an error on overflow is also a perfectly valid way to get defined behaviour and not end up with a nonsense value.
- deleted 4y ago
  [deleted]
- silon42 4y ago
  He did harden the code by having an explicit range check.

josephcsible 4y ago

If this kind of optimization is unacceptably risky for your use case, you need a different programming language, not a different C compiler.

turminal 4y ago
Do you have any specific languages in mind?
- matkoniecz 4y ago
  Author of linked article mentions Rust
  - turminal 4y ago
    Rust is a good replacement for most use cases, but I think specifically in case where you're looking for a more predictable and less risky implicit behavior, the replacement should be more stable and predictable than Rust is at the moment.
    - matkoniecz 4y ago
      What kind of language is C replacement without UB and better concurrency and more stable/predictable than Rust?
      - mlindner 4y ago
        Question, but where do you get the idea that Rust is not stable or predictable? I understand you were asking for something _more_ stable/predictable than Rust, but Rust is already very stable and very predictable (in fact I can't think of any ways that Rust is "unpredictable").
  - JonChesterfield 4y ago
    Fun thing there is rust feeds into the same optimisation pipeline as C or C++, so there's a definite risk of it inheriting some of their semantics via errors in the compiler implementation.

32gbsd 4y ago

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.

ototot 4y ago
This is not a bug. This is the model of C. You should blame C not GCC.
- iforgotpassword 4y ago
  I blame GCC. The C standards committee is some out of touch with reality conglomerate working in a vacuum, taking 50 years of language history into account. I expect my compiler vendor to be on my side, ie produce a compiler that helps me write good software and not get in my way. GCC is doing the opposite, it's deliberately looking to use the standard to fuck me over in the most subtle and unexpected ways. Signed integer overflow is undefined; that gives compiler authors the liberty to make it do anything they want, including well defined things that anyone would expect and find useful. But GCC decides to fuck you over so their devs can give you an arrogant reply and impose their superiority if you show up on their bug tracker.
  - astrange 4y ago
    GCC's developers work for companies that want more optimizations. UB is the way you get these optimizations. But "gcc -fsanitize=undefined" is just as easy to run as "gcc -O3" is.
  - saagarjha 4y ago
    Turns out people get upset when their code goes slower because the the compiler added traps on signed overflow.
    - iforgotpassword 4y ago
      Don't add traps, just let it overflow and don't fuck up any bounds checks the programmer added.

vgatherps 4y ago

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”

proto_lambda 4y ago
The problem here is that the thing that "can't happen" isn't actually something that can't happen, it's something that isn't allowed to happen according to a many-hundred-page document that approximately nobody reads. It's not something that can be optimised because the compiler can prove it cannot happen, it is allowed to be optimised because the standard says "dear programmer, if you ever make this happen, god help you".
- iforgotpassword 4y ago
  It's still braindead and idiotic. Every relevant platform nowadays has well defined overflow for signed ints. A sane C compiler should go with that and base its optimizations on it. GCC has been a pile of garbage in this regard for many years now. Its devs get further removed from reality with every year. Treating signed int overflow as undefined should be hidden behind a flag.
  - 4y ago

FpUser 4y ago

I am sort of uneasy with what the optimizing doing in here. But I would not ever write something like this: int32_t i = x * 0x1ff / 0xffff; Not because I am supersmart and will / can predict how optimizer will fuck it up. It is just that I am paranoid when coding and this type of code just simply hurts my perception for some reason.

saagarjha 4y ago
It seems like a perfectly cromulent line of code to me, assuming you have overflow checks somewhere.
- Karliss 4y ago
  The trap in C is that you can't have overflow checks after the calculations testing if overflow happened by making assumptions about what the UB does. Once the UB has happened it's already too late. What you actually need is input range checks to ensure that following code can perform it's calculations correctly without hitting UB or you need to use helper intrinsics which perform checked math operations.
- FpUser 4y ago
  As already said it just ruffles my feathers the wrong way. I would not analyze why as I usually have better things to do with my programming time. The best answer I can come up with without thinking is something like this: overflow is an error. I would prefer the code not to create errors unless absolutely needed.
eru 4y ago
This is the minimal example. For all we know, the original code might have made more sense in context?

hxhxhrra 4y ago

As others are pointing out, the C standard does allow this. There is no safe way to check for undefined behavior (UB) after it has happened, because the whole program is immediately invalidated. 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/ https://lwn.net/Articles/342330/

charcircuit 4y ago
>the C standard does allow this The C standard also allows doing it even when there is no UB. C gives implementations a ton of freedom.
xeeeeeeeeeeenu 4y ago
>Linux kernel is now compiled with -fno-delete-null-pointer-checks Like many other large C codebases, it also uses -fno-strict-aliasing and -fno-strict-overflow (which is a synonym for "-fwrapv -fwrapv-pointer").
- fps_doug 4y ago
  We've got a few components written in C that I'm (partially) responsible for. It's mostly maintenance, but for reasons like this I run that code with -O0 in production, and add all those kinds of flags. I'd be curious to know how much production code today that's written in C is that performance critical, i.e. depends on all those bonkers exploits of UB for optimizations. The Linux kernel seems to do fine without this.
  - NohatCoder 4y ago
    I'm fairly confident in declaring the answer to your question: None. Most programs rarely issue all the instructions that a CPU can handle simultaneously, they are stuck waiting on memory or linear dependencies. An extra compile-out-able conditional typically doesn't touch memory and is off the linear dependency path, which makes it virtually free. So the actual real-world overhead ends up at less than 1%, but in most cases something that is indistinguishable from 0. If you care that much about 1% you are probably already writing the most performance critical parts in Assembly anyway.

Phelinofist 4y ago

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

proto_lambda 4y ago
It's just an artifact of decompilation. It's the same operation in machine code (checking the MSB), there's no way to tell which one was used in the original source code.
stop50 4y ago
An signed integer uses the leftmost bit for the sign: 00000000 = 0 10000000 = 128 = -128 https://onlinetoolz.net/unsigned-signed#base=2&value=10000000&bits=8 https://onlinetoolz.net/unsigned-signed#base=2&value=1000000...

WirelessGigabit 4y ago

What the purpose of the / 0xffff?

f1shy 4y ago
Had the same question. This is the minimal implementation of the error, so there is no clue what was the original purpose. I think as it is, it indexes a table where the first positions return tab[0], the next ffff/1ff will return tab[1] and so on. If I see such a code at work I would reject it in less than 1ms

hddqsb 4y ago

It should be noted that in this particular case it only happens when optimisations are enabled (-O2). With -O2: https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:___c,selection:(endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:'%23include+%3Cstdint.h%3E%0A%23include+%3Cstdio.h%3E%0A%23include+%3Cstdlib.h%3E%0A%0Auint8_t+tab%5B0x1ff+%2B+1%5D%3B%0A%0Auint8_t+f(int32_t+x)%0A%7B%0A++++if+(x+%3C+0)%0A++++++++return+0%3B%0A++++int32_t+i+%3D+x+*+0x1ff+/+0xffff%3B%0A++++if+(i+%3E%3D+0+%26%26+i+%3C+sizeof(tab))+%7B%0A++++++++printf(%22tab%5B%25d%5D+looks+safe+because+%25d+is+between+%5B0%3B%25d%5B%5Cn%22,+i,+i,+(int)sizeof(tab))%3B%0A++++++++return+tab%5Bi%5D%3B%0A++++%7D%0A%0A++++return+0%3B%0A%7D%0A%0Aint+main(int+ac,+char+**av)%0A%7B%0A++++return+f(atoi(av%5B1%5D))%3B%0A%7D'),l:'5',n:'0',o:'C+source+%231',t:'0')),k:50,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:cg122,deviceViewOpen:'1',filters:(b:'0',binary:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'0',libraryCode:'0',trim:'1'),flagsViewOpen:'1',fontScale:14,fontUsePx:'0',j:1,lang:___c,libs:!(),options:'-O2',selection:(endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:1),l:'5',n:'0',o:'+x86-64+gcc+12.2+(Editor+%231)',t:'0')),k:50,l:'4',n:'0',o:'',s:0,t:'0')),l:'2',n:'0',o:'',t:'0')),version:4 https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename... Without -O2: https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:___c,selection:(endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:'%23include+%3Cstdint.h%3E%0A%23include+%3Cstdio.h%3E%0A%23include+%3Cstdlib.h%3E%0A%0Auint8_t+tab%5B0x1ff+%2B+1%5D%3B%0A%0Auint8_t+f(int32_t+x)%0A%7B%0A++++if+(x+%3C+0)%0A++++++++return+0%3B%0A++++int32_t+i+%3D+x+*+0x1ff+/+0xffff%3B%0A++++if+(i+%3E%3D+0+%26%26+i+%3C+sizeof(tab))+%7B%0A++++++++printf(%22tab%5B%25d%5D+looks+safe+because+%25d+is+between+%5B0%3B%25d%5B%5Cn%22,+i,+i,+(int)sizeof(tab))%3B%0A++++++++return+tab%5Bi%5D%3B%0A++++%7D%0A%0A++++return+0%3B%0A%7D%0A%0Aint+main(int+ac,+char+**av)%0A%7B%0A++++return+f(atoi(av%5B1%5D))%3B%0A%7D'),l:'5',n:'0',o:'C+source+%231',t:'0')),k:50,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:cg122,deviceViewOpen:'1',filters:(b:'0',binary:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'0',libraryCode:'0',trim:'1'),flagsViewOpen:'1',fontScale:14,fontUsePx:'0',j:1,lang:___c,libs:!(),options:'',selection:(endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:1),l:'5',n:'0',o:'+x86-64+gcc+12.2+(Editor+%231)',t:'0')),k:50,l:'4',n:'0',o:'',s:0,t:'0')),l:'2',n:'0',o:'',t:'0')),version:4 https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename... [Edited. I originally wrote "It should be noted that this only happens when..." but inserted "in this particular case" after @eru pointed it out.]

t0suj4 4y ago

I think the lesson here is to stop using signed integer as an index into an array.

eru 4y ago
The lesson is to only use C when absolutely necessary, and regularly use all the sanitizers and other safety tools you can find. Not just when you suspect something fishy.
sanxiyn 4y ago
The lesson is you shouldn't use standard C, until the standard is fixed. Until then, compile with -fno-strict-overflow, like I do.

nly 4y ago

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.html https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins...

nindalf 4y ago
If these intrinsics are used can clang or msvc still compile it?
- latency-guy2 4y ago
  Clang should, MSVC has plans for it but no news since 2018: https://developercommunity.visualstudio.com/t/please-implement-integer-overflow-detection/409051 https://developercommunity.visualstudio.com/t/please-impleme..., so looks like it's a blackhole for now
saagarjha 4y ago
The C standard (finally) fixed this in C23, see <stdckdint.h>.
- codedokode 4y ago
  Sadly the macros they proposed are ugly, long to type and hard to read. People will not use them.
  - saagarjha 4y ago
    They seem reasonable to me? They're similar to the compiler builtins people already know and pretty short (7 characters…). What don't you like about them?
josephcsible 4y ago
> C standards fault. I take issue with this sentence, since it makes it sound like there's something wrong with the C standard for it, which isn't the case.

leni536 4y ago

In gcc you can use the -ftrapv or -fwrapv compiler options to get defined signed integer overflow arithmetic.

sanxiyn 4y ago
These also work on Clang.

pbsd 4y ago

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 https://rust.godbolt.org/z/xf67rM77T -- the difference being that there's a second language-level bounds-check inserted at the lookup site.

comex 4y ago
It doesn’t matter what x is. Without prior undefined behavior, there is no way to justify “if (i >= 0 && i < sizeof(tab))” passing when (as demonstrated by the printf) i is not actually in that range. Edit: Though, incidentally, the comparison does not work the way it was probably intended to work. In `i < sizeof(tab)`, `i` is converted to `size_t`, so an unsigned comparison is performed, making the `i >= 0` part redundant. But the result is the same as what was intended.
- dathinab 4y ago
  That is not how undefined behavior works in C (or C++). Effects of UB are not temporal or spacial limited to the place where undefined behavior happens. The moment you enter a compilation unit (assuming no link optimizations) with a state which at some point will run into undefined behavior all bets are of. EDIT: Yes, UB can "time travel". Compared to that ignoring an if condition iff the UB code was triggered is harmless. Similar it can also "split realities". E.g. a value produced by UB might at one place have the value 1 and at another place a completely different value. E.g. unsigned int overflow values might for an if condition have one value and for the print statment in the condition another and for the index operation again a different value. EDIT2: Which is why a lot of people which have proper understanding of C++ and don't have a sunken (learn C++) cost fallacy came to the conclusion that using C++ is a bad choice for most use-case.
  - 4y ago

eru 4y ago

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.

pjmlp 4y ago

GCC's UBSan catches it, > runtime error: signed integer overflow: 50000000 * 511 cannot be represented in type 'int' https://godbolt.org/z/oz9vvj5YM 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 https://www.youtube.com/watch?v=vEtGtphI3lc

saagarjha 4y ago
Note that UBSan is a dynamic analysis tool.
- pjmlp 4y ago
  Thanks for the correction, one should use those as well on debug builds for integration tests.
  - saagarjha 4y ago
    Agreed :)
- eru 4y ago
  Indeed. But still a good idea to run at least your test-suite with it. And also with address sanitizer and clang's memory sanitizer, etc. Whatever you can find.
- astrange 4y ago
  The static analysis is you compile with it and see if there's any trap instructions emitted by the compiler. (The answer is: yes.)
yaantc 4y ago
Yes absolutely, and this is possible today with only open source software. So money is not a barrier. The sanitizers (UB, address, memory, threads) are supported by both Clang and GCC [1]. Yes that's up to 4 different builds and tests runs but with an automated C/I this is not a big deal. The Clang static analyzer, with Z3 enabled as a checker, used through CodeChecker [2] is now very good, so much so that I prefer it to a different commercial product showing too many false alarms. Using it on an embedded GCC cross-compiled code base may still require some workarounds, but nothing too bad and this is improving regularly too. I wouldn't want to do without this. Switching to Rust may not always be possible, and there are big C and C++ code base that will live a long while. Tools like this help and they should be used. [1] https://github.com/google/sanitizers/ https://github.com/google/sanitizers/ [2] https://codechecker.readthedocs.io/en/latest/ https://codechecker.readthedocs.io/en/latest/

symmetricsaurus 4y ago

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?)

josephcsible 4y ago
Be careful: it's not just that the result of the multiplication won't be what you expect. The entire execution of the program becomes undefined. For example, if you had an unconditional `puts("hello");` between the multiplication and comparison lines, if the overflow happens, it would be allowed to print "goodbye" instead.
- symmetricsaurus 4y ago
  Yes, and in particular the compiler can assume that you stay within the defined behavior. That's what's enabling the optimization in removing the i < 0 check.

eqvinox 4y ago

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

colonwqbang 4y ago
-fwrapv
eru 4y ago
`-fno-strict-overflow`

moring 4y ago

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.

fisf 4y ago
There really is no disagreement here. GCC implements a language. The intended users are people programming in that language, which implies some sort of proficiency. The author isn't aware of the pitfalls of said language. This is not about GCC.
- unsafecast 4y ago
  Oh it is. The fact that you have to remember a (very lengthy) document and every single mention of undefined behavior in it just to be sure that the code that goes out of the compiler will somewhat resemble your mental model of it is, in my opinion, not a reasonable requirement. It really shouldn't be that difficult to wrap all these assumptions into a ‘if (can_exploit_ub)’. Then you can just pass something like -fno-exploit-ub and everybody's happy.
- moring 4y ago
  That's just saying, "there is no disagreement because one side is clearly right, and the other is clearly wrong". Even if that were true, which is far from certain in this case, it doesn't preclude a disagreement. The argument about proficiency has been bruoght up multiple times already -- but only by one of the parties involved in the discussion, which shows that there is disagreement -- and besides that, makes a visit in literally every single discussion about usability.

avereveard 4y ago

question about the condition removal he's lamenting his code would have gotten an overflow at int32_t i = x * 0x1ff / 0xffff; where it not optimized away so it seems gcc is maintaining the code behaviour, only reporting a wrong debug line for it due code being shifted around.

shultays 4y ago
the part that was optimized away is `i >= 0` check. Which can't happen because x >= 0 already holds true
- avereveard 4y ago
  it also moves the division around

PointyFluff 4y ago

ranguna 4y ago
It's free but why so critical? It's a blog, it's not like your handling sensitive information.
- skozharinov 4y ago
  Because there are internet providers out in the wild that can and will insert some garbage into any unencrypted HTML page, including ads or phishing.

WalterBright 4y ago

D solved this particular problem by defining arithmetic as being 2-s complement, including wraparound behavior.

eru 4y ago
`-fno-strict-overflow` give you that behaviour in GCC and clang, too.

shultays 4y ago

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"

nullc 4y ago

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.

sanxiyn 4y ago

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.

rowanG077 4y ago

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.

codedokode 4y ago

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.

MiguelX413 4y ago
What's wrong with checked_add() and its friends in Rust?
- codedokode 4y ago
  They are longer to type than `+`. It is easy to write unsafe code and difficult to write safe code. As a result, while most mathematical operations must be safe, developers use unsafe operations because they are easier to type and more readable. Operators like `+` should be equivalent to checked_add().unwrap(), not to unchecked_add(). Why choose unsafe and rarely used operation as a default? It is a mistake. Swift uses sane defaults. UPD: for example, let's say we need to allocate memory for N elements of size S and a header of size H. Here is the unsafe code: u32 s = N * S + H And here is safe code: u32 s = checked_add(checked_mul(N, S).unwrap(), H).unwrap() And here is safe code in Swift: let s: Uint32 = N * S + H And unsafe code in Swift: let s = N &* S &+ H

anfilt 4y ago

This probably just an example, but why are they using a signed int for indexing???

mxmlnkn 4y ago
I would also prefer unsigned indexes but exactly because the compiler may assume that there will be no overflow, signed index access may be a bit faster and therefore preferable.
- account42 4y ago
  Is there a reason why the language doesn't provide UB-on-overflow (and wrappring overflow) for both unsigned and signed types? It always feels dirty deliberately using a signed type for something you know can never be neagtive just because that signed type has other properties you want.
  - anfilt 4y ago
    The newest C standard will define signed integers as 2's complement. Getting rid of this instance of UB. https://en.wikipedia.org/wiki/C2x https://en.wikipedia.org/wiki/C2x
- anfilt 4y ago
  On most machines this days there is not really a performance difference between the math done on signed or unsigned integers. The only case would be if your wanting to the compiler to optimize on the fact that UB does exist. So like this in example "impossible things" get optimized out. The author here clearly does not want that.
astrange 4y ago
They're correct to do this. Signed integers have more UB, therefore you /should/ use them in all situations when overflow isn't going to happen, because you're not going to need that extra defined behavior. This lets you use UBSan most effectively and it's what the Google style guide says to do. (Exception if you care about micro-performance: * / >> operations can be a little faster on unsigned types IIRC)

Pabloski80 4y ago

Make C Safe Again. UBs in C language are the asleep plague just asking to get triggered into a głos bal disaster. Oops, too late. There is another class of those there, described in some papers for CSmith. Milder but still quite bad. Both got quietly not acted upon, when C++ got made. Lets go back to Pascal/Modula/Oberon.

p0nce 4y ago

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.

dxuh 4y ago

This is why I use unsigned integers for indices (and firmly believe most everyone should).

0x000xca0xfe 4y ago

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 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.

sanxiyn 4y ago
As I understand, the only ones' complement architecture in active use is UNIVAC (yes, believe or not UNIVAC is in active use and Unisys provides commercial support). Non-8-bit char is a bit more common, probably the most common is TMS320 C5000, see https://lists.llvm.org/pipermail/llvm-dev/2009-September/026027.html https://lists.llvm.org/pipermail/llvm-dev/2009-September/026... for an example. As far as I know there is no GCC port, but it could very well have one, after all TMS320 C6000 port is upstream in GCC. (It is c6x in your table.)
- 0x000xca0xfe 4y ago
  Interesting, thanks. So the c5x (if it would be in the list) has 16-bit bytes and the c6x the usual 8-bit bytes. Do you happen to know what compiler/language the UNIVAC folks use?
  - sanxiyn 4y ago
    Wikipedia has pointers here: https://en.wikipedia.org/wiki/Unisys_OS_2200_programming_languages https://en.wikipedia.org/wiki/Unisys_OS_2200_programming_lan.... It seems links are now broken, but googling e.g. "Unisys publication 7831 0448" etc. should lead you to correct documents.

nsajko 4y ago

It's rude to spam bug reports like that. GCC has a mailing list, if a discussion is what you want.

skozharinov 4y ago

Well, that's undefined behaviour. It could have inserted system("rm -rf /*"); instead and be right about that.

xg15 4y ago

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".

ohdannyboy 4y ago

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.