作為一個C程序員，每天都在和malloc/free/calloc/realloc系列函數打交道。也許和它們混得太熟了，反而忽略了它們的存在，甚至有了三五年的交情，仍然對它們的實現一無所知。相反，一些好奇心未泯的新手，對它們的實現有著濃厚的興趣。當初正是一個新同事的問題，促使我去研究內存管理算法的實現。
內存管理算法多少有些神秘，我們很少想著去實現自己的內存管理算法，這也難怪：有這樣需求的情況並不多。其實，至於內存分配算法的實現，說簡單也簡單，說復雜也復雜。要寫一個簡單的，或許半天時間就可以搞掂，而要寫一個真正實用的，可能要花上你幾周甚至幾個月的時間。
malloc和free是兩個核心函數，而calloc和realloc之所以存在，完全是為了提高效率的緣故。否則完全可以用malloc和free的組合來模擬它們。
拿calloc函數的實現來說，在32位機上，內存管理器保證內存至少是4字節對齊的，其長度也會擴展到能被4字節整除，那麼其清零算法就可以優化。可以一次清零4個字節，這大大提高清零速度。
拿realloc函數的實現來說，如果realloc的指針後面有足夠的空間，內存管理器可以直接擴展其大小，而無須拷貝原有內容。當然，新大小比原來還小時，更不拷貝了。相反，通過malloc和free來實現realloc時，兩種情況下都要拷貝，效率自然會低不少。
另外還有兩個非機標准的，但很常用的函數，也涉及到內存分配：strdup和strndup。這兩個函數在linux和win32下都支持，非常方便。這完全可以用malloc來模擬，而且沒有性能上的損失。
這裡我們主要關注malloc和free兩個函數的實現，並以glibc 2.3.5(32位linux) 為例分析。
內存管理器的目標
內存管理器為什麼難寫？在設計內存管理算法時，要考慮什麼因素？管理內存這是內存管理器的功能需求。正如設計其它軟件一樣，質量需求一樣占有重要的地位。分析內存管理算法之前，我們先看看對內存管理算法的質量需求有哪些：
l 最大化兼容性
要實現內存管理器時，先要定義出分配器的接口函數。接口函數沒有必要標新立異，而是要遵循現有標准(如POSIX或者Win32)，讓使用者可以平滑的過度到新的內存管理器上。
l 最大化可移植性
通常情況下，內存管理器要向OS申請內存，然後進行二次分配。所以，在適當的時候要擴展內存或釋放多余的內存，這要調用OS提供的函數才行。OS提供的函數則是因平台而異，盡量抽象出平台相關的代碼，保證內存管理器的可移植性。
l 浪費最小的空間
內存管理器要管理內存，必然要使用自己一些數據結構，這些數據結構本身也要占內存空間。在用戶眼中，這些內存空間毫無疑問是浪費掉了，如果浪費在內存管理器身的內存太多，顯然是不可以接受的。
內存碎片也是浪費空間的罪魁禍首，若內存管理器中有大量的內存碎片，它們是一些不連續的小塊內存，它們總量可能很大，但無法使用，這也是不可以接受的。
l 最快的速度
內存分配/釋放是常用的操作。按著2/8原則，常用的操作就是性能熱點，熱點函數的性能對系統的整體性能尤為重要。
l 最大化可調性（以適應於不同的情況）
內存管理算法設計的難點就在於要適應用不同的情況。事實上，如果缺乏應用的上下文，是無法評估內存管理算法的好壞的。可以說在任何情況下，專用算法都比通用算法在時/空性能上的表現更優。
為每種情況都寫一套內存管理算法，顯然是不太合適的。我們不需要追求最優算法，那樣代價太高，能達到次優就行了。設計一套通用內存管理算法，通過一些參數對它進行配置，可以讓它在特定情況也有相當出色的表現，這就是可調性。
l 最大化局部性(Locality)
大家都知道，使用cache可以提高程度的速度，但很多人未必知道cache使程序速度提高的真正原因。拿CPU內部的cache和RAM的訪問速度相比，速度可能相差一個數量級。兩者的速度上的差異固然重要，但這並不是提高速度的充分條件，只是必要條件。
另外一個條件是程序訪問內存的局部性(Locality)。大多數情況下，程序總訪問一塊內存附近的內存，把附近的內存先加入到cache中，下次訪問cache中的數據，速度就會提高。否則，如果程序一會兒訪問這裡，一會兒訪問另外一塊相隔十萬八千裡的內存，這只會使數據在內存與cache之間來回搬運，不但於提高速度無益，反而會大大降低程序的速度。
因此，內存管理算法要考慮這一因素，減少cache miss和page fault。
l 最大化調試功能
作為一個C/C++程序員，內存錯誤可以說是我們的噩夢，上一次的內存錯誤一定還讓你記憶猶新。內存管理器提供的調試功能，強大易用，特別對於嵌入式環境來說，內存錯誤檢測工具缺乏，內存管理器提供的調試功能就更是不可或缺了。
l 最大化適應性
前面說了最大化可調性，以便讓內存管理器適用於不同的情況。但是，對於不同情況都要去調設置，無疑太麻煩，是非用戶友好的。要盡量讓內存管理器適用於很廣的情況，只有極少情況下才去調設置。
設計是一個多目標優化的過程，有些目標之間存在著競爭。如何平衡這些競爭力是設計的難點之一。在不同的情況下，這些目標的重要性又不一樣，所以根本不存在一個最好的內存分配算法。
關於glibc的內存分配器，我們並打算做代碼級分析，只談談幾點有趣的東西：
1. Glibc分配算法概述：
l 小於等於64字節：用pool算法分配。
l 64到512字節之間：在最佳憑配算法分配和pool算法分配中取一種合適的。
l 大於等於512字節：用最佳憑配算法分配。
l 大於等於128K：直接調用OS提供的函數(如mmap)分配。
2. Glibc擴展內存的方式：
l int brk(void *end_data_segment);
本函數用於擴展堆空間（堆空間的定義可參考內存模型一章），用end_data_segment指明堆的結束地址。
l void *sbrk(ptrdiff_t increment);
本函數用於擴展堆空間（堆空間的定義可參考內存模型一章），用increment指定要增加的大小。
l void* mmap(void *start, size_t length, int prot , int flags, int fd, off_t offset);
本函數用於分配大塊內存了，如前面所述大於128K的內存。
3. 空指針和零長度內存
l free(NULL)會讓程序crash嗎？答案是不會，標准C要求free接受空指針，然後什麼也不做。
l malloc(0)會分配成功嗎？答案是會的，它會返回一塊最小內存給你。
4. 對齊與取整
l 內存管理器會保證分配出來的內存地址是對齊的，通常是4或8字節對齊。
l 內存管理器會對要求內存長度取整，讓內存長度能被4或8的整除。
5. 已經分配內存的結構
如果前面有一塊有效內存塊的，則第一個size_t指明前一塊內存的大小。
第二個size_t指明自己的大小，同時還指明：自己是不是用mmap分配的(M)，前面是否有一個效內存塊（P）。你可能覺得奇怪，在32位機上，sizeof(size_t)就是32位，怎麼還能留下兩個位來保存標志呢？前面我們說了，會對內存長度取整，保證最低2或3bits為0，即是空閒的。
6. 空閒內存的管理
由此可以看出，最小內存塊的長度為16字節：
sizeof(size_t) +
sizeof(size_t) +
sizeof(void*) +
sizeof(void*) +
0
這一招非常管用，第一次看到時，感覺簡直太巧妙了。這使得無需要額外的內存來管理空閒塊，利用空閒塊自己，把空閒塊強制轉換成一個雙向鏈表就行了。
