freea - Gegenstück zu alloca

dachschaden

Ich versuche mich derzeit an einer C-Funktion, die Speicher, der mit alloca "reserviert" wurde, wieder freizugeben. Der Code muss nur für x86 und x86-64 funktionieren, und auch erst einmal nur für GCC unter Linux. Für den Zugriff auf die Register verwende ich inline assembly.

Warum man so etwas benötigen sollte? Weil ich eine Aufrufsstruktur von geinlinten Funktionen habe, die unter Umständen den Stack platzen lassen kann, wenn alle alloca -Variablen bis zum nächsten zurücksetzen des Stacks draufbleiben.

Ich sollte dazu sagen, dass ich noch nicht wirklich standhaft in inline assembly bin. Korrekturen und Anmerkungen sind willkommen.

Ja, ich weiß, dass ein solches freea nur dann funktioniert, wenn ich die letzten alloca -Pointer in ungekehrter Reihenfolge freigebe (oder indem ich alles en-block freigebe, aber das sind Details). Oder?

Allerdings habe ich dabei direkt ein kleines Problem. Als Beispiel soll folgender Code dienen:

#include <stdint.h>
#include <string.h>
#include <alloca.h>

inline __attribute__((always_inline)) void sp_free
(
	size_t bytes
)
{
	if(sizeof(uintptr_t) == 8)
		__asm__ __volatile__("add %0,%%rsp"::"m"(bytes):"rsp");
	else if(sizeof(uintptr_t) == 4)
		__asm__ __volatile__("add %0,%%esp"::"m"(bytes):"esp");
	else
		__asm__ __volatile__("add %0,%%sp"::"m"(bytes):"sp");
}

int main(void)
{
	char*x = alloca(50);
	/*memcpy(x,"bla",sizeof("bla"));*/
	sp_free(50);
	return 0;
}

Der Code funktioniert (sprich, die Subtraktionen und Additionen auf %rsp sind im kompiliertem Code vorhanden) mit -O0, unabhangig davon, ob, der Aufruf von memcpy drin ist oder nicht.

Der Code funktioniert nicht mehr unter -O1 oder höher, wenn der Aufruf auf memcpy entfernt wird. In diesem Fall kann der Compiler keine Referenz mehr auf x finden und löscht die Variabel gleich lieber komplett - zusammen mit dem alloca -Aufruf. Wenn main dann zurückkehrt, stimmt natürlich auf dem Stack gar nichts mehr, und die glibc bricht das Programm ab.

Die einzige Lösung, auf die ich gekommen bin, ist mein eigenes alloca (im Folgenden sp_alloc genannt) mitzuliefern, welches volatile deklariert wird. Auf diese Weise bleibt die Reservierung des Speichers auf dem Stack, egal, welches O-Level ich angebe, und das Programm stürzt nicht ab.

#include <stdint.h>
#include <string.h>
#include <alloca.h>

inline __attribute__((always_inline)) uintptr_t sp_read(void)
{
	register uintptr_t sp;

	if(sizeof(uintptr_t) == 8)
		__asm__ __volatile__("mov %%rsp,%0":"=a"(sp));
	else if(sizeof(uintptr_t) == 4)
		__asm__ __volatile__("mov %%esp,%0":"=a"(sp));
	else
		__asm__ __volatile__("mov %%sp,%0":"=a"(sp));;

	return sp;
}

inline __attribute__((always_inline)) void*sp_alloc
(
	size_t bytes
)
{
	register void*pointer;

	if(sizeof(uintptr_t) == 8)
		__asm__ __volatile__("sub %0,%%rsp"::"m"(bytes):"rsp");
	else if(sizeof(uintptr_t) == 4)
		__asm__ __volatile__("sub %0,%%esp"::"m"(bytes):"esp");
	else
		__asm__ __volatile__("sub %0,%%sp"::"m"(bytes):"sp");

	pointer = (void*)sp_read();

	return pointer;
}

inline __attribute__((always_inline)) void sp_free
(
	size_t bytes
)
{
	if(sizeof(uintptr_t) == 8)
		__asm__ __volatile__("add %0,%%rsp"::"m"(bytes):"rsp");
	else if(sizeof(uintptr_t) == 4)
		__asm__ __volatile__("add %0,%%esp"::"m"(bytes):"esp");
	else
		__asm__ __volatile__("add %0,%%sp"::"m"(bytes):"sp");
}

int main(void)
{
	char*x = sp_alloc(50);
	/*memcpy(x,"bla",sizeof("bla"));*/

	sp_free(50);
	return 0;
}

Weil ich die Gelegenheit auch direkt Nutzen will, Frieden mit dem Inline-Assembler zu schließen, sind die Fragen:

1. Ist die Idee überhaupt gut?
2. Gibt es Sachen, die ihr besser machen würdet? *

*Aligning auf 16-Byte könnte man machen, aber dann haben wir später wieder eventuell blöde Reste auf dem Stack, die erst mit dem nächsten Stack-Abbau entfernt werden.

EDIT: Originalimplementierung hatte erst mal einen dicken Fehler drin - super! sp_read sollte nach, nicht vor dem Ändern des Stackpointers aufgerufen werden.

SeppJ

Wenn du alloca-Speicher manuell freigeben möchtest, warum dann überhaupt alloca verwenden? Der ganze Witz an alloca ist dann doch dahin und man wäre besser mit einem normalen malloc bedient.

dachschaden

SeppJ schrieb:

Wenn du alloca-Speicher manuell freigeben möchtest, warum dann überhaupt alloca verwenden?

Geschwindigkeit? Speicher mit alloca zu reservieren ist das Ändern eines Registers. Das Freigeben das Ändern des gleichen Registers. *

malloc ist das Suchen nach Speicherplatz in einer internen Liste, das Hinzufügen eines Eintrags in der Liste, und, wenn es blöd läuft, ein Syscall, um den Standardheap zu vergrößern/neuen Speicher zu reservieren (passiert bei mir aber eigentlich kaum). Zudem kommt ein bisschen Speicher zur Verwaltung der internen Liste weg, das ist auch nicht optimal. Das Freigeben ist das Suchen eines Zeigers in der Liste und das Neuverketten dieser. Und wenn wir Pech haben, laufen wir in einer Multi-Threading-Umgebung, in der die Threads miteinander um Speicherplatz racen. **

Allein das Verhalten von alloca niederzuschreiben ist weniger aufwendig als das Verhalten von malloc . Ich habe hier Code laufen, da ist das Reservieren von Speicher und das anschließende Freigeben der größte Flaschenhals - für etwas, welches ich oft nur benötige, um z.B. bei nicht-nullterminierten Strings ein zusätzliches NUL-Byte einzufügen. Das Kopieren geht schnell, der Funktionsaufruf geht schnell, aber die Speicherreservierung ist einfach lahm.

Ein Algorithmus hier (bei dem der Compiler nichts optimieren kann, weil die Speicherverwaltung über Lib-Funktionen geht) kostet mit meiner alloca -Version ~70 Cycles pro Iteration. Mit malloc sind wir bei über ~220 Cycles. Das sind über 300%. Und das war noch eine Single-Threaded-Anwendung, wo das System automatisch keine Locks implementiert (sprich, nicht alles noch langsamer macht).

Von daher ist diese Aussage:

SeppJ schrieb:

Der ganze Witz an alloca ist dann doch dahin und man wäre besser mit einem normalen malloc bedient.

einfach nur Quatsch.

* Und wenn die anzufallenden Bereiche unter 128 Bytes liegen auf einem x64-Prozess, darf ich mir laut ABI selbst das Ändern des Registers noch sparen. Wegen Red Zone und so. Damit wäre die Speicherverwaltung dann komplett kostenlos.
** Das Problem habe wir bei Speicher auf dem Stack nicht. Hier hat jeder Thread seinen eigenen Frame. Es gibt nichts, was um den Zugriff auf das Register racen könnte, weil wir gerade eh ausgeführt werden.

meine Anmerkungen
-es könnte es passieren das dein volatile Optimierungen sehr stark unterbindet
-spielen mit sp,eps oder rsp ist eine ziemlich heisse Kiste oder?

ich würde mich mal auf die Suche machen warum es alloca aber kein freea gibt haben doch bestimmt schon viel mehr Leute bemängelt

(http://stackoverflow.com/questions/283024/freeing-alloca-allocated-memory)

oder was war der Grund warum dyn_array es wieder nicht in den C++ Standard geschafft hat

usw.

technisch geht es schon, und hat sicher auch in bestimmten Bereichen massive Performanzvorteile - aber solange es keinen direkten Support vom Kompiler gibt wäre ich da vorsichtig

mach doch ein github Projekt drauss jags durch https://news.ycombinator.com/news, reddit und Stackoverflow - da bekommst du bestimmt ein Haufen Input, DOs and DONT's - wäre bestimmt interessant

dachschaden

Gast3 schrieb:

-es könnte es passieren das dein volatile Optimierungen sehr stark unterbindet

Stimmt. Aber wie kann ich mir sonst sicher sein, dass - oder ob - Speicher auf dem Stack reserviert wurde? Eine Möglichkeit wäre, vor und nach alloca rsp zu laden und dann die Differenz noch mal manuell abzuziehen. Nachteil: benötigt wieder zusätzliche Variablen auf dem Stack - jede Funktion, die dann mal schnell Speicher benötigt, vernichtet erst mal ein bisschen der Red Zone, die ich schon gerne (zumindest auf Linux) nutzen möchte.

Gast3 schrieb:

-spielen mit sp,eps oder rsp ist eine ziemlich heisse Kiste oder?

Sag an. Deswegen frage ich ja nach.

Gast3 schrieb:

ich würde mich mal auf die Suche machen warum es alloca aber kein freea gibt haben doch bestimmt schon viel mehr Leute bemängelt

(http://stackoverflow.com/questions/283024/freeing-alloca-allocated-memory)

freea ist in der Hinsicht eigentlich ein falscher Name.
malloc reserviert Speicher und gibt uns die Adresse auf den reservierten Speicherbereich zurück. free übernimmt den Zeiger und gibt den Speicherbereich wieder frei.
Einem freea würden wir keinen Zeiger übergeben, weil das wieder eine Liste impliziert, in der nach dem Zeiger gesucht werden muss. Diese Liste haben wir nicht, und ich werde den Teufel tun und da wieder malloc -artige Komplexität reinzubringen versuchen. Das hat den Nachteil, dass wir mit Längen arbeiten müssen und in umgekehrter Reihenfolge den Stack wieder abbauen. Für die Funktionen, in denen dies gebraucht wird, bin ich auch bereit, dies so zu implementieren. Der Compiler würde nichts anderes machen, nur muss er nicht wie die Bescheuerten Bytes zählen.

(Eigentlich ist es für mich nicht nachvollziehbar, warum es diese Art von freea nicht gibt. Der Compiler sieht doch die Aufrufe von alloca . Notfalls könnte er auch für inline-Funktionen rsp zwischenspeichern und, wenn der Aufruf von freea erfolgt, rsp wiederherstellen. Dann muss er nicht mal zur Kompilierzeit wissen, wie viele Bytes reserviert wurden. Nur die explizite Aufforderung "Hey, mach mal hier den Stack wieder klein", und dann könnte er bspw. nach jedem Schleifendurchlauf rsp wiederherstellen.)

Hey - DAS wäre die Idee! Wir speichern uns explizit rsp und stellen ihn zum Freigeben des Speichers explizit wieder her. Die Idee gefällt mir!

Gast3 schrieb:

technisch geht es schon, und hat sicher auch in bestimmten Bereichen massive Performanzvorteile - aber solange es keinen direkten Support vom Kompiler gibt wäre ich da vorsichtig

Genau das bin ich. Deswegen stürme ich auch nicht los und baue meine Idee überall ein, sondern ich warte erst einmal, ob mir nicht noch was besseres einfällt,

Gast3 schrieb:

mach doch ein github Projekt drauss jags durch https://news.ycombinator.com/news, reddit und Stackoverflow - da bekommst du bestimmt ein Haufen Input, DOs and DONT's - wäre bestimmt interessant

Github mag mich nicht. Ich fluche denen in meinem Quellcode zu häufig. Und ich glaube auch ehrlich gesagt nicht, dass die Idee "hip" genug ist, um außerhalb eines deutschsprachigen Forums Aufmerksamkeit zu erhalten.

Aber die Idee mit dem rsp sichern ... die hat was.

dachschaden

Ach, Mann, dieses Inline-Assembly ist doch der letzte Hühnerdreck.

#include <stdint.h>
#include <stddef.h>

#define MY_INLINE inline __attribute__((always_inline))

MY_INLINE uintptr_t sp_read(void)
{
	uintptr_t sp;
	__asm__ __volatile__("mov %%rsp,%0":"=r"(sp));
	return sp;
}

MY_INLINE void sp_write
(
	uintptr_t sp
)
{
	__asm__ __volatile__("mov %0,%%rsp"::"r"(sp):"rsp");
}

MY_INLINE void*sp_alloc
(
	size_t bytes
)
{
	void*pointer;

	/*********************************************************************
	**Wir setzen hier rsp clobbered - der Compiler sollte wissen, danach
	**nicht mehr ueber rsp auf Variablen zuzugreifen.
	*********************************************************************/
	__asm__ __volatile__("sub %0,%%rsp"::"r"(bytes):"rsp");
	pointer = (void*)sp_read();

	return pointer;
}

/*Welches Register gemappt wird, ist egal, es muss nur angegeben werden ...*/
/*#define SHOULD_WORK*/
#if defined(SHOULD_WORK)
#	define ALLOCA_SUPPORT volatile register uintptr_t _sp asm("r15")
#else
#	define ALLOCA_SUPPORT volatile register uintptr_t _sp
#endif

#define ALLOCA_MARK \
	do \
	{ \
		_sp = sp_read(); \
	} \
	while(0)

#define ALLOCA_FREE \
	do \
	{ \
		sp_write(_sp); \
	} \
	while(0)

void func(void)
{
	ALLOCA_SUPPORT;

	char*x;
	int i;

	ALLOCA_MARK;

	for(i = 0;i < 0x10000;i++)
	{
		x = sp_alloc(0x200);

		ALLOCA_FREE;
	}
}

int main(void)
{
	func();
	return 0;
}

SHOULD_WORK ist nur von Relevanz, wenn -On angegeben wurde und n > 0.

gcc x86.c -o x86 -O0 : Funktioniert ohne Probleme.

gcc x86.c -o x86 -O1 : Funktioniert nur mit SHOULD_WORK , ohne gibt's einen Speicherzugriffsfehler.

ASM-Code der nicht- SHOULD_WORK -Variante von func :

mov	%rsp,%rax			;Speichern des Stack Pointers in rax ...
mov	%rax,-0x8(%rsp)		;... um ihn auf den Stack zu legen.
mov	$0x10000,%eax		;Anzahl der Iterationen
mov	$0x200,%ecx			;Anzahl der Bytes pro Iteration
sub	%rcx,%rsp			;WICHTIG: %rsp wurde geändert, UND DER COMPILER WEISS DAVON
mov	%rsp,%rdx			;Unsere Pointer-Variable, x im C-Code, liegt in %rdx
mov	-0x8(%rsp),%rdx		;FEHLER: -0x8(%rsp) ist nicht mehr die Adresse, in der der alte %rsp liegt.
mov	%rdx,%rsp			;Sondern ein undefinierter Wert, mit dem wir uns den Stack zerhauen.
sub	$0x1,%eax
jne	400527 <func+0x12>	;Schleife
repz retq

ASM-Code der SHOULD_WORK -Variante von func :

push %r15
mov	%rsp,%r15		;Stack Pointer wird direkt in Register gespeichert.
mov	$0x10000,%eax
mov	$0x200,%edx
sub	%rdx,%rsp
mov	%rsp,%rcx
mov	%r15,%rsp		;Kein Zugriff mehr über %rsp, der Wert stimmt, der Stack wird wiederhergestellt.
sub	$0x1,%eax
jne	400524 <func+0xf>
pop	%r15			;Da am Ende der Stack wieder stimmt, können wir %r15 wiederherstellen.
retq

Programmierer sagen oft leichtfertig, dass Compiler-Bugs vorliegen ... aber an dieser Stelle wird mich der Verdacht nicht los, dass dem tatsächlich so ist. rsp wurde hier deutlich als clobbered angegeben, und dennoch macht der GCC sich nicht die Mühe, die Zugriffe über rsp wegzumachen. Schmackhaft finde ich auch, dass, obwohl _sp als volatile register angegeben wurde, der Compiler das dennoch weggemacht hat. Erst explizit mit dem Register-Mapping hat das funktioniert.

Ich habe das mit SHOULD_WORK so hinbekommen, dass zumindest der Zugriff über diesen Wert über ein Register läuft, das kann der GCC nicht kaputtmachen. Aber das ist für den Zugriff auf Stack-Variablen in komplexerem Code natürlich überhaupt keine Lösung, die können wir nicht alle in ein Register packen.
Langsam habe ich aber das Gefühl, der Thread sollte eher ins Assembler-Subforum verschoben werden.

EDIT:

Ich habe mal testweise:

x = alloca(0x200);
memcpy(x,"asdasd",sizeof("asdasd")); /*Damit's nicht wegoptimiert wird.*/

Eingefügt. Damit scheint's zu funktionieren:

push   %rbp
mov    %rsp,%rbp
sub    $0x10,%rsp
mov    %fs:0x28,%rax			;Konnte ein Canary sein, ob eventuell über den Stack geschrieben wurde?
mov    %rax,-0x8(%rbp)
xor    %eax,%eax
mov    %rsp,%rax
mov    %rax,-0x10(%rbp)			;Wert wird diesmal über rbp gespeichert und auch wieder geladen.
mov    $0x10000,%edx
mov    %rsp,%rcx
sub    $0x210,%rcx
mov    %rcx,%rsp
lea    0xf(%rsp),%rax			;... was er hier macht, ist mir auch nicht ganz klar.
and    $0xfffffffffffffff0,%rax	;Zugriff alignen
movl   $0x61647361,(%rax)		;"asda" schreiben
movw   $0x6473,0x4(%rax)		;"sd" schreiben
movb   $0x0,0x6(%rax)
mov    -0x10(%rbp),%rax			;Wert wird diesmal über rbp gespeichert und auch wieder geladen.
mov    %rax,%rsp				;Und hier wird der Stack zurückgesetzt.
sub    $0x1,%edx
jne    4005b2 <func+0x2d>
mov    -0x8(%rbp),%rax			;Und hier prüfen wir, ob der Canary noch lebt.
xor    %fs:0x28,%rax
je     4005ee <func+0x69>
callq  400450 <__stack_chk_fail@plt>
leaveq 
retq

Bin mir aber nicht sicher, ob ich damit alle Fälle abgedeckt habe. -On führt zumindest nicht mehr zu Laufzeitfehlern - keine derzeit sichtbaren zumindest.

ich würde den Code zumindest auf der gcc Mailingliste zur Diskussion stellen - da bekommst du besseres/fundierteres Feedback als hier

und was sagen die GCC-ler?