Checking stack usage at compile time

Question

Is there a way to know and output the stack size needed by a function at compile time in C ? Here is what I would like to know :

Let's take some function :

void foo(int a) {
    char c[5];
    char * s;
    //do something
    return;
}

When compiling this function, I would like to know how much stack space it will consume whent it is called. This might be useful to detect the on stack declaration of a structure hiding a big buffer.

I am looking for something that would print something like this :

file foo.c : function foo stack usage is n bytes

Is there a way not to look at the generated assembly to know that ? Or a limit that can be set for the compiler ?

Update : I am not trying to avoid runtime stack overflow for a given process, I am looking for a way to find before runtime, if a function stack usage, as determined by the compiler, is available as an output of the compilation process.

Let's put it another way : is it possible to know the size of all the objects local to a function ? I guess compiler optimization won't be my friend, because some variable will disappear but a superior limit is fine.

Answer 1

Linux kernel code runs on a 4K stack on x86. Hence they care. What they use to check that, is a perl script they wrote, which you may find as scripts/checkstack.pl in a recent kernel tarball (2.6.25 has got it). It runs on the output of objdump, usage documentation is in the initial comment.

I think I already used it for user-space binaries ages ago, and if you know a bit of perl programming, it's easy to fix that if it is broken.

Anyway, what it basically does is to look automatically at GCC's output. And the fact that kernel hackers wrote such a tool means that there is no static way to do it with GCC (or maybe that it was added very recently, but I doubt so).

Btw, with objdump from the mingw project and ActivePerl, or with Cygwin, you should be able to do that also on Windows and also on binaries obtained with other compilers.

Answer 2

StackAnlyser seems to examinate the executable code itself plus some debugging info. What is described by this reply, is what I am looking for, stack analyzer looks like overkill to me.

Something similar to what exists for ADA would be fine. Look at this manual page from the gnat manual :

22.2 Static Stack Usage Analysis

A unit compiled with -fstack-usage will generate an extra file that specifies the maximum amount of stack used, on a per-function basis. The file has the same basename as the target object file with a .su extension. Each line of this file is made up of three fields:

* The name of the function.
* A number of bytes.
* One or more qualifiers: static, dynamic, bounded. 

The second field corresponds to the size of the known part of the function frame.

The qualifier static means that the function frame size is purely static. It usually means that all local variables have a static size. In this case, the second field is a reliable measure of the function stack utilization.

The qualifier dynamic means that the function frame size is not static. It happens mainly when some local variables have a dynamic size. When this qualifier appears alone, the second field is not a reliable measure of the function stack analysis. When it is qualified with bounded, it means that the second field is a reliable maximum of the function stack utilization.

Answer 3

I don't see why a static code analysis couldn't give a good enough figure for this.

It's trivial to find all the local variables in any given function, and the size for each variable can be found either through the C standard (for built in types) or by calculating it (for complex types like structs and unions).

Sure, the answer can't be guaranteed to be 100% accurate, since the compiler can do various sorts of optimizations like padding, putting variables in registers or completely remove unnecessary variables. But any answer it gives should be a good estimate at least.

I did a quick google search and found StackAnalyzer but my guess is that other static code analysis tools have similar capabilities.

If you want a 100% accurate figure, then you'd have to look at the output from the compiler or check it during runtime (like Ralph suggested in his reply)

Answer 4

Only the compiler would really know, since it is the guy that puts all your stuff together. You'd have to look at the generated assembly and see how much space is reserved in the preamble, but that doesn't really account for things like alloca which do their thing at runtime.

Answer 5

Assuming you're on an embedded platform, you might find that your toolchain has a go at this. Good commercial embedded compilers (like, for example the Arm/Keil compiler) often produce reports of stack usage.

Of course, interrupts and recursion are usually a bit beyond them, but it gives you a rough idea if someone has committed some terrible screw-up with a multi megabyte buffer on the stack somewhere.

Answer 6

Not exactly "compile time", but I would do this as a post-build step:

• let the linker create a map file for you
• for each function in the map file read the corresponding part of the executable, and analyse the function prologue.

This is similar to what StackAnalyzer does, but a lot simpler. I think analysing the executable or the disassembly is the easiest way you can get to the compiler output. While the compiler knows those things internally, I am afraid you will not be able to get it from it (you might ask the compiler vendor to implement the functionality, or if using open source compiler, you could do it yourself or let someone do it for you).

To implement this you need to:

• be able to parse map file
• understand format of the executable
• know what a function prologue can look like and be able to "decode" it

How easy or difficult this would be depends on your target platform. (Embedded? Which CPU architecture? What compiler?)

All of this definitely can be done in x86/Win32, but if you never did anything like this and have to create all of this from the scratch, it can take a few days before you are done and have something working.

Answer 7

Not in general. The Halting Problem in theoretical computer science suggests that you can't even predict if a general program halts on a given input. Calculating the stack used for a program run in general would be even more complicated. So: no. Maybe in special cases.

Let's say you have a recursive function whose recursion level depends on the input which can be of arbitrary length and you are already out of luck.