Epoch Adventures: Breaking Free from ABA in Concurrent Rust
- Introduction
Introduction
In our previous post, we explored how to solve the ABA problem using tagged pointers. Today, we’ll dive into another powerful solution: epoch-based reclamation (EBR). This approach offers a different trade-off between complexity and performance, making it an excellent choice for many concurrent data structures.
📺 Series Overview
This is the second post in our three-part series on solving the ABA problem in Rust:
- ✅ Part 1: Tagged Pointers with Versioning – We covered how to pair pointers with version numbers
- 🎯 Part 2: Epoch-Based Reclamation – Today’s post on using epochs for safe memory management
- 📅 Part 3: Hazard Pointers – Coming soon: exploring hazard pointers
🎯 What is Epoch-Based Reclamation?
Epoch-based reclamation is a memory management technique that solves the ABA problem by ensuring memory isn’t reused while any thread might be accessing it. Instead of tracking individual pointers, EBR tracks “epochs” – periods during which threads may access shared data.
Key concepts:
- Epochs: Global time periods that threads can participate in
- Pinning: Threads “pin” themselves to the current epoch when accessing shared data
- Deferred Reclamation: Memory is only freed when no thread is in an epoch that could access it
⚙️ Implementation with crossbeam
Here’s our lock-free stack implementation using crossbeam’s epoch-based reclamation:
use crossbeam_epoch::{self as epoch, Atomic, Owned};
use crossbeam_utils::Backoff;
use std::fmt::Debug;
use std::ptr;
use std::sync::atomic::{AtomicUsize, Ordering};
use std::thread;
/// Error types that can occur during stack operations
#[derive(Debug, PartialEq)]
pub enum StackError {
/// Indicates that the stack has reached its maximum capacity
CapacityExceeded,
/// Indicates that the push operation failed after maximum retries
PushFailed,
}
/// A node in the lock-free stack
///
/// Each node contains a value and an atomic pointer to the next node.
struct Node<T> {
/// The value stored in this node
value: T,
/// Atomic pointer to the next node in the stack
next: Atomic<Node<T>>,
}
/// A lock-free stack implementation using epoch-based memory reclamation
///
/// This implementation provides O(1) push and pop operations with strong
/// ABA prevention through epoch-based garbage collection.
///
/// # Type Parameters
/// * `T`: The type of values stored in the stack
///
/// # Examples
/// ```
/// use ebr_aba_protection::LockFreeStack;
///
/// let stack = LockFreeStack::new();
/// stack.push(1).unwrap();
/// assert_eq!(stack.pop(), Some(1));
/// ```
#[derive(Debug)]
pub struct LockFreeStack<T: Send + Sync + 'static> {
head: Atomic<Node<T>>,
size: AtomicUsize,
capacity: Option<usize>,
}
impl<T: Send + Sync + 'static> Default for LockFreeStack<T> {
fn default() -> Self {
Self::new()
}
}
impl<T: Send + Sync + 'static> LockFreeStack<T> {
/// Creates a new empty stack with unlimited capacity
pub fn new() -> Self {
Self {
head: Atomic::null(),
size: AtomicUsize::new(0),
capacity: None,
}
}
/// Creates a new empty stack with specified capacity
pub fn with_capacity(capacity: usize) -> Self {
Self {
head: Atomic::null(),
size: AtomicUsize::new(0),
capacity: Some(capacity),
}
}
/// Pushes a value onto the stack
///
/// # Arguments
/// * `value`: The value to push onto the stack
///
/// # Returns
/// * `Ok(())` if the push was successful
/// * `Err(StackError::CapacityExceeded)` if the stack is at capacity
/// * `Err(StackError::PushFailed)` if the push failed after maximum retries
///
/// # Safety
/// This operation is lock-free and thread-safe.
pub fn push(&self, value: T) -> Result<(), StackError> {
// Check capacity if set
if let Some(capacity) = self.capacity {
if self.size.load(Ordering::Relaxed) >= capacity {
return Err(StackError::CapacityExceeded);
}
}
let guard = epoch::pin();
let node = Owned::new(Node {
value,
next: Atomic::null(),
})
.into_shared(&guard);
let backoff = Backoff::new();
let mut attempts = 0;
const MAX_ATTEMPTS: u32 = 1000;
loop {
let head = self.head.load(Ordering::Relaxed, &guard);
unsafe {
(*node.as_raw()).next.store(head, Ordering::Release);
}
match self.head.compare_exchange(
head,
node,
Ordering::AcqRel,
Ordering::Acquire,
&guard,
) {
Ok(_) => {
self.size.fetch_add(1, Ordering::Relaxed);
return Ok(());
}
Err(_) => {
attempts += 1;
if attempts >= MAX_ATTEMPTS {
return Err(StackError::PushFailed);
}
backoff.spin();
if backoff.is_completed() {
thread::yield_now();
}
}
}
}
}
/// Removes and returns the top element from the stack
///
/// # Returns
/// * `Some(T)` if the stack was not empty
/// * `None` if the stack was empty
///
/// # Safety
/// This operation is lock-free and thread-safe.
pub fn pop(&self) -> Option<T> {
let guard = epoch::pin();
let backoff = Backoff::new();
let mut attempts = 0;
const MAX_ATTEMPTS: u32 = 1000;
loop {
let head = self.head.load(Ordering::Acquire, &guard);
match unsafe { head.as_ref() } {
Some(head_node) => {
let next = head_node.next.load(Ordering::Acquire, &guard);
if self
.head
.compare_exchange(head, next, Ordering::AcqRel, Ordering::Acquire, &guard)
.is_ok()
{
self.size.fetch_sub(1, Ordering::Relaxed);
unsafe {
guard.defer_destroy(head);
return Some(ptr::read(&(*head.as_raw()).value));
}
}
attempts += 1;
if attempts >= MAX_ATTEMPTS {
// If we've failed too many times, back off and try again
thread::yield_now();
attempts = 0;
}
backoff.spin();
}
None => return None,
}
}
}
/// Returns the current size of the stack
///
/// Note: Due to concurrent operations, the size may change
/// immediately after this call returns.
pub fn len(&self) -> usize {
self.size.load(Ordering::Relaxed)
}
/// Returns true if the stack is empty
pub fn is_empty(&self) -> bool {
self.len() == 0
}
/// Attempts to collect garbage from previous operations
///
/// This is an optimization that can be called periodically to
/// help manage memory usage.
pub fn try_collect_garbage(&self) {
let mut guard = epoch::pin();
guard.flush();
guard.repin();
guard.flush();
}
}
impl<T: Send + Sync + 'static> Drop for LockFreeStack<T> {
fn drop(&mut self) {
while self.pop().is_some() {}
}
}Additional Commentary on the Code
- Memory Orderings
Ordering::Relaxed: Often used for operations like size counting where strict ordering is unnecessary.Ordering::Acquire/Release: Ensures all reads/writes happen in the correct sequence when interacting with shared data. -Purpose of Backoff: The Backoff struct helps reduce contention in tight CAS loops. It starts with a small spin-wait, then escalates tothread::yield_now()when spinning is no longer effective. This adaptive strategy can prevent excessive CPU usage in high-contention scenarios while still giving good performance under moderate load. -Use oftry_collect_garbage():While crossbeam automatically reclaims memory eventually, callingtry_collect_garbage()can be beneficial if you know a large number of nodes are eligible for reclamation (e.g., after a burst of pops). This manual flush can help reclaim memory sooner and reduce peak usage in certain workloads.
🧐 How It Works
Epoch-based reclamation is built on three key mechanisms:
-
Epoch Tracking: Each thread declares when it’s accessing shared memory:
// Thread declares "I'm accessing shared memory" let guard = epoch::pin(); -
Safe Memory Access: The guard ensures memory won’t be freed while in use:
let head = self.head.load(Ordering::Acquire, &guard); -
Deferred Cleanup: Memory is freed only when we’re certain no thread can access it:
unsafe { // Will be freed when all older epochs complete guard.defer_destroy(head); }
The key difference from garbage collection is that EBR is entirely deterministic and manual:
- You explicitly mark when you start accessing shared memory
- You explicitly queue memory for cleanup
- Cleanup happens at well-defined points (when all threads exit an epoch)
- No runtime collector or heap scanning is involved
- All memory management follows Rust’s ownership rules
Here’s how memory flows through the system:
Memory Lifecycle in EBR:
┌──────────────┐ ┌──────────────┐ ┌──────────────┐
│ Active │ → │ Pending │ → │ Freed │
│ Memory │ │ Cleanup │ │ Memory │
└──────────────┘ └──────────────┘ └──────────────┘
↑ │ ↑
│ │ │
└─ Owned and └─ Waiting for │
in use epoch completion ──┘Epoch State Transitions
┌──────────────┐ Pin ┌──────────────┐
│ Inactive │ ──────────> │ Active │
└──────────────┘ └──────────────┘
▲ │
│ │
└───────────────────────────┘
Unpin & Collect
Epoch States:
- Inactive: Thread not accessing shared memory
- Active: Thread safely accessing shared memory
- Collection occurs when all threads unpinnedMemory Management Flow
Operation Timeline
┌─────────┐ ┌─────────┐ ┌─────────┐
│ Thread 1│ │ Thread 2│ │ Thread 3│
└────┬────┘ └────┬────┘ └────┬────┘
│ │ │
│ Pin(1) │ │
├────────────┤ │
│ Access │ Pin(1) │
│ Data ├────────────┤
│ │ Access │ Pin(1)
│ │ Data ├────────┐
│ Unpin │ │ Access │
├────────────┤ │ Data │
│ │ Unpin │ │
│ ├────────────┤ │
│ │ │ Unpin │
│ │ ├────────┘
│ │ │
Epoch 1 Epoch 1 Epoch 1Lock-Free Stack Operations with EBR
1. Initial State:
HEAD → [A] → [B] → [C]
Thread1: Active(1)
Thread2: Inactive
1. Thread1 Starts Pop:
HEAD → [A] → [B] → [C]
↑
Thread1
Thread1: Active(1)
Thread2: Inactive
1. Thread2 Becomes Active:
HEAD → [A] → [B] → [C]
↑
Thread1
Thread2: Active(1)
1. Thread1 Completes Pop:
HEAD → [B] → [C]
[A] → marked for deletion
Thread1: Inactive
Thread2: Active(1)
1. Memory Reclamation:
- [A] not freed until Thread2 unpins
- Ensures no use-after-freeMemory Reclamation Phases
Phase 1: Marking for Cleanup Phase 2: Reclamation
┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐
│ A │ ──> │ B │ │ A │ │ B │
└─────┘ └─────┘ └─────┘ └─────┘
↑ ↑ ↑ ↑
Active Active Freed Active
Thread1 Thread2 Thread1 Thread2Here’s a visualization of how memory reclamation happens concurrently:
Timeline Thread 1 Thread 2 Collection Status
─────────┬──────────────────────────────────────────────────────────────────────────────────
t=0 │ Pin epoch 1
│ Remove node A
│ Defer deletion A Pin epoch 1 [A] → marked for deletion
─────────┼──────────────────────────────────────────────────────────────────────────────────
t=1 │ Unpin Access data A still accessible to Thread 2
─────────┼──────────────────────────────────────────────────────────────────────────────────
t=2 │ Pin epoch 2 Unpin A cannot be freed (Thread 2 was in epoch 1)
─────────┼──────────────────────────────────────────────────────────────────────────────────
t=3 │ Access data Pin epoch 2 A can now be freed (no threads in epoch 1)
│ [Background cleanup occurs]
─────────┼──────────────────────────────────────────────────────────────────────────────────This demonstrates how:
- Memory is reclaimed only when safe (no threads in earlier epochs)
- Normal operations continue uninterrupted
- Cleanup happens automatically in the background
- No thread ever has to wait for memory reclamation
🧪 Testing
Here are tests that demonstrates how EBR prevents the ABA problem:
#[cfg(test)]
mod tests {
use super::*;
use crossbeam_epoch::Shared;
use std::sync::Arc;
use std::thread;
use std::time::Duration;
#[test]
fn test_stack_basic_operations() {
let stack = LockFreeStack::new();
assert!(stack.is_empty());
stack.push(1).unwrap();
stack.push(2).unwrap();
stack.push(3).unwrap();
assert_eq!(stack.len(), 3);
assert_eq!(stack.pop(), Some(3));
assert_eq!(stack.pop(), Some(2));
assert_eq!(stack.pop(), Some(1));
assert_eq!(stack.pop(), None);
}
#[test]
fn test_stack_capacity() {
let stack = LockFreeStack::with_capacity(2);
assert!(stack.push(1).is_ok());
assert!(stack.push(2).is_ok());
assert_eq!(stack.push(3), Err(StackError::CapacityExceeded));
assert_eq!(stack.pop(), Some(2));
assert!(stack.push(3).is_ok());
}
#[test]
fn test_stack_concurrent_operations() {
let stack = Arc::new(LockFreeStack::new());
let mut handles = vec![];
// Spawn multiple push threads
for i in 0..1000 {
let stack = Arc::clone(&stack);
handles.push(thread::spawn(move || {
stack.push(i).unwrap();
}));
}
// Spawn multiple pop threads
for _ in 0..500 {
let stack = Arc::clone(&stack);
handles.push(thread::spawn(move || {
stack.pop();
}));
}
for handle in handles {
handle.join().unwrap();
}
assert_eq!(stack.len(), 500);
}
#[test]
fn test_stack_concurrent_mixed_operations() {
let stack = Arc::new(LockFreeStack::new());
let mut handles = vec![];
for i in 0..10 {
let stack = Arc::clone(&stack);
handles.push(thread::spawn(move || {
for j in 0..100 {
if j % 2 == 0 {
stack.push(i * 100 + j).unwrap();
} else {
stack.pop();
}
}
}));
}
for handle in handles {
handle.join().unwrap();
}
}
#[test]
fn test_aba_prevention() {
let stack = Arc::new(LockFreeStack::new());
// Push initial values
stack.push(1).unwrap();
stack.push(2).unwrap();
let stack_clone = stack.clone();
// Thread 1: Try to pop and modify
let t1 = thread::spawn(move || {
let guard = epoch::pin();
let old_head = stack_clone.head.load(Ordering::Acquire, &guard);
thread::sleep(Duration::from_millis(100));
stack_clone
.head
.compare_exchange(
old_head,
Shared::null(),
Ordering::AcqRel,
Ordering::Acquire,
&guard,
)
.is_err()
});
// Thread 2: Modify the stack
thread::sleep(Duration::from_millis(50));
assert_eq!(stack.pop(), Some(2));
assert_eq!(stack.pop(), Some(1));
stack.push(3).unwrap();
assert!(t1.join().unwrap());
}
#[test]
fn test_garbage_collection() {
let stack = LockFreeStack::new();
// Push and pop many times to create garbage
for i in 0..1000 {
stack.push(i).unwrap();
}
for _ in 0..1000 {
stack.pop();
}
// Try to collect garbage
stack.try_collect_garbage();
// Verify stack is still usable
stack.push(42).unwrap();
assert_eq!(stack.pop(), Some(42));
}
}🔄 Comparison with Tagged Pointers
Let’s compare EBR with the tagged pointer approach from our previous post:
🎯 Design Philosophy
Tagged Pointers
- Version numbers track individual pointer changes
- Immediate memory reclamation
- Hardware-dependent (128-bit atomics)
- Local change tracking
Epoch-Based Reclamation
- Global epoch tracking
- Batched memory reclamation
- Hardware-independent
- Global synchronization state
💡 Implementation Complexity
| Aspect | Tagged Pointers | Epoch-Based Reclamation |
|---|---|---|
| Memory Management | Manual, immediate | Automatic, deferred |
| Pointer Size | Double-width required | Standard width |
| Platform Support | Limited (x86_64) | Universal |
| Debug/Maintenance | Simpler to trace | More complex state |
🔋 Resource Usage
Tagged Pointers
Memory per pointer: 16 bytes
Memory overhead: Fixed
Cleanup delays: None
Cache utilization: BetterEpoch-Based Reclamation
Memory per pointer: 8 bytes
Memory overhead: Variable
Cleanup delays: Deferred until safe
Cache utilization: More missesThe phrase “Cleanup delays: Deferred until safe” means that in epoch-based reclamation:
-
No Global Pauses: Unlike traditional garbage collected languages, EBR in Rust never needs to stop all threads at once.
-
Incremental Cleanup: Memory reclamation happens incrementally as part of normal operations:
- When threads unpin from an epoch
- When new operations begin
- During regular pointer operations
-
Background Reclamation: Deferred cleanup operations happen alongside normal program execution:
// When a node is removed, it's not immediately freed unsafe { guard.defer_destroy(head); // Queues for later cleanup // Program continues immediately, cleanup happens when safe } -
Zero Blocking: Operations never need to wait for memory reclamation - all operations proceed normally while cleanup happens in the background when it’s safe to do so.
🎮 Use Case Decision Matrix
| Requirement | Better Choice | Reason |
|---|---|---|
| Minimal memory usage | Tagged Pointers | No deferred cleanup |
| Cross-platform code | EBR | No hardware requirements |
| Predictable latency | Tagged Pointers | No epoch syncs |
| High throughput | EBR | Better scalability |
| Read-heavy workload | EBR | Lower read overhead |
| Write-heavy workload | Tagged Pointers | Immediate reclamation |
🛠 Migration Considerations
When migrating between approaches:
// From Tagged Pointers to EBR
- Replace AtomicTaggedPtr with Atomic<T>
- Add epoch::pin() calls
- Replace direct frees with defer_destroy
- Remove version tracking logic
// From EBR to Tagged Pointers
- Add version field to pointers
- Remove epoch pinning
- Replace defer_destroy with immediate free
- Add version increment logic🎯 Best Use Cases
Tagged Pointers Excel At:
- Low-latency trading systems
- Real-time control systems
- Embedded systems with constrained memory
EBR Excel At:
- Web services with many concurrent readers
- Distributed caches
- Long-running background services
🔬 Performance Analysis
Let’s dive into the real performance characteristics based on our benchmark results:
Note: Benchmark results are highly dependent on hardware configuration, operating system, CPU architecture, memory subsystem, and system load. Your results may vary significantly based on your specific environment.
Based on our concurrent_benchmarks.rs results:
| Operation | EBR Stack | Mutex Stack |
|---|---|---|
| Single Push | 42ns | 95ns |
| Concurrent Push (2T) | 85ns | 210ns |
| Concurrent Push (4T) | 120ns | 380ns |
| Concurrent Push (8T) | 180ns | 720ns |
| Memory Per Node | 16 bytes | 16 bytes |
| Memory Overhead | O(T*N) | O(N) |
Where T is the number of threads and N is the number of nodes.
🔒 Understanding the Safety of Unsafe Code
Our implementation uses several unsafe blocks. Let’s examine why each usage is actually safe:
- Node Creation and Modification
unsafe {
(*node.as_raw()).next.store(head, Ordering::Release);
}This is safe because:
- The node was just created via
Owned::newand converted toShared - We have exclusive access to the node at this point
- The node is still valid because we hold the epoch guard
- No other thread can access this node until we successfully link it
- Memory Access During Pop
unsafe {
guard.defer_destroy(head);
return Some(ptr::read(&(*head.as_raw()).value));
}This is safe because:
- We successfully performed the CAS operation, ensuring exclusive access
- The epoch guard ensures no other thread can free this memory
ptr::readis safe here as we own the value and move it outdefer_destroywill only free the memory when no thread can access it
- Reference Access
match unsafe { head.as_ref() } {
Some(head_node) => {
// ...
}
None => return None,
}This is safe because:
- The
guardkeeps the epoch active - No thread can free this memory while we hold the guard
- We check for null before dereferencing
🛡️ Safety Guarantees
The safety of our implementation relies on several key mechanisms:
- Epoch Protection
let guard = epoch::pin(); // Ensures memory safety- Prevents memory reclamation while threads are accessing data
- Guarantees no use-after-free can occur
- Automatically manages cleanup when safe
- Atomic Operations
self.head.compare_exchange(
head,
node,
Ordering::AcqRel, // Full fence for ownership transfer
Ordering::Acquire,
&guard,
)- Ensures thread-safe updates
- Prevents data races
- Maintains memory ordering guarantees
- Deferred Destruction
guard.defer_destroy(head); // Safe memory cleanup- Only frees memory when no thread can access it
- Managed by the epoch system
- Prevents dangling pointers
- Ownership Rules
- Each node is owned by exactly one location
- Ownership transfers are atomic
- Memory is properly aligned and initialized
These safety mechanisms work together to ensure our unsafe code is actually safe:
- Memory is never freed while in use
- Pointers are always valid when dereferenced
- Atomic operations maintain proper synchronization
- Resources are properly cleaned up
The unsafe blocks in our code are necessary for performance but don’t compromise safety thanks to:
- Careful management of epoch guards
- Proper use of atomic operations
- Strict adherence to Rust’s ownership rules
- Defensive programming with backoff and retry logic
🔍 Memory Ordering Guarantees
Our implementation uses specific memory orderings that are crucial for safety:
// In push():
self.head.load(Ordering::Relaxed, &guard) // Safe because we're in a CAS loop
(*node.as_raw()).next.store(head, Ordering::Release) // Ensures visibility of node data
self.head.compare_exchange(
head,
node,
Ordering::AcqRel, // Full fence for ownership transfer
Ordering::Acquire,
&guard,
)
// In pop():
self.head.load(Ordering::Acquire, &guard) // Ensures we see latest head
head_node.next.load(Ordering::Acquire, &guard) // Ensures we see latest nextThese orderings ensure that:
- Node construction is visible before the node becomes accessible
- No reads can be reordered before the guard is pinned
- All threads see a consistent view of ownership transfers
- Memory deallocation cannot occur while the guard is active
These guarantees, combined with the epoch-based reclamation, make our unsafe operations provably safe.
Caveats and Limitations of Epoch-Based Reclamation
- Memory Accumulation If a thread remains pinned for too long, memory that’s deferred for reclamation can build up, potentially causing higher memory usage.
- Global Epoch Overhead EBR relies on a global epoch counter; coordinating updates and cleaning up memory introduce some extra overhead in highly concurrent systems.
- Deferred Cleanup Spikes Because reclamation only occurs after all threads leave earlier epochs, memory usage can spike unpredictably under heavy loads.
- Real-Time Constraints The deferred nature of EBR may conflict with strict latency or worst-case memory usage requirements in real-time scenarios.
Despite these caveats, EBR remains a strong choice for many concurrent applications, especially those with numerous readers and where slight delays in memory reclamation are acceptable.
🔗 Resources
🤔 Final Thoughts
Epoch-based reclamation offers a robust solution to the ABA problem by ensuring memory safety through epochs rather than explicit version counting. While it may introduce some overhead from epoch tracking, it provides an excellent balance of safety, performance, and ease of use.
In our next post, we’ll explore hazard pointers, another fascinating approach to memory reclamation in concurrent programming.Stay tuned to learn how hazard pointers can offer even more fine-grained control over memory access patterns!