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#pragma once
27
28#include <wtf/Noncopyable.h>
29#include <wtf/ParkingLot.h>
30#include <wtf/TimeWithDynamicClockType.h>
31
32namespace WTF {
33
34// This is a condition variable that is suitable for use with any lock-like object, including
35// our own WTF::Lock. It features standard wait()/notifyOne()/notifyAll() methods in addition to
36// a variety of wait-with-timeout methods. This includes methods that use WTF's own notion of
37// time, like wall-clock time (i.e. WallTime) and monotonic time (i.e. MonotonicTime). This is
38// a very efficient condition variable. It only requires one byte of memory. notifyOne() and
39// notifyAll() require just a load and branch for the fast case where no thread is waiting.
40// This condition variable, when used with WTF::Lock, can outperform a system condition variable
41// and lock by up to 58x.
42class Condition final {
43 WTF_MAKE_NONCOPYABLE(Condition);
44 WTF_MAKE_FAST_ALLOCATED;
45public:
46 // Condition will accept any kind of time and convert it internally, but this typedef tells
47 // you what kind of time Condition would be able to use without conversions. However, if you
48 // are unlikely to be affected by the cost of conversions, it is better to use MonotonicTime.
49 using Time = ParkingLot::Time;
50
51 constexpr Condition() = default;
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
171private:
172 Atomic<bool> m_hasWaiters { false };
173};
174
175using StaticCondition = Condition;
176
177} // namespace WTF
178
179using WTF::Condition;
180using WTF::StaticCondition;
181