proxygen: folly::detail::distributed_mutex::DistributedMutex< Atomic, TimePublishing

#include <DistributedMutex.h>

Classes
class	DistributedMutexStateProxy

Public Member Functions
	DistributedMutex ()

	DistributedMutex (DistributedMutex &&)=delete

	DistributedMutex (const DistributedMutex &)=delete

DistributedMutex &	operator= (DistributedMutex &&)=delete

DistributedMutex &	operator= (const DistributedMutex &)=delete

DistributedMutexStateProxy	lock ()

void	unlock (DistributedMutexStateProxy)

DistributedMutexStateProxy	try_lock ()

template<typename Rep , typename Period >
DistributedMutexStateProxy	try_lock_for (const std::chrono::duration< Rep, Period > &duration)

template<typename Clock , typename Duration >
DistributedMutexStateProxy	try_lock_until (const std::chrono::time_point< Clock, Duration > &deadline)

Private Attributes
Atomic< std::uintptr_t >	state_ {0}

Detailed Description

template<template< typename > class Atomic = std::atomic, bool TimePublishing = true>
class folly::detail::distributed_mutex::DistributedMutex< Atomic, TimePublishing >

DistributedMutex is a small, exclusive-only mutex that distributes the bookkeeping required for mutual exclusion in the stacks of threads that are contending for it. It tries to come at a lower space cost than std::mutex while still trying to maintain the fairness benefits that come from using std::mutex. DistributedMutex provides the entire API included in std::mutex, and more, with slight modifications. DistributedMutex is the same width as a single pointer (8 bytes on most platforms), where on the other hand, std::mutex and pthread_mutex_t are both 40 bytes. It is larger than some of the other smaller locks, but the wide majority of cases using the small locks are wasting the difference in alignment padding anyway

Benchmark results are good - at the time of writing in the common uncontended case, it is 30% faster than some of the other small mutexes in folly and as fast as std::mutex, which recently optimized its uncontended path. In the contended case, it is about 4-5x faster than some of the smaller locks in folly, ~2x faster than std::mutex in clang and ~1.8x faster in gcc. DistributedMutex is also resistent to tail latency pathalogies unlike many of the other small mutexes. Which sleep for large time quantums to reduce spin churn, this causes elevated latencies for threads that enter the sleep cycle. The tail latency of lock acquisition on average up to 10x better with DistributedMutex

DistributedMutex reduces cache line contention by making each thread wait on a thread local spinlock and futex. This allows threads to keep working only on their own cache lines without requiring cache coherence operations when a mutex heavy contention. This strategy does not require sequential ordering on the centralized atomic storage for wakeup operations as each thread assigned its own wait state

Non-timed mutex acquisitions are scheduled through intrusive LIFO contention chains. Each thread starts by spinning for a short quantum and falls back to two phased sleeping. Enqueue operations are lock free and are piggybacked off mutex acquisition attempts. The LIFO behavior of a contention chain is good in the case where the mutex is held for a short amount of time, as the head of the chain is likely to not have slept on futex() after exhausting its spin quantum. This allow us to avoid unnecessary traversal and syscalls in the fast path with a higher probability. Even though the contention chains are LIFO, the mutex itself does not adhere to that scheduling policy globally. During contention, threads that fail to lock the mutex form a LIFO chain on the central mutex state, this chain is broken when a wakeup is scheduled, and future enqueue operations form a new chain. This makes the chains themselves LIFO, but preserves global fairness through a constant factor which is limited to the number of concurrent failed mutex acquisition attempts. This binds the last in first out behavior to the number of contending threads and helps prevent starvation and latency outliers

This strategy of waking up wakers one by one in a queue does not scale well when the number of threads goes past the number of cores. At which point preemption causes elevated lock acquisition latencies. DistributedMutex implements a hardware timestamp publishing heuristic to detect and adapt to preemption.

DistributedMutex does not have the typical mutex API - it does not satisfy the Lockable concept. It requires the user to maintain ephemeral bookkeeping and pass that bookkeeping around to unlock() calls. The API overhead, however, comes for free when you wrap this mutex for usage with folly::Synchronized or std::unique_lock, which is the recommended usage (std::lock_guard, in optimized mode, has no performance benefit over std::unique_lock, so has been omitted). A benefit of this API is that it disallows incorrect usage where a thread unlocks a mutex that it does not own, thinking a mutex is functionally identical to a binary semaphore, which, unlike a mutex, is a suitable primitive for that usage

Timed locking through DistributedMutex is implemented through a centralized algorithm - all waiters wait on the central mutex state, by setting and resetting bits within the pointer-length word. Since pointer length atomic integers are incompatible with futex(FUTEX_WAIT) on most systems, a non-standard implementation of futex() is used, where wait queues are managed in user-space. See p1135r0 and folly::ParkingLot

Definition at line 101 of file DistributedMutex.h.

Constructor & Destructor Documentation

template<template< typename > class Atomic, bool TimePublishing>

folly::detail::distributed_mutex::DistributedMutex< Atomic, TimePublishing >::DistributedMutex ( )

DistributedMutex is only default constructible, it can neither be moved nor copied

Definition at line 305 of file DistributedMutex-inl.h.

306 : state_{kUnlocked} {}

folly::detail::distributed_mutex::kUnlocked

constexpr auto kUnlocked

Definition: DistributedMutex-inl.h:47

folly::detail::distributed_mutex::DistributedMutex::state_

Atomic< std::uintptr_t > state_

Definition: DistributedMutex.h:177

template<template< typename > class Atomic = std::atomic, bool TimePublishing = true>

folly::detail::distributed_mutex::DistributedMutex< Atomic, TimePublishing >::DistributedMutex ( DistributedMutex< Atomic, TimePublishing > && )

delete

template<template< typename > class Atomic = std::atomic, bool TimePublishing = true>

folly::detail::distributed_mutex::DistributedMutex< Atomic, TimePublishing >::DistributedMutex ( const DistributedMutex< Atomic, TimePublishing > & )

delete

Member Function Documentation

template<template< typename > class Atomic, bool TimePublishing>

DistributedMutex< Atomic, TimePublishing >::DistributedMutexStateProxy folly::detail::distributed_mutex::DistributedMutex< Atomic, TimePublishing >::lock ( )

Acquires the mutex in exclusive mode

This returns an ephemeral proxy that contains internal mutex state. This must be kept around for the duration of the critical section and passed subsequently to unlock() as an rvalue

The proxy has no public API and is intended to be for internal usage only

This is not a recursive mutex - trying to acquire the mutex twice from the same thread without unlocking it results in undefined behavior

Definition at line 455 of file DistributedMutex-inl.h.

Referenced by burn().

                                                {
   // first try and acquire the lock as a fast path, the underlying
   // implementation is slightly faster than using std::atomic::exchange() as
   // is used in this function.  So we get a small perf boost in the
   // uncontended case
   if (auto state = try_lock()) {
     return state;
   }
 
   auto previous = std::uintptr_t{0};
   auto waitMode = kUninitialized;
   auto nextWaitMode = kAboutToWait;
   auto timedWaiter = false;
   CachelinePadded<Waiter<Atomic>>* nextSleeper = nullptr;
   while (true) {
     // construct the state needed to wait
     auto&& state = CachelinePadded<Waiter<Atomic>>{waitMode};
     auto&& address = reinterpret_cast<std::uintptr_t>(&state);
     DCHECK(!(address & 0b1));
 
     // set the locked bit in the address we will be persisting in the mutex
     address |= kLocked;
 
     // attempt to acquire the mutex, mutex acquisition is successful if the
     // previous value is zeroed out
     //
     // we use memory_order_acq_rel here because we want the read-modify-write
     // operation to be both acquire and release.  Acquire becasue if this is a
     // successful lock acquisition, we want to acquire state any other thread
     // has released from a prior unlock.  We want release semantics becasue
     // other threads that read the address of this value should see the full
     // well-initialized node we are going to wait on if the mutex acquisition
     // was unsuccessful
     previous = state_.exchange(address, std::memory_order_acq_rel);
     recordTimedWaiterAndClearTimedBit(timedWaiter, previous);
     state->next_ = previous;
     if (previous == kUnlocked) {
       return {nullptr, address, timedWaiter, {}, nullptr, nextSleeper};
     }
     DCHECK(previous & kLocked);
 
     // wait until we get a signal from another thread, if this returns false,
     // we got skipped and had probably been scheduled out, so try again
     if (!wait(&state, (waitMode == kAboutToWait), nextSleeper)) {
       std::swap(waitMode, nextWaitMode);
       continue;
     }
 
     // at this point it is safe to access the other fields in the waiter state,
     // since the thread that woke us up is gone and nobody will be touching this
     // state again, note that this requires memory ordering, and this is why we
     // use memory_order_acquire (among other reasons) in the above wait
     //
     // first we see if the value we took off the mutex state was the thread that
     // initated the wakeups, if so, we are the terminal node of the current
     // contention chain.  If we are the terminal node, then we should expect to
     // see a kLocked in the mutex state when we unlock, if we see that, we can
     // commit the unlock to the centralized mutex state.  If not, we need to
     // continue wakeups
     //
     // a nice consequence of passing kLocked as the current address if we are
     // the terminal node is that it naturally just works with the algorithm.  If
     // we get a contention chain when coming out of a contention chain, the tail
     // of the new contention chain will have kLocked set as the previous, which,
     // as it happens "just works", since we have now established a recursive
     // relationship until broken
     auto next = previous;
     auto expected = address;
     if (previous == state->wakerMetadata_.waker_) {
       next = 0;
       expected = kLocked;
     }
 
     // if we are just coming out of a futex call, then it means that the next
     // waiter we are responsible for is also a waiter waiting on a futex, so
     // we return that list in the list of ready threads.  We wlil be waking up
     // the ready threads on unlock no matter what
     return {extractAddress<CachelinePadded<Waiter<Atomic>>>(next),
             expected,
             timedWaiter,
             state->wakerMetadata_,
             extractAddress<CachelinePadded<Waiter<Atomic>>>(state->waiters_),
             nextSleeper};
   }
 }

template<template< typename > class Atomic = std::atomic, bool TimePublishing = true>

DistributedMutex& folly::detail::distributed_mutex::DistributedMutex< Atomic, TimePublishing >::operator= ( DistributedMutex< Atomic, TimePublishing > && )

delete

template<template< typename > class Atomic = std::atomic, bool TimePublishing = true>

DistributedMutex& folly::detail::distributed_mutex::DistributedMutex< Atomic, TimePublishing >::operator= ( const DistributedMutex< Atomic, TimePublishing > & )

delete

template<template< typename > class Atomic, bool TimePublishing>

DistributedMutex< Atomic, TimePublishing >::DistributedMutexStateProxy folly::detail::distributed_mutex::DistributedMutex< Atomic, TimePublishing >::try_lock ( )

Try to acquire the mutex

A non blocking version of the lock() function. The returned object is contextually convertible to bool. And has the value true when the mutex was successfully acquired, false otherwise

This is allowed to return false spuriously, i.e. this is not guaranteed to return true even when the mutex is currently unlocked. In the event of a failed acquisition, this does not impose any memory ordering constraints for other threads

Definition at line 766 of file DistributedMutex-inl.h.

References folly::atomic_fetch_set(), and folly::detail::distributed_mutex::DistributedMutex< Atomic, TimePublishing >::state_.

                                                    {
   // Try and set the least significant bit of the centralized lock state to 1,
   // indicating locked.
   //
   // If this succeeds, it must have been the case that we had a kUnlocked (or
   // 0) in the centralized storage before, since that is the only case where a
   // 0 can be found.  So we assert that in debug mode
   //
   // If this fails, then it is a no-op
   auto previous = atomic_fetch_set(state_, 0, std::memory_order_acquire);
   if (!previous) {
     return {nullptr, kLocked};
   }
 
   return {nullptr, 0};
 }

template<template< typename > class Atomic, bool TimePublishing>

template<typename Rep , typename Period >

DistributedMutex< Atomic, TimePublishing >::DistributedMutexStateProxy folly::detail::distributed_mutex::DistributedMutex< Atomic, TimePublishing >::try_lock_for ( const std::chrono::duration< Rep, Period > & duration )

Try to acquire the mutex, blocking for the given time

Like try_lock(), this is allowed to fail spuriously and is not guaranteed to return false even when the mutex is currently unlocked. But only after the given time has elapsed

try_lock_for() accepts a duration to block for, and try_lock_until() accepts an absolute wall clock time point

Definition at line 870 of file DistributedMutex-inl.h.

References folly::gen::as(), now(), folly::detail::distributed_mutex::DistributedMutex< Atomic, TimePublishing >::state_, folly::detail::distributed_mutex::timedLock(), and folly::detail::distributed_mutex::DistributedMutex< Atomic, TimePublishing >::try_lock().

                                                     {
   // fast path for the uncontended case.  Reasoning for doing this here is the
   // same as in try_lock_until()
   if (auto state = try_lock()) {
     return state;
   }
 
   // fall back to the timed locking algorithm
   using Proxy = DistributedMutexStateProxy;
   auto deadline = std::chrono::steady_clock::now() + duration;
   return timedLock(state_, deadline, [](auto... as) { return Proxy{as...}; });
 }

template<template< typename > class Atomic, bool TimePublishing>

template<typename Clock , typename Duration >

DistributedMutex< Atomic, TimePublishing >::DistributedMutexStateProxy folly::detail::distributed_mutex::DistributedMutex< Atomic, TimePublishing >::try_lock_until ( const std::chrono::time_point< Clock, Duration > & deadline )

Try to acquire the lock, blocking until the given deadline

Other than the difference in the meaning of the second argument, the semantics of this function are identical to try_lock_for()

Definition at line 847 of file DistributedMutex-inl.h.

References folly::gen::as(), folly::detail::distributed_mutex::DistributedMutex< Atomic, TimePublishing >::state_, folly::detail::distributed_mutex::timedLock(), and folly::detail::distributed_mutex::DistributedMutex< Atomic, TimePublishing >::try_lock().

                                                           {
   // fast path for the uncontended case
   //
   // we get the time after trying to acquire the mutex because in the
   // uncontended case, the price of getting the time is about 1/3 of the
   // actual mutex acquisition.  So we only pay the price of that extra bit of
   // latency when needed
   //
   // this is even higher when VDSO is involved on architectures that do not
   // offer a direct interface to the timestamp counter
   if (auto state = try_lock()) {
     return state;
   }
 
   // fall back to the timed locking algorithm
   using Proxy = DistributedMutexStateProxy;
   return timedLock(state_, deadline, [](auto... as) { return Proxy{as...}; });
 }

template<template< typename > class Atomic, bool Publish>

void folly::detail::distributed_mutex::DistributedMutex< Atomic, Publish >::unlock ( DistributedMutex< Atomic, TimePublishing >::DistributedMutexStateProxy proxy )

Unlocks the mutex

The proxy returned by lock must be passed to unlock as an rvalue. No other option is possible here, since the proxy is only movable and not copyable

Definition at line 705 of file DistributedMutex-inl.h.

Referenced by burn().

                                                       {
   // we always wake up ready threads and timed waiters if we saw either
   DCHECK(proxy) << "Invalid proxy passed to DistributedMutex::unlock()";
   SCOPE_EXIT {
     doFutexWake(proxy.ready_);
     wakeTimedWaiters(&state_, proxy.timedWaiters_);
   };
 
   // if there is a wait queue we are responsible for, try and start wakeups,
   // don't bother with the mutex state
   auto sleepers = proxy.waiters_;
   if (proxy.next_) {
     if (wake(Publish, *proxy.next_, proxy.wakerMetadata_, sleepers)) {
       return;
     }
 
     // At this point, if are in the if statement, we were not the terminal
     // node of the wakeup chain.  Terminal nodes have the next_ pointer set to
     // null in lock()
     //
     // So we need to pretend we were the end of the contention chain.  Coming
     // out of a contention chain always has the kLocked state set in the
     // mutex.  Unless there is another contention chain lined up, which does
     // not matter since we are the terminal node anyway
     proxy.expected_ = kLocked;
   }
 
   while (true) {
     // otherwise, since we don't have anyone we need to wake up, we try and
     // release the mutex just as is
     //
     // if this is successful, we can return, the unlock was successful, we have
     // committed a nice kUnlocked to the central storage, yay
     if (tryUnlockClean(state_, proxy, sleepers)) {
       return;
     }
 
     // here we have a contention chain built up on the mutex.  We grab the
     // wait queue and start executing wakeups.  We leave a locked bit on the
     // centralized storage and handoff control to the head of the queue
     //
     // we use memory_order_acq_rel here because we want to see the
     // full well-initialized node that the other thread is waiting on
     //
     // If we are unable to wake the contention chain, it is possible that when
     // we come back to looping here, a new contention chain will form.  In
     // that case we need to use kLocked as the waker_ value because the
     // terminal node of the new chain will see kLocked in the central storage
     auto head = state_.exchange(kLocked, std::memory_order_acq_rel);
     recordTimedWaiterAndClearTimedBit(proxy.timedWaiters_, head);
     auto next = extractAddress<CachelinePadded<Waiter<Atomic>>>(head);
     DCHECK((head & kLocked) && (head != kLocked)) << "incorrect state " << head;
     if (wake(Publish, *next, {exchange(proxy.expected_, kLocked)}, sleepers)) {
       break;
     }
   }
 }

Member Data Documentation

template<template< typename > class Atomic = std::atomic, bool TimePublishing = true>

Atomic<std::uintptr_t> folly::detail::distributed_mutex::DistributedMutex< Atomic, TimePublishing >::state_ {0}

private

Definition at line 177 of file DistributedMutex.h.

Referenced by folly::detail::distributed_mutex::DistributedMutex< Atomic, TimePublishing >::lock(), folly::detail::distributed_mutex::DistributedMutex< Atomic, TimePublishing >::try_lock(), folly::detail::distributed_mutex::DistributedMutex< Atomic, TimePublishing >::try_lock_for(), folly::detail::distributed_mutex::DistributedMutex< Atomic, TimePublishing >::try_lock_until(), and folly::detail::distributed_mutex::DistributedMutex< Atomic, TimePublishing >::unlock().

The documentation for this class was generated from the following files:

proxygen/folly/folly/synchronization/DistributedMutex.h
proxygen/folly/folly/synchronization/DistributedMutex-inl.h

Classes

Public Member Functions

Private Attributes

Detailed Description

template<template< typename > class Atomic = std::atomic, bool TimePublishing = true> class folly::detail::distributed_mutex::DistributedMutex< Atomic, TimePublishing >

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<template< typename > class Atomic = std::atomic, bool TimePublishing = true>
class folly::detail::distributed_mutex::DistributedMutex< Atomic, TimePublishing >