gc
1.0.0
gc ist eine Implementierung eines konservativen, Thread-lokalen Mark-and-Sweep-Garbage Collectors. Die Implementierung bietet einen voll funktionsfähigen Ersatz für die standardmäßigen POSIX-Aufrufe malloc() , calloc() , realloc() und free() .
Der Schwerpunkt von gc liegt auf der Bereitstellung einer konzeptionell sauberen Implementierung eines Mark-and-Sweep-GC, ohne in die Tiefen der architekturspezifischen Optimierung einzutauchen (siehe z. B. den Boehm GC für ein solches Unterfangen). Es sollte besonders für Lernzwecke geeignet sein und ist offen für Optimierungen aller Art (PRs willkommen!).
Die ursprüngliche Motivation für gc war mein Wunsch, mein eigenes LISP in C völlig von Grund auf zu schreiben – und das erforderte Garbage Collection.
Diese Arbeit wäre ohne die Fähigkeit, die Arbeit anderer zu lesen, nicht möglich gewesen, insbesondere von Boehm GC, orangeducks tgc (das ebenfalls den Idealen von Winzigkeit und Einfachheit folgt) und The Garbage Collection Handbook.
gc eingeflossen sind. $ git clone [email protected]:mkirchner/gc.git
$ cd gc
So kompilieren Sie mit dem clang -Compiler:
$ make test
So verwenden Sie die GNU Compiler Collection (GCC):
$ make test CC=gcc
Die Tests sollten erfolgreich abgeschlossen werden. So erstellen Sie den aktuellen Abdeckungsbericht:
$ 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 ;
} Dies beschreibt die Kern-API, weitere Details finden Sie unter gc.h und die Low-Level-API.
Um die Garbage Collection zu initialisieren und zu starten, verwenden Sie die Funktion gc_start() und übergeben Sie eine Adresse am unteren Ende des Stapels :
void gc_start ( GarbageCollector * gc , void * bos ); Der Bottom-of-Stack-Parameter bos muss auf eine dem Stack zugewiesene Variable verweisen und markiert das untere Ende des Stacks, von dem aus die Root-Suche (Scanning) beginnt.
Die Garbage Collection kann mit gestoppt, pausiert und wieder aufgenommen werden
void gc_stop ( GarbageCollector * gc );
void gc_pause ( GarbageCollector * gc );
void gc_resume ( GarbageCollector * gc );und die manuelle Speicherbereinigung kann mit ausgelöst werden
size_t gc_run ( GarbageCollector * gc ); gc unterstützt die Speicherzuweisung im Stil malloc() , calloc() und realloc() . Die jeweiligen Funktionssignaturen ahmen die POSIX-Funktionen nach (mit der Ausnahme, dass wir den Garbage Collector als erstes Argument übergeben müssen):
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 );Es ist möglich, über die erweiterte Schnittstelle einen Zeiger auf eine Destruktorfunktion zu übergeben:
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 unterstützt statische Zuweisungen, deren Garbage Collection nur erfolgt, wenn der GC über gc_stop() heruntergefahren wird. Benutzen Sie einfach die entsprechende Hilfsfunktion:
void * gc_malloc_static ( GarbageCollector * gc , size_t size , void ( * dtor )( void * )); Die statische Zuweisung erwartet einen Zeiger auf eine Finalisierungsfunktion. einfach auf NULL setzen, wenn keine Finalisierung erforderlich ist.
Beachten Sie, dass gc derzeit keine bestimmte Reihenfolge beim Sammeln statischer Variablen garantiert. Wenn statische Variablen in einer bestimmten Reihenfolge freigegeben werden müssen, sollte der Benutzer gc_free() in der gewünschten Reihenfolge für sie aufrufen, bevor er gc_stop() aufruft, siehe unten .
Es ist auch möglich, eine explizite Speicherfreigabe auszulösen
void gc_free ( GarbageCollector * gc , void * ptr ); Der Aufruf von gc_free() garantiert (a) die Finalisierung/Zerstörung des Objekts, auf das ptr zeigt, sofern zutreffend, und (b) die Freigabe des Speichers, auf den ptr zeigt, unabhängig von der aktuellen Planung für die Speicherbereinigung, und funktioniert auch, wenn GC durchgeführt wurde pausiert mit gc_pause() oben.
gc bietet auch eine strdup() Implementierung, die eine vom Garbage Collection gesammelte Kopie zurückgibt:
char * gc_strdup ( GarbageCollector * gc , const char * s );Die Grundidee der Garbage Collection besteht darin, den Speicherzuweisungs-/-freigabezyklus zu automatisieren. Dies wird erreicht, indem der gesamte zugewiesene Speicher verfolgt und in regelmäßigen Abständen die Freigabe für Speicher ausgelöst wird, der noch zugewiesen, aber nicht erreichbar ist.
Viele fortgeschrittene Garbage Collectors implementieren auch ihren eigenen Ansatz zur Speicherzuweisung (z. B. ersetzen Sie malloc() ). Dies ermöglicht es ihnen oft, den Speicher platzsparender zu gestalten oder einen schnelleren Zugriff zu ermöglichen, allerdings geht dies auf Kosten architekturspezifischer Implementierungen und erhöhter Komplexität. gc umgeht diese Probleme, indem es auf die POSIX *alloc() Implementierungen zurückgreift und Speicherverwaltung und Garbage-Collection-Metadaten getrennt hält. Dadurch ist gc viel einfacher zu verstehen, aber natürlich auch weniger platz- und zeiteffizient als optimiertere Ansätze.
Die Kerndatenstruktur in gc ist eine Hash-Map, die die Adresse des zugewiesenen Speichers den Garbage-Collection-Metadaten dieses Speichers zuordnet:
Die Elemente in der Hash-Map sind Zuweisungen, modelliert mit der 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 ; Jede Allocation -Instanz enthält einen Zeiger auf den zugewiesenen Speicher, die Größe des zugewiesenen Speichers an dieser Stelle, ein Tag für Mark-and-Sweep (siehe unten), einen optionalen Zeiger auf die Destruktorfunktion und einen Zeiger auf die nächste Allocation -Instanz ( separate Verkettung siehe unten).
Die Allokationen werden in einer AllocationMap gesammelt
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 ; Dies stellt zusammen mit einer Reihe static Funktionen in gc.c eine Hash-Map-Semantik für die Implementierung der öffentlichen API bereit.
Die AllocationMap ist die zentrale Datenstruktur in der GarbageCollector -Struktur, die Teil der öffentlichen API ist:
typedef struct GarbageCollector {
struct AllocationMap * allocs ;
bool paused ;
void * bos ;
size_t min_size ;
} GarbageCollector ; Wenn die grundlegenden Datenstrukturen vorhanden sind, ist jede gc_*alloc() -Speicherzuweisungsanforderung ein zweistufiger Vorgang: Erstens wird der Speicher über die Systemfunktionalität (d. h. die Standardfunktion malloc() ) zugewiesen und zweitens werden die zugehörigen Metadaten hinzugefügt oder aktualisiert Hash-Karte.
Verwenden Sie für gc_free() den Zeiger, um die Metadaten in der Hash-Map zu lokalisieren, festzustellen, ob die Freigabe einen Destruktoraufruf erfordert, rufen Sie bei Bedarf auf, geben den verwalteten Speicher frei und löschen den Metadateneintrag aus der Hash-Map.
Diese Datenstrukturen und die zugehörigen Schnittstellen ermöglichen die Verwaltung der Metadaten, die zum Aufbau eines Garbage Collectors erforderlich sind.
gc löst die Erfassung unter zwei Umständen aus: (a) wenn einer der Aufrufe der Systemzuweisung fehlschlägt (in der Hoffnung, ausreichend Speicher freizugeben, um die aktuelle Anforderung zu erfüllen); und (b) wenn die Anzahl der Einträge in der Hash-Map eine dynamisch angepasste Höchstgrenze überschreitet.
Wenn einer dieser Fälle auftritt, stoppt gc die Welt und startet einen Mark-and-Sweep-Garbage-Collection-Lauf über alle aktuellen Zuweisungen. Diese Funktionalität ist in der Funktion gc_run() implementiert, die Teil der öffentlichen API ist und die gesamte Arbeit an die Funktionen gc_mark() und gc_sweep() delegiert, die Teil der privaten API sind.
gc_mark() hat die Aufgabe, Wurzeln zu finden und alle bekannten Zuordnungen, die von einer Wurzel aus referenziert werden (oder von einer Zuordnung, die von einer Wurzel aus referenziert wird, also transitiv), als „verwendet“ zu kennzeichnen. Sobald die Markierung abgeschlossen ist, durchläuft gc_sweep() alle bekannten Zuweisungen und gibt alle nicht verwendeten (d. h. nicht markierten) Zuweisungen frei, kehrt zu gc_run() zurück und die Welt läuft weiter.
gc behält die erreichbaren Speicherzuordnungen bei und sammelt alles andere. Eine Zuweisung gilt als erreichbar, wenn eine der folgenden Bedingungen zutrifft:
gc_start() übergeben wird (dh bos ist die kleinste Stapeladresse, die während der Markierungsphase berücksichtigt wird).gc_*alloc() -allocated-Inhalt, der auf den Allocation-Inhalt zeigt.GC_TAG_ROOT gekennzeichnet.Der naive Mark-and-Sweep-Algorithmus läuft in zwei Stufen ab. Zunächst findet und markiert der Algorithmus in einer Markierungsphase alle Root- Zuweisungen und alle Zuweisungen, die von den Roots aus erreichbar sind. Zweitens durchläuft der Algorithmus in der Sweep -Phase alle bekannten Zuweisungen und sammelt alle Zuweisungen, die nicht markiert wurden und daher als nicht erreichbar gelten.
Zu Beginn der Markierungsphase durchsuchen wir zunächst alle bekannten Zuordnungen und finden explizite Wurzeln mit dem Tag-Set GC_TAG_ROOT . Jede dieser Wurzeln ist ein Ausgangspunkt für die rekursive Tiefenmarkierung.
gc erkennt anschließend alle Wurzeln im Stapel (beginnend mit dem unteren Stapelzeiger bos der an gc_start() übergeben wird) und die Register (indem sie sie vor der Markierungsphase auf dem Stapel ablegen) und verwendet diese als Ausgangspunkte für auch Markierung.
Bei einer Root-Zuweisung besteht die Markierung darin, (1) das tag -Feld in einem Allocation auf GC_TAG_MARK zu setzen und (2) den zugewiesenen Speicher nach Zeigern auf bekannte Zuweisungen zu durchsuchen und den Vorgang rekursiv zu wiederholen.
Die zugrunde liegende Implementierung ist eine einfache, rekursive Tiefensuche, die den gesamten Speicherinhalt durchsucht, um potenzielle Referenzen zu finden:
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 );
}
}
} In gc.c startet gc_mark() den Markierungsprozess, indem es die bekannten Wurzeln auf dem Stapel über einen Aufruf von gc_mark_roots() markiert. Um die Wurzeln zu markieren, führen wir einen vollständigen Durchlauf durch alle bekannten Zuordnungen durch. Anschließend legen wir die Register auf dem Stapel ab.
Um die CPU-Registerinhalte für die Root-Suche verfügbar zu machen, legt gc sie auf dem Stapel ab. Dies wird auf einigermaßen portable Weise mit setjmp() implementiert, das sie direkt vor dem Markieren des Stapels in einer jmp_buf Variablen speichert:
...
/* 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 );
... Der Umweg über den volatile Funktionszeiger _mark_stack zur Funktion gc_mark_stack() ist notwendig, um das Inlining des Aufrufs von gc_mark_stack() zu vermeiden.
Nachdem der gesamte Speicher markiert wurde, der erreichbar ist und daher möglicherweise noch verwendet wird, ist das Erfassen der nicht erreichbaren Zuweisungen trivial. Hier ist die Implementierung von 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 ;
} Wir iterieren über alle Zuweisungen in der Hash-Map (die for Schleife), folgen jeder Kette (die while Schleife mit dem chunk = chunk->next update) und entfernen entweder (1) die Markierung des Blocks, wenn er markiert war; oder (2) Rufen Sie den Destruktor für den Block auf und geben Sie den Speicher frei, wenn er nicht markiert wurde, und behalten Sie eine laufende Summe der von uns freigegebenen Speichermenge bei.
Damit ist der Mark & Sweep-Lauf abgeschlossen. Die gestoppte Welt wird wieder aufgenommen und wir sind bereit für den nächsten Lauf!
