Dynamische lokale Variablen in C
In C muss der Platzbedarf von lokalen (automatischen) Variablen bereits zur Übersetzungszeit bekannt sein. In diesem Artikel wird eine einfache Funktion vorgestellt, mit der zur Laufzeit Platz für weitere lokale Variablen geschaffen wird, die genauso wie die vom Compiler bereitgestellten beim Verlassen der Funktion „zerstört“ werden.
Diese Funktion nenne ich in Anlehnung an [1] alloca(), und sie ist wie folgt deklariert:
void *alloca( size )
unsigned int size;
Falls Ihr C-Compiler den Typ void nicht kennt (wie z.B. MEGAMAX, mit dem ich arbeite), können Sie stattdessen genausogut char verwenden. Der bezeigte Typ tut nichts zur Sache.
Listing 1 zeigt die Funktion, wobei ein Inline-Assembler benutzt wird. Falls Ihr Compiler dieses Feature nicht hat, finden Sie in Listing 2 dieselbe Funktion als Assembler-Programm. Dieses können Sie beim Linken Ihrem Programm anfügen. Der einzige Unterschied der beiden Versionen ist der UNLK-Befehl ganz oben bei Listing 1. Eristnotwendig, weil der Compiler an den Anfang jeder C-Funktion ein LINK A6,#x stellt, auch wenn sie keine lokalen Variablen hat. Dieser Befehl legt 4 Bytes auf dem Stack ab, und die müssen wieder heruntergeholt werden, damit alloca() funktioniert. Ein guter Assembler setzt freilich nicht aus heiterem Himmel LINKs ins Programm, und das UNLK kann beim Assemblerprogramm weggelassen werden.
Stack-Akrobatik
Nun zur eigentlichen Arbeitsweise: Wie bereits erwähnt, steht am Anfang jeder C-Funktion ein LINK A6,#x. Dieser Befehl sichert zunächst den Wert von A6 auf dem Stack. Das ist erforderlich, damit alle Funktionen das gleiche Register verwenden können. Dann wird der Stackpointer (SP bzw. A7) nach A6 gebracht und der Wert x (er muß negativ sein) zum SP addiert. Effekt dieser komplizierten Angelegenheit ist, daß auf dem Stack ein „Loch“ entsteht. Dieses Loch wird als Platz für die lokalen Variablen benutzt. Zusätzlich hat man in A6 einen Zeiger auf das obere Ende des Lochs, der zum Zugriff auf die Variablen verwendet wird. Am Ende der Funktion muß dann der Befehl UNLK A6 erfolgen. Damit wird das Ganze rückgängig gemacht, d.h. A6 in den SP übertragen und der alte Wert von A6 vom Stack geholt. Danach ist alles wieder beim alten, wie vordem LINK-Befehl. Und genau diese Tatsache, daß UNLK keine Information benötigt, wieviel Platz durch LINK reserviert wurde, macht sich alloca() zunutze.
Man kann sich die Vorgänge anhand der Grafiken in Bild 1 vorstellen. Das erste Bild zeigt den vorher geschilderten Zustand. Beim Aufruf von alloca() wird der Parameter size auf den Stack geschoben, ebenso die Rücksprungadresse und das Register A6 (wegen des vom Compiler eingesetzten LINK-Befehls). alloca() führt zuerst ein UNLK aus, um das störende LINK rückgängig zu machen. Dann wird die Rücksprungadresse vom Stack geholt und in A0 gemerkt. Jetzt kommt der eigentliche Sinn der Sache: Vom SP wird der Wert size abgezogen, genauso wie es LINK tut. Es hat auch denselben Effekt: auf dem Stack entsteht wiederum ein Loch. Nur ist die Größe des Lochs nicht im Programm festgeschrieben, sondern wird von size angegeben. Damit hätten wir unseren dynamisch allozierten Speicher. Nun muß alloca() noch einen Zeiger auf diesen Speicher zurückgeben, und das ist SP+2. Dieser Wert wird in D0 geladen und mit JMP (A0) zurückgesprungen. Die Rücksprungadresse haben wir ja vom Stack heruntergeholt, also ist RTS nicht möglich.
Warum ist eigentlich der Zeiger SP+2! Die aufrufende Funktion muß nach der Rückkehr noch eine Stack-Korrektur durchführen, d.h. den Platz für die Parameter wieder freigeben. In unserem Fall sind das 2 Bytes. Nach dem JSR alloca steht also noch ADDQ.L #2,SP (oder so ähnlich). Daher beginnt der allozierte Speicher nicht bei SP, sondern bei SP+2. Er wird aber dadurch nicht kürzer, da der Platz, den der Parameter eingenommen hat, jetzt zum allozierten Speicher gehört.
Es gibt aber auch ein paar Compiler, die nach einer besonderen Methode bei der Parameterübergabe arbeiten (z.B. DRI). Sie reservieren 4 Bytes mehr für die lokalen Variablen, als eigentlich nötig wäre. Diese Bytes werden dann für Parameter genutzt. Im Fall alloca() erfolgt bei ihnen keine Stack-Korrektur, da nur 2 Bytes an Parametern da sind. Man muß also bei solchen Compilern SP+4 anstatt SP+2 einsetzen.
Nun die schlechte Nachricht...
So schön wie alloca() funktioniert, im Leben gibt es leider keine Vorteile ohne Nachteile. Und der Nachteil von alloca() ist, daß eine Funktion, die dynamische lokale Variablen nutzt, keine Registervariablen benutzen darf.
Die Erklärung ist einfach: Werden Register verwendet, müssen deren alte Inhalte irgendwohin gerettet werden, man will ja nicht die Registervariablen einer aufrufenden Funktion zerstören. Der Compiler macht das, indem er die in Frage kommenden Register mit einer MOVEM-Anweisung auf den Stack schiebt und vor dem Rücksprung wieder zurückholt. Und das Ablegen geschieht unglücklicherweise genau unter den lokalen Variablen. alloca() würde seinen Speicher jetzt unterhalb der Register anlegen, so daß beim Funktionsende nicht die alten Registerwerte zurückgeholt würden, sondern der Inhalt des dynamischen Speichers, was natürlich Unsinn ergibt.
Es wäre zwar eine Änderung an alloca() denkbar, die die geretteten Registerwerte nach unten verschiebt und auf diese Weise Platz reserviert. Doch leider ist die Länge des Registerbereichs nicht bekannt, nur die Länge Register + lokale Variable (A6-SP). Man müßte also, wenn, dann beide zusammen verschieben, um neuen Platz auf dem Stack zu gewinnen. Bitte denken Sie selbst alle Möglichkeiten durch (ich habe mir lange genug den Kopf zerbrochen). Wenn nicht eine der beiden Teillängen bekannt ist, kommt entweder Unsinn heraus, oder die vorher vorhandenen Inhalte der lokalen Variablen gehen verloren. Und das ist nun wirklich nicht der Sinn von dynamischem Speicher.
Wo die Freiheit endet
Wenn man nun exzessiv Stack-Platz beansprucht, kann dieser natürlich auch zu klein werden und überlaufen. Um die katastrophalen Folgen zu vermeiden, gibt es noch eine weitere Funktion zu alloca(), die feststellt, wieviel Platz auf dem Stack noch frei ist (auch [1]). Manche Compiler haben eine solche Stack-Prüfung schon eingebaut. Wer einen solchen sein eigen nennt, der benötigt stackavail() nicht, für den Rest der Menschheit leistet es aber gute Dienste (z.B. auch für rekursive Funktionen).
stackavail() berechnet nun aus den Segmentlängen, die in der Basepage vermerkt sind, das obere Ende der BSS, das gleichzeitig unteres Ende des Stacks ist. Wird dieser Wert vom aktuellen SP abgezogen (um 12 Byte korrigiert, die stackavail() selbst belegt), hat man die Länge des freien Stacks. Um die Funktion auf Ihrem Compiler zu implementieren, sehen Sie bitte in der Beschreibung nach, wie Sie an die Basepage-Adresse kommen. Meist wird bei der Initialisierung eine Variable _base oder so ähnlich angelegt, die dann als extern deklariert wird.
Der Vorteil dieser Berechnungsmethode ist, daß nirgendwo die Größe des Stacks benötigt wird, die manchmal nicht ohne weiteres zur Laufzeit verfügbar ist.
Literatur:
[1] Schildt, Herbert, „C-Befehlsbibliothek“ McGraw-Hill, 1988
/* alloca() reserviert Platz auf dem Stack */
/* Die aufrufende Funktion darf keine Regi- */
/* stervariablen verwenden! */
char *alloca(size)
unsigned int size;
{ asm{ unlk A6 /* link rückgängig */
move.l (A7)+,A0 / * Rücksprungadr. */
move.w (A7),D0
suba.w D0,A7 /* Platz machen */
move.l A7,D0
addq.l #2,D0 /* Zeiger zurück */
jmp (A0) /* Rücksprung */
}
}
Listing 1: Die alloca()-Funktion in C mit Inline-Assembler
; alloca() reserviert Platz auf dem Stack
; Die aufrufende Funktion darf keine Regi-
; stervariablen verwenden!
alloca: move.l (a7)+,a0 ; Rücksprungadr.
move.w (a7),d0
suba.l d0,a7
move.l a7,d0
addq.l #2,d0
jmp (a0)
Listing 2: Die allocai)-Funktion in Assembler
/* stackavail() liefert den jetzt freien Platz */
/* auf dem Stack */
long stackavail()
{ long stack;
extern long *_base;
/* jetzigen SP in Variable 'stack' bringen */
asm{ move.l A7,stack(A6) }
return( (
stack+12 /* akt. Stack mit Korrektur */
) - ( /* unteres Ende des Stacks : */
(long)_base+ /* Basepageadr. */
_base[3]+ /* Text size */
_base[5]+ /* Data size */
_base[7]+ /* Bss size */
256L /* Basepagesize */
)
);
}
Listing 3: Die stackavail()-Funktion
Roman Hodek