It should be easy to decide how WebKit yields
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 22 Jul 2017 14:36:18 +0000 (14:36 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 22 Jul 2017 14:36:18 +0000 (14:36 +0000)
https://bugs.webkit.org/show_bug.cgi?id=174298

Reviewed by Saam Barati.
Source/bmalloc:

Use sched_yield() explicitly.

* bmalloc/StaticMutex.cpp:
(bmalloc::StaticMutex::lockSlowCase):

Source/JavaScriptCore:

Use the new WTF::Thread::yield() function for yielding instead of the C++ function.

* heap/Heap.cpp:
(JSC::Heap::resumeThePeriphery):
* heap/VisitingTimeout.h:
* runtime/JSCell.cpp:
(JSC::JSCell::lockSlow):
(JSC::JSCell::unlockSlow):
* runtime/JSCell.h:
* runtime/JSCellInlines.h:
(JSC::JSCell::lock):
(JSC::JSCell::unlock):
* runtime/JSLock.cpp:
(JSC::JSLock::grabAllLocks):
* runtime/SamplingProfiler.cpp:

Source/WebCore:

No new tests because the WebCore change is just a change to how we #include things.

* inspector/InspectorPageAgent.h:
* inspector/TimelineRecordFactory.h:
* workers/Worker.h:
* workers/WorkerGlobalScopeProxy.h:
* workers/WorkerMessagingProxy.h:

Source/WebKitLegacy:

* Storage/StorageTracker.h:

Source/WTF:

Created a Thread::yield() abstraction for sched_yield(), and made WTF use it everywhere that it
had previously used std::this_thread::yield().

To make it less annoying to experiment with changes to the lock algorithm in the future, this also
moves the meat of the algorithm into LockAlgorithmInlines.h. Only two files include that header.
Since LockAlgorithm.h no longer includes ParkingLot.h, a bunch of files in WK now need to include
timing headers (Seconds, MonotonicTime, etc) manually.

* WTF.xcodeproj/project.pbxproj:
* benchmarks/ToyLocks.h:
* wtf/CMakeLists.txt:
* wtf/Lock.cpp:
* wtf/LockAlgorithm.h:
(WTF::LockAlgorithm::lockSlow): Deleted.
(WTF::LockAlgorithm::unlockSlow): Deleted.
* wtf/LockAlgorithmInlines.h: Added.
(WTF::hasParkedBit>::lockSlow):
(WTF::hasParkedBit>::unlockSlow):
* wtf/MainThread.cpp:
* wtf/RunLoopTimer.h:
* wtf/Threading.cpp:
* wtf/Threading.h:
* wtf/ThreadingPthreads.cpp:
(WTF::Thread::yield):
* wtf/ThreadingWin.cpp:
(WTF::Thread::yield):
* wtf/WordLock.cpp:
(WTF::WordLockBase::lockSlow):
(WTF::WordLockBase::unlockSlow):

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

32 files changed:
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/heap/Heap.cpp
Source/JavaScriptCore/heap/VisitingTimeout.h
Source/JavaScriptCore/runtime/JSCell.cpp
Source/JavaScriptCore/runtime/JSCell.h
Source/JavaScriptCore/runtime/JSCellInlines.h
Source/JavaScriptCore/runtime/JSLock.cpp
Source/JavaScriptCore/runtime/SamplingProfiler.cpp
Source/WTF/ChangeLog
Source/WTF/WTF.xcodeproj/project.pbxproj
Source/WTF/benchmarks/ToyLocks.h
Source/WTF/wtf/CMakeLists.txt
Source/WTF/wtf/Lock.cpp
Source/WTF/wtf/LockAlgorithm.h
Source/WTF/wtf/LockAlgorithmInlines.h [new file with mode: 0644]
Source/WTF/wtf/MainThread.cpp
Source/WTF/wtf/RunLoopTimer.h
Source/WTF/wtf/Threading.cpp
Source/WTF/wtf/Threading.h
Source/WTF/wtf/ThreadingPthreads.cpp
Source/WTF/wtf/ThreadingWin.cpp
Source/WTF/wtf/WordLock.cpp
Source/WebCore/ChangeLog
Source/WebCore/inspector/InspectorPageAgent.h
Source/WebCore/inspector/TimelineRecordFactory.h
Source/WebCore/workers/Worker.h
Source/WebCore/workers/WorkerGlobalScopeProxy.h
Source/WebCore/workers/WorkerMessagingProxy.h
Source/WebKitLegacy/ChangeLog
Source/WebKitLegacy/Storage/StorageTracker.h
Source/bmalloc/ChangeLog
Source/bmalloc/bmalloc/StaticMutex.cpp

index b4633bb4110740be46ef5429c8d93218226ddccc..d6a929b4ebc4408626bbac4b72adbd3cb03473ee 100644 (file)
@@ -1,3 +1,26 @@
+2017-07-14  Filip Pizlo  <fpizlo@apple.com>
+
+        It should be easy to decide how WebKit yields
+        https://bugs.webkit.org/show_bug.cgi?id=174298
+
+        Reviewed by Saam Barati.
+        
+        Use the new WTF::Thread::yield() function for yielding instead of the C++ function.
+
+        * heap/Heap.cpp:
+        (JSC::Heap::resumeThePeriphery):
+        * heap/VisitingTimeout.h:
+        * runtime/JSCell.cpp:
+        (JSC::JSCell::lockSlow):
+        (JSC::JSCell::unlockSlow):
+        * runtime/JSCell.h:
+        * runtime/JSCellInlines.h:
+        (JSC::JSCell::lock):
+        (JSC::JSCell::unlock):
+        * runtime/JSLock.cpp:
+        (JSC::JSLock::grabAllLocks):
+        * runtime/SamplingProfiler.cpp:
+
 2017-07-21  Mark Lam  <mark.lam@apple.com>
 
         Refactor MASM probe CPUState to use arrays for register storage.
index a909dd07c4b4db783f116507e23af50a09a5b49b..f65ef841a7c1e006a2eab71524fdde8a6aa2a267 100644 (file)
@@ -79,6 +79,7 @@
 #include <wtf/ProcessID.h>
 #include <wtf/RAMSize.h>
 #include <wtf/SimpleStats.h>
+#include <wtf/Threading.h>
 
 #if USE(FOUNDATION)
 #if __has_include(<objc/objc-internal.h>)
@@ -1620,7 +1621,7 @@ NEVER_INLINE void Heap::resumeThePeriphery()
                 slotVisitorsToUpdate.takeLast();
             }
         }
-        std::this_thread::yield();
+        WTF::Thread::yield();
     }
     
     for (SlotVisitor* slotVisitor : slotVisitorsToUpdate)
index f1ac861f3b087c03c7645ee84ab84212aebd3663..609766232dccba46cae1090918e3704e5c4821f8 100644 (file)
@@ -26,7 +26,7 @@
 #pragma once
 
 #include "SlotVisitor.h"
-#include <wtf/MonotonicTime.h>
+#include <wtf/TimeWithDynamicClockType.h>
 
 namespace JSC {
 
index 013b7dd7592113bd99476e3d502c98b0a96fb375..44da987f31803a08b6a16ae92aeb3cb7041b0546 100644 (file)
@@ -30,6 +30,7 @@
 #include "JSObject.h"
 #include "NumberObject.h"
 #include "WebAssemblyToJSCallee.h"
+#include <wtf/LockAlgorithmInlines.h>
 #include <wtf/MathExtras.h>
 
 namespace JSC {
@@ -294,4 +295,16 @@ JSValue JSCell::getPrototype(JSObject*, ExecState*)
     RELEASE_ASSERT_NOT_REACHED();
 }
 
+void JSCell::lockSlow()
+{
+    Atomic<IndexingType>* lock = bitwise_cast<Atomic<IndexingType>*>(&m_indexingTypeAndMisc);
+    IndexingTypeLockAlgorithm::lockSlow(*lock);
+}
+
+void JSCell::unlockSlow()
+{
+    Atomic<IndexingType>* lock = bitwise_cast<Atomic<IndexingType>*>(&m_indexingTypeAndMisc);
+    IndexingTypeLockAlgorithm::unlockSlow(*lock);
+}
+
 } // namespace JSC
index 65e1a778fc37e85fc0b37e378edf397176aebc76..39318039c5e4d4a21203302f529c3eeacdbaa823 100644 (file)
@@ -265,6 +265,8 @@ private:
     friend class LLIntOffsetsExtractor;
 
     JS_EXPORT_PRIVATE JSObject* toObjectSlow(ExecState*, JSGlobalObject*) const;
+    JS_EXPORT_PRIVATE void lockSlow();
+    JS_EXPORT_PRIVATE void unlockSlow();
 
     StructureID m_structureID;
     IndexingType m_indexingTypeAndMisc; // DO NOT store to this field. Always CAS.
index 3571a0863c2c245597a0e176f13ab2660c4844be..9dd3e995a89c857a9040bb1be62ecc62b74ff6f4 100644 (file)
@@ -329,7 +329,8 @@ inline void JSCell::callDestructor(VM& vm)
 inline void JSCell::lock()
 {
     Atomic<IndexingType>* lock = bitwise_cast<Atomic<IndexingType>*>(&m_indexingTypeAndMisc);
-    IndexingTypeLockAlgorithm::lock(*lock);
+    if (UNLIKELY(!IndexingTypeLockAlgorithm::lockFast(*lock)))
+        lockSlow();
 }
 
 inline bool JSCell::tryLock()
@@ -341,7 +342,8 @@ inline bool JSCell::tryLock()
 inline void JSCell::unlock()
 {
     Atomic<IndexingType>* lock = bitwise_cast<Atomic<IndexingType>*>(&m_indexingTypeAndMisc);
-    IndexingTypeLockAlgorithm::unlock(*lock);
+    if (UNLIKELY(!IndexingTypeLockAlgorithm::unlockFast(*lock)))
+        unlockSlow();
 }
 
 inline bool JSCell::isLocked() const
index dbd6a581a22dc1fa75c02178894f6b40f784dc4d..ba6c44a5df514de517c9a2587561a98a9d92410e 100644 (file)
@@ -246,7 +246,7 @@ void JSLock::grabAllLocks(DropAllLocks* dropper, unsigned droppedLockCount)
 
     while (dropper->dropDepth() != m_lockDropDepth) {
         unlock(droppedLockCount);
-        std::this_thread::yield();
+        Thread::yield();
         lock(droppedLockCount);
     }
 
index 0159de1487a61e28a551afdff3a25836b936209a..a4be95b13582b77a9686e9d3276a6c9d5b95cd7e 100644 (file)
@@ -48,6 +48,7 @@
 #include "SlotVisitor.h"
 #include "StrongInlines.h"
 #include "VM.h"
+#include <thread>
 #include <wtf/FilePrintStream.h>
 #include <wtf/HashSet.h>
 #include <wtf/RefPtr.h>
index 6ac443708c7d04d5548454e50a2881ad63339bf2..fe33513065eaab4b523c8704e579293d243d8b2d 100644 (file)
@@ -1,3 +1,40 @@
+2017-07-14  Filip Pizlo  <fpizlo@apple.com>
+
+        It should be easy to decide how WebKit yields
+        https://bugs.webkit.org/show_bug.cgi?id=174298
+
+        Reviewed by Saam Barati.
+        
+        Created a Thread::yield() abstraction for sched_yield(), and made WTF use it everywhere that it
+        had previously used std::this_thread::yield().
+        
+        To make it less annoying to experiment with changes to the lock algorithm in the future, this also
+        moves the meat of the algorithm into LockAlgorithmInlines.h. Only two files include that header.
+        Since LockAlgorithm.h no longer includes ParkingLot.h, a bunch of files in WK now need to include
+        timing headers (Seconds, MonotonicTime, etc) manually.
+
+        * WTF.xcodeproj/project.pbxproj:
+        * benchmarks/ToyLocks.h:
+        * wtf/CMakeLists.txt:
+        * wtf/Lock.cpp:
+        * wtf/LockAlgorithm.h:
+        (WTF::LockAlgorithm::lockSlow): Deleted.
+        (WTF::LockAlgorithm::unlockSlow): Deleted.
+        * wtf/LockAlgorithmInlines.h: Added.
+        (WTF::hasParkedBit>::lockSlow):
+        (WTF::hasParkedBit>::unlockSlow):
+        * wtf/MainThread.cpp:
+        * wtf/RunLoopTimer.h:
+        * wtf/Threading.cpp:
+        * wtf/Threading.h:
+        * wtf/ThreadingPthreads.cpp:
+        (WTF::Thread::yield):
+        * wtf/ThreadingWin.cpp:
+        (WTF::Thread::yield):
+        * wtf/WordLock.cpp:
+        (WTF::WordLockBase::lockSlow):
+        (WTF::WordLockBase::unlockSlow):
+
 2017-07-22  Yusuke Suzuki  <utatane.tea@gmail.com>
 
         [WTF] Extend ThreadGroup::add results from bool to ThreadGroupAddResult
index 98cd23d253a0a13d6469bd1de21fc126e600e0e6..95c908e9760f68fcef5dade1b165178f5918acae 100644 (file)
                0F30BA8D1E78708E002CA847 /* LoggingHashMap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = LoggingHashMap.h; sourceTree = "<group>"; };
                0F30BA8E1E78708E002CA847 /* LoggingHashSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = LoggingHashSet.h; sourceTree = "<group>"; };
                0F30BA8F1E78708E002CA847 /* LoggingHashTraits.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = LoggingHashTraits.h; sourceTree = "<group>"; };
+               0F31DD701F1308BC0072EB4A /* LockAlgorithmInlines.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = LockAlgorithmInlines.h; sourceTree = "<group>"; };
                0F3501631BB258C800F0A2A3 /* WeakRandom.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = WeakRandom.h; sourceTree = "<group>"; };
                0F43D8EF1DB5ADDC00108FB6 /* AutomaticThread.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = AutomaticThread.cpp; sourceTree = "<group>"; };
                0F43D8F01DB5ADDC00108FB6 /* AutomaticThread.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = AutomaticThread.h; sourceTree = "<group>"; };
                9BC70F04176C379D00101DEC /* AtomicStringTable.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = AtomicStringTable.cpp; sourceTree = "<group>"; };
                9BD8F40A176C2AD80002D865 /* AtomicStringTable.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = AtomicStringTable.h; sourceTree = "<group>"; };
                9C67C542589348E285B49699 /* IndexedContainerIterator.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = IndexedContainerIterator.h; sourceTree = "<group>"; };
-               A30D412C1F0DE0BA00B71954 /* SoftLinking.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = SoftLinking.h; path = SoftLinking.h; sourceTree = "<group>"; };
-               A30D412D1F0DE13F00B71954 /* SoftLinking.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = SoftLinking.h; path = SoftLinking.h; sourceTree = "<group>"; };
+               A30D412C1F0DE0BA00B71954 /* SoftLinking.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SoftLinking.h; sourceTree = "<group>"; };
+               A30D412D1F0DE13F00B71954 /* SoftLinking.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SoftLinking.h; sourceTree = "<group>"; };
                A5098AFF1C169E0700087797 /* SandboxSPI.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SandboxSPI.h; sourceTree = "<group>"; };
                A5098B011C16A4F900087797 /* SecuritySPI.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = SecuritySPI.h; sourceTree = "<group>"; };
                A561F30F1DF2642100FF675D /* DeprecatedOptional.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = DeprecatedOptional.h; sourceTree = "<group>"; };
                                0FF4B4C41E88939C00DBBE86 /* Liveness.h */,
                                0FE164681B6FFC9600400E7C /* Lock.cpp */,
                                0FE164691B6FFC9600400E7C /* Lock.h */,
+                               0F31DD701F1308BC0072EB4A /* LockAlgorithmInlines.h */,
                                0F0FCDDD1DD167F900CCAB53 /* LockAlgorithm.h */,
                                0F60F32D1DFCBD1B00416D6C /* LockedPrintStream.cpp */,
                                0F60F32E1DFCBD1B00416D6C /* LockedPrintStream.h */,
index 3869b0da15f4b79abfe1b32e1fc91128419d60ba..090ad96d4d50047387aa3cc625dceb2b1e353885 100644 (file)
@@ -52,7 +52,7 @@ public:
     void lock()
     {
         while (!m_lock.compareExchangeWeak(0, 1, std::memory_order_acquire))
-            std::this_thread::yield();
+            Thread::yield();
     }
 
     void unlock()
@@ -118,7 +118,7 @@ public:
                 : "memory");
             if (result)
                 return;
-            std::this_thread::yield();
+            Thread::yield();
         }
     }
 
@@ -215,7 +215,7 @@ private:
             if (currentState & hasParkedBit)
                 break;
             
-            std::this_thread::yield();
+            Thread::yield();
         }
         
         for (;;) {
@@ -292,7 +292,7 @@ private:
             if (currentState == LockedAndParked)
                 break;
             
-            std::this_thread::yield();
+            Thread::yield();
         }
         
         for (;;) {
@@ -361,7 +361,7 @@ private:
             if (currentState == LockedAndParked)
                 break;
             
-            std::this_thread::yield();
+            Thread::yield();
         }
         
         State desiredState = Locked;
index f73bd5bb2215b34f25192597fabf0189be9294ee..abd66cc00731a515e1c77316e3937bcd70318e43 100644 (file)
@@ -60,6 +60,7 @@ set(WTF_HEADERS
     ListHashSet.h
     Liveness.h
     Lock.h
+    LockAlgorithmInlines.h
     LockAlgorithm.h
     LockedPrintStream.h
     Locker.h
index 1d295f68eb798532aedb9638ebc7b1eb9f9e5e58..ba869e9ab77dfe1dbd2a286c9ad22c06b95a1e65 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
+ * Copyright (C) 2015-2017 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -26,6 +26,8 @@
 #include "config.h"
 #include "Lock.h"
 
+#include <wtf/LockAlgorithmInlines.h>
+
 namespace WTF {
 
 void LockBase::lockSlow()
index 25a37a4f2c855e6423f6abe8c7ddb358af0f888e..451485477acf6564b82877d3e659e90278c8951e 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
+ * Copyright (C) 2015-2017 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
 #ifndef WTF_LockAlgorithm_h
 #define WTF_LockAlgorithm_h
 
-#include <thread>
 #include <wtf/Atomics.h>
 #include <wtf/Compiler.h>
-#include <wtf/ParkingLot.h>
+#include <wtf/Threading.h>
 
 namespace WTF {
 
@@ -123,108 +122,13 @@ public:
         return lock.load(std::memory_order_acquire) & isHeldBit;
     }
     
-    NEVER_INLINE static void lockSlow(Atomic<LockType>& lock)
-    {
-        unsigned spinCount = 0;
-
-        // This magic number turns out to be optimal based on past JikesRVM experiments.
-        const unsigned spinLimit = 40;
-    
-        for (;;) {
-            uint8_t currentByteValue = lock.load();
-
-            // We allow ourselves to barge in.
-            if (!(currentByteValue & isHeldBit)
-                && lock.compareExchangeWeak(currentByteValue, currentByteValue | isHeldBit))
-                return;
-
-            // If there is nobody parked and we haven't spun too much, we can just try to spin around.
-            if (!(currentByteValue & hasParkedBit) && spinCount < spinLimit) {
-                spinCount++;
-                std::this_thread::yield();
-                continue;
-            }
-
-            // Need to park. We do this by setting the parked bit first, and then parking. We spin around
-            // if the parked bit wasn't set and we failed at setting it.
-            if (!(currentByteValue & hasParkedBit)
-                && !lock.compareExchangeWeak(currentByteValue, currentByteValue | hasParkedBit))
-                continue;
-
-            // We now expect the value to be isHeld|hasParked. So long as that's the case, we can park.
-            ParkingLot::ParkResult parkResult =
-                ParkingLot::compareAndPark(&lock, currentByteValue | 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(isLocked(lock));
-                    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;
-                }
-            }
-
-            // We have awoken, or we never parked because the byte value changed. Either way, we loop
-            // around and try again.
-        }
-    }
+    NEVER_INLINE static void lockSlow(Atomic<LockType>& lock);
     
     enum Fairness {
-        Fair,
-        Unfair
+        Unfair,
+        Fair
     };
-    NEVER_INLINE static void unlockSlow(Atomic<LockType>& lock, Fairness fairness)
-    {
-        // We could get here because the weak CAS in unlock() failed spuriously, or because there is
-        // someone parked. So, we need a CAS loop: even if right now the lock is just held, it could
-        // be held and parked if someone attempts to lock just as we are unlocking.
-        for (;;) {
-            uint8_t oldByteValue = lock.load();
-            RELEASE_ASSERT(
-                (oldByteValue & mask) == isHeldBit
-                || (oldByteValue & mask) == (isHeldBit | hasParkedBit));
-        
-            if ((oldByteValue & mask) == isHeldBit) {
-                if (lock.compareExchangeWeak(oldByteValue, oldByteValue & ~isHeldBit))
-                    return;
-                continue;
-            }
-
-            // 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.
-            ASSERT((oldByteValue & mask) == (isHeldBit | hasParkedBit));
-            ParkingLot::unparkOne(
-                &lock,
-                [&] (ParkingLot::UnparkResult result) -> intptr_t {
-                    // We are the only ones that can clear either the isHeldBit or the hasParkedBit,
-                    // so we should still see both bits set right now.
-                    ASSERT((lock.load() & mask) == (isHeldBit | hasParkedBit));
-                
-                    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;
-                    }
-                    
-                    lock.transaction(
-                        [&] (LockType& value) -> bool {
-                            value &= ~mask;
-                            if (result.mayHaveMoreThreads)
-                                value |= hasParkedBit;
-                            return true;
-                        });
-                    return BargingOpportunity;
-                });
-            return;
-        }
-    }
+    NEVER_INLINE static void unlockSlow(Atomic<LockType>& lock, Fairness fairness = Unfair);
     
     NEVER_INLINE static void safepointSlow(Atomic<LockType>& lockWord)
     {
diff --git a/Source/WTF/wtf/LockAlgorithmInlines.h b/Source/WTF/wtf/LockAlgorithmInlines.h
new file mode 100644 (file)
index 0000000..8438d2e
--- /dev/null
@@ -0,0 +1,139 @@
+/*
+ * Copyright (C) 2015-2017 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. 
+ */
+
+#pragma once
+
+#include <wtf/LockAlgorithm.h>
+#include <wtf/ParkingLot.h>
+
+// It's a good idea to avoid including this header in too many places, so that it's possible to change
+// the lock algorithm slow path without recompiling the world. Right now this should be included in two
+// places (Lock.cpp and JSCell.cpp).
+
+namespace WTF {
+
+template<typename LockType, LockType isHeldBit, LockType hasParkedBit>
+void LockAlgorithm<LockType, isHeldBit, hasParkedBit>::lockSlow(Atomic<LockType>& lock)
+{
+    // This magic number turns out to be optimal based on past JikesRVM experiments.
+    static const unsigned spinLimit = 40;
+    
+    unsigned spinCount = 0;
+    
+    for (;;) {
+        uint8_t currentByteValue = lock.load();
+        
+        // We allow ourselves to barge in.
+        if (!(currentByteValue & isHeldBit)
+            && lock.compareExchangeWeak(currentByteValue, currentByteValue | isHeldBit))
+            return;
+
+        // If there is nobody parked and we haven't spun too much, we can just try to spin around.
+        if (!(currentByteValue & hasParkedBit) && spinCount < spinLimit) {
+            spinCount++;
+            Thread::yield();
+            continue;
+        }
+
+        // Need to park. We do this by setting the parked bit first, and then parking. We spin around
+        // if the parked bit wasn't set and we failed at setting it.
+        if (!(currentByteValue & hasParkedBit)
+            && !lock.compareExchangeWeak(currentByteValue, currentByteValue | hasParkedBit))
+            continue;
+
+        // We now expect the value to be isHeld|hasParked. So long as that's the case, we can park.
+        ParkingLot::ParkResult parkResult =
+            ParkingLot::compareAndPark(&lock, currentByteValue | 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(isLocked(lock));
+                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;
+            }
+        }
+
+        // We have awoken, or we never parked because the byte value changed. Either way, we loop
+        // around and try again.
+    }
+}
+
+template<typename LockType, LockType isHeldBit, LockType hasParkedBit>
+void LockAlgorithm<LockType, isHeldBit, hasParkedBit>::unlockSlow(Atomic<LockType>& lock, Fairness fairness)
+{
+    // We could get here because the weak CAS in unlock() failed spuriously, or because there is
+    // someone parked. So, we need a CAS loop: even if right now the lock is just held, it could
+    // be held and parked if someone attempts to lock just as we are unlocking.
+    for (;;) {
+        uint8_t oldByteValue = lock.load();
+        RELEASE_ASSERT(
+            (oldByteValue & mask) == isHeldBit
+            || (oldByteValue & mask) == (isHeldBit | hasParkedBit));
+        
+        if ((oldByteValue & mask) == isHeldBit) {
+            if (lock.compareExchangeWeak(oldByteValue, oldByteValue & ~isHeldBit))
+                return;
+            continue;
+        }
+
+        // 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.
+        ASSERT((oldByteValue & mask) == (isHeldBit | hasParkedBit));
+        ParkingLot::unparkOne(
+            &lock,
+            [&] (ParkingLot::UnparkResult result) -> intptr_t {
+                // We are the only ones that can clear either the isHeldBit or the hasParkedBit,
+                // so we should still see both bits set right now.
+                ASSERT((lock.load() & mask) == (isHeldBit | hasParkedBit));
+                
+                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;
+                }
+                
+                lock.transaction(
+                    [&] (LockType& value) -> bool {
+                        value &= ~mask;
+                        if (result.mayHaveMoreThreads)
+                            value |= hasParkedBit;
+                        return true;
+                    });
+                return BargingOpportunity;
+            });
+        return;
+    }
+}
+
+} // namespace WTF
+
index 25a283e83d5c31da9e57dbb9223a84357cd2c4ff..161e7a37add69017d1f9e89315e721f3fe8d83d5 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2007, 2008, 2015-2016 Apple Inc. All rights reserved.
+ * Copyright (C) 2007-2017 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -31,6 +31,7 @@
 
 #include "CurrentTime.h"
 #include "Deque.h"
+#include "MonotonicTime.h"
 #include "StdLibExtras.h"
 #include "Threading.h"
 #include <mutex>
index e5e557c0d2752b93cb9b08899911bfc59bb59b45..39a9f3a176fdfca973d0851973e8ba9bc186b680 100644 (file)
@@ -30,6 +30,7 @@
 #define RunLoopTimer_h
 
 #include <wtf/SchedulePair.h>
+#include <wtf/Seconds.h>
 #include <wtf/RetainPtr.h>
 
 namespace WTF {
index d49ccfb6bb605484479bb1cde50e4711fc72d5a0..4e4bfb952c01f733282f473604e0c8ea7d48f1fa 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2008, 2009, 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2008-2017 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -29,6 +29,7 @@
 #include <algorithm>
 #include <cmath>
 #include <cstring>
+#include <thread>
 #include <wtf/DateMath.h>
 #include <wtf/PrintStream.h>
 #include <wtf/RandomNumberSeed.h>
index 3ab27c44371c3a95f6265acd2c992579af8575cb..59245dd4ff88b79c7f90899d03a6c0d6f3bb76d5 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2007, 2008, 2010, 2014 Apple Inc. All rights reserved.
+ * Copyright (C) 2007-2017 Apple Inc. All rights reserved.
  * Copyright (C) 2007 Justin Haygood <jhaygood@reaktix.com>
  * Copyright (C) 2017 Yusuke Suzuki <utatane.tea@gmail.com>
  *
@@ -116,6 +116,9 @@ public:
     // Helpful for platforms where the thread name must be set from within the thread.
     static void initializeCurrentThreadInternal(Thread&, const char* threadName);
     static void initializeCurrentThreadEvenIfNonWTFCreated(Thread&);
+    
+    WTF_EXPORT_PRIVATE static const unsigned lockSpinLimit;
+    WTF_EXPORT_PRIVATE static void yield();
 
     WTF_EXPORT_PRIVATE void dump(PrintStream& out) const;
 
index 55db3d6f83711a7d9d19cb51502a1ce6c1e9c9d8..249ca85c96261773dee48a347f986b57f3eeed10 100644 (file)
@@ -533,6 +533,11 @@ void ThreadCondition::broadcast()
     ASSERT_UNUSED(result, !result);
 }
 
+void Thread::yield()
+{
+    sched_yield();
+}
+
 } // namespace WTF
 
 #endif // USE(PTHREADS)
index f2304e6e1c6c41fad3ea1e2f99b213e40128d03a..7d339366d16c9af1491b349edd412f120648ad3e 100644 (file)
@@ -522,6 +522,11 @@ int waitForThreadCompletion(ThreadIdentifier threadID)
 
 }
 
+void Thread::yield()
+{
+    SwitchToThread();
+}
+
 } // namespace WTF
 
 #endif // OS(WINDOWS)
index 774fec368a866385c39b2f2e530af35dd0fcadbe..9e8fb9bff05f6e6beaf890b6dd19d1c29a0845f0 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2015-2016 Apple Inc. All rights reserved.
+ * Copyright (C) 2015-2017 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -27,6 +27,7 @@
 #include "WordLock.h"
 
 #include "ThreadSpecific.h"
+#include "Threading.h"
 #include "ThreadingPrimitives.h"
 #include <condition_variable>
 #include <mutex>
@@ -99,7 +100,7 @@ NEVER_INLINE void WordLockBase::lockSlow()
         // If there is no queue and we haven't spun too much, we can just try to spin around again.
         if (!(currentWordValue & ~queueHeadMask) && spinCount < spinLimit) {
             spinCount++;
-            std::this_thread::yield();
+            Thread::yield();
             continue;
         }
 
@@ -120,7 +121,7 @@ NEVER_INLINE void WordLockBase::lockSlow()
         if ((currentWordValue & isQueueLockedBit)
             || !(currentWordValue & isLockedBit)
             || !m_word.compareExchangeWeak(currentWordValue, currentWordValue | isQueueLockedBit)) {
-            std::this_thread::yield();
+            Thread::yield();
             continue;
         }
         
@@ -197,12 +198,12 @@ NEVER_INLINE void WordLockBase::unlockSlow()
                 return;
             }
             // Loop around and try again.
-            std::this_thread::yield();
+            Thread::yield();
             continue;
         }
         
         if (currentWordValue & isQueueLockedBit) {
-            std::this_thread::yield();
+            Thread::yield();
             continue;
         }
 
index 9709df4548c742f4ba3ccc29dfea2fab221a8a87..70c4ed8dfb27ccb29cff9a777d5d4f7814b70f36 100644 (file)
@@ -1,3 +1,18 @@
+2017-07-14  Filip Pizlo  <fpizlo@apple.com>
+
+        It should be easy to decide how WebKit yields
+        https://bugs.webkit.org/show_bug.cgi?id=174298
+
+        Reviewed by Saam Barati.
+
+        No new tests because the WebCore change is just a change to how we #include things.
+
+        * inspector/InspectorPageAgent.h:
+        * inspector/TimelineRecordFactory.h:
+        * workers/Worker.h:
+        * workers/WorkerGlobalScopeProxy.h:
+        * workers/WorkerMessagingProxy.h:
+
 2017-07-22  Said Abou-Hallawa  <sabouhallawa@apple.com>
 
         REGRESSION(r219045): A partially loaded image may not be repainted when its complete frame finishes decoding
index 1c3d15b4ba364022bb76fa59553684cb5470f8d7..9bbf568e8ca2f46389c5cd12ac451d5684c64bc5 100644 (file)
@@ -36,6 +36,7 @@
 #include <inspector/InspectorBackendDispatchers.h>
 #include <inspector/InspectorFrontendDispatchers.h>
 #include <wtf/HashMap.h>
+#include <wtf/Seconds.h>
 #include <wtf/text/WTFString.h>
 
 namespace Inspector {
index ddf8d05dfe4ee36d840416b41aaa7e741aa564bf..dd9de60120ee182bad5b02db0c13fd1f4cd141e4 100644 (file)
@@ -33,6 +33,7 @@
 
 #include <inspector/InspectorValues.h>
 #include <wtf/Forward.h>
+#include <wtf/Seconds.h>
 #include <wtf/text/WTFString.h>
 
 namespace Inspector {
index 9a9a4145a317953ae3588aa31182fd2c2955e505..0bf32450db4ca5f6c42003d5d9298b3104cb36fd 100644 (file)
@@ -32,6 +32,7 @@
 #include "MessagePort.h"
 #include "WorkerScriptLoaderClient.h"
 #include <runtime/RuntimeFlags.h>
+#include <wtf/MonotonicTime.h>
 #include <wtf/Optional.h>
 #include <wtf/text/AtomicStringHash.h>
 
index 1cff6b7dc6047cc62c94d9a90631f19579ac1e19..93855737508ebc718f7e1c95bd3e87260fdcc441 100644 (file)
@@ -33,6 +33,7 @@
 
 #include "MessagePortChannel.h"
 #include <runtime/RuntimeFlags.h>
+#include <wtf/MonotonicTime.h>
 
 namespace WebCore {
 
index 8fd3cd6a3f981befa28d4ece3f9af43f73024fb3..c90008b12d6b7839383bb3c1c2c328a3bfa8728c 100644 (file)
@@ -28,6 +28,7 @@
 #include "WorkerGlobalScopeProxy.h"
 #include "WorkerLoaderProxy.h"
 #include "WorkerObjectProxy.h"
+#include <wtf/MonotonicTime.h>
 #include <wtf/ThreadSafeRefCounted.h>
 
 namespace WebCore {
index 18e8f872edb9642fb708f171f25ed33bae40c95c..b2d360b1d6c9482b7d362d85d29dd079d97afc83 100644 (file)
@@ -1,3 +1,12 @@
+2017-07-14  Filip Pizlo  <fpizlo@apple.com>
+
+        It should be easy to decide how WebKit yields
+        https://bugs.webkit.org/show_bug.cgi?id=174298
+
+        Reviewed by Saam Barati.
+
+        * Storage/StorageTracker.h:
+
 2017-07-21  Konstantin Tokarev  <annulen@yandex.ru>
 
         Unreviewed, fix Mac cmake build after r219733
index e1ed6b936b6f77dc0d1818a65a4b713084c9067b..238f635c0b17d6666b0c1b6db435468cb52f7605 100644 (file)
@@ -27,6 +27,7 @@
 
 #include <WebCore/SQLiteDatabase.h>
 #include <wtf/HashSet.h>
+#include <wtf/Seconds.h>
 #include <wtf/Vector.h>
 #include <wtf/text/StringHash.h>
 #include <wtf/text/WTFString.h>
index 0ee9959835f042a5af14aa5ea15a9291e22be66b..43319c723be1b7ffdf8f5810ce8e0f7962d22db3 100644 (file)
@@ -1,3 +1,15 @@
+2017-07-14  Filip Pizlo  <fpizlo@apple.com>
+
+        It should be easy to decide how WebKit yields
+        https://bugs.webkit.org/show_bug.cgi?id=174298
+
+        Reviewed by Saam Barati.
+        
+        Use sched_yield() explicitly.
+
+        * bmalloc/StaticMutex.cpp:
+        (bmalloc::StaticMutex::lockSlowCase):
+
 2017-07-20  Chris Dumez  <cdumez@apple.com>
 
         Replace calls to Vector::resize() with calls to more efficient shrink() / grow() when applicable
index ea25b1bdf969d6a38c344a15db79b20706314186..1e2e1c3c0c084e33c2ea31aaa8551eb0326dd455 100644 (file)
@@ -47,7 +47,7 @@ void StaticMutex::lockSlowCase()
 
     // Avoid spinning pathologically.
     while (!try_lock())
-        std::this_thread::yield();
+        sched_yield();
 }
 
 } // namespace bmalloc