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
44namespace WebCore {
45
46class 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
54static ThreadTimerHeap& threadGlobalTimerHeap()
55{
56 return threadGlobalData().threadTimers().timerHeap();
57}
58#endif
59
60inline 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
69inline RefPtr<ThreadTimerHeapItem> ThreadTimerHeapItem::create(TimerBase& timer, MonotonicTime time, unsigned insertionOrder)
70{
71 return adoptRef(*new ThreadTimerHeapItem { timer, time, insertionOrder });
72}
73
74// ----------------
75
76class TimerHeapPointer {
77public:
78 TimerHeapPointer(RefPtr<ThreadTimerHeapItem>* pointer)
79 : m_pointer(pointer)
80 { }
81
82 TimerHeapReference operator*() const;
83 RefPtr<ThreadTimerHeapItem>& operator->() const { return *m_pointer; }
84private:
85 RefPtr<ThreadTimerHeapItem>* m_pointer;
86};
87
88class TimerHeapReference {
89public:
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
107private:
108 RefPtr<ThreadTimerHeapItem>& m_reference;
109
110 friend void swap(TimerHeapReference a, TimerHeapReference b);
111};
112
113inline TimerHeapReference TimerHeapPointer::operator*() const
114{
115 return TimerHeapReference { *m_pointer };
116}
117
118inline TimerHeapReference& TimerHeapReference::operator=(TimerHeapReference&& other)
119{
120 m_reference = WTFMove(other.m_reference);
121 updateHeapIndex();
122 return *this;
123}
124
125inline TimerHeapReference& TimerHeapReference::operator=(RefPtr<ThreadTimerHeapItem>&& item)
126{
127 m_reference = WTFMove(item);
128 updateHeapIndex();
129 return *this;
130}
131
132inline void TimerHeapReference::swap(TimerHeapReference& other)
133{
134 m_reference.swap(other.m_reference);
135 updateHeapIndex();
136 other.updateHeapIndex();
137}
138
139inline 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
146inline 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.
155class TimerHeapIterator : public std::iterator<std::random_access_iterator_tag, RefPtr<ThreadTimerHeapItem>, ptrdiff_t, TimerHeapPointer, TimerHeapReference> {
156public:
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
172private:
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
197inline bool operator==(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer == b.m_pointer; }
198inline bool operator!=(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer != b.m_pointer; }
199inline bool operator<(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer < b.m_pointer; }
200inline bool operator>(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer > b.m_pointer; }
201inline bool operator<=(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer <= b.m_pointer; }
202inline bool operator>=(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer >= b.m_pointer; }
203
204inline TimerHeapIterator operator+(TimerHeapIterator a, size_t b) { return TimerHeapIterator(a.m_pointer + b); }
205inline TimerHeapIterator operator+(size_t a, TimerHeapIterator b) { return TimerHeapIterator(a + b.m_pointer); }
206
207inline TimerHeapIterator operator-(TimerHeapIterator a, size_t b) { return TimerHeapIterator(a.m_pointer - b); }
208inline ptrdiff_t operator-(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer - b.m_pointer; }
209
210// ----------------
211
212class TimerHeapLessThanFunction {
213public:
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
229private:
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
245static 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
256TimerBase::TimerBase()
257{
258}
259
260TimerBase::~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
271void 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
279void 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
291Seconds 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
302inline 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
317inline 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
325void 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
335inline void TimerBase::heapDelete()
336{
337 ASSERT(!static_cast<bool>(nextFireTime()));
338 heapPop();
339 m_heapItem->timerHeap().removeLast();
340 m_heapItem->setNotInHeap();
341}
342
343void TimerBase::heapDeleteMin()
344{
345 ASSERT(!static_cast<bool>(nextFireTime()));
346 heapPopMin();
347 m_heapItem->timerHeap().removeLast();
348 m_heapItem->setNotInHeap();
349}
350
351inline void TimerBase::heapIncreaseKey()
352{
353 ASSERT(static_cast<bool>(nextFireTime()));
354 heapPop();
355 heapDecreaseKey();
356}
357
358inline 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
368inline 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
379void 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
390void 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
399static 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
407static 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
414bool 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
432void 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
463void 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
506void TimerBase::fireTimersInNestedEventLoop()
507{
508 // Redirect to ThreadTimers.
509 threadGlobalData().threadTimers().fireTimersInNestedEventLoop();
510}
511
512void TimerBase::didChangeAlignmentInterval()
513{
514 setNextFireTime(m_unalignedNextFireTime);
515}
516
517Seconds 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
527