1/*
2 * Copyright 2014-present 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
26using folly::SpinLockGuardImpl;
27
28namespace {
29
30template <typename LOCK>
31struct LockedVal {
32 int ar[1024];
33 LOCK lock;
34
35 LockedVal() {
36 memset(ar, 0, sizeof ar);
37 }
38};
39
40template <typename LOCK>
41void 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
58template <typename LOCK>
59struct TryLockState {
60 LOCK lock1;
61 LOCK lock2;
62 bool locked{false};
63 uint64_t obtained{0};
64 uint64_t failed{0};
65};
66
67template <typename LOCK>
68void 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 if (ret) {
81 // We got lock2.
82 EXPECT_NE(state->locked, ret);
83 ++state->obtained;
84 state->locked = true;
85
86 // Release lock1 and wait until at least one other thread fails to
87 // obtain the lock2 before continuing.
88 auto oldFailed = state->failed;
89 while (state->failed == oldFailed && state->obtained < count) {
90 state->lock1.unlock();
91 folly::asm_volatile_pause();
92 state->lock1.lock();
93 }
94
95 state->locked = false;
96 state->lock2.unlock();
97 } else {
98 ++state->failed;
99 }
100 }
101}
102
103template <typename LOCK>
104void correctnessTest() {
105 int nthrs = sysconf(_SC_NPROCESSORS_ONLN) * 2;
106 std::vector<std::thread> threads;
107 LockedVal<LOCK> v;
108 for (int i = 0; i < nthrs; ++i) {
109 threads.push_back(std::thread(spinlockTestThread<LOCK>, &v));
110 }
111 for (auto& t : threads) {
112 t.join();
113 }
114}
115
116template <typename LOCK>
117void trylockTest() {
118 int nthrs = sysconf(_SC_NPROCESSORS_ONLN) + 4;
119 std::vector<std::thread> threads;
120 TryLockState<LOCK> state;
121 size_t count = 100;
122 for (int i = 0; i < nthrs; ++i) {
123 threads.push_back(std::thread(trylockTestThread<LOCK>, &state, count));
124 }
125 for (auto& t : threads) {
126 t.join();
127 }
128
129 EXPECT_EQ(count, state.obtained);
130 // Each time the code obtains lock2 it waits for another thread to fail
131 // to acquire it. The only time this might not happen is on the very last
132 // loop when no other threads are left.
133 EXPECT_GE(state.failed + 1, state.obtained);
134}
135
136} // namespace
137
138TEST(SpinLock, Correctness) {
139 correctnessTest<folly::SpinLock>();
140}
141TEST(SpinLock, TryLock) {
142 trylockTest<folly::SpinLock>();
143}
144