CoreCLR源码探索(四) GC内存收集器的内部实现 分析篇
在這篇中我將講述GC Collector內部的實現, 這是CoreCLR中除了JIT以外最復雜部分，下面一些概念目前尚未有公開的文檔和書籍講到。
為了分析這部分我花了一個多月的時間，期間也多次向CoreCLR的開發組提問過，我有信心以下內容都是比較準確的，但如果你發現了錯誤或者有疑問的地方請指出來，
以下的內容基于CoreCLR 1.1.0的源代碼分析，以后可能會有所改變。
因為內容過長，我分成了兩篇，這一篇分析代碼，下一篇實際使用LLDB跟蹤GC收集垃圾的處理。
需要的預備知識
看過BOTR中GC設計的文檔 原文 譯文
看過我之前的系列文章, 碰到不明白的可以先跳過但最少需要看一遍
CoreCLR源碼探索(一) Object是什么
CoreCLR源碼探索(二) new是什么
CoreCLR源碼探索(三) GC內存分配器的內部實現
對c中的指針有一定了解
對常用數據結構有一定了解, 例如鏈表
對基礎c++語法有一定了解, 高級語法和STL不需要因為微軟只用了低級語法
GC的觸發
GC一般在已預留的內存不夠用或者已經分配量超過閾值時觸發，場景包括:
不能給分配上下文指定新的空間時
當調用try_allocate_more_space不能從segment結尾或自由對象列表獲取新的空間時會觸發GC, 詳細可以看我上一篇中分析的代碼。
分配的數據量達到一定閾值時
閾值儲存在各個heap的dd_min_gc_size(初始值), dd_desired_allocation(動態調整值), dd_new_allocation(消耗值)中，每次給分配上下文指定空間時會減少dd_new_allocation。
如果dd_new_allocation變為負數或者與dd_desired_allocation的比例小于一定值則觸發GC,
觸發完GC以后會重新調整dd_new_allocation到dd_desired_allocation。
參考new_allocation_limit, new_allocation_allowed和check_for_full_gc函數。
值得一提的是可以在.Net程序中使用GC.RegisterForFullGCNotification可以設置觸發GC需要的dd_new_allocation / dd_desired_allocation的比例(會儲存在fgn_maxgen_percent和fgn_loh_percent中), 設置一個大于0的比例可以讓GC觸發的更加頻繁。
StressGC
允許手動設置特殊的GC觸發策略, 參考這個文檔
作為例子，你可以試著在運行程序前運行export COMPlus_GCStress=1
GCStrees會通過調用GCStress<gc_on_alloc>::MaybeTrigger(acontext)觸發，
如果你設置了COMPlus_GCStressStart環境變量，在調用MaybeTrigger一定次數后會強制觸發GC，另外還有COMPlus_GCStressStartAtJit等參數，請參考上面的文檔。
默認StressGC不會啟用。
手動觸發GC
在.Net程序中使用GC.Collect可以觸發手動觸發GC，我相信你們都知道。
調用.Net中的GC.Collect會調用CoreCLR中的GCHeap::GarbageCollect => GarbageCollectTry => GarbageCollectGeneration。
GC的處理
以下函數大部分都在gc.cpp里，在這個文件里的函數我就不一一標出文件了。
GC的入口點
GC的入口點是GCHeap::GarbageCollectGeneration函數，這個函數的主要作用是停止運行引擎和調用各個gc_heap的gc_heap::garbage_collect函數
因為這一篇重點在于GC做出的處理，我將不對如何停止運行引擎和后臺GC做出詳細的解釋，希望以后可以再寫一篇文章講述
以下是gc_heap::garbage_collect函數，這個函數也是GC的入口點函數，
主要作用是針對gc_heap做gc開始前和結束后的清理工作，例如重設各個線程的分配上下文和修改gc參數
GC的主函數
GC的主函數是gc1，包含了GC中最關鍵的處理，也是這一篇中需要重點講解的部分。
gc1中的總體流程在BOTR文檔已經有初步的介紹:
首先是mark phase，標記存活的對象
然后是plan phase，決定要壓縮還是要清掃
如果要壓縮則進入relocate phase和compact phase
如果要清掃則進入sweep phase
在看具體的代碼之前讓我們一起復習之前講到的Object的結構
GC使用其中的2個bit來保存標記(marked)和固定(pinned)
標記(marked)表示對象是存活的，不應該被收集，儲存在MethodTable指針 & 1中
固定(pinned)表示對象不能被移動(壓縮時不要移動這個對象), 儲存在對象頭 & 0x20000000中
這兩個bit會在mark_phase中被標記，在plan_phase中被清除，不會殘留到GC結束后
再復習堆段(heap segment)的結構
一個gc_heap中有兩個segment鏈表，一個是小對象(gen 0~gen 2)用的鏈表，一個是大對象(gen 3)用的鏈表，
其中鏈表的最后一個節點是ephemeral heap segment，只用來保存gen 0和gen 1的對象，各個代都有一個開始地址，在開始地址之后的對象屬于這個代或更年輕的代。
接下來我們將分別分析GC中的五個階段(mark_phase, plan_phase, relocate_phase, compact_phase, sweep_phase)的內部處理
標記階段(mark_phase)
這個階段的作用是找出收集垃圾的范圍(gc_low ~ gc_high)中有哪些對象是存活的，如果存活則標記(m_pMethTab |= 1)，
另外還會根據GC Handle查找有哪些對象是固定的(pinned)，如果對象固定則標記(m_uSyncBlockValue |= 0x20000000)。
簡單解釋下GC Handle和Pinned Object，GC Handle用于在托管代碼中調用非托管代碼時可以決定傳遞的指針的處理，
一個類型是Pinned的GC Handle可以防止GC在壓縮時移動對象，這樣非托管代碼中保存的指針地址不會失效，詳細可以看微軟的文檔。
在繼續看代碼之前我們先來了解Card Table的概念:
Card Table
如果你之前已經了解過GC，可能知道有的語言實現GC會有一個根對象，從根對象一直掃描下去可以找到所有存活的對象。
但這樣有一個缺陷，如果對象很多，掃描的時間也會相應的變長，為了提高效率，CoreCLR使用了分代GC(包括之前的.Net Framework都是分代GC)，
分代GC可以只選擇掃描一部分的對象(年輕的對象更有可能被回收)而不是全部對象，那么分代GC的掃描是如何實現的？
在CoreCLR中對象之間的引用(例如B是A的成員或者B在數組A中，可以稱作A引用B)一般包含以下情況
各個線程棧(stack)和寄存器(register)中的對象引用堆段(heap segment)中的對象?
CoreCLR有辦法可以檢測到Managed Thread中在棧和寄存器中的對象
這些對象是根對象(GC Root)的一種
GC Handle表中的句柄引用堆段(heap segment)中的對象?
這些對象也是根對象的一種
析構隊列中的對象引用堆段(heap segment)中的對象?
這些對象也是根對象的一種
同代對象之間的引用
隔代對象之間的引用
請考慮下圖的情況，我們這次只想掃描gen 0，棧中的對象A引用了gen 1的對象B，對象B引用了gen 0的對象C，
在掃描的時候因為B不在掃描范圍(gc_low ~ gc_high)中，CoreCLR不會去繼續跟蹤B的引用，
如果這時候gen 0中無其他對象引用對象C，是否會導致對象C被誤回收？
為了解決這種情況導致的問題，CoreCLR使用了Card Table，所謂Card Table就是專門記錄跨代引用的一個數組
當我們設置B.member = C的時候，JIT會把賦值替換為JIT_WriteBarrier(&B.member, C)(或同等的其他函數)
JIT_WriteBarrier函數中會設置*dst = ref，并且如果ref在ephemeral heap segment中(ref可能是gen 0或gen 1的對象)時，
設置dst在Card Table中所屬的字節為0xff，Card Table中一個字節默認涵蓋的范圍在32位下是1024字節，在64位下是2048字節。
需要注意的是這里的dst是B.member的地址而不是B的地址，B.member的地址會是B的地址加一定的偏移值，
而B自身的地址不一定會在Card Table中得到標記，我們之后可以根據B.member的地址得到B的地址(可以看find_first_object函數)。
有了Card Table以后，只回收年輕代(非Full GC)時除了掃描根對象以外我們還需要掃描Card Table中標記的范圍來防止誤回收對象。
接下來我們看下GCHeap::Promote函數，在plan_phase中掃描到的對象都會調用這個函數進行標記，
這個函數名稱雖然叫Promote但是里面只負責對對象進行標記，被標記的對象不一定會升代
經過標記階段以后，在堆中存活的對象都被設置了marked標記，如果對象是固定的還會被設置pinned標記
接下來是計劃階段plan_phase:
計劃階段(plan_phase)
在這個階段首先會模擬壓縮和構建Brick Table，在模擬完成后判斷是否應該進行實際的壓縮，
如果進行實際的壓縮則進入重定位階段(relocate_phase)和壓縮階段(compact_phase)，否則進入清掃階段(sweep_phase)，
在繼續看代碼之前我們需要先了解計劃階段如何模擬壓縮和什么是Brick Table。
計劃階段如何模擬壓縮
計劃階段首先會根據相鄰的已標記的對象創建plug，用于加快處理速度和減少需要的內存空間，我們假定一段內存中的對象如下圖
計劃階段會為這一段對象創建2個unpinned plug和一個pinned plug:
第一個plug是unpinned plug，包含了對象B, C，不固定地址
第二個plug是pinned plug，包含了對象E, F, G，固定地址
第三個plug是unpinned plug，包含了對象H，不固定地址
各個plug的信息保存在開始地址之前的一段內存中，結構如下
struct plug_and_gap
{
? ? // 在這個plug之前有多少空間是未被標記(可回收)的
? ? ptrdiff_t ? gap;
? ? // 壓縮這個plug中的對象時需要移動的偏移值，一般是負數
? ? ptrdiff_t ? reloc;
? ? union
? ? {
? ? ? ? // 左邊節點和右邊節點
? ? ? ? pair ? ?m_pair;
? ? ? ? int ? ? lr; ?//for clearing the entire pair in one instruction
? ? };
? ? // 填充對象(防止覆蓋同步索引塊)
? ? plug ? ? ? ?m_plug;
};
眼尖的會發現上面的圖有兩個問題
對象G不是pinned但是也被歸到pinned plug里了?
這是因為pinned plug會把下一個對象也拉進來防止pinned object的末尾被覆蓋，具體請看下面的代碼
第三個plug把對象G的結尾給覆蓋(破壞)了?
對于這種情況原來的內容會備份到saved_post_plug中，具體請看下面的代碼
多個plug會構建成一棵樹，例如上面的三個plug會構建成這樣的樹:
第一個plug: { gap: 24, reloc: 未定義, m_pair: { left: 0, right: 0 } }
第二個plug: { gap: 132, reloc: 0, m_pair: { left: -356, right: 206 } }
第三個plug: { gap: 24, reloc: 未定義, m_pair: { left: 0, right 0 } }
第二個plug的left和right保存的是離子節點plug的偏移值，
第三個plug的gap比較特殊，可能你們會覺得應該是0但是會被設置為24(sizeof(gap_reloc_pair))，這個大小在實際復制第二個plug(compact_plug)的時候會加回來。
當計劃階段找到一個plug的開始時，
如果這個plug是pinned plug則加到mark_stack_array隊列中。
當計劃階段找到一個plug的結尾時，
如果這個plug是pinned plug則設置這個plug的大小并移動隊列頂部(mark_stack_tos)，
否則使用使用函數allocate_in_condemned_generations計算把這個plug移動到前面(壓縮)時的偏移值，
allocate_in_condemned_generations的原理請看下圖
函數allocate_in_condemned_generations不會實際的移動內存和修改指針，它只設置了plug的reloc成員，
這里需要注意的是如果有pinned plug并且前面的空間不夠，會從pinned plug的結尾開始計算，
同時出隊列以后的plug B在mark_stack_array中的len會被設置為前面一段空間的大小，也就是32+39=71。
現在讓我們思考一個問題，如果我們遇到一個對象x，如何求出對象x應該移動到的位置？
我們需要根據對象x找到它所在的plug，然后根據這個plug的reloc移動，查找plug使用的索引就是接下來要說的Brick Table。
Brick Table
brick_table是一個類型為short*的數組，用于快速索引plug，如圖
根據所屬的brick不同，會構建多個plug樹(避免plug樹過大)，然后設置根節點的信息到brick_table中，
brick中的值如果是正值則表示brick對應的開始地址離根節點plug的偏移值+1，
如果是負值則表示plug樹橫跨了多個brick，需要到前面的brick查找。
brick_table相關的代碼如下，我們可以看到在64位下brick的大小是4096，在32位下brick的大小是2048
brick_table中出現負值的情況是因為plug橫跨幅度比較大，超過了單個brick的時候后面的brick就會設為負值，
如果對象地址在上圖的1001或1002，查找這個對象對應的plug會從1000的plug樹開始。
另外1002中的值不一定需要是-2，-1也是有效的，如果是-1會一直向前查找直到找到正值的brick。
在上面我們提到的問題可以通過brick_table解決，可以看下面relocate_address函數的代碼。
brick_table在gc過程中會儲存plug樹，但是在gc完成后(gc不執行時)會儲存各個brick中地址最大的plug，用于給find_first_object等函數定位對象的開始地址使用。
對于Pinned Plug的特殊處理
pinned plug除了會在plug樹和brick table中，還會保存在mark_stack_array隊列中，類型是mark。
因為unpinned plug和pinned plug相鄰會導致原來的內容被plug信息覆蓋，mark中還會保存以下的特殊信息
saved_pre_plug?
如果這個pinned plug覆蓋了上一個unpinned plug的結尾，這里會保存覆蓋前的原始內容
saved_pre_plug_reloc?
同上，但是這個值用于重定位和壓縮階段（中間會交換）
saved_post_plug?
如果這個pinned plug被下一個unpinned plug覆蓋了結尾，這里會保存覆蓋前的原始內容
saved_post_plug_reloc?
同上，但是這個值用于重定位和壓縮階段（中間會交換）
saved_pre_plug_info_reloc_start?
被覆蓋的saved_pre_plug內容在重定位后的地址，如果重定位未發生則可以直接用(first - sizeof (plug_and_gap))
saved_post_plug_info_start?
被覆蓋的saved_post_plug內容的地址，注意pinned plug不會被重定位
saved_pre_p?
是否保存了saved_pre_plug
如果覆蓋的內容包含了對象的開頭(對象比較小，整個都被覆蓋了)
這里還會保存對象離各個引用成員的偏移值的bitmap (enque_pinned_plug)
saved_post_p?
是否保存了saved_post_p
如果覆蓋的內容包含了對象的開頭(對象比較小，整個都被覆蓋了)
這里還會保存對象離各個引用成員的偏移值的bitmap (save_post_plug_info)
mark_stack_array中的len意義會在入隊和出隊時有所改變，
入隊時len代表pinned plug的大小，
出隊后len代表pinned plug離最后的模擬壓縮分配地址的空間(這個空間可以變成free object)。
mark_stack_array
mark_stack_array的結構如下圖:
入隊時mark_stack_tos增加，出隊時mark_stack_bos增加，空間不夠時會擴展然后mark_stack_array_length會增加。
計劃階段判斷使用壓縮(compact)還是清掃(sweep)的依據是什么
計劃階段模擬壓縮的時候創建plug，設置reloc等等只是為了接下來的壓縮做準備，既不會修改指針地址也不會移動內存。
在做完這些工作之后計劃階段會首先判斷應不應該進行壓縮，如果不進行壓縮而是進行清掃，這些計算結果都會浪費掉。
判斷是否使用壓縮的根據主要有
系統空余空閑是否過少，如果過少觸發swap可能會明顯的拖低性能，這時候應該嘗試壓縮
碎片空間大小(fragmentation) >= 閾值(dd_fragmentation_limit)
碎片空間大小(fragmentation) / 收集代的大小(包括更年輕的代) >= 閾值(dd_fragmentation_burden_limit)
其他還有一些零碎的判斷，將在下面的decide_on_compacting函數的代碼中講解。
對象的升代與降代
在很多介紹.Net GC的書籍中都有提到過，經過GC以后對象會升代，例如gen 0中的對象在一次GC后如果存活下來會變為gen 1。
在CoreCLR中，對象的升代需要滿足一定條件，某些特殊情況下不會升代，甚至會降代(gen1變為gen0)。
對象升代的條件如下:
計劃階段(plan_phase)選擇清掃(sweep)時會啟用升代
入口點(garbage_collect)判斷當前是Full GC時會啟用升代
dt_low_card_table_efficiency_p成立時會啟用升代?
請在前面查找dt_low_card_table_efficiency_p查看該處的解釋
計劃階段(plan_phase)判斷上一代過小，或者這次標記(存活)的對象過多時啟用升代?
請在后面查找promoted_bytes (i) > m查看該處的解釋
如果升代的條件不滿足，則原來在gen 0的對象GC后仍然會在gen 0，
某些特殊條件下還會發生降代，如下圖:
在模擬壓縮時，原來在gen 1的對象會歸到gen 2(pinned object不一定)，原來在gen 0的對象會歸到gen 1，
但是如果所有unpinned plug都已經壓縮到前面，后面還有殘留的pinned plug時，后面殘留的pinned plug中的對象則會不升代或者降代，
當這種情況發生時計劃階段會設置demotion_low來標記被降代的范圍。
如果最終選擇了清掃(sweep)則上圖中的情況不會發生。
計劃代邊界
計劃階段在模擬壓縮的時候還會計劃代邊界(generation::plan_allocation_start)，
計劃代邊界的工作主要在process_ephemeral_boundaries, plan_generation_start, plan_generation_starts函數中完成。
大部分情況下函數process_ephemeral_boundaries會用來計劃gen 1的邊界，如果不升代這個函數還會計劃gen 0的邊界，
當判斷當前計劃的plug大于或等于下一代的邊界時，例如大于等于gen 0的邊界時則會設置gen 1的邊界在這個plug的前面。
最終選擇壓縮(compact)時，會把新的代邊界設置成計劃代邊界(請看fix_generation_bounds函數)，
最終選擇清掃(sweep)時，計劃代邊界不會被使用(請看make_free_lists函數和make_free_list_in_brick函數)。
計劃階段(plan_phase)的代碼
gc_heap::plan_phase函數的代碼如下
計劃階段在模擬壓縮和判斷后會在內部包含重定位階段(relocate_phase)，壓縮階段(compact_phase)和清掃階段(sweep_phase)的處理，
接下來我們仔細分析一下這三個階段做了什么事情:
重定位階段(relocate_phase)
重定位階段的主要工作是修改對象的指針地址，例如A.Member的Member內存移動后，A中指向Member的指針地址也需要改變。
重定位階段只會修改指針地址，復制內存會交給下面的壓縮階段(compact_phase)完成。
如下圖:
圖中對象A和對象B引用了對象C，重定位后各個對象還在原來的位置，只是成員的地址(指針)變化了。
還記得之前標記階段(mark_phase)使用的GcScanRoots等掃描函數嗎？
這些掃描函數同樣會在重定位階段使用，只是執行的不是GCHeap::Promote而是GCHeap::Relocate。
重定位對象會借助計劃階段(plan_phase)構建的brick table和plug樹來進行快速的定位，然后對指針地址移動所屬plug的reloc位置。
重定位階段(relocate_phase)的代碼
重定位階段(relocate_phase)只是修改了引用對象的地址，對象還在原來的位置，接下來進入壓縮階段(compact_phase):
壓縮階段(compact_phase)
壓縮階段負責把對象復制到之前模擬壓縮到的地址上，簡單點來講就是用memcpy復制這些對象到新的地址。
壓縮階段會使用之前構建的brick table和plug樹快速的枚舉對象。
gc_heap::compact_phase函數的代碼如下:
這個函數的代碼是不是有點眼熟？它的流程和上面的relocate_survivors很像，都是枚舉brick table然后中序枚舉plug樹
壓縮階段結束以后還需要做一些收尾工作，請從上面plan_phase中的recover_saved_pinned_info();繼續看。
參考鏈接
https://github.com/dotnet/coreclr/blob/master/Documentation/botr/garbage-collection.md
https://raw.githubusercontent.com/dotnet/coreclr/release/1.1.0/src/gc/gc.cpp
https://github.com/dotnet/coreclr/blob/release/1.1.0/src/gc/gcimpl.h
https://github.com/dotnet/coreclr/blob/release/1.1.0/src/gc/gcpriv.h
https://github.com/dotnet/coreclr/issues/8959
https://github.com/dotnet/coreclr/issues/8995
https://github.com/dotnet/coreclr/issues/9053
https://github.com/dotnet/coreclr/issues/10137
https://github.com/dotnet/coreclr/issues/10305
https://github.com/dotnet/coreclr/issues/10141
寫在最后
GC的實際處理遠遠比文檔和書中寫的要復雜，希望這一篇文章可以讓你更加深入的理解CoreCLR，如果你發現了錯誤或者有疑問的地方請指出來，
另外這篇文章有一些部分尚未涵蓋到，例如SuspendEE的原理，后臺GC的處理和stackwalking等，希望以后可以再花時間去研究它們。
下一篇我將會實際使用LLDB跟蹤GC收集垃圾的處理，再下一篇會寫JIT相關的內容，敬請期待
相關的代碼太多，請閱讀原文。
相關文章：
《代碼的未來》讀書筆記：內存管理與GC那點事兒
CoreCLR源碼探索(一) Object是什么
CoreCLR源碼探索(二) new是什么
CoreCLR源碼探索(三) GC內存分配器的內部實現
.NET跨平臺之旅：corehost 是如何加載 coreclr 的
.NET CoreCLR開發人員指南(上)
原文地址：http://www.cnblogs.com/zkweb/p/6625049.html
.NET社區新聞，深度好文，微信中搜索dotNET跨平臺或掃描二維碼關注
總結
以上是生活随笔為你收集整理的CoreCLR源码探索(四) GC内存收集器的内部实现 分析篇的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： CoreCLR文档翻译 - GC的设计
- 下一篇： CoreCLR源码探索(五) GC内存收