folly/PicoSpinLock.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 /*
  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
  35 /*
  36  * @author Keith Adams <kma@fb.com>
  37  * @author Jordan DeLong <delong.j@fb.com>
  38  */
  39
  40 #include <array>
  41 #include <cinttypes>
  42 #include <type_traits>
  43 #include <cstdlib>
  44 #include <pthread.h>
  45 #include <mutex>
  46 #include <atomic>
  47
  48 #include <glog/logging.h>
  49 #include <folly/detail/Sleeper.h>
  50 #include <folly/Portability.h>
  51
  52 #if !FOLLY_X64 && !FOLLY_A64 && !FOLLY_PPC64
  53 # error "PicoSpinLock.h is currently x64, aarch64 and ppc64 only."
  54 #endif
  55
  56 namespace folly {
  57
  58 /*
  59  * Spin lock on a single bit in an integral type.  You can use this
  60  * with 16, 32, or 64-bit integral types.
  61  *
  62  * This is useful if you want a small lock and already have an int
  63  * with a bit in it that you aren't using.  But note that it can't be
  64  * as small as MicroSpinLock (1 byte), if you don't already have a
  65  * convenient int with an unused bit lying around to put it on.
  66  *
  67  * To construct these, either use init() or zero initialize.  We don't
  68  * have a real constructor because we want this to be a POD type so we
  69  * can put it into packed structs.
  70  */
  71 template<class IntType, int Bit = sizeof(IntType) * 8 - 1>
  72 struct PicoSpinLock {
  73   // Internally we deal with the unsigned version of the type.
  74   typedef typename std::make_unsigned<IntType>::type UIntType;
  75
  76   static_assert(std::is_integral<IntType>::value,
  77                 "PicoSpinLock needs an integral type");
  78   static_assert(sizeof(IntType) == 2 || sizeof(IntType) == 4 ||
  79                   sizeof(IntType) == 8,
  80                 "PicoSpinLock can't work on integers smaller than 2 bytes");
  81
  82  public:
  83   static const UIntType kLockBitMask_ = UIntType(1) << Bit;
  84   UIntType lock_;
  85
  86   /*
  87    * You must call this function before using this class, if you
  88    * default constructed it.  If you zero-initialized it you can
  89    * assume the PicoSpinLock is in a valid unlocked state with
  90    * getData() == 0.
  91    *
  92    * (This doesn't use a constructor because we want to be a POD.)
  93    */
  94   void init(IntType initialValue = 0) {
  95     CHECK(!(initialValue & kLockBitMask_));
  96     lock_ = initialValue;
  97   }
  98
  99   /*
 100    * Returns the value of the integer we using for our lock, except
 101    * with the bit we are using as a lock cleared, regardless of
 102    * whether the lock is held.
 103    *
 104    * It is 'safe' to call this without holding the lock.  (As in: you
 105    * get the same guarantees for simultaneous accesses to an integer
 106    * as you normally get.)
 107    */
 108   IntType getData() const {
 109     return static_cast<IntType>(lock_ & ~kLockBitMask_);
 110   }
 111
 112   /*
 113    * Set the value of the other bits in our integer.
 114    *
 115    * Don't use this when you aren't holding the lock, unless it can be
 116    * guaranteed that no other threads may be trying to use this.
 117    */
 118   void setData(IntType w) {
 119     CHECK(!(w & kLockBitMask_));
 120     lock_ = (lock_ & kLockBitMask_) | w;
 121   }
 122
 123   /*
 124    * Try to get the lock without blocking: returns whether or not we
 125    * got it.
 126    */
 127   bool try_lock() const {
 128     bool ret = false;
 129
 130 #if FOLLY_X64
 131 #define FB_DOBTS(size)                                  \
 132   asm volatile("lock; bts" #size " %1, (%2); setnc %0"  \
 133                : "=r" (ret)                             \
 134                : "i" (Bit),                             \
 135                  "r" (&lock_)                           \
 136                : "memory", "flags")
 137
 138     switch (sizeof(IntType)) {
 139     case 2: FB_DOBTS(w); break;
 140     case 4: FB_DOBTS(l); break;
 141     case 8: FB_DOBTS(q); break;
 142     }
 143
 144 #undef FB_DOBTS
 145 #elif FOLLY_A64
 146     ret = __atomic_fetch_or(&lock_, 1 << Bit, __ATOMIC_SEQ_CST);
 147 #elif FOLLY_PPC64
 148 #define FB_DOBTS(size)                                 \
 149     asm volatile("\teieio\n"                           \
 150                  "\tl" #size "arx 14,0,%[lockPtr]\n"   \
 151                  "\tli 15,1\n"                         \
 152                  "\tsldi 15,15,%[bit]\n"               \
 153                  "\tand. 16,15,14\n"                   \
 154                  "\tbne 0f\n"                          \
 155                  "\tor 14,14,15\n"                     \
 156                  "\tst" #size "cx. 14,0,%[lockPtr]\n"  \
 157                  "\tbne 0f\n"                          \
 158                  "\tori %[output],%[output],1\n"       \
 159                  "\tisync\n"                           \
 160                  "0:\n"                                \
 161                  : [output] "+r" (ret)                 \
 162                  : [lockPtr] "r"(&lock_),              \
 163                    [bit] "i" (Bit)                     \
 164                  : "cr0", "memory", "r14", "r15", "r16")
 165
 166     switch (sizeof(IntType)) {
 167     case 2: FB_DOBTS(h); break;
 168     case 4: FB_DOBTS(w); break;
 169     case 8: FB_DOBTS(d); break;
 170     }
 171
 172 #undef FB_DOBTS
 173 #else
 174 #error "x86 aarch64 ppc64 only"
 175 #endif
 176
 177     return ret;
 178   }
 179
 180   /*
 181    * Block until we can acquire the lock.  Uses Sleeper to wait.
 182    */
 183   void lock() const {
 184     detail::Sleeper sleeper;
 185     while (!try_lock()) {
 186       sleeper.wait();
 187     }
 188   }
 189
 190   /*
 191    * Release the lock, without changing the value of the rest of the
 192    * integer.
 193    */
 194   void unlock() const {
 195 #if FOLLY_X64
 196 #define FB_DOBTR(size)                          \
 197   asm volatile("lock; btr" #size " %0, (%1)"    \
 198                :                                \
 199                : "i" (Bit),                     \
 200                  "r" (&lock_)                   \
 201                : "memory", "flags")
 202
 203
 204     // Reads and writes can not be reordered wrt locked instructions,
 205     // so we don't need a memory fence here.
 206     switch (sizeof(IntType)) {
 207     case 2: FB_DOBTR(w); break;
 208     case 4: FB_DOBTR(l); break;
 209     case 8: FB_DOBTR(q); break;
 210     }
 211
 212 #undef FB_DOBTR
 213 #elif FOLLY_A64
 214     __atomic_fetch_and(&lock_, ~(1 << Bit), __ATOMIC_SEQ_CST);
 215 #elif FOLLY_PPC64
 216 #define FB_DOBTR(size)                                 \
 217     asm volatile("\teieio\n"                           \
 218                  "0:  l" #size "arx 14,0,%[lockPtr]\n" \
 219                  "\tli 15,1\n"                         \
 220                  "\tsldi 15,15,%[bit]\n"               \
 221                  "\txor 14,14,15\n"                    \
 222                  "\tst" #size "cx. 14,0,%[lockPtr]\n"  \
 223                  "\tbne 0b\n"                          \
 224                  "\tisync\n"                           \
 225                  :                                     \
 226                  : [lockPtr] "r"(&lock_),              \
 227                    [bit] "i" (Bit)                     \
 228                  : "cr0", "memory", "r14", "r15")
 229
 230     switch (sizeof(IntType)) {
 231     case 2: FB_DOBTR(h); break;
 232     case 4: FB_DOBTR(w); break;
 233     case 8: FB_DOBTR(d); break;
 234     }
 235
 236 #undef FB_DOBTR
 237 #else
 238 # error "x64 aarch64 ppc64 only"
 239 #endif
 240   }
 241 };
 242
 243 }