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