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 b4633bb..d6a929b 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 a909dd0..f65ef84 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 f1ac861..6097662 100644 (file)
@@ -26,7 +26,7 @@
 #pragma once
 
 #include "SlotVisitor.h"
-#include <wtf/MonotonicTime.h>
+#include <wtf/TimeWithDynamicClockType.h>
 
 namespace JSC {
 
index 013b7dd..44da987 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 65e1a77..3931803 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 3571a08..9dd3e99 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 dbd6a58..ba6c44a 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 0159de1..a4be95b 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 6ac4437..fe33513 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 98cd23d..95c908e 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 3869b0d..090ad96 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 f73bd5b..abd66cc 100644 (file)
@@ -60,6 +60,7 @@ set(WTF_HEADERS
     ListHashSet.h
     Liveness.h
     Lock.h
+    LockAlgorithmInlines.h
     LockAlgorithm.h
     LockedPrintStream.h
     Locker.h
index 1d295f6..ba869e9 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 25a37a4..4514854 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 25a283e..161e7a3 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 e5e557c..39a9f3a 100644 (file)
@@ -30,6 +30,7 @@
 #define RunLoopTimer_h
 
 #include <wtf/SchedulePair.h>
+#include <wtf/Seconds.h>
 #include <wtf/RetainPtr.h>
 
 namespace WTF {
index d49ccfb..4e4bfb9 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 3ab27c4..59245dd 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 55db3d6..249ca85 100644 (file)
@@ -533,6 +533,11 @@ void ThreadCondition::broadcast()
     ASSERT_UNUSED(result, !result);
 }
 
+void Thread::yield()
+{
+    sched_yield();
+}
+
 } // namespace WTF
 
 #endif // USE(PTHREADS)
index f2304e6..7d33936 100644 (file)
@@ -522,6 +522,11 @@ int waitForThreadCompletion(ThreadIdentifier threadID)
 
 }
 
+void Thread::yield()
+{
+    SwitchToThread();
+}
+
 } // namespace WTF
 
 #endif // OS(WINDOWS)
index 774fec3..9e8fb9b 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 9709df4..70c4ed8 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 1c3d15b..9bbf568 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 ddf8d05..dd9de60 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 9a9a414..0bf3245 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 1cff6b7..9385573 100644 (file)
@@ -33,6 +33,7 @@
 
 #include "MessagePortChannel.h"
 #include <runtime/RuntimeFlags.h>
+#include <wtf/MonotonicTime.h>
 
 namespace WebCore {
 
index 8fd3cd6..c90008b 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 18e8f87..b2d360b 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 e1ed6b9..238f635 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 0ee9959..43319c7 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 ea25b1b..1e2e1c3 100644 (file)
@@ -47,7 +47,7 @@ void StaticMutex::lockSlowCase()
 
     // Avoid spinning pathologically.
     while (!try_lock())
-        std::this_thread::yield();
+        sched_yield();
 }
 
 } // namespace bmalloc