blog · git · desktop · images · contact
2011-04-02
Ein Stack im Allgemeinen ist eine sehr einfache Datenstruktur, die ihrem Namen alle Ehre macht: Sie ist ein Stapel. Man legt Dinge oben drauf und das, was man zuerst herunternehmen kann, ist immer das, was man zuletzt oben draufgelegt hat. Genau wie ein Stapel Bücher.
+----+ +-----+ +-----+ +-----+ +-----+ +-----+
| | | | | | | 3 | | | | |
| | | | +-----+ +-----+ +-----+ | |
| | | | | 2 | | 2 | | 2 | | |
| | +-----+ +-----+ +-----+ +-----+ +-----+
| | | 1 | | 1 | | 1 | | 1 | | 1 |
+----+ +-----+ +-----+ +-----+ +-----+ +-----+
Start push(1) push(2) push(3) pop()=3 pop()=2
--------------------------- Zeit --------------------------->
Ein eigener Stack steht zunächst einmal jedem Prozess zur Verfügung.
Man kann darauf mit den Instruktionen push und pop zugreifen.
Folgendes Programm legt erst eine 42 auf den Stack, dann eine 1. Danach
holt es das oberste Element vom Stack und schreibt es ins Register EAX.
Dann das nächste Element ins Register EBX. Der Interrupt 0x80 wechselt
in den Kernel Mode, woraufhin Linux den Syscall mit der Nummer 1 und dem
Argument 42 aufruft: _exit(42).
.text
.global _start
_start:
pushl $42
pushl $1
popl %eax
popl %ebx
int $0x80
Übersetzung und Aufruf:
$ gcc -nostdlib -o foo foo.s
$ ./foo ; echo $?
42
Dieses einfache Beispiel wäre natürlich auch ohne den Stack möglich gewesen. Der Stack, den ein Programm zur Verfügung hat, hält sich jedoch nicht so ganz an die formale Definition – er ist nämlich frei adressierbar. Das heißt, ich kann nicht nur auf das oberste Element zugreifen, sondern auch auf alle anderen. Und zwar ohne vorher alle darüberliegenden Elemente explizit abrufen zu müssen. Das macht den Stack zu einem allgemein verwendbaren Speicherbereich, der seinem Namen dann doch nicht mehr so ganz gerecht wird. ;)
Der Knackpunkt ist das Register ESP (SP = Stack Pointer). Dieses enthält
die Speicheradresse, die auf das letzte Element auf dem Stack zeigt.
Durch Dereferenzierung dieser Adresse gelange ich also auch an den
Inhalt des Stacks – und nicht nur durch push und pop.
.text
.global _start
_start:
/* "Schaffe Platz" auf dem Stack. */
subl $8, %esp
/* Schiebe die beiden Werte in den Speicher, auf den ESP zeigt, und
* hole sie danach wieder zurück. */
movl $1, (%esp)
movl $42, 4(%esp)
movl (%esp), %eax
movl 4(%esp), %ebx
/* Platz wieder "freigeben". */
addl $8, %esp
int $0x80
„Platz schaffen“ heißt einfach nur, ESP zu ändern (Linux greift hiernach
eventuell ein und vergrößert den physikalischen Speicher, der dem
Prozess zugeordnet ist, bis hin zu einer maximalen Größe). Im ersten
Beispiel wurde das implizit von push erledigt. Da der Stack von „oben“
nach „unten“ wächst, muss ich den Wert in ESP also verringern und zwar
um 8, damit ich zwei Adressen bzw. Integer mit je 4 Byte Länge speichern
kann (ja, ich habe hier noch antike 32 Bit-Hardware). Danach kann ich
über (%esp) auf das „letzte“ Element zugreifen und über 4(%esp) auf
das davor. Zuletzt verschiebe ich die Stack-Grenze wieder ein Stück nach
oben.
: : : : : :
: : : : : :
+----+ +----+ +----+
| ?? | <-- ESP alt | ?? | | ?? |
+----+ +----+ +----+
| | | 42 |
+----+ +----+
| | <-- ESP neu | 1 | <-- ESP neu
+----+ +----+
(1) (2) (3)
subl $8, %esp movl ..., movl ...
Anfang, Inhalt bei 8 weitere Byte Neue Werte
ESP vorerst unbekannt reserviert geschrieben
Wenn ich ein Compiler bin, dann reicht das auch im Prinzip, um meinen
Stack zu verwalten. Bin ich aber ein Mensch und schreibe den Code
manuell, wird’s schnell haarig. Ich muss bei der Adressierung nämlich
immer beachten, wo ESP gerade steht. Ein Wert, den ich soeben unter
4(%esp) in den Stack geschrieben habe, kann ein paar Zeilen später
unter 32(%esp) verfügbar sein, wenn sich zwischendrin ESP verändert
hat. Das ist natürlich kein unüberwindliches Hindernis, aber schöner
wäre es, wenn ich mir irgendwo diejenige Speicheradresse merken könnte,
die den „Anfang“ des Stacks kennzeichnet.
Das ist die Idee des „Frame Pointers“ oder „Base Pointers“. Dafür wird normalerweise das Register EBP (BP = Base Pointer) verwendet. Ich muss mich allerdings selbst darum kümmern. Die gängige Vorgehensweise ist, beim Betritt einer „Funktion“ den alten Wert von EBP auf dem Stack zu speichern und dann den aktuellen Wert von ESP nach EBP zu kopieren. Danach kann ich ESP „beliebig“ verändern und habe dennoch mit EBP immer einen festen Referenzpunkt. Verlasse ich die Funktion wieder, muss ich natürlich aufräumen. Dies erreicht man, indem man EBP zurück nach ESP kopiert und dann den ehemals gespeicherten EBP-Wert vom Stack zurück nach EBP holt.
Grundsätzlich wäre das also:
/* Frame Pointer aufsetzen. */
pushl %ebp
movl %esp, %ebp
/* ... do foo ... */
/* Frame Pointer wieder aufräumen. */
movl %ebp, %esp
popl %ebp
Wo auch immer ESP dann gerade hinzeigt, ist nicht mehr wichtig, denn über Werte relativ zu EBP kann ich Speicher des Stacks immer adressieren:
: :
: :
+---------+
| EBP alt | <-- EBP
+---------+
| Var 0 | <-- -4(%ebp)
| Var 1 | <-- -8(%ebp)
| Var 2 | <-- -12(%ebp)
| Var 3 | <-- -16(%ebp)
: :
: :
| letzte | <-- ESP
+---------+
Zum Aufräumen gibt es auch noch eine kürzere Variante, nämlich die
Instruktion leave, die genau dasselbe tut.
Richtig interessant wird der Frame Pointer, wenn man Funktionen aufrufen möchte. Funktionen bekommen Eingabeparameter / Argumente und liefern ein Ergebnis. Die Organisation diese Über- und Rückgabe ist prinzipiell vollkommen frei. Ich könnte mir also irgendetwas ausdenken – zum Beispiel könnte ich immer alles über Register machen. Dann bin ich allerdings ziemlich eingeschränkt, was die Datenmengen betrifft. Spätestens, wenn ich Bibliotheken nutzen will, muss ich mich daher an Konventionen halten. Bezüglich GNU/Linux und C handelt es sich dabei meistens um cdecl.
Ein Beispiel:
.text
.global _start
_start:
/* Frame Pointer aufsetzen. */
pushl %ebp
movl %esp, %ebp
/* Platz auf dem Stack reservieren und eine 21 dort ablegen. Danach
* wird die Subroutine "doppeln" aufgerufen. Die 21 ist ihr erstes
* und einziges Argument. Durch "call" wird zusätzlich noch die
* Rücksprungadresse auf dem Stack abgelegt. */
subl $4, %esp
movl $21, -4(%ebp)
call doppeln
/* "doppeln" gibt das Ergebnis gemäß cdecl Calling Convention in EAX
* zurück. Das Ergebnis soll der Exit Code des Prozesses sein, also
* schiebe den Wert nach EBX und dann die Syscall-Nummer 1 nach EAX.
* Hier wird also wieder _exit(42) aufgerufen. */
movl %eax, %ebx
movl $1, %eax
int $0x80
doppeln:
/* Frame Pointer (für diese Subroutine) aufsetzen. */
pushl %ebp
movl %esp, %ebp
/* Hole erstes Argument nach EAX und addiere es dann noch einmal. */
movl 8(%ebp), %eax
addl 8(%ebp), %eax
/* Lokalen Frame Pointer aufräumen und zurückspringen. "ret" nimmt
für den Sprung die Rücksprungadresse, die auf dem Stack liegt. */
leave
ret
Unmittelbar vor dem call sieht mein Stack also so aus:
: :
: :
+-----------+
| EBP alt 1 | <-- EBP
| 21 | <-- ESP
+-----------+
Und nach dem Aufsetzen des Frame Pointers in der Subroutine dann so:
: :
: :
+-----------+
+---> | EBP alt 1 |
| | 21 | <-- 8(%ebp)
| +-----------+
| | Rückspr. |
+---- | EBP alt 2 | <-- EBP, ESP
+-----------+
Da dieses einfache Beispiel den Sachverhalt vermutlich noch nicht in
Gänze erklärt, hier ein allgemeineres Bild. Es werden nach _start zwei
Funktionen aufgerufen.
: :
: :
+--------------+
Der Anfang, innerhalb | EBP alt 1 | <--+ \
von _start. | Lokale Var 1 | | |
| Lokale Var 2 | | |
| Lokale Var 3 | | | Frame von _start
: : | |
| Argument 2 | | |
| Argument 1 | | /
+--------------+ |
Aufruf einer Funktion, | Rückspr. | | \
sie kann auf die beiden +--> | EBP alt 2 | ---+ |
Argumente des Frames | | Lokale Var 1 | |
darüber zugreifen. | | Lokale Var 2 | | Frame von fkt_1
| | Lokale Var 3 | |
| | Lokale Var 4 | |
| : : |
| | Argument 1 | /
| +--------------+
Aktuelle Position, von | | Rückspr. | \
hier aus kommt man also +--- | EBP alt 3 | <-- EBP | Frame von fkt_2
über 8(%ebp) auf das | Lokale Var 1 | |
eine Argument des | Lokale Var 2 | <-- ESP /
vorherigen Frames. +--------------+
_start selbst sieht man ein paar lokale Variablen, danach
können noch weitere kommen. Unmittelbar vor dem Aufruf von fkt_1
werden dann zwei Argumente für diese Funktion auf dem Stack
abgelegt. Durch call fkt_1 landet zusätzlich die Rücksprungadresse
auf dem Stack.fkt_1 wird ein neuer Frame Pointer aufgebaut, der
alte wird auf dem Stack gesichert. Über den neuen Pointer lassen
sich bequem die Argumente für die eigene Funktion adressieren und
auch die eigenen lokalen Variablen.fkt_2.Nun sollte sich auch der Name „Frame Pointer“ klären: Jeder Funktionsaufruf hat einen eigenen „Frame“ auf dem Stack, der bei EBP beginnt und bei ESP endet. Diese Unterteilung ist natürlich relativ willkürlich und durch nichts fest vorgegeben.
Noch einmal allgemein die Adressierungsmöglichkeiten über den Frame Pointer inklusive Argumenten und Rücksprungadresse:
: : :
: : :
| Arg 2 | <-- 16(%ebp) | vorheriger
| Arg 1 | <-- 12(%ebp) | Frame
| Arg 0 | <-- 8(%ebp) /
+---------+
| Rücksp. | \
| EBP alt | <-- EBP |
| Var 0 | <-- -4(%ebp) |
| Var 1 | <-- -8(%ebp) | aktueller
| Var 2 | <-- -12(%ebp) | Frame
| Var 3 | <-- -16(%ebp) |
: : |
: : |
| letzte | <-- ESP /
+---------+
Es ist übrigens auch genau jener Frame Pointer, von dem bei der häufig
erwähnten Compileroption „-fomit-frame-pointer“ die Rede ist.
Folgender C-Code:
int main(int argc, char *argv[])
{
int a = 1;
int b = 42;
return a + b;
}
Wird dieser Code „normal“ übersetzt, dann entsteht folgender
Assembler-Code (gekürzt und kommentiert – zum Unterschied zwischen
main und _start siehe das vorherige Posting):
.text
.globl main
main:
pushl %ebp /* Frame Pointer */
movl %esp, %ebp
subl $16, %esp /* Stack vergrößern */
movl $1, -4(%ebp) /* Werte relativ zu EBP schreiben */
movl $42, -8(%ebp)
movl -8(%ebp), %eax /* Werte vom Stack in Register */
movl -4(%ebp), %edx
leal (%edx,%eax), %eax /* "Addition", Ziel in EAX */
leave /* Frame Pointer aufräumen */
ret
Man sieht hier auch sehr schön, wie die beiden Variablen a und b auf
dem Stack angelegt und dann mit ihren Werten befüllt werden. Danach
werden sie zur Verarbeitung wieder von dort gelesen. Adressiert wird der
Speicher über EBP.
Kompiliert man stattdessen mit „-fomit-frame-pointer“, dann entsteht
folgendes Ergebnis:
.text
.globl main
main:
subl $16, %esp /* Stack vergrößern */
movl $1, 12(%esp) /* Werte relativ zu ESP schreiben */
movl $42, 8(%esp)
movl 8(%esp), %eax /* Werte relativ zu ESP lesen */
movl 12(%esp), %edx
leal (%edx,%eax), %eax /* Addition der Werte */
addl $16, %esp /* ESP zurücksetzen */
ret
Die Frage, die sich stellt, wäre: Warum macht der C-Compiler das nicht immer so? Wozu benötigt er einen Frame Pointer – sollte er nicht intelligent genug sein, das auch ohne zu schaffen? Immerhin würde man sich dann ein paar Instruktionen sparen und hätte auch ein Register mehr zur Verfügung, da EBP nicht mehr vom Frame Pointer „blockiert“ wäre.
Der Grund ist (leichteres) Debugging. Wie man an einem der obigen Bilder
schön sehen kann, kann man bei Nutzung eines Frame Pointers sehr leicht
nachvollziehen, aus welcher Funktion man gekommen ist (über die
Rücksprungadresse). Man folgt einer verlinkten Liste bis man im Frame
von _start angekommen ist. Ohne Frame Pointer wird das komplizierter,
aber auch nicht notwendigerweise unmöglich.