src/third_party/WebKit/Source/platform/Timer.cpp

   1 /*
   2  * Copyright (C) 2006, 2008 Apple Inc. All rights reserved.
   3  * Copyright (C) 2009 Google Inc. All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
  15  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
  18  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  19  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  20  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  21  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  22  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  24  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25  */
  26
  27 #include "config.h"
  28 #include "platform/Timer.h"
  29
  30 #include "platform/PlatformThreadData.h"
  31 #include "platform/ThreadTimers.h"
  32 #include "wtf/CurrentTime.h"
  33 #include "wtf/HashSet.h"
  34 #include <limits.h>
  35 #include <math.h>
  36 #include <limits>
  37
  38 namespace blink {
  39
  40 class TimerHeapReference;
  41
  42 // Timers are stored in a heap data structure, used to implement a priority queue.
  43 // This allows us to efficiently determine which timer needs to fire the soonest.
  44 // Then we set a single shared system timer to fire at that time.
  45 //
  46 // When a timer's "next fire time" changes, we need to move it around in the priority queue.
  47 static Vector<TimerBase*>& threadGlobalTimerHeap()
  48 {
  49     return PlatformThreadData::current().threadTimers().timerHeap();
  50 }
  51 // ----------------
  52
  53 class TimerHeapPointer {
  54 public:
  55     TimerHeapPointer(TimerBase** pointer) : m_pointer(pointer) { }
  56     TimerHeapReference operator*() const;
  57     TimerBase* operator->() const { return *m_pointer; }
  58 private:
  59     TimerBase** m_pointer;
  60 };
  61
  62 class TimerHeapReference {
  63 public:
  64     TimerHeapReference(TimerBase*& reference) : m_reference(reference) { }
  65     operator TimerBase*() const { return m_reference; }
  66     TimerHeapPointer operator&() const { return &m_reference; }
  67     TimerHeapReference& operator=(TimerBase*);
  68     TimerHeapReference& operator=(TimerHeapReference);
  69 private:
  70     TimerBase*& m_reference;
  71 };
  72
  73 inline TimerHeapReference TimerHeapPointer::operator*() const
  74 {
  75     return *m_pointer;
  76 }
  77
  78 inline TimerHeapReference& TimerHeapReference::operator=(TimerBase* timer)
  79 {
  80     m_reference = timer;
  81     Vector<TimerBase*>& heap = timer->timerHeap();
  82     if (&m_reference >= heap.data() && &m_reference < heap.data() + heap.size())
  83         timer->m_heapIndex = &m_reference - heap.data();
  84     return *this;
  85 }
  86
  87 inline TimerHeapReference& TimerHeapReference::operator=(TimerHeapReference b)
  88 {
  89     TimerBase* timer = b;
  90     return *this = timer;
  91 }
  92
  93 inline void swap(TimerHeapReference a, TimerHeapReference b)
  94 {
  95     TimerBase* timerA = a;
  96     TimerBase* timerB = b;
  97
  98     // Invoke the assignment operator, since that takes care of updating m_heapIndex.
  99     a = timerB;
 100     b = timerA;
 101 }
 102
 103 // ----------------
 104
 105 // Class to represent iterators in the heap when calling the standard library heap algorithms.
 106 // Uses a custom pointer and reference type that update indices for pointers in the heap.
 107 class TimerHeapIterator : public std::iterator<std::random_access_iterator_tag, TimerBase*, ptrdiff_t, TimerHeapPointer, TimerHeapReference> {
 108 public:
 109     explicit TimerHeapIterator(TimerBase** pointer) : m_pointer(pointer) { checkConsistency(); }
 110
 111     TimerHeapIterator& operator++() { checkConsistency(); ++m_pointer; checkConsistency(); return *this; }
 112     TimerHeapIterator operator++(int) { checkConsistency(1); return TimerHeapIterator(m_pointer++); }
 113
 114     TimerHeapIterator& operator--() { checkConsistency(); --m_pointer; checkConsistency(); return *this; }
 115     TimerHeapIterator operator--(int) { checkConsistency(-1); return TimerHeapIterator(m_pointer--); }
 116
 117     TimerHeapIterator& operator+=(ptrdiff_t i) { checkConsistency(); m_pointer += i; checkConsistency(); return *this; }
 118     TimerHeapIterator& operator-=(ptrdiff_t i) { checkConsistency(); m_pointer -= i; checkConsistency(); return *this; }
 119
 120     TimerHeapReference operator*() const { return TimerHeapReference(*m_pointer); }
 121     TimerHeapReference operator[](ptrdiff_t i) const { return TimerHeapReference(m_pointer[i]); }
 122     TimerBase* operator->() const { return *m_pointer; }
 123
 124 private:
 125     void checkConsistency(ptrdiff_t offset = 0) const
 126     {
 127         ASSERT(m_pointer >= threadGlobalTimerHeap().data());
 128         ASSERT(m_pointer <= threadGlobalTimerHeap().data() + threadGlobalTimerHeap().size());
 129         ASSERT_UNUSED(offset, m_pointer + offset >= threadGlobalTimerHeap().data());
 130         ASSERT_UNUSED(offset, m_pointer + offset <= threadGlobalTimerHeap().data() + threadGlobalTimerHeap().size());
 131     }
 132
 133     friend bool operator==(TimerHeapIterator, TimerHeapIterator);
 134     friend bool operator!=(TimerHeapIterator, TimerHeapIterator);
 135     friend bool operator<(TimerHeapIterator, TimerHeapIterator);
 136     friend bool operator>(TimerHeapIterator, TimerHeapIterator);
 137     friend bool operator<=(TimerHeapIterator, TimerHeapIterator);
 138     friend bool operator>=(TimerHeapIterator, TimerHeapIterator);
 139
 140     friend TimerHeapIterator operator+(TimerHeapIterator, size_t);
 141     friend TimerHeapIterator operator+(size_t, TimerHeapIterator);
 142
 143     friend TimerHeapIterator operator-(TimerHeapIterator, size_t);
 144     friend ptrdiff_t operator-(TimerHeapIterator, TimerHeapIterator);
 145
 146     TimerBase** m_pointer;
 147 };
 148
 149 inline bool operator==(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer == b.m_pointer; }
 150 inline bool operator!=(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer != b.m_pointer; }
 151 inline bool operator<(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer < b.m_pointer; }
 152 inline bool operator>(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer > b.m_pointer; }
 153 inline bool operator<=(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer <= b.m_pointer; }
 154 inline bool operator>=(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer >= b.m_pointer; }
 155
 156 inline TimerHeapIterator operator+(TimerHeapIterator a, size_t b) { return TimerHeapIterator(a.m_pointer + b); }
 157 inline TimerHeapIterator operator+(size_t a, TimerHeapIterator b) { return TimerHeapIterator(a + b.m_pointer); }
 158
 159 inline TimerHeapIterator operator-(TimerHeapIterator a, size_t b) { return TimerHeapIterator(a.m_pointer - b); }
 160 inline ptrdiff_t operator-(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer - b.m_pointer; }
 161
 162 // ----------------
 163
 164 class TimerHeapLessThanFunction {
 165 public:
 166     bool operator()(const TimerBase*, const TimerBase*) const;
 167 };
 168
 169 inline bool TimerHeapLessThanFunction::operator()(const TimerBase* a, const TimerBase* b) const
 170 {
 171     // The comparisons below are "backwards" because the heap puts the largest
 172     // element first and we want the lowest time to be the first one in the heap.
 173     double aFireTime = a->m_nextFireTime;
 174     double bFireTime = b->m_nextFireTime;
 175     if (bFireTime != aFireTime)
 176         return bFireTime < aFireTime;
 177
 178     // We need to look at the difference of the insertion orders instead of comparing the two
 179     // outright in case of overflow.
 180     unsigned difference = a->m_heapInsertionOrder - b->m_heapInsertionOrder;
 181     return difference < std::numeric_limits<unsigned>::max() / 2;
 182 }
 183
 184 // ----------------
 185
 186 TimerBase::TimerBase()
 187     : m_nextFireTime(0)
 188     , m_unalignedNextFireTime(0)
 189     , m_repeatInterval(0)
 190     , m_heapIndex(-1)
 191     , m_cachedThreadGlobalTimerHeap(0)
 192 #if ENABLE(ASSERT)
 193     , m_thread(currentThread())
 194 #endif
 195 {
 196 }
 197
 198 TimerBase::~TimerBase()
 199 {
 200     stop();
 201     ASSERT(!inHeap());
 202 }
 203
 204 void TimerBase::start(double nextFireInterval, double repeatInterval, const TraceLocation& caller)
 205 {
 206     ASSERT(m_thread == currentThread());
 207
 208     m_location = caller;
 209     m_repeatInterval = repeatInterval;
 210     setNextFireTime(monotonicallyIncreasingTime() + nextFireInterval);
 211 }
 212
 213 void TimerBase::stop()
 214 {
 215     ASSERT(m_thread == currentThread());
 216
 217     m_repeatInterval = 0;
 218     setNextFireTime(0);
 219
 220     ASSERT(m_nextFireTime == 0);
 221     ASSERT(m_repeatInterval == 0);
 222     ASSERT(!inHeap());
 223 }
 224
 225 double TimerBase::nextFireInterval() const
 226 {
 227     ASSERT(isActive());
 228     double current = monotonicallyIncreasingTime();
 229     if (m_nextFireTime < current)
 230         return 0;
 231     return m_nextFireTime - current;
 232 }
 233
 234 inline void TimerBase::checkHeapIndex() const
 235 {
 236     ASSERT(timerHeap() == threadGlobalTimerHeap());
 237     ASSERT(!timerHeap().isEmpty());
 238     ASSERT(m_heapIndex >= 0);
 239     ASSERT(m_heapIndex < static_cast<int>(timerHeap().size()));
 240     ASSERT(timerHeap()[m_heapIndex] == this);
 241 }
 242
 243 inline void TimerBase::checkConsistency() const
 244 {
 245     // Timers should be in the heap if and only if they have a non-zero next fire time.
 246     ASSERT(inHeap() == (m_nextFireTime != 0));
 247     if (inHeap())
 248         checkHeapIndex();
 249 }
 250
 251 void TimerBase::heapDecreaseKey()
 252 {
 253     ASSERT(m_nextFireTime != 0);
 254     checkHeapIndex();
 255     TimerBase** heapData = timerHeap().data();
 256     push_heap(TimerHeapIterator(heapData), TimerHeapIterator(heapData + m_heapIndex + 1), TimerHeapLessThanFunction());
 257     checkHeapIndex();
 258 }
 259
 260 inline void TimerBase::heapDelete()
 261 {
 262     ASSERT(m_nextFireTime == 0);
 263     heapPop();
 264     timerHeap().removeLast();
 265     m_heapIndex = -1;
 266 }
 267
 268 void TimerBase::heapDeleteMin()
 269 {
 270     ASSERT(m_nextFireTime == 0);
 271     heapPopMin();
 272     timerHeap().removeLast();
 273     m_heapIndex = -1;
 274 }
 275
 276 inline void TimerBase::heapIncreaseKey()
 277 {
 278     ASSERT(m_nextFireTime != 0);
 279     heapPop();
 280     heapDecreaseKey();
 281 }
 282
 283 inline void TimerBase::heapInsert()
 284 {
 285     ASSERT(!inHeap());
 286     timerHeap().append(this);
 287     m_heapIndex = timerHeap().size() - 1;
 288     heapDecreaseKey();
 289 }
 290
 291 inline void TimerBase::heapPop()
 292 {
 293     // Temporarily force this timer to have the minimum key so we can pop it.
 294     double fireTime = m_nextFireTime;
 295     m_nextFireTime = -std::numeric_limits<double>::infinity();
 296     heapDecreaseKey();
 297     heapPopMin();
 298     m_nextFireTime = fireTime;
 299 }
 300
 301 void TimerBase::heapPopMin()
 302 {
 303     ASSERT(this == timerHeap().first());
 304     checkHeapIndex();
 305     Vector<TimerBase*>& heap = timerHeap();
 306     TimerBase** heapData = heap.data();
 307     pop_heap(TimerHeapIterator(heapData), TimerHeapIterator(heapData + heap.size()), TimerHeapLessThanFunction());
 308     checkHeapIndex();
 309     ASSERT(this == timerHeap().last());
 310 }
 311
 312 static inline bool parentHeapPropertyHolds(const TimerBase* current, const Vector<TimerBase*>& heap, unsigned currentIndex)
 313 {
 314     if (!currentIndex)
 315         return true;
 316     unsigned parentIndex = (currentIndex - 1) / 2;
 317     TimerHeapLessThanFunction compareHeapPosition;
 318     return compareHeapPosition(current, heap[parentIndex]);
 319 }
 320
 321 static inline bool childHeapPropertyHolds(const TimerBase* current, const Vector<TimerBase*>& heap, unsigned childIndex)
 322 {
 323     if (childIndex >= heap.size())
 324         return true;
 325     TimerHeapLessThanFunction compareHeapPosition;
 326     return compareHeapPosition(heap[childIndex], current);
 327 }
 328
 329 bool TimerBase::hasValidHeapPosition() const
 330 {
 331     ASSERT(m_nextFireTime);
 332     if (!inHeap())
 333         return false;
 334     // Check if the heap property still holds with the new fire time. If it does we don't need to do anything.
 335     // This assumes that the STL heap is a standard binary heap. In an unlikely event it is not, the assertions
 336     // in updateHeapIfNeeded() will get hit.
 337     const Vector<TimerBase*>& heap = timerHeap();
 338     if (!parentHeapPropertyHolds(this, heap, m_heapIndex))
 339         return false;
 340     unsigned childIndex1 = 2 * m_heapIndex + 1;
 341     unsigned childIndex2 = childIndex1 + 1;
 342     return childHeapPropertyHolds(this, heap, childIndex1) && childHeapPropertyHolds(this, heap, childIndex2);
 343 }
 344
 345 void TimerBase::updateHeapIfNeeded(double oldTime)
 346 {
 347     if (m_nextFireTime && hasValidHeapPosition())
 348         return;
 349 #if ENABLE(ASSERT)
 350     int oldHeapIndex = m_heapIndex;
 351 #endif
 352     if (!oldTime)
 353         heapInsert();
 354     else if (!m_nextFireTime)
 355         heapDelete();
 356     else if (m_nextFireTime < oldTime)
 357         heapDecreaseKey();
 358     else
 359         heapIncreaseKey();
 360     ASSERT(m_heapIndex != oldHeapIndex);
 361     ASSERT(!inHeap() || hasValidHeapPosition());
 362 }
 363
 364 void TimerBase::setNextFireTime(double newUnalignedTime)
 365 {
 366     ASSERT(m_thread == currentThread());
 367
 368     if (m_unalignedNextFireTime != newUnalignedTime)
 369         m_unalignedNextFireTime = newUnalignedTime;
 370
 371     // Accessing thread global data is slow. Cache the heap pointer.
 372     if (!m_cachedThreadGlobalTimerHeap)
 373         m_cachedThreadGlobalTimerHeap = &threadGlobalTimerHeap();
 374
 375     // Keep heap valid while changing the next-fire time.
 376     double oldTime = m_nextFireTime;
 377     double newTime = alignedFireTime(newUnalignedTime);
 378     if (oldTime != newTime) {
 379         m_nextFireTime = newTime;
 380         static unsigned currentHeapInsertionOrder;
 381         m_heapInsertionOrder = currentHeapInsertionOrder++;
 382
 383         bool wasFirstTimerInHeap = m_heapIndex == 0;
 384
 385         updateHeapIfNeeded(oldTime);
 386
 387         bool isFirstTimerInHeap = m_heapIndex == 0;
 388
 389         if (wasFirstTimerInHeap || isFirstTimerInHeap)
 390             PlatformThreadData::current().threadTimers().updateSharedTimer();
 391     }
 392
 393     checkConsistency();
 394 }
 395
 396 void TimerBase::fireTimersInNestedEventLoop()
 397 {
 398     // Redirect to ThreadTimers.
 399     PlatformThreadData::current().threadTimers().fireTimersInNestedEventLoop();
 400 }
 401
 402 void TimerBase::didChangeAlignmentInterval()
 403 {
 404     setNextFireTime(m_unalignedNextFireTime);
 405 }
 406
 407 double TimerBase::nextUnalignedFireInterval() const
 408 {
 409     ASSERT(isActive());
 410     return std::max(m_unalignedNextFireTime - monotonicallyIncreasingTime(), 0.0);
 411 }
 412
 413 } // namespace blink
 414