Die Speicherverwaltung ist eine der zentralen Funktionen moderner Computerprozessoren und hat entscheidenden Einfluss auf die Leistung und Stabilität von Systemen. Seit der Einführung der 386er-Generation unterstützt die x86-Architektur das Paging, bei dem virtuelle Speicheradressen auf physische Speicherseiten abgebildet werden. Dieses Verfahren ermöglicht es Betriebssystemen, jedem Prozess einen separaten, zusammenhängenden virtuellen Adressraum bereitzustellen und gleichzeitig die Speicherbereiche verschiedener Prozesse voneinander zu isolieren. Um die Performance beim Zugriff auf Speicheradressen zu erhöhen, nutzt die CPU unter anderem Caches von Seitenzuordnungen, am bekanntesten darunter die Translation Lookaside Buffer, kurz TLBs. Die Beziehung zwischen diesen TLBs, den Pagetables im Hauptspeicher und der Kohärenz bei Speicherzugriffen ist komplex, aber grundlegend für das korrekte Funktionieren von modernen Computersystemen.
Beim Paging erfolgt die Abbildung von virtuellen zu physischen Adressen auf sogenannten Seitenebene. Standardmäßig beträgt die Größe einer Seite auf x86-Systemen 4 Kilobyte. Für eine 32-Bit-Adresse bedeutet dies, dass die oberen 20 Bits für die Seitenadresse verwendet werden, während die unteren 12 Bits den Offset innerhalb der Seite darstellen. Ohne Zwischenspeicherung müssten bei jedem Speicherzugriff mehrere Speicherzugriffe auf die Seitenstruktur erfolgen, was extrem ineffizient wäre. Hier kommt der TLB ins Spiel, der bereits übersetzte Seitenadressen speichert und so den teuren Zugriff auf den Hauptspeicher reduziert.
Läuft ein Zugriff ins Leere im TLB, führt die CPU einen sogenannten Pagewalk durch: Sie liest die Einträge der Seitenhierarchie im Speicher aus, um die aktuelle Übersetzung zu ermitteln.Die Architektur von x86 definiert dabei eindeutig, dass der TLB keine Kohärenz mit den Seitenstrukturen im Speicher besitzt. Das bedeutet, dass Änderungen an den Pagetable-Einträgen nicht automatisch die entsprechende TLB-Einträge aktualisieren oder entfernen. Dies macht es erforderlich, dass nach jeder Änderung des Page Tables der TLB ganz oder teilweise invalidiert wird. Unterbleibt die Invalidation, kann der Prozessor veraltete Einträge aus dem TLB verwenden, was zu inkonsistentem Verhalten und schwer nachvollziehbaren Fehlern führt.
Gleichzeitig erlauben moderne, aus-order-Prozessoren eine flexiblere Anordnung von Speicheroperationen, was die Performance steigert, aber zugleich die Kohärenzanforderungen komplexer macht.Interessanterweise stellen sich jedoch Fragen, ob und in welchem Umfang reale Prozessorimplementierungen tatsächlich streng diese Spezifikationen einhalten oder ob manche CPUs darüber hinausgehen und zusätzliche Kohärenzgarantien offerieren. Besonders spannend ist der Fall, wenn eine Page Table Entry verändert wird, die Änderung aber noch nicht im TLB vorhanden ist und somit die Adresse neu durch einen Pagewalk übersetzt werden muss. Wird dieser Zugriff sofort nach der Änderung ohne eine Invalidation durchgeführt, sieht der Pagewalk dann bereits die neue Tabelle oder kann er auch auf veraltete Daten zugreifen? Diese Fragestellung, in der Literatur als Pagewalk-Kohärenz bezeichnet, ist sowohl für Entwickler von Betriebssystemen als auch für Hardwareingenieure von großer Relevanz.Untersuchungen zeigen, dass in der Praxis verschiedene x86-Prozessoren unterschiedliche Ansätze zur Sicherstellung der Kohärenz wählen.
Während der TLB in sämtlichen getesteten CPUs nicht kohärent mit den Page Tables ist, existieren dennoch Prozessoren, die für den Pagewalk selbst Kohärenz garantieren. Dabei lassen sich drei Hauptkategorien unterscheiden: Systeme ohne Pagewalk-Kohärenz, solche mit nicht-spekulativen, kohärenten Pagewalks sowie Systeme mit spekulativ kohärenten Pagewalks, die Mechanismen zur Spekulationsdetektion besitzen und den Pagewalk bei Detektion einer Inkonsistenz zurücksetzen. Beispielsweise zeigen Intel Pentium Pro, Sandy Bridge und Haswell zusammen mit verschiedenen AMD K7 und Phenom Prozessoren eine spekulativ kohärente Seitewalk-Strategie, während AMD Bulldozer oder Zen 2 unter den getesteten CPUs keine solche Kohärenz besitzen. Interessanterweise verhält sich die VirtualBox-Virtualisierung mit Shadow Page Tables wie ein vollständig kohärenter TLB, allerdings zu sehr hohen Performancekosten.Um die Kohärenzmechanismen detailliert zu untersuchen, wurden auf Linux-Systemen spezielle Microbenchmarks entwickelt, die komplexe Operationen an den Page Tables ausführen und gleichzeitig sowohl die Zugriffszeiten als auch das Verhalten bei Pagewalks erfassen.
Dabei wurde ein eigener Kernelmodul verwendet, um auf den Control Register CR3 zuzugreifen, der die aktuell aktiven Page Tables beschreibt. Die Tests erlauben es, Einträge im Page Table direkt aus dem User-Space heraus massiv zu modifizieren, indem ein sogenanntes „Fast Page Table Update“ realisiert wird, das auf Mapping-Tricks basiert, um ohne Kernel-Kontextwechsel und Paging Deaktivierung Page Table Entries schnell zu verändern.Die Ergebnisse aus verschiedenen Testdesigns legen nahe, dass Pagewalk-Kohärenz essentiell für die Stabilität älterer Betriebssysteme ist, die keine korrekten TLB-Invalidationen nach Seitenänderungen ausführen. So wurde das Fehlen eines solchen Mechanismus als Ursache von zufälligen Abstürzen in Windows 95 bis Me Klima angenommen. Auch dafür bietet die Untersuchung der modernen CPUs wertvolle Einsichten: Einige neue Mikroarchitekturen erkennen Verstöße durch Vergleich von spekulativen Speicherzugriffen gegen bekannte, ältere Stores und setzen die korrekte Neuausführung entsprechend durch.
Darüber hinaus konnte durch Timing-Analysen differenziert werden, ob ein Pagewalk unmittelbar nach Änderung der Page Table ausgeführt wird, oder ob er spekulativ ausgeführt und bei Fehlern zurückgesetzt wird. Systeme mit spekulativen Pagewalks zeigen typischerweise eine Laufzeitstrafe, wenn Spekulationsfehler auftreten. Die Analyse ausgewählter Intel- und AMD-Prozessoren ergab eine Mixtur verschiedener Verhaltensweisen, die die Komplexität dieses Teilbereichs moderner CPU-Designs widerspiegeln.Ein weiterer spannender Aspekt ist die Rolle von Virtualisierungstechnologien. VirtualBox beispielsweise verwendet Shadow Page Tables und stellt eine vollständige Kohärenz sicher, indem alle Zugriffe auf die Gäste-Page Tables trappingbasiert überwacht werden.
Dies gewährleistet korrekte Sichtbarkeit von Änderungen, ist aber mit erheblichen Kosten bei jeder Page Table Update verbunden. Andere Ansätze, besonders solche mit Nested Paging, benötigen aber keine solch strikte Überwachung, sind dafür aber von der kohärenten Implementierung durch die Hardware abhängig.Ausgehend von diesen Erkenntnissen zeigt sich, dass die Koordination zwischen Hardware-Seitenübersetzung, TLB-Caching und Speicheroperationen eine Schlüsselrolle für die Systemleistung und Integrität spielt. Während TLBs als schnelle Caches unverzichtbar sind, führt ihre Nicht-Kohärenz mit den Page Tables zu komplexen Anforderungen an Software, die explizit TLB-Invalidierungen vornehmen muss. Die Hardware könnte durch erweiterte Kohärenzmechanismen Entlastung bieten, muss dabei jedoch mit den hohen Erwartungen an Out-of-Order-Ausführung und Speculation jonglieren.
