Aufrufstapel

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
QS-Informatik

Dieser Artikel wurde wegen inhaltlicher Mängel auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf mit, die inhaltlichen Mängel dieses Artikels zu beseitigen, und beteilige dich an der Diskussion! (+)
Begründung: Ausbaufähiger Artikelanfang --Lord van Tasm «₪» ‣P:MB 15:33, 22. Aug. 2012 (CEST)

Unter einem Aufrufstapel (englisch call stack genannt) wird in der Softwaretechnik und Informatik ein besonders genutzter Stapelspeicher bezeichnet, der zur Laufzeit eines Programms, Informationen der gerade aufgerufenen Unterprogramme vorhält. Dazu wird üblicherweise das besondere Prozessorregister Stapelzeiger verwendet. Im Befehlssatz eines solchen Prozessors befinden sich Anweisungen zum Einrichten, Befüllen und Abbauen des Stapelspeichers sowie Befehle zum Eintritt in ein Unterprogramm und zur Rückkehr aus einem Unterprogramm.

Beschreibung[Bearbeiten]

Bei der Anwendung von strukturierter Programmierung werden mehrere kleine Unterprogramme gebildet, um eine bestimmte Funktionalität jeweils genau einmal zu implementieren. Sie sollen von verschiedenen Stellen aus aufrufbar sein. Dazu müssen beim Aufruf der verwendeten Unterprogramme Adressen gespeichert werden, an denen die Ausführung nach dem Unterprogramm fortgesetzt wird. Dies ist die Adresse, die direkt hinter der Adresse mit dem Unterprogrammaufruf liegt. Wird das Ende des Unterprogramms während der Ausführung erreicht, so ist die weitere Ausführung also abhängig von der Stelle, die das Unterprogramm aufgerufen hat (der Aufrufebene). Dazu wird die zuvor gespeicherte Rücksprungadresse wieder vom Aufrufstapel entnommen und in das Prozessorregister Befehlszeiger geladen. Mit diesem Verfahren lassen sich Unterprogramme geschachtelt aufrufen, solange der Aufrufstapel dafür Platz bietet.

Bei der Verwendung von Prozessen und Threads muss für jeden Prozess und Thread ein eigener Aufrufstapel eingerichtet werden, damit Rücksprungadressen und lokale Variablen sich nicht gegenseitig überschreiben.

Die drei Hauptaufgaben des Aufrufstapels sind das Bereitstellen von Parametervariablen für aufgerufene Unterprogramme, das Speichern der Rücksprungadresse, um nach Beendigung des Unterprogramms die Programmausführung an der richtigen Stelle (nach dem Unterprogrammaufruf) fortzuführen, und das Bereitstellen von lokalen Variablen von Unterprogrammen.

Vom Befüllen und Entleeren des Aufrufstapels bekommt man als Programmierer allerdings in der Regel nichts mit, wenn man in Hochsprachen programmiert, wie beispielsweise Java. Dann erzeugen Compiler die notwendigen Befehle zur Benutzung des Aufrufstapels. Nach Abschluss eines Unterprogramms muss der Aufrufstapel wieder den ursprünglichen ‚Füllstand‘ haben, damit sich ein Unterprogramm beliebig häufig aufrufen lässt, ohne dass der Aufrufstapel einen Über- oder Unterlauf erfährt.

Auf den nächsten freien Aufrufstapeleintrag wird üblicherweise durch das besondere Prozessorregister Stapelzeiger verwiesen.

Funktion[Bearbeiten]

Aufrufparameter[Bearbeiten]

Unterprogramme können von Parametervariablen abhängig sein. Die Werte werden vor dem Aufruf auf den Aufrufstapel gepackt und können innerhalb des Unterprogramms genutzt werden. Anzahl, Datentyp, Aufrufkonvention und Reihenfolge der Parameter müssen zwischen Aufrufer und Unterprogramm abgestimmt sein, was z. B. durch Signaturen bei der Deklaration kommuniziert wird. Alternativ können Parameter auch in Prozessorregistern übergeben werden.

Lokale Variablen[Bearbeiten]

Benutzt ein Unterprogramm lokale Variablen, so wird für sie Platz auf dem Aufrufstapel reserviert. Da jeder Aufruf zu einem eigenen Satz an Variablen führt, sind damit rekursive Unterprogrammaufrufe möglich, d. h. die jüngeren Aufrufe verändern bei der Ausführung nicht die Variablen älterer, noch nicht abgeschlossener Unterprogrammaufrufe. Bei der Verwendung von rekursiven Aufrufen müssen immer Abbruchbedingungen eine begrenzte Verschachtelung garantieren, ansonsten ist ein Überlauf des Aufrufstapels die Folge.

Für den Zugriff auf lokale Variablen wird häufig der Rahmenzeiger (englisch frame pointer, siehe auch Zeiger (Informatik)) verwendet, der auf die Adresse im Aufrufstapel mit der zugehörigen Rücksprungadresse zeigt.

Rückgabewerte[Bearbeiten]

Ergebniswerte von Unterprogrammen können ebenfalls über den Aufrufstapel zurückgegeben werden. Dies ist bei speziellen Aufrufkonventionen der Fall. Sie belegen dann den gleichen Block wie die Aufrufparameter. Die Größe dieses Bereichs muss daher so gewählt sein, dass jede der beiden Arten hineinpasst. Beim Rücksprung werden die Aufrufparameter nicht mehr benötigt, daher überschreiben die Rückgabewerte einfach die Aufrufparameter und stehen nach dem Rücksprung zur Verfügung. Da ein Ausführungsstrang aber immer nur aus einer Aufrufebene zurückkehren kann, reicht es aus, die Rückgabewerte in einem reservierten, statischen Speicherbereich unterzubringen. Dies ist die vorherrschende Methode. Die Rückgabewerte aller Unterprogramme teilen sich dann diesen Speicherbereich.

Gestaltung[Bearbeiten]

Für jeden aktiven Unterprogrammaufruf gibt es also folgende Struktur (auch Stapelrahmen genannt):

  • optionale Eingangsparameter (geteilt mit optionalen Rückgabewerten, die später erzeugt werden)
  • Rücksprungadresse
  • optionale lokale Variablen

Nach einem Unterprogrammsaufruf gibt es folgende Struktur:

  • optionale Rückgabewerte des Unterprogramms

Im folgenden Diagramm sind beispielhaft drei Aufrufebenen dargestellt.

  1. Aufrufebene (türkis) verwendet Parameter, hat aber keine lokalen Variablen.
  2. Aufrufebene (blau) verwendet keine Parameter, hat aber lokale Variablen.
  3. Aufrufebene (hellblau) verwendet sowohl Parameter, als auch lokale Variablen und Rückgabewerte.
Aufrufstapel während und nach einem Unterprogrammaufruf
während des Unterprogrammaufrufs nach Rückkehr des Unterprogramms nach Übernahme der Rückgabewerte
Aufrufstapel bei aktivem Unterpropgramm Aufrufstapel nach Rückkehr Aufrufstapel nach Freigabe der Rückgabewerte

Aufrufzustand eines Programms[Bearbeiten]

Im Falle eines nicht behebbaren Fehlers wird beim Auslösen einer Ausnahme häufig ein sogenannter Stacktrace zu Diagnosezwecken ausgegeben. Diese Ausgabe spiegelt den Aufrufstapel zum Zeitpunkt des Fehlers wider.

Sicherheitsbetrachtungen[Bearbeiten]

Die Nähe von lokalen Variablen zur Rücksprungadresse kann eine Kompromittierung der Software durch Pufferüberläufe ermöglichen.

Gelingt es einer Schadsoftware in dem gerade aufgerufenen Unterprogramm die auf dem Aufrufstapel hinterlegte Rücksprungadresse definiert zu überschreiben, so kann sie kontrollieren, welcher Code nach dem Rücksprung ausgeführt wird. Ist dazu zuvor eigener Schadcode im Hauptspeicher abgelegt worden, so kann mit diesem Verfahren die Kontrolle an den Schadcode übergeben werden.

Befindet sich z. B. ein Puffer unter den lokalen Variablen, und gelingt es der externen Schadsoftware, durch Ausnutzen von Programmierfehlern zu erreichen, dass dieser Puffer über sein definiertes Ende hinaus beschrieben wird, so wird der Ablageort der Rücksprungadresse erreichbar. Da der Aufrufstapel typischerweise von höheren zu niedrigeren Adressen (der Puffer aber von niedrigen zu höheren Adressen) beschrieben wird, sind durch Überschreiben des Puffers ältere Inhalte des Aufrufstapels veränderbar (siehe auch Pufferüberlauf).

Geschichtliches[Bearbeiten]

Bei McCarthy[1] wird der Einsatz von Aufrufstapeln bei einer LISP-Implementierung ab 1958 berichtet.

Belege[Bearbeiten]

  1. J. McCarthy: History of Lisp.. In: R. L. Wexelblat: History of Programming Languages. Academic Press, New York 1981, S. 173–185.