Dlmalloc详解

admin管理员组

文章数量:1531765

2024年7月12日发(作者：)

Dlmalloc详解

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

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

的版本是2.6.6。

1 边界标注

首先解释一下chunk的概念，这个概念对内存分配器而言十分重要。Chunk是大块的意

思，在dlmalloc中指包含了用户空间、heap控制信息空间以及出于对齐需求而多出来的空

间的内存空间，是dlmalloc分配释放的基本操作对象。

有两种类型的chunk，已分配的chunk和未分配的chunk，两者交错排列，占据了整个

heap空间。注意，没有相邻的两个未分配的chunk，因为在调用free释放被使用过的chunk

时，dlmalloc将合并任何相邻的空闲chunk。交错的两种chunk看起来是这样的。

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

struct malloc_chunk

{

INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */

INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */

struct malloc_chunk* fd; /* double links -- used only if free. */

struct malloc_chunk* bk;

};

成员prev _size记录了物理位置上相邻的前一个chunk的大小，利用prev_size可以找到

前一个chunk，这在调用free合并前一个空闲块时派上了用场。

成员size记录了该chunk的大小，dllmalloc在32位处理器上总是8字节对齐，故size

的低3位对size而言是无效的，dlmalloc利用这三位来记录一些信息。

#define PREV_INUSE 0x01：物理位置上相邻的前一个chunk是否被分配使用的标

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

#define IS_MMAPPED 0x02：该位为1，表示该chunk是通过mmap分配而得的，

那么释放时调用munmap；

Fd和bk则分别指向双向链表中前一个节点和后一个节点。

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

可以看出，chunk指针指向heap内部控制信息，图中head和foot区域的size of chunk

必须是一样的，如此next chunk才能根据size of chunk准确地找到chunk的位置。

另一种是已分配的chunk，其结构体和未分配的chunk结构体一样，只是不会使用fd

和bk两个成员，因为被分配后已经不需要这两个域了，其物理布局看起来像下图，chunk

指针后面8字节的偏移处，即mem区域，是返回给用户的内存指针，该chunk的heap控制

信息占据了8个字节。

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

#define request2size(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的差值，最小是0x04

2、系统可用的size最小为16个字节，即sizeof( malloc_chunk)

3、系统可用的size为8字节对齐

说到这，或许你已经发现一个问题，如果用户申请20个字节的空间，系统会被分配24

个字节，而chunk的heap控制信息占了8个字节，那留给用户使用的只剩下18个字节。如

此看来，岂不是会覆盖下一个chunk的“size of previous chunk”区域？

为解答这个问题，我们先了解什么时候需要定位前一个chunk？只有在释放一块空间，

判断前一个chunk是否空闲时才需要该动作。换而言之，当一个chunk被分配使用时，它根

本不需要下一个chunk被释放来合并它，既然不需要，就利用起来吧。

从这一点讲，前一图中的“size of previous chunk，if allocated”的表述是不对的，应该

是“size if previous chunk， if freed”。

2 分箱管理

Bin的英文含义是“箱柜”，当我们谈到bin，是指某个双向链表的头字节，该链表的成

员节点存放着某一特定范围size的空闲chunk，通过size，我们可以快速的定位bin index，

然后遍历其指向的链表，寻找合适的chunk进行分配，或者将释放的chunk插入到链表中合

适的地方。

程序定义了一个全局静态数组av_[]存放每种bin的头节点，

Typedef struct malloc_chunk *mbinptr;

Static mbinptr av_[128*2+2]

数组类型mbinptr是一个指针，大小为4个字节，数组大小为1032个字节。这就引

出一个问题，既然存放头节点，节点类型为malloc_chunk，一个节点就需要16bytes，

总共有128个头节点，理应128*16=2048字节，现在av_[]才1032个字节，是复合

放下所有的头节点信息的呢？对于头节点而言，有效的是fd和bk，成员prev_size和size

并没有用到，既然没用，那空间能否节约下来呢？可以的，看看dlmalloc是如何做到的。

#define bin_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

#define top (bin_at(0)->fd) /* The topmost chunk */

#define last_remainder (bin_at(1)) /* remainder from last split */

Top最初被称为wilderness chunk，指向dlmalloc 可用内存的最高端的边界chunk，

因为在边界上，top是唯一一个可以任意扩展的块。Top比较特殊，它不受任何分箱管理，

当其他分箱没有可用的chunk时才会用到top。在dlmalloc初始化刚完成时，整个受

dlmalloc管理的内存就是一个chunk，top即指向这个chunk。

Last_remainder 总是指向最近被分割chunk的剩下那一部分。如果malloc在分配

时没有找到“精确匹配”的块，则优先去查看last_remainder是否够用。从局部性原理

来讲，连续申请分配内存的代码总是趋向于有共同的生命周期，它们释放的chunk也就有

很大的机会合并成一个大的chunk。

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

#define binblocks (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函数解释》

本文标签： 空间使用节点分配用户