GC constraint solving should be parallel
[WebKit-https.git] / Source / WTF / wtf / LockAlgorithmInlines.h
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 #pragma once
27
28 #include <wtf/DataLog.h>
29 #include <wtf/LockAlgorithm.h>
30 #include <wtf/ParkingLot.h>
31 #include <wtf/Threading.h>
32
33 // It's a good idea to avoid including this header in too many places, so that it's possible to change
34 // the lock algorithm slow path without recompiling the world. Right now this should be included in two
35 // places (Lock.cpp and JSCell.cpp).
36
37 namespace WTF {
38
39 template<typename LockType, LockType isHeldBit, LockType hasParkedBit, typename Hooks>
40 void LockAlgorithm<LockType, isHeldBit, hasParkedBit, Hooks>::lockSlow(Atomic<LockType>& lock)
41 {
42     // This magic number turns out to be optimal based on past JikesRVM experiments.
43     static const unsigned spinLimit = 40;
44     
45     unsigned spinCount = 0;
46     
47     for (;;) {
48         LockType currentValue = lock.load();
49         
50         // We allow ourselves to barge in.
51         if (!(currentValue & isHeldBit)) {
52             if (lock.compareExchangeWeak(currentValue, Hooks::lockHook(currentValue | isHeldBit)))
53                 return;
54             continue;
55         }
56
57         // If there is nobody parked and we haven't spun too much, we can just try to spin around.
58         if (!(currentValue & hasParkedBit) && spinCount < spinLimit) {
59             spinCount++;
60             Thread::yield();
61             continue;
62         }
63
64         // Need to park. We do this by setting the parked bit first, and then parking. We spin around
65         // if the parked bit wasn't set and we failed at setting it.
66         if (!(currentValue & hasParkedBit)) {
67             LockType newValue = Hooks::parkHook(currentValue | hasParkedBit);
68             if (!lock.compareExchangeWeak(currentValue, newValue))
69                 continue;
70             currentValue = newValue;
71         }
72         
73         if (!(currentValue & isHeldBit)) {
74             dataLog("Lock not held!\n");
75             RELEASE_ASSERT_NOT_REACHED();
76         }
77         if (!(currentValue & hasParkedBit)) {
78             dataLog("Lock not parked!\n");
79             RELEASE_ASSERT_NOT_REACHED();
80         }
81
82         // We now expect the value to be isHeld|hasParked. So long as that's the case, we can park.
83         ParkingLot::ParkResult parkResult =
84             ParkingLot::compareAndPark(&lock, currentValue);
85         if (parkResult.wasUnparked) {
86             switch (static_cast<Token>(parkResult.token)) {
87             case DirectHandoff:
88                 // The lock was never released. It was handed to us directly by the thread that did
89                 // unlock(). This means we're done!
90                 RELEASE_ASSERT(isLocked(lock));
91                 return;
92             case BargingOpportunity:
93                 // This is the common case. The thread that called unlock() has released the lock,
94                 // and we have been woken up so that we may get an opportunity to grab the lock. But
95                 // other threads may barge, so the best that we can do is loop around and try again.
96                 break;
97             }
98         }
99
100         // We have awoken, or we never parked because the byte value changed. Either way, we loop
101         // around and try again.
102     }
103 }
104
105 template<typename LockType, LockType isHeldBit, LockType hasParkedBit, typename Hooks>
106 void LockAlgorithm<LockType, isHeldBit, hasParkedBit, Hooks>::unlockSlow(Atomic<LockType>& lock, Fairness fairness)
107 {
108     // We could get here because the weak CAS in unlock() failed spuriously, or because there is
109     // someone parked. So, we need a CAS loop: even if right now the lock is just held, it could
110     // be held and parked if someone attempts to lock just as we are unlocking.
111     for (;;) {
112         uint8_t oldByteValue = lock.load();
113         RELEASE_ASSERT(
114             (oldByteValue & mask) == isHeldBit
115             || (oldByteValue & mask) == (isHeldBit | hasParkedBit));
116         
117         if ((oldByteValue & mask) == isHeldBit) {
118             if (lock.compareExchangeWeak(oldByteValue, Hooks::unlockHook(oldByteValue & ~isHeldBit)))
119                 return;
120             continue;
121         }
122
123         // Someone is parked. Unpark exactly one thread. We may hand the lock to that thread
124         // directly, or we will unlock the lock at the same time as we unpark to allow for barging.
125         // When we unlock, we may leave the parked bit set if there is a chance that there are still
126         // other threads parked.
127         ASSERT((oldByteValue & mask) == (isHeldBit | hasParkedBit));
128         ParkingLot::unparkOne(
129             &lock,
130             [&] (ParkingLot::UnparkResult result) -> intptr_t {
131                 // We are the only ones that can clear either the isHeldBit or the hasParkedBit,
132                 // so we should still see both bits set right now.
133                 ASSERT((lock.load() & mask) == (isHeldBit | hasParkedBit));
134                 
135                 if (result.didUnparkThread && (fairness == Fair || result.timeToBeFair)) {
136                     // We don't unlock anything. Instead, we hand the lock to the thread that was
137                     // waiting.
138                     lock.transaction(
139                         [&] (LockType& value) -> bool {
140                             LockType newValue = Hooks::handoffHook(value);
141                             if (newValue == value)
142                                 return false;
143                             value = newValue;
144                             return true;
145                         });
146                     return DirectHandoff;
147                 }
148                 
149                 lock.transaction(
150                     [&] (LockType& value) -> bool {
151                         value &= ~mask;
152                         value = Hooks::unlockHook(value);
153                         if (result.mayHaveMoreThreads)
154                             value |= hasParkedBit;
155                         return true;
156                     });
157                 return BargingOpportunity;
158             });
159         return;
160     }
161 }
162
163 } // namespace WTF
164