Wie funktioniert Speichermanagment intern (malloc/realloc/free/..)

1. Wenn ich mit malloc speicher allokiere, muss ja irgend wein speichermangment prozedure im Hintergrund nach freien lücke suchen, und die start adresse des bereichs zurückgeben oder?

2. Woher weis Free wieviel speicher für den Pointer X allokiert wurde? NULL Stellen am Ende oder?

nehmen wir an ich amche sowas:

char *p= malloc(10);

mache p[10]='#';

free(p);

gibt er dann den allokieren speicher + den speicher danach bis NULL kommt frei? wie funktionier das intern ?

Shade Of Mine

malloc merkt sich wieviel es allokiert hat und sagt free das.
keine magie dabei.

stell dir es zB so vor, dass malloc dir einen speicherblock liefert und auf dem index -1 die größe reinschreibt.

wie es genau aussieht hängt von der implementierung dann ab, aber im prinzip passiert es immer so ähnlich.

http://ocw.kfupm.edu.sa/user\ICS2020102\slides/Lecture40.ppt

d.h. malloc merkt sich intern in nem lookup table zur speicher(start)adresse die größe? und free sucht dann nach der adresse im table und kenn dann so die größe?

durch das zusammenstücken der fragmente zur gewünschen größe muss ja ziemlich zeit drauf gehen oder? dann könnte ja vorkommen das bspw. ein integer aufm heap auf mehre fragmente verteil ist oder? Wenn ich mich recht erinnere hab ich mal was von speicher defragmentierung gelesen, so das der speicher parallel defragmentiert wird oder? und so die allokation schneller statt findet?

Oh man sowas ist echt mal interessant, frag mich wieso sich manche leute für sowas nich begeistern können... hehe

danke schonmal

David_pb

MemoryManager schrieb:

d.h. malloc merkt sich intern in nem lookup table zur speicher(start)adresse die größe? und free sucht dann nach der adresse im table und kenn dann so die größe?

Könnte so implementiert sein, muss aber nicht. Wie das im Endeffekt gelöst wird hängt vom jeweiligen Memorymanager ab. Oft wird die Größe, wie bereits gesagt, an den Index -1 geschrieben.

Ein sinnfreies Beispiel:

void* MyMalloc( size_t size )
{
	int* buffer = ( int* )malloc( size + sizeof( int ) );
	*buffer = size;
	return buffer+1;
}

void MyFree( void* ptr )
{
	int* buffer = ( ( int* )ptr )-1;
	printf( "freeing %d bytes\n", *buffer );
	free( buffer );
}

void main()
{
	char* p = ( char* )MyMalloc( 11 );
	strcpy( p, "Hallo Welt" );
	printf( "%s\n", p );
	MyFree( p );
}

MemoryManager schrieb:

durch das zusammenstücken der fragmente zur gewünschen größe muss ja ziemlich zeit drauf gehen oder? dann könnte ja vorkommen das bspw. ein integer aufm heap auf mehre fragmente verteil ist oder? Wenn ich mich recht erinnere hab ich mal was von speicher defragmentierung gelesen, so das der speicher parallel defragmentiert wird oder? und so die allokation schneller statt findet?

Ziel eines jeden Memorymanager ist es eigentlich Speicher möglichst schnell bereit zu stellen. Also werden entsprechende Lösungsansätze verwendet.
Kommt ein schlechter Algorithmus zum einsatz und das Bereitstellen von Speicher dauert ewig, was nicht sein darf, ist der Manager einfach schlecht.

ok danke, da fällt mir noch ne Frage ein:

Sagen wir ich allokiere 100Bytes. Und malloc teilt diese in 5 fragemente auf.

=> 32 Bytes, 16 Bytes, 48 Bytes, 4 Bytes

und ich iteriere die 100 bytes mit Pointer arithmetik.

char* p= malloc(100);
for(unsigned int i=0; i< 100;++i)
   p[i]=(char)i;
free(p);

dann muss ja von i=31 auf i= 32 das fragment gewechselt werden oder? geht das nich nich lang???

Ich glaub man kann speicher sogar so allokieren das der speicher wirklich in einem fragment liegt oder?

P.S.: Ist alles nur aus interesse , es geht nich darum das ich performacne Probleme habe^^

David_pb

Klar, wenn dein physikalischer Speicher stark fragmentiert ist macht sich das bemerkbar. Daher ist es auch Ziel den Speicher möglichst nicht zu fragmentieren und möglichst zusammenhängenden Speicher bereitzustellen.

MemoryManager schrieb:

dann muss ja von i=31 auf i= 32 das fragment gewechselt werden oder?

nö, du kriegst den speicher immer in einem stück. wenn 'malloc' keinen freien block mehr hat, der mindestens deiner geforderten grösse entspricht (und auch aus bisher freigegebenen blöcken keinen zusammenbauen konnte), dann bekommste 0 zurück, also anfrage abgelehnt.
btw: schau dir diesen thread an: http://www.c-plusplus.net/forum/viewtopic-var-t-is-195001-and-postdays-is-0-and-postorder-is-asc-and-start-is-0.html

H´mm.. dann war eine link vorher für andere seichermanagment?

^^der link vorher erklärt etwas die theorie von so'nem 'mallocator'

pointercrash**

MemoryManager schrieb:

H´mm.. dann war eine link vorher für andere seichermanagment?

Guckst Du hier: http://www.ibm.com/developerworks/linux/library/l-memory/
Iss gar nicht schlecht beschrieben, trotz IBM
Wie im Einzelnen die stdlib implementiert ist, obliegt dem Compilerbauer, aber man kann sowas schlechter oder besser machen

Und auf den Index 10 würde ich nicht zugreifen, weil Dein malloc nur Platz für 10 Elemente liefert, also Index 0 .. 9