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