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 a
und zu arbeiten b
, aber das würde bedeuten, dass das Betriebssystem / die CPU (?) Herausspringen muss d
undc
zuerst zu a
und zurückkehren muss b
. Aber dann würde es sich in den Fuß schießen, weil es braucht c
und d
in 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 doSomething
im Wesentlichen auf dieselbe Speicheradresse wie a
und b
in verweisen foo
. Andererseits bedeutet dies, dass es keine gibt der Stapel erst dann angezeigt wird, wenn wir zu a
undb
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.
LIFO
Sie können Elemente nur am Ende des Stapels hinzufügen oder entfernen und jedes Element jederzeit lesen / ändern.Antworten:
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 :
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
gcc.godbolt.org gibt uns
.. für
main
. Ich habe den Code in drei Unterabschnitte unterteilt. Der Funktionsprolog besteht aus den ersten drei Operationen:Dann
cin
wird in das EDI-Register 2 verschoben undget
aufgerufen; 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 wirdc
in EAX gespeichert: EAX wird in ESI verschoben,cout
wird in EDI verschoben und dann wird der Einfügeoperator mitcout
undc
als Argument aufgerufen .Schließlich,
main
wird in EAX: 0 gespeichert. Dies liegt an der implizitenreturn
Anweisung. Sie könnten auchxorl rax rax
anstelle von sehenmovl
.leave
verkürzt diesen Epilog und implizitNach dieser Operation und nachdem
ret
sie 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 übergibtret
.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-pointer
in GCC und-Oy
in 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.
quelle
rbp
andere Arbeiten ausführen .Zusamenfassend:
Die Argumente müssen nicht eingeblendet werden. Die vom Aufrufer
foo
an function übergebenen ArgumentedoSomething
und die lokalen Variablen indoSomething
können alle als Offset vom Basiszeiger referenziert werden .So,
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
funcA
AnrufefuncB
undfuncB
Aufrufe ausgeführt werdenfuncC
, 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).Der Stapel in Ihrer Frage wird vom Anrufer eingerichtet
foo
. WenndoSomething
unddoAnotherThing
aufgerufen werden, richten sie ihren eigenen Stack ein. Die Abbildung kann Ihnen helfen, dies zu verstehen: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.
Schauen Sie sich den folgenden C-Code für die Bildung des Stapelrahmens der Funktion an:
Wenn Anrufer es anrufen
Der folgende Code wird generiert
und der Assembler-Code für die Funktion lautet (von Angerufenen vor der Rückkehr eingerichtet)
Verweise:
quelle
EBP
undESP
?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:
Die Zeitpunkte
T1, T2, etc
. sind im Code markiert und der Speicherstatus zu diesem Zeitpunkt ist in der Zeichnung dargestellt:quelle
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,4
nach jedem Aufruf eine zu verwenden,ADD SP,16
nach 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.
quelle
(g==4)
then schreibeint d = 3
und danachg
Eingaben machescanf
, definiere ich danach eine andere Variableint h = 5
. Wie gibt der Compiler nund = 3
Platz im Stapel? Wie erfolgt der Versatz, denn wenn diesg
nicht4
der Fall ist , gibt es keinen Speicher für d im Stapel, und es wird einfach ein Versatz angegeben,h
und wenng == 4
dann der Versatz zuerst für g und dann für gilth
. Wie macht der Compiler das zur Kompilierungszeit? Er kennt unsere Eingabe fürg
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.
quelle
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:
http://en.wikipedia.org/wiki/Random-access_machine
quelle
Hier ist ein Diagramm, das ich für den Aufrufstapel von C erstellt habe. Es ist genauer und zeitgemäßer als die Google-Bildversionen
Entsprechend der genauen Struktur des obigen Diagramms finden Sie hier ein Debug von notepad.exe x64 unter Windows 7.
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.
quelle
register
hinter 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?call
register
undconst
Optimierungen machen nur bei -O0 einen Unterschied.