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 using namespace std;
  39
  40 namespace WebCore {
  41
  42 class TimerHeapReference;
  43
  44 // Timers are stored in a heap data structure, used to implement a priority queue.
  45 // This allows us to efficiently determine which timer needs to fire the soonest.
  46 // Then we set a single shared system timer to fire at that time.
  47 //
  48 // When a timer's "next fire time" changes, we need to move it around in the priority queue.
  49 static Vector<TimerBase*>& threadGlobalTimerHeap()
  50 {
  51     return PlatformThreadData::current().threadTimers().timerHeap();
  52 }
  53 // ----------------
  54
  55 class TimerHeapPointer {
  56 public:
  57     TimerHeapPointer(TimerBase** pointer) : m_pointer(pointer) { }
  58     TimerHeapReference operator*() const;
  59     TimerBase* operator->() const { return *m_pointer; }
  60 private:
  61     TimerBase** m_pointer;
  62 };
  63
  64 class TimerHeapReference {
  65 public:
  66     TimerHeapReference(TimerBase*& reference) : m_reference(reference) { }
  67     operator TimerBase*() const { return m_reference; }
  68     TimerHeapPointer operator&() const { return &m_reference; }
  69     TimerHeapReference& operator=(TimerBase*);
  70     TimerHeapReference& operator=(TimerHeapReference);
  71 private:
  72     TimerBase*& m_reference;
  73 };
  74
  75 inline TimerHeapReference TimerHeapPointer::operator*() const
  76 {
  77     return *m_pointer;
  78 }
  79
  80 inline TimerHeapReference& TimerHeapReference::operator=(TimerBase* timer)
  81 {
  82     m_reference = timer;
  83     Vector<TimerBase*>& heap = timer->timerHeap();
  84     if (&m_reference >= heap.data() && &m_reference < heap.data() + heap.size())
  85         timer->m_heapIndex = &m_reference - heap.data();
  86     return *this;
  87 }
  88
  89 inline TimerHeapReference& TimerHeapReference::operator=(TimerHeapReference b)
  90 {
  91     TimerBase* timer = b;
  92     return *this = timer;
  93 }
  94
  95 inline void swap(TimerHeapReference a, TimerHeapReference b)
  96 {
  97     TimerBase* timerA = a;
  98     TimerBase* timerB = b;
  99
 100     // Invoke the assignment operator, since that takes care of updating m_heapIndex.
 101     a = timerB;
 102     b = timerA;
 103 }
 104
 105 // ----------------
 106
 107 // Class to represent iterators in the heap when calling the standard library heap algorithms.
 108 // Uses a custom pointer and reference type that update indices for pointers in the heap.
 109 class TimerHeapIterator : public iterator<random_access_iterator_tag, TimerBase*, ptrdiff_t, TimerHeapPointer, TimerHeapReference> {
 110 public:
 111     explicit TimerHeapIterator(TimerBase** pointer) : m_pointer(pointer) { checkConsistency(); }
 112
 113     TimerHeapIterator& operator++() { checkConsistency(); ++m_pointer; checkConsistency(); return *this; }
 114     TimerHeapIterator operator++(int) { checkConsistency(1); return TimerHeapIterator(m_pointer++); }
 115
 116     TimerHeapIterator& operator--() { checkConsistency(); --m_pointer; checkConsistency(); return *this; }
 117     TimerHeapIterator operator--(int) { checkConsistency(-1); return TimerHeapIterator(m_pointer--); }
 118
 119     TimerHeapIterator& operator+=(ptrdiff_t i) { checkConsistency(); m_pointer += i; checkConsistency(); return *this; }
 120     TimerHeapIterator& operator-=(ptrdiff_t i) { checkConsistency(); m_pointer -= i; checkConsistency(); return *this; }
 121
 122     TimerHeapReference operator*() const { return TimerHeapReference(*m_pointer); }
 123     TimerHeapReference operator[](ptrdiff_t i) const { return TimerHeapReference(m_pointer[i]); }
 124     TimerBase* operator->() const { return *m_pointer; }
 125
 126 private:
 127     void checkConsistency(ptrdiff_t offset = 0) const
 128     {
 129         ASSERT(m_pointer >= threadGlobalTimerHeap().data());
 130         ASSERT(m_pointer <= threadGlobalTimerHeap().data() + threadGlobalTimerHeap().size());
 131         ASSERT_UNUSED(offset, m_pointer + offset >= threadGlobalTimerHeap().data());
 132         ASSERT_UNUSED(offset, m_pointer + offset <= threadGlobalTimerHeap().data() + threadGlobalTimerHeap().size());
 133     }
 134
 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     friend bool operator<=(TimerHeapIterator, TimerHeapIterator);
 140     friend bool operator>=(TimerHeapIterator, TimerHeapIterator);
 141
 142     friend TimerHeapIterator operator+(TimerHeapIterator, size_t);
 143     friend TimerHeapIterator operator+(size_t, TimerHeapIterator);
 144
 145     friend TimerHeapIterator operator-(TimerHeapIterator, size_t);
 146     friend ptrdiff_t operator-(TimerHeapIterator, TimerHeapIterator);
 147
 148     TimerBase** m_pointer;
 149 };
 150
 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 inline bool operator<=(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer <= b.m_pointer; }
 156 inline bool operator>=(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer >= b.m_pointer; }
 157
 158 inline TimerHeapIterator operator+(TimerHeapIterator a, size_t b) { return TimerHeapIterator(a.m_pointer + b); }
 159 inline TimerHeapIterator operator+(size_t a, TimerHeapIterator b) { return TimerHeapIterator(a + b.m_pointer); }
 160
 161 inline TimerHeapIterator operator-(TimerHeapIterator a, size_t b) { return TimerHeapIterator(a.m_pointer - b); }
 162 inline ptrdiff_t operator-(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer - b.m_pointer; }
 163
 164 // ----------------
 165
 166 class TimerHeapLessThanFunction {
 167 public:
 168     bool operator()(const TimerBase*, const TimerBase*) const;
 169 };
 170
 171 inline bool TimerHeapLessThanFunction::operator()(const TimerBase* a, const TimerBase* b) const
 172 {
 173     // The comparisons below are "backwards" because the heap puts the largest
 174     // element first and we want the lowest time to be the first one in the heap.
 175     double aFireTime = a->m_nextFireTime;
 176     double bFireTime = b->m_nextFireTime;
 177     if (bFireTime != aFireTime)
 178         return bFireTime < aFireTime;
 179
 180     // We need to look at the difference of the insertion orders instead of comparing the two
 181     // outright in case of overflow.
 182     unsigned difference = a->m_heapInsertionOrder - b->m_heapInsertionOrder;
 183     return difference < numeric_limits<unsigned>::max() / 2;
 184 }
 185
 186 // ----------------
 187
 188 TimerBase::TimerBase()
 189     : m_nextFireTime(0)
 190     , m_unalignedNextFireTime(0)
 191     , m_repeatInterval(0)
 192     , m_heapIndex(-1)
 193     , m_cachedThreadGlobalTimerHeap(0)
 194 #ifndef NDEBUG
 195     , m_thread(currentThread())
 196 #endif
 197 {
 198 }
 199
 200 TimerBase::~TimerBase()
 201 {
 202     stop();
 203     ASSERT(!inHeap());
 204 }
 205
 206 void TimerBase::start(double nextFireInterval, double repeatInterval)
 207 {
 208     ASSERT(m_thread == currentThread());
 209
 210     m_repeatInterval = repeatInterval;
 211     setNextFireTime(monotonicallyIncreasingTime() + nextFireInterval);
 212 }
 213
 214 void TimerBase::stop()
 215 {
 216     ASSERT(m_thread == currentThread());
 217
 218     m_repeatInterval = 0;
 219     setNextFireTime(0);
 220
 221     ASSERT(m_nextFireTime == 0);
 222     ASSERT(m_repeatInterval == 0);
 223     ASSERT(!inHeap());
 224 }
 225
 226 double TimerBase::nextFireInterval() const
 227 {
 228     ASSERT(isActive());
 229     double current = monotonicallyIncreasingTime();
 230     if (m_nextFireTime < current)
 231         return 0;
 232     return m_nextFireTime - current;
 233 }
 234
 235 inline void TimerBase::checkHeapIndex() const
 236 {
 237     ASSERT(timerHeap() == threadGlobalTimerHeap());
 238     ASSERT(!timerHeap().isEmpty());
 239     ASSERT(m_heapIndex >= 0);
 240     ASSERT(m_heapIndex < static_cast<int>(timerHeap().size()));
 241     ASSERT(timerHeap()[m_heapIndex] == this);
 242 }
 243
 244 inline void TimerBase::checkConsistency() const
 245 {
 246     // Timers should be in the heap if and only if they have a non-zero next fire time.
 247     ASSERT(inHeap() == (m_nextFireTime != 0));
 248     if (inHeap())
 249         checkHeapIndex();
 250 }
 251
 252 void TimerBase::heapDecreaseKey()
 253 {
 254     ASSERT(m_nextFireTime != 0);
 255     checkHeapIndex();
 256     TimerBase** heapData = timerHeap().data();
 257     push_heap(TimerHeapIterator(heapData), TimerHeapIterator(heapData + m_heapIndex + 1), TimerHeapLessThanFunction());
 258     checkHeapIndex();
 259 }
 260
 261 inline void TimerBase::heapDelete()
 262 {
 263     ASSERT(m_nextFireTime == 0);
 264     heapPop();
 265     timerHeap().removeLast();
 266     m_heapIndex = -1;
 267 }
 268
 269 void TimerBase::heapDeleteMin()
 270 {
 271     ASSERT(m_nextFireTime == 0);
 272     heapPopMin();
 273     timerHeap().removeLast();
 274     m_heapIndex = -1;
 275 }
 276
 277 inline void TimerBase::heapIncreaseKey()
 278 {
 279     ASSERT(m_nextFireTime != 0);
 280     heapPop();
 281     heapDecreaseKey();
 282 }
 283
 284 inline void TimerBase::heapInsert()
 285 {
 286     ASSERT(!inHeap());
 287     timerHeap().append(this);
 288     m_heapIndex = timerHeap().size() - 1;
 289     heapDecreaseKey();
 290 }
 291
 292 inline void TimerBase::heapPop()
 293 {
 294     // Temporarily force this timer to have the minimum key so we can pop it.
 295     double fireTime = m_nextFireTime;
 296     m_nextFireTime = -numeric_limits<double>::infinity();
 297     heapDecreaseKey();
 298     heapPopMin();
 299     m_nextFireTime = fireTime;
 300 }
 301
 302 void TimerBase::heapPopMin()
 303 {
 304     ASSERT(this == timerHeap().first());
 305     checkHeapIndex();
 306     Vector<TimerBase*>& heap = timerHeap();
 307     TimerBase** heapData = heap.data();
 308     pop_heap(TimerHeapIterator(heapData), TimerHeapIterator(heapData + heap.size()), TimerHeapLessThanFunction());
 309     checkHeapIndex();
 310     ASSERT(this == timerHeap().last());
 311 }
 312
 313 static inline bool parentHeapPropertyHolds(const TimerBase* current, const Vector<TimerBase*>& heap, unsigned currentIndex)
 314 {
 315     if (!currentIndex)
 316         return true;
 317     unsigned parentIndex = (currentIndex - 1) / 2;
 318     TimerHeapLessThanFunction compareHeapPosition;
 319     return compareHeapPosition(current, heap[parentIndex]);
 320 }
 321
 322 static inline bool childHeapPropertyHolds(const TimerBase* current, const Vector<TimerBase*>& heap, unsigned childIndex)
 323 {
 324     if (childIndex >= heap.size())
 325         return true;
 326     TimerHeapLessThanFunction compareHeapPosition;
 327     return compareHeapPosition(heap[childIndex], current);
 328 }
 329
 330 bool TimerBase::hasValidHeapPosition() const
 331 {
 332     ASSERT(m_nextFireTime);
 333     if (!inHeap())
 334         return false;
 335     // Check if the heap property still holds with the new fire time. If it does we don't need to do anything.
 336     // This assumes that the STL heap is a standard binary heap. In an unlikely event it is not, the assertions
 337     // in updateHeapIfNeeded() will get hit.
 338     const Vector<TimerBase*>& heap = timerHeap();
 339     if (!parentHeapPropertyHolds(this, heap, m_heapIndex))
 340         return false;
 341     unsigned childIndex1 = 2 * m_heapIndex + 1;
 342     unsigned childIndex2 = childIndex1 + 1;
 343     return childHeapPropertyHolds(this, heap, childIndex1) && childHeapPropertyHolds(this, heap, childIndex2);
 344 }
 345
 346 void TimerBase::updateHeapIfNeeded(double oldTime)
 347 {
 348     if (m_nextFireTime && hasValidHeapPosition())
 349         return;
 350 #ifndef NDEBUG
 351     int oldHeapIndex = m_heapIndex;
 352 #endif
 353     if (!oldTime)
 354         heapInsert();
 355     else if (!m_nextFireTime)
 356         heapDelete();
 357     else if (m_nextFireTime < oldTime)
 358         heapDecreaseKey();
 359     else
 360         heapIncreaseKey();
 361     ASSERT(m_heapIndex != oldHeapIndex);
 362     ASSERT(!inHeap() || hasValidHeapPosition());
 363 }
 364
 365 void TimerBase::setNextFireTime(double newUnalignedTime)
 366 {
 367     ASSERT(m_thread == currentThread());
 368
 369     if (m_unalignedNextFireTime != newUnalignedTime)
 370         m_unalignedNextFireTime = newUnalignedTime;
 371
 372     // Accessing thread global data is slow. Cache the heap pointer.
 373     if (!m_cachedThreadGlobalTimerHeap)
 374         m_cachedThreadGlobalTimerHeap = &threadGlobalTimerHeap();
 375
 376     // Keep heap valid while changing the next-fire time.
 377     double oldTime = m_nextFireTime;
 378     double newTime = alignedFireTime(newUnalignedTime);
 379     if (oldTime != newTime) {
 380         m_nextFireTime = newTime;
 381         static unsigned currentHeapInsertionOrder;
 382         m_heapInsertionOrder = currentHeapInsertionOrder++;
 383
 384         bool wasFirstTimerInHeap = m_heapIndex == 0;
 385
 386         updateHeapIfNeeded(oldTime);
 387
 388         bool isFirstTimerInHeap = m_heapIndex == 0;
 389
 390         if (wasFirstTimerInHeap || isFirstTimerInHeap)
 391             PlatformThreadData::current().threadTimers().updateSharedTimer();
 392     }
 393
 394     checkConsistency();
 395 }
 396
 397 void TimerBase::fireTimersInNestedEventLoop()
 398 {
 399     // Redirect to ThreadTimers.
 400     PlatformThreadData::current().threadTimers().fireTimersInNestedEventLoop();
 401 }
 402
 403 void TimerBase::didChangeAlignmentInterval()
 404 {
 405     setNextFireTime(m_unalignedNextFireTime);
 406 }
 407
 408 double TimerBase::nextUnalignedFireInterval() const
 409 {
 410     ASSERT(isActive());
 411     return max(m_unalignedNextFireTime - monotonicallyIncreasingTime(), 0.0);
 412 }
 413
 414 } // namespace WebCore
 415