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