new + alignment requirements

ness

Folgendes Problem: ich brauche eine Möglichkeit, speicher auf dem heap zu allozieren, der quadword (16 byte) aligned ist.
Die Frage ist nun, wie stell ich das im größen stil an? Ich kann ja 16 byte mehr allozieren und dann halt den zurückgelieferten pointer einfach bis zur nächsten quadword-grenze erhöhen, aber gehts auch einfacher? Und wie mach ich das mit dem freigeben, da muss ich ja die originale adresse kennen?

Naja, ich hab mir folgendes überlegt:
ich schreibe nen eigenes new (achne, wie einfallsreich ;btw, kann man dann "x = mein_namespace::new char[25]" oder so schreiben?). Da ich mir nicht soviel arbeit machen will, allozier ich 16 + sizeof(void*) bytes zusätzlich, und speichere den pointer vor dem zurückgegebenen wert, das sähe dann etwa so aus:

#include <new> 

void* operator new(size_t bytes)    //richtig?
{
    void* p = new char[bytes + sizeof(void*) + 16);
    void* r = (p + sizeof(void*) + 16) & ~0xF;
    (reinterpret_cast<char*>(r)[-sizeof(void*)] = (char*)r;    //nicht wirklich elegant :D
    return r;
}

void operator delete(void* p)    //richtig?
{
    delete (reinterpret_cast<char*>(r))[-sizeof(void*)];
}

Hat jemand ne bessere idee?

groovemaster

Im Prinzip ist deine Idee schon richtig. Du reservierst 16 Bytes mehr plus den Speicher für einen zusätzlichen Address- oder Offsetwert. Dieser steht dann direkt vor der zurückgegebenen Adresse (also der alignden) und gibt den eigentlichen Beginn des reservierten Speichers an.
Dieses Problem hatte ich vor einiger Zeit ebenfalls wegen SSE und habe es auf die gleiche Weise gelöst. Ich poste einfach mal meine geistigen Ergüsse, vielleicht helfen sie dir ja.

void* memory_allocate(std::size_t size, std::size_t alignment)
{
	std::size_t info_size = sizeof(std::ptrdiff_t) + sizeof(std::size_t);
	// alignment ist eine Zweierpotenzbasis
	std::size_t padding = (1 << alignment) - 1;
	std::size_t n = padding + info_size + size;
	void* p = std::malloc(n);
	if (p)
	{
		std::ptrdiff_t base_address = reinterpret_cast<std::ptrdiff_t>(p);
		std::ptrdiff_t address = base_address + info_size;
		address = (address + padding) & ~padding;
		p = reinterpret_cast<void*>(address);
		std::ptrdiff_t offset = address - base_address;
		address -= info_size;
		*reinterpret_cast<std::ptrdiff_t*>(address) = offset;
		address += sizeof(std::ptrdiff_t);
		*reinterpret_cast<std::size_t*>(address) = alignment;
	}
	return p;
}

void* memory_allocate(std::size_t size)
{
	return memory_allocate(size, 0);
}

void* memory_reallocate(std::size_t size, void* p)
{
	std::size_t info_size = sizeof(std::ptrdiff_t) + sizeof(std::size_t);
	std::ptrdiff_t address = reinterpret_cast<std::ptrdiff_t>(p);
	std::ptrdiff_t base_address = address - info_size;
	std::ptrdiff_t offset = *reinterpret_cast<std::ptrdiff_t*>(base_address);
	base_address += sizeof(std::ptrdiff_t);
	// alignment ist eine Zweierpotenzbasis
	std::size_t alignment = *reinterpret_cast<std::size_t*>(base_address);
	base_address = address - offset;
	p = reinterpret_cast<void*>(base_address);
	std::size_t padding = (1 << alignment) - 1;
	std::size_t n = padding + info_size + size;
	p = std::realloc(p, n);
	if (p)
	{
		base_address = reinterpret_cast<std::ptrdiff_t>(p);
		address = base_address + info_size;
		address = (address + padding) & ~padding;
		p = reinterpret_cast<void*>(address);
		offset = address - base_address;
		address -= info_size;
		*reinterpret_cast<std::ptrdiff_t*>(address) = offset;
		address += sizeof(std::ptrdiff_t);
		*reinterpret_cast<std::size_t*>(address) = alignment;
	}
	return p;
}

void* memory_reallocate(std::size_t size, void* p, std::size_t alignment)
{
	std::size_t info_size = sizeof(std::ptrdiff_t) + sizeof(std::size_t);
	std::ptrdiff_t address = reinterpret_cast<std::ptrdiff_t>(p);
	std::ptrdiff_t base_address = address - info_size;
	std::ptrdiff_t offset = *reinterpret_cast<std::ptrdiff_t*>(base_address);
	base_address = address - offset;
	p = reinterpret_cast<void*>(base_address);
	// alignment ist eine Zweierpotenzbasis
	std::size_t padding = (1 << alignment) - 1;
	std::size_t n = padding + info_size + size;
	p = std::realloc(p, n);
	if (p)
	{
		base_address = reinterpret_cast<std::ptrdiff_t>(p);
		address = base_address + info_size;
		address = (address + padding) & ~padding;
		p = reinterpret_cast<void*>(address);
		offset = address - base_address;
		address -= info_size;
		*reinterpret_cast<std::ptrdiff_t*>(address) = offset;
		address += sizeof(std::ptrdiff_t);
		*reinterpret_cast<std::size_t*>(address) = alignment;
	}
	return p;
}

void memory_deallocate(void* p)
{
	std::size_t info_size = sizeof(std::ptrdiff_t) + sizeof(std::size_t);
	std::ptrdiff_t address = reinterpret_cast<std::ptrdiff_t>(p);
	std::ptrdiff_t base_address = address - info_size;
	std::ptrdiff_t offset = *reinterpret_cast<std::ptrdiff_t*>(base_address);
	base_address = address - offset;
	p = reinterpret_cast<void*>(base_address);
	std::free(p);
}

Die Funktionen sind bis jetzt noch nicht 100%ig ausgetestet, scheinen aber bisher keine Probleme zu bereiten.
Zu beachten ist, dass ich vor dem alignden Bereich nicht nur den Offset speichere, um den eigentlichen Beginn wiederzufinden, sondern ebenfalls das Alignment selbst. Deshalb sieht es auch etwas komplizierter aus. Das mach ich deswegen, da ich das Alignment variabel halte und bei einem reallocate nicht nochmal extra angeben muss. Evtl. fliegt das aber auch wieder raus.
Diese Funktionen kann man dann natürllich auch problemlos in einer operator new/delete Funktion verwenden.

ness

wies aussieht kann ich unter bestimmten bedingungen auch posix_memalign nehmen. das gibt aber (wie malloc) unintialisierten speicher her. Wie initialisiere ich den dann korrekt?
/edit: ich seh grade, die frage ist unsinn. operator new gibt ja sowieso nur void* zurück

camper

ness schrieb:

#include <new> 

void* operator new(size_t bytes)    //richtig?
{
    void* p = new char[bytes + sizeof(void*) + 16);
    void* r = (p + sizeof(void*) + 16) & ~0xF;
    (reinterpret_cast<char*>(r)[-sizeof(void*)] = (char*)r;    //nicht wirklich elegant :D
    return r;
}

void operator delete(void* p)    //richtig?
{
    delete (reinterpret_cast<char*>(r))[-sizeof(void*)];
}

Hat jemand ne bessere idee?

fast, allerdings hat du hier eine endlos recursion - denn new char[..] ruft ja wieder deinen operator auf

so etwas hab ich vor einer weile schon mal gemacht:
http://www.c-plusplus.net/forum/viewtopic-var-t-is-94628.html
(hm, ergibt bei mir komischerweise jetzt eine weisse seite YMMV)

zwei kleine feinheiten zur optimierung:

um ein alignment von n zu erreichen genügt es n-1 bytes zusätzlich anzufordern...
je nachdem worauf dein allokator beruht, kannst du die eigenschaften des zugrundeliegenden allokators ausnutzen:
- malloc liefert generell speicher der hinreichend ausgerichtet ist für alle builtin typen (also auf dem pc 8 byte)
- gleiches gilt für die standard versionen von new char[] und new unsigned char[] (und damit doch wohl für alle standard-news, denn es gibt nur einen globalen operator - den teil des standards hab ich noch nicht begriffen); das wäre relevant, falls du new nur per klasse überladen willst

ness

Ich hab mal versucht, das umzusetzen. Der algo scheint zu stimmen, aber in free_aligned scheint nicht mein sondern der globale operator delete aufgerufen zu werden (sprich es wird nicht "TEST2" ausgegeben), warum?

#include <iostream>

namespace mer
{	
	namespace help
	{
		void* alloc_backend(std::size_t size, std::size_t align)
		{
			char* p = reinterpret_cast<char*>(std::malloc(size + align + sizeof(std::ptrdiff_t)));
			char* r = reinterpret_cast<char*>(reinterpret_cast<std::size_t>(p + align + sizeof(std::ptrdiff_t)) & ~(align - 1));
			*reinterpret_cast<ptrdiff_t*>(r - sizeof(std::ptrdiff_t)) = r - p;
			return r;
		}

		void free_backend(void* p)
		{
			std::free(reinterpret_cast<char*>(p) - *reinterpret_cast<ptrdiff_t*>(reinterpret_cast<char*>(p) - sizeof(std::ptrdiff_t)));
		}

		//just to make the compiler initialize/deinitialize stuff
		void* operator new(std::size_t size, std::size_t align)
		{
			std::cout<<"TEST1"<<std::endl;
			return alloc_backend(size, align);
		}

		void operator delete(void* p)
		{
			std::cout<<"TEST2"<<std::endl;
			return free_backend(p);
		}

		void* operator new[](std::size_t size, std::size_t align)
		{
			return alloc_backend(size, align);
		}

		void operator delete[](void* p)
		{
			return free_backend(p);
		}
	}

	template<class T>
	T* allocate_aligned(std::size_t align)
	{
		using namespace help;
		return new(align) T;
	}

	template<class T>
	void free_aligned(T* p)
	{
		using namespace help;
		delete p;
		//help::free_backend(p);
	}
}

int main()
{
	char* t = mer::allocate_aligned<char>(16);
	mer::free_aligned(t);

	return 0;
}

ZuK

Denke du willst sowas

template<class T>
    void free_aligned(T* p)
    {
        using namespace help;
        operator delete( p );
    }

camper

3.7.3.1/1

An allocation function shall be a class member function or a global function; a program is ill-formed if an allocation function is declared in a namespace scope other than the global scope or declared static in global scope.

ness

das ist natürlich unschön, ich dachte ich kann den compiler das machen lassen...
hab das jetzt so umgeformt:

#include <iostream>

namespace mer
{	
	template<class T>
	struct help
	{
		T t;

		static void* alloc_backend(std::size_t size, std::size_t align)
		{
			char* p = reinterpret_cast<char*>(std::malloc(size + align + sizeof(std::ptrdiff_t)));
			char* r = reinterpret_cast<char*>(reinterpret_cast<std::size_t>(p + align + sizeof(std::ptrdiff_t)) & ~(align - 1));
			*reinterpret_cast<ptrdiff_t*>(r - sizeof(std::ptrdiff_t)) = r - p;
			return r;
		}

		static void free_backend(void* p)
		{
			std::free(reinterpret_cast<char*>(p) - *reinterpret_cast<ptrdiff_t*>(reinterpret_cast<char*>(p) - sizeof(std::ptrdiff_t)));
		}

		//just to make the compiler initialize/deinitialize stuff
		void* operator new(std::size_t size, std::size_t align)
		{
			return alloc_backend(size, align);
		}

		void operator delete(void* p)
		{
			return free_backend(p);
		}

		void* operator new[](std::size_t size, std::size_t align)
		{
			return alloc_backend(size, align);
		}

		void operator delete[](void* p)
		{
			return free_backend(p);
		}
	};

	template<class T>
	T* allocate_aligned(std::size_t align)
	{
		return &((new(align) help<T>)->t);
	}

	template<class T>
	void free_aligned(T* p)
	{
		delete reinterpret_cast<help<T>*>(p);
		//help::free_backend(p);
	}
}

int main()
{
	char* t = mer::allocate_aligned<char>(16);
	mer::free_aligned(t);

	return 0;
}

Allerdings ist free_aligned immernoch unsauber.

camper

sehe den fehler jetzt auch nicht auf anhieb (dass das ganze nicht portable ist, ist dir ja klar) - ein paar sachen kann man allerdings noch etwas einfacher schreiben, und dann wird es möglicherweise klarer:

std::free(reinterpret_cast<char*>(p) - *reinterpret_cast<ptrdiff_t*>(reinterpret_cast<char*>(p) - sizeof(std::ptrdiff_t)));

is äquivalent zu

std::free(reinterpret_cast<char*>(p) - reinterpret_cast<ptrdiff_t*>(p)[-1]);

analog das ganze in alloc - ein reinterpret_cast pro zeile sollte ja nun genügen, um die aufmerksamkeit oder grep darauf zu richten

allerdings gilt logischerweise stets: sizeof(ptrdiff_t)>=sizeof(size_t)
und dein cast in alloc setzt ja bereits voraus, dass beim reinterpret_cast nach size_t keine informationen verloren gehen. du sparst also nichts gegenüber der variante, gleich unmittelbar einen zeiger an dieser stelle zu speichern - aber der code wird einfacher. etwas anderes wäre es, wenn du align in der grösse beschränkst, denn die verschiebung kann ja nie grösser als align+sizeof(T) (mit T der datentyp, den du zum speichern der verschiebung nimmst) sein - mit align < 256 würde z.b. char völlig ausreichen. da malloc allerdings immer für builtin typen hinreichend ausgerichteten speicher liefert, bringt das nicht wirklich einen gewinn.

ness

nein nein, das ganze funktioniert wie gewollt, aber "delete reinterpret_cast<help<T>*>(p);" ist natürlich ser wenig portabel (der rest sollte es doch sein, oder?)
/edit: und das verpacken in ner struktur gefällt mir auch nicht, der compiler könnte ja padden

camper

ness schrieb:

nein nein, das ganze funktioniert wie gewollt, aber "delete reinterpret_cast<help<T>*>(p);" ist natürlich ser wenig portabel (der rest sollte es doch sein, oder?)
/edit: und das verpacken in ner struktur gefällt mir auch nicht, der compiler könnte ja padden

wenn T ein POD ist, garantiert dir der standard sogar, dass das funktioniert. und wenn T kein POD ist, kannst du ohnehin nur beten (allerdings bin ich mir ziemlich sicher, dass padding niemals löcher am anfang einer struktur verursacht) - etwas anderes wäre, wenn du deine klasse so gestaltest, dass potentielle klienten davon öffentlich erben sollen... (dann entfällt logischerweise T und die template-funktionen, align müsste dann eine konstante sein). Eleganter fände ich es, diese funktionalität in einen allokator zu packen - damit machst du sie für mehr Ts zugänglich, und die integration mit containern ist auch kein problem (bloss dumm, das container mit verschied. allokatoren inkompatibel sind )

unportabel ist an dem gesamten projekt grundsätzlich das ziel, nähmlich eine bestimmte ausrichtung für objekte zu erreichen. das macht sich in unportablen konstrukten bemerkbar:
- reinterpret_cast von void* nach char* - muss nichts sinnvolles ergeben (denn die interne representation verschiedener pointer kann sich durchaus unterscheiden), besser ist static_cast

- cast von pointer auf integer - das ist zwar erlaubt, aber niemand garantiert, dass size_t gross genug ist (etwas portabler ist intptr_t aus C99)
- mit dem integer zu rechnen und das ganze in einen pointer zurückzuverwandeln ist gänzlich unportabel, hier musst du die repräsentation von pointern kennen, das ist unterschiedlich von plattform zu plattform

alles nat. kein problem, wenn alles auf einem rechner, den du auf deinen tisch stellen kannst, laufen soll...

ein fehler ist es im übrigen, align + sizeof(std::ptrdiff_t) zu addieren statt
align + sizeof(std::ptrdiff_t) - 1
bedenke was passiert, wenn align 1 ist... nicht alle plattformen erlauben unausgerichtete zugriffe auf integer