Writing a lock-free queue from scratch

A compare-and-swap only checks a pointer's value — not its history. That gap is the ABA problem, and it's the reason a naive lock-free stack corrupts under contention.

The ABA problem

queue.rs

1loop {2    let head = self.head.load(Ordering::Acquire);3    let next = unsafe { (*head).next };  // danger lives here4    if self.head.compare_exchange(head, next, Acquire, Relaxed).is_ok() {5        break;6    }7}

🦀

Ferris' hot tip

If you free that node between the load and the compare_exchange, another thread can reuse the exact same address — same pointer value, totally different node. CAS says "looks fine!" and you've corrupted the queue. That's ABA.

Why tagging works

crossbeam attaches a generation counter to each pointer. The CAS now compares (pointer, tag) together, so a recycled address with a bumped tag fails the swap — exactly what we want.

Gotcha

Tagging needs spare bits in the pointer (alignment) or a double-width CAS. On 64-bit with 8-byte alignment you get 3 low bits for free — usually enough.

Takeaways

Lock-free ≠ wait-free. Our queue is lock-free; a thread can spin indefinitely if others keep succeeding.
ABA is silent — the code compiles and mostly works in tests.
Reach for crossbeam-epoch before rolling your own — which is exactly what the next post is about.