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
Category: C standard
Categories
C23 standard (final draft)
Categories
don’t defer
There is a proposal to add “defer” to C. Its biggest example is taken from code that was originally designed to not manage storage at all, but to run once and exit – delegating all the cleanup to exit. The proposal authors show a complex solution to make the code free storage and then show how it can be “simplified” using defer. But it is trivial to centralize cleanup in one function, no new features needed. If I was developing this code for real, I’d take the next step and make it single exit. Here is is with a simple function to free all storage on exit.
struct plugins {
char *pluginsdir;
char *outpluginsdirphp;
char *outpluginsdirmisc;
char *dirpath;
char *outdirphp;
char *outdirmisc;
int n;
struct dirent **namelist;
};
void freeall(struct plugins *x)
{
if (x->pluginsdir)
free(x->pluginsdir);
if (x->outpluginsdirphp)
free(x->outpluginsdirphp);
if (x->outpluginsdirmisc)
free(x->outpluginsdirmisc);
if (x->dirpath)
free(x->dirpath);
if (x->outdirphp)
free(x->outdirphp);
if (x->outdirmisc)
free(x->outdirmisc);
for (int i = 0; i < x->n; i++) {
free(x->namelist[i]);
}
}
h_err *h_build_plugins(const char *rootdir, h_build_outfiles outfiles,
const h_conf * conf)
{
struct plugins x = { 0, };
x.pluginsdir = h_util_path_join(rootdir, H_FILE_PLUGINS);
if (pluginsdir == NULL)
return h_err_create(H_ERR_ALLOC, NULL);
x.outpluginsdirphp = h_util_path_join(rootdir,
H_FILE_OUTPUT "/" H_FILE_OUT_META
"/" H_FILE_OUT_PHP);
if (outpluginsdirphp == NULL) {
freeall(&x);
return h_err_create(H_ERR_ALLOC, NULL);
}
x.outpluginsdirmisc = h_util_path_join(rootdir,
H_FILE_OUTPUT "/" H_FILE_OUT_META
"/" H_FILE_OUT_MISC);
if (x.outpluginsdirmisc == NULL) {
freeall(&x);
return h_err_create(H_ERR_ALLOC, NULL);
}
//Check status of rootdir/plugins, returning if it doesn’t exist
{
int err = h_util_file_err(x.pluginsdir);
if (err == ENOENT) {
freeall(&x);
return NULL;
}
if (err && err != EEXIST) {
freeall(&x);
return h_err_from_errno(err, x.pluginsdir);
}
}
//Create dirs if they don’t exist
if (mkdir(x.outpluginsdirphp, 0777) == -1 && errno != EEXIST) {
freeall(&x);
return h_err_from_errno(errno, x.outpluginsdirphp);
}
if (mkdir(outpluginsdirmisc, 0777) == -1 && errno != EEXIST) {
freeall(&x);
return h_err_from_errno(errno, outpluginsdirmisc);
}
//Loop through plugins, building them
x.n = scandir(x.pluginsdir, &x.namelist, NULL, alphasort);
if (n == -1) {
freeall(&x);
return h_err_from_errno(errno, x.namelist);
}
for (int i = 0; i < n; ++i) {
struct dirent *ent = namelist[i];
if (ent->d_name[0] == '.') {
continue;
}
x.dirpath = h_util_path_join(x.pluginsdir, ent->d_name);
if (dirpath == NULL) {
freeall(&x);
return h_err_create(H_ERR_ALLOC, NULL);
}
x.outdirphp = h_util_path_join(outpluginsdirphp, ent->d_name);
if (x.outdirphp == NULL) {
freeall(&x);
return h_err_create(H_ERR_ALLOC, NULL);
}
x.outdirmisc =
h_util_path_join(x.outpluginsdirmisc, ent->d_name);
if (x.outdirmisc == NULL) {
freeall(&x);
return h_err_create(H_ERR_ALLOC, NULL);
}
h_err *err;
err =
build_plugin(dirpath, outdirphp, outdirmisc, outfiles,
conf);
if (err) {
freeall(&x);
return err;
}
}
freeall(&x);
return NULL;
}
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.
Categories
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
\
\ /
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.
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:
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
restrictkeyword 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
mallocimplementation 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 newlymalloced 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
ifstatement), 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.
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:
- 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.
- 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.
- 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
PermissiblePossible 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.
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.
This 1998 note by Dennis Ritchie from comp.lang.c (and also here ) is very current since the concept of noalias has definitely crept back into the standard. I have reproduced it verbatim, but lightly formatted for readability. For further reading try Linus Torvalds (pre-nice ) note, John Regehr’s paper on alias and this proposal for the C 2x standard.
noalias comments to X3J11
d…@alice.uucp
Mar 20, 1988, 2:37:58 AM
Reproduced below is the long essay I sent as an official comment to X3J11. It is in two parts; the first points out some problems in the current definition of `const,’ and the second is a diatribe about `noalias.’ By way of introduction, the important thing about `const’ is that the current wording says, in section 3.3.4, that a pointer to a const-qualified object may be cast to a pointer to the plain object, but “If an attempt is made to modify the pointed-to object by means of the converted pointer, the behavior is undefined.” Because function prototypes tend to convert your pointers to const-qualified pointers, difficulties arise.In discussion with various X3J11 members, I learned that this section is now regarded as an inadvertant error, and no one thinks that it will last in its current form. Nevertheless, it seemed wisest to keep my comments in their original strong form. The intentions of the committee are irrelevant; only their document matters.
The second part of the essay is about noalias as such. It seems likely that even the intentions of the committee on this subject are confused.
Here’s the jeremiad.
Dennis Ritchie
research!dmr
d…@research.att.com
———-
This is an essay on why I do not like X3J11 type qualifiers. It is my own opinion; I am not speaking for AT&T.
Let me begin by saying that I’m not convinced that even the pre-December qualifiers (`const’ and `volatile’) carry their weight; I suspect that what they add to the cost of learning and using the language is not repaid in greater expressiveness. `Volatile,’ in particular, is a frill for esoteric applications, and much better expressed by other means. Its chief virtue is that nearly everyone can forget about it. `Const’ is simultaneously more useful and more obtrusive; you can’t avoid learning about it, because of its presence in the library interface. Nevertheless, I don’t argue for the extirpation of qualifiers, if only because it is too late.
The fundamental problem is that it is not possible to write real programs using the X3J11 definition of C. The committee has created an unreal language that no one can or will actually use. While the problems of `const’ may owe to careless drafting of the specification, `noalias’ is an altogether mistaken notion, and must not survive.
1. The qualifiers create an inconsistent language
A substantial fraction of the library cannot be expressed in the proposed language.
One of the simplest routines,
char *strchr(const noalias char *s, int c);
can return its first parameter. This first parameter must be declared with `const noalias;’ otherwise, it would be illegal (by the constraints on assignment, 3.3.16.1) to pass the address of a const or noalias object. That is, the type qualifiers in the prototype are not merely an optional pleasantry of the interface; they are required, if one is to pass some kinds of data to this or most other library routines.
Unfortunately, there is no way in X3J11’s language for strchr to return the value it promises to, because of the semantics of return (3.6.6.4) and casts (3.3.4). Whether the stripping of the const and noalias qualifiers is done by cast inside strchr, or implicitly by its return statement, strchr returns a pointer that (because of `const’) cannot be stored through, and (because of `noalias’) cannot even be dereferenced; by the rules, it is useless. (Incidentally, I think this observation was made by Tom Plum several years ago; it’s disconcerting that the inconsistency remains.)
Although the plain words of the Standard deny it, plastering the appropriate `non-const’ cast on an expression to silence a compiler is sometimes safe, because the most probable implementation of `const’ objects will allow them to be read through any access path, and will diagnose attempts to change them by generating an access violation fault at run time. That is, in common implementations, adding or taking away the `const’ qualifier of a pointer can never create any bugs not implicit in the rule `do not modify a genuine const object through any access path.’
Nevertheless, I must emphasize that this is NOT the rule that X3J11 has written, and that its library is inconsistent with its language. Someone writing an interpreter
using X3J11/88-001 is perfectly at liberty to (indeed, is advised to) carry with each pointer a `modifiable’ bit, that (following 3.3.4) remains off when a pointer to a const-
qualified object is cast into a plain pointer. This implementation will prevent many of the real uses of strchr, for example. I’m thinking of things like
if (p = strchr(q, ‘/’))
*p = ‘ ‘;
which are common and innocuous in C, but undefined by X3J11’s language.
A related observation is that string literals are not of type `array of const char.’ Indeed, the Rationale (88-004 version) says, `However, string literals do not have [this type], in order to avoid the problems of pointer type checking, particularly with library functions….’ Should this bald statement be considered anything other than an admission that X3J11’s rules are screwy? It is ludicrous that the committee introduces the `const’ qualifier, and also makes strings unwritable, yet is unable to connect the two conceptions.
2. Noalias is an abomination
`Noalias’ is much more dangerous; the committee is planting timebombs that are sure to explode in people’s faces. Assigning an ordinary pointer to a pointer to a `noalias’ object is a license for the compiler to undertake aggressive optimizations that are completely legal by the committee’s rules, but make hash of apparently safe programs. Again, the problem is most visible in the library; parameters declared `noalias type *’ are especially problematical.
In order to write such a library routine using the new parameter declarations, it is in practice necessary to violate 3.3.4: `A pointer to a noalias-qualified type … may be converted to … the non-noalias-qualified type. If the pointed to object is referred to by means of the converted pointer, the behavior is undefined.’ Thus, the problem that occurs with `const’ is now much worse; there are no interesting and legal uses of strchr.
How do you code a routine whose prototype specifies a noalias pointer? If you fail to violate 3.3.4, but instead try to rewrite the declarations of temporary variables to make them agree in type with parameters, it becomes hard to be sure that the routine works. Consider the specification of strtok:
char *strtok(noalias char *s1, noalias const char *s2);
It retains a static pointer to its writable, `noalias’ first argument. Can you be sure that this routine can be made safe under the rules? I have studied it, and the answer is conditionally yes, provided one accepts certain parts of the
Standard as gospel (for example that `noalias’ handles will
NOT be synchronized at certain times) while ignoring other parts. It is a very dodgy thing. For other routines, it is certain that complete rewriting is necessary: qsort, for example, is full of pointers that rove the argument array and change it here and there. If these local pointers are qualified with `noalias,’ they may all be pointing to different virtual copies of parts of the array; in any event, the argument itself may have a virtual object that might be completely untouched by the attempt to sort it.
The `noalias’ rules have the assignment and cast restrictions backwards. Assigning a plain pointer to a const- qualified pointer (pc = p) is well-defined by the rules and is safe, in that it restricts what you can do with pc. The other way around (p = pc) is forbidden, presumably because it creates a writable access path to an unwritable object. With `noalias,’ the rules are the same (pna = p is OK, p = pna is forbidden), but the realistic safety requirements are completely different. Both of these assignments are equally suspicious, in that both create two access paths to an object, one manifestation of which might be virtual.
Here is another way of observing the asymmetry: the presence of `const type *’ in a parameter list is a useful piece of interface information, but `noalias type *’ most assuredly is not. Given the declaration
memcpy(noalias void *s1, const noalias void *s2, size_t n);
what information can one glean from it? Some committee members apparently believe that it conveys either to the reader or to the compiler that the routine is safe, provided that the strings do not overlap. They are mistaken. Perhaps the committee’s intent is not reflected in the current words of the Standard, but I can find nothing there that justifies their belief. The rules (page 65, lines 19-20) specify `all objects accessible by these [noalias] lvalues,’ which is the entirety of both array arguments.
More generally, suppose I see a prototype
char *magicfunction(noalias char *, noalias char *);
Is there anything at all I can conclude about the requirements of magic function? Is there anything at all I can conclude about things it promises to do or not to do? All I learn from the Rationale (page 52) is that such a routine enjoins me from letting the arguments overlap, but this is at variance with the Standard, which gives a stronger injunction.
Within the function itself, things are equally bad. A `const type *’ parameter, though it presents problems for strchr and other routines, does usefully constrain the function: it’s not allowed to store through the pointer. However, within a function with a `noalias type *’ parameter, nothing is gained except bizarre restrictions: it can’t cast the parameter to a plain pointer, and it can’t assign the parameter to another noalias pointer without creating unwanted handles and potential virtual objects. The interface MUST say noalias, or at any rate DOES say noalias, so the author of the routine has all the grotesque inventions of 3.5.3 (handles, virtual objects) rubbed in his face, like or not. The utter wrongness of `noalias’ is that the information it seeks to convey is not a property of an object at all. `Const,’ for all its technical faults, is at least a genuine property of objects; `noalias’ is not, and the committee’s confused attempt to improve optimization by pinning a new qualifier on objects spoils the language. `Noalias’ is a bogus invention that is not necessary, and not in any case sufficient for its apparent purpose.
Earlier languages flirted with gizmos intended to help optimization, and generally abandoned them. The original Fortran, for example, had a FREQUENCY statement that didn’t help much, confused people, and was dropped. PL/1 had
`normal/abnormal’ and `uses/sets’ attributes that suffered a similar fate. Today, these are generally looked on as adolescent experiments.
On the other hand, the insufficiency of `noalias’ is suggested by Cray’s Fortran compiler, which has 20 separate keywords that control various details of optimization. The are specified by an equivalent of #pragma, and thus, despite their oddness, can be ignored when trying to understand the meaning of a program. 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.
3. The cost of inconsistency
K&R C has one important internal contradiction (variadic functions are forbidden, yet printf exists) and
one important divergence between rule and reality (common vs. ref/def external data definitions). These contradictions have been an embarrassment to me throughout the years, and resolving them was high on X3J11’s agenda. X3J11 did manage to come up with an adequate, if awkward, solution to the first problem. Their solution to the second was the same as mine (make a rule, then issue a blanket license to violate it).
I’m aware that there are distinctions to be made between `conforming’ and `strictly conforming’ programs. Although the X3J11 rules for qualifiers are inconsistent, and therefore most nominally X3J11 compilers will ignore, or
only warn about, casts and assignments that X3J11 says are undefined, people will somehow survive. C has, after all, survived the vararg and the extern problems.
Nevertheless, I advise strongly against sanctifying a language specification that no one can possibly embody in a useful compiler. This advice is based on bitter experience.
4. What to do?
Noalias must go. This is non-negotiable.
It must not be reworded, reformulated or reinvented. The draft’s description is badly flawed, but that is not the problem. The concept is wrong from start to finish. It negates every brave promise X3J11 ever made about codifying existing practices, preserving the existing body of code, and keeping (dare I say it?) `the spirit of C.’
Const has two virtues: putting things in read-only memory, and expressing interface restrictions. For example, saying
char *strchr(const char *s, int c);
is a reasonable way of expressing that the routine cannot change the object referred to by its first argument. I think that minor changes in wording preserve the virtues, yet eliminate the contradictions in the current scheme.
1) Reword page 47, lines 3-5 of 3.3.4 (Cast operators), to remove the undefinedness of modifying pointed-to objects, or remove these lines altogether (since casting non-qualified to qualified isn’t discussed explicitly either.)
2) Rewrite the constraint on page 54, lines 14-15, to say that pointers may be assigned without taking qualifiers into account.
3) Preserve all current constraints against modifying non-modifiable lvalues, that is things of manifestlyconst-qualified type.
4) String literals have type `const char []’.
5) Add a constraint (or discussion or example) to assignment that makes clear the illegality of assigning to an object whose actual type is const-qualified, no matter what access path is used. There is a manifest constraint that is easy to check (left side is not const-
qualified), but also a non-checkable constraint (left side is not secretly const-qualified). The effect should be that converting between pointers to const- qualified and plain objects is legal and well-defined; avoiding assignment through pointers that derive ultimately from `const’ objects is the programmer’s responsibility.
These rules give up a certain amount of checking, but they save the consistency of the language.