Reclamation¶

Understanding safe memory reclamation in DEBRA+.

State Machine¶

Overview¶

Reclamation is the process of safely freeing retired objects. Each registered thread reclaims its own retired objects from its own thread-local limbo bag list. There is no cross-thread reclamation: the bag list is mutated by the owning thread (via retire) without synchronization, so another thread cannot walk it safely.

Per-thread reclamation¶

Pass your ThreadHandle to reclaimStart(handle) (or reclaimNow(handle)) to walk and free your own thread's retired objects. A thread that retires but never calls reclaim leaks its bags. The recommended pattern is to fold a reclaim attempt into your hot path on a cadence (e.g. once every N retires); see the epoch advancement guide.

If a thread stalls or exits while still pinned, the neutralization mechanism forces it to unpin so the global epoch can advance, but it does not free that thread's already-retired bags. Drain your bags before exiting the thread.

Reclamation Steps¶

Start: Begin reclamation process for your handle's slot
Load epochs: Read global epoch and all thread epochs
Check safety: Determine if any epochs are safe to reclaim
Try reclaim: Walk this thread's own limbo bags and free eligible objects

Epoch Safety¶

The safe epoch is the minimum of all pinned thread epochs. Objects retired in epoch E are safe to reclaim if E < safeEpoch - 1.

Periodic Reclamation¶

Attempt reclamation every N operations to amortize the cost:

# examples/reclamation_periodic.nim
## Periodic reclamation: attempt reclamation every N operations.

import debra

type
  NodeObj = object
    value: int

  Node = ref NodeObj

const ReclaimInterval = 10

proc doOperation(handle: ThreadHandle[64], dtor: Destructor, i: int) =
  handle.withPin:
    let node = retain Node(value: i)
    it.retire(cast[pointer](../../examples/node), dtor)

proc periodicReclaimDemo() =
  var manager = initDebraManager[64](../../examples)
  setGlobalManager(addr manager)

  let handle = registerThread(manager)
  let dtor = releaseDestructor[NodeObj](../../examples)
  var totalReclaimed = 0

  # Perform operations with periodic reclamation
  for i in 0 ..< 50:
    doOperation(handle, dtor, i)

    # Advance epoch periodically
    if i mod 5 == 0:
      manager.advance()

    # Attempt reclamation every ReclaimInterval operations
    if i mod ReclaimInterval == ReclaimInterval - 1:
      let reclaimResult = reclaimStart(addr manager).loadEpochs().checkSafe()

      case reclaimResult.kind
      of rReclaimReady:
        let count = reclaimResult.reclaimready.tryReclaim()
        totalReclaimed += count
        echo "Operation ", i, ": reclaimed ", count, " objects"
      of rReclaimBlocked:
        echo "Operation ", i, ": reclamation blocked"

  echo "Total reclaimed: ", totalReclaimed, " objects"
  echo "Periodic reclamation example completed successfully"

when isMainModule:
  periodicReclaimDemo()

View full source

Background Epoch Advancement¶

A dedicated background thread cannot reclaim other threads' retired objects: each thread reclaims its own. A background thread is still useful for driving the global epoch forward (manager.advance()) while workers continue to retire and reclaim on their own slots.

# examples/reclamation_background.nim
## Background epoch-advancement thread paired with per-worker reclamation.
##
## Each thread reclaims its own retired objects: cross-thread reclamation is
## not supported in DEBRA+ because the limbo bag list is mutated by the owning
## thread without synchronization. A dedicated background thread is still
## useful for driving the global epoch forward so workers' retires become
## eligible for reclamation; the workers themselves call `reclaimNow(handle)`
## on a cadence.
##
## ## refc compatibility
##
## This example is **incompatible with `--mm:refc`** and will skip with a
## diagnostic message under that GC. The reason is a refc design constraint,
## not a debra bug:
##
## * The worker threads allocate `Node` (a `ref`) and `retain` it, which calls
##   `GC_ref`. The refc heap (`gch`) is thread-local (`{.rtlThreadVar.}` in
##   `system/gc.nim`), so the cell metadata lives on the worker's heap.
## * If a different thread later ran the destructor (which does `GC_unref` via
##   `releaseDestructor`), it would mutate a refcount on a cell that doesn't
##   belong to it, and crash inside `decRef`.
## * refc has no public API for cross-thread `ref` release. arc and orc use
##   atomic, shared refcounts and tolerate cross-thread `=destroy` /
##   `GC_unref`.
##
## Per-thread reclamation avoids the cross-thread `GC_unref` problem because
## the same worker thread that allocated a node also frees it. Under refc the
## example would still run safely as long as we never crossed threads, but we
## skip here for consistency.
##
## See also: `examples/reclamation_periodic.nim` for a single-threaded
## reclamation pattern.

when defined(gcRefc):
  echo "reclamation_background: skipped under --mm:refc"
  echo "  Use --mm:arc or --mm:orc for the cross-thread retain/release pattern."
else:
  import debra
  import std/[atomics, os]

  type
    NodeObj = object
      value: int

    Node = ref NodeObj

  var
    manager: DebraManager[4]
    shouldStop: Atomic[bool]
    totalReclaimed: Atomic[int]

  proc epochDriverThread() {.thread.} =
    ## Background thread that periodically advances the global epoch.
    ##
    ## This thread does NOT reclaim on behalf of the workers: each worker
    ## reclaims its own retired objects. Driving the epoch forward unblocks
    ## reclamation in workers that are not actively advancing (e.g., because
    ## their hot path is too tight to use `advanceEvery`).
    while not shouldStop.load(moAcquire):
      manager.advance()
      sleep(5) # 5ms cadence

  proc workerThread() {.thread.} =
    ## Worker thread that retires and reclaims its own objects.
    {.cast(gcsafe).}:
      let handle = registerThread(manager)
      let dtor = releaseDestructor[NodeObj](../../examples)

      for i in 0 ..< 100:
        withPin(handle):
          let node = retain Node(value: i)
          it.retire(cast[pointer](../../examples/node), dtor)

        # Reclaim our own bag occasionally. The background thread keeps the
        # global epoch advancing, so most of these passes find work.
        if i mod 10 == 9:
          let count = reclaimNow(handle)
          discard totalReclaimed.fetchAdd(count, moRelaxed)

      # Drain remaining retired objects before the worker exits, otherwise
      # they leak (no other thread can reclaim them).
      for _ in 0 ..< 4:
        manager.advance()
      let count = reclaimNow(handle)
      discard totalReclaimed.fetchAdd(count, moRelaxed)

  when isMainModule:
    manager = initDebraManager[4](../../examples)
    setGlobalManager(addr manager)
    shouldStop.store(false, moRelaxed)
    totalReclaimed.store(0, moRelaxed)

    # Start background epoch driver
    var driver: Thread[void]
    createThread(driver, epochDriverThread)

    # Start worker threads
    var workers: array[2, Thread[void]]
    for i in 0 ..< 2:
      createThread(workers[i], workerThread)

    # Wait for workers to finish
    for i in 0 ..< 2:
      joinThread(workers[i])

    # Stop epoch driver
    shouldStop.store(true, moRelease)
    joinThread(driver)

    echo "Total reclaimed across workers: ", totalReclaimed.load(moRelaxed)
    echo "Background reclamation example completed successfully"

View full source

Blocked Reclamation¶

If safeEpoch <= 1, reclamation is blocked. This is normal when:

All threads pinned at current epoch
Only one epoch has passed since start

Options when blocked:

Advance epoch: Trigger epoch advancement
Wait: Try again later
Neutralize: If a thread is stalled, neutralize it

Reclamation Scheduling¶

Too frequent: - Wastes CPU checking epochs - Most checks find nothing to reclaim

Too infrequent: - Accumulates memory - Longer pause when reclaim happens

Recommended: Every 100-1000 operations or every 10-100ms.

Performance Considerations¶

Reclamation cost:

Load epochs: O(m) where m = max threads
Walk bags: O(n) where n = retired objects
Total: O(m + n)

Optimization tips:

Batch reclamation: Don't reclaim after every operation
Cadence helper: Use handle.advanceEvery(n) plus a periodic reclaimNow(handle) call
Threshold: Only reclaim when enough objects accumulated

Next Steps¶

Learn about neutralization
Understand integration patterns