Always use a byte-sized lock implementation
https://bugs.webkit.org/show_bug.cgi?id=147908
Reviewed by Geoffrey Garen.
Source/JavaScriptCore:
* runtime/ConcurrentJITLock.h: Lock is now byte-sized and ByteLock is gone, so use Lock.
Source/WTF:
At the start of my locking algorithm crusade, I implemented Lock, which is a sizeof(void*)
lock implementation with some nice theoretical properties and good performance. Then I added
the ParkingLot abstraction and ByteLock. ParkingLot uses Lock in its implementation.
ByteLock uses ParkingLot to create a sizeof(char) lock implementation that performs like
Lock.
It turns out that ByteLock is always at least as good as Lock, and sometimes a lot better:
it requires 8x less memory on 64-bit systems. It's hard to construct a benchmark where
ByteLock is significantly slower than Lock, and when you do construct such a benchmark,
tweaking it a bit can also create a scenario where ByteLock is significantly faster than
Lock.
So, the thing that we call "Lock" should really use ByteLock's algorithm, since it is more
compact and just as fast. That's what this patch does.
But we still need to keep the old Lock algorithm, because it's used to implement ParkingLot,
which in turn is used to implement ByteLock. So this patch does this transformation:
- Move the algorithm in Lock into files called WordLock.h|cpp. Make ParkingLot use
WordLock.
- Move the algorithm in ByteLock into Lock.h|cpp. Make everyone who used ByteLock use Lock
instead. All other users of Lock now get the byte-sized lock implementation.
- Remove the old ByteLock files.
* WTF.vcxproj/WTF.vcxproj:
* WTF.xcodeproj/project.pbxproj:
* benchmarks/LockSpeedTest.cpp:
(main):
* wtf/WordLock.cpp: Added.
(WTF::WordLock::lockSlow):
(WTF::WordLock::unlockSlow):
* wtf/WordLock.h: Added.
(WTF::WordLock::WordLock):
(WTF::WordLock::lock):
(WTF::WordLock::unlock):
(WTF::WordLock::isHeld):
(WTF::WordLock::isLocked):
* wtf/ByteLock.cpp: Removed.
* wtf/ByteLock.h: Removed.
* wtf/CMakeLists.txt:
* wtf/Lock.cpp:
(WTF::LockBase::lockSlow):
(WTF::LockBase::unlockSlow):
* wtf/Lock.h:
(WTF::LockBase::lock):
(WTF::LockBase::unlock):
(WTF::LockBase::isHeld):
(WTF::LockBase::isLocked):
(WTF::Lock::Lock):
* wtf/ParkingLot.cpp:
Tools:
All previous tests of Lock are now tests of WordLock. All previous tests of ByteLock are
now tests of Lock.
* TestWebKitAPI/Tests/WTF/Lock.cpp:
(TestWebKitAPI::runLockTest):
(TestWebKitAPI::TEST):
Canonical link: https://commits.webkit.org/166025@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@188323 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2015-08-12 04:20:24 +00:00
|
|
|
/*
|
2017-07-22 14:36:18 +00:00
|
|
|
* Copyright (C) 2015-2017 Apple Inc. All rights reserved.
|
Always use a byte-sized lock implementation
https://bugs.webkit.org/show_bug.cgi?id=147908
Reviewed by Geoffrey Garen.
Source/JavaScriptCore:
* runtime/ConcurrentJITLock.h: Lock is now byte-sized and ByteLock is gone, so use Lock.
Source/WTF:
At the start of my locking algorithm crusade, I implemented Lock, which is a sizeof(void*)
lock implementation with some nice theoretical properties and good performance. Then I added
the ParkingLot abstraction and ByteLock. ParkingLot uses Lock in its implementation.
ByteLock uses ParkingLot to create a sizeof(char) lock implementation that performs like
Lock.
It turns out that ByteLock is always at least as good as Lock, and sometimes a lot better:
it requires 8x less memory on 64-bit systems. It's hard to construct a benchmark where
ByteLock is significantly slower than Lock, and when you do construct such a benchmark,
tweaking it a bit can also create a scenario where ByteLock is significantly faster than
Lock.
So, the thing that we call "Lock" should really use ByteLock's algorithm, since it is more
compact and just as fast. That's what this patch does.
But we still need to keep the old Lock algorithm, because it's used to implement ParkingLot,
which in turn is used to implement ByteLock. So this patch does this transformation:
- Move the algorithm in Lock into files called WordLock.h|cpp. Make ParkingLot use
WordLock.
- Move the algorithm in ByteLock into Lock.h|cpp. Make everyone who used ByteLock use Lock
instead. All other users of Lock now get the byte-sized lock implementation.
- Remove the old ByteLock files.
* WTF.vcxproj/WTF.vcxproj:
* WTF.xcodeproj/project.pbxproj:
* benchmarks/LockSpeedTest.cpp:
(main):
* wtf/WordLock.cpp: Added.
(WTF::WordLock::lockSlow):
(WTF::WordLock::unlockSlow):
* wtf/WordLock.h: Added.
(WTF::WordLock::WordLock):
(WTF::WordLock::lock):
(WTF::WordLock::unlock):
(WTF::WordLock::isHeld):
(WTF::WordLock::isLocked):
* wtf/ByteLock.cpp: Removed.
* wtf/ByteLock.h: Removed.
* wtf/CMakeLists.txt:
* wtf/Lock.cpp:
(WTF::LockBase::lockSlow):
(WTF::LockBase::unlockSlow):
* wtf/Lock.h:
(WTF::LockBase::lock):
(WTF::LockBase::unlock):
(WTF::LockBase::isHeld):
(WTF::LockBase::isLocked):
(WTF::Lock::Lock):
* wtf/ParkingLot.cpp:
Tools:
All previous tests of Lock are now tests of WordLock. All previous tests of ByteLock are
now tests of Lock.
* TestWebKitAPI/Tests/WTF/Lock.cpp:
(TestWebKitAPI::runLockTest):
(TestWebKitAPI::TEST):
Canonical link: https://commits.webkit.org/166025@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@188323 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2015-08-12 04:20:24 +00:00
|
|
|
*
|
|
|
|
* 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"
|
2018-10-15 14:24:49 +00:00
|
|
|
#include <wtf/WordLock.h>
|
Always use a byte-sized lock implementation
https://bugs.webkit.org/show_bug.cgi?id=147908
Reviewed by Geoffrey Garen.
Source/JavaScriptCore:
* runtime/ConcurrentJITLock.h: Lock is now byte-sized and ByteLock is gone, so use Lock.
Source/WTF:
At the start of my locking algorithm crusade, I implemented Lock, which is a sizeof(void*)
lock implementation with some nice theoretical properties and good performance. Then I added
the ParkingLot abstraction and ByteLock. ParkingLot uses Lock in its implementation.
ByteLock uses ParkingLot to create a sizeof(char) lock implementation that performs like
Lock.
It turns out that ByteLock is always at least as good as Lock, and sometimes a lot better:
it requires 8x less memory on 64-bit systems. It's hard to construct a benchmark where
ByteLock is significantly slower than Lock, and when you do construct such a benchmark,
tweaking it a bit can also create a scenario where ByteLock is significantly faster than
Lock.
So, the thing that we call "Lock" should really use ByteLock's algorithm, since it is more
compact and just as fast. That's what this patch does.
But we still need to keep the old Lock algorithm, because it's used to implement ParkingLot,
which in turn is used to implement ByteLock. So this patch does this transformation:
- Move the algorithm in Lock into files called WordLock.h|cpp. Make ParkingLot use
WordLock.
- Move the algorithm in ByteLock into Lock.h|cpp. Make everyone who used ByteLock use Lock
instead. All other users of Lock now get the byte-sized lock implementation.
- Remove the old ByteLock files.
* WTF.vcxproj/WTF.vcxproj:
* WTF.xcodeproj/project.pbxproj:
* benchmarks/LockSpeedTest.cpp:
(main):
* wtf/WordLock.cpp: Added.
(WTF::WordLock::lockSlow):
(WTF::WordLock::unlockSlow):
* wtf/WordLock.h: Added.
(WTF::WordLock::WordLock):
(WTF::WordLock::lock):
(WTF::WordLock::unlock):
(WTF::WordLock::isHeld):
(WTF::WordLock::isLocked):
* wtf/ByteLock.cpp: Removed.
* wtf/ByteLock.h: Removed.
* wtf/CMakeLists.txt:
* wtf/Lock.cpp:
(WTF::LockBase::lockSlow):
(WTF::LockBase::unlockSlow):
* wtf/Lock.h:
(WTF::LockBase::lock):
(WTF::LockBase::unlock):
(WTF::LockBase::isHeld):
(WTF::LockBase::isLocked):
(WTF::Lock::Lock):
* wtf/ParkingLot.cpp:
Tools:
All previous tests of Lock are now tests of WordLock. All previous tests of ByteLock are
now tests of Lock.
* TestWebKitAPI/Tests/WTF/Lock.cpp:
(TestWebKitAPI::runLockTest):
(TestWebKitAPI::TEST):
Canonical link: https://commits.webkit.org/166025@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@188323 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2015-08-12 04:20:24 +00:00
|
|
|
|
|
|
|
#include <condition_variable>
|
|
|
|
#include <mutex>
|
2018-10-15 14:24:49 +00:00
|
|
|
#include <wtf/Threading.h>
|
Always use a byte-sized lock implementation
https://bugs.webkit.org/show_bug.cgi?id=147908
Reviewed by Geoffrey Garen.
Source/JavaScriptCore:
* runtime/ConcurrentJITLock.h: Lock is now byte-sized and ByteLock is gone, so use Lock.
Source/WTF:
At the start of my locking algorithm crusade, I implemented Lock, which is a sizeof(void*)
lock implementation with some nice theoretical properties and good performance. Then I added
the ParkingLot abstraction and ByteLock. ParkingLot uses Lock in its implementation.
ByteLock uses ParkingLot to create a sizeof(char) lock implementation that performs like
Lock.
It turns out that ByteLock is always at least as good as Lock, and sometimes a lot better:
it requires 8x less memory on 64-bit systems. It's hard to construct a benchmark where
ByteLock is significantly slower than Lock, and when you do construct such a benchmark,
tweaking it a bit can also create a scenario where ByteLock is significantly faster than
Lock.
So, the thing that we call "Lock" should really use ByteLock's algorithm, since it is more
compact and just as fast. That's what this patch does.
But we still need to keep the old Lock algorithm, because it's used to implement ParkingLot,
which in turn is used to implement ByteLock. So this patch does this transformation:
- Move the algorithm in Lock into files called WordLock.h|cpp. Make ParkingLot use
WordLock.
- Move the algorithm in ByteLock into Lock.h|cpp. Make everyone who used ByteLock use Lock
instead. All other users of Lock now get the byte-sized lock implementation.
- Remove the old ByteLock files.
* WTF.vcxproj/WTF.vcxproj:
* WTF.xcodeproj/project.pbxproj:
* benchmarks/LockSpeedTest.cpp:
(main):
* wtf/WordLock.cpp: Added.
(WTF::WordLock::lockSlow):
(WTF::WordLock::unlockSlow):
* wtf/WordLock.h: Added.
(WTF::WordLock::WordLock):
(WTF::WordLock::lock):
(WTF::WordLock::unlock):
(WTF::WordLock::isHeld):
(WTF::WordLock::isLocked):
* wtf/ByteLock.cpp: Removed.
* wtf/ByteLock.h: Removed.
* wtf/CMakeLists.txt:
* wtf/Lock.cpp:
(WTF::LockBase::lockSlow):
(WTF::LockBase::unlockSlow):
* wtf/Lock.h:
(WTF::LockBase::lock):
(WTF::LockBase::unlock):
(WTF::LockBase::isHeld):
(WTF::LockBase::isLocked):
(WTF::Lock::Lock):
* wtf/ParkingLot.cpp:
Tools:
All previous tests of Lock are now tests of WordLock. All previous tests of ByteLock are
now tests of Lock.
* TestWebKitAPI/Tests/WTF/Lock.cpp:
(TestWebKitAPI::runLockTest):
(TestWebKitAPI::TEST):
Canonical link: https://commits.webkit.org/166025@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@188323 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2015-08-12 04:20:24 +00:00
|
|
|
|
|
|
|
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
|
|
|
|
|
2017-12-07 03:52:09 +00:00
|
|
|
NEVER_INLINE void WordLock::lockSlow()
|
Always use a byte-sized lock implementation
https://bugs.webkit.org/show_bug.cgi?id=147908
Reviewed by Geoffrey Garen.
Source/JavaScriptCore:
* runtime/ConcurrentJITLock.h: Lock is now byte-sized and ByteLock is gone, so use Lock.
Source/WTF:
At the start of my locking algorithm crusade, I implemented Lock, which is a sizeof(void*)
lock implementation with some nice theoretical properties and good performance. Then I added
the ParkingLot abstraction and ByteLock. ParkingLot uses Lock in its implementation.
ByteLock uses ParkingLot to create a sizeof(char) lock implementation that performs like
Lock.
It turns out that ByteLock is always at least as good as Lock, and sometimes a lot better:
it requires 8x less memory on 64-bit systems. It's hard to construct a benchmark where
ByteLock is significantly slower than Lock, and when you do construct such a benchmark,
tweaking it a bit can also create a scenario where ByteLock is significantly faster than
Lock.
So, the thing that we call "Lock" should really use ByteLock's algorithm, since it is more
compact and just as fast. That's what this patch does.
But we still need to keep the old Lock algorithm, because it's used to implement ParkingLot,
which in turn is used to implement ByteLock. So this patch does this transformation:
- Move the algorithm in Lock into files called WordLock.h|cpp. Make ParkingLot use
WordLock.
- Move the algorithm in ByteLock into Lock.h|cpp. Make everyone who used ByteLock use Lock
instead. All other users of Lock now get the byte-sized lock implementation.
- Remove the old ByteLock files.
* WTF.vcxproj/WTF.vcxproj:
* WTF.xcodeproj/project.pbxproj:
* benchmarks/LockSpeedTest.cpp:
(main):
* wtf/WordLock.cpp: Added.
(WTF::WordLock::lockSlow):
(WTF::WordLock::unlockSlow):
* wtf/WordLock.h: Added.
(WTF::WordLock::WordLock):
(WTF::WordLock::lock):
(WTF::WordLock::unlock):
(WTF::WordLock::isHeld):
(WTF::WordLock::isLocked):
* wtf/ByteLock.cpp: Removed.
* wtf/ByteLock.h: Removed.
* wtf/CMakeLists.txt:
* wtf/Lock.cpp:
(WTF::LockBase::lockSlow):
(WTF::LockBase::unlockSlow):
* wtf/Lock.h:
(WTF::LockBase::lock):
(WTF::LockBase::unlock):
(WTF::LockBase::isHeld):
(WTF::LockBase::isLocked):
(WTF::Lock::Lock):
* wtf/ParkingLot.cpp:
Tools:
All previous tests of Lock are now tests of WordLock. All previous tests of ByteLock are
now tests of Lock.
* TestWebKitAPI/Tests/WTF/Lock.cpp:
(TestWebKitAPI::runLockTest):
(TestWebKitAPI::TEST):
Canonical link: https://commits.webkit.org/166025@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@188323 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2015-08-12 04:20:24 +00:00
|
|
|
{
|
|
|
|
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++;
|
2017-07-22 14:36:18 +00:00
|
|
|
Thread::yield();
|
Always use a byte-sized lock implementation
https://bugs.webkit.org/show_bug.cgi?id=147908
Reviewed by Geoffrey Garen.
Source/JavaScriptCore:
* runtime/ConcurrentJITLock.h: Lock is now byte-sized and ByteLock is gone, so use Lock.
Source/WTF:
At the start of my locking algorithm crusade, I implemented Lock, which is a sizeof(void*)
lock implementation with some nice theoretical properties and good performance. Then I added
the ParkingLot abstraction and ByteLock. ParkingLot uses Lock in its implementation.
ByteLock uses ParkingLot to create a sizeof(char) lock implementation that performs like
Lock.
It turns out that ByteLock is always at least as good as Lock, and sometimes a lot better:
it requires 8x less memory on 64-bit systems. It's hard to construct a benchmark where
ByteLock is significantly slower than Lock, and when you do construct such a benchmark,
tweaking it a bit can also create a scenario where ByteLock is significantly faster than
Lock.
So, the thing that we call "Lock" should really use ByteLock's algorithm, since it is more
compact and just as fast. That's what this patch does.
But we still need to keep the old Lock algorithm, because it's used to implement ParkingLot,
which in turn is used to implement ByteLock. So this patch does this transformation:
- Move the algorithm in Lock into files called WordLock.h|cpp. Make ParkingLot use
WordLock.
- Move the algorithm in ByteLock into Lock.h|cpp. Make everyone who used ByteLock use Lock
instead. All other users of Lock now get the byte-sized lock implementation.
- Remove the old ByteLock files.
* WTF.vcxproj/WTF.vcxproj:
* WTF.xcodeproj/project.pbxproj:
* benchmarks/LockSpeedTest.cpp:
(main):
* wtf/WordLock.cpp: Added.
(WTF::WordLock::lockSlow):
(WTF::WordLock::unlockSlow):
* wtf/WordLock.h: Added.
(WTF::WordLock::WordLock):
(WTF::WordLock::lock):
(WTF::WordLock::unlock):
(WTF::WordLock::isHeld):
(WTF::WordLock::isLocked):
* wtf/ByteLock.cpp: Removed.
* wtf/ByteLock.h: Removed.
* wtf/CMakeLists.txt:
* wtf/Lock.cpp:
(WTF::LockBase::lockSlow):
(WTF::LockBase::unlockSlow):
* wtf/Lock.h:
(WTF::LockBase::lock):
(WTF::LockBase::unlock):
(WTF::LockBase::isHeld):
(WTF::LockBase::isLocked):
(WTF::Lock::Lock):
* wtf/ParkingLot.cpp:
Tools:
All previous tests of Lock are now tests of WordLock. All previous tests of ByteLock are
now tests of Lock.
* TestWebKitAPI/Tests/WTF/Lock.cpp:
(TestWebKitAPI::runLockTest):
(TestWebKitAPI::TEST):
Canonical link: https://commits.webkit.org/166025@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@188323 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2015-08-12 04:20:24 +00:00
|
|
|
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.
|
2018-04-29 17:29:13 +00:00
|
|
|
|
|
|
|
ThreadData me;
|
Always use a byte-sized lock implementation
https://bugs.webkit.org/show_bug.cgi?id=147908
Reviewed by Geoffrey Garen.
Source/JavaScriptCore:
* runtime/ConcurrentJITLock.h: Lock is now byte-sized and ByteLock is gone, so use Lock.
Source/WTF:
At the start of my locking algorithm crusade, I implemented Lock, which is a sizeof(void*)
lock implementation with some nice theoretical properties and good performance. Then I added
the ParkingLot abstraction and ByteLock. ParkingLot uses Lock in its implementation.
ByteLock uses ParkingLot to create a sizeof(char) lock implementation that performs like
Lock.
It turns out that ByteLock is always at least as good as Lock, and sometimes a lot better:
it requires 8x less memory on 64-bit systems. It's hard to construct a benchmark where
ByteLock is significantly slower than Lock, and when you do construct such a benchmark,
tweaking it a bit can also create a scenario where ByteLock is significantly faster than
Lock.
So, the thing that we call "Lock" should really use ByteLock's algorithm, since it is more
compact and just as fast. That's what this patch does.
But we still need to keep the old Lock algorithm, because it's used to implement ParkingLot,
which in turn is used to implement ByteLock. So this patch does this transformation:
- Move the algorithm in Lock into files called WordLock.h|cpp. Make ParkingLot use
WordLock.
- Move the algorithm in ByteLock into Lock.h|cpp. Make everyone who used ByteLock use Lock
instead. All other users of Lock now get the byte-sized lock implementation.
- Remove the old ByteLock files.
* WTF.vcxproj/WTF.vcxproj:
* WTF.xcodeproj/project.pbxproj:
* benchmarks/LockSpeedTest.cpp:
(main):
* wtf/WordLock.cpp: Added.
(WTF::WordLock::lockSlow):
(WTF::WordLock::unlockSlow):
* wtf/WordLock.h: Added.
(WTF::WordLock::WordLock):
(WTF::WordLock::lock):
(WTF::WordLock::unlock):
(WTF::WordLock::isHeld):
(WTF::WordLock::isLocked):
* wtf/ByteLock.cpp: Removed.
* wtf/ByteLock.h: Removed.
* wtf/CMakeLists.txt:
* wtf/Lock.cpp:
(WTF::LockBase::lockSlow):
(WTF::LockBase::unlockSlow):
* wtf/Lock.h:
(WTF::LockBase::lock):
(WTF::LockBase::unlock):
(WTF::LockBase::isHeld):
(WTF::LockBase::isLocked):
(WTF::Lock::Lock):
* wtf/ParkingLot.cpp:
Tools:
All previous tests of Lock are now tests of WordLock. All previous tests of ByteLock are
now tests of Lock.
* TestWebKitAPI/Tests/WTF/Lock.cpp:
(TestWebKitAPI::runLockTest):
(TestWebKitAPI::TEST):
Canonical link: https://commits.webkit.org/166025@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@188323 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2015-08-12 04:20:24 +00:00
|
|
|
|
|
|
|
// 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)) {
|
2017-07-22 14:36:18 +00:00
|
|
|
Thread::yield();
|
Always use a byte-sized lock implementation
https://bugs.webkit.org/show_bug.cgi?id=147908
Reviewed by Geoffrey Garen.
Source/JavaScriptCore:
* runtime/ConcurrentJITLock.h: Lock is now byte-sized and ByteLock is gone, so use Lock.
Source/WTF:
At the start of my locking algorithm crusade, I implemented Lock, which is a sizeof(void*)
lock implementation with some nice theoretical properties and good performance. Then I added
the ParkingLot abstraction and ByteLock. ParkingLot uses Lock in its implementation.
ByteLock uses ParkingLot to create a sizeof(char) lock implementation that performs like
Lock.
It turns out that ByteLock is always at least as good as Lock, and sometimes a lot better:
it requires 8x less memory on 64-bit systems. It's hard to construct a benchmark where
ByteLock is significantly slower than Lock, and when you do construct such a benchmark,
tweaking it a bit can also create a scenario where ByteLock is significantly faster than
Lock.
So, the thing that we call "Lock" should really use ByteLock's algorithm, since it is more
compact and just as fast. That's what this patch does.
But we still need to keep the old Lock algorithm, because it's used to implement ParkingLot,
which in turn is used to implement ByteLock. So this patch does this transformation:
- Move the algorithm in Lock into files called WordLock.h|cpp. Make ParkingLot use
WordLock.
- Move the algorithm in ByteLock into Lock.h|cpp. Make everyone who used ByteLock use Lock
instead. All other users of Lock now get the byte-sized lock implementation.
- Remove the old ByteLock files.
* WTF.vcxproj/WTF.vcxproj:
* WTF.xcodeproj/project.pbxproj:
* benchmarks/LockSpeedTest.cpp:
(main):
* wtf/WordLock.cpp: Added.
(WTF::WordLock::lockSlow):
(WTF::WordLock::unlockSlow):
* wtf/WordLock.h: Added.
(WTF::WordLock::WordLock):
(WTF::WordLock::lock):
(WTF::WordLock::unlock):
(WTF::WordLock::isHeld):
(WTF::WordLock::isLocked):
* wtf/ByteLock.cpp: Removed.
* wtf/ByteLock.h: Removed.
* wtf/CMakeLists.txt:
* wtf/Lock.cpp:
(WTF::LockBase::lockSlow):
(WTF::LockBase::unlockSlow):
* wtf/Lock.h:
(WTF::LockBase::lock):
(WTF::LockBase::unlock):
(WTF::LockBase::isHeld):
(WTF::LockBase::isLocked):
(WTF::Lock::Lock):
* wtf/ParkingLot.cpp:
Tools:
All previous tests of Lock are now tests of WordLock. All previous tests of ByteLock are
now tests of Lock.
* TestWebKitAPI/Tests/WTF/Lock.cpp:
(TestWebKitAPI::runLockTest):
(TestWebKitAPI::TEST):
Canonical link: https://commits.webkit.org/166025@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@188323 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2015-08-12 04:20:24 +00:00
|
|
|
continue;
|
|
|
|
}
|
|
|
|
|
2018-04-29 17:29:13 +00:00
|
|
|
me.shouldPark = true;
|
Always use a byte-sized lock implementation
https://bugs.webkit.org/show_bug.cgi?id=147908
Reviewed by Geoffrey Garen.
Source/JavaScriptCore:
* runtime/ConcurrentJITLock.h: Lock is now byte-sized and ByteLock is gone, so use Lock.
Source/WTF:
At the start of my locking algorithm crusade, I implemented Lock, which is a sizeof(void*)
lock implementation with some nice theoretical properties and good performance. Then I added
the ParkingLot abstraction and ByteLock. ParkingLot uses Lock in its implementation.
ByteLock uses ParkingLot to create a sizeof(char) lock implementation that performs like
Lock.
It turns out that ByteLock is always at least as good as Lock, and sometimes a lot better:
it requires 8x less memory on 64-bit systems. It's hard to construct a benchmark where
ByteLock is significantly slower than Lock, and when you do construct such a benchmark,
tweaking it a bit can also create a scenario where ByteLock is significantly faster than
Lock.
So, the thing that we call "Lock" should really use ByteLock's algorithm, since it is more
compact and just as fast. That's what this patch does.
But we still need to keep the old Lock algorithm, because it's used to implement ParkingLot,
which in turn is used to implement ByteLock. So this patch does this transformation:
- Move the algorithm in Lock into files called WordLock.h|cpp. Make ParkingLot use
WordLock.
- Move the algorithm in ByteLock into Lock.h|cpp. Make everyone who used ByteLock use Lock
instead. All other users of Lock now get the byte-sized lock implementation.
- Remove the old ByteLock files.
* WTF.vcxproj/WTF.vcxproj:
* WTF.xcodeproj/project.pbxproj:
* benchmarks/LockSpeedTest.cpp:
(main):
* wtf/WordLock.cpp: Added.
(WTF::WordLock::lockSlow):
(WTF::WordLock::unlockSlow):
* wtf/WordLock.h: Added.
(WTF::WordLock::WordLock):
(WTF::WordLock::lock):
(WTF::WordLock::unlock):
(WTF::WordLock::isHeld):
(WTF::WordLock::isLocked):
* wtf/ByteLock.cpp: Removed.
* wtf/ByteLock.h: Removed.
* wtf/CMakeLists.txt:
* wtf/Lock.cpp:
(WTF::LockBase::lockSlow):
(WTF::LockBase::unlockSlow):
* wtf/Lock.h:
(WTF::LockBase::lock):
(WTF::LockBase::unlock):
(WTF::LockBase::isHeld):
(WTF::LockBase::isLocked):
(WTF::Lock::Lock):
* wtf/ParkingLot.cpp:
Tools:
All previous tests of Lock are now tests of WordLock. All previous tests of ByteLock are
now tests of Lock.
* TestWebKitAPI/Tests/WTF/Lock.cpp:
(TestWebKitAPI::runLockTest):
(TestWebKitAPI::TEST):
Canonical link: https://commits.webkit.org/166025@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@188323 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2015-08-12 04:20:24 +00:00
|
|
|
|
|
|
|
// 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.
|
2018-04-29 17:29:13 +00:00
|
|
|
queueHead->queueTail->nextInQueue = &me;
|
|
|
|
queueHead->queueTail = &me;
|
Always use a byte-sized lock implementation
https://bugs.webkit.org/show_bug.cgi?id=147908
Reviewed by Geoffrey Garen.
Source/JavaScriptCore:
* runtime/ConcurrentJITLock.h: Lock is now byte-sized and ByteLock is gone, so use Lock.
Source/WTF:
At the start of my locking algorithm crusade, I implemented Lock, which is a sizeof(void*)
lock implementation with some nice theoretical properties and good performance. Then I added
the ParkingLot abstraction and ByteLock. ParkingLot uses Lock in its implementation.
ByteLock uses ParkingLot to create a sizeof(char) lock implementation that performs like
Lock.
It turns out that ByteLock is always at least as good as Lock, and sometimes a lot better:
it requires 8x less memory on 64-bit systems. It's hard to construct a benchmark where
ByteLock is significantly slower than Lock, and when you do construct such a benchmark,
tweaking it a bit can also create a scenario where ByteLock is significantly faster than
Lock.
So, the thing that we call "Lock" should really use ByteLock's algorithm, since it is more
compact and just as fast. That's what this patch does.
But we still need to keep the old Lock algorithm, because it's used to implement ParkingLot,
which in turn is used to implement ByteLock. So this patch does this transformation:
- Move the algorithm in Lock into files called WordLock.h|cpp. Make ParkingLot use
WordLock.
- Move the algorithm in ByteLock into Lock.h|cpp. Make everyone who used ByteLock use Lock
instead. All other users of Lock now get the byte-sized lock implementation.
- Remove the old ByteLock files.
* WTF.vcxproj/WTF.vcxproj:
* WTF.xcodeproj/project.pbxproj:
* benchmarks/LockSpeedTest.cpp:
(main):
* wtf/WordLock.cpp: Added.
(WTF::WordLock::lockSlow):
(WTF::WordLock::unlockSlow):
* wtf/WordLock.h: Added.
(WTF::WordLock::WordLock):
(WTF::WordLock::lock):
(WTF::WordLock::unlock):
(WTF::WordLock::isHeld):
(WTF::WordLock::isLocked):
* wtf/ByteLock.cpp: Removed.
* wtf/ByteLock.h: Removed.
* wtf/CMakeLists.txt:
* wtf/Lock.cpp:
(WTF::LockBase::lockSlow):
(WTF::LockBase::unlockSlow):
* wtf/Lock.h:
(WTF::LockBase::lock):
(WTF::LockBase::unlock):
(WTF::LockBase::isHeld):
(WTF::LockBase::isLocked):
(WTF::Lock::Lock):
* wtf/ParkingLot.cpp:
Tools:
All previous tests of Lock are now tests of WordLock. All previous tests of ByteLock are
now tests of Lock.
* TestWebKitAPI/Tests/WTF/Lock.cpp:
(TestWebKitAPI::runLockTest):
(TestWebKitAPI::TEST):
Canonical link: https://commits.webkit.org/166025@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@188323 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2015-08-12 04:20:24 +00:00
|
|
|
|
|
|
|
// 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.
|
2018-04-29 17:29:13 +00:00
|
|
|
queueHead = &me;
|
|
|
|
me.queueTail = &me;
|
Always use a byte-sized lock implementation
https://bugs.webkit.org/show_bug.cgi?id=147908
Reviewed by Geoffrey Garen.
Source/JavaScriptCore:
* runtime/ConcurrentJITLock.h: Lock is now byte-sized and ByteLock is gone, so use Lock.
Source/WTF:
At the start of my locking algorithm crusade, I implemented Lock, which is a sizeof(void*)
lock implementation with some nice theoretical properties and good performance. Then I added
the ParkingLot abstraction and ByteLock. ParkingLot uses Lock in its implementation.
ByteLock uses ParkingLot to create a sizeof(char) lock implementation that performs like
Lock.
It turns out that ByteLock is always at least as good as Lock, and sometimes a lot better:
it requires 8x less memory on 64-bit systems. It's hard to construct a benchmark where
ByteLock is significantly slower than Lock, and when you do construct such a benchmark,
tweaking it a bit can also create a scenario where ByteLock is significantly faster than
Lock.
So, the thing that we call "Lock" should really use ByteLock's algorithm, since it is more
compact and just as fast. That's what this patch does.
But we still need to keep the old Lock algorithm, because it's used to implement ParkingLot,
which in turn is used to implement ByteLock. So this patch does this transformation:
- Move the algorithm in Lock into files called WordLock.h|cpp. Make ParkingLot use
WordLock.
- Move the algorithm in ByteLock into Lock.h|cpp. Make everyone who used ByteLock use Lock
instead. All other users of Lock now get the byte-sized lock implementation.
- Remove the old ByteLock files.
* WTF.vcxproj/WTF.vcxproj:
* WTF.xcodeproj/project.pbxproj:
* benchmarks/LockSpeedTest.cpp:
(main):
* wtf/WordLock.cpp: Added.
(WTF::WordLock::lockSlow):
(WTF::WordLock::unlockSlow):
* wtf/WordLock.h: Added.
(WTF::WordLock::WordLock):
(WTF::WordLock::lock):
(WTF::WordLock::unlock):
(WTF::WordLock::isHeld):
(WTF::WordLock::isLocked):
* wtf/ByteLock.cpp: Removed.
* wtf/ByteLock.h: Removed.
* wtf/CMakeLists.txt:
* wtf/Lock.cpp:
(WTF::LockBase::lockSlow):
(WTF::LockBase::unlockSlow):
* wtf/Lock.h:
(WTF::LockBase::lock):
(WTF::LockBase::unlock):
(WTF::LockBase::isHeld):
(WTF::LockBase::isLocked):
(WTF::Lock::Lock):
* wtf/ParkingLot.cpp:
Tools:
All previous tests of Lock are now tests of WordLock. All previous tests of ByteLock are
now tests of Lock.
* TestWebKitAPI/Tests/WTF/Lock.cpp:
(TestWebKitAPI::runLockTest):
(TestWebKitAPI::TEST):
Canonical link: https://commits.webkit.org/166025@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@188323 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2015-08-12 04:20:24 +00:00
|
|
|
|
|
|
|
// 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.
|
|
|
|
|
|
|
|
{
|
2018-04-29 17:29:13 +00:00
|
|
|
std::unique_lock<std::mutex> locker(me.parkingLock);
|
|
|
|
while (me.shouldPark)
|
|
|
|
me.parkingCondition.wait(locker);
|
Always use a byte-sized lock implementation
https://bugs.webkit.org/show_bug.cgi?id=147908
Reviewed by Geoffrey Garen.
Source/JavaScriptCore:
* runtime/ConcurrentJITLock.h: Lock is now byte-sized and ByteLock is gone, so use Lock.
Source/WTF:
At the start of my locking algorithm crusade, I implemented Lock, which is a sizeof(void*)
lock implementation with some nice theoretical properties and good performance. Then I added
the ParkingLot abstraction and ByteLock. ParkingLot uses Lock in its implementation.
ByteLock uses ParkingLot to create a sizeof(char) lock implementation that performs like
Lock.
It turns out that ByteLock is always at least as good as Lock, and sometimes a lot better:
it requires 8x less memory on 64-bit systems. It's hard to construct a benchmark where
ByteLock is significantly slower than Lock, and when you do construct such a benchmark,
tweaking it a bit can also create a scenario where ByteLock is significantly faster than
Lock.
So, the thing that we call "Lock" should really use ByteLock's algorithm, since it is more
compact and just as fast. That's what this patch does.
But we still need to keep the old Lock algorithm, because it's used to implement ParkingLot,
which in turn is used to implement ByteLock. So this patch does this transformation:
- Move the algorithm in Lock into files called WordLock.h|cpp. Make ParkingLot use
WordLock.
- Move the algorithm in ByteLock into Lock.h|cpp. Make everyone who used ByteLock use Lock
instead. All other users of Lock now get the byte-sized lock implementation.
- Remove the old ByteLock files.
* WTF.vcxproj/WTF.vcxproj:
* WTF.xcodeproj/project.pbxproj:
* benchmarks/LockSpeedTest.cpp:
(main):
* wtf/WordLock.cpp: Added.
(WTF::WordLock::lockSlow):
(WTF::WordLock::unlockSlow):
* wtf/WordLock.h: Added.
(WTF::WordLock::WordLock):
(WTF::WordLock::lock):
(WTF::WordLock::unlock):
(WTF::WordLock::isHeld):
(WTF::WordLock::isLocked):
* wtf/ByteLock.cpp: Removed.
* wtf/ByteLock.h: Removed.
* wtf/CMakeLists.txt:
* wtf/Lock.cpp:
(WTF::LockBase::lockSlow):
(WTF::LockBase::unlockSlow):
* wtf/Lock.h:
(WTF::LockBase::lock):
(WTF::LockBase::unlock):
(WTF::LockBase::isHeld):
(WTF::LockBase::isLocked):
(WTF::Lock::Lock):
* wtf/ParkingLot.cpp:
Tools:
All previous tests of Lock are now tests of WordLock. All previous tests of ByteLock are
now tests of Lock.
* TestWebKitAPI/Tests/WTF/Lock.cpp:
(TestWebKitAPI::runLockTest):
(TestWebKitAPI::TEST):
Canonical link: https://commits.webkit.org/166025@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@188323 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2015-08-12 04:20:24 +00:00
|
|
|
}
|
|
|
|
|
2018-04-29 17:29:13 +00:00
|
|
|
ASSERT(!me.shouldPark);
|
|
|
|
ASSERT(!me.nextInQueue);
|
|
|
|
ASSERT(!me.queueTail);
|
Always use a byte-sized lock implementation
https://bugs.webkit.org/show_bug.cgi?id=147908
Reviewed by Geoffrey Garen.
Source/JavaScriptCore:
* runtime/ConcurrentJITLock.h: Lock is now byte-sized and ByteLock is gone, so use Lock.
Source/WTF:
At the start of my locking algorithm crusade, I implemented Lock, which is a sizeof(void*)
lock implementation with some nice theoretical properties and good performance. Then I added
the ParkingLot abstraction and ByteLock. ParkingLot uses Lock in its implementation.
ByteLock uses ParkingLot to create a sizeof(char) lock implementation that performs like
Lock.
It turns out that ByteLock is always at least as good as Lock, and sometimes a lot better:
it requires 8x less memory on 64-bit systems. It's hard to construct a benchmark where
ByteLock is significantly slower than Lock, and when you do construct such a benchmark,
tweaking it a bit can also create a scenario where ByteLock is significantly faster than
Lock.
So, the thing that we call "Lock" should really use ByteLock's algorithm, since it is more
compact and just as fast. That's what this patch does.
But we still need to keep the old Lock algorithm, because it's used to implement ParkingLot,
which in turn is used to implement ByteLock. So this patch does this transformation:
- Move the algorithm in Lock into files called WordLock.h|cpp. Make ParkingLot use
WordLock.
- Move the algorithm in ByteLock into Lock.h|cpp. Make everyone who used ByteLock use Lock
instead. All other users of Lock now get the byte-sized lock implementation.
- Remove the old ByteLock files.
* WTF.vcxproj/WTF.vcxproj:
* WTF.xcodeproj/project.pbxproj:
* benchmarks/LockSpeedTest.cpp:
(main):
* wtf/WordLock.cpp: Added.
(WTF::WordLock::lockSlow):
(WTF::WordLock::unlockSlow):
* wtf/WordLock.h: Added.
(WTF::WordLock::WordLock):
(WTF::WordLock::lock):
(WTF::WordLock::unlock):
(WTF::WordLock::isHeld):
(WTF::WordLock::isLocked):
* wtf/ByteLock.cpp: Removed.
* wtf/ByteLock.h: Removed.
* wtf/CMakeLists.txt:
* wtf/Lock.cpp:
(WTF::LockBase::lockSlow):
(WTF::LockBase::unlockSlow):
* wtf/Lock.h:
(WTF::LockBase::lock):
(WTF::LockBase::unlock):
(WTF::LockBase::isHeld):
(WTF::LockBase::isLocked):
(WTF::Lock::Lock):
* wtf/ParkingLot.cpp:
Tools:
All previous tests of Lock are now tests of WordLock. All previous tests of ByteLock are
now tests of Lock.
* TestWebKitAPI/Tests/WTF/Lock.cpp:
(TestWebKitAPI::runLockTest):
(TestWebKitAPI::TEST):
Canonical link: https://commits.webkit.org/166025@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@188323 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2015-08-12 04:20:24 +00:00
|
|
|
|
|
|
|
// Now we can loop around and try to acquire the lock again.
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
2017-12-07 03:52:09 +00:00
|
|
|
NEVER_INLINE void WordLock::unlockSlow()
|
Always use a byte-sized lock implementation
https://bugs.webkit.org/show_bug.cgi?id=147908
Reviewed by Geoffrey Garen.
Source/JavaScriptCore:
* runtime/ConcurrentJITLock.h: Lock is now byte-sized and ByteLock is gone, so use Lock.
Source/WTF:
At the start of my locking algorithm crusade, I implemented Lock, which is a sizeof(void*)
lock implementation with some nice theoretical properties and good performance. Then I added
the ParkingLot abstraction and ByteLock. ParkingLot uses Lock in its implementation.
ByteLock uses ParkingLot to create a sizeof(char) lock implementation that performs like
Lock.
It turns out that ByteLock is always at least as good as Lock, and sometimes a lot better:
it requires 8x less memory on 64-bit systems. It's hard to construct a benchmark where
ByteLock is significantly slower than Lock, and when you do construct such a benchmark,
tweaking it a bit can also create a scenario where ByteLock is significantly faster than
Lock.
So, the thing that we call "Lock" should really use ByteLock's algorithm, since it is more
compact and just as fast. That's what this patch does.
But we still need to keep the old Lock algorithm, because it's used to implement ParkingLot,
which in turn is used to implement ByteLock. So this patch does this transformation:
- Move the algorithm in Lock into files called WordLock.h|cpp. Make ParkingLot use
WordLock.
- Move the algorithm in ByteLock into Lock.h|cpp. Make everyone who used ByteLock use Lock
instead. All other users of Lock now get the byte-sized lock implementation.
- Remove the old ByteLock files.
* WTF.vcxproj/WTF.vcxproj:
* WTF.xcodeproj/project.pbxproj:
* benchmarks/LockSpeedTest.cpp:
(main):
* wtf/WordLock.cpp: Added.
(WTF::WordLock::lockSlow):
(WTF::WordLock::unlockSlow):
* wtf/WordLock.h: Added.
(WTF::WordLock::WordLock):
(WTF::WordLock::lock):
(WTF::WordLock::unlock):
(WTF::WordLock::isHeld):
(WTF::WordLock::isLocked):
* wtf/ByteLock.cpp: Removed.
* wtf/ByteLock.h: Removed.
* wtf/CMakeLists.txt:
* wtf/Lock.cpp:
(WTF::LockBase::lockSlow):
(WTF::LockBase::unlockSlow):
* wtf/Lock.h:
(WTF::LockBase::lock):
(WTF::LockBase::unlock):
(WTF::LockBase::isHeld):
(WTF::LockBase::isLocked):
(WTF::Lock::Lock):
* wtf/ParkingLot.cpp:
Tools:
All previous tests of Lock are now tests of WordLock. All previous tests of ByteLock are
now tests of Lock.
* TestWebKitAPI/Tests/WTF/Lock.cpp:
(TestWebKitAPI::runLockTest):
(TestWebKitAPI::TEST):
Canonical link: https://commits.webkit.org/166025@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@188323 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2015-08-12 04:20:24 +00:00
|
|
|
{
|
|
|
|
// 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.
|
2017-07-22 14:36:18 +00:00
|
|
|
Thread::yield();
|
Always use a byte-sized lock implementation
https://bugs.webkit.org/show_bug.cgi?id=147908
Reviewed by Geoffrey Garen.
Source/JavaScriptCore:
* runtime/ConcurrentJITLock.h: Lock is now byte-sized and ByteLock is gone, so use Lock.
Source/WTF:
At the start of my locking algorithm crusade, I implemented Lock, which is a sizeof(void*)
lock implementation with some nice theoretical properties and good performance. Then I added
the ParkingLot abstraction and ByteLock. ParkingLot uses Lock in its implementation.
ByteLock uses ParkingLot to create a sizeof(char) lock implementation that performs like
Lock.
It turns out that ByteLock is always at least as good as Lock, and sometimes a lot better:
it requires 8x less memory on 64-bit systems. It's hard to construct a benchmark where
ByteLock is significantly slower than Lock, and when you do construct such a benchmark,
tweaking it a bit can also create a scenario where ByteLock is significantly faster than
Lock.
So, the thing that we call "Lock" should really use ByteLock's algorithm, since it is more
compact and just as fast. That's what this patch does.
But we still need to keep the old Lock algorithm, because it's used to implement ParkingLot,
which in turn is used to implement ByteLock. So this patch does this transformation:
- Move the algorithm in Lock into files called WordLock.h|cpp. Make ParkingLot use
WordLock.
- Move the algorithm in ByteLock into Lock.h|cpp. Make everyone who used ByteLock use Lock
instead. All other users of Lock now get the byte-sized lock implementation.
- Remove the old ByteLock files.
* WTF.vcxproj/WTF.vcxproj:
* WTF.xcodeproj/project.pbxproj:
* benchmarks/LockSpeedTest.cpp:
(main):
* wtf/WordLock.cpp: Added.
(WTF::WordLock::lockSlow):
(WTF::WordLock::unlockSlow):
* wtf/WordLock.h: Added.
(WTF::WordLock::WordLock):
(WTF::WordLock::lock):
(WTF::WordLock::unlock):
(WTF::WordLock::isHeld):
(WTF::WordLock::isLocked):
* wtf/ByteLock.cpp: Removed.
* wtf/ByteLock.h: Removed.
* wtf/CMakeLists.txt:
* wtf/Lock.cpp:
(WTF::LockBase::lockSlow):
(WTF::LockBase::unlockSlow):
* wtf/Lock.h:
(WTF::LockBase::lock):
(WTF::LockBase::unlock):
(WTF::LockBase::isHeld):
(WTF::LockBase::isLocked):
(WTF::Lock::Lock):
* wtf/ParkingLot.cpp:
Tools:
All previous tests of Lock are now tests of WordLock. All previous tests of ByteLock are
now tests of Lock.
* TestWebKitAPI/Tests/WTF/Lock.cpp:
(TestWebKitAPI::runLockTest):
(TestWebKitAPI::TEST):
Canonical link: https://commits.webkit.org/166025@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@188323 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2015-08-12 04:20:24 +00:00
|
|
|
continue;
|
|
|
|
}
|
|
|
|
|
|
|
|
if (currentWordValue & isQueueLockedBit) {
|
2017-07-22 14:36:18 +00:00
|
|
|
Thread::yield();
|
Always use a byte-sized lock implementation
https://bugs.webkit.org/show_bug.cgi?id=147908
Reviewed by Geoffrey Garen.
Source/JavaScriptCore:
* runtime/ConcurrentJITLock.h: Lock is now byte-sized and ByteLock is gone, so use Lock.
Source/WTF:
At the start of my locking algorithm crusade, I implemented Lock, which is a sizeof(void*)
lock implementation with some nice theoretical properties and good performance. Then I added
the ParkingLot abstraction and ByteLock. ParkingLot uses Lock in its implementation.
ByteLock uses ParkingLot to create a sizeof(char) lock implementation that performs like
Lock.
It turns out that ByteLock is always at least as good as Lock, and sometimes a lot better:
it requires 8x less memory on 64-bit systems. It's hard to construct a benchmark where
ByteLock is significantly slower than Lock, and when you do construct such a benchmark,
tweaking it a bit can also create a scenario where ByteLock is significantly faster than
Lock.
So, the thing that we call "Lock" should really use ByteLock's algorithm, since it is more
compact and just as fast. That's what this patch does.
But we still need to keep the old Lock algorithm, because it's used to implement ParkingLot,
which in turn is used to implement ByteLock. So this patch does this transformation:
- Move the algorithm in Lock into files called WordLock.h|cpp. Make ParkingLot use
WordLock.
- Move the algorithm in ByteLock into Lock.h|cpp. Make everyone who used ByteLock use Lock
instead. All other users of Lock now get the byte-sized lock implementation.
- Remove the old ByteLock files.
* WTF.vcxproj/WTF.vcxproj:
* WTF.xcodeproj/project.pbxproj:
* benchmarks/LockSpeedTest.cpp:
(main):
* wtf/WordLock.cpp: Added.
(WTF::WordLock::lockSlow):
(WTF::WordLock::unlockSlow):
* wtf/WordLock.h: Added.
(WTF::WordLock::WordLock):
(WTF::WordLock::lock):
(WTF::WordLock::unlock):
(WTF::WordLock::isHeld):
(WTF::WordLock::isLocked):
* wtf/ByteLock.cpp: Removed.
* wtf/ByteLock.h: Removed.
* wtf/CMakeLists.txt:
* wtf/Lock.cpp:
(WTF::LockBase::lockSlow):
(WTF::LockBase::unlockSlow):
* wtf/Lock.h:
(WTF::LockBase::lock):
(WTF::LockBase::unlock):
(WTF::LockBase::isHeld):
(WTF::LockBase::isLocked):
(WTF::Lock::Lock):
* wtf/ParkingLot.cpp:
Tools:
All previous tests of Lock are now tests of WordLock. All previous tests of ByteLock are
now tests of Lock.
* TestWebKitAPI/Tests/WTF/Lock.cpp:
(TestWebKitAPI::runLockTest):
(TestWebKitAPI::TEST):
Canonical link: https://commits.webkit.org/166025@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@188323 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2015-08-12 04:20:24 +00:00
|
|
|
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);
|
2018-03-10 17:28:09 +00:00
|
|
|
ASSERT(queueHead);
|
Always use a byte-sized lock implementation
https://bugs.webkit.org/show_bug.cgi?id=147908
Reviewed by Geoffrey Garen.
Source/JavaScriptCore:
* runtime/ConcurrentJITLock.h: Lock is now byte-sized and ByteLock is gone, so use Lock.
Source/WTF:
At the start of my locking algorithm crusade, I implemented Lock, which is a sizeof(void*)
lock implementation with some nice theoretical properties and good performance. Then I added
the ParkingLot abstraction and ByteLock. ParkingLot uses Lock in its implementation.
ByteLock uses ParkingLot to create a sizeof(char) lock implementation that performs like
Lock.
It turns out that ByteLock is always at least as good as Lock, and sometimes a lot better:
it requires 8x less memory on 64-bit systems. It's hard to construct a benchmark where
ByteLock is significantly slower than Lock, and when you do construct such a benchmark,
tweaking it a bit can also create a scenario where ByteLock is significantly faster than
Lock.
So, the thing that we call "Lock" should really use ByteLock's algorithm, since it is more
compact and just as fast. That's what this patch does.
But we still need to keep the old Lock algorithm, because it's used to implement ParkingLot,
which in turn is used to implement ByteLock. So this patch does this transformation:
- Move the algorithm in Lock into files called WordLock.h|cpp. Make ParkingLot use
WordLock.
- Move the algorithm in ByteLock into Lock.h|cpp. Make everyone who used ByteLock use Lock
instead. All other users of Lock now get the byte-sized lock implementation.
- Remove the old ByteLock files.
* WTF.vcxproj/WTF.vcxproj:
* WTF.xcodeproj/project.pbxproj:
* benchmarks/LockSpeedTest.cpp:
(main):
* wtf/WordLock.cpp: Added.
(WTF::WordLock::lockSlow):
(WTF::WordLock::unlockSlow):
* wtf/WordLock.h: Added.
(WTF::WordLock::WordLock):
(WTF::WordLock::lock):
(WTF::WordLock::unlock):
(WTF::WordLock::isHeld):
(WTF::WordLock::isLocked):
* wtf/ByteLock.cpp: Removed.
* wtf/ByteLock.h: Removed.
* wtf/CMakeLists.txt:
* wtf/Lock.cpp:
(WTF::LockBase::lockSlow):
(WTF::LockBase::unlockSlow):
* wtf/Lock.h:
(WTF::LockBase::lock):
(WTF::LockBase::unlock):
(WTF::LockBase::isHeld):
(WTF::LockBase::isLocked):
(WTF::Lock::Lock):
* wtf/ParkingLot.cpp:
Tools:
All previous tests of Lock are now tests of WordLock. All previous tests of ByteLock are
now tests of Lock.
* TestWebKitAPI/Tests/WTF/Lock.cpp:
(TestWebKitAPI::runLockTest):
(TestWebKitAPI::TEST):
Canonical link: https://commits.webkit.org/166025@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@188323 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2015-08-12 04:20:24 +00:00
|
|
|
|
|
|
|
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().
|
|
|
|
{
|
2018-04-29 15:23:52 +00:00
|
|
|
// 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.
|
2020-03-01 05:01:30 +00:00
|
|
|
std::scoped_lock<std::mutex> locker(queueHead->parkingLock);
|
Always use a byte-sized lock implementation
https://bugs.webkit.org/show_bug.cgi?id=147908
Reviewed by Geoffrey Garen.
Source/JavaScriptCore:
* runtime/ConcurrentJITLock.h: Lock is now byte-sized and ByteLock is gone, so use Lock.
Source/WTF:
At the start of my locking algorithm crusade, I implemented Lock, which is a sizeof(void*)
lock implementation with some nice theoretical properties and good performance. Then I added
the ParkingLot abstraction and ByteLock. ParkingLot uses Lock in its implementation.
ByteLock uses ParkingLot to create a sizeof(char) lock implementation that performs like
Lock.
It turns out that ByteLock is always at least as good as Lock, and sometimes a lot better:
it requires 8x less memory on 64-bit systems. It's hard to construct a benchmark where
ByteLock is significantly slower than Lock, and when you do construct such a benchmark,
tweaking it a bit can also create a scenario where ByteLock is significantly faster than
Lock.
So, the thing that we call "Lock" should really use ByteLock's algorithm, since it is more
compact and just as fast. That's what this patch does.
But we still need to keep the old Lock algorithm, because it's used to implement ParkingLot,
which in turn is used to implement ByteLock. So this patch does this transformation:
- Move the algorithm in Lock into files called WordLock.h|cpp. Make ParkingLot use
WordLock.
- Move the algorithm in ByteLock into Lock.h|cpp. Make everyone who used ByteLock use Lock
instead. All other users of Lock now get the byte-sized lock implementation.
- Remove the old ByteLock files.
* WTF.vcxproj/WTF.vcxproj:
* WTF.xcodeproj/project.pbxproj:
* benchmarks/LockSpeedTest.cpp:
(main):
* wtf/WordLock.cpp: Added.
(WTF::WordLock::lockSlow):
(WTF::WordLock::unlockSlow):
* wtf/WordLock.h: Added.
(WTF::WordLock::WordLock):
(WTF::WordLock::lock):
(WTF::WordLock::unlock):
(WTF::WordLock::isHeld):
(WTF::WordLock::isLocked):
* wtf/ByteLock.cpp: Removed.
* wtf/ByteLock.h: Removed.
* wtf/CMakeLists.txt:
* wtf/Lock.cpp:
(WTF::LockBase::lockSlow):
(WTF::LockBase::unlockSlow):
* wtf/Lock.h:
(WTF::LockBase::lock):
(WTF::LockBase::unlock):
(WTF::LockBase::isHeld):
(WTF::LockBase::isLocked):
(WTF::Lock::Lock):
* wtf/ParkingLot.cpp:
Tools:
All previous tests of Lock are now tests of WordLock. All previous tests of ByteLock are
now tests of Lock.
* TestWebKitAPI/Tests/WTF/Lock.cpp:
(TestWebKitAPI::runLockTest):
(TestWebKitAPI::TEST):
Canonical link: https://commits.webkit.org/166025@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@188323 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2015-08-12 04:20:24 +00:00
|
|
|
queueHead->shouldPark = false;
|
2018-04-29 15:23:52 +00:00
|
|
|
|
|
|
|
// 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();
|
Always use a byte-sized lock implementation
https://bugs.webkit.org/show_bug.cgi?id=147908
Reviewed by Geoffrey Garen.
Source/JavaScriptCore:
* runtime/ConcurrentJITLock.h: Lock is now byte-sized and ByteLock is gone, so use Lock.
Source/WTF:
At the start of my locking algorithm crusade, I implemented Lock, which is a sizeof(void*)
lock implementation with some nice theoretical properties and good performance. Then I added
the ParkingLot abstraction and ByteLock. ParkingLot uses Lock in its implementation.
ByteLock uses ParkingLot to create a sizeof(char) lock implementation that performs like
Lock.
It turns out that ByteLock is always at least as good as Lock, and sometimes a lot better:
it requires 8x less memory on 64-bit systems. It's hard to construct a benchmark where
ByteLock is significantly slower than Lock, and when you do construct such a benchmark,
tweaking it a bit can also create a scenario where ByteLock is significantly faster than
Lock.
So, the thing that we call "Lock" should really use ByteLock's algorithm, since it is more
compact and just as fast. That's what this patch does.
But we still need to keep the old Lock algorithm, because it's used to implement ParkingLot,
which in turn is used to implement ByteLock. So this patch does this transformation:
- Move the algorithm in Lock into files called WordLock.h|cpp. Make ParkingLot use
WordLock.
- Move the algorithm in ByteLock into Lock.h|cpp. Make everyone who used ByteLock use Lock
instead. All other users of Lock now get the byte-sized lock implementation.
- Remove the old ByteLock files.
* WTF.vcxproj/WTF.vcxproj:
* WTF.xcodeproj/project.pbxproj:
* benchmarks/LockSpeedTest.cpp:
(main):
* wtf/WordLock.cpp: Added.
(WTF::WordLock::lockSlow):
(WTF::WordLock::unlockSlow):
* wtf/WordLock.h: Added.
(WTF::WordLock::WordLock):
(WTF::WordLock::lock):
(WTF::WordLock::unlock):
(WTF::WordLock::isHeld):
(WTF::WordLock::isLocked):
* wtf/ByteLock.cpp: Removed.
* wtf/ByteLock.h: Removed.
* wtf/CMakeLists.txt:
* wtf/Lock.cpp:
(WTF::LockBase::lockSlow):
(WTF::LockBase::unlockSlow):
* wtf/Lock.h:
(WTF::LockBase::lock):
(WTF::LockBase::unlock):
(WTF::LockBase::isHeld):
(WTF::LockBase::isLocked):
(WTF::Lock::Lock):
* wtf/ParkingLot.cpp:
Tools:
All previous tests of Lock are now tests of WordLock. All previous tests of ByteLock are
now tests of Lock.
* TestWebKitAPI/Tests/WTF/Lock.cpp:
(TestWebKitAPI::runLockTest):
(TestWebKitAPI::TEST):
Canonical link: https://commits.webkit.org/166025@main
git-svn-id: https://svn.webkit.org/repository/webkit/trunk@188323 268f45cc-cd09-0410-ab3c-d52691b4dbfc
2015-08-12 04:20:24 +00:00
|
|
|
}
|
|
|
|
|
|
|
|
// The old queue head can now contend for the lock again. We're done!
|
|
|
|
}
|
|
|
|
|
|
|
|
} // namespace WTF
|
|
|
|
|