RSTM: API

The following publications are related to the version 3 API 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.

Version 3 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
Library Calls
class Object
- Fields
- Methods
Smart Pointers
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.

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.
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.
BEGIN_TRANSACTION: Macro to mark the beginning of a transaction. Must be properly paired with an END_TRANSACTION.
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.
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.

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

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 validator parameter in the read accessors is used to insure that the read data is coming from the correct version of the object. It is not really part of the public API as the name Validator will never appear in the client code. Validators are associated with smart pointers. See this section on validation for more information about using validators.

See stm/accessors.h for more details.

GENERATE_FIELD(type, name)

type get_name(const stm::internal::Validator& v) const { ... }
void set_name(type t) { ... }

GENERATE_ARRAY(type, name, size)

type get_name(int i, const stm::internal::Validator& v) const { ... }
void set_name(int i, type t) { ... }

GENERATE_2DARRAY(type, name, rows, columns)

type get_name(int row, int column, const stm::internal::Validator& v) const { ... }
void set_name(int row, int column, type t) { ... }

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);
    ...
};

Methods

virtual [covariant] clone() const = 0

Object has a pure virtual clone() member that your class must implement. clone() is used internally by the library when speculative updates need to be made to an object. In most cases, a clone is made, updates are made to the clone, and when the transaction commits the clone somehow becomes the acknowledged valid version of the object (somehow because the way that this actually happens is implementation dependent).

You should implement clone as needed by your hierarchy. In most cases a shallow clone (essentially a bit copy) is adequate, however we have chosen not to provide a default bitwise clone() operation in order to avoid potential non-obvious programming errors.

We don't use the copy constructor because of the logical difference between copying an object for a standard C++ reason, and copying an object as part of a speculation (transactional update).

[covariant] here means that the library expects you to use C++'s covariant return type capability when defining your override for this function. Covariant return means that you can override a virtual method with a method that has a different return type, as long as the return type is a subclass of the original return type. It's easier to see in an example (code is worth a thousand words).

class Superclass {
    virtual Superclass* foo();
};

class Subclass : public Superclass {
    virtual Subclass* foo();
};

Here, the Subclass override of foo() is fine, even though the return type is different. This is how the clone() method in RSTM works.

/**
 *  A basic declaration of a transactionally shared Node class, shows the
 *  implementation of a basic clone() method. In this case, clone() simply
 *  forwards to the copy constructor for a Node.
 */
class Node : public stm::Object<Node> {
    GENERATE_FIELD(int, val);
    GENERATE_FIELD(stm::sh_ptr<Node>, next);

  public:
    virtual Node* clone() const {
       return new Node(*this);
    }
    ...
};

Note that the return type for the code example is Node*. For all classes (eg Foo) the return type for clone() should be a pointer to an instance of the class (eg virtual Foo* clone() const). If a whole class hierarchy is going to be transactionally shared, and one implementation of clone() is appropriate for the entire hierarchy, then the base class of the hierarchy can implement clone() as virtual Base* clone() const { ... }.

virtual void deactivate()

deactivate() is the logical opposite of clone(). It is called by the library before a clone is disposed of. Any resources acquired by a clone should be released in deactivate(). A default empty implementation is provided for deactivate() because we have found that the vast majority of classes have empty implementations.

^*virtual void redo(SharedBase* s) = 0

^*redo_lock specific

The redo_lock library implementation updates clones out-of-place, and then copies them back into the "actual" object during commit time. The redo() method is a user-provided method for doing that copy back.

Note that this function exposes the SharedBase class. This isn't a class that users need to do anything with. The first thing that all redo() implementations do is to cast the parameter to the correct type.

/**
 *  A basic declaration of a transactionally shared Node class. Shows a simple
 *  redo implementation. Note the similarity between redo and operator=.
 */
class Node : public stm::Object<Node> {
    GENERATE_FIELD(int, val);
    GENERATE_FIELD(stm::sh_ptr<Node>, next);

  public:
    virtual Node* clone() const {
       return new Node(*this);
    }

#ifdef NEED_REDO_METHOD
    /**
     *  Note the initial cast, which is always ok. In addition, redo is called
     *  with a lock held, so we can ignore the need to validate fields and use
     *  the actual fields defined by the macros.
     */
    virtual void redo(SharedBase* s)
    {
        Node* l = static_cast<Node*>(s);
        m_val = l->m_val;
        m_next = l->m_next;
    }
#endif
    ...
};

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:

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.
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.
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.
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.

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> and wr_ptr<T>. It is initialized with the correct version of O when an sh_ptr<T> is opened by a smart pointer. The validator can be retrieved from the smart pointer with the v() call.

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.v()));

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.

A doomed transaction may make an invalid speculative access to a privatized location (speculation after private use).
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:

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.
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.
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.

Rochester Software Transactional Memory