Suspensão da Descrença

Seguindo a maravilhosa jornada que é ler  Crafting Interpreters, cheguei no ponto onde implementamos um interpretador em C! Como sempre, Bob Nystrom impiedosamente nos propõe desafios interessantíssimos que nos mantém ocupados por longos períodos. Por exemplo, neste capítulo ele nos sugere implementar nosso próprio alocador de memória, sem a menor necessidade! Inevitavelmente, caí na armadilha.

O desafio nos permite alocar uma grande região de memória e gerenciá-la, mas decidi implementar a função malloc() do zero. Como uso Ubuntu, foi necessário primeiramente entender melhor o layout da memória de um processo no Linux.

Considere o diagrama abaixo, que representa o layout da memória de um processo.

Na memória alocada para o processo, há várias seções. Quando o programa inicia sua execução, a parte acinzentada não está em uso ainda. Ao longo de sua execução, o programa declara variáveis locais, fazendo a stack (pilha) crescer para trás.

Já a memória dinamicamente alocada é obtida do heap, que cresce na direção oposta. A maneira bem popular de expandir o heap é aumentando o tamanho do segmento de data (i.e. a seção que contém variáveis globais e estáticas) com a chamada de sistema sbrk().

O diagrama acima ilustra como esta chamada de sistema funcional funciona. sbrk() recebe como parâmetro um número inteiro que irá ser somado ao ponteiro que indica o fim do segmento de data. Depois disso, sbrk() retorna o valor do ponteiro antes do incremento.

De certo modo, o comportamento de sbrk() já é suficiente para alocar memória. Nossa funçaõ malloc() pode simplesmente invocar sbrk() e retornar para o usuário o ponteiro para o início do bloco de memória alocada:

void *abmalloc(size_t size) {
   return sbrk(size);
 }

Em princípio, free() não precisa fazer nada: como nesta implementação sempre usamos a memória do topo do heap, não há nada que possamos fazer para reutilizar blocos de memória mais antigos. Nesse sentido, free() pode perfeitamente ser um no-op:

void abfree(void *ptr) {
}

Uma operação útil pode ser feita, porém, se o bloco a ser liberado tiver sido o último a ser alocado. Isto significa que ele está no topo da pilha, então basta mover o ponteiro do topo da pilha para o início do bloco desalocado. Para isto, primeiramente devemos saber onde começa o último bloco de memória alocado, o que é fácil com uma variável global:

void *last_block = NULL;

void *abmalloc(size_t size) {
   last_block = sbrk(size);
   return last_block;
} 

Depois, na função free(), verificamos se o ponteiro passado aponta para o último bloco. Neste caso, movemos o topo da pilha para trás com a chamada de sistema brk(). Esta syscall recebe como parâmetro um ponteiro e, se este ponteiro é um valor “razoável” (não é nulo, não aponta para dentro da stack, não aponta para antes do heap), usa o valor do ponteiro como novo topo do heap. O resultado seria algo assim.

void abfree(void *ptr) {
  if (ptr == last_block) {
      brk(last_block);
  }
}

Esta desalocação, porém, é inútil na prática. Considere o exemplo abaixo:

void *ptr1 = abmalloc(8);
void *ptr2 = abmalloc(8);
abfree(ptr2);
abfree(ptr1);

Com a versão atual de abfree(), conseguimos liberar a memória apontada por ptr1, mas não a apontada por ptr2. Para poder liberar ptr2, seria preciso saber que, uma vez que ptr1 foi desalocada, o próximo último bloco é ptr2. Poderíamos criar uma variável second_last_block? Não adiantaria: teríamos o mesmo problema com o antepenúltimo bloco, e assim por diante.

Precisamos de uma estrutura de dados mais poderosa aqui, e é isto que veremos no nosso próximo post.