Der Stack ========= Eine etwas detailiertere Beschreibung by Dobin Rutishauser (aka Anthraxx) 9.1.2002 Version 0.6 Vorwort ------- Für meinen Text "Elf and the Beyond" hab ich ein Kapitel über den Stack geschrieben. Da die Funktionsweise des Stack's für viele bekannt und zur verständniss des ELF Dokumentes nicht notwendig war, hab ich ihn in ein eigenes File ausgelagert. Hiermit reiht sich also ein Text über Stack den vielen anderen vorherigen an, wobei dieser hier aber 1) ein bisschen detailierter 2) und deutsch ist :) Einführung ---------- Der Stack ist ein Speicherbereich, auf dem Elemente draufgelegt oder weggenommen werden können. Man kann sich ihn als Stapel von Tellern (oder Pizzas, whatever :) vorstellen, bei dem immer nur Teller von oben weggenommen oder draufgelegt werden können. Dieses Prinzip nennt man LIFO (Last in, First out). Auf x86 Computer wächst der Stack nach unten, also von höheren Memory Adressen zu kleinen. Hier nun eine symbolische darstellung des Stacks: ______________________ | 0x00 | 0xff | 0x01 | | 0x02 | | 0x03 | | | . ^ ¦ . . ¦ ¦ . 0x00 ¦ ¦ ¦ v push pop Der Assembler befehl, um etwas auf den Stack zu legen heisst "push", das Gegenteil "pop". Wie wir hier sehen können wir beliebig viele Elemente an den Stack anhängen, dieser wächst immer weiter nach unten (hier von 0xff bis hin zu 0x00). Der Stack des x86 ------------------ Die x86 Prozessorreie hat spezielle Befehle und Register, um einen die Bedienung des Stacks zu vereinfachen. Befehle: push um etwas auf den Stack zu legen pop um etwas vom Stack zu nehmen Register: esp zeigt auf die Adresse des letzten Elements auf dem Stack ebp zeigt auf das Aktuelle Stack frame Die Register bedarf es weitere Erklärungen. ESP zeigt immer auf das letzte gepushte Element auf dem Stack. Wenn also etwas auf den Stack gepusht wird, wird erst ESP um die grösse dieses Elementes verringert (merke: der Stack wächst nach unten), und dann wird das Element geschrieben. EBP wird im nächsten Abschnitt weiter Erklärt. Im Prinzip ist es ein Zeiger auf eine Adresse im Stack, von der aus leicht auf die Lokalen Variablen einer Funktion oder dessen Argumente zugegriffen werden kann. C und der Stack - Adressierung ------------------------------ Die Programmiersprache C macht extensiven gebrauch des Stacks, auch wenn der Programmierer nichts davon merkt. Jede nicht statische Lokale Variable in einem C Programm existiert nur im Stack. Nehmen wir das folgende Programm: void harakiri(int a, int x, char *buf) { int foobar=5; foobar += a; } void main (void) { int a; char buffer[10]; harakiri(a, 23, buffer); } In diesem Programm sind die Variablen a, buffer und foobar auf dem Stack. Ausserdem werden vor dem aufruf der Funktion harakiri alle 3 Argumente auf den Stack gepusht (die 2 integer und die Addresse von buffer). Die Lokalen variablen werden jedesmal beim eintreten in die Funktion neu erstellt, und danach wieder "gelöscht". Compilieren wir diesen Programm einmal und schauen uns die wichtigsten Sachen an: $ gcc -S test.c $ cat test.s harakiri: subl $24,%esp movl $5,-4(%ebp) movl 8(%ebp),%eax addl %eax,-4(%ebp) Hier sehen wir, wie zuerst 24 vom Stack Pointer (%esp) subtrahiert wird, um Platz für die Lokalen Variablen zu schaffen. Auch sehen wir hier, wie alle Variablen relativ zu EBP Addressiert werden. EBP-4 ist die Adresse der Variable foobar, EBP+8 das Argument "int a". In der zweiten Zeile wird also foobar mit 5 initialisiert. Danach wird Variable a nach EAX kopiert (EAX ist also 23), und dann wird noch foobar hinzuaddiert (EAX + 5); Schön ersichtlich ist, wie lokale Variablen unterhalb von EBP Addresiert werden, und Argumente einen positiven Wert zu EBP haben. Wie man auch sieht, würde bei jedem Aufruf dieser Funktion die lokalen Variablen neu erstellt. Grafisch sieht der Stack in einem C Programm immer etwa so aus: Position Inhalt Frame -------------------------------------------------------- 0xff ¦ EBP + 16 ¦ argument 2 ¦ Vorheriges ¦ ¦ EBP + 8 ¦ argument 1 ¦ ¦ ¦ ¦------------------------------------------------------¦ ¦ ¦ EBP + 4 ¦ Rücksprung Adresse ¦ ¦ ¦ ¦ EBP ¦ vorheriger EBP ¦ ¦ ¦ ¦ EBP - 4 ¦ lokale Variablen ¦ Derzeitiges ¦ v ¦ ¦ .... ¦ ¦ ¦ ESP ¦ letzte Variable ¦ ¦ -------------------------------------------------------- 0x00 Funktionen in C und der Stack ----------------------------- In diesem Kapitel werden wir erfahren, wie C Funktionen (bzw Unterprogramme) aufruft und dann wieder zurückkehrt. Ein Programm ist nichts als eine aneinandereihung von Befehlen, die von der CPU abgearbeitet wird. Damit der Prozessor weiss, welchen Befehl er als nächstes Auführen muss gibt es das IP Register (Instruction Pointer), der genau dafür da ist, dh IP zeigt immer auf den nächsten auszuführenden Befehl. Um nun vom normalen Befehlsweg abzugehen und woanders weiterzumachen, gibt es zb den "jmp" Befehl. Dieser verändert den IP, sodass er zu einer anderen Befehlskette Zeigt (zb. konnte er ein paar Befehle überspringen, oder an einer total anderen Stelle weitermachen). Um eine Funktion aufzurufen ist das aber nicht genug, denn wir müssen ja wieder zum alten Befehlsstrang zurückehren wenn die Funktion fertig ist. Ausserdem müssen wir ihr noch Argumente übergeben können, damit wir ihre Funktionsweise beeinflussen können. Auch hat jede Funktion Lokale Variablen, die nur für sie gelten, diese müssten auch noch erstellt werden... Wenn wir also mal Zusammenfassen, was wir machen müssten um eine Funktion aufzurufen: 1) Argumente der Funktion irgendwo plazieren 2) Die Funktion aufrufen 3) Platz schaffen für lokale Variablen 4) die Befehle der Funktion abarbeiten 5) Platz der Variablen wieder freigeben 6) Zum Alten Befehlsstrang zurückkehren Nun schauen wir mal, wie das in Assembler aussieht. Zuerst legen wir die Argumente auf den Stack. Das sieht dann etwa so aus: push push push Da der Stack ein LIFO ist, müssen wir die Argumente in umgekehrter Rheienfolge pushen. jetzt rufen wir die Funktion auf: push jmp Zuerst wird die Adresse auf den Stack gespeichert, wohin die CPU nach dem beendigen der Funktion springen muss. Damit es keine Endlosschleife giebt, möchten wir zum Befehl nach dem Jump springen, darum zählen wir dessen länge noch zu IP dazu. Nun sind wir in der Funktion drin. Als ersten müssen wir ein paar vorbereitungen machen, damit wir sie auch gebrauchen können. Wie schon erwähnt werden in einer Funktion alle lokalen Variablen und die Argumente durch EBP Addressiert. Da wir nun in einer neuen Funktion sind, müssen wir also auch EBP neu setzen. Aber zuerst muss EBP zwischengespeichert werden. Und wo geht das besser als auf dem Stack? push EBP mov ESP, EBP Nach dem Speichern von EBP kopieren wir den Wert von ESP nach EBP. Wieso? Nun, schauen wir mal wie der Stack bis jetzt aussieht (ohne das anpassen von EBP): _______________________________ 0xff | | (funktion main) | | | | | | | | (unterfunktion) | | | | . . 0x00 Eine andere, eher bessere Darstellung des Stacks. Hier wächst er nach links. <---[ ][ ][ebp von main][return address][argumente][lokale variablen] | | ESP EBP ESP zeigt ja auf die nächst freie Stelle im Stack. EBP Zeigt immer noch auf das Stack Frame von der vorherigen Funktion (hier main). Wenn wir nun ESP nach EBP kopieren, haben wir einen neuen Stack Frame dieser Funktion! Nun muss noch Platz geschaffen werden für die Lokalen Variablen. Dies geschieht, indem wir einfach den Stack vergrössern, dh wir verkleinern ESP um die grösse der Variablen + ein bisschen Backup. sub ESP, Der Stack sieht nun abschliessend so aus: _______________________________ 0xff | | | | | | | | | | | | | <........> | | <........> | | | | | . . 0x00 Oder: <---[ ][lokal][ebp von main][return address][argumente][lokale variablen] | EBP / ESP EBP wird nie verändert, ausser es wird eine andere Funktion aufgerufen oder in eine zurückgekehrt. Nun haben wir alles nötige vorbereitet und die Funktion kann ihre Arbeit tun. Wenn sie fertig ist, folgt das Aufräumen (epilog): leave ret Der alte Frame Pointer wird wiederhergestellt, indem er nach EBP gepoppt wird. (durch den Befehl leave). Jetzt zeigt ESP übrigens auf die return adresse, die auch grad nach IP gepoppt wird (das übernimmt die CPU durch den Befehl "ret", da das direkte ändern vom IP nicht erlaubt ist). Nun sind wir wieder in der vorhergehenden Funktion, direkt nach dem call Befehl. Wir haben jetzt immer noch die gepushten Argumente auf dem Stack, die werden wir folgendermassen los: add ESP, Wir verschieben ESP einfach vor die Argumente (wir könnten sie auch wieder zurück poppen, was aber sehr umständlich und langsam wäre). Nun schauen wir mal das ganze in Aktion an: Wir nehmen folgendes kleines Programm: <--snip--> void test (int i) { char buf[12]; } int main() { test(12); } <--snap--> Welches als Assembler Source in sowas kompiliert: <--snip--> test: pushl %ebp # alter frame pointer auf dem stack speichern movl %esp,%ebp # neuer Frame pointer erstellen subl $24,%esp # platz für lokale variablen machen leave # und zurückspringen ret main: pushl %ebp # das gleiche movl %esp,%ebp # wie subl $8,%esp # oben addl $-12,%esp # pushl $12 # argument für die funktion pushen (12) call test # funktion aufrufen addl $16,%esp # stack aufräumen leave # und tschüss... ret <--snap--> References ---------- "Smashing The Stack For Fun And Profit", by Aleph One, Phrack 94, File 14 "System V Application Binary Interface, i386, 4 Edition" http://www.caldera.com/developers/devspecs/