本頁使用了標題或全文手工轉換

堆疊溢位

維基百科,自由的百科全書
跳至導覽 跳至搜尋
「堆疊溢位」的各地常用別名
中國大陸 堆棧溢出
臺灣 堆疊溢位
港澳 堆疊溢位

堆疊溢位(英語: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;
};

參看[編輯]

註釋[編輯]

  1. ^ Chris Anley, John Heasman, Felix Lindner, Gerardo Richarte. The Shellcoder's Handbook: Discovering and Exploiting Security Holes. John Wiley & Sons. 2011. ISBN 1118079124 (英語). 
  2. ^ Kernel Programming Guide: Performance and Stability Tips. Apple Inc. 2006-11-07. (原始內容存檔於2008-12-07) (英語). 
  3. ^ Dunlap, Randy. Linux Kernel Development: Getting Started (PDF). 2005-05-19. (原始內容 (PDF)存檔於2012-02-27) (英語). 
  4. ^ Coplien, James O. To Iterate is Human, to Recurse, Divine. C++ Report Vol 10. No.7. SIGS Publications Group: 43–51. 1998年7月 (英語).