Use WTF::Function instead of std::function in WTF/
[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     // Wait on a parking queue while releasing the given lock. It will unlock the lock just before
54     // parking, and relock it upon wakeup. Returns true if we woke up due to some call to
55     // notifyOne() or notifyAll(). Returns false if we woke up due to a timeout. Note that this form
56     // of waitUntil() has some quirks:
57     //
58     // No spurious wake-up: in order for this to return before the timeout, some notifyOne() or
59     // notifyAll() call must have happened. No scenario other than timeout or notify can lead to this
60     // method returning. This means, for example, that you can't use pthread cancelation or signals to
61     // cause early return.
62     //
63     // Past timeout: it's possible for waitUntil() to be called with a timeout in the past. In that
64     // case, waitUntil() will still release the lock and reacquire it. waitUntil() will always return
65     // false in that case. This is subtly different from some pthread_cond_timedwait() implementations,
66     // which may not release the lock for past timeout. But, this behavior is consistent with OpenGroup
67     // documentation for timedwait().
68     template<typename LockType>
69     bool waitUntil(LockType& lock, const TimeWithDynamicClockType& timeout)
70     {
71         bool result;
72         if (timeout < timeout.nowWithSameClock()) {
73             lock.unlock();
74             result = false;
75         } else {
76             result = ParkingLot::parkConditionally(
77                 &m_hasWaiters,
78                 [this] () -> bool {
79                     // Let everyone know that we will be waiting. Do this while we hold the queue lock,
80                     // to prevent races with notifyOne().
81                     m_hasWaiters.store(true);
82                     return true;
83                 },
84                 [&lock] () { lock.unlock(); },
85                 timeout).wasUnparked;
86         }
87         lock.lock();
88         return result;
89     }
90
91     // Wait until the given predicate is satisfied. Returns true if it is satisfied in the end.
92     // May return early due to timeout.
93     template<typename LockType, typename Functor>
94     bool waitUntil(
95         LockType& lock, const TimeWithDynamicClockType& timeout, const Functor& predicate)
96     {
97         while (!predicate()) {
98             if (!waitUntil(lock, timeout))
99                 return predicate();
100         }
101         return true;
102     }
103
104     // Wait until the given predicate is satisfied. Returns true if it is satisfied in the end.
105     // May return early due to timeout.
106     template<typename LockType, typename Functor>
107     bool waitFor(
108         LockType& lock, Seconds relativeTimeout, const Functor& predicate)
109     {
110         return waitUntil(lock, MonotonicTime::now() + relativeTimeout, predicate);
111     }
112     
113     template<typename LockType>
114     bool waitFor(LockType& lock, Seconds relativeTimeout)
115     {
116         return waitUntil(lock, MonotonicTime::now() + relativeTimeout);
117     }
118
119     template<typename LockType>
120     void wait(LockType& lock)
121     {
122         waitUntil(lock, Time::infinity());
123     }
124
125     template<typename LockType, typename Functor>
126     void wait(LockType& lock, const Functor& predicate)
127     {
128         while (!predicate())
129             wait(lock);
130     }
131
132     // Note that this method is extremely fast when nobody is waiting. It is not necessary to try to
133     // avoid calling this method. This returns true if someone was actually woken up.
134     bool notifyOne()
135     {
136         if (!m_hasWaiters.load()) {
137             // At this exact instant, there is nobody waiting on this condition. The way to visualize
138             // this is that if unparkOne() ran to completion without obstructions at this moment, it
139             // wouldn't wake anyone up. Hence, we have nothing to do!
140             return false;
141         }
142         
143         bool didNotifyThread = false;
144         ParkingLot::unparkOne(
145             &m_hasWaiters,
146             [&] (ParkingLot::UnparkResult result) -> intptr_t {
147                 if (!result.mayHaveMoreThreads)
148                     m_hasWaiters.store(false);
149                 didNotifyThread = result.didUnparkThread;
150                 return 0;
151             });
152         return didNotifyThread;
153     }
154     
155     void notifyAll()
156     {
157         if (!m_hasWaiters.load()) {
158             // See above.
159             return;
160         }
161
162         // It's totally safe for us to set this to false without any locking, because this thread is
163         // guaranteed to then unparkAll() anyway. So, if there is a race with some thread calling
164         // wait() just before this store happens, that thread is guaranteed to be awoken by the call to
165         // unparkAll(), below.
166         m_hasWaiters.store(false);
167         
168         ParkingLot::unparkAll(&m_hasWaiters);
169     }
170     
171 protected:
172     Atomic<bool> m_hasWaiters;
173 };
174
175 class Condition : public ConditionBase {
176     WTF_MAKE_NONCOPYABLE(Condition);
177 public:
178     Condition()
179     {
180         m_hasWaiters.store(false);
181     }
182 };
183
184 typedef ConditionBase StaticCondition;
185
186 } // namespace WTF
187
188 using WTF::Condition;
189 using WTF::StaticCondition;
190
191 #endif // WTF_Condition_h
192