No post desta série sobre implementação de malloc() e free(), mostramos como é possível reutilizar blocos de memória e reduzir o heap liberando blocos mais novos. No entanto, a função atual introduz um problema sutil: ela prioriza a reutilização de blocos mais novos, o que pode levar ao aumento do consumo de memória ao longo do tempo. Por que isso acontece? Vamos decompô-lo.

Redução de heap reutilizando blocos recentes

Considere o seguinte cenário. Primeiro, alocamos quatro blocos de memória:

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

A estrutura da memória pode ser visualizada assim:

Agora, lançamos o primeiro e o terceiro blocos…

abfree(ptr1);
abfree(ptr3);

…resultando na seguinte estrutura:

Em seguida, alocamos outro bloco do mesmo tamanho:

void *ptr5 = abmalloc(8);

À medida que a função abmalloc() começa a procurar o bloco livre mais recente, ela reutiliza o bloco no topo. Se agora liberarmos o último bloco:

Se lançarmos agora o último bloco…

abfree(ptr4);

…podemos reduzir o tamanho do heap em apenas um bloco de 8 bytes, já que o bloco anterior não é mais gratuito:

Reutilização de blocos antigos

Agora, imagine o mesmo cenário, mas com uma modificação: nossa função começa a procurar blocos livres a partir do mais antigo. A estrutura inicial será a mesma…

…e novamente liberamos o primeiro e o terceiro blocos de memória:

Desta vez, o primeiro bloco será reutilizado:

Agora, quando liberarmos o último bloco, teremos dois blocos livres no topo, o que nos permitirá reduzir o heap em dois blocos de 8 bytes:

Este exemplo ilustra como, ao dar preferência a blocos mais novos, acabamos acumulando blocos antigos não utilizados, desperdiçando memória e levando a um crescimento desnecessário de heap. A solução é modificar a estratégia de busca, priorizando o reaproveitamento de blocos mais antigos.

Implementando preferência por blocos antigos

Para resolver este problema, começaremos adicionando um ponteiro para o próximo bloco no cabeçalho. Também criaremos um ponteiro global para o primeiro bloco, para que possamos iniciar a busca a partir dele:

typedef struct Header {
  struct Header *previous, *next;
  size_t size;
  bool available;
} Header;
Header *first = NULL;
Header *last = NULL;

Vamos criar blocos de memória com cabeçalhos em duas situações diferentes, então vamos fazer uma pequena refatoração: vamos extrair essa lógica para uma função auxiliar que aloca e inicializa o cabeçalho (inclusive configurando o campo next com NULL):

Header *header_new(Header *previous, size_t size, bool available) {
  Header *header = sbrk(sizeof(Header)   size);
  header->previous = previous;
  header->next = NULL;
  header->size = size;
  header->available = false;
  return header;
}

Com esta nova função, podemos simplificar a lógica dentro de abmalloc():

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

Agora temos acesso ao primeiro e ao último bloco, e dado um bloco, podemos descobrir os anteriores e os próximos. Sabemos também que quando o ponteiro para o primeiro bloco é nulo, nenhum bloco foi alocado ainda. Portanto, neste caso, alocaremos o bloco imediatamente e inicializaremos o primeiro e o último:

void *abmalloc(size_t size) { 
  if (size == 0) { 
    return NULL; 
  } 
  if (first == NULL) { 
    first = last = header_new(NULL, size, false); 
    return first   1; 
  }

Se primeiro não for mais NULL, já existem blocos alocados, então começaremos a procurar por um bloco reutilizável. Continuaremos usando a variável header como iterador, mas em vez de começar pelo bloco mais recente, a busca começará pelo mais antigo:

  Header *header = first;

A cada iteração, avançaremos para o próximo bloco da sequência, em vez de voltar ao bloco anterior:

  while (header != NULL) { 
    if (header->available && (header->size >= size)) { 
      header->available = false; 
      return header   1; 
    } 
    header = header->next; 
  }

A lógica permanece a mesma: se encontrarmos um bloco disponível de tamanho suficiente, ele será retornado. Caso contrário, se nenhum bloco reutilizável for encontrado após percorrermos a lista, um novo bloco será alocado:

  last = header_new(last, size, false);

Agora precisamos ajustar o bloco que foi o último (após a alocação, o penúltimo). Apontou para NULL, mas agora deve apontar para o novo bloco. Para fazer isso, definimos o próximo campo do bloco anterior para o novo último bloco:

  last->previous->next = last; 
  return last   1; 
}

Ajustes em abfree()

A função abfree() basicamente mantém a mesma estrutura, mas agora devemos lidar com alguns casos extremos. Quando liberamos blocos no topo do heap, um novo bloco se torna o último, como já fazemos neste trecho:

    last = header->previous;
    brk(header)

Aqui, o cabeçalho do ponteiro faz referência ao último bloco não nulo disponível na pilha. Temos dois cenários possíveis:

1. o bloco atual possui um bloco anterior, que se tornará o novo último bloco. Neste caso, devemos definir o ponteiro próximo deste bloco como NULL.
2. o bloco atual não possui um bloco anterior (ou seja, é o primeiro e mais antigo bloco). Quando é liberado, a pilha está vazia. Neste caso, ao invés de tentar atualizar um campo de um bloco inexistente, simplesmente definimos primeiro como NULL, indicando que não há mais blocos alocados.

Aqui está como implementamos:

  last = header->previous; 
  if (last != NULL) { 
    last->next = NULL; 
  } else { 
    first = NULL; 
  } 
  brk(header);

Conclusão

Nossas funções abmalloc() e abfree() agora ficam assim:

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

Header *first = NULL;
Header *last = NULL;

Header *header_new(Header *previous, size_t size, bool available) {
  Header *header = sbrk(sizeof(Header)   size);
  header->previous = previous;
  header->next = NULL;
  header->size = size;
  header->available = false;
  return header;
}

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

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;
    if (last != NULL) {
      last->next = NULL;
    } else {
      first = NULL;
    }
    brk(header);
  } else {
   header->available = true;
  }
 }

Essa mudança nos permite economizar consideravelmente mais memória. Contudo, ainda existem problemas a resolver. Por exemplo, considere o seguinte cenário: solicitamos a alocação de um bloco de memória de 8 bytes e abmalloc() reutiliza um bloco de, digamos, 1024 bytes. Há claramente um desperdício.

Veremos como resolver isso no próximo post.