What Happens When Stack and Heap Collide

Question

I am curious to know what happens when the stack and the heap collide. If anybody has encountered this, please could they explain the scenario.

Redmon

I'm pretty sure it happens when you can't stop the hurt inside – Hamon

Well if your out of Stack memory and out of Heap memory a OutOfMemoryException could be thrown? – Achlorhydria

I disagree with the close votes (NaRQ). The situation described is real, is important in small systems even today, is bad, and is worth understanding. – Hyperphagia

There should be no close votes here. This is like the "Emperor's New Clothes" in reverse. People are closing because they don't understand the question, not because it's not a good question. – Spinose

@JohnSaunders if people don't understand the question, then it's not as good as it could be. Perhaps it could be improved... – Sayres

@NormanRamsey: go for it. – Spinose

Answer 1

In a modern languages running on a modern OS, you'll get either a stack overflow (hurray!) or malloc() or sbrk() or mmap() will fail when you try to grow the heap. But not all software is modern, so let's look at the failure modes:

• If the stack grows into the heap, the typically C compiler will silently start to overwrite the heap's data structures. On a modern OS, there will be one or more virtual memory guard pages which prevent the stack from growing indefinitely. As long as the amount of memory in the guard pages is at least as large as the size of the growing procedure's activation record, the OS will guarantee you a segfault. If you're DOS running on a machine with no MMU, you're probably hosed.

• If the heap grows into the stack, the operating system should always be aware of the situation and some sort of system call will fail. The implementation of malloc() almost certainly notices the failure and returns NULL. What happens after that is up to you.

I'm always amazed at the willingness of compiler writers to hope that the OS puts guard pages in place to prevent stack overflow. Of course, this trick works well until you start having thousands of threads, each with its own stack...

Sayres

Even with a single thread, it is possible to get undetected stack-heap collision: gcc.gnu.org/ml/gcc-help/2014-07/msg00076.html (though this is rather unlikely to occur in practice, perhaps except in case of specific attacks). The GCC man page advises to use the -fstack-check flag with multi-threaded programs (and this flag also allows the collision to be detected in my example). – Illogicality

@Illogicality This is also detected with -fsanitise=thread -g (the -g is to add line numbers). Program runs 2x to 20x slower, but it detects a boatload of threading-safety issues. Also detected with -fsanitise=address. On any issue, it prints the exact line number where it occurred. Running sample program from said link from @Illogicality under Ubuntu 18.04 + gcc 9.3.0 reveals no issue: program correct terminates immediately with a segmentation fault even if compiled witih -O3. Adding the -fsanitise=X options (above) reveals the exact line of code. – Doublet

@Doublet With my test done with GCC 4.9.1 in 2014-07, the program terminated successfully. Now I get a segmentation fault during the GETADDR(c) before its printf, even with GCC 4.6.4 (released in 2013-04). So it seems that something has changed in the system to enable fast protection against stack-heap collision, independently from GCC (binutils? Linux kernel?). I would be interested to know. Things may also have changed in GCC, but later (2017+), so that GCC 4.6.4 is not concerned: gcc.gnu.org/legacy-ml/gcc-patches/2017-06/msg01343.html – Illogicality

"The C compiler" does not overwrite anything. The program does. An important distinction. – Uncaused

Don't you have a $2^48$ size address space on modern systems? What is really the probability of this collision? Is your program really $2^18$ Gigabytes large? – Darg

Answer 2

This would be platform dependent. On many platforms it actually can't happen at all (the heap and stack are allocated in different pages and ne'r the twain shall meet.

Keep in mind that the idea of the heap growing upward and the stack growing downward is only conceptual. On very small systems (like the old 8-bit micros that ran CP/M) and on some PICs and other flat memory model systems (those without an MMU nor any other virtual or protected memory support) then the heap and stack might be actually implemented this way. In that case the behavior would be undefined ... but it would almost certainly crash as soon as the code tried to return to some address on the top of the corrupted stack or follow an indirect pointer from one part of the heap to another or ...

In any event you won't see it on any modern, general purpose workstation or server. You'll hit a resource limit and get malloc failures, or you'll run into virtual memory and eventually the system will thrash itself into quivering pile of "hit the red switch."

Arber

Run into or run out of virtual memory? I've never heard of that happening. – Darg

Search on the term "fork bomb" and try some of the examples you find. But, warning ... you should expect that you'll have to reboot the machine to recover from doing so. – Arber

Hm. Do you mean that you have so many runnable processes that RAM is thrashing (assuming you use swap space)? I meant more that you run out of address space in a single process … with a 64 (or 48 bit) address space, it seems unlikely to me that stack and heap collide. – Darg

You can't run out of address space. The space is of a fixed order. You can fill it; your can overflow the value -- exceeding the type/capacity of any pointer or other data (register) containing addresses. But mostly that just doesn't make sense. It's about where you set the base of the heap and the base of the stack. – Arber

In practice the OS/kernel or memory management service (such as in Mach style microkernels) won't allow any actual collision of stack and heap. The heap is generally dynamically expanded by brk() or sbrk() (Unix system call) -- or some similar mechanism in other operating systems. Don't know about dynamic stack growth; I think that's less common. Thus "stack overflow" is still a real thing. – Arber

I had meant that you're using all your available address space, but I guess that's infeasible. What about on small microcontrollers and stuff where an OS is not stopping me? – Darg

This isn't really a forum for such discussion; but address space is analogous to the number of digits in your car's odometer. The OS provides fuel allowing you to drive up to some range from your current reading; but you can't even discuss addresses outside of the range of the odometers. There just aren't extra digits for referring to them. – Arber

Answer 3

In times like those it's time to turn to the sage words of Dr Egon Spengler....

• Dr. Egon Spengler: There's something very important I forgot to tell you.
• Dr. Peter Venkman: What?
• Dr. Egon Spengler: Don't let the heap collide with the stack.
• Dr. Peter Venkman: Why?
• Dr. Egon Spengler: It would be bad.
• Dr. Peter Venkman: I'm a little fuzzy on the whole "good/bad" thing here. What do you mean, "bad"?
• Dr. Egon Spengler: Try to imagine all life as you know it stopping instantaneously and every molecule in your body exploding at the speed of light.
• Dr. Ray Stantz: Total protonic reversal!
• Dr. Peter Venkman: That's bad. Okay. All right, important safety tip. Thanks, Egon.

Leckie

Oddly enough, the phrase I was thinking of was "dogs and cats living together" – Dipsomania

Great illustration. Hopefully universed -debug frees all it's memory! – Fascicule

Answer 4

You get an out of memory exception or stack exception if you are lucky. If you are unlucky the program heads off into a invalid memory and either throws a bad memory exception. If you are extremely unlucky the program carries on and trashes something it shouldn't and you never know why your program failed.

Finally of course the universe may crack.

Downes

+1 MS-DOS universe have cracked but we have not seen yet the boom – Alfreda

Note that stack overflow can't be a C++ exception. – Plaintive

@atorras - MSDOS universe won't crack until they prise the for command out of my cold dead hands :-) – Downes

Answer 5

You will get segmentation fault or memory allocation error if stack/heap overflow occurs. Here is an example :

void recursiveFun ()
{
    static int i;
//  char *str= (char *)malloc (100);
    printf ("%d\t", i++);
    recursiveFun ();
// free (str);
}

Suppose, you call above function, it will run out of stack and program will crash. Now, remove the commented lines and call the function again, you will find segmentation fault occurs in less time than and less recursion than earlier version. [ In my test environment, Stack Overflow happened after 5237765 recursion in first case, whereas in second scenario it occured after 2616325 recursion.]

Lenz

Amazing. How come the two lines of comment play a role in program execution? – Tine

Answer 6

It will give stack overflow error. Or it will fail the new heap memory allocation functions like malloc().

Telekinesis