Detecting stack overflows during runtime beforehand

Question

I have a rather huge recursive function (also, I write in C), and while I have no doubt that the scenario where stack overflow happens is extremely unlikely, it is still possible. What I wonder is whether you can detect if stack is going to get overflown within a few iterations, so you can do an emergency stop without crashing the program.

Answer 1

In the C programming language itself, that is not possible. In general, you can't know easily that you ran out of stack before running out. I recommend you to instead place a configurable hard limit on the recursion depth in your implementation, so you can simply abort when the depth is exceeded. You could also rewrite your algorithm to use an auxillary data structure instead of using the stack through recursion, this gives you greater flexibility to detect an out-of-memory condition; malloc() tells you when it fails.

However, you can get something similar with a procedure like this on UNIX-like systems:

1. Use setrlimit to set a soft stack limit lower than the hard stack limit
2. Establish signal handlers for both SIGSEGV and SIGBUS to get notified of stack overflows. Some operating systems produce SIGSEGV for these, others SIGBUS.
3. If you get such a signal and determine that it comes from a stack overflow, raise the soft stack limit with setrlimit and set a global variable to identify that this occured. Make the variable volatile so the optimizer doesn't foil your plains.
4. In your code, at each recursion step, check if this variable is set. If it is, abort.

This may not work everywhere and required platform specific code to find out that the signal came from a stack overflow. Not all systems (notably, early 68000 systems) can continue normal processing after getting a SIGSEGV or SIGBUS.

A similar approach was used by the Bourne shell for memory allocation.

Answer 2

Heres a simple solution that works for win-32. Actually resembles what Wossname already posted but less icky :)

unsigned int get_stack_address( void )
{
    unsigned int r = 0;
    __asm mov dword ptr [r], esp;
    return r;
}
void rec( int x, const unsigned int begin_address )
{
    // here just put 100 000 bytes of memory
    if ( begin_address - get_stack_address() > 100000 )
    {
        //std::cout << "Recursion level " << x << " stack too high" << std::endl;
        return;
    }
    rec( x + 1, begin_address );
}
int main( void )
{
    int x = 0;
    rec(x,get_stack_address());
}

Answer 3

Here's a naive method, but it's a bit icky...

When you enter the function for the first time you could store the address of one of your variables declared in that function. Store that value outside your function (e.g. in a global). In subsequent calls compare the current address of that variable with the cached copy. The deeper you recurse the further apart these two values will be.

This will most likely cause compiler warnings (storing addresses of temporary variables) but it does have the benefit of giving you a fairly accurate way of knowing exactly how much stack you're using.

Can't say I really recommend this but it would work.

#include <stdio.h>

char* start = NULL;

void recurse()
{
  char marker = '@';

  if(start == NULL)
    start = &marker;

  printf("depth: %d\n", abs(&marker - start));

  if(abs(&marker - start) < 1000)
    recurse();
  else
    start = NULL;
}

int main()
{
  recurse();

  return 0;
}

Answer 4

An alternative method is to learn the stack limit at the start of the program, and each time in your recursive function to check whether this limit has been approached (within some safety margin, say 64 kb). If so, abort; if not, continue.

The stack limit on POSIX systems can be learned by using getrlimit system call.

Example code that is thread-safe: (note: it code assumes that stack grows backwards, as on x86!)

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

void *stack_limit;
#define SAFETY_MARGIN (64 * 1024) // 64 kb

void recurse(int level)
{
    void *stack_top = &stack_top;
    if (stack_top <= stack_limit) {
        printf("stack limit reached at recursion level %d\n", level);
        return;
    }
    recurse(level + 1);
}

int get_max_stack_size(void)
{
   struct rlimit rl;
   int ret = getrlimit(RLIMIT_STACK, &rl);
   if (ret != 0) {
       return 1024 * 1024 * 8; // 8 MB is the default on many platforms
   }
   printf("max stack size: %d\n", (int)rl.rlim_cur);
   return rl.rlim_cur;
}

int main (int argc, char *argv[])
{
    int x;
    stack_limit = (char *)&x - get_max_stack_size() + SAFETY_MARGIN;
    recurse(0);
    return 0;
}

Output:

max stack size: 8388608
stack limit reached at recursion level 174549