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 }