Malloc-Implementierung?

Ich versuche es umzusetzen malloc und free für C, und ich bin mir nicht sicher, wie ich den Speicher wiederverwenden soll. Ich habe derzeit eine struct das sieht so aus:

typedef struct _mem_dictionary {
    void *addr;
    size_t size;
    int freed;
} mem_dictionary;

Mein malloc sieht aus wie das:

void *malloc(size_t size) {
    void *return_ptr = sbrk(size);
    if (dictionary == NULL) 
        dictionary = sbrk(1024 * sizeof(mem_dictionary));

    dictionary[dictionary_ct].addr = return_ptr;
    dictionary[dictionary_ct].size = size;
    dictionary[dictionary_ct].freed = 1;
    dictionary_ct++;

    return return_ptr;
}

Wenn ich Speicher freigebe, würde ich die Adresse einfach als markieren 0 (das würde bedeuten, dass es kostenlos ist). In meinem mallocwürde ich dann eine for-Schleife verwenden, um nach einem beliebigen Wert im Array zu suchen, der gleich ist 0 und weisen Sie dieser Adresse dann Speicher zu. Ich bin etwas verwirrt, wie ich das umsetzen soll.

Der einfachste Weg, dies zu tun, besteht darin, eine verknüpfte Liste freier Blöcke zu führen. Im malloc, wenn die Liste nicht leer ist, suchen Sie nach einem Block, der groß genug ist, um die Anfrage zu erfüllen, und geben ihn zurück. Wenn die Liste leer ist oder kein solcher Block gefunden werden kann, rufen Sie auf sbrk etwas Speicher vom Betriebssystem zuzuweisen. in free, fügen Sie den Speicherblock einfach der Liste der freien Blöcke hinzu. Als Bonus können Sie versuchen, zusammenhängende freigegebene Blöcke zusammenzuführen, und Sie können die Richtlinie für die Auswahl des zurückzugebenden Blocks ändern (first fit, best fit, …). Sie können den Block auch teilen, wenn er größer als die Anfrage ist.

Einige Beispielimplementierungen (nicht getestet und offensichtlich nicht Thread-sicher, Verwendung auf eigene Gefahr):

typedef struct free_block {
    size_t size;
    struct free_block* next;
} free_block;

static free_block free_block_list_head = { 0, 0 };
static const size_t overhead = sizeof(size_t);
static const size_t align_to = 16;

void* malloc(size_t size) {
    size = (size + sizeof(size_t) + (align_to - 1)) & ~ (align_to - 1);
    free_block* block = free_block_list_head.next;
    free_block** head = &(free_block_list_head.next);
    while (block != 0) {
        if (block->size >= size) {
            *head = block->next;
            return ((char*)block) + sizeof(size_t);
        }
        head = &(block->next);
        block = block->next;
    }

    block = (free_block*)sbrk(size);
    block->size = size;

    return ((char*)block) + sizeof(size_t);
}

void free(void* ptr) {
    free_block* block = (free_block*)(((char*)ptr) - sizeof(size_t));
    block->next = free_block_list_head.next;
    free_block_list_head.next = block;
}

Notiz: (n + align_to - 1) & ~ (align_to - 1) ist ein Trick zum Runden n auf das nächste Vielfache von align_to das ist größer als n. Das funktioniert nur wann align_to ist eine Zweierpotenz und hängt von der binären Darstellung von Zahlen ab.

Wann align_to eine Zweierpotenz ist, hat es nur ein Bit gesetzt, und somit align_to - 1 hat alle niedrigsten Bitsätze (dh. align_to hat die Form 000…010…0, und align_to - 1 ist von der Form 000...001...1). Das bedeutet, dass ~ (align_to - 1) hat alle hohen Bits gesetzt und die niedrigen Bits nicht gesetzt (d.h. es hat die Form 111...110...0). So x & ~ (align_to - 1) werden alle niedrigen Bits von auf Null gesetzt x und auf das nächste Vielfache von abrunden align_to.

Zum Schluss hinzufügen align_to - 1 zu size stellen Sie sicher, dass wir auf das nächste Vielfache von aufrunden align_to (wenn nicht size ist schon ein Vielfaches von align_to in diesem Fall wollen wir bekommen size).

Sie möchten die nicht festlegen size Feld des Wörterbucheintrags auf Null setzen – Sie benötigen diese Informationen zur Wiederverwendung. Setzen Sie stattdessen freed=1 erst wenn der Block freigegeben wird.

Sie können benachbarte Blöcke nicht zusammenführen, da es möglicherweise zwischenzeitliche Aufrufe zu gab sbrk(), das macht es einfacher. Sie brauchen nur eine for Schleife, die nach einem ausreichend großen freigegebenen Block sucht:

typedef struct _mem_dictionary
{
    void *addr;
    size_t size;
    int freed;
} mem_dictionary;


void *malloc(size_t size)
{
     void *return_ptr = NULL;
     int i;

     if (dictionary == NULL) {
         dictionary = sbrk(1024 * sizeof(mem_dictionary));
         memset(dictionary, 0, 1024 * sizeof(mem_dictionary));
     }

     for (i = 0; i < dictionary_ct; i++)
         if (dictionary[i].size >= size
          && dictionary[i].freed)
     {
         dictionary[i].freed = 0;
         return dictionary[i].addr;
     }

     return_ptr = sbrk(size);

     dictionary[dictionary_ct].addr = return_ptr;
     dictionary[dictionary_ct].size = size;
     dictionary[dictionary_ct].freed = 0;
     dictionary_ct++;

     return return_ptr;
}

void free(void *ptr)
{
    int i;

    if (!dictionary)
        return;

    for (i = 0; i < dictionary_ct; i++ )
    {
        if (dictionary[i].addr == ptr)
        {
            dictionary[i].freed = 1;
            return;
        }
    }
}

Das ist nicht großartig malloc() Implementierung. Tatsächlich die meisten malloc/free Implementierungen weisen jedem von malloc zurückgegebenen Block einen kleinen Header zu. Der Header könnte an der Adresse acht (8) Bytes beginnen weniger als beispielsweise der zurückgegebene Zeiger. In diesen Bytes können Sie einen Zeiger auf die speichern mem_dictionary Eintrag, der den Block besitzt. Dies vermeidet die O(N)-Operation in free. Sie können das O(N) in vermeiden malloc() durch Implementieren einer Prioritätswarteschlange von freigegebenen Blöcken. Erwägen Sie die Verwendung eines Binoms Haufenmit Blockgröße als Index.

Ich leihe mir Code aus Sylvains Antwort. Er scheint es versäumt zu haben, die Größe der free_block*-ini bei der Berechnung des Overheads zu berechnen.

Insgesamt funktioniert der Code, indem dieser free_block als Header dem zugewiesenen Speicher vorangestellt wird. 1. Wenn der Benutzer malloc aufruft, gibt malloc die Adresse der Nutzlast direkt nach diesem Header zurück. 2. Wenn free aufgerufen wird, wird die Anfangsadresse des Headers für den Block berechnet (durch Subtrahieren der Headergröße von der Blockadresse) und zum freien Blockpool hinzugefügt.

typedef struct free_block {
    size_t size;
    struct free_block* next;
} free_block;

static free_block free_block_list_head = { 0, 0 };

// static const size_t overhead = sizeof(size_t);

static const size_t align_to = 16;

void* malloc(size_t size) {
    size = (size + sizeof(free_block) + (align_to - 1)) & ~ (align_to - 1);
    free_block* block = free_block_list_head.next;
    free_block** head = &(free_block_list_head.next);
    while (block != 0) {
        if (block->size >= size) {
            *head = block->next;
            return ((char*)block) + sizeof(free_block);
        }
        head = &(block->next);
        block = block->next;
    }

    block = (free_block*)sbrk(size);
    block->size = size;

    return ((char*)block) + sizeof(free_block);
}

void free(void* ptr) {
    free_block* block = (free_block*)(((char*)ptr) - sizeof(free_block ));
    block->next = free_block_list_head.next;
    free_block_list_head.next = block;
}