Gestor de memória, parte II

Agora que já temos uma ideia do que temos de fazer podemos começar a escrever o nosso gestor de memória.

Makefile

Vamos dividir o trabalho em três modulos:

1. mymalloc.o: um módulo com as funções mymalloc e myfree
2. dict.o: para testar vamos usar uma versão modificada do código do primeiro guião, usando mymalloc e myfree no lugar de malloc e free
3. prog.o: um módulo com a função main, exactamente igual à do primeiro guião

Para compilar isto usamos este Makefile:

OBJECT_FILES=prog.o mymalloc.o dict.o
CFLAGS=-g

prog : $(OBJECT_FILES)
    $(CC) $(CFLAGS) -o $@ $(OBJECT_FILES)

.c.o :
    $(CC) $(CFLAGS) -c -o $@ $<;

dict.o : dict.h
mymalloc.o : mymalloc.h

Este foi escrito tirando partido de algumas funcionalidades avançadas do make. Num outro post posso falar sobre isso. Não se preocupem se não perceberem. Se quiserem podem tentar escrever o vosso com base no do primeiro guião. Não se esqueçam da esquisitice do make em relação a tabs e espaços.

Preparação

Os cabeçalhos de mymalloc e myfree ficam em mymalloc.h:

#include <stddef.h>

void* mymalloc(size_t size);

void myfree(void* ptr);

O tipo de dados size_t, que está definido na biblioteca stddef.h é o tipo de dados que se deve usar para representar tamanhos de dados. Geralmente é um inteiro, mas sempre com o tamanho certo para cada máquina. A função malloc recebe um parâmetro deste tipo, e consequentemente também a função mymalloc.

As implementações ficam em mymalloc.c:

#include "mymalloc.h"

#include <unistd.h>

// (1) Outras declarações...

void* mymalloc(size_t size)
{
    // (2) ...
}

void myfree(void* ptr)
{
    // (3) ...
}

Antes de implementar mymalloc ou myfree, temos de definir a estrutura de dados para armazenar a informação dos blocos:

// (1) Outras declarações
typedef struct blockInfo
{
    size_t length;
    int isFree;
} BlockInfo;

Como vimos anteriormente, a primeira coisa a fazer na função mymalloc é procurar um bloco livre com tamanho suficiente. Para começar essa pesquisa precisamos do endereço do primeiro bloco.

// (2) ...
static BlockInfo* firstBlock;

Este endereço vai ser obtido da primeira vez que a função mymalloc seja chamada e nunca mais vai ser alterado porque o primeiro bloco vai estar sempre no início da heap. Podemos obtê-lo assim:

// (2)...
static int isInitialized = 0;

if(!isInitialized)
{
    isInitialized = 1;
    firstBlock = (BlockInfo*)sbrk(0);
}

Agora sim, podemos escrever as funções mymalloc e myfree.

mymalloc

Como já vimos, a primeira coisa a fazer em mymalloc é percorrer a heap à procura de um bloco com tamanho suficiente. Mas temos de saber quando devemos parar, caso não encontremos um. Para isso temos de saber onde termina a heap. Mais uma vez, chamamos a função sbrk com o parâmetro 0.

void* end = sbrk(0);

Agora percorremos a heap:

    BlockInfo* block = firstBlock;
    int found = 0;
    while(block != end && !found)
    {
        if(block->length >= size)
        {
            found = 1;
        }
        block += sizeof(BlockInfo) + block->length; // Errado!
    }

Parece tudo bem, mas a última linha tem um erro. Como block é um apontador para BlockInfo, quando somámos uma quantidade n, block avança não n bytes, mas sim n vezes o tamanho de um BlockInfo. Se o bloco tiver 100 bytes, vamos avançar (100+8)*8 = 864 bytes, porque um BlockInfo ocupa oito bytes.

Uma solução é dividir o avanço pelo tamanho de um BlockInfo. No entanto, esta solução cria outro problema. Nem todos os números são divisíveis pelo tamanho de BlockInfo (oito, neste caso). Temos então de alinhar todos os blocos a oito bytes, ou melhor, ao tamanho de BlockInfo, antes de percorrermos a heap:

    if(size % sizeof(BlockInfo) != 0)
    {
        size += sizeof(BlockInfo) – size % sizeof(BlockInfo);
    }
    BlockInfo* block = firstBlock;
    int found = 0;
    while(block != end && !found)
    {
        if(block->isFree && block->length >= size)
        {
            found = 1;
        }
        block += (sizeof(BlockInfo) + block->length) / sizeof(BlockInfo);
 // ou block += 1 + block->length / sizeof(BlockInfo);
    }

Depois de percorrermos a heap:

• encontrámos um bloco com tamanho suficiente, ou
• chegámos ao fim da heap sem encontrar um bloco com tamanho suficiente.

Se encontrámos um bloco podemos marcá-lo como usado e devolver um apontador para o espaço livre desse bloco.

    if(found)
    {
        block->isFree = 0;
        // O espaço do utilizador fica exactamente um BlockInfo à frente
        return block + 1;
    }

Caso contrário, temos de alocar espaço para um bloco novo, e para a respectiva estrutura de controlo com sbrk:

    else
    {
        BlockInfo* newBlock = (BlockInfo*)sbrk(sizeof(BlockInfo) + size);
        if(newBlock < 0)
        {
            // Não há memória suficiente!
            return NULL;
        }
        newBlock->length = size;
        newBlock->isFree = 0;
        // O espaço do utilizador fica exactamente um BlockInfo à frente
        return newBlock + 1;
    }

myfree

Para libertar um bloco, o utilizador passa à função myfree um apontador para o espaço usado por ele. Para o marcar como livre temos de aceder à estrutura de controlo que está antes desse bloco:

 

Para isso temos de usar aritmética de apontadores. O que nós queremos é andar um BlockInfo para trás. Mas ptr é um apontador do tipo void*. Temos então de fazer um cast para BlockInfo*. Depois disso já podemos recuar um, simplesmente subtraindo 1 ao apontador.

    BlockInfo* usedBlock = ((BlockInfo*)ptr) - 1;

Agora podemos marcar este bloco como livre:

    usedBlock->isFree = 1;

Notas finais

Se agora compilarmos o programa podemos ver que não há erros de compilação:

$ make

E se corrermos o programa podemos confirmar que o dicionário do primeiro guião ainda funciona:

$ ./prog

* Put 42
42: foo
--------
* Put 17
17: spam
42: foo
--------
* Put 23
17: spam
23: bar
42: foo
--------
* Get 1: (null)
--------
* Get 42: foo
--------
* Get 17: spam
--------
* Get 23: bar
--------
* Del 1
17: spam
23: bar
42: foo
--------
* Del 23
17: spam
42: foo
--------
* Del 42
17: spam
--------
* Del 17
--------

O código completo encontram no sítio do costume.