呼叫堆疊

呼叫堆疊（Call stack）別稱有：執行棧（execution stack）、控制棧（control stack）、運行時棧（run-time stack）與機器棧（machine stack），是電腦科學中存儲有關正在執行的子程式的訊息的堆疊。英文有時直接簡稱「棧」（the stack），但堆疊中不一定僅存儲子程式訊息。幾乎所有電腦程式都依賴於呼叫堆疊，而高階語言一般將呼叫堆疊的細節隱藏至後台。

呼叫堆疊最經常被用於存放子程式的返回位址。在呼叫任何子程式時，主程式都必須暫存子程式執行完畢後應該返回到的位址。因此，如果被呼叫的子程式還要呼叫其他的子程式，其自身的返回位址就必須存入呼叫堆疊，在其自身執行完畢後再行取回。在遞迴程式中，每一層次遞迴都必須在呼叫堆疊上增加一條位址，因此如果程式出現無限遞迴（或僅僅是過多的遞迴層次），呼叫堆疊就會產生堆疊溢位。

## 功能

呼叫堆疊的主要功能是存放返回位址。除此之外，呼叫堆疊還用於存放：

- 局部數據存儲：子程式的本地變數可以存入呼叫堆疊，這樣可以達到不同子程式間變數分離開的作用。
- 參數傳遞：如果暫存器不足以容納子程式的參數值，可以在呼叫堆疊上存入參數值。
- 包圍子程式上下文：有些語言（如Pascal與Ada）支援嵌套函數子程式，即子程式中可以利用包圍子程式的本地變數，亦稱其為非局部變量。這些變數可以通過呼叫堆疊鏈接入子程式。

## 結構

<image>

調用棧由棧幀（stack frame）組成，它們也叫做「活躍（activation）記錄」或「活躍幀」。它們是機器依賴軟體並且ABI依賴的數據結構，包含了子例程狀態資訊。每個棧幀對應於一個子例程的仍未通過返回來完成的一次調用。在堆棧頂部的棧幀對應當前執行例程。例如，一個叫做`DrawLine`的子例程當前正在運行，它被子例程`DrawSquare`所調用，右側圖示中給出了調用棧的頂部狀況。

### 棧指針與幀指針

不同函數在棧上分配的棧幀大小通常不同，這取決於局部變量、保存寄存器以及對齊需求。因此，在函數調用和返回過程中，棧指針，通常不會按固定步長或固定規律變化。注意，在某些x86調用約定或編譯選項下，並不會保留幀指針。在採用幀指針的調用約定中，每個函數通常會使用一個專用寄存器作為棧幀基準，如x86架構的EBP或RBP。函數入口時會保存上一層幀指針，並將當前棧指針複製到幀指針中，函數返回時再恢復該幀指針。

棧指針可以通過處理器指令顯式修改，例如直接調整棧指針以分配棧空間，或通過入棧、出棧等操作間接改變。在棧向低地址增長的調用棧中，某個棧幀內其他局部的位置通常可用幀指針的偏移量來表示，在保留幀指針的x86調用約定中，局部變量的位置通常可表示為相對於幀指針（如 RBP）的負偏移量。

### 控制連結

在大多數系統的棧幀中，擁有叫做「控制連結」或「動態連結」的欄位，它包含幀指針寄存器以前的值，這個值指向了調用者的棧幀，調用約定在被調用者返回之前通過它將幀指針復原到調用者的棧幀。這個欄位存儲在棧幀的已知位置通常為首位之上，從而確使這個例程的代碼可以連續地訪問在當前執行例程的棧幀之下的每個棧幀，比如LISP中以符號為鍵訪問棧幀中的關聯列表。

### 交疊

從調用者傳遞給被調用者的參數值所在區域，在調用約定要求在調用結束時清理參數值的責任由被調用者實行的情況下，可以自然地視為處在被調用者棧幀之中；如果在調用結束時清理參數值的責任由調用者實行，這個區域也可以視為是處在被調用者的棧幀和它的調用者的棧幀之間的交疊（overlap）區域。在入棧指令自動遞增棧指針所指地址的調用棧中，調用者傳遞給被調用者的參數值的位置定義為，相對於被調用者幀指針即下面最近幀的頂部的負數偏移量。在x86架構的調用約定下它們定義為，相對於被調用者幀指針`RBP`的正數偏移量。

在一些環境中，調用者將每個實際參數（argument）壓入堆棧之上，從而擴展了它自己棧幀，接著調用被調用者。在其他的環境中，調用者在它的棧幀的頂部有一個預先分配的區域，用來持有它要提供給其所調用的子例程的實際參數。這個區域有時稱為「出去（outgoing）實參區域」或「調出（callout）區域」，可以對應ALGOL 60的術語擬制塊。在這種途徑下，由編譯器計算出的這個區域的大小應當滿足任何被調用的子例程的最大所需。

### 靜態連結

支持嵌套函數子例程的程式語言在調用幀中還擁有一個欄位，它指向最近的封裝這個被調用者的過程的「最新」活躍的棧幀，也就是這個被調用者在詞法上的直接靜態作用域。遞歸的內部例程為每次調用創建單獨的調用棧幀，在這種情況下，所有內部例程的這個連結都指向相同的外部例程上下文。這個連結在動態和遞歸調用期間追蹤了靜態嵌套，它被稱為「靜態連結」或「下棧（downstack）連結」。

連續地憑藉靜態連結可以訪問在所有嵌套層級上封裝它的諸例程的局部數據，故而它也被稱為「訪問連結」。在內層函數不訪問在封裝中的任何非常量的局部數據的時候，訪問連結可以被優化掉，因為在這種情況比如純函數下，只通過實際參數和返回值來通信。

還有一種策略不再只提供到直接包圍者的靜態連結，轉而將到包圍諸靜態棧幀的諸引用搜集進入叫做「展示」（display）的一個指針陣列之中，它們是用來定位想要的棧幀的索引。採用了展示的架構，由於為每個包圍層級都存儲一個連結，訪問淺層數據的深層嵌套例程不需要遍歷多個靜態連結。一些歷史上的電腦比如Burroughs大型系統有特殊的Burroughs大型系統#展示寄存器用來支持直到32層的靜態嵌套。

一個例程的展示通常位於其自己的棧幀之中，展示項目指示包含作用域，它們從適合作為其前綴的調用者展示獲得而來。一個例程的詞法嵌套深度是一個已知常量，所以這個例程的展示的大小是固定的。還有由於要遍歷哪些包含作用域是已知的，進入這個展示的索引也是固定的。針對最現代機器比如無處不在的x86處理器，編譯器及其優化方案在有需要的時候，可以簡單的在棧幀上為到所訪問包圍層級的這些指針預留一些字。

## 棧解繞

<image>

從被調用函數返回會彈出堆棧的頂部幀，並可能留下返回的一個值。更一般性的動作是從堆棧彈出一個或多個棧幀，從而恢復在程序中其它某處的執行，這叫做棧解繞（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）這個函數，並且不僅期望其中的變量不變動，而且期望整個調用序列的棧幀都存在使得這個函數能再次返回。要解決這個問題，棧幀可以在父指針樹結構中動態分配，並在不再有續體引用的時候，將其留作垃圾回收。這種類型的結構還解決了上行和下行的函數參數問題，因為在這種基底上很容易實現頭等詞法閉包。由棧幀連結起來而實現的這種實際運行棧，也被稱為「麵條式堆棧」，它包含了變量綁定和其他環境特徵。

## 安全性

在較底層語言（如組合語言與C語言中），程式控制訊息與資料可能一同被存入呼叫堆疊中，因此造成安全隱患，可能允許惡意程式通過棧緩衝區溢出（stack buffer overflow）來獲取程式的控制權。