Dlmalloc详解

Dlmalloc详解

Dlmalloc是目前一个十分流行的内存分配器，其由DougLea从1987年开始编写，到目

前为止，最新版本为2.8.3，由于其高效率等特点被广泛的使用。U-boot上使用的dlmalloc的版本是2.6.6。

1边界标注

首先解释一下chunk的概念，这个概念对内存分配器而言十分重要。Chunk是大块的意思，在dlmalloc中指包含了用户空间、heap控制信息空间以及出于对齐需求而多出来的空间的内存空间，是dlmalloc分配释放的基本操作对象。

占据了整个heap有两种类型的chunk，已分配的chunk和未分配的chunk，两者交错排列，
空间。注意，没有相邻的两个未分配的chunk，因为在调用free释放被使用过的chunk时，dlmalloc将合并任何相邻的空闲chunk。交错的两种chunk看起来是这样的。

Dlmalloc使用双向链表来管理空闲chunk，其节点数据结构体定义如下：

成员prev_size记录了物理位置上相邻的前一个chunk的大小，利用prev_size可以找到前一个chunk，这在调用free合并前一个空闲块时派上了用场。

成员size记录了该chunk的大小，dllmalloc在32位处理器上总是8字节对齐，故size的低3位对size而言是无效的，dlmalloc利用这三位来记录一些信息。

记，如果为0x01，说明被分配；

那么释放时调用munmap；
Fd和bk则分别指向双向链表中前一个节点和后一个节点。

其物理布局看起来像这样：

可以看出，chunk指针指向heap内部控制信息，图中head和foot区域的sizeof chunk必须是一样的，如此nextchunk才能根据sizeof chunk准确地找到chunk的位置。

另一种是已分配的chunk，其结构体和未分配的chunk结构体一样，只是不会使用fd和bk两个成员，因为被分配后已经不需要这两个域了，其物理布局看起来像下图，chunk指针后面8字节的偏移处，即mem区域，是返回给用户的内存指针，该chunk的heap控制信息占据了8个字节。

在调用malloc时，首先会将用户申请的size转换为系统可用的size。

#definerequest2size(req) \
(((long)((req)+ (SIZE_SZ + MALLOC_ALIGN_MASK)) < \
(long)(MINSIZE+ MALLOC_ALIGN_MASK)) ? MINSIZE : \
(((req)+ (SIZE_SZ + MALLOC_ALIGN_MASK)) & ~(MALLOC_ALIGN_MASK)))

从这个宏定义中，我们可以获取3点信息：
1、系统可用的size和用户申请的size的差值，最小是0x042、系统可用的size最小为16个字节，即sizeof(malloc_chunk) 3、系统可用的size为8字节对齐

说到这，或许你已经发现一个问题，如果用户申请20个字节的空间，系统会被分配24个字节，而chunk的heap控制信息占了8个字节，那留给用户使用的只剩下18个字节。如此看来，岂不是会覆盖下一个chunk的“sizeof previous chunk”区域？

为解答这个问题，我们先了解什么时候需要定位前一个chunk？只有在释放一块空间，判断前一个chunk是否空闲时才需要该动作。换而言之，当一个chunk被分配使用时，它根本不需要下一个chunk被释放来合并它，既然不需要，就利用起来吧。

从这一点讲，前一图中的“sizeof previous chunk，ifallocated”的表述是不对的，应该是“sizeif previous chunk，iffreed”。

2分箱管理

Bin的英文含义是“箱柜”，当我们谈到bin，是指某个双向链表的头字节，该链表的成员节点存放着某一特定范围size的空闲chunk，通过size，我们可以快速的定位binindex，然后遍历其指向的链表，寻找合适的chunk进行分配，或者将释放的chunk插入到链表中合适的地方。

程序定义了一个全局静态数组av_[]存放每种bin的头节点，Typedefstruct malloc_chunk *mbinptr;
Staticmbinptr av_[128*2+2]

数组类型mbinptr是一个指针，大小为4个字节，数组大小为1032个字节。这就引出一个问题，既然存放头节点，节点类型为malloc_chunk，一个节点就需要16bytes，总共有128个头节点，理应128*16=2048字节，现在av_[]才1032个字节，是复合

放下所有的头节点信息的呢？对于头节点而言，有效的是fd和bk，成员prev_size和size并没有用到，既然没用，那空间能否节约下来呢？可以的，看看dlmalloc是如何做到的。

#definebin_at(i) ((mbinptr)((char*)&(av_[2*(i)+ 2]) - 2*SIZE_SZ))

以分配16bytes为例，其箱号为 16/8＝2，于是，bin_at(2)= ((mbinptr)((char*)&(av_[6]) - 2*4))，最终bin_at(2)将&av_[4]强行转换为mbinptr指针，用这个指针访问fd和bk，得到的其实是av_[6]和av_[7]中存放的内容。

在av_[]的初始化可知，header[i].fd与header[i].bk指向&header[i]，这用于表示Bin[i]为

空。

我们来看看dlmalloc中两个特殊的分箱top和last_remainder

#definetop (bin_at(0)->fd) /* The topmost chunk */ #define last_remainder (bin_at(1)) /*remainder from last split */

Top最初被称为wildernesschunk，指向dlmalloc可用内存的最高端的边界chunk，因为在边界上，top是唯一一个可以任意扩展的块。Top比较特殊，它不受任何分箱管理，当其他分箱没有可用的chunk时才会用到top。在dlmalloc初始化刚完成时，整个受dlmalloc管理的内存就是一个chunk，top即指向这个chunk。

Last_remainder总是指向最近被分割chunk的剩下那一部分。如果malloc在分配时没有找到“精确匹配”的块，则优先去查看last_remainder是否够用。从局部性原理来讲，连续申请分配内存的代码总是趋向于有共同的生命周期，它们释放的chunk也就有很大的机会合并成一个大的chunk。

为达到快速检索分箱的目的，dlmalloc使用了一个小技巧

#definebinblocks (bin_at(0)->size)/* bitvector of nonempty blocks */

即用binblocks建立了所有分箱的一个bitmap，binblocks的bit来表示连续的4个相邻

的bin是否为空，只要有一个不为空，其对应的bit置1。Binblocks其实就是av_[1]，

一个32位数据类型，32×4＝128，正好对应128个bins。扫描时先判断binblocks的

相应位，只有当bit不为1时才会真正的去扫描对应的bin。

3其他

? Dlmalloc分配空间是通过MORECORE进行的，而MORECORE即被定义为

sbrk，因此外部需提供sbrk函数，并可通过该函数确定所使用空间的地址范围

? 具体若干函数的解释见《malloc函数解释》