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