Re: Stack size calculation - tool support?

On Nov 16, 6:23 pm, Tim Wescott <t...@xxxxxxxxxxxxxxxx> wrote:
On Mon, 16 Nov 2009 16:37:47 -0600, Vladimir Vassilevsky wrote:
Gerd wrote:

I need to allocate the stack for my system with a proper size. I don't
want do a vage estimation, so I would like to know: Is there a tool
that scans C source code, and calculates the required tack size, based
on the call graph? Only plain C, no recursion.

It is impossible to estimate stack depth from the source code only.

Proof?  Reference to proof?

Absent recursion this should be a pretty direct calculation, if
exceedingly tedious.  With recursion the answer is easy: "go back to
school where you belong, buddy".

Granted, an RTOS makes life difficult, but even there the stack usage of
any one task should be as easy (or impossible) to calculate as for a
traditional single thread of execution.


Assuming no function pointers, you can compute a maximum based on the
call tree simply enough, but that may be a substantial overestimate
based on what sequences of calls are actually possible. Consider:


void a() {... c(0); ...}

void b() {... c(1); ...}

void c(int p)
{
....
if (p)
d();
else
e();
....
}

void d() {...}

void e() {...}


Assume that a() and d() have large stack allocations, the
straightforward analysis will determine that a()->c()->d() results in
the worst case stack usage, when that's not actually possible because
of the control coupled call to d() or e() from c().

Also, function pointers make the analysis much harder. Even if you
assume that no recursion will occur, the straight-forward approach
requires you to assume that you can call *any* routine that has its
address taken from *any* use of a function pointer to execute a call,
which will again likely result in a substantial overestimate.

Of course having a maximum is often a nice place to start.
.

Relevant Pages

  • Re: easy pointers to functions problem
    ... I am trying to get an idea of how function pointers work. ... I.e. you cannot pass a function pointer as a void* parameter. ... int main{ ... It is this that is correct, so change your earlier prototype to match. ...
    (comp.lang.c)
  • Re: help needed with K&R code on p. 87
    ... >void printd ... The code is typical terse ... The output I get is 123, but I am not really sure how the recursion ... novice programmer rather than the newcomer to C. ...
    (alt.comp.lang.learn.c-cpp)
  • Re: help in quicksort
    ... how many recursive calls will quicksort make in the worst case ... While I see how you can limit the worst case _depth_ of recursion to ... void q0sort(void *base, size_t nmemb, size_t size, ...
    (comp.lang.c)
  • Re: Global restricted function pointer
    ... But is that defined in C89? ... could safely convert function pointers from one function pointer to ... pointer to void * and back. ... typedef void; ...
    (comp.lang.c)
  • Re: Richard heathfields casting operation
    ... function pointers to void pointers will break. ... void* and function pointers are both 8 bytes on Linux/IA-64. ... printf = 0x2000000000039608 ... Looking for software development work in the San Diego area. ...
    (comp.lang.c)