Avoiding recursive stack overflow in C on Unix/Linux?

[boltar2003]

Hello

If a program recurses too deeply there's always a chance that it could
run out of stack space and die with a SIGSEGV. Is there any API that can
tell you how much stack space is left or some other method to prevent this
in C/C++? I realise I could catch the signal but thats a pretty damn ugly
way to do it.

B2003

 

[boltar2003]

On some systems there is setrlimit which can be used to set the stack size. On
unix you can start with 'man -k limit' and examine individual man pages.

Actually I suppose i could use getrlimit to get the stack size but is there
a clean way of actually finding the current position of top of the stack? I
could take the addresses of local variables but that seems a bit prone to
error.

B2003

 

[Xavier Roche]

If a program recurses too deeply there's always a chance that it could
run out of stack space and die with a SIGSEGV. Is there any API that can
tell you how much stack space is left or some other method to prevent this
in C/C++? I realise I could catch the signal but thats a pretty damn ugly
way to do it.

There is no portable way to find the stack bottom/size ; I am not even
sure what getrlimit(RLIMIT_STACK) returns exactly (current thread stack
size ? main thread stack size ? default stack size ?)

(And there is no portable way to find the stack top/bottom -- you'll
have to play with an address on the current stack around main, and play
with arithmetics with the page size)

 

[Kleuskes & Moos]

Hello

If a program recurses too deeply there's always a chance that it could
run out of stack space and die with a SIGSEGV. Is there any API that can
tell you how much stack space is left or some other method to prevent this
in C/C++? I realise I could catch the signal but thats a pretty damn ugly
way to do it.

B2003

The only proper way to avoid stack-overflows is to prevent it from
happening in the first place. If at all possible (and frequently it
is) avoid recursion, if it's unavoidable, as it sometimes is, make
sure your design prevents those situations from arising in the first
place.

Trying to solve a design problem by imposing artificial limitations
seems a bad idea.

 

[Ben Bacarisse]

The only proper way to avoid stack-overflows is to prevent it from
happening in the first place. If at all possible (and frequently it
is) avoid recursion, if it's unavoidable, as it sometimes is, make
sure your design prevents those situations from arising in the first
place.

I find this answer interesting, mainly because I think is suggests a
very different view about programming. I would not try to avoid
recursion "if at all possible". In general I consider that it is up to
the system to provide the resources needed by a program and this
includes stack for a reasonable amount of recursion. These resources
can run out of course, and the stack is special in that few languages
provide any way to handle its exhaustion elegantly, but that does not
seem enough reason to design out all recursion.

There are special cases: some environments are severely resource limited
but there's no indication that the OP is using such a system and,
anyway, I don't think you can make general rules from specific situations.

Trying to solve a design problem by imposing artificial limitations
seems a bad idea.

Isn't this what you are doing? Isn't the ban on recursion not an
artificial limitation?

 

[James Kuyper]

The only proper way to avoid stack-overflows is to prevent it from
happening in the first place.

And how do you do that? If the stack size is sufficiently limited, even

int main(int argc, char*argv[]) { return 0; }

could overflow the stack.
You can take measures to reduce the likelihood of overflow, but there's
no easy way to know whether you've done enough. And doing enough on one
system might be a complete waste of time on others. The systems I use
most frequently allow me to put a gigabyte or more of data on the stack;
other systems are far more limited.

....

Trying to solve a design problem by imposing artificial limitations
seems a bad idea.

So what's the design solution you propose to "prevent overflow"?

 

[Ben Bacarisse]

The only proper way to avoid stack-overflows is to prevent it from
happening in the first place.

And how do you do that? If the stack size is sufficiently limited, even

int main(int argc, char*argv[]) { return 0; }

could overflow the stack.

Hmm... only in the most contrived implementation. The standard mandates
that an implementation must be able to translate and run at least one
program that is very much more complex than this. The system would have
to penalise simple, small programs deliberately!

It's a detail. I agree with your point that almost any call can be the
one that causes a stack overflow. Recursion need not be to blame.

<snip>

 

[Nobody]

There is no portable way to find the stack bottom/size ; I am not even
sure what getrlimit(RLIMIT_STACK) returns exactly (current thread stack
size ? main thread stack size ? default stack size ?)

It's the size of the region of address space allocated to the main
thread's stack.

(And there is no portable way to find the stack top/bottom -- you'll
have to play with an address on the current stack around main, and play
with arithmetics with the page size)

If available, the value returned by alloca() will typically be the exact
bottom of the stack.

alloca() doesn't conform to any standard, but it's a common extension.

 

[robertwessel2]

It's the size of the region of address space allocated to the main
thread's stack.


If available, the value returned by alloca() will typically be the exact
bottom of the stack.

alloca() doesn't conform to any standard, but it's a common extension.

The more conventional terminology would have alloca() returning
something near the *top* of the stack - and the direction of stack
growth is irrelevant. But so will taking the address of an automatic,
which is much simpler. The approximate bottom of the stack could be
stored at entry to main().

 

[boltar2003]

The only proper way to avoid stack-overflows is to prevent it from
happening in the first place. If at all possible (and frequently it
is) avoid recursion, if it's unavoidable, as it sometimes is, make
sure your design prevents those situations from arising in the first
place.

Well its always theoretically possible to re-write recursive code in an
iterative format but generally it leads to any reasonably complex recursive
code becoming an unreadable mess.

B2003

 

[Måns Rullgård]

The only proper way to avoid stack-overflows is to prevent it from
happening in the first place.

And how do you do that? If the stack size is sufficiently limited, even

int main(int argc, char*argv[]) { return 0; }

could overflow the stack.
You can take measures to reduce the likelihood of overflow, but there's
no easy way to know whether you've done enough. And doing enough on one
system might be a complete waste of time on others. The systems I use
most frequently allow me to put a gigabyte or more of data on the stack;
other systems are far more limited.

Recursion or not isn't really important. What matters is having a
static bound on the amount of stack space required. Any design with
potentially unbounded stack usage (determined by runtime input) is
flawed since there is no way to reliably detect and recover from a stack
overflow.

 

[Kleuskes & Moos]

Without in any way disagreeing, I can't imagine being able to come up
with a contextual definition for "artificial" in that sentence.

Not inherent to the problem being solved or not part of the original,
abstract, algorithm being implemented. But you're right, "artificial"
is a weird word to use in the programming context.

 

[boltar2003]

The more conventional terminology would have alloca() returning
something near the *top* of the stack - and the direction of stack
growth is irrelevant. But so will taking the address of an automatic,
which is much simpler. The approximate bottom of the stack could be
stored at entry to main().

I'd not heard of that function before. Calling it with zero - alloca(0) -
seems to work and return an address but the man page doesn't hint at
whether this should work or work in the future. Would it be best to call it
with a non zero value just in case the implementation changes?

B2003

 

[Kleuskes & Moos]

I find this answer interesting, mainly because I think is suggests a
very different view about programming.  I would not try to avoid
recursion "if at all possible".  In general I consider that it is up to
the system to provide the resources needed by a program and this
includes stack for a reasonable amount of recursion.  These resources
can run out of course, and the stack is special in that few languages
provide any way to handle its exhaustion elegantly, but that does not
seem enough reason to design out all recursion.

If you compare recursive to equivalent non-recursive algorithms, i
think you will find recursion is usually slower and demands (much)
more resources. So as a rule of thumb, don't recurse, unless you have
to.

And yes, i do have a background in embedded systems, where these
considerations are more important than on modern PC's.

There are special cases: some environments are severely resource limited
but there's no indication that the OP is using such a system and,
anyway, I don't think you can make general rules from specific situations..

well... It's bread and butter for the science guys and the practice is
called "inference". Nevertheless, it's easy to show that recursive
algorithms are outperformed my equivalent non-recursive ones.

The saving grace of recursion is that recursive implementations are
usually easier to understand. If it weren't for that, i'd ban the
practice outright.

Isn't this what you are doing?  Isn't the ban on recursion not an
artificial limitation?

Nope. It follows from the design of processors and a wish to avoid
unneccesary overhead (passing arguments, stack-frame maintenance,
pushing and popping return adresses) and that's without even
considering any effect a call may have on things like branch-
prediction, instruction pipe-lines and such. A 'call' instruction is
(relative to a branch) quite expensive and prevents some optimisations
like loop-unrolling.

So no, that's not an artificial limitation, but a design
consideration.

 

[Kleuskes & Moos]

The restrictions on stack depth are no different than the restrictions
on memory size or disk space that are present on any computer system.

These limits have been relaxed over time, and certainly programs will
run today on a typical computer that would not have run 10 years ago
on a typical computer.

"Don't use recursion" seems to be logically the same as "don't declare
very large arrays" or "don't create really big files".  It is
dependent on the technology of the day, rather than being an absolute
standard.

These days I have a few files on my server that are on the order of
20G.  That would have been unthinkable 10 years ago.

Ah yes... Computers today are so fast and so big that sound design is
superfluous. Unless of course you are dealing with huge amounts of
data, since not only have memory sizes and processor speeds increased,
the amount of data they are supposed to work on have also increased
dramatically, thus cancelling out said improvements in size and speed.

If you don't believe me, try importing planet.osm (see
http://wiki.openstreetmap.org/wiki/Planet.osm)

25 years ago i never imagined i would fill a 54 Gb partition (20 Mb
was a pretty big HD those days), now i'm using a 1Tb drive and looking
at options for an 10 Tb Raid-server.

 

[robertwessel2]

I'd not heard of that function before. Calling it with zero - alloca(0) -
seems to work and return an address but the man page doesn't hint at
whether this should work or work in the future. Would it be best to call it
with a non zero value just in case the implementation changes?

While still non-portable, just write a function like:

char *getappxroximatestackpointer()
{
char c;
return &c;
}


Call it once at the beginning of main(), and save that value. Call it
again when you're interested, subtract the two (watch the order of the
subtraction based on the direction of stack growth - or do an abs() ),
and you'll have a pretty close measurement of the amount of stack
space you're current using on many implementations.

As I said, non-portable (not least, the stack doesn't have to be
contiguous storage), but it will work on many implementations.

 

[boltar2003]

I implemented a simple program that would check when it was getting near
the limit of the stack but for some reason Linux sends it SEGV when
(assuming my program is correct) there should be 10 or 20K of space left
on the stack. Is this normal? I include the code below for someone to point
out the stupid mistake I must have made somewhere. I changed all void * to
char * just in case that was throwing the maths but it made no difference:

#include <stdio.h>
#include <stdlib.h>
#include <alloca.h>
#include <sys/time.h>
#include <sys/resource.h>

char *stack_top;
unsigned int depth;

void recurse()
{
unsigned long int dist;

++depth;
dist = labs((long int)(stack_top - (char *)&dist));
if (dist < 20000)
{
printf("Nearing limit: depth = %u, addr = %lu, dist to end = %lu
\n",
depth,&dist,dist);
}
recurse();
}


int main()
{
struct rlimit rl;
long int mult;
char *top;

depth = 0;

/* Find out which way stack is growing */
top = (char *)alloca(0);
stack_top = (char *)alloca(1);

if (stack_top < top)
{
puts("Stack grows downwards");
mult = -1;
}
else
{
puts("Stack grows upwards");
mult = 1;
}

/* Now find where max extent of the stack by getting its max size */
if (getrlimit(RLIMIT_STACK,&rl) == -1)
{
perror("getrlimit()");
return 1;
}
stack_top += (rl.rlim_cur * mult);
printf("Stack max size = %lu\n",rl.rlim_cur);
printf("Stack max extent = %lu\n",stack_top);
getchar();

recurse();
return 0;
}


B2003

 

[Kleuskes & Moos]

The only proper way to avoid stack-overflows is to prevent it from
happening in the first place.

And how do you do that? If the stack size is sufficiently limited, even

        int main(int argc, char*argv[]) { return 0; }

could overflow the stack.

That would be _very_ bad design, omitting to consider the basic
processing needs of the system.

You can take measures to reduce the likelihood of overflow, but there's
no easy way to know whether you've done enough.

Nope, there isn't. But then again, there's no easy way to produce any
software. Designing software _is_ hard and it will remain hard. Anyone
offering an "easy" solution to this kind of considerartions is either
a fool or a fraud.

And doing enough on one
system might be a complete waste of time on others.

True. But then again, considering the platform(s) your software will
run on is an integral part of the design process.

The systems I use
most frequently allow me to put a gigabyte or more of data on the stack;
other systems are far more limited.

Nice. So what?

So what's the design solution you propose to "prevent overflow"?

Avoid recursion if at all possible, for instance by using things like
finite state machines for parsing data. Recursion is quite costly. I'm
surprised i have to explain this in this forum.

And no, it's not _always_ possible to avoid recursion, not is it
_always_ wise to do so, but as a rule of thumb, it's good.

 

[Kleuskes & Moos]

Well its always theoretically possible to re-write recursive code in an
iterative format but generally it leads to any reasonably complex recursive
code becoming an unreadable mess.

Bravo! That's he first sensible objection I've read in this thread,
and you're right. Recursive algorithms are usually easier to grasp.

 

[Richard Kettlewell]

I implemented a simple program that would check when it was getting near
the limit of the stack but for some reason Linux sends it SEGV when
(assuming my program is correct) there should be 10 or 20K of space left
on the stack. Is this normal? I include the code below for someone to point
out the stupid mistake I must have made somewhere. I changed all void * to
char * just in case that was throwing the maths but it made no difference:

You're not taking into account the stack space above the call to main(),
which will include some amount of space used by Libc plus the command
line and environment.