WIP - not ready for review

Source/platform/TimerHeap.cpp

+// Copyright 2015 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "config.h"
+#include "platform/TimerHeap.h"
+
+#include "platform/PlatformThreadData.h"
+#include "platform/ThreadTimers.h"
+#include "platform/Timer.h"
+#include <limits.h>
+#include <limits>
+#include <math.h>
+
+namespace blink {
+
+class TimerHeapReference;
+
+TimerQueueObserver::TimerQueueObserver()
+{
+}
+
+TimerQueueObserver::~TimerQueueObserver()
+{
+}
+
+ThreadTimers& threadTimers()
+{
+    return PlatformThreadData::current().threadTimers();
+}
+
+// Timers are stored in a heap data structure, used to implement a
+// priority queue.  This allows us to efficiently determine which
+// timer needs to fire the soonest.  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.
+TimerHeap& TimerHeap::get()
+{
+    return threadTimers().timerHeap();
+}
+
+class TimerHeapPointer {
+public:
+    TimerHeapPointer(TimerBase** pointer)
+        : m_pointer(pointer)
+    {
+    }
+    TimerHeapReference operator*() const;
+    TimerBase* operator->() const { return *m_pointer; }
+
+private:
+    TimerBase** m_pointer;
+};
+
+class TimerHeapReference {
+public:
+    TimerHeapReference(TimerBase*& reference)
+        : m_reference(reference)
+    {
+    }
+    operator TimerBase*() const { return m_reference; }
+    TimerHeapPointer operator&() const { return &m_reference; }
+    TimerHeapReference& operator=(TimerBase*);
+    TimerHeapReference& operator=(TimerHeapReference);
+
+private:
+    TimerBase*& m_reference;
+};
+
+inline TimerHeapReference TimerHeapPointer::operator*() const
+{
+    return *m_pointer;
+}
+
+inline TimerHeapReference& TimerHeapReference::operator=(TimerBase* timer)
+{
+    m_reference = timer;
+    TimerHeapEntry& entry = timer->heapEntry();
+    ASSERT_WITH_SECURITY_IMPLICATION(entry.m_owner->m_heap.data() <= &m_reference && &m_reference < entry.m_owner->m_heap.data() + entry.m_owner->m_heap.size());
+    entry.m_heapIndex = &m_reference - entry.m_owner->m_heap.data();
+    return *this;
+}
+
+inline TimerHeapReference& TimerHeapReference::operator=(TimerHeapReference b)
+{
+    TimerBase* timer = b;
+    return * this = timer;
+}
+
+inline void swap(TimerHeapReference a, TimerHeapReference b)
+{
+    TimerBase* timerA = a;
+    TimerBase* timerB = b;
+
+    // Invoke the assignment operator, since that takes care of
+    // updating m_heapIndex.
+    a = timerB;
+    b = timerA;
+}
+
+// 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> {
+public:
+    explicit TimerHeapIterator(TimerBase** 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--);
+    }
+
+    TimerHeapIterator& operator+=(ptrdiff_t i)
+    {
+        checkConsistency();
+        m_pointer += i;
+        checkConsistency();
+        return *this;
+    }
+    TimerHeapIterator& operator-=(ptrdiff_t i)
+    {
+        checkConsistency();
+        m_pointer -= i;
+        checkConsistency();
+        return *this;
+    }
+
+    TimerHeapReference operator*() const { return TimerHeapReference(*m_pointer); }
+    TimerHeapReference operator[](ptrdiff_t i) const { return TimerHeapReference(m_pointer[i]); }
+    TimerBase* operator->() const { return *m_pointer; }
+
+private:
+    void checkConsistency(ptrdiff_t offset = 0) const
+    {
+        ASSERT(m_pointer >= TimerHeap::get().m_heap.data());
+        ASSERT(m_pointer <= TimerHeap::get().m_heap.data() + TimerHeap::get().m_heap.size());
+        ASSERT_UNUSED(offset, m_pointer + offset >= TimerHeap::get().m_heap.data());
+        ASSERT_UNUSED(offset, m_pointer + offset <= TimerHeap::get().m_heap.data() + TimerHeap::get().m_heap.size());
+    }
+
+    friend bool operator==(TimerHeapIterator, TimerHeapIterator);
+    friend bool operator!=(TimerHeapIterator, TimerHeapIterator);
+    friend bool operator<(TimerHeapIterator, TimerHeapIterator);
+    friend bool operator>(TimerHeapIterator, TimerHeapIterator);
+    friend bool operator<=(TimerHeapIterator, TimerHeapIterator);
+    friend bool operator>=(TimerHeapIterator, TimerHeapIterator);
+
+    friend TimerHeapIterator operator+(TimerHeapIterator, size_t);
+    friend TimerHeapIterator operator+(size_t, TimerHeapIterator);
+
+    friend TimerHeapIterator operator-(TimerHeapIterator, size_t);
+    friend ptrdiff_t operator-(TimerHeapIterator, TimerHeapIterator);
+
+    TimerBase** 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; }
+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; }
+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; }
+
+inline TimerHeapIterator operator+(TimerHeapIterator a, size_t b) { return TimerHeapIterator(a.m_pointer + b); }
+inline TimerHeapIterator operator+(size_t a, TimerHeapIterator b) { return TimerHeapIterator(a + b.m_pointer); }
+
+inline TimerHeapIterator operator-(TimerHeapIterator a, size_t b) { return TimerHeapIterator(a.m_pointer - b); }
+inline ptrdiff_t operator-(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer - b.m_pointer; }
+
+class TimerHeapLessThanFunction {
+public:
+    bool operator()(const TimerBase*, const TimerBase*) const;
+};
+
+inline bool TimerHeapLessThanFunction::operator()(const TimerBase* a, const TimerBase* b) const
+{
+    // The comparisons below are "backwards" because the heap puts the
+    // greatest element first but we want the lowest time to be the
+    // first one in the heap.
+
+    // Check if one of the values has the "forced minumum for popping"
+    // value. Only one entry can be popped at once, so only one entry
+    // can have the special value at once.
+    if (a->heapEntry().m_state == TimerHeapEntry::TimerHeapEntryInHeap_ForcedMinimumForPopping) {
+        ASSERT(a == b || b->heapEntry().m_state == TimerHeapEntry::TimerHeapEntryInHeap);
+        return false;
+    }
+    if (b->heapEntry().m_state == TimerHeapEntry::TimerHeapEntryInHeap_ForcedMinimumForPopping) {
+        ASSERT(a == b || a->heapEntry().m_state == TimerHeapEntry::TimerHeapEntryInHeap);
+        return true;
+    }
+
+    double aFireTime = a->heapEntry().value();
+    double bFireTime = b->heapEntry().value();
+    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->heapEntry().m_heapInsertionOrder - b->heapEntry().m_heapInsertionOrder;
+    return difference < std::numeric_limits<unsigned>::max() / 2;
+}
+
+TimerBase* TimerHeap::first() const
+{
+    ASSERT(currentThread() == m_thread);
+    return m_heap.first();
+}
+
+bool TimerHeap::isEmpty() const
+{
+    ASSERT(currentThread() == m_thread);
+    return m_heap.isEmpty();
+}
+
+void TimerHeap::pop(TimerBase* timer)
+{
+    // Temporarily force this timer to have the minimum key so we can pop it.
+    TimerHeapEntry& entry = timer->heapEntry();
+    ASSERT(entry.inHeap());
+    entry.m_state = TimerHeapEntry::TimerHeapEntryInHeap_ForcedMinimumForPopping;
+    didDecreaseKey(timer);
+
+    ASSERT(timer == m_heap.first());
+    TimerBase** heapData = m_heap.data();
+    pop_heap(TimerHeapIterator(heapData), TimerHeapIterator(heapData + m_heap.size()), TimerHeapLessThanFunction());
+    ASSERT(timer == m_heap.last());
+}
+
+void TimerHeap::remove(TimerBase* timer)
+{
+    TimerHeapEntry& entry = timer->heapEntry();
+    ASSERT(this == entry.m_owner);
+    ASSERT(timer->nextFireTime() == 0);
+
+    pop(timer);
+    m_heap.removeLast();
+
+    HashSet<TimerBase*>::iterator it = m_entries.find(timer);
+    ASSERT(it != m_entries.end());
+    m_entries.remove(it);
+
+    entry.m_state = TimerHeapEntry::TimerHeapEntryNotInHeap;
+    entry.m_heapIndex = std::numeric_limits<std::size_t>::max();
+
+    check();
+}
+
+void TimerHeap::didDecreaseKey(TimerBase* timer)
+{
+    TimerHeapEntry& entry = timer->heapEntry();
+    ASSERT(this == entry.m_owner);
+    TimerBase** heapData = m_heap.data();
+    push_heap(TimerHeapIterator(heapData), TimerHeapIterator(heapData + entry.m_heapIndex + 1), TimerHeapLessThanFunction());
+}
+
+void TimerHeap::didIncreaseKey(TimerBase* timer)
+{
+    pop(timer);
+    timer->heapEntry().m_state = TimerHeapEntry::TimerHeapEntryInHeap;
+    didDecreaseKey(timer);
+}
+
+void TimerHeap::insert(TimerBase* timer)
+{
+    TimerHeapEntry& entry = timer->heapEntry();
+    ASSERT(this == entry.m_owner);
+    ASSERT(!entry.inHeap());
+
+    entry.m_heapInsertionOrder = m_currentHeapInsertionOrder++;
+    entry.m_heapIndex = m_heap.size();
+    entry.m_state = TimerHeapEntry::TimerHeapEntryInHeap;
+
+    m_heap.append(timer);
+
+    HashSet<TimerBase*>::AddResult result = m_entries.add(timer);
+    ASSERT(result.isNewEntry);
+
+    didDecreaseKey(timer);
+
+    check(entry);
+}
+
+bool TimerHeap::hasValidHeapPosition(const TimerHeapEntry& entry) const
+{
+    ASSERT(currentThread() == m_thread);
+    ASSERT(this == entry.m_owner);
+    if (!entry.inHeap())
+        return false;
+#if ENABLE(ASSERT)
+    TimerBase* timer = m_heap[entry.m_heapIndex];
+#endif
+    ASSERT(&timer->heapEntry() == &entry);
+    ASSERT(m_entries.find(timer) != m_entries.end());
+    if (!parentHeapPropertyHolds(entry))
+        return false;
+    unsigned childIndex1 = 2 * entry.m_heapIndex + 1;
+    unsigned childIndex2 = childIndex1 + 1;
+    return childHeapPropertyHolds(entry, childIndex1) && childHeapPropertyHolds(entry, childIndex2);
+}
+
+bool TimerHeap::parentHeapPropertyHolds(const TimerHeapEntry& current) const
+{
+    ASSERT(current.inHeap());
+    if (current.m_heapIndex == 0)
+        return true; // This is the root of the heap.
+    unsigned parentIndex = (current.m_heapIndex - 1) / 2;
+    TimerHeapLessThanFunction compareHeapPosition;
+    return compareHeapPosition(m_heap[current.m_heapIndex], m_heap[parentIndex]);
+}
+
+bool TimerHeap::childHeapPropertyHolds(const TimerHeapEntry& current, size_t childIndex) const
+{
+    ASSERT(current.inHeap());
+    if (childIndex >= m_heap.size())
+        return true; // This is a leaf.
+    TimerHeapLessThanFunction compareHeapPosition;
+    return compareHeapPosition(m_heap[childIndex], m_heap[current.m_heapIndex]);
+}
+
+void TimerHeap::check() const
+{
+    ASSERT_WITH_SECURITY_IMPLICATION(m_entries.size() == m_heap.size());
+    for (HashSet<TimerBase*>::const_iterator it = m_entries.begin(); it != m_entries.end(); ++it) {
+        check((*it)->heapEntry());
+    }
+}
+
+void TimerHeap::check(const TimerHeapEntry& entry) const
+{
+    // Is the entry associated with the right heap.
+    ASSERT_WITH_SECURITY_IMPLICATION(this == entry.m_owner);
+
+    // The "forced minimum for popping" state should only exist transiently.
+    ASSERT_WITH_SECURITY_IMPLICATION(entry.m_state != TimerHeapEntry::TimerHeapEntryInHeap_ForcedMinimumForPopping);
+
+    // Sanity-check the heap index.
+    ASSERT_WITH_SECURITY_IMPLICATION(!entry.inHeap() || entry.m_heapIndex < m_heap.size());
+
+    // If in the heap, is the heap index accurate?
+    ASSERT_WITH_SECURITY_IMPLICATION(!entry.inHeap() || &m_heap[entry.m_heapIndex]->heapEntry() == &entry);
+
+    // Timers should be in the heap if and only if they have a
+    // non-zero next fire time.
+    ASSERT_WITH_SECURITY_IMPLICATION(!entry.inHeap() || (entry.value() != 0));
+
+    ASSERT_WITH_SECURITY_IMPLICATION(!entry.inHeap() || hasValidHeapPosition(entry));
+}
+
+void TimerHeap::didChangeValue(TimerBase& timer, double oldValue)
+{
+    ASSERT(currentThread() == m_thread);
+
+    TimerHeapEntry& entry = timer.heapEntry();
+    if (entry.value() && hasValidHeapPosition(entry))
+        return;
+    bool wasInHeap = entry.inHeap();
+    size_t oldHeapIndex = entry.m_heapIndex;
+    bool wasFirstInHeap = wasInHeap && oldHeapIndex == 0;
+    if (!oldValue)
+        insert(&timer);
+    else if (!entry.value())
+        remove(&timer);
+    else if (entry.value() < oldValue)
+        didDecreaseKey(&timer);
+    else
+        didIncreaseKey(&timer);
+    ASSERT(wasInHeap != entry.inHeap() || entry.m_heapIndex != oldHeapIndex);
+    check(entry);
+
+    bool isFirstInHeap = entry.inHeap() && entry.m_heapIndex == 0;
+    if (m_observer && (wasFirstInHeap || isFirstInHeap))
+        m_observer->nextFiringTimerChanged();
+}
+
+TimerHeap::TimerHeap(TimerQueueObserver* observer)
+    : m_observer(observer)
+    , m_thread(currentThread())
+    , m_currentHeapInsertionOrder(0)
+{
+}
+
+TimerHeap::~TimerHeap()
+{
+    ASSERT(currentThread() == m_thread);
+}
+
+} // namespace blink