深入理解計算機系統（十九）：過程（函數的調用原理）

來自專欄 Micropython玩家匯12 人贊了文章

目錄

1、棧幀結構

2、過程的實現

3、過程調用和返回指令

4、寄存器使用慣例

5、過程實例

5、遞歸過程

6、總結

　　上篇博客我們講解了計算機彙編語言是如何實現循環結構的。本篇博客我們將介紹彙編語言中過程的實現方式。

　　過程在高級語言中也稱為函數，方法。一個過程的調用包括將數據（以過程參數和返回值的形式）和控制從代碼的一部分傳遞到另一部分。此外，它還必須在進入時為過程的局部變數分配空間，並在退出時釋放空間。大多數機器，包括我們一直講的 IA32，只提供轉移控制到過程和從過程中轉移出控制這種簡單指令。數據傳遞和局部變數的分配釋放都是通過操縱程序棧來實現。

　　合理的構建方法並調用，能大大增加代碼的復用性，也能使代碼結構更加清晰，接下來我們就來詳細的介紹。

正文：

1、棧幀結構

　　IA32 程序用程序棧來支持過程調用。機器用棧來傳遞過程參數、存儲返回信息、保存寄存器用於以後恢復，以及本地存儲。而為單個過程分配的那部分棧稱為幀棧（stack frame）。

　　幀棧可以認為是程序棧的一段，它有兩個端點，一個標識著起始地址，一個標識著結束地址，而這兩個地址，則分別存儲在固定的寄存器當中，即起始地址存在%ebp寄存器當中，結束地址存在%esp寄存器當中。也就是說寄存器 %ebp 為幀指針，寄存器 %esp 為棧指針。

　　當程序執行時，棧指針可以移動，因此大多數信息的訪問都是相對於幀指針的。

　　這個圖基本上已經包括了程序棧的構成，它由一系列棧幀構成，這些棧幀每一個都對應一個過程，而且每一個幀指針+4的位置都存儲著函數的返回地址，每一個幀指針指向的存儲器位置當中都備份著調用者的幀指針。各位需要知道的是，每一個棧幀都建立在調用者的下方（也就是地址遞減的方向），當被調用者執行完畢時，這一段棧幀會被釋放。還有一點很重要的是，%ebp和%esp的值指示著棧幀的兩端，而棧指針會在運行時移動，所以大部分時候，在訪問存儲器的時候會基於幀指針訪問，因為在一直移動的棧指針無法根據偏移量準確的定位一個存儲器位置。

　　還有一點比較重要的內容，就是棧幀當中內存的分配和釋放。由於棧幀是向地址遞減的方向延伸，因此如果我們將棧指針減去一定的值，就相當於給棧幀分配了一定空間的內存。這個理解起來很簡單，因為在棧指針向下移動以後（也就是變小了），幀指針和棧指針中間的區域會變長，這就是給棧幀分配了更多的內存。相反，如果將棧指針加上一定的值，也就是向上移動，那麼就相當於壓縮了棧幀的長度，也就是說內存被釋放了。需要注意的是，上面的一切內容，都基於一個前提，那就是幀指針在過程調用當中是不會移動的。

2、過程的實現

　　過程的實現主要就是在於數據如何在調用者和被調用者之間傳遞，以及在被調用者當中局部變數內存的分配以及釋放。

　　而過程實現當中，參數傳遞以及局部變數內存的分配和釋放都是通過以上介紹的棧幀來實現的，大部分情況下，我們認為過程調用當中做了以下幾個操作。

　　①、備份原來的幀指針，調整當前的幀指針到棧指針的位置，這個過程就是我們經常看到的如下兩句彙編代碼做的事情。

pushl %ebpmovl %esp, %ebp

　　②、建立起來的棧幀就是為被調用者準備的，當被調用者使用棧幀時，需要給臨時變數分配預留內存，這一步一般是經過下面這樣的彙編代碼處理的。

subl $16,%esp

　　③、備份被調用者保存的寄存器當中的值，如果有值的話，備份的方式就是壓入棧頂。因此會採用如下的彙編代碼處理。

pushl %ebx

　　④、使用建立好的棧幀，比如讀取和寫入，一般使用mov，push以及pop指令等等。

　　⑤、恢復被調用者寄存器當中的值，這一過程其實是從棧幀中將備份的值再恢復到寄存器，不過此時這些值可能已經不在棧頂了。因此在恢復時，大多數會使用pop指令，但也並非一定如此。

　　⑥、釋放被調用者的棧幀，釋放就意味著將棧指針加大，而具體的做法一般是直接將棧指針指向幀指針，因此會採用類似下面的彙編代碼處理（也可能是addl）。

movl %ebp,%esp

　　⑦、恢復調用者的棧幀，恢復其實就是調整棧幀兩端，使得當前棧幀的區域又回到了原始的位置。因為棧指針已經在第六步調整好了，因此此時只需要將備份的原幀指針彈出到%ebp即可。類似的彙編代碼如下。

popl %ebp

　　⑧、彈出返回地址，跳出當前過程，繼續執行調用者的代碼。此時會將棧頂的返回地址彈出到PC，然後程序將按照彈出的返回地址繼續執行。這個過程一般使用ret指令完成。

　　過程的實現大概就是以上八個步驟組成的，不過這些步驟並不都是必須的（大部分時候，開啟編譯器的優化會優化掉很多步驟），而且第6和第7步有時會使用leave指令代替。下面會詳細講解這些步驟。

3、過程調用和返回指令

　　下圖是支持過程調用和返回的指令：

　　①、call指令：call 指令有一個目標，即指明被調用過程起始的指令地址。直接調用的目標可以是一個標號，間接調用的目標是 * 後面跟一個操作符。它一共做兩件事，第一件是將返回地址（也就是call指令執行時PC的值）壓入棧頂，第二件是將程序跳轉到當前調用的方法的起始地址。第一件事是為了為過程的返回做準備，而第二件事則是真正的指令跳轉。

　　②、leave指令：它也是一共做兩件事，第一件是將棧指針指向幀指針，第二件是彈出備份的原幀指針到%ebp。第一件事是為了釋放當前棧幀，第二件事是為了恢復調用者的棧幀。

　　③、ret指令：它同樣也是做兩件事，第一件是將棧頂的返回地址彈出到PC，第二件事則是按照PC此時指示的指令地址繼續執行程序。這兩件事其實也可以認為是一件事，因為第二件事是系統自己保證的，系統總是按照PC的指令地址執行程序。

　　可以看出，除了call指令之外，leave和ret指令都與上面8個步驟有些不可分割的關係。call指令沒有在8個步驟當中體現，是因為它發生在進入過程之前，因此在第1步發生的時候，call指令往往已經被執行了，並且已經為ret指令準備好了返回地址。

4、寄存器使用慣例

　　程序寄存器組是唯一能夠被所有過程共享的資源。雖然在給定時刻只能有一個過程是活動的，但是我們必須保證當一個過程（調用者）調用另一個過程（被調用者）時，被調用者不會覆蓋某個調用者稍後會使用的寄存器的值。為此必須採用一組統一的寄存器使用慣例，所有的過程都必須遵守，包括程序庫的過程。

　　假如沒有這些規矩，比如在調用一個過程時，無論是調用者還是被調用者，都可能更新寄存器的值。假設調用者在%edx中存了一個整數值100，而被調用者也使用這個寄存器，並更新成了1000，於是悲劇就發生了。當過程調用完畢返回後，調用者再使用%edx的時候，值已經從100變成了1000，這幾乎必將導致程序會錯誤的執行下去。所以便有如下規矩：

　　在 IA32 中，寄存器%eax，%edx和%ecx被劃分為調用者保存寄存器。當過程 P 調用 Q 時，Q可以覆蓋這些寄存器，而不會破壞 P 所需的數據。

　　寄存器%ebx,%esi和%edi被劃分為被調用者保存寄存器。這裡 Q 必須在覆蓋這些寄存器的值之前，先把他們保存到棧中，並在返回前恢復它們，因為 P（或某個更高層次的過程）可能會在今後的計算中需要這些值。上面所說的過程實現的8個步驟中第三步便是如此。

　　考慮如下代碼：

int P(int x){ int y = x*x; int z = Q(y); return y+z;}

　　過程 P 在調用 Q 之前會先計算 y 的值，而且它必須保證 y 的值在 Q 返回後是可用的。這裡有兩種方法實現：

　　①、可以在調用 Q 之前，將 y 的值保存在自己的幀棧中；當 Q 返回時，過程 P 就可以從棧中取出y 的值。換句話說就是調用者 P 自己保存這個值。

　　②、可以將 y 保存在被調用者保存寄存器中。如果 Q ,或者其它 Q 調用的程序想使用這個寄存器，它必須將這個寄存器的值保存在幀棧中，並在返回前恢復該值。換句話說就是被調用者保存這個值。當 Q 返回到 P 時，y 的值會在被調用者保存寄存器中，或者是因為寄存器根本就沒有改變，或者是因為它被保存並恢復了。

　　這兩種方法在 IA32 中是都採用的。

5、過程實例

　　考慮如下代碼 function.c

#include <stdio.h> int add(int a,int b){ register int c = a + b; return c;} int main(){ int a = 100; int b = 101; int c = add(a,b); return c;}

相信上面的代碼沒有什麼難度，在 main過程中調用 add過程。我們通過如下指令編譯成彙編代碼：

gcc -O0 -S function.c

為了完整的展現那8個步驟，因此給變數c加了register關鍵字修飾，這將會將c送入寄存器，從而更改被調用者保存寄存器，就會導致步驟3的發生。以下是main函數以及add函數各自的棧幀情況:

　　上面的彙編代碼是我們沒有使用優化級別編譯出來的，所以完整的呈現了前面所講的8個步驟。這裡我們需要注意兩點：

　　①、add函數會將返回結果存入%eax（前提是返回值可以使用整數來表示），在main函數中，call指令之後，默認將%eax作為返回結果來使用。

　　②、所有函數（包括main函數）都必須有第1步和第6、7、8步，這是必須的4步。我們的棧指針和幀指針有固定的大小關係，即棧指針永遠小於等於幀指針，當二者相等時，當前棧幀被認為沒有分配內存空間。

5、遞歸過程

　　前面我們講的都是一個過程能調用其它的過程，但是其實一個過程也能調用自己本身的，也就是遞歸調用。因為每個調用在棧中都有它自己的私人空間，多個未完成調用的局部變數不會互相影響，此外，棧的原則也提供了適當的策略，當過程被調用時分布局部存儲空間，當過程執行完畢返回時釋放存儲空間。

　　下面是一段求 n 的階乘的遞歸調用代碼：

int rfact(int n){ int result; if(n<=1){ result = 1; }else{ result = n * rfact(n-1); } return result;}

　　我們還是用 -O0 -S 來編譯得到彙編代碼：

　　上面的彙編代碼，當用參數 n 來調用時，首先代碼 2~5 行會創建一個幀棧，其中包含 %ebp 的舊值、保存的被調用者保存的寄存器 %ebx 的值，以及當遞歸調用自身的時候保存參數的四個位元組。

　　如下圖所示，它用寄存器 %ebx 來保存過程參數 n 的值（第 6 行代碼）。它將寄存器 %ebx 中的返回值設置為 1，預期 n<=1 的情況，它就會跳轉到完成代碼。

　　對於遞歸的情況，計算 n-1，將這個值存儲在棧上，然後調用函數自身（第10~12行），在代碼的完成部分，我們可以假設：

　　①、寄存器%eax保存這（n-1）!的值

　　②、被調用保存寄存器%ebx保存著參數n

　　因此將這兩個值相乘（第 13 行）得到該函數的返回值。對於終止條件和遞歸調用，代碼都會繼續到完成部分（第15~17行），恢復棧和被調用者保存寄存器，然後在返回。

　　所以我們看到遞歸調用一個函數本身與調用其它函數是一樣的。棧規則提供了一種機制，每次函數調用都有它自己的私有狀態信息（保存的返回值、棧指針和被調用者保存寄存器的值）存儲。如果需要，它還可以提供局部變數的存儲。分配和釋放的棧規則很自然的就與函數調用——返回的順序匹配。

6、總結

　　本章對於函數的彙編實現做了詳細的講解，主要是棧規則的機制，幫我們解決了數據如何在調用者和被調用者之間傳遞，以及在被調用者當中局部變數內存的分配以及釋放。那麼下篇博客我們將介紹數組的分配和訪問，我們知道比如Java語言中的集合很多都是在數組的基礎上實現的。弄懂下一章的內容後，你會對定長數組與不定長數組（集合）有更深刻的了解。

推薦閱讀：