Tag: C

Categories
c programming

Unforgivable C programming 1

Here’s a program that exhibits the  low level nature of  C  by changing the return address of a function. The function “one” always returns the number 1 and the function “two” always returns the number 2. The main code calls “one” and prints out that it returned 1, then calls “two”  and then changes its mind and tells us that “one” returned returned 2. The trick is that that the return address for “two” is modified so it returns as if it had been called from the statement that calls “one”.

This program is a good way to learn some machine architecture and also helps with understanding core operating systems code and computer virus coding, but my main excuse is that it is fun. The expressions marked in red are what make the trick work (although the color doesn’t matter -) ). The first version is for X86-64 and the second version is for Arm64 (and your Apple notebook).

/* Irresponsible C Code  (c) Victor Yodaiken 2022/2026
Tested on  AMD Ryzen 5 and compiled with zero optimization
gcc (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0. 
tcc version 0.9.27 (x86_64 Linux)
Ubuntu clang version 18.1.3 (1ubuntu1) x8664
*/

#ifdef GCC // compile with gcc -DGCC
#define OFFSET 3
#else 
#define OFFSET 2
#endif

#include 
int one(void);
int two(void);
void *y = 0; //eventually holds the return address of "one"
int main() 
{ 
        int i;
        if ((i= one()) == 1) {
            printf("one returns 1\n");
            two();
	    printf("The program never gets here\n");
        } else printf("one returns %d\n",i);
	return 0; 
}
int one(void)
{
	char **x = (char **)(&x + OFFSET);
	y = *x;
	return 1; //always returns 1
}
int two(void)
{
	char **x = (char **)(&x + OFFSET); 
	*x = y;
	return 2;
}

This code works on  current generations of tcc, clang, and gcc (as long as you adjust the stack pointer offset and do not, under any circumstances run the optimizer).  If you compile with GCC you have to define the compile time constant GCC, for example by typing the command “gcc X8664.c -DGCC”.  The expression “&x+ OFFSET”  calculated the address of the stack location that holds the return address. On X86, the call subroutine instruction pushes the address of the next instruction onto the stack and then jumps to the subroutine. This code exploits the C compiler allocating space for the variable “x” on the stack, takes that address and looks further up the stack to find the return address. When I was writing this code, I figured out the pointer arithmetic and where to find the return address on the stack by experiment with code something like:

 printf("x=%p *x=%p x+1=%p *(x+1)=%p\n", x,*x,x+1,*(x+1));

extended to 2 and 3 and 4. Also use “objdump –disassemble a.out” on Linux and MacOS to see the assembly code.  This calculation is very sensitive to what else is in the code – adding another variable declaration above the one for “x” or making “one” or “two” take arguments would change the number. Also turning on the so-called “optimizer” breaks this code because current  both Clang and GCC  can change the semantics of C code in often unpredictable ways when they are supposedly optimizing .  This is permitted by the C Standard  for reasons that strike me as not well thought out, but let’s pass over the problem for now (or see this )

For Arm64, the call subroutine instruction puts the return address into a link register, and not on the stack. So, in simple code, we need to copy and save the link register that “one” gets and then “two” can just load that value into the register. Unfortunately, C has not evolved to allow modification of registers in C code, but C’s inline assembler does the job.

/* Irresponsible C Code  (c) Victor Yodaiken 2022/2026
Tested on Apple M3 Macbook
Apple clang version 17.0.0 (clang-1700.0.13.5) 
gcc-14 (Homebrew GCC 14.2.0_1) 14.2.0
*/

#include <stdio.h>

int one(void);
int two(void);
int main() // On Arm-64 executes both printfs
{
    int i;
    printf("Main\n");

        if ((i= one()) == 1) {
            printf("one returns 1\n");
            two();
            printf("The program never gets here\n");
        } else printf("one returns %d\n",i);

        return 0;
}
void *y = 0; //will hold the return address of "one"

int one(void)
{
asm volatile("mov  %0,lr": "=r" (y)); //save lr (link register) in y
return 1; //always returns 1 
}
int two(void) //always returns 2
{
asm volatile("mov lr,%0 " :: "r" (y)); //load lr from y
return 2;
}

This solution is just as fragile as the X86 solution. Although putting the return value in the link register instead of pushing it onto the stack seems like a cleaner and more modern method, if the called subroutine calls a second subroutine, that link register  has to be saved and restored when the second subroutine returns. Where is it saved? On the stack, like they did in old days. So if you add, say “printf” to “two” before the return, the link register will be saved on the stack and then popped back out before the return – overwriting the value we used from “y” (not that I would have made such an obvious error ).

There is a famous fragment of code in early UNIX kernel versions that uses the same stack  trick used in these examples. It goes something like this:

/* you are not expected to understand this*/
next = find_next_process_to_run();
if(save()){
           current_process = next;
           resume();
           panic("process switch failed catastrophically\n");
           }

“Save” saves the context of the current process in a structure pointed to by “current_process” and returns a non-zero value while “resume” restores state from “current_process”  and then returns 0. The trick is that “save” saves the return address among other things and “resume”  returns to the condition test.   You may be  not expected to understand this,  as Dennis Ritchie wrote, but when you do, you know a lot about how process or thread switching actually works.

Retracted: The next chapter of Unforgivable C  is on the way in about 2 weeks, I hope.

Categories
C standard operating systems

PLOS 2021 paper: How ISO-C became unusable for operating system development

View Fullscreen
Skip to PDF content
Categories
C standard

Memory model and semantics for C

A perceptive note from Linus Torvalds about the C/C++ “memory model” is reproduced below.

From Linus Torvalds <>
Date Thu, 7 Jun 2018 08:40:49 -0700
Subject Re: LKMM litmus test for Roman Penyaev’s rcu-rr
share 0
On Thu, Jun 7, 2018 at 7:57 AM Alan Stern <stern@rowland.harvard.edu> wrote:
>
> You can look at a memory model from three points of view:
>
> 1. To a programmer, the model provides both guarantees (a certain
> code snippet will never yield a particular undesired result)
> and warnings (another snippet might yield an undesired result).
>
> 2. To a CPU designer, the model provides limits on what the
> hardware should be allowed to do (e.g., never execute a store
> before the condition of a preceding conditional branch has been
> determined — not even if the CPU knows that the store would be
> executed on both legs of the branch).
>
> 3. To a compiler writer, the model provides limits on what code
> manipulations should be allowed.
>
> Linus’s comments mostly fall under viewpoint 2 (AFAICT), and a lot of
> our thinking to date has been in viewpoint 1. But viewpoint 3 is the
> one most relevant to the code we have been discussing here.

Hmm. Yes. I’ve been ignoring it because we’ve historically just
“solved” it by having barriers (either “asm volatile” with a memory
clobber, or just a volatile access) for the cases under discussion.
There isn’t a lot of room for compiler games there. We’ve had issues
with compilers _elsewhere_, but when it comes to memory models, we’ve
always solved it with “hey, let’s make that access volatile”, or “we
will force the compiler to use *this* instruction and nothing else”.

So we’ve never actually had much worry about what a compiler could do
for these particular issues.

In fact, one of the reasons I personally doubt we will ever use the
C++ memory model things is that I simply don’t trust the stanards body
to do the right thing. The discussion about control dependencies vs
data dependencies made me 100% convinced that there is no way in hell
that the C++ standards body model can ever work reliably.

Writing the requirements down as English, and writing them down as an
“abstract machine” that had a lot of syntax caused untold and
completely unnecessary verbiage, and made the end result
incomprehensible to any normal human. Very much so to a compiler
writer.

So honestly, I’ve given up on the C++ memory model. We’ve done quite
well with inline asm and “volatile”, and since I do not believe we
will ever get rid of either, the C++ memory model isn’t much of an
improvement.

And notice that this is very much a fundamental doubt about the whole
approach that the standards language is taking. I’m not doubting that
a memory model cannot be defined. I’m doubting that it can sanely be
described with the approach that the C standards body has.

Honestly, if the C++ standards body had taken a completely different
approach of actually *definining* a virtual machine, and defining the
actual code generation (ie the language would actually *define* what
every operation did in the virtual machine), and defining what the
memory ordering within that virtual machine was, I would give it a
chance in hell of working.

But that’s not what the C++ standards body did. Instead, it tried to
define things in terms of “dependency chains” and other very
high-level abstractions.

So I do not believe for a second in the C++ memory ordering. It’s
broken. It’s broken for fundamental reasons, and I doubt we’ll ever
use it because no compiler writer will ever get it remotely right.

> Saying that a control dependency should extend beyond the end of an
> “if” statement is basically equivalent to saying that compiler writers
> are forbidden to implement certain optimizations.

Honestly, what I think the standard should do is *define* that

if (a) B else C

is defined to generate the code

load a
test
je label1;
B
jmp label2
label1:
C
label2:

in the virtual machine. And then each operation (like “load” vs
“load_acquire” vs “load_volatile”) would have well-defined semantics
in that virtual machine. And then a compiler writer would be able to
do any optimization he damn well pleased, as long as it is
semantically 100% equivalent.

That would actually give a program well-defined semantics, and I
guarantee it would make compiler writers happier too, because they’d
have a definition they can follow and think about. The memory ordering
requirements would fall out from the memory ordering defined for the
virtual machine, and then that machine could be described sanely.

In the above kind of situation, I believe we could have described what
“control vs data dependency” means, because you could have specified
it for the virtual machine, and then the compiler writers could
determine from that well-defined flow (and the kind of load they had)
whether they could turn a data dependency into a control dependency
during optimization or not.

But that’s not how the C standard is written, and it’s not how the
people involved *want* to write it. They want to write it at a high
level, not a low level.

End result: I really don’t trust what the C++ memory ordering
semantics are. It’s all much too wishy-washy, and I don’t think a
compiler writer can ever understand it.

> Now, my experience
> has been that compiler writers are loathe to give up an optimization
> unless someone can point to a specific part of the language spec and
> show that the proposed optimization would violate it.

I agree. Which is why we sometimes use the big hammer approach and
just say “don’t do this optimization at all”.

But it’s also why the language definition being unclear is so
horrible. It’s sometimes simply not all that obvious what the standard
actually allows and what it doesn’t, and memory ordering is going to
be way more fragile than even the existing confusion.

So I agree 100% with you that the LKMM cases are not likely to affect
the C standard, and not affect compiler writers.

But I also think that’s largely irrelevant, because I don’t think it’s
worth worrying about. I don’t believe we will be using the standard
memory ordering, because it’s not going to end up usable, and we’ll
continue to roll our own.

I did hope a few years ago that that wouldn’t be the case. But the
discussions I was involved with convinced me that there’s no hope.

Linus

\

\ /

Categories
C standard computer architecture programming languages

unfashionable C

In computer science academia, C  along with UNIX, and PDP11s, is as unfashionable as can be: the equivalent of other 1970’s relics, like polyester leisure suits and mullets.

In 2018 ACM Queue published an essay by David Chisnall called: C Is Not a Low-level Language: Your computer is not a fast PDP-11  that expresses many common misconceptions about C and also takes the time to make a bunch of incorrect claims about computer architecture.  The same authors 2015 ASPLOS paper  Beyond the PDP-11: Architectural Support for a Memory-Safe C Abstract Machine   has much more interesting information about how C is used in practice and about an alternative computer architecure, but I want to focus on the first, because I think the general tendency in academic Computer Science to dismiss C as an embarassing fashion faux-pas has important consequences.

Let’s go through some of Chisnall’s article, starting with  this  claim:

“Most of the complexity involved [in hardware caches] comes from supporting a language [C] in which data is expected to be both shared and mutable as a matter of course.”

Although the recent C11 standard tried to graft on some ideas about concurrency (not a good idea or well done either), historically C doesn’t have  have any notion of concurrency or data sharing1. The first wide use of “threading” in C applications involved UNIX fork/exec which doesn’t share any memory at all. The language designers made a conscious, and successful,  choice to leave such things outside the scope of the language.

BSTJ 57: 6. July-August 1978: UNIX Time-Sharing System: The C Programming Language. (Ritchie, D.M.; Johnson, S.C.; Lesk, M.E.; Kernighan, B.W.

The poor judgment of the C11 authors didn’t really change that.

“Creating a new thread [in C ] is a library operation known to be expensive,

C has threading libraries, but none of them is required (otherwise you couldn’t develop operating systems in C or support multiple thread models).   C thread creation is also not known to be expensive. Determining factors are implementations,  processor architectures, and, for user threads, operating system interfaces.

so processors wishing to keep their execution units busy running C code rely on ILP (instruction-level parallelism).” 

Instruction level parallelism predates  C by 10 years and is not specific to any programming language. The first production computer  with ILP  was the CDC 6600, brought to market in 1964 and intended to run FORTRAN.

In the wake of the recent Meltdown and Spectre vulnerabilities, it’s worth spending some time looking at root causes. Both of these vulnerabilities involved processors speculatively executing instructions past some kind of access check and allowing the attacker to observe the results via a side channel. The features that led to these vulnerabilities, along with several others, were added to let C programmers continue to believe they were programming in a low-level language, when this hasn’t been the case for decades.

The CDC 6600 also had speculative branch prediction as did the IBM 360/91 (1967).  C was developed in the 1970s, well after and only became popular in the 1980s or later.

The root cause of the Spectre and Meltdown vulnerabilities was that processor architects were trying to build not just fast processors, but fast processors that expose the same abstract machine as a PDP-11. This is essential because it allows C programmers to continue in the belief that their language is close to the underlying hardware. In contrast, GPUs achieve very high performance without any of this logic, at the expense of requiring explicitly parallel programs.

Let’s go through these:

  • GPUs are primarily programmed in C dialects, so I’m not sure what is going on there. Using C was the easy choice for GPU makers  because of C’s deliberately incomplete nature (see below).
  • What C programmers believe about  C does not matter to computer architects.
  • The root cause of the Spectre and Meltdown failures is that it is really hard to do out-of-order pipelines with speculative execution and buffered memory access (there is way too much state moving too fast) but the performance advantage makes it hard to pass up.
  •  As for PDP-11s, this is a common error.  C was ported to  IBM/370, Honeywell 6000, Inter data 8/32, Sel86, Data General Nova, Vax and other processors in the mid 1970s – back in the days when there were multiple very different machine architectures.  By the mid 1980s,  when C  was becoming a popular language, and the ANSI standard was developed  the successor VAX architecture supported SMP and C was already highly popular on microprocessors. Much of what changed in C in that era was to make it portable to that wild profusion of architectures.

It’s worth noting that  Chisnall knows this last complaint is wrong, as he writes later:

The C model, in contrast, was intended to allow implementation on a variety of targets, including segmented architectures (where a pointer might be a segment ID and an offset) and even garbage-collected virtual machines.

In any case, although dismissing the PDP11 is  in vogue, the PDP-11 always had an MMU and caches and had parallel processing (with DMA capable devices and co-processors). Although the  article subhead is “Your computer is not a fast PDP-11”, really it is pretty much – just vastly larger (in terms of transistors ),  and faster.  Processor architectures today incorporate a lot of innovation, but use the same basic model programmers encountered 50 years ago and  X86-64 and ARM are both much closer to the PDP-11, for good or ill,  than to the 36 bit Honeywell 6000, the Interdata 8/32  ,  or the Intel 8086 and I486 for that matter.

Let Professor Hennessy explain:

 

From  John Hennessy https://p4.org/assets/P4WS_2019/Speaker_Slides/9_2.05pm_John_Hennessey.pdf

But Chisnall is not done with C.

We have a number of examples of designs that have not focused on traditional C code to provide some inspiration. For example, highly multithreaded chips, such as Sun/Oracle’s UltraSPARC Tx series, don’t require as much cache to keep their execution units full. Research processors2 have extended this concept to very large numbers of hardware-scheduled threads. The key idea behind these designs is that with enough high-level parallelism, you can suspend the threads that are waiting for data from memory and fill your execution units with instructions from others. The problem with such designs is that C programs tend to have few busy threads.

None of these are new or untested ideas. The Cray MTA architecture was a really interesting design that was even built and commercialized and it was designed to run C and Fortran.   The problem with such designs is that highly threaded algorithms are difficult and sometimes impossible (see Amdahl’s Law) in general. The exceptions are specialized processors such as GPUs (where C is used!).

For example, in C, processing a large amount of data means writing a loop that processes each element sequentially

In the Von Neumann style computer architecture (every single existing commercial processor), data is stored in memory and must be brought through the “Von Neumann bottleneck” into the processor. Caches help, and for certain types of processing, data can be moved and modified in larger chunks (vectors) which can be modified in parallel (SIMD processing is another 1960s innovation as explained in most intro computer architecture courses).   When the processor can operate on those longer vectors, it still relies on loops with the same characteristics as loops over bytes for large amounts of data.  Dennis Ritchie thought that C was too limited in its treatment of arrays, but being able to e.g. apply  a map to an array in the programming language just hides the loop.  Writing  \(A.map(x -> x*x)\) doesn’t magically transfer the whole array into the CPU vector unit which can, at best, multiply only a few elements at a time. For big arrays, it is still necessary to loop through the data, and for small arrays, there is not much to win ( here are some other ideas). Chisnall knows this too, because he’s unhappy at how hard it is to compile  vector loops in C.

To run this optimally on a modern CPU, the compiler must first determine that the loop iterations are independent. The C restrict keyword can help here. It guarantees that writes through one pointer do not interfere with reads via another (or if they do, that the programmer is happy for the program to give unexpected results). This information is far more limited than in a language such as Fortran, which is a big part of the reason that C has failed to displace Fortran in high-performance computing.

 Intel’s comments on the problems of vectorizing C and FORTRAN say the opposite. Vectorization is a hard problem – C’s restrict keyword is a good clue to the compiler, and possibly a vector data type would help (as the author argues)  but FORTRAN doesn’t have better information for the compiler. What FORTRAN has (a) no pointers which makes things simpler and (b) a whole lot of special purpose compiler directives and expert programmers who know how to exploit data parallelism.  FYI: C was not  intended by its designers  to displace Fortran in HPC.

Unfortunately, simple translation providing fast code is not true for C. In spite of the heroic efforts that processor architects invest in trying to design chips that can run C code fast, the levels of performance expected by C programmers are achieved only as a result of incredibly complex compiler transforms. The Clang compiler, including the relevant parts of LLVM, is around 2 million lines of code. Even just counting the analysis and transform passes required to make C run quickly adds up to almost 200,000 lines (excluding comments and blank lines).

Much of Clang’s complexity (and the same for GCC) comes from its role compiling C++ which is a gigantic language that  incorporates C as a sublanguage. Additionally, LLVM is designed as a general platform for a number of languages and  LLVM’s complexity is far from C specific.   What would be very interesting to know is how much of Clang’s C performance comes from anything past the 40 year old basic optimization methods like register coloring, peephole optimization, vectorizing and maybe unrolling loops. But here we turn to  real issues:

In C, a read from an uninitialized variable is an unspecified value and is allowed to be any value each time it is read. This is important, because it allows behavior such as lazy recycling of pages: for example, on FreeBSD the malloc implementation informs the operating system that pages are currently unused, and the operating system uses the first write to a page as the hint that this is no longer true. A read to newly malloced memory may initially read the old value; then the operating system may reuse the underlying physical page; and then on the next write to a different location in the page replace it with a newly zeroed page. The second read from the same location will then give a zero value.

This is an interesting point, because it reveals a common problem in current criticisms of C – and of the current efforts of the C Standards and C Compilers: a failure to understand the open border C design or maybe just dislike for it. C was intended as a systems and particularly operating systems language. Unlike Java and most other programming languages, a C program interacts directly with the hardware (and operating system) and other interfaces. Stephen Kell has a paper on precisely this point. That’s why C has no foreign function interface (FFI) but can directly call out to assembler or even support in-line assembler (and C doesn’t have an unsafe mode, because it is an unsafe mode).  Although the C standard document goes on about the “abstract machine”, C gets a lot of its utility from being able use operations that are semantically defined by hardware or other external interfaces. C benefits from incomplete semantics (which is why the ongoing mess about undefined behavior is so damaging to C programmers).  In the case mentioned by Chisnall, the FreeBSD operating system is playing games with the page allocator so allocated pages may not act like abstract store until a write operation2. This should not matter to a C program, because, especially in OS programming, this kind thing is not unusual.  Weird interactions with memory are one reason why C has the concept of intederminate values.  C code can even read device memory that changes its value on each read (think of a hardware fifo from a Analog-to-Digital sensor, for example). In these cases, the C compiler is supposed to let C operate as a high level assembly language and stay out of it.

And then Chisnall makes a really good point.

If an unspecified value for flow control is used (for example, using it as the condition in an if statement), then the result is undefined behavior: anything is allowed to happen. Consider the loop-unswitching optimization, this time in the case where the loop ends up being executed zero times. In the original version, the entire body of the loop is dead code. In the unswitched version, there is now a branch on the variable, which may be uninitialized. Some dead code has now been transformed into undefined behavior. This is just one of many optimizations that a close investigation of the C semantics shows to be unsound.

The important observation here is that  under the current interpretation of the C standard, a number of compiler optimizations are unsound and have been for some time. This has been tolerated because C is so very out of fashion and there is little appreciation of  the basic design concepts of the C language (except from people who use it.)  What is going on here is that standards contributors and compiler developers who start with the assumption that C is an obsolete and semantically confused language feel no obligation to play fair with the programmers who they believe are making a mistake even wanting to write code in the language.  This is why Chris Lattner of LLVM ends his gloomy (and insightful) analysis of the state of C compilation with a suggestion that programmers should switch to another language (like his own). And that is unfortunate because  C is far from a perfect language and slow changes in computer architecture are frustrating, but if you don’t know what works and what doesn’t work, you won’t be able to fix anything. And, finally, some things from the 1970s were pretty good.

 

NOTE 1: The unnecessary complexity of shared data in caches is unpleasant but that’s not C’s fault.

NOTE 2: The much loathed Bourne Shell, in addition to using the pre-processor to pretend it was written in ALGOL for unknown reasons, also implemented a user mode virtual memory with C/UNIX signals. It allocated virtual memory addresses without bothering to call the OS for more memory, and then caught write traps and tried to fix things.

Categories
C standard

Undefined behavior in C is a reading error.

Considering how important “undefined behavior” has become to C semantics and the ISO/IEC JTC1/SC22/WG14 Committee, the lack of any reference to it in the K&R ANSI book is notable and the description in the 1999 C Rationale was quite modest.

Undefined behavior gives the implementor license not to catch certain program errors that are difficult to diagnose. It also identifies areas of possible conforming language extension: the implementor may augment the language by providing a definition of the officially undefined behavior. – C Rationale

And yet, a misreading of C89 has turned this simple property into a serious threat to C semantics.

The destructive prevailing interpretation

The governing provision in C89 starts:

Undefined behavior — behavior, upon use of a nonportable or erroneous program construct, or of erroneous data, or of indeterminately-valued objects, for which the Standard imposes no requirements.

The obvious reading of this passage is that it simply naming the class of behaviors where the Standard doesn’t specify what happens as “undefined behavior”.  But almost immediately, this passage was interpreted by self-appointed experts on the comp.lang.c mailing list  to mean that  “the Standard imposes no requirements” on how compilers can implement undefined behavior. This became the prevailing interpretation and C compilers rely on it to justify all sorts of “optimizations” even though it is an unlikely reading of the text and damages the semantic coherence of the language.    John Regehr explains some consequences, using the example of the surprising  undefined behavior caused by shifting  by more than the number of bits in an “int”:

If any step in a program’s execution has undefined behavior, then the entire execution is without meaning. This is important: it’s not that evaluating (1<<32) has an unpredictable result, but rather that the entire execution of a program that evaluates this expression is meaningless. Also, it’s not that the execution is meaningful up to the point where undefined behavior happens: the bad effects can actually precede the undefined operation.

So, “i << 32” buried in a million lines of database code makes the entire program junk – supposedly as an “optimization”!  That is not the end of the destructive super powers of undefined behavior under the prevailing interpretation, because the compiler developers claim that no requirements are imposed on when they can change how they implement undefined behavior.  Chris Lattner of LLVM warned  that thanks to unrestricted undefined behavior, “huge bodies of C code are land mines just waiting to explode.” The argument is that maybe something  worked in one  way for 20 years, but it was always undefined behavior so the compiler is free to delete it, detonate it, replace it with something else or change behavior in any way, at any time (see this peculiar argument on the gcc bug list ).  Apparently, even then, the compiler could change its mind tomorrow or 5 minutes later!   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  (even as to stability!).

This reading would imply that use of any nonportable program construct or data error or indeterminately-valued object produces undefined behavior  but  WG14  is  not  ready to suppose that the ANSI C standard invalidated nearly every C  program (system calls are nonportable, for example, and malloc returns a pointer to indeterminately valued objects).  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” ( compiler developers have expanded  the list  on their own initiative without documenting much).  The WG14 Committee   also ignored the next sentence in C89, which is an apparent contradiction because it —  imposes requirements on how compilers may implement undefined behavior.

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

In terms of ISO/ANSI conventions, this second sentence is “normative” (imposes requirements) and “Permissible” is a “shall” word (meaning “must” ). The permissible range of undefined behavior went from ignoring the situation (for those difficult to diagnose errors per the Rationale)  to behaving in a documented manner characteristic of the environment, to flagging an error. What is conspicuously missing from this list of permissible undefined behaviors is any hint that undefined behavior renders the entire program meaningless,  any  license for the kinds of  dramatic and unintuitive transformations we’ve seen from the compilers, and any indication that undefined behavior should be a vehicle for permitting optimizations.

A constructive interpretation.

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.

Undefined behavior — behavior,  upon use of those particular nonportable or erroneous program constructs, or of erroneous data, or of indeterminately-valued objects, for which the Standard imposes no requirements.

That is, we take the comma seriously so  that the sentence is read to be limiting the category of “undefined behavior” to uses of certain constructs and data that have not been otherwise defined in the Standard. The sentence doesn’t say anything about implementation, because that is covered in the next sentence with the permissible list. Returning a pointer to indeterminate value data, surely a “use”, is not undefined behavior because the standard mandates that malloc will do that.  Use of “asm” does not cause undefined behavior although it is  nonportable because the standard (glancingly) mentions using asm.  Instead of unleashing the compiler to make arbitrary changes, the provision limits what the standards process could dump into the  undefined behavior bucket.  With this interpretation, the passage as a whole makes sense – and is in agreement with the Rationale. We don’t have to ignore the list of uses that can trigger undefined behavior, we don’t have to ignore the range requirements of the second sentence, we can get some intuition about what should be undefined and what should not be, and undefined behavior stays  a manageable concept, instead of creating a giant breach in the hull of the semantics. In retrospect, it may have been an error to  believe everything claimed  in internet discussion forums like comp.lang.c.

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:

  1. ignore the situation, generate a “shl” instruction for x86 or the appropriate instruction for other architectures and let the machine architecture determine the semantics. In this case, the programmers screwed up because x86 will truncate the shift value to 5 bits but the “permissible range” allows the compiler to escape all blame and let the programmers either find the problem or not.
  2. behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message) – warn the programmer on an X86 and just compile on ARM.
  3. terminating a translation or execution (with the issuance of a diagnostic message) – “Error: Guard your shift left to a machine appropriate number”.

Explaining why the Standard text would decree that  no requirements are imposed in one sentence and then go on to  impose requirements in the next sentence was apparently awkward, so the WG14 committee solved the problem by making a submarine change to the passage in C99.

Undefined behavior —

behavior, upon use of a nonportable or erroneous program construct, of erroneous data, or of indeterminately-valued objects, for which the Standard imposes no requirements. [insert newline]

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

Thanks to Eskil Steenberg for pointing out the difference between C89 and C99 on this point.  Under ISO rules, inserting the word “NOTE” changed the second sentence from “normative” (mandatory) to non-normative (advisory or informational), and  replacing the requirement word “Permissible” with the informational word “Possible” emphasized the optional nature of the range of behaviors. Currently, this second sentence is completely ignored in WG14 deliberations and apparently is also ignored as even a suggestion by compiler developers. Someone felt the need to weaken this sentence, I can’t find any records of the discussion.

The Prevailing interpretation is fatal to C

So what does it matter that 40 years ago, a murky section of an often murky document could have been misinterpreted?  It matters because over time the Standard and the common compilers have  made C an unsuitable language for developing a range of applications, from memory allocators, to cryptography applications, to threading libraries and, especially operating systems. We have the absurd situation that C, specifically constructed to write the UNIX kernel, cannot be used to write operating systems. In fact, 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 (with no guarantees about future “optimizations”).  The Postgres database also needs some of these flags as does the libsodium encryption library and even the machine learning tensor-flow package.

Because the prevailing interpretation of undefined behavior is so powerful, WG14 and the compiler developers have made it their goto method to  enable  “optimization” and  add to type safety and other rules. Instead of adding rules for optimization in the optimization section of the standard, WG14  has preferred to expand the domain of undefined behavior (often based on completely unsupported assumptions about efficacy) so compilers have a free hand. Instead of coming up with coherent rules for how to access memory via pointers, WG14 has simply declared a large part of customary C usage to be undefined behavior and left it to the compilers to figure out what that means.  As a result, as Lattner pointed out this means the C code base is unstable and:

There is No Reliable Way to Determine if a Large Codebase Contains Undefined Behavior

Compilers have become more powerful (opening up new ways to exploit undefined behavior) and the primary C compilers are free software with corporate sponsors, not programmer customers (or else perhaps Andrew Pinski would not have been so blithe about ignoring his customer Felix-gcc  in the GCC bug report cited above). All these help C semantics continue to degrade. There is even  a widely supported (within the standards body) proposed addition to the C Standard which will radically expand the application of undefined behavior to pointers.

None of this is necessary. C can accommodate significant optimization while regaining semantic coherence – if only the standard and the compilers stop a lazy reliance on a mistaken reading of “impose no requirements”.  A standard is supposed to impose requirements and provide clear guidance to programmers and implementors.

See also:   the PLOS paper, or Undefined Behavior and the Purpose of C” , Torvalds on alias, Dennis Ritchie on noalias, and a really simple example

Thanks to Robert Seacord and Eskil Steenberg for reading early versions of this note and providing suggestions.

Categories
C standard programming languages software security

C is not a serious programming language

The C Standards process over the last few decades has addressed both optimization and pointer type safety largely through a concept called “undefined behavior”.  The idea is that instead of  positive rules for what compilers and programmers can do, the Standard will identify some program behavior as something compilers can interpret how they want — really without any guidance at all. These things are not syntax errors that must cause the compiler to reject code or even, necessarily things the compiler must warn about, but are instances of behavior that are outside the standard. It is not even clear whether “undefined behavior” is erroneous at all or even avoidable.  I think this whole process is due to a misreading of the C89 standard, but more importantly, it’s sloppy, makes it hard for programmers to have an intuition about the language, and leads to paradoxical results or nasty surprises.  For example, writing a value to a  variable from a pointer that has been advanced past the end of the object it was supposed to point to has been sort-of-kind-of designated as “undefined behavior”. Here’s  an example: the output of a simple C program compiled and “optimized” by gcc 11

pointer1 = 0x404039 pointer2=0x404039 they are not equal

They look equal, don’t they? Clang 12, on the same code uses  normal arithmetic to compare numbers.

pointer1 = 0x404039 pointer2=0x404039 they are equal

An earlier version of gcc, gcc 4.8.3 also knew how to compare numbers:

pointer1 = 0x404039 pointer2=0x404039 they are equal

And Gcc 11 again, but this time with the optimizer turned off (-O0):

pointer1 = 0x40403a pointer2=0x40403a they are equal

Here’s the code ( see NOTE1 in the code )

#include <stdint.h>
#include <stdio.h>

typedef char T;
T p[1], q[1] = {0};
int main(){
        T *ip = (p-1);//NOTE1. change +1 to -1 if gcc -O0
        T *iq = q;
        printf("pointer1 = %p pointer2=%p ",ip,iq);
        if (iq == ip) {
              printf("they are equal");
             }else printf("they are not equal\n");
}

The explanation is that gcc notices that ip has been set to a fishy address

:6:8: warning: array subscript -1 is outside array bounds of 'T[1]' {aka 'char[1]'} [-Warray-bounds]
6 | T *ip = (p-1);//add if gcc -O0
|  ^~

and, gcc 12 helpfully “optimizes” on the basis of “ip”  holding an “invalid” address, perhaps reasoning that the two pointers “cannot” be equal. Under the prevailing interpretation of the C Standard, compilers can assume “undefined behavior” cannot happen, even if they generate code that makes it happen  At least, in this case, there is a warning, but often these “optimizations” are silent. The rationale is that programmers should not be messing about looking at the order of variables in memory (even though that’s not unusual in C) and that compilers should be able to optimize under the assumption that pointer arithmetic does not ever steer a pointer between objects.  To be fair, most of the time that a pointer goes beyond the boundary of an array, it is an error.

Here’s the link on Compiler Explorer. The example is modified from one given in a post by  Ralf Jung  who attributes it to Chung-Kil Hur (I’m sure both disagree with my reaction).

If C was a new programming language, you might decide that the %p output should provide the address and some additional data.

pointer1 = 0x404039 (int) pointer2=0x404039 (int, invalid)  they are not equal

That would make some sense. But in this case, you’d also have to think through all the implications of this design decision, which nobody has done (see below).  For example, since the 1990s, C Standard has made it impossible to write memory allocators in conforming C. Suppose we have a network application that is performance constrained by “malloc” and we want to put a caching allocator for small and jumbo packets on top of malloc:

(small_packet_t *)newsmall();  (large_packet_t *)newjumbo();  freepacket(void *);

The idea is that when either allocator has too little memory, it calls malloc (or something else) to get a big chunk of memory, puts it into a list of free storage, and slices it up when it is asked to allocate. Maybe something like

free_block_t *p; …. p =malloc(K); p->size = K; p->next = Head; Head = p;

But according to the sloppy type rules in the Standard, after writing through a “free_block_t” pointer, that block now has “effective type”  of “free_block_t” and if we allocate part of it to a caller that then writes to it as a small_packet_t, the behavior is undefined and all bets are off because we have tried to store a value to an object with a different effective type. Even worse, imagine that “freepacket” tries to merge freed packets into blocks again! Suppose 4 small packets can be freed and then consolidated and allocated as a single jumbo packet.  Nope. No can do.  Once storage has an effective type, it is frozen to that type.  How does malloc/free work then? Oh, easy, it is special cased in the standard. Similarly, there is a special case for char pointers so that memcpy can be implemented, even if not very efficiently. To get other allocators to work, C programmers rely on “opaque” interfaces. If the allocators are in a separate file, and we do not have link time optimizers, then probably the compilers won’t be able to learn that the type rules are being violated. But then as link time optimization (LTO) comes in, the whole thing may silently be “optimized” to fail.   One of the other ridiculous  properties of the undefined behavior rules is that they are unstable or ephemeral and depend on the current capabilities of the compiler to see through opaque interfaces or otherwise figure out about some particular instance of undefined behavior.  That is, the rule is something like: “this will work as expected until the compiler figures out that it is undefined behavior”. As you can see above, gcc learned to recognize the undefined behavior somewhere between versions 4.8 and 11 and still can’t figure it out at lower levels of optimization.

Here’s another “optimization” from Clang-C

int are_we_out_of_memory(void) {
        int *y = malloc(2);
        return y == (int*)NULL;
}

Under -O3 optimization, this always returns 0 in Clang-C. Why?  Perhaps in this case Clang is reasoning that the pointer becomes invalid when the function returns because the storage, if any, returned by malloc is now inaccessible, so the comparison is invalid. Who knows? Optimization is easier if we don’t have to care about correctness.

Here’s a question  I asked some compiler and standards developers: can the compiler assume “b” is false and delete the whole branch?

int getadata(int b, char *buf, int n){
       int *p; //forget to initialize
       if(b){
           read(0,buf,n);
           *p =0;
       }
       return 1;
}

Since p is uninitialized, the compiler may decide the assignment, which is “undefined behavior” can’t happen, so the whole branch can be assumed away – and this reasoning would apply no matter what else we do inside the branch. So the code that calls “getdata(1,buff, 1000)” over and over will get nothing done and might even itself be “optimized” away.  Imagine:

char *buf = malloc(1000); getdata(1,buf,1000); if(buf[23]== 'x'){ ....}

 

On the basis of the first “optimization”, the compiler may see that the “if” depends on reading uninitialized memory and delete that case too. With a low level of optimization, the compiler may generate those reads and then silently delete on a higher level of analysis – and different C compilers can make different choices. Effectively, programmers have to guess.

Here is a hypothetical case:

char *b,good;
n = read(fd,b,m);
good = b[m-1];// undefined if n < m
if(n == m  )dosomething(good);
else badread(good);//can we delete this case

Right now, code  like this will compile as expected. But that’s only because the compilers do not incorporate knowledge about “read”. Suppose the compiler understands that if n != m, then b[m-1] is uninitialized and deletes the badread case, because otherwise “good” is the result of reading uninitialized memory which “can’t happen”? So this code may work, contingent on the compilers not figuring out what “read” does.

There is right now in the C Standards process an effort to incorporate pointer “provenance” so that compilers are permitted to consider pointers as pairs (provenance, abstract address) and an 80 page proposal that appears to have a lot of support.  You can read some of the ongoing discussion about this proposal in the message archive. One of the interesting things about this proposal, in the current state, is that it doesn’t provide any solution to the malloc issue – but suggests some solution should be found.  Similarly, it doesn’t discuss how mmap can work with the proposal. The proposal text is also ambivalent about how == should work for pointers. Why? Because it’s impossible for compilers to always correctly figure out the provenance of a pointer, however the proposers want the compilers to enforce provenance rules when they can. Programmers are supposed to just figure it out.

 

See also the purpose of C.

 

Categories
C standard programming languages

undefined behavior and the purpose of C

Kafka The Castle

The C programming language is designed to  let programmers  work  at both low and high levels. In particular, for applications like operating system development,  cryptography,  numerical methods, and network processing, programmers can go back and forth between treating data as representing abstract types and as machine addressable sequences of bits, between abstract operations and low level, machine dependent operations.  The language has, by any account, been spectacularly successful and remains the essential systems programming language. Over 45  years, one would expect some limitations would show up,  but C currently suffers not just from it’s own limitations but from the combination of being being profoundly out of fashion (see the somewhat mixed up critique here for an example)  and the misguided bureaucratic attentions of the ISO standards process which has had  a negative effect on the development of C compilers. At the heart of the problem is that the C standard process is muddying C semantics while also facilitating dubious “optimizations” from the larger compiler projects.  The key aspect of these “optimization” is that they break C programs that work with lower levels of “optimization” or earlier  The situation was concisely summarized by Linus Torvalds: “the C standard is _clearly_ bogus shit“.  And Torvalds is not the only person to object.

  • An alarming  CERT security alert   was issued in 2008:   “Some C compilers optimize away pointer arithmetic overflow tests that depend on undefined behavior without providing a diagnostic (a warning). Applications containing these tests may be vulnerable to buffer overflows if compiled with these compilers.” 
  • Linux developers forced  GCC and Clang compiler developers  to provide an ad-hoc collection of compiler flags for an unstable non-Standard dialect of C that turn off some of the “optimizations” supposedly permitted by the C standard.
  • A  warning from the chief Clang architect that compiler changes  mean that “huge bodies of C code are land mines just waiting to explode” (followed later by a suggestion that programmers switch to other languages).
  • A  paper from the foremost researcher in cryptography asking for a version of C that would be “safe” from dangerous “optimizations”.
  • A polite and  completely ignored  academic proposal by Regehr et al for a “friendly” C compiler and standard. 
  • A really excellent critical  academic analysis, by M. Ertl  also ignored, and see also  this paper. 
  • A graphics programmer practitioner critique  by Eskil Steenberg.

As an example of what provoked these reactions, consider a small C program that, without a warning, when passed though the current gcc and Clang highest level optimizers can’t recognize a negative number as a negative number. The same program  works correctly when compiled at lower levels of “optimization”, or with optimizations by earlier versions of clang and gcc or even currently by the Intel C compiler.  And consider the following, idiomatic C code, transformed into an infinite loop that never gets to emergency shutdown.

//keep opening valve until pressure down or do emergencyshutdown
for(int i=0; i >=0; i++){ //try it a bunch of times
     if ( getpressure() > DANGER)openvalve();
     }
if (getpressure() > DANGER)emergency_shutdown();

You can see how this works in the gcc8 generated machine code for the x86 – a processor family that natively wraps arithmetic overflow to do the right thing. The increment, the check, and the call to emergency shutdown are all deleted by the compiler – as an “optimization”. 

/Machine code output of GCC8 with O3 optimization level.
f:
        sub     rsp, 8
.L4:
        call    getpressure
        cmp     eax, 10
        jle     .L4
        call    openvalve
        jmp     .L4

Of course, this code is perhaps not the best C code, but it accords with the customary and expected behavior of the language over decades of practice. Earlier versions of Gcc compile the code correctly as does the Intel compiler, even later versions compile it correctly unless the higher optimizer levels are invoked. So tested, working safety critical code, moved to a new version of the same compiler will fail with no warning (whoops, sorry about the refinery explosion). And all this apparently meets the requirements of the C standard.

  1. The ISO C standard committee  has spent decades on a botched effort to strengthen C type system in a way that has produced a contradictory and complex set of rules under which a vast body of C code can be considered to embody “undefined behavior” (often with no remedy in the Standard).  Not only is is not possible to access “device memory”, but it is impossible to write a memory allocator let alone a virtual memory system, check for arithmetic overflow, reliably check for null or invalid pointers, checksum network packets,  encrypt arbitrary data,  catch hardware interrupts, copy arbitrary data structures, use type punning, or, most likely,  to implement threads. Application programs written in C face the same problems and worse. For example, the standard POSIX function  “mmap” appears to be intrinsically “undefined behavior”.  This only going to get worse. For example see recent proposals to add pointer “provenance” to the standard.
  2. The primary open source compiler developer groups have seized on the sloppy definition of  undefined behavior in the Standard to justify a series of increasingly dangerous silent code transformations that break working code. For reasons explained below, I will call these transformations  Beyond Guideline Transformations (BGTs). 

The key passage in the C11 Standard is the following (my highlight in red)

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).
  • 3 EXAMPLE An example of undefined behavior is the behavior on integer overflow.

 The compiler developers have seized on “imposes no requirements” to claim a license for arbitrary program transformations in the presence of “undefined behavior”. As pointed out by Eskil Steenberg the C99 standard changed the wording of this provision to  “Possible”  where the C89 standard used the word “permissible” – which would imply that the compilers must restrict themselves to the range of behaviors. The C99 Standard also moved the sentence on the range of behaviors to a note so which in the arcane world of ISO standards, transforms a rule into a “non-normative”  suggestion.  This has been taken to license reasoning such as:  since overflow of signed integers is “undefined behavior” and the standard imposes no requirements, the compiler can assume that signed overflow never happens and delete a test for overflow as an optimization.    GCC/Clang developers, with the tacit acquiescence of the ISO standards committee, now claim the compiler is free to assume undefined behavior “can’t happen” and that the compilers can silently remove programmer checks for it – even while generating code that produces the condition. This reasoning, such as it is, clearly violates the Standard definition of “optimization”, but nobody seems to care.

Clang architect Chris Lattner believes there is nothing the compiler developers can do: 

The important and scary thing to realize is that just about *any* optimization based on undefined behavior can start being triggered on buggy code at any time in the future. Inlining, loop unrolling, memory promotion and other optimizations will keep getting better, and a significant part of their reason for existing is to expose secondary optimizations like the ones above. To me, this is deeply dissatisfying, partially because the compiler inevitably ends up getting blamed, but also because it means that huge bodies of C code are land mines just waiting to explode.

You’d imagine that faced with warnings like this, complaints from influential C practitioners like Torvalds and DJB, a CERT advisory, and a number of academic papers, there would be some concern at the WG14 committee that develops the C standard – but no. 

When I visited the ISO WG14 C Standards committee meeting in Pittsburgh 2018 to ask for some corrective action, I found a peculiar lack of urgency.  The most interesting comments were from a long-time committee member who seemed to believe that C had become a hopeless cause and from another attendee who suggested that fixing contradictions in the standard was not urgent because there are so many of them.

I refer to these strange transformations as “Beyond the Guideline”, because they violate the range of possible/permissible behaviors in the standard definition of undefined behavior.

At one time, it was generally understood that the undefined status of signed integer overflow meant that the native arithmetic operations of the target processor determined the result: so that often  “i+ j” in C can be compiled to a single machine instruction.  If the result of the addition overflows the processor representation of an signed integer – anything could happen -the burden was on the programmer, processor, and execution environment to detect and handle the problem.  This is either “ignoring the situation” or “behaving during [..] program execution in a documented manner characteristic of the environment” : the compiler was not required to do anything about the overflow.  In fact, the standard modern processors  roll over as expected, although there are some processors that generate traps and some embedded devices with things as odd as saturating arithmetic.  None of that is a problem under the customary compilation of the language. The compiler can just leave it up to the underlying machine, the execution environment, and the programmer to sort out. The “beyond the guideline” (BTG) approach is relatively new and is still unknown to many practitioners and involves major conflicts with the ANSI C definition in the second edition Kernighan and Ritchie book: which is the definitive specification .   You can follow Linux’s lead and block the overflow  “optimization” with “frwapv”  which forces wrapping semantics (in some places) but that’s not even necessarily what programmers want and there are many other places where C code is vulnerable to similar transformations. For example, in machines with linear addressing, it is not unusual to check a pointer is in a range with code like:

if( p < startptr || p >= endptr)error()

This code is straightforward and easy to compile on the dominant processor architectures of the day, ARM, x86, MIPS, and similar. It might be a problem on, say, segmented architectures or elaborately typed architectures such as the not lamented Itanium.  It’s also possible that, depending on how the pointer “p” is generated that it might violate complex, contradictory,  and hard to understand type rules for pointer comparisons and fall into the “undefined behavior” bucket. In that case, the compiler developers claim that they can silently delete the check – after all, undefined behavior “can’t happen”. All the code that depends on these types of checks, checks that are reasonable C code and that have worked for decades, may encounter an unpleasant surprise at any future time when the compilers get around to “optimizing” those checks away. And, as usual, there is no guaranteed way in the Standard to “fix” this check. Suggestions involving converting pointers to integers run into other undefined behavior and the optional status of the required data type.

Since common sense has not sufficed, both the compiler development groups and the Standards need an intervention.  The decision to ignore the guideline is easily repaired, mostly by reversing the wording and formatting changes. 

undefined behavior behavior, upon use of a nonportable or erroneous program construct or of erroneous data, for which this International Standard imposes no requirements other than that : Permissible 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). Undefined behavior is common in C programs and translators should document operation in the presence of undefined behavior. It is not acceptable to change the semantics of correct program structures due to undefined behavior elsewhere. 

I’d add the following note as well

NOTE: Undefined behavior, particularly, due to non-portable constructs is a normal component of C programs.  Undefined behavior due to errors that the translator can detect should produce a diagnostic message.

One of the common arguments made by some of the compiler developers who champion BTG transformations is based on a false dichotomy: that without license for BTG transformations, compilers would have to provide an intrusive run-time that guaranteed predictable results and the Standard would have to spell out every possible behavior. This speaks to a fundamental misunderstanding of the purpose and use of C. 

  • How can the compiler distinguish between an erroneous read of uninitialized memory which will produce unspecified results (or even a trap on some architectures) and a syntactically equal chunk of code that reads a memory mapped device control register which  cannot be written? The designers of C solved the problem by leaving it up to the programmer and the execution environment: the compiler produces a load operation, the semantics are not its problem – they are “undefined behavior”. 
  • How can the compiler or standard distinguish between a mistaken use of an integer pointer to access a floating point number and a numerical methods expert’s shortcut divide by 2 which involves changing the binary representation of the exponent? That’s not the responsibility of the compiler.
  • How can the compiler tell the difference between a null pointer dereference in user space where it will, usually, cause a trap on memory mapped systems, and one where the zero page is accessible memory? It cannot: the programmer and operating system can handle it. The best the compiler can do is warn.

What would be nice is if the compilers could warn about possible errors and if the Standard provided opt-in methods of locking down access methods and preventing common errors like array boundary and type violations.  C developers increasingly rely on sophisticated static analysis tools and test frameworks to detect common errors and have embraced methodologies to limit the kinds of haphazard programming that was common earlier. But all of that is very different from retroactive, silent, language changes based on opaque and often ill considered rules.

The developers of the C Standard were forced to add a hurried character pointer exception to their type rules when they discovered they had  inadvertently made it impossible to write the fundamental memcpy function in C. The exception makes the type rules ineffective while still being cumbersome ( Brian Kernighan made exactly this criticism of Pascal decades ago). And it certainly did not fix the problem.  For example, the Standard only makes malloc/free/calloc and similar work within the type system by treating them as special exceptions to the type rules (in a footnote, no less) and apparently nobody realized that those functions could not then be implemented in Standard C. 

Lattner is absolutely correct about the “land mines” which this approach to “optimization” produces but he is wrong to imply that the compilers are required to adopt the BTG  approach to undefined behavior or that the code triggering undefined behavior is necessarily “buggy”.  C compilers could optimize on undefined behavior, as they always have, without violating the guidelines suggested in the standard: as Intel’s ICC still does. The choice to go beyond the guidelines is an engineering choice.

The invisible advantages of BTG optimizations 

Some of the defenders of BTG optimizations argue that code producing undefined behavior is not actually C code and so doesn’t have a meaning. That kind of pedantic legalism has no support in the history of the language, the behavior of compilers (which have no trouble compiling and producing expected behavior from the same code prior to “optimization”) or the language of the standard – it’s just a pompous way of excusing crappy engineering.  The C-Standard is a train-wreck on its own, but it does not mandate the bizarre paradoxical undefined behavior GCC and Clang are choosing to haphazardly implement. 

The supposed motivation for BTG transformations is  that they enable optimizations. There are, however, only a bunch of dubious anecdotes to support the claim of great optimizations – not a single example of careful measurement.  And there are studies that show the opposite. Here’s the justification from one of the LLVM developers:

This behavior enables an analysis known as “Type-Based Alias Analysis” (TBAA) which is used by a broad range of memory access optimizations in the compiler, and can significantly improve performance of the generated code. For example, this rule allows clang to optimize this function: 
float *P;
 void zero_array() {
   int i;
   for (i = 0; i < 10000; ++i)
     P[i] = 0.0f;
 }
into “memset(P, 0, 40000)“. This optimization also allows many loads to be hoisted out of loops, common subexpressions to be eliminated, etc. This class of undefined behavior can be disabled by passing the -fno-strict-aliasing flag, which disallows this analysis. When this flag is passed, Clang is required to compile this loop into 10000 4-byte stores (which is several times slower), because it has to assume that it is possible for any of the stores to change the value of P, as in something like this: 
int main() {
  P = (float*)&P;  // cast causes TBAA violation in zero_array.
  zero_array();
}
This sort of type abuse is pretty uncommon, which is why the standard committee decided that the significant performance wins were worth the unexpected result for “reasonable” type casts.

This is a ridiculously contrived example, of course. The program, as written, makes no sense and will crash on any conceivable system.  If not setup to fail, any half-decent C programmer could have used a local variable parameter for the pointer (in which case -fno-strict-aliasing has no effect) or called memset directly. These are the kinds of things that C programmers find and fix using profiling.  Oddly, the compiler misses the big optimization, which is to do nothing – since nothing is done with the array before the program exits. So here we have the usual elements of an example of why C compilers need to make “unexpected” BTG results out of undefined behavior

  1. A minor or unnecessary optimization
  2. of a contrived example that shows nothing about actual applications
  3. that is possibly a undefined behavior optimization but not a BTG transformation
  4. that is accompanied by absolutely zero in the form of measurement
  5. that ignores actual optimization possibilities.

A  talk by Google’s Clang expert, Chandler Carruth on this topic has an even worse example.  Carruth gives an example of array indexing that has all of the first 4  characteristics above, plus the benefit that if you look at the generated code, the supposedly much better form taking advantage of undefined behavior for optimizations is not really any better than the original.  He also explains how the compiler cannot determine whether programs are correct (!) and makes an unfortunate analogy between compiler behavior and APIs. Imagine if operating systems, for example, were to caution developers that “anything can happen” if the parameters passed to an OS system call are not as expected. Programming languages should minimize surprise.

In the real world, the justification for BTG transformations is convenience for the compilers – which are increasingly driven by not only artificial benchmarks, but by their support for C++ and Java which are languages that have very different semantics. Operating on intermediate codes that are stripped of C specific semantics, it is difficult for the compilers to safely apply optimization passes without making dangerous C transformations. Rather than addressing the weakness of this internal representation of code, it’s easier to find loopholes that allow the customary semantics to be ignored.

 

C is not Java

Here’s something more from Lattner. 

Violating Type Rules: It is undefined behavior to cast an int* to a float* and dereference it (accessing the “int” as if it were a “float”). C requires that these sorts of type conversions happen through memcpy: using pointer casts is not correct and undefined behavior results. The rules for this are quite nuanced and I don’t want to go into the details here (there is an exception for char*, vectors have special properties, unions change things, etc). This behavior enables an analysis known as “Type-Based Alias Analysis” (TBAA) which is used by a broad range of memory access optimizations in the compiler, and can significantly improve performance of the generated code.

To me: “The rules for this are quite nuanced and I don’t want to go into the details here (there is an exception for char*, vectors have special properties, unions change things, etc)” means, “we mucked up the standard and we are going to cause many systems to fail as these nuanced rules confuse and surprise otherwise careful and highly expert programmers”.   Unexpected results are a catastrophe for a C programmer. Limitations on compiler optimizations  based on second guessing the programmer are not catastrophes ( and nothing prevents compiler writers from adding suggestions about optimizations). Programmers who want the compiler to optimize their algorithms using clever transformations should use programming languages that are better suited to large scale compiler transformations where type information is clear indication of purpose. As Chris Lattner notes:

It is worth pointing out that Java gets the benefits of type-based optimizations without these drawbacks because it doesn’t have unsafe pointer casting in the language at all.

Java hides the memory model from the programmer to make programming safer and also to permit compilers to do clever transformations because the programmer is not permitted to interact with the low level system.  Optimization strategies for the C compiler should take into account that C does not put the programmer inside a nice abstract machine.  The  C compiler doesn’t need to force C to become a 5th rate Pascal or Swift.  Unexpected results are far more serious a problem for C than missed minor optimizations.