堆疊溢位
![本页使用了标题或全文手工转换](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) (英语).
|