imported>Dexxor: geringen Farbkontrast im Dunkelmodus behoben

2025-02-06T16:52:41Z

geringen Farbkontrast im Dunkelmodus behoben

Neue Seite

Unter einem '''Aufrufstapel''' ({{enS|''call stack'', ''procedure stack''<ref>{{Internetquelle |autor=Intel Corporation |url=https://software.intel.com/sites/default/files/managed/39/c5/325462-sdm-vol-1-2abcd-3abcd.pdf |titel=Intel® 64 and IA-32 Architectures Software Developer’s Manual (§6.1) |werk= |hrsg=Intel Corporation |datum=May 2019 |abruf=2019-06-18 |sprache=en}}</ref>}}) versteht man in der [[Softwaretechnik]] und [[Informatik]] einen besonders genutzten [[Stapelspeicher]], der zur [[Laufzeit (Informatik)|Laufzeit]] eines Programms den Zustand der gerade aufgerufenen [[Unterprogramm]]e enthält. Er ist vorgesehener Bestandteil der meisten [[Prozessorarchitektur]]en und seine Benutzung wird daher von speziellen [[Befehlssatzarchitektur|Instruktionen]] und [[Register_(Computer)|Registern]] unterstützt oder sogar erfordert. Als ''Stack Machine'' (engl. für ''Stapelmaschine'', nicht zu verwechseln mit [[Kellerautomat]]) wird eine Klasse von Prozessorarchitekturen bezeichnet, die gänzlich um einen Aufrufstapel herum konstruiert sind, demgegenüber verwenden [[Registermaschine]]n zwar üblicherweise einen Aufrufstapel, sind jedoch nicht ausschließlich auf seine Nutzung angewiesen. Die Verwaltung des Aufrufstapels wird in [[Höhere_Programmiersprache|Hochsprachen]] üblicherweise abstrahiert und stattdessen von [[Compiler]] und [[Betriebssystem]] übernommen. Anders als beim [[Stapelspeicher|paradigmatischen Stapelspeicher]] sind die Zugriffsmöglichkeiten auf den Aufrufstapel in vielen Architekturen jedoch nicht auf das oberste Element beschränkt und die Klassifizierung als Stapel ergibt sich aus der Verwendung als Stapelspeicher für Rücksprungadressen von Unterprogrammen. Zudem ist der Inhalt des Speichers sehr inhomogen und verknüpft Nutzdaten mit Verwaltungsdaten.

== Funktionsweise ==
=== Unterprogrammaufrufe ===
Strukturierte Programmierung erfordert in der Regel Programme in kleinere Unterprogramme zu teilen, um eine bestimmte Funktionalität jeweils genau einmal zu implementieren und so Duplizierung von Code zu vermeiden. Da diese von verschiedenen Stellen im Programm aufgerufen werden sollen, kann ein Unterprogramm keine konkrete Adresse kennen, an der die Ausführung fortgesetzt werden soll, wenn das Unterprogramm beendet ist. Daher müssen beim Aufruf Adressen gespeichert werden, an denen die Ausführung nach dem Unterprogramm fortgesetzt wird. Dies ist die Adresse, die direkt hinter der Adresse des Unterprogrammaufrufs liegt. Am Ende des Unterprogramms lädt der Prozessor die gespeicherte Adresse wieder in den Befehlszähler und die Programmausführung setzt in der Aufrufebene hinter dem Unterprogrammaufruf fort; die Rücksprungadresse wird dabei vom Stapel genommen. Das Befüllen und Entleeren des Aufrufstapels ist allerdings nicht Aufgabe des Programmierers, sofern eine [[höhere Programmiersprache]] wie [[Java (Programmiersprache)|Java]] genutzt wird. Dann erzeugen Compiler die notwendigen Befehle zur Benutzung des Aufrufstapels. Nach Abschluss eines Unterprogramms muss der Aufrufstapel wieder in den ursprünglichen Zustand versetzt werden, damit sich ein Unterprogramm beliebig häufig aufrufen lässt, ohne dass der Aufrufstapel einen [[Pufferüberlauf|Über- oder Unterlauf]] erfährt. Ob das Unterprogramm selbst für das Freigeben des Speichers zuständig ist oder der aufrufende Code das erledigen muss, hängt von der verwendeten [[Aufrufkonvention]] ab.

=== Lokaler Zustand ===
Neben der Rücksprungadresse wird aber von vielen Architekturen auch lokaler Zustand der Unterprogramme auf dem Aufrufstapel gespeichert. So wird in der [[X86-Prozessor|x86 Architektur]] beispielsweise zu diesem Zweck der Stapel in sogenannte Stapelrahmen ({{enS|''stack frames''}}) eingeteilt und neben der Rücksprungadresse auch immer ein Verweis auf den Beginn des letzten Stack Frames gespeichert. Im aktuellen Stack Frame ist genügend Speicherplatz für die Daten des aktuellen Unterprogramms reserviert und dieser kann über herkömmliche Speicherzugriffsmechanismen der Prozessorarchitektur angesprochen werden. Ein spezielles Register zeigt auf den aktuellen Frame und das Unterprogramm adressiert seinen Zustand relativ zu dieser Adresse.<ref>{{Internetquelle |autor=Intel Corporation |url=https://software.intel.com/sites/default/files/managed/39/c5/325462-sdm-vol-1-2abcd-3abcd.pdf |titel=Intel® 64 and IA-32 Architectures Software Developer’s Manual (§3.4.1) |werk= |hrsg=Intel Corporation |datum=May 2019 |abruf=2019-06-18 |sprache=en}}</ref> So können Unterprogramme sich gegenseitig aufrufen, indem immer neue Stack Frames [[Allokation_(Informatik)|alloziert]] werden und das Register jeweils um die Größe des Frames verschoben wird. Der Zustand der vorhergehenden, noch nicht beendeten Unterprogrammaufrufe wird dabei tiefer im Stapel erhalten.

=== Parameter und Rückgabewerte ===
Abhängig von der Aufrufkonvention werden auch einige oder alle Parameter für einen Unterprogrammaufruf über den Stack übergeben.<ref>{{Internetquelle |url=https://docs.microsoft.com/en-us/cpp/cpp/cdecl?view=vs-2019 |titel=__cdecl |werk=C++ Language Reference |hrsg=Microsoft |datum=2018-09-10 |abruf=2019-06-18 |sprache=en}}</ref> Ergebniswerte von Unterprogrammen können, je nach Aufrufkonvention, ebenfalls über den Aufrufstapel zurückgegeben werden. Sie belegen dann denselben 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 danach dem aufrufenden Code zur Verfügung.<ref>{{Internetquelle |url=https://itanium-cxx-abi.github.io/cxx-abi/abi.html#return-value |titel=Itanium C++ ABI |abruf=2019-06-18 |sprache=en}}</ref>

== Implementierung ==
Für jeden aktiven Unterprogrammaufruf enthält der Stack-Frame folgende Strukturen:
* optionale Eingangsparameter (geteilt mit optionalen Rückgabewerten, die später erzeugt werden)
* Rücksprungadresse
* optionale lokale Variablen

Nach einem Unterprogrammaufruf verbleibt folgende Struktur:
* optionale Rückgabewerte des Unterprogramms

Im folgenden Diagramm sind beispielhaft drei Aufrufebenen dargestellt.
# Aufrufebene (türkis) verwendet Parameter, hat aber keine lokalen Variablen.
# Aufrufebene (blau) verwendet keine Parameter, hat aber lokale Variablen.
# Aufrufebene (hellblau) verwendet sowohl Parameter, als auch lokale Variablen und Rückgabewerte.

{| class="wikitable"
|+ Aufrufstapel während und nach einem Unterprogrammaufruf
|-
! Während des Unterprogrammaufrufs !! Nach Rückkehr des Unterprogramms !! Nach Übernahme der Rückgabewerte
|- style="vertical-align:bottom"
|[[Datei:Aufrufstapel schema.svg|Aufrufstapel bei aktivem Unterprogramm|class=skin-invert]]
|[[Datei:Aufrufstapellayout nach Rücksprung.svg|Aufrufstapel nach Rückkehr|class=skin-invert]]
|[[Datei:Aufrufstapellayout nach Freigabe.svg|Aufrufstapel nach Freigabe der Rückgabewerte|class=skin-invert]]
|}

=== Nebenläufigkeit und Parallelität ===
Ein Aufrufstapel kann immer nur eine unverzweigte Folge von Unterprogrammaufrufen abbilden. Bei der Verwendung von [[Prozess (Informatik)|Prozessen]] und [[Thread (Informatik)|Threads]] muss daher für jeden Prozess und Thread ein eigener Aufrufstapel eingerichtet werden, damit Rücksprungadressen und lokale Variablen sich nicht gegenseitig überschreiben. Moderne Ansätze zur Nebenläufigkeit erfordern zuweilen auch den Ersatz des Aufrufstapels durch flexiblere Mechanismen (siehe [[#Activation Records|Activation Records]]).

=== Stapelüberlauf, Rekursion und Endrekursion ===
{{Hauptartikel|Stapelüberlauf}}
Der Speicher für den Aufrufstapel ist natürlich nicht beliebig groß. Dies wird vor allem dann zu einem Problem, wenn sich Methoden sehr oft gegenseitig oder selbst aufrufen ([[Rekursion]]). Wenn ein rekursives Problem zu groß ist, erreicht der Stack sein Speicherlimit und es können keine weiteren Stack-Frames reserviert werden: Es kommt zum Programmabsturz. Man spricht von einem ''Stapelüberlauf'' ({{enS|''stack overflow''}}). Gänzlich umgehen lässt sich das Problem nur, wenn der Programmierer Vorkehrungen trifft um eine zu tiefe Rekursion zu verhindern. Zusätzlich können [[Compiler]] dabei helfen, sogenannte [[Endrekursion]] zu optimieren.<ref>{{Literatur |Autor=Harold Abelson, Gerald Jay Sussman, Julie Sussman |Titel=Structure and Interpretation of Computer Programs |Auflage=2 |Ort=Cambridge, Massachusetts |Datum=2016-02-02 |Seiten=45f |Online=[https://web.mit.edu/alexmv/6.037/sicp.pdf] |Abruf=2019-06-26}}</ref> Dabei werden rekursive Aufrufe vom Compiler in [[Schleife (Programmierung)|Schleifen]] übersetzt, ohne die [[Semantik|semantische]] Bedeutung des Codes zu ändern. Die entstehende Schleife arbeitet ausschließlich in einem einzelnen Stack-Frame.

=== Segmentierte Aufrufstapel ===
Eine weitere Möglichkeit ein Überlaufen des Stapels zu umgehen bietet ein segmentierter Aufrufstapel. Wird ein Unterprogramm aufgerufen, überprüft dieses, ob genug Speicherplatz für seinen Stack-Frame vorhanden ist. Ist dies nicht der Fall, ruft es ein weiteres Unterprogramm auf, welches ein neues sogenanntes ''Stacklet'' ({{enS|Stäpelchen}}) alloziert und in einer Liste ablegt. Dieser neu allozierte Block wird dann für folgende Stack-Frames benutzt. Über die Liste lassen sich vorhergehende Blöcke wiederfinden, sobald der Stapel wieder abgebaut wird.<ref>{{Internetquelle |url=https://llvm.org/docs/SegmentedStacks.html |titel=Segmented Stacks in LLVM |werk=LLVM Compiler Infrastructure |hrsg=LLVM Project |datum=2019-06-26 |abruf=2019-06-26 |sprache=en}}</ref> Allerdings führt ein segmentierter Aufrufstapel zu einem Problem, das von der [[Go (Programmiersprache)|Go]]-Community das „hot-split problem“ genannt wird.<ref>{{Internetquelle |url=https://docs.google.com/document/d/1wAaf1rYoM4S4gtnPh0zOlGzWtrZFQ5suE8qr2sD8uWQ/pub |titel=Contiguous Stacks |werk=Go Design Documents |abruf=2019-06-26 |sprache=en}}</ref> Wenn ein Programm in einer Schleife ständig einen neuen Block für den Aufrufstapel anlegt und sofort wieder freigibt, führt dies zu Einbrüchen in der Performance. Aus diesem Grund haben die Programmiersprachen [[Rust (Programmiersprache)|Rust]] und [[Go (Programmiersprache)|Go]], die beide segmentierte Aufrufstapel in früheren Versionen benutzt haben, diese mittlerweile durch alternative Lösungen ersetzt.<ref>{{Internetquelle |autor=Brian Anderson |url=https://mail.mozilla.org/pipermail/rust-dev/2013-November/006314.html |titel=Abandoning segmented stacks in Rust |werk=mail.mozilla.org Mailing Lists |datum=2013-11-04 |abruf=2019-06-26 |sprache=en}}</ref><ref>{{Internetquelle |autor= |url=https://golang.org/doc/go1.3#stacks |titel=Go 1.3 Release Notes |werk=golang.org |datum=2014-06-18 |abruf=2020-09-19 |sprache=en}}</ref>

=== Stacktrace ===
Tritt in einem Programm ein Fehler auf, der nicht durch den Programmierer erwartet und behandelt wurde und die weitere Ausführung des Programms nicht ermöglicht, so stürzt das Programm ab. Dabei werden in der Regel Informationen gesammelt, die die Ursache des Absturzes eingrenzen und die Behebung des Fehlers vereinfachen sollen. Dazu gehört häufig ein sogenannter ''[[Stacktrace]]'', der die Hierarchie des Aufrufstapels zum Zeitpunkt des Fehlers widerspiegelt. Dadurch lässt sich verfolgen, in welchem Unterprogramm der Fehler auftrat und wie das Programm an die Stelle gelangt ist (da ein Unterprogramm möglicherweise von vielen Stellen aus aufgerufen werden könnte). Im Falle einer endrekursiven Funktion fehlt aber ein beträchtlicher Teil des Stacktraces, was über einen [[#Shadow Stack|Shadow Stack]] gelöst werden kann.

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

Gelingt es einer Schadsoftware, in dem gerade aufgerufenen Unterprogramm die auf dem Aufrufstapel hinterlegte Rücksprungadresse zu überschreiben, so kann sie beeinflussen, 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]]).

== Shadow Stack ==
Das Sicherheitsrisiko bezüglich des Überschreibens von Rücksprungadressen kann durch einen sogenannten ''shadow stack'' ({{enS|''Schatten Stapel''}}) mitigiert werden.<ref>{{Literatur |Autor=Saravanan Sinnadurai, Qin Zhao, Weng-Fai Wong |Titel=Transparent Runtime Shadow Stack:
Protection against malicious return address modifications |Ort=Singapore |Datum=2006 |Online=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.120.5702&rep=rep1&type=pdf |Abruf=2019-06-26}}</ref> Dabei werden die Rücksprungadressen auf einem zusätzlichen, vom eigentlichen Stapel getrennten Speicherbereich gesammelt und somit von Nutzdaten getrennt. Modifizierte Rücksprungadressen können somit erkannt und die Programmausführung rechtzeitig beendet werden. Dies erschwert typische stapelbasierte Angriffe, verhindert sie jedoch nicht gänzlich, da ein Angreifer unter Umständen auch Zugriff auf den Shadow-Stack erhalten kann. Des Weiteren werden Shadow-Stacks benutzt, um unvollständige [[#Stacktrace|Stacktraces]] während des [[Debugger|Debuggings]] von Programmen mit [[Endrekursion]] zu ergänzen. Hierzu werden alle Unterprogrammaufrufe, auch solche, die eigentlich durch die Optimierung von Endrekursion nicht mehr stattfinden, in einem Shadow-Stack zusätzlich abgespeichert, um die Fehlerbehebung zu erleichtern.<ref>{{Internetquelle |url=https://github.com/WebKit/webkit/blob/master/Source/JavaScriptCore/interpreter/ShadowChicken.h |titel=ShadowChicken.h |werk=Webkit Code Base |abruf=2019-06-26 |sprache=en}}</ref>

== Interpreter ==
Bei der Implementation eines [[Interpreter]]s wird eine neue Laufzeitumgebung modelliert, die einen eigenen Aufrufstapel besitzen kann. Einige Implementationen gestalten Unterprogrammaufrufe über eine Prozedur <code>call</code>, die bei Rekursion selbst rekursiv aufgerufen wird, was zu einer Kopplung der beiden Aufrufstapel führt. Da die Größe des Aufrufstapels bei einem Maschinenprogramm oft beschränkt ist, wird auch die maximale Rekursionstiefe des vom Interpreter ausgeführten Unterprogramms beschränkt. Eine Lösung für dieses Problem besteht darin, <code>call</code> in die Hauptschleife des Interpreters einzubetten, was der Transformation der Rekursion in eine Iteration entspricht.

== Alternativen ==
=== Registerstack ===
Abhängig von der [[Aufrufkonvention]] werden Parameter an Unterprogramme in [[Register (Computer)|Registern]] übergeben. Da Unterprogramme jedoch ihrerseits Register benötigen und weitere Unterprogramme mit anderen Parametern aufrufen können, müssen häufig Inhalte dieser Register auf dem Aufrufstapel abgelegt werden, um diese später zu rekonstruieren. Eine [[Register Stack Engine]] verhindert diese kostenintensiven Speicherzugriffe, indem es einen Stapel an Registern simuliert und diesen erst dann auf den Aufrufstapel auslagert, wenn er zu groß wird.<ref>{{Internetquelle |url=https://www.intel.com/content/www/us/en/products/docs/processors/itanium/itanium-architecture-vol-1-2-3-4-reference-set-manual.html |titel=Intel® Itanium® Architecture Software Developer's Manual |werk=intel.com |hrsg=Intel Corporation |datum=2010-05 |abruf=2019-06-26 |sprache=en}}</ref> Soll Registerinhalt auf dem Stack abgelegt werden und neuer Inhalt in das Register geschrieben werden, wird stattdessen das Register umbenannt und ein neues Register anstelle des ursprünglichen benutzt. Zur Wiederherstellung des Registerinhalts wird die Umbenennung rückgängig gemacht.

=== Activation Records ===
Alternativ ist es möglich, dass das Stack Frame (auch Activation Record genannt) auf einem [[Dynamischer Speicher|Heap]] alloziert wird. Eine teilweise Heap-Allokation ist bei [[Closure (Funktion)|Closures]] notwendig, eine vollständige bei [[Koroutine]]n, die ihren Zustand zwischen zwei Aufrufen behalten. Aus diesem Grund kann der Zustand nicht auf einem Stapel verwaltet werden, da bei Pausierung des Programms dieser Zustand überschrieben würde.

=== Continuation-Passing Style ===
Bei fester Einbettung des Stack Frames in das Maschinenprogramm entfällt der Aufrufstapel, allerdings unterbindet dies zunächst die Verwendung von Rekursion. Beim [[Continuation-Passing Style]] entfällt sogar die Speicherung der Rücksprungadresse, weil ein Unterprogramm ausschließlich neue Unterprogramme aufruft und niemals zurückkehrt, wodurch Rekursion wieder zur Verfügung steht.

== Geschichtliches ==
Bei McCarthy<ref>J. McCarthy: ''History of Lisp.'' In: R. L. Wexelblat: ''History of Programming Languages.'' Academic Press, New York 1981, S. 173–185.</ref> wird der Einsatz von Aufrufstapeln bei einer LISP-Implementierung ab 1958 berichtet.

== Belege ==
<references />

[[Kategorie:Datenstruktur]]
[[Kategorie:Rekursion]]
[[Kategorie:Unterprogramm]]

Aufrufstapel - Versionsgeschichte

imported>Dexxor: geringen Farbkontrast im Dunkelmodus behoben