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