Go語言 垃圾回收上篇

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

標記清掃算法

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

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

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

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

堆區(qū)域?qū)艘粋€標記位圖區(qū)域，堆中每個字(不是byte，而是word)都會在標記位區(qū)域中有對應的標記位。每個機器字(32位或64位)會對應4位的標記位。因此，64位系統(tǒng)中相當于每個標記位圖的字節(jié)對應16個堆中的字節(jié)。

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

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

這樣設計使得對一個類型的相應的位進行遍歷很容易。

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

偏移 = 地址 - mheap.arena_start
標記位地址 = mheap.arena_start - 偏移/16 - 1
移位 = 偏移 % 16
標記位 = *標記位地址 >> 移位

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

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

精確的垃圾回收

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

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

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

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

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

接下來通過MSpan->type可以得到分配塊的類型。這是一個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四個中的一種。

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

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

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

得到的類型信息最終是什么樣子的呢？其實是一個這樣的結(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)體略有不同，這個是通用的部分?？梢钥吹竭@個結(jié)構(gòu)體中有一個gc域，精確的垃圾回收就是利用類型信息中這個gc域?qū)崿F(xiàn)的。

從gc出去其實是一段指令碼，是對這種類型的數(shù)據(jù)進行垃圾回收的指令，Go中用一個狀態(tài)機來執(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語言使用標記清掃的垃圾回收算法，標記位圖是非侵入式的，內(nèi)存布局設計得比較巧妙。并且當前版本的Go實現(xiàn)了精確的垃圾回收。在精確的垃圾回收中，通過定位對象的類型信息，得到該類型中的垃圾回收的指令碼，通過一個狀態(tài)機解釋這段指令碼來執(zhí)行特定類型的垃圾回收工作。

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

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