Quem Limpa a Memória?
Construindo um Garbage Collector do Zero em Rust

No artigo “Como closures funcionam por dentro: quando a stack não basta”, uma closure passou a ser o par { ponteiro_da_função, ponteiro_do_ambiente }. O ambiente foi criado com malloc porque precisava sobreviver ao retorno da função criadora. O problema é que nunca chamamos free.

fn cria_somador(n) {
    retorne fn(x) { retorne x + n; };
}

var soma_dez = cria_somador(10); // ambiente { n: 10 } no heap
soma_dez = nulo;                 // quem libera aquele ambiente?

O heap é uma região usada para dados cujo tempo de vida não acompanha uma única chamada. O alocador entrega um bloco; alguém precisa devolvê-lo. Esquecer de devolver causa vazamento. Devolver cedo demais cria um dangling pointer, uma referência para memória que já pode ter sido reutilizada. Devolver duas vezes corrompe o alocador.

A Pulso ainda não possui um sistema de tipos capaz de expressar ownership. Contagem de referências pareceria simples, mas closures podem apontar umas para as outras e formar ciclos. Por isso construiremos um coletor traçador: ele parte de referências sabidamente vivas e percorre o grafo.

Uma closure referencia seu ambiente. O ambiente pode guardar outra closure, um par, uma string ou futuramente uma lista. Essas referências transformam o heap em um grafo dirigido. Não basta olhar um objeto isoladamente: ele pode estar vivo porque outro objeto vivo aponta para ele.

RAÍZES
stack ───────┐
globais ─────┼──► Closure A ───► Ambiente B ───► Objeto C
registradores┘                         │
                                      └────────► Objeto D

Objeto E ───► Objeto F   // ilha sem caminho partindo das raízes

A, B, C e D permanecem. E e F são uma ilha inalcançável e podem ser liberados, mesmo que apontem um para o outro.

Uma raiz é uma referência considerada viva sem precisar ser encontrada dentro de outro objeto do heap. Na mini-VM da Pulso, as raízes naturais são os valores na stack, as variáveis globais e as closures dos frames ativos. Em um runtime nativo também podem existir referências em registradores e memória controlada pelo código gerado.

pub enum Value {
    Number(f64),
    Object(Handle), // o runtime sabe que esta variante aponta para o heap
    Nil,
}

1. Mark: comece nas raízes, marque cada objeto visitado e percorra suas referências.
2. Sweep: percorra todos os slots; mantenha os marcados e libere os não marcados.
3. Reset: apague as marcas dos sobreviventes para preparar a próxima coleta.

Nosso primeiro coletor será stop-the-world: a VM interrompe a execução enquanto coleta. Isso não quer dizer que todo GC funcione assim o tempo inteiro; significa apenas que escolhemos o contrato mais fácil de provar antes de introduzir concorrência.

pub struct Handle(pub usize);

struct Slot {
    object: Object,
    marked: bool,
}

pub struct Heap {
    slots: Vec<Option<Slot>>,
    free: Vec<usize>,
    live: usize,
}

O Handle guarda o índice de um slot. Um slot vazio entra em free e pode ser reutilizado pela próxima alocação. Assim conseguimos enxergar alocação e coleta sem depender dos detalhes internos do alocador do sistema.

pub fn allocate(&mut self, object: Object) -> Handle {
    let slot = Slot { object, marked: false };
    self.live += 1;

    if let Some(index) = self.free.pop() {
        self.slots[index] = Some(slot);
        Handle(index)
    } else {
        self.slots.push(Some(slot));
        Handle(self.slots.len() - 1)
    }
}

A lista livre evita que o vetor cresça para sempre. Em um runtime real, o heap costuma trabalhar com blocos, classes de tamanho ou páginas; aqui cada slot guarda um objeto lógico para deixar o algoritmo observável.

fn mark_value(&mut self, value: Value) {
    let Value::Object(handle) = value else { return };
    let Some(slot) = self.slots[handle.0].as_mut() else { return };

    if slot.marked { return; } // já visitado: encerra ciclos
    slot.marked = true;

    let children = match &slot.object {
        Object::Pair(a, b) => vec![*a, *b],
        Object::Closure { captures, .. } => captures.clone(),
    };

    for child in children { self.mark_value(child); }
}

Marcar antes de visitar os filhos é decisivo. Se A aponta para B e B aponta para A, a segunda chegada a A encontra marked = true e para. Conceitualmente, estamos executando uma busca em profundidade no grafo.

for (index, entry) in self.slots.iter_mut().enumerate() {
    let Some(slot) = entry else { continue };

    if slot.marked {
        slot.marked = false;       // sobrevive e prepara o próximo ciclo
    } else {
        *entry = None;             // executa Drop em Object
        self.free.push(index);     // slot poderá ser reutilizado
        self.live -= 1;
    }
}

Em nosso projeto, substituir o slot por None faz o Rust executar Drop sobre o objeto. Em uma VM baseada em blocos brutos, a varredura devolveria o bloco a uma free list ou ao alocador.

pub struct Vm {
    pub heap: Heap,
    pub stack: Vec<Value>,
    pub globals: HashMap<String, Value>,
}

impl Vm {
    pub fn roots(&self) -> Vec<Value> {
        self.stack.iter().copied()
            .chain(self.globals.values().copied())
            .collect()
    }

    pub fn collect_garbage(&mut self) -> GcReport {
        let roots = self.roots();
        self.heap.collect(roots)
    }
}

Copiamos a lista de raízes antes de emprestar o heap mutavelmente. Isso satisfaz o borrow checker e, mais importante, fotografa o conjunto inicial da coleta. Se omitíssemos globais ou um frame ativo, o GC poderia liberar um objeto ainda usado: um bug muito pior que vazamento.

Rodar depois de cada alocação é correto, porém caro. Nunca rodar volta ao vazamento. Uma política inicial pode disparar quando o número de objetos alcançar o dobro do tamanho observado após a última coleta.

if heap.live_objects() >= next_gc {
    let report = vm.collect_garbage();
    next_gc = (report.after * 2).max(64);
}

let lembranca = heap.allocate(Pair(10, nil));       // slot 0
let somador   = heap.allocate(Closure([lembranca])); // slot 1
let temporario = heap.allocate(Pair(99, nil));      // slot 2

globals["soma_dez"] = somador; // raiz → slot 1 → slot 0
collect_garbage();             // slot 2 não é alcançável

// antes: 3 objetos
// depois: 2 objetos; 1 liberado

Um teste que apenas observa “liberou alguma coisa” é insuficiente. Precisamos também verificar handles sobreviventes e caminhos indiretos. O erro mais perigoso em um GC é um falso morto: o coletor não enxergou uma raiz legítima.

Também não estamos coletando o heap do executável LLVM do artigo “Como closures funcionam por dentro: quando a stack não basta”. Para isso, o código nativo precisaria registrar roots e alocações no runtime da Pulso. O projeto deste capítulo implementa primeiro o contrato completo dentro de uma VM pequena, onde cada referência é observável.

O projeto para download contém uma biblioteca, um executável demonstrativo e testes. Rode primeiro sem alterar nada; depois faça cada experimento isoladamente.

cargo run
cargo test

# resultado esperado do exemplo
antes: 3 objetos
depois: 2 objetos; 1 liberado