Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (188322 => 188323)
--- trunk/Source/_javascript_Core/ChangeLog 2015-08-12 03:41:40 UTC (rev 188322)
+++ trunk/Source/_javascript_Core/ChangeLog 2015-08-12 04:20:24 UTC (rev 188323)
@@ -1,3 +1,12 @@
+2015-08-11 Filip Pizlo <[email protected]>
+
+ Always use a byte-sized lock implementation
+ https://bugs.webkit.org/show_bug.cgi?id=147908
+
+ Reviewed by Geoffrey Garen.
+
+ * runtime/ConcurrentJITLock.h: Lock is now byte-sized and ByteLock is gone, so use Lock.
+
2015-08-11 Alexey Proskuryakov <[email protected]>
Make ASan build not depend on asan.xcconfig
Modified: trunk/Source/_javascript_Core/runtime/ConcurrentJITLock.h (188322 => 188323)
--- trunk/Source/_javascript_Core/runtime/ConcurrentJITLock.h 2015-08-12 03:41:40 UTC (rev 188322)
+++ trunk/Source/_javascript_Core/runtime/ConcurrentJITLock.h 2015-08-12 04:20:24 UTC (rev 188323)
@@ -27,14 +27,14 @@
#define ConcurrentJITLock_h
#include "DeferGC.h"
-#include <wtf/ByteLock.h>
+#include <wtf/Lock.h>
#include <wtf/NoLock.h>
namespace JSC {
#if ENABLE(CONCURRENT_JIT)
-typedef ByteLock ConcurrentJITLock;
-typedef ByteLocker ConcurrentJITLockerImpl;
+typedef Lock ConcurrentJITLock;
+typedef LockHolder ConcurrentJITLockerImpl;
#else
typedef NoLock ConcurrentJITLock;
typedef NoLockLocker ConcurrentJITLockerImpl;
Modified: trunk/Source/WTF/ChangeLog (188322 => 188323)
--- trunk/Source/WTF/ChangeLog 2015-08-12 03:41:40 UTC (rev 188322)
+++ trunk/Source/WTF/ChangeLog 2015-08-12 04:20:24 UTC (rev 188323)
@@ -1,5 +1,65 @@
2015-08-11 Filip Pizlo <[email protected]>
+ Always use a byte-sized lock implementation
+ https://bugs.webkit.org/show_bug.cgi?id=147908
+
+ Reviewed by Geoffrey Garen.
+
+ 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:
+
+2015-08-11 Filip Pizlo <[email protected]>
+
Remove ByteSpinLock
https://bugs.webkit.org/show_bug.cgi?id=147900
Modified: trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj (188322 => 188323)
--- trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj 2015-08-12 03:41:40 UTC (rev 188322)
+++ trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj 2015-08-12 04:20:24 UTC (rev 188323)
@@ -1,4 +1,4 @@
-<?xml version="1.0" encoding="utf-8"?>
+<?xml version="1.0" encoding="utf-8"?>
<Project DefaultTargets="Build" ToolsVersion="14.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
<ItemGroup Label="ProjectConfigurations">
<ProjectConfiguration Include="DebugSuffix|Win32">
@@ -53,7 +53,6 @@
<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" />
@@ -155,6 +154,7 @@
<ClCompile Include="..\wtf\win\WorkItemWin.cpp" />
<ClCompile Include="..\wtf\win\WorkQueueWin.cpp" />
<ClCompile Include="..\wtf\win\WTFDLL.cpp" />
+ <ClCompile Include="..\wtf\WordLock.cpp" />
<ClCompile Include="..\wtf\WorkQueue.cpp" />
<ClCompile Include="..\wtf\WTFThreadData.cpp" />
<ClCompile Include="..\wtf\SchedulePairCF.cpp" />
@@ -173,7 +173,6 @@
<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" />
@@ -314,6 +313,7 @@
<ClInclude Include="..\wtf\VMTags.h" />
<ClInclude Include="..\wtf\win\GDIObject.h" />
<ClInclude Include="..\wtf\win\WorkItemWin.h" />
+ <ClInclude Include="..\wtf\WordLock.h" />
<ClInclude Include="..\wtf\WorkQueue.h" />
<ClInclude Include="..\wtf\WTFThreadData.h" />
</ItemGroup>
Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (188322 => 188323)
--- trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2015-08-12 03:41:40 UTC (rev 188322)
+++ trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2015-08-12 04:20:24 UTC (rev 188323)
@@ -24,8 +24,6 @@
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 */; };
@@ -46,6 +44,8 @@
0FDDBFA81666DFA300C55FEF /* StringPrintStream.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FDDBFA61666DFA300C55FEF /* StringPrintStream.h */; };
0FE1646A1B6FFC9600400E7C /* Lock.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FE164681B6FFC9600400E7C /* Lock.cpp */; };
0FE1646B1B6FFC9600400E7C /* Lock.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FE164691B6FFC9600400E7C /* Lock.h */; };
+ 0FE4479C1B7AAA03009498EB /* WordLock.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FE4479A1B7AAA03009498EB /* WordLock.cpp */; };
+ 0FE4479D1B7AAA03009498EB /* WordLock.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FE4479B1B7AAA03009498EB /* WordLock.h */; };
0FED67B61B22D4D80066CE15 /* TinyPtrSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FED67B51B22D4D80066CE15 /* TinyPtrSet.h */; };
14022F4118F5C3FC007FF0EB /* libbmalloc.a in Frameworks */ = {isa = PBXBuildFile; fileRef = 14022F4018F5C3FC007FF0EB /* libbmalloc.a */; };
143F611F1565F0F900DB514A /* RAMSize.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 143F611D1565F0F900DB514A /* RAMSize.cpp */; };
@@ -311,8 +311,6 @@
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>"; };
@@ -333,6 +331,8 @@
0FDDBFA61666DFA300C55FEF /* StringPrintStream.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = StringPrintStream.h; sourceTree = "<group>"; };
0FE164681B6FFC9600400E7C /* Lock.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Lock.cpp; sourceTree = "<group>"; };
0FE164691B6FFC9600400E7C /* Lock.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Lock.h; sourceTree = "<group>"; };
+ 0FE4479A1B7AAA03009498EB /* WordLock.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = WordLock.cpp; sourceTree = "<group>"; };
+ 0FE4479B1B7AAA03009498EB /* WordLock.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = WordLock.h; sourceTree = "<group>"; };
0FED67B51B22D4D80066CE15 /* TinyPtrSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = TinyPtrSet.h; sourceTree = "<group>"; };
14022F4018F5C3FC007FF0EB /* libbmalloc.a */ = {isa = PBXFileReference; lastKnownFileType = archive.ar; path = libbmalloc.a; sourceTree = BUILT_PRODUCTS_DIR; };
143F611D1565F0F900DB514A /* RAMSize.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = RAMSize.cpp; sourceTree = "<group>"; };
@@ -723,8 +723,6 @@
A8A47264151A825A004123FF /* BlockStack.h */,
A8A47265151A825A004123FF /* BloomFilter.h */,
A8A47267151A825A004123FF /* BumpPointerAllocator.h */,
- 0F824A621B7443A0002E345D /* ByteLock.cpp */,
- 0F824A631B7443A0002E345D /* ByteLock.h */,
EB95E1EF161A72410089A2F5 /* ByteOrder.h */,
A8A4726A151A825A004123FF /* CheckedArithmetic.h */,
A8A4726B151A825A004123FF /* CheckedBoolean.h */,
@@ -892,6 +890,8 @@
A8A47371151A825B004123FF /* VectorTraits.h */,
A8A47372151A825B004123FF /* VMTags.h */,
974CFC8D16A4F327006D5404 /* WeakPtr.h */,
+ 0FE4479A1B7AAA03009498EB /* WordLock.cpp */,
+ 0FE4479B1B7AAA03009498EB /* WordLock.h */,
E4A0AD371A96245500536DF6 /* WorkQueue.cpp */,
E4A0AD381A96245500536DF6 /* WorkQueue.h */,
A8A4737A151A825B004123FF /* WTFThreadData.cpp */,
@@ -1166,7 +1166,6 @@
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 */,
@@ -1220,6 +1219,7 @@
A8A47454151A825B004123FF /* ThreadSafeRefCounted.h in Headers */,
A8A47455151A825B004123FF /* ThreadSpecific.h in Headers */,
149EF16316BBFE0D000A4331 /* TriState.h in Headers */,
+ 0FE4479D1B7AAA03009498EB /* WordLock.h in Headers */,
A8A4746D151A825B004123FF /* UnionFind.h in Headers */,
A8A4746A151A825B004123FF /* UTF8.h in Headers */,
A8A473B9151A825B004123FF /* utils.h in Headers */,
@@ -1337,7 +1337,6 @@
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 */,
@@ -1400,6 +1399,7 @@
70ECA60D1B02426800449739 /* AtomicStringImpl.cpp in Sources */,
FEDACD3D1630F83F00C69634 /* StackStats.cpp in Sources */,
A8A4743C151A825B004123FF /* StringBuilder.cpp in Sources */,
+ 0FE4479C1B7AAA03009498EB /* WordLock.cpp in Sources */,
A8A47440151A825B004123FF /* StringImpl.cpp in Sources */,
A5BA15FC182435A600A82E69 /* StringImplCF.cpp in Sources */,
A5BA15F51824348000A82E69 /* StringImplMac.mm in Sources */,
Modified: trunk/Source/WTF/benchmarks/LockSpeedTest.cpp (188322 => 188323)
--- trunk/Source/WTF/benchmarks/LockSpeedTest.cpp 2015-08-12 03:41:40 UTC (rev 188322)
+++ trunk/Source/WTF/benchmarks/LockSpeedTest.cpp 2015-08-12 04:20:24 UTC (rev 188323)
@@ -26,13 +26,13 @@
#include "config.h"
#include <unistd.h>
-#include <wtf/ByteLock.h>
#include <wtf/CurrentTime.h>
#include <wtf/Lock.h>
#include <wtf/SpinLock.h>
#include <wtf/StdLibExtras.h>
#include <wtf/Threading.h>
#include <wtf/ThreadingPrimitives.h>
+#include <wtf/WordLock.h>
namespace {
@@ -44,7 +44,7 @@
NO_RETURN void usage()
{
- 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");
+ printf("Usage: LockSpeedTest spinlock|wordlock|lock|bytelock|mutex|all <num thread groups> <num threads per group> <work per critical section> <num noise threads> <num iterations>\n");
exit(1);
}
@@ -122,14 +122,14 @@
runBenchmark<SpinLock>("SpinLock");
didRun = true;
}
+ if (!strcmp(argv[1], "wordlock") || !strcmp(argv[1], "all")) {
+ runBenchmark<WordLock>("WTF WordLock");
+ didRun = true;
+ }
if (!strcmp(argv[1], "lock") || !strcmp(argv[1], "all")) {
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;
Deleted: trunk/Source/WTF/wtf/ByteLock.cpp (188322 => 188323)
--- trunk/Source/WTF/wtf/ByteLock.cpp 2015-08-12 03:41:40 UTC (rev 188322)
+++ trunk/Source/WTF/wtf/ByteLock.cpp 2015-08-12 04:20:24 UTC (rev 188323)
@@ -1,105 +0,0 @@
-/*
- * 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
-
Deleted: trunk/Source/WTF/wtf/ByteLock.h (188322 => 188323)
--- trunk/Source/WTF/wtf/ByteLock.h 2015-08-12 03:41:40 UTC (rev 188322)
+++ trunk/Source/WTF/wtf/ByteLock.h 2015-08-12 04:20:24 UTC (rev 188323)
@@ -1,108 +0,0 @@
-/*
- * 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 (188322 => 188323)
--- trunk/Source/WTF/wtf/CMakeLists.txt 2015-08-12 03:41:40 UTC (rev 188322)
+++ trunk/Source/WTF/wtf/CMakeLists.txt 2015-08-12 04:20:24 UTC (rev 188323)
@@ -7,7 +7,6 @@
BitVector.h
Bitmap.h
BumpPointerAllocator.h
- ByteLock.h
ByteOrder.h
CompilationThread.h
Compiler.h
@@ -104,6 +103,7 @@
VectorTraits.h
WTFThreadData.h
WeakPtr.h
+ WordLock.h
WorkQueue.h
dtoa.h
@@ -146,7 +146,6 @@
Assertions.cpp
Atomics.cpp
BitVector.cpp
- ByteLock.cpp
CompilationThread.cpp
CryptographicUtilities.cpp
CryptographicallyRandomNumber.cpp
@@ -183,6 +182,7 @@
StringPrintStream.cpp
Threading.cpp
WTFThreadData.cpp
+ WordLock.cpp
WorkQueue.cpp
dtoa.cpp
Modified: trunk/Source/WTF/wtf/Lock.cpp (188322 => 188323)
--- trunk/Source/WTF/wtf/Lock.cpp 2015-08-12 03:41:40 UTC (rev 188322)
+++ trunk/Source/WTF/wtf/Lock.cpp 2015-08-12 04:20:24 UTC (rev 188323)
@@ -27,56 +27,15 @@
#include "Lock.h"
#include "DataLog.h"
+#include "ParkingLot.h"
#include "StringPrintStream.h"
-#include "ThreadSpecific.h"
#include "ThreadingPrimitives.h"
-#include <condition_variable>
-#include <mutex>
#include <thread>
namespace WTF {
-namespace {
+static const bool verbose = false;
-// 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 Lock'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 };
-};
-
-ThreadSpecific<ThreadData>* threadData;
-
-ThreadData* myThreadData()
-{
- static std::once_flag initializeOnce;
- std::call_once(
- initializeOnce,
- [] {
- threadData = new ThreadSpecific<ThreadData>();
- });
-
- return *threadData;
-}
-
-} // anonymous namespace
-
void LockBase::lockSlow()
{
unsigned spinCount = 0;
@@ -85,184 +44,62 @@
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;
- }
- }
+ uint8_t currentByteValue = m_byte.load();
+ if (verbose)
+ dataLog(toString(currentThread(), ": locking with ", currentByteValue, "\n"));
- // 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) {
+ // 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 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.
- // But before we acquire the queue spinlock, we make sure that we have a ThreadData for this
- // thread.
- ThreadData* me = myThreadData();
- ASSERT(!me->shouldPark);
- ASSERT(!me->nextInQueue);
- ASSERT(!me->queueTail);
-
- // 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 Lock is held, and we succeed in
- // acquiring the queue lock.
- if ((currentWordValue & isQueueLockedBit)
- || !(currentWordValue & isLockedBit)
- || !m_word.compareExchangeWeak(currentWordValue, currentWordValue | isQueueLockedBit)) {
- std::this_thread::yield();
+ // 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;
- }
-
- me->shouldPark = true;
- // We own the queue. Nobody can enqueue or dequeue until we're done. Also, it's not possible
- // to release the Lock while we hold the queue lock.
- ThreadData* queueHead = bitwise_cast<ThreadData*>(currentWordValue & ~queueHeadMask);
- if (queueHead) {
- // Put this thread at the end of the queue.
- queueHead->queueTail->nextInQueue = me;
- queueHead->queueTail = me;
+ // 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);
- // Release the queue lock.
- currentWordValue = m_word.load();
- ASSERT(currentWordValue & ~queueHeadMask);
- ASSERT(currentWordValue & isQueueLockedBit);
- ASSERT(currentWordValue & isLockedBit);
- m_word.store(currentWordValue & ~isQueueLockedBit);
- } else {
- // Make this thread be the queue-head.
- queueHead = me;
- me->queueTail = me;
-
- // Release the queue lock and install ourselves as the head. No need for a CAS loop, since
- // we own the queue lock.
- currentWordValue = m_word.load();
- ASSERT(~(currentWordValue & ~queueHeadMask));
- ASSERT(currentWordValue & isQueueLockedBit);
- ASSERT(currentWordValue & isLockedBit);
- uintptr_t newWordValue = currentWordValue;
- newWordValue |= bitwise_cast<uintptr_t>(queueHead);
- newWordValue &= ~isQueueLockedBit;
- m_word.store(newWordValue);
- }
-
- // At this point everyone who acquires the queue lock will see me on the queue, and anyone who
- // acquires me's lock will see that me wants to park. Note that shouldPark may have been
- // cleared as soon as the queue lock was released above, but it will happen while the
- // releasing thread holds me's parkingLock.
-
- {
- std::unique_lock<std::mutex> locker(me->parkingLock);
- while (me->shouldPark)
- me->parkingCondition.wait(locker);
- }
-
- ASSERT(!me->shouldPark);
- ASSERT(!me->nextInQueue);
- ASSERT(!me->queueTail);
-
- // Now we can loop around and try to acquire the lock again.
+ // We have awaken, or we never parked because the byte value changed. Either way, we loop
+ // around and try again.
}
}
void LockBase::unlockSlow()
{
- // The fast path can fail either because of spurious weak CAS failure, or because someone put a
- // thread on the queue, or the queue lock is held. If the queue lock is held, it can only be
- // because someone *will* enqueue a thread onto the queue.
-
- // Acquire the queue lock, or release the lock. This loop handles both lock release in case the
- // fast path's weak CAS spuriously failed and it handles queue lock acquisition if there is
- // actually something interesting on the queue.
+ // 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 (;;) {
- 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.
- std::this_thread::yield();
- continue;
- }
-
- if (currentWordValue & isQueueLockedBit) {
- std::this_thread::yield();
- continue;
- }
-
- // If it wasn't just a spurious weak CAS failure and if the queue lock is not held, then there
- // must be an entry on the queue.
- ASSERT(currentWordValue & ~queueHeadMask);
-
- if (m_word.compareExchangeWeak(currentWordValue, currentWordValue | isQueueLockedBit))
+ oldByteValue = m_byte.load();
+ if (verbose)
+ dataLog(toString(currentThread(), ": unlocking with ", oldByteValue, "\n"));
+ ASSERT(oldByteValue & isHeldBit);
+ if (m_byte.compareExchangeWeak(oldByteValue, 0))
break;
}
- uintptr_t currentWordValue = m_word.load();
-
- // After we acquire the queue lock, the Lock must still be held and the queue must be
- // non-empty. The queue must be non-empty since only the lockSlow() method could have held the
- // queue lock and if it did then it only releases it after putting something on the queue.
- ASSERT(currentWordValue & isLockedBit);
- ASSERT(currentWordValue & isQueueLockedBit);
- ThreadData* queueHead = bitwise_cast<ThreadData*>(currentWordValue & ~queueHeadMask);
- ASSERT(queueHead);
+ // 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.
- 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 Lock.
- 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().
- {
- std::unique_lock<std::mutex> locker(queueHead->parkingLock);
- queueHead->shouldPark = false;
- }
- // Doesn't matter if we notify_all() or notify_one() here since the only thread that could be
- // waiting is queueHead.
- queueHead->parkingCondition.notify_one();
-
- // The old queue head can now contend for the lock again. We're done!
+ // 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
Modified: trunk/Source/WTF/wtf/Lock.h (188322 => 188323)
--- trunk/Source/WTF/wtf/Lock.h 2015-08-12 03:41:40 UTC (rev 188322)
+++ trunk/Source/WTF/wtf/Lock.h 2015-08-12 04:20:24 UTC (rev 188323)
@@ -33,108 +33,18 @@
namespace WTF {
-// A Lock is a fully adaptive mutex that gives you the best of SpinLock and Mutex. For small critical
-// sections (that take nanoseconds), it will usually perform within 2x of a SpinLock in both the
-// contended and uncontended case. When using a Mutex, such critical sections take up to 100x longer
-// than Lock in the contended case, or 3x longer than Lock in the uncontended case. For longer
-// critical sections (that take tens of microseconds), it will perform as well as a Mutex and slightly
-// better than a SpinLock. But, crucially, a SpinLock will burn up to 90x more time in the kernel for
-// such critical sections than either Lock or Mutex. Hence, using Lock will make the common case of
-// locking perform close to SpinLock for any critical section that does more than a few nanoseconds of
-// work while being as kind to the scheduler for longer critical sections as a Mutex.
-//
-// Like SpinLock, Lock takes very little memory - just sizeof(void*), though see a detailed caveat
-// below.
-//
-// Generally, you should use Lock instead of SpinLock because while it penalizes you slightly, you
-// make up for it by not wasting CPU cycles in case of contention.
-//
-// The Lock has the following nice properties:
-//
-// - Uncontended fast paths for lock acquisition and lock release that are almost as fast as the
-// uncontended fast paths of a spinlock. The only overhead is that the spinlock will not CAS on
-// release, while Lock will CAS. This overhead *can* slow things down for extremely small critical
-// sections that do little or nothing - it makes them 2x slower since in that case, CAS is the most
-// expensive instruction and having two of them is twice as bad as just having one. However, this
-// lock implementation is still almost 3x faster than a platform mutex in those cases. It's unlikely
-// that you'll encounter no-op critical sections, so usually, this lock is better than a spinlock.
-//
-// - Contended fast path that attempts to spin and yield for some number of times. For critical
-// sections that are held only briefly, this allows Lock to perform almost as well as a SpinLock.
-// SpinLock can still be almost 2x faster than Lock if the critical section is a no-op, but this
-// advantage diminishes as the critical section grows.
-//
-// - Contended slow path that enqueues the contending thread and causes it to wait on a condition
-// variable until the lock is released. This is the only case in which system mutexes and condition
-// variables are used. This case is rare and self-limiting: it will only happen when a lock is held
-// for long enough that spinning some number of times doesn't acquire it. The fact that Lock does
-// this as a fallback when spinning for some number of times fails means that it will burn
-// dramatically fewer CPU cycles - for example with 10 threads on an 8 logical CPU machine acquiring
-// a critical section that takes 50 microseconds, the WTF SpinLock will cause 90x more time to be
-// spent in the kernel than Lock.
-//
-// - Very low memory usage. Each Lock requires only sizeof(void*) memory. When the contended slow
-// path is activated, Lock only relies on each thread having a preallocated thread-specific data
-// structure called ThreadData that, together with the Lock itself, is used to build up a thread
-// queue. So, the total memory usage of all Locks is still bounded by:
-//
-// numberOfLocks * sizeof(void*) + numberOfThreads * sizeof(ThreadData)
-//
-// Where ThreadData is a decently large data structure, but we will only ever have one per thread,
-// regardless of the number of Locks in memory. Another way to view this is that the worst case
-// memory usage per Lock is:
-//
-// sizeof(void*) + numberOfThreads / numberOfLocks * sizeof(ThreadData)
-//
-// So, unless you have a small number of Locks (or, a large number of threads, which is far less
-// likely), the memory usage per-Lock is still going to be somewhere around sizeof(void*).
-//
-// - Barging fast paths. The Lock is tuned for maximum throughput rather than maximum fairness. If
-// a thread releases a Lock that was contended and had a queue of waiting threads, then it will
-// wake up the head of the queue, but it will also mark the lock as being available. This means that
-// some other thread that is just now attempting to acquire the lock may get it before the thread
-// that got woken up. When a thread barges into the lock, the thread that got woken up will simply
-// go back to the end of the queue. The barging behavior ends up being probabilistic on most
-// platforms and even though it may be unfair to some thread at some moment in time, it will rarely
-// have a long streak of unfairness towards any particular thread: eventually each thread waiting on
-// the lock will get to have a turn so long as no thread just holds the lock forever. That said,
-// there *is* a chance of pathologies - users of Lock should not depend on first-in, first-out lock
-// acquisition order under contention. The same caveat is generally true of SpinLock and platform
-// mutexes on some platforms.
+// This is a fully adaptive mutex that only requires 1 byte of storage. It has fast paths that are
+// competetive to SpinLock (uncontended locking is inlined and is just a CAS, microcontention is
+// handled by spinning and yielding), and a slow path that is competetive to Mutex (if a lock cannot
+// be acquired in a short period of time, the thread is put to sleep until the lock is available
+// again). It uses less memory than either SpinLock or Mutex.
-// 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 {
void lock()
{
- if (LIKELY(m_word.compareExchangeWeak(0, isLockedBit, std::memory_order_acquire))) {
+ if (LIKELY(m_byte.compareExchangeWeak(0, isHeldBit, std::memory_order_acquire))) {
// Lock acquired!
return;
}
@@ -144,8 +54,8 @@
void unlock()
{
- if (LIKELY(m_word.compareExchangeWeak(isLockedBit, 0, std::memory_order_release))) {
- // Lock released, and nobody was waiting!
+ if (LIKELY(m_byte.compareExchangeWeak(isHeldBit, 0, std::memory_order_release))) {
+ // Lock released and nobody was waiting!
return;
}
@@ -154,7 +64,7 @@
bool isHeld() const
{
- return m_word.load(std::memory_order_acquire) & isLockedBit;
+ return m_byte.load(std::memory_order_acquire) & isHeldBit;
}
bool isLocked() const
@@ -163,14 +73,13 @@
}
protected:
- static const uintptr_t isLockedBit = 1;
- static const uintptr_t isQueueLockedBit = 2;
- static const uintptr_t queueHeadMask = 3;
+ static const uint8_t isHeldBit = 1;
+ static const uint8_t hasParkedBit = 2;
WTF_EXPORT_PRIVATE void lockSlow();
WTF_EXPORT_PRIVATE void unlockSlow();
- Atomic<uintptr_t> m_word;
+ Atomic<uint8_t> m_byte;
};
class Lock : public LockBase {
@@ -178,7 +87,7 @@
public:
Lock()
{
- m_word.store(0, std::memory_order_relaxed);
+ m_byte.store(0, std::memory_order_relaxed);
}
};
Modified: trunk/Source/WTF/wtf/ParkingLot.cpp (188322 => 188323)
--- trunk/Source/WTF/wtf/ParkingLot.cpp 2015-08-12 03:41:40 UTC (rev 188322)
+++ trunk/Source/WTF/wtf/ParkingLot.cpp 2015-08-12 04:20:24 UTC (rev 188323)
@@ -28,11 +28,11 @@
#include "DataLog.h"
#include "HashFunctions.h"
-#include "Lock.h"
#include "StringPrintStream.h"
#include "ThreadSpecific.h"
#include "ThreadingPrimitives.h"
#include "Vector.h"
+#include "WordLock.h"
#include <condition_variable>
#include <mutex>
#include <thread>
@@ -170,7 +170,7 @@
// This lock protects the entire bucket. Thou shall not make changes to Bucket without holding
// this lock.
- Lock lock;
+ WordLock lock;
// Put some distane between buckets in memory. This is one of several mitigations against false
// sharing.
Added: trunk/Source/WTF/wtf/WordLock.cpp (0 => 188323)
--- trunk/Source/WTF/wtf/WordLock.cpp (rev 0)
+++ trunk/Source/WTF/wtf/WordLock.cpp 2015-08-12 04:20:24 UTC (rev 188323)
@@ -0,0 +1,269 @@
+/*
+ * 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 "WordLock.h"
+
+#include "DataLog.h"
+#include "StringPrintStream.h"
+#include "ThreadSpecific.h"
+#include "ThreadingPrimitives.h"
+#include <condition_variable>
+#include <mutex>
+#include <thread>
+
+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 };
+};
+
+ThreadSpecific<ThreadData>* threadData;
+
+ThreadData* myThreadData()
+{
+ static std::once_flag initializeOnce;
+ std::call_once(
+ initializeOnce,
+ [] {
+ threadData = new ThreadSpecific<ThreadData>();
+ });
+
+ return *threadData;
+}
+
+} // anonymous namespace
+
+void WordLock::lockSlow()
+{
+ unsigned spinCount = 0;
+
+ // This magic number turns out to be optimal based on past JikesRVM experiments.
+ const unsigned spinLimit = 40;
+
+ for (;;) {
+ uintptr_t currentWordValue = m_word.load();
+
+ if (!(currentWordValue & isLockedBit)) {
+ // It's not possible for someone to hold the queue lock while the lock itself is no longer
+ // held, since we will only attempt to acquire the queue lock when the lock is held and
+ // the queue lock prevents unlock.
+ ASSERT(!(currentWordValue & isQueueLockedBit));
+ if (m_word.compareExchangeWeak(currentWordValue, currentWordValue | isLockedBit)) {
+ // Success! We acquired the lock.
+ return;
+ }
+ }
+
+ // If there is no queue and we haven't spun too much, we can just try to spin around again.
+ if (!(currentWordValue & ~queueHeadMask) && spinCount < spinLimit) {
+ spinCount++;
+ std::this_thread::yield();
+ continue;
+ }
+
+ // Need to put ourselves on the queue. Create the queue if one does not exist. This requries
+ // owning the queue for a little bit. The lock that controls the queue is itself a spinlock.
+ // But before we acquire the queue spinlock, we make sure that we have a ThreadData for this
+ // thread.
+ ThreadData* me = myThreadData();
+ ASSERT(!me->shouldPark);
+ ASSERT(!me->nextInQueue);
+ ASSERT(!me->queueTail);
+
+ // 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)) {
+ std::this_thread::yield();
+ continue;
+ }
+
+ me->shouldPark = true;
+
+ // We own the queue. Nobody can enqueue or dequeue until we're done. Also, it's not possible
+ // to release the WordLock while we hold the queue lock.
+ ThreadData* queueHead = bitwise_cast<ThreadData*>(currentWordValue & ~queueHeadMask);
+ if (queueHead) {
+ // Put this thread at the end of the queue.
+ queueHead->queueTail->nextInQueue = me;
+ queueHead->queueTail = me;
+
+ // Release the queue lock.
+ currentWordValue = m_word.load();
+ ASSERT(currentWordValue & ~queueHeadMask);
+ ASSERT(currentWordValue & isQueueLockedBit);
+ ASSERT(currentWordValue & isLockedBit);
+ m_word.store(currentWordValue & ~isQueueLockedBit);
+ } else {
+ // Make this thread be the queue-head.
+ queueHead = me;
+ me->queueTail = me;
+
+ // Release the queue lock and install ourselves as the head. No need for a CAS loop, since
+ // we own the queue lock.
+ currentWordValue = m_word.load();
+ ASSERT(~(currentWordValue & ~queueHeadMask));
+ ASSERT(currentWordValue & isQueueLockedBit);
+ ASSERT(currentWordValue & isLockedBit);
+ uintptr_t newWordValue = currentWordValue;
+ newWordValue |= bitwise_cast<uintptr_t>(queueHead);
+ newWordValue &= ~isQueueLockedBit;
+ m_word.store(newWordValue);
+ }
+
+ // At this point everyone who acquires the queue lock will see me on the queue, and anyone who
+ // acquires me's lock will see that me wants to park. Note that shouldPark may have been
+ // cleared as soon as the queue lock was released above, but it will happen while the
+ // releasing thread holds me's parkingLock.
+
+ {
+ std::unique_lock<std::mutex> locker(me->parkingLock);
+ while (me->shouldPark)
+ me->parkingCondition.wait(locker);
+ }
+
+ ASSERT(!me->shouldPark);
+ ASSERT(!me->nextInQueue);
+ ASSERT(!me->queueTail);
+
+ // Now we can loop around and try to acquire the lock again.
+ }
+}
+
+void WordLock::unlockSlow()
+{
+ // The fast path can fail either because of spurious weak CAS failure, or because someone put a
+ // thread on the queue, or the queue lock is held. If the queue lock is held, it can only be
+ // because someone *will* enqueue a thread onto the queue.
+
+ // Acquire the queue lock, or release the lock. This loop handles both lock release in case the
+ // fast path's weak CAS spuriously failed and it handles queue lock acquisition if there is
+ // actually something interesting on the queue.
+ for (;;) {
+ uintptr_t currentWordValue = m_word.load();
+
+ ASSERT(currentWordValue & isLockedBit);
+
+ if (currentWordValue == isLockedBit) {
+ if (m_word.compareExchangeWeak(isLockedBit, 0)) {
+ // The fast path's weak CAS had spuriously failed, and now we succeeded. The lock is
+ // unlocked and we're done!
+ return;
+ }
+ // Loop around and try again.
+ std::this_thread::yield();
+ continue;
+ }
+
+ if (currentWordValue & isQueueLockedBit) {
+ std::this_thread::yield();
+ continue;
+ }
+
+ // If it wasn't just a spurious weak CAS failure and if the queue lock is not held, then there
+ // must be an entry on the queue.
+ ASSERT(currentWordValue & ~queueHeadMask);
+
+ if (m_word.compareExchangeWeak(currentWordValue, currentWordValue | isQueueLockedBit))
+ break;
+ }
+
+ uintptr_t currentWordValue = m_word.load();
+
+ // After we acquire the queue lock, the WordLock must still be held and the queue must be
+ // non-empty. The queue must be non-empty since only the lockSlow() method could have held the
+ // queue lock and if it did then it only releases it after putting something on the queue.
+ ASSERT(currentWordValue & isLockedBit);
+ ASSERT(currentWordValue & isQueueLockedBit);
+ ThreadData* queueHead = bitwise_cast<ThreadData*>(currentWordValue & ~queueHeadMask);
+ ASSERT(queueHead);
+
+ ThreadData* newQueueHead = queueHead->nextInQueue;
+ // Either this was the only thread on the queue, in which case we delete the queue, or there
+ // are still more threads on the queue, in which case we create a new queue head.
+ if (newQueueHead)
+ newQueueHead->queueTail = queueHead->queueTail;
+
+ // Change the queue head, possibly removing it if newQueueHead is null. No need for a CAS loop,
+ // since we hold the queue lock and the lock itself so nothing about the lock can change right
+ // now.
+ currentWordValue = m_word.load();
+ ASSERT(currentWordValue & isLockedBit);
+ ASSERT(currentWordValue & isQueueLockedBit);
+ ASSERT((currentWordValue & ~queueHeadMask) == bitwise_cast<uintptr_t>(queueHead));
+ uintptr_t newWordValue = currentWordValue;
+ newWordValue &= ~isLockedBit; // Release the WordLock.
+ newWordValue &= ~isQueueLockedBit; // Release the queue lock.
+ newWordValue &= queueHeadMask; // Clear out the old queue head.
+ newWordValue |= bitwise_cast<uintptr_t>(newQueueHead); // Install new queue head.
+ m_word.store(newWordValue);
+
+ // Now the lock is available for acquisition. But we just have to wake up the old queue head.
+ // After that, we're done!
+
+ queueHead->nextInQueue = nullptr;
+ queueHead->queueTail = nullptr;
+
+ // We do this carefully because this may run either before or during the parkingLock critical
+ // section in lockSlow().
+ {
+ std::unique_lock<std::mutex> locker(queueHead->parkingLock);
+ queueHead->shouldPark = false;
+ }
+ // Doesn't matter if we notify_all() or notify_one() here since the only thread that could be
+ // waiting is queueHead.
+ queueHead->parkingCondition.notify_one();
+
+ // The old queue head can now contend for the lock again. We're done!
+}
+
+} // namespace WTF
+
Added: trunk/Source/WTF/wtf/WordLock.h (0 => 188323)
--- trunk/Source/WTF/wtf/WordLock.h (rev 0)
+++ trunk/Source/WTF/wtf/WordLock.h 2015-08-12 04:20:24 UTC (rev 188323)
@@ -0,0 +1,98 @@
+/*
+ * 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_WordLock_h
+#define WTF_WordLock_h
+
+#include <wtf/Atomics.h>
+#include <wtf/Compiler.h>
+#include <wtf/Locker.h>
+#include <wtf/Noncopyable.h>
+
+namespace WTF {
+
+// A WordLock is a fully adaptive mutex that uses sizeof(void*) storage. It has a fast path that is
+// similar to SpinLock, and a slow path that is similar to Mutex. In most cases, you should use Lock
+// instead. WordLock sits lower in the stack and is used to implement Lock, so Lock is the main
+// client of WordLock.
+
+class WordLock {
+ WTF_MAKE_NONCOPYABLE(WordLock);
+public:
+ WordLock()
+ {
+ m_word.store(0, std::memory_order_relaxed);
+ }
+
+ void lock()
+ {
+ if (LIKELY(m_word.compareExchangeWeak(0, isLockedBit, std::memory_order_acquire))) {
+ // WordLock acquired!
+ return;
+ }
+
+ lockSlow();
+ }
+
+ void unlock()
+ {
+ if (LIKELY(m_word.compareExchangeWeak(isLockedBit, 0, std::memory_order_release))) {
+ // WordLock released, and nobody was waiting!
+ return;
+ }
+
+ unlockSlow();
+ }
+
+ bool isHeld() const
+ {
+ return m_word.load(std::memory_order_acquire) & isLockedBit;
+ }
+
+ bool isLocked() const
+ {
+ return isHeld();
+ }
+
+private:
+ static const uintptr_t isLockedBit = 1;
+ static const uintptr_t isQueueLockedBit = 2;
+ static const uintptr_t queueHeadMask = 3;
+
+ WTF_EXPORT_PRIVATE void lockSlow();
+ WTF_EXPORT_PRIVATE void unlockSlow();
+
+ Atomic<uintptr_t> m_word;
+};
+
+typedef Locker<WordLock> WordLockHolder;
+
+} // namespace WTF
+
+using WTF::WordLock;
+using WTF::WordLockHolder;
+
+#endif // WTF_WordLock_h
+
Modified: trunk/Tools/ChangeLog (188322 => 188323)
--- trunk/Tools/ChangeLog 2015-08-12 03:41:40 UTC (rev 188322)
+++ trunk/Tools/ChangeLog 2015-08-12 04:20:24 UTC (rev 188323)
@@ -1,3 +1,17 @@
+2015-08-11 Filip Pizlo <[email protected]>
+
+ Always use a byte-sized lock implementation
+ https://bugs.webkit.org/show_bug.cgi?id=147908
+
+ Reviewed by Geoffrey Garen.
+
+ 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):
+
2015-08-11 Alexey Proskuryakov <[email protected]>
Make ASan build not depend on asan.xcconfig
Modified: trunk/Tools/TestWebKitAPI/Tests/WTF/Lock.cpp (188322 => 188323)
--- trunk/Tools/TestWebKitAPI/Tests/WTF/Lock.cpp 2015-08-12 03:41:40 UTC (rev 188322)
+++ trunk/Tools/TestWebKitAPI/Tests/WTF/Lock.cpp 2015-08-12 04:20:24 UTC (rev 188323)
@@ -24,10 +24,10 @@
*/
#include "config.h"
-#include <wtf/ByteLock.h>
#include <wtf/Lock.h>
#include <wtf/Threading.h>
#include <wtf/ThreadingPrimitives.h>
+#include <wtf/WordLock.h>
using namespace WTF;
@@ -68,69 +68,69 @@
EXPECT_EQ(expected, words[threadGroupIndex]);
}
-TEST(WTF_Lock, UncontendedShortSection)
+TEST(WTF_WordLock, UncontendedShortSection)
{
- runLockTest<Lock>(1, 1, 1, 10000000);
+ runLockTest<WordLock>(1, 1, 1, 10000000);
}
-TEST(WTF_Lock, UncontendedLongSection)
+TEST(WTF_WordLock, UncontendedLongSection)
{
- runLockTest<Lock>(1, 1, 10000, 1000);
+ runLockTest<WordLock>(1, 1, 10000, 1000);
}
-TEST(WTF_Lock, ContendedShortSection)
+TEST(WTF_WordLock, ContendedShortSection)
{
- runLockTest<Lock>(1, 10, 1, 10000000);
+ runLockTest<WordLock>(1, 10, 1, 10000000);
}
-TEST(WTF_Lock, ContendedLongSection)
+TEST(WTF_WordLock, ContendedLongSection)
{
- runLockTest<Lock>(1, 10, 10000, 10000);
+ runLockTest<WordLock>(1, 10, 10000, 10000);
}
-TEST(WTF_Lock, ManyContendedShortSections)
+TEST(WTF_WordLock, ManyContendedShortSections)
{
- runLockTest<Lock>(10, 10, 1, 500000);
+ runLockTest<WordLock>(10, 10, 1, 500000);
}
-TEST(WTF_Lock, ManyContendedLongSections)
+TEST(WTF_WordLock, ManyContendedLongSections)
{
- runLockTest<Lock>(10, 10, 10000, 1000);
+ runLockTest<WordLock>(10, 10, 10000, 1000);
}
-TEST(WTF_ByteLock, UncontendedShortSection)
+TEST(WTF_Lock, UncontendedShortSection)
{
- runLockTest<ByteLock>(1, 1, 1, 10000000);
+ runLockTest<Lock>(1, 1, 1, 10000000);
}
-TEST(WTF_ByteLock, UncontendedLongSection)
+TEST(WTF_Lock, UncontendedLongSection)
{
- runLockTest<ByteLock>(1, 1, 10000, 1000);
+ runLockTest<Lock>(1, 1, 10000, 1000);
}
-TEST(WTF_ByteLock, ContendedShortSection)
+TEST(WTF_Lock, ContendedShortSection)
{
- runLockTest<ByteLock>(1, 10, 1, 10000000);
+ runLockTest<Lock>(1, 10, 1, 10000000);
}
-TEST(WTF_ByteLock, ContendedLongSection)
+TEST(WTF_Lock, ContendedLongSection)
{
- runLockTest<ByteLock>(1, 10, 10000, 10000);
+ runLockTest<Lock>(1, 10, 10000, 10000);
}
-TEST(WTF_ByteLock, ManyContendedShortSections)
+TEST(WTF_Lock, ManyContendedShortSections)
{
- runLockTest<ByteLock>(10, 10, 1, 500000);
+ runLockTest<Lock>(10, 10, 1, 500000);
}
-TEST(WTF_ByteLock, ManyContendedLongSections)
+TEST(WTF_Lock, ManyContendedLongSections)
{
- runLockTest<ByteLock>(10, 10, 10000, 1000);
+ runLockTest<Lock>(10, 10, 10000, 1000);
}
-TEST(WTF_ByteLock, SectionAddressCollision)
+TEST(WTF_Lock, SectionAddressCollision)
{
- runLockTest<ByteLock>(4, 2, 10000, 2000);
+ runLockTest<Lock>(4, 2, 10000, 2000);
}
} // namespace TestWebKitAPI
