libitm/beginend.cc

   1 /* Copyright (C) 2008, 2009, 2011 Free Software Foundation, Inc.
   2    Contributed by Richard Henderson <rth@redhat.com>.
   3
   4    This file is part of the GNU Transactional Memory Library (libitm).
   5
   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.
  10
  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.
  15
  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.
  19
  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/>.  */
  24
  25 #include "libitm_i.h"
  26 #include <pthread.h>
  27
  28
  29 using namespace GTM;
  30
  31 #if !defined(HAVE_ARCH_GTM_THREAD) || !defined(HAVE_ARCH_GTM_THREAD_DISP)
  32 extern __thread gtm_thread_tls _gtm_thr_tls;
  33 #endif
  34
  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;
  38
  39 gtm_stmlock GTM::gtm_stmlock_array[LOCK_ARRAY_SIZE];
  40 gtm_version GTM::gtm_clock;
  41
  42 /* ??? Move elsewhere when we figure out library initialization.  */
  43 uint64_t GTM::gtm_spin_count_var = 1000;
  44
  45 static _ITM_transactionId_t global_tid;
  46
  47 // Provides a on-thread-exit callback used to release per-thread data.
  48 static pthread_key_t thr_release_key;
  49 static pthread_once_t thr_release_once = PTHREAD_ONCE_INIT;
  50
  51
  52 /* Allocate a transaction structure.  */
  53 void *
  54 GTM::gtm_thread::operator new (size_t s)
  55 {
  56   void *tx;
  57
  58   assert(s == sizeof(gtm_thread));
  59
  60   tx = xmalloc (sizeof (gtm_thread), true);
  61   memset (tx, 0, sizeof (gtm_thread));
  62
  63   return tx;
  64 }
  65
  66 /* Free the given transaction. Raises an error if the transaction is still
  67    in use.  */
  68 void
  69 GTM::gtm_thread::operator delete(void *tx)
  70 {
  71   free(tx);
  72 }
  73
  74 static void
  75 thread_exit_handler(void *)
  76 {
  77   gtm_thread *thr = gtm_thr();
  78   if (thr)
  79     delete thr;
  80   set_gtm_thr(0);
  81 }
  82
  83 static void
  84 thread_exit_init()
  85 {
  86   if (pthread_key_create(&thr_release_key, thread_exit_handler))
  87     GTM_fatal("Creating thread release TLS key failed.");
  88 }
  89
  90
  91 GTM::gtm_thread::~gtm_thread()
  92 {
  93   if (nesting > 0)
  94     GTM_fatal("Thread exit while a transaction is still active.");
  95
  96   // Deregister this transaction.
  97   serial_lock.write_lock ();
  98   gtm_thread **prev = &list_of_threads;
  99   for (; *prev; prev = &(*prev)->next_thread)
 100     {
 101       if (*prev == this)
 102         {
 103           *prev = (*prev)->next_thread;
 104           break;
 105         }
 106     }
 107   number_of_threads--;
 108   number_of_threads_changed(number_of_threads + 1, number_of_threads);
 109   serial_lock.write_unlock ();
 110 }
 111
 112 GTM::gtm_thread::gtm_thread ()
 113 {
 114   // This object's memory has been set to zero by operator new, so no need
 115   // to initialize any of the other primitive-type members that do not have
 116   // constructors.
 117   shared_state = ~(typeof shared_state)0;
 118
 119   // Register this transaction with the list of all threads' transactions.
 120   serial_lock.write_lock ();
 121   next_thread = list_of_threads;
 122   list_of_threads = this;
 123   number_of_threads++;
 124   number_of_threads_changed(number_of_threads - 1, number_of_threads);
 125   serial_lock.write_unlock ();
 126
 127   if (pthread_once(&thr_release_once, thread_exit_init))
 128     GTM_fatal("Initializing thread release TLS key failed.");
 129   // Any non-null value is sufficient to trigger destruction of this
 130   // transaction when the current thread terminates.
 131   if (pthread_setspecific(thr_release_key, this))
 132     GTM_fatal("Setting thread release TLS key failed.");
 133 }
 134
 135
 136
 137 #ifndef HAVE_64BIT_SYNC_BUILTINS
 138 static pthread_mutex_t global_tid_lock = PTHREAD_MUTEX_INITIALIZER;
 139 #endif
 140
 141 static inline uint32_t choose_code_path(uint32_t prop, abi_dispatch *disp)
 142 {
 143   if ((prop & pr_uninstrumentedCode) && disp->can_run_uninstrumented_code())
 144     return a_runUninstrumentedCode;
 145   else
 146     return a_runInstrumentedCode;
 147 }
 148
 149 uint32_t
 150 GTM::gtm_thread::begin_transaction (uint32_t prop, const gtm_jmpbuf *jb)
 151 {
 152   static const _ITM_transactionId_t tid_block_size = 1 << 16;
 153
 154   gtm_thread *tx;
 155   abi_dispatch *disp;
 156   uint32_t ret;
 157
 158   // ??? pr_undoLogCode is not properly defined in the ABI. Are barriers
 159   // omitted because they are not necessary (e.g., a transaction on thread-
 160   // local data) or because the compiler thinks that some kind of global
 161   // synchronization might perform better?
 162   if (unlikely(prop & pr_undoLogCode))
 163     GTM_fatal("pr_undoLogCode not supported");
 164
 165   tx = gtm_thr();
 166   if (unlikely(tx == NULL))
 167     {
 168       // Create the thread object. The constructor will also set up automatic
 169       // deletion on thread termination.
 170       tx = new gtm_thread();
 171       set_gtm_thr(tx);
 172     }
 173
 174   if (tx->nesting > 0)
 175     {
 176       // This is a nested transaction.
 177       // Check prop compatibility:
 178       // The ABI requires pr_hasNoFloatUpdate, pr_hasNoVectorUpdate,
 179       // pr_hasNoIrrevocable, pr_aWBarriersOmitted, pr_RaRBarriersOmitted, and
 180       // pr_hasNoSimpleReads to hold for the full dynamic scope of a
 181       // transaction. We could check that these are set for the nested
 182       // transaction if they are also set for the parent transaction, but the
 183       // ABI does not require these flags to be set if they could be set,
 184       // so the check could be too strict.
 185       // ??? For pr_readOnly, lexical or dynamic scope is unspecified.
 186
 187       if (prop & pr_hasNoAbort)
 188         {
 189           // We can use flat nesting, so elide this transaction.
 190           if (!(prop & pr_instrumentedCode))
 191             {
 192               if (!(tx->state & STATE_SERIAL) ||
 193                   !(tx->state & STATE_IRREVOCABLE))
 194                 tx->serialirr_mode();
 195             }
 196           // Increment nesting level after checking that we have a method that
 197           // allows us to continue.
 198           tx->nesting++;
 199           return choose_code_path(prop, abi_disp());
 200         }
 201
 202       // The transaction might abort, so use closed nesting if possible.
 203       // pr_hasNoAbort has lexical scope, so the compiler should really have
 204       // generated an instrumented code path.
 205       assert(prop & pr_instrumentedCode);
 206
 207       // Create a checkpoint of the current transaction.
 208       gtm_transaction_cp *cp = tx->parent_txns.push();
 209       cp->save(tx);
 210       new (&tx->alloc_actions) aa_tree<uintptr_t, gtm_alloc_action>();
 211
 212       // Check whether the current method actually supports closed nesting.
 213       // If we can switch to another one, do so.
 214       // If not, we assume that actual aborts are infrequent, and rather
 215       // restart in _ITM_abortTransaction when we really have to.
 216       disp = abi_disp();
 217       if (!disp->closed_nesting())
 218         {
 219           // ??? Should we elide the transaction if there is no alternative
 220           // method that supports closed nesting? If we do, we need to set
 221           // some flag to prevent _ITM_abortTransaction from aborting the
 222           // wrong transaction (i.e., some parent transaction).
 223           abi_dispatch *cn_disp = disp->closed_nesting_alternative();
 224           if (cn_disp)
 225             {
 226               disp = cn_disp;
 227               set_abi_disp(disp);
 228             }
 229         }
 230     }
 231   else
 232     {
 233       // Outermost transaction
 234       disp = tx->decide_begin_dispatch (prop);
 235       if (disp == dispatch_serialirr() || disp == dispatch_serial())
 236         {
 237           tx->state = STATE_SERIAL;
 238           if (disp == dispatch_serialirr())
 239             tx->state |= STATE_IRREVOCABLE;
 240           serial_lock.write_lock ();
 241         }
 242       else
 243         serial_lock.read_lock (tx);
 244
 245       set_abi_disp (disp);
 246     }
 247
 248   // Initialization that is common for outermost and nested transactions.
 249   tx->prop = prop;
 250   tx->nesting++;
 251
 252   tx->jb = *jb;
 253
 254   // As long as we have not exhausted a previously allocated block of TIDs,
 255   // we can avoid an atomic operation on a shared cacheline.
 256   if (tx->local_tid & (tid_block_size - 1))
 257     tx->id = tx->local_tid++;
 258   else
 259     {
 260 #ifdef HAVE_64BIT_SYNC_BUILTINS
 261       tx->id = __sync_add_and_fetch (&global_tid, tid_block_size);
 262       tx->local_tid = tx->id + 1;
 263 #else
 264       pthread_mutex_lock (&global_tid_lock);
 265       global_tid += tid_block_size;
 266       tx->id = global_tid;
 267       tx->local_tid = tx->id + 1;
 268       pthread_mutex_unlock (&global_tid_lock);
 269 #endif
 270     }
 271
 272   // Run dispatch-specific restart code. Retry until we succeed.
 273   GTM::gtm_restart_reason rr;
 274   while ((rr = disp->begin_or_restart()) != NO_RESTART)
 275     {
 276       tx->decide_retry_strategy(rr);
 277       disp = abi_disp();
 278     }
 279
 280   // Determine the code path to run. Only irrevocable transactions cannot be
 281   // restarted, so all other transactions need to save live variables.
 282   ret = choose_code_path(prop, disp);
 283   if (!(tx->state & STATE_IRREVOCABLE))
 284     ret |= a_saveLiveVariables;
 285   return ret;
 286 }
 287
 288
 289 void
 290 GTM::gtm_transaction_cp::save(gtm_thread* tx)
 291 {
 292   // Save everything that we might have to restore on restarts or aborts.
 293   jb = tx->jb;
 294   undolog_size = tx->undolog.size();
 295   memcpy(&alloc_actions, &tx->alloc_actions, sizeof(alloc_actions));
 296   user_actions_size = tx->user_actions.size();
 297   id = tx->id;
 298   prop = tx->prop;
 299   cxa_catch_count = tx->cxa_catch_count;
 300   cxa_unthrown = tx->cxa_unthrown;
 301   disp = abi_disp();
 302   nesting = tx->nesting;
 303 }
 304
 305 void
 306 GTM::gtm_transaction_cp::commit(gtm_thread* tx)
 307 {
 308   // Restore state that is not persistent across commits. Exception handling,
 309   // information, nesting level, and any logs do not need to be restored on
 310   // commits of nested transactions. Allocation actions must be committed
 311   // before committing the snapshot.
 312   tx->jb = jb;
 313   memcpy(&tx->alloc_actions, &alloc_actions, sizeof(alloc_actions));
 314   tx->id = id;
 315   tx->prop = prop;
 316 }
 317
 318
 319 void
 320 GTM::gtm_thread::rollback (gtm_transaction_cp *cp, bool aborting)
 321 {
 322   // The undo log is special in that it used for both thread-local and shared
 323   // data. Because of the latter, we have to roll it back before any
 324   // dispatch-specific rollback (which handles synchronization with other
 325   // transactions).
 326   rollback_undolog (cp ? cp->undolog_size : 0);
 327
 328   // Perform dispatch-specific rollback.
 329   abi_disp()->rollback (cp);
 330
 331   // Roll back all actions that are supposed to happen around the transaction.
 332   rollback_user_actions (cp ? cp->user_actions_size : 0);
 333   commit_allocations (true, (cp ? &cp->alloc_actions : 0));
 334   revert_cpp_exceptions (cp);
 335
 336   if (cp)
 337     {
 338       // We do not yet handle restarts of nested transactions. To do that, we
 339       // would have to restore some state (jb, id, prop, nesting) not to the
 340       // checkpoint but to the transaction that was started from this
 341       // checkpoint (e.g., nesting = cp->nesting + 1);
 342       assert(aborting);
 343       // Roll back the rest of the state to the checkpoint.
 344       jb = cp->jb;
 345       id = cp->id;
 346       prop = cp->prop;
 347       if (cp->disp != abi_disp())
 348         set_abi_disp(cp->disp);
 349       memcpy(&alloc_actions, &cp->alloc_actions, sizeof(alloc_actions));
 350       nesting = cp->nesting;
 351     }
 352   else
 353     {
 354       // Roll back to the outermost transaction.
 355       // Restore the jump buffer and transaction properties, which we will
 356       // need for the longjmp used to restart or abort the transaction.
 357       if (parent_txns.size() > 0)
 358         {
 359           jb = parent_txns[0].jb;
 360           id = parent_txns[0].id;
 361           prop = parent_txns[0].prop;
 362         }
 363       // Reset the transaction. Do not reset this->state, which is handled by
 364       // the callers. Note that if we are not aborting, we reset the
 365       // transaction to the point after having executed begin_transaction
 366       // (we will return from it), so the nesting level must be one, not zero.
 367       nesting = (aborting ? 0 : 1);
 368       parent_txns.clear();
 369     }
 370
 371   if (this->eh_in_flight)
 372     {
 373       _Unwind_DeleteException ((_Unwind_Exception *) this->eh_in_flight);
 374       this->eh_in_flight = NULL;
 375     }
 376 }
 377
 378 void ITM_REGPARM
 379 _ITM_abortTransaction (_ITM_abortReason reason)
 380 {
 381   gtm_thread *tx = gtm_thr();
 382
 383   assert (reason == userAbort || reason == (userAbort | outerAbort));
 384   assert ((tx->prop & pr_hasNoAbort) == 0);
 385
 386   if (tx->state & gtm_thread::STATE_IRREVOCABLE)
 387     abort ();
 388
 389   // Roll back to innermost transaction.
 390   if (tx->parent_txns.size() > 0 && !(reason & outerAbort))
 391     {
 392       // If the current method does not support closed nesting but we are
 393       // nested and must only roll back the innermost transaction, then
 394       // restart with a method that supports closed nesting.
 395       abi_dispatch *disp = abi_disp();
 396       if (!disp->closed_nesting())
 397         tx->restart(RESTART_CLOSED_NESTING);
 398
 399       // The innermost transaction is a closed nested transaction.
 400       gtm_transaction_cp *cp = tx->parent_txns.pop();
 401       uint32_t longjmp_prop = tx->prop;
 402       gtm_jmpbuf longjmp_jb = tx->jb;
 403
 404       tx->rollback (cp, true);
 405
 406       // Jump to nested transaction (use the saved jump buffer).
 407       GTM_longjmp (a_abortTransaction | a_restoreLiveVariables,
 408                    &longjmp_jb, longjmp_prop);
 409     }
 410   else
 411     {
 412       // There is no nested transaction or an abort of the outermost
 413       // transaction was requested, so roll back to the outermost transaction.
 414       tx->rollback (0, true);
 415
 416       // Aborting an outermost transaction finishes execution of the whole
 417       // transaction. Therefore, reset transaction state.
 418       if (tx->state & gtm_thread::STATE_SERIAL)
 419         gtm_thread::serial_lock.write_unlock ();
 420       else
 421         gtm_thread::serial_lock.read_unlock (tx);
 422       tx->state = 0;
 423
 424       GTM_longjmp (a_abortTransaction | a_restoreLiveVariables,
 425                    &tx->jb, tx->prop);
 426     }
 427 }
 428
 429 bool
 430 GTM::gtm_thread::trycommit ()
 431 {
 432   nesting--;
 433
 434   // Skip any real commit for elided transactions.
 435   if (nesting > 0 && (parent_txns.size() == 0 ||
 436       nesting > parent_txns[parent_txns.size() - 1].nesting))
 437     return true;
 438
 439   if (nesting > 0)
 440     {
 441       // Commit of a closed-nested transaction. Remove one checkpoint and add
 442       // any effects of this transaction to the parent transaction.
 443       gtm_transaction_cp *cp = parent_txns.pop();
 444       commit_allocations(false, &cp->alloc_actions);
 445       cp->commit(this);
 446       return true;
 447     }
 448
 449   // Commit of an outermost transaction.
 450   gtm_word priv_time = 0;
 451   if (abi_disp()->trycommit (priv_time))
 452     {
 453       // The transaction is now inactive. Everything that we still have to do
 454       // will not synchronize with other transactions anymore.
 455       if (state & gtm_thread::STATE_SERIAL)
 456         gtm_thread::serial_lock.write_unlock ();
 457       else
 458         gtm_thread::serial_lock.read_unlock (this);
 459       state = 0;
 460
 461       // We can commit the undo log after dispatch-specific commit and after
 462       // making the transaction inactive because we only have to reset
 463       // gtm_thread state.
 464       commit_undolog ();
 465       // Reset further transaction state.
 466       cxa_catch_count = 0;
 467       cxa_unthrown = NULL;
 468       restart_total = 0;
 469
 470       // Ensure privatization safety, if necessary.
 471       if (priv_time)
 472         {
 473           // TODO Don't just spin but also block using cond vars / futexes
 474           // here. Should probably be integrated with the serial lock code.
 475           // TODO For C++0x atomics, the loads of other threads' shared_state
 476           // should have acquire semantics (together with releases for the
 477           // respective updates). But is this unnecessary overhead because
 478           // weaker barriers are sufficient?
 479           for (gtm_thread *it = gtm_thread::list_of_threads; it != 0;
 480               it = it->next_thread)
 481             {
 482               if (it == this) continue;
 483               while (it->shared_state < priv_time)
 484                 cpu_relax();
 485             }
 486         }
 487
 488       // After ensuring privatization safety, we execute potentially
 489       // privatizing actions (e.g., calling free()). User actions are first.
 490       commit_user_actions ();
 491       commit_allocations (false, 0);
 492
 493       return true;
 494     }
 495   return false;
 496 }
 497
 498 void ITM_NORETURN
 499 GTM::gtm_thread::restart (gtm_restart_reason r)
 500 {
 501   // Roll back to outermost transaction. Do not reset transaction state because
 502   // we will continue executing this transaction.
 503   rollback ();
 504   decide_retry_strategy (r);
 505
 506   // Run dispatch-specific restart code. Retry until we succeed.
 507   abi_dispatch* disp = abi_disp();
 508   GTM::gtm_restart_reason rr;
 509   while ((rr = disp->begin_or_restart()) != NO_RESTART)
 510     {
 511       decide_retry_strategy(rr);
 512       disp = abi_disp();
 513     }
 514
 515   GTM_longjmp (choose_code_path(prop, disp) | a_restoreLiveVariables,
 516                &jb, prop);
 517 }
 518
 519 void ITM_REGPARM
 520 _ITM_commitTransaction(void)
 521 {
 522   gtm_thread *tx = gtm_thr();
 523   if (!tx->trycommit ())
 524     tx->restart (RESTART_VALIDATE_COMMIT);
 525 }
 526
 527 void ITM_REGPARM
 528 _ITM_commitTransactionEH(void *exc_ptr)
 529 {
 530   gtm_thread *tx = gtm_thr();
 531   if (!tx->trycommit ())
 532     {
 533       tx->eh_in_flight = exc_ptr;
 534       tx->restart (RESTART_VALIDATE_COMMIT);
 535     }
 536 }