Homepage | Contact
gcc

Last update: 2012-05-23

Brief Transactional Memory GCC tutorial

Outline

The idea of transactional memory is to create a block of a code that will be executed 'atomically'. Thanks to this abstraction, the creation of a concurent program is a bit easier. Indeed, it avoids the usage of locks to protect a shared data-structure or variable. This block delimits the start and the commit of the transaction.

The transaction block is executed speculatively and in case of conflicts on a memory access between two transactions (or also threads), one of the transaction is aborted and all modifications to memory are rollback. Then the transaction is retried.

Since there is no hardware support yet (Intel TSX, IBM, ... ), Transaction Memory mechanism is implemted in Software. Over the years, researchers proposed several algorithms and implementations. Some famous implementations are TL2, TinySTM, NOrec, SwissTM. GCC 4.7 includes a Transactional Memory runtime (TM-runtime) called libitm.

Transactional Memory (TM) API in GCC

GCC relies on the draft transactional constructs for C++ (link to PDF). To create a transaction, two new keywords were added to the language. The main keyword is __transaction_atomic followed with a statement or a code block to be executed in the transaction. To indicate that a function can be called in an atomic transaction, you should add the transaction_safe attribute to the function declaration or definition.

Installing GCC 4.7

GCC 4.7 was released in April 2012 so maybe your linux distribution already included it. In ubuntu 11.10+, you can install the gcc-snapshot package (apt-get install gcc-snapshot). If it is not available for your system, you must build the GCC 4.7 compiler. In this case, follow the tutorial on building GCC on the GCC website (Building GCC).

Compiling a TM program with GCC

To enable the support for TM, the '-fgnu-tm' compiler directive has to be added to the compilation command line.
Example: gcc -Wall -fgnu-tm -O3 -o ll ll.c
Note that with the optimization level 0 (-O0), some of the TM optimization are disabled (RaR, RaW, RfW, WaR, WaW, optimized stack memory barriers).

First Transactional program

In this tutorial, I propose to implement two operations for a linked list: the contains and the add operations. The first step is to create a sequential version (This linked list implementation is extracted from tinySTM package).

typedef struct node {
  int val;
  struct node *next;
} node_t;

typedef struct intset {
  node_t *head;
} intset_t;

intset_t *set;

static __attribute__((transaction_safe))
node_t *new_node(val_t val, node_t *next)
{
  node_t *node;

  node = (node_t *)malloc(sizeof(node_t));
  if (node == NULL) {
    exit(1);
  }
  node->val = val;
  node->next = next;

  return node;
}


int contains(int value)
{
  int result;
  node_t *prev, *next;

  __transaction_atomic {
    prev = set->head;
    next = prev->next;
    while (next->val < val) {
      prev = next;
      next = prev->next;
    }
    result = (next->val == val);
  }
  return result;
}

int add(int value)
{
  int result;
  node_t *prev, *next;

  __transaction_atomic {
    prev = set->head;
    next = prev->next;
    while (next->val < val) {
      prev = next;
      next = prev->next;
    }
    result = (next->val != val);
    if (result) {
      prev->next = new_node(val, next);
    }
  }
  return result;
}

When the sequential version is done, the next step is to add the transactions and the threads. In the above code, the __transaction_atomic block delimits the part of code to be executed atomically. In the function add, all shared memory must be accessed inside the transaction.

GCC can infer the transaction safety of a function if the definition is inside the current source file. Otherwise it requires the transaction_safe, transaction_unsafe, or transaction_pure annotation to the function declaration. In our example, transaction_safe for new_node function is not required because the function is defined in the source file. However, exit declaration requires annotation because GCC will infer that the function is transaction unsafe. Note that GCC handles malloc/free functions and new/delete automatically in transactions. To work around this problem, the annotation transaction_pure can be added to the declaration.


__attribute__((transaction_pure)) void exit(int status);
The transaction_pure attribute indicates GCC that the function is safe to be called inside a transaction without instrumentation ie. the function has no a side effect.

In order to reduce the transaction size, new_node can be executed outside the transaction but still the write to prev->next must be inside the transaction.

GCC TM runtime, libitm

GCC comes with a TM runtime library called libitm. It implements different algorithms like Global lock, Read-Writer lock, or an implementation close to the Lazy Snapshot Algorithm to fit the application workload. The TM runtime library should adapt its configuration itself to provide the best performance regarding the workload. But it is possible to force the TM runtime to use another TM algorithm at runtime by setting the environment variable ITM_METHODS. (See libitm documentation for all available options)

Using another TM runtime

Some other TM runtimes propose the support for GCC with TM, like tinySTM and RSTM. To use one of those libraries, you should compile the TM runtime and use the -L/path/to/tm-library option at link time. You may also use the -Wl,-rpath=/path/to/tm-library, to record the library path into the executable (it avoids the modification of LD_LIBRARY_PATH environment variable).

Debugging a transactional program

Unfortunately, debugging a transactional program is not easy. Due to the nature of speculation and the non-determinism, a bug may be hard to reproduce. The first tentative is to use the serial irrevocable mode for all transactions. This mode permits to avoid transactions to abort and thus you can trace your program without being disturbed by the rollback/retry mechanism.

Final words

Finally, note that GCC is an open source project and any contributions (bug reports, testing, code contribution, ...) to make TM mainstream is welcome. I would like to thank RedHat (Richard, Aldy and Torvald) and the VELOX project for this work on GCC and the Swiss National Science Foundation (SNSF) for making this tutorial possible.

You can send me emails for any suggestions or corrections (myfirstname.mylastname@gmail.com).

Known problems

Implied unsafe transactional code

Source code:


#include <unordered_map>
unordered_map<int, int> ht; 

int main() {
    __transaction_atomic {
        ht[1] = 1;
        ht.find(1);
    }
}

Error:


$ g++ -fgnu-tm -std=c++11 test_ht.cpp
test_ht.cpp:18:13: error: unsafe function call ‘std::__detail::_Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>
::mapped_type& std::__detail::_Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::operator[](_Key&&)
 [with _Key = int; _Pair = std::pair; _Hashtable = std::_Hashtable,
 std::allocator >, std::_Select1st >, std::equal_to, std::hash,
 std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, false, false, true>;
 std::__detail::_Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::mapped_type = int]’ within atomic transaction

Explanation: GCC inspects all the defined and non-annotated functions to figure out its transaction safety. If no unsafe statement is found, the function is considered safe for transactions eg. the 'find' method. If an unsafe statement is found, the unsafe attribute is propagated to the callee functions, eg the operator [].
So in the expansion of the operator [], a statement is found to be unsafe inside the possible call stack. Since the std::__throw_bad_alloc is not defined in this scope and it is not annotated as transaction_safe, the unsafe is propagated into the call stack and thus operator [] is unsafe.

Solution: To find which call is making the operator [] unsafe, you have to annotate all methods called as transaction_safe until you reach the unsafe code. In this example, the possible workaround is to annotate __throw_bad_alloc as transaction_pure as following:


namespace std __attribute__ ((__visibility__ ("default")))
{
  __attribute__((transaction_pure))
  void
  __throw_bad_alloc(void) __attribute__((__noreturn__));
}