How to determine maximum stack usage?

Question

What methods are available for determining the optimum stack size for embedded/memory constrained system? If it's too big then memory is wasted that could be used elsewhere. However, if it is too small then we get this website's namesake...

To try to jump start things: Jack Ganssle states in The Art of Designing Embedded Systems that, "With experience, one learns the standard, scientific way to compute the proper size for a stack: Pick a size at random and hope." Can anyone do better than that?

A more specific example was requested. So, how about a C program targeting an MSP430 MCU with 2 kB of RAM using the IAR Embedded Workbench toolchain without an operating system? This IDE can display the stack contents and usage while using a JTAG debugger.

Answer 1

You tagged your question with static-analysis, but this is a problem that is difficult to solve through static-analysis. The stack usage depends on the program's runtime profile, especially, if you're using recursion or alloca. Given that this is an embedded platform I guess it's also difficult to run something like ps or top and see how much stack your application is using.

An interesting approach is to use the address of the current stack frame in order to determine how much stack is used. You can do this by taking the address of a function's argument or local variable. Do that for the main function and for functions you think are using the most stack. The difference will tell you the amount of stack your application requires. Here is an example (assuming customary high-to-low stack growth).

char *stack_top, stack_bottom;

int
main(int argc, char *argv[])
{
    stack_top = (char *)&argc;
    // ...
    printf("Stack usage: %d\n", stack_top - stack_bottom);
}

void
deeply_nested_function(void)
{
    int a;
    stack_bottom = (char *)&a;
    // ...
}

If your compiler allows you to specify a custom function prologue (many do it to allow graph-based program profiling), you can even arrange for all functions to call such measuring code. Then your measurement function mecomes something like

void
stack_measurement_function(void)
{
    int a;
    stack_bottom = min(stack_bottom, (char *)&a);
    // ...
}

I used an approach similar to what I've described to generate these charts.

Answer 2

The most common way to determine the deepest stack usage is to initialize the stack memory with some known but unusual value, then periodically (or at the end of a big test run) see where that pattern stops.

This is exactly how the IAR IDE determines the amount of stack used.

Answer 3

With a good source code static analysis tool, you can produce a call graph for your application. Given that, and estimates of the amount of locals/temporaries produced by your compiler, you can straightforwardly compute a conservative estimate of the stack demand.

What I mean by "good" analysis tool is one that can read all the compilation units involved, can determine direct function calls, can determine indirect pointers, in the compilaiton unit, can compute a conservative points-to analysis across the entire system, can construct a call graph taking into account the points-to analysis. This eliminates a lot of tools, which is why one sees ad hoc methods such as "fill the stack at runtime and see what happens". You also need estimates of the stack demands the compiler places on the stack; you can approximate a lot of this by simply knowing how big the storage demands of all the types are, which is generally fairly easy to determine for embedded systems C programs. Finally, you need to believe that you applicaiton doesn't have recursive calls, or that the tool has an idea of the deepest recursion (probably by you telling it).

The DMS Software Reengineering Toolkit meets all of these requirements for C programs. See http://www.semanticdesigns.com/Products/DMS/DMSToolkit.html You still have to configure it to compute the stack demand by crawling the call graph and using the various size estimates.

If you want a fast answer, use the stack-fill trick. If you want an answer that you can recompute after each source code change you'll need the static analysis approach.