堆栈溢出
![本页使用了标题或全文手工转换](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
“堆栈溢出”的各地常用名称 | |
---|---|
中国大陆 | 堆栈溢出 |
台湾 | 堆叠溢位 |
港澳 | 堆叠溢位 |
堆栈溢出(英语:stack overflow)在电脑科学中是指使用过多的存储器时导致调用堆栈产生的溢出[1],也是缓冲区溢出中的一种。堆栈溢出的产生是由于过多的函数调用,导致使用的调用堆栈大小超过事先规划的大小,覆盖其他存储器内的资料,一般在递归中产生。堆栈溢出很可能由无限递归(Infinite recursion)产生,但也可能仅仅是过多的堆栈层级。
堆栈溢出在內核设计中尤其危险,因此很多入门內核设计教程建议用户不要尝试使用递归程序;而是基于安全和性能考量,改用循环处理问题。[2][3][4]
在POSIX兼容平台上,堆栈溢出通常会造成操作系统产生SIGSEGV信号。
递归溢出
无限递归
无限递归是堆栈溢出的最常见原因,如以下的C/C++语言程序会产生堆栈溢出:
int foo()
{
return foo(); //這裡出現无限重复的自我调用
}
然而有些语言(如Scheme)支持尾部递归优化,在这些语言中只有一般递归会产生堆栈溢出,而尾部递归不会:
(define (foo) (foo))
(define (foo) (+ (foo) 1))
这段代码中,前者(第一句)进入死循环(Infinite loop),但不会产生堆栈溢出;后者(第二句)则会产生堆栈溢出。
防止堆栈溢出
多数无限递归出现原因,都是基于程序本身没有错误检测机制:
int factorial( const int *const n ){
if ( *n == 0 )
return 1;
else
return *n * factorial( *n-- ); //這裡出現自我呼叫
};
如果在这里的n
是负数则会出现无限递归。其实,这段程序可以简单地加以修改,把n
的类型由整数改为非负整数即可解决:
unsigned int factorial( const unsigned int *const n ){
if ( *n == 0 )
return 1;
else
return *n * factorial( *n-- );
};
或者使用循环处理:
unsigned int factorial( const unsigned int *const n ){
unsigned int i, result;
for ( i = *n, result = 1; i > 0 ; --i )
result *= i;
//自我呼叫部份改為迴圈處理
return result;
};
参看
注释
- ^ Chris Anley, John Heasman, Felix Lindner, Gerardo Richarte. The Shellcoder's Handbook: Discovering and Exploiting Security Holes. John Wiley & Sons. 2011. ISBN 1118079124 (英语).
- ^ Kernel Programming Guide: Performance and Stability Tips. Apple Inc. 2006-11-07. (原始内容存档于2008-12-07) (英语).
- ^ Dunlap, Randy. Linux Kernel Development: Getting Started (PDF). 2005-05-19. (原始内容 (PDF)存档于2012-02-27) (英语).
- ^ Coplien, James O. To Iterate is Human, to Recurse, Divine. C++ Report Vol 10. No.7. SIGS Publications Group: 43–51. 1998年7月 [2011-12-20]. (原始内容存档于2020-10-19) (英语).
|