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

#![allow(clippy::all)]
// 467. Epoch-based garbage collection concept
use std::collections::VecDeque;
use std::sync::atomic::{AtomicU64, Ordering};
use std::sync::Mutex;

struct EpochMgr {
    epoch: AtomicU64,
    retired: Mutex<VecDeque<(u64, String)>>,
    pinned: Mutex<Vec<u64>>,
}

impl EpochMgr {
    fn new() -> Self {
        EpochMgr {
            epoch: AtomicU64::new(0),
            retired: Mutex::new(VecDeque::new()),
            pinned: Mutex::new(Vec::new()),
        }
    }
    fn pin(&self) -> u64 {
        let e = self.epoch.load(Ordering::Acquire);
        self.pinned.lock().unwrap().push(e);
        e
    }
    fn unpin(&self, e: u64) {
        let mut p = self.pinned.lock().unwrap();
        if let Some(i) = p.iter().position(|&x| x == e) {
            p.remove(i);
        }
    }
    fn retire(&self, desc: &str) {
        let e = self.epoch.load(Ordering::Relaxed);
        self.retired
            .lock()
            .unwrap()
            .push_back((e, desc.to_string()));
    }
    fn collect(&self) {
        let new_e = self.epoch.fetch_add(1, Ordering::AcqRel) + 1;
        let min_active = self
            .pinned
            .lock()
            .unwrap()
            .iter()
            .cloned()
            .min()
            .unwrap_or(new_e);
        let safe_before = min_active.saturating_sub(1);
        let mut r = self.retired.lock().unwrap();
        let mut n = 0;
        while r.front().map(|(e, _)| *e <= safe_before).unwrap_or(false) {
            let (_, d) = r.pop_front().unwrap();
            println!("  freed: {}", d);
            n += 1;
        }
        println!("epoch→{}; freed {}; deferred {}", new_e, n, r.len());
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_epoch_advances() {
        let m = EpochMgr::new();
        m.collect();
        assert_eq!(m.epoch.load(Ordering::SeqCst), 1);
    }
    #[test]
    fn test_retire() {
        let m = EpochMgr::new();
        m.retire("x");
        assert_eq!(m.retired.lock().unwrap().len(), 1);
    }
}

(* 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

#![allow(clippy::all)]
// 467. Epoch-based garbage collection concept
use std::collections::VecDeque;
use std::sync::atomic::{AtomicU64, Ordering};
use std::sync::Mutex;

struct EpochMgr {
    epoch: AtomicU64,
    retired: Mutex<VecDeque<(u64, String)>>,
    pinned: Mutex<Vec<u64>>,
}

impl EpochMgr {
    fn new() -> Self {
        EpochMgr {
            epoch: AtomicU64::new(0),
            retired: Mutex::new(VecDeque::new()),
            pinned: Mutex::new(Vec::new()),
        }
    }
    fn pin(&self) -> u64 {
        let e = self.epoch.load(Ordering::Acquire);
        self.pinned.lock().unwrap().push(e);
        e
    }
    fn unpin(&self, e: u64) {
        let mut p = self.pinned.lock().unwrap();
        if let Some(i) = p.iter().position(|&x| x == e) {
            p.remove(i);
        }
    }
    fn retire(&self, desc: &str) {
        let e = self.epoch.load(Ordering::Relaxed);
        self.retired
            .lock()
            .unwrap()
            .push_back((e, desc.to_string()));
    }
    fn collect(&self) {
        let new_e = self.epoch.fetch_add(1, Ordering::AcqRel) + 1;
        let min_active = self
            .pinned
            .lock()
            .unwrap()
            .iter()
            .cloned()
            .min()
            .unwrap_or(new_e);
        let safe_before = min_active.saturating_sub(1);
        let mut r = self.retired.lock().unwrap();
        let mut n = 0;
        while r.front().map(|(e, _)| *e <= safe_before).unwrap_or(false) {
            let (_, d) = r.pop_front().unwrap();
            println!("  freed: {}", d);
            n += 1;
        }
        println!("epoch→{}; freed {}; deferred {}", new_e, n, r.len());
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_epoch_advances() {
        let m = EpochMgr::new();
        m.collect();
        assert_eq!(m.epoch.load(Ordering::SeqCst), 1);
    }
    #[test]
    fn test_retire() {
        let m = EpochMgr::new();
        m.retire("x");
        assert_eq!(m.retired.lock().unwrap().len(), 1);
    }
}

(* 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 test_epoch_advances() {
        let m = EpochMgr::new();
        m.collect();
        assert_eq!(m.epoch.load(Ordering::SeqCst), 1);
    }
    #[test]
    fn test_retire() {
        let m = EpochMgr::new();
        m.retire("x");
        assert_eq!(m.retired.lock().unwrap().len(), 1);
    }
}

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