1/*
2 * Copyright (C) 2015-2017 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#include "config.h"
27#include <wtf/WordLock.h>
28
29#include <condition_variable>
30#include <mutex>
31#include <thread>
32#include <wtf/Threading.h>
33
34namespace WTF {
35
36namespace {
37
38// This data structure serves three purposes:
39//
40// 1) A parking mechanism for threads that go to sleep. That involves just a system mutex and
41// condition variable.
42//
43// 2) A queue node for when a thread is on some WordLock's queue.
44//
45// 3) The queue head. This is kind of funky. When a thread is the head of a queue, it also serves as
46// the basic queue bookkeeping data structure. When a thread is dequeued, the next thread in the
47// queue takes on the queue head duties.
48struct ThreadData {
49 // The parking mechanism.
50 bool shouldPark { false };
51 std::mutex parkingLock;
52 std::condition_variable parkingCondition;
53
54 // The queue node.
55 ThreadData* nextInQueue { nullptr };
56
57 // The queue itself.
58 ThreadData* queueTail { nullptr };
59};
60
61} // anonymous namespace
62
63NEVER_INLINE void WordLock::lockSlow()
64{
65 unsigned spinCount = 0;
66
67 // This magic number turns out to be optimal based on past JikesRVM experiments.
68 const unsigned spinLimit = 40;
69
70 for (;;) {
71 uintptr_t currentWordValue = m_word.load();
72
73 if (!(currentWordValue & isLockedBit)) {
74 // It's not possible for someone to hold the queue lock while the lock itself is no longer
75 // held, since we will only attempt to acquire the queue lock when the lock is held and
76 // the queue lock prevents unlock.
77 ASSERT(!(currentWordValue & isQueueLockedBit));
78 if (m_word.compareExchangeWeak(currentWordValue, currentWordValue | isLockedBit)) {
79 // Success! We acquired the lock.
80 return;
81 }
82 }
83
84 // If there is no queue and we haven't spun too much, we can just try to spin around again.
85 if (!(currentWordValue & ~queueHeadMask) && spinCount < spinLimit) {
86 spinCount++;
87 Thread::yield();
88 continue;
89 }
90
91 // Need to put ourselves on the queue. Create the queue if one does not exist. This requries
92 // owning the queue for a little bit. The lock that controls the queue is itself a spinlock.
93
94 ThreadData me;
95
96 // Reload the current word value, since some time may have passed.
97 currentWordValue = m_word.load();
98
99 // We proceed only if the queue lock is not held, the WordLock is held, and we succeed in
100 // acquiring the queue lock.
101 if ((currentWordValue & isQueueLockedBit)
102 || !(currentWordValue & isLockedBit)
103 || !m_word.compareExchangeWeak(currentWordValue, currentWordValue | isQueueLockedBit)) {
104 Thread::yield();
105 continue;
106 }
107
108 me.shouldPark = true;
109
110 // We own the queue. Nobody can enqueue or dequeue until we're done. Also, it's not possible
111 // to release the WordLock while we hold the queue lock.
112 ThreadData* queueHead = bitwise_cast<ThreadData*>(currentWordValue & ~queueHeadMask);
113 if (queueHead) {
114 // Put this thread at the end of the queue.
115 queueHead->queueTail->nextInQueue = &me;
116 queueHead->queueTail = &me;
117
118 // Release the queue lock.
119 currentWordValue = m_word.load();
120 ASSERT(currentWordValue & ~queueHeadMask);
121 ASSERT(currentWordValue & isQueueLockedBit);
122 ASSERT(currentWordValue & isLockedBit);
123 m_word.store(currentWordValue & ~isQueueLockedBit);
124 } else {
125 // Make this thread be the queue-head.
126 queueHead = &me;
127 me.queueTail = &me;
128
129 // Release the queue lock and install ourselves as the head. No need for a CAS loop, since
130 // we own the queue lock.
131 currentWordValue = m_word.load();
132 ASSERT(~(currentWordValue & ~queueHeadMask));
133 ASSERT(currentWordValue & isQueueLockedBit);
134 ASSERT(currentWordValue & isLockedBit);
135 uintptr_t newWordValue = currentWordValue;
136 newWordValue |= bitwise_cast<uintptr_t>(queueHead);
137 newWordValue &= ~isQueueLockedBit;
138 m_word.store(newWordValue);
139 }
140
141 // At this point everyone who acquires the queue lock will see me on the queue, and anyone who
142 // acquires me's lock will see that me wants to park. Note that shouldPark may have been
143 // cleared as soon as the queue lock was released above, but it will happen while the
144 // releasing thread holds me's parkingLock.
145
146 {
147 std::unique_lock<std::mutex> locker(me.parkingLock);
148 while (me.shouldPark)
149 me.parkingCondition.wait(locker);
150 }
151
152 ASSERT(!me.shouldPark);
153 ASSERT(!me.nextInQueue);
154 ASSERT(!me.queueTail);
155
156 // Now we can loop around and try to acquire the lock again.
157 }
158}
159
160NEVER_INLINE void WordLock::unlockSlow()
161{
162 // The fast path can fail either because of spurious weak CAS failure, or because someone put a
163 // thread on the queue, or the queue lock is held. If the queue lock is held, it can only be
164 // because someone *will* enqueue a thread onto the queue.
165
166 // Acquire the queue lock, or release the lock. This loop handles both lock release in case the
167 // fast path's weak CAS spuriously failed and it handles queue lock acquisition if there is
168 // actually something interesting on the queue.
169 for (;;) {
170 uintptr_t currentWordValue = m_word.load();
171
172 ASSERT(currentWordValue & isLockedBit);
173
174 if (currentWordValue == isLockedBit) {
175 if (m_word.compareExchangeWeak(isLockedBit, 0)) {
176 // The fast path's weak CAS had spuriously failed, and now we succeeded. The lock is
177 // unlocked and we're done!
178 return;
179 }
180 // Loop around and try again.
181 Thread::yield();
182 continue;
183 }
184
185 if (currentWordValue & isQueueLockedBit) {
186 Thread::yield();
187 continue;
188 }
189
190 // If it wasn't just a spurious weak CAS failure and if the queue lock is not held, then there
191 // must be an entry on the queue.
192 ASSERT(currentWordValue & ~queueHeadMask);
193
194 if (m_word.compareExchangeWeak(currentWordValue, currentWordValue | isQueueLockedBit))
195 break;
196 }
197
198 uintptr_t currentWordValue = m_word.load();
199
200 // After we acquire the queue lock, the WordLock must still be held and the queue must be
201 // non-empty. The queue must be non-empty since only the lockSlow() method could have held the
202 // queue lock and if it did then it only releases it after putting something on the queue.
203 ASSERT(currentWordValue & isLockedBit);
204 ASSERT(currentWordValue & isQueueLockedBit);
205 ThreadData* queueHead = bitwise_cast<ThreadData*>(currentWordValue & ~queueHeadMask);
206 ASSERT(queueHead);
207
208 ThreadData* newQueueHead = queueHead->nextInQueue;
209 // Either this was the only thread on the queue, in which case we delete the queue, or there
210 // are still more threads on the queue, in which case we create a new queue head.
211 if (newQueueHead)
212 newQueueHead->queueTail = queueHead->queueTail;
213
214 // Change the queue head, possibly removing it if newQueueHead is null. No need for a CAS loop,
215 // since we hold the queue lock and the lock itself so nothing about the lock can change right
216 // now.
217 currentWordValue = m_word.load();
218 ASSERT(currentWordValue & isLockedBit);
219 ASSERT(currentWordValue & isQueueLockedBit);
220 ASSERT((currentWordValue & ~queueHeadMask) == bitwise_cast<uintptr_t>(queueHead));
221 uintptr_t newWordValue = currentWordValue;
222 newWordValue &= ~isLockedBit; // Release the WordLock.
223 newWordValue &= ~isQueueLockedBit; // Release the queue lock.
224 newWordValue &= queueHeadMask; // Clear out the old queue head.
225 newWordValue |= bitwise_cast<uintptr_t>(newQueueHead); // Install new queue head.
226 m_word.store(newWordValue);
227
228 // Now the lock is available for acquisition. But we just have to wake up the old queue head.
229 // After that, we're done!
230
231 queueHead->nextInQueue = nullptr;
232 queueHead->queueTail = nullptr;
233
234 // We do this carefully because this may run either before or during the parkingLock critical
235 // section in lockSlow().
236 {
237 // Be sure to hold the lock across our call to notify_one() because a spurious wakeup could
238 // cause the thread at the head of the queue to exit and delete queueHead.
239 std::lock_guard<std::mutex> locker(queueHead->parkingLock);
240 queueHead->shouldPark = false;
241
242 // Doesn't matter if we notify_all() or notify_one() here since the only thread that could be
243 // waiting is queueHead.
244 queueHead->parkingCondition.notify_one();
245 }
246
247 // The old queue head can now contend for the lock again. We're done!
248}
249
250} // namespace WTF
251
252