Stack overflow - Revision history

imported>Registreernu: /* Constrained environment */

2025-10-18T07:23:29Z

Constrained environment

← Previous revision		Revision as of 07:23, 18 October 2025
Line 17:		Line 17:
	The most-common cause of stack overflow is excessively deep or infinite recursion, in which a function calls itself so many times that the space needed to store the variables and information associated with each call is more than can fit on the stack.<ref name="segFault">[https://stackoverflow.com/questions/2685413/what-is-the-difference-between-a-segmentation-fault-and-a-stack-overflow/2685434#2685434 What is the difference between a segmentation fault and a stack overflow?] {{Webarchive\|url=https://web.archive.org/web/20210913132615/https://stackoverflow.com/questions/2685413/what-is-the-difference-between-a-segmentation-fault-and-a-stack-overflow/2685434#2685434 \|date=2021-09-13 }} at [[Stack Overflow]]</ref>		The most-common cause of stack overflow is excessively deep or infinite recursion, in which a function calls itself so many times that the space needed to store the variables and information associated with each call is more than can fit on the stack.<ref name="segFault">[https://stackoverflow.com/questions/2685413/what-is-the-difference-between-a-segmentation-fault-and-a-stack-overflow/2685434#2685434 What is the difference between a segmentation fault and a stack overflow?] {{Webarchive\|url=https://web.archive.org/web/20210913132615/https://stackoverflow.com/questions/2685413/what-is-the-difference-between-a-segmentation-fault-and-a-stack-overflow/2685434#2685434 \|date=2021-09-13 }} at [[Stack Overflow]]</ref>

	An example of infinite recursion in [[C (programming language)\|C]].		Here is an example of infinite recursion in [[C (programming language)\|C]]:
	<syntaxhighlight lang="c">		<syntaxhighlight lang="c">
	int foo()		int foo() {
	{		return foo();
	return foo();
	}		}
	</syntaxhighlight>		</syntaxhighlight>

	The function ''foo'', when it is invoked, continues to invoke itself, allocating additional space on the stack each time, until the stack overflows resulting in a [[segmentation fault]].<ref name="segFault"/> However, some compilers implement [[tail-call optimization]], allowing 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.<ref name="tailRecur">{{cite web		The function ''foo'', when it is invoked, continues to invoke itself, allocating additional space on the stack each time, until the stack overflows, resulting in a [[segmentation fault]].<ref name="segFault"/> However, some compilers implement [[tail-call optimization]], allowing 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.<ref name="tailRecur">{{cite web
	\|title = An Introduction to Scheme and its Implementation		\|title = An Introduction to Scheme and its Implementation
	\|url = http://www.federated.com/~jim/schintro-v14/schintro_73.html		\|url = http://www.federated.com/~jim/schintro-v14/schintro_73.html
Line 76:		Line 75:
	\|		\|
	<syntaxhighlight lang="cpp">		<syntaxhighlight lang="cpp">
	~~void function (argument)~~		class SomeObject {
	{		public:
	~~if (condition)~~		SomeObject* next;
	~~function (argument.~~next);		};

			void someFunction(SomeObject* argument) {
			if (getCondition()) {
			someFunction(argument.next);
			}
	}		}
	</syntaxhighlight>		</syntaxhighlight>
	\|		\|
	<syntaxhighlight lang="cpp">		<syntaxhighlight lang="cpp">
	~~stack~~.push(argument);		Stack<SomeObject*> s;
	while (!~~stack~~.empty())
	{		s.push(argument);
	argument = ~~stack~~.pop();		while (!s.empty()) {
	if (condition)		argument = s.pop();
	~~stack~~.push(argument.next);		if (condition) {
			s.push(argument.next);
			}
	}		}
	</syntaxhighlight>		</syntaxhighlight>
Line 106:		Line 111:
	<syntaxhighlight lang="cpp">		<syntaxhighlight lang="cpp">
	int pow(int base, int exp) {		int pow(int base, int exp) {
	if (exp > 0)		if (exp > 0) {
	return base * pow(base, exp - 1);		return base * pow(base, exp - 1);
	else		} else {
	return 1;		return 1;
			}
	}		}
	</syntaxhighlight>		</syntaxhighlight>
Line 119:		Line 125:

	int pow_accum(int base, int exp, int accum) {		int pow_accum(int base, int exp, int accum) {
	if (exp > 0)		if (exp > 0) {
	return pow_accum(base, exp - 1, accum * base);		return pow_accum(base, exp - 1, accum * base);
	else		} else {
	return accum;		return accum;
			}
	}		}
	</syntaxhighlight>		</syntaxhighlight>
Line 172:		Line 179:
	An example of a very large stack variable in [[C (programming language)\|C]]:		An example of a very large stack variable in [[C (programming language)\|C]]:
	<syntaxhighlight lang="c">		<syntaxhighlight lang="c">
	int foo()		int foo() {
	{		double x[1048576];
	double x[1048576];
	}		}

	</syntaxhighlight>		</syntaxhighlight>

Line 182:		Line 187:

	===Constrained environment===		===Constrained environment===
	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. Because kernels are generally multi-threaded, people new to ~~[[Kernel (operating system)\|~~kernel]] development are usually discouraged from using recursive algorithms or large stack buffers.<ref name="apple1">{{cite web		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. Because [[Kernel (operating system)\|kernels]] are generally multi-threaded, people new to kernel development are usually discouraged from using recursive algorithms or large stack buffers.<ref name="apple1">{{cite web \|publisher= [[Apple Inc]]. \|title= Kernel Programming Guide: Performance and Stability Tips \|url= https://developer.apple.com/library/mac/documentation/Darwin/Conceptual/KernelProgramming/style/style.html#//apple_ref/doc/uid/TP30000905-CH208-TPXREF111 \|date= 2014-05-02 \|access-date= 2014-05-02 \|archive-date= 2014-05-03 \|archive-url= https://web.archive.org/web/20140503011953/https://developer.apple.com/library/mac/documentation/Darwin/Conceptual/KernelProgramming/style/style.html#//apple_ref/doc/uid/TP30000905-CH208-TPXREF111 \|url-status= live }}</ref>
	\| publisher= [[Apple Inc]].
	\| title= Kernel Programming Guide: Performance and Stability Tips
	\| url= https://developer.apple.com/library/mac/documentation/Darwin/Conceptual/KernelProgramming/style/style.html#//apple_ref/doc/uid/TP30000905-CH208-TPXREF111
	\| date= 2014-05-02
	\| access-date= 2014-05-02
	\| archive-date= 2014-05-03
	\| archive-url= https://web.archive.org/web/20140503011953/https://developer.apple.com/library/mac/documentation/Darwin/Conceptual/KernelProgramming/style/style.html#//apple_ref/doc/uid/TP30000905-CH208-TPXREF111
	\| url-status= live
	}}</ref>

	==See also==		==See also==
			* [[Buffer overflow]]
	*[[Buffer overflow]]		** [[Heap overflow]]
	**[[Heap overflow]]		** [[Stack buffer overflow]]
	**[[Stack buffer overflow]]		* [[Call stack]]
	*[[Call stack]]		* [[Double fault]]
	*[[Double fault]]		* [[Out of memory]]
	*[[Out of memory]]

	==References==		==References==

imported>OAbot: Open access bot: url-access updated in citation with #oabot.

2025-05-25T20:17:50Z

Open access bot: url-access updated in citation with #oabot.

New page

{{Short description|Type of software bug}}
{{for multi|the website|Stack Overflow|other uses}}
In software, a '''stack overflow''' occurs if the [[call stack]] pointer exceeds the [[Stack (abstract data type)|stack]] bound. The call stack may consist of a limited amount of [[address space]], 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 (computing)|crash]].<ref name="fortran1">{{cite web
|last = Burley
|first = James Craig
|title = Using and Porting GNU Fortran
|url = http://sunsite.ualberta.ca/Documentation/Gnu/gcc-2.95.2/html_node/g77_597.html
|date = 1991-06-01
|url-status = dead
|archive-url = https://web.archive.org/web/20120206112619/http://sunsite.ualberta.ca/Documentation/Gnu/gcc-2.95.2/html_node/g77_597.html
|archive-date = 2012-02-06
}}</ref>

==Causes==
===Infinite recursion===
{{Main|Infinite recursion}}
The most-common cause of stack overflow is excessively deep or infinite recursion, in which a function calls itself so many times that the space needed to store the variables and information associated with each call is more than can fit on the stack.<ref name="segFault">[https://stackoverflow.com/questions/2685413/what-is-the-difference-between-a-segmentation-fault-and-a-stack-overflow/2685434#2685434 What is the difference between a segmentation fault and a stack overflow?] {{Webarchive|url=https://web.archive.org/web/20210913132615/https://stackoverflow.com/questions/2685413/what-is-the-difference-between-a-segmentation-fault-and-a-stack-overflow/2685434#2685434 |date=2021-09-13 }} at [[Stack Overflow]]</ref>

An example of infinite recursion in [[C (programming language)|C]].
<syntaxhighlight lang="c">
int foo()
{
return foo();
}
</syntaxhighlight>

The function ''foo'', when it is invoked, continues to invoke itself, allocating additional space on the stack each time, until the stack overflows resulting in a [[segmentation fault]].<ref name="segFault"/> However, some compilers implement [[tail-call optimization]], allowing 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.<ref name="tailRecur">{{cite web
|title = An Introduction to Scheme and its Implementation
|url = http://www.federated.com/~jim/schintro-v14/schintro_73.html
|date = 1997-02-19
|url-status = dead
|archive-url = https://web.archive.org/web/20070810213035/http://www.federated.com/~jim/schintro-v14/schintro_73.html
|archive-date = 2007-08-10
}}</ref>

Some C compiler options will effectively enable [[tail-call optimization]]; for example, compiling the above simple program using [[GNU Compiler Collection|gcc]] with <code>-O1</code> will result in a segmentation fault, but not when using <code>-O2</code> or <code>-O3</code>, since these optimization levels imply the <code>-foptimize-sibling-calls</code> compiler option.<ref>{{cite web|title=Using the GNU Compiler Collection (GCC): Optimize Options|url=https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html|access-date=2017-08-20|archive-date=2017-08-20|archive-url=https://web.archive.org/web/20170820201527/https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html|url-status=live}}</ref> Other languages, such as [[Scheme (programming language)|Scheme]], require all implementations to include tail-recursion as part of the language standard.<ref>{{cite journal
|author = Richard Kelsey
|date = August 1998
|title = Revised<sup>5</sup> Report on the Algorithmic Language Scheme
|url = http://www.schemers.org/Documents/Standards/R5RS/
|journal = Higher-Order and Symbolic Computation
|volume = 11
|issue = 1
|pages = 7–105
|doi = 10.1023/A:1010051815785
|accessdate = 2012-08-09
|author2 = William Clinger
|author3 = Jonathan Rees
|display-authors = 3
|last4 = Rozas
|first4 = G.J.
|last5 = Adams Iv
|first5 = N.I.
|last6 = Friedman
|first6 = D.P.
|last7 = Kohlbecker
|first7 = E.
|last8 = Steele Jr.
|first8 = G.L.
|last9 = Bartley
|first9 = D.H.
|s2cid = 14069423
|archive-date = 2007-01-05
|archive-url = https://web.archive.org/web/20070105152327/http://www.schemers.org/Documents/Standards/R5RS/
|url-status = live
|url-access= subscription
}}</ref>

===Very deep recursion===
A recursive function that terminates in theory but causes a call stack buffer overflow in practice can be fixed by transforming the recursion into a loop and storing the function arguments in an explicit stack (rather than the implicit use of the call stack). This is always possible because the class of [[primitive recursive function]]s is equivalent to the class of LOOP computable functions. Consider this example in [[C++]]-like pseudocode:

{| width="100%"
!width="50%"|
!width="50%"|
|-
|
<syntaxhighlight lang="cpp">
void function (argument)
{
if (condition)
function (argument.next);

}
</syntaxhighlight>
|
<syntaxhighlight lang="cpp">
stack.push(argument);
while (!stack.empty())
{
argument = stack.pop();
if (condition)
stack.push(argument.next);
}
</syntaxhighlight>
|}

A primitive recursive function like the one on the left side can always be transformed into a loop like on the right side.

A function like the example above on the left would not be a problem in an environment supporting [[tail-call optimization]]; however, it is still possible to create a recursive function that may result in a stack overflow in these languages. Consider the example below of two simple integer exponentiation functions.

{| width="100%"
!width="50%"|
!width="50%"|
|-
|
<syntaxhighlight lang="cpp">
int pow(int base, int exp) {
if (exp > 0)
return base * pow(base, exp - 1);
else
return 1;
}
</syntaxhighlight>
|
<syntaxhighlight lang="cpp">
int pow(int base, int exp) {
return pow_accum(base, exp, 1);
}

int pow_accum(int base, int exp, int accum) {
if (exp > 0)
return pow_accum(base, exp - 1, accum * base);
else
return accum;
}
</syntaxhighlight>
|}

Both <code>pow(base, exp)</code> functions above compute an equivalent result, however, the one on the left is prone to causing a stack overflow because tail-call optimization is not possible for this function. During execution, the stack for these functions will look like this:

{| width="100%"
!width="50%"|
!width="50%"|
|-
|
<syntaxhighlight lang="cpp">
pow(5, 4)
5 * pow(5, 3)
5 * (5 * pow(5, 2))
5 * (5 * (5 * pow(5, 1)))
5 * (5 * (5 * (5 * pow(5, 0))))
5 * (5 * (5 * (5 * 1)))
625
</syntaxhighlight>
|
<syntaxhighlight lang="cpp">
pow(5, 4)
pow_accum(5, 4, 1)
pow_accum(5, 3, 5)
pow_accum(5, 2, 25)
pow_accum(5, 1, 125)
pow_accum(5, 0, 625)
625
</syntaxhighlight>
|}

Notice that the function on the left must store in its stack <code>exp</code> number of integers, which will be multiplied when the recursion terminates and the function returns 1. In contrast, the function at the right must only store 3 integers at any time, and computes an intermediary result which is passed to its following invocation. As no other information outside of the current function invocation must be stored, a tail-recursion optimizer can "drop" the prior stack frames, eliminating the possibility of a stack overflow.

===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 [[C dynamic memory allocation|allocated dynamically]] instead of as a local variable.<ref name="onlamp">{{cite web
| last = Feldman
| first = Howard
| title = Modern Memory Management, Part 2
| url = http://www.onlamp.com/pub/a/onlamp/2005/11/23/memory-management-2.html
| date = 2005-11-23
| access-date = 2007-08-14
| archive-date = 2012-09-20
| archive-url = https://web.archive.org/web/20120920112622/http://onlamp.com/pub/a/onlamp/2005/11/23/memory-management-2.html
| url-status = dead
}}</ref>

An example of a very large stack variable in [[C (programming language)|C]]:
<syntaxhighlight lang="c">
int foo()
{
double x[1048576];
}

</syntaxhighlight>

On a C implementation with 8 byte [[Double-precision floating-point format|double-precision floats]], the declared array consumes 8 [[megabytes]] of data; if this is more memory than is available on the stack (as set by thread creation parameters or operating system limits), a stack overflow will occur.

===Constrained environment===
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. Because kernels are generally multi-threaded, people new to [[Kernel (operating system)|kernel]] development are usually discouraged from using recursive algorithms or large stack buffers.<ref name="apple1">{{cite web
| publisher= [[Apple Inc]].
| title= Kernel Programming Guide: Performance and Stability Tips
| url= https://developer.apple.com/library/mac/documentation/Darwin/Conceptual/KernelProgramming/style/style.html#//apple_ref/doc/uid/TP30000905-CH208-TPXREF111
| date= 2014-05-02
| access-date= 2014-05-02
| archive-date= 2014-05-03
| archive-url= https://web.archive.org/web/20140503011953/https://developer.apple.com/library/mac/documentation/Darwin/Conceptual/KernelProgramming/style/style.html#//apple_ref/doc/uid/TP30000905-CH208-TPXREF111
| url-status= live
}}</ref>

==See also==

*[[Buffer overflow]]
**[[Heap overflow]]
**[[Stack buffer overflow]]
*[[Call stack]]
*[[Double fault]]
*[[Out of memory]]

==References==
{{Reflist}}

==External links==
* [http://software.intel.com/en-us/blogs/2010/07/01/the-reasons-why-64-bit-programs-require-more-stack-memory/ The reasons why 64-bit programs require more stack memory] {{webarchive | url = https://web.archive.org/web/20171104123645/http://software.intel.com/en-us/blogs/2010/07/01/the-reasons-why-64-bit-programs-require-more-stack-memory/ | date = 4 November 2017}}

{{Memory management navbox}}

[[Category:Software bugs]]
[[Category:Computer errors]]