Reclamation

Understanding safe memory reclamation in DEBRA+.

State Machine

Overview

Reclamation is the process of safely freeing retired objects. The reclamation system walks thread-local limbo bags and frees objects from old epochs that are no longer accessible.

Reclamation Steps

1. Start: Begin reclamation process
2. Load epochs: Read global epoch and all thread epochs
3. Check safety: Determine if any epochs are safe to reclaim
4. Try reclaim: Walk 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
import std/atomics

type
  NodeObj = object
    value: int
  Node = ref NodeObj

const ReclaimInterval = 10

proc doOperation(handle: ThreadHandle[64], i: int) =
  let u = unpinned(handle)
  let pinned = u.pin()

  let node = managed Node(value: i)
  let ready = retireReady(pinned)
  discard ready.retire(node)

  let unpinResult = pinned.unpin()
  case unpinResult.kind:
  of uUnpinned: discard
  of uNeutralized: discard unpinResult.neutralized.acknowledge()

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

  let handle = registerThread(manager)
  var totalReclaimed = 0

  # Perform operations with periodic reclamation
  for i in 0..<50:
    # Do one operation
    doOperation(handle, 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 Reclamation

Dedicate a thread to reclamation for best separation of concerns:

# examples/reclamation_background.nim
## Background reclamation: dedicated thread for memory reclamation.

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 reclaimerThread() {.thread.} =
  ## Background thread that periodically attempts reclamation.
  while not shouldStop.load(moAcquire):
    let reclaimResult = reclaimStart(addr manager)
      .loadEpochs()
      .checkSafe()

    case reclaimResult.kind:
    of rReclaimReady:
      {.cast(gcsafe).}:
        let count = reclaimResult.reclaimready.tryReclaim()
        discard totalReclaimed.fetchAdd(count, moRelaxed)
    of rReclaimBlocked:
      discard

    sleep(5)  # 5ms between attempts

proc workerThread() {.thread.} =
  ## Worker thread that performs operations.
  let handle = registerThread(manager)

  for i in 0..<100:
    let u = unpinned(handle)
    let pinned = u.pin()

    let node = managed Node(value: i)
    let ready = retireReady(pinned)
    discard ready.retire(node)

    let unpinResult = pinned.unpin()
    case unpinResult.kind:
    of uUnpinned: discard
    of uNeutralized: discard unpinResult.neutralized.acknowledge()

    # Occasionally advance epoch
    if i mod 10 == 0:
      manager.advance()

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

  # Start background reclaimer
  var reclaimer: Thread[void]
  createThread(reclaimer, reclaimerThread)

  # 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])

  # Give reclaimer time to clean up remaining objects
  sleep(50)

  # Stop reclaimer
  shouldStop.store(true, moRelease)
  joinThread(reclaimer)

  echo "Total reclaimed by background thread: ", 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:

1. Advance epoch: Trigger epoch advancement
2. Wait: Try again later
3. 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:

1. Batch reclamation: Don't reclaim after every operation
2. Separate thread: Dedicate a thread to reclamation
3. Threshold: Only reclaim when enough objects accumulated

Next Steps

• Learn about neutralization
• Understand integration patterns