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
37namespace WTF {
38
39template<typename LockType, LockType isHeldBit, LockType hasParkedBit, typename Hooks>
40void 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
105template<typename LockType, LockType isHeldBit, LockType hasParkedBit, typename Hooks>
106void 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 if ((oldByteValue & mask) != isHeldBit
114 && (oldByteValue & mask) != (isHeldBit | hasParkedBit)) {
115 dataLog("Invalid value for lock: ", oldByteValue, "\n");
116 RELEASE_ASSERT_NOT_REACHED();
117 }
118
119 if ((oldByteValue & mask) == isHeldBit) {
120 if (lock.compareExchangeWeak(oldByteValue, Hooks::unlockHook(oldByteValue & ~isHeldBit)))
121 return;
122 continue;
123 }
124
125 // Someone is parked. Unpark exactly one thread. We may hand the lock to that thread
126 // directly, or we will unlock the lock at the same time as we unpark to allow for barging.
127 // When we unlock, we may leave the parked bit set if there is a chance that there are still
128 // other threads parked.
129 ASSERT((oldByteValue & mask) == (isHeldBit | hasParkedBit));
130 ParkingLot::unparkOne(
131 &lock,
132 [&] (ParkingLot::UnparkResult result) -> intptr_t {
133 // We are the only ones that can clear either the isHeldBit or the hasParkedBit,
134 // so we should still see both bits set right now.
135 ASSERT((lock.load() & mask) == (isHeldBit | hasParkedBit));
136
137 if (result.didUnparkThread && (fairness == Fair || result.timeToBeFair)) {
138 // We don't unlock anything. Instead, we hand the lock to the thread that was
139 // waiting.
140 lock.transaction(
141 [&] (LockType& value) -> bool {
142 LockType newValue = Hooks::handoffHook(value);
143 if (newValue == value)
144 return false;
145 value = newValue;
146 return true;
147 });
148 return DirectHandoff;
149 }
150
151 lock.transaction(
152 [&] (LockType& value) -> bool {
153 value &= ~mask;
154 value = Hooks::unlockHook(value);
155 if (result.mayHaveMoreThreads)
156 value |= hasParkedBit;
157 return true;
158 });
159 return BargingOpportunity;
160 });
161 return;
162 }
163}
164
165} // namespace WTF
166
167