Changeset 188400 in webkit


Ignore:
Timestamp:
Aug 13, 2015 1:42:11 PM (9 years ago)
Author:
fpizlo@apple.com
Message:

WTF should have a compact Condition object to use with Lock
​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.

Location:
trunk
Files:
2 added
12 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/WTF/ChangeLog

    r188386 r188400  
     12015-08-13  Filip Pizlo  <fpizlo@apple.com>
     2
     3        WTF should have a compact Condition object to use with Lock
     4        https://bugs.webkit.org/show_bug.cgi?id=147986
     5
     6        Reviewed by Geoffrey Garen.
     7
     8        Adds a condition variable implementation based on ParkingLot, called simply WTF::Condition.
     9        It can be used with WTF::Lock or actually any lock implementation. It should even work with
     10        WTF::SpinLock, WTF::Mutex, or std::mutex. Best of all, Condition only requires one byte.
     11
     12        ParkingLot almost contained all of the functionality needed to implemenet wait/notify. We
     13        could have implemented Condition using a 32-bit (or even 64-bit) version that protects
     14        against a notify that happens just before we park. But, this changes the ParkingLot API to
     15        give us the ability to run some code between when ParkingLot enqueues the current thread
     16        and when it actually sleeps. This callback is called with no locks held, so it can call
     17        unlock() on any kind of lock, so long as that lock's unlock() method doesn't recurse into
     18        ParkingLot::parkConditionally(). That seems unlikely; unlock() is more likely to call
     19        ParkingLot::unparkOne() or unparkAll(). WTF::Lock will never call parkConditionally()
     20        inside unlock(), so WTF::Lock is definitely appropriate for use with Condition.
     21
     22        Condition supports most of the API that std::condition_variable supports. It does some
     23        things to try to reduce footgun potential. The preferred timeout form is waitUntil() which
     24        takes an absolute time from the steady_clock. The only relative timeout form also takes a
     25        predicate callback, so it's impossible to write the subtly incorrect
     26        "while (...) wait_for(...)" idiom.
     27
     28        This patch doesn't actually introduce any uses of WTF::Condition other than the unit tests.
     29        I'll start switching code over to using WTF::Condition in another patch.
     30
     31        * WTF.vcxproj/WTF.vcxproj:
     32        * WTF.xcodeproj/project.pbxproj:
     33        * wtf/CMakeLists.txt:
     34        * wtf/Condition.h: Added.
     35        (WTF::Condition::Condition):
     36        (WTF::Condition::waitUntil):
     37        (WTF::Condition::waitFor):
     38        (WTF::Condition::wait):
     39        (WTF::Condition::notifyOne):
     40        (WTF::Condition::notifyAll):
     41        * wtf/Lock.cpp:
     42        (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.
     43        * wtf/ParkingLot.cpp:
     44        (WTF::ParkingLot::parkConditionally): Add the beforeSleep() callback.
     45        (WTF::ParkingLot::unparkOne):
     46        * wtf/ParkingLot.h:
     47        (WTF::ParkingLot::compareAndPark):
     48
    1492015-08-12  Anders Carlsson  <andersca@apple.com>
    250

  • trunk/Source/WTF/WTF.vcxproj/WTF.vcxproj

    r188323 r188400  
    177177    <ClInclude Include="..\wtf\CheckedBoolean.h" />
    178178    <ClInclude Include="..\wtf\Compiler.h" />
     179    <ClInclude Include="..\wtf\Condition.h" />
    179180    <ClInclude Include="..\wtf\CryptographicUtilities.h" />
    180181    <ClInclude Include="..\wtf\CryptographicallyRandomNumber.h" />

  • trunk/Source/WTF/WTF.xcodeproj/project.pbxproj

    r188323 r188400  
    4141                0FC4EDE61696149600F65041 /* CommaPrinter.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FC4EDE51696149600F65041 /* CommaPrinter.h */; };
    4242                0FD81AC5154FB22E00983E72 /* FastBitVector.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FD81AC4154FB22E00983E72 /* FastBitVector.h */; settings = {ATTRIBUTES = (); }; };
     43                0FDB698E1B7C643A000C1078 /* Condition.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FDB698D1B7C643A000C1078 /* Condition.h */; };
    4344                0FDDBFA71666DFA300C55FEF /* StringPrintStream.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FDDBFA51666DFA300C55FEF /* StringPrintStream.cpp */; };
    4445                0FDDBFA81666DFA300C55FEF /* StringPrintStream.h in Headers */ = {isa = PBXBuildFile; fileRef = 0FDDBFA61666DFA300C55FEF /* StringPrintStream.h */; };
    … …  
    328329                0FC4EDE51696149600F65041 /* CommaPrinter.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CommaPrinter.h; sourceTree = "<group>"; };
    329330                0FD81AC4154FB22E00983E72 /* FastBitVector.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FastBitVector.h; sourceTree = "<group>"; };
     331                0FDB698D1B7C643A000C1078 /* Condition.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Condition.h; sourceTree = "<group>"; };
    330332                0FDDBFA51666DFA300C55FEF /* StringPrintStream.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = StringPrintStream.cpp; sourceTree = "<group>"; };
    331333                0FDDBFA61666DFA300C55FEF /* StringPrintStream.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = StringPrintStream.h; sourceTree = "<group>"; };
    … …  
    731733                                0F8F2B90172E00F0007DBDA5 /* CompilationThread.h */,
    732734                                A8A47270151A825A004123FF /* Compiler.h */,
     735                                0FDB698D1B7C643A000C1078 /* Condition.h */,
    733736                                E15556F318A0CC18006F48FB /* CryptographicUtilities.cpp */,
    734737                                E15556F418A0CC18006F48FB /* CryptographicUtilities.h */,
    … …  
    11861189                                A8A47424151A825B004123FF /* SinglyLinkedList.h in Headers */,
    11871190                                A748745317A0BDAE00FA04CB /* SixCharacterHash.h in Headers */,
     1191                                0FDB698E1B7C643A000C1078 /* Condition.h in Headers */,
    11881192                                A8A47426151A825B004123FF /* Spectrum.h in Headers */,
    11891193                                A8A47428151A825B004123FF /* StackBounds.h in Headers */,

  • trunk/Source/WTF/wtf/CMakeLists.txt

    r188323 r188400  
    1111    CompilationThread.h
    1212    Compiler.h
     13    Condition.h
    1314    CryptographicUtilities.h
    1415    CryptographicallyRandomNumber.h

  • trunk/Source/WTF/wtf/Lock.cpp

    r188374 r188400  
    8282    for (;;) {
    8383        uint8_t oldByteValue = m_byte.load();
    84         ASSERT(oldByteValue == isHeldBit || oldByteValue == (isHeldBit | hasParkedBit));
     84        RELEASE_ASSERT(oldByteValue == isHeldBit || oldByteValue == (isHeldBit | hasParkedBit));
    8585       
    8686        if (oldByteValue == isHeldBit) {

  • trunk/Source/WTF/wtf/ParkingLot.cpp

    r188374 r188400  
    508508} // anonymous namespace
    509509
    510 bool ParkingLot::parkConditionally(const void* address, std::function<bool()> validation)
     510bool ParkingLot::parkConditionally(
     511    const void* address,
     512    std::function<bool()> validation,
     513    std::function<void()> beforeSleep,
     514    std::chrono::steady_clock::time_point timeout)
    511515{
    512516    if (verbose)
    … …  
    514518   
    515519    ThreadData* me = myThreadData();
     520
     521    // Guard against someone calling parkConditionally() recursively from beforeSleep().
     522    RELEASE_ASSERT(!me->address);
    516523
    517524    bool result = enqueue(
    … …  
    528535        return false;
    529536
    530     if (verbose)
    531         dataLog(toString(currentThread(), ": parking self: ", RawPointer(me), "\n"));
     537    beforeSleep();
     538
     539    bool didGetDequeued;
    532540    {
    533541        std::unique_lock<std::mutex> locker(me->parkingLock);
    534         while (me->address)
    535             me->parkingCondition.wait(locker);
    536     }
    537     if (verbose)
    538         dataLog(toString(currentThread(), ": unparked self: ", RawPointer(me), "\n"));
    539     return true;
     542        while (me->address && std::chrono::steady_clock::now() < timeout)
     543            me->parkingCondition.wait_until(locker, timeout);
     544        ASSERT(!me->address || me->address == address);
     545        didGetDequeued = !me->address;
     546    }
     547    if (didGetDequeued) {
     548        // Great! We actually got dequeued rather than the timeout expiring.
     549        return true;
     550    }
     551
     552    // Have to remove ourselves from the queue since we timed out and nobody has dequeued us yet.
     553
     554    // It's possible that we get unparked right here, just before dequeue() grabs a lock. It's
     555    // probably worthwhile to detect when this happens, and return true in that case, to ensure
     556    // that when we return false it really means that no unpark could have been responsible for us
     557    // waking up, and that if an unpark call did happen, it woke someone else up.
     558    bool didFind = false;
     559    dequeue(
     560        address, BucketMode::IgnoreEmpty,
     561        [&] (ThreadData* element) {
     562            if (element == me) {
     563                didFind = true;
     564                return DequeueResult::RemoveAndStop;
     565            }
     566            return DequeueResult::Ignore;
     567        },
     568        [] (bool) { });
     569
     570    ASSERT(!me->nextInQueue);
     571
     572    // Make sure that no matter what, me->address is null after this point.
     573    {
     574        std::lock_guard<std::mutex> locker(me->parkingLock);
     575        me->address = nullptr;
     576    }
     577
     578    // If we were not found in the search above, then we know that someone unparked us.
     579    return !didFind;
    540580}
    541581

  • trunk/Source/WTF/wtf/ParkingLot.h

    r188374 r188400  
    2727#define WTF_ParkingLot_h
    2828
     29#include <chrono>
    2930#include <functional>
    3031#include <wtf/Atomics.h>
    … …  
    4041    // Parks the thread in a queue associated with the given address, which cannot be null. The
    4142    // parking only succeeds if the validation function returns true while the queue lock is held.
    42     // Returns true if the thread actually slept, or false if it returned quickly because of
    43     // validation failure.
    44     WTF_EXPORT_PRIVATE static bool parkConditionally(const void* address, std::function<bool()> validation);
     43    // If validation returns false, it will unlock the internal parking queue and then it will
     44    // return without doing anything else. If validation returns true, it will enqueue the thread,
     45    // unlock the parking queue lock, call the beforeSleep function, and then it will sleep so long
     46    // as the thread continues to be on the queue and the timeout hasn't fired. Finally, this
     47    // returns true if we actually got unparked or false if the timeout was hit. Note that
     48    // beforeSleep is called with no locks held, so it's OK to do pretty much anything so long as
     49    // you don't recursively call parkConditionally(). You can call unparkOne()/unparkAll() though.
     50    // It's useful to use beforeSleep() to unlock some mutex in the implementation of
     51    // Condition::wait().
     52    WTF_EXPORT_PRIVATE static bool parkConditionally(
     53        const void* address,
     54        std::function<bool()> validation,
     55        std::function<void()> beforeSleep,
     56        std::chrono::steady_clock::time_point timeout);
    4557
     58    // Simple version of parkConditionally() that covers the most common case: you want to park
     59    // indefinitely so long as the value at the given address hasn't changed.
    4660    template<typename T, typename U>
    4761    static bool compareAndPark(const Atomic<T>* address, U expected)
    … …  
    5266                U value = address->load();
    5367                return value == expected;
    54             });
     68            },
     69            [] () { },
     70            std::chrono::steady_clock::time_point::max());
    5571    }
    5672

  • trunk/Tools/ChangeLog

    r188387 r188400  
     12015-08-13  Filip Pizlo  <fpizlo@apple.com>
     2
     3        WTF should have a compact Condition object to use with Lock
     4        https://bugs.webkit.org/show_bug.cgi?id=147986
     5
     6        Reviewed by Geoffrey Garen.
     7
     8        Add a test for WTF::Condition.
     9
     10        * TestWebKitAPI/CMakeLists.txt:
     11        * TestWebKitAPI/TestWebKitAPI.vcxproj/TestWebKitAPI.vcxproj:
     12        * TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:
     13        * TestWebKitAPI/Tests/WTF/Condition.cpp: Added.
     14        (TestWebKitAPI::TEST):
     15        * TestWebKitAPI/Tests/WTF/Lock.cpp:
     16        (TestWebKitAPI::runLockTest): Change the name of the thread.
     17
    1182015-08-13  Filip Pizlo  <fpizlo@apple.com>
    219

  • trunk/Tools/TestWebKitAPI/CMakeLists.txt

    r188280 r188400  
    4343    ${TESTWEBKITAPI_DIR}/Tests/WTF/AtomicString.cpp
    4444    ${TESTWEBKITAPI_DIR}/Tests/WTF/CString.cpp
     45    ${TESTWEBKITAPI_DIR}/Tests/WTF/Condition.cpp
    4546    ${TESTWEBKITAPI_DIR}/Tests/WTF/CheckedArithmeticOperations.cpp
    4647    ${TESTWEBKITAPI_DIR}/Tests/WTF/DateMath.cpp

  • trunk/Tools/TestWebKitAPI/TestWebKitAPI.vcxproj/TestWebKitAPI.vcxproj

    r188291 r188400  
    1 <?xml version="1.0" encoding="utf-8"?>
     1<?xml version="1.0" encoding="utf-8"?>
    22<Project DefaultTargets="Build" ToolsVersion="14.0" xmlns="http://schemas.microsoft.com/developer/msbuild/2003">
    33  <ItemGroup Label="ProjectConfigurations">
    … …  
    313313    <ClCompile Include="..\Tests\WTF\cf\RetainPtrHashing.cpp" />
    314314    <ClCompile Include="..\Tests\WTF\CheckedArithmeticOperations.cpp" />
     315    <ClCompile Include="..\Tests\WTF\Condition.cpp" />
    315316    <ClCompile Include="..\Tests\WTF\CString.cpp" />
    316317    <ClCompile Include="..\Tests\WTF\DateMath.cpp" />

  • trunk/Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj

    r188280 r188400  
    1313                0F3B94A71A77267400DE3272 /* WKWebViewEvaluateJavaScript.mm in Sources */ = {isa = PBXBuildFile; fileRef = 0F3B94A51A77266C00DE3272 /* WKWebViewEvaluateJavaScript.mm */; };
    1414                0FE447991B76F1EB009498EB /* ParkingLot.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FE447971B76F1E3009498EB /* ParkingLot.cpp */; };
     15                0FEAE3691B7D19D200CE17F2 /* Condition.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FEAE3671B7D19CB00CE17F2 /* Condition.cpp */; };
    1516                0FFC45A61B73EBEB0085BD62 /* Lock.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0FFC45A41B73EBE20085BD62 /* Lock.cpp */; };
    1617                1A02C870125D4CFD00E3F4BD /* find.html in Copy Resources */ = {isa = PBXBuildFile; fileRef = 1A02C84B125D4A5E00E3F4BD /* find.html */; };
    … …  
    432433                0FC6C4CE141034AD005B7F0C /* MetaAllocator.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = MetaAllocator.cpp; sourceTree = "<group>"; };
    433434                0FE447971B76F1E3009498EB /* ParkingLot.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = ParkingLot.cpp; sourceTree = "<group>"; };
     435                0FEAE3671B7D19CB00CE17F2 /* Condition.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Condition.cpp; sourceTree = "<group>"; };
    434436                0FFC45A41B73EBE20085BD62 /* Lock.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = Lock.cpp; sourceTree = "<group>"; };
    435437                14464012167A8305000BD218 /* LayoutUnit.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = LayoutUnit.cpp; sourceTree = "<group>"; };
    … …  
    10921094                                26F1B44215CA434F00D1E4BF /* AtomicString.cpp */,
    10931095                                A7A966DA140ECCC8005EF9B4 /* CheckedArithmeticOperations.cpp */,
     1096                                0FEAE3671B7D19CB00CE17F2 /* Condition.cpp */,
    10941097                                26A2C72E15E2E73C005B1A14 /* CString.cpp */,
    10951098                                E40019301ACE9B5C001B0A2A /* BloomFilter.cpp */,
    … …  
    14951498                                7CCE7EEF1A411AE600447C4C /* EphemeralSessionPushStateNoHistoryCallback.cpp in Sources */,
    14961499                                7CCE7EF01A411AE600447C4C /* EvaluateJavaScript.cpp in Sources */,
     1500                                0FEAE3691B7D19D200CE17F2 /* Condition.cpp in Sources */,
    14971501                                7CCE7EF11A411AE600447C4C /* FailedLoad.cpp in Sources */,
    14981502                                7CCE7EF31A411AE600447C4C /* Find.cpp in Sources */,

  • trunk/Tools/TestWebKitAPI/Tests/WTF/Lock.cpp

    r188387 r188400  
    5454        for (unsigned threadIndex = numThreadsPerGroup; threadIndex--;) {
    5555            threads[threadGroupIndex * numThreadsPerGroup + threadIndex] = createThread(
    56                 "Benchmark thread",
     56                "Lock test thread",
    5757                [threadGroupIndex, &locks, &words, numIterations, workPerCriticalSection] () {
    5858                    for (unsigned i = numIterations; i--;) {
Note: See TracChangeset for help on using the changeset viewer.