Wie funktioniert der Stack in Assemblersprache?

Ich versuche gerade zu verstehen, wie der Stapel funktioniert, daher habe ich beschlossen, mir eine Assemblersprache beizubringen. Ich verwende dieses Buch:

http://savannah.nongnu.org/projects/pgubook/

Ich benutze Gas und entwickle unter Linux Mint .

Ich bin etwas verwirrt von etwas:

Soweit mir bekannt ist, ist ein Stack einfach eine Datenstruktur. Ich ging also davon aus, dass ich den Stack selbst implementieren müsste, wenn ich in Assembly codieren würde. Dies scheint jedoch nicht der Fall zu sein, da es Befehle wie gibt

pushl
popl

Wenn Sie also in Assembly für die x86- Architektur codieren und die Gassyntax verwenden: Ist der Stack nur eine Datenstruktur, die bereits implementiert ist? Oder ist es tatsächlich auf Hardwareebene implementiert? Oder ist es etwas anderes? Würden die meisten Assemblersprachen für andere Chipsätze den Stack bereits implementiert haben?

Ich weiß, dass dies eine etwas dumme Frage ist, aber das verwirrt mich tatsächlich ziemlich.

Ich denke in erster Linie verwirrt man sich zwischen a program's stackund any old stack.

Ein Stapel

Ist eine abstrakte Datenstruktur, die aus Informationen in einem Last In First Out-System besteht. Sie legen beliebige Objekte auf den Stapel und nehmen sie dann wieder ab, ähnlich wie bei einem Ein- / Aus-Fach. Das oberste Element ist immer das, das abgenommen wird, und Sie legen es immer oben ab.

Ein Programmstapel

Ist ein Stapel, es ist ein Speicherabschnitt, der während der Ausführung verwendet wird, er hat im Allgemeinen eine statische Größe pro Programm und wird häufig zum Speichern von Funktionsparametern verwendet. Sie verschieben die Parameter auf den Stapel, wenn Sie eine Funktion aufrufen, und die Funktion adressiert entweder den Stapel direkt oder entfernt die Variablen vom Stapel.

Ein Programmstapel ist im Allgemeinen keine Hardware (obwohl er im Speicher gespeichert ist, damit er als solcher argumentiert werden kann), aber der Stapelzeiger, der auf einen aktuellen Bereich des Stapels zeigt, ist im Allgemeinen ein CPU-Register. Dies macht es etwas flexibler als ein LIFO-Stapel, da Sie den Punkt ändern können, an dem der Stapel adressiert.

Sie sollten den Wikipedia- Artikel lesen und sicherstellen, dass er eine gute Beschreibung des Hardware-Stacks enthält, mit dem Sie es zu tun haben.

Es gibt auch dieses Tutorial, das den Stack anhand der alten 16-Bit-Register erklärt, aber hilfreich sein könnte, und ein anderes, das sich speziell mit dem Stack befasst.

Von Nils Pipenbrinck:

Es ist anzumerken, dass einige Prozessoren nicht alle Anweisungen für den Zugriff auf und die Bearbeitung des Stapels (Push, Pop, Stapelzeiger usw.) implementieren, der x86 jedoch aufgrund seiner Verwendungshäufigkeit. Wenn Sie in diesen Situationen einen Stapel wünschen, müssen Sie ihn selbst implementieren (einige MIPS- und einige ARM-Prozessoren werden ohne Stapel erstellt).

Zum Beispiel würde in MIPs eine Push-Anweisung implementiert werden wie:

addi $sp, $sp, -4  # Decrement stack pointer by 4  
sw   $t0, ($sp)   # Save $t0 to stack  

und eine Pop-Anweisung würde aussehen wie:

lw   $t0, ($sp)   # Copy from stack to $t0  
addi $sp, $sp, 4   # Increment stack pointer by 4  

(Ich habe einen gemacht Kern aller Code in dieser Antwort , falls Sie mit ihm spielen wollen)

Ich habe während meines CS101-Kurses im Jahr 2003 immer nur die grundlegendsten Dinge in asm gemacht. Und ich hatte nie wirklich "verstanden", wie asm und Stack funktionieren, bis mir klar wurde, dass alles grundlegend wie das Programmieren in C oder C ++ ist ... aber ohne lokale Variablen, Parameter und Funktionen. Klingt wahrscheinlich noch nicht einfach :) Lassen Sie sich von mir zeigen (für x86 asm mit Intel-Syntax ).

1. Was ist der Stapel?

Der Stapel ist normalerweise ein zusammenhängender Speicherblock, der jedem Thread zugewiesen wird, bevor er gestartet wird. Sie können dort speichern, was Sie wollen. In C ++ - Begriffen ( Code-Snippet Nr. 1 ):

const int STACK_CAPACITY = 1000;
thread_local int stack[STACK_CAPACITY];

2. Stapel oben und unten

Im Prinzip können Sie Werte in zufälligen Zellen des stackArrays speichern ( Snippet Nr. 2.1 ):

stack[333] = 123;
stack[517] = 456;
stack[555] = stack[333] + stack[517];

Aber stellen Sie sich vor, wie schwer es wäre, sich daran zu erinnern, welche Zellen stackbereits verwendet werden und welche "frei" sind. Deshalb speichern wir neue Werte nebeneinander auf dem Stapel.

Eine seltsame Sache am Stapel von (x86) asm ist, dass Sie dort Dinge hinzufügen, die mit dem letzten Index beginnen, und zu niedrigeren Indizes wechseln: Stapel [999], dann Stapel [998] und so weiter ( Snippet # 2.2 ):

stack[999] = 123;
stack[998] = 456;
stack[997] = stack[999] + stack[998];

Und nach wie vor (Vorsicht, du bist jetzt verwirrt Gonna werden) , um den „offiziellen“ Namen stack[999]ist der Stapelboden .
Die zuletzt verwendete Zelle ( stack[997]im obigen Beispiel) wird als Oberseite des Stapels bezeichnet (siehe Wo sich die Oberseite des Stapels auf x86 befindet ).

3. Stapelzeiger (SP)

Für die Zwecke dieser Diskussion nehmen wir an, dass CPU-Register als globale Variablen dargestellt werden (siehe Allzweckregister ).

int AX, BX, SP, BP, ...;
int main(){...}

Es gibt ein spezielles CPU-Register (SP), das die Oberseite des Stapels verfolgt. SP ist ein Zeiger (enthält eine Speicheradresse wie 0xAAAABBCC). Aber für die Zwecke dieses Beitrags werde ich ihn als Array-Index verwenden (0, 1, 2, ...).

Wenn ein Thread SP == STACK_CAPACITYgestartet wird und das Programm und das Betriebssystem ihn nach Bedarf ändern. Die Regel ist, dass Sie nicht in Stapelzellen schreiben können, die über den Stapel hinausgehen, und dass ein Index, der kleiner als SP ist, ungültig und unsicher ist (aufgrund von Systemunterbrechungen ). Sie dekrementieren also zuerst SP und schreiben dann einen Wert in die neu zugewiesene Zelle.

Wenn Sie mehrere Werte hintereinander in den Stapel verschieben möchten, können Sie im Voraus Speicherplatz für alle Werte reservieren ( Snippet 3 ):

SP -= 3;
stack[999] = 12;
stack[998] = 34;
stack[997] = stack[999] + stack[998];

Hinweis. Jetzt können Sie sehen, warum die Zuordnung auf dem Stapel so schnell ist - es ist nur eine einzelne Registerdekrementierung.

4. Lokale Variablen

Werfen wir einen Blick auf diese vereinfachende Funktion ( Snippet # 4.1 ):

int triple(int a) {
    int result = a * 3;
    return result;
}

und schreiben Sie es neu, ohne die lokale Variable zu verwenden ( Snippet # 4.2 ):

int triple_noLocals(int a) {
    SP -= 1; // move pointer to unused cell, where we can store what we need
    stack[SP] = a * 3;
    return stack[SP];
}

und sehen, wie es aufgerufen wird ( Snippet # 4.3 ):

// SP == 1000
someVar = triple_noLocals(11);
// now SP == 999, but we don't need the value at stack[999] anymore
// and we will move the stack index back, so we can reuse this cell later
SP += 1; // SP == 1000 again

5. Push / Pop

Das Hinzufügen eines neuen Elements oben auf dem Stapel ist eine so häufige Operation, dass CPUs eine spezielle Anweisung dafür haben push. Wir werden es so implementieren ( Snippet 5.1 ):

void push(int value) {
    --SP;
    stack[SP] = value;
}

Ebenso das oberste Element des Stapels ( Snippet 5.2 ):

void pop(int& result) {
    result = stack[SP];
    ++SP; // note that `pop` decreases stack's size
}

Das übliche Verwendungsmuster für Push / Pop spart vorübergehend etwas Wert. Angenommen, wir haben etwas Nützliches in Variablen myVarund aus irgendeinem Grund müssen wir Berechnungen durchführen, die es überschreiben ( Snippet 5.3 ):

int myVar = ...;
push(myVar); // SP == 999
myVar += 10;
... // do something with new value in myVar
pop(myVar); // restore original value, SP == 1000

6. Funktionsparameter

Übergeben wir nun die Parameter mit dem Stack ( Snippet Nr. 6 ):

int triple_noL_noParams() { // `a` is at index 999, SP == 999
    SP -= 1; // SP == 998, stack[SP + 1] == a
    stack[SP] = stack[SP + 1] * 3;
    return stack[SP];
}

int main(){
    push(11); // SP == 999
    assert(triple(11) == triple_noL_noParams());
    SP += 2; // cleanup 1 local and 1 parameter
}

7. returnAussage

Lassen Sie uns den Wert im AX-Register zurückgeben ( Snippet # 7 ):

void triple_noL_noP_noReturn() { // `a` at 998, SP == 998
    SP -= 1; // SP == 997

    stack[SP] = stack[SP + 1] * 3;
    AX = stack[SP];

    SP += 1; // finally we can cleanup locals right in the function body, SP == 998
}

void main(){
    ... // some code
    push(AX); // save AX in case there is something useful there, SP == 999
    push(11); // SP == 998
    triple_noL_noP_noReturn();
    assert(triple(11) == AX);
    SP += 1; // cleanup param
             // locals were cleaned up in the function body, so we don't need to do it here
    pop(AX); // restore AX
    ...
}

8. Stapelbasiszeiger (BP) (auch als Rahmenzeiger bezeichnet ) und Stapelrahmen

Nehmen wir die "erweiterte" Funktion und schreiben sie in unserem asm-ähnlichen C ++ ( Snippet # 8.1 ) neu:

int myAlgo(int a, int b) {
    int t1 = a * 3;
    int t2 = b * 3;
    return t1 - t2;
}

void myAlgo_noLPR() { // `a` at 997, `b` at 998, old AX at 999, SP == 997
    SP -= 2; // SP == 995

    stack[SP + 1] = stack[SP + 2] * 3; 
    stack[SP]     = stack[SP + 3] * 3;
    AX = stack[SP + 1] - stack[SP];

    SP += 2; // cleanup locals, SP == 997
}

int main(){
    push(AX); // SP == 999
    push(22); // SP == 998
    push(11); // SP == 997
    myAlgo_noLPR();
    assert(myAlgo(11, 22) == AX);
    SP += 2;
    pop(AX);
}

Stellen Sie sich nun vor, wir haben beschlossen, eine neue lokale Variable einzuführen, um das Ergebnis dort zu speichern, bevor wir zurückkehren, wie in tripple(Snippet # 4.1). Der Hauptteil der Funktion ist ( Snippet # 8.2 ):

SP -= 3; // SP == 994
stack[SP + 2] = stack[SP + 3] * 3; 
stack[SP + 1] = stack[SP + 4] * 3;
stack[SP]     = stack[SP + 2] - stack[SP + 1];
AX = stack[SP];
SP += 3;

Sie sehen, wir mussten jeden einzelnen Verweis auf Funktionsparameter und lokale Variablen aktualisieren. Um dies zu vermeiden, benötigen wir einen Ankerindex, der sich nicht ändert, wenn der Stapel wächst.

Wir erstellen den Anker direkt bei der Funktionseingabe (bevor wir Platz für Einheimische zuweisen), indem wir die aktuelle Spitze (Wert von SP) im BP-Register speichern. Snippet # 8.3 :

void myAlgo_noLPR_withAnchor() { // `a` at 997, `b` at 998, SP == 997
    push(BP);   // save old BP, SP == 996
    BP = SP;    // create anchor, stack[BP] == old value of BP, now BP == 996
    SP -= 2;    // SP == 994

    stack[BP - 1] = stack[BP + 1] * 3;
    stack[BP - 2] = stack[BP + 2] * 3;
    AX = stack[BP - 1] - stack[BP - 2];

    SP = BP;    // cleanup locals, SP == 996
    pop(BP);    // SP == 997
}

Die Scheibe des Stapels, Weichen gehört und ist in der vollen Kontrolle über die Funktion aufgerufen Funktion des Stapelrahmen . ZB myAlgo_noLPR_withAnchorist der stack[996 .. 994]Stapelrahmen (beide Ideen inklusive).
Der Frame beginnt beim BP der Funktion (nachdem wir ihn innerhalb der Funktion aktualisiert haben) und dauert bis zum nächsten Stack-Frame. Die Parameter auf dem Stapel sind also Teil des Stapelrahmens des Aufrufers (siehe Anmerkung 8a).

Anmerkungen:
8a. Wikipedia sagt etwas anderes über Parameter, aber hier halte ich mich an das Handbuch für Intel-Softwareentwickler , siehe Bd. 1, Abschnitt 6.2.4.1 Stack-Frame Base Pointer und Abbildung 6-2 in Abschnitt 6.3.2 Far CALL and RET Operation . Die Funktionsparameter und der Stapelrahmen sind Teil des Aktivierungsdatensatzes der Funktion (siehe Die Funktionsperiloge ).
8b. Positive Offsets vom BP-Punkt zu Funktionsparametern und negative Offsets zeigen zu lokalen Variablen. Das ist ziemlich praktisch zum Debuggen von
8c. stack[BP]speichert die Adresse des vorherigen Stapelrahmens,stack[stack[BP]]speichert den vorherigen Stapelrahmen und so weiter. Nach dieser Kette können Sie Frames aller Funktionen im Programm erkennen, die noch nicht zurückgegeben wurden. So zeigen Debugger, dass Sie Stack
8d aufrufen . Die ersten drei Anweisungen myAlgo_noLPR_withAnchor, in denen wir den Frame einrichten (alten BP speichern, BP aktualisieren, Speicherplatz für Einheimische reservieren), werden als Funktionsprolog bezeichnet

9. Aufrufen von Konventionen

In Snippet 8.1 haben wir die Parameter für myAlgovon rechts nach links verschoben und das Ergebnis zurückgegeben AX. Wir könnten genauso gut die Parameter von links nach rechts übergeben und zurückkehren BX. Oder übergeben Sie Parameter in BX und CX und kehren Sie in AX zurück. Offensichtlich müssen caller ( main()) und die aufgerufene Funktion übereinstimmen, wo und in welcher Reihenfolge all diese Dinge gespeichert sind.

Die Aufrufkonvention besteht aus einer Reihe von Regeln für die Übergabe von Parametern und die Rückgabe des Ergebnisses.

Im obigen Code haben wir die cdecl-Aufrufkonvention verwendet :

• Parameter werden auf dem Stapel übergeben, wobei sich das erste Argument zum Zeitpunkt des Aufrufs an der niedrigsten Adresse auf dem Stapel befindet (zuletzt gedrückt <...>). Der Aufrufer ist dafür verantwortlich, dass die Parameter nach dem Aufruf wieder vom Stapel entfernt werden.
• Der Rückgabewert wird in AX platziert
• EBP und ESP müssen vom Angerufenen ( myAlgo_noLPR_withAnchorin unserem Fall mainFunktion) beibehalten werden , damit sich der Anrufer ( Funktion) darauf verlassen kann , dass diese Register nicht durch einen Anruf geändert wurden.
• Alle anderen Register (EAX, <...>) können vom Angerufenen frei geändert werden. Wenn ein Aufrufer einen Wert vor und nach dem Funktionsaufruf beibehalten möchte, muss er den Wert an einer anderen Stelle speichern (dies geschieht mit AX).

^{(Quelle: Beispiel "32-Bit-Cdecl" aus der Stack Overflow-Dokumentation; Copyright 2016 von icktoofay und Peter Cordes ; lizenziert unter CC BY-SA 3.0. Ein Archiv des vollständigen Inhalts der Stack Overflow-Dokumentation finden Sie unter archive.org Dieses Beispiel ist nach Themen-ID 3261 und Beispiel-ID 11196 indiziert.)}

10. Funktionsaufrufe

Nun der interessanteste Teil. Genau wie Daten wird auch ausführbarer Code im Speicher gespeichert (völlig unabhängig vom Speicher für den Stapel), und jeder Befehl hat eine Adresse.
Wenn nicht anders befohlen, führt die CPU die Anweisungen nacheinander in der Reihenfolge aus, in der sie im Speicher gespeichert sind. Wir können der CPU jedoch befehlen, an eine andere Stelle im Speicher zu "springen" und von dort aus Anweisungen auszuführen. In asm kann es sich um eine beliebige Adresse handeln, und in höheren Sprachen wie C ++ können Sie nur zu Adressen springen, die durch Beschriftungen gekennzeichnet sind ( es gibt Problemumgehungen, aber sie sind, gelinde gesagt, nicht hübsch).

Nehmen wir diese Funktion ( Snippet # 10.1 ):

int myAlgo_withCalls(int a, int b) {
    int t1 = triple(a);
    int t2 = triple(b);
    return t1 - t2;
}

Und anstatt trippleC ++ so aufzurufen , gehen Sie wie folgt vor:

1. Kopieren Sie trippleden Code an den Anfang des myAlgoKörpers
2. bei der myAlgoEingabe über trippleden Code mit springengoto
3. Wenn wir den trippleCode ausführen müssen, speichern Sie die Stapeladresse der Codezeile direkt nach dem trippleAufruf, damit wir später hierher zurückkehren und die Ausführung fortsetzen können ( PUSH_ADDRESSMakro unten).
4. Springe zur Adresse der 1. Zeile ( trippleFunktion) und führe sie bis zum Ende aus (3. und 4. sind zusammen CALLMakro)
5. trippleNehmen Sie am Ende von (nachdem wir die Einheimischen aufgeräumt haben) die Absenderadresse vom oberen Rand des Stapels und springen Sie dorthin ( RETMakro).

Da es in C ++ keine einfache Möglichkeit gibt, zu einer bestimmten Codeadresse zu springen, verwenden wir Beschriftungen, um Sprungstellen zu markieren. Ich werde nicht ins Detail gehen, wie die folgenden Makros funktionieren. Glauben Sie mir einfach, dass sie das tun, was ich sage ( Ausschnitt Nr. 10.2 ):

// pushes the address of the code at label's location on the stack
// NOTE1: this gonna work only with 32-bit compiler (so that pointer is 32-bit and fits in int)
// NOTE2: __asm block is specific for Visual C++. In GCC use https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html
#define PUSH_ADDRESS(labelName) {               \
    void* tmpPointer;                           \
    __asm{ mov [tmpPointer], offset labelName } \
    push(reinterpret_cast<int>(tmpPointer));    \
}

// why we need indirection, read https://stackoverflow.com/a/13301627/264047
#define TOKENPASTE(x, y) x ## y
#define TOKENPASTE2(x, y) TOKENPASTE(x, y)

// generates token (not a string) we will use as label name. 
// Example: LABEL_NAME(155) will generate token `lbl_155`
#define LABEL_NAME(num) TOKENPASTE2(lbl_, num)

#define CALL_IMPL(funcLabelName, callId)    \
    PUSH_ADDRESS(LABEL_NAME(callId));       \
    goto funcLabelName;                     \
    LABEL_NAME(callId) :

// saves return address on the stack and jumps to label `funcLabelName`
#define CALL(funcLabelName) CALL_IMPL(funcLabelName, __LINE__)

// takes address at the top of stack and jump there
#define RET() {                                         \
    int tmpInt;                                         \
    pop(tmpInt);                                        \
    void* tmpPointer = reinterpret_cast<void*>(tmpInt); \
    __asm{ jmp tmpPointer }                             \
}

void myAlgo_asm() {
    goto my_algo_start;

triple_label:
    push(BP);
    BP = SP;
    SP -= 1;

    // stack[BP] == old BP, stack[BP + 1] == return address
    stack[BP - 1] = stack[BP + 2] * 3;
    AX = stack[BP - 1];

    SP = BP;     
    pop(BP);
    RET();

my_algo_start:
    push(BP);   // SP == 995
    BP = SP;    // BP == 995; stack[BP] == old BP, 
                // stack[BP + 1] == dummy return address, 
                // `a` at [BP + 2], `b` at [BP + 3]
    SP -= 2;    // SP == 993

    push(AX);
    push(stack[BP + 2]);
    CALL(triple_label);
    stack[BP - 1] = AX;
    SP -= 1;
    pop(AX);

    push(AX);
    push(stack[BP + 3]);
    CALL(triple_label);
    stack[BP - 2] = AX;
    SP -= 1;
    pop(AX);

    AX = stack[BP - 1] - stack[BP - 2];

    SP = BP; // cleanup locals, SP == 997
    pop(BP);
}

int main() {
    push(AX);
    push(22);
    push(11);
    push(7777); // dummy value, so that offsets inside function are like we've pushed return address
    myAlgo_asm();
    assert(myAlgo_withCalls(11, 22) == AX);
    SP += 1; // pop dummy "return address"
    SP += 2;
    pop(AX);
}

Anmerkungen:
10a. Da die Absenderadresse auf dem Stapel gespeichert ist, können wir sie im Prinzip ändern. Dies ist , wie Stack Smashing Angriff funktioniert
10b. Die letzten 3 Anweisungen am "Ende" von triple_label(Lokale bereinigen, alten BP wiederherstellen, zurückgeben) werden als Epilog der Funktion bezeichnet

11. Montage

Nun schauen wir uns real asm an myAlgo_withCalls. So machen Sie das in Visual Studio:

• setze Build-Plattform auf x86 ( nicht x86_64)
• Build-Typ: Debug
• Setze den Haltepunkt irgendwo in myAlgo_withCalls
• Ausführen und wenn die Ausführung am Haltepunkt stoppt, drücken Sie Strg + Alt + D.

Ein Unterschied zu unserem asm-ähnlichen C ++ besteht darin, dass der Stapel von asm mit Bytes statt mit Ints arbeitet. Um Platz für einen zu reservieren int, wird SP um 4 Bytes dekrementiert.
Los geht's ( Snippet # 11.1 , Zeilennummern in Kommentaren stammen aus dem Kern ):

;   114: int myAlgo_withCalls(int a, int b) {
 push        ebp        ; create stack frame 
 mov         ebp,esp  
; return address at (ebp + 4), `a` at (ebp + 8), `b` at (ebp + 12)
 
 sub         esp,0D8h   ; reserve space for locals. Compiler can reserve more bytes then needed. 0D8h is hexadecimal == 216 decimal 
 
 push        ebx        ; cdecl requires to save all these registers
 push        esi  
 push        edi  
 
 ; fill all the space for local variables (from (ebp-0D8h) to (ebp)) with value 0CCCCCCCCh repeated 36h times (36h * 4 == 0D8h)
 ; see https://stackoverflow.com/q/3818856/264047
 ; I guess that's for ease of debugging, so that stack is filled with recognizable values
 ; 0CCCCCCCCh in binary is 110011001100...
 lea         edi,[ebp-0D8h]     
 mov         ecx,36h    
 mov         eax,0CCCCCCCCh  
 rep stos    dword ptr es:[edi]  
 
;   115:    int t1 = triple(a);
 mov         eax,dword ptr [ebp+8]   ; push parameter `a` on the stack
 push        eax  
 
 call        triple (01A13E8h)  
 add         esp,4                   ; clean up param 
 mov         dword ptr [ebp-8],eax   ; copy result from eax to `t1`
 
;   116:    int t2 = triple(b);
 mov         eax,dword ptr [ebp+0Ch] ; push `b` (0Ch == 12)
 push        eax  
 
 call        triple (01A13E8h)  
 add         esp,4  
 mov         dword ptr [ebp-14h],eax ; t2 = eax
 
 mov         eax,dword ptr [ebp-8]   ; calculate and store result in eax
 sub         eax,dword ptr [ebp-14h]  

 pop         edi  ; restore registers
 pop         esi  
 pop         ebx  
 
 add         esp,0D8h  ; check we didn't mess up esp or ebp. this is only for debug builds
 cmp         ebp,esp  
 call        __RTC_CheckEsp (01A116Dh)  
 
 mov         esp,ebp  ; destroy frame
 pop         ebp  
 ret  

Und asm für tripple( Snippet # 11.2 ):

 push        ebp  
 mov         ebp,esp  
 sub         esp,0CCh  
 push        ebx  
 push        esi  
 push        edi  
 lea         edi,[ebp-0CCh]  
 mov         ecx,33h  
 mov         eax,0CCCCCCCCh  
 rep stos    dword ptr es:[edi]  
 imul        eax,dword ptr [ebp+8],3  
 mov         dword ptr [ebp-8],eax  
 mov         eax,dword ptr [ebp-8]  
 pop         edi  
 pop         esi  
 pop         ebx  
 mov         esp,ebp  
 pop         ebp  
 ret  

Hoffe, nach dem Lesen dieses Beitrags sieht die Montage nicht mehr so ​​kryptisch aus wie zuvor :)

Hier sind Links aus dem Beitrag und einige weitere Informationen:

• Eli Bendersky , Wo sich die Oberseite des Stapels auf x86 befindet - oben / unten, Push / Pop, SP, Stapelrahmen, Aufrufkonventionen
• Eli Bendersky , Stapelrahmenlayout auf x86-64 - Argumente, die x64 weitergeben, Stapelrahmen, rote Zone
• University of Mariland, Understanding the Stack - eine wirklich gut geschriebene Einführung in Stack-Konzepte. (Es ist für MIPS (nicht x86) und in GAS-Syntax, aber dies ist für das Thema unbedeutend). Weitere Informationen zur MIPS ISA-Programmierung finden Sie bei Interesse.
• x86 Asm Wikibook, Allzweckregister
• x86 Demontage Wikibook, The Stack
• x86 Demontage-Wikibook, Funktionen und Stapelrahmen
• Handbücher für Intel-Softwareentwickler - Ich habe erwartet, dass es wirklich Hardcore ist, aber überraschenderweise ist es ziemlich einfach zu lesen (obwohl die Menge an Informationen überwältigend ist).
• Jonathan de Boyne Pollard, Die Gen-on-Funktions-Periloge - Prolog / Epilog, Stapelrahmen / Aktivierungsdatensatz, rote Zone

In Bezug darauf, ob der Stack in der Hardware implementiert ist, kann dieser Wikipedia-Artikel hilfreich sein.

Einige Prozessorfamilien, wie z. B. x86, verfügen über spezielle Anweisungen zum Bearbeiten des Stapels des aktuell ausgeführten Threads. Andere Prozessorfamilien, einschließlich PowerPC und MIPS, bieten keine explizite Stapelunterstützung, sondern verlassen sich auf Konventionen und delegieren die Stapelverwaltung an die Application Binary Interface (ABI) des Betriebssystems.

Dieser und die anderen Artikel, auf die verwiesen wird, können hilfreich sein, um ein Gefühl für die Stapelverwendung in Prozessoren zu bekommen.

Das Konzept

Denken Sie zuerst an das Ganze, als wären Sie die Person, die es erfunden hat. So was:

Stellen Sie sich zunächst ein Array vor und wie es auf niedriger Ebene implementiert wird -> es handelt sich im Grunde genommen nur um eine Reihe zusammenhängender Speicherorte (Speicherplätze, die nebeneinander liegen). Nachdem Sie dieses mentale Bild in Ihrem Kopf haben, denken Sie an die Tatsache, dass Sie auf JEDEN dieser Speicherorte zugreifen und es nach Belieben löschen können, wenn Sie Daten in Ihrem Array entfernen oder hinzufügen. Denken Sie jetzt an dasselbe Array, aber anstatt der Möglichkeit, einen beliebigen Speicherort zu löschen, entscheiden Sie, dass Sie nur den LETZTEN Speicherort löschen, wenn Sie Daten in Ihrem Array entfernen oder hinzufügen. Jetzt heißt Ihre neue Idee, die Daten in diesem Array auf diese Weise zu manipulieren, LIFO, was "Last In First Out" bedeutet. Ihre Idee ist sehr gut, da es einfacher ist, den Inhalt dieses Arrays zu verfolgen, ohne jedes Mal, wenn Sie etwas daraus entfernen, einen Sortieralgorithmus verwenden zu müssen. Ebenfalls, Um jederzeit zu wissen, wie die Adresse des letzten Objekts im Array lautet, widmen Sie ein Register in der CPU, um den Überblick zu behalten. Das Register verfolgt dies nun so, dass Sie jedes Mal, wenn Sie etwas entfernen oder zu Ihrem Array hinzufügen, den Wert der Adresse in Ihrem Register um die Anzahl der Objekte verringern oder erhöhen, die Sie aus dem Array entfernt oder hinzugefügt haben (um die Menge des von ihnen belegten Adressraums). Sie möchten auch sicherstellen, dass der Betrag, um den Sie dieses Register dekrementieren oder inkrementieren, auf einen Betrag (wie 4 Speicherplätze, dh 4 Bytes) pro Objekt festgelegt ist, um das Verfolgen zu erleichtern und es auch zu ermöglichen um dieses Register mit einigen Schleifenkonstrukten zu verwenden, da Schleifen eine feste Inkrementierung pro Iteration verwenden (z. Um Ihr Array mit einer Schleife zu durchlaufen, konstruieren Sie die Schleife, um Ihr Register bei jeder Iteration um 4 zu erhöhen. Dies wäre nicht möglich, wenn Ihr Array Objekte unterschiedlicher Größe enthält. Zuletzt nennen Sie diese neue Datenstruktur "Stapel", weil sie Sie an einen Stapel Teller in einem Restaurant erinnert, in dem immer ein Teller oben auf diesem Stapel entfernt oder hinzugefügt wird.

Die Umsetzung

Wie Sie sehen, ist ein Stapel nichts anderes als ein Array zusammenhängender Speicherorte, an denen Sie entschieden haben, wie Sie ihn bearbeiten möchten. Aus diesem Grund können Sie sehen, dass Sie nicht einmal die speziellen Anweisungen und Register verwenden müssen, um den Stapel zu steuern. Sie können es selbst mit den grundlegenden Anweisungen mov, add und sub implementieren und stattdessen Allzweckregister wie ESP und EBP wie folgt verwenden:

mov edx, 0FFFFFFFFh

;; -> Dies ist die Startadresse Ihres Stapels, die am weitesten von Ihrem Code und Ihren Daten entfernt ist. Sie dient auch als das Register, das das letzte Objekt im Stapel verfolgt, das ich zuvor erläutert habe. Sie nennen es den "Stapelzeiger", also wählen Sie das Register EDX als das, wofür ESP normalerweise verwendet wird.

sub edx, 4

mov [edx], dword ptr [someVar]

;; -> Diese beiden Anweisungen dekrementieren Ihren Stapelzeiger um 4 Speicherplätze und kopieren die 4 Bytes, die am Speicherort [someVar] beginnen, an den Speicherort, auf den EDX jetzt zeigt, genau wie ein PUSH-Befehl den ESP dekrementiert, nur hier haben Sie es getan es manuell und Sie haben EDX verwendet. Der PUSH-Befehl ist also im Grunde nur ein kürzerer Opcode, der dies tatsächlich mit ESP macht.

mov eax, dword ptr [edx]

füge edx hinzu, 4

;; -> und hier machen wir das Gegenteil, wir kopieren zuerst die 4 Bytes beginnend an der Speicherstelle, auf die EDX jetzt zeigt, in das Register EAX (hier willkürlich gewählt, wir hätten es kopieren können, wo immer wir wollten). Und dann erhöhen wir unseren Stapelzeiger EDX um 4 Speicherplätze. Dies ist, was der POP-Befehl tut.

Jetzt können Sie sehen, dass die Anweisungen PUSH und POP sowie die Register ESP und EBP gerade von Intel hinzugefügt wurden, um das obige Konzept der "Stack" -Datenstruktur einfacher zu schreiben und zu lesen. Es gibt immer noch einige RISC-CPUs (Reduced Instruction Set), die nicht über die PUSH- und POP-Anweisungen und dedizierten Register für die Stapelmanipulation verfügen, und während Sie Assembly-Programme für diese CPUs schreiben, müssen Sie den Stapel wie folgt selbst implementieren ich habe es Ihnen gezeigt.

Sie verwechseln einen abstrakten Stapel mit dem implementierten Hardware-Stapel. Letzteres ist bereits implementiert.

Ich denke, dass die Hauptantwort, nach der Sie suchen, bereits angedeutet wurde.

Wenn ein x86-Computer hochfährt, wird der Stapel nicht eingerichtet. Der Programmierer muss es beim Booten explizit einrichten. Wenn Sie sich jedoch bereits in einem Betriebssystem befinden, wurde dies behoben. Unten finden Sie ein Codebeispiel aus einem einfachen Bootstrap-Programm.

Zuerst werden die Daten- und Stapelsegmentregister gesetzt, und dann wird der Stapelzeiger darüber hinaus auf 0x4000 gesetzt.

    movw    $BOOT_SEGMENT, %ax
    movw    %ax, %ds
    movw    %ax, %ss
    movw    $0x4000, %ax
    movw    %ax, %sp

Nach diesem Code kann der Stapel verwendet werden. Jetzt bin ich sicher, dass dies auf verschiedene Arten geschehen kann, aber ich denke, dies sollte die Idee veranschaulichen.

Der Stapel ist nur eine Möglichkeit, wie Programme und Funktionen Speicher verwenden.

Der Stapel hat mich immer verwirrt, also habe ich eine Illustration gemacht:

( SVG-Version hier )

Der Stapel ist bereits vorhanden, sodass Sie dies beim Schreiben Ihres Codes annehmen können. Der Stapel enthält die Rücksprungadressen der Funktionen, die lokalen Variablen und die Variablen, die zwischen Funktionen übergeben werden. Es gibt auch integrierte Stapelregister wie BP, SP (Stack Pointer), die Sie verwenden können, daher die von Ihnen erwähnten integrierten Befehle. Wenn der Stapel nicht bereits implementiert war, konnten Funktionen nicht ausgeführt werden und der Codefluss konnte nicht funktionieren.

Der Stapel wird „umgesetzt“ mittels des Stapelzeigers, die Punkte in den Stapel (x86 Architektur hier angenommen wird ) Segment . Jedes Mal, wenn etwas auf den Stapel geschoben wird (mittels Pushl, Call oder einem ähnlichen Stapel-Opcode), wird es in die Adresse geschrieben, auf die der Stapelzeiger zeigt, und der Stapelzeiger wird dekrementiert (der Stapel wächst nach unten , dh kleinere Adressen). . Wenn Sie etwas vom Stapel entfernen (popl, ret), ist der Stapelzeiger inkrementiert und der Wert vom Stapel abgelesen.

In einer User-Space-Anwendung ist der Stack bereits beim Start Ihrer Anwendung für Sie eingerichtet. In einer Kernel-Space-Umgebung müssen Sie zuerst das Stapelsegment und den Stapelzeiger einrichten ...

Ich habe den Gas-Assembler nicht speziell gesehen, aber im Allgemeinen wird der Stapel "implementiert", indem ein Verweis auf die Stelle im Speicher beibehalten wird, an der sich die Oberseite des Stapels befindet. Der Speicherort wird in einem Register gespeichert, das unterschiedliche Namen für unterschiedliche Architekturen hat, aber als Stapelzeigerregister betrachtet werden kann.

Die Pop- und Push-Befehle werden in den meisten Architekturen für Sie implementiert, indem sie auf Mikroanweisungen aufbauen. Bei einigen "Bildungsarchitekturen" müssen Sie diese jedoch selbst implementieren. Funktionell würde Push folgendermaßen implementiert:

   load the address in the stack pointer register to a gen. purpose register x
   store data y at the location x
   increment stack pointer register by size of y

Einige Architekturen speichern auch die zuletzt verwendete Speicheradresse als Stapelzeiger. Einige speichern die nächste verfügbare Adresse.

Was ist Stack? Ein Stapel ist eine Art Datenstruktur - ein Mittel zum Speichern von Informationen in einem Computer. Wenn ein neues Objekt in einen Stapel eingegeben wird, wird es über alle zuvor eingegebenen Objekte gelegt. Mit anderen Worten, die Stapeldatenstruktur ähnelt einem Stapel von Karten, Papieren, Kreditkartenmailings oder anderen realen Objekten, die Sie sich vorstellen können. Wenn Sie ein Objekt von einem Stapel entfernen, wird zuerst das darüber liegende entfernt. Diese Methode wird als LIFO bezeichnet (last in, first out).

Der Begriff "Stapel" kann auch für einen Netzwerkprotokollstapel kurz sein. Im Netzwerk werden Verbindungen zwischen Computern über eine Reihe kleinerer Verbindungen hergestellt. Diese Verbindungen oder Schichten wirken wie die Stapeldatenstruktur, indem sie auf dieselbe Weise aufgebaut und entsorgt werden.

Sie haben Recht, dass ein Stapel eine Datenstruktur ist. Häufig sind Datenstrukturen (einschließlich Stapel), mit denen Sie arbeiten, abstrakt und existieren als Darstellung im Speicher.

Der Stapel, mit dem Sie in diesem Fall arbeiten, hat eine materiellere Existenz - er wird direkt realen physischen Registern im Prozessor zugeordnet. Als Datenstruktur sind Stapel FILO-Strukturen (First In, Last Out), die sicherstellen, dass Daten in der umgekehrten Reihenfolge entfernt werden, in der sie eingegeben wurden. Sehen Sie sich das StackOverflow-Logo für eine visuelle Darstellung an! ;)

Sie arbeiten mit dem Anweisungsstapel . Dies ist der Stapel der tatsächlichen Anweisungen, die Sie dem Prozessor zuführen.

Der Aufrufstapel wird vom x86-Befehlssatz und vom Betriebssystem implementiert.

Anweisungen wie Push und Pop passen den Stapelzeiger an, während das Betriebssystem die Speicherzuweisung übernimmt, wenn der Stapel für jeden Thread wächst.

Die Tatsache, dass der x86-Stapel von höheren zu niedrigeren Adressen "wächst", macht diese Architektur anfälliger für den Pufferüberlaufangriff.

Sie haben Recht, dass ein Stapel "nur" eine Datenstruktur ist. Hier bezieht es sich jedoch auf einen Hardware-implementierten Stack, der für einen bestimmten Zweck verwendet wird - "The Stack".

Viele Leute haben Kommentare zum Hardware-implementierten Stack im Vergleich zur (Software-) Stack-Datenstruktur abgegeben. Ich möchte hinzufügen, dass es drei Hauptstapelstrukturtypen gibt -

1. Ein Call-Stack - Nach welchem ​​fragen Sie? Es speichert Funktionsparameter und Rücksprungadresse usw. Lesen Sie die Funktionen in Kapitel 4 (Alles über die 4. Seite, dh Seite 53) in diesem Buch. Es gibt eine gute Erklärung.
2. Ein generischer Stapel, den Sie in Ihrem Programm verwenden können, um etwas Besonderes zu tun ...
3. Ein generischer Hardware-Stack
   Ich bin mir nicht sicher, aber ich erinnere mich, dass ich irgendwo gelesen habe, dass in einigen Architekturen ein Allzweck-Hardware-implementierter Stack verfügbar ist. Wenn jemand weiß, ob dies korrekt ist, kommentieren Sie bitte.

Das erste, was Sie wissen müssen, ist die Architektur, für die Sie programmieren, was im Buch erklärt wird (ich habe es gerade nachgeschlagen - Link). Um die Dinge wirklich zu verstehen, schlage ich vor, dass Sie etwas über den Speicher, die Adressierung, die Register und die Architektur von x86 lernen (ich gehe davon aus, dass Sie genau das lernen - aus dem Buch).

Das Aufrufen von Funktionen, bei denen der lokale Status auf LIFO-Weise gespeichert und wiederhergestellt werden muss (im Gegensatz zu einem verallgemeinerten Co-Routine-Ansatz), stellt sich als solch ein unglaublich häufiges Bedürfnis heraus, dass Assemblersprachen und CPU-Architekturen diese Funktionalität grundsätzlich einbauen könnte wahrscheinlich für Begriffe wie Threading, Speicherschutz, Sicherheitsstufen usw. gesagt werden. Theoretisch könnten Sie Ihren eigenen Stapel implementieren, Konventionen aufrufen usw., aber ich gehe davon aus, dass einige Opcodes und die meisten vorhandenen Laufzeiten auf diesem nativen Konzept des "Stapels" beruhen. .

stackist Teil der Erinnerung. es verwenden für inputund outputvon functions. wird auch verwendet, um sich an die Rückgabe der Funktion zu erinnern.

esp Register ist die Stapeladresse zu merken.

stackund espwerden von Hardware implementiert. Sie können es auch selbst implementieren. es wird Ihr Programm sehr langsam machen.

Beispiel:

nop // esp= 0012ffc4

espDrücken Sie 0 // = 0012ffc0, Dword [0012ffc0] = 00000000

call proc01 // esp= 0012ffbc, Dword [0012ffbc] = eip, eip= adrr [proc01]

pop eax// eax= Dword [ esp], esp= esp+ 4

Ich habe nach der Funktionsweise von Stack gesucht und diesen Blog gefunden großartig und erklärt das Konzept des Stacks von Grund auf neu und wie der Stack-Wert im Stack gespeichert wird.

Nun zu Ihrer Antwort. Ich werde es mit Python erklären, aber Sie werden eine gute Vorstellung davon bekommen, wie Stack in jeder Sprache funktioniert.

Es ist ein Programm:

def hello(x):
    if x==1:
        return "op"
    else:
        u=1
        e=12
        s=hello(x-1)
        e+=1
        print(s)
        print(x)
        u+=1
    return e

hello(3)

Quelle: Cryptroix

einige seiner Themen, die es im Blog behandelt:

How Function work ?
Calling a Function
 Functions In a Stack
 What is Return Address
 Stack
Stack Frame
Call Stack
Frame Pointer (FP) or Base Pointer (BP)
Stack Pointer (SP)
Allocation stack and deallocation of stack
StackoverFlow
What is Heap?

Aber es wird mit Python-Sprache erklärt. Wenn Sie möchten, können Sie einen Blick darauf werfen.