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.