gc
1.0.0
gc是保守的、線程本地的、標記和清除垃圾收集器的實作。此實作為標準 POSIX malloc() 、 calloc() 、 realloc()和free()呼叫提供了功能齊全的替代。
gc的重點是提供概念上乾淨的標記和清除 GC 實現，而無需深入研究特定於體系結構的最佳化（例如，請參閱 Boehm GC 以了解此類任務）。它應該特別適合學習目的，並且對各種優化開放（歡迎 PR！）。
gc的最初動機是我希望用 C 語言完全從頭開始編寫自己的 LISP - 這需要垃圾收集。
如果沒有閱讀其他人的工作的能力，這項工作是不可能完成的，尤其是 Boehm GC、orangeduck 的 tgc（也遵循小型和簡單的理想）和垃圾收集手冊。
gc實作中的基本概念和設計決策。 $ git clone [email protected]:mkirchner/gc.git
$ cd gc
使用clang編譯器進行編譯：
$ make test
要使用 GNU 編譯器集合 (GCC)：
$ make test CC=gcc
測試應該會成功完成。建立目前覆蓋率報告：
$ make coverage
...
#include "gc.h"
...
void some_fun () {
...
int * my_array = gc_calloc ( & gc , 1024 , sizeof ( int ));
for ( size_t i = 0 ; i < 1024 ; ++ i ) {
my_array [ i ] = 42 ;
}
...
// look ma, no free!
}
int main ( int argc , char * argv []) {
gc_start ( & gc , & argc );
...
some_fun ();
...
gc_stop ( & gc );
return 0 ;
}這描述了核心 API，請參閱gc.h以了解更多詳細資訊和低階 API。
為了初始化並開始垃圾收集，請使用gc_start()函數並傳遞堆疊底部位址：
void gc_start ( GarbageCollector * gc , void * bos );棧底參數bos需要指向堆疊分配的變量，並標記根查找（掃描）開始的堆疊低端。
垃圾收集可以停止、暫停和恢復
void gc_stop ( GarbageCollector * gc );
void gc_pause ( GarbageCollector * gc );
void gc_resume ( GarbageCollector * gc );並且可以透過以下方式觸發手動垃圾收集
size_t gc_run ( GarbageCollector * gc );gc支援malloc() 、 calloc()和realloc()風格的記憶體分配。各自的函數簽章模仿 POSIX 函數（除了我們需要將垃圾收集器作為第一個參數傳遞）：
void * gc_malloc ( GarbageCollector * gc , size_t size );
void * gc_calloc ( GarbageCollector * gc , size_t count , size_t size );
void * gc_realloc ( GarbageCollector * gc , void * ptr , size_t size );可以透過擴充介面將指標傳遞給析構函數：
void * dtor ( void * obj ) {
// do some cleanup work
obj -> parent -> deregister ();
obj -> db -> disconnect ()
...
// no need to free obj
}
...
SomeObject * obj = gc_malloc_ext ( gc , sizeof ( SomeObject ), dtor );
... gc支援靜態分配，僅當 GC 透過gc_stop()關閉時才會進行垃圾收集。只需使用適當的輔助函數：
void * gc_malloc_static ( GarbageCollector * gc , size_t size , void ( * dtor )( void * ));靜態分配需要一個指向終結函數的指標；如果不需要終結，只需設定為NULL 。
請注意， gc目前在收集靜態變數時不保證特定的順序，如果需要以特定順序釋放靜態變量，使用者應在呼叫gc_stop()之前按所需順序對它們呼叫gc_free() ，請參見下文。
也可以使用以下命令觸發顯式記憶體釋放
void gc_free ( GarbageCollector * gc , void * ptr );呼叫gc_free()保證 (a) 在適用的情況下終結/銷毀ptr指向的對象，以及 (b) 釋放ptr指向的內存，無論當前的垃圾回收調度如何，並且如果 GC 已執行，也將起作用。使用上面的gc_pause()暫停。
gc也提供了一個strdup()實現，它傳回垃圾收集的副本：
char * gc_strdup ( GarbageCollector * gc , const char * s );垃圾收集背後的基本想法是自動化記憶體分配/釋放週期。這是透過追蹤所有已分配的記憶體並定期觸發仍已分配但無法存取的記憶體的釋放來實現的。
許多高階垃圾收集器也實作了自己的記憶體分配方法（即替換malloc() ）。這通常使他們能夠以更節省空間的方式佈局記憶體或更快地訪問，但代價是特定於架構的實現和增加的複雜性。 gc透過依靠 POSIX *alloc()實作並將記憶體管理和垃圾收集元資料分開來迴避這些問題。這使得gc更容易理解，但當然，與更優化的方法相比，空間和時間效率也較低。
gc內部的核心資料結構是一個哈希映射，它將分配的記憶體的位址映射到該記憶體的垃圾收集元資料：
哈希映射中的項目是分配，用Allocation struct建模：
typedef struct Allocation {
void * ptr ; // mem pointer
size_t size ; // allocated size in bytes
char tag ; // the tag for mark-and-sweep
void ( * dtor )( void * ); // destructor
struct Allocation * next ; // separate chaining
} Allocation ;每個Allocation實例都包含一個指向已分配記憶體的指標、該位置已分配記憶體的大小、一個用於標記和清除的標記（見下文）、一個指向析構函數的可選指標以及一個指向下一個Allocation實例的指標（對於單獨的鏈接，請參見下文）。
分配收集在AllocationMap中
typedef struct AllocationMap {
size_t capacity ;
size_t min_capacity ;
double downsize_factor ;
double upsize_factor ;
double sweep_factor ;
size_t sweep_limit ;
size_t size ;
Allocation * * allocs ;
} AllocationMap ;它與gc.c內的一組static函數一起，為公共 API 的實作提供雜湊映射語義。
AllocationMap是GarbageCollector結構中的中心資料結構，它是公共 API 的一部分：
typedef struct GarbageCollector {
struct AllocationMap * allocs ;
bool paused ;
void * bos ;
size_t min_size ;
} GarbageCollector ;基本資料結構就位後，任何gc_*alloc()內存分配請求都是一個兩步驟過程：首先，透過系統（即標準malloc() ）功能分配內存，其次，將相關元資料添加或更新到哈希映射。
對於gc_free() ，使用指針在哈希映射中定位元數據，確定釋放是否需要析構函數調用，如果需要則調用，釋放託管內存並從哈希映射中刪除元數據條目。
這些資料結構和相關介面支援管理建置垃圾收集器所需的元資料。
gc在兩種情況下觸發收集： (a) 當對系統分配的任何呼叫失敗時（希望釋放足夠的記憶體來滿足當前請求）； (b)當雜湊映射中的條目數量超過動態調整的高水位線時。
如果發生其中任何一種情況， gc都會停止運行，並對所有目前分配運行標記和清除垃圾收集。此功能在gc_run()函數中實現，該函數是公共 API 的一部分，並將所有工作委託給屬於私有 API 的gc_mark()和gc_sweep()函數。
gc_mark()的任務是尋找根並將從根引用的所有已知分配（或從根引用的分配，即傳遞性）標記為「已使用」。一旦標記完成， gc_sweep()就會迭代所有已知的分配並釋放所有未使用的（即未標記的）分配，返回gc_run()並且世界繼續運行。
gc將保留可存取的記憶體分配並收集其他所有內容。若滿足下列任一條件，則分配視為可達：
gc_start()的堆疊底部變數一樣深（即bos是標記階段期間考慮的最小堆疊位址）。gc_*alloc()指派的內容內部有一個指標指向分配內容。GC_TAG_ROOT 。樸素的標記和清除演算法分兩個階段運行。首先，在標記階段，演算法會尋找並標記所有根分配以及從根可到達的所有分配。其次，在清除階段，演算法會遍歷所有已知的分配，收集所有未標記並因此被視為無法存取的分配。
在標記階段開始時，我們首先掃描所有已知的分配並使用GC_TAG_ROOT標記集找到明確根。每個根都是深度優先遞歸標記的起點。
gc隨後檢測堆疊中的所有根（從傳遞給gc_start()的堆疊底部指標bos開始）和暫存器（透過在標記階段之前將它們轉儲到堆疊上）並使用它們作為起始點標記也是如此。
給定根分配，標記包括 (1) 將Allocation物件中的tag欄位設為GC_TAG_MARK ，以及 (2) 掃描分配的記憶體以查找指向已知分配的指針，並遞歸地重複此過程。
底層實作是一個簡單的遞歸深度優先搜索，它掃描所有記憶體內容以查找潛在的引用：
void gc_mark_alloc ( GarbageCollector * gc , void * ptr )
{
Allocation * alloc = gc_allocation_map_get ( gc -> allocs , ptr );
if ( alloc && !( alloc -> tag & GC_TAG_MARK )) {
alloc -> tag |= GC_TAG_MARK ;
for ( char * p = ( char * ) alloc -> ptr ;
p < ( char * ) alloc -> ptr + alloc -> size ;
++ p ) {
gc_mark_alloc ( gc , * ( void * * ) p );
}
}
}在gc.c中， gc_mark()透過呼叫gc_mark_roots()標記堆疊上的已知根來啟動標記過程。為了標記根，我們對所有已知的分配進行了一次完整的遍歷。然後我們繼續將暫存器轉儲到堆疊上。
為了使 CPU 暫存器內容可用於根查找， gc將它們轉儲到堆疊上。這是使用setjmp()以某種可移植的方式實現的，它在我們標記堆疊之前將它們儲存在jmp_buf變數中：
...
/* Dump registers onto stack and scan the stack */
void ( * volatile _mark_stack )( GarbageCollector * ) = gc_mark_stack ;
jmp_buf ctx ;
memset ( & ctx , 0 , sizeof ( jmp_buf ));
setjmp ( ctx );
_mark_stack ( gc );
...使用volatile函數指標_mark_stack繞道到gc_mark_stack()函數是必要的，以避免內聯對gc_mark_stack()的呼叫。
在標記所有可存取並因此可能仍在使用的記憶體之後，收集不可存取的分配就很簡單了。這是gc_sweep()的實作：
size_t gc_sweep ( GarbageCollector * gc )
{
size_t total = 0 ;
for ( size_t i = 0 ; i < gc -> allocs -> capacity ; ++ i ) {
Allocation * chunk = gc -> allocs -> allocs [ i ];
Allocation * next = NULL ;
while ( chunk ) {
if ( chunk -> tag & GC_TAG_MARK ) {
/* unmark */
chunk -> tag &= ~ GC_TAG_MARK ;
chunk = chunk -> next ;
} else {
total += chunk -> size ;
if ( chunk -> dtor ) {
chunk -> dtor ( chunk -> ptr );
}
free ( chunk -> ptr );
next = chunk -> next ;
gc_allocation_map_remove ( gc -> allocs , chunk -> ptr , false);
chunk = next ;
}
}
}
gc_allocation_map_resize_to_fit ( gc -> allocs );
return total ;
}我們迭代哈希映射中的所有分配（ for循環），遵循每個鏈（帶有chunk = chunk->next update 的while循環），並且（1）如果已標記區塊則取消標記；或 (2) 呼叫該區塊的析構函數並釋放未標記的內存，並保留我們釋放的內存量的運行總數。
標記和掃描運行結束。停止的世界又恢復了，我們已經準備好迎接下一次奔跑了！
