Der Stack
Ich habe mich in letzter Zeit ein wenig mit der Erstellung von Maschinencode und dem Stack beschäftigt. Dies hatte verschiedene Gründe. Zum Einen schreibe ich gerade an einem Simulator für AVR-Geräte, welcher natürlich Maschinencode ausführen soll und zum Anderen wollte ich einfach mal rein schauen und ein bisschen schlauer werden.
Wie dem auch sei. Ich bin dabei auf etwas Interessantes gestoßen. Wenn eine Funktion den Stack für die lokalen Variablen anlegt, so wird der Stack-Pointer immer wieder nach einem Wert ausgerichtet. Normalerweise handelt es sich dabei um den Wert 16. Dies geschieht bei dem anlegen von normalen lokalen Variablen, genauso wie dem definieren von variablen Arrays und auch von dem allozieren des Hauptspeichers auf dem Stack. Dazu möchte ich nun ein paar kleine, einfache Beispiele anbringen. Diese werden dann übersetzt und die de‑assemblierte Datei wird dann untersucht.
Zu dem Programmcode an sich. Natürlich soll dies kein Programm in einer produktiven Umgebung sein. Es dient nur zu Demonstrationszwecken. Weiterhin nutze ich den gcc in der folgenden Version:
$ gcc --version gcc (Gentoo 4.4.5 p1.2, pie-0.4.5) 4.4.5 Copyright (C) 2010 Free Software Foundation, Inc. Dies ist freie Software; die Kopierbedingungen stehen in den Quellen. Es gibt KEINE Garantie; auch nicht für MARKTGÄNGIGKEIT oder FÜR SPEZIELLE ZWECKE.
Nun also habe ich mir ein kleines Programm erstellt, welches in einer Funktion eine feste Puffergröße hat. Diese Puffergröße wird zu Compilezeit definiert.
#include <stdlib.h>
#include <string.h>
#if !defined( SIZE ) || SIZE <= 0
#define SIZE 1
#endif
void foo( void ) {
char buffer[ SIZE ];
strncpy( buffer, "AAAAAAAAAAAAAAAA", SIZE );
buffer[ ( SIZE - 1 ) ] = 0;
}
int main( void ) {
foo();
return EXIT_SUCCESS;
}
Ich werde nun erst einmal erklären wo der Stack für die lokalen Variablen eingerichtet wird. Danach werde ich eine Tabelle erstellen wo sichtbar ist, wie die Größe des Stacks durch die Größe des Puffers beeinflusst wird.
Zuerst wird das Programm kompiliert. Danach schauen wir uns den erzeugten Maschinencode an.
$ gcc -DSIZE=2 stack.c -o stack $ objdump -d stack […] 0000000000400534 <foo>: 400534: 55 push %rbp 400535: 48 89 e5 mov %rsp,%rbp 400538: 48 83 ec 10 sub $0x10,%rsp 40053c: b9 5c 06 40 00 mov $0x40065c,%ecx 400541: 48 8d 45 f0 lea -0x10(%rbp),%rax 400545: ba 02 00 00 00 mov $0x2,%edx 40054a: 48 89 ce mov %rcx,%rsi 40054d: 48 89 c7 mov %rax,%rdi 400550: e8 eb fe ff ff callq 400440 <memcpy@plt> 400555: c6 45 f1 00 movb $0x0,-0xf(%rbp) 400559: c9 leaveq 40055a: c3 retq […]
Am Anfang dieser Funktion befindet sich der Funktionsprolog[1]. Der Stackframe wird eingerichtet. Dies ist unabdingbar, da bei dem Ende der Funktion garantiert werden muss das vom Stack alle Variablen wieder gelöscht werden.
- Alter StackFrame
- Rücksprungadresse
- BasePointer wird gesichert (Anfang des alten StackFrames)
- Der aktuelle StackPointer ist der Anfang des Aktuellen StackFrame
So schaut der aktuelle Stack aus wenn das Programm bis zur Speichernummer 0×400535 ausgeführt wird. Danach werden die lokalen Variablen eingerichtet. Am Ende übernimmt das „leave“ wieder die Aufräumarbeiten. Somit ist leave ein Synonym für[2]:
mov %rbp,%rsp pop %rbp
Damit wird der alte StackFrame wieder eingerichtet und mit return wird dann die Rücksprungadresse von dem Stack gelesen. Somit ist der Stack wieder aufgeräumt.
Weiterhin werden an Speicherstelle 0×400538 die lokalen Variablen alloziert. Wie man sieht werden hier 0×10 also 16 Byte an Variablen reserviert. Ich habe aber als Größe 2 angegeben. Da es sich um char handelt also 2 Byte. Ich möchte nun eine Tabelle erstellen. Diese Zeigt jeweils die Größe welche ich reservieren möchte und die tatsächlich reservierte Größe an.
SIZE (in Byte) Stack SIZE(in Byte)
2 16
3 16
5 16
16 16
17 32
18 32
31 32
32 32
33 48
8192 8192
8193 8208
Wie hier zu sehen ist, handelt es sich jeweils um einen Teiler von 16. Ähnlich verhält es sich bei der Verwendung von alloca, welches Speicherplatz auf dem Stack reserviert. Dies bedeutet der Gültigkeitsbereich der Variablen endet mit Austritt aus der Funktion. Wie bei einer normalen lokalen Variablen. Nur ist die Größe der Variablen dynamisch. Das bringt ab und an ein paar kleine Vorteile. Denn man muss den Speicherplatz nicht wieder mit free frei räumen.
Nun zu dem Beispiel:
#include <stdlib.h>
#include <string.h>
#if !defined( SIZE ) || SIZE <= 0
#define SIZE 1
#endif
void foo( int i ) {
char* buffer = NULL;
buffer = alloca( i );
if( NULL != buffer ) {
strncpy( buffer, "AAAAAAAAAAAAAAAA", SIZE );
buffer[ ( i - 1 ) ] = 0;
}
}
int main( void ) {
foo( SIZE );
return EXIT_SUCCESS;
}
Im Prinzip der gleiche Code. Nur erfolgt die Zuweisung des Speichers mit alloca und ich gebe die Größe des Puffers als Parameter an. Ich übersetze dies und schau mir wieder die de-assemblierte Datei an.
$ gcc stack.c -o stack -DSIZE=2 $ objdump -d stack […] 0000000000400534 <foo>: 400534: 55 push %rbp 400535: 48 89 e5 mov %rsp,%rbp 400538: 48 83 ec 20 sub $0x20,%rsp 40053c: 89 7d ec mov %edi,-0x14(%rbp) 40053f: 48 c7 45 f8 00 00 00 movq $0x0,-0x8(%rbp) 400546: 00 400547: 8b 45 ec mov -0x14(%rbp),%eax 40054a: 48 98 cltq 40054c: 48 83 c0 0f add $0xf,%rax 400550: 48 83 c0 0f add $0xf,%rax 400554: 48 c1 e8 04 shr $0x4,%rax 400558: 48 c1 e0 04 shl $0x4,%rax 40055c: 48 29 c4 sub %rax,%rsp 40055f: 48 89 e0 mov %rsp,%rax 400562: 48 83 c0 0f add $0xf,%rax 400566: 48 c1 e8 04 shr $0x4,%rax 40056a: 48 c1 e0 04 shl $0x4,%rax 40056e: 48 89 45 f8 mov %rax,-0x8(%rbp) 400572: 48 83 7d f8 00 cmpq $0x0,-0x8(%rbp) 400577: 74 29 je 4005a2 <foo+0x6e> 400579: b9 ac 06 40 00 mov $0x4006ac,%ecx 40057e: 48 8b 45 f8 mov -0x8(%rbp),%rax 400582: ba 1f 00 00 00 mov $0x1f,%edx 400587: 48 89 ce mov %rcx,%rsi 40058a: 48 89 c7 mov %rax,%rdi 40058d: e8 ae fe ff ff callq 400440 <strncpy@plt> 400592: 8b 45 ec mov -0x14(%rbp),%eax 400595: 48 98 cltq 400597: 48 83 e8 01 sub $0x1,%rax 40059b: 48 03 45 f8 add -0x8(%rbp),%rax 40059f: c6 00 00 movb $0x0,(%rax) 4005a2: c9 leaveq 4005a3: c3 retq […]
Der Funktionsprolog ist wieder vorhanden und in 0×400538 und 0×40053F wird der Zeiger eingerichtet. Die Zeile 0×40053C lädt den Parameter i nach EDI. Nachzulesen ist dies bei Calling Conventions cdecl[3]. Zu beachten ist dabei immer der Stack und der Anfang des StackFrames. Dieser liegt ja in dem BasePointer.
Nun wird in Zeile 0×400547 nochmals der Parameter nach EAX geladen. CLTQ wird zur Synchronisation genutzt. (Das stimmt ja so nicht. Wie ich nu gelesen hab wird es genutzt um eax in ein QuadWord zu konvertieren. Also nach rax!) Weiterhin wird nun der Parameter vorbereitet. Folgende Rechnung:
( ( 0×02 + 0×0F + 0×0F ) >> 0×04 ) << 0x04 = 0x20
Laut[4] werden Stellen die bei einem Shift frei werden mit 0 aufgefüllt. Dies passiert alles von 0×40054C bis 0×400558. Danach wird das Ergebnis mit dem aktuellen StackPointer verrechnet und den trifft dann das gleiche Schicksal. Also haben wir wieder mehr Speicher reserviert als wir brauchen. Nämlich haben alle einen gemeinsamen Teiler. Der ist 16.
Woher kommt das also. Ich bin bei der Suche dort auf einige interessante Sachen gestoßen. Meine erste Idee war es Fragmentierung zu vermeiden[5]. Jedoch habe ich diese Idee wieder verworfen. Denn es handelt sich hierbei um den Stack. Dieser wird nachdem die Funktion abgearbeitet wurde wieder frei geräumt. Weiterhin denke ich das Vorsorge zur Fragmentierung ein bisschen anders ausschaut. Da müsste ich ggf. mal in den Quellcode von malloc schauen. Dann finde ich da vielleicht auch was dazu.
Eine andere Idee hatte ich gefunden als ich mich mit den Anfängen der Speicherverwaltung beschäftigt habe. Dort bin ich dann auf die Speichersegmentierung der 80×86 Prozessoren gestoßen. Denn als es noch 16Bit Prozessoren gab wollte man doch mehr als 64KiB Speicher haben. Also hatte man eine Adressbreite von 20Bit. Die Speicheradresse wurde dann mit Segment und Offset berechnet. Das ist alles hier[6] ganz schön beschrieben. So lautet auch ein Absatz
Durch die Multiplikation mit 16 hat sich auch die kleinste, durch die Segmentadresse adressierbare Einheit verändert. Sie beträgt nun nicht mehr 1 Byte, sondern insgesamt 16 Byte. Diese 16 Byte werden in diesem Zusammenhang auch als “Paragraph” bezeichnet.
Damit war ich dann die erste Zeit zufrieden. Nach einiger Zeit habe ich mir dann so gedacht, nein das kann ja kein Relikt aus den alten Zeiten sein und machte mich von neuem auf die Suche.
Dann fand ich einen ersten Hinweis. Dabei handelt es sich um einen Schalter vom gcc namens „-mpreferred-stack-boundary=num“[7].
Gibt man diesen beim kompilieren mit an, so verändert sich der „Teiler“. Erst einmal zu der Dokumentation. Der Wert von preferred-stack-boundary muss zwischen 4 und 12 liegen. Berechnet wird dies dann 2num. Also mit dem std Wert 24 usw usf. Also wenn ich mir nun noch mal das erste Beispiel anschaue und dies nochmal mit der Option -mpreferred-stack-boundary übersetze und mit dieser Option spiele ergibt sich folgendes.
Preferred-stack-boundary SIZE (in Byte) Stack SIZE (in Byte)
4 2 16
5 2 48
6 2 112
12 2 8176
Also habe ich dort nun eine Möglichkeit dies zu bearbeiten. Weiterhin fand ich heraus wozu dies gut sein sollte. Denn dies steht ebenso in der Dokumentation unter „-mincoming-stack-boundary“. Einzig und allein für die Streaming SIMD Extentions ist dies von Vorteil. Denn diese haben eine Wortbreite von 128Bit → 16Byte. Wenn nun also SSE in dem Programm genutzt wird, kann einfacher und schneller auf den Stack zugegriffen werden. Es muss nicht darauf geachtet werden die Variablen erst zu „normalisieren“, sondern sie können direkt in den Speicher geladen und genutzt werden.
Leider habe ich nun noch nicht so viel Erfahrung im Bereich SSE. Jedoch gebe ich mich mit dieser Art der Antwort nun endlich zufrieden. Hier[8] hat man auch eine ganz gute Einführung in das Thema. Jedoch werde ich mir dies später mal anschauen.
Ich bin nun froh, das ich doch wieder einiges dazu gelernt habe. Weiterhin ist zu sagen dass ich dies nur auf den GCC hin untersucht habe. Wie sich das bei anderen Compilern verhält weiß ich nicht.
Quellen
- Function prologue
- Enter / Leave
- Aufrufkonventionen
- Intel Architecture Software Developer’s Manual Volume 2: Instruction Set Reference
S. 663 (SAL/SAR/SHL/SHR—Shift (Continued)) - Heap-Fragmentierung
- Logische Adressierung / Segmentierung
- Intel 386 and AMD x86-64 Options (-mpreferred-stack-boundary)
- HowTo: Inline Assembly & SSE: Vector normalization done fast!