Catching stack overflow

Question

What's the best way to catch stack overflow in C?

More specifically:

A C program contains an interpreter for a scripting language.

Scripts are not trusted, and may contain infinite recursion bugs. The interpreter has to be able to catch these and smoothly continue. (Obviously this can partly be handled by using a software stack, but performance is greatly improved if substantial chunks of library code can be written in C; at a minimum, this entails C functions running over recursive data structures created by scripts.)

The preferred form of catching a stack overflow would involve longjmp back to the main loop. (It's perfectly okay to discard all data that was held in stack frames below the main loop.)

The fallback portable solution is to use addresses of local variables to monitor the current stack depth, and for every recursive function to contain a call to a stack checking function that uses this method. Of course, this incurs some runtime overhead in the normal case; it also means if I forget to put the stack check call in one place, the interpreter will have a latent bug.

Is there a better way of doing it? Specifically, I'm not expecting a better portable solution, but if I had a system specific solution for Linux and another one for Windows, that would be okay.

I've seen references to something called structured exception handling on Windows, though the references I've seen have been about translating this into the C++ exception handling mechanism; can it be accessed from C, and if so is it useful for this scenario?

I understand Linux lets you catch a segmentation fault signal; is it possible to reliably turn this into a longjmp back to your main loop?

Java seems to support catching stack overflow exceptions on all platforms; how does it implement this?

Answer 1

Off the top of my head, one way to catch excessive stack growth is to check the relative difference in addresses of stack frames:

#define MAX_ROOM    (64*1024*1024UL)    // 64 MB

static char *   first_stack = NULL;

void foo(...args...)
{
    char    stack;

    // Compare addresses of stack frames
    if (first_stack == NULL)
        first_stack = &stack;
    if (first_stack > &stack  &&  first_stack - &stack > MAX_ROOM  ||
        &stack > first_stack  &&  &stack - first_stack > MAX_ROOM)
        printf("Stack is larger than %lu\n", (unsigned long)MAX_ROOM);

    ...code that recursively calls foo()...
}

This compares the address of the first stack frame for foo() to the current stack frame address, and if the difference exceeds MAX_ROOM it writes a message.

This assumes that you're on an architecture that uses a linear always-grows-down or always-grows-up stack, of course.

You don't have to do this check in every function, but often enough that excessively large stack growth is caught before you hit the limit you've chosen.

Answer 2

AFAIK, all mechanisms for detecting stack overflow will incur some runtime cost. You could let the CPU detect seg-faults, but that's already too late; you've probably already scribbled all over something important.

You say that you want your interpreter to call precompiled library code as much as possible. That's fine, but to maintain the notion of a sandbox, your interpreter engine should always be responsible for e.g. stack transitions and memory allocation (from the interpreted language's point of view); your library routines should probably be implemented as callbacks. The reason being that you need to be handling this sort of thing at a single point, for reasons that you've already pointed out (latent bugs).

Things like Java deal with this by generating machine code, so it's simply a case of generating code to check this at every stack transition.