Intel x86 Assembly Language & Microarchitecture
Paging - Adressage virtuel et mémoire

introduction

Histoire

Les premiers ordinateurs

Les premiers ordinateurs avaient un bloc de mémoire dans lequel le programmeur mettait du code et des données, et le processeur était exécuté dans cet environnement. Étant donné que les ordinateurs étaient alors très coûteux, il était regrettable qu’ils fassent un travail, s’arrêtent et attendent que le prochain travail soit chargé, puis qu’ils le traitent.

Multi-utilisateurs, multi-traitement

Ainsi, les ordinateurs sont rapidement devenus plus sophistiqués et ont pris en charge plusieurs utilisateurs et / ou programmes simultanément - mais c'est à ce moment-là que les problèmes ont commencé à se poser avec l'idée simple d'un "bloc de mémoire". Si un ordinateur exécutait deux programmes simultanément ou exécutait le même programme pour plusieurs utilisateurs, ce qui aurait bien sûr exigé des données séparées pour chaque utilisateur, la gestion de cette mémoire devenait critique.

Exemple

Par exemple: si un programme a été écrit pour fonctionner à l'adresse mémoire 1000, mais qu'un autre programme y était déjà chargé, le nouveau programme n'a pas pu être chargé. Une façon de résoudre ce problème serait de faire fonctionner les programmes avec un "adressage relatif" - peu importe où le programme était chargé, il ne faisait que tout ce qui concernait l'adresse mémoire dans laquelle il était chargé.

Sophistication

Au fur et à mesure que le matériel informatique devenait plus sophistiqué, il était capable de prendre en charge des blocs de mémoire plus importants, autorisant davantage de programmes simultanés, et il devenait plus difficile d'écrire des programmes qui n'interféraient pas avec ce qui était déjà chargé. Une référence de mémoire parasite pourrait faire tomber non seulement le programme en cours, mais tout autre programme en mémoire, y compris le système d'exploitation lui-même!

Solutions

Ce qui était nécessaire était un mécanisme permettant à des blocs de mémoire d’avoir des adresses dynamiques . De cette façon, un programme pourrait être écrit pour fonctionner avec ses blocs de mémoire à des adresses reconnues - et ne pas pouvoir accéder à d’autres blocs pour d’autres programmes (à moins d’une coopération).

Segmentation

Un mécanisme implémenté était la segmentation. Cela permettait de définir des blocs de mémoire de différentes tailles et le programme devait définir le segment auquel il souhaitait accéder en permanence.

Problèmes

Cette technique était puissante, mais sa flexibilité même posait problème. Étant donné que les segments subdivisaient essentiellement la mémoire disponible en blocs de tailles différentes, la gestion de la mémoire pour ces segments posait un problème: allocation, désallocation, croissance, réduction, fragmentation.

Pagination

Une autre technique divisait toute la mémoire en blocs de même taille, appelés "Pages", ce qui rendait très simples les routines d’allocation et de désallocation et éliminait la croissance, la réduction et la fragmentation (à l’exception de la fragmentation interne gaspillage).

Adressage virtuel

En divisant la mémoire en ces blocs, ils pourraient être alloués à différents programmes selon les besoins, quelle que soit l'adresse à laquelle le programme en avait besoin. Ce "mapping" entre l'adresse physique de la mémoire et l'adresse souhaitée par le programme est très puissant et constitue la base de la gestion de la mémoire de tous les processeurs majeurs (Intel, ARM, MIPS, Power et autres).

Prise en charge du matériel et du système d'exploitation

Le matériel effectuait le remappage automatiquement et continuellement, mais nécessitait de la mémoire pour définir les tables de ce qu'il fallait faire. Bien sûr, le ménage associé à ce remappage devait être contrôlé par quelque chose. Le système d'exploitation devrait distribuer la mémoire selon les besoins et gérer les tables de données requises par le matériel pour prendre en charge les programmes requis.

Fonctions de pagination

Une fois que le matériel a pu faire ce remappage, qu'est-ce que cela permettait? Le principal moteur était le multitraitement - la possibilité d'exécuter plusieurs programmes, chacun avec sa propre mémoire, protégée l'un de l'autre. Mais deux autres options incluaient "données rares" et "mémoire virtuelle".

Multitraitement

Chaque programme recevait son propre «espace d'adressage» virtuel - une gamme d'adresses sur lesquelles il était possible de mapper la mémoire physique, à toutes les adresses souhaitées. Tant qu'il y avait suffisamment de mémoire physique pour se déplacer (voir "Mémoire virtuelle" ci-dessous), de nombreux programmes pouvaient être pris en charge simultanément.

De plus, ces programmes ne pouvaient pas accéder à la mémoire qui n'était pas mappée dans leur espace d'adressage virtuel - la protection entre les programmes était automatique. Si les programmes devaient communiquer, ils pouvaient demander au système d'exploitation d'organiser un bloc de mémoire partagé - un bloc de mémoire physique qui était mappé simultanément dans les espaces d'adressage de deux programmes différents.

Données rares

Autoriser un espace d'adressage virtuel énorme (4 Go est typique, pour correspondre aux registres 32 bits généralement utilisés par ces processeurs) ne gaspille pas en soi la mémoire si de grandes zones de cet espace d'adresses ne sont pas cartographiées. Cela permet la création d'énormes structures de données où seules certaines parties sont mappées à la fois. Imaginez un tableau tridimensionnel de 1 000 octets dans chaque direction: cela prend normalement un milliard d'octets! Mais un programme pourrait réserver un bloc de son espace d'adressage virtuel pour "conserver" ces données, mais uniquement pour cartographier les petites sections au fur et à mesure de leur remplissage. Cela permet une programmation efficace, sans gaspiller de mémoire pour les données qui ne sont pas encore nécessaires.

Mémoire virtuelle

Ci-dessus, j'ai utilisé le terme "adressage virtuel" pour décrire l'adressage virtuel-physique effectué par le matériel. Ceci est souvent appelé "mémoire virtuelle" - mais ce terme correspond plus correctement à la technique d'utilisation de l'adressage virtuel pour prendre en charge une illusion de mémoire plus importante que celle réellement disponible.

Cela fonctionne comme ceci:

• À mesure que les programmes sont chargés et demandent plus de mémoire, le système d'exploitation fournit la mémoire à partir des ressources disponibles. En plus de garder une trace de la mémoire qui a été mappée, le système d'exploitation garde également une trace du moment où la mémoire est réellement utilisée - le matériel prend en charge le marquage des pages utilisées.
• Lorsque le système d'exploitation est à court de mémoire physique, il examine toute la mémoire qu'il a déjà distribuée, quelle que soit la page la moins utilisée ou la plus longue. Il enregistre le contenu de cette page particulière sur le disque dur, se souvient de l'endroit où il se trouvait, le marque comme "non présent" sur le matériel du propriétaire d'origine, puis met à zéro la page et la remet au nouveau propriétaire.
• Si le propriétaire d'origine tente à nouveau d'accéder à cette page, le matériel notifie le système d'exploitation. Le système d'exploitation alloue ensuite une nouvelle page (peut-être encore une fois à l'étape précédente!), Charge le contenu de l'ancienne page, puis transmet la nouvelle page au programme d'origine.

  Le point important à noter est que, puisque n'importe quelle page peut être associée à n'importe quelle adresse et que chaque page a la même taille, une page est aussi bonne que n'importe quelle autre - tant que le contenu reste le même!

• Si un programme accède à un emplacement de mémoire non mappé, le matériel notifie le système d'exploitation comme avant. Cette fois, le système d'exploitation note que ce n'était pas une page qui avait été sauvegardée, donc le reconnaît comme un bogue dans le programme et le termine!

  C'est effectivement ce qui se passe lorsque votre application disparaît mystérieusement sur vous - peut-être avec un MessageBox du système d'exploitation. C'est aussi ce qui arrive (souvent) à provoquer un tristement célèbre Blue Screen ou Sad Mac - le programme buggé était en fait un pilote de système d'exploitation qui avait accès à la mémoire qu'il ne devait pas!

Décisions de paging

Les architectes de matériel ont dû prendre de grandes décisions concernant Paging, car la conception affecterait directement la conception du processeur! Un système très flexible aurait un coût élevé, nécessitant de grandes quantités de mémoire uniquement pour gérer l’infrastructure de pagination elle-même.

Quelle taille doit avoir une page?

Dans le matériel, l'implémentation la plus simple de la pagination serait de prendre une adresse et de la diviser en deux parties. La partie supérieure serait un indicateur de la page à laquelle accéder, tandis que la partie inférieure serait l'index de la page pour l'octet requis:

+-----------------+------------+
| Page index      | Byte index |
+-----------------+------------+

Il est vite devenu évident que de petites pages nécessiteraient de vastes index pour chaque programme: même la mémoire qui n’était pas mappée aurait besoin d’une entrée dans la table pour indiquer cela.

Au lieu de cela, un index multi-niveaux est utilisé. L'adresse est divisée en plusieurs parties (trois sont indiquées dans l'exemple ci-dessous) et la partie supérieure (communément appelée "Répertoire") indexe la partie suivante et ainsi de suite jusqu'à ce que l'index d'octet final de la page finale soit décodé:

+-----------+------------+------------+
| Dir index | Page index | Byte index |
+-----------+------------+------------+

Cela signifie qu'un index de répertoire peut indiquer "non mappé" pour une grande partie de l'espace d'adressage, sans nécessiter de nombreux index de page.

Comment optimiser l'utilisation des tables de pages?

Chaque accès d'adresse que fera le processeur devra être mappé - le processus virtuel vers physique doit donc être aussi efficace que possible. Si le système à trois niveaux décrit ci-dessus devait être implémenté, cela signifierait que chaque accès à la mémoire serait en réalité trois accès: un dans le répertoire; un dans la table des pages; et enfin les données souhaitées elles-mêmes. Et si le processeur devait également effectuer des tâches de maintenance, par exemple pour indiquer que cette page avait été accédée ou écrite, cela nécessiterait encore plus d’accès pour mettre à jour les champs.

La mémoire peut être rapide, mais cela imposerait un triple ralentissement sur tous les accès à la mémoire pendant la pagination! Heureusement, la plupart des programmes ont une "localité de portée". En d'autres termes, s'ils accèdent à un emplacement en mémoire, les accès futurs seront probablement proches. Et comme les pages ne sont pas trop petites, cette conversion de mappage n'a besoin d'être effectuée que lors de l'accès à une nouvelle page: pas pour tous les accès.

Mais mieux encore serait d’implémenter un cache de pages récemment accédées, pas seulement la plus récente. Le problème serait de suivre les pages auxquelles on avait accédé et ce qui ne l’était pas - le matériel devrait parcourir le cache à chaque accès pour trouver la valeur mise en cache. Ainsi, le cache est implémenté comme un cache adressable par le contenu: au lieu d'être accédé par adresse, il est accessible par contenu - si les données demandées sont présentes, elles sont proposées, sinon un emplacement vide est marqué. Le cache gère tout cela.

Ce cache adressable par contenu est souvent appelé TLB (Translation Lookaside Buffer) et doit être géré par le système d'exploitation dans le cadre du sous-système d'adressage virtuel. Lorsque les répertoires ou les tables de pages sont modifiés par le système d'exploitation, il doit notifier le TLB pour mettre à jour ses entrées - ou simplement les invalider.

80386 Paging

Conception de haut niveau

Le 80386 est un processeur 32 bits, avec un espace mémoire adressable de 32 bits. Les concepteurs du sous-système Paging ont noté qu'une conception de page 4K était mappée sur ces 32 bits de manière très nette - 10 bits, 10 bits et 12 bits:

+-----------+------------+------------+
| Dir index | Page index | Byte index |
+-----------+------------+------------+
 3         2 2          1 1          0  Bit
 1         2 1          2 1          0  number

Cela signifiait que l'index d'octet était de 12 bits de large, ce qui indexerait dans une page 4K. Les index de répertoire et de page étaient de 10 bits, ce qui ferait en sorte que chaque carte dans une table de 1 024 entrées - et si ces entrées de table étaient chacune de 4 octets, ce serait 4K par table: également une page!

Alors c'est ce qu'ils ont fait:

• Chaque programme aurait son propre répertoire, une page avec 1 024 entrées de page, chacune définissant où se trouvait la table de pages suivante - s'il y en avait une.
• Si c'était le cas, cette table de pages comporterait 1 024 entrées de page, chacune définissant où se trouvait la dernière page - s'il y en avait une.
• S'il y en avait, alors son Byte pourrait être lu directement.

Entrée de la page

Le répertoire de niveau supérieur et la table de pages de niveau supérieur sont composés de 1 024 entrées de page. La partie la plus importante de ces entrées est l'adresse de ce qu'elle indexe: une table de pages ou une page réelle. Notez que cette adresse n'a pas besoin des 32 bits complets - puisque tout est une page, seuls les 20 bits supérieurs sont significatifs. Ainsi, les 12 autres bits de l’entrée de page peuvent être utilisés pour d’autres choses: si le niveau suivant est même présent; le ménage quant à savoir si la page a été accédée ou écrite; et même si les écritures devraient même être autorisées!

+--------------+----+------+-----+---+---+
| Page Address | OS | Used | Sup | W | P |
+--------------+----+------+-----+---+---+
Page Address = Top 20 bits of Page Table or Page address
OS           = Available for OS use
Used         = Whether this page has been accessed or written to
Sup          = Whether this page is Supervisory - only accessible by the OS
W            = Whether this page is allowed to be Written
P            = Whether this page is even Present

Notez que si le bit P est égal à 0, le reste de l'entrée peut contenir tout ce que le système d'exploitation souhaite y placer, par exemple le contenu de la page sur le disque dur!

Registre de base de répertoire de pages ( PDBR )

Si chaque programme a son propre répertoire, comment le matériel sait-il où commencer le mappage? Étant donné que le processeur n'exécute qu'un seul programme à la fois, il dispose d'un registre de contrôle unique pour contenir l'adresse du répertoire du programme en cours. C'est le registre de base du répertoire de pages ( CR3 ). Lorsque le système d'exploitation bascule entre différents programmes, il met à jour le PDBR avec le répertoire de pages correspondant au programme.

Défauts de page

Chaque fois que le processeur accède à la mémoire, il doit mapper l'adresse virtuelle indiquée dans l'adresse physique appropriée. Ceci est un processus en trois étapes:

1. Indexer les 10 premiers bits de l'adresse dans la page indiquée par le PDBR pour obtenir l'adresse de la table de pages appropriée;
2. Indexer les 10 prochains bits de l'adresse dans la page indiquée par l'annuaire pour obtenir l'adresse de la page appropriée;
3. Indexez les 12 derniers bits de l'adresse pour extraire les données de cette page.

Parce que les deux étapes 1. et 2. ci-dessus utilisent les entrées de page, chaque entrée peut indiquer un problème:

• Le niveau suivant peut être marqué "Non présent";
• Le niveau suivant peut être marqué comme "Lecture seule" - et l'opération est une écriture;
• Le niveau suivant peut être marqué comme "Superviseur" - et c'est le programme qui accède à la mémoire, pas le système d'exploitation.

Lorsqu'un problème est détecté par le matériel, au lieu d'effectuer l'accès, il génère une erreur: Interruption # 14, le défaut de page. Il remplit également certains registres de contrôle spécifiques avec les informations expliquant pourquoi l'erreur s'est produite: l'adresse référencée; si c'était un accès de superviseur; et si c'était une tentative d'écriture.

Le système d'exploitation est censé piéger cette erreur, décoder les registres de contrôle et décider quoi faire. S'il s'agit d'un accès non valide, il peut mettre fin au programme défaillant. S'il s'agit d'un accès à la mémoire virtuelle, le système d'exploitation doit allouer une nouvelle page (qui peut devoir libérer une page déjà utilisée!), La remplir avec le contenu requis (soit tous les zéros, soit le contenu précédent chargé du disque). ), mappez la nouvelle page dans la table de pages appropriée, marquez-la comme étant présente, puis reprenez l'instruction de défaillance. Cette fois, l’accès progressera avec succès et le programme se poursuivra sans savoir que quelque chose de spécial s’est produit (à moins de regarder l’horloge!)

80486 Paging

Le sous-système de pagination 80486 était très similaire au sous-système 80386. Il était rétrocompatible et les seules nouvelles fonctionnalités consistaient à autoriser le contrôle du cache mémoire sur une base de page par page - les concepteurs de système d'exploitation pouvaient marquer des pages spécifiques comme ne devant pas être mises en cache ou utiliser différentes écritures ou réécritures. techniques de mise en cache.

À tous autres égards, l'exemple "80386 Paging" est applicable.

Pentium Paging

Lors de la mise au point du Pentium, la taille de la mémoire et les programmes qui fonctionnaient étaient de plus en plus importants. Le système d'exploitation a dû faire de plus en plus de travail pour maintenir le sous-système de pagination juste dans le nombre même d'index de page devant être mis à jour lorsque des programmes ou des ensembles de données volumineux étaient utilisés.

Les concepteurs de Pentium ont donc ajouté un truc simple: ils ont ajouté un bit supplémentaire dans les entrées du répertoire de pages pour indiquer si le niveau suivant était un tableau de pages (comme auparavant) ou s’ils étaient directement sur une page de 4 Mo! En ayant le concept de 4 Mo Pages, le système d'exploitation n'aurait pas à créer une table de pages et à la remplir avec 1 024 entrées indexant essentiellement des adresses 4 Ko plus élevées que la précédente.

Disposition de l'adresse

+-----------+----------------------+
| Dir Index | 4MB Byte Index       |
+-----------+----------------------+
 3         2 2                    0   Bit
 1         2 1                    0   number

Disposition d'entrée d'annuaire

+-----------+----+---+------+-----+---+---+
| Page Addr | OS | S | Used | Sup | W | P |
+-----------+----+---+------+-----+---+---+
Page Addr = Top 20 bits of Page Table or Page address
OS        = Available for OS use
S         = Size of Next Level: 0 = Page Table, 1 = 4 MB Page
Used      = Whether this page has been accessed or written to
Sup       = Whether this page is Supervisory - onlly accessible by the OS
W         = Whether this page is allowed to be Written
P         = Whether this page is even Present

Bien sûr, cela a eu des ramifications:

• La page 4 Mo devait commencer sur une limite d’adresse de 4 Mo, tout comme les pages 4K devaient commencer sur une limite d’adresse 4K.
• Tous les 4 Mo devaient appartenir à un seul programme - ou être partagés par plusieurs.

C'était parfait pour les périphériques à grande mémoire, tels que les cartes graphiques, qui avaient de grandes fenêtres d'espace d'adressage qui devaient être mappées pour que le système d'exploitation puisse les utiliser.

Extension d'adresse physique (PAE)

introduction

Au fur et à mesure que les prix de la mémoire chutaient, les PC à processeur Intel étaient en mesure d’avoir accès à de plus en plus de RAM, ce qui a permis d’atténuer les problèmes rencontrés par de nombreux utilisateurs. Alors que la mémoire virtuelle permettait de "créer" virtuellement la mémoire - en échangeant les "anciens" contenus de page existants sur le disque dur pour permettre le stockage de "nouvelles" données - cela ralentissait l'exécution des programmes. sur et hors du disque dur.

Plus de RAM

Ce qui était nécessaire était la possibilité d'accéder à plus de RAM physique - mais c'était déjà un bus d'adresse 32 bits, donc toute augmentation nécessiterait des registres d'adresses plus importants. Ou serait-ce? Lors du développement du Pentium Pro (et même du Pentium M), en tant que point d'arrêt jusqu'à ce que des processeurs 64 bits puissent être produits, ajouter davantage de bits d'adresse physique (permettant plus de mémoire physique) sans changer le nombre de bits du registre. Cela pourrait être réalisé puisque les adresses virtuelles étaient de toute façon mappées sur des adresses physiques - tout ce qui était nécessaire pour changer était le système de cartographie.

Conception

Le système existant pouvait accéder à un maximum de 32 bits d'adresses physiques. L'augmentation nécessitait un changement complet de la structure de saisie de page, de 32 à 64 bits. Il a été décidé de conserver la granularité minimale à 4K Pages, de sorte que l'entrée 64 bits aurait 52 bits d'adresse et 12 bits de contrôle (comme l'entrée précédente avait 20 bits d'adresse et 12 bits de contrôle).

Avoir une entrée de 64 bits, mais une taille de page (encore) de 4 Ko, signifiait qu'il n'y aurait que 512 entrées par table de pages ou répertoire, au lieu des 1 024 précédentes. Cela signifiait que l'adresse virtuelle 32 bits serait divisée différemment:

+-----+-----------+------------+------------+
| DPI | Dir Index | Page Index | Byte Index |
+-----+-----------+------------+------------+
 3   3 2         2 2          1 1          0   Bit
 1   0 9         1 0          2 1          0   number

 DPI        = 2-bit index into Directory Pointer Table
 Dir Index  = 9-bit index into Directory
 Page Index = 9-bit index into Page Table
 Byte Index = 12-bit index into Page (as before)

Couper un bit à la fois de l'index de répertoire et de l'index de page donnait deux bits pour un troisième niveau de mappage: ils appelaient cela la table PDPT (Table Directory Point Table), une table contenant exactement quatre entrées 64 bits au lieu de la précédente. un. Le PDBR ( CR3 ) pointe maintenant vers le PDPT à la place - qui, étant donné que le CR3 n’a que 32 bits, doit être stocké dans les 4 premiers Go de RAM pour être accessible. Notez que puisque les bits bas de CR3 sont utilisés pour le contrôle, le PDPT doit commencer sur une limite de 32 octets.

Extension de taille de page (PSE)

Et comme les pages précédentes de 4 Mo étaient une si bonne idée, elles souhaitaient pouvoir prendre en charge de grandes pages. Cette fois-ci, la suppression de la dernière couche du système de niveau n'a pas produit 10 pages de 12 Mo ou 4 Mo, mais 9 Mo de pages de 2 bits à la place.

PSE-32 (et PSE-40)

Étant donné que le mode d'extension d'adresse physique (PAE) introduit dans Pentium Pro (et Pentum M) était un tel changement du sous-système de gestion de la mémoire du système d'exploitation, Intel a conçu le mode de page «normal» pour prendre en charge les nouveaux bits d'adresse physique du processeur dans les entrées 32 bits définies précédemment.

Ils ont réalisé que quand une page de 4 Mo était utilisée, l'entrée de répertoire ressemblait à ceci:

+-----------+------------+---------+
| Dir Index |  Unused    | Control |
+-----------+------------+---------+

Les zones Dir Index et Control de l'entrée étaient les mêmes, mais le bloc de bits inutilisés entre eux - qui serait utilisé par l'index de page s'il existait - était gaspillé. Ils ont donc décidé d'utiliser cette zone pour définir les bits d'adresse physique supérieurs à 31 !

+-----------+------+-----+---------+
| Dir Index |Unused|Upper| Control |
+-----------+------+-----+---------+

Cela permettait aux systèmes d'exploitation qui n'adoptaient pas le mode PAE d'accéder à une mémoire vive supérieure à 4 Go - avec un peu de logique supplémentaire, ils pouvaient fournir de grandes quantités de mémoire vive supplémentaire au système, sans dépasser les 4 Go normaux. Au début, seuls 4 bits ont été ajoutés, ce qui permet un adressage physique sur 36 bits. Ce mode s'appelait donc Extension de format de page 36 (PSE-36). En réalité, cela n'a pas modifié la taille de la page, mais uniquement l'adressage.

La limitation de ceci était que seulement 4MB Pages au-dessus de 4 Go étaient définissables - 4K Pages n'étaient pas autorisées. L'adoption de ce mode n'était pas très large - il était apparemment plus lent que d'utiliser PAE, et Linux ne l'a jamais utilisé.

Néanmoins, dans les processeurs ultérieurs qui avaient encore plus de bits d’adresse physique, AMD et Intel ont tous deux élargi la zone PSE à 8 bits, ce que certains appellent "PSE-40".