Timer scheduling should be based off the monotonic clock
[WebKit-https.git] / Source / WebCore / 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 "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
40 using namespace std;
41
42 namespace WebCore {
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
50 // Simple accessors to thread-specific data.
51 static Vector<TimerBase*>& timerHeap()
52 {
53     return threadGlobalData().threadTimers().timerHeap();
54 }
55
56 // Class to represent elements in the heap when calling the standard library heap algorithms.
57 // Maintains the m_heapIndex value in the timers themselves, which allows us to do efficient
58 // modification of the heap.
59 class TimerHeapElement {
60 public:
61     explicit TimerHeapElement(int i)
62         : m_index(i)
63         , m_timer(timerHeap()[m_index])
64     { 
65         checkConsistency(); 
66     }
67
68     TimerHeapElement(const TimerHeapElement&);
69     TimerHeapElement& operator=(const TimerHeapElement&);
70
71     TimerBase* timer() const { return m_timer; }
72
73     void checkConsistency() const
74     {
75         ASSERT(m_index >= 0);
76         ASSERT(m_index < static_cast<int>(timerHeap().size()));
77     }
78
79 private:
80     TimerHeapElement();
81
82     int m_index;
83     TimerBase* m_timer;
84 };
85
86 inline TimerHeapElement::TimerHeapElement(const TimerHeapElement& o)
87     : m_index(-1), m_timer(o.timer())
88 {
89 }
90
91 inline TimerHeapElement& TimerHeapElement::operator=(const TimerHeapElement& o)
92 {
93     TimerBase* t = o.timer();
94     m_timer = t;
95     if (m_index != -1) {
96         checkConsistency();
97         timerHeap()[m_index] = t;
98         t->m_heapIndex = m_index;
99     }
100     return *this;
101 }
102
103 inline bool operator<(const TimerHeapElement& a, const TimerHeapElement& b)
104 {
105     // The comparisons below are "backwards" because the heap puts the largest 
106     // element first and we want the lowest time to be the first one in the heap.
107     double aFireTime = a.timer()->m_nextFireTime;
108     double bFireTime = b.timer()->m_nextFireTime;
109     if (bFireTime != aFireTime)
110         return bFireTime < aFireTime;
111     
112     // We need to look at the difference of the insertion orders instead of comparing the two 
113     // outright in case of overflow. 
114     unsigned difference = a.timer()->m_heapInsertionOrder - b.timer()->m_heapInsertionOrder;
115     return difference < UINT_MAX / 2;
116 }
117
118 // ----------------
119
120 // Class to represent iterators in the heap when calling the standard library heap algorithms.
121 // Returns TimerHeapElement for elements in the heap rather than the TimerBase pointers themselves.
122 class TimerHeapIterator : public iterator<random_access_iterator_tag, TimerHeapElement, int> {
123 public:
124     TimerHeapIterator() : m_index(-1) { }
125     TimerHeapIterator(int i) : m_index(i) { checkConsistency(); }
126
127     TimerHeapIterator& operator++() { checkConsistency(); ++m_index; checkConsistency(); return *this; }
128     TimerHeapIterator operator++(int) { checkConsistency(); checkConsistency(1); return m_index++; }
129
130     TimerHeapIterator& operator--() { checkConsistency(); --m_index; checkConsistency(); return *this; }
131     TimerHeapIterator operator--(int) { checkConsistency(); checkConsistency(-1); return m_index--; }
132
133     TimerHeapIterator& operator+=(int i) { checkConsistency(); m_index += i; checkConsistency(); return *this; }
134     TimerHeapIterator& operator-=(int i) { checkConsistency(); m_index -= i; checkConsistency(); return *this; }
135
136     TimerHeapElement operator*() const { return TimerHeapElement(m_index); }
137     TimerHeapElement operator[](int i) const { return TimerHeapElement(m_index + i); }
138
139     int index() const { return m_index; }
140
141     void checkConsistency(int offset = 0) const
142     {
143         ASSERT_UNUSED(offset, m_index + offset >= 0);
144         ASSERT_UNUSED(offset, m_index + offset <= static_cast<int>(timerHeap().size()));
145     }
146
147 private:
148     int m_index;
149 };
150
151 inline bool operator==(TimerHeapIterator a, TimerHeapIterator b) { return a.index() == b.index(); }
152 inline bool operator!=(TimerHeapIterator a, TimerHeapIterator b) { return a.index() != b.index(); }
153 inline bool operator<(TimerHeapIterator a, TimerHeapIterator b) { return a.index() < b.index(); }
154
155 inline TimerHeapIterator operator+(TimerHeapIterator a, int b) { return a.index() + b; }
156 inline TimerHeapIterator operator+(int a, TimerHeapIterator b) { return a + b.index(); }
157
158 inline TimerHeapIterator operator-(TimerHeapIterator a, int b) { return a.index() - b; }
159 inline int operator-(TimerHeapIterator a, TimerHeapIterator b) { return a.index() - b.index(); }
160
161 // ----------------
162
163 TimerBase::TimerBase()
164     : m_nextFireTime(0)
165     , m_repeatInterval(0)
166     , m_heapIndex(-1)
167 #ifndef NDEBUG
168     , m_thread(currentThread())
169 #endif
170 {
171 }
172
173 TimerBase::~TimerBase()
174 {
175     stop();
176     ASSERT(!inHeap());
177 }
178
179 void TimerBase::start(double nextFireInterval, double repeatInterval)
180 {
181     ASSERT(m_thread == currentThread());
182
183     m_repeatInterval = repeatInterval;
184     setNextFireTime(monotonicallyIncreasingTime() + nextFireInterval);
185 }
186
187 void TimerBase::stop()
188 {
189     ASSERT(m_thread == currentThread());
190
191     m_repeatInterval = 0;
192     setNextFireTime(0);
193
194     ASSERT(m_nextFireTime == 0);
195     ASSERT(m_repeatInterval == 0);
196     ASSERT(!inHeap());
197 }
198
199 double TimerBase::nextFireInterval() const
200 {
201     ASSERT(isActive());
202     double current = monotonicallyIncreasingTime();
203     if (m_nextFireTime < current)
204         return 0;
205     return m_nextFireTime - current;
206 }
207
208 inline void TimerBase::checkHeapIndex() const
209 {
210     ASSERT(!timerHeap().isEmpty());
211     ASSERT(m_heapIndex >= 0);
212     ASSERT(m_heapIndex < static_cast<int>(timerHeap().size()));
213     ASSERT(timerHeap()[m_heapIndex] == this);
214 }
215
216 inline void TimerBase::checkConsistency() const
217 {
218     // Timers should be in the heap if and only if they have a non-zero next fire time.
219     ASSERT(inHeap() == (m_nextFireTime != 0));
220     if (inHeap())
221         checkHeapIndex();
222 }
223
224 void TimerBase::heapDecreaseKey()
225 {
226     ASSERT(m_nextFireTime != 0);
227     checkHeapIndex();
228     push_heap(TimerHeapIterator(0), TimerHeapIterator(m_heapIndex + 1));
229     checkHeapIndex();
230 }
231
232 inline void TimerBase::heapDelete()
233 {
234     ASSERT(m_nextFireTime == 0);
235     heapPop();
236     timerHeap().removeLast();
237     m_heapIndex = -1;
238 }
239
240 void TimerBase::heapDeleteMin()
241 {
242     ASSERT(m_nextFireTime == 0);
243     heapPopMin();
244     timerHeap().removeLast();
245     m_heapIndex = -1;
246 }
247
248 inline void TimerBase::heapIncreaseKey()
249 {
250     ASSERT(m_nextFireTime != 0);
251     heapPop();
252     heapDecreaseKey();
253 }
254
255 inline void TimerBase::heapInsert()
256 {
257     ASSERT(!inHeap());
258     timerHeap().append(this);
259     m_heapIndex = timerHeap().size() - 1;
260     heapDecreaseKey();
261 }
262
263 inline void TimerBase::heapPop()
264 {
265     // Temporarily force this timer to have the minimum key so we can pop it.
266     double fireTime = m_nextFireTime;
267     m_nextFireTime = -numeric_limits<double>::infinity();
268     heapDecreaseKey();
269     heapPopMin();
270     m_nextFireTime = fireTime;
271 }
272
273 void TimerBase::heapPopMin()
274 {
275     ASSERT(this == timerHeap().first());
276     checkHeapIndex();
277     pop_heap(TimerHeapIterator(0), TimerHeapIterator(timerHeap().size()));
278     checkHeapIndex();
279     ASSERT(this == timerHeap().last());
280 }
281
282 void TimerBase::setNextFireTime(double newTime)
283 {
284     ASSERT(m_thread == currentThread());
285
286     // Keep heap valid while changing the next-fire time.
287     double oldTime = m_nextFireTime;
288     if (oldTime != newTime) {
289         m_nextFireTime = newTime;
290         static unsigned currentHeapInsertionOrder;
291         m_heapInsertionOrder = currentHeapInsertionOrder++;
292
293         bool wasFirstTimerInHeap = m_heapIndex == 0;
294
295         if (oldTime == 0)
296             heapInsert();
297         else if (newTime == 0)
298             heapDelete();
299         else if (newTime < oldTime)
300             heapDecreaseKey();
301         else
302             heapIncreaseKey();
303
304         bool isFirstTimerInHeap = m_heapIndex == 0;
305
306         if (wasFirstTimerInHeap || isFirstTimerInHeap)
307             threadGlobalData().threadTimers().updateSharedTimer();
308     }
309
310     checkConsistency();
311 }
312
313 void TimerBase::fireTimersInNestedEventLoop()
314 {
315     // Redirect to ThreadTimers.
316     threadGlobalData().threadTimers().fireTimersInNestedEventLoop();
317 }
318
319 } // namespace WebCore
320