Suspensão da Descrença

Este post faz parte de uma série sobre como implementar as funções malloc() e free(). No artigo anterior, aprendemos como reutilizar blocos de memória. Foi um grande avanço, mas há muito mais a melhorar.

Um exemplo é a redução do tamanho do heap. Quando liberamos o último bloco de memória, movemos o topo do heap para fim do bloco anterior. Contudo, este bloco anterior pode também estar livre, assim como outros. Considere o caso abaixo:

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

Neste caso, ao liberarmos o bloco apontado por ptr2, fazemos com que ptr1 seja o último bloco. Contudo, ptr1 também está livre, então poderíamos reduzir ainda mais o tamanho do heap.

Para isso, vamos iterar sobre os ponteiros do final da lista até não haver mais blocos livres. Se o cabeçalho do ponteiro recebido apontar para o último bloco e o bloco anterior estiver livre, movemos o ponteiro de cabeçalho para ele. Repetimos esse processo até chegar a um bloco disponível cujo anterior esteja em uso (ou seja NULL, caso seja o primeiro bloco). Em seguida, executamos o procedimento de redução do heap:

  if (header == last) {
    while ((header->previous != NULL) && header->previous->available) {
      header = header->previous;
    }
    last = header->previous;
    brk(header);
  } else {

Agora, porém, precisamos corrigir um bug em abfree(). De acordo com a especificação, a função free() deve aceitar o ponteiro nulo e não fazer nada. Se abfree() receber NULL, teremos uma falha de segmentação! Felizmente, isto é fácil de resolver adicionando uma verificação no início da função:

void abfree(void *ptr) {
   if (ptr == NULL) {
     return;
   }
   Header *header = (Header*) ptr - 1

E assim fica nossa função abfree() até o momento:

void abfree(void *ptr) {
   if (ptr == NULL) {
     return;
   }
   Header *header = (Header*) ptr - 1;
   if (header == last) {
     while ((header->previous != NULL) && header->previous->available) {
       header = header->previous;
     }
     last = header->previous;
     brk(header);
   } else {
     header->available = true;
   }
 }

Reduzir o tamanho do heap é uma otimização simples, mas ainda há desafios a serem enfrentados. Por exemplo, a maneira com que escolhemos qual bloco reutilizar pode levar a heaps maiores que o necessário. Veremos por que isto acontece, e como resolver isto, no próximo post.