gc
1.0.0
gc é uma implementação de um coletor de lixo conservador, thread-local e de marcação e varredura. A implementação fornece um substituto totalmente funcional para as chamadas padrão POSIX malloc() , calloc() , realloc() e free() .
O foco do gc é fornecer uma implementação conceitualmente limpa de um GC mark-and-sweep, sem se aprofundar na otimização específica da arquitetura (veja, por exemplo, o GC Boehm para tal empreendimento). Deve ser particularmente adequado para fins de aprendizagem e está aberto a todos os tipos de otimização (RPs bem-vindos!).
A motivação original para gc é meu desejo de escrever meu próprio LISP em C, inteiramente do zero - e isso exigia coleta de lixo.
Este trabalho não teria sido possível sem a capacidade de ler o trabalho de outros, mais notavelmente o Boehm GC, o tgc do orangeduck (que também segue os ideais de ser pequeno e simples) e o The Garbage Collection Handbook.
gc . $ git clone [email protected]:mkirchner/gc.git
$ cd gc
Para compilar usando o compilador clang :
$ make test
Para usar a coleção de compiladores GNU (GCC):
$ make test CC=gcc
Os testes devem ser concluídos com sucesso. Para criar o relatório de cobertura atual:
$ 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 ;
} Isto descreve a API principal, consulte gc.h para obter mais detalhes e a API de baixo nível.
Para inicializar e iniciar a coleta de lixo, use a função gc_start() e passe um endereço no final da pilha :
void gc_start ( GarbageCollector * gc , void * bos ); O parâmetro bos na parte inferior da pilha precisa apontar para uma variável alocada na pilha e marcar a extremidade inferior da pilha de onde começa a localização da raiz (verificação).
A coleta de lixo pode ser interrompida, pausada e retomada com
void gc_stop ( GarbageCollector * gc );
void gc_pause ( GarbageCollector * gc );
void gc_resume ( GarbageCollector * gc );e a coleta manual de lixo pode ser acionada com
size_t gc_run ( GarbageCollector * gc ); gc suporta alocação de memória no estilo malloc() , calloc() e realloc() . As respectivas assinaturas de função imitam as funções POSIX (com a exceção de que precisamos passar o coletor de lixo como primeiro 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 );É possível passar um ponteiro para uma função destruidora através da interface estendida:
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 oferece suporte a alocações estáticas que são coletadas como lixo somente quando o GC é encerrado por meio de gc_stop() . Basta usar a função auxiliar apropriada:
void * gc_malloc_static ( GarbageCollector * gc , size_t size , void ( * dtor )( void * )); A alocação estática espera um ponteiro para uma função de finalização; apenas defina como NULL se a finalização não for necessária.
Observe que gc atualmente não garante uma ordem específica ao coletar variáveis estáticas. Se vars estáticos precisarem ser desalocados em uma ordem específica, o usuário deve chamar gc_free() neles na sequência desejada antes de chamar gc_stop() , veja abaixo .
Também é possível acionar a desalocação explícita de memória usando
void gc_free ( GarbageCollector * gc , void * ptr ); Chamar gc_free() é garantido para (a) finalizar/destruir o objeto apontado por ptr se aplicável e (b) liberar a memória para a qual ptr aponta, independentemente do agendamento atual para coleta de lixo e também funcionará se o GC tiver sido pausado usando gc_pause() acima.
gc também oferece uma implementação strdup() que retorna uma cópia coletada como lixo:
char * gc_strdup ( GarbageCollector * gc , const char * s );A ideia fundamental por trás da coleta de lixo é automatizar o ciclo de alocação/desalocação de memória. Isso é feito controlando toda a memória alocada e acionando periodicamente a desalocação da memória que ainda está alocada, mas inacessível.
Muitos coletores de lixo avançados também implementam sua própria abordagem para alocação de memória (ou seja, substituam malloc() ). Isso geralmente permite que eles organizem a memória de maneira mais eficiente em termos de espaço ou para acesso mais rápido, mas tem o preço de implementações específicas de arquitetura e de maior complexidade. gc evita esses problemas recorrendo às implementações POSIX *alloc() e mantendo o gerenciamento de memória e os metadados de coleta de lixo separados. Isso torna gc muito mais simples de entender, mas, é claro, também menos eficiente em termos de espaço e tempo do que abordagens mais otimizadas.
A estrutura de dados principal dentro gc é um mapa hash que mapeia o endereço da memória alocada para os metadados da coleta de lixo dessa memória:
Os itens no mapa hash são alocações, modeladas com a 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 instância Allocation contém um ponteiro para a memória alocada, o tamanho da memória alocada naquele local, uma tag para marcar e varrer (veja abaixo), um ponteiro opcional para a função destruidora e um ponteiro para a próxima instância Allocation ( para encadeamento separado, veja abaixo).
As alocações são coletadas em um 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 com um conjunto de funções static dentro de gc.c , fornece semântica de mapa hash para a implementação da API pública.
O AllocationMap é a estrutura de dados central na estrutura GarbageCollector que faz parte da API pública:
typedef struct GarbageCollector {
struct AllocationMap * allocs ;
bool paused ;
void * bos ;
size_t min_size ;
} GarbageCollector ; Com as estruturas de dados básicas implementadas, qualquer solicitação de alocação de memória gc_*alloc() é um procedimento de duas etapas: primeiro, aloque a memória por meio da funcionalidade do sistema (ou seja, malloc() padrão) e, segundo, adicione ou atualize os metadados associados ao mapa hash.
Para gc_free() , use o ponteiro para localizar os metadados no mapa hash, determine se a desalocação requer uma chamada de destruidor, chame se necessário, libere a memória gerenciada e exclua a entrada de metadados do mapa hash.
Essas estruturas de dados e as interfaces associadas permitem o gerenciamento dos metadados necessários para construir um coletor de lixo.
gc aciona a coleta em duas circunstâncias: (a) quando qualquer uma das chamadas para a alocação do sistema falha (na esperança de desalocar memória suficiente para atender à solicitação atual); e (b) quando o número de entradas no mapa hash ultrapassa um limite máximo ajustado dinamicamente.
Se qualquer um desses casos ocorrer, gc para o mundo e inicia uma coleta de lixo de marcação e varredura em todas as alocações atuais. Esta funcionalidade é implementada na função gc_run() que faz parte da API pública e delega todo o trabalho às funções gc_mark() e gc_sweep() que fazem parte da API privada.
gc_mark() tem a tarefa de encontrar raízes e marcar todas as alocações conhecidas que são referenciadas a partir de uma raiz (ou de uma alocação que é referenciada a partir de uma raiz, ou seja, transitivamente) como "usadas". Assim que a marcação for concluída, gc_sweep() itera sobre todas as alocações conhecidas e desaloca todas as alocações não utilizadas (ou seja, não marcadas), retorna para gc_run() e o mundo continua a funcionar.
gc manterá as alocações de memória acessíveis e coletará todo o resto. Uma alocação é considerada alcançável se alguma das seguintes afirmações for verdadeira:
gc_start() (ou seja, bos é o menor endereço de pilha considerado durante a fase de marcação).gc_*alloc() que aponta para o conteúdo da alocação.GC_TAG_ROOT .O algoritmo ingênuo de marcar e varrer é executado em dois estágios. Primeiro, numa fase de marcação , o algoritmo encontra e marca todas as alocações de raiz e todas as alocações que são acessíveis a partir das raízes. Segundo, na fase de varredura , o algoritmo passa por todas as alocações conhecidas, coletando todas as alocações que não foram marcadas e são, portanto, consideradas inacessíveis.
No início do estágio de marcação , primeiro varremos todas as alocações conhecidas e encontramos raízes explícitas com o conjunto de tags GC_TAG_ROOT . Cada uma dessas raízes é um ponto de partida para a marcação recursiva em profundidade.
gc subsequentemente detecta todas as raízes na pilha (começando pelo ponteiro inferior da pilha bos que é passado para gc_start() ) e os registradores (despejando-os na pilha antes da fase de marcação) e os usa como pontos de partida para marcação também.
Dada uma alocação raiz, a marcação consiste em (1) definir o campo tag em um objeto Allocation como GC_TAG_MARK e (2) varrer a memória alocada em busca de ponteiros para alocações conhecidas, repetindo recursivamente o processo.
A implementação subjacente é uma pesquisa simples e recursiva em profundidade que examina todo o conteúdo da memória para encontrar referências potenciais:
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 );
}
}
} Em gc.c , gc_mark() inicia o processo de marcação marcando as raízes conhecidas na pilha por meio de uma chamada para gc_mark_roots() . Para marcar as raízes fazemos uma passagem completa por todas as alocações conhecidas. Em seguida, procedemos ao descarregamento dos registros na pilha.
Para disponibilizar o conteúdo do registro da CPU para localização de raiz, gc os despeja na pilha. Isso é implementado de uma forma um tanto portátil usando setjmp() , que os armazena em uma variável jmp_buf logo antes de marcarmos a pilha:
...
/* 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 );
... O desvio usando o ponteiro de função volatile _mark_stack para a função gc_mark_stack() é necessário para evitar o inlining da chamada para gc_mark_stack() .
Depois de marcar toda a memória que está acessível e, portanto, potencialmente ainda em uso, coletar as alocações inacessíveis é trivial. Aqui está a implementação 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 ;
} Iteramos todas as alocações no mapa hash (o loop for ), seguindo cada cadeia (o loop while com o chunk = chunk->next update) e (1) desmarcamos o chunk se ele estiver marcado; ou (2) chamar o destruidor no pedaço e liberar a memória se ela não estiver marcada, mantendo um total da quantidade de memória que liberamos.
Isso conclui a corrida de marcação e varredura. O mundo parado é retomado e estamos prontos para a próxima corrida!
