Stack Analysis
Contents
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. More sophisticated approaches include observing the maximum extent of the stack using a simulator, using debugging printouts, or filling the stack with known values and seeing how many get overwritten. All such techniques are unsafe and can only provide lower bounds on worst case stack memory usage.
Stack depth analysis offers a more principled alternative: static analysis of the compiled application in order to compute an upper bound on worst-case stack memory usage.
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.
Getting More Information
By default, tos-ramsize runs at a verbosity level of 1. By specifying higher levels, you can get more detailed information. For example:
[regehr@babel BaseStation]$ tos-ramsize -verbosity=2 micaz ./build/micaz/main.exe analyzing elf file './build/micaz/main.exe' for platform 'micaz' there are: 112 labels 6252 instructions per-vector results: vector 0 max depth = 127 (not atomic) vector 1 max depth = 5 (atomic) vector 2 max depth = 5 (atomic) vector 3 max depth = 5 (atomic) vector 4 max depth = 5 (atomic) vector 5 max depth = 5 (atomic) vector 6 max depth = 5 (atomic) vector 7 max depth = 39 (atomic) vector 8 max depth = 5 (atomic) vector 11 max depth = 45 (not atomic) vector 12 max depth = 125 (not atomic) vector 13 max depth = 5 (not atomic) vector 14 max depth = 9 (not atomic) vector 15 max depth = 26 (not atomic) vector 16 max depth = 6 (atomic) vector 17 max depth = 132 (atomic) vector 18 max depth = 26 (atomic) vector 20 max depth = 28 (not atomic) vector 24 max depth = 5 (not atomic) vector 25 max depth = 7 (not atomic) vector 26 max depth = 5 (not atomic) vector 27 max depth = 5 (not atomic) vector 28 max depth = 5 (not atomic) vector 29 max depth = 9 (not atomic) vector 30 max depth = 6 (atomic) vector 32 max depth = 5 (not atomic) 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 tos-ramsize has printed the contribution to worst-case stack memory usage of each interrupt vector, and also has told us whether it believes each vector to be atomic (runs with interrupts disabled) or nonatomic. At level 3 the callgraph and the stack memory usage of each function is printed. Higher levels become increasingly useless except for debugging tos-ramsize.
The Model
Computing the worst-case stack memory used by sequential code is generally simple. To put the sequential results together to create a global result, tos-ramsize assumes that the worst-case stack memory usage of an application is the stack usage of main() plus the sum of the stack memory used by all nonatomic interrupt handlers plus the maximum stack memory used by any atomic interrupt handler. The assumption is that interrupt handlers may nest but that they may not reenter. These assumptions are discussed in more detail below.
Assumptions
The correctness of tos-ramsize's results are predicated on some important assumptions.
No Reentrant Interrupts
A reentrant interrupt is one that may have multiple instances on the stack at the same time. For example, consider the following scenario where your application requests high-frequency timer interrupts. First, the timer device requests an interrupt, causing your handler to run. Second, your handler re-enables interrupts. Third, either your handler runs for longer than expected or else a second interrupt handler preempts the timer handler. Finally, the timer device requests its next interrupt, causing the timer handler to be reentered.
tos-ramsize assumes that this scenario never happens. There are three ways to avoid reentrant interrupts:
- Make all interrupt handlers atomic, meaning that they do not run with interrupts enabled
- For every non-atomic interrupt handler in your application, ensure that it returns-from-interrupt before the same interrupt source becomes pending again. In other words, prove that the maximum execution time of the interrupt handler -- including the maximum execution time of all interrupts that may preempt it -- is smaller than the minimum interarrival time of that interrupt.
- Use a platform that supports prioritized interrupts in a reasonable fashion (AVR is not one of them)
Control Flow Integrity
Basically, every function must return control to the instruction that follows the call that invoked it. This is normally the case. Control flow integrity is violated when the compiler or application is buggy. In the most common scenario, a pointer or array bug in the application permits a return address on the stack to be accidentally or deliberatively overwritten. See Safe TinyOS.
Interrupts Are Correctly Classified as Atomic/Nonatomic
tos-ramsize attempts to classify interrupts as atomic or non-atomic. As previously mentioned, an interrupt is non-atomic if it may run with interrupts enabled. tos-ramsize marks an interrupt handler as non-atomic if the sei instruction is executed in any function reachable from that interrupt handler. Stores to SREG, on the other hand, are assumed to be part of nesc_atomic_end() calls-- which only enable interrupts if they were previously enabled.
No Hidden Stack Pointer Updates
tos-ramsize cannot predict worst-case stack depth unless it can correctly interpret all manipulation of the stack pointer. On the AVR architecture, indirect stores can be used to change the SP. You should not write code that does this.
Common Failure Modes
tos-ramsize tries to die if it detects a condition that prevents successful stack depth analysis. These include the following.
"cannot estimate stack depth due to recursive loop"
A TinyOS application can use recursion in a variety of ways. First, it can call a library function such as quicksort(). Second, component programming errors such as signaling events from commands can easily lead to recursive loops. tos-ramsize looks for recursive loops. If such a loop is found, an example is printed and the tool terminates. The example provided will be in terms of the compiled code where function inlining has taken place, so some digging will be required in order to find the source-level recursive loop. tos-ramsize must abort when recursion is detected because it cannot predict the maximum number of times that loop will be traversed.
Recommended action: Remove the recursive loop from your application. If the loop is in TinyOS, ask the subsystem maintainer to remove it. If the loop is in the C library, send a bug report to get an exception added to tos-ramsize for this situation.
"cannot process raw indirect call/jump"
tos-ramsize must know the entire set of possible targets for every indirect call or jump that it encounters in the object code. It includes special code to recognize some forms of these, such as indirect jumps that come from compiling switches, and indirect calls in certain library functions. When an unknown indirect call/jump is found, the tool must terminate.
Recommended action: If the indirect call/jump is your fault (for example, due to use of a function pointer or setjmp/longjmp), stop using that construct. If the indirect call/jump is not your fault, report a bug.
Limitations
At present:
- Only the AVR platforms are supported. MSP430 is not difficult to support but this is not super high priority since the MSP430 variants used by TinyOS have a relatively generous 10 KB of SRAM.
- TOSThreads is not supported. This support is highly desirable because it will permit each thread to be provided with precisely as much stack memory as it requires. However, the details are still being worked out.
Feedback
Please send problem reports and other feedback to tinyos-help or tinyos-devel, as appropriate.
