Freeing is the hard part
In a lock free structure, removing a node from the structure is the easy step. The hard question is when can you actually free its memory. Another thread may have read a pointer to that node a moment ago and be about to dereference it. Free too early and that thread reads freed memory, a use after free.
Why locks would have solved it
With a mutex, no other thread can be inside the structure while you remove and free. Lock free code has no such barrier, so the unlinking thread cannot know whether anyone still holds a reference.
The main techniques
- Hazard pointers each thread publishes the pointers it is currently using. Before freeing a node, a reclaimer scans all published hazard pointers, and defers the free if any thread still references it
- Epoch based reclamation threads announce an epoch on entry. A node retired in one epoch is freed only after every thread has advanced past it, proving no one can still hold an old reference
- Reference counting atomically counts holders and frees at zero, simple but with its own atomic overhead and cycles risk
- Read copy update readers proceed with no cost and writers wait for a grace period
Key idea
Lock free removal is easy but freeing is not, so hazard pointers, epochs, or RCU defer reclamation until no reader can reference the node.