Stack overflow
In software, a stack overflow occurs when too much memory is used on the call stack. The call stack contains a limited amount of memory, often determined at the start of the program. The size of the call stack depends on many factors, including the programming language, machine architecture, multi-threading, and amount of available memory. When a program attempts to use more space than is available on the call stack (that is, when it attempts to access memory beyond the call stack's bounds, which is essentially a buffer overflow), the stack is said to overflow, typically resulting in a program crash.[1] This class of software bug is usually caused by one of two types of programming errors.[2]
Infinite recursion
The most common cause of stack overflows is excessively deep or infinite recursion. Languages like Scheme, which implement tail-call optimization, allow infinite recursion of a specific sort—tail recursion—to occur without stack overflow. This works because tail-recursion calls do not take up additional stack space.[3]
An example of infinite recursion in C.
int foo() {
return foo();
}
The function foo, when it is invoked, continues to invoke itself, using additional space on the stack each time, until the stack overflows resulting in a segmentation fault.[4]
Very large stack variables
The other major cause of a stack overflow results from an attempt to allocate more memory on the stack than will fit, for example by creating local array variables that are too large. For this reason some authors recommend that arrays larger than a few kilobytes should be allocated dynamically instead of as a local variable.[5]
An example of a very large stack variable in C:
int foo() {
double x[1000000];
}
The declared array consumes 8 megabytes of data (assuming each double is 8 bytes); if this is more memory than is available on the stack, a stack overflow will occur. [further explanation needed]
Stack overflows are made worse by anything that reduces the effective stack size of a given program. For example, the same program being run without multiple threads might work fine, but as soon as multi-threading is enabled the program will crash. This is because most programs with threads have less stack space per thread than a program with no threading support. Similarly, people new to kernel development are usually discouraged from using recursive algorithms or large stack buffers.[6][7]
See also
References
- ^ Burley, James Craig (1991-06-01). "Using and Porting GNU Fortran".
- ^ Danny, Kalev (2000-09-05). "Understanding Stack Overflow".
- ^ "An Introduction to Scheme and its Implementation". 1997-02-19.
- ^ What is the difference between a segmentation fault and a stack overflow? at StackOverflow
- ^ Feldman, Howard (2005-11-23). "Modern Memory Management, Part 2".
- ^ "Kernel Programming Guide: Performance and Stability Tips". Apple Inc. 2006-11-07.
- ^ Dunlap, Randy (2005-05-19). "Linux Kernel Development: Getting Started" (PDF).
