# 內存，第 2 部分：實現內存分配器 > 原文：<https://github.com/angrave/SystemProgramming/wiki/Memory%2C-Part-2%3A-Implementing-a-Memory-Allocator> ## 內存分配器教程 內存分配器需要跟蹤當前分配的字節以及可供使用的字節。本頁介紹了構建分配器的實現和概念細節，即實現`malloc`和`free`的實際代碼。 ## 這個頁面討論了塊的鏈接 - 我是不是要為它們設置 malloc 內存？ 雖然從概念上講我們正在考慮創建鏈表和塊列表，但我們不需要“malloc memory”來創建它們！相反，我們將整數和指針寫入我們已經控制的內存中，以便以后可以從一個地址一直跳到另一個地址。此內部信息代表一些開銷。因此，即使我們從系統請求了 1024 KB 的連續內存，我們也無法將其全部提供給正在運行的程序。 ## 在塊中思考 我們可以將堆內存視為每個塊分配或未分配的塊列表。我們不是存儲明確的指針列表，而是存儲有關塊大小 _ 的信息，作為塊 _ 的一部分。因此，概念上存在空閑塊的列表，但它是隱式的，即以塊大小信息的形式存儲，作為每個塊的一部分。 我們可以通過添加塊的大小從一個塊導航到下一個塊。例如，如果要指向塊的開頭的指針`p`，則`next_block`位于`((char *)p) + *(size_t *) p`，如果要以字節為單位存儲塊的大小。轉換為`char *`可確保以字節為單位計算指針算法。轉換為`size_t *`確保將`p`的內存讀取為大小值，并且如果`p`是`void *`或`char *`類型則必須。 調用程序永遠不會看到這些值;它們是內存分配器的內部實現。 例如，假設您的分配器被要求保留 80 個字節（`malloc(80)`）并且需要 8 個字節的內部標頭數據。分配器需要找到至少 88 字節的未分配空間。更新堆數據后，它將返回指向塊的指針。但是，返回的指針不指向塊的開頭，因為這是存儲內部大小數據的位置！相反，我們將返回塊的開始+ 8 個字節。在實現中，請記住指針算法取決于類型。例如，`p += 8`添加`8 * sizeof(p)`，不一定是 8 個字節！ ## 實現 malloc 最簡單的實現使用第一個擬合：從第一個塊開始，假設它存在，并迭代直到找到表示足夠大小的未分配空間的塊，或者我們已經檢查了所有塊。 如果找不到合適的塊，則應該再次調用`sbrk()`以充分擴展堆的大小。快速實現可能會對其進行大量擴展，因此我們不需要在不久的將來請求更多的堆內存。 找到空閑塊時，它可能比我們需要的空間大。如果是這樣，我們將在隱式列表中創建兩個條目。第一個條目是分配的塊，第二個條目是剩余的空間。 如果塊正在使用或可用，有兩種簡單的方法可以注意。第一種是將它作為一個字節存儲在頭信息中，同時將其與大小和第二個一起存儲，以將其編碼為大小中的最低位！因此，塊大小信息將僅限于偶數值： ``` // Assumes p is a reasonable pointer type, e.g. 'size_t *'. isallocated = (*p) & 1; realsize = (*p) & ~1; // mask out the lowest bit ``` ## 對齊和四舍五入的考慮因素 許多架構期望多字節基元與 2 ^ n 的某個倍數對齊。例如，通常需要將 4 字節類型與 4 字節邊界（以及 8 字節邊界上的 8 字節類型）對齊。如果多字節基元沒有存儲在合理的邊界上（例如從奇數地址開始），那么性能會受到很大影響，因為它可能需要兩個存儲器讀取請求而不是一個。在一些架構上，懲罰甚至更大 - 程序將因[總線錯誤](http://en.wikipedia.org/wiki/Bus_error#Unaligned_access)而崩潰。 由于`malloc`不知道用戶將如何使用分配的內存（雙精度數組？字符數組？），返回程序的指針需要針對最壞情況進行對齊，這是與體系結構相關的。 從 glibc 文檔中，glibc `malloc`使用以下啟發式：“malloc 為您提供的塊保證對齊，以便它可以保存任何類型的數據。在 GNU 系統上，地址始終是 8 的倍數系統，以及 64 位系統上 16 個的倍數。“ 例如，如果您需要計算需要多少 16 字節單位，請不要忘記向上舍入 - ``` int s = (requested_bytes + tag_overhead_bytes + 15) / 16 ``` 額外的常量確保不完整的單位被四舍五入。請注意，實際代碼更有可能符號大小，例如`sizeof(x) - 1`，而不是編碼數值常數 15。 [如果您對此感興趣，可以參考以下關于內存對齊的精彩文章](http://www.ibm.com/developerworks/library/pa-dalign/) ## 關于內部碎片的說明 當您提供的塊大于其分配大小時，會發生內部碎片。假設我們有一個大小為 16B 的空閑塊（不包括元數據）。如果它們分配 7 個字節，您可能需要向上舍入到 16B 并返回整個塊。 當你實現合并和拆分時，這會變得非常險惡（下一節）。如果你沒有實現任何一個，那么你可能最終返回一個大小為 64B 的塊用于 7B 分配！這個分配有一個 _ 批次 _ 的開銷，這是我們試圖避免的。 ## 實施免費 當調用`free`時，我們需要重新應用偏移量以返回到塊的“實際”開始（還記得我們沒有給用戶指向塊的實際開始嗎？），即到哪里我們存儲了大小信息。 一個簡單的實現只會將塊標記為未使用。如果我們將塊分配狀態存儲在最小的位中，那么我們只需要清除該位： ```c *p = (*p) & ~1; // Clear lowest bit ``` 但是，我們還有一些工作要做：如果當前塊和下一個塊（如果存在）都是空閑的，我們需要將這些塊合并為一個塊。同樣，我們也需要檢查前一個塊。如果存在并表示未分配的內存，那么我們需要將塊合并為單個大塊。 為了能夠使用先前的空閑塊合并空閑塊，我們還需要找到前一個塊，因此我們也將塊的大小存儲在塊的末尾。這些被稱為“邊界標簽”（ref Knuth73）。由于塊是連續的，因此一個塊的末尾位于下一個塊的開頭旁邊。因此，當前塊（除第一個之外）可以進一步查看幾個字節以查找前一個塊的大小。有了這些信息，您現在可以向后跳！ ## 性能 通過以上描述，可以構建存儲器分配器。它的主要優點是簡單 - 與其他分配器相比至少簡單！分配存儲器是最壞情況的線性時間操作（搜索鏈接列表用于足夠大的空閑塊）并且解除分配是恒定時間（不需要將 3 個塊合并到單個塊中）。使用此分配器可以嘗試不同的放置策略。例如，您可以從最后一個凍結塊的位置開始搜索，或者從上次分配的位置開始搜索。如果你確實存儲了指向塊的指針，你需要非常小心它們始終保持有效（例如，當合并塊或其他 malloc 或免費調用改變堆結構時） ## 明確的自由列表分配器 通過實現明確的雙向鏈接的空閑節點列表，可以實現更好的性能。在這種情況下，我們可以立即遍歷下一個空閑塊和前一個空閑塊。這可以將搜索時間減半，因為鏈接列表僅包括未分配的塊。 第二個優點是我們現在可以控制鏈表的排序。例如，當一個塊被釋放時，我們可以選擇將它插入到鏈表的開頭而不是總是在它的鄰居之間。這將在下面討論。 我們在哪里存儲鏈表的指針？一個簡單的技巧是要意識到塊本身沒有被使用并將下一個和前一個指針存儲為塊的一部分（盡管現在你必須確保空閑塊總是足夠大以容納兩個指針）。 我們仍然需要實現邊界標記（即使用大小的隱式列表），這樣我們就可以正確地釋放塊并將它們與它們的兩個鄰居合并。因此，顯式空閑列表需要更多代碼和復雜性。 使用顯式鏈接列表，使用快速簡單的“查找優先”算法來查找第一個足夠大的鏈接。但是，由于可以修改鏈接順序，因此這對應于不同的放置策略。例如，如果鏈接從最大到最小維護，那么這將產生“最適合”的放置策略。 ### 顯式鏈表插入策略 新凍結的塊可以輕松插入兩個可能的位置：開頭或地址順序（通過使用邊界標簽首先找到鄰居）。 在開頭插入會創建一個 LIFO（后進先出）策略：最近的 free'd 空間將被重用。研究表明碎片比使用地址順序更糟糕。 以地址順序插入（“地址排序策略”）插入空閑塊，以便按遞增的地址順序訪問塊。此策略需要更多時間來釋放塊，因為必須使用邊界標記（大小數據）來查找下一個和以前的未分配塊。但是，碎片化程度較低。 ## 案例研究：Buddy Allocator（隔離列表的一個例子） 隔離分配器是將堆分成不同區域的分配器，這些區域由不同的子分配器處理，具體取決于分配請求的大小。大小被分組為類（例如，2 的冪），并且每個大小由不同的子分配器處理，并且每個大小維護其自己的空閑列表。 眾所周知的這種類型的分配器是伙伴分配器。我們將討論二進制伙伴分配器，它將分配分成大小為 2 ^ n（n = 1,2,3，...）的一些基本單位字節數的塊，但其他也存在（例如 Fibonacci 分裂 - 你能不能看看為什么命名？）。基本概念很簡單：如果沒有大小為 2 ^ n 的空閑塊，則轉到下一級并竊取該塊并將其拆分為兩個。如果相同大小的兩個相鄰塊變為未分配，則它們可以一起合并成一個大小為兩倍的單個塊。 好友分配器很快，因為可以從 free'd 塊的地址計算要合并的相鄰塊，而不是遍歷大小標記。最終性能通常需要少量匯編程序代碼才能使用專用 CPU 指令來查找最低的非零位。 Buddy 分配器的主要缺點是它們受 _ 內部碎片 _ 的影響，因為分配被四舍五入到最接近的塊大小。例如，68 字節的分配將需要 128 字節的塊。 ### 進一步閱讀和參考 * 參見[軟件技術基礎和理論計算機科學 1999 年會議論文](http://books.google.com/books?id=0uHME7EfjQEC&lpg=PP1&pg=PA85#v=onepage&q&f=false)（谷歌書籍，第 85 頁） * ThanksForTheMemory UIUC 講座幻燈片（ [pptx](https://subversion.ews.illinois.edu/svn/sp17-cs241/_shared/wikifiles/CS241-05-ThanksForTheMemorySlides.pptx) ）（ [pdf](https://subversion.ews.illinois.edu/svn/sp17-cs241/_shared/wikifiles/CS241-05-ThanksForTheMemorySlides.pdf) ）和 * [維基百科的好友內存分配頁面](http://en.wikipedia.org/wiki/Buddy_memory_allocation) ## 其他分配器 還有許多其他分配方案。例如 [SLUB](http://en.wikipedia.org/wiki/SLUB_%28software%29) （維基百科） - Linux 內核內部使用的三個分配器之一。