folly/synchronization/ParkingLot.h

   1 /*
   2  * Copyright 2017-present 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 <atomic>
  19 #include <condition_variable>
  20 #include <mutex>
  21
  22 #include <boost/intrusive/list.hpp>
  23
  24 #include <folly/Hash.h>
  25 #include <folly/Indestructible.h>
  26 #include <folly/Optional.h>
  27 #include <folly/Portability.h>
  28 #include <folly/Unit.h>
  29
  30 namespace folly {
  31
  32 namespace parking_lot_detail {
  33
  34 struct WaitNodeBase : public boost::intrusive::list_base_hook<> {
  35   const uint64_t key_;
  36   const uint64_t lotid_;
  37
  38   // tricky: hold both bucket and node mutex to write, either to read
  39   bool signaled_;
  40   std::mutex mutex_;
  41   std::condition_variable cond_;
  42
  43   WaitNodeBase(uint64_t key, uint64_t lotid)
  44       : key_(key), lotid_(lotid), signaled_(false) {}
  45
  46   template <typename Clock, typename Duration>
  47   std::cv_status wait(std::chrono::time_point<Clock, Duration> deadline) {
  48     std::cv_status status = std::cv_status::no_timeout;
  49     std::unique_lock<std::mutex> nodeLock(mutex_);
  50     while (!signaled_ && status != std::cv_status::timeout) {
  51       if (deadline != std::chrono::time_point<Clock, Duration>::max()) {
  52         status = cond_.wait_until(nodeLock, deadline);
  53       } else {
  54         cond_.wait(nodeLock);
  55       }
  56     }
  57     return status;
  58   }
  59
  60   void wake() {
  61     std::unique_lock<std::mutex> nodeLock(mutex_);
  62     signaled_ = true;
  63     cond_.notify_one();
  64   }
  65
  66   bool signaled() {
  67     return signaled_;
  68   }
  69 };
  70
  71 extern std::atomic<uint64_t> idallocator;
  72
  73 // Our emulated futex uses 4096 lists of wait nodes.  There are two levels
  74 // of locking: a per-list mutex that controls access to the list and a
  75 // per-node mutex, condvar, and bool that are used for the actual wakeups.
  76 // The per-node mutex allows us to do precise wakeups without thundering
  77 // herds.
  78 struct Bucket {
  79   std::mutex mutex_;
  80   boost::intrusive::list<WaitNodeBase> waiters_;
  81
  82   static Bucket& bucketFor(uint64_t key);
  83 };
  84
  85 } // namespace parking_lot_detail
  86
  87 enum class UnparkControl {
  88   RetainContinue,
  89   RemoveContinue,
  90   RetainBreak,
  91   RemoveBreak,
  92 };
  93
  94 enum class ParkResult {
  95   Skip,
  96   Unpark,
  97   Timeout,
  98 };
  99
 100 /*
 101  * ParkingLot provides an interface that is similar to Linux's futex
 102  * system call, but with additional functionality.  It is implemented
 103  * in a portable way on top of std::mutex and std::condition_variable.
 104  *
 105  * Additional reading:
 106  * https://webkit.org/blog/6161/locking-in-webkit/
 107  * https://github.com/WebKit/webkit/blob/master/Source/WTF/wtf/ParkingLot.h
 108  * https://locklessinc.com/articles/futex_cheat_sheet/
 109  *
 110  * The main difference from futex is that park/unpark take lambdas,
 111  * such that nearly anything can be done while holding the bucket
 112  * lock.  Unpark() lambda can also be used to wake up any number of
 113  * waiters.
 114  *
 115  * ParkingLot is templated on the data type, however, all ParkingLot
 116  * implementations are backed by a single static array of buckets to
 117  * avoid large memory overhead.  Lambdas will only ever be called on
 118  * the specific ParkingLot's nodes.
 119  */
 120 template <typename Data = Unit>
 121 class ParkingLot {
 122   const uint64_t lotid_;
 123   ParkingLot(const ParkingLot&) = delete;
 124
 125   struct WaitNode : public parking_lot_detail::WaitNodeBase {
 126     const Data data_;
 127
 128     template <typename D>
 129     WaitNode(uint64_t key, uint64_t lotid, D&& data)
 130         : WaitNodeBase(key, lotid), data_(std::forward<Data>(data)) {}
 131   };
 132
 133  public:
 134   ParkingLot() : lotid_(parking_lot_detail::idallocator++) {}
 135
 136   /* Park API
 137    *
 138    * Key is almost always the address of a variable.
 139    *
 140    * ToPark runs while holding the bucket lock: usually this
 141    * is a check to see if we can sleep, by checking waiter bits.
 142    *
 143    * PreWait is usually used to implement condition variable like
 144    * things, such that you can unlock the condition variable's lock at
 145    * the appropriate time.
 146    */
 147   template <typename Key, typename D, typename ToPark, typename PreWait>
 148   ParkResult park(const Key key, D&& data, ToPark&& toPark, PreWait&& preWait) {
 149     return park_until(
 150         key,
 151         std::forward<D>(data),
 152         std::forward<ToPark>(toPark),
 153         std::forward<PreWait>(preWait),
 154         std::chrono::steady_clock::time_point::max());
 155   }
 156
 157   template <
 158       typename Key,
 159       typename D,
 160       typename ToPark,
 161       typename PreWait,
 162       typename Clock,
 163       typename Duration>
 164   ParkResult park_until(
 165       const Key key,
 166       D&& data,
 167       ToPark&& toPark,
 168       PreWait&& preWait,
 169       std::chrono::time_point<Clock, Duration> deadline);
 170
 171   template <
 172       typename Key,
 173       typename D,
 174       typename ToPark,
 175       typename PreWait,
 176       typename Rep,
 177       typename Period>
 178   ParkResult park_for(
 179       const Key key,
 180       D&& data,
 181       ToPark&& toPark,
 182       PreWait&& preWait,
 183       std::chrono::duration<Rep, Period>& timeout) {
 184     return park_until(
 185         key,
 186         std::forward<D>(data),
 187         std::forward<ToPark>(toPark),
 188         std::forward<PreWait>(preWait),
 189         timeout + std::chrono::steady_clock::now());
 190   }
 191
 192   /*
 193    * Unpark API
 194    *
 195    * Key is the same uniqueaddress used in park(), and is used as a
 196    * hash key for lookup of waiters.
 197    *
 198    * Unparker is a function that is given the Data parameter, and
 199    * returns an UnparkControl.  The Remove* results will remove and
 200    * wake the waiter, the Ignore/Stop results will not, while stopping
 201    * or continuing iteration of the waiter list.
 202    */
 203   template <typename Key, typename Unparker>
 204   void unpark(const Key key, Unparker&& func);
 205 };
 206
 207 template <typename Data>
 208 template <
 209     typename Key,
 210     typename D,
 211     typename ToPark,
 212     typename PreWait,
 213     typename Clock,
 214     typename Duration>
 215 ParkResult ParkingLot<Data>::park_until(
 216     const Key bits,
 217     D&& data,
 218     ToPark&& toPark,
 219     PreWait&& preWait,
 220     std::chrono::time_point<Clock, Duration> deadline) {
 221   auto key = hash::twang_mix64(uint64_t(bits));
 222   auto& bucket = parking_lot_detail::Bucket::bucketFor(key);
 223   WaitNode node(key, lotid_, std::forward<D>(data));
 224
 225   {
 226     std::unique_lock<std::mutex> bucketLock(bucket.mutex_);
 227
 228     if (!std::forward<ToPark>(toPark)()) {
 229       return ParkResult::Skip;
 230     }
 231
 232     bucket.waiters_.push_back(node);
 233   } // bucketLock scope
 234
 235   std::forward<PreWait>(preWait)();
 236
 237   auto status = node.wait(deadline);
 238
 239   if (status == std::cv_status::timeout) {
 240     // it's not really a timeout until we unlink the unsignaled node
 241     std::unique_lock<std::mutex> bucketLock(bucket.mutex_);
 242     if (!node.signaled()) {
 243       bucket.waiters_.erase(bucket.waiters_.iterator_to(node));
 244       return ParkResult::Timeout;
 245     }
 246   }
 247
 248   return ParkResult::Unpark;
 249 }
 250
 251 template <typename Data>
 252 template <typename Key, typename Func>
 253 void ParkingLot<Data>::unpark(const Key bits, Func&& func) {
 254   auto key = hash::twang_mix64(uint64_t(bits));
 255   auto& bucket = parking_lot_detail::Bucket::bucketFor(key);
 256   std::unique_lock<std::mutex> bucketLock(bucket.mutex_);
 257
 258   for (auto iter = bucket.waiters_.begin(); iter != bucket.waiters_.end();) {
 259     auto current = iter;
 260     auto& node = *static_cast<WaitNode*>(&*iter++);
 261     if (node.key_ == key && node.lotid_ == lotid_) {
 262       auto result = std::forward<Func>(func)(node.data_);
 263       if (result == UnparkControl::RemoveBreak ||
 264           result == UnparkControl::RemoveContinue) {
 265         // we unlink, but waiter destroys the node
 266         bucket.waiters_.erase(current);
 267
 268         node.wake();
 269       }
 270       if (result == UnparkControl::RemoveBreak ||
 271           result == UnparkControl::RetainBreak) {
 272         return;
 273       }
 274     }
 275   }
 276 }
 277
 278 } // namespace folly