Stack Size Estimation
In multi-threaded embedded software (written in C or C++), a thread must be given enough stack space in order to allow it to complete its operations without overflowing. Correct sizing of the stack is critical in some real-time embedded environments, because (at least in some systems I've worked with), the operating system will NOT detect this for you.
Usually, the stack size for a new thread (other than the main thread) is designated at the time that thread is created (i.e. in an argument to pthread_create() or the like). Often, these stack sizes are hard-coded to values that are known to be good at the time the code was originally written or tested.
However, future changes to the code often break the assumptions on which the hard-coded stack sizes were based, and one fateful day, your thread enters one of the deeper branches of its call graph and overflows the stack -- bringing down the whole system or silently corrupting memory.
I have personally seen this problem in the case where code executed in the thread declares struct instances on the stack. When the struct is augmented to hold additional data, the stack size inflates accordingly, potentially allowing stack overflows to occur. I imagine this could be a huge problem for established codebases where the full effects of adding fields to a structure cannot be known immediately (too many threads/functions to find all the places where that struct is used).
Since the usual response to "stack sizing" questions is "they're not portable", let's assume that the compiler, operating system, and processor are all known quantities for this investigation. Let's also assume recursion isn't used, so we're not dealing with the possibility an "infinite recursion" scenario.
What are some reliable ways to estimate the necessary stack size for a thread? I'd prefer methods that are offline (static analysis) and automatic, but all ideas are welcome.
Answer
Runtime-Evaluation
An online method is to paint the complete stack with a certain value, like 0xAAAA (or 0xAA, whatever your width is). Then you can check how large the stack has maximally grown in the past by checking how much of the painting is left untouched.
Have a look at this link for an explanation with illustration.
The advantage is that it's simple. A disadvantage is that you cannot be certain that your stack size won't eventually exceed the amount of used stack during your testing.
Static Evaluation
There are some static checks and I think there even exists a hacked gcc version that tries to do this. The only thing I can tell you is that static checking is very difficult to do in the general case.
Also have a look at this question.