Understanding memory allocation, test program crashing

Question

I am just about finished reading K&R, and that is all the C that I know. All my compilation is done from Windows command line using MinGW, and I have no knowledge of advanced debugging methods (hence the "ghetto debug" comment in my 2nd program below).

I am trying to make a few small test programs to help me better understand how memory allocation works. These first couple programs do not use malloc or free, I just wanted to see how memory is allocated and de-allocated for standard arrays local to a function. The idea is that I watch my running processes RAM usage to see if it corresponds with what I understand. For this first program below, it does work as I expected. The alloc_one_meg() function allocates and initializes 250,000 4-byte integers, but that MB is de-allocated as soon as the function returns. So if I call that function 1000000 times in a row, I should never see my RAM usage go much above 1MB. And, it works.

#include <stdio.h>
#include <stdlib.h>

void alloc_one_meg() {
    int megabyte[250000];
    int i;
    for (i=0; i<250000; i++) {
        megabyte[i] = rand();
    }
}

main()
{
    int i;
    for (i=0; i<1000000; i++) {
        alloc_one_meg();
    }
}

For this second program below, the idea was to not allow the function to exit, to have 1000 copies of the same function running at once, which I accomplished with recursion. My theory was that the program would consume 1GB of RAM before it de-allocated it all after the recursion finished. However, it doesn't get past the 2nd loop through the recursion (see my ghetto debug comment). The program crashes with a pretty non-informative (to me) message (a Windows pop-up saying ____.exe has encountered a problem). Usually I can always get to the bottom of things with my ghetto debug method... but it's not working here. I'm stumped. What is the problem with this code? Thanks!

#include <stdio.h>
#include <stdlib.h>

int j=0;

void alloc_one_meg() {
    int megabyte[250000];
    int i;
    for (i=0; i<250000; i++) {
        megabyte[i] = rand();
    }
    j++;
    printf("Loop %d\n", j); // ghetto debug
    if (j<1000) {
        alloc_one_meg();
    }
}

main()
{
    alloc_one_meg();
}

Followup question posted here.

Answer 1

You're running into a stack overflow.

Local automatic storage variables (such as megabyte) are allocated on the stack, which has limited amount of space. malloc allocates on the heap, which allows much larger allocations.

You can read more here:

http://en.wikipedia.org/wiki/Stack_overflow

(I should note that the C language does not specify where memory is allocated - stack and heap are implementation details)

Answer 2

The size of the stack in a Windows program is usually around 1 MB, so on the second recursion, you're overflowing the stack. You shouldn't be allocating such large arrays on the stack, use malloc and free to allocate and deallocate the memory on the heap (there's no way to get around malloc for such sizes of arrays):

void alloc_one_meg() {
    int *megabyte = malloc(sizeof(int) * 250000); // allocate space for 250000
                                                  // ints on the heap
    int i;
    for (i=0; i<250000; i++) {
        megabyte[i] = rand();
    }
    j++;
    printf("Loop %d\n", j); // ghetto debug
    if (j<1000) {
        alloc_one_meg();
    }

    free(megabyte); // DO NOT FORGET THIS
}

That said, you can actually change the stack size of a program and make it bigger (though I'd only do so as an educational exercise, not in production code). For Visual Studio you can use the /F compiler option, and on linux you can use setrlimit(3). I'm not sure what to use with MinGW though.

Answer 3

The memory you are allocating via the recursive functional calls is allocated from the stack. All of the stack memory must be contiguous. When your process starts a thread, Windows will reserve a range of virtual memory address space for that thread's stack. The amount of memory to be reserved is specified in your EXE file's "PE header." PE stands for "Portable Executable."

Using the dumpbin utility included with Visual Studio, with itself (dumpbin.exe) as the input file:

dumpbin /headers dumpbin.exe

... there is some output, and then:

      100000 size of stack reserve
        2000 size of stack commit

The "100000" is a hexadecimal number equal to 1,048,576, so this represents around 1MB.

In other words, the operating system will only reserve a 1MB address range for the stack. When that address range is used up, Windows may or may not be able to allocate further consecutive memory ranges to increase the stack. The result depends on whether further contiguous address range is available. It is very unlikely to be available, due to the other allocations Windows made when the thread began.

To allocate a maximum amount of virtual memory under Windows, use the VirtualAlloc family of functions.

Answer 4

StackOverflow. Is this a trick question?