Why is there a stack overflow

Question

Under Linux start with

ulimit -s 1024

to limit the stack size.

First of all a program which works:

#include <stdio.h>

static int calc(int c,int *array)
{
    if (array!=NULL) {
        if (c<=0) {
            array[0]=1;
            return 1;
        }
        calc(c-1,array);
        array[c]=array[c-1]+3;
        return array[c];
    } else {
        int a[2500+c];
        calc(c-1,a);
        a[c]=a[c-1]+3;
        return a[c];
    }
}

int main()
{
    int result;
    result = calc(1000,NULL);
    printf("result = %d\n",result);
}

Now if I change int a[2500+c]; to int a[2500]; then the program crashes with a stack overflow (segmentation fault).

I tried this with

• gcc-4.4.7 -O0, gcc-4.4.7 -O2, gcc-4.4.7 -O3
• gcc-4.8.4 -O0, gcc-4.8.4 -O2, gcc-4.8.4 -O3
• gcc-4.9.3 -O0, gcc-4.9.3 -O2, gcc-4.9.3 -O3

If I use

ulimit -s 1024

then the version with int a[2500]; crashes, whereas the version with int a[2500+c]; works.

Why does the version of the program which uses a variable length array (int a[2500+c];) consume less stack space than the version which uses a fixed length array (int a[2500];) ?

Answer 1

As was mentioned in the comments of your previous question, "why" is an implementation detail of the compiler. The standard doesn't dictate how the stack is laid out (or if there even is a stack). As you've seen different versions of the same compiler, or the same version with different optimization settings, can alter how the compiler does things under the hood.

That being said, the compiler probably allocates stack space for all variables that are declared anywhere in the function that are not VLAs when the function is entered. It's probably more efficient in some way that's opaque to the developer. With a VLA, the size isn't known until runtime, so it's allocated differently.

You're better off using malloc in this case instead of using a local array. That will give you more deterministic behavior.

....
} else {
    int *a = malloc(c * sizeof(int));
    if (a == NULL) {
        perror("malloc failed");
        exit(1);
    }
    calc(c-1,a);
    a[c]=a[c-1]+3;
    int rval = a[c];
    free(a);
    return rval;
}