Suspensão da Descrença

Este post faz parte de uma série sobre como implementar as funções malloc() e free(). Anteriormente, fizemos uma implementação são simplória que praticamente não libera memória nenhuma: um ponteiro aponta para o último bloco alocado, o que permite que abfree() o desaloque, mas somente ele.

Uma opção melhor é fazer o último bloco apontar para o penúltimo, o penúltimo para o antepenúltimo e assim por diante, formando uma lista ligada. Para isso, criamos uma struct que servirá como cabeçalho dos blocos, contendo um ponteiro para o bloco anterior:

typedef struct Header {
  struct Header *previous;
} Header;

Além disso, o ponteiro para o último bloco, que era do tipo void*, agora é do tipo Header*:

Header *last = NULL;

Para usar esses cabeçalhos, abmalloc() reserva memória suficiente para armazenar tanto o cabeçalho quanto o tamanho solicitado:

void *abmalloc(size_t size) {
  Header *header = sbrk(sizeof(Header) + size);

Deste modo, utilizamos o início do bloco para armazenar informações necessárias, como um ponteiro para o último bloco alocado antes do novo:

  header->previous = last;

Em seguida, atualizamos last para apontar para o novo bloco:

   last = header;

Por fim, retornamos um ponteiro para a memória que o usuário pode utilizar. Como header aponta para os metadados, não podemos simplesmente retorná-lo. Caso contrário, toda informação do cabeçalho seria sobrescrita quando o usuário usasse o ponteiro! Ao invés disso, retornamos um ponteiro para logo depois do cabeçalho. Este ponteiro é fácil de calcular: é o endereço de memória do cabeçalho mais o tamanho do cabeçalho:

  return header + 1;
}

Note como incrementamos o ponteiro header em 1. Como o tipo do ponteiro é Header*, o incremento será, na verdade, o número de bytes da struct Header, não um byte apenas. Por isso, o tipo do ponteiro incrementado é muito relevante na aritmética de ponteiros.

Agora que nossos blocos de memória possuem metadados no início, é preciso levar isso em conta na hora de desalocar. free() recebe um ponteiro não para o começo do bloco, mas para a memória disponibilizada ao usuário. Logo, precisamos encontrar o começo do bloco a partir do ponteiro que o usuário passou. Nada que uma pequena aritmética de ponteiros não resolva:

void abfree(void *ptr) {
  Header *header = (Header*) ptr - 1;

Se header aponta para o último bloco alocado, o bloco anterior passará a ser o último. Neste caso, podemos retornar memória do heap para o sistema operacional através de brk():

  if (header == last) {
    last = header->previous;
    brk(header);
  }

Eis a nova versão de nossas funções malloc() e free():

typedef struct Header {
   struct Header *previous;
 } Header;

 Header *last = NULL;

 void *abmalloc(size_t size) {
   Header *header = sbrk(sizeof(Header) + size);
   header->previous = last;
   last = header;
   return header + 1;
 }

 void abfree(void *ptr) {
   Header *header = (Header*) ptr - 1;
   if (header == last) {
     last = header->previous;
     brk(header);
   }
 }

abmalloc() e abfree() podem ser ligeiramente mais econômicos em memória agora, mas não muito. Raramente a memória alocada dinamicamente se comporta com uma pilha, onde o bloco mais velho é sempre desalocado primeiro. No próximo post, veremos como utilizar a memória de blocos mais antigos que não estão mais em uso.