#ifndef WTF_LockAlgorithm_h
#define WTF_LockAlgorithm_h
#include <thread>
#include <wtf/Atomics.h>
#include <wtf/Compiler.h>
#include <wtf/ParkingLot.h>
namespace WTF {
template<typename LockType, LockType isHeldBit, LockType hasParkedBit>
class LockAlgorithm {
static const bool verbose = false;
static const LockType mask = isHeldBit | hasParkedBit;
public:
static bool lockFastAssumingZero(Atomic<LockType>& lock)
{
return lock.compareExchangeWeak(0, isHeldBit, std::memory_order_acquire);
}
static bool lockFast(Atomic<LockType>& lock)
{
LockType oldValue = lock.load(std::memory_order_relaxed);
if (oldValue & isHeldBit)
return false;
return lock.compareExchangeWeak(oldValue, oldValue | isHeldBit, std::memory_order_acquire);
}
static void lock(Atomic<LockType>& lock)
{
if (UNLIKELY(!lockFast(lock)))
lockSlow(lock);
}
static bool tryLock(Atomic<LockType>& lock)
{
for (;;) {
uint8_t currentByteValue = lock.load(std::memory_order_relaxed);
if (currentByteValue & isHeldBit)
return false;
if (lock.compareExchangeWeak(currentByteValue, currentByteValue | isHeldBit, std::memory_order_acquire))
return true;
}
}
static bool unlockFastAssumingZero(Atomic<LockType>& lock)
{
return lock.compareExchangeWeak(isHeldBit, 0, std::memory_order_release);
}
static bool unlockFast(Atomic<LockType>& lock)
{
LockType oldValue = lock.load(std::memory_order_relaxed);
if ((oldValue & mask) != isHeldBit)
return false;
return lock.compareExchangeWeak(oldValue, oldValue & ~isHeldBit, std::memory_order_release);
}
static void unlock(Atomic<LockType>& lock)
{
if (UNLIKELY(!unlockFast(lock)))
unlockSlow(lock, Unfair);
}
static void unlockFairly(Atomic<LockType>& lock)
{
if (UNLIKELY(!unlockFast(lock)))
unlockSlow(lock, Fair);
}
static bool safepointFast(const Atomic<LockType>& lock)
{
WTF::compilerFence();
return !(lock.load(std::memory_order_relaxed) & hasParkedBit);
}
static void safepoint(Atomic<LockType>& lock)
{
if (UNLIKELY(!safepointFast(lock)))
safepointSlow(lock);
}
static bool isLocked(const Atomic<LockType>& lock)
{
return lock.load(std::memory_order_acquire) & isHeldBit;
}
NEVER_INLINE static void lockSlow(Atomic<LockType>& lock)
{
unsigned spinCount = 0;
const unsigned spinLimit = 40;
for (;;) {
uint8_t currentByteValue = lock.load();
if (!(currentByteValue & isHeldBit)
&& lock.compareExchangeWeak(currentByteValue, currentByteValue | isHeldBit))
return;
if (!(currentByteValue & hasParkedBit) && spinCount < spinLimit) {
spinCount++;
std::this_thread::yield();
continue;
}
if (!(currentByteValue & hasParkedBit)
&& !lock.compareExchangeWeak(currentByteValue, currentByteValue | hasParkedBit))
continue;
ParkingLot::ParkResult parkResult =
ParkingLot::compareAndPark(&lock, currentByteValue | isHeldBit | hasParkedBit);
if (parkResult.wasUnparked) {
switch (static_cast<Token>(parkResult.token)) {
case DirectHandoff:
RELEASE_ASSERT(isLocked(lock));
return;
case BargingOpportunity:
break;
}
}
}
}
enum Fairness {
Fair,
Unfair
};
NEVER_INLINE static void unlockSlow(Atomic<LockType>& lock, Fairness fairness)
{
for (;;) {
uint8_t oldByteValue = lock.load();
RELEASE_ASSERT(
(oldByteValue & mask) == isHeldBit
|| (oldByteValue & mask) == (isHeldBit | hasParkedBit));
if ((oldByteValue & mask) == isHeldBit) {
if (lock.compareExchangeWeak(oldByteValue, oldByteValue & ~isHeldBit))
return;
continue;
}
ASSERT((oldByteValue & mask) == (isHeldBit | hasParkedBit));
ParkingLot::unparkOne(
&lock,
[&] (ParkingLot::UnparkResult result) -> intptr_t {
ASSERT((lock.load() & mask) == (isHeldBit | hasParkedBit));
if (result.didUnparkThread && (fairness == Fair || result.timeToBeFair)) {
return DirectHandoff;
}
lock.transaction(
[&] (LockType& value) {
value &= ~mask;
if (result.mayHaveMoreThreads)
value |= hasParkedBit;
});
return BargingOpportunity;
});
return;
}
}
NEVER_INLINE static void safepointSlow(Atomic<LockType>& lockWord)
{
unlockFairly(lockWord);
lock(lockWord);
}
private:
enum Token {
BargingOpportunity,
DirectHandoff
};
};
}
using WTF::LockAlgorithm;
#endif // WTF_LockAlgorithm_h