Always use a byte-sized lock implementation
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 12 Aug 2015 04:20:24 +0000 (04:20 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Wed, 12 Aug 2015 04:20:24 +0000 (04:20 +0000)
https://bugs.webkit.org/show_bug.cgi?id=147908

Reviewed by Geoffrey Garen.

Source/JavaScriptCore:

* runtime/ConcurrentJITLock.h: Lock is now byte-sized and ByteLock is gone, so use Lock.

Source/WTF:

At the start of my locking algorithm crusade, I implemented Lock, which is a sizeof(void*)
lock implementation with some nice theoretical properties and good performance. Then I added
the ParkingLot abstraction and ByteLock. ParkingLot uses Lock in its implementation.
ByteLock uses ParkingLot to create a sizeof(char) lock implementation that performs like
Lock.

It turns out that ByteLock is always at least as good as Lock, and sometimes a lot better:
it requires 8x less memory on 64-bit systems. It's hard to construct a benchmark where
ByteLock is significantly slower than Lock, and when you do construct such a benchmark,
tweaking it a bit can also create a scenario where ByteLock is significantly faster than
Lock.

So, the thing that we call "Lock" should really use ByteLock's algorithm, since it is more
compact and just as fast. That's what this patch does.

But we still need to keep the old Lock algorithm, because it's used to implement ParkingLot,
which in turn is used to implement ByteLock. So this patch does this transformation:

- Move the algorithm in Lock into files called WordLock.h|cpp. Make ParkingLot use
  WordLock.

- Move the algorithm in ByteLock into Lock.h|cpp. Make everyone who used ByteLock use Lock
  instead. All other users of Lock now get the byte-sized lock implementation.

- Remove the old ByteLock files.

* WTF.vcxproj/WTF.vcxproj:
* WTF.xcodeproj/project.pbxproj:
* benchmarks/LockSpeedTest.cpp:
(main):
* wtf/WordLock.cpp: Added.
(WTF::WordLock::lockSlow):
(WTF::WordLock::unlockSlow):
* wtf/WordLock.h: Added.
(WTF::WordLock::WordLock):
(WTF::WordLock::lock):
(WTF::WordLock::unlock):
(WTF::WordLock::isHeld):
(WTF::WordLock::isLocked):
* wtf/ByteLock.cpp: Removed.
* wtf/ByteLock.h: Removed.
* wtf/CMakeLists.txt:
* wtf/Lock.cpp:
(WTF::LockBase::lockSlow):
(WTF::LockBase::unlockSlow):
* wtf/Lock.h:
(WTF::LockBase::lock):
(WTF::LockBase::unlock):
(WTF::LockBase::isHeld):
(WTF::LockBase::isLocked):
(WTF::Lock::Lock):
* wtf/ParkingLot.cpp:

Tools:

All previous tests of Lock are now tests of WordLock. All previous tests of ByteLock are
now tests of Lock.

* TestWebKitAPI/Tests/WTF/Lock.cpp:
(TestWebKitAPI::runLockTest):
(TestWebKitAPI::TEST):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@188323 268f45cc-cd09-0410-ab3c-d52691b4dbfc

16 files changed:
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/runtime/ConcurrentJITLock.h
Source/WTF/ChangeLog
Source/WTF/WTF.vcxproj/WTF.vcxproj
Source/WTF/WTF.xcodeproj/project.pbxproj
Source/WTF/benchmarks/LockSpeedTest.cpp
Source/WTF/wtf/ByteLock.cpp [deleted file]
Source/WTF/wtf/ByteLock.h [deleted file]
Source/WTF/wtf/CMakeLists.txt
Source/WTF/wtf/Lock.cpp
Source/WTF/wtf/Lock.h
Source/WTF/wtf/ParkingLot.cpp
Source/WTF/wtf/WordLock.cpp [new file with mode: 0644]
Source/WTF/wtf/WordLock.h [new file with mode: 0644]
Tools/ChangeLog
Tools/TestWebKitAPI/Tests/WTF/Lock.cpp

index 3753afb248a670a8622071f19d65d049acf2a71d..d581a774941f6a6e1d4aef21230bdf65b37b7389 100644 (file)
@@ -1,3 +1,12 @@
+2015-08-11  Filip Pizlo  <fpizlo@apple.com>
+
+        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  <ap@apple.com>
 
         Make ASan build not depend on asan.xcconfig
index 4c299f362b54cf77351a93384ac6e41ea5c4b89d..9a26876fcabf17ef3eec0e8c61c7710bd776a490 100644 (file)
 #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;
index cefa6b7102bc1fe08ebb722b5b60be88340d0652..982404d83cb572b4f47919881aa9a181839813af 100644 (file)
@@ -1,3 +1,63 @@
+2015-08-11  Filip Pizlo  <fpizlo@apple.com>
+
+        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  <fpizlo@apple.com>
 
         Remove ByteSpinLock
index 1d739b39c68e2f92b1b2f250f334e7ea6bdc17d2..4c2d7b7858780eb0fc99f820a4d291650c65c154 100644 (file)
@@ -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" />
     <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" />
     <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" />
     <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>
index dbd07ea815454197d22caf7d47fb0513ecd7d701..19c05813903001e24bdabaa6bfec47236e7d5e46 100644 (file)
@@ -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 */; };
                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>"; };
                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>"; };
                                A8A47264151A825A004123FF /* BlockStack.h */,
                                A8A47265151A825A004123FF /* BloomFilter.h */,
                                A8A47267151A825A004123FF /* BumpPointerAllocator.h */,
-                               0F824A621B7443A0002E345D /* ByteLock.cpp */,
-                               0F824A631B7443A0002E345D /* ByteLock.h */,
                                EB95E1EF161A72410089A2F5 /* ByteOrder.h */,
                                A8A4726A151A825A004123FF /* CheckedArithmetic.h */,
                                A8A4726B151A825A004123FF /* CheckedBoolean.h */,
                                A8A47371151A825B004123FF /* VectorTraits.h */,
                                A8A47372151A825B004123FF /* VMTags.h */,
                                974CFC8D16A4F327006D5404 /* WeakPtr.h */,
+                               0FE4479A1B7AAA03009498EB /* WordLock.cpp */,
+                               0FE4479B1B7AAA03009498EB /* WordLock.h */,
                                E4A0AD371A96245500536DF6 /* WorkQueue.cpp */,
                                E4A0AD381A96245500536DF6 /* WorkQueue.h */,
                                A8A4737A151A825B004123FF /* WTFThreadData.cpp */,
                                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 */,
                                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 */,
                        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 */,
                                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 */,
index 3287a95fd759f2dfa2a76c2c84c36ecaf419f3c3..6dcbd63941b0db38a4a4098af9bb9b8357148750 100644 (file)
 #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 @@ unsigned numIterations;
     
 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,12 +122,12 @@ int main(int argc, char** argv)
         runBenchmark<SpinLock>("SpinLock");
         didRun = true;
     }
-    if (!strcmp(argv[1], "lock") || !strcmp(argv[1], "all")) {
-        runBenchmark<Lock>("WTF Lock");
+    if (!strcmp(argv[1], "wordlock") || !strcmp(argv[1], "all")) {
+        runBenchmark<WordLock>("WTF WordLock");
         didRun = true;
     }
-    if (!strcmp(argv[1], "bytelock") || !strcmp(argv[1], "all")) {
-        runBenchmark<ByteLock>("WTF ByteLock");
+    if (!strcmp(argv[1], "lock") || !strcmp(argv[1], "all")) {
+        runBenchmark<Lock>("WTF Lock");
         didRun = true;
     }
     if (!strcmp(argv[1], "mutex") || !strcmp(argv[1], "all")) {
diff --git a/Source/WTF/wtf/ByteLock.cpp b/Source/WTF/wtf/ByteLock.cpp
deleted file mode 100644 (file)
index b23324e..0000000
+++ /dev/null
@@ -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
-
diff --git a/Source/WTF/wtf/ByteLock.h b/Source/WTF/wtf/ByteLock.h
deleted file mode 100644 (file)
index 7de6887..0000000
+++ /dev/null
@@ -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
-
index 51a8d5ec047a69696ca3e93db7c9f370b5585bf1..87cdd5e77ab1e40fee508668fc23912b5b892e21 100644 (file)
@@ -7,7 +7,6 @@ set(WTF_HEADERS
     BitVector.h
     Bitmap.h
     BumpPointerAllocator.h
-    ByteLock.h
     ByteOrder.h
     CompilationThread.h
     Compiler.h
@@ -104,6 +103,7 @@ set(WTF_HEADERS
     VectorTraits.h
     WTFThreadData.h
     WeakPtr.h
+    WordLock.h
     WorkQueue.h
     dtoa.h
 
@@ -146,7 +146,6 @@ set(WTF_SOURCES
     Assertions.cpp
     Atomics.cpp
     BitVector.cpp
-    ByteLock.cpp
     CompilationThread.cpp
     CryptographicUtilities.cpp
     CryptographicallyRandomNumber.cpp
@@ -183,6 +182,7 @@ set(WTF_SOURCES
     StringPrintStream.cpp
     Threading.cpp
     WTFThreadData.cpp
+    WordLock.cpp
     WorkQueue.cpp
     dtoa.cpp
 
index 69d449c9f5314e3f8496f6ac6170f8d49400e7e1..d7c743b220cac9033338aaef7cb30f4a3b15c065 100644 (file)
 #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 {
-
-// 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
+static const bool verbose = false;
 
 void LockBase::lockSlow()
 {
@@ -85,184 +44,62 @@ void LockBase::lockSlow()
     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;
-
-            // 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.
+        // 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);
 
-        {
-            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);
-
-    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!
+    // 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
index d1509c48e07cfbc43d9a4a0362867d438743575f..d4150d2327e8d8e5d9f8fc4787c6415ec4963b45 100644 (file)
 
 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.
-
-// 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 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.
 
 // 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 @@ struct LockBase {
 
     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 @@ struct LockBase {
 
     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 @@ struct LockBase {
     }
 
 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 @@ class Lock : public LockBase {
 public:
     Lock()
     {
-        m_word.store(0, std::memory_order_relaxed);
+        m_byte.store(0, std::memory_order_relaxed);
     }
 };
 
index d5917de7738e2bf54ff38ac1e6df66995810f2fe..c1e558ba197d79ac864ec6f1d496b60347fc954b 100644 (file)
 
 #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 @@ public:
 
     // 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.
diff --git a/Source/WTF/wtf/WordLock.cpp b/Source/WTF/wtf/WordLock.cpp
new file mode 100644 (file)
index 0000000..d53653b
--- /dev/null
@@ -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
+
diff --git a/Source/WTF/wtf/WordLock.h b/Source/WTF/wtf/WordLock.h
new file mode 100644 (file)
index 0000000..8d1b3ec
--- /dev/null
@@ -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
+
index 238437626edcb179fdac105d61aae92ee9ad8e88..7dfa104940505d345c497df6c43b16a703fff1b1 100644 (file)
@@ -1,3 +1,17 @@
+2015-08-11  Filip Pizlo  <fpizlo@apple.com>
+
+        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  <ap@apple.com>
 
         Make ASan build not depend on asan.xcconfig
index d03949e1fec99cc10636f601281674d004e7b903..63b14db7faa39e3b45155de69634f382a8d95319 100644 (file)
  */
 
 #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 @@ void runLockTest(unsigned numThreadGroups, unsigned numThreadsPerGroup, unsigned
         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