Quando um programa interpretado roda, ele cria objetos o tempo todo: strings, listas, frames, funções. Em algum momento, alguns desses objetos deixam de ser necessários, mas o programa não avisa isso para a máquina virtual.
A pergunta central que um Garbage Collector responde é:
Como saber quais objetos podem ser liberados da memória?
Existem várias respostas possíveis — contagem de referências, coleção generacional, tri-color marking… Neste artigo vamos estudar o Mark and Sweep, o algoritmo usado no runtime da minha linguagem, a Drax. Vamos entender o conceito de forma geral e depois mergulhar na implementação real: como as raízes são encontradas, como a marcação funciona e como a varredura libera objetos.
Todo programa dinâmico aloca memória em tempo de execução. Em uma linguagem interpretada como o Drax, quando você escreve:
nome = "drax"
uma string é criada no heap e referenciada por uma variável. O mesmo acontece para listas, frames, funções e qualquer outro valor composto.
Durante a execução, o programa mantém um conjunto de objetos que ainda são utilizados — objetos alcançáveis a partir de pontos de entrada conhecidos. Outros objetos podem se tornar inalcançáveis: a referência foi sobrescrita, saiu de escopo ou foi atribuída para nil.
flowchart LR
Root --> A[Objeto A]
A --> B[Objeto B]
Root --> C[Objeto C]
D[Objeto Inalcançável]
E[Objeto Inalcançável]
A, B e C são alcançáveis a partir de Root. D e E são inalcançáveis: nenhuma raiz nem nenhum objeto vivo aponta para eles.
Por que simplesmente "liberar objetos antigos" não funciona? Porque idade não é o critério: um objeto criado no início do programa pode estar vivo até o fim, e um objeto recém-criado pode ser descartado imediatamente. O critério correto é alcançabilidade — se um objeto pode ser alcançado a partir de um ponto de entrada do programa, ele está vivo.
O Mark and Sweep resolve esse problema em duas fases:
flowchart TB
Mark[MARK<br/>Marca objetos alcançáveis] --> Sweep[SWEEP<br/>Libera objetos não marcados]
O GC começa pelas raízes e percorre o grafo de objetos a partir delas. Todo objeto alcançado é marcado como vivo. Nada é liberado nesta fase.
Depois da marcação, o GC percorre todos os objetos alocados. Os que não foram marcados são inalcançáveis e podem ser liberados. Os marcados são desmarcados para o próximo ciclo.
flowchart TB
Root[Raízes] --> Mark[Marcar alcançáveis]
Mark --> Objects{Objetos no heap}
Objects -- marcado --> Keep[Manter vivo]
Objects -- não marcado --> Free[Liberar]
A marcação precisa começar de algum lugar. Os pontos de entrada para o grafo de objetos são chamados de GC Roots. Se um objeto não for alcançável a partir de nenhuma raiz, ele está morto.
Quais estruturas realmente funcionam como raízes no Drax?
As raízes estão todas no ambiente de execução (d_vm) e são varridas pela função dgc_swap no src/dgc.c:
| Raiz | Estrutura | O que guarda |
|---|---|---|
| Variáveis locais | vm->envs->local |
Variáveis locais de funções em execução |
| Variáveis globais | vm->envs->global |
Variáveis globais (tabela hash com encadeamento) |
| Funções nativas | vm->envs->native |
Funções built-in registradas |
| Módulos | vm->envs->modules |
Módulos nativos (Core, List, String, …) |
| Pilha de operandos | vm->stack |
Valores intermediários da VM |
| Instruction Pointer | vm->ip |
Stream de bytecode atual — as constantes embutidas no código |
| Call stack | vm->call_stack->frames |
Frames de chamada: bytecode de cada frame e seu ambiente global |
| Exportado | vm->exported[0] |
Valor exportado pela execução |
flowchart TD
VM[VM — d_vm] --> Locals[envs->local<br/>Variáveis locais]
VM --> Globals[envs->global<br/>Variáveis globais]
VM --> Native[envs->native<br/>Funções nativas]
VM --> Modules[envs->modules<br/>Módulos]
VM --> Stack[stack<br/>Pilha de operandos]
VM --> IP[ip<br/>Bytecode atual]
VM --> CallStack[call_stack->frames<br/>Call stack]
VM --> Exported["exported[0]"]
Locals --> GC[dgc_swap]
Globals --> GC
Native --> GC
Modules --> GC
Stack --> GC
IP --> GC
CallStack --> GC
Exported --> GC
Exemplo na implementação, dgc_swap chama:
dgc_swap_locals(vm->envs->local);
dgc_swap_generic_table(vm->envs->global);
dgc_swap_native(vm->envs->native);
dgc_swap_modules(vm->envs->modules);
dgc_swap_stack(vm);
dgc_swap_ip(vm->ip);
dgc_swap_call_stack(vm);
dgc_swap_exported(vm);
Com as raízes identificadas, a marcação percorre o grafo a partir delas. Considere o grafo abaixo:
flowchart TD
Root --> A[Objeto A]
A --> B[Objeto B]
A --> C[Objeto C]
C --> D[Objeto D]
no Drax, a marcação é feita por dgc_mark. Ela marca o objeto atual (checked = 1) e desce recursivamente pelos filhos:
static void dgc_mark(drax_value v) {
if (v == 0) return;
if IS_STRUCT(v) {
CAST_STRUCT(v)->checked = 1;
/* se for list, marca todos os elementos */
if (IS_LIST(v)) {
drax_list* l = CAST_LIST(v);
int i;
for (i = 0; i < l->length; i++) {
dgc_mark(l->elems[i]);
}
} else if (IS_FRAME(v)) {
drax_frame* f = CAST_FRAME(v);
int i;
for (i = 0; i < f->length; i++) {
dgc_mark(f->values[i]);
}
} else if (IS_FUNCTION(v)) {
drax_function* f = CAST_FUNCTION(v);
int i;
for (i = 0; i < f->instructions->instr_count; i++) {
if (f->instructions->values[i] == v) continue;
dgc_mark(f->instructions->values[i]);
}
}
}
}
No exemplo, o GC visita A, depois B, C e D, marcando todos como vivos. Se existisse um E não referenciado por ninguém, ele permaneceria desmarcado — candidato à coleta.
A marcação é a estrutura mais simples do algoritmo: um grafo percorrido a partir das raízes. Não há necessidade de saber quem alocou cada objeto — basta alcançabilidade.
Depois que os objetos alcançáveis foram marcados, o GC percorre todos os objetos existentes no heap. Os marcados são mantidos; os não marcados são coletados.
flowchart LR
Heap --> A[Marcado]
Heap --> B[Marcado]
Heap --> C[Não marcado]
Heap --> D[Não marcado]
C --> E[Coletar]
D --> E
no Drax, todos os objetos ficam em uma lista ligada onde o inicio é vm->d_ls. O sweep percorre essa lista:
while (d != NULL) {
if (d->checked) {
d->checked = 0; /* desmarca para o próximo ciclo */
p = d;
d = d->next;
} else {
u = d;
d = d->next;
p->next = d; /* remove da lista */
dgc_safe_free(vm, DS_VAL(u)); /* libera de fato */
}
}
Perceba o papel do flag checked:
checked = 1 nos alcançáveis.checked dos vivos (para o próximo ciclo começar limpo) e libera os mortos.Agora vamos ver como tudo isso se conecta na implementação real. o Drax é um interpretador dinâmico escrito em C, com uma VM de bytecode. Aqui está o ciclo de vida dos objetos.
Todo valor composto do Drax é um d_struct — um cabeçalho comum com type, o flag checked e o ponteiro next:
typedef struct d_struct {
dstruct_type type;
bool checked;
struct d_struct* next;
} d_struct;
Os tipos reais derivam desse cabeçalho: DS_LIST, DS_FUNCTION, DS_NATIVE, DS_STRING, DS_FRAME, DS_MODULE, DS_ERROR, DS_TID.
A alocação acontece em dstructs.c, na função allocate_struct. Todo objeto novo é inserido no início da lista ligada do heap:
static d_struct* allocate_struct(d_vm* vm, size_t size, dstruct_type type, int is_orphan) {
d_struct* d = (d_struct*) malloc(sizeof(d_struct) * size);
d->type = type;
d->checked = 0;
if (!is_orphan) {
d->next = vm->d_ls;
vm->d_ls = d;
}
return d;
}
Ou seja: o "heap" do Drax é a lista ligada com inicio em vm->d_ls. O GC não precisa de uma estrutura separada para encontrar os objetos — ela é a estrutura.
flowchart LR
Head[vm->d_ls] --> S1[Objeto<br/>checked=0]
S1 --> S2[Objeto<br/>checked=0]
S2 --> S3[Objeto<br/>checked=1]
S3 --> End[NULL]
o Drax usa NaN-boxing: um valor drax_value é um uint64_t. Números são codificados diretamente no próprio valor; ponteiros para d_struct carregam bits de marcação. Macros como IS_STRUCT, IS_NUMBER, CAST_STRUCT e DS_VAL fazem essa conversão. Isso explica por que o GC primeiro testa if (v == 0) e if (v == 0) return; — valores não-estrutura não interessam à coleta.
Como vimos na seção 3, as raízes são varridas dentro de dgc_swap: locais, globais, nativas, módulos, pilha de operandos, bytecode (ip), call stack e o valor exportado.
dgc_mark marca checked = 1 e recorre pelos filhos conforme o tipo: elementos de listas (elems), valores de frames (values) e constantes de funções (instructions->values, pulando auto-referências).
dgc_swap percorre vm->d_ls: se checked está ativo, o objeto é desmarcado e mantido; caso contrário, é removido da lista e liberado.
A liberação é feita por dgc_safe_free, que desce no tipo do objeto e libera apenas o que foi alocado:
if (IS_STRING(v)) {
drax_string* s = CAST_STRING(v);
if (NULL != s->chars) { free(s->chars); s->chars = NULL; }
} else if (IS_ERROR(v)) {
drax_error* e = CAST_ERROR(v);
if (NULL != e->chars) { free(e->chars); e->chars = NULL; }
} else if (IS_FRAME(v)) {
drax_frame* f = CAST_FRAME(v);
free(f->keys);
free(f->values);
} else if (IS_FUNCTION(v)) {
drax_function* ff = CAST_FUNCTION(v);
free(ff->instructions->values);
free(ff->instructions->extrn_ref);
free(ff->instructions);
}
free(sct);
Cada objeto coletado incrementa vm->gc_meta->n_free_structs, um dos contadores expostos pela VM.
Na implementação atual do Drax, a coleta não é disparada por um limite de memória. Ela acontece em dois momentos:
Core.gc_swap(), que chama dgc_swap(vm) diretamente;__run__/__irun__ chamam dgc_swap(vm) para a VM principal (vid == -1).O mesmo dgc_meta guarda num_cycles e num_free_structs, consultáveis via Core.gc_meta_info() — exatamente o que o teste real de GC faz (tests/drax/gc.dx).
Um exemplo com código Drax, seguindo o padrão do teste de garbage collector da linguagem:
## objetos que serão coletados
"descartado"
"descartado"
## frame em uso — referenciado pela variável local
mp = {
a: "em uso",
b: "em uso"
}
## frame descartado — perde a referência
mp2 = {
a: "descartado2",
b: "descartado3"
}
mp2 = nil
## dispara a coleta manualmente
Core.gc_swap()
## consulta o que foi feito
info = Core.gc_meta_info()
print(info.num_cycles)
print(info.num_free_structs)
Quando Core.gc_swap() roda, os literais "descartado" continuam vivos porque estão embutidos no bytecode (a raiz ip). O frame mp e suas strings estão vivos via variável local. Já o frame mp2 foi atribuído para nil, então ele e suas duas strings se tornam inalcançáveis — são marcados como não marcados e coletados no sweep.
O GC não é um componente isolado. Ele faz parte do runtime: a VM mantém as raízes, os objetos e as estatísticas, e o GC apenas percorre essas estruturas. no Drax, toda a interação acontece em torno do d_vm:
flowchart TD
Source[Programa] --> VM[VM — d_vm]
subgraph Runtime
VM --> Objects[Objetos — vm->d_ls]
VM --> Roots[Raízes — envs, stack, ip, call stack]
Objects --> GC[GC — dgc_swap]
Roots --> GC
end
GC --> Meta[gc_meta — ciclos e liberados]
GC --> Mark[MARK — dgc_mark]
Mark --> Sweep[SWEEP — lista ligada]
Sweep --> Memory[Libera memória — dgc_safe_free]
Repare no fluxo: o GC lê as raízes do d_vm, marca os objetos alcançáveis da lista vm->d_ls, varre a lista e libera os mortos, atualizando gc_meta. A VM participa em todos os pontos: ela é quem cria os objetos, mantém as raízes e expõe a coleta via Core.gc_swap().
Falando de forma teórica (não apliquei nenhum benchmarks no projeto):
Custo do Mark: proporcional ao número de objetos e arestas alcançáveis, O(E), onde E é o total de referências percorridas a partir das raízes.
Custo do Sweep: proporcional ao número total de objetos alocados, O(N) sobre a lista ligada vm->d_ls.
Impacto de percorrer o grafo: a cada ciclo, todo o grafo vivo é visitado de novo. Quanto mais objetos vivos, mais caro fica o ciclo.
Vantagens do Mark and Sweep:
Simples de implementar corretamente, como no Drax, precisa só de um flag checked e de uma lista de objetos.
Não depende de contadores de referência, então trata ciclos naturalmente: um ciclo inalcançável não vaza.
Consegue "se livrar" de tudo o que for inalcançável em um único ciclo.
Limitações:
Fragmentação: o sweep libera objetos individuais, mas não compacta o heap. A memória disponível fica espalhada em blocos, o que pode prejudicar alocações grandes.
Pausas (stop-the-world): durante a coleta, a VM para. no Drax, como a coleta é manual (Core.gc_swap()) e no fim da execução, o impacto é controlado pelo desenvolvedor, mas um runtime que colete automaticamente durante a execução pagaria esse custo em pausas.
O Mark and Sweep transforma a pergunta "quais objetos devo liberar?" em uma pergunta de alcançabilidade:
Se um objeto pode ser alcançado a partir das raízes, ele continua vivo. Caso contrário, pode ser coletado.
flowchart LR
Roots[Raízes] --> Mark[MARK]
Mark --> Reachable[Objetos alcançáveis]
Reachable --> Sweep[SWEEP]
Sweep --> Reclaim[Libera inalcançáveis]
No Drax, isso é tangível: o d_vm mantém as raízes e a lista de objetos, dgc_mark percorre o grafo marcando checked, dgc_swap varre vm->d_ls liberando o que não foi marcado e dgc_safe_free devolve a memória — sempre com os contadores de gc_meta refletindo o que aconteceu.
Entender esse fluxo — raízes → marcação → varredura → liberação — é a base para discutir qualquer coletor mais avançado, como generacional ou incremental. E ver isso funcionando em um runtime real, da alocação ao free, é o que transforma o conceito em engenharia.