Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (188279 => 188280)
--- trunk/Source/_javascript_Core/ChangeLog 2015-08-11 19:48:50 UTC (rev 188279)
+++ trunk/Source/_javascript_Core/ChangeLog 2015-08-11 19:51:35 UTC (rev 188280)
@@ -1,3 +1,14 @@
+2015-08-10 Filip Pizlo <[email protected]>
+
+ WTF should have a ParkingLot for parking sleeping threads, so that locks can fit in 1.6 bits
+ https://bugs.webkit.org/show_bug.cgi?id=147665
+
+ Reviewed by Mark Lam.
+
+ Replace ByteSpinLock with ByteLock.
+
+ * runtime/ConcurrentJITLock.h:
+
2015-08-11 Yusuke Suzuki <[email protected]>
Numeric setter on prototype doesn't get called.
Modified: trunk/Source/_javascript_Core/runtime/ConcurrentJITLock.h (188279 => 188280)
--- trunk/Source/_javascript_Core/runtime/ConcurrentJITLock.h 2015-08-11 19:48:50 UTC (rev 188279)
+++ trunk/Source/_javascript_Core/runtime/ConcurrentJITLock.h 2015-08-11 19:51:35 UTC (rev 188280)
@@ -27,14 +27,14 @@
#define ConcurrentJITLock_h
#include "DeferGC.h"
-#include <wtf/ByteSpinLock.h>
+#include <wtf/ByteLock.h>
#include <wtf/NoLock.h>
namespace JSC {
#if ENABLE(CONCURRENT_JIT)
-typedef ByteSpinLock ConcurrentJITLock;
-typedef ByteSpinLocker ConcurrentJITLockerImpl;
+typedef ByteLock ConcurrentJITLock;
+typedef ByteLocker ConcurrentJITLockerImpl;
#else
typedef NoLock ConcurrentJITLock;
typedef NoLockLocker ConcurrentJITLockerImpl;
Modified: trunk/Source/WTF/ChangeLog (188279 => 188280)
--- trunk/Source/WTF/ChangeLog 2015-08-11 19:48:50 UTC (rev 188279)
+++ trunk/Source/WTF/ChangeLog 2015-08-11 19:51:35 UTC (rev 188280)
@@ -1,3 +1,54 @@
+2015-08-10 Filip Pizlo <[email protected]>
+
+ WTF should have a ParkingLot for parking sleeping threads, so that locks can fit in 1.6 bits
+ https://bugs.webkit.org/show_bug.cgi?id=147665
+
+ Reviewed by Mark Lam.
+
+ This change adds a major new abstraction for concurrency algorithms in WebKit. It's called a
+ ParkingLot, and it makes available a thread parking queue for each virtual address in memory.
+ The queues are maintained by a data-access-parallel concurrent hashtable implementation. The
+ memory usage is bounded at around half a KB per thread.
+
+ The ParkingLot makes it easy to turn any spinlock-based concurrency protocol into one that
+ parks threads after a while. Because queue state management is up to the ParkingLot and not
+ the user's data structure, this patch uses it to implement a full adaptive mutex in one byte.
+ In fact, only three states of that byte are used (0 = available, 1 = locked, 2 = locked and
+ there are parked threads). Hence the joke that ParkingLot allows locks that fit in 1.6 bits.
+
+ ByteLock is used as a replacement for ByteSpinLock in _javascript_Core.
+
+ The API tests for this also demo how to create a completely fair (FIFO) binary semamphore. The
+ comment in Lock.h shows how we could accelerate Lock performance using ParkingLot. After we
+ are sure that this code works, we can expand the use of ParkingLot. That's covered by
+ https://bugs.webkit.org/show_bug.cgi?id=147841.
+
+ * WTF.vcxproj/WTF.vcxproj:
+ * WTF.xcodeproj/project.pbxproj:
+ * benchmarks/LockSpeedTest.cpp:
+ (main):
+ * wtf/Atomics.h:
+ (WTF::Atomic::compareExchangeWeak):
+ (WTF::Atomic::compareExchangeStrong):
+ * wtf/ByteLock.cpp: Added.
+ (WTF::ByteLock::lockSlow):
+ (WTF::ByteLock::unlockSlow):
+ * wtf/ByteLock.h: Added.
+ (WTF::ByteLock::ByteLock):
+ (WTF::ByteLock::lock):
+ (WTF::ByteLock::unlock):
+ (WTF::ByteLock::isHeld):
+ (WTF::ByteLock::isLocked):
+ * wtf/CMakeLists.txt:
+ * wtf/Lock.h:
+ * wtf/ParkingLot.cpp: Added.
+ (WTF::ParkingLot::parkConditionally):
+ (WTF::ParkingLot::unparkOne):
+ (WTF::ParkingLot::unparkAll):
+ (WTF::ParkingLot::forEach):
+ * wtf/ParkingLot.h: Added.
+ (WTF::ParkingLot::compareAndPark):
+
2015-08-11 Brent Fulgham <[email protected]>
[Win] Unreviewed gardening.
Modified: trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj (188279 => 188280)
--- trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj 2015-08-11 19:48:50 UTC (rev 188279)
+++ trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj 2015-08-11 19:51:35 UTC (rev 188280)
@@ -53,6 +53,7 @@
<ItemGroup>
<ClCompile Include="..\wtf\Assertions.cpp" />
<ClCompile Include="..\wtf\BitVector.cpp" />
+ <ClCompile Include="..\wtf\ByteLock.cpp" />
<ClCompile Include="..\wtf\CompilationThread.cpp" />
<ClCompile Include="..\wtf\CryptographicUtilities.cpp" />
<ClCompile Include="..\wtf\CryptographicallyRandomNumber.cpp" />
@@ -116,6 +117,7 @@
<ClCompile Include="..\wtf\OSRandomSource.cpp" />
<ClCompile Include="..\wtf\PageBlock.cpp" />
<ClCompile Include="..\wtf\ParallelJobsGeneric.cpp" />
+ <ClCompile Include="..\wtf\ParkingLot.cpp" />
<ClCompile Include="..\wtf\PrintStream.cpp" />
<ClCompile Include="..\wtf\RAMSize.cpp" />
<ClCompile Include="..\wtf\RandomNumber.cpp" />
@@ -171,6 +173,7 @@
<ClInclude Include="..\wtf\BlockStack.h" />
<ClInclude Include="..\wtf\BloomFilter.h" />
<ClInclude Include="..\wtf\BumpPointerAllocator.h" />
+ <ClInclude Include="..\wtf\ByteLock.h" />
<ClInclude Include="..\wtf\CheckedArithmetic.h" />
<ClInclude Include="..\wtf\CheckedBoolean.h" />
<ClInclude Include="..\wtf\Compiler.h" />
@@ -246,6 +249,7 @@
<ClInclude Include="..\wtf\ParallelJobsGeneric.h" />
<ClInclude Include="..\wtf\ParallelJobsLibdispatch.h" />
<ClInclude Include="..\wtf\ParallelJobsOpenMP.h" />
+ <ClInclude Include="..\wtf\ParkingLot.h" />
<ClInclude Include="..\wtf\PassRefPtr.h" />
<ClInclude Include="..\wtf\Platform.h" />
<ClInclude Include="..\wtf\PrintStream.h" />
Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (188279 => 188280)
--- trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2015-08-11 19:48:50 UTC (rev 188279)
+++ trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2015-08-11 19:51:35 UTC (rev 188280)
@@ -24,6 +24,10 @@
0F0D85B417234CC100338210 /* NoLock.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F0D85B317234CB100338210 /* NoLock.h */; };
0F2B66A617B6B4FB00A7AE3F /* DeferrableRefCounted.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F2B66A417B6B4F700A7AE3F /* DeferrableRefCounted.h */; };
0F2B66A717B6B4FD00A7AE3F /* FlipBytes.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F2B66A517B6B4F700A7AE3F /* FlipBytes.h */; };
+ 0F824A661B7443A0002E345D /* ByteLock.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F824A621B7443A0002E345D /* ByteLock.cpp */; };
+ 0F824A671B7443A0002E345D /* ByteLock.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F824A631B7443A0002E345D /* ByteLock.h */; };
+ 0F824A681B7443A0002E345D /* ParkingLot.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F824A641B7443A0002E345D /* ParkingLot.cpp */; };
+ 0F824A691B7443A0002E345D /* ParkingLot.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F824A651B7443A0002E345D /* ParkingLot.h */; };
0F87105A16643F190090B0AD /* RawPointer.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F87105916643F190090B0AD /* RawPointer.h */; };
0F885E0F1845AEA900F1E3FA /* FastBitVector.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F885E0E1845AE9F00F1E3FA /* FastBitVector.cpp */; };
0F8F2B91172E00FC007DBDA5 /* CompilationThread.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F8F2B90172E00F0007DBDA5 /* CompilationThread.h */; };
@@ -307,6 +311,10 @@
0F2B66A417B6B4F700A7AE3F /* DeferrableRefCounted.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = DeferrableRefCounted.h; sourceTree = "<group>"; };
0F2B66A517B6B4F700A7AE3F /* FlipBytes.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = FlipBytes.h; sourceTree = "<group>"; };
0F300B7D18AB48B400A6D72E /* HashMethod.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = HashMethod.h; sourceTree = "<group>"; };
+ 0F824A621B7443A0002E345D /* ByteLock.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ByteLock.cpp; sourceTree = "<group>"; };
+ 0F824A631B7443A0002E345D /* ByteLock.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ByteLock.h; sourceTree = "<group>"; };
+ 0F824A641B7443A0002E345D /* ParkingLot.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ParkingLot.cpp; sourceTree = "<group>"; };
+ 0F824A651B7443A0002E345D /* ParkingLot.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ParkingLot.h; sourceTree = "<group>"; };
0F87105916643F190090B0AD /* RawPointer.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RawPointer.h; sourceTree = "<group>"; };
0F885E0E1845AE9F00F1E3FA /* FastBitVector.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; path = FastBitVector.cpp; sourceTree = "<group>"; };
0F8F2B8F172E00F0007DBDA5 /* CompilationThread.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; path = CompilationThread.cpp; sourceTree = "<group>"; };
@@ -716,6 +724,8 @@
A8A47264151A825A004123FF /* BlockStack.h */,
A8A47265151A825A004123FF /* BloomFilter.h */,
A8A47267151A825A004123FF /* BumpPointerAllocator.h */,
+ 0F824A621B7443A0002E345D /* ByteLock.cpp */,
+ 0F824A631B7443A0002E345D /* ByteLock.h */,
EB95E1EF161A72410089A2F5 /* ByteOrder.h */,
0FEC3EE4171B834700FDAC8D /* ByteSpinLock.h */,
A8A4726A151A825A004123FF /* CheckedArithmetic.h */,
@@ -810,6 +820,8 @@
A8A472E5151A825B004123FF /* PageReservation.h */,
A8A472E6151A825B004123FF /* ParallelJobs.h */,
A8A472E9151A825B004123FF /* ParallelJobsLibdispatch.h */,
+ 0F824A641B7443A0002E345D /* ParkingLot.cpp */,
+ 0F824A651B7443A0002E345D /* ParkingLot.h */,
A8A472ED151A825B004123FF /* PassRefPtr.h */,
A876DBD7151816E500DADB95 /* Platform.h */,
0F9D335D165DBA73005AD387 /* PrintStream.cpp */,
@@ -1156,6 +1168,7 @@
A8A47415151A825B004123FF /* RandomNumber.h in Headers */,
A8A47416151A825B004123FF /* RandomNumberSeed.h in Headers */,
0F87105A16643F190090B0AD /* RawPointer.h in Headers */,
+ 0F824A671B7443A0002E345D /* ByteLock.h in Headers */,
A8A47417151A825B004123FF /* RedBlackTree.h in Headers */,
A8A47418151A825B004123FF /* RefCounted.h in Headers */,
A8A47419151A825B004123FF /* RefCountedArray.h in Headers */,
@@ -1167,6 +1180,7 @@
1469419216EAAF6D0024E146 /* RunLoopTimer.h in Headers */,
14F3B0F715E45E4600210069 /* SaturatedArithmetic.h in Headers */,
1469419616EAAFF80024E146 /* SchedulePair.h in Headers */,
+ 0F824A691B7443A0002E345D /* ParkingLot.h in Headers */,
A8A4741F151A825B004123FF /* SegmentedVector.h in Headers */,
A8A47420151A825B004123FF /* SentinelLinkedList.h in Headers */,
A8A47422151A825B004123FF /* SHA1.h in Headers */,
@@ -1325,6 +1339,7 @@
files = (
A8A47386151A825B004123FF /* Assertions.cpp in Sources */,
A8A47435151A825B004123FF /* AtomicString.cpp in Sources */,
+ 0F824A661B7443A0002E345D /* ByteLock.cpp in Sources */,
9BC70F05176C379D00101DEC /* AtomicStringTable.cpp in Sources */,
A5BA15FB182435A600A82E69 /* StringCF.cpp in Sources */,
1469419D16EAB10A0024E146 /* AutodrainedPoolMac.mm in Sources */,
@@ -1340,6 +1355,7 @@
A8A4739A151A825B004123FF /* CryptographicallyRandomNumber.cpp in Sources */,
A8A47439151A825B004123FF /* CString.cpp in Sources */,
A8A4739C151A825B004123FF /* CurrentTime.cpp in Sources */,
+ 0F824A681B7443A0002E345D /* ParkingLot.cpp in Sources */,
86F46F601A2840EE00CCBF22 /* RefCounter.cpp in Sources */,
A8A4739E151A825B004123FF /* DataLog.cpp in Sources */,
A8A473A0151A825B004123FF /* DateMath.cpp in Sources */,
Modified: trunk/Source/WTF/benchmarks/LockSpeedTest.cpp (188279 => 188280)
--- trunk/Source/WTF/benchmarks/LockSpeedTest.cpp 2015-08-11 19:48:50 UTC (rev 188279)
+++ trunk/Source/WTF/benchmarks/LockSpeedTest.cpp 2015-08-11 19:51:35 UTC (rev 188280)
@@ -26,6 +26,7 @@
#include "config.h"
#include <unistd.h>
+#include <wtf/ByteLock.h>
#include <wtf/CurrentTime.h>
#include <wtf/Lock.h>
#include <wtf/SpinLock.h>
@@ -43,7 +44,7 @@
NO_RETURN void usage()
{
- printf("Usage: LockSpeedTest spinlock|lock|mutex|all <num thread groups> <num threads per group> <work per critical section> <num noise threads> <num iterations>\n");
+ printf("Usage: LockSpeedTest spinlock|lock|bytelock|mutex|all <num thread groups> <num threads per group> <work per critical section> <num noise threads> <num iterations>\n");
exit(1);
}
@@ -125,6 +126,10 @@
runBenchmark<Lock>("WTF Lock");
didRun = true;
}
+ if (!strcmp(argv[1], "bytelock") || !strcmp(argv[1], "all")) {
+ runBenchmark<ByteLock>("WTF ByteLock");
+ didRun = true;
+ }
if (!strcmp(argv[1], "mutex") || !strcmp(argv[1], "all")) {
runBenchmark<Mutex>("Platform Mutex");
didRun = true;
Added: trunk/Source/WTF/wtf/ByteLock.cpp (0 => 188280)
--- trunk/Source/WTF/wtf/ByteLock.cpp (rev 0)
+++ trunk/Source/WTF/wtf/ByteLock.cpp 2015-08-11 19:51:35 UTC (rev 188280)
@@ -0,0 +1,105 @@
+/*
+ * Copyright (C) 2015 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 "ByteLock.h"
+
+#include "DataLog.h"
+#include "ParkingLot.h"
+#include "StringPrintStream.h"
+#include <thread>
+
+namespace WTF {
+
+static const bool verbose = false;
+
+void ByteLock::lockSlow()
+{
+ unsigned spinCount = 0;
+
+ // This magic number turns out to be optimal based on past JikesRVM experiments.
+ const unsigned spinLimit = 40;
+
+ for (;;) {
+ uint8_t currentByteValue = m_byte.load();
+ if (verbose)
+ dataLog(toString(currentThread(), ": locking with ", currentByteValue, "\n"));
+
+ // We allow ourselves to barge in.
+ if (!(currentByteValue & isHeldBit)
+ && m_byte.compareExchangeWeak(currentByteValue, currentByteValue | isHeldBit))
+ return;
+
+ // If there is nobody parked and we haven't spun too much, we can just try to spin around.
+ if (!(currentByteValue & hasParkedBit) && spinCount < spinLimit) {
+ spinCount++;
+ std::this_thread::yield();
+ continue;
+ }
+
+ // Need to park. We do this by setting the parked bit first, and then parking. We spin around
+ // if the parked bit wasn't set and we failed at setting it.
+ if (!(currentByteValue & hasParkedBit)
+ && !m_byte.compareExchangeWeak(currentByteValue, currentByteValue | hasParkedBit))
+ continue;
+
+ // We now expect the value to be isHeld|hasParked. So long as that's the case, we can park.
+ ParkingLot::compareAndPark(&m_byte, isHeldBit | hasParkedBit);
+
+ // We have awaken, or we never parked because the byte value changed. Either way, we loop
+ // around and try again.
+ }
+}
+
+void ByteLock::unlockSlow()
+{
+ // Release the lock while finding out if someone is parked. Note that as soon as we do this,
+ // someone might barge in.
+ uint8_t oldByteValue;
+ for (;;) {
+ oldByteValue = m_byte.load();
+ if (verbose)
+ dataLog(toString(currentThread(), ": unlocking with ", oldByteValue, "\n"));
+ ASSERT(oldByteValue & isHeldBit);
+ if (m_byte.compareExchangeWeak(oldByteValue, 0))
+ break;
+ }
+
+ // Note that someone could try to park right now. If that happens, they will return immediately
+ // because our parking predicate is that m_byte == isHeldBit | hasParkedBit, but we've already set
+ // m_byte = 0.
+
+ // If there had been threads parked, unpark all of them. This causes a thundering herd, but while
+ // that is theoretically scary, it's totally fine in WebKit because we usually don't have enough
+ // threads for this to matter.
+ // FIXME: We don't really need this to exhibit thundering herd. We could use unparkOne(), and if
+ // that returns true, just set the parked bit again. If in the process of setting the parked bit
+ // we fail the CAS, then just unpark again.
+ if (oldByteValue & hasParkedBit)
+ ParkingLot::unparkAll(&m_byte);
+}
+
+} // namespace WTF
+
Added: trunk/Source/WTF/wtf/ByteLock.h (0 => 188280)
--- trunk/Source/WTF/wtf/ByteLock.h (rev 0)
+++ trunk/Source/WTF/wtf/ByteLock.h 2015-08-11 19:51:35 UTC (rev 188280)
@@ -0,0 +1,108 @@
+/*
+ * Copyright (C) 2015 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 ByteLock_h
+#define ByteLock_h
+
+#include <wtf/Atomics.h>
+#include <wtf/Locker.h>
+#include <wtf/Noncopyable.h>
+
+namespace WTF {
+
+// This is like Lock, but only requires 1 byte instead of sizeof(void*) storage. The downside is that
+// it is slower on the slow path under heavy contention involving many threads because it is
+// susceptible to the "thundering herd" problem: it doesn't have enough state to track how many
+// threads are waiting for the lock, so when unlock detects that any thread is waiting, then it wakes
+// all of the waiting threads. All of those threads will pile onto the lock; one will succeed and take
+// it while the others will go back to sleep. The slow-down is small. Ten threads repeatedly
+// contending for the same ~1-10us long critical section will run 7% slower on my machine. If I mess
+// with any of the parameters - change the number of threads or change the critical section duration -
+// then ByteLock reaches parity with Lock, and sometimes outperforms it. Perhaps most surprisingly,
+// the slow-down goes away even when you increase the number of threads. ByteLock appears to sometimes
+// be faster under microcontention, perhaps because a contentious 8-bit CAS is cheaper than a
+// contentious 64-bit CAS. Note that uncontended locking is equally fast with ByteLock as with Lock.
+// In all, Lock and ByteLock have similar performance under controlled microbenchmarks, but Lock is
+// theoretically safer because of the thundering herd issue. It's probably best to use ByteLock only
+// when you really care about space and you don't have reason to believe that a large number of
+// threads would ever pile onto the same lock.
+
+class ByteLock {
+ WTF_MAKE_NONCOPYABLE(ByteLock);
+public:
+ ByteLock()
+ {
+ m_byte.store(0, std::memory_order_relaxed);
+ }
+
+ void lock()
+ {
+ if (LIKELY(m_byte.compareExchangeWeak(0, isHeldBit, std::memory_order_acquire))) {
+ // Lock acquired!
+ return;
+ }
+
+ lockSlow();
+ }
+
+ void unlock()
+ {
+ if (LIKELY(m_byte.compareExchangeWeak(isHeldBit, 0, std::memory_order_release))) {
+ // Lock released and nobody was waiting!
+ return;
+ }
+
+ unlockSlow();
+ }
+
+ bool isHeld() const
+ {
+ return m_byte.load(std::memory_order_acquire) & isHeldBit;
+ }
+
+ bool isLocked() const
+ {
+ return isHeld();
+ }
+
+private:
+ static const uint8_t isHeldBit = 1;
+ static const uint8_t hasParkedBit = 2;
+
+ WTF_EXPORT_PRIVATE void lockSlow();
+ WTF_EXPORT_PRIVATE void unlockSlow();
+
+ Atomic<uint8_t> m_byte;
+};
+
+typedef Locker<ByteLock> ByteLocker;
+
+} // namespace WTF
+
+using WTF::ByteLock;
+using WTF::ByteLocker;
+
+#endif // ByteLock_h
+
Modified: trunk/Source/WTF/wtf/CMakeLists.txt (188279 => 188280)
--- trunk/Source/WTF/wtf/CMakeLists.txt 2015-08-11 19:48:50 UTC (rev 188279)
+++ trunk/Source/WTF/wtf/CMakeLists.txt 2015-08-11 19:51:35 UTC (rev 188280)
@@ -7,6 +7,7 @@
BitVector.h
Bitmap.h
BumpPointerAllocator.h
+ ByteLock.h
ByteOrder.h
CompilationThread.h
Compiler.h
@@ -62,6 +63,7 @@
ParallelJobsGeneric.h
ParallelJobsLibdispatch.h
ParallelJobsOpenMP.h
+ ParkingLot.h
PassRefPtr.h
Platform.h
PrintStream.h
@@ -144,6 +146,7 @@
Assertions.cpp
Atomics.cpp
BitVector.cpp
+ ByteLock.cpp
CompilationThread.cpp
CryptographicUtilities.cpp
CryptographicallyRandomNumber.cpp
@@ -166,6 +169,7 @@
OSRandomSource.cpp
PageBlock.cpp
ParallelJobsGeneric.cpp
+ ParkingLot.cpp
PrintStream.cpp
RAMSize.cpp
RandomNumber.cpp
Modified: trunk/Source/WTF/wtf/Lock.h (188279 => 188280)
--- trunk/Source/WTF/wtf/Lock.h 2015-08-11 19:48:50 UTC (rev 188279)
+++ trunk/Source/WTF/wtf/Lock.h 2015-08-11 19:51:35 UTC (rev 188280)
@@ -102,6 +102,33 @@
// acquisition order under contention. The same caveat is generally true of SpinLock and platform
// mutexes on some platforms.
+// FIXME: We could make this Lock more efficient by using ParkingLot and atomic add instead of CAS.
+// The lock would be available if the 32-bit lock word <= 1. Locking would atomically add 2 to the
+// word. The lock would be known to be held if the old value of the word was <= 1. The low bit
+// just indicates if anyone is waiting. If the word was >= 2 after the atomic add, we would go to a
+// slow path that repeatedly attempts to set the lock word to 3 [sic] from 0 or 1, and parks if that's
+// not possible. The slow path could also perform defensive fixup that drops the lock value down to
+// 3 if it was greater than 3, anytime that it needed to go to park. The unlock fast path would
+// atomically subtract 2. If the decrement operation does not cause the count to zero, it would go to
+// a slow path. The slow path would unpark one. If unparking returns false, the slow path would
+// attempt a strong CAS from 1 to 0. It wouldn't do anything if the CAS fails, since the only goal of
+// that CAS is to tell future unlock fast paths that there is possibly a thread parked. As such the
+// states of the lock are:
+//
+// 0: lock available and nobody waiting
+// 1: lock available and there may be threads waiting
+// 2: lock taken and no threads waiting
+// >=3: lock taken and threads waiting
+//
+// It may be possible to design an even better lock implementation based on atomic increments rather
+// than atomic +=2/-=2.
+//
+// Note that because ParkingLot uses this lock internally, we would probably rename this lock
+// implementation to something like BootstrapLock or even make it part of an anonymous namespace
+// inside ParkingLot.
+//
+// https://bugs.webkit.org/show_bug.cgi?id=147841
+
// This is a struct without a constructor or destructor so that it can be statically initialized.
// Use Lock in instance variables.
struct LockBase {
Added: trunk/Source/WTF/wtf/ParkingLot.cpp (0 => 188280)
--- trunk/Source/WTF/wtf/ParkingLot.cpp (rev 0)
+++ trunk/Source/WTF/wtf/ParkingLot.cpp 2015-08-11 19:51:35 UTC (rev 188280)
@@ -0,0 +1,611 @@
+/*
+ * Copyright (C) 2015 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 "ParkingLot.h"
+
+#include "DataLog.h"
+#include "HashFunctions.h"
+#include "Lock.h"
+#include "StringPrintStream.h"
+#include "ThreadSpecific.h"
+#include "ThreadingPrimitives.h"
+#include "Vector.h"
+#include <condition_variable>
+#include <mutex>
+#include <thread>
+
+namespace WTF {
+
+namespace {
+
+const bool verbose = false;
+
+struct ThreadData {
+ WTF_MAKE_FAST_ALLOCATED;
+public:
+
+ ThreadData();
+ ~ThreadData();
+
+ ThreadIdentifier threadIdentifier;
+
+ bool shouldPark { false };
+ std::mutex parkingLock;
+ std::condition_variable parkingCondition;
+
+ const void* address;
+ ThreadData* nextInQueue { nullptr };
+};
+
+enum class DequeueResult {
+ Ignore,
+ RemoveAndContinue,
+ RemoveAndStop
+};
+
+struct Bucket {
+ WTF_MAKE_FAST_ALLOCATED;
+public:
+ void enqueue(ThreadData* data)
+ {
+ if (verbose)
+ dataLog(toString(currentThread(), ": enqueueing ", RawPointer(data), " with address = ", RawPointer(data->address), " onto ", RawPointer(this), "\n"));
+ ASSERT(data->address);
+ ASSERT(!data->nextInQueue);
+
+ if (queueTail) {
+ queueTail->nextInQueue = data;
+ queueTail = data;
+ return;
+ }
+
+ queueHead = data;
+ queueTail = data;
+ }
+
+ template<typename Functor>
+ void genericDequeue(const Functor& functor)
+ {
+ if (verbose)
+ dataLog(toString(currentThread(), ": dequeueing from bucket at ", RawPointer(this), "\n"));
+
+ if (!queueHead) {
+ if (verbose)
+ dataLog(toString(currentThread(), ": empty.\n"));
+ return;
+ }
+
+ // This loop is a very clever abomination. The induction variables are the pointer to the
+ // pointer to the current node, and the pointer to the previous node. This gives us everything
+ // we need to both proceed forward to the next node, and to remove nodes while maintaining the
+ // queueHead/queueTail and all of the nextInQueue links. For example, when we are at the head
+ // element, then removal means rewiring queueHead, and if it was also equal to queueTail, then
+ // we'd want queueTail to be set to nullptr. This works because:
+ //
+ // currentPtr == &queueHead
+ // previous == nullptr
+ //
+ // We remove by setting *currentPtr = (*currentPtr)->nextInQueue, i.e. changing the pointer
+ // that used to point to this node to instead point to this node's successor. Another example:
+ // if we were at the second node in the queue, then we'd have:
+ //
+ // currentPtr == &queueHead->nextInQueue
+ // previous == queueHead
+ //
+ // If this node is not equal to queueTail, then removing it simply means making
+ // queueHead->nextInQueue point to queueHead->nextInQueue->nextInQueue (which the algorithm
+ // achieves by mutating *currentPtr). If this node is equal to queueTail, then we want to set
+ // queueTail to previous, which in this case is queueHead - thus making the queue look like a
+ // proper one-element queue with queueHead == queueTail.
+ bool shouldContinue = true;
+ ThreadData** currentPtr = &queueHead;
+ ThreadData* previous = nullptr;
+ while (shouldContinue) {
+ ThreadData* current = *currentPtr;
+ if (verbose)
+ dataLog(toString(currentThread(), ": got thread ", RawPointer(current), "\n"));
+ if (!current)
+ break;
+ DequeueResult result = functor(current);
+ switch (result) {
+ case DequeueResult::Ignore:
+ if (verbose)
+ dataLog(toString(currentThread(), ": currentPtr = ", RawPointer(currentPtr), ", *currentPtr = ", RawPointer(*currentPtr), "\n"));
+ previous = current;
+ currentPtr = &(*currentPtr)->nextInQueue;
+ break;
+ case DequeueResult::RemoveAndContinue:
+ case DequeueResult::RemoveAndStop:
+ if (verbose)
+ dataLog(toString(currentThread(), ": dequeueing ", RawPointer(current), " from ", RawPointer(this), "\n"));
+ if (current == queueTail)
+ queueTail = previous;
+ *currentPtr = current->nextInQueue;
+ current->nextInQueue = nullptr;
+ if (result == DequeueResult::RemoveAndStop)
+ shouldContinue = false;
+ break;
+ }
+ }
+
+ ASSERT(!!queueHead == !!queueTail);
+ }
+
+ ThreadData* dequeue()
+ {
+ ThreadData* result = nullptr;
+ genericDequeue(
+ [&] (ThreadData* element) -> DequeueResult {
+ result = element;
+ return DequeueResult::RemoveAndStop;
+ });
+ return result;
+ }
+
+ ThreadData* queueHead { nullptr };
+ ThreadData* queueTail { nullptr };
+
+ // This lock protects the entire bucket. Thou shall not make changes to Bucket without holding
+ // this lock.
+ Lock lock;
+
+ // Put some distane between buckets in memory. This is one of several mitigations against false
+ // sharing.
+ char padding[64];
+};
+
+struct Hashtable {
+ unsigned size;
+ Atomic<Bucket*> data[1];
+
+ static Hashtable* create(unsigned size)
+ {
+ ASSERT(size >= 1);
+
+ Hashtable* result = static_cast<Hashtable*>(
+ fastZeroedMalloc(sizeof(Hashtable) + sizeof(Atomic<Bucket*>) * (size - 1)));
+ result->size = size;
+ return result;
+ }
+
+ static void destroy(Hashtable* hashtable)
+ {
+ fastFree(hashtable);
+ }
+};
+
+ThreadSpecific<ThreadData>* threadData;
+Atomic<Hashtable*> hashtable;
+Atomic<unsigned> numThreads;
+
+// With 64 bytes of padding per bucket, assuming a hashtable is fully populated with buckets, the
+// memory usage per thread will still be less than 1KB.
+const unsigned maxLoadFactor = 3;
+
+const unsigned growthFactor = 2;
+
+unsigned hashAddress(const void* address)
+{
+ return WTF::PtrHash<const void*>::hash(address);
+}
+
+// Locks the hashtable. This reloops in case of rehashing, so the current hashtable may be different
+// after this returns than when you called it. Guarantees that there is a hashtable. This is pretty
+// slow and not scalable, so it's only used during thread creation and for debugging/testing.
+Vector<Bucket*> lockHashtable()
+{
+ for (;;) {
+ Hashtable* currentHashtable;
+
+ currentHashtable = hashtable.load();
+ if (!currentHashtable) {
+ // Try to be the first to create the hashtable.
+ currentHashtable = Hashtable::create(maxLoadFactor);
+ if (!hashtable.compareExchangeWeak(nullptr, currentHashtable)) {
+ Hashtable::destroy(currentHashtable);
+ continue;
+ }
+ if (verbose)
+ dataLog(toString(currentThread(), ": created initial hashtable ", RawPointer(currentHashtable), "\n"));
+ }
+
+ // Now find all of the buckets. This makes sure that the hashtable is full of buckets so that
+ // we can lock all of the buckets, not just the ones that are materialized.
+ Vector<Bucket*> buckets;
+ for (unsigned i = currentHashtable->size; i--;) {
+ Atomic<Bucket*>& bucketPointer = currentHashtable->data[i];
+
+ for (;;) {
+ Bucket* bucket = bucketPointer.load();
+
+ if (!bucket) {
+ bucket = new Bucket();
+ if (!bucketPointer.compareExchangeWeak(nullptr, bucket)) {
+ delete bucket;
+ continue;
+ }
+ }
+
+ buckets.append(bucket);
+ break;
+ }
+ }
+
+ // Now lock the buckets in the right order.
+ std::sort(buckets.begin(), buckets.end());
+ for (Bucket* bucket : buckets)
+ bucket->lock.lock();
+
+ // If the hashtable didn't change (wasn't rehashed) while we were locking it, then we own it
+ // now.
+ if (hashtable.load() == currentHashtable)
+ return buckets;
+
+ // The hashtable rehashed. Unlock everything and try again.
+ for (Bucket* bucket : buckets)
+ bucket->lock.unlock();
+ }
+}
+
+void unlockHashtable(const Vector<Bucket*>& buckets)
+{
+ for (Bucket* bucket : buckets)
+ bucket->lock.unlock();
+}
+
+// Rehash the hashtable to handle numThreads threads.
+void ensureHashtableSize(unsigned numThreads)
+{
+ // We try to ensure that the size of the hashtable used for thread queues is always large enough
+ // to avoid collisions. So, since we started a new thread, we may need to increase the size of the
+ // hashtable. This does just that. Note that we never free the old spine, since we never lock
+ // around spine accesses (i.e. the "hashtable" global variable).
+
+ // First do a fast check to see if rehashing is needed.
+ Hashtable* oldHashtable = hashtable.load();
+ if (oldHashtable && static_cast<double>(oldHashtable->size) / static_cast<double>(numThreads) >= maxLoadFactor) {
+ if (verbose)
+ dataLog(toString(currentThread(), ": no need to rehash because ", oldHashtable->size, " / ", numThreads, " >= ", maxLoadFactor, "\n"));
+ return;
+ }
+
+ // Seems like we *might* have to rehash, so lock the hashtable and try again.
+ Vector<Bucket*> bucketsToUnlock = lockHashtable();
+
+ // Check again, since the hashtable could have rehashed while we were locking it. Also,
+ // lockHashtable() creates an initial hashtable for us.
+ oldHashtable = hashtable.load();
+ if (oldHashtable && static_cast<double>(oldHashtable->size) / static_cast<double>(numThreads) >= maxLoadFactor) {
+ if (verbose)
+ dataLog(toString(currentThread(), ": after locking, no need to rehash because ", oldHashtable->size, " / ", numThreads, " >= ", maxLoadFactor, "\n"));
+ unlockHashtable(bucketsToUnlock);
+ return;
+ }
+
+ Vector<Bucket*> reusableBuckets = bucketsToUnlock;
+
+ // OK, now we resize. First we gather all thread datas from the old hashtable. These thread datas
+ // are placed into the vector in queue order.
+ Vector<ThreadData*> threadDatas;
+ for (Bucket* bucket : reusableBuckets) {
+ while (ThreadData* threadData = bucket->dequeue())
+ threadDatas.append(threadData);
+ }
+
+ unsigned newSize = numThreads * growthFactor * maxLoadFactor;
+ RELEASE_ASSERT(newSize > oldHashtable->size);
+
+ Hashtable* newHashtable = Hashtable::create(newSize);
+ if (verbose)
+ dataLog(toString(currentThread(), ": created new hashtable: ", RawPointer(newHashtable), "\n"));
+ for (ThreadData* threadData : threadDatas) {
+ if (verbose)
+ dataLog(toString(currentThread(), ": rehashing thread data ", RawPointer(threadData), " with address = ", RawPointer(threadData->address), "\n"));
+ unsigned hash = hashAddress(threadData->address);
+ unsigned index = hash % newHashtable->size;
+ if (verbose)
+ dataLog(toString(currentThread(), ": index = ", index, "\n"));
+ Bucket* bucket = newHashtable->data[index].load();
+ if (!bucket) {
+ if (reusableBuckets.isEmpty())
+ bucket = new Bucket();
+ else
+ bucket = reusableBuckets.takeLast();
+ newHashtable->data[index].store(bucket);
+ }
+
+ bucket->enqueue(threadData);
+ }
+
+ // At this point there may be some buckets left unreused. This could easily happen if the
+ // number of enqueued threads right now is low but the high watermark of the number of threads
+ // enqueued was high. We place these buckets into the hashtable basically at random, just to
+ // make sure we don't leak them.
+ for (unsigned i = 0; i < newHashtable->size && !reusableBuckets.isEmpty(); ++i) {
+ Atomic<Bucket*>& bucketPtr = newHashtable->data[i];
+ if (bucketPtr.load())
+ continue;
+ bucketPtr.store(reusableBuckets.takeLast());
+ }
+
+ // Since we increased the size of the hashtable, we should have exhausted our preallocated
+ // buckets by now.
+ ASSERT(reusableBuckets.isEmpty());
+
+ // OK, right now the old hashtable is locked up and the new hashtable is ready to rock and
+ // roll. After we install the new hashtable, we can release all bucket locks.
+
+ bool result = hashtable.compareExchangeStrong(oldHashtable, newHashtable);
+ RELEASE_ASSERT(result);
+
+ unlockHashtable(bucketsToUnlock);
+}
+
+ThreadData::ThreadData()
+ : threadIdentifier(currentThread())
+{
+ unsigned currentNumThreads;
+ for (;;) {
+ unsigned oldNumThreads = numThreads.load();
+ currentNumThreads = oldNumThreads + 1;
+ if (numThreads.compareExchangeWeak(oldNumThreads, currentNumThreads))
+ break;
+ }
+
+ ensureHashtableSize(currentNumThreads);
+}
+
+ThreadData::~ThreadData()
+{
+ for (;;) {
+ unsigned oldNumThreads = numThreads.load();
+ if (numThreads.compareExchangeWeak(oldNumThreads, oldNumThreads - 1))
+ break;
+ }
+}
+
+ThreadData* myThreadData()
+{
+ static std::once_flag initializeOnce;
+ std::call_once(
+ initializeOnce,
+ [] {
+ threadData = new ThreadSpecific<ThreadData>();
+ });
+
+ return *threadData;
+}
+
+template<typename Functor>
+bool enqueue(const void* address, const Functor& functor)
+{
+ unsigned hash = hashAddress(address);
+
+ for (;;) {
+ Hashtable* myHashtable = hashtable.load();
+ unsigned index = hash % myHashtable->size;
+ Atomic<Bucket*>& bucketPointer = myHashtable->data[index];
+ Bucket* bucket;
+ for (;;) {
+ bucket = bucketPointer.load();
+ if (!bucket) {
+ bucket = new Bucket();
+ if (!bucketPointer.compareExchangeWeak(nullptr, bucket)) {
+ delete bucket;
+ continue;
+ }
+ }
+ break;
+ }
+ if (verbose)
+ dataLog(toString(currentThread(), ": enqueueing onto bucket ", RawPointer(bucket), " with index ", index, " for address ", RawPointer(address), " with hash ", hash, "\n"));
+ bucket->lock.lock();
+
+ // At this point the hashtable could have rehashed under us.
+ if (hashtable.load() != myHashtable) {
+ bucket->lock.unlock();
+ continue;
+ }
+
+ ThreadData* threadData = functor();
+ bool result;
+ if (threadData) {
+ if (verbose)
+ dataLog(toString(currentThread(), ": proceeding to enqueue ", RawPointer(threadData), "\n"));
+ bucket->enqueue(threadData);
+ result = true;
+ } else
+ result = false;
+ bucket->lock.unlock();
+ return result;
+ }
+}
+
+template<typename Functor>
+bool dequeue(const void* address, const Functor& functor)
+{
+ if (verbose)
+ dataLog(toString(currentThread(), ": dequeueing address ", RawPointer(address), "\n"));
+ unsigned hash = hashAddress(address);
+ if (verbose)
+ dataLog(toString(currentThread(), ": hash = ", hash, "\n"));
+
+ for (;;) {
+ Hashtable* myHashtable = hashtable.load();
+ if (!myHashtable) {
+ if (verbose)
+ dataLog(toString(currentThread(), ": no hashtable.\n"));
+ return false;
+ }
+ unsigned index = hash % myHashtable->size;
+ if (verbose)
+ dataLog(toString(currentThread(), ": index = ", index, "\n"));
+ Bucket* bucket = myHashtable->data[index].load();
+ if (!bucket) {
+ if (verbose)
+ dataLog(toString(currentThread(), ": no bucket at ", RawPointer(bucket), ".\n"));
+ return false;
+ }
+
+ if (verbose)
+ dataLog(toString(currentThread(), ": locking bucket at ", RawPointer(bucket), "\n"));
+ bucket->lock.lock();
+ if (verbose)
+ dataLog(toString(currentThread(), ": locked bucket at ", RawPointer(bucket), "\n"));
+
+ // At this point the hashtable could have rehashed under us.
+ if (hashtable.load() != myHashtable) {
+ if (verbose)
+ dataLog(toString(currentThread(), ": hashtable changed.\n"));
+ bucket->lock.unlock();
+ continue;
+ }
+
+ if (verbose)
+ dataLog(toString(currentThread(), ": found bucket.\n"));
+ bucket->genericDequeue(functor);
+ bool result = !!bucket->queueHead;
+ bucket->lock.unlock();
+ return result;
+ }
+}
+
+} // anonymous namespace
+
+bool ParkingLot::parkConditionally(const void* address, std::function<bool()> validation)
+{
+ if (verbose)
+ dataLog(toString(currentThread(), ": parking.\n"));
+
+ ThreadData* me = myThreadData();
+
+ ASSERT(!me->shouldPark);
+
+ bool result = enqueue(
+ address,
+ [&] () -> ThreadData* {
+ if (!validation())
+ return nullptr;
+
+ me->address = address;
+ me->shouldPark = true;
+ return me;
+ });
+
+ if (!result)
+ return false;
+
+ if (verbose)
+ dataLog(toString(currentThread(), ": parking self: ", RawPointer(me), "\n"));
+ {
+ std::unique_lock<std::mutex> locker(me->parkingLock);
+ while (me->shouldPark)
+ me->parkingCondition.wait(locker);
+
+ me->address = nullptr;
+ }
+ if (verbose)
+ dataLog(toString(currentThread(), ": unparked self: ", RawPointer(me), "\n"));
+ return true;
+}
+
+bool ParkingLot::unparkOne(const void* address)
+{
+ if (verbose)
+ dataLog(toString(currentThread(), ": unparking one.\n"));
+
+ ThreadData* threadData = nullptr;
+ bool result = dequeue(
+ address,
+ [&] (ThreadData* element) {
+ if (element->address != address)
+ return DequeueResult::Ignore;
+ threadData = element;
+ return DequeueResult::RemoveAndStop;
+ });
+
+ if (!threadData)
+ return false;
+
+ ASSERT(threadData->shouldPark);
+
+ {
+ std::unique_lock<std::mutex> locker(threadData->parkingLock);
+ threadData->shouldPark = false;
+ threadData->parkingCondition.notify_all();
+ }
+
+ return result;
+}
+
+void ParkingLot::unparkAll(const void* address)
+{
+ if (verbose)
+ dataLog(toString(currentThread(), ": unparking all from ", RawPointer(address), ".\n"));
+
+ Vector<ThreadData*, 8> threadDatas;
+ dequeue(
+ address,
+ [&] (ThreadData* element) {
+ if (verbose)
+ dataLog(toString(currentThread(), ": Observing element with address = ", RawPointer(element->address), "\n"));
+ if (element->address != address)
+ return DequeueResult::Ignore;
+ threadDatas.append(element);
+ return DequeueResult::RemoveAndContinue;
+ });
+
+ for (ThreadData* threadData : threadDatas) {
+ if (verbose)
+ dataLog(toString(currentThread(), ": unparking ", RawPointer(threadData), " with address ", RawPointer(threadData->address), "\n"));
+ ASSERT(threadData->shouldPark);
+ std::unique_lock<std::mutex> locker(threadData->parkingLock);
+ threadData->shouldPark = false;
+ threadData->parkingCondition.notify_all();
+ }
+
+ if (verbose)
+ dataLog(toString(currentThread(), ": done unparking.\n"));
+}
+
+void ParkingLot::forEach(std::function<void(ThreadIdentifier, const void*)> callback)
+{
+ Vector<Bucket*> bucketsToUnlock = lockHashtable();
+
+ Hashtable* currentHashtable = hashtable.load();
+ for (unsigned i = currentHashtable->size; i--;) {
+ Bucket* bucket = currentHashtable->data[i].load();
+ if (!bucket)
+ continue;
+ for (ThreadData* currentThreadData = bucket->queueHead; currentThreadData; currentThreadData = currentThreadData->nextInQueue)
+ callback(currentThreadData->threadIdentifier, currentThreadData->address);
+ }
+
+ unlockHashtable(bucketsToUnlock);
+}
+
+} // namespace WTF
+
Added: trunk/Source/WTF/wtf/ParkingLot.h (0 => 188280)
--- trunk/Source/WTF/wtf/ParkingLot.h (rev 0)
+++ trunk/Source/WTF/wtf/ParkingLot.h 2015-08-11 19:51:35 UTC (rev 188280)
@@ -0,0 +1,86 @@
+/*
+ * Copyright (C) 2015 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 WTF_ParkingLot_h
+#define WTF_ParkingLot_h
+
+#include <functional>
+#include <wtf/Atomics.h>
+#include <wtf/Threading.h>
+
+namespace WTF {
+
+class ParkingLot {
+ ParkingLot() = delete;
+ ParkingLot(const ParkingLot&) = delete;
+
+public:
+ // Parks the thread in a queue associated with the given address, which cannot be null. The
+ // parking only succeeds if the validation function returns true while the queue lock is held.
+ // Returns true if the thread actually slept, or false if it returned quickly because of
+ // validation failure.
+ WTF_EXPORT_PRIVATE static bool parkConditionally(const void* address, std::function<bool()> validation);
+
+ template<typename T, typename U>
+ static bool compareAndPark(const Atomic<T>* address, U expected)
+ {
+ return parkConditionally(
+ address,
+ [address, expected] () -> bool {
+ U value = address->load();
+ return value == expected;
+ });
+ }
+
+ // Unparks one thread from the queue associated with the given address, which cannot be null.
+ // Returns true if there may still be other threads on that queue, or false if there definitely
+ // are no more threads on the queue.
+ WTF_EXPORT_PRIVATE static bool unparkOne(const void* address);
+
+ // Unparks every thread from the queue associated with the given address, which cannot be null.
+ WTF_EXPORT_PRIVATE static void unparkAll(const void* address);
+
+ // Locks the parking lot and walks all of the parked threads and the addresses they are waiting
+ // on. Threads that are on the same queue are guaranteed to be walked from first to last, but the
+ // queues may be randomly interleaved. For example, if the queue for address A1 has T1 and T2 and
+ // the queue for address A2 has T3 and T4, then you might see iteration orders like:
+ //
+ // A1,T1 A1,T2 A2,T3 A2,T4
+ // A2,T3 A2,T4 A1,T1 A1,T2
+ // A1,T1 A2,T3 A1,T2 A2,T4
+ // A1,T1 A2,T3 A2,T4 A1,T2
+ //
+ // As well as many other possible interleaves that all have T1 before T2 and T3 before T4 but are
+ // otherwise unconstrained. This method is useful primarily for debugging. It's also used by unit
+ // tests.
+ WTF_EXPORT_PRIVATE static void forEach(std::function<void(ThreadIdentifier, const void*)>);
+};
+
+} // namespace WTF
+
+using WTF::ParkingLot;
+
+#endif // WTF_ParkingLot_h
+
Modified: trunk/Tools/ChangeLog (188279 => 188280)
--- trunk/Tools/ChangeLog 2015-08-11 19:48:50 UTC (rev 188279)
+++ trunk/Tools/ChangeLog 2015-08-11 19:51:35 UTC (rev 188280)
@@ -1,3 +1,18 @@
+2015-08-10 Filip Pizlo <[email protected]>
+
+ WTF should have a ParkingLot for parking sleeping threads, so that locks can fit in 1.6 bits
+ https://bugs.webkit.org/show_bug.cgi?id=147665
+
+ Reviewed by Mark Lam.
+
+ * TestWebKitAPI/CMakeLists.txt:
+ * TestWebKitAPI/TestWebKitAPI.vcxproj/TestWebKitAPI.vcxproj:
+ * TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:
+ * TestWebKitAPI/Tests/WTF/Lock.cpp:
+ (TestWebKitAPI::TEST):
+ * TestWebKitAPI/Tests/WTF/ParkingLot.cpp: Added.
+ (TestWebKitAPI::TEST):
+
2015-08-11 Brian Burg <[email protected]>
webkit-patch should not explode when $EDITOR is set incorrectly
Modified: trunk/Tools/TestWebKitAPI/CMakeLists.txt (188279 => 188280)
--- trunk/Tools/TestWebKitAPI/CMakeLists.txt 2015-08-11 19:48:50 UTC (rev 188279)
+++ trunk/Tools/TestWebKitAPI/CMakeLists.txt 2015-08-11 19:51:35 UTC (rev 188280)
@@ -56,6 +56,7 @@
${TESTWEBKITAPI_DIR}/Tests/WTF/MediaTime.cpp
${TESTWEBKITAPI_DIR}/Tests/WTF/MetaAllocator.cpp
${TESTWEBKITAPI_DIR}/Tests/WTF/NakedPtr.cpp
+ ${TESTWEBKITAPI_DIR}/Tests/WTF/ParkingLot.cpp
${TESTWEBKITAPI_DIR}/Tests/WTF/RedBlackTree.cpp
${TESTWEBKITAPI_DIR}/Tests/WTF/Ref.cpp
${TESTWEBKITAPI_DIR}/Tests/WTF/RefPtr.cpp
Modified: trunk/Tools/TestWebKitAPI/TestWebKitAPI.vcxproj/TestWebKitAPI.vcxproj (188279 => 188280)
--- trunk/Tools/TestWebKitAPI/TestWebKitAPI.vcxproj/TestWebKitAPI.vcxproj 2015-08-11 19:48:50 UTC (rev 188279)
+++ trunk/Tools/TestWebKitAPI/TestWebKitAPI.vcxproj/TestWebKitAPI.vcxproj 2015-08-11 19:51:35 UTC (rev 188280)
@@ -326,6 +326,7 @@
<ClCompile Include="..\Tests\WTF\MetaAllocator.cpp" />
<ClCompile Include="..\Tests\WTF\NakedPtr.cpp" />
<ClCompile Include="..\Tests\WTF\Optional.cpp" />
+ <ClCompile Include="..\Tests\WTF\ParkingLot.cpp" />
<ClCompile Include="..\Tests\WTF\RedBlackTree.cpp" />
<ClCompile Include="..\Tests\WTF\Ref.cpp" />
<ClCompile Include="..\Tests\WTF\RefCounter.cpp" />
Modified: trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj (188279 => 188280)
--- trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj 2015-08-11 19:48:50 UTC (rev 188279)
+++ trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj 2015-08-11 19:51:35 UTC (rev 188280)
@@ -11,6 +11,7 @@
0F139E781A423A6B00F590F5 /* PlatformUtilitiesCocoa.mm in Sources */ = {isa = PBXBuildFile; fileRef = 0F139E721A423A2B00F590F5 /* PlatformUtilitiesCocoa.mm */; };
0F139E791A42457000F590F5 /* PlatformUtilitiesCocoa.mm in Sources */ = {isa = PBXBuildFile; fileRef = 0F139E721A423A2B00F590F5 /* PlatformUtilitiesCocoa.mm */; };
0F3B94A71A77267400DE3272 /* WKWebViewEvaluateJavaScript.mm in Sources */ = {isa = PBXBuildFile; fileRef = 0F3B94A51A77266C00DE3272 /* WKWebViewEvaluateJavaScript.mm */; };
+ 0FE447991B76F1EB009498EB /* ParkingLot.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FE447971B76F1E3009498EB /* ParkingLot.cpp */; };
0FFC45A61B73EBEB0085BD62 /* Lock.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FFC45A41B73EBE20085BD62 /* Lock.cpp */; };
1A02C870125D4CFD00E3F4BD /* find.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = 1A02C84B125D4A5E00E3F4BD /* find.html */; };
1A50AA201A2A51FC00F4C345 /* close-from-within-create-page.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = 1A50AA1F1A2A4EA500F4C345 /* close-from-within-create-page.html */; };
@@ -429,6 +430,7 @@
0F3B94A51A77266C00DE3272 /* WKWebViewEvaluateJavaScript.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = WKWebViewEvaluateJavaScript.mm; sourceTree = "<group>"; };
0FC6C4CB141027E0005B7F0C /* RedBlackTree.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = RedBlackTree.cpp; sourceTree = "<group>"; };
0FC6C4CE141034AD005B7F0C /* MetaAllocator.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = MetaAllocator.cpp; sourceTree = "<group>"; };
+ 0FE447971B76F1E3009498EB /* ParkingLot.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ParkingLot.cpp; sourceTree = "<group>"; };
0FFC45A41B73EBE20085BD62 /* Lock.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Lock.cpp; sourceTree = "<group>"; };
14464012167A8305000BD218 /* LayoutUnit.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LayoutUnit.cpp; sourceTree = "<group>"; };
14F3B11215E45EAB00210069 /* SaturatedArithmeticOperations.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = SaturatedArithmeticOperations.cpp; sourceTree = "<group>"; };
@@ -1106,6 +1108,7 @@
93A427AC180DA60F00CD24D7 /* MoveOnly.h */,
FEB6F74E1B2BA44E009E4922 /* NakedPtr.cpp */,
1AFDE6541953B2C000C48FFA /* Optional.cpp */,
+ 0FE447971B76F1E3009498EB /* ParkingLot.cpp */,
0FC6C4CB141027E0005B7F0C /* RedBlackTree.cpp */,
93A427AA180DA26400CD24D7 /* Ref.cpp */,
86BD19971A2DB05B006DCF0A /* RefCounter.cpp */,
@@ -1626,6 +1629,7 @@
7CCE7ED71A411A7E00447C4C /* WillPerformClientRedirectToURLCrash.mm in Sources */,
7CCE7F1C1A411AE600447C4C /* WillSendSubmitEvent.cpp in Sources */,
7CCE7ED81A411A7E00447C4C /* WillSendSubmitEvent.mm in Sources */,
+ 0FE447991B76F1EB009498EB /* ParkingLot.cpp in Sources */,
7CCE7ED91A411A7E00447C4C /* WindowlessWebViewWithMedia.mm in Sources */,
7CCE7F2E1A411B1000447C4C /* WKBrowsingContextGroupTest.mm in Sources */,
7CCE7F2F1A411B1000447C4C /* WKBrowsingContextLoadDelegateTest.mm in Sources */,
Modified: trunk/Tools/TestWebKitAPI/Tests/WTF/Lock.cpp (188279 => 188280)
--- trunk/Tools/TestWebKitAPI/Tests/WTF/Lock.cpp 2015-08-11 19:48:50 UTC (rev 188279)
+++ trunk/Tools/TestWebKitAPI/Tests/WTF/Lock.cpp 2015-08-11 19:51:35 UTC (rev 188280)
@@ -24,6 +24,7 @@
*/
#include "config.h"
+#include <wtf/ByteLock.h>
#include <wtf/Lock.h>
#include <wtf/Threading.h>
#include <wtf/ThreadingPrimitives.h>
@@ -97,4 +98,39 @@
runLockTest<Lock>(10, 10, 10000, 1000);
}
+TEST(WTF_ByteLock, UncontentedShortSection)
+{
+ runLockTest<ByteLock>(1, 1, 1, 10000000);
+}
+
+TEST(WTF_ByteLock, UncontentedLongSection)
+{
+ runLockTest<ByteLock>(1, 1, 10000, 1000);
+}
+
+TEST(WTF_ByteLock, ContentedShortSection)
+{
+ runLockTest<ByteLock>(1, 10, 1, 10000000);
+}
+
+TEST(WTF_ByteLock, ContentedLongSection)
+{
+ runLockTest<ByteLock>(1, 10, 10000, 10000);
+}
+
+TEST(WTF_ByteLock, ManyContentedShortSections)
+{
+ runLockTest<ByteLock>(10, 10, 1, 500000);
+}
+
+TEST(WTF_ByteLock, ManyContentedLongSections)
+{
+ runLockTest<ByteLock>(10, 10, 10000, 1000);
+}
+
+TEST(WTF_ByteLock, SectionAddressCollision)
+{
+ runLockTest<ByteLock>(4, 2, 10000, 2000);
+}
+
} // namespace TestWebKitAPI
Added: trunk/Tools/TestWebKitAPI/Tests/WTF/ParkingLot.cpp (0 => 188280)
--- trunk/Tools/TestWebKitAPI/Tests/WTF/ParkingLot.cpp (rev 0)
+++ trunk/Tools/TestWebKitAPI/Tests/WTF/ParkingLot.cpp 2015-08-11 19:51:35 UTC (rev 188280)
@@ -0,0 +1,271 @@
+/*
+ * Copyright (C) 2015 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. AND ITS CONTRIBUTORS ``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 ITS 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 <condition_variable>
+#include <mutex>
+#include <wtf/HashSet.h>
+#include <wtf/ListDump.h>
+#include <wtf/ParkingLot.h>
+#include <wtf/Threading.h>
+#include <wtf/ThreadingPrimitives.h>
+
+using namespace WTF;
+
+namespace TestWebKitAPI {
+
+namespace {
+
+struct SingleLatchTest {
+ void initialize(unsigned numThreads)
+ {
+ // This implements a fair (FIFO) semaphore, and it starts out unavailable.
+ semaphore.store(0);
+
+ for (unsigned i = numThreads; i--;) {
+ threads.append(
+ createThread(
+ "Parking Test Thread",
+ [&] () {
+ EXPECT_NE(0u, currentThread());
+
+ down();
+
+ std::lock_guard<std::mutex> locker(lock);
+ awake.add(currentThread());
+ lastAwoken = currentThread();
+ condition.notify_one();
+ }));
+ }
+ }
+
+ void unparkOne(unsigned singleUnparkIndex)
+ {
+ EXPECT_EQ(0u, lastAwoken);
+
+ unsigned numWaitingOnAddress = 0;
+ Vector<ThreadIdentifier, 8> queue;
+ ParkingLot::forEach(
+ [&] (ThreadIdentifier threadIdentifier, const void* address) {
+ if (address != &semaphore)
+ return;
+
+ queue.append(threadIdentifier);
+
+ numWaitingOnAddress++;
+ });
+
+ EXPECT_LE(numWaitingOnAddress, threads.size() - singleUnparkIndex);
+
+ up();
+
+ {
+ std::unique_lock<std::mutex> locker(lock);
+ while (awake.size() < singleUnparkIndex + 1)
+ condition.wait(locker);
+ EXPECT_NE(0u, lastAwoken);
+ if (!queue.isEmpty() && queue[0] != lastAwoken) {
+ dataLog("Woke up wrong thread: queue = ", listDump(queue), ", last awoken = ", lastAwoken, "\n");
+ EXPECT_EQ(queue[0], lastAwoken);
+ }
+ lastAwoken = 0;
+ }
+ }
+
+ void finish(unsigned numSingleUnparks)
+ {
+ unsigned numWaitingOnAddress = 0;
+ ParkingLot::forEach(
+ [&] (ThreadIdentifier, const void* address) {
+ if (address != &semaphore)
+ return;
+
+ numWaitingOnAddress++;
+ });
+
+ EXPECT_LE(numWaitingOnAddress, threads.size() - numSingleUnparks);
+
+ semaphore.store(threads.size() - numSingleUnparks);
+ ParkingLot::unparkAll(&semaphore);
+
+ numWaitingOnAddress = 0;
+ ParkingLot::forEach(
+ [&] (ThreadIdentifier, const void* address) {
+ if (address != &semaphore)
+ return;
+
+ numWaitingOnAddress++;
+ });
+
+ EXPECT_EQ(0u, numWaitingOnAddress);
+
+ {
+ std::unique_lock<std::mutex> locker(lock);
+ while (awake.size() < threads.size())
+ condition.wait(locker);
+ }
+
+ for (ThreadIdentifier threadIdentifier : threads)
+ waitForThreadCompletion(threadIdentifier);
+ }
+
+ // Semaphore operations.
+ void down()
+ {
+ for (;;) {
+ int oldSemaphoreValue = semaphore.load();
+ int newSemaphoreValue = oldSemaphoreValue - 1;
+ if (!semaphore.compareExchangeWeak(oldSemaphoreValue, newSemaphoreValue))
+ continue;
+
+ if (oldSemaphoreValue > 0) {
+ // We acquired the semaphore. Done.
+ return;
+ }
+
+ // We need to wait.
+ if (ParkingLot::compareAndPark(&semaphore, newSemaphoreValue)) {
+ // We did wait, and then got woken up. This means that someone who up'd the semaphore
+ // passed ownership onto us.
+ return;
+ }
+
+ // We never parked, because the semaphore value changed. Undo our decrement and try again.
+ for (;;) {
+ int oldSemaphoreValue = semaphore.load();
+ if (semaphore.compareExchangeWeak(oldSemaphoreValue, oldSemaphoreValue + 1))
+ break;
+ }
+ }
+ }
+ void up()
+ {
+ int oldSemaphoreValue;
+ for (;;) {
+ oldSemaphoreValue = semaphore.load();
+ if (semaphore.compareExchangeWeak(oldSemaphoreValue, oldSemaphoreValue + 1))
+ break;
+ }
+
+ // Check if anyone was waiting on the semaphore. If they were, then pass ownership to them.
+ if (oldSemaphoreValue < 0)
+ ParkingLot::unparkOne(&semaphore);
+ }
+
+ Atomic<int> semaphore;
+ std::mutex lock;
+ std::condition_variable condition;
+ HashSet<ThreadIdentifier> awake;
+ Vector<ThreadIdentifier> threads;
+ ThreadIdentifier lastAwoken { 0 };
+};
+
+void runParkingTest(unsigned numLatches, unsigned delay, unsigned numThreads, unsigned numSingleUnparks)
+{
+ std::unique_ptr<SingleLatchTest[]> tests = std::make_unique<SingleLatchTest[]>(numLatches);
+
+ for (unsigned latchIndex = numLatches; latchIndex--;)
+ tests[latchIndex].initialize(numThreads);
+
+ for (unsigned unparkIndex = 0; unparkIndex < numSingleUnparks; ++unparkIndex) {
+ usleep(delay);
+ for (unsigned latchIndex = numLatches; latchIndex--;)
+ tests[latchIndex].unparkOne(unparkIndex);
+ }
+
+ for (unsigned latchIndex = numLatches; latchIndex--;)
+ tests[latchIndex].finish(numSingleUnparks);
+}
+
+void repeatParkingTest(unsigned numRepeats, unsigned numLatches, unsigned delay, unsigned numThreads, unsigned numSingleUnparks)
+{
+ while (numRepeats--)
+ runParkingTest(numLatches, delay, numThreads, numSingleUnparks);
+}
+
+} // anonymous namespace
+
+TEST(WTF_ParkingLot, UnparkAllOneFast)
+{
+ repeatParkingTest(10000, 1, 0, 1, 0);
+}
+
+TEST(WTF_ParkingLot, UnparkAllHundredFast)
+{
+ repeatParkingTest(1000, 1, 0, 100, 0);
+}
+
+TEST(WTF_ParkingLot, UnparkOneOneFast)
+{
+ repeatParkingTest(1000, 1, 0, 1, 1);
+}
+
+TEST(WTF_ParkingLot, UnparkOneHundredFast)
+{
+ repeatParkingTest(100, 1, 0, 100, 100);
+}
+
+TEST(WTF_ParkingLot, UnparkOneFiftyThenFiftyAllFast)
+{
+ repeatParkingTest(200, 1, 0, 100, 50);
+}
+
+TEST(WTF_ParkingLot, UnparkAllOne)
+{
+ repeatParkingTest(100, 1, 10000, 1, 0);
+}
+
+TEST(WTF_ParkingLot, UnparkAllHundred)
+{
+ repeatParkingTest(100, 1, 10000, 100, 0);
+}
+
+TEST(WTF_ParkingLot, UnparkOneOne)
+{
+ repeatParkingTest(10, 1, 10000, 1, 1);
+}
+
+TEST(WTF_ParkingLot, UnparkOneHundred)
+{
+ repeatParkingTest(1, 1, 10000, 100, 100);
+}
+
+TEST(WTF_ParkingLot, UnparkOneFiftyThenFiftyAll)
+{
+ repeatParkingTest(2, 1, 10000, 100, 50);
+}
+
+TEST(WTF_ParkingLot, HundredUnparkAllOneFast)
+{
+ repeatParkingTest(100, 100, 0, 1, 0);
+}
+
+TEST(WTF_ParkingLot, HundredUnparkAllOne)
+{
+ repeatParkingTest(1, 100, 10000, 1, 0);
+}
+
+} // namespace TestWebKitAPI
+
