====== Alocador de memória ======

Este projeto faz parte do [[PPOS-v2:start|PPOS v2]].

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'').

==== Estrutura geral ====

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'':

<code c>
// tamanho total da heap: 64 MB
#define HEAP_SIZE 64*1024*1024

static char heap[HEAP_SIZE];
</code>

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:

{{ alocacao.png |}}

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

<note warning>
Observe que neste projeto **não podemos usar** uma lista de descritores dinâmica, nem a biblioteca de filas genéricas desenvolvida anteriormente. Ambas precisam da alocação dinâmica de memória //heap//, que é justamente o objetivo deste projeto. A abordagem mais simples neste caso é definir um vetor estático de descritores de blocos.
</note>

==== Algoritmo de alocação ====

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

  - ajusta o tamanho solicitado para um múltiplo de 16 bytes
  - na lista de blocos livres, procura um bloco com tamanho suficiente (//first-fit//)
  - se não encontrar, retorna NULL (alocação falhou)
  - se o tamanho do bloco livre encontrado for maior que o necessário, divide-o em dois blocos:
    * um bloco a ser alocado, com o tamanho solicitado
    * um bloco livre, com o restante do tamanho anterior
  - marca o bloco como ocupado
  - 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:

{{ mem-alloc.png |Alocação de memória}}

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

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

Ao liberar um bloco, deve-se fazer a **coalescência** dos blocos livres: se um seus vizinhos estiver livre, o bloco recém-liberado e seu vizinho livre devem ser fundidos em um bloco livre maior, **recursivamente**. Esse procedimento permite obter blocos livres maiores, diminuindo a fragmentação da memória.

A coalescência é ilustrada no exemplo abaixo:

{{ mem-free.png |Liberação e coalescência de blocos livres}}

==== Funções a implementar ====

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

=== Inicia a memória ===

<code c>
void mem_init()
</code>

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

=== Aloca memória ===

<code c>
void *mem_alloc(int size)
</code>

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:

<code c>
// versão mais rápida
value = ((value - 1) | 0x00000F) + 1;

// versão mais simples
while (value % 16)
  value++ ;
</code>

=== Libera memória ===

<code c>
int mem_free(void *addr)
</code>

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.

=== Memória total ===

<code c>
int mem_size()
</code>

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

=== Memória livre ===

<code c>
int mem_avail()
</code>

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.

=== Informa sobre o uso da memória ===

<code c>
void mem_report()
</code>

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

<code>
heap: 435 KB allocated (16 blocks), 65100 KB free (1 blocks)
heap: block     0: 0x0000565154c56340 - 0x0000565154c5644f aloc prev    16 next     1 size 272
heap: block     1: 0x0000565154c56450 - 0x0000565154c5646f aloc prev     0 next     2 size 32
heap: block     2: 0x0000565154c56470 - 0x0000565154c5648f aloc prev     1 next     3 size 32
heap: block     3: 0x0000565154c56490 - 0x0000565154c5659f aloc prev     2 next     4 size 272
heap: block     4: 0x0000565154c565a0 - 0x0000565154c5e59f aloc prev     3 next     5 size 32768
heap: block     5: 0x0000565154c5e5a0 - 0x0000565154c5e5bf aloc prev     4 next     6 size 32
heap: block     6: 0x0000565154c5e5c0 - 0x0000565154c6d91f aloc prev     5 next     7 size 62304
heap: block     7: 0x0000565154c6d920 - 0x0000565154c7025f aloc prev     6 next     8 size 10560
heap: block     8: 0x0000565154c70260 - 0x0000565154c7f94f aloc prev     7 next     9 size 63216
heap: block     9: 0x0000565154c7f950 - 0x0000565154c84c8f aloc prev     8 next    10 size 21312
heap: block    10: 0x0000565154c84c90 - 0x0000565154c9319f aloc prev     9 next    11 size 58640
heap: block    11: 0x0000565154c931a0 - 0x0000565154c9f82f aloc prev    10 next    12 size 50832
heap: block    12: 0x0000565154c9f830 - 0x0000565154ca645f aloc prev    11 next    13 size 27696
heap: block    13: 0x0000565154ca6460 - 0x0000565154cac40f aloc prev    12 next    14 size 24496
heap: block    14: 0x0000565154cac410 - 0x0000565154cb82ff aloc prev    13 next    15 size 48880
heap: block    15: 0x0000565154cb8300 - 0x0000565154cc321f aloc prev    14 next    16 size 44832
heap: block    16: 0x0000565154cc3220 - 0x0000565158c5633f FREE prev    15 next     0 size 66662688
</code>

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

===== Observações: =====

Após a implementação do alocador, você deve usá-lo em todo o seu projeto. Nos arquivos ''kernel/*.c'' e ''lib/*.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.

===== Arquivos =====

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 simples
  * ''test/pingpong-memory.txt'': saída esperada do teste
  * ''test/pingpong-mqueue.c'': teste mais complexo

===== Outras informações =====

  * 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]]