Wie funktioniert x86-Paging?

Version dieser Antwort mit einem schönen Inhaltsverzeichnis und mehr Inhalt .

Ich werde jeden gemeldeten Fehler korrigieren. Wenn Sie große Änderungen vornehmen oder einen fehlenden Aspekt hinzufügen möchten, nehmen Sie diese nach Ihren eigenen Antworten vor, um die wohlverdiente Wiederholung zu erhalten. Kleinere Änderungen können direkt in zusammengeführt werden.

Beispielcode

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

Wie alles andere in der Programmierung besteht die einzige Möglichkeit, dies wirklich zu verstehen, darin, mit minimalen Beispielen zu spielen.

Was dies zu einem "schwierigen" Thema macht, ist, dass das minimale Beispiel groß ist, weil Sie Ihr eigenes kleines Betriebssystem erstellen müssen.

Intel Handbuch

Obwohl es ohne Beispiele nicht zu verstehen ist, versuchen Sie, sich so schnell wie möglich mit den Handbüchern vertraut zu machen.

Intel beschreibt das Paging im Intel Manual Volume 3 System Programming Guide - 325384-056US September 2015, Kapitel 4 "Paging".

Besonders interessant ist Abbildung 4-4 "Formate von CR3- und Paging-Struktur-Einträgen mit 32-Bit-Paging", in der die wichtigsten Datenstrukturen dargestellt sind.

MMU

Das Paging erfolgt durch den MMU-Teil ( Memory Management Unit ) der CPU. Wie viele andere (z. B. x87-Co-Prozessor , APIC ) war dies früher ein separater Chip, der später in die CPU integriert wurde. Aber der Begriff wird immer noch verwendet.

Generelle Fakten

Logische Adressen sind die Speicheradressen, die im "normalen" Benutzerlandcode verwendet werden (z. B. der Inhalt von rsiin mov eax, [rsi]).

Die erste Segmentierung übersetzt sie in lineare Adressen, und das Paging übersetzt dann lineare Adressen in physikalische Adressen.

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

In den meisten Fällen können wir uns physische Adressen als Indizierung der tatsächlichen RAM-Hardwarespeicherzellen vorstellen. Dies ist jedoch nicht zu 100% der Fall, weil:

Paging ist nur im geschützten Modus verfügbar. Die Verwendung von Paging im geschützten Modus ist optional. Paging ist aktiviert, wenn das PGBit des cr0Registers gesetzt ist.

Paging gegen Segmentierung

Ein wesentlicher Unterschied zwischen Paging und Segmentierung besteht darin, dass:

Beim Paging wird der Arbeitsspeicher in gleich große Blöcke aufgeteilt, die als Seiten bezeichnet werden
Die Segmentierung teilt den Speicher in Blöcke beliebiger Größe auf

Dies ist der Hauptvorteil des Paging, da gleich große Blöcke die Verwaltung vereinfachen.

Paging ist so populär geworden, dass die Unterstützung für die Segmentierung in x86-64 im 64-Bit-Modus, dem Hauptbetriebsmodus für neue Software, eingestellt wurde, wo es nur im Kompatibilitätsmodus existiert, der IA32 emuliert.

Anwendung

Paging wird verwendet, um virtuelle Adressräume von Prozessen in modernen Betriebssystemen zu implementieren. Mit virtuellen Adressen kann das Betriebssystem zwei oder mehr gleichzeitige Prozesse in einem einzelnen RAM so anpassen, dass:

Beide Programme müssen nichts über das andere wissen
Der Speicher beider Programme kann nach Bedarf vergrößert und verkleinert werden
Der Wechsel zwischen den Programmen ist sehr schnell
Ein Programm kann niemals auf den Speicher eines anderen Prozesses zugreifen

Das Paging erfolgte historisch nach der Segmentierung und ersetzte es weitgehend für die Implementierung des virtuellen Speichers in modernen Betriebssystemen wie Linux, da es einfacher ist, die Speicherblöcke mit fester Größe von Seiten anstelle von Segmenten variabler Länge zu verwalten.

Hardware-Implementierung

Wie die Segmentierung im geschützten Modus (bei der das Ändern eines Segmentregisters eine Last von GDT oder LDT auslöst) verwendet die Paging-Hardware Datenstrukturen im Speicher, um ihre Arbeit zu erledigen (Seitentabellen, Seitenverzeichnisse usw.).

Das Format dieser Datenstrukturen wird von der Hardware festgelegt . Es ist jedoch Sache des Betriebssystems, diese Datenstrukturen im RAM korrekt einzurichten und zu verwalten und der Hardware mitzuteilen, wo sie zu finden sind (via cr3).

Einige andere Architekturen überlassen das Paging fast vollständig der Software, sodass ein TLB-Fehler eine vom Betriebssystem bereitgestellte Funktion ausführt, um die Seitentabellen zu durchsuchen und die neue Zuordnung in den TLB einzufügen. Dadurch müssen die Seitentabellenformate vom Betriebssystem ausgewählt werden, es ist jedoch unwahrscheinlich, dass die Hardware Seitenläufe mit der Ausführung anderer Anweisungen in nicht ordnungsgemäßer Reihenfolge überlappen kann, wie dies bei x86 möglich ist .

Beispiel: vereinfachtes einstufiges Paging-Schema

Dies ist ein Beispiel dafür, wie Paging auf einer vereinfachten Version der x86-Architektur ausgeführt wird, um einen virtuellen Speicherbereich zu implementieren.

Seitentabellen

Das Betriebssystem könnte ihnen die folgenden Seitentabellen geben:

Seitentabelle, die vom Betriebssystem an Prozess 1 übergeben wurde:

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

Seitentabelle, die vom Betriebssystem an Prozess 2 übergeben wurde:

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

Wo:

PT1und PT2: Anfangsposition von Tabelle 1 und 2 im RAM.

Beispielwerte: 0x00000000, 0x12345678usw.

Es ist das Betriebssystem, das diese Werte entscheidet.
L: Länge eines Seitentabelleneintrags.
present: Zeigt an, dass die Seite im Speicher vorhanden ist.

Seitentabellen befinden sich im RAM. Sie könnten zum Beispiel wie folgt lokalisiert sein:

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


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


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

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

Die anfänglichen Speicherorte im RAM für beide Seitentabellen sind beliebig und werden vom Betriebssystem gesteuert. Es ist Sache des Betriebssystems, sicherzustellen, dass sie sich nicht überschneiden!

Jeder Prozess kann keine Seitentabellen direkt berühren, obwohl er Anforderungen an das Betriebssystem stellen kann, die dazu führen, dass die Seitentabellen geändert werden, z. B. nach größeren Stapel- oder Heap-Segmenten.

Eine Seite ist ein Block von 4 KB (12 Bit), und da Adressen 32 Bit haben, sind nur 20 Bit (20 + 12 = 32, also 5 Zeichen in hexadezimaler Schreibweise) erforderlich, um jede Seite zu identifizieren. Dieser Wert wird von der Hardware festgelegt.

Seitentabelleneinträge

Eine Seitentabelle ist ... eine Tabelle mit Seitentabelleneinträgen!

Das genaue Format der Tabelleneinträge wird von der Hardware festgelegt .

In diesem vereinfachten Beispiel enthalten die Seitentabelleneinträge nur zwei Felder:

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

In diesem Beispiel hätten die Hardware-Designer wählen können L = 21.

Die meisten realen Seitentabelleneinträge haben andere Felder.

Es wäre unpraktisch, Dinge auf 21 Bit auszurichten, da der Speicher durch Bytes und nicht durch Bits adressierbar ist. Selbst wenn in diesem Fall nur 21 Bit benötigt werden, würden Hardware-Designer wahrscheinlich L = 32den Zugriff beschleunigen und nur die verbleibenden Bits für die spätere Verwendung reservieren. Der tatsächliche Wert für Lx86 beträgt 32 Bit.

Adressübersetzung im einstufigen Schema

Sobald die Seitentabellen vom Betriebssystem eingerichtet wurden, wird die Adressumsetzung zwischen linearen und physischen Adressen von der Hardware durchgeführt .

Wenn das Betriebssystem Prozess 1 aktivieren möchte, setzt cr3es PT1den Anfang der Tabelle für Prozess 1 auf.

Wenn Prozess 1 auf eine lineare Adresse zugreifen möchte 0x00000001, führt die Paging- Hardwareschaltung für das Betriebssystem automatisch die folgenden Schritte aus:

Teilen Sie die lineare Adresse in zwei Teile:
```
| page (20 bits) | offset (12 bits) |
```
In diesem Fall hätten wir also:
- Seite = 0x00000
- Offset = 0x001
Schauen Sie in die Seitentabelle 1, weil sie darauf cr3verweist.
Eintrag suchen, 0x00000da dies der Seitenteil ist.

Die Hardware weiß, dass sich dieser Eintrag an der RAM-Adresse befindet PT1 + 0 * L = PT1.
da es vorhanden ist, ist der Zugriff gültig
von der Seitentabelle, die Lage der Seitenzahl 0x00000ist 0x00001 * 4K = 0x00001000.
Um die endgültige physikalische Adresse zu finden, müssen wir nur den Offset hinzufügen:
```
  00001 000
+ 00000 001
  -----------
  00001 001
```
denn 00001ist die physikalische Adresse der Seite in der Tabelle nachgeschlagen und 001ist der Versatz.

Wie der Name schon sagt, wird dem Offset immer einfach die physische Adresse der Seite hinzugefügt.
Die Hardware erhält dann den Speicher an diesem physischen Ort.

Auf die gleiche Weise würden die folgenden Übersetzungen für Prozess 1 erfolgen:

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

Wenn Sie beispielsweise auf die Adresse zugreifen 00001000, 00001weiß die Hardware, dass sich der Seitentabelleneintrag an der RAM-Adresse befindet: PT1 + 1 * L( 1aufgrund des Seitenteils), und dort wird danach gesucht.

Wenn das Betriebssystem zu Prozess 2 wechseln möchte, muss es nur cr3auf Seite 2 verweisen. So einfach ist das!

Nun würden die folgenden Übersetzungen für Prozess 2 passieren:

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

Dieselbe lineare Adresse wird für verschiedene Prozesse in unterschiedliche physikalische Adressen übersetzt , abhängig nur vom Wert im Inneren cr3.

Auf diese Weise kann jedes Programm erwarten, dass seine Daten beginnen 0und enden FFFFFFFF, ohne sich um genaue physikalische Adressen kümmern zu müssen.

Seitenfehler

Was passiert, wenn Prozess 1 versucht, auf eine Adresse innerhalb einer Seite zuzugreifen, die nicht vorhanden ist?

Die Hardware benachrichtigt die Software über eine Seitenfehlerausnahme.

In der Regel muss dann das Betriebssystem einen Ausnahmebehandler registrieren, um zu entscheiden, was zu tun ist.

Es ist möglich, dass der Zugriff auf eine Seite, die sich nicht in der Tabelle befindet, ein Programmierfehler ist:

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

Es kann jedoch Fälle geben, in denen dies akzeptabel ist, z. B. unter Linux, wenn:

Das Programm möchte seinen Stack erhöhen.

Es wird lediglich versucht, auf ein bestimmtes Byte in einem bestimmten möglichen Bereich zuzugreifen. Wenn das Betriebssystem zufrieden ist, wird diese Seite dem Prozessadressraum hinzugefügt.
Die Seite wurde auf die Festplatte ausgetauscht.

Das Betriebssystem muss einige Arbeiten hinter den Prozessen ausführen, um die Seite wieder in den RAM zu bringen.

Das Betriebssystem kann anhand des Inhalts des restlichen Seitentabelleneintrags feststellen, dass dies der Fall ist, da die anderen Einträge des Seitentabelleneintrags dem Betriebssystem vollständig überlassen bleiben, was es möchte.

Unter Linux zum Beispiel, wenn vorhanden = 0:
- Wenn alle Felder des Seitentabelleneintrags 0 sind, ist die Adresse ungültig.
- Andernfalls wurde die Seite auf die Festplatte ausgetauscht, und die tatsächlichen Werte dieser Felder codieren die Position der Seite auf der Festplatte.

In jedem Fall muss das Betriebssystem wissen, welche Adresse den Seitenfehler generiert hat, um das Problem beheben zu können. Aus diesem Grund setzen die netten IA32-Entwickler den Wert cr2auf diese Adresse, wenn ein Seitenfehler auftritt. Der Ausnahmebehandler kann dann einfach nachsehen cr2, um die Adresse zu erhalten.

Vereinfachungen

Vereinfachungen der Realität, die das Verständnis dieses Beispiels erleichtern:

Alle realen Paging-Schaltkreise verwenden mehrstufiges Paging, um Platz zu sparen. Dies zeigte jedoch ein einfaches einstufiges Schema.
Seitentabellen enthielten nur zwei Felder: eine 20-Bit-Adresse und ein 1-Bit-Present-Flag.

Reale Seitentabellen enthalten insgesamt 12 Felder und daher andere Funktionen, die weggelassen wurden.

Beispiel: Mehrstufiges Paging-Schema

Das Problem bei einem einstufigen Paging-Schema besteht darin, dass es zu viel RAM beanspruchen würde: 4G / 4K = 1M Einträge pro Prozess. Wenn jeder Eintrag 4 Byte lang ist, würde dies 4 MB pro Prozess ergeben , was selbst für einen Desktop-Computer zu viel ist: ps -A | wc -lsagt, dass ich gerade 244 Prozesse ausführe, was ungefähr 1 GB RAM beanspruchen würde!

Aus diesem Grund haben sich x86-Entwickler für ein mehrstufiges Schema entschieden, das die RAM-Nutzung reduziert.

Der Nachteil dieses Systems ist, dass es eine etwas höhere Zugriffszeit hat.

In dem einfachen 3-Ebenen-Paging-Schema, das für 32-Bit-Prozessoren ohne PAE verwendet wird, sind die 32 Adressbits wie folgt unterteilt:

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

Jedem Prozess muss ein und nur ein Seitenverzeichnis zugeordnet sein, sodass mindestens 2^10 = 1KSeitenverzeichniseinträge enthalten sind , was viel besser ist als die Mindestanzahl von 1 Million, die für ein einstufiges Schema erforderlich ist.

Seitentabellen werden nur nach Bedarf vom Betriebssystem zugewiesen. Jede Seitentabelle enthält 2^10 = 1KSeitenverzeichniseinträge

Seitenverzeichnisse enthalten ... Seitenverzeichniseinträge! Seitenverzeichniseinträge sind dieselben wie Seitentabelleneinträge, außer dass sie auf RAM-Adressen von Seitentabellen anstelle von physischen Adressen von Tabellen verweisen . Da diese Adressen nur 20 Bit breit sind, müssen sich Seitentabellen am Anfang von 4-KB-Seiten befinden.

cr3 zeigt jetzt auf den Speicherort im RAM des Seitenverzeichnisses des aktuellen Prozesses anstelle von Seitentabellen.

Seitentabelleneinträge ändern sich in einem einstufigen Schema überhaupt nicht.

Seitentabellen ändern sich von einem einstufigen Schema, weil:

Jeder Prozess kann bis zu 1 KB Seitentabellen enthalten, eine pro Seitenverzeichniseintrag.
Jede Seitentabelle enthält genau 1K-Einträge anstelle von 1M-Einträgen.

Der Grund für die Verwendung von 10 Bit auf den ersten beiden Ebenen (und beispielsweise nicht 12 | 8 | 12) besteht darin, dass jeder Seitentabelleneintrag 4 Byte lang ist. Dann passen die 2 ^ 10 Einträge von Seitenverzeichnissen und Seitentabellen gut in 4-KB-Seiten. Dies bedeutet, dass das Zuweisen und Freigeben von Seiten für diesen Zweck schneller und einfacher ist.

Adressübersetzung im mehrstufigen Schema

Seitenverzeichnis, das vom Betriebssystem an Prozess 1 übergeben wurde:

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

Seitentabellen, die vom Betriebssystem für Prozess 1 unter PT1 = 0x10000000( 0x10000* 4K) angegeben wurden:

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

Seitentabellen, die vom Betriebssystem für Prozess 1 unter PT2 = 0x80000000( 0x80000* 4K) angegeben wurden:

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

wo:

PD1: Anfangsposition des Seitenverzeichnisses von Prozess 1 im RAM.
PT1und PT2: Anfangsposition von Seitentabelle 1 und Seitentabelle 2 für Prozess 1 im RAM.

In diesem Beispiel könnten das Seitenverzeichnis und die Seitentabelle im RAM wie folgt gespeichert werden:

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


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

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


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

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

Lassen Sie uns die lineare Adresse 0x00801004Schritt für Schritt übersetzen.

Wir nehmen an cr3 = PD1, dass es auf das gerade beschriebene Seitenverzeichnis verweist.

In binär ist die lineare Adresse:

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

Gruppierung wie 10 | 10 | 12folgt:

0000000010 0000000001 000000000100
0x2        0x1        0x4

was gibt:

Seitenverzeichniseintrag = 0x2
Seitentabelleneintrag = 0x1
Offset = 0x4

Die Hardware sucht also nach Eintrag 2 des Seitenverzeichnisses.

Die Seitenverzeichnis-Tabelle gibt an, dass sich die Seitentabelle unter befindet 0x80000 * 4K = 0x80000000. Dies ist der erste RAM-Zugriff des Prozesses.

Da es sich bei dem Seitentabelleneintrag um handelt 0x1, prüft die Hardware den Eintrag 1 der Seitentabelle unter 0x80000000, der angibt, dass sich die physische Seite unter der Adresse befindet 0x0000C * 4K = 0x0000C000. Dies ist der zweite RAM-Zugriff des Prozesses.

Schließlich fügt die Paging-Hardware den Offset hinzu, und die endgültige Adresse lautet 0x0000C004.

Andere Beispiele für übersetzte Adressen sind:

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

Seitenfehler treten auf, wenn entweder ein Seitenverzeichniseintrag oder ein Seitentabelleneintrag nicht vorhanden ist.

Wenn das Betriebssystem einen anderen Prozess gleichzeitig ausführen möchte, gibt es dem zweiten Prozess ein separates Seitenverzeichnis und verknüpft dieses Verzeichnis mit separaten Seitentabellen.

64-Bit-Architekturen

64 Bit sind immer noch zu viel Adresse für aktuelle RAM-Größen, sodass die meisten Architekturen weniger Bit verwenden.

x86_64 verwendet 48 Bit (256 TiB), und die PAE des Legacy-Modus erlaubt bereits 52-Bit-Adressen (4 PiB).

12 dieser 48 Bits sind bereits für den Offset reserviert, wodurch 36 Bits übrig bleiben.

Wenn ein 2-Ebenen-Ansatz gewählt wird, wäre die beste Aufteilung zwei 18-Bit-Ebenen.

Dies würde jedoch bedeuten, dass das Seitenverzeichnis 2^18 = 256KEinträge enthält, die zu viel RAM benötigen: in der Nähe eines einstufigen Paging für 32-Bit-Architekturen!

Daher erstellen 64-Bit-Architekturen noch weitere Seitenebenen, üblicherweise 3 oder 4.

x86_64 verwendet 4 Ebenen in einem 9 | 9 | 9 | 12Schema, sodass die obere Ebene nur 2^9Einträge höherer Ebene aufnimmt .

PAE

Physische Adresserweiterung.

Mit 32 Bit können nur 4 GB RAM adressiert werden.

Dies wurde zu einer Einschränkung für große Server, daher führte Intel den PAE-Mechanismus in Pentium Pro ein.

Um das Problem zu beheben, fügte Intel 4 neue Adressleitungen hinzu, sodass 64 GB adressiert werden konnten.

Die Seitentabellenstruktur wird auch geändert, wenn PAE aktiviert ist. Die genaue Art und Weise der Änderung hängt davon ab, ob die PSE ein- oder ausgeschaltet ist.

PAE wird über das PAEBit von ein- und ausgeschaltet cr4.

Selbst wenn der gesamte adressierbare Speicher 64 GB beträgt, können einzelne Prozesse nur bis zu 4 GB verwenden. Das Betriebssystem kann jedoch unterschiedliche Prozesse auf unterschiedliche 4-GB-Blöcke übertragen.

PSE

Seitengrößenerweiterung.

Ermöglicht Seiten mit einer Länge von 4 MB (oder 2 MB, wenn PAE aktiviert ist) anstelle von 4 KB.

PSE wird über das PAEBit von ein- und ausgeschaltet cr4.

PAE- und PSE-Seitentabellenschemata

Wenn entweder PAE oder PSE aktiv sind, werden verschiedene Paging-Level-Schemata verwendet:

keine PAE und keine PSE: 10 | 10 | 12
keine PAE und PSE : 10 | 22.

22 ist der Versatz innerhalb der 4-MB-Seite, da 22-Bit-Adresse 4 MB ist.
PAE und keine PSE: 2 | 9 | 9 | 12

Der Entwurfsgrund, warum 9 zweimal anstelle von 10 verwendet wird, besteht darin, dass Einträge jetzt nicht mehr in 32 Bits passen, die alle mit 20 Adressbits und 12 aussagekräftigen oder reservierten Flag-Bits gefüllt waren.

Der Grund dafür ist, dass 20 Bit nicht mehr ausreichen, um die Adresse von Seitentabellen darzustellen: 24 Bit werden jetzt benötigt, da dem Prozessor 4 zusätzliche Drähte hinzugefügt wurden.

Aus diesem Grund haben die Designer beschlossen, die Eintragsgröße auf 64 Bit zu erhöhen. Um sie in eine einzelne Seitentabelle einzufügen, muss die Anzahl der Einträge auf 2 ^ 9 anstatt auf 2 ^ 10 reduziert werden.

Die Start-2 ist eine neue Seitenebene namens Page Directory Pointer Table (PDPT), da sie auf Seitenverzeichnisse verweist und die lineare 32-Bit-Adresse ausfüllt. PDPTs sind ebenfalls 64 Bit breit.

cr3zeigt jetzt auf PDPTs, die sich auf den ersten vier 4 GB Speicher befinden und auf 32-Bit-Vielfachen ausgerichtet sein müssen, um die Adressierungseffizienz zu gewährleisten. Dies bedeutet, dass jetzt cr327 signifikante Bits anstelle von 20: 2 ^ 5 für die 32 Vielfachen * 2 ^ 27 vorhanden sind, um die 2 ^ 32 der ersten 4 GB zu vervollständigen.
PAE und PSE: 2 | 9 | 21

Die Designer haben beschlossen, ein 9 Bit breites Feld beizubehalten, damit es auf eine einzelne Seite passt.

Dies lässt 23 Bits übrig. Wenn Sie 2 für die PDPT belassen, um die Dinge mit dem PAE-Fall ohne PSE einheitlich zu halten, bleibt 21 für den Versatz übrig, was bedeutet, dass die Seiten 2M breit sind anstatt 4M.

TLB

Der Translation Lookahead Buffer (TLB) ist ein Cache für Paging-Adressen.

Da es sich um einen Cache handelt, werden viele Entwurfsprobleme des CPU-Cache gemeinsam genutzt, z. B. die Assoziativitätsstufe.

In diesem Abschnitt wird ein vereinfachter, vollständig assoziativer TLB mit 4 einzelnen Adresseinträgen beschrieben. Beachten Sie, dass echte TLBs wie andere Caches normalerweise nicht vollständig assoziativ sind.

Grundbetrieb

Nachdem eine Übersetzung zwischen linearer und physikalischer Adresse erfolgt ist, wird diese im TLB gespeichert. Ein TLB mit 4 Einträgen startet beispielsweise im folgenden Status:

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

Das >gibt den aktuellen Eintrag an, der ersetzt werden soll.

und nachdem eine lineare Seitenadresse 00003in eine physikalische Adresse übersetzt wurde 00005, wird der TLB:

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

und nach einer zweiten Übersetzung des 00007auf 00009sie zu:

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

Wenn 00003nun erneut übersetzt werden muss, sucht die Hardware zuerst den TLB und ermittelt seine Adresse mit einem einzigen RAM-Zugriff 00003 --> 00005.

Ist natürlich 00000nicht im TLB, da kein gültiger Eintrag 00000als Schlüssel enthält .

Ersatzrichtlinie

Wenn der TLB voll ist, werden ältere Adressen überschrieben. Genau wie beim CPU-Cache ist die Ersetzungsrichtlinie eine potenziell komplexe Operation, aber eine einfache und vernünftige Heuristik besteht darin, den zuletzt verwendeten Eintrag (LRU) zu entfernen.

Mit LRU ausgehend vom Status:

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

Hinzufügen 0000D -> 0000Awürde geben:

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

NOCKEN

Die Verwendung des TLB beschleunigt die Übersetzung, da für die anfängliche Übersetzung ein Zugriff pro TLB-Ebene erforderlich ist. Dies bedeutet 2 bei einem einfachen 32-Bit-Schema, 3 oder 4 bei 64-Bit-Architekturen.

Der TLB wird normalerweise als teurer RAM-Typ implementiert, der als Content-Addressable Memory (CAM) bezeichnet wird. CAM implementiert eine assoziative Zuordnung auf Hardware, dh eine Struktur, die mit einem Schlüssel (lineare Adresse) einen Wert abruft.

Zuordnungen könnten auch für RAM-Adressen implementiert werden, aber für CAM-Zuordnungen sind möglicherweise viel weniger Einträge erforderlich als für eine RAM-Zuordnung.

Zum Beispiel eine Karte, in der:

Sowohl Schlüssel als auch Werte haben 20 Bit (der Fall eines einfachen Paging-Schemas).
Es müssen jeweils höchstens 4 Werte gespeichert werden

könnte in einem TLB mit 4 Einträgen gespeichert werden:

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

Um dies jedoch mit RAM zu implementieren, müssten 2 ^ 20 Adressen vorhanden sein :

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

Das wäre sogar noch teurer als die Verwendung eines TLB.

Einträge ungültig machen

Bei cr3Änderungen werden alle TLB-Einträge ungültig, da eine neue Seitentabelle für einen neuen Prozess verwendet wird. Daher ist es unwahrscheinlich, dass einer der alten Einträge eine Bedeutung hat.

Der x86 bietet auch die invlpgAnweisung, die einen einzelnen TLB-Eintrag explizit ungültig macht. Andere Architekturen bieten noch mehr Anweisungen für ungültig gemachte TLB-Einträge, z. B. die Ungültigmachung aller Einträge in einem bestimmten Bereich.

Einige x86-CPUs gehen über die Anforderungen der x86-Spezifikation hinaus und bieten mehr Kohärenz als garantiert, zwischen dem Ändern eines Seitentabelleneintrags und seiner Verwendung, wenn er nicht bereits im TLB zwischengespeichert wurde . Anscheinend hat sich Windows 9x aus Gründen der Korrektheit darauf verlassen, aber moderne AMD-CPUs bieten keine kohärenten Seitengänge. Intel-CPUs tun dies, obwohl sie dafür falsche Spekulationen erkennen müssen. Dies auszunutzen ist wahrscheinlich eine schlechte Idee, da es wahrscheinlich nicht viel zu gewinnen gibt und ein großes Risiko besteht, subtile zeitkritische Probleme zu verursachen, die schwer zu debuggen sind.

Verwendung des Linux-Kernels

Der Linux-Kernel nutzt die Paging-Funktionen von x86 in großem Umfang, um schnelle Prozesswechsel mit geringer Datenfragmentierung zu ermöglichen.

In v4.2, Blick unter arch/x86/:

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

Es scheinen keine Strukturen definiert zu sein, die die Seiten darstellen, nur Makros: include/asm/page_types.hist besonders interessant. Auszug:

#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.hdefiniert CR0und insbesondere die PGBitposition:

#define X86_CR0_PG_BIT      31 /* Paging */

Literaturverzeichnis

Frei:

rutgers-pxk-416 Kapitel "Speicherverwaltung: Vorlesungsunterlagen"

Gute historische Übersicht über Speicherorganisationstechniken, die von älteren Betriebssystemen verwendet werden.

Nicht frei:

bovet05 Kapitel "Speicheradressierung"

Angemessene Einführung in die x86-Speicheradressierung. Es fehlen einige gute und einfache Beispiele.

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

Tolle Antwort, aber ich bin mir immer noch nicht sicher, wie LRU entschieden wird. Das Aufrufen des Betriebssystems bei jedem Zugriff auf eine andere Seite als MRU erscheint teuer. Alternativ konnte ich sehen, wie die Hardware die Seitentabelle für LRU neu ordnete, was für gleichzeitige Programme gefährlich sein kann. Ist einer von diesen richtig? Woher weiß das Betriebssystem, welche Seite die LRU ist, wenn ein Seitenfehler auftritt?

Keynan

@Keynan Ich denke, es ist die Hardware, die das macht, also ist die benötigte Zeit kein Problem. Was die Parallelität betrifft, weiß ich nicht, wie sie verwaltet wird. Ich denke, es gibt einen CR3 und einen Cache pro Prozessor, und das Betriebssystem muss nur sicherstellen, dass sich die Speicherseiten nicht überlappen.

Ciro Santilli 法轮功冠状病六四事件 19

real TLBs are not usually fully associative… The TLB is usually implemented as … CAMSind diese beiden Aussagen nicht widersprüchlich?

a3f

>>> x86_64 verwendet 4 Ebenen in einer 9 | 9 | 9 | 12 Schema sollte es 9 | sein 9 | 9 | 9 | 12？

monklof

@monklof Ich denke, das ist richtig: 9 9 9 12 erlaubt bereits 512 GB RAM. Das 5-Level-Schema ist eine neuere Entwicklung, die sich nur an Server richtet. Dies wird in der Antwort auf meiner Website erwähnt, die aktueller ist.

Ciro Santilli 法轮功冠状病六四事件 17