folly/test/SmallLocksTest.cpp

   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 #include <folly/SmallLocks.h>
  18
  19 #include <folly/Random.h>
  20
  21 #include <cassert>
  22 #include <cstdio>
  23 #include <mutex>
  24 #include <condition_variable>
  25 #include <string>
  26 #include <vector>
  27 #include <pthread.h>
  28 #include <unistd.h>
  29
  30 #include <thread>
  31
  32 #include <gtest/gtest.h>
  33
  34 #include <folly/portability/Asm.h>
  35
  36 using folly::MSLGuard;
  37 using folly::MicroLock;
  38 using folly::MicroSpinLock;
  39 using std::string;
  40
  41 #ifdef FOLLY_PICO_SPIN_LOCK_H_
  42 using folly::PicoSpinLock;
  43 #endif
  44
  45 namespace {
  46
  47 struct LockedVal {
  48   int ar[1024];
  49   MicroSpinLock lock;
  50
  51   LockedVal() {
  52     lock.init();
  53     memset(ar, 0, sizeof ar);
  54   }
  55 };
  56
  57 // Compile time test for packed struct support (requires that both of
  58 // these classes are POD).
  59 FOLLY_PACK_PUSH
  60 struct ignore1 { MicroSpinLock msl; int16_t foo; } FOLLY_PACK_ATTR;
  61 static_assert(sizeof(ignore1) == 3, "Size check failed");
  62 static_assert(sizeof(MicroSpinLock) == 1, "Size check failed");
  63 #ifdef FOLLY_PICO_SPIN_LOCK_H_
  64 struct ignore2 { PicoSpinLock<uint32_t> psl; int16_t foo; } FOLLY_PACK_ATTR;
  65 static_assert(sizeof(ignore2) == 6, "Size check failed");
  66 #endif
  67 FOLLY_PACK_POP
  68
  69 LockedVal v;
  70 void splock_test() {
  71
  72   const int max = 1000;
  73   auto rng = folly::ThreadLocalPRNG();
  74   for (int i = 0; i < max; i++) {
  75     folly::asm_pause();
  76     MSLGuard g(v.lock);
  77
  78     int first = v.ar[0];
  79     for (size_t i = 1; i < sizeof v.ar / sizeof i; ++i) {
  80       EXPECT_EQ(first, v.ar[i]);
  81     }
  82
  83     int byte = folly::Random::rand32(rng);
  84     memset(v.ar, char(byte), sizeof v.ar);
  85   }
  86 }
  87
  88 #ifdef FOLLY_PICO_SPIN_LOCK_H_
  89 template<class T> struct PslTest {
  90   PicoSpinLock<T> lock;
  91
  92   PslTest() { lock.init(); }
  93
  94   void doTest() {
  95     T ourVal = rand() % (T(1) << (sizeof(T) * 8 - 1));
  96     for (int i = 0; i < 10000; ++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 }
 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 static_assert(sizeof(MicroLock) == 1, "Size check failed");
 185 FOLLY_PACK_POP
 186
 187 namespace {
 188
 189 struct SimpleBarrier {
 190
 191   SimpleBarrier() : lock_(), cv_(), ready_(false) {}
 192
 193   void wait() {
 194     std::unique_lock<std::mutex> lockHeld(lock_);
 195     while (!ready_) {
 196       cv_.wait(lockHeld);
 197     }
 198   }
 199
 200   void run() {
 201     {
 202       std::unique_lock<std::mutex> lockHeld(lock_);
 203       ready_ = true;
 204     }
 205
 206     cv_.notify_all();
 207   }
 208
 209  private:
 210   std::mutex lock_;
 211   std::condition_variable cv_;
 212   bool ready_;
 213 };
 214 }
 215
 216 TEST(SmallLocks, MicroLock) {
 217   volatile uint64_t counters[4] = {0, 0, 0, 0};
 218   std::vector<std::thread> threads;
 219   static const unsigned nrThreads = 20;
 220   static const unsigned iterPerThread = 10000;
 221   SimpleBarrier startBarrier;
 222
 223   assert(iterPerThread % 4 == 0);
 224
 225   // Embed the lock in a larger structure to ensure that we do not
 226   // affect bits outside the ones MicroLock is defined to affect.
 227   struct {
 228     uint8_t a;
 229     volatile uint8_t b;
 230     MicroLock alock;
 231     volatile uint8_t d;
 232   } x;
 233
 234   uint8_t origB = 'b';
 235   uint8_t origD = 'd';
 236
 237   x.a = 'a';
 238   x.b = origB;
 239   x.alock.init();
 240   x.d = origD;
 241
 242   // This thread touches other parts of the host word to show that
 243   // MicroLock does not interfere with memory outside of the byte
 244   // it owns.
 245   std::thread adjacentMemoryToucher = std::thread([&] {
 246     startBarrier.wait();
 247     for (unsigned iter = 0; iter < iterPerThread; ++iter) {
 248       if (iter % 2) {
 249         x.b++;
 250       } else {
 251         x.d++;
 252       }
 253     }
 254   });
 255
 256   for (unsigned i = 0; i < nrThreads; ++i) {
 257     threads.emplace_back([&] {
 258       startBarrier.wait();
 259       for (unsigned iter = 0; iter < iterPerThread; ++iter) {
 260         unsigned slotNo = iter % 4;
 261         x.alock.lock(slotNo);
 262         counters[slotNo] += 1;
 263         // The occasional sleep makes it more likely that we'll
 264         // exercise the futex-wait path inside MicroLock.
 265         if (iter % 1000 == 0) {
 266           struct timespec ts = {0, 10000};
 267           (void)nanosleep(&ts, nullptr);
 268         }
 269         x.alock.unlock(slotNo);
 270       }
 271     });
 272   }
 273
 274   startBarrier.run();
 275
 276   for (auto it = threads.begin(); it != threads.end(); ++it) {
 277     it->join();
 278   }
 279
 280   adjacentMemoryToucher.join();
 281
 282   EXPECT_EQ(x.a, 'a');
 283   EXPECT_EQ(x.b, (uint8_t)(origB + iterPerThread / 2));
 284   EXPECT_EQ(x.d, (uint8_t)(origD + iterPerThread / 2));
 285   for (unsigned i = 0; i < 4; ++i) {
 286     EXPECT_EQ(counters[i], ((uint64_t)nrThreads * iterPerThread) / 4);
 287   }
 288 }
 289
 290 TEST(SmallLocks, MicroLockTryLock) {
 291   MicroLock lock;
 292   lock.init();
 293   EXPECT_TRUE(lock.try_lock());
 294   EXPECT_FALSE(lock.try_lock());
 295   lock.unlock();
 296 }