OSDN Git Service

Merge from transactional-memory branch.
[pf3gnuchains/gcc-fork.git] / 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 (&longjmp_jb, a_abortTransaction | a_restoreLiveVariables,
408           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 (&tx->jb, a_abortTransaction | a_restoreLiveVariables,
425           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 (&jb,
516       choose_code_path(prop, disp) | a_restoreLiveVariables, 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 }