blog · git · desktop · images · contact & privacy · gopher


Stack, Frame Pointer, Parameterübergabe

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.              +--------------+

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.