folly/fibers/TimedMutex.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 <folly/IntrusiveList.h>
  19 #include <folly/SpinLock.h>
  20 #include <folly/fibers/GenericBaton.h>
  21
  22 namespace folly {
  23 namespace fibers {
  24
  25 /**
  26  * @class TimedMutex
  27  *
  28  * Like mutex but allows timed_lock in addition to lock and try_lock.
  29  **/
  30 class TimedMutex {
  31  public:
  32   TimedMutex() {}
  33
  34   ~TimedMutex() {
  35     DCHECK(threadWaiters_.empty());
  36     DCHECK(fiberWaiters_.empty());
  37     DCHECK(notifiedFiber_ == nullptr);
  38   }
  39
  40   TimedMutex(const TimedMutex& rhs) = delete;
  41   TimedMutex& operator=(const TimedMutex& rhs) = delete;
  42   TimedMutex(TimedMutex&& rhs) = delete;
  43   TimedMutex& operator=(TimedMutex&& rhs) = delete;
  44
  45   // Lock the mutex. The thread / fiber is blocked until the mutex is free
  46   void lock();
  47
  48   // Lock the mutex. The thread / fiber will be blocked for a time duration.
  49   //
  50   // @return        true if the mutex was locked, false otherwise
  51   template <typename Rep, typename Period>
  52   bool timed_lock(const std::chrono::duration<Rep, Period>& duration);
  53
  54   // Try to obtain lock without blocking the thread or fiber
  55   bool try_lock();
  56
  57   // Unlock the mutex and wake up a waiter if there is one
  58   void unlock();
  59
  60  private:
  61   enum class LockResult { SUCCESS, TIMEOUT, STOLEN };
  62
  63   template <typename WaitFunc>
  64   LockResult lockHelper(WaitFunc&& waitFunc);
  65
  66   // represents a waiter waiting for the lock. The waiter waits on the
  67   // baton until it is woken up by a post or timeout expires.
  68   struct MutexWaiter {
  69     Baton baton;
  70     folly::IntrusiveListHook hook;
  71   };
  72
  73   using MutexWaiterList = folly::IntrusiveList<MutexWaiter, &MutexWaiter::hook>;
  74
  75   folly::SpinLock lock_; //< lock to protect waiter list
  76   bool locked_ = false; //< is this locked by some thread?
  77   MutexWaiterList threadWaiters_; //< list of waiters
  78   MutexWaiterList fiberWaiters_; //< list of waiters
  79   MutexWaiter* notifiedFiber_{nullptr}; //< Fiber waiter which has been notified
  80 };
  81
  82 /**
  83  * @class TimedRWMutex
  84  *
  85  * A readers-writer lock which allows multiple readers to hold the
  86  * lock simultaneously or only one writer.
  87  *
  88  * NOTE: This is a reader-preferred RWLock i.e. readers are give priority
  89  * when there are both readers and writers waiting to get the lock.
  90  **/
  91 template <typename BatonType>
  92 class TimedRWMutex {
  93  public:
  94   TimedRWMutex() = default;
  95   ~TimedRWMutex() = default;
  96
  97   TimedRWMutex(const TimedRWMutex& rhs) = delete;
  98   TimedRWMutex& operator=(const TimedRWMutex& rhs) = delete;
  99   TimedRWMutex(TimedRWMutex&& rhs) = delete;
 100   TimedRWMutex& operator=(TimedRWMutex&& rhs) = delete;
 101
 102   // Lock for shared access. The thread / fiber is blocked until the lock
 103   // can be acquired.
 104   void read_lock();
 105
 106   // Like read_lock except the thread /fiber is blocked for a time duration
 107   // @return        true if locked successfully, false otherwise.
 108   template <typename Rep, typename Period>
 109   bool timed_read_lock(const std::chrono::duration<Rep, Period>& duration);
 110
 111   // Like read_lock but doesn't block the thread / fiber if the lock can't
 112   // be acquired.
 113   // @return        true if lock was acquired, false otherwise.
 114   bool try_read_lock();
 115
 116   // Obtain an exclusive lock. The thread / fiber is blocked until the lock
 117   // is available.
 118   void write_lock();
 119
 120   // Like write_lock except the thread / fiber is blocked for a time duration
 121   // @return        true if locked successfully, false otherwise.
 122   template <typename Rep, typename Period>
 123   bool timed_write_lock(const std::chrono::duration<Rep, Period>& duration);
 124
 125   // Like write_lock but doesn't block the thread / fiber if the lock cant be
 126   // obtained.
 127   // @return        true if lock was acquired, false otherwise.
 128   bool try_write_lock();
 129
 130   // Wrapper for write_lock() for compatibility with Mutex
 131   void lock() {
 132     write_lock();
 133   }
 134
 135   // Realease the lock. The thread / fiber will wake up all readers if there are
 136   // any. If there are waiting writers then only one of them will be woken up.
 137   // NOTE: readers are given priority over writers (see above comment)
 138   void unlock();
 139
 140   // Downgrade the lock. The thread / fiber will wake up all readers if there
 141   // are any.
 142   void downgrade();
 143
 144   class ReadHolder {
 145    public:
 146     explicit ReadHolder(TimedRWMutex& lock) : lock_(&lock) {
 147       lock_->read_lock();
 148     }
 149
 150     ~ReadHolder() {
 151       if (lock_) {
 152         lock_->unlock();
 153       }
 154     }
 155
 156     ReadHolder(const ReadHolder& rhs) = delete;
 157     ReadHolder& operator=(const ReadHolder& rhs) = delete;
 158     ReadHolder(ReadHolder&& rhs) = delete;
 159     ReadHolder& operator=(ReadHolder&& rhs) = delete;
 160
 161    private:
 162     TimedRWMutex* lock_;
 163   };
 164
 165   class WriteHolder {
 166    public:
 167     explicit WriteHolder(TimedRWMutex& lock) : lock_(&lock) {
 168       lock_->write_lock();
 169     }
 170
 171     ~WriteHolder() {
 172       if (lock_) {
 173         lock_->unlock();
 174       }
 175     }
 176
 177     WriteHolder(const WriteHolder& rhs) = delete;
 178     WriteHolder& operator=(const WriteHolder& rhs) = delete;
 179     WriteHolder(WriteHolder&& rhs) = delete;
 180     WriteHolder& operator=(WriteHolder&& rhs) = delete;
 181
 182    private:
 183     TimedRWMutex* lock_;
 184   };
 185
 186  private:
 187   // invariants that must hold when the lock is not held by anyone
 188   void verify_unlocked_properties() {
 189     assert(readers_ == 0);
 190     assert(read_waiters_.empty());
 191     assert(write_waiters_.empty());
 192   }
 193
 194   // Different states the lock can be in
 195   enum class State {
 196     UNLOCKED,
 197     READ_LOCKED,
 198     WRITE_LOCKED,
 199   };
 200
 201   typedef boost::intrusive::list_member_hook<> MutexWaiterHookType;
 202
 203   // represents a waiter waiting for the lock.
 204   struct MutexWaiter {
 205     BatonType baton;
 206     MutexWaiterHookType hook;
 207   };
 208
 209   typedef boost::intrusive::
 210       member_hook<MutexWaiter, MutexWaiterHookType, &MutexWaiter::hook>
 211           MutexWaiterHook;
 212
 213   typedef boost::intrusive::list<
 214       MutexWaiter,
 215       MutexWaiterHook,
 216       boost::intrusive::constant_time_size<true>>
 217       MutexWaiterList;
 218
 219   folly::SpinLock lock_; //< lock protecting the internal state
 220   // (state_, read_waiters_, etc.)
 221   State state_ = State::UNLOCKED;
 222
 223   uint32_t readers_ = 0; //< Number of readers who have the lock
 224
 225   MutexWaiterList write_waiters_; //< List of thread / fibers waiting for
 226   //  exclusive access
 227
 228   MutexWaiterList read_waiters_; //< List of thread / fibers waiting for
 229   //  shared access
 230 };
 231 }
 232 }
 233
 234 #include "TimedMutex-inl.h"