467 Fundamental

Epoch-Based Garbage Collection

Functional Programming

Tutorial

The Problem

Lock-free data structures remove nodes without a lock, but cannot immediately free the memory: another thread may still be traversing the node. Reference counting (like Arc) adds atomic overhead to every access. Epoch-based reclamation (EBR), introduced by Fraser (2004) and popularised by the crossbeam-epoch crate, solves this by grouping time into epochs. A thread "pins" its current epoch before reading, then unpins after. Memory retired in epoch E is only freed when every thread has advanced past E, guaranteeing no live references remain.

🎯 Learning Outcomes

• Understand why safe deallocation in lock-free code requires more than a simple free

• Model the epoch counter with AtomicU64 and Acquire/Release ordering

• Track pinned epochs to compute the safe-to-free threshold

• Implement retire (mark for deferred free) and collect (advance epoch and reclaim)

• Distinguish EBR from hazard pointers and reference counting

Code Example

//! Epoch-based garbage collection concept.
//!
//! Demonstrates deferred reclamation: retired values are tagged with the
//! current global epoch and are only reclaimed once the epoch has advanced
//! past any reader that might still observe them.

use std::sync::Mutex;

/// A value retired at a particular epoch, awaiting safe reclamation.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Retired<T> {
    /// The retired value.
    pub value: T,
    /// Epoch at which the value was retired.
    pub epoch: u64,
}

/// A simple epoch-based reclamation manager.
pub struct EpochGc<T> {
    state: Mutex<State<T>>,
}

struct State<T> {
    global_epoch: u64,
    retired: Vec<Retired<T>>,
}

impl<T> Default for EpochGc<T> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T> EpochGc<T> {
    /// Creates a new manager at epoch `0` with no retired values.
    pub fn new() -> Self {
        Self {
            state: Mutex::new(State {
                global_epoch: 0,
                retired: Vec::new(),
            }),
        }
    }

    /// Retires `value` at the current global epoch.
    pub fn retire(&self, value: T) {
        let mut state = self.state.lock().expect("epoch gc mutex poisoned");
        let epoch = state.global_epoch;
        state.retired.push(Retired { value, epoch });
    }

    /// Advances the global epoch by one and returns the new epoch.
    pub fn advance(&self) -> u64 {
        let mut state = self.state.lock().expect("epoch gc mutex poisoned");
        state.global_epoch += 1;
        state.global_epoch
    }

    /// Returns the current global epoch.
    pub fn epoch(&self) -> u64 {
        self.state
            .lock()
            .expect("epoch gc mutex poisoned")
            .global_epoch
    }

    /// Returns the number of retired values still pending reclamation.
    pub fn retired_len(&self) -> usize {
        self.state
            .lock()
            .expect("epoch gc mutex poisoned")
            .retired
            .len()
    }

    /// Reclaims all retired values whose epoch is strictly less than
    /// `min_safe_epoch` and returns them in retirement order.
    pub fn collect(&self, min_safe_epoch: u64) -> Vec<Retired<T>> {
        let mut state = self.state.lock().expect("epoch gc mutex poisoned");
        let retired = std::mem::take(&mut state.retired);
        let (safe, keep): (Vec<_>, Vec<_>) =
            retired.into_iter().partition(|r| r.epoch < min_safe_epoch);
        state.retired = keep;
        safe
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn retire_tracks_current_epoch() {
        let gc: EpochGc<&'static str> = EpochGc::new();
        gc.retire("a");
        gc.advance();
        gc.retire("b");

        assert_eq!(gc.retired_len(), 2);
        assert_eq!(gc.epoch(), 1);
    }

    #[test]
    fn collect_reclaims_only_older_epochs() {
        let gc: EpochGc<&'static str> = EpochGc::new();
        gc.retire("e0-a");
        gc.retire("e0-b");
        gc.advance();
        gc.retire("e1-a");

        let reclaimed = gc.collect(1);
        assert_eq!(reclaimed.len(), 2);
        assert!(reclaimed.iter().all(|r| r.epoch == 0));
        assert_eq!(gc.retired_len(), 1);
    }

    #[test]
    fn collect_zero_reclaims_nothing() {
        let gc: EpochGc<i32> = EpochGc::new();
        gc.retire(10);
        gc.retire(20);

        let reclaimed = gc.collect(0);
        assert!(reclaimed.is_empty());
        assert_eq!(gc.retired_len(), 2);
    }

    #[test]
    fn advance_returns_new_epoch() {
        let gc: EpochGc<()> = EpochGc::new();
        assert_eq!(gc.advance(), 1);
        assert_eq!(gc.advance(), 2);
        assert_eq!(gc.epoch(), 2);
    }

    #[test]
    fn scenario_matches_ocaml_example() {
        let gc: EpochGc<&'static str> = EpochGc::new();
        gc.retire("node-A");
        gc.retire("node-B");
        gc.retire("node-C");
        assert_eq!(gc.epoch(), 0);
        assert_eq!(gc.retired_len(), 3);

        assert_eq!(gc.advance(), 1);
        let reclaimed = gc.collect(1);
        assert_eq!(reclaimed.len(), 3);
        assert_eq!(gc.retired_len(), 0);
    }
}

(* 467. Epoch GC concept – OCaml *)
(* OCaml has a GC; this demonstrates the concept of deferred reclamation *)

type 'a retired = { value: 'a; epoch: int }

let global_epoch = ref 0
let retired_list : 'a retired list ref = ref []
let mutex = Mutex.create ()

let retire v =
  Mutex.lock mutex;
  let e = !global_epoch in
  retired_list := { value=v; epoch=e } :: !retired_list;
  Mutex.unlock mutex

let collect min_safe_epoch =
  Mutex.lock mutex;
  let (safe, keep) = List.partition (fun r -> r.epoch < min_safe_epoch) !retired_list in
  retired_list := keep;
  Mutex.unlock mutex;
  Printf.printf "reclaiming %d objects\n" (List.length safe)

let advance () =
  Mutex.lock mutex; incr global_epoch; Mutex.unlock mutex

let () =
  retire "node-A"; retire "node-B"; retire "node-C";
  Printf.printf "retired 3, epoch=%d\n" !global_epoch;
  advance ();
  Printf.printf "advanced to epoch=%d\n" !global_epoch;
  collect 1;  (* safe epoch: reclaim anything from epoch < 1 *)
  Printf.printf "remaining: %d\n" (List.length !retired_list)

Key Differences

Memory model: Rust requires explicit AtomicU64 with ordering annotations; OCaml's Atomic module provides sequentially consistent operations by default, hiding the ordering complexity.

Manual vs. automatic GC: Rust demands explicit EBR because the borrow checker does not track concurrent pointer lifetimes across thread boundaries; OCaml's GC handles ordinary heap objects automatically.

Mutex necessity: Rust uses Mutex<VecDeque> for the retire list because there is no GC-assisted write barrier; OCaml would use a domain-local list to avoid cross-domain locking.

**unsafe boundary**: Rust's actual lock-free structures require unsafe for raw pointer dereference; OCaml's type system prevents raw pointer arithmetic entirely.

OCaml Approach

OCaml's garbage collector handles memory automatically, so EBR is not required in pure OCaml code. For C bindings or Bigarray-allocated memory, manual tracking is necessary. The Domainslib library for Multicore OCaml uses domain-local state to track safe points, analogous to pin/unpin:

(* Conceptual OCaml EBR sketch *)
let epoch = Atomic.make 0
let pinned = Domain.DLS.new_key (fun () -> ref (-1))

let pin () =
  let e = Atomic.get epoch in
  !(Domain.DLS.get pinned) <- e; e

let unpin () =
  !(Domain.DLS.get pinned) <- -1

Full Source

//! Epoch-based garbage collection concept.
//!
//! Demonstrates deferred reclamation: retired values are tagged with the
//! current global epoch and are only reclaimed once the epoch has advanced
//! past any reader that might still observe them.

use std::sync::Mutex;

/// A value retired at a particular epoch, awaiting safe reclamation.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Retired<T> {
    /// The retired value.
    pub value: T,
    /// Epoch at which the value was retired.
    pub epoch: u64,
}

/// A simple epoch-based reclamation manager.
pub struct EpochGc<T> {
    state: Mutex<State<T>>,
}

struct State<T> {
    global_epoch: u64,
    retired: Vec<Retired<T>>,
}

impl<T> Default for EpochGc<T> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T> EpochGc<T> {
    /// Creates a new manager at epoch `0` with no retired values.
    pub fn new() -> Self {
        Self {
            state: Mutex::new(State {
                global_epoch: 0,
                retired: Vec::new(),
            }),
        }
    }

    /// Retires `value` at the current global epoch.
    pub fn retire(&self, value: T) {
        let mut state = self.state.lock().expect("epoch gc mutex poisoned");
        let epoch = state.global_epoch;
        state.retired.push(Retired { value, epoch });
    }

    /// Advances the global epoch by one and returns the new epoch.
    pub fn advance(&self) -> u64 {
        let mut state = self.state.lock().expect("epoch gc mutex poisoned");
        state.global_epoch += 1;
        state.global_epoch
    }

    /// Returns the current global epoch.
    pub fn epoch(&self) -> u64 {
        self.state
            .lock()
            .expect("epoch gc mutex poisoned")
            .global_epoch
    }

    /// Returns the number of retired values still pending reclamation.
    pub fn retired_len(&self) -> usize {
        self.state
            .lock()
            .expect("epoch gc mutex poisoned")
            .retired
            .len()
    }

    /// Reclaims all retired values whose epoch is strictly less than
    /// `min_safe_epoch` and returns them in retirement order.
    pub fn collect(&self, min_safe_epoch: u64) -> Vec<Retired<T>> {
        let mut state = self.state.lock().expect("epoch gc mutex poisoned");
        let retired = std::mem::take(&mut state.retired);
        let (safe, keep): (Vec<_>, Vec<_>) =
            retired.into_iter().partition(|r| r.epoch < min_safe_epoch);
        state.retired = keep;
        safe
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn retire_tracks_current_epoch() {
        let gc: EpochGc<&'static str> = EpochGc::new();
        gc.retire("a");
        gc.advance();
        gc.retire("b");

        assert_eq!(gc.retired_len(), 2);
        assert_eq!(gc.epoch(), 1);
    }

    #[test]
    fn collect_reclaims_only_older_epochs() {
        let gc: EpochGc<&'static str> = EpochGc::new();
        gc.retire("e0-a");
        gc.retire("e0-b");
        gc.advance();
        gc.retire("e1-a");

        let reclaimed = gc.collect(1);
        assert_eq!(reclaimed.len(), 2);
        assert!(reclaimed.iter().all(|r| r.epoch == 0));
        assert_eq!(gc.retired_len(), 1);
    }

    #[test]
    fn collect_zero_reclaims_nothing() {
        let gc: EpochGc<i32> = EpochGc::new();
        gc.retire(10);
        gc.retire(20);

        let reclaimed = gc.collect(0);
        assert!(reclaimed.is_empty());
        assert_eq!(gc.retired_len(), 2);
    }

    #[test]
    fn advance_returns_new_epoch() {
        let gc: EpochGc<()> = EpochGc::new();
        assert_eq!(gc.advance(), 1);
        assert_eq!(gc.advance(), 2);
        assert_eq!(gc.epoch(), 2);
    }

    #[test]
    fn scenario_matches_ocaml_example() {
        let gc: EpochGc<&'static str> = EpochGc::new();
        gc.retire("node-A");
        gc.retire("node-B");
        gc.retire("node-C");
        assert_eq!(gc.epoch(), 0);
        assert_eq!(gc.retired_len(), 3);

        assert_eq!(gc.advance(), 1);
        let reclaimed = gc.collect(1);
        assert_eq!(reclaimed.len(), 3);
        assert_eq!(gc.retired_len(), 0);
    }
}

(* 467. Epoch GC concept – OCaml *)
(* OCaml has a GC; this demonstrates the concept of deferred reclamation *)

type 'a retired = { value: 'a; epoch: int }

let global_epoch = ref 0
let retired_list : 'a retired list ref = ref []
let mutex = Mutex.create ()

let retire v =
  Mutex.lock mutex;
  let e = !global_epoch in
  retired_list := { value=v; epoch=e } :: !retired_list;
  Mutex.unlock mutex

let collect min_safe_epoch =
  Mutex.lock mutex;
  let (safe, keep) = List.partition (fun r -> r.epoch < min_safe_epoch) !retired_list in
  retired_list := keep;
  Mutex.unlock mutex;
  Printf.printf "reclaiming %d objects\n" (List.length safe)

let advance () =
  Mutex.lock mutex; incr global_epoch; Mutex.unlock mutex

let () =
  retire "node-A"; retire "node-B"; retire "node-C";
  Printf.printf "retired 3, epoch=%d\n" !global_epoch;
  advance ();
  Printf.printf "advanced to epoch=%d\n" !global_epoch;
  collect 1;  (* safe epoch: reclaim anything from epoch < 1 *)
  Printf.printf "remaining: %d\n" (List.length !retired_list)

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn retire_tracks_current_epoch() {
        let gc: EpochGc<&'static str> = EpochGc::new();
        gc.retire("a");
        gc.advance();
        gc.retire("b");

        assert_eq!(gc.retired_len(), 2);
        assert_eq!(gc.epoch(), 1);
    }

    #[test]
    fn collect_reclaims_only_older_epochs() {
        let gc: EpochGc<&'static str> = EpochGc::new();
        gc.retire("e0-a");
        gc.retire("e0-b");
        gc.advance();
        gc.retire("e1-a");

        let reclaimed = gc.collect(1);
        assert_eq!(reclaimed.len(), 2);
        assert!(reclaimed.iter().all(|r| r.epoch == 0));
        assert_eq!(gc.retired_len(), 1);
    }

    #[test]
    fn collect_zero_reclaims_nothing() {
        let gc: EpochGc<i32> = EpochGc::new();
        gc.retire(10);
        gc.retire(20);

        let reclaimed = gc.collect(0);
        assert!(reclaimed.is_empty());
        assert_eq!(gc.retired_len(), 2);
    }

    #[test]
    fn advance_returns_new_epoch() {
        let gc: EpochGc<()> = EpochGc::new();
        assert_eq!(gc.advance(), 1);
        assert_eq!(gc.advance(), 2);
        assert_eq!(gc.epoch(), 2);
    }

    #[test]
    fn scenario_matches_ocaml_example() {
        let gc: EpochGc<&'static str> = EpochGc::new();
        gc.retire("node-A");
        gc.retire("node-B");
        gc.retire("node-C");
        assert_eq!(gc.epoch(), 0);
        assert_eq!(gc.retired_len(), 3);

        assert_eq!(gc.advance(), 1);
        let reclaimed = gc.collect(1);
        assert_eq!(reclaimed.len(), 3);
        assert_eq!(gc.retired_len(), 0);
    }
}

Exercises

Thread-local pinning: Replace Mutex<Vec<u64>> with thread_local! storage so pin/unpin do not contend on a shared mutex.

Batch retirement: Collect a thread-local retire list and only flush to the global queue on unpin, reducing mutex acquisitions.

Integration: Build a lock-free singly linked list that uses EpochMgr to retire removed nodes, verifying with Miri or loom that no use-after-free occurs.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust