實作 malloc() 和 free() — 分割大塊

在本系列的上一篇文章中，我們看到了選擇要重用的記憶體區塊的順序如何導致更大或更少的記憶體消耗，並且我們更改了函數來避免這種情況浪費。但我們需要解決另一個甚至更嚴重的問題：有時，一個非常大的記憶體區塊可能會佔用幾個較小區塊可以使用的空間。考慮下面的情況，我們分配一大塊內存，釋放它，然後分配兩個小得多的區塊：

void *ptr1 = abmalloc(128);
void *ptr2 = abmalloc(8);
abfree(ptr1);
void *ptr3 = abmalloc(8);
void *ptr4 = abmalloc(8);

這裡，我們有一個空閒的 128 位元組記憶體區塊，當我們分配一個只有 8 個位元組的區塊時，所有 128 位元組都變得不可用。當我們分配另一個 8 位元組區塊時，堆需要再次增長。這不是對內存的有效利用。

對於這種情況至少有兩種流行的解決方案。更有效的方法是使用 bins：列出大小分組的區塊。這是一種更複雜、更有效的方法，但也更複雜。另一個更簡單的選擇是找到一個大塊並將其分成更小的塊。我們將遵循這種方法。

但請記住：更簡單並不意味著簡單;-)

初始重構

在開始之前，讓我們先進行一個小的重構。目前， header_new() 函數做了兩件事：為新區塊分配更多記憶體並初始化其標頭，設定元資料和指向前一個區塊的指標。初始化標頭的部分可能有用，所以讓我們將其提取出來。我們將建立兩個新函數來提高可讀性：

• header_plug() 函數，它將初始化的區塊「插入」到前一個和下一個區塊。
• header_init() 函數，用於設定區塊元資料的初始值（大小和可用性）。

它們的外觀如下：

void header_init(Header *header, size_t size, bool available) {
    header->size = size;
    header->available = available;
}

void header_plug(Header *header, Header *previous, Header *next) {
    header->previous = previous;
    if (previous != NULL) {
        previous->next = header;
    }
    header->next = next;
    if (next != NULL) {
        next->previous = header;
    }
}

現在，我們只需要修改 header_new() 即可使用這些新函數：

Header *header_new(Header *previous, size_t size, bool available) {
    Header *header = sbrk(sizeof(Header) + size);
    header_init(header, size, available);
    header_plug(header, previous, NULL);
    return header;
}

（此外，我們可以從 abmalloc() 函數中刪除最後一行 ->previous->next = last; 行，因為 header_plug() 現在可以處理該問題。）

分裂方塊

有了這些工具，讓我們建立 header_split() 函數。給定標頭和所需的最小大小，如果原始區塊足夠大以包含

，則此函數會將記憶體區塊分成兩部分

• 所需尺寸，
• 新區塊的新標頭，以及
• 一點額外的記憶體。

首先，我們檢查塊是否足夠大：

Header *header_split(Header *header, size_t size) {
    size_t original_size = header->size;
    if (original_size >= size + sizeof(Header)) {

如果滿足這個條件，我們就分割區塊。首先，我們透過減去標頭的大小和 abmalloc 請求的空間來減少目前區塊的大小：

void *ptr1 = abmalloc(128);
void *ptr2 = abmalloc(8);
abfree(ptr1);
void *ptr3 = abmalloc(8);
void *ptr4 = abmalloc(8);

這會在當前區塊之後留下一個記憶體空間，我們將用它來建立新區塊。我們計算這個新區塊的指標：

void header_init(Header *header, size_t size, bool available) {
    header->size = size;
    header->available = available;
}

void header_plug(Header *header, Header *previous, Header *next) {
    header->previous = previous;
    if (previous != NULL) {
        previous->next = header;
    }
    header->next = next;
    if (next != NULL) {
        next->previous = header;
    }
}

現在我們有了指向新區塊的指針，我們用 header_init() 初始化它的頭：

Header *header_new(Header *previous, size_t size, bool available) {
    Header *header = sbrk(sizeof(Header) + size);
    header_init(header, size, available);
    header_plug(header, previous, NULL);
    return header;
}

我們使用 header_plug() 將新區塊連接到前一個和下一個區塊：

Header *header_split(Header *header, size_t size) {
    size_t original_size = header->size;
    if (original_size >= size + sizeof(Header)) {

如果原始區塊是最後一個，那麼新區塊現在將是最後一個，因此我們更新最後一個指標：

header->size = original_size - size - sizeof(Header);

最後，我們回到新區塊：

Header *new_header = header + sizeof(Header) + header->size;

如果原始區塊不夠大，我們只需返回原始區塊：

header_init(new_header, size, true);

更新 abmalloc()

現在，我們只需要回到 abmalloc() 函數，在找到可用區塊的地方，我們呼叫 header_split() 來嘗試拆分它：

header_plug(new_header, header, header->next);

如果區塊可以分裂，則傳回新區塊。否則，原始區塊將像以前一樣保留並返回。

關於區塊分裂的注意事項

請注意，我們在原始區塊的末尾創建了新區塊。我們可以在一開始就創建它，但是透過在最後建立新的已使用區塊，新的空閒區塊會更接近舊區塊。這樣，下次呼叫 abmalloc() 時就會先找到它。

分割大記憶體區塊是向前邁出的一步，但存在相反的問題：小記憶體區塊可能會導致碎片，發出更大的請求會導致堆增長。我們將在下一篇文章中看到如何解決這個問題。

以上是實作 malloc() 和 free() — 分割大塊的詳細內容。更多資訊請關注PHP中文網其他相關文章！