Stack and Memory Budgeting for a Set of Preemptive Tasks

A preemptive kernel gives each task its own stack because the task’s call frames have to survive preemption: when a task is switched out mid-call, its locals and return addresses live on its stack until it resumes, which may be milliseconds later or never. The memory cost is one stack per task, plus one for the main context, plus one for interrupts if the kernel uses a separate interrupt stack. Sizing them is the part that goes wrong, usually in the direction of too small, and the failure appears as a corrupted variable in an unrelated task.

What a stack frame contains under a real-time kernel

The task’s own frames are the familiar ones: arguments, locals, saved callee-saved registers, return addresses. On top of those comes the exception frame. When an interrupt preempts a task, the core pushes a context frame onto the current stack — eight registers, thirty-two bytes on ARMv7-M — and the handler’s own frames go above. If the handler itself is preempted by a higher-priority interrupt, another frame and another context frame are added.

The nesting depth is therefore not a property of the task alone. It is the task’s own depth plus the depth of the deepest chain of interrupt handlers that can preempt it. A low-priority task that spends most of its time idle can still need a large stack if an interrupt arriving during its deepest call can nest three levels with a stack-hungry handler at the bottom.

A separate interrupt stack removes that coupling. Interrupts run on the system stack, tasks keep their own, and each task’s requirement drops to its own call depth plus the one exception frame needed if the stack switch happens after the frame is pushed. The system stack then has to be sized for the worst nesting of handlers, which is a single number for the whole system rather than a per-task addition. Kernels differ in whether they support a separate stack at all and in whether the switch happens before or after the frame is pushed. On ARMv8.1-M parts the core adds stack limit registers, one for the main stack and one for the process stack, which turn a store below the limit into a fault; that replaces the guard region with an architectural check but does not change the sizing arithmetic.

The kernel’s own context save adds a fixed amount above the task’s frame. A full register save adds a fixed number of words, and the kernel’s scheduler frame adds a handful more. The value is in the kernel’s documentation or in the port’s assembly, and it should be treated as a constant in the budget.

Computing worst-case stack depth

The textbook method is to build a call graph, compute each function’s frame size, and find the longest path from a root to a leaf. With indirect calls through function pointers the graph is not a tree, and the longest path may be through a pointer whose target is known only at run time.

Several mitigations make the problem tractable. The first is to remove recursion, which MISRA and most coding standards for embedded C require anyway, so that the call graph is acyclic and the longest path is finite. The second is to bound indirect calls: a driver registration mechanism with a small, fixed set of handlers can have its worst path computed by taking the maximum over the registered handlers. The third is to measure rather than compute, by filling the stack with a known pattern at startup and checking the high-water mark — the lowest address that the pattern was overwritten to — after a long run.

High-water measurement has two limits worth stating. It sees only the paths that were taken, so a fault path that runs once in a thousand hours is not in the measurement; and it is defeated by a stack that overflows silently into adjacent memory rather than into a guard region. A pattern of a single byte value can also be coincidentally matched by real data, so a 32-bit pattern with a mixed value is safer. The standard combination is high-water measurement for the normal paths, plus a computed bound for the worst path, plus a safety margin, plus a guard.

The guard is the part that turns a silent corruption into a diagnosable fault. Fill the region below each task’s stack with a known value, or place the stack just above a memory region that the MPU marks as no-access, and check the guard on every context switch. The check costs a comparison per switch; the alternative is a corrupted pointer in a task that was never involved. On parts with a memory protection unit the no-access region is the better tool, because it turns the overflow into an immediate fault at the offending store rather than a delayed corruption.

The margin, and why percentages are not enough

A margin of a few hundred bytes on a small stack is a reasonable buffer against compiler changes, library version differences, and the occasional deeper path. A percentage margin is misleading on small stacks: 20 percent of a 256-byte stack is 51 bytes, which is less than one frame on some compilers.

Frame sizes are not stable across builds. A change in optimisation level, a new compiler version, or a switch from one C library’s floating-point formatting to another can change the depth of the deepest path by tens of bytes. Builds that differ in this way should be re-measured rather than assumed to be equivalent, and the budget should record the toolchain version it was measured with.

Library calls are the usual cause of a surprise. printf-family functions are among the deepest callers in any code base because they reach into formatting, and floating-point formatting in particular can pull in a large working set. A task that logs error messages has to be sized for the formatter, not for its own code, and a system that is short of memory replaces the formatter with a small integer-only version for this reason.

The other memory the kernel needs per task

The stack is the largest per-task allocation but not the only one. The task control block holds the saved stack pointer, the priority, the state, the list links, and the notification or event fields: a few dozen bytes to a few hundred depending on the kernel’s features. The ready list, the delay list, and any wait lists the task can be on need links, which are in the control block.

Queues allocate their storage at creation or statically, and the item count times the item size is a budget that has to be argued like any other. A queue of 16 items of 32 bytes is 512 bytes, which on a part with 32 KB of RAM is a noticeable share; a queue that holds pointers to pooled buffers uses less per entry but needs the pool. The trade between copying into a queue and passing ownership of a buffer is a real one, and it interacts with the latency budget: passing a buffer defers the copy to the consumer, which may be the right thing when the producer is an interrupt handler.

Kernel objects are often allocated from a heap at run time, which brings fragmentation into a system that otherwise has none. Static allocation removes the fragmentation and the failure path but requires the sizes to be known at configuration time. Kernels that offer a static-only configuration option exist precisely because the heap’s worst case is not analysable: a request that cannot be satisfied returns null, the kernel’s own internal allocations can fail, and the failure happens at the worst possible moment. A design that allocates all kernel objects at startup and never frees them gets most of the benefit without the configuration burden.

Reading a memory budget

The budget is a table with a row per task and a column per allocation, plus a row for the kernel’s own data and one for the shared pools. Its purpose is the same as the latency budget’s: to show which change moves which number and to make the total visible before the linker reports that the region is full.

A useful discipline is to compare the sum against the region’s size with the largest single allocation removed, which shows whether the design is tight or has a structural problem. A system that is at 95 percent and whose tightest item is one task’s stack has a fixable problem; a system that is at 95 percent with every item near its computed bound has a design that will not fit the next feature.

The link between this and the timing side is direct: the analysis in response-time analysis for fixed-priority sets assumes the tasks run at their measured execution times, and a stack that is too small changes those times by adding fault handling or, worse, changes behaviour entirely. A task set that is schedulable on paper and has a corrupted stack is not schedulable.

Memory and timing also trade against each other in the handler design: inline processing uses more stack (the handler’s frames go on the task stack) and less queue memory, while deferred processing uses less stack per task and more queue memory. The decision in deferred interrupt work is partly a memory decision, and the two budgets should be reviewed together.