25a37a4f2c855e6423f6abe8c7ddb358af0f888e
[WebKit-https.git] / Source / WTF / wtf / LockAlgorithm.h
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 #ifndef WTF_LockAlgorithm_h
27 #define WTF_LockAlgorithm_h
28
29 #include <thread>
30 #include <wtf/Atomics.h>
31 #include <wtf/Compiler.h>
32 #include <wtf/ParkingLot.h>
33
34 namespace WTF {
35
36 // This is the algorithm used by WTF::Lock. You can use it to project one lock onto any atomic
37 // field. The limit of one lock is due to the use of the field's address as a key to find the lock's
38 // queue.
39
40 template<typename LockType, LockType isHeldBit, LockType hasParkedBit>
41 class LockAlgorithm {
42     static const bool verbose = false;
43     static const LockType mask = isHeldBit | hasParkedBit;
44
45 public:
46     static bool lockFastAssumingZero(Atomic<LockType>& lock)
47     {
48         return lock.compareExchangeWeak(0, isHeldBit, std::memory_order_acquire);
49     }
50     
51     static bool lockFast(Atomic<LockType>& lock)
52     {
53         return lock.transaction(
54             [&] (LockType& value) -> bool {
55                 if (value & isHeldBit)
56                     return false;
57                 value |= isHeldBit;
58                 return true;
59             },
60             std::memory_order_acquire);
61     }
62     
63     static void lock(Atomic<LockType>& lock)
64     {
65         if (UNLIKELY(!lockFast(lock)))
66             lockSlow(lock);
67     }
68     
69     static bool tryLock(Atomic<LockType>& lock)
70     {
71         for (;;) {
72             uint8_t currentByteValue = lock.load(std::memory_order_relaxed);
73             if (currentByteValue & isHeldBit)
74                 return false;
75             if (lock.compareExchangeWeak(currentByteValue, currentByteValue | isHeldBit, std::memory_order_acquire))
76                 return true;
77         }
78     }
79
80     static bool unlockFastAssumingZero(Atomic<LockType>& lock)
81     {
82         return lock.compareExchangeWeak(isHeldBit, 0, std::memory_order_release);
83     }
84     
85     static bool unlockFast(Atomic<LockType>& lock)
86     {
87         return lock.transaction(
88             [&] (LockType& value) -> bool {
89                 if ((value & mask) != isHeldBit)
90                     return false;
91                 value &= ~isHeldBit;
92                 return true;
93             },
94             std::memory_order_relaxed);
95     }
96     
97     static void unlock(Atomic<LockType>& lock)
98     {
99         if (UNLIKELY(!unlockFast(lock)))
100             unlockSlow(lock, Unfair);
101     }
102     
103     static void unlockFairly(Atomic<LockType>& lock)
104     {
105         if (UNLIKELY(!unlockFast(lock)))
106             unlockSlow(lock, Fair);
107     }
108     
109     static bool safepointFast(const Atomic<LockType>& lock)
110     {
111         WTF::compilerFence();
112         return !(lock.load(std::memory_order_relaxed) & hasParkedBit);
113     }
114     
115     static void safepoint(Atomic<LockType>& lock)
116     {
117         if (UNLIKELY(!safepointFast(lock)))
118             safepointSlow(lock);
119     }
120     
121     static bool isLocked(const Atomic<LockType>& lock)
122     {
123         return lock.load(std::memory_order_acquire) & isHeldBit;
124     }
125     
126     NEVER_INLINE static void lockSlow(Atomic<LockType>& lock)
127     {
128         unsigned spinCount = 0;
129
130         // This magic number turns out to be optimal based on past JikesRVM experiments.
131         const unsigned spinLimit = 40;
132     
133         for (;;) {
134             uint8_t currentByteValue = lock.load();
135
136             // We allow ourselves to barge in.
137             if (!(currentByteValue & isHeldBit)
138                 && lock.compareExchangeWeak(currentByteValue, currentByteValue | isHeldBit))
139                 return;
140
141             // If there is nobody parked and we haven't spun too much, we can just try to spin around.
142             if (!(currentByteValue & hasParkedBit) && spinCount < spinLimit) {
143                 spinCount++;
144                 std::this_thread::yield();
145                 continue;
146             }
147
148             // Need to park. We do this by setting the parked bit first, and then parking. We spin around
149             // if the parked bit wasn't set and we failed at setting it.
150             if (!(currentByteValue & hasParkedBit)
151                 && !lock.compareExchangeWeak(currentByteValue, currentByteValue | hasParkedBit))
152                 continue;
153
154             // We now expect the value to be isHeld|hasParked. So long as that's the case, we can park.
155             ParkingLot::ParkResult parkResult =
156                 ParkingLot::compareAndPark(&lock, currentByteValue | isHeldBit | hasParkedBit);
157             if (parkResult.wasUnparked) {
158                 switch (static_cast<Token>(parkResult.token)) {
159                 case DirectHandoff:
160                     // The lock was never released. It was handed to us directly by the thread that did
161                     // unlock(). This means we're done!
162                     RELEASE_ASSERT(isLocked(lock));
163                     return;
164                 case BargingOpportunity:
165                     // This is the common case. The thread that called unlock() has released the lock,
166                     // and we have been woken up so that we may get an opportunity to grab the lock. But
167                     // other threads may barge, so the best that we can do is loop around and try again.
168                     break;
169                 }
170             }
171
172             // We have awoken, or we never parked because the byte value changed. Either way, we loop
173             // around and try again.
174         }
175     }
176     
177     enum Fairness {
178         Fair,
179         Unfair
180     };
181     NEVER_INLINE static void unlockSlow(Atomic<LockType>& lock, Fairness fairness)
182     {
183         // We could get here because the weak CAS in unlock() failed spuriously, or because there is
184         // someone parked. So, we need a CAS loop: even if right now the lock is just held, it could
185         // be held and parked if someone attempts to lock just as we are unlocking.
186         for (;;) {
187             uint8_t oldByteValue = lock.load();
188             RELEASE_ASSERT(
189                 (oldByteValue & mask) == isHeldBit
190                 || (oldByteValue & mask) == (isHeldBit | hasParkedBit));
191         
192             if ((oldByteValue & mask) == isHeldBit) {
193                 if (lock.compareExchangeWeak(oldByteValue, oldByteValue & ~isHeldBit))
194                     return;
195                 continue;
196             }
197
198             // Someone is parked. Unpark exactly one thread. We may hand the lock to that thread
199             // directly, or we will unlock the lock at the same time as we unpark to allow for barging.
200             // When we unlock, we may leave the parked bit set if there is a chance that there are still
201             // other threads parked.
202             ASSERT((oldByteValue & mask) == (isHeldBit | hasParkedBit));
203             ParkingLot::unparkOne(
204                 &lock,
205                 [&] (ParkingLot::UnparkResult result) -> intptr_t {
206                     // We are the only ones that can clear either the isHeldBit or the hasParkedBit,
207                     // so we should still see both bits set right now.
208                     ASSERT((lock.load() & mask) == (isHeldBit | hasParkedBit));
209                 
210                     if (result.didUnparkThread && (fairness == Fair || result.timeToBeFair)) {
211                         // We don't unlock anything. Instead, we hand the lock to the thread that was
212                         // waiting.
213                         return DirectHandoff;
214                     }
215                     
216                     lock.transaction(
217                         [&] (LockType& value) -> bool {
218                             value &= ~mask;
219                             if (result.mayHaveMoreThreads)
220                                 value |= hasParkedBit;
221                             return true;
222                         });
223                     return BargingOpportunity;
224                 });
225             return;
226         }
227     }
228     
229     NEVER_INLINE static void safepointSlow(Atomic<LockType>& lockWord)
230     {
231         unlockFairly(lockWord);
232         lock(lockWord);
233     }
234     
235 private:
236     enum Token {
237         BargingOpportunity,
238         DirectHandoff
239     };
240 };
241
242 } // namespace WTF
243
244 using WTF::LockAlgorithm;
245
246 #endif // WTF_LockAlgorithm_h
247