Comment fonctionne la pagination x86?

Question 1

Cette question vise à combler le vide d'une bonne information gratuite sur le sujet.

Je crois qu'une bonne réponse s'intégrera dans une grande réponse SO ou du moins dans quelques réponses.

L'objectif principal est de donner aux débutants juste assez d'informations pour qu'ils puissent prendre le manuel par eux-mêmes et être en mesure de comprendre les concepts de base du système d'exploitation liés à la pagination.

Lignes directrices suggérées:

Les réponses doivent être adaptées aux débutants:
- des exemples concrets, mais éventuellement simplifiés, sont très importants
- les applications des concepts présentés sont les bienvenues
citer des ressources utiles, c'est bien
de petites digressions sur la façon dont les systèmes d'exploitation utilisent les fonctionnalités de pagination sont les bienvenues
Les explications PAE et PSE sont les bienvenues
de petites digressions dans x86_64 sont les bienvenues

Questions connexes et pourquoi je pense qu'elles ne sont pas dupes:

Comment fonctionnent les tableaux de pages x86? : le titre est presque le même que cette question, mais le corps pose des questions spécifiques liées à cr3 et TLB. Cette question est un sous-ensemble de celle-ci.
Comment fonctionne la virtualisation x86 : le corps ne demande que les sources.

Question 2

Version de cette réponse avec une belle table des matières et plus de contenu .

Je corrigerai toute erreur signalée. Si vous souhaitez apporter des modifications importantes ou ajouter un aspect manquant, faites-les sur vos propres réponses pour obtenir une réputation bien méritée. Les modifications mineures peuvent être fusionnées directement dans.

Exemple de code

Exemple minimal: https://github.com/cirosantilli/x86-bare-metal-examples/blob/5c672f73884a487414b3e21bd9e579c67cd77621/paging.S

Comme tout le reste de la programmation, la seule façon de vraiment comprendre cela est de jouer avec des exemples minimaux.

Ce qui en fait un sujet "difficile", c'est que l'exemple minimal est grand car vous devez créer votre propre petit système d'exploitation.

Manuel Intel

Bien qu'il soit impossible de comprendre sans exemples en tête, essayez de vous familiariser avec les manuels dès que possible.

Intel décrit la pagination dans le Manuel de programmation du système Intel Volume 3 - 325384-056FR Septembre 2015 Chapitre 4 «Paging».

La Figure 4-4 "Formats des entrées CR3 et de structure de pagination avec pagination 32 bits" est particulièrement intéressante, qui donne les principales structures de données.

MMU

La pagination est effectuée par la partie MMU ( Memory Management Unit ) de la CPU. Comme beaucoup d'autres (par exemple le coprocesseur x87 , APIC ), cela se faisait auparavant par une puce séparée, qui a ensuite été intégrée au processeur. Mais le terme est toujours utilisé.

Faits généraux

Les adresses logiques sont les adresses de mémoire utilisées dans le code utilisateur-pays "normal" (par exemple le contenu de rsiin mov eax, [rsi]).

La première segmentation les traduit en adresses linéaires, puis la pagination traduit les adresses linéaires en adresses physiques.

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

La plupart du temps, nous pouvons considérer les adresses physiques comme indexant les cellules de mémoire matérielles RAM réelles, mais ce n'est pas vrai à 100% à cause de:

La pagination n'est disponible qu'en mode protégé. L'utilisation de la pagination en mode protégé est facultative. La pagination est activée ssi le PGbit du cr0registre est activé.

Pagination vs segmentation

Une différence majeure entre la pagination et la segmentation est que:

la pagination divise la RAM en morceaux de taille égale appelés pages
la segmentation divise la mémoire en morceaux de tailles arbitraires

C'est le principal avantage de la pagination, car des blocs de taille égale rendent les choses plus faciles à gérer.

La pagination est devenue tellement plus populaire que la prise en charge de la segmentation a été abandonnée dans x86-64 en mode 64 bits, le mode de fonctionnement principal des nouveaux logiciels, où elle n'existe qu'en mode de compatibilité, qui émule IA32.

Application

La pagination est utilisée pour implémenter les espaces d'adressage virtuels des processus sur les systèmes d'exploitation modernes. Avec les adresses virtuelles, le système d'exploitation peut adapter deux ou plusieurs processus simultanés sur une seule RAM de manière à:

les deux programmes n'ont besoin de rien savoir de l'autre
la mémoire des deux programmes peut augmenter et diminuer selon les besoins
le passage d'un programme à l'autre est très rapide
un programme ne peut jamais accéder à la mémoire d'un autre processus

La pagination est historiquement venue après la segmentation et l'a largement remplacée pour l'implémentation de la mémoire virtuelle dans les systèmes d'exploitation modernes tels que Linux car il est plus facile de gérer les blocs de mémoire de taille fixe des pages au lieu de segments de longueur variable.

Implémentation matérielle

Comme la segmentation en mode protégé (où la modification d'un registre de segment déclenche un chargement depuis le GDT ou LDT), le matériel de pagination utilise des structures de données en mémoire pour faire son travail (tables de pages, répertoires de pages, etc.).

Le format de ces structures de données est fixé par le matériel , mais il appartient au système d'exploitation de configurer et de gérer correctement ces structures de données sur la RAM, et d'indiquer au matériel où les trouver (via cr3).

Certaines autres architectures laissent la pagination presque entièrement entre les mains du logiciel, de sorte qu'un TLB miss exécute une fonction fournie par le système d'exploitation pour parcourir les tableaux de pages et insérer le nouveau mappage dans le TLB. Cela laisse le choix des formats de table de pages par le système d'exploitation, mais il est peu probable que le matériel puisse chevaucher les parcours de page avec l'exécution dans le désordre d'autres instructions, comme le peut x86 .

Exemple: schéma de pagination simplifié à un seul niveau

Voici un exemple de la façon dont la pagination fonctionne sur une version simplifiée de l'architecture x86 pour implémenter un espace mémoire virtuel.

Tableaux de pages

Le système d'exploitation pourrait leur donner les tableaux de pages suivants:

Tableau des pages donné au processus 1 par l'OS:

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

Tableau des pages donné au processus 2 par l'OS:

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

Où:

PT1et PT2: position initiale des tables 1 et 2 sur la RAM.

Des exemples de valeurs: 0x00000000, 0x12345678, etc.

C'est le système d'exploitation qui décide de ces valeurs.
L: longueur d'une entrée de table de pages.
present: indique que la page est présente en mémoire.

Les tableaux de pages sont situés sur la RAM. Ils pourraient par exemple être situés comme:

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


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


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

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

Les emplacements initiaux sur la RAM pour les deux tables de pages sont arbitraires et contrôlés par le système d'exploitation. C'est à l'OS de s'assurer qu'ils ne se chevauchent pas!

Chaque processus ne peut pas toucher directement les tables de pages, bien qu'il puisse faire des requêtes au système d'exploitation qui entraînent la modification des tables de pages, par exemple en demandant des segments de pile ou de tas plus grands.

Une page est un morceau de 4 Ko (12 bits), et comme les adresses ont 32 bits, seuls 20 bits (20 + 12 = 32, donc 5 caractères en notation hexadécimale) sont nécessaires pour identifier chaque page. Cette valeur est fixée par le matériel.

Entrées de table de page

Une table de pages est ... une table d'entrées de table de pages!

Le format exact des entrées de table est fixé par le matériel .

Dans cet exemple simplifié, les entrées de la table des pages ne contiennent que deux champs:

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

donc dans cet exemple, les concepteurs de matériel auraient pu choisir L = 21.

La plupart des entrées de table de pages réelles ont d'autres champs.

Il ne serait pas pratique d'aligner les choses à 21 bits car la mémoire est adressable par octets et non par bits. Par conséquent, même si seulement 21 bits sont nécessaires dans ce cas, les concepteurs de matériel choisiraient probablement L = 32de rendre l'accès plus rapide et de réserver simplement les bits restants pour une utilisation ultérieure. La valeur réelle pour Lsur x86 est de 32 bits.

Traduction d'adresse dans un schéma à un niveau

Une fois les tables de pages configurées par le système d'exploitation, la traduction d'adresses entre les adresses linéaires et physiques est effectuée par le matériel .

Lorsque le système d'exploitation souhaite activer le processus 1, il définit cr3sur PT1, le début de la table pour le processus un.

Si le processus 1 souhaite accéder à une adresse linéaire 0x00000001, le circuit matériel de radiomessagerie effectue automatiquement les opérations suivantes pour le système d'exploitation:

divisez l'adresse linéaire en deux parties:
```
| page (20 bits) | offset (12 bits) |
```
Donc, dans ce cas, nous aurions:
- page = 0x00000
- offset = 0x001
regardez dans le tableau de la page 1 parce qu'il cr3pointe vers lui.
regardez l'entrée 0x00000parce que c'est la partie de la page.

Le matériel sait que cette entrée se trouve à l'adresse RAM PT1 + 0 * L = PT1.
puisqu'il est présent, l'accès est valide
par la table de page, l'emplacement du numéro de page 0x00000est à 0x00001 * 4K = 0x00001000.
pour trouver l'adresse physique finale, il suffit d'ajouter le décalage:
```
  00001 000
+ 00000 001
  -----------
  00001 001
```
car 00001c'est l'adresse physique de la page recherchée sur la table et 001c'est le décalage.

Comme son nom l'indique, le décalage est toujours simplement ajouté à l'adresse physique de la page.
le matériel obtient alors la mémoire à cet emplacement physique.

De la même manière, les traductions suivantes se produiraient pour le processus 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

Par exemple, lors de l'accès à l'adresse 00001000, la partie de page est 00001le matériel sait que son entrée de table de page est située à l'adresse RAM: PT1 + 1 * L(à 1cause de la partie de page), et c'est là qu'il la recherchera.

Lorsque le système d'exploitation veut passer au processus 2, il lui suffit de cr3pointer vers la page 2. C'est aussi simple que cela!

Maintenant, les traductions suivantes se produiraient pour le processus 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

La même adresse linéaire se traduit par différentes adresses physiques pour différents processus , en fonction uniquement de la valeur à l'intérieur cr3.

De cette façon, chaque programme peut s'attendre à ce que ses données commencent 0et se terminent à FFFFFFFF, sans se soucier des adresses physiques exactes.

Erreur de page

Que faire si le processus 1 essaie d'accéder à une adresse à l'intérieur d'une page qui n'est pas présente?

Le matériel notifie le logiciel via une exception de défaillance de page.

Il appartient alors généralement au système d'exploitation d'enregistrer un gestionnaire d'exceptions pour décider de ce qui doit être fait.

Il est possible que l'accès à une page qui ne figure pas sur la table soit une erreur de programmation:

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

mais il peut y avoir des cas où cela est acceptable, par exemple sous Linux lorsque:

le programme veut augmenter sa pile.

Il essaie simplement d'accéder à un certain octet dans une plage possible donnée, et si le système d'exploitation est satisfait, il ajoute cette page à l'espace d'adressage du processus.
la page a été échangée sur le disque.

Le système d'exploitation devra effectuer un certain travail derrière les processus pour remettre la page dans la RAM.

Le système d'exploitation peut découvrir que c'est le cas en fonction du contenu du reste de l'entrée de la table de pages, car si l'indicateur actuel est clair, les autres entrées de l'entrée de la table de pages sont complètement laissées au système d'exploitation à ce qu'il veut.

Sur Linux par exemple, lorsqu'il est présent = 0:
- si tous les champs de l'entrée de table de page sont 0, adresse invalide.
- sinon, la page a été permutée sur le disque et les valeurs réelles de ces champs codent la position de la page sur le disque.

Dans tous les cas, le système d'exploitation a besoin de savoir quelle adresse a généré l'erreur de page pour pouvoir traiter le problème. C'est pourquoi les gentils développeurs IA32 définissent la valeur de cr2sur cette adresse chaque fois qu'une erreur de page se produit. Le gestionnaire d'exceptions peut alors simplement regarder cr2pour obtenir l'adresse.

Simplifications

Des simplifications à la réalité qui facilitent la compréhension de cet exemple:

tous les circuits de pagination réels utilisent la pagination à plusieurs niveaux pour économiser de l'espace, mais cela a montré un schéma simple à un niveau.
les tables de pages ne contenaient que deux champs: une adresse de 20 bits et un indicateur de présence de 1 bit.

Les tableaux de pages réelles contiennent un total de 12 champs, et donc d'autres fonctionnalités qui ont été omises.

Exemple: schéma de pagination à plusieurs niveaux

Le problème avec un schéma de pagination à un seul niveau est qu'il prendrait trop de RAM: 4G / 4K = 1M d'entrées par processus. Si chaque entrée est longue de 4 octets, cela ferait 4 Mo par processus , ce qui est trop même pour un ordinateur de bureau: ps -A | wc -ldit que j'exécute 244 processus en ce moment, donc cela prendrait environ 1 Go de RAM!

Pour cette raison, les développeurs x86 ont décidé d'utiliser un schéma à plusieurs niveaux qui réduit l'utilisation de la RAM.

L'inconvénient de ce système est qu'il a un temps d'accès légèrement plus élevé.

Dans le schéma de pagination simple à 3 niveaux utilisé pour les processeurs 32 bits sans PAE, les 32 bits d'adresse sont divisés comme suit:

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

Chaque processus doit avoir un et un seul répertoire de pages associé, de sorte qu'il contiendra au moins des 2^10 = 1Kentrées de répertoire de pages, bien mieux que le minimum de 1M requis sur un schéma à un seul niveau.

Les tableaux de pages ne sont alloués que selon les besoins du système d'exploitation. Chaque table de 2^10 = 1Kpages a des entrées de répertoire de pages

Les répertoires de pages contiennent ... des entrées de répertoire de pages! Les entrées de l'annuaire de pages sont les mêmes que les entrées de tables de pages, sauf qu'elles pointent vers les adresses RAM des tables de pages au lieu des adresses physiques des tables . Étant donné que ces adresses ne font que 20 bits de large, les tableaux de pages doivent se trouver au début des pages de 4 Ko.

cr3 pointe maintenant vers l'emplacement sur la RAM du répertoire de pages du processus en cours au lieu des tables de pages.

Les entrées des tables de pages ne changent pas du tout à partir d'un schéma à un seul niveau.

Les tableaux de pages changent d'un schéma à un seul niveau car:

chaque processus peut avoir jusqu'à 1K tables de pages, une par entrée d'annuaire de page.
chaque table de page contient exactement 1K entrées au lieu de 1M d'entrées.

La raison de l'utilisation de 10 bits sur les deux premiers niveaux (et non, par exemple 12 | 8 | 12) est que chaque entrée de la table de pages a une longueur de 4 octets. Ensuite, les 2 ^ 10 entrées des répertoires de pages et des tables de pages s'intégreront parfaitement dans les pages de 4 Ko. Cela signifie qu'il est plus rapide et plus simple d'allouer et de désallouer des pages à cette fin.

Traduction d'adresse dans un schéma à plusieurs niveaux

Répertoire de pages donné au processus 1 par le système d'exploitation:

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

Tables de pages données au processus 1 par le système d'exploitation à 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

Tables de pages données au processus 1 par le système d'exploitation à 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

où:

PD1: position initiale du répertoire de pages du processus 1 sur la RAM.
PT1et PT2: position initiale du tableau de pages 1 et du tableau de pages 2 pour le processus 1 sur la RAM.

Donc, dans cet exemple, le répertoire des pages et la table des pages pourraient être stockés dans la RAM quelque chose comme:

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


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

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


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

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

Traduisons 0x00801004pas à pas l' adresse linéaire .

Nous supposons que cr3 = PD1, c'est-à-dire qu'il pointe vers le répertoire de pages que nous venons de décrire.

En binaire, l'adresse linéaire est:

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

Regrouper comme 10 | 10 | 12donne:

0000000010 0000000001 000000000100
0x2        0x1        0x4

qui donne:

entrée de répertoire de page = 0x2
entrée de table de page = 0x1
offset = 0x4

Le matériel recherche donc l'entrée 2 du répertoire de pages.

La table du répertoire de page indique que la table de page se trouve à 0x80000 * 4K = 0x80000000. Il s'agit du premier accès RAM du processus.

Puisque l'entrée de la table de pages est 0x1, le matériel regarde l'entrée 1 de la table de pages à 0x80000000, qui lui indique que la page physique se trouve à l'adresse 0x0000C * 4K = 0x0000C000. Il s'agit du deuxième accès RAM du processus.

Enfin, le matériel de pagination ajoute le décalage et l'adresse finale est 0x0000C004.

D'autres exemples d'adresses traduites sont:

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

Les erreurs de page se produisent si une entrée d'annuaire de pages ou une entrée de table de pages n'est pas présente.

Si le système d'exploitation souhaite exécuter un autre processus simultanément, il attribuera au second processus un répertoire de pages distinct et liera ce répertoire à des tables de pages distinctes.

Architectures 64 bits

64 bits est toujours trop d'adresse pour les tailles de RAM actuelles, donc la plupart des architectures utiliseront moins de bits.

x86_64 utilise 48 bits (256 Tio) et le PAE du mode hérité autorise déjà les adresses de 52 bits (4 PiB).

12 de ces 48 bits sont déjà réservés pour le décalage, ce qui laisse 36 bits.

Si une approche à 2 niveaux est adoptée, la meilleure répartition serait de deux niveaux de 18 bits.

Mais cela signifierait que le répertoire de pages aurait des 2^18 = 256Kentrées, ce qui prendrait trop de RAM: proche d'une pagination à un seul niveau pour les architectures 32 bits!

Par conséquent, les architectures 64 bits créent encore plus de niveaux de page, généralement 3 ou 4.

x86_64 utilise 4 niveaux dans un 9 | 9 | 9 | 12schéma, de sorte que le niveau supérieur n'occupe que les 2^9entrées de niveau supérieur.

PAE

Extension d'adresse physique.

Avec 32 bits, seuls 4 Go de RAM peuvent être adressés.

Cela a commencé à devenir une limitation pour les grands serveurs, c'est pourquoi Intel a introduit le mécanisme PAE dans Pentium Pro.

Pour résoudre le problème, Intel a ajouté 4 nouvelles lignes d'adresse, de sorte que 64 Go puissent être adressés.

La structure de la table des pages est également modifiée si PAE est activé. La manière exacte dont elle est modifiée dépend de l'activation ou de la désactivation de PSE.

PAE est activé et désactivé via le PAEbit de cr4.

Même si la mémoire adressable totale est de 64 Go, les processus individuels ne peuvent toujours utiliser que jusqu'à 4 Go. Le système d'exploitation peut cependant placer différents processus sur différents blocs de 4 Go.

PSE

Extension de taille de page.

Permet aux pages d'avoir une longueur de 4M (ou 2M si PAE est activé) au lieu de 4K.

PSE est activé et désactivé via le PAEbit de cr4.

Schémas de table de page PAE et PSE

Si PAE et PSE sont actifs, différents schémas de niveau de pagination sont utilisés:

pas de PAE et pas de PSE: 10 | 10 | 12
pas Pae PSE: 10 | 22.

22 est le décalage dans la page de 4 Mo, puisque 22 bits adressent 4 Mo.
PAE et pas de PSE: 2 | 9 | 9 | 12

La raison de conception pour laquelle 9 est utilisé deux fois au lieu de 10 est que maintenant les entrées ne peuvent plus tenir dans 32 bits, qui étaient tous remplis par 20 bits d'adresse et 12 bits d'indicateur significatifs ou réservés.

La raison en est que 20 bits ne suffisent plus pour représenter l'adresse des tables de pages: 24 bits sont désormais nécessaires à cause des 4 fils supplémentaires ajoutés au processeur.

Par conséquent, les concepteurs ont décidé d'augmenter la taille des entrées à 64 bits, et pour les faire tenir dans une table à une seule page, il est nécessaire de réduire le nombre d'entrées à 2 ^ 9 au lieu de 2 ^ 10.

Le 2 de départ est un nouveau niveau de page appelé Table de pointeur de répertoire de page (PDPT), car il pointe vers les répertoires de page et remplit l'adresse linéaire 32 bits. Les PDPT ont également une largeur de 64 bits.

cr3pointe maintenant vers les PDPT qui doivent être sur les quatre premiers 4 Go de mémoire et alignés sur des multiples de 32 bits pour une efficacité d'adressage. Cela signifie qu'il a maintenant cr327 bits significatifs au lieu de 20: 2 ^ 5 pour les 32 multiples * 2 ^ 27 pour compléter les 2 ^ 32 des 4 premiers Go.
PAE et PSE: 2 | 9 | 21

Les concepteurs ont décidé de garder un champ large de 9 bits pour qu'il tienne dans une seule page.

Cela laisse 23 bits. Laisser 2 pour que le PDPT garde les choses uniformes avec le cas PAE sans PSE laisse 21 pour le décalage, ce qui signifie que les pages ont une largeur de 2M au lieu de 4M.

TLB

Le TLB (Translation Lookahead Buffer) est un cache pour les adresses de pagination.

Puisqu'il s'agit d'un cache, il partage de nombreux problèmes de conception du cache du processeur, tels que le niveau d'associativité.

Cette section doit décrire un TLB entièrement associatif simplifié avec 4 entrées d'adresse unique. Notez que comme les autres caches, les vrais TLB ne sont généralement pas entièrement associatifs.

Opération de base

Après une traduction entre l'adresse linéaire et l'adresse physique, elle est stockée sur le TLB. Par exemple, un TLB à 4 entrées démarre dans l'état suivant:

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

Le >indique l'entrée actuelle à remplacer.

et après qu'une adresse linéaire de page 00003est traduite en une adresse physique 00005, le TLB devient:

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

et après une seconde traduction de 00007to 00009il devient:

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

Maintenant, s'il 00003faut à nouveau traduire, le matériel recherche d'abord le TLB et trouve son adresse avec un seul accès RAM 00003 --> 00005.

Bien sûr, 00000n'est pas sur le TLB puisqu'aucune entrée valide ne contient 00000comme clé.

Politique de remplacement

Lorsque TLB est rempli, les anciennes adresses sont écrasées. Tout comme pour le cache CPU, la politique de remplacement est une opération potentiellement complexe, mais une heuristique simple et raisonnable consiste à supprimer l'entrée la moins récemment utilisée (LRU).

Avec LRU, à partir de l'état:

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

l'ajout 0000D -> 0000Adonnerait:

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

CAME

L'utilisation du TLB accélère la traduction, car la traduction initiale nécessite un accès par niveau TLB , ce qui signifie 2 sur un schéma simple de 32 bits, mais 3 ou 4 sur des architectures 64 bits.

Le TLB est généralement mis en œuvre comme un type de RAM coûteux appelé mémoire adressable par le contenu (CAM). CAM implémente une carte associative sur le matériel, c'est-à-dire une structure qui, donnée une clé (adresse linéaire), récupère une valeur.

Les mappages peuvent également être implémentés sur les adresses RAM, mais les mappages CAM peuvent nécessiter beaucoup moins d'entrées qu'un mappage RAM.

Par exemple, une carte dans laquelle:

les clés et les valeurs ont 20 bits (le cas d'un schéma de pagination simple)
au plus 4 valeurs doivent être stockées à chaque fois

pourrait être stocké dans un TLB avec 4 entrées:

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

Cependant, pour implémenter cela avec de la RAM, il serait nécessaire d'avoir 2 ^ 20 adresses :

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

ce qui serait encore plus cher que d'utiliser un TLB.

Entrées invalides

En cas de cr3modification, toutes les entrées TLB sont invalidées, car une nouvelle table de pages pour un nouveau processus va être utilisée, il est donc peu probable que l'une des anciennes entrées ait une signification.

Le x86 propose également l' invlpginstruction qui invalide explicitement une seule entrée TLB. D'autres architectures offrent encore plus d'instructions aux entrées TLB invalides, telles que l'invalidation de toutes les entrées sur une plage donnée.

Certains processeurs x86 vont au-delà des exigences de la spécification x86 et offrent plus de cohérence qu'elle n'en garantit, entre la modification d'une entrée de table de page et son utilisation, alors qu'elle n'était pas déjà mise en cache dans le TLB . Apparemment, Windows 9x s'est appuyé sur cela pour l'exactitude, mais les processeurs AMD modernes ne permettent pas de parcourir les pages cohérentes. Les processeurs Intel le font, même s'ils doivent détecter des spéculations erronées pour le faire. En tirer parti est probablement une mauvaise idée, car il n'y a probablement pas grand chose à gagner, et un grand risque de causer de subtils problèmes sensibles au timing qui seront difficiles à déboguer.

Utilisation du noyau Linux

Le noyau Linux utilise largement les fonctionnalités de pagination de x86 pour permettre des changements de processus rapides avec une petite fragmentation des données.

Dans v4.2, regardez sous arch/x86/:

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

Il ne semble y avoir aucune structure définie pour représenter les pages, seulement des macros: include/asm/page_types.hc'est particulièrement intéressant. Extrait:

#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.hdéfinit CR0, et en particulier la PGposition du bit:

#define X86_CR0_PG_BIT      31 /* Paging */

Bibliographie

Libre:

rutgers-pxk-416 chapitre "Gestion de la mémoire: notes de cours"

Bonne revue historique des techniques d'organisation de la mémoire utilisées par les anciens systèmes d'exploitation.

Non libre:

bovet05 chapitre "Adressage mémoire"

Introduction raisonnable à l'adressage de la mémoire x86. Manque de bons et simples exemples.

Question 3

Voici une réponse très courte et de haut niveau:

Un processeur x86 fonctionne dans l'un des plusieurs modes possibles (en gros: réel, protégé, 64 bits). Chaque mode peut utiliser l'un des nombreux modèles d'adressage mémoire possibles (mais tous les modes ne peuvent pas utiliser tous les modèles), à savoir: l'adressage en mode réel, l'adressage segmenté et l'adressage linéaire plat.

Dans le monde moderne, seul l'adressage linéaire plat en mode protégé ou 64 bits est pertinent, et les deux modes sont essentiellement les mêmes, la principale différence étant la taille du mot machine et donc la quantité de mémoire adressable.

Or, le mode d'adressage mémoire donne un sens aux opérandes mémoire des instructions machine (par exemple mov DWORD PTR [eax], 25, qui stocke un dwordentier 32 bits (aka ) de valeur 25 dans la mémoire dont l'adresse est stockée dans le eaxregistre 32 bits). Dans l'adressage linéaire plat, ce nombre in eaxest autorisé à s'exécuter sur une seule plage contiguë, de zéro à la valeur maximale (dans notre cas, c'est 2 ³² - 1).

Cependant, l'adressage linéaire plat peut être paginé ou non paginé . Sans pagination, l'adresse fait directement référence à la mémoire physique. Avec la pagination, l'unité de gestion de la mémoire du processeur (ou MMU) alimente de manière transparente l'adresse souhaitée (maintenant appelée adresse virtuelle ) dans un mécanisme de recherche, les soi-disant tables de pages , et obtient une nouvelle valeur, qui est interprétée comme une adresse physique. L'opération d'origine opère désormais sur cette nouvelle adresse traduite dans la mémoire physique, même si l'utilisateur ne voit que l'adresse virtuelle.

Le principal avantage de la pagination est que les tables de pages sont gérées par le système d'exploitation. Ainsi, le système d'exploitation peut modifier et remplacer les tableaux de pages de manière arbitraire, par exemple lors d'un "changement de tâche". Il peut conserver toute une collection de tables de pages, une pour chaque "processus", et chaque fois qu'il décide qu'un processus particulier va s'exécuter sur un processeur donné, il charge les tables de pages du processus dans la MMU de ce processeur (chaque processeur a son propre ensemble de tableaux de pages). Le résultat est que chaque processus voit son propre espace d'adressage virtuel qui a le même aspect quelles que soient les pages physiques qui étaient libres lorsque le système d'exploitation a dû lui allouer de la mémoire. Il ne connaît jamais la mémoire d'un autre processus, car il ne peut pas accéder directement à la mémoire physique.

Les tables de pages sont des structures de données imbriquées en forme d'arborescence stockées dans la mémoire normale, écrites par le système d'exploitation mais lues directement par le matériel, le format est donc fixe. Ils sont "chargés" dans la MMU en définissant un registre de contrôle CPU spécial pour pointer vers la table de niveau supérieur. Le processeur utilise un cache appelé TLB pour mémoriser les recherches, de sorte que les accès répétés aux mêmes quelques pages sont beaucoup plus rapides que les accès dispersés, pour des raisons de manque de TLB ainsi que pour les raisons habituelles du cache de données. Il est courant de voir le terme «entrée TLB» utilisé pour faire référence aux entrées de table de page même lorsqu'elles ne sont pas mises en cache dans le TLB.

Et au cas où vous craignez qu'un processus puisse simplement désactiver la pagination ou essayer de modifier les tables de pages: ce n'est pas autorisé, car x86 implémente des niveaux de privilège (appelés «anneaux»), et le code utilisateur s'exécute à un niveau de privilège trop bas pour permettre pour modifier les tables de pages du CPU.

Answer 1

Cette question vise à combler le vide d'une bonne information gratuite sur le sujet.

Je crois qu'une bonne réponse s'intégrera dans une grande réponse SO ou du moins dans quelques réponses.

L'objectif principal est de donner aux débutants juste assez d'informations pour qu'ils puissent prendre le manuel par eux-mêmes et être en mesure de comprendre les concepts de base du système d'exploitation liés à la pagination.

Lignes directrices suggérées:

Les réponses doivent être adaptées aux débutants:
- des exemples concrets, mais éventuellement simplifiés, sont très importants
- les applications des concepts présentés sont les bienvenues
citer des ressources utiles, c'est bien
de petites digressions sur la façon dont les systèmes d'exploitation utilisent les fonctionnalités de pagination sont les bienvenues
Les explications PAE et PSE sont les bienvenues
de petites digressions dans x86_64 sont les bienvenues

Questions connexes et pourquoi je pense qu'elles ne sont pas dupes:

Comment fonctionnent les tableaux de pages x86? : le titre est presque le même que cette question, mais le corps pose des questions spécifiques liées à cr3 et TLB. Cette question est un sous-ensemble de celle-ci.
Comment fonctionne la virtualisation x86 : le corps ne demande que les sources.

Answer 2

1

Cela devrait être étiqueté "faq" et marqué comme "community-wiki".

Kerrek SB

Answer 3

@KerrekSB Je ne sais pas vraiment comment gérer ce genre de questions. Les réponses devraient être des wikis communautaires, c'est ça? Je n'ai pas trouvé de faqbalise.

Ciro Santilli 郝海东冠状病六四事件法轮功

Answer 4

3

Je dirais que la réponse courte est, "lisez Vol 3, Chapitre 4: Pagination dans le Manuel Intel". C'est assez clair, concis et bien écrit, et cela ne fait plus autorité.

Kerrek SB

Answer 5

4

@KerrekSB Je suis d'accord que le manuel est clair et faisant autorité, mais c'était un peu trop dur en première lecture pour moi, j'avais besoin de quelques exemples simples et concrets + une justification pour mieux comprendre les choses.

Ciro Santilli 郝海东冠状病六四事件法轮功

Answer 6

Version de cette réponse avec une belle table des matières et plus de contenu .

Je corrigerai toute erreur signalée. Si vous souhaitez apporter des modifications importantes ou ajouter un aspect manquant, faites-les sur vos propres réponses pour obtenir une réputation bien méritée. Les modifications mineures peuvent être fusionnées directement dans.

Exemple de code

Exemple minimal: https://github.com/cirosantilli/x86-bare-metal-examples/blob/5c672f73884a487414b3e21bd9e579c67cd77621/paging.S

Comme tout le reste de la programmation, la seule façon de vraiment comprendre cela est de jouer avec des exemples minimaux.

Ce qui en fait un sujet "difficile", c'est que l'exemple minimal est grand car vous devez créer votre propre petit système d'exploitation.

Manuel Intel

Bien qu'il soit impossible de comprendre sans exemples en tête, essayez de vous familiariser avec les manuels dès que possible.

Intel décrit la pagination dans le Manuel de programmation du système Intel Volume 3 - 325384-056FR Septembre 2015 Chapitre 4 «Paging».

La Figure 4-4 "Formats des entrées CR3 et de structure de pagination avec pagination 32 bits" est particulièrement intéressante, qui donne les principales structures de données.

MMU

La pagination est effectuée par la partie MMU ( Memory Management Unit ) de la CPU. Comme beaucoup d'autres (par exemple le coprocesseur x87 , APIC ), cela se faisait auparavant par une puce séparée, qui a ensuite été intégrée au processeur. Mais le terme est toujours utilisé.

Faits généraux

Les adresses logiques sont les adresses de mémoire utilisées dans le code utilisateur-pays "normal" (par exemple le contenu de rsiin mov eax, [rsi]).

La première segmentation les traduit en adresses linéaires, puis la pagination traduit les adresses linéaires en adresses physiques.

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

La plupart du temps, nous pouvons considérer les adresses physiques comme indexant les cellules de mémoire matérielles RAM réelles, mais ce n'est pas vrai à 100% à cause de:

La pagination n'est disponible qu'en mode protégé. L'utilisation de la pagination en mode protégé est facultative. La pagination est activée ssi le PGbit du cr0registre est activé.

Pagination vs segmentation

Une différence majeure entre la pagination et la segmentation est que:

la pagination divise la RAM en morceaux de taille égale appelés pages
la segmentation divise la mémoire en morceaux de tailles arbitraires

C'est le principal avantage de la pagination, car des blocs de taille égale rendent les choses plus faciles à gérer.

La pagination est devenue tellement plus populaire que la prise en charge de la segmentation a été abandonnée dans x86-64 en mode 64 bits, le mode de fonctionnement principal des nouveaux logiciels, où elle n'existe qu'en mode de compatibilité, qui émule IA32.

Application

La pagination est utilisée pour implémenter les espaces d'adressage virtuels des processus sur les systèmes d'exploitation modernes. Avec les adresses virtuelles, le système d'exploitation peut adapter deux ou plusieurs processus simultanés sur une seule RAM de manière à:

les deux programmes n'ont besoin de rien savoir de l'autre
la mémoire des deux programmes peut augmenter et diminuer selon les besoins
le passage d'un programme à l'autre est très rapide
un programme ne peut jamais accéder à la mémoire d'un autre processus

La pagination est historiquement venue après la segmentation et l'a largement remplacée pour l'implémentation de la mémoire virtuelle dans les systèmes d'exploitation modernes tels que Linux car il est plus facile de gérer les blocs de mémoire de taille fixe des pages au lieu de segments de longueur variable.

Implémentation matérielle

Comme la segmentation en mode protégé (où la modification d'un registre de segment déclenche un chargement depuis le GDT ou LDT), le matériel de pagination utilise des structures de données en mémoire pour faire son travail (tables de pages, répertoires de pages, etc.).

Le format de ces structures de données est fixé par le matériel , mais il appartient au système d'exploitation de configurer et de gérer correctement ces structures de données sur la RAM, et d'indiquer au matériel où les trouver (via cr3).

Certaines autres architectures laissent la pagination presque entièrement entre les mains du logiciel, de sorte qu'un TLB miss exécute une fonction fournie par le système d'exploitation pour parcourir les tableaux de pages et insérer le nouveau mappage dans le TLB. Cela laisse le choix des formats de table de pages par le système d'exploitation, mais il est peu probable que le matériel puisse chevaucher les parcours de page avec l'exécution dans le désordre d'autres instructions, comme le peut x86 .

Exemple: schéma de pagination simplifié à un seul niveau

Voici un exemple de la façon dont la pagination fonctionne sur une version simplifiée de l'architecture x86 pour implémenter un espace mémoire virtuel.

Tableaux de pages

Le système d'exploitation pourrait leur donner les tableaux de pages suivants:

Tableau des pages donné au processus 1 par l'OS:

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

Tableau des pages donné au processus 2 par l'OS:

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

Où:

PT1et PT2: position initiale des tables 1 et 2 sur la RAM.

Des exemples de valeurs: 0x00000000, 0x12345678, etc.

C'est le système d'exploitation qui décide de ces valeurs.
L: longueur d'une entrée de table de pages.
present: indique que la page est présente en mémoire.

Les tableaux de pages sont situés sur la RAM. Ils pourraient par exemple être situés comme:

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


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


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

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

Les emplacements initiaux sur la RAM pour les deux tables de pages sont arbitraires et contrôlés par le système d'exploitation. C'est à l'OS de s'assurer qu'ils ne se chevauchent pas!

Chaque processus ne peut pas toucher directement les tables de pages, bien qu'il puisse faire des requêtes au système d'exploitation qui entraînent la modification des tables de pages, par exemple en demandant des segments de pile ou de tas plus grands.

Une page est un morceau de 4 Ko (12 bits), et comme les adresses ont 32 bits, seuls 20 bits (20 + 12 = 32, donc 5 caractères en notation hexadécimale) sont nécessaires pour identifier chaque page. Cette valeur est fixée par le matériel.

Entrées de table de page

Une table de pages est ... une table d'entrées de table de pages!

Le format exact des entrées de table est fixé par le matériel .

Dans cet exemple simplifié, les entrées de la table des pages ne contiennent que deux champs:

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

donc dans cet exemple, les concepteurs de matériel auraient pu choisir L = 21.

La plupart des entrées de table de pages réelles ont d'autres champs.

Il ne serait pas pratique d'aligner les choses à 21 bits car la mémoire est adressable par octets et non par bits. Par conséquent, même si seulement 21 bits sont nécessaires dans ce cas, les concepteurs de matériel choisiraient probablement L = 32de rendre l'accès plus rapide et de réserver simplement les bits restants pour une utilisation ultérieure. La valeur réelle pour Lsur x86 est de 32 bits.

Traduction d'adresse dans un schéma à un niveau

Une fois les tables de pages configurées par le système d'exploitation, la traduction d'adresses entre les adresses linéaires et physiques est effectuée par le matériel .

Lorsque le système d'exploitation souhaite activer le processus 1, il définit cr3sur PT1, le début de la table pour le processus un.

Si le processus 1 souhaite accéder à une adresse linéaire 0x00000001, le circuit matériel de radiomessagerie effectue automatiquement les opérations suivantes pour le système d'exploitation:

divisez l'adresse linéaire en deux parties:
```
| page (20 bits) | offset (12 bits) |
```
Donc, dans ce cas, nous aurions:
- page = 0x00000
- offset = 0x001
regardez dans le tableau de la page 1 parce qu'il cr3pointe vers lui.
regardez l'entrée 0x00000parce que c'est la partie de la page.

Le matériel sait que cette entrée se trouve à l'adresse RAM PT1 + 0 * L = PT1.
puisqu'il est présent, l'accès est valide
par la table de page, l'emplacement du numéro de page 0x00000est à 0x00001 * 4K = 0x00001000.
pour trouver l'adresse physique finale, il suffit d'ajouter le décalage:
```
  00001 000
+ 00000 001
  -----------
  00001 001
```
car 00001c'est l'adresse physique de la page recherchée sur la table et 001c'est le décalage.

Comme son nom l'indique, le décalage est toujours simplement ajouté à l'adresse physique de la page.
le matériel obtient alors la mémoire à cet emplacement physique.

De la même manière, les traductions suivantes se produiraient pour le processus 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

Par exemple, lors de l'accès à l'adresse 00001000, la partie de page est 00001le matériel sait que son entrée de table de page est située à l'adresse RAM: PT1 + 1 * L(à 1cause de la partie de page), et c'est là qu'il la recherchera.

Lorsque le système d'exploitation veut passer au processus 2, il lui suffit de cr3pointer vers la page 2. C'est aussi simple que cela!

Maintenant, les traductions suivantes se produiraient pour le processus 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

La même adresse linéaire se traduit par différentes adresses physiques pour différents processus , en fonction uniquement de la valeur à l'intérieur cr3.

De cette façon, chaque programme peut s'attendre à ce que ses données commencent 0et se terminent à FFFFFFFF, sans se soucier des adresses physiques exactes.

Erreur de page

Que faire si le processus 1 essaie d'accéder à une adresse à l'intérieur d'une page qui n'est pas présente?

Le matériel notifie le logiciel via une exception de défaillance de page.

Il appartient alors généralement au système d'exploitation d'enregistrer un gestionnaire d'exceptions pour décider de ce qui doit être fait.

Il est possible que l'accès à une page qui ne figure pas sur la table soit une erreur de programmation:

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

mais il peut y avoir des cas où cela est acceptable, par exemple sous Linux lorsque:

le programme veut augmenter sa pile.

Il essaie simplement d'accéder à un certain octet dans une plage possible donnée, et si le système d'exploitation est satisfait, il ajoute cette page à l'espace d'adressage du processus.
la page a été échangée sur le disque.

Le système d'exploitation devra effectuer un certain travail derrière les processus pour remettre la page dans la RAM.

Le système d'exploitation peut découvrir que c'est le cas en fonction du contenu du reste de l'entrée de la table de pages, car si l'indicateur actuel est clair, les autres entrées de l'entrée de la table de pages sont complètement laissées au système d'exploitation à ce qu'il veut.

Sur Linux par exemple, lorsqu'il est présent = 0:
- si tous les champs de l'entrée de table de page sont 0, adresse invalide.
- sinon, la page a été permutée sur le disque et les valeurs réelles de ces champs codent la position de la page sur le disque.

Dans tous les cas, le système d'exploitation a besoin de savoir quelle adresse a généré l'erreur de page pour pouvoir traiter le problème. C'est pourquoi les gentils développeurs IA32 définissent la valeur de cr2sur cette adresse chaque fois qu'une erreur de page se produit. Le gestionnaire d'exceptions peut alors simplement regarder cr2pour obtenir l'adresse.

Simplifications

Des simplifications à la réalité qui facilitent la compréhension de cet exemple:

tous les circuits de pagination réels utilisent la pagination à plusieurs niveaux pour économiser de l'espace, mais cela a montré un schéma simple à un niveau.
les tables de pages ne contenaient que deux champs: une adresse de 20 bits et un indicateur de présence de 1 bit.

Les tableaux de pages réelles contiennent un total de 12 champs, et donc d'autres fonctionnalités qui ont été omises.

Exemple: schéma de pagination à plusieurs niveaux

Le problème avec un schéma de pagination à un seul niveau est qu'il prendrait trop de RAM: 4G / 4K = 1M d'entrées par processus. Si chaque entrée est longue de 4 octets, cela ferait 4 Mo par processus , ce qui est trop même pour un ordinateur de bureau: ps -A | wc -ldit que j'exécute 244 processus en ce moment, donc cela prendrait environ 1 Go de RAM!

Pour cette raison, les développeurs x86 ont décidé d'utiliser un schéma à plusieurs niveaux qui réduit l'utilisation de la RAM.

L'inconvénient de ce système est qu'il a un temps d'accès légèrement plus élevé.

Dans le schéma de pagination simple à 3 niveaux utilisé pour les processeurs 32 bits sans PAE, les 32 bits d'adresse sont divisés comme suit:

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

Chaque processus doit avoir un et un seul répertoire de pages associé, de sorte qu'il contiendra au moins des 2^10 = 1Kentrées de répertoire de pages, bien mieux que le minimum de 1M requis sur un schéma à un seul niveau.

Les tableaux de pages ne sont alloués que selon les besoins du système d'exploitation. Chaque table de 2^10 = 1Kpages a des entrées de répertoire de pages

Les répertoires de pages contiennent ... des entrées de répertoire de pages! Les entrées de l'annuaire de pages sont les mêmes que les entrées de tables de pages, sauf qu'elles pointent vers les adresses RAM des tables de pages au lieu des adresses physiques des tables . Étant donné que ces adresses ne font que 20 bits de large, les tableaux de pages doivent se trouver au début des pages de 4 Ko.

cr3 pointe maintenant vers l'emplacement sur la RAM du répertoire de pages du processus en cours au lieu des tables de pages.

Les entrées des tables de pages ne changent pas du tout à partir d'un schéma à un seul niveau.

Les tableaux de pages changent d'un schéma à un seul niveau car:

chaque processus peut avoir jusqu'à 1K tables de pages, une par entrée d'annuaire de page.
chaque table de page contient exactement 1K entrées au lieu de 1M d'entrées.

La raison de l'utilisation de 10 bits sur les deux premiers niveaux (et non, par exemple 12 | 8 | 12) est que chaque entrée de la table de pages a une longueur de 4 octets. Ensuite, les 2 ^ 10 entrées des répertoires de pages et des tables de pages s'intégreront parfaitement dans les pages de 4 Ko. Cela signifie qu'il est plus rapide et plus simple d'allouer et de désallouer des pages à cette fin.

Traduction d'adresse dans un schéma à plusieurs niveaux

Répertoire de pages donné au processus 1 par le système d'exploitation:

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

Tables de pages données au processus 1 par le système d'exploitation à 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

Tables de pages données au processus 1 par le système d'exploitation à 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

où:

PD1: position initiale du répertoire de pages du processus 1 sur la RAM.
PT1et PT2: position initiale du tableau de pages 1 et du tableau de pages 2 pour le processus 1 sur la RAM.

Donc, dans cet exemple, le répertoire des pages et la table des pages pourraient être stockés dans la RAM quelque chose comme:

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


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

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


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

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

Traduisons 0x00801004pas à pas l' adresse linéaire .

Nous supposons que cr3 = PD1, c'est-à-dire qu'il pointe vers le répertoire de pages que nous venons de décrire.

En binaire, l'adresse linéaire est:

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

Regrouper comme 10 | 10 | 12donne:

0000000010 0000000001 000000000100
0x2        0x1        0x4

qui donne:

entrée de répertoire de page = 0x2
entrée de table de page = 0x1
offset = 0x4

Le matériel recherche donc l'entrée 2 du répertoire de pages.

La table du répertoire de page indique que la table de page se trouve à 0x80000 * 4K = 0x80000000. Il s'agit du premier accès RAM du processus.

Puisque l'entrée de la table de pages est 0x1, le matériel regarde l'entrée 1 de la table de pages à 0x80000000, qui lui indique que la page physique se trouve à l'adresse 0x0000C * 4K = 0x0000C000. Il s'agit du deuxième accès RAM du processus.

Enfin, le matériel de pagination ajoute le décalage et l'adresse finale est 0x0000C004.

D'autres exemples d'adresses traduites sont:

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

Les erreurs de page se produisent si une entrée d'annuaire de pages ou une entrée de table de pages n'est pas présente.

Si le système d'exploitation souhaite exécuter un autre processus simultanément, il attribuera au second processus un répertoire de pages distinct et liera ce répertoire à des tables de pages distinctes.

Architectures 64 bits

64 bits est toujours trop d'adresse pour les tailles de RAM actuelles, donc la plupart des architectures utiliseront moins de bits.

x86_64 utilise 48 bits (256 Tio) et le PAE du mode hérité autorise déjà les adresses de 52 bits (4 PiB).

12 de ces 48 bits sont déjà réservés pour le décalage, ce qui laisse 36 bits.

Si une approche à 2 niveaux est adoptée, la meilleure répartition serait de deux niveaux de 18 bits.

Mais cela signifierait que le répertoire de pages aurait des 2^18 = 256Kentrées, ce qui prendrait trop de RAM: proche d'une pagination à un seul niveau pour les architectures 32 bits!

Par conséquent, les architectures 64 bits créent encore plus de niveaux de page, généralement 3 ou 4.

x86_64 utilise 4 niveaux dans un 9 | 9 | 9 | 12schéma, de sorte que le niveau supérieur n'occupe que les 2^9entrées de niveau supérieur.

PAE

Extension d'adresse physique.

Avec 32 bits, seuls 4 Go de RAM peuvent être adressés.

Cela a commencé à devenir une limitation pour les grands serveurs, c'est pourquoi Intel a introduit le mécanisme PAE dans Pentium Pro.

Pour résoudre le problème, Intel a ajouté 4 nouvelles lignes d'adresse, de sorte que 64 Go puissent être adressés.

La structure de la table des pages est également modifiée si PAE est activé. La manière exacte dont elle est modifiée dépend de l'activation ou de la désactivation de PSE.

PAE est activé et désactivé via le PAEbit de cr4.

Même si la mémoire adressable totale est de 64 Go, les processus individuels ne peuvent toujours utiliser que jusqu'à 4 Go. Le système d'exploitation peut cependant placer différents processus sur différents blocs de 4 Go.

PSE

Extension de taille de page.

Permet aux pages d'avoir une longueur de 4M (ou 2M si PAE est activé) au lieu de 4K.

PSE est activé et désactivé via le PAEbit de cr4.

Schémas de table de page PAE et PSE

Si PAE et PSE sont actifs, différents schémas de niveau de pagination sont utilisés:

pas de PAE et pas de PSE: 10 | 10 | 12
pas Pae PSE: 10 | 22.

22 est le décalage dans la page de 4 Mo, puisque 22 bits adressent 4 Mo.
PAE et pas de PSE: 2 | 9 | 9 | 12

La raison de conception pour laquelle 9 est utilisé deux fois au lieu de 10 est que maintenant les entrées ne peuvent plus tenir dans 32 bits, qui étaient tous remplis par 20 bits d'adresse et 12 bits d'indicateur significatifs ou réservés.

La raison en est que 20 bits ne suffisent plus pour représenter l'adresse des tables de pages: 24 bits sont désormais nécessaires à cause des 4 fils supplémentaires ajoutés au processeur.

Par conséquent, les concepteurs ont décidé d'augmenter la taille des entrées à 64 bits, et pour les faire tenir dans une table à une seule page, il est nécessaire de réduire le nombre d'entrées à 2 ^ 9 au lieu de 2 ^ 10.

Le 2 de départ est un nouveau niveau de page appelé Table de pointeur de répertoire de page (PDPT), car il pointe vers les répertoires de page et remplit l'adresse linéaire 32 bits. Les PDPT ont également une largeur de 64 bits.

cr3pointe maintenant vers les PDPT qui doivent être sur les quatre premiers 4 Go de mémoire et alignés sur des multiples de 32 bits pour une efficacité d'adressage. Cela signifie qu'il a maintenant cr327 bits significatifs au lieu de 20: 2 ^ 5 pour les 32 multiples * 2 ^ 27 pour compléter les 2 ^ 32 des 4 premiers Go.
PAE et PSE: 2 | 9 | 21

Les concepteurs ont décidé de garder un champ large de 9 bits pour qu'il tienne dans une seule page.

Cela laisse 23 bits. Laisser 2 pour que le PDPT garde les choses uniformes avec le cas PAE sans PSE laisse 21 pour le décalage, ce qui signifie que les pages ont une largeur de 2M au lieu de 4M.

TLB

Le TLB (Translation Lookahead Buffer) est un cache pour les adresses de pagination.

Puisqu'il s'agit d'un cache, il partage de nombreux problèmes de conception du cache du processeur, tels que le niveau d'associativité.

Cette section doit décrire un TLB entièrement associatif simplifié avec 4 entrées d'adresse unique. Notez que comme les autres caches, les vrais TLB ne sont généralement pas entièrement associatifs.

Opération de base

Après une traduction entre l'adresse linéaire et l'adresse physique, elle est stockée sur le TLB. Par exemple, un TLB à 4 entrées démarre dans l'état suivant:

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

Le >indique l'entrée actuelle à remplacer.

et après qu'une adresse linéaire de page 00003est traduite en une adresse physique 00005, le TLB devient:

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

et après une seconde traduction de 00007to 00009il devient:

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

Maintenant, s'il 00003faut à nouveau traduire, le matériel recherche d'abord le TLB et trouve son adresse avec un seul accès RAM 00003 --> 00005.

Bien sûr, 00000n'est pas sur le TLB puisqu'aucune entrée valide ne contient 00000comme clé.

Politique de remplacement

Lorsque TLB est rempli, les anciennes adresses sont écrasées. Tout comme pour le cache CPU, la politique de remplacement est une opération potentiellement complexe, mais une heuristique simple et raisonnable consiste à supprimer l'entrée la moins récemment utilisée (LRU).

Avec LRU, à partir de l'état:

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

l'ajout 0000D -> 0000Adonnerait:

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

CAME

L'utilisation du TLB accélère la traduction, car la traduction initiale nécessite un accès par niveau TLB , ce qui signifie 2 sur un schéma simple de 32 bits, mais 3 ou 4 sur des architectures 64 bits.

Le TLB est généralement mis en œuvre comme un type de RAM coûteux appelé mémoire adressable par le contenu (CAM). CAM implémente une carte associative sur le matériel, c'est-à-dire une structure qui, donnée une clé (adresse linéaire), récupère une valeur.

Les mappages peuvent également être implémentés sur les adresses RAM, mais les mappages CAM peuvent nécessiter beaucoup moins d'entrées qu'un mappage RAM.

Par exemple, une carte dans laquelle:

les clés et les valeurs ont 20 bits (le cas d'un schéma de pagination simple)
au plus 4 valeurs doivent être stockées à chaque fois

pourrait être stocké dans un TLB avec 4 entrées:

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

Cependant, pour implémenter cela avec de la RAM, il serait nécessaire d'avoir 2 ^ 20 adresses :

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

ce qui serait encore plus cher que d'utiliser un TLB.

Entrées invalides

En cas de cr3modification, toutes les entrées TLB sont invalidées, car une nouvelle table de pages pour un nouveau processus va être utilisée, il est donc peu probable que l'une des anciennes entrées ait une signification.

Le x86 propose également l' invlpginstruction qui invalide explicitement une seule entrée TLB. D'autres architectures offrent encore plus d'instructions aux entrées TLB invalides, telles que l'invalidation de toutes les entrées sur une plage donnée.

Certains processeurs x86 vont au-delà des exigences de la spécification x86 et offrent plus de cohérence qu'elle n'en garantit, entre la modification d'une entrée de table de page et son utilisation, alors qu'elle n'était pas déjà mise en cache dans le TLB . Apparemment, Windows 9x s'est appuyé sur cela pour l'exactitude, mais les processeurs AMD modernes ne permettent pas de parcourir les pages cohérentes. Les processeurs Intel le font, même s'ils doivent détecter des spéculations erronées pour le faire. En tirer parti est probablement une mauvaise idée, car il n'y a probablement pas grand chose à gagner, et un grand risque de causer de subtils problèmes sensibles au timing qui seront difficiles à déboguer.

Utilisation du noyau Linux

Le noyau Linux utilise largement les fonctionnalités de pagination de x86 pour permettre des changements de processus rapides avec une petite fragmentation des données.

Dans v4.2, regardez sous arch/x86/:

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

Il ne semble y avoir aucune structure définie pour représenter les pages, seulement des macros: include/asm/page_types.hc'est particulièrement intéressant. Extrait:

#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.hdéfinit CR0, et en particulier la PGposition du bit:

#define X86_CR0_PG_BIT      31 /* Paging */

Bibliographie

Libre:

rutgers-pxk-416 chapitre "Gestion de la mémoire: notes de cours"

Bonne revue historique des techniques d'organisation de la mémoire utilisées par les anciens systèmes d'exploitation.

Non libre:

bovet05 chapitre "Adressage mémoire"

Introduction raisonnable à l'adressage de la mémoire x86. Manque de bons et simples exemples.

Answer 7

Excellente réponse, mais je ne sais toujours pas comment LRU est décidé. Invoquer le système d'exploitation à chaque fois qu'une page autre que MRU est accédée semble coûteux. Alternativement, je pourrais voir le matériel réorganiser la table des pages pour LRU, ce qui peut être dangereux pour les programmes concurrents. Est-ce que l'un ou l'autre est correct? Comment le système d'exploitation sait-il quelle page est le LRU lorsqu'une erreur de page se produit?

Keynan

Answer 8

@Keynan Je pense que c'est le matériel qui le fait, donc le temps nécessaire n'est pas un problème. Quant à la concurrence, je ne sais pas comment elle est gérée. Je pense qu'il y a un CR3 et un cache par processeur, et le système d'exploitation doit juste s'assurer que les pages de mémoire ne se chevauchent pas.

Ciro Santilli 郝海东冠状病六四事件法轮功

Answer 9

1

real TLBs are not usually fully associative… The TLB is usually implemented as … CAMCes deux déclarations ne sont-elles pas contradictoires?

a3f

Answer 10

>>> x86_64 utilise 4 niveaux dans un 9 | 9 | 9 | 12 régime il devrait être 9 | 9 | 9 | 9 | 12？

monklof

Answer 11

@monklof Je pense que c'est correct: 9 9 9 12 autorise déjà 512 Go de RAM. Le schéma à 5 niveaux est un développement plus récent destiné uniquement aux serveurs, cela est mentionné dans la réponse de mon site Web qui est plus à jour.

Ciro Santilli 郝海东冠状病六四事件法轮功

Answer 12

Voici une réponse très courte et de haut niveau:

Un processeur x86 fonctionne dans l'un des plusieurs modes possibles (en gros: réel, protégé, 64 bits). Chaque mode peut utiliser l'un des nombreux modèles d'adressage mémoire possibles (mais tous les modes ne peuvent pas utiliser tous les modèles), à savoir: l'adressage en mode réel, l'adressage segmenté et l'adressage linéaire plat.

Dans le monde moderne, seul l'adressage linéaire plat en mode protégé ou 64 bits est pertinent, et les deux modes sont essentiellement les mêmes, la principale différence étant la taille du mot machine et donc la quantité de mémoire adressable.

Or, le mode d'adressage mémoire donne un sens aux opérandes mémoire des instructions machine (par exemple mov DWORD PTR [eax], 25, qui stocke un dwordentier 32 bits (aka ) de valeur 25 dans la mémoire dont l'adresse est stockée dans le eaxregistre 32 bits). Dans l'adressage linéaire plat, ce nombre in eaxest autorisé à s'exécuter sur une seule plage contiguë, de zéro à la valeur maximale (dans notre cas, c'est 2 ³² - 1).

Cependant, l'adressage linéaire plat peut être paginé ou non paginé . Sans pagination, l'adresse fait directement référence à la mémoire physique. Avec la pagination, l'unité de gestion de la mémoire du processeur (ou MMU) alimente de manière transparente l'adresse souhaitée (maintenant appelée adresse virtuelle ) dans un mécanisme de recherche, les soi-disant tables de pages , et obtient une nouvelle valeur, qui est interprétée comme une adresse physique. L'opération d'origine opère désormais sur cette nouvelle adresse traduite dans la mémoire physique, même si l'utilisateur ne voit que l'adresse virtuelle.

Le principal avantage de la pagination est que les tables de pages sont gérées par le système d'exploitation. Ainsi, le système d'exploitation peut modifier et remplacer les tableaux de pages de manière arbitraire, par exemple lors d'un "changement de tâche". Il peut conserver toute une collection de tables de pages, une pour chaque "processus", et chaque fois qu'il décide qu'un processus particulier va s'exécuter sur un processeur donné, il charge les tables de pages du processus dans la MMU de ce processeur (chaque processeur a son propre ensemble de tableaux de pages). Le résultat est que chaque processus voit son propre espace d'adressage virtuel qui a le même aspect quelles que soient les pages physiques qui étaient libres lorsque le système d'exploitation a dû lui allouer de la mémoire. Il ne connaît jamais la mémoire d'un autre processus, car il ne peut pas accéder directement à la mémoire physique.

Les tables de pages sont des structures de données imbriquées en forme d'arborescence stockées dans la mémoire normale, écrites par le système d'exploitation mais lues directement par le matériel, le format est donc fixe. Ils sont "chargés" dans la MMU en définissant un registre de contrôle CPU spécial pour pointer vers la table de niveau supérieur. Le processeur utilise un cache appelé TLB pour mémoriser les recherches, de sorte que les accès répétés aux mêmes quelques pages sont beaucoup plus rapides que les accès dispersés, pour des raisons de manque de TLB ainsi que pour les raisons habituelles du cache de données. Il est courant de voir le terme «entrée TLB» utilisé pour faire référence aux entrées de table de page même lorsqu'elles ne sont pas mises en cache dans le TLB.

Et au cas où vous craignez qu'un processus puisse simplement désactiver la pagination ou essayer de modifier les tables de pages: ce n'est pas autorisé, car x86 implémente des niveaux de privilège (appelés «anneaux»), et le code utilisateur s'exécute à un niveau de privilège trop bas pour permettre pour modifier les tables de pages du CPU.

Comment fonctionne la pagination x86?

Réponses:

Exemple de code

Manuel Intel

MMU

Faits généraux

Pagination vs segmentation

Application

Implémentation matérielle

Exemple: schéma de pagination simplifié à un seul niveau

Tableaux de pages

Entrées de table de page

Traduction d'adresse dans un schéma à un niveau

Erreur de page

Simplifications

Exemple: schéma de pagination à plusieurs niveaux

Traduction d'adresse dans un schéma à plusieurs niveaux

Architectures 64 bits

PAE

PSE

Schémas de table de page PAE et PSE

TLB

Opération de base

Politique de remplacement

CAME

Entrées invalides

Utilisation du noyau Linux

Bibliographie