热门问题
时间线
聊天
视角
呼叫堆疊
用于存储运行程序子程序的栈数据结构 来自维基百科，自由的百科全书
Remove ads
呼叫堆疊（英語：Call stack，中國大陸稱調用堆棧）別稱有：執行棧（execution stack）、控制棧（control stack）、運行時棧（run-time stack）與機器棧（machine stack），是電腦科學中存儲有關正在執行的子程式的訊息的堆疊。英文有時直接簡稱「棧」（the stack），但堆疊中不一定僅存儲子程式訊息。幾乎所有電腦程式都依賴於呼叫堆疊，而高階語言一般將呼叫堆疊的細節隱藏至後台。
 | 此條目可參照英語維基百科相應條目來擴充。 (2020年7月28日) |
呼叫堆疊最經常被用於存放子程式的返回位址。在呼叫任何子程式時，主程式都必須暫存子程式執行完畢後應該返回到的位址。因此，如果被呼叫的子程式還要呼叫其他的子程式，其自身的返回位址就必須存入呼叫堆疊，在其自身執行完畢後再行取回。在遞迴程式中，每一層次遞迴都必須在呼叫堆疊上增加一條位址，因此如果程式出現無限遞迴（或僅僅是過多的遞迴層次），呼叫堆疊就會產生堆疊溢位。
Remove ads
功能
呼叫堆疊的主要功能是存放返回位址。除此之外，呼叫堆疊還用於存放：
結構
調用棧由棧幀（stack frame）組成，它們也叫做「活動記錄」或「活動幀」。它們是機器依賴並且ABI依賴的數據結構，包含了子例程狀態信息。每個棧幀對應於一個子例程的仍未通過返回來完成的一次調用[1]。在堆棧頂部的棧幀對應當前執行例程。例如，一個叫做DrawLine的子例程當前正在運行，它被子例程DrawSquare所調用，右側圖示中給出了調用棧的頂部狀況。
在棧幀大小可以不同的時候，比如在不同的函數之間或在特定函數的多次調用之間，從堆棧彈出一個幀不導致棧指針（stack pointer）減少固定大小。在函數返回之時，指針轉而被復原為幀指針（frame pointer），即這個函數被調用前最近的棧指針的值。每個棧幀都包含一個幀指針，指向下面最近的幀的頂部。棧指針是在所有調用之間共享的可變的寄存器。一個函數的給定一次調用的幀指針，是這個函數被調用前的棧指針的複製品[2]。
一個例程可以直接變更棧指針，或執行入棧指令和出棧指令間接改變棧指針。在入棧指令自動遞增棧指針所指地址的調用棧中，在一個幀之中的所有其他局部的字段的位置都可定義為，相對於幀指針即下面最近幀的頂部的正數偏移量。在x86架構的調用約定下它們定義為，相對於幀指針RBP的負數偏移量。
出於某些目的，一個子例程的棧幀和它的調用者的棧幀可以視為有所交疊（overlap），交疊由從調用者傳遞給被調用者的參數值所在區域組成。在調用結束時清理參數值的責任由被調用者實行的情況下，比如Pascal式調用約定，交疊自然地劃分在被調用者棧幀之中。在入棧指令自動遞增棧指針所指地址的調用棧中，調用者傳遞給一個例程的參數值的位置定義為，相對於幀指針即下面最近幀的頂部的負數偏移量。在x86架構的調用約定下它們定義為，相對於幀指針RBP的正數偏移量。
在一些環境中，調用者將每個實際參數（argument）壓入堆棧之上，從而擴展了它自己棧幀，接着調用被調用者。在其他的環境中，調用者在它的棧幀的頂部有一個預先分配的區域，用來持有它要提供給其所調用的子例程的實際參數。這個區域有時稱為「出去（outgoing）實參區域」或「調出（callout）區域」，可以對應ALGOL 60的術語擬制塊。在這種途徑下，由編譯器計算出的這個區域的大小應當滿足任何被調用的子例程的最大所需。
Remove ads
棧解繞
從被調用函數返回會彈出堆棧的頂部幀，並可能留下返回的一個值。更一般性的動作是從堆棧彈出一個或多個幀，從而恢復在程序中其它某處的執行，這叫做棧解繞（unwind），並且在使用了非局部控制結構的時候必須進行，比如例外處理。在這種情況下，一個函數的棧幀包含了指定例外處理器的一個或多個入口（entry）。在一個例外被拋出的時候，堆棧被解繞直到找到了準備處理（接住）這個拋出例外類型的一個處理器。
一些語言有要求一般性解繞的其他控制結構。Pascal允許使用全局性的goto語句，將控制從嵌套的函數傳送出來並進入此前調用的外面的函數。這個操作要求堆棧被解繞，為了恢復正確的上下文，從而將控制傳送給包圍它的外面函數中的目標語句，需要移除多少棧幀就移除多少。與之類似，C語言有setjmp與longjmp函數充當非局部跳轉，它們分別保存和恢復：棧指針、程序計數器、由被調用者保存的寄存器和ABI要求的任何其他內部狀態。在編寫可移植的C++代碼之時，不應信賴執行非局部跳轉會發生正常的堆棧解繞來進行所要的清理動作。
Common Lisp允許通過使用unwind-protect特殊算子，控制在堆棧被解繞時都要做些什麼。在支持續體的編程語言比如Scheme和新澤西Standard ML中，在應用續體的時候，堆棧在邏輯上被解繞並重繞（rewind）上這個續體的堆棧，接着盤繞（wind）上要傳遞的那一個值。實現續體可以採用多種策略，例如通過使用多個顯式的堆棧，應用一個續體可以簡單的停用或捨棄當前堆棧並激活這個續體的堆棧。Scheme語言提供了對續體調用進行「保護」的dynamic-wind，只要控制離開或進入它所界定範圍，包括通過應用續體這種非局部跳轉方式，在分別對控制棧「解繞」或「重繞」的特定點上，都會執行任意指定的thunk。
在支持續體的編程語言和執行棧可以在運行時檢查並修改的編程語言比如Smalltalk和Cilk中，在必須支持續體的時候，一個函數的局部變量在這個函數返回時不能被銷毀：一個保存了的續體可以在往後時重入（re-enter）這個函數，並且不僅期望其中的變量不變動，而且期望整個調用序列的棧幀都存在使得這個函數能再次返回。要解決這個問題，棧幀可以在父指針樹結構中動態分配，並在不再有續體引用的時候，將其留作垃圾回收。這種類型的結構還解決了上行和下行的函數參數問題，因為在這種基底上很容易實現頭等詞法閉包。由棧幀鏈接起來而實現的這種實際運行棧，也被稱為「麵條式堆棧」[3]，它包含了變量綁定和其他環境特徵。
Remove ads
安全性
在較底層語言（如組合語言與C語言中），程式控制訊息與資料可能一同被存入呼叫堆疊中，因此造成安全隱患，可能允許惡意程式通過棧緩衝區溢出（stack buffer overflow）來獲取程式的控制權。
參見
引用
延伸閱讀
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads