OSDN Git Service

Merge from transactional-memory branch.
[pf3gnuchains/gcc-fork.git] / libitm / method-gl.cc
1 /* Copyright (C) 2011 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;
39   static bool is_locked(gtm_word l) { return l & LOCK_BIT; }
40   static gtm_word set_locked(gtm_word l) { return l | LOCK_BIT; }
41   static gtm_word clear_locked(gtm_word l) { return l & ~LOCK_BIT; }
42
43   // The global ownership record.
44   gtm_word orec;
45   virtual void init()
46   {
47     orec = 0;
48   }
49   virtual void fini() { }
50 };
51
52 static gl_mg o_gl_mg;
53
54
55 // The global lock, write-through TM method.
56 // Acquires the orec eagerly before the first write, and then writes through.
57 // Reads abort if the global orec's version number changed or if it is locked.
58 // Currently, writes require undo-logging to prevent deadlock between the
59 // serial lock and the global orec (writer txn acquires orec, reader txn
60 // upgrades to serial and waits for all other txns, writer tries to upgrade to
61 // serial too but cannot, writer cannot abort either, deadlock). We could
62 // avoid this if the serial lock would allow us to prevent other threads from
63 // going to serial mode, but this probably is too much additional complexity
64 // just to optimize this TM method.
65 // gtm_thread::shared_state is used to store a transaction's current
66 // snapshot time (or commit time). The serial lock uses ~0 for inactive
67 // transactions and 0 for active ones. Thus, we always have a meaningful
68 // timestamp in shared_state that can be used to implement quiescence-based
69 // privatization safety. This even holds if a writing transaction has the
70 // lock bit set in its shared_state because this is fine for both the serial
71 // lock (the value will be smaller than ~0) and privatization safety (we
72 // validate that no other update transaction comitted before we acquired the
73 // orec, so we have the most recent timestamp and no other transaction can
74 // commit until we have committed).
75 // However, we therefore cannot use this method for a serial transaction
76 // (because shared_state needs to remain at ~0) and we have to be careful
77 // when switching to serial mode (see the special handling in trycommit() and
78 // rollback()).
79 // ??? This sharing adds some complexity wrt. serial mode. Just use a separate
80 // state variable?
81 class gl_wt_dispatch : public abi_dispatch
82 {
83 protected:
84   static void pre_write(const void *addr, size_t len)
85   {
86     gtm_thread *tx = gtm_thr();
87     if (unlikely(!gl_mg::is_locked(tx->shared_state)))
88       {
89         // Check for and handle version number overflow.
90         if (unlikely(tx->shared_state >= gl_mg::VERSION_MAX))
91           tx->restart(RESTART_INIT_METHOD_GROUP);
92
93         // CAS global orec from our snapshot time to the locked state.
94         // This validates that we have a consistent snapshot, which is also
95         // for making privatization safety work (see the class' comments).
96         gtm_word now = o_gl_mg.orec;
97         if (now != tx->shared_state)
98           tx->restart(RESTART_VALIDATE_WRITE);
99         if (__sync_val_compare_and_swap(&o_gl_mg.orec, now,
100             gl_mg::set_locked(now)) != now)
101           tx->restart(RESTART_LOCKED_WRITE);
102
103         // Set shared_state to new value. The CAS is a full barrier, so the
104         // acquisition of the global orec is visible before this store here,
105         // and the store will not be visible before earlier data loads, which
106         // is required to correctly ensure privatization safety (see
107         // begin_and_restart() and release_orec() for further comments).
108         tx->shared_state = gl_mg::set_locked(now);
109       }
110
111     // TODO Ensure that this gets inlined: Use internal log interface and LTO.
112     GTM_LB(addr, len);
113   }
114
115   static void validate()
116   {
117     // Check that snapshot is consistent. The barrier ensures that this
118     // happens after previous data loads.
119     atomic_read_barrier();
120     gtm_thread *tx = gtm_thr();
121     gtm_word l = o_gl_mg.orec;
122     if (l != tx->shared_state)
123       tx->restart(RESTART_VALIDATE_READ);
124   }
125
126   template <typename V> static V load(const V* addr, ls_modifier mod)
127   {
128     // Read-for-write should be unlikely, but we need to handle it or will
129     // break later WaW optimizations.
130     if (unlikely(mod == RfW))
131       {
132         pre_write(addr, sizeof(V));
133         return *addr;
134       }
135     V v = *addr;
136     if (likely(mod != RaW))
137       validate();
138     return v;
139   }
140
141   template <typename V> static void store(V* addr, const V value,
142       ls_modifier mod)
143   {
144     if (unlikely(mod != WaW))
145       pre_write(addr, sizeof(V));
146     *addr = value;
147   }
148
149 public:
150   static void memtransfer_static(void *dst, const void* src, size_t size,
151       bool may_overlap, ls_modifier dst_mod, ls_modifier src_mod)
152   {
153     if ((dst_mod != WaW && src_mod != RaW)
154         && (dst_mod != NONTXNAL || src_mod == RfW))
155       pre_write(dst, size);
156
157     if (!may_overlap)
158       ::memcpy(dst, src, size);
159     else
160       ::memmove(dst, src, size);
161
162     if (src_mod != RfW && src_mod != RaW && src_mod != NONTXNAL
163         && dst_mod != WaW)
164       validate();
165   }
166
167   static void memset_static(void *dst, int c, size_t size, ls_modifier mod)
168   {
169     if (mod != WaW)
170       pre_write(dst, size);
171     ::memset(dst, c, size);
172   }
173
174   virtual gtm_restart_reason begin_or_restart()
175   {
176     // We don't need to do anything for nested transactions.
177     gtm_thread *tx = gtm_thr();
178     if (tx->parent_txns.size() > 0)
179       return NO_RESTART;
180
181     // Spin until global orec is not locked.
182     // TODO This is not necessary if there are no pure loads (check txn props).
183     gtm_word v;
184     unsigned i = 0;
185     while (gl_mg::is_locked(v = o_gl_mg.orec))
186       {
187         // TODO need method-specific max spin count
188         if (++i > gtm_spin_count_var) return RESTART_VALIDATE_READ;
189         cpu_relax();
190       }
191     // This barrier ensures that we have read the global orec before later
192     // data loads.
193     atomic_read_barrier();
194
195     // Everything is okay, we have a snapshot time.
196     // We don't need to enforce any ordering for the following store. There
197     // are no earlier data loads in this transaction, so the store cannot
198     // become visible before those (which could lead to the violation of
199     // privatization safety). The store can become visible after later loads
200     // but this does not matter because the previous value will have been
201     // smaller or equal (the serial lock will set shared_state to zero when
202     // marking the transaction as active, and restarts enforce immediate
203     // visibility of a smaller or equal value with a barrier (see
204     // release_orec()).
205     tx->shared_state = v;
206     return NO_RESTART;
207   }
208
209   virtual bool trycommit(gtm_word& priv_time)
210   {
211     gtm_thread* tx = gtm_thr();
212     gtm_word v = tx->shared_state;
213
214     // Special case: If shared_state is ~0, then we have acquired the
215     // serial lock (tx->state is not updated yet). In this case, the previous
216     // value isn't available anymore, so grab it from the global lock, which
217     // must have a meaningful value because no other transactions are active
218     // anymore. In particular, if it is locked, then we are an update
219     // transaction, which is all we care about for commit.
220     if (v == ~(typeof v)0)
221       v = o_gl_mg.orec;
222
223     // Release the orec but do not reset shared_state, which will be modified
224     // by the serial lock right after our commit anyway. Also, resetting
225     // shared state here would interfere with the serial lock's use of this
226     // location.
227     if (gl_mg::is_locked(v))
228       {
229         // Release the global orec, increasing its version number / timestamp.
230         // TODO replace with C++0x-style atomics (a release in this case)
231         atomic_write_barrier();
232         v = gl_mg::clear_locked(v) + 1;
233         o_gl_mg.orec = v;
234
235         // Need to ensure privatization safety. Every other transaction must
236         // have a snapshot time that is at least as high as our commit time
237         // (i.e., our commit must be visible to them).
238         priv_time = v;
239       }
240     return true;
241   }
242
243   virtual void rollback(gtm_transaction_cp *cp)
244   {
245     // We don't do anything for rollbacks of nested transactions.
246     if (cp != 0)
247       return;
248
249     gtm_thread *tx = gtm_thr();
250     gtm_word v = tx->shared_state;
251     // Special case: If shared_state is ~0, then we have acquired the
252     // serial lock (tx->state is not updated yet). In this case, the previous
253     // value isn't available anymore, so grab it from the global lock, which
254     // must have a meaningful value because no other transactions are active
255     // anymore. In particular, if it is locked, then we are an update
256     // transaction, which is all we care about for rollback.
257     if (v == ~(typeof v)0)
258       v = o_gl_mg.orec;
259
260     // Release lock and increment version number to prevent dirty reads.
261     // Also reset shared state here, so that begin_or_restart() can expect a
262     // value that is correct wrt. privatization safety.
263     if (gl_mg::is_locked(v))
264       {
265         // Release the global orec, increasing its version number / timestamp.
266         // TODO replace with C++0x-style atomics (a release in this case)
267         atomic_write_barrier();
268         v = gl_mg::clear_locked(v) + 1;
269         o_gl_mg.orec = v;
270
271         // Also reset the timestamp published via shared_state.
272         // Special case: Only do this if we are not a serial transaction
273         // because otherwise, we would interfere with the serial lock.
274         if (tx->shared_state != ~(typeof tx->shared_state)0)
275           tx->shared_state = v;
276
277         // We need a store-load barrier after this store to prevent it
278         // from becoming visible after later data loads because the
279         // previous value of shared_state has been higher than the actual
280         // snapshot time (the lock bit had been set), which could break
281         // privatization safety. We do not need a barrier before this
282         // store (see pre_write() for an explanation).
283         __sync_synchronize();
284       }
285
286   }
287
288   CREATE_DISPATCH_METHODS(virtual, )
289   CREATE_DISPATCH_METHODS_MEM()
290
291   gl_wt_dispatch() : abi_dispatch(false, true, false, false, &o_gl_mg)
292   { }
293 };
294
295 } // anon namespace
296
297 static const gl_wt_dispatch o_gl_wt_dispatch;
298
299 abi_dispatch *
300 GTM::dispatch_gl_wt ()
301 {
302   return const_cast<gl_wt_dispatch *>(&o_gl_wt_dispatch);
303 }