Three modest proposals for fixing the C standard.
PLOS paper ISO C is not suitable for operating systems.
Torvalds on aliasing. Ritchie on aliasing.
Three modest proposals for the C standard WG14
Tag: c language
Categories
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 #includeint 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
Threads in C
There is a nice example thread semantics in a paper by David Goldblatt (P1916R0) which illustrates a couple of things about multi-core processing – including how interesting it is and how poorly defined the C11 atomic/thread extension is . A simplified version looks like this:
//Example1
int x=0; int y=0; int r1=0; int r2 =0; //globals
void t1() { r1=x; int local = r1; if (local == 0) { y=1;} } // thread1 code
void t2() { r2=y; x= r2; } //thread 2 code
When both threads finish, r1==0. How do we know that? Suppose r1 is not zero. It starts as zero, so it must have been changed somewhere, and the only place it is assigned a value is the first statement of thread1 where we see “r1 = x”. So we must have “x != 0” and, again, initially, “x == 0” so “x” must change before r1 is assigned and the only place x is assigned a value is in the final statement of thread2 “x=y”. So “y !=0″ is required before that assignment to get the result we want, and since initially ” y==0″ we look for a place where y is changed, and the only place is the final statement in thread1 “y = 1”, which is executed only if the conditional permits – which is only if “local == 0”, which is only if “r1 == 0”, which would contradict our premise. So, it is required that “r1 == 0” when these two threads complete. Now suppose that the programmer (or the compiler) is smart enough to optimize this code and decides that since we know “r1 == 0” is an invariant of the code, we can leave out the test:
//Example2
int x=0; int y=0; int r1=0; int r2 =0; //globals
void t1() { r1=x; y=1; } // thread1 code
void t2() { r2=y; x= r2; } //thread 2 code
It may appear that things are still good. The assignment to y happens only after the assignment to x. If “r1 != 0” then “x !=0” which means “r2 != 0” which means that “y !=0”, but the assignment to “y” in Thread1 happens AFTER the assignment to r1! But as Goldblatt notes, it is possible that running the code leaves “r1 == 1” – on an ARM processor. The ARM has what is called “relaxed” memory order. Loads and stores on a single core (and we assume our threads are running on single cores, perhaps incorrectly) all become visible sequentially following code order – so “y=1” happens AFTER “r1 = x” in thread1, but that nice ordering is not guaranteed between cores. Memory operations have been a bottleneck for a long time so processors look for ways to short circuit operations. On the ARM the two threads compile down to load and store operations:
//Example3
void t1() { 1: load register1a from Memory[x]; 2: store register1a to Memory[r1]; 3: store 1 to Memory[y]; } // thread1 code
void t2() { 4: load register1b from Memory[y]; 5: store register1b to Memory[r2]; 6: store register1b to Memory[x] } //thread 2 code
The compiler has figured out, in this code, that in thread2 it doesn’t need to load Memory[r2] back to a register since it has the value still in register1b: and in Thread1 it can leave “local” as a register. But the ARM processor is free to mess around with the order instructions complete, as long as the result does not change the computation within the core. The processor may notice that instruction 3 does not depend on any results of 1 or 2, so it can complete memory operations in order 3,4,5,6,1,2 which would let the 1 be stored in y before y was loaded into register1b – which allows r1 to end up with a value of 1.
Why does the original code work on the ARM then? Because the test “if (local == 0)” creates a dependency — the processor cannot evaluate local and complete this test until x has been loaded into a register in thread1. In the code below, (2a) must complete before 3 can happen, and 2a depends on the value loaded from x so that load has to complete before the assignment to y.
//Example4
void t1() { 1: load register1a from Memory[x]; 2: store register1a to Memory[r1]; 2a: if register1a != 0 skip the next instruction 3: store 1 to Memory[y]; } // thread1 code
void t2() { 4: load register1b from Memory[y]; 5: store register1b to Memory[r2]; 6: store register1b to Memory[x] } //thread 2 code
If the programmer or the compiler deleted the test as an optimization, it changed the semantics of the code. From my point of view, the first is ok and the responsibility of the programmer but the second possibility would be a miscompilation. But in ISO-C and the open source C compilers, preserving semantics through optimizations is not always necessary. In this case, the kind of mushy C dependency rules probably prevent the compiler from making this transformation in the original code, but Goldblatt shows a case where it can and does happen if the programmer adds an “else unreachable()” clause. In theory, “unreachable” is a clue to the compiler that the branch cannot be taken. The compiler, then, decides to eliminate the test, since the programmer told it that the test always produces true, and then the compiler produces code like in the second example.
//Example5
int x=0; int y=0; int r1=0; int r2 =0; //globals
void t1() { r1=x; int local = r1; if (local == 0) { y=1;}else unreachable();} // thread1 code
void t2() { r2=y; x= r2; } //thread 2 code
In the original paper, instead of the simple assignments of x and y, the code uses C11 “atomic” operations which are now becoming common in the standard open source C++ and C compilers – even though what they mean is not even clear to the people who wrote the specification. In this case, the original example uses atomic operations with a so-called “relaxed” memory order. Translated into C from C++
//Example6
atomic_int x = 0; atomic_int y = 0; int r1 = 0; int r2 = 0;
void t1() {r1 = __atomic_load_n(&x,__ATOMIC_RELAXED); int local = (r1 & 1); if (local == 0) {__atomic_store_n(&y,1,__ATOMIC_RELAXED);}}
void t2() { r2 = __atomic_load_n(&y,__ATOMIC_RELAXED); __atomic_store_n(&x,r2,__ATOMIC_RELAXED); }
In every modern processor I know about (including ARM, x86, MIPS, RISCV, Power … ), ordinary loads and stores of words (ints) are already atomic, so – currently – the compilers emit the same machine code with or without the C11 atomic operators. You can see this example, with conditional compilation using and not using the atomic operations here. One of the big supposed advantages of adding atomics to C is that they are portable but the example of P1916R0 shows that for even the simplest use, we can see different behaviors on different processors. I am ok with that because, to me, C is a low level language that exposes architectural differences like different word size and different memory rules. But C11 atomics/threads is built on the theory that C and C++ should not be low level languages. The compilers are supposed to “portably” figure out how to do atomic assignments to larger data structures too – somehow. That they cannot do so is a problem for mere practice, not theory.
The program of example1 in my version has “maybe undefined behavior” according to the C11 Standard and the compilers maybe are entitled to, at any moment, change the code in any arbitrary way, possibly by deleting one or both threads entirely or deleting reference to y in the first and to x in the second or – well, really anything. The reason the code has “undefined behavior”(maybe) is that any two threads that refer to the same variables without using atomic operations that do not have a “before” relationship as far as the C/C++ compiler is concerned have a “data race” and are undefined according to C11.
The execution of a program contains a data race if it contains two conflicting actions in different threads, at least one of which is not atomic, and neither happens before the other. Any such data race results in undefined behavior.
As far as C17 is concerned, there is no definition of “conflicting action” but perhaps what is meant is “conflicting evaluations”
Two expression evaluations conflict if one of them modifies a memory location and the other one reads or modifies the same memory location
The “maybe” is because the current compilers don’t do that kind of analysis (which is really hard) and because C11 atomics are supposed to be optional (after strong user pushback), but the standard text was not edited to make that clear. For example, the definition of “data race” depends on on “threads”, which are defined in a different supposedly optional part of C11. Before C11, C had no notion of “data race” because it didn’t know anything about threads. Suppose that the underlying OS implements threads as run-to-exit co-routines. In that case, threads 1 and 2 would not have anything like a data race and r1 would have to be 0 at the completion of both. Does the C compiler know what the OS or run-time is doing with threads? No. Not at all. Perhaps thread 1 and 2 will run on the same core with “memory fences” (to force completion of any delayed memory operations) between them. The compiler has no practical way to find out. Perhaps the threads themselves can switch cores between instructions (as in some architectures or maybe in a smart future OS). Or they could be in separate processes with separate address spaces (see: “fork”). This is why the designers of C left threads out of the language entirely – so that the language did not incorporate a complex but limited view of threading. Prior to C11, C had a successful history of implementing threads and concurrency control in libraries. The requirement for adding atomics/threads to C11 was kind of nebulous. The result is, well:
Here’s one way of thinking about why the out-of-thin-air problem is tricky to resolve: we want additional constraints on the concurrent part of the memory model, but the desire for those
constraints is motivated by the dependency ordering established during execution of the non-concurrent parts of the program on real hardware. So we want sequential code to maintain a(n implicit) memory ordering constraint on concurrent code. The problem of outlawing OOTA, then, is about defining which sequential dependencies the compiler is not allowed to optimize away.
This is the main topic of P1619R0: that C11 Atomics have a multiplicative effect on ISO-C’s “undefined behavior” problem by increasing the surface space of undefined behavior . You might ask: “Out of thin air? That sounds bad.” or “why is the compiler ‘optimizing away’ sequential dependencies that are expressed in the code some programmer wrote in the first place?”. The C standard text pretty clearly says that the compiler can reorder expressions within a statement, but cannot reorder statements. This is disputed within the standard body, where the argument is that reordering can happen if it does not change “observable state”. That’s a reasonable argument in the abstract because if the compiler reorders statements without changing the semantics, who could object? Imagine:
//Example 6 x = f(); //x is in a register ...do a bunch of stuff which does not involve y .. y = x; ---------Reorder---- x = f(); y = x; //while x is still in a register ... do a bunch of stuff
Unfortunately, figuring out what is observable in practice and what dependencies exist is not simple. One might imagine that adding concurrency would mean that more state is “observable” since a concurrent thread might observe changes that would otherwise be invisible between different points in sequential code. Suppose a second thread accesses “y” while “do a bunch of stuff” happens in the example above. Now moving the assignment to “y” changes the operation of the program because the second thread might see a different value. Reordering statements is much more dangerous in a multi-thread environment – like an operating system. In practice, statement reordering is not common in current compilers and, critically, the programmer can reorder statements in response to profile data if she wants and, hopefully, with some understanding of the threading semantics of her code. The C11 atomics are, in many ways an invitation to compiler developers to become more aggressive with reordering. The current attitude of WG14 appears to be that negative effects are just too bad, the programmer has absolutely no assurances about what the compiler will change in program order without using atomic operations. The code of Example6 is conformant without threads and undefined behavior with a data race if there is a second thread that accesses “y” so all bets are off. Even with the atomic operations things are not clear. If the program in example 6 used atomic operations to access “y” would the statement order be preserved? Maybe. That’s essentially the main topic of P1619R0. The net result is that it is essentially impossible to tell what C programs do in the presence of concurrent threads partly because the rules for what compilers can do to statement order are totally unclear. If this unclarity produced profound optimizations, there would be at least some grounds for accepting it, but there is no reason to believe that reordering statements by the compilers produce anything but micro-benchmark optimizations or optimizations of bad code. It is bizarre to read P1619R0, written in 2019, 8 years after C11 was published and to see a discussion of unanticipated interactions between atomic operations and undefined behavior.
Although I very much dislike the addition of atomics in C11, I am sympathetic to the argument that unstructured sharing of variables in a multi-thread environment is not a good methodology. However, creating yet more compiler introduced failures in production code that has already been designed to work with existing compilers is irresponsible.
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.
Categories
Pointer alias analysis in C
Perhaps there is some reason to provide a mechanism for asserting, in a particular patch of code, that the compiler is free to make optimistic assumptions about the kinds of aliasing that can occur. I don’t know any acceptable way of changing the language specification to express the possibility of this kind of optimization, and I don’t know how much performance improvement is likely to result. I would encourage compiler-writers to experiment with extensions, by #pragma or otherwise, to see what ideas and improvements they can come up with, but I am certain that nothing resembling the noalias proposal should be in the Standard. – Dennis Ritchie, 1988
From the beginning of the C standards process, the standards committee has wanted to break C pointer semantics in the cause of never quantified compiler optimizations. In C, pointers are memory addresses with types to permit both pointer arithmetic scaled to the size of the data type and checking for unintentional misapplication – such as assigning the result of dereferencing an integer pointer to a structure. Pointer aliasing (multiple pointers addressing the same or overlapping memory objects) and “type punning” (pointing to the same memory block with pointers of different types) are fundamental operations in C. For example, the C library sorting utility relies on converting pointers to an array of some type to pointer “void *” so it can sort arrays of abitrary type. Similarly the C library memory allocators return pointers of type “void *” that are generally converted to non-void typed pointers, e.g. “struct mystruct *m = malloc(sizeof(struct mystruct))”. In a sequence, “x = malloc(n); … free(x)… y = malloc(m) …” that same pointer value may be reused multiple times to point to objects of different type. The memory copy utility is passed “void *” pointers too, and then internally decides where it should copy byte by byte or using larger chunks of memory.
Compiler developers prefer to limit both pointer alias and type-punning. The “noalias” discussion was ostensibly driven by the difficulty of vectorizing code given overlapping pointers – an issue that has been considered in FORTRAN almost since the dawn of time. Essentially pointer-aliasing creates a classical consistency issue, like ones we have in distributed computing. Suppose we have code:
*x += *y; *(x+1) += *(y+1)
Given a two element vector load, store, and addition instructions, the compiler could potentially get this done in parallel: maybe
“load2 v,x” to load *x and *(x+1) into the vector register and “add2 v,y” for the addition of (*y,*(y+1)) and “store v x” would complete it. But maybe the bad programmer has an overlapping alias and x = y+1. If y points to [10,20,30] then the step-by step produces [10,30,20] and then [10,30,50] but the parallel operation produces [10,40,40]. This gets more depressing for large scale matrix operations – which is where it was first encountered in FORTRAN. So compiler writers would like to have unaliased pointers, but in C, aliased pointers are very useful. To move all the elements of a string left by one place is a simple application: “b = c+1; while( (*c++ = *b++))”. Another obvious example is computing a checksum for a packet. Instead of worrying about the possibly complex structure of the packet, the programmer might want to think of it as a sequence of 64bit unsigned ints and just xor them, but this requires pointers to overlapping memory object that don’t have the same type. So these kinds of pointer operations are useful and customary in C code and, to make it more peculiar, the claimed optimizations are of such marginal utility and so dangerous that the Linux project specifically disables them (fno-strictalias).
If the only reason is to permit compilers to use vector instructions in loops, it seems like a simple opt-in could be used. C restrict is a solution, even though the standard description of it is terrible. The only other substantive optimization found in examples is where the compiler can substitute “memcpy” (which assumes non-overlapping pointers) for a loop, but surely that’s something the programmer should do where it’s an advantage. Maybe there are other reasons for wanting unaliased pointers (the examples in Regehr’s post are not all that compelling) and someone can tell me about them.
The compiler developers and standards authors, however, don’t want to leave it to the programmers. Instead they have made use of a loophole created in C99 which can be read as permitting compilers to do anything at all in the presence of “undefined behavior” and another change to the C standard that allows pointer casting and aliasing to be treated as undefined behavior.
Anyone who thinks the C Standard has a clear or even excusable model of type-punning and pointer alias could read this horrifying discussion which ends with the understatement “The conclusion for the de facto semantics here is not completely clear. ” ( via @comex in twitter) or look at John Regehr’s authoritative post with the even more understated title:
The Strict Aliasing Situation is Pretty Bad
And now, we can see that the standards committee is attempting to go way beyond these to make pointer rules even more opaque.
See this for a more optimistic take.
From the LLVM developer mailing list this remarkable exchange in which Chris Lattner of LLVM says that the compiler use of undefined behavior (UB) is so “crappy” that the only solution is to abandon C programming (my bold).
On Jul 7, 2017, at 1:40 PM, Peter Lawrence <peterl95124 at sbcglobal.net> wrote: > Chris, > The issue the original poster brought up is that instead of a compiler > that as you say “makes things work” and “gets the job done” we have a compiler > that intentionally deletes “undefined behavior”, on the assumption that since it > is the users responsibility to avoid UB this code must be unreachable and > is therefore safe to delete. > > It seems like there are three things the compiler could do with undefined behavior > 1) let the code go through (perhaps with a warning) > 2) replace the code with a trap > 3) optimize the code as unreachable (no warning because we’re assuming this is the users intention) Hi Peter, I think you have a somewhat fundamental misunderstanding of how UB works (or rather, why it is so crappy and doesn’t really work :-). The compiler can and does do all three of those, and it doesn’t have to have consistent algorithms for how it picks. I highly recommend you read some blog posts I wrote about it years ago, starting with: http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html John Regehr also has written a lot on the topic, including the recent post: https://blog.regehr.org/archives/1520 What you should take from this is that while UB is an inseperable part of C programming, that this is a depressing and faintly terrifying thing. The tooling built around the C family of languages helps make the situation “less bad”, but it is still pretty bad. The only solution is to move to new programming languages that don’t inherit the problem of C. I’m a fan of Swift, but there are others. In the case of this particular thread, we aren’t trying to fix UB, we’re trying to switch one very specific syntactic idiom from UB to defined. -Chris
When Lattner writes “The compiler can and does do all three of those, and it doesn’t have to have consistent algorithms for how it picks” the key terms are “can” and “doesn’t have to”. The C standard may permit “depressing and … terrifying” operations in a compiler but there is no requirement for compilers to make UB into a minefield for programmers. The compiler writers have seized onto what is essentially a loophole in the standard as permission to do stupid things and call them optimizations. It seems only reasonable to hope that WG14-C would consider that their standard is used by compiler writers to justify deprecating use of the language, but maybe they don’t care either. The other interesting fact I learned from this exchange is that it is impossible to write conforming C implementations of “malloc” and “free”. Why? Because once “free” returns, any access to the pointer is UB, so malloc cannot allocate the same memory again.
The Kafkaesque interaction of the C standard and the main open source C compilers was concisely outlined by one of the main LLVM authors back in 2011:
“knowing that
INT_MAX+1is undefined allows optimizingX+1 > Xto “true”. Knowing the multiplication “cannot” overflow (because doing so would be undefined) allows optimizingX*2/2to X ( Chris Lattner)
The C standard defines signed integer types to be fixed length chunks of binary data in either 1s or 2s complement format so x+1 > x is not a theorem and neither is x*2/2= x. Those are elementary mathematical facts – facts that make some kinds of optimizations harder. Instead of trying to work with that reality, C compiler developers have chosen to use a loophole in the C Standard to insist that they can transform code using false theorems. Both the default versions of the GCC and clang compilers that come with current Ubuntu Linux compile the following program so that it works differently depending on optimizations level.
for (i = 0; i < i + 1; i++) {
if (i == INT_MAX) { flag = 1; }
if (flag > 0) {printf("%d |", i);flag++; }
if (flag > 5) { putchar('\n'); exit(0);}
}
exit(0);When compiled without optimization, there is no output. When compiled with optimization output is:
2147483647 |-2147483648 |-2147483647 |-2147483646 |-2147483645 |
Deducing that i < i + 1 is always true, the “optimizer” omits the test and then produces code that calculates it was wrong. The compiler is deducing that it won’t produce the executable code that the compiler produces! Nice. According to the C standard, correct code would have used unsigned integers for the comparison because integer overflow is “undefined behavior” even though using signed integers infor loops is ubiquitous in C programming. The curious thing here is that the compilers don’t warn, complain or reject the signed comparison, instead they generate a paradoxical executable that refutes itself. The program could run correctly for years until someone turns on the optimizer and finds paradoxical results. Similar compiler innovations have produced all sorts of failures in working code including security failures. This stupid technology is constructed from the interaction of two reasonable projects that went wrong and then amplified each others difficulties. One project is the C standard committee tightening up C’s loose semantics. The other project is an effort to import new optimization methods into the C compilers. The flaws in each project have resonated with each other. In this case, different processor architectures (or processing modes) will produce different behavior when signed words overflow and C is designed to allow use of native arithmetic close to the machine level for utmost efficiency. But instead of finding ways to make signed integer overflow alternatives precise, the standards committee tossed signed overflow into special category of things labeled “undefined behavior” which is different from “indeterminate” or not specified in that undefined behavior makes C code “non-conforming” and “this International Standard imposes no requirements” for undefined behavior. Then, in a ghastly miscalculation, compiler developers interpreted “imposes no requirements” as a license to produce incorrect code and call it optimization. The standard imposes no requirements and it is convenient to assume there will not be overflows, so QED we can conclude that FALSE is TRUE. In fact, the position seems to be that if the compiler produces code that encrypts all your files, mails the password to Moldavia, and prints a cryptic message about end times, it’s all good. No requirements means no requirements and you should have declared those variables unsigned. This is no exaggeration. Discussing the undefined behavior of shift operations Lattner writes: ” shifting by 32-bits on PowerPC could format your hard drive, it is not guaranteed to produce zero.”
The unsound logic of the compilers has drawn complaints for decades: from the most prominent author of cryptography code ( DJB ), former members of the C standards committee ( Derek Jones), groups of researchers and academics (Regehr) and many C programmers (this one is like horror movie about an engineer trapped in a department of motor vehicles office). As Derek Jones observed, the main C compiler groups don’t sell software to application developers, so they don’t have to care. And the compiler developers don’t have anyone who can do what Linus Torvalds did for Linux so many times: politely and humbly reject innovations that break applications without compelling justification. Even worse, the standards committee and compiler developers split responsibility – so they can and do blame each other. The example cited by DJB is truly horrendous and is based on the standards edict that dereferencing a null pointer is undefined behavior (even though it’s widely used in embedded code and in some UNIX distributions).
- The code erroneously, but harmlessly in this case, dereferences a pointer before checking whether the pointer is null.
- The compiler considers two possibilities: either the pointer is not null, in which case the null check that follows is redundant, or the pointer is null in which case undefined behavior has been detected.
- The compiler “optimizes” by removing the null check (silently). Note that the code deleted is not “undefined behavior” code, it just follows the offending null pointer dereference so all rules are off.
- A security breach is discovered as someone exploited the failure of the code to check for null pointers.
All programming languages have some places where they run into machine or architecture or resource dependencies. If you take the most over-the-top mathematically pretentious highest level programming language and write code to compute factorial, a fairly small input will cause the program run out of time or memory and produce some error. Because C is so close to the machine, it bumps into hardware a lot. Pointers are machine addresses – just numbers, shift operations are specified to compile down to single machine instructions, and arithmetic is so close to the hardware that number representation schemes are programmer visible. As another example, C structures may contain “padding” bytes added by the compiler to accommodate processor alignment requirements. A structure struct x{ char c; int i;}; could have 3 bytes of padding inserted after the 1 byte character so that the integer is on a 4 byte boundary. For efficiency, padding bytes are generally uninitialized – not set to any particular value – so copying the structure may involve copying uninitialized data. The C90 standard declared that reading uninitialized bytes was undefined behavior. The unintentional consequence was that it became impossible to write the C library in conforming C because copying a structure in the memcpy routine might involve copying (reading and writing) uninitialized data. The standards committee “solved” the problem with a dismally giant hack by making unsigned characters specially immune from undefined behavior. If you copy indeterminate bytes via unsigned character pointers, that’s ok, but otherwise it’s undefined behavior. Here’s Chris Lattner explaining a small part of the resulting mess:
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). – Chris Lattner
To anyone who has ever managed a programming project, the signs of a fatally broken design decision are unmistakable (a cascade of special cases is never good). Nuance is nice in poetry, not in engineering. But the C standards committee was not piling whole categories of C code into the undefined behavior basket for no reason. They were trying to deal with two different types of pressure. The first is that the definition of C had too many holes in it so that C code was often way too machine or compiler dependent or just sloppy. The second problem was that C is resistant to a number of useful types of optimization and compiler developers pushed for changes that would allow them to assume things about code that made certain optimizations more widely applicable. It seems like the idea was that by ruling certain types of constructions to be “non-conforming”, the standard would discourage their use and make the language more consistent and more suited to modern optimization methods. As an example, certain widely used crypto code apparently uses uninitialized variables to inject randomness into low level encryption code – relying on the variable to be allocated from the leftover garbage on the stack. That code will fail dismally if stack allocation changes or automatic variables are not allocated from the stack (or the previously called process filled the stack with something predictable). So warning about that code or even refusing to compile it might improve applications, but because of the nice split in responsibilities, the Standards body can rule such code non-conforming and look away as the compiler writers then perform arbitrary transformations on that code.
And all of this is so unnecessary. As Jones points out, some sort of undefined behavior is intrinsic to C, but implementations are not required to treat it as an excuse for sabotaging programs:
A willingness to accept whatever behavior happens to occur, in an error situation, is the price that has to be paid for efficient execution on a wide range of disparate processors. The C/C++ designers were willing to pay this price while the Java designers were not, with the Ada designers willing to tolerate less variability than C/C++.
Undefined behavior need not be nasty behavior, an implementation could choose to generate a helpful message or try to recover from it.
Changes to the C standard could be used to make it more optimizable. C would definitely benefit from increased use of “restricted pointers” (the definitions needs to be clarified but it’s a great step forward.) And the gcc “pure” modifier on function types is interesting and should be considered for the standard. The standard could promote methods of writing verifiable, optimizable code as opt-in. An additional easy step would be to move things like reading uninitialized data from “undefined” to “indeterminate” and make pointer casting well-defined whenever alignment and object size are compatible. The Committee could also modify the definition of undefined behavior by specifically limiting the freedom of conforming implementations. Replacing “this International Standard imposes no requirements” with “conforming implementations may reject non-conforming constructs or implement in a consistent implementation dependent manner.” C already provides machine dependent information to the programmer. The file limits.h tells the programmer about the native word sizes and number ranges on the target computer. There is no reason why that cannot be extended to specify signed integer overflow behavior (and in 99.999% of cases that behavior is rollover). The language has intrinsic access to nonportable machine dependent and/or implementation dependent information. Pretending otherwise only creates too much – well – nuance. Underlying all of this, it’s easy to get the feeling that the C standards process and C compiler development has lost the plot – that the objective has become a doomed effort to recreate C as a kind of low grade patched up Ada or (forgive me) Rust. Consider this note on uninitialized data from Lattner
Use of an uninitialized variable: This is commonly known as source of problems in C programs and there are many tools to catch these: from compiler warnings to static and dynamic analyzers. This improves performance by not requiring that all variables be zero initialized when they come into scope (as Java does). For most scalar variables, this would cause little overhead, but stack arrays and malloc’d memory would incur a memset of the storage, which could be quite costly, particularly since the storage is usually completely overwritten.
But the alternatives are not only to either impose mandatory initialization of variables or to allow the compiler to treat use of uninitialized memory as permission to arbitrarily rewrite code. Where compilers and tools can warn about use of uninitialized variables – that’s good. Where they cannot, it should be up to the programmer. The intent of C is to give the programmer enormous flexibility. C developers are not supposed to need to escape the language and invoke pragmas or “unsafe” keywords (or call out to libraries written in some scorned low level language). The Linux networking code (lib/checksum) below shows off one of the compelling things about C – the ability to work directly with memory and control the mapping from bit patterns to denotations. The code is computing a checksum for a network packet. Starting with the packet data structure it first looks at it as a sequences of unsigned characters and then does a type coercion to map sequences of 4 unsigned characters into “int” types so it can run through and compute the checksum.
do {
unsigned int w = *(unsigned int *) buff;
buff += 4; result += carry;
result += w;
carry = (w > result); }
while (buff < end);
result += carry;
result = (result & 0xffff) + (result >> 16);This type of code makes it easy to screw up and can complicate optimization for compilers and everything for static analyzers (changes in type, aliased pointers, demonical possession … ) but it’s the essence of systems programming and a lot of application programming too. It’s what C was designed to do and for expert C programmers gives C programming a flexible and fluid character. Is this code legal C under the current C standard? It appears not. But if the standard requires the mother of all hacks to make memcpy implementation conform to spec (and not a real one either, it actually seems to force C compilers to use escape to assembler) it’s going to trip up C. And if the implementations are going to claim that unsound deduction is a legitimate optimization then C is really doomed.
Bonus – from the C89 standard.
A pointer to an object or incomplete type may be converted to a pointer to a different object type or a different incomplete type. The resulting pointer might not be valid if it is improperly aligned for the type pointed to. It is guaranteed, however, that a pointer to an object of a given alignment may be converted to a pointer to an object of the same alignment or a less strict alignment and back again; the result shall compare equal to the original pointer.
rough notes for this are at https://www.yodaiken.com/2017/06/16/the-c-standard-committee-effort-to-kill-c-continues/