folly/PicoSpinLock.h

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