folly/test/SpinLockTest.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/SpinLock.h>
  18
  19 #include <folly/Random.h>
  20
  21 #include <thread>
  22
  23 #include <folly/portability/Asm.h>
  24 #include <folly/portability/GTest.h>
  25
  26 using folly::SpinLockGuardImpl;
  27
  28 namespace {
  29
  30 template <typename LOCK>
  31 struct LockedVal {
  32   int ar[1024];
  33   LOCK lock;
  34
  35   LockedVal() {
  36     memset(ar, 0, sizeof ar);
  37   }
  38 };
  39
  40 template <typename LOCK>
  41 void spinlockTestThread(LockedVal<LOCK>* v) {
  42   const int max = 1000;
  43   auto rng = folly::ThreadLocalPRNG();
  44   for (int i = 0; i < max; i++) {
  45     folly::asm_volatile_pause();
  46     SpinLockGuardImpl<LOCK> g(v->lock);
  47
  48     int first = v->ar[0];
  49     for (size_t j = 1; j < sizeof v->ar / sizeof j; ++j) {
  50       EXPECT_EQ(first, v->ar[j]);
  51     }
  52
  53     int byte = folly::Random::rand32(rng);
  54     memset(v->ar, char(byte), sizeof v->ar);
  55   }
  56 }
  57
  58 template <typename LOCK>
  59 struct TryLockState {
  60   LOCK lock1;
  61   LOCK lock2;
  62   bool locked{false};
  63   uint64_t obtained{0};
  64   uint64_t failed{0};
  65 };
  66
  67 template <typename LOCK>
  68 void trylockTestThread(TryLockState<LOCK>* state, size_t count) {
  69   while (true) {
  70     folly::asm_volatile_pause();
  71     bool ret = state->lock2.try_lock();
  72     SpinLockGuardImpl<LOCK> g(state->lock1);
  73     if (state->obtained >= count) {
  74       if (ret) {
  75         state->lock2.unlock();
  76       }
  77       break;
  78     }
  79
  80
  81     if (ret) {
  82       // We got lock2.
  83       EXPECT_NE(state->locked, ret);
  84       ++state->obtained;
  85       state->locked = true;
  86
  87       // Release lock1 and wait until at least one other thread fails to
  88       // obtain the lock2 before continuing.
  89       auto oldFailed = state->failed;
  90       while (state->failed == oldFailed && state->obtained < count) {
  91         state->lock1.unlock();
  92         folly::asm_volatile_pause();
  93         state->lock1.lock();
  94       }
  95
  96       state->locked = false;
  97       state->lock2.unlock();
  98     } else {
  99       ++state->failed;
 100     }
 101   }
 102 }
 103
 104 template <typename LOCK>
 105 void correctnessTest() {
 106   int nthrs = sysconf(_SC_NPROCESSORS_ONLN) * 2;
 107   std::vector<std::thread> threads;
 108   LockedVal<LOCK> v;
 109   for (int i = 0; i < nthrs; ++i) {
 110     threads.push_back(std::thread(spinlockTestThread<LOCK>, &v));
 111   }
 112   for (auto& t : threads) {
 113     t.join();
 114   }
 115 }
 116
 117 template <typename LOCK>
 118 void trylockTest() {
 119   int nthrs = sysconf(_SC_NPROCESSORS_ONLN) + 4;
 120   std::vector<std::thread> threads;
 121   TryLockState<LOCK> state;
 122   size_t count = 100;
 123   for (int i = 0; i < nthrs; ++i) {
 124     threads.push_back(std::thread(trylockTestThread<LOCK>, &state, count));
 125   }
 126   for (auto& t : threads) {
 127     t.join();
 128   }
 129
 130   EXPECT_EQ(count, state.obtained);
 131   // Each time the code obtains lock2 it waits for another thread to fail
 132   // to acquire it.  The only time this might not happen is on the very last
 133   // loop when no other threads are left.
 134   EXPECT_GE(state.failed + 1, state.obtained);
 135 }
 136
 137 } // namespace
 138
 139 TEST(SpinLock, Correctness) {
 140   correctnessTest<folly::SpinLock>();
 141 }
 142 TEST(SpinLock, TryLock) {
 143   trylockTest<folly::SpinLock>();
 144 }