folly/PicoSpinLock.h

   1 /*
   2  * Copyright 2015-present 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 /*
  18  * N.B. You most likely do _not_ want to use PicoSpinLock or any other
  19  * kind of spinlock.  Consider MicroLock instead.
  20  *
  21  * In short, spinlocks in preemptive multi-tasking operating systems
  22  * have serious problems and fast mutexes like std::mutex are almost
  23  * certainly the better choice, because letting the OS scheduler put a
  24  * thread to sleep is better for system responsiveness and throughput
  25  * than wasting a timeslice repeatedly querying a lock held by a
  26  * thread that's blocked, and you can't prevent userspace
  27  * programs blocking.
  28  *
  29  * Spinlocks in an operating system kernel make much more sense than
  30  * they do in userspace.
  31  */
  32
  33 #pragma once
  34 #define FOLLY_PICO_SPIN_LOCK_H_
  35
  36 /*
  37  * @author Keith Adams <kma@fb.com>
  38  * @author Jordan DeLong <delong.j@fb.com>
  39  */
  40
  41 #include <array>
  42 #include <atomic>
  43 #include <cinttypes>
  44 #include <cstdlib>
  45 #include <mutex>
  46 #include <type_traits>
  47
  48 #include <glog/logging.h>
  49
  50 #include <folly/Portability.h>
  51 #include <folly/synchronization/detail/Sleeper.h>
  52
  53 #if !FOLLY_X64 && !FOLLY_AARCH64 && !FOLLY_PPC64
  54 #error "PicoSpinLock.h is currently x64, aarch64 and ppc64 only."
  55 #endif
  56
  57 namespace folly {
  58
  59 /*
  60  * Spin lock on a single bit in an integral type.  You can use this
  61  * with 16, 32, or 64-bit integral types.
  62  *
  63  * This is useful if you want a small lock and already have an int
  64  * with a bit in it that you aren't using.  But note that it can't be
  65  * as small as MicroSpinLock (1 byte), if you don't already have a
  66  * convenient int with an unused bit lying around to put it on.
  67  *
  68  * To construct these, either use init() or zero initialize.  We don't
  69  * have a real constructor because we want this to be a POD type so we
  70  * can put it into packed structs.
  71  */
  72 template <class IntType, int Bit = sizeof(IntType) * 8 - 1>
  73 struct PicoSpinLock {
  74   // Internally we deal with the unsigned version of the type.
  75   typedef typename std::make_unsigned<IntType>::type UIntType;
  76
  77   static_assert(std::is_integral<IntType>::value,
  78                 "PicoSpinLock needs an integral type");
  79   static_assert(sizeof(IntType) == 2 || sizeof(IntType) == 4 ||
  80                   sizeof(IntType) == 8,
  81                 "PicoSpinLock can't work on integers smaller than 2 bytes");
  82
  83  public:
  84   static const UIntType kLockBitMask_ = UIntType(1) << Bit;
  85   mutable UIntType lock_;
  86
  87   /*
  88    * You must call this function before using this class, if you
  89    * default constructed it.  If you zero-initialized it you can
  90    * assume the PicoSpinLock is in a valid unlocked state with
  91    * getData() == 0.
  92    *
  93    * (This doesn't use a constructor because we want to be a POD.)
  94    */
  95   void init(IntType initialValue = 0) {
  96     CHECK(!(initialValue & kLockBitMask_));
  97     reinterpret_cast<std::atomic<UIntType>*>(&lock_)->store(
  98         UIntType(initialValue), std::memory_order_release);
  99   }
 100
 101   /*
 102    * Returns the value of the integer we using for our lock, except
 103    * with the bit we are using as a lock cleared, regardless of
 104    * whether the lock is held.
 105    *
 106    * It is 'safe' to call this without holding the lock.  (As in: you
 107    * get the same guarantees for simultaneous accesses to an integer
 108    * as you normally get.)
 109    */
 110   IntType getData() const {
 111     auto res = reinterpret_cast<std::atomic<UIntType>*>(&lock_)->load(
 112                    std::memory_order_relaxed) &
 113         ~kLockBitMask_;
 114     return res;
 115   }
 116
 117   /*
 118    * Set the value of the other bits in our integer.
 119    *
 120    * Don't use this when you aren't holding the lock, unless it can be
 121    * guaranteed that no other threads may be trying to use this.
 122    */
 123   void setData(IntType w) {
 124     CHECK(!(w & kLockBitMask_));
 125     auto l = reinterpret_cast<std::atomic<UIntType>*>(&lock_);
 126     l->store(
 127         (l->load(std::memory_order_relaxed) & kLockBitMask_) | w,
 128         std::memory_order_relaxed);
 129   }
 130
 131   /*
 132    * Try to get the lock without blocking: returns whether or not we
 133    * got it.
 134    */
 135   bool try_lock() const {
 136     bool ret = false;
 137
 138 #if defined(FOLLY_SANITIZE_THREAD)
 139     // TODO: Might be able to fully move to std::atomic when gcc emits lock btr:
 140     // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=49244
 141     ret =
 142         !(reinterpret_cast<std::atomic<UIntType>*>(&lock_)->fetch_or(
 143               kLockBitMask_, std::memory_order_acquire) &
 144           kLockBitMask_);
 145 #elif _MSC_VER
 146     switch (sizeof(IntType)) {
 147       case 2:
 148         // There is no _interlockedbittestandset16 for some reason :(
 149         ret = _InterlockedOr16(
 150             (volatile short*)&lock_, (short)kLockBitMask_) & kLockBitMask_;
 151         break;
 152       case 4:
 153         ret = _interlockedbittestandset((volatile long*)&lock_, Bit);
 154         break;
 155       case 8:
 156         ret = _interlockedbittestandset64((volatile long long*)&lock_, Bit);
 157         break;
 158     }
 159 #elif FOLLY_X64
 160 #define FB_DOBTS(size)                                  \
 161   asm volatile("lock; bts" #size " %1, (%2); setnc %0"  \
 162                : "=r" (ret)                             \
 163                : "i" (Bit),                             \
 164                  "r" (&lock_)                           \
 165                : "memory", "flags")
 166
 167     switch (sizeof(IntType)) {
 168     case 2: FB_DOBTS(w); break;
 169     case 4: FB_DOBTS(l); break;
 170     case 8: FB_DOBTS(q); break;
 171     }
 172
 173 #undef FB_DOBTS
 174 #elif FOLLY_AARCH64
 175     using SIntType = typename std::make_signed<UIntType>::type;
 176     auto const lock = reinterpret_cast<SIntType*>(&lock_);
 177     auto const mask = static_cast<SIntType>(kLockBitMask_);
 178     return !(mask & __atomic_fetch_or(lock, mask, __ATOMIC_ACQUIRE));
 179 #elif FOLLY_PPC64
 180 #define FB_DOBTS(size)                                 \
 181     asm volatile("\teieio\n"                           \
 182                  "\tl" #size "arx 14,0,%[lockPtr]\n"   \
 183                  "\tli 15,1\n"                         \
 184                  "\tsldi 15,15,%[bit]\n"               \
 185                  "\tand. 16,15,14\n"                   \
 186                  "\tbne 0f\n"                          \
 187                  "\tor 14,14,15\n"                     \
 188                  "\tst" #size "cx. 14,0,%[lockPtr]\n"  \
 189                  "\tbne 0f\n"                          \
 190                  "\tori %[output],%[output],1\n"       \
 191                  "\tisync\n"                           \
 192                  "0:\n"                                \
 193                  : [output] "+r" (ret)                 \
 194                  : [lockPtr] "r"(&lock_),              \
 195                    [bit] "i" (Bit)                     \
 196                  : "cr0", "memory", "r14", "r15", "r16")
 197
 198     switch (sizeof(IntType)) {
 199     case 2: FB_DOBTS(h); break;
 200     case 4: FB_DOBTS(w); break;
 201     case 8: FB_DOBTS(d); break;
 202     }
 203
 204 #undef FB_DOBTS
 205 #else
 206 #error "x86 aarch64 ppc64 only"
 207 #endif
 208
 209     return ret;
 210   }
 211
 212   /*
 213    * Block until we can acquire the lock.  Uses Sleeper to wait.
 214    */
 215   void lock() const {
 216     detail::Sleeper sleeper;
 217     while (!try_lock()) {
 218       sleeper.wait();
 219     }
 220   }
 221
 222   /*
 223    * Release the lock, without changing the value of the rest of the
 224    * integer.
 225    */
 226   void unlock() const {
 227 #ifdef _MSC_VER
 228     switch (sizeof(IntType)) {
 229       case 2:
 230         // There is no _interlockedbittestandreset16 for some reason :(
 231         _InterlockedAnd16((volatile short*)&lock_, (short)~kLockBitMask_);
 232         break;
 233       case 4:
 234         _interlockedbittestandreset((volatile long*)&lock_, Bit);
 235         break;
 236       case 8:
 237         _interlockedbittestandreset64((volatile long long*)&lock_, Bit);
 238         break;
 239     }
 240 #elif FOLLY_X64
 241 #define FB_DOBTR(size)                          \
 242   asm volatile("lock; btr" #size " %0, (%1)"    \
 243                :                                \
 244                : "i" (Bit),                     \
 245                  "r" (&lock_)                   \
 246                : "memory", "flags")
 247
 248
 249     // Reads and writes can not be reordered wrt locked instructions,
 250     // so we don't need a memory fence here.
 251     switch (sizeof(IntType)) {
 252     case 2: FB_DOBTR(w); break;
 253     case 4: FB_DOBTR(l); break;
 254     case 8: FB_DOBTR(q); break;
 255     }
 256
 257 #undef FB_DOBTR
 258 #elif FOLLY_AARCH64
 259     using SIntType = typename std::make_signed<UIntType>::type;
 260     auto const lock = reinterpret_cast<SIntType*>(&lock_);
 261     auto const mask = static_cast<SIntType>(kLockBitMask_);
 262     __atomic_fetch_and(lock, ~mask, __ATOMIC_RELEASE);
 263 #elif FOLLY_PPC64
 264 #define FB_DOBTR(size)                                 \
 265     asm volatile("\teieio\n"                           \
 266                  "0:  l" #size "arx 14,0,%[lockPtr]\n" \
 267                  "\tli 15,1\n"                         \
 268                  "\tsldi 15,15,%[bit]\n"               \
 269                  "\txor 14,14,15\n"                    \
 270                  "\tst" #size "cx. 14,0,%[lockPtr]\n"  \
 271                  "\tbne 0b\n"                          \
 272                  "\tisync\n"                           \
 273                  :                                     \
 274                  : [lockPtr] "r"(&lock_),              \
 275                    [bit] "i" (Bit)                     \
 276                  : "cr0", "memory", "r14", "r15")
 277
 278     switch (sizeof(IntType)) {
 279     case 2: FB_DOBTR(h); break;
 280     case 4: FB_DOBTR(w); break;
 281     case 8: FB_DOBTR(d); break;
 282     }
 283
 284 #undef FB_DOBTR
 285 #else
 286 # error "x64 aarch64 ppc64 only"
 287 #endif
 288   }
 289 };
 290
 291 } // namespace folly