Lock-Free Programming and Memory Reclamation¶

Where this fits¶

Memory Model and Atomics covers atomic operations and ordering. This page covers what you build with them — lock-free data structures — and the problem that dominates their design everywhere: when is it safe to reuse a node that other threads might still be reading? In Go, the garbage collector answers that question for ordinary memory, which makes lock-free code dramatically simpler — until you start recycling memory yourself. Then every classic problem comes back, as measured below.

Measurements: Go 1.26.4, Apple M1 Pro, 8 goroutines.

Progress guarantees¶

"Lock-free" is a progress property, not a speed claim. An uncontended sync.Mutex costs about 13 ns; a lock-free structure under contention retries its CAS repeatedly and bounces cache lines just as badly. The real benefits are narrower: readers that never block behind a writer (critical for tail latency), and no deadlocks or priority inversion.

The basic tool: a CAS loop¶

A Treiber stack is the simplest lock-free structure: a singly linked list whose head is updated with compare-and-swap.

type node struct {
    value int64
    next  atomic.Pointer[node]
}

type Stack struct{ head atomic.Pointer[node] }

func (s *Stack) Push(v int64) {
    n := &node{value: v}
    for {
        old := s.head.Load()
        n.next.Store(old)
        if s.head.CompareAndSwap(old, n) {
            return
        }
        // Another goroutine changed head between Load and CAS: retry.
    }
}

func (s *Stack) Pop() (int64, bool) {
    for {
        old := s.head.Load()
        if old == nil {
            return 0, false
        }
        next := old.next.Load()
        if s.head.CompareAndSwap(old, next) {
            return old.value, true
        }
    }
}

Push builds the node privately, points it at the current head, and tries to swing head to it; if another goroutine changed head in the meantime, the CAS fails and it retries. The atomic store of head publishes the node's contents to any goroutine that later loads it.

The hidden dependency: no node is reused while it is referenced¶

Look at Pop between loading old and the CAS. Another goroutine can pop old in that window. In Go that is harmless: this goroutine still holds a pointer to old, so the garbage collector will not free it, and no new node can be allocated at the same address while old is reachable. The CAS then fails (head moved on) and the loop retries.

Remove that guarantee and the stack breaks. Here is the same stack with one "optimization": popped nodes go into a sync.Pool and Push reuses them, to avoid allocating.

func (s *PooledStack) Pop() (int64, bool) {
    for {
        old := s.head.Load()
        if old == nil {
            return 0, false
        }
        next := old.next.Load() // may be stale if old is recycled before our CAS
        if s.head.CompareAndSwap(old, next) {
            v := atomic.LoadInt64(&old.value)
            s.pool.Put(old) // recycle: the node may be pushed again immediately
            return v, true
        }
    }
}

8 goroutines each push and pop 200,000 unique values; afterwards every value must have been popped exactly once:

The recycled version is 2.4x faster and corrupts more than half the data. This is the ABA problem:

head → A → B → C

G1: old = A, next = B, ...descheduled before its CAS
G2: Pop() → removes A, recycles it          head → B → C
G2: Pop() → removes B, recycles it          head → C
G2: Push(X) → gets A's node from the pool    head → A(X) → C
G1: resumes: CAS(head, expected=A, desired=B) → SUCCEEDS (head is "A" again)
                                             head → B   ← B is a recycled node: lost
                                                          values, duplicates, cycles

The CAS compares addresses, and the address came back with a different meaning. Neither the race detector nor the type system can help: every access is atomic, so there is no data race — only a logic race. The GC version passes the same test under -race with zero anomalies.

The general rule: the moment you reuse memory yourself — a free list, sync.Pool, a slab or arena, an mmaped region, offsets into a big []byte — you take over the job the GC was doing, and need one of the reclamation schemes below.

Approach 1: tagged pointers (ABA only)¶

Pair the pointer with a counter that increments on every change and CAS both together: in Go, pack an index into a slab plus a version into one uint64 and use atomic.Uint64.CompareAndSwap. The recycled A now has a different version, so G1's CAS fails. This fixes ABA but not use-after-reuse: G1 still read A.next after A was reused. It is only safe when that stale read is harmless (as in a slab of plain values that are never freed back to the OS).

Approach 2: reference counting¶

Each node carries an atomic count of goroutines currently using it; reuse it at zero. The difficulty is that you must increment the count of a node you reached through a pointer that may already be stale — and every read operation writes a shared counter, destroying read scalability. Rarely the right tool for a hot path; the right tool for coarse objects such as SSTables and memtables (one count per object, not per node).

Approach 3: hazard pointers¶

Each goroutine has a few hazard pointer slots — single-writer, multi-reader atomic pointers announcing "I am about to dereference this node; don't reuse it."

Reader (Pop):
  loop:
    n = head.Load()
    hazard[me].Store(n)                 // announce
    if head.Load() != n: continue       // re-validate: n may have been removed
                                        // before the announcement was visible
    next = n.next.Load()                // safe: n cannot be reused while announced
    if head.CompareAndSwap(n, next): break
  hazard[me].Store(nil)
  retire(n)

retire(n):
  add n to my retired list
  if the list is long: scan all hazard slots, recycle every retired node
  no slot points to, keep the rest

Memory held is bounded (a retired node waits only while a reader actually holds it), but every protected load costs an extra atomic store and re-check. Goroutines are not pinned to threads, so in Go the slots are usually per-P or handed out from a pool.

Approach 4: epoch-based reclamation (EBR)¶

Instead of protecting individual pointers, readers announce that they are inside a critical section during an epoch.

globalEpoch: atomic counter
per reader:  localEpoch, active flag
retired lists: one per epoch (only three needed: e, e-1, e-2)

Enter():     active = true; localEpoch = globalEpoch
Exit():      active = false
Retire(p):   add p to the retired list for the current global epoch
TryAdvance():
  if every ACTIVE reader's localEpoch == globalEpoch:
    globalEpoch += 1
    recycle everything retired two epochs ago   // no reader can still see it

The unbounded-memory risk of EBR is the same failure mode as a long-running snapshot in a storage engine, or a leaked iterator: one slow reader holds back reclamation for everyone.

Approach 5: RCU (read-copy-update)¶

RCU is the Linux kernel's version of the idea, optimized for read-mostly data. Readers do nothing but mark a read-side critical section (in the kernel, often just disabling preemption — zero atomics). Writers copy the data, modify the copy, publish it by swapping one pointer, then wait for a grace period — until every CPU has passed through a quiescent state — and free the old copy.

In Go, the publish half is idiomatic and the reclaim half is free:

var cfg atomic.Pointer[Config]

func handle() { c := cfg.Load(); use(c) } // readers: one atomic load, never block

func update(change func(*Config)) {        // writers (serialized by a mutex)
    next := cfg.Load().Clone()
    change(next)
    cfg.Store(next)                         // publish; the GC frees the old version
}                                           // once the last reader drops it

How storage engines solve it¶

Engines mostly avoid per-node reclamation by reclaiming in bulk at a coarse granularity:

The common thread: make reads touch immutable data, publish new versions by swapping one pointer, and free old versions in batches once a cheap check proves no reader can see them.

Testing lock-free code¶

• go test -race reports data races on the non-atomic data around atomics — but, as the pooled stack shows, a pure ABA bug has no data race. Check results, not only races: count, sum, or compare against a model.
• Stress with more goroutines than cores (-cpu=1,2,8,32), so goroutines are preempted in the middle of CAS loops — the interleavings that expose ABA.
• Guard checks against corruption that loops forever: the first run of the pooled-stack test hung, because ABA had turned the list into a cycle and draining it never ended. The test now caps the drain and reports cycle=true.
• Test on ARM as well as x86: x86's stronger ordering hides some bugs (Memory Model and Atomics).
• For a new algorithm, model-check the design (TLA+, or exhaustive interleaving of a tiny instance) before trusting stress tests.

Common pitfall¶

Adding a free list to a lock-free structure "because the profile shows allocations". The structure was correct only because the GC guaranteed that no node is reused while anyone references it; the free list silently removes that guarantee. Tests with low contention pass, the benchmark improves by 2–3x, and under production load values vanish and reappear. If allocation really is the bottleneck, reduce it without reuse races — allocate nodes in batches (a slice of nodes handed out one by one and never recycled), shard the structure, or switch to a mutex-protected design whose free list is safe because the lock orders every reuse.

Review questions¶

1. What does "lock-free" guarantee, and why is it not a performance claim?
2. Why is the GC-based Treiber stack safe even though another goroutine can pop a node while this one is between Load and CompareAndSwap?
3. Walk through the ABA sequence that corrupted the sync.Pool version. Why did -race not report it?
4. Compare hazard pointers and epoch-based reclamation: read cost, memory bound, failure mode.
5. Why do storage engines reclaim at the granularity of a memtable or version rather than per node?