[trans-mem] Beginning of refactoring

On Tue, 2011-07-19 at 01:19 +0200, Torvald Riegel wrote:
> 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?
> 

This time with patches attached, sorry.
commit 267504991b7b6724f5fee633045dfbdd363cc754
Author: Torvald Riegel <triegel@redhat.com>
Date:   Mon Jul 18 22:54:34 2011 +0200

    New erase method and placement new for aatree.
    
            * aatree.h (aa_tree::remove): New.
            (aa_tree::operator new): Add placement new.
commit ca8b345e703109038617bf75693f6b5e8cb43019
Author: Torvald Riegel <triegel@redhat.com>
Date:   Mon Jul 18 23:06:19 2011 +0200

    Change pr_hasElse to the value specified in the ABI.
    
            * libitm.h (_ITM_codeProperties): Change pr_hasElse to the ABI's value.

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;
commit 7bc4fad41e8a5a2efaba6fc0d272e79357d3877f
Author: Torvald Riegel <triegel@redhat.com>
Date:   Mon Jul 18 23:18:13 2011 +0200

    Add information to dispatch about closed nesting and uninstrumented code.
    
            * 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.

diff --git a/libitm/dispatch.h b/libitm/dispatch.h
index 3643503..38f1342 100644
--- a/libitm/dispatch.h
+++ b/libitm/dispatch.h
@@ -255,8 +255,17 @@ public:
   // 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 +284,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/method-serial.cc b/libitm/method-serial.cc
index a6fbc7f..009d221 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.
@@ -77,9 +77,16 @@ class serial_dispatch : public abi_dispatch
   virtual void rollback() { 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 reinit() { }
+  virtual void fini() { }
 
   CREATE_DISPATCH_METHODS(virtual, )
   CREATE_DISPATCH_METHODS_MEM()
+
+  serial_dispatch_ul() : abi_dispatch(false, true, false, true) { }
 };
 
 } // anon namespace
commit 10732b9b900e63d4b38e054b1175080ccdd2fa52
Author: Torvald Riegel <triegel@redhat.com>
Date:   Tue Jul 19 00:10:11 2011 +0200

    Use vector instead of list to store user actions.
    
    	* useraction.cc: Use vector instead of list to store actions.
    	Also support partial rollbacks for closed nesting.
    	* libitm_i.h (GTM::gtm_transaction::user_action): Same.
    	* beginend.cc: Same.

diff --git a/libitm/beginend.cc b/libitm/beginend.cc
index 9b16973..26dbaf1 100644
--- a/libitm/beginend.cc
+++ b/libitm/beginend.cc
@@ -171,8 +171,7 @@ GTM::gtm_transaction::rollback ()
   abi_disp()->rollback ();
   rollback_local ();
 
-  free_actions (&this->commit_actions);
-  run_actions (&this->undo_actions);
+  rollback_user_actions();
   commit_allocations (true);
   revert_cpp_exceptions ();
 
@@ -214,8 +213,7 @@ GTM::gtm_transaction::trycommit ()
   if (abi_disp()->trycommit ())
     {
       commit_local ();
-      free_actions (&this->undo_actions);
-      run_actions (&this->commit_actions);
+      commit_user_actions();
       commit_allocations (false);
       return true;
     }
diff --git a/libitm/libitm_i.h b/libitm/libitm_i.h
index 01b2e4a..31584ac 100644
--- a/libitm/libitm_i.h
+++ b/libitm/libitm_i.h
@@ -96,12 +96,19 @@ 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;
 
 // 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 +119,10 @@ 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;
@@ -191,8 +196,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/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;
 }
commit 21dc1b25dccfc5bec97886c80f135623c38a0aba
Author: Torvald Riegel <triegel@redhat.com>
Date:   Tue Jul 19 00:35:56 2011 +0200

    Add closed nesting as restart reason.
    
    	* libitm_i.h: Add closed nesting as restart reason.
    	* retry.cc (GTM::gtm_transaction::decide_retry_strategy): Same.

diff --git a/libitm/libitm_i.h b/libitm/libitm_i.h
index 31584ac..9857087 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
 };
 
diff --git a/libitm/retry.cc b/libitm/retry.cc
index 8e586de..bfca2ca 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
@@ -54,9 +56,8 @@ 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)
+      // doesn't contain an abort.
+      if ((this->prop & pr_hasNoAbort) && (r != RESTART_CLOSED_NESTING))
 	retry_irr = true;
     }
 
@@ -64,12 +65,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);
     }
 }
commit c3fc59da237c51dfa2aea25069080a74cb2fdc12
Author: Torvald Riegel <triegel@redhat.com>
Date:   Tue Jul 19 00:54:23 2011 +0200

    Make flat nesting the default, use closed nesting on demand.
    
            * local.cc (gtm_transaction::rollback_local): Support closed nesting.
            * eh_cpp.cc (GTM::gtm_transaction::revert_cpp_exceptions): Same.
    	* dispatch.h: Same.
    	* 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.
            * libitm_i.h (GTM::gtm_transaction_cp): New helper struct for nesting.
            (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.texi: Update user action section, add description of nesting.

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 26dbaf1..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,57 +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 ();
-
-  rollback_user_actions();
-  commit_allocations (true);
-  revert_cpp_exceptions ();
-
   if (this->eh_in_flight)
     {
       _Unwind_DeleteException ((_Unwind_Exception *) this->eh_in_flight);
@@ -193,45 +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 ();
-      commit_user_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;
@@ -240,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);
 }
 
@@ -265,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 38f1342..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,7 +250,7 @@ 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
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.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 9857087..4cc0a70 100644
--- a/libitm/libitm_i.h
+++ b/libitm/libitm_i.h
@@ -97,6 +97,30 @@ struct gtm_alloc_action
 // This type is private to local.c.
 struct gtm_local_undo;
 
+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
@@ -120,8 +144,6 @@ struct gtm_transaction
   // Data used by alloc.c for the malloc/free undo log.
   aa_tree<uintptr_t, gtm_alloc_action> alloc_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;
 
@@ -131,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.
@@ -148,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];
@@ -159,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)
@@ -168,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);
@@ -182,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
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 009d221..a93b991 100644
--- a/libitm/method-serial.cc
+++ b/libitm/method-serial.cc
@@ -74,7 +74,7 @@ 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() { }
 
@@ -129,7 +129,7 @@ public:
   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() { }
 
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;


[trans-mem] Beginning of refactoring

Commit Message

Comments

Patch