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