gc
1.0.0
gc est une implémentation d'un garbage collector conservateur, thread-local, mark-and-sweep. L'implémentation fournit un remplacement entièrement fonctionnel pour les appels POSIX standard malloc() , calloc() , realloc() et free() .
L'objectif de gc est de fournir une implémentation conceptuellement propre d'un GC mark-and-sweep, sans plonger dans les profondeurs de l'optimisation spécifique à l'architecture (voir par exemple le GC Boehm pour une telle entreprise). Il doit être particulièrement adapté à des fins d'apprentissage et est ouvert à toutes sortes d'optimisation (RP bienvenus !).
La motivation initiale de gc est mon désir d'écrire mon propre LISP en C, entièrement à partir de zéro - et cela nécessitait un garbage collection.
Ce travail n'aurait pas été possible sans la capacité de lire le travail des autres, notamment le Boehm GC, le tgc d'orangeduck (qui suit également les idéaux d'être petit et simple) et The Garbage Collection Handbook.
gc . $ git clone [email protected]:mkirchner/gc.git
$ cd gc
Pour compiler à l'aide du compilateur clang :
$ make test
Pour utiliser la collection de compilateurs GNU (GCC) :
$ make test CC=gcc
Les tests devraient se terminer avec succès. Pour créer le rapport de couverture actuel :
$ 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 ;
} Ceci décrit l'API principale, voir gc.h pour plus de détails et l'API de bas niveau.
Afin d'initialiser et de démarrer le garbage collection, utilisez la fonction gc_start() et transmettez une adresse de bas de pile :
void gc_start ( GarbageCollector * gc , void * bos ); Le paramètre de bas de pile bos doit pointer vers une variable allouée à la pile et marque l'extrémité inférieure de la pile à partir de laquelle commence la recherche (analyse) de la racine.
La collecte des déchets peut être arrêtée, mise en pause et reprise avec
void gc_stop ( GarbageCollector * gc );
void gc_pause ( GarbageCollector * gc );
void gc_resume ( GarbageCollector * gc );et la collecte manuelle des déchets peut être déclenchée avec
size_t gc_run ( GarbageCollector * gc ); gc prend en charge l'allocation de mémoire de style malloc() , calloc() et realloc() . Les signatures de fonctions respectives imitent les fonctions POSIX (à l'exception du fait que nous devons transmettre le garbage collector comme premier argument) :
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 );Il est possible de passer un pointeur vers une fonction destructeur via l'interface étendue :
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 prend en charge les allocations statiques qui sont récupérées uniquement lorsque le GC s'arrête via gc_stop() . Utilisez simplement la fonction d'assistance appropriée :
void * gc_malloc_static ( GarbageCollector * gc , size_t size , void ( * dtor )( void * )); L'allocation statique attend un pointeur vers une fonction de finalisation ; définissez simplement sur NULL si la finalisation n'est pas requise.
Notez que gc ne garantit actuellement pas un ordre spécifique lorsqu'il collecte des variables statiques. Si les variables statiques doivent être libérées dans un ordre particulier, l'utilisateur doit les appeler gc_free() dans l'ordre souhaité avant d'appeler gc_stop() , voir ci-dessous. .
Il est également possible de déclencher une désallocation explicite de mémoire en utilisant
void gc_free ( GarbageCollector * gc , void * ptr ); L'appel de gc_free() est garanti pour (a) finaliser/détruire l'objet pointé par ptr le cas échéant et (b) libérer la mémoire vers laquelle ptr pointe quelle que soit la planification actuelle du garbage collection et fonctionnera également si GC a été mis en pause en utilisant gc_pause() ci-dessus.
gc propose également une implémentation strdup() qui renvoie une copie récupérée :
char * gc_strdup ( GarbageCollector * gc , const char * s );L’idée fondamentale derrière le garbage collection est d’automatiser le cycle d’allocation/désallocation de mémoire. Ceci est accompli en gardant une trace de toute la mémoire allouée et en déclenchant périodiquement la désallocation de la mémoire qui est toujours allouée mais inaccessible.
De nombreux garbage collector avancés implémentent également leur propre approche de l'allocation de mémoire (c'est-à-dire remplacer malloc() ). Cela leur permet souvent d'agencer la mémoire de manière plus efficace en termes d'espace ou pour un accès plus rapide, mais cela se fait au prix d'implémentations spécifiques à l'architecture et d'une complexité accrue. gc évite ces problèmes en s'appuyant sur les implémentations POSIX *alloc() et en séparant la gestion de la mémoire et les métadonnées du garbage collection. Cela rend gc beaucoup plus simple à comprendre mais, bien sûr, aussi moins efficace en termes d'espace et de temps que des approches plus optimisées.
La structure de données de base à l'intérieur gc est une carte de hachage qui mappe l'adresse de la mémoire allouée aux métadonnées du garbage collection de cette mémoire :
Les éléments de la table de hachage sont des allocations, modélisées avec la struct Allocation :
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 ; Chaque instance Allocation contient un pointeur vers la mémoire allouée, la taille de la mémoire allouée à cet emplacement, une balise pour le marquage et le balayage (voir ci-dessous), un pointeur facultatif vers la fonction destructeur et un pointeur vers l'instance Allocation suivante ( pour un chaînage séparé, voir ci-dessous).
Les allocations sont collectées dans un 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 ; qui, associé à un ensemble de fonctions static dans gc.c , fournit une sémantique de carte de hachage pour la mise en œuvre de l'API publique.
AllocationMap est la structure de données centrale de la structure GarbageCollector qui fait partie de l'API publique :
typedef struct GarbageCollector {
struct AllocationMap * allocs ;
bool paused ;
void * bos ;
size_t min_size ;
} GarbageCollector ; Avec les structures de données de base en place, toute demande d'allocation de mémoire gc_*alloc() est une procédure en deux étapes : premièrement, allouer la mémoire via la fonctionnalité du système (c'est-à-dire malloc() standard) et deuxièmement, ajouter ou mettre à jour les métadonnées associées au carte de hachage.
Pour gc_free() , utilisez le pointeur pour localiser les métadonnées dans la carte de hachage, déterminez si la désallocation nécessite un appel au destructeur, appelez si nécessaire, libérez la mémoire gérée et supprimez l'entrée de métadonnées de la carte de hachage.
Ces structures de données et les interfaces associées permettent la gestion des métadonnées nécessaires à la construction d'un garbage collector.
gc déclenche la collecte dans deux circonstances : (a) lorsque l'un des appels à l'allocation système échoue (dans l'espoir de libérer suffisamment de mémoire pour répondre à la demande en cours) ; et (b) lorsque le nombre d'entrées dans la carte de hachage dépasse une limite supérieure ajustée dynamiquement.
Si l'un de ces cas se produit, gc arrête le monde et démarre un garbage collection par marquage et balayage sur toutes les allocations actuelles. Cette fonctionnalité est implémentée dans la fonction gc_run() qui fait partie de l'API publique et délègue tout le travail aux fonctions gc_mark() et gc_sweep() qui font partie de l'API privée.
gc_mark() a pour tâche de trouver les racines et de marquer toutes les allocations connues qui sont référencées depuis une racine (ou depuis une allocation référencée depuis une racine, c'est-à-dire de manière transitive) comme "utilisées". Une fois le marquage de terminé, gc_sweep() parcourt toutes les allocations connues et libère toutes les allocations inutilisées (c'est-à-dire non marquées), retourne à gc_run() et le monde continue de fonctionner.
gc conservera les allocations de mémoire accessibles et collectera tout le reste. Une allocation est considérée comme accessible si l'une des conditions suivantes est vraie :
gc_start() (c'est-à-dire que bos est la plus petite adresse de pile prise en compte lors de la phase de marquage).gc_*alloc() qui pointe vers le contenu d'allocation.GC_TAG_ROOT .L’algorithme naïf de marquage et de balayage s’exécute en deux étapes. Tout d'abord, lors d'une étape de marquage , l'algorithme trouve et marque toutes les allocations racines et toutes les allocations accessibles depuis les racines. Deuxièmement, lors de la phase de balayage , l'algorithme ignore toutes les allocations connues, collectant toutes les allocations qui n'ont pas été marquées et sont donc jugées inaccessibles.
Au début de l'étape de marquage , nous balayons d'abord toutes les allocations connues et trouvons des racines explicites avec le jeu de balises GC_TAG_ROOT . Chacune de ces racines est un point de départ pour un marquage récursif axé d’abord sur la profondeur.
gc détecte ensuite toutes les racines de la pile (en commençant par le pointeur de bas de pile bos transmis à gc_start() ) et les registres (en les déversant sur la pile avant la phase de marquage) et les utilise comme points de départ pour marquage également.
Étant donné une allocation racine, le marquage consiste à (1) définir le champ tag dans un objet Allocation sur GC_TAG_MARK et (2) analyser la mémoire allouée à la recherche de pointeurs vers des allocations connues, en répétant le processus de manière récursive.
L'implémentation sous-jacente est une recherche simple et récursive en profondeur qui analyse tout le contenu de la mémoire pour trouver des références potentielles :
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 );
}
}
} Dans gc.c , gc_mark() démarre le processus de marquage en marquant les racines connues sur la pile via un appel à gc_mark_roots() . Pour marquer les racines, nous effectuons un passage complet dans toutes les allocations connues. Nous procédons ensuite au dump des registres sur la pile.
Afin de rendre le contenu du registre CPU disponible pour la recherche de racine, gc les dépose sur la pile. Ceci est implémenté de manière quelque peu portable en utilisant setjmp() , qui les stocke dans une variable jmp_buf juste avant de marquer la pile :
...
/* 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 );
... Le détour par le pointeur de fonction volatile _mark_stack vers la fonction gc_mark_stack() est nécessaire pour éviter l'inline de l'appel à gc_mark_stack() .
Après avoir marqué toute la mémoire accessible et donc potentiellement encore utilisée, la collecte des allocations inaccessibles est triviale. Voici l'implémentation de 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 ;
} Nous parcourons toutes les allocations dans la carte de hachage (la boucle for ), en suivant chaque chaîne (la boucle while avec le chunk = chunk->next update) et soit (1) décochons le chunk s'il était marqué ; ou (2) appeler le destructeur sur le morceau et libérer la mémoire si elle n'a pas été marquée, en gardant un total cumulé de la quantité de mémoire que nous libérons.
Ceci conclut la course de marquage et de balayage. Le monde arrêté reprend et nous sommes prêts pour la prochaine manche !
