fcf32c84d454b06202aa382a00b52bcdf065242d
[WebKit-https.git] / Source / WTF / wtf / Condition.h
1 /*
2  * Copyright (C) 2015-2016 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 <wtf/CurrentTime.h>
30 #include <wtf/Noncopyable.h>
31 #include <wtf/ParkingLot.h>
32 #include <wtf/TimeWithDynamicClockType.h>
33
34 namespace WTF {
35
36 // This is a condition variable that is suitable for use with any lock-like object, including
37 // our own WTF::Lock. It features standard wait()/notifyOne()/notifyAll() methods in addition to
38 // a variety of wait-with-timeout methods. This includes methods that use WTF's own notion of
39 // time, like wall-clock time (i.e. currentTime()) and monotonic time (i.e.
40 // monotonicallyIncreasingTime()). This is a very efficient condition variable. It only requires
41 // one byte of memory. notifyOne() and notifyAll() require just a load and branch for the fast
42 // case where no thread is waiting. This condition variable, when used with WTF::Lock, can
43 // outperform a system condition variable and lock by up to 58x.
44
45 // This is a struct without a constructor or destructor so that it can be statically initialized.
46 // Use Lock in instance variables.
47 struct ConditionBase {
48     // Condition will accept any kind of time and convert it internally, but this typedef tells
49     // you what kind of time Condition would be able to use without conversions. However, if you
50     // are unlikely to be affected by the cost of conversions, it is better to use MonotonicTime.
51     typedef ParkingLot::Time Time;
52     
53     void construct()
54     {
55         m_hasWaiters.store(false);
56     }
57     
58     // Wait on a parking queue while releasing the given lock. It will unlock the lock just before
59     // parking, and relock it upon wakeup. Returns true if we woke up due to some call to
60     // notifyOne() or notifyAll(). Returns false if we woke up due to a timeout. Note that this form
61     // of waitUntil() has some quirks:
62     //
63     // No spurious wake-up: in order for this to return before the timeout, some notifyOne() or
64     // notifyAll() call must have happened. No scenario other than timeout or notify can lead to this
65     // method returning. This means, for example, that you can't use pthread cancelation or signals to
66     // cause early return.
67     //
68     // Past timeout: it's possible for waitUntil() to be called with a timeout in the past. In that
69     // case, waitUntil() will still release the lock and reacquire it. waitUntil() will always return
70     // false in that case. This is subtly different from some pthread_cond_timedwait() implementations,
71     // which may not release the lock for past timeout. But, this behavior is consistent with OpenGroup
72     // documentation for timedwait().
73     template<typename LockType>
74     bool waitUntil(LockType& lock, const TimeWithDynamicClockType& timeout)
75     {
76         bool result;
77         if (timeout < timeout.nowWithSameClock()) {
78             lock.unlock();
79             result = false;
80         } else {
81             result = ParkingLot::parkConditionally(
82                 &m_hasWaiters,
83                 [this] () -> bool {
84                     // Let everyone know that we will be waiting. Do this while we hold the queue lock,
85                     // to prevent races with notifyOne().
86                     m_hasWaiters.store(true);
87                     return true;
88                 },
89                 [&lock] () { lock.unlock(); },
90                 timeout).wasUnparked;
91         }
92         lock.lock();
93         return result;
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 Functor>
99     bool waitUntil(
100         LockType& lock, const TimeWithDynamicClockType& timeout, const Functor& predicate)
101     {
102         while (!predicate()) {
103             if (!waitUntil(lock, timeout))
104                 return predicate();
105         }
106         return true;
107     }
108
109     // Wait until the given predicate is satisfied. Returns true if it is satisfied in the end.
110     // May return early due to timeout.
111     template<typename LockType, typename Functor>
112     bool waitFor(
113         LockType& lock, Seconds relativeTimeout, const Functor& predicate)
114     {
115         return waitUntil(lock, MonotonicTime::now() + relativeTimeout, predicate);
116     }
117     
118     template<typename LockType>
119     bool waitFor(LockType& lock, Seconds relativeTimeout)
120     {
121         return waitUntil(lock, MonotonicTime::now() + relativeTimeout);
122     }
123
124     template<typename LockType>
125     void wait(LockType& lock)
126     {
127         waitUntil(lock, Time::infinity());
128     }
129
130     template<typename LockType, typename Functor>
131     void wait(LockType& lock, const Functor& predicate)
132     {
133         while (!predicate())
134             wait(lock);
135     }
136
137     // Note that this method is extremely fast when nobody is waiting. It is not necessary to try to
138     // avoid calling this method. This returns true if someone was actually woken up.
139     bool notifyOne()
140     {
141         if (!m_hasWaiters.load()) {
142             // At this exact instant, there is nobody waiting on this condition. The way to visualize
143             // this is that if unparkOne() ran to completion without obstructions at this moment, it
144             // wouldn't wake anyone up. Hence, we have nothing to do!
145             return false;
146         }
147         
148         bool didNotifyThread = false;
149         ParkingLot::unparkOne(
150             &m_hasWaiters,
151             [&] (ParkingLot::UnparkResult result) -> intptr_t {
152                 if (!result.mayHaveMoreThreads)
153                     m_hasWaiters.store(false);
154                 didNotifyThread = result.didUnparkThread;
155                 return 0;
156             });
157         return didNotifyThread;
158     }
159     
160     void notifyAll()
161     {
162         if (!m_hasWaiters.load()) {
163             // See above.
164             return;
165         }
166
167         // It's totally safe for us to set this to false without any locking, because this thread is
168         // guaranteed to then unparkAll() anyway. So, if there is a race with some thread calling
169         // wait() just before this store happens, that thread is guaranteed to be awoken by the call to
170         // unparkAll(), below.
171         m_hasWaiters.store(false);
172         
173         ParkingLot::unparkAll(&m_hasWaiters);
174     }
175     
176 private:
177     Atomic<bool> m_hasWaiters;
178 };
179
180 class Condition : public ConditionBase {
181     WTF_MAKE_NONCOPYABLE(Condition);
182 public:
183     Condition()
184     {
185         construct();
186     }
187 };
188
189 typedef ConditionBase StaticCondition;
190
191 } // namespace WTF
192
193 using WTF::Condition;
194 using WTF::StaticCondition;
195
196 #endif // WTF_Condition_h
197