我們經常會讨論這樣的問題:什麼時候資料存儲在堆棧(Stack)中,什麼時候資料存儲在堆(Heap)中。我們知道,局部變量是存儲在堆棧中的;debug時,檢視堆棧可以知道函數的調用順序;函數調用時傳遞參數,事實上是把參數壓入堆棧,聽起來,堆棧象一個大雜燴。那麼,堆棧(Stack)到底是如何工作的呢? 本文将詳解C/C++堆棧的工作機制。閱讀時請注意以下幾點:
1)本文讨論的編譯環境是 Visual C/C++,由于進階語言的堆棧工作機制大緻相同,是以對其他編譯環境或進階語言如C#也有意義。
2)本文讨論的堆棧,是指程式為每個線程配置設定的預設堆棧,用以支援程式的運作,而不是指程式員為了實作算法而自己定義的堆棧。
3) 本文讨論的平台為intel x86。
4)本文的主要部分将盡量避免涉及到彙編的知識,在本文最後可選章節,給出前面章節的反編譯代碼和注釋。
5)結構化異常處理也是通過堆棧來實作的(當你使用try…catch語句時,使用的就是c++對windows結構化異常處理的擴充),但是關于結構化異常處理的主題太複雜了,本文将不會涉及到。
從一些基本的知識和概念開始
1) 程式的堆棧是由處理器直接支援的。在intel x86的系統中,堆棧在記憶體中是從高位址向低位址擴充(這和自定義的堆棧從低位址向高位址擴充不同),如下圖所示:
是以,棧頂位址是不斷減小的,越後入棧的資料,所處的位址也就越低。
2) 在32位系統中,堆棧每個資料單元的大小為4位元組。小于等于4位元組的資料,比如位元組、字、雙字和布爾型,在堆棧中都是占4個位元組的;大于4位元組的資料在堆棧中占4位元組整數倍的空間。
3) 和堆棧的操作相關的兩個寄存器是EBP寄存器和ESP寄存器的,本文中,你隻需要把EBP和ESP了解成2個指針就可以了。ESP寄存器總是指向堆棧的棧頂,執行PUSH指令向堆棧壓入資料時,ESP減4,然後把資料拷貝到ESP指向的位址;執行POP指令時,首先把ESP指向的資料拷貝到記憶體位址/寄存器中,然後ESP加4。EBP寄存器是用于通路堆棧中的資料的,它指向堆棧中間的某個位置(具體位置後文會具體講解),函數的參數位址比EBP的值高,而函數的局部變量位址比EBP的值低,是以參數或局部變量總是通過EBP加減一定的偏移位址來通路的,比如,要通路函數的第一個參數為EBP+8。
4) 堆棧中到底存儲了什麼資料? 包括了:函數的參數,函數的局部變量,寄存器的值(用以恢複寄存器),函數的傳回位址以及用于結構化異常處理的資料(當函數中有try…catch語句時才有,本文不讨論)。這些資料是按照一定的順序組織在一起的,我們稱之為一個堆棧幀(Stack Frame)。一個堆棧幀對應一次函數的調用。在函數開始時,對應的堆棧幀已經完整地建立了(所有的局部變量在函數幀建立時就已經配置設定好空間了,而不是随着函數的執行而不斷建立和銷毀的);在函數退出時,整個函數幀将被銷毀。
5) 在文中,我們把函數的調用者稱為caller(調用者),被調用的函數稱為callee(被調用者)。之是以引入這個概念,是因為一個函數幀的建立和清理,有些工作是由Caller完成的,有些則是由Callee完成的。
開始讨論堆棧是如何工作的
我們來讨論堆棧的工作機制。堆棧是用來支援函數的調用和執行的,是以,我們下面将通過一組函數調用的例子來講解,看下面的代碼:
int foo1(int m, int n)
{
int p=m*n;
return p;
}
int foo(int a, int b)
{
int c=a+1;
int d=b+1;
int e=foo1(c,d);
return e;
}
int main()
{
int result=foo(3,4);
return 0;
}
這段代碼本身并沒有實際的意義,我們隻是用它來跟蹤堆棧。下面的章節我們來跟蹤堆棧的建立,堆棧的使用和堆棧的銷毀。
堆棧的建立
我們從main函數執行的第一行代碼,即int result=foo(3,4); 開始跟蹤。這時main以及之前的函數對應的堆棧幀已經存在在堆棧中了,如下圖所示:
圖1
參數入棧
當foo函數被調用,首先,caller(此時caller為main函數)把foo函數的兩個參數:a=3,b=4壓入堆棧。參數入棧的順序是由函數的調用約定(Calling Convention)決定的,我們将在後面一個專門的章節來講解調用約定。一般來說,參數都是從右往左入棧的,是以,b=4先壓入堆棧,a=3後壓入,如圖:
圖2
傳回位址入棧
我們知道,當函數結束時,代碼要傳回到上一層函數繼續執行,那麼,函數如何知道該傳回到哪個函數的什麼位置執行呢?函數被調用時,會自動把下一條指令的位址壓入堆棧,函數結束時,從堆棧讀取這個位址,就可以跳轉到該指令執行了。如果目前"call foo"指令的位址是0x00171482,由于call指令占5個位元組,那麼下一個指令的位址為0x00171487,0x00171487将被壓入堆棧:
圖3
代碼跳轉到被調用函數執行
傳回位址入棧後,代碼跳轉到被調用函數foo中執行。到目前為止,堆棧幀的前一部分,是由caller建構的;而在此之後,堆棧幀的其他部分是由callee來建構。
EBP指針入棧
在foo函數中,首先将EBP寄存器的值壓入堆棧。因為此時EBP寄存器的值還是用于main函數的,用來通路main函數的參數和局部變量的,是以需要将它暫存在堆棧中,在foo函數退出時恢複。同時,給EBP賦于新值。
1)将EBP壓入堆棧
2)把ESP的值賦給EBP
圖4
這樣一來,我們很容易發現目前EBP寄存器指向的堆棧位址就是EBP先前值的位址,你還會發現發現,EBP+4的位址就是函數傳回值的位址,EBP+8就是函數的第一個參數的位址(第一個參數位址并不一定是EBP+8,後文中将講到)。是以,通過EBP很容易查找函數是被誰調用的或者通路函數的參數(或局部變量)。
為局部變量配置設定位址
接着,foo函數将為局部變量配置設定位址。程式并不是将局部變量一個個壓入堆棧的,而是将ESP減去某個值,直接為所有的局部變量配置設定空間,比如在foo函數中有ESP=ESP-0x00E4,(根據燭秋兄在其他編譯環境上的測試,也可能使用push指令配置設定位址,本質上并沒有差别,特此說明)如圖所示:
圖5
奇怪的是,在debug模式下,編譯器為局部變量配置設定的空間遠遠大于實際所需,而且局部變量之間的位址不是連續的(據我觀察,總是間隔8個位元組)如下圖所示:
圖6
我還不知道編譯器為什麼這麼設計,或許是為了在堆棧中插入調試資料,不過這無礙我們今天的讨論。
通用寄存器入棧
最後,将函數中使用到的通用寄存器入棧,暫存起來,以便函數結束時恢複。在foo函數中用到的通用寄存器是EBX,ESI,EDI,将它們壓入堆棧,如圖所示:
圖7
至此,一個完整的堆棧幀建立起來了。
堆棧特性分析
上一節中,一個完整的堆棧幀已經建立起來,現在函數可以開始正式執行代碼了。本節我們對堆棧的特性進行分析,有助于了解函數與堆棧幀的依賴關系。
1)一個完整的堆棧幀建立起來後,在函數執行的整個生命周期中,它的結構和大小都是保持不變的;不論函數在什麼時候被誰調用,它對應的堆棧幀的結構也是一定的。
2)在A函數中調用B函數,對應的,是在A函數對應的堆棧幀“下方”建立B函數的堆棧幀。例如在foo函數中調用foo1函數,foo1函數的堆棧幀将在foo函數的堆棧幀下方建立。如下圖所示:
圖8
3)函數用EBP寄存器來通路參數和局部變量。我們知道,參數的位址總是比EBP的值高,而局部變量的位址總是比EBP的值低。而在特定的堆棧幀中,每個參數或局部變量相對于EBP的位址偏移總是固定的。是以函數對參數和局部變量的的通路是通過EBP加上某個偏移量來通路的。比如,在foo函數中,EBP+8為第一個參數的位址,EBP-8為第一個局部變量的位址。
4)如果仔細思考,我們很容易發現EBP寄存器還有一個非常重要的特性,請看下圖中:
圖9
我們發現,EBP寄存器總是指向先前的EBP,而先前的EBP又指向先前的先前的EBP,這樣就在堆棧中形成了一個連結清單!這個特性有什麼用呢,我們知道EBP+4位址存儲了函數的傳回位址,通過該位址我們可以知道目前函數的上一級函數(通過在符号檔案中查找距該函數傳回位址最近的函數位址,該函數即目前函數的上一級函數),以此類推,我們就可以知道目前線程整個的函數調用順序。事實上,調試器正是這麼做的,這也就是為什麼調試時我們檢視函數調用順序時總是說“檢視堆棧”了。
傳回值是如何傳遞的
堆棧幀建立起後,函數的代碼真正地開始執行,它會操作堆棧中的參數,操作堆棧中的局部變量,甚至在堆(Heap)上建立對象,balabala….,終于函數完成了它的工作,有些函數需要将結果傳回給它的上一層函數,這是怎麼做的呢?
首先,caller和callee在這個問題上要有一個“約定”,由于caller是不知道callee内部是如何執行的,是以caller需要從callee的函數聲明就可以知道應該從什麼地方取得傳回值。同樣的,callee不能随便把傳回值放在某個寄存器或者記憶體中而指望Caller能夠正确地獲得的,它應該根據函數的聲明,按照“約定”把傳回值放在正确的”地方“。下面我們來講解這個“約定”:
1)首先,如果傳回值等于4位元組,函數将把傳回值賦予EAX寄存器,通過EAX寄存器傳回。例如傳回值是位元組、字、雙字、布爾型、指針等類型,都通過EAX寄存器傳回。
2)如果傳回值等于8位元組,函數将把傳回值賦予EAX和EDX寄存器,通過EAX和EDX寄存器傳回,EDX存儲高位4位元組,EAX存儲低位4位元組。例如傳回值類型為__int64或者8位元組的結構體通過EAX和EDX傳回。
3) 如果傳回值為double或float型,函數将把傳回值賦予浮點寄存器,通過浮點寄存器傳回。
4)如果傳回值是一個大于8位元組的資料,将如何傳遞傳回值呢?這是一個比較麻煩的問題,我們将詳細講解:
我們修改foo函數的定義如下并将它的代碼做适當的修改:
MyStruct foo(int a, int b)
{
...
}
MyStruct定義為:
struct MyStruct
{
int value1;
__int64 value2;
bool value3;
};
這時,在調用foo函數時參數的入棧過程會有所不同,如下圖所示:
圖10
caller會在壓入最左邊的參數後,再壓入一個指針,我們姑且叫它ReturnValuePointer,ReturnValuePointer指向caller局部變量區的一塊未命名的位址,這塊位址将用來存儲callee的傳回值。函數傳回時,callee把傳回值拷貝到ReturnValuePointer指向的位址中,然後把ReturnValuePointer的位址賦予EAX寄存器。函數傳回後,caller通過EAX寄存器找到ReturnValuePointer,然後通過ReturnValuePointer找到傳回值,最後,caller把傳回值拷貝到負責接收的局部變量上(如果接收傳回值的話)。
你或許會有這樣的疑問,函數傳回後,對應的堆棧幀已經被銷毀,而ReturnValuePointer是在該堆棧幀中,不也應該被銷毀了嗎?對的,堆棧幀是被銷毀了,但是程式不會自動清理其中的值,是以ReturnValuePointer中的值還是有效的。
堆棧幀的銷毀
當函數将傳回值賦予某些寄存器或者拷貝到堆棧的某個地方後,函數開始清理堆棧幀,準備退出。堆棧幀的清理順序和堆棧建立的順序剛好相反:(堆棧幀的銷毀過程就不一一畫圖說明了)
1)如果有對象存儲在堆棧幀中,對象的析構函數會被函數調用。
2)從堆棧中彈出先前的通用寄存器的值,恢複通用寄存器。
3)ESP加上某個值,回收局部變量的位址空間(加上的值和堆棧幀建立時配置設定給局部變量的位址大小相同)。
4)從堆棧中彈出先前的EBP寄存器的值,恢複EBP寄存器。
5)從堆棧中彈出函數的傳回位址,準備跳轉到函數的傳回位址處繼續執行。
6)ESP加上某個值,回收所有的參數位址。
前面1-5條都是由callee完成的。而第6條,參數位址的回收,是由caller或者callee完成是由函數使用的調用約定(calling convention )來決定的。下面的小節我們就來講解函數的調用約定。
函數的調用約定(calling convention)
函數的調用約定(calling convention)指的是進入函數時,函數的參數是以什麼順序壓入堆棧的,函數退出時,又是由誰(Caller還是Callee)來清理堆棧中的參數。有2個辦法可以指定函數使用的調用約定:
1)在函數定義時加上修飾符來指定,如
1
2
3
4
void __thiscall mymethod();
{
...
}
2)在VS工程設定中為工程中定義的所有的函數指定預設的調用約定:在工程的主菜單打開Project|Project Property|Configuration Properties|C/C++|Advanced|Calling Convention,選擇調用約定(注意:這種做法對類成員函數無效)。
常用的調用約定有以下3種:
1)__cdecl。這是VC編譯器預設的調用約定。其規則是:參數從右向左壓入堆棧,函數退出時由caller清理堆棧中的參數。這種調用約定的特點是支援可變數量的參數,比如printf方法。由于callee不知道caller到底将多少參數壓入堆棧,是以callee就沒有辦法自己清理堆棧,是以隻有函數退出之後,由caller清理堆棧,因為caller總是知道自己傳入了多少參數。
2)__stdcall。所有的Windows API都使用__stdcall。其規則是:參數從右向左壓入堆棧,函數退出時由callee自己清理堆棧中的參數。由于參數是由callee自己清理的,是以__stdcall不支援可變數量的參數。
3) __thiscall。類成員函數預設使用的調用約定。其規則是:參數從右向左壓入堆棧,x86構架下this指針通過ECX寄存器傳遞,函數退出時由callee清理堆棧中的參數,x86構架下this指針通過ECX寄存器傳遞。同樣不支援可變數量的參數。如果顯式地把類成員函數聲明為使用__cdecl或者__stdcall,那麼,将采用__cdecl或者__stdcall的規則來壓棧和出棧,而this指針将作為函數的第一個參數最後壓入堆棧,而不是使用ECX寄存器來傳遞了。
反編譯代碼的跟蹤(不熟悉彙編可跳過)
以下代碼為和foo函數對應的堆棧幀建立相關的代碼的反編譯代碼,我将逐行給出注釋,可對照前文中對堆棧的描述:
main函數中 int result=foo(3,4); 的反彙編:
1
2
3
4
5
008A147E push 4 //b=4 壓入堆棧
008A1480 push 3 //a=3 壓入堆棧,到達圖2的狀态
008A1482 call foo (8A10F5h) //函數傳回值入棧,轉入foo中執行,到達圖3的狀态
008A1487 add esp,8 //foo傳回,由于采用__cdecl,由Caller清理參數
008A148A mov dword ptr [result],eax //傳回值儲存在EAX中,把EAX賦予result變量
下面是foo函數代碼正式執行前和執行後的反彙編代碼
008A13F0 push ebp //把ebp壓入堆棧
008A13F1 mov ebp,esp //ebp指向先前的ebp,到達圖4的狀态
008A13F3 sub esp,0E4h //為局部變量配置設定0E4位元組的空間,到達圖5的狀态
008A13F9 push ebx //壓入EBX
008A13FA push esi //壓入ESI
008A13FB push edi //壓入EDI,到達圖7的狀态
008A13FC lea edi,[ebp-0E4h] //以下4行把局部變量區初始化為每個位元組都等于cch
008A1402 mov ecx,39h
008A1407 mov eax,0CCCCCCCCh
008A140C rep stos dword ptr es:[edi]
...... //省略代碼執行N行
......
008A1436 pop edi //恢複EDI
008A1437 pop esi //恢複ESI
008A1438 pop ebx //恢複EBX
008A1439 add esp,0E4h //回收局部變量位址空間
008A143F cmp ebp,esp //以下3行為Runtime Checking,檢查ESP和EBP是否一緻
008A1441 call @ILT+330(__RTC_CheckEsp) (8A114Fh)
008A1446 mov esp,ebp
008A1448 pop ebp //恢複EBP
008A1449 ret //彈出函數傳回位址,跳轉到函數傳回位址執行 //(__cdecl調用約定,Callee未清理參數)