JOSTALY TECHNOLOGIES JOHN SETH THIELEMANN July 31, 2024 Article Preview: Unit Test Scheduler Starvation Case 1. Problem A recent change to the core scheduler code to determine if a task switch was required bypassed logic to send an SMP heartbeat to secondary CPU(s) causing starvation. 2. Solution Breakout logic into simple function, calling scheduler logic under both return cases must ensure an SMP heartbeat is generated to a secondary CPU(s) with a finished task. Breakout logic within the scheduler: + constexpr Errno scheduleUpdateCurrentTask(size_t cpuId, RegisterFile& regs) noexcept { + if (m_current[cpuId]) { + m_current[cpuId]->update(regs); + + if (!doTaskSwitch(cpuId)) { + regs = m_current[cpuId]->registers(); + return Errno::ESRCH; + } + + if (!m_current[cpuId]->isComplete()) + if (!m_queue.enqueue(m_current[cpuId])) + return Errno::EAGAIN; + } + + return Errno::OK; + } The logic within this broken-out function is under unit test. The primary goal for the new unit test, is to ensure that both variations of return cause an SMP heartbeat to a CPU with a completed task. 3. Complete Unit Test The unit test to ensure proper behavior, complete to digiest, then is broken down for analysis: constexpr static void starvedTask(void) noexcept { while(1) { /* Never actually runs */ } } constexpr static void gluttonTask(void) noexcept { while(1) { /* Never actually runs */ } } addr_t starvationCpuIrqTaskSwitch(MemoryManager& heap) noexcept { arch::RegisterFile dummyContext; const size_t cpus = 2; bool smpFlag = false; Affinity smpAffinity; auto starvationSmpIrq = [&](size_t irq, Affinity affinity) { smpFlag = true; smpAffinity |= affinity; return Errno::OK; }; CpuScheduler scheduler(heap, cpus, SmpController::generate_irq_t(starvationSmpIrq)); if (!scheduler) return 0x01; if (scheduler.m_smp.modifyMap(SmpIrqType::Heartbeat, 0x01) != Errno::OK) return 0x02; Pair> starved = scheduler.createTask( heap, &CpuSchedulerTest::starvedTask); if (starved.m_first != Errno::OK) return 0x03; if (!starved.m_second) return 0x04; Pair> glutton = scheduler.createTask( heap, &CpuSchedulerTest::gluttonTask); if (glutton.m_first != Errno::OK) return 0x05; if (!glutton.m_second) return 0x06; if (Errno::OK != scheduler.schedule(starved.m_second)) return 0x07; if (Errno::OK != scheduler.schedule(glutton.m_second)) return 0x08; if (Errno::OK != scheduler.cpuSchedule(0, dummyContext)) return 0x09; if (Errno::OK != scheduler.cpuSchedule(1, dummyContext)) return 0x0A; if (scheduler.m_current[0]->id() != starved.m_second->id()) return 0x0B; if (scheduler.m_current[1]->id() != glutton.m_second->id()) return 0x0C; smpFlag = false; smpAffinity = Affinity(Affinity::Mask::Invalid); if (Errno::OK != scheduler.cpuSchedule(1, dummyContext)) return 0x0D; if (smpFlag) return 0x0E; if (!starved.m_second->state(ExecutionState::Finished)) return 0x0F; if (Errno::ESRCH != scheduler.scheduleUpdateCurrentTask(1, dummyContext)) return 0x10; if (Errno::OK != scheduler.cpuSchedule(1, dummyContext)) return 0x11; if (!smpFlag) return 0x12; if (smpAffinity != Affinity::affinityCpu(0)) return 0x13; smpFlag = false; smpAffinity = Affinity(Affinity::Mask::Invalid); if (!glutton.m_second->state(ExecutionState::Finished)) return 0x14; if (Errno::OK != scheduler.cpuSchedule(1, dummyContext)) return 0x15; if (!smpFlag) return 0x16; if (!smpAffinity & Affinity::affinityCpu(0)) return 0x17; if (!smpAffinity & Affinity::affinityCpu(1)) return 0x18; return 0; } 4. Breakdown and Analysis: constexpr static void starvedTask(void) noexcept { while(1) { /* Never actually runs */ } } constexpr static void gluttonTask(void) noexcept { while(1) { /* Never actually runs */ } } addr_t starvationCpuIrqTaskSwitch(MemoryManager& heap) noexcept { arch::RegisterFile dummyContext; const size_t cpus = 2; bool smpFlag = false; Affinity smpAffinity; auto starvationSmpIrq = [&](size_t irq, Affinity affinity) { smpFlag = true; smpAffinity |= affinity; return Errno::OK; }; CpuScheduler scheduler(heap, cpus, SmpController::generate_irq_t(starvationSmpIrq)); This section is largely the setup. A dummy architectural register context is needed to call scheduler functions, and the flags are for verifying proper behavior (below). The empty static functions were chosen to reduce the complexity of the unit test. The lambda was chosen to keep the test within the single scope of the testing function. if (!scheduler) return 0x01; if (scheduler.m_smp.modifyMap(SmpIrqType::Heartbeat, 0x01) != Errno::OK) return 0x02; Verify the scheduler test object was created successfully, bypass external logic to enable SMP heartbeat irq logic. Pair> starved = scheduler.createTask( heap, &CpuSchedulerTest::starvedTask); if (starved.m_first != Errno::OK) return 0x03; if (!starved.m_second) return 0x04; Pair> glutton = scheduler.createTask( heap, &CpuSchedulerTest::gluttonTask); if (glutton.m_first != Errno::OK) return 0x05; if (!glutton.m_second) return 0x06; This code creates the dummy starvation and glutton tasks, then proceeds to verify that the return value was successful and that the task is valid. if (Errno::OK != scheduler.schedule(starved.m_second)) return 0x07; if (Errno::OK != scheduler.schedule(glutton.m_second)) return 0x08; if (Errno::OK != scheduler.cpuSchedule(0, dummyContext)) return 0x09; if (Errno::OK != scheduler.cpuSchedule(1, dummyContext)) return 0x0A; if (scheduler.m_current[0]->id() != starved.m_second->id()) return 0x0B; if (scheduler.m_current[1]->id() != glutton.m_second->id()) return 0x0C; This section queues up the starvation and glutton tasks within the scheduler, calls the cpu scheduling function for each CPU to move the tasks into the internal current datastructure and verifies the task IDs. smpFlag = false; smpAffinity = Affinity(Affinity::Mask::Invalid); if (Errno::OK != scheduler.cpuSchedule(1, dummyContext)) return 0x0D; if (smpFlag) return 0x0E; Start with clean slate on smp flags, kick the scheduler and verify that no SMP action has been taken. if (!starved.m_second->state(ExecutionState::Finished)) return 0x0F; if (Errno::ESRCH != scheduler.scheduleUpdateCurrentTask(1, dummyContext)) return 0x10; if (Errno::OK != scheduler.cpuSchedule(1, dummyContext)) return 0x11; if (!smpFlag) return 0x12; if (smpAffinity != Affinity::affinityCpu(0)) return 0x13; Set the starved task to Finished, verify that there is no need for a task switch on CPU(1), then verify calling into the scheduler was successful. Next ensure that the SMP flag was set correctly and that an SMP irq generate call would've been issued to CPU(0). smpFlag = false; smpAffinity = Affinity(Affinity::Mask::Invalid); if (!glutton.m_second->state(ExecutionState::Finished)) return 0x14; if (Errno::OK != scheduler.cpuSchedule(1, dummyContext)) return 0x15; if (!smpFlag) return 0x16; if (!smpAffinity & Affinity::affinityCpu(0)) return 0x17; if (!smpAffinity & Affinity::affinityCpu(1)) return 0x18; Set the glutton task to Finished, this will cause a task switch to be required and travel down the alternate return path. Call into the scheduler, and then verify that an SMP irq would be generated for both CPUs. return 0; } Indicate successful unit test.