GCC Code Coverage Report

Directory: ./
File: firmware/controllers/system/timer/event_queue.cpp
Date: 2025-10-03 00:57:22
Warnings: 4 unchecked decisions!
Coverage Exec Excl Total
Lines: 94.4% 119 0 126
Functions: 100.0% 13 0 13
Branches: 87.0% 80 0 92
Decisions: 72.9% 35 - 48
Line Branch Decision Exec Source
1 /**
2 * @file event_queue.cpp
3 * This is a data structure which keeps track of all pending events
4 * Implemented as a linked list, which is fine since the number of
5 * pending events is pretty low
6 * todo: MAYBE migrate to a better data structure, but that's low priority
7 *
8 * this data structure is NOT thread safe
9 *
10 * @date Apr 17, 2014
11 * @author Andrey Belomutskiy, (c) 2012-2020
12 */
13
14 #include "pch.h"
15
16 #include "event_queue.h"
17 #include "efitime.h"
18
19 #ifndef EFI_UNIT_TEST_VERBOSE_ACTION
20 #define EFI_UNIT_TEST_VERBOSE_ACTION 0
21 #elif EFI_UNIT_TEST_VERBOSE_ACTION
22 #include <iostream>
23 #endif
24
25 #if EFI_UNIT_TEST
26 extern bool verboseMode;
27 #endif /* EFI_UNIT_TEST */
28
29 694 EventQueue::EventQueue(efidur_t lateDelay)
30 694 : m_lateDelay(lateDelay)
31 {
32
2/2
✓ Branch 1 taken 44416 times.
✓ Branch 2 taken 694 times.
2/2
✓ Decision 'true' taken 44416 times.
✓ Decision 'false' taken 694 times.
 45110 for (size_t i = 0; i < efi::size(m_pool); i++) {
33 44416 tryReturnScheduling(&m_pool[i]);
34 }
35
36 #if EFI_PROD_CODE
37 getTunerStudioOutputChannels()->schedulingUsedCount = 0;
38 #endif
39 694 }
40
41 3091 scheduling_s* EventQueue::getFreeScheduling() {
42 3091 auto retVal = m_freelist;
43
44
2/2
✓ Branch 0 taken 3005 times.
✓ Branch 1 taken 86 times.
2/2
✓ Decision 'true' taken 3005 times.
✓ Decision 'false' taken 86 times.
 3091 if (retVal) {
45 3005 m_freelist = retVal->nextScheduling_s;
46 3005 retVal->nextScheduling_s = nullptr;
47
48 #if EFI_PROD_CODE
49 getTunerStudioOutputChannels()->schedulingUsedCount++;
50 #endif
51 }
52
53 3091 return retVal;
54 }
55
56 61991 void EventQueue::tryReturnScheduling(scheduling_s* sched) {
57 // Only return this scheduling to the free list if it's from the correct pool
58
6/6
✓ Branch 0 taken 60711 times.
✓ Branch 1 taken 1280 times.
✓ Branch 3 taken 47088 times.
✓ Branch 4 taken 13623 times.
✓ Branch 5 taken 47088 times.
✓ Branch 6 taken 14903 times.
2/2
✓ Decision 'true' taken 47088 times.
✓ Decision 'false' taken 14903 times.
 61991 if (sched >= &m_pool[0] && sched <= &m_pool[efi::size(m_pool) - 1]) {
59 47088 sched->nextScheduling_s = m_freelist;
60 47088 m_freelist = sched;
61
62 #if EFI_PROD_CODE
63 getTunerStudioOutputChannels()->schedulingUsedCount--;
64 #endif
65 }
66 61991 }
67
68 /**
69 * @return true if inserted into the head of the list
70 */
71 25397 bool EventQueue::insertTask(scheduling_s *scheduling, efitick_t timeNt, action_s const& action) {
72 25397 ScopePerf perf(PE::EventQueueInsertTask);
73
74
2/2
✓ Branch 0 taken 3091 times.
✓ Branch 1 taken 22306 times.
2/2
✓ Decision 'true' taken 3091 times.
✓ Decision 'false' taken 22306 times.
 25397 if (!scheduling) {
75
1/1
✓ Branch 1 taken 3091 times.
 3091 scheduling = getFreeScheduling();
76
77 // If still null, the free list is empty and all schedulings in the pool have been expended.
78
2/2
✓ Branch 0 taken 86 times.
✓ Branch 1 taken 3005 times.
2/2
✓ Decision 'true' taken 86 times.
✓ Decision 'false' taken 3005 times.
 3091 if (!scheduling) {
79 // TODO: should we warn or error here?
80 // todo: look into why units tests fail here
81 #if EFI_PROD_CODE
82 criticalError("No slots in scheduling pool");
83 #endif
84 86 return false;
85 }
86 }
87
88
1/1
✓ Branch 1 taken 25311 times.
 25311 assertListIsSorted();
89
1/3
✗ Branch 1 not taken.
✓ Branch 2 taken 25311 times.
✗ Branch 4 not taken.
 25311 efiAssert(ObdCode::CUSTOM_ERR_ASSERT, action.getCallback() != NULL, "NULL callback", false);
90
91 // please note that simulator does not use this code at all - simulator uses signal_executor_sleep
92
93
2/2
✓ Branch 1 taken 6038 times.
✓ Branch 2 taken 19273 times.
2/2
✓ Decision 'true' taken 6038 times.
✓ Decision 'false' taken 19273 times.
 25311 if (scheduling->action) {
94 #if EFI_UNIT_TEST
95
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 6038 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 6038 times.
 6038 if (verboseMode) {
96 ✗ printf("Already scheduled was %d\r\n", (int)scheduling->getMomentNt());
97 ✗ printf("Already scheduled now %d\r\n", (int)timeNt);
98 }
99 #endif /* EFI_UNIT_TEST */
100 6038 return false;
101 }
102
103 19273 scheduling->setMomentNt(timeNt);
104 19273 scheduling->action = action;
105
106
6/6
✓ Branch 0 taken 12838 times.
✓ Branch 1 taken 6435 times.
✓ Branch 3 taken 1714 times.
✓ Branch 4 taken 11124 times.
✓ Branch 5 taken 8149 times.
✓ Branch 6 taken 11124 times.
2/2
✓ Decision 'true' taken 8149 times.
✓ Decision 'false' taken 11124 times.
 19273 if (!m_head || timeNt < m_head->getMomentNt()) {
107 // here we insert into head of the linked list
108 8149 LL_PREPEND2(m_head, scheduling, nextScheduling_s);
109
1/1
✓ Branch 1 taken 8149 times.
 8149 assertListIsSorted();
110 8149 return true;
111 } else {
112 // here we know we are not in the head of the list, let's find the position - linear search
113 11124 scheduling_s *insertPosition = m_head;
114
6/6
✓ Branch 0 taken 598958 times.
✓ Branch 1 taken 9265 times.
✓ Branch 3 taken 597099 times.
✓ Branch 4 taken 1859 times.
✓ Branch 5 taken 597099 times.
✓ Branch 6 taken 11124 times.
0/1
? Decision couldn't be analyzed.
 608223 while (insertPosition->nextScheduling_s != NULL && insertPosition->nextScheduling_s->getMomentNt() < timeNt) {
115 597099 insertPosition = insertPosition->nextScheduling_s;
116 }
117
118 11124 scheduling->nextScheduling_s = insertPosition->nextScheduling_s;
119 11124 insertPosition->nextScheduling_s = scheduling;
120
1/1
✓ Branch 1 taken 11124 times.
 11124 assertListIsSorted();
121 11124 return false;
122 }
123 }
124
125 1270 void EventQueue::remove(scheduling_s* scheduling) {
126 1270 assertListIsSorted();
127
128 // Special case: event isn't scheduled, so don't cancel it
129
2/2
✓ Branch 1 taken 147 times.
✓ Branch 2 taken 1123 times.
2/2
✓ Decision 'true' taken 147 times.
✓ Decision 'false' taken 1123 times.
 1270 if (!scheduling->action) {
130 147 return;
131 }
132
133 // Special case: empty list, nothing to do
134
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 1123 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 1123 times.
 1123 if (!m_head) {
135 ✗ return;
136 }
137
138 // Special case: is the item to remove at the head?
139
2/2
✓ Branch 0 taken 893 times.
✓ Branch 1 taken 230 times.
2/2
✓ Decision 'true' taken 893 times.
✓ Decision 'false' taken 230 times.
 1123 if (scheduling == m_head) {
140 893 m_head = m_head->nextScheduling_s;
141 893 scheduling->nextScheduling_s = nullptr;
142 893 scheduling->action = {};
143 } else {
144 230 auto prev = m_head; // keep track of the element before the one to remove, so we can link around it
145 230 auto current = prev->nextScheduling_s;
146
147 // Find our element
148
3/4
✓ Branch 0 taken 3175 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2945 times.
✓ Branch 3 taken 230 times.
0/1
? Decision couldn't be analyzed.
 3175 while (current && current != scheduling) {
149 2945 prev = current;
150 2945 current = current->nextScheduling_s;
151 }
152
153 // Walked off the end, this is an error since this *should* have been scheduled
154
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 230 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 230 times.
 230 if (!current) {
155 ✗ firmwareError(ObdCode::OBD_PCM_Processor_Fault, "EventQueue::remove didn't find element");
156 ✗ return;
157 }
158
159
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 230 times.
 230 efiAssertVoid(ObdCode::OBD_PCM_Processor_Fault, current == scheduling, "current not equal to scheduling");
160
161 // Link around the removed item
162 230 prev->nextScheduling_s = current->nextScheduling_s;
163
164 // Clean the item to remove
165 230 current->nextScheduling_s = nullptr;
166 230 current->action = {};
167 }
168
169 1123 assertListIsSorted();
170 }
171
172 /**
173 * On this layer it does not matter which units are used - us, ms ot nt.
174 *
175 * This method is always invoked under a lock
176 * @return Get the timestamp of the soonest pending action, skipping all the actions in the past
177 */
178 5 expected<efitick_t> EventQueue::getNextEventTime(efitick_t nowNt) const {
179
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 2 times.
2/2
✓ Decision 'true' taken 3 times.
✓ Decision 'false' taken 2 times.
 5 if (m_head) {
180
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 3 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 3 times.
 3 if (m_head->getMomentNt() <= nowNt) {
181 /**
182 * We are here if action timestamp is in the past. We should rarely be here since this 'getNextEventTime()' is
183 * always invoked by 'scheduleTimerCallback' which is always invoked right after 'executeAllPendingActions' - but still,
184 * for events which are really close to each other we would end up here.
185 *
186 * looks like we end up here after 'writeconfig' (which freezes the firmware) - we are late
187 * for the next scheduled event
188 */
189 ✗ return nowNt + m_lateDelay;
190 } else {
191 3 return m_head->getMomentNt();
192 }
193 }
194
195 2 return unexpected;
196 }
197
198 /**
199 * See also maxPrecisionCallbackDuration for total hw callback time
200 */
201 uint32_t maxEventCallbackDuration = 0;
202
203 /**
204 * Invoke all pending actions prior to specified timestamp
205 * @return number of executed actions
206 */
207 13312 int EventQueue::executeAll(efitick_t now) {
208 13312 ScopePerf perf(PE::EventQueueExecuteAll);
209
210 13312 int executionCounter = 0;
211
212
1/1
✓ Branch 1 taken 13312 times.
 13312 assertListIsSorted();
213
214 bool didExecute;
215 30887 do {
216
1/1
✓ Branch 1 taken 30887 times.
 30887 didExecute = executeOne(now);
217
4/4
✓ Branch 0 taken 17575 times.
✓ Branch 1 taken 13312 times.
✓ Branch 2 taken 17575 times.
✓ Branch 3 taken 13312 times.
 30887 executionCounter += didExecute ? 1 : 0;
218 } while (didExecute);
219
220 13312 return executionCounter;
221 }
222
223 30887 bool EventQueue::executeOne(efitick_t now) {
224 // Read the head every time - a previously executed event could
225 // have inserted something new at the head
226 30887 scheduling_s* current = m_head;
227
228 // Queue is empty - bail
229
2/2
✓ Branch 0 taken 5597 times.
✓ Branch 1 taken 25290 times.
2/2
✓ Decision 'true' taken 5597 times.
✓ Decision 'false' taken 25290 times.
 30887 if (!current) {
230 5597 return false;
231 }
232
233 // If the next event is far in the future, we'll reschedule
234 // and execute it next time.
235 // We do this when the next event is close enough that the overhead of
236 // resetting the timer and scheduling an new interrupt is greater than just
237 // waiting for the time to arrive. On current CPUs, this is reasonable to set
238 // around 10 microseconds.
239
2/2
✓ Branch 1 taken 7715 times.
✓ Branch 2 taken 17575 times.
2/2
✓ Decision 'true' taken 7715 times.
✓ Decision 'false' taken 17575 times.
 25290 if (current->getMomentNt() > now + m_lateDelay) {
240 7715 return false;
241 }
242
243 #if EFI_UNIT_TEST
244 // efitick_t spinDuration = current->getMomentNt() - getTimeNowNt();
245 // if (spinDuration > 0) {
246 // throw std::runtime_error("Time Spin in unit test");
247 // }
248 #endif
249
250 // near future - spin wait for the event to happen and avoid the
251 // overhead of rescheduling the timer.
252 // yes, that's a busy wait but that's what we need here
253
3/3
✓ Branch 2 taken 33500292 times.
✓ Branch 4 taken 33482744 times.
✓ Branch 5 taken 17548 times.
0/1
? Decision couldn't be analyzed.
 33500292 while (current->getMomentNt() > getTimeNowNt()) {
254 #if EFI_UNIT_TEST
255 // todo: remove this hack see https://github.com/rusefi/rusefi/issues/6457
256 extern bool unitTestBusyWaitHack;
257
2/2
✓ Branch 0 taken 27 times.
✓ Branch 1 taken 33482717 times.
2/2
✓ Decision 'true' taken 27 times.
✓ Decision 'false' taken 33482717 times.
 33482744 if (unitTestBusyWaitHack) {
258 27 break;
259 }
260 #endif
261
1/1
✓ Branch 1 taken 33482717 times.
 33482717 UNIT_TEST_BUSY_WAIT_CALLBACK();
262 }
263
264 // step the head forward, unlink this element, clear scheduled flag
265 17575 m_head = current->nextScheduling_s;
266 17575 current->nextScheduling_s = nullptr;
267
268 // Grab the action but clear it in the event so we can reschedule from the action's execution
269 17575 auto const action{ std::move(current->action) };
270
271
1/1
✓ Branch 1 taken 17575 times.
 17575 tryReturnScheduling(current);
272 17575 current = nullptr;
273
274 #if EFI_DETAILED_LOGGING
275 printf("QUEUE: execute current=%d param=%d\r\n", reinterpret_cast<uintptr_t>(current), action.getArgumentRaw());
276 #endif
277
278 // Execute the current element
279 {
280 17575 ScopePerf perf2(PE::EventQueueExecuteCallback);
281 #if EFI_DETAILED_LOGGING && EFI_UNIT_TEST_VERBOSE_ACTION
282 std::cout << "EventQueue::executeOne: " << action.getCallbackName() << "(" << reinterpret_cast<uintptr_t>(action.getCallback()) << ") with raw arg = " << action.getArgumentRaw() << std::endl;
283 #endif
284
1/1
✓ Branch 1 taken 17575 times.
 17575 action.execute();
285
286 #if EFI_UNIT_TEST
287 // std::cout << "Executed at " << now << std::endl;
288 #endif
289 }
290
291
1/1
✓ Branch 1 taken 17575 times.
 17575 assertListIsSorted();
292 17575 return true;
293 }
294
295 239 int EventQueue::size() const {
296 scheduling_s *tmp;
297 int result;
298
2/2
✓ Branch 0 taken 952 times.
✓ Branch 1 taken 239 times.
 1191 LL_COUNT2(m_head, tmp, result, nextScheduling_s);
299 239 return result;
300 }
301
302 77864 void EventQueue::assertListIsSorted() const {
303 #if EFI_UNIT_TEST || EFI_SIMULATOR
304 77864 int counter = 0;
305 77864 scheduling_s *current = m_head;
306
4/4
✓ Branch 0 taken 2911188 times.
✓ Branch 1 taken 12858 times.
✓ Branch 2 taken 2846182 times.
✓ Branch 3 taken 65006 times.
0/1
? Decision couldn't be analyzed.
 2924046 while (current != NULL && current->nextScheduling_s != NULL) {
307
1/2
✗ Branch 2 not taken.
✓ Branch 3 taken 2846182 times.
 2846182 efiAssertVoid(ObdCode::CUSTOM_ERR_6623, current->getMomentNt() <= current->nextScheduling_s->getMomentNt(), "list order");
308 2846182 current = current->nextScheduling_s;
309
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 2846182 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 2846182 times.
 2846182 if (counter++ > 1'000'000'000)
310 ✗ criticalError("EventQueue: looks like a loop?!");
311 }
312 #endif // EFI_UNIT_TEST || EFI_SIMULATOR
313 }
314
315 599205 scheduling_s * EventQueue::getHead() {
316 599205 return m_head;
317 }
318
319 // todo: reduce code duplication with another 'getElementAtIndexForUnitText'
320 177 scheduling_s *EventQueue::getElementAtIndexForUnitText(int index) {
321 scheduling_s * current;
322
323
2/2
✓ Branch 0 taken 444 times.
✓ Branch 1 taken 8 times.
 452 LL_FOREACH2(m_head, current, nextScheduling_s)
324 {
325
2/2
✓ Branch 0 taken 169 times.
✓ Branch 1 taken 275 times.
2/2
✓ Decision 'true' taken 169 times.
✓ Decision 'false' taken 275 times.
 444 if (index == 0) {
326 169 return current;
327 }
328 275 index--;
329 }
330
331 8 return NULL;
332 }
333
334 694 void EventQueue::clear() {
335 // Flush the queue, resetting all scheduling_s as though we'd executed them
336
2/2
✓ Branch 0 taken 564 times.
✓ Branch 1 taken 694 times.
2/2
✓ Decision 'true' taken 564 times.
✓ Decision 'false' taken 694 times.
 1258 while(m_head) {
337 564 auto x = m_head;
338 // link next element to head
339 564 m_head = x->nextScheduling_s;
340
341 // Reset this element
342 564 x->setMomentNt(0);
343 564 x->nextScheduling_s = nullptr;
344 564 x->action = {};
345 }
346
347 694 m_head = nullptr;
348 694 }
349