7 ms·

> how insidious undefined behavior is. Indeed. UB in C doesn't mean "and then the program goes off the rails", it means that the entire program execution was m

by titzer 4y ago

> how insidious undefined behavior is. Indeed. UB in C doesn't mean "and then the program goes off the rails", it means that the entire program execution was meaningless, and no part of the toolchain is obligated to give any guarantees whatsoever if the program is ever executed, from the very first instruction. A UB-having program could time-travel back to the start of the universe, delete it, and replace the entire universe with a version that did not give rise to humans and thus did not give rise to computers or C, and thus never exist. It's so insidiously defined because compilers optimize based on UB; they assume it never happens and will make transformations to the program whose effects could manifest before the UB-having code executes. That effectively makes UB impossible to debug. It's monumentally rude to us poor programmers who have bugs in our programs.

LegionMammal978 4y ago
> Indeed. UB in C doesn't mean "and then the program goes off the rails", it means that the entire program execution was meaningless, and no part of the toolchain is obligated to give any guarantees whatsoever if the program is ever executed, from the very first instruction. I don't think this is exactly accurate: a program can result in UB given some input, but not result in UB given some other input. The time travel couldn't extend before the first input that makes UB inevitable.
- nayuki 4y ago
  False. If a program triggers UB, then all behaviors of the entire program run is invalid. > However, if any such execution contains an undefined operation, this International Standard places no requirement on the implementation executing that program with that input (not even with regard to operations preceding the first undefined operation). -- https://devblogs.microsoft.com/oldnewthing/20140627-00/?p=633 https://devblogs.microsoft.com/oldnewthing/20140627-00/?p=63...
  - LegionMammal978 4y ago
    Executing the program with that input is the key term. The program can't "take back" observable effects that happen before the input is completely read, and it can't know before reading it whether the input will be one that results in an execution with UB. This is a consequence of basic causality. (If physical time travel were possible, then perhaps your point would be valid.)
    - Filligree 4y ago
      The standard does permit time-travel, however. As unlikely as it might seem, I could imagine some rare scenarios in which something seemingly similar happens -- let's say the optimiser reaching into gets() and crashing the program prior to the gets() call that overflows the stack.
      - LegionMammal978 4y ago
        Time travel only applies to an execution that is already known to contain UB. How could it know that the gets() call will necessarily overflow the stack, before it actually starts reading the line (at which point all prior observable behavior must have already occurred)?
        lmm 4y ago
        It doesn't matter how it knows. The standard permits it to do that. The compiler authors will not accept your bug report.
        LegionMammal978 4y ago
        If you truly believe so, then can you give an example of input-conditional UB causing unexpected observable behavior, before the input is actually read? This should be impossible, since otherwise the program would have incorrect behavior if a non-UB-producing input is given.
        saagarjha 4y ago
- kllrnohj 4y ago
  They might be referring to eg. the `_Nonnull` annotation being added to memset. The result is that this: if (ptr == null) { set_some_flag = true; } else { set_some_flag = false; } memset(ptr, 0, size); Will never see `set_some_flag == true`, as the memset call guarantees that ptr is not null, otherwise it's UB, and therefore the earlier `if` statement is always false and the optimizer will remove it. Now the bug here is changing the definition of memset to match its documentation a solid, what, 20? 30? years after it was first defined, especially when that "null isn't allowed" isn't useful behavior. After all, every memset ever implemented already totally handles null w/ size = 0 without any issue. And it was indeed rather quickly reverted as a change. But that really broke people's minds around UB propagation with modern optimizing passes.
andrewmcwatters 4y ago
Personally, I've found that some of the optimizations cause undefined behavior, which is so much worse. You can write perfectly good, strict C that does not cause undefined behavior, then one pass of optimization and another together can CAUSE undefined behavior. When I learned this, if it was and is correct, I felt that one could be betrayed by the compiler.
- LegionMammal978 4y ago
  Optimizations themselves (except for perhaps -ffast-math) can't cause undefined behavior: the undefined behavior was already there. They can just change the program from behaving expectedly to behaving unexpectedly. The problem is that so many snippets, which have historically been obvious or even idiomatic, contain UB that has almost never resulted in unexpected behavior. Modern optimizing compilers have only been catching up to these in recent years.
  - titzer 4y ago
    There have been more than a few compiler bugs that have introduced UB and then that was subsequently optimized, leading to very incorrect program behavior.
    - joosters 4y ago
      A compiler bug is a compiler bug, UB or not. You might as well just say "There have been more than a few compiler bugs, leading to very incorrect program behavior."
      - titzer 4y ago
        The whole thread is about how UB is not like other kinds of bugs. Having a compiler optimization erroneously introduce a UB operation means that downstream the program can be radically altered in ways (as discussed in thread) that don't happen in systems without the notion of a UB. While it's technically true that any compiler bug (in any system) introduces bizarre, incorrect behavior into a program, UB just supercharges the things that can go wrong due to downstream optimizations. And incidentally, makes things much, much harder to diagnose.
nayuki 4y ago
I agree with the factual things that you said (e.g. "entire program execution was meaningless"). Some stuff was hyperbolic ("time-travel back to the start of the universe, delete it"). > [compilers] will make transformations to the program whose effects could manifest before the UB-having code executes [...] It's monumentally rude to us poor programmers who have bugs in our programs. The first statement is factually true, but I can provide a justification for the second statement which is an opinion. Consider this code: void foo(int x, int y) { printf("sum %d", x + y); printf("quotient %d", x / y); } We know that foo(0, 0) will cause undefined behavior because it performs division by zero. Integer division is a slow operation, and under the rules of C, it has no side effects. An optimizing compiler may choose to move the division operation earlier so that the processor can do other useful work while the division is running in the background. For example, the compiler can move the expression x / y above the first printf(), which would totally be legal. But then, the behavior is that the program would appear to crash before the sum and first printf() were executed. UB time travel is real, and that's why it's important to follow the rules, not just make conclusions based on observed behavior. https://blog.regehr.org/archives/232 https://blog.regehr.org/archives/232
- vikingerik 4y ago
  > Integer division is a slow operation, and under the rules of C, it has no side effects. Then C isn't following this rule - crashing is a pretty major side effect.
  - Dylan16807 4y ago
    Side effects are a type of defined behavior. Crashing is not a "side effect" in C terms.
  - t0mas88 4y ago
    Only non-zero integer division is specified as having no side effects. Division by zero is in the C standard as "undefined behavior" meaning the compiler can decide what to do with it, crashing would be nice but it doesn't have to. It could also give you a wrong answer if it wanted to. Edit: And just to illustrate, I tried in clang++ and it gave me "5 / 0 = 0" so some compilers in some cases indeed make use of their freedom to give you a wrong answer.
hzhou321 4y ago
> Indeed. UB in C doesn't mean "and then the program goes off the rails", it means that the entire program execution was meaningless, and no part of the toolchain is obligated to give any guarantees whatsoever if the program is ever executed, from the very first instruction. This is the greatest sin modern compiler folks committed to abuse C. C as the language never says the compiler can change the code arbitrarily due to an UB statement. It is undefined. Most UB code in C, while not fully defined, has an obvious part of semantics that every one understands. For example, an integer overflow, while not defined on what should be the final value, it is understood that it is an operation of updating a value. It is definitely not, e.g., an assertion on the operand because UB can't happen. Think about our natural language, which is full of undefined sentences. For example, "I'll lasso the moon for you". A compiler, which is a listener's brain, may not fully understand the sentence and it is perfectly fine to ignore the sentence. But if we interpret an undefined sentence as a license to misinterpret the entire conversation, then no one would dare to speak. As computing goes beyond arithmetic and the program grows in complexity, I personally believe some amount of fuzziness is the key. This current narrow view from the compiler folks (and somehow gets accepted at large) is really, IMO, a setback in the computing evolution.
- kllrnohj 4y ago
  > It is definitely not, e.g., an assertion on the operand because UB can't happen. C specification says a program is ill-formed if any UB happens. So yes, the spec does say that compilers are allowed to assume UB doesn't happen. After all, a program with UB is ill-formed and therefore shouldn't exist! I think you're conflating "unspecified behavior" and "undefined behavior" - the two have different meanings in the spec.
  - hzhou321 4y ago
    > C specification says a program is ill-formed if any UB happens. So yes, the spec does say that compilers are allowed to assume UB doesn't happen. I disagree on the logic from "ill-formed" to "assume it doesn't happen". > I think you're conflating "unspecified behavior" and "undefined behavior" - the two have different meanings in the spec. I admit I don't differentiate those two words. I think they are just word-play.
mattkrause 4y ago
I'm not sure that's a productive way to think about UB. The "weirdness" happens because the compiler is deducing things from false premises. For example, 1. Null pointers must never be dereferenced. 2. This pointer is dereferenced. 3. Therefore, it is not null. 4. If a pointer is provably non-null, the result of `if(p)` is true. 5. Therefore, the conditional can be removed. There are definitely situations where many interacting rules and assumptions produce deeply weird, emergent behavior, but deep down, there is some kind of logic to it. It's not as if the compiler writers are doing if(find_undefined_behv(AST)) emit_nasal_demons() else do_what_they_mean(AST)
- titzer 4y ago
  This is the problem; every compiler outcome is a series of small logic inferences that are each justifiable by language definition, the program's structure, and the target hardware. The nasal demons are emergent behavior. It'd be one thing if programs hitting UB just vanished in a puff of smoke without a trace, but they don't. They can keep on spazzing out literally forever and do I/O, spewing garbage to the outside world. UB cannot be contained even to the process at that point. I personally find that offensive and rude that tools get away with being so garbage that they can't even promise to help you crash and diagnose your own problems. One mistake and you invite the wrath of God!
  - nayuki 4y ago
    > I personally find that offensive and rude that tools get away with being so garbage that they can't even promise to help you crash and diagnose your own problems. This is literally why newer languages like Java, JavaScript, Python, Go, Rust, etc. exist. With the hindsight of C and C++, they were designed to drastically reduce the types of UB. They guarantee that a compile-time or run-time diagnostic is produced when something bad happens (e.g. NullPointerException). They don't include silly rules like "not ending a file with newline is UB". They overflow numbers in a consistent way (even if it's not a way you like, at least you can reliably reproduce a problem). They guarantee the consistent execution of statements like "i = i++ + i++". And for all the flak that JavaScript gets about its confusing weak type coercions, at least they are coded in the spec and must be implemented in one way. But all of these languages are not C/C++ and not compatible with them.

by titzer 4y ago

LegionMammal978 4y ago

nayuki 4y ago
False. If a program triggers UB, then all behaviors of the entire program run is invalid. > However, if any such execution contains an undefined operation, this International Standard places no requirement on the implementation executing that program with that input (not even with regard to operations preceding the first undefined operation). -- https://devblogs.microsoft.com/oldnewthing/20140627-00/?p=633 https://devblogs.microsoft.com/oldnewthing/20140627-00/?p=63...
- LegionMammal978 4y ago
  Executing the program with that input is the key term. The program can't "take back" observable effects that happen before the input is completely read, and it can't know before reading it whether the input will be one that results in an execution with UB. This is a consequence of basic causality. (If physical time travel were possible, then perhaps your point would be valid.)
  - Filligree 4y ago
    The standard does permit time-travel, however. As unlikely as it might seem, I could imagine some rare scenarios in which something seemingly similar happens -- let's say the optimiser reaching into gets() and crashing the program prior to the gets() call that overflows the stack.
    - LegionMammal978 4y ago
      Time travel only applies to an execution that is already known to contain UB. How could it know that the gets() call will necessarily overflow the stack, before it actually starts reading the line (at which point all prior observable behavior must have already occurred)?
      - lmm 4y ago
        It doesn't matter how it knows. The standard permits it to do that. The compiler authors will not accept your bug report.
        LegionMammal978 4y ago
        If you truly believe so, then can you give an example of input-conditional UB causing unexpected observable behavior, before the input is actually read? This should be impossible, since otherwise the program would have incorrect behavior if a non-UB-producing input is given.
        saagarjha 4y ago
kllrnohj 4y ago
They might be referring to eg. the `_Nonnull` annotation being added to memset. The result is that this: if (ptr == null) { set_some_flag = true; } else { set_some_flag = false; } memset(ptr, 0, size); Will never see `set_some_flag == true`, as the memset call guarantees that ptr is not null, otherwise it's UB, and therefore the earlier `if` statement is always false and the optimizer will remove it. Now the bug here is changing the definition of memset to match its documentation a solid, what, 20? 30? years after it was first defined, especially when that "null isn't allowed" isn't useful behavior. After all, every memset ever implemented already totally handles null w/ size = 0 without any issue. And it was indeed rather quickly reverted as a change. But that really broke people's minds around UB propagation with modern optimizing passes.

andrewmcwatters 4y ago

Personally, I've found that some of the optimizations cause undefined behavior, which is so much worse. You can write perfectly good, strict C that does not cause undefined behavior, then one pass of optimization and another together can CAUSE undefined behavior. When I learned this, if it was and is correct, I felt that one could be betrayed by the compiler.

LegionMammal978 4y ago
Optimizations themselves (except for perhaps -ffast-math) can't cause undefined behavior: the undefined behavior was already there. They can just change the program from behaving expectedly to behaving unexpectedly. The problem is that so many snippets, which have historically been obvious or even idiomatic, contain UB that has almost never resulted in unexpected behavior. Modern optimizing compilers have only been catching up to these in recent years.
- titzer 4y ago
  There have been more than a few compiler bugs that have introduced UB and then that was subsequently optimized, leading to very incorrect program behavior.
  - joosters 4y ago
    A compiler bug is a compiler bug, UB or not. You might as well just say "There have been more than a few compiler bugs, leading to very incorrect program behavior."
    - titzer 4y ago
      The whole thread is about how UB is not like other kinds of bugs. Having a compiler optimization erroneously introduce a UB operation means that downstream the program can be radically altered in ways (as discussed in thread) that don't happen in systems without the notion of a UB. While it's technically true that any compiler bug (in any system) introduces bizarre, incorrect behavior into a program, UB just supercharges the things that can go wrong due to downstream optimizations. And incidentally, makes things much, much harder to diagnose.

nayuki 4y ago

I agree with the factual things that you said (e.g. "entire program execution was meaningless"). Some stuff was hyperbolic ("time-travel back to the start of the universe, delete it"). > [compilers] will make transformations to the program whose effects could manifest before the UB-having code executes [...] It's monumentally rude to us poor programmers who have bugs in our programs. The first statement is factually true, but I can provide a justification for the second statement which is an opinion. Consider this code: void foo(int x, int y) { printf("sum %d", x + y); printf("quotient %d", x / y); } We know that foo(0, 0) will cause undefined behavior because it performs division by zero. Integer division is a slow operation, and under the rules of C, it has no side effects. An optimizing compiler may choose to move the division operation earlier so that the processor can do other useful work while the division is running in the background. For example, the compiler can move the expression x / y above the first printf(), which would totally be legal. But then, the behavior is that the program would appear to crash before the sum and first printf() were executed. UB time travel is real, and that's why it's important to follow the rules, not just make conclusions based on observed behavior. https://blog.regehr.org/archives/232 https://blog.regehr.org/archives/232

vikingerik 4y ago
> Integer division is a slow operation, and under the rules of C, it has no side effects. Then C isn't following this rule - crashing is a pretty major side effect.
- Dylan16807 4y ago
  Side effects are a type of defined behavior. Crashing is not a "side effect" in C terms.
- t0mas88 4y ago
  Only non-zero integer division is specified as having no side effects. Division by zero is in the C standard as "undefined behavior" meaning the compiler can decide what to do with it, crashing would be nice but it doesn't have to. It could also give you a wrong answer if it wanted to. Edit: And just to illustrate, I tried in clang++ and it gave me "5 / 0 = 0" so some compilers in some cases indeed make use of their freedom to give you a wrong answer.

hzhou321 4y ago

> Indeed. UB in C doesn't mean "and then the program goes off the rails", it means that the entire program execution was meaningless, and no part of the toolchain is obligated to give any guarantees whatsoever if the program is ever executed, from the very first instruction. This is the greatest sin modern compiler folks committed to abuse C. C as the language never says the compiler can change the code arbitrarily due to an UB statement. It is undefined. Most UB code in C, while not fully defined, has an obvious part of semantics that every one understands. For example, an integer overflow, while not defined on what should be the final value, it is understood that it is an operation of updating a value. It is definitely not, e.g., an assertion on the operand because UB can't happen. Think about our natural language, which is full of undefined sentences. For example, "I'll lasso the moon for you". A compiler, which is a listener's brain, may not fully understand the sentence and it is perfectly fine to ignore the sentence. But if we interpret an undefined sentence as a license to misinterpret the entire conversation, then no one would dare to speak. As computing goes beyond arithmetic and the program grows in complexity, I personally believe some amount of fuzziness is the key. This current narrow view from the compiler folks (and somehow gets accepted at large) is really, IMO, a setback in the computing evolution.

kllrnohj 4y ago
> It is definitely not, e.g., an assertion on the operand because UB can't happen. C specification says a program is ill-formed if any UB happens. So yes, the spec does say that compilers are allowed to assume UB doesn't happen. After all, a program with UB is ill-formed and therefore shouldn't exist! I think you're conflating "unspecified behavior" and "undefined behavior" - the two have different meanings in the spec.
- hzhou321 4y ago
  > C specification says a program is ill-formed if any UB happens. So yes, the spec does say that compilers are allowed to assume UB doesn't happen. I disagree on the logic from "ill-formed" to "assume it doesn't happen". > I think you're conflating "unspecified behavior" and "undefined behavior" - the two have different meanings in the spec. I admit I don't differentiate those two words. I think they are just word-play.

mattkrause 4y ago

I'm not sure that's a productive way to think about UB. The "weirdness" happens because the compiler is deducing things from false premises. For example, 1. Null pointers must never be dereferenced. 2. This pointer is dereferenced. 3. Therefore, it is not null. 4. If a pointer is provably non-null, the result of `if(p)` is true. 5. Therefore, the conditional can be removed. There are definitely situations where many interacting rules and assumptions produce deeply weird, emergent behavior, but deep down, there is some kind of logic to it. It's not as if the compiler writers are doing if(find_undefined_behv(AST)) emit_nasal_demons() else do_what_they_mean(AST)

titzer 4y ago
This is the problem; every compiler outcome is a series of small logic inferences that are each justifiable by language definition, the program's structure, and the target hardware. The nasal demons are emergent behavior. It'd be one thing if programs hitting UB just vanished in a puff of smoke without a trace, but they don't. They can keep on spazzing out literally forever and do I/O, spewing garbage to the outside world. UB cannot be contained even to the process at that point. I personally find that offensive and rude that tools get away with being so garbage that they can't even promise to help you crash and diagnose your own problems. One mistake and you invite the wrath of God!
- nayuki 4y ago
  > I personally find that offensive and rude that tools get away with being so garbage that they can't even promise to help you crash and diagnose your own problems. This is literally why newer languages like Java, JavaScript, Python, Go, Rust, etc. exist. With the hindsight of C and C++, they were designed to drastically reduce the types of UB. They guarantee that a compile-time or run-time diagnostic is produced when something bad happens (e.g. NullPointerException). They don't include silly rules like "not ending a file with newline is UB". They overflow numbers in a consistent way (even if it's not a way you like, at least you can reliably reproduce a problem). They guarantee the consistent execution of statements like "i = i++ + i++". And for all the flak that JavaScript gets about its confusing weak type coercions, at least they are coded in the spec and must be implemented in one way. But all of these languages are not C/C++ and not compatible with them.