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, alteramos nossas funções para liberar alguns blocos de memória. Contudo, isto apenas ocorria se os blocos liberados fossem desalocados do mais novo ao mais antigo.

Isto não faria muita diferença. Raramente a memória alocada dinamicamente se comporta com uma pilha, onde o bloco mais novo é sempre desalocado primeiro. A grande vantagem da alocação de memória dinâmica, afinal, é que ela não funciona como uma pilha.

Para entender as limitações de nossa implementação, considere o código abaixo

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

Na primeira linha, alocamos oito bytes, e os liberamos na terceira linha. Na última linha, alocamos oito bytes de novo. Contudo, não podemos reaproveitar a memória liberada, pois novos blocos de memória só são alocados no topo do heap. Para economizar memória de verdade, precisamos de uma solução mais sofisticada.

Uma opção é reutilizar blocos livres. Quando desalocarmos um bloco de memória, vamos marcá-lo como disponível para reuso. Quando uma solicitação de memória de tamanho menor ou igual a algum bloco disponível ocorrer, podemos apenas retornar um ponteiro para o bloco disponível e marcá-lo como em uso.

Para isto, acrescentamos ao cabeçalho dos blocos um campo booleano, chamado available, que indicará se o bloco está livre. Como um bloco só pode ser reusado se a memória solicitada por abmalloc() for menor ou igual à disponível no bloco, precisamos também de um campo no cabeçalho indicando o tamanho do bloco, que chamaremos de size.

typedef struct Header {
  struct Header *previous;
  size_t size;
  bool available;
} Header;

Quando o bloco é alocado, o valor do campo available deve ser false (já que o bloco não está disponível). Também registramos o tamanho do bloco no campo size:

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

Temos as informações no cabeçalho mas ainda não estamos reusando memória desalocada. Para reaproveitar os blocos disponíveis, precisamos encontrá-los! O algoritmo para isto é bem simples: logo no começo abmalloc() irá iterar sobre os blocos, a partir do último até chegar ao primeiro. Como o ponteiro previous do primeiro bloco é sempre NULL, paramos quando o ponteiro for NULL:

void *abmalloc(size_t size) {
   Header *header = last;
   while (header != NULL) {
     header = header->previous;
   }

Em cada iteração, verificamos se o bloco está disponível e tem tamanho aceitável. Se no meio desse processo encontrarmos um bloco disponível maior ou igual ao que precisamos, estamos com sorte! Marcamos o bloco como indisponível, e o retornamos.

void *abmalloc(size_t size) {
   Header *header = last;
   while (header != NULL) {
     if (header->available && (header->size >= size)) {
       header->available = false;
       return header + 1;
     }
     header = header->previous;
   }

E se não encontrarmos um bloco que satisfaça essas condições? Neste caso a função abmalloc() aumenta o heap, como já fazia antes:

void *abmalloc(size_t size) {
  Header *header = last;
  while (header != NULL) {
    if (header->available && (header->size >= size)) {
      header->available = false;
      return header + 1;
    }
    header = header->previous;
  }
  header = sbrk(sizeof(Header) + size);
  header->previous = last;
  header->size = size;
  header->available = false;
  last = header;
  return last + 1;
}

Na hora de desalocar, temos duas situações possíveis. Se o bloco desalocado por abfree() for o último, nada muda: movemos o topo do heap para o começo do bloco, alteramos o ponteiro last. Mas se o bloco não estiver no topo do heap? Simplesmente marcamos ele como disponível, como pode ser visto na cláusula else da função abaixo:

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

Reutilizar blocos de memória é um enorme avanço. Contudo, podemos ser ainda mais eficientes no uso de memória. Por exemplo, só reduzimos o tamanho do heap se desalocamos o último bloco. Se há mais blocos inutilizados logo antes dele, poderíamos liberá-los também. Veremos como fazer isto no próximo post.