Is it possible to predict a stack overflow in C on Linux?

Question

There are certain conditions that can cause stack overflows on an x86 Linux system:

• struct my_big_object[HUGE_NUMBER] on the stack. Walking through it eventually causes SIGSEGV.
• The alloca() routine (like malloc(), but uses the stack, automatically frees itself, and also blows up with SIGSEGV if it's too big). Update: alloca() isn't formally deprecated as I originally stated; it is merely discouraged.

Is there a way to programmatically detect if the local stack is big enough for a given object? I know the stack size is adjustable via ulimit, so I have hope there is a way (however non-portable it may be). Ideally, I would like to be able to do something like this:

int min_stack_space_available = /* ??? */;
if (object_size < min_stack_space_available)
{
    char *foo = alloca(object_size);
    do_stuff(foo);
}
else
{
    char *foo = malloc(object_size);
    do_stuff(foo);
    free(foo);
}

Answer 1

You can determine the stack space the process has available by finding the size of a process' stack space and then subtracting the amount used.

ulimit -s

shows the stack size on a linux system. For a programmatic approach, check out getrlimit(). Then, to determine the current stack depth, subtract a pointer to the top of the stack from one to the bottom. For example (code untested):

unsigned char *bottom_of_stack_ptr;

void call_function(int argc, char *argv) {
    unsigned char top_of_stack;
    unsigned int depth = (&top_of_stack > bottom_of_stack_ptr) ? 
        &top_of_stack-bottom_of_stack_ptr : 
        bottom_of_stack_ptr-&top_of_stack;

    if( depth+100 < PROGRAMMATICALLY_DETERMINED_STACK_SIZE ) {
        ...
    }
}

int main(int argc, char *argv) {
    unsigned char bottom_of_stack;
    bottom_of_stack_ptr = &bottom_of_stack;
    my_function();
    return 0;
}

Answer 2

The deprecated alloca() routine (like malloc(), but uses the stack, automatically frees itself, and also blows up with SIGSEGV if it's too big).

Why is alloca deprecated?

Anyhow, how much faster in your case is alloca vs malloc? (Is it worth it?)

And don't you get null back from alloca if there is not enought space left? (the same way as malloc?)

And when your code crash, where does it crash? is it in alloca or is in doStuff()?

/Johan

Answer 3

Not sure if this applies on Linux, but on Windows it's possible to run into access violations with large stack allocations even if they succeed!

This is because by default, Windows' VMM only actually marks the top few (not sure how many exactly) 4096-byte pages of stack RAM as pageable (i.e. backed by the pagefile), since it believes that stack accesses will generally march downwards from the top; as accesses get closer and closer to the current "boundary", lower and lower pages are marked as pageable. But this means that an early memory read/write far below the top of the stack will trigger an access violation as that memory is not actually allocated yet!

Answer 4

alloca() is going to return NULL on failure, I believe the behavior of alloca(0) is undefined and platform variant. If you check for that prior to do_something(), you should never be hit with a SEGV.

I have a couple of questions:

1. Why, oh why, do you need something that big on the stack? The default size on most systems is 8M, that's still too small?
2. If the function calling alloca() blocks, would protecting the same amount of heap via mlock() / mlockall() guarantee close to the same access performance (i.e. "Don't swap me, bro!") over time? If your using a more aggressive 'rt' scheduler, its recommended to call those anyway.

The question is interesting but raises an eyebrow. It raises the needle on my square-peg-round-hole-o-meter.

Answer 5

You don't say much about why you want to allocate on the stack, but if it is the stack memory model which is appealing, you could implement stack allocation on the heap as well. Allocate a large chunk of memory at the beginning of the program and keep a stack of pointers to this which would correspond to frames on the regular stack. You just need to remember to pop your private stack pointer when the function returns.

Answer 6

Several compilers, for example Open Watcom C/C++, support stackavail() function that lets you do exactly that

Answer 7

You can use GNU libsigsegv to handle a page fault, including cases where a stack overflow occurs (from its website):

In some applications, the stack overflow handler performs some cleanup or notifies the user and then immediately terminates the application. In other applications, the stack overflow handler longjmps back to a central point in the application. This library supports both uses. In the second case, the handler must ensure to restore the normal signal mask (because many signals are blocked while the handler is executed), and must also call sigsegv_leave_handler() to transfer control; then only it can longjmp away.

Answer 8

The alloca function is not deprecated. However, it is not in POSIX and it is also machine- and compiler-dependent. The Linux man-page for alloca notes that "for certain applications, its use can improve efficiency compared to the use of malloc, and in certain cases it can also simplify memory deallocation in applications that use longjmp() or siglongjmp(). Otherwise, its use is discouraged."

The manpage also says that "there is no error indication if the stack frame cannot be extended. However, after a failed allocation, the program is likely to receive a SIGSEGV."

The performance of malloc was actually mentioned on the Stackoverflow Podcast #36.

(I know this is not a proper answer to your question, but I thought it might be useful anyway.)

Answer 9

Even if this isn't a direct answer to your question, I hope you're aware of the existence of valgrind - a wonderful tool for detecting such problems in runtime, on Linux.

Regarding the stack problem, you can attempt allocating objects dynamically from a fixed pool that detects these overflows. With a simple macro-wizardry you can make this run at debug time, with real code running at release time, and thus know (at least for the scenarios you're executing) that you're not taking too much. Here's more info and a link to a sample implementation.

Answer 10

There isn't a nice way I can think of. Maybe it is possible by using getrlimit() (suggested before) and some pointer arithmetic? But first ask yourself if you really want this.

void *closeToBase;

main () {
  int closeToBase;
  stackTop = &closeToBase;
}

int stackHasRoomFor(int bytes) {
  int currentTop;
  return getrlimit(...) - (¤tTop  - closeToBase) > bytes + SomeExtra;
}

Personally, I'd not do this. Allocate big things on the heap, the stack was not meant for it.

Answer 11

The end of the stack area is determined dynamically by the OS. Although you can find the "static" bounds of the stack by looking at the virtual memory areas (VMAs) in a highly OS dependent way (see the stackvma* files in libsigsegv/src/), you will additionally have to consider

• the getrlimit values,
• the per-thread stack size (see pthread_getstacksize)

Answer 12

Apologies if this is stating the obvious, but you could easily write a function to test for a specific stack allocation size by just trying the alloca (of that size) and catching a stack overflow exception. If you wanted you could put it into a function, with some pre-determined math for the function stack overhead. Eg:

bool CanFitOnStack( size_t num_bytes )
{
    int stack_offset_for_function = 4; // <- Determine this
    try
    {
        alloca( num_bytes - stack_offset_for_function );
    }
    catch ( ... )
    {
        return false;
    }

    return true;
}