Der Aufrufstack: Stackrahmen, Rücksprungadressen und Überläufe

Ein Funktionsaufruf schreibt ein paar Werte in den Speicher. Bei der Rückkehr wird eine Adresse daraus gelesen und angesprungen. Geh eines der vier kleinen Programme Schritt für Schritt durch und beobachte den Stack. Oben steht die höchste Adresse; Schreibzugriffe leuchten bernsteinfarben, Lesezugriffe blau. Die Speicherstellen eines abgebauten Stackrahmens bleiben blass sichtbar, denn gelöscht wurde dort nichts.

Rechenbeispiel — Der Aufrufstack: Stackrahmen, Rücksprungadressen und Überläufe

Anzahl der Aufrufe	5
Größte Tiefe in Stackrahmen	5
Stackbelegung bei größter Tiefe	60 von 128 Bytes
Ergebnis	120

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Lektion

Die Theorie — Der Aufrufstack: Stackrahmen, Rücksprungadressen und Überläufe

Der Aufrufstack ist ein Speicherbereich, in dem jeder Funktionsaufruf einen Stackrahmen erhält. Hier enthält er das Argument, die Rücksprungadresse, an der der Aufrufer seine Ausführung fortsetzt, den gesicherten Rahmenzeiger des Aufrufers und die lokalen Variablen. Der Stackzeiger markiert die niedrigste belegte Adresse. Ein Aufruf verschiebt ihn um einen Stackrahmen nach unten, die Rückkehr wieder nach oben. Eine Rekursion mit der Aufruftiefe d und Stackrahmen von jeweils f Bytes benötigt d·f Bytes auf dem Stack.

Was die einzelnen Symbole bedeuten

d: die Tiefe: Anzahl der gleichzeitig vorhandenen Stackrahmen
f: die Größe eines Stackrahmens in Bytes: hier 12, dazu 4 je lokaler Variable

Setzt voraus: Eine 32-Bit-Maschine mit der klassischen C-Aufrufkonvention: 4-Byte-Speicherstellen, ein Stack, der zu niedrigeren Adressen wächst, Argumentübergabe auf dem Stack und ein Rahmenzeiger in jedem Stackrahmen. Gängige 64-Bit-Aufrufkonventionen übergeben die ersten Argumente in Registern. Compiler können den Rahmenzeiger weglassen, und auf ARM kann eine Funktion, die keine weitere Funktion aufruft, ihre Rücksprungadresse in einem Register halten. Echte Stackrahmen unterscheiden sich daher in Größe und Aufbau von den drei hier gezeigten Speicherstellen.

Die Rücksprungadresse ist eine Zahl im Speicher. Ein Array kann sie überschreiben. 🖖

Klick auf Sechs Werte, vier Plätze. In buf hat copy Platz für vier int-Werte. buf[0] liegt an der niedrigsten Adresse; buf[4] und buf[5] sind deshalb einfach die nächsten beiden Speicherstellen oberhalb des Arrays. Dort hat der Aufruf den gesicherten Rahmenzeiger und anschließend die Rücksprungadresse abgelegt. Die Schleife prüft ihren Index nie. So ersetzt der fünfte Wert den Rahmenzeiger und der sechste, 0x46464646, die Rücksprungadresse. Wenn copy zurückkehrt, liest der Prozessor dieses Adressfeld und springt zur angegebenen Adresse. Mit vier Werten kehrt copy wie vorgesehen zu 0x08048400 zurück. Mit fünf Werten gelingt der Rücksprung ebenfalls, doch main erhält einen beschädigten Rahmenzeiger zurück. Das ist ein Pufferüberlauf auf dem Stack. Im November 1988 drang der Morris-Wurm auf diese Weise in fingerd ein: fingerd las seine Eingabe in einen 512-Byte-Puffer ein, ohne die eingelesene Menge zu begrenzen.

Eine Variable ohne zugewiesenen Wert enthält noch, was der letzte Aufruf hinterlassen hat 🖖

Klick auf Übrig gebliebener Wert. set schreibt 42 in seine lokale Variable und kehrt zurück. Dabei wandert der Stackzeiger nach oben; gelöscht wird nichts. Anschließend wird peek von derselben Stelle aus aufgerufen. Sein Stackrahmen belegt daher dieselben Adressen, und seine lokale Variable y liegt an Adresse 1008, genau dort, wo zuvor x lag. peek schreibt nie in y. Beim Lesen kommt deshalb 42 zurück. In C gilt das Lesen einer nicht initialisierten Variable als undefiniertes Verhalten: Die Sprache garantiert dafür nichts, und ein optimierender Compiler liest die Speicherstelle womöglich gar nicht. Findet der Lesezugriff statt, liefert er den Wert, den der letzte Schreibzugriff an dieser Adresse hinterlassen hat.

Auf dem Stack liegt jeweils ein Pfad durch die Aufrufe 🖖

Stell fib auf 10. Die Funktion wird 177-mal aufgerufen, doch bei größter Tiefe liegen nur 10 Stackrahmen mit insgesamt 120 Bytes auf dem Stack. Bevor der nächste Aufruf auf derselben Verzweigungsebene beginnt, ist der Stackrahmen des vorherigen bereits abgebaut. Der Stack enthält also immer nur die Aufrufkette von fib(10) bis zur gerade ausgeführten Funktion. fact(11) kommt mit 11 Aufrufen aus, etwa einem Sechzehntel davon, und verursacht trotzdem einen Überlauf: Seine Kette ist 11 Stackrahmen lang und braucht 132 Bytes. Bei diesen beiden Funktionen erledigt jeder Aufruf neben seinen rekursiven Aufrufen einen festen Arbeitsumfang. Die Anzahl der Aufrufe ist daher ein Maß für die Laufzeit; die Länge der tiefsten Aufrufkette bestimmt den Stackbedarf.

Aufgabe vollständig gelöst

Wie tief kann eine Rekursion gehen? 4 Schritte
Klick auf fact(11): Überlauf. Der Stack dieser Seite fasst 128 Bytes. Der Linker von Microsoft reserviert für ein Programm standardmäßig 1 MB Stack. Rechne dafür mit 1 MiB, also 1.048.576 Bytes, und den Stackrahmen dieser Seite. Wie tief kann fact damit gehen? Wie tief, wenn jeder Aufruf zusätzlich eine lokale Variable von 4 Bytes hält? Und wie viel Stack braucht fib(30) im Verhältnis zur Anzahl seiner Aufrufe?

Öffne diese Aufgabe im Tool
1. Ein Stackrahmen enthält hier ein Argument, eine Rücksprungadresse und einen gesicherten Rahmenzeiger: 3 × 4 = 12 Bytes. 128 / 12 = 10,67, also passen 10 Stackrahmen hinein. fact(11) braucht 11 × 12 = 132 Bytes. Die Ergebnistabelle zeigt den Überlauf.
  
  $f = 3 \times 4 = 12, ⌊ \frac{128}{12} ⌋ = 10, 11 \times 12 = 132 > 128$
2. 1.048.576 / 12 = 87.381,33, also passen 87.381 Stackrahmen hinein. fact könnte eine Rekursionstiefe von 87.381 erreichen, bevor der Stack voll ist. Schon viel früher passt das Ergebnis nicht mehr in einen 32-Bit-int: bei 13! = 6.227.020.800.
  
  $⌊ \frac{1 048 576}{12} ⌋ = 87381$
3. Mit einer lokalen Variable von 4 Bytes wächst jeder Stackrahmen auf 16 Bytes. 1.048.576 / 16 = 65.536 geht genau auf.
  
  $f = 16 : \frac{1 048 576}{16} = 65536$
4. Die längste Aufrufkette von fib(30) umfasst 30 Stackrahmen und benötigt 30 × 12 = 360 Bytes. Die Anzahl der Aufrufe ist 2·F(31) − 1. Dabei ist F(31) = 1.346.269 die 31. Fibonacci-Zahl. Das ergibt 2.692.537 Aufrufe.
  
  $d = 30 : 30 \times 12 = 360, 2 F_{31} - 1 = 2 \times 1346269 - 1 = 2692537$
Antwort

87.381 Rekursionsebenen, mit einer lokalen Variable 65.536. fib(30) braucht für 2.692.537 Aufrufe nur 360 Bytes Stack. Die Tiefe bestimmt den Stackbedarf; bei fib bestimmt die Anzahl der Aufrufe die Laufzeit.

$d_{m a x} = ⌊ \frac{S}{f} ⌋ = 87381 (f = 12), 65536 (f = 16)$

Lernpfad

Wie ein Computer ein Programm ausführt

Quellen (2)

The worked problem's stack size: the linker's default reservation: Microsoft Learn, "/STACK (Stack allocations)," C/C++ build reference, updated 23 February 2022.
The first insight's 1988 example: fingerd's unbounded read into a 512-byte buffer on the stack: Bob Page, "A Report on the Internet Worm." University of Lowell, 7 November 1988 (copy hosted at Toronto Metropolitan University).

Vom 42Math-Team · Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen.