Suspensão da Descrença

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.