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 "platform/Timer.h" 29 30 #include "platform/PlatformThreadData.h" 31 #include "platform/ThreadTimers.h" 32 #include "wtf/CurrentTime.h" 33 #include "wtf/HashSet.h" 34 #include <limits.h> 35 #include <math.h> 36 #include <limits> 37 38 using namespace std; 39 40 namespace WebCore { 41 42 class TimerHeapReference; 43 44 // Timers are stored in a heap data structure, used to implement a priority queue. 45 // This allows us to efficiently determine which timer needs to fire the soonest. 46 // Then we set a single shared system timer to fire at that time. 47 // 48 // When a timer's "next fire time" changes, we need to move it around in the priority queue. 49 static Vector<TimerBase*>& threadGlobalTimerHeap() 50 { 51 return PlatformThreadData::current().threadTimers().timerHeap(); 52 } 53 // ---------------- 54 55 class TimerHeapPointer { 56 public: 57 TimerHeapPointer(TimerBase** pointer) : m_pointer(pointer) { } 58 TimerHeapReference operator*() const; 59 TimerBase* operator->() const { return *m_pointer; } 60 private: 61 TimerBase** m_pointer; 62 }; 63 64 class TimerHeapReference { 65 public: 66 TimerHeapReference(TimerBase*& reference) : m_reference(reference) { } 67 operator TimerBase*() const { return m_reference; } 68 TimerHeapPointer operator&() const { return &m_reference; } 69 TimerHeapReference& operator=(TimerBase*); 70 TimerHeapReference& operator=(TimerHeapReference); 71 private: 72 TimerBase*& m_reference; 73 }; 74 75 inline TimerHeapReference TimerHeapPointer::operator*() const 76 { 77 return *m_pointer; 78 } 79 80 inline TimerHeapReference& TimerHeapReference::operator=(TimerBase* timer) 81 { 82 m_reference = timer; 83 Vector<TimerBase*>& heap = timer->timerHeap(); 84 if (&m_reference >= heap.data() && &m_reference < heap.data() + heap.size()) 85 timer->m_heapIndex = &m_reference - heap.data(); 86 return *this; 87 } 88 89 inline TimerHeapReference& TimerHeapReference::operator=(TimerHeapReference b) 90 { 91 TimerBase* timer = b; 92 return *this = timer; 93 } 94 95 inline void swap(TimerHeapReference a, TimerHeapReference b) 96 { 97 TimerBase* timerA = a; 98 TimerBase* timerB = b; 99 100 // Invoke the assignment operator, since that takes care of updating m_heapIndex. 101 a = timerB; 102 b = timerA; 103 } 104 105 // ---------------- 106 107 // Class to represent iterators in the heap when calling the standard library heap algorithms. 108 // Uses a custom pointer and reference type that update indices for pointers in the heap. 109 class TimerHeapIterator : public iterator<random_access_iterator_tag, TimerBase*, ptrdiff_t, TimerHeapPointer, TimerHeapReference> { 110 public: 111 explicit TimerHeapIterator(TimerBase** pointer) : m_pointer(pointer) { checkConsistency(); } 112 113 TimerHeapIterator& operator++() { checkConsistency(); ++m_pointer; checkConsistency(); return *this; } 114 TimerHeapIterator operator++(int) { checkConsistency(1); return TimerHeapIterator(m_pointer++); } 115 116 TimerHeapIterator& operator--() { checkConsistency(); --m_pointer; checkConsistency(); return *this; } 117 TimerHeapIterator operator--(int) { checkConsistency(-1); return TimerHeapIterator(m_pointer--); } 118 119 TimerHeapIterator& operator+=(ptrdiff_t i) { checkConsistency(); m_pointer += i; checkConsistency(); return *this; } 120 TimerHeapIterator& operator-=(ptrdiff_t i) { checkConsistency(); m_pointer -= i; checkConsistency(); return *this; } 121 122 TimerHeapReference operator*() const { return TimerHeapReference(*m_pointer); } 123 TimerHeapReference operator[](ptrdiff_t i) const { return TimerHeapReference(m_pointer[i]); } 124 TimerBase* operator->() const { return *m_pointer; } 125 126 private: 127 void checkConsistency(ptrdiff_t offset = 0) const 128 { 129 ASSERT(m_pointer >= threadGlobalTimerHeap().data()); 130 ASSERT(m_pointer <= threadGlobalTimerHeap().data() + threadGlobalTimerHeap().size()); 131 ASSERT_UNUSED(offset, m_pointer + offset >= threadGlobalTimerHeap().data()); 132 ASSERT_UNUSED(offset, m_pointer + offset <= threadGlobalTimerHeap().data() + threadGlobalTimerHeap().size()); 133 } 134 135 friend bool operator==(TimerHeapIterator, TimerHeapIterator); 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 142 friend TimerHeapIterator operator+(TimerHeapIterator, size_t); 143 friend TimerHeapIterator operator+(size_t, TimerHeapIterator); 144 145 friend TimerHeapIterator operator-(TimerHeapIterator, size_t); 146 friend ptrdiff_t operator-(TimerHeapIterator, TimerHeapIterator); 147 148 TimerBase** m_pointer; 149 }; 150 151 inline bool operator==(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer == b.m_pointer; } 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 158 inline TimerHeapIterator operator+(TimerHeapIterator a, size_t b) { return TimerHeapIterator(a.m_pointer + b); } 159 inline TimerHeapIterator operator+(size_t a, TimerHeapIterator b) { return TimerHeapIterator(a + b.m_pointer); } 160 161 inline TimerHeapIterator operator-(TimerHeapIterator a, size_t b) { return TimerHeapIterator(a.m_pointer - b); } 162 inline ptrdiff_t operator-(TimerHeapIterator a, TimerHeapIterator b) { return a.m_pointer - b.m_pointer; } 163 164 // ---------------- 165 166 class TimerHeapLessThanFunction { 167 public: 168 bool operator()(const TimerBase*, const TimerBase*) const; 169 }; 170 171 inline bool TimerHeapLessThanFunction::operator()(const TimerBase* a, const TimerBase* b) const 172 { 173 // The comparisons below are "backwards" because the heap puts the largest 174 // element first and we want the lowest time to be the first one in the heap. 175 double aFireTime = a->m_nextFireTime; 176 double bFireTime = b->m_nextFireTime; 177 if (bFireTime != aFireTime) 178 return bFireTime < aFireTime; 179 180 // We need to look at the difference of the insertion orders instead of comparing the two 181 // outright in case of overflow. 182 unsigned difference = a->m_heapInsertionOrder - b->m_heapInsertionOrder; 183 return difference < numeric_limits<unsigned>::max() / 2; 184 } 185 186 // ---------------- 187 188 TimerBase::TimerBase() 189 : m_nextFireTime(0) 190 , m_unalignedNextFireTime(0) 191 , m_repeatInterval(0) 192 , m_heapIndex(-1) 193 , m_cachedThreadGlobalTimerHeap(0) 194 #ifndef NDEBUG 195 , m_thread(currentThread()) 196 #endif 197 { 198 } 199 200 TimerBase::~TimerBase() 201 { 202 stop(); 203 ASSERT(!inHeap()); 204 } 205 206 void TimerBase::start(double nextFireInterval, double repeatInterval, const TraceLocation& caller) 207 { 208 ASSERT(m_thread == currentThread()); 209 210 m_location = caller; 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 PlatformThreadData::current().threadTimers().updateSharedTimer(); 393 } 394 395 checkConsistency(); 396 } 397 398 void TimerBase::fireTimersInNestedEventLoop() 399 { 400 // Redirect to ThreadTimers. 401 PlatformThreadData::current().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
