1 This is libitm.info, produced by makeinfo version 4.12 from
2 /space/rguenther/gcc-4.7.3/gcc-4.7.3/libitm/libitm.texi.
4 Copyright (C) 2011 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 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 3.3.6 [No changes] Scatter/gather calls
147 ---------------------------------------
149 3.3.7 [No changes] Serial and irrevocable mode
150 ----------------------------------------------
152 3.3.8 [No changes] Transaction descriptor
153 -----------------------------------------
155 3.3.9 Store allocation
156 ----------------------
158 There is no `getTransaction' function.
160 3.3.10 [No changes] Naming conventions
161 --------------------------------------
163 3.3.11 Function pointer encryption
164 ----------------------------------
166 Currently, this is not implemented.
168 3.4 Types and macros list
169 =========================
171 `_ITM_codeProperties' has changed, *note Starting a transaction:
172 txn-code-properties. `_ITM_srcLocation' is not used.
177 3.5.1 Initialization and finalization functions
178 -----------------------------------------------
180 These functions are not part of the ABI.
182 3.5.2 [No changes] Version checking
183 -----------------------------------
185 3.5.3 [No changes] Error reporting
186 ----------------------------------
188 3.5.4 [No changes] inTransaction call
189 -------------------------------------
191 3.5.5 State manipulation functions
192 ----------------------------------
194 There is no `getTransaction' function. Transaction identifiers for
195 nested transactions will be ordered but not necessarily sequential
196 (i.e., for a nested transaction's identifier IN and its enclosing
197 transaction's identifier IE, it is guaranteed that IN >= IE).
199 3.5.6 [No changes] Source locations
200 -----------------------------------
202 3.5.7 Starting a transaction
203 ----------------------------
205 3.5.7.1 Transaction code properties
206 ...................................
208 The bit `hasNoXMMUpdate' is instead called `hasNoVectorUpdate'. Iff it
209 is set, vector register save/restore is not necessary for any target
212 The `hasNoFloatUpdate' bit (`0x0010') is new. Iff it is set, floating
213 point register save/restore is not necessary for any target machine.
215 `undoLogCode' is not supported and a fatal runtime error will be
216 raised if this bit is set. It is not properly defined in the ABI why
217 barriers other than undo logging are not present; Are they not
218 necessary (e.g., a transaction operating purely on thread-local data)
219 or have they been omitted by the compiler because it thinks that some
220 kind of global synchronization (e.g., serial mode) might perform
221 better? The specification suggests that the latter might be the case,
222 but the former seems to be more useful.
224 The `readOnly' bit (`0x4000') is new. *TODO* Lexical or dynamic
227 `hasNoRetry' is not supported. If this bit is not set, but
228 `hasNoAbort' is set, the library can assume that transaction rollback
229 will not be requested.
231 It would be useful if the absence of externally-triggered rollbacks
232 would be reported for the dynamic scope as well, not just for the
233 lexical scope (`hasNoAbort'). Without this, a library cannot exploit
234 this together with flat nesting.
236 `exceptionBlock' is not supported because exception blocks are not
239 3.5.7.2 [No changes] Windows exception state
240 ............................................
242 3.5.7.3 [No changes] Other machine state
243 ........................................
245 3.5.7.4 [No changes] Results from beginTransaction
246 ..................................................
248 3.5.8 Aborting a transaction
249 ----------------------------
251 `_ITM_rollbackTransaction' is not supported. `_ITM_abortTransaction' is
252 supported but the abort reasons `exceptionBlockAbort', `TMConflict',
253 and `userRetry' are not supported. There are no exception blocks in
254 general, so the related cases also do not have to be considered. To
255 encode `__transaction_cancel [[outer]]', compilers must set the new
256 `outerAbort' bit (`0x10') additionally to the `userAbort' bit in the
259 3.5.9 Committing a transaction
260 ------------------------------
262 The exception handling (EH) scheme is different. The Intel ABI requires
263 the `_ITM_tryCommitTransaction' function that will return even when the
264 commit failed and will have to be matched with calls to either
265 `_ITM_abortTransaction' or `_ITM_commitTransaction'. In contrast, gcc
266 relies on transactional wrappers for the functions of the Exception
267 Handling ABI and on one additional commit function (shown below). This
268 allows the TM to keep track of EH internally and thus it does not have
269 to embed the cleanup of EH state into the existing EH code in the
270 program. `_ITM_tryCommitTransaction' is not supported.
271 `_ITM_commitTransactionToId' is also not supported because the
272 propagation of thrown exceptions will not bypass commits of nested
275 void _ITM_commitTransactionEH(void *exc_ptr) ITM_REGPARM;
276 void *_ITM_cxa_allocate_exception (size_t);
277 void _ITM_cxa_throw (void *obj, void *tinfo, void *dest);
278 void *_ITM_cxa_begin_catch (void *exc_ptr);
279 void _ITM_cxa_end_catch (void);
281 `_ITM_commitTransactionEH' must be called to commit a transaction if
282 an exception could be in flight at this position in the code. `exc_ptr'
283 is the current exception or zero if there is no current exception. The
284 `_ITM_cxa...' functions are transactional wrappers for the respective
285 `__cxa...' functions and must be called instead of these in
288 To support this EH scheme, libstdc++ needs to provide one additional
289 function (`_cxa_tm_cleanup'), which is used by the TM to clean up the
290 exception handling state while rolling back a transaction:
292 void __cxa_tm_cleanup (void *unthrown_obj, void *cleanup_exc,
293 unsigned int caught_count);
295 `unthrown_obj' is non-null if the program called
296 `__cxa_allocate_exception' for this exception but did not yet called
297 `__cxa_throw' for it. `cleanup_exc' is non-null if the program is
298 currently processing a cleanup along an exception path but has not
299 caught this exception yet. `caught_count' is the nesting depth of
300 `__cxa_begin_catch' within the transaction (which can be counted by the
301 TM using `_ITM_cxa_begin_catch' and `_ITM_cxa_end_catch');
302 `__cxa_tm_cleanup' then performs rollback by essentially performing
303 `__cxa_end_catch' that many times.
305 3.5.10 Exception handling support
306 ---------------------------------
308 Currently, there is no support for functionality like
309 `__transaction_cancel throw' as described in the C++ TM specification.
310 Supporting this should be possible with the EH scheme explained
311 previously because via the transactional wrappers for the EH ABI, the
312 TM is able to observe and intercept EH.
314 3.5.11 [No changes] Transition to serial-irrevocable mode
315 ---------------------------------------------------------
317 3.5.12 [No changes] Data transfer functions
318 -------------------------------------------
320 3.5.13 [No changes] Transactional memory copies
321 -----------------------------------------------
323 3.5.14 Transactional versions of memmove
324 ----------------------------------------
326 If either the source or destination memory region is to be accessed
327 nontransactionally, then source and destination regions must not be
328 overlapping. The respective `_ITM_memmove' functions are still
329 available but a fatal runtime error will be raised if such regions do
330 overlap. To support this functionality, the ABI would have to specify
331 how the intersection of the regions has to be accessed (i.e.,
332 transactionally or nontransactionally).
334 3.5.15 [No changes] Transactional versions of memset
335 ----------------------------------------------------
337 3.5.16 [No changes] Logging functions
338 -------------------------------------
340 3.5.17 User-registered commit and undo actions
341 ----------------------------------------------
343 Commit actions will get executed in the same order in which the
344 respective calls to `_ITM_addUserCommitAction' happened. Only
345 `_ITM_noTransactionId' is allowed as value for the
346 `resumingTransactionId' argument. Commit actions get executed after
347 privatization safety has been ensured.
349 Undo actions will get executed in reverse order compared to the
350 order in which the respective calls to `_ITM_addUserUndoAction'
351 happened. The ordering of undo actions w.r.t. the roll-back of other
352 actions (e.g., data transfers or memory allocations) is undefined.
354 `_ITM_getThreadnum' is not supported currently because its only
355 purpose is to provide a thread ID that matches some assumed performance
356 tuning output, but this output is not part of the ABI nor further
359 `_ITM_dropReferences' is not supported currently because its
360 semantics and the intention behind it is not entirely clear. The
361 specification suggests that this function is necessary because of
362 certain orderings of data transfer undos and the releasing of memory
363 regions (i.e., privatization). However, this ordering is never defined,
364 nor is the ordering of dropping references w.r.t. other events.
366 3.5.18 [New] Transactional indirect calls
367 -----------------------------------------
369 Indirect calls (i.e., calls through a function pointer) within
370 transactions should execute the transactional clone of the original
371 function (i.e., a clone of the original that has been fully
372 instrumented to use the TM runtime), if such a clone is available. The
373 runtime provides two functions to register/deregister clone tables:
380 void _ITM_registerTMCloneTable (clone_entry *table, size_t entries);
381 void _ITM_deregisterTMCloneTable (clone_entry *table);
383 Registered tables must be writable by the TM runtime, and must be
384 live throughout the life-time of the TM runtime.
386 *TODO* The intention was always to drop the registration functions
387 entirely, and create a new ELF Phdr describing the linker-sorted table.
388 Much like what currently happens for `PT_GNU_EH_FRAME'. This work kept
389 getting bogged down in how to represent the N different code generation
390 variants. We clearly needed at least two--SW and HW transactional
391 clones--but there was always a suggestion of more variants for
392 different TM assumptions/invariants.
394 The compiler can then use two TM runtime functions to perform
395 indirect calls in transactions:
396 void *_ITM_getTMCloneOrIrrevocable (void *function) ITM_REGPARM;
397 void *_ITM_getTMCloneSafe (void *function) ITM_REGPARM;
399 If there is a registered clone for supplied function, both will
400 return a pointer to the clone. If not, the first runtime function will
401 attempt to switch to serial-irrevocable mode and return the original
402 pointer, whereas the second will raise a fatal runtime error.
404 3.5.19 [New] Transactional dynamic memory management
405 ----------------------------------------------------
407 void *_ITM_malloc (size_t)
408 __attribute__((__malloc__)) ITM_PURE;
409 void *_ITM_calloc (size_t, size_t)
410 __attribute__((__malloc__)) ITM_PURE;
411 void _ITM_free (void *) ITM_PURE;
413 These functions are essentially transactional wrappers for `malloc',
414 `calloc', and `free'. Within transactions, the compiler should replace
415 calls to the original functions with calls to the wrapper functions.
417 3.6 [No changes] Future Enhancements to the ABI
418 ===============================================
423 The code examples might not be correct w.r.t. the current version of
424 the ABI, especially everything related to exception handling.
426 3.8 [New] Memory model
427 ======================
429 The ABI should define a memory model and the ordering that is
430 guaranteed for data transfers and commit/undo actions, or at least
431 refer to another memory model that needs to be preserved. Without that,
432 the compiler cannot ensure the memory model specified on the level of
433 the programming language (e.g., by the C++ TM specification).
435 For example, if a transactional load is ordered before another
436 load/store, then the TM runtime must also ensure this ordering when
437 accessing shared state. If not, this might break the kind of
438 publication safety used in the C++ TM specification. Likewise, the TM
439 runtime must ensure privatization safety.
442 File: libitm.info, Node: Internals, Next: GNU Free Documentation License, Prev: The libitm ABI, Up: Top
447 4.1 TM methods and method groups
448 ================================
450 libitm supports several ways of synchronizing transactions with each
451 other. These TM methods (or TM algorithms) are implemented in the form
452 of subclasses of `abi_dispatch', which provide methods for
453 transactional loads and stores as well as callbacks for rollback and
454 commit. All methods that are compatible with each other (i.e., that
455 let concurrently running transactions still synchronize correctly even
456 if different methods are used) belong to the same TM method group.
457 Pointers to TM methods can be obtained using the factory methods
458 prefixed with `dispatch_' in `libitm_i.h'. There are two special
459 methods, `dispatch_serial' and `dispatch_serialirr', that are
460 compatible with all methods because they run transactions completely in
463 4.1.1 TM method life cycle
464 --------------------------
466 The state of TM methods does not change after construction, but they do
467 alter the state of transactions that use this method. However, because
468 per-transaction data gets used by several methods, `gtm_thread' is
469 responsible for setting an initial state that is useful for all methods.
470 After that, methods are responsible for resetting/clearing this state
471 on each rollback or commit (of outermost transactions), so that the
472 transaction executed next is not affected by the previous transaction.
474 There is also global state associated with each method group, which
475 is initialized and shut down (`method_group::init()' and `fini()') when
476 switching between method groups (see `retry.cc').
478 4.1.2 Selecting the default method
479 ----------------------------------
481 The default method that libitm uses for freshly started transactions
482 (but not necessarily for restarted transactions) can be set via an
483 environment variable (`ITM_DEFAULT_METHOD'), whose value should be
484 equal to the name of one of the factory methods returning abi_dispatch
485 subclasses but without the "dispatch_" prefix (e.g., "serialirr"
486 instead of `GTM::dispatch_serialirr()').
488 Note that this environment variable is only a hint for libitm and
489 might not be supported in the future.
491 4.2 Nesting: flat vs. closed
492 ============================
494 We support two different kinds of nesting of transactions. In the case
495 of _flat nesting_, the nesting structure is flattened and all nested
496 transactions are subsumed by the enclosing transaction. In contrast,
497 with _closed nesting_, nested transactions that have not yet committed
498 can be rolled back separately from the enclosing transactions; when they
499 commit, they are subsumed by the enclosing transaction, and their
500 effects will be finally committed when the outermost transaction
501 commits. _Open nesting_ (where nested transactions can commit
502 independently of the enclosing transactions) are not supported.
504 Flat nesting is the default nesting mode, but closed nesting is
505 supported and used when transactions contain user-controlled aborts
506 (`__transaction_cancel' statements). We assume that user-controlled
507 aborts are rare in typical code and used mostly in exceptional
508 situations. Thus, it makes more sense to use flat nesting by default
509 to avoid the performance overhead of the additional checkpoints
510 required for closed nesting. User-controlled aborts will correctly
511 abort the innermost enclosing transaction, whereas the whole (i.e.,
512 outermost) transaction will be restarted otherwise (e.g., when a
513 transaction encounters data conflicts during optimistic execution).
515 4.3 Locking conventions
516 =======================
518 This section documents the locking scheme and rules for all uses of
519 locking in libitm. We have to support serial(-irrevocable) mode, which
520 is implemented using a global lock as explained next (called the
521 _serial lock_). To simplify the overall design, we use the same lock as
522 catch-all locking mechanism for other infrequent tasks such as
523 (de)registering clone tables or threads. Besides the serial lock, there
524 are _per-method-group locks_ that are managed by specific method groups
525 (i.e., groups of similar TM concurrency control algorithms), and
526 lock-like constructs for quiescence-based operations such as ensuring
527 privatization safety.
529 Thus, the actions that participate in the libitm-internal locking
530 are either _active transactions_ that do not run in serial mode, _serial
531 transactions_ (which (are about to) run in serial mode), and management
532 tasks that do not execute within a transaction but have acquired the
533 serial mode like a serial transaction would do (e.g., to be able to
534 register threads with libitm). Transactions become active as soon as
535 they have successfully used the serial lock to announce this globally
536 (*note Serial lock implementation: serial-lock-impl.). Likewise,
537 transactions become serial transactions as soon as they have acquired
538 the exclusive rights provided by the serial lock (i.e., serial mode,
539 which also means that there are no other concurrent active or serial
540 transactions). Note that active transactions can become serial
541 transactions when they enter serial mode during the runtime of the
544 4.3.1 State-to-lock mapping
545 ---------------------------
547 Application data is protected by the serial lock if there is a serial
548 transaction and no concurrently running active transaction (i.e.,
549 non-serial). Otherwise, application data is protected by the currently
550 selected method group, which might use per-method-group locks or other
551 mechanisms. Also note that application data that is about to be
552 privatized might not be allowed to be accessed by nontransactional code
553 until privatization safety has been ensured; the details of this are
554 handled by the current method group.
556 libitm-internal state is either protected by the serial lock or
557 accessed through custom concurrent code. The latter applies to the
558 public/shared part of a transaction object and most typical
559 method-group-specific state.
561 The former category (protected by the serial lock) includes:
562 * The list of active threads that have used transactions.
564 * The tables that map functions to their transactional clones.
566 * The current selection of which method group to use.
568 * Some method-group-specific data, or invariants of this data. For
569 example, resetting a method group to its initial state is handled
570 by switching to the same method group, so the serial lock protects
571 such resetting as well.
572 In general, such state is immutable whenever there exists an active
573 (non-serial) transaction. If there is no active transaction, a serial
574 transaction (or a thread that is not currently executing a transaction
575 but has acquired the serial lock) is allowed to modify this state (but
576 must of course be careful to not surprise the current method group's
577 implementation with such modifications).
579 4.3.2 Lock acquisition order
580 ----------------------------
582 To prevent deadlocks, locks acquisition must happen in a globally
583 agreed-upon order. Note that this applies to other forms of blocking
584 too, but does not necessarily apply to lock acquisitions that do not
585 block (e.g., trylock() calls that do not get retried forever). Note
586 that serial transactions are never return back to active transactions
587 until the transaction has committed. Likewise, active transactions
588 stay active until they have committed. Per-method-group locks are
589 typically also not released before commit.
591 Lock acquisition / blocking rules:
592 * Transactions must become active or serial before they are allowed
593 to use method-group-specific locks or blocking (i.e., the serial
594 lock must be acquired before those other locks, either in serial
597 * Any number of threads that do not currently run active
598 transactions can block while trying to get the serial lock in
599 exclusive mode. Note that active transactions must not block when
600 trying to upgrade to serial mode unless there is no other
601 transaction that is trying that (the latter is ensured by the
602 serial lock implementation.
604 * Method groups must prevent deadlocks on their locks. In
605 particular, they must also be prepared for another active
606 transaction that has acquired method-group-specific locks but is
607 blocked during an attempt to upgrade to being a serial
608 transaction. See below for details.
610 * Serial transactions can acquire method-group-specific locks
611 because 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.
629 * Active transactions blocking on per-method-group locks need to
630 check the serial lock and abort if there is a pending serial
633 * Lost wake-ups have to be prevented (e.g., by changing a bit in each
634 per-method-group lock before doing the wake-up, and only blocking
635 on this lock using a futex if this bit is not group).
637 *TODO*: Can reuse serial lock for gl-*? And if we can, does it make
638 sense to introduce further complexity in the serial lock? For gl-*, we
639 can really only avoid an abort if we do -wb and -vbv.
641 4.3.3 Serial lock implementation
642 --------------------------------
644 The serial lock implementation is optimized towards assuming that serial
645 transactions are infrequent and not the common case. However, the
646 performance of entering serial mode can matter because when only few
647 transactions are run concurrently or if there are few threads, then it
648 can be efficient to run transactions serially.
650 The serial lock is similar to a multi-reader-single-writer lock in
651 that there can be several active transactions but only one serial
652 transaction. However, we do want to avoid contention (in the lock
653 implementation) between active transactions, so we split up the reader
654 side of the lock into per-transaction flags that are true iff the
655 transaction is active. The exclusive writer side remains a shared
656 single flag, which is acquired using a CAS, for example. On the
657 fast-path, the serial lock then works similar to Dekker's algorithm but
658 with several reader flags that a serial transaction would have to check.
659 A serial transaction thus requires a list of all threads with
660 potentially active transactions; we can use the serial lock itself to
661 protect this list (i.e., only threads that have acquired the serial
662 lock can modify this list).
664 We want starvation-freedom for the serial lock to allow for using it
665 to ensure progress for potentially starved transactions (*note Progress
666 Guarantees: progress-guarantees. for details). However, this is
667 currently not enforced by the implementation of the serial lock.
669 Here is pseudo-code for the read/write fast paths of acquiring the
670 serial lock (read-to-write upgrade is similar to write_lock:
672 tx->shared_state |= active;
673 __sync_synchronize(); // or STLD membar, or C++0x seq-cst fence
674 while (!serial_lock.exclusive)
675 if (spinning_for_too_long) goto slowpath;
678 if (CAS(&serial_lock.exclusive, 0, this) != 0)
679 goto slowpath; // writer-writer contention
680 // need a membar here, but CAS already has full membar semantics
681 bool need_blocking = false;
684 for (;t->shared_state & active;)
685 if (spinning_for_too_long) { need_blocking = true; break; }
687 if (need_blocking) goto slowpath;
689 Releasing a lock in this spin-lock version then just consists of
690 resetting `tx->shared_state' to inactive or clearing
691 `serial_lock.exclusive'.
693 However, we can't rely on a pure spinlock because we need to get the
694 OS involved at some time (e.g., when there are more threads than CPUs
695 to run on). Therefore, the real implementation falls back to a
696 blocking slow path, either based on pthread mutexes or Linux futexes.
701 libitm has to consider the following cases of reentrancy:
702 * Transaction calls unsafe code that starts a new transaction: The
703 outer transaction will become a serial transaction before
704 executing unsafe code. Therefore, nesting within serial
705 transactions must work, even if the nested transaction is called
706 from within uninstrumented code.
708 * Transaction calls either a transactional wrapper or safe code,
709 which in turn starts a new transaction: It is not yet defined in
710 the specification whether this is allowed. Thus, it is undefined
711 whether libitm supports this.
713 * Code that starts new transactions might be called from within any
714 part of libitm: This kind of reentrancy would likely be rather
715 complex and can probably be avoided. Therefore, it is not
719 4.3.5 Privatization safety
720 --------------------------
722 Privatization safety is ensured by libitm using a quiescence-based
723 approach. Basically, a privatizing transaction waits until all
724 concurrent active transactions will either have finished (are not
725 active anymore) or operate on a sufficiently recent snapshot to not
726 access the privatized data anymore. This happens after the privatizing
727 transaction has stopped being an active transaction, so waiting for
728 quiescence does not contribute to deadlocks.
730 In method groups that need to ensure publication safety explicitly,
731 active transactions maintain a flag or timestamp in the public/shared
732 part of the transaction descriptor. Before blocking, privatizers need
733 to let the other transactions know that they should wake up the
736 *TODO* Ho to implement the waiters? Should those flags be
737 per-transaction or at a central place? We want to avoid one wake/wait
738 call per active transactions, so we might want to use either a tree or
739 combining to reduce the syscall overhead, or rather spin for a long
740 amount of time instead of doing blocking. Also, it would be good if
741 only the last transaction that the privatizer waits for would do the
744 4.3.6 Progress guarantees
745 -------------------------
747 Transactions that do not make progress when using the current TM method
748 will eventually try to execute in serial mode. Thus, the serial lock's
749 progress guarantees determine the progress guarantees of the whole TM.
750 Obviously, we at least need deadlock-freedom for the serial lock, but
751 it would also be good to provide starvation-freedom (informally, all
752 threads will finish executing a transaction eventually iff they get
755 However, the scheduling of transactions (e.g., thread scheduling by
756 the OS) also affects the handling of progress guarantees by the TM.
757 First, the TM can only guarantee deadlock-freedom if threads do not get
758 stopped. Likewise, low-priority threads can starve if they do not get
759 scheduled when other high-priority threads get those cycles instead.
761 If all threads get scheduled eventually, correct lock
762 implementations will provide deadlock-freedom, but might not provide
763 starvation-freedom. We can either enforce the latter in the TM's lock
764 implementation, or assume that the scheduling is sufficiently random to
765 yield a probabilistic guarantee that no thread will starve (because
766 eventually, a transaction will encounter a scheduling that will allow
767 it to run). This can indeed work well in practice but is not
768 necessarily guaranteed to work (e.g., simple spin locks can be pretty
771 Because enforcing stronger progress guarantees in the TM has a
772 higher runtime overhead, we focus on deadlock-freedom right now and
773 assume that the threads will get scheduled eventually by the OS (but
774 don't consider threads with different priorities). We should support
775 starvation-freedom for serial transactions in the future. Everything
776 beyond that is highly related to proper contention management across
777 all of the TM (including with TM method to choose), and is future work.
779 *TODO* Handling thread priorities: We want to avoid priority
780 inversion but it's unclear how often that actually matters in practice.
781 Workloads that have threads with different priorities will likely also
782 require lower latency or higher throughput for high-priority threads.
783 Therefore, it probably makes not that much sense (except for eventual
784 progress guarantees) to use priority inheritance until the TM has
785 priority-aware contention management.
788 File: libitm.info, Node: GNU Free Documentation License, Next: Index, Prev: Internals, Up: Top
790 GNU Free Documentation License
791 ******************************
793 Version 1.3, 3 November 2008
795 Copyright (C) 2000, 2001, 2002, 2007, 2008 Free Software Foundation, Inc.
798 Everyone is permitted to copy and distribute verbatim copies
799 of this license document, but changing it is not allowed.
803 The purpose of this License is to make a manual, textbook, or other
804 functional and useful document "free" in the sense of freedom: to
805 assure everyone the effective freedom to copy and redistribute it,
806 with or without modifying it, either commercially or
807 noncommercially. Secondarily, this License preserves for the
808 author and publisher a way to get credit for their work, while not
809 being considered responsible for modifications made by others.
811 This License is a kind of "copyleft", which means that derivative
812 works of the document must themselves be free in the same sense.
813 It complements the GNU General Public License, which is a copyleft
814 license designed for free software.
816 We have designed this License in order to use it for manuals for
817 free software, because free software needs free documentation: a
818 free program should come with manuals providing the same freedoms
819 that the software does. But this License is not limited to
820 software manuals; it can be used for any textual work, regardless
821 of subject matter or whether it is published as a printed book.
822 We recommend this License principally for works whose purpose is
823 instruction or reference.
825 1. APPLICABILITY AND DEFINITIONS
827 This License applies to any manual or other work, in any medium,
828 that contains a notice placed by the copyright holder saying it
829 can be distributed under the terms of this License. Such a notice
830 grants a world-wide, royalty-free license, unlimited in duration,
831 to use that work under the conditions stated herein. The
832 "Document", below, refers to any such manual or work. Any member
833 of the public is a licensee, and is addressed as "you". You
834 accept the license if you copy, modify or distribute the work in a
835 way requiring permission under copyright law.
837 A "Modified Version" of the Document means any work containing the
838 Document or a portion of it, either copied verbatim, or with
839 modifications and/or translated into another language.
841 A "Secondary Section" is a named appendix or a front-matter section
842 of the Document that deals exclusively with the relationship of the
843 publishers or authors of the Document to the Document's overall
844 subject (or to related matters) and contains nothing that could
845 fall directly within that overall subject. (Thus, if the Document
846 is in part a textbook of mathematics, a Secondary Section may not
847 explain any mathematics.) The relationship could be a matter of
848 historical connection with the subject or with related matters, or
849 of legal, commercial, philosophical, ethical or political position
852 The "Invariant Sections" are certain Secondary Sections whose
853 titles are designated, as being those of Invariant Sections, in
854 the notice that says that the Document is released under this
855 License. If a section does not fit the above definition of
856 Secondary then it is not allowed to be designated as Invariant.
857 The Document may contain zero Invariant Sections. If the Document
858 does not identify any Invariant Sections then there are none.
860 The "Cover Texts" are certain short passages of text that are
861 listed, as Front-Cover Texts or Back-Cover Texts, in the notice
862 that says that the Document is released under this License. A
863 Front-Cover Text may be at most 5 words, and a Back-Cover Text may
866 A "Transparent" copy of the Document means a machine-readable copy,
867 represented in a format whose specification is available to the
868 general public, that is suitable for revising the document
869 straightforwardly with generic text editors or (for images
870 composed of pixels) generic paint programs or (for drawings) some
871 widely available drawing editor, and that is suitable for input to
872 text formatters or for automatic translation to a variety of
873 formats suitable for input to text formatters. A copy made in an
874 otherwise Transparent file format whose markup, or absence of
875 markup, has been arranged to thwart or discourage subsequent
876 modification by readers is not Transparent. An image format is
877 not Transparent if used for any substantial amount of text. A
878 copy that is not "Transparent" is called "Opaque".
880 Examples of suitable formats for Transparent copies include plain
881 ASCII without markup, Texinfo input format, LaTeX input format,
882 SGML or XML using a publicly available DTD, and
883 standard-conforming simple HTML, PostScript or PDF designed for
884 human modification. Examples of transparent image formats include
885 PNG, XCF and JPG. Opaque formats include proprietary formats that
886 can be read and edited only by proprietary word processors, SGML or
887 XML for which the DTD and/or processing tools are not generally
888 available, and the machine-generated HTML, PostScript or PDF
889 produced by some word processors for output purposes only.
891 The "Title Page" means, for a printed book, the title page itself,
892 plus such following pages as are needed to hold, legibly, the
893 material this License requires to appear in the title page. For
894 works in formats which do not have any title page as such, "Title
895 Page" means the text near the most prominent appearance of the
896 work's title, preceding the beginning of the body of the text.
898 The "publisher" means any person or entity that distributes copies
899 of the Document to the public.
901 A section "Entitled XYZ" means a named subunit of the Document
902 whose title either is precisely XYZ or contains XYZ in parentheses
903 following text that translates XYZ in another language. (Here XYZ
904 stands for a specific section name mentioned below, such as
905 "Acknowledgements", "Dedications", "Endorsements", or "History".)
906 To "Preserve the Title" of such a section when you modify the
907 Document means that it remains a section "Entitled XYZ" according
910 The Document may include Warranty Disclaimers next to the notice
911 which states that this License applies to the Document. These
912 Warranty Disclaimers are considered to be included by reference in
913 this License, but only as regards disclaiming warranties: any other
914 implication that these Warranty Disclaimers may have is void and
915 has no effect on the meaning of this License.
919 You may copy and distribute the Document in any medium, either
920 commercially or noncommercially, provided that this License, the
921 copyright notices, and the license notice saying this License
922 applies to the Document are reproduced in all copies, and that you
923 add no other conditions whatsoever to those of this License. You
924 may not use technical measures to obstruct or control the reading
925 or further copying of the copies you make or distribute. However,
926 you may accept compensation in exchange for copies. If you
927 distribute a large enough number of copies you must also follow
928 the conditions in section 3.
930 You may also lend copies, under the same conditions stated above,
931 and you may publicly display copies.
933 3. COPYING IN QUANTITY
935 If you publish printed copies (or copies in media that commonly
936 have printed covers) of the Document, numbering more than 100, and
937 the Document's license notice requires Cover Texts, you must
938 enclose the copies in covers that carry, clearly and legibly, all
939 these Cover Texts: Front-Cover Texts on the front cover, and
940 Back-Cover Texts on the back cover. Both covers must also clearly
941 and legibly identify you as the publisher of these copies. The
942 front cover must present the full title with all words of the
943 title equally prominent and visible. You may add other material
944 on the covers in addition. Copying with changes limited to the
945 covers, as long as they preserve the title of the Document and
946 satisfy these conditions, can be treated as verbatim copying in
949 If the required texts for either cover are too voluminous to fit
950 legibly, you should put the first ones listed (as many as fit
951 reasonably) on the actual cover, and continue the rest onto
954 If you publish or distribute Opaque copies of the Document
955 numbering more than 100, you must either include a
956 machine-readable Transparent copy along with each Opaque copy, or
957 state in or with each Opaque copy a computer-network location from
958 which the general network-using public has access to download
959 using public-standard network protocols a complete Transparent
960 copy of the Document, free of added material. If you use the
961 latter option, you must take reasonably prudent steps, when you
962 begin distribution of Opaque copies in quantity, to ensure that
963 this Transparent copy will remain thus accessible at the stated
964 location until at least one year after the last time you
965 distribute an Opaque copy (directly or through your agents or
966 retailers) of that edition to the public.
968 It is requested, but not required, that you contact the authors of
969 the Document well before redistributing any large number of
970 copies, to give them a chance to provide you with an updated
971 version of the Document.
975 You may copy and distribute a Modified Version of the Document
976 under the conditions of sections 2 and 3 above, provided that you
977 release the Modified Version under precisely this License, with
978 the Modified Version filling the role of the Document, thus
979 licensing distribution and modification of the Modified Version to
980 whoever possesses a copy of it. In addition, you must do these
981 things in the Modified Version:
983 A. Use in the Title Page (and on the covers, if any) a title
984 distinct from that of the Document, and from those of
985 previous versions (which should, if there were any, be listed
986 in the History section of the Document). You may use the
987 same title as a previous version if the original publisher of
988 that version gives permission.
990 B. List on the Title Page, as authors, one or more persons or
991 entities responsible for authorship of the modifications in
992 the Modified Version, together with at least five of the
993 principal authors of the Document (all of its principal
994 authors, if it has fewer than five), unless they release you
995 from this requirement.
997 C. State on the Title page the name of the publisher of the
998 Modified Version, as the publisher.
1000 D. Preserve all the copyright notices of the Document.
1002 E. Add an appropriate copyright notice for your modifications
1003 adjacent to the other copyright notices.
1005 F. Include, immediately after the copyright notices, a license
1006 notice giving the public permission to use the Modified
1007 Version under the terms of this License, in the form shown in
1010 G. Preserve in that license notice the full lists of Invariant
1011 Sections and required Cover Texts given in the Document's
1014 H. Include an unaltered copy of this License.
1016 I. Preserve the section Entitled "History", Preserve its Title,
1017 and add to it an item stating at least the title, year, new
1018 authors, and publisher of the Modified Version as given on
1019 the Title Page. If there is no section Entitled "History" in
1020 the Document, create one stating the title, year, authors,
1021 and publisher of the Document as given on its Title Page,
1022 then add an item describing the Modified Version as stated in
1023 the previous sentence.
1025 J. Preserve the network location, if any, given in the Document
1026 for public access to a Transparent copy of the Document, and
1027 likewise the network locations given in the Document for
1028 previous versions it was based on. These may be placed in
1029 the "History" section. You may omit a network location for a
1030 work that was published at least four years before the
1031 Document itself, or if the original publisher of the version
1032 it refers to gives permission.
1034 K. For any section Entitled "Acknowledgements" or "Dedications",
1035 Preserve the Title of the section, and preserve in the
1036 section all the substance and tone of each of the contributor
1037 acknowledgements and/or dedications given therein.
1039 L. Preserve all the Invariant Sections of the Document,
1040 unaltered in their text and in their titles. Section numbers
1041 or the equivalent are not considered part of the section
1044 M. Delete any section Entitled "Endorsements". Such a section
1045 may not be included in the Modified Version.
1047 N. Do not retitle any existing section to be Entitled
1048 "Endorsements" or to conflict in title with any Invariant
1051 O. Preserve any Warranty Disclaimers.
1053 If the Modified Version includes new front-matter sections or
1054 appendices that qualify as Secondary Sections and contain no
1055 material copied from the Document, you may at your option
1056 designate some or all of these sections as invariant. To do this,
1057 add their titles to the list of Invariant Sections in the Modified
1058 Version's license notice. These titles must be distinct from any
1059 other section titles.
1061 You may add a section Entitled "Endorsements", provided it contains
1062 nothing but endorsements of your Modified Version by various
1063 parties--for example, statements of peer review or that the text
1064 has been approved by an organization as the authoritative
1065 definition of a standard.
1067 You may add a passage of up to five words as a Front-Cover Text,
1068 and a passage of up to 25 words as a Back-Cover Text, to the end
1069 of the list of Cover Texts in the Modified Version. Only one
1070 passage of Front-Cover Text and one of Back-Cover Text may be
1071 added by (or through arrangements made by) any one entity. If the
1072 Document already includes a cover text for the same cover,
1073 previously added by you or by arrangement made by the same entity
1074 you are acting on behalf of, you may not add another; but you may
1075 replace the old one, on explicit permission from the previous
1076 publisher that added the old one.
1078 The author(s) and publisher(s) of the Document do not by this
1079 License give permission to use their names for publicity for or to
1080 assert or imply endorsement of any Modified Version.
1082 5. COMBINING DOCUMENTS
1084 You may combine the Document with other documents released under
1085 this License, under the terms defined in section 4 above for
1086 modified versions, provided that you include in the combination
1087 all of the Invariant Sections of all of the original documents,
1088 unmodified, and list them all as Invariant Sections of your
1089 combined work in its license notice, and that you preserve all
1090 their Warranty Disclaimers.
1092 The combined work need only contain one copy of this License, and
1093 multiple identical Invariant Sections may be replaced with a single
1094 copy. If there are multiple Invariant Sections with the same name
1095 but different contents, make the title of each such section unique
1096 by adding at the end of it, in parentheses, the name of the
1097 original author or publisher of that section if known, or else a
1098 unique number. Make the same adjustment to the section titles in
1099 the list of Invariant Sections in the license notice of the
1102 In the combination, you must combine any sections Entitled
1103 "History" in the various original documents, forming one section
1104 Entitled "History"; likewise combine any sections Entitled
1105 "Acknowledgements", and any sections Entitled "Dedications". You
1106 must delete all sections Entitled "Endorsements."
1108 6. COLLECTIONS OF DOCUMENTS
1110 You may make a collection consisting of the Document and other
1111 documents released under this License, and replace the individual
1112 copies of this License in the various documents with a single copy
1113 that is included in the collection, provided that you follow the
1114 rules of this License for verbatim copying of each of the
1115 documents in all other respects.
1117 You may extract a single document from such a collection, and
1118 distribute it individually under this License, provided you insert
1119 a copy of this License into the extracted document, and follow
1120 this License in all other respects regarding verbatim copying of
1123 7. AGGREGATION WITH INDEPENDENT WORKS
1125 A compilation of the Document or its derivatives with other
1126 separate and independent documents or works, in or on a volume of
1127 a storage or distribution medium, is called an "aggregate" if the
1128 copyright resulting from the compilation is not used to limit the
1129 legal rights of the compilation's users beyond what the individual
1130 works permit. When the Document is included in an aggregate, this
1131 License does not apply to the other works in the aggregate which
1132 are not themselves derivative works of the Document.
1134 If the Cover Text requirement of section 3 is applicable to these
1135 copies of the Document, then if the Document is less than one half
1136 of the entire aggregate, the Document's Cover Texts may be placed
1137 on covers that bracket the Document within the aggregate, or the
1138 electronic equivalent of covers if the Document is in electronic
1139 form. Otherwise they must appear on printed covers that bracket
1140 the whole aggregate.
1144 Translation is considered a kind of modification, so you may
1145 distribute translations of the Document under the terms of section
1146 4. Replacing Invariant Sections with translations requires special
1147 permission from their copyright holders, but you may include
1148 translations of some or all Invariant Sections in addition to the
1149 original versions of these Invariant Sections. You may include a
1150 translation of this License, and all the license notices in the
1151 Document, and any Warranty Disclaimers, provided that you also
1152 include the original English version of this License and the
1153 original versions of those notices and disclaimers. In case of a
1154 disagreement between the translation and the original version of
1155 this License or a notice or disclaimer, the original version will
1158 If a section in the Document is Entitled "Acknowledgements",
1159 "Dedications", or "History", the requirement (section 4) to
1160 Preserve its Title (section 1) will typically require changing the
1165 You may not copy, modify, sublicense, or distribute the Document
1166 except as expressly provided under this License. Any attempt
1167 otherwise to copy, modify, sublicense, or distribute it is void,
1168 and will automatically terminate your rights under this License.
1170 However, if you cease all violation of this License, then your
1171 license from a particular copyright holder is reinstated (a)
1172 provisionally, unless and until the copyright holder explicitly
1173 and finally terminates your license, and (b) permanently, if the
1174 copyright holder fails to notify you of the violation by some
1175 reasonable means prior to 60 days after the cessation.
1177 Moreover, your license from a particular copyright holder is
1178 reinstated permanently if the copyright holder notifies you of the
1179 violation by some reasonable means, this is the first time you have
1180 received notice of violation of this License (for any work) from
1181 that copyright holder, and you cure the violation prior to 30 days
1182 after your receipt of the notice.
1184 Termination of your rights under this section does not terminate
1185 the licenses of parties who have received copies or rights from
1186 you under this License. If your rights have been terminated and
1187 not permanently reinstated, receipt of a copy of some or all of
1188 the same material does not give you any rights to use it.
1190 10. FUTURE REVISIONS OF THIS LICENSE
1192 The Free Software Foundation may publish new, revised versions of
1193 the GNU Free Documentation License from time to time. Such new
1194 versions will be similar in spirit to the present version, but may
1195 differ in detail to address new problems or concerns. See
1196 `http://www.gnu.org/copyleft/'.
1198 Each version of the License is given a distinguishing version
1199 number. If the Document specifies that a particular numbered
1200 version of this License "or any later version" applies to it, you
1201 have the option of following the terms and conditions either of
1202 that specified version or of any later version that has been
1203 published (not as a draft) by the Free Software Foundation. If
1204 the Document does not specify a version number of this License,
1205 you may choose any version ever published (not as a draft) by the
1206 Free Software Foundation. If the Document specifies that a proxy
1207 can decide which future versions of this License can be used, that
1208 proxy's public statement of acceptance of a version permanently
1209 authorizes you to choose that version for the Document.
1213 "Massive Multiauthor Collaboration Site" (or "MMC Site") means any
1214 World Wide Web server that publishes copyrightable works and also
1215 provides prominent facilities for anybody to edit those works. A
1216 public wiki that anybody can edit is an example of such a server.
1217 A "Massive Multiauthor Collaboration" (or "MMC") contained in the
1218 site means any set of copyrightable works thus published on the MMC
1221 "CC-BY-SA" means the Creative Commons Attribution-Share Alike 3.0
1222 license published by Creative Commons Corporation, a not-for-profit
1223 corporation with a principal place of business in San Francisco,
1224 California, as well as future copyleft versions of that license
1225 published by that same organization.
1227 "Incorporate" means to publish or republish a Document, in whole or
1228 in part, as part of another Document.
1230 An MMC is "eligible for relicensing" if it is licensed under this
1231 License, and if all works that were first published under this
1232 License somewhere other than this MMC, and subsequently
1233 incorporated in whole or in part into the MMC, (1) had no cover
1234 texts or invariant sections, and (2) were thus incorporated prior
1235 to November 1, 2008.
1237 The operator of an MMC Site may republish an MMC contained in the
1238 site under CC-BY-SA on the same site at any time before August 1,
1239 2009, provided the MMC is eligible for relicensing.
1242 ADDENDUM: How to use this License for your documents
1243 ====================================================
1245 To use this License in a document you have written, include a copy of
1246 the License in the document and put the following copyright and license
1247 notices just after the title page:
1249 Copyright (C) YEAR YOUR NAME.
1250 Permission is granted to copy, distribute and/or modify this document
1251 under the terms of the GNU Free Documentation License, Version 1.3
1252 or any later version published by the Free Software Foundation;
1253 with no Invariant Sections, no Front-Cover Texts, and no Back-Cover
1254 Texts. A copy of the license is included in the section entitled ``GNU
1255 Free Documentation License''.
1257 If you have Invariant Sections, Front-Cover Texts and Back-Cover
1258 Texts, replace the "with...Texts." line with this:
1260 with the Invariant Sections being LIST THEIR TITLES, with
1261 the Front-Cover Texts being LIST, and with the Back-Cover Texts
1264 If you have Invariant Sections without Cover Texts, or some other
1265 combination of the three, merge those two alternatives to suit the
1268 If your document contains nontrivial examples of program code, we
1269 recommend releasing these examples in parallel under your choice of
1270 free software license, such as the GNU General Public License, to
1271 permit their use in free software.
1274 File: libitm.info, Node: Index, Prev: GNU Free Documentation License, Up: Top
1282 * FDL, GNU Free Documentation License: GNU Free Documentation License.
1284 * Introduction: Top. (line 6)
1290 Node: Enabling libitm
\7f2080
1291 Node: C/C++ Language Constructs for TM
\7f2474
1292 Node: The libitm ABI
\7f3954
1293 Ref: txn-code-properties
\7f7322
1294 Node: Internals
\7f17597
1295 Ref: serial-lock-impl
\7f27622
1296 Ref: progress-guarantees
\7f32372
1297 Node: GNU Free Documentation License
\7f34646
projects / platform / upstream / gcc48.git / blob