Attachment 358771 Details for Bug 192975 – Patch for landing

[patch] Patch for landing

bug-192975-20190109172827.patch (text/plain), 35.19 KB, created by Ryosuke Niwa on 2019-01-09 17:28:28 PST

(hide)

Description:

Filename:

MIME Type:

Creator: Ryosuke Niwa

Created: 2019-01-09 17:28:28 PST

Size: 35.19 KB

patch

obsolete

>Index: Source/WebCore/ChangeLog
>===================================================================
>--- Source/WebCore/ChangeLog	(revision 239789)
>+++ Source/WebCore/ChangeLog	(working copy)
>@@ -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  Zalan Bujtas  <zalan@apple.com>
> 
>         [Datalist] Crash when input with datalist is dynamically added.
>Index: Source/WebCore/WebCore.xcodeproj/project.pbxproj
>===================================================================
>--- Source/WebCore/WebCore.xcodeproj/project.pbxproj	(revision 239789)
>+++ Source/WebCore/WebCore.xcodeproj/project.pbxproj	(working copy)
>@@ -452,7 +452,7 @@
> 		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 */; };
>Index: Source/WebCore/platform/ThreadTimers.cpp
>===================================================================
>--- Source/WebCore/platform/ThreadTimers.cpp	(revision 239789)
>+++ Source/WebCore/platform/ThreadTimers.cpp	(working copy)
>@@ -75,12 +75,18 @@ void ThreadTimers::updateSharedTimer()
> {
>     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 {
>-        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.
>@@ -104,17 +110,23 @@ void ThreadTimers::sharedTimerFiredInter
>     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.
>-        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())
>Index: Source/WebCore/platform/ThreadTimers.h
>===================================================================
>--- Source/WebCore/platform/ThreadTimers.h	(revision 239789)
>+++ Source/WebCore/platform/ThreadTimers.h	(working copy)
>@@ -29,36 +29,100 @@
> 
> #include <wtf/MonotonicTime.h>
> #include <wtf/Noncopyable.h>
>+#include <wtf/RefCounted.h>
>+#include <wtf/ThreadSafeRefCounted.h>
> #include <wtf/Vector.h>
> 
> namespace WebCore {
> 
>-    class SharedTimer;
>-    class TimerBase;
>+class SharedTimer;
>+class ThreadTimers;
>+class TimerBase;
>+
>+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*);
>+
>+    ThreadTimerHeap& timerHeap() { return m_timerHeap; }
>+
>+    void updateSharedTimer();
>+    void fireTimersInNestedEventLoop();
>+
>+private:
>+    void sharedTimerFiredInternal();
>+    void fireTimersInNestedEventLoopInternal();
>+
>+    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;
>+}
> 
>-    // 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*);
>-
>-        Vector<TimerBase*>& timerHeap() { return m_timerHeap; }
>-
>-        void updateSharedTimer();
>-        void fireTimersInNestedEventLoop();
>-
>-    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;
>-    };
>+inline ThreadTimerHeap& ThreadTimerHeapItem::timerHeap() const
>+{
>+    return m_threadTimers.timerHeap();
>+}
> 
> }
> 
>Index: Source/WebCore/platform/Timer.cpp
>===================================================================
>--- Source/WebCore/platform/Timer.cpp	(revision 239789)
>+++ Source/WebCore/platform/Timer.cpp	(working copy)
>@@ -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.
>-static Vector<TimerBase*>& threadGlobalTimerHeap()
>+#if !ASSERT_DISABLED
>+static ThreadTimerHeap& threadGlobalTimerHeap()
> {
>     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:
>-    TimerHeapPointer(TimerBase** pointer) : m_pointer(pointer) { }
>+    TimerHeapPointer(RefPtr<ThreadTimerHeapItem>* pointer)
>+        : m_pointer(pointer)
>+    { }
>+
>     TimerHeapReference operator*() const;
>-    TimerBase* operator->() const { return *m_pointer; }
>+    RefPtr<ThreadTimerHeapItem>& operator->() const { return *m_pointer; }
> private:
>-    TimerBase** m_pointer;
>+    RefPtr<ThreadTimerHeapItem>* m_pointer;
> };
> 
> 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; }
>-    TimerHeapReference& operator=(TimerBase*);
>-    TimerHeapReference& operator=(TimerHeapReference);
>+    TimerHeapReference& operator=(TimerHeapReference&&);
>+    TimerHeapReference& operator=(RefPtr<ThreadTimerHeapItem>&&);
>+
>+    void swap(TimerHeapReference& other);
>+
>+    void updateHeapIndex();
>+
> private:
>-    TimerBase*& m_reference;
>+    RefPtr<ThreadTimerHeapItem>& m_reference;
>+
>+    friend void swap(TimerHeapReference a, TimerHeapReference b);
> };
> 
> 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;
> }
> 
>-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 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:
>-    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++); }
>@@ -125,7 +167,7 @@ public:
> 
>     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
>@@ -149,7 +191,7 @@ private:
>     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; }
>@@ -169,23 +211,34 @@ inline ptrdiff_t operator-(TimerHeapIter
> 
> 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 shouldSuppressThreadSafetyCh
> }
> 
> 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());
>+    if (m_heapItem) {
>+        m_heapItem->clearTimer();
>+        m_heapItem = nullptr;
>+    }
>     m_wasDeleted = true;
> }
> 
>@@ -230,7 +286,7 @@ void TimerBase::stop()
>     m_repeatInterval = 0_s;
>     setNextFireTime(MonotonicTime { });
> 
>-    ASSERT(!static_cast<bool>(m_nextFireTime));
>+    ASSERT(!static_cast<bool>(nextFireTime()));
>     ASSERT(m_repeatInterval == 0_s);
>     ASSERT(!inHeap());
> }
>@@ -238,57 +294,66 @@ void TimerBase::stop()
> Seconds TimerBase::nextFireInterval() const
> {
>     ASSERT(isActive());
>+    ASSERT(m_heapItem);
>     MonotonicTime current = MonotonicTime::now();
>-    if (m_nextFireTime < current)
>+    auto fireTime = nextFireTime();
>+    if (fireTime < current)
>         return 0_s;
>-    return m_nextFireTime - current;
>+    return fireTime - current;
> }
> 
> 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.
>-    ASSERT(inHeap() == static_cast<bool>(m_nextFireTime));
>+    ASSERT(inHeap() == static_cast<bool>(nextFireTime()));
>     if (inHeap())
>         checkHeapIndex();
> }
> 
> void TimerBase::heapDecreaseKey()
> {
>-    ASSERT(static_cast<bool>(m_nextFireTime));
>+    ASSERT(static_cast<bool>(nextFireTime()));
>+    ASSERT(m_heapItem);
>     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()
> {
>-    ASSERT(!static_cast<bool>(m_nextFireTime));
>+    ASSERT(!static_cast<bool>(nextFireTime()));
>     heapPop();
>-    timerHeap().removeLast();
>-    m_heapIndex = -1;
>+    m_heapItem->timerHeap().removeLast();
>+    m_heapItem->setNotInHeap();
> }
> 
> void TimerBase::heapDeleteMin()
> {
>-    ASSERT(!static_cast<bool>(m_nextFireTime));
>+    ASSERT(!static_cast<bool>(nextFireTime()));
>     heapPopMin();
>-    timerHeap().removeLast();
>-    m_heapIndex = -1;
>+    m_heapItem->timerHeap().removeLast();
>+    m_heapItem->setNotInHeap();
> }
> 
> inline void TimerBase::heapIncreaseKey()
> {
>-    ASSERT(static_cast<bool>(m_nextFireTime));
>+    ASSERT(static_cast<bool>(nextFireTime()));
>     heapPop();
>     heapDecreaseKey();
> }
>@@ -296,81 +361,105 @@ inline void TimerBase::heapIncreaseKey()
> 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()
> {
>+    ASSERT(m_heapItem);
>     // 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();
>-    m_nextFireTime = fireTime;
>+    m_heapItem->time = fireTime;
> }
> 
> void TimerBase::heapPopMin()
> {
>-    ASSERT(this == timerHeap().first());
>+    ASSERT(m_heapItem == m_heapItem->timerHeap().first());
>     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();
>-    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;
>-    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;
>-    TimerHeapLessThanFunction compareHeapPosition;
>-    return compareHeapPosition(heap[childIndex], current);
>+    return TimerHeapLessThanFunction::compare(heap[childIndex], *current);
> }
> 
> 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.
>-    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;
>-    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)
> {
>-    if (m_nextFireTime && hasValidHeapPosition())
>+    auto fireTime = nextFireTime();
>+    if (fireTime && hasValidHeapPosition())
>         return;
>-#ifndef NDEBUG
>-    int oldHeapIndex = m_heapIndex;
>+
>+#if !ASSERT_DISABLED
>+    Optional<unsigned> oldHeapIndex;
>+    if (m_heapItem->isInHeap())
>+        oldHeapIndex = m_heapItem->heapIndex();
> #endif
>+
>     if (!oldTime)
>         heapInsert();
>-    else if (!m_nextFireTime)
>+    else if (!fireTime)
>         heapDelete();
>-    else if (m_nextFireTime < oldTime)
>+    else if (fireTime < oldTime)
>         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());
> }
> 
>@@ -383,12 +472,8 @@ void TimerBase::setNextFireTime(Monotoni
>     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.
>-    MonotonicTime oldTime = m_nextFireTime;
>+    MonotonicTime oldTime = nextFireTime();
>     // Don't realign zero-delay timers.
>     if (newTime) {
>         if (auto newAlignedTime = alignedFireTime(newTime))
>@@ -396,16 +481,20 @@ void TimerBase::setNextFireTime(Monotoni
>     }
> 
>     if (oldTime != newTime) {
>-        m_nextFireTime = newTime;
>         // 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);
> 
>-        bool isFirstTimerInHeap = m_heapIndex == 0;
>+        bool isFirstTimerInHeap = m_heapItem->isFirstInHeap();
> 
>         if (wasFirstTimerInHeap || isFirstTimerInHeap)
>             threadGlobalData().threadTimers().updateSharedTimer();
>Index: Source/WebCore/platform/Timer.h
>===================================================================
>--- Source/WebCore/platform/Timer.h	(revision 239789)
>+++ Source/WebCore/platform/Timer.h	(working copy)
>@@ -25,6 +25,7 @@
> 
> #pragma once
> 
>+#include "ThreadTimers.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/WeakPtr.h>
> 
> #if PLATFORM(IOS_FAMILY)
> #include "WebCoreThread.h"
>@@ -40,10 +42,6 @@
> 
> namespace WebCore {
> 
>-// Time intervals are all in seconds.
>-
>-class TimerHeapElement;
>-
> class TimerBase {
>     WTF_MAKE_NONCOPYABLE(TimerBase);
>     WTF_MAKE_FAST_ALLOCATED;
>@@ -63,7 +61,7 @@ public:
>     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();
>@@ -80,7 +78,7 @@ private:
> 
>     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);
>@@ -92,17 +90,15 @@ private:
>     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
>-    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;
>@@ -142,7 +138,7 @@ inline bool TimerBase::isActive() const
> #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 {

Actions: View | Formatted Diff | Diff

Attachments on bug 192975: 357931 | 357980 | 358010 | 358055 | 358766 | 358771