Go語言 垃圾回收上篇

Go語言中使用的垃圾回收使用的是標(biāo)記清掃算法。進(jìn)行垃圾回收時(shí)會(huì)stoptheworld。不過，在當(dāng)前1.3版本中，實(shí)現(xiàn)了精確的垃圾回收和并行的垃圾回收，大大地提高了垃圾回收的速度，進(jìn)行垃圾回收時(shí)系統(tǒng)并不會(huì)長(zhǎng)時(shí)間卡住。

標(biāo)記清掃算法

標(biāo)記清掃算法是一個(gè)很基礎(chǔ)的垃圾回收算法，該算法中有一個(gè)標(biāo)記初始的root區(qū)域，以及一個(gè)受控堆區(qū)。root區(qū)域主要是程序運(yùn)行到當(dāng)前時(shí)刻的棧和全局?jǐn)?shù)據(jù)區(qū)域。在受控堆區(qū)中，很多數(shù)據(jù)是程序以后不需要用到的，這類數(shù)據(jù)就可以被當(dāng)作垃圾回收了。判斷一個(gè)對(duì)象是否為垃圾，就是看從root區(qū)域的對(duì)象是否有直接或間接的引用到這個(gè)對(duì)象。如果沒有任何對(duì)象引用到它，則說明它沒有被使用，因此可以安全地當(dāng)作垃圾回收掉。

標(biāo)記清掃算法分為兩階段：標(biāo)記階段和清掃階段。標(biāo)記階段，從root區(qū)域出發(fā)，掃描所有root區(qū)域的對(duì)象直接或間接引用到的對(duì)象，將這些對(duì)上全部加上標(biāo)記。在回收階段，掃描整個(gè)堆區(qū)，對(duì)所有無標(biāo)記的對(duì)象進(jìn)行回收。(補(bǔ)圖)

位圖標(biāo)記和內(nèi)存布局

既然垃圾回收算法要求給對(duì)象加上垃圾回收的標(biāo)記，顯然是需要有標(biāo)記位的。一般的做法會(huì)將對(duì)象結(jié)構(gòu)體中加上一個(gè)標(biāo)記域，一些優(yōu)化的做法會(huì)利用對(duì)象指針的低位進(jìn)行標(biāo)記，這都只是些奇技淫巧罷了。Go沒有這么做，它的對(duì)象和C的結(jié)構(gòu)體對(duì)象完全一致，使用的是非侵入式的標(biāo)記位，我們看看它是怎么實(shí)現(xiàn)的。

堆區(qū)域?qū)?yīng)了一個(gè)標(biāo)記位圖區(qū)域，堆中每個(gè)字(不是byte，而是word)都會(huì)在標(biāo)記位區(qū)域中有對(duì)應(yīng)的標(biāo)記位。每個(gè)機(jī)器字(32位或64位)會(huì)對(duì)應(yīng)4位的標(biāo)記位。因此，64位系統(tǒng)中相當(dāng)于每個(gè)標(biāo)記位圖的字節(jié)對(duì)應(yīng)16個(gè)堆中的字節(jié)。

雖然是一個(gè)堆字節(jié)對(duì)應(yīng)4位標(biāo)記位，但標(biāo)記位圖區(qū)域的內(nèi)存布局并不是按4位一組，而是16個(gè)堆字節(jié)為一組，將它們的標(biāo)記位信息打包存儲(chǔ)的。每組64位的標(biāo)記位圖從上到下依次包括：

16位的 特殊位 標(biāo)記位
16位的 垃圾回收 標(biāo)記位
16位的 無指針/塊邊界 的標(biāo)記位
16位的 已分配 標(biāo)記位

這樣設(shè)計(jì)使得對(duì)一個(gè)類型的相應(yīng)的位進(jìn)行遍歷很容易。

前面提到堆區(qū)域和堆地址的標(biāo)記位圖區(qū)域是分開存儲(chǔ)的，其實(shí)它們是以mheap.arena_start地址為邊界，向上是實(shí)際使用的堆地址空間，向下則是標(biāo)記位圖區(qū)域。以64位系統(tǒng)為例，計(jì)算堆中某個(gè)地址的標(biāo)記位的公式如下：

偏移 = 地址 - mheap.arena_start
標(biāo)記位地址 = mheap.arena_start - 偏移/16 - 1
移位 = 偏移 % 16
標(biāo)記位 = *標(biāo)記位地址 >> 移位

然后就可以通過 (標(biāo)記位 & 垃圾回收標(biāo)記位),(標(biāo)記位 & 分配位),等來測(cè)試相應(yīng)的位。其中已分配的標(biāo)記為1<<0,無指針/塊邊界是1<<16,垃圾回收的標(biāo)記位為1<<32,特殊位1<<48

具體的內(nèi)存布局如下圖所示: 

精確的垃圾回收

像C這種不支持垃圾回收的語言，其實(shí)還是有些垃圾回收的庫可以使用的。這類庫一般也是用的標(biāo)記清掃算法實(shí)現(xiàn)的，但是它們都是保守的垃圾回收。為什么叫“保守”的垃圾回收呢？之所以叫“保守”是因?yàn)樗鼈儧]辦法獲取對(duì)象類型信息，因此只能保守地假設(shè)地址區(qū)間中每個(gè)字都是指針。

無法獲取對(duì)象的類型信息會(huì)造成什么問題呢？這里舉兩個(gè)例子來說明。先看第一個(gè)例子，假設(shè)某個(gè)結(jié)構(gòu)體中是不包含指針成員的，那么對(duì)該結(jié)構(gòu)體成員進(jìn)行垃圾回收時(shí)，其實(shí)是不必要遞歸地標(biāo)記結(jié)構(gòu)體的成員的。但是由于沒有類型信息，我們并不知道這個(gè)結(jié)構(gòu)體成員不包含指針，因此我們只能對(duì)結(jié)構(gòu)體的每個(gè)字節(jié)遞歸地標(biāo)記下去，這顯然會(huì)浪費(fèi)很多時(shí)間。這個(gè)例子說明精確的垃圾回收可以減少不必要的掃描，提高標(biāo)記過程的速度。

再看另一個(gè)例子，假設(shè)堆中有一個(gè)long的變量，它的值是8860225560。但是我們不知道它的類型是long，所以在進(jìn)行垃圾回收時(shí)會(huì)把個(gè)當(dāng)作指針處理，這個(gè)指針引用到了0x2101c5018位置。假設(shè)0x2101c5018碰巧有某個(gè)對(duì)象，那么這個(gè)對(duì)象就無法被釋放了，即使實(shí)際上已經(jīng)沒任何地方使用它。這個(gè)例子說明，保守的垃圾回收某些情況下會(huì)出現(xiàn)垃圾無法被回收。雖然不會(huì)造成大的問題，但總是讓人很不爽，都是沒有類型信息惹的禍。

現(xiàn)在好了，Go在1.1版本中開始支持精確的垃圾回收。精確的垃圾回收首先需要的就是類型信息，上一節(jié)中講過MSpan結(jié)構(gòu)體，類型信息是存儲(chǔ)在MSpan中的。從一個(gè)地址計(jì)算它所屬的MSpan，公式如下：

頁號(hào) = (地址 - mheap.arena_start) >> 頁大小
MSpan = mheap->map[頁號(hào)]

接下來通過MSpan->type可以得到分配塊的類型。這是一個(gè)MType的結(jié)構(gòu)體：

    struct MTypes
    {
        byte    compression;    // one of MTypes_*
        bool    sysalloc;    // whether (void*)data is from runtime·SysAlloc
        uintptr    data;
    };

MTypes描述MSpan里分配的塊的類型，其中compression域描述數(shù)據(jù)的布局。它的取值為MTypes_Empty，MTypes_Single，MTypes_Words，MTypes_Bytes四個(gè)中的一種。

MTypes_Empty:
    所有的塊都是free的，或者這個(gè)分配塊的類型信息不可用。這種情況下data域是無意義的。
MTypes_Single:
    這個(gè)MSpan只包含一個(gè)塊，data域存放類型信息，sysalloc域無意義
MTypes_Words:
    這個(gè)MSpan包含多個(gè)塊(塊的種類多于7)。這時(shí)data指向一個(gè)數(shù)組[NumBlocks]uintptr,，數(shù)組里每個(gè)元素存放相應(yīng)塊的類型信息
MTypes_Bytes:
    這個(gè)MSpan中包含最多7種不同類型的塊。這時(shí)data域指下面這個(gè)結(jié)構(gòu)體
    struct {
        type  [8]uintptr       // type[0] is always 0
        index [NumBlocks]byte
    }
    第i個(gè)塊的類型是data.type[data.index[i]]

表面上看MTypes_Bytes好像最復(fù)雜，其實(shí)這里的復(fù)雜程度是MTypes_Empty小于MTypes_Single小于MTypes_Bytes小于MTypes_Words的。MTypes_Bytes只不過為了做優(yōu)化而顯得很復(fù)雜。

上一節(jié)中說過，每一塊MSpan中存放的塊的大小都是一樣的，不過它們的類型不一定相同。如果沒有使用，那么這個(gè)MSpan的類型就是MTypes_Empty。如果存一個(gè)很大塊，大于這個(gè)MSpan大小的一半，因此存不了其它東西了，那么這個(gè)MSpan的類型是MTypes_Single。假設(shè)存了多種塊，每一塊用一個(gè)指針，本來可以直接用MTypes_Words存的。但是當(dāng)類型不多時(shí)，可以把這些類型的指針集中起來放在數(shù)組中，然后存儲(chǔ)數(shù)組索引。這是一個(gè)小的優(yōu)化，可以節(jié)省內(nèi)存空間。

得到的類型信息最終是什么樣子的呢？其實(shí)是一個(gè)這樣的結(jié)構(gòu)體：

struct Type
{
    uintptr size;
    uint32 hash;
    uint8 _unused;
    uint8 align;
    uint8 fieldAlign;
    uint8 kind;
    Alg *alg;
    void *gc;
    String *string;
    UncommonType *x;
    Type *ptrto;
};

不同類型的類型信息結(jié)構(gòu)體略有不同，這個(gè)是通用的部分?？梢钥吹竭@個(gè)結(jié)構(gòu)體中有一個(gè)gc域，精確的垃圾回收就是利用類型信息中這個(gè)gc域?qū)崿F(xiàn)的。

從gc出去其實(shí)是一段指令碼，是對(duì)這種類型的數(shù)據(jù)進(jìn)行垃圾回收的指令，Go中用一個(gè)狀態(tài)機(jī)來執(zhí)行垃圾回收指令碼。大致的框架是類似下面這樣子：

    for(;;) {
        switch(pc[0]) {
            case GC_PTR:
            break;
            case GC_SLICE:
            break;
            case GC_APTR:
            break;
            case GC_STRING:
            continue;
            case GC_EFACE:
            if(eface->type == nil)
                continue;
            break;
            case GC_IFACE:
            break;
            case GC_DEFAULT_PTR:
            while(stack_top.b <= end_b) {
                obj = *(byte**)stack_top.b;
                stack_top.b += PtrSize;
                if(obj >= arena_start && obj < arena_used) {
                    *ptrbufpos++ = (PtrTarget){obj, 0};
                    if(ptrbufpos == ptrbuf_end)
                        flushptrbuf(ptrbuf, &ptrbufpos, &wp, &wbuf, &nobj);
                }
            }
            case GC_ARRAY_START:
            continue;
            case GC_ARRAY_NEXT:
            continue;
            case GC_CALL:
            continue;
            case GC_MAP_PTR:
            continue;
            case GC_MAP_NEXT:
            continue;
            case GC_REGION:
            continue;
            case GC_CHAN_PTR:
            continue;
            case GC_CHAN:
            continue;
            default:
            runtime·throw("scanblock: invalid GC instruction");
            return;
        }
    }

小結(jié)

Go語言使用標(biāo)記清掃的垃圾回收算法，標(biāo)記位圖是非侵入式的，內(nèi)存布局設(shè)計(jì)得比較巧妙。并且當(dāng)前版本的Go實(shí)現(xiàn)了精確的垃圾回收。在精確的垃圾回收中，通過定位對(duì)象的類型信息，得到該類型中的垃圾回收的指令碼，通過一個(gè)狀態(tài)機(jī)解釋這段指令碼來執(zhí)行特定類型的垃圾回收工作。

對(duì)于堆中任意地址的對(duì)象，找到它的類型信息過程為，先通過它在的內(nèi)存頁找到它所屬的MSpan，然后通過MSpan中的類型信息找到它的類型信息。

不知道讀者有沒有注意一個(gè)細(xì)節(jié)，MType中的data值應(yīng)該是存放Type結(jié)構(gòu)體的指針，但它卻是uintptr表示的。這是為什么呢？