重學計算機組成原理（六）- 函數調用怎麼突然Stack Overflow了!
- 2019 年 10 月 3 日
- 筆記
用Google搜異常信息，肯定都訪問過Stack Overflow網站
全球最大的程序員問答網站，名字來自於一個常見的報錯，就是棧溢出（stack overflow）
從函數調用開始，在計算機指令層面函數間的相互調用是怎麼實現的，以及什麼情況下會發生棧溢出
1 棧的意義
先看一個簡單的C程序
- function.c
- 直接在Linux中使用GCC編譯運行
[hadoop@JavaEdge Documents]$ vim function.c [hadoop@JavaEdge Documents]$ gcc -g -c function.c [hadoop@JavaEdge Documents]$ objdump -d -M intel -S function.o function.o: file format elf64-x86-64 Disassembly of section .text: 0000000000000000 <add>: #include <stdio.h> int static add(int a, int b) { 0: 55 push rbp 1: 48 89 e5 mov rbp,rsp 4: 89 7d fc mov DWORD PTR [rbp-0x4],edi 7: 89 75 f8 mov DWORD PTR [rbp-0x8],esi a: 8b 45 f8 mov eax,DWORD PTR [rbp-0x8] d: 8b 55 fc mov edx,DWORD PTR [rbp-0x4] 10: 01 d0 add eax,edx 12: 5d pop rbp 13: c3 ret 0000000000000014 <main>: return a+b; } int main() { 14: 55 push rbp 15: 48 89 e5 mov rbp,rsp 18: 48 83 ec 10 sub rsp,0x10 int x = 5; 1c: c7 45 fc 05 00 00 00 mov DWORD PTR [rbp-0x4],0x5 int y = 10; 23: c7 45 f8 0a 00 00 00 mov DWORD PTR [rbp-0x8],0xa int u = add(x, y); 2a: 8b 55 f8 mov edx,DWORD PTR [rbp-0x8] 2d: 8b 45 fc mov eax,DWORD PTR [rbp-0x4] 30: 89 d6 mov esi,edx 32: 89 c7 mov edi,eax 34: e8 c7 ff ff ff call 0 <add> 39: 89 45 f4 mov DWORD PTR [rbp-0xc],eax return 0; 3c: b8 00 00 00 00 mov eax,0x0 } 41: c9 leave 42: c3 ret main函數和上一節我們講的的程序執行區別不大,主要是把jump指令換成了函數調用的call指令,call指令後面跟着的，仍然是跳轉後的程序地址
看看add函數
add函數編譯後，代碼先執行了一條push指令和一條mov指令
在函數執行結束的時候，又執行了一條pop和一條ret指令
這四條指令的執行，其實就是在進行我們接下來要講壓棧（Push）和出棧（Pop）
函數調用和上一節我們講的if…else和for/while循環有點像
都是在原來順序執行的指令過程里，執行了一個內存地址的跳轉指令，讓指令從原來順序執行的過程里跳開，從新的跳轉後的位置開始執行。
但是，這兩個跳轉有個區別
- if…else和for/while的跳轉，是跳轉走了就不再回來了，就在跳轉後的新地址開始順序地執行指令，後會無期
- 函數調用的跳轉，在對應函數的指令執行完了之後，還要再回到函數調用的地方，繼續執行call之後的指令，地球畢竟是圓的
有沒有一個可以不跳回原來開始的地方,從而實現函數的調用呢
似乎有.可以把調用的函數指令，直接插入在調用函數的地方，替換掉對應的call指令，然後在編譯器編譯代碼的時候，直接就把函數調用變成對應的指令替換掉。
不過思考一下，你會發現漏洞
如果函數A調用了函數B，然後函數B再調用函數A，我們就得面臨在A裏面插入B的指令，然後在B裏面插入A的指令，這樣就會產生無窮無盡地替換。
就好像兩面鏡子面對面放在一塊兒，任何一面鏡子裏面都會看到無窮多面鏡子
Infinite Mirror Effect
如果函數A調用B，B再調用A，那麼代碼會無限展開
那就換一個思路，能不能把後面要跳回來執行的指令地址給記錄下來呢？
就像PC寄存器一樣，可以專門設立一個「程序調用寄存器」，存儲接下來要跳轉回來執行的指令地址
等到函數調用結束，從這個寄存器里取出地址，再跳轉到這個記錄的地址，繼續執行就好了。
但在多層函數調用里，只記錄一個地址是不夠的
在調用函數A之後，A還可以調用函數B，B還能調用函數C
這一層又一層的調用並沒有數量上的限制
在所有函數調用返回之前，每一次調用的返回地址都要記錄下來，但是我們CPU里的寄存器數量並不多
像我們一般使用的Intel i7 CPU只有16個64位寄存器，調用的層數一多就存不下了。
最終，CSer們想到了一個比單獨記錄跳轉回來的地址更完善的辦法
在內存裏面開闢一段空間，用棧這個後進先出（LIFO，Last In First Out）的數據結構
棧就像一個乒乓球桶，每次程序調用函數之前，我們都把調用返回後的地址寫在一個乒乓球上，然後塞進這個球桶
這個操作其實就是我們常說的壓棧。如果函數執行完了，我們就從球桶里取出最上面的那個乒乓球，很顯然，這就是出棧。
拿到出棧的乒乓球，找到上面的地址，把程序跳轉過去，就返回到了函數調用後的下一條指令了
如果函數A在執行完成之前又調用了函數B，那麼在取出乒乓球之前，我們需要往球桶里塞一個乒乓球。而我們從球桶最上面拿乒乓球的時候，拿的也一定是最近一次的，也就是最下面一層的函數調用完成後的地址
乒乓球桶的底部，就是棧底，最上面的乒乓球所在的位置，就是棧頂
壓棧的不只有函數調用完成後的返回地址
比如函數A在調用B的時候，需要傳輸一些參數數據，這些參數數據在寄存器不夠用的時候也會被壓入棧中
整個函數A所佔用的所有內存空間，就是函數A的棧幀（Stack Frame）
Frame在中文裏也有「相框」的意思，所以，每次到這裡，都有種感覺，整個函數A所需要的內存空間就像是被這麼一個「相框」給框了起來，放在了棧裏面。
而實際的程序棧布局，頂和底與我們的乒乓球桶相比是倒過來的
底在最上面，頂在最下面，這樣的布局是因為棧底的內存地址是在一開始就固定的。而一層層壓棧之後，棧頂的內存地址是在逐漸變小而不是變大
對應上面函數add的彙編代碼，我們來仔細看看，main函數調用add函數時
- add函數入口在0～1行
- add函數結束之後在12～13行
在調用第34行的call指令時，會把當前的PC寄存器里的下一條指令的地址壓棧，保留函數調用結束後要執行的指令地址
- 而add函數的第0行，push rbp指令，就是在壓棧
這裡的rbp又叫棧幀指針（Frame Pointer），存放了當前棧幀位置的寄存器。push rbp就把之前調用函數，也就是main函數的棧幀的棧底地址，壓到棧頂。 - 第1行的一條命令mov rbp, rsp，則是把rsp這個棧指針（Stack Pointer）的值複製到rbp里，而rsp始終會指向棧頂
這個命令意味着，rbp這個棧幀指針指向的地址，變成當前最新的棧頂，也就是add函數的棧幀的棧底地址了。 - 在函數add執行完成之後，又會分別調用第12行的pop rbp
將當前的棧頂出棧,這部分操作維護好了我們整個棧幀 - 然後調用第13行的ret指令，這時候同時要把call調用的時候壓入的PC寄存器里的下一條指令出棧，更新到PC寄存器中，將程序的控制權返回到出棧後的棧頂。
2 構造Stack Overflow
通過引入棧，我們可以看到，無論有多少層的函數調用，或者在函數A里調用函數B，再在函數B里調用A
這樣的遞歸調用，我們都只需要通過維持rbp和rsp，這兩個維護棧頂所在地址的寄存器，就能管理好不同函數之間的跳轉
不過，棧的大小也是有限的。如果函數調用層數太多，我們往棧里壓入它存不下的內容，程序在執行的過程中就會遇到棧溢出的錯誤，這就是stack overflow
構造一個棧溢出的錯誤
並不困難，最簡單的辦法，就是我們上面說的Infiinite Mirror Effect的方式，讓函數A調用自己，並且不設任何終止條件
這樣一個無限遞歸的程序，在不斷地壓棧過程中，將整個棧空間填滿，並最終遇上stack overflow。
int a() { return a(); } int main() { a(); return 0; }除了無限遞歸，遞歸層數過深，在棧空間裏面創建非常占內存的變量（比如一個巨大的數組），這些情況都很可能給你帶來stack overflow
相信你理解了棧在程序運行的過程裏面是怎麼回事，未來在遇到stackoverflow這個錯誤的時候，不會完全沒有方向了。
3 利用函數內聯實現性能優化
上面我們提到一個方法，把一個實際調用的函數產生的指令，直接插入到的位置，來替換對應的函數調用指令。儘管這個通用的函數調用方案，被我們否決了，但是如果被調用的函數里，沒有調用其他函數，這個方法還是可以行得通的。
事實上，這就是一個常見的編譯器進行自動優化的場景，我們通常叫函數內聯(Inline)
只要在GCC編譯的時候，加上對應的一個讓編譯器自動優化的參數-O，編譯器就會在可行的情況下，進行這樣的指令替換。
- 案例
為了避免編譯器優化掉太多代碼，小小修改了一下function.c，讓參數x和y都變成了，通過隨機數生成，並在代碼的最後加上將u通過printf打印
[hadoop@JavaEdge Documents]$ vim function.c [hadoop@JavaEdge Documents]$ gcc -g -c -O function.c [hadoop@JavaEdge Documents]$ objdump -d -M intel -S function.o function.o: file format elf64-x86-64 Disassembly of section .text: 0000000000000000 <main>: { return a+b; } int main() { 0: 53 push rbx 1: bf 00 00 00 00 mov edi,0x0 6: e8 00 00 00 00 call b <main+0xb> b: 89 c7 mov edi,eax d: e8 00 00 00 00 call 12 <main+0x12> 12: e8 00 00 00 00 call 17 <main+0x17> 17: 89 c3 mov ebx,eax 19: e8 00 00 00 00 call 1e <main+0x1e> 1e: 89 c1 mov ecx,eax 20: bf 67 66 66 66 mov edi,0x66666667 25: 89 d8 mov eax,ebx 27: f7 ef imul edi 29: d1 fa sar edx,1 2b: 89 d8 mov eax,ebx 2d: c1 f8 1f sar eax,0x1f 30: 29 c2 sub edx,eax 32: 8d 04 92 lea eax,[rdx+rdx*4] 35: 29 c3 sub ebx,eax 37: 89 c8 mov eax,ecx 39: f7 ef imul edi 3b: c1 fa 02 sar edx,0x2 3e: 89 d7 mov edi,edx 40: 89 c8 mov eax,ecx 42: c1 f8 1f sar eax,0x1f 45: 29 c7 sub edi,eax 47: 8d 04 bf lea eax,[rdi+rdi*4] 4a: 01 c0 add eax,eax 4c: 29 c1 sub ecx,eax #include <time.h> #include <stdlib.h> int static add(int a, int b) { return a+b; 4e: 8d 34 0b lea esi,[rbx+rcx*1] { srand(time(NULL)); int x = rand() % 5; int y = rand() % 10; int u = add(x, y); printf("u = %dn", u); 51: bf 00 00 00 00 mov edi,0x0 56: b8 00 00 00 00 mov eax,0x0 5b: e8 00 00 00 00 call 60 <main+0x60> 60: b8 00 00 00 00 mov eax,0x0 65: 5b pop rbx 66: c3 ret 上面的function.c的編譯出來的彙編代碼，沒有把add函數單獨編譯成一段指令順序，而是在調用u = add(x, y)的時候，直接替換成了一個add指令。
除了依靠編譯器的自動優化，你還可以在定義函數的地方，加上inline的關鍵字，來提示編譯器對函數進行內聯。
內聯帶來的優化是，CPU需要執行的指令數變少了，根據地址跳轉的過程不需要了，壓棧和出棧的過程也不用了。
不過內聯並不是沒有代價，內聯意味着，我們把可以復用的程序指令在調用它的地方完全展開了。如果一個函數在很多地方都被調用了，那麼就會展開很多次，整個程序佔用的空間就會變大了。
這樣沒有調用其他函數，只會被調用的函數，我們一般稱之為葉子函數（或葉子過程）
3 總結
這一節，我們講了一個程序的函數間調用，在CPU指令層面是怎麼執行的。其中一定需要你牢記的，就是程序棧這個新概念。
我們可以方便地通過壓棧和出棧操作，使得程序在不同的函數調用過程中進行轉移。而函數內聯和棧溢出，一個是我們常常可以選擇的優化方案，另一個則是我們會常遇到的程序Bug。
通過加入了程序棧，我們相當於在指令跳轉的過程種，加入了一個「記憶」的功能，能在跳轉去運行新的指令之後，再回到跳出去的位置，能夠實現更加豐富和靈活的指令執行流程。這個也為我們在程序開發的過程中，提供了「函數」這樣一個抽象，使得我們在軟件開發的過程中，可以復用代碼和指令，而不是只能簡單粗暴地複製、粘貼代碼和指令。
4 推薦閱讀
可以仔細讀一下《深入理解計算機系統（第三版）》的3.7小節《過程》，進一步了解函數調用是怎麼回事。
另外，我推薦你花一點時間，通過搜索引擎搞清楚function.c每一行彙編代碼的含義，這個能夠幫你進一步深入了解程序棧、棧幀、寄存器以及Intel CPU的指令集。
參考
深入淺出計算機組成原理
