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
15using namespace std::chrono;
16// Implied by "using namespace std::chrono", but be explicit about it, for grep-ability
17using namespace std::chrono_literals;
18
19QT_BEGIN_NAMESPACE
20
21Q_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
28QTimerInfoList::QTimerInfoList() = default;
29
30steady_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*/
42bool QTimerInfoList::hasPendingTimers()
43{
44 if (timers.isEmpty())
45 return false;
46 return updateCurrentTime() < timers.at(i: 0)->timeout;
47}
48
49static bool byTimeout(const QTimerInfo *a, const QTimerInfo *b)
50{ return a->timeout < b->timeout; };
51
52/*
53 insert timer info into list
54*/
55void 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
61static 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
68static_assert(roundToMillisecond(val: 0ns) == 0ms);
69static_assert(roundToMillisecond(val: 1ns) == 1ms);
70static_assert(roundToMillisecond(val: 999'999ns) == 1ms);
71static_assert(roundToMillisecond(val: 1'000'000ns) == 1ms);
72static_assert(roundToMillisecond(val: 999'000'000ns) == 999ms);
73static_assert(roundToMillisecond(val: 999'000'001ns) == 1000ms);
74static_assert(roundToMillisecond(val: 999'999'999ns) == 1000ms);
75static_assert(roundToMillisecond(val: 1s) == 1s);
76
77static 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
96static 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
211static 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 */
238std::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*/
259QTimerInfoList::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
277void 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
320bool 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
337bool 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
360auto 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*/
373int 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 = &currentTimerInfo;
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
441QT_END_NAMESPACE
442

source code of qtbase/src/corelib/kernel/qtimerinfo_unix.cpp