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