Reading 4. Word granularity STM

March 14, 2008

Harris and Fraser’s 2003 OOPSLA paper was the first to describe a practical STM system integrated into a programming language. They implemented WSTM word-granularity STM) in the ResearchVM from Sun Labs.
WSTM benefits

• WSTM did not require a programmer to declare the memory locations accessed within a transaction.
• WSTM was integrated into a modern, object-oriented language ( Java) by extending the language with the atomic operation. Strangely enough, WSTM did not exploit the object-oriented nature of Java and could support procedural languages as well.

Strong or Weak Isolation	Weak
Transaction Granularity	Word
Direct or Deferred Update	Deferred (update in place)
Concurrency Control	Optimistic
Synchronization	Obstruction free
Conflict Detection	Late
Inconsistent Reads	Inconsistency toleration
Conflict Resolution	Helping or aborting
Nested Transaction	Flattened
Exceptions	Terminate

WSTM extended Java with a new statement:

atomic (condition) { 
   statements; 
} 

A modified JIT ( Just-In-Time, i.e., run-time) compiler translated this statement into

bool done = false; 
   while (!done) { 
            STMStart(); 
            try { 
                if (condition) { 
                    statements; 
                    done = STMCommit(); 
                } else { 
                    STMWait(); 
                } 
            } catch (Exception t) { 
              done = STMCommit(); 
              if (done) { 
                  throw t; 
              } 
            } 
   } 

Note: an exception within the atomic region’s predicate or body causes the transaction to commit. Subsequent systems more typically treated an exception as an error that aborts a transaction.
The code produced by the compiler relies on five primitive operations provided by the

void   STMStart() 
void   STMAbort() 
bool   STMCommit() 
bool   STMValidate() 
void   STMWait()

In addition, all references to object fields from statements within an atomic region are replaced by calls to an appropriate library operation:

STMWord STMRead(Addr a) 
void STMWrite(Addr a, STMWord w) 

Restrictions: Because the JVM’s JIT compiler performs this translation, only references from Java bytecodes, not those in native methods, are translated to access these auxiliary structures. A few native methods were hand translated and included in a WSTM library, but a call on most native methods (including those that perform IO operations) from a transaction would cause a run-time error.

enum TransactionStatus { ACTIVE, COMMITTED, ABORTED, ASLEEP }; 
class TransactionEntry { 
     public Addr loc; 
     public STMWord oldValue; 
     public STMWord oldVersion; 
     public STMWord newValue; 
     public STMWord newVersion; 
} 
class TransactionDescriptor { 
     public TransactionStatus status = ACTIVE; 
     int nestingDepth = 0; 
     public Set entries; 
} 

The status field records the transaction status. A transaction starts in state ACTIVE and makes a transition into one of the three other states. The nestingDepth field records the number of (flattened) transactions sharing this descriptor.
The entries field holds a TransactionEntry record for each location the transaction
reads or writes. The compiler redirects memory reads and writes to the appropriate descriptor. A TransactionEntry records a location’s original value (before the transaction’s first access) and its current value. For a location only read, the two values are identical. A transaction increments the version number when it modifies the location. The system uses the version number to detect conflicts.

OwnershipRec records the version number of the memory location, produced by the most recent committed transaction that updated the location. Second, when a transaction is in the process of committing, an OwnershipRec records the transaction that has acquired exclusive ownership of the location. Each ownership record holds either a version number or a pointer to the transaction that owns the location:

class OwnershipRec { 
     union { 
         public STMWord version; 
         public TransactionDescriptor* trans; 
     } val; 
     public bool HoldsVersion() { return (val.version & 0x1) != 0; } 
} 

The function FindOwnershipRec(a) maps memory address a to its associated OwnershipRec. The function CASOwnershipRec(a, old, new) performs a compare-and-swap operation on the OwnershipRec for memory address a, replacing it with value new, if the existing entry is equal to old.

void STMStart() { 
   if (ActiveTrans == null || ActiveTrans.status != TransactionStatus.ACTIVE) { 
        ActiveTrans = new TransactionDescriptor(); 
        ActiveTrans.status = TransactionStatus.ACTIVE; 
   } 
   AtomicAdd(ActiveTrans.nestingDepth, 1); 
} 

void STMAbort() { 
   ActiveTrans.status = TransactionStatus.ABORTED; 
   ActiveTrans.entries = null; 
   AtomicAdd(ActiveTrans.nestingDepth, -1); 
} 

struct ValVersion { 
   public STMWord val; 
   public STMWord version; 
} 

STMWord STMRead(Addr a) { 
   TransactionEntry* te = ActiveTrans.entries.Find(a); 
   if (null == te) { 
   // No entry in transaction descriptor. Create new entry (get value from memory) 
   // and add it to descriptor. 
      ValVersion vv = MemRead(a); 
      te = new TransactionEntry(a, vv.val, vv.version, vv.val, vv.version); 
      ActiveTrans.entries.Add(a, te); 
      return vv.val; 
   } else { 
   // Entry already exists in descriptor, so return its (possibly updated) value. 
      return te.newValue; 
   } 
}

void STMWrite(Addr a, STMWord w) { 
    STMRead(a); // Create entry if necessary. 
    TransactionEntry te = ActiveTrans.entries.Find(a); 
    te.newValue = w; 
    te.newVersion += 2; // Version numbers are odd numbers. 
} 

The function MemRead returns the value of a memory location, along with its version number:

• If no other transaction accessed the location and started committing, then the current value resides in the memory location and its ownership record contains the version number.
• If another transaction accessed the location and committed, the value is in the transaction’s newValue field and the version in the newVersion field.
• If another transaction accessed the location and has started, but not finished committing, the value is stored in the transaction’s oldValue field and the version in its oldVersion

STMCommit first acquires the ownership records for all locations accessed by the transaction. If successful, STMCommit changes the transaction’s state to COMMITTED, copies the modified values to memory, and releases the ownership records.
These three steps appear logically atomic to concurrent transactions because the committing transaction’s status changes atomically (and irrevocably) from ACTIVE to COMMITTED using an atomic read-modify-write operation. Once this change occurs, MemRead will return the updated value, even before the transaction copies value back to memory.

void STMCommit() { 
     // Only outermost nested transaction can commit. 
     if (AtomicAdd(ActiveTrans.nestingDepth, -1) != 0) { return; } 
     // A nested transaction already aborted this transaction. 
     if (ActiveTrans.status == TransactionStatus.ABORTED) { return; } 
       // Acquire ownership of all locations accessed by transaction. 
      int i; 
      for (i = 0; i < ActiveTrans.entries.Size(); i++) { 
           TransactionEntry* te = ActiveTrans.entries[i]; 
           switch (acquire(te)) { 
               case TRUE: { continue; } 
               case FALSE: { 
                       ActiveTrans.status = TransactionStatus.ABORTED; 
                       goto releaseAndReturn; 
               } 
               case BUSY: { /* conflict resolution */ } 
           } 
      } 
       // Transaction commits. 
      ActiveTrans.status = TransactionStatus.COMMITTED; 
        //Copy modified values to memory. 
      for (i = 0; i < ActiveTrans.entries.Size(); i++) { 
           TransactionEntry te = ActiveTrans.entries[i]; 
           *((STMWord*)te.loc) = te.newValue; 
      } 
   releaseAndReturn: // Release the ownership records. 
           for (int j = 0; j < i; j++) { release(te); } 
   } 
   bool acquire(TransactionEntry* te) { 
           OwnershipRec orec = CASOwnershipRec(te.loc, te.oldVersion, 
                                        ActiveTrans); 
           if (orec.HoldsVersion()) 
               { return orec.val.version == te.oldVersion; } 
           else { 
               if (orec.val.trans == ActiveTrans) { return true; } 
               else { return BUSY; } 
      } 
   } 

void release(TransactionEntry* te) { 
   if (ActiveTrans.status == TransactionStatus.COMMITTED) { 
       CASOwnershipRec(te.loc, ActiveTrans, te.newVersion); 
   } else { 
       CASOwnershipRec(te.loc, ActiveTrans, te.oldVersion); 
   } 
} 

STMValidate is a read-only operation that checks the ownership records for each location accessed by the current transaction, to ensure that they are still consistent with the version the transaction initially read:

bool STMValidate() { 
    for (int i = 0; i < ActiveTrans.entries.Size(); i++) { 
        TransactionEntry* te = ActiveTrans.entries[i]; 
        OwnershipRec orec = FindOwnershipRec(te.loc); 
        if (orec.val.version != te.oldVersion) { return false; } 
    } 
    return true; 
} 

STMWait can be used to implement a conditional critical region by suspending the transaction until its predicate should be reevaluated. It aborts the current transaction and waits until another transaction modifies a location accessed by the first transaction. It acquires ownership of the TransactionEntry accessed by the transaction, changes the transactions status to ASLEEP, and suspends the thread running the transaction. When another transaction updates one of these locations, it will conflict with the suspended transaction!!!
The conflict manager should allow the active transaction to complete execution and then resume the suspended transaction, which releases its ownership records and then retries the transaction:

void STMWait() { 
    int I; 
    for (i = 0; i < ActiveTrans.entries.Size(); i++) { 
          TransactionEntry* te = ActiveTrans.entries[i]; 
          switch (acquire(te)) { 
              case TRUE: { continue; } 
              case FALSE: { 
                   ActiveTrans.status = TransactionStatus.ABORTED; 
                   goto releaseAndReturn; 
              } 
              case BUSY: { /* conflict resolution */ } 
         } 
   } 
   // Transaction waits, unless in conflict with another transaction and 
   // needs to immediately re-execute. 
   ActiveTrans.status = TransactionStatus.ASLEEP; 
   SuspendThread(); 
   // Release the ownership records. 
   releaseAndReturn: 
       for (int j = 0; j < i; j++) { release(te); } 
} 

If two transactions share a location that neither one modifies, one transaction will be aborted, since the system does not distinguish read-only locations from modified locations.
This performance issue is easily corrected. STMWrite can set a flag isModified in a transaction entry to record a modification of the location. STMCommit should acquire ownership of modified locations and validate unmodified locations! This introduces a new transaction status READ_PHASE. The transaction remains in this state until it commits.

void STMCommit() { 
   for (int i = 0; i < ActiveTrans.entries.Size(); i++) { 
      TransactionEntry* te = ActiveTrans.entries[i]; 
      if (te.isModified) { 
         switch (acquire(te)) { 
            case TRUE: { continue; } 
            case FALSE: { 
               ActiveTrans.status = TansactionStatus.ABORTED; 
               goto releaseAndReturn; 
            } 
            case BUSY: { /* conflict resolution */ } 
         } 
      } 
   } 
   ActiveTrans.status = TransactionStatus.READ_PHASE; 
   for (int i = 0; i < ActiveTrans.entries.Size(); i++) { 
      TransactionEntry* te = ActiveTrans.entries[i]; 
      if (!te.isModified) { 
         ValVersion vv = MemRead(te.loc); 
         if (te.oldVersion != vv.version) { 
         // Another transaction updated this location. 
            ActiveTrans.status = TransactionStatus.ABORTED; 
            goto releaseAndReturn; 
         } 
      } 
   } 
   // Transaction commits. Write modified values to memory. 
   ActiveTrans.status = TransactionStatus.COMMITTED; 
   for (int i = 0; i < ActiveTrans.entries.Size(); i++) { 
       TransactionEntry te = ActiveTrans.entries[i]; 
       *((STMWord*)te.loc) = te.newValue; 
   } 
   // Release the ownership records. 
releaseAndReturn: 
       for (int j = 0; j < i; j++) { release(te); } 
}