2017
[folly.git] / folly / fibers / TimedMutex-inl.h
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 #pragma once
17
18 namespace folly {
19 namespace fibers {
20
21 //
22 // TimedMutex implementation
23 //
24
25 template <typename WaitFunc>
26 TimedMutex::LockResult TimedMutex::lockHelper(WaitFunc&& waitFunc) {
27   std::unique_lock<folly::SpinLock> lock(lock_);
28   if (!locked_) {
29     locked_ = true;
30     return LockResult::SUCCESS;
31   }
32
33   const auto isOnFiber = onFiber();
34
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;
42   }
43
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.
47   MutexWaiter waiter;
48   if (isOnFiber) {
49     fiberWaiters_.push_back(waiter);
50   } else {
51     threadWaiters_.push_back(waiter);
52   }
53
54   lock.unlock();
55
56   if (!waitFunc(waiter)) {
57     return LockResult::TIMEOUT;
58   }
59
60   if (isOnFiber) {
61     auto lockStolen = [&] {
62       std::lock_guard<folly::SpinLock> lg(lock_);
63
64       auto stolen = notifiedFiber_ != &waiter;
65       notifiedFiber_ = nullptr;
66       return stolen;
67     }();
68
69     if (lockStolen) {
70       return LockResult::STOLEN;
71     }
72   }
73
74   return LockResult::SUCCESS;
75 }
76
77 inline void TimedMutex::lock() {
78   auto result = lockHelper([](MutexWaiter& waiter) {
79     waiter.baton.wait();
80     return true;
81   });
82
83   DCHECK(result != LockResult::TIMEOUT);
84   if (result == LockResult::SUCCESS) {
85     return;
86   }
87   lock();
88 }
89
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
99       //    this
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();
104         return false;
105       }
106     }
107     return true;
108   });
109
110   switch (result) {
111     case LockResult::SUCCESS:
112       return true;
113     case LockResult::TIMEOUT:
114       return false;
115     case LockResult::STOLEN:
116       // We don't respect the duration if lock was stolen
117       lock();
118       return true;
119   }
120   assume_unreachable();
121 }
122
123 inline bool TimedMutex::try_lock() {
124   std::lock_guard<folly::SpinLock> lg(lock_);
125   if (locked_) {
126     return false;
127   }
128   locked_ = true;
129   return true;
130 }
131
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();
143   } else {
144     locked_ = false;
145   }
146 }
147
148 //
149 // TimedRWMutex implementation
150 //
151
152 template <typename BatonType>
153 void TimedRWMutex<BatonType>::read_lock() {
154   pthread_spin_lock(&lock_);
155   if (state_ == State::WRITE_LOCKED) {
156     MutexWaiter waiter;
157     read_waiters_.push_back(waiter);
158     pthread_spin_unlock(&lock_);
159     waiter.baton.wait();
160     assert(state_ == State::READ_LOCKED);
161     return;
162   }
163   assert(
164       (state_ == State::UNLOCKED && readers_ == 0) ||
165       (state_ == State::READ_LOCKED && readers_ > 0));
166   assert(read_waiters_.empty());
167   state_ = State::READ_LOCKED;
168   readers_ += 1;
169   pthread_spin_unlock(&lock_);
170 }
171
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) {
178     MutexWaiter waiter;
179     read_waiters_.push_back(waiter);
180     pthread_spin_unlock(&lock_);
181
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_);
192         return false;
193       }
194       pthread_spin_unlock(&lock_);
195     }
196     return true;
197   }
198   assert(
199       (state_ == State::UNLOCKED && readers_ == 0) ||
200       (state_ == State::READ_LOCKED && readers_ > 0));
201   assert(read_waiters_.empty());
202   state_ = State::READ_LOCKED;
203   readers_ += 1;
204   pthread_spin_unlock(&lock_);
205   return true;
206 }
207
208 template <typename BatonType>
209 bool TimedRWMutex<BatonType>::try_read_lock() {
210   pthread_spin_lock(&lock_);
211   if (state_ != State::WRITE_LOCKED) {
212     assert(
213         (state_ == State::UNLOCKED && readers_ == 0) ||
214         (state_ == State::READ_LOCKED && readers_ > 0));
215     assert(read_waiters_.empty());
216     state_ = State::READ_LOCKED;
217     readers_ += 1;
218     pthread_spin_unlock(&lock_);
219     return true;
220   }
221   pthread_spin_unlock(&lock_);
222   return false;
223 }
224
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_);
232     return;
233   }
234   MutexWaiter waiter;
235   write_waiters_.push_back(waiter);
236   pthread_spin_unlock(&lock_);
237   waiter.baton.wait();
238 }
239
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_);
249     return true;
250   }
251   MutexWaiter waiter;
252   write_waiters_.push_back(waiter);
253   pthread_spin_unlock(&lock_);
254
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_);
265       return false;
266     }
267     pthread_spin_unlock(&lock_);
268   }
269   assert(state_ == State::WRITE_LOCKED);
270   return true;
271 }
272
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_);
280     return true;
281   }
282   pthread_spin_unlock(&lock_);
283   return false;
284 }
285
286 template <typename BatonType>
287 void TimedRWMutex<BatonType>::unlock() {
288   pthread_spin_lock(&lock_);
289   assert(state_ != State::UNLOCKED);
290   assert(
291       (state_ == State::READ_LOCKED && readers_ > 0) ||
292       (state_ == State::WRITE_LOCKED && readers_ == 0));
293   if (state_ == State::READ_LOCKED) {
294     readers_ -= 1;
295   }
296
297   if (!read_waiters_.empty()) {
298     assert(
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();
303
304     while (!read_waiters_.empty()) {
305       MutexWaiter& to_wake = read_waiters_.front();
306       read_waiters_.pop_front();
307       to_wake.baton.post();
308     }
309   } else if (readers_ == 0) {
310     if (!write_waiters_.empty()) {
311       assert(read_waiters_.empty());
312       state_ = State::WRITE_LOCKED;
313
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();
318     } else {
319       verify_unlocked_properties();
320       state_ = State::UNLOCKED;
321     }
322   } else {
323     assert(state_ == State::READ_LOCKED);
324   }
325   pthread_spin_unlock(&lock_);
326 }
327
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;
333   readers_ += 1;
334
335   if (!read_waiters_.empty()) {
336     readers_ += read_waiters_.size();
337
338     while (!read_waiters_.empty()) {
339       MutexWaiter& to_wake = read_waiters_.front();
340       read_waiters_.pop_front();
341       to_wake.baton.post();
342     }
343   }
344   pthread_spin_unlock(&lock_);
345 }
346 }
347 }