linux下基本上所有的stl容器的實現都不是sgi stl的那種使用容器內置freelist內存池的方式了，其默認的allocate只是簡單的調用malloc和free，而在malloc內部實現了內存池。這里的好處在于，如果用內置freelist的做法，就想到于一定義個vector就維護一個freelist內存池，消耗太大，而如果用malloc內存池的做法，就相當于在進程內部共享了一個內存池，增加了分配和釋放的效率。

上面一段對于sgi stl的描述是錯誤的，sgi stl就是實現了該進程中所有內存塊的管理，不管在進程中定義多少個vector或者map之類的，所使用的內存塊均是由sgi 的allocate統一用二級內存池管理。

如此，在運行程序的時候會發現這個情況，malloc一些內存，free之后，進程仍然占用這些內存。

在malloc內部，是將一個大內存塊，將各個小內存塊（還沒有分配的）組織到不同的雙向鏈表中，注意，并不是在物理上將大內存塊進行分割，而是在邏輯上分割。

一個小塊內存我們稱之為chunk , 對于這個chunk用下面的數據結構進行控制管理

struct?chunk?{
????size_t?prev_size;
????size_t?size;?
????struct?chunk*?prev;?
????struct?chunk*?next;?
};

這樣設計的目的就是用以內存復用。（為了便于理解，請無視圖中第5,6個字節空間）

prev_size表示和這個內存塊緊挨著的前一個內存塊的大小，注意這里的緊挨著指的是在物理內存中是緊挨著，而不是指在接下來要講到的鏈表中相鄰。

size的后三個位中的P位表明前一個塊是否正在使用。

prev指針，和next指針，如果這個塊正在使用中，那么這兩個變量占用的空間將被用戶使用，也就是說這兩個變量是無效的

如果塊是free，pre指向在空閑鏈表中前一個塊的地址，next指后一個塊的地址。

如果設置一個塊的指針是p, 這個塊處于使用中，那么用戶實際申請到的內存是 ?（用戶實際需要的內存）+ (4 + 4) - 4 并且要基于8對齊

也就是說，用戶能用的內存是上圖中mem以下的空間，返回給用戶使用的內存指針是 p + (4 + 4)

因為當前塊已經使用了，所以下一個塊的prev_size也就沒有意義，所以也給當前塊了。

空閑塊是由多個雙向鏈表組織的

第一種是bins，bins有128個鏈表，前64個雙向鏈表是定長的，每隔8個字節大小的塊分配在一個雙向鏈表，后面的64個雙向鏈表是不定長的，就是在一個范圍長度的都分配在一個雙向鏈表中。所以長度小于512字節（大約）的都分配在定長的雙向鏈表中。后面的64個雙向鏈表是變長的雙向鏈表，每個雙向鏈表中的chunk都是從小到大排列的。
第二種是unsort雙向鏈表（只有一個雙向鏈表），（是一個緩沖）所有free下來的如果要進入bins雙向鏈表中都要經過unsort雙向鏈表。
第三種雙向鏈表是fastbins，大約有10個定長雙向鏈表，（是一個高速緩沖）所有free下來的并且長度是小于80的chunk就會進入這種雙向鏈表中。進入此雙向鏈表的chunk在free的時候并不修改使用位，目的是為了避免被相鄰的塊合并掉。
malloc的步驟
? ? ? ? ?先在fastbins中找，如果能找到，從雙向鏈表中取下后（不需要再置使用為為1了）立刻返回。
? ? ? ? ?判端需求的塊是否在小箱子（bins的前64個bin）范圍，如果在小箱子的范圍，并且剛好有需求的塊，則直接返回內存地址；如果范圍在大箱子（bins的后64個bin）里，則觸發consolidate。（因為在大箱子找一般都要切割，所以要優先合并，避免過多碎片）
? ? ? ? ?然后在unsort中取出一個chunk，如果能找到剛好和想要的chunk相同大小的chunk，立刻返回，如果不是想要chunk大小的chunk，就把他插入到bins對應的雙向鏈表中去。轉3，直到清空，或者一次循環了10000次。
? ? ? ? ?然后才在bins中找，找到一個最小的能符合需求的chunk從雙向鏈表中取下，如果剩下的大小還能建一個chunk，就把chunk分成兩個部分，把剩下的chunk插入到unsort雙向鏈表中去，把chunk的內存地址返回。
? ? ? ? ?在topchunk（是堆頂的一個chunk，不會放到任何一個雙向鏈表里的）找，如果能切出符合要求的，把剩下的一部分當作topchunk，然后返回內存地址。
? ? ? ? ?如果fastbins不為空，觸發consolidate即把所有的fanbins清空（是把fanbins的使用位置0，把相鄰的塊合并起來，然后掛到unsort雙向鏈表中去），然后繼續第3步。
? ? ? ? ?還找不到話就調用sysalloc，其實就是增長堆了。然后返回內存地址。
free的步驟
? ? ? ? ?如果和topchunk相鄰，直接和topchunk合并，不會放到其他的空閑雙向鏈表中去。
? ? ? ? ?如果釋放的大小小于80字節，就把它掛到fastbins中去，使用位仍然為1，當然更不會去合并相鄰塊。
? ? ? ? ?如果釋放塊大小介于80-128k，把chunk的使用為置成0，然后試圖合并相鄰塊，掛到unsort雙向鏈表中去，如果合并后的大小大于64k，也會觸發consolidate，（可能是周圍比較多小塊了吧），然后才試圖去收縮堆。（收縮堆的條件是當前free的塊大小加上前后能合并chunk的大小大于64k，并且要堆頂的大小要達到閥值，才有可能收縮堆）

當一個chunk被free，并且要被鏈接到bin時，首先要先把該chunk是否處于使用中的標志P設為0，注意，這個標志實際上也處于下一個chunk中，同時如果它前后的chunk也是空閑的，就要進行合并。注意不用檢查其下下一個是否空閑的，因為如果是空閑的，就在上次中已經做個合并了。

至于怎么在初始化時將一個塊用chunk表示，可以參考下面的代碼：

chunk * c = brk(sizeof(chunk) + xxxx);

c->prev_size = xxx;

c->size = xxxx;

malloc需要處理的申請大小是任意的，為了保持有限的鏈表個數。就必須在鏈表上存放了大小不同的塊。它會進行排序，排序是為了加速遍歷查找合適大小的塊。這就是為什么malloc性能不如我們應用內存池的原因，也是為啥應用內存池還有必要存在的原因。換句話說，采用malloc的管理結構設計，但保持鏈表上塊大小相同，將會是一個非常高效的沒有遍歷的O(1)的內存池。

參考 ：http://rdc.taobao.com/blog/cs/?p=1015

http://hi.baidu.com/flowskyac/item/cfab9ff7dcc9c80985d27872

總結

以上是生活随笔為你收集整理的glibc malloc的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。