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