Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(43)

Side by Side Diff: Source/platform/Timer.cpp

Issue 1134523002: Implement timers by posting delayed tasks (Closed) Base URL: svn://svn.chromium.org/blink/trunk
Patch Set: Gyp tweak. Created 5 years, 7 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
OLDNEW
1 /* 1 /*
2 * Copyright (C) 2006, 2008 Apple Inc. All rights reserved. 2 * Copyright (C) 2006, 2008 Apple Inc. All rights reserved.
3 * Copyright (C) 2009 Google Inc. All rights reserved. 3 * Copyright (C) 2009 Google Inc. All rights reserved.
4 * 4 *
5 * Redistribution and use in source and binary forms, with or without 5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions 6 * modification, are permitted provided that the following conditions
7 * are met: 7 * are met:
8 * 1. Redistributions of source code must retain the above copyright 8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer. 9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright 10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the 11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution. 12 * documentation and/or other materials provided with the distribution.
13 * 13 *
14 * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY 14 * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
15 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 15 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE COMPUTER, INC. OR 17 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE COMPUTER, INC. OR
18 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 18 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 19 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 20 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY 21 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 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. 24 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */ 25 */
26 26
27 #include "config.h" 27 #include "config.h"
28 #include "platform/Timer.h" 28 #include "platform/Timer.h"
29 29
30 #include "platform/PlatformThreadData.h" 30 #include "platform/TraceEvent.h"
31 #include "platform/ThreadTimers.h" 31 #include "public/platform/Platform.h"
32 #include "public/platform/WebScheduler.h"
32 #include "wtf/Atomics.h" 33 #include "wtf/Atomics.h"
33 #include "wtf/CurrentTime.h" 34 #include "wtf/CurrentTime.h"
34 #include "wtf/HashSet.h" 35 #include "wtf/HashSet.h"
35 #include <algorithm> 36 #include <algorithm>
36 #include <limits.h> 37 #include <limits.h>
37 #include <limits> 38 #include <limits>
38 #include <math.h> 39 #include <math.h>
39 40
40 namespace blink { 41 namespace blink {
41 42
42 class TimerHeapReference;
43
44 // Timers are stored in a heap data structure, used to implement a priority queu e.
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 pri ority 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_heapI ndex.
101 a = timerB;
102 b = timerA;
103 }
104
105 // ----------------
106
107 // Class to represent iterators in the heap when calling the standard library he ap algorithms.
108 // Uses a custom pointer and reference type that update indices for pointers in the heap.
109 class TimerHeapIterator : public std::iterator<std::random_access_iterator_tag, TimerBase*, ptrdiff_t, TimerHeapPointer, TimerHeapReference> {
110 public:
111 explicit TimerHeapIterator(TimerBase** pointer) : m_pointer(pointer) { check Consistency(); }
112
113 TimerHeapIterator& operator++() { checkConsistency(); ++m_pointer; checkCons istency(); return *this; }
114 TimerHeapIterator operator++(int) { checkConsistency(1); return TimerHeapIte rator(m_pointer++); }
115
116 TimerHeapIterator& operator--() { checkConsistency(); --m_pointer; checkCons istency(); return *this; }
117 TimerHeapIterator operator--(int) { checkConsistency(-1); return TimerHeapIt erator(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() + threadGlobalTimerHe ap().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_po inter == b.m_pointer; }
152 inline bool operator!=(TimerHeapIterator a, TimerHeapIterator b) { return a.m_po inter != b.m_pointer; }
153 inline bool operator<(TimerHeapIterator a, TimerHeapIterator b) { return a.m_poi nter < b.m_pointer; }
154 inline bool operator>(TimerHeapIterator a, TimerHeapIterator b) { return a.m_poi nter > b.m_pointer; }
155 inline bool operator<=(TimerHeapIterator a, TimerHeapIterator b) { return a.m_po inter <= b.m_pointer; }
156 inline bool operator>=(TimerHeapIterator a, TimerHeapIterator b) { return a.m_po inter >= b.m_pointer; }
157
158 inline TimerHeapIterator operator+(TimerHeapIterator a, size_t b) { return Timer HeapIterator(a.m_pointer + b); }
159 inline TimerHeapIterator operator+(size_t a, TimerHeapIterator b) { return Timer HeapIterator(a + b.m_pointer); }
160
161 inline TimerHeapIterator operator-(TimerHeapIterator a, size_t b) { return Timer HeapIterator(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 Time rBase* 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 comp aring the two
181 // outright in case of overflow.
182 unsigned difference = a->m_heapInsertionOrder - b->m_heapInsertionOrder;
183 return difference < std::numeric_limits<unsigned>::max() / 2;
184 }
185
186 // ----------------
187
188 TimerBase::TimerBase() 43 TimerBase::TimerBase()
189 : m_nextFireTime(0) 44 : m_nextFireTime(0)
190 , m_unalignedNextFireTime(0) 45 , m_unalignedNextFireTime(0)
191 , m_repeatInterval(0) 46 , m_repeatInterval(0)
192 , m_heapIndex(-1) 47 , m_cancellableTaskFactory(WTF::bind(&TimerBase::run, this))
193 , m_cachedThreadGlobalTimerHeap(0) 48 , m_webScheduler(Platform::current()->currentThread()->scheduler())
194 #if ENABLE(ASSERT) 49 #if ENABLE(ASSERT)
195 , m_thread(currentThread()) 50 , m_thread(currentThread())
196 #endif 51 #endif
197 { 52 {
198 } 53 }
199 54
200 TimerBase::~TimerBase() 55 TimerBase::~TimerBase()
201 { 56 {
202 stop(); 57 stop();
203 ASSERT(!inHeap());
204 } 58 }
205 59
206 void TimerBase::start(double nextFireInterval, double repeatInterval, const WebT raceLocation& caller) 60 void TimerBase::start(double nextFireInterval, double repeatInterval, const WebT raceLocation& caller)
207 { 61 {
208 ASSERT(m_thread == currentThread()); 62 ASSERT(m_thread == currentThread());
209 63
210 m_location = caller; 64 m_location = caller;
211 m_repeatInterval = repeatInterval; 65 m_repeatInterval = repeatInterval;
212 setNextFireTime(monotonicallyIncreasingTime() + nextFireInterval); 66 setNextFireTime(monotonicallyIncreasingTime(), nextFireInterval);
213 } 67 }
214 68
215 void TimerBase::stop() 69 void TimerBase::stop()
216 { 70 {
217 ASSERT(m_thread == currentThread()); 71 ASSERT(m_thread == currentThread());
218 72
219 m_repeatInterval = 0; 73 m_repeatInterval = 0;
220 setNextFireTime(0); 74 m_nextFireTime = 0;
221 75 m_cancellableTaskFactory.cancel();
222 ASSERT(m_nextFireTime == 0);
223 ASSERT(m_repeatInterval == 0);
224 ASSERT(!inHeap());
225 } 76 }
226 77
227 double TimerBase::nextFireInterval() const 78 double TimerBase::nextFireInterval() const
228 { 79 {
229 ASSERT(isActive()); 80 ASSERT(isActive());
230 double current = monotonicallyIncreasingTime(); 81 double current = monotonicallyIncreasingTime();
231 if (m_nextFireTime < current) 82 if (m_nextFireTime < current)
232 return 0; 83 return 0;
233 return m_nextFireTime - current; 84 return m_nextFireTime - current;
234 } 85 }
235 86
236 inline void TimerBase::checkHeapIndex() const 87 void TimerBase::setNextFireTime(double now, double delay)
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 fir e 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_heapIn dex + 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 = -std::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 Vecto r<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) && childHeapPropertyH olds(this, heap, childIndex2);
345 }
346
347 void TimerBase::updateHeapIfNeeded(double oldTime)
348 {
349 if (m_nextFireTime && hasValidHeapPosition())
350 return;
351 #if ENABLE(ASSERT)
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 { 88 {
368 ASSERT(m_thread == currentThread()); 89 ASSERT(m_thread == currentThread());
369 90
370 if (m_unalignedNextFireTime != newUnalignedTime) 91 m_unalignedNextFireTime = now + delay;
371 m_unalignedNextFireTime = newUnalignedTime;
372 92
373 // Accessing thread global data is slow. Cache the heap pointer. 93 double newTime = alignedFireTime(m_unalignedNextFireTime);
374 if (!m_cachedThreadGlobalTimerHeap) 94 if (m_nextFireTime != newTime) {
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; 95 m_nextFireTime = newTime;
382 static unsigned currentHeapInsertionOrder; 96 // Round the delay up to the nearest millisecond to be consistant with t he
383 m_heapInsertionOrder = atomicAdd(&currentHeapInsertionOrder, 1); 97 // previous behavior of BlinkPlatformImpl::setSharedTimerFireInterval.
384 98 long long delayMs = static_cast<long long>(ceil((newTime - now) * 1000.0 ));
385 bool wasFirstTimerInHeap = m_heapIndex == 0; 99 if (delayMs < 0)
386 100 delayMs = 0;
387 updateHeapIfNeeded(oldTime); 101 m_webScheduler->postTimerTask(m_location, m_cancellableTaskFactory.task( ), delayMs);
kinuko 2015/05/13 08:26:39 Just want to make sure-- so this one actually canc
alex clarke (OOO till 29th) 2015/05/13 08:43:01 Yes it does. We where thinking of changing the nam
Sami 2015/05/13 18:01:26 We could consider introducing a non-thread safe va
388
389 bool isFirstTimerInHeap = m_heapIndex == 0;
390
391 if (wasFirstTimerInHeap || isFirstTimerInHeap)
392 PlatformThreadData::current().threadTimers().updateSharedTimer();
393 } 102 }
394
395 checkConsistency();
396 } 103 }
397 104
398 void TimerBase::didChangeAlignmentInterval() 105 void TimerBase::run()
399 { 106 {
400 setNextFireTime(m_unalignedNextFireTime); 107 TRACE_EVENT0("blink", "TimerBase::run");
108 ASSERT_WITH_MESSAGE(m_thread == currentThread(), "Timer posted by %s %s was run on a different thread", m_location.functionName(), m_location.fileName());
109 TRACE_EVENT_SET_SAMPLING_STATE("blink", "BlinkInternal");
110
111 m_nextFireTime = 0;
112 // Note: repeating timers drift, but this is preserving the functionality of the old timer heap.
113 // See crbug.com/328700.
114 if (m_repeatInterval)
115 setNextFireTime(monotonicallyIncreasingTime(), m_repeatInterval);
116 fired();
117 TRACE_EVENT_SET_SAMPLING_STATE("blink", "Sleeping");
118 }
119
120 void TimerBase::didChangeAlignmentInterval(double now)
121 {
122 setNextFireTime(now, m_unalignedNextFireTime - now);
401 } 123 }
402 124
403 double TimerBase::nextUnalignedFireInterval() const 125 double TimerBase::nextUnalignedFireInterval() const
404 { 126 {
405 ASSERT(isActive()); 127 ASSERT(isActive());
406 return std::max(m_unalignedNextFireTime - monotonicallyIncreasingTime(), 0.0 ); 128 return std::max(m_unalignedNextFireTime - monotonicallyIncreasingTime(), 0.0 );
407 } 129 }
408 130
409 } // namespace blink 131 } // namespace blink
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698