blob: bacad2e321f33ab0b609dd1f27ac6246cf50a683 [file] [log] [blame]
/*
* Copyright (C) 2015-2017 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.
*/
#ifndef ToyLocks_h
#define ToyLocks_h
#include <mutex>
#include <thread>
#include <wtf/Atomics.h>
#include <wtf/Lock.h>
#include <wtf/ParkingLot.h>
#include <wtf/WordLock.h>
#if __has_include(<os/lock.h>)
#include <os/lock.h>
#define HAS_UNFAIR_LOCK
#endif
#if defined(EXTRA_LOCKS) && EXTRA_LOCKS
#include <synchronic>
#endif
namespace {
unsigned toyLockSpinLimit = 40;
// This is the old WTF::SpinLock class, included here so that we can still compare our new locks to a
// spinlock baseline.
class YieldSpinLock {
public:
YieldSpinLock()
{
m_lock.store(0, std::memory_order_relaxed);
}
void lock()
{
while (!m_lock.compareExchangeWeak(0, 1, std::memory_order_acquire))
Thread::yield();
}
void unlock()
{
m_lock.store(0, std::memory_order_release);
}
bool isLocked() const
{
return m_lock.load(std::memory_order_acquire);
}
private:
Atomic<unsigned> m_lock;
};
class PauseSpinLock {
public:
PauseSpinLock()
{
m_lock.store(0, std::memory_order_relaxed);
}
void lock()
{
while (!m_lock.compareExchangeWeak(0, 1, std::memory_order_acquire))
asm volatile ("pause");
}
void unlock()
{
m_lock.store(0, std::memory_order_release);
}
bool isLocked() const
{
return m_lock.load(std::memory_order_acquire);
}
private:
Atomic<unsigned> m_lock;
};
#if defined(EXTRA_LOCKS) && EXTRA_LOCKS
class TransactionalSpinLock {
public:
TransactionalSpinLock()
{
m_lock = 0;
}
void lock()
{
for (;;) {
unsigned char result;
unsigned expected = 0;
unsigned desired = 1;
asm volatile (
"xacquire; lock; cmpxchgl %3, %2\n\t"
"sete %1"
: "+a"(expected), "=q"(result), "+m"(m_lock)
: "r"(desired)
: "memory");
if (result)
return;
Thread::yield();
}
}
void unlock()
{
asm volatile (
"xrelease; movl $0, %0"
:
: "m"(m_lock)
: "memory");
}
bool isLocked() const
{
return m_lock;
}
private:
unsigned m_lock;
};
class SynchronicLock {
public:
SynchronicLock()
: m_locked(0)
{
}
void lock()
{
for (;;) {
int state = 0;
if (m_locked.compare_exchange_weak(state, 1, std::memory_order_acquire))
return;
m_sync.wait_for_change(m_locked, state, std::memory_order_relaxed);
}
}
void unlock()
{
m_sync.notify_one(m_locked, 0, std::memory_order_release);
}
bool isLocked()
{
return m_locked.load();
}
private:
std::atomic<int> m_locked;
std::experimental::synchronic<int> m_sync;
};
#endif
template<typename StateType>
class BargingLock {
public:
BargingLock()
{
m_state.store(0);
}
void lock()
{
if (LIKELY(m_state.compareExchangeWeak(0, isLockedBit, std::memory_order_acquire)))
return;
lockSlow();
}
void unlock()
{
if (LIKELY(m_state.compareExchangeWeak(isLockedBit, 0, std::memory_order_release)))
return;
unlockSlow();
}
bool isLocked() const
{
return m_state.load(std::memory_order_acquire) & isLockedBit;
}
private:
NEVER_INLINE void lockSlow()
{
for (unsigned i = toyLockSpinLimit; i--;) {
StateType currentState = m_state.load();
if (!(currentState & isLockedBit)
&& m_state.compareExchangeWeak(currentState, currentState | isLockedBit))
return;
if (currentState & hasParkedBit)
break;
Thread::yield();
}
for (;;) {
StateType currentState = m_state.load();
if (!(currentState & isLockedBit)
&& m_state.compareExchangeWeak(currentState, currentState | isLockedBit))
return;
m_state.compareExchangeWeak(isLockedBit, isLockedBit | hasParkedBit);
ParkingLot::compareAndPark(&m_state, isLockedBit | hasParkedBit);
}
}
NEVER_INLINE void unlockSlow()
{
ParkingLot::unparkOne(
&m_state,
[this] (ParkingLot::UnparkResult result) -> intptr_t {
if (result.mayHaveMoreThreads)
m_state.store(hasParkedBit);
else
m_state.store(0);
return 0;
});
}
static const StateType isLockedBit = 1;
static const StateType hasParkedBit = 2;
Atomic<StateType> m_state;
};
template<typename StateType>
class ThunderLock {
public:
ThunderLock()
{
m_state.store(Unlocked);
}
void lock()
{
if (LIKELY(m_state.compareExchangeWeak(Unlocked, Locked, std::memory_order_acquire)))
return;
lockSlow();
}
void unlock()
{
if (LIKELY(m_state.compareExchangeWeak(Locked, Unlocked, std::memory_order_release)))
return;
unlockSlow();
}
bool isLocked() const
{
return m_state.load(std::memory_order_acquire) != Unlocked;
}
private:
NEVER_INLINE void lockSlow()
{
for (unsigned i = toyLockSpinLimit; i--;) {
State currentState = m_state.load();
if (currentState == Unlocked
&& m_state.compareExchangeWeak(Unlocked, Locked))
return;
if (currentState == LockedAndParked)
break;
Thread::yield();
}
for (;;) {
if (m_state.compareExchangeWeak(Unlocked, Locked))
return;
m_state.compareExchangeWeak(Locked, LockedAndParked);
ParkingLot::compareAndPark(&m_state, LockedAndParked);
}
}
NEVER_INLINE void unlockSlow()
{
if (m_state.exchange(Unlocked) == LockedAndParked)
ParkingLot::unparkAll(&m_state);
}
enum State : StateType {
Unlocked,
Locked,
LockedAndParked
};
Atomic<State> m_state;
};
template<typename StateType>
class CascadeLock {
public:
CascadeLock()
{
m_state.store(Unlocked);
}
void lock()
{
if (LIKELY(m_state.compareExchangeWeak(Unlocked, Locked, std::memory_order_acquire)))
return;
lockSlow();
}
void unlock()
{
if (LIKELY(m_state.compareExchangeWeak(Locked, Unlocked, std::memory_order_release)))
return;
unlockSlow();
}
bool isLocked() const
{
return m_state.load(std::memory_order_acquire) != Unlocked;
}
private:
NEVER_INLINE void lockSlow()
{
for (unsigned i = toyLockSpinLimit; i--;) {
State currentState = m_state.load();
if (currentState == Unlocked
&& m_state.compareExchangeWeak(Unlocked, Locked))
return;
if (currentState == LockedAndParked)
break;
Thread::yield();
}
State desiredState = Locked;
for (;;) {
if (m_state.compareExchangeWeak(Unlocked, desiredState))
return;
desiredState = LockedAndParked;
m_state.compareExchangeWeak(Locked, LockedAndParked);
ParkingLot::compareAndPark(&m_state, LockedAndParked);
}
}
NEVER_INLINE void unlockSlow()
{
if (m_state.exchange(Unlocked) == LockedAndParked)
ParkingLot::unparkOne(&m_state);
}
enum State : StateType {
Unlocked,
Locked,
LockedAndParked
};
Atomic<State> m_state;
};
class HandoffLock {
public:
HandoffLock()
{
m_state.store(0);
}
void lock()
{
if (LIKELY(m_state.compareExchangeWeak(0, isLockedBit, std::memory_order_acquire)))
return;
lockSlow();
}
void unlock()
{
if (LIKELY(m_state.compareExchangeWeak(isLockedBit, 0, std::memory_order_release)))
return;
unlockSlow();
}
bool isLocked() const
{
return m_state.load(std::memory_order_acquire) & isLockedBit;
}
private:
NEVER_INLINE void lockSlow()
{
for (;;) {
unsigned state = m_state.load();
if (!(state & isLockedBit)) {
if (m_state.compareExchangeWeak(state, state | isLockedBit))
return;
continue;
}
if (m_state.compareExchangeWeak(state, state + parkedCountUnit)) {
bool result = ParkingLot::compareAndPark(&m_state, state + parkedCountUnit).wasUnparked;
m_state.exchangeAdd(-parkedCountUnit);
if (result)
return;
}
}
}
NEVER_INLINE void unlockSlow()
{
for (;;) {
unsigned state = m_state.load();
if (!(state >> parkedCountShift)) {
RELEASE_ASSERT(state == isLockedBit);
if (m_state.compareExchangeWeak(isLockedBit, 0))
return;
continue;
}
if (ParkingLot::unparkOne(&m_state).didUnparkThread) {
// We unparked someone. There are now running and they hold the lock.
return;
}
// Nobody unparked. Maybe there isn't anyone waiting. Just try again.
}
}
static const unsigned isLockedBit = 1;
static const unsigned parkedCountShift = 1;
static const unsigned parkedCountUnit = 1 << parkedCountShift;
Atomic<unsigned> m_state;
};
#ifdef HAS_UNFAIR_LOCK
class UnfairLock {
os_unfair_lock l = OS_UNFAIR_LOCK_INIT;
public:
void lock()
{
os_unfair_lock_lock(&l);
}
void unlock()
{
os_unfair_lock_unlock(&l);
}
};
#endif
template<typename Benchmark>
void runEverything(const char* what)
{
if (!strcmp(what, "yieldspinlock") || !strcmp(what, "all"))
Benchmark::template run<YieldSpinLock>("YieldSpinLock");
if (!strcmp(what, "pausespinlock") || !strcmp(what, "all"))
Benchmark::template run<PauseSpinLock>("PauseSpinLock");
#if defined(EXTRA_LOCKS) && EXTRA_LOCKS
if (!strcmp(what, "transactionalspinlock") || !strcmp(what, "all"))
Benchmark::template run<TransactionalSpinLock>("TransactionalSpinLock");
if (!strcmp(what, "synchroniclock") || !strcmp(what, "all"))
Benchmark::template run<SynchronicLock>("SynchronicLock");
#endif
if (!strcmp(what, "wordlock") || !strcmp(what, "all"))
Benchmark::template run<WordLock>("WTFWordLock");
if (!strcmp(what, "lock") || !strcmp(what, "all"))
Benchmark::template run<Lock>("WTFLock");
if (!strcmp(what, "barginglock") || !strcmp(what, "all"))
Benchmark::template run<BargingLock<uint8_t>>("ByteBargingLock");
if (!strcmp(what, "bargingwordlock") || !strcmp(what, "all"))
Benchmark::template run<BargingLock<uint32_t>>("WordBargingLock");
if (!strcmp(what, "thunderlock") || !strcmp(what, "all"))
Benchmark::template run<ThunderLock<uint8_t>>("ByteThunderLock");
if (!strcmp(what, "thunderwordlock") || !strcmp(what, "all"))
Benchmark::template run<ThunderLock<uint32_t>>("WordThunderLock");
if (!strcmp(what, "cascadelock") || !strcmp(what, "all"))
Benchmark::template run<CascadeLock<uint8_t>>("ByteCascadeLock");
if (!strcmp(what, "cascadewordlock") || !strcmp(what, "all"))
Benchmark::template run<CascadeLock<uint32_t>>("WordCascadeLock");
if (!strcmp(what, "handofflock") || !strcmp(what, "all"))
Benchmark::template run<HandoffLock>("HandoffLock");
#ifdef HAS_UNFAIR_LOCK
if (!strcmp(what, "unfairlock") || !strcmp(what, "all"))
Benchmark::template run<UnfairLock>("UnfairLock");
#endif
if (!strcmp(what, "mutex") || !strcmp(what, "all"))
Benchmark::template run<std::mutex>("std::mutex");
}
} // anonymous namespace
#endif // ToyLocks_h