Timer's nextFireInterval() / repeatInterval() should return Seconds
[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 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 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/MainThread.h>
38 #include <wtf/Vector.h>
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 threadGlobalData().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 std::iterator<std::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     MonotonicTime aFireTime = a->m_nextFireTime;
176     MonotonicTime 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 < std::numeric_limits<unsigned>::max() / 2;
184 }
185
186 // ----------------
187
188 TimerBase::TimerBase()
189 #ifndef NDEBUG
190     : m_thread(currentThread())
191 #endif
192 {
193 }
194
195 TimerBase::~TimerBase()
196 {
197     stop();
198     ASSERT(!inHeap());
199 #ifndef NDEBUG
200     m_wasDeleted = true;
201 #endif
202 }
203
204 void TimerBase::start(double nextFireInterval, double repeatInterval)
205 {
206     start(Seconds { nextFireInterval }, Seconds { repeatInterval });
207 }
208
209 void TimerBase::start(Seconds nextFireInterval, Seconds repeatInterval)
210 {
211     ASSERT(canAccessThreadLocalDataForThread(m_thread));
212
213     m_repeatInterval = repeatInterval;
214     setNextFireTime(MonotonicTime::now() + nextFireInterval);
215 }
216
217 void TimerBase::stop()
218 {
219     ASSERT(canAccessThreadLocalDataForThread(m_thread));
220
221     m_repeatInterval = 0_s;
222     setNextFireTime(MonotonicTime { });
223
224     ASSERT(!static_cast<bool>(m_nextFireTime));
225     ASSERT(m_repeatInterval == 0_s);
226     ASSERT(!inHeap());
227 }
228
229 Seconds TimerBase::nextFireInterval() const
230 {
231     ASSERT(isActive());
232     MonotonicTime current = MonotonicTime::now();
233     if (m_nextFireTime < current)
234         return 0_s;
235     return m_nextFireTime - current;
236 }
237
238 inline void TimerBase::checkHeapIndex() const
239 {
240     ASSERT(timerHeap() == threadGlobalTimerHeap());
241     ASSERT(!timerHeap().isEmpty());
242     ASSERT(m_heapIndex >= 0);
243     ASSERT(m_heapIndex < static_cast<int>(timerHeap().size()));
244     ASSERT(timerHeap()[m_heapIndex] == this);
245 }
246
247 inline void TimerBase::checkConsistency() const
248 {
249     // Timers should be in the heap if and only if they have a non-zero next fire time.
250     ASSERT(inHeap() == static_cast<bool>(m_nextFireTime));
251     if (inHeap())
252         checkHeapIndex();
253 }
254
255 void TimerBase::heapDecreaseKey()
256 {
257     ASSERT(static_cast<bool>(m_nextFireTime));
258     checkHeapIndex();
259     TimerBase** heapData = timerHeap().data();
260     push_heap(TimerHeapIterator(heapData), TimerHeapIterator(heapData + m_heapIndex + 1), TimerHeapLessThanFunction());
261     checkHeapIndex();
262 }
263
264 inline void TimerBase::heapDelete()
265 {
266     ASSERT(!static_cast<bool>(m_nextFireTime));
267     heapPop();
268     timerHeap().removeLast();
269     m_heapIndex = -1;
270 }
271
272 void TimerBase::heapDeleteMin()
273 {
274     ASSERT(!static_cast<bool>(m_nextFireTime));
275     heapPopMin();
276     timerHeap().removeLast();
277     m_heapIndex = -1;
278 }
279
280 inline void TimerBase::heapIncreaseKey()
281 {
282     ASSERT(static_cast<bool>(m_nextFireTime));
283     heapPop();
284     heapDecreaseKey();
285 }
286
287 inline void TimerBase::heapInsert()
288 {
289     ASSERT(!inHeap());
290     timerHeap().append(this);
291     m_heapIndex = timerHeap().size() - 1;
292     heapDecreaseKey();
293 }
294
295 inline void TimerBase::heapPop()
296 {
297     // Temporarily force this timer to have the minimum key so we can pop it.
298     MonotonicTime fireTime = m_nextFireTime;
299     m_nextFireTime = -MonotonicTime::infinity();
300     heapDecreaseKey();
301     heapPopMin();
302     m_nextFireTime = fireTime;
303 }
304
305 void TimerBase::heapPopMin()
306 {
307     ASSERT(this == timerHeap().first());
308     checkHeapIndex();
309     Vector<TimerBase*>& heap = timerHeap();
310     TimerBase** heapData = heap.data();
311     pop_heap(TimerHeapIterator(heapData), TimerHeapIterator(heapData + heap.size()), TimerHeapLessThanFunction());
312     checkHeapIndex();
313     ASSERT(this == timerHeap().last());
314 }
315
316 static inline bool parentHeapPropertyHolds(const TimerBase* current, const Vector<TimerBase*>& heap, unsigned currentIndex)
317 {
318     if (!currentIndex)
319         return true;
320     unsigned parentIndex = (currentIndex - 1) / 2;
321     TimerHeapLessThanFunction compareHeapPosition;
322     return compareHeapPosition(current, heap[parentIndex]);
323 }
324
325 static inline bool childHeapPropertyHolds(const TimerBase* current, const Vector<TimerBase*>& heap, unsigned childIndex)
326 {
327     if (childIndex >= heap.size())
328         return true;
329     TimerHeapLessThanFunction compareHeapPosition;
330     return compareHeapPosition(heap[childIndex], current);
331 }
332
333 bool TimerBase::hasValidHeapPosition() const
334 {
335     ASSERT(m_nextFireTime);
336     if (!inHeap())
337         return false;
338     // Check if the heap property still holds with the new fire time. If it does we don't need to do anything.
339     // This assumes that the STL heap is a standard binary heap. In an unlikely event it is not, the assertions
340     // in updateHeapIfNeeded() will get hit.
341     const Vector<TimerBase*>& heap = timerHeap();
342     if (!parentHeapPropertyHolds(this, heap, m_heapIndex))
343         return false;
344     unsigned childIndex1 = 2 * m_heapIndex + 1;
345     unsigned childIndex2 = childIndex1 + 1;
346     return childHeapPropertyHolds(this, heap, childIndex1) && childHeapPropertyHolds(this, heap, childIndex2);
347 }
348
349 void TimerBase::updateHeapIfNeeded(MonotonicTime oldTime)
350 {
351     if (m_nextFireTime && hasValidHeapPosition())
352         return;
353 #ifndef NDEBUG
354     int oldHeapIndex = m_heapIndex;
355 #endif
356     if (!oldTime)
357         heapInsert();
358     else if (!m_nextFireTime)
359         heapDelete();
360     else if (m_nextFireTime < oldTime)
361         heapDecreaseKey();
362     else
363         heapIncreaseKey();
364     ASSERT(m_heapIndex != oldHeapIndex);
365     ASSERT(!inHeap() || hasValidHeapPosition());
366 }
367
368 void TimerBase::setNextFireTime(MonotonicTime newTime)
369 {
370     ASSERT(canAccessThreadLocalDataForThread(m_thread));
371     ASSERT(!m_wasDeleted);
372
373     if (m_unalignedNextFireTime != newTime)
374         m_unalignedNextFireTime = newTime;
375
376     // Accessing thread global data is slow. Cache the heap pointer.
377     if (!m_cachedThreadGlobalTimerHeap)
378         m_cachedThreadGlobalTimerHeap = &threadGlobalTimerHeap();
379
380     // Keep heap valid while changing the next-fire time.
381     MonotonicTime oldTime = m_nextFireTime;
382     // Don't realign zero-delay timers.
383     if (newTime) {
384         if (auto newAlignedTime = alignedFireTime(newTime))
385             newTime = newAlignedTime.value();
386     }
387
388     if (oldTime != newTime) {
389         m_nextFireTime = newTime;
390         // FIXME: This should be part of ThreadTimers, or another per-thread structure.
391         static std::atomic<unsigned> currentHeapInsertionOrder;
392         m_heapInsertionOrder = currentHeapInsertionOrder++;
393
394         bool wasFirstTimerInHeap = m_heapIndex == 0;
395
396         updateHeapIfNeeded(oldTime);
397
398         bool isFirstTimerInHeap = m_heapIndex == 0;
399
400         if (wasFirstTimerInHeap || isFirstTimerInHeap)
401             threadGlobalData().threadTimers().updateSharedTimer();
402     }
403
404     checkConsistency();
405 }
406
407 void TimerBase::fireTimersInNestedEventLoop()
408 {
409     // Redirect to ThreadTimers.
410     threadGlobalData().threadTimers().fireTimersInNestedEventLoop();
411 }
412
413 void TimerBase::didChangeAlignmentInterval()
414 {
415     setNextFireTime(m_unalignedNextFireTime);
416 }
417
418 Seconds TimerBase::nextUnalignedFireInterval() const
419 {
420     ASSERT(isActive());
421     return std::max(m_unalignedNextFireTime - MonotonicTime::now(), 0_s);
422 }
423
424 } // namespace WebCore
425