ThreadTimers should not store a raw pointer in its heap
authorrniwa@webkit.org <rniwa@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 10 Jan 2019 02:27:45 +0000 (02:27 +0000)
committerrniwa@webkit.org <rniwa@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Thu, 10 Jan 2019 02:27:45 +0000 (02:27 +0000)
https://bugs.webkit.org/show_bug.cgi?id=192975
<rdar://problem/46893946>

Reviewed by Geoffrey Garen.

Right now, ThreadTimers's heap data structure stores a raw pointer to TimerBase. In order to harden the timer code,
this patch replaces it with ThreadTimerHeapItem, a newly introduced struct, which effectively acks like
WeakReference<TimerBase*> as the timer heap and TimerBase both store RefPtr to it, and TimerBase's destructor clears
the raw pointer back to TimerBase*.

This approach was taken instead of an out-right adoptation of WeakPtr since the heap data structure requires each node
in the heap to have a fixed "priority" yet WeakPtr with no valid pointer back to TimerBase would effectively lose its
"priority" thereby corrupting the heap data structure. That is, each item in the heap must remember its fire time and
insertion order even when the underlying TimerBase had gone away (this should never happen but the whole point of this
hardening is to make it work even in the precense of such a bug).

This patch also moves the heap index in TimerBase to ThreadTimerHeapItem, and replaces the pointer to the heap vector
in TimerBase by a reference to ThreadTimers in ThreadTimerHeapItem. Note that ThreadTimers is a per-thread singleton.

The correctness of this hardening was tested by commenting out the call to stop() and !isInHeap() assertion in
TimerBase::~TimerBase() as well as the !isInHeap() assertion in ThreadTimerHeapItem::clearTimer() and observing that
layout tests run successfully without hitting any debug assertions.

No new tests since there should be no observable behavior difference.

* WebCore.xcodeproj/project.pbxproj: Export ThreadTimers.h as a private header since it's now included in Timer.h
* platform/ThreadTimers.cpp:
(WebCore::ThreadTimers::updateSharedTimer): Delete ThreadTimerHeapItem's with nullptr TimerBase* (TimerBase had
already been deleted). This should only happen when TimerBase's destructor failed to remove itself from the timer heap,
which should never happen.
(WebCore::ThreadTimers::sharedTimerFiredInternal): Ditto. Also removed the redundant code which had removed the timer
from the heap since setNextFireTime does the removal already.
* platform/ThreadTimers.h: Outdented the whole file.
(WebCore::ThreadTimers::timerHeap): We use Vector<RefPtr<ThreadTimerHeapItem>> instead of Vector<Ref<~>> since Ref<~>
doesn't have a copy constructor which is used by std::push_heap.
(WebCore::ThreadTimerHeapItem): Added.
(WebCore::ThreadTimerHeapItem::hasTimer const): Added.
(WebCore::ThreadTimerHeapItem::setNotInHeap): Added. ThreadTimerHeapItem uses unsigned -1 as the single value which
signifies the item not being in the heap instead of all negative values as in the old code in TimerBase.
(WebCore::ThreadTimerHeapItem::isInHeap const): Added.
(WebCore::ThreadTimerHeapItem::isFirstInHeap const): Added.
(WebCore::ThreadTimerHeapItem::timer): Added.
(WebCore::ThreadTimerHeapItem::clearTimer): Added.
(WebCore::ThreadTimerHeapItem::heapIndex const): Added.
(WebCore::ThreadTimerHeapItem::setHeapIndex): Added.
(WebCore::ThreadTimerHeapItem::timerHeap const): Added.
* platform/Timer.cpp:
(WebCore::threadGlobalTimerHeap): This function is now only used in assertions.
(WebCore::ThreadTimerHeapItem::ThreadTimerHeapItem): Added.
(WebCore::ThreadTimerHeapItem::create): Added.
(WebCore::TimerHeapPointer::TimerHeapPointer):
(WebCore::TimerHeapPointer::operator-> const):
(WebCore::TimerHeapReference::TimerHeapReference): Added a copy constructor.
(WebCore::TimerHeapReference::copyRef const): Added.
(WebCore::TimerHeapReference::operator RefPtr<ThreadTimerHeapItem>& const):
(WebCore::TimerHeapPointer::operator* const):
(WebCore::TimerHeapReference::operator=): Use move assignment operator.
(WebCore::TimerHeapReference::swapWith):
(WebCore::TimerHeapReference::updateHeapIndex): Extracted to share code between two verions of operator=.
(WebCore::swap):
(WebCore::TimerHeapIterator::TimerHeapIterator):
(WebCore::TimerHeapIterator::operator-> const):
(WebCore::TimerHeapLessThanFunction::compare): Added variants which take RefPtr<ThreadTimerHeapItem>.
(WebCore::TimerHeapLessThanFunction::operator() const):
(WebCore::TimerBase::TimerBase):
(WebCore::TimerBase::~TimerBase):Clear the raw pointer in ThreadTimerHeapItem.
(WebCore::TimerBase::stop):
(WebCore::TimerBase::nextFireInterval const):
(WebCore::TimerBase::checkHeapIndex const): Added the consistency check for other items in the heap.
(WebCore::TimerBase::checkConsistency const):
(WebCore::TimerBase::heapDecreaseKey):
(WebCore::TimerBase::heapDelete):
(WebCore::TimerBase::heapDeleteMin):
(WebCore::TimerBase::heapIncreaseKey):
(WebCore::TimerBase::heapInsert):
(WebCore::TimerBase::heapPop):
(WebCore::TimerBase::heapPopMin):
(WebCore::TimerBase::heapDeleteNullMin): Added. Used to delete ThreadTimerHeapItem which no longer has a valid TimerBase.
(WebCore::parentHeapPropertyHolds):
(WebCore::childHeapPropertyHolds):
(WebCore::TimerBase::hasValidHeapPosition const):
(WebCore::TimerBase::updateHeapIfNeeded): Tweaked the heap index assertion as heapIndex() itself would assert when called
on an item with an invalid (-1) heap index.
(WebCore::TimerBase::setNextFireTime): Create ThreadTimerHeapItem. Note m_heapItem is never cleared until this TimerBase
is deleted.
(WebCore::TimerHeapReference::operator TimerBase* const): Deleted.
* platform/Timer.h:
(WebCore::TimerBase): Replaced m_nextFireTime, m_heapIndex, m_heapInsertionOrder, and m_cachedThreadGlobalTimerHeap
by m_heapItem, RefPtr to an ThreadTimerHeapItem.
(WebCore::TimerBase::augmentFireInterval):
(WebCore::TimerBase::inHeap const):
(WebCore::TimerBase::nextFireTime const):
(WebCore::TimerBase::isActive const):
(WebCore::TimerBase:: const): Deleted.

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

Source/WebCore/ChangeLog
Source/WebCore/WebCore.xcodeproj/project.pbxproj
Source/WebCore/platform/ThreadTimers.cpp
Source/WebCore/platform/ThreadTimers.h
Source/WebCore/platform/Timer.cpp
Source/WebCore/platform/Timer.h

index 91dffd1..becfba6 100644 (file)
@@ -1,3 +1,101 @@
+2019-01-09  Ryosuke Niwa  <rniwa@webkit.org>
+
+        ThreadTimers should not store a raw pointer in its heap
+        https://bugs.webkit.org/show_bug.cgi?id=192975
+        <rdar://problem/46893946>
+
+        Reviewed by Geoffrey Garen.
+
+        Right now, ThreadTimers's heap data structure stores a raw pointer to TimerBase. In order to harden the timer code,
+        this patch replaces it with ThreadTimerHeapItem, a newly introduced struct, which effectively acks like
+        WeakReference<TimerBase*> as the timer heap and TimerBase both store RefPtr to it, and TimerBase's destructor clears
+        the raw pointer back to TimerBase*.
+
+        This approach was taken instead of an out-right adoptation of WeakPtr since the heap data structure requires each node
+        in the heap to have a fixed "priority" yet WeakPtr with no valid pointer back to TimerBase would effectively lose its
+        "priority" thereby corrupting the heap data structure. That is, each item in the heap must remember its fire time and
+        insertion order even when the underlying TimerBase had gone away (this should never happen but the whole point of this
+        hardening is to make it work even in the precense of such a bug).
+
+        This patch also moves the heap index in TimerBase to ThreadTimerHeapItem, and replaces the pointer to the heap vector
+        in TimerBase by a reference to ThreadTimers in ThreadTimerHeapItem. Note that ThreadTimers is a per-thread singleton.
+
+        The correctness of this hardening was tested by commenting out the call to stop() and !isInHeap() assertion in
+        TimerBase::~TimerBase() as well as the !isInHeap() assertion in ThreadTimerHeapItem::clearTimer() and observing that
+        layout tests run successfully without hitting any debug assertions.
+
+        No new tests since there should be no observable behavior difference.
+
+        * WebCore.xcodeproj/project.pbxproj: Export ThreadTimers.h as a private header since it's now included in Timer.h
+        * platform/ThreadTimers.cpp:
+        (WebCore::ThreadTimers::updateSharedTimer): Delete ThreadTimerHeapItem's with nullptr TimerBase* (TimerBase had
+        already been deleted). This should only happen when TimerBase's destructor failed to remove itself from the timer heap,
+        which should never happen.
+        (WebCore::ThreadTimers::sharedTimerFiredInternal): Ditto. Also removed the redundant code which had removed the timer
+        from the heap since setNextFireTime does the removal already.
+        * platform/ThreadTimers.h: Outdented the whole file.
+        (WebCore::ThreadTimers::timerHeap): We use Vector<RefPtr<ThreadTimerHeapItem>> instead of Vector<Ref<~>> since Ref<~>
+        doesn't have a copy constructor which is used by std::push_heap.
+        (WebCore::ThreadTimerHeapItem): Added.
+        (WebCore::ThreadTimerHeapItem::hasTimer const): Added.
+        (WebCore::ThreadTimerHeapItem::setNotInHeap): Added. ThreadTimerHeapItem uses unsigned -1 as the single value which
+        signifies the item not being in the heap instead of all negative values as in the old code in TimerBase.
+        (WebCore::ThreadTimerHeapItem::isInHeap const): Added.
+        (WebCore::ThreadTimerHeapItem::isFirstInHeap const): Added.
+        (WebCore::ThreadTimerHeapItem::timer): Added.
+        (WebCore::ThreadTimerHeapItem::clearTimer): Added.
+        (WebCore::ThreadTimerHeapItem::heapIndex const): Added.
+        (WebCore::ThreadTimerHeapItem::setHeapIndex): Added.
+        (WebCore::ThreadTimerHeapItem::timerHeap const): Added.
+        * platform/Timer.cpp:
+        (WebCore::threadGlobalTimerHeap): This function is now only used in assertions.
+        (WebCore::ThreadTimerHeapItem::ThreadTimerHeapItem): Added.
+        (WebCore::ThreadTimerHeapItem::create): Added.
+        (WebCore::TimerHeapPointer::TimerHeapPointer):
+        (WebCore::TimerHeapPointer::operator-> const):
+        (WebCore::TimerHeapReference::TimerHeapReference): Added a copy constructor.
+        (WebCore::TimerHeapReference::copyRef const): Added.
+        (WebCore::TimerHeapReference::operator RefPtr<ThreadTimerHeapItem>& const):
+        (WebCore::TimerHeapPointer::operator* const):
+        (WebCore::TimerHeapReference::operator=): Use move assignment operator.
+        (WebCore::TimerHeapReference::swapWith):
+        (WebCore::TimerHeapReference::updateHeapIndex): Extracted to share code between two verions of operator=.
+        (WebCore::swap):
+        (WebCore::TimerHeapIterator::TimerHeapIterator):
+        (WebCore::TimerHeapIterator::operator-> const):
+        (WebCore::TimerHeapLessThanFunction::compare): Added variants which take RefPtr<ThreadTimerHeapItem>.
+        (WebCore::TimerHeapLessThanFunction::operator() const):
+        (WebCore::TimerBase::TimerBase):
+        (WebCore::TimerBase::~TimerBase):Clear the raw pointer in ThreadTimerHeapItem.
+        (WebCore::TimerBase::stop):
+        (WebCore::TimerBase::nextFireInterval const):
+        (WebCore::TimerBase::checkHeapIndex const): Added the consistency check for other items in the heap.
+        (WebCore::TimerBase::checkConsistency const):
+        (WebCore::TimerBase::heapDecreaseKey):
+        (WebCore::TimerBase::heapDelete):
+        (WebCore::TimerBase::heapDeleteMin):
+        (WebCore::TimerBase::heapIncreaseKey):
+        (WebCore::TimerBase::heapInsert):
+        (WebCore::TimerBase::heapPop):
+        (WebCore::TimerBase::heapPopMin):
+        (WebCore::TimerBase::heapDeleteNullMin): Added. Used to delete ThreadTimerHeapItem which no longer has a valid TimerBase.
+        (WebCore::parentHeapPropertyHolds):
+        (WebCore::childHeapPropertyHolds):
+        (WebCore::TimerBase::hasValidHeapPosition const):
+        (WebCore::TimerBase::updateHeapIfNeeded): Tweaked the heap index assertion as heapIndex() itself would assert when called
+        on an item with an invalid (-1) heap index.
+        (WebCore::TimerBase::setNextFireTime): Create ThreadTimerHeapItem. Note m_heapItem is never cleared until this TimerBase
+        is deleted.
+        (WebCore::TimerHeapReference::operator TimerBase* const): Deleted.
+        * platform/Timer.h:
+        (WebCore::TimerBase): Replaced m_nextFireTime, m_heapIndex, m_heapInsertionOrder, and m_cachedThreadGlobalTimerHeap
+        by m_heapItem, RefPtr to an ThreadTimerHeapItem.
+        (WebCore::TimerBase::augmentFireInterval):
+        (WebCore::TimerBase::inHeap const):
+        (WebCore::TimerBase::nextFireTime const):
+        (WebCore::TimerBase::isActive const):
+        (WebCore::TimerBase:: const): Deleted.
+
 2019-01-09  Alex Christensen  <achristensen@webkit.org>
 
         REGRESSION(239737) iOS quicklook tests should not dereference null
 2019-01-09  Alex Christensen  <achristensen@webkit.org>
 
         REGRESSION(239737) iOS quicklook tests should not dereference null
index 3ec6678..ca59a63 100644 (file)
                159741DB1B7D140100201C92 /* JSMediaDeviceInfo.h in Headers */ = {isa = PBXBuildFile; fileRef = 157CC2621B7C1CA400D8D075 /* JSMediaDeviceInfo.h */; };
                15C7708D100D3C6B005BA267 /* ValidityState.h in Headers */ = {isa = PBXBuildFile; fileRef = 15C7708A100D3C6A005BA267 /* ValidityState.h */; settings = {ATTRIBUTES = (Private, ); }; };
                15C77093100D3CA8005BA267 /* JSValidityState.h in Headers */ = {isa = PBXBuildFile; fileRef = 15C77091100D3CA8005BA267 /* JSValidityState.h */; };
                159741DB1B7D140100201C92 /* JSMediaDeviceInfo.h in Headers */ = {isa = PBXBuildFile; fileRef = 157CC2621B7C1CA400D8D075 /* JSMediaDeviceInfo.h */; };
                15C7708D100D3C6B005BA267 /* ValidityState.h in Headers */ = {isa = PBXBuildFile; fileRef = 15C7708A100D3C6A005BA267 /* ValidityState.h */; settings = {ATTRIBUTES = (Private, ); }; };
                15C77093100D3CA8005BA267 /* JSValidityState.h in Headers */ = {isa = PBXBuildFile; fileRef = 15C77091100D3CA8005BA267 /* JSValidityState.h */; };
-               185BCF290F3279CE000EA262 /* ThreadTimers.h in Headers */ = {isa = PBXBuildFile; fileRef = 185BCF270F3279CE000EA262 /* ThreadTimers.h */; };
+               185BCF290F3279CE000EA262 /* ThreadTimers.h in Headers */ = {isa = PBXBuildFile; fileRef = 185BCF270F3279CE000EA262 /* ThreadTimers.h */; settings = {ATTRIBUTES = (Private, ); }; };
                188604B40F2E654A000B6443 /* DOMTimer.h in Headers */ = {isa = PBXBuildFile; fileRef = 188604B20F2E654A000B6443 /* DOMTimer.h */; settings = {ATTRIBUTES = (Private, ); }; };
                18F831B80FD48C7800D8C56B /* WorkerLoaderProxy.h in Headers */ = {isa = PBXBuildFile; fileRef = 18F831B70FD48C7800D8C56B /* WorkerLoaderProxy.h */; settings = {ATTRIBUTES = (Private, ); }; };
                1921327511C0E6BB00456238 /* SVGFEConvolveMatrixElement.h in Headers */ = {isa = PBXBuildFile; fileRef = 1921327211C0E6BB00456238 /* SVGFEConvolveMatrixElement.h */; };
                188604B40F2E654A000B6443 /* DOMTimer.h in Headers */ = {isa = PBXBuildFile; fileRef = 188604B20F2E654A000B6443 /* DOMTimer.h */; settings = {ATTRIBUTES = (Private, ); }; };
                18F831B80FD48C7800D8C56B /* WorkerLoaderProxy.h in Headers */ = {isa = PBXBuildFile; fileRef = 18F831B70FD48C7800D8C56B /* WorkerLoaderProxy.h */; settings = {ATTRIBUTES = (Private, ); }; };
                1921327511C0E6BB00456238 /* SVGFEConvolveMatrixElement.h in Headers */ = {isa = PBXBuildFile; fileRef = 1921327211C0E6BB00456238 /* SVGFEConvolveMatrixElement.h */; };
index ac850f2..c4c79e3 100644 (file)
@@ -75,12 +75,18 @@ void ThreadTimers::updateSharedTimer()
 {
     if (!m_sharedTimer)
         return;
 {
     if (!m_sharedTimer)
         return;
-        
+
+    while (!m_timerHeap.isEmpty() && !m_timerHeap.first()->hasTimer()) {
+        ASSERT_NOT_REACHED();
+        TimerBase::heapDeleteNullMin(m_timerHeap);
+    }
+    ASSERT(m_timerHeap.isEmpty() || m_timerHeap.first()->hasTimer());
+
     if (m_firingTimers || m_timerHeap.isEmpty()) {
         m_pendingSharedTimerFireTime = MonotonicTime { };
         m_sharedTimer->stop();
     } else {
     if (m_firingTimers || m_timerHeap.isEmpty()) {
         m_pendingSharedTimerFireTime = MonotonicTime { };
         m_sharedTimer->stop();
     } else {
-        MonotonicTime nextFireTime = m_timerHeap.first()->m_nextFireTime;
+        MonotonicTime nextFireTime = m_timerHeap.first()->time;
         MonotonicTime currentMonotonicTime = MonotonicTime::now();
         if (m_pendingSharedTimerFireTime) {
             // No need to restart the timer if both the pending fire time and the new fire time are in the past.
         MonotonicTime currentMonotonicTime = MonotonicTime::now();
         if (m_pendingSharedTimerFireTime) {
             // No need to restart the timer if both the pending fire time and the new fire time are in the past.
@@ -104,17 +110,23 @@ void ThreadTimers::sharedTimerFiredInternal()
     MonotonicTime fireTime = MonotonicTime::now();
     MonotonicTime timeToQuit = fireTime + maxDurationOfFiringTimers;
 
     MonotonicTime fireTime = MonotonicTime::now();
     MonotonicTime timeToQuit = fireTime + maxDurationOfFiringTimers;
 
-    while (!m_timerHeap.isEmpty() && m_timerHeap.first()->m_nextFireTime <= fireTime) {
-        TimerBase* timer = m_timerHeap.first();
-        timer->m_nextFireTime = MonotonicTime { };
-        timer->m_unalignedNextFireTime = MonotonicTime { };
-        timer->heapDeleteMin();
+    while (!m_timerHeap.isEmpty()) {
+        Ref<ThreadTimerHeapItem> item = *m_timerHeap.first();
+        ASSERT(item->hasTimer());
+        if (!item->hasTimer()) {
+            TimerBase::heapDeleteNullMin(m_timerHeap);
+            continue;
+        }
+
+        if (item->time > fireTime)
+            break;
 
 
-        Seconds interval = timer->repeatInterval();
-        timer->setNextFireTime(interval ? fireTime + interval : MonotonicTime { });
+        auto& timer = item->timer();
+        Seconds interval = timer.repeatInterval();
+        timer.setNextFireTime(interval ? fireTime + interval : MonotonicTime { });
 
         // Once the timer has been fired, it may be deleted, so do nothing else with it after this point.
 
         // Once the timer has been fired, it may be deleted, so do nothing else with it after this point.
-        timer->fired();
+        item->timer().fired();
 
         // Catch the case where the timer asked timers to fire in a nested event loop, or we are over time limit.
         if (!m_firingTimers || timeToQuit < MonotonicTime::now())
 
         // Catch the case where the timer asked timers to fire in a nested event loop, or we are over time limit.
         if (!m_firingTimers || timeToQuit < MonotonicTime::now())
index 0d1d893..7a11138 100644 (file)
 
 #include <wtf/MonotonicTime.h>
 #include <wtf/Noncopyable.h>
 
 #include <wtf/MonotonicTime.h>
 #include <wtf/Noncopyable.h>
+#include <wtf/RefCounted.h>
+#include <wtf/ThreadSafeRefCounted.h>
 #include <wtf/Vector.h>
 
 namespace WebCore {
 
 #include <wtf/Vector.h>
 
 namespace WebCore {
 
-    class SharedTimer;
-    class TimerBase;
+class SharedTimer;
+class ThreadTimers;
+class TimerBase;
 
 
-    // A collection of timers per thread. Kept in ThreadGlobalData.
-    class ThreadTimers {
-        WTF_MAKE_NONCOPYABLE(ThreadTimers); WTF_MAKE_FAST_ALLOCATED;
-    public:
-        ThreadTimers();
+struct ThreadTimerHeapItem;
+typedef Vector<RefPtr<ThreadTimerHeapItem>> ThreadTimerHeap;
+    
+// A collection of timers per thread. Kept in ThreadGlobalData.
+class ThreadTimers {
+    WTF_MAKE_NONCOPYABLE(ThreadTimers); WTF_MAKE_FAST_ALLOCATED;
+public:
+    ThreadTimers();
 
 
-        // On a thread different then main, we should set the thread's instance of the SharedTimer.
-        void setSharedTimer(SharedTimer*);
+    // On a thread different then main, we should set the thread's instance of the SharedTimer.
+    void setSharedTimer(SharedTimer*);
 
 
-        Vector<TimerBase*>& timerHeap() { return m_timerHeap; }
+    ThreadTimerHeap& timerHeap() { return m_timerHeap; }
 
 
-        void updateSharedTimer();
-        void fireTimersInNestedEventLoop();
+    void updateSharedTimer();
+    void fireTimersInNestedEventLoop();
 
 
-    private:
-        void sharedTimerFiredInternal();
-        void fireTimersInNestedEventLoopInternal();
+private:
+    void sharedTimerFiredInternal();
+    void fireTimersInNestedEventLoopInternal();
 
 
-        Vector<TimerBase*> m_timerHeap;
-        SharedTimer* m_sharedTimer { nullptr }; // External object, can be a run loop on a worker thread. Normally set/reset by worker thread.
-        bool m_firingTimers { false }; // Reentrancy guard.
-        MonotonicTime m_pendingSharedTimerFireTime;
-    };
+    ThreadTimerHeap m_timerHeap;
+    SharedTimer* m_sharedTimer { nullptr }; // External object, can be a run loop on a worker thread. Normally set/reset by worker thread.
+    bool m_firingTimers { false }; // Reentrancy guard.
+    MonotonicTime m_pendingSharedTimerFireTime;
+};
+
+struct ThreadTimerHeapItem : ThreadSafeRefCounted<ThreadTimerHeapItem> {
+    static RefPtr<ThreadTimerHeapItem> create(TimerBase&, MonotonicTime, unsigned);
+
+    bool hasTimer() const { return m_timer; }
+    TimerBase& timer();
+    void clearTimer();
+
+    ThreadTimerHeap& timerHeap() const;
+
+    unsigned heapIndex() const;
+    void setHeapIndex(unsigned newIndex);
+    void setNotInHeap() { m_heapIndex = invalidHeapIndex; }
+
+    bool isInHeap() const { return m_heapIndex != invalidHeapIndex; }
+    bool isFirstInHeap() const { return !m_heapIndex; }
+
+    MonotonicTime time;
+    unsigned insertionOrder { 0 };
+
+private:
+    ThreadTimers& m_threadTimers;
+    TimerBase* m_timer { nullptr };
+    unsigned m_heapIndex { invalidHeapIndex };
+
+    static const unsigned invalidHeapIndex = static_cast<unsigned>(-1);
+
+    ThreadTimerHeapItem(TimerBase&, MonotonicTime, unsigned);
+};
+
+inline TimerBase& ThreadTimerHeapItem::timer()
+{
+    ASSERT(m_timer);
+    return *m_timer;
+}
+
+inline void ThreadTimerHeapItem::clearTimer()
+{
+    ASSERT(!isInHeap());
+    m_timer = nullptr;
+}
+
+inline unsigned ThreadTimerHeapItem::heapIndex() const
+{
+    ASSERT(m_heapIndex != invalidHeapIndex);
+    return static_cast<unsigned>(m_heapIndex);
+}
+
+inline void ThreadTimerHeapItem::setHeapIndex(unsigned newIndex)
+{
+    ASSERT(newIndex != invalidHeapIndex);
+    m_heapIndex = newIndex;
+}
+
+inline ThreadTimerHeap& ThreadTimerHeapItem::timerHeap() const
+{
+    return m_threadTimers.timerHeap();
+}
 
 }
 
 
 }
 
index 38a03d0..fd82402 100644 (file)
@@ -50,69 +50,111 @@ class TimerHeapReference;
 // Then we set a single shared system timer to fire at that time.
 //
 // When a timer's "next fire time" changes, we need to move it around in the priority queue.
 // Then we set a single shared system timer to fire at that time.
 //
 // When a timer's "next fire time" changes, we need to move it around in the priority queue.
-static Vector<TimerBase*>& threadGlobalTimerHeap()
+#if !ASSERT_DISABLED
+static ThreadTimerHeap& threadGlobalTimerHeap()
 {
     return threadGlobalData().threadTimers().timerHeap();
 }
 {
     return threadGlobalData().threadTimers().timerHeap();
 }
+#endif
+
+inline ThreadTimerHeapItem::ThreadTimerHeapItem(TimerBase& timer, MonotonicTime time, unsigned insertionOrder)
+    : time(time)
+    , insertionOrder(insertionOrder)
+    , m_threadTimers(threadGlobalData().threadTimers())
+    , m_timer(&timer)
+{
+    ASSERT(m_timer);
+}
+    
+inline RefPtr<ThreadTimerHeapItem> ThreadTimerHeapItem::create(TimerBase& timer, MonotonicTime time, unsigned insertionOrder)
+{
+    return adoptRef(*new ThreadTimerHeapItem { timer, time, insertionOrder });
+}
+
 // ----------------
 
 class TimerHeapPointer {
 public:
 // ----------------
 
 class TimerHeapPointer {
 public:
-    TimerHeapPointer(TimerBase** pointer) : m_pointer(pointer) { }
+    TimerHeapPointer(RefPtr<ThreadTimerHeapItem>* pointer)
+        : m_pointer(pointer)
+    { }
+
     TimerHeapReference operator*() const;
     TimerHeapReference operator*() const;
-    TimerBase* operator->() const { return *m_pointer; }
+    RefPtr<ThreadTimerHeapItem>& operator->() const { return *m_pointer; }
 private:
 private:
-    TimerBase** m_pointer;
+    RefPtr<ThreadTimerHeapItem>* m_pointer;
 };
 
 class TimerHeapReference {
 public:
 };
 
 class TimerHeapReference {
 public:
-    TimerHeapReference(TimerBase*& reference) : m_reference(reference) { }
-    operator TimerBase*() const { return m_reference; }
+    TimerHeapReference(RefPtr<ThreadTimerHeapItem>& reference)
+        : m_reference(reference)
+    { }
+
+    TimerHeapReference(const TimerHeapReference& other)
+        : m_reference(other.m_reference)
+    { }
+
+    operator RefPtr<ThreadTimerHeapItem>&() const { return m_reference; }
     TimerHeapPointer operator&() const { return &m_reference; }
     TimerHeapPointer operator&() const { return &m_reference; }
-    TimerHeapReference& operator=(TimerBase*);
-    TimerHeapReference& operator=(TimerHeapReference);
+    TimerHeapReference& operator=(TimerHeapReference&&);
+    TimerHeapReference& operator=(RefPtr<ThreadTimerHeapItem>&&);
+
+    void swap(TimerHeapReference& other);
+
+    void updateHeapIndex();
+
 private:
 private:
-    TimerBase*& m_reference;
+    RefPtr<ThreadTimerHeapItem>& m_reference;
+
+    friend void swap(TimerHeapReference a, TimerHeapReference b);
 };
 
 inline TimerHeapReference TimerHeapPointer::operator*() const
 {
 };
 
 inline TimerHeapReference TimerHeapPointer::operator*() const
 {
-    return *m_pointer;
+    return TimerHeapReference { *m_pointer };
 }
 
 }
 
-inline TimerHeapReference& TimerHeapReference::operator=(TimerBase* timer)
+inline TimerHeapReference& TimerHeapReference::operator=(TimerHeapReference&& other)
 {
 {
-    m_reference = timer;
-    Vector<TimerBase*>& heap = timer->timerHeap();
-    if (&m_reference >= heap.data() && &m_reference < heap.data() + heap.size())
-        timer->m_heapIndex = &m_reference - heap.data();
+    m_reference = WTFMove(other.m_reference);
+    updateHeapIndex();
     return *this;
 }
 
     return *this;
 }
 
-inline TimerHeapReference& TimerHeapReference::operator=(TimerHeapReference b)
+inline TimerHeapReference& TimerHeapReference::operator=(RefPtr<ThreadTimerHeapItem>&& item)
 {
 {
-    TimerBase* timer = b;
-    return *this = timer;
+    m_reference = WTFMove(item);
+    updateHeapIndex();
+    return *this;
 }
 
 }
 
-inline void swap(TimerHeapReference a, TimerHeapReference b)
+inline void TimerHeapReference::swap(TimerHeapReference& other)
 {
 {
-    TimerBase* timerA = a;
-    TimerBase* timerB = b;
+    m_reference.swap(other.m_reference);
+    updateHeapIndex();
+    other.updateHeapIndex();
+}
 
 
-    // Invoke the assignment operator, since that takes care of updating m_heapIndex.
-    a = timerB;
-    b = timerA;
+inline void TimerHeapReference::updateHeapIndex()
+{
+    auto& heap = m_reference->timerHeap();
+    if (&m_reference >= heap.data() && &m_reference < heap.data() + heap.size())
+        m_reference->setHeapIndex(&m_reference - heap.data());
+}
+
+inline void swap(TimerHeapReference a, TimerHeapReference b)
+{
+    a.swap(b);
 }
 
 // ----------------
 
 // Class to represent iterators in the heap when calling the standard library heap algorithms.
 // Uses a custom pointer and reference type that update indices for pointers in the heap.
 }
 
 // ----------------
 
 // Class to represent iterators in the heap when calling the standard library heap algorithms.
 // Uses a custom pointer and reference type that update indices for pointers in the heap.
-class TimerHeapIterator : public std::iterator<std::random_access_iterator_tag, TimerBase*, ptrdiff_t, TimerHeapPointer, TimerHeapReference> {
+class TimerHeapIterator : public std::iterator<std::random_access_iterator_tag, RefPtr<ThreadTimerHeapItem>, ptrdiff_t, TimerHeapPointer, TimerHeapReference> {
 public:
 public:
-    explicit TimerHeapIterator(TimerBase** pointer) : m_pointer(pointer) { checkConsistency(); }
+    explicit TimerHeapIterator(RefPtr<ThreadTimerHeapItem>* pointer) : m_pointer(pointer) { checkConsistency(); }
 
     TimerHeapIterator& operator++() { checkConsistency(); ++m_pointer; checkConsistency(); return *this; }
     TimerHeapIterator operator++(int) { checkConsistency(1); return TimerHeapIterator(m_pointer++); }
 
     TimerHeapIterator& operator++() { checkConsistency(); ++m_pointer; checkConsistency(); return *this; }
     TimerHeapIterator operator++(int) { checkConsistency(1); return TimerHeapIterator(m_pointer++); }
@@ -125,7 +167,7 @@ public:
 
     TimerHeapReference operator*() const { return TimerHeapReference(*m_pointer); }
     TimerHeapReference operator[](ptrdiff_t i) const { return TimerHeapReference(m_pointer[i]); }
 
     TimerHeapReference operator*() const { return TimerHeapReference(*m_pointer); }
     TimerHeapReference operator[](ptrdiff_t i) const { return TimerHeapReference(m_pointer[i]); }
-    TimerBase* operator->() const { return *m_pointer; }
+    RefPtr<ThreadTimerHeapItem>& operator->() const { return *m_pointer; }
 
 private:
     void checkConsistency(ptrdiff_t offset = 0) const
 
 private:
     void checkConsistency(ptrdiff_t offset = 0) const
@@ -149,7 +191,7 @@ private:
     friend TimerHeapIterator operator-(TimerHeapIterator, size_t);
     friend ptrdiff_t operator-(TimerHeapIterator, TimerHeapIterator);
 
     friend TimerHeapIterator operator-(TimerHeapIterator, size_t);
     friend ptrdiff_t operator-(TimerHeapIterator, TimerHeapIterator);
 
-    TimerBase** m_pointer;
+    RefPtr<ThreadTimerHeapItem>* m_pointer;
 };
 
 inline bool operator==(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer == b.m_pointer; }
 };
 
 inline bool operator==(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer == b.m_pointer; }
@@ -169,23 +211,34 @@ inline ptrdiff_t operator-(TimerHeapIterator a, TimerHeapIterator b) { return a.
 
 class TimerHeapLessThanFunction {
 public:
 
 class TimerHeapLessThanFunction {
 public:
-    bool operator()(const TimerBase*, const TimerBase*) const;
-};
+    static bool compare(const TimerBase& a, const RefPtr<ThreadTimerHeapItem>& b)
+    {
+        return compare(a.m_heapItem->time, a.m_heapItem->insertionOrder, b->time, b->insertionOrder);
+    }
 
 
-inline bool TimerHeapLessThanFunction::operator()(const TimerBase* a, const TimerBase* b) const
-{
-    // The comparisons below are "backwards" because the heap puts the largest 
-    // element first and we want the lowest time to be the first one in the heap.
-    MonotonicTime aFireTime = a->m_nextFireTime;
-    MonotonicTime bFireTime = b->m_nextFireTime;
-    if (bFireTime != aFireTime)
-        return bFireTime < aFireTime;
-    
-    // We need to look at the difference of the insertion orders instead of comparing the two 
-    // outright in case of overflow. 
-    unsigned difference = a->m_heapInsertionOrder - b->m_heapInsertionOrder;
-    return difference < std::numeric_limits<unsigned>::max() / 2;
-}
+    static bool compare(const RefPtr<ThreadTimerHeapItem>& a, const TimerBase& b)
+    {
+        return compare(a->time, a->insertionOrder, b.m_heapItem->time, b.m_heapItem->insertionOrder);
+    }
+
+    bool operator()(const RefPtr<ThreadTimerHeapItem>& a, const RefPtr<ThreadTimerHeapItem>& b) const
+    {
+        return compare(a->time, a->insertionOrder, b->time, b->insertionOrder);
+    }
+
+private:
+    static bool compare(MonotonicTime aTime, unsigned aOrder, MonotonicTime bTime, unsigned bOrder)
+    {
+        // The comparisons below are "backwards" because the heap puts the largest
+        // element first and we want the lowest time to be the first one in the heap.
+        if (bTime != aTime)
+            return bTime < aTime;
+        // We need to look at the difference of the insertion orders instead of comparing the two
+        // outright in case of overflow.
+        unsigned difference = aOrder - bOrder;
+        return difference < std::numeric_limits<unsigned>::max() / 2;
+    }
+};
 
 // ----------------
 
 
 // ----------------
 
@@ -201,8 +254,7 @@ static bool shouldSuppressThreadSafetyCheck()
 }
 
 TimerBase::TimerBase()
 }
 
 TimerBase::TimerBase()
-    : m_heapIndex(-1)
-    , m_wasDeleted(false)
+    : m_wasDeleted(false)
 {
 }
 
 {
 }
 
@@ -212,6 +264,10 @@ TimerBase::~TimerBase()
     RELEASE_ASSERT(canAccessThreadLocalDataForThread(m_thread.get()) || shouldSuppressThreadSafetyCheck());
     stop();
     ASSERT(!inHeap());
     RELEASE_ASSERT(canAccessThreadLocalDataForThread(m_thread.get()) || shouldSuppressThreadSafetyCheck());
     stop();
     ASSERT(!inHeap());
+    if (m_heapItem) {
+        m_heapItem->clearTimer();
+        m_heapItem = nullptr;
+    }
     m_wasDeleted = true;
 }
 
     m_wasDeleted = true;
 }
 
@@ -230,7 +286,7 @@ void TimerBase::stop()
     m_repeatInterval = 0_s;
     setNextFireTime(MonotonicTime { });
 
     m_repeatInterval = 0_s;
     setNextFireTime(MonotonicTime { });
 
-    ASSERT(!static_cast<bool>(m_nextFireTime));
+    ASSERT(!static_cast<bool>(nextFireTime()));
     ASSERT(m_repeatInterval == 0_s);
     ASSERT(!inHeap());
 }
     ASSERT(m_repeatInterval == 0_s);
     ASSERT(!inHeap());
 }
@@ -238,57 +294,66 @@ void TimerBase::stop()
 Seconds TimerBase::nextFireInterval() const
 {
     ASSERT(isActive());
 Seconds TimerBase::nextFireInterval() const
 {
     ASSERT(isActive());
+    ASSERT(m_heapItem);
     MonotonicTime current = MonotonicTime::now();
     MonotonicTime current = MonotonicTime::now();
-    if (m_nextFireTime < current)
+    auto fireTime = nextFireTime();
+    if (fireTime < current)
         return 0_s;
         return 0_s;
-    return m_nextFireTime - current;
+    return fireTime - current;
 }
 
 inline void TimerBase::checkHeapIndex() const
 {
 }
 
 inline void TimerBase::checkHeapIndex() const
 {
-    ASSERT(timerHeap() == threadGlobalTimerHeap());
-    ASSERT(!timerHeap().isEmpty());
-    ASSERT(m_heapIndex >= 0);
-    ASSERT(m_heapIndex < static_cast<int>(timerHeap().size()));
-    ASSERT(timerHeap()[m_heapIndex] == this);
+#if !ASSERT_DISABLED
+    ASSERT(m_heapItem);
+    auto& heap = m_heapItem->timerHeap();
+    ASSERT(&heap == &threadGlobalTimerHeap());
+    ASSERT(!heap.isEmpty());
+    ASSERT(m_heapItem->isInHeap());
+    ASSERT(m_heapItem->heapIndex() < m_heapItem->timerHeap().size());
+    ASSERT(heap[m_heapItem->heapIndex()] == m_heapItem);
+    for (unsigned i = 0, size = heap.size(); i < size; i++)
+        ASSERT(heap[i]->heapIndex() == i);
+#endif
 }
 
 inline void TimerBase::checkConsistency() const
 {
     // Timers should be in the heap if and only if they have a non-zero next fire time.
 }
 
 inline void TimerBase::checkConsistency() const
 {
     // Timers should be in the heap if and only if they have a non-zero next fire time.
-    ASSERT(inHeap() == static_cast<bool>(m_nextFireTime));
+    ASSERT(inHeap() == static_cast<bool>(nextFireTime()));
     if (inHeap())
         checkHeapIndex();
 }
 
 void TimerBase::heapDecreaseKey()
 {
     if (inHeap())
         checkHeapIndex();
 }
 
 void TimerBase::heapDecreaseKey()
 {
-    ASSERT(static_cast<bool>(m_nextFireTime));
+    ASSERT(static_cast<bool>(nextFireTime()));
+    ASSERT(m_heapItem);
     checkHeapIndex();
     checkHeapIndex();
-    TimerBase** heapData = timerHeap().data();
-    push_heap(TimerHeapIterator(heapData), TimerHeapIterator(heapData + m_heapIndex + 1), TimerHeapLessThanFunction());
+    auto* heapData = m_heapItem->timerHeap().data();
+    push_heap(TimerHeapIterator(heapData), TimerHeapIterator(heapData + m_heapItem->heapIndex() + 1), TimerHeapLessThanFunction());
     checkHeapIndex();
 }
 
 inline void TimerBase::heapDelete()
 {
     checkHeapIndex();
 }
 
 inline void TimerBase::heapDelete()
 {
-    ASSERT(!static_cast<bool>(m_nextFireTime));
+    ASSERT(!static_cast<bool>(nextFireTime()));
     heapPop();
     heapPop();
-    timerHeap().removeLast();
-    m_heapIndex = -1;
+    m_heapItem->timerHeap().removeLast();
+    m_heapItem->setNotInHeap();
 }
 
 void TimerBase::heapDeleteMin()
 {
 }
 
 void TimerBase::heapDeleteMin()
 {
-    ASSERT(!static_cast<bool>(m_nextFireTime));
+    ASSERT(!static_cast<bool>(nextFireTime()));
     heapPopMin();
     heapPopMin();
-    timerHeap().removeLast();
-    m_heapIndex = -1;
+    m_heapItem->timerHeap().removeLast();
+    m_heapItem->setNotInHeap();
 }
 
 inline void TimerBase::heapIncreaseKey()
 {
 }
 
 inline void TimerBase::heapIncreaseKey()
 {
-    ASSERT(static_cast<bool>(m_nextFireTime));
+    ASSERT(static_cast<bool>(nextFireTime()));
     heapPop();
     heapDecreaseKey();
 }
     heapPop();
     heapDecreaseKey();
 }
@@ -296,81 +361,105 @@ inline void TimerBase::heapIncreaseKey()
 inline void TimerBase::heapInsert()
 {
     ASSERT(!inHeap());
 inline void TimerBase::heapInsert()
 {
     ASSERT(!inHeap());
-    timerHeap().append(this);
-    m_heapIndex = timerHeap().size() - 1;
+    ASSERT(m_heapItem);
+    auto& heap = m_heapItem->timerHeap();
+    heap.append(m_heapItem.copyRef());
+    m_heapItem->setHeapIndex(heap.size() - 1);
     heapDecreaseKey();
 }
 
 inline void TimerBase::heapPop()
 {
     heapDecreaseKey();
 }
 
 inline void TimerBase::heapPop()
 {
+    ASSERT(m_heapItem);
     // Temporarily force this timer to have the minimum key so we can pop it.
     // Temporarily force this timer to have the minimum key so we can pop it.
-    MonotonicTime fireTime = m_nextFireTime;
-    m_nextFireTime = -MonotonicTime::infinity();
+    MonotonicTime fireTime = m_heapItem->time;
+    m_heapItem->time = -MonotonicTime::infinity();
     heapDecreaseKey();
     heapPopMin();
     heapDecreaseKey();
     heapPopMin();
-    m_nextFireTime = fireTime;
+    m_heapItem->time = fireTime;
 }
 
 void TimerBase::heapPopMin()
 {
 }
 
 void TimerBase::heapPopMin()
 {
-    ASSERT(this == timerHeap().first());
+    ASSERT(m_heapItem == m_heapItem->timerHeap().first());
     checkHeapIndex();
     checkHeapIndex();
-    Vector<TimerBase*>& heap = timerHeap();
-    TimerBase** heapData = heap.data();
+    auto& heap = m_heapItem->timerHeap();
+    auto* heapData = heap.data();
     pop_heap(TimerHeapIterator(heapData), TimerHeapIterator(heapData + heap.size()), TimerHeapLessThanFunction());
     checkHeapIndex();
     pop_heap(TimerHeapIterator(heapData), TimerHeapIterator(heapData + heap.size()), TimerHeapLessThanFunction());
     checkHeapIndex();
-    ASSERT(this == timerHeap().last());
+    ASSERT(m_heapItem == m_heapItem->timerHeap().last());
 }
 
 }
 
-static inline bool parentHeapPropertyHolds(const TimerBase* current, const Vector<TimerBase*>& heap, unsigned currentIndex)
+void TimerBase::heapDeleteNullMin(ThreadTimerHeap& heap)
+{
+    RELEASE_ASSERT(!heap.first()->hasTimer());
+    heap.first()->time = -MonotonicTime::infinity();
+    auto* heapData = heap.data();
+    pop_heap(TimerHeapIterator(heapData), TimerHeapIterator(heapData + heap.size()), TimerHeapLessThanFunction());
+    heap.removeLast();
+}
+
+static inline bool parentHeapPropertyHolds(const TimerBase* current, const ThreadTimerHeap& heap, unsigned currentIndex)
 {
     if (!currentIndex)
         return true;
     unsigned parentIndex = (currentIndex - 1) / 2;
 {
     if (!currentIndex)
         return true;
     unsigned parentIndex = (currentIndex - 1) / 2;
-    TimerHeapLessThanFunction compareHeapPosition;
-    return compareHeapPosition(current, heap[parentIndex]);
+    return TimerHeapLessThanFunction::compare(*current, heap[parentIndex]);
 }
 
 }
 
-static inline bool childHeapPropertyHolds(const TimerBase* current, const Vector<TimerBase*>& heap, unsigned childIndex)
+static inline bool childHeapPropertyHolds(const TimerBase* current, const ThreadTimerHeap& heap, unsigned childIndex)
 {
     if (childIndex >= heap.size())
         return true;
 {
     if (childIndex >= heap.size())
         return true;
-    TimerHeapLessThanFunction compareHeapPosition;
-    return compareHeapPosition(heap[childIndex], current);
+    return TimerHeapLessThanFunction::compare(heap[childIndex], *current);
 }
 
 bool TimerBase::hasValidHeapPosition() const
 {
 }
 
 bool TimerBase::hasValidHeapPosition() const
 {
-    ASSERT(m_nextFireTime);
+    ASSERT(nextFireTime());
+    ASSERT(m_heapItem);
     if (!inHeap())
         return false;
     // Check if the heap property still holds with the new fire time. If it does we don't need to do anything.
     // This assumes that the STL heap is a standard binary heap. In an unlikely event it is not, the assertions
     // in updateHeapIfNeeded() will get hit.
     if (!inHeap())
         return false;
     // Check if the heap property still holds with the new fire time. If it does we don't need to do anything.
     // This assumes that the STL heap is a standard binary heap. In an unlikely event it is not, the assertions
     // in updateHeapIfNeeded() will get hit.
-    const Vector<TimerBase*>& heap = timerHeap();
-    if (!parentHeapPropertyHolds(this, heap, m_heapIndex))
+    const auto& heap = m_heapItem->timerHeap();
+    unsigned heapIndex = m_heapItem->heapIndex();
+    if (!parentHeapPropertyHolds(this, heap, heapIndex))
         return false;
         return false;
-    unsigned childIndex1 = 2 * m_heapIndex + 1;
+    unsigned childIndex1 = 2 * heapIndex + 1;
     unsigned childIndex2 = childIndex1 + 1;
     return childHeapPropertyHolds(this, heap, childIndex1) && childHeapPropertyHolds(this, heap, childIndex2);
 }
 
 void TimerBase::updateHeapIfNeeded(MonotonicTime oldTime)
 {
     unsigned childIndex2 = childIndex1 + 1;
     return childHeapPropertyHolds(this, heap, childIndex1) && childHeapPropertyHolds(this, heap, childIndex2);
 }
 
 void TimerBase::updateHeapIfNeeded(MonotonicTime oldTime)
 {
-    if (m_nextFireTime && hasValidHeapPosition())
+    auto fireTime = nextFireTime();
+    if (fireTime && hasValidHeapPosition())
         return;
         return;
-#ifndef NDEBUG
-    int oldHeapIndex = m_heapIndex;
+
+#if !ASSERT_DISABLED
+    Optional<unsigned> oldHeapIndex;
+    if (m_heapItem->isInHeap())
+        oldHeapIndex = m_heapItem->heapIndex();
 #endif
 #endif
+
     if (!oldTime)
         heapInsert();
     if (!oldTime)
         heapInsert();
-    else if (!m_nextFireTime)
+    else if (!fireTime)
         heapDelete();
         heapDelete();
-    else if (m_nextFireTime < oldTime)
+    else if (fireTime < oldTime)
         heapDecreaseKey();
     else
         heapIncreaseKey();
         heapDecreaseKey();
     else
         heapIncreaseKey();
-    ASSERT(m_heapIndex != oldHeapIndex);
+
+#if !ASSERT_DISABLED
+    Optional<unsigned> newHeapIndex;
+    if (m_heapItem->isInHeap())
+        newHeapIndex = m_heapItem->heapIndex();
+    ASSERT(newHeapIndex != oldHeapIndex);
+#endif
+
     ASSERT(!inHeap() || hasValidHeapPosition());
 }
 
     ASSERT(!inHeap() || hasValidHeapPosition());
 }
 
@@ -383,12 +472,8 @@ void TimerBase::setNextFireTime(MonotonicTime newTime)
     if (m_unalignedNextFireTime != newTime)
         m_unalignedNextFireTime = newTime;
 
     if (m_unalignedNextFireTime != newTime)
         m_unalignedNextFireTime = newTime;
 
-    // Accessing thread global data is slow. Cache the heap pointer.
-    if (!m_cachedThreadGlobalTimerHeap)
-        m_cachedThreadGlobalTimerHeap = &threadGlobalTimerHeap();
-
     // Keep heap valid while changing the next-fire time.
     // Keep heap valid while changing the next-fire time.
-    MonotonicTime oldTime = m_nextFireTime;
+    MonotonicTime oldTime = nextFireTime();
     // Don't realign zero-delay timers.
     if (newTime) {
         if (auto newAlignedTime = alignedFireTime(newTime))
     // Don't realign zero-delay timers.
     if (newTime) {
         if (auto newAlignedTime = alignedFireTime(newTime))
@@ -396,16 +481,20 @@ void TimerBase::setNextFireTime(MonotonicTime newTime)
     }
 
     if (oldTime != newTime) {
     }
 
     if (oldTime != newTime) {
-        m_nextFireTime = newTime;
         // FIXME: This should be part of ThreadTimers, or another per-thread structure.
         static std::atomic<unsigned> currentHeapInsertionOrder;
         // FIXME: This should be part of ThreadTimers, or another per-thread structure.
         static std::atomic<unsigned> currentHeapInsertionOrder;
-        m_heapInsertionOrder = currentHeapInsertionOrder++;
+        auto newOrder = currentHeapInsertionOrder++;
+
+        if (!m_heapItem)
+            m_heapItem = ThreadTimerHeapItem::create(*this, newTime, 0);
+        m_heapItem->time = newTime;
+        m_heapItem->insertionOrder = newOrder;
 
 
-        bool wasFirstTimerInHeap = m_heapIndex == 0;
+        bool wasFirstTimerInHeap = m_heapItem->isFirstInHeap();
 
         updateHeapIfNeeded(oldTime);
 
 
         updateHeapIfNeeded(oldTime);
 
-        bool isFirstTimerInHeap = m_heapIndex == 0;
+        bool isFirstTimerInHeap = m_heapItem->isFirstInHeap();
 
         if (wasFirstTimerInHeap || isFirstTimerInHeap)
             threadGlobalData().threadTimers().updateSharedTimer();
 
         if (wasFirstTimerInHeap || isFirstTimerInHeap)
             threadGlobalData().threadTimers().updateSharedTimer();
index 98e51e3..6601675 100644 (file)
@@ -25,6 +25,7 @@
 
 #pragma once
 
 
 #pragma once
 
+#include "ThreadTimers.h"
 #include <functional>
 #include <wtf/Function.h>
 #include <wtf/MonotonicTime.h>
 #include <functional>
 #include <wtf/Function.h>
 #include <wtf/MonotonicTime.h>
@@ -33,6 +34,7 @@
 #include <wtf/Seconds.h>
 #include <wtf/Threading.h>
 #include <wtf/Vector.h>
 #include <wtf/Seconds.h>
 #include <wtf/Threading.h>
 #include <wtf/Vector.h>
+#include <wtf/WeakPtr.h>
 
 #if PLATFORM(IOS_FAMILY)
 #include "WebCoreThread.h"
 
 #if PLATFORM(IOS_FAMILY)
 #include "WebCoreThread.h"
 
 namespace WebCore {
 
 
 namespace WebCore {
 
-// Time intervals are all in seconds.
-
-class TimerHeapElement;
-
 class TimerBase {
     WTF_MAKE_NONCOPYABLE(TimerBase);
     WTF_MAKE_FAST_ALLOCATED;
 class TimerBase {
     WTF_MAKE_NONCOPYABLE(TimerBase);
     WTF_MAKE_FAST_ALLOCATED;
@@ -63,7 +61,7 @@ public:
     Seconds nextUnalignedFireInterval() const;
     Seconds repeatInterval() const { return m_repeatInterval; }
 
     Seconds nextUnalignedFireInterval() const;
     Seconds repeatInterval() const { return m_repeatInterval; }
 
-    void augmentFireInterval(Seconds delta) { setNextFireTime(m_nextFireTime + delta); }
+    void augmentFireInterval(Seconds delta) { setNextFireTime(m_heapItem->time + delta); }
     void augmentRepeatInterval(Seconds delta) { augmentFireInterval(delta); m_repeatInterval += delta; }
 
     void didChangeAlignmentInterval();
     void augmentRepeatInterval(Seconds delta) { augmentFireInterval(delta); m_repeatInterval += delta; }
 
     void didChangeAlignmentInterval();
@@ -80,7 +78,7 @@ private:
 
     void setNextFireTime(MonotonicTime);
 
 
     void setNextFireTime(MonotonicTime);
 
-    bool inHeap() const { return m_heapIndex != -1; }
+    bool inHeap() const { return m_heapItem && m_heapItem->isInHeap(); }
 
     bool hasValidHeapPosition() const;
     void updateHeapIfNeeded(MonotonicTime oldTime);
 
     bool hasValidHeapPosition() const;
     void updateHeapIfNeeded(MonotonicTime oldTime);
@@ -92,17 +90,15 @@ private:
     void heapInsert();
     void heapPop();
     void heapPopMin();
     void heapInsert();
     void heapPop();
     void heapPopMin();
+    static void heapDeleteNullMin(ThreadTimerHeap&);
 
 
-    Vector<TimerBase*>& timerHeap() const { ASSERT(m_cachedThreadGlobalTimerHeap); return *m_cachedThreadGlobalTimerHeap; }
+    MonotonicTime nextFireTime() const { return m_heapItem ? m_heapItem->time : MonotonicTime { }; }
 
 
-    MonotonicTime m_nextFireTime; // 0 if inactive
     MonotonicTime m_unalignedNextFireTime; // m_nextFireTime not considering alignment interval
     Seconds m_repeatInterval; // 0 if not repeating
     MonotonicTime m_unalignedNextFireTime; // m_nextFireTime not considering alignment interval
     Seconds m_repeatInterval; // 0 if not repeating
-    signed int m_heapIndex : 31; // -1 if not in heap
-    bool m_wasDeleted : 1;
-    unsigned m_heapInsertionOrder; // Used to keep order among equal-fire-time timers
-    Vector<TimerBase*>* m_cachedThreadGlobalTimerHeap { nullptr };
+    bool m_wasDeleted { false };
 
 
+    RefPtr<ThreadTimerHeapItem> m_heapItem;
     Ref<Thread> m_thread { Thread::current() };
 
     friend class ThreadTimers;
     Ref<Thread> m_thread { Thread::current() };
 
     friend class ThreadTimers;
@@ -142,7 +138,7 @@ inline bool TimerBase::isActive() const
 #else
     ASSERT(WebThreadIsCurrent() || pthread_main_np() || m_thread.ptr() == &Thread::current());
 #endif // PLATFORM(IOS_FAMILY)
 #else
     ASSERT(WebThreadIsCurrent() || pthread_main_np() || m_thread.ptr() == &Thread::current());
 #endif // PLATFORM(IOS_FAMILY)
-    return static_cast<bool>(m_nextFireTime);
+    return static_cast<bool>(nextFireTime());
 }
 
 class DeferrableOneShotTimer : protected TimerBase {
 }
 
 class DeferrableOneShotTimer : protected TimerBase {