CLR探索系列-GC Heap架構及其實現（垃圾回收系列）

在CLR探索系列的研究DotNet下的垃圾回收器這幾個博文裡，就先說說GC Heap結構吧，至於垃圾回收的詳析算法實現，以後再寫了。在一個托管進程被創建以後，在托管進程的內存空間裡面，包含了System Domain，Shared Domain，Default Domain，以及一系列的Heap，有Process的Heap，JIT Code Heap，GC Heap以及LOH。在DotNet的CLR的實現中，GC heap和LOH（Large Object Heap）是包含在一個類裡面實現的。這就造成了在內存中，一個GC Heap後面緊跟著的就是LOH Heap。在實現的時候，一個gc_heap類裡面包含了一個GC的結構類，以及一個LOH。

一個GC Heap的結構大致如下：

上面是一個GC Heap的大致結構。從上面到下面是從低地址到高地址。有的時候，需要找一個需要的存在了很久的Object的時候，並不是往高地址去尋找，也有可能存在於低地址區域，這個和每個Generation的大小的動態改變有關。

說到這裡，就會提到一個非常有趣的概念，“策略”。這個是GC開發小組的開發人員在研究呢很久性能和用戶的操作以及內存管理之間的平衡只會整出來的一個比較有趣的概念。在垃圾回收的過程中加入了“策略”。譬如一個Generation 0代占有256KB的內存大小，如果在實際的程序的運行過程中發現新對象的創建特別頻繁，那麼GC EE就會自動增加這個Generation 0的大小。

在說明一個GC Heap的結構的時候，先用windbg+sos來看看一個用戶態運行的程序的GC Heap裡面都有些啥：

0:003> !eeheap=======================================
Number of GC Heaps: 1
generation 0 starts at 0x00ca1018
generation 1 starts at 0x00ca
100c
generation 2 starts at 0x00ca1000
ephemeral segment allocation context: none
segment　　begin allocated　　 size00161e00 790d5588
790f
4b38 0x
0001f
5b0(128432)
00ca0000 00ca1000　00ca3ff4 0x00002ff4(12276)
Large object heap starts at 0x01ca1000segment　　begin allocated　　 size
01ca0000 01ca1000　01ca3250 0x00002250(8784)
Total Size　 0x
247f
4(149492)
------------------------------
GC Heap Size　 0x
247f
4(149492)
=======================================

可以看到，在上面顯示的GC Heap的結構中，一個GC Heap裡面有兩個Heap Segment，緊接著Heap Segment的，是LOH。

在上面的一個GC Heap中，分成三個Generation，最年輕的Object在G 0中。這些Generation是保存在一個一個的Heap Segment裡面的。一個Heap Segment可以包含兩個Generation或者三個，或者更多。而一個Generation可以跨越多個Heap Segment。一個GC Heap主要有一個或者是多個Heap Segment組成。然後在GC Heap的最後還有一個保留區域，用來保存一些比較特別的Object。譬如有一種類型的Object叫做pinned Object。當某個Object存在於Generation 0的內存區域中的時候，如果有其它的外部指針指向了它，再進行一次局部的垃圾回收的時候，這個Object就是不能被移走的，這樣的對象就叫做pinned Object。但是，為了保證垃圾回收器的效率和性能，最年輕的Generation在每次垃圾回收的時候就會被refresh一次，清空所有的對象。先前存在的對象要麼被移動到更老的Generation中去，而象這種pinned Object，就會被移動到GC Heap保留的內存區域裡面去。一個Heap Segment中可以包含一個或者多個Generation，這個是可以動態擴展的。緊接著GC Heap的內存區域，就是Large Object Heap。在默認情況下，超過85000byte的對象就被保存到這裡。因為在LOH裡面的對象清理一次對系統資源的消耗比較大，在存儲大對象的時候，就會首先根據一個Object的MetaTable，掃描一遍來判斷這個對象有沒有對別的對象的引用。如果有的話，這一類對象就會存儲在一起，而沒有對其它對象引用的對象就會存在其余的另外一個區域。這樣做的好處，主要體現在性能的優化上面。在進行垃圾清理的時候，確定一個Object是否是live Object，LOH的這種布局方式可以減少很多不必要的對一個對象的掃描工作。接下來，看看這些結構都是如何實現的，首先看看基本類gc_heap裡面都有些什麼：

//class definition of the internal class
class gc_heap
{
//GC Heap
　 friend class GCHeap;
　 friend class CFinalize;
　 friend void ProfScanRootsHelper(Object*&, ScanContext*, DWORD);
　 friend void GCProfileWalkHeap();
public:
//創建一個Heap Segment
　　 heap_segment* make_heap_segment (BYTE* new_pages, size_t size);
//創建一個大對象堆，包含引用的對象
　　 l_heap* make_large_heap (BYTE* new_pages, size_t size, BOOL managed);
　　 gc_heap* make_gc_heap();
　　 void destroy_gc_heap(gc_heap* heap);
　　 static
　　 HRESULT initialize_gc　(size_t vm_block_size,
　　　　　　　　　　　　　　 size_t segment_size,
　　　　　　　　　　　　　　 size_t heap_size);
　　 static
　　 void shutdown_gc();
　　　 //allocate object in heap segments.這個分配動作並不分配大對象，只是分配在GC Heap上面的對象，而不是LOH上面的。LOH上面的對象分配是下面的allocate_large_object方法。
　　 static
　　 CObjectHeader* allocate (size_t jsize,
　　　　　　　　　　　　　　 alloc_context* acontext );
　　 CObjectHeader* try_fast_alloc (size_t jsize);
　　　 //allocate large object method，區別上面的allocate方法。
　　 static
　　 CObjectHeader* allocate_large_object (size_t size, BOOL pointerp, alloc_context* acontext);
　　　 //部分收集，對第幾代進行垃圾收集。
　　 static
　　 int garbage_collect (int n);
　　　 //update brick table and card table。
　　 static
　　 int grow_brick_card_tables (BYTE* start, BYTE* end);
protected:
　　　 //獲取一個Heap segment
　　 static
　　 heap_segment* get_segment ();
　　　 //得到lHeap，屬於保存large objects with pointers。
　　 static
　　 l_heap* get_heap();
　　 static
　　 BOOL allocate_more_space (alloc_context* acontext, size_t jsize);
　　 void reset_allocation_pointers (generation* gen, BYTE* start);
　　 void delete_heap_segment (heap_segment* seg);
　　 void delete_large_heap (l_heap* hp);
　　 void adjust_ephemeral_limits ();
　　 void make_generation (generation& gen, heap_segment* seg,
　　　　　　　　　　　　　 BYTE* start, BYTE* pointer);
　　 int heap_grow_hook (BYTE* mem, size_t memsize, ptrdiff_t delta);
　　 int heap_pregrow_hook (size_t memsize);
　　　 //對card table的操作。
　　 size_t card_of ( BYTE* object);
　　 BYTE* brick_address (size_t brick);
　　 size_t brick_of (BYTE* add);
　　 BYTE* card_address (size_t card);
　　 size_t card_to_brick (size_t card);
　　 void clear_card (size_t card);
　　 void set_card (size_t card);
　　 BOOL　card_set_p (size_t card);
　　 int grow_heap_segment (heap_segment* seg, size_t size);
　　 void copy_brick_card_range (BYTE* la, BYTE* old_card_table,
　　　　　　　　　　　　　　　　 short* old_brick_table,
　　　　　　　　　　　　 　　　 heap_segment* seg,
　　　　　　　　　　　　　　　　 BYTE* start, BYTE* end, BOOL heap_expand);
　　 void copy_brick_card_table_l_heap ();
　　 void copy_brick_card_table(BOOL heap_expand);
　　 void clear_brick_table (BYTE* from, BYTE* end);
　　 void set_brick (size_t index, ptrdiff_t val);
　　　 //根據是否是調試模式來確定是否進行引用的驗證。
　　 static
　　 gc_heap* heap_of (BYTE* object, BOOL verify_p =
#ifdef _DEBUG
　　　　　　　　　　　 TRUE
#else
　　　　　　　　　　　 FALSE
#endif //_DEBUG
){return (gc_heap*)0;}
　　　 //下面的這些方法是在進行垃圾回收整理移動和復制對象的時候適用的。包括一系列的針對object還有card table以及進程的make，copy，fix和verify等動作。
　　 BYTE* mark_object(BYTE* o );
　　 BYTE* mark_object_class (BYTE* o );
　　 void copy_object_simple_const (BYTE** o );
　　 void get_copied_object (BYTE** o );
　　 void scavenge_object_simple (BYTE* o );
　　　 //pinned object被移動到保留的Heap segment區域裡面去。
　　 void scavenge_pinned_object (BYTE* o );
　　 void mark_object_internal (BYTE* o );
　　 BYTE* next_end (heap_segment* seg, BYTE* f);
　　 void fix_card_table ();
　　 void verify_card_table ();
　　 void mark_through_object (BYTE* oo );
　　 BOOL process_mark_overflow (int condemned_gen_number);
　　 void mark_phase (int condemned_gen_number, BOOL mark_only_p);
　　　 //把一個object整成pinned object
　　 void pin_object (BYTE* o, BYTE* low, BYTE* high);
　　　 //update brick table
　　 size_t update_brick_table (BYTE* tree, size_t current_brick,
　　　　　　　　　　　　　　　 BYTE* x, BYTE* plug_end);
　　　 //對card和bricktable的操作
　　 void clear_cards (size_t start_card, size_t end_card);
　　 void clear_card_for_addresses (BYTE* start_address, BYTE* end_address);
　　 void copy_cards (size_t dst_card, size_t src_card,
　　　　　　　　　　 size_t end_card, BOOL nextp);
　　 void copy_cards_for_addresses (BYTE* dest, BYTE* src, size_t len);
　　 BOOL ephemeral_pointer_p (BYTE* o);
　　 void fix_brick_to_highest (BYTE* o, BYTE* next_o);
　　 void copy_through_cards_helper (BYTE** poo, unsigned int& ngen, card_fn fn);
　　 void copy_through_cards_for_segments (card_fn fn);
　　 /* ------------------- per heap members --------------------------*/
public:
　　 BYTE* card_table;
　　 short* brick_table;
　　 BYTE* lowest_address;
　　 BYTE* highest_address;
protected:
　　 heap_segment* ephemeral_heap_segment;
　　　 //定義一個GC可以有幾個Generation
　　 int　　　　 condemned_generation_num;
　　 BYTE* 　　　scavenge_list;
　　 BYTE*　　　 last_scavenge;
　　 BOOL　　　　pinning;
　　 BYTE*　　　 gc_low; // lowest address being condemned
　　 BYTE*　　　 gc_high; //highest address being condemned
　　 size_t　　 　segment_size; //size of each heap segment
　　 size_t　　　lheap_size;　//size of each lheap
　　 BYTE*　min_overflow_address;
　　 BYTE*　max_overflow_address;
　　 GCSpinLock more_space_lock; //lock while allocating more space
　　 GCSpinLock gc_lock; //lock while allocating more space
　　 dynamic_data dynamic_data_table [NUMBERGENERATIONS+1];
　　 //Large object support
　　 l_heap* lheap;
　　 BYTE* lheap_card_table;
　　 gmallocHeap* gheap;
　　 large_object_block* large_p_objects;
　　 large_object_block** last_large_p_object;
　　 large_object_block* large_np_objects;
　　　 //定義多大的對象就會保存到LOH中去。這個默認定義的大小是85000
　　 size_t large_objects_size;
　　 size_t large_blocks_size;
　　 BOOL gen0_bricks_cleared;
　　 CFinalize* finalize_queue;
　　 /* ----------------------- global members ----------------------- */
public:
　　　 //定義最大支持幾代的垃圾回收
　　 static
　　 int g_max_generation;
　　　 //定義一個保留的內存區域
　　 static
　　 size_t reserved_memory;
　　 static
　　 size_t reserved_memory_limit;
}; // class gc_heap

在上面的gc_heap類中，將對傳統意義上面的GC Heap的管理和對LOH的管理，整合到了一起。這兩部分對於垃圾回收是關系密切不可分離的兩個部分，雖然LOH並不會有類似於帶的概念，也不進行compaction的操作，但是個人更加願意把LOH歸類於垃圾回收的一個子系統。上面說到，LOH和GC Heap一個很大的不同，就是LOH並不進行Heap的壓縮工作。Heap的壓縮是說，譬如在Generation 1中，經常進行Object的分配和finalize，就會造成這個區域的很多碎片，這個對於整個Heap的效率內存空間都有比較大的負面影響。關於對Heap的Compaction壓縮，這是一個非常有趣好玩的事情，當然不是一兩句能夠說清楚的，這篇文章的重點在於說說GC Heap的結構，這個有趣的解決方法就在以後的博文裡面探討把。這裡只說說LOH的Heap為什麼沒有Compaction。因為在一個LOH中移動一個大對象是非常消耗系統資源的。LOH在實現的時候，是采用了開源的malloc-style heap的實現。這個實現中並沒有涉及到Heap的壓縮。基於性能的考慮，MS采用了一種折中的解決方案。給這個LOH中劃分出了兩種不同類型的Heap，也就是上面提到的，一種存放不包含pointer的Heap，另外一種是包含pointer的Heap。對對象的這種判斷，是基於其Metatable的。

接下來，看看Heap Segment的實現：

class heap_segment
{
public:
　　　 //指向已經分配了的內存的末端
　　 BYTE*　　　　　 allocated;
　　 BYTE*　　　　　 committed;
　　　 //指向一個segment的保留區域
　　 BYTE*　　　　　 reserved;
　　 BYTE*　　　　　 used;
　　 BYTE*　　　　　 mem;
　　　 //對所有的Heap segment都是鏈在一起成一條鏈的。
　　 heap_segment*　 next;
　　 BYTE*　　　　　 plan_allocated;
　　 BYTE*　　　　　 padx;
　　 BYTE*　　　　　 pad0;
#if ((SIZEOF_OBJHEADER+ALIGNFIXUP) % 8) != 0
　　 BYTE　　　　　　pad1[8 - ((SIZEOF_OBJHEADER+ALIGNFIXUP) % 8)];　 // Must pad to quad word
#endif
　　 plug　　　　　　mPlug;
};然後看看一個Heap segment裡面的Generation是如何實現的：class generation
{
public:
　　　 //分配上下文
　　alloc_context　 allocation_context;
　　　 //這個generation存在的Heap segment
　　heap_segment*　 allocation_segment;
　　BYTE*　　　　　free_list;
　　heap_segment*　 start_segment;
　　BYTE*　　　　　 allocation_start;
　　BYTE*　　　　　 plan_allocation_start;
　　BYTE*　　　　　 last_gap;
　　　 //一個Generation裡面剩余的空閒未分配空間
　　size_t　　　　　free_list_space;
　　　 //generation裡面的已經分配的空間的大小
　　size_t　　　　　allocation_size;
};

還有一個問題提一下，就是在最上面的gc_heap的實現的時候，一個GC Heap裡面的Heap Segment可以方便的添加和擴展，而且，在邏輯結構上面，同一個Generation的東西，可以分布在一個或者多個Heap segment裡面。同時，gc_heap類的設計，也保證了可以方便的擴展一個GC Heap裡面的Generation的個數。對一個GC Heap的架構設計及其實現，就寫到這裡吧，雖然有許多細節問題沒有寫出來，敲的太多了，但是主要的問題也算講清楚了吧 ^_^在下面的文章中，就探索下垃圾回收的算法和回收實現機制，以及在垃圾回收裡面的比較棘手的問題的挺有趣的解決方案吧。