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