内存分配器dlmalloc 2.8.3源码浅析

通过这种分法，任一号箱的字节范围被对应在一颗树上，在查找某一大小的空闲 chunk 时则按照这种规律来进行“快速”搜索，比如应用程序 malloc (278)，则由于278 在 [256,320)范围内，因此先进入树 T1 ，接着由于 278 在 [256,288)范围内，因此由进入 T3 ，接

通过这种分法，任一号箱的字节范围被对应在一颗树上，在查找某一大小的空闲chunk时则按照这种规律来进行“快速”搜索，比如应用程序malloc( 278 )，则由于278在[256, 320)范围内，因此先进入树T1，接着由于278在[256, 288)范围内，因此由进入T3，接着进入T8，……。

之所以说这种搜索是“快速”的，因为这里的范围划为很巧妙，我们来看一下各字节范围用二进制表示的情况：

根节点T的左子树T1 [256, 320)为： [1 0000 0000 1 00xx xxxx]

而根节点T的右子树T2 [320, 384)为： [1 01xx xxxx 1 01xx xxxx]

其中的x表示为1或者0，可以看到T1和T2的管理范围很好区分，即通过判断第6bit位是否为1即可，为1表示在右子树T2范围内，为0表示在左子树T1范围内。

再来看看树T1的左子树T3和右子树T4情况：

T3管理[256, 288)为：[1 0000 0000 1 000x xxxx]

T4管理[288, 320)为：[1 0010 0000 1 001x xxxx]

可以看到T3和T4的管理范围也很好区分，即通过判断第5bit位是否为1即可，为1表示在右子树T4范围内，为0表示在左子树T3范围内。

其它的类似……。因此，我们在查找某字节在哪个范围内的树上只需要顺序的比较各bit位就可以了，对比Trie树，我们可以认为dltree是关键码只有0和1的Trie树。

4. 核心结构体malloc_state

在讲解核心结构体malloc_state之前，先来看看另外一个结构体segment。前面内容介绍的chunk块是dlmalloc内比较细粒度的管理结构，比它们更大的内存块被称之为段（segment），其结构体以及相关定义如下：

struct malloc_segment {

char* base; /* base address */

size_t size; /* allocated size */

struct malloc_segment* next; /* ptr to next segment */

flag_t sflags; /* mmap and extern flag */

};

#define is_mmapped_segment(S) ((S)->sflags & IS_MMAPPED_BIT)

#define is_extern_segment(S) ((S)->sflags & EXTERN_BIT)

typedef struct malloc_segment msegment;

typedef struct malloc_segment* msegmentptr;

英文注释很清晰，字段base表示该segment段的起始地址，size表示该segment段的大小，sflags是一个标记字段（两个标记，一个用于标记该segment段是否为通过mmap申请，一个用于标记该segment段是否已经分配），而字段next用于指向下一个segment段，从而形成单链表结构。记录该单链表表头的变量同样定义在结构体malloc_state内，如下：

msegment seg;

这是个结构体变量，而不是结构体指针变量，这一点需要注意。刚才已经提到多个segment段是通过next形成单链表结构来组织管理的，dlmalloc也没有对它们做其它特别的索引处理，因此查找某一个segment段需要在该单链表内线性扫描查找，不过大多数情况下，segment段应该是非常少的，所以并不会造成多大的性能损失。

在dlmalloc中对malloc_chunk、malloc_tree_chunk、malloc_segment给出了一个统一的管理结构体，那就是前面反复提到的结构体malloc_state，其具体定义如下：

struct malloc_state {

binmap_t smallmap;

binmap_t treemap;

size_t dvsize;

size_t topsize;

char* least_addr;

mchunkptr dv;

mchunkptr top;

size_t trim_check;

size_t magic;

mchunkptr smallbins[(NSMALLBINS+1)*2];

tbinptr treebins[NTREEBINS];

size_t footprint;

size_t max_footprint;

flag_t mflags;

#if USE_LOCKS

MLOCK_T mutex; /* locate lock among fields that rarely change */

#endif /* USE_LOCKS */

msegment seg;

};

typedef struct malloc_state* mstate;

该结构体中的一些字段在前面已经详细分析过了，比如smallbins、treebins和seg。其它几个字段的作用，现在也一一说明如下：

smallmap是一个位图，用于标记对应的smallbins链表是否为空，1表示非空，0表示空。

treemap也是一个位图，用于标记对应的treebins树是否为空，1表示非空，0表示空。

dv和dvsize指向一个chunk块（dvsize记录该chunk块大小），该chunk块具有一个特点就是：它是从最近的一次被用来服务小于256字节内存申请的chunk块中分裂出来的chunk块。比较拗口，简单点说就是为了更有效的利用程序的局部性原理，即对于应用程序的一连续小块内存申请请求，dlmalloc总是尽量从同一个chunk块获取空闲内存来满足这些请求，因此分配给应用程序的内存都是在挨得比较近的地址空间内，从局部性原理可以知道，这种内存分配方式在一定程度上可以提高应用程序的性能。当然，这种分配方式只是尽量，如果有其它更好的chunk块选择（比如刚好有某个chunk大小就是应用程序申请的内存大小）则会选择其它chunk块来分配内存，这在后面具体代码的分析过程中会看到。

top 和topsize也是指向一个chunk块（topsize记录该chunk块大小），该chunk块比较特殊，它不被任何分箱管理（即既不位于smallbins，也不位于treebins。），它位于当前活跃segment段（即最近被用来分配空间服务应用程序内存请求的）的最顶端，在最顶端的好处就是它可以*伸缩（通过库函数sbrk()），因此大小可变。在segment段中间的那些chunk块大小一般不可变，但是有两种情况会变动，一是分配出去一部分内存用于满足应用程序申请，此时chunk块变小；二是，当应用程序释放内存（free()）时，dlmalloc将检查该释放内存是否可与前后空闲内存合并，此时就可能导致chunk块变大。

字段least_addr用来记录可获取的最小内存地址，直白点说就是相当于一个边界点，用于做越界安全检查。

字段trim_check用来记录一个临界值。我们知道应用程序free内存空间时，该释放的内存空间并没有直接返还给系统而是被送回dlmalloc中进行管理。当释放的内存空间越来越多时，dlmalloc中管理的空闲chunk块也会变得越来越大（即由于多个连续空闲块合并的结果），对于一个segment段中间的空闲chunk块没有办法释放给系统（因为释放中间的空闲chunk块会将segment段切断），但是对于顶端（top）的chunk块则可以*伸缩的，缩小顶端的chunk块也就是将空闲内存真正的返还给系统。那什么时候需要缩小顶端的chunk块呢？字段trim_check就是记录的这个临界值。当顶端的chunk块大小大于字段trim_check记录的值时就要进行缩减操作了，具体情况在后面源码分析时再看。

其它几个字段不是我们主要关注的内容且比较简单，比如字段magic用于做确认检查；字段mflags用于标记一些属性，比如启用mmap、禁用连续分配，……；字段footprint记录从系统获得的字节数目；字段max_footprint记录从系统获得的最大字节数目；字段mutex用于多线程互斥锁等等，在此就不做过多介绍了。

dlmalloc定义了一个结构体malloc_state的全局变量，相关代码如下：

static struct malloc_state _gm_;

#define gm (&_gm_)

#define is_global(M) ((M) == &_gm_)

#define is_initialized(M) ((M)->top != 0)

变量_gm_是结构体malloc_state的静态全局变量，因此当使用dlmalloc的应用程序被加载运行时，变量_gm_自动初始化为全0，这对于dlmalloc是十分重要的（例如_gm_结构体字段seg也为全0）；另外还有一个gm宏，其值被定义为_gm_的地址，因此可以当指针一样使用它。其它两个宏is_global和is_initialized很明朗，无需多说。

总结起来，可以看到dlmalloc利用静态全局变量_gm_管理着segment段，小块空闲chunk块、大块空闲chunk块以及其它相关信息，所有的内存分配和释放都是围绕着_gm_进行的。

5. 内存分配相关函数

本节主要对dlmalloc内存分配器的核心函数dlmalloc()以及相关函数进行讲解，函数dlmalloc用于服务应用程序的内存空间申请请求，因此也是我们平常使用得最多的两个函数（另外一个dlfree()）之一。下面我们先来直接看源码并同时进行分析。（下面给出的源码都已标号，标号为源文件malloc-2.8.3.c内的实际行号，未标号的行都为我给出的分析注解内容。）

5.1 函数dlmalloc

4023. void* dlmalloc(size_t bytes) {

下面的英文注释给出了dlmalloc选择空闲内存来服务应用程序请求的分配策略：

对于小块内存请求（即小于256字节减去块头开销的内存申请请求）：

1. 优先选择大小和请求大小刚好一致的空闲chunk块（即在请求大小对应的箱号内找到空闲chunk块），这么做的好处很明显，那就是这种分配不用分割chunk块就可以满足请求服务。如果大小刚好一致的空闲chunk块不存在（即在请求大小对应的箱号内为空）则选择大小比较一致的空闲chunk块，这种比较一致是指空闲chunk块大小和请求大小相差一个箱号（即相差8字节），如果在比请求大小对应的箱号大一的箱子内找到空闲chunk块也可以拿来分配以满足请求服务，否则进入下一步。

2. 如果dv chunkchunk块内分割出一部分内存以满足请求服务。否则的话，进入下一步。

3. 第1步中查找空闲chunk块只在请求大小对应的和比其大一的两个箱号内查找，这一步就不做这些限制了，只要smallbins和treebins管理的chunk空闲链/树内有满足请求（即需要比请求字节数目大）的chunk空闲块存在（当然也是选择大小和请求字节数目最接近的chunk空闲块），则分割出一部分内存以满足请求服务，同时将剩余部分作为新的dv chunk块。否则的话，进入下一步。

4. 如果top chunkchunk块内分割出一部分内存以满足请求服务。否则的话，进入下一步。

5. dlmalloc从系统获取内存空间。

对于大块内存请求（对于大块内存都是由treebins管理的）：

1. 在treebins管理的空闲chunk块中找一个大小最接近请求字节数目的chunk块（假设为chunk块A），如果chunk块A比dv chunk块更合适（即如果dv chunk块本身就太小而无法满足请求服务或者太大以至于chunk块A的大小比dv chunk块大小更接近请求字节数目，我们应注意到dlmalloc总是选择从大小和当前请求字节数目最接近的chunk块中分配内存来服务请求，也就是所谓的最佳适应算法。这些常见内存分配算法比如首次适应算法、循环首次适应算法、最差适应算法等在操作系统原理课程上应该有讲解过。）则使用它。否则的话，进入下一步。

2. 如果dv chunk块足够大则使用它以满足请求服务。否则的话，进入下一步。

3. 如果top chunk块足够大则使用它以满足请求服务。否则的话，进入下一步。

4. 如果请求字节数目超过了预设的mmap调用界限则直接mmap一块内存来满足请求服务。否则的话，进入下一步。

5. dlmalloc从系统获取内存空间。

上面这些步骤的跳转使用了goto语法，以保证所有执行路径的最后都能够执行宏语句POSTACTION。

4024. /*

4025. Basic algorithm:

4026. If a small request (

4027. 1. If one exists, use a remainderless chunk in associated smallbin.

4028. (Remainderless means that there are too few excess bytes to

4029. represent as a chunk.)

4030. 2. If it is big enough, use the dv chunk, which is normally the

4031. chunk adjacent to the one used for the most recent small request.

4032. 3. If one exists, split the smallest available chunk in a bin,

4033. saving remainder in dv.

4034. 4. If it is big enough, use the top chunk.

4035. 5. If available, get memory from system and use it

4036. Otherwise, for a large request:

4037. 1. Find the smallest available binned chunk that fits, and use it

4038. if it is better fitting than dv chunk, splitting if necessary.

4039. 2. If better fitting than any binned chunk, use the dv chunk.

4040. 3. If it is big enough, use the top chunk.

4041. 4. If request size >= mmap threshold, try to directly mmap this chunk.

4042. 5. If available, get memory from system and use it

4043.

4044. The ugly goto's here ensure that postaction occurs along all paths.

4045. */

PREACTION是一个宏，作用和后面的POSTACTION宏相对，用于进行互斥锁定。我们知道“互斥锁是用来保证一段时间内只有一个线程在执行一段代码”，而下面的这段代码在多线程情形下恰好需要这一保证，因此有这一宏的存在。具体来看：

#define PREACTION(M) ((GLOBALLY_INITIALIZE() || use_lock(M))? ACQUIRE_LOCK(&(M)->mutex) : 0)

#define use_lock(M) ((M)->mflags & USE_LOCK_BIT)

#define ACQUIRE_LOCK(l) pthread_mutex_lock(l)

未初始化（GLOBALLY_INITIALIZE()）或者的确需要锁定（use_lock(M)）则调用函数pthread_mutex_lock()（Unix/Linux环境，Windows环境类似，以下同）对互斥锁上锁。

4046.

4047. if (!PREACTION(gm)) {

4048. void* mem;

4049. size_t nb;

MAX_SMALL_REQUEST被定义为小块内存请求的最大值：

#define MAX_SMALL_REQUEST (MAX_SMALL_SIZE - CHUNK_ALIGN_MASK - CHUNK_OVERHEAD)

根据对齐和其它（比如是否具有foot）等设置，该值具体数据稍有不同（比如为247或248等），但都比256小，在这里我们简单的认定它为256。

4050. if (bytes

4051. bindex_t idx;

4052. binmap_t smallbits;

对请求内存数目进行对齐处理，另外如果请求内存数目小于最小请求值（MIN_REQUEST）则取最小值chunk块大小（16字节）。

4053. nb = (bytes

small_index是一个宏，用于根据请求字节数目计算对应大小的空闲chunk块所在的箱号：

#define SMALLBIN_SHIFT (3U)

#define small_index(s) ((s) >> SMALLBIN_SHIFT)

4054. idx = small_index(nb);

将箱号的位图标记移到最右边位。

4055. smallbits = gm->smallmap >> idx;

4056.

注意0x3U的二进制为0000 0011（只给出了低8位），因此如果它和smallbits进行位与为真，则smallbits的低2位有三种情况：

第一种情况：1 1

第二种情况：0 1

第三种情况：1 0

为1表示该对应箱号内存在对应大小的空闲chunk块，前两种情况都表示存在大小刚好和请求大小一致的空闲chunk块；而第三种情况表示不存在大小刚好和请求大小一致的空闲chunk块，但是存在大小和请求大小只相差一个箱号的空闲chunk块。

4057. if ((smallbits & 0x3U) != 0) { /* Remainderless fit to a smallbin. */

4058. mchunkptr b, p;

在第三种情况（1 0）时需要将箱号（idx）加1，下面这行代码将这三种情况都无区别的处理了，即在第一二种情况时箱号（idx）并不会加1，很精巧的代码！

4059. idx += ~smallbits & 1; /* Uses next bin if idx empty */

找到对应箱号的chunk块链头节点：

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

4060. b = smallbin_at(gm, idx);

4061. p = b->fd;

4062. assert(chunksize(p) == small_index2size(idx));

将第一块空闲chunk块（假设为chunk块A）从链表中拆出，用于分配。环形双向链表的头节点拆除就不多讲了。

4063. unlink_first_small_chunk(gm, b, p, idx);

本块chunk块A被用于分配使用，因此需要修改边界标记：

宏small_index2size用于根据箱号计算对应箱内空闲chunk块字节数目：

#define small_index2size(i) ((i)

#define SMALLBIN_SHIFT (3U)

宏set_inuse_and_pinuse根据设置（FOOTERS是否存在，即是否有footers），下面给出有footers的情况（没有footers的情况相对简单）下set_inuse_and_pinuse宏的定义：

#define set_inuse_and_pinuse(M,p,s)\

((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\

(((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT),\

mark_inuse_foot(M,p,s))

该宏第二行用于标记本chunk块A在使用中（即将被分配使用以满足请求）并且前一块也在使用中（这是显然的，因为有合并的操作，所以不会存在两个连续的空闲块）。第三行是修改邻接的下一chunk块的PINUSE_BIT标记，表明邻接的下一chunk块的前一邻接chunk块（即当前正要被分配使用的chunk块A）在使用中。第四行修改footers标记。前面曾经说过prev_foot用于记录前一邻接chunk块的大小，那是在前一邻接chunk块空闲情况，如果前一邻接chunk块处于使用状况，prev_foot则用于记录它们所在的malloc_state信息，如下：

/* Set foot of inuse chunk to be xor of mstate and seed */

#define mark_inuse_foot(M,p,s)\

(((mchunkptr)((char*)(p) + (s)))->prev_foot = ((size_t)(M) ^ mparams.magic))

mparams.magic起安全检测作用。

4064. set_inuse_and_pinuse(gm, p, small_index2size(idx));

宏chunk2mem和mem2chunk用于在chunk块头地址和实际可用内存起始地址之间进行相互转换，这点根据chunk块结构体malloc_chunk和malloc_tree_chunk的定义很容易理解：

/* conversion from malloc headers to user pointers, and back */

#define chunk2mem(p) ((void*)((char*)(p) + TWO_SIZE_T_SIZES))

#define mem2chunk(mem) ((mchunkptr)((char*)(mem) - TWO_SIZE_T_SIZES))

4065. mem = chunk2mem(p);

debug编译时用于做安全检测。

4066. check_malloced_chunk(gm, mem, nb);

内存申请请求得以满足，跳到最后执行解除互斥锁操作，返回分配的内存起始地址。

就算不考虑块头、对齐等开销，malloc分配的内存也可能会比应用程序实际应分配内存多，即前面的第三种情况：1 0，这种情况时，dlmalloc分配的内存将多出8个字节。由于8个字节不足以组成一个chunk块，因此也就没有必要进行分割，而是全部分配给当前申请请求，下面还可以看到这种情况。

4067. goto postaction;

4068. }

4069.

dv chunk块不够大，因此在所有空闲chunk块中查找可以满足该请求的chunk块。

4070. else if (nb > gm->dvsize) {

在smallbins中存在可满足该请求的空闲chunk块。

4071. if (smallbits != 0) { /* Use chunk in next nonempty smallbin */

4072. mchunkptr b, p, r;

4073. size_t rsize;

4074. bindex_t i;

下面两个宏用于位操作，我们来看看：

idx2bit宏取第i位为1，其它位都为0的掩码，举个例子：idx2bit(3) 为 “0000 1000”（只显示8位，下同）。

#define idx2bit(i) ((binmap_t)(1)

left_bits宏取x中值为1的最小bit位的左边(不包括值为1的该最小bit位) 所有位都为1，其它位都为0的掩码，举个例子：left_bits(6)为“1111 1100”，因为6的二进制位“0000 0110”，值为1的最小bit位为第1位，因此结果为第1位左边(不包括第1位) 所有位都为1，其它位都为0的掩码。

#define left_bits(x) ((x

leftbits为所有可满足当前申请请求的箱号。

4075. binmap_t leftbits = (smallbits

选择最佳适合的箱号对应的bitmap位码，即获取值为1的最小bit位：x中值为1的最小bit位为1，其它位都为0的掩码。

#define least_bit(x) ((x) & -(x))

4076. binmap_t leastbit = least_bit(leftbits);

compute_bit2idx 是一个宏，它使得i 取leastbit的二进制中位为1的最小位置索引，从0开始。举个例子：

leastbit为0000 0100，则compute_bit2idx(leastbit, i)的结果是使得i的值为2。

因此作用是根据bitmap位码计算对应的箱号。

4077. compute_bit2idx(leastbit, i);

获取箱号对应的链表头节点。

4078. b = smallbin_at(gm, i);

4079. p = b->fd;

4080. assert(chunksize(p) == small_index2size(i));

拆出链表的第一个空闲chunk块以进行内存分配。

4081. unlink_first_small_chunk(gm, b, p, i);

计算分割该chunk块（用于服务内存申请请求）后，该chunk块剩余的字节数。

4082. rsize = small_index2size(i) - nb;

4083. /* Fit here cannot be remainderless if 4byte sizes */

剩余的字节数太小无法组建一个新的空闲块，因此直接全部分配。

这里的判断利用了短路运算符的特性，我们应注意到当前待分配的chunk块大小和申请请求字节大小至少相差两个箱号的字节数目（即剩余字节数至少有16字节），当SIZE_T_SIZE == 4时，是不可能出现rsize SIZE_T_SIZE!=4