THE FOLD / GLITCH / RACE CONDITION / THE SEQLOCK
THE SEQLOCK
starvation wearing the costume of latency
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
A reader that writes nothing. No lock to acquire, no cache line to own, no cost imposed on anyone else. It reads a counter, reads the data, reads the counter again — and if the two disagree it throws the answer away and starts over.
LIT verified live. enumerating every interleaving exhaustively: a plain unguarded reader against a two-field writer has 6 orderings, and 2 of them return a torn pair that violates the invariant. Wrapping the same reader in a sequence counter gives 70 orderings, of which 68 are detected and retried and 2 complete — and of the ones that complete, 0 are torn. The reader performs 0 writes to shared state in every case. Under a writer active 90% of the time, 89.96% of reads retry and the worst observed run needed 101 attempts.
LIT verified live. enumerating every interleaving exhaustively: a plain unguarded reader against a two-field writer has 6 orderings, and 2 of them return a torn pair that violates the invariant. Wrapping the same reader in a sequence counter gives 70 orderings, of which 68 are detected and retried and 2 complete — and of the ones that complete, 0 are torn. The reader performs 0 writes to shared state in every case. Under a writer active 90% of the time, 89.96% of reads retry and the worst observed run needed 101 attempts.
2 HOW IT WAS WEAVED · AI + HUMAN
Seqlocks are a standard Linux kernel primitive (Stephen Hemminger, from earlier reader/writer sequence schemes) used for
AVAN (AI) proved the safety property by exhaustion rather than argument — all 70 interleavings of a 4-op writer and a 4-op reader, with 0 torn results getting through. The number worth reporting honestly is the other one: 68 of 70 retried. In this tiny space the writer is always active, so that figure is not the real-world retry rate; the rate sweep is, and it climbs to 89.96% exactly where the writer does.
jiffies, timekeeping and other write-rare data.AVAN (AI) proved the safety property by exhaustion rather than argument — all 70 interleavings of a 4-op writer and a 4-op reader, with 0 torn results getting through. The number worth reporting honestly is the other one: 68 of 70 retried. In this tiny space the writer is always active, so that figure is not the real-world retry rate; the rate sweep is, and it climbs to 89.96% exactly where the writer does.
3 ONE DIMENSION
70 interleavings. Zero torn reads. Sixty-eight retries.
4 TWO DIMENSIONS · INTERACTIVE
Pick an interleaving and see whether the counter catches it.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object.
AVAN’s addition (the inverse-companion): the forward reading is that readers never block writers. The inverse is that the cost was moved, not removed — and it was moved somewhere nobody measures. The writer is wait-free; the reader is only obstruction-free, and its retries do not appear as contention, as a blocked thread, or in any lock profile. They appear as a read that took longer, which every latency graph will average away. Read backwards, a lock-free reader is not a reader that cannot be starved — it is a reader whose starvation has been made to look like slowness.
LIT enumerating every interleaving exhaustively, a plain unguarded reader against a two-field writer has 6 orderings of which 2 return a torn pair violating the invariant, while the same reader wrapped in a sequence counter gives 70 orderings of which 68 are detected and retried and 2 complete - and of those that complete, 0 are torn, with the reader performing 0 writes to shared state in every case; under a writer active 90% of the time 89.96% of reads retry and the worst observed run needed 101 attempts
FIG Seqlocks are a standard Linux kernel primitive used for jiffies, timekeeping and other write-rare data. AVAN proved the safety property by exhaustion rather than argument - all 70 interleavings, 0 torn results getting through. The number worth reporting honestly is the other one: 68 of 70 retried, and in this tiny space the writer is always active, so that figure is not the real-world retry rate. The rate sweep is, and it climbs to 89.96% exactly where the writer does.
FIG Seqlocks are a standard Linux kernel primitive used for jiffies, timekeeping and other write-rare data. AVAN proved the safety property by exhaustion rather than argument - all 70 interleavings, 0 torn results getting through. The number worth reporting honestly is the other one: 68 of 70 retried, and in this tiny space the writer is always active, so that figure is not the real-world retry rate. The rate sweep is, and it climbs to 89.96% exactly where the writer does.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of RACE CONDITION · David Lee Wise (ROOT0), with AVAN