Thobias Salazar Trevisan
(15/03/2002)
e-mail: thobias
at cos.ufrj.br
Este texto tem como base as arquiteturas 80x86, deste
modo diversas partes não se aplicam a outros processadores.
As estruturas de dados que mapeiam endereço virtual
para físico são as tabelas de página (page tables),
que são armazenada na memória principal e deve ser inicializada
pelo kernel antes de habilitar paginação.
MMU (Memory Management Unit), dispositivo de hardware
que realiza a tradução de endereço virtual para físico.
A MMU está localizada dentro do chip dos processadores.
O programa do usuário lida com endereços virtuais, ele
nunca trata os endereços físicos. Assim cada processo
tem o seu espaço de endereçamento virtual, ou seja,
a página 0 de um processo não é a página 0 de outro
processo. Neste esquema de page tables e MM, cada acesso
a dado ou instrução requer dois acessos a memória, um
para a page tables e outro para o dado ou instrução.
Este problema é resolvido com o uso de uma cache associativa
chamada TLB (Translation Lookaside Buffer), que é uma
cache para a MMU, ou seja, os endereços traduzidos pela
MMU são armazenados na TLB, assim acessos futuros a
este endereço serão rapidamente traduzidos sem acessar
a memória.
Quando a MMU não consegue traduzir um endereço, por
exemplo, quando o endereço virtual é inválido ou quando
não existe uma página física para o endereço virtual,
é gerado um page fault (falha de página), o qual o kernel
resolve. Isto será discutido mais adiante.
Para invalidar uma entrada da TLB é usada a intrução
"invlpg".
Para invalidar todas as entradas da TLB, simplesmente
escreve-se no registrador cr3, o qual aponta para a
Page Directory corrente.
movl %cr3 %eax
movl %eax %cr3
Para isto, o kernel utiliza as funções flush_tlb_page
e flush_tlb() respectivamente.
Outras funções para flush da TLB podem ser encontradas
em: include/asm-i386/pgalloc.h
e arch/i386/kernel/smp.c
A instrução "invlpg" não
existe em i386, somente em 486+. O conjunto de instruções
dos processadores 80x86 pode ser encontrado em http://linuxcompressed.sourceforge.net/intel/
Quando um programa acessa um endereço virtual (lógico),
a CPU traduz o endereço virtual para endereço físico
para acessar a memória física na posição correta. Para
isto o endereço lógico é dividido em 3 partes em arquiteturas
x86, onde o endereço é de 32 bits. Os 10 bits mais significativos
para o diretório de página, os 10 bits intermediários
para a tabela de página e os últimos 12 bits para o
offset. O endereço físico do diretório de página é armazenado
no registrador cr3, deste modo os 10 bits mais significativos
do endereço significam a entrada no diretório de páginas
que aponta para tabela de páginas adequada. Os 10 bits
intermediários determinam a entrada na tabela de páginas
que contém o endereço físico da page frame (página física)
que contém a página. Os últimos 12 bits determinam a
posição dentro da page frame. O offset é 12 bits, deste
modo cada página consiste em 4096 bytes de dados, ou
seja, 4KB. Cada processo tem seu próprio diretório de
páginas e seu próprio conjunto de tabela de páginas.
Quando uma troca de processo (process switching) ocorre,
dentre as inúmeras instruções que o kernel realiza,
uma é guardar o conteúdo do registrador cr3 do processo
corrente, e setar o registrador cr3 com o endereço do
diretório de página do processo que irá rodar, deste
modo o processo que irá rodar acessará o seu diretório
de página e o seu conjunto de tabela de páginas correto.
Foi introduzido nos modelos Pentium, processadores
80x86, o extended paging, o qual permite as page frames
terem o tamanho de 4KB ou 4MB. Deste modo o endereço
é dividido em 2 campos. 10 bits mais significativos
para o diretório e os outros 22 bits para o offset.
Paginação com dois níveis é usada em processadores
de 32 bits. Mas existem diversos processadores de 64
bits como Alpha, UltraSPARC, etc. Neste caso paginação
com dois níveis não seria muito eficiente, deste modo,
estas arquiteturas utilizam três níveis. O modo para
a tradução do endereço é o mesmo, somente é acrescentado
uma outra tabela, chamada tabela de diretório intermediária
(PMD). Os três níveis são:
- PGD (Page Global Directory), diretório global de
página
- PMD (Page Middle Directory), diretório intermediário
de página
- PT (Page Table), tabela de página.
O Linux utiliza o modelo de paginação de três níveis,
mesmo quando o hardware suporta somente dois níveis,
como os processadores 80x86 por exemplo. O que acontece
é que o kernel elimina o campo PMD dizendo que ele tem
0 bits, ou seja, continua usando os 10 bits para o diretório
global de página, 10 bits para tabela de páginas e 12
bits para o offset. Entretanto, a posição da PMD na
sequência de ponteiros é mantida, deste modo o mesmo
código roda sobre arquiteturas de 32 bits e 64 bits.
O kernel mantém uma posição para a PMD, setando esta
com apenas uma entrada e mapeando esta única entrada
para o diretório de página adequado.
pgd_t, pmd_t e pte_t são tipos de dados de 32 bits
que representam, respectivamente, uma entrada no diretório
de página global, uma entrada no diretório de página
intermediário e uma entrada na tabela de página.
Dê uma olhada nas macros que o kernel utiliza
para manipular as entradas de cada nível, elas estão
definidas em include/asm-i386/page.h
e include/asm-i386/pgtable.h
Agora que já temos uma idéia de como as coisas funcionam,
vamos ver como o kernel mantém as informações sobre
o espaço de memória do processo.
Todas as informações relacionadas com o espaço de endereçamento
do processo estão incluídas na estrutura referenciada
pelo campo mm no descritor
do processo (struct task_struct).
O campo mm é um ponteiro
para a estrutura mm_struct,
que pode ser encontrada em include/linux/sched.h.
Assim, cada processo tem uma mm_struct.
O linux implementa a área virtual de memória (VMA)
através da estrutura vm_area_struct,
que pode ser encontrada em include/linux/mm.h.
Uma VMA é um intervalo contíguo de endereço linear
que contém as mesmas FLAGs de permissões, ou seja, uma
região homogênea. Assim, cada processo tem uma
lista de VMA.
Todas as regiões de memória do processo são lincadas.
O kernel encontra uma área de memória através
do campo mmap da mm_struct.
Para evitar uma pesquisa linear nesta lista de VMAs,
o kernel utiliza uma red black tree. Isto ocorreu na
versão 2.4.10 do kernel, as versões anteriores utilizavam
uma lista encadeada simples para manter a lista das
VMAs, e quando o número de VMAs alcançava 32 ele usava
uma AVL tree. Nas versões acima da 2.4.10, ele sempre
utiliza uma rb tree. A qual tem um algoritmo mais eficiente
de pesquisa, insert, etc. Assim, quando o kernel tem
um endereço e quer encontrar a qual VMA este endereço
pertence, ele usa a função find_vma,
que pode ser encontrada em mm/mmap.c.
As regiões de memória de cada processo podem ser acessadas
através de /proc/pid/maps onde pid é o id do
processo. Alguns campos da vm_area_struct
são:
- vm_star e vm_end:
endereços de memória virtual de início e de fim da
VMA, ou seja, eles mostram a faixa de endereço que
a VMA pertence;
- vm_mm: um ponteiro para
a mm_struct;
- vm_next: aponta para
a próxima VMA;
- vm_file: pode ser um
arquivo mapeado em memória, como por exemplo, uma
biblioteca, o código do programa (chamado de text),
etc. Este campo também pode ser NULL para um mapeamento
anônimo, por exemplo quando você aloca memória
dinâmica;
- vm_ops: um conjunto
de funções que o kernel deve chamar para operar sobre
esta área. Este campo é um ponteiro para a estrutura
vm_operations_struct.
Um dos campos da vm_operations_struct
é o nopage. Quando um processo
tenta acessar uma página que não está na memória e pertence
a uma VMA válida, ou seja, tem um endereço válido, este
método é chamado (se estiver definido) para esta VMA.
Se o método nopage não estiver definido para esta área
o kernel aloca uma página vazia.
A rotina que manipula os page fault é a do_page_fault.
Page fault pode ocorrer quando uma página não está na
memória, quando um processo viola as proteções a nível
de página, como ao tentar gravar em uma página somente
leitura, etc. Assim o Linux usa paginação sob demanda,
ou seja, as páginas só são trazidas para a memória quando
forem acessadas. Quando uma destas situações
ocorre o kernel chama do_page_fault.
Esta função recebe o endereço da estrutura pt_regs
contendo os valores dos registradores do processador
quando a exceção ocorreu e o error_code
que indica qual o tipo de erro que ocorreu para gerar
o page fault. O endereço que causou a exceção esta no
registrador %cr2, a função move o conteúdo do registrador
para a variável local address, depois tenta localizar
a VMA através do find_vma,
etc. Após garantir que o endereço pertence a uma VMA,
e diversas outros testes realizados, a função do_page_fault
chama a handle_mm_fault
para disponibilizar uma página para o endereço. Agora
dê uma olhada nesta função que as coisas vão ficar
mais claras.
Agora que você já tem uma visão básica de como
MM funciona no kernel, dê uma olhada no módulo
my_mmap, na seção
de exemplos de códigos.
Referências:
|
