Rochester Software Transactional Memory

Last update: 07/06/10
  • Google Code Site
  • Main
  • License
  • Download
  • Building RSTM
  • Programming with RSTM
  • Applications
  • STM Implementations
  • STM Primer

Google Code Site

The RSTM package is now available as a Google code project. We welcome your comments, suggestions, and contributions. Future releases will occur through the Google code mechanism.

The information hosted here is accurate with respect to the fifth release, and the initial Google code release. The STM Implementations and STM Primer pages will continue to be relevant, but we expect the RSTM-specific information hosted at the University of Rochester to become rapidly out-of-date.


This information has been updated for RSTM release 5. Information about older releases can be found here (v3) and here (v2).

The following publications are related to the RSTM and may be helpful additional sources of information.

  • Delaunay Triangulation with Transactions and Barriers, from IISWC, 2007.
  • Capabilities and Limitations of Library-Based Software Transactional Memory in C++, from TRANSACT, 2007.
  • Privatization Techniques for Software Transactional Memory, a University of Rochester technical report.
  • Inevitability Mechanisms for Software Transactional Memory, from TRANSACT, 2008.
  • Ordering-Based Semantics for Software Transactional Memory, from OPODIS, 2008.
  • A Comprehensive Contention Management Strategy for Software Transactional Memory, from PPOPP, 2009.

RSTM API

Everything in the API (other than the BEGIN_TRANSACTION and END_TRANSACTION macros of course) is part of namespace stm. We'll periodically omit the namespace qualifier below. More detailed information can be found in the library comments.

  • Caveats
    • "this" is not a smart pointer
    • Do no work in a shared object constructor
    • Initialize pertinent thread local variables inside the transaction.
  • Library Calls
    • void init(...)
    • void shutdown()
    • BEGIN_TRANSACTION
    • END_TRANSACTION
    • void tx_release(rd_ptr<T>)
    • void tx_free([any smart pointer type])
    • void fence()
    • void acquire_fence() (new in release 5)
    • void release_fence() (new in release 5)
    • void retry()
    • void halt_retry() (new in release 5)
    • bool try_inevitable()
    • void inevitable_read_prefetch(const void* addr, unsigned bytes)
    • void inevitable_write_prefetch(const void* addr, unsigned bytes)
    • void setPrio(unsigned p) (new in release 5)
    • void restart() (new in release 5)
  • class Object
    • Fields
      • GENERATE_FIELD(type, name)
      • GENERATE_ARRAY(type, name, size)
      • GENERATE_2DARRAY(type, name, rows, columns)
  • Smart Pointers
    • class sh_ptr<T>
    • class rd_ptr<T>
    • class wr_ptr<T>
    • class un_ptr<T>
  • Validation
  • Privatization

Caveats

These are the most likely sources of problems when using the library.

"this" is not a smart pointer

See the section on smart pointers for information about smart pointers and how they are used in the RSTM API.

All accesses to shared objects need to be done through smart pointers, however the built-in this pointer passed during a call to an instance's method is not a smart pointer. If the object instance is actually a shared object, it is unsafe to use the this pointer directly. There are two ways to deal with this.

  1. Initialize an sh_ptr<T> with this, and then use it as you normally might.*

    *This is supported in the current API. This may not be supported in the future, as its correctness relies on some implementation specific functionality.

  2. Use static class functions, simulating the implicit this pointer by passing an explicit sh_ptr<T> as a parameter. This is the preferred method as it does not require special library support.

Do no work inside a shared object constructor

Causing an exception or transaction to abort inside a shared object constructor will cause a difficult to debug double delete runtime error. Essentially, the aborting transaction will attempt to delete the newed object, however the object has already been deleted due to the exception (or abort).

The workaround for this limitation is to use a separate initialization routine to initialize a shared object, after it has been newed.

It is also possible to have a constructor that does nothing that would cause an exception (including newing any members), and that makes no STM API calls (accessors, etc). This double delete error is difficult enough to trace that we recommend constructors that do nothing.

Note that the construction of the shared object can safely fail immediately with a bad allocation exception.

Initialize pertinent thread local variables inside the transaction.

The transaction system only protects shared data. No other data is rolled back when a transaction aborts. This means that you should initialize all thread local variables (usually stack allocated) inside the boundary of a transaction, if the transaction is going to modify them. This prevents you from mistakenly reading a local variable whose value was set during an aborted transaction.

Common examples are boolean flags, iterators, and smart pointers that you are using as indexes into a data structure (essentially iterators).

bool flag = FALSE;

BEGIN_TRANSACTION
...
if (!flag) {
  ...
  flag = TRUE;
}

... // Likely a bug if we abort here

END_TRANSACTION
    

In this example, a flag is allocated on the stack, and initialized outside of the transaction. The flag is checked inside the transaction, and then reset at some later point. If the transaction aborts after the flag is reset, you might wind up with inconsistent results. The same sort of problem occurs if you have iterated through half of a list and then abort. You must reset your iterator inside the transaction for correct behaviour (assuming you'd like to re-read the entire list).

Library Calls

void init(...)

Must be called once in each thread before it engages in any transactions.

void shutdown()

Call before a transactional thread exits in order to release thread specific transactional resources and print statistics.

BEGIN_TRANSACTION

Macro to mark the beginning of a transaction. Must be properly paired (lexically) with an END_TRANSACTION. Subsumption nesting is supported in the v4 release, so nested BEGIN_TRANSACTIONs are safe and essentially ignored by the runtime. Future releases will implement closed nesting (and possibly open nesting).

END_TRANSACTION

Macro to mark the end of a transaction. Must be properly paired with a BEGIN_TRANSACTION.

void tx_release(rd_ptr<T>)

Used for "early" release of a read pointer (supported only in object-based runtimes).

void tx_free([any smart pointer type])

Because the API smart pointers are not actual pointers, you can't delete them directly. Use tx_delete when you need to delete a smart pointer. See the code for more details.

void fence()

Transactional fence mechanism. Will return once all current transactions have either committed or aborted. A transactional fence is typically used during privatization, but can also be used for barrier based synchronization.

void acquire_fence() (new in release 5)

The acquire_fence() function indicates to the runtime that the previous transaction was a privatizing transaction. It should immediately follow the END_TRANSACTION macro. See the SSS transactional memory model notes, as well as our OPODIS 2008 paper paper for more information.

void release_fence() (new in release 5)

The release_fence() function indicates to the runtime that the next transaction is a publisgin transaction. It should immediately precede the BEGIN_TRANSACTION macro. See the SSS transactional memory model notes, as well as our OPODIS 2008 paper paper for more information.

void retry()

The retry() call allows a transaction to manually self-abort and retry if it encounters a situation in which it should do so. The common use for retry is for condition synchronization. If a condition isn't met, the transaction can just abort and retry, knowing that at some point in the future some other transaction will set the condition as necessary.

In many of our runtimes, retry() simply aborts, waits a brief period, and retries the transaction. The RSTM and Fair runtimes provide additional mechanisms.

Note that a call to retry() is invalid inside an inevitable transaction. Using retry() in an inevitable transaction, or from a non-transactional context, will result in a runtime assertion when assertions are enabled.

void halt_retry() (new in release 5)

The halt_retry() function should be used prior to shutting down the transactional memory system if retrying transactions may be present.

bool try_inevitable()

An inevitable transaction is one that will not abort. Inevitability can be used to make calls to non-transactional code (system or library calls), as well as to attempt to increase application performance in the face of transactions that abort with high probability.

Only one transaction at a time in a system can run inevitably. There are a number of different mechanisms for implementation of inevitability, some of which allow concurrent, disjoint writing transactions to run. More information can be found in our TRANSACT 2008 paper. The LLT and Fair runtimes support multiple implementations, which can be selected at compile-time.

The try_inevitable() call returns a boolean indicating either success or failure. Transactional code can decide how to respond to this call as needed. Common usage is to spin on the call, to call retry() to restart the transaction that cannot become inevitable, or to execute a different code path in a non-inevitable fashion if possible.

Our current library implementations require that try_inevitable() be called before any data has been read or written transactionally. Failure to do so will result in a runtime assertion. A future release will address this limitation, as it is simply an implementation artifact.

void inevitable_[read/write]_prefetch(const void* addr, unsigned bytes)

Depending on the inevitability mechanism you choose, you may need to "prefetch" the locations to be read and written by a library routine before calling it inevitably. The inevitable_read_prefetch() and inevitable_write_prefetch() calls can perform the required instrumentation for library code with predictable read and write sets.

void setPrio(unsigned new_priority) (new in release 5)

When using a runtime that supports transactional priority (currently only the Fair runtime), the setPrio(unsigned) attempts to give the indicated priority to the calling function. When conflicts are detected, a transaction with lower priority will defer to transactions with higher priority.

For more information see our PPOPP 2009 paper.

void restart() (new in release 5)

Immediately aborts and restarts a transaction, without using a retry() mechanism.

Transactional Objects

class Object<T>

All transactionally protected classes must inherit from the Object<T> template. This template injects the appropriate transactional metadata into the class hierarchy.

The Object<T> template is an instance of the C++ Curiously Recurring Template pattern. Transactional classes should inherit publicly from this template, passing their own class name as the template argument.

/**
 *  A basic declaration of a transactionally shared Node class.
 */
class Node : public stm::Object<Node> {
    ...
};
    

Fields (updated for v4)

The following macros generate a protected field of the given type, with the name m_name. Direct use of m_name is only safe if you are positive that you have exclusive access to the instance. Under normal transactional circumstances you will use the accessors generated by the macro.

Many STM systems require post-validation (read and/or write). The fundamental idea is that some implementations need to check and see if a value that was just read or written came from a version of the object that is consistent with all previous reads and writes to that object. RSTM manages this detail by requiring that all object field reads and writes happen through accessors that do the validation.

The smart pointer parameter in the read accessor (getter) is used to insure that the read data is coming from the correct version of the object. Alternately, the smart pointer parameter in the write accessor (setter) is used to distinguish between writes to currently shared data, or privatized data as they may require different types of instrumentation. See this section on validation for more information.

GENERATE_FIELD(type, name)
  • type get_name(const [smart pointer]&) const { ... }
  • void set_name(type t, const [smart pointer]&) { ... }
GENERATE_ARRAY(type, name, size)
  • type get_name(int i, const [smart pointer]& v) const { ... }
  • void set_name(int i, type t, const [smart pointer]&) { ... }
GENERATE_2DARRAY(type, name, rows, columns)
  • type get_name(int row, int column, const [smart pointer]& v) const { ... }
  • void set_name(int row, int column, type t, const [smart pointer]&) { ... }

In our Node example each node has a payload value, and a shared next node. Note that the type of the pointer to the next node is sh_ptr<Node>. See the section on smart pointers for more details.

/**
 *  A basic declaration of a transactionally shared Node class, with fields
 *  m_val and m_next generated by our accessor macros.
 */
class Node : public stm::Object<Node> {
    GENERATE_FIELD(int, val);
    GENERATE_FIELD(stm::sh_ptr<Node>, next);
    ...
};
    

Using the resulting getters and setters is straightforward. Assuming that we have a node and we'd like to read or write it's next pointer we would see code like the following (note that the smart pointer passed to the accessor must always be the same pointer we're accessing the shared object through).

sh_ptr<Node> n;
rd_ptr<Node> node(n);
sh_ptr<Node> next = node->get_next(node);    // getter
wr_ptr<Node> node_w(node);
node_w->set_next(next, node_w);              // setter
    

Smart Pointers

The following discussion assumes basic familiarity on the C++ smart pointer design pattern. There are a lot of good references about smart pointers, as well as some existing libraries that use smart pointers. The stl::auto_ptr is an example of a widely used smart pointer.

  • Boost Smart Pointers - the Boost library has a good overview of smart pointers, as well as providing some special purpose implementations.
  • Smart Pointers in C++ - a chapter from Andrei Alexandrescu's "Modern C++ Design." This is one of the more detailed and thorough discussions available of the ins and outs of smart pointers. The Loki library that accompanies the book is a good place to see a first-class implementation of a generic smart pointer.

Smart pointers are the fundamental way that client code interacts with transactional objects. Smart pointers correspond to the different transactional "state" that a shared object can be in. The following four states are possible in the RSTM system:

  1. Shared - A shared object is one that has not yet been touched in a transaction. An example of a shared object is the "next" pointer of a linked list node, before it is read or written.
  2. Read Only - A read only object represents an object that has been opened for reading in the current transaction. A read only object roughly corresponds to a const object.
  3. Writable - A writable object is one that has been opened for writing by the current transaction. Both const and non-const members can be called on a writable object. No changes made to a writable object will be visible to other threads until the transaction commits.
  4. Privatized - A privatized object is a nominally shared object that will only be accessed (read or written) by one thread at a time. Program logic is responsible for ensuring this invariant. Privatized objects may be safely read or written inside or outside of transactions.

Smart pointers capture these object states, providing API hooks and statically verifiable programming correctness. See the actual code for more information. These are overviews of the four types of smart pointers in RSTM.

class sh_ptr<T>

An sh_ptr<T> (pronounced "s h pointer" and also called simply a "shared pointer") is a pointer to a shared object. In our Node example, the "next" pointer is an sh_ptr<Node>.

An sh_ptr<Node> cannot be dereferenced directly. It can only be tested for NULL, copied, initialized from a T*, and used to initialize a rd_ptr<T>, wr_ptr<T>, or un_ptr<T>. These three pointer classes can then be used to access the actual shared object. An operator<(...) is provided so that sh_ptrs can be stored in stl containers.

class rd_ptr<T>

A rd_ptr<T> ("read pointer") points to an object that the current transaction has opened for read only access. You can only call a const method through a read pointer. A rd_ptr<T> is constructed from an sh_ptr<T> through an explicit constructor. Once a rd_ptr<T> has been constructed, an sh_ptr<T> can be opened for reading simply by assignment (operator=()) into the constructed rd_ptr<T>.

A rd_ptr<T> can be upgraded to a wr_ptr<T> through an explicit constructor.

class wr_ptr<T>

A wr_ptr<T> ("write pointer") points to a shared object that the current transaction has opened for writing. A wr_ptr<T> is initialized explicitly from an sh_ptr<T>. A wr_ptr<T> can also be explicitly constructed from a rd_ptr<T> as an upgrade-to-writable operation.

class un_ptr<T>

An un_ptr<T> ("un pointer") represents an object that has been privatized. An un_ptr<T> is unprotected by the transaction system, and thus can be used either inside or outside a transaction.

An un_ptr<T> is initialized from an sh_ptr<T>. It is unsafe to use an un_ptr<T> in the same transaction in which it was initialized. More information about privatization in RSTM is available here.

Validation

STM implementations that use either in-place update, or buffered update, typically need to have reads (or possibly writes) post-validated. Consider a redo style STM implementation. Imagine that thread 1 reads value X from object O, and then is preempted. Meanwhile, thread 2 updates Y (a field of O that points to some object) commits, and copies back the changes to O.

When thread 1 wakes up, it makes a decision based on the value that it read for X that eventually ends up with thread 1 reading Y and dereferencing it without checking it for NULL (perhaps the value it read for X is never paired with a NULL X.

Thread 1 will crash with a SEGV. The logical issue here is that the values for X and Y read by thread 1 come from inconsistent versions of O. A conservative solution to this issue is to check that the version of O is the same for all reads from O. We "post-validate" O after every read.

Internally RSTM uses a Validator object to do this post validation. The Validator is never directly visible in client code. A Validator is maintained internally by all rd_ptr<T>s. It is initialized with the correct version of O when an sh_ptr<T> is opened by a smart pointer.

The actual validation is handled by the field read accessor generated by the GENERATE_* macros. The following code example initializes a rd_ptr<Node> from an sh_ptr<Node> (sentinel). Then, in order to read the next pointer, the code uses the get_next(...) accessor, passing in the validator as returned from the smart pointer.

rd_ptr<Node> prev(sentinel);
rd_ptr<Node> curr(prev->get_next(prev));

This pattern of calling a getter through a smart pointer, and passing the validator associated with that smart pointer is used everywhere.

Some STM implementations, like the basic non-blocking rstm implementation provided, do not need validation. When you compile RSTM using this implementation, all of the validation calls will be no ops that are optimized out during compilation.

Privatization

See our technical report for a more thorough treatment of privatization and the privatization problem.

In General

All software transactional memory runtimes have some unavoidable overheads in the form of indirection, logging, validation, and/or conflict detection. They also tend to have some restrictions, typically prohibiting system calls and I/O during transactions. One proposed solution to these problems in an STM with weak isolation is to allow non-mediated (non-transactional) access to shared data. This may be accomplished through extra-transactional means, such as locks or barriers. This data is called privatized data.

The simplest example of privatized data is a newly allocated shared object that has not yet been linked into a shared data structure. The only transactional pointer to the object exists in the current thread, thus no conflict is possible on the object, and no validation need occur. Another common example is privatizing part of a linked data structure. A thread might excise part of a tree for private use outside of a transaction. A third example might be a phase based application where one phase consists of shared access to a data structure (perhaps a partitioning phase), while a second phase involves threads operating on disjoint sections of the partitioned data structure. Or single thread phases interleaved with multithread phases. The mesh application included with RSTM is an example of an application that uses phase-based privatization.

A library implementation of an STM typically requires explicit privatization, where the user statically annotates the use of private data, while an integrated compiler-based implementation has the option of providing different levels of implicit privatization, as well as mixed privatization.

In Practice

Safe privatization is complex issue for an STM system, and a very active research topic. The implementation of privatization is highly dependent on the type of STM (indirection, redo log, or undo log), as well as the implementation of the STM.

Ideally a privatization implementation would be completely transparent to the user. Unfortunately, many STM implementations suffer from the privatization problem, in which there exists a window where logically privatized data cannot be safely used. This window manifests itself as two symmetric problems.

  1. A doomed transaction may make an invalid speculative access to a privatized location (speculation after private use).
  2. A privatizer may not see committed changes to an object from transactional cleanup phases (cleanup after private use).

Any STM system that supports privatization will provide some mechanism for ensuring that privatized access is safe access.

In RSTM

The RSTM API supports explicit privatization via the un_ptr<T>. Like all of the smart pointers, an un_ptr<T> is initialized from an sh_ptr<T>. The un_ptr<T> allows read/write access to its shared object but these accesses are not logged or checked. In addition, sh_ptr<T>s are not opened when assigned to an un_ptr<T>, though some implementations may need to clean the shared object on first access. This provides fast unshared access to shared objects.

RSTM deals with privatization safety by providing the transactional fence() library routine. Privatization in RSTM consists of:

  1. Privatizing some shared objects in a transaction. This typically means modifying some shared data structure links, or writing to a shared flag somewhere. After privatization the thread local sh_ptr<T>s to the privatized data must be the only active sh_ptr<T>s until the data is logically publicized.
  2. Once the privatizing transaction commits, the privatizing thread executes a fence() call. When the call returns, the privatizing thread knows that no transaction is currently looking at, or cleaning up, any of the data that it privatized.
  3. The privatizer can now initialize un_ptr<T>s from the sh_ptr<T>s allocated on its stack, and use them as normal.

In the context of our Node example, the following code truncates a linked list, and then can work on the now private tail of the list outside of a transaction.

sh_ptr<Node> to_truncate;             // Initialize to NULL

BEGIN_TRANSACTION

rd_ptr<Node> prev(sentinel);
rd_ptr<Node> curr(prev->get_next(prev.v()));

to_truncate = curr->get_next(curr.v());
curr->set_next(NULL);

END_TRANSACTION

fence();          // Transactional fence, no one is looking
                  // at to_truncate after return.

un_ptr<Node> truncate(to_truncate);         // Use the privatized node
cout << truncate->get_data(truncate.v());   // in I/O
    

The mesh application uses privatization. See the transaction in worker.cc (around line 294) for more details and a real-world example.

Questions? contact webmaster
Department of Computer Science
University of Rochester