Intel - Prozessoren bieten mittels ihrer Register und Befehlscode die Nutzung eines sogenannten "procedure stack" an. Dies ist ein Speicherbereich, der für die Verwaltung folgender Daten vorgesehen ist: Rücksprungadressen und Parameter für Funktionen, lokale Parameter sowie kurzfristig zu speichernde kleine Datenmengen.

Das folgende Schaubild skizziert diesen Stack:

In der Regel hat jeder Thread eines Programmes auch einen eigenen Stack; jedoch kann man sich beliebig viele verschiedene Stacks selbst erzeugen (solange noch genügend freier Speicher vorhanden ist).

Der Stack wird initialisiert, indem er eine Basisadresse bekommt, die man "Bottom of Stack" nennt. Auf einem Stack kann man Daten ablegen und wieder abrufen nach dem sogenannten "LIFO" - Prinzip ("last in first out"). Dies gilt zumindest für die Befehle PUSH und POP (die gleich noch beschrieben werden), es gibt aber auch die Möglichkeit des wahlfreien Zugriffes innerhalb eines sogenannten "Stack Frame" (der ebenfalls noch beschrieben wird).

Wenn Daten auf dem Stack abgelegt werden, dann "wächst" der Stack in Richtung niedrigerer Speicheradressen; dies stellt für Anfänger häufig eine mentale Hürde dar, weil ein "normales Array" in C oder C++ zum Beispiel in höhere Speicheradressen "wächst".

Mit dem Prozessor - Befehl "PUSH" kann man Daten auf dem Stack ablegen (zum Beispiel aus einem Register, direkt aus einer Speicherstelle, oder einen konstanten Wert), und mit "POP" holt man die obersten Daten wieder zurück, ebenfalls in ein Register oder direkt in den Speicher.

Nachdem ich schon gezeigt habe, wo der "Boden" des Stack liegt (der steht nach dem Einrichten eines Stacks immer fest), muß ich noch erklären, wo das "obere Ende" ist: Das sogenannte "ESP - Register" (ESP = "extended stack pointer"), ein bestimmtes 32-Bit Register in Intel - Prozessoren, zeigt stets auf den obersten gültigen Stack - Wert. Da die 16-Bit-Zeit nun wirklich vorbei ist, beschränke ich mich auf die 32-Bit- Welt, und man kann einfach davon ausgehen, daß sowohl PUSH / POP wie auch das ESP - Register stets mit 32-Bit-Werten arbeiten.

Wichtig ist, die Begriffe "oben" und "unten" nicht mit der relativen Lage im Speicher zu verwechseln, die ist nämlich umgekehrt, wie oben beschrieben (und wie im Schaubild zu sehen).

Wenn der Prozessor ein Programm abarbeitet, dann liegt dieses immer in Maschinencode vor, denn etwas anderes versteht er nicht. Maschinencode entsteht in aller Regel durch das Compilieren bestimmter Programmiersprachen, wie z.B. Assembler oder C++.
Wenn von einer Funktion in eine andere gesprungen werden soll (dafür gibt es den "CALL" - Befehl"), so macht der Prozessor folgendes: er rechnet aus, welcher Befehl nach diesem CALL in der noch aktuellen Funktion drankommen würde, und legt die Adresse dieses Befehls automatisch auf den Stack (das nennt man die "Rücksprungadresse"); dies passiert immer beim CALL - Befehl, ohne daß man etwas dazu tun müßte. Dann wird die aufgerufene Funktion abgearbeitet, und an deren Ende steht in der Regel der Befehl "RET", der den obersten Wert vom Stack runternimmt, und diesen in den sogenannten "Instruction Pointer" lädt, einem Register, welches dem Prozessor sagt, welcher Befehl als nächstes abgearbeitet werden soll.

Es passiert aber in aller Regel noch ein wenig mehr bei einem Funktionsaufruf. Das folgende Codebeispiel paßt exakt zum obigen Schaubild:

Wenn diese Beispielfunktion von irgendwo aufgerufen wird, dann müssen zwei Parameter übergeben werden. In meinem Beispiel sind es zwei 32-Bit-Werte. Ich werde die verschiedenen Aufrufkonventionen gleich erklären, und gehe der Einfachheit halber hier vom "stdcall" aus. Dabei legt der Aufrufer die nötigen Parameter vor dem Aufruf auf dem Stack ab, noch vor der Rücksprungadresse (die ja beim CALL - Befehl automatisch drauf kommt). Diese beiden Parameter kann man oben im Stack - Schaubild auch sehen.

Wenn man dann in die Funktion hineingesprungen ist, dann wird ein Stück Code abgearbeitet, welches die lokalen Variablen einrichtet, und den sogenannten stack frame damit fertigstellt: In der Fachsprache heißt das "Prolog". Am Ende der Funktion werden diese Initialisierungen rückgängig gemacht, das heißt dann "Epilog".

In meinem Beispiel sind die beiden lokalen Variablen zufällig auch 32-Bit-Werte, so daß es schön auf den Stack paßt. Im Schaubild sind die lokalen Variablen zu Erkennen. Und jetzt kann man auch den Begriff Stack Frame verstehen: Es ist wie ein Rahmen, der um einen Teil des Stacks gezogen wird. Dieser Rahmen enthält alle Parameter, die lokalen Variablen und die Rücksprungadresse. Das sogenannte EBP - Register (EBP = "extended base pointer"), ebenfalls ein 32-Bit-Register in Intel - Prozessoren, bildet dabei die Grenze zwischen lokalen Variablen auf der einen Seite und Rücksprungadresse / Parameter auf der anderen Seite. Wenn man also im Dissasembler Operanden der Form "[EBP+4h]" findet, dann handelt es sich um die Rücksprungadresse, bei "[EBP+8h], [EBP+0Bh], ..." handelt es sich um Aufrufparameter, und bei "[EBP-4h], [EBP-8h], ..." geht es um lokale Variablen.

Da beim Wechsel der aufrufenden Funktion, die ja selbst einen Stack Frame hat, zur aufgerufenen Funktion, die einen neuen, eigenen Stack Frame kriegt, der EBP - Zeiger natürlich verschoben werden muß, geschieht auch das im Prolog. Der alte Wert des EBP wird für die Dauer des Aufrufes in genau dem Stack - Register gespeichert, auf das der EBP währenddessen zeigt (ist doch praktisch!). Im Epilog wird der alte EBP - Wert wieder restauriert, damit er in der Aufrufer - Funktion stimmt.

Wie oben schonmal angedeutet wurde, gibt es verschiedene Möglichkeiten, wie man einer Funktion ihre Parameter übergibt, und wie (oder ob überhaupt) der Stack für die aufgerufene Funktion eingerichtet werden soll.

Am meisten Verbreitung findet der sogenannte stdcall (="standard call"). Dabei wird genau das gemacht, wie oben beschrieben: Der Aufrufer legt die Parameter auf dem stack ab, und die aufgerufene Funktion macht nachher den stack selbst wieder sauber und bringt ihn wieder in den Zustand, den der Aufrufer hinterlassen hatte (die Parameter sind dann auch weg).

Diese Variante ist am performantesten, und bis auf zwei Funktionen (wsprintfA und wsprintfW) nutzen sämtliche Win32 API - Funktionen diese Aufrufkonvention. Dies gilt auch für COM, und für die alten Visual Basic - Programme (bis Version 6.0, noch nicht .NET), die mit der Option "native" compiliert wurden.

Die zweite Variante, ist cdecl. Es gibt nämlich in der Sprache C (und natürlich in C++) die Möglichkeit, einer Funktion eine variable Parameterliste zu geben. Das bekannteste Beispiel ist sicher die "printf" - Funktion in all ihren Variationen, die das flexible Füllen eines formatierten Strings durchführt mit einer beliebigen Anzahl an Parametern.

Wenn nun die Anzahl der Parameter variabel ist, dann kann die Funktionsimplementierung von printf unmöglich wissen, wieviele Parameter auf dem Stack hereinkommen. Daher kann sie auch nicht ihren Stack Frame selbst aufbauen, und sie kann den Stack auch nicht anschließend wieder zurückführen. Da nur der Aufrufer weiß, wieviele Parameter er übergibt, muß er diese beiden Arbeiten (Prolog und Epilog) selbst durchführen. Dies gilt nur für die Parameter, denn die lokalen Variablen richtet sich natürlich die aufgerufene Funktion selbst ein.

Woher weiß denn der Aufrufer, ob er mit stdcall oder mit cdecl - Konvention aufrufen soll ? Ganz einfach: Der Programmierer der aufgerufenen Funktion entscheidet es, und er schreibt es entweder direkt in die Deklaration der Funktion (mit den Schlüsselworten __stdcall oder __cdecl), oder er stellt es in den Complieroptionen ein. Compiler und Linker müssen dann am Ende selbst herausarbeiten, wie die Konventionen aussehen, und wie die Parameterübergabe durchzuführen ist.

Eine dritte Konvention soll noch erwähnt werden, nämlich der thiscall. Dieser ist fast identisch zur cdecl - Variante, nur daß zusätzlich noch der "this" - Pointer im ECX - Register übergeben wird.

Es gibt noch zwei Exoten (fastcall und naked call), für die sich aber nur Borland Delphi- Entwickler (fastcall) und Treiberprogrammierer (naked call) interessieren.

Eine Sache, die nicht unerwähnt bleiben darf, ist die sogenannte FPO ("Frame Pointer Omission"). Bei Programmen, die mit Optimierung compiliert werden (also in der Regel nur die "Release" - Variante), kann es vorteilhaft sein, keinen Stack Frame in bestimmten Funktionen einzurichten. Dies ist zum Beispiel dann vorteilhaft, wenn keine oder wenige Parameter übergeben werden, oder keine oder wenige lokale Variablen existieren. Dann kostet ein Stack unnötig Zeit. Solche Fälle erkennt man daran, daß in Assembler-Operationen Ausdrücke der Form [ESP+8h] verwendet werden. Hierbei muß man höllisch aufpassen, denn derselbe Ausdruck kann wenige Zeilen später schon [ESP+20h] heißen, weil andere Operationen den Stack verändert haben. Optimierung und gute Lesbarkeit / Verständlichkeit schließen sich dort leider gegenseitig aus.

Nach dieser Einführung wird klar, dass der Stack besonders gut geeignet ist für Speicheranforderungen, die lokal begrenzt und volumenmäßig überschaubar sind: Der Stack ist in aller Regel komplett im Cache-Speicher des Prozessors, und die Arbeit mit Speicherzellen im Cache geht bedeutend schneller als der Zugriff auf den Hauptspeicher. Es gibt verschiedene Untersuchungen und Messungen hierzu, dabei kommt es auf die Verbindung zwischen Hauptspeicher und Prozessor an, aber man kann ganz grob allgemein sagen, daß ein Geschwindigkeits-Verbesserungsfaktor der Größenordnung 1000 nicht übertrieben ist. Dies macht sich in Schleifen natürlich extrem bemerkbar.

Dazu kommt, daß in Multiprozessor - Systemen dieser Vorteil noch viel größer werden kann, da dort mit hohem Aufwand ein Speicher-Management betrieben wird, welches aufpaßt, daß alle Prozessoren bei Änderungen des globalen Speichers benachrichtigt werden, sofern deren Cache-Speicher in einen veränderten globalen Bereich "hineinzeigt". Dann muß meistens der komplette Cache neu geladen werden.

Ein einfaches Beispiel, wie man Speicheranforderungen optimieren kann:

void zeigeWarnung(TCHAR * lpszWarnung)
{
  if (lpszWarnung)
  {
    TCHAR * lpszTextMitUhrzeit = 
		new TCHAR[_tcslen(lpszWarnung) + 32];

    _stprintf(lpszTextMitUhrzeit, _T("%s: %s"), getUhrzeitString(), lpszWarnung);
    MessageBox(NULL, lpszTextMitUhrzeit, _T("Warnung!"), MB_OK);
    delete [] lpszTextMitUhrzeit;
  }
}               

... kann ersetzt werden durch folgende, viel performantere Variante:

void zeigeWarnung(TCHAR * lpszWarnung)
{
  if (lpszWarnung)
  {
    TCHAR * lpszTextMitUhrzeit = 
		(TCHAR *) _alloca(_tcslen(lpszWarnung) + 32);

    _stprintf(lpszTextMitUhrzeit, _T("%s: %s"), getUhrzeitString(), lpszWarnung);
    MessageBox(NULL, lpszTextMitUhrzeit, _T("Warnung!"), MB_OK);
    // Kein Aufräumen nötig, der Speicher wird nach der Funktion wieder
    // freigegeben.
  }
}               

Die Funktion "_alloca()" wird von Microsoft Visual C++ zum Zweck der Stack - Speicherallokation zur Verfügung gestellt, andere Compiler bieten dafür ähnliche Funktionen. Die Zahl der zu allokierenden Bytes wird automatisch auf ein Vielfaches von 4 Bytes erhöht (das sogenannte alignment).

Einen kleinen Haken hat die Sache allerdings: Man muß aufpassen, daß man nicht den Stack mit überhöhten Speicheranforderungen "sprengt", denn sonst endet _alloca() mit einer stack-overflow-exception. Daher auch der Hinweis, nur maßvolle Speicheranforderungen damit zu realisieren, oder entsprechend die Stackgröße zu erhöhen.

Doch woher weiß man überhaupt, was in diesem Zusammenhang "maßvoll" heißt, und wie groß der Stack tatsächlich ist ? Wenn man mit Microsoft Visual C++ arbeitet, kann man mit dem Compilierparameter /F festlegen, wie groß der Stack sein soll. Standardmäßig beträgt die Größe 1 MB. Die Anweisung /F0x1000 zum Beispiel legt die Stackgröße auf 4 kB fest (= 4096 Bytes, eben 0x1000 hexadezimal). Wichtig dabei ist, daß nur vielfache von 4096 Bytes (also vielfache von 0x1000) vom Compiler akzeptiert werden, die sogenannte PAGESIZE. Gibt man andere Werte an, wird auf das nächste Vielfache aufgerundet. In Visual Studio 6 zum Beispiel erreicht man diese Einstellung auch über "Project Settings / Link / Stack allocations / Reserve".

Man sollte sich stets durch exception-handling vor einem stack overflow schützen, wenn man mit _alloca arbeitet, und nicht absolut sicherstellen kann, daß in jeder Situation genügend Platz auf dem Stack verfügbar ist. Ein kleines Beispiel demonstriert, wie man eine solche Exception abfangen kann:

#include "stdafx.h"
#include "malloc.h"

int main(int argc, char* argv[])
{
	__try
	{
		_alloca(0x00FFFF00);
	}
	__except(1) // EXCEPTION_EXECUTE_HANDLER 
	{
		printf("Stack geplatzt !");
	}

	return 0;
}		

Wenn man hier mit dem Parameter der Funktion _alloca() etwas experimentiert, kann man sowohl den erfolgreichen wie auch den gescheiterten Aufruf testen.

Ein interessantes Projekt inkl. Sourcecode zum analysieren des Stacks zur Laufzeit findet sich bei Codeproject: Stackwalker.