Golang 內存模型與分配機制
0 前言
未來兩週，想和大家探討的主題是 Golang 內存管理機制.
本系列會分爲兩篇，第一篇談及 Golang 內存模型以及內存分配機制，第二篇會和大家討論 Golang 的垃圾回收機制. 本文是其中第一篇.
我個人比較推崇” 基於源碼支撐原理 “的信念，所以本文在闡述原理的基礎上，會伴有大量源碼走讀的過程，作爲理論的支撐論證. 走讀的 Go 源碼版本爲 1.19.
內存管理與垃圾回收都屬 Go 語言最複雜的模塊，受限於筆者個人水平，文章內容可能有不足或紕漏之處，很歡迎大家添加我的個人 VX：xingyun19951212 進行批評指正.
1 內存模型
1.1 操作系統存儲模型
本文既然要聊到 Golang 的內存模型設計，就讓我們首先回顧操作系統中經典的多級存儲模型設計.
觀察上圖，我們可以從中捕捉到的關鍵詞是：
-
多級模型
-
動態切換
1.2 虛擬內存與物理內存
操作系統內存管理中，另一個重要概念是虛擬內存，其作用如下：
-
在用戶與硬件間添加中間代理層（沒有什麼是加一箇中間層解決不了的）
-
優化用戶體驗（進程感知到獲得的內存空間是 “連續” 的）
-
“放大” 可用內存（虛擬內存可以由物理內存 + 磁盤補足，並根據冷熱動態置換，用戶無感知）
1.3 分頁管理
操作系統中通常會將虛擬內存和物理內存切割成固定的尺寸，於虛擬內存而言叫作 “頁”，於物理內存而言叫作 “幀”，原因及要點如下：
-
提高內存空間利用（以頁爲粒度後，消滅了不穩定的外部碎片，取而代之的是相對可控的內部碎片）
-
提高內外存交換效率（更細的粒度帶來了更高的靈活度）
-
與虛擬內存機制呼應，便於建立虛擬地址 -> 物理地址的映射關係（聚合映射關係的數據結構，稱爲頁表）
-
linux 頁 / 幀的大小固定，爲 4KB（這實際是由實踐推動的經驗值，太粗會增加碎片率，太細會增加分配頻率影響效率）
1.4 Golang 內存模型
前幾小節的鋪墊，旨在從 “內存模型設計” 這件事情中收穫一些觸類旁通的設計理念.
下面步入正題，聊聊 Golang 的內存模型設計的幾個核心要點：
- 以空間換時間，一次緩存，多次複用
由於每次向操作系統申請內存的操作很重，那麼不妨一次多申請一些，以備後用.
Golang 中的堆 mheap 正是基於該思想，產生的數據結構. 我們可以從兩個視角來解決 Golang 運行時的堆：
I 對操作系統而言，這是用戶進程中緩存的內存
II 對於 Go 進程內部，堆是所有對象的內存起源
- 多級緩存，實現無 / 細鎖化
堆是 Go 運行時中最大的臨界共享資源，這意味着每次存取都要加鎖，在性能層面是一件很可怕的事情.
在解決這個問題，Golang 在堆 mheap 之上，依次細化粒度，建立了 mcentral、mcache 的模型，下面對三者作個梳理：
-
mheap：全局的內存起源，訪問要加全局鎖
-
mcentral：每種對象大小規格（全局共劃分爲 68 種）對應的緩存，鎖的粒度也僅限於同一種規格以內
-
mcache：每個 P（正是 GMP 中的 P）持有一份的內存緩存，訪問時無鎖
這些概念，我們在第 2 節中都會再作詳細展開，此處可以先不深究，注重於宏觀架構即可.
- 多級規格，提高利用率
首先理下 page 和 mspan 兩個概念：
（1）page：最小的存儲單元.
Golang 借鑑操作系統分頁管理的思想，每個最小的存儲單元也稱之爲頁 page，但大小爲 8 KB
（2）mspan：最小的管理單元.
mspan 大小爲 page 的整數倍，且從 8B 到 80 KB 被劃分爲 67 種不同的規格，分配對象時，會根據大小映射到不同規格的 mspan，從中獲取空間.
於是，我們回頭小節多規格 mspan 下產生的特點：
I 根據規格大小，產生了等級的制度
II 消除了外部碎片，但不可避免會有內部碎片
III 宏觀上能提高整體空間利用率
IV 正是因爲有了規格等級的概念，才支持 mcentral 實現細鎖化
- 全局總覽，留個印象
上圖是 Thread-Caching Malloc 的整體架構圖，Golang 正是借鑑了該內存模型. 我們先看眼架構，有個整體概念，後續小節中，我們會不斷對細節進行補充.
2 核心概念梳理
2.1 內存單元 mspan
分點闡述 mspan 的特質：
-
mspan 是 Golang 內存管理的最小單元
-
mspan 大小是 page 的整數倍（Go 中的 page 大小爲 8KB），且內部的頁是連續的（至少在虛擬內存的視角中是這樣）
-
每個 mspan 根據空間大小以及面向分配對象的大小，會被劃分爲不同的等級（2.2 小節展開）
-
同等級的 mspan 會從屬同一個 mcentral，最終會被組織成鏈表，因此帶有前後指針（prev、next）
-
由於同等級的 mspan 內聚於同一個 mcentral，所以會基於同一把互斥鎖管理
-
mspan 會基於 bitMap 輔助快速找到空閒內存塊（塊大小爲對應等級下的 object 大小），此時需要使用到 Ctz64 算法.
mspan 類的源碼位於 runtime/mheap.go 文件中：
type mspan struct {
// 標識前後節點的指針
next *mspan
prev *mspan
// ...
// 起始地址
startAddr uintptr
// 包含幾頁，頁是連續的
npages uintptr
// 標識此前的位置都已被佔用
freeindex uintptr
// 最多可以存放多少個 object
nelems uintptr // number of object in the span.
// bitmap 每個 bit 對應一個 object 塊，標識該塊是否已被佔用
allocCache uint64
// ...
// 標識 mspan 等級，包含 class 和 noscan 兩部分信息
spanclass spanClass
// ...
}
2.2 內存單元等級 spanClass
mspan 根據空間大小和麪向分配對象的大小，被劃分爲 67 種等級（1-67，實際上還有一種隱藏的 0 級，用於處理更大的對象，上不封頂）
下表展示了部分的 mspan 等級列表，數據取自 runtime/sizeclasses.go 文件中：
對上表各列進行解釋：
（1）class：mspan 等級標識，1-67
（2）bytes/obj：該大小規格的對象會從這一 mspan 中獲取空間. 創建對象過程中，大小會向上取整爲 8B 的整數倍，因此該表可以直接實現 object 到 mspan 等級 的映射
（3）bytes/span：該等級的 mspan 的總空間大小
（4）object：該等級的 mspan 最多可以 new 多少個對象，結果等於 （3）/（2）
（5）tail waste：（3）/（2）可能除不盡，於是該項值爲（3）%（2）
（6）max waste：通過下面示例解釋：
以 class 3 的 mspan 爲例，class 分配的 object 大小統一爲 24B，由於 object 大小 <= 16B 的會被分配到 class 2 及之前的 class 中，因此只有 17B-24B 大小的 object 會被分配到 class 3.
最不利的情況是，當 object 大小爲 17B，會產生浪費空間比例如下：
((24-17)*341 + 8)/8192 = 0.292358 ≈ 29.24%除了上面談及的根據大小確定的 mspan 等級外，每個 object 還有一個重要的屬性叫做 nocan，標識了 object 是否包含指針，在 gc 時是否需要展開標記.
在 Golang 中，會將 span class + nocan 兩部分信息組裝成一個 uint8，形成完整的 spanClass 標識. 8 個 bit 中，高 7 位表示了上表的 span 等級（總共 67 + 1 個等級，8 個 bit 足夠用了），最低位表示 nocan 信息.
代碼位於 runtime/mheap.go
type spanClass uint8
// uint8 左 7 位爲 mspan 等級，最右一位標識是否爲 noscan
func makeSpanClass(sizeclass uint8, noscan bool) spanClass {
return spanClass(sizeclass<<1) | spanClass(bool2int(noscan))
}
func (sc spanClass) sizeclass() int8 {
return int8(sc >> 1)
}
func (sc spanClass) noscan() bool {
return sc&1 != 0
}
2.3 線程緩存 mcache
要點：
（1）mcache 是每個 P 獨有的緩存，因此交互無鎖
（2）mcache 將每種 spanClass 等級的 mspan 各緩存了一個，總數爲 2（nocan 維度） * 68（大小維度）= 136
（3）mcache 中還有一個爲對象分配器 tiny allocator，用於處理小於 16B 對象的內存分配，在 3.3 小節中詳細展開.
代碼位於 runtime/mcache.go：
const numSpanClasses = 136
type mcache struct {
// 微對象分配器相關
tiny uintptr
tinyoffset uintptr
tinyAllocs uintptr
// mcache 中緩存的 mspan，每種 spanClass 各一個
alloc [numSpanClasses]*mspan
// ...
}
2.4 中心緩存 mcentral
要點：
（1）每個 mcentral 對應一種 spanClass
（2）每個 mcentral 下聚合了該 spanClass 下的 mspan
（3）mcentral 下的 mspan 分爲兩個鏈表，分別爲有空間 mspan 鏈表 partial 和滿空間 mspan 鏈表 full
（4）每個 mcentral 一把鎖
代碼位於 runtime/mcentral.go
type mcentral struct {
// 對應的 spanClass
spanclass spanClass
// 有空位的 mspan 集合，數組長度爲 2 是用於抗一輪 GC
partial [2]spanSet
// 無空位的 mspan 集合
full [2]spanSet
}
2.5 全局堆緩存 mheap
要點：
-
對於 Golang 上層應用而言，堆是操作系統虛擬內存的抽象
-
以頁（8KB）爲單位，作爲最小內存存儲單元
-
負責將連續頁組裝成 mspan
-
全局內存基於 bitMap 標識其使用情況，每個 bit 對應一頁，爲 0 則自由，爲 1 則已被 mspan 組裝
-
通過 heapArena 聚合頁，記錄了頁到 mspan 的映射信息（2.7 小節展開）
-
建立空閒頁基數樹索引 radix tree index，輔助快速尋找空閒頁（2.6 小節展開）
-
是 mcentral 的持有者，持有所有 spanClass 下的 mcentral，作爲自身的緩存
-
內存不夠時，向操作系統申請，申請單位爲 heapArena（64M）
代碼位於 runtime/mheap.go
type mheap struct {
// 堆的全局鎖
lock mutex
// 空閒頁分配器，底層是多棵基數樹組成的索引，每棵樹對應 16 GB 內存空間
pages pageAlloc
// 記錄了所有的 mspan. 需要知道，所有 mspan 都是經由 mheap，使用連續空閒頁組裝生成的
allspans []*mspan
// heapAreana 數組，64 位系統下，二維數組容量爲 [1][2^22]
// 每個 heapArena 大小 64M，因此理論上，Golang 堆上限爲 2^22*64M = 256T
arenas [1 << arenaL1Bits]*[1 << arenaL2Bits]*heapArena
// ...
// 多個 mcentral，總個數爲 spanClass 的個數
central [numSpanClasses]struct {
mcentral mcentral
// 用於內存地址對齊
pad [cpu.CacheLinePadSize - unsafe.Sizeof(mcentral{})%cpu.CacheLinePadSize]byte
}
// ...
}
2.6 空閒頁索引 pageAlloc
與 mheap 中，與空閒頁尋址分配的基數樹索引有關的內容較爲晦澀難懂. 網上能把這個問題真正講清楚的文章幾乎沒有.
所幸我最後找到這個數據結構的作者發佈的筆記，終於對方案的原貌有了大概的瞭解，這裏粘貼鏈接，供大家自取：https://go.googlesource.com/proposal/+/master/design/35112-scaling-the-page-allocator.md
要理清這棵技術樹，首先需要明白以下幾點：
（1）數據結構背後的含義：
I 2.5 小節有提及，mheap 會基於 bitMap 標識內存中各頁的使用情況，bit 位爲 0 代表該頁是空閒的，爲 1 代表該頁已被 mspan 佔用.
II 每棵基數樹聚合了 16 GB 內存空間中各頁使用情況的索引信息，用於幫助 mheap 快速找到指定長度的連續空閒頁的所在位置
III mheap 持有 2^14 棵基數樹，因此索引全面覆蓋到 2^14 * 16 GB = 256 T 的內存空間.
（2）基數樹節點設定
基數樹中，每個節點稱之爲 PallocSum，是一個 uint64 類型，體現了索引的聚合信息，包含以下四部分：
-
start：最右側 21 個 bit，標識了當前節點映射的 bitMap 範圍中首端有多少個連續的 0 bit（空閒頁），稱之爲 start；
-
max：中間 21 個 bit，標識了當前節點映射的 bitMap 範圍中最多有多少個連續的 0 bit（空閒頁），稱之爲 max；
-
end：左側 21 個 bit，標識了當前節點映射的 bitMap 範圍中最末端有多少個連續的 0 bit（空閒頁），稱之爲 end.
-
最左側一個 bit，棄置不用
（3）父子關係
-
每個父 pallocSum 有 8 個子 pallocSum
-
根 pallocSum 總覽全局，映射的 bitMap 範圍爲全局的 16 GB 空間（其 max 最大值爲 2^21，因此總空間大小爲 2^21*8KB=16GB）；
-
從首層向下是一個依次八等分的過程，每一個 pallocSum 映射其父節點 bitMap 範圍的八分之一，因此第二層 pallocSum 的 bitMap 範圍爲 16GB/8 = 2GB，以此類推，第五層節點的範圍爲 16GB / (8^4) = 4 MB，已經很小
-
聚合信息時，自底向上. 每個父 pallocSum 聚合 8 個子 pallocSum 的 start、max、end 信息，形成自己的信息，直到根 pallocSum，坐擁全局 16 GB 的 start、max、end 信息
-
mheap 尋頁時，自頂向下. 對於遍歷到的每個 pallocSum，先看起 start 是否符合，是則尋頁成功；再看 max 是否符合，是則進入其下層孩子 pallocSum 中進一步尋訪；最後看 end 和下一個同輩 pallocSum 的 start 聚合後是否滿足，是則尋頁成功.
代碼位於 runtime/mpagealloc.go
const summaryLevels = 5
type pageAlloc struct {
// 共有五層基數樹，第一層有 2^14 個節點，因此共用 2^14棵基數樹
// 總空間大小爲 2^14*16GB = 256T
// 接下來每層的節點數爲上層的 8 倍
summary [summaryLevels][]pallocSum
// ...
// 類似於 tiny offset，小於此值的地址無鎖檢索，必然沒有空間可用
searchAddr offAddr
// ...
}
基數樹節點
const(
logMaxPackedValue = 21
maxPackedValue = 1 << logMaxPackedValue
)
type pallocSum uint64
// 基於 start、max、end 組裝成一個基數樹節點 pallocSum
func packPallocSum(start, max, end uint) pallocSum {
// ...
return pallocSum((uint64(start) & (maxPackedValue - 1)) |
((uint64(max) & (maxPackedValue - 1)) << logMaxPackedValue) |
((uint64(end) & (maxPackedValue - 1)) << (2 * logMaxPackedValue)))
}
// 當前節點對應區域內，首部連續空閒頁的長度
// 通過 uint64 最右側 21 個 bit 標識
func (p pallocSum) start() uint {
// ...
return uint(uint64(p) & (maxPackedValue - 1))
}
// 當前節點對應區域內，連續空閒頁的最大長度
// 通過 uint64 左數 23~43 個 bit 標識
func (p pallocSum) max() uint {
// ...
return uint((uint64(p) >> logMaxPackedValue) & (maxPackedValue - 1))
}
// 當前節點對應區域內，尾部連續空閒頁的長度
// 通過 uint64 左數 2~22 個 bit 標識
func (p pallocSum) end() uint {
return uint((uint64(p) >> (2 * logMaxPackedValue)) & (maxPackedValue - 1))
}
2.7 heapArena
-
每個 heapArena 包含 8192 個頁，大小爲 8192 * 8KB = 64 MB
-
heapArena 記錄了頁到 mspan 的映射. 因爲 GC 時，通過地址偏移找到頁很方便，但找到其所屬的 mspan 不容易. 因此需要通過這個映射信息進行輔助.
-
heapArena 是 mheap 向操作系統申請內存的單位（64MB）
代碼位於 runtime/mheap.go
const pagesPerArena = 8192
type heapArena struct {
// ...
// 實現 page 到 mspan 的映射
spans [pagesPerArena]*mspan
// ...
}
3 對象分配流程
下面來串聯 Golang 中分配對象的流程，不論是以下哪種方式，最終都會殊途同歸步入 mallocgc 方法中，並且根據 3.1 小節中的策略執行分配流程：
-
new(T)
-
&T{}
-
make(xxxx)
3.1 分配流程總覽
Golang 中，依據 object 的大小，會將其分爲下述三類：
不同類型的對象，會有着不同的分配策略，這些內容在 mallocgc 方法中都有體現.
核心流程類似於讀多級緩存的過程，由上而下，每一步只要成功則直接返回. 若失敗，則由下層方法兜底.
對於微對象的分配流程：
（1）從 P 專屬 mcache 的 tiny 分配器取內存（無鎖）
（2）根據所屬的 spanClass，從 P 專屬 mcache 緩存的 mspan 中取內存（無鎖）
（3）根據所屬的 spanClass 從對應的 mcentral 中取 mspan 填充到 mcache，然後從 mspan 中取內存（spanClass 粒度鎖）
（4）根據所屬的 spanClass，從 mheap 的頁分配器 pageAlloc 取得足夠數量空閒頁組裝成 mspan 填充到 mcache，然後從 mspan 中取內存（全局鎖）
（5）mheap 向操作系統申請內存，更新頁分配器的索引信息，然後重複（4）.
對於小對象的分配流程是跳過（1）步，執行上述流程的（2）-（5）步；
對於大對象的分配流程是跳過（1）-（3）步，執行上述流程的（4）-（5）步.
3.2 主幹方法 mallocgc
先上道硬菜，malloc 方法主幹全流程展示.
如果覺得理解曲線太陡峭，可以先跳到後續小節，把拆解的各部分模塊都熟悉後，再回過頭來總覽一遍.
代碼位於 runtime/malloc.go 文件中：
func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {
// ...
// 獲取 m
mp := acquirem()
// 獲取當前 p 對應的 mcache
c := getMCache(mp)
var span *mspan
var x unsafe.Pointer
// 根據當前對象是否包含指針，標識 gc 時是否需要展開掃描
noscan := typ == nil || typ.ptrdata == 0
// 是否是小於 32KB 的微、小對象
if size <= maxSmallSize {
// 小於 16 B 且無指針，則視爲微對象
if noscan && size < maxTinySize {
// tiny 內存塊中，從 offset 往後有空閒位置
off := c.tinyoffset
// 如果大小爲 5 ~ 8 B，size 會被調整爲 8 B，此時 8 & 7 == 0，會走進此分支
if size&7 == 0 {
// 將 offset 補齊到 8 B 倍數的位置
off = alignUp(off, 8)
// 如果大小爲 3 ~ 4 B，size 會被調整爲 4 B，此時 4 & 3 == 0，會走進此分支
} else if size&3 == 0 {
// 將 offset 補齊到 4 B 倍數的位置
off = alignUp(off, 4)
// 如果大小爲 1 ~ 2 B，size 會被調整爲 2 B，此時 2 & 1 == 0，會走進此分支
} else if size&1 == 0 {
// 將 offset 補齊到 2 B 倍數的位置
off = alignUp(off, 2)
}
// 如果當前 tiny 內存塊空間還夠用，則直接分配並返回
if off+size <= maxTinySize && c.tiny != 0 {
// 分配空間
x = unsafe.Pointer(c.tiny + off)
c.tinyoffset = off + size
c.tinyAllocs++
mp.mallocing = 0
releasem(mp)
return x
}
// 分配一個新的 tiny 內存塊
span = c.alloc[tinySpanClass]
// 從 mCache 中獲取
v := nextFreeFast(span)
if v == 0 {
// 從 mCache 中獲取失敗，則從 mCentral 或者 mHeap 中獲取進行兜底
v, span, shouldhelpgc = c.nextFree(tinySpanClass)
}
// 分配空間
x = unsafe.Pointer(v)
(*[2]uint64)(x)[0] = 0
(*[2]uint64)(x)[1] = 0
size = maxTinySize
} else {
// 根據對象大小，映射到其所屬的 span 的等級(0~66）
var sizeclass uint8
if size <= smallSizeMax-8 {
sizeclass = size_to_class8[divRoundUp(size, smallSizeDiv)]
} else {
sizeclass = size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]
}
// 對應 span 等級下，分配給每個對象的空間大小(0~32KB)
size = uintptr(class_to_size[sizeclass])
// 創建 spanClass 標識，其中前 7 位對應爲 span 的等級(0~66)，最後標識表示了這個對象 gc 時是否需要掃描
spc := makeSpanClass(sizeclass, noscan)
// 獲取 mcache 中的 span
span = c.alloc[spc]
// 從 mcache 的 span 中嘗試獲取空間
v := nextFreeFast(span)
if v == 0 {
// mcache 分配空間失敗，則通過 mcentral、mheap 兜底
v, span, shouldhelpgc = c.nextFree(spc)
}
// 分配空間
x = unsafe.Pointer(v)
// ...
}
// 大於 32KB 的大對象
} else {
// 從 mheap 中獲取 0 號 span
span = c.allocLarge(size, noscan)
span.freeindex = 1
span.allocCount = 1
size = span.elemsize
// 分配空間
x = unsafe.Pointer(span.base())
}
// ...
return x
}
3.3 步驟（1）：tiny 分配
每個 P 獨有的 mache 會有個微對象分配器，基於 offset 線性移動的方式對微對象進行分配，每 16B 成塊，對象依據其大小，會向上取整爲 2 的整數次冪進行空間補齊，然後進入分配流程.
noscan := typ == nil || typ.ptrdata == 0
// ...
if noscan && size < maxTinySize {
// tiny 內存塊中，從 offset 往後有空閒位置
off := c.tinyoffset
// ...
// 如果當前 tiny 內存塊空間還夠用，則直接分配並返回
if off+size <= maxTinySize && c.tiny != 0 {
// 分配空間
x = unsafe.Pointer(c.tiny + off)
c.tinyoffset = off + size
c.tinyAllocs++
mp.mallocing = 0
releasem(mp)
return x
}
// ...
}
3.4 步驟（2）：mcache 分配
// 根據對象大小，映射到其所屬的 span 的等級(0~66）
var sizeclass uint8
// get size class ....
// 對應 span 等級下，分配給每個對象的空間大小(0~32KB)
// get span class
spc := makeSpanClass(sizeclass, noscan)
// 獲取 mcache 中的 span
span = c.alloc[spc]
// 從 mcache 的 span 中嘗試獲取空間
v := nextFreeFast(span)
if v == 0 {
// mcache 分配空間失敗，則通過 mcentral、mheap 兜底
v, span, shouldhelpgc = c.nextFree(spc)
}
// 分配空間
x = unsafe.Pointer(v)
在 mspan 中，基於 Ctz64 算法，根據 mspan.allocCache 的 bitMap 信息快速檢索到空閒的 object 塊，進行返回.
代碼位於 runtime/malloc.go 文件中：
func nextFreeFast(s *mspan) gclinkptr {
// 通過 ctz64 算法，在 bit map 上尋找到首個 object 空位
theBit := sys.Ctz64(s.allocCache)
if theBit < 64 {
result := s.freeindex + uintptr(theBit)
if result < s.nelems {
freeidx := result + 1
if freeidx%64 == 0 && freeidx != s.nelems {
return 0
}
s.allocCache >>= uint(theBit + 1)
// 偏移 freeindex
s.freeindex = freeidx
s.allocCount++
// 返回獲取 object 空位的內存地址
return gclinkptr(result*s.elemsize + s.base())
}
}
return 0
}
3.5 步驟（3）：mcentral 分配
當 mspan 無可用的 object 內存塊時，會步入 mcache.nextFree 方法進行兜底.
代碼位於 runtime/mcache.go 文件中：
func (c *mcache) nextFree(spc spanClass) (v gclinkptr, s *mspan, shouldhelpgc bool) {
s = c.alloc[spc]
// ...
// 從 mcache 的 span 中獲取 object 空位的偏移量
freeIndex := s.nextFreeIndex()
if freeIndex == s.nelems {
// ...
// 倘若 mcache 中 span 已經沒有空位，則調用 refill 方法從 mcentral 或者 mheap 中獲取新的 span
c.refill(spc)
// ...
// 再次從替換後的 span 中獲取 object 空位的偏移量
s = c.alloc[spc]
freeIndex = s.nextFreeIndex()
}
// ...
v = gclinkptr(freeIndex*s.elemsize + s.base())
s.allocCount++
// ...
return
}
倘若 mcache 中，對應的 mspan 空間不足，則會在 mcache.refill 方法中，向更上層的 mcentral 乃至 mheap 獲取 mspan，填充到 mache 中:
代碼位於 runtime/mcache.go 文件中：
func (c *mcache) refill(spc spanClass) {
s := c.alloc[spc]
// ...
// 從 mcentral 當中獲取對應等級的 span
s = mheap_.central[spc].mcentral.cacheSpan()
// ...
// 將新的 span 添加到 mcahe 當中
c.alloc[spc] = s
}
mcentral.cacheSpan 方法中，會加鎖（spanClass 級別的 sweepLocker），分別從 partial 和 full 中嘗試獲取有空間的 mspan:
代碼位於 runtime/mcentral.go 文件中：
func (c *mcentral) cacheSpan() *mspan {
// ...
var sl sweepLocker
// ...
sl = sweep.active.begin()
if sl.valid {
for ; spanBudget >= 0; spanBudget-- {
s = c.partialUnswept(sg).pop()
// ...
if s, ok := sl.tryAcquire(s); ok {
// ...
sweep.active.end(sl)
goto havespan
}
// 通過 sweepLock，加鎖嘗試從 mcentral 的非空鏈表 full 中獲取 mspan
for ; spanBudget >= 0; spanBudget-- {
s = c.fullUnswept(sg).pop()
// ...
if s, ok := sl.tryAcquire(s); ok {
// ...
sweep.active.end(sl)
goto havespan
}
// ...
}
}
// ...
}
// ...
// 執行到此處時，s 已經指向一個存在 object 空位的 mspan 了
havespan:
// ...
return
}
3.6 步驟（4）：mheap 分配
在 mcentral.cacheSpan 方法中，倘若從 partial 和 full 中都找不到合適的 mspan 了，則會調用 mcentral 的 grow 方法，將事態繼續升級：
func (c *mcentral) cacheSpan() *mspan {
// ...
// mcentral 中也沒有可用的 mspan 了，則需要從 mheap 中獲取，最終會調用 mheap_.alloc 方法
s = c.grow()
// ...
// 執行到此處時，s 已經指向一個存在 object 空位的 mspan 了
havespan:
// ...
return
}
經由 mcentral.grow 方法和 mheap.alloc 方法的週轉，最終會步入 mheap.allocSpan 方法中：
func (c *mcentral) grow() *mspan {
npages := uintptr(class_to_allocnpages[c.spanclass.sizeclass()])
size := uintptr(class_to_size[c.spanclass.sizeclass()])
s := mheap_.alloc(npages, c.spanclass)
// ...
// ...
return s
}
代碼位於 runtime/mheap.go
func (h *mheap) alloc(npages uintptr, spanclass spanClass) *mspan {
var s *mspan
systemstack(func() {
// ...
s = h.allocSpan(npages, spanAllocHeap, spanclass)
})
return s
}
代碼位於 runtime/mheap.go
func (h *mheap) allocSpan(npages uintptr, typ spanAllocType, spanclass spanClass) (s *mspan) {
gp := getg()
base, scav := uintptr(0), uintptr(0)
// ...此處實際上還有一階緩存，是從每個 P 的頁緩存 pageCache 中獲取空閒頁組裝 mspan，此處先略去了...
// 加上堆全局鎖
lock(&h.lock)
if base == 0 {
// 通過基數樹索引快速尋找滿足條件的連續空閒頁
base, scav = h.pages.alloc(npages)
// ...
}
// ...
unlock(&h.lock)
HaveSpan:
// 把空閒頁組裝成 mspan
s.init(base, npages)
// 將這批頁添加到 heapArena 中，建立由頁指向 mspan 的映射
h.setSpans(s.base(), npages, s)
// ...
return s
}
倘若對 mheap 空閒頁分配器基數樹 pageAlloc 分配空閒頁的源碼感興趣，莫慌，3.8 小節見.
3.7 步驟（5）：向操作系統申請
倘若 mheap 中沒有足夠多的空閒頁了，會發起 mmap 系統調用，向操作系統申請額外的內存空間.
代碼位於 runtime/mheap.go 文件的 mheap.grow 方法中：
func (h *mheap) grow(npage uintptr) (uintptr, bool) {
av, asize := h.sysAlloc(ask)
}
func (h *mheap) sysAlloc(n uintptr) (v unsafe.Pointer, size uintptr) {
v = sysReserve(unsafe.Pointer(p), n)
}
func sysReserve(v unsafe.Pointer, n uintptr) unsafe.Pointer {
return sysReserveOS(v, n)
}
func sysReserveOS(v unsafe.Pointer, n uintptr) unsafe.Pointer {
p, err := mmap(v, n, _PROT_NONE, _MAP_ANON|_MAP_PRIVATE, -1, 0)
if err != 0 {
return nil
}
return p
}
3.8 步驟（4）拓展：基數樹尋頁
核心源碼位於 runtime/pagealloc.go 的 pageAlloc 方法中，要點都以在代碼中給出註釋：
func (p *pageAlloc) find(npages uintptr) (uintptr, offAddr) {
// 必須持有堆鎖
assertLockHeld(p.mheapLock)
// current level.
i := 0
// ...
lastSum := packPallocSum(0, 0, 0)
lastSumIdx := -1
nextLevel:
// 1 ~ 5 層依次遍歷
for l := 0; l < len(p.summary); l++ {
// ...
// 根據上一層的 index，映射到下一層的 index.
// 映射關係示例：上層 0 -> 下層 [0~7]
// 上層 1 -> 下層 [8~15]
// 以此類推
i <<= levelBits[l]
entries := p.summary[l][i : i+entriesPerBlock]
// ...
// var levelBits = [summaryLevels]uint{
// 14,3,3,3,3
// }
// 除第一層有 2^14 個節點外，接下來每層都只要關心 8 個 節點.
// 由於第一層有 2^14 個節點，所以 heap 內存上限爲 2^14 * 16G = 256T
var base, size uint
for j := j0; j < len(entries); j++ {
sum := entries[j]
// ...
// 倘若當前節點對應內存空間首部即滿足，直接返回結果
s := sum.start()
if size+s >= uint(npages) {
if size == 0 {
base = uint(j) << logMaxPages
}
size += s
break
}
// 倘若當前節點對應內存空間首部不滿足，但是內部最長連續頁滿足，則到下一層節點展開搜索
if sum.max() >= uint(npages) {
i += j
lastSumIdx = i
lastSum = sum
continue nextLevel
}
// 即便內部最長連續頁不滿足，還可以嘗試將尾部與下個節點的首部疊加，看是否滿足
if size == 0 || s < 1<<logMaxPages {
size = sum.end()
base = uint(j+1)<<logMaxPages - size
continue
}
// The entry is completely free, so continue the run.
size += 1 << logMaxPages
}
// 根據 i 和 j 可以推導得到對應的內存地址，進行返回
ci := chunkIdx(i)
addr := chunkBase(ci) + uintptr(j)*pageSize
// ...
return addr, p.findMappedAddr(firstFree.base)
}
4 展望
祝賀，到此爲止，整個 Golang 內存分配流程已經梳理完畢.
兩週內，我會帶來新作——Golang 垃圾回收機制.
Go 友們不見不散~
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/2TBwpQT5-zU4Gy7-i0LZmQ