By Jack Ganssle

Stack Management

Published 11/03/2006

Intel's 4004, the first microprocessor, had an on-chip hardware stack a mere three levels deep. When a year later the 8008 came out, it, also had a hardware stack, boosted to a depth of seven words. Since neither had push and pop instructions the stack contained only return addresses from CALL instructions. No, interrupts did not necessarily eat stack space. An interrupt cycle initiated a nearly-normal fetch. It was up to external hardware to jam an instruction onto the bus. Though most designers jammed an RST, a single-byte CALL, more than a few used alternatives like JMP.

With these tiny stacks developers constantly worried about deep call trees, for there were no tools to trace program execution. But programs were small. After getting burned once one learned to sketch simple execution path diagrams to track call depth.

We take a wild guess.

Get it wrong and you're either wasting expensive RAM or inserting a deadly bug that might not surface for years when the perfect storm of interrupts and deep programmatic stack usage coincide.

I've read more than a few academic papers outlining alternative approaches that typically analyze the compiler's assembly listings. But without complete knowledge of the runtime library's requirements, and that of other bits of add-in software like communications packages, these ideas collapse.

Today wise developers monitor stack consumption using a variety of methods, like filling a newly-allocated stack with a pattern (I like 0xDEAD) and keeping an eye on how much of that gets overwritten. Some RTOSes include provisions to log high-water marks.

But these are all ultimately reactive. We take a stack-size guess and then start debugging. When something goes wrong, change the source code to increase the stack's size. It violates my sense of elegance, paralleling as it does the futile notion of testing quality into a product. It's better to insert correctness from the outset.

AdaCore has a new tool (http://www.adacore.com/2006/10/31/2006-10-31-gnatstack/) that almost does this. It takes extant code (unfortunately, Ada only) and using proprietary information generated by their compiler generates a somewhat complex assessment of required stack space. The tool can't know everything, but does offer a first or second level approximation that has to be very useful.

The tool produces metrics that are a step closer to provably correct software, and a big jump away from the notion of "hey, it seems to work. Ship it."

What do you think? Have you used a tool like this? How do you manage stack size?