棧
作為一名有政治覺悟的、堅持政治思想正確的、胸口飄揚鮮紅的工卡的程序員，我們要謹記這句話：
沒有黨就沒有新中國，沒有棧就沒有過程調用。
是的，棧就是過程調用的基礎。為保證順利的過程調用，棧主要做了以下四點：
- 保存函數參數。
- 保存返回地址。
- 保存寄存器。
- 調整幀指針(ebp)和棧指針(esp)。
保存函數參數這是必須的，不多說了，當然有可能是寄存器保存，具體細節下面會聊到。保存返回地址，保存call指令的下一條指令的地址，ret指令會返回這一地址。保存寄存器這一步，主要是為了防止被調用者覆蓋調用者的寄存器。而幀指針和棧指針之間的空間就是本次棧幀的空間，調整這兩個指針以訪問空間。
常見的棧結構如下：
過程調用可以分為三個部分，初始化棧幀、主體、銷燬棧幀。初始化棧幀和銷燬棧幀部分涉及到的就是棧主要做的四點。主體部分涉及到的就是使用棧幀的部分。
常見的過程調用匯編如下：
可以看到，過程調用的初始化和銷燬部分是完全相反的。並且，棧在過程調用前後現場必須是一致的。
Calling-Convention(調用慣例)
就像平時寫代碼時會用到的協議模式，雙方之間需要規定一些規則才能合力將一件事做好。過程調用也一樣，需要調用者和被調用者遵守一組“協議”，以順利地共同完成過程調用。Calling Convention就可以看做是這樣的一組協議。Calling Convention主要包括以下三個方面：
- 函數參數的傳遞方式和順序。
- 棧恢復現場的方式。
- 函數返回值的傳遞方式。
先聊第一點，函數參數的傳遞順序和方式。方式指的是參數是放在寄存器上還是棧上還是混合？ia32規定參數全部放在棧上，而x86-64則規定先放寄存器上，如果超過6個再放到棧上。這是因為ia32有8個通用寄存器，而x86-64有16個通用寄存器。函數的傳遞順序指的是，從左至右存儲還是從右至左存儲。比較常見的Calling-Convention比如C語言默認的cdecl規定就是從右至左存儲。
對於第二點，棧恢復現場的方式。要做到棧在過程調用前後現場一致這一點，就要將參數都從棧上pop掉。實際上，只要調整esp就可以。這件事可以由調用者做，也可以由被調用者做，大部分Calling Convention規定由調用者做。Calling Convention就要規定這一點。除了參數，被保存的寄存器也有自己的Calling Convention，被保存的寄存器可以被分為調用者保存或者被調用者保存，棧恢復現場的時候，被保存的寄存器也要按Calling Convention從棧上pop掉。這第二點是必須要做的，Calling Convention就是規定由調用者做還是被調用者做。
第三點，函數返回值的傳遞方式。幾乎所有的Calling Convention都規定小於4字節的返回值，放到eax中。小於8字節、大於4字節的返回值，放到eax和edx中。若是更大的返回值，怎麼辦？總不能都放在寄存器中吧。那就不直接傳遞值，傳遞地址。調用者先在棧上分配足夠大的空間，然後將空間的地址以隱式參數(implicit argument )的方式傳遞給被調用者，被調用者將返回值先複製到作為隱式參數的地址中，再將地址放到eax中。調用者將eax中地址的內容再複製到返回值中，這樣通過一箇中介空間和其地址就可以處理更大的返回值。
關於隱式參數再聊一點。支持面向對象的語言當中，比如，C++中的this，Objective-C中的Self，代表對象自己的變量都會作為方法的第一個隱式參數。
字節對齊(alignment)、字節陪襯(padding)
在聊堆之前，先鋪墊一些字節對齊和字節陪襯內容，在後面會用到。字節對齊、字節陪襯都源於CPU讀取存儲器中的數據看上去是“隨機訪問”的，實則是按單位(chunk)訪問的。最常見的是以4字節作為單位訪問，也就是說CPU只能訪問4的n倍到4的(n+1)倍地址的數據。那你應該就能看出問題了，如果數據起始地址不是4的n倍數，CPU就需要更多次的存儲器訪問。
數據的字節對齊指的是：數據的起始地址，應該正好落在CPU訪問存儲器地址的邊界上(the address fall evenly on the processor’s memory access boundary)。更加詳細的資料看IBM文檔、WikiPedia、MicroSoft文檔。而我們一般說數據對n字節對齊就是數據的起始地址正好落在n的整數倍上。
如果出現了不對齊的數據，最好的對齊方式就為起始地址的前一數據末尾添加字節，相當於將不對齊數據遷移(shift)到邊界上，完成對齊。這就是字節陪襯，為數據末尾添加一些無意義的陪襯字節(insert some meaningless bytes)，以對齊後面的數據。
這時，要明確字節對齊由誰來做？自然是編譯器，編譯器會幫你進行自然對齊，自然對齊會按數據類型的大小作為數據字節對齊的n。當然，還有強制對齊，你可以使用attribute((aligned()))指明對齊的n，C++中還可以使用alignas關鍵字。
那麼，對於基本類型數據考慮自身對齊就可以了。如果是複合類型數據呢，比如說Array、Struct？對於複合類型數據有兩條規則要遵守：
- 保證每個元素字節對齊。
- 保證自身字節對齊。
對於Array來說，將Array起始地址根據元素類型對齊就是保證自身字節對齊。如果Array中的元素是基礎類型數據，只要Array自身字節對齊就已經滿足每個元素對齊了。而如果是複合類型，複合類型自身要負責在Array中每個元素對齊，要保證複合類型數據大小能夠整除Array自身對齊的n。
對於Struct來說，要遵守以下三點，實際上這三點都是保證每個元素字節對齊、保證自身對齊這兩條規則的印證：
- 為了保證每個元素字節對齊，元素要按照自己的offset自然對齊。
- 為了保證自身對齊，Struct將包含的所有元素類型大小的最大值作為n進行對齊。
- 當Struct在複合類型數據中，Struct作為複合類型數據的元素，為了保證複合類型數據中每個元素對齊，Struct的大小要整除Struct包含的所有元素類型大小的最大值n。
比如，如下Struct：
按照第一條，long類型的元素l，起始offset是8而不是5。按照第二條，S1要對8進行對齊。
而如下Struct:
按照第三條，S2的大小是12而不是9。
實際上，在我們使用Struct的時候，聲明元素的順序會影響Struct的真實大小。在使用Struct的時候要注意這一點。
堆
數據除了棧這種隨著過程調用分配、釋放的管理方式，還需要要一種主動控制分配、釋放時機的管理方式。這種管理方式就是堆，更加明確的來說是堆管理器。
注意，這裡要明確非常關鍵的一點。堆管理器管理的是虛擬空間，並且僅將虛擬空間從未分配轉換到已分配，等到真正使用再發生缺頁中斷，將虛擬空間從已分配轉換到已緩存。這裡如果有疑惑可以回顧一下上篇文章再看裝載這一部分的這段話：
從虛擬空間來看，進程創建後，虛擬空間也被創建。此時，虛擬空間是未分配的，裝載將映射記錄在進程的vma中，就是將虛擬空間從未分配轉換為已分配。等到缺頁中斷，再將虛擬空間從已分配轉換到已緩存。
明確這一點後，可以思考這樣的一個問題，堆分配空間和mmap有什麼本質的不同？實則沒有，都是向虛擬存儲器申請一段空間，這裡我們再提高一下領悟層次、總結一下。實際上，裝載、mmap、堆都是虛擬存儲器的“最佳實踐(best practice)”。堆管理器實質上就是向操作系統申請資源，堆管理器有兩種管理方式。有趣的是，其中一種就是由mmap實現的，直接將映射類型傳入匿名空間(MAP_ANONYMOUS)，操作系統就會挑一個合適的虛擬空間分配。這種管理方式操作系統職責較多、分配的空間碎片化。碎片化指的並不是單次分配空間內不是連續的，而是多次分配空間之間不是連續的。
而另一種管理方式操作系統職責較少、分配的空間連續化，連續化管理方式要先向操作系統“批發”適當的資源，只要“批發”下來的資源夠使就從這些資源中”零售”，不夠使再另“批發”資源，堆管理器就成了以計算機資源作為商品線上的“連鎖超市”。連續化管理方式防止每次”零售”都要進行系統調用，只有“批發”的時候進行系統調用。連續化管理方式分配的空間從進程空間中的數據段結尾處開始，並向高地址增長。已分配的空間與未分配的空間之間由brk指針區分。
brk指針
“批發”被操作系統形式化成增加(increment)brk指針。直接調用Linux提供的brk和sbrk接口，進行系統調用，增加brk指針，等同於從操作系統申請資源。brk指針還有個有趣的作用，就是在Linux中可以通過它分辨地址是在棧上還是在堆上，詳細點我。
glibc在分配的空間小於128kb時會使用連續化管理方式，大於時使用碎片化管理方式。下面主要聊聊操作系統職責較少的管理方式，操作系統職責較多的管理方式實現沒有複雜度，調用mmap就好。
堆管理器設計
CRT(C Runtime Library)已經為我們實現了堆管理器，其相關API就是malloc、calloc、free、realloc，CRT實現的堆管理器自然是高效的、可靠的，無需我們再重複造輪子。但學習堆管理器的最好辦法就是自行實現一個mini堆管理器，這裡就聊聊如何設計一個堆管理器，聊一聊其背後的思想。
在設計堆管理器之前，我們要明確衡量堆管理器是否高效的標準。堆管理器有兩個標準，一個是堆管理器的響應速度(吞吐率)、一個是存儲器存儲真正分配空間的比率(使用率)。這也就是說，在設計堆管理的時候不能為了節省空間使用過於複雜的算法拖慢響應速度，不能用過於複雜的數據結構，從而恢復性質導致拖慢響應速度，也不能過於浪費存儲器空間。很明顯，要在這兩點之間做trade-off。
結構組織
首先，第一個要意識到的就是除了分配的空間，我們至少要記錄下空間的大小、佔用情況以管理空間。那麼如何組織分配的空間和空間的信息？將分配的空間組織成metadata和payload的chunk形式。
Unix中為了讓任意類型的數據字節對齊，對分配的空間以8進行字節對齊。我們在設計的時候，可以僅使整體chunk以8字節對齊，不需強制metadata和payload各自對齊，或者對metadata和payload都強制8字節對齊，這裡我們使整體chunk以8字節對齊就可以了。如何做到呢？通過上文的字節陪襯，為每個chunk插入padding，使chunk size為8的整數倍。
強制對齊chunk以後，表示chunk大小的字段最低3位必定是000，這3位就可以用來記錄chunk是否空閒。這樣一個典型的組織如下：
通過每個chunk的size就可以按順訪問chunk。實際上，這就將chunk組織成無需next指針域的鏈表。
分配和釋放
分配：先要確定請求是否合理。然後，對齊請求的空間大小，查找鏈表中是否有size合適而且free的chunk，如果有直接將free置為1，並且返回payload地址。如果沒有，要通過sbrk向操作系統申請空間或用早已申請好的空間，構建新的chunk。
釋放：同樣，先確定請求是否合理。然後找到chunk，將free置為0。
查找
查找有以下三種算法：
- 首次適配(first fit)：按順序遍歷鏈表，直到找到第一個合適的free chunk。
- 下一次適配(next fit)：從上次查找結構開始遍歷鏈表，直到找到第一個合適的free chunk。
- 最佳適配(best fit)：遍歷整個鏈表，找到合適的free chunk。
這裡簡單分析一下這三種算法，首次適配會導致整個鏈表的chunk size分佈不均勻，小size chunk都集中在頭部，大size chunk都集中在尾部，堆管理器的使用率還不錯，吞吐率由於查找大size chunk不會太理想。下一次適配會使整個鏈表的chunk size較為平均，堆管理器的使用率不如首次適配，但是吞吐率會高於首次適配。而最佳適配有最好的使用率，最差的吞吐率。綜合來看，建議使用首次適配，簡單而高效。
碎片
然而，光是這樣分配和釋放會造成很多碎片。比如將一個大size的chunk分配給了一個小空間的申請造成剩餘size浪費的內部碎片，或者多個小size的chunk無法響應一個大空間的申請而造成的外部碎片。這時，需要引入對chunk進行split(分割)和coalesce(合併)。
split比較簡單，當first fit找到個合適的chunk後，只要chunk還有比最小chunk還大的空間，就在此空間上構建一個新的free chunk。
coalesce相對複雜一點，coalesce需要檢查前一節點和後一節點是否free，如果free就合併。而合併就是累加所需coalesce的chunk size給coalesce中首個chunk就行。複雜的地方在，檢查前一節點要求chunk有快速訪問前一節點的能力。最簡單的方式就是為chunk metadata添加一個prev前向指針域，實際上這就是轉化為雙向鏈表。還有一種方式就是邊界標記法(boundary tag)，為chunk添加footer，footer就是metadata的copy。這樣每次chunk想要訪問前一節點，只要訪問metadata的前4字節就可以。並且只有free的chunk擁有footer就行，不需要所有chunk都擁有footer，相對於添加prev增大了使用率，則chunk組織更改如下：
可以看到metadata和footer為8字節，payload加上padding大小必定是8的整數倍。
這裡還有一個原因不使用添加prev前向指針域解決問題。在查找合適chunk的時候，需要查找所有chunk，完全不需要這樣做。可以為所有free的chunk添加一個指向前一個free chunk的prev域，一個指向後一個free chunk的next域，來降低吞吐率，最後chunk組織更改如下：
當然，還有更多的堆管理器設計方式，比如說用位圖。還有一種比較有趣的分離存儲(segregated storage)，這種管理方式維護多個鏈表，每個鏈表的chunk size近似。這種方式就像是，按請求空間的大小作為請求模式去分離請求，每個鏈表只應對一種請求模式。
ABI(應用二進制接口)
ABI全名是application binary interface，實際上它也是一個“協議”，“協議”的主體有兩種類型，一種是二進制代碼、一種是承載二進制代碼的操作系統。實際上，二進制代碼與操作系統之間可以遵守同樣的“協議”，二進制代碼與二進制代碼之間也可以遵守同樣的“協議”。只要生成的二進制代碼遵守這個“協議”，任何同樣遵守這個“協議”的操作系統都可以運行，遵守同樣“協議”的二進制代碼可以一起運行，比如說不同語言需要遵守同樣的“協議”才可以一起運行。ABI包括：
- 基本類型大小、佈局以及上文所提到的對齊。還包括面嚮對象語言中比如C++中對象的多重繼承佈局。
- 上文提到的Calling Convention。
- 系統調用的方法。
- 目標文件格式的二進制格式、系統庫格式。
而二進制代碼要遵守ABI，主要的工作在彙編、鏈接階段，比如說用同樣的指令集、使用同樣的符號修飾，更多詳細信息參見。接下來的字節序就當是本篇文章的彩蛋吧O(∩_∩)O
字節序
字節序是計算機存儲一個多字節數據(比如說int)的順序，指的是字節與字節之間的順序，而不是單個字節內的順序。字節序分為大端法(big endian)和小端法(little endian)。很明顯，大端法高位在前，小端法低位在前。比如一個int類型16進制數據為0×1234567，大端法和小端法分別如下：
大端法和小端法沒有明顯的優劣，只要統一使用一種就不會有問題，如果不同字節序的計算機之間傳送數據，網絡應用程序就要做好轉換，將四字節大端法轉換為小端法如下：
閱讀更多 戚小柒說IT 的文章
