Undefined behavior in C is a reading error • Hacker News Board

Re: Undefined behavior in C is a reading error

#341

Post by a1369209993 » Fri, May 21, 2021, 3:27 AM UTC

d110af5ccf wrote: post #336

a1369209993 wrote: post #332

Earlier quoted context omitted.

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…

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

Re: Undefined behavior in C is a reading error

#342

Post by Dylan16807 » Fri, May 21, 2021, 3:58 AM UTC

vyodaiken wrote: post #256

MauranKilom wrote: post #240

Earlier quoted context omitted.

So what optimizations do you mean with "these UB optimizations" then? And would it change your mind to see a benchmark proving the usefulness of that particular UB optimization?

e.g. assuming UB can't happen: deleting overflow or null pointer checks, deleting comparisons between pointers that are assumed to point at different objects, ...

I'm surprised you don't think deleting a bunch of checks will improve performance.

Re: Undefined behavior in C is a reading error

#343

Post by d110af5ccf » Fri, May 21, 2021, 4:06 AM UTC

a1369209993 wrote: post #341

d110af5ccf wrote: post #336

Earlier quoted context omitted.

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…

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

Re: Undefined behavior in C is a reading error

#344

Post by hnjst » Fri, May 21, 2021, 4:06 AM UTC

a1369209993 wrote: post #340

hnjst wrote: post #329

Earlier quoted context omitted.

I don't get what you or the comment you're responding to are wishing for. Do you want compilers to stop adding optimizations while staying within the bounds defined by the spec? That they somehow guess that a given piece of code that may trigger UB is too important for them to optimize it based on the assumption that the developer knew what she was doing and ensured that it wouldn't? The case of a compiler update bre…

> I don't get what you or the comment you're responding to are wishing for. Quoting from another of my comments: > > [What are you objecting to?] > Inferring any propositional statement about the program (eg "this pointer is not null") from the fact that its negation would imply undefined behaviour. That is what the problem is. Undefined behaviour is a licence to implement operations without regard for unusual corner…

> Inferring any propositional statement about the program (eg "this pointer is not null") from the fact that its negation would imply undefined behaviour.

I'm not completely sure I understand that correctly, but do you mean that statements that are constant unless considering a possible (and "credible"?) implementation of UB shouldn't be fair-game for the compiler to optimize out? EDIT: I think I see a more tricky case that may be one of those you're referring to. Dereferencing a pointer further in the code shouldn't be a valid justification for optimizing out previous tests of it being null. I can relate with that but I suspect that it would prevent many classes of branch pruning.

I get what you suggest while describing malicious compliance but I can imagine that it could be a false impression resulting from trade-offs that favor optimization opportunities to "out-of-spec but canonical/natural" implementations.

Re: Undefined behavior in C is a reading error

#345

Post by Jweb_Guru » Fri, May 21, 2021, 4:15 AM UTC

Dylan16807 wrote: post #324

btilly wrote: post #282

Earlier quoted context omitted.

There may be programs that desire such behavior. But I've never intentionally written one. Which is why I personally avoid C, and wish that I didn't have to work in environments coded in C. I seriously would accept everything running at half speed for the certainty of not being subject to the problems of C level bugs. But as Rust grows in popularity, it looks like I won't need to worry about that.

> I seriously would accept everything running at half speed for the certainty of not being subject to the problems of C level bugs. I think most people would. But the described code is still buggy even when it's not optimized.

Well, any code that triggers undefined behavior is already buggy by definition. I think it would be a lot more fruitful if, instead of blaming compilers for doing their job (trying to optimize code in a language that allows all sorts of potentially unsafe behavior), people enumerated the specific UB they had issues with. For example, a lot of people don't consider integer overflow, too-large bitshift, nonterminating loops, type punning without union, or "benign" data races automatic bugs in themselves. Some people don't even consider a null pointer dereference an automatic bug (but what about a null pointer field access, or array index that happens to land on a non-null page? Is the compiler allowed to optimize field accesses to pointer arithmetic, or not?).

Anyway this is all fine, but as you can imagine you lose a lot of optimizations that are facilitated by all that UB, so the compiler authors should then counter with some way to signal that you want the original undefined semantics (for instance, references in C++ and restrict pointers in C), or provide compile-time checking to prevent misuse that messes up optimizations (e.g. Rust's Send+Sync for avoiding data races, or UnsafeCell for signaling lack of restrict semantics / raw pointers for lack of non-nullability).

Re: Undefined behavior in C is a reading error

#346

Post by markslicker » Fri, May 21, 2021, 4:30 AM UTC

The main problem with undefined behavior is that the compiler does not produce any warning to that effect (in my case gcc). I've been caught by bugs that were truly puzzling until I understood undefined behavior, and the licensee it gives to the makers of compilers. I think undefined behavior is giving C a reputation worse than it deserves.

Re: Undefined behavior in C is a reading error

#347

Post by a1369209993 » Fri, May 21, 2021, 4:36 AM UTC

msbarnett wrote: post #123

bhk wrote: post #112

Earlier quoted context omitted.

It isn't clear to me precisely what example you have in mind. If you are saying that deleting array bounds checks might have performance benefits that outweigh the security concerns, then I disagree. If you are saying that the compiler would have to insert bounds checks, I don't see how you arrive at that. I have seen claims that gratuitous UB is important for enabling meaningful optimizations, but in every such case…

> If you are saying that deleting array bounds checks might have performance benefits that outweigh the security concerns, then I disagree. I'm saying that there is existing code in this world in which some variation on /* insanely hot loop where ARRAYSIZE > 32 */ while(true) { ... int x = 1 exists that's currently compiling down to just "a[index] = 1 I'm saying that the authors and their customers are unlikely to be…

(I'll assume int is 32 bits, the hardware generates zero on shl overflow, and we don't care if a[31] is negative, since "everything working fine" wouldn't be true otherwise.)

The compiler is perfectly capable of seeing 1= 32, then x is 0 (on this hardware), so the two branches of the conditional are the same, and we can just use the first one. On the other hand, if index Note that that did not make any reference to undefined behaviour.

Re: Undefined behavior in C is a reading error

#348

Post by a1369209993 » Fri, May 21, 2021, 4:55 AM UTC

jcranmer wrote: post #20

It's easy to pick on undefined behavior in C when you focus on the more gratuitous undefined behaviors such as signed overflow or oversized shifts. I'm not certain why these are undefined behavior instead of implementation-defined, but my suspicion is that these caused traps on some processors, and traps are inherently undefined behavior. Instead, if you dislike undefined behavior, I challenge you to come up with wor…

I'll bite.

  > int x = cond ? 2 : y; /* Is it legal to fold this to int x = 2; ? */

This is permissible (on typical hardware) only if the implementation chooses to 'initialize' y to 2 (possibly skipping the actual write if it is later overwritten), since doing otherwise would result in:

  int x1 = cond1 ? 2 : y; /* So int x1 = 2; */
  int x2 = cond2 ? 3 : y; /* So int x2 = 3; */

No, no it may not do that.

Edit1: actually, as vyodaiken points out, that's only valid in the first place if y is auto, not static.

> Can this be lowered to int y = x;

Sure; the compiler is free to implement dereference in a non-trapping manner if possible.

> No one uses the result of the load, can I delete it?

Yes, it's not volatile.

> Can I hoist the load out of the loop?

I don't think so; foo might write to z.

> Note that all of the optimizations I'm alluding to here are ones that would have existed all the way back in the 1980s when C was being standardized, and these are pretty basic, pedestrian optimizations that you will cover in Compilers 101.

Yep, some of the proposed optimizations (x1x2 and hoist) aren't actually available, but they all seem like reasonable things to consider.

Edit, missed these:

> A function marked _Noreturn returns.

If written in C, the body of the function must include a return statement, and is thus a compile time error. If written in assembly, this is no different than overwriting your return address via buffer overflow and ending up in the middle of a function. The compiler should probably stick a trap instruction after the call instruction, though.

> Or you alias two pointers marked restrict.

`restrict` (formerly noalias) is not valid C[0] (or any language), no matter what the standard says; the compiler must emit a compile time error.

0: https://www.lysator.liu.se/c/dmr-on-noalias.html

Re: Undefined behavior in C is a reading error

#349

Post by lmm » Fri, May 21, 2021, 5:05 AM UTC

UncleMeat wrote: post #303

lmm wrote: post #297

Earlier quoted context omitted.

How so? The implementation can, and perhaps should, define that it errors. Whatever behaviour you're worried about a compiler doing for implementation-defined behaviour, it could do exactly the same thing if the behaviour was undefined.

Implementation defined behavior can only ever produce compiler warnings, which you can choose to be commit blockers if you want. But if a compiler can prove that UB can happen then it can completely prevent you from building that program.

> But if a compiler can prove that UB can happen then it can completely prevent you from building that program.

Not really; the C standard requires implementations to have particular behaviour for executions which do not encounter undefined behaviour, so an implementation still has to do the right thing for valid cases. So if there's even one possible set of user input etc. for which the program has defined behaviour then a compiler has to produce an executable.

Re: Undefined behavior in C is a reading error

#350

Post by Too » Fri, May 21, 2021, 5:13 AM UTC

saagarjha wrote: post #309

alerighi wrote: post #263

Earlier quoted context omitted.

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 b…

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