1/*
2 * Copyright (C) 2015 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#ifndef WTF_Condition_h
27#define WTF_Condition_h
28
29#include <chrono>
30#include <functional>
31#include <wtf/CurrentTime.h>
32#include <wtf/Noncopyable.h>
33#include <wtf/ParkingLot.h>
34
35namespace WTF {
36
37// This is a condition variable that is suitable for use with any lock-like object, including
38// our own WTF::Lock. It features standard wait()/notifyOne()/notifyAll() methods in addition to
39// a variety of wait-with-timeout methods. This includes methods that use WTF's own notion of
40// time, like wall-clock time (i.e. currentTime()) and monotonic time (i.e.
41// monotonicallyIncreasingTime()). This is a very efficient condition variable. It only requires
42// one byte of memory. notifyOne() and notifyAll() require just a load and branch for the fast
43// case where no thread is waiting. This condition variable, when used with WTF::Lock, can
44// outperform a system condition variable and lock by up to 58x.
45
46// This is a struct without a constructor or destructor so that it can be statically initialized.
47// Use Lock in instance variables.
48struct ConditionBase {
49 typedef ParkingLot::Clock Clock;
50
51 // Wait on a parking queue while releasing the given lock. It will unlock the lock just before
52 // parking, and relock it upon wakeup. Returns true if we woke up due to some call to
53 // notifyOne() or notifyAll(). Returns false if we woke up due to a timeout. Note that this form
54 // of waitUntil() has some quirks:
55 //
56 // No spurious wake-up: in order for this to return before the timeout, some notifyOne() or
57 // notifyAll() call must have happened. No scenario other than timeout or notify can lead to this
58 // method returning. This means, for example, that you can't use pthread cancelation or signals to
59 // cause early return.
60 //
61 // Past timeout: it's possible for waitUntil() to be called with a timeout in the past. In that
62 // case, waitUntil() will still release the lock and reacquire it. waitUntil() will always return
63 // false in that case. This is subtly different from some pthread_cond_timedwait() implementations,
64 // which may not release the lock for past timeout. But, this behavior is consistent with OpenGroup
65 // documentation for timedwait().
66 template<typename LockType>
67 bool waitUntil(LockType& lock, Clock::time_point timeout)
68 {
69 bool result;
70 if (timeout < Clock::now()) {
71 lock.unlock();
72 result = false;
73 } else {
74 result = ParkingLot::parkConditionally(
75 &m_hasWaiters,
76 [this] () -> bool {
77 // Let everyone know that we will be waiting. Do this while we hold the queue lock,
78 // to prevent races with notifyOne().
79 m_hasWaiters.store(true);
80 return true;
81 },
82 [&lock] () { lock.unlock(); },
83 timeout);
84 }
85 lock.lock();
86 return result;
87 }
88
89 // Wait until the given predicate is satisfied. Returns true if it is satisfied in the end.
90 // May return early due to timeout.
91 template<typename LockType, typename Functor>
92 bool waitUntil(LockType& lock, Clock::time_point timeout, const Functor& predicate)
93 {
94 while (!predicate()) {
95 if (!waitUntil(lock, timeout))
96 return predicate();
97 }
98 return true;
99 }
100
101 // Wait until the given predicate is satisfied. Returns true if it is satisfied in the end.
102 // May return early due to timeout.
103 template<typename LockType, typename DurationType, typename Functor>
104 bool waitFor(
105 LockType& lock, const DurationType& relativeTimeout, const Functor& predicate)
106 {
107 return waitUntil(lock, absoluteFromRelative(relativeTimeout), predicate);
108 }
109
110 template<typename LockType>
111 void wait(LockType& lock)
112 {
113 waitUntil(lock, Clock::time_point::max());
114 }
115
116 template<typename LockType, typename Functor>
117 void wait(LockType& lock, const Functor& predicate)
118 {
119 while (!predicate())
120 wait(lock);
121 }
122
123 template<typename LockType, typename TimeType>
124 bool waitUntil(LockType& lock, const TimeType& timeout)
125 {
126 if (timeout == TimeType::max()) {
127 wait(lock);
128 return true;
129 }
130 return waitForImpl(lock, timeout - TimeType::clock::now());
131 }
132
133 template<typename LockType>
134 bool waitUntilWallClockSeconds(LockType& lock, double absoluteTimeoutSeconds)
135 {
136 return waitForSecondsImpl(lock, absoluteTimeoutSeconds - currentTime());
137 }
138
139 template<typename LockType>
140 bool waitUntilMonotonicClockSeconds(LockType& lock, double absoluteTimeoutSeconds)
141 {
142 return waitForSecondsImpl(lock, absoluteTimeoutSeconds - monotonicallyIncreasingTime());
143 }
144
145 // Note that this method is extremely fast when nobody is waiting. It is not necessary to try to
146 // avoid calling this method.
147 void notifyOne()
148 {
149 if (!m_hasWaiters.load()) {
150 // At this exact instant, there is nobody waiting on this condition. The way to visualize
151 // this is that if unparkOne() ran to completion without obstructions at this moment, it
152 // wouldn't wake anyone up. Hence, we have nothing to do!
153 return;
154 }
155
156 ParkingLot::unparkOne(
157 &m_hasWaiters,
158 [this] (bool, bool mayHaveMoreThreads) {
159 if (!mayHaveMoreThreads)
160 m_hasWaiters.store(false);
161 });
162 }
163
164 void notifyAll()
165 {
166 if (!m_hasWaiters.load()) {
167 // See above.
168 return;
169 }
170
171 // It's totally safe for us to set this to false without any locking, because this thread is
172 // guaranteed to then unparkAll() anyway. So, if there is a race with some thread calling
173 // wait() just before this store happens, that thread is guaranteed to be awoken by the call to
174 // unparkAll(), below.
175 m_hasWaiters.store(false);
176
177 ParkingLot::unparkAll(&m_hasWaiters);
178 }
179
180protected:
181 template<typename LockType>
182 bool waitForSecondsImpl(LockType& lock, double relativeTimeoutSeconds)
183 {
184 double relativeTimeoutNanoseconds = relativeTimeoutSeconds * (1000.0 * 1000.0 * 1000.0);
185
186 if (!(relativeTimeoutNanoseconds > 0)) {
187 // This handles insta-timeouts as well as NaN.
188 lock.unlock();
189 lock.lock();
190 return false;
191 }
192
193 if (relativeTimeoutNanoseconds > static_cast<double>(std::numeric_limits<int64_t>::max())) {
194 // If the timeout in nanoseconds cannot be expressed using a 64-bit integer, then we
195 // might as well wait forever.
196 wait(lock);
197 return true;
198 }
199
200 auto relativeTimeout =
201 std::chrono::nanoseconds(static_cast<int64_t>(relativeTimeoutNanoseconds));
202
203 return waitForImpl(lock, relativeTimeout);
204 }
205
206 template<typename LockType, typename DurationType>
207 bool waitForImpl(LockType& lock, const DurationType& relativeTimeout)
208 {
209 return waitUntil(lock, absoluteFromRelative(relativeTimeout));
210 }
211
212 template<typename DurationType>
213 Clock::time_point absoluteFromRelative(const DurationType& relativeTimeout)
214 {
215 if (relativeTimeout < DurationType::zero())
216 return Clock::time_point::min();
217
218 if (relativeTimeout > Clock::duration::max()) {
219 // This is highly unlikely. But if it happens, we want to not do anything dumb. Sleeping
220 // without a timeout seems sensible when the timeout duration is greater than what can be
221 // expressed using steady_clock.
222 return Clock::time_point::max();
223 }
224
225 Clock::duration myRelativeTimeout =
226 std::chrono::duration_cast<Clock::duration>(relativeTimeout);
227
228 return Clock::now() + myRelativeTimeout;
229 }
230
231 Atomic<bool> m_hasWaiters;
232};
233
234class Condition : public ConditionBase {
235 WTF_MAKE_NONCOPYABLE(Condition);
236public:
237 Condition()
238 {
239 m_hasWaiters.store(false);
240 }
241};
242
243typedef ConditionBase StaticCondition;
244
245} // namespace WTF
246
247using WTF::Condition;
248using WTF::StaticCondition;
249
250#endif // WTF_Condition_h
251
252