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 #include <mutex>
  19
  20 namespace folly {
  21 namespace fibers {
  22
  23 //
  24 // TimedMutex implementation
  25 //
  26
  27 template <typename WaitFunc>
  28 TimedMutex::LockResult TimedMutex::lockHelper(WaitFunc&& waitFunc) {
  29   std::unique_lock<folly::SpinLock> lock(lock_);
  30   if (!locked_) {
  31     locked_ = true;
  32     return LockResult::SUCCESS;
  33   }
  34
  35   const auto isOnFiber = onFiber();
  36
  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;
  44   }
  45
  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.
  49   MutexWaiter waiter;
  50   if (isOnFiber) {
  51     fiberWaiters_.push_back(waiter);
  52   } else {
  53     threadWaiters_.push_back(waiter);
  54   }
  55
  56   lock.unlock();
  57
  58   if (!waitFunc(waiter)) {
  59     return LockResult::TIMEOUT;
  60   }
  61
  62   if (isOnFiber) {
  63     auto lockStolen = [&] {
  64       std::lock_guard<folly::SpinLock> lg(lock_);
  65
  66       auto stolen = notifiedFiber_ != &waiter;
  67       notifiedFiber_ = nullptr;
  68       return stolen;
  69     }();
  70
  71     if (lockStolen) {
  72       return LockResult::STOLEN;
  73     }
  74   }
  75
  76   return LockResult::SUCCESS;
  77 }
  78
  79 inline void TimedMutex::lock() {
  80   auto result = lockHelper([](MutexWaiter& waiter) {
  81     waiter.baton.wait();
  82     return true;
  83   });
  84
  85   DCHECK(result != LockResult::TIMEOUT);
  86   if (result == LockResult::SUCCESS) {
  87     return;
  88   }
  89   lock();
  90 }
  91
  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
 101       //    this
 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();
 106         return false;
 107       }
 108     }
 109     return true;
 110   });
 111
 112   switch (result) {
 113     case LockResult::SUCCESS:
 114       return true;
 115     case LockResult::TIMEOUT:
 116       return false;
 117     case LockResult::STOLEN:
 118       // We don't respect the duration if lock was stolen
 119       lock();
 120       return true;
 121   }
 122   assume_unreachable();
 123 }
 124
 125 inline bool TimedMutex::try_lock() {
 126   std::lock_guard<folly::SpinLock> lg(lock_);
 127   if (locked_) {
 128     return false;
 129   }
 130   locked_ = true;
 131   return true;
 132 }
 133
 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();
 145   } else {
 146     locked_ = false;
 147   }
 148 }
 149
 150 //
 151 // TimedRWMutex implementation
 152 //
 153
 154 template <typename BatonType>
 155 void TimedRWMutex<BatonType>::read_lock() {
 156   std::unique_lock<folly::SpinLock> lock{lock_};
 157   if (state_ == State::WRITE_LOCKED) {
 158     MutexWaiter waiter;
 159     read_waiters_.push_back(waiter);
 160     lock.unlock();
 161     waiter.baton.wait();
 162     assert(state_ == State::READ_LOCKED);
 163     return;
 164   }
 165   assert(
 166       (state_ == State::UNLOCKED && readers_ == 0) ||
 167       (state_ == State::READ_LOCKED && readers_ > 0));
 168   assert(read_waiters_.empty());
 169   state_ = State::READ_LOCKED;
 170   readers_ += 1;
 171 }
 172
 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) {
 179     MutexWaiter waiter;
 180     read_waiters_.push_back(waiter);
 181     lock.unlock();
 182
 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));
 192         return false;
 193       }
 194     }
 195     return true;
 196   }
 197   assert(
 198       (state_ == State::UNLOCKED && readers_ == 0) ||
 199       (state_ == State::READ_LOCKED && readers_ > 0));
 200   assert(read_waiters_.empty());
 201   state_ = State::READ_LOCKED;
 202   readers_ += 1;
 203   return true;
 204 }
 205
 206 template <typename BatonType>
 207 bool TimedRWMutex<BatonType>::try_read_lock() {
 208   std::lock_guard<SpinLock> guard{lock_};
 209   if (state_ != State::WRITE_LOCKED) {
 210     assert(
 211         (state_ == State::UNLOCKED && readers_ == 0) ||
 212         (state_ == State::READ_LOCKED && readers_ > 0));
 213     assert(read_waiters_.empty());
 214     state_ = State::READ_LOCKED;
 215     readers_ += 1;
 216     return true;
 217   }
 218   return false;
 219 }
 220
 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;
 227     return;
 228   }
 229   MutexWaiter waiter;
 230   write_waiters_.push_back(waiter);
 231   lock.unlock();
 232   waiter.baton.wait();
 233 }
 234
 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;
 243     return true;
 244   }
 245   MutexWaiter waiter;
 246   write_waiters_.push_back(waiter);
 247   lock.unlock();
 248
 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));
 258       return false;
 259     }
 260   }
 261   assert(state_ == State::WRITE_LOCKED);
 262   return true;
 263 }
 264
 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;
 271     return true;
 272   }
 273   return false;
 274 }
 275
 276 template <typename BatonType>
 277 void TimedRWMutex<BatonType>::unlock() {
 278   std::lock_guard<SpinLock> guard{lock_};
 279   assert(state_ != State::UNLOCKED);
 280   assert(
 281       (state_ == State::READ_LOCKED && readers_ > 0) ||
 282       (state_ == State::WRITE_LOCKED && readers_ == 0));
 283   if (state_ == State::READ_LOCKED) {
 284     readers_ -= 1;
 285   }
 286
 287   if (!read_waiters_.empty()) {
 288     assert(
 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();
 293
 294     while (!read_waiters_.empty()) {
 295       MutexWaiter& to_wake = read_waiters_.front();
 296       read_waiters_.pop_front();
 297       to_wake.baton.post();
 298     }
 299   } else if (readers_ == 0) {
 300     if (!write_waiters_.empty()) {
 301       assert(read_waiters_.empty());
 302       state_ = State::WRITE_LOCKED;
 303
 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();
 308     } else {
 309       verify_unlocked_properties();
 310       state_ = State::UNLOCKED;
 311     }
 312   } else {
 313     assert(state_ == State::READ_LOCKED);
 314   }
 315 }
 316
 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;
 322   readers_ += 1;
 323
 324   if (!read_waiters_.empty()) {
 325     readers_ += read_waiters_.size();
 326
 327     while (!read_waiters_.empty()) {
 328       MutexWaiter& to_wake = read_waiters_.front();
 329       read_waiters_.pop_front();
 330       to_wake.baton.post();
 331     }
 332   }
 333 }
 334 }
 335 }