Stack Analysis

What is Stack Depth Analysis?

Calling a function or handling an interrupt requires allocation of memory from the stack memory region. If the stack memory region is not large enough to hold the stack, RAM is corrupted, leading to difficult, non-deterministic node failure. For obvious reasons these failures cannot be replicated in TOSSIM.

In a TinyOS application (as in any embedded system lacking virtual memory) the size of the stack is determined statically and it is important that the size be chosen appropriately. The stack region must not be too small. If it is too large the system will operate correctly, but RAM that could have been put to good use is wasted.

TinyOS (without TOSThreads) has a single stack. When a heap is not in use, the size of the stack memory region is simply:

(RAM size) - (data segment size) - (BSS segment size)

The only question is: Is this region large enough? The most common way to answer this question is by running the system. If it crashes in a non-deterministic way, one of the things a developer will try is to reduce the size of the data or BSS segments.

Stack depth analysis offers a more principled alternative: static analysis of the compiled application in order to predict its worst case stack memory usage.

For applications that use a heap and/or threads, the situation is more complicated.

Stack Depth Analysis for TinyOS

A stack depth checking tool is available from the TinyOS CVS repository (and will be available in the next release following TinyOS 2.1). You can get this tool either by checking out the entire repository or by using this direct link into the CVS repository. The remainder of this tutorial will assume that tos-ramsize is in your path (because, for example, you ran "make install" in tinyos-2.x/tools).

Running tos-ramsize directly

Given an application for one of the AVR platforms, you can run a command like this:

[regehr@babel BaseStation]$ tos-ramsize micaz ./build/micaz/main.exe 

The result should be something like:

BSS segment size is 1708, data segment size is 16
The upper bound on stack size is 538
The upper bound on RAM usage is 2262
There are 1834 unused bytes of RAM

Here the tool is telling us that for the BaseStation application on the MicaZ platform, approximately 1.8 KB of RAM is free and could have been allocated for packet buffers or some other purpose.

Running tos-ramsize from the build system

Run a command like this:

[regehr@babel MultihopOscilloscope]$ make micaz stack-check

The result should be something like:

[regehr@babel MultihopOscilloscope]$ make micaz stack-check
mkdir -p build/micaz
    compiling MultihopOscilloscopeAppC to a micaz binary
ncc -o build/micaz/main.exe  -Os -fnesc-separator=__ -Wall -Wshadow -Wnesc-all -target=micaz -fnesc-cfile=build/micaz/app.c -board=micasb -DDEFINED_TOS_AM_GROUP=0x22 --param max-inline-insns-single=100000 -I/home/regehr/z/tinyos-2.x/tos/lib/net/ -I/home/regehr/z/tinyos-2.x/tos/lib/net/ctp  -I/home/regehr/z/tinyos-2.x/tos/lib/net/4bitle -DIDENT_APPNAME=\"MultihopOscillo\" -DIDENT_USERNAME=\"regehr\" -DIDENT_HOSTNAME=\"babel\" -DIDENT_USERHASH=0xaa57ee96L -DIDENT_TIMESTAMP=0x49e3a884L -DIDENT_UIDHASH=0xb4560dc8L -fnesc-dump=wiring -fnesc-dump='interfaces(!abstract())' -fnesc-dump='referenced(interfacedefs, components)' -fnesc-dumpfile=build/micaz/wiring-check.xml MultihopOscilloscopeAppC.nc -lm 
/home/regehr/z/tinyos-2.x/tos/chips/cc2420/lpl/DummyLplC.nc:39:2: warning: #warning "*** LOW POWER COMMUNICATIONS DISABLED ***"

BSS segment size is 3421, data segment size is 24
The upper bound on stack size is 578
The upper bound on RAM usage is 4023
There are 73 unused bytes of RAM

    compiled MultihopOscilloscopeAppC to build/micaz/main.exe
           25458 bytes in ROM
            3445 bytes in RAM
avr-objcopy --output-target=srec build/micaz/main.exe build/micaz/main.srec
avr-objcopy --output-target=ihex build/micaz/main.exe build/micaz/main.ihex
    writing TOS image

Here, tos-ramsize is telling us that only 73 bytes of memory are available.

Limitations

write me

Internals

write me