O amigão da vizinhança…

Nope… não vou falar do Homem Aranha, aqui… trata-se de um método de alocação de memória chamado Buddy System (Systema “Amigão”, se preferirem). Eis o problema: Tendo, vamos supor, uns 8 GiB de memória RAM, como “alocar” e “dealocar” pedaços de memória menores. Como saber se o resto da memória está livre ou usada?

O primeiro pensamento é manter um mapa contendo o endereço inicial e final de blocos “em uso” e o restante, por exclusão, estará livre, certo? Bem… é um jeito, mas neste caso a lista pode ficar bem grande, logo de cara… Considere que num sistema paginado (memória virtual), com 8 GiB de memória física, temos 2097152 páginas de 4 KiB possíveis e todas elas teriam que estar pré mapeadas, onde muitas estariam marcadas como “livres”. Ora, no modo x86-64 cada tabela de páginas (que tem 4 KiB) suporta apenas 512 entradas. Teríamos que ter 4096 tabelas dessas (totalizando 16 MiB) mais as tabelas de diretórios… É bem mais fácil mapear as PTEs à medida que elas forem necessárias, deixando as entradas de diretórios não usadas zeradas (“livres”). No entanto, o problema continua… Como controlar o que é “livre” e o que é “usado”?

Outra solução é manter arrays com estruturas pequenas, indicando tamanhos de páginas, mas começando com páginas bem grandes… Nas extensões de paginação do modo x86-64 temos a possibilidade de ter páginas de 4 KiB, 2 MiB e 1 GiB. Começamos criando um mapa com 8 “huge pages” de 1 GiB (se possível) “livres”. Quando tentarmos alocar 4 KiB (1 página) o algoritmo vai achar a primeira página de 1 GiB livre e dividí-la em 512 páginas menores de 2 MiB… Dessas a primeira página será dividida em 512 páginas de 4 KiB onde a primeira será mapeada e marcada como “usada”.

Acabaremos com: 1 página de 4 KiB usada, 511 páginas de 4 KiB não usadas, 511 páginas de 2 MiB não usadas e 7 páginas de 1 GiB não usadas… Na próxima alocação o algoritmo varre a lista atrás das menores páginas possíveis (4 KiB). Se achar alguma livre, apropria-se dela, caso contrário tentará achar páginas de 2 MiB e a dividirá, apropriando-se de uma pagininha de 4 KiB… Se não achar páginas de 2 MiB livres, procura pela próxima de 1 GiB e a subdividirá até obter o que quer…

A “dealocação” é apenas questão de marcar os blocos como “livres”. Normalmente não precisaremos reconstruir as páginas maiores, a não ser que o espaço tomado pelas tabelas de páginas esteja muito grande. A reconstrução é simples: Basta percorrer a lista de páginas menores contíguas, contá-las e se conseguirmos 512 páginas, transformá-las em uma única página de tamanho maior “livre”… Geralmente isso não é desejável pelo tempo de processamento extra e porque o sistema estará alocando/dealocando páginas o tempo todo… Sem contar que, a reconstrução de páginas implica na recarga do registrador de controle CR3, que invalidará os Translation Lookaside Buffers, tomando muitos ciclos…

O algorítmo tem lá suas vantagens: A alocação de blocos de 4 KiB, 2 MiB e 1 GiB é bem direta… E a fragmentação será um problema menor do que uma simples lista encadeada… Aliás, uma lista encadeada é necessária apenas para manter o registro dos tamanhos dos blocos e de quais estão em uso ou livres. Algo assim:

struct buddy_node_s {
  struct buddy_node_s *next;
  char used:1;
  char size:2; /* 0 = 4 KiB, 1 = 2 MiB, 2 = 1 GiB */
};

Yep! Cada entrada terá 9 bytes apenas… A lista começará com 72 bytes de tamanho (8 entradas para tamanhos de 1 GiB) e cada entrada será subdividida de acordo com o uso… É claro que o tamanho total, depois de subdivisões em blocos pequenos poderá ter uns 18 MiB apenas para memória física (8 GiB / 4 KiB vezes 9 bytes), mas apenas em casos extremos!

O cálculo do endereço físico base, para ser usado na tabela de paginas, é facilmente calculado com base no tamanho de cada bloco e, para cada subdivisão, um diretório de páginas adicional é criado. As 8 páginas de 1 GiB iniciais usam 8 entradas na PDPT (Page Directory Pointer Table). Quando uma entrada dessas é subdividida, ela apontará para uma PDT (Page Directory Table) com 512 entradas onde apenas algumas delas serão mapeadas (de acordo com a quantidade de páginas de 2 MiB que forem requisitas)… Se tamanhos residuais ou totais menores que 2 MiB foram requisitados, então uma PT (Page Table) será criada com 512 entradas para páginas de 4 KiB…

É claro que podemos ignorar a lista encadeada citada acima e trabalharmos diretamente na estrutura de árvore nas tabelas de página (ainda estou pensando em como fazer isso!), mas a lista intermediária é mais simples e podemos montar uma árvore e depois “ativá-la” mais facilmente (creio!).

Então, o “sistema amigão” simplesmente divide a memória nos maiores blocos possíveis, inicialmente, e vai subdividindo-os à medida que blocos menores forem necessários… As subdivisões sempre são feitas em potências 2^n, mais especificamente, 2^9, no caso da arquitetura Intel x86-64, já que cada tabela de páginas suporta apenas 512 entradas… Quanto à alocação, ele procurará pelos menores blocos que puder encontrar antes de tentar os maiores… Para alocação de tamanhos maiores que 4 KiB e menores que 2 MiB, blocos sequenciais de 4 KiB são procurados. Por exemplo, 15 KiB são mapeados em 4 blocos de 4 KiB (totalizando 16 KiB – o 1 KiB extra fica como um bonus!). Isso se deve ao fato de que 4 KiB é o menor tamanho de bloco alocável para uma página. O mesmo vale para valores maiores que 2 MiB e menores que 1 GiB… 3 MiB, por exemplo, alocará 1 bloco de 2 MiB e 256 blocos de 4 KiB em sequência, particionando o próximo bloco de 2 MiB (se é que não foi particionado ainda) que segue o primeiro.

Atenção: O algoritmo é simples, mas a coisa é mais difícil do que parece: O particionamento sequencial refere-se às páginas, não à memória física… Lembre-se que um endereço linear precisa ser sequencial, mas um físico não! O endereço linear 0x000000000000 pode estar mapeado no primeiro bloco de 4 KiB da memória física, enquanto o endereço 0x000000001000 pode estar no final, mas os endereços lineares parecerão contínuos (de 0x000000000000 até 0x000000000fff [página 0] e de de 0x000000001000 até 0x000000001fff [página 1]).

De fato, o mapeamento dos endereços lineares versus endereços físicos é um troço delicado. Algumas regiões do espaço de endereçamento linear têm que coincidir com o espaço de endereçamento físico (especialmente na inicialização do modo de paginação), mas podemos, por exemplo, mapear a RAM do sistema inteiro como se fosse um grande array contínuo, no espaço linear, sendo que ela é fragmentada no espaço físico (temos ROM, memória de I/O e “buracos”). Considere: As primeiras 128 páginas de 4 KiB são RAM (do endereço físico 0 até 0x80000), segue um possível buraco de 128 KiB (32 páginas de 4 KiB) e a RAM usada pela placa de vídeo (128 KiB, ou, mais 32 páginas). Mais um buraco ou I/O entre 0xC0000 até 0xdffff de 128 KiB (mais 32 páginas) e a ROM (de 0xe0000 até 0xfffff), ou seja, mais 128 KiB:

128 (livres) + 32 (não usáveis) + 32 (video) + 64 (não usáveis?!) = 256 páginas.

Em teoria temos mais 841277 páginas de 4 KiB livres até atingirmos a área usada pelos dispositivos PCI, do endereço 0x00010000 até 0xcd73bfff (no mapa de memória de minha máquina, obtida via /proc/iomap). Isso dá pouco mais que 3,2 GiB, somados às 128 páginas do início da memória baixa. Essas 841405 páginas de RAM que podem ser mapeadas. Páginas de 1 GiB tem que ser alinhadas com os primeiros 30 bits zerados, páginas de 2 MiB com 21 e 4 KiB com os primeiros 12. Assim, teríamos, nas tabelas de páginas, em sequência, 384 páginas de 4 KiB (as 128 primeiras e 1 MiB acima da ROM), segue 1130 páginas de 2 MiB (para completar 1 GiB) e, logo depois, duas páginas de 1 GiB. Faltam ainda 107 páginas de 2 MiB e 189 páginas de 4 KiB.

Ao invés de termos 841405 entradas PTE (ou 1644 PTs), temos  agora 1810! Essa é a força do buddy system. Notem que nessa pré alocação as páginas de 2 MiB e 1 GiB poderão ser subdivididas!

Outro aviso: Eu não considerei aqui a memória “virtual”, apenas um pedaço da física.

Anúncios