WTF should have a compact Condition object to use with Lock
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 13 Aug 2015 20:42:11 +0000 (20:42 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 13 Aug 2015 20:42:11 +0000 (20:42 +0000)
https://bugs.webkit.org/show_bug.cgi?id=147986

Reviewed by Geoffrey Garen.

Source/WTF:

Adds a condition variable implementation based on ParkingLot, called simply WTF::Condition.
It can be used with WTF::Lock or actually any lock implementation. It should even work with
WTF::SpinLock, WTF::Mutex, or std::mutex. Best of all, Condition only requires one byte.

ParkingLot almost contained all of the functionality needed to implemenet wait/notify. We
could have implemented Condition using a 32-bit (or even 64-bit) version that protects
against a notify that happens just before we park. But, this changes the ParkingLot API to
give us the ability to run some code between when ParkingLot enqueues the current thread
and when it actually sleeps. This callback is called with no locks held, so it can call
unlock() on any kind of lock, so long as that lock's unlock() method doesn't recurse into
ParkingLot::parkConditionally(). That seems unlikely; unlock() is more likely to call
ParkingLot::unparkOne() or unparkAll(). WTF::Lock will never call parkConditionally()
inside unlock(), so WTF::Lock is definitely appropriate for use with Condition.

Condition supports most of the API that std::condition_variable supports. It does some
things to try to reduce footgun potential. The preferred timeout form is waitUntil() which
takes an absolute time from the steady_clock. The only relative timeout form also takes a
predicate callback, so it's impossible to write the subtly incorrect
"while (...) wait_for(...)" idiom.

This patch doesn't actually introduce any uses of WTF::Condition other than the unit tests.
I'll start switching code over to using WTF::Condition in another patch.

* WTF.vcxproj/WTF.vcxproj:
* WTF.xcodeproj/project.pbxproj:
* wtf/CMakeLists.txt:
* wtf/Condition.h: Added.
(WTF::Condition::Condition):
(WTF::Condition::waitUntil):
(WTF::Condition::waitFor):
(WTF::Condition::wait):
(WTF::Condition::notifyOne):
(WTF::Condition::notifyAll):
* wtf/Lock.cpp:
(WTF::LockBase::unlockSlow): Make this useful assertion be a release assertion. It catches cases where you unlock the lock even though you don't hold it.
* wtf/ParkingLot.cpp:
(WTF::ParkingLot::parkConditionally): Add the beforeSleep() callback.
(WTF::ParkingLot::unparkOne):
* wtf/ParkingLot.h:
(WTF::ParkingLot::compareAndPark):

Tools:

Add a test for WTF::Condition.

* TestWebKitAPI/CMakeLists.txt:
* TestWebKitAPI/TestWebKitAPI.vcxproj/TestWebKitAPI.vcxproj:
* TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:
* TestWebKitAPI/Tests/WTF/Condition.cpp: Added.
(TestWebKitAPI::TEST):
* TestWebKitAPI/Tests/WTF/Lock.cpp:
(TestWebKitAPI::runLockTest): Change the name of the thread.

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

14 files changed:
Source/WTF/ChangeLog
Source/WTF/WTF.vcxproj/WTF.vcxproj
Source/WTF/WTF.xcodeproj/project.pbxproj
Source/WTF/wtf/CMakeLists.txt
Source/WTF/wtf/Condition.h [new file with mode: 0644]
Source/WTF/wtf/Lock.cpp
Source/WTF/wtf/ParkingLot.cpp
Source/WTF/wtf/ParkingLot.h
Tools/ChangeLog
Tools/TestWebKitAPI/CMakeLists.txt
Tools/TestWebKitAPI/TestWebKitAPI.vcxproj/TestWebKitAPI.vcxproj
Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj
Tools/TestWebKitAPI/Tests/WTF/Condition.cpp [new file with mode: 0644]
Tools/TestWebKitAPI/Tests/WTF/Lock.cpp

index 5e3d8c3..6a980b4 100644 (file)
@@ -1,3 +1,51 @@
+2015-08-13  Filip Pizlo  <fpizlo@apple.com>
+
+        WTF should have a compact Condition object to use with Lock
+        https://bugs.webkit.org/show_bug.cgi?id=147986
+
+        Reviewed by Geoffrey Garen.
+
+        Adds a condition variable implementation based on ParkingLot, called simply WTF::Condition.
+        It can be used with WTF::Lock or actually any lock implementation. It should even work with
+        WTF::SpinLock, WTF::Mutex, or std::mutex. Best of all, Condition only requires one byte.
+
+        ParkingLot almost contained all of the functionality needed to implemenet wait/notify. We
+        could have implemented Condition using a 32-bit (or even 64-bit) version that protects
+        against a notify that happens just before we park. But, this changes the ParkingLot API to
+        give us the ability to run some code between when ParkingLot enqueues the current thread
+        and when it actually sleeps. This callback is called with no locks held, so it can call
+        unlock() on any kind of lock, so long as that lock's unlock() method doesn't recurse into
+        ParkingLot::parkConditionally(). That seems unlikely; unlock() is more likely to call
+        ParkingLot::unparkOne() or unparkAll(). WTF::Lock will never call parkConditionally()
+        inside unlock(), so WTF::Lock is definitely appropriate for use with Condition.
+
+        Condition supports most of the API that std::condition_variable supports. It does some
+        things to try to reduce footgun potential. The preferred timeout form is waitUntil() which
+        takes an absolute time from the steady_clock. The only relative timeout form also takes a
+        predicate callback, so it's impossible to write the subtly incorrect
+        "while (...) wait_for(...)" idiom.
+
+        This patch doesn't actually introduce any uses of WTF::Condition other than the unit tests.
+        I'll start switching code over to using WTF::Condition in another patch.
+
+        * WTF.vcxproj/WTF.vcxproj:
+        * WTF.xcodeproj/project.pbxproj:
+        * wtf/CMakeLists.txt:
+        * wtf/Condition.h: Added.
+        (WTF::Condition::Condition):
+        (WTF::Condition::waitUntil):
+        (WTF::Condition::waitFor):
+        (WTF::Condition::wait):
+        (WTF::Condition::notifyOne):
+        (WTF::Condition::notifyAll):
+        * wtf/Lock.cpp:
+        (WTF::LockBase::unlockSlow): Make this useful assertion be a release assertion. It catches cases where you unlock the lock even though you don't hold it.
+        * wtf/ParkingLot.cpp:
+        (WTF::ParkingLot::parkConditionally): Add the beforeSleep() callback.
+        (WTF::ParkingLot::unparkOne):
+        * wtf/ParkingLot.h:
+        (WTF::ParkingLot::compareAndPark):
+
 2015-08-12  Anders Carlsson  <andersca@apple.com>
 
         Use WTF::Optional in WindowFeatures
index 4c2d7b7..0c65902 100644 (file)
     <ClInclude Include="..\wtf\CheckedArithmetic.h" />
     <ClInclude Include="..\wtf\CheckedBoolean.h" />
     <ClInclude Include="..\wtf\Compiler.h" />
+    <ClInclude Include="..\wtf\Condition.h" />
     <ClInclude Include="..\wtf\CryptographicUtilities.h" />
     <ClInclude Include="..\wtf\CryptographicallyRandomNumber.h" />
     <ClInclude Include="..\wtf\CurrentTime.h" />
index 19c0581..3065f16 100644 (file)
@@ -40,6 +40,7 @@
                0FC4488316FE9FE100844BE9 /* ProcessID.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC4488216FE9FE100844BE9 /* ProcessID.h */; };
                0FC4EDE61696149600F65041 /* CommaPrinter.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC4EDE51696149600F65041 /* CommaPrinter.h */; };
                0FD81AC5154FB22E00983E72 /* FastBitVector.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FD81AC4154FB22E00983E72 /* FastBitVector.h */; settings = {ATTRIBUTES = (); }; };
+               0FDB698E1B7C643A000C1078 /* Condition.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FDB698D1B7C643A000C1078 /* Condition.h */; };
                0FDDBFA71666DFA300C55FEF /* StringPrintStream.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FDDBFA51666DFA300C55FEF /* StringPrintStream.cpp */; };
                0FDDBFA81666DFA300C55FEF /* StringPrintStream.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FDDBFA61666DFA300C55FEF /* StringPrintStream.h */; };
                0FE1646A1B6FFC9600400E7C /* Lock.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FE164681B6FFC9600400E7C /* Lock.cpp */; };
                0FC4488216FE9FE100844BE9 /* ProcessID.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = ProcessID.h; sourceTree = "<group>"; };
                0FC4EDE51696149600F65041 /* CommaPrinter.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CommaPrinter.h; sourceTree = "<group>"; };
                0FD81AC4154FB22E00983E72 /* FastBitVector.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FastBitVector.h; sourceTree = "<group>"; };
+               0FDB698D1B7C643A000C1078 /* Condition.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Condition.h; sourceTree = "<group>"; };
                0FDDBFA51666DFA300C55FEF /* StringPrintStream.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = StringPrintStream.cpp; sourceTree = "<group>"; };
                0FDDBFA61666DFA300C55FEF /* StringPrintStream.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = StringPrintStream.h; sourceTree = "<group>"; };
                0FE164681B6FFC9600400E7C /* Lock.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Lock.cpp; sourceTree = "<group>"; };
                                0F8F2B8F172E00F0007DBDA5 /* CompilationThread.cpp */,
                                0F8F2B90172E00F0007DBDA5 /* CompilationThread.h */,
                                A8A47270151A825A004123FF /* Compiler.h */,
+                               0FDB698D1B7C643A000C1078 /* Condition.h */,
                                E15556F318A0CC18006F48FB /* CryptographicUtilities.cpp */,
                                E15556F418A0CC18006F48FB /* CryptographicUtilities.h */,
                                A8A47273151A825A004123FF /* CryptographicallyRandomNumber.cpp */,
                                A8A47423151A825B004123FF /* SimpleStats.h in Headers */,
                                A8A47424151A825B004123FF /* SinglyLinkedList.h in Headers */,
                                A748745317A0BDAE00FA04CB /* SixCharacterHash.h in Headers */,
+                               0FDB698E1B7C643A000C1078 /* Condition.h in Headers */,
                                A8A47426151A825B004123FF /* Spectrum.h in Headers */,
                                A8A47428151A825B004123FF /* StackBounds.h in Headers */,
                                FEDACD3E1630F83F00C69634 /* StackStats.h in Headers */,
index 87cdd5e..972920e 100644 (file)
@@ -10,6 +10,7 @@ set(WTF_HEADERS
     ByteOrder.h
     CompilationThread.h
     Compiler.h
+    Condition.h
     CryptographicUtilities.h
     CryptographicallyRandomNumber.h
     CurrentTime.h
diff --git a/Source/WTF/wtf/Condition.h b/Source/WTF/wtf/Condition.h
new file mode 100644 (file)
index 0000000..b155ef9
--- /dev/null
@@ -0,0 +1,113 @@
+/*
+ * 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_Condition_h
+#define WTF_Condition_h
+
+#include <chrono>
+#include <functional>
+#include <mutex>
+#include <wtf/ParkingLot.h>
+
+namespace WTF {
+
+class Condition {
+public:
+    Condition() { }
+
+    // Wait on a parking queue while releasing the given lock. It will unlock the lock just before
+    // parking, and relock it upon wakeup. Returns true if we woke up due to some call to
+    // notifyOne() or notifyAll(). Returns false if we woke up due to a timeout.
+    template<typename LockType>
+    bool waitUntil(
+        LockType& lock, std::chrono::steady_clock::time_point timeout)
+    {
+        bool result = ParkingLot::parkConditionally(
+            &m_dummy,
+            [] () -> bool { return true; },
+            [&lock] () { lock.unlock(); },
+            timeout);
+        lock.lock();
+        return result;
+    }
+
+    // Wait until the given predicate is satisfied. Returns true if it is satisfied in the end.
+    // May return early due to timeout.
+    template<typename LockType, typename Functor>
+    bool waitUntil(
+        LockType& lock, std::chrono::steady_clock::time_point timeout, const Functor& predicate)
+    {
+        while (!predicate()) {
+            if (!waitUntil(lock, timeout))
+                return predicate();
+        }
+        return true;
+    }
+
+    // Wait until the given predicate is satisfied. Returns true if it is satisfied in the end.
+    // May return early due to timeout.
+    template<typename LockType, typename DurationType, typename Functor>
+    bool waitFor(
+        LockType& lock, const DurationType& relativeTimeout, const Functor& predicate)
+    {
+        std::chrono::steady_clock::time_point absoluteTimeout =
+            std::chrono::steady_clock::now() +
+            std::chrono::duration_cast<std::chrono::steady_clock::duration>(relativeTimeout);
+
+        return waitUntil(lock, absoluteTimeout, predicate);
+    }
+
+    template<typename LockType>
+    void wait(LockType& lock)
+    {
+        waitUntil(lock, std::chrono::steady_clock::time_point::max());
+    }
+
+    template<typename LockType, typename Functor>
+    void wait(LockType& lock, const Functor& predicate)
+    {
+        while (!predicate())
+            wait(lock);
+    }
+
+    void notifyOne()
+    {
+        ParkingLot::unparkOne(&m_dummy);
+    }
+    
+    void notifyAll()
+    {
+        ParkingLot::unparkAll(&m_dummy);
+    }
+    
+private:
+    
+    uint8_t m_dummy;
+};
+
+} // namespace WTF
+
+#endif // WTF_Condition_h
+
index da64b2f..c844271 100644 (file)
@@ -81,7 +81,7 @@ void LockBase::unlockSlow()
     // be held and parked if someone attempts to lock just as we are unlocking.
     for (;;) {
         uint8_t oldByteValue = m_byte.load();
-        ASSERT(oldByteValue == isHeldBit || oldByteValue == (isHeldBit | hasParkedBit));
+        RELEASE_ASSERT(oldByteValue == isHeldBit || oldByteValue == (isHeldBit | hasParkedBit));
         
         if (oldByteValue == isHeldBit) {
             if (m_byte.compareExchangeWeak(isHeldBit, 0))
index 5c1b9c1..4c42a7f 100644 (file)
@@ -507,13 +507,20 @@ bool dequeue(
 
 } // anonymous namespace
 
-bool ParkingLot::parkConditionally(const void* address, std::function<bool()> validation)
+bool ParkingLot::parkConditionally(
+    const void* address,
+    std::function<bool()> validation,
+    std::function<void()> beforeSleep,
+    std::chrono::steady_clock::time_point timeout)
 {
     if (verbose)
         dataLog(toString(currentThread(), ": parking.\n"));
     
     ThreadData* me = myThreadData();
 
+    // Guard against someone calling parkConditionally() recursively from beforeSleep().
+    RELEASE_ASSERT(!me->address);
+
     bool result = enqueue(
         address,
         [&] () -> ThreadData* {
@@ -527,16 +534,49 @@ bool ParkingLot::parkConditionally(const void* address, std::function<bool()> va
     if (!result)
         return false;
 
-    if (verbose)
-        dataLog(toString(currentThread(), ": parking self: ", RawPointer(me), "\n"));
+    beforeSleep();
+
+    bool didGetDequeued;
     {
         std::unique_lock<std::mutex> locker(me->parkingLock);
-        while (me->address)
-            me->parkingCondition.wait(locker);
+        while (me->address && std::chrono::steady_clock::now() < timeout)
+            me->parkingCondition.wait_until(locker, timeout);
+        ASSERT(!me->address || me->address == address);
+        didGetDequeued = !me->address;
     }
-    if (verbose)
-        dataLog(toString(currentThread(), ": unparked self: ", RawPointer(me), "\n"));
-    return true;
+    if (didGetDequeued) {
+        // Great! We actually got dequeued rather than the timeout expiring.
+        return true;
+    }
+
+    // Have to remove ourselves from the queue since we timed out and nobody has dequeued us yet.
+
+    // 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.
+    bool didFind = false;
+    dequeue(
+        address, BucketMode::IgnoreEmpty,
+        [&] (ThreadData* element) {
+            if (element == me) {
+                didFind = true;
+                return DequeueResult::RemoveAndStop;
+            }
+            return DequeueResult::Ignore;
+        },
+        [] (bool) { });
+
+    ASSERT(!me->nextInQueue);
+
+    // Make sure that no matter what, me->address is null after this point.
+    {
+        std::lock_guard<std::mutex> locker(me->parkingLock);
+        me->address = nullptr;
+    }
+
+    // If we were not found in the search above, then we know that someone unparked us.
+    return !didFind;
 }
 
 bool ParkingLot::unparkOne(const void* address)
index 8bfa2f9..383653e 100644 (file)
@@ -26,6 +26,7 @@
 #ifndef WTF_ParkingLot_h
 #define WTF_ParkingLot_h
 
+#include <chrono>
 #include <functional>
 #include <wtf/Atomics.h>
 #include <wtf/Threading.h>
@@ -39,10 +40,23 @@ class ParkingLot {
 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);
+    // If validation returns false, it will unlock the internal parking queue and then it will
+    // 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
+    // Condition::wait().
+    WTF_EXPORT_PRIVATE static bool parkConditionally(
+        const void* address,
+        std::function<bool()> validation,
+        std::function<void()> beforeSleep,
+        std::chrono::steady_clock::time_point timeout);
 
+    // Simple version of parkConditionally() that covers the most common case: you want to park
+    // indefinitely so long as the value at the given address hasn't changed.
     template<typename T, typename U>
     static bool compareAndPark(const Atomic<T>* address, U expected)
     {
@@ -51,7 +65,9 @@ public:
             [address, expected] () -> bool {
                 U value = address->load();
                 return value == expected;
-            });
+            },
+            [] () { },
+            std::chrono::steady_clock::time_point::max());
     }
 
     // Unparks one thread from the queue associated with the given address, which cannot be null.
index f8c01c5..4e7fc76 100644 (file)
@@ -1,5 +1,22 @@
 2015-08-13  Filip Pizlo  <fpizlo@apple.com>
 
+        WTF should have a compact Condition object to use with Lock
+        https://bugs.webkit.org/show_bug.cgi?id=147986
+
+        Reviewed by Geoffrey Garen.
+
+        Add a test for WTF::Condition.
+
+        * TestWebKitAPI/CMakeLists.txt:
+        * TestWebKitAPI/TestWebKitAPI.vcxproj/TestWebKitAPI.vcxproj:
+        * TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:
+        * TestWebKitAPI/Tests/WTF/Condition.cpp: Added.
+        (TestWebKitAPI::TEST):
+        * TestWebKitAPI/Tests/WTF/Lock.cpp:
+        (TestWebKitAPI::runLockTest): Change the name of the thread.
+
+2015-08-13  Filip Pizlo  <fpizlo@apple.com>
+
         Unreviewed, shorten another test. It's timing out in debug on some bot.
 
         * TestWebKitAPI/Tests/WTF/Lock.cpp:
index f462dd4..b5e5904 100644 (file)
@@ -42,6 +42,7 @@ set(TestWTF_SOURCES
     ${TESTWEBKITAPI_DIR}/TestsController.cpp
     ${TESTWEBKITAPI_DIR}/Tests/WTF/AtomicString.cpp
     ${TESTWEBKITAPI_DIR}/Tests/WTF/CString.cpp
+    ${TESTWEBKITAPI_DIR}/Tests/WTF/Condition.cpp
     ${TESTWEBKITAPI_DIR}/Tests/WTF/CheckedArithmeticOperations.cpp
     ${TESTWEBKITAPI_DIR}/Tests/WTF/DateMath.cpp
     ${TESTWEBKITAPI_DIR}/Tests/WTF/Deque.cpp
index d4e2da7..a484edc 100644 (file)
@@ -1,4 +1,4 @@
-<?xml version="1.0" encoding="utf-8"?>
+<?xml version="1.0" encoding="utf-8"?>
 <Project DefaultTargets="Build" ToolsVersion="14.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
   <ItemGroup Label="ProjectConfigurations">
     <ProjectConfiguration Include="DebugSuffix|Win32">
     <ClCompile Include="..\Tests\WTF\cf\RetainPtr.cpp" />
     <ClCompile Include="..\Tests\WTF\cf\RetainPtrHashing.cpp" />
     <ClCompile Include="..\Tests\WTF\CheckedArithmeticOperations.cpp" />
+    <ClCompile Include="..\Tests\WTF\Condition.cpp" />
     <ClCompile Include="..\Tests\WTF\CString.cpp" />
     <ClCompile Include="..\Tests\WTF\DateMath.cpp" />
     <ClCompile Include="..\Tests\WTF\Deque.cpp" />
index ad1ce61..ac4cccd 100644 (file)
@@ -12,6 +12,7 @@
                0F139E791A42457000F590F5 /* PlatformUtilitiesCocoa.mm in Sources */ = {isa = PBXBuildFile; fileRef = 0F139E721A423A2B00F590F5 /* PlatformUtilitiesCocoa.mm */; };
                0F3B94A71A77267400DE3272 /* WKWebViewEvaluateJavaScript.mm in Sources */ = {isa = PBXBuildFile; fileRef = 0F3B94A51A77266C00DE3272 /* WKWebViewEvaluateJavaScript.mm */; };
                0FE447991B76F1EB009498EB /* ParkingLot.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FE447971B76F1E3009498EB /* ParkingLot.cpp */; };
+               0FEAE3691B7D19D200CE17F2 /* Condition.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FEAE3671B7D19CB00CE17F2 /* Condition.cpp */; };
                0FFC45A61B73EBEB0085BD62 /* Lock.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FFC45A41B73EBE20085BD62 /* Lock.cpp */; };
                1A02C870125D4CFD00E3F4BD /* find.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = 1A02C84B125D4A5E00E3F4BD /* find.html */; };
                1A50AA201A2A51FC00F4C345 /* close-from-within-create-page.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = 1A50AA1F1A2A4EA500F4C345 /* close-from-within-create-page.html */; };
                0FC6C4CB141027E0005B7F0C /* RedBlackTree.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = RedBlackTree.cpp; sourceTree = "<group>"; };
                0FC6C4CE141034AD005B7F0C /* MetaAllocator.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = MetaAllocator.cpp; sourceTree = "<group>"; };
                0FE447971B76F1E3009498EB /* ParkingLot.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ParkingLot.cpp; sourceTree = "<group>"; };
+               0FEAE3671B7D19CB00CE17F2 /* Condition.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Condition.cpp; sourceTree = "<group>"; };
                0FFC45A41B73EBE20085BD62 /* Lock.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Lock.cpp; sourceTree = "<group>"; };
                14464012167A8305000BD218 /* LayoutUnit.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LayoutUnit.cpp; sourceTree = "<group>"; };
                14F3B11215E45EAB00210069 /* SaturatedArithmeticOperations.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = SaturatedArithmeticOperations.cpp; sourceTree = "<group>"; };
                                BC029B1A1486B23800817DA9 /* ns */,
                                26F1B44215CA434F00D1E4BF /* AtomicString.cpp */,
                                A7A966DA140ECCC8005EF9B4 /* CheckedArithmeticOperations.cpp */,
+                               0FEAE3671B7D19CB00CE17F2 /* Condition.cpp */,
                                26A2C72E15E2E73C005B1A14 /* CString.cpp */,
                                E40019301ACE9B5C001B0A2A /* BloomFilter.cpp */,
                                7AA021BA1AB09EA70052953F /* DateMath.cpp */,
                                7CCE7EBF1A411A7E00447C4C /* ElementAtPointInWebFrame.mm in Sources */,
                                7CCE7EEF1A411AE600447C4C /* EphemeralSessionPushStateNoHistoryCallback.cpp in Sources */,
                                7CCE7EF01A411AE600447C4C /* EvaluateJavaScript.cpp in Sources */,
+                               0FEAE3691B7D19D200CE17F2 /* Condition.cpp in Sources */,
                                7CCE7EF11A411AE600447C4C /* FailedLoad.cpp in Sources */,
                                7CCE7EF31A411AE600447C4C /* Find.cpp in Sources */,
                                7CCE7EF41A411AE600447C4C /* FindMatches.mm in Sources */,
diff --git a/Tools/TestWebKitAPI/Tests/WTF/Condition.cpp b/Tools/TestWebKitAPI/Tests/WTF/Condition.cpp
new file mode 100644 (file)
index 0000000..411bcd4
--- /dev/null
@@ -0,0 +1,257 @@
+/*
+ * 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 <mutex>
+#include <thread>
+#include <wtf/Condition.h>
+#include <wtf/DataLog.h>
+#include <wtf/Deque.h>
+#include <wtf/Lock.h>
+#include <wtf/StringPrintStream.h>
+#include <wtf/Threading.h>
+#include <wtf/Vector.h>
+
+using namespace WTF;
+
+namespace TestWebKitAPI {
+
+namespace {
+
+const bool verbose = false;
+
+enum NotifyStyle {
+    AlwaysNotifyOne,
+    TacticallyNotifyAll
+};
+
+template<typename Functor>
+void wait(Condition& condition, std::unique_lock<Lock>& locker, const Functor& predicate, std::chrono::microseconds timeout)
+{
+    if (timeout == std::chrono::microseconds::max())
+        condition.wait(locker, predicate);
+    else {
+        // This tests timeouts in the sense that it verifies that we can call wait() again after a
+        // timeout happened. That's a non-trivial piece of functionality since upon timeout the
+        // ParkingLot has to remove us from the queue.
+        while (!predicate())
+            condition.waitFor(locker, timeout, predicate);
+    }
+}
+
+void notify(NotifyStyle notifyStyle, Condition& condition, bool shouldNotify)
+{
+    switch (notifyStyle) {
+    case AlwaysNotifyOne:
+        condition.notifyOne();
+        break;
+    case TacticallyNotifyAll:
+        if (shouldNotify)
+            condition.notifyAll();
+        break;
+    }
+}
+
+void runTest(
+    unsigned numProducers,
+    unsigned numConsumers,
+    unsigned maxQueueSize,
+    unsigned numMessagesPerProducer,
+    NotifyStyle notifyStyle,
+    std::chrono::microseconds timeout = std::chrono::microseconds::max(),
+    std::chrono::microseconds delay = std::chrono::microseconds::zero())
+{
+    Deque<unsigned> queue;
+    bool shouldContinue = true;
+    Lock lock;
+    Condition emptyCondition;
+    Condition fullCondition;
+
+    Vector<ThreadIdentifier> consumerThreads;
+    Vector<ThreadIdentifier> producerThreads;
+
+    Vector<unsigned> received;
+    Lock receivedLock;
+    
+    for (unsigned i = numConsumers; i--;) {
+        ThreadIdentifier threadIdentifier = createThread(
+            "Consumer thread",
+            [&] () {
+                for (;;) {
+                    unsigned result;
+                    unsigned shouldNotify = false;
+                    {
+                        std::unique_lock<Lock> locker(lock);
+                        wait(
+                            emptyCondition, locker, 
+                            [&] () {
+                                if (verbose)
+                                    dataLog(toString(currentThread(), ": Checking consumption predicate with shouldContinue = ", shouldContinue, ", queue.size() == ", queue.size(), "\n"));
+                                return !shouldContinue || !queue.isEmpty();
+                            },
+                            timeout);
+                        if (!shouldContinue)
+                            return;
+                        shouldNotify = queue.size() == maxQueueSize;
+                        result = queue.takeFirst();
+                    }
+                    notify(notifyStyle, fullCondition, shouldNotify);
+
+                    {
+                        std::lock_guard<Lock> locker(receivedLock);
+                        received.append(result);
+                    }
+                }
+            });
+        consumerThreads.append(threadIdentifier);
+    }
+
+    std::this_thread::sleep_for(delay);
+
+    for (unsigned i = numProducers; i--;) {
+        ThreadIdentifier threadIdentifier = createThread(
+            "Producer Thread",
+            [&] () {
+                for (unsigned i = 0; i < numMessagesPerProducer; ++i) {
+                    bool shouldNotify = false;
+                    {
+                        std::unique_lock<Lock> locker(lock);
+                        wait(
+                            fullCondition, locker,
+                            [&] () {
+                                if (verbose)
+                                    dataLog(toString(currentThread(), ": Checking production predicate with shouldContinue = ", shouldContinue, ", queue.size() == ", queue.size(), "\n"));
+                                return queue.size() < maxQueueSize;
+                            },
+                            timeout);
+                        shouldNotify = queue.isEmpty();
+                        queue.append(i);
+                    }
+                    notify(notifyStyle, emptyCondition, shouldNotify);
+                }
+            });
+        producerThreads.append(threadIdentifier);
+    }
+
+    for (ThreadIdentifier threadIdentifier : producerThreads)
+        waitForThreadCompletion(threadIdentifier);
+
+    {
+        std::lock_guard<Lock> locker(lock);
+        shouldContinue = false;
+    }
+    emptyCondition.notifyAll();
+
+    for (ThreadIdentifier threadIdentifier : consumerThreads)
+        waitForThreadCompletion(threadIdentifier);
+
+    EXPECT_EQ(numProducers * numMessagesPerProducer, received.size());
+    std::sort(received.begin(), received.end());
+    for (unsigned messageIndex = 0; messageIndex < numMessagesPerProducer; ++messageIndex) {
+        for (unsigned producerIndex = 0; producerIndex < numProducers; ++producerIndex)
+            EXPECT_EQ(messageIndex, received[messageIndex * numProducers + producerIndex]);
+    }
+}
+
+} // anonymous namespace
+
+TEST(WTF_Condition, OneProducerOneConsumerOneSlot)
+{
+    runTest(1, 1, 1, 100000, TacticallyNotifyAll);
+}
+
+TEST(WTF_Condition, OneProducerOneConsumerOneSlotTimeout)
+{
+    runTest(
+        1, 1, 1, 100000, TacticallyNotifyAll,
+        std::chrono::microseconds(10000),
+        std::chrono::microseconds(1000000));
+}
+
+TEST(WTF_Condition, OneProducerOneConsumerHundredSlots)
+{
+    runTest(1, 1, 100, 1000000, TacticallyNotifyAll);
+}
+
+TEST(WTF_Condition, TenProducersOneConsumerOneSlot)
+{
+    runTest(10, 1, 1, 10000, TacticallyNotifyAll);
+}
+
+TEST(WTF_Condition, TenProducersOneConsumerHundredSlotsNotifyAll)
+{
+    runTest(10, 1, 100, 10000, TacticallyNotifyAll);
+}
+
+TEST(WTF_Condition, TenProducersOneConsumerHundredSlotsNotifyOne)
+{
+    runTest(10, 1, 100, 10000, AlwaysNotifyOne);
+}
+
+TEST(WTF_Condition, OneProducerTenConsumersOneSlot)
+{
+    runTest(1, 10, 1, 10000, TacticallyNotifyAll);
+}
+
+TEST(WTF_Condition, OneProducerTenConsumersHundredSlotsNotifyAll)
+{
+    runTest(1, 10, 100, 100000, TacticallyNotifyAll);
+}
+
+TEST(WTF_Condition, OneProducerTenConsumersHundredSlotsNotifyOne)
+{
+    runTest(1, 10, 100, 100000, AlwaysNotifyOne);
+}
+
+TEST(WTF_Condition, TenProducersTenConsumersOneSlot)
+{
+    runTest(10, 10, 1, 50000, TacticallyNotifyAll);
+}
+
+TEST(WTF_Condition, TenProducersTenConsumersHundredSlotsNotifyAll)
+{
+    runTest(10, 10, 100, 50000, TacticallyNotifyAll);
+}
+
+TEST(WTF_Condition, TenProducersTenConsumersHundredSlotsNotifyOne)
+{
+    runTest(10, 10, 100, 50000, AlwaysNotifyOne);
+}
+
+TEST(WTF_Condition, TimeoutTimesOut)
+{
+    Lock lock;
+    Condition condition;
+
+    lock.lock();
+    bool result = condition.waitFor(
+        lock, std::chrono::microseconds(10000), [] () -> bool { return false; });
+    lock.unlock();
+
+    EXPECT_EQ(false, result);
+}
+
+} // namespace TestWebKitAPI
+
index 840ec84..8f2ed16 100644 (file)
@@ -53,7 +53,7 @@ void runLockTest(unsigned numThreadGroups, unsigned numThreadsPerGroup, unsigned
 
         for (unsigned threadIndex = numThreadsPerGroup; threadIndex--;) {
             threads[threadGroupIndex * numThreadsPerGroup + threadIndex] = createThread(
-                "Benchmark thread",
+                "Lock test thread",
                 [threadGroupIndex, &locks, &words, numIterations, workPerCriticalSection] () {
                     for (unsigned i = numIterations; i--;) {
                         locks[threadGroupIndex].lock();