gc
1.0.0
gc es una implementación de un recolector de basura conservador, local de subprocesos y de marcado y barrido. La implementación proporciona un reemplazo completamente funcional para las llamadas estándar POSIX malloc() , calloc() , realloc() y free() .
El objetivo de gc es proporcionar una implementación conceptualmente limpia de un GC de marcado y barrido, sin profundizar en las profundidades de la optimización específica de la arquitectura (consulte, por ejemplo, Boehm GC para tal tarea). Debería ser especialmente adecuado para fines de aprendizaje y está abierto a todo tipo de optimización (¡los RP son bienvenidos!).
La motivación original para gc es mi deseo de escribir mi propio LISP en C, completamente desde cero, y eso requería recolección de basura.
Este trabajo no habría sido posible sin la capacidad de leer el trabajo de otros, en particular el Boehm GC, el tgc de orangeduck (que también sigue los ideales de ser pequeño y simple) y The Garbage Collection Handbook.
gc . $ git clone [email protected]:mkirchner/gc.git
$ cd gc
Para compilar usando el compilador clang :
$ make test
Para utilizar la Colección de compiladores GNU (GCC):
$ make test CC=gcc
Las pruebas deberían completarse con éxito. Para crear el informe de cobertura actual:
$ 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 ;
} Esto describe la API principal; consulte gc.h para obtener más detalles y la API de bajo nivel.
Para inicializar e iniciar la recolección de basura, use la función gc_start() y pase una dirección al final de la pila :
void gc_start ( GarbageCollector * gc , void * bos ); El parámetro bos de la parte inferior de la pila debe apuntar a una variable asignada a la pila y marca el extremo inferior de la pila desde donde comienza la búsqueda (escaneo) de raíz.
La recolección de basura se puede detener, pausar y reanudar con
void gc_stop ( GarbageCollector * gc );
void gc_pause ( GarbageCollector * gc );
void gc_resume ( GarbageCollector * gc );y la recolección manual de basura se puede activar con
size_t gc_run ( GarbageCollector * gc ); gc admite la asignación de memoria de estilo malloc() , calloc() y realloc() . Las firmas de funciones respectivas imitan las funciones POSIX (con la excepción de que necesitamos pasar el recolector de basura como primer argumento):
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 posible pasar un puntero a una función destructora a través de la interfaz extendida:
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 admite asignaciones estáticas que se recolectan como basura solo cuando el GC se apaga mediante gc_stop() . Simplemente use la función auxiliar adecuada:
void * gc_malloc_static ( GarbageCollector * gc , size_t size , void ( * dtor )( void * )); La asignación estática espera un puntero a una función de finalización; simplemente configúrelo en NULL si no se requiere la finalización.
Tenga en cuenta que gc actualmente no garantiza un orden específico cuando recopila variables estáticas. Si es necesario desasignar las variables estáticas en un orden particular, el usuario debe llamar gc_free() en ellas en la secuencia deseada antes de llamar gc_stop() , consulte a continuación .
También es posible activar la desasignación de memoria explícita usando
void gc_free ( GarbageCollector * gc , void * ptr ); Se garantiza que llamar a gc_free() (a) finalizará/destruirá el objeto señalado por ptr si corresponde y (b) liberará la memoria a la que apunta ptr independientemente de la programación actual para la recolección de basura y también funcionará si GC ha sido pausado usando gc_pause() arriba.
gc también ofrece una implementación strdup() que devuelve una copia recolectada como basura:
char * gc_strdup ( GarbageCollector * gc , const char * s );La idea fundamental detrás de la recolección de basura es automatizar el ciclo de asignación/desasignación de memoria. Esto se logra realizando un seguimiento de toda la memoria asignada y activando periódicamente la desasignación de la memoria que todavía está asignada pero es inalcanzable.
Muchos recolectores de basura avanzados también implementan su propio enfoque para la asignación de memoria (es decir, reemplazan malloc() ). Esto a menudo les permite diseñar la memoria de una manera más eficiente en cuanto a espacio o para un acceso más rápido, pero tiene el precio de implementaciones específicas de la arquitectura y una mayor complejidad. gc evita estos problemas recurriendo a las implementaciones POSIX *alloc() y manteniendo separados los metadatos de administración de memoria y recolección de basura. Esto hace que gc sea mucho más simple de entender pero, por supuesto, también menos eficiente en espacio y tiempo que los enfoques más optimizados.
La estructura de datos central dentro de gc es un mapa hash que asigna la dirección de la memoria asignada a los metadatos de recolección de basura de esa memoria:
Los elementos del mapa hash son asignaciones, modeladas con 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 ; Cada instancia Allocation contiene un puntero a la memoria asignada, el tamaño de la memoria asignada en esa ubicación, una etiqueta para marcar y barrer (ver más abajo), un puntero opcional a la función destructora y un puntero a la siguiente instancia Allocation ( para encadenamiento por separado, ver más abajo).
Las asignaciones se recogen en 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 ; que, junto con un conjunto de funciones static dentro de gc.c , proporciona semántica de mapa hash para la implementación de la API pública.
AllocationMap es la estructura de datos central en la estructura GarbageCollector que forma parte de la API pública:
typedef struct GarbageCollector {
struct AllocationMap * allocs ;
bool paused ;
void * bos ;
size_t min_size ;
} GarbageCollector ; Con las estructuras de datos básicas implementadas, cualquier solicitud de asignación de memoria gc_*alloc() es un procedimiento de dos pasos: primero, asignar la memoria a través de la funcionalidad del sistema (es decir, malloc() estándar) y segundo, agregar o actualizar los metadatos asociados a la mapa hash.
Para gc_free() , use el puntero para ubicar los metadatos en el mapa hash, determine si la desasignación requiere una llamada al destructor, llame si es necesario, libere la memoria administrada y elimine la entrada de metadatos del mapa hash.
Estas estructuras de datos y las interfaces asociadas permiten la gestión de los metadatos necesarios para crear un recolector de basura.
gc desencadena la recopilación en dos circunstancias: (a) cuando falla alguna de las llamadas a la asignación del sistema (con la esperanza de desasignar suficiente memoria para cumplir con la solicitud actual); y (b) cuando el número de entradas en el mapa hash supera una marca máxima ajustada dinámicamente.
Si ocurre cualquiera de estos casos, gc detiene el mundo e inicia una recolección de basura de marcado y barrido sobre todas las asignaciones actuales. Esta funcionalidad se implementa en la función gc_run() que forma parte de la API pública y delega todo el trabajo a las funciones gc_mark() y gc_sweep() que forman parte de la API privada.
gc_mark() tiene la tarea de encontrar raíces y etiquetar todas las asignaciones conocidas a las que se hace referencia desde una raíz (o desde una asignación a la que se hace referencia desde una raíz, es decir, de forma transitiva) como "usadas". Una vez que se completa el marcado, gc_sweep() itera sobre todas las asignaciones conocidas y desasigna todas las asignaciones no utilizadas (es decir, sin marcar), regresa a gc_run() y el mundo continúa ejecutándose.
gc mantendrá las asignaciones de memoria accesibles y recopilará todo lo demás. Una asignación se considera alcanzable si se cumple alguna de las siguientes condiciones:
gc_start() (es decir, bos es la dirección de pila más pequeña considerada durante la fase de marca).gc_*alloc() que apunta al contenido asignado.GC_TAG_ROOT .El ingenuo algoritmo de marcar y barrer se ejecuta en dos etapas. Primero, en una etapa de marca , el algoritmo encuentra y marca todas las asignaciones de raíces y todas las asignaciones a las que se puede acceder desde las raíces. En segundo lugar, en la etapa de barrido , el algoritmo pasa por alto todas las asignaciones conocidas y recopila todas las asignaciones que no fueron marcadas y, por lo tanto, se consideran inalcanzables.
Al comienzo de la etapa de marca , primero barremos todas las asignaciones conocidas y encontramos raíces explícitas con la etiqueta GC_TAG_ROOT establecida. Cada una de estas raíces es un punto de partida para el marcado recursivo en profundidad.
Posteriormente, gc detecta todas las raíces en la pila (comenzando desde el puntero bos de la parte inferior de la pila que se pasa a gc_start() ) y los registros (volcándolos en la pila antes de la fase de marca) y los utiliza como puntos de partida para marcado también.
Dada una asignación raíz, el marcado consiste en (1) establecer el campo tag en un objeto Allocation en GC_TAG_MARK y (2) escanear la memoria asignada en busca de punteros a asignaciones conocidas, repitiendo el proceso de forma recursiva.
La implementación subyacente es una búsqueda en profundidad simple y recursiva que escanea todo el contenido de la memoria para encontrar referencias potenciales:
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 );
}
}
} En gc.c , gc_mark() inicia el proceso de marcado marcando las raíces conocidas en la pila mediante una llamada a gc_mark_roots() . Para marcar las raíces hacemos una pasada completa por todas las asignaciones conocidas. Luego procedemos a volcar los registros en la pila.
Para que el contenido del registro de la CPU esté disponible para la búsqueda de root, gc los descarga en la pila. Esto se implementa de una manera algo portátil usando setjmp() , que los almacena en una variable jmp_buf justo antes de marcar la pila:
...
/* 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 );
... El desvío utilizando el puntero de función volatile _mark_stack a la función gc_mark_stack() es necesario para evitar la inserción de la llamada a gc_mark_stack() .
Después de marcar toda la memoria accesible y, por lo tanto, potencialmente todavía en uso, recopilar las asignaciones inalcanzables es trivial. Aquí está la implementación 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 ;
} Repetimos todas las asignaciones en el mapa hash (el bucle for ), siguiendo cada cadena (el bucle while con el chunk = chunk->next actualización) y (1) desmarcamos el fragmento si estaba marcado; o (2) llamar al destructor en el fragmento y liberar la memoria si no estaba marcada, manteniendo un total acumulado de la cantidad de memoria que liberamos.
Esto concluye la carrera de marcar y barrer. ¡El mundo detenido se reanuda y estamos listos para la siguiente carrera!
