No artigo anterior da série, vimos como a ordem em que escolhemos que blocos de memória reutilizar pode levar a maior ou menor consumo de memória, e mudamos nossas funções para evitar esse desperdício. Mas precisamos resolver outro problema, até mais grave: às vezes, um bloco de memória muito grande pode ocupar o espaço que vários blocos menores poderiam usar. Considere o caso abaixo, em que alocamos um grande pedaço de memória, desalocamos e depois alocamos dois blocos bem menores:
void *ptr1 = abmalloc(128);
void *ptr2 = abmalloc(8);
abfree(ptr1);
void *ptr3 = abmalloc(8);
void *ptr4 = abmalloc(8);Code language: JavaScript (javascript)Aqui, temos um bloco de memória de 128 bytes livre, e, ao alocarmos um bloco de apenas 8 bytes, todos os 128 bytes ficam indisponíveis. Quando alocamos outro bloco de 8 bytes, o heap precisa crescer novamente. Isso não é um uso eficiente de memória.
Existem pelo menos duas soluções populares para esse caso. Uma, mais eficiente, é usar bins: listas que agrupam blocos por tamanho. Essa é uma abordagem mais sofisticada, porém mais complexa. Outra opção, mais simples, é encontrar um bloco grande e dividi-lo em blocos menores. Vamos seguir por essa abordagem.
Mas lembre-se: mais simples não significa exatamente simples 😉
Refatoração Inicial
Antes de começarmos, faremos uma pequena refatoração. Atualmente, a função header_new() faz duas coisas: aloca mais memória para um novo bloco e já inicializa seu cabeçalho, definindo os metadados e os ponteiros para o bloco anterior. A parte de inicializar o cabeçalho pode ser útil, então vamos extraí-la. Criamos duas novas funções para melhorar a legibilidade:
- A função
header_plug(), que “conecta” o bloco inicializado ao anterior e ao próximo. - A função
header_init(), que define os valores iniciais dos metadados do bloco (tamanho e disponibilidade).
Aqui está como elas ficam:
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;
}
}Code language: PHP (php)Agora, basta alterar header_new() para usar essas novas funções:
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;
}Code language: PHP (php)(Além disso, podemos remover a linha last->previous->next = last; da função abmalloc(), já que header_plug() agora cuida disso.)
Dividindo Blocos
Com essas ferramentas em mãos, vamos criar a função header_split(). Dado um cabeçalho e um tamanho mínimo requerido, esta função divide o bloco de memória em dois, se o bloco original for grande o suficiente para conter
- o tamanho requerido,
- um novo cabeçalho do novo bloco e
- um pouco de memória extra.
Primeiro, verificamos se o bloco é grande o bastante:
Header *header_split(Header *header, size_t size) {
size_t original_size = header->size;
if (original_size >= size + sizeof(Header)) {Code language: PHP (php)Se essa condição for satisfeita, dividimos o bloco. Primeiro, reduzimos o tamanho do bloco atual, subtraindo o tamanho de um cabeçalho e o espaço solicitado por abmalloc:
header->size = original_size - size - sizeof(Header);Code language: PHP (php)Isso deixa um espaço de memória após o bloco atual, que usaremos para criar o novo bloco. Calculamos o ponteiro para esse novo bloco:
Header *new_header = header + sizeof(Header) + header->size;Code language: PHP (php)Agora que temos o ponteiro para o novo bloco, inicializamos o cabeçalho com header_init():
header_init(new_header, size, true);Code language: JavaScript (javascript)E conectamos o novo bloco ao anterior e ao próximo usando header_plug():
header_plug(new_header, header, header->next);Code language: PHP (php)Se o bloco original for o último, o novo bloco agora será o último, então atualizamos o ponteiro last:
if (header == last) {
last = new_header;
}Por fim, retornamos o novo bloco:
return new_header;Code language: JavaScript (javascript)Se o bloco original não for grande o suficiente, simplesmente retornamos o bloco original:
} else {
return header;
}
}Code language: JavaScript (javascript)Atualizando abmalloc()
Agora, basta voltar à função abmalloc() e, no lugar onde encontramos um bloco utilizável, invocamos header_split() para tentar dividi-lo:
if (header->available && (header->size >= size)) {
header = header_split(header, size);
header->available = false;
return header + 1;
}Code language: PHP (php)Se o bloco puder ser dividido, o novo bloco será retornado. Caso contrário, o bloco original será mantido e retornado, como antes.
Nota sobre a Divisão de Blocos
Observe que criamos o novo bloco ao final do bloco original. Poderíamos criá-lo no início, mas criar o novo bloco utilizado ao final, o novo bloco livre fica mais próximo dos blocos mais antigos. Com isso, ele será encontrado primeiro na próxima vez que abmalloc() for invocado.
Dividir blocos de memória grandes é um avanço, mas há um problema contrário: blocos de memória pequenos podem causar fragmentação, fazendo com que requisições maiores façam o heap crescer. Veremos como resolver isso no próximo post.
