OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libitm/] [method-gl.cc] - Blame information for rev 772

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 737 jeremybenn
/* Copyright (C) 2011, 2012 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
  // No tail-padding necessary (the virtual functions aren't used frequently).
45
  atomic<gtm_word> orec __attribute__((aligned(HW_CACHELINE_SIZE)));
46
 
47
  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
  }
53
  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:
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
 
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
 
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
 
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:
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
 
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
 
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
 
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
        // Need to ensure privatization safety. Every other transaction must
296
        // have a snapshot time that is at least as high as our commit time
297
        // (i.e., our commit must be visible to them).
298
        priv_time = v;
299
      }
300
    return true;
301
  }
302
 
303
  virtual void rollback(gtm_transaction_cp *cp)
304
  {
305
    // We don't do anything for rollbacks of nested transactions.
306
    if (cp != 0)
307
      return;
308
 
309
    gtm_thread *tx = gtm_thr();
310
    gtm_word v = tx->shared_state.load(memory_order_relaxed);
311
 
312
    // Release lock and increment version number to prevent dirty reads.
313
    // Also reset shared state here, so that begin_or_restart() can expect a
314
    // value that is correct wrt. privatization safety.
315
    if (gl_mg::is_locked(v))
316
      {
317
        // With our rollback, global time increases.
318
        v = gl_mg::clear_locked(v) + 1;
319
 
320
        // First reset the timestamp published via shared_state.  Release
321
        // memory order will make this happen after undoing prior data writes.
322
        // This must also happen before we actually release the global orec
323
        // next, so that future update transactions in other threads observe
324
        // a meaningful snapshot time for our transaction; otherwise, they
325
        // could read a shared_store value with the LOCK_BIT set, which can
326
        // break privatization safety because it's larger than the actual
327
        // snapshot time.  Note that we only need to consider other update
328
        // transactions because only those will potentially privatize data.
329
        tx->shared_state.store(v, memory_order_release);
330
 
331
        // Release the global orec, increasing its version number / timestamp.
332
        // See begin_or_restart() for why we need release memory order here,
333
        // and we also need it to make future update transactions read the
334
        // prior update to shared_state too (update transactions acquire the
335
        // global orec with acquire memory order).
336
        o_gl_mg.orec.store(v, memory_order_release);
337
      }
338
 
339
  }
340
 
341
  CREATE_DISPATCH_METHODS(virtual, )
342
  CREATE_DISPATCH_METHODS_MEM()
343
 
344
  gl_wt_dispatch() : abi_dispatch(false, true, false, false, &o_gl_mg)
345
  { }
346
};
347
 
348
} // anon namespace
349
 
350
static const gl_wt_dispatch o_gl_wt_dispatch;
351
 
352
abi_dispatch *
353
GTM::dispatch_gl_wt ()
354
{
355
  return const_cast<gl_wt_dispatch *>(&o_gl_wt_dispatch);
356
}

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.