<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN"
"http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head><meta http-equiv="content-type" content="text/html; charset=utf-8" />
<title>[188323] trunk</title>
</head>
<body>
<style type="text/css"><!--
#msg dl.meta { border: 1px #006 solid; background: #369; padding: 6px; color: #fff; }
#msg dl.meta dt { float: left; width: 6em; font-weight: bold; }
#msg dt:after { content:':';}
#msg dl, #msg dt, #msg ul, #msg li, #header, #footer, #logmsg { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; }
#msg dl a { font-weight: bold}
#msg dl a:link { color:#fc3; }
#msg dl a:active { color:#ff0; }
#msg dl a:visited { color:#cc6; }
h3 { font-family: verdana,arial,helvetica,sans-serif; font-size: 10pt; font-weight: bold; }
#msg pre { overflow: auto; background: #ffc; border: 1px #fa0 solid; padding: 6px; }
#logmsg { background: #ffc; border: 1px #fa0 solid; padding: 1em 1em 0 1em; }
#logmsg p, #logmsg pre, #logmsg blockquote { margin: 0 0 1em 0; }
#logmsg p, #logmsg li, #logmsg dt, #logmsg dd { line-height: 14pt; }
#logmsg h1, #logmsg h2, #logmsg h3, #logmsg h4, #logmsg h5, #logmsg h6 { margin: .5em 0; }
#logmsg h1:first-child, #logmsg h2:first-child, #logmsg h3:first-child, #logmsg h4:first-child, #logmsg h5:first-child, #logmsg h6:first-child { margin-top: 0; }
#logmsg ul, #logmsg ol { padding: 0; list-style-position: inside; margin: 0 0 0 1em; }
#logmsg ul { text-indent: -1em; padding-left: 1em; }#logmsg ol { text-indent: -1.5em; padding-left: 1.5em; }
#logmsg > ul, #logmsg > ol { margin: 0 0 1em 0; }
#logmsg pre { background: #eee; padding: 1em; }
#logmsg blockquote { border: 1px solid #fa0; border-left-width: 10px; padding: 1em 1em 0 1em; background: white;}
#logmsg dl { margin: 0; }
#logmsg dt { font-weight: bold; }
#logmsg dd { margin: 0; padding: 0 0 0.5em 0; }
#logmsg dd:before { content:'\00bb';}
#logmsg table { border-spacing: 0px; border-collapse: collapse; border-top: 4px solid #fa0; border-bottom: 1px solid #fa0; background: #fff; }
#logmsg table th { text-align: left; font-weight: normal; padding: 0.2em 0.5em; border-top: 1px dotted #fa0; }
#logmsg table td { text-align: right; border-top: 1px dotted #fa0; padding: 0.2em 0.5em; }
#logmsg table thead th { text-align: center; border-bottom: 1px solid #fa0; }
#logmsg table th.Corner { text-align: left; }
#logmsg hr { border: none 0; border-top: 2px dashed #fa0; height: 1px; }
#header, #footer { color: #fff; background: #636; border: 1px #300 solid; padding: 6px; }
#patch { width: 100%; }
#patch h4 {font-family: verdana,arial,helvetica,sans-serif;font-size:10pt;padding:8px;background:#369;color:#fff;margin:0;}
#patch .propset h4, #patch .binary h4 {margin:0;}
#patch pre {padding:0;line-height:1.2em;margin:0;}
#patch .diff {width:100%;background:#eee;padding: 0 0 10px 0;overflow:auto;}
#patch .propset .diff, #patch .binary .diff {padding:10px 0;}
#patch span {display:block;padding:0 10px;}
#patch .modfile, #patch .addfile, #patch .delfile, #patch .propset, #patch .binary, #patch .copfile {border:1px solid #ccc;margin:10px 0;}
#patch ins {background:#dfd;text-decoration:none;display:block;padding:0 10px;}
#patch del {background:#fdd;text-decoration:none;display:block;padding:0 10px;}
#patch .lines, .info {color:#888;background:#fff;}
--></style>
<div id="msg">
<dl class="meta">
<dt>Revision</dt> <dd><a href="http://trac.webkit.org/projects/webkit/changeset/188323">188323</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2015-08-11 21:20:24 -0700 (Tue, 11 Aug 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>Always use a byte-sized lock implementation
https://bugs.webkit.org/show_bug.cgi?id=147908
Reviewed by Geoffrey Garen.
Source/JavaScriptCore:
* runtime/ConcurrentJITLock.h: Lock is now byte-sized and ByteLock is gone, so use Lock.
Source/WTF:
At the start of my locking algorithm crusade, I implemented Lock, which is a sizeof(void*)
lock implementation with some nice theoretical properties and good performance. Then I added
the ParkingLot abstraction and ByteLock. ParkingLot uses Lock in its implementation.
ByteLock uses ParkingLot to create a sizeof(char) lock implementation that performs like
Lock.
It turns out that ByteLock is always at least as good as Lock, and sometimes a lot better:
it requires 8x less memory on 64-bit systems. It's hard to construct a benchmark where
ByteLock is significantly slower than Lock, and when you do construct such a benchmark,
tweaking it a bit can also create a scenario where ByteLock is significantly faster than
Lock.
So, the thing that we call "Lock" should really use ByteLock's algorithm, since it is more
compact and just as fast. That's what this patch does.
But we still need to keep the old Lock algorithm, because it's used to implement ParkingLot,
which in turn is used to implement ByteLock. So this patch does this transformation:
- Move the algorithm in Lock into files called WordLock.h|cpp. Make ParkingLot use
WordLock.
- Move the algorithm in ByteLock into Lock.h|cpp. Make everyone who used ByteLock use Lock
instead. All other users of Lock now get the byte-sized lock implementation.
- Remove the old ByteLock files.
* WTF.vcxproj/WTF.vcxproj:
* WTF.xcodeproj/project.pbxproj:
* benchmarks/LockSpeedTest.cpp:
(main):
* wtf/WordLock.cpp: Added.
(WTF::WordLock::lockSlow):
(WTF::WordLock::unlockSlow):
* wtf/WordLock.h: Added.
(WTF::WordLock::WordLock):
(WTF::WordLock::lock):
(WTF::WordLock::unlock):
(WTF::WordLock::isHeld):
(WTF::WordLock::isLocked):
* wtf/ByteLock.cpp: Removed.
* wtf/ByteLock.h: Removed.
* wtf/CMakeLists.txt:
* wtf/Lock.cpp:
(WTF::LockBase::lockSlow):
(WTF::LockBase::unlockSlow):
* wtf/Lock.h:
(WTF::LockBase::lock):
(WTF::LockBase::unlock):
(WTF::LockBase::isHeld):
(WTF::LockBase::isLocked):
(WTF::Lock::Lock):
* wtf/ParkingLot.cpp:
Tools:
All previous tests of Lock are now tests of WordLock. All previous tests of ByteLock are
now tests of Lock.
* TestWebKitAPI/Tests/WTF/Lock.cpp:
(TestWebKitAPI::runLockTest):
(TestWebKitAPI::TEST):</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceJavaScriptCoreChangeLog">trunk/Source/JavaScriptCore/ChangeLog</a></li>
<li><a href="#trunkSourceJavaScriptCoreruntimeConcurrentJITLockh">trunk/Source/JavaScriptCore/runtime/ConcurrentJITLock.h</a></li>
<li><a href="#trunkSourceWTFChangeLog">trunk/Source/WTF/ChangeLog</a></li>
<li><a href="#trunkSourceWTFWTFvcxprojWTFvcxproj">trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj</a></li>
<li><a href="#trunkSourceWTFWTFxcodeprojprojectpbxproj">trunk/Source/WTF/WTF.xcodeproj/project.pbxproj</a></li>
<li><a href="#trunkSourceWTFbenchmarksLockSpeedTestcpp">trunk/Source/WTF/benchmarks/LockSpeedTest.cpp</a></li>
<li><a href="#trunkSourceWTFwtfCMakeListstxt">trunk/Source/WTF/wtf/CMakeLists.txt</a></li>
<li><a href="#trunkSourceWTFwtfLockcpp">trunk/Source/WTF/wtf/Lock.cpp</a></li>
<li><a href="#trunkSourceWTFwtfLockh">trunk/Source/WTF/wtf/Lock.h</a></li>
<li><a href="#trunkSourceWTFwtfParkingLotcpp">trunk/Source/WTF/wtf/ParkingLot.cpp</a></li>
<li><a href="#trunkToolsChangeLog">trunk/Tools/ChangeLog</a></li>
<li><a href="#trunkToolsTestWebKitAPITestsWTFLockcpp">trunk/Tools/TestWebKitAPI/Tests/WTF/Lock.cpp</a></li>
</ul>
<h3>Added Paths</h3>
<ul>
<li><a href="#trunkSourceWTFwtfWordLockcpp">trunk/Source/WTF/wtf/WordLock.cpp</a></li>
<li><a href="#trunkSourceWTFwtfWordLockh">trunk/Source/WTF/wtf/WordLock.h</a></li>
</ul>
<h3>Removed Paths</h3>
<ul>
<li><a href="#trunkSourceWTFwtfByteLockcpp">trunk/Source/WTF/wtf/ByteLock.cpp</a></li>
<li><a href="#trunkSourceWTFwtfByteLockh">trunk/Source/WTF/wtf/ByteLock.h</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (188322 => 188323)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2015-08-12 03:41:40 UTC (rev 188322)
+++ trunk/Source/JavaScriptCore/ChangeLog 2015-08-12 04:20:24 UTC (rev 188323)
</span><span class="lines">@@ -1,3 +1,12 @@
</span><ins>+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.
+
</ins><span class="cx"> 2015-08-11 Alexey Proskuryakov <ap@apple.com>
</span><span class="cx">
</span><span class="cx"> Make ASan build not depend on asan.xcconfig
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreruntimeConcurrentJITLockh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/runtime/ConcurrentJITLock.h (188322 => 188323)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/runtime/ConcurrentJITLock.h 2015-08-12 03:41:40 UTC (rev 188322)
+++ trunk/Source/JavaScriptCore/runtime/ConcurrentJITLock.h 2015-08-12 04:20:24 UTC (rev 188323)
</span><span class="lines">@@ -27,14 +27,14 @@
</span><span class="cx"> #define ConcurrentJITLock_h
</span><span class="cx">
</span><span class="cx"> #include "DeferGC.h"
</span><del>-#include <wtf/ByteLock.h>
</del><ins>+#include <wtf/Lock.h>
</ins><span class="cx"> #include <wtf/NoLock.h>
</span><span class="cx">
</span><span class="cx"> namespace JSC {
</span><span class="cx">
</span><span class="cx"> #if ENABLE(CONCURRENT_JIT)
</span><del>-typedef ByteLock ConcurrentJITLock;
-typedef ByteLocker ConcurrentJITLockerImpl;
</del><ins>+typedef Lock ConcurrentJITLock;
+typedef LockHolder ConcurrentJITLockerImpl;
</ins><span class="cx"> #else
</span><span class="cx"> typedef NoLock ConcurrentJITLock;
</span><span class="cx"> typedef NoLockLocker ConcurrentJITLockerImpl;
</span></span></pre></div>
<a id="trunkSourceWTFChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/ChangeLog (188322 => 188323)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -1,5 +1,65 @@
</span><span class="cx"> 2015-08-11 Filip Pizlo <fpizlo@apple.com>
</span><span class="cx">
</span><ins>+ 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>
+
</ins><span class="cx"> Remove ByteSpinLock
</span><span class="cx"> https://bugs.webkit.org/show_bug.cgi?id=147900
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWTFWTFvcxprojWTFvcxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj (188322 => 188323)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -1,4 +1,4 @@
</span><del>-<?xml version="1.0" encoding="utf-8"?>
</del><ins>+<?xml version="1.0" encoding="utf-8"?>
</ins><span class="cx"> <Project DefaultTargets="Build" ToolsVersion="14.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
</span><span class="cx"> <ItemGroup Label="ProjectConfigurations">
</span><span class="cx"> <ProjectConfiguration Include="DebugSuffix|Win32">
</span><span class="lines">@@ -53,7 +53,6 @@
</span><span class="cx"> <ItemGroup>
</span><span class="cx"> <ClCompile Include="..\wtf\Assertions.cpp" />
</span><span class="cx"> <ClCompile Include="..\wtf\BitVector.cpp" />
</span><del>- <ClCompile Include="..\wtf\ByteLock.cpp" />
</del><span class="cx"> <ClCompile Include="..\wtf\CompilationThread.cpp" />
</span><span class="cx"> <ClCompile Include="..\wtf\CryptographicUtilities.cpp" />
</span><span class="cx"> <ClCompile Include="..\wtf\CryptographicallyRandomNumber.cpp" />
</span><span class="lines">@@ -155,6 +154,7 @@
</span><span class="cx"> <ClCompile Include="..\wtf\win\WorkItemWin.cpp" />
</span><span class="cx"> <ClCompile Include="..\wtf\win\WorkQueueWin.cpp" />
</span><span class="cx"> <ClCompile Include="..\wtf\win\WTFDLL.cpp" />
</span><ins>+ <ClCompile Include="..\wtf\WordLock.cpp" />
</ins><span class="cx"> <ClCompile Include="..\wtf\WorkQueue.cpp" />
</span><span class="cx"> <ClCompile Include="..\wtf\WTFThreadData.cpp" />
</span><span class="cx"> <ClCompile Include="..\wtf\SchedulePairCF.cpp" />
</span><span class="lines">@@ -173,7 +173,6 @@
</span><span class="cx"> <ClInclude Include="..\wtf\BlockStack.h" />
</span><span class="cx"> <ClInclude Include="..\wtf\BloomFilter.h" />
</span><span class="cx"> <ClInclude Include="..\wtf\BumpPointerAllocator.h" />
</span><del>- <ClInclude Include="..\wtf\ByteLock.h" />
</del><span class="cx"> <ClInclude Include="..\wtf\CheckedArithmetic.h" />
</span><span class="cx"> <ClInclude Include="..\wtf\CheckedBoolean.h" />
</span><span class="cx"> <ClInclude Include="..\wtf\Compiler.h" />
</span><span class="lines">@@ -314,6 +313,7 @@
</span><span class="cx"> <ClInclude Include="..\wtf\VMTags.h" />
</span><span class="cx"> <ClInclude Include="..\wtf\win\GDIObject.h" />
</span><span class="cx"> <ClInclude Include="..\wtf\win\WorkItemWin.h" />
</span><ins>+ <ClInclude Include="..\wtf\WordLock.h" />
</ins><span class="cx"> <ClInclude Include="..\wtf\WorkQueue.h" />
</span><span class="cx"> <ClInclude Include="..\wtf\WTFThreadData.h" />
</span><span class="cx"> </ItemGroup>
</span></span></pre></div>
<a id="trunkSourceWTFWTFxcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (188322 => 188323)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -24,8 +24,6 @@
</span><span class="cx"> 0F0D85B417234CC100338210 /* NoLock.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F0D85B317234CB100338210 /* NoLock.h */; };
</span><span class="cx"> 0F2B66A617B6B4FB00A7AE3F /* DeferrableRefCounted.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F2B66A417B6B4F700A7AE3F /* DeferrableRefCounted.h */; };
</span><span class="cx"> 0F2B66A717B6B4FD00A7AE3F /* FlipBytes.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F2B66A517B6B4F700A7AE3F /* FlipBytes.h */; };
</span><del>- 0F824A661B7443A0002E345D /* ByteLock.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F824A621B7443A0002E345D /* ByteLock.cpp */; };
- 0F824A671B7443A0002E345D /* ByteLock.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F824A631B7443A0002E345D /* ByteLock.h */; };
</del><span class="cx"> 0F824A681B7443A0002E345D /* ParkingLot.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F824A641B7443A0002E345D /* ParkingLot.cpp */; };
</span><span class="cx"> 0F824A691B7443A0002E345D /* ParkingLot.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F824A651B7443A0002E345D /* ParkingLot.h */; };
</span><span class="cx"> 0F87105A16643F190090B0AD /* RawPointer.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F87105916643F190090B0AD /* RawPointer.h */; };
</span><span class="lines">@@ -46,6 +44,8 @@
</span><span class="cx"> 0FDDBFA81666DFA300C55FEF /* StringPrintStream.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FDDBFA61666DFA300C55FEF /* StringPrintStream.h */; };
</span><span class="cx"> 0FE1646A1B6FFC9600400E7C /* Lock.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FE164681B6FFC9600400E7C /* Lock.cpp */; };
</span><span class="cx"> 0FE1646B1B6FFC9600400E7C /* Lock.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FE164691B6FFC9600400E7C /* Lock.h */; };
</span><ins>+ 0FE4479C1B7AAA03009498EB /* WordLock.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FE4479A1B7AAA03009498EB /* WordLock.cpp */; };
+ 0FE4479D1B7AAA03009498EB /* WordLock.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FE4479B1B7AAA03009498EB /* WordLock.h */; };
</ins><span class="cx"> 0FED67B61B22D4D80066CE15 /* TinyPtrSet.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FED67B51B22D4D80066CE15 /* TinyPtrSet.h */; };
</span><span class="cx"> 14022F4118F5C3FC007FF0EB /* libbmalloc.a in Frameworks */ = {isa = PBXBuildFile; fileRef = 14022F4018F5C3FC007FF0EB /* libbmalloc.a */; };
</span><span class="cx"> 143F611F1565F0F900DB514A /* RAMSize.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 143F611D1565F0F900DB514A /* RAMSize.cpp */; };
</span><span class="lines">@@ -311,8 +311,6 @@
</span><span class="cx"> 0F2B66A417B6B4F700A7AE3F /* DeferrableRefCounted.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = DeferrableRefCounted.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F2B66A517B6B4F700A7AE3F /* FlipBytes.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = FlipBytes.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F300B7D18AB48B400A6D72E /* HashMethod.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = HashMethod.h; sourceTree = "<group>"; };
</span><del>- 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>"; };
</del><span class="cx"> 0F824A641B7443A0002E345D /* ParkingLot.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ParkingLot.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 0F824A651B7443A0002E345D /* ParkingLot.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ParkingLot.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F87105916643F190090B0AD /* RawPointer.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RawPointer.h; sourceTree = "<group>"; };
</span><span class="lines">@@ -333,6 +331,8 @@
</span><span class="cx"> 0FDDBFA61666DFA300C55FEF /* StringPrintStream.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = StringPrintStream.h; sourceTree = "<group>"; };
</span><span class="cx"> 0FE164681B6FFC9600400E7C /* Lock.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Lock.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 0FE164691B6FFC9600400E7C /* Lock.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Lock.h; sourceTree = "<group>"; };
</span><ins>+ 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>"; };
</ins><span class="cx"> 0FED67B51B22D4D80066CE15 /* TinyPtrSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = TinyPtrSet.h; sourceTree = "<group>"; };
</span><span class="cx"> 14022F4018F5C3FC007FF0EB /* libbmalloc.a */ = {isa = PBXFileReference; lastKnownFileType = archive.ar; path = libbmalloc.a; sourceTree = BUILT_PRODUCTS_DIR; };
</span><span class="cx"> 143F611D1565F0F900DB514A /* RAMSize.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = RAMSize.cpp; sourceTree = "<group>"; };
</span><span class="lines">@@ -723,8 +723,6 @@
</span><span class="cx"> A8A47264151A825A004123FF /* BlockStack.h */,
</span><span class="cx"> A8A47265151A825A004123FF /* BloomFilter.h */,
</span><span class="cx"> A8A47267151A825A004123FF /* BumpPointerAllocator.h */,
</span><del>- 0F824A621B7443A0002E345D /* ByteLock.cpp */,
- 0F824A631B7443A0002E345D /* ByteLock.h */,
</del><span class="cx"> EB95E1EF161A72410089A2F5 /* ByteOrder.h */,
</span><span class="cx"> A8A4726A151A825A004123FF /* CheckedArithmetic.h */,
</span><span class="cx"> A8A4726B151A825A004123FF /* CheckedBoolean.h */,
</span><span class="lines">@@ -892,6 +890,8 @@
</span><span class="cx"> A8A47371151A825B004123FF /* VectorTraits.h */,
</span><span class="cx"> A8A47372151A825B004123FF /* VMTags.h */,
</span><span class="cx"> 974CFC8D16A4F327006D5404 /* WeakPtr.h */,
</span><ins>+ 0FE4479A1B7AAA03009498EB /* WordLock.cpp */,
+ 0FE4479B1B7AAA03009498EB /* WordLock.h */,
</ins><span class="cx"> E4A0AD371A96245500536DF6 /* WorkQueue.cpp */,
</span><span class="cx"> E4A0AD381A96245500536DF6 /* WorkQueue.h */,
</span><span class="cx"> A8A4737A151A825B004123FF /* WTFThreadData.cpp */,
</span><span class="lines">@@ -1166,7 +1166,6 @@
</span><span class="cx"> A8A47415151A825B004123FF /* RandomNumber.h in Headers */,
</span><span class="cx"> A8A47416151A825B004123FF /* RandomNumberSeed.h in Headers */,
</span><span class="cx"> 0F87105A16643F190090B0AD /* RawPointer.h in Headers */,
</span><del>- 0F824A671B7443A0002E345D /* ByteLock.h in Headers */,
</del><span class="cx"> A8A47417151A825B004123FF /* RedBlackTree.h in Headers */,
</span><span class="cx"> A8A47418151A825B004123FF /* RefCounted.h in Headers */,
</span><span class="cx"> A8A47419151A825B004123FF /* RefCountedArray.h in Headers */,
</span><span class="lines">@@ -1220,6 +1219,7 @@
</span><span class="cx"> A8A47454151A825B004123FF /* ThreadSafeRefCounted.h in Headers */,
</span><span class="cx"> A8A47455151A825B004123FF /* ThreadSpecific.h in Headers */,
</span><span class="cx"> 149EF16316BBFE0D000A4331 /* TriState.h in Headers */,
</span><ins>+ 0FE4479D1B7AAA03009498EB /* WordLock.h in Headers */,
</ins><span class="cx"> A8A4746D151A825B004123FF /* UnionFind.h in Headers */,
</span><span class="cx"> A8A4746A151A825B004123FF /* UTF8.h in Headers */,
</span><span class="cx"> A8A473B9151A825B004123FF /* utils.h in Headers */,
</span><span class="lines">@@ -1337,7 +1337,6 @@
</span><span class="cx"> files = (
</span><span class="cx"> A8A47386151A825B004123FF /* Assertions.cpp in Sources */,
</span><span class="cx"> A8A47435151A825B004123FF /* AtomicString.cpp in Sources */,
</span><del>- 0F824A661B7443A0002E345D /* ByteLock.cpp in Sources */,
</del><span class="cx"> 9BC70F05176C379D00101DEC /* AtomicStringTable.cpp in Sources */,
</span><span class="cx"> A5BA15FB182435A600A82E69 /* StringCF.cpp in Sources */,
</span><span class="cx"> 1469419D16EAB10A0024E146 /* AutodrainedPoolMac.mm in Sources */,
</span><span class="lines">@@ -1400,6 +1399,7 @@
</span><span class="cx"> 70ECA60D1B02426800449739 /* AtomicStringImpl.cpp in Sources */,
</span><span class="cx"> FEDACD3D1630F83F00C69634 /* StackStats.cpp in Sources */,
</span><span class="cx"> A8A4743C151A825B004123FF /* StringBuilder.cpp in Sources */,
</span><ins>+ 0FE4479C1B7AAA03009498EB /* WordLock.cpp in Sources */,
</ins><span class="cx"> A8A47440151A825B004123FF /* StringImpl.cpp in Sources */,
</span><span class="cx"> A5BA15FC182435A600A82E69 /* StringImplCF.cpp in Sources */,
</span><span class="cx"> A5BA15F51824348000A82E69 /* StringImplMac.mm in Sources */,
</span></span></pre></div>
<a id="trunkSourceWTFbenchmarksLockSpeedTestcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/benchmarks/LockSpeedTest.cpp (188322 => 188323)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -26,13 +26,13 @@
</span><span class="cx"> #include "config.h"
</span><span class="cx">
</span><span class="cx"> #include <unistd.h>
</span><del>-#include <wtf/ByteLock.h>
</del><span class="cx"> #include <wtf/CurrentTime.h>
</span><span class="cx"> #include <wtf/Lock.h>
</span><span class="cx"> #include <wtf/SpinLock.h>
</span><span class="cx"> #include <wtf/StdLibExtras.h>
</span><span class="cx"> #include <wtf/Threading.h>
</span><span class="cx"> #include <wtf/ThreadingPrimitives.h>
</span><ins>+#include <wtf/WordLock.h>
</ins><span class="cx">
</span><span class="cx"> namespace {
</span><span class="cx">
</span><span class="lines">@@ -44,7 +44,7 @@
</span><span class="cx">
</span><span class="cx"> NO_RETURN void usage()
</span><span class="cx"> {
</span><del>- 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");
</del><ins>+ 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");
</ins><span class="cx"> exit(1);
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -122,14 +122,14 @@
</span><span class="cx"> runBenchmark<SpinLock>("SpinLock");
</span><span class="cx"> didRun = true;
</span><span class="cx"> }
</span><ins>+ if (!strcmp(argv[1], "wordlock") || !strcmp(argv[1], "all")) {
+ runBenchmark<WordLock>("WTF WordLock");
+ didRun = true;
+ }
</ins><span class="cx"> if (!strcmp(argv[1], "lock") || !strcmp(argv[1], "all")) {
</span><span class="cx"> runBenchmark<Lock>("WTF Lock");
</span><span class="cx"> didRun = true;
</span><span class="cx"> }
</span><del>- if (!strcmp(argv[1], "bytelock") || !strcmp(argv[1], "all")) {
- runBenchmark<ByteLock>("WTF ByteLock");
- didRun = true;
- }
</del><span class="cx"> if (!strcmp(argv[1], "mutex") || !strcmp(argv[1], "all")) {
</span><span class="cx"> runBenchmark<Mutex>("Platform Mutex");
</span><span class="cx"> didRun = true;
</span></span></pre></div>
<a id="trunkSourceWTFwtfByteLockcpp"></a>
<div class="delfile"><h4>Deleted: trunk/Source/WTF/wtf/ByteLock.cpp (188322 => 188323)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -1,105 +0,0 @@
</span><del>-/*
- * 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
-
</del></span></pre></div>
<a id="trunkSourceWTFwtfByteLockh"></a>
<div class="delfile"><h4>Deleted: trunk/Source/WTF/wtf/ByteLock.h (188322 => 188323)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -1,108 +0,0 @@
</span><del>-/*
- * 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
-
</del></span></pre></div>
<a id="trunkSourceWTFwtfCMakeListstxt"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/CMakeLists.txt (188322 => 188323)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -7,7 +7,6 @@
</span><span class="cx"> BitVector.h
</span><span class="cx"> Bitmap.h
</span><span class="cx"> BumpPointerAllocator.h
</span><del>- ByteLock.h
</del><span class="cx"> ByteOrder.h
</span><span class="cx"> CompilationThread.h
</span><span class="cx"> Compiler.h
</span><span class="lines">@@ -104,6 +103,7 @@
</span><span class="cx"> VectorTraits.h
</span><span class="cx"> WTFThreadData.h
</span><span class="cx"> WeakPtr.h
</span><ins>+ WordLock.h
</ins><span class="cx"> WorkQueue.h
</span><span class="cx"> dtoa.h
</span><span class="cx">
</span><span class="lines">@@ -146,7 +146,6 @@
</span><span class="cx"> Assertions.cpp
</span><span class="cx"> Atomics.cpp
</span><span class="cx"> BitVector.cpp
</span><del>- ByteLock.cpp
</del><span class="cx"> CompilationThread.cpp
</span><span class="cx"> CryptographicUtilities.cpp
</span><span class="cx"> CryptographicallyRandomNumber.cpp
</span><span class="lines">@@ -183,6 +182,7 @@
</span><span class="cx"> StringPrintStream.cpp
</span><span class="cx"> Threading.cpp
</span><span class="cx"> WTFThreadData.cpp
</span><ins>+ WordLock.cpp
</ins><span class="cx"> WorkQueue.cpp
</span><span class="cx"> dtoa.cpp
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWTFwtfLockcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/Lock.cpp (188322 => 188323)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -27,56 +27,15 @@
</span><span class="cx"> #include "Lock.h"
</span><span class="cx">
</span><span class="cx"> #include "DataLog.h"
</span><ins>+#include "ParkingLot.h"
</ins><span class="cx"> #include "StringPrintStream.h"
</span><del>-#include "ThreadSpecific.h"
</del><span class="cx"> #include "ThreadingPrimitives.h"
</span><del>-#include <condition_variable>
-#include <mutex>
</del><span class="cx"> #include <thread>
</span><span class="cx">
</span><span class="cx"> namespace WTF {
</span><span class="cx">
</span><del>-namespace {
</del><ins>+static const bool verbose = false;
</ins><span class="cx">
</span><del>-// 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
-
</del><span class="cx"> void LockBase::lockSlow()
</span><span class="cx"> {
</span><span class="cx"> unsigned spinCount = 0;
</span><span class="lines">@@ -85,184 +44,62 @@
</span><span class="cx"> const unsigned spinLimit = 40;
</span><span class="cx">
</span><span class="cx"> for (;;) {
</span><del>- 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;
- }
- }
</del><ins>+ uint8_t currentByteValue = m_byte.load();
+ if (verbose)
+ dataLog(toString(currentThread(), ": locking with ", currentByteValue, "\n"));
</ins><span class="cx">
</span><del>- // 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) {
</del><ins>+ // 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) {
</ins><span class="cx"> spinCount++;
</span><span class="cx"> std::this_thread::yield();
</span><span class="cx"> continue;
</span><span class="cx"> }
</span><span class="cx">
</span><del>- // 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();
</del><ins>+ // 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))
</ins><span class="cx"> continue;
</span><del>- }
-
- me->shouldPark = true;
</del><span class="cx">
</span><del>- // 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;
</del><ins>+ // 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);
</ins><span class="cx">
</span><del>- // 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.
</del><ins>+ // We have awaken, or we never parked because the byte value changed. Either way, we loop
+ // around and try again.
</ins><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> void LockBase::unlockSlow()
</span><span class="cx"> {
</span><del>- // 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.
</del><ins>+ // 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;
</ins><span class="cx"> for (;;) {
</span><del>- 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))
</del><ins>+ oldByteValue = m_byte.load();
+ if (verbose)
+ dataLog(toString(currentThread(), ": unlocking with ", oldByteValue, "\n"));
+ ASSERT(oldByteValue & isHeldBit);
+ if (m_byte.compareExchangeWeak(oldByteValue, 0))
</ins><span class="cx"> break;
</span><span class="cx"> }
</span><span class="cx">
</span><del>- 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);
</del><ins>+ // 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.
</ins><span class="cx">
</span><del>- 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!
</del><ins>+ // 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);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> } // namespace WTF
</span></span></pre></div>
<a id="trunkSourceWTFwtfLockh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/Lock.h (188322 => 188323)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -33,108 +33,18 @@
</span><span class="cx">
</span><span class="cx"> namespace WTF {
</span><span class="cx">
</span><del>-// 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.
</del><ins>+// 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.
</ins><span class="cx">
</span><del>-// 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
-
</del><span class="cx"> // This is a struct without a constructor or destructor so that it can be statically initialized.
</span><span class="cx"> // Use Lock in instance variables.
</span><span class="cx"> struct LockBase {
</span><span class="cx"> void lock()
</span><span class="cx"> {
</span><del>- if (LIKELY(m_word.compareExchangeWeak(0, isLockedBit, std::memory_order_acquire))) {
</del><ins>+ if (LIKELY(m_byte.compareExchangeWeak(0, isHeldBit, std::memory_order_acquire))) {
</ins><span class="cx"> // Lock acquired!
</span><span class="cx"> return;
</span><span class="cx"> }
</span><span class="lines">@@ -144,8 +54,8 @@
</span><span class="cx">
</span><span class="cx"> void unlock()
</span><span class="cx"> {
</span><del>- if (LIKELY(m_word.compareExchangeWeak(isLockedBit, 0, std::memory_order_release))) {
- // Lock released, and nobody was waiting!
</del><ins>+ if (LIKELY(m_byte.compareExchangeWeak(isHeldBit, 0, std::memory_order_release))) {
+ // Lock released and nobody was waiting!
</ins><span class="cx"> return;
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -154,7 +64,7 @@
</span><span class="cx">
</span><span class="cx"> bool isHeld() const
</span><span class="cx"> {
</span><del>- return m_word.load(std::memory_order_acquire) & isLockedBit;
</del><ins>+ return m_byte.load(std::memory_order_acquire) & isHeldBit;
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> bool isLocked() const
</span><span class="lines">@@ -163,14 +73,13 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> protected:
</span><del>- static const uintptr_t isLockedBit = 1;
- static const uintptr_t isQueueLockedBit = 2;
- static const uintptr_t queueHeadMask = 3;
</del><ins>+ static const uint8_t isHeldBit = 1;
+ static const uint8_t hasParkedBit = 2;
</ins><span class="cx">
</span><span class="cx"> WTF_EXPORT_PRIVATE void lockSlow();
</span><span class="cx"> WTF_EXPORT_PRIVATE void unlockSlow();
</span><span class="cx">
</span><del>- Atomic<uintptr_t> m_word;
</del><ins>+ Atomic<uint8_t> m_byte;
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> class Lock : public LockBase {
</span><span class="lines">@@ -178,7 +87,7 @@
</span><span class="cx"> public:
</span><span class="cx"> Lock()
</span><span class="cx"> {
</span><del>- m_word.store(0, std::memory_order_relaxed);
</del><ins>+ m_byte.store(0, std::memory_order_relaxed);
</ins><span class="cx"> }
</span><span class="cx"> };
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWTFwtfParkingLotcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/ParkingLot.cpp (188322 => 188323)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -28,11 +28,11 @@
</span><span class="cx">
</span><span class="cx"> #include "DataLog.h"
</span><span class="cx"> #include "HashFunctions.h"
</span><del>-#include "Lock.h"
</del><span class="cx"> #include "StringPrintStream.h"
</span><span class="cx"> #include "ThreadSpecific.h"
</span><span class="cx"> #include "ThreadingPrimitives.h"
</span><span class="cx"> #include "Vector.h"
</span><ins>+#include "WordLock.h"
</ins><span class="cx"> #include <condition_variable>
</span><span class="cx"> #include <mutex>
</span><span class="cx"> #include <thread>
</span><span class="lines">@@ -170,7 +170,7 @@
</span><span class="cx">
</span><span class="cx"> // This lock protects the entire bucket. Thou shall not make changes to Bucket without holding
</span><span class="cx"> // this lock.
</span><del>- Lock lock;
</del><ins>+ WordLock lock;
</ins><span class="cx">
</span><span class="cx"> // Put some distane between buckets in memory. This is one of several mitigations against false
</span><span class="cx"> // sharing.
</span></span></pre></div>
<a id="trunkSourceWTFwtfWordLockcpp"></a>
<div class="addfile"><h4>Added: trunk/Source/WTF/wtf/WordLock.cpp (0 => 188323)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/WordLock.cpp (rev 0)
+++ trunk/Source/WTF/wtf/WordLock.cpp 2015-08-12 04:20:24 UTC (rev 188323)
</span><span class="lines">@@ -0,0 +1,269 @@
</span><ins>+/*
+ * 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
+
</ins></span></pre></div>
<a id="trunkSourceWTFwtfWordLockh"></a>
<div class="addfile"><h4>Added: trunk/Source/WTF/wtf/WordLock.h (0 => 188323)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/WordLock.h (rev 0)
+++ trunk/Source/WTF/wtf/WordLock.h 2015-08-12 04:20:24 UTC (rev 188323)
</span><span class="lines">@@ -0,0 +1,98 @@
</span><ins>+/*
+ * 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
+
</ins></span></pre></div>
<a id="trunkToolsChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Tools/ChangeLog (188322 => 188323)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/ChangeLog 2015-08-12 03:41:40 UTC (rev 188322)
+++ trunk/Tools/ChangeLog 2015-08-12 04:20:24 UTC (rev 188323)
</span><span class="lines">@@ -1,3 +1,17 @@
</span><ins>+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):
+
</ins><span class="cx"> 2015-08-11 Alexey Proskuryakov <ap@apple.com>
</span><span class="cx">
</span><span class="cx"> Make ASan build not depend on asan.xcconfig
</span></span></pre></div>
<a id="trunkToolsTestWebKitAPITestsWTFLockcpp"></a>
<div class="modfile"><h4>Modified: trunk/Tools/TestWebKitAPI/Tests/WTF/Lock.cpp (188322 => 188323)</h4>
<pre class="diff"><span>
<span class="info">--- 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)
</span><span class="lines">@@ -24,10 +24,10 @@
</span><span class="cx"> */
</span><span class="cx">
</span><span class="cx"> #include "config.h"
</span><del>-#include <wtf/ByteLock.h>
</del><span class="cx"> #include <wtf/Lock.h>
</span><span class="cx"> #include <wtf/Threading.h>
</span><span class="cx"> #include <wtf/ThreadingPrimitives.h>
</span><ins>+#include <wtf/WordLock.h>
</ins><span class="cx">
</span><span class="cx"> using namespace WTF;
</span><span class="cx">
</span><span class="lines">@@ -68,69 +68,69 @@
</span><span class="cx"> EXPECT_EQ(expected, words[threadGroupIndex]);
</span><span class="cx"> }
</span><span class="cx">
</span><del>-TEST(WTF_Lock, UncontendedShortSection)
</del><ins>+TEST(WTF_WordLock, UncontendedShortSection)
</ins><span class="cx"> {
</span><del>- runLockTest<Lock>(1, 1, 1, 10000000);
</del><ins>+ runLockTest<WordLock>(1, 1, 1, 10000000);
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-TEST(WTF_Lock, UncontendedLongSection)
</del><ins>+TEST(WTF_WordLock, UncontendedLongSection)
</ins><span class="cx"> {
</span><del>- runLockTest<Lock>(1, 1, 10000, 1000);
</del><ins>+ runLockTest<WordLock>(1, 1, 10000, 1000);
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-TEST(WTF_Lock, ContendedShortSection)
</del><ins>+TEST(WTF_WordLock, ContendedShortSection)
</ins><span class="cx"> {
</span><del>- runLockTest<Lock>(1, 10, 1, 10000000);
</del><ins>+ runLockTest<WordLock>(1, 10, 1, 10000000);
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-TEST(WTF_Lock, ContendedLongSection)
</del><ins>+TEST(WTF_WordLock, ContendedLongSection)
</ins><span class="cx"> {
</span><del>- runLockTest<Lock>(1, 10, 10000, 10000);
</del><ins>+ runLockTest<WordLock>(1, 10, 10000, 10000);
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-TEST(WTF_Lock, ManyContendedShortSections)
</del><ins>+TEST(WTF_WordLock, ManyContendedShortSections)
</ins><span class="cx"> {
</span><del>- runLockTest<Lock>(10, 10, 1, 500000);
</del><ins>+ runLockTest<WordLock>(10, 10, 1, 500000);
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-TEST(WTF_Lock, ManyContendedLongSections)
</del><ins>+TEST(WTF_WordLock, ManyContendedLongSections)
</ins><span class="cx"> {
</span><del>- runLockTest<Lock>(10, 10, 10000, 1000);
</del><ins>+ runLockTest<WordLock>(10, 10, 10000, 1000);
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-TEST(WTF_ByteLock, UncontendedShortSection)
</del><ins>+TEST(WTF_Lock, UncontendedShortSection)
</ins><span class="cx"> {
</span><del>- runLockTest<ByteLock>(1, 1, 1, 10000000);
</del><ins>+ runLockTest<Lock>(1, 1, 1, 10000000);
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-TEST(WTF_ByteLock, UncontendedLongSection)
</del><ins>+TEST(WTF_Lock, UncontendedLongSection)
</ins><span class="cx"> {
</span><del>- runLockTest<ByteLock>(1, 1, 10000, 1000);
</del><ins>+ runLockTest<Lock>(1, 1, 10000, 1000);
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-TEST(WTF_ByteLock, ContendedShortSection)
</del><ins>+TEST(WTF_Lock, ContendedShortSection)
</ins><span class="cx"> {
</span><del>- runLockTest<ByteLock>(1, 10, 1, 10000000);
</del><ins>+ runLockTest<Lock>(1, 10, 1, 10000000);
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-TEST(WTF_ByteLock, ContendedLongSection)
</del><ins>+TEST(WTF_Lock, ContendedLongSection)
</ins><span class="cx"> {
</span><del>- runLockTest<ByteLock>(1, 10, 10000, 10000);
</del><ins>+ runLockTest<Lock>(1, 10, 10000, 10000);
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-TEST(WTF_ByteLock, ManyContendedShortSections)
</del><ins>+TEST(WTF_Lock, ManyContendedShortSections)
</ins><span class="cx"> {
</span><del>- runLockTest<ByteLock>(10, 10, 1, 500000);
</del><ins>+ runLockTest<Lock>(10, 10, 1, 500000);
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-TEST(WTF_ByteLock, ManyContendedLongSections)
</del><ins>+TEST(WTF_Lock, ManyContendedLongSections)
</ins><span class="cx"> {
</span><del>- runLockTest<ByteLock>(10, 10, 10000, 1000);
</del><ins>+ runLockTest<Lock>(10, 10, 10000, 1000);
</ins><span class="cx"> }
</span><span class="cx">
</span><del>-TEST(WTF_ByteLock, SectionAddressCollision)
</del><ins>+TEST(WTF_Lock, SectionAddressCollision)
</ins><span class="cx"> {
</span><del>- runLockTest<ByteLock>(4, 2, 10000, 2000);
</del><ins>+ runLockTest<Lock>(4, 2, 10000, 2000);
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> } // namespace TestWebKitAPI
</span></span></pre>
</div>
</div>
</body>
</html>