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/Atomics.h>
29#include <wtf/ScopedLambda.h>
30#include <wtf/TimeWithDynamicClockType.h>
31
32namespace WTF {
33
34class Thread;
35
36class ParkingLot {
37 WTF_MAKE_FAST_ALLOCATED;
38
39 ParkingLot() = delete;
40 ParkingLot(const ParkingLot&) = delete;
41
42public:
43 // ParkingLot will accept any kind of time and convert it internally, but this typedef tells
44 // you what kind of time ParkingLot would be able to use without conversions. It's sad that
45 // this is WallTime not MonotonicTime, but that's just how OS wait functions work. However,
46 // because ParkingLot evaluates whether it should wait by checking if your time has passed
47 // using whatever clock you used, specifying timeouts in MonotonicTime is semantically better.
48 // For example, if the user sets his computer's clock back during the time that you wanted to
49 // wait for one second, and you specified the timeout using the MonotonicTime, then ParkingLot
50 // will be smart enough to know that your one second has elapsed.
51 typedef WallTime Time;
52
53 // Parks the thread in a queue associated with the given address, which cannot be null. The
54 // parking only succeeds if the validation function returns true while the queue lock is held.
55 //
56 // If validation returns false, it will unlock the internal parking queue and then it will
57 // return a null ParkResult (wasUnparked = false, token = 0) without doing anything else.
58 //
59 // If validation returns true, it will enqueue the thread, unlock the parking queue lock, call
60 // the beforeSleep function, and then it will sleep so long as the thread continues to be on the
61 // queue and the timeout hasn't fired. Finally, this returns wasUnparked = true if we actually
62 // got unparked or wasUnparked = false if the timeout was hit. When wasUnparked = true, the
63 // token will contain whatever token was returned from the callback to unparkOne(), or 0 if the
64 // thread was unparked using unparkAll() or the form of unparkOne() that doesn't take a
65 // callback.
66 //
67 // Note that beforeSleep is called with no locks held, so it's OK to do pretty much anything so
68 // long as you don't recursively call parkConditionally(). You can call unparkOne()/unparkAll()
69 // though. It's useful to use beforeSleep() to unlock some mutex in the implementation of
70 // Condition::wait().
71 struct ParkResult {
72 bool wasUnparked { false };
73 intptr_t token { 0 };
74 };
75 template<typename ValidationFunctor, typename BeforeSleepFunctor>
76 static ParkResult parkConditionally(
77 const void* address,
78 const ValidationFunctor& validation,
79 const BeforeSleepFunctor& beforeSleep,
80 const TimeWithDynamicClockType& timeout)
81 {
82 return parkConditionallyImpl(
83 address,
84 scopedLambdaRef<bool()>(validation),
85 scopedLambdaRef<void()>(beforeSleep),
86 timeout);
87 }
88
89 // Simple version of parkConditionally() that covers the most common case: you want to park
90 // indefinitely so long as the value at the given address hasn't changed.
91 template<typename T, typename U>
92 static ParkResult compareAndPark(const Atomic<T>* address, U expected)
93 {
94 return parkConditionally(
95 address,
96 [address, expected] () -> bool {
97 U value = address->load();
98 return value == expected;
99 },
100 [] () { },
101 Time::infinity());
102 }
103
104 // Unparking status given to you anytime you unparkOne().
105 struct UnparkResult {
106 // True if some thread was unparked.
107 bool didUnparkThread { false };
108 // True if there may be more threads on this address. This may be conservatively true.
109 bool mayHaveMoreThreads { false };
110 // This bit is randomly set to true indicating that it may be profitable to unlock the lock
111 // using a fair unlocking protocol. This is most useful when used in conjunction with
112 // unparkOne(address, callback).
113 bool timeToBeFair { false };
114 };
115
116 // Unparks one thread from the queue associated with the given address, which cannot be null.
117 // Returns true if there may still be other threads on that queue, or false if there definitely
118 // are no more threads on the queue.
119 WTF_EXPORT_PRIVATE static UnparkResult unparkOne(const void* address);
120
121 // This is an expert-mode version of unparkOne() that allows for really good thundering herd
122 // avoidance and eventual stochastic fairness in adaptive mutexes.
123 //
124 // Unparks one thread from the queue associated with the given address, and calls the given
125 // callback while the address is locked. Reports to the callback whether any thread got
126 // unparked, whether there may be any other threads still on the queue, and whether this may be
127 // a good time to do fair unlocking. The callback returns an intptr_t token, which is returned
128 // to the unparked thread via ParkResult::token.
129 //
130 // WTF::Lock and WTF::Condition both use this form of unparkOne() because it allows them to use
131 // the ParkingLot's internal queue lock to serialize some decision-making. For example, if
132 // UnparkResult::mayHaveMoreThreads is false inside the callback, then we know that at that
133 // moment nobody can add any threads to the queue because the queue lock is still held. Also,
134 // WTF::Lock uses the timeToBeFair and token mechanism to implement eventual fairness.
135 template<typename Callback>
136 static void unparkOne(const void* address, const Callback& callback)
137 {
138 unparkOneImpl(address, scopedLambdaRef<intptr_t(UnparkResult)>(callback));
139 }
140
141 WTF_EXPORT_PRIVATE static unsigned unparkCount(const void* address, unsigned count);
142
143 // Unparks every thread from the queue associated with the given address, which cannot be null.
144 WTF_EXPORT_PRIVATE static void unparkAll(const void* address);
145
146 // Locks the parking lot and walks all of the parked threads and the addresses they are waiting
147 // on. Threads that are on the same queue are guaranteed to be walked from first to last, but the
148 // queues may be randomly interleaved. For example, if the queue for address A1 has T1 and T2 and
149 // the queue for address A2 has T3 and T4, then you might see iteration orders like:
150 //
151 // A1,T1 A1,T2 A2,T3 A2,T4
152 // A2,T3 A2,T4 A1,T1 A1,T2
153 // A1,T1 A2,T3 A1,T2 A2,T4
154 // A1,T1 A2,T3 A2,T4 A1,T2
155 //
156 // As well as many other possible interleavings that all have T1 before T2 and T3 before T4 but are
157 // otherwise unconstrained. This method is useful primarily for debugging. It's also used by unit
158 // tests.
159 template<typename Func>
160 static void forEach(const Func& func)
161 {
162 forEachImpl(scopedLambdaRef<void(Thread&, const void*)>(func));
163 }
164
165private:
166 WTF_EXPORT_PRIVATE static ParkResult parkConditionallyImpl(
167 const void* address,
168 const ScopedLambda<bool()>& validation,
169 const ScopedLambda<void()>& beforeSleep,
170 const TimeWithDynamicClockType& timeout);
171
172 WTF_EXPORT_PRIVATE static void unparkOneImpl(
173 const void* address, const ScopedLambda<intptr_t(UnparkResult)>& callback);
174
175 WTF_EXPORT_PRIVATE static void forEachImpl(const ScopedLambda<void(Thread&, const void*)>&);
176};
177
178} // namespace WTF
179
180using WTF::ParkingLot;
181