folly::pushmi::entangled< T, Dual > Struct Template Reference

#include <entangle.h>

Public Member Functions
bool	tryLockBoth ()
void	lockBoth ()
void	unlockBoth ()
	entangled ()=delete
	entangled (const entangled &)=delete
entangled &	operator= (const entangled &)=delete
entangled &	operator= (entangled &&)=delete
	entangled (T t)
	entangled (entangled &&other)
	~entangled ()
Dual *	lockPointerToDual ()
void	unlockPointerToDual ()

Public Attributes
std::atomic< int >	stateMachine
T	t
entangled< Dual, T > *	dual

Static Public Attributes
static const int	kUnlocked = 0
static const int	kLocked = 1
static const int	kLockedAndLossAcknowledged = 2

Detailed Description

template<class T, class Dual>
struct folly::pushmi::entangled< T, Dual >

Definition at line 71 of file entangle.h.

Constructor & Destructor Documentation

template<class T, class Dual>

folly::pushmi::entangled< T, Dual >::entangled ( )

delete

Referenced by folly::pushmi::entangled< T, Dual >::unlockBoth().

template<class T, class Dual>

folly::pushmi::entangled< T, Dual >::entangled ( const entangled< T, Dual > &  )

delete

template<class T, class Dual>

folly::pushmi::entangled< T, Dual >::entangled ( T  t )

inlineexplicit

Definition at line 168 of file entangle.h.

      : stateMachine(kUnlocked), t(std::move(t)), dual(nullptr) {}

template<class T, class Dual>

folly::pushmi::entangled< T, Dual >::entangled ( entangled< T, Dual > &&  other )

inline

Definition at line 170 of file entangle.h.

References folly::pushmi::entangled< T, Dual >::dual, and folly::pushmi::entangled< T, Dual >::unlockBoth().

      : stateMachine((other.lockBoth(), kLocked)),
        t(std::move(other.t)),
        dual(std::move(other.dual)) {
    // Note that, above, we initialized stateMachine to the locked state; the
    // address of this object hasn't escaped yet, and won't (until we unlock
    // the dual), so it doesn't *really* matter, but it's conceptually helpful
    // to maintain that invariant.

    // Update our dual's data.
    if (dual != nullptr) {
      dual->dual = this;
    }

    // Update other's data.
    other.dual = nullptr;
    // unlock other so that its destructor can complete
    other.stateMachine.store(kUnlocked);

    // We locked on other, but will unlock on *this. The locking protocol
    // ensured that no accesses to other will occur after lock() returns, and
    // since then we updated dual's dual to be us.
    unlockBoth();
  }

template<class T, class Dual>

folly::pushmi::entangled< T, Dual >::~entangled ( )

inline

Definition at line 195 of file entangle.h.

References folly::pushmi::entangled< T, Dual >::dual, folly::pushmi::entangled< T, Dual >::lockBoth(), and folly::pushmi::entangled< T, Dual >::unlockBoth().

               {
    lockBoth();
    if (dual != nullptr) {
      dual->dual = nullptr;
    }
    unlockBoth();
  }

Member Function Documentation

template<class T, class Dual>

void folly::pushmi::entangled< T, Dual >::lockBoth ( )

inline

Definition at line 139 of file entangle.h.

References folly::pushmi::entangled< T, Dual >::tryLockBoth().

Referenced by folly::pushmi::locked_entangled_pair< T, Dual >::locked_entangled_pair(), folly::pushmi::entangled< T, Dual >::lockPointerToDual(), and folly::pushmi::entangled< T, Dual >::~entangled().

                  {
    while (!tryLockBoth()) {
      // Spin. But, note that all the unbounded spinning in tryLockBoth can be
      // straightforwardly futex-ified. There's a potentialy starvation issue
      // here, but note that it can be dealt with by adding a "priority" bit to
      // the state machine (i.e. if my priority bit is set, the thread for whom
      // I'm the local member of the pair gets to win the race, rather than
      // using address-ordering).
    }
  }

template<class T, class Dual>

Dual* folly::pushmi::entangled< T, Dual >::lockPointerToDual ( )

inline

Definition at line 204 of file entangle.h.

References folly::pushmi::entangled< T, Dual >::lockBoth(), and folly::pushmi::entangled< T, Dual >::t.

                            {
    lockBoth();
    return !!dual ? std::addressof(dual->t) : nullptr;
  }

template<class T, class Dual>

entangled& folly::pushmi::entangled< T, Dual >::operator= ( const entangled< T, Dual > &  )

delete

Referenced by folly::pushmi::locked_entangled_pair< T, Dual >::locked_entangled_pair(), and folly::pushmi::entangled< T, Dual >::unlockBoth().

template<class T, class Dual>

entangled& folly::pushmi::entangled< T, Dual >::operator= ( entangled< T, Dual > &&  )

delete

template<class T, class Dual>

bool folly::pushmi::entangled< T, Dual >::tryLockBoth ( )

inline

Definition at line 92 of file entangle.h.

References folly::pushmi::entangled< T, Dual >::kLockedAndLossAcknowledged, folly::pushmi::entangled< T, Dual >::kUnlocked, and folly::pushmi::entangled< T, Dual >::stateMachine.

Referenced by folly::pushmi::entangled< T, Dual >::lockBoth().

                     {
    // Try to acquire the local lock. We have to start locally, since local
    // addresses are the only ones we know are safe at first. The rule is, you
    // have to hold *both* locks to write any of either entangled object's
    // metadata, but need only one to read it.
    int expected = kUnlocked;
    if (!stateMachine.compare_exchange_weak(
            expected,
            kLocked,
            std::memory_order_seq_cst,
            std::memory_order_relaxed)) {
      return false;
    }
    // Having *either* object local-locked protects the data in both objects.
    // Once we hold our lock, no control data can change, in either object.
    if (dual == nullptr) {
      return true;
    }
    expected = kUnlocked;
    if (dual->stateMachine.compare_exchange_strong(
            expected, kLocked, std::memory_order_seq_cst)) {
      return true;
    }
    // We got here, and so hit the race; we're deadlocked if we stick to
    // locking. Revert to address-ordering. Note that address-ordering would
    // not be safe on its own, because of the lifetime issues involved; the
    // addresses here are only stable *because* we know both sides are locked,
    // and because of the invariant that you must hold both locks to modify
    // either piece of data.
    if ((uintptr_t)this < (uintptr_t)dual) {
      // I get to win the race. I'll acquire the locks, but have to make sure
      // my memory stays valid until the other thread acknowledges its loss.
      while (stateMachine.load(std::memory_order_relaxed) !=
             kLockedAndLossAcknowledged) {
        // Spin.
      }
      stateMachine.store(kLocked, std::memory_order_relaxed);
      return true;
    } else {
      // I lose the race, but have to coordinate with the winning thread, so
      // that it knows that I'm not about to try to touch it's data
      dual->stateMachine.store(
          kLockedAndLossAcknowledged, std::memory_order_relaxed);
      return false;
    }
  }

template<class T, class Dual>

void folly::pushmi::entangled< T, Dual >::unlockBoth ( )

inline

Definition at line 150 of file entangle.h.

References folly::pushmi::entangled< T, Dual >::entangled(), folly::pushmi::entangled< T, Dual >::operator=(), and folly::pushmi::entangled< T, Dual >::stateMachine.

Referenced by folly::pushmi::entangled< T, Dual >::entangled(), folly::pushmi::entangled< T, Dual >::unlockPointerToDual(), folly::pushmi::entangled< T, Dual >::~entangled(), and folly::pushmi::locked_entangled_pair< T, Dual >::~locked_entangled_pair().

                    {
    // Note that unlocking locally and then remotely is the right order. There
    // are no concurrent accesses to this object (as an API constraint -- lock
    // and unlock are not thread safe!), and no other thread will touch the
    // other object so long as its locked. Going in the other order could let
    // another thread incorrectly think we're going down the deadlock-avoidance
    // path in tryLock().
    stateMachine.store(kUnlocked, std::memory_order_release);
    if (dual != nullptr) {
      dual->stateMachine.store(kUnlocked, std::memory_order_release);
    }
  }

template<class T, class Dual>

void folly::pushmi::entangled< T, Dual >::unlockPointerToDual ( )

inline

Definition at line 209 of file entangle.h.

References folly::pushmi::entangled< T, Dual >::unlockBoth().

                             {
    unlockBoth();
  }

Member Data Documentation

template<class T, class Dual>

entangled<Dual, T>* folly::pushmi::entangled< T, Dual >::dual

Definition at line 79 of file entangle.h.

Referenced by folly::pushmi::entangle(), folly::pushmi::entangled< T, Dual >::entangled(), folly::pushmi::locked_entangled_pair< T, Dual >::locked_entangled_pair(), and folly::pushmi::entangled< T, Dual >::~entangled().

template<class T, class Dual>

const int folly::pushmi::entangled< T, Dual >::kLocked = 1

static

Definition at line 82 of file entangle.h.

template<class T, class Dual>

const int folly::pushmi::entangled< T, Dual >::kLockedAndLossAcknowledged = 2

static

Definition at line 83 of file entangle.h.

Referenced by folly::pushmi::entangled< T, Dual >::tryLockBoth().

template<class T, class Dual>

const int folly::pushmi::entangled< T, Dual >::kUnlocked = 0

static

Definition at line 81 of file entangle.h.

Referenced by folly::pushmi::entangled< T, Dual >::tryLockBoth().

template<class T, class Dual>

std::atomic<int> folly::pushmi::entangled< T, Dual >::stateMachine

Definition at line 74 of file entangle.h.

Referenced by folly::pushmi::entangled< T, Dual >::tryLockBoth(), and folly::pushmi::entangled< T, Dual >::unlockBoth().

template<class T, class Dual>

T folly::pushmi::entangled< T, Dual >::t

Definition at line 76 of file entangle.h.

Referenced by folly::pushmi::locked_entangled_pair< T, Dual >::locked_entangled_pair(), and folly::pushmi::entangled< T, Dual >::lockPointerToDual().

---

The documentation for this struct was generated from the following file:

• proxygen/folly/folly/experimental/pushmi/entangle.h