LICM implementation

We implemented our capture analysis solution in the Deuce framework (the poster from PPoPP13 provides a general overiew). For that implementation, we had three major design goals: (1) to avoid changing the current Deuce API; (2) to guarantee retro-compatibility with existing applications and STMs for Deuce; and (3) to provide the ability to enhance any existing STM with the capture analysis technique without requiring either its recompilation or any modification to its source-code.

Enhancing Deuce with the capture analysis technique requires three main changes to the Deuce core structures: (1) the Context implementation of any STM must keep a fingerprint representing the identity of the transaction in execution by a context; (2) a transactional class (i.e., a class whose instances are accessed in a transactional scope) must have an additional field---owner---to store the fingerprint of the transaction that instantiates it; and (3) all STM barriers must perform the capture analysis dictated in the following code:

public class ContextDelegatorCapturedState extends ContextDelegator {
 public static int onReadAccess(Object ref, int val, long addr, Context ctx) {
  if (isCaptured(ref, ctx)) return val;
  else return ctx.onReadAccess(ref, val, addr);
 }
 public static void onWriteAccess(Object ref, int val, long addr, Context ctx) {
  if (isCaptured(ref, ctx)) UnsafeHolder.getUnsafe().putInt(ref, addr, value);
  else ctx.onWriteAccess(ref, val, addr);
 }
 ... 
 // There is a corresponding pair of barriers for each primitive type.
}

In the following, we explain the implementation of each of these enhancements.

Transaction Fingerprint

A Context object must keep the fingerprint of the transaction that is running, for later performing the capture analysis, as shown in the capture analysis algorithm of the isCaptured function:

public class ContextDelegatorCapturedState extends ContextDelegator {
 ...
 public static boolean isCaptured(Object ref, Context ctx){
   return (((CapturedState)ref).owner == ((ContextFilterCapturedState)ctx).trxFingerprint);
 } 
}

To implement this technique in Deuce we need to initialize and store a new fingerprint in the Context object of the executing thread, when it is notified of the beginning of a new transaction. Besides that, given that Deuce uses linear nesting, meaning that there is no concurrency among nested transactions within a nesting tree, the fingerprint of a top-level transaction can be shared across its nested transactions. In the following we show the code of a Context implementation that controls the initialization of new fingerprints:

public class ContextFilterCapturedState implements Context {
  protected final Context ctx;
  protected Object trxFingerprint = null;
  protected int nestedLevel = 0;
  
  public ContextFilterCapturedState (Context ctx) {
    this.ctx = ctx;
  }
  @Override
  public void init(int atomicBlockId, String metainf) {
    nestedLevel++;
    if (nestedLevel == 1) trxFingerprint = new Object();
    ctx.init(atomicBlockId, metainf);
  }
  @Override
  public boolean commit(){
    nestedLevel--;
    return ctx.commit();
  }
  ...
}

To support this feature in Deuce, we added a new system property, org.deuce.filter, which enables the specification of a filter context---that is, a class that implements the Context interface and adds some functionality to any existing Context (using the decorator design pattern). The new class ContextFilterCapturedState uses this approach, so that it can be applied to an existing Context of any STM.

Transactional Objects in Captured Memory

According to our capture analysis algorithm, all transactional objects should have the type CapturedState, meaning that transactional classes must inherit, directly or indirectly, from the class CapturedState:

public class CapturedState {    

  private final Object owner;

  public CapturedState() {
    this.owner = null;
  }
  
  public CapturedState(Context ctx) {
    this.owner = ((ContextFilterCapturedState) ctx).trxFingerprint;
  }  
}

Depending on whether a transactional class is instantiated outside or inside a transactional scope, the constructor invoked will be either the parameterless constructor or the constructor with a Context parameter, respectively. If an object is instantiated out of a transactional scope then its owner field will be null. Otherwise, it will point to the fingerprint of the executing Context (we assume that whenever the class CapturedState is used, all contexts will be instances of the class ContextFilterCapturedState).

To support this feature, we added to the Deuce framework a new infrastructure that allows the specification and execution of enhancers, which are additional transformations to the standard Deuce instrumentation. These enhancers are instances of classes implementing the interface Enhancer and they may be added to the Deuce engine through the system properties org.deuce.transform.pre and org.deuce.transform.post, depending on whether they should be performed before or after the standard Deuce instrumentation. Moreover, the enhancers may be combined in a chain of transformations, when more than one enhancer is specified in the same pre or post property.

The enhancer EnhancerCapturedState defines the transformation responsible for replacing the top of the transactional classes hierarchy from Object to CapturedState. Yet, we cannot apply the same approach for arrays, because we cannot change their base class. So, we need to wrap arrays with instances of the class CapturedStateArrayBase, which in turn inherits from CapturedState. The enhancer EnhancerCapturedStateArray defines the transformation that is responsible for this transformation and for replacing all operations that deal with arrays with new operations manipulating instances of the CapturedStateArrayBase class. This approach allows us to apply capture analysis for regular objects only, or for both objects and arrays, depending on the enhancers that we pass to Deuce.

Furthermore, wrapping arrays in captured state objects adds an extra indirection when they are accessed from non-transactional code, because these objects are no longer arrays themselves. Note that for regular objects, we do not change their behavior: We preserve their original structure and interface, which can be accessed either from transactional or non-transactional code. So, unlike with regular objects, when we access arrays from non-transactional code we have to get the encapsulated array from the captured state object. But, unlike unidimensional arrays, where the unwrap operation consists only in getting its elements field, for multidimensional arrays we need to instantiate a new array and copy the elements from each unidimensional array that is encapsulated in its own captured state array. For this reason, in our current approach, the unwrap of a multidimensional array has a huge overhead.

Note that we cannot let the inner dimensions of a multidimensional array be ordinary'' arrays. In Java, the elements of a multidimensional array are accessed as a series of unidimensional accesses (e.g. in the case of a bidimensional array stored in a field we need to perform an `aaload` to get the reference to the inner array, followed by another array access). All of these operations (which may not appear collocated in the code, because we may pass an inner array as an argument to a method) are instrumented by the Deuce STM and replaced by STM barriers. So, if we let the inner array be an ordinary'' array then we cannot perform the capture analysis in the second barrier.

Thus, the reverse process of unwrapping a multidimensional array from the captured state object forces us to rebuild the entire multidimensional array from the elements encapsulated on each array of every inner captured state object, instead of just getting the reference to the internal array, as happens for unidimensional arrays. Yet, we disallowed the unwrap of multidimensional arrays (throwing an UnsupportedOperationException), due to the huge overhead of this operation and in this case, we recommend one of the following alternative options, if possible: (1) to exclude the owner class from Deuce instrumentation; or (2) to access always the array from atomic methods, such as atomic indexers. If none of the previous options is well-suited, then we suggest to use the capture analysis support just for regular objects.

STM Barriers with Capture Analysis

Given that the methods of the ContextDelegator class are static (not virtual) we cannot override them in the same way as we do for the Context interface. But we can replace the whole class with a new one preserving the same methods' signatures. In fact, the instrumentation engine refers to this class by its internal name that is stored in a global constant---CONTEXT\_DELEGATOR\_INTERNAL---and if we replace it with the name of the new class containing methods with a new implementation, then the static methods of this class will be used as the STM barriers.

So, to include the capture analysis in the current Deuce implementation we allow the Deuce engine to receive an extra system property---org.deuce.delegator---specifying the delegator class responsible for providing the STM barriers. In this case, we should specify the class ContextDelegatorCapturedState, which defines the STM barriers able to perform the capture analysis.

But when we instrument arrays with the EnhancerCapturedStateArray, then all the barriers that were previously invoked passing an array by argument are now invoked with that array wrapped inside a CapturedStateArrayBase object. So, we need to extend the array barriers of the ContextDelegatorCapturedState with new methods according to the previous invocation. For this purpose, we duplicated every array barrier with a corresponding method that replaces the array argument by a CapturedStateArrayBase. These barriers are responsible for performing the capture analysis on captured state arrays, whereas the original array barriers stay unmodified. Thus the delegator ContextDelegatorCapturedState can perform the capture analysis including arrays, or not.

Concluding, to run an application with the Deuce framework performing the capture analysis for transactional objects, we must specify the class enhancer EnhancerCapturedState through the parameter org.deuce.transform.post, the filter ContextFilterCapturedState through the parameter org.deuce.filter and the new delegator in the parameter org.deuce.delegator. Yet, because it makes no sense to run this delegator without supporting captured state objects and without transaction's fingerprints, then by default we automatically include these two features when the ContextDelegatorCapturedState is specified.

Example of executing Vacation instrumented by Deuce and running the LSA STM with capture analysis.

java -javaagent:deuceAgent.jar
 -Dorg.deuce.transaction.contextClass=org.deuce.transaction.lsa.Context
 -Dorg.deuce.transform.post=org.deuce.transform.asm.EnhancerCapturedState
 -Dorg.deuce.filter=org.deuce.transaction.ContextFilterCapturedState
 -Dorg.deuce.delegator=org.deuce.transaction.ContextDelegatorCapturedState
  jstamp.vacation.Vacation

To simplify the execution with full capture analysis (for objects and arrays) we also defined an auxiliary system property that may be used in conjunction with the previous delegator, like this: -Dorg.deuce.capmem=full.