Alocador de memória

Este projeto visa construir um alocador de memória heap para o PPOS. Com ele funcionando, não precisaremos mais usar o alocador da biblioteca C (malloc/free).

A área de memória heap, usada para alocação dinâmica, será representada em nosso SO por um grande vetor estático de bytes, a ser definido em memory.c:

// tamanho total da heap: 64 MB
#define HEAP_SIZE 64*1024*1024
 
static char heap[HEAP_SIZE];

Essa área de memória poderá ser alocada pelas aplicações em blocos de tamanho variável, usando o algoritmo de alocação first-fit, que aloca sempre o primeiro bloco de memória livre com tamanho suficiente. A figura abaixo mostra a organização da memória heap, com blocos alocados e blocos livres:

Para gerenciar os blocos de memória (livres ou alocados), sugere-se definir um vetor de descritores de bloco contendo, para cada bloco:

• endereço inicial do bloco
• tamanho do bloco em bytes
• estado do bloco (livre ou alocado)
• número do bloco vizinho da esquerda
• número do bloco vizinho da direita

A alocação de um bloco usa a seguinte estratégia:

1. ajusta o tamanho solicitado para um múltiplo de 16 bytes
2. na lista de blocos livres, procura um bloco com tamanho suficiente (first-fit)
3. se não encontrar, retorna NULL
4. se o tamanho do bloco livre encontrado for maior que o necessário, redimensiona-o e cria um novo bloco livre com a área excedente
5. marca o bloco como ocupado
6. retorna um ponteiro para o início do bloco

A figura a seguir ilustra a alocação consecutiva de 4 blocos de memória, em um heap inicialmente livre:

A liberação de um bloco usa a seguinte estratégia:

1. localiza o número do bloco alocado a partir do endereço fornecido
2. se não encontrar o bloco, retorna erro
3. se o bloco já estiver livre, retorna erro
4. marca o bloco como livre
5. se o bloco à sua esquerda também estiver livre, funde-os em um só bloco
6. se o bloco à sua direita também estiver livre, funde-os em um só bloco

Ao liberar um bloco, deve-se verificar se seus vizinhos imediatos estão livres. Se algum vizinho estiver livre, o bloco recém-liberado e seus vizinhos livres podem ser fundidos em um bloco livre maior. Esse processo, denominado coalescência e ilustrado abaixo, permite obter blocos livres maiores, diminuindo a fragmentação da memória.

As seguintes funções, com suas respectivas estruturas de dados de apoio, devem ser implementadas em memory.c:

void mem_init();

Inicia o subsistema de memória, preparando as estruturas de dados de controle do mesmo (tabelas/listas de descritores, etc.).

void *mem_alloc(int size);

Aloca um bloco de memória com o tamanho indicado em bytes; retorna um ponteiro para a área alocada ou NULL se houver erro.

Cada bloco alocado deve ter um tamanho mínimo de 16 bytes e deve ser alinhado em 16 bytes, ou seja, seu tamanho e endereço inicial devem ser múltiplos de 16. O ajuste de um valor para o próximo múltiplo de 16 pode ser feito assim:

// versão mais rápida
value = ((value - 1) | 0x00000F) + 1;
 
// versão mais simples
while (value % 16)
  value++ ;

int mem_free(void *addr);

Libera um bloco de memória previamente alocado, indicado pelo endereço addr; retorna 0 se executar sem problemas ou -1 se o ponteiro for NULL ou indicar uma área não-alocada.

Caso algum bloco vizinho esteja livre, ele deve ser fundido ao bloco liberado.

int mem_size();

Informa a quantidade de memória total, em bytes.

int mem_avail();

Informa a quantidade total de memória disponível, em bytes. Não se preocupa se essa memória livre está fragmentada ou não.

void mem_report();

Imprime um relatório sobre o uso atual da memória, com o seguinte formato:

heap: 184 KB allocated in 11 blocks, 65351 KB available, 65536 KB total
heap: block 1: 0x000055c9a1202340 - 0x000055c9a120537f used prev 0 next 2 size 12352
heap: block 2: 0x000055c9a1205380 - 0x000055c9a1206c3f used prev 1 next 3 size 6336
heap: block 3: 0x000055c9a1206c40 - 0x000055c9a12079af used prev 2 next 4 size 3440
heap: block 4: 0x000055c9a12079b0 - 0x000055c9a12082bf used prev 3 next 5 size 2320
heap: block 5: 0x000055c9a12082c0 - 0x000055c9a12161bf used prev 4 next 6 size 57088
heap: block 6: 0x000055c9a12161c0 - 0x000055c9a12227ff used prev 5 next 7 size 50752
heap: block 7: 0x000055c9a1222800 - 0x000055c9a1226f1f used prev 6 next 8 size 18208
heap: block 8: 0x000055c9a1226f20 - 0x000055c9a122ca7f used prev 7 next 9 size 23392
heap: block 9: 0x000055c9a122ca80 - 0x000055c9a122feff used prev 8 next 10 size 13440
heap: block 10: 0x000055c9a122ff00 - 0x000055c9a123035f used prev 9 next 11 size 1120
heap: block 11: 0x000055c9a1230360 - 0x000055c9a520233f FREE prev 10 next 0 size 66920416

Cada entrada do relatório deve informar:

• número do bloco
• endereços inicial e final
• status (livre ou ocupado)
• vizinho à esquerda e à direita
• tamanho em bytes

Após a implementação do alocador, você deve usá-lo em todo o seu projeto. Nos arquivos kernel/*.c e lib/queue.c, você deve:

• trocar todas as ocorrências de malloc por mem_alloc
• trocar todas as ocorrências de free por mem_free
• remover todas as inclusões de stdlib.h

Sua implementação deve funcionar corretamente com o programa de teste test/pingpong-mqueue.c. Esse programa vai usar intensivamente a alocação de memória na criação e destruição de filas genéricas, tarefas, semáforos e filas de mensagens.

Os seguintes arquivos são relevantes para este projeto:

• kernel/memory.h: interface da gestão de memória
• kernel/memory.c: implementação gestão de memória
• test/pingpong-memory.c: programa de teste
• test/pingpong-memory.txt: saída esperada do teste
• test/pingpong-mqueue.c: teste mais complexo

• Duração estimada: 6 horas.
• Dependências:
  • Tarefas cooperativas
  • Despachante de tarefas
  • Preempção por Tempo
  • Tarefas que esperam
  • Tarefas que dormem
  • Spinlocks e Semáforos