⚠ Archived content — this site is no longer maintained.   Current WebKit documentation is at docs.webkit.org.

Changeset 239814 in webkit


Ignore:
Timestamp:
Jan 9, 2019, 6:27:45 PM (8 years ago)
Author:
rniwa@webkit.org
Message:

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.

Location:
trunk/Source/WebCore
Files:
6 edited

Legend:

Unmodified
Added
Removed

  • trunk/Source/WebCore/ChangeLog

    r239791 r239814  
     12019-01-09  Ryosuke Niwa  <rniwa@webkit.org>
     2
     3        ThreadTimers should not store a raw pointer in its heap
     4        https://bugs.webkit.org/show_bug.cgi?id=192975
     5        <rdar://problem/46893946>
     6
     7        Reviewed by Geoffrey Garen.
     8
     9        Right now, ThreadTimers's heap data structure stores a raw pointer to TimerBase. In order to harden the timer code,
     10        this patch replaces it with ThreadTimerHeapItem, a newly introduced struct, which effectively acks like
     11        WeakReference<TimerBase*> as the timer heap and TimerBase both store RefPtr to it, and TimerBase's destructor clears
     12        the raw pointer back to TimerBase*.
     13
     14        This approach was taken instead of an out-right adoptation of WeakPtr since the heap data structure requires each node
     15        in the heap to have a fixed "priority" yet WeakPtr with no valid pointer back to TimerBase would effectively lose its
     16        "priority" thereby corrupting the heap data structure. That is, each item in the heap must remember its fire time and
     17        insertion order even when the underlying TimerBase had gone away (this should never happen but the whole point of this
     18        hardening is to make it work even in the precense of such a bug).
     19
     20        This patch also moves the heap index in TimerBase to ThreadTimerHeapItem, and replaces the pointer to the heap vector
     21        in TimerBase by a reference to ThreadTimers in ThreadTimerHeapItem. Note that ThreadTimers is a per-thread singleton.
     22
     23        The correctness of this hardening was tested by commenting out the call to stop() and !isInHeap() assertion in
     24        TimerBase::~TimerBase() as well as the !isInHeap() assertion in ThreadTimerHeapItem::clearTimer() and observing that
     25        layout tests run successfully without hitting any debug assertions.
     26
     27        No new tests since there should be no observable behavior difference.
     28
     29        * WebCore.xcodeproj/project.pbxproj: Export ThreadTimers.h as a private header since it's now included in Timer.h
     30        * platform/ThreadTimers.cpp:
     31        (WebCore::ThreadTimers::updateSharedTimer): Delete ThreadTimerHeapItem's with nullptr TimerBase* (TimerBase had
     32        already been deleted). This should only happen when TimerBase's destructor failed to remove itself from the timer heap,
     33        which should never happen.
     34        (WebCore::ThreadTimers::sharedTimerFiredInternal): Ditto. Also removed the redundant code which had removed the timer
     35        from the heap since setNextFireTime does the removal already.
     36        * platform/ThreadTimers.h: Outdented the whole file.
     37        (WebCore::ThreadTimers::timerHeap): We use Vector<RefPtr<ThreadTimerHeapItem>> instead of Vector<Ref<~>> since Ref<~>
     38        doesn't have a copy constructor which is used by std::push_heap.
     39        (WebCore::ThreadTimerHeapItem): Added.
     40        (WebCore::ThreadTimerHeapItem::hasTimer const): Added.
     41        (WebCore::ThreadTimerHeapItem::setNotInHeap): Added. ThreadTimerHeapItem uses unsigned -1 as the single value which
     42        signifies the item not being in the heap instead of all negative values as in the old code in TimerBase.
     43        (WebCore::ThreadTimerHeapItem::isInHeap const): Added.
     44        (WebCore::ThreadTimerHeapItem::isFirstInHeap const): Added.
     45        (WebCore::ThreadTimerHeapItem::timer): Added.
     46        (WebCore::ThreadTimerHeapItem::clearTimer): Added.
     47        (WebCore::ThreadTimerHeapItem::heapIndex const): Added.
     48        (WebCore::ThreadTimerHeapItem::setHeapIndex): Added.
     49        (WebCore::ThreadTimerHeapItem::timerHeap const): Added.
     50        * platform/Timer.cpp:
     51        (WebCore::threadGlobalTimerHeap): This function is now only used in assertions.
     52        (WebCore::ThreadTimerHeapItem::ThreadTimerHeapItem): Added.
     53        (WebCore::ThreadTimerHeapItem::create): Added.
     54        (WebCore::TimerHeapPointer::TimerHeapPointer):
     55        (WebCore::TimerHeapPointer::operator-> const):
     56        (WebCore::TimerHeapReference::TimerHeapReference): Added a copy constructor.
     57        (WebCore::TimerHeapReference::copyRef const): Added.
     58        (WebCore::TimerHeapReference::operator RefPtr<ThreadTimerHeapItem>& const):
     59        (WebCore::TimerHeapPointer::operator* const):
     60        (WebCore::TimerHeapReference::operator=): Use move assignment operator.
     61        (WebCore::TimerHeapReference::swapWith):
     62        (WebCore::TimerHeapReference::updateHeapIndex): Extracted to share code between two verions of operator=.
     63        (WebCore::swap):
     64        (WebCore::TimerHeapIterator::TimerHeapIterator):
     65        (WebCore::TimerHeapIterator::operator-> const):
     66        (WebCore::TimerHeapLessThanFunction::compare): Added variants which take RefPtr<ThreadTimerHeapItem>.
     67        (WebCore::TimerHeapLessThanFunction::operator() const):
     68        (WebCore::TimerBase::TimerBase):
     69        (WebCore::TimerBase::~TimerBase):Clear the raw pointer in ThreadTimerHeapItem.
     70        (WebCore::TimerBase::stop):
     71        (WebCore::TimerBase::nextFireInterval const):
     72        (WebCore::TimerBase::checkHeapIndex const): Added the consistency check for other items in the heap.
     73        (WebCore::TimerBase::checkConsistency const):
     74        (WebCore::TimerBase::heapDecreaseKey):
     75        (WebCore::TimerBase::heapDelete):
     76        (WebCore::TimerBase::heapDeleteMin):
     77        (WebCore::TimerBase::heapIncreaseKey):
     78        (WebCore::TimerBase::heapInsert):
     79        (WebCore::TimerBase::heapPop):
     80        (WebCore::TimerBase::heapPopMin):
     81        (WebCore::TimerBase::heapDeleteNullMin): Added. Used to delete ThreadTimerHeapItem which no longer has a valid TimerBase.
     82        (WebCore::parentHeapPropertyHolds):
     83        (WebCore::childHeapPropertyHolds):
     84        (WebCore::TimerBase::hasValidHeapPosition const):
     85        (WebCore::TimerBase::updateHeapIfNeeded): Tweaked the heap index assertion as heapIndex() itself would assert when called
     86        on an item with an invalid (-1) heap index.
     87        (WebCore::TimerBase::setNextFireTime): Create ThreadTimerHeapItem. Note m_heapItem is never cleared until this TimerBase
     88        is deleted.
     89        (WebCore::TimerHeapReference::operator TimerBase* const): Deleted.
     90        * platform/Timer.h:
     91        (WebCore::TimerBase): Replaced m_nextFireTime, m_heapIndex, m_heapInsertionOrder, and m_cachedThreadGlobalTimerHeap
     92        by m_heapItem, RefPtr to an ThreadTimerHeapItem.
     93        (WebCore::TimerBase::augmentFireInterval):
     94        (WebCore::TimerBase::inHeap const):
     95        (WebCore::TimerBase::nextFireTime const):
     96        (WebCore::TimerBase::isActive const):
     97        (WebCore::TimerBase:: const): Deleted.
     98
    1992019-01-09  Alex Christensen  <achristensen@webkit.org>
    2100

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

    r239723 r239814  
    453453                15C7708D100D3C6B005BA267 /* ValidityState.h in Headers */ = {isa = PBXBuildFile; fileRef = 15C7708A100D3C6A005BA267 /* ValidityState.h */; settings = {ATTRIBUTES = (Private, ); }; };
    454454                15C77093100D3CA8005BA267 /* JSValidityState.h in Headers */ = {isa = PBXBuildFile; fileRef = 15C77091100D3CA8005BA267 /* JSValidityState.h */; };
    455                 185BCF290F3279CE000EA262 /* ThreadTimers.h in Headers */ = {isa = PBXBuildFile; fileRef = 185BCF270F3279CE000EA262 /* ThreadTimers.h */; };
     455                185BCF290F3279CE000EA262 /* ThreadTimers.h in Headers */ = {isa = PBXBuildFile; fileRef = 185BCF270F3279CE000EA262 /* ThreadTimers.h */; settings = {ATTRIBUTES = (Private, ); }; };
    456456                188604B40F2E654A000B6443 /* DOMTimer.h in Headers */ = {isa = PBXBuildFile; fileRef = 188604B20F2E654A000B6443 /* DOMTimer.h */; settings = {ATTRIBUTES = (Private, ); }; };
    457457                18F831B80FD48C7800D8C56B /* WorkerLoaderProxy.h in Headers */ = {isa = PBXBuildFile; fileRef = 18F831B70FD48C7800D8C56B /* WorkerLoaderProxy.h */; settings = {ATTRIBUTES = (Private, ); }; };

  • trunk/Source/WebCore/platform/ThreadTimers.cpp

    r237266 r239814  
    7676    if (!m_sharedTimer)
    7777        return;
    78        
     78
     79    while (!m_timerHeap.isEmpty() && !m_timerHeap.first()->hasTimer()) {
     80        ASSERT_NOT_REACHED();
     81        TimerBase::heapDeleteNullMin(m_timerHeap);
     82    }
     83    ASSERT(m_timerHeap.isEmpty() || m_timerHeap.first()->hasTimer());
     84
    7985    if (m_firingTimers || m_timerHeap.isEmpty()) {
    8086        m_pendingSharedTimerFireTime = MonotonicTime { };
    8187        m_sharedTimer->stop();
    8288    } else {
    83         MonotonicTime nextFireTime = m_timerHeap.first()->m_nextFireTime;
     89        MonotonicTime nextFireTime = m_timerHeap.first()->time;
    8490        MonotonicTime currentMonotonicTime = MonotonicTime::now();
    8591        if (m_pendingSharedTimerFireTime) {
    … …  
    105111    MonotonicTime timeToQuit = fireTime + maxDurationOfFiringTimers;
    106112
    107     while (!m_timerHeap.isEmpty() && m_timerHeap.first()->m_nextFireTime <= fireTime) {
    108         TimerBase* timer = m_timerHeap.first();
    109         timer->m_nextFireTime = MonotonicTime { };
    110         timer->m_unalignedNextFireTime = MonotonicTime { };
    111         timer->heapDeleteMin();
     113    while (!m_timerHeap.isEmpty()) {
     114        Ref<ThreadTimerHeapItem> item = *m_timerHeap.first();
     115        ASSERT(item->hasTimer());
     116        if (!item->hasTimer()) {
     117            TimerBase::heapDeleteNullMin(m_timerHeap);
     118            continue;
     119        }
    112120
    113         Seconds interval = timer->repeatInterval();
    114         timer->setNextFireTime(interval ? fireTime + interval : MonotonicTime { });
     121        if (item->time > fireTime)
     122            break;
     123
     124        auto& timer = item->timer();
     125        Seconds interval = timer.repeatInterval();
     126        timer.setNextFireTime(interval ? fireTime + interval : MonotonicTime { });
    115127
    116128        // Once the timer has been fired, it may be deleted, so do nothing else with it after this point.
    117         timer->fired();
     129        item->timer().fired();
    118130
    119131        // Catch the case where the timer asked timers to fire in a nested event loop, or we are over time limit.

  • trunk/Source/WebCore/platform/ThreadTimers.h

    r215136 r239814  
    3030#include <wtf/MonotonicTime.h>
    3131#include <wtf/Noncopyable.h>
     32#include <wtf/RefCounted.h>
     33#include <wtf/ThreadSafeRefCounted.h>
    3234#include <wtf/Vector.h>
    3335
    3436namespace WebCore {
    3537
    36     class SharedTimer;
    37     class TimerBase;
     38class SharedTimer;
     39class ThreadTimers;
     40class TimerBase;
    3841
    39     // A collection of timers per thread. Kept in ThreadGlobalData.
    40     class ThreadTimers {
    41         WTF_MAKE_NONCOPYABLE(ThreadTimers); WTF_MAKE_FAST_ALLOCATED;
    42     public:
    43         ThreadTimers();
     42struct ThreadTimerHeapItem;
     43typedef Vector<RefPtr<ThreadTimerHeapItem>> ThreadTimerHeap;
     44   
     45// A collection of timers per thread. Kept in ThreadGlobalData.
     46class ThreadTimers {
     47    WTF_MAKE_NONCOPYABLE(ThreadTimers); WTF_MAKE_FAST_ALLOCATED;
     48public:
     49    ThreadTimers();
    4450
    45         // On a thread different then main, we should set the thread's instance of the SharedTimer.
    46         void setSharedTimer(SharedTimer*);
     51    // On a thread different then main, we should set the thread's instance of the SharedTimer.
     52    void setSharedTimer(SharedTimer*);
    4753
    48         Vector<TimerBase*>& timerHeap() { return m_timerHeap; }
     54    ThreadTimerHeap& timerHeap() { return m_timerHeap; }
    4955
    50         void updateSharedTimer();
    51         void fireTimersInNestedEventLoop();
     56    void updateSharedTimer();
     57    void fireTimersInNestedEventLoop();
    5258
    53     private:
    54         void sharedTimerFiredInternal();
    55         void fireTimersInNestedEventLoopInternal();
     59private:
     60    void sharedTimerFiredInternal();
     61    void fireTimersInNestedEventLoopInternal();
    5662
    57         Vector<TimerBase*> m_timerHeap;
    58         SharedTimer* m_sharedTimer { nullptr }; // External object, can be a run loop on a worker thread. Normally set/reset by worker thread.
    59         bool m_firingTimers { false }; // Reentrancy guard.
    60         MonotonicTime m_pendingSharedTimerFireTime;
    61     };
     63    ThreadTimerHeap m_timerHeap;
     64    SharedTimer* m_sharedTimer { nullptr }; // External object, can be a run loop on a worker thread. Normally set/reset by worker thread.
     65    bool m_firingTimers { false }; // Reentrancy guard.
     66    MonotonicTime m_pendingSharedTimerFireTime;
     67};
     68
     69struct ThreadTimerHeapItem : ThreadSafeRefCounted<ThreadTimerHeapItem> {
     70    static RefPtr<ThreadTimerHeapItem> create(TimerBase&, MonotonicTime, unsigned);
     71
     72    bool hasTimer() const { return m_timer; }
     73    TimerBase& timer();
     74    void clearTimer();
     75
     76    ThreadTimerHeap& timerHeap() const;
     77
     78    unsigned heapIndex() const;
     79    void setHeapIndex(unsigned newIndex);
     80    void setNotInHeap() { m_heapIndex = invalidHeapIndex; }
     81
     82    bool isInHeap() const { return m_heapIndex != invalidHeapIndex; }
     83    bool isFirstInHeap() const { return !m_heapIndex; }
     84
     85    MonotonicTime time;
     86    unsigned insertionOrder { 0 };
     87
     88private:
     89    ThreadTimers& m_threadTimers;
     90    TimerBase* m_timer { nullptr };
     91    unsigned m_heapIndex { invalidHeapIndex };
     92
     93    static const unsigned invalidHeapIndex = static_cast<unsigned>(-1);
     94
     95    ThreadTimerHeapItem(TimerBase&, MonotonicTime, unsigned);
     96};
     97
     98inline TimerBase& ThreadTimerHeapItem::timer()
     99{
     100    ASSERT(m_timer);
     101    return *m_timer;
     102}
     103
     104inline void ThreadTimerHeapItem::clearTimer()
     105{
     106    ASSERT(!isInHeap());
     107    m_timer = nullptr;
     108}
     109
     110inline unsigned ThreadTimerHeapItem::heapIndex() const
     111{
     112    ASSERT(m_heapIndex != invalidHeapIndex);
     113    return static_cast<unsigned>(m_heapIndex);
     114}
     115
     116inline void ThreadTimerHeapItem::setHeapIndex(unsigned newIndex)
     117{
     118    ASSERT(newIndex != invalidHeapIndex);
     119    m_heapIndex = newIndex;
     120}
     121
     122inline ThreadTimerHeap& ThreadTimerHeapItem::timerHeap() const
     123{
     124    return m_threadTimers.timerHeap();
     125}
    62126
    63127}

  • trunk/Source/WebCore/platform/Timer.cpp

    r237266 r239814  
    5151//
    5252// When a timer's "next fire time" changes, we need to move it around in the priority queue.
    53 static Vector<TimerBase*>& threadGlobalTimerHeap()
     53#if !ASSERT_DISABLED
     54static ThreadTimerHeap& threadGlobalTimerHeap()
    5455{
    5556    return threadGlobalData().threadTimers().timerHeap();
    5657}
     58#endif
     59
     60inline ThreadTimerHeapItem::ThreadTimerHeapItem(TimerBase& timer, MonotonicTime time, unsigned insertionOrder)
     61    : time(time)
     62    , insertionOrder(insertionOrder)
     63    , m_threadTimers(threadGlobalData().threadTimers())
     64    , m_timer(&timer)
     65{
     66    ASSERT(m_timer);
     67}
     68   
     69inline RefPtr<ThreadTimerHeapItem> ThreadTimerHeapItem::create(TimerBase& timer, MonotonicTime time, unsigned insertionOrder)
     70{
     71    return adoptRef(*new ThreadTimerHeapItem { timer, time, insertionOrder });
     72}
     73
    5774// ----------------
    5875
    5976class TimerHeapPointer {
    6077public:
    61     TimerHeapPointer(TimerBase** pointer) : m_pointer(pointer) { }
     78    TimerHeapPointer(RefPtr<ThreadTimerHeapItem>* pointer)
     79        : m_pointer(pointer)
     80    { }
     81
    6282    TimerHeapReference operator*() const;
    63     TimerBase* operator->() const { return *m_pointer; }
     83    RefPtr<ThreadTimerHeapItem>& operator->() const { return *m_pointer; }
    6484private:
    65     TimerBase** m_pointer;
     85    RefPtr<ThreadTimerHeapItem>* m_pointer;
    6686};
    6787
    6888class TimerHeapReference {
    6989public:
    70     TimerHeapReference(TimerBase*& reference) : m_reference(reference) { }
    71     operator TimerBase*() const { return m_reference; }
     90    TimerHeapReference(RefPtr<ThreadTimerHeapItem>& reference)
     91        : m_reference(reference)
     92    { }
     93
     94    TimerHeapReference(const TimerHeapReference& other)
     95        : m_reference(other.m_reference)
     96    { }
     97
     98    operator RefPtr<ThreadTimerHeapItem>&() const { return m_reference; }
    7299    TimerHeapPointer operator&() const { return &m_reference; }
    73     TimerHeapReference& operator=(TimerBase*);
    74     TimerHeapReference& operator=(TimerHeapReference);
     100    TimerHeapReference& operator=(TimerHeapReference&&);
     101    TimerHeapReference& operator=(RefPtr<ThreadTimerHeapItem>&&);
     102
     103    void swap(TimerHeapReference& other);
     104
     105    void updateHeapIndex();
     106
    75107private:
    76     TimerBase*& m_reference;
     108    RefPtr<ThreadTimerHeapItem>& m_reference;
     109
     110    friend void swap(TimerHeapReference a, TimerHeapReference b);
    77111};
    78112
    79113inline TimerHeapReference TimerHeapPointer::operator*() const
    80114{
    81     return *m_pointer;
    82 }
    83 
    84 inline TimerHeapReference& TimerHeapReference::operator=(TimerBase* timer)
    85 {
    86     m_reference = timer;
    87     Vector<TimerBase*>& heap = timer->timerHeap();
     115    return TimerHeapReference { *m_pointer };
     116}
     117
     118inline TimerHeapReference& TimerHeapReference::operator=(TimerHeapReference&& other)
     119{
     120    m_reference = WTFMove(other.m_reference);
     121    updateHeapIndex();
     122    return *this;
     123}
     124
     125inline TimerHeapReference& TimerHeapReference::operator=(RefPtr<ThreadTimerHeapItem>&& item)
     126{
     127    m_reference = WTFMove(item);
     128    updateHeapIndex();
     129    return *this;
     130}
     131
     132inline void TimerHeapReference::swap(TimerHeapReference& other)
     133{
     134    m_reference.swap(other.m_reference);
     135    updateHeapIndex();
     136    other.updateHeapIndex();
     137}
     138
     139inline void TimerHeapReference::updateHeapIndex()
     140{
     141    auto& heap = m_reference->timerHeap();
    88142    if (&m_reference >= heap.data() && &m_reference < heap.data() + heap.size())
    89         timer->m_heapIndex = &m_reference - heap.data();
    90     return *this;
    91 }
    92 
    93 inline TimerHeapReference& TimerHeapReference::operator=(TimerHeapReference b)
    94 {
    95     TimerBase* timer = b;
    96     return *this = timer;
     143        m_reference->setHeapIndex(&m_reference - heap.data());
    97144}
    98145
    99146inline void swap(TimerHeapReference a, TimerHeapReference b)
    100147{
    101     TimerBase* timerA = a;
    102     TimerBase* timerB = b;
    103 
    104     // Invoke the assignment operator, since that takes care of updating m_heapIndex.
    105     a = timerB;
    106     b = timerA;
     148    a.swap(b);
    107149}
    108150
    … …  
    111153// Class to represent iterators in the heap when calling the standard library heap algorithms.
    112154// Uses a custom pointer and reference type that update indices for pointers in the heap.
    113 class TimerHeapIterator : public std::iterator<std::random_access_iterator_tag, TimerBase*, ptrdiff_t, TimerHeapPointer, TimerHeapReference> {
     155class TimerHeapIterator : public std::iterator<std::random_access_iterator_tag, RefPtr<ThreadTimerHeapItem>, ptrdiff_t, TimerHeapPointer, TimerHeapReference> {
    114156public:
    115     explicit TimerHeapIterator(TimerBase** pointer) : m_pointer(pointer) { checkConsistency(); }
     157    explicit TimerHeapIterator(RefPtr<ThreadTimerHeapItem>* pointer) : m_pointer(pointer) { checkConsistency(); }
    116158
    117159    TimerHeapIterator& operator++() { checkConsistency(); ++m_pointer; checkConsistency(); return *this; }
    … …  
    126168    TimerHeapReference operator*() const { return TimerHeapReference(*m_pointer); }
    127169    TimerHeapReference operator[](ptrdiff_t i) const { return TimerHeapReference(m_pointer[i]); }
    128     TimerBase* operator->() const { return *m_pointer; }
     170    RefPtr<ThreadTimerHeapItem>& operator->() const { return *m_pointer; }
    129171
    130172private:
    … …  
    150192    friend ptrdiff_t operator-(TimerHeapIterator, TimerHeapIterator);
    151193
    152     TimerBase** m_pointer;
     194    RefPtr<ThreadTimerHeapItem>* m_pointer;
    153195};
    154196
    … …  
    170212class TimerHeapLessThanFunction {
    171213public:
    172     bool operator()(const TimerBase*, const TimerBase*) const;
     214    static bool compare(const TimerBase& a, const RefPtr<ThreadTimerHeapItem>& b)
     215    {
     216        return compare(a.m_heapItem->time, a.m_heapItem->insertionOrder, b->time, b->insertionOrder);
     217    }
     218
     219    static bool compare(const RefPtr<ThreadTimerHeapItem>& a, const TimerBase& b)
     220    {
     221        return compare(a->time, a->insertionOrder, b.m_heapItem->time, b.m_heapItem->insertionOrder);
     222    }
     223
     224    bool operator()(const RefPtr<ThreadTimerHeapItem>& a, const RefPtr<ThreadTimerHeapItem>& b) const
     225    {
     226        return compare(a->time, a->insertionOrder, b->time, b->insertionOrder);
     227    }
     228
     229private:
     230    static bool compare(MonotonicTime aTime, unsigned aOrder, MonotonicTime bTime, unsigned bOrder)
     231    {
     232        // The comparisons below are "backwards" because the heap puts the largest
     233        // element first and we want the lowest time to be the first one in the heap.
     234        if (bTime != aTime)
     235            return bTime < aTime;
     236        // We need to look at the difference of the insertion orders instead of comparing the two
     237        // outright in case of overflow.
     238        unsigned difference = aOrder - bOrder;
     239        return difference < std::numeric_limits<unsigned>::max() / 2;
     240    }
    173241};
    174 
    175 inline bool TimerHeapLessThanFunction::operator()(const TimerBase* a, const TimerBase* b) const
    176 {
    177     // The comparisons below are "backwards" because the heap puts the largest
    178     // element first and we want the lowest time to be the first one in the heap.
    179     MonotonicTime aFireTime = a->m_nextFireTime;
    180     MonotonicTime bFireTime = b->m_nextFireTime;
    181     if (bFireTime != aFireTime)
    182         return bFireTime < aFireTime;
    183    
    184     // We need to look at the difference of the insertion orders instead of comparing the two
    185     // outright in case of overflow.
    186     unsigned difference = a->m_heapInsertionOrder - b->m_heapInsertionOrder;
    187     return difference < std::numeric_limits<unsigned>::max() / 2;
    188 }
    189242
    190243// ----------------
    … …  
    202255
    203256TimerBase::TimerBase()
    204     : m_heapIndex(-1)
    205     , m_wasDeleted(false)
     257    : m_wasDeleted(false)
    206258{
    207259}
    … …  
    213265    stop();
    214266    ASSERT(!inHeap());
     267    if (m_heapItem) {
     268        m_heapItem->clearTimer();
     269        m_heapItem = nullptr;
     270    }
    215271    m_wasDeleted = true;
    216272}
    … …  
    231287    setNextFireTime(MonotonicTime { });
    232288
    233     ASSERT(!static_cast<bool>(m_nextFireTime));
     289    ASSERT(!static_cast<bool>(nextFireTime()));
    234290    ASSERT(m_repeatInterval == 0_s);
    235291    ASSERT(!inHeap());
    … …  
    239295{
    240296    ASSERT(isActive());
     297    ASSERT(m_heapItem);
    241298    MonotonicTime current = MonotonicTime::now();
    242     if (m_nextFireTime < current)
     299    auto fireTime = nextFireTime();
     300    if (fireTime < current)
    243301        return 0_s;
    244     return m_nextFireTime - current;
     302    return fireTime - current;
    245303}
    246304
    247305inline void TimerBase::checkHeapIndex() const
    248306{
    249     ASSERT(timerHeap() == threadGlobalTimerHeap());
    250     ASSERT(!timerHeap().isEmpty());
    251     ASSERT(m_heapIndex >= 0);
    252     ASSERT(m_heapIndex < static_cast<int>(timerHeap().size()));
    253     ASSERT(timerHeap()[m_heapIndex] == this);
     307#if !ASSERT_DISABLED
     308    ASSERT(m_heapItem);
     309    auto& heap = m_heapItem->timerHeap();
     310    ASSERT(&heap == &threadGlobalTimerHeap());
     311    ASSERT(!heap.isEmpty());
     312    ASSERT(m_heapItem->isInHeap());
     313    ASSERT(m_heapItem->heapIndex() < m_heapItem->timerHeap().size());
     314    ASSERT(heap[m_heapItem->heapIndex()] == m_heapItem);
     315    for (unsigned i = 0, size = heap.size(); i < size; i++)
     316        ASSERT(heap[i]->heapIndex() == i);
     317#endif
    254318}
    255319
    … …  
    257321{
    258322    // Timers should be in the heap if and only if they have a non-zero next fire time.
    259     ASSERT(inHeap() == static_cast<bool>(m_nextFireTime));
     323    ASSERT(inHeap() == static_cast<bool>(nextFireTime()));
    260324    if (inHeap())
    261325        checkHeapIndex();
    … …  
    264328void TimerBase::heapDecreaseKey()
    265329{
    266     ASSERT(static_cast<bool>(m_nextFireTime));
     330    ASSERT(static_cast<bool>(nextFireTime()));
     331    ASSERT(m_heapItem);
    267332    checkHeapIndex();
    268     TimerBase** heapData = timerHeap().data();
    269     push_heap(TimerHeapIterator(heapData), TimerHeapIterator(heapData + m_heapIndex + 1), TimerHeapLessThanFunction());
     333    auto* heapData = m_heapItem->timerHeap().data();
     334    push_heap(TimerHeapIterator(heapData), TimerHeapIterator(heapData + m_heapItem->heapIndex() + 1), TimerHeapLessThanFunction());
    270335    checkHeapIndex();
    271336}
    … …  
    273338inline void TimerBase::heapDelete()
    274339{
    275     ASSERT(!static_cast<bool>(m_nextFireTime));
     340    ASSERT(!static_cast<bool>(nextFireTime()));
    276341    heapPop();
    277     timerHeap().removeLast();
    278     m_heapIndex = -1;
     342    m_heapItem->timerHeap().removeLast();
     343    m_heapItem->setNotInHeap();
    279344}
    280345
    281346void TimerBase::heapDeleteMin()
    282347{
    283     ASSERT(!static_cast<bool>(m_nextFireTime));
     348    ASSERT(!static_cast<bool>(nextFireTime()));
    284349    heapPopMin();
    285     timerHeap().removeLast();
    286     m_heapIndex = -1;
     350    m_heapItem->timerHeap().removeLast();
     351    m_heapItem->setNotInHeap();
    287352}
    288353
    289354inline void TimerBase::heapIncreaseKey()
    290355{
    291     ASSERT(static_cast<bool>(m_nextFireTime));
     356    ASSERT(static_cast<bool>(nextFireTime()));
    292357    heapPop();
    293358    heapDecreaseKey();
    … …  
    297362{
    298363    ASSERT(!inHeap());
    299     timerHeap().append(this);
    300     m_heapIndex = timerHeap().size() - 1;
     364    ASSERT(m_heapItem);
     365    auto& heap = m_heapItem->timerHeap();
     366    heap.append(m_heapItem.copyRef());
     367    m_heapItem->setHeapIndex(heap.size() - 1);
    301368    heapDecreaseKey();
    302369}
    … …  
    304371inline void TimerBase::heapPop()
    305372{
     373    ASSERT(m_heapItem);
    306374    // Temporarily force this timer to have the minimum key so we can pop it.
    307     MonotonicTime fireTime = m_nextFireTime;
    308     m_nextFireTime = -MonotonicTime::infinity();
     375    MonotonicTime fireTime = m_heapItem->time;
     376    m_heapItem->time = -MonotonicTime::infinity();
    309377    heapDecreaseKey();
    310378    heapPopMin();
    311     m_nextFireTime = fireTime;
     379    m_heapItem->time = fireTime;
    312380}
    313381
    314382void TimerBase::heapPopMin()
    315383{
    316     ASSERT(this == timerHeap().first());
     384    ASSERT(m_heapItem == m_heapItem->timerHeap().first());
    317385    checkHeapIndex();
    318     Vector<TimerBase*>& heap = timerHeap();
    319     TimerBase** heapData = heap.data();
     386    auto& heap = m_heapItem->timerHeap();
     387    auto* heapData = heap.data();
    320388    pop_heap(TimerHeapIterator(heapData), TimerHeapIterator(heapData + heap.size()), TimerHeapLessThanFunction());
    321389    checkHeapIndex();
    322     ASSERT(this == timerHeap().last());
    323 }
    324 
    325 static inline bool parentHeapPropertyHolds(const TimerBase* current, const Vector<TimerBase*>& heap, unsigned currentIndex)
     390    ASSERT(m_heapItem == m_heapItem->timerHeap().last());
     391}
     392
     393void TimerBase::heapDeleteNullMin(ThreadTimerHeap& heap)
     394{
     395    RELEASE_ASSERT(!heap.first()->hasTimer());
     396    heap.first()->time = -MonotonicTime::infinity();
     397    auto* heapData = heap.data();
     398    pop_heap(TimerHeapIterator(heapData), TimerHeapIterator(heapData + heap.size()), TimerHeapLessThanFunction());
     399    heap.removeLast();
     400}
     401
     402static inline bool parentHeapPropertyHolds(const TimerBase* current, const ThreadTimerHeap& heap, unsigned currentIndex)
    326403{
    327404    if (!currentIndex)
    328405        return true;
    329406    unsigned parentIndex = (currentIndex - 1) / 2;
    330     TimerHeapLessThanFunction compareHeapPosition;
    331     return compareHeapPosition(current, heap[parentIndex]);
    332 }
    333 
    334 static inline bool childHeapPropertyHolds(const TimerBase* current, const Vector<TimerBase*>& heap, unsigned childIndex)
     407    return TimerHeapLessThanFunction::compare(*current, heap[parentIndex]);
     408}
     409
     410static inline bool childHeapPropertyHolds(const TimerBase* current, const ThreadTimerHeap& heap, unsigned childIndex)
    335411{
    336412    if (childIndex >= heap.size())
    337413        return true;
    338     TimerHeapLessThanFunction compareHeapPosition;
    339     return compareHeapPosition(heap[childIndex], current);
     414    return TimerHeapLessThanFunction::compare(heap[childIndex], *current);
    340415}
    341416
    342417bool TimerBase::hasValidHeapPosition() const
    343418{
    344     ASSERT(m_nextFireTime);
     419    ASSERT(nextFireTime());
     420    ASSERT(m_heapItem);
    345421    if (!inHeap())
    346422        return false;
    … …  
    348424    // This assumes that the STL heap is a standard binary heap. In an unlikely event it is not, the assertions
    349425    // in updateHeapIfNeeded() will get hit.
    350     const Vector<TimerBase*>& heap = timerHeap();
    351     if (!parentHeapPropertyHolds(this, heap, m_heapIndex))
     426    const auto& heap = m_heapItem->timerHeap();
     427    unsigned heapIndex = m_heapItem->heapIndex();
     428    if (!parentHeapPropertyHolds(this, heap, heapIndex))
    352429        return false;
    353     unsigned childIndex1 = 2 * m_heapIndex + 1;
     430    unsigned childIndex1 = 2 * heapIndex + 1;
    354431    unsigned childIndex2 = childIndex1 + 1;
    355432    return childHeapPropertyHolds(this, heap, childIndex1) && childHeapPropertyHolds(this, heap, childIndex2);
    … …  
    358435void TimerBase::updateHeapIfNeeded(MonotonicTime oldTime)
    359436{
    360     if (m_nextFireTime && hasValidHeapPosition())
     437    auto fireTime = nextFireTime();
     438    if (fireTime && hasValidHeapPosition())
    361439        return;
    362 #ifndef NDEBUG
    363     int oldHeapIndex = m_heapIndex;
     440
     441#if !ASSERT_DISABLED
     442    Optional<unsigned> oldHeapIndex;
     443    if (m_heapItem->isInHeap())
     444        oldHeapIndex = m_heapItem->heapIndex();
    364445#endif
     446
    365447    if (!oldTime)
    366448        heapInsert();
    367     else if (!m_nextFireTime)
     449    else if (!fireTime)
    368450        heapDelete();
    369     else if (m_nextFireTime < oldTime)
     451    else if (fireTime < oldTime)
    370452        heapDecreaseKey();
    371453    else
    372454        heapIncreaseKey();
    373     ASSERT(m_heapIndex != oldHeapIndex);
     455
     456#if !ASSERT_DISABLED
     457    Optional<unsigned> newHeapIndex;
     458    if (m_heapItem->isInHeap())
     459        newHeapIndex = m_heapItem->heapIndex();
     460    ASSERT(newHeapIndex != oldHeapIndex);
     461#endif
     462
    374463    ASSERT(!inHeap() || hasValidHeapPosition());
    375464}
    … …  
    384473        m_unalignedNextFireTime = newTime;
    385474
    386     // Accessing thread global data is slow. Cache the heap pointer.
    387     if (!m_cachedThreadGlobalTimerHeap)
    388         m_cachedThreadGlobalTimerHeap = &threadGlobalTimerHeap();
    389 
    390475    // Keep heap valid while changing the next-fire time.
    391     MonotonicTime oldTime = m_nextFireTime;
     476    MonotonicTime oldTime = nextFireTime();
    392477    // Don't realign zero-delay timers.
    393478    if (newTime) {
    … …  
    397482
    398483    if (oldTime != newTime) {
    399         m_nextFireTime = newTime;
    400484        // FIXME: This should be part of ThreadTimers, or another per-thread structure.
    401485        static std::atomic<unsigned> currentHeapInsertionOrder;
    402         m_heapInsertionOrder = currentHeapInsertionOrder++;
    403 
    404         bool wasFirstTimerInHeap = m_heapIndex == 0;
     486        auto newOrder = currentHeapInsertionOrder++;
     487
     488        if (!m_heapItem)
     489            m_heapItem = ThreadTimerHeapItem::create(*this, newTime, 0);
     490        m_heapItem->time = newTime;
     491        m_heapItem->insertionOrder = newOrder;
     492
     493        bool wasFirstTimerInHeap = m_heapItem->isFirstInHeap();
    405494
    406495        updateHeapIfNeeded(oldTime);
    407496
    408         bool isFirstTimerInHeap = m_heapIndex == 0;
     497        bool isFirstTimerInHeap = m_heapItem->isFirstInHeap();
    409498
    410499        if (wasFirstTimerInHeap || isFirstTimerInHeap)

  • trunk/Source/WebCore/platform/Timer.h

    r239427 r239814  
    2626#pragma once
    2727
     28#include "ThreadTimers.h"
    2829#include <functional>
    2930#include <wtf/Function.h>
    … …  
    3435#include <wtf/Threading.h>
    3536#include <wtf/Vector.h>
     37#include <wtf/WeakPtr.h>
    3638
    3739#if PLATFORM(IOS_FAMILY)
    … …  
    4042
    4143namespace WebCore {
    42 
    43 // Time intervals are all in seconds.
    44 
    45 class TimerHeapElement;
    4644
    4745class TimerBase {
    … …  
    6462    Seconds repeatInterval() const { return m_repeatInterval; }
    6563
    66     void augmentFireInterval(Seconds delta) { setNextFireTime(m_nextFireTime + delta); }
     64    void augmentFireInterval(Seconds delta) { setNextFireTime(m_heapItem->time + delta); }
    6765    void augmentRepeatInterval(Seconds delta) { augmentFireInterval(delta); m_repeatInterval += delta; }
    6866
    … …  
    8179    void setNextFireTime(MonotonicTime);
    8280
    83     bool inHeap() const { return m_heapIndex != -1; }
     81    bool inHeap() const { return m_heapItem && m_heapItem->isInHeap(); }
    8482
    8583    bool hasValidHeapPosition() const;
    … …  
    9391    void heapPop();
    9492    void heapPopMin();
     93    static void heapDeleteNullMin(ThreadTimerHeap&);
    9594
    96     Vector<TimerBase*>& timerHeap() const { ASSERT(m_cachedThreadGlobalTimerHeap); return *m_cachedThreadGlobalTimerHeap; }
     95    MonotonicTime nextFireTime() const { return m_heapItem ? m_heapItem->time : MonotonicTime { }; }
    9796
    98     MonotonicTime m_nextFireTime; // 0 if inactive
    9997    MonotonicTime m_unalignedNextFireTime; // m_nextFireTime not considering alignment interval
    10098    Seconds m_repeatInterval; // 0 if not repeating
    101     signed int m_heapIndex : 31; // -1 if not in heap
    102     bool m_wasDeleted : 1;
    103     unsigned m_heapInsertionOrder; // Used to keep order among equal-fire-time timers
    104     Vector<TimerBase*>* m_cachedThreadGlobalTimerHeap { nullptr };
     99    bool m_wasDeleted { false };
    105100
     101    RefPtr<ThreadTimerHeapItem> m_heapItem;
    106102    Ref<Thread> m_thread { Thread::current() };
    107103
    … …  
    143139    ASSERT(WebThreadIsCurrent() || pthread_main_np() || m_thread.ptr() == &Thread::current());
    144140#endif // PLATFORM(IOS_FAMILY)
    145     return static_cast<bool>(m_nextFireTime);
     141    return static_cast<bool>(nextFireTime());
    146142}
    147143
Note: See TracChangeset for help on using the changeset viewer.