Coletor de Lixo Stop-and-copy para SmallLua

O objetivo desse trabalho é trocar o coletor de lixo de SmallLua do coletor mark-sweep implementado atualmente para um coletor stop-and-copy de dois espaços, aproveitando para trocar o alocador de memória para objetos gerenciados (strings, funções, sequências e upvalues) de malloc para um alocador “bump” (alocador por incremento simples de ponteiro).

O coletor de lixo deve continuar funcionando tanto com a representação “tagged unions” quanto a representação “nanbox”, pois a escolha de representação afeta apenas como os ponteiros para os objetos gerenciados são representados, não o conteúdo deles.

O heap (uma tripla de um bloco de memória void*, a capacidade dele em bytes e quanto espaço está alocado em uma estrutura Heap) agora vai ser parte do estado do intepretador (estrutura State). Escreva um alocador void *aloca(Heap *heap, size_t len) que reserva os próximos len bytes do heap e retorna um ponteiro para ele, caso o heap ainda tenha capacidade. Caso o heap não tenha mais espaço a função retorna NULL.

Mude as funções new_string, new_function, new_sequence e new_upvalue para usar o novo alocador. Por enquanto elas devem retornar NULL caso a tentativa de alocação falhe, depois que o novo coletor estiver escrito ela tentará uma coleta antes de uma segunda tentativa, e só retornar NULL caso a segunda tentativa falhe. Mude a função new_state para alocar o heap inicial. Comente o corpo atual da função gc e certifique-se de que o interpretador está funcionando com o novo alocador, contanto que você dê um heap suficiente para a execução do programa.

No coletor mark-sweep, todos os objetos gerenciados têm como prefixo uma estrutura GCValue que contém a marca (usada na fase mark) e a ligação com o objeto anteriormente alocado no heap (usado para a fase sweep). O coletor stop-and-copy não precisa da marca e da ligação, mas vai precisar de um flag que indica se o que está no heap ainda é o objeto ou é um ponteiro para um objeto que já foi movido. Crie uma estrutura Forward para representar esse ponteiro.

Agora você está pronto para escrever a nova implementação da função gc. Ela irá alocar um novo heap para ser o destino da cópia. Escreva uma função void copy_value(Heap *to, Value *val) que irá copiar o valor para o novo heap caso ele seja um valor gerenciado que ainda não tenha sido copiado.

A função copy_value não faz nada se o valor não for um valor gerenciado. Se ele já for um forwarding pointer ela reescreve o ponteiro em val para apontar para o novo endereço. Se for uma string ela aloca uma nova string igual à primeira no novo heap, deixa um forwarding pointer no lugar da string antiga, e reescreve o ponteiro em val para apontar para o nova string. Se ele for uma função ela aloca uma nova função com base no mesmo protótipo e copia os upvalues do display para o novo heap, também deixando um forwarding pointer no lugar da função antiga. Se ele for uma sequência aloca uma nova sequência com o mesmo tamanho e copia recursivamente os valores da sequência antiga para o novo heap, preenchendo a nova sequência, e deixando um forwarding pointer no lugar da sequência antiga.

Para copiar os upvalues você pode fazer uma função auxiliar Upvalue *copy_upvalue(Heap *to, Upvalue *upval) que retorna o novo endereço caso upval seja na verdade um forwarding pointer, ou aloca um upvalue no novo heap, copia recursivamente o valor guardado no upvalue, deixa um forwarding pointer no endereço antigo e retorna o novo endereço.

Agora a coleta de lixo é uma questão de percorrer toda a pilha e as tabelas de constantes dos protótipos chamando copy_value para cada valor. Depois disso o heap antigo pode ser liberado, e o novo heap passa a ser o heap guardado em State.

Uma maneira de fazer um “teste de stress” do coletor de lixo é rodá-lo antes de cada alocação, ao invés de apenas quando o espaço do heap termina. Inclua uma opção em tempo de compilação para fazer isso.

Uma otimização simples é, ao invés de liberar o heap antigo após cada coleta de lixo, manter esse heap para ser usado como heap novo na próxima coleta, evitando uma alocação de um novo heap. Implemente essa otimização.


Última Atualização: 2016-12-05 17:40