Hacker News Reader

Comment by layer8 | Hacker News Reader

Because there seems to be some confusion in this thread:

- "Implementation-defined behavior" means that the C standard specifies the allowable behaviors that a C implementation must choose from, and the implementation must document its particular choice.

- "Unspecified behavior" means that the C standard places no particular restrictions on the behavior, but a C implementation must pick a behavior and document its choice.

- "Undefined behavior" means that C implementations are allowed to assume that the respective runtime condition does not ever occur, and for example can generate optimized code based on that assumption. In particular, it is free to not decide any behavior for the condition (let alone document it). As a consequence, if the runtime condition actually does occur, this can affect the behavior of any part of the program, even the behavior of code executed before the condition would occur. This is because from a false assumption the truth of any statement can be logically derived (principle of explosion [0]). And that is why the C standard does not restrict the behavior of the whole program if it contains undefined behavior.

[0] https://en.m.wikipedia.org/wiki/Principle_of_explosion

View on HN

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.

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.

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

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

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

> - "Undefined behavior" means that C implementations are allowed to assume that the respective runtime condition does not ever occur, and for example can generate optimized code based on that assumption.

Please note that the article is making the specific argument that this interpretation of UB is an incorrect interpretation. The author is arguing that you, me, the llvm and gcc teams are wrong to interpret UB that way.

Linux had a bug in it a few years ago; the code would dereference a pointer, then check if it was null, then returned an error state if it was null, or continued performing the important part of the function. The compiler deduced that if the pointer had been null when it was dereferenced, that's UB, so the null check was unnecessary, and optimized the null check out. The trouble was that in that context, a null pointer dereference didn't trap, (because it was kernel code? not sure.) so the bug was not detected. It ended up being an exploitable security vulnerability in the kernel, I think a local privilege escalation.

The article is making the argument that the compiler should not be free to optimize out the null check before subsequent dereferences. The compiler is permitted to summon nasal demons where the pointer is dereferenced the first time, but should not be free to summon nasal demons at later lines of code, after the no-nasal-demons-please check.

(The linux kernel now uses -fno-delete-null-pointer-checks to ensure that doesn't happen again. The idea is that even though it was a bug that UB was invoked, the failure behavior should be safe instead of granting root privileges to an unprivileged user.)

Fun with NULL pointers part 1 https://lwn.net/Articles/342330/

Fun with NULL pointers part 2 https://lwn.net/Articles/342420/

By the way, dereferencing NULL is a well defined behaviour on every computer architecture: you are basically reading at address 0 of memory. It just causes a crash if you have an operating system since it will cause a page fault, but in kernel mode or in devices without an OS is a legit thing to do (and even useful in some cases).

Why should C compilers make it undefined? The standard doesn't mandate that undefined behaviour should change the semantic of the program. Just define all the undefined behaviour that you could, to me keeping them undefined makes no sense (even from the standard point, everyone knows that if you overflow an int it wraps around, why should it be undefined??)

I’m not totally sure, but I think dereferencing a zero pointer is theoretically not undefined behavior in C, just so long as you didn’t obtain the zero pointer by initializing a pointer with a null pointer constant.

NULL is not required to have a bit representation of all zeroes. If you are programming for a low-level hardware device, it might be worth your while to get a C implementation that does not represent the NULL pointer this way.

Pointers are hardly even required to have a bit representation at all! [1]

This is one of the most common impedance mismatches between programmers and the C spec. C does not mention how the machine should handle memory. Variables and pointers are just abstract constructs there. While many programmers think their programs are a giant char* on their DRAM stick that can be fiddled with at any time and in any way they please.

([1] Actually this is not entirely true but it is better to think of them this way for the sake of not making more assumptions on the memory which are UB. Pointers are allowed to be converted to integer types - but with the caveat that alot of behaviour around it is implementation defined and of course surrounded with a big dose of UB as well!)

> The trouble was that in that context, a null pointer dereference didn't trap, (because it was kernel code? not sure.) so the bug was not detected.

Yes, because it was kernel code. Because that dereference is completely legal in kernel code. The C code was fine, assuming that it was compiled with appropriate kernel flags. This was not a bug in Linux, at least not on the level of the C code itself.

> The linux kernel now uses -fno-delete-null-pointer-checks to ensure that doesn't happen again.

I also seem to remember that it was already using other "please compile this as kernel code" flags that should have implied "no-delete-null-pointer-checks" behavior, and that the lack of this implication was considered a bug in GCC and fixed.

I noticed that I mixed up "implementation-defined behavior" and "unspecified behavior" a bit. Here are the actual definitions:

implementation-defined behavior: unspecified behavior where each implementation documents how the choice is made

unspecified behavior: use of an unspecified value, or other behavior where this International Standard provides two or more possibilities and imposes no further requirements on which is chosen in any instance

Yeah, I was about to post about this. Note that implementation-defined behavior and unspecified behavior are not _only_ used in places where a choice is given. Quite a few uses of implementation-defined behavior do not actually select between options. It just says the behavior is implementation-defined. So I suppose it selects between infinite options.

For this kind of behavior there is actually no limit on what the implementation is allowed to do, including assuming it never happens and optimizing accordingly. Implementations just need to document what they do.

I don't think these attempts to change the definition of UB are useful. As a compiler vendor it doesn't help to just say "it has a behavior", because that doesn't stop me from doing exactly what I do today. If people want some specific behavior, or to limit behaviors, then they need to actually say that in the spec.

To take left shift for example. Instead of saying it's implementation-defined behavior, they should say that it produces a implementation-defined non-trap value in the range of the resulting type that is consistent for the same inputs.

This would be pretty short to write in standardees, doesn't allow UB based optimizations, and allows the required implementation divergence.

To my knowledge, in case of unspecified behaviour, it's not required to pick and document a particular choice. Behaviour may even vary on a case by case basis where it makes sense (eg order of evaluation of function arguments, whether an inline or external definition of an inline function gets used, etc).

The need to properly document the choice is the defining characteristic of implementation-defined behaviour.

Reply on news.ycombinator.com