1 /* Copyright (C) 2011-2016 Free Software Foundation, Inc.
2    Contributed by Torvald Riegel <triegel@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 
27 using namespace GTM;
28 
29 namespace {
30 
31 // This group consists of all TM methods that synchronize via just a single
32 // global lock (or ownership record).
33 struct gl_mg : public method_group
34 {
35   static const gtm_word LOCK_BIT = (~(gtm_word)0 >> 1) + 1;
36   // We can't use the full bitrange because ~0 in gtm_thread::shared_state has
37   // special meaning.
38   static const gtm_word VERSION_MAX = (~(gtm_word)0 >> 1) - 1;
is_locked__anoncc7278300111::gl_mg39   static bool is_locked(gtm_word l) { return l & LOCK_BIT; }
set_locked__anoncc7278300111::gl_mg40   static gtm_word set_locked(gtm_word l) { return l | LOCK_BIT; }
clear_locked__anoncc7278300111::gl_mg41   static gtm_word clear_locked(gtm_word l) { return l & ~LOCK_BIT; }
42 
43   // The global ownership record.
44   // No tail-padding necessary (the virtual functions aren't used frequently).
45   atomic<gtm_word> orec __attribute__((aligned(HW_CACHELINE_SIZE)));
46 
init__anoncc7278300111::gl_mg47   virtual void init()
48   {
49     // This store is only executed while holding the serial lock, so relaxed
50     // memory order is sufficient here.
51     orec.store(0, memory_order_relaxed);
52   }
fini__anoncc7278300111::gl_mg53   virtual void fini() { }
54 };
55 
56 static gl_mg o_gl_mg;
57 
58 
59 // The global lock, write-through TM method.
60 // Acquires the orec eagerly before the first write, and then writes through.
61 // Reads abort if the global orec's version number changed or if it is locked.
62 // Currently, writes require undo-logging to prevent deadlock between the
63 // serial lock and the global orec (writer txn acquires orec, reader txn
64 // upgrades to serial and waits for all other txns, writer tries to upgrade to
65 // serial too but cannot, writer cannot abort either, deadlock). We could
66 // avoid this if the serial lock would allow us to prevent other threads from
67 // going to serial mode, but this probably is too much additional complexity
68 // just to optimize this TM method.
69 // gtm_thread::shared_state is used to store a transaction's current
70 // snapshot time (or commit time). The serial lock uses ~0 for inactive
71 // transactions and 0 for active ones. Thus, we always have a meaningful
72 // timestamp in shared_state that can be used to implement quiescence-based
73 // privatization safety. This even holds if a writing transaction has the
74 // lock bit set in its shared_state because this is fine for both the serial
75 // lock (the value will be smaller than ~0) and privatization safety (we
76 // validate that no other update transaction comitted before we acquired the
77 // orec, so we have the most recent timestamp and no other transaction can
78 // commit until we have committed).
79 // However, we therefore depend on shared_state not being modified by the
80 // serial lock during upgrades to serial mode, which is ensured by
81 // gtm_thread::serialirr_mode by not calling gtm_rwlock::write_upgrade_finish
82 // before we have committed or rolled back.
83 class gl_wt_dispatch : public abi_dispatch
84 {
85 protected:
pre_write(const void * addr,size_t len,gtm_thread * tx=gtm_thr ())86   static void pre_write(const void *addr, size_t len,
87       gtm_thread *tx = gtm_thr())
88   {
89     gtm_word v = tx->shared_state.load(memory_order_relaxed);
90     if (unlikely(!gl_mg::is_locked(v)))
91       {
92 	// Check for and handle version number overflow.
93 	if (unlikely(v >= gl_mg::VERSION_MAX))
94 	  tx->restart(RESTART_INIT_METHOD_GROUP);
95 
96 	// This validates that we have a consistent snapshot, which is also
97 	// for making privatization safety work (see the class' comments).
98 	// Note that this check here will be performed by the subsequent CAS
99 	// again, so relaxed memory order is fine.
100 	gtm_word now = o_gl_mg.orec.load(memory_order_relaxed);
101 	if (now != v)
102 	  tx->restart(RESTART_VALIDATE_WRITE);
103 
104 	// CAS global orec from our snapshot time to the locked state.
105         // We need acquire memory order here to synchronize with other
106         // (ownership) releases of the orec.  We do not need acq_rel order
107         // because whenever another thread reads from this CAS'
108         // modification, then it will abort anyway and does not rely on
109         // any further happens-before relation to be established.
110 	// Also note that unlike in ml_wt's increase of the global time
111 	// base (remember that the global orec is used as time base), we do
112 	// not need require memory order here because we do not need to make
113 	// prior orec acquisitions visible to other threads that try to
114 	// extend their snapshot time.
115 	if (!o_gl_mg.orec.compare_exchange_strong (now, gl_mg::set_locked(now),
116 						   memory_order_acquire))
117 	  tx->restart(RESTART_LOCKED_WRITE);
118 
119 	// We use an explicit fence here to avoid having to use release
120 	// memory order for all subsequent data stores.  This fence will
121 	// synchronize with loads of the data with acquire memory order.  See
122 	// validate() for why this is necessary.
123         // Adding require memory order to the prior CAS is not sufficient,
124         // at least according to the Batty et al. formalization of the
125         // memory model.
126 	atomic_thread_fence(memory_order_release);
127 
128 	// Set shared_state to new value.
129 	tx->shared_state.store(gl_mg::set_locked(now), memory_order_release);
130       }
131 
132     tx->undolog.log(addr, len);
133   }
134 
validate(gtm_thread * tx=gtm_thr ())135   static void validate(gtm_thread *tx = gtm_thr())
136   {
137     // Check that snapshot is consistent.  We expect the previous data load to
138     // have acquire memory order, or be atomic and followed by an acquire
139     // fence.
140     // As a result, the data load will synchronize with the release fence
141     // issued by the transactions whose data updates the data load has read
142     // from.  This forces the orec load to read from a visible sequence of side
143     // effects that starts with the other updating transaction's store that
144     // acquired the orec and set it to locked.
145     // We therefore either read a value with the locked bit set (and restart)
146     // or read an orec value that was written after the data had been written.
147     // Either will allow us to detect inconsistent reads because it will have
148     // a higher/different value.
149     gtm_word l = o_gl_mg.orec.load(memory_order_relaxed);
150     if (l != tx->shared_state.load(memory_order_relaxed))
151       tx->restart(RESTART_VALIDATE_READ);
152   }
153 
load(const V * addr,ls_modifier mod)154   template <typename V> static V load(const V* addr, ls_modifier mod)
155   {
156     // Read-for-write should be unlikely, but we need to handle it or will
157     // break later WaW optimizations.
158     if (unlikely(mod == RfW))
159       {
160 	pre_write(addr, sizeof(V));
161 	return *addr;
162       }
163     if (unlikely(mod == RaW))
164       return *addr;
165 
166     // We do not have acquired the orec, so we need to load a value and then
167     // validate that this was consistent.
168     // This needs to have acquire memory order (see validate()).
169     // Alternatively, we can put an acquire fence after the data load but this
170     // is probably less efficient.
171     // FIXME We would need an atomic load with acquire memory order here but
172     // we can't just forge an atomic load for nonatomic data because this
173     // might not work on all implementations of atomics.  However, we need
174     // the acquire memory order and we can only establish this if we link
175     // it to the matching release using a reads-from relation between atomic
176     // loads.  Also, the compiler is allowed to optimize nonatomic accesses
177     // differently than atomic accesses (e.g., if the load would be moved to
178     // after the fence, we potentially don't synchronize properly anymore).
179     // Instead of the following, just use an ordinary load followed by an
180     // acquire fence, and hope that this is good enough for now:
181     // V v = atomic_load_explicit((atomic<V>*)addr, memory_order_acquire);
182     V v = *addr;
183     atomic_thread_fence(memory_order_acquire);
184     validate();
185     return v;
186   }
187 
store(V * addr,const V value,ls_modifier mod)188   template <typename V> static void store(V* addr, const V value,
189       ls_modifier mod)
190   {
191     if (likely(mod != WaW))
192       pre_write(addr, sizeof(V));
193     // FIXME We would need an atomic store here but we can't just forge an
194     // atomic load for nonatomic data because this might not work on all
195     // implementations of atomics.  However, we need this store to link the
196     // release fence in pre_write() to the acquire operation in load, which
197     // is only guaranteed if we have a reads-from relation between atomic
198     // accesses.  Also, the compiler is allowed to optimize nonatomic accesses
199     // differently than atomic accesses (e.g., if the store would be moved
200     // to before the release fence in pre_write(), things could go wrong).
201     // atomic_store_explicit((atomic<V>*)addr, value, memory_order_relaxed);
202     *addr = value;
203   }
204 
205 public:
memtransfer_static(void * dst,const void * src,size_t size,bool may_overlap,ls_modifier dst_mod,ls_modifier src_mod)206   static void memtransfer_static(void *dst, const void* src, size_t size,
207       bool may_overlap, ls_modifier dst_mod, ls_modifier src_mod)
208   {
209     gtm_thread *tx = gtm_thr();
210     if (dst_mod != WaW && dst_mod != NONTXNAL)
211       pre_write(dst, size, tx);
212     // We need at least undo-logging for an RfW src region because we might
213     // subsequently write there with WaW.
214     if (src_mod == RfW)
215       pre_write(src, size, tx);
216 
217     // FIXME We should use atomics here (see store()).  Let's just hope that
218     // memcpy/memmove are good enough.
219     if (!may_overlap)
220       ::memcpy(dst, src, size);
221     else
222       ::memmove(dst, src, size);
223 
224     if (src_mod != RfW && src_mod != RaW && src_mod != NONTXNAL
225 	&& dst_mod != WaW)
226       validate(tx);
227   }
228 
memset_static(void * dst,int c,size_t size,ls_modifier mod)229   static void memset_static(void *dst, int c, size_t size, ls_modifier mod)
230   {
231     if (mod != WaW)
232       pre_write(dst, size);
233     // FIXME We should use atomics here (see store()).  Let's just hope that
234     // memset is good enough.
235     ::memset(dst, c, size);
236   }
237 
begin_or_restart()238   virtual gtm_restart_reason begin_or_restart()
239   {
240     // We don't need to do anything for nested transactions.
241     gtm_thread *tx = gtm_thr();
242     if (tx->parent_txns.size() > 0)
243       return NO_RESTART;
244 
245     // Spin until global orec is not locked.
246     // TODO This is not necessary if there are no pure loads (check txn props).
247     unsigned i = 0;
248     gtm_word v;
249     while (1)
250       {
251         // We need acquire memory order here so that this load will
252         // synchronize with the store that releases the orec in trycommit().
253         // In turn, this makes sure that subsequent data loads will read from
254         // a visible sequence of side effects that starts with the most recent
255         // store to the data right before the release of the orec.
256         v = o_gl_mg.orec.load(memory_order_acquire);
257         if (!gl_mg::is_locked(v))
258 	  break;
259 	// TODO need method-specific max spin count
260 	if (++i > gtm_spin_count_var)
261 	  return RESTART_VALIDATE_READ;
262 	cpu_relax();
263       }
264 
265     // Everything is okay, we have a snapshot time.
266     // We don't need to enforce any ordering for the following store. There
267     // are no earlier data loads in this transaction, so the store cannot
268     // become visible before those (which could lead to the violation of
269     // privatization safety). The store can become visible after later loads
270     // but this does not matter because the previous value will have been
271     // smaller or equal (the serial lock will set shared_state to zero when
272     // marking the transaction as active, and restarts enforce immediate
273     // visibility of a smaller or equal value with a barrier (see
274     // rollback()).
275     tx->shared_state.store(v, memory_order_relaxed);
276     return NO_RESTART;
277   }
278 
trycommit(gtm_word & priv_time)279   virtual bool trycommit(gtm_word& priv_time)
280   {
281     gtm_thread* tx = gtm_thr();
282     gtm_word v = tx->shared_state.load(memory_order_relaxed);
283 
284     // Release the orec but do not reset shared_state, which will be modified
285     // by the serial lock right after our commit anyway. Also, resetting
286     // shared state here would interfere with the serial lock's use of this
287     // location.
288     if (gl_mg::is_locked(v))
289       {
290 	// Release the global orec, increasing its version number / timestamp.
291         // See begin_or_restart() for why we need release memory order here.
292 	v = gl_mg::clear_locked(v) + 1;
293 	o_gl_mg.orec.store(v, memory_order_release);
294       }
295 
296     // Need to ensure privatization safety. Every other transaction must have
297     // a snapshot time that is at least as high as our commit time (i.e., our
298     // commit must be visible to them).  Because of proxy privatization, we
299     // must ensure that even if we are a read-only transaction.  See
300     // ml_wt_dispatch::trycommit() for details: We can't get quite the same
301     // set of problems because we just use one orec and thus, for example,
302     // there cannot be concurrent writers -- but we can still get pending
303     // loads to privatized data when not ensuring privatization safety, which
304     // is problematic if the program unmaps the privatized memory.
305     priv_time = v;
306     return true;
307   }
308 
rollback(gtm_transaction_cp * cp)309   virtual void rollback(gtm_transaction_cp *cp)
310   {
311     // We don't do anything for rollbacks of nested transactions.
312     if (cp != 0)
313       return;
314 
315     gtm_thread *tx = gtm_thr();
316     gtm_word v = tx->shared_state.load(memory_order_relaxed);
317 
318     // Release lock and increment version number to prevent dirty reads.
319     // Also reset shared state here, so that begin_or_restart() can expect a
320     // value that is correct wrt. privatization safety.
321     if (gl_mg::is_locked(v))
322       {
323 	// With our rollback, global time increases.
324 	v = gl_mg::clear_locked(v) + 1;
325 
326 	// First reset the timestamp published via shared_state.  Release
327 	// memory order will make this happen after undoing prior data writes.
328 	// This must also happen before we actually release the global orec
329 	// next, so that future update transactions in other threads observe
330 	// a meaningful snapshot time for our transaction; otherwise, they
331 	// could read a shared_store value with the LOCK_BIT set, which can
332 	// break privatization safety because it's larger than the actual
333 	// snapshot time.  Note that we only need to consider other update
334 	// transactions because only those will potentially privatize data.
335 	tx->shared_state.store(v, memory_order_release);
336 
337 	// Release the global orec, increasing its version number / timestamp.
338 	// See begin_or_restart() for why we need release memory order here,
339 	// and we also need it to make future update transactions read the
340 	// prior update to shared_state too (update transactions acquire the
341 	// global orec with acquire memory order).
342 	o_gl_mg.orec.store(v, memory_order_release);
343       }
344 
345   }
346 
snapshot_most_recent()347   virtual bool snapshot_most_recent()
348   {
349     // This is the same check as in validate() except that we do not restart
350     // on failure but simply return the result.
351     return o_gl_mg.orec.load(memory_order_relaxed)
352 	== gtm_thr()->shared_state.load(memory_order_relaxed);
353   }
354 
355 
356   CREATE_DISPATCH_METHODS(virtual, )
CREATE_DISPATCH_METHODS_MEM()357   CREATE_DISPATCH_METHODS_MEM()
358 
359   gl_wt_dispatch() : abi_dispatch(false, true, false, false, 0, &o_gl_mg)
360   { }
361 };
362 
363 } // anon namespace
364 
365 static const gl_wt_dispatch o_gl_wt_dispatch;
366 
367 abi_dispatch *
dispatch_gl_wt()368 GTM::dispatch_gl_wt ()
369 {
370   return const_cast<gl_wt_dispatch *>(&o_gl_wt_dispatch);
371 }
372