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