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;
}
A trivial theorem, more of a tautology, on networking and Turing’s deep theorem on decidability are both widely cited, widely misunderstood and widely misapplied in computer science. It is often claimed that Fischer, Lynch, Patterson (FLP) “theorem” on networks shows that we cannot reliably detect failure on a packet network and that Turing showed that no program exists that can always detect whether an arbitrary program will halt. Neither of those claims are true in computer programming. FLP applies only to “asynchronous networks” where there are no timeouts and where there are no probabilities to lean on so failures are not distinguishable from delays. These types of networks are rare. Turing’s result applies to abstract “programs” with unbounded memory and unbounded compute time, not to real programs that run on real computers. In both cases, people in computer science make the same error of conflating a precise definition of a term in a theorem with an informal definition used in engineering practice and this error leads to significant misunderstanding of how systems work.
There’s a good example of misuse of the FLP theorem in an ACM Queue article:
Perfect failure detectors are impossible to implement in a distributed system,9,15 in which it is impossible to distinguish between delay and failure. [ACM Queue]
The citation 15 above is to the FLP paper. In actual engineering systems, delay of over a certain duration is failure. This is easy to see in extreme: in the FLP model network nodes cannot distinguish between a peer that has not answered a query in 1 millisecond and a peer that has been silent for 10 years because the model excludes clocks of any kind. Is that a realistic model of a computer network? Consider a distributed consensus system in which the client cannot get responses from the coordinator. Normally, we can provide each device with a timer and have them enter a recovery mode if they don’t receive a response over a period chosen to meet the characteristics of the network and the requirements of the application. If a node does not receive a communication from the coordinator over the timeout period, it may be that the coordinator has crashed, or that there is a network problem, or that the coordinator is busy watching Sanctuary Moon and can’t be bothered to reply yet – in any of those cases, the important property is that the coordinator is not coordinating and a new one needs to be elected. Protocols for safe election of a new coordinator have been developed many times over the last 50 years or so – it is no mystery. Of course, like any engineered object, such a system is subject to failure when assumptions about probability or network properties are violated. We generally assume that spurious packets are not delivered and packets that have been corrupted in transit are detected, and that all participants follow the protocol (no Byzantine failure) and that Brownian motion doesn’t rip the network apart and deposit nodes into other networks, and that the power stays on etc. But none of these possibilities means we cannot have deterministically correct systems modulo reasonable assumptions.
In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist. […] Turing proved no algorithm exists that always correctly decides whether, for a given arbitrary program and input, the program halts when run with that input.
The link to the Wikipedia definition of “computer program” is what transforms this page from sloppy to wrong.
Turing machines are not either computers or computer programs under these definitions, so Turing’s theorem says nothing about the decision problem for computer programs. In fact, since computer programs executing on digital electronic devices correspond to finite state machines, the decision problem is trivial in terms of Turing machines. We can provide an actual computer program as an input to a Turing machine and have the Turing machine simulate execution until either a state repeats (which means the program would loop forever) or it terminates. Just because you call computer programs, programs, and can call Turing machine codes “programs” doesn’t mean they are the same things or that a theorem about one class of things applies to the other class of things.
There are several common, but incorrect rejoinders to this observation and one of them is on the Wikipedia page under a section titled “Common Pitfalls”. In this section it is noted that that finite state programs may have a lot of states so, in practice, it might be difficult to determine if they halt or otherwise verify system properties. Quoting Marvin Minsky:
…the magnitudes involved should lead one to suspect that theorems and arguments based chiefly on the mere finiteness [of] the state diagram may not carry a great deal of significance.
This exactly why one uses mathematics instead of hand waving. The “mere finiteness” of the state diagram is actually pretty important. A theorem that says no Turing Machine can solve the halting problem for all other Turing machines says absolutely nothing about how hard it is to validate large finite state machines. Big numbers are not unbounded numbers. In fact, Turing’s result does not even mean that some Turing machine could not, with very high probability, solve the halting program for a randomly chosen Turing machine. The undecidability of the halting problem for Turing machines has zero significance for engineering and, as Kurt Godel pointed out, not as much as it might initially appear for mathematics. There is a parallel Wikipedia page on decision problemwhich seems to be written more by mathematicians than computer scientists and it doesn’t make the same error but does discuss a number of computer programs that manage to work with very large numbers of states to solve real problems in mathematics and software engineering.
Practical decision procedures
Having practical decision procedures for classes of logical formulas is of considerable interest for program verification and circuit verification. Pure Boolean logical formulas are usually decided using SAT-solving techniques based on the DPLL algorithm. Conjunctive formulas over linear real or rational arithmetic can be decided using the simplex algorithm, formulas in linear integer arithmetic (Presburger arithmetic) can be decided using Cooper’s algorithm or William Pugh’s Omega test. Formulas with negations, conjunctions and disjunctions combine the difficulties of satisfiability testing with that of decision of conjunctions; they are generally decided nowadays using SMT-solving techniques, which combine SAT-solving with decision procedures for conjunctions and propagation techniques. Real polynomial arithmetic, also known as the theory of real closed fields, is decidable; this is the Tarski–Seidenberg theorem, which has been implemented in computers by using the cylindrical algebraic decomposition.
It turns out that in many important cases, it is possible to have one computer program evaluate another one or a mathematical theorem and tell us whether it is true or not. This is a hard problem, but not an impossible one. Mathematical results, even in computer science have meanings determined by the precise definitions of terms used in the theorems – they are not general statements about the world or metaphorical.
Here’s a program that exhibits the low level nature of C by changing the return address of a function. The function “one” always returns the number 1 and the function “two” always returns the number 2. The main code calls “one” and prints out that it returned 1, then calls “two” and then changes its mind and tells us that “one” returned returned 2. The trick is that that the return address for “two” is modified so it returns as if it had been called from the statement that calls “one”.
This program is a good way to learn some machine architecture and also helps with understanding core operating systems code and computer virus coding, but my main excuse is that it is fun. The expressions marked in red are what make the trick work (although the color doesn’t matter -) ). The first version is for X86-64 and the second version is for Arm64 (and your Apple notebook).
/* Irresponsible C Code (c) Victor Yodaiken 2022/2026
Tested on AMD Ryzen 5 and compiled with zero optimization
gcc (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0.
tcc version 0.9.27 (x86_64 Linux)
Ubuntu clang version 18.1.3 (1ubuntu1) x8664
*/
#ifdef GCC // compile with gcc -DGCC
#define OFFSET 3
#else
#define OFFSET 2
#endif
#include
int one(void);
int two(void);
void *y = 0; //eventually holds the return address of "one"
int main()
{
int i;
if ((i= one()) == 1) {
printf("one returns 1\n");
two();
printf("The program never gets here\n");
} else printf("one returns %d\n",i);
return 0;
}
int one(void)
{
char **x = (char **)(&x + OFFSET);
y = *x;
return 1; //always returns 1
}
int two(void)
{
char **x = (char **)(&x + OFFSET);
*x = y;
return 2;
}
This code works on current generations of tcc, clang, and gcc (as long as you adjust the stack pointer offset and do not, under any circumstances run the optimizer). If you compile with GCC you have to define the compile time constant GCC, for example by typing the command “gcc X8664.c -DGCC”. The expression “&x+ OFFSET” calculated the address of the stack location that holds the return address. On X86, the call subroutine instruction pushes the address of the next instruction onto the stack and then jumps to the subroutine. This code exploits the C compiler allocating space for the variable “x” on the stack, takes that address and looks further up the stack to find the return address. When I was writing this code, I figured out the pointer arithmetic and where to find the return address on the stack by experiment with code something like:
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.
Milner’s Communication and Concurrency contrasts a notion of “bisimulation” with what he characterizes as the view in standard automata theory. Standard automata theory, however, has a much more interesting and well defined notion of both equivalence and concurrency than what is presented in the process algebra literature. In fact, the absence of any reference to automata products, covering, machine homomorphism, minimization, conversion of NFAs to DFAs, and to Mealy and Moore machines is striking.
PAXOS – (c) Victor Yodaiken, 2022
These are the lecture notes, or see the paper.
1. Really clever distributed consensus algorithm by Leslie Lamport
A. Infamously hard to understand - but not complicated
B. Livelocks - can get stuck without reaching consensus
C. Highly patented
D. Widely used - supposedly.
2. Original paper: The Part Time Parliament, 1990
Most annoying CS paper ever published.
3. Paxos Made Simple, 2001.
The key text: but it really describes 3 different
algorithms.
====================================================
DISTRIBUTED CONSENSUS PROBLEM
Network of computers (agents) that can lose messages but never corrupts them
(semi-realistic)
Agents can fail completely but don't lie or break the rules
Proposer agents propose values
Acceptor agents can accept proposals or reject them
Goals: Majority of acceptors agree on value,
Winning proposer sees agreement
No more than one winning value (safety)
====================================================
SIMPLE SOLUTION - NOT PAXOS
1. One network "agent" is the only proposer
2. The proposer sends a proposed value to all acceptor agents until ..
Acceptors send back acknowledgment messages
3. When the proposer has acks from a majority it knows it has won
Use timeouts to make it more robust -
Oki and Liskov, Viewstamped Replication, 1988
Use cycles for more efficiency
Chang and Maxemchuk, Reliable Broacast Protocols, 1984
Use with "state machine" model for fault tolerance
Borg, Baumbach, Glazer,
A Message System Supporting Fault Tolerance 1983
====================================================
PAXOS SOLVES THE PROBLEM OF TOO MUCH SIMPLICITY
Key premise at start is the network is asynchronous (no clocks)
(fashionable premise 1980s, not realistic)
also that the algorithm needs multiple proposers
(for fault tolerance, performance?)
Clever idea: Multiple winning proposers ok
- if they all propose the same value.
2 phase algorithm ensures that proposers converge on single
winning value
====================================================
PAXOS MADE SIMPLE
Pages 1-6 explain how the algorithm works
Page 6, Lamport explains that the algorithm "livelocks" although it is safe
Page 7: different algorithm also called Paxos that has a single proposer
selected via timeouts (clocks) or randomization.
Rest: the state machine model of fault tolerance using Paxos2
Question: What is advantage of Paxos2 over Simple Method?
====================================================
HOW DOES PAXOS1 SORT OF WORK?
id numbers are unique per proposer and per proposal.
(called "sequence numbers" in Paxos Made Simple)
Proposers start in phase1 and ask acceptors to agree to their proposal id.
When/if a majority of acceptors agree to the proposal id
The proposer can pick a value, enter phase 2,
and send its actual proposal
When/if a majority of acceptors accept the proposal, the proposer wins
Key: the messages agreeing to a proposal id carry the best
(highest numbered) proposal the acceptor has accepted so far
the proposer has to take (inherit) the value from the highest
numbered one of those
====================================================
THERE ARE FOUR KINDS OF MESSAGES
(phase1, id) - sent by proposers in phase 1 to acceptors
(ok1, id, bestproposal ) -sent by acceptors to agree to phase 1
(phase2, id,value) - sent by proposers in phase 2
(ok2, id) - sent by acceptors to agree to phase 2 proposal
Also messages reliably carry the identity of the original sender
of the message
====================================================
ACCEPTORS ENFORCE ID ORDER
Each acceptor A keeps track of
A.BestID which is the highest id it has agreed to (either phase)
A.BestID is initially 0
A.BestProposal =(phase2,id,value) the highest numbered proposal
the acceptor has accepted
A.BestProposal is initially null
When an acceptor A receives m=(phase1,id) if m.id > A.BestID
can send (ok1,m.id,A.BestProposal) back
update A.BestId = m.id
When an acceptor A receives m=(phase2,id,value) if m.id >= A.BestId
can send (ok2,m.id) back and update A.BestProposal=m and A.BestId=m.id
====================================================
PROPOSERS CAN ABANDON THEIR NON-WINNING PROPOSALS
They can pick a new id number that must be higher and still unique
and start over
at any time
but it can still livelock forever
Proposer 1 and 2
2 starts and gets a majority in phase 1 and then rests
1 starts and gets 1 less than a majority, blocks, increases
number to 3, gets a majority for phase 1
... repeat
=====================================================
PROOF OF SAFETY:
If only one proposal has won, nothing to prove
If more than one proposal has won, let
m_0 =(id0,value0) be the winning proposal with the lowest id number
Let L = (m_0,m_1,m_2 ... m_N) add to m_0, in id order,
the complete list of proposals
with m_i.id > m_0.id that have been sent by some proposer,
If m_i is on the list,
the proposer of m_i reached phase2 with id m_i.id
L includes all winning proposals plus more
Claim: All of these must have the same value v = m_0.value.
====================================================
WHY?
P0 sent m_0 and received (ok2,m_0.id) from a majority of acceptors
because we chose it as the lowest numbered WINNING proposal
if P sent proposal m_i, i>0, then P got
(ok1,m_i.id, best) from a majority of acceptors
The two majority sets of acceptors must intersect at some A
A must have sent (ok2,m_0.id) BEFORE it sent
(ok1,m_i.id,A.BestProposal) since m_i.id > m_0.id
When A agrees to m_i.id it already accepted m_0,
so A.BestProposal was not null
and m_0.id <= A.BestProposal.id < m_i.id
P must have inherited at least 1 proposal m with
m_0.id <= m.id < m_i.id
====================================================
BACK TO LIST FOR INDUCTION
L = (m_0,m_1,m_2 ... m_N)
CLAIM i >= 0 implies m_i.value = m_0.value.
Proof by induction.
True for i=0
Suppose true for 0,... j-1 and consider j
the proposer P of m_j inherited some best message m with
m_0.id <= m.id < m_j.id
and since m was sent, the proposer of m must have reached phase2
so m must be on the list.
Since m.id < m_j.id and it is on the list,
m.value = m_0.value and so m_j.value = m_0.value
QED.
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.
“A day is coming, when, in the eye of the law, literary property will be as sacred as whisky, or any other of the necessaries of life.” —Mark Twain”
Inventors, programmers, writers, and musicians often get the same advice for the new Internet economy and the world of downloading and digital copying. The advice is to embrace new business models which give us exposure and access, maybe even fame or cryptocurrency in place of boring old money. We can sell labor like consulting services and live performances, T-shirts and books too, but we better give up hopes of obsolete and shameful licensing fees and royalties.
Here’s the foremost legal theorist of the Free Software Movement insisting that the collapse of copyright law will be good for musicians too ( from Liberation Musicology published in The Nation magazine in 2001).
“This increase in efficiency means that composers, songwriters and performers have everything to gain from making use of the system of unowned or anarchistic distribution, provided that each listener at the end of the chain still knows how to pay the artist and feels under some obligation to do so, or will buy something else–a concert ticket, a T-shirt, a poster–as a result of having received the music for free. Hundreds of potential “business models” remain to be explored … “
Back in 2000, when I started a software company, I was advised to give away software and sell services. The argument was that my company would be known as the experts on what we had invented and customers would pay a premium for our work. Each user in the chain would know how to pay the inventor and feel under an obligation to do so and we’d be profitably exploring a new business model. Well, it seemed plausible enough at the time if you were not too smart (raises hand). But it turns out that neither corporations nor consumers — the customers — are interested in this model.
Experience taught us that the business logic of corporate customers was not favorable to small company inventors who sold services. Our small business with a new product came with a certain level of risk that customers could reduce by asking some huge corporation to support the software instead of relying on a tiny startup. On the other hand, low wage consultants and competing venture funded startups could always under-price us particularly since we did all the work and bore all the cost of inventing and making the software. And to complete the picture, users in the chain who had money at stake were very quick to come up with convenient reasons why they did not have an obligation to pay us. Our ideas were, according to them, wrong, obvious and well known, not new at all. Our personalities were lacking in charm, our sense of style was off, our demands unreasonable. Any competent engineer, we were informed, could reproduce what we did over a weekend. In short, we didn’t deserve payment of any kind. I have heard very similar justifications for copying music in similarly resentful tones. People downloaded our code, rearranged it, and announced they had something better that owed nothing to our crappy inventions anyway. We were left with a very small bit of the market – unusual people who were willing to take a chance. We met some cool people, but it was no way to make a living .
Professor Moglen was correct, however, in the sense that this system was very efficient for the big companies that used our work. Instead of royalties and licensing fees, they only needed to pay for labor in a market where everyone was undercutting everyone else. Big companies with brands, marketing power, distribution, large legal teams, and lots of different ways to charge can often find all sorts of ways to wring money from products (“monetize”). In fact, the ways in which big companies like Amazon, IBM, and Google exploit free software both as users and contributors are fascinating for people who find innovative business models fascinating. Record companies can offer low royalty payments to Spotify and make it back on equity, non-license fees, and sheer volume ( as David Byrne explained). They can even mass produce T-shirts. RedHat and Oracle can sell free software by leveraging marketing, brand name, and risk minimization. RedHat’s Bob Young used to have a standard speech explaining both that he, Young, was dumber than his audience of programmers and that Red Hat’s business was like ketchup where Heinz could charge a premium because of brand alone. The first part was an outrageous lie well crafted to appeal to an audience of egotistical and naive programmers, but the second part was true enough. Even IBM used to give away software back when it was essentially the only computer hardware vendor in the world. The software helped them sell hardware and kept competing software vendors from taking too much of the revenue stream. For that matter, selling bottled tap water can be a very profitable business for Pepsi, but only because it has the distribution channels and marketing reach. In the end, though, all this clever monetization can leave artists and inventors who are not marketing wizards with a small share of the T-shirt revenue- if that.
Eventually we lost the faith, stopped releasing our code and started enforcing our intellectual property rights. Not everyone was happy. A high level corporate manager in a big company told me “we know about your technology and we understand its advantages but your patents make it awkward for us to use.” I asked what was awkward about paying a license fee, and he told me that his company was not about to pay license fees to some small time losers from nowhere. But here’s the important fact: Copyrights and patents, although they are often misused, can make it more awkward for big companies to shift revenue from the artists or inventor’s pocket to the corporate pocket in the course of some “agile efficient monetization of the marketplace”. Efficiency is one of those virtues that depends on where you sit. It’s certainly less efficient for a giant corporation to devote time and effort to licensing technology from small companies or paying ungrateful artists for their music than to simply make use of it. It’s expensive for a large firm to vet a product from a small company for utility and possible legal exposure and, at least initially, low cost to just download something for free.
On the other hand, it’s a lot more efficient for an inventor, programmer, writer, or musician to get a royalty check than to sell T-shirts. More lucrative, anyway.
There are downsides to depending on other people to do the work for nothing, but they are downstream ones. A manager or programmer at a tech company would have received a chilly response from her bosses a couple of years ago if she had explained that the company was depending on a minor component for logging, produced by some volunteer team, and that the corporation should go through all the effort needed to onboard that tiny team as a vendor and purchase and vet that software even though it could be downloaded for free. Years later, it turned out the software in question opened a major security hole in corporate firewalls and nobody who decided to download it for free was fired.
Property versus intellectual property
But is any of this morally correct? For many people software patents are bad, in fact, intellectual property itself is bad. One complaint involves the supposedly dubious status of intellectual property as property. The argument goes something like this:
“the owner of a digital recording or program doesn’t lose anything when a copy is made, unlike the owner of a piano or a bicycle who no longer has physical possession if ownership is transferred. You still have a recording of your movie or musical performance or program even if someone is letting people download copies for nothing. See – it’s not actual property.”
But even with physical objects, ownership and transfer is not really that simple. Suppose my family and I move into your house without your permission. You still “have” the house – the physical object is still there. If there is sufficient space or if it’s a rental house, you may not even be inconvenienced. What you’ve lost is something far more abstract than a physical object. You lost a right to control use or to demand payment for use – exactly what the musician lost when someone pirated her song. And what about intangible property? Bank accounts, loans and other financial assets are intangible pseudo-objects that have less physical presence than a bunch of bits encoding a song or program. If your financial adviser embezzles your retirement savings to bet on the dog track or your bank invents bogus charges that they deduct from your account, no physical object passes out of your possession but you’d most likely consider yourself deprived of something. What you were deprived of is a right to some money, itself a strange non-material abstraction. Property rights are all about fictional entities, pseudo objects, rights to forbid others to do something and so on – there is nothing specially unmaterial or spectral about intellectual property compared to other kinds of property.
We also heard that some kinds of IP are more worthwhile than others. It’s not especially surprising, I suppose, that these theories often seem to align with the financial interests of the person making the argument (me included, of course). For example, in Germany software patents are widely derided, but patents on pharmaceuticals (controversial elsewhere) are not. Germany is a net payer on one of those kinds of patents and a net payee on the other kind. Guess which is which. Similarly, I’ve had interesting discussions about software intellectual property with people who work for computer hardware companies and sincerely believe software intellectual property to be dubious at best. For them, somehow, a design expressed in a hardware programming language which is then converted into a recipe for computer chips can be worthy of protection, but a design expressed in a different programming language that is then converted into a process for controlling the machinery that makes those same chips is different in kind. The most entertaining argument I saw, however, was from an enthusiastic supporter of free software who wrote an indignant email to me from his company account, lambasting my use of software patents. When I pointed out that his corporate employer owned a lot more software patents than we did, he explained that his employer was a commercial enterprise and my business was not. Musicians seem to often get these kinds of lectures too.
The internet changes everything
People also argue that the nature of the internet and of digital representations of music and programs and movies makes that old-fashioned copyright and patent stuff obsolete. Here’s Professor Moglen again:
“our world consists increasingly of nothing but large numbers (also known as bitstreams), and that – for reasons having nothing to do with emergent properties of the numbers themselves – the legal system is presently committed to treating similar numbers radically differently. No one can tell, simply by looking at a number that is 100 million digits long, whether that number is subject to patent, copyright, or trade secret protection, or indeed whether it is “owned” by anyone at all. “
No one can tell, simply by looking at it, whether a particular block of land or house or apartment is “owned” by one private individual or another, though. Does simply looking at an automobile or a pile of I-beams or a basket of mangos, produce information on whether that object is owned, or leased, or stolen? There is nothing fundamental about a number that tells you whether it encodes a program or musical composition protected by copyright, or a method protected by patent, but there’s nothing “emergent” about a vat of chemicals or a ball point pen that tells you whether it embodies a patented chemical process or mechanical design. Ownership is not a physical property of an object or pseudo-object, ownership comes out of social relationships of human beings. Moglen continues:
” Like everything else in the digital world, music as seen by a CD player is mere numeric information; a particular recording of Beethoven’s Ninth Symphony recorded by Arturo Toscanini and the NBC Symphony Orchestra and Chorale is (to drop a few insignificant digits) 76749873424, while Glenn Gould’s peculiarly perverse last recording of the Goldberg Variations is (similarly rather truncated) 767459083268. Oddly enough, these two numbers are “copyrighted.” This means, supposedly, that you can’t possess another copy of these numbers, once fixed in any physical form, unless you have licensed them. And you can’t turn 767459083268 into 2347895697 for your friends (thus correcting Gould’s ridiculous judgment about tempi) without making a “derivative work,” for which a license is necessary.”
It’s illuminating to transfer this argument back to an older technology.
“Like everything else in the printed world, novels are mere sequences of letters; a particular printing of Fledgling might contain “When your rage is choking you, it is best to say nothing.”, while “the banana company did not have, never had had, and never would have any workers in its service” is from One Hundred Years of Solitude. You can’t fix Octavia Butler’s anger or Garcia-Marquez’s antipathy to banana companies and make other copies of these sequences of letters for your friends unless you have licensed them.”
We had copyrights for written works long before there were those electronic computers and pesky binary numbers that are supposedly eroding the whole basis of copyright law. And, by the way, that line about “correcting” Gould hit home for me. If you think you can play the piano better than Glenn Gould, go ahead. If you don’t like his work, don’t buy it. If you want to be “creative” with it and distribute it, pay a license fee to his heirs. The concept of “derivative work” in intellectual property law is there because people were publishing “improved” versions of Mark Twain’s work too. Intellectual property is important primarily because of the money, but it’s also important because it allows the people who create the product to exercise some control of how it is used. Neil Young was able to prevent Spotify from using his music to promote disinformation because he owned the rights. For our real-time software, one question I used to ask free software advocates was to explain why it would be immoral for us to forbid use of the software to control land mines.
Free software, public domain software, creative commons licenses – all of those can be good things. Irving Wladawsky-Berger’s recognition of how free software could help IBM’s business was pretty much brilliant although one could easily come up with more cynical formulations of his explanation. I even agree with those who say music and inventions are never wholly original, but build on the accomplishments of others. Of course they are. None of that justifies compulsory pre-emptive “freeing” of creative works or inventions by consumers of that work who just feel like they know better or, more likely, that their corporate employer would find it easier. Commerce is all about incentives and the incentive of a corporate lawyer or manager to insist that the company should pay an individual inventor or small business because it is the right thing to do is not all that high, believe it or not. Same with the incentive of a consumer to buy a song or movie that can be downloaded for free. And when some companies find it more profitable to use your work without paying, that makes it even more difficult for people at other companies to argue in favor of cutting you a big check. If all your friends stream new music from a company that systematically underpays artists, you tend to look like a chump for paying more. The same peer pressure operates in corporate purchasing. A lot of people actually want to do the right thing, but very few will buck the trend to do so.
And what’s the right thing?
“To promote the Progress of Science and useful Arts, by securing for limited Times to Authors and Inventors the exclusive Right to their respective Writings and Discoveries.”
The legal system of intellectual property is far from perfect. Actually, it’s scarily imperfect. Several times only dumb luck saved us being ground up between the vast resources of big companies and the vast expense of the legal system. But I was able to help create interesting technology, and get paid for it, and stay independent, because the much maligned intellectual property laws do something to protect inventors, musicians, artists, film makers and others who don’t want to work for a giant multinational, but do want to make things.
A free software advocate once told me that Mozart didn’t need copyrights. Years later I read Mozart’s letters and was appalled at how much time he had to spend groveling to wealthy sponsors. And maybe those of us who are less talented than Mozart but also create works that other people want to use or listen to or read also should get paid by labor right, not because someone with money wants to be a sponsor. So when next you hear about terrible Disney and their apparently infinite copyrights on Mickey, or about some patent troll demanding to be paid, or some musician suing a streaming service, think also about those of us who just want to be paid when someone uses our writings, music, creations, and discoveries. Proudhon may have been right and property may be theft, but in a society based on thievery, it is quite convenient to have some property.
YOUR GRACE, MOST WORTHY PRINCE OF THE HOLY ROMAN EMPIRE!
I will not presume to trouble Your Grace with a full description of our unhappy circumstances, which my father has set forth most accurately in his very humble petition which was handed to you on March 14th, 1777. As, however, your most gracious decision was never conveyed to him, my father intended last June once more most respectfully to beg Your Grace to allow us to travel for a few months in order to enable us to make some money; and he would have done so, if you had not given orders that in view of the imminent visit of His Majesty the Emperor your orchestra should practise various works with a view to their performance. Later my father again applied for leave of absence, which Your Grace refused to grant, though you permitted me, who am in any case only a half-time servant, to travel alone. Our situation is pressing and my father has therefore decided to let me go alone. But to this course also Your Grace has been pleased to raise certain objections. Most Gracious Prince and Lord! Parents endeavour to place their children in a position to earn their own bread; and in this they follow alike their own interest and that of the State. The greater the talents which children have received from God, the more are they bound to use them for the improvement of their own and their parents’ circumstances, so that they may at the same time assist them and take thought for their own future progress. The Gospel teaches us to use our talents in this way. My conscience tells me that I owe it to God to be grateful to my father, who has spent his time unwearyingly upon my education, so that I may lighten his burden, look after myself and later on be able to support my sister. For I should be sorry to think that she should have spent so many hours at the harpsichord and not be able to make good use of her training.
Your Grace will therefore be so good as to allow me to ask you most humbly for my discharge, of which I should like to take advantage before the autumn, so that I may not be obliged to face the bad weather of the ensuing months of winter. Your Grace will not misunderstand this petition, seeing that when I asked you for to travel to Vienna three graciously declared that I had nothing to hope for in Salzburg and would do better to seek my fortune elsewhere. I thank Your Grace for all the favours I have received from you and, in the hope of being able to serve you later on with greater success, I am
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.
In computer science academia, C along with UNIX, and PDP11s, is as unfashionable as can be: the equivalent of other 1970’s relics, like polyester leisure suits and mullets.
In 2018 ACM Queue published an essay by David Chisnall called: C Is Not a Low-level Language: Your computer is not a fast PDP-11 that expresses many common misconceptions about C and also takes the time to make a bunch of incorrect claims about computer architecture. The same authors 2015 ASPLOS paper Beyond the PDP-11: Architectural Support for a Memory-Safe C Abstract Machine has much more interesting information about how C is used in practice and about an alternative computer architecure, but I want to focus on the first, because I think the general tendency in academic Computer Science to dismiss C as an embarassing fashion faux-pas has important consequences.
Let’s go through some of Chisnall’s article, starting with this claim:
“Most of the complexity involved [in hardware caches] comes from supporting a language [C] in which data is expected to be both shared and mutable as a matter of course.”
Although the recent C11 standard tried to graft on some ideas about concurrency (not a good idea or well done either), historically C doesn’t have have any notion of concurrency or data sharing1. The first wide use of “threading” in C applications involved UNIX fork/exec which doesn’t share any memory at all. The language designers made a conscious, and successful, choice to leave such things outside the scope of the language.
BSTJ 57: 6. July-August 1978: UNIX Time-Sharing System: The C Programming Language. (Ritchie, D.M.; Johnson, S.C.; Lesk, M.E.; Kernighan, B.W.
The poor judgment of the C11 authors didn’t really change that.
“Creating a new thread [in C ] is a library operation known to be expensive,
C has threading libraries, but none of them is required (otherwise you couldn’t develop operating systems in C or support multiple thread models). C thread creation is also not known to be expensive. Determining factors are implementations, processor architectures, and, for user threads, operating system interfaces.
so processors wishing to keep their execution units busy running C code rely on ILP (instruction-level parallelism).”
Instruction level parallelism predates C by 10 years and is not specific to any programming language. The first production computer with ILP was the CDC 6600, brought to market in 1964 and intended to run FORTRAN.
In the wake of the recent Meltdown and Spectre vulnerabilities, it’s worth spending some time looking at root causes. Both of these vulnerabilities involved processors speculatively executing instructions past some kind of access check and allowing the attacker to observe the results via a side channel. The features that led to these vulnerabilities, along with several others, were added to let C programmers continue to believe they were programming in a low-level language, when this hasn’t been the case for decades.
The CDC 6600 also had speculative branch prediction as did the IBM 360/91 (1967). C was developed in the 1970s, well after and only became popular in the 1980s or later.
The root cause of the Spectre and Meltdown vulnerabilities was that processor architects were trying to build not just fast processors, but fast processors that expose the same abstract machine as a PDP-11. This is essential because it allows C programmers to continue in the belief that their language is close to the underlying hardware. In contrast, GPUs achieve very high performance without any of this logic, at the expense of requiring explicitly parallel programs.
Let’s go through these:
GPUs are primarily programmed in C dialects, so I’m not sure what is going on there. Using C was the easy choice for GPU makers because of C’s deliberately incomplete nature (see below).
What C programmers believe about C does not matter to computer architects.
The root cause of the Spectre and Meltdown failures is that it is really hard to do out-of-order pipelines with speculative execution and buffered memory access (there is way too much state moving too fast) but the performance advantage makes it hard to pass up.
As for PDP-11s, this is a common error. C was ported to IBM/370, Honeywell 6000, Inter data 8/32, Sel86, Data General Nova, Vax and other processors in the mid 1970s – back in the days when there were multiple very different machine architectures. By the mid 1980s, when C was becoming a popular language, and the ANSI standard was developed the successor VAX architecture supported SMP and C was already highly popular on microprocessors. Much of what changed in C in that era was to make it portable to that wild profusion of architectures.
It’s worth noting that Chisnall knows this last complaint is wrong, as he writes later:
The C model, in contrast, was intended to allow implementation on a variety of targets, including segmented architectures (where a pointer might be a segment ID and an offset) and even garbage-collected virtual machines.
In any case, although dismissing the PDP11 is in vogue, the PDP-11 always had an MMU and caches and had parallel processing (with DMA capable devices and co-processors). Although the article subhead is “Your computer is not a fast PDP-11”, really it is pretty much – just vastly larger (in terms of transistors ), and faster. Processor architectures today incorporate a lot of innovation, but use the same basic model programmers encountered 50 years ago and X86-64 and ARM are both much closer to the PDP-11, for good or ill, than to the 36 bit Honeywell 6000, the Interdata 8/32 , or the Intel 8086 and I486 for that matter.
Let Professor Hennessy explain:
From John Hennessy https://p4.org/assets/P4WS_2019/Speaker_Slides/9_2.05pm_John_Hennessey.pdf
But Chisnall is not done with C.
We have a number of examples of designs that have not focused on traditional C code to provide some inspiration. For example, highly multithreaded chips, such as Sun/Oracle’s UltraSPARC Tx series, don’t require as much cache to keep their execution units full. Research processors2 have extended this concept to very large numbers of hardware-scheduled threads. The key idea behind these designs is that with enough high-level parallelism, you can suspend the threads that are waiting for data from memory and fill your execution units with instructions from others. The problem with such designs is that C programs tend to have few busy threads.
None of these are new or untested ideas. The Cray MTA architecture was a really interesting design that was even built and commercialized and it was designed to run C and Fortran. The problem with such designs is that highly threaded algorithms are difficult and sometimes impossible (see Amdahl’s Law) in general. The exceptions are specialized processors such as GPUs (where C is used!).
For example, in C, processing a large amount of data means writing a loop that processes each element sequentially
In the Von Neumann style computer architecture (every single existing commercial processor), data is stored in memory and must be brought through the “Von Neumann bottleneck” into the processor. Caches help, and for certain types of processing, data can be moved and modified in larger chunks (vectors) which can be modified in parallel (SIMD processing is another 1960s innovation as explained in most intro computer architecture courses). When the processor can operate on those longer vectors, it still relies on loops with the same characteristics as loops over bytes for large amounts of data. Dennis Ritchie thought that C was too limited in its treatment of arrays, but being able to e.g. apply a map to an array in the programming language just hides the loop. Writing \(A.map(x -> x*x)\) doesn’t magically transfer the whole array into the CPU vector unit which can, at best, multiply only a few elements at a time. For big arrays, it is still necessary to loop through the data, and for small arrays, there is not much to win ( here are some other ideas). Chisnall knows this too, because he’s unhappy at how hard it is to compile vector loops in C.
To run this optimally on a modern CPU, the compiler must first determine that the loop iterations are independent. The C restrict keyword can help here. It guarantees that writes through one pointer do not interfere with reads via another (or if they do, that the programmer is happy for the program to give unexpected results). This information is far more limited than in a language such as Fortran, which is a big part of the reason that C has failed to displace Fortran in high-performance computing.
Intel’s comments on the problems of vectorizing C and FORTRAN say the opposite. Vectorization is a hard problem – C’s restrict keyword is a good clue to the compiler, and possibly a vector data type would help (as the author argues) but FORTRAN doesn’t have better information for the compiler. What FORTRAN has (a) no pointers which makes things simpler and (b) a whole lot of special purpose compiler directives and expert programmers who know how to exploit data parallelism. FYI: C was not intended by its designers to displace Fortran in HPC.
Unfortunately, simple translation providing fast code is not true for C. In spite of the heroic efforts that processor architects invest in trying to design chips that can run C code fast, the levels of performance expected by C programmers are achieved only as a result of incredibly complex compiler transforms. The Clang compiler, including the relevant parts of LLVM, is around 2 million lines of code. Even just counting the analysis and transform passes required to make C run quickly adds up to almost 200,000 lines (excluding comments and blank lines).
Much of Clang’s complexity (and the same for GCC) comes from its role compiling C++ which is a gigantic language that incorporates C as a sublanguage. Additionally, LLVM is designed as a general platform for a number of languages and LLVM’s complexity is far from C specific. What would be very interesting to know is how much of Clang’s C performance comes from anything past the 40 year old basic optimization methods like register coloring, peephole optimization, vectorizing and maybe unrolling loops. But here we turn to real issues:
In C, a read from an uninitialized variable is an unspecified value and is allowed to be any value each time it is read. This is important, because it allows behavior such as lazy recycling of pages: for example, on FreeBSD the malloc implementation informs the operating system that pages are currently unused, and the operating system uses the first write to a page as the hint that this is no longer true. A read to newly malloced memory may initially read the old value; then the operating system may reuse the underlying physical page; and then on the next write to a different location in the page replace it with a newly zeroed page. The second read from the same location will then give a zero value.
This is an interesting point, because it reveals a common problem in current criticisms of C – and of the current efforts of the C Standards and C Compilers: a failure to understand the open border C design or maybe just dislike for it. C was intended as a systems and particularly operating systems language. Unlike Java and most other programming languages, a C program interacts directly with the hardware (and operating system) and other interfaces. Stephen Kell has a paper on precisely this point. That’s why C has no foreign function interface (FFI) but can directly call out to assembler or even support in-line assembler (and C doesn’t have an unsafe mode, because it is an unsafe mode). Although the C standard document goes on about the “abstract machine”, C gets a lot of its utility from being able use operations that are semantically defined by hardware or other external interfaces. C benefits from incomplete semantics (which is why the ongoing mess about undefined behavior is so damaging to C programmers). In the case mentioned by Chisnall, the FreeBSD operating system is playing games with the page allocator so allocated pages may not act like abstract store until a write operation2. This should not matter to a C program, because, especially in OS programming, this kind thing is not unusual. Weird interactions with memory are one reason why C has the concept of intederminate values. C code can even read device memory that changes its value on each read (think of a hardware fifo from a Analog-to-Digital sensor, for example). In these cases, the C compiler is supposed to let C operate as a high level assembly language and stay out of it.
And then Chisnall makes a really good point.
If an unspecified value for flow control is used (for example, using it as the condition in an if statement), then the result is undefined behavior: anything is allowed to happen. Consider the loop-unswitching optimization, this time in the case where the loop ends up being executed zero times. In the original version, the entire body of the loop is dead code. In the unswitched version, there is now a branch on the variable, which may be uninitialized. Some dead code has now been transformed into undefined behavior. This is just one of many optimizations that a close investigation of the C semantics shows to be unsound.
The important observation here is that under the current interpretation of the C standard, a number of compiler optimizations are unsound and have been for some time. This has been tolerated because C is so very out of fashion and there is little appreciation of the basic design concepts of the C language (except from people who use it.) What is going on here is that standards contributors and compiler developers who start with the assumption that C is an obsolete and semantically confused language feel no obligation to play fair with the programmers who they believe are making a mistake even wanting to write code in the language. This is why Chris Lattner of LLVM ends his gloomy (and insightful) analysis of the state of C compilation with a suggestion that programmers should switch to another language (like his own). And that is unfortunate because C is far from a perfect language and slow changes in computer architecture are frustrating, but if you don’t know what works and what doesn’t work, you won’t be able to fix anything. And, finally, some things from the 1970s were pretty good.
NOTE 1: The unnecessary complexity of shared data in caches is unpleasant but that’s not C’s fault.
NOTE 2: The much loathed Bourne Shell, in addition to using the pre-processor to pretend it was written in ALGOL for unknown reasons, also implemented a user mode virtual memory with C/UNIX signals. It allocated virtual memory addresses without bothering to call the OS for more memory, and then caught write traps and tried to fix things.
