Department of Computer Science
University of Rochester
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.
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.
void init(...)void shutdown()BEGIN_TRANSACTIONEND_TRANSACTIONvoid 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
These are the most likely sources of problems when using the library.
this" is not a smart pointerSee 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.
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.
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).
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.
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> {
...
};
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
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.
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:
const object.
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.
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.
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.
See our technical report for a more thorough treatment of privatization and the privatization problem.
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.
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.
Any STM system that supports privatization will provide some mechanism for ensuring that privatized access is safe access.
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:
sh_ptr<T>s to the privatized data must be the only
active sh_ptr<T>s until the data is logically
publicized.
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.
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.