dlmalloc由Doug Lea編寫的內存分配算法

????

(1)mspace_malloc/mspace_free

(2)?dlmalloc/dlfree

???????

1.邊界標記

2.空閑塊分箱:2個分箱數組

?? ?(1)小塊空閑塊大小(0-256):數組元素-空閑塊鏈表

??? (2)大塊空閑塊大小(>256):數組元素-空閑塊樹

3.?空閑段

??

內存分配過程:查找空閑內存

1.小塊內存(1)相應鏈表---->清出鏈表,返回(空閑塊中數據)內存地址

?????????????? (2)所有鏈表---->清出

???????????????(3)樹

???????????????(4)上次分配剩余的空閑塊(找到后分割剩下的)---->清出鏈表,分割

???????????????(5)空閑段

???????????????(6)系統分配內存

2.大塊內存(1)樹

???????????????(2)上次分配剩余的空閑塊

?????????????? (3)空閑段

?????????????? (5)系統分配內存

??

內存釋放過程:

??

??

??

1.邊界標記

Dlmalloc將內存分成很多塊，并且采用所謂的邊界標記法對內存進行管理，在Dlmalloc的實現源碼中定義了兩種結構體malloc_chunk 和malloc_tree_chunk，從它們的定義中可以看到結構體malloc_tree_chunk除了比malloc_chunk多三個字段以外，前四個字段和malloc_chunk完全一樣。這兩種結構體主要用于對內存塊按大小進行不同的管理。
struct malloc_chunk {
??size_t? ?? ?? ?? ?? ?prev_foot;??/* Size of previous chunk (if free).??*/
??size_t? ?? ?? ?? ?? ?head;? ?? ? /* Size and inuse bits. */
??struct malloc_chunk* fd;? ?? ?? ?/* double links -- used only if free. */
??struct malloc_chunk* bk;
};
typedef struct malloc_chunk??mchunk;
typedef struct malloc_chunk* mchunkptr;
typedef struct malloc_chunk* sbinptr;??/* The type of bins of chunks */
struct malloc_tree_chunk {
??/* The first four fields must be compatible with malloc_chunk */
??size_t? ?? ?? ?? ?? ?? ???prev_foot;
??size_t? ?? ?? ?? ?? ?? ???head;
??struct malloc_tree_chunk* fd;
??struct malloc_tree_chunk* bk;
??struct malloc_tree_chunk* child[2];
??struct malloc_tree_chunk* parent;
??bindex_t? ?? ?? ?? ?? ?? ?index;
};

我們先來看看只考慮使用結構體malloc_chunk管理內存的情況（內存都被分為小塊，32位機器上即是256字節以下，而對于結構體 malloc_tree_chunk，其管理的是大塊，32位機器上即是256字節以上）：


按照邊界標記法，結構體malloc_chunk通過字段head和prev_foot將內存分割成很多塊，從圖中①所示，可以看到某結構體內的 prev_foot是記錄的前一個chunk塊的信息（事實上是前一個chunk塊的大小），因此我們可以利用如下宏：
#define prev_chunk(p) ((mchunkptr)( ((char*)(p)) - ((p)->prev_foot) ))
來獲得前一個chunk塊的malloc_chunk結構體指針。
指針fd、bk只有當該chunk塊空閑時才存在，其作用時用于加入到空閑chunk塊鏈中統一管理，而如果該chunk塊被分配給應用 程序使用，那么這兩個指針也就沒有用（該已經 chunk塊從空閑鏈中拆出）了，所以也當作應用程序的使用空間，而不至于浪費，圖中②所示。
head字段記錄與本chunk塊的相關信息，這包括本chunk塊大小，本塊是否在使用中，前一chunk塊是否在使用中。
head一個字段就能存儲這么多信息是因為Dlmalloc在分割內存的時候總是以地址對齊（默認是8字節，可以自由設置，但是8字節是最小值并且設置的值必須是2為底的冪函數值，即是alignment = 2^n，n為整數且n>=3）的方式來進行的，所以用head來存儲本chunk塊大小字節數的話，其末3bit位總是0，因此這三位可以用來存儲其它信息，比如：
以第0位作為標志位，標記前一chunk塊是否在使用中，為1表示使用，為0表示空閑。
以第1位作為標志位，標記本chunk塊是否在使用中，為1表示使用，為0表示空閑。
我們來看看它們的各自相關判斷代碼：
#define SIZE_T_ONE? ?? ?? ? ((size_t)1)
#define SIZE_T_TWO? ?? ?? ? ((size_t)2)
#define PINUSE_BIT? ?? ?? ? (SIZE_T_ONE)
#define CINUSE_BIT? ?? ?? ? (SIZE_T_TWO)
#define cinuse(p)? ?? ?? ???((p)->head & CINUSE_BIT)
#define pinuse(p)? ?? ?? ???((p)->head & PINUSE_BIT)
對于前面說的prev_foot字段，也利用了其一個空閑位用于標記該chunk塊是否右mmap分配，于此類似，所以就不多說了，感興趣的可以查看源碼。
對于結構體malloc_tree_chunk，其實在內存分割上合結構體malloc_chunk完全一致，因為它們的前四個字段完全一樣（事實上只有兩個字段prev_foot和head起邊界標記作用），其它的字段都是用于空閑鏈管理的。
本篇簡單的把Dlmalloc如果按照邊界標記法分割內存描述了一下，下篇繼續兩種空閑鏈的各自管理分析。

二.空閑塊分箱

(1)對于大小在 256 字節以下的 chunk 塊是通過 malloc_chunk 組織管理的， 256 字節 以下的chunk塊一共有256/8=32類，即字節為8字節、16字節、24字節、32字節，……，256字節，因此dlmalloc維護32個雙向環形鏈表（而且具有鏈表頭節點，加頭節點的最大作用就是便于對鏈表內節點的統一處理，即簡化編程），每一個鏈表里的各空閑chunk塊的大小一致，因此當應用程序需要某個字節大小（這里的字節大小是考慮了chunk塊頭和對齊等所占空間了的，即如果應用如果程序調用函數malloc( 8 )，那么到dlmalloc這應該比8大，這種更細節的疑問下面還有，并非我故意不表達，只是轉述太多了，倒說不清我自己真正想說的了，閱讀時請讀者自己注意就好）的內存空間時直接在對應的鏈表內取就可以了（具體稍有不同，即如果對應鏈表內沒有空閑可用chunk塊，則還會查看下一個鏈表，舉個例子：當應用程序申請32個字節，如果32字節大小的鏈表為空，那么dlmalloc還會在大小為40字節的鏈表內查找空閑chunk塊。），這樣既可以很好的滿足應用程序的內存空間申請請求而又不會出現太多的內存碎片。我們可以用如下圖來表示dlmalloc對256字節以下的空閑chunk塊組織方式。

?

(2)對于大小在256字節以上的chunk塊，dlmalloc同樣也采用了所謂的分箱機制，不過由于大于256的數目有很多，因此這里的分箱不能夠像對于0到256這個有限區間的分箱來得簡單。?

?? ?

?

??

?

dlmalloc程序使用 smallbins 數組來記錄這 32個雙向環形鏈表表頭，該字段定義在結構體malloc_state內，在這里我們先不管malloc_state結構體而只關注 smallbins 這個字段，它的定義如下：
struct malloc_chunk {
size_t
prev_foot;
/* Size of previous chunk (if free).
*/
size_t
head;
/* Size and inuse bits. */
struct malloc_chunk* fd;
/* double links -- used only if free. */
struct malloc_chunk* bk;
};
mchunkptr
smallbins[(NSMALLBINS+1)*2];
最后，至于為什么是 66 個數組元素而不是 64 或 65 ，這個仔細想想也好理解，好了，就到這，下篇繼續吧。
其中，mchunkptr在上一小節已經提過，為“typedef struct malloc_chunk* mchunkptr;”，而宏NSMALLBINS為32，即是“#define NSMALLBINS (32U)”。因此smallbins為一個具有66個malloc_chunk結構體指針元素的數組，為什么是66個呢？不是32就可以了么？這里 Doug Lea使用了一個技巧，如果按照我們的常規想法，也許會申請32個malloc_chunk結構體指針元素的數組，然后再給鏈表申請一個頭節點（即32 個），再讓每個指針元素正確指向而形成32個具有頭節點的鏈表。事實上，對于malloc_chunk類型的鏈表“頭節點”，其內的prev_foot和 head字段是沒有任何實際作用的，因此這兩個字段所占空間如果不合理使用的話那就是白白的浪費。我們再來看一看66個malloc_chunk結構體指針元素的數組占了多少內存空間呢？結果為66*4=264字節。而32個malloc_chunk類型的鏈表“頭節點”需要多少內存呢？32*16=512，真的是512么？不是，剛才不是說了，prev_foot和head這兩個字段是沒有任何實際作用的，因此完全可以被重用（覆蓋），因此實際需要內存為32*8=256。264大于256（事實上前8個字節被浪費掉了），那么這66個malloc_chunk結構體指針元素數組所占內存空間就可以存儲這32個頭節點了，事實上Doug Lea也是這么做的。我們來看下于此相關的這一句代碼：

#define smallbin_at(M, i)? ?((sbinptr)((char*)&((M)->smallbins[(i)<<1])))

其中的sbinptr也是個malloc_chunk結構體指針類型（typedef struct malloc_chunk* sbinptr;），M表示前面提到的結構體malloc_state，各位仔細體會一下這句代碼中的強制轉換就會理解這種技巧了。

??

總結

以上是生活随笔為你收集整理的DLmalloc 内存分配算法的全部內容，希望文章能夠幫你解決所遇到的問題。

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