malloc implementieren

Hi,
ich versuche malloc selber zu nach zu implementieren. bitte um feedback zum code! habe noch keine memory alignment und fragmentation bedacht...

#include <stdio.h>
#include <stdbool.h>

#define HEAP_MEM_SIZE 1000

typedef struct header {
	void *memory;
	unsigned int size;
	bool is_available;
	struct header *next;
}header;

char buffer[HEAP_MEM_SIZE];
header head;
int heap_size = HEAP_MEM_SIZE;

void init() {
	head.memory = buffer;
	head.next = NULL;
	head.is_available = true;
	head.size = HEAP_MEM_SIZE;
}

void *my_malloc(int bytes) {
	static bool is_init = false;

	if(!is_init) {
		init();
		is_init = true;
	}

	header *curr = &head;

	int curr_size = bytes + sizeof(header);

	while(curr) {
		if(curr->is_available && 
		   curr->size >= curr_size) {

		   	printf("found\n");

			heap_size -= curr_size;
			curr->size = curr_size;
			curr->is_available = false; 
			curr->next = (header*)curr + curr_size;
			curr->memory = curr + sizeof(header);

			header *next_ptr = curr->next;
			next_ptr->size = heap_size;
			next_ptr->is_available = true;
			next_ptr->next = NULL;
			next_ptr->memory = NULL;

			return curr->memory;
		}
		else {
			curr = curr->next;
		}
	}

	return NULL;
}

void my_free(void *firstbyte) {
	header *memory_ptr = (header*)firstbyte;

	header *prev = &head;
	header *curr = &head;

	while (curr) {
		if (curr->memory == memory_ptr) {
			heap_size += curr->size;

			if (curr == &head) {
				curr->next = NULL;
				curr->size = heap_size;
			}
			else {
				prev->next = curr->next;
			}

			curr->memory = NULL;

			// Mark the block as being available
			curr->is_available = true;
			break;
		}

		prev = curr;
		curr = curr->next;
	}

	firstbyte = NULL;
	return;
}

int main(void) {
	// your code goes here

	void *curr1 = my_malloc(12);
	printf("heap_size: %d\n", heap_size);
	void *curr2 = my_malloc(12);
	printf("heap_size: %d\n", heap_size);
	//my_free(curr2);
	printf("heap_size: %d\n", heap_size);
	//my_free(curr1);
	printf("heap_size: %d\n", heap_size);

	return 0;
}

ArneMax

Ich bin leider noch nicht ganz wach aber ich meine einen groessseren Fehler in deiner my_malloc Funktion zu sehen. So wie ich das jetzt (ohne Kaffee) sehe verursacht dein Reallokieren einen Fehler.

Teste mal bitte folgendes:

int main(void) {
    void *mem1= my_malloc(20);
    memset (mem1,'x',19);
    mem1[19] = '\0';
    void *mem2= my_malloc(20);
    memset (mem2,'y',19);
    mem2[19] = '\0';
    void *mem3= my_malloc(20);
    memset (mem3,'z',19);
    mem3[19] = '\0';

    printf("Sollten 19 x sein: %s\n", mem1);
    printf("Sollten 19 y sein: %s\n", mem2);
    printf("Sollten 19 z sein: %s\n", mem3);

    my_free(mem2);

    void *mem4= my_malloc(10);
    mem4[9] = '\0';
    void *mem5= my_malloc(20);

    printf("Sollten 9 y sein: %s\n", mem4);
    printf("Sollten 9 y sein: %s\n", mem5);

    memset (mem5,'a',19);
    mem5[19] = '\0';

    // Wenn meine Theorie stimmt, dann wird dieses Ergebnis nicht mehr passen...
    printf("Sollten 19 z sein: %s\n", mem3);

    return 0;
}

Grundsaetzlich eine nette Idee. Ich meine aber (wie schon gesagt) einen Fehler in der Implementierung zu sehen. Das bringt mich aber zu einer wesentlichen Schwachstelle in deinem System. Du hast den Verwaltungs- und den Anwenderspeicher im selben Speicherbereich. Wenn nun der Anwender einen Fehler macht und ueber seinen allokierten Speicher hinaus schreibt, dann wird er es erstmal nicht merken und beim naechsten Aufruf einer deiner malloc Funktionen werden diese Sturm-laufen. Das macht es erstmal schwerer den Fehler zu finden und zweitens kann deine Funktion aufgrund von fehlender Fehlerueberpruefung dann einen erheblichen Schaden verursachen.
Dann doch lieber einen Heap und ein Array von verwaltenen Zeigern. Dann wird dein Speicher zwar sowohl durch die Anzahl der Zeiger, als auch durch die Groesse des Speichers limitiert. Jedoch bist du dann auf der sicheren Seite.

kann jemand das problem sehen?

runtime error tritt schon mit dem zweiten malloc auf:

header *next_ptr = curr->next; 
next_ptr->size = heap_size; // hier gibt es den runtime error!!

hi, folgendes basic design concept sollte nun funktionieren...

#include <stdio.h>
#include <stdbool.h>

#define HEAP_MEM_SIZE 100
#define MEMORY_AVAILABLE 1 
#define MEMORY_USED 0 

struct chunk_header {
  struct chunk_header *next; // next pointer on free list
  size_t size;               // the size of this chunk
  bool free;             // > 0 if this pointer is free - useful for runtime assertions
};

typedef struct chunk_header chunk_header;
chunk_header *chunk_header_begin;
char buffer[HEAP_MEM_SIZE];
unsigned int heap_size;

void init() {
	heap_size = HEAP_MEM_SIZE;
	chunk_header_begin = &buffer;
	chunk_header_begin->next = NULL;
	chunk_header_begin->size = heap_size;
	chunk_header_begin->free = MEMORY_AVAILABLE;
}

void init_next_chunk(chunk_header *curr, unsigned int bytes) {
	heap_size -= bytes;
	curr->next = NULL;
	curr->size = heap_size;
	curr->free = MEMORY_AVAILABLE;
}

void *my_malloc(unsigned int nbytes) {
	static bool init_flag = false;

	if(!init_flag) {
		init();
		init_flag = true;
	}

	int alloc_size = nbytes + sizeof(chunk_header);	
	chunk_header *curr = chunk_header_begin;

	while(curr) {
		if(curr->free && curr->size >= alloc_size) {
			curr->free = MEMORY_USED;
			curr->size = alloc_size;
			curr->next = curr + alloc_size;

			init_next_chunk(curr->next, alloc_size);

			// return memory region
			curr = curr + sizeof(chunk_header);
			return curr;
		}

		curr = curr->next;
	}

	return NULL;
}

void my_free(void *firstbyte) {
	chunk_header *mem = (chunk_header*)firstbyte - sizeof(chunk_header);
	chunk_header *curr = chunk_header_begin;

	while (curr) {
		if (curr == mem) {
			heap_size += curr->size;

			// Mark the block as being available
			curr->free = MEMORY_AVAILABLE;
			break;
		}

		curr = curr->next;
	}

	firstbyte = NULL;
}

int main() {
	char *mem1 = (char*)my_malloc(20); 
    memset (mem1,'x',19); 
    mem1[19] = '\0'; 
    char *mem2 = (char*)my_malloc(20); 
    memset (mem2,'y',19); 
    mem2[19] = '\0'; 
    char *mem3 = (char*)my_malloc(20); 
    memset (mem3,'z',19); 
    mem3[19] = '\0'; 

  	my_free(mem2);

  	char *mem4 = (char*)my_malloc(20); 
    memset (mem4,'a',20); 
    mem4[19] = '\0';

    printf("Sollten 19 x sein: %s\n", mem1); 
    printf("Sollten 19 a sein: %s\n", mem4); 
    printf("Sollten 19 z sein: %s\n", mem3);

	return 0;
}

ArneMax

Der Fehler ist immernoch in deinem Code! Fuehre doch einfach mal den kompletten Test aus, den ich dir geschrieben habe. Und warum fragst du ueberhaupt nach Hilfe, wenn du die Hinweise einfach ignorierst?

habe deinen test ausgefuehrt und er war erfolgreich...so was meinst du?

int main() {
	char *mem1= (char*)my_malloc(20); 
    if(mem1 == NULL) {
	    goto err;
	}
    memset (mem1,'x',19); 
    mem1[19] = '\0'; 
    char *mem2= (char*)my_malloc(20); 
    if(mem2 == NULL) {
	    goto err;
	}
    memset (mem2,'y',19); 
    mem2[19] = '\0'; 
    char *mem3= (char*)my_malloc(20); 
    if(mem3 == NULL) {
	    goto err;
	}
    memset (mem3,'z',19); 
    mem3[19] = '\0'; 

    printf("Sollten 19 x sein: %s\n", mem1); 
    printf("Sollten 19 y sein: %s\n", mem2); 
    printf("Sollten 19 z sein: %s\n", mem3); 

    my_free(mem2); 

    char *mem4= (char*)my_malloc(10); 
    if(mem4 == NULL) {
	    goto err;
	}
    mem4[9] = '\0'; 
    char *mem5= (char*)my_malloc(20); 
    if(mem5 == NULL) {
	    goto err;
	}

    printf("Sollten 9 y sein: %s\n", mem4); 
    //printf("Sollten 9 y sein: %s\n", mem5); // <--- warum hier?

    memset (mem5,'a',19); 
    mem5[19] = '\0'; 

    printf("Sollten 19 a sein: %s\n", mem5);

    // Wenn meine Theorie stimmt, dann wird dieses Ergebnis nicht mehr passen... 
    printf("Sollten 19 z sein: %s\n", mem3); 

	return 0;

err:
    printf("could not allocate mem\n");
    return 0;
}

hier die ausgabe:

Sollten 19 x sein: xxxxxxxxxxxxxxxxxxx
Sollten 19 y sein: yyyyyyyyyyyyyyyyyyy
Sollten 19 z sein: zzzzzzzzzzzzzzzzzzz
Sollten 9 y sein: yyyyyyyyy
Sollten 19 a sein: aaaaaaaaaaaaaaaaaaa
Sollten 19 z sein: zzzzzzzzzzzzzzzzzzz

ArneMax

Da ich das ganze gerade auch nur im Kopf durch gehe kann ich dir leider nicht direkt die Fehler zu 100% aufzeigen. Ich kann dich nur darauf aufmerksam machen, was fuer mich beim Lesen fehlerhaft aussieht.

Gerade meine ich zu sehen, dass du deine verkettete Liste mit Speicherplaetzen nur auf schneidest, ein Element anhaengst aber nicht den Rest wieder anknuepfst. In Zeile 49 sagst du einfach, dass der Speicher hinter deinen neu allokierten Speicher die naechste freie Stelle ist. In der Funktion init_next_chunk setzt du dann auch noch die Groesse des Bereiches auf die Groesse deines freien Heaps.

Also entweder ich sehe das Ganze falsch oder ich habe die Werte fuer den Test falsch dimensioniert. Jedoch sollte bei meinem Test drei Speicherfelder hintereinander angelegt werden. Durch das Freigeben des mittleren Feldes sollte Speicher in der Mitte frei sein (im Test 20 Bytes). Durch ein neues Allokieren von 10 Byte sollte der Speicher wiederverwendet werden (durch mem4 im Test). Die Ausgabe beweist auch, dass mem4 den ehemaligen Speicher von mem2 bekommt. Soweit ist jetzt alles in Ordnung.
Aber wenn ich den Fehler richtig sehe, dann wurde mit dem Allokieren von mem4 deine verkettete Liste mit freien Speicher zerschnitten und der naechste freie Speicher liegt nun zwischen mem4 und mem3, hat jedoch die Groesse deines freien Heaps. Durch das Allokieren von mem5 sollte dann der Speicher von mem3 zum Teil doppelt belegt sein (kann aber auch sein, dass ich den Speicher fuer mem5 zu klein ausgewaehlt habe).
Das Ergebnis wuerde dann sein, dass mem3 beschaedigt ist und dass du auch schon nach dem Allokieren von mem4 mem3 nicht mehr freigeben kannst, weil deine verkettete Liste beschaedigt ist.

Dazu kommt dann wie schon zuvor erwaehnt das Problem, dass du ein Konzept verwendest, welches man aus guten Gruenden nicht verwendet. Es reicht aus, dass du spaeter einen kleinen Fehler mit deinem allokierten Speicher machst (also einen Pointerfehlern, von denen du hier ja auch ein paar hast/hattest) und du wirst diesen Fehler nicht finden. Erst wenn du irgendwann wieder malloc oder free aufrufst, dann wirst du nur erleben, dass malloc und free auf irgendwelchen Speicher rumschreiben und im guenstigsten Fall einen runtime error ausloesen.
Ich lege dir daher waermstens ans Herz, dass du dir ein etabliertes System fuer die Speicherverwaltung auswaehlst. Auch solltest du dir vorher mehr Zeit zum Planen des Ablaufes nehmen und verschiedene Szenarien durch gehen.

ArneMax

Ok, ich hatte heute mal kurz die Zeit deinen Code zu testen. Der Fehler, den ich dir mit meinem Test zeigen wollte kam nicht zum Tageslicht. Erstmal muss mem5 nicht mit 20, sondern mit 50 laufen. Dann ist dein Heap generell zu klein. Der Header ist unter meinem Compiler 24 Byte groß. Damit müsste schon beim dritten Malloc ein Fehler auftreten.

Aber kommen wir am Besten zu einer Liste der Fehler:
1. Du rechnest bei der Initialisierung des Heaps nicht die Größe des ersten Headers an (später schon).
2. Folgendes ist falsch:

chunk_header_begin = &buffer;

buffer alleine ist schon die Adresse des Arrays. Daher solltest du das & weg lassen.
3. Folgende Zeile macht nicht das, was du denkst, was sie macht.

curr->next = curr + alloc_size;

Was du machen möchtest ist "curr->next = current_pointer_address + num_of_allocated_bytes". Es macht aber "curr->next = current_pointer_address + num_of_allocated_bytes * sizeof(chunk_header)". Damit liegt alleine schon der zweite angefragt Block weit außerhalb deines Heaps.

Wenn du diese Fehler beseitigst, dann kommst du zu der Ausgabe, die ich vorgesehen hatte:
Sollten 19 x sein: xxxxxxxxxxxxxxxxxxx
Sollten 19 y sein: yyyyyyyyyyyyyyyyyyy
Sollten 19 z sein: zzzzzzzzzzzzzzzzzzz
Sollten 9 y sein: yyyyyyyyy
Sollten 9 y sein:
Sollten 19 z sein: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Also da ist einiges zu machen, bis das ganze funktioniert. Du solltest zumindest mal anfangen den Speicher selber zu überwachen. Bisher hast du zwar ausgaben bekommen, aber deine Pointer sind wild im Speicher rum gesprungen und haben auf irgendwelche Speicherzellen gezeigt.
Also wenn du das ganze unbedingt weiter machen möchtest (und auch noch bei dem Konzept bleiben möchtest), dann solltest du zusehen, dass du deinem Speicher besser überwachst, mit den Pointer etwas sorgfältiger umgehst, mehr Details planst (bevor du den Code schreibst) und (ganz wichtig!) du solltest Fehlerkontrollen einbauen.