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

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

作者主頁：

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

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

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

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

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

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

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

• GC會自動觸發(fā)，不同平臺運行頻率不一樣。

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

2. GC操作帶來的問題

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

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

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

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

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

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

二、Unity托管堆

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

1. 托管堆的工作原理及其擴展原因

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

Unity官方文檔圖

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

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

至關(guān)重要的是，Unity的垃圾收集是非分代的，也是非壓縮的?！胺欠执币馕吨鳪C在執(zhí)行每遍收集時必須掃描整個堆，因此隨著堆的擴展，其性能會下降?！胺菈嚎s”意味著不會為內(nèi)存中的對象重新分配內(nèi)存地址來消除對象之間的間隙。

內(nèi)存空隙

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

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

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

• 運行垃圾回收器，嘗試釋放空間來滿足分配請求。

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

2. Unity托管堆的問題

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

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

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

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

三、Unity的GC機制 -- Boehm GC

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

1. IL2CPP - Boehm GC

貝姆垃圾收集器是計算機應(yīng)用在C/C++語言上的一個保守的垃圾回收器（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移植平臺。同時支援許多的作業(yè)平臺，如各種Unix操作系統(tǒng)，微軟的操作系統(tǒng)（Microsoft Windows），以及麥金塔上的操作系統(tǒng)（Mac OS X），還有更進一步的功能，例如：漸進式收集（Incremental Collection），平行收集（Parallel Collection）以及終結(jié)語意的變化（Variety Offinalizersemantics）。

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

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

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

接下來我們來看看Boehm GC的背后機制。

2. Boehm GC算法思路

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

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

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

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

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

3. 漸進式GC

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

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

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

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

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

Boehm GC的使用方法非常簡單，只需要將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);
}

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

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

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

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

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

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

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

1. 粒度對齊

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

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

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

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

示意

2. 空閑鏈表 - ok_freelist

決定了GRANULE的大小之后，在申請內(nèi)存時刻首先會從“空閑鏈表”中查看是否有空閑內(nèi)存塊，如果有則直接返回這塊內(nèi)存，完成分配，其算法維護了一個數(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]對應(yīng)了3種內(nèi)存類型，分別是PTRFREE、NORMAL和UNCOLLECTABLE，每種類型都有一個obj_kind結(jié)構(gòu)體信息。

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

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

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

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

freelist示意

于是，根據(jù)要申請的內(nèi)存大小計算得到GRANULE在freelist的索引，然后去查詢對應(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方法進一步獲取內(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)存池的實現(xiàn)邏輯和ok_freelist類似，維護了一個空閑內(nèi)存塊鏈表的指針鏈表GC_hblkfreeelist，但是和ok_freelist不同的是，這個鏈表中的內(nèi)存塊的基本單位是4KB，也就是一個內(nèi)存頁（page_size）的大小。GC_hblkfreelist一個有60個元素，每一個元素都是一個鏈表。

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

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

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

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

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

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

structh blk *GC_allochblk(size_t sz, int kind, unsigned flags/* IGNORE_OFF_PAGE or 0 */)
{
    ...
    //1.計算需要的內(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)存大小計算出需要的內(nèi)存塊大小，如果申請的大小小于4096字節(jié)，則結(jié)果是1，對于小對象內(nèi)存塊的個數(shù)就是1。

根據(jù)實際需要的內(nèi)存塊數(shù)，判斷并決定從哪一個GC_hblkfreelist鏈表查找，start_list是開始查找的鏈表index，即從GC_hblkfreelist[start_list]開始查找。并不是需要blocks，就一定會從GC_hblkfreelist[blocks]的鏈表中查找，遵循轉(zhuǎn)換規(guī)則（小內(nèi)存索引是連續(xù)的，中內(nèi)存索引是32+8的步長，大點的內(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個，對應(yīng)GC_hblkfreelist[index]的index增加1。

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

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

如果精準查找失敗，則逐漸增大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 */
    //計算需要分配的內(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) {
            //要求精準不分割，退出循環(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;
}

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

拆分示意

如上圖示例，如果要申請1KB，則會先找4KB，如果沒有4KB則去找8KB，找到了8KB就進行兩個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方法中實現(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鏈表中。同時加入一個全局的存放堆內(nèi)存信息的數(shù)組中。

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

7. ok_freeList

在GC_new_hblk中調(diào)用GC_build_fl方法構(gòu)建鏈表，就是這個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個小內(nèi)存塊，編號是0～255，將最后一個內(nèi)存塊（255）作為新鏈表的首節(jié)點。

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

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

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

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

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

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

OBJ_SZ_TO_BLOCKS用于計算需要的hblk內(nèi)存塊的個數(shù)，對于大內(nèi)存，需要的個數(shù)大于等于1。例如需要分配9000字節(jié)的內(nèi)存，則需要3個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)存查找和小對象方式一樣，會不斷增加start_list。從更大的鏈表中查找是否有空閑內(nèi)存，不同的是，如果查找到了空閑內(nèi)存不會分裂構(gòu)建ok_freeList鏈表而是直接返回大內(nèi)存塊的地址提供使用。

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

示意

七、額外：SGen GC

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

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

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

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

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

初生代對象跟隨Minor GC和Major GC進行回收。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

近期精彩回顧