計算機體系 – 棧與堆

（點選上方公眾號，可快速關註）

來源：MRRiddler ，

blog.mrriddler.com/2017/05/01/計算機體系-棧與堆/

繼上篇講述了虛擬儲存器和行程以後，程式終於乖乖“開始”運行了。此篇就來聊聊程式如何“持續”執行，繼續來看看what’s beyond the scene。

棧

作為一名有政治覺悟的、堅持政治思想正確的、胸口飄揚鮮紅的工卡的程式員，我們要謹記這句話：

沒有黨就沒有新中國，沒有棧就沒有過程呼叫。

是的，棧就是過程呼叫的基礎。為保證順利的過程呼叫，棧主要做了以下四點：

• 儲存函式引數。

• 儲存傳回地址。

• 儲存暫存器。

• 調整幀指標(ebp)和棧指標(esp)。

儲存函式引數這是必須的，不多說了，當然有可能是暫存器儲存，具體細節下麵會聊到。儲存傳回地址，儲存call指令的下一條指令的地址，ret指令會傳回這一地址。儲存暫存器這一步，主要是為了防止被呼叫者改寫呼叫者的暫存器。而幀指標和棧指標之間的空間就是本次棧幀的空間，調整這兩個指標以訪問空間。

常見的棧結構如下：

        —— —— —— —— —— —— ——   ——        high

       |…..                |       |

       |—— —— —— —— —— —— —— |       |    

       |引數n                |       |

       |—— —— —— —— —— —— —— |       |         

       |…..                |       |——>呼叫者棧 

       |—— —— —— —— —— —— —— |       |

       |引數1                |       | 

       |—— —— —— —— —— —— —— |       |

       |傳回地址              |      | 

ebp—>|—— —— —— —— —— —— —— |——-

       |被儲存的ebp           |      |

       |—— —— —— —— —— —— —— |      |

       |被儲存的暫存器和       |      | 

       |區域性變數              |      |——->被呼叫者棧幀

       |—— —— —— —— —— —— —— |      |

       |其他資料              |      |

esp—>|—— —— —— —— —— —— —— |——-       low

過程呼叫可以分為三個部分，初始化棧幀、主體、銷毀棧幀。初始化棧幀和銷毀棧幀部分涉及到的就是棧主要做的四點。主體部分涉及到的就是使用棧幀的部分。

常見的過程呼叫彙編如下：

call xxx               儲存傳回地址，並跳轉到過程起始地址

push ebp               儲存幀指標

mov ebp esp            調整幀指標

push 被儲存的暫存器     儲存暫存器

sub esp xxx            調整棧指標，分配幀棧。

……                 主體

mov eax xxx            傳回值放入eax

pop 被儲存的暫存器      取出被儲存的暫存器

mov esp ebp            調整棧指標

pop ebp                取出幀指標

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：

struct S1 {

  int i;

  char c;

  long l;

}

按照第一條，long型別的元素l，起始offset是8而不是5。按照第二條，S1要對8進行對齊。

而如下Struct:

struct S2 {

  int i;

  int j;

  char c;

}

按照第三條，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是否空閑。這樣一個典型的組織如下：

31    …..    3 2 1 0

 ——————–

|  chunk size  |free |

|——————–|

|       payload      |

|——————–|

|       padding      |

 ——————–

透過每個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組織更改如下：

31    …..    3 2 1 0

 ——————–

|  chunk size  |free |

|——————–|

|       payload      |

|——————–|

|       padding      |

|——————–|

|       footer       |

 ——————–

可以看到metadata和footer為8位元組，payload加上padding大小必定是8的整數倍。

這裡還有一個原因不使用新增prev前向指標域解決問題。在查詢合適chunk的時候，需要查詢所有chunk，完全不需要這樣做。可以為所有free的chunk新增一個指向前一個free chunk的prev域，一個指向後一個free chunk的next域，來降低吞吐率，最後chunk組織更改如下：

31    …..    3 2 1 0

 ——————–

|  chunk size  |free |

|——————–|

|       prev         |

|——————–|

|       next         |

|——————–|

|       payload      |

|——————–|

|       padding      |

|——————–|

|       footer       |

 ——————–

更多

具體實現，這裡就不多聊了，可以看CSAPP和這篇文章，看這篇文章的時候，可以對照著英文原版去看，文章中free函式中的b->prev->prev敲錯了，應該是b->prev->next。

當然，還有更多的堆管理器設計方式，比如說用點陣圖。還有一種比較有趣的分離儲存(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，大端法和小端法分別如下：

01 23 45 67 — big endian

67 45 23 01 — little endian

大端法和小端法沒有明顯的優劣，只要統一使用一種就不會有問題，如果不同位元組序的計算機之間傳送資料，網路應用程式就要做好轉換，將四位元組大端法轉換為小端法如下：

static unsigned int swap_bigendian_to_littleendian_Four_Byte(unsigned int value) {

    return (unsigned int)((value & 0x000000FF) << 24) 

      | (unsigned int)((value & 0x0000FF00) << 16)

      | (unsigned int)((value & 0x00FF0000) << 8) 

      | (unsigned int)((value & 0xFF000000) >> 24);

}

更多位元組序問題推薦這篇文章。

推薦文章

• 實用Calling Convention http://blog.cnbang.net/tech/3219/

• 位元組對齊(一) http://sysfork.com/post/about-cpp-alignment/

• 位元組對齊(二) http://opass.logdown.com/posts/743054-about-memory-alignment

看完本文有收穫？請轉發分享給更多人

關註「ImportNew」，提升Java技能