Thema: meine Paging-Ideen

[erik.vikinger]

Hallo,


da ich darum gebeten wurde (und heute etwas Langeweile hatte) schreibe ich hier mal etwas über die Art und Weise wie ich auf meiner Plattform Paging realisieren und benutzen möchte:

Die nötigen Descriptoren findet man da http://www.megaupload.com/?d=IASLIBGX (Stand 2011-07-31).
Die Paging-Directory-Ebenen hab ich von "Root" angefangen mit L0 bis L? durchnummeriert. Paging-Directory-Tables sind immer genau eine Page groß und müssen auch entsprechend ausgerichtet sein.

Paging möchte ich vor allem für 2 Dinge benutzen: einmal um die Segmente im Hintergrund defragmentieren zu können (ohne Paging geht das zwar auch aber ich müsste dafür das ganze System einfrieren und das wäre insbesondere bei großen Segmenten eher doof) und dann noch zum Swappen (das hat bei mir zwar erst mal keine hohe Priorität aber es muss trotzdem von der Plattform angemessen unterstützt werden und Swappen in ganzen Segmenten ist auch eher doof). Paging ist für meine Plattform also nicht unbedingt zwangsweise nötig aber es macht das Leben an ein paar Stellen doch etwas leichter so das ich es dann doch als integralen Bestandteil meiner Plattform betrachte. Ich versuche von Segmentierung und Paging jeweils die Vorteile zu übernehmen aber ohne mir die Nachteile mit aufzuhalsen (zumindest nicht in vollem Umfang).

Ich möchte meine Plattform in 2 Ausführungen bauen: als 32Bit-System und als 64Bit-System. Beides wird aus dem selben VHDL-Code generiert nur eben mit unterschiedlichen Parametern. Auch der OS-Kernel wird aus dem selben Source kompiliert nur eben mit unterschiedlichen Compiler-Parametern. Daher wird es auch das Paging in verschiedenen Ausführungen geben, darüber hinaus möchte ich mir für die 64Bit-Variante auch die Option offen halten dort verschiedene Paging-Varianten zu implementieren. In der Descriptor-Beschreibung sieht man für die 64Bit-Plattform auch 2 verschiedene Varianten, einmal mit 512kB als kleinste Page-Größe und einem 3-stufigem Paging und zum anderen mit 64kB als kleinste Page-Größe und einem 4-stufigem Paging. In den 64Bit-Varianten sind die Page-Descriptoren jeweils 128Bit groß so das der Page-Table-Index immer um 4 Bit kleiner ist als das Page-Offset: 15-15-15-19 oder 12-12-12-12-16. Das sind die 2 besten Varianten die exakt aufgehen und den vollen 64Bit-Adressraum anbieten können. Sollten die 64kB-Pages immer noch zu groß/grob sein kann ich auch noch ein 10-10-10-10-10-14 Paging mit 16kB-Pages und 5 Stufen machen aber ich denke das wird sich langfristig kaum lohnen. Das Paging auf x86-64 kann nur einen 48Bit-Adressraum anbieten (9-9-9-9-12), da ist das aber auch Okay weil das ja immer nur den virtuellen Adressraum eines einzelnen Prozesses betrifft da bei Flat-Memory ja jeder Prozess seinen eigenen virtuellen Adressraum hat. Auf meiner Plattform gibt es immer insgesamt nur einen virtuellen Adressraum da es systemweit nur ein einziges Paging-Directory geben kann, mein CR3-Äquivalent gilt also nicht nur für eine CPU sondern immer für das gesamte System, inklusive Chipsatz da auch dieser auf das Paging-Directory zugreift, so das es im globalen Bereich der Control-Register liegt.

In allen Segment-Descriptoren ist an Bit 7 ein PE-Bit (Paging-Enable) womit man die Benutzung von Paging pro Segment individuell anschalten kann. Daraus ergibt sich das es auf meiner Plattform quasi 2 unabhängige lineare Adressräume gibt. Einmal ohne Paging wo die lineare Adresse immer 1:1 eine physische Adresse ist und zum anderen mit Paging wo die lineare Addresse auf eine beliebige physische Adresse gemappt werden kann. Das Paging als solches wird immer aktiv sein und es wird auch immer ein halbwegs vollständiges Paging-Directory geben in dem aber alle Einträge auch auf 1:1-Mapping stehen (zumindest in den Bereichen wo auch echter physischer RAM vorhanden ist), nur wird es die meiste Zeit über komplett ignoriert werden. Selbst wenn das Paging von einzelnen Segmenten benutzt wird so trifft die Bremswirkung des Paging auch nur diese Segmente und nicht das gesamte System.


Das Paging für 32Bit sieht ziemlich gewohnt aus (10-10-12 mit 4kB als kleinste Page-Größe) und ist auch im wesentlichen von x86 abgeschaut. Der offensichtlichste Unterschied sind die Flags im Descriptor. Es gibt keine Access-Control-Flags u.ä. da das ja schon von den Segmenten erledigt wird, dafür einen richtigen Typ-Eintrag (der auch stimmen muss sonst gibt es eine Paging-Exception beim Zugriff) und ansonsten nur einen Eintrag für die Page-Größe. Das mit der Page-Größe hab ich mir von ARM abgeschaut und funktioniert ganz einfach: wenn dort drin 0b0010 steht dann bedeutet dass das die Page nicht 4kB sondern 16kB groß ist (der Wert gibt an wie viele Bits von der physischen Page-Adresse ignoriert werden sollen) und das 4 gleiche Einträge hintereinander in der L1-Table liegen müssen (an 16kB ausgerichtet) so das unabhängig davon mit welcher linearen Adresse der Page-Table-Walk sucht (der geht ja erst einmal von einer 4kB-Page aus) immer das korrekte Mapping gefunden wird. Im TLB landet dann ein 16kB-Mapping-Eintrag der nur die Bits 31..14 der physischen Adresse enthält (Bit 13 und 12 vom Descriptor werden ignoriert). Wie viele verschiedene Page-Größen ich unterstützen möchte habe ich noch nicht wirklich entschieden aber jede Zweierpotenz ist wohl doch etwas übertrieben (wenn auch theoretisch möglich). Das Problem ist das umso mehr Page-Größen möglich sind auch der TLB-LookUp aufwendiger wird und das im Endeffekt nur noch zusätzliche Performance kostet anstatt was zu bringen. Der gleiche Mechanismus ist auch bei den Einträgen in der L0-Directory-Table vorgesehen aber ob Pages mit mehr als 4MB auf einer 32Bit-Plattform überhaupt Sinn machen würde ich dann doch bezweifeln, vor allem da Paging ja eh nur die Ausnahme sein soll. Wahrscheinlich werde ich wohl nur 4kB, 16kB und 64kB, zuzüglich 4MB damit ich auch mal eine Ebene sparen kann, unterstützen. Auch sind in den Einträgen keine Statistik-Flags wie Accessed und Modified drin, da ich auf der 32Bit-Version eh nicht vor habe zu swappen (es wird immer genug physischer RAM vorhanden sein) hab ich das dort einfach komplett gelassen.

Das Paging für 64Bit ist schon deutlich komplexer und man sieht auch sofort das die Einträge die doppelte Größe als üblich haben. Der zusätzliche Platz wird für einige interessante Features genutzt. Das erste neue Feature ist "Guarded Pages" (wird da erklärt http://www.technovelty.org/code/guarded-page-table.html und dort noch eine Umsetzung für Alpha os.inf.tu-dresden.de/~schoenbg/papers/gpt.pdf). Das wird gerne bei CPUs benutzt die keinen Page-Walk in Hardware haben sondern wo das die SW erledigen muss (das trifft nicht nur auf viele kleine CPUs wie AVR32, MIPS und die meisten Soft-CPUs zu sondern auch auf viele große CPUs wie Alpha, Sparc und PA-RISC, selbst der Itanium unterstützt software-based Paging optional). Damit kann man den Page-Table-Baum in vielen Fällen um einiges verkleinern und spart sich auch gleich ein paar Speicherzugriffe ein. Falls ich das tatsächlich hinbekomme wäre ich meines Wissens nach der Erste der das in HW realisiert, auch wenn ich davon erst mal nur eine Light-Version realisieren möchte in der nur Directory-Ebenen übersprungen werden können (ich hab das fürs erste nicht für Leaf-Nodes vorgesehen). Das zweite wesentliche Feature sind die Access-Observer-Bytes in den Descriptoren. Das ist mein Äquivalent zu den Accessed/Modified-Bits aus x86. Der entscheidende Punkt ist das es Bytes sind die mit einem simplen Schreibzugriff, im Gegensatz zu einem Read-Modify-Write-Zugriff bei einzelnen Bits, aktualisiert werden können. Dadurch ergeben sich auch weitere Vorteile bei der Statistik, anhand der Werte in diesen Bytes kann man ungefähr ablesen wie lange der letzte entsprechende Zugriff zurück liegt so das man fürs Auslagern eine gute Wahl treffen kann. Gute Page-Ersetzungsstrategien sind keine triviale Angelegenheit (was einem ein Blick in den Source-Code von OSen die sowas haben schnell verdeutlicht) und kosten auch immer etwas an CPU-Leistung. An dieser Stelle möchte ich auch die Unterstützung der Hardware in Anspruch nehmen. Wenn ich eh ein festes PTE-Layout benutzen will dann kann das auch im Chipsatz benutzt werden damit dort eine kleine Komponente in regelmäßigen Abständen den kompletten Page-Directory-Baum durchtraversiert und alle Access-Observer-Bytes in den gültigen Einträgen dekrementiert, dazu nutzt der Chipsatz semaphorische Speicherzugriffe damit ein paralleles Rücksetzen (auf 0xFF) durch eine CPU immer Vorrang hat. Dieses komplette Durchtraversieren kann in regelmäßigen Abständen passieren und kostet natürlich auch ein klein wenig Speicherbandbreite aber zumindest keine CPU-Zeit. Dafür kann der Chipsatz beim traversieren auch eine interne Liste mitpflegen in der die Pages mit den kleinsten Werten in den Access-Observer-Bytes geloggt werden und wenn dann doch mal geswappt werden muss braucht der Kernel einfach nur dort nachsehen und hat sofort einen guten Kandidaten fürs Auslagern. Auch in der 64Bit-Version des Paging möchte ich fexible Page-Größen unterstützen aber auch hier gilt das ich da einen ausgewogenen Kompromiss aus Flexibilität und Hardware-Aufwand (gerade der zusätzliche Zeitaufwand beim TLB-LookUp ist da relevant, wenn das nicht in einem einzelnen Takt passieren kann wäre das echt problematisch) finden muss, also diese Entscheidung wird wohl erst dann endgültig getroffen wenn ich soweit bin und das Synthese-Tool mir sagt was für diese Komponente der maximale Takt ist.

Der Chipsatz soll auf der 32Bit-Plattform und auf der 64Bit-Plattform bei der Verwaltung des Paging-Baums helfend mitarbeiten. Das betrifft auch das Defragmentieren wo der Chipsatz nur eine lineare Adresse mit der Quelle und die physische Adresse des Ziels und die Größe bekommt und dann selbstständig Page für Page umkopiert und immer die PTEs passend mitändert.


Wenn ein Segment vergrößert werden soll aber dahinter etwas anderes im Weg ist dann wird zuerst ein neuer zusammenhängender Platz im linearen (physischen) Adressraum gesucht und dieser Alloziert, danach wird im zugehörigen gepagten Adressraum für den bereits vorhandenen Segment-Bereich ein Mapping auf den alten Speicher eingerichtet (der neue Rest des Segments zeigt bereits auf den neuen Speicher), danach wird die Segment-Basis auf den neuen linearen (noch virtuellen) Speicher umgestellt und gleichzeitig das PE-Bit gesetzt und das Limit passend vergrößert, dann muss nur noch an alle CPUs ein Segment-Shadow-Renew-Kommando für den betreffenden Selector gesendet werden und schon arbeiten alle CPUs mit dem selben Segment aber an einer anderen linearen Adresse und das ohne das die SW das merken würde. Der einzigste Unterschied ist dass das Segment jetzt etwas langsamer ist weil ja nun Paging benutzt wird, durch dieses Paging zeigt der alte Bereich noch auf den alten physischen Speicher und der neue Bereich schon auf den neuen physischen Speicher (1:1). Nun muss nur noch im Hintergrund Page für Page des alten Bereichs umkopiert werden (so das am Schluss alle Pages 1:1 gemappt sind) und wenn das erledigt ist kann das PE-Bit wieder gelöscht und der alte lineare Speicherbereich freigegeben werden (anschließend noch ein Segment-Shadow-Renew-Kommando und schon arbeiten alle CPUs auch in diesem Segment wieder mit voller Performance).

Ein Segment das teilweise Ausgelagert ist liegt nicht mehr in dem linearen Speicherbereich der physischem RAM enthält sondern in einem zusätzlichen Bereich in dem dann immer Paging benutzt werden muss. Es soll auf meiner Plattform auch möglich sein Segmente zu erstellen und zu benutzen die größer sind als überhaupt physischer RAM vorhanden ist (nur die Summe aller Segmentgrößen darf nicht die Summe aus RAM und Swapp-Space übersteigen). Das Mapping für so ein Segment zeigt dann teilweise auf physischen RAM und teilweise nicht (da wird dann einfach der Descriptor-Typ auf einen ungültigen Wert gesetzt und der restliche Inhalt kennzeichnet dann den Ort im Swapp-Space). Im physischen RAM liegen dann etliche Segmente jeweils noch am Stück (für die auch kein Paging benutzt wird) und dazwischen unabhängige Pages von fragmentierten bzw. teilweise ausgelagerten Segmenten. Desto mehr geswappt werden muss desto mehr sieht der physische RAM dann so aus wie in einem klassischen Flat-Memory-Sytem und desto größer ist der Performanceverlust durch das Paging. Wenn das Swapping aber später nicht mehr benötigt wird (also die Summe aller Segmentgrößen kleiner als der physische RAM ist) kann der Kernel die Segmente einfach defragmentieren und sie alle wieder in den normalen linearen Adressraum holen um das Paging jeweils abzuschalten, so dass das System Stück für Stück wieder die volle Performance (ohne dem Paging) bekommt.


Ich hoffe dieser recht kurze Umriss meiner Paging-Ideen/Phantasien ist wenigstens ein wenig interessant.
Zumindest das Attribut "dumm" ist damit jetzt für mein Paging erledigt.


Grüße
Erik