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