folly/MicroLock.h

   1 /*
   2  * Copyright 2016 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #pragma once
  18
  19 #include <assert.h>
  20 #include <climits>
  21 #include <stdint.h>
  22 #include <folly/detail/Futex.h>
  23 #include <folly/Portability.h>
  24
  25 namespace folly {
  26
  27 /**
  28  * Tiny exclusive lock that packs four lock slots into a single
  29  * byte. Each slot is an independent real, sleeping lock.  The default
  30  * lock and unlock functions operate on slot zero, which modifies only
  31  * the low two bits of the host byte.
  32  *
  33  * You should zero-initialize the bits of a MicroLock that you intend
  34  * to use.
  35  *
  36  * If you're not space-constrained, prefer std::mutex, which will
  37  * likely be faster, since it has more than two bits of information to
  38  * work with.
  39  *
  40  * You are free to put a MicroLock in a union with some other object.
  41  * If, for example, you want to use the bottom two bits of a pointer
  42  * as a lock, you can put a MicroLock in a union with the pointer and
  43  * limit yourself to MicroLock slot zero, which will use the two
  44  * least-significant bits in the bottom byte.
  45  *
  46  * MicroLock uses a dirty trick: it actually operates on the full
  47  * word-size, word-aligned bit of memory into which it is embedded.
  48  * It never modifies bits outside the ones it's defined to modify, but
  49  * it _accesses_ all the bits in the word for purposes of
  50  * futex management.
  51  *
  52  * The MaxSpins template parameter controls the number of times we
  53  * spin trying to acquire the lock.  MaxYields controls the number of
  54  * times we call sched_yield; once we've tried to acquire the lock
  55  * MaxSpins + MaxYields times, we sleep on the lock futex.
  56  * By adjusting these parameters, you can make MicroLock behave as
  57  * much or as little like a conventional spinlock as you'd like.
  58  *
  59  * Performance
  60  * -----------
  61  *
  62  * With the default template options, the timings for uncontended
  63  * acquire-then-release come out as follows on Intel(R) Xeon(R) CPU
  64  * E5-2660 0 @ 2.20GHz, in @mode/opt, as of the master tree at Tue, 01
  65  * Mar 2016 19:48:15.
  66  *
  67  * ========================================================================
  68  * folly/test/SmallLocksBenchmark.cpp          relative  time/iter  iters/s
  69  * ========================================================================
  70  * MicroSpinLockUncontendedBenchmark                       13.46ns   74.28M
  71  * PicoSpinLockUncontendedBenchmark                        14.99ns   66.71M
  72  * MicroLockUncontendedBenchmark                           27.06ns   36.96M
  73  * StdMutexUncontendedBenchmark                            25.18ns   39.72M
  74  * VirtualFunctionCall                                      1.72ns  579.78M
  75  * ========================================================================
  76  *
  77  * (The virtual dispatch benchmark is provided for scale.)
  78  *
  79  * The contended case for MicroLock is likely to be worse compared to
  80  * std::mutex than the contended case is.  Make sure to benchmark your
  81  * particular workload.
  82  *
  83  */
  84
  85 class MicroLockCore {
  86  protected:
  87   uint8_t lock_;
  88   inline detail::Futex<>* word() const;
  89   inline uint32_t baseShift(unsigned slot) const;
  90   inline uint32_t heldBit(unsigned slot) const;
  91   inline uint32_t waitBit(unsigned slot) const;
  92   static void lockSlowPath(uint32_t oldWord,
  93                            detail::Futex<>* wordPtr,
  94                            uint32_t slotHeldBit,
  95                            unsigned maxSpins,
  96                            unsigned maxYields);
  97
  98  public:
  99   inline void unlock(unsigned slot);
 100   inline void unlock() { unlock(0); }
 101   inline void init(unsigned slot) { lock_ &= ~(3U << (2 * slot)); }
 102   inline void init() { init(0); }
 103 };
 104
 105 inline detail::Futex<>* MicroLockCore::word() const {
 106   uintptr_t lockptr = (uintptr_t)&lock_;
 107   lockptr &= ~(sizeof(uint32_t) - 1);
 108   return (detail::Futex<>*)lockptr;
 109 }
 110
 111 inline unsigned MicroLockCore::baseShift(unsigned slot) const {
 112   assert(slot < CHAR_BIT / 2);
 113
 114   unsigned offset_bytes = (unsigned)((uintptr_t)&lock_ - (uintptr_t)word());
 115
 116   return kIsLittleEndian
 117              ? offset_bytes * CHAR_BIT + slot * 2
 118              : CHAR_BIT * (sizeof(uint32_t) - offset_bytes - 1) + slot * 2;
 119 }
 120
 121 inline uint32_t MicroLockCore::heldBit(unsigned slot) const {
 122   return 1U << (baseShift(slot) + 0);
 123 }
 124
 125 inline uint32_t MicroLockCore::waitBit(unsigned slot) const {
 126   return 1U << (baseShift(slot) + 1);
 127 }
 128
 129 void MicroLockCore::unlock(unsigned slot) {
 130   detail::Futex<>* wordPtr = word();
 131   uint32_t oldWord;
 132   uint32_t newWord;
 133
 134   oldWord = wordPtr->load(std::memory_order_relaxed);
 135   do {
 136     assert(oldWord & heldBit(slot));
 137     newWord = oldWord & ~(heldBit(slot) | waitBit(slot));
 138   } while (!wordPtr->compare_exchange_weak(
 139       oldWord, newWord, std::memory_order_release, std::memory_order_relaxed));
 140
 141   if (oldWord & waitBit(slot)) {
 142     // We don't track the number of waiters, so wake everyone
 143     (void)wordPtr->futexWake(std::numeric_limits<int>::max(), heldBit(slot));
 144   }
 145 }
 146
 147 template <unsigned MaxSpins = 1000, unsigned MaxYields = 0>
 148 class MicroLockBase : public MicroLockCore {
 149  public:
 150   inline void lock(unsigned slot);
 151   inline void lock() { lock(0); }
 152   inline bool try_lock(unsigned slot);
 153   inline bool try_lock() { return try_lock(0); }
 154 };
 155
 156 template <unsigned MaxSpins, unsigned MaxYields>
 157 bool MicroLockBase<MaxSpins, MaxYields>::try_lock(unsigned slot) {
 158
 159   // N.B. You might think that try_lock is just the fast path of lock,
 160   // but you'd be wrong.  Keep in mind that other parts of our host
 161   // word might be changing while we take the lock!  We're not allowed
 162   // to fail spuriously if the lock is in fact not held, even if other
 163   // people are concurrently modifying other parts of the word.
 164   //
 165   // We need to loop until we either see firm evidence that somebody
 166   // else has the lock (by looking at heldBit) or see our CAS succeed.
 167   // A failed CAS by itself does not indicate lock-acquire failure.
 168
 169   detail::Futex<>* wordPtr = word();
 170   uint32_t oldWord = wordPtr->load(std::memory_order_relaxed);
 171   do {
 172     if (oldWord & heldBit(slot)) {
 173       return false;
 174     }
 175   } while (!wordPtr->compare_exchange_weak(oldWord,
 176                                            oldWord | heldBit(slot),
 177                                            std::memory_order_acquire,
 178                                            std::memory_order_relaxed));
 179
 180   return true;
 181 }
 182
 183 template <unsigned MaxSpins, unsigned MaxYields>
 184 void MicroLockBase<MaxSpins, MaxYields>::lock(unsigned slot) {
 185
 186   static_assert(MaxSpins + MaxYields < (unsigned)-1, "overflow");
 187
 188   detail::Futex<>* wordPtr = word();
 189   uint32_t oldWord;
 190   oldWord = wordPtr->load(std::memory_order_relaxed);
 191   if ((oldWord & heldBit(slot)) == 0 &&
 192       wordPtr->compare_exchange_weak(oldWord,
 193                                      oldWord | heldBit(slot),
 194                                      std::memory_order_acquire,
 195                                      std::memory_order_relaxed)) {
 196     // Fast uncontended case: seq_cst above is our memory barrier
 197   } else {
 198     // lockSlowPath doesn't have any slot-dependent computation; it
 199     // just shifts the input bit.  Make sure its shifting produces the
 200     // same result a call to waitBit for our slot would.
 201     assert(heldBit(slot) << 1 == waitBit(slot));
 202     // lockSlowPath emits its own memory barrier
 203     lockSlowPath(oldWord, wordPtr, heldBit(slot), MaxSpins, MaxYields);
 204   }
 205 }
 206
 207 typedef MicroLockBase<> MicroLock;
 208 }