gc
1.0.0
gc 、保守的なスレッドローカルのマークアンドスイープ ガベージ コレクターの実装です。この実装は、標準の POSIX malloc() 、 calloc() 、 realloc() 、およびfree()呼び出しの完全な機能の置き換えを提供します。
gcの焦点は、アーキテクチャ固有の最適化を深く掘り下げることなく、概念的にクリーンなマークアンドスイープ GC の実装を提供することです (そのような取り組みについては、たとえば Boehm GC を参照してください)。特に学習目的に適しており、あらゆる種類の最適化に対応しています (PR 歓迎!)。
gcの元々の動機は、完全にゼロから C で独自の LISP を書きたいという願望でした。そのためにはガベージ コレクションが必要でした。
この作品は、他の作品、特に Boehm GC、orangeduck の tgc (これも小型でシンプルであるという理想に従っています)、および The Garbage Collection Handbook を読む能力がなければ不可能でした。
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 について説明しています。詳細と低レベル API についてはgc.h参照してください。
ガベージ コレクションを初期化して開始するには、 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_stop()によって GC がシャットダウンされた場合にのみガベージ コレクションされる静的割り当てをサポートします。適切なヘルパー関数を使用するだけです。
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 、パブリック API の一部であるGarbageCollector構造体の中心となるデータ構造です。
typedef struct GarbageCollector {
struct AllocationMap * allocs ;
bool paused ;
void * bos ;
size_t min_size ;
} GarbageCollector ;基本的なデータ構造が整っている場合、 gc_*alloc()メモリ割り当てリクエストは 2 段階の手順になります。まず、システム (つまり、標準のmalloc() ) 機能を通じてメモリを割り当てます。次に、関連するメタデータをシステムに追加または更新します。ハッシュマップ。
gc_free()の場合、ポインタを使用してハッシュ マップ内のメタデータを見つけ、割り当て解除にデストラクタ呼び出しが必要かどうかを判断し、必要に応じて呼び出し、マネージド メモリを解放し、ハッシュ マップからメタデータ エントリを削除します。
これらのデータ構造と関連インターフェイスにより、ガベージ コレクターの構築に必要なメタデータの管理が可能になります。
gc次の 2 つの状況で収集をトリガーします。(a) システム割り当てへの呼び出しのいずれかが失敗したとき (現在の要求を満たすために十分なメモリの割り当てを解除することを期待している場合)。 (b) ハッシュ マップ内のエントリの数が動的に調整された最高水準点を超えたとき。
これらのケースのいずれかが発生した場合、 gcワールドを停止し、現在のすべての割り当てに対してマークアンドスイープ ガベージ コレクションの実行を開始します。この機能は、パブリック API の一部であるgc_run()関数に実装されており、すべての作業をプライベート API の一部であるgc_mark()およびgc_sweep()関数に委任します。
gc_mark()は、ルートを検索し、ルートから (またはルートから、つまり推移的に参照される割り当てから) 参照されるすべての既知の割り当てを「使用済み」としてタグ付けするタスクがあります。のマーク付けが完了すると、 gc_sweep()すべての既知の割り当てを繰り返し、すべての未使用 (つまりマークされていない) 割り当てを割り当て解除し、 gc_run()に戻り、ワールドは実行を続けます。
gc到達可能なメモリ割り当てを保持し、その他すべてを収集します。次のいずれかに該当する場合、割り当ては到達可能であるとみなされます。
gc_start()に渡されるスタックの底部変数と同じ深さのスタック フレーム内に存在する必要があります (つまり、 bosマーク フェーズ中に考慮される最小のスタック アドレスです)。gc_*alloc()で割り当てられたコンテンツ内には、割り当てコンテンツを指すポインタがあります。GC_TAG_ROOTのタグが付けられます。単純なマークアンドスイープ アルゴリズムは 2 段階で実行されます。まず、マーク段階で、アルゴリズムはすべてのルート割り当てとルートから到達可能なすべての割り当てを見つけてマークします。 2 番目に、スイープステージでは、アルゴリズムはすべての既知の割り当てを渡し、マークされていないため、到達不可能と見なされるすべての割り当てを収集します。
マークステージの開始時に、まず既知の割り当てをすべてスイープし、 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()の呼び出しを介してスタック上の既知のルートをマークすることにより、マーク プロセスを開始します。ルートをマークするために、既知のすべての割り当てを 1 回完全に実行します。次に、スタック上のレジスタのダンプに進みます。
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 );
... gc_mark_stack()への呼び出しのインライン化を回避するには、 volatile関数ポインタ_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) チャンクに対してデストラクターを呼び出し、マークされていない場合はメモリを解放し、解放したメモリ量の現在までの合計を維持します。
これでマーク＆スイープの実行は終了です。停止した世界が再開され、次の実行の準備が整いました。
