blob: ff8f2001eb9dc975e31208e1b8fa8c16deec12b1 [file] [log] [blame]
/*
* Copyright (C) 2015-2019 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#pragma once
#include <wtf/DataLog.h>
#include <wtf/LockAlgorithm.h>
#include <wtf/ParkingLot.h>
#include <wtf/Threading.h>
// It's a good idea to avoid including this header in too many places, so that it's possible to change
// the lock algorithm slow path without recompiling the world. Right now this should be included in two
// places (Lock.cpp and JSCell.cpp).
namespace WTF {
template<typename LockType, LockType isHeldBit, LockType hasParkedBit, typename Hooks>
void LockAlgorithm<LockType, isHeldBit, hasParkedBit, Hooks>::lockSlow(Atomic<LockType>& lock)
{
// This magic number turns out to be optimal based on past JikesRVM experiments.
static constexpr unsigned spinLimit = 40;
unsigned spinCount = 0;
for (;;) {
LockType currentValue = lock.load();
// We allow ourselves to barge in.
if (!(currentValue & isHeldBit)) {
if (lock.compareExchangeWeak(currentValue, Hooks::lockHook(currentValue | isHeldBit)))
return;
continue;
}
// If there is nobody parked and we haven't spun too much, we can just try to spin around.
if (!(currentValue & hasParkedBit) && spinCount < spinLimit) {
spinCount++;
Thread::yield();
continue;
}
// Need to park. We do this by setting the parked bit first, and then parking. We spin around
// if the parked bit wasn't set and we failed at setting it.
if (!(currentValue & hasParkedBit)) {
LockType newValue = Hooks::parkHook(currentValue | hasParkedBit);
if (!lock.compareExchangeWeak(currentValue, newValue))
continue;
currentValue = newValue;
}
if (!(currentValue & isHeldBit)) {
dataLog("Lock not held!\n");
RELEASE_ASSERT_NOT_REACHED();
}
if (!(currentValue & hasParkedBit)) {
dataLog("Lock not parked!\n");
RELEASE_ASSERT_NOT_REACHED();
}
// We now expect the value to be isHeld|hasParked. So long as that's the case, we can park.
ParkingLot::ParkResult parkResult =
ParkingLot::compareAndPark(&lock, currentValue);
if (parkResult.wasUnparked) {
switch (static_cast<Token>(parkResult.token)) {
case DirectHandoff:
// The lock was never released. It was handed to us directly by the thread that did
// unlock(). This means we're done!
RELEASE_ASSERT(isLocked(lock));
return;
case BargingOpportunity:
// This is the common case. The thread that called unlock() has released the lock,
// and we have been woken up so that we may get an opportunity to grab the lock. But
// other threads may barge, so the best that we can do is loop around and try again.
break;
}
}
// We have awoken, or we never parked because the byte value changed. Either way, we loop
// around and try again.
}
}
template<typename LockType, LockType isHeldBit, LockType hasParkedBit, typename Hooks>
void LockAlgorithm<LockType, isHeldBit, hasParkedBit, Hooks>::unlockSlow(Atomic<LockType>& lock, Fairness fairness)
{
// We could get here because the weak CAS in unlock() failed spuriously, or because there is
// someone parked. So, we need a CAS loop: even if right now the lock is just held, it could
// be held and parked if someone attempts to lock just as we are unlocking.
for (;;) {
uint8_t oldByteValue = lock.load();
if ((oldByteValue & mask) != isHeldBit
&& (oldByteValue & mask) != (isHeldBit | hasParkedBit)) {
dataLog("Invalid value for lock: ", oldByteValue, "\n");
RELEASE_ASSERT_NOT_REACHED();
}
if ((oldByteValue & mask) == isHeldBit) {
if (lock.compareExchangeWeak(oldByteValue, Hooks::unlockHook(oldByteValue & ~isHeldBit)))
return;
continue;
}
// Someone is parked. Unpark exactly one thread. We may hand the lock to that thread
// directly, or we will unlock the lock at the same time as we unpark to allow for barging.
// When we unlock, we may leave the parked bit set if there is a chance that there are still
// other threads parked.
ASSERT((oldByteValue & mask) == (isHeldBit | hasParkedBit));
ParkingLot::unparkOne(
&lock,
[&] (ParkingLot::UnparkResult result) -> intptr_t {
// We are the only ones that can clear either the isHeldBit or the hasParkedBit,
// so we should still see both bits set right now.
ASSERT((lock.load() & mask) == (isHeldBit | hasParkedBit));
if (result.didUnparkThread && (fairness == Fair || result.timeToBeFair)) {
// We don't unlock anything. Instead, we hand the lock to the thread that was
// waiting.
lock.transaction(
[&] (LockType& value) -> bool {
LockType newValue = Hooks::handoffHook(value);
if (newValue == value)
return false;
value = newValue;
return true;
});
return DirectHandoff;
}
lock.transaction(
[&] (LockType& value) -> bool {
value &= ~mask;
value = Hooks::unlockHook(value);
if (result.mayHaveMoreThreads)
value |= hasParkedBit;
return true;
});
return BargingOpportunity;
});
return;
}
}
} // namespace WTF