Call-Stack
Jede Funktion in C und C++ representiert ein kleines Unterprogramm, in welchem der entsprechende Code in einer abgeschlossenen und nach aussen nicht sichtbaren Umgebung ausgeführt wird. Um eine abgeschlossene Umgebung sicherzustellen, wird bei einem Funktionsaufruf ein Datenblock angelegt, welcher sämtliche benötigte Daten des aktuellen Programmablaufes speichert. Sobald die Funktion beendet ist, wird der Datenblock wieder abgebaut.
Da Funktionsaufrufe sehr häufig und zudem ineinander verschachtelt auftreten, müssen diese Datenblöcke in einer einfach zu erweiternden, hierarchischen Ordnung gespeichert werden. In C und C++ werden Funktionen somit auf einem Stack gespeichert. Da dieser Stack für Funktionsaufrufe benutzt wird, wird er Call-Stack
genannt.
Details
Für jeden Thread eines Prozesses existiert ein Stack, welcher sämtliche benötigte Daten des aktuellen Programmablaufes speichert. Ein Stack wird vom Runtime-System zu Beginn eines Threads (beziehungsweise zu Beginn des Prozesses) einmalig alloziiert. Die Grösse eines Stacks liegt bei modernen Systemen zwischen einigen Dutzend Kilobytes bis wenigen Megabytes.
Jeder Thread speichert zudem einen Stack-Pointer, welcher die Adresse innerhalb des Stacks bezeichnet, ab welcher noch keine Daten geschrieben stehen. Der Stack-Pointer belegt bei modernen Prozessoren ein eigenes Register und ist somit stets verfügbar.
Jede Funktion hat die Möglichkeit, einen Datenblock auf dem Stack zu reservieren. Die Datenblöcke werden Stack-Frames
genannt und werden mittels einer simplen Addition oder Subtraktion des Stack-Pointers reserviert, beziehungsweise wieder abgebaut.
Current Stackpointer
Previous Stackpointer
Bottom of Stack
Je nach Prozessor, System, Compiler und Situation werden in einem Stack-Frame unterschiedliche Daten gespeichert. Welche Daten wie, in welche Reihenfolge, wann und mit welchen Maschinenbefehlen gespeichert werden, kann nicht allgemein beschrieben werden. Auf dieser Seite wird versucht, ein Grundprinzip eines Funktionsaufrufes aufzuzeigen. Die zu speichernden Daten werden hierfür grob in folgende Teile aufgeteilt: Prozessorstatus, Signatur und lokale Variablen.
Speicherung des Prozessorstatus
Bei Aufruf einer Funktion wird grundsätzlich zum Maschinencode der Funktion gesprungen und am Ende der Funktion wieder zur aufrufenden Stelle zurückgekehrt. Um während der Ausführung der Funktion die Prozessorregister der aufrufenden Funktion nicht zu zerstören, werden sie im Stack-Frame gespeichert (abgelegt). Die Speicherung aller notwendigen Register wird auch als Speicherung des Prozessorstatus bezeichnet.
Je nach Prozessor, System, Compiler oder Situation werden unterschiedliche Register gespeichert. Manche Systeme speichern grundsätzlich sämtliche Register, andere speichern nur diejenigen, welche durch die Funktion verändert werden könnten und nochmals andere speichern aus Prinzip nur solche, welche von der Architektur aus für die Speicherung vorgesehen sind. Dennoch werden insbesondere zwei Register stets gespeichert: Der Stack-Pointer sowie der Befehls-Zeiger der aufrufenden Funktion.
Die Speicherung des Stack-Pointers sowie des Befehls-Zeigers ist notwendig, um nach dem Rücksprung der Funktion den Stack wieder in den vorherigen Zustand zurückzuversetzen und den Code an der Stelle fortzuführen, an welcher zur Funktion gesprungen wurde. Je nach System und Architektur sind gewisse Details zu beachten, welche hier jedoch nicht weiter ausgeführt sind. Grundsätzlich gilt: Beim Rücksprung aus einer Funktion muss der Prozessor wieder in den Zustand zurückversetzt werden, welchen er vor dem Aufruf der Funktion hatte. Durch die Speicherung aller notwendigen Register auf dem Stack und der Wiederherstellung beim dem Rücksprung kann dies garantiert werden.
Ein Stackframe einer sehr einfachen Funktion sieht somit folgendermassen aus:
New Stackpointer
Old Stackpointer
Die Namen der Register sowie die Position des alten Stack-Pointers und des Befehls-Zeigers wurden hier auf dieser Seite willkürlich gewählt.
Beim Aufruf einer Funktion passiert somit folgendes: Befehls-Zeiger, Stack-Pointer und alle benötigten Register werden beginnend beim aktuellen Stack-Pointer auf den Stack geschrieben. Danach wird der Stack-Pointer an die neue Stelle verschoben. Daraufhin wird der Befehls-Zeiger auf die Adresse des Maschinencodes der aufzurufenden Funktion gesetzt und dort weitergefahren.
Bei Rücksprung aus der Funktion passiert folgendes: Ausgehend vom aktuellen Stack-Pointer werden sämtliche Werte wieder in die entsprechenden Register zurückkopiert. Ganz zum Schluss werden auch der Stack-Pointer und der Befehlszeiger auf den alten Wert zurückgesetzt. Sodann wird beim nächsten Maschinenbefehl nach dem Befehlszeiger fortgefahren.
Für die Ausführung der Status-Speicherung und -Wiederherstellung gibt es in modernen Prozessoren teilweise spezielle Befehle. Auf dieser Seite wird jedoch nicht weiter darauf eingegangen.
Signatur: Argumente, Parameter und Rückgabewert
Bei Aufruf einer Funktion können Argumente als Eingabewerte übergeben werden. Damit diese Eingabewerte während der Laufzeit der Funktion als Parameter verfügbar sind, werden die Argumente ebenfalls auf dem Stack gespeichert. Des weiteren kann eine Funktion nach Abschluss einen Wert zurückgeben. Für eine detailierte Beschreibung der Begriffe wird auf die Seiten über Argumente und Parameter und dem Rückgabewert verwiesen.
Die Signatur einer Funktion legt fest, welche Parameter in welcher Reihenfolge von der Funktion erwartet werden und welche Art von Rückgabewert von der Funktion geliefert wird. Die aufrufende Funktion speichert somit vor Aufruf der Funktion sämtliche Eingabewerte auf dem Stack und reserviert gegebenfalls Platz für den Rückgabewert. Diese Reservation passiert durch eine einfache Verschiebung des Stack-Pointers. Nachdem alle Argumente geschrieben wurden, wird wie oben beschrieben mit der Statusspeicherung des Prozessors fortgefahren und die Funktion angesprungen. Das Stack-Frame einer Funktion mit Argumenten und Rückgabewert sieht dementsprechend folgendermassen aus:
New Stackpointer
Old Stackpointer
Da der Compiler beim Compilieren einer Funktion weiss, wie gross der Register-Teil des Stack-Frames ist, können die Parameter einfach durch die Adresse des aktuellen Stack-Pointers plus einem Offset representiert werden. Während der Laufzeit der Funktion sind somit sämtliche Parameter wie auch der Rückgabewert direkt ansprechbar.
Da sämtliche Parameter innerhalb der aufgerufenen Funktion stets vom (neuen) Stack-Pointer aus adressiert werden, können durch die oben gezeigte Anordnung der Parameter beliebig viele Argumente übergeben werden. Solche als variadisch
bezeichnete Funktionen können diese Parameter mittels geeigneter Makros auslesen.
Beim Rücksprung wird das Stack-Frame abgebaut. Zuerst werden wie oben beschrieben die Register wiederhergestellt. Daraufhin werden sämtliche Argumente und der Rückgabewert verworfen, indem der Stackpointer wieder an die ursprüngliche Position zurückverschoben wird. Der Compiler weiss während der Compilation, wieviele Bytes für die Argumente und den Rückgabewert reserviert wurden und kann somit den Stack-Pointer einfach wieder um die gleiche Anzahl Bytes zurückverschieben. Damit die aufrufende Funktion trotz Abbau des Stackframes den Rückgabewert verwenden kann, muss derselbe vor Abbau an eine lokale Variable kopiert werden.
Wenn als Rückgabewert ein Struct oder ein Objekt einer Klasse erwartet wird, so müsste vor Abbau des Datenblockes das gesamte Objekt an eine lokale Variable per Copy-Konstruktor kopiert werden. Um diesen Aufwand zu sparen, wird der Compiler für das gewünschte Objekt bereits bei den lokalen Variablen der aufrufenden Funktion genügend Platz reservieren. Bei Aufruf der aufzurufenden Funktion wird ein Pointer auf diesen Platz anstelle des Rückgabewertes übergeben. Die aufgerufene Funktion kann somit mittels dieser Adresse auf die lokale Variable der aufrufenden Funktion zugreifen und dort das gewünschte Rückgabe-Objekt ablegen.
Argumente sowie Rückgabewert könnten grundsätzlich auch per Prozessorregister übergeben werden. Somit müssten die Daten nicht mehr auf dem Stack gespeichert werden und das Zurückkopieren des Rückgabewertes entfällt. Tatsächlich wird dies bei sehr einfachen Funktionen auch gemacht. Dennoch wird der Stack in vielen Fällen trotzdem benötigt. Ein einfacher Grund für die Verwendung des Stacks ist, dass zuwenig Register vorhanden sind.
Ein weiterer Grund ist, wenn innerhalb der Funktion der Pointer eines Wertes angesprochen werden soll. Da ein Prozessorregister keine Adresse besitzt, muss der Wert per Stack übergeben werden.
Ein anderer Grund ist, wenn die Prozessorregister zu klein sind für den zu speichernden Wert. Bei heutigen 64-Bit-Systemen ist dies bei den Basistypen meistens kein Problem mehr, doch können auch Structs und Objekte übergeben werden. Im Falle eines Objekts muss somit auf dem Stack ein Konstruktor aufgerufen werden, um das Objekt zu instantiieren und bei Rückkehr der Funktion muss der Destruktor dieses Objekt wieder abbauen. Der Compiler baut dies automatisch in den Funktionsaufruf ein. Je nach Häufigkeit eines Funktionsaufrufes und der Komplexität der Konstruktoren und Destruktoren kann dies die Laufzeit stark beeinflussen.
Lokale Variablen
Lokale Variablen werden von einer Funktion angelegt, indem einfach der Stack-Pointer um die benötigte Anzahl Bytes verschoben wird. Beim Rücksprung aus der Funktion wird der Stack-Pointer wieder an die ursprüngliche Position zurückversetzt. Ein Stackframe mit lokalen Variablen sieht somit folgendermassen aus:
New Stackpointer
Old Stackpointer
Da ein Compiler während der Übersetzung des Funktionscodes genau weiss, wieviele Bytes für die lokalen Variablen und für die Register benötigt werden, können alle Parameter vom aktuellen Stack-Pointer aus mittels einem einfachen Offset angesprochen werden.
Sobald eine Funktion Platz für die lokalen Variablen auf dem Stack reserviert hat, können die Daten initialisiert werden. Für Objekte werden somit auf dem Stack Konstruktoren aufgerufen. Beim Rücksprung aus einer Funktion wird das Stackframes abgebaut und es werden für lokale Objekte die entsprechenden Destruktoren aufgerufen. Somit gelten die lokalen Variablen der Funktion nach dem Rücksprung als ungültig. Aus diesem Grund sollten keine lokalen Objekte (in diesem Zusammenhang auch temporäre
Objekte gennant) als Rückgabewerte verwendet werden.
Abschliessende Bemerkungen
Die verschiedenen Teile eines Stackframes wurden auf dieser Seite gemäss einem logischen Verständnis erklärt. Wie ein Stackframe dann tatsächlich in einem echten System, mit einem echten Prozessor und einem wirklichen Compiler aufgebaut werden, kann sich an allen Ecken und Kanten ändern. Manche Umgebungen ordnen die Register stets zuoberst an, andere reservieren Reservebytes, und nochmals andere optimieren Funktionsaufrufe automatisch, sodass ein Stackframe vollständig hinfällig wird.
Über all die Finessen des Stacks muss während des Programmierens normalerweise nicht nachgedacht werden. Der Compiler übernimmt die ganze Arbeit, genau dazu ist er schliesslich auch da. Dennoch gibt es die Möglichkeit, mittels Attribute den Compiler anzuweisen, wie der Aufruf der Funktion vonstatten zu gehen habe und wie die Parameter und lokalen Variablen gespeichert werden. Da moderne Compiler jedoch sehr gute Optimierungen vornehmen, ist der Umgang mit Attributen heute fast nicht mehr gebräuchlich.
Mit dem Call-Stack wird grundsätzlich erst dann in Berührung gekommen, wenn etwas nicht funktioniert. Debugger können mittels des Call-Stacks sämtliche lokalen Variablen, Parameter und Prozessorregister auslesen und präsentieren. Die Durchsicht des Call-Stacks ist häufig eine wertvolle Hilfe, um herauszufinden, wo im Programm ein Fehler seinen Ursprung hat.
Da der Call-Stack für die Fehlersuche ein so wertvolles Hilfsmittel ist, wurde in C++ das Exception-Handling
eingeführt. Hiermit kann direkt im Code beschreiben werden, bis zu welchem Punkt der Stack automatisch abgebaut werden soll, falls eine Ausnahme, beziehungsweise ein Fehler auftritt. Weiterführende Informationen können bei der try-catch-Struktur nachgelesen werden.
Falls bei einem Funktionsaufruf der Stack-Pointer aus dem Stack hinausläuft (Overflow), greift das System ein und lässt das Programm abstürzen. Dies passiert äusserst selten. Sehr häufig deutet ein Stack-Overflow auf eine fehlerhafte, unendliche Rekursion hin. Dennoch können auch korrekte Funktionen sich gegenseitig so oft aufrufen, dass der Stack überläuft. In diesem Falle muss eine andere Lösung für das Programm gefunden werden.
Nächstes Kapitel: Structs