-/* Copyright (C) 2011 Free Software Foundation, Inc.
+/* Copyright (C) 2011-2023 Free Software Foundation, Inc.
Contributed by Torvald Riegel <triegel@redhat.com>.
This file is part of the GNU Transactional Memory Library (libitm).
static gtm_word clear_locked(gtm_word l) { return l & ~LOCK_BIT; }
// The global ownership record.
- atomic<gtm_word> orec;
+ // No tail-padding necessary (the virtual functions aren't used frequently).
+ atomic<gtm_word> orec __attribute__((aligned(HW_CACHELINE_SIZE)));
virtual void init()
{
+ // This store is only executed while holding the serial lock, so relaxed
+ // memory order is sufficient here.
orec.store(0, memory_order_relaxed);
}
virtual void fini() { }
// validate that no other update transaction comitted before we acquired the
// orec, so we have the most recent timestamp and no other transaction can
// commit until we have committed).
-// However, we therefore cannot use this method for a serial transaction
-// (because shared_state needs to remain at ~0) and we have to be careful
-// when switching to serial mode (see the special handling in trycommit() and
-// rollback()).
-// ??? This sharing adds some complexity wrt. serial mode. Just use a separate
-// state variable?
+// However, we therefore depend on shared_state not being modified by the
+// serial lock during upgrades to serial mode, which is ensured by
+// gtm_thread::serialirr_mode by not calling gtm_rwlock::write_upgrade_finish
+// before we have committed or rolled back.
class gl_wt_dispatch : public abi_dispatch
{
protected:
- static void pre_write(const void *addr, size_t len)
+ static void pre_write(const void *addr, size_t len,
+ gtm_thread *tx = gtm_thr())
{
- gtm_thread *tx = gtm_thr();
- gtm_word v = tx->shared_state.load(memory_order_acquire);
+ gtm_word v = tx->shared_state.load(memory_order_relaxed);
if (unlikely(!gl_mg::is_locked(v)))
{
// Check for and handle version number overflow.
if (unlikely(v >= gl_mg::VERSION_MAX))
tx->restart(RESTART_INIT_METHOD_GROUP);
- // CAS global orec from our snapshot time to the locked state.
// This validates that we have a consistent snapshot, which is also
// for making privatization safety work (see the class' comments).
+ // Note that this check here will be performed by the subsequent CAS
+ // again, so relaxed memory order is fine.
gtm_word now = o_gl_mg.orec.load(memory_order_relaxed);
if (now != v)
tx->restart(RESTART_VALIDATE_WRITE);
+
+ // CAS global orec from our snapshot time to the locked state.
+ // We need acquire memory order here to synchronize with other
+ // (ownership) releases of the orec. We do not need acq_rel order
+ // because whenever another thread reads from this CAS'
+ // modification, then it will abort anyway and does not rely on
+ // any further happens-before relation to be established.
+ // Also note that unlike in ml_wt's increase of the global time
+ // base (remember that the global orec is used as time base), we do
+ // not need require memory order here because we do not need to make
+ // prior orec acquisitions visible to other threads that try to
+ // extend their snapshot time.
if (!o_gl_mg.orec.compare_exchange_strong (now, gl_mg::set_locked(now),
memory_order_acquire))
tx->restart(RESTART_LOCKED_WRITE);
+ // We use an explicit fence here to avoid having to use release
+ // memory order for all subsequent data stores. This fence will
+ // synchronize with loads of the data with acquire memory order. See
+ // validate() for why this is necessary.
+ // Adding require memory order to the prior CAS is not sufficient,
+ // at least according to the Batty et al. formalization of the
+ // memory model.
+ atomic_thread_fence(memory_order_release);
+
// Set shared_state to new value.
tx->shared_state.store(gl_mg::set_locked(now), memory_order_release);
}
- // TODO Ensure that this gets inlined: Use internal log interface and LTO.
- GTM_LB(addr, len);
+ tx->undolog.log(addr, len);
}
- static void validate()
+ static void validate(gtm_thread *tx = gtm_thr())
{
- // Check that snapshot is consistent. The barrier ensures that this
- // happens after previous data loads. Recall that load cannot itself
- // have memory_order_release.
- gtm_thread *tx = gtm_thr();
- atomic_thread_fence(memory_order_release);
+ // Check that snapshot is consistent. We expect the previous data load to
+ // have acquire memory order, or be atomic and followed by an acquire
+ // fence.
+ // As a result, the data load will synchronize with the release fence
+ // issued by the transactions whose data updates the data load has read
+ // from. This forces the orec load to read from a visible sequence of side
+ // effects that starts with the other updating transaction's store that
+ // acquired the orec and set it to locked.
+ // We therefore either read a value with the locked bit set (and restart)
+ // or read an orec value that was written after the data had been written.
+ // Either will allow us to detect inconsistent reads because it will have
+ // a higher/different value.
gtm_word l = o_gl_mg.orec.load(memory_order_relaxed);
if (l != tx->shared_state.load(memory_order_relaxed))
tx->restart(RESTART_VALIDATE_READ);
pre_write(addr, sizeof(V));
return *addr;
}
+ if (unlikely(mod == RaW))
+ return *addr;
+
+ // We do not have acquired the orec, so we need to load a value and then
+ // validate that this was consistent.
+ // This needs to have acquire memory order (see validate()).
+ // Alternatively, we can put an acquire fence after the data load but this
+ // is probably less efficient.
+ // FIXME We would need an atomic load with acquire memory order here but
+ // we can't just forge an atomic load for nonatomic data because this
+ // might not work on all implementations of atomics. However, we need
+ // the acquire memory order and we can only establish this if we link
+ // it to the matching release using a reads-from relation between atomic
+ // loads. Also, the compiler is allowed to optimize nonatomic accesses
+ // differently than atomic accesses (e.g., if the load would be moved to
+ // after the fence, we potentially don't synchronize properly anymore).
+ // Instead of the following, just use an ordinary load followed by an
+ // acquire fence, and hope that this is good enough for now:
+ // V v = atomic_load_explicit((atomic<V>*)addr, memory_order_acquire);
V v = *addr;
- if (likely(mod != RaW))
- validate();
+ atomic_thread_fence(memory_order_acquire);
+ validate();
return v;
}
template <typename V> static void store(V* addr, const V value,
ls_modifier mod)
{
- if (unlikely(mod != WaW))
+ if (likely(mod != WaW))
pre_write(addr, sizeof(V));
+ // FIXME We would need an atomic store here but we can't just forge an
+ // atomic load for nonatomic data because this might not work on all
+ // implementations of atomics. However, we need this store to link the
+ // release fence in pre_write() to the acquire operation in load, which
+ // is only guaranteed if we have a reads-from relation between atomic
+ // accesses. Also, the compiler is allowed to optimize nonatomic accesses
+ // differently than atomic accesses (e.g., if the store would be moved
+ // to before the release fence in pre_write(), things could go wrong).
+ // atomic_store_explicit((atomic<V>*)addr, value, memory_order_relaxed);
*addr = value;
}
static void memtransfer_static(void *dst, const void* src, size_t size,
bool may_overlap, ls_modifier dst_mod, ls_modifier src_mod)
{
- if ((dst_mod != WaW && src_mod != RaW)
- && (dst_mod != NONTXNAL || src_mod == RfW))
- pre_write(dst, size);
-
+ gtm_thread *tx = gtm_thr();
+ if (dst_mod != WaW && dst_mod != NONTXNAL)
+ pre_write(dst, size, tx);
+ // We need at least undo-logging for an RfW src region because we might
+ // subsequently write there with WaW.
+ if (src_mod == RfW)
+ pre_write(src, size, tx);
+
+ // FIXME We should use atomics here (see store()). Let's just hope that
+ // memcpy/memmove are good enough.
if (!may_overlap)
::memcpy(dst, src, size);
else
if (src_mod != RfW && src_mod != RaW && src_mod != NONTXNAL
&& dst_mod != WaW)
- validate();
+ validate(tx);
}
static void memset_static(void *dst, int c, size_t size, ls_modifier mod)
{
if (mod != WaW)
pre_write(dst, size);
+ // FIXME We should use atomics here (see store()). Let's just hope that
+ // memset is good enough.
::memset(dst, c, size);
}
gtm_word v;
while (1)
{
+ // We need acquire memory order here so that this load will
+ // synchronize with the store that releases the orec in trycommit().
+ // In turn, this makes sure that subsequent data loads will read from
+ // a visible sequence of side effects that starts with the most recent
+ // store to the data right before the release of the orec.
v = o_gl_mg.orec.load(memory_order_acquire);
if (!gl_mg::is_locked(v))
break;
// smaller or equal (the serial lock will set shared_state to zero when
// marking the transaction as active, and restarts enforce immediate
// visibility of a smaller or equal value with a barrier (see
- // release_orec()).
+ // rollback()).
tx->shared_state.store(v, memory_order_relaxed);
return NO_RESTART;
}
virtual bool trycommit(gtm_word& priv_time)
{
gtm_thread* tx = gtm_thr();
- gtm_word v = tx->shared_state.load(memory_order_acquire);
-
- // Special case: If shared_state is ~0, then we have acquired the
- // serial lock (tx->state is not updated yet). In this case, the previous
- // value isn't available anymore, so grab it from the global lock, which
- // must have a meaningful value because no other transactions are active
- // anymore. In particular, if it is locked, then we are an update
- // transaction, which is all we care about for commit.
- if (v == ~(typeof v)0)
- v = o_gl_mg.orec.load(memory_order_relaxed);
+ gtm_word v = tx->shared_state.load(memory_order_relaxed);
// Release the orec but do not reset shared_state, which will be modified
// by the serial lock right after our commit anyway. Also, resetting
if (gl_mg::is_locked(v))
{
// Release the global orec, increasing its version number / timestamp.
+ // See begin_or_restart() for why we need release memory order here.
v = gl_mg::clear_locked(v) + 1;
o_gl_mg.orec.store(v, memory_order_release);
-
- // Need to ensure privatization safety. Every other transaction must
- // have a snapshot time that is at least as high as our commit time
- // (i.e., our commit must be visible to them).
- priv_time = v;
}
+
+ // Need to ensure privatization safety. Every other transaction must have
+ // a snapshot time that is at least as high as our commit time (i.e., our
+ // commit must be visible to them). Because of proxy privatization, we
+ // must ensure that even if we are a read-only transaction. See
+ // ml_wt_dispatch::trycommit() for details: We can't get quite the same
+ // set of problems because we just use one orec and thus, for example,
+ // there cannot be concurrent writers -- but we can still get pending
+ // loads to privatized data when not ensuring privatization safety, which
+ // is problematic if the program unmaps the privatized memory.
+ priv_time = v;
return true;
}
return;
gtm_thread *tx = gtm_thr();
- gtm_word v = tx->shared_state.load(memory_order_acquire);
- // Special case: If shared_state is ~0, then we have acquired the
- // serial lock (tx->state is not updated yet). In this case, the previous
- // value isn't available anymore, so grab it from the global lock, which
- // must have a meaningful value because no other transactions are active
- // anymore. In particular, if it is locked, then we are an update
- // transaction, which is all we care about for rollback.
- bool is_serial = v == ~(typeof v)0;
- if (is_serial)
- v = o_gl_mg.orec.load(memory_order_relaxed);
+ gtm_word v = tx->shared_state.load(memory_order_relaxed);
// Release lock and increment version number to prevent dirty reads.
// Also reset shared state here, so that begin_or_restart() can expect a
// value that is correct wrt. privatization safety.
if (gl_mg::is_locked(v))
{
- // Release the global orec, increasing its version number / timestamp.
+ // With our rollback, global time increases.
v = gl_mg::clear_locked(v) + 1;
- o_gl_mg.orec.store(v, memory_order_release);
- // Also reset the timestamp published via shared_state.
- // Special case: Only do this if we are not a serial transaction
- // because otherwise, we would interfere with the serial lock.
- if (!is_serial)
- tx->shared_state.store(v, memory_order_relaxed);
-
- // We need a store-load barrier after this store to prevent it
- // from becoming visible after later data loads because the
- // previous value of shared_state has been higher than the actual
- // snapshot time (the lock bit had been set), which could break
- // privatization safety. We do not need a barrier before this
- // store (see pre_write() for an explanation).
- atomic_thread_fence(memory_order_acq_rel);
+ // First reset the timestamp published via shared_state. Release
+ // memory order will make this happen after undoing prior data writes.
+ // This must also happen before we actually release the global orec
+ // next, so that future update transactions in other threads observe
+ // a meaningful snapshot time for our transaction; otherwise, they
+ // could read a shared_store value with the LOCK_BIT set, which can
+ // break privatization safety because it's larger than the actual
+ // snapshot time. Note that we only need to consider other update
+ // transactions because only those will potentially privatize data.
+ tx->shared_state.store(v, memory_order_release);
+
+ // Release the global orec, increasing its version number / timestamp.
+ // See begin_or_restart() for why we need release memory order here,
+ // and we also need it to make future update transactions read the
+ // prior update to shared_state too (update transactions acquire the
+ // global orec with acquire memory order).
+ o_gl_mg.orec.store(v, memory_order_release);
}
}
+ virtual bool snapshot_most_recent()
+ {
+ // This is the same check as in validate() except that we do not restart
+ // on failure but simply return the result.
+ return o_gl_mg.orec.load(memory_order_relaxed)
+ == gtm_thr()->shared_state.load(memory_order_relaxed);
+ }
+
+
CREATE_DISPATCH_METHODS(virtual, )
CREATE_DISPATCH_METHODS_MEM()
- gl_wt_dispatch() : abi_dispatch(false, true, false, false, &o_gl_mg)
+ gl_wt_dispatch() : abi_dispatch(false, true, false, false, 0, &o_gl_mg)
{ }
};