Programmieren Teil 6 – Der Stack

Wie im letzten Artikel angekündigt, soll es heute ein wenig technischer zugehen. Konkret möchte ich ein paar Worte darüber verlieren, wie der Speicher im Rahmen von Variablendeklarationen und Funktionsaufrufen verwaltet wird. Programmiert wird da weniger, aber für das Verständnis eines Programmablaufes ist das enorm hilfreich.

Der zentrale Mechanismus zum Verwalten von Variablendeklarationen ist der Stack. Wie im Artikel über Variablen bereits geschrieben, ist der Stack ein bestimmter Bereich im Arbeitsspeicher. Er arbeitet streng linear: neue Daten werden immer an einem Ende angefügt und beim Entfernen von Daten müssen immer die zuletzt angefügten auch zuerst wieder entfernt werden.

Damit ist der Stack ideal geeignet, um mit ihm die Variablen im Rahmen von Funktionsaufrufen zu verwalten. Der Grund hierfür ist einfach: wird an einer Stelle im Programm eine Funktion aufgerufen, so springt der Programmfluss an diese Stelle; im Rahmen der Abarbeitung werden neue Variablen deklariert und verwendet; nach der Abarbeitung der Funktion springt der Programmfluss zurück an den Aufruf-Ort – die in der Funktion verwendeten Variablen werden nicht mehr benötigt und können “weggeräumt” werden. Die Verwendung des Stacks während der Programmabarbeitung folgt genau diesem Schema; wird eine neue Funktion aufgerufen, so werden alle darin deklarierten Variablen ans Ende des Stacks angefügt und nach dem Funktionsaufruf wieder von dort entfernt.

Nun stellen sich dabei 2 wichtige Fragen: wie genau lassen sich Werte von Variablen ans Ende des Stacks anfügen, und woher wissen Variablen, auf welche Stelle im Stack sie zeigen müssen? Die Antwort auf beide Fragen liegt in der Funktionsweise des Stacks im Arbeitsspeicher. 1 Der Stack ist ein bestimmter, reservierter Bereich im Arbeitsspeicher, und zwar von für gewöhnlich fester Größe (wobei jedes ausgeführte Programm seinen eigenen Stack-Bereich bekommt). Der Speicherbereich des Stacks an sich kann also weder wachsen noch schrumpfen. Das Hinzufügen von Werten funktioniert daher nach folgendem Prinzip:

1An dieser Stelle ein wichtiger Hinweis: der Stack im Arbeitsspeicher ist nicht mit dem Stack als Datenstruktur zu verwechseln; beiden liegt ein ähnliches Konzept zugrunde, aber sie funktionieren – technisch gesehen – etwas unterschiedlich.

Wir erinnern uns: der Speicher ist in einzelne Speicherzellen aufgeteilt, welche jeweils über eine Adresse ansprechbar sind. Das könnte etwa so aussehen (die Inhalte der Zellen spielen noch keine Rolle, sind daher erst einmal leer dargestellt); zu beachten ist, dass ich immer 4 Speicherzellen zu einer Zeile zusammengefasst habe und die Adressen daher auch in 4er-Schritten springen; den Grund dafür sehen wir noch:

Adresse Inhalt Inhalt Inhalt Inhalt
123450
123454
123458
123462
123466
123470
123474

Der Stack hat eine bestimmte Basisadresse – in der Fachliteratur bottom genannt, die das untere Ende des für den Stacks gültigen Speicherbereich markiert und über den gesamten Programmverlauf hin unveränderbar ist. Kurioserweise liegt der bottom in der Regel bei einer hohen Adresse und der Stack “wächst” zu den niedrigeren Adressen hin (der Grund ist vermutlich technisch-historischer Natur und soll hier nicht diskutiert werden).

Darüber hinaus existiert eine zweite Adresse, welche das obere Ende des aktuell genutzten Stacks markiert und sich während der Programmausführung verschieben kann. Diese zweite Adresse wird in einem Register gespeichert, welches esp (kurz für extended stack pointer) genannt wird. Wir erinnern uns: Register sind spezielle Speicherbereiche im Prozessor, die immer eindeutig angesprochen werden können (auch der Program Counter, der die Adresse der nächsten auszuführenden Anweisung speichert, ist ein solches Register). Das esp-Register enthält also die Adresse der Speicherzelle, bis zu welcher der Stack bisher schon gewachsen ist. Sollen neue Werte auf den Stack gelegt werden, so wird der Wert in die Zelle, auf welcher der esp aktuell zeigt, gespeichert und anschließend der Wert des esp-Registers verringert (da der Stack ja zu den niedrigeren Speicheradressen wächst), um somit eine Vergrößerung des Stacks anzuzeigen. Beim Entfernen von Werten vom Stack wird einfach der Wert des esp-Registers wieder erhöht und die damit weiter “oben” gespeicherten Werte verworfen.

Interessant wird das Konzept nun im Kontext von Funktionsaufrufen. Beim Aufruf einer Funktion wird für sie festgelegt, ab welche Speicheradresse sie ihre Daten ablegen kann; diese Speicheradresse wird ebenfalls in einem Register gespeichert, welches mit ebp (kurz für extended base pointer) bezeichnet wird. Wird nun einer aufgerufenen Funktion mitgeteilt, dass sie ihre Daten zum Beispiel ab der Adresse 123462 ablegen kann, ergibt sich das folgende Bild im Speicher (der Pfeil <-- deutet dabei an, dass der entsprechende Bezeichner auf die angegebene Speicherzeile verweist):

Adresse Inhalt Inhalt Inhalt Inhalt
123450
123454
123458
123462 <– ebp
<– esp
123466
123470
123490 <– bottom

Wird innerhalb einer Funktion nun eine Variable deklariert, wird ihre Adresse einfach relativ zur aktuellen Adresse von ebp definiert und der esp entsprechend angepasst; die letzte lokale Variable der Funktion liegt dabei immer in der Zeile (nicht Zelle!) vor der ebp-Adresse, die vorletzte lokale Variable in der Zeile davor und so weiter (natürlich nur bei Variablen, die nur eine einzelne Speicherzeile zum Ablegen ihrer Daten brauchen). Man sieht: die Variablen einer Funktion werden im Speicher in umgekehrter Reihenfolge angelegt. Zu beachten ist auch: der esp wird nicht erst verschoben, wenn die entsprechende Variable deklariert wird, sondern direkt beim Funktionsaufruf passend gesetzt; der Speicher für alle in einer Funktion benötigten Variablen wird also direkt beim Aufruf der Funktion reserviert.

Die Adresse der letzten Variable lautet also ebp - 4, die der vorletzten Variable entsprechend ebp - 8 und so weiter. Nehmen wir zum Beispiel folgenden Codeausschnitt:

void f() { int x; int y; ... }

Damit würde sich folgendes Bild im Speicher ergeben:

Adresse Inhalt Inhalt Inhalt Inhalt
123450 <– esp
123454 <– x [= ebp - 8]
123458 <– y [= ebp - 4]
123462 <– ebp
123466
123470
123490 <– bottom

Damit ist auch gleich die Frage geklärt, wie eine Variable immer auf die korrekte Speicheradresse verweisen kann; sie wird immer relativ zum ebp der umschließenden Funktion definiert und kann so auch während der Programmausführung dynamisch bestimmt werden.

Funktionsparameter werden in der gleichen Manier definiert, allerdings in der anderen Richtung vom ebp aus gesehen. Der Wert des ersten Parameters wird 2(!) Zeilen hinter dem ebp gespeichert, der zweite Parameter in der folgenden Zeile und so weiter; nehmen wir folgenden Codeausschnitt:

void f( int m, int n ) { int x; int y; ... }

Dann ergibt sich hier das folgende Speicherbild bei einem konkreten Funktionsaufruf:

Adresse Inhalt Inhalt Inhalt Inhalt
123450 <– esp
123454 <– x [= ebp - 8]
123458 <– y [= ebp - 4]
123462 <– ebp
123466
123470 <– m
123474 <– n
123490 <– bottom

Der Speicherbereich übrigens, der alle Parameter und Variablen eines Funktionsaufrufs umfasst (im Beispiel also von 123450 bis einschließlich 123474), wird Stack Frame genannt.

Jetzt stellen sich aber 2 neue Fragen: woher kommt der Wert für den ebp eigentlich und was wird in den beiden Speicherzellen um den ebp herum
gespeichert, die ich bisher ignoriert habe – immerhin wird auf letztere ja nicht durch eine Variable verwiesen.

Die Herkunft des ebp-Wertes ist recht einfach zu klären. Wenn wir uns innerhalb einer Funktion befinden, hat das esp-Register ja einen bestimmten Wert, nämlich das aktuelle Ende des gültigen Stack-Bereiches. Wird nun innerhalb der Funktion eine weitere aufgerufen, wird der Wert des esp-Registers genutzt, um den ebp-Wert der aufgerufenen Funktion zu bestimmen (nachdem die Argumente für den Funktionsaufruf durch die aufrufende Funktion auf den Stack gelegt wurden). Betrachten wir hierzu als Beispiel den folgenden Code:

void f( int n ) { int x; int y; ... } void g( int m ) { int a; ... f( a ); }

Vor dem Aufruf von f in g sieht der Speicher folgendermaßen aus:

Adresse Inhalt Inhalt Inhalt Inhalt
123434
123438
123442
123446
123450
123454 <– esp
123458 <– a
123462 <– ebp von g
123466
123470 <– m
123490 <– bottom

Unmittelbar nach dem Aufruf von f (noch in f!) ergibt sich dann das folgende Bild:

Adresse Inhalt Inhalt Inhalt Inhalt
123434 <– esp
123438 <– x
123442 <– y
123446 <– ebp von f
123450
123454 <– n
123458 <– a
123462 <– ebp von g
123466
123470 <– m
123490 <– bottom

In diesem Bild sehen wir 2 Stack Frames: einen im Bereich 123434 bis 123454 für die Funktion f und einen im Bereich 123458 bis 123470 für die Funktion g.

Gar nicht so schwierig, oder?

Bleiben noch die beiden nicht erklärten Speicherzeilen. In der Zeile, auf welche der aktuelle ebp verweist, ist der ebp-Wert der aufrufenden Funktion gespeichert. Dieser Wert wird vom Prozessor benötigt, um nach dem Ende einer Funktion den Wert des ebp-Registers im Kontext der aufrufenden Funktion wiederherzustellen. Die Speicherzeile hinter dem so abgelegten ebp-Wert enthält dagegen die Adresse der Anweisung, welche nach dem Ende der aktuellen Funktion ausgeführt werden soll – die sogenannte Rücksprungadresse. Nach dem Ende einer Funktion muss der Program Counter (also das Register, welches auf die nächste auszuführende Anweisung verweist) lediglich auf den in dieser Zeile gespeicherten Wert gesetzt werden, um mit dem Programmablauf an der Stelle vor dem Aufruf fortzufahren.

Und warum nun ausgerechnet 4 Zellen pro Zeile? Auch das ist einfach erklärt. Eine Zelle kann auf regulären Rechnern 8 Bit fassen – ein Byte. 4 Zellen entsprechen also 4 Bytes oder 32 Bit; 32 Bit ist aber die Grundlage vieler aktueller Betriebssysteme (weswegen wir auch in einigen Jahren da ein nettes kleines Problem bekommen können) und die meisten Werte während eines Programmablaufes passen genau in 4 Bytes oder Vielfache davon hinein – daher auch die entsprechende Darstellung. Auf 64-Bit-Systemen würden 8 Zellen (entsprechend 8 Bytes oder 64 Bit) für die Darstellung verwendet werden; für die Verwaltung des Stacks gibt es dort auch 2 eigene Register, nämlich rsp (entspricht dem esp unter 32 Bit) und rbp (entspricht dem ebp unter 32 Bit).

Kommentare

  1. #1 rolak
    April 25, 2013

    Der zentrale Mechanismus zum Verwalten von Variablendeklarationen ist der Stack

    Zum Verwalten des _Speicherbedarfs_ der _nicht-statischen/-globalen_ Variablen

    Stack .. von fester Größe

    Jein. Typischerweise ja, aber nicht aus Prinzip – immerhin sind die Mechanismen zur Erweiterung von Stack (nach ‘unten’) und Heap (nach ‘oben’) und andersrum spätestens seit dem 386er cpu-unterstützt. Daß sich typische 08/15-Compiler weigern, solche Möglichkeiten umzusetzen, sollte kein Argument sein – immerhin habe (nicht nur) ich derart flexible Programme geschrieben ;-)

    die Adresse der Speicherzelle, bis zu welcher der Stack bisher schon gewachsen ist

    (wg ebp/esp:) zumindest beim x86 zeigt esp auf das nächste freie Byte, also Dein Wert +1.

    Das mit dem alignment (ich hoffe nicht vorzugreifen) könnte etwas genauer formuliert werden: n=(1,2,4,8,..,wordsize)-Byte-Daten sollten zur Vermeidung einer Zeitstrafe an Adressen (adr mod n)=0 gelegt werden, daraus zwingenderweise folgend sollte die Größe des gesamten local block immer 0 mod wordsize sein. Mit den Fusseln (heutzutage 1- und 2-Byte-Werte) können dann die Lücken gefüllt werden, state of the art: Immer wieder (wie auch der Rest).

    Jetzt könnte eigentlich der Untergangszug anrollen mit seinem Buffer-Overflow — immerhin ist nunmehr schön zu sehen, wie bei


    retadr
    ebp: ebp_b4
    intarr(2)
    intarr(1)
    intarr(0)
    esp:

    vermittels “intarr(4)=da_will_ich_hin” eine Umleitung implementiert wird (wenn es denn so einfach wäre).

    Die Ungnade der frühen Geburt — solch wesentliches (insbesondere cpu-spezifisches) Wissen bekam ich in meiner Anfangszeit bestenfalls über die Fernleihe, ansonsten unter der Hand als Kopie {von Kopie}* (selbstverständlich Papierkopien mit wachsendem Grauschleier).

  2. #2 rolak
    April 25, 2013

    also doch &nbsp;… :( das pre-tag wird gefressen

  3. #3 DeLuRo
    April 25, 2013

    das pre-tag wird gefressen

    Blog-Autoren mit “Rechten” scheinen privilegiert zu sein – bei Marcus hatte es geklappt.
    Das Experiment von Marcus mit demselben Code wie in Teil 5:
    Dies
    ist
    ein
    Test

    Was kommt bzgl. Linksbündigkeit raus?

  4. #4 DeLuRo
    April 25, 2013

    anders schaut’s aus, nämlich nach links gequetscht — was die Annahme bestätigt: man muss Rechte haben, damit’s rechts bleibt… :-)

  5. #5 rolak
    April 25, 2013

    Die Einrückung ist halb-lebendig aka zombiesk: Luur ens, DeLuRo, im feed leben sie, hier nicht.

  6. #6 Marcus Frenkel
    April 25, 2013

    @rolak

    Zum Verwalten des _Speicherbedarfs_ der _nicht-statischen/-globalen_ Variablen

    Beim Speicherbedarf gehe ich mit, das ist im Artikel etwas ungenau geschrieben. Statische/globale Variablen dürften meines Wissens aber auch auf dem Stack liegen.

    Stack .. von fester Größe

    Jein. Typischerweise ja, aber nicht aus Prinzip – immerhin sind die Mechanismen zur Erweiterung von Stack (nach ‘unten’) und Heap (nach ‘oben’) und andersrum spätestens seit dem 386er cpu-unterstützt. Daß sich typische 08/15-Compiler weigern, solche Möglichkeiten umzusetzen, sollte kein Argument sein – immerhin habe (nicht nur) ich derart flexible Programme geschrieben

    Dass sich der vom OS zugewiesene Stack-Bereich dynamisch zur Laufzeit vergrößern lässt, wäre mir neu (Heap zählt nicht). Gibt es dazu eine Quelle?

    die Adresse der Speicherzelle, bis zu welcher der Stack bisher schon gewachsen ist

    (wg ebp/esp:) zumindest beim x86 zeigt esp auf das nächste freie Byte, also Dein Wert +1.

    Das ist im Artikel wohl etwas missverständlich formuliert. Die Abbildungen sollten es aber klarer machen.

    @Thema pre-Tag
    Ja, da habe ich auch keine Ahnung, was da los ist. Wenn sich jemand mit WordPress und diesem Thema auskennt…immer her mit den Informationen.

  7. #7 michael
    April 26, 2013

    > Der Speicherbereich des Stacks an sich kann also weder wachsen noch schrumpfen

    man setrlimit:

    ….
    RLIMIT_STACK
    The maximum size of the process stack, in bytes. Upon reaching
    this limit, a SIGSEGV signal is generated. To handle this sig‐
    nal, a process must employ an alternate signal stack (sigalt‐
    stack(2)).

    aber nicht über konfigurierte hard limits hinweg.
    http://linux.die.net/man/5/limits.conf

  8. #8 rolak
    April 26, 2013

    auch auf dem Stack

    et ceterum censeo: Nö. Das typische Speicher-Layout in einer adressflachen Umgebung dürfte so aussehen:
    0:        code¹
    dat0:     compiletime known data values¹ ²
              uninitialized data
    heap0:    heap
    heapmax:  -unused gap-
    stacklow: stack
    stackhi:  end-of-mem ($F...F)

    wobei die Teile mit ¹ mehr oder weniger 1:1 aus dem executable geladen werden, die mit ² Konstanten mit Speicherabbild (strings et al) oder initialisierte Variablen sind.

    Gibt es dazu eine Quelle?

    Aber sicher doch – allerdings werde ich (ganz speziell um diese Tageszeit) nicht Seite und Abbildungs# heraussuchen. Bei Intels zu Hause gibt es die IA-32 Architectures Software Developer’s Manuals; eine bis aufs Grausamste detaillierte Aufdröselung des historisch gewachsenen und daher grotesk strukturierten segment/page/tss/..-selectors findet sich meines Wissens nach in #3. Der ‘unused gap’ aus dem ‘Bildchen’ oben sind keine real existierenden Speicherseiten zugewiesen, ein Zugriff löst einen trap aus, die auffangende proc kann -falls gewünscht- Seiten hinzufügen, egal ob nun bei Stack oder Heap. Mir ist so, als wäre in einem dieser Selektoren sogar die Wuchsrichtung (auf, ab) der Adressierung vermerkt.
    Der Stackcheck der Compiler bzw deren RTL ist ja nur ein Vergleich der Art ‘Ist (esp-wanted)>stacklow)?’, der durch Änderung der initialisierten Variable stacklow angepaßt wird.

    WordPress … immer her

    Ist wohl eine Filtereigenschaft des Textfensterchens, ob die von euch Subusern geändert werden kann, ist fraglich. Jetzt, da man es weiß, läßt es sich umgehen – hatte ich schon früher notiert, es aber wg Deines Tests allzu früh wieder verworfen.
    Außerdem werde ich mich erst im Laufe des Jahres genötigt sehen, WP näher und intensiver kennenzulernen.

     

  9. #9 Marcus Frenkel
    April 26, 2013

    @rolak

    Das typische Speicher-Layout in einer adressflachen Umgebung dürfte so aussehen:

    Ah, gerade im Netz gefunden; sie liegen im data segment. Wieder was gelernt.

    @michael
    Danke für den Hinweis, das kannte ich auch nicht. Sagt aber, dass für unprivilegierte Prozesse das harte Limit fest ist – passt ja fast zum Text. ;)
    Ich passe ihn etwas an.

  10. #10 CM
    April 27, 2013

    Mir geht die Verbindung zu C++ nicht so ganz auf – abgesehen davon natürlich, daß man C-like mit Speicheradressen jonglieren kann, wenn man möchte. Kann mich jemand (oder der nächste Post) erleuchten?

  11. #11 Marcus Frenkel
    April 27, 2013

    @CM
    Es gibt in diesem Artikel keine direkte Verbindung explizit zu C++; das ist ein Grundlagenartikel, der das Verständnis späterer Techniken (insbesondere die Pointer) leichter verständlich machen soll.