Go語言中使用的垃圾回收使用的是標記清掃演算法。進行垃圾回收時會 stoptheworld。不過在Go語言 1.3 版本中，實現了精確的垃圾回收和並行的垃圾回收，大大地提高了垃圾回收的速度，進行垃圾回收時系統並不會長時間卡住。
標記清掃演算法
標記清掃演算法是一個很基礎的垃圾回收演算法，該演算法中有一個標記初始的 root 區域，以及一個受控堆區。root 區域主要是程式執行到當前時刻的棧和全域性資料區域。在受控堆區中，很多資料是程式以後不需要用到的，這類資料就可以被當作垃圾回收了。
判斷一個物件是否為垃圾，就是看從 root 區域的物件是否有直接或間接的參照到這個物件。如果沒有任何物件參照到它，則說明它沒有被使用，因此可以安全地當作垃圾回收掉。
標記清掃演算法分為兩階段，分別是標記階段和清掃階段。
-
標記階段，從 root 區域出發，掃描所有 root 區域的物件直接或間接參照到的物件，將這些對上全部加上標記；
-
清掃階段，掃描整個堆區，對所有無標記的物件進行回收。
點陣圖標記和記憶體布局
既然垃圾回收演算法要求給物件加上垃圾回收的標記，顯然是需要有標記位的。一般的做法會將物件結構體中加上一個標記域，一些優化的做法會利用物件指標的低位進行標記，這都只是些奇技淫巧罷了。Go 沒有這麼做，它的物件和 C 的結構體物件完全一致，使用的是非侵入式的標記位，我們看看它是怎麼實現的。
堆區域對應了一個標記點陣圖區域，堆中每個字（不是 byte，而是 word）都會在標記位區域中有對應的標記位。每個機器字（32 位或 64 位）會對應 4 位的標記位。因此 64 位系統中相當於每個標記點陣圖的位元組對應 16 個堆中的位元組。
雖然是一個堆位元組對應 4 位標記位，但標記點陣圖區域的記憶體布局並不是按 4 位一組，而是 16 個堆位元組為一組，將它們的標記位資訊打包儲存的。每組 64 位的標記點陣圖從上到下依次包括：
-
16 位的特殊位、標記位；
-
16 位的垃圾回收標記位；
-
16 位的無指標 / 塊邊界的標記位；
-
16 位的已分配標記位。
這樣設計使得對一個型別的相應的位進行遍歷很容易。
前面提到堆區域和堆地址的標記點陣圖區域是分開儲存的，其實它們是以 mheap.arena_start 地址為邊界，向上是實際使用的堆地址空間，向下則是標記點陣圖區域。以 64 位系統為例，計算堆中某個地址的標記位的公式如下：
偏移 = 地址 - mheap.arena_start
標記位地址 = mheap.arena_start - 偏移/16 - 1
移位 = 偏移 % 16
標記位 = *標記位地址 >> 移位
然後就可以通過（標記位 & 垃圾回收標記位）、（標記位 & 分配位）等來測試相應的位。其中已分配的標記為 1<<0，無指標/塊邊界是 1<<16，垃圾回收的標記位為 1<<32，特殊位 1<<48。
精確的垃圾回收
像C語言這種不支援垃圾回收的語言，其實還是有些垃圾回收的庫可以使用的。這類庫一般也是用的標記清掃演算法實現的，但是它們都是保守的垃圾回收。之所以叫“保守”是因為它們沒辦法獲取物件型別資訊，因此只能保守地假設地址區間中每個字都是指標。
無法獲取物件的型別資訊會造成什麼問題呢？這裡舉兩個例子來說明。
先看第一個例子，假設某個結構體中是不包含指標成員的，那麼對該結構體成員進行垃圾回收時，其實是不必要遞回地標記結構體的成員的。但是由於沒有型別資訊，我們並不知道這個結構體成員不包含指標，因此我們只能對結構體的每個位元組遞回地標記下去，這顯然會浪費很多時間。這個例子說明精確的垃圾回收可以減少不必要的掃描，提高標記過程的速度。
再看另一個例子，假設堆中有一個 long 的變數，它的值是 8860225560。但是我們不知道它的型別是 long，所以在進行垃圾回收時會把它當作指標處理，這個指標參照到了 0x2101c5018 位置。假設 0x2101c5018 碰巧有某個物件，那麼這個物件就無法被釋放了，即使實際上已經沒任何地方使用它。
這個例子說明，保守的垃圾回收某些情況下會出現垃圾無法被回收的情況。雖然不會造成大的問題，但總是讓人很不爽，都是沒有型別資訊惹的禍。
現在好了，在Go語言的 1.1 版本中開始支援精確的垃圾回收。精確的垃圾回收首先需要的就是型別資訊，上一節中講過 MSpan 結構體，型別資訊是儲存在 MSpan 中的。從一個地址計算它所屬的 MSpan，公式如下：
頁號 = (地址 - mheap.arena_start) >> 頁大小
MSpan = mheap->map[頁號]
接下來通過 MSpan->type 可以得到分配塊的型別。這是一個 MType 的結構體：
struct MTypes
{
byte compression; // one of MTypes_*
bool sysalloc; // whether (void*)data is from runtime·SysAlloc uintptr data;
};
MTypes 描述 MSpan 裡分配的塊的型別，其中 compression 域描述資料的布局。它的取值為 MTypes_Empty、MTypes_Single、MTypes_Words、MTypes_Bytes 四個中的一種：
-
MTypes_Empty：所有的塊都是 free 的，或者這個分配塊的型別資訊不可用。這種情況下 data 域是無意義的。
-
MTypes_Single：這個 MSpan 只包含一個塊，data 域存放型別資訊，sysalloc 域無意義。
-
MTypes_Words：這個 MSpan 包含多個塊（塊的種類多於 7）。這時 data 指向一個陣列 [NumBlocks]uintptr，陣列裡每個元索存放相應塊的型別資訊。
-
MTypes_Bytes：這個 MSpan 中包含最多 7 種不同型別的塊。這時 data 域指下面這個結構體
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 只不過為了做優化而顯得很複雜。
上一節中說過，每一塊 MSpan 中存放的塊的大小都是一樣的，不過它們的型別不一定相同。如果沒有使用，那麼這個 MSpan 的型別就是 MTypes_Empty。如果存一個很大塊，大於這個 MSpan 大小的一半，因此存不了其它東西了，那麼這個 MSpan 的型別是 MTypes_Single。
假設存了多種塊，每一塊用一個指標，本來可以直接用 MTypes_Words 存的。但是當型別不多時，可以把這些型別的指標集中起來放在陣列中，然後儲存陣列索引。這是一個小的優化，可以節省記憶體空間。
得到的型別資訊最終是什麼樣子的呢？其實是一個這樣的結構體：
struct Type
{
uintptr size;
uint32 hash;
uint8 _unused;
uint8 align;
uint8 fieldAlign;
uint8 kind;
Alg *alg;
void *gc;
String *string;
UncommonType *x;
Type *ptrto;
};
不同型別的型別資訊結構體略有不同，這個是通用的部分。可以看到這個結構體中有一個 gc 域，精確的垃圾回收就是利用型別資訊中這個 gc 域實現的。
從 gc 出去其實是一段指令碼，是對這種型別的資料進行垃圾回收的指令，Go語言中用一個狀態機來執行垃圾回收指令碼。大致的框架是類似下面這樣子：
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;
}
}
Go語言使用標記清掃的垃圾回收演算法，標記點陣圖是非侵入式的，記憶體布局設計得比較巧妙。並且當前版本的Go語言實現了精確的垃圾回收。在精確的垃圾回收中，通過定位物件的型別資訊，得到該型別中的垃圾回收的指令碼，通過一個狀態機解釋這段指令碼來執行特定型別的垃圾回收工作。
對於堆中任意地址的物件，找到它的型別資訊過程為，先通過它在的記憶體頁找到它所屬的 MSpan，然後通過 MSpan 中的型別資訊找到它的型別資訊。
目前Go語言中垃圾回收的核心函數是 scanblock，原始碼在檔案 runtime/mgc0.c 中。這個函數非常難讀，單個函數寫了足足 500 多行。
上面有兩個大的迴圈，外層迴圈作用是掃描整個記憶體塊區域，將型別資訊提取出來，得到其中的 gc 域。內層的大迴圈是實現一個狀態機，解析執行型別資訊中 gc 域的指令碼。
MType 中的資料其實是型別資訊，但它是用 uintptr 表示，而不是 Type 結構體的指標，這是一個優化的小技巧。由於記憶體分配是機器位元組對齊的，所以地址就只用到了高位，低位是用不到的。
於是低位可以利用起來儲存一些額外的資訊。這裡的 uintptr 中高位存放的是 Type 結構體的指標，低位用來存放型別。通過下面的程式碼：
t = (Type*)(type & ~(uintptr)(PtrSize-1));
就可以從 uintptr 得到 Type 結構體指標，而通過下面的程式碼：
type & (PtrSize-1)
就可以得到型別。這裡的型別有 TypeInfo_SingleObject、TypeInfo_Array、TypeInfo_Map、TypeInfo_Chan 幾種。
基本的標記過程
從最簡單的開始看，基本的標記過程，有一個不帶任何優化的標記的實現，對應於函數 debug_scanblock。
debug_scanblock 函數是遞迴實現的，單執行緒的，更簡單更慢的 scanblock 版本。該函數接收的引數分別是一個指標表示要掃描的地址，以及位元組數。
首先要將傳入的地址，按機器位元組大小對齊。然後對待掃描區域的每個地址：
-
找到它所屬的 MSpan，將地址轉換為 MSpan 裡的物件地址。
-
根據物件的地址，找到對應的標記點陣圖裡的標記位。
-
判斷標記位，如果是未分配則跳過。否則加上特殊位標記（debug_scanblock 中用特殊位程式碼的 mark 位）完成標記。
-
判斷標記位中標記了無指標標記位，如果沒有，則要遞回地呼叫 debug_scanblock。
這個遞迴版本的標記演算法還是很容易理解的。其中涉及的細節在上節中已經說過了，比如任意給定一個地址，找到它的標記位資訊。很明顯這裡僅僅使用了一個無指標位，並沒有精確的垃圾回收。
並行的垃圾回收
Go語言在這個版本中不僅實現了精確的垃圾回收，而且實現了並行的垃圾回收。標記演算法本質上就是一個樹的遍歷過程，上面實現的是一個遞迴版本。
並行的垃圾回收需要做的第一步，就是先將演算法做成非遞回的。非遞回版本的樹的遍歷需要用到一個佇列。樹的非遞回遍歷的虛擬碼大致是：
根結點進隊
while(佇列不空){
出隊
存取
將子結點進隊
}
第二步是使上面的程式碼能夠並行地工作，顯然這時是需要一個執行緒安全的佇列的。假設有這樣一個佇列，那麼上面程式碼就能夠工作了。但是，如果不加任何優化，這裡的佇列的併行存取非常地頻繁，對這個佇列加鎖代價會非常高，即使是使用 CAS 操作也會大大降低效率。
所以，第三步要做的就是優化上面佇列的資料結構。事實上，Go中並沒有使用這樣一個佇列，為了優化，它通過三個資料結構共同來完成這個佇列的功能，這三個資料結構分別是 PtrTarget 陣列，Workbuf，lfstack。
先說 Workbuf 吧。聽名字就知道，這個結構體的意思是工作緩衝區，裡面存放的是一個陣列，陣列中的每個元素都是一個待處理的結點，也就是一個 Obj 指標。這個物件本身是已經標記了的，這個物件直接或間接參照到的物件，都是應該被標記的，它們不會被當作垃圾回收掉。Workbuf 是比較大的，一般是 N 個記憶體頁的大小(目前是 2 頁，也就是 8K)。
PtrTarget 陣列也是一個緩衝區，相當於一個 intermediate buffer，跟 Workbuf 有一點點的區別。
-
第一，它比 Workbuf 小很多，大概只有 32 或 64 個元素的陣列。
-
第二，Workbuf 中的物件全部是已經標記過的，而 PtrTarget 中的元素可能是標記的，也可能是沒標記的。
-
第三，PtrTarget 裡面的元素是指標而不是物件，指標是指向任意地址的，而物件是對齊到正確地址的。從一個指標變為一個物件要經過一次變換，上一節中有講過具體細節。
垃圾回收過程中，會有一個從 PtrTarget 陣列沖刷到 Workbuf 緩衝區的過程。對應於原始碼中的 flushptrbuf 函數，這個函數作用就是對 PtrTaget 陣列中的所有元素，如果該地址是 mark 了的，則將它移到 Workbuf 中。
標記過程形成了一個環，在環的一邊，對 Workbuf 中的物件，會將它們可能參照的區域全部放到 PtrTarget 中記錄下來。在環的另一邊，又會將 PtrTarget 中確定需要標記的地址刷到 Workbuf 中。這個過程一輪一輪地進行，推動非遞回版本的樹的遍歷過程，也就是前面虛擬碼中的出隊，存取，子結點進隊的過程。
另一個資料結構是 lfstack，這個名字的意思是 lock free 棧。其實它是被用作了一個無鎖的連結串列，連結串列結點是以 Workbuf 為單位的。並行垃圾回收中，多條執行緒會從這個連結串列中取資料，每次以一個 Workbuf 為工作單位。
同時，標記的過程中也會產生 Workbuf 結點放到鏈中。lfstack 保證了對這個鏈的並行存取的安全性。由於現在連結串列結點是以 Workbuf 為單位的，所以保證整體的效能，lfstack 的底層程式碼是用 CAS 操作實現的。
經過第三步中資料結構上的拆解，整個並行垃圾回收的架構已經呼之欲出了，這就是標記掃描的核心函數 scanblock。這個函數是在多執行緒下並行安全的。
那麼，最後一步，多執行緒並行。整個的 gc 是以 runtime.gc 函數為入口的，它實際呼叫的是 gc。進入 gc 函數後會先 stoptheworld，接著新增標記的 root 區域。然後會設定 markroot 和 sweepspan 的並行任務。執行 mark 的任務，掃描塊，執行 sweep 的任務，最後 starttheworld 並切換出去。
有一個 ParFor 的資料結構。在 gc 函數中呼叫了
runtime·parforsetup(work.markfor, work.nproc, work.nroot, nil, false, markroot);
runtime·parforsetup(work.sweepfor, work.nproc, runtime·mheap->nspan, nil, true, sweepspan);
是設定好回撥函數讓執行緒去執行 markroot 和 sweepspan 函數。垃圾回收時會 stoptheworld，其它 goroutine 會對發起 stoptheworld 做出響應，呼叫 runtime.gchelper，這個函數會呼叫 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);
}
其中並行時也有實現工作流竊取的概念，多個 worker 同時去工作快取中取資料出來處理，如果自己的任務做完了，就會從其它的任務中“偷”一些過來執行。
垃圾回收的時機
垃圾回收的觸發是由一個 gcpercent 的變數控制的，當新分配的記憶體占已在使用中的記憶體的比例超過 gcprecent 時就會觸發。
比如 gcpercent=100，當前使用了 4M 的記憶體，那麼當記憶體分配到達 8M 時就會再次 gc。如果回收完畢後，記憶體的使用量為 5M，那麼下次回收的時機則是記憶體分配達到 10M 的時候。也就是說，並不是記憶體分配越多，垃圾回收頻率越高，這個演算法使得垃圾回收的頻率比較穩定，適合應用的場景。
gcpercent 的值是通過環境變數 GOGC 獲取的，如果不設定這個環境變數，預設值是 100。如果將它設定成 off，則是關閉垃圾回收。