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
38namespace blink {
39
40class 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.
47static Vector<TimerBase*>& threadGlobalTimerHeap()
48{
49    return PlatformThreadData::current().threadTimers().timerHeap();
50}
51// ----------------
52
53class TimerHeapPointer {
54public:
55    TimerHeapPointer(TimerBase** pointer) : m_pointer(pointer) { }
56    TimerHeapReference operator*() const;
57    TimerBase* operator->() const { return *m_pointer; }
58private:
59    TimerBase** m_pointer;
60};
61
62class TimerHeapReference {
63public:
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);
69private:
70    TimerBase*& m_reference;
71};
72
73inline TimerHeapReference TimerHeapPointer::operator*() const
74{
75    return *m_pointer;
76}
77
78inline 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
87inline TimerHeapReference& TimerHeapReference::operator=(TimerHeapReference b)
88{
89    TimerBase* timer = b;
90    return *this = timer;
91}
92
93inline 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.
107class TimerHeapIterator : public std::iterator<std::random_access_iterator_tag, TimerBase*, ptrdiff_t, TimerHeapPointer, TimerHeapReference> {
108public:
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
124private:
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
149inline bool operator==(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer == b.m_pointer; }
150inline bool operator!=(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer != b.m_pointer; }
151inline bool operator<(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer < b.m_pointer; }
152inline bool operator>(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer > b.m_pointer; }
153inline bool operator<=(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer <= b.m_pointer; }
154inline bool operator>=(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer >= b.m_pointer; }
155
156inline TimerHeapIterator operator+(TimerHeapIterator a, size_t b) { return TimerHeapIterator(a.m_pointer + b); }
157inline TimerHeapIterator operator+(size_t a, TimerHeapIterator b) { return TimerHeapIterator(a + b.m_pointer); }
158
159inline TimerHeapIterator operator-(TimerHeapIterator a, size_t b) { return TimerHeapIterator(a.m_pointer - b); }
160inline ptrdiff_t operator-(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer - b.m_pointer; }
161
162// ----------------
163
164class TimerHeapLessThanFunction {
165public:
166    bool operator()(const TimerBase*, const TimerBase*) const;
167};
168
169inline 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
186TimerBase::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
198TimerBase::~TimerBase()
199{
200    stop();
201    ASSERT(!inHeap());
202}
203
204void 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
213void 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
225double 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
234inline 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
243inline 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
251void 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
260inline void TimerBase::heapDelete()
261{
262    ASSERT(m_nextFireTime == 0);
263    heapPop();
264    timerHeap().removeLast();
265    m_heapIndex = -1;
266}
267
268void TimerBase::heapDeleteMin()
269{
270    ASSERT(m_nextFireTime == 0);
271    heapPopMin();
272    timerHeap().removeLast();
273    m_heapIndex = -1;
274}
275
276inline void TimerBase::heapIncreaseKey()
277{
278    ASSERT(m_nextFireTime != 0);
279    heapPop();
280    heapDecreaseKey();
281}
282
283inline void TimerBase::heapInsert()
284{
285    ASSERT(!inHeap());
286    timerHeap().append(this);
287    m_heapIndex = timerHeap().size() - 1;
288    heapDecreaseKey();
289}
290
291inline 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
301void 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
312static 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
321static 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
329bool 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
345void 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
364void 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
396void TimerBase::fireTimersInNestedEventLoop()
397{
398    // Redirect to ThreadTimers.
399    PlatformThreadData::current().threadTimers().fireTimersInNestedEventLoop();
400}
401
402void TimerBase::didChangeAlignmentInterval()
403{
404    setNextFireTime(m_unalignedNextFireTime);
405}
406
407double TimerBase::nextUnalignedFireInterval() const
408{
409    ASSERT(isActive());
410    return std::max(m_unalignedNextFireTime - monotonicallyIncreasingTime(), 0.0);
411}
412
413} // namespace blink
414
415