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

Topic Overview

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.

Your Task

A lock-free structure cannot free() a node the moment it unlinks it, because another thread may still hold a pointer it loaded a moment earlier. Epoch-based reclamation (EBR) solves this. Threads pin themselves to the current global epoch while touching shared nodes. Unlinked nodes are retired with the epoch they were retired in. The epoch advances only when every pinned thread has caught up, and a node retired in epoch e is freed once the global epoch reaches e + 2. At that point nobody can still hold it. Simulate EBR, including a stalled reader that blocks all reclamation.

Input

cCopy
Loading…

Threads and nodes are created on first mention. The global epoch starts at 0.

Rules

• advance fails if any pinned thread's recorded epoch differs from the global epoch: blocked: T is still pinned at epoch e, N nodes waiting names the first such thread in order of first appearance. Otherwise the epoch increments, the advancing thread (if pinned) moves with it, and every retired node whose retire epoch + 2 <= the new epoch is freed, in order of first mention.
• read:
  • a freed node gives USE AFTER FREE (X was freed);
  • otherwise, if the thread is not pinned: unsafe: not pinned (X may be freed at any moment);
  • otherwise ok, plus (retired, but still protected) if the node is retired.
• Errors: already pinned, not pinned, X was already retired / X was already freed, and unknown operation.

Output

cCopy
Loading…

Every command is echoed as T OP[ NODE]: before its result. state lists threads in order of first appearance, then retired nodes (none if there are none), then the total number freed.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Derive "safe to free" only from epochs (the retire epoch plus two). Never ask threads what they are reading.
2. Advance only when every pinned thread has observed the current epoch. That condition is what makes the +2 rule safe.

Hidden tests cover a stalled reader that holds many retired nodes back, re-pinning so the epoch can move on, several retirements in different epochs, reads outside a pinned section, retiring a node twice, double enter/exit, and unknown operations.