EpochManager

Usage

use EpochManager;

or

import EpochManager;

Support for Epoch-based Memory Reclamation.

Warning

This module relies on the AtomicObjects package module, which has several platform restrictions in its current state:

• It relies on Chapel extern code blocks and so requires that the Chapel compiler is built with LLVM enabled.

• Currently only CHPL_TARGET_ARCH=x86_64 is supported as it uses the x86-64 instruction: CMPXCHG16B.

• The implementation relies on GCC style inline assembly, and so is restricted to a CHPL_TARGET_COMPILER value of gnu, clang, or llvm.

Epoch-Based Memory Reclamation

In Epoch-Based Memory Reclamation, the lifetime of an arbitrary number of objects are represented in terms of an epoch. While inside of an epoch, there is a guarantee that no object that is reachable will be reclaimed. To ensure this guarantee, objects are marked for deletion first prior to actually deleting them by inserting them into a data structure specific to the current epoch. Objects, prior to deletion, must be logically removed such that no future operations are able to access them. One example of logical removal is removing a node from a linked list by a task; the node is no longer accessible by other tasks after its removal, but any other task could have access to said node before it was removed. To further concretize this example by applying epochs, imagine that all tasks are in epoch e, a node n is logically removed and therefore pushed on e’s data structure, then the epoch is advanced to e’, then n can be safely deleted once no task is in e.

Note

The correctness of Epoch-Based Memory Reclamation is contingent on the fact that delete is never explicitly called on an object accessible during an epoch, and that all deletion is handled through the EpochManager API.

There are two variants of the EpochManager, the LocalEpochManager, which is optimized for shared-memory, and the EpochManager, which is optimized for distributed memory. The LocalEpochManager is a shared-memory variant that is implemented entirely as a class that enables the user to specify their own lifetime management as you would with any other class. The EpochManager on the other hand, is a record that is forwarding to a privatized class instance, which ensures that all field accesses and method invocations are forwarded to the an instance that is local to the current locale. The EpochManager and LocalEpochManager share the same API and semantics in all but one case: deallocation. Since EpochManager is a record, you must explicitly invoke destroy on it, as it will not automatically clean itself up when it goes out of scope.

var localManager = new owned LocalEpochManager();
var distManager = new EpochManager();
// Necessary
distManager.destroy();

For a task to enter an epoch, they must first register their task with the manager. Once registered, a token specific to that task is returned, which will automatically unregister the task after it goes out of scope via owned lifetime semantics.

var manager = new owned EpochManager();
var token = manager.register();
// Optional
token.unregister();
forall i in 1..N with (var token = manager.register()) {}
manager.destroy();

After registering, the task must then pin to enter the current epoch, and unpin once they are finished. This token can also be used to mark objects for reclamation via deferDelete. The EpochManager takes any type of unmanaged class and treats them as object, so no generics are required.

forall i in 1..N with (var token = manager.register()) {
  token.pin();
  token.deferDelete(new unmanaged object());
  token.unpin();
}

To advance the epoch and ensure that objects can be reclaimed, tryReclaim must be invoked, and should be done so periodically. tryReclaim is concurrent-safe to call, and so can be called from the context of multiple tasks.

var dom = {1..N} dmapped Cyclic(startIdx=1);
var manager = new EpochManager();
forall i in dom with (var token = manager.register(), var numOps : int) {
  token.pin();
  // ...
  token.unpin();
  numOps += 1;
  if numOps % 1024 == 0 then {
    manager.tryReclaim();
  }
}
manager.tryReclaim();
manager.destroy();

class LocalEpochManager

LocalEpochManager manages reclamation of objects, ensuring thread-safety.

proc init()

Default initialize the manager.

proc register(): owned TokenWrapper

Register a task.

Returns

A handle to the manager

proc tryReclaim()

Try to announce a new epoch. If successful, reclaim objects which are safe to reclaim. It is legal to call it in or outside of a read-side critical section (while the task is pinned).

proc deinit()

Reclaim all objects

class TokenWrapper

Handle to LocalEpochManager

proc pin()

Pin a task

proc unpin()

Unpin a task

proc deferDelete(x: unmanaged object?)

Delete an object.

Arguments

x – The class instance to be deleted. Must be of unmanaged class type

proc tryReclaim()

Try to announce a new epoch. If successful, reclaim objects which are safe to reclaim

proc unregister()

Unregister the handle from the manager

proc deinit()

Unregister the handle from the manager

record EpochManager

EpochManager manages reclamation of objects, ensuring thread-safety. It employs privatization.

proc init()

Default initialize with instance of privatized class.

proc destroy()

Reclaim all allocated memory; destroy all privatized objects.

class EpochManagerImpl

The class which is privatized on each locale for EpochManager.

proc register(): owned DistTokenWrapper

Register a task.

Returns

A handle to the manager

proc tryReclaim()

Try to announce a new epoch. If successful, reclaim objects which are safe to reclaim

proc clear()

Destroy all objects. Not thread-safe

class DistTokenWrapper

Handle to EpochManager

proc pin()

Pin a task

proc unpin()

Unpin a task

proc deferDelete(x: unmanaged object?)

Delete an object.

Arguments

x – The class instance to be deleted. Must be of unmanaged class type

proc tryReclaim()

Try to announce a new epoch. If successful, reclaim objects which are safe to reclaim

proc unregister()

Unregister the handle from the manager

proc deinit()

Unregister the handle from the manager