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