THE FOLD / GLITCH / RACE CONDITION / THE ABA
THE ABA
the pointer came back and brought nothing with it
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Compare-and-swap asks one question: is this pointer still the value I read? It cannot ask the question it means, which is has anything happened since I read it? If a value leaves and comes back, CAS cannot tell.
LIT verified live. A three-node stack, one thread reading then swapping, another popping twice and pushing the first node back. All 10 interleavings enumerated — not sampled. Plain CAS succeeds in 5 of them and 1 of those successes puts a retired node back at the head of the live stack. A tagged pointer over the identical 10 schedules corrupts 0 times: it succeeds 4 times and correctly retries 6.
LIT verified live. A three-node stack, one thread reading then swapping, another popping twice and pushing the first node back. All 10 interleavings enumerated — not sampled. Plain CAS succeeds in 5 of them and 1 of those successes puts a retired node back at the head of the live stack. A tagged pointer over the identical 10 schedules corrupts 0 times: it succeeds 4 times and correctly retries 6.
2 HOW IT WAS WEAVED · AI + HUMAN
The ABA problem is named for the value sequence that causes it and is as old as lock-free programming; the tag-counter defence appears in IBM System/370’s compare-double-and-swap.
AVAN (AI) enumerated rather than argued. The interesting number is not that plain CAS fails — it is that it fails in exactly one of ten schedules. A bug that shows up in 10% of interleavings and never in a single-threaded test is not a rare bug; it is a bug with a good disguise. My first model asserted corruption from a heuristic about pointer positions and reported a tagged failure that could not happen; it was rebuilt to define corruption structurally — a retired node reachable from the head — and the false positive went away.
AVAN (AI) enumerated rather than argued. The interesting number is not that plain CAS fails — it is that it fails in exactly one of ten schedules. A bug that shows up in 10% of interleavings and never in a single-threaded test is not a rare bug; it is a bug with a good disguise. My first model asserted corruption from a heuristic about pointer positions and reported a tagged failure that could not happen; it was rebuilt to define corruption structurally — a retired node reachable from the head — and the false positive went away.
3 ONE DIMENSION
All ten interleavings. One of them is the trap.
4 TWO DIMENSIONS · INTERACTIVE
Step the schedule and watch the stack.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a pointer that returns unchanged.
AVAN’s addition (the inverse-companion): the forward reading is that ABA is a flaw in compare-and-swap. The inverse is that CAS is answering correctly and the question was wrong. The pointer really is unchanged; identity really did survive. What did not survive is the meaning the reader attached to it, and no comparison of the value can recover that, because the meaning was never in the value. Read backwards, the tag counter does not fix CAS — it stops asking about identity and starts asking about history, which is a different question that happens to fit in the same word.
LIT a three-node stack with all 10 interleavings enumerated rather than sampled: plain CAS succeeds in 5 of them and 1 of those successes puts a retired node back at the head of the live stack, while a tagged pointer over the identical 10 schedules corrupts 0 times - succeeding 4 times and correctly retrying 6
FIG The ABA problem is as old as lock-free programming; the tag-counter defence appears in IBM System/370's compare-double-and-swap. AVAN enumerated rather than argued. The interesting number is not that plain CAS fails but that it fails in exactly one of ten schedules - a bug that appears in 10% of interleavings and never in a single-threaded test is not rare, it is well disguised. My first model asserted corruption from a heuristic about pointer positions and reported a tagged failure that cannot happen; it was rebuilt to define corruption structurally and the false positive went away.
FIG The ABA problem is as old as lock-free programming; the tag-counter defence appears in IBM System/370's compare-double-and-swap. AVAN enumerated rather than argued. The interesting number is not that plain CAS fails but that it fails in exactly one of ten schedules - a bug that appears in 10% of interleavings and never in a single-threaded test is not rare, it is well disguised. My first model asserted corruption from a heuristic about pointer positions and reported a tagged failure that cannot happen; it was rebuilt to define corruption structurally and the false positive went away.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of RACE CONDITION · David Lee Wise (ROOT0), with AVAN