checking for stack overflow in recursive function

[Victor]

Hello,

I've got a situation in which the number of (valid) recursive calls I
make will cause stack overflow. I can use getrlimit (and setrlimit)
to test (and set) my current stack size. However, it is not as
straightforward to determine the base address for my stack space. The
approach I have taken is to save the address of an automatic variable
in main( ), and assume this is a fairly good indicator of my base
address. Then, I can store this in a non-stack variable for use in
the recursive function so that I don't have to keep passing it (and
therefore pushing it on the stack) for each recursive call.

The recursive function can then compare the address of one of its own
automatic variables to the "base" address computed in main( ), and
return with a stack overflow warning, i.e. before the stack is
overflowed. Furthermore, the recursive function can also store the
address of this automatic variable into a static variable to determine
its own stack size requirement on the next recursive call. By
comparison with the corresponding automatic variable in the previous
call, the recursive function can compute the difference.

My question, then is whether there isn't a more straightforward way to
accomplish this goal. I have a couple of issues with my current
methodology.

1) I seem to overflow the stack - that is, the operating system
detects a memory fault and terminates the process - before I've
reached what I believe to be the stack limit. This seems reasonable,
as my guess at the stack base is probably not entirely accurate.
However, I would like to have some accurate way of determining where
my stack limit is. To solve this issue, I simply scaled the available
stack space (what getrlimit reports) by, say 90%.

2) It seems like I'm having to jump through a lot of hoops to guard
against what I consider to be a fairly typical problem. Are there
either system calls that allow me to determine my base address or some
other means to guard against the overflow?

Thanks for your time. I hope that my question is understandable
despite its lack of source code!

Victor Weinstein

 

[Irrwahn Grausewitz]

Hello,

Thanks for your time. I hope that my question is understandable
despite its lack of source code!

It is, but since standard C does not know anything about specific
operating systems, calls to these or stacks or the like, all this is
unfortunately off-topic in c.l.c, sorry.

You'd better ask your question in a NG dedicated to your OS, which you
didn't mention, so I cannot direct you to a specific one.

Try something like comp.<your OS>.programmer.

Thank you.

Regards

Irrwahn
--
do not write: void main(...)
do not use gets()
do not cast the return value of malloc()
do not fflush( stdin )
read the c.l.c-faq: http://www.eskimo.com/~scs/C-faq/top.html

 

[bd]

Hello,

I've got a situation in which the number of (valid) recursive calls I
make will cause stack overflow. I can use getrlimit (and setrlimit)
to test (and set) my current stack size. However, it is not as
straightforward to determine the base address for my stack space. The
approach I have taken is to save the address of an automatic variable
in main( ), and assume this is a fairly good indicator of my base
address. Then, I can store this in a non-stack variable for use in
the recursive function so that I don't have to keep passing it (and
therefore pushing it on the stack) for each recursive call.

getrlimit() and setrlimit() are not defined in the C standard. Actually,
AFAIK a conforming implementation could use CPS or something instead of a
stack, which would render this moot.

[snip]

2) It seems like I'm having to jump through a lot of hoops to guard
against what I consider to be a fairly typical problem. Are there
either system calls that allow me to determine my base address or some
other means to guard against the overflow?

Have you considered an iterative solution? If you're overflowing the stack,
then you may be approaching the problem wrong. In any case, I'm not aware
of a portable way of detecting a stack overflow.

 

[Malcolm]

I've got a situation in which the number of (valid) recursive calls I
make will cause stack overflow.

This is possible, but it is unlikely. Compiler writers generally give a
large enough stack for any normal use. Unless you have a seriously greedy
algorithm, the problem is probably a bug.

I can use getrlimit (and setrlimit) to test (and set) my current stack
size.

The compiler might provide platform-specific functions for manipulating the
stack. However they are off-topic on clc.

However, it is not as straightforward to determine the base
address for my stack space. The approach I have taken is to save the
address of an automatic variable in main( )
My question, then is whether there isn't a more straightforward way to
accomplish this goal. I have a couple of issues with my current
methodology.

There isn't a nice way of doing what you seem to want to do. Taking the
address of a dummy variable is as good a method as any.

2) It seems like I'm having to jump through a lot of hoops to guard
against what I consider to be a fairly typical problem.

Unless you are running on a very unusual platform, running out of stack
space isn't a typical problem.
What you can do is allocate enough space for your algorithm using malloc()
and then rewrite it so that it saves return information in the space you
have allocated. Effectively make it data recursive instead of function
recursive.
However this is only if you have an exceptionally greedy algorithm that you
can't rewrite any other way. Probably you will find that the terminating
condition in your recursive function is miswritten, and this is causing the
stack overflow. Compiler writers generally provide enough stack space for
any normal recursive function.

 

[James Hu]

Hello,

I've got a situation in which the number of (valid) recursive calls I
make will cause stack overflow. [...]

My question, then is whether there isn't a more straightforward way to
accomplish this goal. [...]

First, see if you can find another algorithm for your function that
does not depend on the per invocation state. If you can do this, then
you have removed the memory consumption problem of your recursive
function.

If it is not possible to remove that requirement, the next best
alternative is to re-write your function to remove the recursive
calls and manage the per invocation state explicitly. This will
give you precise control over the memory used by your function.

As an example, consider the following textbook illustration of a bad
recursive implementation of a function to find the n-th Fibonacci
number:


unsigned fib(unsigned n)
{
if (n < 2) return n;
return fib(n-1) + fib(n-2);
}


This function can be rewritten as (remember that we are staying
true to the per invocation state of the original recursive
implementation):


#define N 1024
#define fibpush(x) (fibstack[fibcount++] = x)
#define fibpop() (fibstack[--fibcount])
#define fibtop() (fibstack[fibcount-1])

unsigned fib(unsigned n)
{
enum state { BEG, FIB, SUM, END, FIN } state = BEG;
enum point { INIT, FIB1, FIB2, FINI };
struct fibstate { enum point point; unsigned value; } s, t;
struct fibstate fibstack[N];
unsigned fibcount = 0;

t.point = INIT;
t.value = n;
fibpush(t);

while (state != FIN)
switch(state) {
case BEG: if (fibtop().value < 2) {
state = END; break;
}
t.point = FIB1;
t.value = fibtop().value - 1;
fibpush(t);
state = BEG; break;

case FIB: t = fibpop();
s = fibtop();
s.point = FIB2;
s.value = fibtop().value - 2;
t.point = FINI;
fibpush(t);
fibpush(s);
state = BEG; break;

case SUM: t = fibpop();
s = fibpop();
fibtop().value = s.value + t.value;
state = END; break;

case END: switch (fibtop().point) {
case INIT: state = FIN; break;
case FIB1: state = FIB; break;
case FIB2: state = SUM; break;
case FINI: break;
}

case FIN: break;
}

t = fibpop();
return t.value;
}


In practice, you would check for stack overflow and underflow
in the push and pop operations.

This is just an example. There are, of course, far better ways
to write a function that finds the n-th Fibonacci number
recursively. One improved implementation is:


static unsigned fib_r(unsigned a, unsigned b, unsigned n)
{
if (n < 2) return b;
return fib_r(b, a+b, n-1);
}

unsigned fib(unsigned n)
{
if (n < 2) return n;
return fib_r(0, 1, n);
}


When translated into the equivalent non-recursive version, the
above implementation becomes:


static unsigned fib_r(unsigned a, unsigned b, unsigned n)
{
for (; {
if (n < 2) return b;
#ifdef TRICKY
b = a+b;
a = b-a;
#else
{
int t = a;
a = b;
b += t;
}
#endif
--n;
}
}

unsigned fib(unsigned n)
{
if (n < 2) return n;
return fib_r(0, 1, n);
}


-- James