Daily bump.
[official-gcc.git] / libitm / beginend.cc
blob6110cfdf688ba3a5128961b20a222905e09bea1a
1 /* Copyright (C) 2008-2014 Free Software Foundation, Inc.
2 Contributed by Richard Henderson <rth@redhat.com>.
4 This file is part of the GNU Transactional Memory Library (libitm).
6 Libitm is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3 of the License, or
9 (at your option) any later version.
11 Libitm is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
13 FOR A PARTICULAR PURPOSE. See the GNU General Public License for
14 more details.
16 Under Section 7 of GPL version 3, you are granted additional
17 permissions described in the GCC Runtime Library Exception, version
18 3.1, as published by the Free Software Foundation.
20 You should have received a copy of the GNU General Public License and
21 a copy of the GCC Runtime Library Exception along with this program;
22 see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 <http://www.gnu.org/licenses/>. */
25 #include "libitm_i.h"
26 #include <pthread.h>
29 using namespace GTM;
31 #if !defined(HAVE_ARCH_GTM_THREAD) || !defined(HAVE_ARCH_GTM_THREAD_DISP)
32 extern __thread gtm_thread_tls _gtm_thr_tls;
33 #endif
35 gtm_rwlock GTM::gtm_thread::serial_lock;
36 gtm_thread *GTM::gtm_thread::list_of_threads = 0;
37 unsigned GTM::gtm_thread::number_of_threads = 0;
39 gtm_stmlock GTM::gtm_stmlock_array[LOCK_ARRAY_SIZE];
40 atomic<gtm_version> GTM::gtm_clock;
42 /* ??? Move elsewhere when we figure out library initialization. */
43 uint64_t GTM::gtm_spin_count_var = 1000;
45 #ifdef HAVE_64BIT_SYNC_BUILTINS
46 static atomic<_ITM_transactionId_t> global_tid;
47 #else
48 static _ITM_transactionId_t global_tid;
49 static pthread_mutex_t global_tid_lock = PTHREAD_MUTEX_INITIALIZER;
50 #endif
53 // Provides a on-thread-exit callback used to release per-thread data.
54 static pthread_key_t thr_release_key;
55 static pthread_once_t thr_release_once = PTHREAD_ONCE_INIT;
57 // See gtm_thread::begin_transaction.
58 uint32_t GTM::htm_fastpath = 0;
60 /* Allocate a transaction structure. */
61 void *
62 GTM::gtm_thread::operator new (size_t s)
64 void *tx;
66 assert(s == sizeof(gtm_thread));
68 tx = xmalloc (sizeof (gtm_thread), true);
69 memset (tx, 0, sizeof (gtm_thread));
71 return tx;
74 /* Free the given transaction. Raises an error if the transaction is still
75 in use. */
76 void
77 GTM::gtm_thread::operator delete(void *tx)
79 free(tx);
82 static void
83 thread_exit_handler(void *)
85 gtm_thread *thr = gtm_thr();
86 if (thr)
87 delete thr;
88 set_gtm_thr(0);
91 static void
92 thread_exit_init()
94 if (pthread_key_create(&thr_release_key, thread_exit_handler))
95 GTM_fatal("Creating thread release TLS key failed.");
99 GTM::gtm_thread::~gtm_thread()
101 if (nesting > 0)
102 GTM_fatal("Thread exit while a transaction is still active.");
104 // Deregister this transaction.
105 serial_lock.write_lock ();
106 gtm_thread **prev = &list_of_threads;
107 for (; *prev; prev = &(*prev)->next_thread)
109 if (*prev == this)
111 *prev = (*prev)->next_thread;
112 break;
115 number_of_threads--;
116 number_of_threads_changed(number_of_threads + 1, number_of_threads);
117 serial_lock.write_unlock ();
120 GTM::gtm_thread::gtm_thread ()
122 // This object's memory has been set to zero by operator new, so no need
123 // to initialize any of the other primitive-type members that do not have
124 // constructors.
125 shared_state.store(-1, memory_order_relaxed);
127 // Register this transaction with the list of all threads' transactions.
128 serial_lock.write_lock ();
129 next_thread = list_of_threads;
130 list_of_threads = this;
131 number_of_threads++;
132 number_of_threads_changed(number_of_threads - 1, number_of_threads);
133 serial_lock.write_unlock ();
135 if (pthread_once(&thr_release_once, thread_exit_init))
136 GTM_fatal("Initializing thread release TLS key failed.");
137 // Any non-null value is sufficient to trigger destruction of this
138 // transaction when the current thread terminates.
139 if (pthread_setspecific(thr_release_key, this))
140 GTM_fatal("Setting thread release TLS key failed.");
143 static inline uint32_t
144 choose_code_path(uint32_t prop, abi_dispatch *disp)
146 if ((prop & pr_uninstrumentedCode) && disp->can_run_uninstrumented_code())
147 return a_runUninstrumentedCode;
148 else
149 return a_runInstrumentedCode;
152 uint32_t
153 GTM::gtm_thread::begin_transaction (uint32_t prop, const gtm_jmpbuf *jb)
155 static const _ITM_transactionId_t tid_block_size = 1 << 16;
157 gtm_thread *tx;
158 abi_dispatch *disp;
159 uint32_t ret;
161 // ??? pr_undoLogCode is not properly defined in the ABI. Are barriers
162 // omitted because they are not necessary (e.g., a transaction on thread-
163 // local data) or because the compiler thinks that some kind of global
164 // synchronization might perform better?
165 if (unlikely(prop & pr_undoLogCode))
166 GTM_fatal("pr_undoLogCode not supported");
168 #ifdef USE_HTM_FASTPATH
169 // HTM fastpath. Only chosen in the absence of transaction_cancel to allow
170 // using an uninstrumented code path.
171 // The fastpath is enabled only by dispatch_htm's method group, which uses
172 // serial-mode methods as fallback. Serial-mode transactions cannot execute
173 // concurrently with HW transactions because the latter monitor the serial
174 // lock's writer flag and thus abort if another thread is or becomes a
175 // serial transaction. Therefore, if the fastpath is enabled, then a
176 // transaction is not executing as a HW transaction iff the serial lock is
177 // write-locked. This allows us to use htm_fastpath and the serial lock's
178 // writer flag to reliable determine whether the current thread runs a HW
179 // transaction, and thus we do not need to maintain this information in
180 // per-thread state.
181 // If an uninstrumented code path is not available, we can still run
182 // instrumented code from a HW transaction because the HTM fastpath kicks
183 // in early in both begin and commit, and the transaction is not canceled.
184 // HW transactions might get requests to switch to serial-irrevocable mode,
185 // but these can be ignored because the HTM provides all necessary
186 // correctness guarantees. Transactions cannot detect whether they are
187 // indeed in serial mode, and HW transactions should never need serial mode
188 // for any internal changes (e.g., they never abort visibly to the STM code
189 // and thus do not trigger the standard retry handling).
190 #ifndef HTM_CUSTOM_FASTPATH
191 if (likely(htm_fastpath && (prop & pr_hasNoAbort)))
193 for (uint32_t t = htm_fastpath; t; t--)
195 uint32_t ret = htm_begin();
196 if (htm_begin_success(ret))
198 // We are executing a transaction now.
199 // Monitor the writer flag in the serial-mode lock, and abort
200 // if there is an active or waiting serial-mode transaction.
201 // Note that this can also happen due to an enclosing
202 // serial-mode transaction; we handle this case below.
203 if (unlikely(serial_lock.is_write_locked()))
204 htm_abort();
205 else
206 // We do not need to set a_saveLiveVariables because of HTM.
207 return (prop & pr_uninstrumentedCode) ?
208 a_runUninstrumentedCode : a_runInstrumentedCode;
210 // The transaction has aborted. Don't retry if it's unlikely that
211 // retrying the transaction will be successful.
212 if (!htm_abort_should_retry(ret))
213 break;
214 // Wait until any concurrent serial-mode transactions have finished.
215 // This is an empty critical section, but won't be elided.
216 if (serial_lock.is_write_locked())
218 tx = gtm_thr();
219 if (unlikely(tx == NULL))
221 // See below.
222 tx = new gtm_thread();
223 set_gtm_thr(tx);
225 // Check whether there is an enclosing serial-mode transaction;
226 // if so, we just continue as a nested transaction and don't
227 // try to use the HTM fastpath. This case can happen when an
228 // outermost relaxed transaction calls unsafe code that starts
229 // a transaction.
230 if (tx->nesting > 0)
231 break;
232 // Another thread is running a serial-mode transaction. Wait.
233 serial_lock.read_lock(tx);
234 serial_lock.read_unlock(tx);
235 // TODO We should probably reset the retry count t here, unless
236 // we have retried so often that we should go serial to avoid
237 // starvation.
241 #else
242 // If we have a custom HTM fastpath in ITM_beginTransaction, we implement
243 // just the retry policy here. We communicate with the custom fastpath
244 // through additional property bits and return codes, and either transfer
245 // control back to the custom fastpath or run the fallback mechanism. The
246 // fastpath synchronization algorithm itself is the same.
247 // pr_HTMRetryableAbort states that a HW transaction started by the custom
248 // HTM fastpath aborted, and that we thus have to decide whether to retry
249 // the fastpath (returning a_tryHTMFastPath) or just proceed with the
250 // fallback method.
251 if (likely(htm_fastpath && (prop & pr_HTMRetryableAbort)))
253 tx = gtm_thr();
254 if (unlikely(tx == NULL))
256 // See below.
257 tx = new gtm_thread();
258 set_gtm_thr(tx);
260 // If this is the first abort, reset the retry count. We abuse
261 // restart_total for the retry count, which is fine because our only
262 // other fallback will use serial transactions, which don't use
263 // restart_total but will reset it when committing.
264 if (!(prop & pr_HTMRetriedAfterAbort))
265 tx->restart_total = htm_fastpath;
267 if (--tx->restart_total > 0)
269 // Wait until any concurrent serial-mode transactions have finished.
270 // Essentially the same code as above.
271 if (serial_lock.is_write_locked())
273 if (tx->nesting > 0)
274 goto stop_custom_htm_fastpath;
275 serial_lock.read_lock(tx);
276 serial_lock.read_unlock(tx);
278 // Let ITM_beginTransaction retry the custom HTM fastpath.
279 return a_tryHTMFastPath;
282 stop_custom_htm_fastpath:
283 #endif
284 #endif
286 tx = gtm_thr();
287 if (unlikely(tx == NULL))
289 // Create the thread object. The constructor will also set up automatic
290 // deletion on thread termination.
291 tx = new gtm_thread();
292 set_gtm_thr(tx);
295 if (tx->nesting > 0)
297 // This is a nested transaction.
298 // Check prop compatibility:
299 // The ABI requires pr_hasNoFloatUpdate, pr_hasNoVectorUpdate,
300 // pr_hasNoIrrevocable, pr_aWBarriersOmitted, pr_RaRBarriersOmitted, and
301 // pr_hasNoSimpleReads to hold for the full dynamic scope of a
302 // transaction. We could check that these are set for the nested
303 // transaction if they are also set for the parent transaction, but the
304 // ABI does not require these flags to be set if they could be set,
305 // so the check could be too strict.
306 // ??? For pr_readOnly, lexical or dynamic scope is unspecified.
308 if (prop & pr_hasNoAbort)
310 // We can use flat nesting, so elide this transaction.
311 if (!(prop & pr_instrumentedCode))
313 if (!(tx->state & STATE_SERIAL) ||
314 !(tx->state & STATE_IRREVOCABLE))
315 tx->serialirr_mode();
317 // Increment nesting level after checking that we have a method that
318 // allows us to continue.
319 tx->nesting++;
320 return choose_code_path(prop, abi_disp());
323 // The transaction might abort, so use closed nesting if possible.
324 // pr_hasNoAbort has lexical scope, so the compiler should really have
325 // generated an instrumented code path.
326 assert(prop & pr_instrumentedCode);
328 // Create a checkpoint of the current transaction.
329 gtm_transaction_cp *cp = tx->parent_txns.push();
330 cp->save(tx);
331 new (&tx->alloc_actions) aa_tree<uintptr_t, gtm_alloc_action>();
333 // Check whether the current method actually supports closed nesting.
334 // If we can switch to another one, do so.
335 // If not, we assume that actual aborts are infrequent, and rather
336 // restart in _ITM_abortTransaction when we really have to.
337 disp = abi_disp();
338 if (!disp->closed_nesting())
340 // ??? Should we elide the transaction if there is no alternative
341 // method that supports closed nesting? If we do, we need to set
342 // some flag to prevent _ITM_abortTransaction from aborting the
343 // wrong transaction (i.e., some parent transaction).
344 abi_dispatch *cn_disp = disp->closed_nesting_alternative();
345 if (cn_disp)
347 disp = cn_disp;
348 set_abi_disp(disp);
352 else
354 // Outermost transaction
355 disp = tx->decide_begin_dispatch (prop);
356 set_abi_disp (disp);
359 // Initialization that is common for outermost and nested transactions.
360 tx->prop = prop;
361 tx->nesting++;
363 tx->jb = *jb;
365 // As long as we have not exhausted a previously allocated block of TIDs,
366 // we can avoid an atomic operation on a shared cacheline.
367 if (tx->local_tid & (tid_block_size - 1))
368 tx->id = tx->local_tid++;
369 else
371 #ifdef HAVE_64BIT_SYNC_BUILTINS
372 // We don't really care which block of TIDs we get but only that we
373 // acquire one atomically; therefore, relaxed memory order is
374 // sufficient.
375 tx->id = global_tid.fetch_add(tid_block_size, memory_order_relaxed);
376 tx->local_tid = tx->id + 1;
377 #else
378 pthread_mutex_lock (&global_tid_lock);
379 global_tid += tid_block_size;
380 tx->id = global_tid;
381 tx->local_tid = tx->id + 1;
382 pthread_mutex_unlock (&global_tid_lock);
383 #endif
386 // Run dispatch-specific restart code. Retry until we succeed.
387 GTM::gtm_restart_reason rr;
388 while ((rr = disp->begin_or_restart()) != NO_RESTART)
390 tx->decide_retry_strategy(rr);
391 disp = abi_disp();
394 // Determine the code path to run. Only irrevocable transactions cannot be
395 // restarted, so all other transactions need to save live variables.
396 ret = choose_code_path(prop, disp);
397 if (!(tx->state & STATE_IRREVOCABLE))
398 ret |= a_saveLiveVariables;
399 return ret;
403 void
404 GTM::gtm_transaction_cp::save(gtm_thread* tx)
406 // Save everything that we might have to restore on restarts or aborts.
407 jb = tx->jb;
408 undolog_size = tx->undolog.size();
409 memcpy(&alloc_actions, &tx->alloc_actions, sizeof(alloc_actions));
410 user_actions_size = tx->user_actions.size();
411 id = tx->id;
412 prop = tx->prop;
413 cxa_catch_count = tx->cxa_catch_count;
414 cxa_unthrown = tx->cxa_unthrown;
415 disp = abi_disp();
416 nesting = tx->nesting;
419 void
420 GTM::gtm_transaction_cp::commit(gtm_thread* tx)
422 // Restore state that is not persistent across commits. Exception handling,
423 // information, nesting level, and any logs do not need to be restored on
424 // commits of nested transactions. Allocation actions must be committed
425 // before committing the snapshot.
426 tx->jb = jb;
427 memcpy(&tx->alloc_actions, &alloc_actions, sizeof(alloc_actions));
428 tx->id = id;
429 tx->prop = prop;
433 void
434 GTM::gtm_thread::rollback (gtm_transaction_cp *cp, bool aborting)
436 // The undo log is special in that it used for both thread-local and shared
437 // data. Because of the latter, we have to roll it back before any
438 // dispatch-specific rollback (which handles synchronization with other
439 // transactions).
440 undolog.rollback (this, cp ? cp->undolog_size : 0);
442 // Perform dispatch-specific rollback.
443 abi_disp()->rollback (cp);
445 // Roll back all actions that are supposed to happen around the transaction.
446 rollback_user_actions (cp ? cp->user_actions_size : 0);
447 commit_allocations (true, (cp ? &cp->alloc_actions : 0));
448 revert_cpp_exceptions (cp);
450 if (cp)
452 // We do not yet handle restarts of nested transactions. To do that, we
453 // would have to restore some state (jb, id, prop, nesting) not to the
454 // checkpoint but to the transaction that was started from this
455 // checkpoint (e.g., nesting = cp->nesting + 1);
456 assert(aborting);
457 // Roll back the rest of the state to the checkpoint.
458 jb = cp->jb;
459 id = cp->id;
460 prop = cp->prop;
461 if (cp->disp != abi_disp())
462 set_abi_disp(cp->disp);
463 memcpy(&alloc_actions, &cp->alloc_actions, sizeof(alloc_actions));
464 nesting = cp->nesting;
466 else
468 // Roll back to the outermost transaction.
469 // Restore the jump buffer and transaction properties, which we will
470 // need for the longjmp used to restart or abort the transaction.
471 if (parent_txns.size() > 0)
473 jb = parent_txns[0].jb;
474 id = parent_txns[0].id;
475 prop = parent_txns[0].prop;
477 // Reset the transaction. Do not reset this->state, which is handled by
478 // the callers. Note that if we are not aborting, we reset the
479 // transaction to the point after having executed begin_transaction
480 // (we will return from it), so the nesting level must be one, not zero.
481 nesting = (aborting ? 0 : 1);
482 parent_txns.clear();
485 if (this->eh_in_flight)
487 _Unwind_DeleteException ((_Unwind_Exception *) this->eh_in_flight);
488 this->eh_in_flight = NULL;
492 void ITM_REGPARM
493 _ITM_abortTransaction (_ITM_abortReason reason)
495 gtm_thread *tx = gtm_thr();
497 assert (reason == userAbort || reason == (userAbort | outerAbort));
498 assert ((tx->prop & pr_hasNoAbort) == 0);
500 if (tx->state & gtm_thread::STATE_IRREVOCABLE)
501 abort ();
503 // Roll back to innermost transaction.
504 if (tx->parent_txns.size() > 0 && !(reason & outerAbort))
506 // If the current method does not support closed nesting but we are
507 // nested and must only roll back the innermost transaction, then
508 // restart with a method that supports closed nesting.
509 abi_dispatch *disp = abi_disp();
510 if (!disp->closed_nesting())
511 tx->restart(RESTART_CLOSED_NESTING);
513 // The innermost transaction is a closed nested transaction.
514 gtm_transaction_cp *cp = tx->parent_txns.pop();
515 uint32_t longjmp_prop = tx->prop;
516 gtm_jmpbuf longjmp_jb = tx->jb;
518 tx->rollback (cp, true);
520 // Jump to nested transaction (use the saved jump buffer).
521 GTM_longjmp (a_abortTransaction | a_restoreLiveVariables,
522 &longjmp_jb, longjmp_prop);
524 else
526 // There is no nested transaction or an abort of the outermost
527 // transaction was requested, so roll back to the outermost transaction.
528 tx->rollback (0, true);
530 // Aborting an outermost transaction finishes execution of the whole
531 // transaction. Therefore, reset transaction state.
532 if (tx->state & gtm_thread::STATE_SERIAL)
533 gtm_thread::serial_lock.write_unlock ();
534 else
535 gtm_thread::serial_lock.read_unlock (tx);
536 tx->state = 0;
538 GTM_longjmp (a_abortTransaction | a_restoreLiveVariables,
539 &tx->jb, tx->prop);
543 bool
544 GTM::gtm_thread::trycommit ()
546 nesting--;
548 // Skip any real commit for elided transactions.
549 if (nesting > 0 && (parent_txns.size() == 0 ||
550 nesting > parent_txns[parent_txns.size() - 1].nesting))
551 return true;
553 if (nesting > 0)
555 // Commit of a closed-nested transaction. Remove one checkpoint and add
556 // any effects of this transaction to the parent transaction.
557 gtm_transaction_cp *cp = parent_txns.pop();
558 commit_allocations(false, &cp->alloc_actions);
559 cp->commit(this);
560 return true;
563 // Commit of an outermost transaction.
564 gtm_word priv_time = 0;
565 if (abi_disp()->trycommit (priv_time))
567 // The transaction is now inactive. Everything that we still have to do
568 // will not synchronize with other transactions anymore.
569 if (state & gtm_thread::STATE_SERIAL)
571 gtm_thread::serial_lock.write_unlock ();
572 // There are no other active transactions, so there's no need to
573 // enforce privatization safety.
574 priv_time = 0;
576 else
577 gtm_thread::serial_lock.read_unlock (this);
578 state = 0;
580 // We can commit the undo log after dispatch-specific commit and after
581 // making the transaction inactive because we only have to reset
582 // gtm_thread state.
583 undolog.commit ();
584 // Reset further transaction state.
585 cxa_catch_count = 0;
586 cxa_unthrown = NULL;
587 restart_total = 0;
589 // Ensure privatization safety, if necessary.
590 if (priv_time)
592 // There must be a seq_cst fence between the following loads of the
593 // other transactions' shared_state and the dispatch-specific stores
594 // that signal updates by this transaction (e.g., lock
595 // acquisitions). This ensures that if we read prior to other
596 // reader transactions setting their shared_state to 0, then those
597 // readers will observe our updates. We can reuse the seq_cst fence
598 // in serial_lock.read_unlock() however, so we don't need another
599 // one here.
600 // TODO Don't just spin but also block using cond vars / futexes
601 // here. Should probably be integrated with the serial lock code.
602 for (gtm_thread *it = gtm_thread::list_of_threads; it != 0;
603 it = it->next_thread)
605 if (it == this) continue;
606 // We need to load other threads' shared_state using acquire
607 // semantics (matching the release semantics of the respective
608 // updates). This is necessary to ensure that the other
609 // threads' memory accesses happen before our actions that
610 // assume privatization safety.
611 // TODO Are there any platform-specific optimizations (e.g.,
612 // merging barriers)?
613 while (it->shared_state.load(memory_order_acquire) < priv_time)
614 cpu_relax();
618 // After ensuring privatization safety, we execute potentially
619 // privatizing actions (e.g., calling free()). User actions are first.
620 commit_user_actions ();
621 commit_allocations (false, 0);
623 return true;
625 return false;
628 void ITM_NORETURN
629 GTM::gtm_thread::restart (gtm_restart_reason r, bool finish_serial_upgrade)
631 // Roll back to outermost transaction. Do not reset transaction state because
632 // we will continue executing this transaction.
633 rollback ();
635 // If we have to restart while an upgrade of the serial lock is happening,
636 // we need to finish this here, after rollback (to ensure privatization
637 // safety despite undo writes) and before deciding about the retry strategy
638 // (which could switch to/from serial mode).
639 if (finish_serial_upgrade)
640 gtm_thread::serial_lock.write_upgrade_finish(this);
642 decide_retry_strategy (r);
644 // Run dispatch-specific restart code. Retry until we succeed.
645 abi_dispatch* disp = abi_disp();
646 GTM::gtm_restart_reason rr;
647 while ((rr = disp->begin_or_restart()) != NO_RESTART)
649 decide_retry_strategy(rr);
650 disp = abi_disp();
653 GTM_longjmp (choose_code_path(prop, disp) | a_restoreLiveVariables,
654 &jb, prop);
657 void ITM_REGPARM
658 _ITM_commitTransaction(void)
660 #if defined(USE_HTM_FASTPATH)
661 // HTM fastpath. If we are not executing a HW transaction, then we will be
662 // a serial-mode transaction. If we are, then there will be no other
663 // concurrent serial-mode transaction.
664 // See gtm_thread::begin_transaction.
665 if (likely(htm_fastpath && !gtm_thread::serial_lock.is_write_locked()))
667 htm_commit();
668 return;
670 #endif
671 gtm_thread *tx = gtm_thr();
672 if (!tx->trycommit ())
673 tx->restart (RESTART_VALIDATE_COMMIT);
676 void ITM_REGPARM
677 _ITM_commitTransactionEH(void *exc_ptr)
679 #if defined(USE_HTM_FASTPATH)
680 // See _ITM_commitTransaction.
681 if (likely(htm_fastpath && !gtm_thread::serial_lock.is_write_locked()))
683 htm_commit();
684 return;
686 #endif
687 gtm_thread *tx = gtm_thr();
688 if (!tx->trycommit ())
690 tx->eh_in_flight = exc_ptr;
691 tx->restart (RESTART_VALIDATE_COMMIT);