8 ms·

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 ma

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

josephcsible 4y ago
I think this view is slightly unfair. I think of UB as the compiler saying "when you promised this thing wouldn't happen, I took you at your word. If bad things happen because you lied, they're your fault, not mine."
- proto_lambda 4y ago
  Lying requires intent. This was a mistake, something that humans are well-known for making, and if the compiler is designed to assume otherwise, it borders on useless in the real world.
  - baq 4y ago
    And yet C is still the dominant language. Undefined behavior is actually the reason why: any defined behavior is expensive to implement in the compiler and possibly incurs a cost at runtime. The language design intentionally trades programmer’s sanity for ease of implementation.
    - pjmlp 4y ago
      Legacy reasons, most embedded devs and UNIX clones won't use anything else. In many other domains, other languages have taken their place, and this will keep on going, even if it takes a couple of generations, or goverment cybersecurity mandatates to make it happen.
    - eru 4y ago
      Not sure that's actually the reason in practice? For a real prominent counterexample: the Linux kernel is intentionally programmed in a C dialect (defined by a myriad of GCC compiler flags) that removes a lot of UB. If they craved the Faustian bargain of UB for speed, they could immediately move in that direction by dropping some GCC options.
    - adwn 4y ago
      > The language design intentionally trades programmer’s sanity for ease of implementation. There's nothing "easy" at all about UB-exploiting performance optimizations in modern C compilers, and "ease of implementation" is absolutely not why those optimization passes have been included. In fact, the easiest thing for the compiler to do, when it sees an int * int operation, is to emit an IMUL assembly instruction (or the equivalent for your CPU architecture) and not worry about deleting overflow checking code. Which is what C compilers did before the extent of UB exploitation became excessive.
      - baq 4y ago
        I agree on the top compilers but there are dozens if not hundreds architectures with their own proprietary C compilers maintained by a dinosaur and a couple intern dino chicks if they’re lucky. I postulate any other language wouldn’t be implemented or would be defanged to C-level of (non)safety anyway in a way similar to mrustc.
  - eru 4y ago
    That's C for you. If you want something saner, use Rust or Haskell or Python or even Java or Go or.. almost any other language that's not C or C++. These days the whole point of C is this Faustian pact with the devil of speed for sanity.
    - pca006132 4y ago
      I think Rust doesn't allow integer overflow either, unless you specifically use the wrapping_* operations. Probably the same kind of thing will also happen to Rust.
      - masklinn 4y ago
        Rust either allows or traps on integer overflow depending on the mode. Either way it’s defined behaviour.
        pca006132 4y ago
        Ah, I forgot that it is also defined in release mode, but just considered undesirable.
    - consp 4y ago
      Writing Rust and Haskell for sanity is not something I would agree with. Maybe for language characteristics but reading those make me jump out of the window.
      - eru 4y ago
        I have the same issue with Java and Go. (Which I brought up as well.) Yet, they still compare favourably with C in this regard. Almost anything does.
  - masklinn 4y ago
    A compiler can’t know why you fucked up, it can’t even know that you fucked up, because UBs are just ways for it to infer and propagate constraints. If an optimising C compiler can’t rely on UBs not happening, its potential is severely cut down due to the dearth of useful information provided by C’s type system.
    - eru 4y ago
      > A compiler can’t know why you fucked up, it can’t even know that you fucked up, because UBs are just ways for it to infer and propagate constraints. To be honest, that's just how compiler writers interpret UB these days. It's perfectly possible (in principle) to use lots of more sophisticated static and dynamic analysis to recover much of what C compiler just assume. You don't have to restrict yourself to what C's type system provides. (For an example of what's possible, have a look at all the great techniques employed to make JavaScript as fast as possible. They have basically no static types to work with at all.)
      - masklinn 4y ago
        > For an example of what's possible, have a look at all the great techniques employed to make JavaScript as fast as possible. They have basically no static types to work with at all. I’m sure people will be very happy with a C JIT. That’s definitely what they use C for. JIT-ed code is full of runtime type and range assertions which bail if the compiler’s assumptions are incorrect.
        eru 4y ago
        Oh, I didn't mean to imply that it would be practical. Only that it's possible and that the type system isn't the only thing you can rely on. Instead of just assuming that 'x > x + 1' is always true (for signed integers), the compiler could also do the heavy lifting of static analysis (for cases where that's possible).
        littlestymaar 4y ago
  - andrewaylett 4y ago
    C has always considered that the programmer knows what they are doing. Programs are assumed correct unless proven invalid. This is -- or at least was -- a feature, not a bug. You can implement any valid program, but you can also implement some invalid programs. I know the OP mentioned Rust, but it's a valid comparison: if you don't invoke "unsafe" then all your behaviour is well-defined. But the trade-off is that Rust will only let you implement a subset of valid programs unless you invoke "unsafe", which might be better termed "assumed correct".
- spullara 4y ago
  Does the compiler know? If so, can't they have a flag that doesn't allow UB?
  - pca006132 4y ago
    Doesn't allow optimization enabled by this specific UB: Yes Does't allow UB: Hard, because you probably need runtime checks.
- oxff 4y ago
  This is a good positive model of UB, fulfilling the compiler assumptions.
- afiori 4y ago
  I don't think this is a fair comparison as this is all based on implicit inferences by the compiler. If the programmer had specifically invoked the "__assert_valid_pointer(p)" standard function (which does not exists) to promise the compile that the pointer was valid then it would be fine. The problem is that there are a lot of places where the compiler makes these assumptions.
- imtringued 4y ago
  "and I'm going to kill you for it even though I could also just slap 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.
- masklinn 4y ago
  Signed int overflow being UB is one of the most basic UBs of the language, and what allows generating tight code in loops. This is not new, -fwrapv was introduced in 2003, but it can quite severely impact code quality, if you don’t care, just set that. Then complain that C is slow, because C is a shit language.
  - iforgotpassword 4y ago
    > and what allows generating tight code in loops. How so? How does breaking an if statement the programmer added make the code faster? If they intended the check not to happen/be required, they wouldn't have written it. Let signed int overflow and leave any code that depends on its value alone. So yes maybe make fwrapv the default. > because C is a shit language. Well, it's as low level as it can get before reaching assembly, but why not try reducing the number of foot guns? Sometimes you still need C, and that's not going to go away for the foreseeable future.
    - masklinn 4y ago
      > How does breaking an if statement the programmer added make the code faster? If they intended the check not to happen/be required, they wouldn't have written it. See your problem is that you’re 1. not thinking like a compiler 2. and reasoning on an isolated example The compiler does not “break an if statement”, the compiler uses the UB to limit the range of the input and output, it can then propagate this range analysis to see that the check is dead code, and so removes the dead code. It’s common for users to write unnecessary or redundant checks, even more so because of inlining, and especially macros. If you’re carefully checking for null in every function prologue, and the compiler in-line everything and knows the pointer is non-null, all checks are dead and can be removed. Which is what the compiler does. This reduces the amount of branches (and thus the space needed by the branch predictor), and reduces the amount of code meaning the new inlined function could fall below threshold and itself become a candidate for inlining.
raverbashing 4y ago
Except this can't happen happens many and many times in practice so maybe it's time the language bureaucrats got off their high horse (but they won't)
pjmlp 4y ago
Even if someone would read all those pages, constraining ourselves to ISO C only, no way that after an year they would still remeber the about 200 UB cases that are documented there. Which is why everyone should adopt static analysis tooling and enable all the warnings that are related to UB, pointer and casts misuses. Many think they know better, it is like those that think builders don't need protection gear at a construction site, it is stuff only for the weak.
- gpderetta 4y ago
  I think implicitly compiler-added runtime check are a more robust and reliable solution than static analysis. For example for pointer dereferences the compiler should could 0-offset dummy load if the load is not guaranteed to be within a page of the pointer. Or adding abort-on-overflow for math. Or bound checking where possible. It will have a non-trivial cost, but hopefully aggressive optimizations can remove many of these checks (which ironically it is exactly the kind of optimizations people are complaining about) and compilers provide pragmas to disable them when critical. In a way sanitizers are getting there, but they are explicitly marked as for non-production use which is a problem.
  - pjmlp 4y ago
    I agree, but unfortunely that will never happen in most C and C++ circles, just see the heat JF Bastien has been facing for a feature that has been shipping in Windows and Android for the last two years, proven in the battlefield to hardly hinder performance in real use cases. https://isocpp.org/files/papers/P2723R0.html https://isocpp.org/files/papers/P2723R0.html Lots of people telling him it will never fly in production, while their Windows and Android phones are using the code that they say isn't good enough.
    - gpderetta 4y ago
      Zero initialization is also one of those features that seems such a low hanging fruit to implement... I'm still moderately optimistic. I suspect that many of these checks will end up being enabled by default on compilers shipped by distros, like stack guards and other forms of hardening.
Asooka 4y ago
Basically, the compiler implements integer addition using an operation that doesn't match the semantics of integer addition in the standard, then hallucinates that it did. That is: 1) The compiler sees an expression like "a += b;" where a and b are signed integers. 2) It emits "add rA rB" in x86 assembly (rA/B being the register a/b is currently in). 3) Technically the machine code emitted does not match the semantics of the source code, since it uses wraparound addition, whereas the C standard says that for the operation to be valid, the values of a and b must be such that no overflow would occur. This is fine however, because the implementation has the freedom to do anything on integer overflow, including just punting the problem to hardware as it did in this case. 4) The compiler proceeds with the rest of the code as if the line above would never overflow. My brother in the machine spirit, you chose to translate my program to a form where integer overflow is defined. The compiler should either a) trap on integer overflow; or b) accept integer overflow. It will be fine if it chooses either a) or b) situationally, i.e. if we have a loop where assuming no overflow is faster, then by all means - add a precondition check and crash the program if it's false, but don't just assume overflow doesn't happen when you explicitly emit code with well-defined overflow semantics. The bigger problem is there is pretty much no way to guard against this. The moment your program is longer than one page you're screwed. You may think all your functions are fine, but then you call something from some library, the compiler does some inlining and suddenly there's an integer overflow where you didn't expect, leading to your bounds check being deleted.

josephcsible 4y ago

I think this view is slightly unfair. I think of UB as the compiler saying "when you promised this thing wouldn't happen, I took you at your word. If bad things happen because you lied, they're your fault, not mine."

proto_lambda 4y ago
Lying requires intent. This was a mistake, something that humans are well-known for making, and if the compiler is designed to assume otherwise, it borders on useless in the real world.
- baq 4y ago
  And yet C is still the dominant language. Undefined behavior is actually the reason why: any defined behavior is expensive to implement in the compiler and possibly incurs a cost at runtime. The language design intentionally trades programmer’s sanity for ease of implementation.
  - pjmlp 4y ago
    Legacy reasons, most embedded devs and UNIX clones won't use anything else. In many other domains, other languages have taken their place, and this will keep on going, even if it takes a couple of generations, or goverment cybersecurity mandatates to make it happen.
  - eru 4y ago
    Not sure that's actually the reason in practice? For a real prominent counterexample: the Linux kernel is intentionally programmed in a C dialect (defined by a myriad of GCC compiler flags) that removes a lot of UB. If they craved the Faustian bargain of UB for speed, they could immediately move in that direction by dropping some GCC options.
  - adwn 4y ago
    > The language design intentionally trades programmer’s sanity for ease of implementation. There's nothing "easy" at all about UB-exploiting performance optimizations in modern C compilers, and "ease of implementation" is absolutely not why those optimization passes have been included. In fact, the easiest thing for the compiler to do, when it sees an int * int operation, is to emit an IMUL assembly instruction (or the equivalent for your CPU architecture) and not worry about deleting overflow checking code. Which is what C compilers did before the extent of UB exploitation became excessive.
    - baq 4y ago
      I agree on the top compilers but there are dozens if not hundreds architectures with their own proprietary C compilers maintained by a dinosaur and a couple intern dino chicks if they’re lucky. I postulate any other language wouldn’t be implemented or would be defanged to C-level of (non)safety anyway in a way similar to mrustc.
- eru 4y ago
  That's C for you. If you want something saner, use Rust or Haskell or Python or even Java or Go or.. almost any other language that's not C or C++. These days the whole point of C is this Faustian pact with the devil of speed for sanity.
  - pca006132 4y ago
    I think Rust doesn't allow integer overflow either, unless you specifically use the wrapping_* operations. Probably the same kind of thing will also happen to Rust.
    - masklinn 4y ago
      Rust either allows or traps on integer overflow depending on the mode. Either way it’s defined behaviour.
      - pca006132 4y ago
        Ah, I forgot that it is also defined in release mode, but just considered undesirable.
  - consp 4y ago
    Writing Rust and Haskell for sanity is not something I would agree with. Maybe for language characteristics but reading those make me jump out of the window.
    - eru 4y ago
      I have the same issue with Java and Go. (Which I brought up as well.) Yet, they still compare favourably with C in this regard. Almost anything does.
- masklinn 4y ago
  A compiler can’t know why you fucked up, it can’t even know that you fucked up, because UBs are just ways for it to infer and propagate constraints. If an optimising C compiler can’t rely on UBs not happening, its potential is severely cut down due to the dearth of useful information provided by C’s type system.
  - eru 4y ago
    > A compiler can’t know why you fucked up, it can’t even know that you fucked up, because UBs are just ways for it to infer and propagate constraints. To be honest, that's just how compiler writers interpret UB these days. It's perfectly possible (in principle) to use lots of more sophisticated static and dynamic analysis to recover much of what C compiler just assume. You don't have to restrict yourself to what C's type system provides. (For an example of what's possible, have a look at all the great techniques employed to make JavaScript as fast as possible. They have basically no static types to work with at all.)
    - masklinn 4y ago
      > For an example of what's possible, have a look at all the great techniques employed to make JavaScript as fast as possible. They have basically no static types to work with at all. I’m sure people will be very happy with a C JIT. That’s definitely what they use C for. JIT-ed code is full of runtime type and range assertions which bail if the compiler’s assumptions are incorrect.
      - eru 4y ago
        Oh, I didn't mean to imply that it would be practical. Only that it's possible and that the type system isn't the only thing you can rely on. Instead of just assuming that 'x > x + 1' is always true (for signed integers), the compiler could also do the heavy lifting of static analysis (for cases where that's possible).
        littlestymaar 4y ago
- andrewaylett 4y ago
  C has always considered that the programmer knows what they are doing. Programs are assumed correct unless proven invalid. This is -- or at least was -- a feature, not a bug. You can implement any valid program, but you can also implement some invalid programs. I know the OP mentioned Rust, but it's a valid comparison: if you don't invoke "unsafe" then all your behaviour is well-defined. But the trade-off is that Rust will only let you implement a subset of valid programs unless you invoke "unsafe", which might be better termed "assumed correct".
spullara 4y ago
Does the compiler know? If so, can't they have a flag that doesn't allow UB?
- pca006132 4y ago
  Doesn't allow optimization enabled by this specific UB: Yes Does't allow UB: Hard, because you probably need runtime checks.
oxff 4y ago
This is a good positive model of UB, fulfilling the compiler assumptions.
afiori 4y ago
I don't think this is a fair comparison as this is all based on implicit inferences by the compiler. If the programmer had specifically invoked the "__assert_valid_pointer(p)" standard function (which does not exists) to promise the compile that the pointer was valid then it would be fine. The problem is that there are a lot of places where the compiler makes these assumptions.
imtringued 4y ago
"and I'm going to kill you for it even though I could also just slap 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.

masklinn 4y ago
Signed int overflow being UB is one of the most basic UBs of the language, and what allows generating tight code in loops. This is not new, -fwrapv was introduced in 2003, but it can quite severely impact code quality, if you don’t care, just set that. Then complain that C is slow, because C is a shit language.
- iforgotpassword 4y ago
  > and what allows generating tight code in loops. How so? How does breaking an if statement the programmer added make the code faster? If they intended the check not to happen/be required, they wouldn't have written it. Let signed int overflow and leave any code that depends on its value alone. So yes maybe make fwrapv the default. > because C is a shit language. Well, it's as low level as it can get before reaching assembly, but why not try reducing the number of foot guns? Sometimes you still need C, and that's not going to go away for the foreseeable future.
  - masklinn 4y ago
    > How does breaking an if statement the programmer added make the code faster? If they intended the check not to happen/be required, they wouldn't have written it. See your problem is that you’re 1. not thinking like a compiler 2. and reasoning on an isolated example The compiler does not “break an if statement”, the compiler uses the UB to limit the range of the input and output, it can then propagate this range analysis to see that the check is dead code, and so removes the dead code. It’s common for users to write unnecessary or redundant checks, even more so because of inlining, and especially macros. If you’re carefully checking for null in every function prologue, and the compiler in-line everything and knows the pointer is non-null, all checks are dead and can be removed. Which is what the compiler does. This reduces the amount of branches (and thus the space needed by the branch predictor), and reduces the amount of code meaning the new inlined function could fall below threshold and itself become a candidate for inlining.

raverbashing 4y ago

Except this can't happen happens many and many times in practice so maybe it's time the language bureaucrats got off their high horse (but they won't)

pjmlp 4y ago

Even if someone would read all those pages, constraining ourselves to ISO C only, no way that after an year they would still remeber the about 200 UB cases that are documented there. Which is why everyone should adopt static analysis tooling and enable all the warnings that are related to UB, pointer and casts misuses. Many think they know better, it is like those that think builders don't need protection gear at a construction site, it is stuff only for the weak.

gpderetta 4y ago
I think implicitly compiler-added runtime check are a more robust and reliable solution than static analysis. For example for pointer dereferences the compiler should could 0-offset dummy load if the load is not guaranteed to be within a page of the pointer. Or adding abort-on-overflow for math. Or bound checking where possible. It will have a non-trivial cost, but hopefully aggressive optimizations can remove many of these checks (which ironically it is exactly the kind of optimizations people are complaining about) and compilers provide pragmas to disable them when critical. In a way sanitizers are getting there, but they are explicitly marked as for non-production use which is a problem.
- pjmlp 4y ago
  I agree, but unfortunely that will never happen in most C and C++ circles, just see the heat JF Bastien has been facing for a feature that has been shipping in Windows and Android for the last two years, proven in the battlefield to hardly hinder performance in real use cases. https://isocpp.org/files/papers/P2723R0.html https://isocpp.org/files/papers/P2723R0.html Lots of people telling him it will never fly in production, while their Windows and Android phones are using the code that they say isn't good enough.
  - gpderetta 4y ago
    Zero initialization is also one of those features that seems such a low hanging fruit to implement... I'm still moderately optimistic. I suspect that many of these checks will end up being enabled by default on compilers shipped by distros, like stack guards and other forms of hardening.

Asooka 4y ago

Basically, the compiler implements integer addition using an operation that doesn't match the semantics of integer addition in the standard, then hallucinates that it did. That is: 1) The compiler sees an expression like "a += b;" where a and b are signed integers. 2) It emits "add rA rB" in x86 assembly (rA/B being the register a/b is currently in). 3) Technically the machine code emitted does not match the semantics of the source code, since it uses wraparound addition, whereas the C standard says that for the operation to be valid, the values of a and b must be such that no overflow would occur. This is fine however, because the implementation has the freedom to do anything on integer overflow, including just punting the problem to hardware as it did in this case. 4) The compiler proceeds with the rest of the code as if the line above would never overflow. My brother in the machine spirit, you chose to translate my program to a form where integer overflow is defined. The compiler should either a) trap on integer overflow; or b) accept integer overflow. It will be fine if it chooses either a) or b) situationally, i.e. if we have a loop where assuming no overflow is faster, then by all means - add a precondition check and crash the program if it's false, but don't just assume overflow doesn't happen when you explicitly emit code with well-defined overflow semantics. The bigger problem is there is pretty much no way to guard against this. The moment your program is longer than one page you're screwed. You may think all your functions are fine, but then you call something from some library, the compiler does some inlining and suddenly there's an integer overflow where you didn't expect, leading to your bounds check being deleted.