Stack overflow

From Wikipedia, the free encyclopedia

In software, a stack overflow occurs when too much memory is used on the call stack. In many programming languages, the call stack contains a limited amount of memory, usually 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 too much memory is used on the call stack 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]

[edit] 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]

[edit] 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. This is usually the result of creating local array variables that are far too large. For this reason arrays larger than a few kilobytes should be allocated dynamically instead of as a local variable.^[4]

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.^[5][6]

[edit] C/C++/Objective C/Objective C++ examples

[edit] Infinite recursion with one function

 void a() {
   a();
 }
 int main() {
   a();
   return 0;
 }

This code calls a(), and a() calls itself, which will never end.

[edit] Infinite recursion with two functions

 void f(void); 
 void g(void);
 
 int main(void) {
   f();
 
   return 0;
 }
 
 void f(void) {
   g();
 }
 
 void g(void) {
   f();  
 }

f() and g() continuously call each other until the stack overflows.

[edit] Excessively large stack variables

 int main(void) {
   double n[10000000]; 
   return 0;
 }

The declared array consumes more memory than is available on the stack.

[edit] See also

Computer Science portal

• Stack buffer overflow
• Heap overflow
• Buffer overflow
• Call stack

[edit] References