| 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 | 695 | EventQueue::EventQueue(efidur_t lateDelay) | ||
| 30 | 695 | : m_lateDelay(lateDelay) | ||
| 31 | { | |||
| 32 |
2/2✓ Branch 1 taken 44480 times.
✓ Branch 2 taken 695 times.
|
2/2✓ Decision 'true' taken 44480 times.
✓ Decision 'false' taken 695 times.
|
45175 | for (size_t i = 0; i < efi::size(m_pool); i++) { |
| 33 | 44480 | tryReturnScheduling(&m_pool[i]); | ||
| 34 | } | |||
| 35 | ||||
| 36 | #if EFI_PROD_CODE | |||
| 37 | getTunerStudioOutputChannels()->schedulingUsedCount = 0; | |||
| 38 | #endif | |||
| 39 | 695 | } | ||
| 40 | ||||
| 41 | 3087 | scheduling_s* EventQueue::getFreeScheduling() { | ||
| 42 | 3087 | auto retVal = m_freelist; | ||
| 43 | ||||
| 44 |
2/2✓ Branch 0 taken 3001 times.
✓ Branch 1 taken 86 times.
|
2/2✓ Decision 'true' taken 3001 times.
✓ Decision 'false' taken 86 times.
|
3087 | if (retVal) { |
| 45 | 3001 | m_freelist = retVal->nextScheduling_s; | ||
| 46 | 3001 | retVal->nextScheduling_s = nullptr; | ||
| 47 | ||||
| 48 | #if EFI_PROD_CODE | |||
| 49 | getTunerStudioOutputChannels()->schedulingUsedCount++; | |||
| 50 | #endif | |||
| 51 | } | |||
| 52 | ||||
| 53 | 3087 | return retVal; | ||
| 54 | } | |||
| 55 | ||||
| 56 | 63676 | 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 62396 times.
✓ Branch 1 taken 1280 times.
✓ Branch 3 taken 47148 times.
✓ Branch 4 taken 15248 times.
✓ Branch 5 taken 47148 times.
✓ Branch 6 taken 16528 times.
|
2/2✓ Decision 'true' taken 47148 times.
✓ Decision 'false' taken 16528 times.
|
63676 | if (sched >= &m_pool[0] && sched <= &m_pool[efi::size(m_pool) - 1]) { |
| 59 | 47148 | sched->nextScheduling_s = m_freelist; | ||
| 60 | 47148 | m_freelist = sched; | ||
| 61 | ||||
| 62 | #if EFI_PROD_CODE | |||
| 63 | getTunerStudioOutputChannels()->schedulingUsedCount--; | |||
| 64 | #endif | |||
| 65 | } | |||
| 66 | 63676 | } | ||
| 67 | ||||
| 68 | /** | |||
| 69 | * @return true if inserted into the head of the list | |||
| 70 | */ | |||
| 71 | 27608 | bool EventQueue::insertTask(scheduling_s *scheduling, efitick_t timeNt, action_s const& action) { | ||
| 72 | 27608 | ScopePerf perf(PE::EventQueueInsertTask); | ||
| 73 | ||||
| 74 |
2/2✓ Branch 0 taken 3087 times.
✓ Branch 1 taken 24521 times.
|
2/2✓ Decision 'true' taken 3087 times.
✓ Decision 'false' taken 24521 times.
|
27608 | if (!scheduling) { |
| 75 |
1/1✓ Branch 1 taken 3087 times.
|
3087 | 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 3001 times.
|
2/2✓ Decision 'true' taken 86 times.
✓ Decision 'false' taken 3001 times.
|
3087 | 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 27522 times.
|
27522 | assertListIsSorted(); | |
| 89 |
1/3✗ Branch 1 not taken.
✓ Branch 2 taken 27522 times.
✗ Branch 4 not taken.
|
27522 | 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 6035 times.
✓ Branch 2 taken 21487 times.
|
2/2✓ Decision 'true' taken 6035 times.
✓ Decision 'false' taken 21487 times.
|
27522 | if (scheduling->action) { |
| 94 | #if EFI_UNIT_TEST | |||
| 95 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 6035 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 6035 times.
|
6035 | 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 | 6035 | return false; | ||
| 101 | } | |||
| 102 | ||||
| 103 | 21487 | scheduling->setMomentNt(timeNt); | ||
| 104 | 21487 | scheduling->action = action; | ||
| 105 | ||||
| 106 |
6/6✓ Branch 0 taken 13991 times.
✓ Branch 1 taken 7496 times.
✓ Branch 3 taken 1882 times.
✓ Branch 4 taken 12109 times.
✓ Branch 5 taken 9378 times.
✓ Branch 6 taken 12109 times.
|
2/2✓ Decision 'true' taken 9378 times.
✓ Decision 'false' taken 12109 times.
|
21487 | if (!m_head || timeNt < m_head->getMomentNt()) { |
| 107 | // here we insert into head of the linked list | |||
| 108 | 9378 | LL_PREPEND2(m_head, scheduling, nextScheduling_s); | ||
| 109 |
1/1✓ Branch 1 taken 9378 times.
|
9378 | assertListIsSorted(); | |
| 110 | 9378 | 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 | 12109 | scheduling_s *insertPosition = m_head; | ||
| 114 |
6/6✓ Branch 0 taken 599107 times.
✓ Branch 1 taken 10247 times.
✓ Branch 3 taken 597245 times.
✓ Branch 4 taken 1862 times.
✓ Branch 5 taken 597245 times.
✓ Branch 6 taken 12109 times.
|
0/1? Decision couldn't be analyzed.
|
609354 | while (insertPosition->nextScheduling_s != NULL && insertPosition->nextScheduling_s->getMomentNt() < timeNt) { |
| 115 | 597245 | insertPosition = insertPosition->nextScheduling_s; | ||
| 116 | } | |||
| 117 | ||||
| 118 | 12109 | scheduling->nextScheduling_s = insertPosition->nextScheduling_s; | ||
| 119 | 12109 | insertPosition->nextScheduling_s = scheduling; | ||
| 120 |
1/1✓ Branch 1 taken 12109 times.
|
12109 | assertListIsSorted(); | |
| 121 | 12109 | return false; | ||
| 122 | } | |||
| 123 | } | |||
| 124 | ||||
| 125 | 1735 | void EventQueue::remove(scheduling_s* scheduling) { | ||
| 126 | 1735 | assertListIsSorted(); | ||
| 127 | ||||
| 128 | // Special case: event isn't scheduled, so don't cancel it | |||
| 129 |
2/2✓ Branch 1 taken 24 times.
✓ Branch 2 taken 1711 times.
|
2/2✓ Decision 'true' taken 24 times.
✓ Decision 'false' taken 1711 times.
|
1735 | if (!scheduling->action) { |
| 130 | 24 | return; | ||
| 131 | } | |||
| 132 | ||||
| 133 | // Special case: empty list, nothing to do | |||
| 134 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 1711 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 1711 times.
|
1711 | if (!m_head) { |
| 135 | ✗ | return; | ||
| 136 | } | |||
| 137 | ||||
| 138 | // Special case: is the item to remove at the head? | |||
| 139 |
2/2✓ Branch 0 taken 1405 times.
✓ Branch 1 taken 306 times.
|
2/2✓ Decision 'true' taken 1405 times.
✓ Decision 'false' taken 306 times.
|
1711 | if (scheduling == m_head) { |
| 140 | 1405 | m_head = m_head->nextScheduling_s; | ||
| 141 | 1405 | scheduling->nextScheduling_s = nullptr; | ||
| 142 | 1405 | scheduling->action = {}; | ||
| 143 | } else { | |||
| 144 | 306 | auto prev = m_head; // keep track of the element before the one to remove, so we can link around it | ||
| 145 | 306 | auto current = prev->nextScheduling_s; | ||
| 146 | ||||
| 147 | // Find our element | |||
| 148 |
3/4✓ Branch 0 taken 3251 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 2945 times.
✓ Branch 3 taken 306 times.
|
0/1? Decision couldn't be analyzed.
|
3251 | 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 306 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 306 times.
|
306 | 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 306 times.
|
306 | efiAssertVoid(ObdCode::OBD_PCM_Processor_Fault, current == scheduling, "current not equal to scheduling"); | |
| 160 | ||||
| 161 | // Link around the removed item | |||
| 162 | 306 | prev->nextScheduling_s = current->nextScheduling_s; | ||
| 163 | ||||
| 164 | // Clean the item to remove | |||
| 165 | 306 | current->nextScheduling_s = nullptr; | ||
| 166 | 306 | current->action = {}; | ||
| 167 | } | |||
| 168 | ||||
| 169 | 1711 | 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 | 18664 | int EventQueue::executeAll(efitick_t now) { | ||
| 208 | 18664 | ScopePerf perf(PE::EventQueueExecuteAll); | ||
| 209 | ||||
| 210 | 18664 | int executionCounter = 0; | ||
| 211 | ||||
| 212 |
1/1✓ Branch 1 taken 18664 times.
|
18664 | assertListIsSorted(); | |
| 213 | ||||
| 214 | bool didExecute; | |||
| 215 | 37860 | do { | ||
| 216 |
1/1✓ Branch 1 taken 37860 times.
|
37860 | didExecute = executeOne(now); | |
| 217 |
4/4✓ Branch 0 taken 19196 times.
✓ Branch 1 taken 18664 times.
✓ Branch 2 taken 19196 times.
✓ Branch 3 taken 18664 times.
|
37860 | executionCounter += didExecute ? 1 : 0; | |
| 218 | } while (didExecute); | |||
| 219 | ||||
| 220 | 18664 | return executionCounter; | ||
| 221 | } | |||
| 222 | ||||
| 223 | 37860 | 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 | 37860 | scheduling_s* current = m_head; | ||
| 227 | ||||
| 228 | // Queue is empty - bail | |||
| 229 |
2/2✓ Branch 0 taken 6203 times.
✓ Branch 1 taken 31657 times.
|
2/2✓ Decision 'true' taken 6203 times.
✓ Decision 'false' taken 31657 times.
|
37860 | if (!current) { |
| 230 | 6203 | 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 12461 times.
✓ Branch 2 taken 19196 times.
|
2/2✓ Decision 'true' taken 12461 times.
✓ Decision 'false' taken 19196 times.
|
31657 | if (current->getMomentNt() > now + m_lateDelay) { |
| 240 | 12461 | 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 19196 times.
✓ Branch 4 taken 27 times.
✓ Branch 5 taken 19169 times.
|
0/1? Decision couldn't be analyzed.
|
19196 | 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 |
1/2✓ Branch 0 taken 27 times.
✗ Branch 1 not taken.
|
1/2✓ Decision 'true' taken 27 times.
✗ Decision 'false' not taken.
|
27 | if (unitTestBusyWaitHack) { |
| 258 | 27 | break; | ||
| 259 | } | |||
| 260 | #endif | |||
| 261 | ✗ | UNIT_TEST_BUSY_WAIT_CALLBACK(); | ||
| 262 | } | |||
| 263 | ||||
| 264 | // step the head forward, unlink this element, clear scheduled flag | |||
| 265 | 19196 | m_head = current->nextScheduling_s; | ||
| 266 | 19196 | 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 | 19196 | auto const action{ std::move(current->action) }; | ||
| 270 | ||||
| 271 |
1/1✓ Branch 1 taken 19196 times.
|
19196 | tryReturnScheduling(current); | |
| 272 | 19196 | 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 | 19196 | 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 19196 times.
|
19196 | 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 19196 times.
|
19196 | assertListIsSorted(); | |
| 292 | 19196 | 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 | 90315 | void EventQueue::assertListIsSorted() const { | ||
| 303 | #if EFI_UNIT_TEST || EFI_SIMULATOR | |||
| 304 | 90315 | int counter = 0; | ||
| 305 | 90315 | scheduling_s *current = m_head; | ||
| 306 |
4/4✓ Branch 0 taken 2928957 times.
✓ Branch 1 taken 14899 times.
✓ Branch 2 taken 2853541 times.
✓ Branch 3 taken 75416 times.
|
0/1? Decision couldn't be analyzed.
|
2943856 | while (current != NULL && current->nextScheduling_s != NULL) { |
| 307 |
1/2✗ Branch 2 not taken.
✓ Branch 3 taken 2853541 times.
|
2853541 | efiAssertVoid(ObdCode::CUSTOM_ERR_6623, current->getMomentNt() <= current->nextScheduling_s->getMomentNt(), "list order"); | |
| 308 | 2853541 | current = current->nextScheduling_s; | ||
| 309 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 2853541 times.
|
1/2✗ Decision 'true' not taken.
✓ Decision 'false' taken 2853541 times.
|
2853541 | if (counter++ > 1'000'000'000) |
| 310 | ✗ | criticalError("EventQueue: looks like a loop?!"); | ||
| 311 | } | |||
| 312 | #endif // EFI_UNIT_TEST || EFI_SIMULATOR | |||
| 313 | } | |||
| 314 | ||||
| 315 | 612681 | scheduling_s * EventQueue::getHead() { | ||
| 316 | 612681 | 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 | 695 | void EventQueue::clear() { | ||
| 335 | // Flush the queue, resetting all scheduling_s as though we'd executed them | |||
| 336 |
2/2✓ Branch 0 taken 569 times.
✓ Branch 1 taken 695 times.
|
2/2✓ Decision 'true' taken 569 times.
✓ Decision 'false' taken 695 times.
|
1264 | while(m_head) { |
| 337 | 569 | auto x = m_head; | ||
| 338 | // link next element to head | |||
| 339 | 569 | m_head = x->nextScheduling_s; | ||
| 340 | ||||
| 341 | // Reset this element | |||
| 342 | 569 | x->setMomentNt(0); | ||
| 343 | 569 | x->nextScheduling_s = nullptr; | ||
| 344 | 569 | x->action = {}; | ||
| 345 | } | |||
| 346 | ||||
| 347 | 695 | m_head = nullptr; | ||
| 348 | 695 | } | ||
| 349 |