Arbeitsweise eines Stacks
-
Hallo Zusammen!
Ich habe die Arbeitsweise des Stacks leider nicht verstehen können,
wirds jedenfalls in einem Buch beschrieben. Für meinen Geschmack etwas unverständlich. kann mir bitte jemand ganz vereinfacht die Arbeitsweise des Stacks mit eigenen Worten erklären?Zitat:
laut Buch
Die Analogie zum Geschirrstapel eignet sich zwar zur anschaulichen Darstellung, versagt aber bei der grundlegenden Arbeitsweise des Stacks. Eine genauere Vorstellung liefert eine Folge von Fächern, die von oben nach unten angeordnet sind. Auf der Spitze des Stacks befindet sich das Fach, auf das der Stack-Pointer zeigt. Alle Fächer haben eine forlaufende Adresse und eine dieser Adressen wird im Stack-Register abgelegt. Alles unterhalb dieser magischen Adresse, die man als Spitze des Stacks bezeichnet, wird als auf dem Stack befindlich betrachtet.
Alles oberhalb des Stack-Pointers liegt außerhalb des Stacks und ist ungültig.
-
Moin, Moin...
Der Stack ist erstmal ein bestimmter Bereich im Speicher. Dieser Speicherbereich wird vom Prozessor verwendet, um z.B. Rücksprungadressen aus Funktionen abzulegen. Dazu gibt es einen Zeiger, eine Adresse, der auf die Spitze des Stacks zeigt. Der Stack wächst von oben(hohe Adressen) nach unten(niedrige Adressen).
Beispiel (16 Bit):
Adresse Inhalt Stackpointer(sp) 01004h 00001h 01002h 08976h 01000h 0abcdh <== 01000h 00ffeh undefiniert 00ffch undefiniert 00ffah undefiniert Befehl push 01234h Der Wert 01234h wird auf den Stack gelegt. Dazu wird der Stackpointer um 2 verringert und der Wert in den Speicher Geschrieben, ab der Adresse auf die sp jetzt zeigt. Alle Werte, die unterhalb des sp stehen, gelten als undefiniert. Adresse Inhalt Stackpointer(sp) 01004h 00001h 01002h 08976h 01000h 0abcdh 00ffeh 01234h <== 00ffeh 00ffch undefiniert 00ffah undefiniert Befehl push 08989h Adresse Inhalt Stackpointer(sp) 01004h 00001h 01002h 08976h 01000h 0abcdh 00ffeh 01234h 00ffch 08989h <== 00ffch 00ffah undefiniert Befehl pop ax Der Wert auf den der Stackpointer zeigt, wird in das Register ax kopiert und dann sp um 2 erhöht. Alle Werte, die unterhalb des neuen sp stehen, gelten als undefiniert. Adresse Inhalt Stackpointer(sp) 01004h 00001h 01002h 08976h 01000h 0abcdh 00ffeh 01234h <== 00ffeh 00ffch undefiniert 00ffah undefiniertCiao...
-
Das mit dem Geschirrstapel passt schon, nur dass sich das Geschirr normalerweise von unten nach oben stapelt, der Stack (auf x86 und den meisten CPUs zumindest) aber von oben nach unten.
Du machst:
push 1
push 2
push 3Du bekommst:
pop -> 3
pop -> 2
pop -> 1Oder
push 1
push 2
pop -> 2
push 3
push 4
pop -> 4
pop -> 3
pop -> 1
-
auf IA32 arbeitet der Stack (Stackpointer %esp) wie bereits gesagt von oben nach unten, wenn du nun Speicher auf dem Stack reservieren willst, ziehst du einfach die Anzahl der bytes vom Stackpointer ab
int main() { int a; }sehe dann so aus (bei 4byte pro int)
main: #Funktions Initialisierung erklär ich gleich subl $4, %esp #Funktions Deinitialisierung erklär ich auch gleichin C und C++ räumt man nach dem schließen eines Scopes ( { } ) den Stack wieder auf, also man wirft alles runter was darauf liegt, dass sieht dann beim GCC so aus
main: pushl %ebp movl %esp, %ebp #stack pointer wird in %ebp gespeichert subl $4, %esp #speicher für int a reservieren #... hier sind noch uninteressante Sachen, wie Rückgabewert etc. movl %ebp, %esp #so der stack zeigt auf das gleiche wie am Anfang popl %ebp ret
-
int main() { int a; a=0xBABE; }also der Zugriff auf den reservierten Stack Speicher sieht dann so aus
main: pushl %ebp movl %esp, %ebp #stack pointer wird in %ebp gespeichert subl $4, %esp #speicher für int a reservieren movl $0xBABE, -4(%ebp) #4 byte abziehen vom Anfang des Stacks #... hier sind noch uninteressante Sachen, wie Rückgabewert etc. movl %ebp, %esp #so der stack zeigt auf das gleiche wie am Anfang popl %ebp ret
-
Gehen wir mal davon aus das der Stack 100 dec Byte groß ist.
Speicheradresse AsBefehl Stackpointer Stackinhalt 10 call func 99 Adresse nach dem Call (13) auf den Stack Rückkehr aus func 100 Nichts 13 push al 99 Inhalt von AL auf den Stack 14 pop al 100 Al vom Stack ;/// func: 99 13(Adresse nach dem Call) 40 Assemblercode .... ret 100 Der Wert 13(Rücksprung Adresse) wird durch ret vom Stack geholt um zur Adresse nach dem Aufruf der Function zurückzukehren. Es ist Fatal, wenn man z.B in einer aufgerufen Function Register auf den Stack packt und dann vergisst sie wieder vom Stack zu holen. func: 99 13(Adresse nach dem Call) 40 Assemblercode .... push al 98 Ihalt von AL auf den Stack ret 99 Hier wird nun nicht die eigentliche Rücksprungadresse vom Stack geholt sonder der vorher auf den Stack gepackte Wert von al, was zu einem Absturz führt.
-
Podschun wählt im Assembler-Buch den "anschaulichen" Vergleich mit einer Stalagtite!
-
hi,
stacks sind eine häufig eingesetzte datenstruktur z.b. in parsern o.ä.
man solltet stacks nicht immer nur auf assembler-level betrachten
guckt ihr hier: http://www.cs.bu.edu/teaching/c/stack/