folly/test/SmallLocksTest.cpp

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