Gestor de memória, parte I

A Heap

Quando um programa está em memória, há dois segmentos de memória que podem crescer: a heap e a stack.

A stack cresce quando se chamam funções e diminui quando estas retornam. A heap cresce quando alocamos memória dinamicamente.

Quando alocamos memória geralmente fazemo-lo por blocos, dependendo do tamanho das nossas estruturas de dados. Para isto usamos as funções malloc e free.

malloc aloca um bloco de memória com o tamanho que desejamos e free liberta um bloco previamente alocado por malloc.

Por forma não desperdiçar os blocos que vão sendo libertados, a função malloc nem sempre aumenta o tamanho da heap, reutilizando porções livres quando possível.

É este mecanismo de gestão dos blocos livres que iremos implementar. Quando for realmente necessário aumentar o tamanho da heap, usaremos a função sbrk, que faz exactamente isso: aumenta o tamanho da heap do programa.

void* sbrk(int incr);

Esta função devolve um apontador para o início do novo espaço, assim:

Se passarmos 0 como argumento a sbrk obtemos um apontador para o final da heap, e nenhum espaço é alocado.

Usar esta função é bastante simples. O que é mais complicado é a gestão do espaço que está ocupado ou livre.

É para fazer exactamente o quê?

As funções que vamos implementar, mymalloc e myfree, devem funcionar da mesma forma que malloc e free. Vamos começar por perceber o que deve ser exactamente esta funcionalidade.

mymalloc encontra e reserva um bloco com o tamanho desejado. Caso não exista nenhum bloco com espaço suficiente na heap esta deve ser expandida (com recurso a sbrk) e este novo bloco deve ser reservado. A função devolve um apontador para o início desse bloco. O utilizador pode escrever o que quiser nesse bloco e é da sua responsabilidade a libertação do mesmo.

Para cumprir essa responsabilidade, o utilizador deve chamar a função myfree passando o mesmo apontador que recebeu de mymalloc. A função myfree deve então marcar esse espaço como espaço livre para poder ser reutilizado mais tarde.

Como vamos tomar conta dos blocos?

A partir destas descrições de cada uma das funções sabemos que informações são necessárias para cada bloco de memória:

• Os blocos não têm todos o mesmo tamanho. O utilizador é quem decide o tamanho dos blocos.
• Os blocos podem estar ocupados ou livres.

Onde vamos guardar isso?

Vamos guardar esta informação junto dos próprios blocos porque o único argumento de myfree é um apontador para o espaço ocupado pelo bloco. Não pode ser exactamente nesse endereço porque o utilizador pode escrever nesse espaço. Restam-nos duas opções: antes ou depois do espaço do utilizador:

Para acedermos a essa informação se ela estiver no final do bloco, teríamos primeiro de saber o tamanho desse bloco. Como o tamanho do bloco está armazenado precisamente no final do mesmo, temos o problema clássico do ovo e da galinha. Esta solução não serve.

Para acedermos à informação do bloco se esta estiver antes do bloco, basta subtrair o tamanho dessa informação ao apontador que foi passado a myfree e já temos o espaço que queríamos. Esta vai ser a nossa solução.

Como é que procuramos por blocos livres?

Para mymalloc é necessário procurar por blocos livres com um tamanho adequado.

Com o esquema que definimos anteriormente para armazenar a informação sobre os blocos podemos passar de um bloco para outro de forma simples porque sabemos o tamanho de cada um. Isto é verdade porque vamos manter os blocos contíguos, assim:

Agora falta implementar todas estas ideias…