Patchwork [trans-mem] Beginning of refactoring

login
register
mail settings
Submitter Torvald Riegel
Date July 9, 2011, 2:30 p.m.
Message ID <1310221819.5106.1054.camel@triegel.csb>
Download mbox | patch
Permalink /patch/103979/
State New
Headers show

Comments

Torvald Riegel - July 9, 2011, 2:30 p.m.
The attached patch makes flat nesting the default, while still
supporting closed nesting on demand (for user-controlled aborts via
__transaction_cancel).
Previously, a new transaction object was created for each nested
transaction. The patch changes this to using one transaction object
during the whole lifetime of a thread and keeping checkpoints of the
transaction state when starting closed nested transactions. This allows
us to easily use flat nesting and decreases the transaction start/commit
overheads to some extent.

OK for branch?
commit a6b608b3b7e942b2ffaff7f7b8a897dd7cfd62c1
Author: Torvald Riegel <triegel@redhat.com>
Date:   Sat Jul 9 16:22:21 2011 +0200

    Use flat nesting by default and support closed nesting via checkpoints.
    
    	* local.cc (gtm_transaction::rollback_local): Support closed nesting.
    	* retry.cc (GTM::gtm_transaction::decide_retry_strategy): Same.
    	* eh_cpp.cc (GTM::gtm_transaction::revert_cpp_exceptions): Same.
    	* useraction.cc: Same. Also use vector instead of list to store actions.
    	* dispatch.h (GTM::abi_dispatch): Add can_run_uninstrumented_code and
    	closed_nesting flags, as well as a closed nesting alternative.
    	* method-serial.cc: Same.
    	* beginend.cc (GTM::gtm_transaction::begin_transaction): Change to
    	flat nesting as default, and closed nesting on demand.
    	(GTM::gtm_transaction::rollback): Same.
    	(_ITM_abortTransaction): Same.
    	(GTM::gtm_transaction::restart): Same.
    	(GTM::gtm_transaction::trycommit): Same.
    	(GTM::gtm_transaction::trycommit_and_finalize): Removed.
    	(choose_code_path): New.
    	(GTM::gtm_transaction_cp::save): New.
    	(GTM::gtm_transaction_cp::commit): New.
    	* query.cc (_ITM_inTransaction): Support flat nesting.
    	* aatree.h (aa_tree::remove): New.
    	(aa_tree::operator new): Add placement new.
    	* libitm_i.h: Add closed nesting as restart reason.
    	(GTM::gtm_transaction_cp): New helper struct for nesting.
    	(GTM::gtm_transaction::user_action): Same.
    	(GTM::gtm_transaction): Support flat and closed nesting.
    	* alloc.cc (commit_allocations_2): New.
    	(commit_cb_data): New helper struct.
    	(GTM::gtm_transaction::commit_allocations): Handle nested
    	commits/rollbacks.
    	* libitm.h (_ITM_codeProperties): Change pr_hasElse to the ABI's value.
    	* libitm.texi: Update user action section, add description of nesting.
Torvald Riegel - July 18, 2011, 11:19 p.m.
On Sat, 2011-07-09 at 16:30 +0200, Torvald Riegel wrote:
> The attached patch makes flat nesting the default, while still
> supporting closed nesting on demand (for user-controlled aborts via
> __transaction_cancel).
> Previously, a new transaction object was created for each nested
> transaction. The patch changes this to using one transaction object
> during the whole lifetime of a thread and keeping checkpoints of the
> transaction state when starting closed nested transactions. This allows
> us to easily use flat nesting and decreases the transaction start/commit
> overheads to some extent.
> 
> OK for branch?

I split the patch, as requested.

First three parts are smaller changes:

patch1: New erase method and placement new for aatree.
patch2: Change pr_hasElse to the value specified in the ABI.
patch3: Add information to dispatch about closed nesting and
uninstrumented code.

Then, in preparation for the following flat-transaction object design:
patch4: Use vector instead of list to store user actions.
patch5: Add closed nesting as restart reason.

And the actual core change:
patch6: Make flat nesting the default, use closed nesting on demand.

This last patch is still rather large, but it is one logical piece.
beginend.cc has most changes, but splitting this one up would rather
create incomplete intermediate steps than make the direction of this
whole patch clear.

As discussed offline, reducing the one extra copying of jmpbuf for
actual closed-nested transactions can be addressed in a future patch by
modifying _ITM_beginTransaction, which could additionally remove the
extra copying from stack to jmpbuf for all transactions as it existed
before this patch here.

Ok for branch, or is further splitting required?

Patch

diff --git a/libitm/aatree.h b/libitm/aatree.h
index 6d28890..3e11b95 100644
--- a/libitm/aatree.h
+++ b/libitm/aatree.h
@@ -1,4 +1,4 @@ 
-/* Copyright (C) 2009 Free Software Foundation, Inc.
+/* Copyright (C) 2009, 2011 Free Software Foundation, Inc.
    Contributed by Richard Henderson <rth@redhat.com>.
 
    This file is part of the GNU Transactional Memory Library (libitm).
@@ -141,6 +141,8 @@  class aa_tree : public aa_tree_key<KEY>
   aa_tree() = default;
   ~aa_tree() { clear(); }
 
+  static void *operator new (size_t s, aa_tree<KEY, DATA>* p) { return p; }
+
   DATA *find(KEY k) const
   {
     node_ptr n = static_cast<node_ptr>(base::find (k));
@@ -160,6 +162,13 @@  class aa_tree : public aa_tree_key<KEY>
     delete n;
   }
 
+  node_ptr remove(KEY k, DATA** data)
+  {
+    node_ptr n = static_cast<node_ptr>(base::erase (k));
+    *data = (n ? &n->data : 0);
+    return n;
+  }
+
   void clear()
   {
     node_ptr n = static_cast<node_ptr>(this->m_tree);
diff --git a/libitm/alloc.cc b/libitm/alloc.cc
index 5c70144..9b60835 100644
--- a/libitm/alloc.cc
+++ b/libitm/alloc.cc
@@ -1,4 +1,4 @@ 
-/* Copyright (C) 2009 Free Software Foundation, Inc.
+/* Copyright (C) 2009, 2011 Free Software Foundation, Inc.
    Contributed by Richard Henderson <rth@redhat.com>.
 
    This file is part of the GNU Transactional Memory Library (libitm).
@@ -52,6 +52,55 @@  gtm_transaction::forget_allocation (void *ptr, void (*free_fn)(void *))
   a->allocated = false;
 }
 
+namespace {
+struct commit_cb_data {
+  aa_tree<uintptr_t, gtm_alloc_action>* parent;
+  bool revert_p;
+};
+}
+
+static void
+commit_allocations_2 (uintptr_t key, gtm_alloc_action *a, void *data)
+{
+  void *ptr = (void *)key;
+  commit_cb_data *cb_data = static_cast<commit_cb_data *>(data);
+
+  if (cb_data->revert_p)
+    {
+      // Roll back nested allocations.
+      if (a->allocated)
+        a->free_fn (ptr);
+    }
+  else
+    {
+      if (a->allocated)
+        {
+          // Add nested allocations to parent transaction.
+          gtm_alloc_action* a_parent = cb_data->parent->insert(key);
+          *a_parent = *a;
+        }
+      else
+        {
+          // Eliminate a parent allocation if it matches this memory release,
+          // otherwise just add it to the parent.
+          gtm_alloc_action* a_parent;
+          aa_tree<uintptr_t, gtm_alloc_action>::node_ptr node_ptr =
+              cb_data->parent->remove(key, &a_parent);
+          if (node_ptr)
+            {
+              assert(a_parent->allocated);
+              a_parent->free_fn(ptr);
+              delete node_ptr;
+            }
+          else
+            {
+              a_parent = cb_data->parent->insert(key);
+              *a_parent = *a;
+            }
+        }
+    }
+}
+
 static void
 commit_allocations_1 (uintptr_t key, gtm_alloc_action *a, void *cb_data)
 {
@@ -67,10 +116,19 @@  commit_allocations_1 (uintptr_t key, gtm_alloc_action *a, void *cb_data)
    REVERT_P is true if instead of committing the allocations, we want
    to roll them back (and vice versa).  */
 void
-gtm_transaction::commit_allocations (bool revert_p)
+gtm_transaction::commit_allocations (bool revert_p,
+    aa_tree<uintptr_t, gtm_alloc_action>* parent)
 {
-  this->alloc_actions.traverse (commit_allocations_1,
-				(void *)(uintptr_t)revert_p);
+  if (parent)
+    {
+      commit_cb_data cb_data;
+      cb_data.parent = parent;
+      cb_data.revert_p = revert_p;
+      this->alloc_actions.traverse (commit_allocations_2, &cb_data);
+    }
+  else
+    this->alloc_actions.traverse (commit_allocations_1,
+				  (void *)(uintptr_t)revert_p);
   this->alloc_actions.clear ();
 }
 
diff --git a/libitm/beginend.cc b/libitm/beginend.cc
index 9b16973..6023390 100644
--- a/libitm/beginend.cc
+++ b/libitm/beginend.cc
@@ -88,6 +88,14 @@  GTM::gtm_transaction::operator delete(void *tx)
 static pthread_mutex_t global_tid_lock = PTHREAD_MUTEX_INITIALIZER;
 #endif
 
+static inline uint32_t choose_code_path(uint32_t prop, abi_dispatch *disp)
+{
+  if ((prop & pr_uninstrumentedCode) && disp->can_run_uninstrumented_code())
+    return a_runUninstrumentedCode;
+  else
+    return a_runInstrumentedCode;
+}
+
 uint32_t
 GTM::gtm_transaction::begin_transaction (uint32_t prop, const gtm_jmpbuf *jb)
 {
@@ -97,14 +105,112 @@  GTM::gtm_transaction::begin_transaction (uint32_t prop, const gtm_jmpbuf *jb)
   abi_dispatch *disp;
   uint32_t ret;
 
+  // ??? pr_undoLogCode is not properly defined in the ABI. Are barriers
+  // omitted because they are not necessary (e.g., a transaction on thread-
+  // local data) or because the compiler thinks that some kind of global
+  // synchronization might perform better?
+  if (unlikely(prop & pr_undoLogCode))
+    GTM_fatal("pr_undoLogCode not supported");
+
   gtm_thread *thr = setup_gtm_thr ();
 
-  tx = new gtm_transaction;
+  tx = gtm_tx();
+  if (tx == NULL)
+    {
+      tx = new gtm_transaction;
+      set_gtm_tx(tx);
+    }
+
+  if (tx->nesting > 0)
+    {
+      // This is a nested transaction.
+      // Check prop compatibility:
+      // The ABI requires pr_hasNoFloatUpdate, pr_hasNoVectorUpdate,
+      // pr_hasNoIrrevocable, pr_aWBarriersOmitted, pr_RaRBarriersOmitted, and
+      // pr_hasNoSimpleReads to hold for the full dynamic scope of a
+      // transaction. We could check that these are set for the nested
+      // transaction if they are also set for the parent transaction, but the
+      // ABI does not require these flags to be set if they could be set,
+      // so the check could be too strict.
+      // ??? For pr_readOnly, lexical or dynamic scope is unspecified.
+
+      if (prop & pr_hasNoAbort)
+        {
+          // We can use flat nesting, so elide this transaction.
+          if (!(prop & pr_instrumentedCode))
+            {
+              if (!(tx->state & STATE_SERIAL) ||
+                  !(tx->state & STATE_IRREVOCABLE))
+                tx->serialirr_mode();
+            }
+          // Increment nesting level after checking that we have a method that
+          // allows us to continue.
+          tx->nesting++;
+          return choose_code_path(prop, abi_disp());
+        }
+
+      // The transaction might abort, so use closed nesting if possible.
+      // pr_hasNoAbort has lexical scope, so the compiler should really have
+      // generated an instrumented code path.
+      assert(prop & pr_instrumentedCode);
+
+      // Create a checkpoint of the current transaction.
+      gtm_transaction_cp *cp = tx->parent_txns.push();
+      cp->save(tx);
+      new (&tx->alloc_actions) aa_tree<uintptr_t, gtm_alloc_action>();
+
+      // Check whether the current method actually supports closed nesting.
+      // If we can switch to another one, do so.
+      // If not, we assume that actual aborts are infrequent, and rather
+      // restart in _ITM_abortTransaction when we really have to.
+      disp = abi_disp();
+      if (!disp->closed_nesting())
+        {
+          // ??? Should we elide the transaction if there is no alternative
+          // method that supports closed nesting? If we do, we need to set
+          // some flag to prevent _ITM_abortTransaction from aborting the
+          // wrong transaction (i.e., some parent transaction).
+          abi_dispatch *cn_disp = disp->closed_nesting_alternative();
+          if (cn_disp)
+            {
+              disp = cn_disp;
+              set_abi_disp(disp);
+            }
+        }
+    }
+  else
+    {
+      // Outermost transaction
+      // TODO Pay more attention to prop flags (eg, *omitted) when selecting
+      // dispatch.
+      if ((prop & pr_doesGoIrrevocable) || !(prop & pr_instrumentedCode))
+        tx->state = (STATE_SERIAL | STATE_IRREVOCABLE);
+
+      else
+        disp = tx->decide_begin_dispatch ();
+
+      if (tx->state & STATE_SERIAL)
+        {
+          serial_lock.write_lock ();
 
+          if (tx->state & STATE_IRREVOCABLE)
+            disp = dispatch_serialirr ();
+          else
+            disp = dispatch_serial ();
+        }
+      else
+        {
+          serial_lock.read_lock ();
+        }
+
+      set_abi_disp (disp);
+    }
+
+  // Initialization that is common for outermost and nested transactions.
   tx->prop = prop;
-  tx->prev = gtm_tx();
-  if (tx->prev)
-    tx->nesting = tx->prev->nesting + 1;
+  tx->nesting++;
+
+  tx->jb = *jb;
 
   // As long as we have not exhausted a previously allocated block of TIDs,
   // we can avoid an atomic operation on a shared cacheline.
@@ -124,58 +230,80 @@  GTM::gtm_transaction::begin_transaction (uint32_t prop, const gtm_jmpbuf *jb)
 #endif
     }
 
-  tx->jb = *jb;
+  // Determine the code path to run. Only irrevocable transactions cannot be
+  // restarted, so all other transactions need to save live variables.
+  ret = choose_code_path(prop, disp);
+  if (!(tx->state & STATE_IRREVOCABLE)) ret |= a_saveLiveVariables;
+  return ret;
+}
 
-  set_gtm_tx (tx);
 
-  // ??? pr_undoLogCode is not properly defined in the ABI. Are barriers
-  // omitted because they are not necessary (e.g., a transaction on thread-
-  // local data) or because the compiler thinks that some kind of global
-  // synchronization might perform better?
-  if (unlikely(prop & pr_undoLogCode))
-    GTM_fatal("pr_undoLogCode not supported");
+void
+GTM::gtm_transaction_cp::save(gtm_transaction* tx)
+{
+  // Save everything that we might have to restore on restarts or aborts.
+  jb = tx->jb;
+  local_undo_size = tx->local_undo.size();
+  memcpy(&alloc_actions, &tx->alloc_actions, sizeof(alloc_actions));
+  user_actions_size = tx->user_actions.size();
+  id = tx->id;
+  prop = tx->prop;
+  cxa_catch_count = tx->cxa_catch_count;
+  cxa_unthrown = tx->cxa_unthrown;
+  disp = abi_disp();
+  nesting = tx->nesting;
+}
 
-  if ((prop & pr_doesGoIrrevocable) || !(prop & pr_instrumentedCode))
-    tx->state = (STATE_SERIAL | STATE_IRREVOCABLE);
+void
+GTM::gtm_transaction_cp::commit(gtm_transaction* tx)
+{
+  // Restore state that is not persistent across commits. Exception handling,
+  // information, nesting level, and any logs do not need to be restored on
+  // commits of nested transactions. Allocation actions must be committed
+  // before committing the snapshot.
+  tx->jb = jb;
+  memcpy(&tx->alloc_actions, &alloc_actions, sizeof(alloc_actions));
+  tx->id = id;
+  tx->prop = prop;
+}
 
-  else
-    disp = tx->decide_begin_dispatch ();
 
-  if (tx->state & STATE_SERIAL)
-    {
-      serial_lock.write_lock ();
+void
+GTM::gtm_transaction::rollback (gtm_transaction_cp *cp)
+{
+  abi_disp()->rollback (cp);
 
-      if (tx->state & STATE_IRREVOCABLE)
-        disp = dispatch_serialirr ();
-      else
-        disp = dispatch_serial ();
+  rollback_local (cp ? cp->local_undo_size : 0);
+  rollback_user_actions (cp ? cp->user_actions_size : 0);
+  commit_allocations (true, (cp ? &cp->alloc_actions : 0));
+  revert_cpp_exceptions (cp);
 
-      ret = a_runUninstrumentedCode;
-      if ((prop & pr_multiwayCode) == pr_instrumentedCode)
-	ret = a_runInstrumentedCode;
+  if (cp)
+    {
+      // Roll back the rest of the state to the checkpoint.
+      jb = cp->jb;
+      id = cp->id;
+      prop = cp->prop;
+      if (cp->disp != abi_disp())
+        set_abi_disp(cp->disp);
+      memcpy(&alloc_actions, &cp->alloc_actions, sizeof(alloc_actions));
+      nesting = cp->nesting;
     }
   else
     {
-      serial_lock.read_lock ();
-      ret = a_runInstrumentedCode | a_saveLiveVariables;
+      // Restore the jump buffer and transaction properties, which we will
+      // need for the longjmp used to restart or abort the transaction.
+      if (parent_txns.size() > 0)
+        {
+          jb = parent_txns[0].jb;
+          prop = parent_txns[0].prop;
+        }
+      // Reset the transaction. Do not reset state, which is handled by the
+      // callers.
+      nesting = 0;
+      parent_txns.clear();
     }
 
-  set_abi_disp (disp);
-
-  return ret;
-}
-
-void
-GTM::gtm_transaction::rollback ()
-{
-  abi_disp()->rollback ();
-  rollback_local ();
-
-  free_actions (&this->commit_actions);
-  run_actions (&this->undo_actions);
-  commit_allocations (true);
-  revert_cpp_exceptions ();
-
   if (this->eh_in_flight)
     {
       _Unwind_DeleteException ((_Unwind_Exception *) this->eh_in_flight);
@@ -194,46 +322,87 @@  _ITM_abortTransaction (_ITM_abortReason reason)
   if (tx->state & gtm_transaction::STATE_IRREVOCABLE)
     abort ();
 
-  tx->rollback ();
-  abi_disp()->fini ();
+  // If the current method does not support closed nesting, we are nested, and
+  // we can restart, then restart with a method that supports closed nesting.
+  abi_dispatch *disp = abi_disp();
+  if (!disp->closed_nesting())
+    tx->restart(RESTART_CLOSED_NESTING);
+
+  // Roll back to innermost transaction.
+  if (tx->parent_txns.size() > 0)
+    {
+      // The innermost transaction is a nested transaction.
+      gtm_transaction_cp *cp = tx->parent_txns.pop();
+      uint32_t longjmp_prop = tx->prop;
+      gtm_jmpbuf longjmp_jb = tx->jb;
+
+      tx->rollback (cp);
+      abi_disp()->fini ();
 
-  if (tx->state & gtm_transaction::STATE_SERIAL)
-    gtm_transaction::serial_lock.write_unlock ();
+      // Jump to nested transaction (use the saved jump buffer).
+      GTM_longjmp (&longjmp_jb, a_abortTransaction | a_restoreLiveVariables,
+          longjmp_prop);
+    }
   else
-    gtm_transaction::serial_lock.read_unlock ();
+    {
+      // There is no nested transaction, so roll back to outermost transaction.
+      tx->rollback ();
+      abi_disp()->fini ();
 
-  set_gtm_tx (tx->prev);
-  delete tx;
+      // Aborting an outermost transaction finishes execution of the whole
+      // transaction. Therefore, reset transaction state.
+      if (tx->state & gtm_transaction::STATE_SERIAL)
+        gtm_transaction::serial_lock.write_unlock ();
+      else
+        gtm_transaction::serial_lock.read_unlock ();
+      tx->state = 0;
 
-  GTM_longjmp (&tx->jb, a_abortTransaction | a_restoreLiveVariables, tx->prop);
+      GTM_longjmp (&tx->jb, a_abortTransaction | a_restoreLiveVariables,
+          tx->prop);
+    }
 }
 
 bool
 GTM::gtm_transaction::trycommit ()
 {
-  if (abi_disp()->trycommit ())
+  nesting--;
+
+  // Skip any real commit for elided transactions.
+  if (nesting > 0 && (parent_txns.size() == 0 ||
+      nesting > parent_txns[parent_txns.size() - 1].nesting))
+    return true;
+
+  if (nesting > 0)
     {
-      commit_local ();
-      free_actions (&this->undo_actions);
-      run_actions (&this->commit_actions);
-      commit_allocations (false);
+      // Commit of a closed-nested transaction. Remove one checkpoint and add
+      // any effects of this transaction to the parent transaction.
+      gtm_transaction_cp *cp = parent_txns.pop();
+      commit_allocations(false, &cp->alloc_actions);
+      cp->commit(this);
       return true;
     }
-  return false;
-}
 
-bool
-GTM::gtm_transaction::trycommit_and_finalize ()
-{
-  if (trycommit ())
+  // Commit of an outermost transaction.
+  if (abi_disp()->trycommit ())
     {
+      commit_local ();
+      // FIXME: run after ensuring privatization safety:
+      commit_user_actions ();
+      commit_allocations (false, 0);
       abi_disp()->fini ();
-      set_gtm_tx (this->prev);
-      delete this;
-      if (this->state & gtm_transaction::STATE_SERIAL)
+
+      // Reset transaction state.
+      cxa_catch_count = 0;
+      cxa_unthrown = NULL;
+
+      // TODO can release SI mode before committing user actions? If so,
+      // we can release before ensuring privatization safety too.
+      if (state & gtm_transaction::STATE_SERIAL)
 	gtm_transaction::serial_lock.write_unlock ();
       else
 	gtm_transaction::serial_lock.read_unlock ();
+      state = 0;
+
       return true;
     }
   return false;
@@ -242,24 +411,21 @@  GTM::gtm_transaction::trycommit_and_finalize ()
 void ITM_NORETURN
 GTM::gtm_transaction::restart (gtm_restart_reason r)
 {
-  uint32_t actions;
-
+  // Roll back to outermost transaction. Do not reset transaction state because
+  // we will continue executing this transaction.
   rollback ();
   decide_retry_strategy (r);
 
-  actions = a_runInstrumentedCode | a_restoreLiveVariables;
-  if ((this->prop & pr_uninstrumentedCode)
-      && (this->state & gtm_transaction::STATE_IRREVOCABLE))
-    actions = a_runUninstrumentedCode | a_restoreLiveVariables;
-
-  GTM_longjmp (&this->jb, actions, this->prop);
+  GTM_longjmp (&this->jb,
+      choose_code_path(prop, abi_disp()) | a_restoreLiveVariables,
+      this->prop);
 }
 
 void ITM_REGPARM
 _ITM_commitTransaction(void)
 {
   gtm_transaction *tx = gtm_tx();
-  if (!tx->trycommit_and_finalize ())
+  if (!tx->trycommit ())
     tx->restart (RESTART_VALIDATE_COMMIT);
 }
 
@@ -267,7 +433,7 @@  void ITM_REGPARM
 _ITM_commitTransactionEH(void *exc_ptr)
 {
   gtm_transaction *tx = gtm_tx();
-  if (!tx->trycommit_and_finalize ())
+  if (!tx->trycommit ())
     {
       tx->eh_in_flight = exc_ptr;
       tx->restart (RESTART_VALIDATE_COMMIT);
diff --git a/libitm/dispatch.h b/libitm/dispatch.h
index 3643503..0ab5c4e 100644
--- a/libitm/dispatch.h
+++ b/libitm/dispatch.h
@@ -234,6 +234,8 @@  void ITM_REGPARM _ITM_memset##WRITE(void *dst, int c, size_t size) \
 
 namespace GTM HIDDEN {
 
+struct gtm_transaction_cp;
+
 // This pass-through method is the basis for other methods.
 // It can be used for serial-irrevocable mode.
 struct abi_dispatch
@@ -248,15 +250,24 @@  private:
 
 public:
   virtual bool trycommit() = 0;
-  virtual void rollback() = 0;
+  virtual void rollback(gtm_transaction_cp *cp = 0) = 0;
   virtual void reinit() = 0;
 
   // Use fini instead of dtor to support a static subclasses that uses
   // a unique object and so we don't want to destroy it from common code.
   virtual void fini() = 0;
 
+  // Return an alternative method that is compatible with the current
+  // method but supports closed nesting. Return zero if there is none.
+  virtual abi_dispatch* closed_nesting_alternative() { return 0; }
+
   bool read_only () const { return m_read_only; }
   bool write_through() const { return m_write_through; }
+  bool can_run_uninstrumented_code() const
+  {
+    return m_can_run_uninstrumented_code;
+  }
+  bool closed_nesting() const { return m_closed_nesting; }
 
   static void *operator new(size_t s) { return xmalloc (s); }
   static void operator delete(void *p) { free (p); }
@@ -275,7 +286,13 @@  public:
 protected:
   const bool m_read_only;
   const bool m_write_through;
-  abi_dispatch(bool ro, bool wt) : m_read_only(ro), m_write_through(wt) { }
+  const bool m_can_run_uninstrumented_code;
+  const bool m_closed_nesting;
+  abi_dispatch(bool ro, bool wt, bool uninstrumented, bool closed_nesting) :
+    m_read_only(ro), m_write_through(wt),
+    m_can_run_uninstrumented_code(uninstrumented),
+    m_closed_nesting(closed_nesting)
+  { }
 };
 
 }
diff --git a/libitm/eh_cpp.cc b/libitm/eh_cpp.cc
index bd83f72..35c0b50 100644
--- a/libitm/eh_cpp.cc
+++ b/libitm/eh_cpp.cc
@@ -72,14 +72,37 @@  _ITM_cxa_end_catch (void)
 }
 
 void
-GTM::gtm_transaction::revert_cpp_exceptions (void)
+GTM::gtm_transaction::revert_cpp_exceptions (gtm_transaction_cp *cp)
 {
-  if (this->cxa_unthrown || this->cxa_catch_count)
+  if (cp)
     {
-      __cxa_tm_cleanup (this->cxa_unthrown, this->eh_in_flight,
-			this->cxa_catch_count);
-      this->cxa_catch_count = 0;
-      this->cxa_unthrown = NULL;
-      this->eh_in_flight = NULL;
+      // If rolling back a nested transaction, only clean up unthrown
+      // exceptions since the last checkpoint. Always reset eh_in_flight
+      // because it just contains the argument provided to
+      // _ITM_commitTransactionEH
+      void *unthrown =
+          (cxa_unthrown != cp->cxa_unthrown ? cxa_unthrown : NULL);
+      assert (cxa_catch_count > cp->cxa_catch_count);
+      uint32_t catch_count = cxa_catch_count - cp->cxa_catch_count;
+      if (unthrown || catch_count)
+        {
+          __cxa_tm_cleanup (unthrown, this->eh_in_flight, catch_count);
+          cxa_catch_count = cp->cxa_catch_count;
+          cxa_unthrown = cp->cxa_unthrown;
+          this->eh_in_flight = NULL;
+        }
+    }
+  else
+    {
+      // Both cxa_catch_count and cxa_unthrown are maximal because EH regions
+      // and transactions are properly nested.
+      if (this->cxa_unthrown || this->cxa_catch_count)
+        {
+          __cxa_tm_cleanup (this->cxa_unthrown, this->eh_in_flight,
+              this->cxa_catch_count);
+          this->cxa_catch_count = 0;
+          this->cxa_unthrown = NULL;
+          this->eh_in_flight = NULL;
+        }
     }
 }
diff --git a/libitm/libitm.h b/libitm/libitm.h
index abd4274..e961e81 100644
--- a/libitm/libitm.h
+++ b/libitm/libitm.h
@@ -93,8 +93,8 @@  typedef enum
    pr_preferUninstrumented	= 0x0800,
    /* Exception blocks are not used nor supported. */
    pr_exceptionBlock		= 0x1000,
+   pr_hasElse			= 0x2000,
    pr_readOnly			= 0x4000,
-   pr_hasElse			= 0x200000,
    pr_hasNoSimpleReads		= 0x400000
 } _ITM_codeProperties;
 
diff --git a/libitm/libitm.texi b/libitm/libitm.texi
index 046b0bd..8d7aef4 100644
--- a/libitm/libitm.texi
+++ b/libitm/libitm.texi
@@ -314,13 +314,16 @@  nontransactionally).
 
 @subsection User-registered commit and undo actions
 
-The order in which commit or undo actions are executed is undefined. It is also
-undefined whether privatization safety has been ensured by the time the
-transactions are executed. The ordering of undo actions and the roll-back of
-data transfers is undefined.
+Commit actions will get executed in the same order in which the respective
+calls to @code{_ITM_addUserCommitAction} happened. Only
+@code{_ITM_noTransactionId} is allowed as value for the
+@code{resumingTransactionId} argument. Commit actions get executed after
+privatization safety has been ensured.
 
-However, the ABI should specify ordering guarantees where necessary (in
-particular, w.r.t. privatization safety).
+Undo actions will get executed in reverse order compared to the order in which
+the respective calls to @code{_ITM_addUserUndoAction} happened. The ordering of
+undo actions w.r.t. the roll-back of other actions (e.g., data transfers or
+memory allocations) is undefined.
 
 @code{_ITM_dropReferences} is not supported currently because its semantics and
 the intention behind it is not entirely clear. The
@@ -415,7 +418,31 @@  specification. Likewise, the TM runtime must ensure privatization safety.
 @node Internals
 @chapter Internals
 
-TODO: SI-mode implementation, method sets, ...
+@section Nesting: flat vs. closed
+
+We support two different kinds of nesting of transactions. In the case of
+@emph{flat nesting}, the nesting structure is flattened and all nested
+transactions are subsumed by the enclosing transaction. In contrast,
+with @emph{closed nesting}, nested transactions that have not yet committed
+can be rolled back separately from the enclosing transactions; when they
+commit, they are subsumed by the enclosing transaction, and their effects
+will be finally committed when the outermost transaction commits.
+@emph{Open nesting} (where nested transactions can commit independently of the
+enclosing transactions) are not supported.
+
+Flat nesting is the default nesting mode, but closed nesting is supported and
+used when transactions contain user-controlled aborts
+(@code{__transaction_cancel} statements). We assume that user-controlled
+aborts are rare in typical code and used mostly in exceptional situations.
+Thus, it makes more sense to use flat nesting by default to avoid the
+performance overhead of the additional checkpoints required for closed
+nesting. User-controlled aborts will correctly abort the innermost enclosing
+transaction, whereas the whole (i.e., outermost) transaction will be restarted
+otherwise (e.g., when a transaction encounters data conflicts during
+optimistic execution).
+
+
+@strong{TODO}: SI-mode implementation, method sets, ...
 
 @c ---------------------------------------------------------------------
 @c GNU General Public License
diff --git a/libitm/libitm_i.h b/libitm/libitm_i.h
index 01b2e4a..4cc0a70 100644
--- a/libitm/libitm_i.h
+++ b/libitm/libitm_i.h
@@ -82,6 +82,7 @@  enum gtm_restart_reason
   RESTART_VALIDATE_COMMIT,
   RESTART_SERIAL_IRR,
   RESTART_NOT_READONLY,
+  RESTART_CLOSED_NESTING,
   NUM_RESTARTS
 };
 
@@ -96,12 +97,43 @@  struct gtm_alloc_action
 // This type is private to local.c.
 struct gtm_local_undo;
 
-// This type is private to useraction.c.
-struct gtm_user_action;
+struct gtm_transaction;
+
+// A transaction checkpoint: data that has to saved and restored when doing
+// closed nesting.
+struct gtm_transaction_cp
+{
+  gtm_jmpbuf jb;
+  size_t local_undo_size;
+  aa_tree<uintptr_t, gtm_alloc_action> alloc_actions;
+  size_t user_actions_size;
+  _ITM_transactionId_t id;
+  uint32_t prop;
+  uint32_t cxa_catch_count;
+  void *cxa_unthrown;
+  // We might want to use a different but compatible dispatch method for
+  // a nested transaction.
+  abi_dispatch *disp;
+  // Nesting level of this checkpoint (1 means that this is a checkpoint of
+  // the outermost transaction).
+  uint32_t nesting;
+
+  void save(gtm_transaction* tx);
+  void commit(gtm_transaction* tx);
+};
 
 // All data relevant to a single transaction.
 struct gtm_transaction
 {
+
+  struct user_action
+  {
+    _ITM_userCommitFunction fn;
+    void *arg;
+    bool on_commit;
+    _ITM_transactionId_t resuming_id;
+  };
+
   // The jump buffer by which GTM_longjmp restarts the transaction.
   // This field *must* be at the beginning of the transaction.
   gtm_jmpbuf jb;
@@ -112,12 +144,8 @@  struct gtm_transaction
   // Data used by alloc.c for the malloc/free undo log.
   aa_tree<uintptr_t, gtm_alloc_action> alloc_actions;
 
-  // Data used by useraction.c for the user defined undo log.
-  struct gtm_user_action *commit_actions;
-  struct gtm_user_action *undo_actions;
-
-  // A pointer to the "outer" transaction.
-  struct gtm_transaction *prev;
+  // Data used by useraction.c for the user-defined commit/abort handlers.
+  vector<user_action> user_actions;
 
   // A numerical identifier for this transaction.
   _ITM_transactionId_t id;
@@ -125,13 +153,16 @@  struct gtm_transaction
   // The _ITM_codeProperties of this transaction as given by the compiler.
   uint32_t prop;
 
-  // The nesting depth of this transaction.
+  // The nesting depth for subsequently started transactions. This variable
+  // will be set to 1 when starting an outermost transaction.
   uint32_t nesting;
 
   // Set if this transaction owns the serial write lock.
+  // Can be reset only when restarting the outermost transaction.
   static const uint32_t STATE_SERIAL		= 0x0001;
   // Set if the serial-irrevocable dispatch table is installed.
   // Implies that no logging is being done, and abort is not possible.
+  // Can be reset only when restarting the outermost transaction.
   static const uint32_t STATE_IRREVOCABLE	= 0x0002;
 
   // A bitmask of the above.
@@ -142,6 +173,9 @@  struct gtm_transaction
   void *cxa_unthrown;
   void *eh_in_flight;
 
+  // Checkpoints for closed nesting.
+  vector<gtm_transaction_cp> parent_txns;
+
   // Data used by retry.c for deciding what STM implementation should
   // be used for the next iteration of the transaction.
   uint32_t restart_reason[NUM_RESTARTS];
@@ -153,7 +187,7 @@  struct gtm_transaction
   static gtm_rwlock serial_lock;
 
   // In alloc.cc
-  void commit_allocations (bool);
+  void commit_allocations (bool, aa_tree<uintptr_t, gtm_alloc_action>*);
   void record_allocation (void *, void (*)(void *));
   void forget_allocation (void *, void (*)(void *));
   void drop_references_allocations (const void *ptr)
@@ -162,9 +196,8 @@  struct gtm_transaction
   }
 
   // In beginend.cc
-  void rollback ();
+  void rollback (gtm_transaction_cp *cp = 0);
   bool trycommit ();
-  bool trycommit_and_finalize ();
   void restart (gtm_restart_reason) ITM_NORETURN;
 
   static void *operator new(size_t);
@@ -176,11 +209,11 @@  struct gtm_transaction
 	__asm__("GTM_begin_transaction") ITM_REGPARM;
 
   // In eh_cpp.cc
-  void revert_cpp_exceptions ();
+  void revert_cpp_exceptions (gtm_transaction_cp *cp = 0);
 
   // In local.cc
   void commit_local (void);
-  void rollback_local (void);
+  void rollback_local (size_t until_size = 0);
   void drop_references_local (const void *, size_t);
 
   // In retry.cc
@@ -191,8 +224,8 @@  struct gtm_transaction
   void serialirr_mode ();
 
   // In useraction.cc
-  static void run_actions (struct gtm_user_action **);
-  static void free_actions (struct gtm_user_action **);
+  void rollback_user_actions (size_t until_size = 0);
+  void commit_user_actions ();
 };
 
 } // namespace GTM
diff --git a/libitm/local.cc b/libitm/local.cc
index a1a5655..3da67ab 100644
--- a/libitm/local.cc
+++ b/libitm/local.cc
@@ -48,22 +48,21 @@  gtm_transaction::commit_local ()
 }
 
 void
-gtm_transaction::rollback_local (void)
+gtm_transaction::rollback_local (size_t until_size)
 {
   size_t i, n = local_undo.size();
 
   if (n > 0)
     {
-      for (i = n; i-- > 0; )
+      for (i = n; i-- > until_size; )
 	{
-	  gtm_local_undo *u = local_undo[i];
+	  gtm_local_undo *u = *local_undo.pop();
 	  if (u)
 	    {
 	      memcpy (u->addr, u->saved, u->len);
 	      free (u);
 	    }
 	}
-      local_undo.clear();
     }
 }
 
diff --git a/libitm/method-serial.cc b/libitm/method-serial.cc
index a6fbc7f..a93b991 100644
--- a/libitm/method-serial.cc
+++ b/libitm/method-serial.cc
@@ -38,7 +38,7 @@  namespace {
 class serial_dispatch : public abi_dispatch
 {
  public:
-  serial_dispatch() : abi_dispatch(false, true) { }
+  serial_dispatch() : abi_dispatch(false, true, true, false) { }
 
  protected:
   // Transactional loads and stores simply access memory directly.
@@ -74,12 +74,19 @@  class serial_dispatch : public abi_dispatch
   CREATE_DISPATCH_METHODS_MEM()
 
   virtual bool trycommit() { return true; }
-  virtual void rollback() { abort(); }
+  virtual void rollback(gtm_transaction_cp *cp) { abort(); }
   virtual void reinit() { }
   virtual void fini() { }
+
+  virtual abi_dispatch* closed_nesting_alternative()
+  {
+    // For nested transactions with an instrumented code path, we can do
+    // undo logging.
+    return GTM::dispatch_serial();
+  }
 };
 
-class serial_dispatch_ul : public serial_dispatch
+class serial_dispatch_ul : public abi_dispatch
 {
 protected:
   static void log(const void *addr, size_t len)
@@ -119,12 +126,17 @@  public:
     ::memset(dst, c, size);
   }
 
+  virtual bool trycommit() { return true; }
   // Local undo will handle this.
   // trydropreference() need not be changed either.
-  virtual void rollback() { }
+  virtual void rollback(gtm_transaction_cp *cp) { }
+  virtual void reinit() { }
+  virtual void fini() { }
 
   CREATE_DISPATCH_METHODS(virtual, )
   CREATE_DISPATCH_METHODS_MEM()
+
+  serial_dispatch_ul() : abi_dispatch(false, true, false, true) { }
 };
 
 } // anon namespace
diff --git a/libitm/query.cc b/libitm/query.cc
index 1f03ddf..4905fc6 100644
--- a/libitm/query.cc
+++ b/libitm/query.cc
@@ -44,7 +44,7 @@  _ITM_howExecuting ITM_REGPARM
 _ITM_inTransaction (void)
 {
   struct gtm_transaction *tx = gtm_tx();
-  if (tx)
+  if (tx && (tx->nesting > 0))
     {
       if (tx->state & gtm_transaction::STATE_IRREVOCABLE)
 	return inIrrevocableTransaction;
diff --git a/libitm/retry.cc b/libitm/retry.cc
index 8e586de..c3b3a1d 100644
--- a/libitm/retry.cc
+++ b/libitm/retry.cc
@@ -35,6 +35,8 @@  GTM::gtm_transaction::decide_retry_strategy (gtm_restart_reason r)
   bool retry_irr = (r == RESTART_SERIAL_IRR);
   bool retry_serial = (this->restart_total > 100 || retry_irr);
 
+  if (r == RESTART_CLOSED_NESTING) retry_serial = true;
+
   if (retry_serial)
     {
       // In serialirr_mode we can succeed with the upgrade to
@@ -56,7 +58,7 @@  GTM::gtm_transaction::decide_retry_strategy (gtm_restart_reason r)
       // ??? We can only retry with dispatch_serial when the transaction
       // doesn't contain an abort.  TODO: Create a serial mode dispatch
       // that does logging in order to support abort.
-      if (this->prop & pr_hasNoAbort)
+      if ((this->prop & pr_hasNoAbort) && (r != RESTART_CLOSED_NESTING))
 	retry_irr = true;
     }
 
@@ -64,12 +66,13 @@  GTM::gtm_transaction::decide_retry_strategy (gtm_restart_reason r)
     {
       this->state = (STATE_SERIAL | STATE_IRREVOCABLE);
       disp->fini ();
-      disp = dispatch_serial ();
+      disp = dispatch_serialirr ();
       set_abi_disp (disp);
     }
   else
     {
-      GTM_fatal("internal error: unsupported mode");
+      disp = dispatch_serial();
+      set_abi_disp (disp);
     }
 }
 
diff --git a/libitm/useraction.cc b/libitm/useraction.cc
index adbe470..4042366 100644
--- a/libitm/useraction.cc
+++ b/libitm/useraction.cc
@@ -26,50 +26,28 @@ 
 
 namespace GTM HIDDEN {
 
-struct gtm_user_action
-{
-  struct gtm_user_action *next;
-  _ITM_userCommitFunction fn;
-  void *arg;
-};
-
-
 void
-gtm_transaction::run_actions (gtm_user_action **list)
+gtm_transaction::rollback_user_actions(size_t until_size)
 {
-  gtm_user_action *a = *list;
-
-  if (a == NULL)
-    return;
-  *list = NULL;
-
-  do
+  for (size_t s = user_actions.size(); s > until_size; s--)
     {
-      gtm_user_action *n = a->next;
-      a->fn (a->arg);
-      free (a);
-      a = n;
+      user_action *a = user_actions.pop();
+      if (!a->on_commit)
+        a->fn (a->arg);
     }
-  while (a);
 }
 
 
 void
-gtm_transaction::free_actions (gtm_user_action **list)
+gtm_transaction::commit_user_actions()
 {
-  gtm_user_action *a = *list;
-
-  if (a == NULL)
-    return;
-  *list = NULL;
-
-  do
+  for (vector<user_action>::iterator i = user_actions.begin(),
+      ie = user_actions.end(); i != ie; i++)
     {
-      gtm_user_action *n = a->next;
-      free (a);
-      a = n;
+      if (i->on_commit)
+        i->fn (i->arg);
     }
-  while (a);
+  user_actions.clear();
 }
 
 } // namespace GTM
@@ -80,17 +58,15 @@  void ITM_REGPARM
 _ITM_addUserCommitAction(_ITM_userCommitFunction fn,
 			 _ITM_transactionId_t tid, void *arg)
 {
-  gtm_transaction *tx;
-  gtm_user_action *a;
-
-  for (tx = gtm_tx(); tx->id != tid; tx = tx->prev)
-    continue;
-
-  a = (gtm_user_action *) xmalloc (sizeof (*a));
-  a->next = tx->commit_actions;
+  gtm_transaction *tx = gtm_tx();
+  if (tid != _ITM_noTransactionId)
+    GTM_fatal("resumingTransactionId in _ITM_addUserCommitAction must be "
+              "_ITM_noTransactionId");
+  gtm_transaction::user_action *a = tx->user_actions.push();
   a->fn = fn;
   a->arg = arg;
-  tx->commit_actions = a;
+  a->on_commit = true;
+  a->resuming_id = tid;
 }
 
 
@@ -98,11 +74,8 @@  void ITM_REGPARM
 _ITM_addUserUndoAction(_ITM_userUndoFunction fn, void * arg)
 {
   gtm_transaction *tx = gtm_tx();
-  gtm_user_action *a;
-
-  a = (gtm_user_action *) xmalloc (sizeof (*a));
-  a->next = tx->undo_actions;
+  gtm_transaction::user_action *a = tx->user_actions.push();
   a->fn = fn;
   a->arg = arg;
-  tx->undo_actions = a;
+  a->on_commit = false;
 }