folly/test/SmallLocksTest.cpp

   1 /*
   2  * Copyright 2011-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 #include <folly/SmallLocks.h>
  18
  19 #include <cassert>
  20 #include <condition_variable>
  21 #include <cstdio>
  22 #include <mutex>
  23 #include <string>
  24 #include <thread>
  25 #include <vector>
  26
  27 #include <glog/logging.h>
  28
  29 #include <folly/Random.h>
  30 #include <folly/portability/Asm.h>
  31 #include <folly/portability/GTest.h>
  32 #include <folly/portability/PThread.h>
  33 #include <folly/portability/Unistd.h>
  34
  35 using folly::MSLGuard;
  36 using folly::MicroLock;
  37 using folly::MicroSpinLock;
  38 using std::string;
  39
  40 #ifdef FOLLY_PICO_SPIN_LOCK_H_
  41 using folly::PicoSpinLock;
  42 #endif
  43
  44 namespace {
  45
  46 struct LockedVal {
  47   int ar[1024];
  48   MicroSpinLock lock;
  49
  50   LockedVal() {
  51     lock.init();
  52     memset(ar, 0, sizeof ar);
  53   }
  54 };
  55
  56 // Compile time test for packed struct support (requires that both of
  57 // these classes are POD).
  58 FOLLY_PACK_PUSH
  59 struct ignore1 { MicroSpinLock msl; int16_t foo; } FOLLY_PACK_ATTR;
  60 static_assert(sizeof(ignore1) == 3, "Size check failed");
  61 static_assert(sizeof(MicroSpinLock) == 1, "Size check failed");
  62 #ifdef FOLLY_PICO_SPIN_LOCK_H_
  63 struct ignore2 { PicoSpinLock<uint32_t> psl; int16_t foo; } FOLLY_PACK_ATTR;
  64 static_assert(sizeof(ignore2) == 6, "Size check failed");
  65 #endif
  66 FOLLY_PACK_POP
  67
  68 LockedVal v;
  69 void splock_test() {
  70
  71   const int max = 1000;
  72   auto rng = folly::ThreadLocalPRNG();
  73   for (int i = 0; i < max; i++) {
  74     folly::asm_volatile_pause();
  75     MSLGuard g(v.lock);
  76
  77     int first = v.ar[0];
  78     for (size_t j = 1; j < sizeof v.ar / sizeof j; ++j) {
  79       EXPECT_EQ(first, v.ar[j]);
  80     }
  81
  82     int byte = folly::Random::rand32(rng);
  83     memset(v.ar, char(byte), sizeof v.ar);
  84   }
  85 }
  86
  87 #ifdef FOLLY_PICO_SPIN_LOCK_H_
  88 template <class T> struct PslTest {
  89   PicoSpinLock<T> lock;
  90
  91   PslTest() { lock.init(); }
  92
  93   void doTest() {
  94     using UT = typename std::make_unsigned<T>::type;
  95     T ourVal = rand() % T(UT(1) << (sizeof(UT) * 8 - 1));
  96     for (int i = 0; i < 100; ++i) {
  97       std::lock_guard<PicoSpinLock<T>> guard(lock);
  98       lock.setData(ourVal);
  99       for (int n = 0; n < 10; ++n) {
 100         folly::asm_volatile_pause();
 101         EXPECT_EQ(lock.getData(), ourVal);
 102       }
 103     }
 104   }
 105 };
 106
 107 template <class T>
 108 void doPslTest() {
 109   PslTest<T> testObj;
 110
 111   const int nthrs = 17;
 112   std::vector<std::thread> threads;
 113   for (int i = 0; i < nthrs; ++i) {
 114     threads.push_back(std::thread(&PslTest<T>::doTest, &testObj));
 115   }
 116   for (auto& t : threads) {
 117     t.join();
 118   }
 119 }
 120 #endif
 121
 122 struct TestClobber {
 123   TestClobber() {
 124     lock_.init();
 125   }
 126
 127   void go() {
 128     std::lock_guard<MicroSpinLock> g(lock_);
 129     // This bug depends on gcc register allocation and is very sensitive. We
 130     // have to use DCHECK instead of EXPECT_*.
 131     DCHECK(!lock_.try_lock());
 132   }
 133
 134  private:
 135   MicroSpinLock lock_;
 136 };
 137
 138 } // namespace
 139
 140 TEST(SmallLocks, SpinLockCorrectness) {
 141   EXPECT_EQ(sizeof(MicroSpinLock), 1);
 142
 143   int nthrs = sysconf(_SC_NPROCESSORS_ONLN) * 2;
 144   std::vector<std::thread> threads;
 145   for (int i = 0; i < nthrs; ++i) {
 146     threads.push_back(std::thread(splock_test));
 147   }
 148   for (auto& t : threads) {
 149     t.join();
 150   }
 151 }
 152
 153 #ifdef FOLLY_PICO_SPIN_LOCK_H_
 154 TEST(SmallLocks, PicoSpinCorrectness) {
 155   doPslTest<int16_t>();
 156   doPslTest<uint16_t>();
 157   doPslTest<int32_t>();
 158   doPslTest<uint32_t>();
 159   doPslTest<int64_t>();
 160   doPslTest<uint64_t>();
 161 }
 162
 163 TEST(SmallLocks, PicoSpinSigned) {
 164   typedef PicoSpinLock<int16_t,0> Lock;
 165   Lock val;
 166   val.init(-4);
 167   EXPECT_EQ(val.getData(), -4);
 168
 169   {
 170     std::lock_guard<Lock> guard(val);
 171     EXPECT_EQ(val.getData(), -4);
 172     val.setData(-8);
 173     EXPECT_EQ(val.getData(), -8);
 174   }
 175   EXPECT_EQ(val.getData(), -8);
 176 }
 177 #endif
 178
 179 TEST(SmallLocks, RegClobber) {
 180   TestClobber().go();
 181 }
 182
 183 FOLLY_PACK_PUSH
 184 #if defined(__SANITIZE_ADDRESS__) && !defined(__clang__) && \
 185     (defined(__GNUC__) || defined(__GNUG__))
 186 static_assert(sizeof(MicroLock) == 4, "Size check failed");
 187 #else
 188 static_assert(sizeof(MicroLock) == 1, "Size check failed");
 189 #endif
 190 FOLLY_PACK_POP
 191
 192 namespace {
 193
 194 struct SimpleBarrier {
 195
 196   SimpleBarrier() : lock_(), cv_(), ready_(false) {}
 197
 198   void wait() {
 199     std::unique_lock<std::mutex> lockHeld(lock_);
 200     while (!ready_) {
 201       cv_.wait(lockHeld);
 202     }
 203   }
 204
 205   void run() {
 206     {
 207       std::unique_lock<std::mutex> lockHeld(lock_);
 208       ready_ = true;
 209     }
 210
 211     cv_.notify_all();
 212   }
 213
 214  private:
 215   std::mutex lock_;
 216   std::condition_variable cv_;
 217   bool ready_;
 218 };
 219 } // namespace
 220
 221 TEST(SmallLocks, MicroLock) {
 222   volatile uint64_t counters[4] = {0, 0, 0, 0};
 223   std::vector<std::thread> threads;
 224   static const unsigned nrThreads = 20;
 225   static const unsigned iterPerThread = 10000;
 226   SimpleBarrier startBarrier;
 227
 228   assert(iterPerThread % 4 == 0);
 229
 230   // Embed the lock in a larger structure to ensure that we do not
 231   // affect bits outside the ones MicroLock is defined to affect.
 232   struct {
 233     uint8_t a;
 234     std::atomic<uint8_t> b;
 235     MicroLock alock;
 236     std::atomic<uint8_t> d;
 237   } x;
 238
 239   uint8_t origB = 'b';
 240   uint8_t origD = 'd';
 241
 242   x.a = 'a';
 243   x.b = origB;
 244   x.alock.init();
 245   x.d = origD;
 246
 247   // This thread touches other parts of the host word to show that
 248   // MicroLock does not interfere with memory outside of the byte
 249   // it owns.
 250   std::thread adjacentMemoryToucher = std::thread([&] {
 251     startBarrier.wait();
 252     for (unsigned iter = 0; iter < iterPerThread; ++iter) {
 253       if (iter % 2) {
 254         x.b++;
 255       } else {
 256         x.d++;
 257       }
 258     }
 259   });
 260
 261   for (unsigned i = 0; i < nrThreads; ++i) {
 262     threads.emplace_back([&] {
 263       startBarrier.wait();
 264       for (unsigned iter = 0; iter < iterPerThread; ++iter) {
 265         unsigned slotNo = iter % 4;
 266         x.alock.lock(slotNo);
 267         counters[slotNo] += 1;
 268         // The occasional sleep makes it more likely that we'll
 269         // exercise the futex-wait path inside MicroLock.
 270         if (iter % 1000 == 0) {
 271           struct timespec ts = {0, 10000};
 272           (void)nanosleep(&ts, nullptr);
 273         }
 274         x.alock.unlock(slotNo);
 275       }
 276     });
 277   }
 278
 279   startBarrier.run();
 280
 281   for (auto it = threads.begin(); it != threads.end(); ++it) {
 282     it->join();
 283   }
 284
 285   adjacentMemoryToucher.join();
 286
 287   EXPECT_EQ(x.a, 'a');
 288   EXPECT_EQ(x.b, (uint8_t)(origB + iterPerThread / 2));
 289   EXPECT_EQ(x.d, (uint8_t)(origD + iterPerThread / 2));
 290   for (unsigned i = 0; i < 4; ++i) {
 291     EXPECT_EQ(counters[i], ((uint64_t)nrThreads * iterPerThread) / 4);
 292   }
 293 }
 294
 295 TEST(SmallLocks, MicroLockTryLock) {
 296   MicroLock lock;
 297   lock.init();
 298   EXPECT_TRUE(lock.try_lock());
 299   EXPECT_FALSE(lock.try_lock());
 300   lock.unlock();
 301 }