Wie Compiler und Linker arbeiten

Obwohl es um Compiler und Linker geht, beginnen wir erst mal mit Assembler. Die frühen Assembler waren in der Lage, direkt Maschinenkode zu erzeugen, und nichts anderes. Da gab es nichts zu linken. Für wirklich kleine Mikrocontroller wie PIC immer noch das beste, weil es bei linkbaren Assembler erhebliche Einschränkungen in der Kode-Gestaltung gibt. So kann man bspw. nicht mit kurzen Sprüngen in ein anderes Objektmodul springen, sonden muss die längstmögliche Form kodieren:

Alle modernen Assembler erzeugen sogenannten Objektkode. Das hat nichts mit Klassen und Objekten von C++ zu tun sondern ist ein Dateiformat, welches:

Ein solches SEGMENT enthält bereits den fertigen Maschinenkode, allerdings mit freien Stellen (zumeist Nullen) an den Stellen, an denen die Werte importierter Symbole eingetragen werden müssen. Wie genau der Patch vor sich geht ist maschinenabhängig und muss irgendwie in der Import-Symboltabelle vermerkt sein, denn es gibt absolute und relative Adressen, kurze und lange Sprünge, NEAR- und FAR-Prozeduraufrufe, getrennte Low- und High-Teile bei Mikrocontrollern.

Erstellt man ein Programm aus genau einer Assemblerdatei, darf diese keine importierten Symbole aufweisen, oder die importierten Symbole werden vom Linker (irgendwie, über die Kommandozeile oder ein Linkerskript) bereitgestellt.

Der Linker reloziert dann das Kodesegment, das ist das SEGMENT mit dem Namen ".TEXT", auf die Zielsystem-Basisadresse (bei Mikrocontrollern meistens 0, bei Win32 bei 4 MiB) und legt die initialisierten Daten, das ist das SEGMENT mit dem Namen ".DATA" dahinter. Übleicherweise dahinter noch das SEGMENT ".BSS", welches leer ist aber eine bestimmte Größe hat. Das sind die uninitialisierten Daten. Kreuzweise Referenzen zwischen ".TEXT" und ".DATA" werden durch Patch der jeweiligen Segmente aufgelöst. Der häufigste Fall ist das Festlegen von Adressen im Kodesegment zum Zugriff auf Daten, aber auch Daten können in Kode verweisen, etwa bei initialisierten Kodezeigern. Daten, die auf Daten zeigen, werden bereits vom Assembler aufgelöst.

Warum die Segmente genau so (oder anders) heißen ist im Assembler und Linker eingebaut und/oder mittels Pseudobefehlen und Linkerskript steuerbar. So kann man beim X86-Assembler mit

	.code

mitteilen, dass alles nachfolgende in das Segment mit dem Namen ".TEXT" ausgegeben wird. Ob man da Maschinenkode oder Daten hineinwirft ist dem Assembler und dem Linker völlig egal. Das wird dann erst beim Ausführen der EXE-Datei wichtig!

Im Assembler können wir jederzeit zwischen .code und .data hin- und herschalten, der Assembler sortiert den entstehenden Output bereits automatisch. Dabei beachtet er Ausrichtungsregeln (Alignment) automatisch, so dass jeder dieser Subabschnitte an einer geeigneten Adresse beginnt, falls der vorhergehende nicht „glatt“ war. Womit der Assembler die Lücken auffüllt ist seine Geschmackssache oder angebbar, häufig Nullen oder (im X86-Kodesegment) 0xCC für den Int3-Breakpoint-Interrupt.

Genau ein bestimmtes Symbol sollte der X86-Assembler exportieren, nämlich den Programmanfang. Das ist ein gesondertes Symbol (bspw. mit leerem Namen), das der Linker dann in den EXE-Header eintragen kann, wo das Programm beginnt. Bei Mikrocontrollern geht das so nicht, hier geht das Programm immer von vorn los.

Bei Microsoft haben Objektdateien die Endung .obj, bei Gnu und Linux die Endung .o.

Der C- und C++-Compiler

Um es wirklich kurz zu fassen: C- und C++-Compiler erstellen (für Menschen unleserlichen) Assemblerkode, der dann dem Assembler zum Fraß vorgeworfen wird. Selbst wenn dem (bei Microsoft) nicht so ist, bei Gnu-C (gcc) ist es nach wie vor so, und man braucht sich's gar nicht anders zu denken.

Das Umlenken von Kode und Daten in andere Segmente geschieht über #pragma-Anweisungen (Microsoft) oder __attribute__(()) (gcc) und ist nicht portabel.

Was enthält Debuginformation?
Debuginformation wird vom Assembler oder Compiler in der Regel automatisch generiert und bläht die Objektdateien auf (=unkritisch). Bei gcc landet diese in einem weiteren Segment. Im einfachsten Fall enthält diese eine Zuordnung von Quelltextzeilennummer und Kodeadresse. Damit kann der Debugger die Quelltextzeile zu einer Kodeadresse (ungefähr) zuordnen. Im allgemeinen Fall werden auch die Zuordnungen zwischen Adressen, Stackadressen oder Registern zu Symbolen und deren Gültigkeitsbereiche (Scopes) abgelegt. Am kompliziertesten ist korrekte Debuginformation für Inline-Funktionen, Lambdas, C++-Templates und hoher Optimierung (bspw. Register-Cache von Speicher-Variablen, vertauschte Kode-Reihenfolge, Zusammenfassung gemeinsamer Funktions-Enden) zu realisieren. Daher funktioniert symbolisches Debuggen oft nur ohne derartige Optimierung.
Debug-Information bläht den Ergebnis-Kode nicht auf und kann mit strip entfernt werden.

Was enthält Debug-Kode?
Im Gegensatz zu Debuginformation ist Debug-Kode wenig optimierter und mit zusätzlichen Anweisungen zur Fehlerprüfung versehener Maschinenkode. Dieser bläht auch das Endprodukt auf und macht es langsamer und sollte nie in einem Endprodukt erscheinen. Bestimmte Kompiler-Optionen sowie (Microsoft) das Symbol _DEBUG schalten auf das Generieren von Debug-Kode um, wobei _DEBUG vor allem vom Anwender für bedingte Kompilierung verwendet wird, etwa für OutputDebugString(). Kode zum „Verändern und fortfahren“ (das betrifft nur ausführbare Dateien) enthält sogar extra Platz zwischen den gelinkten Objektmodulen, damit beim Patch eines einzelnen Objekts leichte Größenveränderungen vertragen werden, ohne das sonstige Speicherabbild überschreiben zu müssen (abgesehen von Referenzen). Da solcherart Kode oftmals funktionsweise in Objektdateien rutscht (siehe unten), befindet sich diese Lücke zwischen jeder Funktion, und es braucht nur eine Funktion ersetzt werden sowie keine Referenz.

Wie löst der Compiler Rechenoperatoren auf?
Normale Funktionen wie sin() sind nichts besonderes, aber der Stein kommt ins Rollen bei normalen Operatoren + - * / %. Steht für den Datentyp (etwa float) nicht gleich etwas inline kompilierbares zur Verfügung, werden Funktionen mit kryptischem, bisweilen in C ungültigen Namen aus der Standardbibliothek referenziert und vom Linker (hoffentlich) gefunden und eingebunden. Diese Namen und deren Aufrufparameter (nicht immer nach Konvention) müssen zwischen C-Compiler und Standardbibliothek vereinbart sein und passen! Daher kann man Standardbibliothek und Compiler nicht einfach trennen. Zumindest nicht, wenn man Mathematik benötigt.

Der Linker

Bei dem oben geschilderten Beispiel arbeitet der Linker genau eine Objektdatei ab. Das ist natürlich ein unverständlicher Schritt, früher ging es ja auch ohne.

Nehmen wir an, dass das Programm 2 Assemblerquelltexte hat. Der kleinere Quelltext implementiert bspw. eine erweiterte Version von printf(), die Integer-NaNs verarbeitet und Kommastellen für Integerzahlen ausgibt, also Festkommazahlen. Die entstehende Objektdatei exportiert die Symbole "_printf" und "_vprintf" und importiert "_putchar" zum einzelzeichenweisen Ausgabe. (Die Anstriche sind üblich für C unter Windows. Ich verwende sie hier, um anzuzeigen, dass diese Funktionen C-konform sind.)

Der andere Quelltext exportiert "_putchar" und importiert "_printf". So kann der Linker beide Objektdateien verbinden. In welcher Reihenfolge ist vom Linker bzw. seiner Kommandozeile abhängig!! In einer EXE-Datei ist die Reihenfolge jedoch egal, da dann der Einsprungpunkt eben weiter vorn oder weiter hinten ist. Dass bei Mikrocontrollern kein Unsinn herauskommt muss man entweder durch die richtige Reihenfolge auf der Kommandozeile oder durch gesonderte Segmentnamen, die per Linkerskript nach vorn sortiert werden, sicherstellen. Bei den Gnu-Compilern wird so verfahren.

Was passiert, wenn "_vprintf" gar nicht referenziert wird?
Einbinden von Objektdateien ist eine Alles-Oder-Nichts-Entscheidung! Die Funktion wird eingebaut, auch wenn sie nicht referenziert wird. In diesem Fall macht das nichts (= bläht die EXE-Datei nicht auf), weil nahezu jede printf()-Implementierung intern vprintf() aufruft und nicht umgekehrt.
Diese Alles-Oder-Nichts-Entscheidung wird heutzutage aufgeweicht, indem der Compiler funktionsweise Assemblerdateien erzeugt und tatsächlich eine Archivdatei (= mehrere Objektdateien im Bundle) erzeugt.

Was passiert, wenn nur der „große“ Quelltext dem Linker übergeben wird?
Man würde erwarten, dass es eine Fehlermeldung „Unaufgelöstes Symbol "_printf"“ gibt. Stattdessen läuft der Linker in der Regel mit ein paar Warnungen durch! Das kommt daher, dass der Linker „insgeheim“ die C-Standardbibliothek dazulinkt, wo das Symbol "_printf" exportiert wird. Allerdings kann diese dann kein Integer-Festkomma, und der Output leidet unter Code Bloat, je nach Qualität der _printf-Implementierung. Abschalten lässt sich das automatische Hinzuziehen der Standardbibliothek mit /NODEFAULTLIB.

Wie bearbeitet der Linker verschiedene Aufrufkonventionen? Ich finde es ja besser, wenn mein "_printf" den String-Template in SI bereithält statt auf dem Stack.
Der Linker tut gar nichts!!! Er kennt nur Namen und Zahlen (letztere sind meist Adressen). Es ist Aufgabe des Programmierers, die Schnittstelle passend zu machen und zu halten! Unter Windows werden Symbole mit verschiedenen Aufrufkonventionen verschieden „garniert“ svw. exportiert:

Was passiert, wenn nur der „kleine“ Quelltext dem Linker übergeben wird?
Man würde erwarten, dass es eine Fehlermeldung „Unaufgelöstes Symbol "_putchar"“ gibt. Stattdessen beschwert er sich über das fehlende Symbol "_main"! Das kommt daher, dass der Linker „insgeheim“ die C-Standardbibliothek dazulinkt. Diese definiert einen Eintrittspunkt und will stattdessen "_main" (das C-Hauptprogramm) referenzieren und aufrufen. Abschalten lässt sich das automatische Hinzuziehen der Standardbibliothek mit /NODEFAULTLIB.

Was passiert, wenn es mehrere Symbole mit gleichem Namen gibt?
Das ist der Fall, wenn man beide o.g. Programme verbindet und die Standardbibliothek ins Spiel kommt. Entweder man bekommt eine Warnung, und das jeweils erste Symbol gewinnt (die Standardbibliothek ist stets „hinten“), oder es gibt gar eine Fehlermeldung.

Wenn mehrere Symbole mit gleichem Namen gewünscht sind?
Dieser Sonderfall ersetzt faktisch virtuelle Methodenzeiger: Es ist die Standardimplementierung von Interruptroutinen under avr-gcc: Die Laufzeitbibliothek stellt einfach für alle Interruptvektoren einen Handler zur Verfügung, der zum Reset-Vektor springt. Eigene Handler verwenden den gleichen Namen. Damit dieser bei der Namensauflösung „gewinnt“ sind die Namen der Laufzeitbibliothek allesamt „weak“, also schwach.
Unter Borland- und Microsoft-Linkern sind „weak“-Symbole unbekannt.
Eine Verkettung oder gar Parallel-Abarbeitung von Funkionen ist damit weder möglich noch gewollt.

Die Bibliothek

Um es kurz zu machen, eine Bibliothek ist nichts anderes als eine Zusammenfassung (vergleichbar mit einem ZIP- oder tar-Archiv) von mehreren (durchaus tausenden) Objektdateien. Diese Anordnung ist nicht hierarchisch, alle diese Objektdateien liegen hintereinander, sodass deren Reihenfolge auch die Reihenfolge in der fertigen ausführbaren Datei bestimmt.

Bei Microsoft haben Bibliotheksdateien die Endung .lib (für „library“ = Bibliothek), bei Gnu und Linux die Endung .a (für „Archiv“).

Man kann Bibliotheken bspw. mit ranlib selbst erstellen, aber das wird eher selten vorkommen. Zumeist wird man Bibliotheken verwenden.

Anders als bei auf der Kommandozeile angegebenen Objektdateien entnimmt der Linker nur die notwendigen Objektdateien aus der Bibliothek, um alle Symbole auflösen zu können. Alles andere lässt der Linker weg.

Wie schafft es der C-Compiler, nicht benötigte Funktionen, also toten Kode zu eliminieren?
Nun, ist eine Funktion mit static garniert, sollte sich der Compiler mit einer Warnung beschweren. Wenn nicht, wird sie per se in die Objektdatei geworfen und gelinkt und der tote Kode in die ausführbare Datei eingebaut.
Moderne C-Compiler können jedoch insgeheim direkt Bibliotheken erstellen, in denen sie Funktion für Funktion und Variable für Variable in einzelne Objektdateien packen. (Das was man früher für die Standardbibliothek mit hunderten oder tausenden C-Dateischnipseln machen musste: Jede Funktion in eine C-Datei.) Dann betrachtet sie der Linker wie eine Bibliothek und wirft bei Nichtreferenz den toten Kode und und tote Variablen heraus.

Binärdatei(en) einbinden

Bisweilen steht man vor dem oberflächlich trivialen Problem, eine Binärdatei in die ausführbare Datei zu inkludieren. Dafür gab es früher (bei Borland Pascal und Borland C++) binobj.exe. Diese erstellte eine Objektdatei mit einem einzigen Symbol, der dem angegebenen Dateinamen entsprach, und IMHO der Segmentbezeichnung .DATA.

Für Windows-Programme ist der richtige Weg, Binärdaten einzubinden, über eine Ressource. Seit Win32 werden die Binärdaten „gemappt“, d.h. in den linearen Adressraum eingeblendet und stehen ohne extra Ladeoperationen zur Verfügung.

Bei gcc gibt es dafür objcopy oder ähnliche Programme, mit deren kryptischer Kommandozeile dasselbe bewerkstelligen kann, üblicher ist aber der umständliche aber portable Weg, die Binärdatei in ein C-Bytearray umzuwandeln. Dem Linker direkt eine Binärdatei mitgeben zu können hat man beim Linker „vergessen“: Es gibt keine Kommandozeilen-Option dafür.

Ausführbare Datei

Man geht naiv davon aus, dass eine ausführbare Datei vom Betriebssystem einfach in den Speicher geladen und gestartet wird. So einfach war das nur bei CP/M, DOS und COM-Dateien: Die Lade- und Startadresse war stets 0x100, und mehr als 63¾ Kilobyte ging nicht. (Variable) Daten befanden sich stets hinter dem Kode. Da alles im RAM lag, war auch Kode variabel — also beschreibbar, fertig. Die C-Standardbibliothek hatte nur den .bss-Bereich zu löschen. Ob diese dann das Betriebssystem mit überschreibt (das bei CP/M ungeschützt „ganz hinten“ liegt) oder mit einer Fehlermeldung abbricht hängt von der Cleverness der Standardbibliothek ab.

Beim Mikrocontroller wird Kode üblicherweise vom Flash ausgeführt, und der RAM-Inhalt ist beim Start undefiniert. Dafür bindet die Standardbibliothek noch Kode dazu, den RAM mit Vorgaben aus dem Flash zu initialisieren (.data) und zu löschen (.bss), damit das C-Programm von mit 0 initialisierten statischen Variablen ausgehen darf. Die Initialisierungsdaten werden durch das Linkerskript hinter den Kode gesetzt und sind nicht für den Zugriff durch das Anwendungsprogramm bestimmt. Dieses Verfahren ist unabhängig davon, ob Harvard- oder Von-Neumann-Architektur vorliegt.

Ein Sonderfall ist beim Mikrocontroller CY7C68013A zu beobachten: Seine von-neumannisierte 8051-Architektur wird von einem seriellen EEPROM oder von USB gefüllt. Hier liegt demnach die Situation wie bei CP/M vor, nur dass der Kode bei Adresse 0 beginnt und auch Interruptvektoren beinhaltet.

Bei heute üblichen Betriebssystemen ist eine ausführbare Datei nicht mehr so viel anders als eine Objektdatei: Auch diese enthält exportierte und importierte Symbole, die der Lader auflösen muss. Der wesentliche Unterschied ist nur, dass importierte Symbole auch einen Dateinamen benennen, woher das Symbol kommen soll. Das Betriebssystem lädt schließlich den Kode in einen (idealerweise) schreibgeschützten Bereich, die Daten in einen Schreib-Lese-Bereich, löscht das .bss (schon aus Sicherheitsgründen, um nicht verwaiste Passwörter aufzufischen) und stellt im .bss Platz für den Stack des ersten Threads bereit. Wohlgemerkt, auch von allen DLLs, die die EXE referenziert. Wie dabei (bei mehreren Prozessen, die bspw. Kernel32.dll verwenden) RAM-speichersparend vorgegangen wird muss hierbei nicht interessieren: Das wird im wesentlichen über die Pagingeinheit realisiert.