Paginação e Memória Virtual

Paginação é o mecanismo pelo qual uma CPU traduz endereços virtuais (os endereços que o código de fato usa) em endereços físicos, as localizações reais na RAM às quais esses endereços correspondem. Todo endereço que um programa em execução toca, de busca de instrução a leitura de dados, passa por essa tradução, realizada por hardware dedicado (a memory management unit) consultando um conjunto de tabelas em memória que o sistema operacional constrói e mantém.

Por que memória virtual

Sem tradução, todo programa precisaria conhecer os endereços físicos exatos da memória que usa, e quaisquer dois programas rodando ao mesmo tempo precisariam de memória física disjunta reservada para eles por convenção, em vez de aplicação forçada: um bug em um programa poderia silenciosamente corromper a memória de outro, ou a do próprio kernel. A paginação resolve os dois problemas dando a cada processo seu próprio mapeamento independente de um espaço de endereçamento virtual privado para memória física: dois processos podem usar o mesmo endereço virtual idêntico para dados inteiramente diferentes, já que o hardware traduz cada um através de um conjunto diferente de tabelas, e um processo não tem como construir um endereço virtual que resolva para memória física fora de seus próprios mapeamentos, porque é o próprio mapeamento que teria que permitir isso.

A paginação também habilita capacidades sem equivalente em um sistema que endereça memória física diretamente. O espaço de endereçamento virtual de um processo pode parecer contíguo mesmo quando a memória física que o sustenta está espalhada pela RAM em localizações não relacionadas, já que só o mapeamento precisa ser contíguo, não os frames subjacentes. Memória pode ser mapeada de forma preguiçosa, com uma página só sendo fisicamente sustentada na primeira vez que é de fato tocada. E mais memória virtual pode ser prometida a um processo do que memória física realmente existe para sustentá-la, com a diferença compensada movendo páginas raramente usadas para o disco, caso o sistema operacional implemente swapping.

A hierarquia de tradução

Em vez de uma tabela plana única mapeando todo endereço virtual possível (o que seria impraticavelmente grande), a paginação em x86-64 usa uma árvore de tabelas em múltiplos níveis, cada nível restringindo parte do endereço até que o frame físico final seja identificado. Na configuração mais comum, um endereço virtual de 64 bits é dividido em seis partes: 16 bits que atualmente precisam ser uma extensão de sinal do bit 47 (limitando a faixa efetivamente utilizável a 48 bits), quatro índices de 9 bits selecionando uma entrada em cada um de quatro níveis de tabela, e um offset de 12 bits dentro da página final de 4 KB.

Nível	Tabela	Índices	Entradas
4	PML4 (Page Map Level 4)	bits 47:39	512
3	PDPT (Page Directory Pointer Table)	bits 38:30	512
2	PD (Page Directory)	bits 29:21	512
1	PT (Page Table)	bits 20:12	512

Cada tabela contém 512 entradas de oito bytes, e cada entrada aponta ou para a próxima tabela abaixo ou, no nível final, para um frame de página física. CR3 contém o endereço físico da tabela PML4 de nível superior para qualquer espaço de endereçamento atualmente ativo; trocar CR3, como acontece em toda troca de contexto entre processos, troca todo o mapeamento que a CPU usa, sem precisar atualizar os próprios mapeamentos.

Uma entrada de tabela de página empacota um endereço físico junto com vários bits de controle no espaço restante:

Bit	Significado
0	Present: precisa estar definido, ou todo outro bit é ignorado e qualquer acesso falha
1	Writable
2	User-accessible: se limpo, restringe a página apenas ao ring 0
3	Cache write-through
4	Cache desabilitado: definido para um mapeamento MMIO para que a CPU nunca sirva uma leitura cacheada desatualizada
5	Accessed: definido pela CPU, nunca limpo pelo hardware
6	Dirty (apenas entradas de page table): definido pela CPU em uma escrita
7	Page size (huge page) no nível PD/PDPT, ou PAT no nível final
63	No-execute: exige o recurso NX habilitado via uma MSR, uma das mitigações de segurança cobertas separadamente

Percorrendo as tabelas

Em todo acesso à memória, a CPU pega o endereço virtual, o divide nos índices acima, e percorre a partir de CR3 descendo por cada nível de tabela, usando cada índice para selecionar a próxima entrada, até alcançar uma entrada presente no nível final apontando para um frame físico; nesse momento o offset de 12 bits da página é adicionado diretamente, já que offsets dentro de uma página não exigem tradução. Se qualquer tabela percorrida no caminho tiver seu present bit limpo, ou o acesso violar as permissões codificadas em uma entrada (escrever em uma página somente leitura, ou executar uma página no-execute), a CPU gera um page fault em vez de completar o acesso.

Realizar esse percurso de quatro níveis em todo acesso individual à memória seria lento demais, então a CPU armazena traduções recentes em cache em um translation lookaside buffer (TLB) e só realiza o percurso completo em um TLB miss. Esse cache é o que torna mudar um mapeamento mais envolvido do que simplesmente reescrever a entrada de tabela de página correspondente: uma entrada de TLB desatualizada para aquele endereço virtual ainda pode existir e continuará sendo usada até ser explicitamente invalidada, seja para uma única página com a instrução invlpg, ou, de forma menos seletiva, recarregando CR3 por completo, o que descarta toda entrada de TLB não global associada ao espaço de endereçamento anterior de uma vez.

Huge pages

Definir o bit de tamanho de página (bit 7) no nível PD ou PDPT, em vez de descer até uma page table completa, produz uma página de 2 MB (no nível PD) ou de 1 GB (no nível PDPT) em vez da página usual de 4 KB, mapeada diretamente por essa única entrada. Como um TLB tem um número fixo de entradas independentemente de quanta memória cada uma cobre, mapear uma região grande com huge pages permite que muito mais dela permaneça residente no TLB de uma vez: uma carga de trabalho tocando gigabytes de memória pode esgotar rapidamente a cobertura de um TLB de páginas de 4 KB, enquanto a mesma memória mapeada com páginas de 2 MB precisa de mil vezes menos entradas para cobrir a mesma faixa. A troca é proteção e alocação de granularidade mais grosseira: uma região inteira de 2 MB ou 1 GB compartilha um único conjunto de bits de permissão e é sustentada como uma única unidade, o que desperdiça memória se apenas uma pequena parte dela é de fato usada.

Page faults

Um page fault (#PF, vetor 14) não é necessariamente uma condição de erro: é o mecanismo que a paginação usa para notificar o software de que um acesso não pôde ser completado apenas pelo hardware, e um handler de page fault deve distinguir várias situações genuinamente diferentes usando o código de erro empilhado junto com a falha. O bit 0 do código de erro diz se a falha foi causada por uma página que não estava presente, versus uma que estava presente mas violou uma verificação de permissão; o bit 1 diz se o acesso ofensor era uma escrita; o bit 2 diz se ele se originou de user mode.

Dois usos comuns e deliberados desse mecanismo são demand paging e copy-on-write. Demand paging mapeia uma página como não presente inicialmente e só aloca e preenche um frame físico real na primeira vez que uma falha ocorre nela, adiando o custo de sustentar a memória até que ela seja de fato usada: a base de carregar o código de um executável sem ler o arquivo inteiro para a memória de antemão. Copy-on-write mapeia uma página como somente leitura em dois ou mais espaços de endereçamento que, logicamente, cada um acredita ter sua própria cópia privada e gravável; a primeira escrita de qualquer lado gera uma falha, e o handler nesse momento aloca uma cópia privada real e atualiza o mapeamento daquele espaço de endereçamento, deixando o mapeamento do outro lado, e o frame físico original, intocados. Isso é o que torna fork barato apesar de parecer duplicar um espaço de endereçamento inteiro: nenhuma memória física é de fato copiada, a menos e até que um dos lados escreva nela.

Habilitando a paginação

A paginação é controlada pelo bit 31 de CR0 (PG). Defini-lo exige que CR3 já esteja apontando para uma tabela de nível superior válida, já que a própria próxima busca de instrução depois que PG é definido será ela mesma traduzida através das tabelas recém-instaladas: um kernel habilitando paginação precisa já ter mapeado por identidade, ou de outra forma corretamente mapeado, o código atualmente em execução, ou a máquina falha imediatamente em uma busca de instrução que não consegue resolver. O long mode agrava isso: transicionar para long mode de 64 bits exige que a paginação já esteja habilitada com PAE (Physical Address Extension, bit 5 de CR4) ativo, já que o formato de tabela de página do long mode é o formato PAE estendido com um nível adicional de tabela, e a CPU recusará a transição para long mode com PAE desligado.

Notas de implementação

Em um sistema multiprocessado, mudar um mapeamento que outra CPU possa ter em cache em seu próprio TLB exige mais do que atualizar a tabela e descartar o TLB local: um TLB shootdown é necessário, tipicamente implementado enviando uma interrupção entre processadores para toda outra CPU que possa manter a entrada desatualizada, cada uma das quais então executa seu próprio invlpg local ou recarregamento de CR3 em resposta, antes que a operação seja considerada completa. Pular isso em SMP produz uma classe rara e difícil de reproduzir de bug, onde uma CPU atualiza um mapeamento enquanto outra continua silenciosamente usando a tradução antiga, agora incorreta.

Uma técnica de implementação comum para acessar tabelas de página de dentro do próprio kernel é o mapeamento recursivo: uma entrada da PML4 de nível superior é feita apontar de volta para a própria tabela PML4, em vez de para uma PDPT. Como a lógica de percurso de página da CPU não distingue esse caso de qualquer outro, esse truque torna toda tabela de página, em todo nível, endereçável através de uma faixa previsível e fixa de endereços virtuais, sem que o kernel precise rastrear separadamente ou mapear fisicamente a localização de cada tabela; percorrer a entrada recursiva o número certo de vezes chega a qualquer tabela que o kernel precise inspecionar ou modificar.

Referências

^ Intel, Intel 64 and IA-32 Architectures Software Developer’s Manual, Volume 3A, Capítulo 4: define o formato de entrada de tabela de página e o processo de tradução referenciados ao longo deste artigo.
^ AMD, AMD64 Architecture Programmer’s Manual, Volume 2, Capítulo 5: a referência correspondente de paginação em long mode.

Ver também

Physical Memory: o alocador de frames do qual as tabelas de página tiram endereços físicos.
Long Mode: o modo de 64 bits cuja sequência de entrada exige que a paginação já esteja ativa.
Port I/O versus Memory-Mapped I/O: por que um mapeamento MMIO precisa do bit de cache desabilitado acima definido.
Model-Specific Registers: o mecanismo por trás do bit de habilitação de NX referenciado acima.
Mitigações de Segurança: o bit NX, e SMEP/SMAP ao lado dele, cobertos como parte da postura mais ampla de um kernel contra exploração de bugs.
TLB Shootdown: o protocolo de invalidação entre CPUs que as notas de implementação deste artigo só resumem.
Buffer Cache: um tipo diferente de cache, guardando blocos de disco em vez de traduções de endereço.
Áudio (AC97/HDA): um dispositivo capaz de DMA cujos buffers de amostra precisam exatamente do mapeamento fisicamente contíguo que este artigo descreve.
IPC: memória compartilhada, um uso deliberado do mesmo mecanismo de múltiplos mapeamentos para um frame coberto aqui.