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