2018-02-28 Paul Thomas <pault@gcc.gnu.org>
[official-gcc.git] / libitm / libitm.texi
blob7a91348947f038906afa2074389606b7ef076ad0
1 \input texinfo @c -*-texinfo-*-
3 @c %**start of header
4 @setfilename libitm.info
5 @settitle GNU libitm
6 @c %**end of header
9 @copying
10 Copyright @copyright{} 2011-2018 Free Software Foundation, Inc.
12 Permission is granted to copy, distribute and/or modify this document
13 under the terms of the GNU Free Documentation License, Version 1.2 or
14 any later version published by the Free Software Foundation; with no
15 Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts.
16 A copy of the license is included in the section entitled ``GNU
17 Free Documentation License''.
18 @end copying
20 @ifinfo
21 @dircategory GNU Libraries
22 @direntry
23 * libitm: (libitm).                    GNU Transactional Memory Library
24 @end direntry
26 This manual documents the GNU Transactional Memory Library.
28 @insertcopying
29 @end ifinfo
32 @setchapternewpage odd
34 @titlepage
35 @title The GNU Transactional Memory Library
36 @page
37 @vskip 0pt plus 1filll
38 @comment For the @value{version-GCC} Version*
39 @sp 1
40 @insertcopying
41 @end titlepage
43 @summarycontents
44 @contents
45 @page
48 @node Top
49 @top Introduction
50 @cindex Introduction
52 This manual documents the usage and internals of libitm, the GNU Transactional
53 Memory Library. It provides transaction support for accesses to a process'
54 memory, enabling easy-to-use synchronization of accesses to shared memory by
55 several threads.
58 @comment
59 @comment  When you add a new menu item, please keep the right hand
60 @comment  aligned to the same column.  Do not use tabs.  This provides
61 @comment  better formatting.
62 @comment
63 @menu
64 * Enabling libitm::            How to enable libitm for your applications.
65 * C/C++ Language Constructs for TM::
66                                Notes on the language-level interface supported
67                                by gcc.
68 * The libitm ABI::             Notes on the external ABI provided by libitm.
69 * Internals::                  Notes on libitm's internal synchronization.
70 * GNU Free Documentation License::
71                                How you can copy and share this manual.
72 * Library Index::              Index of this documentation.
73 @end menu
76 @c ---------------------------------------------------------------------
77 @c Enabling libitm
78 @c ---------------------------------------------------------------------
80 @node Enabling libitm
81 @chapter Enabling libitm
83 To activate support for TM in C/C++, the compile-time flag @option{-fgnu-tm}
84 must be specified. This enables TM language-level constructs such as
85 transaction statements (e.g., @code{__transaction_atomic}, @pxref{C/C++
86 Language Constructs for TM} for details).
88 @c ---------------------------------------------------------------------
89 @c C/C++ Language Constructs for TM
90 @c ---------------------------------------------------------------------
92 @node C/C++ Language Constructs for TM
93 @chapter C/C++ Language Constructs for TM
95 Transactions are supported in C++ and C in the form of transaction statements,
96 transaction expressions, and function transactions. In the following example,
97 both @code{a} and @code{b} will be read and the difference will be written to
98 @code{c}, all atomically and isolated from other transactions:
100 @example
101 __transaction_atomic @{ c = a - b; @}
102 @end example
104 Therefore, another thread can use the following code to concurrently update
105 @code{b} without ever causing @code{c} to hold a negative value (and without
106 having to use other synchronization constructs such as locks or C++11
107 atomics):
109 @example
110 __transaction_atomic @{ if (a > b) b++; @}
111 @end example
113 GCC follows the @uref{https://sites.google.com/site/tmforcplusplus/, Draft
114 Specification of Transactional Language Constructs for C++ (v1.1)} in its
115 implementation of transactions.
117 The precise semantics of transactions are defined in terms of the C++11/C11
118 memory model (see the specification). Roughly, transactions provide
119 synchronization guarantees that are similar to what would be guaranteed when
120 using a single global lock as a guard for all transactions. Note that like
121 other synchronization constructs in C/C++, transactions rely on a
122 data-race-free program (e.g., a nontransactional write that is concurrent
123 with a transactional read to the same memory location is a data race).
125 @c ---------------------------------------------------------------------
126 @c The libitm ABI
127 @c ---------------------------------------------------------------------
129 @node The libitm ABI
130 @chapter The libitm ABI
132 The ABI provided by libitm is basically equal to the Linux variant of Intel's
133 current TM ABI specification document (Revision 1.1, May 6 2009) but with the
134 differences listed in this chapter. It would be good if these changes would
135 eventually be merged into a future version of this specification. To ease
136 look-up, the following subsections mirror the structure of this specification.
138 @section [No changes] Objectives
139 @section [No changes] Non-objectives
141 @section Library design principles
142 @subsection [No changes] Calling conventions
143 @subsection [No changes] TM library algorithms
144 @subsection [No changes] Optimized load and store routines
145 @subsection [No changes] Aligned load and store routines
147 @subsection Data logging functions
149 The memory locations accessed with transactional loads and stores and the
150 memory locations whose values are logged must not overlap. This required
151 separation only extends to the scope of the execution of one transaction
152 including all the executions of all nested transactions.
154 The compiler must be consistent (within the scope of a single transaction)
155 about which memory locations are shared and which are not shared with other
156 threads (i.e., data must be accessed either transactionally or
157 nontransactionally). Otherwise, non-write-through TM algorithms would not work.
159 For memory locations on the stack, this requirement extends to only the
160 lifetime of the stack frame that the memory location belongs to (or the
161 lifetime of the transaction, whichever is shorter).  Thus, memory that is
162 reused for several stack frames could be target of both data logging and
163 transactional accesses; however, this is harmless because these stack frames'
164 lifetimes will end before the transaction finishes.
166 @subsection [No changes] Scatter/gather calls
167 @subsection [No changes] Serial and irrevocable mode
168 @subsection [No changes] Transaction descriptor
169 @subsection Store allocation
171 There is no @code{getTransaction} function. 
173 @subsection [No changes] Naming conventions
175 @subsection Function pointer encryption
177 Currently, this is not implemented.
180 @section Types and macros list
182 @code{_ITM_codeProperties} has changed, @pxref{txn-code-properties,,Starting a
183 transaction}.
184 @code{_ITM_srcLocation} is not used. 
187 @section Function list
189 @subsection Initialization and finalization functions
190 These functions are not part of the ABI.
192 @subsection [No changes] Version checking
193 @subsection [No changes] Error reporting
194 @subsection [No changes] inTransaction call
196 @subsection State manipulation functions
197 There is no @code{getTransaction} function. Transaction identifiers for
198 nested transactions will be ordered but not necessarily sequential (i.e., for
199 a nested transaction's identifier @var{IN} and its enclosing transaction's
200 identifier @var{IE}, it is guaranteed that @math{IN >= IE}).
202 @subsection [No changes] Source locations
204 @subsection Starting a transaction
206 @subsubsection Transaction code properties
208 @anchor{txn-code-properties}
209 The bit @code{hasNoXMMUpdate} is instead called @code{hasNoVectorUpdate}.
210 Iff it is set, vector register save/restore is not necessary for any target
211 machine.
213 The @code{hasNoFloatUpdate} bit (@code{0x0010}) is new. Iff it is set, floating
214 point register save/restore is not necessary for any target machine.
216 @code{undoLogCode} is not supported and a fatal runtime error will be raised
217 if this bit is set. It is not properly defined in the ABI why barriers
218 other than undo logging are not present; Are they not necessary (e.g., a
219 transaction operating purely on thread-local data) or have they been omitted by
220 the compiler because it thinks that some kind of global synchronization
221 (e.g., serial mode) might perform better? The specification suggests that the
222 latter might be the case, but the former seems to be more useful.
224 The @code{readOnly} bit (@code{0x4000}) is new. @strong{TODO} Lexical or dynamic
225 scope?
227 @code{hasNoRetry} is not supported. If this bit is not set, but
228 @code{hasNoAbort} is set, the library can assume that transaction
229 rollback will not be requested.
231 It would be useful if the absence of externally-triggered rollbacks would be
232 reported for the dynamic scope as well, not just for the lexical scope
233 (@code{hasNoAbort}). Without this, a library cannot exploit this together
234 with flat nesting.
236 @code{exceptionBlock} is not supported because exception blocks are not used.
238 @subsubsection [No changes] Windows exception state
239 @subsubsection [No changes] Other machine state
241 @subsubsection [No changes] Results from beginTransaction
243 @subsection Aborting a transaction
245 @code{_ITM_rollbackTransaction} is not supported. @code{_ITM_abortTransaction}
246 is supported but the abort reasons @code{exceptionBlockAbort},
247 @code{TMConflict}, and @code{userRetry} are not supported. There are no
248 exception blocks in general, so the related cases also do not have to be
249 considered. To encode @code{__transaction_cancel [[outer]]}, compilers must
250 set the new @code{outerAbort} bit (@code{0x10}) additionally to the
251 @code{userAbort} bit in the abort reason.
253 @subsection Committing a transaction
255 The exception handling (EH) scheme is different. The Intel ABI requires the
256 @code{_ITM_tryCommitTransaction} function that will return even when the
257 commit failed and will have to be matched with calls to either
258 @code{_ITM_abortTransaction} or @code{_ITM_commitTransaction}. In contrast,
259 gcc relies on transactional wrappers for the functions of the Exception
260 Handling ABI and on one additional commit function (shown below). This allows
261 the TM to keep track of EH internally and thus it does not have to embed the
262 cleanup of EH state into the existing EH code in the program.
263 @code{_ITM_tryCommitTransaction} is not supported.
264 @code{_ITM_commitTransactionToId} is also not supported because the
265 propagation of thrown exceptions will not bypass commits of nested
266 transactions.
268 @example
269 void _ITM_commitTransactionEH(void *exc_ptr) ITM_REGPARM;
270 void *_ITM_cxa_allocate_exception (size_t);
271 void _ITM_cxa_free_exception (void *exc_ptr);
272 void _ITM_cxa_throw (void *obj, void *tinfo, void *dest);
273 void *_ITM_cxa_begin_catch (void *exc_ptr);
274 void _ITM_cxa_end_catch (void);
275 @end example
277 The EH scheme changed in version 6 of GCC.  Previously, the compiler
278 added a call to @code{_ITM_commitTransactionEH} to commit a transaction if
279 an exception could be in flight at this position in the code; @code{exc_ptr} is
280 the address of the current exception and must be non-zero.  Now, the
281 compiler must catch all exceptions that are about to be thrown out of a
282 transaction and call @code{_ITM_commitTransactionEH} from the catch clause,
283 with @code{exc_ptr} being zero.
285 Note that the old EH scheme never worked completely in GCC's implementation;
286 libitm currently does not try to be compatible with the old scheme.
288 The @code{_ITM_cxa...} functions are transactional wrappers for the respective
289 @code{__cxa...} functions and must be called instead of these in transactional
290 code.  @code{_ITM_cxa_free_exception} is new in GCC 6.
292 To support this EH scheme, libstdc++ needs to provide one additional function
293 (@code{_cxa_tm_cleanup}), which is used by the TM to clean up the exception
294 handling state while rolling back a transaction:
296 @example
297 void __cxa_tm_cleanup (void *unthrown_obj, void *cleanup_exc,
298                        unsigned int caught_count);
299 @end example
301 Since GCC 6, @code{unthrown_obj} is not used anymore and always null;
302 prior to that, @code{unthrown_obj} is non-null if the program called
303 @code{__cxa_allocate_exception} for this exception but did not yet called
304 @code{__cxa_throw} for it. @code{cleanup_exc} is non-null if the program is
305 currently processing a cleanup along an exception path but has not caught this
306 exception yet. @code{caught_count} is the nesting depth of
307 @code{__cxa_begin_catch} within the transaction (which can be counted by the TM
308 using @code{_ITM_cxa_begin_catch} and @code{_ITM_cxa_end_catch});
309 @code{__cxa_tm_cleanup} then performs rollback by essentially performing
310 @code{__cxa_end_catch} that many times.
314 @subsection Exception handling support
316 Currently, there is no support for functionality like
317 @code{__transaction_cancel throw} as described in the C++ TM specification.
318 Supporting this should be possible with the EH scheme explained previously
319 because via the transactional wrappers for the EH ABI, the TM is able to
320 observe and intercept EH.
323 @subsection [No changes] Transition to serial--irrevocable mode
324 @subsection [No changes] Data transfer functions
325 @subsection [No changes] Transactional memory copies
327 @subsection Transactional versions of memmove
329 If either the source or destination memory region is to be accessed
330 nontransactionally, then source and destination regions must not be
331 overlapping. The respective @code{_ITM_memmove} functions are still
332 available but a fatal runtime error will be raised if such regions do overlap.
333 To support this functionality, the ABI would have to specify how the
334 intersection of the regions has to be accessed (i.e., transactionally or
335 nontransactionally).
337 @subsection [No changes] Transactional versions of memset
338 @subsection [No changes] Logging functions
340 @subsection User-registered commit and undo actions
342 Commit actions will get executed in the same order in which the respective
343 calls to @code{_ITM_addUserCommitAction} happened. Only
344 @code{_ITM_noTransactionId} is allowed as value for the
345 @code{resumingTransactionId} argument. Commit actions get executed after
346 privatization safety has been ensured.
348 Undo actions will get executed in reverse order compared to the order in which
349 the respective calls to @code{_ITM_addUserUndoAction} happened. The ordering of
350 undo actions w.r.t. the roll-back of other actions (e.g., data transfers or
351 memory allocations) is undefined.
353 @code{_ITM_getThreadnum} is not supported currently because its only purpose
354 is to provide a thread ID that matches some assumed performance tuning output,
355 but this output is not part of the ABI nor further defined by it.
357 @code{_ITM_dropReferences} is not supported currently because its semantics and
358 the intention behind it is not entirely clear. The
359 specification suggests that this function is necessary because of certain
360 orderings of data transfer undos and the releasing of memory regions (i.e.,
361 privatization). However, this ordering is never defined, nor is the ordering of
362 dropping references w.r.t. other events.
364 @subsection [New] Transactional indirect calls
366 Indirect calls (i.e., calls through a function pointer) within transactions
367 should execute the transactional clone of the original function (i.e., a clone
368 of the original that has been fully instrumented to use the TM runtime), if
369 such a clone is available. The runtime provides two functions to
370 register/deregister clone tables:
372 @example
373 struct clone_entry
375   void *orig, *clone;
378 void _ITM_registerTMCloneTable (clone_entry *table, size_t entries);
379 void _ITM_deregisterTMCloneTable (clone_entry *table);
380 @end example
382 Registered tables must be writable by the TM runtime, and must be live
383 throughout the life-time of the TM runtime.
385 @strong{TODO} The intention was always to drop the registration functions
386 entirely, and create a new ELF Phdr describing the linker-sorted table.  Much
387 like what currently happens for @code{PT_GNU_EH_FRAME}.
388 This work kept getting bogged down in how to represent the @var{N} different
389 code generation variants.  We clearly needed at least two---SW and HW
390 transactional clones---but there was always a suggestion of more variants for
391 different TM assumptions/invariants.
393 The compiler can then use two TM runtime functions to perform indirect calls in
394 transactions:
395 @example
396 void *_ITM_getTMCloneOrIrrevocable (void *function) ITM_REGPARM;
397 void *_ITM_getTMCloneSafe (void *function) ITM_REGPARM;
398 @end example
400 If there is a registered clone for supplied function, both will return a
401 pointer to the clone. If not, the first runtime function will attempt to switch
402 to serial--irrevocable mode and return the original pointer, whereas the second
403 will raise a fatal runtime error.
405 @subsection [New] Transactional dynamic memory management
407 @example
408 void *_ITM_malloc (size_t)
409        __attribute__((__malloc__)) ITM_PURE;
410 void *_ITM_calloc (size_t, size_t)
411        __attribute__((__malloc__)) ITM_PURE;
412 void _ITM_free (void *) ITM_PURE;
413 @end example
415 These functions are essentially transactional wrappers for @code{malloc},
416 @code{calloc}, and @code{free}. Within transactions, the compiler should
417 replace calls to the original functions with calls to the wrapper functions.
419 libitm also provides transactional clones of C++ memory management functions
420 such as global operator new and delete.  They are part of libitm for historic
421 reasons but do not need to be part of this ABI.
424 @section [No changes] Future Enhancements to the ABI
426 @section Sample code 
428 The code examples might not be correct w.r.t. the current version of the ABI,
429 especially everything related to exception handling.
432 @section [New] Memory model
434 The ABI should define a memory model and the ordering that is guaranteed for
435 data transfers and commit/undo actions, or at least refer to another memory
436 model that needs to be preserved. Without that, the compiler cannot ensure the
437 memory model specified on the level of the programming language (e.g., by the
438 C++ TM specification).
440 For example, if a transactional load is ordered before another load/store, then
441 the TM runtime must also ensure this ordering when accessing shared state. If
442 not, this might break the kind of publication safety used in the C++ TM
443 specification. Likewise, the TM runtime must ensure privatization safety.
447 @c ---------------------------------------------------------------------
448 @c Internals
449 @c ---------------------------------------------------------------------
451 @node Internals
452 @chapter Internals
454 @section TM methods and method groups
456 libitm supports several ways of synchronizing transactions with each other.
457 These TM methods (or TM algorithms) are implemented in the form of
458 subclasses of @code{abi_dispatch}, which provide methods for
459 transactional loads and stores as well as callbacks for rollback and commit.
460 All methods that are compatible with each other (i.e., that let concurrently
461 running transactions still synchronize correctly even if different methods
462 are used) belong to the same TM method group. Pointers to TM methods can be
463 obtained using the factory methods prefixed with @code{dispatch_} in
464 @file{libitm_i.h}. There are two special methods, @code{dispatch_serial} and
465 @code{dispatch_serialirr}, that are compatible with all methods because they
466 run transactions completely in serial mode.
468 @subsection TM method life cycle
470 The state of TM methods does not change after construction, but they do alter
471 the state of transactions that use this method. However, because
472 per-transaction data gets used by several methods, @code{gtm_thread} is
473 responsible for setting an initial state that is useful for all methods.
474 After that, methods are responsible for resetting/clearing this state on each
475 rollback or commit (of outermost transactions), so that the transaction
476 executed next is not affected by the previous transaction.
478 There is also global state associated with each method group, which is
479 initialized and shut down (@code{method_group::init()} and @code{fini()})
480 when switching between method groups (see @file{retry.cc}).
482 @subsection Selecting the default method
484 The default method that libitm uses for freshly started transactions (but
485 not necessarily for restarted transactions) can be set via an environment
486 variable (@env{ITM_DEFAULT_METHOD}), whose value should be equal to the name
487 of one of the factory methods returning abi_dispatch subclasses but without
488 the "dispatch_" prefix (e.g., "serialirr" instead of
489 @code{GTM::dispatch_serialirr()}).
491 Note that this environment variable is only a hint for libitm and might not
492 be supported in the future.
495 @section Nesting: flat vs. closed
497 We support two different kinds of nesting of transactions. In the case of
498 @emph{flat nesting}, the nesting structure is flattened and all nested
499 transactions are subsumed by the enclosing transaction. In contrast,
500 with @emph{closed nesting}, nested transactions that have not yet committed
501 can be rolled back separately from the enclosing transactions; when they
502 commit, they are subsumed by the enclosing transaction, and their effects
503 will be finally committed when the outermost transaction commits.
504 @emph{Open nesting} (where nested transactions can commit independently of the
505 enclosing transactions) are not supported.
507 Flat nesting is the default nesting mode, but closed nesting is supported and
508 used when transactions contain user-controlled aborts
509 (@code{__transaction_cancel} statements). We assume that user-controlled
510 aborts are rare in typical code and used mostly in exceptional situations.
511 Thus, it makes more sense to use flat nesting by default to avoid the
512 performance overhead of the additional checkpoints required for closed
513 nesting. User-controlled aborts will correctly abort the innermost enclosing
514 transaction, whereas the whole (i.e., outermost) transaction will be restarted
515 otherwise (e.g., when a transaction encounters data conflicts during
516 optimistic execution).
519 @section Locking conventions
521 This section documents the locking scheme and rules for all uses of locking
522 in libitm. We have to support serial(-irrevocable) mode, which is implemented
523 using a global lock as explained next (called the @emph{serial lock}). To
524 simplify the overall design, we use the same lock as catch-all locking
525 mechanism for other infrequent tasks such as (de)registering clone tables or
526 threads. Besides the serial lock, there are @emph{per-method-group locks} that
527 are managed by specific method groups (i.e., groups of similar TM concurrency
528 control algorithms), and lock-like constructs for quiescence-based operations
529 such as ensuring privatization safety.
531 Thus, the actions that participate in the libitm-internal locking are either
532 @emph{active transactions} that do not run in serial mode, @emph{serial
533 transactions} (which (are about to) run in serial mode), and management tasks
534 that do not execute within a transaction but have acquired the serial mode
535 like a serial transaction would do (e.g., to be able to register threads with
536 libitm). Transactions become active as soon as they have successfully used the
537 serial lock to announce this globally (@pxref{serial-lock-impl,,Serial lock
538 implementation}). Likewise, transactions become serial transactions as soon as
539 they have acquired the exclusive rights provided by the serial lock (i.e.,
540 serial mode, which also means that there are no other concurrent active or
541 serial transactions). Note that active transactions can become serial
542 transactions when they enter serial mode during the runtime of the
543 transaction.
545 @subsection State-to-lock mapping
547 Application data is protected by the serial lock if there is a serial
548 transaction and no concurrently running active transaction (i.e., non-serial).
549 Otherwise, application data is protected by the currently selected method
550 group, which might use per-method-group locks or other mechanisms. Also note
551 that application data that is about to be privatized might not be allowed to be
552 accessed by nontransactional code until privatization safety has been ensured;
553 the details of this are handled by the current method group.
555 libitm-internal state is either protected by the serial lock or accessed
556 through custom concurrent code. The latter applies to the public/shared part
557 of a transaction object and most typical method-group-specific state.
559 The former category (protected by the serial lock) includes:
560 @itemize @bullet
561 @item The list of active threads that have used transactions.
562 @item The tables that map functions to their transactional clones.
563 @item The current selection of which method group to use.
564 @item Some method-group-specific data, or invariants of this data. For example,
565 resetting a method group to its initial state is handled by switching to the
566 same method group, so the serial lock protects such resetting as well.
567 @end itemize
568 In general, such state is immutable whenever there exists an active
569 (non-serial) transaction. If there is no active transaction, a serial
570 transaction (or a thread that is not currently executing a transaction but has
571 acquired the serial lock) is allowed to modify this state (but must of course
572 be careful to not surprise the current method group's implementation with such
573 modifications).
575 @subsection Lock acquisition order
577 To prevent deadlocks, locks acquisition must happen in a globally agreed-upon
578 order. Note that this applies to other forms of blocking too, but does not
579 necessarily apply to lock acquisitions that do not block (e.g., trylock()
580 calls that do not get retried forever). Note that serial transactions are
581 never return back to active transactions until the transaction has committed.
582 Likewise, active transactions stay active until they have committed.
583 Per-method-group locks are typically also not released before commit.
585 Lock acquisition / blocking rules:
586 @itemize @bullet
588 @item Transactions must become active or serial before they are allowed to
589 use method-group-specific locks or blocking (i.e., the serial lock must be
590 acquired before those other locks, either in serial or nonserial mode).
592 @item Any number of threads that do not currently run active transactions can
593 block while trying to get the serial lock in exclusive mode. Note that active
594 transactions must not block when trying to upgrade to serial mode unless there
595 is no other transaction that is trying that (the latter is ensured by the
596 serial lock implementation.
598 @item Method groups must prevent deadlocks on their locks. In particular, they
599 must also be prepared for another active transaction that has acquired
600 method-group-specific locks but is blocked during an attempt to upgrade to
601 being a serial transaction. See below for details.
603 @item Serial transactions can acquire method-group-specific locks because there
604 will be no other active nor serial transaction.
606 @end itemize
608 There is no single rule for per-method-group blocking because this depends on
609 when a TM method might acquire locks. If no active transaction can upgrade to
610 being a serial transaction after it has acquired per-method-group locks (e.g.,
611 when those locks are only acquired during an attempt to commit), then the TM
612 method does not need to consider a potential deadlock due to serial mode.
614 If there can be upgrades to serial mode after the acquisition of
615 per-method-group locks, then TM methods need to avoid those deadlocks:
616 @itemize @bullet
617 @item When upgrading to a serial transaction, after acquiring exclusive rights
618 to the serial lock but before waiting for concurrent active transactions to
619 finish (@pxref{serial-lock-impl,,Serial lock implementation} for details),
620 we have to wake up all active transactions waiting on the upgrader's
621 per-method-group locks.
622 @item Active transactions blocking on per-method-group locks need to check the
623 serial lock and abort if there is a pending serial transaction.
624 @item Lost wake-ups have to be prevented (e.g., by changing a bit in each
625 per-method-group lock before doing the wake-up, and only blocking on this lock
626 using a futex if this bit is not group).
627 @end itemize
629 @strong{TODO}: Can reuse serial lock for gl-*? And if we can, does it make
630 sense to introduce further complexity in the serial lock? For gl-*, we can
631 really only avoid an abort if we do -wb and -vbv.
634 @subsection Serial lock implementation
635 @anchor{serial-lock-impl}
637 The serial lock implementation is optimized towards assuming that serial
638 transactions are infrequent and not the common case. However, the performance
639 of entering serial mode can matter because when only few transactions are run
640 concurrently or if there are few threads, then it can be efficient to run
641 transactions serially.
643 The serial lock is similar to a multi-reader-single-writer lock in that there
644 can be several active transactions but only one serial transaction. However,
645 we do want to avoid contention (in the lock implementation) between active
646 transactions, so we split up the reader side of the lock into per-transaction
647 flags that are true iff the transaction is active. The exclusive writer side
648 remains a shared single flag, which is acquired using a CAS, for example.
649 On the fast-path, the serial lock then works similar to Dekker's algorithm but
650 with several reader flags that a serial transaction would have to check.
651 A serial transaction thus requires a list of all threads with potentially
652 active transactions; we can use the serial lock itself to protect this list
653 (i.e., only threads that have acquired the serial lock can modify this list).
655 We want starvation-freedom for the serial lock to allow for using it to ensure
656 progress for potentially starved transactions (@pxref{progress-guarantees,,
657 Progress Guarantees} for details). However, this is currently not enforced by
658 the implementation of the serial lock.
660 Here is pseudo-code for the read/write fast paths of acquiring the serial
661 lock (read-to-write upgrade is similar to write_lock:
662 @example
663 // read_lock:
664 tx->shared_state |= active;
665 __sync_synchronize(); // or STLD membar, or C++0x seq-cst fence
666 while (!serial_lock.exclusive)
667   if (spinning_for_too_long) goto slowpath;
669 // write_lock:
670 if (CAS(&serial_lock.exclusive, 0, this) != 0)
671   goto slowpath; // writer-writer contention
672 // need a membar here, but CAS already has full membar semantics
673 bool need_blocking = false;
674 for (t: all txns)
675   @{
676     for (;t->shared_state & active;)
677       if (spinning_for_too_long) @{ need_blocking = true; break; @}
678   @}
679 if (need_blocking) goto slowpath;
680 @end example
682 Releasing a lock in this spin-lock version then just consists of resetting
683 @code{tx->shared_state} to inactive or clearing @code{serial_lock.exclusive}.
685 However, we can't rely on a pure spinlock because we need to get the OS
686 involved at some time (e.g., when there are more threads than CPUs to run on).
687 Therefore, the real implementation falls back to a blocking slow path, either
688 based on pthread mutexes or Linux futexes.
691 @subsection Reentrancy
693 libitm has to consider the following cases of reentrancy:
694 @itemize @bullet
696 @item Transaction calls unsafe code that starts a new transaction: The outer
697 transaction will become a serial transaction before executing unsafe code.
698 Therefore, nesting within serial transactions must work, even if the nested
699 transaction is called from within uninstrumented code.
701 @item Transaction calls either a transactional wrapper or safe code, which in
702 turn starts a new transaction: It is not yet defined in the specification
703 whether this is allowed. Thus, it is undefined whether libitm supports this.
705 @item Code that starts new transactions might be called from within any part
706 of libitm: This kind of reentrancy would likely be rather complex and can
707 probably be avoided. Therefore, it is not supported.
709 @end itemize
711 @subsection Privatization safety
713 Privatization safety is ensured by libitm using a quiescence-based approach.
714 Basically, a privatizing transaction waits until all concurrent active
715 transactions will either have finished (are not active anymore) or operate on
716 a sufficiently recent snapshot to not access the privatized data anymore. This
717 happens after the privatizing transaction has stopped being an active
718 transaction, so waiting for quiescence does not contribute to deadlocks.
720 In method groups that need to ensure publication safety explicitly, active
721 transactions maintain a flag or timestamp in the public/shared part of the
722 transaction descriptor. Before blocking, privatizers need to let the other
723 transactions know that they should wake up the privatizer.
725 @strong{TODO} Ho to implement the waiters? Should those flags be
726 per-transaction or at a central place? We want to avoid one wake/wait call
727 per active transactions, so we might want to use either a tree or combining
728 to reduce the syscall overhead, or rather spin for a long amount of time
729 instead of doing blocking. Also, it would be good if only the last transaction
730 that the privatizer waits for would do the wake-up.
732 @subsection Progress guarantees
733 @anchor{progress-guarantees}
735 Transactions that do not make progress when using the current TM method will
736 eventually try to execute in serial mode. Thus, the serial lock's progress
737 guarantees determine the progress guarantees of the whole TM. Obviously, we at
738 least need deadlock-freedom for the serial lock, but it would also be good to
739 provide starvation-freedom (informally, all threads will finish executing a
740 transaction eventually iff they get enough cycles).
742 However, the scheduling of transactions (e.g., thread scheduling by the OS)
743 also affects the handling of progress guarantees by the TM. First, the TM
744 can only guarantee deadlock-freedom if threads do not get stopped. Likewise,
745 low-priority threads can starve if they do not get scheduled when other
746 high-priority threads get those cycles instead.
748 If all threads get scheduled eventually, correct lock implementations will
749 provide deadlock-freedom, but might not provide starvation-freedom. We can
750 either enforce the latter in the TM's lock implementation, or assume that
751 the scheduling is sufficiently random to yield a probabilistic guarantee that
752 no thread will starve (because eventually, a transaction will encounter a
753 scheduling that will allow it to run). This can indeed work well in practice
754 but is not necessarily guaranteed to work (e.g., simple spin locks can be
755 pretty efficient).
757 Because enforcing stronger progress guarantees in the TM has a higher runtime
758 overhead, we focus on deadlock-freedom right now and assume that the threads
759 will get scheduled eventually by the OS (but don't consider threads with
760 different priorities). We should support starvation-freedom for serial
761 transactions in the future. Everything beyond that is highly related to proper
762 contention management across all of the TM (including with TM method to
763 choose), and is future work.
765 @strong{TODO} Handling thread priorities: We want to avoid priority inversion
766 but it's unclear how often that actually matters in practice. Workloads that
767 have threads with different priorities will likely also require lower latency
768 or higher throughput for high-priority threads. Therefore, it probably makes
769 not that much sense (except for eventual progress guarantees) to use
770 priority inheritance until the TM has priority-aware contention management.
773 @c ---------------------------------------------------------------------
774 @c GNU Free Documentation License
775 @c ---------------------------------------------------------------------
777 @include fdl.texi
779 @c ---------------------------------------------------------------------
780 @c Index
781 @c ---------------------------------------------------------------------
783 @node Library Index
784 @unnumbered Library Index
786 @printindex cp
788 @bye