From patchwork Sat Jul 9 14:30:19 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Torvald Riegel X-Patchwork-Id: 103979 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) by ozlabs.org (Postfix) with SMTP id 53DC71007D1 for ; Sun, 10 Jul 2011 00:30:48 +1000 (EST) Received: (qmail 5907 invoked by alias); 9 Jul 2011 14:30:46 -0000 Received: (qmail 5892 invoked by uid 22791); 9 Jul 2011 14:30:42 -0000 X-SWARE-Spam-Status: No, hits=-3.4 required=5.0 tests=AWL, BAYES_00, KAM_STOCKTIP, RCVD_IN_DNSWL_HI, SPF_HELO_PASS, TW_CP, TW_CX, TW_GJ, TW_RW, T_RP_MATCHES_RCVD X-Spam-Check-By: sourceware.org Received: from mx1.redhat.com (HELO mx1.redhat.com) (209.132.183.28) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Sat, 09 Jul 2011 14:30:22 +0000 Received: from int-mx01.intmail.prod.int.phx2.redhat.com (int-mx01.intmail.prod.int.phx2.redhat.com [10.5.11.11]) by mx1.redhat.com (8.14.4/8.14.4) with ESMTP id p69EUMfT005136 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK) for ; Sat, 9 Jul 2011 10:30:22 -0400 Received: from [10.36.4.119] (vpn1-4-119.ams2.redhat.com [10.36.4.119]) by int-mx01.intmail.prod.int.phx2.redhat.com (8.13.8/8.13.8) with ESMTP id p69EUKT2018359; Sat, 9 Jul 2011 10:30:20 -0400 Subject: Re: [trans-mem] Beginning of refactoring From: Torvald Riegel To: GCC Patches Cc: Richard Henderson In-Reply-To: <1306357828.13348.423.camel@triegel.csb> References: <1306357828.13348.423.camel@triegel.csb> Date: Sat, 09 Jul 2011 16:30:19 +0200 Message-ID: <1310221819.5106.1054.camel@triegel.csb> Mime-Version: 1.0 X-IsSubscribed: yes Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org 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 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. 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 . This file is part of the GNU Transactional Memory Library (libitm). @@ -141,6 +141,8 @@ class aa_tree : public aa_tree_key aa_tree() = default; ~aa_tree() { clear(); } + static void *operator new (size_t s, aa_tree* p) { return p; } + DATA *find(KEY k) const { node_ptr n = static_cast(base::find (k)); @@ -160,6 +162,13 @@ class aa_tree : public aa_tree_key delete n; } + node_ptr remove(KEY k, DATA** data) + { + node_ptr n = static_cast(base::erase (k)); + *data = (n ? &n->data : 0); + return n; + } + void clear() { node_ptr n = static_cast(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 . 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* 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(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::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* 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(); + + // 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 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 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_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 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*); 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::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; }