Hacker News Reader

Comment by tsimionescu | Hacker News Reader

I would note that the article is explicitly contesting the definition of UB that you are giving here (though you are absolutely right that this is the de facto definition used by all major compilers, and the commtitee).

Basically the article is arguing that UB should be similar to Unspecified behavior - behavior that the implementation leaves up to the hardware and/or OS.

I'm not sure where I fall to this issue, though I would note that the definition of UB in the standard needs quite a bit of interpretation to arrive at the commonly used definition you are quoting. That is, while I think the definition you give is compatible with the one in the standard, I don't think it is the definition of the standard, which is much softer about how UB should impact the semantics of a C program. In particular, nothing in the wording of the standard expliclty says that an implementation is expected to assume UB doesn't happen, or that a standard-conforming program can't have UB.

View on HN

For me, the canonical UB example is a buffer overflow. No matter how you define UB, in practice a buffer overflow can result in for example, a system crash or - given appropriate very specific input data - encrypting all the files on your hard drive for a ransom.

Requiring compilers to restrict UB to something similar to unspecified behavior (where the behavior is not specified by the standard, but a C implementation must pick a behavior and document its choice) would require C compilers to prevent arbitrary code execution given a buffer overflow in C code, i.e. ensure that a buffer overflow in C code does not ever result in actual buffer overflow on the physical machine. This seems implausible to achieve - given the tradeoffs chosen for C, once UB hits, it really is undefined as it can (not in all, but in some) scenarios result in executing absolutely arbitrary machine code depending on the data provided to the program.

On the other hand, if you'd just want to say that the compiler can't assume that UB won't happen for optimizations, then many optimizations are impossible because theoretical UB is literally everywhere where basic arithmetic happens because of the possibility of an integer overflow - if UB would be required to do "whatever the hardware does" then it means that you can't even reorder basic chains of arithmetic instructions and have to execute every operation in order as-written to have the appropriate behavior in case of overflow.

The trouble here is porting the maximalist disaster of one scenario to another scenario simply because the same phrase is used to describe them.

Because a buffer overflow may lead to arbitrary control flow escape via ROP or other hijacking of the instruction pointer, it does not follow that e.g. signed overflow is similarly dangerous.

Signed overflow, if not guarded against, may enable buffer overflow, but the deeper irony is that detecting when signed overflow has already occurred is close to impossible if the compiler is also aware that the check implies that it has occurred.

Thus, code designed for safety, guarding against buffer overflows by detecting signed overflow, ends up not protecting against buffer overflow, simply because signed overflow is described using the same name as buffer overflow.

Yes, now if the proposal would be not to redefine the semantics of UB (as the post to which I replied suggested) but rather about specifying that buffer overflows are UB1 and integer overflows are UB2, and UB2 means something different from UB1 (perhaps identical to implementation-specified behavior, perhaps something different), then that could be reasonable.

It goes further than that. The debates around UB a more about whether the compiler can assume that there are no buffer overflows and perform optimizations based on that. For example, if you have a local variable `char buffer[16]`, and there is an access `buffer[i]`, should the compiler be allowed to derive that 0 <= i < 16, and perform optimizations on other uses of `i` based on that "knowledge"? If all bets are off for `buffer[i]` when i < 0 or i >= 16, why shouldn't it? But some argue that the compiler shouldn't, exactly because such automated formal reasoning can lead to arbitrarily wide reaching effects. The problem is that it's hard to see where a middle ground could be.

The result is a perpetually unstable situation fostering inevitable errors when the programmer is surprised by the compiler. There's no remedy except to move away from C to more tightly specified languages.

The problem is ecosystems like UNIX based platforms, that will never move to something else.

The only solution is to throw them away, e.g. Android style.

Android threw away a unix based platform? News to me.

It did, ask termux guys.

The Linux kernel is an implementation detail.

There is nothing UNIX related exposed to userspace.

Java and Kotlin applications, while NDK APIs are clearly defined,

https://developer.android.com/ndk/guides/stable_apis

Or Treble Project for that matter,

https://source.android.com/devices/architecture/hidl

Try to use private APIs (which is what the Linux underpinnings are) and the application might be blessed with being killed by the OS.

If the array index is unconditional, then sure that seems like a reasonable undefined behavior? If the access is conditional and the compiler can't infer whether the branch is taken, though, then it shouldn't make that assumption.

This reminds me of a bug in the msp430 variant of gcc. The compiler would replace "x <= literal" with "x < literal + 1" because it generated more efficient code. If the literal was UINT_MAX, though, the compiler would trudge ahead and roll over the literal to 0. It would then subsequently reason that the comparison was unconditionally false, and then completely optimize away the nominal path of my code. That was a frustrating day of debugging!

What I never see mentioned in this type of discussion is what this compiler trick buys us. Like how much faster does my program run because of deductions like these? And are there any patterns that particularly benefit from it? Could they hint the constraint manually?

There are plenty of examples in this thread alone.

In my opinion hinting won't help. Everyone who cares about the performance gain will enable the hint (which I expect will be almost everyone) so you have won nothing but added noise with the hint.

There is not a single compelling example. Just contrived examples with dubious speedups and obvious errors.

> given appropriate very specific input data

That's the operative words there. Compilers are not required to ensure that, in sufficiently perverse circumstances, undefined behaviour never results in demons flying out of you nose. They are, however, required to not actively put said demons there themselves, because that's part of what distinguishes a programming language implementation from a piece of malware masquerading as a programming language implementation.

Compilers never actively try to put demons in your program. However, they do occasionally end up making constructs that result from a reasonable (if not the most well-thought-out) chain of decisions that end up looking like demons to the untrained eye.

I didn't say "try"; if it quacks like demon, it's a demon, and the implementation is (whether the standards commitee likes it or not) required not to actively put it into programs that didn't already have it[0], deliberately or otherwise.

0: like this one:

  int* zero = 0;
  int bad = *zero; // maybe crash lol
  if(!zero) abort(); // definitely crash lol
  printf("Uln nasaloth geb hai!\n");

It just isn't that simple in practice. Modern compilers automatically apply a plethora of different rules in sequence when transforming code. This results in a long chain of transformations where each operation is perfectly reasonable when considered on its own. Unfortunately, for certain inputs, the sum total occasionally appears demonic.

The current state of the art is such that there is no way to reliably prevent this that doesn't also severely reduce the optimization abilities of modern compilers. Realistically, adding such language to the standard would (at best) result in worse optimizations by default and additional compiler flags to reenable the more aggressive "nonstandard" ones. (Such flags already exist for various arithmetic operations.)

> where each operation is perfectly reasonable when considered on its own.

No, it is not. For example, the transformation:

  int read_and_discard = *p;
  // vvvv
  int read_and_discard = *p;
  __unsafe_assume_always(p != 0);

is not reasonable, since p is not, in fact, always nonnull.

Your examples are far too simplistic. Real world code is going to be far more complex and will tend to resist trivial analysis.

For example, please explain how to prevent this without also (inadvertently) preventing the removal of unnecessary null checks when functions are inlined. What about an unnecessary null check that's hidden inside a macro? What about whole program LTO?

A macro could be used in a variety of situations. In some of them, you need the null check for safety. In others, the null check in entirely redundant. Short of AGI, the compiler can't actually comprehend the code it operates on. Yet surely you expect it to eliminate "obviously" redundant work? It accomplishes this by applying a large set of fairly simple rules.

(There are probably much better examples but I can't think of them off the top of my head.)

In practice, when I play with Godbolt I find that the "obvious" cases tend to result in helpful diagnostic messages.

> For example, please explain how to prevent this without also (inadvertently) preventing the removal of unnecessary null checks when functions are inlined. What about an unnecessary null check that's hidden inside a macro?

If a null check is unnecessary, that's because it is reachable only from the not-null side of some previous null check. The compiler can track that information just fine, using the same tools it uses to track false information derived pointer dereferences.

If:

  if(!p) abort();
  // we know p is non-null here, regardless of the dereference
  use(*p);
  MACRO(p);

expands to:

  if(!p) abort(); // first null check (this is relevant to optimizing out unnecessary null checks)
  use(*p); // pointer dereference (this isn't)
  if(!p) abort(); // second null check (unnecessary *because of the if*)
  utilize(*p); // more pointer dereference

the compiler can optimize out the second if (the "unnecessary null check" you refer to) based on the first if, regardless of whether the pointer dereference is even there.

This is still too simplistic. Think along the lines of:

    void foo(T *p) {
      if (!p) abort();
      bar(p);
    }

    void bar(T *p) {
      use(*p);
      MACRO(p);
    }

In other words, the first null-check and the latter check are in different functions that may not even be in the same compilation unit, or where the call sequence is hard to reason about due to function pointers etc.

Assuming bar isn't inlined (eg separate compilation unit, as you mentioned), the null check in MACRO is not unnecessary, because bar can be called from places other than foo, and those places might pass null pointer.

This is one of several situations where it might be useful for the compiler to excercise it's perogative to implement operations without regard for undefined behaviour to rewrite `use(*p);` as `if(!p) abort(); use(*p);`, which would make the null check in MACRO unnecessary, but unless it does so, the check is not unnecessary, just insufficient.

I disagree. The transformation should be valid; if p is null then the result is undefined and may crash, including the rest of the program after that occurs. However, I do think that it should not make such a transformation for a volatile read/write; in that case it should not make such an assumption (who knows if it is meaningful on the target computer or some sort of emulator or operating system or debugger or whatever).

> In particular, nothing in the wording of the standard expliclty says that an implementation is expected to assume UB doesn't happen, or that a standard-conforming program can't have UB.

An implementation isn't expected to assume that UB doesn't occur, but it is allowed to assume that.

With regard to programs, the C standard has two different notions of conformance (cf. chapter 4 Conformance). There are strictly conforming programs, which may not rely on anything that would depend on the specifics of a particular C implementation, which of course includes UB. Strictly conforming programs are thus guaranteed to have the same behavior on all conforming C implementations. Then there is the larger class of conforming programs, which is defined as programs acceptable to a (particular) conforming C implementation.

Strictly conforming C programs are severly limited in what they can do. It has been argued that there are hardly any useful strictly conforming C progams.

Non-strictly conforming programs are conforming with respect to a specific C implementation. It is then the job of the C implementation to define what programs it accepts beyond strictly conforming ones, and how it handles (or doesn't handle) undefined behavior. Everything is possible here, from the infamous DeathStation 9000 (with the most insidious UB behavior) to a fully deterministic C implementation that processes any program in the most unsurprising developer-friendly fashion.

There is arguabley a misconception that C is a single language. It is effectively rather a family of languages, for which the C standard only defines a common denominator.

I despair at writing C code where the compiler won't silently surprise me. How are we supposed to learn all these subtle rules and intuit when to apply them without making any mistakes?

By learning only the most important rules, and then enable the compilers undefined behaviour sanitizer(1) during development, making mistakes, and fixing them.

(1)https://clang.llvm.org/docs/UndefinedBehaviorSanitizer.html#...

> and the commtitee

I'd argue that for a document like the C standard, if there's a well-known intended meaning, that is the meaning of the document - any other interpretation is purely academic.

These are all interpretations. Your trying to special privilege one interpretation by calling it the intended meaning when really it’s what I’d call an authoritative interpretation. The accepted interpretation by an authority. That doesn’t necessarily make it the actual intended meaning though.

I was under the impression the "committee" here was the people who wrote the C standard? So the accepted interpretation by the people who wrote the document must be the intended meaning, no? If it wasn't, they'd have written something else.

(Sure, it's possible they wrote something, then only later came to understand the implications of this. But the standard has been understood as allowing nasal demons since long before the latest revision of the C standard, so I'd argue that by publishing a new version without rewording that section, they're making clear that they intend its current interpretation to be part of the standard.)

It sounds like you're arguing that the authors' interpretation isn't an authoritative interpretation.

Is this what you meant?

To some extent, though the committee has not moved to make this definition explicit in the standard (UB = behavior the compiler is free to assume can't happen), for one reason or another.

For the same reason that it came into the standard in first place.

No compiler vendor wanted to give up their own C variant "features".

from ISO/IEC 9899:2011 "Programming Languages -- C"

    3.4.3

    1 undefined behavior behavior, upon use of a nonportable or erroneous program   construct or of erroneous data, for which this International Standard imposes no requirements

    2 NOTE Possible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message).

It doesn't look like a leap to go from this definition to that of ignoring the situation completely with unpredictable results.

This quote is the topic of the original article and the article goes into detail about how it believes the quote should be interpreted.

...and yet the article completely ignores the "with unpredictable results" part and instead spends a lot of time discussing all the other valid consequences (which are also only mentioned as examples, at least in the common understanding of "from ... to ...").

Downthread commenters go into more detail regarding the "ignoring e.g. the possibility of signed overflow may mean to assume that it never happens" reading, so I won't elaborate on it here.

Leaving overflow to the processor is an example of ignoring it with unpredictable results. Deleting overflow checks because you assume, incorrectly, that overflow is impossible is not an example of ignoring with unpredictable effects, it does produce unpredictable effects, though.

How is the compiler supposed to know that a particular operation is intended as an overflow check though? It isn't a human and it doesn't actually comprehend the code it operates on. It just blindly applies rules.

I want the compiler to eliminate redundant operations. That's a large part of the point of doing optimizations in my view! Best effort attempts to avoid eliminating obvious sanity checks are desired of course, but I doubt it's feasible to reliably identify those short of AGI. (And at that point, why are you still writing code?)

You are advocating incorrect code that uses a few less machine operations than correct code.

The compiler should have valid rules, not invalid ones.

The original article's interpretation seemed untenable.

While the difference between "Permissible" and "Possible" could be quite significant, in this case, it was qualifying:

> [Permissible/Possible] undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message).

The previously-"Permissible" behaviors were so broad that they basically allowed anything, including translating the source-code in any documented manner.. which basically means that, as long as a compiler says how it'll treat undefined-behavior, it can do it that way, because it's free to completely reinterpret the source-code in any (documented) manner.

To me ignore the situation completely with unpredictable results would mean: the compiler generates an assembly that could not be correct, and then the behaviour of the program is determined by what the processor does.

Doing something like removing checks is not ignoring the situation: is acting in some particular way when undefined behaviour is detected.

And it has neither unpredictable results: it specifies what happens, since these checks are added systematically.

I don't see anywhere in the standard that the compilers are free to change at their choice the semantic of the program if undefined behaviour is detected. Rather undefined means to me that the compiler generates code where the result cannot be known because it will depend on external factors (basically the hardware implementation).

This is untenable, because different compilers will generate different sequences of instructions which will misbehave in different ways. For example, one compiler may choose to reorder the actual memory access until much later, to a branch of the code that doesn't execute in some cases, so "the hardware implementation" could vary from "nothing happens" to "consistent SIGSEGV".

Compilers don't "detect undefined behaviour": they assume no undefined behaviour is present. It is not possible to change the semantics of the program that contains undefined behaviour because undefined behaviour means there are no valid semantics to begin with.

This is exactly the same situation as dividing by zero in mathematics. If your proof relies on division by zero, you can always prove anything true (the classic 1 == 0 proof for example).

It's not a huge leap, but it still doesn't mean that UB by definition means that the compiler is allowed to assume UB doesn't happen. Allowing the compiler to assume this is one reasonable result of this definition (I give an example of how this reasoning works somewhere else), but it is not equivalent to the definition of UB, in principle.

The definition logically implies that compilers are allowed to assume UB doesn't happen. The definition is:

> undefined behavior: behavior, upon use of a nonportable or erroneous program construct or of erroneous data, for which this International Standard imposes no requirements.

With these optimisations, either:

1. The program contains no UB, the transformed code acts as expected, and the compilation is valid.

2. There's UB; the standard imposes no requirements on what behaviour that translates to; and so the transformed code is valid, regardless of what it does.

It implies it, but they are not equivalent. Basically the common interpretation of UB is sufficient, but not necessary, given the standard.

Reply on news.ycombinator.com