<!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>[188280] 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/188280">188280</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2015-08-11 12:51:35 -0700 (Tue, 11 Aug 2015)</dd>
</dl>
<h3>Log Message</h3>
<pre>WTF should have a ParkingLot for parking sleeping threads, so that locks can fit in 1.6 bits
https://bugs.webkit.org/show_bug.cgi?id=147665
Reviewed by Mark Lam.
Source/JavaScriptCore:
Replace ByteSpinLock with ByteLock.
* runtime/ConcurrentJITLock.h:
Source/WTF:
This change adds a major new abstraction for concurrency algorithms in WebKit. It's called a
ParkingLot, and it makes available a thread parking queue for each virtual address in memory.
The queues are maintained by a data-access-parallel concurrent hashtable implementation. The
memory usage is bounded at around half a KB per thread.
The ParkingLot makes it easy to turn any spinlock-based concurrency protocol into one that
parks threads after a while. Because queue state management is up to the ParkingLot and not
the user's data structure, this patch uses it to implement a full adaptive mutex in one byte.
In fact, only three states of that byte are used (0 = available, 1 = locked, 2 = locked and
there are parked threads). Hence the joke that ParkingLot allows locks that fit in 1.6 bits.
ByteLock is used as a replacement for ByteSpinLock in JavaScriptCore.
The API tests for this also demo how to create a completely fair (FIFO) binary semamphore. The
comment in Lock.h shows how we could accelerate Lock performance using ParkingLot. After we
are sure that this code works, we can expand the use of ParkingLot. That's covered by
https://bugs.webkit.org/show_bug.cgi?id=147841.
* WTF.vcxproj/WTF.vcxproj:
* WTF.xcodeproj/project.pbxproj:
* benchmarks/LockSpeedTest.cpp:
(main):
* wtf/Atomics.h:
(WTF::Atomic::compareExchangeWeak):
(WTF::Atomic::compareExchangeStrong):
* wtf/ByteLock.cpp: Added.
(WTF::ByteLock::lockSlow):
(WTF::ByteLock::unlockSlow):
* wtf/ByteLock.h: Added.
(WTF::ByteLock::ByteLock):
(WTF::ByteLock::lock):
(WTF::ByteLock::unlock):
(WTF::ByteLock::isHeld):
(WTF::ByteLock::isLocked):
* wtf/CMakeLists.txt:
* wtf/Lock.h:
* wtf/ParkingLot.cpp: Added.
(WTF::ParkingLot::parkConditionally):
(WTF::ParkingLot::unparkOne):
(WTF::ParkingLot::unparkAll):
(WTF::ParkingLot::forEach):
* wtf/ParkingLot.h: Added.
(WTF::ParkingLot::compareAndPark):
Tools:
* TestWebKitAPI/CMakeLists.txt:
* TestWebKitAPI/TestWebKitAPI.vcxproj/TestWebKitAPI.vcxproj:
* TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:
* TestWebKitAPI/Tests/WTF/Lock.cpp:
(TestWebKitAPI::TEST):
* TestWebKitAPI/Tests/WTF/ParkingLot.cpp: Added.
(TestWebKitAPI::TEST):</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="#trunkSourceWTFwtfLockh">trunk/Source/WTF/wtf/Lock.h</a></li>
<li><a href="#trunkToolsChangeLog">trunk/Tools/ChangeLog</a></li>
<li><a href="#trunkToolsTestWebKitAPICMakeListstxt">trunk/Tools/TestWebKitAPI/CMakeLists.txt</a></li>
<li><a href="#trunkToolsTestWebKitAPITestWebKitAPIvcxprojTestWebKitAPIvcxproj">trunk/Tools/TestWebKitAPI/TestWebKitAPI.vcxproj/TestWebKitAPI.vcxproj</a></li>
<li><a href="#trunkToolsTestWebKitAPITestWebKitAPIxcodeprojprojectpbxproj">trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj</a></li>
<li><a href="#trunkToolsTestWebKitAPITestsWTFLockcpp">trunk/Tools/TestWebKitAPI/Tests/WTF/Lock.cpp</a></li>
</ul>
<h3>Added 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>
<li><a href="#trunkSourceWTFwtfParkingLotcpp">trunk/Source/WTF/wtf/ParkingLot.cpp</a></li>
<li><a href="#trunkSourceWTFwtfParkingLoth">trunk/Source/WTF/wtf/ParkingLot.h</a></li>
<li><a href="#trunkToolsTestWebKitAPITestsWTFParkingLotcpp">trunk/Tools/TestWebKitAPI/Tests/WTF/ParkingLot.cpp</a></li>
</ul>
</div>
<div id="patch">
<h3>Diff</h3>
<a id="trunkSourceJavaScriptCoreChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/ChangeLog (188279 => 188280)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/ChangeLog 2015-08-11 19:48:50 UTC (rev 188279)
+++ trunk/Source/JavaScriptCore/ChangeLog 2015-08-11 19:51:35 UTC (rev 188280)
</span><span class="lines">@@ -1,3 +1,14 @@
</span><ins>+2015-08-10 Filip Pizlo <fpizlo@apple.com>
+
+ WTF should have a ParkingLot for parking sleeping threads, so that locks can fit in 1.6 bits
+ https://bugs.webkit.org/show_bug.cgi?id=147665
+
+ Reviewed by Mark Lam.
+
+ Replace ByteSpinLock with ByteLock.
+
+ * runtime/ConcurrentJITLock.h:
+
</ins><span class="cx"> 2015-08-11 Yusuke Suzuki <utatane.tea@gmail.com>
</span><span class="cx">
</span><span class="cx"> Numeric setter on prototype doesn't get called.
</span></span></pre></div>
<a id="trunkSourceJavaScriptCoreruntimeConcurrentJITLockh"></a>
<div class="modfile"><h4>Modified: trunk/Source/JavaScriptCore/runtime/ConcurrentJITLock.h (188279 => 188280)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/JavaScriptCore/runtime/ConcurrentJITLock.h 2015-08-11 19:48:50 UTC (rev 188279)
+++ trunk/Source/JavaScriptCore/runtime/ConcurrentJITLock.h 2015-08-11 19:51:35 UTC (rev 188280)
</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/ByteSpinLock.h>
</del><ins>+#include <wtf/ByteLock.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 ByteSpinLock ConcurrentJITLock;
-typedef ByteSpinLocker ConcurrentJITLockerImpl;
</del><ins>+typedef ByteLock ConcurrentJITLock;
+typedef ByteLocker 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 (188279 => 188280)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/ChangeLog 2015-08-11 19:48:50 UTC (rev 188279)
+++ trunk/Source/WTF/ChangeLog 2015-08-11 19:51:35 UTC (rev 188280)
</span><span class="lines">@@ -1,3 +1,54 @@
</span><ins>+2015-08-10 Filip Pizlo <fpizlo@apple.com>
+
+ WTF should have a ParkingLot for parking sleeping threads, so that locks can fit in 1.6 bits
+ https://bugs.webkit.org/show_bug.cgi?id=147665
+
+ Reviewed by Mark Lam.
+
+ This change adds a major new abstraction for concurrency algorithms in WebKit. It's called a
+ ParkingLot, and it makes available a thread parking queue for each virtual address in memory.
+ The queues are maintained by a data-access-parallel concurrent hashtable implementation. The
+ memory usage is bounded at around half a KB per thread.
+
+ The ParkingLot makes it easy to turn any spinlock-based concurrency protocol into one that
+ parks threads after a while. Because queue state management is up to the ParkingLot and not
+ the user's data structure, this patch uses it to implement a full adaptive mutex in one byte.
+ In fact, only three states of that byte are used (0 = available, 1 = locked, 2 = locked and
+ there are parked threads). Hence the joke that ParkingLot allows locks that fit in 1.6 bits.
+
+ ByteLock is used as a replacement for ByteSpinLock in JavaScriptCore.
+
+ The API tests for this also demo how to create a completely fair (FIFO) binary semamphore. The
+ comment in Lock.h shows how we could accelerate Lock performance using ParkingLot. After we
+ are sure that this code works, we can expand the use of ParkingLot. That's covered by
+ https://bugs.webkit.org/show_bug.cgi?id=147841.
+
+ * WTF.vcxproj/WTF.vcxproj:
+ * WTF.xcodeproj/project.pbxproj:
+ * benchmarks/LockSpeedTest.cpp:
+ (main):
+ * wtf/Atomics.h:
+ (WTF::Atomic::compareExchangeWeak):
+ (WTF::Atomic::compareExchangeStrong):
+ * wtf/ByteLock.cpp: Added.
+ (WTF::ByteLock::lockSlow):
+ (WTF::ByteLock::unlockSlow):
+ * wtf/ByteLock.h: Added.
+ (WTF::ByteLock::ByteLock):
+ (WTF::ByteLock::lock):
+ (WTF::ByteLock::unlock):
+ (WTF::ByteLock::isHeld):
+ (WTF::ByteLock::isLocked):
+ * wtf/CMakeLists.txt:
+ * wtf/Lock.h:
+ * wtf/ParkingLot.cpp: Added.
+ (WTF::ParkingLot::parkConditionally):
+ (WTF::ParkingLot::unparkOne):
+ (WTF::ParkingLot::unparkAll):
+ (WTF::ParkingLot::forEach):
+ * wtf/ParkingLot.h: Added.
+ (WTF::ParkingLot::compareAndPark):
+
</ins><span class="cx"> 2015-08-11 Brent Fulgham <bfulgham@apple.com>
</span><span class="cx">
</span><span class="cx"> [Win] Unreviewed gardening.
</span></span></pre></div>
<a id="trunkSourceWTFWTFvcxprojWTFvcxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj (188279 => 188280)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj 2015-08-11 19:48:50 UTC (rev 188279)
+++ trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj 2015-08-11 19:51:35 UTC (rev 188280)
</span><span class="lines">@@ -53,6 +53,7 @@
</span><span class="cx"> <ItemGroup>
</span><span class="cx"> <ClCompile Include="..\wtf\Assertions.cpp" />
</span><span class="cx"> <ClCompile Include="..\wtf\BitVector.cpp" />
</span><ins>+ <ClCompile Include="..\wtf\ByteLock.cpp" />
</ins><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">@@ -116,6 +117,7 @@
</span><span class="cx"> <ClCompile Include="..\wtf\OSRandomSource.cpp" />
</span><span class="cx"> <ClCompile Include="..\wtf\PageBlock.cpp" />
</span><span class="cx"> <ClCompile Include="..\wtf\ParallelJobsGeneric.cpp" />
</span><ins>+ <ClCompile Include="..\wtf\ParkingLot.cpp" />
</ins><span class="cx"> <ClCompile Include="..\wtf\PrintStream.cpp" />
</span><span class="cx"> <ClCompile Include="..\wtf\RAMSize.cpp" />
</span><span class="cx"> <ClCompile Include="..\wtf\RandomNumber.cpp" />
</span><span class="lines">@@ -171,6 +173,7 @@
</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><ins>+ <ClInclude Include="..\wtf\ByteLock.h" />
</ins><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">@@ -246,6 +249,7 @@
</span><span class="cx"> <ClInclude Include="..\wtf\ParallelJobsGeneric.h" />
</span><span class="cx"> <ClInclude Include="..\wtf\ParallelJobsLibdispatch.h" />
</span><span class="cx"> <ClInclude Include="..\wtf\ParallelJobsOpenMP.h" />
</span><ins>+ <ClInclude Include="..\wtf\ParkingLot.h" />
</ins><span class="cx"> <ClInclude Include="..\wtf\PassRefPtr.h" />
</span><span class="cx"> <ClInclude Include="..\wtf\Platform.h" />
</span><span class="cx"> <ClInclude Include="..\wtf\PrintStream.h" />
</span></span></pre></div>
<a id="trunkSourceWTFWTFxcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/WTF.xcodeproj/project.pbxproj (188279 => 188280)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2015-08-11 19:48:50 UTC (rev 188279)
+++ trunk/Source/WTF/WTF.xcodeproj/project.pbxproj 2015-08-11 19:51:35 UTC (rev 188280)
</span><span class="lines">@@ -24,6 +24,10 @@
</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><ins>+ 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 */; };
</ins><span class="cx"> 0F87105A16643F190090B0AD /* RawPointer.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F87105916643F190090B0AD /* RawPointer.h */; };
</span><span class="cx"> 0F885E0F1845AEA900F1E3FA /* FastBitVector.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F885E0E1845AE9F00F1E3FA /* FastBitVector.cpp */; };
</span><span class="cx"> 0F8F2B91172E00FC007DBDA5 /* CompilationThread.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F8F2B90172E00F0007DBDA5 /* CompilationThread.h */; };
</span><span class="lines">@@ -307,6 +311,10 @@
</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><ins>+ 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>"; };
</ins><span class="cx"> 0F87105916643F190090B0AD /* RawPointer.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = RawPointer.h; sourceTree = "<group>"; };
</span><span class="cx"> 0F885E0E1845AE9F00F1E3FA /* FastBitVector.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; path = FastBitVector.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 0F8F2B8F172E00F0007DBDA5 /* CompilationThread.cpp */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; path = CompilationThread.cpp; sourceTree = "<group>"; };
</span><span class="lines">@@ -716,6 +724,8 @@
</span><span class="cx"> A8A47264151A825A004123FF /* BlockStack.h */,
</span><span class="cx"> A8A47265151A825A004123FF /* BloomFilter.h */,
</span><span class="cx"> A8A47267151A825A004123FF /* BumpPointerAllocator.h */,
</span><ins>+ 0F824A621B7443A0002E345D /* ByteLock.cpp */,
+ 0F824A631B7443A0002E345D /* ByteLock.h */,
</ins><span class="cx"> EB95E1EF161A72410089A2F5 /* ByteOrder.h */,
</span><span class="cx"> 0FEC3EE4171B834700FDAC8D /* ByteSpinLock.h */,
</span><span class="cx"> A8A4726A151A825A004123FF /* CheckedArithmetic.h */,
</span><span class="lines">@@ -810,6 +820,8 @@
</span><span class="cx"> A8A472E5151A825B004123FF /* PageReservation.h */,
</span><span class="cx"> A8A472E6151A825B004123FF /* ParallelJobs.h */,
</span><span class="cx"> A8A472E9151A825B004123FF /* ParallelJobsLibdispatch.h */,
</span><ins>+ 0F824A641B7443A0002E345D /* ParkingLot.cpp */,
+ 0F824A651B7443A0002E345D /* ParkingLot.h */,
</ins><span class="cx"> A8A472ED151A825B004123FF /* PassRefPtr.h */,
</span><span class="cx"> A876DBD7151816E500DADB95 /* Platform.h */,
</span><span class="cx"> 0F9D335D165DBA73005AD387 /* PrintStream.cpp */,
</span><span class="lines">@@ -1156,6 +1168,7 @@
</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><ins>+ 0F824A671B7443A0002E345D /* ByteLock.h in Headers */,
</ins><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">@@ -1167,6 +1180,7 @@
</span><span class="cx"> 1469419216EAAF6D0024E146 /* RunLoopTimer.h in Headers */,
</span><span class="cx"> 14F3B0F715E45E4600210069 /* SaturatedArithmetic.h in Headers */,
</span><span class="cx"> 1469419616EAAFF80024E146 /* SchedulePair.h in Headers */,
</span><ins>+ 0F824A691B7443A0002E345D /* ParkingLot.h in Headers */,
</ins><span class="cx"> A8A4741F151A825B004123FF /* SegmentedVector.h in Headers */,
</span><span class="cx"> A8A47420151A825B004123FF /* SentinelLinkedList.h in Headers */,
</span><span class="cx"> A8A47422151A825B004123FF /* SHA1.h in Headers */,
</span><span class="lines">@@ -1325,6 +1339,7 @@
</span><span class="cx"> files = (
</span><span class="cx"> A8A47386151A825B004123FF /* Assertions.cpp in Sources */,
</span><span class="cx"> A8A47435151A825B004123FF /* AtomicString.cpp in Sources */,
</span><ins>+ 0F824A661B7443A0002E345D /* ByteLock.cpp in Sources */,
</ins><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">@@ -1340,6 +1355,7 @@
</span><span class="cx"> A8A4739A151A825B004123FF /* CryptographicallyRandomNumber.cpp in Sources */,
</span><span class="cx"> A8A47439151A825B004123FF /* CString.cpp in Sources */,
</span><span class="cx"> A8A4739C151A825B004123FF /* CurrentTime.cpp in Sources */,
</span><ins>+ 0F824A681B7443A0002E345D /* ParkingLot.cpp in Sources */,
</ins><span class="cx"> 86F46F601A2840EE00CCBF22 /* RefCounter.cpp in Sources */,
</span><span class="cx"> A8A4739E151A825B004123FF /* DataLog.cpp in Sources */,
</span><span class="cx"> A8A473A0151A825B004123FF /* DateMath.cpp in Sources */,
</span></span></pre></div>
<a id="trunkSourceWTFbenchmarksLockSpeedTestcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/benchmarks/LockSpeedTest.cpp (188279 => 188280)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/benchmarks/LockSpeedTest.cpp 2015-08-11 19:48:50 UTC (rev 188279)
+++ trunk/Source/WTF/benchmarks/LockSpeedTest.cpp 2015-08-11 19:51:35 UTC (rev 188280)
</span><span class="lines">@@ -26,6 +26,7 @@
</span><span class="cx"> #include "config.h"
</span><span class="cx">
</span><span class="cx"> #include <unistd.h>
</span><ins>+#include <wtf/ByteLock.h>
</ins><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="lines">@@ -43,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|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|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">@@ -125,6 +126,10 @@
</span><span class="cx"> runBenchmark<Lock>("WTF Lock");
</span><span class="cx"> didRun = true;
</span><span class="cx"> }
</span><ins>+ if (!strcmp(argv[1], "bytelock") || !strcmp(argv[1], "all")) {
+ runBenchmark<ByteLock>("WTF ByteLock");
+ didRun = true;
+ }
</ins><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="addfile"><h4>Added: trunk/Source/WTF/wtf/ByteLock.cpp (0 => 188280)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/ByteLock.cpp (rev 0)
+++ trunk/Source/WTF/wtf/ByteLock.cpp 2015-08-11 19:51:35 UTC (rev 188280)
</span><span class="lines">@@ -0,0 +1,105 @@
</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 "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
+
</ins></span></pre></div>
<a id="trunkSourceWTFwtfByteLockh"></a>
<div class="addfile"><h4>Added: trunk/Source/WTF/wtf/ByteLock.h (0 => 188280)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/ByteLock.h (rev 0)
+++ trunk/Source/WTF/wtf/ByteLock.h 2015-08-11 19:51:35 UTC (rev 188280)
</span><span class="lines">@@ -0,0 +1,108 @@
</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 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
+
</ins></span></pre></div>
<a id="trunkSourceWTFwtfCMakeListstxt"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/CMakeLists.txt (188279 => 188280)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/CMakeLists.txt 2015-08-11 19:48:50 UTC (rev 188279)
+++ trunk/Source/WTF/wtf/CMakeLists.txt 2015-08-11 19:51:35 UTC (rev 188280)
</span><span class="lines">@@ -7,6 +7,7 @@
</span><span class="cx"> BitVector.h
</span><span class="cx"> Bitmap.h
</span><span class="cx"> BumpPointerAllocator.h
</span><ins>+ ByteLock.h
</ins><span class="cx"> ByteOrder.h
</span><span class="cx"> CompilationThread.h
</span><span class="cx"> Compiler.h
</span><span class="lines">@@ -62,6 +63,7 @@
</span><span class="cx"> ParallelJobsGeneric.h
</span><span class="cx"> ParallelJobsLibdispatch.h
</span><span class="cx"> ParallelJobsOpenMP.h
</span><ins>+ ParkingLot.h
</ins><span class="cx"> PassRefPtr.h
</span><span class="cx"> Platform.h
</span><span class="cx"> PrintStream.h
</span><span class="lines">@@ -144,6 +146,7 @@
</span><span class="cx"> Assertions.cpp
</span><span class="cx"> Atomics.cpp
</span><span class="cx"> BitVector.cpp
</span><ins>+ ByteLock.cpp
</ins><span class="cx"> CompilationThread.cpp
</span><span class="cx"> CryptographicUtilities.cpp
</span><span class="cx"> CryptographicallyRandomNumber.cpp
</span><span class="lines">@@ -166,6 +169,7 @@
</span><span class="cx"> OSRandomSource.cpp
</span><span class="cx"> PageBlock.cpp
</span><span class="cx"> ParallelJobsGeneric.cpp
</span><ins>+ ParkingLot.cpp
</ins><span class="cx"> PrintStream.cpp
</span><span class="cx"> RAMSize.cpp
</span><span class="cx"> RandomNumber.cpp
</span></span></pre></div>
<a id="trunkSourceWTFwtfLockh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/Lock.h (188279 => 188280)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/Lock.h 2015-08-11 19:48:50 UTC (rev 188279)
+++ trunk/Source/WTF/wtf/Lock.h 2015-08-11 19:51:35 UTC (rev 188280)
</span><span class="lines">@@ -102,6 +102,33 @@
</span><span class="cx"> // acquisition order under contention. The same caveat is generally true of SpinLock and platform
</span><span class="cx"> // mutexes on some platforms.
</span><span class="cx">
</span><ins>+// 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
+
</ins><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></pre></div>
<a id="trunkSourceWTFwtfParkingLotcpp"></a>
<div class="addfile"><h4>Added: trunk/Source/WTF/wtf/ParkingLot.cpp (0 => 188280)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/ParkingLot.cpp (rev 0)
+++ trunk/Source/WTF/wtf/ParkingLot.cpp 2015-08-11 19:51:35 UTC (rev 188280)
</span><span class="lines">@@ -0,0 +1,611 @@
</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 "ParkingLot.h"
+
+#include "DataLog.h"
+#include "HashFunctions.h"
+#include "Lock.h"
+#include "StringPrintStream.h"
+#include "ThreadSpecific.h"
+#include "ThreadingPrimitives.h"
+#include "Vector.h"
+#include <condition_variable>
+#include <mutex>
+#include <thread>
+
+namespace WTF {
+
+namespace {
+
+const bool verbose = false;
+
+struct ThreadData {
+ WTF_MAKE_FAST_ALLOCATED;
+public:
+
+ ThreadData();
+ ~ThreadData();
+
+ ThreadIdentifier threadIdentifier;
+
+ bool shouldPark { false };
+ std::mutex parkingLock;
+ std::condition_variable parkingCondition;
+
+ const void* address;
+ ThreadData* nextInQueue { nullptr };
+};
+
+enum class DequeueResult {
+ Ignore,
+ RemoveAndContinue,
+ RemoveAndStop
+};
+
+struct Bucket {
+ WTF_MAKE_FAST_ALLOCATED;
+public:
+ void enqueue(ThreadData* data)
+ {
+ if (verbose)
+ dataLog(toString(currentThread(), ": enqueueing ", RawPointer(data), " with address = ", RawPointer(data->address), " onto ", RawPointer(this), "\n"));
+ ASSERT(data->address);
+ ASSERT(!data->nextInQueue);
+
+ if (queueTail) {
+ queueTail->nextInQueue = data;
+ queueTail = data;
+ return;
+ }
+
+ queueHead = data;
+ queueTail = data;
+ }
+
+ template<typename Functor>
+ void genericDequeue(const Functor& functor)
+ {
+ if (verbose)
+ dataLog(toString(currentThread(), ": dequeueing from bucket at ", RawPointer(this), "\n"));
+
+ if (!queueHead) {
+ if (verbose)
+ dataLog(toString(currentThread(), ": empty.\n"));
+ return;
+ }
+
+ // This loop is a very clever abomination. The induction variables are the pointer to the
+ // pointer to the current node, and the pointer to the previous node. This gives us everything
+ // we need to both proceed forward to the next node, and to remove nodes while maintaining the
+ // queueHead/queueTail and all of the nextInQueue links. For example, when we are at the head
+ // element, then removal means rewiring queueHead, and if it was also equal to queueTail, then
+ // we'd want queueTail to be set to nullptr. This works because:
+ //
+ // currentPtr == &queueHead
+ // previous == nullptr
+ //
+ // We remove by setting *currentPtr = (*currentPtr)->nextInQueue, i.e. changing the pointer
+ // that used to point to this node to instead point to this node's successor. Another example:
+ // if we were at the second node in the queue, then we'd have:
+ //
+ // currentPtr == &queueHead->nextInQueue
+ // previous == queueHead
+ //
+ // If this node is not equal to queueTail, then removing it simply means making
+ // queueHead->nextInQueue point to queueHead->nextInQueue->nextInQueue (which the algorithm
+ // achieves by mutating *currentPtr). If this node is equal to queueTail, then we want to set
+ // queueTail to previous, which in this case is queueHead - thus making the queue look like a
+ // proper one-element queue with queueHead == queueTail.
+ bool shouldContinue = true;
+ ThreadData** currentPtr = &queueHead;
+ ThreadData* previous = nullptr;
+ while (shouldContinue) {
+ ThreadData* current = *currentPtr;
+ if (verbose)
+ dataLog(toString(currentThread(), ": got thread ", RawPointer(current), "\n"));
+ if (!current)
+ break;
+ DequeueResult result = functor(current);
+ switch (result) {
+ case DequeueResult::Ignore:
+ if (verbose)
+ dataLog(toString(currentThread(), ": currentPtr = ", RawPointer(currentPtr), ", *currentPtr = ", RawPointer(*currentPtr), "\n"));
+ previous = current;
+ currentPtr = &(*currentPtr)->nextInQueue;
+ break;
+ case DequeueResult::RemoveAndContinue:
+ case DequeueResult::RemoveAndStop:
+ if (verbose)
+ dataLog(toString(currentThread(), ": dequeueing ", RawPointer(current), " from ", RawPointer(this), "\n"));
+ if (current == queueTail)
+ queueTail = previous;
+ *currentPtr = current->nextInQueue;
+ current->nextInQueue = nullptr;
+ if (result == DequeueResult::RemoveAndStop)
+ shouldContinue = false;
+ break;
+ }
+ }
+
+ ASSERT(!!queueHead == !!queueTail);
+ }
+
+ ThreadData* dequeue()
+ {
+ ThreadData* result = nullptr;
+ genericDequeue(
+ [&] (ThreadData* element) -> DequeueResult {
+ result = element;
+ return DequeueResult::RemoveAndStop;
+ });
+ return result;
+ }
+
+ ThreadData* queueHead { nullptr };
+ ThreadData* queueTail { nullptr };
+
+ // This lock protects the entire bucket. Thou shall not make changes to Bucket without holding
+ // this lock.
+ Lock lock;
+
+ // Put some distane between buckets in memory. This is one of several mitigations against false
+ // sharing.
+ char padding[64];
+};
+
+struct Hashtable {
+ unsigned size;
+ Atomic<Bucket*> data[1];
+
+ static Hashtable* create(unsigned size)
+ {
+ ASSERT(size >= 1);
+
+ Hashtable* result = static_cast<Hashtable*>(
+ fastZeroedMalloc(sizeof(Hashtable) + sizeof(Atomic<Bucket*>) * (size - 1)));
+ result->size = size;
+ return result;
+ }
+
+ static void destroy(Hashtable* hashtable)
+ {
+ fastFree(hashtable);
+ }
+};
+
+ThreadSpecific<ThreadData>* threadData;
+Atomic<Hashtable*> hashtable;
+Atomic<unsigned> numThreads;
+
+// With 64 bytes of padding per bucket, assuming a hashtable is fully populated with buckets, the
+// memory usage per thread will still be less than 1KB.
+const unsigned maxLoadFactor = 3;
+
+const unsigned growthFactor = 2;
+
+unsigned hashAddress(const void* address)
+{
+ return WTF::PtrHash<const void*>::hash(address);
+}
+
+// Locks the hashtable. This reloops in case of rehashing, so the current hashtable may be different
+// after this returns than when you called it. Guarantees that there is a hashtable. This is pretty
+// slow and not scalable, so it's only used during thread creation and for debugging/testing.
+Vector<Bucket*> lockHashtable()
+{
+ for (;;) {
+ Hashtable* currentHashtable;
+
+ currentHashtable = hashtable.load();
+ if (!currentHashtable) {
+ // Try to be the first to create the hashtable.
+ currentHashtable = Hashtable::create(maxLoadFactor);
+ if (!hashtable.compareExchangeWeak(nullptr, currentHashtable)) {
+ Hashtable::destroy(currentHashtable);
+ continue;
+ }
+ if (verbose)
+ dataLog(toString(currentThread(), ": created initial hashtable ", RawPointer(currentHashtable), "\n"));
+ }
+
+ // Now find all of the buckets. This makes sure that the hashtable is full of buckets so that
+ // we can lock all of the buckets, not just the ones that are materialized.
+ Vector<Bucket*> buckets;
+ for (unsigned i = currentHashtable->size; i--;) {
+ Atomic<Bucket*>& bucketPointer = currentHashtable->data[i];
+
+ for (;;) {
+ Bucket* bucket = bucketPointer.load();
+
+ if (!bucket) {
+ bucket = new Bucket();
+ if (!bucketPointer.compareExchangeWeak(nullptr, bucket)) {
+ delete bucket;
+ continue;
+ }
+ }
+
+ buckets.append(bucket);
+ break;
+ }
+ }
+
+ // Now lock the buckets in the right order.
+ std::sort(buckets.begin(), buckets.end());
+ for (Bucket* bucket : buckets)
+ bucket->lock.lock();
+
+ // If the hashtable didn't change (wasn't rehashed) while we were locking it, then we own it
+ // now.
+ if (hashtable.load() == currentHashtable)
+ return buckets;
+
+ // The hashtable rehashed. Unlock everything and try again.
+ for (Bucket* bucket : buckets)
+ bucket->lock.unlock();
+ }
+}
+
+void unlockHashtable(const Vector<Bucket*>& buckets)
+{
+ for (Bucket* bucket : buckets)
+ bucket->lock.unlock();
+}
+
+// Rehash the hashtable to handle numThreads threads.
+void ensureHashtableSize(unsigned numThreads)
+{
+ // We try to ensure that the size of the hashtable used for thread queues is always large enough
+ // to avoid collisions. So, since we started a new thread, we may need to increase the size of the
+ // hashtable. This does just that. Note that we never free the old spine, since we never lock
+ // around spine accesses (i.e. the "hashtable" global variable).
+
+ // First do a fast check to see if rehashing is needed.
+ Hashtable* oldHashtable = hashtable.load();
+ if (oldHashtable && static_cast<double>(oldHashtable->size) / static_cast<double>(numThreads) >= maxLoadFactor) {
+ if (verbose)
+ dataLog(toString(currentThread(), ": no need to rehash because ", oldHashtable->size, " / ", numThreads, " >= ", maxLoadFactor, "\n"));
+ return;
+ }
+
+ // Seems like we *might* have to rehash, so lock the hashtable and try again.
+ Vector<Bucket*> bucketsToUnlock = lockHashtable();
+
+ // Check again, since the hashtable could have rehashed while we were locking it. Also,
+ // lockHashtable() creates an initial hashtable for us.
+ oldHashtable = hashtable.load();
+ if (oldHashtable && static_cast<double>(oldHashtable->size) / static_cast<double>(numThreads) >= maxLoadFactor) {
+ if (verbose)
+ dataLog(toString(currentThread(), ": after locking, no need to rehash because ", oldHashtable->size, " / ", numThreads, " >= ", maxLoadFactor, "\n"));
+ unlockHashtable(bucketsToUnlock);
+ return;
+ }
+
+ Vector<Bucket*> reusableBuckets = bucketsToUnlock;
+
+ // OK, now we resize. First we gather all thread datas from the old hashtable. These thread datas
+ // are placed into the vector in queue order.
+ Vector<ThreadData*> threadDatas;
+ for (Bucket* bucket : reusableBuckets) {
+ while (ThreadData* threadData = bucket->dequeue())
+ threadDatas.append(threadData);
+ }
+
+ unsigned newSize = numThreads * growthFactor * maxLoadFactor;
+ RELEASE_ASSERT(newSize > oldHashtable->size);
+
+ Hashtable* newHashtable = Hashtable::create(newSize);
+ if (verbose)
+ dataLog(toString(currentThread(), ": created new hashtable: ", RawPointer(newHashtable), "\n"));
+ for (ThreadData* threadData : threadDatas) {
+ if (verbose)
+ dataLog(toString(currentThread(), ": rehashing thread data ", RawPointer(threadData), " with address = ", RawPointer(threadData->address), "\n"));
+ unsigned hash = hashAddress(threadData->address);
+ unsigned index = hash % newHashtable->size;
+ if (verbose)
+ dataLog(toString(currentThread(), ": index = ", index, "\n"));
+ Bucket* bucket = newHashtable->data[index].load();
+ if (!bucket) {
+ if (reusableBuckets.isEmpty())
+ bucket = new Bucket();
+ else
+ bucket = reusableBuckets.takeLast();
+ newHashtable->data[index].store(bucket);
+ }
+
+ bucket->enqueue(threadData);
+ }
+
+ // At this point there may be some buckets left unreused. This could easily happen if the
+ // number of enqueued threads right now is low but the high watermark of the number of threads
+ // enqueued was high. We place these buckets into the hashtable basically at random, just to
+ // make sure we don't leak them.
+ for (unsigned i = 0; i < newHashtable->size && !reusableBuckets.isEmpty(); ++i) {
+ Atomic<Bucket*>& bucketPtr = newHashtable->data[i];
+ if (bucketPtr.load())
+ continue;
+ bucketPtr.store(reusableBuckets.takeLast());
+ }
+
+ // Since we increased the size of the hashtable, we should have exhausted our preallocated
+ // buckets by now.
+ ASSERT(reusableBuckets.isEmpty());
+
+ // OK, right now the old hashtable is locked up and the new hashtable is ready to rock and
+ // roll. After we install the new hashtable, we can release all bucket locks.
+
+ bool result = hashtable.compareExchangeStrong(oldHashtable, newHashtable);
+ RELEASE_ASSERT(result);
+
+ unlockHashtable(bucketsToUnlock);
+}
+
+ThreadData::ThreadData()
+ : threadIdentifier(currentThread())
+{
+ unsigned currentNumThreads;
+ for (;;) {
+ unsigned oldNumThreads = numThreads.load();
+ currentNumThreads = oldNumThreads + 1;
+ if (numThreads.compareExchangeWeak(oldNumThreads, currentNumThreads))
+ break;
+ }
+
+ ensureHashtableSize(currentNumThreads);
+}
+
+ThreadData::~ThreadData()
+{
+ for (;;) {
+ unsigned oldNumThreads = numThreads.load();
+ if (numThreads.compareExchangeWeak(oldNumThreads, oldNumThreads - 1))
+ break;
+ }
+}
+
+ThreadData* myThreadData()
+{
+ static std::once_flag initializeOnce;
+ std::call_once(
+ initializeOnce,
+ [] {
+ threadData = new ThreadSpecific<ThreadData>();
+ });
+
+ return *threadData;
+}
+
+template<typename Functor>
+bool enqueue(const void* address, const Functor& functor)
+{
+ unsigned hash = hashAddress(address);
+
+ for (;;) {
+ Hashtable* myHashtable = hashtable.load();
+ unsigned index = hash % myHashtable->size;
+ Atomic<Bucket*>& bucketPointer = myHashtable->data[index];
+ Bucket* bucket;
+ for (;;) {
+ bucket = bucketPointer.load();
+ if (!bucket) {
+ bucket = new Bucket();
+ if (!bucketPointer.compareExchangeWeak(nullptr, bucket)) {
+ delete bucket;
+ continue;
+ }
+ }
+ break;
+ }
+ if (verbose)
+ dataLog(toString(currentThread(), ": enqueueing onto bucket ", RawPointer(bucket), " with index ", index, " for address ", RawPointer(address), " with hash ", hash, "\n"));
+ bucket->lock.lock();
+
+ // At this point the hashtable could have rehashed under us.
+ if (hashtable.load() != myHashtable) {
+ bucket->lock.unlock();
+ continue;
+ }
+
+ ThreadData* threadData = functor();
+ bool result;
+ if (threadData) {
+ if (verbose)
+ dataLog(toString(currentThread(), ": proceeding to enqueue ", RawPointer(threadData), "\n"));
+ bucket->enqueue(threadData);
+ result = true;
+ } else
+ result = false;
+ bucket->lock.unlock();
+ return result;
+ }
+}
+
+template<typename Functor>
+bool dequeue(const void* address, const Functor& functor)
+{
+ if (verbose)
+ dataLog(toString(currentThread(), ": dequeueing address ", RawPointer(address), "\n"));
+ unsigned hash = hashAddress(address);
+ if (verbose)
+ dataLog(toString(currentThread(), ": hash = ", hash, "\n"));
+
+ for (;;) {
+ Hashtable* myHashtable = hashtable.load();
+ if (!myHashtable) {
+ if (verbose)
+ dataLog(toString(currentThread(), ": no hashtable.\n"));
+ return false;
+ }
+ unsigned index = hash % myHashtable->size;
+ if (verbose)
+ dataLog(toString(currentThread(), ": index = ", index, "\n"));
+ Bucket* bucket = myHashtable->data[index].load();
+ if (!bucket) {
+ if (verbose)
+ dataLog(toString(currentThread(), ": no bucket at ", RawPointer(bucket), ".\n"));
+ return false;
+ }
+
+ if (verbose)
+ dataLog(toString(currentThread(), ": locking bucket at ", RawPointer(bucket), "\n"));
+ bucket->lock.lock();
+ if (verbose)
+ dataLog(toString(currentThread(), ": locked bucket at ", RawPointer(bucket), "\n"));
+
+ // At this point the hashtable could have rehashed under us.
+ if (hashtable.load() != myHashtable) {
+ if (verbose)
+ dataLog(toString(currentThread(), ": hashtable changed.\n"));
+ bucket->lock.unlock();
+ continue;
+ }
+
+ if (verbose)
+ dataLog(toString(currentThread(), ": found bucket.\n"));
+ bucket->genericDequeue(functor);
+ bool result = !!bucket->queueHead;
+ bucket->lock.unlock();
+ return result;
+ }
+}
+
+} // anonymous namespace
+
+bool ParkingLot::parkConditionally(const void* address, std::function<bool()> validation)
+{
+ if (verbose)
+ dataLog(toString(currentThread(), ": parking.\n"));
+
+ ThreadData* me = myThreadData();
+
+ ASSERT(!me->shouldPark);
+
+ bool result = enqueue(
+ address,
+ [&] () -> ThreadData* {
+ if (!validation())
+ return nullptr;
+
+ me->address = address;
+ me->shouldPark = true;
+ return me;
+ });
+
+ if (!result)
+ return false;
+
+ if (verbose)
+ dataLog(toString(currentThread(), ": parking self: ", RawPointer(me), "\n"));
+ {
+ std::unique_lock<std::mutex> locker(me->parkingLock);
+ while (me->shouldPark)
+ me->parkingCondition.wait(locker);
+
+ me->address = nullptr;
+ }
+ if (verbose)
+ dataLog(toString(currentThread(), ": unparked self: ", RawPointer(me), "\n"));
+ return true;
+}
+
+bool ParkingLot::unparkOne(const void* address)
+{
+ if (verbose)
+ dataLog(toString(currentThread(), ": unparking one.\n"));
+
+ ThreadData* threadData = nullptr;
+ bool result = dequeue(
+ address,
+ [&] (ThreadData* element) {
+ if (element->address != address)
+ return DequeueResult::Ignore;
+ threadData = element;
+ return DequeueResult::RemoveAndStop;
+ });
+
+ if (!threadData)
+ return false;
+
+ ASSERT(threadData->shouldPark);
+
+ {
+ std::unique_lock<std::mutex> locker(threadData->parkingLock);
+ threadData->shouldPark = false;
+ threadData->parkingCondition.notify_all();
+ }
+
+ return result;
+}
+
+void ParkingLot::unparkAll(const void* address)
+{
+ if (verbose)
+ dataLog(toString(currentThread(), ": unparking all from ", RawPointer(address), ".\n"));
+
+ Vector<ThreadData*, 8> threadDatas;
+ dequeue(
+ address,
+ [&] (ThreadData* element) {
+ if (verbose)
+ dataLog(toString(currentThread(), ": Observing element with address = ", RawPointer(element->address), "\n"));
+ if (element->address != address)
+ return DequeueResult::Ignore;
+ threadDatas.append(element);
+ return DequeueResult::RemoveAndContinue;
+ });
+
+ for (ThreadData* threadData : threadDatas) {
+ if (verbose)
+ dataLog(toString(currentThread(), ": unparking ", RawPointer(threadData), " with address ", RawPointer(threadData->address), "\n"));
+ ASSERT(threadData->shouldPark);
+ std::unique_lock<std::mutex> locker(threadData->parkingLock);
+ threadData->shouldPark = false;
+ threadData->parkingCondition.notify_all();
+ }
+
+ if (verbose)
+ dataLog(toString(currentThread(), ": done unparking.\n"));
+}
+
+void ParkingLot::forEach(std::function<void(ThreadIdentifier, const void*)> callback)
+{
+ Vector<Bucket*> bucketsToUnlock = lockHashtable();
+
+ Hashtable* currentHashtable = hashtable.load();
+ for (unsigned i = currentHashtable->size; i--;) {
+ Bucket* bucket = currentHashtable->data[i].load();
+ if (!bucket)
+ continue;
+ for (ThreadData* currentThreadData = bucket->queueHead; currentThreadData; currentThreadData = currentThreadData->nextInQueue)
+ callback(currentThreadData->threadIdentifier, currentThreadData->address);
+ }
+
+ unlockHashtable(bucketsToUnlock);
+}
+
+} // namespace WTF
+
</ins></span></pre></div>
<a id="trunkSourceWTFwtfParkingLoth"></a>
<div class="addfile"><h4>Added: trunk/Source/WTF/wtf/ParkingLot.h (0 => 188280)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/ParkingLot.h (rev 0)
+++ trunk/Source/WTF/wtf/ParkingLot.h 2015-08-11 19:51:35 UTC (rev 188280)
</span><span class="lines">@@ -0,0 +1,86 @@
</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_ParkingLot_h
+#define WTF_ParkingLot_h
+
+#include <functional>
+#include <wtf/Atomics.h>
+#include <wtf/Threading.h>
+
+namespace WTF {
+
+class ParkingLot {
+ ParkingLot() = delete;
+ ParkingLot(const ParkingLot&) = delete;
+
+public:
+ // Parks the thread in a queue associated with the given address, which cannot be null. The
+ // parking only succeeds if the validation function returns true while the queue lock is held.
+ // Returns true if the thread actually slept, or false if it returned quickly because of
+ // validation failure.
+ WTF_EXPORT_PRIVATE static bool parkConditionally(const void* address, std::function<bool()> validation);
+
+ template<typename T, typename U>
+ static bool compareAndPark(const Atomic<T>* address, U expected)
+ {
+ return parkConditionally(
+ address,
+ [address, expected] () -> bool {
+ U value = address->load();
+ return value == expected;
+ });
+ }
+
+ // Unparks one thread from the queue associated with the given address, which cannot be null.
+ // Returns true if there may still be other threads on that queue, or false if there definitely
+ // are no more threads on the queue.
+ WTF_EXPORT_PRIVATE static bool unparkOne(const void* address);
+
+ // Unparks every thread from the queue associated with the given address, which cannot be null.
+ WTF_EXPORT_PRIVATE static void unparkAll(const void* address);
+
+ // Locks the parking lot and walks all of the parked threads and the addresses they are waiting
+ // on. Threads that are on the same queue are guaranteed to be walked from first to last, but the
+ // queues may be randomly interleaved. For example, if the queue for address A1 has T1 and T2 and
+ // the queue for address A2 has T3 and T4, then you might see iteration orders like:
+ //
+ // A1,T1 A1,T2 A2,T3 A2,T4
+ // A2,T3 A2,T4 A1,T1 A1,T2
+ // A1,T1 A2,T3 A1,T2 A2,T4
+ // A1,T1 A2,T3 A2,T4 A1,T2
+ //
+ // As well as many other possible interleaves that all have T1 before T2 and T3 before T4 but are
+ // otherwise unconstrained. This method is useful primarily for debugging. It's also used by unit
+ // tests.
+ WTF_EXPORT_PRIVATE static void forEach(std::function<void(ThreadIdentifier, const void*)>);
+};
+
+} // namespace WTF
+
+using WTF::ParkingLot;
+
+#endif // WTF_ParkingLot_h
+
</ins></span></pre></div>
<a id="trunkToolsChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Tools/ChangeLog (188279 => 188280)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/ChangeLog 2015-08-11 19:48:50 UTC (rev 188279)
+++ trunk/Tools/ChangeLog 2015-08-11 19:51:35 UTC (rev 188280)
</span><span class="lines">@@ -1,3 +1,18 @@
</span><ins>+2015-08-10 Filip Pizlo <fpizlo@apple.com>
+
+ WTF should have a ParkingLot for parking sleeping threads, so that locks can fit in 1.6 bits
+ https://bugs.webkit.org/show_bug.cgi?id=147665
+
+ Reviewed by Mark Lam.
+
+ * TestWebKitAPI/CMakeLists.txt:
+ * TestWebKitAPI/TestWebKitAPI.vcxproj/TestWebKitAPI.vcxproj:
+ * TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:
+ * TestWebKitAPI/Tests/WTF/Lock.cpp:
+ (TestWebKitAPI::TEST):
+ * TestWebKitAPI/Tests/WTF/ParkingLot.cpp: Added.
+ (TestWebKitAPI::TEST):
+
</ins><span class="cx"> 2015-08-11 Brian Burg <bburg@apple.com>
</span><span class="cx">
</span><span class="cx"> webkit-patch should not explode when $EDITOR is set incorrectly
</span></span></pre></div>
<a id="trunkToolsTestWebKitAPICMakeListstxt"></a>
<div class="modfile"><h4>Modified: trunk/Tools/TestWebKitAPI/CMakeLists.txt (188279 => 188280)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/TestWebKitAPI/CMakeLists.txt 2015-08-11 19:48:50 UTC (rev 188279)
+++ trunk/Tools/TestWebKitAPI/CMakeLists.txt 2015-08-11 19:51:35 UTC (rev 188280)
</span><span class="lines">@@ -56,6 +56,7 @@
</span><span class="cx"> ${TESTWEBKITAPI_DIR}/Tests/WTF/MediaTime.cpp
</span><span class="cx"> ${TESTWEBKITAPI_DIR}/Tests/WTF/MetaAllocator.cpp
</span><span class="cx"> ${TESTWEBKITAPI_DIR}/Tests/WTF/NakedPtr.cpp
</span><ins>+ ${TESTWEBKITAPI_DIR}/Tests/WTF/ParkingLot.cpp
</ins><span class="cx"> ${TESTWEBKITAPI_DIR}/Tests/WTF/RedBlackTree.cpp
</span><span class="cx"> ${TESTWEBKITAPI_DIR}/Tests/WTF/Ref.cpp
</span><span class="cx"> ${TESTWEBKITAPI_DIR}/Tests/WTF/RefPtr.cpp
</span></span></pre></div>
<a id="trunkToolsTestWebKitAPITestWebKitAPIvcxprojTestWebKitAPIvcxproj"></a>
<div class="modfile"><h4>Modified: trunk/Tools/TestWebKitAPI/TestWebKitAPI.vcxproj/TestWebKitAPI.vcxproj (188279 => 188280)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/TestWebKitAPI/TestWebKitAPI.vcxproj/TestWebKitAPI.vcxproj 2015-08-11 19:48:50 UTC (rev 188279)
+++ trunk/Tools/TestWebKitAPI/TestWebKitAPI.vcxproj/TestWebKitAPI.vcxproj 2015-08-11 19:51:35 UTC (rev 188280)
</span><span class="lines">@@ -326,6 +326,7 @@
</span><span class="cx"> <ClCompile Include="..\Tests\WTF\MetaAllocator.cpp" />
</span><span class="cx"> <ClCompile Include="..\Tests\WTF\NakedPtr.cpp" />
</span><span class="cx"> <ClCompile Include="..\Tests\WTF\Optional.cpp" />
</span><ins>+ <ClCompile Include="..\Tests\WTF\ParkingLot.cpp" />
</ins><span class="cx"> <ClCompile Include="..\Tests\WTF\RedBlackTree.cpp" />
</span><span class="cx"> <ClCompile Include="..\Tests\WTF\Ref.cpp" />
</span><span class="cx"> <ClCompile Include="..\Tests\WTF\RefCounter.cpp" />
</span></span></pre></div>
<a id="trunkToolsTestWebKitAPITestWebKitAPIxcodeprojprojectpbxproj"></a>
<div class="modfile"><h4>Modified: trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj (188279 => 188280)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj 2015-08-11 19:48:50 UTC (rev 188279)
+++ trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj 2015-08-11 19:51:35 UTC (rev 188280)
</span><span class="lines">@@ -11,6 +11,7 @@
</span><span class="cx"> 0F139E781A423A6B00F590F5 /* PlatformUtilitiesCocoa.mm in Sources */ = {isa = PBXBuildFile; fileRef = 0F139E721A423A2B00F590F5 /* PlatformUtilitiesCocoa.mm */; };
</span><span class="cx"> 0F139E791A42457000F590F5 /* PlatformUtilitiesCocoa.mm in Sources */ = {isa = PBXBuildFile; fileRef = 0F139E721A423A2B00F590F5 /* PlatformUtilitiesCocoa.mm */; };
</span><span class="cx"> 0F3B94A71A77267400DE3272 /* WKWebViewEvaluateJavaScript.mm in Sources */ = {isa = PBXBuildFile; fileRef = 0F3B94A51A77266C00DE3272 /* WKWebViewEvaluateJavaScript.mm */; };
</span><ins>+ 0FE447991B76F1EB009498EB /* ParkingLot.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FE447971B76F1E3009498EB /* ParkingLot.cpp */; };
</ins><span class="cx"> 0FFC45A61B73EBEB0085BD62 /* Lock.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FFC45A41B73EBE20085BD62 /* Lock.cpp */; };
</span><span class="cx"> 1A02C870125D4CFD00E3F4BD /* find.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = 1A02C84B125D4A5E00E3F4BD /* find.html */; };
</span><span class="cx"> 1A50AA201A2A51FC00F4C345 /* close-from-within-create-page.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = 1A50AA1F1A2A4EA500F4C345 /* close-from-within-create-page.html */; };
</span><span class="lines">@@ -429,6 +430,7 @@
</span><span class="cx"> 0F3B94A51A77266C00DE3272 /* WKWebViewEvaluateJavaScript.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = WKWebViewEvaluateJavaScript.mm; sourceTree = "<group>"; };
</span><span class="cx"> 0FC6C4CB141027E0005B7F0C /* RedBlackTree.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = RedBlackTree.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 0FC6C4CE141034AD005B7F0C /* MetaAllocator.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = MetaAllocator.cpp; sourceTree = "<group>"; };
</span><ins>+ 0FE447971B76F1E3009498EB /* ParkingLot.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ParkingLot.cpp; sourceTree = "<group>"; };
</ins><span class="cx"> 0FFC45A41B73EBE20085BD62 /* Lock.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Lock.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 14464012167A8305000BD218 /* LayoutUnit.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LayoutUnit.cpp; sourceTree = "<group>"; };
</span><span class="cx"> 14F3B11215E45EAB00210069 /* SaturatedArithmeticOperations.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = SaturatedArithmeticOperations.cpp; sourceTree = "<group>"; };
</span><span class="lines">@@ -1106,6 +1108,7 @@
</span><span class="cx"> 93A427AC180DA60F00CD24D7 /* MoveOnly.h */,
</span><span class="cx"> FEB6F74E1B2BA44E009E4922 /* NakedPtr.cpp */,
</span><span class="cx"> 1AFDE6541953B2C000C48FFA /* Optional.cpp */,
</span><ins>+ 0FE447971B76F1E3009498EB /* ParkingLot.cpp */,
</ins><span class="cx"> 0FC6C4CB141027E0005B7F0C /* RedBlackTree.cpp */,
</span><span class="cx"> 93A427AA180DA26400CD24D7 /* Ref.cpp */,
</span><span class="cx"> 86BD19971A2DB05B006DCF0A /* RefCounter.cpp */,
</span><span class="lines">@@ -1626,6 +1629,7 @@
</span><span class="cx"> 7CCE7ED71A411A7E00447C4C /* WillPerformClientRedirectToURLCrash.mm in Sources */,
</span><span class="cx"> 7CCE7F1C1A411AE600447C4C /* WillSendSubmitEvent.cpp in Sources */,
</span><span class="cx"> 7CCE7ED81A411A7E00447C4C /* WillSendSubmitEvent.mm in Sources */,
</span><ins>+ 0FE447991B76F1EB009498EB /* ParkingLot.cpp in Sources */,
</ins><span class="cx"> 7CCE7ED91A411A7E00447C4C /* WindowlessWebViewWithMedia.mm in Sources */,
</span><span class="cx"> 7CCE7F2E1A411B1000447C4C /* WKBrowsingContextGroupTest.mm in Sources */,
</span><span class="cx"> 7CCE7F2F1A411B1000447C4C /* WKBrowsingContextLoadDelegateTest.mm in Sources */,
</span></span></pre></div>
<a id="trunkToolsTestWebKitAPITestsWTFLockcpp"></a>
<div class="modfile"><h4>Modified: trunk/Tools/TestWebKitAPI/Tests/WTF/Lock.cpp (188279 => 188280)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/TestWebKitAPI/Tests/WTF/Lock.cpp 2015-08-11 19:48:50 UTC (rev 188279)
+++ trunk/Tools/TestWebKitAPI/Tests/WTF/Lock.cpp 2015-08-11 19:51:35 UTC (rev 188280)
</span><span class="lines">@@ -24,6 +24,7 @@
</span><span class="cx"> */
</span><span class="cx">
</span><span class="cx"> #include "config.h"
</span><ins>+#include <wtf/ByteLock.h>
</ins><span class="cx"> #include <wtf/Lock.h>
</span><span class="cx"> #include <wtf/Threading.h>
</span><span class="cx"> #include <wtf/ThreadingPrimitives.h>
</span><span class="lines">@@ -97,4 +98,39 @@
</span><span class="cx"> runLockTest<Lock>(10, 10, 10000, 1000);
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+TEST(WTF_ByteLock, UncontentedShortSection)
+{
+ runLockTest<ByteLock>(1, 1, 1, 10000000);
+}
+
+TEST(WTF_ByteLock, UncontentedLongSection)
+{
+ runLockTest<ByteLock>(1, 1, 10000, 1000);
+}
+
+TEST(WTF_ByteLock, ContentedShortSection)
+{
+ runLockTest<ByteLock>(1, 10, 1, 10000000);
+}
+
+TEST(WTF_ByteLock, ContentedLongSection)
+{
+ runLockTest<ByteLock>(1, 10, 10000, 10000);
+}
+
+TEST(WTF_ByteLock, ManyContentedShortSections)
+{
+ runLockTest<ByteLock>(10, 10, 1, 500000);
+}
+
+TEST(WTF_ByteLock, ManyContentedLongSections)
+{
+ runLockTest<ByteLock>(10, 10, 10000, 1000);
+}
+
+TEST(WTF_ByteLock, SectionAddressCollision)
+{
+ runLockTest<ByteLock>(4, 2, 10000, 2000);
+}
+
</ins><span class="cx"> } // namespace TestWebKitAPI
</span></span></pre></div>
<a id="trunkToolsTestWebKitAPITestsWTFParkingLotcpp"></a>
<div class="addfile"><h4>Added: trunk/Tools/TestWebKitAPI/Tests/WTF/ParkingLot.cpp (0 => 188280)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/TestWebKitAPI/Tests/WTF/ParkingLot.cpp (rev 0)
+++ trunk/Tools/TestWebKitAPI/Tests/WTF/ParkingLot.cpp 2015-08-11 19:51:35 UTC (rev 188280)
</span><span class="lines">@@ -0,0 +1,271 @@
</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. AND ITS CONTRIBUTORS ``AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+#include <condition_variable>
+#include <mutex>
+#include <wtf/HashSet.h>
+#include <wtf/ListDump.h>
+#include <wtf/ParkingLot.h>
+#include <wtf/Threading.h>
+#include <wtf/ThreadingPrimitives.h>
+
+using namespace WTF;
+
+namespace TestWebKitAPI {
+
+namespace {
+
+struct SingleLatchTest {
+ void initialize(unsigned numThreads)
+ {
+ // This implements a fair (FIFO) semaphore, and it starts out unavailable.
+ semaphore.store(0);
+
+ for (unsigned i = numThreads; i--;) {
+ threads.append(
+ createThread(
+ "Parking Test Thread",
+ [&] () {
+ EXPECT_NE(0u, currentThread());
+
+ down();
+
+ std::lock_guard<std::mutex> locker(lock);
+ awake.add(currentThread());
+ lastAwoken = currentThread();
+ condition.notify_one();
+ }));
+ }
+ }
+
+ void unparkOne(unsigned singleUnparkIndex)
+ {
+ EXPECT_EQ(0u, lastAwoken);
+
+ unsigned numWaitingOnAddress = 0;
+ Vector<ThreadIdentifier, 8> queue;
+ ParkingLot::forEach(
+ [&] (ThreadIdentifier threadIdentifier, const void* address) {
+ if (address != &semaphore)
+ return;
+
+ queue.append(threadIdentifier);
+
+ numWaitingOnAddress++;
+ });
+
+ EXPECT_LE(numWaitingOnAddress, threads.size() - singleUnparkIndex);
+
+ up();
+
+ {
+ std::unique_lock<std::mutex> locker(lock);
+ while (awake.size() < singleUnparkIndex + 1)
+ condition.wait(locker);
+ EXPECT_NE(0u, lastAwoken);
+ if (!queue.isEmpty() && queue[0] != lastAwoken) {
+ dataLog("Woke up wrong thread: queue = ", listDump(queue), ", last awoken = ", lastAwoken, "\n");
+ EXPECT_EQ(queue[0], lastAwoken);
+ }
+ lastAwoken = 0;
+ }
+ }
+
+ void finish(unsigned numSingleUnparks)
+ {
+ unsigned numWaitingOnAddress = 0;
+ ParkingLot::forEach(
+ [&] (ThreadIdentifier, const void* address) {
+ if (address != &semaphore)
+ return;
+
+ numWaitingOnAddress++;
+ });
+
+ EXPECT_LE(numWaitingOnAddress, threads.size() - numSingleUnparks);
+
+ semaphore.store(threads.size() - numSingleUnparks);
+ ParkingLot::unparkAll(&semaphore);
+
+ numWaitingOnAddress = 0;
+ ParkingLot::forEach(
+ [&] (ThreadIdentifier, const void* address) {
+ if (address != &semaphore)
+ return;
+
+ numWaitingOnAddress++;
+ });
+
+ EXPECT_EQ(0u, numWaitingOnAddress);
+
+ {
+ std::unique_lock<std::mutex> locker(lock);
+ while (awake.size() < threads.size())
+ condition.wait(locker);
+ }
+
+ for (ThreadIdentifier threadIdentifier : threads)
+ waitForThreadCompletion(threadIdentifier);
+ }
+
+ // Semaphore operations.
+ void down()
+ {
+ for (;;) {
+ int oldSemaphoreValue = semaphore.load();
+ int newSemaphoreValue = oldSemaphoreValue - 1;
+ if (!semaphore.compareExchangeWeak(oldSemaphoreValue, newSemaphoreValue))
+ continue;
+
+ if (oldSemaphoreValue > 0) {
+ // We acquired the semaphore. Done.
+ return;
+ }
+
+ // We need to wait.
+ if (ParkingLot::compareAndPark(&semaphore, newSemaphoreValue)) {
+ // We did wait, and then got woken up. This means that someone who up'd the semaphore
+ // passed ownership onto us.
+ return;
+ }
+
+ // We never parked, because the semaphore value changed. Undo our decrement and try again.
+ for (;;) {
+ int oldSemaphoreValue = semaphore.load();
+ if (semaphore.compareExchangeWeak(oldSemaphoreValue, oldSemaphoreValue + 1))
+ break;
+ }
+ }
+ }
+ void up()
+ {
+ int oldSemaphoreValue;
+ for (;;) {
+ oldSemaphoreValue = semaphore.load();
+ if (semaphore.compareExchangeWeak(oldSemaphoreValue, oldSemaphoreValue + 1))
+ break;
+ }
+
+ // Check if anyone was waiting on the semaphore. If they were, then pass ownership to them.
+ if (oldSemaphoreValue < 0)
+ ParkingLot::unparkOne(&semaphore);
+ }
+
+ Atomic<int> semaphore;
+ std::mutex lock;
+ std::condition_variable condition;
+ HashSet<ThreadIdentifier> awake;
+ Vector<ThreadIdentifier> threads;
+ ThreadIdentifier lastAwoken { 0 };
+};
+
+void runParkingTest(unsigned numLatches, unsigned delay, unsigned numThreads, unsigned numSingleUnparks)
+{
+ std::unique_ptr<SingleLatchTest[]> tests = std::make_unique<SingleLatchTest[]>(numLatches);
+
+ for (unsigned latchIndex = numLatches; latchIndex--;)
+ tests[latchIndex].initialize(numThreads);
+
+ for (unsigned unparkIndex = 0; unparkIndex < numSingleUnparks; ++unparkIndex) {
+ usleep(delay);
+ for (unsigned latchIndex = numLatches; latchIndex--;)
+ tests[latchIndex].unparkOne(unparkIndex);
+ }
+
+ for (unsigned latchIndex = numLatches; latchIndex--;)
+ tests[latchIndex].finish(numSingleUnparks);
+}
+
+void repeatParkingTest(unsigned numRepeats, unsigned numLatches, unsigned delay, unsigned numThreads, unsigned numSingleUnparks)
+{
+ while (numRepeats--)
+ runParkingTest(numLatches, delay, numThreads, numSingleUnparks);
+}
+
+} // anonymous namespace
+
+TEST(WTF_ParkingLot, UnparkAllOneFast)
+{
+ repeatParkingTest(10000, 1, 0, 1, 0);
+}
+
+TEST(WTF_ParkingLot, UnparkAllHundredFast)
+{
+ repeatParkingTest(1000, 1, 0, 100, 0);
+}
+
+TEST(WTF_ParkingLot, UnparkOneOneFast)
+{
+ repeatParkingTest(1000, 1, 0, 1, 1);
+}
+
+TEST(WTF_ParkingLot, UnparkOneHundredFast)
+{
+ repeatParkingTest(100, 1, 0, 100, 100);
+}
+
+TEST(WTF_ParkingLot, UnparkOneFiftyThenFiftyAllFast)
+{
+ repeatParkingTest(200, 1, 0, 100, 50);
+}
+
+TEST(WTF_ParkingLot, UnparkAllOne)
+{
+ repeatParkingTest(100, 1, 10000, 1, 0);
+}
+
+TEST(WTF_ParkingLot, UnparkAllHundred)
+{
+ repeatParkingTest(100, 1, 10000, 100, 0);
+}
+
+TEST(WTF_ParkingLot, UnparkOneOne)
+{
+ repeatParkingTest(10, 1, 10000, 1, 1);
+}
+
+TEST(WTF_ParkingLot, UnparkOneHundred)
+{
+ repeatParkingTest(1, 1, 10000, 100, 100);
+}
+
+TEST(WTF_ParkingLot, UnparkOneFiftyThenFiftyAll)
+{
+ repeatParkingTest(2, 1, 10000, 100, 50);
+}
+
+TEST(WTF_ParkingLot, HundredUnparkAllOneFast)
+{
+ repeatParkingTest(100, 100, 0, 1, 0);
+}
+
+TEST(WTF_ParkingLot, HundredUnparkAllOne)
+{
+ repeatParkingTest(1, 100, 10000, 1, 0);
+}
+
+} // namespace TestWebKitAPI
+
</ins></span></pre>
</div>
</div>
</body>
</html>