Implement Epoch-Based Memory Reclamation for Lock-Free Data Structures

Safe Deletion in Lock-Free Structures

You cannot free a node while another thread may still read it through an old pointer. Epoch-based reclamation batches retired nodes and frees them only after every thread passes a global epoch boundary. Userspace RCU and Folly's hazptr variants solve the same problem.

Epoch Protocol

Each thread enters a critical section by recording the current epoch. Retire nodes to a per-thread list. Advance global epoch; when all threads observe epoch E, free nodes retired before E.

cCopy
Loading…

• Epoch counters must be wide enough to avoid wrap during delay
• Thread exit must publish final epoch snapshot
• Hazard pointers trade memory for simpler retirement rules
• Kernel RCU is the same idea with scheduler integration

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

• Trace first: walk one failing input step by step
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will add epoch reclamation to a lock-free stack so freed nodes are not reused too early. This exercise asks you to run a concurrent pop/push stress test without use-after-free.