1 | // Copyright (C) 2021 The Qt Company Ltd. |
2 | // Copyright (C) 2016 Intel Corporation. |
3 | // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only |
4 | |
5 | #include <qelapsedtimer.h> |
6 | #include <qcoreapplication.h> |
7 | |
8 | #include "private/qcore_unix_p.h" |
9 | #include "private/qtimerinfo_unix_p.h" |
10 | #include "private/qobject_p.h" |
11 | #include "private/qabstracteventdispatcher_p.h" |
12 | |
13 | #include <sys/times.h> |
14 | |
15 | using namespace std::chrono; |
16 | // Implied by "using namespace std::chrono", but be explicit about it, for grep-ability |
17 | using namespace std::chrono_literals; |
18 | |
19 | QT_BEGIN_NAMESPACE |
20 | |
21 | Q_CORE_EXPORT bool qt_disable_lowpriority_timers=false; |
22 | |
23 | /* |
24 | * Internal functions for manipulating timer data structures. The |
25 | * timerBitVec array is used for keeping track of timer identifiers. |
26 | */ |
27 | |
28 | QTimerInfoList::QTimerInfoList() = default; |
29 | |
30 | steady_clock::time_point QTimerInfoList::updateCurrentTime() const |
31 | { |
32 | currentTime = steady_clock::now(); |
33 | return currentTime; |
34 | } |
35 | |
36 | /*! \internal |
37 | Updates the currentTime member to the current time, and returns \c true if |
38 | the first timer's timeout is in the future (after currentTime). |
39 | |
40 | The list is sorted by timeout, thus it's enough to check the first timer only. |
41 | */ |
42 | bool QTimerInfoList::hasPendingTimers() |
43 | { |
44 | if (timers.isEmpty()) |
45 | return false; |
46 | return updateCurrentTime() < timers.at(i: 0)->timeout; |
47 | } |
48 | |
49 | static bool byTimeout(const QTimerInfo *a, const QTimerInfo *b) |
50 | { return a->timeout < b->timeout; }; |
51 | |
52 | /* |
53 | insert timer info into list |
54 | */ |
55 | void QTimerInfoList::timerInsert(QTimerInfo *ti) |
56 | { |
57 | timers.insert(before: std::upper_bound(first: timers.cbegin(), last: timers.cend(), val: ti, comp: byTimeout), |
58 | t: ti); |
59 | } |
60 | |
61 | static constexpr milliseconds roundToMillisecond(nanoseconds val) |
62 | { |
63 | // always round up |
64 | // worst case scenario is that the first trigger of a 1-ms timer is 0.999 ms late |
65 | return ceil<milliseconds>(d: val); |
66 | } |
67 | |
68 | static_assert(roundToMillisecond(val: 0ns) == 0ms); |
69 | static_assert(roundToMillisecond(val: 1ns) == 1ms); |
70 | static_assert(roundToMillisecond(val: 999'999ns) == 1ms); |
71 | static_assert(roundToMillisecond(val: 1'000'000ns) == 1ms); |
72 | static_assert(roundToMillisecond(val: 999'000'000ns) == 999ms); |
73 | static_assert(roundToMillisecond(val: 999'000'001ns) == 1000ms); |
74 | static_assert(roundToMillisecond(val: 999'999'999ns) == 1000ms); |
75 | static_assert(roundToMillisecond(val: 1s) == 1s); |
76 | |
77 | static constexpr seconds roundToSecs(nanoseconds interval) |
78 | { |
79 | // The very coarse timer is based on full second precision, so we want to |
80 | // round the interval to the closest second, rounding 500ms up to 1s. |
81 | // |
82 | // std::chrono::round() wouldn't work with all multiples of 500 because for the |
83 | // middle point it would round to even: |
84 | // value round() wanted |
85 | // 500 0 1 |
86 | // 1500 2 2 |
87 | // 2500 2 3 |
88 | |
89 | auto secs = duration_cast<seconds>(d: interval); |
90 | const nanoseconds frac = interval - secs; |
91 | if (frac >= 500ms) |
92 | ++secs; |
93 | return secs; |
94 | } |
95 | |
96 | static void calculateCoarseTimerTimeout(QTimerInfo *t, steady_clock::time_point now) |
97 | { |
98 | // The coarse timer works like this: |
99 | // - interval under 40 ms: round to even |
100 | // - between 40 and 99 ms: round to multiple of 4 |
101 | // - otherwise: try to wake up at a multiple of 25 ms, with a maximum error of 5% |
102 | // |
103 | // We try to wake up at the following second-fraction, in order of preference: |
104 | // 0 ms |
105 | // 500 ms |
106 | // 250 ms or 750 ms |
107 | // 200, 400, 600, 800 ms |
108 | // other multiples of 100 |
109 | // other multiples of 50 |
110 | // other multiples of 25 |
111 | // |
112 | // The objective is to make most timers wake up at the same time, thereby reducing CPU wakeups. |
113 | |
114 | Q_ASSERT(t->interval >= 20ms); |
115 | |
116 | const auto timeoutInSecs = time_point_cast<seconds>(t: t->timeout); |
117 | |
118 | auto recalculate = [&](const milliseconds frac) { |
119 | t->timeout = timeoutInSecs + frac; |
120 | if (t->timeout < now) |
121 | t->timeout += t->interval; |
122 | }; |
123 | |
124 | // Calculate how much we can round and still keep within 5% error |
125 | milliseconds interval = roundToMillisecond(val: t->interval); |
126 | const milliseconds absMaxRounding = interval / 20; |
127 | |
128 | auto fracMsec = duration_cast<milliseconds>(d: t->timeout - timeoutInSecs); |
129 | |
130 | if (interval < 100ms && interval != 25ms && interval != 50ms && interval != 75ms) { |
131 | auto fracCount = fracMsec.count(); |
132 | // special mode for timers of less than 100 ms |
133 | if (interval < 50ms) { |
134 | // round to even |
135 | // round towards multiples of 50 ms |
136 | bool roundUp = (fracCount % 50) >= 25; |
137 | fracCount >>= 1; |
138 | fracCount |= roundUp; |
139 | fracCount <<= 1; |
140 | } else { |
141 | // round to multiple of 4 |
142 | // round towards multiples of 100 ms |
143 | bool roundUp = (fracCount % 100) >= 50; |
144 | fracCount >>= 2; |
145 | fracCount |= roundUp; |
146 | fracCount <<= 2; |
147 | } |
148 | fracMsec = milliseconds{fracCount}; |
149 | recalculate(fracMsec); |
150 | return; |
151 | } |
152 | |
153 | milliseconds min = std::max(a: 0ms, b: fracMsec - absMaxRounding); |
154 | milliseconds max = std::min(a: 1000ms, b: fracMsec + absMaxRounding); |
155 | |
156 | // find the boundary that we want, according to the rules above |
157 | // extra rules: |
158 | // 1) whatever the interval, we'll take any round-to-the-second timeout |
159 | if (min == 0ms) { |
160 | fracMsec = 0ms; |
161 | recalculate(fracMsec); |
162 | return; |
163 | } else if (max == 1000ms) { |
164 | fracMsec = 1000ms; |
165 | recalculate(fracMsec); |
166 | return; |
167 | } |
168 | |
169 | milliseconds wantedBoundaryMultiple{25}; |
170 | |
171 | // 2) if the interval is a multiple of 500 ms and > 5000 ms, we'll always round |
172 | // towards a round-to-the-second |
173 | // 3) if the interval is a multiple of 500 ms, we'll round towards the nearest |
174 | // multiple of 500 ms |
175 | if ((interval % 500) == 0ms) { |
176 | if (interval >= 5s) { |
177 | fracMsec = fracMsec >= 500ms ? max : min; |
178 | recalculate(fracMsec); |
179 | return; |
180 | } else { |
181 | wantedBoundaryMultiple = 500ms; |
182 | } |
183 | } else if ((interval % 50) == 0ms) { |
184 | // 4) same for multiples of 250, 200, 100, 50 |
185 | milliseconds mult50 = interval / 50; |
186 | if ((mult50 % 4) == 0ms) { |
187 | // multiple of 200 |
188 | wantedBoundaryMultiple = 200ms; |
189 | } else if ((mult50 % 2) == 0ms) { |
190 | // multiple of 100 |
191 | wantedBoundaryMultiple = 100ms; |
192 | } else if ((mult50 % 5) == 0ms) { |
193 | // multiple of 250 |
194 | wantedBoundaryMultiple = 250ms; |
195 | } else { |
196 | // multiple of 50 |
197 | wantedBoundaryMultiple = 50ms; |
198 | } |
199 | } |
200 | |
201 | milliseconds base = (fracMsec / wantedBoundaryMultiple) * wantedBoundaryMultiple; |
202 | milliseconds middlepoint = base + wantedBoundaryMultiple / 2; |
203 | if (fracMsec < middlepoint) |
204 | fracMsec = qMax(a: base, b: min); |
205 | else |
206 | fracMsec = qMin(a: base + wantedBoundaryMultiple, b: max); |
207 | |
208 | recalculate(fracMsec); |
209 | } |
210 | |
211 | static void calculateNextTimeout(QTimerInfo *t, steady_clock::time_point now) |
212 | { |
213 | switch (t->timerType) { |
214 | case Qt::PreciseTimer: |
215 | case Qt::CoarseTimer: |
216 | t->timeout += t->interval; |
217 | if (t->timeout < now) { |
218 | t->timeout = now; |
219 | t->timeout += t->interval; |
220 | } |
221 | if (t->timerType == Qt::CoarseTimer) |
222 | calculateCoarseTimerTimeout(t, now); |
223 | return; |
224 | |
225 | case Qt::VeryCoarseTimer: |
226 | // t->interval already rounded to full seconds in registerTimer() |
227 | t->timeout += t->interval; |
228 | if (t->timeout <= now) |
229 | t->timeout = time_point_cast<seconds>(t: now + t->interval); |
230 | break; |
231 | } |
232 | } |
233 | |
234 | /* |
235 | Returns the time to wait for the first timer that has not been activated yet, |
236 | otherwise returns std::nullopt. |
237 | */ |
238 | std::optional<QTimerInfoList::Duration> QTimerInfoList::timerWait() |
239 | { |
240 | steady_clock::time_point now = updateCurrentTime(); |
241 | |
242 | auto isWaiting = [](QTimerInfo *tinfo) { return !tinfo->activateRef; }; |
243 | // Find first waiting timer not already active |
244 | auto it = std::find_if(first: timers.cbegin(), last: timers.cend(), pred: isWaiting); |
245 | if (it == timers.cend()) |
246 | return std::nullopt; |
247 | |
248 | Duration timeToWait = (*it)->timeout - now; |
249 | if (timeToWait > 0ns) |
250 | return roundToMillisecond(val: timeToWait); |
251 | return 0ms; |
252 | } |
253 | |
254 | /* |
255 | Returns the timer's remaining time in milliseconds with the given timerId. |
256 | If the timer id is not found in the list, the returned value will be \c{Duration::min()}. |
257 | If the timer is overdue, the returned value will be 0. |
258 | */ |
259 | QTimerInfoList::Duration QTimerInfoList::remainingDuration(Qt::TimerId timerId) const |
260 | { |
261 | const steady_clock::time_point now = updateCurrentTime(); |
262 | |
263 | auto it = findTimerById(timerId); |
264 | if (it == timers.cend()) { |
265 | #ifndef QT_NO_DEBUG |
266 | qWarning(msg: "QTimerInfoList::timerRemainingTime: timer id %i not found" , int(timerId)); |
267 | #endif |
268 | return Duration::min(); |
269 | } |
270 | |
271 | const QTimerInfo *t = *it; |
272 | if (now < t->timeout) // time to wait |
273 | return t->timeout - now; |
274 | return 0ms; |
275 | } |
276 | |
277 | void QTimerInfoList::registerTimer(Qt::TimerId timerId, QTimerInfoList::Duration interval, |
278 | Qt::TimerType timerType, QObject *object) |
279 | { |
280 | // correct the timer type first |
281 | if (timerType == Qt::CoarseTimer) { |
282 | // this timer has up to 5% coarseness |
283 | // so our boundaries are 20 ms and 20 s |
284 | // below 20 ms, 5% inaccuracy is below 1 ms, so we convert to high precision |
285 | // above 20 s, 5% inaccuracy is above 1 s, so we convert to VeryCoarseTimer |
286 | if (interval >= 20s) |
287 | timerType = Qt::VeryCoarseTimer; |
288 | else if (interval <= 20ms) |
289 | timerType = Qt::PreciseTimer; |
290 | } |
291 | |
292 | QTimerInfo *t = new QTimerInfo(timerId, interval, timerType, object); |
293 | QTimerInfo::TimePoint expected = updateCurrentTime() + interval; |
294 | |
295 | switch (timerType) { |
296 | case Qt::PreciseTimer: |
297 | // high precision timer is based on millisecond precision |
298 | // so no adjustment is necessary |
299 | t->timeout = expected; |
300 | break; |
301 | |
302 | case Qt::CoarseTimer: |
303 | t->timeout = expected; |
304 | t->interval = roundToMillisecond(val: interval); |
305 | calculateCoarseTimerTimeout(t, now: currentTime); |
306 | break; |
307 | |
308 | case Qt::VeryCoarseTimer: |
309 | t->interval = roundToSecs(interval: t->interval); |
310 | const auto currentTimeInSecs = floor<seconds>(tp: currentTime); |
311 | t->timeout = currentTimeInSecs + t->interval; |
312 | // If we're past the half-second mark, increase the timeout again |
313 | if (currentTime - currentTimeInSecs > 500ms) |
314 | t->timeout += 1s; |
315 | } |
316 | |
317 | timerInsert(ti: t); |
318 | } |
319 | |
320 | bool QTimerInfoList::unregisterTimer(Qt::TimerId timerId) |
321 | { |
322 | auto it = findTimerById(timerId); |
323 | if (it == timers.cend()) |
324 | return false; // id not found |
325 | |
326 | // set timer inactive |
327 | QTimerInfo *t = *it; |
328 | if (t == firstTimerInfo) |
329 | firstTimerInfo = nullptr; |
330 | if (t->activateRef) |
331 | *(t->activateRef) = nullptr; |
332 | delete t; |
333 | timers.erase(pos: it); |
334 | return true; |
335 | } |
336 | |
337 | bool QTimerInfoList::unregisterTimers(QObject *object) |
338 | { |
339 | if (timers.isEmpty()) |
340 | return false; |
341 | |
342 | auto associatedWith = [this](QObject *o) { |
343 | return [this, o](auto &t) { |
344 | if (t->obj == o) { |
345 | if (t == firstTimerInfo) |
346 | firstTimerInfo = nullptr; |
347 | if (t->activateRef) |
348 | *(t->activateRef) = nullptr; |
349 | delete t; |
350 | return true; |
351 | } |
352 | return false; |
353 | }; |
354 | }; |
355 | |
356 | qsizetype count = timers.removeIf(pred: associatedWith(object)); |
357 | return count > 0; |
358 | } |
359 | |
360 | auto QTimerInfoList::registeredTimers(QObject *object) const -> QList<TimerInfo> |
361 | { |
362 | QList<TimerInfo> list; |
363 | for (const auto &t : timers) { |
364 | if (t->obj == object) |
365 | list.emplaceBack(args: TimerInfo{.interval: t->interval, .timerId: t->id, .timerType: t->timerType}); |
366 | } |
367 | return list; |
368 | } |
369 | |
370 | /* |
371 | Activate pending timers, returning how many where activated. |
372 | */ |
373 | int QTimerInfoList::activateTimers() |
374 | { |
375 | if (qt_disable_lowpriority_timers || timers.isEmpty()) |
376 | return 0; // nothing to do |
377 | |
378 | firstTimerInfo = nullptr; |
379 | |
380 | const steady_clock::time_point now = updateCurrentTime(); |
381 | // qDebug() << "Thread" << QThread::currentThreadId() << "woken up at" << now; |
382 | // Find out how many timer have expired |
383 | auto stillActive = [&now](const QTimerInfo *t) { return now < t->timeout; }; |
384 | // Find first one still active (list is sorted by timeout) |
385 | auto it = std::find_if(first: timers.cbegin(), last: timers.cend(), pred: stillActive); |
386 | auto maxCount = it - timers.cbegin(); |
387 | |
388 | int n_act = 0; |
389 | //fire the timers. |
390 | while (maxCount--) { |
391 | if (timers.isEmpty()) |
392 | break; |
393 | |
394 | QTimerInfo *currentTimerInfo = timers.constFirst(); |
395 | if (now < currentTimerInfo->timeout) |
396 | break; // no timer has expired |
397 | |
398 | if (!firstTimerInfo) { |
399 | firstTimerInfo = currentTimerInfo; |
400 | } else if (firstTimerInfo == currentTimerInfo) { |
401 | // avoid sending the same timer multiple times |
402 | break; |
403 | } else if (currentTimerInfo->interval < firstTimerInfo->interval |
404 | || currentTimerInfo->interval == firstTimerInfo->interval) { |
405 | firstTimerInfo = currentTimerInfo; |
406 | } |
407 | |
408 | // determine next timeout time |
409 | calculateNextTimeout(t: currentTimerInfo, now); |
410 | if (timers.size() > 1) { |
411 | // Find where "currentTimerInfo" should be in the list so as |
412 | // to keep the list ordered by timeout |
413 | auto afterCurrentIt = timers.begin() + 1; |
414 | auto iter = std::upper_bound(first: afterCurrentIt, last: timers.end(), val: currentTimerInfo, comp: byTimeout); |
415 | currentTimerInfo = *std::rotate(first: timers.begin(), middle: afterCurrentIt, last: iter); |
416 | } |
417 | |
418 | if (currentTimerInfo->interval > 0ms) |
419 | n_act++; |
420 | |
421 | // Send event, but don't allow it to recurse: |
422 | if (!currentTimerInfo->activateRef) { |
423 | currentTimerInfo->activateRef = ¤tTimerInfo; |
424 | |
425 | QTimerEvent e(qToUnderlying(e: currentTimerInfo->id)); |
426 | QCoreApplication::sendEvent(receiver: currentTimerInfo->obj, event: &e); |
427 | |
428 | // Storing currentTimerInfo's address in its activateRef allows the |
429 | // handling of that event to clear this local variable on deletion |
430 | // of the object it points to - if it didn't, clear activateRef: |
431 | if (currentTimerInfo) |
432 | currentTimerInfo->activateRef = nullptr; |
433 | } |
434 | } |
435 | |
436 | firstTimerInfo = nullptr; |
437 | // qDebug() << "Thread" << QThread::currentThreadId() << "activated" << n_act << "timers"; |
438 | return n_act; |
439 | } |
440 | |
441 | QT_END_NAMESPACE |
442 | |