Suspensão da Descrença

No post anterior, aprendemos como dividir blocos para aproveitar melhor os espaços grandes. Contudo, isso traz um novo desafio: a fragmentação da memória. Blocos ores podem se acumular, formando cadeias de blocos livres que, se unificados, atenderiam a requisições maiores. À medida que os blocos são divididos, tornam-se cada vez menores, dificultando seu reaproveitamento.

Como blocos pequenos podem aumentar o consumo de memória

Considere, por exemplo, o snippet de código abaixo:

void *ptr1 = abmalloc(128);
void *ptr2 = abmalloc(8);
abfree(ptr1);
void *ptr3 = abmalloc(8);
abfree(ptr3);
void *ptr4 = abmalloc(128);Code language: JavaScript (javascript)

Nele, alocamos 128 bytes de memória e, posteriormente, 8 bytes. Os blocos de memória teriam um layout similar à figura abaixo:

Depois, liberamos o bloco maior:

…e alocamos 8 bytes. Devido às últimas mudanças na função abmalloc(), esses 8 bytes serão extraídos do bloco maior:

Agora, ao liberar os 8 bytes recém-alocados, obtivemos dois blocos livres:

Quando alocamos um novo bloco de 128 bytes, enfrentamos um problema: nenhum dos dois blocos livres possui tamanho suficiente individualmente, embora, juntos, eles pudessem atender à requisição. Como resultado, um novo bloco é alocado no final da stack, que continua a crescer.

Uma solução para esse problema é unir blocos livres adjacentes.

Refatorando para reuso e legibilidade

Antes de prosseguirmos, faremos mais uma rodada de refatorações, pois há trechos de código pequenos, mas complexos, que serão reutilizados.

Primeiramente, vamos criar uma função que, ao receber um header, retorne um ponteiro para a área de memória a ser devolvida ao usuário. Até agora, temos obtido esse resultado somando uma unidade ao ponteiro do header. Vamos encapsular essa lógica em uma função para simplificar e melhorar a reutilização do código:

void *header_user_area(Header *header) {
  return header + 1;
}Code language: JavaScript (javascript)

Consequentemente, em todos os lugares de abmalloc() onde anteriormente utilizávamos:

return header + 1;Code language: JavaScript (javascript)

…vamos utilizar a nova função:

return header_user_area(first);

Também precisamos frequentemente do ponteiro para a posição de memória após o bloco. Atualmente, calculamos isso com uma fórmula um tanto complicada: fazemos o casting do ponteiro do header para void*, somamos o tamanho da estrutura Header e adicionamos o tamanho do bloco alocado. Essa lógica pode ser observada na função header_split():

    Header *new_header = ((void*)header) + sizeof(Header) + header->size;Code language: JavaScript (javascript)

Vamos criar uma função para executar esta operação, chamada header_address_after_block():

void *header_address_after_block(Header *header) {<br>  return ((void*)header) + sizeof(Header) + header->size;<br>}Code language: JavaScript (javascript)

Como a função header_user_area() já realiza basicamente a mesma operação que a primeira parte da fórmula, podemos utilizá-la para simplificar header_split():

void *header_address_after_block(Header *header) {
  return header_user_area(header) + header->size;
}Code language: JavaScript (javascript)

Depois disso, substituiremos a fórmula pela nossa função em header_split():

    Header *new_header = header_address_after_block(header);

Por fim, será necessário verificar se, dado um header, existe um bloco livre antes ou depois dele. A expressão para essa verificação é intuitiva, mas extensa. Por exemplo, a fórmula abaixo é usada para determinar se há um bloco livre antes:

(header->previous != NULL) && header->previous->availableCode language: PHP (php)

Para facilitar um pouco a leitura, vamos colocar essa expressão em uma função, assim como a outra, correspondente a blocos posteriores:

bool header_previous_available(Header *header) {
  return (header->previous != NULL) && header->previous->available;
}

bool header_next_available(Header *header) {
  return (header->next != NULL) && header->next->available;
}Code language: PHP (php)

Pronto, agora temos quatro novas ferramentas que irão nos ajudar a fundir blocos disponíveis. Vamos em frente!

Procurando blocos livres adjacentes

Para juntar blocos de memória livres e adjacentes, precisamos, no momento da desalocação, verificar se o bloco anterior ou o bloco posterior estão disponíveis. Podemos fazer isso criando duas variáveis: uma para apontar para o primeiro bloco livre e outra para o último bloco livre. Inicialmente, ambas apontarão para o bloco que está sendo desalocado.

Header *header_merge(Header *header) {<br>  Header *first_available = header;<br>  Header *last_available = header;Code language: HTML, XML (xml)

Se o bloco anterior ao atual estiver livre, first_available aponta para ele.

   if (header_previous_available(header)) {<br>     first_available = header->previous;<br>   }Code language: HTML, XML (xml)

De modo análogo, se o próximo bloco estiver disponível, last_available deve apontar para ele

  if (header_next_available(header)) {<br>    last_available = header->next;<br>  }Code language: HTML, XML (xml)

Quando não há blocos livres

Caso não haja blocos livres nem à frente nem antes do bloco recém-desalocado, não há nada a ser fundido. Neste caso, as variáveis first_available e last_available serão iguais a header, e nossa função simplesmente retornará o ponteiro para o bloco que foi passado a ela.

  if ((first_available == header) && (last_available == header)) {
    return header;
  }Code language: JavaScript (javascript)

Nota: Não precisamos verificar o bloco anterior ao anterior, ou o posterior ao posterior, e assim por diante. Se, em cada chamada de abfree(), fundimos o bloco com qualquer vizinho livre, é impossível ter dois blocos livres consecutivos. Portanto, basta verificar apenas os vizinhos imediatos.

Atualizando o tamanho quando há blocos livres

Caso alguma das variáveis first_available ou last_available não seja igual a header, precisaremos fundir os blocos. Para isso, precisamos realizar duas ações.

Primeiro, devemos atualizar o tamanho do primeiro bloco disponível para incluir o último bloco. Para isso, obtemos o ponteiro que aponta logo após o último bloco disponível.

  void *end = header_address_after_block(last_available);Code language: JavaScript (javascript)

O tamanho do novo bloco será a diferença entre este ponteiro e o endereço do bloco de usuário:

  size_t size = end - header_user_area(first_available);E

Uma vez que tenhamos o tamanho, só precisamos atualizar o primeiro bloco disponível:

  header_init(first_available, size, true);Code language: JavaScript (javascript)

Atualizando ponteiros do bloco fundido

Com o tamanho do bloco atualizado, precisamos ajustar seus ponteiros. Para o ponteiro para trás, ele deve passar a apontar para o bloco anterior ao primeiro bloco disponível:

  Header *previous = first_available->previous;Code language: PHP (php)

Já o próximo deve ser o que se seguia ao último bloco disponível:

  Header *next = last_available->next;Code language: PHP (php)

Uma vez que tenhamos esses valores, basta conectá-los adequadamente utilizando a função header_plug():

  header_plug(first_available, previous, next);

Caso de borda: o último bloco

Um último cuidado que devemos ter é considerar que o novo bloco pode vir a ser o último. Neste caso, o bloco que criamos deve se tornar o último bloco agora.

  if (last_available == last) {<br>    last = first_available;<br>  }<br>  return first_available;<br>}Code language: HTML, XML (xml)

Com isso, nossa função de fusão está implementada.

Utilizando header_merge() em abfree()

Agora que temos uma função que une blocos livres, alteramos abfree() para invocá-la no header do bloco a ser desalocado. Feito isso, prosseguimos com a liberação de memória

  Header *header = (Header*) ptr - 1;
  header = header_merge(header);

  if (header == last) {

Conclusão

Aqui está a função abfree() completa:

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

  header = header_merge(header);

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

Header *header_new(Header *previous, size_t size, bool available) {
  Header *header = sbrk(sizeof(Header) + size);
  header_init(header, size, available);
  header_plug(header, previous, NULL);
  return header;
}

void header_init( Header *header, size_t size, bool available) {
  header->size = size;
  header->available = available;
}

void header_plug(Header *header, Header *previous, Header *next) {
  header->previous = previous;
  if (previous != NULL) {
    previous->next = header;
  }
  header->next = next;
  if (next != NULL) {
    next->previous = header;
  }
}

void *header_user_area(Header *header) {
  return header + 1;
}

void *header_address_after_block(Header *header) {
  return header_user_area(header) + header->size;
}

bool header_previous_available(Header *header) {
  return (header->previous != NULL) && header->previous->available;
}

bool header_next_available(Header *header) {
  return (header->next != NULL) && header->next->available;
}

Header *header_merge(Header *header) {
  Header *first_available = header;
  Header *last_available = header;

  if (header_previous_available(header)) {
    first_available = header->previous;
  }
  if (header_next_available(header)) {
    last_available = header->next;
  }

  if ((first_available == header) && (last_available == header)) {
    return header;
  }

  void *end = header_address_after_block(last_available);
  size_t size = end - header_user_area(first_available);
  header_init(first_available, size, true);

  Header *previous = first_available->previous;
  Header *next = last_available->next;
  header_plug(first_available, previous, next);

  if (last_available == last) {
    last = first_available;
  }

  return first_available;
}

Header *header_split(Header *header, size_t size) {
  size_t original_size = header->size;
  if (original_size > size + sizeof(Header)) {
    header->size = original_size - size - sizeof(Header);
    Header *new_header = header_address_after_block(header);
    header_init(new_header, size, true);
    header_plug(new_header, header, header->next);
    if (header == last) {
      last = new_header;
    }
    return new_header;
  } else {
    return header;
  }
}Code language: PHP (php)

Com as alterações deste e do último post, o tamanho dos blocos livres deixam de ser um agravante no consumo de memória, e nossa função malloc() aproxima-se de ficar pronta. Há porém, um último problema a ser resolvido: o alinhamento de blocos de memória. Examinaremos isto no próximo post.