最早學習C、C++語言時,它們都是把記憶體的管理全部交給開發者,這種方式最靈活但是也最容易出問題,對人員要求極高;後來出現的一些進階語言像Java、JavaScript、C#、Go,都有語言自身解決了記憶體配置設定和回收問題,降低開發門檻,釋放生産力。然而對于想要深入了解原理的同學來說卻帶來了負擔,本篇文章主要從記憶體配置設定角度來梳理個人了解,後續文章中會介紹Go的垃圾回收機制。
程序的記憶體空間
- 程式檔案段(.text),包括二進制可執行代碼;
- 已初始化資料段(.data),包括靜态常量;
- 未初始化資料段(.bss),包括未初始化的靜态變量;(bss與data一般作為靜态存儲區)
- 堆段,包括動态配置設定的記憶體,從低位址開始向上增長;
- 檔案映射段,包括動态庫、共享記憶體等,從低位址開始向上增長(跟硬體和核心版本有關 (opens new window));
- 棧段,包括局部變量和函數調用的上下文等。棧的大小是固定的,一般是 8 MB。當然系統也提供了參數,以便我們自定義大小;
(以上來自小林coding)
上面是以程序為機關的視圖,程序中可能有多個線程,每個線程的棧空間是獨立的,但是都位于程序的棧區域中,而程序的堆區這是所有線程共享的,如下圖所示
Go語言中的GMP管理機制來說,隻有M對應的是作業系統中的線程,是以goroutine中是保留了必要的(rp、bp、pc指針),當goroutine執行時,對應到指定的棧空間位址區中。
說的有點遠,回到本文主題。
記憶體配置設定一般有三種方式:靜态存儲區(根對象、靜态變量、常量)、棧(函數中的臨時局部變量)、堆(malloc、new等);
一般最長讨論的是棧和堆,棧的特點可以認為是線性記憶體,管理簡單,配置設定比堆上更快,棧上配置設定的記憶體一般不需要程式員關心,程式語言都有專門的棧幀來管理(一般來說線程的棧空間是2M有的是8M,不能變化超過會崩潰,Go語言中goroutine是2kb,Go語言來有自己的棧擴容和縮容能力,64位系統超過1G則會崩潰)。(這裡說的線性記憶體其實在真實的機器實體記憶體中并不一定連續,這是因為作業系統提供了虛拟記憶體,讓各個程式看起來是獨占整個實體記憶體,實際上對程式來說連續的位址空間,在作業系統視角下未必是連續的,可以參考這篇文章)
因為堆區是多個線程共用的,是以就需要一套機制來進行配置設定(考慮記憶體碎片、公平性、沖突解決);不同的記憶體配置設定管理方式的适用場景都不同。在詳細講解Go記憶體配置設定政策之前,我們先來看一個簡單的記憶體配置設定。
堆記憶體配置設定
堆記憶體在最開始時時連續的,當程式運作過程中大家都去堆中申請自己的使用空間,如果不做任何處理,那麼會産生兩個主要問題:
第一個記憶體碎片問題:
假設堆有100M,線程A申請500M,線程B申請200M,線程C申請300M,此時堆空間為A(500)B(200)C(300),然後A和C把空間釋放了,空間變為 空閑區(500m)線程B空間(200M)空閑區(300M) 這時候線程D需要留600M就會發現此時沒有完成的一塊空間給線程D;
是以一些進階語言中堆空間配置設定以類似作業系統的頁式配置設定的方式進行管理,分割出一個個小塊,一個小塊中包含一些中繼資料(如使用者資料大小、是否空閑、頭指針、尾指針)、使用者資料區、對齊padding區;
因為現代作業系統一個頁的區域一般是4kb,是以每次配置設定堆記憶體塊也會把使用者資料區設定為4kb的倍數,同時因為還需要額外的區域來存儲中繼資料資訊,但是中繼資料大小未必是4位元組的倍數(像C++中可以設定4位元組對齊https://blog.csdn.net/sinat_28296297/article/details/77864874),在加上要考慮到CPU的僞共享緩存帶來的性能問題,是以需要一些額外的空閑空間來做補充(這就是對齊位元組的意義)。
那麼如果隻用連結清單形式來管理堆記憶體,看起來就像是下面這樣:
第二個則是并發沖突問題
因為多個線程在同時向堆記憶體中申請資源,如果沒有控制必然會出現沖突和覆寫問題,是以常見的方案是使用鎖,但是鎖則不可避免的帶來性能問題;是以有各種各樣的方案兼顧性能和碎片化以及預配置設定的政策來進行記憶體配置設定。
一個簡單的記憶體配置設定器
我們先按照上面的介紹來實作一個簡單的記憶體配置設定器,即實作一個malloc、free方法。
在這裡我們我們把data、bss、heap三個區域統稱為“data segment”,datasegment的結尾由一個指向此處的指針brk(program break)确定。如果想在heap上配置設定更多的空間,隻需要請求系統由低像高移動brk指針,并把對應的記憶體首位址傳回,釋放記憶體時,隻需要向下移動brk指針即可。
在Linux和unix系統中,我們這裡就調用sbrk()方法來操縱brk指針:
- sbrk(0)擷取目前brk的位址
- 調用sbrk(x),x為正數時,請求配置設定x bytes的記憶體空間,x為負數時,請求釋放x bytes的記憶體空間
現在寫一個簡易版本的malloc:
void *malloc(size_t size) {
void *block;
block = sbrk(size);
if (block == (void *) -1) {
return NULL;
}
return block;
}
現在問題是我們可以申請記憶體,但是如何釋放呢?因為釋放記憶體需要sbrk來移動brk指針向下縮減,但是我們目前沒有記錄這個區域的尺寸資訊;
還有另外一個問題,假設我們現在申請了兩塊記憶體,A\B,B在A的後面,如果這時候使用者想将A釋放,這時候brk指針在B的末尾處,那麼如果簡單的移動brk指針,就會對B進行破壞,是以對于A區域,我們不能直接還給作業系統,而是等B也同時被是釋放時再還給作業系統,同時也可以把A作為一個緩存,等下次有小于等于A區域的記憶體需要申請時,可以直接使用A記憶體,也可以将AB進行合并來統一配置設定(當然會存在記憶體碎片問題,這裡我就先不考慮)。
是以現在我們将記憶體按照塊的結構來進行劃分,為了簡單起見,我們使用連結清單的方式來管理;那麼除了本身使用者申請的記憶體區域外,還需要一些額外的資訊來記錄塊的大小、下一個塊的位置,目前塊是否在使用。整個結構如下:
typedef char ALIGN[16]; // padding位元組對齊使用
union header {
struct {
size_t size; // 塊大小
unsigned is_free; // 是否有在使用
union header *next; // 下一個塊的位址
} s;
ALIGN stub;
};
typedef union header header_t;
這裡将一個結構體與一個16位元組的數組封裝進一個union,這就保證了這個header始終會指向一個對齊16位元組的位址(union的尺寸等于成員中最大的尺寸)。而header的尾部是實際給使用者的記憶體的起始位置,是以這裡給使用者的記憶體也是一個16位元組對齊的(位元組對齊目的為了提升緩存命中率和批處理能力提升系統效率)。
現在的記憶體結構如下圖所示:
現在我們使用head和tail來使用這個連結清單
header_t *head, *tail
為了支援多線程并發通路記憶體,我們這裡簡單的使用全局鎖。
pthread_mutex_t global_malloc_lock;
我們的malloc現在是這樣:
void *malloc(size_t size)
{
size_t total_size;
void *block;
header_t *header;
if (!size) // 如果size為0或者NULL直接傳回null
return NULL;
pthread_mutex_lock(&global_malloc_lock); // 全局加鎖
header = get_free_block(size); // 先從已空閑區域找一塊合适大小的記憶體
if (header) { // 如果能找到就直接使用,無需每次向作業系統申請
header->s.is_free = 0; // 标志這塊區域非空閑
pthread_mutex_unlock(&global_malloc_lock); // 解鎖
// 這個header對外部應該是完全隐藏的,真正使用者需要的記憶體在header尾部的下一個位置
return (void*)(header + 1);
}
// 如果空閑區域沒有則向作業系統申請一塊記憶體,因為我們需要header存儲一些中繼資料
// 是以這裡要申請的記憶體實際是中繼資料區+使用者實際需要的大小
total_size = sizeof(header_t) + size;
block = sbrk(total_size);
if (block == (void*) -1) { // 擷取失敗解鎖、傳回NULL
pthread_mutex_unlock(&global_malloc_lock);
return NULL;
}
// 申請成功設定中繼資料資訊
header = block;
header->s.size = size;
header->s.is_free = 0;
header->s.next = NULL;
// 更新連結清單對應指針
if (!head)
head = header;
if (tail)
tail->s.next = header;
tail = header;
// 解鎖傳回給使用者記憶體
pthread_mutex_unlock(&global_malloc_lock);
return (void*)(header + 1);
}
// 這個函數從連結清單中已有的記憶體塊進行判斷是否存在空閑的,并且能夠容得下申請區域的記憶體塊
// 有則傳回,每次都從頭周遊,暫不考慮性能和記憶體碎片問題。
header_t *get_free_block(size_t size)
{
header_t *curr = head;
while(curr) {
if (curr->s.is_free && curr->s.size >= size)
return curr;
curr = curr->s.next;
}
return NULL;
}
可以看下現在我們的記憶體配置設定具有的基本能力:
- 通過加鎖保證線程安全
- 通過連結清單的方式管理記憶體塊,并解決記憶體複用問題。
接下來我們來寫free函數,首先要看下需要釋放的記憶體是否在brk的位置,如果是,則直接還給作業系統,如果不是,标記為空閑,以後複用。
void free(void *block)
{
header_t *header, *tmp;
void *programbreak;
if (!block)
return;
pthread_mutex_lock(&global_malloc_lock); // 全局加鎖
header = (header_t*)block - 1; // block轉變為header_t為機關的結構,并向前移動一個機關,也就是拿到了這個塊的中繼資料的起始位址
programbreak = sbrk(0); // 擷取目前brk指針的位置
if ((char*)block + header->s.size == programbreak) { // 如果目前記憶體塊的末尾位置(即tail塊)剛好是brk指針位置就把它還給作業系統
if (head == tail) { // 隻有一個塊,直接将連結清單設定為空
head = tail = NULL;
} else {// 存在多個塊,則找到tail的前一個快,并把它next設定為NULL
tmp = head;
while (tmp) {
if(tmp->s.next == tail) {
tmp->s.next = NULL;
tail = tmp;
}
tmp = tmp->s.next;
}
}
// 将記憶體還給作業系統
sbrk(0 - sizeof(header_t) - header->s.size);
pthread_mutex_unlock(&global_malloc_lock); // 解鎖
return;
}
// 如果不是最後的連結清單就标志位free,後面可以複用
header->s.is_free = 1;
pthread_mutex_unlock(&global_malloc_lock);
}
以上就是一個簡單的記憶體配置設定器;可以看到我們使用連結清單來管理堆記憶體區域,并通過全局鎖來線程安全問題,同時也提供一定的記憶體複用能力。當然這個記憶體配置設定器也存在幾個嚴重的問題:
- 全局鎖在高并發場景下會帶來嚴重性能問題
- 記憶體複用每次從頭周遊也存在一些性能問題
- 記憶體碎片問題,我們記憶體複用時隻是簡單的判斷塊記憶體是否大于需要的記憶體區域,如果極端情況下,我們一塊空閑記憶體為1G,而新申請記憶體為1kb,那就造成嚴重的碎片浪費
- 記憶體釋放存在問題,隻會把末尾處的記憶體還給作業系統,中間的空閑部分則沒有機會還給作業系統。
那麼下面我們介紹一些完善的記憶體配置設定器是如何處理的,以及Go中的記憶體配置設定政策
TCMalloc
記憶體配置設定器多種多樣,概括起來主要是以下幾個思想:
1、劃分記憶體配置設定粒度,先将記憶體區域以最小機關定義出來,然後區分對象大小分别對待。小對象分為若幹類,使用對應的資料結構來管理,降低記憶體碎片化
2、垃圾回收及預測優化:釋放記憶體時,能夠合并小記憶體為大記憶體,根據政策進行緩存,下次可以直接複用提升性能。達到一定條件釋放回作業系統,避免長期占用導緻記憶體不足。
3、優化多線程下的性能:針對多線程每個線程有自己獨立的一段堆記憶體配置設定區。線程對這片區域可以無鎖通路,提升性能
這其中谷歌的TCMalloc是業界的佼佼者,Go也是借鑒了它的思想,接下來我們來介紹一下。
TCMalloc的幾個重要概念:
- Page:作業系統對記憶體管理以頁為機關,TCMalloc也是這樣,隻不過TCMalloc裡的Page大小與作業系統裡的大小并不一定相等,而是倍數關系。《TCMalloc解密》裡稱x64下Page大小是8KB。
- Span:一組連續的Page被稱為Span,比如可以有2個頁大小的Span,也可以有16頁大小的Span,Span比Page高一個層級,是為了友善管理一定大小的記憶體區域,Span是TCMalloc中記憶體管理的基本機關。
- ThreadCache:每個線程各自的Cache,一個Cache包含多個空閑記憶體塊連結清單,每個連結清單連接配接的都是記憶體塊,同一個連結清單上記憶體塊的大小是相同的,也可以說按記憶體塊大小,給記憶體塊分了個類,這樣可以根據申請的記憶體大小,快速從合适的連結清單選擇空閑記憶體塊。由于每個線程有自己的ThreadCache,是以ThreadCache通路是無鎖的。
- CentralCache:是所有線程共享的緩存,也是儲存的空閑記憶體塊連結清單,連結清單的數量與ThreadCache中連結清單數量相同,當ThreadCache記憶體塊不足時,可以從CentralCache取,當ThreadCache記憶體塊多時,可以放回CentralCache。由于CentralCache是共享的,是以它的通路是要加鎖的。
- PageHeap:PageHeap是堆記憶體的抽象,PageHeap存的也是若幹連結清單,連結清單儲存的是Span,當CentralCache沒有記憶體的時,會從PageHeap取,把1個Span拆成若幹記憶體塊,添加到對應大小的連結清單中,當CentralCache記憶體多的時候,會放回PageHeap。如上圖,分别是1頁Page的Span連結清單,2頁Page的Span連結清單等,最後是large span set,這個是用來儲存中大對象的。毫無疑問,PageHeap也是要加鎖的。
TCMalloc中區分了不同級别的對象,對應不同的配置設定流程:
- 小對象大小:0~256KB;配置設定流程:ThreadCache -> CentralCache -> HeapPage,大部分時候,ThreadCache緩存都是足夠的,不需要去通路CentralCache和HeapPage,無鎖配置設定加無系統調用,配置設定效率是非常高的。
- 中對象大小:257~1MB;配置設定流程:直接在PageHeap中選擇适當的大小即可,128 Page的Span所儲存的最大記憶體就是1MB。
- 大對象大小:>1MB;配置設定流程:從large span set選擇合适數量的頁面組成span,用來存儲資料。
(以上圖文借鑒自:圖解TCMalloc、Go記憶體配置設定那些事)
除此之外,TCMalloc中還涉及記憶體釋放時多個小區域合并為大區域的方法,大家感興趣的可以看這篇文章:TCMalloc解密
Go記憶體配置設定方案
Go中的記憶體配置設定政策是借鑒TCMalloc的方案來進行記憶體配置設定。同時結合Go自身特點,比TCMalloc更加細緻的劃分對象等級,将TCMalloc中針對線程的緩存變更為綁定到邏輯處理器P上的緩存區域。除此之外Go還結合自身的逃逸分析和垃圾回收政策整體制定了一套記憶體配置設定政策。
Go通過編譯階段的逃逸分析來判斷變量應該被配置設定到棧還是堆上,關于逃逸分析我們不做過多介紹,總結以下幾點:
- 棧比堆更高效,不需要GC,是以Go會盡可能的将記憶體配置設定到棧上。Go的協程棧可以自動擴容和縮容
- 當配置設定到棧上可能會引起非法記憶體通路等問題,則會使用堆,如:
- 當一個值在函數被調用後通路(即作為傳回值傳回變量位址),這個值極有可能被配置設定到堆上
- 當編譯器檢測到某個值過大,這個值被配置設定到堆上(棧擴容和縮容有成本)
- 當編譯時,編譯器不知道這個值的大小(slice、map等引用類型)這個值會被配置設定到堆上
- 最後,不要去猜值在哪,隻有編譯器和編譯器開發者知道
Go通過細緻的對象劃分、極緻的多級緩存+無鎖政策緩存、精确的位圖管理來進行精細化的記憶體管理和性能保障。Go中把所有對象分為三個層級:
- 微小對象(0,16byte):配置設定流程為,mache->mcentral->mheap位圖查找->mheap基數樹查找->作業系統配置設定
- 小對象 [16byte, 32KB]:配置設定流程與微小對象一樣
- 大對象(32KB以上):分為流程為,mheap基數樹查找->作業系統配置設定(不經過mcache和mcentral)
Go中的記憶體配置設定流程可以看下面的概覽圖:
主要涉及如下概念:
page
與TCMalloc中的Page相同,一個page大小為8kb(為作業系統中頁的兩倍),上圖中一個淺藍色的長方形代表一個page
span
span是Go中記憶體管理的基本機關,go中為mspan,span的大小是page的倍數,上圖中一個淡紫色的長方形為一個span
Go1.9.2往後一共劃分了67級的mspan;
比如第一級span中每個對象大小是8b、第一級span的大小是一個page即8192b、一共可以存放1024個對象。
對應到代碼中放在一個叫做class_to_size的數組中,存儲每個級别的span中的object的大小
// path: /usr/local/go/src/runtime/sizeclasses.go
const _NumSizeClasses = 67
var class_to_size = [_NumSizeClasses]uint16{0, 8, 16, 32, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208, 224, 240, 256, 288, 320, 352, 384, 416, 448, 480, 512, 576, 640, 704, 768, 896, 1024, 1152, 1280, 1408, 1536,1792, 2048, 2304, 2688, 3072, 3200, 3456, 4096, 4864, 5376, 6144, 6528, 6784, 6912, 8192, 9472, 9728, 10240, 10880, 12288, 13568, 14336, 16384, 18432, 19072, 20480, 21760, 24576, 27264, 28672, 32768}
還有一個class_to_allocnpages數組存儲每個級别的span對應的page的個數
// path: /usr/local/go/src/runtime/sizeclasses.go
const _NumSizeClasses = 67
var class_to_allocnpages = [_NumSizeClasses]uint8{0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 3, 2, 3, 1, 3, 2, 3, 4, 5, 6, 1, 7, 6, 5, 4, 3, 5, 7, 2, 9, 7, 5, 8, 3, 10, 7, 4}
代碼中mspan結構體的定義如下:
// path: /usr/local/go/src/runtime/mheap.go
type mspan struct {
//連結清單前向指針,用于将span連結起來
next *mspan
//連結清單前向指針,用于将span連結起來
prev *mspan
// 起始位址,也即所管理頁的位址
startAddr uintptr
// 管理的頁數
npages uintptr
// 塊個數,表示有多少個塊可供配置設定
nelems uintptr
// 用來輔助确定目前span中的元素配置設定到了哪裡
freeindex uintptr
//配置設定位圖,每一位代表一個塊是否已配置設定
allocBits *gcBits
// allocBits的補碼,以用來快速查找記憶體中未被使用的記憶體
allocCache unit64
// 已配置設定塊的個數
allocCount uint16
// class表中的class ID,和Size Classs相關
spanclass spanClass
// class表中的對象大小,也即塊大小
elemsize uintptr
// GC中來标記哪些塊已經釋放了
gcmarkBits *gcBits
}
這裡有一個spanClass需要注意下,他其實是class_to_size的兩倍,這是因為每個類别的對象對應兩個mspan,一個配置設定給含有指針的的對象,一個配置設定給不含有指針的對象,這樣垃圾回收時,針對無指針對象的span區域不需要進行複雜的标記處理,提升效果。
舉個例子,第10級的size_class中一個對象是144位元組,一個span占用一個page,共可以存儲56個對象(可以看到56個對象占不滿1個page,是以尾部會有128位元組是無用的),它的mspan結構如下:
當然微小對象的配置設定會複用一個對象,比如兩個char類型都放在一個object中。後續會介紹。
mcache
mcache與TCMalloc中的ThreadCache類似,每個層級的span都會在mcache中儲存一份;每個邏輯處理器P會有自己的mcache,對這部分區域的通路是無鎖的。mcache的結構中有幾個字段需要關注:
//path: /usr/local/go/src/runtime/mcache.go
type mcache struct {
// mcache中對應各個等級的span都會有兩份緩存
alloc [numSpanClasses]*mspan
// 下面三個是在微小對象配置設定時專門使用
tiny uintptr
tinyoffset uintptr
local_tinyallocs uintptr
}
numSpanClasses = _NumSizeClasses << 1
可以看到macache包含所有規格的span,微小對象和小對象都會先從這裡開始找空間,大對象(超過32kb)沒有對應的class索引,不經過這裡。alloc數組中一共有134個元素,每一個級别的span在其中有兩個即67x2;因為每一個級别對應兩個span,一個給無指針的對象使用一半給有指針的對象使用(無指針對象在垃圾回收時不需要去掃描他是否引用了其他活躍對象),結構如下:
mcache也是從mcentral中擷取的記憶體,Go運作時初始化時會調用runtime.allocmache初始化線程緩存
// init initializes pp, which may be a freshly allocated p or a
// previously destroyed p, and transitions it to status _Pgcstop.
func (pp *p) init(id int32) {
pp.id = id
////////
.........
/////////
if pp.mcache == nil {
if id == 0 {
if mcache0 == nil {
throw("missing mcache?")
}
// Use the bootstrap mcache0. Only one P will get
// mcache0: the one with ID 0.
pp.mcache = mcache0
} else {
pp.mcache = allocmcache()
}
}
..........
}
該函數會在系統棧中調用runtime.mheap中的緩存配置設定器初始化新的runtime.mcache結構體:
// dummy mspan that contains no free objects.
var emptymspan mspan
func allocmcache() *mcache {
var c *mcache
// 在系統棧中調用mheap的緩存配置設定器建立mcache
systemstack(func() {
lock(&mheap_.lock) // mheap是所有協程共用的需要加鎖通路
c = (*mcache)(mheap_.cachealloc.alloc())
c.flushGen = mheap_.sweepgen
unlock(&mheap_.lock)
})
// 将alloc數組設定為空span
for i := range c.alloc {
c.alloc[i] = &emptymspan
}
c.nextSample = nextSample()
return c
}
但是剛剛初始化的mcache中所有的mspan都是空的占位符emptymspan
之後需要時會從mcentral中擷取指定spanClass的span:
// refill acquires a new span of span class spc for c. This span will
// have at least one free object. The current span in c must be full.
//
// Must run in a non-preemptible context since otherwise the owner of
// c could change.
func (c *mcache) refill(spc spanClass) {
// Return the current cached span to the central lists.
s := c.alloc[spc]
...............
if s != &emptymspan {
// Mark this span as no longer cached.
if s.sweepgen != mheap_.sweepgen+3 {
throw("bad sweepgen in refill")
}
mheap_.central[spc].mcentral.uncacheSpan(s)
}
// Get a new cached span from the central lists.
s = mheap_.central[spc].mcentral.cacheSpan()
................
...............
c.alloc[spc] = s
}
refill這個方法在runtime.malloc方法中會調用;
mcentral
mcentral是所有線程共享的的緩存,需要加鎖通路;它的主要作用是為mcache提供切分好的mspan資源。每個spanClass對應一個級别的mcentral;mcentral整體是在mheap中管理的,它之中包含兩個mspan連結清單,Go1.17.7版本中分别為partial代表有空閑區域的span、full代表無空閑區域的span清單。(這裡并不是網上很多文章講的nonempty和empty隊列)
type mcentral struct {
spanclass spanClass
partial [2]spanSet // list of spans with a free object
full [2]spanSet // list of spans with no free objects
}
type spanSet struct {
spineLock mutex
spine unsafe.Pointer // *[N]*spanSetBlock, accessed atomically
spineLen uintptr // Spine array length, accessed atomically
spineCap uintptr // Spine array cap, accessed under lock
index headTailIndex
}
對于微小對象和小對象的記憶體會首先從mcache和mcentral中擷取,這部分要看runtime.malloc代碼
微小對象配置設定
Go中小于16位元組的作為微小對象,微小對象會被放入sizeClass為2的span中即16位元組,這裡并不是說每次微小對象配置設定都配置設定一個16位元組的空間,而是會把一個16位元組的空間按照2、4、8的規則進行位元組對齊的形式來存儲,比如1位元組的char會被配置設定2位元組空間,9位元組的資料會被配置設定2+8=10位元組空間。
off := c.tinyoffset
// Align tiny pointer for required (conservative) alignment.
if size&7 == 0 {
off = alignUp(off, 8)
} else if sys.PtrSize == 4 && size == 12 {
// Conservatively align 12-byte objects to 8 bytes on 32-bit
// systems so that objects whose first field is a 64-bit
// value is aligned to 8 bytes and does not cause a fault on
// atomic access. See issue 37262.
// TODO(mknyszek): Remove this workaround if/when issue 36606
// is resolved.
off = alignUp(off, 8)
} else if size&3 == 0 {
off = alignUp(off, 4)
} else if size&1 == 0 {
off = alignUp(off, 2)
}
如果目前的一個16位元組元素能夠容納新的微小對象則充分利用目前元素空間
if off+size <= maxTinySize && c.tiny != 0 {
// The object fits into existing tiny block.
x = unsafe.Pointer(c.tiny + off)
c.tinyoffset = off + size
c.tinyAllocs++
mp.mallocing = 0
releasem(mp)
return x
}
否則從下一個元素中去配置設定空間
// Allocate a new maxTinySize block.
span = c.alloc[tinySpanClass]
v := nextFreeFast(span)
if v == 0 {
v, span, shouldhelpgc = c.nextFree(tinySpanClass)
}
x = unsafe.Pointer(v)
(*[2]uint64)(x)[0] = 0
(*[2]uint64)(x)[1] = 0
// See if we need to replace the existing tiny block with the new one
// based on amount of remaining free space.
if !raceenabled && (size < c.tinyoffset || c.tiny == 0) {
// Note: disabled when race detector is on, see comment near end of this function.
c.tiny = uintptr(x)
c.tinyoffset = size
}
size = maxTinySize
nextFreeFast和nextFree的内容在下面介紹
小對象配置設定
var sizeclass uint8
if size <= smallSizeMax-8 {
sizeclass = size_to_class8[divRoundUp(size, smallSizeDiv)]
} else {
sizeclass = size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]
}
size = uintptr(class_to_size[sizeclass])
spc := makeSpanClass(sizeclass, noscan)
span = c.alloc[spc]
v := nextFreeFast(span)
if v == 0 {
v, span, shouldhelpgc = c.nextFree(spc)
}
x = unsafe.Pointer(v)
if needzero && span.needzero != 0 {
memclrNoHeapPointers(unsafe.Pointer(v), size)
}
1-6行,根據參數中要配置設定的空間大小計算對應的sizeClass即對象大小
7-9行,根據對象大小的等級以及是否有指針(noscan)找到mcache的alloc數組中對應的span
第10行,先計算目前的span中是否有空閑空間,并傳回可配置設定的空閑空間位址
11-13行,如果mcache目前對應的span沒有空閑空間,則進入到nextFree函數尋找一個空閑的span
然後經過其他處理(垃圾回收标記、鎖定關系辨別等)傳回給調用方
同時也需要注意到,這裡的空間配置設定都是需要做記憶體對齊的,比如申請17位元組的空間,但是span的分類中是按照8的倍數進行增長的,比17大且最接近的級别是32,是以即使需要17位元組,在内部也會使用一個32位元組的空間,這也是上面代碼中需要根據size計算sizeClass的原因;也可以看到這種配置設定方式必然會存在記憶體浪費,TCMalloc算法機盡量将浪費率控制在15%以内
nextFreeFast中可以看到用到了上面mspan中的freeIndex、allocCache等屬性;
因為這裡使用了allocCache來對前64位元組進行快速通路,如果目前配置設定位元組在allocCache範圍之内,可以直接利用位圖緩存來進行快速計算可配置設定的區域;至于為什麼是64位元組,我猜與CPU中CacheLine的大小有關,64位CPU的cache line就是64位元組,利用此來提升CPU緩存命中率,提升性能。
// nextFreeFast returns the next free object if one is quickly available.
// Otherwise it returns 0.
func nextFreeFast(s *mspan) gclinkptr {
theBit := sys.Ctz64(s.allocCache) // Is there a free object in the 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)
s.freeindex = freeidx
s.allocCount++
return gclinkptr(result*s.elemsize + s.base())
}
}
return 0
}
關于freeIndex和allocCache的關系,實際是利用了bitmap位圖緩存和階段标記的方式來進行配合,因為allocCache一次隻能緩存64位元組資料,是以在span被配置設定過程中,allocCache是滾動前進的,一次辨別一塊64位元組區域,而freeIndex代表上次配置設定結束的元素位置,通過目前allocCache中的空閑位置+freeIndex即可以算出目前span被配置設定的區域。
具體計算方式可以mbitmap.go中的nextFreeIndex方法
// nextFreeIndex returns the index of the next free object in s at
// or after s.freeindex.
// There are hardware instructions that can be used to make this
// faster if profiling warrants it.
func (s *mspan) nextFreeIndex() uintptr {
sfreeindex := s.freeindex
snelems := s.nelems
if sfreeindex == snelems {
return sfreeindex
}
if sfreeindex > snelems {
throw("s.freeindex > s.nelems")
}
aCache := s.allocCache
bitIndex := sys.Ctz64(aCache)
for bitIndex == 64 {
// Move index to start of next cached bits.
sfreeindex = (sfreeindex + 64) &^ (64 - 1)
if sfreeindex >= snelems {
s.freeindex = snelems
return snelems
}
whichByte := sfreeindex / 8
// Refill s.allocCache with the next 64 alloc bits.
s.refillAllocCache(whichByte)
aCache = s.allocCache
bitIndex = sys.Ctz64(aCache)
// nothing available in cached bits
// grab the next 8 bytes and try again.
}
result := sfreeindex + uintptr(bitIndex)
if result >= snelems {
s.freeindex = snelems
return snelems
}
s.allocCache >>= uint(bitIndex + 1)
sfreeindex = result + 1
if sfreeindex%64 == 0 && sfreeindex != snelems {
// We just incremented s.freeindex so it isn't 0.
// As each 1 in s.allocCache was encountered and used for allocation
// it was shifted away. At this point s.allocCache contains all 0s.
// Refill s.allocCache so that it corresponds
// to the bits at s.allocBits starting at s.freeindex.
whichByte := sfreeindex / 8
s.refillAllocCache(whichByte)
}
s.freeindex = sfreeindex
return result
}
在回到nextFree函數中
func (c *mcache) nextFree(spc spanClass) (v gclinkptr, s *mspan, shouldhelpgc bool) {
s = c.alloc[spc]
shouldhelpgc = false
freeIndex := s.nextFreeIndex() // 擷取可配置設定的元素位置
if freeIndex == s.nelems {
//如果目前span沒有可配置設定空間,調用refill方法把目前span交給mcentral的full隊列
// 并從mcentral的partial隊列取一個有空閑的span放到mcache上
// The span is full.
if uintptr(s.allocCount) != s.nelems {
println("runtime: s.allocCount=", s.allocCount, "s.nelems=", s.nelems)
throw("s.allocCount != s.nelems && freeIndex == s.nelems")
}
c.refill(spc)
shouldhelpgc = true
s = c.alloc[spc]
freeIndex = s.nextFreeIndex() // 在新擷取的span中重新計算freeIndex
}
if freeIndex >= s.nelems {
throw("freeIndex is not valid")
}
v = gclinkptr(freeIndex*s.elemsize + s.base()) // 擷取span中資料的起始位址加上目前已配置設定的區域擷取一個可配置設定的空閑區域
s.allocCount++
if uintptr(s.allocCount) > s.nelems {
println("s.allocCount=", s.allocCount, "s.nelems=", s.nelems)
throw("s.allocCount > s.nelems")
}
return
}
函數第4行擷取下一個被配置設定的元素位置,如果freeIndex等于span中的最大元素數目,代表目前級别span已經被配置設定完了,這時候需要調用mcache的refill方法去mheap中對應的spanClass的mcentral中,把目前沒有空閑的span還給mcentral的full隊列,并從partail對列中擷取一個有空閑區域的span放到mcache上。
下方可以看到refill方法,如果mcache對應等級的span沒有則直接從mcentral中擷取,否則代表目前span已經沒有可配置設定的空間,是以需要把這個span重新交給mcentral,等待垃圾回收器标記完成之後則可以後面繼續使用。
func (c *mcache) refill(spc spanClass) {
// Return the current cached span to the central lists.
s := c.alloc[spc]
...............
if s != &emptymspan {
// Mark this span as no longer cached.
if s.sweepgen != mheap_.sweepgen+3 {
throw("bad sweepgen in refill")
}
mheap_.central[spc].mcentral.uncacheSpan(s)
}
// Get a new cached span from the central lists.
s = mheap_.central[spc].mcentral.cacheSpan()
................
...............
c.alloc[spc] = s
}
進入到cacheSpan函數中可以看到,這裡的擷取空閑span經過以下幾個順序:
- 是先從partail隊列中已經被垃圾回收清掃的部分嘗試拿一個span
- 如果pop沒有代表目前沒有被GC清掃的span,從partial隊列中未被GC清掃的部分嘗試擷取空閑span,并進行清掃
- 如果partail隊列都沒擷取到,嘗試從full隊列的未清掃區擷取一個span,進行清掃,并放入到full隊列的以清掃區,代表這個span不會配置設定給其他的mcache了;
- 如果未清掃區也沒有擷取到對應的span則代表mcentral需要擴容,向mheap申請一塊區域。
同時可以發現這裡的周遊次數寫死為100,可能是覺得差不多就得了,畢竟這些操作也需要耗時,先跟mheap要一個得了。
如果獲得了空閑span,跳轉到haveSpan代碼段,這裡更新freeindex和allocCache位圖緩存,傳回span;
// Allocate a span to use in an mcache.
func (c *mcentral) cacheSpan() *mspan {
// Deduct credit for this span allocation and sweep if necessary.
spanBytes := uintptr(class_to_allocnpages[c.spanclass.sizeclass()]) * _PageSize
deductSweepCredit(spanBytes, 0)
traceDone := false
if trace.enabled {
traceGCSweepStart()
}
spanBudget := 100
var s *mspan
sl := newSweepLocker()
sg := sl.sweepGen
// Try partial swept spans first.
if s = c.partialSwept(sg).pop(); s != nil {
goto havespan
}
// Now try partial unswept spans.
for ; spanBudget >= 0; spanBudget-- {
s = c.partialUnswept(sg).pop()
if s == nil {
break
}
if s, ok := sl.tryAcquire(s); ok {
// We got ownership of the span, so let's sweep it and use it.
s.sweep(true)
sl.dispose()
goto havespan
}
}
// Now try full unswept spans, sweeping them and putting them into the
// right list if we fail to get a span.
for ; spanBudget >= 0; spanBudget-- {
s = c.fullUnswept(sg).pop()
if s == nil {
break
}
if s, ok := sl.tryAcquire(s); ok {
// We got ownership of the span, so let's sweep it.
s.sweep(true)
// Check if there's any free space.
freeIndex := s.nextFreeIndex()
if freeIndex != s.nelems {
s.freeindex = freeIndex
sl.dispose()
goto havespan
}
// Add it to the swept list, because sweeping didn't give us any free space.
c.fullSwept(sg).push(s.mspan)
}
// See comment for partial unswept spans.
}
sl.dispose()
if trace.enabled {
traceGCSweepDone()
traceDone = true
}
// We failed to get a span from the mcentral so get one from mheap.
s = c.grow()
if s == nil {
return nil
}
// At this point s is a span that should have free slots.
havespan:
if trace.enabled && !traceDone {
traceGCSweepDone()
}
n := int(s.nelems) - int(s.allocCount)
if n == 0 || s.freeindex == s.nelems || uintptr(s.allocCount) == s.nelems {
throw("span has no free objects")
}
freeByteBase := s.freeindex &^ (64 - 1)
whichByte := freeByteBase / 8
// Init alloc bits cache.
s.refillAllocCache(whichByte)
// Adjust the allocCache so that s.freeindex corresponds to the low bit in
// s.allocCache.
s.allocCache >>= s.freeindex % 64
return s
}
對于mcache如果覺得目前級别的span剩餘空間無法滿足使用者要求的大小,則會把這個span交給mcentral;mcentral根據條件判斷是直接放到堆中等待回收還是需要放到自己來管理,如果自己管理那麼再判斷這個span的freeIndex與容量的關系如果還有剩餘容量則進入partialSweep隊列,如果麼有容量則進入fullSweep中。
func (c *mcentral) uncacheSpan(s *mspan) {
if s.allocCount == 0 {
throw("uncaching span but s.allocCount == 0")
}
sg := mheap_.sweepgen
stale := s.sweepgen == sg+1
// Fix up sweepgen.
if stale {
// Span was cached before sweep began. It's our
// responsibility to sweep it.
//
// Set sweepgen to indicate it's not cached but needs
// sweeping and can't be allocated from. sweep will
// set s.sweepgen to indicate s is swept.
atomic.Store(&s.sweepgen, sg-1)
} else {
// Indicate that s is no longer cached.
atomic.Store(&s.sweepgen, sg)
}
// Put the span in the appropriate place.
if stale {
// It's stale, so just sweep it. Sweeping will put it on
// the right list.
//
// We don't use a sweepLocker here. Stale cached spans
// aren't in the global sweep lists, so mark termination
// itself holds up sweep completion until all mcaches
// have been swept.
ss := sweepLocked{s}
ss.sweep(false)
} else {
if int(s.nelems)-int(s.allocCount) > 0 {
// Put it back on the partial swept list.
c.partialSwept(sg).push(s)
} else {
// There's no free space and it's not stale, so put it on the
// full swept list.
c.fullSwept(sg).push(s)
}
}
}
可以看到mcentral中的partial和full都是擁有兩個元素的spanSet數組,這樣的目的其實是雙緩存政策,當垃圾回收隻回收和使用者協程并發進行,每次回收一半而寫入另一半,下一次交替過來,這樣保證永遠有空間可以配置設定,而不是串行等待垃圾回收完成後在配置設定空間,以空間換時間來提升響應性能
type mcentral struct {
spanclass spanClass
partial [2]spanSet // list of spans with a free object
full [2]spanSet // list of spans with no free objects
}
mcentral中的grow方法涉及到mheap的記憶體配置設定和管理,下面介紹。
mheap
mheap與TCMalloc中的PageHeap類似,代表Go中所持有的堆空間,mcentral管理的span也是從這裡拿到的。當mcentral沒有空閑span時,會向mheap申請,如果mheap中也沒有資源了,會向作業系統來申請記憶體。向作業系統申請是按照頁為機關來的(4kb),然後把申請來的記憶體頁按照page(8kb)、span(page的倍數)、chunk(512kb)、heapArena(64m)這種級别來組織起來。
pageCache的位圖緩存
mcentral中的grow方法會調用mheap的alloc方法
// grow allocates a new empty span from the heap and initializes it for c's size class.
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, true)
if s == nil {
return nil
}
// Use division by multiplication and shifts to quickly compute:
// n := (npages << _PageShift) / size
n := s.divideByElemSize(npages << _PageShift)
s.limit = s.base() + size*n
heapBitsForAddr(s.base()).initSpan(s)
return s
}
然後内部調用allocSpan方法。
func (h *mheap) alloc(npages uintptr, spanclass spanClass, needzero bool) (*mspan, bool) {
// Don't do any operations that lock the heap on the G stack.
// It might trigger stack growth, and the stack growth code needs
// to be able to allocate heap.
var s *mspan
systemstack(func() {
// To prevent excessive heap growth, before allocating n pages
// we need to sweep and reclaim at least n pages.
if !isSweepDone() {
h.reclaim(npages)
}
s = h.allocSpan(npages, spanAllocHeap, spanclass)
})
if s == nil {
return nil, false
}
isZeroed := s.needzero == 0
if needzero && !isZeroed {
memclrNoHeapPointers(unsafe.Pointer(s.base()), s.npages<<_PageShift)
isZeroed = true
}
s.needzero = 0
return s, isZeroed
}
而在allocSpan方法中,如果要配置設定的區域不大,并且不需要考慮實體對齊的情況下,會首先從邏輯處理器的pageCache緩存上去擷取空間,這樣的目的是為了無鎖配置設定空間提升性能(又是空間換時間)。
下面的16行可以看到先從邏輯處理器P的pcache上嘗試擷取對應的空間。
func (h *mheap) allocSpan(npages uintptr, typ spanAllocType, spanclass spanClass) (s *mspan) {
// Function-global state.
gp := getg()
base, scav := uintptr(0), uintptr(0)
// On some platforms we need to provide physical page aligned stack
// allocations. Where the page size is less than the physical page
// size, we already manage to do this by default.
needPhysPageAlign := physPageAlignedStacks && typ == spanAllocStack && pageSize < physPageSize
// If the allocation is small enough, try the page cache!
// The page cache does not support aligned allocations, so we cannot use
// it if we need to provide a physical page aligned stack allocation.
pp := gp.m.p.ptr()
if !needPhysPageAlign && pp != nil && npages < pageCachePages/4 {
c := &pp.pcache
// If the cache is empty, refill it.
if c.empty() {
lock(&h.lock)
*c = h.pages.allocToCache()
unlock(&h.lock)
}
// Try to allocate from the cache.
base, scav = c.alloc(npages)
if base != 0 {
s = h.tryAllocMSpan()
if s != nil {
goto HaveSpan
}
// We have a base but no mspan, so we need
// to lock the heap.
}
}
pageCache的結構如下:
代碼在runtime/mpagecache.go中
// 代表pageCache能夠使用的空間數,8x64一共是512kb空間
const pageCachePages = 8 * unsafe.Sizeof(pageCache{}.cache)
// pageCache represents a per-p cache of pages the allocator can
// allocate from without a lock. More specifically, it represents
// a pageCachePages*pageSize chunk of memory with 0 or more free
// pages in it.
type pageCache struct {
base uintptr // base代表該虛拟記憶體的基線位址
// cache和scav都是起到位圖示記的作用,cache主要是标記哪些記憶體位置已經被使用了,scav标記已經被清除的區域
// 用來加速垃圾未收,在垃圾回收一定條件下兩個可以互換,提升配置設定和垃圾回收效率。
cache uint64 // 64-bit bitmap representing free pages (1 means free)
scav uint64 // 64-bit bitmap representing scavenged pages (1 means scavenged)
}
下面回到mheap的allocSpan方法中
基數樹
如果pageCache不滿足配置設定條件或者沒有空閑空間了,則對mheap進行全局加鎖擷取記憶體
// For one reason or another, we couldn't get the
// whole job done without the heap lock.
lock(&h.lock)
.................
if base == 0 {
// Try to acquire a base address.
base, scav = h.pages.alloc(npages)
if base == 0 {
if !h.grow(npages) {
unlock(&h.lock)
return nil
}
base, scav = h.pages.alloc(npages)
if base == 0 {
throw("grew heap, but no adequate free space found")
}
}
}
................
unlock(&h.lock)
這裡首先從mheap的pages中去擷取,這個pages是一個pageAlloc的結構體執行個體,它是以基數樹的形式來進行管理。最多有5層,每個節點都對應一個pallocSum對象,除葉子節點外每個節點都包含連續8個子節點的記憶體資訊,越上層的節點包含的記憶體資訊越多,一顆完整的基數樹最多能夠代表16G記憶體空間。同時這裡面還做了一些搜尋優化
然後當mheap沒有空間時,會向作業系統去申請,這部分代碼在mheap的grow函數中,會調用到pageAlloc的grow和sysGrow方法,内部會調用平台相關的sysUsed方法來向作業系統去申請記憶體。
mheap中還有一個要注意的地方,就是對mcentral的管理
//path: /usr/local/go/src/runtime/mheap.go
type mheap struct {
lock mutex
// spans: 指向mspans區域,用于映射mspan和page的關系
spans []*mspan
// 指向bitmap首位址,bitmap是從高位址向低位址增長的
bitmap uintptr
// 訓示arena區首位址
arena_start uintptr
// 訓示arena區已使用位址位置
arena_used uintptr
// 訓示arena區末位址
arena_end uintptr
central [67*2]struct {
mcentral mcentral
pad [sys.CacheLineSize - unsafe.Sizeof(mcentral{})%sys.CacheLineSize]byte
}
}
首先注意到這裡的sys.CacheLineSize,根據這個對mcentral做空餘對齊,來防止CPU的僞共享緩存帶來的性能問題(關于僞共享緩存推薦看我的這篇文章:https://www.cnblogs.com/dojo-lzz/p/16183006.html)。
其次要注意到這裡mcentral的個數是67x2=134,也是針對有指針和無指針對象分别處理,提升垃圾回收效率,進而提升整體性能。
借用一下這張圖看的更清晰一些
總結來看通過細緻的對象劃分、極緻的多級緩存+無鎖政策緩存、精确的位圖管理來進行精細化的記憶體管理和性能保障。
整個文章大概花費一個月時間,通過自己看源碼能夠發現,現有講解Go記憶體配置設定的資料要麼已經老舊、要麼人雲亦雲,還是獨立思考實踐最能揭露本質。
參考文章
- 圖解Go語言記憶體配置設定:https://juejin.cn/post/6844903795739082760
- 記憶體配置設定器:https://draveness.me/golang/docs/part3-runtime/ch07-memory/golang-memory-allocator/
- 棧空間管理:https://draveness.me/golang/docs/part3-runtime/ch07-memory/golang-stack-management/
- 技術幹貨 | 了解 Go 記憶體配置設定:https://cloud.tencent.com/developer/article/1861429
- 一個簡單的記憶體配置設定器:https://github.com/KatePang13/Note/blob/main/%E4%B8%80%E4%B8%AA%E7%AE%80%E5%8D%95%E7%9A%84%E5%86%85%E5%AD%98%E5%88%86%E9%85%8D%E5%99%A8.md
- 編寫自己的記憶體配置設定器:https://soptq.me/2020/07/18/mem-allocator/
- Go記憶體配置設定原來這麼簡單:https://segmentfault.com/a/1190000020338427
- 圖解Go語言記憶體配置設定:https://juejin.cn/post/6844903795739082760
- TCMalloc介紹:https://blog.csdn.net/aaronjzhang/article/details/8696212
- TCMalloc解密:https://wallenwang.com/2018/11/tcmalloc/
- 圖解TCMalloc:https://zhuanlan.zhihu.com/p/29216091
- 記憶體配置設定器:https://draveness.me/golang/docs/part3-runtime/ch07-memory/golang-memory-allocator/
- 程序與線程:https://baijiahao.baidu.com/s?id=1687308494061329777&wfr=spider&for=pc
- 記憶體配置設定器 (Memory Allocator):https://blog.csdn.net/weixin_30940783/article/details/97806139
您可以考慮給樹發個小額微信紅包以資鼓勵