Aufgabe 4: Kontextwechsel

Unsere Hardware hat in OOStuBS eine Recheneinheit und Speicher, in MPStuBS haben wir zusätzlich maximal 7 weitere Recheneinheiten. Das wollen wir multiplexen, damit wir deutlich mehr Anwendungen als Kerne gleichzeitig laufen lassen können. Jede Anwendung soll also eine eigene illusionierte Hardware, mit virtueller CPU und Speicher, für sich haben.

Dazu müssen wir beides virtualisieren. Beim Speicher ist das einfach: Wir teilen ihn in Bereiche auf, jede Anwendung bekommt ein Stück davon. Allerdings funktioniert das bei der CPU so nicht, wir können nicht einfach irgendwie die Instruktionen aufspalten. Allerdings können wir die Ausführungszeit auf der CPU zwischen den Anwendungen aufteilen.

Aber wie kann man so eine Aufteilung umsetzen? Wir schauen uns das mal anhand zweier Funktionen an, die sich abwechseln sollen. Um es einfach zu halten, geben foo und bar jeweils in einer Schleife nur ihren Namen sowie eine herunterzählende Zahl aus.

Erster Versuch: Wir hängen einen Aufruf von bar ans Ende von foo, ein einseitiger Aufruf. Wir sehen, dass zuerst alle Ausgaben von foo getätigt werden, danach die Ausgaben von bar – welches am Ende aufgerufen wird. Wir haben also einen sequenziellen Stapelbetrieb, nicht die gewünschte gleichzeitige Ausführung.

Nächster Versuch: Die Zählervariablen bekommen einen festen Speicher zugewiesen und wir setzen den Aufruf der jeweils anderen Funktion in die Schleifen, und zwar bei beiden Funktionen – ein gegenseitiger Aufruf also. Wenn wir das laufen lassen, dann sieht die Ausgabe auch auf einen ersten Blick gut aus! Aber wenn wir die Aufrufhierarchie betrachten, sehen wir, das wir jedes Mal einen neuen Funktionsaufruf tätigen, und entsprechend den Stapel füllen – was in der Regel einen hohen Speicherverbrauch bedeutet, und wir Gefahr laufen einen Stapelüberlauf zu provozieren, insbesondere wenn wir eine Endlosrekursion haben.

Was wir statt dem Aufruf wollen, ist ein Umschalten, der Kontext von dem alten Faden muss gesichert und der neue geladen werden. Dabei bilden bei uns Stapelspeicherinhalt sowie die Register den Kontext. Außerdem brauchen wir eine Umschaltefunktion, bei uns heißt diese context_switch. Sie bekommt als ersten Parameter den Stackzeiger des aktuellen Fadens und wechselt dann zum neuen Faden.

Betrachten wir die Funktion erst einmal als Blackbox, ob sie denn unseren Anforderungen genügen würde: Wir erweitern unsere Anwendungen um den Aufruf, mit statischen Variablen stack_bar und stack_foo für die Parameter. Die Ausgabe entspricht wieder dem gewünschten Ergebnis. Und auch unter der Haube sieht es gut aus, wir wechseln zwischen den Anwendungen foo und bar hin und her, und zwar ohne das unser Speicherverbrauch stetig steigt – also genau das was wir erreichen wollen.

Aber was muss diese mystische Umschaltefunktion context_switch dafür nun tun? Zuerst müssen die Register des aktuellen Kontexts gesichert werden. Wir können nun dafür einen statischen Speicher nehmen, aber noch einfach ist: Wir pushen diese einfach der Reihe nach auf den Stack. Dann müssen wir uns lediglich den aktuellen Stapelzeiger merken. Vom neuen Kontext laden wir nun den Stapelzeiger, und stellen die dort irgendwann zuvor auf diesen Stapel gesicherten Register wieder hier.

Der Instruktionszeiger ist das Register rip, also wenn wir diesen dann wie die anderen Register wiederherstellen, können wir gleich wieder an der entsprechenden Stelle fortsetzen, oder? Nun, leider ist es nicht ganz so leicht, denn wir können nicht einfach eine Adresse in das Register rip schreiben, das erlaubt uns die x86 Architektur nicht. Stattdessen müssen wir einen kleinen Umweg nehmen, indem wir die gewünschte Adresse auf den Stack pushen, und dann die Instruktion ret ausführen. Diese popt vom Stack den aktuellen Eintrag und setzt das als Instruktionszeiger.

Der Kontextwechsel am Beispiel: Wir haben unsere Struktur Stackpointer, welche derzeit nur einen einzigen Zeiger – den Kernelstapelzeiger – beinhaltet. In Betriebssystemtechnik (BST) werden wir auch noch den Benutzerstapelzeiger speichern müssen, deshalb packen wir das schon einmal vorsorglich in eine Struktur. Wir haben für jede Anwendung – foo und bar – eine solche Struktur instanziiert. Und wir gehen auch davon aus, dass diese bereits sinnvoll initialisiert wurden, und wir also mitten im Betrieb drin sind, gerade in der Abarbeitung von foo, kurz vor dem Aufruf von context_switch, mit welchen wir zu bar wechseln wollen.

Wie wir von der Aufrufkonventionen bereits wissen, müssen vor einem Funktionsaufruf zuerst die flüchtigen Register gesichert werden – das generiert uns der Compiler bereits hin, hier entscheidet er beispielsweise, dass r8 gesichert werden muss, in dem es auf den Stack pushed wird. Beim Funktionsaufruf wird durch das call noch die Rücksprungadresse auf den Stack gepusht, für uns hier das symbolische Label LFOO, und dann der Instruktionszeiger auf den Beginn der Funktion context_switch gesetzt.

Da die relevanten flüchtigen Register ja bereits vor dem Aufruf gesichert wurden, müssen wir uns nun nur um alle nicht-flüchtigen Register kümmern, diese können nun ebenfalls auf den Stack gepusht werden. Den Stackpointer selbst auf den Stack zu legen ist natürlich nicht wirklich sinnvoll, stattdessen schreiben wir dessen aktuelle Adresse in stack_foo. Damit haben wir den Kontext von foo gesichert, nun beginnt das umgekehrte Spiel mit dem Kontext von bar: Wir setzen den Stackpointer rsp entsprechend der in stack_bar gespeicherten Adresse.

Der Stackpointer wird nun (hoffentlich) auf einen Speicher zeigen, auf dem irgendwann vorher der Kontext von bar gesichert wurde, also konkret auf die zuletzt gesicherten nicht-flüchtigen Register von bar. Diese stellen wir wieder her. Danach führen wir ein ret aus, welches vom Stack die Rücksprungadresse nimmt und den Instruktionszeiger entsprechend setzt – was direkt hinter dem Funktionsaufruf sein wird. Anschließend wird der vom Übersetzer generierte Code zur Wiederherstellung aller vor dem Aufruf gesicherten flüchtigen Register aufgerufen, hier zum Beispiel r10. Und die Ausführung von bar wird dort fortgesetzt, wo sie beim Aufruf von ihrem letzten context_switch pausiert wurde.

In dem Beispiel sind wir bis jetzt davon ausgegangen, das wir bereits mitten im Ablauf stecken. Wie mache ich das aber ganz zu Beginn, wenn ich bereits beim ersten Aufruf von context_switch einen validen Zielkontext brauche, in den ich Wechseln kann?

Ich muss dafür einen Stack händisch vorbereiten, in dem von context_switch benötigten Format, welcher dafür sorgt, dass in die Koroutine gesprungen wird – in unserem Beispiel startet diese mit der parameterlosen Funktion bar. Somit muss auf dem Stack auch die Startadresse dieser Funktion stehen, in welche dann mittels ret Instruktion gesprungen wird. Unser context_switch erwartet außerdem vorher auf dem Stack die gesicherten Einträge für die nicht-flüchtigen Register. Und der Stackzeiger muss dabei auf den letzten Registereintrag zeigen.

Aber ich hab ja eigentlich noch gar keinen Stack für diese Koroutine. Also nehm ich dafür einfach einen ausreichend großen Speicherbereich, und definiere das obere Ende als top-of-stack. In den Eintrag an der höchsten Adresse schreibe ich also den Funktionszeiger zu bar. Für die flüchtigen Register brauche ich nun Werte. Da am Anfang der Funktion keine Annahmen über die Inhalte dieser Register getroffen werden, kann ich irgendetwas reinschreiben – zum Beispiel 0. Die Variable für den Kernelstackzeiger von bar wird dann auf den Eintrag 56 Bytes unterhalb von unserem top-of-stack gesetzt, in dem auch der initiale Wert des letzten Registers steht. Nun kann context_switch ausgeführt werden – es wird, nachdem es zuvor von foo alle Register gesichert hat, die nicht-flüchtigen Register auf 0 setzen, und an den Anfang von bar springen. Wir haben den ersten Einsprung geschafft.

Allerdings müssen wir aufpassen: Sollte die Funktion bar nun selbst zurückkehren, also ein ret ausführen… dann wird der Inhalt, der über unserem top-of-stack steht genommen, als Adresse interpretiert und angesprungen. Und dort kann irgendetwas stehen, aber sicherlich nichts Vernünftiges. Ein Invalid Opcode oder General Protection Fault sind wahrscheinlich, aber es kann auch vorkommen, das es zufällig an irgendeiner anderen Stelle weiterläuft – alles nichts, was wir wollen.

Besser wir entwickeln eine defensive Lösung, welche uns in so einem Fall eine Fehlermeldung anzeigt, und das System anhält. Zum Beispiel über die Funktion context_panic, welche über die Funktion kernelpanic eben dies erreicht. Diese Adresse muss nun am Anfang des Stacks stehen, vor der Adresse der Funktion bar – dadurch würde nun ein ret in bar an den Beginn der Funktion context_panic springen und wie gewünscht das System anhalten. Wir sehen: Durch die Funktionsadresse auf dem Stack ist es eigentlich einfach in diese mittels ret Instruktion zu springen.

Was aber, wenn wir Funktionsparameter haben? So soll bar nun mit einem Integer Parameter i aufgerufen werden. Nach der System V ABI wird dieser in rdi – einem flüchtigen Register – erwartet. Dieser kann einen beliebigen Wert haben, je nachdem was foo vor dem context_switch dort reingeschrieben hat.

Wir setzen auf dem Stack nur die Werte für die nicht-flüchtigen Register. Natürlich könnten wir auch die flüchtigen Register in context_switch sichern, aber das wäre ein massiver Overhead bei jedem Kontextwechsel, keine akzeptable Lösung für uns. Aber brauchen wir auch nicht, wir können auch mit dem vorhanden Ablauf arbeiten, indem wir den Umweg über eine Hilfsfunktion gehen: Diese soll dabei lediglich aus einem nicht-flüchtigen Register, beispielsweise r15, den Wert lesen und nach rdi – dem Register für den ersten Parameter kopieren, und dann die eigentliche Funktion aufrufen. Und beim Vorbereiten des Stacks geben wir an der Speicherstelle, in der wir den initialen Wert für r15 schreiben eben den gewünschten Parameterwert an. Außerdem muss noch die Adresse durch die der Hilfsfunktion ausgetauscht werden. Die Hilfsfunktion selbst schreibt man natürlich in Assembler, damit da nicht der Übersetzer zuvor irgendetwas mit den Registern anstellt. Außerdem besteht nun noch die Möglichkeit, die Hilfsfunktion so zu erweitern, damit sie nicht nur statisch bar anspringt, sondern generisch ist und auch für foo verwendet werden kann.

Fassen wir die Voraussetzungen für den Start einer Koroutine zusammen: Wir müssen einen Speicherbereich als Stack reservieren, in der Praxis sollten 4K reichen, diesen für context_switch vorbereiten und den Stackzeiger der Koroutine entsprechenden setzen. Damit sind wir in der Lage, mittels context_switch in eine neue Koroutine zu wechseln.

Bleibt die Frage: Wie komme ich in die allererste Koroutine, direkt nach dem Start des Betriebssystems, nachdem wir die Geräteinitialisierung abgeschlossen haben und den Koroutinen die Kontrolle übergeben wollen? Das ist sogar ziemlich einfach, ohne das wir dafür eine neue Funktion brauchen: Es reicht, wenn man einfach einen temporären StackPointer anlegt, und diesen als current Parameter übergibt. context_switch pusht dann einfach die Register auf den aktuellen Stack, den wir danach eh nicht mehr brauchen, und schreibt den Wert des Stackzeigers in die temporäre Variable. Danach wird der Kontext der ersten Koroutine geladen und diese ausgeführt.