A stack with one atomic pointer
The Treiber stack is the canonical introductory lock free structure. It is a singly linked list whose head pointer is atomic. Every operation is a CAS loop on that head.
Push
To push a node:
- Allocate the new node holding the value.
- Read the current head into a local snapshot.
- Point the new node next field at that snapshot.
- CAS head from the snapshot to the new node.
- On failure, re read head, re link next, and retry.
Pop
To pop:
- Read the current head snapshot; if null the stack is empty.
- Read the head next pointer to find the new top.
- CAS head from the snapshot to that next pointer.
- On success the popped node is detached and returned.
The lurking hazard
Pop reads head next before the CAS. If between the read and the CAS another thread pops this node, frees it, and pushes a recycled node back, head may again equal the snapshot while next is now stale. CAS succeeds wrongly. This is the ABA problem, and it is why a Treiber stack needs safe reclamation or tagged pointers.
Key idea
The Treiber stack drives push and pop through CAS loops on one atomic head pointer, which is elegant but exposes the ABA problem during pop.