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 }