A single atomic top
The Treiber stack is the textbook lock free stack. It keeps one atomic pointer to the top node. Both push and pop are loops that read the current top, prepare a change, and commit it with a single compare and swap, retrying when another thread wins the race.
Push and pop
- Push creates a new node, sets its next field to the current top, then compare and swaps top from the old value to the new node
- Pop reads the current top, reads its next field, then compare and swaps top from the old node to that next node, returning the old node's value
Because each operation commits with one atomic instruction, the stack never blocks and a stalled thread cannot stop others from progressing.
The reuse hazard
The pop path hides a famous trap. A thread reads top as node A and plans to swap to A's old next. If between those steps A is popped, freed, and a recycled allocation makes top point at A again, the compare and swap sees the expected A and succeeds wrongly, corrupting the stack. This is the reuse problem that motivates tagged pointers or hazard pointers.
Key idea
The Treiber stack pushes and pops with a single compare and swap on the top pointer, but its pop path is vulnerable to the reuse hazard.