At the ferry town there was a left-luggage hut for travellers crossing the river.

It was small: eighty wooden pegs on one wall, numbered one to eighty. Each peg held one trunk on top of another, and every trunk had a slip of paper pinned to its side reading “the peg below me is number such-and-such.” Eighty pegs strung into a single chain, and the keeper only ever cared about the top one.

On the floor against the wall lay a ledger. Its first page held one line: “Top peg: seven.” That line was the hut’s entire bookkeeping. To fetch a trunk, look at the top peg. To store one, change the top peg. Nothing else in the room was written down anywhere.

The keeper was named He, and he was careful — careful nearly to the point of slowness. Nobody in town could find a flaw in how he retrieved a trunk:

First, look at the ledger. Top peg is seven. Second, look at the slip on the trunk hanging on peg seven. It says: below me is peg twelve. Third, lift trunk seven down and hand it to the customer. Fourth, write the top peg in the ledger as twelve.

That middle step — reading the slip — required carrying the trunk to the light by the window, because the slips were often rain-blurred. Carrying it took a while.

Keeper He ran the hut alone for twenty years without a single mistake. What finally broke the hut was that he took on an apprentice.

The apprentice was named Shao: quick-handed, and he’d have liked to unhook three trunks with one hand if he could. He had worried about it at first, then decided it was fine — two people, one lifting trunks and one reading slips, each doing a separate step, neither touching the other’s work. Surely that was twice as fast.

It was not. Two people’s speed meant splitting one thing that had to happen in one piece into two halves done by two people, with a stretch in the middle that nobody was watching.

The day it happened was market day.

Keeper He was at the window with a trunk in his arms reading its slip. Trunk seven, slip says: below me is peg twelve.

Shao was working at the same time. The old woman from West Street came for trunk seven, and Shao unhooked it and handed it over, neat as you like. The owner of trunk twelve — the one beneath it — arrived too, and Shao unhooked that one and handed it over as well. Both trunks gone; pegs seven and twelve now empty.

Immediately after, a porter with a carrying pole wanted to store a trunk. Two pegs out of eighty stood empty, and by the hut’s old rule, freed pegs were recycled at once and renumbered on the spot — so the porter’s trunk went onto that freshly emptied peg seven, and became the topmost thing on the wall. Below it hung peg three.

That was when Keeper He looked up from the window. He had the slip clear in his mind: below me is peg twelve.

He checked the ledger — that thought between his second step and his fourth — and the ledger still read “top peg: seven.”

He relaxed. No change. Nobody had touched a thing.

So he lifted the trunk off peg seven, handed it to the customer holding a claim ticket, and solemnly wrote the top peg down as twelve.

Three things happened at once, and at the time nobody knew which three:

One: the customer did not walk out with his own trunk, but with the porter’s. The claim ticket matched — the ticket said “seven.” Two: the ledger’s top peg now pointed at twelve, and peg twelve was empty. The next person to fetch a trunk would be led to a bare wall. Three: the chain starting at peg seven no longer had anything to do with the chain written in the ledger.

By afternoon the hut was in ruins. Someone was handed an empty peg. Someone got another man’s trunk. Somebody’s trunks fell off the wall — because an apprentice followed the ledger to unhook a trunk that “existed,” slipped, and brought three of them down together.

Keeper He sat against the wall with the ledger on his knees and read it all night.

What he could not work out was not who was wrong. Neither was wrong. He had followed the rules: read the ledger, read the slip, changed the ledger. Shao had followed the rules: unhooked the customer’s trunk, recycled the free pegs. What was wrong was the gap — between the moment he read the ledger and the moment he wrote it, he spent time carrying a trunk to the window. During that time the wall was changed, and changed back to the way it looked.

The next morning he called everyone to the wall and said three things. Those three were later carved on a board above the door.

One: “still peg seven” is not enough. You need “which peg seven.”

He had the carpenter cut a shallow notch into every peg, deepened each time the peg took a new trunk, tallied in strokes like the character for five. A notch cannot be erased, only added. From then on the ledger would not read “top peg: seven,” but “top peg: seven, forty-first stroke.”

Look again with that in place. While he carried the trunk to the window, the ledger read “seven, forty-first stroke.” When he came back it read “seven, forty-seventh stroke” — the same seven, but seven had turned over six times. He could see at a glance: the wall I looked at is not the wall this is.

The town called the notch “one more stroke.” Keeper He said that stroke was worth more than the peg.

Two: what you are looking at may not be taken away.

He added a row of wooden clips to the wall. Whoever carried a trunk to the window clipped the trunk, and the trunk under it, first. A clipped peg could not be reused. The rule was simple: an account being read aloud may not be edited.

At first people said it was wasteful. On market day, seventeen of eighty pegs were clipped at once, and later customers had to hang their trunks higher. Keeper He said only this: leave the pegs free, and a customer walks a few extra steps. Let a free peg be taken, and a customer walks off with the wrong trunk. The extra steps, I will answer for. The wrong trunk, who will answer for?

Three: free pegs are not recycled at once. Wait one round.

This was the easiest to do and the hardest to accept. A freed peg would not be renumbered that day. Only after every customer on the wall had gone through a full round would it return to the usable pile and take a new number. That way, any “seven” in somebody’s hand would not become somebody else’s seven while he held it.

The cost was pegs standing idle on the wall. Keeper He said an idle peg is rent, not waste.

Later the hut ran into fresh trouble.

The wall held more than eighty pegs — on market days extra ones were added, and their numbers were grabbed from a heap of old wooden tags, whichever came up. Some tags dragged out of that heap had their tallies fully carved, and turned over, still read seven. Keeper He thought little of it at first: same number, same kind of peg. Then one year a trunk went out on “seven, forty-first stroke” — identical to a tag retired four years earlier. He carried it to the window, read the slip, checked the ledger, and it matched perfectly. He handed over another man’s trunk.

That day he collected every retired tag into a camphor chest and pasted a paper to its lid: a tag whose tally is full does not go out again.

The town’s own summary of the hut was sharper than Keeper He’s:

One: a number in the ledger does not count. A number plus its tally counts. Two: a number in your hand may not change before you let go of it. Three: a number that cannot change must not be handed out.

By now you have probably recognized it: this is the ABA problem in lock-free data structures.

What it is

Start with the instruction. Every CAS (compare-and-swap) — x86’s LOCK CMPXCHG, ARM’s LDXR/STXR, C++’s std::atomic<T>::compare_exchange_weak — does exactly one thing: “if the value at this address is still X, write Y and report success; otherwise do nothing and report failure.” It compares a value, not a history.

That is the whole problem. A value can change, and it can change back.

The classic site, a lock-free stack:

// top is the stack head; each node carries its own next
Node *pop(void) {
    Node *old_top = top;           // 1: read top == A
    Node *next    = old_top->next; // 2: read A->next == B
    // ...here we may be preempted, or merely slowed (cache miss, page fault, a debugger breakpoint)
    return CAS(&top, old_top, next) ? old_top : retry(); // 3
}

Between 2 and 3, another thread does three things: pop()s A, pop()s B, and then — because B was freed and its memory reused — push()es A back on top (or a new node that happens to land at A’s address).

Now top equals A again. The CAS at 3 succeeds, because what it sees is A. So the code sets the head to next — which is B, already popped and possibly already freed.

Two consequences, both bad:

• Lost data. The head now points to a node no longer in the stack, and every element below it loses its last reference. Permanent leak.
• Dangling pointers. If that memory went back to the allocator and was reused elsewhere, the chain is a row of wild pointers, and walking it is a use-after-free.

Note what this is not: it is not a race that produced a stale read. Every read returned the true value of its moment. What broke was treating “same value” as “same state.” A value that goes A→B→A is indistinguishable from an unchanged one to a CAS. That is ABA.

Three standard fixes, matching the hut’s three sentences:

1. Attach a counter to the value (tagged pointer / version). Compare pointer and version together, via double-width CAS (cmpxchg16b, cmpxchg8b) or by packing a version into high pointer bits. When A comes back the version has moved, and the CAS fails. That is the notch.
   • The key detail: the version wraps. A 32-bit counter with a 64-bit pointer needs 2³² modifications to reproduce the same (pointer, version) pair — fine in practice. Do not gamble on an 8-bit version. That is not safety, it is a probability.
2. Do not let what you are looking at be taken away (safe memory reclamation). The version fixes the head pointer; the node being freed and reused is the deeper hole. Three engineering answers:
   • Hazard pointers: a thread publishes “I am looking at this pointer,” and reclaimers skip anything hazarded. That is the wooden clip.
   • Epoch / QSBR (quiescent-state-based reclamation): defer reclamation until every thread has passed a quiescent point. That is “wait one round.”
   • Garbage collection (Java’s AtomicReference, Go’s GC): memory is not yours to free, so ABA reduces to the pointer layer, and stamped references like AtomicStampedReference cover it.
3. Do not hand out identifiers that can come back renovated. When reusing memory, make the old value not equal the new one — and where that is physically impossible, route around it with the two mechanisms above instead of pretending it cannot happen.

Where this bites in the real world: Java’s AtomicInteger.compareAndSet in a lock-free stack is the textbook ABA (hence AtomicStampedReference); in C, malloc() returning the address you just free()d is the common case, not the exception (glibc’s tcache all but guarantees it); in the kernel, slab reclamation goes through RCU plus refcounts and dodges ABA entirely; and MVCC version numbers in databases are the same idea pointed the other way.

Why it matters

Because this is the kind of bug that tests never catch, a load test passes every time, and production hits three months in.

• It needs exact timing, and the window is tiny. Step 2 to step 3 is usually a handful of instructions. Triggering it requires a preemption at precisely that spot and another thread completing push/pop/push inside the window. Ten thousand runs locally: nothing. A full load test: nothing. Production, once in thirty million operations.
• It reports no error, only damage. CAS returns true. The logs are all successes. The stack looks like it works — push increments the size, pop returns something, it is just the wrong something, or the back half of the chain is gone. It surfaces as “memory grows slowly” and “data occasionally missing,” the two hardest symptoms to attribute.
• Better tooling can make it disappear. AddressSanitizer and TSan catch some of the UAF, but they change timing and may make the ABA unobservable. This is why lock-free code gets model checkers: CDSChecker, GenMC, Loom for Rust and Go.
• It hides inside a performance motive. Moving from a mutex to lock-free is usually a decision made under pressure, and refactors made under pressure most often skip the reclamation layer. A lock’s protected range is explicit (lock to unlock). A lock-free loop’s protected range is implicit — it is the gap inside every read-compute-write triple.

Engineering trade-offs, ordered by payoff:

1. Ask first whether you need lock-free at all. Lock-free buys “no thread is ever parked”; it pays with readability and verifiability. Channels, a plain mutex, per-thread local structures, and sharded locks may solve the problem; if they do, do not write a CAS loop. That is not conservatism, it is trading risk for certainty.
2. If you write a CAS loop, write the reclamation policy in the same commit. They are two halves of one thing. Do not ship half and think about the other later.
3. Do not hand-roll; start from the standard containers. Go’s sync.Map / atomic.Pointer (GC-backed), Java’s java.util.concurrent, Rust’s crossbeam (epoch reclamation built in, which is exactly the wooden tag). Those libraries exist for one reason: somebody already stepped in this row of holes.

And the metaphor itself. Keeper He was not careless. He confused “still peg seven” with “still the same trunk.” Of all the concurrency bugs, this one is hardest to prevent, because it does not come from inattention — it comes from a perfectly reasonable assumption that fails only at a vanishingly small fraction of moments.

The board’s third line is the valuable one: a number that cannot change must not be handed out.

Metaphor mapping

• Eighty pegs strung into a chain → the node chain of a lock-free stack
• “Top peg: seven” on the ledger’s first page → the atomic head pointer top
• The slip reading “below me is peg twelve” → each node’s next pointer
• Keeper He’s four-step retrieval → pop(): read top, read next, CAS, retry loop
• Carrying the trunk to the window to read the slip → the window between the second read and the CAS (preemption, cache miss, page fault)
• Shao unhooking both seven and twelve → another thread popping A and then B
• Pegs recycled and renumbered at once → popped memory free()d and immediately reused by the allocator
• The porter’s trunk rehung on peg seven → the same value A reappearing at the same address
• The ledger still reading “seven,” so He relaxed → CAS seeing an unchanged value and succeeding
• Top peg set to twelve, and twelve is empty → head set to an already-popped, possibly freed B; the chain breaks
• A customer getting the wrong trunk with a matching claim ticket → the program receives a wrong object of the right type, with no exception and no log
• Someone handed an empty peg; trunks falling off the wall → next is now dangling; traversal reads garbage
• “Two people, one step each, twice as fast” → splitting a critical section across two threads, leaving a stretch nobody guards
• “Not just which seven, but which peg seven” → tagged pointer / version, compared with double-width CAS on (pointer, version); when A returns, the version has moved
• Notches that can only be added, never erased → the version is monotonic and does not roll back with business state
• Tallies filling up and turning over → version wrap: bit width sets the safety boundary, not logic
• A full tag never going out again → on reuse, the old value must not equal the new one; where it must, route around it with reclamation
• Wooden clips forbidding a clipped peg’s reuse → hazard pointers: a thread publishes the pointer it is accessing
• “An account being read aloud may not be edited” → a hazarded node cannot be reclaimed even after it leaves the chain
• Free pegs waiting one round → epoch / QSBR deferred reclamation after a quiescent point
• Idle pegs as rent, not waste → delaying reclamation buys correctness at the cost of memory
• Market-day tags grabbed from the old pile → tcache / slab reuse almost always returns the address just freed
• The retired “seven, forty-first stroke” tag going out again → the version wrapped, so (pointer, version) genuinely repeated and CAS was fully fooled
• The camphor chest marked “a full tag does not go out again” → an undersized version field is a probability mechanism, never a safety mechanism
• The town’s three lines: number plus tally counts; a number in hand may not change; an unchanging number must not go out → versioned compare, safe reclamation, never expose a reusable old value
• Twenty flawless years, then a failure on the apprentice’s first day → single-threaded code has no ABA; it appears only under real concurrency, which is why load tests and local repro rarely hit it
• “Two people, one step each, neither touching the other’s work” → the intuitive pull of lock-free code, and its hidden cost: a lock’s protected range is explicit, a CAS loop’s is implicit