Determining Worst-Case Stack Depth
To prevent stack overflow you may need to know the worst-case stack depth of a C program. Here's how to find out.

This page describes how to determine stack space usage with the PDQ Board Users Guide and prevent stack overflow. This "tips and tricks" article is aimed at those doing software development using GNU C (GCC) via the Codeblocks-based IDE Plus C compiler, however the topics covered apply to Forth programs as well.

If inadequate stack space is assigned to an application, stack overflow can cause hard-to-debug crashes, or worse, seemingly random computational errors. Stack overflow often occurs because some routines require surprisingly great stack depth (printf is notorious for this). To guard against overflow, you must reserve sufficient stack space. But how can we know what is sufficient? There are two methods, analytical and empirical, that should bracket the actual stack depth requirement.

The analytical approach to sizing stacks requires analyzing the code, routine-by-routine, to determine their independent stack use, then using the application's call map to tally the maximum stack size. In the simplest case you can count all push, pop, call, and return instructions along different execution paths through the compiled code and add their stack requirements. Of course, this approach doesn't scale well to large programs! But even with large code bases its relatively easy to tally a worst-case stack depth to each routine assuming a worst case execution path, and hence to get an ultimate overestimation of the stack depth required.

The empirical approach requires that you run the application with diverse inputs and data to exercise as many execution paths as possible, and directly observer how much stack space was used. Because this approach can miss some rarely called but circuitous execution paths through the code, it provides a lower limit on the true maximum stack depth.

This page focuses on finding the empirical lower bound. The method consists of:

1. Allocating adequate stack space and initializing it.
2. Running the application and attempting to test it over all its internal paths by providing all combinations of input and parameters.
3. Directly examining the stack area and see how much of the stack was actually used.

The GNU C Call Stack is used for the following functions:

• Storing the return address of a subroutine
• Storing local variables
• Passing parameters to subroutines
• Evaluation of arithmetic or logical operations

Because GNU C mixes diverse data and control types on the stack, it's often tricky to calculate stack usage for routines, necessitating actual measurement.

It is important to note that program flow affects stack usage – a branch in your program might use twice as much stack space when followed as when not followed. Consequently, it's is difficult to correctly determine the worse case stack usage. Before running the tests below, you should examine your program and verify that the most deep execution paths are taken when main is executed.

The function that takes the most stack space is printf() by far. Depending on the formatting options given to printf(), stack space usage can be over 950 bytes!

It can be very useful to determine the stack usage of the default, or Forth, task. This default task is setup when the PDQ Kernel boots. When your program enters main() it is running from the default task.

First we need to erase the stack. Because we are operating from forth, we cannot erase the entire stack. Doing so would crash the board. Instead we can erase the majority of the stack, less 100 ( 0x64 ) bytes:

HEX
(sp) 0              \ stack address
(rp) (sp) - 0x64 -  \ stack length less 0x64
ERASE
 
(sp) 0              \ stack address
(rp) (sp) -         \ stack length
DUMP

The resulting dump should be filled with all 00's (except for the bottom). This is the starting state for our stack.

If your program uses no other tasks, you can continue on to fill-up-the-stack below.

If your program uses one or more additional tasks, it is very useful to determine the maximum stack usage of each task. In this example, we declare our task, named 'CalculationTask', like this:

TASK CalculationTask;

First we need to determine the memory location and size of the stack. Add this line to main() in your program:

printf("The requested stack is located at 0x%x and has a size of 0x%x bytes.\n", (int)CalculationTask.rstack, sizeof(CalculationTask.rstack) );

After compiling and loading your program, the results from the line above will look something like this:

The requested stack is located at 0x6686 and has a size of 0x400 bytes.

With this information, we can fill the bytes in the stack with a known value (0x00) and then run our task. After the task has run for awhile, we dump out the contents of the stack and observe stack usage.

To get started, type "cold" to reset the board, and stop any running tasks. Type the following command in, replacing the values below with the results from your program:

HEX
6686 0 400 ERASE
6686 0 400 DUMP

The resulting dump should be filled with all 00's. This is the starting state for our stack.

Run your program by typing "main". Let the task in your program run for a few minutes, and then execute the following command. If your main() function never exits, you can press the reset button on the board before the typing in this command:

HEX 6686 0 400 DUMP 

(sp) 0 (rp) (sp) - DUMP

The resulting memory dump should have an area of all 00's at the top. Somewhere in the middle, bytes will have non-zero values. The memory location of the first non-zero byte is the worst case depth of the stack. If your dump does not have an area of all 00's at the top, your program has overflowed its allocated stack space. In this event, the stack has overwritten other parts of memory. This usually causes the processor to crash, but not always. You should avoid a stack overflow at all costs.

If a task uses few bytes on the stack, it is possible to save common memory space by changing how the task is declared. Consider declaring a memory efficient task as "small_taskArea" instead of "TASK". Any task that uses printf() cannot be declared as a "small_taskArea".

See also → Using Paged Memory