<!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>[203350] 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/203350">203350</a></dd>
<dt>Author</dt> <dd>fpizlo@apple.com</dd>
<dt>Date</dt> <dd>2016-07-18 11:32:52 -0700 (Mon, 18 Jul 2016)</dd>
</dl>
<h3>Log Message</h3>
<pre>WTF::Lock should be fair eventually
https://bugs.webkit.org/show_bug.cgi?id=159384
Reviewed by Geoffrey Garen.
Source/WTF:
In https://webkit.org/blog/6161/locking-in-webkit/ we showed how relaxing the fairness of
locks makes them fast. That post presented lock fairness as a trade-off between two
extremes:
- Barging. A barging lock, like WTF::Lock, releases the lock in unlock() even if there was a
thread on the queue. If there was a thread on the queue, the lock is released and that
thread is made runnable. That thread may then grab the lock, or some other thread may grab
the lock first (it may barge). Usually, the barging thread is the thread that released the
lock in the first place. This maximizes throughput but hurts fairness. There is no good
theoretical bound on how unfair the lock may become, but empirical data suggests that it's
fair enough for the cases we previously measured.
- FIFO. A FIFO lock, like HandoffLock in ToyLocks.h, does not release the lock in unlock()
if there is a thread waiting. If there is a thread waiting, unlock() will make that thread
runnable and inform it that it now holds the lock. This ensures perfect round-robin
fairness and allows us to reason theoretically about how long it may take for a thread to
grab the lock. For example, if we know that only N threads are running and each one may
contend on a critical section, and each one may hold the lock for at most S seconds, then
the time it takes to grab the lock is N * S. Unfortunately, FIFO locks perform very badly
in most cases. This is because for the common case of short critical sections, they force
a context switch after each critical section if the lock is contended.
This change makes WTF::Lock almost as fair as FIFO while still being as fast as barging.
Thanks to this new algorithm, you can now have both of these things at the same time.
This change makes WTF::Lock eventually fair. We can almost (more on the caveats below)
guarantee that the time it takes to grab a lock is N * max(1ms, S). In other words, critical
sections that are longer than 1ms are always fair. For shorter critical sections, the amount
of time that any thread waits is 1ms times the number of threads. There are some caveats
that arise from our use of randomness, but even then, in the limit as the critical section
length goes to infinity, the lock becomes fair. The corner cases are unlikely to happen; our
experiments show that the lock becomes exactly as fair as a FIFO lock for any critical
section that is 1ms or longer.
The fairness mechanism is broken into two parts. WTF::Lock can now choose to unlock a lock
fairly or unfairly thanks to the new ParkingLot token mechanism. WTF::Lock knows when to use
fair unlocking based on a timeout mechanism in ParkingLot called timeToBeFair.
ParkingLot::unparkOne() and ParkingLot::parkConditionally() can now communicate with each
other via a token. unparkOne() can pass a token, which parkConditionally() will return. This
change also makes parkConditionally() a lot more precise about when it was unparked due to a
call to unparkOne(). If unparkOne() is told that a thread was unparked then this thread is
guaranteed to report that it was unparked rather than timing out, and that thread is
guaranteed to get the token that unparkOne() passed. The token is an intptr_t. We use it as
a boolean variable in WTF::Lock, but you could use it to pass arbitrary data structures. By
default, the token is zero. WTF::Lock's unlock() will pass 1 as the token if it is doing
fair unlocking. In that case, unlock() will not release the lock, and lock() will know that
it holds the lock as soon as parkConditionally() returns. Note that this algorithm relies
on unparkOne() invoking WTF::Lock's callback while the queue lock is held, so that WTF::Lock
can make a decision about unlock strategy and inject a token while it has complete knowledge
over the state of the queue. As such, it's not immediately obvious how to implement this
algorithm on top of futexes. You really need ParkingLot!
WTF::Lock does not use fair unlocking every time. We expose a new API, Lock::unlockFairly(),
which forces the fair unlocking behavior. Additionally, ParkingLot now maintains a
per-bucket stochastic fairness timeout. When the timeout fires, the unparkOne() callback
sees UnparkResult::timeToBeFair = true. This timeout is set to be anywhere from 0ms to 1ms
at random. When a dequeue happens and there are threads that actually get dequeued, we check
if the time since the last unfair unlock (the last time timeToBeFair was set to true) is
more than the timeout amount. If so, then we set timeToBeFair to true and reset the timeout.
This means that in the absence of ParkingLot collisions, unfair unlocking is guaranteed to
happen at least once per millisecond. It will happen at 2 KHz on average. If there are
collisions, then each collision adds one millisecond to the worst case (and 0.5 ms to the
average case). The reason why we don't just use a fixed 1ms timeout is that we want to avoid
resonance. Imagine a program in which some thread acquires a lock at 1 KHz in-phase with the
timeToBeFair timeout. Then this thread would be the benefactor of fairness to the detriment
of everyone else. Randomness ensures that we aren't too fair to any one thread.
Empirically, this is neutral on our major benchmarks like JetStream but it's an enormous
improvement in LockFairnessTest. It's common for an unfair lock (either our BargingLock, the
old WTF::Lock, any of the other futex-based locks that barge, or new os_unfair_lock) to
allow only one thread to hold the lock during a whole second in which each thread is holding
the lock for 1ms at a time. This is because in a barging lock, releasing a lock after
holding it for 1ms and then reacquiring it immediately virtually ensures that none of the
other threads can wake up in time to grab it before it's relocked. But the new WTF::Lock
handles this case like a champ: each thread gets equal turns.
Here's some data. If we launch 10 threads and have each of them run for 1 second while
repeatedly holding a critical section for 1ms, then here's how many times each thread gets
to hold the lock using the old WTF::Lock algorithm:
799, 6, 1, 1, 1, 1, 1, 1, 1, 1
One thread hogged the lock for almost the whole time! With the new WTF::Lock, the lock
becomes totally fair:
80, 79, 79, 79, 79, 79, 79, 80, 80, 79
I don't know of anyone creating such an automatically-fair adaptive lock before, so I think
that this is a pretty awesome advancement to the state of the art!
This change is good for three reasons:
- We do have long critical sections in WebKit and we don't want to have to worry about
starvation. This reduces the likelihood that we will see starvation due to our lock
strategy.
- I was talking to ggaren about bmalloc's locking needs, and he wanted unlockFairly() or
lockFairly() or some moral equivalent for the scavenger thread.
- If we use a WTF::Lock to manage heap access in a multithreaded GC, we'll need the ability
to unlock and relock without barging.
* benchmarks/LockFairnessTest.cpp:
(main):
* benchmarks/ToyLocks.h:
* wtf/Condition.h:
(WTF::ConditionBase::waitUntil):
(WTF::ConditionBase::notifyOne):
* wtf/Lock.cpp:
(WTF::LockBase::lockSlow):
(WTF::LockBase::unlockSlow):
(WTF::LockBase::unlockFairlySlow):
(WTF::LockBase::unlockSlowImpl):
* wtf/Lock.h:
(WTF::LockBase::try_lock):
(WTF::LockBase::unlock):
(WTF::LockBase::unlockFairly):
(WTF::LockBase::isHeld):
(WTF::LockBase::isFullyReset):
* wtf/ParkingLot.cpp:
(WTF::ParkingLot::parkConditionallyImpl):
(WTF::ParkingLot::unparkOne):
(WTF::ParkingLot::unparkOneImpl):
(WTF::ParkingLot::unparkAll):
* wtf/ParkingLot.h:
(WTF::ParkingLot::parkConditionally):
(WTF::ParkingLot::compareAndPark):
(WTF::ParkingLot::unparkOne):
Tools:
* TestWebKitAPI/Tests/WTF/ParkingLot.cpp:</pre>
<h3>Modified Paths</h3>
<ul>
<li><a href="#trunkSourceWTFChangeLog">trunk/Source/WTF/ChangeLog</a></li>
<li><a href="#trunkSourceWTFbenchmarksLockFairnessTestcpp">trunk/Source/WTF/benchmarks/LockFairnessTest.cpp</a></li>
<li><a href="#trunkSourceWTFbenchmarksToyLocksh">trunk/Source/WTF/benchmarks/ToyLocks.h</a></li>
<li><a href="#trunkSourceWTFwtfConditionh">trunk/Source/WTF/wtf/Condition.h</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="#trunkSourceWTFwtfParkingLoth">trunk/Source/WTF/wtf/ParkingLot.h</a></li>
<li><a href="#trunkToolsChangeLog">trunk/Tools/ChangeLog</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="trunkSourceWTFChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/ChangeLog (203349 => 203350)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/ChangeLog 2016-07-18 17:43:26 UTC (rev 203349)
+++ trunk/Source/WTF/ChangeLog 2016-07-18 18:32:52 UTC (rev 203350)
</span><span class="lines">@@ -1,3 +1,140 @@
</span><ins>+2016-07-02 Filip Pizlo <fpizlo@apple.com>
+
+ WTF::Lock should be fair eventually
+ https://bugs.webkit.org/show_bug.cgi?id=159384
+
+ Reviewed by Geoffrey Garen.
+
+ In https://webkit.org/blog/6161/locking-in-webkit/ we showed how relaxing the fairness of
+ locks makes them fast. That post presented lock fairness as a trade-off between two
+ extremes:
+
+ - Barging. A barging lock, like WTF::Lock, releases the lock in unlock() even if there was a
+ thread on the queue. If there was a thread on the queue, the lock is released and that
+ thread is made runnable. That thread may then grab the lock, or some other thread may grab
+ the lock first (it may barge). Usually, the barging thread is the thread that released the
+ lock in the first place. This maximizes throughput but hurts fairness. There is no good
+ theoretical bound on how unfair the lock may become, but empirical data suggests that it's
+ fair enough for the cases we previously measured.
+
+ - FIFO. A FIFO lock, like HandoffLock in ToyLocks.h, does not release the lock in unlock()
+ if there is a thread waiting. If there is a thread waiting, unlock() will make that thread
+ runnable and inform it that it now holds the lock. This ensures perfect round-robin
+ fairness and allows us to reason theoretically about how long it may take for a thread to
+ grab the lock. For example, if we know that only N threads are running and each one may
+ contend on a critical section, and each one may hold the lock for at most S seconds, then
+ the time it takes to grab the lock is N * S. Unfortunately, FIFO locks perform very badly
+ in most cases. This is because for the common case of short critical sections, they force
+ a context switch after each critical section if the lock is contended.
+
+ This change makes WTF::Lock almost as fair as FIFO while still being as fast as barging.
+ Thanks to this new algorithm, you can now have both of these things at the same time.
+
+ This change makes WTF::Lock eventually fair. We can almost (more on the caveats below)
+ guarantee that the time it takes to grab a lock is N * max(1ms, S). In other words, critical
+ sections that are longer than 1ms are always fair. For shorter critical sections, the amount
+ of time that any thread waits is 1ms times the number of threads. There are some caveats
+ that arise from our use of randomness, but even then, in the limit as the critical section
+ length goes to infinity, the lock becomes fair. The corner cases are unlikely to happen; our
+ experiments show that the lock becomes exactly as fair as a FIFO lock for any critical
+ section that is 1ms or longer.
+
+ The fairness mechanism is broken into two parts. WTF::Lock can now choose to unlock a lock
+ fairly or unfairly thanks to the new ParkingLot token mechanism. WTF::Lock knows when to use
+ fair unlocking based on a timeout mechanism in ParkingLot called timeToBeFair.
+
+ ParkingLot::unparkOne() and ParkingLot::parkConditionally() can now communicate with each
+ other via a token. unparkOne() can pass a token, which parkConditionally() will return. This
+ change also makes parkConditionally() a lot more precise about when it was unparked due to a
+ call to unparkOne(). If unparkOne() is told that a thread was unparked then this thread is
+ guaranteed to report that it was unparked rather than timing out, and that thread is
+ guaranteed to get the token that unparkOne() passed. The token is an intptr_t. We use it as
+ a boolean variable in WTF::Lock, but you could use it to pass arbitrary data structures. By
+ default, the token is zero. WTF::Lock's unlock() will pass 1 as the token if it is doing
+ fair unlocking. In that case, unlock() will not release the lock, and lock() will know that
+ it holds the lock as soon as parkConditionally() returns. Note that this algorithm relies
+ on unparkOne() invoking WTF::Lock's callback while the queue lock is held, so that WTF::Lock
+ can make a decision about unlock strategy and inject a token while it has complete knowledge
+ over the state of the queue. As such, it's not immediately obvious how to implement this
+ algorithm on top of futexes. You really need ParkingLot!
+
+ WTF::Lock does not use fair unlocking every time. We expose a new API, Lock::unlockFairly(),
+ which forces the fair unlocking behavior. Additionally, ParkingLot now maintains a
+ per-bucket stochastic fairness timeout. When the timeout fires, the unparkOne() callback
+ sees UnparkResult::timeToBeFair = true. This timeout is set to be anywhere from 0ms to 1ms
+ at random. When a dequeue happens and there are threads that actually get dequeued, we check
+ if the time since the last unfair unlock (the last time timeToBeFair was set to true) is
+ more than the timeout amount. If so, then we set timeToBeFair to true and reset the timeout.
+ This means that in the absence of ParkingLot collisions, unfair unlocking is guaranteed to
+ happen at least once per millisecond. It will happen at 2 KHz on average. If there are
+ collisions, then each collision adds one millisecond to the worst case (and 0.5 ms to the
+ average case). The reason why we don't just use a fixed 1ms timeout is that we want to avoid
+ resonance. Imagine a program in which some thread acquires a lock at 1 KHz in-phase with the
+ timeToBeFair timeout. Then this thread would be the benefactor of fairness to the detriment
+ of everyone else. Randomness ensures that we aren't too fair to any one thread.
+
+ Empirically, this is neutral on our major benchmarks like JetStream but it's an enormous
+ improvement in LockFairnessTest. It's common for an unfair lock (either our BargingLock, the
+ old WTF::Lock, any of the other futex-based locks that barge, or new os_unfair_lock) to
+ allow only one thread to hold the lock during a whole second in which each thread is holding
+ the lock for 1ms at a time. This is because in a barging lock, releasing a lock after
+ holding it for 1ms and then reacquiring it immediately virtually ensures that none of the
+ other threads can wake up in time to grab it before it's relocked. But the new WTF::Lock
+ handles this case like a champ: each thread gets equal turns.
+
+ Here's some data. If we launch 10 threads and have each of them run for 1 second while
+ repeatedly holding a critical section for 1ms, then here's how many times each thread gets
+ to hold the lock using the old WTF::Lock algorithm:
+
+ 799, 6, 1, 1, 1, 1, 1, 1, 1, 1
+
+ One thread hogged the lock for almost the whole time! With the new WTF::Lock, the lock
+ becomes totally fair:
+
+ 80, 79, 79, 79, 79, 79, 79, 80, 80, 79
+
+ I don't know of anyone creating such an automatically-fair adaptive lock before, so I think
+ that this is a pretty awesome advancement to the state of the art!
+
+ This change is good for three reasons:
+
+ - We do have long critical sections in WebKit and we don't want to have to worry about
+ starvation. This reduces the likelihood that we will see starvation due to our lock
+ strategy.
+
+ - I was talking to ggaren about bmalloc's locking needs, and he wanted unlockFairly() or
+ lockFairly() or some moral equivalent for the scavenger thread.
+
+ - If we use a WTF::Lock to manage heap access in a multithreaded GC, we'll need the ability
+ to unlock and relock without barging.
+
+ * benchmarks/LockFairnessTest.cpp:
+ (main):
+ * benchmarks/ToyLocks.h:
+ * wtf/Condition.h:
+ (WTF::ConditionBase::waitUntil):
+ (WTF::ConditionBase::notifyOne):
+ * wtf/Lock.cpp:
+ (WTF::LockBase::lockSlow):
+ (WTF::LockBase::unlockSlow):
+ (WTF::LockBase::unlockFairlySlow):
+ (WTF::LockBase::unlockSlowImpl):
+ * wtf/Lock.h:
+ (WTF::LockBase::try_lock):
+ (WTF::LockBase::unlock):
+ (WTF::LockBase::unlockFairly):
+ (WTF::LockBase::isHeld):
+ (WTF::LockBase::isFullyReset):
+ * wtf/ParkingLot.cpp:
+ (WTF::ParkingLot::parkConditionallyImpl):
+ (WTF::ParkingLot::unparkOne):
+ (WTF::ParkingLot::unparkOneImpl):
+ (WTF::ParkingLot::unparkAll):
+ * wtf/ParkingLot.h:
+ (WTF::ParkingLot::parkConditionally):
+ (WTF::ParkingLot::compareAndPark):
+ (WTF::ParkingLot::unparkOne):
+
</ins><span class="cx"> 2016-07-17 Myles C. Maxfield <mmaxfield@apple.com>
</span><span class="cx">
</span><span class="cx"> Support new emoji group candidates
</span></span></pre></div>
<a id="trunkSourceWTFbenchmarksLockFairnessTestcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/benchmarks/LockFairnessTest.cpp (203349 => 203350)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/benchmarks/LockFairnessTest.cpp 2016-07-18 17:43:26 UTC (rev 203349)
+++ trunk/Source/WTF/benchmarks/LockFairnessTest.cpp 2016-07-18 18:32:52 UTC (rev 203350)
</span><span class="lines">@@ -48,12 +48,13 @@
</span><span class="cx">
</span><span class="cx"> NO_RETURN void usage()
</span><span class="cx"> {
</span><del>- printf("Usage: LockFairnessTest yieldspinlock|pausespinlock|wordlock|lock|barginglock|bargingwordlock|thunderlock|thunderwordlock|cascadelock|cascadewordlockhandofflock|mutex|all <num threads> <seconds per test>\n");
</del><ins>+ printf("Usage: LockFairnessTest yieldspinlock|pausespinlock|wordlock|lock|barginglock|bargingwordlock|thunderlock|thunderwordlock|cascadelock|cascadewordlockhandofflock|mutex|all <num threads> <seconds per test> <microseconds in critical section>\n");
</ins><span class="cx"> exit(1);
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> unsigned numThreads;
</span><span class="cx"> double secondsPerTest;
</span><ins>+unsigned microsecondsInCriticalSection;
</ins><span class="cx">
</span><span class="cx"> struct Benchmark {
</span><span class="cx"> template<typename LockType>
</span><span class="lines">@@ -72,9 +73,19 @@
</span><span class="cx"> threads[threadIndex] = createThread(
</span><span class="cx"> "Benchmark Thread",
</span><span class="cx"> [&, threadIndex] () {
</span><ins>+ if (!microsecondsInCriticalSection) {
+ while (keepGoing) {
+ lock.lock();
+ counts[threadIndex]++;
+ lock.unlock();
+ }
+ return;
+ }
+
</ins><span class="cx"> while (keepGoing) {
</span><span class="cx"> lock.lock();
</span><span class="cx"> counts[threadIndex]++;
</span><ins>+ usleep(microsecondsInCriticalSection);
</ins><span class="cx"> lock.unlock();
</span><span class="cx"> }
</span><span class="cx"> });
</span><span class="lines">@@ -85,8 +96,8 @@
</span><span class="cx">
</span><span class="cx"> sleep(secondsPerTest);
</span><span class="cx">
</span><ins>+ keepGoing = false;
</ins><span class="cx"> lock.lock();
</span><del>- keepGoing = false;
</del><span class="cx">
</span><span class="cx"> dataLog(name, ": ");
</span><span class="cx"> CommaPrinter comma;
</span><span class="lines">@@ -106,9 +117,10 @@
</span><span class="cx"> {
</span><span class="cx"> WTF::initializeThreading();
</span><span class="cx">
</span><del>- if (argc != 4
</del><ins>+ if (argc != 5
</ins><span class="cx"> || sscanf(argv[2], "%u", &numThreads) != 1
</span><del>- || sscanf(argv[3], "%lf", &secondsPerTest) != 1)
</del><ins>+ || sscanf(argv[3], "%lf", &secondsPerTest) != 1
+ || sscanf(argv[4], "%u", &microsecondsInCriticalSection) != 1)
</ins><span class="cx"> usage();
</span><span class="cx">
</span><span class="cx"> runEverything<Benchmark>(argv[1]);
</span></span></pre></div>
<a id="trunkSourceWTFbenchmarksToyLocksh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/benchmarks/ToyLocks.h (203349 => 203350)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/benchmarks/ToyLocks.h 2016-07-18 17:43:26 UTC (rev 203349)
+++ trunk/Source/WTF/benchmarks/ToyLocks.h 2016-07-18 18:32:52 UTC (rev 203350)
</span><span class="lines">@@ -235,11 +235,12 @@
</span><span class="cx"> {
</span><span class="cx"> ParkingLot::unparkOne(
</span><span class="cx"> &m_state,
</span><del>- [this] (ParkingLot::UnparkResult result) {
</del><ins>+ [this] (ParkingLot::UnparkResult result) -> intptr_t {
</ins><span class="cx"> if (result.mayHaveMoreThreads)
</span><span class="cx"> m_state.store(hasParkedBit);
</span><span class="cx"> else
</span><span class="cx"> m_state.store(0);
</span><ins>+ return 0;
</ins><span class="cx"> });
</span><span class="cx"> }
</span><span class="cx">
</span><span class="lines">@@ -430,7 +431,7 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> if (m_state.compareExchangeWeak(state, state + parkedCountUnit)) {
</span><del>- bool result = ParkingLot::compareAndPark(&m_state, state + parkedCountUnit);
</del><ins>+ bool result = ParkingLot::compareAndPark(&m_state, state + parkedCountUnit).wasUnparked;
</ins><span class="cx"> m_state.exchangeAndAdd(-parkedCountUnit);
</span><span class="cx"> if (result)
</span><span class="cx"> return;
</span></span></pre></div>
<a id="trunkSourceWTFwtfConditionh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/Condition.h (203349 => 203350)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/Condition.h 2016-07-18 17:43:26 UTC (rev 203349)
+++ trunk/Source/WTF/wtf/Condition.h 2016-07-18 18:32:52 UTC (rev 203350)
</span><span class="lines">@@ -80,7 +80,7 @@
</span><span class="cx"> return true;
</span><span class="cx"> },
</span><span class="cx"> [&lock] () { lock.unlock(); },
</span><del>- timeout);
</del><ins>+ timeout).wasUnparked;
</ins><span class="cx"> }
</span><span class="cx"> lock.lock();
</span><span class="cx"> return result;
</span><span class="lines">@@ -180,9 +180,10 @@
</span><span class="cx">
</span><span class="cx"> ParkingLot::unparkOne(
</span><span class="cx"> &m_hasWaiters,
</span><del>- [this] (ParkingLot::UnparkResult result) {
</del><ins>+ [this] (ParkingLot::UnparkResult result) -> intptr_t {
</ins><span class="cx"> if (!result.mayHaveMoreThreads)
</span><span class="cx"> m_hasWaiters.store(false);
</span><ins>+ return 0;
</ins><span class="cx"> });
</span><span class="cx"> }
</span><span class="cx">
</span></span></pre></div>
<a id="trunkSourceWTFwtfLockcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/Lock.cpp (203349 => 203350)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/Lock.cpp 2016-07-18 17:43:26 UTC (rev 203349)
+++ trunk/Source/WTF/wtf/Lock.cpp 2016-07-18 18:32:52 UTC (rev 203350)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2015 Apple Inc. All rights reserved.
</del><ins>+ * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
</ins><span class="cx"> *
</span><span class="cx"> * Redistribution and use in source and binary forms, with or without
</span><span class="cx"> * modification, are permitted provided that the following conditions
</span><span class="lines">@@ -67,7 +67,22 @@
</span><span class="cx"> continue;
</span><span class="cx">
</span><span class="cx"> // We now expect the value to be isHeld|hasParked. So long as that's the case, we can park.
</span><del>- ParkingLot::compareAndPark(&m_byte, isHeldBit | hasParkedBit);
</del><ins>+ ParkingLot::ParkResult parkResult =
+ ParkingLot::compareAndPark(&m_byte, isHeldBit | hasParkedBit);
+ if (parkResult.wasUnparked) {
+ switch (static_cast<Token>(parkResult.token)) {
+ case DirectHandoff:
+ // The lock was never released. It was handed to us directly by the thread that did
+ // unlock(). This means we're done!
+ RELEASE_ASSERT(isHeld());
+ return;
+ case BargingOpportunity:
+ // This is the common case. The thread that called unlock() has released the lock,
+ // and we have been woken up so that we may get an opportunity to grab the lock. But
+ // other threads may barge, so the best that we can do is loop around and try again.
+ break;
+ }
+ }
</ins><span class="cx">
</span><span class="cx"> // We have awoken, or we never parked because the byte value changed. Either way, we loop
</span><span class="cx"> // around and try again.
</span><span class="lines">@@ -74,8 +89,18 @@
</span><span class="cx"> }
</span><span class="cx"> }
</span><span class="cx">
</span><del>-NEVER_INLINE void LockBase::unlockSlow()
</del><ins>+void LockBase::unlockSlow()
</ins><span class="cx"> {
</span><ins>+ unlockSlowImpl(Unfair);
+}
+
+void LockBase::unlockFairlySlow()
+{
+ unlockSlowImpl(Fair);
+}
+
+NEVER_INLINE void LockBase::unlockSlowImpl(Fairness fairness)
+{
</ins><span class="cx"> // We could get here because the weak CAS in unlock() failed spuriously, or because there is
</span><span class="cx"> // someone parked. So, we need a CAS loop: even if right now the lock is just held, it could
</span><span class="cx"> // be held and parked if someone attempts to lock just as we are unlocking.
</span><span class="lines">@@ -89,20 +114,29 @@
</span><span class="cx"> continue;
</span><span class="cx"> }
</span><span class="cx">
</span><del>- // Someone is parked. Unpark exactly one thread, possibly leaving the parked bit set if
- // there is a chance that there are still other threads parked.
</del><ins>+ // Someone is parked. Unpark exactly one thread. We may hand the lock to that thread
+ // directly, or we will unlock the lock at the same time as we unpark to allow for barging.
+ // When we unlock, we may leave the parked bit set if there is a chance that there are still
+ // other threads parked.
</ins><span class="cx"> ASSERT(oldByteValue == (isHeldBit | hasParkedBit));
</span><span class="cx"> ParkingLot::unparkOne(
</span><span class="cx"> &m_byte,
</span><del>- [this] (ParkingLot::UnparkResult result) {
</del><ins>+ [&] (ParkingLot::UnparkResult result) -> intptr_t {
</ins><span class="cx"> // We are the only ones that can clear either the isHeldBit or the hasParkedBit,
</span><span class="cx"> // so we should still see both bits set right now.
</span><span class="cx"> ASSERT(m_byte.load() == (isHeldBit | hasParkedBit));
</span><ins>+
+ if (result.didUnparkThread && (fairness == Fair || result.timeToBeFair)) {
+ // We don't unlock anything. Instead, we hand the lock to the thread that was
+ // waiting.
+ return DirectHandoff;
+ }
</ins><span class="cx">
</span><span class="cx"> if (result.mayHaveMoreThreads)
</span><span class="cx"> m_byte.store(hasParkedBit);
</span><span class="cx"> else
</span><span class="cx"> m_byte.store(0);
</span><ins>+ return BargingOpportunity;
</ins><span class="cx"> });
</span><span class="cx"> return;
</span><span class="cx"> }
</span></span></pre></div>
<a id="trunkSourceWTFwtfLockh"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/Lock.h (203349 => 203350)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/Lock.h 2016-07-18 17:43:26 UTC (rev 203349)
+++ trunk/Source/WTF/wtf/Lock.h 2016-07-18 18:32:52 UTC (rev 203350)
</span><span class="lines">@@ -1,5 +1,5 @@
</span><span class="cx"> /*
</span><del>- * Copyright (C) 2015 Apple Inc. All rights reserved.
</del><ins>+ * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
</ins><span class="cx"> *
</span><span class="cx"> * Redistribution and use in source and binary forms, with or without
</span><span class="cx"> * modification, are permitted provided that the following conditions
</span><span class="lines">@@ -40,8 +40,13 @@
</span><span class="cx"> // This is a fully adaptive mutex that only requires 1 byte of storage. It has fast paths that are
</span><span class="cx"> // competetive to a spinlock (uncontended locking is inlined and is just a CAS, microcontention is
</span><span class="cx"> // handled by spinning and yielding), and a slow path that is competetive to std::mutex (if a lock
</span><del>-// 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 a std::mutex.
</del><ins>+// 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 a std::mutex. This lock guarantees eventual stochastic
+// fairness, even in programs that relock the lock immediately after unlocking it. Except when there
+// are collisions between this lock and other locks in the ParkingLot, this lock will guarantee that
+// at worst one call to unlock() per millisecond will do a direct hand-off to the thread that is at
+// the head of the queue. When there are collisions, each collision increases the fair unlock delay
+// by one millisecond in the worst case.
</ins><span class="cx">
</span><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="lines">@@ -73,6 +78,14 @@
</span><span class="cx"> return tryLock();
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ // Relinquish the lock. Either one of the threads that were waiting for the lock, or some other
+ // thread that happens to be running, will be able to grab the lock. This bit of unfairness is
+ // called barging, and we allow it because it maximizes throughput. However, we bound how unfair
+ // barging can get by ensuring that every once in a while, when there is a thread waiting on the
+ // lock, we hand the lock to that thread directly. Every time unlock() finds a thread waiting,
+ // we check if the last time that we did a fair unlock was more than roughly 1ms ago; if so, we
+ // unlock fairly. Fairness matters most for long critical sections, and this virtually
+ // guarantees that long critical sections always get a fair lock.
</ins><span class="cx"> void unlock()
</span><span class="cx"> {
</span><span class="cx"> if (LIKELY(m_byte.compareExchangeWeak(isHeldBit, 0, std::memory_order_release))) {
</span><span class="lines">@@ -83,6 +96,21 @@
</span><span class="cx"> unlockSlow();
</span><span class="cx"> }
</span><span class="cx">
</span><ins>+ // This is like unlock() but it guarantees that we unlock the lock fairly. For short critical
+ // sections, this is much slower than unlock(). For long critical sections, unlock() will learn
+ // to be fair anyway. However, if you plan to relock the lock right after unlocking and you want
+ // to ensure that some other thread runs in the meantime, this is probably the function you
+ // want.
+ void unlockFairly()
+ {
+ if (LIKELY(m_byte.compareExchangeWeak(isHeldBit, 0, std::memory_order_release))) {
+ // Lock released and nobody was waiting!
+ return;
+ }
+
+ unlockFairlySlow();
+ }
+
</ins><span class="cx"> bool isHeld() const
</span><span class="cx"> {
</span><span class="cx"> return m_byte.load(std::memory_order_acquire) & isHeldBit;
</span><span class="lines">@@ -101,6 +129,18 @@
</span><span class="cx">
</span><span class="cx"> WTF_EXPORT_PRIVATE void lockSlow();
</span><span class="cx"> WTF_EXPORT_PRIVATE void unlockSlow();
</span><ins>+ WTF_EXPORT_PRIVATE void unlockFairlySlow();
+
+ enum Fairness {
+ Fair,
+ Unfair
+ };
+ void unlockSlowImpl(Fairness);
+
+ enum Token {
+ BargingOpportunity,
+ DirectHandoff
+ };
</ins><span class="cx">
</span><span class="cx"> // Method used for testing only.
</span><span class="cx"> bool isFullyReset() const
</span></span></pre></div>
<a id="trunkSourceWTFwtfParkingLotcpp"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/ParkingLot.cpp (203349 => 203350)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/ParkingLot.cpp 2016-07-18 17:43:26 UTC (rev 203349)
+++ trunk/Source/WTF/wtf/ParkingLot.cpp 2016-07-18 18:32:52 UTC (rev 203350)
</span><span class="lines">@@ -26,6 +26,7 @@
</span><span class="cx"> #include "config.h"
</span><span class="cx"> #include "ParkingLot.h"
</span><span class="cx">
</span><ins>+#include "CurrentTime.h"
</ins><span class="cx"> #include "DataLog.h"
</span><span class="cx"> #include "HashFunctions.h"
</span><span class="cx"> #include "StringPrintStream.h"
</span><span class="lines">@@ -32,6 +33,7 @@
</span><span class="cx"> #include "ThreadSpecific.h"
</span><span class="cx"> #include "ThreadingPrimitives.h"
</span><span class="cx"> #include "Vector.h"
</span><ins>+#include "WeakRandom.h"
</ins><span class="cx"> #include "WordLock.h"
</span><span class="cx"> #include <condition_variable>
</span><span class="cx"> #include <mutex>
</span><span class="lines">@@ -58,6 +60,8 @@
</span><span class="cx"> const void* address { nullptr };
</span><span class="cx">
</span><span class="cx"> ThreadData* nextInQueue { nullptr };
</span><ins>+
+ intptr_t token { 0 };
</ins><span class="cx"> };
</span><span class="cx">
</span><span class="cx"> enum class DequeueResult {
</span><span class="lines">@@ -69,6 +73,11 @@
</span><span class="cx"> struct Bucket {
</span><span class="cx"> WTF_MAKE_FAST_ALLOCATED;
</span><span class="cx"> public:
</span><ins>+ Bucket()
+ : random(static_cast<unsigned>(bitwise_cast<intptr_t>(this))) // Cannot use default seed since that recurses into Lock.
+ {
+ }
+
</ins><span class="cx"> void enqueue(ThreadData* data)
</span><span class="cx"> {
</span><span class="cx"> if (verbose)
</span><span class="lines">@@ -123,6 +132,14 @@
</span><span class="cx"> bool shouldContinue = true;
</span><span class="cx"> ThreadData** currentPtr = &queueHead;
</span><span class="cx"> ThreadData* previous = nullptr;
</span><ins>+
+ double time = monotonicallyIncreasingTimeMS();
+ bool timeToBeFair = false;
+ if (time > nextFairTime)
+ timeToBeFair = true;
+
+ bool didDequeue = false;
+
</ins><span class="cx"> while (shouldContinue) {
</span><span class="cx"> ThreadData* current = *currentPtr;
</span><span class="cx"> if (verbose)
</span><span class="lines">@@ -129,7 +146,7 @@
</span><span class="cx"> dataLog(toString(currentThread(), ": got thread ", RawPointer(current), "\n"));
</span><span class="cx"> if (!current)
</span><span class="cx"> break;
</span><del>- DequeueResult result = functor(current);
</del><ins>+ DequeueResult result = functor(current, timeToBeFair);
</ins><span class="cx"> switch (result) {
</span><span class="cx"> case DequeueResult::Ignore:
</span><span class="cx"> if (verbose)
</span><span class="lines">@@ -143,6 +160,7 @@
</span><span class="cx"> dataLog(toString(currentThread(), ": dequeueing ", RawPointer(current), " from ", RawPointer(this), "\n"));
</span><span class="cx"> if (current == queueTail)
</span><span class="cx"> queueTail = previous;
</span><ins>+ didDequeue = true;
</ins><span class="cx"> *currentPtr = current->nextInQueue;
</span><span class="cx"> current->nextInQueue = nullptr;
</span><span class="cx"> if (result == DequeueResult::RemoveAndStop)
</span><span class="lines">@@ -150,6 +168,9 @@
</span><span class="cx"> break;
</span><span class="cx"> }
</span><span class="cx"> }
</span><ins>+
+ if (timeToBeFair && didDequeue)
+ nextFairTime = time + random.get();
</ins><span class="cx">
</span><span class="cx"> ASSERT(!!queueHead == !!queueTail);
</span><span class="cx"> }
</span><span class="lines">@@ -158,7 +179,7 @@
</span><span class="cx"> {
</span><span class="cx"> ThreadData* result = nullptr;
</span><span class="cx"> genericDequeue(
</span><del>- [&] (ThreadData* element) -> DequeueResult {
</del><ins>+ [&] (ThreadData* element, bool) -> DequeueResult {
</ins><span class="cx"> result = element;
</span><span class="cx"> return DequeueResult::RemoveAndStop;
</span><span class="cx"> });
</span><span class="lines">@@ -171,6 +192,10 @@
</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><span class="cx"> WordLock lock;
</span><ins>+
+ double nextFairTime { 0 };
+
+ WeakRandom random;
</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 class="lines">@@ -530,7 +555,7 @@
</span><span class="cx">
</span><span class="cx"> } // anonymous namespace
</span><span class="cx">
</span><del>-NEVER_INLINE bool ParkingLot::parkConditionallyImpl(
</del><ins>+NEVER_INLINE ParkingLot::ParkResult ParkingLot::parkConditionallyImpl(
</ins><span class="cx"> const void* address,
</span><span class="cx"> const ScopedLambda<bool()>& validation,
</span><span class="cx"> const ScopedLambda<void()>& beforeSleep,
</span><span class="lines">@@ -540,11 +565,12 @@
</span><span class="cx"> dataLog(toString(currentThread(), ": parking.\n"));
</span><span class="cx">
</span><span class="cx"> ThreadData* me = myThreadData();
</span><ins>+ me->token = 0;
</ins><span class="cx">
</span><span class="cx"> // Guard against someone calling parkConditionally() recursively from beforeSleep().
</span><span class="cx"> RELEASE_ASSERT(!me->address);
</span><span class="cx">
</span><del>- bool result = enqueue(
</del><ins>+ bool enqueueResult = enqueue(
</ins><span class="cx"> address,
</span><span class="cx"> [&] () -> ThreadData* {
</span><span class="cx"> if (!validation())
</span><span class="lines">@@ -554,8 +580,8 @@
</span><span class="cx"> return me;
</span><span class="cx"> });
</span><span class="cx">
</span><del>- if (!result)
- return false;
</del><ins>+ if (!enqueueResult)
+ return ParkResult();
</ins><span class="cx">
</span><span class="cx"> beforeSleep();
</span><span class="cx">
</span><span class="lines">@@ -582,34 +608,48 @@
</span><span class="cx">
</span><span class="cx"> if (didGetDequeued) {
</span><span class="cx"> // Great! We actually got dequeued rather than the timeout expiring.
</span><del>- return true;
</del><ins>+ ParkResult result;
+ result.wasUnparked = true;
+ result.token = me->token;
+ return result;
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> // Have to remove ourselves from the queue since we timed out and nobody has dequeued us yet.
</span><span class="cx">
</span><del>- // It's possible that we get unparked right here, just before dequeue() grabs a lock. It's
- // probably worthwhile to detect when this happens, and return true in that case, to ensure
- // that when we return false it really means that no unpark could have been responsible for us
- // waking up, and that if an unpark call did happen, it woke someone else up.
</del><ins>+ bool didDequeue = false;
</ins><span class="cx"> dequeue(
</span><span class="cx"> address, BucketMode::IgnoreEmpty,
</span><del>- [&] (ThreadData* element) {
- if (element == me)
</del><ins>+ [&] (ThreadData* element, bool) {
+ if (element == me) {
+ didDequeue = true;
</ins><span class="cx"> return DequeueResult::RemoveAndStop;
</span><ins>+ }
</ins><span class="cx"> return DequeueResult::Ignore;
</span><span class="cx"> },
</span><span class="cx"> [] (bool) { });
</span><ins>+
+ // If didDequeue is true, then we dequeued ourselves. This means that we were not unparked.
+ // If didDequeue is false, then someone unparked us.
+
+ RELEASE_ASSERT(!me->nextInQueue);
</ins><span class="cx">
</span><del>- ASSERT(!me->nextInQueue);
-
</del><span class="cx"> // Make sure that no matter what, me->address is null after this point.
</span><span class="cx"> {
</span><span class="cx"> std::lock_guard<std::mutex> locker(me->parkingLock);
</span><ins>+ if (!didDequeue) {
+ // If we were unparked then our address would have been reset by the unparker.
+ RELEASE_ASSERT(!me->address);
+ }
</ins><span class="cx"> me->address = nullptr;
</span><span class="cx"> }
</span><span class="cx">
</span><del>- // If we were not found in the search above, then we know that someone unparked us.
- return false;
</del><ins>+ ParkResult result;
+ result.wasUnparked = !didDequeue;
+ if (!didDequeue) {
+ // If we were unparked then there should be a token.
+ result.token = me->token;
+ }
+ return result;
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> NEVER_INLINE ParkingLot::UnparkResult ParkingLot::unparkOne(const void* address)
</span><span class="lines">@@ -623,7 +663,7 @@
</span><span class="cx"> result.mayHaveMoreThreads = dequeue(
</span><span class="cx"> address,
</span><span class="cx"> BucketMode::EnsureNonEmpty,
</span><del>- [&] (ThreadData* element) {
</del><ins>+ [&] (ThreadData* element, bool) {
</ins><span class="cx"> if (element->address != address)
</span><span class="cx"> return DequeueResult::Ignore;
</span><span class="cx"> threadData = element;
</span><span class="lines">@@ -643,6 +683,7 @@
</span><span class="cx"> {
</span><span class="cx"> std::unique_lock<std::mutex> locker(threadData->parkingLock);
</span><span class="cx"> threadData->address = nullptr;
</span><ins>+ threadData->token = 0;
</ins><span class="cx"> }
</span><span class="cx"> threadData->parkingCondition.notify_one();
</span><span class="cx">
</span><span class="lines">@@ -651,19 +692,21 @@
</span><span class="cx">
</span><span class="cx"> NEVER_INLINE void ParkingLot::unparkOneImpl(
</span><span class="cx"> const void* address,
</span><del>- const ScopedLambda<void(ParkingLot::UnparkResult)>& callback)
</del><ins>+ const ScopedLambda<intptr_t(ParkingLot::UnparkResult)>& callback)
</ins><span class="cx"> {
</span><span class="cx"> if (verbose)
</span><span class="cx"> dataLog(toString(currentThread(), ": unparking one the hard way.\n"));
</span><del>-
</del><ins>+
</ins><span class="cx"> ThreadData* threadData = nullptr;
</span><ins>+ bool timeToBeFair = false;
</ins><span class="cx"> dequeue(
</span><span class="cx"> address,
</span><span class="cx"> BucketMode::EnsureNonEmpty,
</span><del>- [&] (ThreadData* element) {
</del><ins>+ [&] (ThreadData* element, bool passedTimeToBeFair) {
</ins><span class="cx"> if (element->address != address)
</span><span class="cx"> return DequeueResult::Ignore;
</span><span class="cx"> threadData = element;
</span><ins>+ timeToBeFair = passedTimeToBeFair;
</ins><span class="cx"> return DequeueResult::RemoveAndStop;
</span><span class="cx"> },
</span><span class="cx"> [&] (bool mayHaveMoreThreads) {
</span><span class="lines">@@ -670,7 +713,12 @@
</span><span class="cx"> UnparkResult result;
</span><span class="cx"> result.didUnparkThread = !!threadData;
</span><span class="cx"> result.mayHaveMoreThreads = result.didUnparkThread && mayHaveMoreThreads;
</span><del>- callback(result);
</del><ins>+ if (timeToBeFair)
+ RELEASE_ASSERT(threadData);
+ result.timeToBeFair = timeToBeFair;
+ intptr_t token = callback(result);
+ if (threadData)
+ threadData->token = token;
</ins><span class="cx"> });
</span><span class="cx">
</span><span class="cx"> if (!threadData)
</span><span class="lines">@@ -694,7 +742,7 @@
</span><span class="cx"> dequeue(
</span><span class="cx"> address,
</span><span class="cx"> BucketMode::IgnoreEmpty,
</span><del>- [&] (ThreadData* element) {
</del><ins>+ [&] (ThreadData* element, bool) {
</ins><span class="cx"> if (verbose)
</span><span class="cx"> dataLog(toString(currentThread(), ": Observing element with address = ", RawPointer(element->address), "\n"));
</span><span class="cx"> if (element->address != address)
</span></span></pre></div>
<a id="trunkSourceWTFwtfParkingLoth"></a>
<div class="modfile"><h4>Modified: trunk/Source/WTF/wtf/ParkingLot.h (203349 => 203350)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Source/WTF/wtf/ParkingLot.h 2016-07-18 17:43:26 UTC (rev 203349)
+++ trunk/Source/WTF/wtf/ParkingLot.h 2016-07-18 18:32:52 UTC (rev 203350)
</span><span class="lines">@@ -43,17 +43,28 @@
</span><span class="cx">
</span><span class="cx"> // Parks the thread in a queue associated with the given address, which cannot be null. The
</span><span class="cx"> // parking only succeeds if the validation function returns true while the queue lock is held.
</span><ins>+ //
</ins><span class="cx"> // If validation returns false, it will unlock the internal parking queue and then it will
</span><del>- // return without doing anything else. If validation returns true, it will enqueue the thread,
- // unlock the parking queue lock, call the beforeSleep function, and then it will sleep so long
- // as the thread continues to be on the queue and the timeout hasn't fired. Finally, this
- // returns true if we actually got unparked or false if the timeout was hit. Note that
- // beforeSleep is called with no locks held, so it's OK to do pretty much anything so long as
- // you don't recursively call parkConditionally(). You can call unparkOne()/unparkAll() though.
- // It's useful to use beforeSleep() to unlock some mutex in the implementation of
</del><ins>+ // return a null ParkResult (wasUnparked = false, token = 0) without doing anything else.
+ //
+ // If validation returns true, it will enqueue the thread, unlock the parking queue lock, call
+ // the beforeSleep function, and then it will sleep so long as the thread continues to be on the
+ // queue and the timeout hasn't fired. Finally, this returns wasUnparked = true if we actually
+ // got unparked or wasUnparked = false if the timeout was hit. When wasUnparked = true, the
+ // token will contain whatever token was returned from the callback to unparkOne(), or 0 if the
+ // thread was unparked using unparkAll() or the form of unparkOne() that doesn't take a
+ // callback.
+ //
+ // Note that beforeSleep is called with no locks held, so it's OK to do pretty much anything so
+ // long as you don't recursively call parkConditionally(). You can call unparkOne()/unparkAll()
+ // though. It's useful to use beforeSleep() to unlock some mutex in the implementation of
</ins><span class="cx"> // Condition::wait().
</span><ins>+ struct ParkResult {
+ bool wasUnparked { false };
+ intptr_t token { 0 };
+ };
</ins><span class="cx"> template<typename ValidationFunctor, typename BeforeSleepFunctor>
</span><del>- static bool parkConditionally(
</del><ins>+ static ParkResult parkConditionally(
</ins><span class="cx"> const void* address,
</span><span class="cx"> ValidationFunctor&& validation,
</span><span class="cx"> BeforeSleepFunctor&& beforeSleep,
</span><span class="lines">@@ -69,7 +80,7 @@
</span><span class="cx"> // Simple version of parkConditionally() that covers the most common case: you want to park
</span><span class="cx"> // indefinitely so long as the value at the given address hasn't changed.
</span><span class="cx"> template<typename T, typename U>
</span><del>- static bool compareAndPark(const Atomic<T>* address, U expected)
</del><ins>+ static ParkResult compareAndPark(const Atomic<T>* address, U expected)
</ins><span class="cx"> {
</span><span class="cx"> return parkConditionally(
</span><span class="cx"> address,
</span><span class="lines">@@ -81,30 +92,41 @@
</span><span class="cx"> Clock::time_point::max());
</span><span class="cx"> }
</span><span class="cx">
</span><del>- // 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.
</del><ins>+ // Unparking status given to you anytime you unparkOne().
</ins><span class="cx"> struct UnparkResult {
</span><ins>+ // True if some thread was unparked.
</ins><span class="cx"> bool didUnparkThread { false };
</span><ins>+ // True if there may be more threads on this address. This may be conservatively true.
</ins><span class="cx"> bool mayHaveMoreThreads { false };
</span><ins>+ // This bit is randomly set to true indicating that it may be profitable to unlock the lock
+ // using a fair unlocking protocol. This is most useful when used in conjunction with
+ // unparkOne(address, callback).
+ bool timeToBeFair { false };
</ins><span class="cx"> };
</span><ins>+
+ // 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.
</ins><span class="cx"> WTF_EXPORT_PRIVATE static UnparkResult unparkOne(const void* address);
</span><span class="cx">
</span><ins>+ // This is an expert-mode version of unparkOne() that allows for really good thundering herd
+ // avoidance and eventual stochastic fairness in adaptive mutexes.
+ //
</ins><span class="cx"> // Unparks one thread from the queue associated with the given address, and calls the given
</span><del>- // functor while the address is locked. Reports to the callback whether any thread got unparked
- // and whether there may be any other threads still on the queue. This is an expert-mode version
- // of unparkOne() that allows for really good thundering herd avoidance in adaptive mutexes.
- // Without this, a lock implementation that uses unparkOne() has to have some trick for knowing
- // if there are still threads parked on the queue, so that it can set some bit in its lock word
- // to indicate that the next unlock() also needs to unparkOne(). But there is a race between
- // manipulating that bit and some other thread acquiring the lock. It's possible to work around
- // that race - see Rusty Russel's well-known usersem library - but it's not pretty. This form
- // allows that race to be completely avoided, since there is no way that a thread can be parked
- // while the callback is running.
</del><ins>+ // callback while the address is locked. Reports to the callback whether any thread got
+ // unparked, whether there may be any other threads still on the queue, and whether this may be
+ // a good time to do fair unlocking. The callback returns an intptr_t token, which is returned
+ // to the unparked thread via ParkResult::token.
+ //
+ // WTF::Lock and WTF::Condition both use this form of unparkOne() because it allows them to use
+ // the ParkingLot's internal queue lock to serialize some decision-making. For example, if
+ // UnparkResult::mayHaveMoreThreads is false inside the callback, then we know that at that
+ // moment nobody can add any threads to the queue because the queue lock is still held. Also,
+ // WTF::Lock uses the timeToBeFair and token mechanism to implement eventual fairness.
</ins><span class="cx"> template<typename Callback>
</span><span class="cx"> static void unparkOne(const void* address, Callback&& callback)
</span><span class="cx"> {
</span><del>- unparkOneImpl(address, scopedLambda<void(UnparkResult)>(std::forward<Callback>(callback)));
</del><ins>+ unparkOneImpl(address, scopedLambda<intptr_t(UnparkResult)>(std::forward<Callback>(callback)));
</ins><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> // Unparks every thread from the queue associated with the given address, which cannot be null.
</span><span class="lines">@@ -126,7 +148,7 @@
</span><span class="cx"> WTF_EXPORT_PRIVATE static void forEach(std::function<void(ThreadIdentifier, const void*)>);
</span><span class="cx">
</span><span class="cx"> private:
</span><del>- WTF_EXPORT_PRIVATE static bool parkConditionallyImpl(
</del><ins>+ WTF_EXPORT_PRIVATE static ParkResult parkConditionallyImpl(
</ins><span class="cx"> const void* address,
</span><span class="cx"> const ScopedLambda<bool()>& validation,
</span><span class="cx"> const ScopedLambda<void()>& beforeSleep,
</span><span class="lines">@@ -133,7 +155,7 @@
</span><span class="cx"> Clock::time_point timeout);
</span><span class="cx">
</span><span class="cx"> WTF_EXPORT_PRIVATE static void unparkOneImpl(
</span><del>- const void* address, const ScopedLambda<void(UnparkResult)>& callback);
</del><ins>+ const void* address, const ScopedLambda<intptr_t(UnparkResult)>& callback);
</ins><span class="cx">
</span><span class="cx"> WTF_EXPORT_PRIVATE static void forEachImpl(const std::function<void(ThreadIdentifier, const void*)>&);
</span><span class="cx"> };
</span></span></pre></div>
<a id="trunkToolsChangeLog"></a>
<div class="modfile"><h4>Modified: trunk/Tools/ChangeLog (203349 => 203350)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/ChangeLog 2016-07-18 17:43:26 UTC (rev 203349)
+++ trunk/Tools/ChangeLog 2016-07-18 18:32:52 UTC (rev 203350)
</span><span class="lines">@@ -1,3 +1,12 @@
</span><ins>+2016-07-02 Filip Pizlo <fpizlo@apple.com>
+
+ WTF::Lock should be fair eventually
+ https://bugs.webkit.org/show_bug.cgi?id=159384
+
+ Reviewed by Geoffrey Garen.
+
+ * TestWebKitAPI/Tests/WTF/ParkingLot.cpp:
+
</ins><span class="cx"> 2016-07-17 Sam Weinig <sam@webkit.org>
</span><span class="cx">
</span><span class="cx"> [WebKit API] Add SPI to track multiple navigations caused by a single user gesture
</span></span></pre></div>
<a id="trunkToolsTestWebKitAPITestsWTFParkingLotcpp"></a>
<div class="modfile"><h4>Modified: trunk/Tools/TestWebKitAPI/Tests/WTF/ParkingLot.cpp (203349 => 203350)</h4>
<pre class="diff"><span>
<span class="info">--- trunk/Tools/TestWebKitAPI/Tests/WTF/ParkingLot.cpp 2016-07-18 17:43:26 UTC (rev 203349)
+++ trunk/Tools/TestWebKitAPI/Tests/WTF/ParkingLot.cpp 2016-07-18 18:32:52 UTC (rev 203350)
</span><span class="lines">@@ -148,7 +148,7 @@
</span><span class="cx"> }
</span><span class="cx">
</span><span class="cx"> // We need to wait.
</span><del>- if (ParkingLot::compareAndPark(&semaphore, newSemaphoreValue)) {
</del><ins>+ if (ParkingLot::compareAndPark(&semaphore, newSemaphoreValue).wasUnparked) {
</ins><span class="cx"> // We did wait, and then got woken up. This means that someone who up'd the semaphore
</span><span class="cx"> // passed ownership onto us.
</span><span class="cx"> return;
</span></span></pre>
</div>
</div>
</body>
</html>