Go語(yǔ)言 垃圾回收下篇

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

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

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

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

type & (PtrSize-1)

就可以得到類(lèi)型。這里的類(lèi)型有TypeInfo_SingleObject，TypeInfo_Array，TypeInfo_Map，TypeInfo_Chan幾種。

基本的標(biāo)記過(guò)程

從最簡(jiǎn)單的開(kāi)始看，基本的標(biāo)記過(guò)程，有一個(gè)不帶任何優(yōu)化的標(biāo)記的實(shí)現(xiàn)，對(duì)應(yīng)于函數(shù)debug_scanblock。

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

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

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

并行的垃圾回收

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

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

根結(jié)點(diǎn)進(jìn)隊(duì)
while(隊(duì)列不空) {
    出隊(duì)
    訪問(wèn)
    將子結(jié)點(diǎn)進(jìn)隊(duì)
}

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

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

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

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

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

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

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

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

有一個(gè)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ù)。垃圾回收時(shí)會(huì)stoptheworld，其它goroutine會(huì)對(duì)發(fā)起stoptheworld做出響應(yīng)，調(diào)用runtime.gchelper，這個(gè)函數(shù)會(huì)調(diào)用scanblock幫助標(biāo)記過(guò)程。也會(huì)并行地做markroot和sweepspan的過(guò)程。

    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);
    }

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

垃圾回收的時(shí)機(jī)

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

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