Go語言 垃圾回收下篇

目前Go中垃圾回收的核心函數(shù)是scanblock，源代碼在文件runtime/mgc0.c中。這個函數(shù)非常難讀，單個函數(shù)寫了足足500多行。上面有兩個大的循環(huán)，外層循環(huán)作用是掃描整個內(nèi)存塊區(qū)域，將類型信息提取出來，得到其中的gc域。內(nèi)層的大循環(huán)是實現(xiàn)一個狀態(tài)機，解析執(zhí)行類型信息中g(shù)c域的指令碼。

先說說上一節(jié)留的疑問吧。MType中的數(shù)據(jù)其實是類型信息，但它是用uintptr表示，而不是Type結(jié)構(gòu)體的指針，這是一個優(yōu)化的小技巧。由于內(nèi)存分配是機器字節(jié)對齊的，所以地址就只用到了高位，低位是用不到的。于是低位可以利用起來存儲一些額外的信息。這里的uintptr中高位存放的是Type結(jié)構(gòu)體的指針，低位用來存放類型。通過

    t = (Type*)(type & ~(uintptr)(PtrSize-1));

就可以從uintptr得到Type結(jié)構(gòu)體指針，而通過

type & (PtrSize-1)

就可以得到類型。這里的類型有TypeInfo_SingleObject，TypeInfo_Array，TypeInfo_Map，TypeInfo_Chan幾種。

基本的標記過程

從最簡單的開始看，基本的標記過程，有一個不帶任何優(yōu)化的標記的實現(xiàn)，對應(yīng)于函數(shù)debug_scanblock。

debug_scanblock函數(shù)是遞歸實現(xiàn)的，單線程的，更簡單更慢的scanblock版本。該函數(shù)接收的參數(shù)分別是一個指針表示要掃描的地址，以及字節(jié)數(shù)。

首先要將傳入的地址，按機器字節(jié)大小對齊。
然后對待掃描區(qū)域的每個地址：
找到它所屬的MSpan，將地址轉(zhuǎn)換為MSpan里的對象地址。
根據(jù)對象的地址，找到對應(yīng)的標記位圖里的標記位。
判斷標記位，如果是未分配則跳過。否則加上特殊位標記(debug_scanblock中用特殊位代碼的mark位)完成標記。
判斷標記位中標記了無指針標記位，如果沒有，則要遞歸地調(diào)用debug_scanblock。

這個遞歸版本的標記算法還是很容易理解的。其中涉及的細節(jié)在上節(jié)中已經(jīng)說過了，比如任意給定一個地址，找到它的標記位信息。很明顯這里僅僅使用了一個無指針位，并沒有精確的垃圾回收。

并行的垃圾回收

Go在這個版本中不僅實現(xiàn)了精確的垃圾回收，而且實現(xiàn)了并行的垃圾回收。標記算法本質(zhì)上就是一個樹的遍歷過程，上面實現(xiàn)的是一個遞歸版本。

并行的垃圾回收需要做的第一步，就是先將算法做成非遞歸的。非遞歸版本的樹的遍歷需要用到一個隊列。樹的非遞歸遍歷的偽代碼大致是：

根結(jié)點進隊
while(隊列不空) {
    出隊
    訪問
    將子結(jié)點進隊
}

第二步是使上面的代碼能夠并行地工作，顯然這時是需要一個線程安全的隊列的。假設(shè)有這樣一個隊列，那么上面代碼就能夠工作了。但是，如果不加任何優(yōu)化，這里的隊列的并行訪問非常地頻繁，對這個隊列加鎖代價會非常高，即使是使用CAS操作也會大大降低效率。

所以，第三步要做的就是優(yōu)化上面隊列的數(shù)據(jù)結(jié)構(gòu)。事實上，Go中并沒有使用這樣一個隊列，為了優(yōu)化，它通過三個數(shù)據(jù)結(jié)構(gòu)共同來完成這個隊列的功能，這三個數(shù)據(jù)結(jié)構(gòu)分別是PtrTarget數(shù)組，Workbuf，lfstack。

先說Workbuf吧。聽名字就知道，這個結(jié)構(gòu)體的意思是工作緩沖區(qū)，里面存放的是一個數(shù)組，數(shù)組中的每個元素都是一個待處理的結(jié)點，也就是一個Obj指針。這個對象本身是已經(jīng)標記了的，這個對象直接或間接引用到的對象，都是應(yīng)該被標記的，它們不會被當作垃圾回收掉。Workbuf是比較大的，一般是N個內(nèi)存頁的大小(目前是2頁，也就是8K)。

PtrTarget數(shù)組也是一個緩沖區(qū)，相當于一個intermediate buffer，跟Workbuf有一點點的區(qū)別。第一，它比Workbuf小很多，大概只有32或64個元素的數(shù)組。第二，Workbuf中的對象全部是已經(jīng)標記過的，而PtrTarget中的元素可能是標記的，也可能是沒標記的。第三，PtrTarget里面的元素是指針而不是對象，指針是指向任意地址的，而對象是對齊到正確地址的。從一個指針變?yōu)橐粋€對象要經(jīng)過一次變換，上一節(jié)中有講過具體細節(jié)。

垃圾回收過程中，會有一個從PtrTarget數(shù)組沖刷到Workbuf緩沖區(qū)的過程。對應(yīng)于源代碼中的flushptrbuf函數(shù)，這個函數(shù)作用就是對PtrTaget數(shù)組中的所有元素，如果該地址是mark了的，則將它移到Workbuf中。標記過程形成了一個環(huán)，在環(huán)的一邊，對Workbuf中的對象，會將它們可能引用的區(qū)域全部放到PtrTarget中記錄下來。在環(huán)的另一邊，又會將PtrTarget中確定需要標記的地址刷到Workbuf中。這個過程一輪一輪地進行，推動非遞歸版本的樹的遍歷過程，也就是前面?zhèn)未a中的出隊，訪問，子結(jié)點進隊的過程。

另一個數(shù)據(jù)結(jié)構(gòu)是lfstack，這個名字的意思是lock free棧。其實它是被用作了一個無鎖的鏈表，鏈表結(jié)點是以Workbuf為單位的。并行垃圾回收中，多條線程會從這個鏈表中取數(shù)據(jù)，每次以一個Workbuf為工作單位。同時，標記的過程中也會產(chǎn)生Workbuf結(jié)點放到鏈中。lfstack保證了對這個鏈的并發(fā)訪問的安全性。由于現(xiàn)在鏈表結(jié)點是以Workbuf為單位的，所以保證整體的性能，lfstack的底層代碼是用CAS操作實現(xiàn)的。

經(jīng)過第三步中數(shù)據(jù)結(jié)構(gòu)上的拆解，整個并行垃圾回收的架構(gòu)已經(jīng)呼之欲出了，這就是標記掃描的核心函數(shù)scanblock。這個函數(shù)是在多線程下并行安全的。

那么，最后一步，多線程并行。整個的gc是以runtime.gc函數(shù)為入口的，它實際調(diào)用的是gc。進入gc函數(shù)后會先stoptheworld，接著添加標記的root區(qū)域。然后會設(shè)置markroot和sweepspan的并行任務(wù)。運行mark的任務(wù)，掃描塊，運行sweep的任務(wù)，最后starttheworld并切換出去。

有一個ParFor的數(shù)據(jù)結(jié)構(gòu)。在gc函數(shù)中調(diào)用了

    runtime·parforsetup(work.markfor, work.nproc, work.nroot, nil, false, markroot);
    runtime·parforsetup(work.sweepfor, work.nproc, runtime·mheap->nspan, nil, true, sweepspan);

是設(shè)置好回調(diào)函數(shù)讓線程去執(zhí)行markroot和sweepspan函數(shù)。垃圾回收時會stoptheworld，其它goroutine會對發(fā)起stoptheworld做出響應(yīng)，調(diào)用runtime.gchelper，這個函數(shù)會調(diào)用scanblock幫助標記過程。也會并行地做markroot和sweepspan的過程。

    void
    runtime·gchelper(void)
    {
        gchelperstart();

        // parallel mark for over gc roots
        runtime·parfordo(work.markfor);

        // help other threads scan secondary blocks
        scanblock(nil, nil, 0, true);

        if(DebugMark) {
            // wait while the main thread executes mark(debug_scanblock)
            while(runtime·atomicload(&work.debugmarkdone) == 0)
                runtime·usleep(10);
        }

        runtime·parfordo(work.sweepfor);
        bufferList[m->helpgc].busy = 0;
        if(runtime·xadd(&work.ndone, +1) == work.nproc-1)
            runtime·notewakeup(&work.alldone);
    }

其中并行時也有實現(xiàn)工作流竊取的概念，多個worker同時去工作緩存中取數(shù)據(jù)出來處理，如果自己的任務(wù)做完了，就會從其它的任務(wù)中“偷”一些過來執(zhí)行。

垃圾回收的時機

垃圾回收的觸發(fā)是由一個gcpercent的變量控制的，當新分配的內(nèi)存占已在使用中的內(nèi)存的比例超過gcprecent時就會觸發(fā)。比如，gcpercent=100，當前使用了4M的內(nèi)存，那么當內(nèi)存分配到達8M時就會再次gc。如果回收完畢后，內(nèi)存的使用量為5M，那么下次回收的時機則是內(nèi)存分配達到10M的時候。也就是說，并不是內(nèi)存分配越多，垃圾回收頻率越高，這個算法使得垃圾回收的頻率比較穩(wěn)定，適合應(yīng)用的場景。

gcpercent的值是通過環(huán)境變量GOGC獲取的，如果不設(shè)置這個環(huán)境變量，默認值是100。如果將它設(shè)置成off，則是關(guān)閉垃圾回收。