Suspensão da Descrença

No post anterior desta série sobre a implementação das funções malloc() e free(), mostramos como é possível reutilizar blocos de memória e reduzir o heap ao liberar os blocos mais novos. No entanto, a função atual tem um comportamento que sutilmente leva a um consumo de memória maior: ela escolhe blocos de memória mais recentes para reutilizar. Por que isso é um problema? Vamos analisar como isso ocorre.

Redução do heap com reaproveitamento de blocos recentes

Considere o cenário a seguir. 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 em memória pode ser visualizada assim:

Agora, liberamos o primeiro e o terceiro bloco…

abfree(ptr1);
abfree(ptr3); 

…resultando na seguinte estrutura:

Em seguida, alocamos outro bloco do mesmo tamanho:

void *ptr5 = abmalloc(8); 

Como função abmalloc() começa a busca pelo bloco livre mais recente, ela reutiliza o bloco que está no topo. Se agora liberarmos o último bloco:

Se, agora, liberamos o último bloco…

abfree(ptr4);

…poderemos reduzir o tamanho do heap em apenas um bloco de 8 bytes, já que o penúltimo bloco não está mais livre:

Reaproveitamento de blocos antigos

Agora, imagine o mesmo cenário, mas com uma modificação: nossa função busca blocos livres começando pelo mais antigo.

A estrutura inicial será a mesma…

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

Dessa vez, o primeiro bloco será reutilizado:

Agora, ao liberarmos o último bloco, teremos dois blocos livres no topo, permitindo reduzir o heap em dois blocos de 8 bytes:

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

Implementando preferência por blocos antigos

Para resolver esse problema, vamos implementar uma nova abordagem no código. Primeiramente, vamos adicionar ao cabeçalho dos blocos um ponteiro para o próximo bloco, permitindo percorrermos a memória de maneira eficiente. Também adicionaremos um ponteiro para o primeiro bloco, o que facilitará a busca:

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

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

Agora, faremos uma pequena refatoração. Como criamos blocos de memória com headers em duas situações diferentes, extrairemos essa lógica para uma função auxiliar que aloca e inicializa o cabeçalho (inclusive setando 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 essa 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 último blocos e, dado um bloco, podemos descobrir o anterior e o posterior. Sabemos, também, que quando o ponteiro para o primeiro bloco for nulo, nenhum bloco terá sido alocado ainda. Então, neste caso, alocaremos o bloco imediatamente, e inicializaremos tanto first quanto last:

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

Se first não é mais NULL, já existem blocos alocados, então começaremos a busca por um bloco reutilizável. Continuaremos utilizando a variável header como iterador, mas, em vez de começar pelo bloco mais recente, a pesquisa será iniciada a partir do mais antigo:

  Header *header = first;

A cada iteração, avançaremos para o próximo bloco na sequência, em vez de retroceder para o 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 encontramos um bloco disponível e de tamanho suficiente, ele é 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 era o último (e que, após a alocação, passa a ser o penúltimo). Ele apontava para NULL, mas agora deve apontar para o novo bloco. Para isso, acessamos o ponteiro previous do novo último bloco e atualizamos o campo next do bloco anterior:

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

Ajustes na Função abfree()

A função abfree() mantém basicamente a mesma estrutura, mas agora devemos tratar alguns casos de borda. Quando liberamos blocos no topo do heap, um novo bloco passa a ser o último, conforme já fazemos neste trecho:

    last = header->previous;
    brk(header)

Aqui, o ponteiro header referencia o último bloco não nulo e disponível na pilha. Temos dois cenários possíveis: no primeiro, o bloco atual possui um bloco anterior, que se tornará o novo último bloco. Nesse caso, devemos ajustar o ponteiro next desse bloco para NULL. No segundo cenário, o bloco atual não possui um bloco anterior (ou seja, ele é o primeiro e mais antigo bloco). Quando ele é liberado, a pilha fica vazia. Nesse caso, em vez de tentar atualizar um campo de um bloco inexistente, basta definirmos first como NULL, indicando que não há mais blocos alocados:

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

Conclusão

Nossas funções abmalloc() e abfree() agora estão 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;
  }
 }Code language: PHP (php)

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

Veremos como resolver isso no próximo post.