2 * Copyright 2017 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
22 // TimedMutex implementation
25 template <typename WaitFunc>
26 TimedMutex::LockResult TimedMutex::lockHelper(WaitFunc&& waitFunc) {
27 std::unique_lock<folly::SpinLock> lock(lock_);
30 return LockResult::SUCCESS;
33 const auto isOnFiber = onFiber();
35 if (!isOnFiber && notifiedFiber_ != nullptr) {
36 // lock() was called on a thread and while some other fiber was already
37 // notified, it hasn't be run yet. We steal the lock from that fiber then
38 // to avoid potential deadlock.
39 DCHECK(threadWaiters_.empty());
40 notifiedFiber_ = nullptr;
41 return LockResult::SUCCESS;
44 // Delay constructing the waiter until it is actually required.
45 // This makes a huge difference, at least in the benchmarks,
46 // when the mutex isn't locked.
49 fiberWaiters_.push_back(waiter);
51 threadWaiters_.push_back(waiter);
56 if (!waitFunc(waiter)) {
57 return LockResult::TIMEOUT;
61 auto lockStolen = [&] {
62 std::lock_guard<folly::SpinLock> lg(lock_);
64 auto stolen = notifiedFiber_ != &waiter;
65 notifiedFiber_ = nullptr;
70 return LockResult::STOLEN;
74 return LockResult::SUCCESS;
77 inline void TimedMutex::lock() {
78 auto result = lockHelper([](MutexWaiter& waiter) {
83 DCHECK(result != LockResult::TIMEOUT);
84 if (result == LockResult::SUCCESS) {
90 template <typename Rep, typename Period>
91 bool TimedMutex::timed_lock(
92 const std::chrono::duration<Rep, Period>& duration) {
93 auto result = lockHelper([&](MutexWaiter& waiter) {
94 if (!waiter.baton.timed_wait(duration)) {
95 // We timed out. Two cases:
96 // 1. We're still in the waiter list and we truly timed out
97 // 2. We're not in the waiter list anymore. This could happen if the baton
98 // times out but the mutex is unlocked before we reach this code. In
100 // case we'll pretend we got the lock on time.
101 std::lock_guard<folly::SpinLock> lg(lock_);
102 if (waiter.hook.is_linked()) {
103 waiter.hook.unlink();
111 case LockResult::SUCCESS:
113 case LockResult::TIMEOUT:
115 case LockResult::STOLEN:
116 // We don't respect the duration if lock was stolen
120 assume_unreachable();
123 inline bool TimedMutex::try_lock() {
124 std::lock_guard<folly::SpinLock> lg(lock_);
132 inline void TimedMutex::unlock() {
133 std::lock_guard<folly::SpinLock> lg(lock_);
134 if (!threadWaiters_.empty()) {
135 auto& to_wake = threadWaiters_.front();
136 threadWaiters_.pop_front();
137 to_wake.baton.post();
138 } else if (!fiberWaiters_.empty()) {
139 auto& to_wake = fiberWaiters_.front();
140 fiberWaiters_.pop_front();
141 notifiedFiber_ = &to_wake;
142 to_wake.baton.post();
149 // TimedRWMutex implementation
152 template <typename BatonType>
153 void TimedRWMutex<BatonType>::read_lock() {
154 pthread_spin_lock(&lock_);
155 if (state_ == State::WRITE_LOCKED) {
157 read_waiters_.push_back(waiter);
158 pthread_spin_unlock(&lock_);
160 assert(state_ == State::READ_LOCKED);
164 (state_ == State::UNLOCKED && readers_ == 0) ||
165 (state_ == State::READ_LOCKED && readers_ > 0));
166 assert(read_waiters_.empty());
167 state_ = State::READ_LOCKED;
169 pthread_spin_unlock(&lock_);
172 template <typename BatonType>
173 template <typename Rep, typename Period>
174 bool TimedRWMutex<BatonType>::timed_read_lock(
175 const std::chrono::duration<Rep, Period>& duration) {
176 pthread_spin_lock(&lock_);
177 if (state_ == State::WRITE_LOCKED) {
179 read_waiters_.push_back(waiter);
180 pthread_spin_unlock(&lock_);
182 if (!waiter.baton.timed_wait(duration)) {
183 // We timed out. Two cases:
184 // 1. We're still in the waiter list and we truly timed out
185 // 2. We're not in the waiter list anymore. This could happen if the baton
186 // times out but the mutex is unlocked before we reach this code. In
187 // this case we'll pretend we got the lock on time.
188 pthread_spin_lock(&lock_);
189 if (waiter.hook.is_linked()) {
190 read_waiters_.erase(read_waiters_.iterator_to(waiter));
191 pthread_spin_unlock(&lock_);
194 pthread_spin_unlock(&lock_);
199 (state_ == State::UNLOCKED && readers_ == 0) ||
200 (state_ == State::READ_LOCKED && readers_ > 0));
201 assert(read_waiters_.empty());
202 state_ = State::READ_LOCKED;
204 pthread_spin_unlock(&lock_);
208 template <typename BatonType>
209 bool TimedRWMutex<BatonType>::try_read_lock() {
210 pthread_spin_lock(&lock_);
211 if (state_ != State::WRITE_LOCKED) {
213 (state_ == State::UNLOCKED && readers_ == 0) ||
214 (state_ == State::READ_LOCKED && readers_ > 0));
215 assert(read_waiters_.empty());
216 state_ = State::READ_LOCKED;
218 pthread_spin_unlock(&lock_);
221 pthread_spin_unlock(&lock_);
225 template <typename BatonType>
226 void TimedRWMutex<BatonType>::write_lock() {
227 pthread_spin_lock(&lock_);
228 if (state_ == State::UNLOCKED) {
229 verify_unlocked_properties();
230 state_ = State::WRITE_LOCKED;
231 pthread_spin_unlock(&lock_);
235 write_waiters_.push_back(waiter);
236 pthread_spin_unlock(&lock_);
240 template <typename BatonType>
241 template <typename Rep, typename Period>
242 bool TimedRWMutex<BatonType>::timed_write_lock(
243 const std::chrono::duration<Rep, Period>& duration) {
244 pthread_spin_lock(&lock_);
245 if (state_ == State::UNLOCKED) {
246 verify_unlocked_properties();
247 state_ = State::WRITE_LOCKED;
248 pthread_spin_unlock(&lock_);
252 write_waiters_.push_back(waiter);
253 pthread_spin_unlock(&lock_);
255 if (!waiter.baton.timed_wait(duration)) {
256 // We timed out. Two cases:
257 // 1. We're still in the waiter list and we truly timed out
258 // 2. We're not in the waiter list anymore. This could happen if the baton
259 // times out but the mutex is unlocked before we reach this code. In
260 // this case we'll pretend we got the lock on time.
261 pthread_spin_lock(&lock_);
262 if (waiter.hook.is_linked()) {
263 write_waiters_.erase(write_waiters_.iterator_to(waiter));
264 pthread_spin_unlock(&lock_);
267 pthread_spin_unlock(&lock_);
269 assert(state_ == State::WRITE_LOCKED);
273 template <typename BatonType>
274 bool TimedRWMutex<BatonType>::try_write_lock() {
275 pthread_spin_lock(&lock_);
276 if (state_ == State::UNLOCKED) {
277 verify_unlocked_properties();
278 state_ = State::WRITE_LOCKED;
279 pthread_spin_unlock(&lock_);
282 pthread_spin_unlock(&lock_);
286 template <typename BatonType>
287 void TimedRWMutex<BatonType>::unlock() {
288 pthread_spin_lock(&lock_);
289 assert(state_ != State::UNLOCKED);
291 (state_ == State::READ_LOCKED && readers_ > 0) ||
292 (state_ == State::WRITE_LOCKED && readers_ == 0));
293 if (state_ == State::READ_LOCKED) {
297 if (!read_waiters_.empty()) {
299 state_ == State::WRITE_LOCKED && readers_ == 0 &&
300 "read waiters can only accumulate while write locked");
301 state_ = State::READ_LOCKED;
302 readers_ = read_waiters_.size();
304 while (!read_waiters_.empty()) {
305 MutexWaiter& to_wake = read_waiters_.front();
306 read_waiters_.pop_front();
307 to_wake.baton.post();
309 } else if (readers_ == 0) {
310 if (!write_waiters_.empty()) {
311 assert(read_waiters_.empty());
312 state_ = State::WRITE_LOCKED;
314 // Wake a single writer (after releasing the spin lock)
315 MutexWaiter& to_wake = write_waiters_.front();
316 write_waiters_.pop_front();
317 to_wake.baton.post();
319 verify_unlocked_properties();
320 state_ = State::UNLOCKED;
323 assert(state_ == State::READ_LOCKED);
325 pthread_spin_unlock(&lock_);
328 template <typename BatonType>
329 void TimedRWMutex<BatonType>::downgrade() {
330 pthread_spin_lock(&lock_);
331 assert(state_ == State::WRITE_LOCKED && readers_ == 0);
332 state_ = State::READ_LOCKED;
335 if (!read_waiters_.empty()) {
336 readers_ += read_waiters_.size();
338 while (!read_waiters_.empty()) {
339 MutexWaiter& to_wake = read_waiters_.front();
340 read_waiters_.pop_front();
341 to_wake.baton.post();
344 pthread_spin_unlock(&lock_);