251 lines
10 KiB
C++
251 lines
10 KiB
C++
/*
|
|
* 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 <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::scoped_lock<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
|
|
|