Wie genau funktioniert der Callstack?

103

Ich versuche ein tieferes Verständnis dafür zu bekommen, wie die Low-Level-Operationen von Programmiersprachen funktionieren und insbesondere wie sie mit dem Betriebssystem / der CPU interagieren. Ich habe wahrscheinlich jede Antwort in jedem Stack / Heap-bezogenen Thread hier auf Stack Overflow gelesen und sie sind alle brillant. Aber eines habe ich noch nicht ganz verstanden.

Betrachten Sie diese Funktion im Pseudocode, der tendenziell ein gültiger Rust-Code ist ;-)

fn foo() {
    let a = 1;
    let b = 2;
    let c = 3;
    let d = 4;

    // line X

    doSomething(a, b);
    doAnotherThing(c, d);
}

So gehe ich davon aus, dass der Stapel in Zeile X aussieht:

Stack

a +-------------+
  | 1           | 
b +-------------+     
  | 2           |  
c +-------------+
  | 3           | 
d +-------------+     
  | 4           | 
  +-------------+ 

Alles, was ich über die Funktionsweise des Stacks gelesen habe, ist, dass er sich strikt an die LIFO-Regeln hält (last in, first out). Genau wie ein Stack-Datentyp in .NET, Java oder einer anderen Programmiersprache.

Aber wenn das der Fall ist, was passiert dann nach Zeile X? Denn das nächste, was wir brauchen, ist natürlich, mit aund zu arbeiten b, aber das würde bedeuten, dass das Betriebssystem / die CPU (?) Herausspringen muss dundc zuerst zu aund zurückkehren muss b. Aber dann würde es sich in den Fuß schießen, weil es braucht cund din die nächste Zeile.

Ich frage mich also, was genau hinter den Kulissen passiert.

Eine andere verwandte Frage. Stellen Sie sich vor, wir geben einen Verweis auf eine der anderen Funktionen wie folgt weiter:

fn foo() {
    let a = 1;
    let b = 2;
    let c = 3;
    let d = 4;

    // line X

    doSomething(&a, &b);
    doAnotherThing(c, d);
}

Nach meinem Verständnis würde dies bedeuten, dass die Parameter in doSomethingim Wesentlichen auf dieselbe Speicheradresse wie aund bin verweisen foo. Andererseits bedeutet dies, dass es keine gibt der Stapel erst dann angezeigt wird, wenn wir zu aundb geschehen.

Diese beiden Fälle lassen mich denken, dass ich nicht vollständig verstanden habe, wie genau der Stack funktioniert und wie er sich strikt an die LIFO- Regeln hält.

Christoph
quelle
14
LIFO ist nur wichtig, um Platz auf dem Stapel zu reservieren. Sie können jederzeit auf jede Variable zugreifen, die sich mindestens in Ihrem Stapelrahmen befindet (innerhalb der Funktion deklariert), auch wenn sie sich unter vielen anderen Variablen befindet
VoidStar
2
Mit anderen Worten, LIFOSie können Elemente nur am Ende des Stapels hinzufügen oder entfernen und jedes Element jederzeit lesen / ändern.
HolyBlackCat
12
Warum zerlegen Sie nach dem Kompilieren mit -O0 keine einfache Funktion und sehen sich die generierten Anweisungen an? Es ist hübsch, gut, lehrreich ;-). Sie werden feststellen, dass der Code den R-Teil des RAM gut nutzt. es greift direkt nach Belieben auf Adressen zu. Sie können sich einen Variablennamen als Offset zu einem Adressregister (dem Stapelzeiger) vorstellen. Wie die anderen sagten, ist der Stapel in Bezug auf das Stapeln nur LIFO (gut für die Rekursion usw.). Es ist kein LIFO in Bezug auf den Zugriff darauf. Der Zugriff ist völlig zufällig.
Peter - Stellen Sie Monica am
6
Sie können mithilfe eines Arrays eine eigene Stapeldatenstruktur erstellen und einfach den Index des obersten Elements speichern, ihn beim Drücken erhöhen und beim Popup dekrementieren. Wenn Sie dies getan haben, können Sie jederzeit auf jedes einzelne Element im Array zugreifen, ohne es zu verschieben oder zu öffnen, so wie Sie es bei Arrays immer tun können. Ungefähr das Gleiche passiert hier.
Crowman
3
Grundsätzlich ist die Benennung von Stack / Heap unglücklich. Sie haben wenig Ähnlichkeit mit Stack und Heap in der Terminologie von Datenstrukturen, daher ist es sehr verwirrend, sie gleich zu nennen.
Siyuan Ren

Antworten:

117

Der Aufrufstapel kann auch als Frame-Stack bezeichnet werden.
Die Dinge, die nach dem LIFO-Prinzip gestapelt werden, sind nicht die lokalen Variablen, sondern die gesamten Stapelrahmen ("Aufrufe") der aufgerufenen Funktionen . Die lokalen Variablen werden zusammen mit diesen Frames im sogenannten Funktionsprolog und Epilog verschoben und gepoppt .

Innerhalb des Rahmens ist die Reihenfolge der Variablen völlig unbestimmt. Compiler "ordnen" die Positionen lokaler Variablen innerhalb eines Frames entsprechend neu an, um ihre Ausrichtung zu optimieren, damit der Prozessor sie so schnell wie möglich abrufen kann. Die entscheidende Tatsache ist, dass der Versatz der Variablen relativ zu einer festen Adresse während der gesamten Lebensdauer des Rahmens konstant ist. Es reicht also aus, eine Ankeradresse, beispielsweise die Adresse des Rahmens selbst, zu verwenden und mit Versätzen dieser Adresse zu arbeiten die Variablen. Eine solche Ankeradresse ist tatsächlich in der sogenannten Basis enthalten, oder Rahmenzeiger enthalten die im EBP-Register gespeichert ist. Die Offsets hingegen sind zum Zeitpunkt der Kompilierung klar bekannt und daher im Maschinencode fest codiert.

Diese Grafik aus Wikipedia zeigt, wie der typische Aufrufstapel wie folgt aufgebaut ist : 1 :

Bild eines Stapels

Fügen Sie den Offset einer Variablen, auf die wir zugreifen möchten, zu der im Frame-Zeiger enthaltenen Adresse hinzu, und wir erhalten die Adresse unserer Variablen. Kurz gesagt, der Code greift direkt über konstante Kompilierungszeit-Offsets vom Basiszeiger auf sie zu. Es ist eine einfache Zeigerarithmetik.

Beispiel

#include <iostream>

int main()
{
    char c = std::cin.get();
    std::cout << c;
}

gcc.godbolt.org gibt uns

main:
    pushq   %rbp
    movq    %rsp, %rbp
    subq    $16, %rsp

    movl    std::cin, %edi
    call    std::basic_istream<char, std::char_traits<char> >::get()
    movb    %al, -1(%rbp)
    movsbl  -1(%rbp), %eax
    movl    %eax, %esi
    movl    std::cout, %edi
    call    [... the insertion operator for char, long thing... ]

    movl    $0, %eax
    leave
    ret

.. für main. Ich habe den Code in drei Unterabschnitte unterteilt. Der Funktionsprolog besteht aus den ersten drei Operationen:

  • Der Basiszeiger wird auf den Stapel geschoben.
  • Der Stapelzeiger wird im Basiszeiger gespeichert
  • Der Stapelzeiger wird subtrahiert, um Platz für lokale Variablen zu schaffen.

Dann cinwird in das EDI-Register 2 verschoben und getaufgerufen; Der Rückgabewert ist in EAX.

So weit, ist es gut. Jetzt passiert das Interessante:

Das durch das 8-Bit-Register AL bezeichnete niederwertige Byte von EAX wird direkt nach dem Basiszeiger genommen und im Byte gespeichert : Das heißt -1(%rbp), der Versatz des Basiszeigers ist -1. Dieses Byte ist unsere Variablec . Der Versatz ist negativ, da der Stapel auf x86 nach unten wächst. Die nächste Operation wird cin EAX gespeichert: EAX wird in ESI verschoben, coutwird in EDI verschoben und dann wird der Einfügeoperator mit coutund cals Argument aufgerufen .

Schließlich,

  • Der Rückgabewert von mainwird in EAX: 0 gespeichert. Dies liegt an der impliziten returnAnweisung. Sie könnten auch xorl rax raxanstelle von sehen movl.
  • verlassen und zur Anrufstelle zurückkehren. leaveverkürzt diesen Epilog und implizit
    • Ersetzt den Stapelzeiger durch den Basiszeiger und
    • Öffnet den Basiszeiger.

Nach dieser Operation und nachdem retsie ausgeführt wurde, wurde der Frame effektiv gelöscht, obwohl der Aufrufer die Argumente noch bereinigen muss, da wir die Aufrufkonvention cdecl verwenden. Andere Konventionen, z. B. stdcall, erfordern, dass der Angerufene aufräumt, z. B. indem er die Anzahl der Bytes an übergibt ret.

Auslassung des Rahmenzeigers

Es ist auch möglich, keine Offsets vom Basis- / Frame-Zeiger, sondern vom Stack-Zeiger (ESB) zu verwenden. Dies macht das EBP-Register, das sonst den Frame-Zeigerwert enthalten würde, für eine willkürliche Verwendung verfügbar - es kann jedoch das Debuggen auf einigen Computern unmöglich machen und wird für einige Funktionen implizit deaktiviert . Dies ist besonders nützlich, wenn Sie für Prozessoren mit nur wenigen Registern kompilieren, einschließlich x86.

Diese Optimierung wird als FPO (Frame Pointer Ommission) bezeichnet und von -fomit-frame-pointerin GCC und -Oyin Clang festgelegt. Beachten Sie, dass es implizit von jeder Optimierungsstufe> 0 ausgelöst wird, wenn und nur wenn das Debuggen noch möglich ist, da es sonst keine Kosten verursacht. Weitere Informationen finden Sie hier und hier .


1 Wie in den Kommentaren ausgeführt, soll der Rahmenzeiger vermutlich auf die Adresse nach der Rücksprungadresse zeigen.

2 Beachten Sie, dass die Register, die mit R beginnen, die 64-Bit-Gegenstücke derjenigen sind, die mit E beginnen. EAX bezeichnet die vier niederwertigen Bytes von RAX. Ich habe die Namen der 32-Bit-Register zur Klarheit verwendet.

Columbo
quelle
1
Gute Antwort. Die Sache mit der Adressierung der Daten durch Offsets war das fehlende Bit für mich :)
Christoph
1
Ich denke, es gibt einen kleinen Fehler in der Zeichnung. Der Rahmenzeiger müsste sich auf der anderen Seite der Rücksprungadresse befinden. Das Verlassen einer Funktion erfolgt normalerweise wie folgt: Bewegen des Stapelzeigers auf den Rahmenzeiger,
Entfernen des Aufrufzeigerzeigers
Kasperd ist absolut richtig. Entweder verwenden Sie den Frame-Zeiger überhaupt nicht (gültige Optimierung und insbesondere für Architekturen ohne Register wie x86 äußerst nützlich) oder Sie verwenden ihn und speichern den vorherigen auf dem Stapel - normalerweise direkt nach der Rücksprungadresse. Wie der Frame eingerichtet und entfernt wird, hängt stark von der Architektur und dem ABI ab. Es gibt einige Architekturen (hallo Itanium), in denen das Ganze interessanter ist (und es gibt Dinge wie Argumentlisten mit variabler Größe!)
Voo
3
@Christoph Ich denke, Sie nähern sich dem aus konzeptioneller Sicht. Hier ist ein Kommentar, der dies hoffentlich klären wird - Der RTS oder RunTime-Stapel unterscheidet sich ein wenig von anderen Stapeln darin, dass es sich um einen "schmutzigen Stapel" handelt. Es gibt eigentlich nichts, was Sie daran hindert, einen Wert zu betrachten, der nicht ' t oben. Beachten Sie, dass im Diagramm die "Rücksprungadresse" für die grüne Methode angegeben ist - die von der blauen Methode benötigt wird! ist nach den Parametern. Wie erhält die blaue Methode den Rückgabewert, nachdem der vorherige Frame eingeblendet wurde? Nun, es ist ein schmutziger Stapel, also kann er einfach hineingreifen und ihn greifen.
Riking
1
Der Frame-Zeiger wird eigentlich nicht benötigt, da stattdessen immer Offsets vom Stack-Zeiger verwendet werden können. GCC, das auf x64-Architekturen abzielt, verwendet standardmäßig einen Stapelzeiger und kann rbpandere Arbeiten ausführen .
Siyuan Ren
27

Denn das nächste, was wir brauchen, ist natürlich, mit a und b zu arbeiten, aber das würde bedeuten, dass das Betriebssystem / die CPU (?) Zuerst d und c herausspringen muss, um zu a und b zurückzukehren. Aber dann würde es sich in den Fuß schießen, weil es in der nächsten Zeile c und d braucht.

Zusamenfassend:

Die Argumente müssen nicht eingeblendet werden. Die vom Aufrufer fooan function übergebenen Argumente doSomethingund die lokalen Variablen in doSomething können alle als Offset vom Basiszeiger referenziert werden .
So,

  • Wenn ein Funktionsaufruf ausgeführt wird, werden die Argumente der Funktion auf dem Stapel PUSHed. Auf diese Argumente wird weiter durch den Basiszeiger verwiesen.
  • Wenn die Funktion zu ihrem Aufrufer zurückkehrt, werden die Argumente der zurückkehrenden Funktion mithilfe der LIFO-Methode vom Stapel gepoppt.

Im Detail:

Die Regel lautet, dass bei jedem Funktionsaufruf ein Stapelrahmen erstellt wird (wobei das Minimum die Adresse ist, an die zurückgegeben werden soll). Wenn also funcAAnrufe funcBund funcBAufrufe ausgeführt werden funcC, werden drei Stapelrahmen übereinander eingerichtet. Wenn eine Funktion zurückkehrt, wird ihr Frame ungültig . Eine gut erzogene Funktion wirkt nur auf ihren eigenen Stapelrahmen und greift nicht auf den eines anderen ein. Mit anderen Worten, das POPing wird für den Stapelrahmen oben ausgeführt (bei Rückkehr von der Funktion).

Geben Sie hier die Bildbeschreibung ein

Der Stapel in Ihrer Frage wird vom Anrufer eingerichtet foo. Wenn doSomethingund doAnotherThingaufgerufen werden, richten sie ihren eigenen Stack ein. Die Abbildung kann Ihnen helfen, dies zu verstehen:

Geben Sie hier die Bildbeschreibung ein

Beachten Sie, dass der Funktionskörper für den Zugriff auf die Argumente von dem Speicherort, an dem die Rücksprungadresse gespeichert ist, nach unten (höhere Adressen) durchlaufen muss. Um auf die lokalen Variablen zugreifen zu können, muss der Funktionskörper den Stapel nach oben durchlaufen (niedrigere Adressen) ) relativ zu dem Ort, an dem die Absenderadresse gespeichert ist. Tatsächlich wird ein typischer vom Compiler generierter Code für die Funktion genau dies tun. Der Compiler reserviert hierfür ein Register namens EBP (Base Pointer). Ein anderer Name dafür ist Frame Pointer. Der Compiler schiebt normalerweise als erstes für den Funktionskörper den aktuellen EBP-Wert auf den Stapel und setzt den EBP auf den aktuellen ESP. Dies bedeutet, dass, sobald dies erledigt ist, in einem beliebigen Teil des Funktionscodes Argument 1 EBP + 8 entfernt ist (4 Bytes für jedes EBP des Aufrufers und die Rücksprungadresse), Argument 2 EBP + 12 (dezimal) entfernt ist, lokale Variablen sind EBP-4n entfernt.

.
.
.
[ebp - 4]  (1st local variable)
[ebp]      (old ebp value)
[ebp + 4]  (return address)
[ebp + 8]  (1st argument)
[ebp + 12] (2nd argument)
[ebp + 16] (3rd function argument) 

Schauen Sie sich den folgenden C-Code für die Bildung des Stapelrahmens der Funktion an:

void MyFunction(int x, int y, int z)
{
     int a, int b, int c;
     ...
}

Wenn Anrufer es anrufen

MyFunction(10, 5, 2);  

Der folgende Code wird generiert

^
| call _MyFunction  ; Equivalent to: 
|                   ; push eip + 2
|                   ; jmp _MyFunction
| push 2            ; Push first argument  
| push 5            ; Push second argument  
| push 10           ; Push third argument  

und der Assembler-Code für die Funktion lautet (von Angerufenen vor der Rückkehr eingerichtet)

^
| _MyFunction:
|  sub esp, 12 ; sizeof(a) + sizeof(b) + sizeof(c)
|  ;x = [ebp + 8], y = [ebp + 12], z = [ebp + 16]
|  ;a = [ebp - 4] = [esp + 8], b = [ebp - 8] = [esp + 4], c = [ebp - 12] =   [esp]
|  mov ebp, esp
|  push ebp
 

Verweise:

Haccks
quelle
1
Vielen Dank für Ihre Antwort. Auch die Links sind wirklich cool und helfen mir, mehr Licht in die unendliche Frage zu bringen, wie Computer tatsächlich funktionieren :)
Christoph
Was meinst du mit "schiebt den aktuellen EBP-Wert auf den Stapel" und auch, dass der Stapelzeiger im Register gespeichert ist oder auch das eine Position im Stapel einnimmt ... Ich bin wenig verwirrt
Suraj Jain
Und sollte das nicht * [ebp + 8] sein, nicht [ebp + 8]?
Suraj Jain
@ Suraj Jain; Weißt du was ist EBPund ESP?
Haccks
esp ist Stapelzeiger und ebp ist Basiszeiger. Wenn ich etwas fehlendes Wissen habe, korrigieren Sie es bitte.
Suraj Jain
19

Wie andere angemerkt haben, müssen Parameter erst eingeblendet werden, wenn sie den Gültigkeitsbereich verlassen.

Ich werde ein Beispiel aus "Pointers and Memory" von Nick Parlante einfügen. Ich denke, die Situation ist etwas einfacher als Sie es sich vorgestellt haben.

Hier ist Code:

void X() 
{
  int a = 1;
  int b = 2;

  // T1
  Y(a);

  // T3
  Y(b);

  // T5
}

void Y(int p) 
{
  int q;
  q = p + 2;
  // T2 (first time through), T4 (second time through)
}

Die Zeitpunkte T1, T2, etc. sind im Code markiert und der Speicherstatus zu diesem Zeitpunkt ist in der Zeichnung dargestellt:

Geben Sie hier die Bildbeschreibung ein


quelle
2
Tolle visuelle Erklärung. Ich habe gegoogelt und das Papier hier gefunden: cslibrary.stanford.edu/102/PointersAndMemory.pdf Wirklich hilfreiches Papier!
Christoph
7

Verschiedene Prozessoren und Sprachen verwenden einige unterschiedliche Stack-Designs. Zwei traditionelle Muster auf 8x86 und 68000 werden als Pascal-Aufrufkonvention und C-Aufrufkonvention bezeichnet. Jede Konvention wird in beiden Prozessoren bis auf die Namen der Register gleich behandelt. Jedes verwendet zwei Register, um den Stapel und die zugehörigen Variablen zu verwalten, die als Stapelzeiger (SP oder A7) und Rahmenzeiger (BP oder A6) bezeichnet werden.

Wenn Sie eine Unterroutine mit einer der beiden Konventionen aufrufen, werden alle Parameter auf den Stapel verschoben, bevor Sie die Routine aufrufen. Der Code der Routine schiebt dann den aktuellen Wert des Rahmenzeigers auf den Stapel, kopiert den aktuellen Wert des Stapelzeigers auf den Rahmenzeiger und subtrahiert vom Stapelzeiger die Anzahl der von lokalen Variablen verwendeten Bytes [falls vorhanden]. Sobald dies erledigt ist, werden alle lokalen Variablen in Variablen mit einer konstanten negativen Verschiebung vom Stapelzeiger gespeichert, selbst wenn zusätzliche Daten auf den Stapel übertragen werden, und auf alle Parameter, die vom Aufrufer auf den Stapel verschoben wurden, kann unter a zugegriffen werden konstante positive Verschiebung vom Rahmenzeiger.

Der Unterschied zwischen den beiden Konventionen liegt in der Art und Weise, wie sie einen Ausgang aus dem Unterprogramm behandeln. In der C-Konvention kopiert die Rückgabefunktion den Rahmenzeiger auf den Stapelzeiger [Wiederherstellen auf den Wert, den er unmittelbar nach dem Drücken des alten Rahmenzeigers hatte], öffnet den alten Rahmenzeigerwert und führt eine Rückgabe durch. Alle Parameter, die der Aufrufer vor dem Aufruf auf den Stapel gedrückt hat, bleiben dort. In der Pascal-Konvention öffnet der Prozessor nach dem Aufsetzen des alten Frame-Zeigers die Funktionsrückgabeadresse, fügt dem Stapelzeiger die Anzahl der vom Aufrufer gepuschten Parameterbytes hinzu und wechselt dann zur aufgesprungenen Rücksprungadresse. Auf dem ursprünglichen 68000 war es erforderlich, eine Sequenz mit drei Befehlen zu verwenden, um die Parameter des Anrufers zu entfernen. Die 8x86- und alle 680x0-Prozessoren nach dem Original enthielten ein "ret N".

Die Pascal-Konvention hat den Vorteil, dass auf der Aufruferseite ein wenig Code gespeichert wird, da der Aufrufer den Stapelzeiger nach einem Funktionsaufruf nicht aktualisieren muss. Es erfordert jedoch, dass die aufgerufene Funktion genau weiß, wie viele Bytes an Parametern der Aufrufer auf den Stapel legen wird. Wenn Sie nicht die richtige Anzahl von Parametern auf den Stapel übertragen, bevor Sie eine Funktion aufrufen, die die Pascal-Konvention verwendet, wird fast garantiert ein Absturz verursacht. Dies wird jedoch durch die Tatsache ausgeglichen, dass ein wenig zusätzlicher Code in jeder aufgerufenen Methode Code an den Stellen speichert, an denen die Methode aufgerufen wird. Aus diesem Grund verwendeten die meisten ursprünglichen Macintosh-Toolbox-Routinen die Pascal-Aufrufkonvention.

Die C-Aufrufkonvention hat den Vorteil, dass Routinen eine variable Anzahl von Parametern akzeptieren können und robust sind, selbst wenn eine Routine nicht alle übergebenen Parameter verwendet (der Aufrufer weiß, wie viele Bytes an Parametern er gesendet hat, und wird somit in der Lage sein, sie aufzuräumen). Außerdem muss nicht nach jedem Funktionsaufruf eine Stapelbereinigung durchgeführt werden. Wenn eine Routine nacheinander vier Funktionen aufruft, von denen jede Parameter im Wert von vier Bytes verwendet, kann sie - anstatt ADD SP,4nach jedem Aufruf eine zu verwenden, ADD SP,16nach dem letzten Aufruf eine verwenden, um die Parameter aller vier Aufrufe zu bereinigen.

Heutzutage gelten die beschriebenen Aufrufkonventionen als etwas veraltet. Da Compiler bei der Registernutzung effizienter geworden sind, ist es üblich, dass Methoden einige Parameter in Registern akzeptieren, anstatt dass alle Parameter auf den Stapel verschoben werden müssen. Wenn eine Methode Register verwenden kann, um alle Parameter und lokalen Variablen zu speichern, muss kein Frame-Zeiger verwendet werden, und daher muss der alte nicht gespeichert und wiederhergestellt werden. Dennoch ist es manchmal erforderlich, die älteren Aufrufkonventionen zu verwenden, wenn Bibliotheken aufgerufen werden, die für deren Verwendung verknüpft wurden.

Superkatze
quelle
1
Beeindruckend! Kann ich mir dein Gehirn für eine Woche oder so ausleihen? Müssen Sie ein paar Kleinigkeiten extrahieren! Gute Antwort!
Christoph
Wo werden der Frame und der Stapelzeiger im Stapel selbst oder anderswo gespeichert?
Suraj Jain
@SurajJain: Normalerweise wird jede gespeicherte Kopie des Frame-Zeigers mit einer festen Verschiebung relativ zum neuen Frame-Zeigerwert gespeichert.
Supercat
Sir, ich habe diesen Zweifel schon lange. Wenn ich in meiner Funktion if (g==4)then schreibe int d = 3und danach gEingaben mache scanf, definiere ich danach eine andere Variable int h = 5. Wie gibt der Compiler nun d = 3Platz im Stapel? Wie erfolgt der Versatz, denn wenn dies gnicht 4der Fall ist , gibt es keinen Speicher für d im Stapel, und es wird einfach ein Versatz angegeben, hund wenn g == 4dann der Versatz zuerst für g und dann für gilt h. Wie macht der Compiler das zur Kompilierungszeit? Er kennt unsere Eingabe fürg
Suraj Jain
@SurajJain: Frühere Versionen von C erforderten, dass alle automatischen Variablen innerhalb einer Funktion vor ausführbaren Anweisungen erscheinen müssen. Diese komplizierte Kompilierung wird etwas gelockert, aber ein Ansatz besteht darin, Code zu Beginn einer Funktion zu generieren, die den Wert eines vorwärts deklarierten Labels von SP subtrahiert. Innerhalb der Funktion kann der Compiler an jedem Punkt im Code verfolgen, wie viele Bytes von Einheimischen noch im Gültigkeitsbereich sind, und auch die maximale Anzahl von Bytes von Einheimischen verfolgen, die sich jemals im Gültigkeitsbereich befinden. Am Ende der Funktion kann es den Wert für die frühere ...
Supercat
5

Hier gibt es bereits einige wirklich gute Antworten. Wenn Sie jedoch immer noch über das LIFO-Verhalten des Stapels besorgt sind, stellen Sie sich diesen als einen Stapel von Frames und nicht als einen Stapel von Variablen vor. Ich möchte vorschlagen, dass eine Funktion zwar auf Variablen zugreifen kann, die sich nicht oben im Stapel befinden, jedoch nur für das Element oben im Stapel ausgeführt wird: einen einzelnen Stapelrahmen.

Natürlich gibt es Ausnahmen. Die lokalen Variablen der gesamten Anrufkette sind weiterhin zugeordnet und verfügbar. Sie werden jedoch nicht direkt aufgerufen. Stattdessen werden sie als Referenz (oder als Zeiger übergeben, was eigentlich nur semantisch anders ist). In diesem Fall kann auf eine lokale Variable eines Stapelrahmens viel weiter unten zugegriffen werden. Aber auch in diesem Fall arbeitet die aktuell ausgeführte Funktion nur mit ihren eigenen lokalen Daten. Es greift auf eine Referenz zu, die in einem eigenen Stapelrahmen gespeichert ist. Dies kann eine Referenz auf etwas auf dem Heap, im statischen Speicher oder weiter unten im Stapel sein.

Dies ist der Teil der Stapelabstraktion, der Funktionen in beliebiger Reihenfolge aufrufbar macht und eine Rekursion ermöglicht. Der obere Stapelrahmen ist das einzige Objekt, auf das der Code direkt zugreift. Auf alles andere wird indirekt zugegriffen (über einen Zeiger, der sich im oberen Stapelrahmen befindet).

Es kann lehrreich sein, sich die Zusammenstellung Ihres kleinen Programms anzusehen, insbesondere wenn Sie ohne Optimierung kompilieren. Ich denke, Sie werden sehen, dass der gesamte Speicherzugriff in Ihrer Funktion über einen Versatz vom Stapelrahmenzeiger erfolgt. Auf diese Weise wird der Code für die Funktion vom Compiler geschrieben. Im Fall einer Referenzübergabe würden Sie Anweisungen für den indirekten Speicherzugriff über einen Zeiger sehen, der in einem gewissen Versatz vom Stapelrahmenzeiger gespeichert ist.

Jeremy West
quelle
4

Der Aufrufstapel ist eigentlich keine Stapeldatenstruktur. Hinter den Kulissen sind die von uns verwendeten Computer Implementierungen der Maschinenarchitektur mit wahlfreiem Zugriff. Auf a und b kann also direkt zugegriffen werden.

Hinter den Kulissen macht die Maschine:

  • get "a" entspricht dem Lesen des Werts des vierten Elements unter der Stapeloberseite.
  • get "b" entspricht dem Lesen des Werts des dritten Elements unter der Stapeloberseite.

http://en.wikipedia.org/wiki/Random-access_machine

hdante
quelle
1

Hier ist ein Diagramm, das ich für den Aufrufstapel von C erstellt habe. Es ist genauer und zeitgemäßer als die Google-Bildversionen

Geben Sie hier die Bildbeschreibung ein

Entsprechend der genauen Struktur des obigen Diagramms finden Sie hier ein Debug von notepad.exe x64 unter Windows 7.

Geben Sie hier die Bildbeschreibung ein

Die niedrigen und hohen Adressen werden vertauscht, sodass der Stapel in diesem Diagramm nach oben steigt. Rot zeigt den Rahmen genau wie im ersten Diagramm an (das Rot und Schwarz verwendete, aber Schwarz wurde jetzt neu verwendet); Schwarz ist der Wohnraum; blau ist die Rücksprungadresse, die ein Versatz in der Aufruferfunktion zur Anweisung nach dem Aufruf ist; Orange ist die Ausrichtung und Pink ist die Stelle, an der der Befehlszeiger direkt nach dem Aufruf und vor dem ersten Befehl zeigt. Der Homespace + Return-Wert ist der kleinste zulässige Frame in Windows. Da die 16-Byte-rsp-Ausrichtung direkt zu Beginn der aufgerufenen Funktion beibehalten werden muss, umfasst dies immer auch eine 8-Byte-Ausrichtung.BaseThreadInitThunk und so weiter.

Die roten Funktionsrahmen umreißen, was die Angerufene Funktion logisch "besitzt" + liest / ändert (sie kann einen Parameter ändern, der auf dem Stapel übergeben wurde, der zu groß war, um in einem Register auf -Ofast übergeben zu werden). Die grünen Linien markieren den Raum, den sich die Funktion vom Anfang bis zum Ende der Funktion zuweist.

Lewis Kelsey
quelle
RDI- und andere Registerargumente werden nur dann auf den Stapel verschüttet, wenn Sie im Debug-Modus kompilieren, und es gibt keine Garantie dafür, dass eine Kompilierung diese Reihenfolge auswählt. Warum werden Stapelargumente für den ältesten Funktionsaufruf nicht oben im Diagramm angezeigt? In Ihrem Diagramm gibt es keine klare Abgrenzung zwischen dem Frame, der welche Daten "besitzt". (Ein Angerufene besitzt seine Stapelargumente). Wenn Sie die Stapelargumente oben im Diagramm weglassen, wird es noch schwieriger zu erkennen, dass "Parameter, die nicht in Registern übergeben werden können", immer direkt über der Rücksprungadresse jeder Funktion liegen.
Peter Cordes
Die Ausgabe von @PeterCordes goldbolt asm zeigt clang- und gcc-Callees an, die einen in einem Register übergebenen Parameter als Standardverhalten an den Stack senden, sodass er eine Adresse hat. Wenn Sie gcc registerhinter dem Parameter verwenden, wird dies optimiert, aber Sie würden denken, dass dies ohnehin optimiert wird, da die Adresse niemals innerhalb der Funktion verwendet wird. Ich werde den oberen Rahmen reparieren; Zugegeben, ich hätte die Auslassungspunkte in einen separaten leeren Rahmen setzen sollen. 'Ein Angerufene besitzt seine Stack-Argumente', was schließt diejenigen ein, die der Anrufer drückt, wenn sie nicht in Registern übergeben werden können?
Lewis Kelsey
Ja, wenn Sie mit deaktivierter Optimierung kompilieren, wird der Angerufene es irgendwo verschütten. Aber im Gegensatz zur Position von Stack-Args (und wohl gespeicherten RBP) ist nichts standardisiert, wo. Re: callee besitzt seine Stack-Argumente: Ja, Funktionen dürfen ihre eingehenden Argumente ändern. Die Reg-Argumente, die es selbst verschüttet, sind keine Stapel-Argumente. Compiler tun dies manchmal, aber IIRC verschwenden häufig Stapelspeicherplatz, indem sie Speicherplatz unterhalb der Rücksprungadresse verwenden, selbst wenn sie das Argument nie wieder lesen. Wenn ein Anrufer einen weiteren Anruf mit denselben Argumenten tätigen möchte, muss er aus Sicherheitsgründen eine weitere Kopie speichern, bevor er dencall
Peter Cordes
@PeterCordes Nun, ich habe die Argumente zum Teil des Aufruferstapels gemacht, weil ich die Stapelrahmen basierend darauf abgegrenzt habe, wo rbp zeigt. Einige Diagramme zeigen dies als Teil des Angerufenen-Stapels (wie das erste Diagramm zu dieser Frage) und andere zeigen es als Teil des Aufrufer-Stapels, aber vielleicht ist es sinnvoll, sie als Parameterbereich als Teil des Angerufenen-Stapels zu betrachten ist für den Anrufer im Code höherer Ebene nicht zugänglich. Ja, es scheint, registerund constOptimierungen machen nur bei -O0 einen Unterschied.
Lewis Kelsey
@ PeterCordes Ich habe es geändert. Ich könnte es aber noch einmal ändern
Lewis Kelsey