Das Elend mit dem Linker

(und wie man sich dann doch mit ihm anfreundet)

Bernhard Heinloth

2022-06-16

In der 4. BST-Aufgabe wollen wir eigene Anwendungen getrennt vom Kernel übersetzen und isoliert ausführen. Um deren Entwicklung bequemer zu machen, soll es mit libsys eine minimale (statische!) Standard-Bibliothek geben.

_{Die Idee ist damit grundsätzlich ähnlich zur weit verbreiteten glibc, aber soll natürlich um Größenordnungen einfacher sein — der historisch gewachsene GNU Code ist eine unwartbare #ifdef-Hölle, weswegen inzwischen auch häufig (insbesondere im Forschungsbereich) auf kompakte & verständlichere Alternativen wie musl zurückgegriffen wird!}

Grundlagen

Ein Compiler übersetzt ein Hochsprachenprogramm (ggf. über den Zwischenschritt Assembler) in Maschinencode. Aus (ehemaligen) Performancegründen wird das in systemnahen Sprachen wie C & C++ heutzutage noch modulweise gemacht: Die .cc-Dateien werden einzeln in Objektdateien .o übersetzt — Änderungen an einer Datei führen also nicht zwingend dazu, dass alles neu übersetzt werden muss, sondern eben nur der modifizierte Teil. Als die CPUs noch langsamer waren, war das auch für kleine Projekte relevant, heute ist das maximal noch bei großen Projekten von Bedeutung.

Damit das funktionieren kann, muss der Compiler wissen, welche Funktionen es gibt, welche Parameter[typen] diese erwarten & was sie zurück geben — also die Signaturen (Funktionsdeklarationen). Analog gilt dies für (globale) Variablen, Strukturen usw. Dafür verwenden wir die Headerdatei (.h).

Der Compiler macht hierfür symbolische Verknüpfungen, gibt dabei an, welche Symbole er in der Objektdatei selbst anbietet (definiert) und wo & in welcher Form er im generierten Maschinencode ein externes (undefiniertes) Symbol — genauer: dessen Zieladresse — braucht.

Dabei entspricht in C der Funktions- oder Variablenname direkt dem Symbolnamen, in C++ muss (aufgrund der Möglichkeit Funktionen zu überladen) der Name noch mit weiteren Eigenschaften (z.B. Parametertypen) verwurschtelt werden.

Zudem teilt der Compiler den Maschinencode und die dazugehörigen Daten in Sektionen ein, unter anderem:

.text für den ausführbaren Maschinencode
.data für initialisierte Variablen (mit einem Wert ungleich 0)
.bss für mit 0 initialisierte Variablen [damit kann man später den Speicherverbrauch der Binärdatei optimieren]
.rodata für nur lesbare Variablen (Konstanten)

_{Das ist nur eine Konvention — es können beliebig weitere Sektionen erstellt werden, man kann dies auch selbst in den Quelltextdateien steuern!}

Am Ende, wenn wir alle Quelltextdateien im übersetzten Zustand vorliegen haben, muss es noch zusammen gebunden werden — was bekanntlich die Aufgabe vom Linker/Binder ist. Dieser braucht nun nicht zwingend ein Verständnis was der Code da jeweils tut, sondern Interessiert sich vereinfacht gesagt für zwei Dinge: die Symbole und die Sektionen.

Er geht der Reihe nach die Objektdateien durch, speichert sich in einer Datenstruktur (Hashmap) welche definierten Symbole er bis jetzt vorgefunden hat und ordnet diesen (Abhängig von den Sektionen in den sie liegen und was die Konfiguration dafür vorgibt) Adressen zu. Sollte er auf ein undefiniertes Symbol stoßen, schaut er in seiner Hashmap nach, und ersetzt es entweder mit der Adresse von dem Symbol — oder wirft einen Fehler, weil er auf ein ihm bisher unbekanntes Symbol gestoßen ist.

_{Das ist nun natürlich eine maximal vereinfachte Darstellung, denn mit positionsunabhängigen Code fügt der Linker durchaus eigene Sektionen wie die Global Offset Table ein, bei Binde-Zeit-Optimierungen (LTO) übernimmt er sogar die Aufgabe des Compilers und erstellt (emitiert) den Maschinencode — was effizienten Code bei deutlich höherer Laufzeit des Binders ermöglicht. Aber diese ganzen Themen sind für das grundlegende Verständnis erst einmal nicht weiter wichtig!}

Wenn der Linker aber alle Symbole findet, fällt (hoffentlich) eine ausführbare Datei heraus. Und genau um die geht es in dieser Aufgabe 🙂

Ausgangssituation

In user/app1/main.c schreiben wir unser erstes Programm — ein typisches hello-world-Beispiel:

#include <syscall.h>

extern "C" void main() {
    while(1) {
        sys_write(1, "Hallo Welt!\n", 12);
        sys_sleep(1000);
    }
}

Damit das laufen kann, haben wir in der libsys unsere Systemaufrufstümpfe (stubs) angelegt. Und da auch unser Standardbibliotheksordner bei include-Anweisungen aufgrund des Parameters -I ../../libsys in der Makefile durchsucht wird, können wir die Systemaufrufe dank der Deklarationen in der syscall.h bequem verwenden!

Randnotiz: Es ist in Ordnung, wenn die Systemaufrufnummer von nun an in zwei Dateien verwaltet werden: Einmal in der libsys und ein zweites Mal im Kernel bei den skeletons. Man könnte das zwar mit includes und Symlinks auch gemeinsam in einer Datei managen, aber macht es lieber (zumindest anfangs) so einfach wie möglich!

Das Benutzeranwendungslinkerskript

Wie in der Tafelübung erwähnt brauchen wir für C(++) Code erst einmal ein Linkerskript für die Anwendungen. Die können wir uns aus dem Kernel von compiler/sections.ld kopieren und passen das dann an:

unsere Einsprungsfunktion soll nun start sein
start im Userspace (bei 0x4000000 = 64 MB)
unnötige Sektionen (.boot und .setup_ap_seg) werden entfernt
ebenso brauchen wir die Source Code References (___KERNEL_START___ usw.) nicht mehr

Die Initialisierungsroutinen

Außerdem brauchen wir ebenfalls noch die Startup-Routinen für die Initialisierung. Da bedienen wir uns wieder beim Kernel und kopieren das aus compiler/libc.cc nach user/init.cc zusammen, zum Beispiel:

#ifdef __cplusplus
extern "C" {
#endif

extern void _init();
extern void _fini();
extern void main();

extern void(*__preinit_array_start[]) ();
extern void(*__preinit_array_end[]) ();
extern void(*__init_array_start[]) ();
extern void(*__init_array_end[]) ();
extern void(*__fini_array_start[]) ();
extern void(*__fini_array_end[]) ();

[[noreturn]] void start() {
    // Call constructors
    const unsigned int preinit_size = __preinit_array_end - __preinit_array_start;
    for (unsigned int i = 0; i != preinit_size; ++i)
        (*__preinit_array_start[i])();

    _init();

    const unsigned int init_size = __init_array_end - __init_array_start;
    for (unsigned int i = 0; i != init_size; ++i)
        (*__init_array_start[i])();

    // Call teh application
    main();

    // Call destructors
    const unsigned int fini_size = __fini_array_end - __fini_array_start;
    for (unsigned int i = 0; i != fini_size; ++i)
        (*__fini_array_start[i])();

    _fini();

    // Wait forever
    while(1) {}
}

#ifdef __cplusplus
}
#endif

Wozu wird das eigentlich gebraucht?

Nun, es kann zum Beispiel sein, dass nicht alle globalen Objekte zur Übersetzungszeit ausgewertet werden — einfaches (StuBS) Beispiel ist eine Instanz einer Klasse, welche im Konstruktor die Anzahl der aktiven CPU Kerne auswertet. Das muss zur Laufzeit geschehen, aber vor der eigentlichen main.

Der Gcc-Compiler kann übrigens auch mittels Funktionsattribut eine Ausführung während der Initialisierung ermöglichen:

__attribute__((constructor)) void foo() {
    sys_write(1, "bar\n", 4);
}

Der Übersetzer würde hierbei lediglich einen Zeiger auf foo in das Init-Array stecken (und im vorherigen Beispiel einen Zeiger auf den Konstruktor des Objekts), und unsere Initialisierungsroutinen kümmern sich um die Ausführung bevor das eigentliche Hauptprogramm (main) aufgerufen wird.

Objektdateien

Wenn wir die Datei mit den Initialisierungsroutinen nun zur init.o kompilieren (in Gcc mit dem Parameter -c, in der Makefile tools/build.mk wird das im Rezept $(BUILDDIR)/%.o gemacht), so kommt eine relozierbare Objektdatei raus.

Was heißt das?

Schauen wir uns mal den Assembler des übersetzte Objekt (mittels objdump -d user/.build/init.o) an:

0000000000000000 <start>:
   0:   f3 0f 1e fa             endbr64 
   4:   55                      push   %rbp
   5:   b8 00 00 00 00          mov    $0x0,%eax
   a:   53                      push   %rbx
   b:   48 2d 00 00 00 00       sub    $0x0,%rax
  11:   48 c1 f8 03             sar    $0x3,%rax
  15:   48 83 ec 08             sub    $0x8,%rsp
  19:   85 c0                   test   %eax,%eax
  1b:   74 18                   je     35 <start+0x35>
  1d:   8d 68 ff                lea    -0x1(%rax),%ebp
  20:   31 db                   xor    %ebx,%ebx
  22:   ff 14 dd 00 00 00 00    callq  *0x0(,%rbx,8)
  29:   48 89 d8                mov    %rbx,%rax
  29:   48 89 d8                mov    %rbx,%rax
  2c:   48 83 c3 01             add    $0x1,%rbx
  30:   48 39 e8                cmp    %rbp,%rax
  33:   75 ed                   jne    22 <start+0x22>
  35:   e8 00 00 00 00          callq  3a <start+0x3a>
  ...

Was man hier sieht:

start beginnt an Adresse 0
es sind insgesammt auffallend viele Nullen, egal ob an Adresse 6 (5 + 1 Byte), d (b + 2 Bytes) oder bei den callq ab Adresse 25 & 36…

Beides ist Aufgabe vom Linker: Adressen für Symbole zu vergeben und die Referenzen darauf anzupassen. Aber dazu fehlen noch weitere Informationen — allen voran, was überhaupt wohin zeigen soll.

Relokationen

Die Objektdatei liegt ja im ELF-Format vor, und da können mehr Sektionen drin sein — nicht nur der Code selbst. Wir lassen uns dazu mal die sogenannten Relokationen mittels readelf -r user/.build/init.o ausgeben — für uns ist nur .rela.text interessant:

 Relocation section '.rela.text' at offset 0xfd8 contains 12 entries:
  Offset          Info           Type           Sym. Value    Sym. Name + Addend
000000000006  00110000000a R_X86_64_32       0000000000000000 __preinit_array_end + 0
00000000000d  00120000000b R_X86_64_32S      0000000000000000 __preinit_array_start + 0
000000000025  00120000000b R_X86_64_32S      0000000000000000 __preinit_array_start + 0
000000000036  001300000004 R_X86_64_PLT32    0000000000000000 _init - 4
...

Offset trifft ganz zufällig die Adressen, die uns gerade aufgefallen sind. Die Symbolnamen können wir auch gut zum obigen Hochsprachencode zuordnen. Hinter Type verbergen sich die verschiedenen Berechnung, die (unter anderem) mit der Adresse des Symbols und dem Addend den Wert ausrechnen, der an die durch Offset angegebene Adresse angegeben wird.

Beispiel: Wenn sich der Linker dazu entscheidet, das (automatisch vom Compiler generierte Symbol) __preinit_array_end an die Adresse 0x4002000 zu legen, dann wird bei R_X86_64_32 schlicht diese Symboladresse zusammen mit dem Addend (hier 0) als 32-Bit langer Wert ausgewertet (04 00 20 00) und an Offset geschrieben — aber Intel-typisch dank little-endian umgedreht: 00 20 00 04.

_{Eine detaillierte Übersicht über die verschiedenen Relokationstypen findet sich unter 4.4. Relocation der System V ABI}

Binden

Aber wie wird der Linker aufgerufen? Standardmäßig ist ld der Linker. Außer ihr nutzt Clang — dann ist es ld.lld. Oder wollt gewisse Binde-Zeit-Optimierungen, dann ld.gold. Da das alles verwirrend ist, kann euch der Compiler (über eine weitere Indirektion: collect2) das abnehmen und direkt selbst den Linker aufrufen — was wir auch aus Kompatibilitätsgründen in StuBS nutzen: Im Kernel lautet die entsprechende Makefile-Zeile

$(VERBOSE) $(CXX) $(CXXFLAGS) -Wl,-T $(LINKER_SCRIPT) -o $@ $(LDFLAGS) $(CRTI_OBJECT) $(CRTBEGIN_OBJECT) $(ASM_OBJECTS) $(CC_OBJECTS) $(LIBGCC) $(CRTEND_OBJECT) $(CRTN_OBJECT)

Hinter $(CXX) versteckt sich mit g++ unser Compiler, und mit -Wl, weisen wir diesen an, den nach dem Komma folgenden Parameter an den Linker weiterzugeben, hier -T um ein eigenes Linkerskript (statt dem für Betriebssystem völlig ungeeignete Standardlinkerskript, siehe gcc -Wl,-verbose) zu verwenden.

Mit erstellter statischer libsys Bibliothek und main.o Objektdatei ignorieren wir mal die Parameter und führen das an unsere Anwendung angepasste

g++ $(CXXFLAGS) -Wl,-T ../sections.ld -o user/app1/.build/app user/.build/init.o user/app1/.build/main.o -Llibsys/.build -lsys

aus — als vereinfachendes Beispiel gehen wir davon aus, dass die Übersetzung funktioniert, etwaige Fehler in diesem Schritt werden weiter unten erklärt.

Die resultierende (nun ausführbare Elf-)Datei wird wieder dissassembiliert (objdump -d user/app1/.build/app):

0000000004000000 <start>:
 4000000:       f3 0f 1e fa             endbr64 
 4000004:       55                      push   %rbp
 4000005:       b8 00 20 00 04          mov    $0x4002000,%eax
 400000a:       53                      push   %rbx
 400000b:       48 2d 00 20 00 04       sub    $0x4002000,%rax
 4000011:       48 c1 f8 03             sar    $0x3,%rax
 4000015:       48 83 ec 08             sub    $0x8,%rsp
 4000019:       85 c0                   test   %eax,%eax
 400001b:       74 18                   je     4000035 <start+0x35>
 400001d:       8d 68 ff                lea    -0x1(%rax),%ebp
 4000020:       31 db                   xor    %ebx,%ebx
 4000022:       ff 14 dd 00 20 00 04    callq  *0x4002000(,%rbx,8)
 4000029:       48 89 d8                mov    %rbx,%rax
 400002c:       48 83 c3 01             add    $0x1,%rbx
 4000030:       48 39 e8                cmp    %rbp,%rax
 4000033:       75 ed                   jne    4000022 <start+0x22>
 4000035:       e8 e2 0d 00 00          callq  4000e1c <_init>
 ...

Wir sehen, der Linker hat gar nicht so viel gezaubert, sondern lediglich die init.o an den Anfang geklatscht, start zum ersten Symbol gemacht (also die Adresse die wir im Linkerskript als Beginn definiert hatten) und die zuvor genullten Stellen gemäß den Relokationen wie im Beispiel gezeigt angepasst!

_{Für aufmerksame Beobachter: Nicht wundern — da das Preinit-Array leer ist, sind Start- und Endadresse gleich.}

Alle, die Flat Binaries implementieren, müssen hier aufpassen: Der Linker klebt die gleichnamigen Sektionen der Objektdateien in der Reihenfolge zusammen, wie sie als Parameter angegeben werden! Wenn ihr zuerst die main.o und danach die init.o angebt, werden (in .text) die Initialisierungsroutinen nicht aufgerufen, sonder direkt die main (was je nach Anwendungsinhalt vielleicht sogar mal funktionieren kann). Und selbst bei der richtigen Reihenfolge, mit der init.o als erste Objektdatei, muss man noch aufpassen, dass start die erste Funktion in der Datei (also auch im Quelltext) ist — uns nicht etwa eine kleine Hilfsfunktion, die direkt davor steht… Man kann das entweder mit objdump abprüfen (wenn wie oben 0000000004000000 <start> steht ist alles gut) oder mittels nm user/app1/.build/app | grep "4000000 T start (was auch idealerweise als Check in der Makefile eingebaut wird).

_{Und exakt aus diesem Grund ist diese Datei im Beispiel aus der Tafelübung auch nicht Teil von libsys, sondern liegt unter user — den als Teil einer statischen Bibliothek ist es nicht einfach möglich diese Objektdatei als erste dem Linker zu übergeben! Wenn du nun jedoch den ELF-Lader implementierst, dann ist es nicht weiter notwendig, dass der Einsprung die erste Adresse ist — du könntest in diesem Fall auch den Code der Initialisierungsroutinen in das Verzeichnis für die Bibliothek packen!}

Bindefehler

Bis jetzt funktioniert das alles jedoch nur in der Theorie…

Alte (De-)Initialisierungsmethode

In der Praxis wird uns obiger Aufruf zum Linken ein paar Fehler werfen, allen voran

undefined reference to `_init'

Und hier beißen uns wieder historische Altlasten von vor der Einführung der (deutlich flexibleren) [Pre]Init-Arrays, also zu Zeiten von Gcc 4.4. Damals wurde der Aufruf von Konstruktoren (wie auch das Beispiel mit __attribute__((constructor)) bei den Initialisierungsroutinen) noch über die Funktion _init abgewickelt:

Für jede Initialisierung in einer Objektdatei wird vom Compiler schlicht Code für einen Funktionsaufruf in die .init Sektion geklebt und vom Linker zusammen gefügt. Davor kommt noch ein Prolog (der zum Beispiel den Rahmenzeiger setzt) und Epilog (mit Rücksprung) — crti.o und crtn.o (aus den gleichnamigen Assemblerdateien in Kernel compiler/). Und, weil’s grad so schön ist, will sich der Übersetzer auch die Möglichkeit beibehalten weitere eigene Routinen dran klatschen zu können (vor und nach den eigentlichen Initialisierungen, mittels crtbegin.o und crtend.o) — unnötig zu erwähnen, dass es dann noch crt0.o, crt1.o usw geben kann… (mehr Details)

Und, quasi als Sahnehäubchen für die Komplexität: Wir haben bereits gelernt, dass der Linker die Objekte in der Reihenfolge abarbeitet, wie sie als Parameter übergeben werden. Das heißt, wir müssen sicherstellen, dass crti.o vor den ganzen Benutzerobjektdateien (mit Ausnahme der init.o) ausgeführt wird, direkt gefolgt von crtbegin.o. Und am Ende dann crtend.o und crtn.o.

Welche Datei der Compiler will, kann man zum Glück mit dem Parameter --print-file-name=crtbegin.o abfragen — im CIP ist das demnach zum Beispiel die /usr/lib/gcc/x86_64-linux-gnu/10/crtbegin.o, und diese wird heutzutage nur noch verwendet um Hilfsfunktionen (z.B. für transaktionalen Speicher!) einzubauen — also nur .text, aber keinen Code für die ursprünglich eigentlich angedachte .init-Sektion.

_{Die tatsächliche Realität ist leider sogar noch ein Stück verwirrender, denn es wird abhängig von den Compilerflags unter Umständen eine andere Datei benötigt, z.B. die crtbeginT.so für statische und crtbeginS.so für dynamische Programme. Aber sie besitzen in den für uns relevanten Fällen ebenfalls keine .init-Sektion.}

Das bedeutet also, dass wir zwar aus historischen Gründen diese ganzen crt*.o einbinden müssen, aber in der Praxis davon nur der Funktionsprolog aus der crti.o und der Funktionsepilog aus der crtn.o als _init-Funktion in unsere ausführbare Binärdatei wandern, ohne jedoch wirklich wichtigen Code zu enthalten — wie eine Auswertung mittels objdump -d user/app1/.build/app zeigt (Kommentare nachträglich eingefügt):

...
0000000004000e5c <_init>:
 # Stuff from crti.asm
 4000e5c:   55                      push   %rbp
 4000e5d:   48 89 e5                mov    %rsp,%rbp
 
 # Space which would have been filled by crtbegin.S, crt0.S, ...., crtend.S in previous compiler versions
 
 # Stuff from crtn.asm
 4000e60:   5d                      pop    %rbp
 4000e61:   c3                      retq   

...

_{Im obigen Beispiel haben wir uns nur die Initialisierung (init) angeschaut, aber analog gibt es auch noch eine Deinitialisierung, also z.B. Destruktoren von globalen Objekten, dass wird fini genannt und funktioniert exakt genauso (eigene .fini Sektion, in welcher die Funktion _fini steckt)!}

Bonus: den toten Mechanismus wiederbeleben

Es ist übrigens einfach, dieses ursprüngliche Verfahren auch heute noch zu nutzen, z.B. wenn man das oben vorgestellte constructor Funktionsattribut nicht verwenden will. Wir nehmen, wie im vorherigen Beispiel, wieder unsere Funktion foo, hier mit C-Linkage:

extern "C" void foo() {
    sys_write(1, "bar\n", 4);
}

Und nun erstellen wir noch eine Assembler Datei (der Einfachheit halber in gewohnter NASM Syntax, selbstverständlich könnte man das aber auch als Inline-ASM in die C(++)-Datei schreiben):

[EXTERN foo]
[SECTION .init]
call foo

Das ist alles: Wir sagen, dass wir gerne den Code call foo in der Sektion .init hätten. Und wenn nun diese Objektdatei einfach in der richtigen Reihenfolge, also irgendwann nach crti.o aber vor crtn.o vom Linker verarbeitet wird, steht folgender Maschinencode in der erzeugten Binärdatei:

0000000004000e5c <_init>:
 4000e5c:   55                      push   %rbp
 4000e5d:   48 89 e5                mov    %rsp,%rbp
 4000e60:   e8 2b f3 ff ff          callq  4000190 <foo>
 4000e65:   5d                      pop    %rbp
 4000e66:   c3                      retq

Nun sieht auch _init aus wie eine typische übersetzte C-Funktion 🙂

_{Wir haben in StuBS eine leicht vereinfachte/abgewandelte crti.asm und crtn.asm im Vergleich zur glibc, dort wird zum Beispiel der Rahmenzeiger (%rbp) nicht verwendet und entsprechend steht in letzterer dann auch add $0x8,%rsp statt pop %rbp.}

Fehlende Methoden gemäß C++ ABI

Der nächste auftretende Fehler ist möglicherweise

undefined reference to `__cxa_atexit'

Diese fehlende Funktion ermöglicht das dynamische Registrieren von Destruktoren in einer bestimmten Reihenfolge und wird eigentlich nur für dynamische Bibliotheken (.so) gebraucht. Da wir diese aber in der Übung aufgrund der immensen Komplexität nicht unterstützen werden, ist es für uns also irrelevant (d.h. wir müssen uns da keinen Kopf bzgl. Logik machen, ein Dummy reicht).

Analog verhält es sich mit der __cxa_pure_virtual(), welche aufgerufen wird, wenn eine rein virtuelle Methode angesprungen werden sollte (was ja eigentlich verboten ist). Hier machen wir’s uns einfach und gehen in eine Endlosschleife (mangels anderer Alternativen derzeit).

Beides ist im Kernel übrigens auch schon in der compiler/libcxx.cc implementiert, denn sonst würden wir die gleichen Probleme beim Kernel bauen haben — wir klauen wieder dreist (kann entweder in die init.cc oder in eine Datei im libsys-Ordner):

// additional C++ stuff
extern "C" void __cxa_pure_virtual() {
    // Pure virtual function was called -- this if obviously not valid,
    // therefore we wait infinitely.
    while(1) {}
}

// (Dynamic) libraries can register exit commands -- we don't need them,
// hence a dummy is sufficient
extern "C"  int __cxa_atexit(void(*func) (void *), void * arg, void * dso_handle) {
    (void)func;
    (void)arg;
    (void)dso_handle;

    return 0;
}

Fehlendes `delete`

Ein dynamischer Speicherallokator ist in dieser Aufgabe noch nicht verlangt (und zumindest für den Anfang auch gar nicht empfohlen). Aber selbst wenn wir die Finger von new und delete lassen, kann es vorkommen, dass sich in einem Destruktor über eine fehlende Referenz zum delete-Operator beschwert wird:

undefined reference to `operator delete(void*, unsigned long)'

Das ist wieder so eine C++ ABI Sache, bei dem ein Destruktur aufgrund einer virtuellen Vererbungshierarchie automatisch vom Übersetzer angelegt wird — der deleting destructor. Da wir zu Beginn keinen Allokator haben, reichen vorerst Dummyfunktionen:

void operator delete(void *ptr) {
    (void) ptr;
}

void operator delete(void *ptr, __SIZE_TYPE__ size) {
    (void) ptr;
    (void) size;
}

Die `libgcc` und weitere Abhängigkeiten

Sind wir nun fertig? Nun, es könnte sein das alles tut. Aber muss nicht. Der Compiler darf prinzipiell beliebigen Code emittieren, statt direkt Maschinencode auch einfach Aufrufe an (Hilfs-)Funktionen — die er dann in einer eigenen Bibliothek bereitstellen muss. Das macht er auch für diverse arithmetische Operationen (sofern diese von der Architektur nicht direkt unterstützt werden) und Fehlerbehandlungsroutinen in der libgcc, weswegen immer auch gegen diese gelinkt werden sollte (siehe auch Beitrag auf OSDev).

_{Im Kernel ist diese Abhängigkeit übrigens nicht ganz unproblematisch — vor allem wegen der red zone (3.2.2 System V ABI): Funktionen können damit die nächsten 128 Byte des Stacks einfach nach belieben nutzen (solang sie selbst keine anderen Funktionen aufrufen), auch ohne %rsp zu ändern. Aber in Ring 0 in StuBS würde ein Interrupt dazu führen, dass der interrupt_entry direkt beim Kernelstack an %rsp weiter macht und Register sichert (und dadurch ggf. Daten im red zone überschreibt). Um das zu verhindern, wird der Kernel selbst mit dem Parameter -mno-red-zone gebaut, so dass dieses Feature für Kernelcode eigentlich nicht zur Verfügung steht… aber die libgcc.a bauen wir nicht selbst, sondern wird vom Compiler mitgeliefert, und da ist die red zone aktiv… Das ist einer der Gründe, wieso bei Betriebssystementwicklern eigentlich das Verwenden eines eigenen Cross-Compilers empfohlen wird. Wir setzen uns in BS/BST jedoch bewusst darüber hinweg, um die Einstiegshürde so gering wie möglich zu halten, und versuchen solche Probleme weitestgehend auszuschließen (bis jetzt mit Erfolg) 🙂}

Weiterhin kann es noch passieren, das beim Kopieren von großen Datenmengen (z.B. Klassen mit großen Arrays) der Compiler auf die Idee kommt, statt dem Maschinencode einen Aufruf zu memcpy zu emittieren. Das ist deswegen sinnvoll, weil die glibc diese Speicherfunktionen hoch optimiert hat, auch angepasst an die jeweilige Architektur. Hier sieht man gut die enge Zusammenarbeit zwischen der GNU Compiler Collection (Gcc) und der GNU LibC (glibc), aber wir können mit der bereits im Kernel implementierten utils/string.cc Abhilfe schaffen — diese kann mit Ausnahme der Stringduplikationsfunktionen strdup/strndup (aufgrund des fehlenden Allokators) einfach übernommen werden.

_{Das Optimieren der Speicheroperationsfunktionen memcpy, memset usw lohnt sich wirklich! Der Linux Kernel patcht sich da zum Bootvorgang selbst, abhängig von den verfügbaren Hardwareerweiterungen nimmt er die schnellste Variante. Und in glibc hat man dafür sogar einen eigenen Symboltyp eingebaut (GNU indirect function aka IFUNC), welche beim ersten Funktionsaufruf die vorhandene Architekturfeatures abfrägt und entsprechend die beste Variante bindet. Gruseliges Zeug, allerdings sind das durchaus die wenigen Stellen, wo das wirklich einen signifikanten Unterschied bringen kann & entsprechend wurde das dann auch trotz des Aufwands (und der aus Software-Engineering-Sicht eher ungünstigen Codestruktur) umgesetzt.}

Wieso wusste ich von all dem noch nichts?

Weil du in SP geschlafen hast? 😉

Vieles der Komplexität sind historische Altlasten, und aus der Geschichte des x86er wissen wir sehr genau, dass Abwärtskompatibilität in der Praxis ein sehr wichtiger Punkt ist. Entsprechend wurde nicht versucht diese Altlasten zu entfernen, sondern sie zu verstecken: Der Compiler ruft den Linker meist mit allen notwendigen Parametern für euch auf, ihr müsst lediglich die benötigten Bibliotheken angeben (-l...). Ein generisches Linkerskript passt für so gut wie alle Benutzeranwendungen. Die Initialisierung der Laufzeitumgebung wird komplett von der glibc übernommen, für uns sieht es so aus als ob wir einfach in der main starten, von dem davor und danach bekommen wir nichts mit. Vielleicht wundern wir uns kurz, wieso das ein simples statisch gebautes hello-world (gcc -static -o hw hw.c) selbst ohne Debugsymbole (strip hw) noch deutlich über 750 KiB groß ist, bei der C++ Variante (mit cout) sogar 1.9 MiB — im Vergleich zu 15 KiB bei der gleichen Anwendung in unserem StuBS. Aber das sind alles die Kosten, die wir für unsere Bequemlichkeit im normalen Userspace zahlen. Dafür müssen wir uns halt keine eigene Standardbibliothek schreiben, keine Gedanken über Linkerskripte und Linkeraufrufe machen.

Alles funktioniert (meistens) einfach.

Ihr wisst nun aber auch, was im Hintergrund alles noch passiert!

Und wie soll ich nun meine Ordner und Dateien strukturieren?

Vorweg: Es ist eure Sache, solang es funktioniert passt es. Es gibt nicht die eine richtige Lösung, und (meines Wissens nach) keine wirklich schöne.

Klar sollte sein, dass alles, was generisch für die Verwendung in den unterschiedlichen Apps ist, nach libsys soll: Syscall-Stubs, Ausgabestrom, Stringfunktion, …

Sonderfälle bleiben crti.asm, crtn.asm und init.cc: Thematisch passen diese besser in die libsys, jedoch sollten diese nicht in die statische Bibliothek libsys.a gepackt werden, sondern müssen — wie oben ausführlich erklärt — an die richtigen Stellen beim Linker für das Bauen einer jeden Anwendung gepackt werden.

_{Bei der init.cc gilt das natürlich nur für die Flat Binaries — bei ELF darf das von dieser Datei bereitgestellte start irgendwo in der Binärdatei stehen, es muss nicht zwangsweise die erste Adresse sein! Entsprechend kann dann die Datei ohne weitere Sonderbehandlung auch in der libsys stecken.}

Eine Möglichkeit wäre da filter-out im libsys/Makefile, während die Dateien dann beim Makefile der einzelnen Anwendungen an der korrekten Stelle eingebunden werden (also quasi ../../libsys/$(BUILDDIR)/crti.asm.o usw). Dazu muss aber dafür gesorgt werden, dass diese Dateien beim erstellen der statischen Bibliothek trotzdem übersetzt werden.

Das geht nun wiederum bequemer, wenn man die Dateien in user/ packt und eben zusammen mit der jeweiligen Anwendung neu übersetzt.

Schlussendlich solltet ihr eine für euch gangbare Ordnung finden — ihr müsst noch ein paar Aufgaben damit leben 😉

Makefiles

Ich hab mich für eine Variante entschieden, in der ich crti.asm und crtn.asm in libsys packe, die init.cc und section.ld aber in user — hier mal eine mögliche Verzeichnisstruktur:

StuBSmI
├── kernel
│   └── ...
├── libsys
│   ├── crti.asm
│   ├── crtn.asm
│   ├── iostream.cc
│   ├── iostream.h
│   ├── libcxx.cc
│   ├── Makefile
│   ├── math.h
│   ├── outputstream.cc
│   ├── outputstream.h
│   ├── rand.cc
│   ├── rand.h
│   ├── stringbuffer.cc
│   ├── stringbuffer.h
│   ├── syscall.asm
│   ├── syscall.h
│   ├── types.h
│   └── vector.h
├── Makefile
├── tools
│   ├── build.mk
│   ├── common.mk
│   ├── cpplint.py
│   ├── image.mk
│   ├── linter.mk
│   ├── qemu.mk
│   └── remote.mk
└── user
    ├── imgbuilder.cc
    ├── init.cc
    ├── Makefile
    ├── sections.ld
    ├── app1
    │   ├── Makefile
    │   ├── main.cc
    │   └── main.h
    └── app2
        ├── keypress.cc
        ├── keypress.h
        └── Makefile -> ../app1/Makefile

Ich habe die hier verlinkten Makefiles nochmal leicht angepasst (sie sind nun hoffentlich etwas verständlicher) und es gibt nun auch ein Beispiel für die Apps selbst. Eine Hilfe ist übrigens auch make VERBOSE=, um zu sehen was überhaupt ausgeführt wird. Aber dies ist nur ein Vorschlag, keine Vorgabe — wenn es euch nicht gefällt oder ihr nicht damit zurecht kommt, baut euch bitte selbst welche.

Außerdem solltet ihr euch unbedingt auch mal die tools/build.mk anschauen: Diese bestimmt zum Beispiel die Variable CRTI_OBJECT (anhand der lokalen CRTI_SOURCE oder, sofern es fehlt, der systemweiten Datei crti,o vom Übersetzer).

_{Es gibt noch einen kleinen Schönheitsfehler, so werden die crti.asm.o sowie crtn.asm.o im Ordner user/libsys/ gebaut, aber das stört mich nicht weiter — ihr könnt das gerne bei euch ändern.}

Bonus: ein einfacher Ausgabestrom

Schön wäre es, wenn man in den Benutzeranwendungen ähnlich wie im im Linux-Userspace-C++ einfach cout verwenden könnte. Aber eigentlich haben wir mit OutputStream und StringBuffer im Kernel schon alles implementiert was wir brauchen. Einfach beide Dateien in libsys kopieren (oder symlinken) und eine neue iostream.h erstellen:

#pragma once

#include "outputstream.h"
#include "syscall.h"

class IOStream : public OutputStream {
 private:
    IOStream(IOStream &copy);  // no copy
    int fd;

 public:
    explicit IOStream(int sysfd = 0) : fd(sysfd) {}

    ~IOStream() {
        if (pos > 0) {
            sys_write(fd, buffer, pos);
        }
    }

    void flush() override {
        sys_write(fd, buffer, pos);
        pos = 0;
    }
};

extern IOStream cout, cerr;

und passend dazu in die iostream.cc Datei

#include <iostream.h>
IOStream cout;
IOStream cerr(1);

Nun kann man das (leicht erweiterte) hello-world-Beispiel in der Benutzeranwendung gewohnt einfach schreiben:

void main() {
    for (unsigned i = 0; ; i++) {
        cout << "Hallo Welt!" << endl;
        cerr << "Durchlauf Nr. " << i << endl;
        sys_sleep(1000);
    }
}

Fühlt sich doch schon langsam fast an wie ein richtiges Betriebssystem? 🙂

Weiterführende Literatur

Linkers and Loaders von John R. Levine
Eli Bendersky’s Blog mit vielen systemnahen Betrachtungen rund um dieses Thema (siehe Archiv, vor etwa 10 Jahren)

Zurück zur Übersicht

Blog