簡(jiǎn)介
編程語(yǔ)言離不開函數(shù)鞠评，函數(shù)是對(duì)一段代碼的封裝脱茉，往往實(shí)現(xiàn)了某個(gè)特定的功能剪芥，在程序中可以多次調(diào)用這個(gè)函數(shù)。稍有編程經(jīng)驗(yàn)的同學(xué)都知道琴许，函數(shù)是由棧實(shí)現(xiàn)的税肪，調(diào)用對(duì)應(yīng)入棧，退出對(duì)應(yīng)出棧虚吟。在寫遞歸函數(shù)的時(shí)候寸认，如果遞歸層次太深會(huì)出現(xiàn)棧溢出（StackOverFlow）的錯(cuò)誤。
"函數(shù)棧"包含了對(duì)函數(shù)調(diào)用的基本理解串慰，但是從細(xì)節(jié)來(lái)看偏塞，還有很多疑問(wèn)，例如：
- 函數(shù)的棧是如何開辟的邦鲫？
- 如何傳入?yún)?shù)灸叼？
- 返回值是如何得到的？
本文以 C 語(yǔ)言為例庆捺，從內(nèi)存布局古今、匯編代碼的角度來(lái)分析函數(shù)棧的實(shí)現(xiàn)原理。
Linux 進(jìn)程內(nèi)存布局
當(dāng)程序被執(zhí)行的時(shí)候滔以，Linux 會(huì)為其在內(nèi)存中分配相應(yīng)的空間以支撐程序的運(yùn)行捉腥，如下圖所示。
在虛擬內(nèi)存中你画，內(nèi)存空間被分為多個(gè)區(qū)域抵碟。代碼指令保存在文本段桃漾，已初始化的全局變量 global 保存在數(shù)據(jù)段，程序運(yùn)行中動(dòng)態(tài)申請(qǐng)的內(nèi)存malloc(10 * char())放在堆中拟逮，而函數(shù)執(zhí)行的時(shí)候則在棧中開辟空間運(yùn)行撬统。例如main函數(shù)便占有一個(gè)函數(shù)棧，其中的變量i和ip都保存在main的椂仄空間中恋追。
函數(shù)的棧空間有個(gè)名字叫做 棧幀罚屋，下面就具體了解一下棧幀苦囱。
棧幀
下圖是棧的結(jié)構(gòu)。圖中右側(cè)是椘⒚停空間沿彭，其中有多個(gè)棧幀。從上往下由較早的棧幀到較新的棧幀尖滚，由于棧是從高地址往低地址生長(zhǎng)的喉刘，所以最新的棧永遠(yuǎn)在最下面，即棧頂漆弄。
圖中有兩個(gè)畫出了具體結(jié)構(gòu)的棧幀睦裳，分別是函數(shù) A 和函數(shù) B。函數(shù) A 的棧幀最上面有一塊省略號(hào)標(biāo)識(shí)的區(qū)域撼唾，其中保存的是上一個(gè)棧幀的寄存器值以及函數(shù) A 自己內(nèi)部創(chuàng)建的局部變量廉邑。下面的參數(shù) n 到參數(shù) 1 則是函數(shù) A 要傳給函數(shù) B 的調(diào)用參數(shù)。那么函數(shù) B 如何獲鹊构取蛛蒙？答案是用寄存器。
CPU 計(jì)算時(shí)會(huì)把很多變量放在寄存器中渤愁，根據(jù)硬件體系的不同牵祟，寄存器數(shù)量和作用也不同。一般在 x86 32位中抖格，寄存器 %esp 保存了棧指針的值诺苹，也就是棧頂，而 %ebp 作為當(dāng)前棧幀的幀指針雹拄，也就是當(dāng)前棧幀的底部收奔，所以通過(guò) %esp 和 %ebp 就可以知道當(dāng)前棧幀的頭跟尾。除了這兩個(gè)寄存器滓玖，還有其它一些通用寄存器（%eax坪哄、%edx等），用于保存程序執(zhí)行的臨時(shí)值。
了解了寄存器的基本知識(shí)后翩肌，下面我們就可以知道函數(shù) B 如何獲取到函數(shù) A 傳給它的參數(shù)了饰剥。參數(shù) 1 的地址是 %ebp + 8，參數(shù) 2 的地址是 %ebp + 12摧阅，參數(shù) n 的地址是 %ebp + 4 + 4 * n。相信大家已經(jīng)看明白绷蹲，通過(guò)幀指針往上找就可以取得這些參數(shù)棒卷，而這些參數(shù)之所以在這里當(dāng)然是函數(shù) A 預(yù)先準(zhǔn)備好的，關(guān)于這一點(diǎn)下文會(huì)有例子祝钢。
另外在所有參數(shù)的最下面保存著 返回地址比规，這個(gè)是在函數(shù) B 返回之后接下來(lái)要執(zhí)行的指令的地址。
看了函數(shù) A 之后拦英，再看看函數(shù) B蜒什。在函數(shù) B 的棧幀最上面是 被保存的 %ebp，這個(gè)指的是函數(shù) A 的幀指針疤估，畢竟 %ebp 這個(gè)寄存器就一個(gè)灾常，所以新的函數(shù)入棧的時(shí)候要先把老的保存起來(lái)，等函數(shù)出棧再恢復(fù)铃拇。在這個(gè)老的幀指針下面則是其它需要保存的寄存器變量以及函數(shù) B 自己內(nèi)部用到的局部變量钞瀑。再往下是 參數(shù)構(gòu)造區(qū)域，也就是函數(shù) B 即將調(diào)用另一個(gè)函數(shù)慷荔，在這里先把參數(shù)準(zhǔn)備好雕什。可以看出显晶，函數(shù) B 與函數(shù) A 的棧幀結(jié)構(gòu)是類似的贷岸。
了解了棧幀的理論之后，大家可能會(huì)覺得很抽象磷雇，下面結(jié)合具體實(shí)例來(lái)看棧幀從產(chǎn)生到消亡的過(guò)程偿警。
函數(shù)調(diào)用實(shí)例
下面圖是函數(shù) caller 的具體執(zhí)行過(guò)程，左邊是 C 代碼唯笙，中間是匯編碼户敬，右邊是對(duì)應(yīng)的棧幀。
我們一行一行的來(lái)分析睁本，看中間匯編碼尿庐，上面三行綠色的：
pushl %ebp // 保存舊的 %ebp
movl %esp, %ebp // 將 %ebp 設(shè)置為 %esp
subl $24, %esp // 將 %esp 減 24 開辟棧空間
這三行其實(shí)是為棧幀做準(zhǔn)備工作呢堰。第一行保存舊的 %ebp抄瑟，此時(shí)新的棧空間還沒有創(chuàng)建，但保存舊的 %ebp 的這一行空間將作為新棧幀的棧底皮假，也就是幀指針鞋拟，因此第二行將棧指針 %esp（永遠(yuǎn)指向棧頂）的值設(shè)置到 %ebp 上。 第三行將 %esp 下移 24 個(gè)字節(jié)惹资，這一行其實(shí)就是為函數(shù) caller 開辟椇馗伲空間了。從圖中可以看出褪测，下面的空間用于保存 caller 中的變量以及傳給下個(gè)函數(shù)的參數(shù)猴誊。有部分空間未使用，這個(gè)是為了地址對(duì)齊侮措，不影響我們的分析懈叹，可以忽略。
在開辟了棧幀之后分扎，就開始執(zhí)行 caller 內(nèi)部的邏輯了澄成，caller 首先創(chuàng)建了兩個(gè)局部變量（arg1和arg2）。對(duì)應(yīng)的匯編代碼為 movl $534, -4(%ebp); movl $1057, -8(%ebp)畏吓，其中 -4(%ebp) 表示 %ebp - 4 的位置墨状，也就是圖中 arg1 所在的位置， arg2 的位置則是 %ebp - 8 的位置菲饼。這兩行是把 534 和 1057 保存到傳送到這兩個(gè)位置上歉胶。
繼續(xù)往下是這幾行：
leal -8(%ebp), %eax // 把 %ebp - 8 這個(gè)地址保存到 %eax
movl %eax, 4(%esp) // 把 %eax 的值保存到 %esp + 4 這個(gè)位置上
leal -4(%ebp), %eax // 把 %ebp - 4 這個(gè)地址保存到 %eax
movl %eax, ($esp) // 把 %eax 的值保存到 %esp 這個(gè)位置上
第一行把 %ebp - 8 這個(gè)地址保存到 %eax 中，而 %ebp - 8 是 arg2 的地址巴粪，下一行把這個(gè)地址放到 %esp + 4 這個(gè)位置上通今，也就是圖中 &arg2 的那個(gè)區(qū)域塊。其實(shí)這一行是在為函數(shù) swap_add 準(zhǔn)備參數(shù) &arg2肛根，而下面兩行則是準(zhǔn)備參數(shù) &arg1辫塌。
再下面一行是 call swap_add。這一行就是調(diào)用函數(shù) swap_add 了派哲，不過(guò)在這之前還需要把返回地址壓到棧上臼氨，這里的返回地址是函數(shù) swap_add 返回后要接著執(zhí)行的代碼的地址，也就是 int diff = arg1 - arg2 地址芭届。
在調(diào)用 swap_add 后用到了其返回值 sum 繼續(xù)進(jìn)行計(jì)算储矩，我們還不知道返回值是怎么拿到的。在這之前褂乍，我們先進(jìn)入 swap_add 函數(shù)持隧，下面是對(duì)應(yīng)的代碼執(zhí)行圖：
swap_add 對(duì)應(yīng)的匯編代碼的前三行與 caller 類似，同樣是保存舊的幀指針逃片，但是因?yàn)?swap_add 不需要保存額外的變量屡拨，只需要多用一個(gè)寄存器 %ebx，所以這里保存了這個(gè)寄存器的舊值，但是沒有將 %esp 直接下移一段長(zhǎng)度的操作呀狼。
接下來(lái)綠色的兩行就是關(guān)鍵了：
movl 8(%ebp), %edx // 從 %ebp + 8 取值保存到 %edx
movl 12(%ebp), %ecx // 從 %ebp + 12 取值保存到 %ecx
這兩行分別是從 caller 中保存參數(shù) &arg1 和 &arg2 的地方取得地址值裂允，并根據(jù)地址取得 arg1和arg2 的實(shí)際數(shù)值。
接下來(lái)的 4 行是交換操作哥艇，這里就不具體看每一行的邏輯了绝编。
再下面一行 addl %ebx, %eax 是將返回值保存到寄存器 %eax 中，這里非常關(guān)鍵貌踏，函數(shù) swap_add 的返回值保存在 %eax 中十饥，一會(huì)兒 caller 就是從這個(gè)寄存器獲取的。
swap_add 的最后幾行是出棧操作哩俭，將 %ebx 和 %ebp 分別恢復(fù)為 caller 中的值。最后執(zhí)行 ret 返回到 caller 中拳恋。
下面我們繼續(xù)回到 caller 中凡资，剛才執(zhí)行到 call swap_add，下面幾行是執(zhí)行 int diff = arg1 - arg2谬运，結(jié)果保存在 %edx 中隙赁。
最后一行是計(jì)算 sum * diff，對(duì)應(yīng)的匯編代碼為 imull %edx, %eax梆暖。這里是把 %edx 和 %eax 的值相乘并且把結(jié)果保存到 %eax 中伞访。在上面的分析中，我們知道 %eax 保存著 swap_add 的返回值轰驳，這里還是從 %eax 中取出返回值進(jìn)行計(jì)算厚掷，并且把結(jié)果繼續(xù)保存到 %eax 中，而這個(gè)值又是 caller 的返回值级解，這樣調(diào)用 caller 的函數(shù)也可以從這個(gè)寄存器中獲取返回值了冒黑。
caller 函數(shù)的最后一行匯編代碼是 ret，這會(huì)銷毀 caller 的棧幀并且恢復(fù)相應(yīng)寄存器的舊值勤哗。到此抡爹，caller 和 swap_add 這個(gè)函數(shù)的調(diào)用過(guò)程就全部分析完了。
總結(jié)
本文詳細(xì)分析了函數(shù)調(diào)用過(guò)程中棧幀變化的過(guò)程芒划，對(duì)于開頭提出的幾個(gè)疑問(wèn)也都有了解答冬竟。函數(shù)棧的實(shí)現(xiàn)在常規(guī)的開發(fā)中幾乎不會(huì)涉及到，但是學(xué)習(xí)其中的原理有利于更深入地理解內(nèi)存以及編程語(yǔ)言的奧秘民逼。
參考
- 《深入理解計(jì)算機(jī)系統(tǒng)》
