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