folly/MicroLock.h

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