| \input texinfo @c -*-texinfo-*- |
| |
| @c %**start of header |
| @setfilename libitm.info |
| @settitle GNU libitm |
| @c %**end of header |
| |
| |
| @copying |
| Copyright @copyright{} 2011-2021 Free Software Foundation, Inc. |
| |
| Permission is granted to copy, distribute and/or modify this document |
| under the terms of the GNU Free Documentation License, Version 1.2 or |
| any later version published by the Free Software Foundation; with no |
| Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. |
| A copy of the license is included in the section entitled ``GNU |
| Free Documentation License''. |
| @end copying |
| |
| @ifinfo |
| @dircategory GNU Libraries |
| @direntry |
| * libitm: (libitm). GNU Transactional Memory Library |
| @end direntry |
| |
| This manual documents the GNU Transactional Memory Library. |
| |
| @insertcopying |
| @end ifinfo |
| |
| |
| @setchapternewpage odd |
| |
| @titlepage |
| @title The GNU Transactional Memory Library |
| @page |
| @vskip 0pt plus 1filll |
| @comment For the @value{version-GCC} Version* |
| @sp 1 |
| @insertcopying |
| @end titlepage |
| |
| @summarycontents |
| @contents |
| @page |
| |
| |
| @node Top |
| @top Introduction |
| @cindex Introduction |
| |
| This manual documents the usage and internals of libitm, the GNU Transactional |
| Memory Library. It provides transaction support for accesses to a process' |
| memory, enabling easy-to-use synchronization of accesses to shared memory by |
| several threads. |
| |
| |
| @comment |
| @comment When you add a new menu item, please keep the right hand |
| @comment aligned to the same column. Do not use tabs. This provides |
| @comment better formatting. |
| @comment |
| @menu |
| * Enabling libitm:: How to enable libitm for your applications. |
| * C/C++ Language Constructs for TM:: |
| Notes on the language-level interface supported |
| by gcc. |
| * The libitm ABI:: Notes on the external ABI provided by libitm. |
| * Internals:: Notes on libitm's internal synchronization. |
| * GNU Free Documentation License:: |
| How you can copy and share this manual. |
| * Library Index:: Index of this documentation. |
| @end menu |
| |
| |
| @c --------------------------------------------------------------------- |
| @c Enabling libitm |
| @c --------------------------------------------------------------------- |
| |
| @node Enabling libitm |
| @chapter Enabling libitm |
| |
| To activate support for TM in C/C++, the compile-time flag @option{-fgnu-tm} |
| must be specified. This enables TM language-level constructs such as |
| transaction statements (e.g., @code{__transaction_atomic}, @pxref{C/C++ |
| Language Constructs for TM} for details). |
| |
| @c --------------------------------------------------------------------- |
| @c C/C++ Language Constructs for TM |
| @c --------------------------------------------------------------------- |
| |
| @node C/C++ Language Constructs for TM |
| @chapter C/C++ Language Constructs for TM |
| |
| Transactions are supported in C++ and C in the form of transaction statements, |
| transaction expressions, and function transactions. In the following example, |
| both @code{a} and @code{b} will be read and the difference will be written to |
| @code{c}, all atomically and isolated from other transactions: |
| |
| @example |
| __transaction_atomic @{ c = a - b; @} |
| @end example |
| |
| Therefore, another thread can use the following code to concurrently update |
| @code{b} without ever causing @code{c} to hold a negative value (and without |
| having to use other synchronization constructs such as locks or C++11 |
| atomics): |
| |
| @example |
| __transaction_atomic @{ if (a > b) b++; @} |
| @end example |
| |
| GCC follows the @uref{https://sites.google.com/site/tmforcplusplus/, Draft |
| Specification of Transactional Language Constructs for C++ (v1.1)} in its |
| implementation of transactions. |
| |
| The precise semantics of transactions are defined in terms of the C++11/C11 |
| memory model (see the specification). Roughly, transactions provide |
| synchronization guarantees that are similar to what would be guaranteed when |
| using a single global lock as a guard for all transactions. Note that like |
| other synchronization constructs in C/C++, transactions rely on a |
| data-race-free program (e.g., a nontransactional write that is concurrent |
| with a transactional read to the same memory location is a data race). |
| |
| @c --------------------------------------------------------------------- |
| @c The libitm ABI |
| @c --------------------------------------------------------------------- |
| |
| @node The libitm ABI |
| @chapter The libitm ABI |
| |
| The ABI provided by libitm is basically equal to the Linux variant of Intel's |
| current TM ABI specification document (Revision 1.1, May 6 2009) but with the |
| differences listed in this chapter. It would be good if these changes would |
| eventually be merged into a future version of this specification. To ease |
| look-up, the following subsections mirror the structure of this specification. |
| |
| @section [No changes] Objectives |
| @section [No changes] Non-objectives |
| |
| @section Library design principles |
| @subsection [No changes] Calling conventions |
| @subsection [No changes] TM library algorithms |
| @subsection [No changes] Optimized load and store routines |
| @subsection [No changes] Aligned load and store routines |
| |
| @subsection Data logging functions |
| |
| The memory locations accessed with transactional loads and stores and the |
| memory locations whose values are logged must not overlap. This required |
| separation only extends to the scope of the execution of one transaction |
| including all the executions of all nested transactions. |
| |
| The compiler must be consistent (within the scope of a single transaction) |
| about which memory locations are shared and which are not shared with other |
| threads (i.e., data must be accessed either transactionally or |
| nontransactionally). Otherwise, non-write-through TM algorithms would not work. |
| |
| For memory locations on the stack, this requirement extends to only the |
| lifetime of the stack frame that the memory location belongs to (or the |
| lifetime of the transaction, whichever is shorter). Thus, memory that is |
| reused for several stack frames could be target of both data logging and |
| transactional accesses; however, this is harmless because these stack frames' |
| lifetimes will end before the transaction finishes. |
| |
| @subsection [No changes] Scatter/gather calls |
| @subsection [No changes] Serial and irrevocable mode |
| @subsection [No changes] Transaction descriptor |
| @subsection Store allocation |
| |
| There is no @code{getTransaction} function. |
| |
| @subsection [No changes] Naming conventions |
| |
| @subsection Function pointer encryption |
| |
| Currently, this is not implemented. |
| |
| |
| @section Types and macros list |
| |
| @code{_ITM_codeProperties} has changed, @pxref{txn-code-properties,,Starting a |
| transaction}. |
| @code{_ITM_srcLocation} is not used. |
| |
| |
| @section Function list |
| |
| @subsection Initialization and finalization functions |
| These functions are not part of the ABI. |
| |
| @subsection [No changes] Version checking |
| @subsection [No changes] Error reporting |
| @subsection [No changes] inTransaction call |
| |
| @subsection State manipulation functions |
| There is no @code{getTransaction} function. Transaction identifiers for |
| nested transactions will be ordered but not necessarily sequential (i.e., for |
| a nested transaction's identifier @var{IN} and its enclosing transaction's |
| identifier @var{IE}, it is guaranteed that @math{IN >= IE}). |
| |
| @subsection [No changes] Source locations |
| |
| @subsection Starting a transaction |
| |
| @subsubsection Transaction code properties |
| |
| @anchor{txn-code-properties} |
| The bit @code{hasNoXMMUpdate} is instead called @code{hasNoVectorUpdate}. |
| Iff it is set, vector register save/restore is not necessary for any target |
| machine. |
| |
| The @code{hasNoFloatUpdate} bit (@code{0x0010}) is new. Iff it is set, floating |
| point register save/restore is not necessary for any target machine. |
| |
| @code{undoLogCode} is not supported and a fatal runtime error will be raised |
| if this bit is set. It is not properly defined in the ABI why barriers |
| other than undo logging are not present; Are they not necessary (e.g., a |
| transaction operating purely on thread-local data) or have they been omitted by |
| the compiler because it thinks that some kind of global synchronization |
| (e.g., serial mode) might perform better? The specification suggests that the |
| latter might be the case, but the former seems to be more useful. |
| |
| The @code{readOnly} bit (@code{0x4000}) is new. @strong{TODO} Lexical or dynamic |
| scope? |
| |
| @code{hasNoRetry} is not supported. If this bit is not set, but |
| @code{hasNoAbort} is set, the library can assume that transaction |
| rollback will not be requested. |
| |
| It would be useful if the absence of externally-triggered rollbacks would be |
| reported for the dynamic scope as well, not just for the lexical scope |
| (@code{hasNoAbort}). Without this, a library cannot exploit this together |
| with flat nesting. |
| |
| @code{exceptionBlock} is not supported because exception blocks are not used. |
| |
| @subsubsection [No changes] Windows exception state |
| @subsubsection [No changes] Other machine state |
| |
| @subsubsection [No changes] Results from beginTransaction |
| |
| @subsection Aborting a transaction |
| |
| @code{_ITM_rollbackTransaction} is not supported. @code{_ITM_abortTransaction} |
| is supported but the abort reasons @code{exceptionBlockAbort}, |
| @code{TMConflict}, and @code{userRetry} are not supported. There are no |
| exception blocks in general, so the related cases also do not have to be |
| considered. To encode @code{__transaction_cancel [[outer]]}, compilers must |
| set the new @code{outerAbort} bit (@code{0x10}) additionally to the |
| @code{userAbort} bit in the abort reason. |
| |
| @subsection Committing a transaction |
| |
| The exception handling (EH) scheme is different. The Intel ABI requires the |
| @code{_ITM_tryCommitTransaction} function that will return even when the |
| commit failed and will have to be matched with calls to either |
| @code{_ITM_abortTransaction} or @code{_ITM_commitTransaction}. In contrast, |
| gcc relies on transactional wrappers for the functions of the Exception |
| Handling ABI and on one additional commit function (shown below). This allows |
| the TM to keep track of EH internally and thus it does not have to embed the |
| cleanup of EH state into the existing EH code in the program. |
| @code{_ITM_tryCommitTransaction} is not supported. |
| @code{_ITM_commitTransactionToId} is also not supported because the |
| propagation of thrown exceptions will not bypass commits of nested |
| transactions. |
| |
| @example |
| void _ITM_commitTransactionEH(void *exc_ptr) ITM_REGPARM; |
| void *_ITM_cxa_allocate_exception (size_t); |
| void _ITM_cxa_free_exception (void *exc_ptr); |
| void _ITM_cxa_throw (void *obj, void *tinfo, void (*dest) (void *)); |
| void *_ITM_cxa_begin_catch (void *exc_ptr); |
| void _ITM_cxa_end_catch (void); |
| @end example |
| |
| The EH scheme changed in version 6 of GCC. Previously, the compiler |
| added a call to @code{_ITM_commitTransactionEH} to commit a transaction if |
| an exception could be in flight at this position in the code; @code{exc_ptr} is |
| the address of the current exception and must be non-zero. Now, the |
| compiler must catch all exceptions that are about to be thrown out of a |
| transaction and call @code{_ITM_commitTransactionEH} from the catch clause, |
| with @code{exc_ptr} being zero. |
| |
| Note that the old EH scheme never worked completely in GCC's implementation; |
| libitm currently does not try to be compatible with the old scheme. |
| |
| The @code{_ITM_cxa...} functions are transactional wrappers for the respective |
| @code{__cxa...} functions and must be called instead of these in transactional |
| code. @code{_ITM_cxa_free_exception} is new in GCC 6. |
| |
| To support this EH scheme, libstdc++ needs to provide one additional function |
| (@code{_cxa_tm_cleanup}), which is used by the TM to clean up the exception |
| handling state while rolling back a transaction: |
| |
| @example |
| void __cxa_tm_cleanup (void *unthrown_obj, void *cleanup_exc, |
| unsigned int caught_count); |
| @end example |
| |
| Since GCC 6, @code{unthrown_obj} is not used anymore and always null; |
| prior to that, @code{unthrown_obj} is non-null if the program called |
| @code{__cxa_allocate_exception} for this exception but did not yet called |
| @code{__cxa_throw} for it. @code{cleanup_exc} is non-null if the program is |
| currently processing a cleanup along an exception path but has not caught this |
| exception yet. @code{caught_count} is the nesting depth of |
| @code{__cxa_begin_catch} within the transaction (which can be counted by the TM |
| using @code{_ITM_cxa_begin_catch} and @code{_ITM_cxa_end_catch}); |
| @code{__cxa_tm_cleanup} then performs rollback by essentially performing |
| @code{__cxa_end_catch} that many times. |
| |
| |
| |
| @subsection Exception handling support |
| |
| Currently, there is no support for functionality like |
| @code{__transaction_cancel throw} as described in the C++ TM specification. |
| Supporting this should be possible with the EH scheme explained previously |
| because via the transactional wrappers for the EH ABI, the TM is able to |
| observe and intercept EH. |
| |
| |
| @subsection [No changes] Transition to serial--irrevocable mode |
| @subsection [No changes] Data transfer functions |
| @subsection [No changes] Transactional memory copies |
| |
| @subsection Transactional versions of memmove |
| |
| If either the source or destination memory region is to be accessed |
| nontransactionally, then source and destination regions must not be |
| overlapping. The respective @code{_ITM_memmove} functions are still |
| available but a fatal runtime error will be raised if such regions do overlap. |
| To support this functionality, the ABI would have to specify how the |
| intersection of the regions has to be accessed (i.e., transactionally or |
| nontransactionally). |
| |
| @subsection [No changes] Transactional versions of memset |
| @subsection [No changes] Logging functions |
| |
| @subsection User-registered commit and undo actions |
| |
| 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. |
| |
| 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_getThreadnum} is not supported currently because its only purpose |
| is to provide a thread ID that matches some assumed performance tuning output, |
| but this output is not part of the ABI nor further defined by it. |
| |
| @code{_ITM_dropReferences} is not supported currently because its semantics and |
| the intention behind it is not entirely clear. The |
| specification suggests that this function is necessary because of certain |
| orderings of data transfer undos and the releasing of memory regions (i.e., |
| privatization). However, this ordering is never defined, nor is the ordering of |
| dropping references w.r.t. other events. |
| |
| @subsection [New] Transactional indirect calls |
| |
| Indirect calls (i.e., calls through a function pointer) within transactions |
| should execute the transactional clone of the original function (i.e., a clone |
| of the original that has been fully instrumented to use the TM runtime), if |
| such a clone is available. The runtime provides two functions to |
| register/deregister clone tables: |
| |
| @example |
| struct clone_entry |
| @{ |
| void *orig, *clone; |
| @}; |
| |
| void _ITM_registerTMCloneTable (clone_entry *table, size_t entries); |
| void _ITM_deregisterTMCloneTable (clone_entry *table); |
| @end example |
| |
| Registered tables must be writable by the TM runtime, and must be live |
| throughout the life-time of the TM runtime. |
| |
| @strong{TODO} The intention was always to drop the registration functions |
| entirely, and create a new ELF Phdr describing the linker-sorted table. Much |
| like what currently happens for @code{PT_GNU_EH_FRAME}. |
| This work kept getting bogged down in how to represent the @var{N} different |
| code generation variants. We clearly needed at least two---SW and HW |
| transactional clones---but there was always a suggestion of more variants for |
| different TM assumptions/invariants. |
| |
| The compiler can then use two TM runtime functions to perform indirect calls in |
| transactions: |
| @example |
| void *_ITM_getTMCloneOrIrrevocable (void *function) ITM_REGPARM; |
| void *_ITM_getTMCloneSafe (void *function) ITM_REGPARM; |
| @end example |
| |
| If there is a registered clone for supplied function, both will return a |
| pointer to the clone. If not, the first runtime function will attempt to switch |
| to serial--irrevocable mode and return the original pointer, whereas the second |
| will raise a fatal runtime error. |
| |
| @subsection [New] Transactional dynamic memory management |
| |
| @example |
| void *_ITM_malloc (size_t) |
| __attribute__((__malloc__)) ITM_PURE; |
| void *_ITM_calloc (size_t, size_t) |
| __attribute__((__malloc__)) ITM_PURE; |
| void _ITM_free (void *) ITM_PURE; |
| @end example |
| |
| These functions are essentially transactional wrappers for @code{malloc}, |
| @code{calloc}, and @code{free}. Within transactions, the compiler should |
| replace calls to the original functions with calls to the wrapper functions. |
| |
| libitm also provides transactional clones of C++ memory management functions |
| such as global operator new and delete. They are part of libitm for historic |
| reasons but do not need to be part of this ABI. |
| |
| |
| @section [No changes] Future Enhancements to the ABI |
| |
| @section Sample code |
| |
| The code examples might not be correct w.r.t. the current version of the ABI, |
| especially everything related to exception handling. |
| |
| |
| @section [New] Memory model |
| |
| The ABI should define a memory model and the ordering that is guaranteed for |
| data transfers and commit/undo actions, or at least refer to another memory |
| model that needs to be preserved. Without that, the compiler cannot ensure the |
| memory model specified on the level of the programming language (e.g., by the |
| C++ TM specification). |
| |
| For example, if a transactional load is ordered before another load/store, then |
| the TM runtime must also ensure this ordering when accessing shared state. If |
| not, this might break the kind of publication safety used in the C++ TM |
| specification. Likewise, the TM runtime must ensure privatization safety. |
| |
| |
| |
| @c --------------------------------------------------------------------- |
| @c Internals |
| @c --------------------------------------------------------------------- |
| |
| @node Internals |
| @chapter Internals |
| |
| @section TM methods and method groups |
| |
| libitm supports several ways of synchronizing transactions with each other. |
| These TM methods (or TM algorithms) are implemented in the form of |
| subclasses of @code{abi_dispatch}, which provide methods for |
| transactional loads and stores as well as callbacks for rollback and commit. |
| All methods that are compatible with each other (i.e., that let concurrently |
| running transactions still synchronize correctly even if different methods |
| are used) belong to the same TM method group. Pointers to TM methods can be |
| obtained using the factory methods prefixed with @code{dispatch_} in |
| @file{libitm_i.h}. There are two special methods, @code{dispatch_serial} and |
| @code{dispatch_serialirr}, that are compatible with all methods because they |
| run transactions completely in serial mode. |
| |
| @subsection TM method life cycle |
| |
| The state of TM methods does not change after construction, but they do alter |
| the state of transactions that use this method. However, because |
| per-transaction data gets used by several methods, @code{gtm_thread} is |
| responsible for setting an initial state that is useful for all methods. |
| After that, methods are responsible for resetting/clearing this state on each |
| rollback or commit (of outermost transactions), so that the transaction |
| executed next is not affected by the previous transaction. |
| |
| There is also global state associated with each method group, which is |
| initialized and shut down (@code{method_group::init()} and @code{fini()}) |
| when switching between method groups (see @file{retry.cc}). |
| |
| @subsection Selecting the default method |
| |
| The default method that libitm uses for freshly started transactions (but |
| not necessarily for restarted transactions) can be set via an environment |
| variable (@env{ITM_DEFAULT_METHOD}), whose value should be equal to the name |
| of one of the factory methods returning abi_dispatch subclasses but without |
| the "dispatch_" prefix (e.g., "serialirr" instead of |
| @code{GTM::dispatch_serialirr()}). |
| |
| Note that this environment variable is only a hint for libitm and might not |
| be supported in the future. |
| |
| |
| @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). |
| |
| |
| @section Locking conventions |
| |
| This section documents the locking scheme and rules for all uses of locking |
| in libitm. We have to support serial(-irrevocable) mode, which is implemented |
| using a global lock as explained next (called the @emph{serial lock}). To |
| simplify the overall design, we use the same lock as catch-all locking |
| mechanism for other infrequent tasks such as (de)registering clone tables or |
| threads. Besides the serial lock, there are @emph{per-method-group locks} that |
| are managed by specific method groups (i.e., groups of similar TM concurrency |
| control algorithms), and lock-like constructs for quiescence-based operations |
| such as ensuring privatization safety. |
| |
| Thus, the actions that participate in the libitm-internal locking are either |
| @emph{active transactions} that do not run in serial mode, @emph{serial |
| transactions} (which (are about to) run in serial mode), and management tasks |
| that do not execute within a transaction but have acquired the serial mode |
| like a serial transaction would do (e.g., to be able to register threads with |
| libitm). Transactions become active as soon as they have successfully used the |
| serial lock to announce this globally (@pxref{serial-lock-impl,,Serial lock |
| implementation}). Likewise, transactions become serial transactions as soon as |
| they have acquired the exclusive rights provided by the serial lock (i.e., |
| serial mode, which also means that there are no other concurrent active or |
| serial transactions). Note that active transactions can become serial |
| transactions when they enter serial mode during the runtime of the |
| transaction. |
| |
| @subsection State-to-lock mapping |
| |
| Application data is protected by the serial lock if there is a serial |
| transaction and no concurrently running active transaction (i.e., non-serial). |
| Otherwise, application data is protected by the currently selected method |
| group, which might use per-method-group locks or other mechanisms. Also note |
| that application data that is about to be privatized might not be allowed to be |
| accessed by nontransactional code until privatization safety has been ensured; |
| the details of this are handled by the current method group. |
| |
| libitm-internal state is either protected by the serial lock or accessed |
| through custom concurrent code. The latter applies to the public/shared part |
| of a transaction object and most typical method-group-specific state. |
| |
| The former category (protected by the serial lock) includes: |
| @itemize @bullet |
| @item The list of active threads that have used transactions. |
| @item The tables that map functions to their transactional clones. |
| @item The current selection of which method group to use. |
| @item Some method-group-specific data, or invariants of this data. For example, |
| resetting a method group to its initial state is handled by switching to the |
| same method group, so the serial lock protects such resetting as well. |
| @end itemize |
| In general, such state is immutable whenever there exists an active |
| (non-serial) transaction. If there is no active transaction, a serial |
| transaction (or a thread that is not currently executing a transaction but has |
| acquired the serial lock) is allowed to modify this state (but must of course |
| be careful to not surprise the current method group's implementation with such |
| modifications). |
| |
| @subsection Lock acquisition order |
| |
| To prevent deadlocks, locks acquisition must happen in a globally agreed-upon |
| order. Note that this applies to other forms of blocking too, but does not |
| necessarily apply to lock acquisitions that do not block (e.g., trylock() |
| calls that do not get retried forever). Note that serial transactions are |
| never return back to active transactions until the transaction has committed. |
| Likewise, active transactions stay active until they have committed. |
| Per-method-group locks are typically also not released before commit. |
| |
| Lock acquisition / blocking rules: |
| @itemize @bullet |
| |
| @item Transactions must become active or serial before they are allowed to |
| use method-group-specific locks or blocking (i.e., the serial lock must be |
| acquired before those other locks, either in serial or nonserial mode). |
| |
| @item Any number of threads that do not currently run active transactions can |
| block while trying to get the serial lock in exclusive mode. Note that active |
| transactions must not block when trying to upgrade to serial mode unless there |
| is no other transaction that is trying that (the latter is ensured by the |
| serial lock implementation. |
| |
| @item Method groups must prevent deadlocks on their locks. In particular, they |
| must also be prepared for another active transaction that has acquired |
| method-group-specific locks but is blocked during an attempt to upgrade to |
| being a serial transaction. See below for details. |
| |
| @item Serial transactions can acquire method-group-specific locks because there |
| will be no other active nor serial transaction. |
| |
| @end itemize |
| |
| There is no single rule for per-method-group blocking because this depends on |
| when a TM method might acquire locks. If no active transaction can upgrade to |
| being a serial transaction after it has acquired per-method-group locks (e.g., |
| when those locks are only acquired during an attempt to commit), then the TM |
| method does not need to consider a potential deadlock due to serial mode. |
| |
| If there can be upgrades to serial mode after the acquisition of |
| per-method-group locks, then TM methods need to avoid those deadlocks: |
| @itemize @bullet |
| @item When upgrading to a serial transaction, after acquiring exclusive rights |
| to the serial lock but before waiting for concurrent active transactions to |
| finish (@pxref{serial-lock-impl,,Serial lock implementation} for details), |
| we have to wake up all active transactions waiting on the upgrader's |
| per-method-group locks. |
| @item Active transactions blocking on per-method-group locks need to check the |
| serial lock and abort if there is a pending serial transaction. |
| @item Lost wake-ups have to be prevented (e.g., by changing a bit in each |
| per-method-group lock before doing the wake-up, and only blocking on this lock |
| using a futex if this bit is not group). |
| @end itemize |
| |
| @strong{TODO}: Can reuse serial lock for gl-*? And if we can, does it make |
| sense to introduce further complexity in the serial lock? For gl-*, we can |
| really only avoid an abort if we do -wb and -vbv. |
| |
| |
| @subsection Serial lock implementation |
| @anchor{serial-lock-impl} |
| |
| The serial lock implementation is optimized towards assuming that serial |
| transactions are infrequent and not the common case. However, the performance |
| of entering serial mode can matter because when only few transactions are run |
| concurrently or if there are few threads, then it can be efficient to run |
| transactions serially. |
| |
| The serial lock is similar to a multi-reader-single-writer lock in that there |
| can be several active transactions but only one serial transaction. However, |
| we do want to avoid contention (in the lock implementation) between active |
| transactions, so we split up the reader side of the lock into per-transaction |
| flags that are true iff the transaction is active. The exclusive writer side |
| remains a shared single flag, which is acquired using a CAS, for example. |
| On the fast-path, the serial lock then works similar to Dekker's algorithm but |
| with several reader flags that a serial transaction would have to check. |
| A serial transaction thus requires a list of all threads with potentially |
| active transactions; we can use the serial lock itself to protect this list |
| (i.e., only threads that have acquired the serial lock can modify this list). |
| |
| We want starvation-freedom for the serial lock to allow for using it to ensure |
| progress for potentially starved transactions (@pxref{progress-guarantees,, |
| Progress Guarantees} for details). However, this is currently not enforced by |
| the implementation of the serial lock. |
| |
| Here is pseudo-code for the read/write fast paths of acquiring the serial |
| lock (read-to-write upgrade is similar to write_lock: |
| @example |
| // read_lock: |
| tx->shared_state |= active; |
| __sync_synchronize(); // or STLD membar, or C++0x seq-cst fence |
| while (!serial_lock.exclusive) |
| if (spinning_for_too_long) goto slowpath; |
| |
| // write_lock: |
| if (CAS(&serial_lock.exclusive, 0, this) != 0) |
| goto slowpath; // writer-writer contention |
| // need a membar here, but CAS already has full membar semantics |
| bool need_blocking = false; |
| for (t: all txns) |
| @{ |
| for (;t->shared_state & active;) |
| if (spinning_for_too_long) @{ need_blocking = true; break; @} |
| @} |
| if (need_blocking) goto slowpath; |
| @end example |
| |
| Releasing a lock in this spin-lock version then just consists of resetting |
| @code{tx->shared_state} to inactive or clearing @code{serial_lock.exclusive}. |
| |
| However, we can't rely on a pure spinlock because we need to get the OS |
| involved at some time (e.g., when there are more threads than CPUs to run on). |
| Therefore, the real implementation falls back to a blocking slow path, either |
| based on pthread mutexes or Linux futexes. |
| |
| |
| @subsection Reentrancy |
| |
| libitm has to consider the following cases of reentrancy: |
| @itemize @bullet |
| |
| @item Transaction calls unsafe code that starts a new transaction: The outer |
| transaction will become a serial transaction before executing unsafe code. |
| Therefore, nesting within serial transactions must work, even if the nested |
| transaction is called from within uninstrumented code. |
| |
| @item Transaction calls either a transactional wrapper or safe code, which in |
| turn starts a new transaction: It is not yet defined in the specification |
| whether this is allowed. Thus, it is undefined whether libitm supports this. |
| |
| @item Code that starts new transactions might be called from within any part |
| of libitm: This kind of reentrancy would likely be rather complex and can |
| probably be avoided. Therefore, it is not supported. |
| |
| @end itemize |
| |
| @subsection Privatization safety |
| |
| Privatization safety is ensured by libitm using a quiescence-based approach. |
| Basically, a privatizing transaction waits until all concurrent active |
| transactions will either have finished (are not active anymore) or operate on |
| a sufficiently recent snapshot to not access the privatized data anymore. This |
| happens after the privatizing transaction has stopped being an active |
| transaction, so waiting for quiescence does not contribute to deadlocks. |
| |
| In method groups that need to ensure publication safety explicitly, active |
| transactions maintain a flag or timestamp in the public/shared part of the |
| transaction descriptor. Before blocking, privatizers need to let the other |
| transactions know that they should wake up the privatizer. |
| |
| @strong{TODO} Ho to implement the waiters? Should those flags be |
| per-transaction or at a central place? We want to avoid one wake/wait call |
| per active transactions, so we might want to use either a tree or combining |
| to reduce the syscall overhead, or rather spin for a long amount of time |
| instead of doing blocking. Also, it would be good if only the last transaction |
| that the privatizer waits for would do the wake-up. |
| |
| @subsection Progress guarantees |
| @anchor{progress-guarantees} |
| |
| Transactions that do not make progress when using the current TM method will |
| eventually try to execute in serial mode. Thus, the serial lock's progress |
| guarantees determine the progress guarantees of the whole TM. Obviously, we at |
| least need deadlock-freedom for the serial lock, but it would also be good to |
| provide starvation-freedom (informally, all threads will finish executing a |
| transaction eventually iff they get enough cycles). |
| |
| However, the scheduling of transactions (e.g., thread scheduling by the OS) |
| also affects the handling of progress guarantees by the TM. First, the TM |
| can only guarantee deadlock-freedom if threads do not get stopped. Likewise, |
| low-priority threads can starve if they do not get scheduled when other |
| high-priority threads get those cycles instead. |
| |
| If all threads get scheduled eventually, correct lock implementations will |
| provide deadlock-freedom, but might not provide starvation-freedom. We can |
| either enforce the latter in the TM's lock implementation, or assume that |
| the scheduling is sufficiently random to yield a probabilistic guarantee that |
| no thread will starve (because eventually, a transaction will encounter a |
| scheduling that will allow it to run). This can indeed work well in practice |
| but is not necessarily guaranteed to work (e.g., simple spin locks can be |
| pretty efficient). |
| |
| Because enforcing stronger progress guarantees in the TM has a higher runtime |
| overhead, we focus on deadlock-freedom right now and assume that the threads |
| will get scheduled eventually by the OS (but don't consider threads with |
| different priorities). We should support starvation-freedom for serial |
| transactions in the future. Everything beyond that is highly related to proper |
| contention management across all of the TM (including with TM method to |
| choose), and is future work. |
| |
| @strong{TODO} Handling thread priorities: We want to avoid priority inversion |
| but it's unclear how often that actually matters in practice. Workloads that |
| have threads with different priorities will likely also require lower latency |
| or higher throughput for high-priority threads. Therefore, it probably makes |
| not that much sense (except for eventual progress guarantees) to use |
| priority inheritance until the TM has priority-aware contention management. |
| |
| |
| @c --------------------------------------------------------------------- |
| @c GNU Free Documentation License |
| @c --------------------------------------------------------------------- |
| |
| @include fdl.texi |
| |
| @c --------------------------------------------------------------------- |
| @c Index |
| @c --------------------------------------------------------------------- |
| |
| @node Library Index |
| @unnumbered Library Index |
| |
| @printindex cp |
| |
| @bye |