When does the stack really overflow?

Question

Is infinite recursion the only case or can it happen for other reasons? Doesn't the stack size grow as needed same as heap?

Sorry if this question has been asked before, would appreciate links to them if that is the case.

Answer 1

I can't speak for all platforms, but as it happens, I've just spent some time working with Windows .exe files (I mean, actually studying the binary format of them - I know in a sense all of us here work with executable files ;) ). I'm betting that most other platforms have similar capabilities, but I'm not immediate familiar with them.

Part of the file format itself includes two values relevant to the current discussion:

typedef struct _IMAGE_OPTIONAL_HEADER {
    ...
    DWORD   SizeOfStackReserve;
    DWORD   SizeOfStackCommit;
    ...
} IMAGE_OPTIONAL_HEADER32, *PIMAGE_OPTIONAL_HEADER32;

From MSDN:

SizeOfStackReserve

The number of bytes to reserve for the stack. Only the memory specified by the SizeOfStackCommit member is committed at load time; the rest is made available one page at a time until this reserve size is reached.

SizeOfStackCommit

The number of bytes to commit for the stack.

In other words, the linker specifies a maximum size for the program's stack. If you hit the maximum size, you overflow - no matter how you hit the maximum size. You could write a simple program to do it in one line of code just by allocating a single stack variable (say, an array) that's bigger than the maximum stack size. Or you could do it via infinite (or finite, but very deep) recursion, or just by allocating too many stack variables.

The Microsoft linker sets this value to 1MB by default on X86 platforms (4MB on Itanium systems). This seems small on the face of it, for a modern system. However, more modern versions of Windows interpret these values slightly differently. Instead of completely limiting the stack, it limits the physical memory the stack will use. If your stack grows beyond this, virtual memory will get involved, so you should still be good... assuming you have enough virtual memory.

Remember, it is possible to run out of memory, even on modern systems with huge amounts of RAM and plenty of virtual memory on disk. You just need to allocate really big amounts of data.

So, long story short: is it possible to overflow the stack without infinite recursion? Definitely. Is it likely? Not really, unless you're allocating really huge objects.

Answer 2

The stack overflows when the stack pointer is pushed out of the memory block the operating system has allocated for the stack. Some operating systems will resize the stack as it grows (IIRC Linux does this) while in others the stack size is fixed at the start of the process or thread (IIRC Windows does this).

Possible reasons for overflowing the stack:

• An unbounded number of stack frames (e.g. from unbounded recursion)
• Attempting to allocate large blocks from the stack
• Buffer overflows for buffers allocated on the stack

There are probably other reasons as well that I can't think of off the top of my head.