Live data from Hacker News

Undefined behavior in C is a reading error (2021)

yodaiken.com

41–50 of 69 posts

Re: Undefined behavior in C is a reading error (2021)

#41

Earlier quoted context omitted.

What behavior should the following have: int f(int x) { switch (x) { case 0: return 31; case 1: return 28; case 2: return 30; } } This code on its own has no undefined behavior. In another translation unit, someone calls `f(3)`. What would you have compilers do in that case? That path through the program has undefined behavior. However, the two translation units are separate and as such normal tooling will not be abl…

I would do what the standard tells me to do, which is to ignore the undefined behavior if I don't detect it. On most platforms, that would probably result in the return value of 3 (it would still be in AX, EAX, r0, x0, o0/i0, whatever, when execution hits the ret instruction or whatever that ISA/ABI uses to mark the end of the function). But it would be undefined. But that's fine. [EDIT: I misremembered the x86 calli…

So let's change it up a bit.

  typedef int (*pfn)(void);
  int g(void);
  int h(void);

  pfn f(double x) {
    switch ((long long)x) {
    case 0:
      return g;
    case 17:
      return h;
    }
  }

If I understand your perspective correctly, `f` should return whatever happens to be in rax if the caller does not pass in a number which truncates to 0 or 17?

Re: Undefined behavior in C is a reading error (2021)

#42
So a while back, I did some spelunking into the history of C99 to actually try to put the one-word-change-theory to bed, but I've never gotten around to writing anything that's public on the internet yet. I guess it's time for me to rectify it.

Tracking down the history of the changes at that time is a bit difficult, because there's clearly multiple drafts that didn't make it into the WG14 document log (this is the days when the document log was literal physical copies being mailed to people), and the drafts in question are also of a status that makes them not publicly available. Nevertheless, by reading N827 (the editors report for one of the drafts), we do find this quote about the changes made:

> Definitions are only allowed to contain actual definitions in the normative text; anything else must be a note or an example. Things that were obviously requirements have been moved elsewhere (generally to Conformance, see above), the examples that used to be at the end of the clause have been distributed to the appropriate definitions, anything else has been made into a note. (Some of the notes appear to be requirements, but I haven't figured out a good place to put them yet.)

In other words, the change seems to be have made purely editorially. The original wording was not intended to be read as imposing requirements, and the change therefore made it a note instead of moving it to conformance. This is probably why "permissible" became "possible": the former is awkward word choice for non-normative text.

Second, the committee had, before this change, discussed the distinctions between implementation-defined, unspecified, and undefined behavior in a way that makes it clear that the anything-goes interpretation is intentional. Specifically, in N732, one committee introduces unspecified behavior as consisting of four properties: 1) multiple possible behaviors; 2) the choice need not be consistent; 3) the choice need not be documented; and 4) the choice needs to not have long-range impacts. Drop the third option, and you get implementation-defined behavior; drop the fourth option, and you get undefined behavior[1]. This results in a change to the definition of unspecified and implementation-defined behavior, while undefined behavior retains the same. Notice how, given a chance to very explicitly repudiate the notion that undefined behavior has spooky-action-at-a-distance, the committee declined to, and it declined to before the supposed critical change in the standard.

Finally, the C committee even by C99 was explicitly endorsing optimizations permitted only by undefined behavior. In N802, a C rationale draft for C99 (that again predates the supposed critical change, which was part of the new draft in N828), there is this quote:

> The bitwise logical operators can be arbitrarily regrouped [converting `(a op b) op c` to `a op (b op c)`], since any regrouping gives the same result as if the expression had not been regrouped. This is also true of integer addition and multiplication in implementations with twos-complement arithmetic and silent wraparound on overflow. Indeed, in any implementation, regroupings which do not introduce overflows behave as if no regrouping had occurred. (Results may also differ in such an implementation if the expression as written results in overflows: in such a case the behavior is undefined, so any regrouping couldn’t be any worse.)

This is the C committee, in 1998, endorsing an optimization relying on the undefined nature of signed integer overflow. If the C committee is doing that way back then, then there is really no grounds one can stand on to claim that it was somehow an unintended interpretation of the standard.

[1] What happens if you want to drop both the third and fourth option is the point of the paper, with the consensus seeming to be "you don't want to do both at the same time."

Re: Undefined behavior in C is a reading error (2021)

#43

Earlier quoted context omitted.

I would do what the standard tells me to do, which is to ignore the undefined behavior if I don't detect it. On most platforms, that would probably result in the return value of 3 (it would still be in AX, EAX, r0, x0, o0/i0, whatever, when execution hits the ret instruction or whatever that ISA/ABI uses to mark the end of the function). But it would be undefined. But that's fine. [EDIT: I misremembered the x86 calli…

So let's change it up a bit. typedef int (*pfn)(void); int g(void); int h(void); pfn f(double x) { switch ((long long)x) { case 0: return g; case 17: return h; } } If I understand your perspective correctly, `f` should return whatever happens to be in rax if the caller does not pass in a number which truncates to 0 or 17?

More or less, yes.

I quibble with "should return" because I don't think it's accurate to say it "should" do anything in any specific set of circumstances. In fact, I'm saying the opposite: it should generate the generic, semantic code translation of what is actually written in source, and if it happens to "return whatever happens to be in rax" (as is likely on x64), then so be it.

In my view, that's what "ignoring the situation completely with unpredictable results" means.

Re: Undefined behavior in C is a reading error (2021)

#44

Earlier quoted context omitted.

What behavior should the following have: int f(int x) { switch (x) { case 0: return 31; case 1: return 28; case 2: return 30; } } This code on its own has no undefined behavior. In another translation unit, someone calls `f(3)`. What would you have compilers do in that case? That path through the program has undefined behavior. However, the two translation units are separate and as such normal tooling will not be abl…

I would do what the standard tells me to do, which is to ignore the undefined behavior if I don't detect it. On most platforms, that would probably result in the return value of 3 (it would still be in AX, EAX, r0, x0, o0/i0, whatever, when execution hits the ret instruction or whatever that ISA/ABI uses to mark the end of the function). But it would be undefined. But that's fine. [EDIT: I misremembered the x86 calli…

Why isn't that fine? The compiler ignored the undefined behavior it didn't detect.

Re: Undefined behavior in C is a reading error (2021)

#45
post #28

Earlier quoted context omitted.

No, C is totally sane for the machine it describes. If you want to describe a different machine, one in which objects can alias, where signed overflow has a specific meaning, etc, you can choose to describe that machine instead using compiler flags. In that case it is on you to understand what new, unstandardized machine you are describing. This is fine and good, nothing wrong with it, and often very useful. The prob…

> No, C is totally sane for the machine it describes. Are brainfuck[1] or malbolge[2] sane? They do exactly what they says they will do, so following your logic they are sane, aren't they? > The problem is with ever believing what you are describing with C has some 1-to-1 relationship with what the compiler is producing for a given real world hardware implementation. I'm not sure, that it is possible to be a good C p…

> Are brainfuck[1] or malbolge[2] sane?

In that they are sound and consistent, yes, any esoteric language is sane. Merely esoteric.

> I'm not sure, that it is possible to be a good C programmer and to not have any clue of what the compiler will produce...

The compiler is under no requirement to pack structures in a specific way, or under any requirement to produce accesses in a cache pattern that mirrors your intent in the code. The compiler is required to produce a very specific set of observable behaviors, specifically:

> Volatile accesses to objects are evaluated strictly according to the rules of the abstract machine.

> At program termination, all data written into files shall be identical to the result that execution of the program according to the abstract semantics would have produced.

> The input and output dynamics of interactive devices shall take place as specified in 7.23.3. The intent of these requirements is that unbuffered or line-buffered output appear as soon as possible, to ensure that prompting messages appear prior to a program waiting for input.

And that's it. When thinking about the correctness of one's code, things like layout and cache access patterns are irrelevant because the abstract machine does not provide for such things. Thinking in that frame can only lead to errors.

Now, as a fully separate and apart lens to view one's code, of course performance matters. Of course struct layout (as guaranteed by ABI standards like SysV and Windows) matters, of course you should make the optimizer's job easier by doing sequential rather than scattered accesses. That's true of any programming language.

It's true for COBOL and Go and Ada, and yet when using those languages one does not try to reason about accessing objects via incompatible lvalues like C programmers often try to do. This machine-optimization frame of thinking is not a frame you can use to think about the behavior of the program with, behavior needs to be conceived in the frame of the abstract machine.

Re: Undefined behavior in C is a reading error (2021)

#46

Earlier quoted context omitted.

> the implementor (compiler writer) has two choices: (a) assume that the undefined behavior doesn’t occur, and implement optimizations under that assumption, or (b) nevertheless implement a defined behavior for it, which in many cases amounts to a pessimization. No. The implementor has three choices: (1) Ignore the situation altogether; (2) behave according to documentation (with or without a warning); or (3) issue a…

What behavior should the following have: int f(int x) { switch (x) { case 0: return 31; case 1: return 28; case 2: return 30; } } This code on its own has no undefined behavior. In another translation unit, someone calls `f(3)`. What would you have compilers do in that case? That path through the program has undefined behavior. However, the two translation units are separate and as such normal tooling will not be abl…

What I would have it to do is: Return a number that is in the range of the "int" type, but there is no guarantee what number it will be, and it will not necessarily be consistent when called more than once, when the program is executed more than once (unless the operating system has features to enforce consistent behaviour), when the program is compiled for and running on a different computer, etc. I would also have the undefined value to be frozen, like the "freeze" command in LLVM. Normally, the effect would be according to the target instruction set, because it would be compiled in the best way for that target instruction set. Depending on the compiler options, it might also display a warning that not all cases are handled, although this warning would be disabled by default. (However, some instruction sets might allow it to be handled differently; e.g. if you have an instruction set with tagged pointers that can be stored in ordinary registers and memory, then there is the possibility that trying to use the return value causes an error condition.)

Re: Undefined behavior in C is a reading error (2021)

#47
post #9

The crux of this argument seems to be that the author interprets the "range of permissible behavior" they cite as specifications on undefined behavior as not allowing the sort of optimizations that potentially render anything else in the program moot. A large part of this argument depends arguing that the earlier section defining the term undefined behavior has an "obvious" interpretation that's been ignored in favor…

Expressio unius est exclusio alterius.

This construction is called a "false range" in English.

https://www.chicagomanualofstyle.org/qanda/data/faq/topics/C... https://www.cjr.org/language_corner/out_of_range.php

The wording change from Permissible to Possible and making it non-normative was an attempt to clarify that the list of behaviors that follows is a false range and not an exhaustive list.

It's a submarine change because in the eyes of the committee, this is not a change, merely a clarification of what it already said, to guard against ongoing misinterpretation.

Re: Undefined behavior in C is a reading error (2021)

#48

Earlier quoted context omitted.

I would do what the standard tells me to do, which is to ignore the undefined behavior if I don't detect it. On most platforms, that would probably result in the return value of 3 (it would still be in AX, EAX, r0, x0, o0/i0, whatever, when execution hits the ret instruction or whatever that ISA/ABI uses to mark the end of the function). But it would be undefined. But that's fine. [EDIT: I misremembered the x86 calli…

Why isn't that fine? The compiler ignored the undefined behavior it didn't detect.

No. No honest person can claim that making a decision predicated on the existence of X is the same as "ignoring" X.

Re: Undefined behavior in C is a reading error (2021)

#49
Well, where have we had trouble in C in the past? Usually, with de-referencing null pointers. The classic is

   char* p = 0;
   char c = *p;
   if (p) {
      ...
   }
Some compilers will observe that de-referencing p implies that P is non-null. Therefore, the test for (p) is unnecessary and can optimized out. The if-clause is then executed unconditionally, leading to trouble.

The program is wrong. On some hardware, you can't de-reference address 0 and the program will abort at "*p". But many machines (i.e. x86) let you de-reference 0 without a trap. This one has caught the Linux kernel devs at least once.

From a compiler point of view, inferring that some pointers are valid is useful as an optimization. C lacks a notation for non-null pointers. In theory, C++ references should never be null, but there are some people who think they're cool and force a null into a reference.

Rust, of course, has

    Option
with unambiguous semantics. This is often implemented with a zero pointer indicating None, but the user doesn't see that.

So, what else? Use after free? In C++, the compiler knows that "delete" should make the memory go away. But that doesn't kill the variable in that scope. It's still possible to reference a gone object. This is common in some old C code, where something is accessed after "free". This is Common Security Weakness #414.[1]

Not a problem in Rust, or any GC language.

Over-optimization in benchmarks can be amusing.

   for (i=0; i
will be removed by many compilers today. If the loop body is identical every time, it might only be done once. This is usually not a cause of bad program behavior. The program isn't wrong, just pointless.

What else is a legit problem?

[1] https://cwe.mitre.org/data/definitions/416.html

Re: Undefined behavior in C is a reading error (2021)

#50

I really don't like reading these dimwitted screeds. We did not get here because layering over a standard or a document --- this is not the US supreme court or similar. We got here because - There are legit issues trying to define everything without loosing portability. This affects C and anything like it. - Compiler writes do want to write optimizations regardless of whether this is C or anything else --- witness th…

> I really don't like reading these dimwitted screeds.

this 'dimwitted screed' is by the primary author of rtlinux, which was to my knowledge the first instance of running linux under a hypervisor, and the leader of the small team that ported linux to the powerpc in the 90s. he has also written a highly cited paper on priority inheritance. if you disagree with him, it is probably for some reason other than his dimwittedness

i can't specifically testify to his knowledge of modern proof theory, but his dissertation was on 'a modal arithmetic for reasoning about multilevel systems of finite state machines', and his recent preprints include 'standard automata theory and process algebra' https://arxiv.org/abs/2205.03515 (no citations), 'understanding paxos and other distributed consensus algorithms' https://arxiv.org/abs/2202.06348 (one citation), and 'the meaning of concurrent programs' https://arxiv.org/abs/0810.1316 (draft, no citations), so i wouldn't bet too much against it

i'm interested to hear what you've written on modern logic and proof theory to understand your perspective better

Post reply on HN