Defining the Undefinedness of C (2015) [pdf] • Hacker News Board

Re: Defining the Undefinedness of C (2015) [pdf]

#51

Post by _kst_ » Wed, Jul 26, 2017, 6:17 PM UTC

kps wrote: post #9

iainmerrick wrote: post #2

Here's something I'd love to know about undefined behavior in C: is this something specific to C, or is it something that any similar language would have to contend with? It seems like problems crop up when you combine a fairly low-level language with an emphasis on performance, a specification that explicitly calls out implementation-defined and undefined semantics, and very highly optimizing compilers. None of the…

I think it was an unintended consequence of the wording chosen by the ANSI C89 committee. The reality of pre-ANSI C was that if you wrote ‘+’, the expectation was that you'd get the target machine's ‘add’ instruction, no more and no less. It might overflow, it might not; it might crash or hang your machine on overflow or trap values — but that is all your problem, not the language's or compiler's. I worked on a comme…

Which "add" instruction? Integer (signed or unsigned), floating-point? How big are the operands? What if the operands are of different types? What if the CPU doesn't have an "add" instruction? Or, perhaps more plausibly, doesn't have a divide instruction?

C code defines run-time behavior (or fails to define it in some cases), not CPU instruction sequences. If you want assembly language, you know where to find it.

Re: Defining the Undefinedness of C (2015) [pdf]

#52

Post by kbenson » Wed, Jul 26, 2017, 6:19 PM UTC

simias wrote: post #24

iainmerrick wrote: post #20

Earlier quoted context omitted.

So that "next = a + 1" is essentially a note to the compiler, promising that "++a" won't overflow? To me that seems really reckless! If you need that note, make it a compiler pragma or something, rather than trying to sneak it in by repurposing some existing code. Now if overflow were implementation-defined, the compiler would have to assume that INT_MAX + 1 wraps to INT_MIN (say). So as written, the "if (a == INT_MA…

I wouldn't write code like this on purpose, rather I'd genuinely need "next" for some other computation and the compiler could then use that to infer that I know "a" not to overflow. If I wanted to make it an "annotation" then I'd use "assert(a This is a very simple example of course, but maybe this "increment" code is actually used in many other parts of the codebase where the test actually makes sense. It's not rar…

This is essentially what caused the Cap'n'Proto remote vulnerability[1] 6 months back. The compiler optimized away an overflow check that directed control to an error handling path, eliding the code that checked for the exact error. Fun.

1: https://news.ycombinator.com/item?id=14163111

Re: Defining the Undefinedness of C (2015) [pdf]

#53

Post by smitherfield » Wed, Jul 26, 2017, 6:29 PM UTC

steveklabnik wrote: post #41

smitherfield wrote: post #17

Earlier quoted context omitted.

Yes, there are a number of optimizations that require UB, or something like it. For example, say you have this valid C or Rust code: if (my_signed_int + 1 > my_signed_int) { foo(); } Since signed integer overflow is UB in C, C compilers can optimize out the conditional, but since Rust specifies that overflow may wrap, the compiler can’t assume the condition is true.

To be clear here, overflow is a "program error" in Rust; it's specified to panic in debug builds, and any build where it doesn't panic is defined as wrapping two's compliment. I tried to toss this into godbolt, but the optimizer is too good of course, it will optimize away the entire if if my_signed_int is a literal. Here's one without optimizations: https://godbolt.org/g/tBZcTA It seems to compare 1 to 1, and then b…

Rust does do the loop condition (well, comparing `my_signed_int` to INT_MAX) even with optimizations: https://godbolt.org/g/dnBEJi

(You need to put a side effect such as I/O in the conditional branch for it not be optimized away, "pub" before the function declaration for it not to be eliminated as dead code, and pass `my_signed_int` as an argument so the condition isn't constant-folded).

Clang OTOH optimizes away the condition with even the lowest optimization level (-Og) turned on, as you'd expect: https://godbolt.org/g/8ftkED

Re: Defining the Undefinedness of C (2015) [pdf]

#54

Post by pcwalton » Wed, Jul 26, 2017, 6:38 PM UTC

duneroadrunner wrote: post #46

iainmerrick wrote: post #16

Earlier quoted context omitted.

by "safer C", i assume you're talking about the likes of rust et al. I'm actually thinking of variants of C that allow existing code to be used with no or minimal modifications. The "Friendly C" proposal that another commenter linked to is a good example: https://blog.regehr.org/archives/1180 It seems like Rust is getting some traction, and that's great, but it's certainly not a drop-in replacement for C.

I can't say for certain why none of the "safer C"s have caught on, but I can say that they all have significant compromises and/or impracticalities. Often, performance cost is one of them. Today though, you can use the safe numerics[1] library along with SaferCPlusPlus[2] (shameless plug) as a high performance solution to address undefined behavior in your C code. This solution preserves most of your C code intact, a…

There have been lots of solutions like "SaferCPlusPlus" over the years. In my view, the real reasons why these have not been adopted widely are (1) aversion to any sort of runtime overhead greater than zero; (2) cognitive overhead of introducing new language machinery, type-level or otherwise; (3) interoperability with existing code; (4) few people want to be the first to adopt these kinds of tools in production due to the perceived risk; (5) denial that memory safety problems are indeed problems.

If you're going for wide usage, I think it's actually easier to start over with a new language rather than to try to graft safety features onto C++. A lot of low-level folks don't realize it, but C and C++ are no longer the behemoths they used to be. If you look at the languages people are switching to rather than just absolute usage share, the usage chart [1] paints a very different picture.

[1]: https://blog.sourced.tech/post/language_migrations/eigenvect...

Re: Defining the Undefinedness of C (2015) [pdf]

#55

Post by pcwalton » Wed, Jul 26, 2017, 6:39 PM UTC

pjmlp wrote: post #38

iainmerrick wrote: post #16

Earlier quoted context omitted.

by "safer C", i assume you're talking about the likes of rust et al. I'm actually thinking of variants of C that allow existing code to be used with no or minimal modifications. The "Friendly C" proposal that another commenter linked to is a good example: https://blog.regehr.org/archives/1180 It seems like Rust is getting some traction, and that's great, but it's certainly not a drop-in replacement for C.

C will always be around, unless we get rid of UNIX and POSIX compatibility layers. Which given Microsoft's sudden love to stay relevant, means that we are at the edge of an UNIX monoculture. So any improvement to make C safer is more than welcome. My preference would be to have something like Frama-C be part of ANSI C.

Virtually nobody who is not already using Frama-C would start using it as a result of it being added to ANSI C.

Ask industry C programmers "why aren't you using theorem provers to prove the correctness of your C code?" The number of them who will give you "because ANSI didn't standardize them" as an answer is zero.

Re: Defining the Undefinedness of C (2015) [pdf]

#56

Post by gumby » Wed, Jul 26, 2017, 6:44 PM UTC

kps wrote: post #9

iainmerrick wrote: post #2

Here's something I'd love to know about undefined behavior in C: is this something specific to C, or is it something that any similar language would have to contend with? It seems like problems crop up when you combine a fairly low-level language with an emphasis on performance, a specification that explicitly calls out implementation-defined and undefined semantics, and very highly optimizing compilers. None of the…

I think it was an unintended consequence of the wording chosen by the ANSI C89 committee. The reality of pre-ANSI C was that if you wrote ‘+’, the expectation was that you'd get the target machine's ‘add’ instruction, no more and no less. It might overflow, it might not; it might crash or hang your machine on overflow or trap values — but that is all your problem, not the language's or compiler's. I worked on a comme…

Also C was designed for PDP-7/PDP-11 style machines with 8-bit bytes, 16-bit words and the like. It was ported to a variety of other architectures which had to make assumptions and adaptations. These live in UB.

One somewhat unfortunate side effect of the pervasiveness of C and Unix-style machines is that it encouraged CPUs to optimize for C rather than the opposite way around. The use of GPUs for non-graphics programming is a welcome improvement.

Re: Defining the Undefinedness of C (2015) [pdf]

#57

Post by rofex » Wed, Jul 26, 2017, 6:48 PM UTC

jabl wrote: post #43

woodrowbarlow wrote: post #10

Earlier quoted context omitted.

> is it something that any similar language would have to contend with? it's something any language could _potentially_ have to deal with. C's penchant for undefined behavior comes from two factors, i think: 1. it's ancient. we've learned a lot of lessons since its inception about how to design a language. it also comes from a time when CPU architectures varied wildly -- even within a given manufacturer's product lin…

> 1. it's ancient. we've learned a lot of lessons since its inception about how to design a language. True, but even so, one of the most damning things about C is that it wasn't even "state of the art" back when it was designed. See https://pastebin.com/UAQaWuWG

Very interesting, thanks for the link!

Re: Defining the Undefinedness of C (2015) [pdf]

#58

Post by dfox » Wed, Jul 26, 2017, 7:00 PM UTC

iainmerrick wrote: post #2

Here's something I'd love to know about undefined behavior in C: is this something specific to C, or is it something that any similar language would have to contend with? It seems like problems crop up when you combine a fairly low-level language with an emphasis on performance, a specification that explicitly calls out implementation-defined and undefined semantics, and very highly optimizing compilers. None of the…

The problem with C's undefined behavior is not the undefined behavior itself, but that todays optimizing compilers use UB as a hint to detect "impossible" code paths which then causes the behavior to really become undefined and unpredictable, also many notionally UB constructions are used in lot of existing code, because before such aggressively optimizing compilers the results were somewhat predictable.

Many other languages have concept of UB, sometimes hidden by different wording, even languages that usually target virtual machines (ANSI CL uses the phrase "is an error" for essentially same concept). On the other hand for various VMs the undefined behavior is usually understood as "anything that does not compromise the VM integrity" and similar thing should be true for UB on CPUs (although you should read Intel's errata that contain "causes undefined behavior" as "allows privilege escalation")

Re: Defining the Undefinedness of C (2015) [pdf]

#59

Post by Sprocklem » Wed, Jul 26, 2017, 7:14 PM UTC

_kst_ wrote: post #51

kps wrote: post #9

Earlier quoted context omitted.

I think it was an unintended consequence of the wording chosen by the ANSI C89 committee. The reality of pre-ANSI C was that if you wrote ‘+’, the expectation was that you'd get the target machine's ‘add’ instruction, no more and no less. It might overflow, it might not; it might crash or hang your machine on overflow or trap values — but that is all your problem, not the language's or compiler's. I worked on a comme…

Which "add" instruction? Integer (signed or unsigned), floating-point? How big are the operands? What if the operands are of different types? What if the CPU doesn't have an "add" instruction? Or, perhaps more plausibly, doesn't have a divide instruction? C code defines run-time behavior (or fails to define it in some cases), not CPU instruction sequences. If you want assembly language, you know where to find it.

> Which "add" instruction?

I believe the intention was whichever one matched the types. If you're adding 2 16-bit ints, it would use the 16-bit add instruction, if it existed or a larger one (then, in this case, cast it back down to 16-bits when appropriate). If it's a floating-point type, it would get a floating point add.

[Edit: The compilers usually wouldn't provide a 16-bit int type if they didn't have the instructions to deal with it.]

> What if the operands are of different types?

C89 has well defined promotion rules. You'd convert the operands appropriately, then use the equivalent add.

> What if the CPU doesn't have an "add" instruction?

Then it would probably end up as a function call to a system specific function. Either way, it wouldn't do anything particularly unexpected for the system.

> If you want assembly language, you know where to find it.

C was originally just used as a high-level assembly language. I suspect people found it easier to reason about, even if it basically used the system instruction's behaviour.

Re: Defining the Undefinedness of C (2015) [pdf]

#60

Post by gh02t » Wed, Jul 26, 2017, 7:17 PM UTC

littlestymaar wrote: post #25

iainmerrick wrote: post #7

Earlier quoted context omitted.

Yeah, it's not at all clear to me why so many things need to be undefined rather than implementation-defined.

Undefined means : the compiler can omit this case and assume it never happens. Take integer overflow for instance: an implementation-defined behavior means in case of overflow the compiler can either wrap, crash, or have a saturation at max value. Undefined behavior means the compiler can assume it doesn't happen and optimize with this information in mind. For instance, the following code : for(i = 0; i With the unde…

> Undefined means : the compiler can omit this case and assume it never happens.

That's not the whole picture though. The standard actually says that anything can happen in undefined cases.

> However, if any such execution contains an undefined operation, this International Standard places no requirement on the implementation executing that program with that input (not even with regard to operations preceding the first undefined operation).

The standard doesn't specify what the resulting program should do at all. It's equally valid to e.g. emit code that fails gracefully instead totally ignoring the undefined branch.