folly/SmallLocks.h

   1 /*
   2  * Copyright 2012 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 #ifndef FOLLY_SMALLLOCKS_H_
  18 #define FOLLY_SMALLLOCKS_H_
  19
  20 /*
  21  * This header defines a few very small mutex types.  These are useful
  22  * in highly memory-constrained environments where contention is
  23  * unlikely.
  24  *
  25  * Note: these locks are for use when you aren't likely to contend on
  26  * the critical section, or when the critical section is incredibly
  27  * small.  Given that, both of the locks defined in this header are
  28  * inherently unfair: that is, the longer a thread is waiting, the
  29  * longer it waits between attempts to acquire, so newer waiters are
  30  * more likely to get the mutex.  For the intended use-case this is
  31  * fine.
  32  *
  33  * @author Keith Adams <kma@fb.com>
  34  * @author Jordan DeLong <delong.j@fb.com>
  35  */
  36
  37 #include <cinttypes>
  38 #include <type_traits>
  39 #include <ctime>
  40 #include <boost/noncopyable.hpp>
  41 #include <cstdlib>
  42 #include <pthread.h>
  43 #include <mutex>
  44
  45 #include <glog/logging.h>
  46
  47 #ifndef __x86_64__
  48 # error "SmallLocks.h is currently x64-only."
  49 #endif
  50
  51 namespace folly {
  52
  53 //////////////////////////////////////////////////////////////////////
  54
  55 namespace detail {
  56
  57   /*
  58    * A helper object for the condended case. Starts off with eager
  59    * spinning, and falls back to sleeping for small quantums.
  60    */
  61   class Sleeper {
  62     static const int32_t kMaxActiveSpin = 4000;
  63
  64     uint32_t spinCount;
  65
  66   public:
  67     Sleeper() : spinCount(0) {}
  68
  69     void wait() {
  70       if (spinCount < kMaxActiveSpin) {
  71         ++spinCount;
  72         asm volatile("pause");
  73       } else {
  74         /*
  75          * Always sleep 0.5ms, assuming this will make the kernel put
  76          * us down for whatever its minimum timer resolution is (in
  77          * linux this varies by kernel version from 1ms to 10ms).
  78          */
  79         struct timespec ts = { 0, 500000 };
  80         nanosleep(&ts, NULL);
  81       }
  82     }
  83   };
  84
  85 }
  86
  87 //////////////////////////////////////////////////////////////////////
  88
  89 /*
  90  * A really, *really* small spinlock for fine-grained locking of lots
  91  * of teeny-tiny data.
  92  *
  93  * Zero initializing these is guaranteed to be as good as calling
  94  * init(), since the free state is guaranteed to be all-bits zero.
  95  *
  96  * This class should be kept a POD, so we can used it in other packed
  97  * structs (gcc does not allow __attribute__((packed)) on structs that
  98  * contain non-POD data).  This means avoid adding a constructor, or
  99  * making some members private, etc.
 100  */
 101 struct MicroSpinLock {
 102   enum { FREE = 0, LOCKED = 1 };
 103   uint8_t lock_;
 104
 105   /*
 106    * Atomically move lock_ from "compare" to "newval". Return boolean
 107    * success. Do not play on or around.
 108    */
 109   bool cas(uint8_t compare, uint8_t newVal) {
 110     bool out;
 111     asm volatile("lock; cmpxchgb %2, (%3);"
 112                  "setz %0;"
 113                  : "=r" (out)
 114                  : "a" (compare), // cmpxchgb constrains this to be in %al
 115                    "q" (newVal),  // Needs to be byte-accessible
 116                    "r" (&lock_)
 117                  : "memory", "flags");
 118     return out;
 119   }
 120
 121   // Initialize this MSL.  It is unnecessary to call this if you
 122   // zero-initialize the MicroSpinLock.
 123   void init() {
 124     lock_ = FREE;
 125   }
 126
 127   bool try_lock() {
 128     return cas(FREE, LOCKED);
 129   }
 130
 131   void lock() {
 132     detail::Sleeper sleeper;
 133     do {
 134       while (lock_ != FREE) {
 135         asm volatile("" : : : "memory");
 136         sleeper.wait();
 137       }
 138     } while (!try_lock());
 139     DCHECK(lock_ == LOCKED);
 140   }
 141
 142   void unlock() {
 143     CHECK(lock_ == LOCKED);
 144     asm volatile("" : : : "memory");
 145     lock_ = FREE; // release barrier on x86
 146   }
 147 };
 148
 149 //////////////////////////////////////////////////////////////////////
 150
 151 /*
 152  * Spin lock on a single bit in an integral type.  You can use this
 153  * with 16, 32, or 64-bit integral types.
 154  *
 155  * This is useful if you want a small lock and already have an int
 156  * with a bit in it that you aren't using.  But note that it can't be
 157  * as small as MicroSpinLock (1 byte), if you don't already have a
 158  * convenient int with an unused bit lying around to put it on.
 159  *
 160  * To construct these, either use init() or zero initialize.  We don't
 161  * have a real constructor because we want this to be a POD type so we
 162  * can put it into packed structs.
 163  */
 164 template<class IntType, int Bit = sizeof(IntType) * 8 - 1>
 165 struct PicoSpinLock {
 166   // Internally we deal with the unsigned version of the type.
 167   typedef typename std::make_unsigned<IntType>::type UIntType;
 168
 169   static_assert(std::is_integral<IntType>::value,
 170                 "PicoSpinLock needs an integral type");
 171   static_assert(sizeof(IntType) == 2 || sizeof(IntType) == 4 ||
 172                   sizeof(IntType) == 8,
 173                 "PicoSpinLock can't work on integers smaller than 2 bytes");
 174
 175 public:
 176   static const UIntType kLockBitMask_ = UIntType(1) << Bit;
 177   UIntType lock_;
 178
 179   /*
 180    * You must call this function before using this class, if you
 181    * default constructed it.  If you zero-initialized it you can
 182    * assume the PicoSpinLock is in a valid unlocked state with
 183    * getData() == 0.
 184    *
 185    * (This doesn't use a constructor because we want to be a POD.)
 186    */
 187   void init(IntType initialValue = 0) {
 188     CHECK(!(initialValue & kLockBitMask_));
 189     lock_ = initialValue;
 190   }
 191
 192   /*
 193    * Returns the value of the integer we using for our lock, except
 194    * with the bit we are using as a lock cleared, regardless of
 195    * whether the lock is held.
 196    *
 197    * It is 'safe' to call this without holding the lock.  (As in: you
 198    * get the same guarantees for simultaneous accesses to an integer
 199    * as you normally get.)
 200    */
 201   IntType getData() const {
 202     return static_cast<IntType>(lock_ & ~kLockBitMask_);
 203   }
 204
 205   /*
 206    * Set the value of the other bits in our integer.
 207    *
 208    * Don't use this when you aren't holding the lock, unless it can be
 209    * guaranteed that no other threads may be trying to use this.
 210    */
 211   void setData(IntType w) {
 212     CHECK(!(w & kLockBitMask_));
 213     lock_ = (lock_ & kLockBitMask_) | w;
 214   }
 215
 216   /*
 217    * Try to get the lock without blocking: returns whether or not we
 218    * got it.
 219    */
 220   bool try_lock() const {
 221     bool ret = false;
 222
 223 #define FB_DOBTS(size)                                  \
 224   asm volatile("lock; bts" #size " %1, (%2); setnc %0"  \
 225                : "=r" (ret)                             \
 226                : "i" (Bit),                             \
 227                  "r" (&lock_)                           \
 228                : "memory", "flags")
 229
 230     switch (sizeof(IntType)) {
 231     case 2: FB_DOBTS(w); break;
 232     case 4: FB_DOBTS(l); break;
 233     case 8: FB_DOBTS(q); break;
 234     }
 235
 236 #undef FB_DOBTS
 237
 238     return ret;
 239   }
 240
 241   /*
 242    * Block until we can acquire the lock.  Uses Sleeper to wait.
 243    */
 244   void lock() const {
 245     detail::Sleeper sleeper;
 246     while (!try_lock()) {
 247       sleeper.wait();
 248     }
 249   }
 250
 251   /*
 252    * Release the lock, without changing the value of the rest of the
 253    * integer.
 254    */
 255   void unlock() const {
 256 #define FB_DOBTR(size)                          \
 257   asm volatile("lock; btr" #size " %0, (%1)"    \
 258                :                                \
 259                : "i" (Bit),                     \
 260                  "r" (&lock_)                   \
 261                : "memory", "flags")
 262
 263
 264     // Reads and writes can not be reordered wrt locked instructions,
 265     // so we don't need a memory fence here.
 266     switch (sizeof(IntType)) {
 267     case 2: FB_DOBTR(w); break;
 268     case 4: FB_DOBTR(l); break;
 269     case 8: FB_DOBTR(q); break;
 270     }
 271
 272 #undef FB_DOBTR
 273   }
 274 };
 275
 276 //////////////////////////////////////////////////////////////////////
 277
 278 typedef std::lock_guard<MicroSpinLock> MSLGuard;
 279
 280 //////////////////////////////////////////////////////////////////////
 281
 282 }
 283
 284 #endif