6 Implementation

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:

  1. Der Prozessor erkennt eine Ausnahmesituation.

    Er unterscheidet dabei:

  2. Das Programm löst durch einen Befehl gezielt eine Ausnahme aus.

    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:

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:

Zustellung von Ausnahmen und Fehlern

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.

Struktur eines Trap Gate's

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 Ausnahme-Stackstrukturen

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:

  1. Wie wird der Speicherbedarf eines Prozesses befriedigt, der über den Standarddatenraum hinausgeht?
  2. Wie verhindert man ein Hineinlaufen des Stacks in den Datenbereich des Programms?

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:

  1. Der Stack wird mit zwei Megabyte dimensioniert.
  2. Die erste Seite unterhalb des Stacks wird durch SetAccessRights(FirstPage, read only) schreibgeschützt.
  3. Tritt eine Stack-Ausnahme auf, wird diese in ein Segmentation Fault-Signal umgesetzt. Da vom L3-Kern der Schreibschutz von der Seite entfernt wurde, ist eine Behandlung des Signals möglich. Diese führt in der Regel zu einer Beendigung des Prozesses.
  4. Die brk()-Anweisung prüft für den Fall, daß der Heap im Standarddatenraum liegt, ob eine Kollision auftreten kann.

6.1.4 Anbindung der Emulationsbibliothek

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:

  1. Wie wird der UNIX-Thread dazu veranlaßt, ein Signal zu behandeln?
  2. Wie erfolgt die Signalbehandlung?
  3. Wie wird die Semantik der unterbrechbaren und nicht unterbrechbaren bzw. neu startbaren Systemrufe realisiert?

Asynchrone Unterbrechung des UNIX-Threads zum Zwecke der Signalbehandlung

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

Die Zustellung von Signalen

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.


Fu▀noten:
  1. Segmente sind Speicherbereiche, die durch Deskriptoren beschrieben werden. Deskriptoren enthalten unter anderem die Basisadresse des Segments, die Größe des Segments und Schutzattribute.
  2. Der Zugriff auf eine Adresse erfolgt über eine Kombination von Segmentregister und Offset. Das Segmentregister enthält einen sogenannten Selektor, der auf einen Eintrag in einer der beiden Deskriptortabellen (es gibt zwei Arten von Deskriptortabellen, die globale Deskriptortabelle (GDT) und die lokale Deskriptortabelle (LDT)) verweist. In diesen Deskriptortabellen stehen die Deskriptoren der existierenden Segmente. Durch Addieren der Basisadresse und des Offsets wird die eigentliche Adresse gebildet.
  3. Bereitgestellt wird hier im Sinne von spezifiziert verwendet. Der Stackpointer wird beim Erzeugen des Threads auf den vom Erzeuger angegebenen Wert gesetzt. Dieser sollte auf einen verfügbaren Speicherbereich zeigen.
  4. Die Return-Anweisung für ein Trap-Gate muß ein Far Return sein, das das Kodesegment vom Stack nimmt. Der Compiler generiert nur ein Near Return.
  5. Der Aufruf einer L3-Ausnahmebehandlungsroutine erfolgt ohne Wechsel der Privilegstufe.

6.2 Der Prozeßserver

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

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:


Fu▀noten:
  1. Der Zustand zwischen exit() und Abholen der Informationen durch den Vater-Prozeß wird als zombie-Zustand bezeichnet, da der Prozeß an sich beendet ist, die Prozeßverwaltung aber noch Daten des Prozesses für den Vater aufbewahrt.

Jean Wolter
14.11.1995