gcc/
[official-gcc.git] / libitm / method-ml.cc
blob37cb08bbabfa2255b03019c24ca4d94869e921e7
1 /* Copyright (C) 2012-2015 Free Software Foundation, Inc.
2 Contributed by Torvald Riegel <triegel@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"
27 using namespace GTM;
29 namespace {
31 // This group consists of all TM methods that synchronize via multiple locks
32 // (or ownership records).
33 struct ml_mg : public method_group
35 static const gtm_word LOCK_BIT = (~(gtm_word)0 >> 1) + 1;
36 static const gtm_word INCARNATION_BITS = 3;
37 static const gtm_word INCARNATION_MASK = 7;
38 // Maximum time is all bits except the lock bit, the overflow reserve bit,
39 // and the incarnation bits).
40 static const gtm_word TIME_MAX = (~(gtm_word)0 >> (2 + INCARNATION_BITS));
41 // The overflow reserve bit is the MSB of the timestamp part of an orec,
42 // so we can have TIME_MAX+1 pending timestamp increases before we overflow.
43 static const gtm_word OVERFLOW_RESERVE = TIME_MAX + 1;
45 static bool is_locked(gtm_word o) { return o & LOCK_BIT; }
46 static gtm_word set_locked(gtm_thread *tx)
48 return ((uintptr_t)tx >> 1) | LOCK_BIT;
50 // Returns a time that includes the lock bit, which is required by both
51 // validate() and is_more_recent_or_locked().
52 static gtm_word get_time(gtm_word o) { return o >> INCARNATION_BITS; }
53 static gtm_word set_time(gtm_word time) { return time << INCARNATION_BITS; }
54 static bool is_more_recent_or_locked(gtm_word o, gtm_word than_time)
56 // LOCK_BIT is the MSB; thus, if O is locked, it is larger than TIME_MAX.
57 return get_time(o) > than_time;
59 static bool has_incarnation_left(gtm_word o)
61 return (o & INCARNATION_MASK) < INCARNATION_MASK;
63 static gtm_word inc_incarnation(gtm_word o) { return o + 1; }
65 // The shared time base.
66 atomic<gtm_word> time __attribute__((aligned(HW_CACHELINE_SIZE)));
68 // The array of ownership records.
69 atomic<gtm_word>* orecs __attribute__((aligned(HW_CACHELINE_SIZE)));
70 char tailpadding[HW_CACHELINE_SIZE - sizeof(atomic<gtm_word>*)];
72 // Location-to-orec mapping. Stripes of 16B mapped to 2^19 orecs.
73 static const gtm_word L2O_ORECS = 1 << 19;
74 static const gtm_word L2O_SHIFT = 4;
75 static size_t get_orec(const void* addr)
77 return ((uintptr_t)addr >> L2O_SHIFT) & (L2O_ORECS - 1);
79 static size_t get_next_orec(size_t orec)
81 return (orec + 1) & (L2O_ORECS - 1);
83 // Returns the next orec after the region.
84 static size_t get_orec_end(const void* addr, size_t len)
86 return (((uintptr_t)addr + len + (1 << L2O_SHIFT) - 1) >> L2O_SHIFT)
87 & (L2O_ORECS - 1);
90 virtual void init()
92 // We assume that an atomic<gtm_word> is backed by just a gtm_word, so
93 // starting with zeroed memory is fine.
94 orecs = (atomic<gtm_word>*) xcalloc(
95 sizeof(atomic<gtm_word>) * L2O_ORECS, true);
96 // This store is only executed while holding the serial lock, so relaxed
97 // memory order is sufficient here.
98 time.store(0, memory_order_relaxed);
101 virtual void fini()
103 free(orecs);
106 // We only re-initialize when our time base overflows. Thus, only reset
107 // the time base and the orecs but do not re-allocate the orec array.
108 virtual void reinit()
110 // This store is only executed while holding the serial lock, so relaxed
111 // memory order is sufficient here. Same holds for the memset.
112 time.store(0, memory_order_relaxed);
113 memset(orecs, 0, sizeof(atomic<gtm_word>) * L2O_ORECS);
117 static ml_mg o_ml_mg;
120 // The multiple lock, write-through TM method.
121 // Maps each memory location to one of the orecs in the orec array, and then
122 // acquires the associated orec eagerly before writing through.
123 // Writes require undo-logging because we are dealing with several locks/orecs
124 // and need to resolve deadlocks if necessary by aborting one of the
125 // transactions.
126 // Reads do time-based validation with snapshot time extensions. Incarnation
127 // numbers are used to decrease contention on the time base (with those,
128 // aborted transactions do not need to acquire a new version number for the
129 // data that has been previously written in the transaction and needs to be
130 // rolled back).
131 // gtm_thread::shared_state is used to store a transaction's current
132 // snapshot time (or commit time). The serial lock uses ~0 for inactive
133 // transactions and 0 for active ones. Thus, we always have a meaningful
134 // timestamp in shared_state that can be used to implement quiescence-based
135 // privatization safety.
136 class ml_wt_dispatch : public abi_dispatch
138 protected:
139 static void pre_write(gtm_thread *tx, const void *addr, size_t len)
141 gtm_word snapshot = tx->shared_state.load(memory_order_relaxed);
142 gtm_word locked_by_tx = ml_mg::set_locked(tx);
144 // Lock all orecs that cover the region.
145 size_t orec = ml_mg::get_orec(addr);
146 size_t orec_end = ml_mg::get_orec_end(addr, len);
149 // Load the orec. Relaxed memory order is sufficient here because
150 // either we have acquired the orec or we will try to acquire it with
151 // a CAS with stronger memory order.
152 gtm_word o = o_ml_mg.orecs[orec].load(memory_order_relaxed);
154 // Check whether we have acquired the orec already.
155 if (likely (locked_by_tx != o))
157 // If not, acquire. Make sure that our snapshot time is larger or
158 // equal than the orec's version to avoid masking invalidations of
159 // our snapshot with our own writes.
160 if (unlikely (ml_mg::is_locked(o)))
161 tx->restart(RESTART_LOCKED_WRITE);
163 if (unlikely (ml_mg::get_time(o) > snapshot))
165 // We only need to extend the snapshot if we have indeed read
166 // from this orec before. Given that we are an update
167 // transaction, we will have to extend anyway during commit.
168 // ??? Scan the read log instead, aborting if we have read
169 // from data covered by this orec before?
170 snapshot = extend(tx);
173 // We need acquire memory order here to synchronize with other
174 // (ownership) releases of the orec. We do not need acq_rel order
175 // because whenever another thread reads from this CAS'
176 // modification, then it will abort anyway and does not rely on
177 // any further happens-before relation to be established.
178 if (unlikely (!o_ml_mg.orecs[orec].compare_exchange_strong(
179 o, locked_by_tx, memory_order_acquire)))
180 tx->restart(RESTART_LOCKED_WRITE);
182 // We use an explicit fence here to avoid having to use release
183 // memory order for all subsequent data stores. This fence will
184 // synchronize with loads of the data with acquire memory order.
185 // See post_load() for why this is necessary.
186 // Adding require memory order to the prior CAS is not sufficient,
187 // at least according to the Batty et al. formalization of the
188 // memory model.
189 atomic_thread_fence(memory_order_release);
191 // We log the previous value here to be able to use incarnation
192 // numbers when we have to roll back.
193 // ??? Reserve capacity early to avoid capacity checks here?
194 gtm_rwlog_entry *e = tx->writelog.push();
195 e->orec = o_ml_mg.orecs + orec;
196 e->value = o;
198 orec = o_ml_mg.get_next_orec(orec);
200 while (orec != orec_end);
202 // Do undo logging. We do not know which region prior writes logged
203 // (even if orecs have been acquired), so just log everything.
204 tx->undolog.log(addr, len);
207 static void pre_write(const void *addr, size_t len)
209 gtm_thread *tx = gtm_thr();
210 pre_write(tx, addr, len);
213 // Returns true iff all the orecs in our read log still have the same time
214 // or have been locked by the transaction itself.
215 static bool validate(gtm_thread *tx)
217 gtm_word locked_by_tx = ml_mg::set_locked(tx);
218 // ??? This might get called from pre_load() via extend(). In that case,
219 // we don't really need to check the new entries that pre_load() is
220 // adding. Stop earlier?
221 for (gtm_rwlog_entry *i = tx->readlog.begin(), *ie = tx->readlog.end();
222 i != ie; i++)
224 // Relaxed memory order is sufficient here because we do not need to
225 // establish any new synchronizes-with relationships. We only need
226 // to read a value that is as least as current as enforced by the
227 // callers: extend() loads global time with acquire, and trycommit()
228 // increments global time with acquire. Therefore, we will see the
229 // most recent orec updates before the global time that we load.
230 gtm_word o = i->orec->load(memory_order_relaxed);
231 // We compare only the time stamp and the lock bit here. We know that
232 // we have read only committed data before, so we can ignore
233 // intermediate yet rolled-back updates presented by the incarnation
234 // number bits.
235 if (ml_mg::get_time(o) != ml_mg::get_time(i->value)
236 && o != locked_by_tx)
237 return false;
239 return true;
242 // Tries to extend the snapshot to a more recent time. Returns the new
243 // snapshot time and updates TX->SHARED_STATE. If the snapshot cannot be
244 // extended to the current global time, TX is restarted.
245 static gtm_word extend(gtm_thread *tx)
247 // We read global time here, even if this isn't strictly necessary
248 // because we could just return the maximum of the timestamps that
249 // validate sees. However, the potential cache miss on global time is
250 // probably a reasonable price to pay for avoiding unnecessary extensions
251 // in the future.
252 // We need acquire memory oder because we have to synchronize with the
253 // increment of global time by update transactions, whose lock
254 // acquisitions we have to observe (also see trycommit()).
255 gtm_word snapshot = o_ml_mg.time.load(memory_order_acquire);
256 if (!validate(tx))
257 tx->restart(RESTART_VALIDATE_READ);
259 // Update our public snapshot time. Probably useful to decrease waiting
260 // due to quiescence-based privatization safety.
261 // Use release memory order to establish synchronizes-with with the
262 // privatizers; prior data loads should happen before the privatizers
263 // potentially modify anything.
264 tx->shared_state.store(snapshot, memory_order_release);
265 return snapshot;
268 // First pass over orecs. Load and check all orecs that cover the region.
269 // Write to read log, extend snapshot time if necessary.
270 static gtm_rwlog_entry* pre_load(gtm_thread *tx, const void* addr,
271 size_t len)
273 // Don't obtain an iterator yet because the log might get resized.
274 size_t log_start = tx->readlog.size();
275 gtm_word snapshot = tx->shared_state.load(memory_order_relaxed);
276 gtm_word locked_by_tx = ml_mg::set_locked(tx);
278 size_t orec = ml_mg::get_orec(addr);
279 size_t orec_end = ml_mg::get_orec_end(addr, len);
282 // We need acquire memory order here so that this load will
283 // synchronize with the store that releases the orec in trycommit().
284 // In turn, this makes sure that subsequent data loads will read from
285 // a visible sequence of side effects that starts with the most recent
286 // store to the data right before the release of the orec.
287 gtm_word o = o_ml_mg.orecs[orec].load(memory_order_acquire);
289 if (likely (!ml_mg::is_more_recent_or_locked(o, snapshot)))
291 success:
292 gtm_rwlog_entry *e = tx->readlog.push();
293 e->orec = o_ml_mg.orecs + orec;
294 e->value = o;
296 else if (!ml_mg::is_locked(o))
298 // We cannot read this part of the region because it has been
299 // updated more recently than our snapshot time. If we can extend
300 // our snapshot, then we can read.
301 snapshot = extend(tx);
302 goto success;
304 else
306 // If the orec is locked by us, just skip it because we can just
307 // read from it. Otherwise, restart the transaction.
308 if (o != locked_by_tx)
309 tx->restart(RESTART_LOCKED_READ);
311 orec = o_ml_mg.get_next_orec(orec);
313 while (orec != orec_end);
314 return &tx->readlog[log_start];
317 // Second pass over orecs, verifying that the we had a consistent read.
318 // Restart the transaction if any of the orecs is locked by another
319 // transaction.
320 static void post_load(gtm_thread *tx, gtm_rwlog_entry* log)
322 for (gtm_rwlog_entry *end = tx->readlog.end(); log != end; log++)
324 // Check that the snapshot is consistent. We expect the previous data
325 // load to have acquire memory order, or be atomic and followed by an
326 // acquire fence.
327 // As a result, the data load will synchronize with the release fence
328 // issued by the transactions whose data updates the data load has read
329 // from. This forces the orec load to read from a visible sequence of
330 // side effects that starts with the other updating transaction's
331 // store that acquired the orec and set it to locked.
332 // We therefore either read a value with the locked bit set (and
333 // restart) or read an orec value that was written after the data had
334 // been written. Either will allow us to detect inconsistent reads
335 // because it will have a higher/different value.
336 // Also note that differently to validate(), we compare the raw value
337 // of the orec here, including incarnation numbers. We must prevent
338 // returning uncommitted data from loads (whereas when validating, we
339 // already performed a consistent load).
340 gtm_word o = log->orec->load(memory_order_relaxed);
341 if (log->value != o)
342 tx->restart(RESTART_VALIDATE_READ);
346 template <typename V> static V load(const V* addr, ls_modifier mod)
348 // Read-for-write should be unlikely, but we need to handle it or will
349 // break later WaW optimizations.
350 if (unlikely(mod == RfW))
352 pre_write(addr, sizeof(V));
353 return *addr;
355 if (unlikely(mod == RaW))
356 return *addr;
357 // ??? Optimize for RaR?
359 gtm_thread *tx = gtm_thr();
360 gtm_rwlog_entry* log = pre_load(tx, addr, sizeof(V));
362 // Load the data.
363 // This needs to have acquire memory order (see post_load()).
364 // Alternatively, we can put an acquire fence after the data load but this
365 // is probably less efficient.
366 // FIXME We would need an atomic load with acquire memory order here but
367 // we can't just forge an atomic load for nonatomic data because this
368 // might not work on all implementations of atomics. However, we need
369 // the acquire memory order and we can only establish this if we link
370 // it to the matching release using a reads-from relation between atomic
371 // loads. Also, the compiler is allowed to optimize nonatomic accesses
372 // differently than atomic accesses (e.g., if the load would be moved to
373 // after the fence, we potentially don't synchronize properly anymore).
374 // Instead of the following, just use an ordinary load followed by an
375 // acquire fence, and hope that this is good enough for now:
376 // V v = atomic_load_explicit((atomic<V>*)addr, memory_order_acquire);
377 V v = *addr;
378 atomic_thread_fence(memory_order_acquire);
380 // ??? Retry the whole load if it wasn't consistent?
381 post_load(tx, log);
383 return v;
386 template <typename V> static void store(V* addr, const V value,
387 ls_modifier mod)
389 if (likely(mod != WaW))
390 pre_write(addr, sizeof(V));
391 // FIXME We would need an atomic store here but we can't just forge an
392 // atomic load for nonatomic data because this might not work on all
393 // implementations of atomics. However, we need this store to link the
394 // release fence in pre_write() to the acquire operation in load, which
395 // is only guaranteed if we have a reads-from relation between atomic
396 // accesses. Also, the compiler is allowed to optimize nonatomic accesses
397 // differently than atomic accesses (e.g., if the store would be moved
398 // to before the release fence in pre_write(), things could go wrong).
399 // atomic_store_explicit((atomic<V>*)addr, value, memory_order_relaxed);
400 *addr = value;
403 public:
404 static void memtransfer_static(void *dst, const void* src, size_t size,
405 bool may_overlap, ls_modifier dst_mod, ls_modifier src_mod)
407 gtm_rwlog_entry* log = 0;
408 gtm_thread *tx = 0;
410 if (src_mod == RfW)
412 tx = gtm_thr();
413 pre_write(tx, src, size);
415 else if (src_mod != RaW && src_mod != NONTXNAL)
417 tx = gtm_thr();
418 log = pre_load(tx, src, size);
420 // ??? Optimize for RaR?
422 if (dst_mod != NONTXNAL && dst_mod != WaW)
424 if (src_mod != RfW && (src_mod == RaW || src_mod == NONTXNAL))
425 tx = gtm_thr();
426 pre_write(tx, dst, size);
429 // FIXME We should use atomics here (see store()). Let's just hope that
430 // memcpy/memmove are good enough.
431 if (!may_overlap)
432 ::memcpy(dst, src, size);
433 else
434 ::memmove(dst, src, size);
436 // ??? Retry the whole memtransfer if it wasn't consistent?
437 if (src_mod != RfW && src_mod != RaW && src_mod != NONTXNAL)
439 // See load() for why we need the acquire fence here.
440 atomic_thread_fence(memory_order_acquire);
441 post_load(tx, log);
445 static void memset_static(void *dst, int c, size_t size, ls_modifier mod)
447 if (mod != WaW)
448 pre_write(dst, size);
449 // FIXME We should use atomics here (see store()). Let's just hope that
450 // memset is good enough.
451 ::memset(dst, c, size);
454 virtual gtm_restart_reason begin_or_restart()
456 // We don't need to do anything for nested transactions.
457 gtm_thread *tx = gtm_thr();
458 if (tx->parent_txns.size() > 0)
459 return NO_RESTART;
461 // Read the current time, which becomes our snapshot time.
462 // Use acquire memory oder so that we see the lock acquisitions by update
463 // transcations that incremented the global time (see trycommit()).
464 gtm_word snapshot = o_ml_mg.time.load(memory_order_acquire);
465 // Re-initialize method group on time overflow.
466 if (snapshot >= o_ml_mg.TIME_MAX)
467 return RESTART_INIT_METHOD_GROUP;
469 // We don't need to enforce any ordering for the following store. There
470 // are no earlier data loads in this transaction, so the store cannot
471 // become visible before those (which could lead to the violation of
472 // privatization safety). The store can become visible after later loads
473 // but this does not matter because the previous value will have been
474 // smaller or equal (the serial lock will set shared_state to zero when
475 // marking the transaction as active, and restarts enforce immediate
476 // visibility of a smaller or equal value with a barrier (see
477 // rollback()).
478 tx->shared_state.store(snapshot, memory_order_relaxed);
479 return NO_RESTART;
482 virtual bool trycommit(gtm_word& priv_time)
484 gtm_thread* tx = gtm_thr();
486 // If we haven't updated anything, we can commit.
487 if (!tx->writelog.size())
489 tx->readlog.clear();
490 return true;
493 // Get a commit time.
494 // Overflow of o_ml_mg.time is prevented in begin_or_restart().
495 // We need acq_rel here because (1) the acquire part is required for our
496 // own subsequent call to validate(), and the release part is necessary to
497 // make other threads' validate() work as explained there and in extend().
498 gtm_word ct = o_ml_mg.time.fetch_add(1, memory_order_acq_rel) + 1;
500 // Extend our snapshot time to at least our commit time.
501 // Note that we do not need to validate if our snapshot time is right
502 // before the commit time because we are never sharing the same commit
503 // time with other transactions.
504 // No need to reset shared_state, which will be modified by the serial
505 // lock right after our commit anyway.
506 gtm_word snapshot = tx->shared_state.load(memory_order_relaxed);
507 if (snapshot < ct - 1 && !validate(tx))
508 return false;
510 // Release orecs.
511 // See pre_load() / post_load() for why we need release memory order.
512 // ??? Can we use a release fence and relaxed stores?
513 gtm_word v = ml_mg::set_time(ct);
514 for (gtm_rwlog_entry *i = tx->writelog.begin(), *ie = tx->writelog.end();
515 i != ie; i++)
516 i->orec->store(v, memory_order_release);
518 // We're done, clear the logs.
519 tx->writelog.clear();
520 tx->readlog.clear();
522 // Need to ensure privatization safety. Every other transaction must
523 // have a snapshot time that is at least as high as our commit time
524 // (i.e., our commit must be visible to them).
525 priv_time = ct;
526 return true;
529 virtual void rollback(gtm_transaction_cp *cp)
531 // We don't do anything for rollbacks of nested transactions.
532 // ??? We could release locks here if we snapshot writelog size. readlog
533 // is similar. This is just a performance optimization though. Nested
534 // aborts should be rather infrequent, so the additional save/restore
535 // overhead for the checkpoints could be higher.
536 if (cp != 0)
537 return;
539 gtm_thread *tx = gtm_thr();
540 gtm_word overflow_value = 0;
542 // Release orecs.
543 for (gtm_rwlog_entry *i = tx->writelog.begin(), *ie = tx->writelog.end();
544 i != ie; i++)
546 // If possible, just increase the incarnation number.
547 // See pre_load() / post_load() for why we need release memory order.
548 // ??? Can we use a release fence and relaxed stores? (Same below.)
549 if (ml_mg::has_incarnation_left(i->value))
550 i->orec->store(ml_mg::inc_incarnation(i->value),
551 memory_order_release);
552 else
554 // We have an incarnation overflow. Acquire a new timestamp, and
555 // use it from now on as value for each orec whose incarnation
556 // number cannot be increased.
557 // Overflow of o_ml_mg.time is prevented in begin_or_restart().
558 // See pre_load() / post_load() for why we need release memory
559 // order.
560 if (!overflow_value)
561 // Release memory order is sufficient but required here.
562 // In contrast to the increment in trycommit(), we need release
563 // for the same reason but do not need the acquire because we
564 // do not validate subsequently.
565 overflow_value = ml_mg::set_time(
566 o_ml_mg.time.fetch_add(1, memory_order_release) + 1);
567 i->orec->store(overflow_value, memory_order_release);
571 // We need this release fence to ensure that privatizers see the
572 // rolled-back original state (not any uncommitted values) when they read
573 // the new snapshot time that we write in begin_or_restart().
574 atomic_thread_fence(memory_order_release);
576 // We're done, clear the logs.
577 tx->writelog.clear();
578 tx->readlog.clear();
581 virtual bool supports(unsigned number_of_threads)
583 // Each txn can commit and fail and rollback once before checking for
584 // overflow, so this bounds the number of threads that we can support.
585 // In practice, this won't be a problem but we check it anyway so that
586 // we never break in the occasional weird situation.
587 return (number_of_threads * 2 <= ml_mg::OVERFLOW_RESERVE);
590 CREATE_DISPATCH_METHODS(virtual, )
591 CREATE_DISPATCH_METHODS_MEM()
593 ml_wt_dispatch() : abi_dispatch(false, true, false, false, 0, &o_ml_mg)
597 } // anon namespace
599 static const ml_wt_dispatch o_ml_wt_dispatch;
601 abi_dispatch *
602 GTM::dispatch_ml_wt ()
604 return const_cast<ml_wt_dispatch *>(&o_ml_wt_dispatch);