THE FOLD / CO-OP / THE SYNC / THE MEMORY FENCE
THE MEMORY FENCE
a subtraction, not an instruction
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Store buffering: x=1 then read y, on one core; y=1 then read x, on the other. Both reading zero is impossible if the machine does what the program says. Every x86 in the world will do it anyway.
LIT verified live. enumerating every schedule exhaustively: under sequential consistency there are 6 interleavings and 0 of them produce
LIT verified live. enumerating every schedule exhaustively: under sequential consistency there are 6 interleavings and 0 of them produce
r0=r1=0. Add per-core store buffers and the schedule space grows to 80, of which 18 produce it — 22.5% of executions reach a state the source code forbids. Put a fence between each store and its load and the space collapses to 20 schedules, with 0 bad outcomes. The fence did not add anything: it deleted 60 of the 80 possible executions.2 HOW IT WAS WEAVED · AI + HUMAN
The store-buffer litmus test (SB) is the canonical TSO example, from Sewell, Sarkar and Owens’ x86-TSO work and every memory-model course since.
AVAN (AI) enumerated the linear extensions rather than reasoning about them, which caught a real error: the first sequential-consistency run reported 12 schedules and 1 bad outcome, because one load had been left unconstrained relative to its own thread’s store. Correcting the precedence gives 6 and 0 — and the fact that the buggy version produced a plausible number is the reason the check has to be exhaustive rather than sampled.
AVAN (AI) enumerated the linear extensions rather than reasoning about them, which caught a real error: the first sequential-consistency run reported 12 schedules and 1 bad outcome, because one load had been left unconstrained relative to its own thread’s store. Correcting the precedence gives 6 and 0 — and the fact that the buggy version produced a plausible number is the reason the check has to be exhaustive rather than sampled.
3 ONE DIMENSION
6 schedules, none bad. Then 80, and 18 are.
4 TWO DIMENSIONS · INTERACTIVE
Walk any schedule and watch both registers land on zero.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object.
AVAN’s addition (the inverse-companion): the forward reading is that a fence synchronises. The inverse is that a fence is a subtraction — it does not order your program, it removes futures from the machine. Nothing is added: no message, no handshake, no value. The count goes 80 → 20, and correctness arrives as the disappearance of 60 executions you never wanted. Read backwards, an unfenced program is not one that runs incorrectly; it is one that runs all of its possibilities, and every synchronisation primitive ever written is a way of saying which of them you refuse.
LIT enumerating every schedule exhaustively, sequential consistency gives 6 interleavings and 0 of them produce r0=r1=0; adding per-core store buffers grows the space to 80 of which 18 produce it, 22.5% of executions reaching a state the source code forbids; putting a fence between each store and its load collapses the space to 20 schedules with 0 bad outcomes - the fence added nothing, it deleted 60 of the 80 possible executions
FIG The store-buffer litmus test is the canonical TSO example, from Sewell, Sarkar and Owens' x86-TSO work. AVAN enumerated the linear extensions rather than reasoning about them, which caught a real error: the first sequential-consistency run reported 12 schedules and 1 bad outcome because one load had been left unconstrained relative to its own thread's store. Correcting the precedence gives 6 and 0 - and the buggy version producing a plausible number is exactly why the check has to be exhaustive rather than sampled.
FIG The store-buffer litmus test is the canonical TSO example, from Sewell, Sarkar and Owens' x86-TSO work. AVAN enumerated the linear extensions rather than reasoning about them, which caught a real error: the first sequential-consistency run reported 12 schedules and 1 bad outcome because one load had been left unconstrained relative to its own thread's store. Correcting the precedence gives 6 and 0 - and the buggy version producing a plausible number is exactly why the check has to be exhaustive rather than sampled.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE SYNC · David Lee Wise (ROOT0), with AVAN