4db3e29a3b11eee5cf4705658764d157d65b07b0
[WebKit-https.git] / Source / WTF / wtf / Condition.h
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
35 namespace 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.
48 struct 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).wasUnparked;
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     template<typename LockType, typename Functor>
146     bool waitForSeconds(LockType& lock, double relativeTimeoutSeconds, const Functor& predicate)
147     {
148         double relativeTimeoutNanoseconds = relativeTimeoutSeconds * (1000.0 * 1000.0 * 1000.0);
149         
150         if (!(relativeTimeoutNanoseconds > 0)) {
151             // This handles insta-timeouts as well as NaN.
152             lock.unlock();
153             lock.lock();
154             return false;
155         }
156
157         if (relativeTimeoutNanoseconds > static_cast<double>(std::numeric_limits<int64_t>::max())) {
158             // If the timeout in nanoseconds cannot be expressed using a 64-bit integer, then we
159             // might as well wait forever.
160             wait(lock, predicate);
161             return true;
162         }
163         
164         auto relativeTimeout =
165             std::chrono::nanoseconds(static_cast<int64_t>(relativeTimeoutNanoseconds));
166
167         return waitFor(lock, relativeTimeout, predicate);
168     }
169
170     // Note that this method is extremely fast when nobody is waiting. It is not necessary to try to
171     // avoid calling this method.
172     void notifyOne()
173     {
174         if (!m_hasWaiters.load()) {
175             // At this exact instant, there is nobody waiting on this condition. The way to visualize
176             // this is that if unparkOne() ran to completion without obstructions at this moment, it
177             // wouldn't wake anyone up. Hence, we have nothing to do!
178             return;
179         }
180         
181         ParkingLot::unparkOne(
182             &m_hasWaiters,
183             [this] (ParkingLot::UnparkResult result) -> intptr_t {
184                 if (!result.mayHaveMoreThreads)
185                     m_hasWaiters.store(false);
186                 return 0;
187             });
188     }
189     
190     void notifyAll()
191     {
192         if (!m_hasWaiters.load()) {
193             // See above.
194             return;
195         }
196
197         // It's totally safe for us to set this to false without any locking, because this thread is
198         // guaranteed to then unparkAll() anyway. So, if there is a race with some thread calling
199         // wait() just before this store happens, that thread is guaranteed to be awoken by the call to
200         // unparkAll(), below.
201         m_hasWaiters.store(false);
202         
203         ParkingLot::unparkAll(&m_hasWaiters);
204     }
205     
206 protected:
207     template<typename LockType>
208     bool waitForSecondsImpl(LockType& lock, double relativeTimeoutSeconds)
209     {
210         double relativeTimeoutNanoseconds = relativeTimeoutSeconds * (1000.0 * 1000.0 * 1000.0);
211         
212         if (!(relativeTimeoutNanoseconds > 0)) {
213             // This handles insta-timeouts as well as NaN.
214             lock.unlock();
215             lock.lock();
216             return false;
217         }
218
219         if (relativeTimeoutNanoseconds > static_cast<double>(std::numeric_limits<int64_t>::max())) {
220             // If the timeout in nanoseconds cannot be expressed using a 64-bit integer, then we
221             // might as well wait forever.
222             wait(lock);
223             return true;
224         }
225         
226         auto relativeTimeout =
227             std::chrono::nanoseconds(static_cast<int64_t>(relativeTimeoutNanoseconds));
228
229         return waitForImpl(lock, relativeTimeout);
230     }
231     
232     template<typename LockType, typename DurationType>
233     bool waitForImpl(LockType& lock, const DurationType& relativeTimeout)
234     {
235         return waitUntil(lock, absoluteFromRelative(relativeTimeout));
236     }
237
238     template<typename DurationType>
239     Clock::time_point absoluteFromRelative(const DurationType& relativeTimeout)
240     {
241         if (relativeTimeout < DurationType::zero())
242             return Clock::time_point::min();
243
244         if (relativeTimeout > Clock::duration::max()) {
245             // This is highly unlikely. But if it happens, we want to not do anything dumb. Sleeping
246             // without a timeout seems sensible when the timeout duration is greater than what can be
247             // expressed using steady_clock.
248             return Clock::time_point::max();
249         }
250         
251         Clock::duration myRelativeTimeout =
252             std::chrono::duration_cast<Clock::duration>(relativeTimeout);
253
254         return Clock::now() + myRelativeTimeout;
255     }
256
257     Atomic<bool> m_hasWaiters;
258 };    
259
260 class Condition : public ConditionBase {
261     WTF_MAKE_NONCOPYABLE(Condition);
262 public:
263     Condition()
264     {
265         m_hasWaiters.store(false);
266     }
267 };
268
269 typedef ConditionBase StaticCondition;
270
271 } // namespace WTF
272
273 using WTF::Condition;
274 using WTF::StaticCondition;
275
276 #endif // WTF_Condition_h
277