Unity IL2CPP的GC原理

【USparkle專欄】如果你深懷絕技，愛“搞點(diǎn)研究”，樂于分享也博采眾長(zhǎng)，我們期待你的加入，讓智慧的火花碰撞交織，讓知識(shí)的傳遞生生不息！

這是侑虎科技第1924篇文章，感謝作者Jamin發(fā)供稿。歡迎轉(zhuǎn)發(fā)分享，未經(jīng)作者授權(quán)請(qǐng)勿轉(zhuǎn)載。如果您有任何獨(dú)到的見解或者發(fā)現(xiàn)也歡迎聯(lián)系我們，一起探討。（QQ群：793972859）

作者主頁：

https://www.zhihu.com/people/liang-zhi-ming-70

背景：前段時(shí)間在項(xiàng)目?jī)?nèi)做了關(guān)于Mono內(nèi)存（堆內(nèi)存）的優(yōu)化。從結(jié)果上將Mono內(nèi)存從220MB降低到130MB，優(yōu)化過程中喚起了部分關(guān)于GC的消失的回憶，雖然實(shí)際的優(yōu)化工作中也許并用不到，但是更明確底層實(shí)現(xiàn)機(jī)制總歸是一件迭代自我的過程，在這里就來回顧一下。

一、什么是垃圾回收 - GC（Garbage Collector）

在游戲運(yùn)行的時(shí)候，數(shù)據(jù)主要存儲(chǔ)在內(nèi)存中，當(dāng)游戲的數(shù)據(jù)在不需要的時(shí)候，存儲(chǔ)當(dāng)前數(shù)據(jù)的內(nèi)存就可以被回收以再次使用。內(nèi)存垃圾是指當(dāng)前廢棄數(shù)據(jù)所占用的內(nèi)存，垃圾回收（GC）是指將廢棄的內(nèi)存重新回收再次使用的過程。

1. 什么時(shí)候觸發(fā)垃圾回收

有三個(gè)操作會(huì)觸發(fā)垃圾回收：

• 在堆內(nèi)存上進(jìn)行內(nèi)存分配操作而內(nèi)存不夠的時(shí)候都會(huì)觸發(fā)垃圾回收來利用閑置的內(nèi)存。

• GC會(huì)自動(dòng)觸發(fā)，不同平臺(tái)運(yùn)行頻率不一樣。

• GC被代碼強(qiáng)制執(zhí)行。

2. GC操作帶來的問題

直白點(diǎn)就兩個(gè)問題：一個(gè)是Stop-the-world導(dǎo)致的“卡”；一個(gè)是內(nèi)存碎片導(dǎo)致的“堆內(nèi)存太大”。

• GC操作會(huì)需要大量的時(shí)間來運(yùn)行，如果堆內(nèi)存上有大量的變量或者引用需要檢查，則檢查的操作會(huì)十分緩慢，這就會(huì)使得游戲運(yùn)行緩慢。

• GC可能會(huì)在關(guān)鍵時(shí)候運(yùn)行，例如在CPU處于游戲的性能運(yùn)行關(guān)鍵時(shí)刻，此時(shí)任何一個(gè)額外的操作都可能會(huì)帶來極大的影響，使得游戲幀率下降。

• 另外一個(gè)GC帶來的問題是堆內(nèi)存的碎片。當(dāng)一個(gè)內(nèi)存單元從堆內(nèi)存上分配出來，其大小取決于其存儲(chǔ)的變量的大小。當(dāng)該內(nèi)存被回收到堆內(nèi)存上的時(shí)候，有可能使得堆內(nèi)存被分割成碎片化的單元。也就是說堆內(nèi)存總體可以使用的內(nèi)存單元較大，但是單獨(dú)的內(nèi)存單元較小，在下次內(nèi)存分配的時(shí)候不能找到合適大小的存儲(chǔ)單元，這也會(huì)觸發(fā)GC操作或者堆內(nèi)存擴(kuò)展操作。

• 堆內(nèi)存碎片會(huì)造成兩個(gè)結(jié)果：一個(gè)是游戲占用的內(nèi)存會(huì)越來越大；一個(gè)是GC會(huì)更加頻繁地被觸發(fā)。

特別是在堆內(nèi)存上進(jìn)行內(nèi)存分配時(shí)內(nèi)存單元不足夠的時(shí)候，GC會(huì)被頻繁觸發(fā)，這就意味著頻繁在堆內(nèi)存上進(jìn)行內(nèi)存分配和回收會(huì)觸發(fā)頻繁的GC操作。

二、Unity托管堆

在講具體的Unity GC機(jī)制之前再回顧一下Unity托管堆。

1. 托管堆的工作原理及其擴(kuò)展原因

“托管堆”是由項(xiàng)目腳本運(yùn)行時(shí)（Mono或IL2CPP）的內(nèi)存管理器自動(dòng)管理的一段內(nèi)存。必須在托管堆上分配托管代碼中創(chuàng)建的所有對(duì)象。

Unity官方文檔圖

在上圖中，白框表示分配給托管堆的內(nèi)存量，而其中的彩色框表示存儲(chǔ)在托管堆的內(nèi)存空間中的數(shù)據(jù)值。當(dāng)需要更多值時(shí)，將從托管堆中分配更多空間。

GC定期運(yùn)行將掃描堆上的所有對(duì)象，將任何不再引用的對(duì)象標(biāo)記為刪除。然后會(huì)刪除未引用的對(duì)象，從而釋放內(nèi)存。

至關(guān)重要的是，Unity的垃圾收集是非分代的，也是非壓縮的。“非分代”意味著GC在執(zhí)行每遍收集時(shí)必須掃描整個(gè)堆，因此隨著堆的擴(kuò)展，其性能會(huì)下降。“非壓縮”意味著不會(huì)為內(nèi)存中的對(duì)象重新分配內(nèi)存地址來消除對(duì)象之間的間隙。

內(nèi)存空隙

上圖為內(nèi)存碎片化示例。釋放對(duì)象時(shí)，將釋放其內(nèi)存。但是，釋放的空間不會(huì)整合成為整個(gè)“可用內(nèi)存”池的一部分。位于釋放的對(duì)象兩側(cè)的對(duì)象可能仍在使用中。因此，釋放的空間成為其他內(nèi)存段之間的“間隙”（該間隙由上圖中的紅色圓圈指示）。因此，新釋放的空間僅可用于存儲(chǔ)與釋放相同大小或更小的對(duì)象的數(shù)據(jù)。

這導(dǎo)致了內(nèi)存碎片化這個(gè)核心問題：雖然堆中的可用空間總量可能很大，但是可能其中的部分或全部的可分配空間對(duì)象之間存在小的“間隙”。這種情況下，即使可用空間總量高于要分配的空間量，托管堆可能也找不到足夠大的連續(xù)內(nèi)存塊來滿足該分配需求。

如果分配了大型對(duì)象又沒有足夠的連續(xù)空間提供使用則：

• 運(yùn)行垃圾回收器，嘗試釋放空間來滿足分配請(qǐng)求。

• 如果在GC運(yùn)行后，仍然沒有足夠的連續(xù)空間來滿足請(qǐng)求的內(nèi)存量，則必須擴(kuò)展堆。堆的具體擴(kuò)展量視平臺(tái)而定。

2. Unity托管堆的問題

• Unity在擴(kuò)展托管堆后不會(huì)經(jīng)常釋放分配給托管堆的內(nèi)存頁,防止再次發(fā)生大量分配時(shí)需要重新擴(kuò)展堆。

• 在大多數(shù)平臺(tái)上，Unity最終會(huì)將托管堆的空置部分使用的頁面釋放回操作系統(tǒng)。發(fā)生此行為的間隔時(shí)間是不確定的，不要指望靠這種方法釋放內(nèi)存。

頻繁分配臨時(shí)數(shù)據(jù)給托管堆，這種情況通常對(duì)項(xiàng)目的性能極為不利。

如果每幀分配1KB的臨時(shí)內(nèi)存，并且以60幀的速率運(yùn)行，那么它必須每秒分配60KB的臨時(shí)內(nèi)存。在一分鐘內(nèi)，這會(huì)在內(nèi)存中增加3.6MB的垃圾。對(duì)內(nèi)存不足的設(shè)備而言每分鐘3.6MB的垃圾也無法接受。

三、Unity的GC機(jī)制 -- Boehm GC

以前看過Unity使用的GC方案但最近才驚覺現(xiàn)在使用的Unity都是IL2CPP的版本了，所謂的Mono GC本來就已經(jīng)不存在了。于是來看下現(xiàn)在的IL2CPP的GC機(jī)制： Boehm GC(貝姆垃圾收集器)。

1. IL2CPP - Boehm GC

貝姆垃圾收集器是計(jì)算機(jī)應(yīng)用在C/C++語言上的一個(gè)保守的垃圾回收器（Garbage Collector），可應(yīng)用于許多經(jīng)由C\C++開發(fā)的程序中。

摘錄一段定義：

Boehm-Demers-Weiser garbage collector，適用于其它執(zhí)行環(huán)境的各類編程語言，包括了GNU版Java編譯器執(zhí)行環(huán)境，以及Mono的Microsoft .NET移植平臺(tái)。同時(shí)支援許多的作業(yè)平臺(tái)，如各種Unix操作系統(tǒng)，微軟的操作系統(tǒng)（Microsoft Windows），以及麥金塔上的操作系統(tǒng)（Mac OS X），還有更進(jìn)一步的功能，例如：漸進(jìn)式收集（Incremental Collection），平行收集（Parallel Collection）以及終結(jié)語意的變化（Variety Offinalizersemantics）。

在Unity中我們可以看到關(guān)于Boehm GC的算法部分：

BoehmGC.cpp內(nèi)部調(diào)用的就是這個(gè)第三方庫，他是Stop-the-world類型的垃圾收集器，這表明了在執(zhí)行垃圾回收的時(shí)候，將會(huì)停止正在運(yùn)行的程序，而停止時(shí)間的只有在完成工作后才會(huì)恢復(fù)，所以這就導(dǎo)致了GC引起的程序卡頓峰值，很顯然這對(duì)游戲的平滑體驗(yàn)造成了較大的負(fù)面影響。

通常，解決這個(gè)問題的常規(guī)方案是盡可能地“減少”運(yùn)行時(shí)垃圾回收（后續(xù)用GC代替），亦或者將GC放在不那么操作敏感的場(chǎng)景中，比如回城、死亡后等。但完全避免運(yùn)行時(shí)垃圾回收在大部分時(shí)間是不現(xiàn)實(shí)的。

接下來我們來看看Boehm GC的背后機(jī)制。

2. Boehm GC算法思路

Boehm GC是一種Mark-Sweep（標(biāo)記-清掃）算法，大致思路包含了四個(gè)階段：

• 準(zhǔn)備階段：每個(gè)托管堆內(nèi)存對(duì)象在創(chuàng)建出來的時(shí)候會(huì)有一個(gè)關(guān)聯(lián)的標(biāo)記位，來表示當(dāng)前對(duì)象是否被引用，默認(rèn)為0。

• 標(biāo)記階段：從根內(nèi)存節(jié)點(diǎn)（靜態(tài)變量；棧；寄存器）出發(fā)，遍歷掃描托管堆的內(nèi)存節(jié)點(diǎn)，將被引用的內(nèi)存節(jié)點(diǎn)標(biāo)記為1。

• 清掃階段：遍歷所有節(jié)點(diǎn)，將沒有被標(biāo)記的節(jié)點(diǎn)的內(nèi)存數(shù)據(jù)清空，并且基于一定條件釋放。

• 結(jié)束階段：觸發(fā)注冊(cè)過的回調(diào)邏輯。

3. 漸進(jìn)式GC

使用漸進(jìn)式GC允許把GC工作分成多個(gè)片，因此為了不讓GC工作長(zhǎng)時(shí)間的“阻塞”主線程，將其拆分成了多個(gè)更短的中斷。需要明確的是這并不會(huì)使GC總體上變得更快，但是卻可以將工作負(fù)載分配到多幀來平緩單次GC峰值帶來的卡頓影響。

注: Unity在高版本已經(jīng)默認(rèn)是漸進(jìn)式GC了，大概是Unity 19.1a10版本。

[Unity 活動(dòng)]-淺談Unity內(nèi)存管理_嗶哩嗶哩_bilibili

https://www.bilibili.com/video/BV1aJ411t7N6/?vd_source=60173b91c5d0a0bed2ae426307dcc6b5

4. GC中的內(nèi)存分配

Boehm GC的使用方法非常簡(jiǎn)單，只需要將malloc替換為GC_malloc即可，在此之后便無需關(guān)心free的問題。

void * GC_malloc(size_t lb)
{
    return GC_malloc_kind(lb, NORMAL);
}


 void * GC_malloc_kind(size_t lb, int k)
{
    return GC_malloc_kind_global(lb, k);
}

在整個(gè)內(nèi)存分配鏈的最底部，Boehm GC通過平臺(tái)相關(guān)接口來向操作系統(tǒng)申請(qǐng)內(nèi)存。為了提高申請(qǐng)的效率，每次批量申請(qǐng)4KB的倍數(shù)大小。

分配器的核心是一個(gè)分級(jí)的結(jié)構(gòu)，Boehm GC把每次申請(qǐng)根據(jù)內(nèi)存大小歸類成小內(nèi)存對(duì)象和大內(nèi)存對(duì)象。

• 小內(nèi)存對(duì)象：不超過PageSize/2，小于2048字節(jié)的對(duì)象。

• 大內(nèi)存對(duì)象：大于PageSize/2的對(duì)象。

對(duì)于大內(nèi)存對(duì)象，向上取整到4KB的倍數(shù)大小，以整數(shù)的內(nèi)存塊形式給出。而小內(nèi)存對(duì)象則會(huì)先申請(qǐng)一個(gè)內(nèi)存塊出來，而后在這塊內(nèi)存上進(jìn)一步細(xì)分為Small Objects，形成free-list。

下面會(huì)分別說下大內(nèi)存對(duì)象和小內(nèi)存對(duì)象，參考網(wǎng)上的資料整理，確實(shí)有點(diǎn)點(diǎn)干，但是配圖我重新做了一下，大概可以輔助消化。

四、IL2CPP - Boehm GC：小內(nèi)存分配

1. 粒度對(duì)齊

實(shí)現(xiàn)思路是，提出粒度（GRANULES）的概念，即一個(gè)GRANULE的大小是16字節(jié)。實(shí)際分配內(nèi)存的時(shí)候按照GRANULE為基本單位來分配。分配過程中，按照原始需要的大小，計(jì)算并映射得到實(shí)際需要分配的GRANULE個(gè)數(shù)，代碼如下：

//lb是原始的分配大小，lg是GRANULE（1～128）。
size_t lg = GC_size_map[lb];

例如需要18字節(jié)的內(nèi)存，則lg=2，即實(shí)際分配2個(gè)GRANULE（32字節(jié)），如果需要1字節(jié)的內(nèi)存，則lg=1，即實(shí)際分配1個(gè)GRANULE（16字節(jié)）。

GC_size_map是一個(gè)“GRANULE索引映射表”，用來維護(hù)原始分配的內(nèi)存大小和內(nèi)存索引之間的關(guān)系。最多可以返回128個(gè)GRANULE，所以小內(nèi)存的大小上限是128*16=2048。GC_size_map數(shù)組本身會(huì)不斷加載根據(jù)需要不斷擴(kuò)容。

示意

2. 空閑鏈表 - ok_freelist

決定了GRANULE的大小之后，在申請(qǐng)內(nèi)存時(shí)刻首先會(huì)從“空閑鏈表”中查看是否有空閑內(nèi)存塊，如果有則直接返回這塊內(nèi)存，完成分配，其算法維護(hù)了一個(gè)數(shù)據(jù)結(jié)構(gòu)obj_kind：

struct obj_kind {
    void **ok_freelist;
    struct hblk **ok_reclaim_list;
    ...
} GC_obj_kinds[3];

GC_obj_kinds[3]對(duì)應(yīng)了3種內(nèi)存類型，分別是PTRFREE、NORMAL和UNCOLLECTABLE，每種類型都有一個(gè)obj_kind結(jié)構(gòu)體信息。

PTRFREE：無指針內(nèi)存分配，明確的告訴GC，該對(duì)象內(nèi)無任何的指針信息，在GC時(shí)候無需查找該對(duì)象是否引用了其他對(duì)象。

NORMAL：無類型的內(nèi)存分配，因?yàn)闊o法得到對(duì)象的類型元數(shù)據(jù)，所以在GC時(shí)會(huì)按照只針對(duì)其的方式掃描內(nèi)存塊，如果通過了指針校驗(yàn)，就會(huì)認(rèn)為該對(duì)象引用了該指針地址指向的對(duì)象。

UNCOLLECTABLE：為BOEHM自己分配的內(nèi)存，這些不需要標(biāo)記和回收。

每一個(gè)obj_kind的結(jié)構(gòu)體都維護(hù)了一個(gè)ok_freelist的二維指針鏈表用來存放空閑的內(nèi)存塊。ok_freelist維護(hù)了0~127個(gè)鏈表索引。而每一個(gè)尺寸的freelist就是對(duì)應(yīng)大小的GRANULE池子，其結(jié)構(gòu)示意如圖：

freelist示意

于是，根據(jù)要申請(qǐng)的內(nèi)存大小計(jì)算得到GRANULE在freelist的索引，然后去查詢對(duì)應(yīng)索引的freelist，如果存在空閑看空間ok_freelist[index][0]，則將其返回并從鏈上移除。

ok_freelist鏈表最初為空，如果ok_freelist中沒有相應(yīng)的空閑內(nèi)存塊，則調(diào)用GC_allocobj(lg, k)去底層查找可用的內(nèi)存。

GC_allocobj的核心邏輯是調(diào)用GC_new_hblk(gran, kind)去底層內(nèi)存池獲取內(nèi)存，并且查看底層內(nèi)存池中是否分配了空閑的內(nèi)存塊，如果沒有則通過系統(tǒng)函數(shù)例如malloc分配內(nèi)存給底層內(nèi)存池，如果內(nèi)存池有，直接取出一塊返回。GC_new_hblk的代碼邏輯如下：

GC_INNER void GC_new_hblk(size_t gran, int kind)
{
    struct hblk *h; /* the new heap block */
    GC_bool clear = GC_obj_kinds[kind].ok_init;

     /* Allocate a new heap block */
    h = GC_allochblk(GRANULES_TO_BYTES(gran), kind, 0);
    if (h == 0) return;

     /* Build the free list */
    GC_obj_kinds[kind].ok_freelist[gran] =
    GC_build_fl(h, GRANULES_TO_WORDS(gran), clear,(ptr_t)GC_obj_kinds[kind].ok_freelist[gran]);
}

GC_new_hblk的主要邏輯有2步：

1. 調(diào)用GC_allochblk方法進(jìn)一步獲取內(nèi)存池中可用的內(nèi)存塊；

2. 調(diào)用GC_build_fl方法，利用內(nèi)存池中返回的內(nèi)存塊構(gòu)建ok_freelist，供上層使用。

3. 核心內(nèi)存塊鏈表GC_hblkfreelist

底層內(nèi)存池的實(shí)現(xiàn)邏輯和ok_freelist類似，維護(hù)了一個(gè)空閑內(nèi)存塊鏈表的指針鏈表GC_hblkfreeelist，但是和ok_freelist不同的是，這個(gè)鏈表中的內(nèi)存塊的基本單位是4KB，也就是一個(gè)內(nèi)存頁（page_size）的大小。GC_hblkfreelist一個(gè)有60個(gè)元素，每一個(gè)元素都是一個(gè)鏈表。

4. 內(nèi)存塊 - hblk、頭信息 - hblkhdr

鏈表中的每一個(gè)內(nèi)存塊都以大小4096（4KB）為一基本單位，一個(gè)大小為4096的內(nèi)存塊被稱為hblk，數(shù)據(jù)定義如下：

struct hblk {
    char hb_body[HBLKSIZE]; //HBLKSIZE=4096
};

每個(gè)hblk擁有一個(gè)相應(yīng)的header信息，用來描述這個(gè)內(nèi)存快的情況，數(shù)據(jù)的定義如下：

//頭部信息
struct hblkhdr {
    struct hblk * hb_next; //指向下一個(gè)hblk
    struct hblk * hb_prev; //指向上一個(gè)hblk
    struct hblk * hb_block; //對(duì)應(yīng)的hblk
    unsigned char hb_obj_kind; //kink類型
    unsigned char hb_flags; //標(biāo)記位
    word hb_sz; //如果給上層使用，則表示實(shí)際分配的單位，如果空閑，則表示內(nèi)存塊的大小
    word hb_descr; 
    size_t hb_n_marks;//標(biāo)記位個(gè)數(shù)，用于GC
    word hb_marks[MARK_BITS_SZ]; //標(biāo)記為，用于GC
}

5. hblk內(nèi)存塊查詢

structh blk *GC_allochblk(size_t sz, int kind, unsigned flags/* IGNORE_OFF_PAGE or 0 */)
{
    ...
    //1.計(jì)算需要的內(nèi)存塊大小
    blocks_needed = OBJ_SZ_TO_BLOCKS_CHECKED(sz);
    start_list = GC_hblk_fl_from_blocks(blocks_needed);

     //2.查找精確的hblk內(nèi)存塊
    result = GC_allochblk_nth(sz, kind, flags, start_list, FALSE);
    if (0 != result) return result;

     may_split = TRUE;
    ...
    if (start_list < UNIQUE_THRESHOLD) {
        ++start_list;
    }
    //3.從更大的內(nèi)存塊鏈表中找
    for (; start_list <= split_limit; ++start_list) {
        result = GC_allochblk_nth(sz, kind, flags, start_list, may_split);
        if (0 != result) break;
    }
    return result;
}

 STATIC int GC_hblk_fl_from_blocks(word blocks_needed)
{
    if (blocks_needed <= 32) return blocks_needed;
    if (blocks_needed >= 256) return (256-32)/8+32;
    return (blocks_needed-32)/8+32;
}

先根據(jù)上層需要分配的內(nèi)存大小計(jì)算出需要的內(nèi)存塊大小，如果申請(qǐng)的大小小于4096字節(jié)，則結(jié)果是1，對(duì)于小對(duì)象內(nèi)存塊的個(gè)數(shù)就是1。

根據(jù)實(shí)際需要的內(nèi)存塊數(shù)，判斷并決定從哪一個(gè)GC_hblkfreelist鏈表查找，start_list是開始查找的鏈表index，即從GC_hblkfreelist[start_list]開始查找。并不是需要blocks，就一定會(huì)從GC_hblkfreelist[blocks]的鏈表中查找，遵循轉(zhuǎn)換規(guī)則（小內(nèi)存索引是連續(xù)的，中內(nèi)存索引是32+8的步長(zhǎng)，大點(diǎn)的內(nèi)存索引都是60）。

• 如果blocks_needed小于32，則startlist=blocks_needed，直接去GC_hblkfreelist[blocks_needed]中查找。

• 如果blocks_needed位于32～256，則startlist=(blocks_needed-32)/8+32，即blocks_needed每增加8個(gè)，對(duì)應(yīng)GC_hblkfreelist[index]的index增加1。

• 如果blocks_needed大于256，則都從GC_hblkfreelist[60]鏈表中查找。

決定從哪個(gè)鏈表開始查找之后，首先進(jìn)行精確查找，如果直接找到，則直接返回找到的內(nèi)存塊。

如果精準(zhǔn)查找失敗，則逐漸增大start_list，從更大的內(nèi)存塊鏈表中查找。

STATIC struct hblk *GC_allochblk_nth(size_t sz, int kind, unsigned flags, int n, int may_split)
{
    struct hblk *hbp;
    hdr * hhdr;
    struct hblk *thishbp;
    hdr * thishdr;/* Header corr. to thishbp */
    //計(jì)算需要分配的內(nèi)存塊大小
    signed_word size_needed = HBLKSIZE * OBJ_SZ_TO_BLOCKS_CHECKED(sz);


     //從鏈表中查找合適的內(nèi)存塊
    for (hbp = GC_hblkfreelist[n];; hbp = hhdr -> hb_next) {
        signed_word size_avail;
        if (NULL == hbp) return NULL;
        //獲取內(nèi)存塊的header信息
        GET_HDR(hbp, hhdr);
        //內(nèi)存塊大小
        size_avail = (signed_word)hhdr->hb_sz;
        if (size_avail < size_needed) continue;
        //可用內(nèi)存大于需要的分配的大小
        if (size_avail != size_needed) {
            //要求精準(zhǔn)不分割，退出循環(huán)，返回空
            if (!may_split) continue;
            ...
            if( size_avail >= size_needed ) {
                ...
                //分割內(nèi)存塊，修改鏈表
                hbp = GC_get_first_part(hbp, hhdr, size_needed, n);
                break;
            }
        }
    }
    if (0 == hbp) return0;
    ...
    //修改header信息
    setup_header(hhdr, hbp, sz, kind, flags)
    ...
    return hbp;
}

當(dāng)分配字節(jié)的時(shí)候先通過精確查找如果發(fā)現(xiàn)有精確內(nèi)存，則會(huì)返回相應(yīng)的內(nèi)存塊，如果沒有發(fā)現(xiàn)精確內(nèi)存則會(huì)去查找更大的內(nèi)存塊并進(jìn)行分割，一半返回使用，一半放到池子里。

拆分示意

如上圖示例，如果要申請(qǐng)1KB，則會(huì)先找4KB，如果沒有4KB則去找8KB，找到了8KB就進(jìn)行兩個(gè)4KB的拆分，然后移除8KB出池子，再把拆分過的另一半4KB內(nèi)存塊加入到池子里：

STATIC struct hblk *GC_get_first_part(struct hblk *h, hdr *hhdr, size_t bytes, int index) {
    word total_size = hhdr -> hb_sz;
    struct hblk * rest;
    hdr * rest_hdr;
    //從空閑鏈表刪除
    GC_remove_from_fl_at(hhdr, index);
    if (total_size == bytes) return h;
    //后半部分
    rest = (struct hblk *)((word)h + bytes);
    //生成header信息
    rest_hdr = GC_install_header(rest);
    //內(nèi)存塊大小
    rest_hdr -> hb_sz = total_size - bytes;
    rest_hdr -> hb_flags = 0;
    ...
    //加入相應(yīng)的空閑鏈表
    GC_add_to_fl(rest, rest_hdr);
}

6. 內(nèi)存塊分配

如果GC_hblkfreelist空閑鏈表中找不到合適的內(nèi)存塊，則考慮從系統(tǒng)開辟一段新的內(nèi)存，并添加到GC_hblkfreelist鏈表中。在GC_expand_hp_inner方法中實(shí)現(xiàn)：

GC_INNER GC_bool GC_expand_hp_inner(word n)
{
    ...
    //調(diào)用系統(tǒng)方式開辟內(nèi)存
    space = GET_MEM(bytes);
    //記錄內(nèi)存地址和大小
    GC_add_to_our_memory((ptr_t)space, bytes);
    ...
    //添加到GC_hblkfreelist鏈表中
    GC_add_to_heap(space, bytes);
    ...
}

GC_add_to_heap方法將創(chuàng)建出來的內(nèi)存塊加入相應(yīng)的GC_hblkfreelist鏈表中。同時(shí)加入一個(gè)全局的存放堆內(nèi)存信息的數(shù)組中。

其中如果發(fā)現(xiàn)內(nèi)存連續(xù)的前后內(nèi)存塊存在且空閑，則合并前后的內(nèi)存塊，生成一個(gè)更大的內(nèi)存塊。

7. ok_freeList

在GC_new_hblk中調(diào)用GC_build_fl方法構(gòu)建鏈表，就是這個(gè)GC系統(tǒng)的緩存池核心數(shù)據(jù)結(jié)構(gòu)。

//構(gòu)建ok_freelist[gran]
GC_obj_kinds[kind].ok_freelist[gran] = GC_build_fl(h, GRANULES_TO_WORDS(gran), clear,(ptr_t)GC_obj_kinds[kind].ok_freelist[gran]);

 GC_INNER ptr_t GC_build_fl(struct hblk *h, size_t sz, GC_bool clear,
ptr_t list) {
    word *p, *prev;
    word *last_object;/* points to last object in new hblk*/
    ...
    //構(gòu)建鏈表
    p = (word *)(h -> hb_body) + sz;/* second object in *h*/
    prev = (word *)(h -> hb_body);/* One object behind p*/
    last_object = (word *)((char *)h + HBLKSIZE);
    last_object -= sz;
    while ((word)p <= (word)last_object) {
        /* current object's link points to last object */
        obj_link(p) = (ptr_t)prev;
        prev = p;
        p += sz;
    }
    p -= sz;

     //拼接之前的鏈表
    *(ptr_t *)h = list;
    //返回入口地址
    return ((ptr_t)p);
}

以4096字節(jié)的內(nèi)存塊劃分為16字節(jié)單元的freeList為例，步驟如下：

1. 4096字節(jié)按照16字節(jié)分配，劃分為256個(gè)小內(nèi)存塊，編號(hào)是0～255，將最后一個(gè)內(nèi)存塊（255）作為新鏈表的首節(jié)點(diǎn)。

2. 內(nèi)存地址向前遍歷，建立鏈表，即255的下一個(gè)節(jié)點(diǎn)是254，尾節(jié)點(diǎn)是0。

3. 將尾節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指向原鏈表的首地址。

4. 將新鏈表的首節(jié)點(diǎn)地址作為ok_freelist[N]，N是上文提到的GRANULE，例如16字節(jié)對(duì)應(yīng)1。

重建好的freeList，并將首節(jié)點(diǎn)提供給上層使用。

五、Boehm GC：大內(nèi)存分配

分配大內(nèi)存對(duì)象是指分配的內(nèi)存大于2048字節(jié)。

OBJ_SZ_TO_BLOCKS用于計(jì)算需要的hblk內(nèi)存塊的個(gè)數(shù)，對(duì)于大內(nèi)存，需要的個(gè)數(shù)大于等于1。例如需要分配9000字節(jié)的內(nèi)存，則需要3個(gè)hblk內(nèi)存塊，然后調(diào)用GC_alloc_large分配內(nèi)存。

GC_INNER ptr_t GC_alloc_large(size_t lb, int k, unsigned flags)
{
    struct hblk * h;
    word n_blocks;
    ptr_t result;
    ...
    n_blocks = OBJ_SZ_TO_BLOCKS_CHECKED(lb);
    ...
    //分配內(nèi)存
    h = GC_allochblk(lb, k, flags);
    ...
    //分配失敗，系統(tǒng)分配內(nèi)存塊后繼續(xù)嘗試分配
    while (0 == h && GC_collect_or_expand(n_blocks, flags != 0, retry)) {
        h = GC_allochblk(lb, k, flags);
        retry = TRUE;
    }
    //記錄大內(nèi)存創(chuàng)建大小
    size_t total_bytes = n_blocks * HBLKSIZE;
    ...
    GC_large_allocd_bytes += total_bytes;
    ...
    result = h -> hb_body;
    //返回內(nèi)存地址
    return result;
}

大內(nèi)存分配的內(nèi)存查找和小對(duì)象方式一樣，會(huì)不斷增加start_list。從更大的鏈表中查找是否有空閑內(nèi)存，不同的是，如果查找到了空閑內(nèi)存不會(huì)分裂構(gòu)建ok_freeList鏈表而是直接返回大內(nèi)存塊的地址提供使用。

六、Boehm GC：內(nèi)存分配流程圖

示意

七、額外：SGen GC

Simple Generational Garbage Collection簡(jiǎn)稱SGen GC，是相比Boehm GC（貝姆GC）更為先進(jìn)的一種GC方式。官方Mono在2.8版本中增加了SGen GC，但默認(rèn)的仍是Boehm GC。3.2版本之后，Mono正式將SGen GC作為默認(rèn)GC方式。

SGen GC將堆內(nèi)存分為初生代（Nursery）和舊生代（Old Generation）兩代進(jìn)行管理，并包含兩個(gè)GC過程：Minor GC對(duì)初生代進(jìn)行清理；Major GC對(duì)初生代和舊生代同時(shí)進(jìn)行清理。

1. 內(nèi)存分配策略 - 初代

在SGen GC中，初生代是一塊固定大小的連續(xù)內(nèi)存，默認(rèn)為4MB，可以通過配置修改。這一點(diǎn)與G1不同，在G1中同一代的Region在物理上是不要求連續(xù)的。

為了支持多線程工作，新對(duì)象的內(nèi)存分配依然在每個(gè)線程的TLAB中進(jìn)行，當(dāng)前每個(gè)TLAB均為4KB，有提到可能會(huì)在不久后進(jìn)行優(yōu)化。而在TLAB內(nèi)部，內(nèi)存分配是通過指針碰撞的方式進(jìn)行的，也就是說，在SGen GC中，初生代內(nèi)存并沒有進(jìn)行粒度劃分也沒有分塊管理。

初生代對(duì)象跟隨Minor GC和Major GC進(jìn)行回收。

2. 內(nèi)存分配策略 - 舊代

在SGen GC中，舊生代內(nèi)存劃分方式可以概括為：

Section（1MB） → Block（16KB）→ Page（4KB）→ Slot（不同粒度）

在使用內(nèi)存時(shí)，按照上述鏈條依次向下拆分，與貝姆GC相同，同一個(gè)Block中的Page也只能拆分成相同粒度的Slot。

雖然在初生代中并沒有劃分內(nèi)存粒度，但是當(dāng)對(duì)象從初生代轉(zhuǎn)移到舊生代時(shí)會(huì)找到對(duì)應(yīng)粒度的Slot進(jìn)行存儲(chǔ)。釋放對(duì)象時(shí)，對(duì)應(yīng)的Slot也會(huì)返還給空閑鏈表（類似貝姆GC中的ok_freeList），并在某一級(jí)結(jié)構(gòu)完全清空時(shí)依次向上一級(jí)返還。

舊生代內(nèi)存最終是通過一個(gè)GCMemSection結(jié)構(gòu)的鏈表進(jìn)行管理的。

3. 內(nèi)存分配策略 - 大對(duì)象

超過8KB的對(duì)象均被視為大對(duì)象，大對(duì)象通過單獨(dú)的LOSSection結(jié)構(gòu)進(jìn)行管理。而大對(duì)象的內(nèi)存管理又分為兩種情況：

• 不超過1MB的，仍然存儲(chǔ)在Mono自己的托管堆上，清理后返還給托管堆；

• 超過1MB的，直接從操作系統(tǒng)申請(qǐng)內(nèi)存，清理后內(nèi)存也同樣返還給操作系統(tǒng)。

4. 內(nèi)存分配策略 - 固定內(nèi)存對(duì)象

有一些對(duì)象被顯式或隱式地標(biāo)記為了固定內(nèi)存的對(duì)象，這些對(duì)象在初始時(shí)依然被分配在初生代中，但不會(huì)被GC過程移動(dòng)位置。

• 顯式：用戶顯式聲明的，比如通過fixed關(guān)鍵字進(jìn)行修飾；

• 隱式：在GC開始時(shí)，所有寄存器和ROOT中直接指向的對(duì)象都視為固定內(nèi)存對(duì)象。

文末，再次感謝Jamin 的分享， 作者主頁：https://www.zhihu.com/people/liang-zhi-ming-70， 如果您有任何獨(dú)到的見解或者發(fā)現(xiàn)也歡迎聯(lián)系我們，一起探討。（QQ群： 793972859 ）。

近期精彩回顧