C語言/C++ 堆棧工作機(jī)制

前言

我們經(jīng)常會(huì)討論這樣的問題：什么時(shí)候數(shù)據(jù)存儲(chǔ)在堆棧 (Stack) 中，什么時(shí)候數(shù)據(jù)存儲(chǔ)在堆 (Heap) 中。我們知道，局部變量是存儲(chǔ)在堆棧中的；debug 時(shí)，查看堆?？梢灾篮瘮?shù)的調(diào)用順序；函數(shù)調(diào)用時(shí)傳遞參數(shù)，事實(shí)上是把參數(shù)壓入堆棧，聽起來，堆棧象一個(gè)大雜燴。那么，堆棧 (Stack) 到底是如何工作的呢？本文將詳解 C/C++ 堆棧的工作機(jī)制。閱讀時(shí)請(qǐng)注意以下幾點(diǎn)：

1）本文討論的編譯環(huán)境是 Visual C/C++，由于高級(jí)語言的堆棧工作機(jī)制大致相同，因此對(duì)其他編譯環(huán)境或高級(jí)語言如 C# 也有意義。

2）本文討論的堆棧，是指程序?yàn)槊總€(gè)線程分配的默認(rèn)堆棧，用以支持程序的運(yùn)行，而不是指程序員為了實(shí)現(xiàn)算法而自己定義的堆棧。

3)? 本文討論的平臺(tái)為 intel x86。

4）本文的主要部分將盡量避免涉及到匯編的知識(shí)，在本文最后可選章節(jié)，給出前面章節(jié)的反編譯代碼和注釋。

5）結(jié)構(gòu)化異常處理也是通過堆棧來實(shí)現(xiàn)的(當(dāng)你使用 try…catch 語句時(shí)，使用的就是? c++ 對(duì) windows 結(jié)構(gòu)化異常處理的擴(kuò)展)，但是關(guān)于結(jié)構(gòu)化異常處理的主題太復(fù)雜了，本文將不會(huì)涉及到。

從一些基本的知識(shí)和概念開始

1) 程序的堆棧是由處理器直接支持的。在 intel x86 的系統(tǒng)中，堆棧在內(nèi)存中是從高地址向低地址擴(kuò)展（這和自定義的堆棧從低地址向高地址擴(kuò)展不同），如下圖所示：

?因此，棧頂?shù)刂肥遣粩鄿p小的，越后入棧的數(shù)據(jù)，所處的地址也就越低。

2) 在 32 位系統(tǒng)中，堆棧每個(gè)數(shù)據(jù)單元的大小為 4 字節(jié)。小于等于 4 字節(jié)的數(shù)據(jù)，比如字節(jié)、字、雙字和布爾型，在堆棧中都是占 4 個(gè)字節(jié)的；大于 4 字節(jié)的數(shù)據(jù)在堆棧中占4字節(jié)整數(shù)倍的空間。

3) 和堆棧的操作相關(guān)的兩個(gè)寄存器是 EBP 寄存器和 ESP 寄存器的，本文中，你只需要把 EBP 和 ESP 理解成 2 個(gè)指針就可以了。ESP 寄存器總是指向堆棧的棧頂，執(zhí)行 PUSH 命令向堆棧壓入數(shù)據(jù)時(shí)，ESP減4，然后把數(shù)據(jù)拷貝到ESP指向的地址；執(zhí)行POP 命令時(shí)，首先把 ESP 指向的數(shù)據(jù)拷貝到內(nèi)存地址/寄存器中，然后 ESP 加 4。EBP 寄存器是用于訪問堆棧中的數(shù)據(jù)的，它指向堆棧中間的某個(gè)位置（具體位置后文會(huì)具體講解），函數(shù)的參數(shù)地址比 EBP 的值高，而函數(shù)的局部變量地址比 EBP 的值低，因此參數(shù)或局部變量總是通過 EBP 加減一定的偏移地址來訪問的，比如，要訪問函數(shù)的第一個(gè)參數(shù)為 EBP+8。

4) 堆棧中到底存儲(chǔ)了什么數(shù)據(jù)？包括了：函數(shù)的參數(shù)，函數(shù)的局部變量，寄存器的值（用以恢復(fù)寄存器），函數(shù)的返回地址以及用于結(jié)構(gòu)化異常處理的數(shù)據(jù)（當(dāng)函數(shù)中有 try…catch 語句時(shí)才有，本文不討論）。這些數(shù)據(jù)是按照一定的順序組織在一起的， 我們稱之為一個(gè)堆棧幀（Stack Frame）。一個(gè)堆棧幀對(duì)應(yīng)一次函數(shù)的調(diào)用。在函數(shù)開始時(shí)，對(duì)應(yīng)的堆棧幀已經(jīng)完整地建立了（所有的局部變量在函數(shù)幀建立時(shí)就已經(jīng)分配好空間了，而不是隨著函數(shù)的執(zhí)行而不斷創(chuàng)建和銷毀的）；在函數(shù)退出時(shí)，整個(gè)函數(shù)幀將被銷毀。

5) 在文中，我們把函數(shù)的調(diào)用者稱為 caller（調(diào)用者），被調(diào)用的函數(shù)稱為callee（被調(diào)用者）。之所以引入這個(gè)概念，是因?yàn)橐粋€(gè)函數(shù)幀的建立和清理，有些工作是由 Caller 完成的，有些則是由 Callee 完成的。

開始討論堆棧是如何工作的

我們來討論堆棧的工作機(jī)制。堆棧是用來支持函數(shù)的調(diào)用和執(zhí)行的，因此，我們下面將通過一組函數(shù)調(diào)用的例子來講解，看下面的代碼：

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;}

這段代碼本身并沒有實(shí)際的意義，我們只是用它來跟蹤堆棧。下面的章節(jié)我們來跟蹤堆棧的建立，堆棧的使用和堆棧的銷毀。

堆棧的建立

我們從main函數(shù)執(zhí)行的第一行代碼，即 int result=foo(3,4); 開始跟蹤。這時(shí) main 以及之前的函數(shù)對(duì)應(yīng)的堆棧幀已經(jīng)存在在堆棧中了，如下圖所示：

圖1

參數(shù)入棧?

當(dāng) foo 函數(shù)被調(diào)用，首先，caller（此時(shí)caller為main函數(shù)）把 foo 函數(shù)的兩個(gè)參數(shù)：a=3,b=4 壓入堆棧。參數(shù)入棧的順序是由函數(shù)的調(diào)用約定 (Calling Convention) 決定的，我們將在后面一個(gè)專門的章節(jié)來講解調(diào)用約定。一般來說，參數(shù)都是從右往左入棧的，因此，b=4 先壓入堆棧，a=3 后壓入，如圖：

圖2

返回地址入棧

我們知道，當(dāng)函數(shù)結(jié)束時(shí)，代碼要返回到上一層函數(shù)繼續(xù)執(zhí)行，那么，函數(shù)如何知道該返回到哪個(gè)函數(shù)的什么位置執(zhí)行呢？函數(shù)被調(diào)用時(shí)，會(huì)自動(dòng)把下一條指令的地址壓入堆棧，函數(shù)結(jié)束時(shí)，從堆棧讀取這個(gè)地址，就可以跳轉(zhuǎn)到該指令執(zhí)行了。如果當(dāng)前＂call foo＂指令的地址是 0x00171482 ,由于 call 指令占 5 個(gè)字節(jié)，那么下一個(gè)指令的地址為 0x00171487，0x00171487 將被壓入堆棧:

圖3

代碼跳轉(zhuǎn)到被調(diào)用函數(shù)執(zhí)行

返回地址入棧后，代碼跳轉(zhuǎn)到被調(diào)用函數(shù) foo 中執(zhí)行。到目前為止，堆棧幀的前一部分，是由 caller 構(gòu)建的；而在此之后，堆棧幀的其他部分是由 callee 來構(gòu)建。

EBP指針入棧

????

在 foo 函數(shù)中，首先將 EBP 寄存器的值壓入堆棧。因?yàn)榇藭r(shí) EBP 寄存器的值還是用于 main 函數(shù)的，用來訪問 main 函數(shù)的參數(shù)和局部變量的，因此需要將它暫存在堆棧中，在 foo 函數(shù)退出時(shí)恢復(fù)。同時(shí)，給 EBP 賦于新值。

1）將 EBP 壓入堆棧

2）把 ESP 的值賦給 EBP

圖4

????

這樣一來，我們很容易發(fā)現(xiàn)當(dāng)前EBP寄存器指向的堆棧地址就是 EBP 先前值的地址，你還會(huì)發(fā)現(xiàn)發(fā)現(xiàn)，EBP+4 的地址就是函數(shù)返回值的地址，EBP+8 就是函數(shù)的第一個(gè)參數(shù)的地址（第一個(gè)參數(shù)地址并不一定是 EBP+8，后文中將講到）。因此，通過 EBP 很容易查找函數(shù)是被誰調(diào)用的或者訪問函數(shù)的參數(shù)（或局部變量）。

為局部變量分配地址

接著，foo 函數(shù)將為局部變量分配地址。程序并不是將局部變量一個(gè)個(gè)壓入堆棧的，而是將 ESP 減去某個(gè)值，直接為所有的局部變量分配空間，比如在 foo 函數(shù)中有 ESP=ESP-0x00E4，（根據(jù)燭秋兄在其他編譯環(huán)境上的測(cè)試，也可能使用 push 命令分配地址，本質(zhì)上并沒有差別，特此說明）如圖所示：

圖5

?????

奇怪的是，在 debug 模式下，編譯器為局部變量分配的空間遠(yuǎn)遠(yuǎn)大于實(shí)際所需，而且局部變量之間的地址不是連續(xù)的（據(jù)我觀察，總是間隔 8 個(gè)字節(jié)）如下圖所示：

?

圖6

????

我還不知道編譯器為什么這么設(shè)計(jì)，或許是為了在堆棧中插入調(diào)試數(shù)據(jù)，不過這無礙我們今天的討論。

通用寄存器入棧

?????

最后，將函數(shù)中使用到的通用寄存器入棧，暫存起來，以便函數(shù)結(jié)束時(shí)恢復(fù)。在 foo 函數(shù)中用到的通用寄存器是 EBX，ESI，EDI，將它們壓入堆棧，如圖所示：

圖7

???

至此，一個(gè)完整的堆棧幀建立起來了。

堆棧特性分析

??

上一節(jié)中，一個(gè)完整的堆棧幀已經(jīng)建立起來，現(xiàn)在函數(shù)可以開始正式執(zhí)行代碼了。本節(jié)我們對(duì)堆棧的特性進(jìn)行分析，有助于了解函數(shù)與堆棧幀的依賴關(guān)系。

1）一個(gè)完整的堆棧幀建立起來后，在函數(shù)執(zhí)行的整個(gè)生命周期中，它的結(jié)構(gòu)和大小都是保持不變的；不論函數(shù)在什么時(shí)候被誰調(diào)用，它對(duì)應(yīng)的堆棧幀的結(jié)構(gòu)也是一定的。

2）在 A 函數(shù)中調(diào)用B函數(shù)，對(duì)應(yīng)的，是在A函數(shù)對(duì)應(yīng)的堆棧幀“下方”建立 B 函數(shù)的堆棧幀。例如在 foo 函數(shù)中調(diào)用 foo1 函數(shù)，foo1 函數(shù)的堆棧幀將在 foo 函數(shù)的堆棧幀下方建立。如下圖所示：

圖8?

?

3）函數(shù)用 EBP 寄存器來訪問參數(shù)和局部變量。我們知道，參數(shù)的地址總是比 EBP 的值高，而局部變量的地址總是比 EBP 的值低。而在特定的堆棧幀中，每個(gè)參數(shù)或局部變量相對(duì)于 EBP 的地址偏移總是固定的。因此函數(shù)對(duì)參數(shù)和局部變量的的訪問是通過 EBP 加上某個(gè)偏移量來訪問的。比如，在 foo 函數(shù)中，EBP+8 為第一個(gè)參數(shù)的地址，EBP-8 為第一個(gè)局部變量的地址。

4）如果仔細(xì)思考，我們很容易發(fā)現(xiàn) EBP 寄存器還有一個(gè)非常重要的特性，請(qǐng)看下圖中：

圖9

???

我們發(fā)現(xiàn)，EBP 寄存器總是指向先前的 EBP，而先前的 EBP 又指向先前的先前的 EBP，這樣就在堆棧中形成了一個(gè)鏈表！這個(gè)特性有什么用呢，我們知道 EBP+4 地址存儲(chǔ)了函數(shù)的返回地址，通過該地址我們可以知道當(dāng)前函數(shù)的上一級(jí)函數(shù)（通過在符號(hào)文件中查找距該函數(shù)返回地址最近的函數(shù)地址，該函數(shù)即當(dāng)前函數(shù)的上一級(jí)函數(shù)），以此類推，我們就可以知道當(dāng)前線程整個(gè)的函數(shù)調(diào)用順序。事實(shí)上，調(diào)試器正是這么做的，這也就是為什么調(diào)試時(shí)我們查看函數(shù)調(diào)用順序時(shí)總是說“查看堆?！绷?。

返回值是如何傳遞的

堆棧幀建立起后，函數(shù)的代碼真正地開始執(zhí)行，它會(huì)操作堆棧中的參數(shù)，操作堆棧中的局部變量，甚至在堆（Heap）上創(chuàng)建對(duì)象，balabala….，終于函數(shù)完成了它的工作，有些函數(shù)需要將結(jié)果返回給它的上一層函數(shù)，這是怎么做的呢？

????

首先，caller 和 callee 在這個(gè)問題上要有一個(gè)“約定”，由于 caller 是不知道 callee 內(nèi)部是如何執(zhí)行的，因此 caller 需要從 callee 的函數(shù)聲明就可以知道應(yīng)該從什么地方取得返回值。同樣的，callee 不能隨便把返回值放在某個(gè)寄存器或者內(nèi)存中而指望Caller 能夠正確地獲得的，它應(yīng)該根據(jù)函數(shù)的聲明，按照“約定”把返回值放在正確的”地方“。下面我們來講解這個(gè)“約定”：?

1）首先，如果返回值等于 4 字節(jié)，函數(shù)將把返回值賦予EAX寄存器，通過 EAX 寄存器返回。例如返回值是字節(jié)、字、雙字、布爾型、指針等類型，都通過 EAX 寄存器返回。

2）如果返回值等于 8 字節(jié)，函數(shù)將把返回值賦予 EAX 和 EDX 寄存器，通過 EAX 和 EDX 寄存器返回，EDX 存儲(chǔ)高位 4 字節(jié)，EAX存儲(chǔ)低位 4 字節(jié)。例如返回值類型為 __int64 或者 8 字節(jié)的結(jié)構(gòu)體通過 EAX 和 EDX 返回。

3)? 如果返回值為 double 或 float 型，函數(shù)將把返回值賦予浮點(diǎn)寄存器，通過浮點(diǎn)寄存器返回。

4）如果返回值是一個(gè)大于 8 字節(jié)的數(shù)據(jù)，將如何傳遞返回值呢？這是一個(gè)比較麻煩的問題，我們將詳細(xì)講解：

我們修改 foo 函數(shù)的定義如下并將它的代碼做適當(dāng)?shù)男薷模?/span>

MyStruct foo(`int a, int b)`{ ...}

MyStruct定義為：

struct MyStruct{ int value1; __int64 value2; bool value3;};

?這時(shí)，在調(diào)用 foo 函數(shù)時(shí)參數(shù)的入棧過程會(huì)有所不同，如下圖所示：

圖10

????

caller 會(huì)在壓入最左邊的參數(shù)后，再壓入一個(gè)指針，我們姑且叫它ReturnValuePointer，ReturnValuePointer 指向 caller 局部變量區(qū)的一塊未命名的地址，這塊地址將用來存儲(chǔ) callee 的返回值。函數(shù)返回時(shí)，callee 把返回值拷貝到ReturnValuePointer 指向的地址中，然后把 ReturnValuePointer 的地址賦予 EAX 寄存器。函數(shù)返回后，caller 通過 EAX 寄存器找到 ReturnValuePointer，然后通過ReturnValuePointer 找到返回值，最后，caller 把返回值拷貝到負(fù)責(zé)接收的局部變量上（如果接收返回值的話）。

????

你或許會(huì)有這樣的疑問，函數(shù)返回后，對(duì)應(yīng)的堆棧幀已經(jīng)被銷毀，而ReturnValuePointer 是在該堆棧幀中，不也應(yīng)該被銷毀了嗎？對(duì)的，堆棧幀是被銷毀了，但是程序不會(huì)自動(dòng)清理其中的值，因此 ReturnValuePointer 中的值還是有效的。

堆棧幀的銷毀

???

當(dāng)函數(shù)將返回值賦予某些寄存器或者拷貝到堆棧的某個(gè)地方后，函數(shù)開始清理堆棧幀，準(zhǔn)備退出。堆棧幀的清理順序和堆棧建立的順序剛好相反：（堆棧幀的銷毀過程就不一一畫圖說明了）

??? 1）如果有對(duì)象存儲(chǔ)在堆棧幀中，對(duì)象的析構(gòu)函數(shù)會(huì)被函數(shù)調(diào)用。

??? 2）從堆棧中彈出先前的通用寄存器的值，恢復(fù)通用寄存器。

??? 3）ESP 加上某個(gè)值，回收局部變量的地址空間（加上的值和堆棧幀建立時(shí)分配給局部變量的地址大小相同）。

??? 4）從堆棧中彈出先前的 EBP 寄存器的值，恢復(fù) EBP 寄存器。

??? 5）從堆棧中彈出函數(shù)的返回地址，準(zhǔn)備跳轉(zhuǎn)到函數(shù)的返回地址處繼續(xù)執(zhí)行。

??? 6）ESP 加上某個(gè)值，回收所有的參數(shù)地址。

前面 1-5 條都是由 callee 完成的。而第 6 條，參數(shù)地址的回收，是由 caller 或者callee 完成是由函數(shù)使用的調(diào)用約定（calling convention ）來決定的。下面的小節(jié)我們就來講解函數(shù)的調(diào)用約定。

函數(shù)的調(diào)用約定（calling convention）

函數(shù)的調(diào)用約定 (calling convention) 指的是進(jìn)入函數(shù)時(shí)，函數(shù)的參數(shù)是以什么順序壓入堆棧的，函數(shù)退出時(shí)，又是由誰（Caller還是Callee）來清理堆棧中的參數(shù)。有 2 個(gè)辦法可以指定函數(shù)使用的調(diào)用約定：

1）在函數(shù)定義時(shí)加上修飾符來指定，如

void __thiscall mymethod();{ ...}

2）在 VS 工程設(shè)置中為工程中定義的所有的函數(shù)指定默認(rèn)的調(diào)用約定：在工程的主菜單打開 Project|Project Property|Configuration Properties|C/C++|Advanced|Calling Convention，選擇調(diào)用約定（注意：這種做法對(duì)類成員函數(shù)無效）。

常用的調(diào)用約定有以下3種：

1）__cdecl。這是 VC 編譯器默認(rèn)的調(diào)用約定。其規(guī)則是：參數(shù)從右向左壓入堆棧，函數(shù)退出時(shí)由 caller 清理堆棧中的參數(shù)。這種調(diào)用約定的特點(diǎn)是支持可變數(shù)量的參數(shù)，比如 printf 方法。由于 callee 不知道caller到底將多少參數(shù)壓入堆棧，因此callee 就沒有辦法自己清理堆棧，所以只有函數(shù)退出之后，由 caller 清理堆棧，因?yàn)?caller 總是知道自己傳入了多少參數(shù)。

2）__stdcall。所有的 Windows API 都使用 __stdcall。其規(guī)則是：參數(shù)從右向左壓入堆棧，函數(shù)退出時(shí)由 callee 自己清理堆棧中的參數(shù)。由于參數(shù)是由 callee 自己清理的，所以 __stdcall 不支持可變數(shù)量的參數(shù)。

3)?__thiscall。類成員函數(shù)默認(rèn)使用的調(diào)用約定。其規(guī)則是：參數(shù)從右向左壓入堆棧，x86 構(gòu)架下 this 指針通過 ECX 寄存器傳遞，函數(shù)退出時(shí)由 callee 清理堆棧中的參數(shù)，x86構(gòu)架下this指針通過ECX寄存器傳遞。同樣不支持可變數(shù)量的參數(shù)。如果顯式地把類成員函數(shù)聲明為使用__cdecl或者_(dá)_stdcall，那么，將采用__cdecl或者_(dá)_stdcall的規(guī)則來壓棧和出棧，而this指針將作為函數(shù)的第一個(gè)參數(shù)最后壓入堆棧，而不是使用ECX寄存器來傳遞了。

反編譯代碼的跟蹤（不熟悉匯編可跳過）

以下代碼為和 foo 函數(shù)對(duì)應(yīng)的堆棧幀建立相關(guān)的代碼的反編譯代碼，我將逐行給出注釋，可對(duì)照前文中對(duì)堆棧的描述：

main 函數(shù)中 int result=foo(3,4); 的反匯編：

008A147E push 4 //b=4 壓入堆棧008A1480 push 3 //a=3 壓入堆棧,到達(dá)圖2的狀態(tài)008A1482 call foo (8A10F5h) //函數(shù)返回值入棧,轉(zhuǎn)入foo中執(zhí)行,到達(dá)圖3的狀態(tài)008A1487 add esp,8 //foo返回,由于采用__cdecl,由Caller清理參數(shù)008A148A mov dword ptr [result],eax //返回值保存在EAX中,把EAX賦予result變量

下面是 foo 函數(shù)代碼正式執(zhí)行前和執(zhí)行后的反匯編代碼

008A13F0 push ebp //把ebp壓入堆棧008A13F1 mov ebp,esp //ebp指向先前的ebp,到達(dá)圖4的狀態(tài)008A13F3 sub esp,0E4h //為局部變量分配0E4字節(jié)的空間,到達(dá)圖5的狀態(tài)008A13F9 push ebx //壓入EBX008A13FA push esi //壓入ESI008A13FB push edi //壓入EDI,到達(dá)圖7的狀態(tài)008A13FC lea edi,[ebp-0E4h] //以下4行把局部變量區(qū)初始化為每個(gè)字節(jié)都等于cch008A1402 mov ecx,39h008A1407 mov eax,0CCCCCCCCh008A140C rep stos dword ptr es:[edi]...... //省略代碼執(zhí)行N行......008A1436 pop edi //恢復(fù)EDI008A1437 pop esi //恢復(fù)ESI008A1438 pop ebx //恢復(fù)EBX008A1439 add esp,0E4h //回收局部變量地址空間008A143F cmp ebp,esp //以下3行為Runtime Checking,檢查ESP和EBP是否一致008A1441 call @ILT+330(__RTC_CheckEsp) (8A114Fh)008A1446 mov esp,ebp008A1448 pop ebp //恢復(fù)EBP008A1449 ret //彈出函數(shù)返回地址，跳轉(zhuǎn)到函數(shù)返回地址執(zhí)行 //(__cdecl調(diào)用約定,Callee未清理參數(shù))

參考

Debug Tutorial Part 2: The Stack

Intel匯編語言程序設(shè)計(jì)(第四版)?第8章