1 - Memória

A memória é um dos componentes mais importantes na arquitetura de um computador. Isso reflete na variedade de memórias presentes, atualmente (registradores, cache, RAM, etc), e suas características distintas. Elas, no entanto, precisam ser gerenciadas para que sejam utilizadas de forma inteligente. Um exemplo disso é a RAM, que é uma tipo de memória, obviamente, limitada e existem vários processos que precisam desse recurso ao mesmo tempo.

A memória pode parecer linear e simples quando você acessa, por exemplo, por meio de uma linguagem de alto nível. Mas, por trás de tudo isso, a memória é algo complexo: Precisamos separar áreas de código e dados, e evitar que ambas colidem uma com a outra; As informações armazenadas se fragmentam com facilidade; Processos não podem acessar o espaço de endereço de outro, etc..

Existem vários outros problemas, porém citei apenas alguns. Podemos utilizar de recursos disponibilizadas pelo hardware e algoritmos/técnicas para minimizar ou resolver esses problemas.

Abstrações de hardware como a paginação é um exemplo de recurso que podemos usar para mapear e descrever memória. Além disso, algoritmos de alocação como o Buddy System e Slab organizam a memória de forma que ela possa ser utilizada da melhor forma possível. Esses mecanismos, juntos, são essenciais para o gerenciamento da memória por um kernel.

A partir do que foi dito acima, a simples ação de armazenar bits é mais complexa do que parece. O entendimento disso tudo possibilita que o programador conheça as bases de um kernel, dos recursos gerenciados por esse tipo de software e da arquitetura do processador, na qual pode ajudar no desenvolvimento de software que lidem com isso, seja em nível de kernel ou usuário.

2 - Arquitetura

Cada arquitetura de processador tem sua própria maneira de lidar com a memória. No caso do x86, é fornecido uma abstração em nível de hardware chamada de paginação. Alguns outros como a segmentação veio bem antes, mas teve que ser substituída, pois tinha vários problemas como o limite de memória endereçável, por exemplo. No caso do ARM, também existe paginação, mas tem uma maneira diferente de lidar com isso, então vamos focar apenas no x86, uma vez que falar de duas ou mais arquiteturas estenderia muito o artigo.

Com a paginação, a memória é organizada em páginas, que é um bloco de memória, geralmente, de 4 KiB, em sistemas Linux. O tamanho de uma página influencia várias outras partes do sistema. Um exemplo disso é o sistema de arquivos Ext, que organiza a memória no disco em blocos de 4 KiB. Existem também outros tamanho de páginas, no entanto falaremos disso nos próximos tópicos.

A página é acessada por meio de um endereço linear, onde o tamanho pode variar dependendo do modo de operação do processador. Esse endereço é convertido, pela MMU, para um endereço físico, que em alguns casos pode ou não ser igual ao endereço linear. Essa conversão precisa de uma estrutura hierárquica, na qual irá descrever um conjunto de tabelas e páginas.

2.1 - Paginação de 32 bits

A paginação, no modo protegido, pode ser ablitada setando o bit PG do registrado CR0. Mas, primeiro, deve ser colocado a estrutura de paginação no registrador cr3. Esse registrador será chamado sempre que for necessário a tradução de um endereço linear para um físico.

Em sistemas UEFI, a paginação já vem ativada por padrão e a memória tem um mapeamento 1:1. Com esse tipo de mapeamento significa que o endereço virtual é o mesmo do físico.

Na paginação de 32 bits, podemos usar apenas páginas com 4 KiB e 4 MiB de tamanho. Isso influencia bastante na forma como é organizado o endereço linear. A Figura 2-1 exibe o endereço linear para páginas de 4 KiB.

Todo o endereço linear tem 32 bits de tamanho. Cada campo nesse endereço é um índice em uma tabela. Veja também que cada campo tem um tamanho em bits. Esses tamanhos não foram escolhidos por acaso, mas sim para utilizar, sem desperdício, cada bit.

A especificação diz que o endereço linear pode ser traduzido para um endereço físico de 40 bits de tamanho. Se fizer os calculos, verá que 40 bits podem endereçar até 1 TiB (\(2^{40} = 1099511627776\)) de memória, porém não podemos ter isso tudo de RAM, então esse tamanho de endereço nem chega a ser 40 bits em alguns processadores.

Precisamos que parte do endereço linear seja usada como um deslocamento dentro de uma página. Os primeiros 12 bits (11:0), que são reservados para o Offset, servem exatamente para isso, pois 12 bits (\(2^{12}\) = 4096) é o suficiente para endereçar uma página inteira. Quanto ao Table, ele é um índice em uma Page Table, tabela usada para descrever páginas. Cada entrada nessa tabela vai dizer o endereço físico, permissões de acesso e outros atributos da página descrita pela entrada. Note que o Table tem apenas 10 bits (\(2^{10} = 1024\)), então uma tabela pode ter apenas 1024 entradas. O Directory também é um índice e pode ter até 1024 entradas, entretanto nesse caso ele irá descrever uma Page Directory Table, tabela onde cada entrada aponta para uma Page Table. Isso tudo forma a hierarquia de tabelas que falei acima (Veja a figura 2-2).

Se você fizer um cálculo rápido verá que é possível endereçar até 4 GiB:

Esse é o motivo do seu processador de 32 bits poder usar apenas 4 GiB de RAM. A coisa complica um pouco mais, porque cada entrada nessa tabela tem 4 bytes de tamanho, istó é, cada Directory Table e Page Table tem, no máximo 4 KiB de tamanho (\(4 \cdot 1024 = 4096\)). Para descrever 4 GiB usando páginas de 4 KiB, precisamos de mais ou menos 4 MiB de tabelas:

Veja que \(2^{10} \cdot 2^{10} + 2^{10}\) são todas as entradas de Page Tables e Directory Tables necessárias para mapear 4 GiB. Depois é multiplicado por 4 para calcular o tamanho em bytes das tabelas.

Essa PDE (Page Directory Entry) é uma entrada na Directory Table. Cada entrada tem uma estrutura (Veja a Tabela 2-1) com flags e o endereço físico da Page Table. O endereço da Page Table precisa estar alinhado em 4 KiB, então os 12 primeiros bits são zerados. A Intel aproveitou parte desses bits e usou eles como flags. O mesmo vale para a PTE (Page Table Entry), mas em vez de apontar e descrever uma tabela, ela faz isso para uma página (Veja a Tabela 2-2).

Tabela 2-1: Entrada da PDE para descrever uma página de 4 KiB.

Tabela 2-2: Entrada da PTE para descrever uma página de 4 KiB.

A coisa muda um pouco quando precisamos lidar com páginas de 4 MiB, porque são necessários 22 bits (\(2^{22} = 4194304 = 4 \text{ MiB}\)). Isso será permitido apenas se o bit PS da PDE for igual a 1 (Veja a Tabela 2-1). A Figura 2-3 mostra como é organizado o endereço virtual para páginas de 4 MiB.

A Page Table foi sacrificada para dar mais bit para o campo de Offset. Agora, uma entrada na Directory Table aponta para um tabela de 4 MiB. E, deve haver um alinhamento de 4 MiB no endereço colocado na entrada.

Claro, você só pode mapear 4 GiB de memória linear de uma vez:

Ou seja, a Page Table foi retirada e o Offset aumentou. Um vantagem é que precisamos apenas de uma única tabela de 4 KiB para mapear todo o kernel:

2.2 - Uma breve introdução ao PAE

Com a Paginação PAE as coisas mudam um pouco, porque é adicionado mais um campo no endereço linear (Veja a Figura 2-4) e uma tabela de registradores, chamada de PDPT (Page-Directory-Pointer-Table).

Fazendo um calculo rápido verá que cada PDPTE pode mapear até 1 GiB de memória:

Como são 4 registradores, então podemos mapear até 4 GiB, claro.

O PAE permite também que tabelas de 2 MiB sejam usadas se a flag PS da PDE estiver igual a 1. Olhe a Figura 2-5 e você vera que a Page Table é tirada e agora temos 21 bits para o Offset, ou seja, \(2^{21} = 2097152 = 2 \text{ MiB}\).

2.3 - Paginação de nível 4

Aqui será apenas uma apresentação rápida. Não irei falar da estrutura das entradas de tabela, mas você pode consultar isso na especificação.

Primeiramente, no modo longo, existe dois tipos de paginação: o de nível 4 e o de nível 5. O foco aqui será o primeiro. Com o nível 4, o endereço linear tem 48 bits de tamanho. Isso permite endereçar até 256 TiB (\(2^{48}\)) de memória linear. Esse endereço linear pode ser traduzido para um endereço de até 52 bits. “Mas, com 52 bits não seria possível endereçar até 4 PiB?” Sim, no entanto apenas 256 TiB são possíveis de um vez, devido ao tamanho de 48 bits do endereço liner. Tecnicamente, você não vai encontrar uma memória RAM de 4 PiB, então não precisa se preocupar com isso.

No caso da paginação de nível 5, o endereço linear terá 57 bits de tamanho, ou seja, 128 PiB de memória linar. E o endereço físico pode ter até 52 bits, isto é, 4 PiB de memória física.

A estrutura da tabela para nível 4 é mostrado na Figura 2-6.

Existe também a estrutura para mapear páginas de 2 MiB e 1 GiB. Nesse caso, os bits 20:0 (\(2^{20}\)) serão o offset para as páginas de 2 MiB, e os bits 29:0 (\(2^{30}\))para as de 1 GiB.

2.4 - Um exemplo simples

Como exemplo, eu escrevi um código, em ASM, que mostra o mapeamento de páginas de 2 MiB (Listagem 2-1).

.code64

.equ START_KERNEL, 0xFFFFFFFF80000000

.global _start

.align 4096
.section .text
_start:
  leaq  plm4(%rip), %rax
  movq  %rax, %cr3
  movq  $higher_half_kernel, %rax
  jmp   %rax
higher_half_kernel:
  jmp .

.section .data

.align 4096
plm4:
  .quad identity_pdpt - START_KERNEL + 0x3
  .fill 510, 8, 0
  .quad pdpt - START_KERNEL + 0x3

.align 4096
pdpt:
  .fill 510, 8, 0
  .quad pd - START_KERNEL + 0x3
  .fill 1, 8, 0

.align 4096
identity_pdpt:
  .quad pd - START_KERNEL + 0x3
  .fill 511, 8, 0

.align 4096
pd:
  .set i, 0;
  .rept 512
    .quad i + 0x83
    .set i, i + (1 << 21)
  .endr

Listagem 2-1 (Código que implementa tabelas de paginação e pula para o endereço mapeado)

Vamos analisar esse código por partes. Primeiramente, veja que eu tenho uma macro chamada START_KERNEL (0xFFFFFFFF80000000), que será o endereço linear do início do nosso kernel.

Note que existe um plm4 com entradas de 8 bytes:

.align 4096
plm4:
  .quad identity_pdpt - START_KERNEL + 0x3
  .fill 510, 8, 0
  .quad pdpt - START_KERNEL + 0x3

A diretiva .quad cria um espaço de 8 bytes, na qual irá receber o valor resultado da expressão que vem depois. Essa subtração do pdpt pela START_KERNEL vai resultar no endereço físico da tabela. Lembre também que o endereço deve estar alinhado em 4 KiB. A soma com 0x3 (0b11) vai setar os dois primeiros bits, bit 1 e 0, que são os bits P (para definir se uma página esta presente) e o bit R/W (para permissão de escrita), respectivamente.

Claro, essa primeira entrada vai apontar para identity_pdpt, que também vai apontar para outra tabela (pd):

.align 4096
identity_pdpt:
  .quad pd - START_KERNEL + 0x3
  .fill 511, 8, 0

A pd, por outro lado, não aponta para outra tabela, mas sim para as páginas que essa estrutura toda está mapeando:

.align 4096
pd:
  .set i, 0
  .rept 512
    .quad i + 0x83
    .set i, i + (1 << 21)
  .endr

A .rept vai repetir 512 vezes um bloco de diretivas (O .quad e.set, nesse caso) e o .endr vai definir o final. Dito isso, é fácil notar que serão criadas 512 entradas, onde cada uma vai receber i + 0x83. Com 0x83 (0b10000011), o bit 8 vai ser setado. Se você olhar a especificação, verá que se esse bit ficar setado, a tabela deve apontar para páginas de 2 MiB. Depois disso, o .set vai incrementar o i de 2 em 2 MiB, ou seja, vai ser mapeado 1 GiB (\(512 \cdot 2 \text{ MiB}\)) de memória.

Essas tabelas prefixada com “identity” são para um mapemanto 1:1. Como os índices da pdpt na plm4 e o da pd na pdpt são 0, então deve ser assim também no endereço linear caso você queria acessar essas entradas, isto é, será mapeado até 0x3fffffff (\((1 \cdot 1 \cdot 2^9 \cdot 2 \text{ MiB}) - 1\), onde 9 é o tamanho em bits do campo no endereço linear para os índices da pd)

Veja que a plm4 também preenche 510 entradas (.fill 510, 8, 0) com zero. Depois disso, a entrada 511 aponta para a pdpt. E, a última entrada na pdpt, também 511, aponta para a pd:

pdpt:
  .fill 510, 8, 0
  .quad pd - START_KERNEL + 0x3
  .fill 1, 8, 0

Esses são os mesmo índices no endereço base do kernel (0xFFFFFFFF80000000). Se pegar os bits desse endereço em 47:39 e 38:30 irão são 511 e 510, respectivamente. E, graças a pd, podemos acessar até 1 GiB a partir desse endereço base.

Alguns kernel (Linux, por exemplo) são mapeados para endereços que ficam bem perto do final do espaço de endereço linear (geralmente um endereço como 0xFFFFFFFF80000000, como acima). Depois que o CR3 é alterado com o mapeamento dos endereços altos, o código ainda continua executando no antigo espaço de endereços, ou seja, se o kernel estiver executando no endereço 0x1000000 e depois apenas o 0xFFFFFFFF80000000 em diante fica mapeado (após o CR3 ser alterado), então vai acontecer um Page Fault. Para resolver isso deve haver um mapeamento 1:1, assim o kernel vai conseguir usar a instrução jmpl para chegar nos endereços altos.

2-5 - Mapeando 1 GiB de uma só tacada

Você deve ter notado que quanto maior o tamanho da página, menor é o número de níveis de tabelas necessários. O equivalente das tabelas acima usando páginas de 1 GiB é mais simples (Listagem 2-2).

.align 4096
plm4:
  .quad pdte - START_KERNEL + 0x3
  .fill 510, 8, 0
  .quad pdte - START_KERNEL + 0x3

.align 4096
pdte:
  .quad 0 + 0x83 # Para o mapeamento 1:1
  .fill 509, 8, 0
  .quad 0 + 0x83 # Para os endereços altos
  .quad 0

Listagem 2-2 (Uso de páginas de 1 GiB)

Embora a implementação seja simples, eu não recomendo o uso de páginas de 2 MiB e 1 GiB como padrão. 4 KiB é o ideal, pois não é um tamanho nem tão grande e nem tão pequeno. Imagine você precisando mapear um frame buffer de 4196352 bytes e ver que esse valor tem 2048 (\(4196352 - 4 \text{ MiB}\)) bytes a mais que 4 MiB, portanto você precisara de mais uma página de 2 MiB apenas para mapear esses bytes. Bom, não preciso nem dizer que com 1 GiB o desperdício seria maior ainda.