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#ifdef QTIMERINFO_DEBUG
14# include <QDebug>
15# include <QThread>
16#endif
17
18#include <sys/times.h>
19
20using namespace std::chrono;
21
22QT_BEGIN_NAMESPACE
23
24Q_CORE_EXPORT bool qt_disable_lowpriority_timers=false;
25
26/*
27 * Internal functions for manipulating timer data structures. The
28 * timerBitVec array is used for keeping track of timer identifiers.
29 */
30
31QTimerInfoList::QTimerInfoList()
32{
33 firstTimerInfo = nullptr;
34}
35
36timespec QTimerInfoList::updateCurrentTime()
37{
38 return (currentTime = qt_gettime());
39}
40
41/*
42 insert timer info into list
43*/
44void QTimerInfoList::timerInsert(QTimerInfo *ti)
45{
46 int index = size();
47 while (index--) {
48 const QTimerInfo * const t = at(i: index);
49 if (!(ti->timeout < t->timeout))
50 break;
51 }
52 insert(i: index+1, t: ti);
53}
54
55static constexpr timespec roundToMillisecond(timespec val)
56{
57 // always round up
58 // worst case scenario is that the first trigger of a 1-ms timer is 0.999 ms late
59
60 int ns = val.tv_nsec % (1000 * 1000);
61 if (ns)
62 val.tv_nsec += 1000 * 1000 - ns;
63 return normalizedTimespec(t&: val);
64}
65static_assert(roundToMillisecond(val: {.tv_sec: 0, .tv_nsec: 0}) == timespec{.tv_sec: 0, .tv_nsec: 0});
66static_assert(roundToMillisecond(val: {.tv_sec: 0, .tv_nsec: 1}) == timespec{.tv_sec: 0, .tv_nsec: 1'000'000});
67static_assert(roundToMillisecond(val: {.tv_sec: 0, .tv_nsec: 999'999}) == timespec{.tv_sec: 0, .tv_nsec: 1'000'000});
68static_assert(roundToMillisecond(val: {.tv_sec: 0, .tv_nsec: 1'000'000}) == timespec{.tv_sec: 0, .tv_nsec: 1'000'000});
69static_assert(roundToMillisecond(val: {.tv_sec: 0, .tv_nsec: 999'999'999}) == timespec{.tv_sec: 1, .tv_nsec: 0});
70static_assert(roundToMillisecond(val: {.tv_sec: 1, .tv_nsec: 0}) == timespec{.tv_sec: 1, .tv_nsec: 0});
71
72static constexpr seconds roundToSecs(milliseconds msecs)
73{
74 // The very coarse timer is based on full second precision, so we want to
75 // round the interval to the closest second, rounding 500ms up to 1s.
76 //
77 // std::chrono::round() wouldn't work with all multiples of 500 because for the
78 // middle point it would round to even:
79 // value round() wanted
80 // 500 0 1
81 // 1500 2 2
82 // 2500 2 3
83
84 auto secs = duration_cast<seconds>(d: msecs);
85 const milliseconds frac = msecs - secs;
86 if (frac >= 500ms)
87 ++secs;
88 return secs;
89}
90
91#ifdef QTIMERINFO_DEBUG
92QDebug operator<<(QDebug s, timeval tv)
93{
94 QDebugStateSaver saver(s);
95 s.nospace() << tv.tv_sec << "." << qSetFieldWidth(6) << qSetPadChar(QChar(48)) << tv.tv_usec << Qt::reset;
96 return s;
97}
98QDebug operator<<(QDebug s, Qt::TimerType t)
99{
100 QDebugStateSaver saver(s);
101 s << (t == Qt::PreciseTimer ? "P" :
102 t == Qt::CoarseTimer ? "C" : "VC");
103 return s;
104}
105#endif
106
107static void calculateCoarseTimerTimeout(QTimerInfo *t, timespec now)
108{
109 // The coarse timer works like this:
110 // - interval under 40 ms: round to even
111 // - between 40 and 99 ms: round to multiple of 4
112 // - otherwise: try to wake up at a multiple of 25 ms, with a maximum error of 5%
113 //
114 // We try to wake up at the following second-fraction, in order of preference:
115 // 0 ms
116 // 500 ms
117 // 250 ms or 750 ms
118 // 200, 400, 600, 800 ms
119 // other multiples of 100
120 // other multiples of 50
121 // other multiples of 25
122 //
123 // The objective is to make most timers wake up at the same time, thereby reducing CPU wakeups.
124
125 Q_ASSERT(t->interval >= 20ms);
126
127 auto recalculate = [&](const milliseconds fracMsec) {
128 if (fracMsec == 1000ms) {
129 ++t->timeout.tv_sec;
130 t->timeout.tv_nsec = 0;
131 } else {
132 t->timeout.tv_nsec = nanoseconds{fracMsec}.count();
133 }
134
135 if (t->timeout < now)
136 t->timeout += t->interval;
137 };
138
139 // Calculate how much we can round and still keep within 5% error
140 const milliseconds absMaxRounding = t->interval / 20;
141
142 auto fracMsec = duration_cast<milliseconds>(d: nanoseconds{t->timeout.tv_nsec});
143
144 if (t->interval < 100ms && t->interval != 25ms && t->interval != 50ms && t->interval != 75ms) {
145 auto fracCount = fracMsec.count();
146 // special mode for timers of less than 100 ms
147 if (t->interval < 50ms) {
148 // round to even
149 // round towards multiples of 50 ms
150 bool roundUp = (fracCount % 50) >= 25;
151 fracCount >>= 1;
152 fracCount |= roundUp;
153 fracCount <<= 1;
154 } else {
155 // round to multiple of 4
156 // round towards multiples of 100 ms
157 bool roundUp = (fracCount % 100) >= 50;
158 fracCount >>= 2;
159 fracCount |= roundUp;
160 fracCount <<= 2;
161 }
162 fracMsec = milliseconds{fracCount};
163 recalculate(fracMsec);
164 return;
165 }
166
167 milliseconds min = std::max(a: 0ms, b: fracMsec - absMaxRounding);
168 milliseconds max = std::min(a: 1000ms, b: fracMsec + absMaxRounding);
169
170 // find the boundary that we want, according to the rules above
171 // extra rules:
172 // 1) whatever the interval, we'll take any round-to-the-second timeout
173 if (min == 0ms) {
174 fracMsec = 0ms;
175 recalculate(fracMsec);
176 return;
177 } else if (max == 1000ms) {
178 fracMsec = 1000ms;
179 recalculate(fracMsec);
180 return;
181 }
182
183 milliseconds wantedBoundaryMultiple{25};
184
185 // 2) if the interval is a multiple of 500 ms and > 5000 ms, we'll always round
186 // towards a round-to-the-second
187 // 3) if the interval is a multiple of 500 ms, we'll round towards the nearest
188 // multiple of 500 ms
189 if ((t->interval % 500) == 0ms) {
190 if (t->interval >= 5s) {
191 fracMsec = fracMsec >= 500ms ? max : min;
192 recalculate(fracMsec);
193 return;
194 } else {
195 wantedBoundaryMultiple = 500ms;
196 }
197 } else if ((t->interval % 50) == 0ms) {
198 // 4) same for multiples of 250, 200, 100, 50
199 milliseconds mult50 = t->interval / 50;
200 if ((mult50 % 4) == 0ms) {
201 // multiple of 200
202 wantedBoundaryMultiple = 200ms;
203 } else if ((mult50 % 2) == 0ms) {
204 // multiple of 100
205 wantedBoundaryMultiple = 100ms;
206 } else if ((mult50 % 5) == 0ms) {
207 // multiple of 250
208 wantedBoundaryMultiple = 250ms;
209 } else {
210 // multiple of 50
211 wantedBoundaryMultiple = 50ms;
212 }
213 }
214
215 milliseconds base = (fracMsec / wantedBoundaryMultiple) * wantedBoundaryMultiple;
216 milliseconds middlepoint = base + wantedBoundaryMultiple / 2;
217 if (fracMsec < middlepoint)
218 fracMsec = qMax(a: base, b: min);
219 else
220 fracMsec = qMin(a: base + wantedBoundaryMultiple, b: max);
221
222 recalculate(fracMsec);
223}
224
225static void calculateNextTimeout(QTimerInfo *t, timespec now)
226{
227 switch (t->timerType) {
228 case Qt::PreciseTimer:
229 case Qt::CoarseTimer:
230 t->timeout += t->interval;
231 if (t->timeout < now) {
232 t->timeout = now;
233 t->timeout += t->interval;
234 }
235#ifdef QTIMERINFO_DEBUG
236 t->expected += t->interval;
237 if (t->expected < currentTime) {
238 t->expected = currentTime;
239 t->expected += t->interval;
240 }
241#endif
242 if (t->timerType == Qt::CoarseTimer)
243 calculateCoarseTimerTimeout(t, now);
244 return;
245
246 case Qt::VeryCoarseTimer:
247 // t->interval already rounded to full seconds in registerTimer()
248 const auto secs = duration_cast<seconds>(d: t->interval).count();
249 t->timeout.tv_sec += secs;
250 if (t->timeout.tv_sec <= now.tv_sec)
251 t->timeout.tv_sec = now.tv_sec + secs;
252#ifdef QTIMERINFO_DEBUG
253 t->expected.tv_sec += t->interval;
254 if (t->expected.tv_sec <= currentTime.tv_sec)
255 t->expected.tv_sec = currentTime.tv_sec + t->interval;
256#endif
257 return;
258 }
259
260#ifdef QTIMERINFO_DEBUG
261 if (t->timerType != Qt::PreciseTimer)
262 qDebug() << "timer" << t->timerType << Qt::hex << t->id << Qt::dec << "interval" << t->interval
263 << "originally expected at" << t->expected << "will fire at" << t->timeout
264 << "or" << (t->timeout - t->expected) << "s late";
265#endif
266}
267
268/*
269 Returns the time to wait for the next timer, or null if no timers
270 are waiting.
271*/
272bool QTimerInfoList::timerWait(timespec &tm)
273{
274 timespec now = updateCurrentTime();
275
276 auto isWaiting = [](QTimerInfo *tinfo) { return !tinfo->activateRef; };
277 // Find first waiting timer not already active
278 auto it = std::find_if(first: cbegin(), last: cend(), pred: isWaiting);
279 if (it == cend())
280 return false;
281
282 QTimerInfo *t = *it;
283 if (now < t->timeout) // Time to wait
284 tm = roundToMillisecond(val: t->timeout - now);
285 else // No time to wait
286 tm = {.tv_sec: 0, .tv_nsec: 0};
287
288 return true;
289}
290
291/*
292 Returns the timer's remaining time in milliseconds with the given timerId.
293 If the timer id is not found in the list, the returned value will be -1.
294 If the timer is overdue, the returned value will be 0.
295*/
296qint64 QTimerInfoList::timerRemainingTime(int timerId)
297{
298 return remainingDuration(timerId).count();
299}
300
301milliseconds QTimerInfoList::remainingDuration(int timerId)
302{
303 timespec now = updateCurrentTime();
304
305 auto it = findTimerById(timerId);
306 if (it == cend()) {
307#ifndef QT_NO_DEBUG
308 qWarning(msg: "QTimerInfoList::timerRemainingTime: timer id %i not found", timerId);
309#endif
310 return milliseconds{-1};
311 }
312
313 const QTimerInfo *t = *it;
314 if (now < t->timeout) // time to wait
315 return timespecToChronoMs(ts: roundToMillisecond(val: t->timeout - now));
316 else
317 return milliseconds{0};
318}
319
320void QTimerInfoList::registerTimer(int timerId, qint64 interval, Qt::TimerType timerType, QObject *object)
321{
322 registerTimer(timerId, interval: milliseconds{interval}, timerType, object);
323}
324
325void QTimerInfoList::registerTimer(int timerId, milliseconds interval,
326 Qt::TimerType timerType, QObject *object)
327{
328 QTimerInfo *t = new QTimerInfo;
329 t->id = timerId;
330 t->interval = interval;
331 t->timerType = timerType;
332 t->obj = object;
333 t->activateRef = nullptr;
334
335 timespec expected = updateCurrentTime() + interval;
336
337 switch (timerType) {
338 case Qt::PreciseTimer:
339 // high precision timer is based on millisecond precision
340 // so no adjustment is necessary
341 t->timeout = expected;
342 break;
343
344 case Qt::CoarseTimer:
345 // this timer has up to 5% coarseness
346 // so our boundaries are 20 ms and 20 s
347 // below 20 ms, 5% inaccuracy is below 1 ms, so we convert to high precision
348 // above 20 s, 5% inaccuracy is above 1 s, so we convert to VeryCoarseTimer
349 if (interval >= 20s) {
350 t->timerType = Qt::VeryCoarseTimer;
351 } else {
352 t->timeout = expected;
353 if (interval <= 20ms) {
354 t->timerType = Qt::PreciseTimer;
355 // no adjustment is necessary
356 } else if (interval <= 20s) {
357 calculateCoarseTimerTimeout(t, now: currentTime);
358 }
359 break;
360 }
361 Q_FALLTHROUGH();
362 case Qt::VeryCoarseTimer:
363 const seconds secs = roundToSecs(msecs: t->interval);
364 t->interval = secs;
365 t->timeout.tv_sec = currentTime.tv_sec + secs.count();
366 t->timeout.tv_nsec = 0;
367
368 // if we're past the half-second mark, increase the timeout again
369 if (currentTime.tv_nsec > nanoseconds{500ms}.count())
370 ++t->timeout.tv_sec;
371 }
372
373 timerInsert(ti: t);
374
375#ifdef QTIMERINFO_DEBUG
376 t->expected = expected;
377 t->cumulativeError = 0;
378 t->count = 0;
379 if (t->timerType != Qt::PreciseTimer)
380 qDebug() << "timer" << t->timerType << Qt::hex <<t->id << Qt::dec << "interval" << t->interval << "expected at"
381 << t->expected << "will fire first at" << t->timeout;
382#endif
383}
384
385bool QTimerInfoList::unregisterTimer(int timerId)
386{
387 auto it = findTimerById(timerId);
388 if (it == cend())
389 return false; // id not found
390
391 // set timer inactive
392 QTimerInfo *t = *it;
393 if (t == firstTimerInfo)
394 firstTimerInfo = nullptr;
395 if (t->activateRef)
396 *(t->activateRef) = nullptr;
397 delete t;
398 erase(pos: it);
399 return true;
400}
401
402bool QTimerInfoList::unregisterTimers(QObject *object)
403{
404 if (isEmpty())
405 return false;
406 for (int i = 0; i < size(); ++i) {
407 QTimerInfo *t = at(i);
408 if (t->obj == object) {
409 // object found
410 removeAt(i);
411 if (t == firstTimerInfo)
412 firstTimerInfo = nullptr;
413 if (t->activateRef)
414 *(t->activateRef) = nullptr;
415 delete t;
416 // move back one so that we don't skip the new current item
417 --i;
418 }
419 }
420 return true;
421}
422
423QList<QAbstractEventDispatcher::TimerInfo> QTimerInfoList::registeredTimers(QObject *object) const
424{
425 QList<QAbstractEventDispatcher::TimerInfo> list;
426 for (const QTimerInfo *const t : std::as_const(t: *this)) {
427 if (t->obj == object)
428 list.emplaceBack(args: t->id, args: t->interval.count(), args: t->timerType);
429 }
430 return list;
431}
432
433/*
434 Activate pending timers, returning how many where activated.
435*/
436int QTimerInfoList::activateTimers()
437{
438 if (qt_disable_lowpriority_timers || isEmpty())
439 return 0; // nothing to do
440
441 firstTimerInfo = nullptr;
442
443 timespec now = updateCurrentTime();
444 // qDebug() << "Thread" << QThread::currentThreadId() << "woken up at" << now;
445 // Find out how many timer have expired
446 auto stillActive = [&now](const QTimerInfo *t) { return now < t->timeout; };
447 // Find first one still active (list is sorted by timeout)
448 auto it = std::find_if(first: cbegin(), last: cend(), pred: stillActive);
449 auto maxCount = it - cbegin();
450
451 int n_act = 0;
452 //fire the timers.
453 while (maxCount--) {
454 if (isEmpty())
455 break;
456
457 QTimerInfo *currentTimerInfo = constFirst();
458 if (now < currentTimerInfo->timeout)
459 break; // no timer has expired
460
461 if (!firstTimerInfo) {
462 firstTimerInfo = currentTimerInfo;
463 } else if (firstTimerInfo == currentTimerInfo) {
464 // avoid sending the same timer multiple times
465 break;
466 } else if (currentTimerInfo->interval < firstTimerInfo->interval
467 || currentTimerInfo->interval == firstTimerInfo->interval) {
468 firstTimerInfo = currentTimerInfo;
469 }
470
471 // remove from list
472 removeFirst();
473
474#ifdef QTIMERINFO_DEBUG
475 float diff;
476 if (currentTime < currentTimerInfo->expected) {
477 // early
478 timeval early = currentTimerInfo->expected - currentTime;
479 diff = -(early.tv_sec + early.tv_usec / 1000000.0);
480 } else {
481 timeval late = currentTime - currentTimerInfo->expected;
482 diff = late.tv_sec + late.tv_usec / 1000000.0;
483 }
484 currentTimerInfo->cumulativeError += diff;
485 ++currentTimerInfo->count;
486 if (currentTimerInfo->timerType != Qt::PreciseTimer)
487 qDebug() << "timer" << currentTimerInfo->timerType << Qt::hex << currentTimerInfo->id << Qt::dec << "interval"
488 << currentTimerInfo->interval << "firing at" << currentTime
489 << "(orig" << currentTimerInfo->expected << "scheduled at" << currentTimerInfo->timeout
490 << ") off by" << diff << "activation" << currentTimerInfo->count
491 << "avg error" << (currentTimerInfo->cumulativeError / currentTimerInfo->count);
492#endif
493
494 // determine next timeout time
495 calculateNextTimeout(t: currentTimerInfo, now);
496
497 // reinsert timer
498 timerInsert(ti: currentTimerInfo);
499 if (currentTimerInfo->interval > 0ms)
500 n_act++;
501
502 // Send event, but don't allow it to recurse:
503 if (!currentTimerInfo->activateRef) {
504 currentTimerInfo->activateRef = &currentTimerInfo;
505
506 QTimerEvent e(currentTimerInfo->id);
507 QCoreApplication::sendEvent(receiver: currentTimerInfo->obj, event: &e);
508
509 // Storing currentTimerInfo's address in its activateRef allows the
510 // handling of that event to clear this local variable on deletion
511 // of the object it points to - if it didn't, clear activateRef:
512 if (currentTimerInfo)
513 currentTimerInfo->activateRef = nullptr;
514 }
515 }
516
517 firstTimerInfo = nullptr;
518 // qDebug() << "Thread" << QThread::currentThreadId() << "activated" << n_act << "timers";
519 return n_act;
520}
521
522QT_END_NAMESPACE
523

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