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