heap_allocator
1.0.0
這是我為我一直在開發的一個業餘愛好作業系統編寫的一個簡單的堆分配器。我寫這個分配器時只做了很少的研究，而且它被設計得盡可能容易理解。我認為這個儲存庫對於那些剛接觸作業系統開發的人（例如我自己）或有興趣查看 malloc 和 free 等函數的簡化版本的人來說很有用。
有兩個頭檔定義堆和鍊錶。編譯此儲存庫：
$ gcc main.c llist.c heap.c -o heap_test
$ ./heap_test
這將運行分配器的演示並列印出一些資訊。
為了初始化這個堆，必須提供一段記憶體。在此儲存庫中，該記憶體由malloc提供（是的，透過堆分配堆）。在作業系統設定中，某些頁面需要映射並提供給堆（一種情況）。請注意， heap_t結構中的 bin 也需要為其分配記憶體。
當呼叫函數 init_heap 時，必須提供空堆結構（帶有分配的 bin 指標）的位址。然後，init_heap 函數將建立一個帶有標頭（ node_t結構）和頁腳（ footer_t結構）的大塊。為了確定區塊的大小，函數使用常數HEAP_INIT_SIZE 。它將把它加到start參數中以確定堆的結束位置。
每個記憶體區塊的開頭都有一個節點結構，最後有一個頁腳結構。此節點保存大小（無論區塊是否空閒）以及雙向鍊錶中使用的兩個指標（下一個和上一個）。頁腳結構僅保存指向標頭的指標（在釋放相鄰區塊時使用）。堆末尾的塊稱為“荒野”塊。它是最大的區塊，其最小和最大大小在 heap.h 中定義。收縮和擴展堆就像調整這個荒野塊的大小一樣簡單。空閒的記憶體區塊儲存在「bins」中，每個bin實際上只是具有相似大小的節點的雙向連結清單。堆結構保存定義數量的 bin（heap.h 中的BIN_COUNT ）。為了確定放置區塊的 bin，區塊的大小透過函數get_bin_index映射到 bin 索引。這種一致的分箱功能將確保可以以定義的方式存取和儲存區塊。區塊在插入 bin 時進行排序，因此區塊插入不是 O(1)，但這使得更容易找到最適合的區塊。請注意，可以按照該堆的使用者認為合適的方式定義分箱函數。確定更複雜的分箱函數以幫助快速檢索區塊可能是有益的。
函數heap_alloc取得要指派的堆結構的位址和大小。該函數只是使用get_bin_index來確定該大小的區塊應該在哪裡，當然可能不存在該大小的區塊。如果在相應的 bin 中沒有找到區塊，則將檢查下一個 bin。這將繼續，直到找到一個塊，或到達最後一個 bin，在這種情況下，將從荒野塊中取出一塊內存。如果找到的塊足夠大，那麼它將被分割。為了確定是否應該分割一個區塊，從我們目前分配不使用的元資料量（開銷）中減去。如果剩下的內容大於或等於MIN_ALLOC_SZ那麼這意味著我們應該分割這個區塊並將剩餘的內容放入正確的垃圾箱中。一旦我們準備好返回找到的區塊，我們就會取得next欄位的位址並傳回它。這樣做是因為在分配區塊時未使用next和prev字段，因此區塊的使用者可以將資料寫入這些字段，而不會影響堆的內部工作。
函數heap_free採用heap_alloc回傳的指標。它減去正確的偏移量以獲得節點結構的位址。不是簡單地將塊放入正確的容器中，而是檢查所提供的塊周圍的塊。如果這些區塊中的任何一個是空閒的，那麼我們可以合併這些區塊以創建更大的區塊。為了合併區塊，頁腳用於取得前一個區塊的節點結構和下一個區塊的節點結構。例如，假設我們有一個名為to_free區塊。為了取得該區塊之前的區塊，我們減去sizeof(footer_t)以取得前一個區塊的頁尾。頁腳包含指向前一個區塊的頭部的指標。要取得下一個區塊，我們只需取得to_free的頁腳，然後新增sizeof(footer_t)即可取得下一個區塊。一旦完成所有這些並重新計算大小，該區塊就會放回容器中。
注意：此程式碼最初是為 32 位元機器編譯的，這表示當使用此程式碼時，可以將 int 轉換為指針，因為它們的大小相同。在 64 位元系統上，編譯器會警告您大小差異。為了消除這些警告，我在從 unsigned int 轉換為指標時使用了uintptr_t 。這確實使可讀性有點混亂，並且一些強制轉換和指針算術很冗長，因此在閱讀程式碼時請記住這一點。
