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.
24 // TimedMutex implementation
27 template <typename WaitFunc>
28 TimedMutex::LockResult TimedMutex::lockHelper(WaitFunc&& waitFunc) {
29 std::unique_lock<folly::SpinLock> lock(lock_);
32 return LockResult::SUCCESS;
35 const auto isOnFiber = onFiber();
37 if (!isOnFiber && notifiedFiber_ != nullptr) {
38 // lock() was called on a thread and while some other fiber was already
39 // notified, it hasn't be run yet. We steal the lock from that fiber then
40 // to avoid potential deadlock.
41 DCHECK(threadWaiters_.empty());
42 notifiedFiber_ = nullptr;
43 return LockResult::SUCCESS;
46 // Delay constructing the waiter until it is actually required.
47 // This makes a huge difference, at least in the benchmarks,
48 // when the mutex isn't locked.
51 fiberWaiters_.push_back(waiter);
53 threadWaiters_.push_back(waiter);
58 if (!waitFunc(waiter)) {
59 return LockResult::TIMEOUT;
63 auto lockStolen = [&] {
64 std::lock_guard<folly::SpinLock> lg(lock_);
66 auto stolen = notifiedFiber_ != &waiter;
67 notifiedFiber_ = nullptr;
72 return LockResult::STOLEN;
76 return LockResult::SUCCESS;
79 inline void TimedMutex::lock() {
80 auto result = lockHelper([](MutexWaiter& waiter) {
85 DCHECK(result != LockResult::TIMEOUT);
86 if (result == LockResult::SUCCESS) {
92 template <typename Rep, typename Period>
93 bool TimedMutex::timed_lock(
94 const std::chrono::duration<Rep, Period>& duration) {
95 auto result = lockHelper([&](MutexWaiter& waiter) {
96 if (!waiter.baton.timed_wait(duration)) {
97 // We timed out. Two cases:
98 // 1. We're still in the waiter list and we truly timed out
99 // 2. We're not in the waiter list anymore. This could happen if the baton
100 // times out but the mutex is unlocked before we reach this code. In
102 // case we'll pretend we got the lock on time.
103 std::lock_guard<folly::SpinLock> lg(lock_);
104 if (waiter.hook.is_linked()) {
105 waiter.hook.unlink();
113 case LockResult::SUCCESS:
115 case LockResult::TIMEOUT:
117 case LockResult::STOLEN:
118 // We don't respect the duration if lock was stolen
122 assume_unreachable();
125 inline bool TimedMutex::try_lock() {
126 std::lock_guard<folly::SpinLock> lg(lock_);
134 inline void TimedMutex::unlock() {
135 std::lock_guard<folly::SpinLock> lg(lock_);
136 if (!threadWaiters_.empty()) {
137 auto& to_wake = threadWaiters_.front();
138 threadWaiters_.pop_front();
139 to_wake.baton.post();
140 } else if (!fiberWaiters_.empty()) {
141 auto& to_wake = fiberWaiters_.front();
142 fiberWaiters_.pop_front();
143 notifiedFiber_ = &to_wake;
144 to_wake.baton.post();
151 // TimedRWMutex implementation
154 template <typename BatonType>
155 void TimedRWMutex<BatonType>::read_lock() {
156 std::unique_lock<folly::SpinLock> lock{lock_};
157 if (state_ == State::WRITE_LOCKED) {
159 read_waiters_.push_back(waiter);
162 assert(state_ == State::READ_LOCKED);
166 (state_ == State::UNLOCKED && readers_ == 0) ||
167 (state_ == State::READ_LOCKED && readers_ > 0));
168 assert(read_waiters_.empty());
169 state_ = State::READ_LOCKED;
173 template <typename BatonType>
174 template <typename Rep, typename Period>
175 bool TimedRWMutex<BatonType>::timed_read_lock(
176 const std::chrono::duration<Rep, Period>& duration) {
177 std::unique_lock<folly::SpinLock> lock{lock_};
178 if (state_ == State::WRITE_LOCKED) {
180 read_waiters_.push_back(waiter);
183 if (!waiter.baton.timed_wait(duration)) {
184 // We timed out. Two cases:
185 // 1. We're still in the waiter list and we truly timed out
186 // 2. We're not in the waiter list anymore. This could happen if the baton
187 // times out but the mutex is unlocked before we reach this code. In
188 // this case we'll pretend we got the lock on time.
189 std::lock_guard<SpinLock> guard{lock_};
190 if (waiter.hook.is_linked()) {
191 read_waiters_.erase(read_waiters_.iterator_to(waiter));
198 (state_ == State::UNLOCKED && readers_ == 0) ||
199 (state_ == State::READ_LOCKED && readers_ > 0));
200 assert(read_waiters_.empty());
201 state_ = State::READ_LOCKED;
206 template <typename BatonType>
207 bool TimedRWMutex<BatonType>::try_read_lock() {
208 std::lock_guard<SpinLock> guard{lock_};
209 if (state_ != State::WRITE_LOCKED) {
211 (state_ == State::UNLOCKED && readers_ == 0) ||
212 (state_ == State::READ_LOCKED && readers_ > 0));
213 assert(read_waiters_.empty());
214 state_ = State::READ_LOCKED;
221 template <typename BatonType>
222 void TimedRWMutex<BatonType>::write_lock() {
223 std::unique_lock<folly::SpinLock> lock{lock_};
224 if (state_ == State::UNLOCKED) {
225 verify_unlocked_properties();
226 state_ = State::WRITE_LOCKED;
230 write_waiters_.push_back(waiter);
235 template <typename BatonType>
236 template <typename Rep, typename Period>
237 bool TimedRWMutex<BatonType>::timed_write_lock(
238 const std::chrono::duration<Rep, Period>& duration) {
239 std::unique_lock<folly::SpinLock> lock{lock_};
240 if (state_ == State::UNLOCKED) {
241 verify_unlocked_properties();
242 state_ = State::WRITE_LOCKED;
246 write_waiters_.push_back(waiter);
249 if (!waiter.baton.timed_wait(duration)) {
250 // We timed out. Two cases:
251 // 1. We're still in the waiter list and we truly timed out
252 // 2. We're not in the waiter list anymore. This could happen if the baton
253 // times out but the mutex is unlocked before we reach this code. In
254 // this case we'll pretend we got the lock on time.
255 std::lock_guard<SpinLock> guard{lock_};
256 if (waiter.hook.is_linked()) {
257 write_waiters_.erase(write_waiters_.iterator_to(waiter));
261 assert(state_ == State::WRITE_LOCKED);
265 template <typename BatonType>
266 bool TimedRWMutex<BatonType>::try_write_lock() {
267 std::lock_guard<SpinLock> guard{lock_};
268 if (state_ == State::UNLOCKED) {
269 verify_unlocked_properties();
270 state_ = State::WRITE_LOCKED;
276 template <typename BatonType>
277 void TimedRWMutex<BatonType>::unlock() {
278 std::lock_guard<SpinLock> guard{lock_};
279 assert(state_ != State::UNLOCKED);
281 (state_ == State::READ_LOCKED && readers_ > 0) ||
282 (state_ == State::WRITE_LOCKED && readers_ == 0));
283 if (state_ == State::READ_LOCKED) {
287 if (!read_waiters_.empty()) {
289 state_ == State::WRITE_LOCKED && readers_ == 0 &&
290 "read waiters can only accumulate while write locked");
291 state_ = State::READ_LOCKED;
292 readers_ = read_waiters_.size();
294 while (!read_waiters_.empty()) {
295 MutexWaiter& to_wake = read_waiters_.front();
296 read_waiters_.pop_front();
297 to_wake.baton.post();
299 } else if (readers_ == 0) {
300 if (!write_waiters_.empty()) {
301 assert(read_waiters_.empty());
302 state_ = State::WRITE_LOCKED;
304 // Wake a single writer (after releasing the spin lock)
305 MutexWaiter& to_wake = write_waiters_.front();
306 write_waiters_.pop_front();
307 to_wake.baton.post();
309 verify_unlocked_properties();
310 state_ = State::UNLOCKED;
313 assert(state_ == State::READ_LOCKED);
317 template <typename BatonType>
318 void TimedRWMutex<BatonType>::downgrade() {
319 std::lock_guard<SpinLock> guard{lock_};
320 assert(state_ == State::WRITE_LOCKED && readers_ == 0);
321 state_ = State::READ_LOCKED;
324 if (!read_waiters_.empty()) {
325 readers_ += read_waiters_.size();
327 while (!read_waiters_.empty()) {
328 MutexWaiter& to_wake = read_waiters_.front();
329 read_waiters_.pop_front();
330 to_wake.baton.post();