Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1428)

Unified Diff: Source/platform/Timer.cpp

Issue 1134523002: Implement timers by posting delayed tasks (Closed) Base URL: svn://svn.chromium.org/blink/trunk
Patch Set: Gyp tweak. Created 5 years, 7 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
Index: Source/platform/Timer.cpp
diff --git a/Source/platform/Timer.cpp b/Source/platform/Timer.cpp
index 6a2111200a0957f6e6af3c7fda62a2a966ecb9ce..0772050d12e33f7b86de393ebedb5fb479dc8382 100644
--- a/Source/platform/Timer.cpp
+++ b/Source/platform/Timer.cpp
@@ -27,8 +27,9 @@
#include "config.h"
#include "platform/Timer.h"
-#include "platform/PlatformThreadData.h"
-#include "platform/ThreadTimers.h"
+#include "platform/TraceEvent.h"
+#include "public/platform/Platform.h"
+#include "public/platform/WebScheduler.h"
#include "wtf/Atomics.h"
#include "wtf/CurrentTime.h"
#include "wtf/HashSet.h"
@@ -39,158 +40,12 @@
namespace blink {
-class TimerHeapReference;
-
-// 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.
-static Vector<TimerBase*>& threadGlobalTimerHeap()
-{
- return PlatformThreadData::current().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;
- Vector<TimerBase*>& heap = timer->timerHeap();
- if (&m_reference >= heap.data() && &m_reference < heap.data() + heap.size())
- timer->m_heapIndex = &m_reference - 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 >= threadGlobalTimerHeap().data());
- ASSERT(m_pointer <= threadGlobalTimerHeap().data() + threadGlobalTimerHeap().size());
- ASSERT_UNUSED(offset, m_pointer + offset >= threadGlobalTimerHeap().data());
- ASSERT_UNUSED(offset, m_pointer + offset <= threadGlobalTimerHeap().data() + threadGlobalTimerHeap().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 largest
- // element first and we want the lowest time to be the first one in the heap.
- double aFireTime = a->m_nextFireTime;
- double 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;
-}
-
-// ----------------
-
TimerBase::TimerBase()
: m_nextFireTime(0)
, m_unalignedNextFireTime(0)
, m_repeatInterval(0)
- , m_heapIndex(-1)
- , m_cachedThreadGlobalTimerHeap(0)
+ , m_cancellableTaskFactory(WTF::bind(&TimerBase::run, this))
+ , m_webScheduler(Platform::current()->currentThread()->scheduler())
#if ENABLE(ASSERT)
, m_thread(currentThread())
#endif
@@ -200,7 +55,6 @@ TimerBase::TimerBase()
TimerBase::~TimerBase()
{
stop();
- ASSERT(!inHeap());
}
void TimerBase::start(double nextFireInterval, double repeatInterval, const WebTraceLocation& caller)
@@ -209,7 +63,7 @@ void TimerBase::start(double nextFireInterval, double repeatInterval, const WebT
m_location = caller;
m_repeatInterval = repeatInterval;
- setNextFireTime(monotonicallyIncreasingTime() + nextFireInterval);
+ setNextFireTime(monotonicallyIncreasingTime(), nextFireInterval);
}
void TimerBase::stop()
@@ -217,11 +71,8 @@ void TimerBase::stop()
ASSERT(m_thread == currentThread());
m_repeatInterval = 0;
- setNextFireTime(0);
-
- ASSERT(m_nextFireTime == 0);
- ASSERT(m_repeatInterval == 0);
- ASSERT(!inHeap());
+ m_nextFireTime = 0;
+ m_cancellableTaskFactory.cancel();
}
double TimerBase::nextFireInterval() const
@@ -233,171 +84,42 @@ double TimerBase::nextFireInterval() const
return m_nextFireTime - 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);
-}
-
-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() == (m_nextFireTime != 0));
- if (inHeap())
- checkHeapIndex();
-}
-
-void TimerBase::heapDecreaseKey()
-{
- ASSERT(m_nextFireTime != 0);
- checkHeapIndex();
- TimerBase** heapData = timerHeap().data();
- push_heap(TimerHeapIterator(heapData), TimerHeapIterator(heapData + m_heapIndex + 1), TimerHeapLessThanFunction());
- checkHeapIndex();
-}
-
-inline void TimerBase::heapDelete()
-{
- ASSERT(m_nextFireTime == 0);
- heapPop();
- timerHeap().removeLast();
- m_heapIndex = -1;
-}
-
-void TimerBase::heapDeleteMin()
-{
- ASSERT(m_nextFireTime == 0);
- heapPopMin();
- timerHeap().removeLast();
- m_heapIndex = -1;
-}
-
-inline void TimerBase::heapIncreaseKey()
-{
- ASSERT(m_nextFireTime != 0);
- heapPop();
- heapDecreaseKey();
-}
-
-inline void TimerBase::heapInsert()
-{
- ASSERT(!inHeap());
- timerHeap().append(this);
- m_heapIndex = timerHeap().size() - 1;
- heapDecreaseKey();
-}
-
-inline void TimerBase::heapPop()
-{
- // Temporarily force this timer to have the minimum key so we can pop it.
- double fireTime = m_nextFireTime;
- m_nextFireTime = -std::numeric_limits<double>::infinity();
- heapDecreaseKey();
- heapPopMin();
- m_nextFireTime = fireTime;
-}
-
-void TimerBase::heapPopMin()
-{
- ASSERT(this == timerHeap().first());
- checkHeapIndex();
- Vector<TimerBase*>& heap = timerHeap();
- TimerBase** heapData = heap.data();
- pop_heap(TimerHeapIterator(heapData), TimerHeapIterator(heapData + heap.size()), TimerHeapLessThanFunction());
- checkHeapIndex();
- ASSERT(this == timerHeap().last());
-}
-
-static inline bool parentHeapPropertyHolds(const TimerBase* current, const Vector<TimerBase*>& heap, unsigned currentIndex)
-{
- if (!currentIndex)
- return true;
- unsigned parentIndex = (currentIndex - 1) / 2;
- TimerHeapLessThanFunction compareHeapPosition;
- return compareHeapPosition(current, heap[parentIndex]);
-}
-
-static inline bool childHeapPropertyHolds(const TimerBase* current, const Vector<TimerBase*>& heap, unsigned childIndex)
-{
- if (childIndex >= heap.size())
- return true;
- TimerHeapLessThanFunction compareHeapPosition;
- return compareHeapPosition(heap[childIndex], current);
-}
-
-bool TimerBase::hasValidHeapPosition() const
-{
- ASSERT(m_nextFireTime);
- 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))
- return false;
- unsigned childIndex1 = 2 * m_heapIndex + 1;
- unsigned childIndex2 = childIndex1 + 1;
- return childHeapPropertyHolds(this, heap, childIndex1) && childHeapPropertyHolds(this, heap, childIndex2);
-}
-
-void TimerBase::updateHeapIfNeeded(double oldTime)
-{
- if (m_nextFireTime && hasValidHeapPosition())
- return;
-#if ENABLE(ASSERT)
- int oldHeapIndex = m_heapIndex;
-#endif
- if (!oldTime)
- heapInsert();
- else if (!m_nextFireTime)
- heapDelete();
- else if (m_nextFireTime < oldTime)
- heapDecreaseKey();
- else
- heapIncreaseKey();
- ASSERT(m_heapIndex != oldHeapIndex);
- ASSERT(!inHeap() || hasValidHeapPosition());
-}
-
-void TimerBase::setNextFireTime(double newUnalignedTime)
+void TimerBase::setNextFireTime(double now, double delay)
{
ASSERT(m_thread == currentThread());
- if (m_unalignedNextFireTime != newUnalignedTime)
- m_unalignedNextFireTime = newUnalignedTime;
+ m_unalignedNextFireTime = now + delay;
- // 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.
- double oldTime = m_nextFireTime;
- double newTime = alignedFireTime(newUnalignedTime);
- if (oldTime != newTime) {
+ double newTime = alignedFireTime(m_unalignedNextFireTime);
+ if (m_nextFireTime != newTime) {
m_nextFireTime = newTime;
- static unsigned currentHeapInsertionOrder;
- m_heapInsertionOrder = atomicAdd(&currentHeapInsertionOrder, 1);
-
- bool wasFirstTimerInHeap = m_heapIndex == 0;
-
- updateHeapIfNeeded(oldTime);
-
- bool isFirstTimerInHeap = m_heapIndex == 0;
-
- if (wasFirstTimerInHeap || isFirstTimerInHeap)
- PlatformThreadData::current().threadTimers().updateSharedTimer();
+ // Round the delay up to the nearest millisecond to be consistant with the
+ // previous behavior of BlinkPlatformImpl::setSharedTimerFireInterval.
+ long long delayMs = static_cast<long long>(ceil((newTime - now) * 1000.0));
+ if (delayMs < 0)
+ delayMs = 0;
+ m_webScheduler->postTimerTask(m_location, m_cancellableTaskFactory.task(), delayMs);
kinuko 2015/05/13 08:26:39 Just want to make sure-- so this one actually canc
alex clarke (OOO till 29th) 2015/05/13 08:43:01 Yes it does. We where thinking of changing the nam
Sami 2015/05/13 18:01:26 We could consider introducing a non-thread safe va
}
+}
+
+void TimerBase::run()
+{
+ TRACE_EVENT0("blink", "TimerBase::run");
+ ASSERT_WITH_MESSAGE(m_thread == currentThread(), "Timer posted by %s %s was run on a different thread", m_location.functionName(), m_location.fileName());
+ TRACE_EVENT_SET_SAMPLING_STATE("blink", "BlinkInternal");
- checkConsistency();
+ m_nextFireTime = 0;
+ // Note: repeating timers drift, but this is preserving the functionality of the old timer heap.
+ // See crbug.com/328700.
+ if (m_repeatInterval)
+ setNextFireTime(monotonicallyIncreasingTime(), m_repeatInterval);
+ fired();
+ TRACE_EVENT_SET_SAMPLING_STATE("blink", "Sleeping");
}
-void TimerBase::didChangeAlignmentInterval()
+void TimerBase::didChangeAlignmentInterval(double now)
{
- setNextFireTime(m_unalignedNextFireTime);
+ setNextFireTime(now, m_unalignedNextFireTime - now);
}
double TimerBase::nextUnalignedFireInterval() const

Powered by Google App Engine
This is Rietveld 408576698