Feb 23, 2025

Epoch Adventures: Breaking Free from ABA in Concurrent Rust

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 to thread::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 of try_collect_garbage():While crossbeam automatically reclaims memory eventually, calling try_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 unpinned

Memory 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 1

Lock-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-free

Memory Reclamation Phases

Phase 1: Marking for Cleanup          Phase 2: Reclamation
┌─────┐     ┌─────┐                  ┌─────┐     ┌─────┐
│  A  │ ──> │  B  │                  │  A  │     │  B  │
└─────┘     └─────┘                  └─────┘     └─────┘
   ↑           ↑                         ↑           ↑
Active       Active                   Freed       Active
Thread1      Thread2                 Thread1     Thread2

Here’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: Better

Epoch-Based Reclamation

Memory per pointer: 8 bytes
Memory overhead: Variable
Cleanup delays: Deferred until safe
Cache utilization: More misses

The 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::new and converted to Shared
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::read is safe here as we own the value and move it out
defer_destroy will 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 guard keeps 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 next

These 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!