folly::MicroLockCore Class Reference

#include <MicroLock.h>

Inheritance diagram for folly::MicroLockCore:

Public Member Functions
void	unlock (unsigned slot)
void	unlock ()
void	init ()

Protected Member Functions
detail::Futex *	word () const
uint32_t	baseShift (unsigned slot) const
uint32_t	heldBit (unsigned slot) const
uint32_t	waitBit (unsigned slot) const

Static Protected Member Functions
static void	lockSlowPath (uint32_t oldWord, detail::Futex<> *wordPtr, uint32_t slotHeldBit, unsigned maxSpins, unsigned maxYields)

Protected Attributes
uint8_t	lock_

Detailed Description

Tiny exclusive lock that packs four lock slots into a single byte. Each slot is an independent real, sleeping lock. The default lock and unlock functions operate on slot zero, which modifies only the low two bits of the host byte.

You should zero-initialize the bits of a MicroLock that you intend to use.

If you're not space-constrained, prefer std::mutex, which will likely be faster, since it has more than two bits of information to work with.

You are free to put a MicroLock in a union with some other object. If, for example, you want to use the bottom two bits of a pointer as a lock, you can put a MicroLock in a union with the pointer and limit yourself to MicroLock slot zero, which will use the two least-significant bits in the bottom byte.

(Note that such a union is safe only because MicroLock is based on a character type, and even under a strict interpretation of C++'s aliasing rules, character types may alias anything.)

MicroLock uses a dirty trick: it actually operates on the full 32-bit, four-byte-aligned bit of memory into which it is embedded. It never modifies bits outside the ones it's defined to modify, but it accesses all the bits in the 32-bit memory location for purposes of futex management.

The MaxSpins template parameter controls the number of times we spin trying to acquire the lock. MaxYields controls the number of times we call sched_yield; once we've tried to acquire the lock MaxSpins + MaxYields times, we sleep on the lock futex. By adjusting these parameters, you can make MicroLock behave as much or as little like a conventional spinlock as you'd like.

Performance

With the default template options, the timings for uncontended acquire-then-release come out as follows on Intel(R) Xeon(R) CPU E5-2660 0 @ 2.20GHz, in /opt, as of the master tree at Tue, 01 Mar 2016 19:48:15.

---

folly/test/SmallLocksBenchmark.cpp relative time/iter iters/s

MicroSpinLockUncontendedBenchmark 13.46ns 74.28M PicoSpinLockUncontendedBenchmark 14.99ns 66.71M MicroLockUncontendedBenchmark 27.06ns 36.96M StdMutexUncontendedBenchmark 25.18ns 39.72M

VirtualFunctionCall 1.72ns 579.78M

(The virtual dispatch benchmark is provided for scale.)

While the uncontended case for MicroLock is competitive with the glibc 2.2.0 implementation of std::mutex, std::mutex is likely to be faster in the contended case, because we need to wake up all waiters when we release.

Make sure to benchmark your particular workload.

Definition at line 99 of file MicroLock.h.

Member Function Documentation

unsigned folly::MicroLockCore::baseShift ( unsigned  slot ) const

inlineprotected

Definition at line 135 of file MicroLock.h.

References folly::kIsLittleEndian, lock_, uint32_t, and word().

Referenced by heldBit(), and waitBit().

                                                            {
  assert(slot < CHAR_BIT / 2);

  unsigned offset_bytes = (unsigned)((uintptr_t)&lock_ - (uintptr_t)word());

  return (
      unsigned)(kIsLittleEndian ? offset_bytes * CHAR_BIT + slot * 2 : CHAR_BIT * (sizeof(uint32_t) - offset_bytes - 1) + slot * 2);
}

uint32_t folly::MicroLockCore::heldBit ( unsigned  slot ) const

inlineprotected

Definition at line 144 of file MicroLock.h.

References baseShift().

Referenced by folly::MicroLockBase< MaxSpins, MaxYields >::lock(), folly::MicroLockBase< MaxSpins, MaxYields >::try_lock(), and unlock().

                                                          {
  return 1U << (baseShift(slot) + 0);
}

void folly::MicroLockCore::init ( )

inline

Definition at line 124 of file MicroLock.h.

                     {
    lock_ = 0;
  }

void folly::MicroLockCore::lockSlowPath ( uint32_t  oldWord, detail::Futex<> *  wordPtr, uint32_t  slotHeldBit, unsigned  maxSpins, unsigned  maxYields  )

staticprotected

Definition at line 24 of file MicroLock.cpp.

References folly::asm_volatile_pause(), folly::detail::futexWait(), retry, uint32_t, and folly::fibers::yield().

Referenced by folly::MicroLockBase< MaxSpins, MaxYields >::lock().

                        {
  uint32_t newWord;
  unsigned spins = 0;
  uint32_t slotWaitBit = slotHeldBit << 1;
  uint32_t needWaitBit = 0;

retry:
  if ((oldWord & slotHeldBit) != 0) {
    ++spins;
    if (spins > maxSpins + maxYields) {
      // Somebody appears to have the lock.  Block waiting for the
      // holder to unlock the lock.  We set heldbit(slot) so that the
      // lock holder knows to FUTEX_WAKE us.
      newWord = oldWord | slotWaitBit;
      if (newWord != oldWord) {
        if (!wordPtr->compare_exchange_weak(
                oldWord,
                newWord,
                std::memory_order_relaxed,
                std::memory_order_relaxed)) {
          goto retry;
        }
      }
      detail::futexWait(wordPtr, newWord, slotHeldBit);
      needWaitBit = slotWaitBit;
    } else if (spins > maxSpins) {
      // sched_yield(), but more portable
      std::this_thread::yield();
    } else {
      folly::asm_volatile_pause();
    }
    oldWord = wordPtr->load(std::memory_order_relaxed);
    goto retry;
  }

  newWord = oldWord | slotHeldBit | needWaitBit;
  if (!wordPtr->compare_exchange_weak(
          oldWord,
          newWord,
          std::memory_order_acquire,
          std::memory_order_relaxed)) {
    goto retry;
  }
}

void folly::MicroLockCore::unlock ( unsigned  slot )

inline

Definition at line 152 of file MicroLock.h.

References folly::detail::futexWake(), heldBit(), uint32_t, waitBit(), and word().

                                        {
  detail::Futex<>* wordPtr = word();
  uint32_t oldWord;
  uint32_t newWord;

  oldWord = wordPtr->load(std::memory_order_relaxed);
  do {
    assert(oldWord & heldBit(slot));
    newWord = oldWord & ~(heldBit(slot) | waitBit(slot));
  } while (!wordPtr->compare_exchange_weak(
      oldWord, newWord, std::memory_order_release, std::memory_order_relaxed));

  if (oldWord & waitBit(slot)) {
    detail::futexWake(wordPtr, 1, heldBit(slot));
  }
}

void folly::MicroLockCore::unlock ( )

inline

Definition at line 120 of file MicroLock.h.

                       {
    unlock(0);
  }

uint32_t folly::MicroLockCore::waitBit ( unsigned  slot ) const

inlineprotected

Definition at line 148 of file MicroLock.h.

References baseShift().

Referenced by folly::MicroLockBase< MaxSpins, MaxYields >::lock(), and unlock().

                                                          {
  return 1U << (baseShift(slot) + 1);
}

detail::Futex * folly::MicroLockCore::word ( ) const

inlineprotected

Definition at line 129 of file MicroLock.h.

References lock_, and uint32_t.

Referenced by baseShift(), folly::MicroLockBase< MaxSpins, MaxYields >::lock(), folly::MicroLockBase< MaxSpins, MaxYields >::try_lock(), and unlock().

                                                {
  uintptr_t lockptr = (uintptr_t)&lock_;
  lockptr &= ~(sizeof(uint32_t) - 1);
  return (detail::Futex<>*)lockptr;
}

Member Data Documentation

uint8_t folly::MicroLockCore::lock_

protected

Definition at line 105 of file MicroLock.h.

Referenced by baseShift(), and word().

---

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

• proxygen/folly/folly/MicroLock.h
• proxygen/folly/folly/MicroLock.cpp