Programmiersprachen und Übersetzer
10 - Maschinencode

Graphiken und Animationen

PreviousNext

In dem Teil der Veranstaltung "Programmiersprachen und Übersetzer", der sich mit der technischen Seite, dem Übersetzerbau, beschäftigt, haben wir zunehmend darauf hingearbeitet, die semantische Lücke zwischen dem Text der Quellcodeebene und dem Programm der Maschinenebene zu schließen. Schrittweise haben wir uns von Zeichen zu Tokens (Scanner), von Tokens zu Bäumen (Parsing), von Bäumen zu semantisch korrekten Bäumen (Semantische Analyse), und von abstrakten Syntaxbäumen zum Zwischencode (Codeerzeugung) bewegt. Aber es fehlt noch ein letzter Schritt: Wir müssen von der Ebene des Zwischencodes zur Ebene der real existierenden Maschine kommen. Und da gibt es noch einige Unterschiede: Wo die IR-Maschine beliebig viele Register hat, hat der Prozessor nur eine endliche Anzahl derer. Wo die IR-Maschine Funktionsaufrufe mit Parameterübergabe beherrscht, gibt es auf dem physikalisch existierenden Prozessor nur einen call-Befehl, der mehr ein Sprung auf Steroiden ist. Wo die IR-Maschine unspezifiziert ist, wie das Programm startet, müssen wir für die Ausführungsplattform ein passendes Binärformat erzeugen. All diese verbleibenden Aspekte werden wir in die Vorlesung thematisieren. Damit vollenden wir unsere Reise zur Schließung der semantischen Lücke, einer Reise, die man als 10.000 Abstraktionsebenen unter der Entwicklungsumgebung bezeichnen könnte.

Als Zielplattform, anhand derer wir die Maschinencodeerzeugung diskutieren werden, habe ich die IA-32 (32-Bit Intel Architektur) gewählt. Nicht, weil diese besonders hübsch oder zugänglich ist, sondern weil sie ein seit 40 Jahren stabiles Prozessorinterface bietet. Außerdem unterstützen alle Intel CPUs bis heute diesen 32-Bit Modus, auch wenn wir diese normalerweise im 64-Bit AMD64 Modus betreiben. Daher können Sie die Programme, die aus dem Übungsübersetzer fallen, wirklich ausführen und schrittweise im Debugger durchgehen. Dabei ist die Konzentration auf IA-32 kein Hindernis für die Verallgemeinerbarkeit der vorgestellten Techniken. Jede Abbildung des Zwischencodes auf eine reale Prozessorarchitektur muss die selben Probleme lösen, wie wir dies für IA-32 tun müssen. Oft fallen dabei Designentscheidungen anders aus, aber die Probleme bleiben die gleichen.

Das erste Problem, dessen wir uns annehmen müssen, ist, wie wir die Speicherabstraktion der IR-Maschine auf den Prozessor abbilden. Unsere IR-Maschine ist mit einer sehr mächtigen Speicherabstraktion ausgestattet, weil wir dort zum einen symbolisch benannte Variablen (Register) haben, von denen wir unendlich viele besitzen können. Außerdem gibt es die Befehle StackAlloc und HeapAlloc, die es uns erlauben, zusätzlichen Speicherplatz für Objekte anzufordern; es gibt also eine sehr rudimentäre Unterstützung für Objekte. Reale Prozessoren sind deutlich eingeschränkter: Kein realer Prozessor hat unendlich viele Registern, sondern ihre Anzahl ist beschränkt. Der Speicher ist auch nicht so hübsch in Variablen und allozierte Objekte strukturiert, sondern wir arbeiten nur mit einer endlichen Anzahl an Speicherzellen, die wir über einen numerischen Index (== Zeiger) ansprechen können. Zwischen beiden Welten bedarf es also einer Abbildungsfunktion.

Das zweite Problem sind die Befehle der IR-Maschine: Wir haben uns den Zwischencode so definiert, dass die meisten Befehle 3 Operanden haben (Quadrupelschreibweise), wobei Quell- und Zieloperanden getrennt voneinander gewählt werden können. Auf IA-32 haben wir diesen Luxus nicht, dort haben Befehle in der Regel 2 Operanden, wovon ein Operand eine doppelte Rolle hat und sowohl Quell- als auch Zieloperand ist. Außerdem haben wir auf der IR-Ebene den Call-Befehl, der nicht nur eine Funktion aufruft, sondern auch, nebenbei, eine beliebige Anzahl an Argumenten als Parameter an die neue Funktionsinstanz übergeben kann, wo sie dann wie lokale Variablen verwendet werden können. Das ist sehr schick, aber es wird von keiner realen Maschine unterstützt. Das Attribut, bei dem Sie stutzig werden müssen, ist "beliebige Anzahl", denn nichts auf einer realen Maschine hat eine beliebige Anzahl; immer gibt es irgendeine Art von oberer SchrankeAm Ende besteht die Maschine eben doch aus einer endlichen Anzahl von Atomen, die nur eine endliche Anzahl von Taktzyklen betrieben werden kann, bevor Elektromigration alle Gates und Leitungen aufgefressen hat. Oh Memento Mori!. Auch hier brauchen wir für jeden IR-Befehl eine Abbildung auf einen IA-32-Befehl.

Das dritte Problem ist die Speicherung des Programms. Darüber haben wir uns bei der IR-Maschine überhaupt keine Gedanken gemacht. Die Befehle kamen einfach irgendwo her und wurden entlang des Kontrollflussgraphen abgearbeitet. IA-32 kennt aber Kontrollflussgraphen nicht als Dateiformat, sondern nur einen linearen Instruktionsstrom. Wir müssen unser übersetztes Programm so in eine Datei speichern, dass es vom Betriebssystem, als ein Prozess, in den Speicher geladen wird, wo es dann als Instruktionsstrom abgearbeitet werden kann. Wir schauen uns dazu an, wie das ELF-Binärformat für Linux aufgebaut ist und wie der erzeugte Assemblercode im Anschluss an die Übersetzung für die Ausführung vorbereitet wird.

Alles in allem: Machen Sie sich bereit, die letzte semantische Lücke zu schließen. Am Ende haben wir ein ausführbares Binärprogramm.

Graphiken und Animationen

PreviousNext

Der erste Schritt, über den wir uns bei der Transformation von IR-Code zu Maschinencode Gedanken machen werden, sind Funktionsaufrufe. Anhand dieser Funktionsaufrufe lernen wir nicht nur, wie Argumente transportiert werden, sondern auch, wie lokale Variablen im Call-Frame abgelegt werden. Dazu wollen wir uns aber zunächst in Erinnerung rufen, was der IR-Befehl Call genau getan hat. Der erste Operand von Call war der Name der Funktion, die der Aufrufer (Caller) aktivieren will (Callee). Die restlichen (beliebig viele) Operanden sind die Argumente, die vom Caller zum Callee übertragen werden (Datenfluss A). Für jeden Funktionsaufruf entsteht eine neue Funktionsinstanz, die wir mit eigenen lokalen Variablen ausstatten, die im Call-Frame gespeichert werden. Zusätzlich wird im Call-Frame auch noch eine Rücksprungadresse gespeichert, die angibt, an welche Codestelle im Caller wir beim Return-Befehl zurückkehren. Mit der Rückkehr kann, über den Rückgabewert, ein zweiter Datenfluss (R) stattfinden.

Zentral bei der Abbildung auf die Maschine ist der Call-Frame. Für diesen stellt sich die Frage nach dem Datenlayout. Ähnlich wie bei Record-Typen müssen wir uns auf ein konkretes Abbild im Speicher festlegen. Nur so können wir die Verwendung von symbolischen Namen effizient auf die zeigerbasierte Adressierung der Maschine abbilden. Darüber hinaus müssen wir die Entscheidung über den BesitzerSiehe Besitz von Objekten. des Call-Frames treffen: Wer erzeugt den Call-Frame und wer löscht ihn wieder? Caller oder Callee? Außerdem müssen wir uns darauf festlegen, was der Callee am Maschinenzustand überhaupt verändern darf. Darf der Callee den gesamten Speicher mit Nullen überschreiben (eher nicht nützlich), oder darf der Caller annehmen, dass einige Teile des Maschinenzustands unverändert bleiben.

Wie Sie bereits sehen, ich spreche hier häufig davon, dass wir uns festlegen müssen. Diese Entscheidungen, die wir bei der Abbildung von Funktionsaufrufen und dem Call-Frame machen, sind nicht zwingend, sondern es sind Designentscheidungen. Es sind Konventionen, an die sich sowohl Caller als auch Callee halten, um miteinander arbeiten zu können. Daher heißen diese Designentscheidungen auch Aufrufkonventionen.

Eine Aufrufkonvention regelt, im Kern, drei Dinge: Zum einen wird geregelt, wie Operanden von Caller zum Callee kommen. Dabei legt der Caller die Operanden an fest definierte Orte in der Maschine (z.B. auf den Stack oder ins Register) und der Callee verlässt sich darauf, an genau diesen Stellen die Argumente zu finden. In der Rückrichtung verhält es sich mit dem Rückgabewert: Der Callee legt sein Berechnungsergebnis an eine vordefinierte Stelle in der Maschine, wo sie der Caller wieder auslesen kann.

Das Dritte, was eine Aufrufkonvention regelt, ist der Maschinenzustand, der über einen Funktionsaufruf hinaus unberührt bleibt. Wir haben schon häufiger davon gesprochen, dass wir Funktionsaufrufe als Komplexoperationen ansehen können, mit denen der Befehlssatz erweitert wird. Die Aufrufkonvention beschreibt dann, welche Seiteneffekte eine solche Call-Komplexoperation auf den Maschinenzustand hat. Eine mögliche Regel könnte zum Beispiel sein: Der Callee darf nur das Register eax, seinen eigenen Call-Frame, und alle über Zeiger erreichbare Speicherzellen verändern.

Aufrufkonventionen dienen dazu Kompatibilität zu schaffen. Zum einen kann ein Übersetzer so Funktionen unabhängig voneinander zu Maschinencode übersetzen, da die Regeln für Funktionsaufrufe überall gleich sind. Dies funktioniert sogar, wenn wir den Übersetzer auf mehreren Quelldateien ausführen, um eine separate Übersetzung durchzuführen (dazu später mehr). Aber eine Aufrufkonvention fördert auch die Kompatibilität zwischen verschiedenen Übersetzern, und sogar zwischen unterschiedlichen Programmiersprachen. So ist die Aufrufkonvention für C-Funktionen auf den meisten Plattformen die Lingua Franca, um Funktionen aus anderen Programmiersprachen aufzurufen.

Als Beispiel werden wir uns im Folgenden der System-V Aufrufkonvention für C auf der IA-32 Plattform beschäftigen. Diese können Sie genauer im Spezifikationsdokument ab Seite 35 nachlesen. Keine Angst, die Spezifikation ist sehr klar und, wenn Sie mit dieser Vorlesungseinheit durch sind, gut zu verstehen. Bei dieser Konvention werden die Argumente von rechts nach links auf den Stack gelegt, was dazu führt, dass das erste Argument zu oberst auf dem Stack liegt. Wir werden gleich sehen, welchen Vorteil diese Entscheidung bei Funktionen mit einer variablen Anzahl an Argumenten hat (z.B. printf()). Außerdem regelt die Aufrufkonvention, dass Rückgabewerte vom Typ int in %eax und Fließkommazahlen in %st0 gespeichert werden. Bezüglich des unveränderten Maschinenzustands regelt die System-V Aufrufkonvention, dass fünf Register (%esp, %ebp, %ebx, %esi, %edi) nach einem Funktionsaufruf den gleichen Zustand haben müssen, wie vor dem Funktionsaufruf. Die Callee-saved Register werden vom Callee gespeichert und am Ende wiederhergestellt.

Da Konventionen nur Konventionen sind, gibt es natürlich verschiedene Aufrufkonventionensiehe xkcd: Competing Standard. So verwendet Windows im selben Programm für normale Funktionsaufrufe die fastcall-Konvention und die Pascal-Konvention für Systemaufrufe.

Graphiken und Animationen

PreviousNext

Betrachten wir die Situation eines Funktionsaufrufs und die Erzeugung des Call-Frames auf IA-32 noch einmal genauer. Basis für diese Betrachtung ist, dass der Stack auf IA-32 von den hohen zu den niedrigen Adressen wächst, was sich in Maschinenbefehlen wie push und pop niederschlägt. Außerdem wird im Register %esp der Stackzeiger gespeichert, der als impliziter Quell- und Zieloperand für push/pop dient. Wir starten unsere Betrachtung im Caller, der eine Funktion mit 3 Parametern aufrufen wird. Um diesen Aufruf zu tätigen, führt der Caller die sogenannte Aufrufsequenz durch. Die Aufrufsequenz sind jene Maschinenbefehle, die auf Seiten des Callers den Funktionsaufruf vorbereiten und durchführen.

Der erste Schritt der Aufrufsequenz ist das Speichern der Argumente auf den Stack. Dabei legen wir die Argumente von rechts nach links auf den Stack. Achten Sie bei der Animation auf den linken und den rechten Rand des Stacks. Auf der linken Seite sehen wir, wie der Stackzeiger mit jedem Argument nach unten wandert, da er immer auf das oberste Element des Stacks zeigt. Auf der rechten Seite habe ich notiert, wie wir zu jedem Zeitpunkt auf das jeweilige Argument relativ zum Stackzeiger zugreifen könnten. Nachdem alle drei Argumente auf dem Stack liegen, können wir auf den Wert von arg2 mit einem relativen Offset von 8 (8(%esp) == %esp + 8) zugreifen.

Dieser relative Zugriff ist von großer Bedeutung, weil der Stackzeiger (und später der Basiszeiger) der Anker ist, an dem wir den Call-Frame festhalten können. Über die relativen und konstanten (!) Offsets können wir dann auf die einzelnen Felder des Call-Frames zugreifen. Dieses Vorgehen ist dem Vorgehen für Records sehr ähnlich: Auch dort gab es einen Zeiger, an dem wir das Objekt festgehalten haben und relative Offsets, die wir mit dem Datenlayout festgelegt haben. Genauso verhält es sich bei Call-Frames.

In den relativen Offsets liegt auch der Grund, wieso die Argumente von rechts nach links auf den Stack gelegt werden: Stellen Sie sich vor, dass unsere Funktion nicht nur 3 Parameter hat, sondern noch viel mehr, im schlimmsten Fall sogar eine variable Anzahl. Diese würden unter arg2 liegen und sie hätten keinen Einfluss auf die relativen Offsets für die ersten 3 Argumente. Der Callee kann also auf die ersten Argumente zugreifen, ohne zu wissen, wie viele Argumente noch kommen. Überlegen Sie sich dazu, mit welchem Offset das erste Argument von printf()int printf(const char *format, …) relativ zum Stackzeiger gespeichert ist. Da mit diesem ersten Argument format gespeichert ist, wie viele Argumente noch zu erwarten sind, kann die Implementierung die restlichen Offsets dynamisch berechnen. Wenn sie diesen Mechanismus noch genauer verstehen möchten, schauen Sie sich die Manpage va_arg(3) an.

Nachdem die Argumente auf dem Stack liegen, wird der Maschinenbefehl call ausgeführt, der die Rücksprungadresse auf den Stack legt und den Kontrollfluss zum Callee umleitet. Durch die Rücksprungadresse können wir später den Kontrollfluss des Callers wieder aufnehmen.

Da die Kontrolle über die Maschine nun beim Callee liegt, kann dieser den Rest des Call-Frames anlegen, indem der Stackpointer noch weiter nach unten verschoben wird. In diesem Zwischenbereich (gelb) werden dann die lokalen Variablen abgelegt. Wie Sie sehen, habe ich in der Animation keine feste Größe für diesen Bereich angegeben, sondern erst mal die Zahl x. Solange eine Funktion nur lokale Variablen hat, aber niemals eine dynamische Stackallokation (StackAlloc) durchführt, ist der gelbe Bereich von bekannter Größe und die Zahl x eine Konstante. In diesem Fall können wir weiterhin über einen konstanten Stackzeiger-Offset auf die Argumente zugreifen. Hätte unsere Funktion beispielsweise 3 lokale Variablen à 4 Byte, würden wir mit 24(%esp) an arg2 kommen.

Problematisch wird es, wenn der gelbe Bereich von unbekannter Größe ist. In diesem Fall brauchen wir einen zweiten Zeiger, der in die Mitte des Call-Frames zeigt, sodass die Parameter weiterhin über konstante Offsets erreicht werden können. Dieser Zeiger heißt Basiszeiger und wird auf IA-32 in %ebp gespeichert. Es heißt deswegen Basiszeiger, weil er eigentlich an die Basis des Call-Frames zeigt, die viele Autoren am Beginn des gelben Bereichs verorten. Für diese Autoren beginnt der Call-Frame erst mit den lokalen Variablen und die Argumente gehören noch zum Call-Frame des Aufrufers. Da ich es aber unlogisch finde, dass Parameter und lokale Variablen einer Funktionsinstanz in unterschiedlichen Call-Frames liegen, definieren wir den Call-Frame in dieser Veranstaltung so, dass er sowohl Parameter und lokale Variablen überdeckt.

Verwendet man einen Basiszeiger, so muss der ursprüngliche Wert dieses Registers gesichert (und am Ende wiederhergestellt) werden. Schließlich gehört %ebp zu den Callee-Save Registern.

Am Ende der Funktion baut der Callee seinen Anteil des Call-Frames wieder ab und gibt die Kontrolle mit dem ret-Maschinenbefehl an den Caller zurück. Dieser entfernt dann wieder die Parameter vom Stack und fährt mit seinem Kontrollfluss, nun um den Rückgabewert reicher, fort.

Ich möchte noch ganz kurz darauf eingehen, in welchen Aspekten sich Aufrufkonventionen unterscheiden können. Da auf aktuellen Plattformen Speicherzugriffe langsamer sind als Registerzugriffe, werden bei neueren Aufrufkonventionen die ersten Argumente nicht über den Speicher, sondern über die Register übergeben. Dies ist eine Optimierung, die insbesondere bei Funktionen mit weniger Argumenten, was die meisten Funktionen sind, die Anzahl der Speicheroperationen erheblich einschränkt.

Eine andere Designentscheidung für Aufrufkonventionen ist die Anzahl der Callee-Save Register. Umso mehr Register als Callee-Save angenommen werden, desto mehr Sicherungsoperationen können wir uns auf Seiten des Aufrufers sparen, da diese beim Callee gesichert werden. Andersherum, bei weniger Callee-save Registern haben Funktionen, insbesondere Blattfunktionen, mehr Register zur Verfügung, die ohne Sicherung verwendet werden können. Das grundlegende Problem ist, dass der Caller nicht weiß, welche Register der Callee tatsächlich verwenden wird, und der Callee nicht weiß, welche Register sein Caller in der Zukunft noch verwenden will. Deshalb suchen Aufrufkonventionen nach einem Trade-Off zwischen keine Callee-save Register und ausschließlich Callee-save Registern, der dieses gegenseitige Nicht-Kennen ausgleicht. Meist kümmert sich sowohl Caller als auch Callee um etwa die Sicherung des halben Registersatzes.

Der dritte Aspekt, der ebenfalls in Aufrufkonventionen geregelt ist, sind zusätzliche, nicht sichtbare Register. So wird beim thiscall (C++) der Zeiger auf das Objekt, auf dem eine Methode ausgeführt werden soll, im Register %ecx übergeben. Über solche zusätzlichen Argumente haben wir allerdings schon im Kapitel zur Codeerzeugung ausführlich geredetSiehe Codeerzeugung für Records..

Die Aufrufkonvention legt fest, welche Argumente über den Speicher im Call-Frame und welche in Registern übergeben werden. Daher wissen wir nun, wie der Maschinenzustand aussieht, bevor die erste Instruktion unserer Funktion ausgeführt wird. Nachdem wir dort den alten Basiszeiger gesichert und einen neuen etabliert haben, können wir mit konstanten Offsets auf die Parameter zugreifen. Aber es fehlt noch etwas essentielles: Wie bilden wir die lokalen Variablen auf den Speicher ab? Diesen (gelben) Teil habe ich bisher absichtlich ausgelassen, um jetzt genauer darauf einzugehen.

Das Problem ist, dass es (meist) mehr lokale Variablen in einer IR-Funktion gibt als der Registersatz der Maschine Plätze vorsieht. So bleiben bei IA-32 noch 6 "General-Purpose Register" über, in denen wir Werte speichern können, nachdem wir Stackzeiger und Basiszeiger abgezogen haben. Für alle Funktionen, die nur 6 IR-Variablen haben, können wir also eine 1:1 Abbildung vornehmen und brauchen keinen Stackspeicher vorsehen. Aber wie oft trifft das schon ein, nur 6 Variablen?

Daher müssen wir den Call-Frame als zusätzlichen Zustandsspeicher für die Funktionsinstanz auffassen. Dazu legen wir am Beginn der Funktion eine gewisse Anzahl an Speicherslots an, in denen wir Variablenwerte zwischenspeichern können, wenn sie gerade nicht in Register liegen. Wir können dann Werte zwischen Registern und Speicherslots hin und her verschieben.

Bei der einfachsten Variante diese Abbildung von IR-Variablen durchzuführen, legen wir für jede Variable einen festen Slot an, der fix mit dieser IR-Variable verbunden ist. Durch diese fixe Zuordnung zwischen IR-Variable und Stack-Slot können wir für jede Variable einen konstanten Basiszeiger-Offset angeben, mit dem wir den zugehörigen Slot adressieren können.

Ich möchte hier noch einmal ganz deutlich machen, dass es einen kategorischen Unterschied zwischen Variable und Stack-Slot gibt: Variablen sind ein Konzept der IR-Ebene und so auf der Maschinenebene so nicht vorhanden. Slots dagegen sind auf der Maschinenebene vorhanden, da wir auf eine konkrete Speicherzelle zeigen können und sagen: "Das ist der Stack-Slot 3 im Call-Frame zu einer Funktionsinstanz von bar()". Wie ist aber das Verhältnis von Variable zu Slot (in unserer fixen Zuordnung)? Man kann es sich bildlich so vorstellen, dass die Variable ein Geist ist, der entweder gerade in einem Register oder in einem Stack-Slot lebt. Zu jedem Zeitpunkt kann dieser Geist nur in einem dieser beiden Orte leben, denn entweder enthält ein Register den aktuellen Wert der Variable oder ein Stack-Slot.

Im Fall eines etwas komplexeren Übersetzers ist die Zuordnung von Variable an Stack-Slots nicht so fix wie in unserer einfachen Variante. In diesen Fällen kann eine Variable an unterschiedlichen Punkten in einer Funktion in verschiedenen Slots leben und mehrere Variablen können sich einen Slot teilen. Auf diese Weise kann ein Übersetzer den Speicherverbrauch minimieren, was, durch weniger Druck auf den Cache, auch zu einer schnelleren Ausführung führt.

Nachdem durch die Aufrufkonvention und die Abbildung von IR-Variablen auf Stack-Slots klar ist, wie das Datenlayout für einen Call-Frame aussieht, geht es nun darum, die IR-Befehle als Maschinenbefehle zu codieren. Dazu müssen zwei Entscheidungen getroffen werden: Bei der Befehlsauswahl wird für einen IR-Befehl ein einzelner oder eine Sequenz von Maschinenbefehlen ausgewählt. Bei der Registerallokation entscheiden wir, zu welchem Zeitpunkt eine Variable in ihrem Slot lebt und wann sie in einem CPU-Register zu finden ist. Haben wir beide Probleme gelöst, können wir die Maschinenbefehle zusammen mit den passenden Registeroperanden als Assembler rausschreiben und sind fertig mit der Übersetzung. Also eigentlich ganz einfach, wären da nicht zwei NP-vollständige Probleme.

Zum einen ist die Befehlsauswahl nicht so einfach: Viele Prozessoren, insbesondere CISC-Architekturen, haben viele Varianten eines einzelnen Befehls, die sich alle, mehr oder weniger stark, in ihrer Semantik und in ihren nicht-funktionalen Eigenschaften unterscheiden. So kennt die AMD64-Architektur 36 verschiedene Varianten von mov, die im Assembler alle mit dem mov-Opcode notiert werden. Außerdem ist nicht für jeden IR-Befehl eine 1:1 Abbildung möglich, sondern es wird eine 1:N Abbildung auf Maschinenbefehle benötigt, um die geforderte Funktionalität umzusetzen. Das ganze wird noch schlimmer, weil die Betrachtung mehrerer IR-Befehle in einer M:N Weise zu besseren Übersetzungsergebnissen führt. Alles in allem hat sich herausgestellt, dass eine optimale Befehlsauswahl ein NP-vollständiges Problem ist.

Zum anderen ist auch die Registerallokation ein Problem: Die Entscheidung, welche Variable zu welchem Zeitpunkt in welchem Register lebt, hat zum einen massive Auswirkungen auf die Performance des Programms. Dies rührt daher, dass Zugriffe auf den Speicher viel, viel langsamer sind als auf Registersiehe: Your computer is already a distributed system. Why isn't your OS?Zugriffszeiten von Stackoverflow.. Daher kostet jeder Transfer zwischen Stack-Slot und Register richtig viel Zeit und wir möchten während der Laufzeit möglichst wenige Slot-Register-Transfers haben. Aber Registerallokation ist auch ein kompliziertes Problem, wenn man Variablen über Basisblockgrenzen hinweg im Register halten möchte. Erwartet der Code eines Basisblocks zum Beispiel eine Variable in einem bestimmten Register, so müssen alle Vorgängerblöcke dafür sorgen, dass die Variable auch tatsächlich in diesem Register geladen ist. Da der CFG im Allgemeinen aber weder linear noch azyklisch ist, haben wir es hier mit einer zyklischen Rückkopplung solcher Bedingungen zu tun. Alles in allem hat sich herausgestellt, dass eine optimale Registerallokation ein NP-vollständiges Problem ist.

Aber das ganze wird noch schlimmer, da Befehlsauswahl und Registerallokation miteinander interagieren: Nicht jede Befehlssequenz, die die Befehlsauswahl in Betracht zieht, braucht gleich Register. Und nicht jeder Maschinenbefehl kann mit jedem Register aufgerufen werden. Außerdem gibt es auch noch Befehle, die als Seiteneffekt den Inhalt von Registern verändern. Alles in allem: Die Kombination aus Registerallokation und Befehlsauswahl ist ein richtig richtig dickes Brett.

Graphiken und Animationen

PreviousNext

Und immer wenn der Informatiker nicht weiter weiß, besinnt man sich auf die einfachste Methode, das Problem zu lösen und überlegt sich danach, an welchen Stellen man die Methode verbessern kannWichtig bei einem solchen Vorgehen inkrementeller Verbesserungen ist aber, dass man sich leicht in ein lokales Optimum manövrieren kann. Um dies zu vermeiden lohnt es sich eine optimale Lösung zu formulieren, egal wie aufwendig diese ist.. Dieser einfachste Basisfall für die Maschinencodeerzeugung wird uns dabei helfen, das Problem genauer zu verstehen, bevor wir einen Vorschlag diskutieren, wie wir diese Minimallösung verbessern können. Die Minimallösung besteht daraus, dass wir eine Makroexpansion für jeden IR-Befehl durchführen und alle Variablen vor der Sequenz aus dem Slot lesen und direkt danach wieder in zurückschreiben.

Für die Makroexpansion hinterlegen wir für jeden unserer 16 IR-Befehle ein festes Makro, welches wir expandieren, wenn ein solcher Befehl im IR-Programm vorkommt. Dieses Makro besteht aus einer Maschinenbefehlsequenz, die einen oder mehrere Instruktionen umfasst. An den Stellen, an denen Register in den Operationen verwendet werden würden, enthält das Makro allerdings Platzhalter (R1, R2), die von der Registerallokation gefüllt werden. Zusätzlich gibt es noch eine Reihe von Anweisungen, welcher IR-Operand in welchen Platzhalter geladen werden soll, und in welchem Platzhalter-Register das Ergebnis zu finden sein wird.

Für jedes Auftreten des IR-Befehls im IR-Programm instantiieren wir das Makro und verbinden die Anweisungen an den Ein- und Ausgängen mit den konkreten Operanden. Die Instantiierung des Makros übergeben wir dann an die Registerallokation, die dafür sorgen muss, dass für jeden Platzhalter ein Register ausgewählt wird, die aktuellen Variablen-Werte in den Register landen, und das Ergebnis im Zieloperanden landet.

Die einfachste Variante einer Registerallokation ist ein Spilling-Registerallokator. Bei dieser Art der Registerallokation betrachten wir immer nur einen einzigen Befehl: Vor dem Befehl laden wir alle Variablen frisch aus ihrem fix zugeordneten Stack-Slot in ein Register. Nachdem die Befehlssequenz abgearbeitet ist, wird das Ergebnis sofort wieder in einen Slot zurückgeschrieben. Dieses direkte Zurückschreiben führt dazu, dass eine Variable nur für die Dauer einer einzige Instruktion in einem Register lebt. Es gibt keinerlei Probleme, dass es über Kontrollflüsse hinweg zu irgendwelchen Inkonsistenzen kommen kann oder wir vergessen, irgendeinen Wert zurückzuschreiben. Schick. Schick, aber ineffizient.

Ineffizienz ist genau das Problem dieser minimalen Maschinencodeerzeugung. An (mindestens) drei Stellen wird das Potential der Maschine nicht voll ausgenützt: Zum einen transferieren wir ständig Variablen-Werte zwischen Speicher und Register hin und her, egal ob diese vielleicht schon in einem Register vorgeladen sind. Allein am Add-Beispiel, bei dem 3 von 4 Befehlen nur Transfers waren, wird deutlich, dass ein Hauptteil unseres Programms sich damit beschäftigt, den Speicher zu beschäftigen. Viel klüger wäre es, nur das aus dem Speicher zu laden, was nicht schon in einem Register geladen ist. Wenn wir den Preis für das Laden aus dem Speicher bezahlt haben, dann wollten wir, solange es irgendwie geht, auch etwas davon haben.

Das zweite Problem ist, dass die starren Makros komplexere Fähigkeiten der CPU nicht ausnützen können. Insbesondere bei CISC Maschinen kann ein einzelner Befehl eine sehr komplexe Semantik haben. Auf den Folien sehen Sie eine Adressberechnung für ein Array, das einmal naiv aus drei Makros zusammengesetzt wurde, und einmal den passenden IA-32 Befehl, der in einem Rutsch %eax+8*%ebx rechnet und dereferenziert. Die Besonderheiten der Prozessorarchitektur werden also nicht vollständig ausgenützt.

In eine ähnliche Richtung, aber unterschiedlich davon, ist das dritte Problem der Minimallösung: Die Makroexpansion ignoriert, dass moderne CPUs Befehle nicht stumpf hintereinander ausführen, sondern dass diese mit einer Pipeline arbeiten, Instruktionen in unterschiedlicher Reihenfolge als angegeben ausführen können (Out-of-Order) und überdies noch mehrere funktionale Einheiten haben (Superskalar). Dies führt dazu, dass Befehle quasi im Windschatten anderer Befehle "umsonst" ausgeführt werden können. So können in einer Out-of-Order-CPU Befehle auf der ALU ausgeführt werden, während ein früherer Befehl noch auf den Speicher wartet. Dieses Problem kann man so zusammenfassen, dass die Besonderheiten der Prozessor-Mikroarchitektur nicht ausgenützt werden.

Für all diese Teilaspekte gibt es Methoden die Maschinencodeerzeugung zu verbessern: Zum einen kann man bei der Registerallokation mehr als nur einen Befehl auf einmal betrachten und so eine globalere Registerallokation durchführen. Durch dieses größere Wissen wird die Allokation zwar aufwendiger, das Ergebnis aber um Größenordnungen besser. Um die Prozessorarchitektur auszunützen, haben moderne Übersetzer einen Peephole-Optimizer, der immer eine fixe Anzahl an Assemblerinstruktionen (z.B. 3 aufeinanderfolgende Befehle) mit einer Muster-Datenbank vergleicht und durch effizientere Schnipsel ersetzt. Um die mikroarchitekturellen Besonderheiten auszunützen, kann die Instruktion-Selektion Assemblerbefehle so umordnen, dass immer noch die gleiche Berechnung durchgeführt wird, aber möglichst viele Instruktionen im Windschatten anderer verdeckt werden.

Im Folgenden greifen wir uns den Aspekt der Registervergabe heraus und diskutieren einen Registerallokator, der nicht so sehr unter Amnesie leidet und sich, über den Verlauf eines einzelnen Basisblocks hinweg, merkt, welche Variablen bereits in den Registersatz transferiert wurden.

Graphiken und Animationen

PreviousNext

Zuerst müssen wir die Weltsicht dieses Allokators grundlegend erklären: Dieser Allokator mit Gedächtnis sieht den Registersatz als eine Art schnellen Zwischenspeicher (Cache) für die Slots der Variablen im Speicher. Der Allokator geht einen Basisblock Instruktion für Instruktion, von oben nach unten, durch und merkt sich währenddessen, welche Werte bereits im Cache liegen und welche in den Registersatz geladen werden müssen. Für letztere werden dann Load-Befehle emittiert, um den Cache zu füllen. Außerdem schreibt der Allokator die Werte aus den Registern nicht sofort zurück, wie das bei der Minimallösung der Fall war, sondern erst verzögert (lazy spilling). In den Worten der Veranstaltung "Grundlagen der Rechnerarchitektur" verwendet dieser Allokator den Registersatz als einen vollassoziativen Cache mit Write-Back Strategie. Wenn Ihnen dieser Satz Probleme bereitet, gehen Sie noch einmal zu Ihren GRA Unterlagen zurück und lesen Sie dort nach, was damit gemeint ist.

Verwendet werden kann der Allokator direkt aus der Makroexpansion heraus. Auf den Folien sehen Sie, wie die Makroexpansion für den Add-IR-Befehl aussieht. Dabei hat die Expansion über self.RA Zugriff auf den verwendeten Registerallokator. Dieser verwaltet nicht nur, wie der Name andeutet, die vollen und freien Register, sondern auch die Zuordnung von Register zu Variablen. Daher ordnet die Makroexpansion an, dass die linke (instr.lhs) und die rechte (instr.rhs) in Register geladen sein müssen. Dabei gibt das Makro zusätzlich die Information an die Registerallokation, dass Sie gedenkt, das Register in dem die rechte Seite geladen (reg_rhs) ist, zu modifizieren. Die eigentliche Makro-Sequenz besteht nur aus der Instruktion "add", welche in den Assembler ausgegeben bzw. emittiert wird. Am Ende kommuniziert die Makrosequenz, dass die Zielvariable (instr.dst) in reg_rhs zu finden ist.

Um die Integration von Makroexpansion und Registerallokator vollends zu verstehen, schauen wir uns die API des Registerallokators an. In einer funktionalen Hierarchie ist der Registerallokator vollständig abhängig von der Makroexpansion. Dies bedeutet, dass die Registerallokation niemals von alleine tätig wird, sondern an neuralgischen Stellen aufgerufen wird, um Variablen zu laden bzw. ihr die Chance gibt, sich mit der Maschinencodeerzeugung zu synchronisieren.

Durch drei Hooks, die jeweils vor der Maschinencodeerzeugung für eine Funktion, einen Basisblock oder eine einzelne Instruktion ausgeführt werden, erhält der Allokator die Möglichkeit, seine interne Buchführung entsprechend anzupassen. An diesen Stellen findet kein Informationsfluss vom Allokator zur Makroexpansion statt.

Anders Verhält es sich bei den Funktionen alloc_register(), load() und write(). Hier bekommt der Allokator einen konkreten Arbeitsauftrag von der Makroexpansion ein Register freizuräumen, eine Variable in ein Register zu transferieren, bzw. ein Ergebnis-Register mit einer IR-Variable zu verknüpfen. Dabei muss die Makroexpansion anfordern können, dass ein konkretes Register allokiert werden soll (reg, dst_reg), da manche Maschinenbefehle ihre Operanden in bestimmten Registern erwarten. Ohne diese Nebenbedingung darf der Allokator sich das Register frei aussuchen.

Graphiken und Animationen

PreviousNext

Bevor wir zur Funktionalität des Allokators kommen, schauen wir uns an auf welcher Datenbasis der Allokator arbeitetGrundprinzip, um informatische Lösungen zu verstehen: Fragen Sie danach, was der Zustand (Daten) ist und mit nach welchen Regeln dieser verarbeitet wird.. Der Zustand unseres verbesserten Allokators besteht aus drei Feldern pro Prozessor-Register, die während der Maschinencodeerzeugung kontinuierlich geupdatet werden.

Das free-Feld zeigt an, ob dieses Register für die aktuelle Instruktion bereits allokiert wurde. Da wir sicherstellen müssen, dass die beiden load() Befehle im Add-Makro unterschiedliche Register bekommen, brauchen wir dieses Boolesche Flag, um doppelte Herausgabe zu verhindern. Diese Felder werden vor jeder Instruktion im before_Instruction()-Hook zurück auf free=true gesetzt.

Das value-Feld zeigt an, ob gerade eine Variable in diesem Register "lebt", und wenn ja, welche. Zu Beginn eines Basisblocks wissen wir von keinem Register, dass es den aktuellen Wert einer Variable beinhaltet, weswegen diese Felder als leer initialisiert werden.

Das dirty-Feld zeigt an, dass der Stack-Slot der Variable und der Register-Inhalt gerade nicht synchronisiert sind und im Stack-Slot nur ein veralteter Wert zu finden ist. Dies bedeutet auch, dass der Wert im Register irgendwann in den Speicher zurückgeschrieben werden muss. Der Wert des Booleschen dirty-Flags ist nur dann von Relevanz, wenn dem Register eine IR-Variable in value zugeordnet ist.

Gehen wir nun die drei wichtigen API-Befehle (alloc_register(), load() und write()) durch:

Graphiken und Animationen

PreviousNext

Als erstes schauen wir uns alloc_register() an, mit dem die Makroexpansion ein leeres Register anfordern kann. Dies ist beispielsweise notwendig, wenn ein Wert aus dem "Nichts" erschaffen wird, wie dies, zum Beispiel, bei Reference der Fall ist. Das Ziel der Vergabe ist es, ein Register so zu wählen, dass im weiteren Verlauf so wenig Folgekosten wie möglich entstehen. Zwar kann unser Allokator nicht in die Zukunft schauen, aber wir können zumindest eine oberere Schranke angeben, welche maximalen Folgekosten im weiteren Verlauf des Basisblocks entstehen können. Der Allokator errechnet für jedes CPU-Register einen Score und gibt jenes Register mit dem günstigsten Score heraus; er nimmt eine priorisierte Allokation vor. Für jeden Aufruf von alloc_register() kommen natürlich nur jene Register in Frage, die noch nicht vergeben sind (free=yes).

Die niedrigsten Kosten fallen an, wenn wir ein leeres Register herausgeben. Da kein Wert aus dem Registersatz verdrängt wird, können in der Zukunft auch keine Kosten für ein Neu-Laden des Wertes auftauchen. Leere Register werden also mit der höchsten Priorität vergeben.

Als nächstes geben wir Register heraus, die zwar einen Wert beinhalten, dieser aber mit dem Stack-Slot synchronisiert sind. Für diese Register können im weiteren Verlauf nur kosten für das Neu-Laden des Wertes anfallen, wenn dieser von einem anderen Befehl noch einmal benötigt werden sollte; es fällt maximal ein Speicher-Register-Transfer an. Wenn dieses Register herausgegeben wird, wird die Bindung zwischen Register und IR-Variable aufgehoben (value=None).

Der teuerste Fall tritt ein, wenn wir ein Register herausgeben, das einen noch nicht synchronisierten Wert beinhaltet (dirty=yes). In dieser Situation kommen auf jeden Fall Kosten für die Spill-Operation zusammen und es kann zusätzlich in der Zukunft dazu kommen, dass wir den Wert neu laden müssen. Im schlimmsten Fall zieht die Vergabe dieses Registers also zwei Register-Speicher-Transfers hinter sich her. Wir sollten diese Register also nur dann Herausgeben, wenn kein anderes Register mehr frei ist, oder die Makroexpansion ganz explizit nach diesem Register gefragt hat (alloc_register(reg="ecx")).

Graphiken und Animationen

PreviousNext

Am Ende eines Makroexpansion wird häufig angewiesen, dass das Ergebnis, was nun in einem der allokierten Register vorliegt, in eine IR-Variable geschrieben werden soll. Dabei geht unser Allokator den Weg, dass wir den Wert nicht sofort in den Stack-Slot schreiben, sondern nur ab sofort alle Zugriffe auf die IR-Variable aus dem angegebenen Register bedienen. Dazu setzen wir das value-Feld auf die entsprechende Zielvariable und vermerken, dass Registerinhalt und Stack-Slot gerade nicht übereinstimmen. Das Zurückschreiben geschieht dann zu einem späteren Zeitpunkt.

Graphiken und Animationen

PreviousNext

Der load()-Befehl unseres Allokators ist der spannendste Teil der verfügbaren API. Hier verwenden wir die Buchhaltung, die wir über die Registerinhalte führen, um Ladebefehle zu sparen, wenn Werte bereits im Register-"Cache" verfügbar sind. Dabei weist uns die Makroexpansion an, eine gewisse IR-Variable (src) in ein Register zu laden. Hierbei unterscheiden wir zwischen mehreren Fällen, abhängig davon, wie der aktuelle Allokatorzustand aussieht:

Findet sich die zu ladende Variable in keinem Register (load(z)), so allokieren wir mittels alloc_register() ein neues Register und emittieren einen Ladebefehl, der die Variable aus ihrem Stack-Slot in das Register transferiert.

Spannend wird es, wenn die Variable bereits in einem Register lebt.Dieser ist einer der Knackpunkte des Registerallokators mit Gedächtnis. Wenn die Variable bereits geladen ist und das Register mit dem Stack-Slot synchronisiert ist, geben wir das Register (ebx) einfach heraus. Erst wenn Register als dreckig markiert sind, müssen wir unterscheiden, was die Makroexpansion mit dem Register vorhat: Will die Expansion das Register mit dem Variablenwert nur lesen, so können wir dreckige Register einfach herausgeben. Will die Makroexpansion nicht nur den Wert einer Variable haben, sondern darüber hinaus das Register auch zum rechnen bzw. für das Ergebnis verwenden, so müssen wir dreckige Register zuerst durch einen Spill-Befehl mit dem entsprechenden Stack-Slot synchronisieren. Würden wir das dreckige Register nicht vorher in den Variablen-Slot zurückschreiben, würden der aktuellste Wert der Variable verloren gehen.

Neben diesen vier Fällen gibt es noch einige Sonderfälle, wenn der Aufrufer von load() ein konkretes Register angefordert hat. In diesem Fall kann es sich lohnen, wenn ein Wert bereits in einem anderen Register geladen ist, den Inhalt beider Register zu tauschen (xchg) Befehl. Falls Sie weitergehendes Interesse an diesen Sonderfällen haben, können Sie diese im Übungsübersetzer anschauen.

Graphiken und Animationen

PreviousNext

Zuletzt müssen wir noch einige Situationen behandeln, die besonderer Behandlung durch den Allokator bedürfen. Informiert wird der Allokator über diese Situationen durch die bereits erwähnten Hooks.

Zum einen ist eine Registervergabe, die Basisblockgrenzen überschreitet, viel schwieriger als eine blocklokale Vergabe. Wieder haben wir hier das Problem, dass nur die Registerbelegungen, die in allen Vorgängerknoten konsistent sind, über Blockgrenzen hinweg Gültigkeit haben. Anders ausgedrückt: Eine Variable muss am Ende aller Vorgängerknoten im gleichen Register geladen sein, um bereits vor der ersten Instruktion eines Blocks als geladen zu gelten. Wir machen es uns hier einfach und werfen vor jedem Block einfach den gesamten Allokatorzustand weg.

Ein anderes Problem sind Funktionsaufrufe. Da eine Funktion nur die Calle-saved Register über einen Funktionsaufruf bewahrt, müssen wir bei einem Call-Befehl alle Register, deren Inhalt potentiell vernichtet wird, invalidieren. Dazu gehört, dass dreckige Register vorher rausgeschrieben und die Kopplung zwischen Register und IR-Variable aufgehoben werden muss. Um auf Nummer sicher zu gehen, werfen wir an dieser Stelle ebenfalls den gesamten Allokator-Zustand weg und tun so, als würde nach dem Call ein neuer Basisblock beginnen.

Ebenfalls kommen wir an dieser Stelle wieder mit dem Alias-Problem in Berührung: Eine Referenz auf eine lokale IR-Variable wird auf der Maschinencodeebene zu einem Zeiger auf den entsprechenden Stack-Slot. Daher kann Store-Befehl dazu führen, dass der Stack-Slot einer Variable plötzlich einen aktuelleren Wert enthält als das Register. Unser Cache wurde also "hintenrum" invalidiert. Um dieses Problem zu behandeln, werfen wir bei jedem Store alle Variablen aus unserer Buchhaltung, für die irgendwo in der Funktion eine Referenz erzeugt worden ist. Auf diese Weise verhindern wir, dass wir aus einem Register einen veralteten Wert für gültig halten.

Trotz aller dieser konservativen Annahmen und das häufige Wegwerfen des Allokator-Zustandes, hat unser verbesserter Allokator bereits einen erheblichen Einfluss auf die Performance von Programmen. Um Ihnen dies zu verdeutlichen, habe ich einen iterativen Fibonacci einmal mit der Minimallösung und einmal mit der verbesserten Registervergabe übersetzt. Dabei kommt bereits ein gewaltige Verbesserung von 36 Prozent heraus und unser Übungsübersetzer kommt in die Region von gcc, wenn dieser ohne Optimierungen gestartet wird. Allerdings sehen Sie auch, dass GCC noch einiges aus einem solchen iterativen Fibonacci herausholt. Diese Verbesserungen stammen sogar hauptsächlich aus der Registervergabe, da die innere Schleife der Fibonacci-Berechnung gänzlich in Registern stattfinden kann und ohne Speicheroperationen auskommt.

Graphiken und Animationen

PreviousNext

Mit Makroexpansion und Registervergabe haben wir jetzt alle Bausteine zusammen, um einen Übersetzer zu bauen, der aus dem Quellcode ein Stück Assembler-Programm für einen konkreten Prozessor erstelltEr herrscht große Freude allerorten!. Aber damit sind wir eigentlich noch lange nicht fertig, denn Prozessoren führen, wie wir in der ersten Vorlesung gelernt haben, keinen Assembler aus, sondern binär-codierte Maschinenbefehle aus dem Speicher. Daher müssen wir noch kurz besprechen, was nach dem Übersetzer kommt, um ein vollständiges Bild zu bekommen.

Diskutieren werden wir diesen weiteren Lebenslauf unseres Programms anhand es ELF-Dateiformats, welches unter Linux verwendet wird, um bereits übersetzte Programme und Programmfragmente zu speichern, und welche auch die Basis für die Ausführung eines Programms im Rahmen eines Prozesses darstelltSollte Ihnen der Unterschied zwischen Programm und Prozess nicht klar sein, schauen Sie sich noch einmal die zugehörigen Folien in der Veranstaltung "Grundlagen der Betriebssysteme" an.. ELF ist also der zentrale Angelpunkt, um binär-codierten Maschinencode zu speichern und zur Ausführung zu bringen.

ELF ist auch eng verbunden mit der separaten Übersetzung von Quellcodedateien. Dabei wird der Übersetzer für mehrere Quelldateien separat aufgerufen und mit dem Zwischenschritt über den Assembler eine Objekt-Datei erstellt. Diese Objektdateien, die bereits Binärdaten enthalten und dem ELF-Format entsprechen, werden dann vom Linker zu einer großen ELF-Datei zusammengebunden. Dabei werden symbolische Referenzen zwischen den Objektdateien aufgelöst, sodass es möglich ist, eine Funktion, die in einer anderen Objekt-Datei definiert ist, aufzurufen.

Ebenfalls spielt das ELF-Format eine zentrale Rolle für die gemeinsame Verwendung von Bibliotheken. Durch diese "Shared Libraries" kann Binärcode in mehreren Programmen und Prozessen verwenden werden, ohne ihn mehrfach auf Platte bzw. im RAM zu halten. Die Verbindung zu ELF ist, dass auch diese geteilten Bibliotheken im ELF-Format gespeichert sind.

Aber was ist dieses ELF? ELF ist ein Dateiformat, das nicht nur Binärcode beinhaltet, sondern auch noch zusätzliche Metadaten speichert. Zum Beispiel geben Symbole in einem ELF einem Byte einen "symbolischen Namen", welcher an anderer Stelle im ELF, oder in einem anderen ELF referenziert werden kann. Ein sehr hübscher graphischer Überblick über das ELF Dateiformat wurde von Ange Albertini angefertigt. Wichtig an ELF ist, dass die Metadaten zwei Sichten auf die enthaltenen Binärdaten beinhalten: den Link- und den Load View. Beide schauen wir uns nun an.

Graphiken und Animationen

PreviousNext

Zuerst betrachten wir den Link View der, wie der Name es andeutet, beim Linken von mehreren Objektdateien zu einem ausführbaren Programm verwendet wird. Erzeugt werden die Objektdateien vom Assembler, der aus den MnemonicsDas Wort lässt sich in etwa mit Merkspruch übersetzen und es ist selbst das genaue Gegenteil von dem, was es bedeutet. Ich finde es überhaupt nicht einfach zu merken. Binärcode erstellt. Neben den als Maschinenbefehle kodierten Assemblerzeilen gibt es auch noch Pseudo-Instruktionen, die die Erzeugung der ELF-Datei steuern. So gibt der Pseudobefehl .text an, dass ab nun Code kommt, während .data angibt, dass nun Daten folgen. Außerdem beinhaltet Assembler symbolische Namen (main, foo), die der Prozessor nicht unterstützt, und die daher in des ELFs landen müssen. Der Link-View besteht hauptsächlich aus drei wichtigen Elementen: Sektionen, Symbole und Relokationen.

Sektionen beinhalten die eigentlichen Binärdaten, die im Fall der Text-Sektion Maschinenbefehle sind, und im Falle der Daten-Sektion vorinitialisierte globale Variablen. Sektionen haben also, in der ELF-Datei, einen Anfang, eine Länge und einen Namen. Außerdem hat jede Sektion noch Flags, die angeben, ob der Inhalt der Sektion einmal in den Prozess geladen werden soll (A), dort ausführbar ist (X) oder geschrieben werden soll (W). Da der Assembler noch nicht alle symbolischen Referenzen auflösen kann (z.B. zu Funktionen aus anderen Objekt-Dateien), lässt er an entsprechender Stelle Platzhalter, die vom Linker aufgefüllt werden. Sie sollten einmal hergehen und eine Objektdatei mittels readelf -a (Metadaten) objdump -D (Disassembly) dekodieren, um ein Gefühl für den Inhalt dieser Sektionen zu bekommen.

Neben der eigentlichen Nutzlast, die in Sektionen gespeichert ist, gibt es noch die SymboltabelleTechnisch gesehen ist die Symboltabelle auch eine Sektion, die allerdings nicht in den Prozess geladen wird. Aber zum Erklären ist es einfacher hier einen strikten Unterschied zu postulieren.. In dieser sind symbolische Namen deklariert. Wenn diese in der ELF-Datei definiert sind, so referenziert ein Symbol ein bestimmtes Byte in einer der Sektionen. So zeigt das Symbol main in die Text-Sektion (T) auf das Byte mit dem Wert 0x55, was dem IA-32 Befehl push %ebp entspricht und den Beginn der Funktion markiert. Aber ein Symbol kann auch noch undefiniert (U) sein, wie das bei fib der Fall ist. Eine solche Situation zeigt an, dass das Symbol in einer anderen Objektdatei definiert sein muss. Die Auflösung der undefinierten Symbole übernimmt der Linker. Um die Symbole einer ELF-Datei zu betrachten, rufen Sie einmal das Tool nm auf einer Objektdatei auf.

Außerdem gibt es noch die Liste der Relokationen. Diese Relokationen sind Anweisungen wie der Binärcode beim Linken bzw. beim Laden verändert werden muss. So enthält eine Objekt-Datei für jede Verwendung eines undefinierten Symbols eine Relokation, die das undefinierte Symbol mit der Verwendungsstelle verbindet. Steht irgendwann die Adresse eines Symbols fest, so wird die referenzierte Lücke entsprechend umgebogen. Da manche Platzhalter eine relative (Funktionsaufrufe auf IA-32 sind Funktionsrelativ) und manche eine absolute Adressierung (Referenzerzeugung einer Variable) verlangen, hat jede Relokation noch einen Typ, der angibt, wie die Adresse des Symbols in die Binärdaten hineingepatcht werden soll.

Relokationen spielen sowohl beim Linken als auch beim Laden eine Rolle. Wenn ein Programm es erlauben soll, an unterschiedliche Stellen in den RAM geladen zu werden, so müssen alle Codestellen, die eine absolute Adressierung verlangen, entsprechend angepasst werden. Insbesondere bei geteilten Bibliotheken spielen diese Run-Time Relocations eine große Rolle.

Was geschieht nun also beim Linken mehrerer Objektdateien? Wir rufen den Linker mit mehreren Objektdateien (main.o, foo.o) auf. Dieser sammelt Sektionen gleichen Namens ein und hängt diese im Ergebnis-ELF hintereinander. Wichtig zu verstehen ist, dass nicht einzelne Funktionen die Granularität des Linkers ist, sondern ganze Sektionen.

Nachdem die Sektionen gesammelt und verbunden sind, wird auch die Symboltabelle vereinigt. Dabei werden undefinierte Symbole, soweit möglich, durch definierte Symbole aus anderen Objekt-Dateien (oder aus Bibliotheken) aufgelöst. Soll am Ende eine ausführbare Datei entstehen, darf kein Symbol unaufgelöst bleiben. Ist dies doch der Fall, kommt es zu einem Linker-Fehler.

Zusätzlich werden beim Linken alle Relokationen aufgelöst, die auf nun definierte Symbole zeigen. Dazu modifiziert der Linker die Platzhalter in den Sektionen entsprechend des Relokationstyps und des Symbolwertes. Betrachten Sie sich hierzu die beiden Relokationen: Beides sind PC-relative Relokationen (R_386_PC32), die das Symbol fib referenzierene8 xx xx xx xx ist ein call-Befehl. Die obere Lücke ist in main() und führt daher einen Sprung nach vorne (um 5 Bytes aus), während die zweite Lücke ein PC-relativ nach hinten springt (der Rekursionsschritt). Kann eine Relokation bereits vollständig beim Linken durchgeführt werden, so müssen wir sie nicht in die ausführbare Datei übernehmen.

Graphiken und Animationen

PreviousNext

Die zweite Sicht auf eine ELF-Datei ist die Load-View. Diese wird beim Laden eines Programms in den Adressraum eines Prozesses verwendet. Dabei werden völlig andere Metadaten verwendet als beim Linken, was es auch erlaubt, die Metadaten über Sektionen und Symbole aus der ELF-Datei zu entfernen. Dieses "strippen" von Binärdateien wird verwendet, um kleinere Programme zu erzeugen, aber auch, um Informationen über die Programmstruktur vor einem Reverse-Engineer zu verheimlichen. Daher wird Ihnen nm /bin/bash nur nm: /bin/bash no symbols ausgeben.

Aber zurück zum Ladeprozess: Dieser basiert auf Segmenten, die eine Abbildung von einem Abschnitt der ELF-Datei und einem Speicherbereich im Adressraum vornehmen. Jedes Segment, welches als "zu laden" markiert ist, wird beim Ladeprozess aus der ELF-Datei in den Speicher eines Prozesses geladen. Dabei trägt ein Segment wiederum Metadaten: So kann ein Segment angeben, an eine fixe Adresse geladen zu werden oder besondere Zugriffsrechte zu bekommen. So muss der Zielbereich eines Segments, welches ausführbaren Code enthält, nach dem Laden beim Betriebssystem als ausführbar markiert werden, da es ansonsten zu einem Segmentation Fault kommt.

Auf der Seite des ELFs besteht ein Segment aus einem Offset, das relativ zum Beginn der ELF-Datei berechnet wird, und der Länge in der Datei (FileSiz). Auf der Abbildungsseite kann ein Segment eine virtuelle Adresse (VirtAddr) vorgeben, an die es geladen werden will, eine Abbildungslänge (MemSiz) und besagte Segment-Metadaten (Flg)

Ist die Abbildungslänge länger als die Dateilänge, wird beim Laden mit Nullen aufgefüllt. Auf diese Weise ist auch das BSS Segment implementiert: Beim Segment, das die Daten-Sektion enthält, gilt FileSiz < MemSize.

Der Loader iteriert über die Segmente und fordert entsprechende Bereiche im Adressraum an. In diese Bereiche werden dann die Daten aus der ELF Datei, entsprechend der Segmente, kopiert und beim Betriebssystem entsprechend als ausführbar oder schreibbar markiert. Nach dem Ladeprozess springt der Loader an den Einstiegspunkt, der ebenfalls in den ELF-Metadaten gespeichert wird.

Alles in allem ist ein ELF-Loader ein relativ einfaches Stück Code, das in einigen Zeilen und mit einigen Kopieroperationen bereits eine Datei zur Ausführung bringen kann. Komplizierter wird es erst, wenn die Binärdatei an unterschiedlichen Stellen geladen werden kann oder es geteilte Bibliotheken gibt.

Wie bereits angedeutet, geteilte Bibliotheken sind ein gutes Mittel, um Platz, sowohl auf der Platte als auch im RAM, zu sparen. Dies funktioniert indem Shared Libraries Code enthalten, der von mehreren Programmen referenziert werden kann. Beim Laden wird dann nicht nur das ausführbare Hauptprogramm geladen, sondern auch noch alle referenzierten Bibliotheken. Der Loader löst dann alle Querverbindungen zwischen Bibliothek und Hauptprogramm auf, sodass es so wirkt, als hätten wir den Inhalt der Bibliothek im Linkprozess mit in das Binärprogramm kopiert.

Ein weiterer Vorteil von geteilten Bibliotheken ist, dass wir bei einem Update nur die Bibliothek updaten müssen, um eine ganze Reihe von Programmen mit dem Update zu versorgen. Dieser Vorteil, ist allerdings auch ein Nachteil, wenn ein System Programme enthält, welche die selbe Bibliothek in unterschiedlichen Versionen erwarten.

Wie sich mit geteilten Bibliotheken Platz auf der Platte sparen lässt, ist einigermaßen naheliegend: Der Code der Bibliothek liegt nur einmal auf Platte und nicht zig mal für jedes Binärprogramm, was ihn verwendet. Aber wie lässt sich durch geteilte Bibliotheken Platz im RAM sparen, wo die Bibliothek doch in unterschiedlichen Adressräumen zugreifbar ist. Die Antwort liegt darin zuzugeben, dass Segmente beim Laden nicht wirklich in den Speicher kopiert werden, sondern der Abschnitt im ELF nur mittels Speichervirtualisierung eingeblendet wird. Die gleiche physikalische Seite, wie sie im RAM-Riegel liegt, wird also in mehreren Prozessen, teilweise an unterschiedlichen virtuellen Adressen, sichtbar. Daher muss der Code in geteilten Bibliotheken auch Unabhängig von seiner Ladeadresse sein, was mit diversen technischen Tricks erreicht werden kann.

Auf Ebene der ELF-Datei funktionieren Bibliotheken so, dass das Hauptprogramm und jede Bibliothek eine Liste der benötigten Bibliotheken enthält. Außerdem sind in den ELF-Dateien auch noch alle importierten und exportierten dynamischen Symbolen vermerkt, die als Referenzen vom Loader aufgelöst werden. Eine Übersicht über die benötigten Bibliotheken einer Binärdatei erhalten Sie mit dem Werkzeug ldd:

$ ldd /bin/bash
	linux-vdso.so.1 (0x00007ffde376d000)
	libtinfo.so.6 => /lib/x86_64-linux-gnu/libtinfo.so.6 (0x00007ff34a6c6000)
	libdl.so.2 => /lib/x86_64-linux-gnu/libdl.so.2 (0x00007ff34a6c1000)
	libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007ff34a501000)
	/lib64/ld-linux-x86-64.so.2 (0x00007ff34a85e000)

Hier sehen wir, dass fünf Shared Libraries bei Start einer Bash-Shell geladen werden. Dabei gibt es in dieser Ausgabe zwei besondere Bibliotheken: Die linux-vdso.so ist eine Bibliothek, die vom Betriebssystemkern stammt und schnellen sehr ausgewählte Kerndatenstrukturen zulässtWikipedia: VDSO. Die andere ist die ld-linux.so (letzte Zeile). Diese ist das Ladeprogramm selbst und hat bei der GNU C Bibliothek die Besonderheit, sowohl eine geteilte Bibliothek als auch eine ausführbare Datei zu sein. Überzeugen Sie sich selbst davon: Finden Sie den Pfad Ihrer ld-linux.so heraus und führen Sie den Loader einmal von Hand aus. Ohne Argumente wird es Sie nur über seine Fähigkeiten in einer Hilfemeldung in Kenntnis setzen.