Stack Implementation - Preventing Fatal Error in Real Time Systems

Question

Does every programming language that implements recursion implement Stack. How in a real computer the stack grows ? Does running out of Stack space a fatal error ? How to prevent from happening ?

Answer 1

The short answer is, You must monitor the stack and the heap for growth but remember, memory is finite. You can always run out of room.

First of all, you have an incorrect assumption that needs to be corrected. The stack is not a construct of the programming language. It is a implementation of the hardware. As such the solution for protecting from an overrun is going to be specific to the environment.

Also, stack implementation will differ from hardware to hardware. In the x86 world, stacks grow down. Paging is often used to separate the stack in such a way that if a overrun occurs, a page fault will be raised. This will allow the operating system to deal with or stop the offending process. ref: What is the direction of stack growth in most modern systems?

Theoretically, a stack overrun does not have to cause a error. If your monitor or other mechanism detects a fault, it can be handled by adding memory to the stack and allow for more space. This would assume that you have consecutive memory space or some way to virtually apply consecutive memory space. However, this really doesn't solve the problem. it just delays the crash (assuming the recursion continues). You will eventually run out of memory or collide with your heap.

To answer your questions directly:

Does every program that uses recursion use the stack? - Every progarm that runs on hardware that uses the stack for CALL and RET (or equivalent) will use the stack even without using recursion.

How do stacks grow? - Depends on the hardware. Find the white paper for your processor.

Does running out of stack space cause an error? - Not necessarily. If the hardware or OS does not cause an error, the program will happily keep running. Memory corruption is the most likely result in that case. That will cause all sorts of odd behavior and probably segfault.

How to prevent this from happening? - Depends on hardware and on the situation. Generically, i would check stack integrity for each process on task switch. Also pad the stack to safely allow for small overruns. If an overrun occurs, you will need to either allocate more CONSECUTIVE memory or relocate the stack.

Allocating consecutive memory is unlikely if you do not have a virtual memory model. Without that you would need to keep the space clear for growth, and in that case, you might as well just allocate it to the stack to begin with.

Hope this helps.