簡易 malloc/free 實作筆記

在C語言當中很常用到 malloc 來動態配置一塊記憶體，透過 malloc 宣告出來的記憶體是位在Heap當中，如下圖所示

因此，實作 malloc 的目標就是把Heap Top的指標往未分配的記憶體區段移動，這部分有很多不同的實作方法，在這裡會提到的是brk與sbrk，其定義如下

int brk(void *addr);
void *sbrk(intptr_t x);

1. brk() 將Program Break的位置往指定的addr移動
2. sbrk() 將目前的Program Break位置往上加 x Bytes，並回傳這塊記憶體的起點

最簡單的malloc可以透過以下程式碼來實作，若OS分配記憶體失敗則會回傳(void *) -1

#include <unistd.h>
void *malloc(unsigned int size) {
  void *start = sbrk(0);
  void *request = sbrk(size);
  if (request == (void*) -1) { // OS分配失敗
    return NULL;
  } else {
    return p;
  }
}

malloc分配記憶體的方法最簡單就是這樣，但分配完之後還需要管理，在這裡是透過Linked-List的方式來做記憶體管理，每次分配記憶時額外加上一段header，讓我們能夠到這段分配的記憶體大小以及是否已經被釋放等等資訊，結構如下。

typedef struct header {
    unsigned int size; // 分配的記憶體大小
    unsigned int free; // 是否被釋放
    struct header *next; // 下一段記憶體區塊在哪
}Header;

這裡可能會有個疑問就是，heap上方的記憶體不就是連續給我們使用的嗎，為什麼還需要用到Linked-List?

主要是因為程式其他部分也有可能會更動到Program Break指標的位置，因此使用上可能會出現不連續的情況。

首先我們需要最一開始的Program Break起點

void *global_base = NULL;

透過sbrk宣告一塊size+sizeof(Header)的記憶體，用來存放每一個區塊的資料，每次宣告完成都需更新header的資料，函式傳入的 *last 為最後一個node的位址，用來判斷global_base是否為NULL。

Header *request_memory(Header *last, unsigned int size){
    void *heapBegin = sbrk(0);
    Header *block = sbrk(sizeof(Header) + size);
    if(!block){
        printf("sbrk error");
        return NULL;
    }
    if(last == NULL){
        last = block;
    }
    block->size = size;
    block->free = 0;
    block->next = NULL;
    return block;
}

malloc本體的部分設計為傳入一個無號整數，用來指定分配的大小，並將request_memory成功分配的位址放到對應的變數上。 在使用者的角度上，malloc回傳的位址應該是能直接存放資料的位址，而不是header起始的位址，因此需要+1之後再回傳(available_block型態為Header*，所以+1是移動16 Bytes)。

void* _malloc(unsigned int size){
    Header *available_block;
    if(!global_base){
        available_block = request_memory(NULL, size);
        global_base = available_block;
    }
    return (available_block+1);

}

接下來要處理的是global_base已經有資料，或是已經被釋放過記憶體的處理方法，在此我們需要寫一個在走訪malloc list的函式，檢查每個block是否有被釋放而且大小是我們所需要的空間，若找到足夠的空間則回傳該空間的位址。

void *find_free_space(unsigned int size){
    Header *current = global_base;
    while(current->next){
        if(current->size>=size && current->free == 1){
            return current;
        }
        current = current->next;
    }
    return current;
}

之後把malloc做一點改寫，加入走訪malloc list與分配記憶體的方法

void* _malloc(unsigned int size){
    printf("-->_malloc\n");
    Header *available_block;
    if(!global_base){
        available_block = request_memory(NULL, size);
        global_base = available_block;
    }
    else{
        Header *block = find_free_space(size); //檢查是否有適合的空間
        if(block->next == NULL){ // 若走到最後一個block，則直接宣告新空間
            available_block = request_memory(block, size);
            block->next = available_block; // 把最後一個block連結到新的block上
        }
        else{ //找到適合的空間直接使用
            block->size = size;
            block->free = 0;
            available_block = block;
        }
    }
    return (available_block+1);

}

最後要做的函式就是剛剛都沒提到的free，由於我們在malloc時回傳的都是+sizeof(Header)大小的位址，因此在free時需要減掉一次sizeof(Header)才是我們當初真正宣告的標頭位置，找到這個位置之後即可將free的內容改為1。

void _free(Header *target){
    if(target == NULL) return;
    Header *h = target-1;
    h->free = 1;
}

以上就大概是最簡單的 malloc/free 實作方法，這個程式還有非常非常多的空間可以改，時做方法沒絕對，在此只是說個入門。