1c36d5304b2e945b386aa09e5d4c358d95aed759
[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 #if !ASSERT_DISABLED
54 static ThreadTimerHeap& threadGlobalTimerHeap()
55 {
56     return threadGlobalData().threadTimers().timerHeap();
57 }
58 #endif
59
60 inline ThreadTimerHeapItem::ThreadTimerHeapItem(TimerBase& timer, MonotonicTime time, unsigned insertionOrder)
61     : time(time)
62     , insertionOrder(insertionOrder)
63     , m_threadTimers(threadGlobalData().threadTimers())
64     , m_timer(&timer)
65 {
66     ASSERT(m_timer);
67 }
68     
69 inline RefPtr<ThreadTimerHeapItem> ThreadTimerHeapItem::create(TimerBase& timer, MonotonicTime time, unsigned insertionOrder)
70 {
71     return adoptRef(*new ThreadTimerHeapItem { timer, time, insertionOrder });
72 }
73
74 // ----------------
75
76 class TimerHeapPointer {
77 public:
78     TimerHeapPointer(RefPtr<ThreadTimerHeapItem>* pointer)
79         : m_pointer(pointer)
80     { }
81
82     TimerHeapReference operator*() const;
83     RefPtr<ThreadTimerHeapItem>& operator->() const { return *m_pointer; }
84 private:
85     RefPtr<ThreadTimerHeapItem>* m_pointer;
86 };
87
88 class TimerHeapReference {
89 public:
90     TimerHeapReference(RefPtr<ThreadTimerHeapItem>& reference)
91         : m_reference(reference)
92     { }
93
94     TimerHeapReference(const TimerHeapReference& other)
95         : m_reference(other.m_reference)
96     { }
97
98     operator RefPtr<ThreadTimerHeapItem>&() const { return m_reference; }
99     TimerHeapPointer operator&() const { return &m_reference; }
100     TimerHeapReference& operator=(TimerHeapReference&&);
101     TimerHeapReference& operator=(RefPtr<ThreadTimerHeapItem>&&);
102
103     void swap(TimerHeapReference& other);
104
105     void updateHeapIndex();
106
107 private:
108     RefPtr<ThreadTimerHeapItem>& m_reference;
109
110     friend void swap(TimerHeapReference a, TimerHeapReference b);
111 };
112
113 inline TimerHeapReference TimerHeapPointer::operator*() const
114 {
115     return TimerHeapReference { *m_pointer };
116 }
117
118 inline TimerHeapReference& TimerHeapReference::operator=(TimerHeapReference&& other)
119 {
120     m_reference = WTFMove(other.m_reference);
121     updateHeapIndex();
122     return *this;
123 }
124
125 inline TimerHeapReference& TimerHeapReference::operator=(RefPtr<ThreadTimerHeapItem>&& item)
126 {
127     m_reference = WTFMove(item);
128     updateHeapIndex();
129     return *this;
130 }
131
132 inline void TimerHeapReference::swap(TimerHeapReference& other)
133 {
134     m_reference.swap(other.m_reference);
135     updateHeapIndex();
136     other.updateHeapIndex();
137 }
138
139 inline void TimerHeapReference::updateHeapIndex()
140 {
141     auto& heap = m_reference->timerHeap();
142     if (&m_reference >= heap.data() && &m_reference < heap.data() + heap.size())
143         m_reference->setHeapIndex(&m_reference - heap.data());
144 }
145
146 inline void swap(TimerHeapReference a, TimerHeapReference b)
147 {
148     a.swap(b);
149 }
150
151 // ----------------
152
153 // Class to represent iterators in the heap when calling the standard library heap algorithms.
154 // Uses a custom pointer and reference type that update indices for pointers in the heap.
155 class TimerHeapIterator : public std::iterator<std::random_access_iterator_tag, RefPtr<ThreadTimerHeapItem>, ptrdiff_t, TimerHeapPointer, TimerHeapReference> {
156 public:
157     explicit TimerHeapIterator(RefPtr<ThreadTimerHeapItem>* pointer) : m_pointer(pointer) { checkConsistency(); }
158
159     TimerHeapIterator& operator++() { checkConsistency(); ++m_pointer; checkConsistency(); return *this; }
160     TimerHeapIterator operator++(int) { checkConsistency(1); return TimerHeapIterator(m_pointer++); }
161
162     TimerHeapIterator& operator--() { checkConsistency(); --m_pointer; checkConsistency(); return *this; }
163     TimerHeapIterator operator--(int) { checkConsistency(-1); return TimerHeapIterator(m_pointer--); }
164
165     TimerHeapIterator& operator+=(ptrdiff_t i) { checkConsistency(); m_pointer += i; checkConsistency(); return *this; }
166     TimerHeapIterator& operator-=(ptrdiff_t i) { checkConsistency(); m_pointer -= i; checkConsistency(); return *this; }
167
168     TimerHeapReference operator*() const { return TimerHeapReference(*m_pointer); }
169     TimerHeapReference operator[](ptrdiff_t i) const { return TimerHeapReference(m_pointer[i]); }
170     RefPtr<ThreadTimerHeapItem>& operator->() const { return *m_pointer; }
171
172 private:
173     void checkConsistency(ptrdiff_t offset = 0) const
174     {
175         ASSERT(m_pointer >= threadGlobalTimerHeap().data());
176         ASSERT(m_pointer <= threadGlobalTimerHeap().data() + threadGlobalTimerHeap().size());
177         ASSERT_UNUSED(offset, m_pointer + offset >= threadGlobalTimerHeap().data());
178         ASSERT_UNUSED(offset, m_pointer + offset <= threadGlobalTimerHeap().data() + threadGlobalTimerHeap().size());
179     }
180
181     friend bool operator==(TimerHeapIterator, TimerHeapIterator);
182     friend bool operator!=(TimerHeapIterator, TimerHeapIterator);
183     friend bool operator<(TimerHeapIterator, TimerHeapIterator);
184     friend bool operator>(TimerHeapIterator, TimerHeapIterator);
185     friend bool operator<=(TimerHeapIterator, TimerHeapIterator);
186     friend bool operator>=(TimerHeapIterator, TimerHeapIterator);
187     
188     friend TimerHeapIterator operator+(TimerHeapIterator, size_t);
189     friend TimerHeapIterator operator+(size_t, TimerHeapIterator);
190     
191     friend TimerHeapIterator operator-(TimerHeapIterator, size_t);
192     friend ptrdiff_t operator-(TimerHeapIterator, TimerHeapIterator);
193
194     RefPtr<ThreadTimerHeapItem>* m_pointer;
195 };
196
197 inline bool operator==(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer == b.m_pointer; }
198 inline bool operator!=(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer != b.m_pointer; }
199 inline bool operator<(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer < b.m_pointer; }
200 inline bool operator>(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer > b.m_pointer; }
201 inline bool operator<=(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer <= b.m_pointer; }
202 inline bool operator>=(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer >= b.m_pointer; }
203
204 inline TimerHeapIterator operator+(TimerHeapIterator a, size_t b) { return TimerHeapIterator(a.m_pointer + b); }
205 inline TimerHeapIterator operator+(size_t a, TimerHeapIterator b) { return TimerHeapIterator(a + b.m_pointer); }
206
207 inline TimerHeapIterator operator-(TimerHeapIterator a, size_t b) { return TimerHeapIterator(a.m_pointer - b); }
208 inline ptrdiff_t operator-(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer - b.m_pointer; }
209
210 // ----------------
211
212 class TimerHeapLessThanFunction {
213 public:
214     static bool compare(const TimerBase& a, const RefPtr<ThreadTimerHeapItem>& b)
215     {
216         return compare(a.m_heapItem->time, a.m_heapItem->insertionOrder, b->time, b->insertionOrder);
217     }
218
219     static bool compare(const RefPtr<ThreadTimerHeapItem>& a, const TimerBase& b)
220     {
221         return compare(a->time, a->insertionOrder, b.m_heapItem->time, b.m_heapItem->insertionOrder);
222     }
223
224     bool operator()(const RefPtr<ThreadTimerHeapItem>& a, const RefPtr<ThreadTimerHeapItem>& b) const
225     {
226         return compare(a->time, a->insertionOrder, b->time, b->insertionOrder);
227     }
228
229 private:
230     static bool compare(MonotonicTime aTime, unsigned aOrder, MonotonicTime bTime, unsigned bOrder)
231     {
232         // The comparisons below are "backwards" because the heap puts the largest
233         // element first and we want the lowest time to be the first one in the heap.
234         if (bTime != aTime)
235             return bTime < aTime;
236         // We need to look at the difference of the insertion orders instead of comparing the two
237         // outright in case of overflow.
238         unsigned difference = aOrder - bOrder;
239         return difference < std::numeric_limits<unsigned>::max() / 2;
240     }
241 };
242
243 // ----------------
244
245 static bool shouldSuppressThreadSafetyCheck()
246 {
247 #if PLATFORM(IOS_FAMILY)
248     return WebThreadIsEnabled() || applicationSDKVersion() < DYLD_IOS_VERSION_12_0;
249 #elif PLATFORM(MAC)
250     return !isInWebProcess() && applicationSDKVersion() < DYLD_MACOSX_VERSION_10_14;
251 #else
252     return false;
253 #endif
254 }
255
256 TimerBase::TimerBase()
257 {
258 }
259
260 TimerBase::~TimerBase()
261 {
262     ASSERT(canAccessThreadLocalDataForThread(m_thread.get()));
263     RELEASE_ASSERT(canAccessThreadLocalDataForThread(m_thread.get()) || shouldSuppressThreadSafetyCheck());
264     stop();
265     ASSERT(!inHeap());
266     if (m_heapItem)
267         m_heapItem->clearTimer();
268     m_unalignedNextFireTime = MonotonicTime::nan();
269 }
270
271 void TimerBase::start(Seconds nextFireInterval, Seconds repeatInterval)
272 {
273     ASSERT(canAccessThreadLocalDataForThread(m_thread.get()));
274
275     m_repeatInterval = repeatInterval;
276     setNextFireTime(MonotonicTime::now() + nextFireInterval);
277 }
278
279 void TimerBase::stop()
280 {
281     ASSERT(canAccessThreadLocalDataForThread(m_thread.get()));
282
283     m_repeatInterval = 0_s;
284     setNextFireTime(MonotonicTime { });
285
286     ASSERT(!static_cast<bool>(nextFireTime()));
287     ASSERT(m_repeatInterval == 0_s);
288     ASSERT(!inHeap());
289 }
290
291 Seconds TimerBase::nextFireInterval() const
292 {
293     ASSERT(isActive());
294     ASSERT(m_heapItem);
295     MonotonicTime current = MonotonicTime::now();
296     auto fireTime = nextFireTime();
297     if (fireTime < current)
298         return 0_s;
299     return fireTime - current;
300 }
301
302 inline void TimerBase::checkHeapIndex() const
303 {
304 #if !ASSERT_DISABLED
305     ASSERT(m_heapItem);
306     auto& heap = m_heapItem->timerHeap();
307     ASSERT(&heap == &threadGlobalTimerHeap());
308     ASSERT(!heap.isEmpty());
309     ASSERT(m_heapItem->isInHeap());
310     ASSERT(m_heapItem->heapIndex() < m_heapItem->timerHeap().size());
311     ASSERT(heap[m_heapItem->heapIndex()] == m_heapItem);
312     for (unsigned i = 0, size = heap.size(); i < size; i++)
313         ASSERT(heap[i]->heapIndex() == i);
314 #endif
315 }
316
317 inline void TimerBase::checkConsistency() const
318 {
319     // Timers should be in the heap if and only if they have a non-zero next fire time.
320     ASSERT(inHeap() == static_cast<bool>(nextFireTime()));
321     if (inHeap())
322         checkHeapIndex();
323 }
324
325 void TimerBase::heapDecreaseKey()
326 {
327     ASSERT(static_cast<bool>(nextFireTime()));
328     ASSERT(m_heapItem);
329     checkHeapIndex();
330     auto* heapData = m_heapItem->timerHeap().data();
331     push_heap(TimerHeapIterator(heapData), TimerHeapIterator(heapData + m_heapItem->heapIndex() + 1), TimerHeapLessThanFunction());
332     checkHeapIndex();
333 }
334
335 inline void TimerBase::heapDelete()
336 {
337     ASSERT(!static_cast<bool>(nextFireTime()));
338     heapPop();
339     m_heapItem->timerHeap().removeLast();
340     m_heapItem->setNotInHeap();
341 }
342
343 void TimerBase::heapDeleteMin()
344 {
345     ASSERT(!static_cast<bool>(nextFireTime()));
346     heapPopMin();
347     m_heapItem->timerHeap().removeLast();
348     m_heapItem->setNotInHeap();
349 }
350
351 inline void TimerBase::heapIncreaseKey()
352 {
353     ASSERT(static_cast<bool>(nextFireTime()));
354     heapPop();
355     heapDecreaseKey();
356 }
357
358 inline void TimerBase::heapInsert()
359 {
360     ASSERT(!inHeap());
361     ASSERT(m_heapItem);
362     auto& heap = m_heapItem->timerHeap();
363     heap.append(m_heapItem.copyRef());
364     m_heapItem->setHeapIndex(heap.size() - 1);
365     heapDecreaseKey();
366 }
367
368 inline void TimerBase::heapPop()
369 {
370     ASSERT(m_heapItem);
371     // Temporarily force this timer to have the minimum key so we can pop it.
372     MonotonicTime fireTime = m_heapItem->time;
373     m_heapItem->time = -MonotonicTime::infinity();
374     heapDecreaseKey();
375     heapPopMin();
376     m_heapItem->time = fireTime;
377 }
378
379 void TimerBase::heapPopMin()
380 {
381     ASSERT(m_heapItem == m_heapItem->timerHeap().first());
382     checkHeapIndex();
383     auto& heap = m_heapItem->timerHeap();
384     auto* heapData = heap.data();
385     pop_heap(TimerHeapIterator(heapData), TimerHeapIterator(heapData + heap.size()), TimerHeapLessThanFunction());
386     checkHeapIndex();
387     ASSERT(m_heapItem == m_heapItem->timerHeap().last());
388 }
389
390 void TimerBase::heapDeleteNullMin(ThreadTimerHeap& heap)
391 {
392     RELEASE_ASSERT(!heap.first()->hasTimer());
393     heap.first()->time = -MonotonicTime::infinity();
394     auto* heapData = heap.data();
395     pop_heap(TimerHeapIterator(heapData), TimerHeapIterator(heapData + heap.size()), TimerHeapLessThanFunction());
396     heap.removeLast();
397 }
398
399 static inline bool parentHeapPropertyHolds(const TimerBase* current, const ThreadTimerHeap& heap, unsigned currentIndex)
400 {
401     if (!currentIndex)
402         return true;
403     unsigned parentIndex = (currentIndex - 1) / 2;
404     return TimerHeapLessThanFunction::compare(*current, heap[parentIndex]);
405 }
406
407 static inline bool childHeapPropertyHolds(const TimerBase* current, const ThreadTimerHeap& heap, unsigned childIndex)
408 {
409     if (childIndex >= heap.size())
410         return true;
411     return TimerHeapLessThanFunction::compare(heap[childIndex], *current);
412 }
413
414 bool TimerBase::hasValidHeapPosition() const
415 {
416     ASSERT(nextFireTime());
417     ASSERT(m_heapItem);
418     if (!inHeap())
419         return false;
420     // Check if the heap property still holds with the new fire time. If it does we don't need to do anything.
421     // This assumes that the STL heap is a standard binary heap. In an unlikely event it is not, the assertions
422     // in updateHeapIfNeeded() will get hit.
423     const auto& heap = m_heapItem->timerHeap();
424     unsigned heapIndex = m_heapItem->heapIndex();
425     if (!parentHeapPropertyHolds(this, heap, heapIndex))
426         return false;
427     unsigned childIndex1 = 2 * heapIndex + 1;
428     unsigned childIndex2 = childIndex1 + 1;
429     return childHeapPropertyHolds(this, heap, childIndex1) && childHeapPropertyHolds(this, heap, childIndex2);
430 }
431
432 void TimerBase::updateHeapIfNeeded(MonotonicTime oldTime)
433 {
434     auto fireTime = nextFireTime();
435     if (fireTime && hasValidHeapPosition())
436         return;
437
438 #if !ASSERT_DISABLED
439     Optional<unsigned> oldHeapIndex;
440     if (m_heapItem->isInHeap())
441         oldHeapIndex = m_heapItem->heapIndex();
442 #endif
443
444     if (!oldTime)
445         heapInsert();
446     else if (!fireTime)
447         heapDelete();
448     else if (fireTime < oldTime)
449         heapDecreaseKey();
450     else
451         heapIncreaseKey();
452
453 #if !ASSERT_DISABLED
454     Optional<unsigned> newHeapIndex;
455     if (m_heapItem->isInHeap())
456         newHeapIndex = m_heapItem->heapIndex();
457     ASSERT(newHeapIndex != oldHeapIndex);
458 #endif
459
460     ASSERT(!inHeap() || hasValidHeapPosition());
461 }
462
463 void TimerBase::setNextFireTime(MonotonicTime newTime)
464 {
465     ASSERT(canAccessThreadLocalDataForThread(m_thread.get()));
466     RELEASE_ASSERT(canAccessThreadLocalDataForThread(m_thread.get()) || shouldSuppressThreadSafetyCheck());
467     bool timerHasBeenDeleted = std::isnan(m_unalignedNextFireTime);
468     RELEASE_ASSERT_WITH_SECURITY_IMPLICATION(!timerHasBeenDeleted);
469
470     if (m_unalignedNextFireTime != newTime) {
471         RELEASE_ASSERT(!std::isnan(newTime));
472         m_unalignedNextFireTime = newTime;
473     }
474
475     // Keep heap valid while changing the next-fire time.
476     MonotonicTime oldTime = nextFireTime();
477     // Don't realign zero-delay timers.
478     if (newTime) {
479         if (auto newAlignedTime = alignedFireTime(newTime))
480             newTime = newAlignedTime.value();
481     }
482
483     if (oldTime != newTime) {
484         // FIXME: This should be part of ThreadTimers, or another per-thread structure.
485         static std::atomic<unsigned> currentHeapInsertionOrder;
486         auto newOrder = currentHeapInsertionOrder++;
487
488         if (!m_heapItem)
489             m_heapItem = ThreadTimerHeapItem::create(*this, newTime, 0);
490         m_heapItem->time = newTime;
491         m_heapItem->insertionOrder = newOrder;
492
493         bool wasFirstTimerInHeap = m_heapItem->isFirstInHeap();
494
495         updateHeapIfNeeded(oldTime);
496
497         bool isFirstTimerInHeap = m_heapItem->isFirstInHeap();
498
499         if (wasFirstTimerInHeap || isFirstTimerInHeap)
500             threadGlobalData().threadTimers().updateSharedTimer();
501     }
502
503     checkConsistency();
504 }
505
506 void TimerBase::fireTimersInNestedEventLoop()
507 {
508     // Redirect to ThreadTimers.
509     threadGlobalData().threadTimers().fireTimersInNestedEventLoop();
510 }
511
512 void TimerBase::didChangeAlignmentInterval()
513 {
514     setNextFireTime(m_unalignedNextFireTime);
515 }
516
517 Seconds TimerBase::nextUnalignedFireInterval() const
518 {
519     ASSERT(isActive());
520     auto result = std::max(m_unalignedNextFireTime - MonotonicTime::now(), 0_s);
521     RELEASE_ASSERT(std::isfinite(result));
522     return result;
523 }
524
525 } // namespace WebCore
526