1. 33
  1.  

  2. 14

    Linus on undefined behaviour:

    Strict aliasing:

    The fact is, using a union to do type punning is the traditional AND STANDARD way to do type punning in gcc. In fact, it is the documented way to do it for gcc, when you are a f*cking moron and use “-fstrict-aliasing” and need to undo the braindamage that that piece of garbage C standard imposes.

    Don’t tell me “the C standard is unclear”. The C standard is clearly bogus shit (see above on strict aliasing rules), and when it is bogus garbage, it needs to be explicitly ignored, and it needs per-compiler workarounds for braindamage. The exact same situation is true when there is some lack of clarity.

    This is why we use -fwrapv, -fno-strict-aliasing etc. The standard simply is not important, when it is in direct conflict with reality and reliable code generation.

    The fact is that gcc documents type punning through unions as the “right way”. You may disagree with that, but putting some theoretical standards language over the explicit and long-time documentation of the main compiler we use is pure and utter bullshit.

    I’ve said this before, and I’ll say it again: a standards paper is just so much toilet paper when it conflicts with reality. It has absolutely zero relevance. In fact, I’ll take real toilet paper over standards any day, because at least that way I won’t have splinters and ink up my arse.

    Null pointer dereferencing:

    Note that we explicitly use “-fno-delete-null-pointer-checks” because we do not want NULL pointer check removal even in the case of a bug.

    Removing the NULL pointer check turned a benign bug into a trivially exploitable one by just mapping user space data at NULL (which avoided the kernel oops, and then made the kernel use the user value!).

    The kernel generally really doesn’t want optimizations that are perhaps allowed by the standard, but that result in code generation that doesn’t match the source code.

    It’s ok to do optimizations that are based on “hardware does the exact same thing”, but not on “the standard says this is undefined so we can remove it”.

    Signed overflow:

    -fno-strict-overflow: again, this is a stupid optimization that purely depends on the compiler generating faster code by generating incorrect code.

    1. 11

      If even one instance of undefined behavior means you are exempt from the C standard, and every major C codebase has at least one instance of undefined behavior, then every major C codebase is exempt from the C standard.

      Which implies C is a language nobody actually uses anywhere major.

      I’m pretty sure this is two steps away from committing semantic murder, but I’m not sure how.

      1. 10

        We have the absurd situation that C, specifically constructed to write the UNIX kernel, cannot be used to write operating systems.

        That’s the money quote for me.

        1. 2

          Well. Considering kernels like Linux use non standard C (Gnu99 if I’m correct, or C99 with some compiler extensions), I’m not surprised. Some compiler extensions are really handy for kernel/low level development like inline assembly for instance.

          1. 1

            Yeah, I’m curious about that. And the following text:

            Linux and other operating systems are written in an unstable dialect of C that is produced by using a number of special flags that turn off compiler transformations based on undefined behavior

            I wish they’d given (or linked to) more details. What flags? What makes this an “unstable dialect”?

          2. 3

            Meh. The more I look at concrete cases, the more I say, so what do you want the compiler to do?

            You do shit, now you expect the compiler to inspect your brain as to what you meant by that shit?

            Index out of bounds… You get whatever happened to be out there. That can be anything and will change from run to run, compile to compile, optimization to optimization, link to link.

            Trying to get the compiler to guess what you thought was out there is beyond foolish. Just fix your damn code already.

            Trying to hamstring the optimizer because you have some weird, literally undefined expectation about what is out there… Oh stop it.

            If you ranted about lack of warnings when the compiler could have warned… yup, I’m with you.

            If you ranted about the lack of balls on the standards committee to make a choice, any choice on something as trivial and obvious as to whether char is signed or unsigned (and there a couple of places where for fear of offending some vendor they haven’t chosen), yup I’m with you.

            But yup, venture into the realm of undefined… I’m content that you may be subject to nasal daemons and you literally cannot define what else you may expect to happen.

            1. 3

              Index out of bounds… You get whatever happened to be out there.

              That is what any sensible person would think. The real treacherous thing about UB is that it’s not like this!

              When the compiler sees UB, it can assume that that code is unreachable. From that, it can infer that the whole branch that contains UB can be deleted, and as a ripple effect, it also knows something about all calculations leading up to determining if the branch is taken. That is how null pointer checks get deleted.

              And despite what the compiler thinks, the code may actually be (if not valid) perfectly correct!

              • Index out of bounds: A perfectly reasonable thing to do if the programmer actually allocated that space off the end of a struct, for example.
              • Integer overflow: Every hardware engineer knows that this is perfectly well-defined (in reality).
              • Pointer aliasing: Or polymorphism – also perfectly reasonable. Yet another problem that does not exist in reality. Lots of people think this is about alignment, which is all that the hardware cares about.
              1. 0

                But the packing of a struct is not portable, nor is portable from version to version of the compiler. Don’t do that.

                Integer Overflow is classic lack of balls on the part of the standards committee.

                Type punning, just don’t do it, it’s not worth the cycle or two you think you’re saving. Static type checking is there to save you pain, stop hurting yourself.

                1. 0

                  The standard is quite explicit…

                  https://en.cppreference.com/w/c/language/operator_member_access

                  Dereferencing a null pointer, a pointer to an object outside of its lifetime (a dangling pointer), a misaligned pointer, or a pointer with indeterminate value is undefined behavior, except when the dereference operator is nullified by applying the address-of operator to its result, as in &*E (since C99)

                  ie. You can have null pointers, but you can’t deference them, so if you’re dereferencing them a couple of paces down from a check….. it can’t be null. So don’t do that.

                  Yes, I know an embedded system can have stuff mapped to address zero, but you can’t access it using the language C99. If you want to, you need a different language or to whack the C standards committee over the head until they come up with C2x that allows you to. But it will be a different language to C99. Get use to it.

                2. 2

                  What about “I don’t want the compiler to remove my null check”?

                  1. 1

                    In the particular case Torvald’s was ranting about, the correct behaviour from the compiler would be to warn about “unreachable code” or “condition always true/false”. (And if you ignore the warnings… you get all you deserve…)

                    Maybe at the time of that bug those warnings hadn’t been implemented. They are now. Use them.

                    But let’s take this whole Undefined Behaviour conversation away from compilers and operating system kernels and into the realm of day to day programmers….

                    Your job, that you have been contracted to do, is to write a simple “double sqrt_fast( double x)” implementation.

                    Your precondition you can rely on is x >= 0.0

                    Don’t bother to check that, that’s the job of higher level code. No point in doing the check twice.

                    Put in a check for that, in the middle of my hot inner loop when I’m desperate for cycles…. you’ve created a performance bug.

                    There will be another routine called sqrt_slow() available, if the programmer wants.

                    “sqrt_slow()” does all those checks and always has defined behaviour. (Hint, it’s implemented in terms of sqrt_fast())

                    Now some twat writing the higher level code checks for x < 0.0, prints out an error message AND CONTINUES ON.

                    ie. Goes and calls does sqrt_fast( x) with a negative value anyway.

                    So what do you expect to happen?

                    Well, whatever the sqrt implementer decided to do on the day. Some routines will go into an infinite loop, some will just produce random garbage, some will produce a NaN, some will trap.

                    The point is the higher level code is shit.

                    It’s a bug.

                    Don’t do it.

                    It would be nice if tools and the compiler could warn you, but given the halting problem, they cannot stop you.

                    What you’re effectively saying is never have a sqrt_fast() because you write shit.

                    In which case, we better not have you implementing sqrt_slow() then…

                3. 2

                  This was a great read. Thanks for posting.

                  1. 2

                    I feel like this is quoting a specific part of the text, which specifies that the “standard imposes no requirements” on how undefined behaviour is implemented, and then complaining that people interpreted this to mean that the standard imposes no requirements on how undefined behaviour is implemented.

                    Compiler vendors are free to have, for example, signed integer overflow calculations actually wrap around as per 2’s complement arithmetic; some of them do; others have a flag which enables this.

                    But if you store a value through an invalid pointer, potentially overwriting the program code itself (I know - it’s usually protected in modern operation systems, but the standard is meant to be more general than that), what is the “reasonable behaviour” that you could hope for? (The result of doing this also falls under “undefined behaviour”).

                    Complaining about compiler vendor choices makes sense; compiling about the actual text of the standard makes sense; complaining about people interpreting the above text to mean exactly what it states (and even denigrating those people as “self-appointed experts”) is ridiculous.

                    From the article:

                    Parsing it out, the prevailing interpretation reads the passage as follows (and note that we have to delete the comma after “behavior” to make it work):

                    behavior upon use of a nonportable or erroneous program construct, or of erroneous data, or of indeterminately-valued objects: The Standard imposes no requirements on this behavior

                    No, this has deleted the “for which” part. The behaviour on use of a nonportable or erroneous program construct is “undefined behaviour” only if the standard imposes no requirements on it; that is the “prevailing interpretation”. Nobody is assuming that the standard both does and doesn’t proscribe behaviour on use of objects with indeterminate value for example.

                    Under the prevailing interpretation “imposes no requirements” is the only operative phrase: the WG14 Committee ignores “use of a nonportable or …” from the text, and has built out a long, ad-hoc list of uses that produce “undefined behavior”

                    The point is that that list describes program constructs which are nonportable, or erroneous, and for which the standard imposes no requirements. Not just that the standard imposes no requirements that all nonportable/erroneous constructs cause erroneous behaviour. Which is, if I understand correctly, what the author also believes, but they are saying that the prevailing interpretation is the latter, which I just don’t see. Eg of undefined behaviour (from the C99 standard):

                    An object is referred to outside of its lifetime (6.2.4).

                    That this is listed in an appendix titled “Portability issues” should be telling.

                    The more constructive interpretation is that the intention of the first sentence was specify that “undefined behavior” was what happened when the programmer used certain constructs and data, not otherwise defined by the Standard.

                    That is exactly the interpretation that is being taken, with the results that the article is decrying.

                    Returning a pointer to indeterminate value data, surely a “use”, is not undefined behavior because the standard mandates that malloc will do that

                    It is not in fact a “use”. This is “using”, if anything, the pointer value, not the value to which it points; the pointer value is not indeterminate (unspecified or a trap) since its value is specified by the specification for malloc.

                    Further:

                    Consider the shift example from Linux that Regehr mentioned. Under the constructive interpretation, compilers would have to choose some “in range” option in place of an “optimization” that doesn’t optimize anything:

                    That would be imposing requirements, when the text specifically says that no requirements are imposed.

                    ignore the situation, generate a “shl” instruction for x86 or the appropriate instruction for other architectures and let the machine architecture determine the semantics.

                    “Ignoring the situation” means ignoring the situation where the shift count is greater than what is allowed, and therefore assuming that it is within the allowed range.

                    1. 3

                      I feel like this is quoting a specific part of the text, which specifies that the “standard imposes no requirements” on how undefined behaviour is implemented

                      The argument being made here is that the spec as written should have been read more like (yes, this is not the wording it used, it is a rewrite to indicate the meaning):

                      Undefined behavior — Undefined behavior occurs when both of the following are true:

                      1. The program makes use of a nonportable or erroneous program construct, or of erroneous data, or of indeterminately-valued objects
                      2. No other part of this Standard imposes requirements for the handling of the particular construct(s), data, or object(s) at issue.

                      When only condition (1) above is met, but condition (2) is not, the situation is not undefined behavior and conformant implementations MUST NOT invoke their handling for undefined behavior.

                      Conformant implementations MAY handle undefined behavior in any of the following ways, but MUST NOT handle undefined behavior in any other way:

                      • Ignore the situation completely with unpredictable results
                      • Behave during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message)
                      • Terminate a translation or execution (with the issuance of a diagnostic message)

                      This is wordier, but is the “plain English” meaning of the original standard as quoted. The entire argument here is that the rest of your comment, and of compiler implementations, is based on a willful misreading which redefined UB to be only item (1) above and separated out item (2) as the handling of it, despite the text explicitly not supporting and in fact contradicting this reading.

                      The fact that it is contradicted is clear from the fact that the Standard does in fact impose requirements for how to handle undefined behavior, immediately afterward. Thus, the contention that the Standard intended to impose no requirements is unsupported by text.

                      1. 1

                        The entire argument here is that the rest of your comment, and of compiler implementations, is based on a willful misreading which redefined UB to be only item (1) above and separated out item (2) as the handling of it, despite the text explicitly not supporting and in fact contradicting this reading.

                        But the rest of my comment doesn’t separate out item (2). I’m in full agreement that both (1) and (2) must apply for something to have “undefined behaviour”. If some behaviour is required, it is not undefined behaviour. That seems fundamentally obvious, and I don’t think anyone has really misunderstood that, despite OP’s claims.

                        The problem I have is this part (of your re-wording):

                        Conformant implementations MAY handle undefined behavior in any of the following ways, but MUST NOT handle undefined behavior in any other way

                        I think it’s clear that is not the case in the C99 text, and I don’t think it was strictly the case from the C89 text either, even if you do ignore the contradiction with the previous paragraph (“imposes no requirements”). The C89 text:

                        Permissible undefined behavior ranges from …

                        … implies that there is a range of permissible behaviours, and that edges of this range are specified;

                        Furthermore, one of the “permissible” behaviours:

                        … ignoring the situation completely with unpredictable results, …

                        … pretty much accurately describes the current behaviour of compilers in the presence of UB that the author is complaining about.

                        So I feel like there are a bunch of things in the post that are wrong or at least contentious:

                        1. The supposition that compiler vendors who implement UB in a way that author disagrees with have separated out items (1) and (2) from the definition of UB, as you break it down above – which I think is wrong;
                        2. That the C89 text was not trying to say what the C99 text now does say – contentious;
                        3. That “ignoring the situation completely” is a behaviour aligned with what the post author wants, rather than what compilers often now do – contentious.

                        In particular, from the OP:

                        What is conspicuously missing from this list of permissible undefined behaviors is any hint that undefined behavior renders the entire program meaningless

                        … yet “with unpredictable results” captures this quite nicely, I think.

                        1. 1

                          No other part of this Standard imposes requirements

                          I suddenly twigged to the significance of “other part” here. You are saying that no other part of the standard imposes requirements, but that this part does.

                          While that makes the whole argument make a little more sense, I don’t think the text supports this; the actual text does not use the “other part” wording at all (it’s unorthodox to put normative requirements in the “terms” section anyway), and I think my other points still hold: the “permissible undefined behaviour” from C89 specifically includes an option which allows for “unpredictable results”, i.e. the “required behaviour” is not requiring any specific behaviour anyway.

                          1. 2

                            I suddenly twigged to the significance of “other part” here.

                            Yes, that’s the intended reading. The very next bit of text imposes requirements for handling UB, so any attempt to read it as a declaration that the Standard intends to impose no requirements for handling UB is nonsensical and requires disregarding the text itself. The only possible logically-consistent interpretation of the “imposes no requirements” is thus as part of the definition of UB – that UB is behavior which meets both prongs (use of erroneous construct/data/etc. and one for which the Standard doesn’t otherwise impose requirements), not as a declaration of the rules for handling of UB (which is explicitly defined in the following section).

                            Compiler implementers, as the OP explains in detail, have rammed their preferred reading all the way through to later versions of the Standard (which have had to do some grammatical gymnastics documented in the OP). That doesn’t mean it was the right reading. That doesn’t mean it should be the right reading.

                            1. 1

                              The very next bit of text imposes requirements for handling UB

                              I don’t think that it does, though. “Ignoring the situation completely with unpredictable results” is one of the explicitly listed “permissible” behaviours, but is hardly proscriptive. And, the text describes a range of permissible behaviour, implying that the examples given may not be a complete set.

                              any attempt to read it as a declaration that the Standard intends to impose no requirements for handling UB

                              The reading is actually that if the standard imposes behavioural requirements on something, then it is not UB. It is not “if it is UB, the standard imposes no requirements”, it is “it is not UB unless the standard imposes no requirements”. That “2nd prong” isn’t being ignored as part of the definition of UB at all. That “the standard intends to impose no requirements” is a logical consequence of, but is not the actual full interpreted meaning of, that 2nd part.

                              The only possible logically-consistent interpretation of the “imposes no requirements” is thus as part of the definition of UB – that UB is behavior which meets both prongs (use of erroneous construct/data/etc. and one for which the Standard doesn’t otherwise impose requirements)

                              The problem is you’ve inserted the “otherwise”. The text actually says “for which this International Standard imposes no requirements”, and that necessarily includes the subsequent paragraph. I.e. for this interpretation to be logically consistent, you need to modify the text slightly.

                              Another logically-consistent interpretation is that the paragraph which “imposes requirements” is not actually intended to do so, which, given that it allows a range of behaviour (i.e. perhaps not fully specified) and that one of those “behaviours” is effectively anything at all (“unpredicatable results”), doesn’t seem too unlikely.

                              (edit: and again, I note that this text is all in the “terms, definitions and symbols” section, which typically is definitive rather than proscriptive).

                      2. 2

                        How do other languages treat undefined behaviour? Is there any hope in formalizing a dialect of C (and C++) that requires compilers to fail when the program is invalid, instead of taking it as license to optimize the whole program away?

                        My attempt at a summary (I’m no expert):

                        • Ada Spark: If disabling the static verification and runtime checks that normally prevent this, there is a concept of bounded errors, where a value may be allowed to become invalid, yet the program is otherwise intact – defined error behaviour.
                        • Rust: The program won’t compile if it has memory errors. Integer overflow generate panics in debug mode and is defined (as two’s complement) in release mode.
                        • Go: Nil dereference panics; integer overflow does not.
                        • Zig:

                          If undefined behavior is detected at compile-time, Zig emits a compile error and refuses to continue. Most undefined behavior that cannot be detected at compile-time can be detected at runtime. In these cases, Zig has safety checks. Safety checks can be disabled on a per-block basis

                        1. 3

                          Is there any hope in formalizing a dialect of C (and C++) that requires compilers to fail when the program is invalid, instead of taking it as license to optimize the whole program away?

                          No, this is impossible. Even CompCERT, which is formally verified, does not make any guarantees when your input program contains undefined behaviour. The entire point of UB is to encode things that the implementation cannot guarantee that it can catch. There are basically three things you can do for this kind of behaviour:

                          • Restrict your language to disallow things that make analysis hard. For example, Rust does not allow two pointers to the same object except in very restricted situations (one is the canonical owning pointer and the lifetime of the others must have shorter lifetimes than that one), Java doesn’t allow pointer arithmetic at all and so disallows any kind of type or bounds errors that can result from them.
                          • Require run-time checks, for example Java or C# require whole-program garbage collection.
                          • Require complex static analysis.

                          The C spec says, for example, that using a pointer to an object after a pointer to the same object has been passed to free is UB. This means that the compiler may assume that any pointer that you dereference has not been passed to free and so is still valid. If you wanted C implementations to fail in this case then you’d need to either restrict what C is allowed to do with pointers (to the extent that the language is no longer very C-like), require a global garbage collector, or require whole-programme data-flow analysis that gets sufficiently close to symbolic execution that it’s infeasible for any nontrivial C program.

                          Or consider a simpler example, such as division by zero. This is UB in C because some architectures trap on division by 0, others give an invalid result. The compiler can potentially warn if it discovers that the value is guaranteed to be zero, but a compiler typically only learns this after inlining and multiple other optimisations, at which point it typically doesn’t have the information lying around to explain why the value is guaranteed to be zero (requiring compilers to record the sequence of transforms that led to a particular endpoint would increase memory usage by at least a factor of 10 and would probably still be incomprehensible to 99% of users). If you want the compiler to dynamically protect against this, it would need to insert a conditional move to replace the divisor with some other value to give a predictable outcome. Pony does this and defines N / 0 = 1, so just replaces the denominator by the numerator in a conditional move. That’s about the only fast thing you can do, but still adds some overhead unless the compiler can statically prove that the value won’t be 0.

                          Or how about Linus’ favourite one: signed integer overflow. This one exists because some older machines didn’t have deterministic (and definitely not portable) behaviour on overflow but it turns out to be really useful for optimisation. If you are using int as the type of a loop induction variable and a < or > comparison for loop termination then the compiler needs to prove that overflow and underflow won’t happen to be able to usefully reason about this. This, in turn, feeds into autovectorisation (which isn’t enabled for the kernel) and increases the number of loops that can be vectorised.

                          1. 3

                            Rust does have a notion of undefined behavior; std::mem::transmute-ing something is UB out of a few situations, and transmuting an immutable reference to a mutable reference is immediate UB. They even had to deprecate the old “give me some uninitialized memory” API in favor of MaybeInit because let x: bool = std::mem::uninitialized() was UB.

                            All of these require unsafe to do, but they’re still undefined behavior.

                            1. 3

                              Is there any hope in formalizing a dialect of C (and C++) that requires compilers to fail when the program is invalid

                              Not really; consider that C is intended to be applicable to a wide range of architectures and operating systems, and is used when speed/efficiency are important (more so than safety in the presence of errors), and finally that for example a write through an invalid pointer is tricky to detect without a significant performance penalty (but can have an effectively unbounded range of possible behaviours).

                              That said I believe Regehr was working on a “safer C” at some point. I think the effort floundered.

                              Edit: https://blog.regehr.org/archives/1180 and https://blog.regehr.org/archives/1287 are relevant links to Regehr’s work.

                            2. 1

                              All this sloppiness is obviously how they like it, because it’s still this way. It’s also why Java exists as several thick books of detailed specifications, precisely to get away from it.