1 This is libitm.info, produced by makeinfo version 5.1 from libitm.texi.
3 Copyright (C) 2011-2013 Free Software Foundation, Inc.
5 Permission is granted to copy, distribute and/or modify this document
6 under the terms of the GNU Free Documentation License, Version 1.2 or
7 any later version published by the Free Software Foundation; with no
8 Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A
9 copy of the license is included in the section entitled "GNU Free
10 Documentation License".
11 INFO-DIR-SECTION GNU Libraries
13 * libitm: (libitm). GNU Transactional Memory Library
16 This manual documents the GNU Transactional Memory Library.
18 Copyright (C) 2011-2013 Free Software Foundation, Inc.
20 Permission is granted to copy, distribute and/or modify this document
21 under the terms of the GNU Free Documentation License, Version 1.2 or
22 any later version published by the Free Software Foundation; with no
23 Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A
24 copy of the license is included in the section entitled "GNU Free
25 Documentation License".
28 File: libitm.info, Node: Top, Next: Enabling libitm, Up: (dir)
33 This manual documents the usage and internals of libitm, the GNU
34 Transactional Memory Library. It provides transaction support for
35 accesses to a process' memory, enabling easy-to-use synchronization of
36 accesses to shared memory by several threads.
40 * Enabling libitm:: How to enable libitm for your applications.
41 * C/C++ Language Constructs for TM::
42 Notes on the language-level interface supported
44 * The libitm ABI:: Notes on the external ABI provided by libitm.
45 * Internals:: Notes on libitm's internal synchronization.
46 * GNU Free Documentation License::
47 How you can copy and share this manual.
48 * Index:: Index of this documentation.
51 File: libitm.info, Node: Enabling libitm, Next: C/C++ Language Constructs for TM, Prev: Top, Up: Top
56 To activate support for TM in C/C++, the compile-time flag '-fgnu-tm'
57 must be specified. This enables TM language-level constructs such as
58 transaction statements (e.g., '__transaction_atomic', *note C/C++
59 Language Constructs for TM:: for details).
62 File: libitm.info, Node: C/C++ Language Constructs for TM, Next: The libitm ABI, Prev: Enabling libitm, Up: Top
64 2 C/C++ Language Constructs for TM
65 **********************************
67 Transactions are supported in C++ and C in the form of transaction
68 statements, transaction expressions, and function transactions. In the
69 following example, both 'a' and 'b' will be read and the difference will
70 be written to 'c', all atomically and isolated from other transactions:
72 __transaction_atomic { c = a - b; }
74 Therefore, another thread can use the following code to concurrently
75 update 'b' without ever causing 'c' to hold a negative value (and
76 without having to use other synchronization constructs such as locks or
79 __transaction_atomic { if (a > b) b++; }
81 GCC follows the Draft Specification of Transactional Language
82 Constructs for C++ (v1.1)
83 (https://sites.google.com/site/tmforcplusplus/) in its implementation of
86 The precise semantics of transactions are defined in terms of the
87 C++11/C11 memory model (see the specification). Roughly, transactions
88 provide synchronization guarantees that are similar to what would be
89 guaranteed when using a single global lock as a guard for all
90 transactions. Note that like other synchronization constructs in C/C++,
91 transactions rely on a data-race-free program (e.g., a nontransactional
92 write that is concurrent with a transactional read to the same memory
93 location is a data race).
96 File: libitm.info, Node: The libitm ABI, Next: Internals, Prev: C/C++ Language Constructs for TM, Up: Top
101 The ABI provided by libitm is basically equal to the Linux variant of
102 Intel's current TM ABI specification document (Revision 1.1, May 6 2009)
103 but with the differences listed in this chapter. It would be good if
104 these changes would eventually be merged into a future version of this
105 specification. To ease look-up, the following subsections mirror the
106 structure of this specification.
108 3.1 [No changes] Objectives
109 ===========================
111 3.2 [No changes] Non-objectives
112 ===============================
114 3.3 Library design principles
115 =============================
117 3.3.1 [No changes] Calling conventions
118 --------------------------------------
120 3.3.2 [No changes] TM library algorithms
121 ----------------------------------------
123 3.3.3 [No changes] Optimized load and store routines
124 ----------------------------------------------------
126 3.3.4 [No changes] Aligned load and store routines
127 --------------------------------------------------
129 3.3.5 Data logging functions
130 ----------------------------
132 The memory locations accessed with transactional loads and stores and
133 the memory locations whose values are logged must not overlap. This
134 required separation only extends to the scope of the execution of one
135 transaction including all the executions of all nested transactions.
137 The compiler must be consistent (within the scope of a single
138 transaction) about which memory locations are shared and which are not
139 shared with other threads (i.e., data must be accessed either
140 transactionally or nontransactionally). Otherwise, non-write-through TM
141 algorithms would not work.
143 For memory locations on the stack, this requirement extends to only
144 the lifetime of the stack frame that the memory location belongs to (or
145 the lifetime of the transaction, whichever is shorter). Thus, memory
146 that is reused for several stack frames could be target of both data
147 logging and transactional accesses; however, this is harmless because
148 these stack frames' lifetimes will end before the transaction finishes.
150 3.3.6 [No changes] Scatter/gather calls
151 ---------------------------------------
153 3.3.7 [No changes] Serial and irrevocable mode
154 ----------------------------------------------
156 3.3.8 [No changes] Transaction descriptor
157 -----------------------------------------
159 3.3.9 Store allocation
160 ----------------------
162 There is no 'getTransaction' function.
164 3.3.10 [No changes] Naming conventions
165 --------------------------------------
167 3.3.11 Function pointer encryption
168 ----------------------------------
170 Currently, this is not implemented.
172 3.4 Types and macros list
173 =========================
175 '_ITM_codeProperties' has changed, *note Starting a transaction:
176 txn-code-properties. '_ITM_srcLocation' is not used.
181 3.5.1 Initialization and finalization functions
182 -----------------------------------------------
184 These functions are not part of the ABI.
186 3.5.2 [No changes] Version checking
187 -----------------------------------
189 3.5.3 [No changes] Error reporting
190 ----------------------------------
192 3.5.4 [No changes] inTransaction call
193 -------------------------------------
195 3.5.5 State manipulation functions
196 ----------------------------------
198 There is no 'getTransaction' function. Transaction identifiers for
199 nested transactions will be ordered but not necessarily sequential
200 (i.e., for a nested transaction's identifier IN and its enclosing
201 transaction's identifier IE, it is guaranteed that IN >= IE).
203 3.5.6 [No changes] Source locations
204 -----------------------------------
206 3.5.7 Starting a transaction
207 ----------------------------
209 3.5.7.1 Transaction code properties
210 ...................................
212 The bit 'hasNoXMMUpdate' is instead called 'hasNoVectorUpdate'. Iff it
213 is set, vector register save/restore is not necessary for any target
216 The 'hasNoFloatUpdate' bit ('0x0010') is new. Iff it is set,
217 floating point register save/restore is not necessary for any target
220 'undoLogCode' is not supported and a fatal runtime error will be
221 raised if this bit is set. It is not properly defined in the ABI why
222 barriers other than undo logging are not present; Are they not necessary
223 (e.g., a transaction operating purely on thread-local data) or have they
224 been omitted by the compiler because it thinks that some kind of global
225 synchronization (e.g., serial mode) might perform better? The
226 specification suggests that the latter might be the case, but the former
227 seems to be more useful.
229 The 'readOnly' bit ('0x4000') is new. *TODO* Lexical or dynamic
232 'hasNoRetry' is not supported. If this bit is not set, but
233 'hasNoAbort' is set, the library can assume that transaction rollback
234 will not be requested.
236 It would be useful if the absence of externally-triggered rollbacks
237 would be reported for the dynamic scope as well, not just for the
238 lexical scope ('hasNoAbort'). Without this, a library cannot exploit
239 this together with flat nesting.
241 'exceptionBlock' is not supported because exception blocks are not
244 3.5.7.2 [No changes] Windows exception state
245 ............................................
247 3.5.7.3 [No changes] Other machine state
248 ........................................
250 3.5.7.4 [No changes] Results from beginTransaction
251 ..................................................
253 3.5.8 Aborting a transaction
254 ----------------------------
256 '_ITM_rollbackTransaction' is not supported. '_ITM_abortTransaction' is
257 supported but the abort reasons 'exceptionBlockAbort', 'TMConflict', and
258 'userRetry' are not supported. There are no exception blocks in
259 general, so the related cases also do not have to be considered. To
260 encode '__transaction_cancel [[outer]]', compilers must set the new
261 'outerAbort' bit ('0x10') additionally to the 'userAbort' bit in the
264 3.5.9 Committing a transaction
265 ------------------------------
267 The exception handling (EH) scheme is different. The Intel ABI requires
268 the '_ITM_tryCommitTransaction' function that will return even when the
269 commit failed and will have to be matched with calls to either
270 '_ITM_abortTransaction' or '_ITM_commitTransaction'. In contrast, gcc
271 relies on transactional wrappers for the functions of the Exception
272 Handling ABI and on one additional commit function (shown below). This
273 allows the TM to keep track of EH internally and thus it does not have
274 to embed the cleanup of EH state into the existing EH code in the
275 program. '_ITM_tryCommitTransaction' is not supported.
276 '_ITM_commitTransactionToId' is also not supported because the
277 propagation of thrown exceptions will not bypass commits of nested
280 void _ITM_commitTransactionEH(void *exc_ptr) ITM_REGPARM;
281 void *_ITM_cxa_allocate_exception (size_t);
282 void _ITM_cxa_throw (void *obj, void *tinfo, void *dest);
283 void *_ITM_cxa_begin_catch (void *exc_ptr);
284 void _ITM_cxa_end_catch (void);
286 '_ITM_commitTransactionEH' must be called to commit a transaction if
287 an exception could be in flight at this position in the code. 'exc_ptr'
288 is the current exception or zero if there is no current exception. The
289 '_ITM_cxa...' functions are transactional wrappers for the respective
290 '__cxa...' functions and must be called instead of these in
293 To support this EH scheme, libstdc++ needs to provide one additional
294 function ('_cxa_tm_cleanup'), which is used by the TM to clean up the
295 exception handling state while rolling back a transaction:
297 void __cxa_tm_cleanup (void *unthrown_obj, void *cleanup_exc,
298 unsigned int caught_count);
300 'unthrown_obj' is non-null if the program called
301 '__cxa_allocate_exception' for this exception but did not yet called
302 '__cxa_throw' for it. 'cleanup_exc' is non-null if the program is
303 currently processing a cleanup along an exception path but has not
304 caught this exception yet. 'caught_count' is the nesting depth of
305 '__cxa_begin_catch' within the transaction (which can be counted by the
306 TM using '_ITM_cxa_begin_catch' and '_ITM_cxa_end_catch');
307 '__cxa_tm_cleanup' then performs rollback by essentially performing
308 '__cxa_end_catch' that many times.
310 3.5.10 Exception handling support
311 ---------------------------------
313 Currently, there is no support for functionality like
314 '__transaction_cancel throw' as described in the C++ TM specification.
315 Supporting this should be possible with the EH scheme explained
316 previously because via the transactional wrappers for the EH ABI, the TM
317 is able to observe and intercept EH.
319 3.5.11 [No changes] Transition to serial-irrevocable mode
320 ---------------------------------------------------------
322 3.5.12 [No changes] Data transfer functions
323 -------------------------------------------
325 3.5.13 [No changes] Transactional memory copies
326 -----------------------------------------------
328 3.5.14 Transactional versions of memmove
329 ----------------------------------------
331 If either the source or destination memory region is to be accessed
332 nontransactionally, then source and destination regions must not be
333 overlapping. The respective '_ITM_memmove' functions are still
334 available but a fatal runtime error will be raised if such regions do
335 overlap. To support this functionality, the ABI would have to specify
336 how the intersection of the regions has to be accessed (i.e.,
337 transactionally or nontransactionally).
339 3.5.15 [No changes] Transactional versions of memset
340 ----------------------------------------------------
342 3.5.16 [No changes] Logging functions
343 -------------------------------------
345 3.5.17 User-registered commit and undo actions
346 ----------------------------------------------
348 Commit actions will get executed in the same order in which the
349 respective calls to '_ITM_addUserCommitAction' happened. Only
350 '_ITM_noTransactionId' is allowed as value for the
351 'resumingTransactionId' argument. Commit actions get executed after
352 privatization safety has been ensured.
354 Undo actions will get executed in reverse order compared to the order
355 in which the respective calls to '_ITM_addUserUndoAction' happened. The
356 ordering of undo actions w.r.t. the roll-back of other actions (e.g.,
357 data transfers or memory allocations) is undefined.
359 '_ITM_getThreadnum' is not supported currently because its only
360 purpose is to provide a thread ID that matches some assumed performance
361 tuning output, but this output is not part of the ABI nor further
364 '_ITM_dropReferences' is not supported currently because its
365 semantics and the intention behind it is not entirely clear. The
366 specification suggests that this function is necessary because of
367 certain orderings of data transfer undos and the releasing of memory
368 regions (i.e., privatization). However, this ordering is never defined,
369 nor is the ordering of dropping references w.r.t. other events.
371 3.5.18 [New] Transactional indirect calls
372 -----------------------------------------
374 Indirect calls (i.e., calls through a function pointer) within
375 transactions should execute the transactional clone of the original
376 function (i.e., a clone of the original that has been fully instrumented
377 to use the TM runtime), if such a clone is available. The runtime
378 provides two functions to register/deregister clone tables:
385 void _ITM_registerTMCloneTable (clone_entry *table, size_t entries);
386 void _ITM_deregisterTMCloneTable (clone_entry *table);
388 Registered tables must be writable by the TM runtime, and must be
389 live throughout the life-time of the TM runtime.
391 *TODO* The intention was always to drop the registration functions
392 entirely, and create a new ELF Phdr describing the linker-sorted table.
393 Much like what currently happens for 'PT_GNU_EH_FRAME'. This work kept
394 getting bogged down in how to represent the N different code generation
395 variants. We clearly needed at least two--SW and HW transactional
396 clones--but there was always a suggestion of more variants for different
397 TM assumptions/invariants.
399 The compiler can then use two TM runtime functions to perform
400 indirect calls in transactions:
401 void *_ITM_getTMCloneOrIrrevocable (void *function) ITM_REGPARM;
402 void *_ITM_getTMCloneSafe (void *function) ITM_REGPARM;
404 If there is a registered clone for supplied function, both will
405 return a pointer to the clone. If not, the first runtime function will
406 attempt to switch to serial-irrevocable mode and return the original
407 pointer, whereas the second will raise a fatal runtime error.
409 3.5.19 [New] Transactional dynamic memory management
410 ----------------------------------------------------
412 void *_ITM_malloc (size_t)
413 __attribute__((__malloc__)) ITM_PURE;
414 void *_ITM_calloc (size_t, size_t)
415 __attribute__((__malloc__)) ITM_PURE;
416 void _ITM_free (void *) ITM_PURE;
418 These functions are essentially transactional wrappers for 'malloc',
419 'calloc', and 'free'. Within transactions, the compiler should replace
420 calls to the original functions with calls to the wrapper functions.
422 3.6 [No changes] Future Enhancements to the ABI
423 ===============================================
428 The code examples might not be correct w.r.t. the current version of
429 the ABI, especially everything related to exception handling.
431 3.8 [New] Memory model
432 ======================
434 The ABI should define a memory model and the ordering that is guaranteed
435 for data transfers and commit/undo actions, or at least refer to another
436 memory model that needs to be preserved. Without that, the compiler
437 cannot ensure the memory model specified on the level of the programming
438 language (e.g., by the C++ TM specification).
440 For example, if a transactional load is ordered before another
441 load/store, then the TM runtime must also ensure this ordering when
442 accessing shared state. If not, this might break the kind of
443 publication safety used in the C++ TM specification. Likewise, the TM
444 runtime must ensure privatization safety.
447 File: libitm.info, Node: Internals, Next: GNU Free Documentation License, Prev: The libitm ABI, Up: Top
452 4.1 TM methods and method groups
453 ================================
455 libitm supports several ways of synchronizing transactions with each
456 other. These TM methods (or TM algorithms) are implemented in the form
457 of subclasses of 'abi_dispatch', which provide methods for transactional
458 loads and stores as well as callbacks for rollback and commit. All
459 methods that are compatible with each other (i.e., that let concurrently
460 running transactions still synchronize correctly even if different
461 methods are used) belong to the same TM method group. Pointers to TM
462 methods can be obtained using the factory methods prefixed with
463 'dispatch_' in 'libitm_i.h'. There are two special methods,
464 'dispatch_serial' and 'dispatch_serialirr', that are compatible with all
465 methods because they run transactions completely in serial mode.
467 4.1.1 TM method life cycle
468 --------------------------
470 The state of TM methods does not change after construction, but they do
471 alter the state of transactions that use this method. However, because
472 per-transaction data gets used by several methods, '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
475 each rollback or commit (of outermost transactions), so that the
476 transaction executed next is not affected by the previous transaction.
478 There is also global state associated with each method group, which
479 is initialized and shut down ('method_group::init()' and 'fini()') when
480 switching between method groups (see 'retry.cc').
482 4.1.2 Selecting the default method
483 ----------------------------------
485 The default method that libitm uses for freshly started transactions
486 (but not necessarily for restarted transactions) can be set via an
487 environment variable ('ITM_DEFAULT_METHOD'), whose value should be equal
488 to the name of one of the factory methods returning abi_dispatch
489 subclasses but without the "dispatch_" prefix (e.g., "serialirr" instead
490 of 'GTM::dispatch_serialirr()').
492 Note that this environment variable is only a hint for libitm and
493 might not be supported in the future.
495 4.2 Nesting: flat vs. closed
496 ============================
498 We support two different kinds of nesting of transactions. In the case
499 of _flat nesting_, the nesting structure is flattened and all nested
500 transactions are subsumed by the enclosing transaction. In contrast,
501 with _closed nesting_, nested transactions that have not yet committed
502 can be rolled back separately from the enclosing transactions; when they
503 commit, they are subsumed by the enclosing transaction, and their
504 effects will be finally committed when the outermost transaction
505 commits. _Open nesting_ (where nested transactions can commit
506 independently of the enclosing transactions) are not supported.
508 Flat nesting is the default nesting mode, but closed nesting is
509 supported and used when transactions contain user-controlled aborts
510 ('__transaction_cancel' statements). We assume that user-controlled
511 aborts are rare in typical code and used mostly in exceptional
512 situations. Thus, it makes more sense to use flat nesting by default to
513 avoid the performance overhead of the additional checkpoints required
514 for closed nesting. User-controlled aborts will correctly abort the
515 innermost enclosing transaction, whereas the whole (i.e., outermost)
516 transaction will be restarted otherwise (e.g., when a transaction
517 encounters data conflicts during optimistic execution).
519 4.3 Locking conventions
520 =======================
522 This section documents the locking scheme and rules for all uses of
523 locking in libitm. We have to support serial(-irrevocable) mode, which
524 is implemented using a global lock as explained next (called the _serial
525 lock_). To simplify the overall design, we use the same lock as
526 catch-all locking mechanism for other infrequent tasks such as
527 (de)registering clone tables or threads. Besides the serial lock, there
528 are _per-method-group locks_ that are managed by specific method groups
529 (i.e., groups of similar TM concurrency control algorithms), and
530 lock-like constructs for quiescence-based operations such as ensuring
531 privatization safety.
533 Thus, the actions that participate in the libitm-internal locking are
534 either _active transactions_ that do not run in serial mode, _serial
535 transactions_ (which (are about to) run in serial mode), and management
536 tasks that do not execute within a transaction but have acquired the
537 serial mode like a serial transaction would do (e.g., to be able to
538 register threads with libitm). Transactions become active as soon as
539 they have successfully used the serial lock to announce this globally
540 (*note Serial lock implementation: serial-lock-impl.). Likewise,
541 transactions become serial transactions as soon as they have acquired
542 the exclusive rights provided by the serial lock (i.e., serial mode,
543 which also means that there are no other concurrent active or serial
544 transactions). Note that active transactions can become serial
545 transactions when they enter serial mode during the runtime of the
548 4.3.1 State-to-lock mapping
549 ---------------------------
551 Application data is protected by the serial lock if there is a serial
552 transaction and no concurrently running active transaction (i.e.,
553 non-serial). Otherwise, application data is protected by the currently
554 selected method group, which might use per-method-group locks or other
555 mechanisms. Also note that application data that is about to be
556 privatized might not be allowed to be accessed by nontransactional code
557 until privatization safety has been ensured; the details of this are
558 handled by the current method group.
560 libitm-internal state is either protected by the serial lock or
561 accessed through custom concurrent code. The latter applies to the
562 public/shared part of a transaction object and most typical
563 method-group-specific state.
565 The former category (protected by the serial lock) includes:
566 * The list of active threads that have used transactions.
567 * The tables that map functions to their transactional clones.
568 * The current selection of which method group to use.
569 * Some method-group-specific data, or invariants of this data. For
570 example, resetting a method group to its initial state is handled
571 by switching to the same method group, so the serial lock protects
572 such resetting as well.
573 In general, such state is immutable whenever there exists an active
574 (non-serial) transaction. If there is no active transaction, a serial
575 transaction (or a thread that is not currently executing a transaction
576 but has acquired the serial lock) is allowed to modify this state (but
577 must of course be careful to not surprise the current method group's
578 implementation with such modifications).
580 4.3.2 Lock acquisition order
581 ----------------------------
583 To prevent deadlocks, locks acquisition must happen in a globally
584 agreed-upon order. Note that this applies to other forms of blocking
585 too, but does not necessarily apply to lock acquisitions that do not
586 block (e.g., trylock() calls that do not get retried forever). Note
587 that serial transactions are never return back to active transactions
588 until the transaction has committed. Likewise, active transactions stay
589 active until they have committed. Per-method-group locks are typically
590 also not released before commit.
592 Lock acquisition / blocking rules:
594 * Transactions must become active or serial before they are allowed
595 to use method-group-specific locks or blocking (i.e., the serial
596 lock must be acquired before those other locks, either in serial or
599 * Any number of threads that do not currently run active transactions
600 can block while trying to get the serial lock in exclusive mode.
601 Note that active transactions must not block when trying to upgrade
602 to serial mode unless there is no other transaction that is trying
603 that (the latter is ensured by the serial lock implementation.
605 * Method groups must prevent deadlocks on their locks. In
606 particular, they must also be prepared for another active
607 transaction that has acquired method-group-specific locks but is
608 blocked during an attempt to upgrade to being a serial transaction.
609 See below for details.
611 * Serial transactions can acquire method-group-specific locks because
612 there will be no other active nor serial transaction.
614 There is no single rule for per-method-group blocking because this
615 depends on when a TM method might acquire locks. If no active
616 transaction can upgrade to being a serial transaction after it has
617 acquired per-method-group locks (e.g., when those locks are only
618 acquired during an attempt to commit), then the TM method does not need
619 to consider a potential deadlock due to serial mode.
621 If there can be upgrades to serial mode after the acquisition of
622 per-method-group locks, then TM methods need to avoid those deadlocks:
623 * When upgrading to a serial transaction, after acquiring exclusive
624 rights to the serial lock but before waiting for concurrent active
625 transactions to finish (*note Serial lock implementation:
626 serial-lock-impl. for details), we have to wake up all active
627 transactions waiting on the upgrader's per-method-group locks.
628 * Active transactions blocking on per-method-group locks need to
629 check the serial lock and abort if there is a pending serial
631 * Lost wake-ups have to be prevented (e.g., by changing a bit in each
632 per-method-group lock before doing the wake-up, and only blocking
633 on this lock using a futex if this bit is not group).
635 *TODO*: Can reuse serial lock for gl-*? And if we can, does it make
636 sense to introduce further complexity in the serial lock? For gl-*, we
637 can really only avoid an abort if we do -wb and -vbv.
639 4.3.3 Serial lock implementation
640 --------------------------------
642 The serial lock implementation is optimized towards assuming that serial
643 transactions are infrequent and not the common case. However, the
644 performance of entering serial mode can matter because when only few
645 transactions are run concurrently or if there are few threads, then it
646 can be efficient to run transactions serially.
648 The serial lock is similar to a multi-reader-single-writer lock in
649 that there can be several active transactions but only one serial
650 transaction. However, we do want to avoid contention (in the lock
651 implementation) between active transactions, so we split up the reader
652 side of the lock into per-transaction flags that are true iff the
653 transaction is active. The exclusive writer side remains a shared
654 single flag, which is acquired using a CAS, for example. On the
655 fast-path, the serial lock then works similar to Dekker's algorithm but
656 with several reader flags that a serial transaction would have to check.
657 A serial transaction thus requires a list of all threads with
658 potentially active transactions; we can use the serial lock itself to
659 protect this list (i.e., only threads that have acquired the serial lock
660 can modify this list).
662 We want starvation-freedom for the serial lock to allow for using it
663 to ensure progress for potentially starved transactions (*note Progress
664 Guarantees: progress-guarantees. for details). However, this is
665 currently not enforced by the implementation of the serial lock.
667 Here is pseudo-code for the read/write fast paths of acquiring the
668 serial lock (read-to-write upgrade is similar to write_lock:
670 tx->shared_state |= active;
671 __sync_synchronize(); // or STLD membar, or C++0x seq-cst fence
672 while (!serial_lock.exclusive)
673 if (spinning_for_too_long) goto slowpath;
676 if (CAS(&serial_lock.exclusive, 0, this) != 0)
677 goto slowpath; // writer-writer contention
678 // need a membar here, but CAS already has full membar semantics
679 bool need_blocking = false;
682 for (;t->shared_state & active;)
683 if (spinning_for_too_long) { need_blocking = true; break; }
685 if (need_blocking) goto slowpath;
687 Releasing a lock in this spin-lock version then just consists of
688 resetting 'tx->shared_state' to inactive or clearing
689 'serial_lock.exclusive'.
691 However, we can't rely on a pure spinlock because we need to get the
692 OS involved at some time (e.g., when there are more threads than CPUs to
693 run on). Therefore, the real implementation falls back to a blocking
694 slow path, either based on pthread mutexes or Linux futexes.
699 libitm has to consider the following cases of reentrancy:
701 * Transaction calls unsafe code that starts a new transaction: The
702 outer transaction will become a serial transaction before executing
703 unsafe code. Therefore, nesting within serial transactions must
704 work, even if the nested transaction is called from within
707 * Transaction calls either a transactional wrapper or safe code,
708 which in turn starts a new transaction: It is not yet defined in
709 the specification whether this is allowed. Thus, it is undefined
710 whether libitm supports this.
712 * Code that starts new transactions might be called from within any
713 part of libitm: This kind of reentrancy would likely be rather
714 complex and can probably be avoided. Therefore, it is not
717 4.3.5 Privatization safety
718 --------------------------
720 Privatization safety is ensured by libitm using a quiescence-based
721 approach. Basically, a privatizing transaction waits until all
722 concurrent active transactions will either have finished (are not active
723 anymore) or operate on a sufficiently recent snapshot to not access the
724 privatized data anymore. This happens after the privatizing transaction
725 has stopped being an active transaction, so waiting for quiescence does
726 not contribute to deadlocks.
728 In method groups that need to ensure publication safety explicitly,
729 active transactions maintain a flag or timestamp in the public/shared
730 part of the transaction descriptor. Before blocking, privatizers need
731 to let the other transactions know that they should wake up the
734 *TODO* Ho to implement the waiters? Should those flags be
735 per-transaction or at a central place? We want to avoid one wake/wait
736 call per active transactions, so we might want to use either a tree or
737 combining to reduce the syscall overhead, or rather spin for a long
738 amount of time instead of doing blocking. Also, it would be good if
739 only the last transaction that the privatizer waits for would do the
742 4.3.6 Progress guarantees
743 -------------------------
745 Transactions that do not make progress when using the current TM method
746 will eventually try to execute in serial mode. Thus, the serial lock's
747 progress guarantees determine the progress guarantees of the whole TM.
748 Obviously, we at least need deadlock-freedom for the serial lock, but it
749 would also be good to provide starvation-freedom (informally, all
750 threads will finish executing a transaction eventually iff they get
753 However, the scheduling of transactions (e.g., thread scheduling by
754 the OS) also affects the handling of progress guarantees by the TM.
755 First, the TM can only guarantee deadlock-freedom if threads do not get
756 stopped. Likewise, low-priority threads can starve if they do not get
757 scheduled when other high-priority threads get those cycles instead.
759 If all threads get scheduled eventually, correct lock implementations
760 will provide deadlock-freedom, but might not provide starvation-freedom.
761 We can either enforce the latter in the TM's lock implementation, or
762 assume that the scheduling is sufficiently random to yield a
763 probabilistic guarantee that no thread will starve (because eventually,
764 a transaction will encounter a scheduling that will allow it to run).
765 This can indeed work well in practice but is not necessarily guaranteed
766 to work (e.g., simple spin locks can be pretty efficient).
768 Because enforcing stronger progress guarantees in the TM has a higher
769 runtime overhead, we focus on deadlock-freedom right now and assume that
770 the threads will get scheduled eventually by the OS (but don't consider
771 threads with different priorities). We should support
772 starvation-freedom for serial transactions in the future. Everything
773 beyond that is highly related to proper contention management across all
774 of the TM (including with TM method to choose), and is future work.
776 *TODO* Handling thread priorities: We want to avoid priority
777 inversion but it's unclear how often that actually matters in practice.
778 Workloads that have threads with different priorities will likely also
779 require lower latency or higher throughput for high-priority threads.
780 Therefore, it probably makes not that much sense (except for eventual
781 progress guarantees) to use priority inheritance until the TM has
782 priority-aware contention management.
785 File: libitm.info, Node: GNU Free Documentation License, Next: Index, Prev: Internals, Up: Top
787 GNU Free Documentation License
788 ******************************
790 Version 1.3, 3 November 2008
792 Copyright (C) 2000, 2001, 2002, 2007, 2008 Free Software Foundation, Inc.
795 Everyone is permitted to copy and distribute verbatim copies
796 of this license document, but changing it is not allowed.
800 The purpose of this License is to make a manual, textbook, or other
801 functional and useful document "free" in the sense of freedom: to
802 assure everyone the effective freedom to copy and redistribute it,
803 with or without modifying it, either commercially or
804 noncommercially. Secondarily, this License preserves for the
805 author and publisher a way to get credit for their work, while not
806 being considered responsible for modifications made by others.
808 This License is a kind of "copyleft", which means that derivative
809 works of the document must themselves be free in the same sense.
810 It complements the GNU General Public License, which is a copyleft
811 license designed for free software.
813 We have designed this License in order to use it for manuals for
814 free software, because free software needs free documentation: a
815 free program should come with manuals providing the same freedoms
816 that the software does. But this License is not limited to
817 software manuals; it can be used for any textual work, regardless
818 of subject matter or whether it is published as a printed book. We
819 recommend this License principally for works whose purpose is
820 instruction or reference.
822 1. APPLICABILITY AND DEFINITIONS
824 This License applies to any manual or other work, in any medium,
825 that contains a notice placed by the copyright holder saying it can
826 be distributed under the terms of this License. Such a notice
827 grants a world-wide, royalty-free license, unlimited in duration,
828 to use that work under the conditions stated herein. The
829 "Document", below, refers to any such manual or work. Any member
830 of the public is a licensee, and is addressed as "you". You accept
831 the license if you copy, modify or distribute the work in a way
832 requiring permission under copyright law.
834 A "Modified Version" of the Document means any work containing the
835 Document or a portion of it, either copied verbatim, or with
836 modifications and/or translated into another language.
838 A "Secondary Section" is a named appendix or a front-matter section
839 of the Document that deals exclusively with the relationship of the
840 publishers or authors of the Document to the Document's overall
841 subject (or to related matters) and contains nothing that could
842 fall directly within that overall subject. (Thus, if the Document
843 is in part a textbook of mathematics, a Secondary Section may not
844 explain any mathematics.) The relationship could be a matter of
845 historical connection with the subject or with related matters, or
846 of legal, commercial, philosophical, ethical or political position
849 The "Invariant Sections" are certain Secondary Sections whose
850 titles are designated, as being those of Invariant Sections, in the
851 notice that says that the Document is released under this License.
852 If a section does not fit the above definition of Secondary then it
853 is not allowed to be designated as Invariant. The Document may
854 contain zero Invariant Sections. If the Document does not identify
855 any Invariant Sections then there are none.
857 The "Cover Texts" are certain short passages of text that are
858 listed, as Front-Cover Texts or Back-Cover Texts, in the notice
859 that says that the Document is released under this License. A
860 Front-Cover Text may be at most 5 words, and a Back-Cover Text may
863 A "Transparent" copy of the Document means a machine-readable copy,
864 represented in a format whose specification is available to the
865 general public, that is suitable for revising the document
866 straightforwardly with generic text editors or (for images composed
867 of pixels) generic paint programs or (for drawings) some widely
868 available drawing editor, and that is suitable for input to text
869 formatters or for automatic translation to a variety of formats
870 suitable for input to text formatters. A copy made in an otherwise
871 Transparent file format whose markup, or absence of markup, has
872 been arranged to thwart or discourage subsequent modification by
873 readers is not Transparent. An image format is not Transparent if
874 used for any substantial amount of text. A copy that is not
875 "Transparent" is called "Opaque".
877 Examples of suitable formats for Transparent copies include plain
878 ASCII without markup, Texinfo input format, LaTeX input format,
879 SGML or XML using a publicly available DTD, and standard-conforming
880 simple HTML, PostScript or PDF designed for human modification.
881 Examples of transparent image formats include PNG, XCF and JPG.
882 Opaque formats include proprietary formats that can be read and
883 edited only by proprietary word processors, SGML or XML for which
884 the DTD and/or processing tools are not generally available, and
885 the machine-generated HTML, PostScript or PDF produced by some word
886 processors for output purposes only.
888 The "Title Page" means, for a printed book, the title page itself,
889 plus such following pages as are needed to hold, legibly, the
890 material this License requires to appear in the title page. For
891 works in formats which do not have any title page as such, "Title
892 Page" means the text near the most prominent appearance of the
893 work's title, preceding the beginning of the body of the text.
895 The "publisher" means any person or entity that distributes copies
896 of the Document to the public.
898 A section "Entitled XYZ" means a named subunit of the Document
899 whose title either is precisely XYZ or contains XYZ in parentheses
900 following text that translates XYZ in another language. (Here XYZ
901 stands for a specific section name mentioned below, such as
902 "Acknowledgements", "Dedications", "Endorsements", or "History".)
903 To "Preserve the Title" of such a section when you modify the
904 Document means that it remains a section "Entitled XYZ" according
907 The Document may include Warranty Disclaimers next to the notice
908 which states that this License applies to the Document. These
909 Warranty Disclaimers are considered to be included by reference in
910 this License, but only as regards disclaiming warranties: any other
911 implication that these Warranty Disclaimers may have is void and
912 has no effect on the meaning of this License.
916 You may copy and distribute the Document in any medium, either
917 commercially or noncommercially, provided that this License, the
918 copyright notices, and the license notice saying this License
919 applies to the Document are reproduced in all copies, and that you
920 add no other conditions whatsoever to those of this License. You
921 may not use technical measures to obstruct or control the reading
922 or further copying of the copies you make or distribute. However,
923 you may accept compensation in exchange for copies. If you
924 distribute a large enough number of copies you must also follow the
925 conditions in section 3.
927 You may also lend copies, under the same conditions stated above,
928 and you may publicly display copies.
930 3. COPYING IN QUANTITY
932 If you publish printed copies (or copies in media that commonly
933 have printed covers) of the Document, numbering more than 100, and
934 the Document's license notice requires Cover Texts, you must
935 enclose the copies in covers that carry, clearly and legibly, all
936 these Cover Texts: Front-Cover Texts on the front cover, and
937 Back-Cover Texts on the back cover. Both covers must also clearly
938 and legibly identify you as the publisher of these copies. The
939 front cover must present the full title with all words of the title
940 equally prominent and visible. You may add other material on the
941 covers in addition. Copying with changes limited to the covers, as
942 long as they preserve the title of the Document and satisfy these
943 conditions, can be treated as verbatim copying in other respects.
945 If the required texts for either cover are too voluminous to fit
946 legibly, you should put the first ones listed (as many as fit
947 reasonably) on the actual cover, and continue the rest onto
950 If you publish or distribute Opaque copies of the Document
951 numbering more than 100, you must either include a machine-readable
952 Transparent copy along with each Opaque copy, or state in or with
953 each Opaque copy a computer-network location from which the general
954 network-using public has access to download using public-standard
955 network protocols a complete Transparent copy of the Document, free
956 of added material. If you use the latter option, you must take
957 reasonably prudent steps, when you begin distribution of Opaque
958 copies in quantity, to ensure that this Transparent copy will
959 remain thus accessible at the stated location until at least one
960 year after the last time you distribute an Opaque copy (directly or
961 through your agents or retailers) of that edition to the public.
963 It is requested, but not required, that you contact the authors of
964 the Document well before redistributing any large number of copies,
965 to give them a chance to provide you with an updated version of the
970 You may copy and distribute a Modified Version of the Document
971 under the conditions of sections 2 and 3 above, provided that you
972 release the Modified Version under precisely this License, with the
973 Modified Version filling the role of the Document, thus licensing
974 distribution and modification of the Modified Version to whoever
975 possesses a copy of it. In addition, you must do these things in
976 the Modified Version:
978 A. Use in the Title Page (and on the covers, if any) a title
979 distinct from that of the Document, and from those of previous
980 versions (which should, if there were any, be listed in the
981 History section of the Document). You may use the same title
982 as a previous version if the original publisher of that
983 version gives permission.
985 B. List on the Title Page, as authors, one or more persons or
986 entities responsible for authorship of the modifications in
987 the Modified Version, together with at least five of the
988 principal authors of the Document (all of its principal
989 authors, if it has fewer than five), unless they release you
990 from this requirement.
992 C. State on the Title page the name of the publisher of the
993 Modified Version, as the publisher.
995 D. Preserve all the copyright notices of the Document.
997 E. Add an appropriate copyright notice for your modifications
998 adjacent to the other copyright notices.
1000 F. Include, immediately after the copyright notices, a license
1001 notice giving the public permission to use the Modified
1002 Version under the terms of this License, in the form shown in
1005 G. Preserve in that license notice the full lists of Invariant
1006 Sections and required Cover Texts given in the Document's
1009 H. Include an unaltered copy of this License.
1011 I. Preserve the section Entitled "History", Preserve its Title,
1012 and add to it an item stating at least the title, year, new
1013 authors, and publisher of the Modified Version as given on the
1014 Title Page. If there is no section Entitled "History" in the
1015 Document, create one stating the title, year, authors, and
1016 publisher of the Document as given on its Title Page, then add
1017 an item describing the Modified Version as stated in the
1020 J. Preserve the network location, if any, given in the Document
1021 for public access to a Transparent copy of the Document, and
1022 likewise the network locations given in the Document for
1023 previous versions it was based on. These may be placed in the
1024 "History" section. You may omit a network location for a work
1025 that was published at least four years before the Document
1026 itself, or if the original publisher of the version it refers
1027 to gives permission.
1029 K. For any section Entitled "Acknowledgements" or "Dedications",
1030 Preserve the Title of the section, and preserve in the section
1031 all the substance and tone of each of the contributor
1032 acknowledgements and/or dedications given therein.
1034 L. Preserve all the Invariant Sections of the Document, unaltered
1035 in their text and in their titles. Section numbers or the
1036 equivalent are not considered part of the section titles.
1038 M. Delete any section Entitled "Endorsements". Such a section
1039 may not be included in the Modified Version.
1041 N. Do not retitle any existing section to be Entitled
1042 "Endorsements" or to conflict in title with any Invariant
1045 O. Preserve any Warranty Disclaimers.
1047 If the Modified Version includes new front-matter sections or
1048 appendices that qualify as Secondary Sections and contain no
1049 material copied from the Document, you may at your option designate
1050 some or all of these sections as invariant. To do this, add their
1051 titles to the list of Invariant Sections in the Modified Version's
1052 license notice. These titles must be distinct from any other
1055 You may add a section Entitled "Endorsements", provided it contains
1056 nothing but endorsements of your Modified Version by various
1057 parties--for example, statements of peer review or that the text
1058 has been approved by an organization as the authoritative
1059 definition of a standard.
1061 You may add a passage of up to five words as a Front-Cover Text,
1062 and a passage of up to 25 words as a Back-Cover Text, to the end of
1063 the list of Cover Texts in the Modified Version. Only one passage
1064 of Front-Cover Text and one of Back-Cover Text may be added by (or
1065 through arrangements made by) any one entity. If the Document
1066 already includes a cover text for the same cover, previously added
1067 by you or by arrangement made by the same entity you are acting on
1068 behalf of, you may not add another; but you may replace the old
1069 one, on explicit permission from the previous publisher that added
1072 The author(s) and publisher(s) of the Document do not by this
1073 License give permission to use their names for publicity for or to
1074 assert or imply endorsement of any Modified Version.
1076 5. COMBINING DOCUMENTS
1078 You may combine the Document with other documents released under
1079 this License, under the terms defined in section 4 above for
1080 modified versions, provided that you include in the combination all
1081 of the Invariant Sections of all of the original documents,
1082 unmodified, and list them all as Invariant Sections of your
1083 combined work in its license notice, and that you preserve all
1084 their Warranty Disclaimers.
1086 The combined work need only contain one copy of this License, and
1087 multiple identical Invariant Sections may be replaced with a single
1088 copy. If there are multiple Invariant Sections with the same name
1089 but different contents, make the title of each such section unique
1090 by adding at the end of it, in parentheses, the name of the
1091 original author or publisher of that section if known, or else a
1092 unique number. Make the same adjustment to the section titles in
1093 the list of Invariant Sections in the license notice of the
1096 In the combination, you must combine any sections Entitled
1097 "History" in the various original documents, forming one section
1098 Entitled "History"; likewise combine any sections Entitled
1099 "Acknowledgements", and any sections Entitled "Dedications". You
1100 must delete all sections Entitled "Endorsements."
1102 6. COLLECTIONS OF DOCUMENTS
1104 You may make a collection consisting of the Document and other
1105 documents released under this License, and replace the individual
1106 copies of this License in the various documents with a single copy
1107 that is included in the collection, provided that you follow the
1108 rules of this License for verbatim copying of each of the documents
1109 in all other respects.
1111 You may extract a single document from such a collection, and
1112 distribute it individually under this License, provided you insert
1113 a copy of this License into the extracted document, and follow this
1114 License in all other respects regarding verbatim copying of that
1117 7. AGGREGATION WITH INDEPENDENT WORKS
1119 A compilation of the Document or its derivatives with other
1120 separate and independent documents or works, in or on a volume of a
1121 storage or distribution medium, is called an "aggregate" if the
1122 copyright resulting from the compilation is not used to limit the
1123 legal rights of the compilation's users beyond what the individual
1124 works permit. When the Document is included in an aggregate, this
1125 License does not apply to the other works in the aggregate which
1126 are not themselves derivative works of the Document.
1128 If the Cover Text requirement of section 3 is applicable to these
1129 copies of the Document, then if the Document is less than one half
1130 of the entire aggregate, the Document's Cover Texts may be placed
1131 on covers that bracket the Document within the aggregate, or the
1132 electronic equivalent of covers if the Document is in electronic
1133 form. Otherwise they must appear on printed covers that bracket
1134 the whole aggregate.
1138 Translation is considered a kind of modification, so you may
1139 distribute translations of the Document under the terms of section
1140 4. Replacing Invariant Sections with translations requires special
1141 permission from their copyright holders, but you may include
1142 translations of some or all Invariant Sections in addition to the
1143 original versions of these Invariant Sections. You may include a
1144 translation of this License, and all the license notices in the
1145 Document, and any Warranty Disclaimers, provided that you also
1146 include the original English version of this License and the
1147 original versions of those notices and disclaimers. In case of a
1148 disagreement between the translation and the original version of
1149 this License or a notice or disclaimer, the original version will
1152 If a section in the Document is Entitled "Acknowledgements",
1153 "Dedications", or "History", the requirement (section 4) to
1154 Preserve its Title (section 1) will typically require changing the
1159 You may not copy, modify, sublicense, or distribute the Document
1160 except as expressly provided under this License. Any attempt
1161 otherwise to copy, modify, sublicense, or distribute it is void,
1162 and will automatically terminate your rights under this License.
1164 However, if you cease all violation of this License, then your
1165 license from a particular copyright holder is reinstated (a)
1166 provisionally, unless and until the copyright holder explicitly and
1167 finally terminates your license, and (b) permanently, if the
1168 copyright holder fails to notify you of the violation by some
1169 reasonable means prior to 60 days after the cessation.
1171 Moreover, your license from a particular copyright holder is
1172 reinstated permanently if the copyright holder notifies you of the
1173 violation by some reasonable means, this is the first time you have
1174 received notice of violation of this License (for any work) from
1175 that copyright holder, and you cure the violation prior to 30 days
1176 after your receipt of the notice.
1178 Termination of your rights under this section does not terminate
1179 the licenses of parties who have received copies or rights from you
1180 under this License. If your rights have been terminated and not
1181 permanently reinstated, receipt of a copy of some or all of the
1182 same material does not give you any rights to use it.
1184 10. FUTURE REVISIONS OF THIS LICENSE
1186 The Free Software Foundation may publish new, revised versions of
1187 the GNU Free Documentation License from time to time. Such new
1188 versions will be similar in spirit to the present version, but may
1189 differ in detail to address new problems or concerns. See
1190 <http://www.gnu.org/copyleft/>.
1192 Each version of the License is given a distinguishing version
1193 number. If the Document specifies that a particular numbered
1194 version of this License "or any later version" applies to it, you
1195 have the option of following the terms and conditions either of
1196 that specified version or of any later version that has been
1197 published (not as a draft) by the Free Software Foundation. If the
1198 Document does not specify a version number of this License, you may
1199 choose any version ever published (not as a draft) by the Free
1200 Software Foundation. If the Document specifies that a proxy can
1201 decide which future versions of this License can be used, that
1202 proxy's public statement of acceptance of a version permanently
1203 authorizes you to choose that version for the Document.
1207 "Massive Multiauthor Collaboration Site" (or "MMC Site") means any
1208 World Wide Web server that publishes copyrightable works and also
1209 provides prominent facilities for anybody to edit those works. A
1210 public wiki that anybody can edit is an example of such a server.
1211 A "Massive Multiauthor Collaboration" (or "MMC") contained in the
1212 site means any set of copyrightable works thus published on the MMC
1215 "CC-BY-SA" means the Creative Commons Attribution-Share Alike 3.0
1216 license published by Creative Commons Corporation, a not-for-profit
1217 corporation with a principal place of business in San Francisco,
1218 California, as well as future copyleft versions of that license
1219 published by that same organization.
1221 "Incorporate" means to publish or republish a Document, in whole or
1222 in part, as part of another Document.
1224 An MMC is "eligible for relicensing" if it is licensed under this
1225 License, and if all works that were first published under this
1226 License somewhere other than this MMC, and subsequently
1227 incorporated in whole or in part into the MMC, (1) had no cover
1228 texts or invariant sections, and (2) were thus incorporated prior
1229 to November 1, 2008.
1231 The operator of an MMC Site may republish an MMC contained in the
1232 site under CC-BY-SA on the same site at any time before August 1,
1233 2009, provided the MMC is eligible for relicensing.
1235 ADDENDUM: How to use this License for your documents
1236 ====================================================
1238 To use this License in a document you have written, include a copy of
1239 the License in the document and put the following copyright and license
1240 notices just after the title page:
1242 Copyright (C) YEAR YOUR NAME.
1243 Permission is granted to copy, distribute and/or modify this document
1244 under the terms of the GNU Free Documentation License, Version 1.3
1245 or any later version published by the Free Software Foundation;
1246 with no Invariant Sections, no Front-Cover Texts, and no Back-Cover
1247 Texts. A copy of the license is included in the section entitled ``GNU
1248 Free Documentation License''.
1250 If you have Invariant Sections, Front-Cover Texts and Back-Cover
1251 Texts, replace the "with...Texts." line with this:
1253 with the Invariant Sections being LIST THEIR TITLES, with
1254 the Front-Cover Texts being LIST, and with the Back-Cover Texts
1257 If you have Invariant Sections without Cover Texts, or some other
1258 combination of the three, merge those two alternatives to suit the
1261 If your document contains nontrivial examples of program code, we
1262 recommend releasing these examples in parallel under your choice of free
1263 software license, such as the GNU General Public License, to permit
1264 their use in free software.
1267 File: libitm.info, Node: Index, Prev: GNU Free Documentation License, Up: Top
1275 * FDL, GNU Free Documentation License: GNU Free Documentation License.
1277 * Introduction: Top. (line 6)
1283 Node: Enabling libitm
\7f2045
1284 Node: C/C++ Language Constructs for TM
\7f2440
1285 Node: The libitm ABI
\7f3923
1286 Ref: txn-code-properties
\7f7721
1287 Node: Internals
\7f18026
1288 Ref: serial-lock-impl
\7f28064
1289 Ref: progress-guarantees
\7f32825
1290 Node: GNU Free Documentation License
\7f35103