Epoch-Based Reclamation without TLS

[LouisJenkinsCS]

As Chapel lacks any TLS we can't use TLS to keep track of which epoch we are in. As such we need a way for each individual task to maintain their own epoch and to make it visible to any other task performing a deletion. The idea is simple...

class EBRDescriptor {
   var epoch : atomic uint(64);
   var inUse : bool;
   var listNext : EBRDescriptor;
   var queueNext : EBRDescriptor;
   var deleteList : list(object);

   proc enter() { /* ... */ }
   proc exit() { /* ... */ }
   proc deferDelete(obj) { /* ... */ }
}

class EBRManager {
   var descriptors : list(EBRDescriptor);
   var unusedDescriptors : queue(EBRDescriptor);
   var globalEpoch : atomic uint(64);
}

If a task wishes to perform an operation they must first obtain a descriptor from unusedDescriptors which is a non-blocking queue; if a descriptor is not found then you must create one and append it to descriptors which is a simple non-blocking list which appends via performing an atomic add on its size count and then a simple atomic exchange; as you cannot delete descriptors we only need to maintain the head. By maintaining a list of descriptors, we can perform an O(N) scan across them all to determine whether an operation is in-flight as well as the version of the data structure they are using.