Gegenüberstellung von Thread- und Prozessoreigenschaften
Im vorangegangenen Kapitel wurde ausgehend von verschiedenen UNIX-Konzepten die UNIX-Emulation auf L3 entworfen. In diesem Kapitel soll in einigen wenigen ausgewählten Bereichen auf die Umsetzung dieses Entwurfs eingegangen werden. Dabei wird der Schwerpunkt auf folgende Kernelemente der Emulation gelegt:
Gezeigt wird dabei der Einsatz der L3-Konzepte und ein kurzer Abriß
der eingesetzten Algorithmen. 6.1 Die Emulationstask
Eines der Kernelemente der Emulation ist die Emulationstask. Sie
verkörpert den UNIX-Prozeß, den Träger der Aktivität innerhalb von
UNIX. In den vorangegangenen Kapiteln wurde die Struktur der Task und
die Anbindung der Emulationsbibliothek sowie das
Prinzip der Signalbehandlung beschrieben. In
diesem Kapitel soll die Umsetzung der geschilderten Konzepte gezeigt
werden. Dabei wird von den zugrundeliegenden L3-Konzepten ausgegangen
und die darauf aufbauende Lösung beschrieben. 6.1.1 Threads in L3 - Widerspiegelung der Hardware
Die Intel-Prozessoren stellen dem Systementwickler im Protected Mode zwei Speichermodelle zur Verfügung, das segmentierte und das flache Speichermodell. Beide beruhen auf der Verwendung von Segmenten(1), wobei der Unterschied in der Verwendung der Segmente liegt.
Das flache Speichermodell definiert ein Segment, das bei Adresse 0 beginnt und sich über den gesamten Adreßraum erstreckt. Dadurch wird das Neuladen von Segmentregistern(2) vermieden und der bei einem Speicherzugriff verwendete Offset ist zugleich die richtige virtuelle Adresse. L3 verwendet das flache Speichermodell für Tasks.
L3 stellt jedem Thread einen virtuellen Prozessor zur Verfügung. Dabei werden nahezu alle Eigenschaften des 80x86 an den Thread weitergereicht. Jeder Thread hat:
Der Stack muß von der erzeugenden Task bereitgestellt(3) werden, während die IDT vom Thread selbst gesetzt werden muß. Da die Anweisung zum Setzen der IDT aber eine privilegierte Anweisung ist, wird sie in L3 durch einen Systemruf realisiert. In Abbildung [hier] sind die Elemente des Threads und Prozessors noch einmal gegenübergestellt.
Gegenüberstellung von Thread- und Prozessoreigenschaften
6.1.2 Zustellung von Ausnahmen und Fehlern
Da jedem Thread ein virtueller Prozessor zur Verfügung gestellt wird,
muß ein Thread auch in der Lage sein, Ausnahmen zu behandeln. Einen
großen Teil der Ausnahmen behandelt der Kern. So werden
z. B. Seitenfehler innerhalb eines gültigen Mappings mit Hilfe der
Speicherverwaltung behandelt. Unter bestimmten Bedingungen werden die
Ausnahmen allerdings an die Task zugestellt. Ausnahmen und Fehler
Der 80x86-Prozessor stellt zwei Konstrukte zur Verfügung, die den normalen Programmfluß ändern können, Unterbrechungen und Ausnahmen. Sie können als nicht programmierte Prozeduraufrufe betrachtet werden und dienen zur Behandlung externer Ereignisse oder zur Anzeige von Fehlern oder Ausnahmesituationen.
Unterbrechungen werden von externen Geräten generiert und sind dadurch asynchron zum normalen Programmfluß. Sie werden in L3 auf Nachrichten abgebildet, die von Gerätetreibern empfangen werden können.
Ausnahmen werden durch Befehle des Programms ausgelöst und sind damit synchron zum Programmfluß. Sie werden in zwei Situationen ausgelöst:
Er unterscheidet dabei:
Faults sind Ausnahmen, die gemeldet werden, als ob der Befehl nicht ausgeführt worden wäre. Sie werden vor oder während der Befehlsausführung entdeckt. Der Prozessorzustand wird dabei so gesichert, daß ein erneutes Ausführen des Befehls möglich ist.
Ausnahmen, die nach der Beendigung des verursachenden Befehls gemeldet werden, werden als Traps bezeichnet.
Aborts sind Ausnahmen, die bei Hardwarefehlern oder inkonsistenten Systemtabellen ausgelöst werden. Sie gestatten keine Lokalisierung der Fehlerstelle.
Der 80x86 stellt Befehle zur Verfügung, die sogenannte Softwareunterbrechungen auslösen. Diese werden vom Prozessor allerdings wie Ausnahmen behandelt. Zu den Befehlen gehören INTO, INT 3, INT n und BOUND.
Die wichtigsten, vom Prozessor generierten Ausnahmen, die in der Emulation eine Rolle spielen, sind:
Diese Ausnahme wird durch einen INT 3 generiert. Sie wird in der Regel von Debuggern genutzt.
Diese Ausnahme wird vom L3-Kern genutzt, um einem Thread Ausnahmesituationen zu signalisieren, die sich aus dem Programmablauf des Threads ergeben haben. Welche Ausnahmen das sind, wird im weiter unten stehenden Abschnitt über Fehler beschrieben.
Wird während der Aktivierung einer Ausnahmebehandlungsroutine eine erneute Ausnahme ausgelöst, kann der Prozessor sie normalerweise nacheinander behandeln. Es gibt allerdings Kombinationen, bei denen das nicht möglich ist. Dann wird eine Double Fault-Ausnahme signalisiert.
Diese Ausnahme wird der L3-Task signalisiert, wenn ein Schreibzugriff auf eine schreibgeschützte Seite erfolgt und sich der Stackpointer in der Nähe der den Fehler verursachenden Adresse befindet. Da der Thread zur Behandlung des Fehlers Platz auf dem Stack braucht, wird der Schreibschutz von der Seite entfernt und eine Stack-Ausnahme ausgelöst.
Schutzverletzungen, die nicht in eine andere Kategorie fallen, verursachen eine allgemeine Schutzverletzung. Unter anderem wird eine allgemeine Schutzverletzung signalisiert, wenn eine Ausnahme ausgelöst wird, für die keine gültige Behandlungsroutine existiert.
Ein Seitenfehler wird einem Thread zugestellt, wenn er auf einen schreibgeschützten Bereich zugreifen will und keine Stack-Ausnahme ausgelöst wird.
Eine genaue Beschreibung der Ausnahmen kann [32] entnommen werden.
Neben den Ausnahmen, die vom Kern an die Threads weitergeleitet werden, gibt es einen Mechanismus, über den der L3-Kern Fehlersituationen signalisiert, die nicht in das Ausnahme-Schema passen. Das sind:
Dieser Fehler resultiert aus einem der wenigen L3-Signale, dem Signal halt_signal. Es kann von einem Thread einer privilegierten Task an jeden beliebigen anderen Thread bzw. von einem Thread einer beliebigen Task an einen Thread der gleichen Task zugestellt werden.
Dieser Fehler wird signalisiert, wenn ein Thread auf einen Bereich zugreift, für den es kein Mapping gibt.
Fehler werden über die Ausnahme 7 zugestellt. Die Ursache kann innerhalb der Ausnahmebehandlungsroutine mit dem Systemruf GetError() abgefragt werden. In Abhängigkeit vom Fehler kann dann eine entsprechende Reaktion eingeleitet werden.
Der L3-Kern stellt Ausnahmen nach dem selben Schema zu wie der 80x86. Eine Ausnahme oder Unterbrechung kann im Kontext der verursachenden Task oder in einer separaten Task behandelt werden. Die Unterscheidung erfolgt anhand des der Ausnahme zugeordneten Deskriptors. Dieser kann drei Typen beschreiben, das Task Gate, das die Behandlung in einer separaten Task aktiviert, und das Interrupt und Trap Gate, das die Behandlung im Kontext der verursachenden Task durchführt. Da das Interrupt Gate für die Behandlung von Unterbrechungen bestimmt ist, die Emulation aber nur Ausnahmen behandeln muß, wurde das Trap Gate für die Ausnahmebehandlung in der Emulation gewählt. Ein Deskriptor für ein Trap Gate ist in Abbildung [hier] beschrieben.
Tritt eine Ausnahme auf, holt der Prozessor aus der IDT den zugehörigen Deskriptor. Ist der Deskriptor gültig, bereitet der Prozessor den Stack vor, wechselt evtl. die Privilegstufe und springt die Routine an. Dabei wird bei einigen Ausnahmen ein Fehlerkode auf den Stack gelegt. Dieser muß von den Ausnahmebehandlungsroutinen der Emulationsbibliothek vor dem Verlassen der Behandlungsroutine vom Stack genommen werden.
Da die Emulationsbibliothek in C implementiert wurde, sich dieser Fehlerkode und die Art und Weise der Rückkehr zur Fehlerstelle aber nicht mit der vom C-Compiler generierten Return-Sequenz für eine C-Funktion verträgt(4), wurde eine Ebene zwischen die eigentliche Behandlungsroutine und den Aufruf durch den Kern gelegt. Diese Ebene besteht aus einer Assemblerroutine, die den Stack entsprechend bearbeitet. Der Aufbau eines Ausnahmestacks ohne Privilegwechsel(5) ist in Abbildung [hier] dargestellt.
Die Assemblerroutine rettet die Register und aktiviert die
eigentliche Ausnahmebehandlungsroutine. Diese kennt die von der
Assembleroutine vorbereitete Stackstruktur und kann nun ganz normal
eine Behandlung der Ausnahme vornehmen. Kehrt sie zurück, bereinigt
die Assemblerroutine den Stack und führt ein Far Return aus.
Dadurch können die Behandlungsroutinen in C geschrieben werden und
brauchen sich nicht um die besonderen Umstände ihres Aufrufs kümmern.
6.1.3 Aufbau der Emulationstask
In Abschnitt [hier] wurde das Layout des UNIX-Prozesses im Speicher dargestellt. Dabei wurden zwei Probleme der Implementation überlassen:
Ein UNIX-Programm ruft als einen der ersten Systemrufe im Startupkode brk(0) auf, um sich die Anfangsadresse der Halde geben zu lassen. Wird danach durch die Bibliotheksfunktion sbrk(int increment) mehr Speicher angefordert, wird über einen Aufruf von brk(HeapStart + Actsize + increment) der Heap durch den Kern vergrößert.
Diese Semantik läßt sich durch einen separaten Datenraum implementieren. Dieser kann an eine beliebige Stelle im Adreßraum gelegt werden, da sich der Prozeß über brk(0) die Anfangsadresse des Heaps geben läßt. Das Anwachsen des Heaps wird dann durch ein erneutes Mappen auf die gleiche Adresse mit der geforderten Größe realisiert. Hinzu kommt, daß L3-Resourcen wie Seitentabellen-Einträge und Platz auf dem Hintergrund erst dann reserviert werden, wenn auf sie zugegriffen wird. Dadurch kann der Datenraum prophylaktisch größer gemappt werden, als vom Prozeß gefordert wird, um die Effizienz der Speicherreservierung zu erhöhen.
Im gegebenen Layout wachsen Stack und Heap aufeinander zu. Hier wird nach folgendem Schema eine Kollision verhindert:
In Kapitel [hier] wurde für die Anbindung der
Emulationsbibliothek die Variante des Abfangens der Systemrufe
gewählt. Nach einer kurzen Beschreibung des Aufrufs der Systemdienste
in Linux wird der Mechanismus vorgestellt, mit dessen Hilfe dieses
Abfangen implementiert wird. Systemrufe in Linux
Der Aufruf des Linux-Kerns erfolgt in den Kapitel (2) Funktionen der C-Bibliothek. Diese Funktionen übergeben in Register EAX die Nummer des angeforderten Systemdienstes und in den Registern EBX, ECX, EDX, ESI und EDI die Parameter. Dabei werden die Werte den Registern in der angeführten Reihenfolge übergeben.
Die für die Parameterübergabe benötigten Register werden gerettet und
nach dem Laden der Parameter wird über die Anweisung INT 0x80 der
Kern betreten. Dieser rettet die Register, sucht aus einer Tabelle die
entsprechende Funktion heraus und springt diese an. Der Rückgabewert
der aufgerufenen Funktion wird in EAX zurückgegeben. Die
Funktionen der C-Bibliothek prüfen diesen Wert und setzen im
Fehlerfalle die globale Fehlervariable errno.
Abfangen des Kern-Eintritts
Um die Emulationsbibliothek einzubinden, muß also der INT 0x80 abgefangen werden. Da jeder Thread eine eigene IDT hat, ist der erste Ansatz das Definieren einer Ausnahmebehandlungsroutine für die Softwareunterbrechung INT 0x80. Das geht allerdings nicht, da der L3-Kern keinen INT n an den Thread weiterleitet.
Stattdessen generiert der Kern eine allgemeine Schutzverletzung, da er einen ungültigen Deskripor bzw. eine zu kleine IDT diagnostiziert. Der Fehlerkode der allgemeinen Schutzverletzung enthält allerdings alle Informationen, um den INT 0x80 durch zwei einfache Tests als Verursacher der Ausnahme zu identifizieren.
Die Behandlungsroutine kann dann anhand der Nummer des Systemrufs die zugehörige Funktion aus einer Tabelle entnehmen. Da diese Funktion Parameter erwartet, legt die vorgeschaltete Assemblerroutine die Register auf den Stack, von wo aus sie von der Behandlungsroutine als Prozedurparameter abgeholt werden können. Abbildung [hier] stellt einen normalen Prozeduraufruf und die von der Behandlungsroutine erwartete und vorgefundene Stackstruktur gegenüber.
Die Stackstruktur beim Aufruf der Behandlungsroutine für eine
allgemeine Schutzverletzung
Da die allgemeine Schutzverletzung ein Fault ist, muß in einem letzten Schritt noch die Rückkehr-Adresse korrigiert werden, um den INT 0x80 zu überspringen.
Der Algorithmus zum Abfangen der Systemrufe in der Behandlungsroutine sieht dann so aus:
Der gesamte Ablauf von der Auslösung eines Rufs der C-Bibliothek bis zum Aufruf der zugehörigen Funktion der Emulation ist in Abbildung [hier] dargestellt. Er ähnelt stark dem in [1] beschriebenen Trampoline-Mechanismus, baut allerdings nicht auf einem extra dafür geschaffenen Kern-Mechanismus, sondern auf der allgemeineren Abstraktion der Spiegelung der Hardware auf.
Ablauf beim Aufruf eines Systemrufs
6.1.5 Signalzustellung
Für die Behandlung der Signale wurden zwei Entscheidungen getroffen. Es wird ein separater Signal-Thread eingeführt, der die asynchron auftretenden Signale akzeptiert und nach einer Prüfung den UNIX-Thread dazu veranlaßt, die Signale zu behandeln. Hier sind drei Probleme zu lösen:
Um den UNIX-Thread zu unterbrechen, wird ein L3-Signal verwendet, das Signal Halt from Terminal. Es bewirkt eine Unterbrechung aller Aktivitäten des Threads, insbesondere der IPC, und eine Aktivierung der Ausnahme 7 (Koprozessor nicht verfügbar).
Das Senden dieses Signals war ursprünglich privilegierten Prozessen
vorbehalten, wurde aber unter Beachtung der Autonomie der Task so
modifiziert, daß ein Thread einer Task dieses Signal an einen anderen
Thread der gleichen Task senden kann.
Die Signalbehandlung im Zusammenspiel von Signal- und
UNIX-Thread
Abbildung [hier] stellt den Ablauf bei der Zustellung eines Signals dar. Der Signal-Thread empfängt ein Signal vom Prozeß-Server und trägt das Signal in die Menge der zuzustellenden Signale ein. Ist das Signal nicht blockiert, muß es zugestellt werden. Dabei verfährt der Signal-Thread nach folgendem Algorithmus:
Da UNIX keine Warteschlangen für Signale verwendet, ist es möglich ist, daß kurz hintereinander kommende Signale des gleichen Typs verloren gehen. Da hier keine neue Semantik der Signalzustellung eingeführt werden soll, werden neue Signale einfach zu den vorhandenen hinzugefügt. Ist die Signalbehandlung nicht aktiv, wird dem UNIX-Thread gemeldet, daß Signale da sind.
Auf der Gegenseite bearbeitet die Behandlungsroutine für die Ausnahme 7 die eingetroffenen Signale. Das geschieht durch Parsieren der ausstehenden Signale (pending signals). Dabei wird eine Menge aufzurufender Signalbehandlungsroutinen aufgebaut, die im Anschluß an das Parsieren der Signale nacheinander aufgerufen werden.
Da aber während der Bearbeitung der Signale neue Signale eintreffen können, kontrolliert der Algoritmus am Ende noch einmal, ob die Signalmenge leer ist. Sind wieder Signale vorhanden, beginnt die Bearbeitung von vorn. Der Algorithmus läßt sich wie folgt beschreiben:
Kritisch ist nur die Situation, wenn ein Signal hinzugefügt wird, während die Signalbehandlung aktiv ist. Ist die Behandlungsroutine beim Iterieren über die Signalmenge aber schon an dem Signal vorbei, könnte es verloren gehen, ohne überhaupt behandelt zu werden. Das darf nicht geschehen. Deshalb kontrolliert die Routine nach dem Deaktivieren des flags noch einmal, ob in der Zwischenzeit Signale angekommen sind. Ist das der Fall, wird die Signalbehandlung wieder aktiviert und dabei geprüft, ob sie schon wieder aktiv war. Wenn das der Fall war, wurde bereits ein erneutes Halt-Signal vom Signal-Thread generiert und die Signale werden von einer eingeschachtelten Behandlungsroutine bearbeitet und die Arbeit der Routine ist beendet.
Das Zusammenspiel der beiden Threads garantiert also eine Zustellung
der Signale im Kontext des UNIX-Threads und nimmt dabei in Kauf, daß
kurz nacheinander kommende Signale verloren gehen.
Unterbrechbare und nicht unterbrechbare bzw. wieder aufsetzbare
Systemrufe
Mit der vorliegenden Variante der Signalbehandlung lassen sich auf einfache Weise beide Arten von Systemrufen realisieren. Der Signal-Thread entscheidet anhand des SignalPropagationFlags, ob er dem UNIX-Thread ein Halt zustellen soll oder nicht. Folgender Algorithmus realisiert einen nicht unterbrechbaren Systemruf:
Ein unterbrechbarer Systemruf muß damit rechnen, daß die Kommunikation mit dem Server abgebrochen wird. Er erkennt das an einem Timeout-Error, mit dem die IPC im Falle eines Halt abgebrochen wird. Ein unterbrechbarer Systemruf sieht dann so aus:
Hier muß allerdings ein Protokoll mit den Servern vereinbart werden, das ein Wiederaufsetzen der Systemrufe gestattet. Die Server dürfen insbesondere einen Dienst erst als abgeschlossen betrachten, wenn sie die Antwort erfolgreich an den Klienten gesendet haben.
Der Prozeßserver verwaltet die in Kapitel [hier]
beschriebenen Daten und bietet die in Kapitel [hier]
erläuterte Funtionalität. Er ist im Stadium einer Prototypimplementation und
realisiert deshalb die angebotene Funktionalität auf einfachste Art
und Weise. Die dabei verwendeten Datenstrukturen und Algorithmen
sollen kurz dargelegt werden. 6.2.1 Die Verwaltungsstrukturen des Prozeßservers
Die Daten der Prozesse werden in einer Tabelle verwaltet. Der Zugriff
auf die Elemente der Tabelle erfolgt mit der Id des Threads als
Schlüssel. Beim Entwurf der Struktur wurde darauf geachtet, daß
Datenelemente, die von einem der Informationsdienste des Servers
geliefert werden, einen zusammenhängenden Speicherbereich belegen. Das
ermöglicht einen Transfer zum Klienten mit Hilfe indirekter
Strings.
6.2.2 Die Dienste des Prozeßservers
Der Prozeßserver bietet neben den Informationsdiensten
Dieser Dienst liefert die verschiedenen Id's eines Prozesses. Dabei werden nur wirklich notwendige Daten übertragen. Nicht belegte zusätzliche Gruppen oder effektive Id's, die sich nicht von den richtigen Id's unterscheiden, werden nicht übertragen.
Dieser Dienst liefert die mit der Job-Steuerung verbundenen Daten. Sie werden mit Hilfe eines indirekten Strings übertragen.
Dieser Dienst liefert alle Informationen über einen Prozeß. Er ist für Dienste wie ps vorgesehen.
Dienste zum
Die Dienste der zweiten Gruppe stellen einen Aspekt in der
Implementierung der Systemrufe der Prozßverwaltung dar und werden
deshalb im nächsten Abschnitt im Kontext der sie nutzenden
Emulationsfunktionen beschrieben.
6.3 Das Zusammenspiel von Emulationstask und Prozeßserver
Die Systemrufe der UNIX-Emulation werden durch eine Kombination der
Aktivität der Emulationsbibliothek und des Prozeßservers
realisiert. Dieses Kapitel beschreibt die Zusammenarbeit der beiden
Emulationselemente und konzentriert sich dabei auf die wesentlichen
Aspekte. 6.3.1 fork()
Auszug aus dem Ablauf eines fork()
Der Systemruf erzeugt eine bis auf wenige Details identische Kopie des rufenden Prozesses. Er muß dazu den Zustand des aktuellen Prozesses ,,einfrieren'', den Adreßraum ,,kopieren'' und mit Hilfe des Prozeß-Servers einen neuen Prozeß daraus erzeugen. Der neue Prozeß versetzt die Register in den Zustand ,,vor dem fork()'' und kehrt zurück. Der Ablauf bei einem fork() ist in Abbildung [hier] dargestellt. Dabei wird von der Struktur mit einem separaten Heap ausgegangen. Nicht dargestellt ist die Iteration über die Filedeskriptoren, um alle Fileserver von der Existenz eines neuen Prozesses zu informieren.
Der Prozeßserver reserviert einen Eintrag in der Prozeßtabelle,
kopiert die Informationen des Vaters und initialisiert einige Felder
neu (siehe [26], Kapitel 3.3.1). Dann erzeugt er eine
neue Task und liefert die Id's des neuen Prozesses an den Vater zurück.
6.3.2 execve()
Auszug aus dem Ablauf eines execve()
Execve() ersetzt das aktuelle Programm durch das beim Aufruf angegebene Programm. Dazu müssen im wesentlichen folgende Schritte ausgeführt werden:
Dieser Ablauf ist in Abbildung [hier] dargestellt.
6.3.3 wait(), waitpid()
Die wait-Rufe bestehen im wesentlichen aus einem Call zum Prozeß-Server mit Übergabe entsprechender Parameter. Der Prozeßserver sucht in seinen Datenstrukturen nach einem Sohn-Prozeß, der ein exit() ausgeführt hat. Existiert ein solcher, werden die entsprechenden Informationen zurückgegeben.
Befindet sich kein Prozeß im zombie-Zustand(1) und will der Prozeß auf einen solchen warten, wird keine Antwort gesendet. Beendet sich ein Sohn-Prozeß, findet der Prozeß-Server in seinen Datenstrukturen einen wartenden Vater-Prozeß. Diesem werden die Informationen des Sohnes zugestellt.
Der Wartezustand wird durch die ausbleibende Antwort im Falle eines
nicht vorhandenen, beendeten Sohnprozesses realisiert.
6.3.4 getxxx()
Die getxxx()-Funktionen greifen auf im Prozeß gepufferte Daten
zurück. Diese werden beim ersten Aufruf einer getxxx()-Funktion
vom Prozeß-Server beschafft und beim Aufruf einer setxxx()
aktualisiert. Dadurch wird die Kommunikation mit dem Prozeß-Server
gering gehalten.
6.3.5 kill()
Ein kill()-Ruf besteht im wesentlichen aus einer Nachricht an den
Prozeßserver, der nach der Prüfung der Rechte das Signal an den
Signal-Thread der UNIX-Task weiterleitet. Optimierungen für
Spezialfälle wie kill(myself) wurden dabei noch nicht
berücksichtigt.
6.3.6 sigxxx()
Die sigxxx()-Funktionen stellen Fuktionen zur Manipulation der verschiedenen Signalstrukturen bereit. Sie arbeiten über einem 32-Bit-Integer und einer Datenstruktur, die die Signalbehandlungsroutinen und Flags enthalten.
Interessant sind hier nur:
das mit einer atomaren Operation eine neue Signalmaske setzt und dann ein Receive() auf den Signale-Thread ausführt. Da dieser nie an den UNIX-Thread sendet, wartet der UNIX-Thread solange, bis der Signal-Thread eine Signalbehandlung auslöst.
das beim Setzen einer neuen Signalmaske darauf achten muß, daß deblockierte Signale zugestellt werden.
Struktur eines Trap Gate's
Die Ausnahme-Stackstrukturen
Die Zustellung von Signalen