热门问题
时间线
聊天
视角
呼叫堆疊
用于存储运行程序子程序的栈数据结构 来自维基百科，自由的百科全书
Remove ads
呼叫堆疊（英語：Call stack，中國大陸稱調用堆棧）別稱有：執行堆疊（execution stack）、控制堆疊（control stack）、執行時堆疊（run-time stack）與機器堆疊（machine stack），是電腦科學中儲存有關正在執行的子程式的訊息的堆疊。英文有時直接簡稱「堆疊」（the stack），但堆疊中不一定僅儲存子程式訊息。幾乎所有電腦程式都依賴於呼叫堆疊，而高階語言一般將呼叫堆疊的細節隱藏至後台。
呼叫堆疊最經常被用於存放子程式的返回位址。在呼叫任何子程式時，主程式都必須暫存子程式執行完畢後應該返回到的位址。因此，如果被呼叫的子程式還要呼叫其他的子程式，其自身的返回位址就必須存入呼叫堆疊，在其自身執行完畢後再行取回。在遞迴程式中，每一層次遞迴都必須在呼叫堆疊上增加一條位址，因此如果程式出現無限遞迴（或僅僅是過多的遞迴層次），呼叫堆疊就會產生堆疊溢位。
Remove ads
功能
呼叫堆疊的主要功能是存放返回位址。除此之外，呼叫堆疊還用於存放：
結構
呼叫堆疊由堆疊框（stack frame）組成，它們也叫做「活躍（activation）記錄」或「活躍訊框」。它們是機器依賴並且ABI依賴的資料結構，包含了次常式狀態資訊。每個堆疊框對應於一個次常式的仍未通過返回來完成的一次呼叫[1]。在堆疊頂部的堆疊框對應當前執行常式。例如，一個叫做DrawLine的次常式當前正在執行，它被次常式DrawSquare所呼叫，右側圖示中給出了呼叫堆疊的頂部狀況。
在堆疊框大小可以不同的時候，比如在不同的函式之間或在特定函式的多次呼叫之間，從堆疊彈出一個訊框不導致堆疊指標（stack pointer）減少固定大小。在函式返回之時，指標轉而被復原為影格指標（frame pointer），即這個函式被呼叫前最近的堆疊指標的值。每個堆疊框都包含一個影格指標，指向下面最近的訊框的頂部。堆疊指標是在所有呼叫之間共享的可變的暫存器。一個函式的給定一次呼叫的影格指標，是這個函式被呼叫前的堆疊指標的複製品[2]。
一個常式可以直接變更堆疊指標在堆疊框中為局部變數指定儲存空間，也可以執行入堆疊指令和出堆疊指令間接改變堆疊指標。在入堆疊指令自動遞增堆疊指標所指位址的呼叫堆疊中，在一個訊框之中的所有其他局部欄位的位置都可定義為，相對於影格指標即下面最近訊框的頂部的正數偏移量。在x86架構的呼叫約定下它們定義為，相對於影格指標RBP的負數偏移量。
出於某些目的，一個次常式的堆疊框和它的呼叫者的堆疊框可以視為有所交疊（overlap），交疊由從呼叫者傳遞給被呼叫者的參數值所在區域組成。在呼叫結束時清理參數值的責任由被呼叫者實行的情況下，比如Pascal式呼叫約定，交疊自然地劃分在被呼叫者堆疊框之中。在入堆疊指令自動遞增堆疊指標所指位址的呼叫堆疊中，呼叫者傳遞給一個常式的參數值的位置定義為，相對於影格指標即下面最近訊框的頂部的負數偏移量。在x86架構的呼叫約定下它們定義為，相對於影格指標RBP的正數偏移量。
在一些環境中，呼叫者將每個實際參數（argument）壓入堆疊之上，從而擴充了它自己堆疊框，接著呼叫被呼叫者。在其他的環境中，呼叫者在它的堆疊框的頂部有一個預先分配的區域，用來持有它要提供給其所呼叫的次常式的實際參數。這個區域有時稱為「出去（outgoing）實參區域」或「調出（callout）區域」，可以對應ALGOL 60的術語擬制塊。在這種途徑下，由編譯器計算出的這個區域的大小應當滿足任何被呼叫的次常式的最大所需。
Remove ads
支援巢狀次常式的程式語言在呼叫訊框中還擁有一個欄位，它指向最近的封裝這個被呼叫者的過程的「最新」活躍的堆疊框，也就是這個被呼叫者在詞法上的直接靜態範疇。這個欄位叫做「造訪連結」，由於它在動態和遞迴呼叫期間追蹤了靜態巢狀，也叫做「靜態連結」。為這個被呼叫者提供了同任何可能呼叫的其他常式一樣的一個常式，用來訪問在所有巢狀層級上封裝它的諸常式的局部資料。在內層函式不訪問在封裝中的任何非常數的局部資料的時候，造訪連結可以被最佳化掉，因為在這種情況比如純函式下，只通過實際參數和返回值來通訊。
某些架構為每個包圍層級都儲存一個連結，並非只提供給直接包圍者，所以訪問淺層資料的深層巢狀常式不需要遍歷多個連結，這種策略經常叫做「展示」（display）[3]。一些歷史上的電腦比如Electrologica X8和稍晚一些的Burroughs大型系統，有特殊的展示暫存器用來支援巢狀函式。針對最現代機器比如無處不在的x86處理器，編譯器及其最佳化方案在有需要的時候，可以簡單的在堆疊上為到所訪問包圍層級的這些指標預留一些字。
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）這個函式，並且不僅期望其中的變數不變動，而且期望整個呼叫序列的堆疊框都存在使得這個函式能再次返回。要解決這個問題，堆疊框可以在父指標樹結構中動態分配，並在不再有續體參照的時候，將其留作垃圾回收。這種類型的結構還解決了上行和下行的函式參數問題，因為在這種基底上很容易實現頭等詞法閉包。由堆疊框連結起來而實現的這種實際執行堆疊，也被稱為「麵條式堆疊」[4]，它包含了變數繫結和其他環境特徵。
Remove ads
安全性
在較底層語言（如組合語言與C語言中），程式控制訊息與資料可能一同被存入呼叫堆疊中，因此造成安全隱患，可能允許惡意程式通過堆疊緩衝區溢位（stack buffer overflow）來獲取程式的控制權。
參見
參照
延伸閱讀
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads