2 * Copyright 2017-present Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
19 #include <condition_variable>
22 #include <boost/intrusive/list.hpp>
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>
32 namespace parking_lot_detail {
34 struct WaitNodeBase : public boost::intrusive::list_base_hook<> {
36 const uint64_t lotid_;
38 // tricky: hold both bucket and node mutex to write, either to read
41 std::condition_variable cond_;
43 WaitNodeBase(uint64_t key, uint64_t lotid)
44 : key_(key), lotid_(lotid), signaled_(false) {}
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);
61 std::unique_lock<std::mutex> nodeLock(mutex_);
71 extern std::atomic<uint64_t> idallocator;
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
80 boost::intrusive::list<WaitNodeBase> waiters_;
82 static Bucket& bucketFor(uint64_t key);
85 } // namespace parking_lot_detail
87 enum class UnparkControl {
94 enum class ParkResult {
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.
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/
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
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.
120 template <typename Data = Unit>
122 const uint64_t lotid_;
123 ParkingLot(const ParkingLot&) = delete;
125 struct WaitNode : public parking_lot_detail::WaitNodeBase {
128 template <typename D>
129 WaitNode(uint64_t key, uint64_t lotid, D&& data)
130 : WaitNodeBase(key, lotid), data_(std::forward<Data>(data)) {}
134 ParkingLot() : lotid_(parking_lot_detail::idallocator++) {}
138 * Key is almost always the address of a variable.
140 * ToPark runs while holding the bucket lock: usually this
141 * is a check to see if we can sleep, by checking waiter bits.
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.
147 template <typename Key, typename D, typename ToPark, typename PreWait>
148 ParkResult park(const Key key, D&& data, ToPark&& toPark, PreWait&& preWait) {
151 std::forward<D>(data),
152 std::forward<ToPark>(toPark),
153 std::forward<PreWait>(preWait),
154 std::chrono::steady_clock::time_point::max());
164 ParkResult park_until(
169 std::chrono::time_point<Clock, Duration> deadline);
183 std::chrono::duration<Rep, Period>& timeout) {
186 std::forward<D>(data),
187 std::forward<ToPark>(toPark),
188 std::forward<PreWait>(preWait),
189 timeout + std::chrono::steady_clock::now());
195 * Key is the same uniqueaddress used in park(), and is used as a
196 * hash key for lookup of waiters.
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.
203 template <typename Key, typename Unparker>
204 void unpark(const Key key, Unparker&& func);
207 template <typename Data>
215 ParkResult ParkingLot<Data>::park_until(
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));
226 std::unique_lock<std::mutex> bucketLock(bucket.mutex_);
228 if (!std::forward<ToPark>(toPark)()) {
229 return ParkResult::Skip;
232 bucket.waiters_.push_back(node);
233 } // bucketLock scope
235 std::forward<PreWait>(preWait)();
237 auto status = node.wait(deadline);
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;
248 return ParkResult::Unpark;
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_);
258 for (auto iter = bucket.waiters_.begin(); iter != bucket.waiters_.end();) {
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);
270 if (result == UnparkControl::RemoveBreak ||
271 result == UnparkControl::RetainBreak) {