WTF::Condition should have a fast path for notifyOne/notifyAll that avoids calling...
[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 <mutex>
32 #include <wtf/CurrentTime.h>
33 #include <wtf/ParkingLot.h>
34
35 namespace WTF {
36
37 class Condition {
38 public:
39     typedef ParkingLot::Clock Clock;
40     
41     Condition()
42     {
43         m_hasWaiters.store(false);
44     }
45
46     // Wait on a parking queue while releasing the given lock. It will unlock the lock just before
47     // parking, and relock it upon wakeup. Returns true if we woke up due to some call to
48     // notifyOne() or notifyAll(). Returns false if we woke up due to a timeout. Note that this form
49     // of waitUntil() has some quirks:
50     //
51     // No spurious wake-up: in order for this to return before the timeout, some notifyOne() or
52     // notifyAll() call must have happened. No scenario other than timeout or notify can lead to this
53     // method returning. This means, for example, that you can't use pthread cancelation or signals to
54     // cause early return.
55     //
56     // Past timeout: it's possible for waitUntil() to be called with a timeout in the past. In that
57     // case, waitUntil() will still release the lock and reacquire it. waitUntil() will always return
58     // false in that case. This is subtly different from some pthread_cond_timedwait() implementations,
59     // which may not release the lock for past timeout. But, this behavior is consistent with OpenGroup
60     // documentation for timedwait().
61     template<typename LockType>
62     bool waitUntil(LockType& lock, Clock::time_point timeout)
63     {
64         bool result;
65         if (timeout < Clock::now()) {
66             lock.unlock();
67             result = false;
68         } else {
69             result = ParkingLot::parkConditionally(
70                 &m_hasWaiters,
71                 [this] () -> bool {
72                     // Let everyone know that we will be waiting. Do this while we hold the queue lock,
73                     // to prevent races with notifyOne().
74                     m_hasWaiters.store(true);
75                     return true;
76                 },
77                 [&lock] () { lock.unlock(); },
78                 timeout);
79         }
80         lock.lock();
81         return result;
82     }
83
84     // Wait until the given predicate is satisfied. Returns true if it is satisfied in the end.
85     // May return early due to timeout.
86     template<typename LockType, typename Functor>
87     bool waitUntil(LockType& lock, Clock::time_point timeout, const Functor& predicate)
88     {
89         while (!predicate()) {
90             if (!waitUntil(lock, timeout))
91                 return predicate();
92         }
93         return true;
94     }
95
96     // Wait until the given predicate is satisfied. Returns true if it is satisfied in the end.
97     // May return early due to timeout.
98     template<typename LockType, typename DurationType, typename Functor>
99     bool waitFor(
100         LockType& lock, const DurationType& relativeTimeout, const Functor& predicate)
101     {
102         return waitUntil(lock, absoluteFromRelative(relativeTimeout), predicate);
103     }
104
105     template<typename LockType>
106     void wait(LockType& lock)
107     {
108         waitUntil(lock, Clock::time_point::max());
109     }
110
111     template<typename LockType, typename Functor>
112     void wait(LockType& lock, const Functor& predicate)
113     {
114         while (!predicate())
115             wait(lock);
116     }
117
118     template<typename LockType, typename TimeType>
119     bool waitUntil(LockType& lock, const TimeType& timeout)
120     {
121         if (timeout == TimeType::max()) {
122             wait(lock);
123             return true;
124         }
125         return waitForImpl(lock, timeout - TimeType::clock::now());
126     }
127
128     template<typename LockType>
129     bool waitUntilWallClockSeconds(LockType& lock, double absoluteTimeoutSeconds)
130     {
131         return waitForSecondsImpl(lock, absoluteTimeoutSeconds - currentTime());
132     }
133
134     template<typename LockType>
135     bool waitUntilMonotonicClockSeconds(LockType& lock, double absoluteTimeoutSeconds)
136     {
137         return waitForSecondsImpl(lock, absoluteTimeoutSeconds - monotonicallyIncreasingTime());
138     }
139
140     // Note that this method is extremely fast when nobody is waiting. It is not necessary to try to
141     // avoid calling this method.
142     void notifyOne()
143     {
144         if (!m_hasWaiters.load()) {
145             // At this exact instant, there is nobody waiting on this condition. The way to visualize
146             // this is that if unparkOne() ran to completion without obstructions at this moment, it
147             // wouldn't wake anyone up. Hence, we have nothing to do!
148             return;
149         }
150         
151         ParkingLot::unparkOne(
152             &m_hasWaiters,
153             [this] (bool, bool mayHaveMoreThreads) {
154                 if (!mayHaveMoreThreads)
155                     m_hasWaiters.store(false);
156             });
157     }
158     
159     void notifyAll()
160     {
161         if (!m_hasWaiters.load()) {
162             // See above.
163             return;
164         }
165
166         // It's totally safe for us to set this to false without any locking, because this thread is
167         // guaranteed to then unparkAll() anyway. So, if there is a race with some thread calling
168         // wait() just before this store happens, that thread is guaranteed to be awoken by the call to
169         // unparkAll(), below.
170         m_hasWaiters.store(false);
171         
172         ParkingLot::unparkAll(&m_hasWaiters);
173     }
174     
175 private:
176     template<typename LockType>
177     bool waitForSecondsImpl(LockType& lock, double relativeTimeoutSeconds)
178     {
179         double relativeTimeoutNanoseconds = relativeTimeoutSeconds * (1000.0 * 1000.0 * 1000.0);
180         
181         if (!(relativeTimeoutNanoseconds > 0)) {
182             // This handles insta-timeouts as well as NaN.
183             lock.unlock();
184             lock.lock();
185             return false;
186         }
187
188         if (relativeTimeoutNanoseconds > static_cast<double>(std::numeric_limits<int64_t>::max())) {
189             // If the timeout in nanoseconds cannot be expressed using a 64-bit integer, then we
190             // might as well wait forever.
191             wait(lock);
192             return true;
193         }
194         
195         auto relativeTimeout =
196             std::chrono::nanoseconds(static_cast<int64_t>(relativeTimeoutNanoseconds));
197
198         return waitForImpl(lock, relativeTimeout);
199     }
200     
201     template<typename LockType, typename DurationType>
202     bool waitForImpl(LockType& lock, const DurationType& relativeTimeout)
203     {
204         return waitUntil(lock, absoluteFromRelative(relativeTimeout));
205     }
206
207     template<typename DurationType>
208     Clock::time_point absoluteFromRelative(const DurationType& relativeTimeout)
209     {
210         if (relativeTimeout < DurationType::zero())
211             return Clock::time_point::min();
212
213         if (relativeTimeout > Clock::duration::max()) {
214             // This is highly unlikely. But if it happens, we want to not do anything dumb. Sleeping
215             // without a timeout seems sensible when the timeout duration is greater than what can be
216             // expressed using steady_clock.
217             return Clock::time_point::max();
218         }
219         
220         Clock::duration myRelativeTimeout =
221             std::chrono::duration_cast<Clock::duration>(relativeTimeout);
222
223         return Clock::now() + myRelativeTimeout;
224     }
225
226     Atomic<bool> m_hasWaiters;
227 };
228
229 } // namespace WTF
230
231 using WTF::Condition;
232
233 #endif // WTF_Condition_h
234