內存分配器一直是性能優化的重頭戲，其結構複雜、內容抽象，涉及的數據結構繁多，相信很多人都曾被它搞瘋了。本文將從內存的基本知識入手，到一般的內存分配器，進而延伸到 Go 內存分配器，對其進行全方位深層次的講解，希望能讓你對進程內存管理有一個全新的認識。

物理內存 VS 虛擬內存

在研究內存分配器之前，讓我們先看一下物理內存和虛擬內存的背景知識。劇透一下，內存分配器實際上操作的不是物理內存而是虛擬內存。

物理內存細胞結構簡化圖

內存細胞作為物理內存結構的最小單元，工作原理如下：

1. 地址線（三相晶體管）其實是連接數據線與數據電容的三相開關。
2. 當地址線負載時（紅線），數據線開始向電容中寫數據，電容處於充電狀態，邏輯值變為 1
3. 當地址線空載時（綠線），數據線不能向電容中寫數據，電容處於未充電狀態，邏輯值為 0
4. 當 CPU 從 RAM 中讀值時，它首先會給地址線發送一個電流信號從而合上開關，連通數據電路。這時如果電容處於高電位，則電容中的電流會流向數據線，CPU 讀數為 1；否則，數據線中沒有電流負載，CPU 讀數為 0。

CPU 和內存的交互

CPU 實際上通過地址總線、數據總線和控制總線實現對內存的訪問。

• 數據總線：在 CPU 和內存之間傳遞數據的通道；
• 控制總線：在 CPU 和內存之間傳遞各種控制 / 狀態信號的通道；
• 地址總線： 傳送地址信號，以確定所要訪問的內存地址。

讓我們進一步分析一下地址線和按字節尋址：

1. 在 DRAM 中，每一個字節都有一個唯一的地址。“可尋址字節不一定等於地址線的數量”，
2. 例如 16 位的 Intel 8088、PAE（物理地址擴展）等，其物理字節大於地址線數量。
3. 每一條地址線可以傳送 1-bit 的數值，可表示尋址字節中的一位。
4. 圖中有 32 位地址線，所以可認為可尋址字節是 32 位的。

[ 00000000000000000000000000000000 ] —低位內存地址。

[ 11111111111111111111111111111111 ] — 高位內存地址。

4. 因為上圖物理字節有 32 條地址線，所以其尋址空間大小為 2 的 32 次方，也就是 4GB

可尋址字節的大小其實取決於地址線的數量，例如具有 64 個地址線的 CPU（x86–64 處理器）可以尋址 2 的 64 次方，但是目前大多數 64 位的 CPU 其實只使用了其中的 48 位（AMD）或者 42 位（Intel）。儘管理論上可訪問 2 的 64 次方（256TB）大小的地址空間，但是通常操作系統並沒有完全支持它們（Linux 的四層頁表結構允許處理器訪問 128TB 大小的地址空間，Windows 支持 192TB）。

由於實際物理內存的大小是有限制的，所以每個進程都運行在各自的沙盒中，也就是所謂的“虛擬地址空間”，簡稱虛擬內存。

虛擬內存中的字節地址其實並不是實際的物理地址。操作系統需要記錄所有虛擬地址到物理地址的映射轉換，也就是我們熟知的頁表。

進程中的虛擬地址如下圖所示：

虛擬地址空間示意圖

所以當 CPU 執行內存中一條指令的時候，它首先需要把 VMA（虛擬內存區域）中的邏輯地址轉換為線性地址，轉化過程通過 MMU（內存管理單元）實現。

虛擬地址與實際物理地址的映射

由於邏輯地址太大很難被有效地管理，於是引入了頁（page）的概念。所有的虛擬內存空間被分成很多相對較小的區域（通常為 4KB），也就是我們所稱的頁。頁是虛擬內存管理中最小的單位，虛擬內存通常不存儲任何內容，只是簡單的將程序地址空間映射到底層的物理地址。

用戶進程只能使用虛擬內存地址。讓我們來看一下程序如何申請堆內存空間：

（堆內存申請的彙編實現）

堆內存增長

程序通常使用系統調用brk(sbrk/mmap) 來獲取更多的內存，內核僅更新堆的 VMA，並沒有進行進行實際的申請操作。

內存分配器

相信通過前面對“虛擬地址空間”以及堆內存申請的學習，相信我們對內存分配器說也就不難理解了。

當然內存分配器的職責不僅僅是更新 brk 地址，更多的還是用於減少碎片以及快速分配內存塊。讓我們來看一個實例：假設我們的程序通過函數 malloc 來申請一塊連續內存塊，使用函數 free 來釋放申請的內存塊，步驟 p1 到 p4 的整個操作順序如下：

內存碎片演示

到步驟 p4 的時候，儘管剩餘的內存塊數量大於需要申請的數量，但是因為碎片的關係，我們已經不能獲得 6 個連續的內存塊了。我們該如何減少內存碎片呢？答案要取決於具體使用的分配算法。

由於 Go 內存分配器同 TCMalloc 分配器非常相似，我們先看一下相對簡單的 TCMalloc。

TCMalloc

TCMalloc（Thread Cache Malloc）的核心思想是將內存分解為多層，從而減小內存鎖的粒度。TC-Malloc 內存管理分為線程內存以及頁堆兩部分：

線程內存

為減少內存碎片，每個內存頁都被分成了多個固定類大小的空閒列表。這樣每一個線程都都有一個不帶鎖的小對象緩存，從而可以高效的為並行程序分配小對象（<=32KB）。

線程緩存 (每個線程都有一個本地線程緩存)

頁堆

TCMalloc 管理的堆其實由一組頁構成，而這樣一組連續的頁又被稱為頁堆（span）。當我們申請大於 32K 的對象時，TCMalloc 將使用頁堆進行分配。

頁堆 （span）管理

當沒有足夠的內存來分配小對象時，將使用頁堆內存；而如果頁堆內存也不不能滿足時，將會向操作系統申請更多的內存。這種基於用戶空間內存池的管理模式極大地提高了內存分配和釋放的效率。

Go 內存分配器

Go 運行時調度器其實把 Goroutines (G) 綁定到邏輯處理器（P）上執行。同 TCMalloc 一樣，Go 內存分配器將內存頁分成了 67 個不同類大小的塊。

Go 中的內存頁大小列表

Go 中內存的最小粒度為 8KB，如果頁被分成大小為 1KB 的塊，那麼將會有如下 8 個塊。

8 KB 的頁被成了 8 個大小為 1KB 的塊

Go 通過數據結構 mspan 來管理這些頁。

mspan

簡單來講，mspan 是一個雙端鏈表，包含了頁起始地址，span 類以及這個類中頁的數量。

mspan 示意圖

mcache

同 TCMalloc 一樣，Go 內存分配器為每一個邏輯處理器§提供了一個本地線程緩存，也就是 mcache。如果 Goroutine 需要內存，可以直接從 mcache 中獲取，由於只有一個 Goroutine 運行在邏輯處理器（P）上，所以中間不需要使用任何鎖。

mcache 包含了所有類大小的 mspan。

Go 中 P、mcache 以及 mspan 的關係示意圖

每一種類大小的 mspan 都有兩種類型：

1. scan — 含有指針的對象。
2. noscan — 沒有指針的對象。

這樣分類的好處是在垃圾回收的時候，不需要遍歷 noscan 對象（noscan 中根本就沒有指針）。

那什麼情況下內存分配器會從 mcache 中申請內存呢?

• <=32K 字節的對象將直接從 mchae 中相應大小的 mspan 申請。*

如果 mcache 沒有可用空間的時候會怎麼樣?

將會從 mcentra 中相應大小的 mspanl 列表中分配一個新的 mspan。

mcentral

mcentral 對象收集了所有給定類大小的 span，每一個 mcentral 都包含了兩個 mspan 列表：

1. empty mspanList — 沒有空閒對象或者已經被 mcache 緩存的 mspans 列表。
2. noempty mspanList — 所有空閒對象的 span 列表。

mcentral 結構示意圖

每一個 mcentral 結構體都由 mheap 結構體維護。

mheap

mheap 示意圖

如上圖所示：mheap 保存了一個 mcentral 的數組，而 mcentral 又保存了所有 span。

複製代碼

central [numSpanClasses]struct {
 	mcentral mcentral
 	pad [sys.CacheLineSize unsafe.Sizeof(mcentral{})%sys.CacheLineSize]byte
}

Padding（對齊填充）確保了 mcentrals 按照 CacheLine 的大小對齊，所以每一個 MCentral.lock 都可以獲得自己的的 cache line，避免了偽共享問題。

如果 mcentral 為空會發生什麼呢？mcentral 會從 mheap 中申請一些頁來創建不同大小的 span。

• free[_MaxMHeapList]mSpanList: 一個 spanList 數組。每一個 spanList 中的 mspan 都包含了 1 ~ 127 個頁 (_MaxMHeapList - 1) 。例如，free[3] 是一個包含了 3 個頁的 mspan 鏈表，Free 表示列表為空，未分配，對應 busy list。
• freelarge mSpanList: 一個 mspan 列表。每一個元素的頁數大於 127。通過數據結構 mtreap 來管理，對應 busylarge。

• 小於 16B，使用 mcache 的 Tiny 分配。
• 大小介於 16B 和 32k，計算 sizeClass 的大小，然後在 mcache 中申請相應大小的內存塊。
• 大於 32k 的大對象, 直接從 mheap 中分配。
• 如果 mcache 中找不到相應大小的內存塊，則轉向 mcentral 申請。
• 如果 mcentral 中也沒有相應大小的內存塊，則轉向 mheap 申請，使用 BestFit 策略找尋最合適的 mspan；如果申請到的 mspan 太大，則根據用戶的需求進行切分，剩餘的頁構成一個新的 mspan，並放回到 mheap 的空閒列表。
• 如果 mheap 中沒有可用的 span，將會直接向操作系統申請新的內存頁（至少 1M）

所有在在堆上申請的內存都來自 arena，讓我們接下來看一看 arean：

Go 虛擬內存：Arena

讓我們通過一個簡單的 Go 程序來看一下內存使用情況：

複製代碼

func main() {
 for {}
}

程序進程信息統計

即便是隻有三行的小程序也使用了大約 100MB 的虛擬內存，但 RSS（實際物理內存佔用大小）

僅為 696KB。讓我們先看一下兩者的區別：

map 和 smap 統計

這裡有一些大小為 2MB、32MB 和 64MB 的內存區域，這些區域其實就是 arena 內存塊。

Go 的虛擬內存其實由一系列的 arena 構成，初始堆映射也是一個 arena，如 go 1.11.5

採用了 64MB 的 arena 內存塊。

不同系統中 arena 大小

當前 Go 內存分配器是按照程序需要逐步增加內存映射的，初始只預留留了一個 arena 的大小（約 64MB）。而早期的 Go 內存分配器會先保留一大段虛擬內存，在 64 位系統上為 512GB（發散問題：如果申請的內存太大，以至於被 mmap 拒絕了怎麼辦？）

這些 arena 就是我們所說的堆。Go 中每一個 arena 都按照 8KB 的粒度進行管理。

單個 arena ( 64 MB )

Go 同時還有兩個其它塊：span 和 bitmap。兩者都獨立於堆內存空間之外，並且保存了所有 arena 的元數據。他們主要在垃圾回收的時候使用，我們暫且不在這裡討論。

結語

我們剛剛討論的內存分配策略只是眾多內存分配器的冰山一角。但其管理核心本質上是一致的：針對不同大小的對象，在不同的 cache 層中，使用不同的內存結構；將從系統中獲得的一塊連續內存分割成多層次的 cache，以減少鎖的使用以提高內存分配效率；申請不同類大小的內存塊來減少內存碎片，同時加速內存釋放後的垃圾回收。

最後讓我們用 GO 內存分配器的結構示意圖作為結束：

內存分配器示意圖

英文原文地址：https://blog.learngoprogramming.com/a-visual-guide-to-golang-memory-allocator-from-ground-up-e132258453ed

閱讀更多 InfoQ 的文章

關鍵字: 數據結構 英特爾 分配器