THE FOLD / CO-OP / SPLIT SCREEN / THE RCU
THE RCU
never edit what someone might be reading
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Never modify what someone might be reading. Copy it, change the copy, swing the pointer — and then wait, not for a lock, but for every reader who could still be holding the old version to simply finish.
LIT verified live. enumerating all 56 interleavings of a five-step writer against a three-step reader: 0 readers see a torn structure and 0 touch freed memory, because each reader captures the pointer once and then holds an entire consistent version — 46 of them see the old one and 10 the new. Remove the grace period and free immediately after publishing, and 12 of the 35 remaining interleavings dereference memory that has already been reclaimed. In every case the reader performs 0 writes to shared state.
LIT verified live. enumerating all 56 interleavings of a five-step writer against a three-step reader: 0 readers see a torn structure and 0 touch freed memory, because each reader captures the pointer once and then holds an entire consistent version — 46 of them see the old one and 10 the new. Remove the grace period and free immediately after publishing, and 12 of the 35 remaining interleavings dereference memory that has already been reclaimed. In every case the reader performs 0 writes to shared state.
2 HOW IT WAS WEAVED · AI + HUMAN
Read-copy-update is Paul McKenney’s, in the Linux kernel since 2002; the copy-publish-wait structure and the grace period are his.
AVAN (AI) enumerated the schedule space instead of arguing about it, and split the claim in two. The 0 torn reads is structural — a reader that captures the pointer once cannot straddle two versions, and it is worth saying that plainly rather than dressing it up as a surprising measurement. The number that is not structural is 12 of 35: that is what the grace period is actually buying, and without it the failure is not rare.
AVAN (AI) enumerated the schedule space instead of arguing about it, and split the claim in two. The 0 torn reads is structural — a reader that captures the pointer once cannot straddle two versions, and it is worth saying that plainly rather than dressing it up as a surprising measurement. The number that is not structural is 12 of 35: that is what the grace period is actually buying, and without it the failure is not rare.
3 ONE DIMENSION
56 interleavings. Nobody reads a half-built object.
4 TWO DIMENSIONS · INTERACTIVE
Walk a schedule and see which version the reader got.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object.
AVAN’s addition (the inverse-companion): the forward reading is that RCU makes readers free. The inverse is that the cost did not disappear, it was converted into memory and deferred. The writer cannot reclaim until the last pre-existing reader finishes, so a single slow reader holds the whole reclamation queue open; the garbage is unbounded by construction, because the bound is ‘whenever everyone happens to be done.’ Read backwards, RCU trades a latency you can see — a lock — for a memory footprint you cannot, and the price of never blocking a reader is never being able to promise when the memory comes back.
LIT enumerating all 56 interleavings of a five-step writer against a three-step reader, 0 readers see a torn structure and 0 touch freed memory - 46 see the old version and 10 the new, because each captures the pointer once and holds an entire consistent copy; remove the grace period and free immediately after publishing, and 12 of the remaining 35 interleavings dereference reclaimed memory, with the reader performing 0 writes to shared state in every case
FIG Read-copy-update is Paul McKenney's, in the Linux kernel since 2002. AVAN enumerated the schedule space and split the claim in two: the 0 torn reads is STRUCTURAL - a reader that captures the pointer once cannot straddle two versions, and it is worth saying plainly rather than dressing up as a surprising measurement. The number that is not structural is 12 of 35, which is what the grace period actually buys.
FIG Read-copy-update is Paul McKenney's, in the Linux kernel since 2002. AVAN enumerated the schedule space and split the claim in two: the 0 torn reads is STRUCTURAL - a reader that captures the pointer once cannot straddle two versions, and it is worth saying plainly rather than dressing up as a surprising measurement. The number that is not structural is 12 of 35, which is what the grace period actually buys.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of SPLIT SCREEN · David Lee Wise (ROOT0), with AVAN