棧幀的結構
?
倘若我們要想搞清楚過程的實現，就必須先知道棧幀的結構是如何構成的。棧幀其實可以認為是程序棧的一段，而程序棧又是存儲器的一段，因此棧幀說到底還是存儲器的一段。那么既然是一段，肯定有兩個端點，這個不需要LZ再普及了吧。
這兩個端點其實就是兩個地址，一個標識著起始地址，一個標識著結束地址，而這兩個地址，則分別存儲在固定的寄存器當中，即起始地址存在%ebp寄存器當中，結束地址存在%esp寄存器當中。至于為什么要存在這兩個寄存器當中，就像程序的下一條指令地址為什么存在PC當中一樣，是毫無意義的問題，就是這樣規定的，沒有為什么。
起始地址和結束地址還有另外的名字，起始地址通常稱為幀指針，結束地址通常稱為棧指針（也就是棧頂的地址）。因此，我們就把過程的存儲器內存使用區域稱為棧幀。這下我們就了解了棧幀的來歷以及它們的命名習慣和存儲慣例，接下來是LZ畫的一幅圖，它揭示了棧幀在存儲器當中的位置。
這個圖基本上已經包括了程序棧的構成，它由一系列棧幀構成，這些棧幀每一個都對應一個過程，而且每一個幀指針+4的位置都存儲著函數的返回地址，每一個幀指針指向的存儲器位置當中都備份著調用者的幀指針。各位需要知道的是，每一個棧幀都建立在調用者的下方（也就是地址遞減的方向），當被調用者執行完畢時，這一段棧幀會被釋放。還有一點很重要的是，%ebp和%esp的值指示著棧幀的兩端，而棧指針會在運行時移動，所以大部分時候，在訪問存儲器的時候會基于幀指針訪問，因為在一直移動的棧指針無法根據偏移量準確的定位一個存儲器位置。
還有一點比較重要的內容，就是棧幀當中內存的分配和釋放。由于棧幀是向地址遞減的方向延伸，因此如果我們將棧指針減去一定的值，就相當于給棧幀分配了一定空間的內存。這個理解起來很簡單，因為在棧指針向下移動以后（也就是變小了），幀指針和棧指針中間的區域會變長，這就是給棧幀分配了更多的內存。相反，如果將棧指針加上一定的值，也就是向上移動，那么就相當于壓縮了棧幀的長度，也就是說內存被釋放了。需要注意的是，上面的一切內容，都基于一個前提，那就是幀指針在過程調用當中是不會移動的。
?
過程的實現
?
過程雖然很好，但想要實現過程，還是存在一定難度的，盡管現在看來它并不困難。它實現的難度主要就在于數據如何在調用者和被調用者之間傳遞，以及在被調用者當中局部變量內存的分配以及釋放。
不過天大的難題都難不倒那群計算機界的大神們，他們找出了一種方式，可以簡單并有效的處理過程實現當中的難題。這一切似乎看起來十分偶然，但其實也是必然的。世間的很多規律都是客觀存在的，只是它在等著我們去發現而已。
總的來說，過程實現當中，參數傳遞以及局部變量內存的分配和釋放都是通過以上介紹的棧幀來實現的，大部分情況下，我們認為過程調用當中做了以下幾個操作。
1、備份原來的幀指針，調整當前的幀指針到棧指針的位置，這個過程就是我們經常看到的如下兩句匯編代碼做的事情。
pushl %ebpmovl %esp, %ebp 2、建立起來的棧幀就是為被調用者準備的，當被調用者使用棧幀時，需要給臨時變量分配預留內存，這一步一般是經過下面這樣的匯編代碼處理的。
subl $16,%esp 3、備份被調用者保存的寄存器當中的值，如果有值的話，備份的方式就是壓入棧頂。因此會采用如下的匯編代碼處理。
pushl %ebx 4、使用建立好的棧幀，比如讀取和寫入，一般使用mov，push以及pop指令等等。
5、恢復被調用者寄存器當中的值，這一過程其實是從棧幀中將備份的值再恢復到寄存器，不過此時這些值可能已經不在棧頂了。因此在恢復時，大多數會使用pop指令，但也并非一定如此。
6、釋放被調用者的棧幀，釋放就意味著將棧指針加大，而具體的做法一般是直接將棧指針指向幀指針，因此會采用類似下面的匯編代碼處理（也可能是addl）。
movl %ebp,%esp 7、恢復調用者的棧幀，恢復其實就是調整棧幀兩端，使得當前棧幀的區域又回到了原始的位置。因為棧指針已經在第六步調整好了，因此此時只需要將備份的原幀指針彈出到%ebp即可。類似的匯編代碼如下。
popl %ebp 8、彈出返回地址，跳出當前過程，繼續執行調用者的代碼。此時會將棧頂的返回地址彈出到PC，然后程序將按照彈出的返回地址繼續執行。這個過程一般使用ret指令完成。
過程的實現大概就是以上八個步驟組成的，不過這些步驟并不都是必須的（大部分時候，開啟編譯器的優化會優化掉很多步驟），而且第6和第7步有時會使用leave指令代替。這里猿友們可以先了解一下這些步驟，在接下來的內容當中，還會有這幾個步驟的詳細示例。
?
過程相關指令：call、leave、ret
?
由于過程調用當中會經常見到幾個新的指令，因此在這里，LZ先給大家介紹一下這三個指令。它們三個都是過程實現當中非常重要的角色，這三個指令很類似，因為它們都是一個指令做了兩件事，這里LZ就依次介紹一下它們各自都做了什么事。
call指令：它一共做兩件事，第一件是將返回地址（也就是call指令執行時PC的值）壓入棧頂，第二件是將程序跳轉到當前調用的方法的起始地址。第一件事是為了為過程的返回做準備，而第二件事則是真正的指令跳轉。
leave指令：它也是一共做兩件事，第一件是將棧指針指向幀指針，第二件是彈出備份的原幀指針到%ebp。第一件事是為了釋放當前棧幀，第二件事是為了恢復調用者的棧幀。
ret指令：它同樣也是做兩件事，第一件是將棧頂的返回地址彈出到PC，第二件事則是按照PC此時指示的指令地址繼續執行程序。這兩件事其實也可以認為是一件事，因為第二件事是系統自己保證的，系統總是按照PC的指令地址執行程序。
可以看出，除了call指令之外，leave和ret指令都與上面8個步驟有些不可分割的關系。call指令沒有在8個步驟當中體現，是因為它發生在進入過程之前，因此在第1步發生的時候，call指令往往已經被執行了，并且已經為ret指令準備好了返回地址。
?
寄存器使用的規矩
?
寄存器一共就8個，因此在數目上來說的話，使用起來肯定是捉襟見肘的。在這種情況下，就肯定需要一定的規矩去約束程序如何使用，否則要是一群人翻同一個人的牌子，那到底伺候誰才是呢。其實我們在之前已經或多或少的接觸到了寄存器的規矩，比如%eax一般用于存儲過程的返回值，%ebp保存幀指針，%esp保存棧指針。這里要介紹的，是另外一個規矩，而這個規矩是與過程實現相關的。
試想一下，在調用一個過程時，無論是調用者還是被調用者，都可能更新寄存器的值。假設調用者在%edx中存了一個整數值100，而被調用者也使用這個寄存器，并更新成了1000，于是悲劇就發生了。當過程調用完畢返回后，調用者再使用%edx的時候，值已經從100變成了1000，這幾乎必將導致程序會錯誤的執行下去。
為了避免上面這種情況發生，就需要在調用者和被調用者之間做一個協調。于是便有了這樣的規矩，它的描述如下，我們假設這里在過程P中調用了過程Q，P是調用者，Q是被調用者。
%eax、%edx、%ecx：這三個寄存器被稱為調用者保存寄存器。意思就是說，這三個寄存器由調用者P來保存，而對于Q來說，Q可以隨便使用，用完了就不用再管了。
%ebx、%esi、%edi：這三個寄存器被稱為被調用者保存寄存器。同樣的，這里是指這三個寄存器由被調用者Q來保存，換句話說，Q可以使用這三個寄存器，但是如果里面有P的變量值，Q必須保證使用完以后將這三個寄存器恢復到原來的值，這里的備份，其實就是上面那8個步驟中第3個步驟做的事情。
?
一個過程示例
?
上面已經做好了充足的準備，接下來我們就要探索真理了，我們隨便寫一個調用過程的例子，LZ寫了以下的代碼來做這個十分重要的例子，我們稱它為function.c。
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; } 這里LZ為了完整的展現那8個步驟，因此給變量c加了register關鍵字修飾，這將會將c送入寄存器，從而更改被調用者保存寄存器，就會導致步驟3的發生。接下來我們就使用參數-S來編譯這段代碼，然后使用cat來看看這段代碼的匯編形式。以下是main函數以及add函數各自的棧幀情況，LZ已經詳細標記了它們屬于哪個步驟。
由于我們沒有使用編譯優化，因此匯編代碼會多出很多，這也為了完整的詮釋我們的步驟。可以看到，圖中包含了完整的8個步驟，但是無論是main函數還是add函數，它們單獨來講，都沒有完整的8個步驟，這其實是大多數的情況。大部分時候，一個函數不會完全包含上述的8個步驟。LZ這里不再一一拆分各個步驟，各位猿友可以嚴格按照各個指令的作用，自己畫圖理解一下這個過程，答案自會浮現。
LZ這里只說幾點各位需要注意的地方，首先第一點是，add函數會將返回結果存入%eax（前提是返回值可以使用整數來表示），在main函數中，call指令之后，默認將%eax作為返回結果來使用。第二點是，所有函數（包括main函數）都必須有第1步和第6、7、8步，這是必須的4步。最后一點是，我們的棧指針和幀指針有固定的大小關系，即棧指針永遠小于等于幀指針，當二者相等時，當前棧幀被認為沒有分配內存空間。
還有一點十分有趣的事情，注意main函數當中100和101的傳遞過程，是先進入存儲器，然后再進去寄存器，然后再進去存儲器，準備作為add函數的參數。這一來一回產生了四次寄存器與存儲器之間的數據傳輸，倘若我們加上-O1參數去編譯這個程序，編譯器將產生如下的匯編代碼。
可以看到，整個main函數的指令數驟降，100和101將直接進入存儲器，準備作為add函數的參數。可見編譯器的優化當中至少會有一項，就是減少數據的來回傳輸，增加效率。不過這一點其實與過程的實現沒有什么關系，只是讓以前可能不知道的猿友看一下，編譯器其實會將我們的程序做很大的改動。
遞歸過程調用
?
書中對遞歸調用還進行了說明，這是為了讓我們相信，棧幀的建立和銷毀慣例，可以保證遞歸過程的正常運行。其實如果各位猿友愿意一點一點的，將上面main函數和add函數的匯編代碼搞清楚，那么遞歸調用其實也可以很輕松的搞定。因為指令就這么多了，只要嚴格按照-S編譯出的匯編指令，一步一步的推算寄存器和存儲器的狀態，那么遞歸調用的實現也會自動浮現。
LZ這里準備給各位猿友詮釋一下遞歸的過程，各位猿友可以對照著上面的示例看一下，以下是一段簡單的求n的階乘的代碼。
int rfact(int n){int result; if(n<=1){ result = 1; }else{ result = n * rfact(n-1); } return result; } 接下來我們編譯一下這段代碼，使用-O1優化，我們可以得到如下的匯編代碼。
LZ在圖中詳細標注了各個步驟所做的事情，其實嚴格按照各個指令的作用分析，很輕松的就可以分析出圖中的解釋部分（即注釋）。難點就在于，棧幀的變化是如何的，LZ這里就給各位演示一下棧幀的變化過程，如果各位已經把前面的那個main函數和add函數搞定了，那么可以在這里驗證一下自己的理解是否正確。
需要特殊說明的是，以上每一個棧幀（大括號括起來的），最上面（也就是地址遞增方向）的都是幀指針位置，最下面的都是棧指針位置。然而寄存器中只有%ebp和%esp保存棧幀指針，因此同一時間只能保存一對。當進展到第三層的時候，已經有了三個棧幀（原則上來講一定是多于3個），寄存器當然是存不下的，因此就需要在存儲器當中備份一下，之后再恢復。于是就出現了每個棧幀的幀指針指向的存儲器位置，都會備份著外層方法（也就是調用者）的幀指針。
當方法遞歸到n=1結束時，棧幀會自下向上依次收回，棧幀指針（也就是%ebp和%esp當中的值）都會依次向上移動，直到程序結束。也就是說，上面的三幅圖，如果倒過來，就是遞歸方法依次結束時棧幀的狀態。
由此就可以看出，過程當中棧幀建立以及完成的慣例，可以保證遞歸調用的正常運行，包括循環調用。不得不說，這群計算機界的大神們實在是太牛了，盡管當棧幀出現以后，看起來也并不復雜，但難點就在于無中生有的發現或者說某種意義上的創造。
?
作者：zuoxiaolong（左瀟龍）
出處：博客園左瀟龍的技術博客--http://www.cnblogs.com/zuoxiaolong
)
