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) 207 { 208 ASSERT(m_thread == currentThread()); 209 210 m_repeatInterval = repeatInterval; 211 setNextFireTime(monotonicallyIncreasingTime() + nextFireInterval); 212 } 213 214 void TimerBase::stop() 215 { 216 ASSERT(m_thread == currentThread()); 217 218 m_repeatInterval = 0; 219 setNextFireTime(0); 220 221 ASSERT(m_nextFireTime == 0); 222 ASSERT(m_repeatInterval == 0); 223 ASSERT(!inHeap()); 224 } 225 226 double TimerBase::nextFireInterval() const 227 { 228 ASSERT(isActive()); 229 double current = monotonicallyIncreasingTime(); 230 if (m_nextFireTime < current) 231 return 0; 232 return m_nextFireTime - current; 233 } 234 235 inline void TimerBase::checkHeapIndex() const 236 { 237 ASSERT(timerHeap() == threadGlobalTimerHeap()); 238 ASSERT(!timerHeap().isEmpty()); 239 ASSERT(m_heapIndex >= 0); 240 ASSERT(m_heapIndex < static_cast<int>(timerHeap().size())); 241 ASSERT(timerHeap()[m_heapIndex] == this); 242 } 243 244 inline void TimerBase::checkConsistency() const 245 { 246 // Timers should be in the heap if and only if they have a non-zero next fire time. 247 ASSERT(inHeap() == (m_nextFireTime != 0)); 248 if (inHeap()) 249 checkHeapIndex(); 250 } 251 252 void TimerBase::heapDecreaseKey() 253 { 254 ASSERT(m_nextFireTime != 0); 255 checkHeapIndex(); 256 TimerBase** heapData = timerHeap().data(); 257 push_heap(TimerHeapIterator(heapData), TimerHeapIterator(heapData + m_heapIndex + 1), TimerHeapLessThanFunction()); 258 checkHeapIndex(); 259 } 260 261 inline void TimerBase::heapDelete() 262 { 263 ASSERT(m_nextFireTime == 0); 264 heapPop(); 265 timerHeap().removeLast(); 266 m_heapIndex = -1; 267 } 268 269 void TimerBase::heapDeleteMin() 270 { 271 ASSERT(m_nextFireTime == 0); 272 heapPopMin(); 273 timerHeap().removeLast(); 274 m_heapIndex = -1; 275 } 276 277 inline void TimerBase::heapIncreaseKey() 278 { 279 ASSERT(m_nextFireTime != 0); 280 heapPop(); 281 heapDecreaseKey(); 282 } 283 284 inline void TimerBase::heapInsert() 285 { 286 ASSERT(!inHeap()); 287 timerHeap().append(this); 288 m_heapIndex = timerHeap().size() - 1; 289 heapDecreaseKey(); 290 } 291 292 inline void TimerBase::heapPop() 293 { 294 // Temporarily force this timer to have the minimum key so we can pop it. 295 double fireTime = m_nextFireTime; 296 m_nextFireTime = -numeric_limits<double>::infinity(); 297 heapDecreaseKey(); 298 heapPopMin(); 299 m_nextFireTime = fireTime; 300 } 301 302 void TimerBase::heapPopMin() 303 { 304 ASSERT(this == timerHeap().first()); 305 checkHeapIndex(); 306 Vector<TimerBase*>& heap = timerHeap(); 307 TimerBase** heapData = heap.data(); 308 pop_heap(TimerHeapIterator(heapData), TimerHeapIterator(heapData + heap.size()), TimerHeapLessThanFunction()); 309 checkHeapIndex(); 310 ASSERT(this == timerHeap().last()); 311 } 312 313 static inline bool parentHeapPropertyHolds(const TimerBase* current, const Vector<TimerBase*>& heap, unsigned currentIndex) 314 { 315 if (!currentIndex) 316 return true; 317 unsigned parentIndex = (currentIndex - 1) / 2; 318 TimerHeapLessThanFunction compareHeapPosition; 319 return compareHeapPosition(current, heap[parentIndex]); 320 } 321 322 static inline bool childHeapPropertyHolds(const TimerBase* current, const Vector<TimerBase*>& heap, unsigned childIndex) 323 { 324 if (childIndex >= heap.size()) 325 return true; 326 TimerHeapLessThanFunction compareHeapPosition; 327 return compareHeapPosition(heap[childIndex], current); 328 } 329 330 bool TimerBase::hasValidHeapPosition() const 331 { 332 ASSERT(m_nextFireTime); 333 if (!inHeap()) 334 return false; 335 // Check if the heap property still holds with the new fire time. If it does we don't need to do anything. 336 // This assumes that the STL heap is a standard binary heap. In an unlikely event it is not, the assertions 337 // in updateHeapIfNeeded() will get hit. 338 const Vector<TimerBase*>& heap = timerHeap(); 339 if (!parentHeapPropertyHolds(this, heap, m_heapIndex)) 340 return false; 341 unsigned childIndex1 = 2 * m_heapIndex + 1; 342 unsigned childIndex2 = childIndex1 + 1; 343 return childHeapPropertyHolds(this, heap, childIndex1) && childHeapPropertyHolds(this, heap, childIndex2); 344 } 345 346 void TimerBase::updateHeapIfNeeded(double oldTime) 347 { 348 if (m_nextFireTime && hasValidHeapPosition()) 349 return; 350 #ifndef NDEBUG 351 int oldHeapIndex = m_heapIndex; 352 #endif 353 if (!oldTime) 354 heapInsert(); 355 else if (!m_nextFireTime) 356 heapDelete(); 357 else if (m_nextFireTime < oldTime) 358 heapDecreaseKey(); 359 else 360 heapIncreaseKey(); 361 ASSERT(m_heapIndex != oldHeapIndex); 362 ASSERT(!inHeap() || hasValidHeapPosition()); 363 } 364 365 void TimerBase::setNextFireTime(double newUnalignedTime) 366 { 367 ASSERT(m_thread == currentThread()); 368 369 if (m_unalignedNextFireTime != newUnalignedTime) 370 m_unalignedNextFireTime = newUnalignedTime; 371 372 // Accessing thread global data is slow. Cache the heap pointer. 373 if (!m_cachedThreadGlobalTimerHeap) 374 m_cachedThreadGlobalTimerHeap = &threadGlobalTimerHeap(); 375 376 // Keep heap valid while changing the next-fire time. 377 double oldTime = m_nextFireTime; 378 double newTime = alignedFireTime(newUnalignedTime); 379 if (oldTime != newTime) { 380 m_nextFireTime = newTime; 381 static unsigned currentHeapInsertionOrder; 382 m_heapInsertionOrder = currentHeapInsertionOrder++; 383 384 bool wasFirstTimerInHeap = m_heapIndex == 0; 385 386 updateHeapIfNeeded(oldTime); 387 388 bool isFirstTimerInHeap = m_heapIndex == 0; 389 390 if (wasFirstTimerInHeap || isFirstTimerInHeap) 391 PlatformThreadData::current().threadTimers().updateSharedTimer(); 392 } 393 394 checkConsistency(); 395 } 396 397 void TimerBase::fireTimersInNestedEventLoop() 398 { 399 // Redirect to ThreadTimers. 400 PlatformThreadData::current().threadTimers().fireTimersInNestedEventLoop(); 401 } 402 403 void TimerBase::didChangeAlignmentInterval() 404 { 405 setNextFireTime(m_unalignedNextFireTime); 406 } 407 408 double TimerBase::nextUnalignedFireInterval() const 409 { 410 ASSERT(isActive()); 411 return max(m_unalignedNextFireTime - monotonicallyIncreasingTime(), 0.0); 412 } 413 414 } // namespace WebCore 415 416
