Como funciona a paginação x86?

90

Esta questão pretende preencher o vazio de boas informações gratuitas sobre o assunto.

Acredito que uma boa resposta caberá em uma grande resposta do SO ou pelo menos em algumas respostas.

O objetivo principal é fornecer aos iniciantes apenas informações suficientes para que possam ler o manual por conta própria e entender os conceitos básicos do sistema operacional relacionados à paginação.

Diretrizes sugeridas:

  • as respostas devem ser amigáveis ​​para iniciantes:
    • exemplos concretos, mas possivelmente simplificados são muito importantes
    • aplicações dos conceitos mostrados são bem-vindos
  • citar recursos úteis é bom
  • pequenas digressões sobre como os sistemas operacionais usam recursos de paginação são bem-vindas
  • Explicações PAE e PSE são bem-vindas
  • pequenas digressões em x86_64 são bem-vindas

Perguntas relacionadas e por que eu acho que eles não são tolos:

Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
fonte
1
Deve ser marcado como "faq" e marcado como "wiki da comunidade".
Kerrek SB
@KerrekSB Eu realmente não sei como lidar com esse tipo de pergunta. As respostas devem ser wikis da comunidade, é isso? Não consegui encontrar uma faqtag.
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
3
Eu diria que a resposta curta é, "leia o Vol 3, Capítulo 4: Paginação no Manual da Intel". É muito claro, conciso e bem escrito, e não tem mais autoridade.
Kerrek SB
4
@KerrekSB Concordo que o manual é claro e confiável, mas foi um pouco duro como primeira leitura para mim, eu precisava de alguns exemplos simples e concretos + justificativa para entender melhor as coisas.
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功

Respostas:

142

Versão desta resposta com um bom sumário e mais conteúdo .

Vou corrigir qualquer erro relatado. Se você quiser fazer grandes modificações ou adicionar um aspecto ausente, faça-as em suas próprias respostas para obter uma representação bem merecida. Pequenas edições podem ser mescladas diretamente no.

Código de amostra

Exemplo mínimo: https://github.com/cirosantilli/x86-bare-metal-examples/blob/5c672f73884a487414b3e21bd9e579c67cd77621/paging.S

Como tudo na programação, a única maneira de realmente entender isso é brincar com exemplos mínimos.

O que torna este um assunto "difícil" é que o exemplo mínimo é grande porque você precisa fazer seu próprio sistema operacional pequeno.

Manual da Intel

Embora seja impossível entender sem exemplos em mente, tente se familiarizar com os manuais o mais rápido possível.

A Intel descreve o paging no Manual da Intel Volume 3 System Programming Guide - 325384-056US Setembro de 2015, Capítulo 4 "Paging".

Especialmente interessante é a Figura 4-4 "Formatos de CR3 e entradas de estrutura de paginação com paginação de 32 bits", que fornece as principais estruturas de dados.

MMU

A paginação é feita pela unidade de gerenciamento de memória (MMU) da CPU. Como muitos outros (por exemplo, coprocessador x87 , APIC ), isso costumava ser por chip separado nos primeiros dias, que mais tarde foi integrado à CPU. Mas o termo ainda é usado.

Fatos gerais

Os endereços lógicos são os endereços de memória usados ​​no código de terreno do usuário "normal" (por exemplo, o conteúdo de rsiin mov eax, [rsi]).

Primeiro, a segmentação os traduz em endereços lineares e, em seguida, a paginação traduz os endereços lineares em endereços físicos.

(logical) ------------------> (linear) ------------> (physical)
             segmentation                 paging

Na maioria das vezes, podemos pensar em endereços físicos como a indexação de células de memória de hardware RAM reais, mas isso não é 100% verdadeiro devido a:

Paging só está disponível no modo protegido. O uso de paginação no modo protegido é opcional. A paginação está ativada se o PGbit do cr0registro estiver definido.

Paging vs segmentação

Uma das principais diferenças entre paginação e segmentação é que:

  • paging divide a RAM em blocos de tamanhos iguais chamados de páginas
  • a segmentação divide a memória em pedaços de tamanhos arbitrários

Esta é a principal vantagem da paginação, uma vez que pedaços de tamanhos iguais tornam as coisas mais gerenciáveis.

O paging se tornou tão mais popular que o suporte para segmentação foi abandonado no x86-64 no modo de 64 bits, o principal modo de operação para o novo software, onde só existe no modo de compatibilidade, que emula IA32.

Inscrição

Paging é usado para implementar espaços de endereços virtuais de processos no sistema operacional moderno. Com endereços virtuais, o sistema operacional pode caber dois ou mais processos simultâneos em uma única RAM de forma que:

  • ambos os programas não precisam saber nada sobre o outro
  • a memória de ambos os programas pode aumentar e diminuir conforme necessário
  • a troca entre programas é muito rápida
  • um programa nunca pode acessar a memória de outro processo

A paginação veio historicamente após a segmentação e a substituiu amplamente para a implementação de memória virtual em sistemas operacionais modernos como o Linux, uma vez que é mais fácil gerenciar os pedaços de memória de tamanho fixo das páginas em vez de segmentos de comprimento variável.

Implementação de hardware

Como a segmentação em modo protegido (onde a modificação de um registro de segmento dispara uma carga do GDT ou LDT), o hardware de paginação usa estruturas de dados na memória para fazer seu trabalho (tabelas de páginas, diretórios de páginas, etc.).

O formato dessas estruturas de dados é fixado pelo hardware , mas cabe ao sistema operacional configurar e gerenciar essas estruturas de dados na RAM corretamente e dizer ao hardware onde encontrá-las (via cr3).

Algumas outras arquiteturas deixam a paginação quase completamente nas mãos do software, portanto, um erro TLB executa uma função fornecida pelo sistema operacional para percorrer as tabelas de página e inserir o novo mapeamento no TLB. Isso deixa os formatos de tabela de página a serem escolhidos pelo sistema operacional, mas torna improvável que o hardware seja capaz de sobrepor passeios de página com a execução fora de ordem de outras instruções, como o x86 pode .

Exemplo: esquema simplificado de paginação de nível único

Este é um exemplo de como a paginação opera em uma versão simplificada da arquitetura x86 para implementar um espaço de memória virtual.

Tabelas de página

O sistema operacional pode fornecer as seguintes tabelas de página:

Tabela de página fornecida ao processo 1 pelo sistema operacional:

RAM location        physical address   present
-----------------   -----------------  --------
PT1 + 0       * L   0x00001            1
PT1 + 1       * L   0x00000            1
PT1 + 2       * L   0x00003            1
PT1 + 3       * L                      0
...                                    ...
PT1 + 0xFFFFF * L   0x00005            1

Tabela de página fornecida ao processo 2 pelo sistema operacional:

RAM location       physical address   present
-----------------  -----------------  --------
PT2 + 0       * L  0x0000A            1
PT2 + 1       * L  0x0000B            1
PT2 + 2       * L                     0
PT2 + 3       * L  0x00003            1
...                ...                ...
PT2 + 0xFFFFF * L  0x00004            1

Onde:

  • PT1e PT2: posição inicial das tabelas 1 e 2 na RAM.

    Os valores da amostra: 0x00000000, 0x12345678, etc.

    É o sistema operacional que decide esses valores.

  • L: comprimento de uma entrada da tabela de página.

  • present: indica que a página está presente na memória.

As tabelas de páginas estão localizadas na RAM. Eles podem, por exemplo, estar localizados como:

--------------> 0xFFFFFFFF


--------------> PT1 + 0xFFFFF * L
Page Table 1
--------------> PT1


--------------> PT2 + 0xFFFFF * L
Page Table 2
--------------> PT2

--------------> 0x0

As localizações iniciais na RAM para ambas as tabelas de página são arbitrárias e controladas pelo sistema operacional. Depende do sistema operacional garantir que eles não se sobreponham!

Cada processo não pode tocar em nenhuma tabela de página diretamente, embora possa fazer solicitações ao SO que faça com que as tabelas de página sejam modificadas, por exemplo, pedindo uma pilha maior ou segmentos de heap.

Uma página é um pedaço de 4 KB (12 bits) e, como os endereços têm 32 bits, apenas 20 bits (20 + 12 = 32, portanto 5 caracteres em notação hexadecimal) são necessários para identificar cada página. Este valor é fixado pelo hardware.

Entradas de tabela de página

Uma tabela de páginas é ... uma tabela de entradas da tabela de páginas!

O formato exato das entradas da tabela é fixado pelo hardware .

Neste exemplo simplificado, as entradas da tabela de páginas contêm apenas dois campos:

bits   function
-----  -----------------------------------------
20     physical address of the start of the page
1      present flag

portanto, neste exemplo, os designers de hardware poderiam ter escolhido L = 21.

A maioria das entradas da tabela da página real possui outros campos.

Seria impraticável alinhar as coisas em 21 bits, pois a memória é endereçável por bytes e não por bits. Portanto, mesmo que apenas 21 bits sejam necessários neste caso, os projetistas de hardware provavelmente escolheriam L = 32tornar o acesso mais rápido e apenas reservar os bits restantes para uso posterior. O valor real para Lem x86 é de 32 bits.

Tradução de endereços em esquema de nível único

Uma vez que as tabelas de página tenham sido configuradas pelo sistema operacional, a tradução de endereços entre os endereços linear e físico é feita pelo hardware .

Quando o sistema operacional deseja ativar o processo 1, ele define o cr3como PT1, o início da tabela do processo um.

Se o Processo 1 deseja acessar o endereço linear 0x00000001, o circuito de hardware de paging faz automaticamente o seguinte para o SO:

  • dividir o endereço linear em duas partes:

    | page (20 bits) | offset (12 bits) |
    

    Portanto, neste caso, teríamos:

    • página = 0x00000
    • deslocamento = 0x001
  • olhe para a tabela 1 da página porque cr3aponta para ela.

  • olhe a entrada 0x00000porque essa é a parte da página.

    O hardware sabe que essa entrada está localizada no endereço RAM PT1 + 0 * L = PT1.

  • uma vez que está presente, o acesso é válido

  • pela tabela de páginas, a localização do número da página 0x00000está em 0x00001 * 4K = 0x00001000.

  • para encontrar o endereço físico final, só precisamos adicionar o deslocamento:

      00001 000
    + 00000 001
      -----------
      00001 001
    

    porque 00001é o endereço físico da página pesquisada na tabela e 001é o deslocamento.

    Como o nome indica, o deslocamento é sempre simplesmente adicionado ao endereço físico da página.

  • o hardware então obtém a memória naquele local físico.

Da mesma forma, as seguintes traduções aconteceriam para o processo 1:

linear     physical
---------  ---------
00000 002  00001 002
00000 003  00001 003
00000 FFF  00001 FFF
00001 000  00000 000
00001 001  00000 001
00001 FFF  00000 FFF
00002 000  00002 000
FFFFF 000  00005 000

Por exemplo, ao acessar o endereço 00001000, a parte da página é que 00001o hardware sabe que sua entrada na tabela da página está localizada no endereço RAM: PT1 + 1 * L( 1por causa da parte da página), e é onde ele a procurará.

Quando o sistema operacional deseja mudar para o processo 2, tudo o que precisa fazer é cr3apontar para a página 2. É simples assim!

Agora, as seguintes traduções aconteceriam para o processo 2:

linear     physical
---------  ---------
00000 002  00001 002
00000 003  00001 003
00000 FFF  00001 FFF
00001 000  00000 000
00001 001  00000 001
00001 FFF  00000 FFF
00003 000  00003 000
FFFFF 000  00004 000

O mesmo endereço linear se traduz em diferentes endereços físicos para diferentes processos , dependendo apenas do valor interno cr3.

Dessa forma, todo programa pode esperar que seus dados comecem 0e terminem em FFFFFFFF, sem se preocupar com os endereços físicos exatos.

Falha de página

E se o Processo 1 tentar acessar um endereço dentro de uma página que não está presente?

O hardware notifica o software por meio de uma exceção de falha de página.

Em geral, cabe ao sistema operacional registrar um manipulador de exceções para decidir o que deve ser feito.

É possível que acessar uma página que não está na tabela seja um erro de programação:

int is[1];
is[2] = 1;

mas pode haver casos em que seja aceitável, por exemplo, no Linux quando:

  • o programa deseja aumentar sua pilha.

    Ele apenas tenta acessar um determinado byte em um determinado intervalo possível e, se o sistema operacional estiver satisfeito, ele adiciona essa página ao espaço de endereço do processo.

  • a página foi trocada para o disco.

    O sistema operacional precisará fazer algum trabalho por trás dos processos para colocar a página de volta na RAM.

    O SO pode descobrir que este é o caso com base no conteúdo do resto da entrada da tabela de página, uma vez que se o sinalizador presente estiver desmarcado, as outras entradas da entrada da tabela de página são deixadas completamente para o SO fazer o que ele deseja.

    No Linux, por exemplo, quando presente = 0:

    • se todos os campos da entrada da tabela da página forem 0, endereço inválido.

    • caso contrário, a página foi trocada para o disco e os valores reais desses campos codificam a posição da página no disco.

Em qualquer caso, o SO precisa saber qual endereço gerou a falha de página para poder lidar com o problema. É por isso que os simpáticos desenvolvedores do IA32 definem o valor de cr2para esse endereço sempre que ocorre uma falha de página. O manipulador de exceções pode então apenas olhar cr2para obter o endereço.

Simplificações

Simplificações da realidade que tornam este exemplo mais fácil de entender:

  • todos os circuitos de paging reais usam paging de vários níveis para economizar espaço, mas isso mostrou um esquema simples de nível único.

  • as tabelas de páginas continham apenas dois campos: um endereço de 20 bits e um sinalizador de presente de 1 bit.

    As tabelas de página real contêm um total de 12 campos e, portanto, outros recursos que foram omitidos.

Exemplo: esquema de paginação multinível

O problema com um esquema de paginação de nível único é que ocuparia muita RAM: 4G / 4K = 1 milhão de entradas por processo. Se cada entrada tiver 4 bytes de comprimento, isso daria 4 MB por processo , o que é demais até para um computador desktop: ps -A | wc -ldiz que estou executando 244 processos agora, então isso ocuparia cerca de 1 GB da minha RAM!

Por esse motivo, os desenvolvedores x86 decidiram usar um esquema de vários níveis que reduz o uso de RAM.

A desvantagem desse sistema é que ele tem um tempo de acesso um pouco maior.

No esquema simples de paginação de 3 níveis usado para processadores de 32 bits sem PAE, os 32 bits de endereço são divididos da seguinte forma:

| directory (10 bits) | table (10 bits) | offset (12 bits) |

Cada processo deve ter um e apenas um diretório de página associado a ele, portanto, conterá pelo menos 2^10 = 1Kentradas de diretório de página, muito melhor do que o mínimo de 1M necessário em um esquema de nível único.

As tabelas de página são alocadas apenas conforme necessário pelo sistema operacional. Cada tabela de 2^10 = 1Kpágina tem entradas de diretório de página

Os diretórios da página contêm ... entradas do diretório da página! As entradas do diretório de páginas são iguais às entradas da tabela de páginas, exceto que apontam para endereços RAM de tabelas de páginas em vez de endereços físicos de tabelas . Como esses endereços têm apenas 20 bits de largura, as tabelas de páginas devem estar no início das páginas de 4 KB.

cr3 agora aponta para a localização na RAM do diretório da página do processo atual em vez das tabelas de página.

As entradas das tabelas de página não mudam em nada a partir de um esquema de nível único.

As tabelas de páginas mudam de um esquema de nível único porque:

  • cada processo pode ter até 1K tabelas de página, uma por entrada de diretório de página.
  • cada tabela de página contém exatamente 1 mil entradas em vez de 1 milhão de entradas.

A razão para usar 10 bits nos primeiros dois níveis (e não, digamos 12 | 8 | 12) é que cada entrada da Tabela de Página tem 4 bytes de comprimento. Então, as 2 ^ 10 entradas de diretórios de páginas e tabelas de páginas se encaixarão perfeitamente em páginas de 4 KB. Isso significa que é mais rápido e simples alocar e desalocar páginas para esse propósito.

Tradução de endereços em esquema de vários níveis

Diretório de páginas fornecido ao processo 1 pelo sistema operacional:

RAM location     physical address   present
---------------  -----------------  --------
PD1 + 0     * L  0x10000            1
PD1 + 1     * L                     0
PD1 + 2     * L  0x80000            1
PD1 + 3     * L                     0
...                                 ...
PD1 + 0x3FF * L                     0

Tabelas de páginas fornecidas ao processo 1 pelo sistema operacional em PT1 = 0x10000000( 0x10000* 4K):

RAM location      physical address   present
---------------   -----------------  --------
PT1 + 0     * L   0x00001            1
PT1 + 1     * L                      0
PT1 + 2     * L   0x0000D            1
...                                  ...
PT1 + 0x3FF * L   0x00005            1

Tabelas de páginas fornecidas ao processo 1 pelo sistema operacional em PT2 = 0x80000000( 0x80000* 4K):

RAM location      physical address   present
---------------   -----------------  --------
PT2 + 0     * L   0x0000A            1
PT2 + 1     * L   0x0000C            1
PT2 + 2     * L                      0
...                                  ...
PT2 + 0x3FF * L   0x00003            1

Onde:

  • PD1: posição inicial do diretório da página do processo 1 na RAM.
  • PT1e PT2: posição inicial da tabela de páginas 1 e tabela de páginas 2 para o processo 1 na RAM.

Portanto, neste exemplo, o diretório da página e a tabela da página podem ser armazenados na RAM da seguinte forma:

----------------> 0xFFFFFFFF


----------------> PT2 + 0x3FF * L
Page Table 1
----------------> PT2

----------------> PD1 + 0x3FF * L
Page Directory 1
----------------> PD1


----------------> PT1 + 0x3FF * L
Page Table 2
----------------> PT1

----------------> 0x0

Vamos traduzir o endereço linear 0x00801004passo a passo.

Supomos que cr3 = PD1, ou seja, ele aponta para o diretório da página que acabamos de descrever.

Em binário, o endereço linear é:

0    0    8    0    1    0    0    4
0000 0000 1000 0000 0001 0000 0000 0100

Agrupando como 10 | 10 | 12dá:

0000000010 0000000001 000000000100
0x2        0x1        0x4

que dá:

  • entrada do diretório da página = 0x2
  • entrada da tabela da página = 0x1
  • deslocamento = 0x4

Portanto, o hardware procura a entrada 2 do diretório da página.

A tabela do diretório da página informa que a tabela da página está localizada em 0x80000 * 4K = 0x80000000. Este é o primeiro acesso à RAM do processo.

Como a entrada da tabela de página é 0x1, o hardware examina a entrada 1 da tabela de página em 0x80000000, que informa que a página física está localizada no endereço 0x0000C * 4K = 0x0000C000. Este é o segundo acesso RAM do processo.

Por fim, o hardware de paging adiciona o deslocamento e o endereço final é 0x0000C004.

Outros exemplos de endereços traduzidos são:

linear    10 10 12 split   physical
--------  ---------------  ----------
00000001  000 000 001      00001001
00001001  000 001 001      page fault
003FF001  000 3FF 001      00005001
00400000  001 000 000      page fault
00800001  002 000 001      0000A001
00801008  002 001 008      0000C008
00802008  002 002 008      page fault
00B00001  003 000 000      page fault

As falhas de página ocorrem se uma entrada de diretório de página ou uma entrada de tabela de página não estiver presente.

Se o sistema operacional quiser executar outro processo simultaneamente, ele fornecerá ao segundo processo um diretório de página separado e vinculará esse diretório a tabelas de página separadas.

Arquiteturas de 64 bits

64 bits ainda é muito endereço para os tamanhos de RAM atuais, portanto, a maioria das arquiteturas usará menos bits.

x86_64 usa 48 bits (256 TiB), e o PAE do modo legado já permite endereços de 52 bits (4 PiB).

12 desses 48 bits já estão reservados para o deslocamento, que deixa 36 bits.

Se for adotada uma abordagem de 2 níveis, a melhor divisão seria de dois níveis de 18 bits.

Mas isso significaria que o diretório da página teria 2^18 = 256Kentradas, o que consumiria muita RAM: quase uma paginação de nível único para arquiteturas de 32 bits!

Portanto, as arquiteturas de 64 bits criam ainda mais níveis de página, normalmente 3 ou 4.

O x86_64 usa 4 níveis em um 9 | 9 | 9 | 12esquema, de modo que o nível superior ocupa apenas 2^9as entradas de nível superior.

PAE

Extensão do endereço físico.

Com 32 bits, apenas 4 GB de RAM podem ser endereçados.

Isso começou a se tornar uma limitação para servidores grandes, então a Intel introduziu o mecanismo PAE no Pentium Pro.

Para aliviar o problema, a Intel adicionou 4 novas linhas de endereço, para que 64 GB pudessem ser endereçados.

A estrutura da tabela da página também é alterada se o PAE estiver ativado. A maneira exata como ela é alterada depende se o PSE está ativado ou desativado.

PAE é ativado e desativado através do PAEbit de cr4.

Mesmo que a memória total endereçável seja de 64 GB, os processos individuais ainda são capazes de usar até 4 GB. O sistema operacional pode, no entanto, colocar processos diferentes em blocos de 4 GB diferentes.

PSE

Extensão do tamanho da página.

Permite que as páginas tenham 4M (ou 2M se o PAE estiver ativado) em vez de 4K.

PSE é ativado e desativado através do PAEbit de cr4.

Esquemas de tabela de página PAE e PSE

Se PAE e PSE estiverem ativos, diferentes esquemas de nível de paginação serão usados:

  • sem PAE e sem PSE: 10 | 10 | 12

  • não PAE e PSE: 10 | 22.

    22 é o deslocamento dentro da página 4Mb, uma vez que o endereço de 22 bits é 4Mb.

  • PAE e sem PSE: 2 | 9 | 9 | 12

    O motivo do projeto pelo qual 9 é usado duas vezes em vez de 10 é que agora as entradas não cabem mais em 32 bits, que foram todos preenchidos por 20 bits de endereço e 12 bits de sinalização significativos ou reservados.

    O motivo é que 20 bits não são mais suficientes para representar o endereço das tabelas de página: 24 bits agora são necessários por causa dos 4 fios extras adicionados ao processador.

    Portanto, os designers decidiram aumentar o tamanho das entradas para 64 bits e, para fazê-las caber em uma única tabela de página, é necessário reduzir o número de entradas para 2 ^ 9 em vez de 2 ^ 10.

    O 2 inicial é um novo nível de página denominado Page Directory Pointer Table (PDPT), uma vez que aponta para os diretórios de página e preenche o endereço linear de 32 bits. Os PDPTs também têm 64 bits de largura.

    cr3agora aponta para PDPTs que devem estar no punho 4 GB de memória e alinhados em múltiplos de 32 bits para eficiência de endereçamento. Isso significa que agora cr3tem 27 bits significativos em vez de 20: 2 ^ 5 para os 32 múltiplos * 2 ^ 27 para completar os 2 ^ 32 dos primeiros 4 GB.

  • PAE e PSE: 2 | 9 | 21

    Os designers decidiram manter um campo de 9 bits de largura para caber em uma única página.

    Isso deixa 23 bits. Deixando 2 para o PDPT manter as coisas uniformes com o caso PAE sem PSE, deixa 21 para deslocamento, o que significa que as páginas têm 2M de largura em vez de 4M.

TLB

O Translation Lookahead Buffer (TLB) é um cache para endereços de paginação.

Por ser um cache, ele compartilha muitos dos problemas de design do cache da CPU, como o nível de associatividade.

Esta seção deve descrever um TLB totalmente associativo simplificado com 4 entradas de endereço único. Observe que, como outros caches, os TLBs reais geralmente não são totalmente associativos.

Operação basica

Depois que ocorre uma tradução entre o endereço linear e o endereço físico, ele é armazenado no TLB. Por exemplo, um TLB de 4 entradas começa no seguinte estado:

  valid   linear   physical
  ------  -------  ---------
> 0       00000    00000
  0       00000    00000
  0       00000    00000
  0       00000    00000

O >indica a entrada atual a ser substituída.

e depois que um endereço linear de página 00003é traduzido para um endereço físico 00005, o TLB se torna:

  valid   linear   physical
  ------  -------  ---------
  1       00003    00005
> 0       00000    00000
  0       00000    00000
  0       00000    00000

e após uma segunda tradução de 00007para 00009ele se torna:

  valid   linear   physical
  ------  -------  ---------
  1       00003    00005
  1       00007    00009
> 0       00000    00000
  0       00000    00000

Agora, se 00003precisar ser traduzido novamente, o hardware primeiro procura o TLB e descobre seu endereço com um único acesso à RAM 00003 --> 00005.

Claro, 00000não está no TLB, pois nenhuma entrada válida contém 00000uma chave.

Política de substituição

Quando o TLB é preenchido, os endereços mais antigos são substituídos. Assim como para o cache da CPU, a política de substituição é uma operação potencialmente complexa, mas uma heurística simples e razoável é remover a entrada menos usada recentemente (LRU).

Com LRU, a partir do estado:

  valid   linear   physical
  ------  -------  ---------
> 1       00003    00005
  1       00007    00009
  1       00009    00001
  1       0000B    00003

adicionar 0000D -> 0000Adaria:

  valid   linear   physical
  ------  -------  ---------
  1       0000D    0000A
> 1       00007    00009
  1       00009    00001
  1       0000B    00003

CAM

Usar o TLB torna a tradução mais rápida, porque a tradução inicial leva um acesso por nível de TLB , o que significa 2 em um esquema simples de 32 bits, mas 3 ou 4 em arquiteturas de 64 bits.

O TLB é geralmente implementado como um tipo caro de RAM chamada memória endereçável por conteúdo (CAM). O CAM implementa um mapa associativo no hardware, ou seja, uma estrutura que dada uma chave (endereço linear), recupera um valor.

Os mapeamentos também podem ser implementados em endereços de RAM, mas os mapeamentos de CAM podem exigir muito menos entradas do que um mapeamento de RAM.

Por exemplo, um mapa no qual:

  • ambas as chaves e valores têm 20 bits (no caso de esquemas de paginação simples)
  • no máximo 4 valores precisam ser armazenados de cada vez

pode ser armazenado em um TLB com 4 entradas:

linear   physical
-------  ---------
00000    00001
00001    00010
00010    00011
FFFFF    00000

No entanto, para implementar isso com RAM, seria necessário ter 2 ^ 20 endereços :

linear   physical
-------  ---------
00000    00001
00001    00010
00010    00011
... (from 00011 to FFFFE)
FFFFF    00000

o que seria ainda mais caro do que usar um TLB.

Invalidando entradas

Quando cr3muda, todas as entradas de TLB são invalidadas, porque uma nova tabela de página para um novo processo será usada, então é improvável que qualquer uma das entradas antigas tenha algum significado.

O x86 também oferece a invlpginstrução que invalida explicitamente uma única entrada TLB. Outras arquiteturas oferecem ainda mais instruções para entradas TLB invalidadas, como invalidar todas as entradas em um determinado intervalo.

Algumas CPUs x86 vão além dos requisitos da especificação x86 e fornecem mais coerência do que ela garante, entre modificar uma entrada da tabela de páginas e usá-la, quando ainda não estava armazenada em cache no TLB . Aparentemente, o Windows 9x confiava nisso para correção, mas as CPUs AMD modernas não oferecem passeios de página coerentes. CPUs da Intel sim, embora tenham que detectar especulações incorretas para isso. Tirar vantagem disso é provavelmente uma má ideia, já que provavelmente não há muito a ganhar, e há um grande risco de causar problemas sutis e sensíveis ao tempo que serão difíceis de depurar.

Uso do kernel Linux

O kernel do Linux faz uso extensivo dos recursos de paginação do x86 para permitir mudanças rápidas de processo com pequena fragmentação de dados.

Em v4.2, olhe em arch/x86/:

  • include/asm/pgtable*
  • include/asm/page*
  • mm/pgtable*
  • mm/page*

Parece não haver estruturas definidas para representar as páginas, apenas macros: include/asm/page_types.hé especialmente interessante. Excerto:

#define _PAGE_BIT_PRESENT   0   /* is present */
#define _PAGE_BIT_RW        1   /* writeable */
#define _PAGE_BIT_USER      2   /* userspace addressable */
#define _PAGE_BIT_PWT       3   /* page write through */

arch/x86/include/uapi/asm/processor-flags.hdefine CR0, e em particular a PGposição do bit:

#define X86_CR0_PG_BIT      31 /* Paging */

Bibliografia

Livre:

  • rutgers-pxk-416 capítulo "Gerenciamento de memória: notas de aula"

    Boa revisão histórica das técnicas de organização de memória usadas por sistemas operacionais mais antigos.

Não livre:

  • bovet05 capítulo "Endereçamento de memória"

    Introdução razoável ao endereçamento de memória x86. Faltando alguns exemplos bons e simples.

Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
fonte
Ótima resposta, mas ainda não estou certo de como o LRU é decidido. Invocar o SO sempre que uma página diferente de MRU é acessada parece caro. Como alternativa, pude ver o hardware reordenando a tabela de páginas para LRU, o que pode ser perigoso para programas simultâneos. Algum destes está correto? Como o SO sabe qual página é o LRU quando ocorre uma falha de página?
Keynan
@Keynan Acho que é o hardware que faz isso, então o tempo gasto não é uma preocupação. Quanto à simultaneidade, não sei como ela é gerenciada. Eu acho que há um CR3 e cache por processador, e o sistema operacional só deve se certificar de que as páginas de memória não se sobreponham.
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
1
real TLBs are not usually fully associativeThe TLB is usually implemented as … CAMEssas duas afirmações não são contraditórias?
A3f
>>> x86_64 usa 4 níveis em um 9 | 9 | 9 Esquema de 12 deve ser 9 | 9 | 9 | 9 12?
monklof
@monklof Acho que está correto: 9 9 9 12 já permite 512gb de RAM. O esquema de 5 níveis é um desenvolvimento mais recente voltado apenas para servidores, isso é mencionado na resposta no meu site que está mais atualizado.
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
20

Aqui está uma resposta muito curta e de alto nível:

Um processador x86 opera em um dos vários modos possíveis (aproximadamente: real, protegido, 64 bits). Cada modo pode usar um dos vários modelos de endereçamento de memória possíveis (mas nem todos os modos podem usar todos os modelos), a saber: endereçamento em modo real, endereçamento segmentado e endereçamento linear simples.

No mundo moderno, apenas o endereçamento linear plano no modo protegido ou de 64 bits é relevante, e os dois modos são essencialmente os mesmos, com a principal diferença sendo o tamanho da palavra de máquina e, portanto, a quantidade endereçável de memória.

Agora, o modo de endereçamento de memória dá significado aos operandos de memória das instruções da máquina (como mov DWORD PTR [eax], 25, que armazena um dwordinteiro de 32 bits (aka ) de valor 25 na memória, cujo endereço é armazenado no eaxregistrador de 32 bits). No endereçamento linear plano, esse número em eaxpode ser executado em um único intervalo contíguo, de zero até o valor máximo (em nosso caso, é 2 32  - 1).

No entanto, o endereçamento linear simples pode ser paginado ou não paginado . Sem paginação, o endereço se refere diretamente à memória física. Com a paginação, a unidade de gerenciamento de memória do processador (ou MMU) alimenta de forma transparente o endereço desejado (agora chamado de endereço virtual ) em um mecanismo de pesquisa, as chamadas tabelas de página , e obtém um novo valor, que é interpretado como um endereço físico. A operação original agora opera nesse novo endereço traduzido na memória física, embora o usuário apenas veja o endereço virtual.

O principal benefício da paginação é que as tabelas de páginas são gerenciadas pelo sistema operacional. Assim, o sistema operacional pode modificar e substituir as tabelas de página arbitrariamente, como ao "alternar tarefas". Ele pode manter uma coleção inteira de tabelas de páginas, uma para cada "processo", e sempre que decide que um determinado processo será executado em uma determinada CPU, ele carrega as tabelas de páginas do processo na MMU dessa CPU (cada CPU tem sua própria conjunto de tabelas de páginas). O resultado é que cada processo vê seu próprio espaço de endereço virtual , que parece o mesmo, independentemente de quais páginas físicas estavam livres quando o sistema operacional teve que alocar memória para ele. Ele nunca sabe sobre a memória de qualquer outro processo, uma vez que não pode acessar a memória física diretamente.

As tabelas de página são estruturas de dados semelhantes a árvores aninhadas, armazenadas na memória normal, escritas pelo sistema operacional, mas lidas diretamente pelo hardware, portanto, o formato é fixo. Eles são "carregados" na MMU definindo um registro de controle de CPU especial para apontar para a tabela de nível superior. A CPU usa um cache chamado TLB para lembrar as pesquisas, portanto, os acessos repetidos às mesmas poucas páginas são muito mais rápidos do que os acessos dispersos, por motivos de falta de TLB e também pelos motivos usuais de cache de dados. É comum ver o termo "entrada TLB" usado para referir-se às entradas da tabela de páginas, mesmo quando não estão armazenadas em cache no TLB.

E caso você se preocupe que um processo possa apenas desativar a paginação ou tentar modificar as tabelas de página: Isso não é permitido, uma vez que o x86 implementa níveis de privilégio (chamados de "anéis") e o código do usuário é executado em um nível de privilégio muito baixo para permitir para modificar as tabelas de páginas da CPU.

Kerrek SB
fonte