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 <trie...@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.
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 <r...@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);
commit ca8b345e703109038617bf75693f6b5e8cb43019
Author: Torvald Riegel <trie...@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 <trie...@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 <trie...@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 <trie...@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 <trie...@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 <r...@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;
