blob: fb2c78e3f314bd046ff3a897942c4ea8280afd35 [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.
*/
#include "config.h"
#include <wtf/WordLock.h>
#include <condition_variable>
#include <mutex>
#include <thread>
#include <wtf/Threading.h>
namespace WTF {
namespace {
// This data structure serves three purposes:
//
// 1) A parking mechanism for threads that go to sleep. That involves just a system mutex and
// condition variable.
//
// 2) A queue node for when a thread is on some WordLock's queue.
//
// 3) The queue head. This is kind of funky. When a thread is the head of a queue, it also serves as
// the basic queue bookkeeping data structure. When a thread is dequeued, the next thread in the
// queue takes on the queue head duties.
struct ThreadData {
// The parking mechanism.
bool shouldPark { false };
std::mutex parkingLock;
std::condition_variable parkingCondition;
// The queue node.
ThreadData* nextInQueue { nullptr };
// The queue itself.
ThreadData* queueTail { nullptr };
};
} // anonymous namespace
NEVER_INLINE void WordLock::lockSlow()
{
unsigned spinCount = 0;
// This magic number turns out to be optimal based on past JikesRVM experiments.
const unsigned spinLimit = 40;
for (;;) {
uintptr_t currentWordValue = m_word.load();
if (!(currentWordValue & isLockedBit)) {
// It's not possible for someone to hold the queue lock while the lock itself is no longer
// held, since we will only attempt to acquire the queue lock when the lock is held and
// the queue lock prevents unlock.
ASSERT(!(currentWordValue & isQueueLockedBit));
if (m_word.compareExchangeWeak(currentWordValue, currentWordValue | isLockedBit)) {
// Success! We acquired the lock.
return;
}
}
// If there is no queue and we haven't spun too much, we can just try to spin around again.
if (!(currentWordValue & ~queueHeadMask) && spinCount < spinLimit) {
spinCount++;
Thread::yield();
continue;
}
// Need to put ourselves on the queue. Create the queue if one does not exist. This requries
// owning the queue for a little bit. The lock that controls the queue is itself a spinlock.
ThreadData me;
// Reload the current word value, since some time may have passed.
currentWordValue = m_word.load();
// We proceed only if the queue lock is not held, the WordLock is held, and we succeed in
// acquiring the queue lock.
if ((currentWordValue & isQueueLockedBit)
|| !(currentWordValue & isLockedBit)
|| !m_word.compareExchangeWeak(currentWordValue, currentWordValue | isQueueLockedBit)) {
Thread::yield();
continue;
}
me.shouldPark = true;
// We own the queue. Nobody can enqueue or dequeue until we're done. Also, it's not possible
// to release the WordLock while we hold the queue lock.
ThreadData* queueHead = bitwise_cast<ThreadData*>(currentWordValue & ~queueHeadMask);
if (queueHead) {
// Put this thread at the end of the queue.
queueHead->queueTail->nextInQueue = &me;
queueHead->queueTail = &me;
// Release the queue lock.
currentWordValue = m_word.load();
ASSERT(currentWordValue & ~queueHeadMask);
ASSERT(currentWordValue & isQueueLockedBit);
ASSERT(currentWordValue & isLockedBit);
m_word.store(currentWordValue & ~isQueueLockedBit);
} else {
// Make this thread be the queue-head.
queueHead = &me;
me.queueTail = &me;
// Release the queue lock and install ourselves as the head. No need for a CAS loop, since
// we own the queue lock.
currentWordValue = m_word.load();
ASSERT(~(currentWordValue & ~queueHeadMask));
ASSERT(currentWordValue & isQueueLockedBit);
ASSERT(currentWordValue & isLockedBit);
uintptr_t newWordValue = currentWordValue;
newWordValue |= bitwise_cast<uintptr_t>(queueHead);
newWordValue &= ~isQueueLockedBit;
m_word.store(newWordValue);
}
// At this point everyone who acquires the queue lock will see me on the queue, and anyone who
// acquires me's lock will see that me wants to park. Note that shouldPark may have been
// cleared as soon as the queue lock was released above, but it will happen while the
// releasing thread holds me's parkingLock.
{
std::unique_lock<std::mutex> locker(me.parkingLock);
while (me.shouldPark)
me.parkingCondition.wait(locker);
}
ASSERT(!me.shouldPark);
ASSERT(!me.nextInQueue);
ASSERT(!me.queueTail);
// Now we can loop around and try to acquire the lock again.
}
}
NEVER_INLINE void WordLock::unlockSlow()
{
// The fast path can fail either because of spurious weak CAS failure, or because someone put a
// thread on the queue, or the queue lock is held. If the queue lock is held, it can only be
// because someone *will* enqueue a thread onto the queue.
// Acquire the queue lock, or release the lock. This loop handles both lock release in case the
// fast path's weak CAS spuriously failed and it handles queue lock acquisition if there is
// actually something interesting on the queue.
for (;;) {
uintptr_t currentWordValue = m_word.load();
ASSERT(currentWordValue & isLockedBit);
if (currentWordValue == isLockedBit) {
if (m_word.compareExchangeWeak(isLockedBit, 0)) {
// The fast path's weak CAS had spuriously failed, and now we succeeded. The lock is
// unlocked and we're done!
return;
}
// Loop around and try again.
Thread::yield();
continue;
}
if (currentWordValue & isQueueLockedBit) {
Thread::yield();
continue;
}
// If it wasn't just a spurious weak CAS failure and if the queue lock is not held, then there
// must be an entry on the queue.
ASSERT(currentWordValue & ~queueHeadMask);
if (m_word.compareExchangeWeak(currentWordValue, currentWordValue | isQueueLockedBit))
break;
}
uintptr_t currentWordValue = m_word.load();
// After we acquire the queue lock, the WordLock must still be held and the queue must be
// non-empty. The queue must be non-empty since only the lockSlow() method could have held the
// queue lock and if it did then it only releases it after putting something on the queue.
ASSERT(currentWordValue & isLockedBit);
ASSERT(currentWordValue & isQueueLockedBit);
ThreadData* queueHead = bitwise_cast<ThreadData*>(currentWordValue & ~queueHeadMask);
ASSERT(queueHead);
ThreadData* newQueueHead = queueHead->nextInQueue;
// Either this was the only thread on the queue, in which case we delete the queue, or there
// are still more threads on the queue, in which case we create a new queue head.
if (newQueueHead)
newQueueHead->queueTail = queueHead->queueTail;
// Change the queue head, possibly removing it if newQueueHead is null. No need for a CAS loop,
// since we hold the queue lock and the lock itself so nothing about the lock can change right
// now.
currentWordValue = m_word.load();
ASSERT(currentWordValue & isLockedBit);
ASSERT(currentWordValue & isQueueLockedBit);
ASSERT((currentWordValue & ~queueHeadMask) == bitwise_cast<uintptr_t>(queueHead));
uintptr_t newWordValue = currentWordValue;
newWordValue &= ~isLockedBit; // Release the WordLock.
newWordValue &= ~isQueueLockedBit; // Release the queue lock.
newWordValue &= queueHeadMask; // Clear out the old queue head.
newWordValue |= bitwise_cast<uintptr_t>(newQueueHead); // Install new queue head.
m_word.store(newWordValue);
// Now the lock is available for acquisition. But we just have to wake up the old queue head.
// After that, we're done!
queueHead->nextInQueue = nullptr;
queueHead->queueTail = nullptr;
// We do this carefully because this may run either before or during the parkingLock critical
// section in lockSlow().
{
// Be sure to hold the lock across our call to notify_one() because a spurious wakeup could
// cause the thread at the head of the queue to exit and delete queueHead.
std::lock_guard<std::mutex> locker(queueHead->parkingLock);
queueHead->shouldPark = false;
// Doesn't matter if we notify_all() or notify_one() here since the only thread that could be
// waiting is queueHead.
queueHead->parkingCondition.notify_one();
}
// The old queue head can now contend for the lock again. We're done!
}
} // namespace WTF