内存分配器dlmalloc2.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 chunk chunk 块内分割出一部分内存以满足请求服务。否则的话，进入下一步。

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

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

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.

注意 0 x3U的二进制为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 的情况下， rsize 才有可能为真。至于为什么，可由 MIN_CHUNK_SIZE的具体定义找到原因：

#define MIN_CHUNK_SIZE\

((MCHUNK_SIZE + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)

#define MCHUNK_SIZE (sizeof(mchunk))

当SIZE_T_SIZE == 4时（对齐 8 ， 32 环境）， MIN_CHUNK_SIZE为 16 ，自然不会比剩余字节数 rsize大。其它对齐设置和环境类似推理。

4084. if (SIZE_T_SIZE != 4 && rsize

4085. set_inuse_and_pinuse(gm, p, small_index2size(i));

4086. else {

分割并将剩余字节组建一个新的空闲 chunk 块。

#define set_size_and_pinuse_of_inuse_chunk(M, p, s)\

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

mark_inuse_foot(M, p, s))

#define mark_inuse_foot(M,p,s)\

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

4087. set_size_and_pinuse_of_inuse_chunk(gm, p, nb);

新组建空闲 chunk 块结构起始地址

#define chunk_plus_offset(p, s) ((mchunkptr)(((char*)(p)) + (s)))

4088. r = chunk_plus_offset(p, nb);

设置新组建空闲 chunk 块的标记，包括本块大小、本块的前一邻接块在使用中标识以及设置 prev_foot数据为前一邻接块大小。

#define set_size_and_pinuse_of_free_chunk(p, s)\

((p)->head = (s|PINUSE_BIT), set_foot(p, s))

#define set_foot(p, s) (((mchunkptr)((char*)(p) + (s)))->prev_foot = (s))

4089. set_size_and_pinuse_of_free_chunk(r, rsize);

将新组建空闲 chunk 块替换原来的 dv chunk 块：

#define replace_dv(M, P, S) {\

size_t DVS = M->dvsize;\

if (DVS != 0) {\

mchunkptr DV = M->dv;\

assert(is_small(DVS));\

insert_small_chunk(M, DV, DVS);\

M->dvsize = S;\

M->dv = P;\

}

4090. replace_dv(gm, r, rsize);

4091. }

获取对应的实际分配内存起始地址、做 debug 检测，跳转等。

4092. mem = chunk2mem(p);

4093. check_malloced_chunk(gm, mem, nb);

4094. goto postaction;

4095. }

4096.

在smallbins中没有可满足该请求的空闲 chunk 块，则试图在 treebins中查找可满足该请求的空闲 chunk 块。函数 tmalloc_small()的分析在后面给出。

4097. else if (gm->treemap != 0 && (mem = tmalloc_small(gm, nb)) != 0) {

4098. check_malloced_chunk(gm, mem, nb);

4099. goto postaction;

4100. }

4101. }

4102. }

超过最大请求值。

4103. else if (bytes >= MAX_REQUEST)

4104. nb = MAX_SIZE_T; /* Too big to allocate. Force failure (in sys alloc) */

4105. else {

请求的内存大小在 MAX_SMALL_REQUEST 和 MAX_REQUEST 之间。

首先进行对齐处理：CHUNK_OVERHEAD为边界标记占用的空间，CHUNK_ALIGN_MASK为对齐设置值。

#define pad_request(req) \

(((req) + CHUNK_OVERHEAD + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)

4106. nb = pad_request(bytes);

试图在treebins中查找可满足该请求的空闲 chunk 块。函数 tmalloc_large()的分析在后面给出。

4107. if (gm->treemap != 0 && (mem = tmalloc_large(gm, nb)) != 0) {

4108. check_malloced_chunk(gm, mem, nb);

4109. goto postaction;

4110. }

4111. }

4112.

从 dv chunk 块内分配（注意各个执行路径）：

4113. if (nb dvsize) {

4114. size_t rsize = gm->dvsize - nb;

4115. mchunkptr p = gm->dv;

剩余空间足够大，则进行分割和组建新 chunk 块。

4116. if (rsize >= MIN_CHUNK_SIZE) { /* split dv */

4117. mchunkptr r = gm->dv = chunk_plus_offset(p, nb);

4118. gm->dvsize = rsize;

4119. set_size_and_pinuse_of_free_chunk(r, rsize);

4120. set_size_and_pinuse_of_inuse_chunk(gm, p, nb);

4121. }

4122. else { /* exhaust dv */

否则的话，直接全部分配完。

4123. size_t dvs = gm->dvsize;

4124. gm->dvsize = 0;

4125. gm->dv = 0;

4126. set_inuse_and_pinuse(gm, p, dvs);

4127. }

4128. mem = chunk2mem(p);

4129. check_malloced_chunk(gm, mem, nb);

4130. goto postaction;

4131. }

4132.

从 top chunk 块内分配（注意各个执行路径）：

4133. else if (nb topsize) { /* Split top */

4134. size_t rsize = gm->topsize -= nb;

4135. mchunkptr p = gm->top;

4136. mchunkptr r = gm->top = chunk_plus_offset(p, nb);

4137. r->head = rsize | PINUSE_BIT;

4138. set_size_and_pinuse_of_inuse_chunk(gm, p, nb);

4139. mem = chunk2mem(p);

4140. check_top_chunk(gm, gm->top);

4141. check_malloced_chunk(gm, mem, nb);

4142. goto postaction;

4143. }

4144.

最后的办法，直接从系统获取内存空间。函数sys_alloc()的分析在后面给出。

4145. mem = sys_alloc(gm, nb);

4146.

4147. postaction:

和前面的PREACTION宏对应，用于进行解锁操作：

#define POSTACTION(M) { if (use_lock(M)) RELEASE_LOCK(&(M)->mutex); }

#define RELEASE_LOCK(l) pthread_mutex_unlock(l)

4148. POSTACTION(gm);

4149. return mem;

4150. }

4151.

4152. return 0;

4153. }

5.2 函数 tmalloc_small

3693. /* allocate a small request from the best fitting chunk in a treebin */

这里的参数nb总是小于等于256，应注意这点。

3694. static void* tmalloc_small(mstate m, size_t nb) {

3695. tchunkptr t, v;

3696. size_t rsize;

3697. bindex_t i;

3698. binmap_t leastbit = least_bit(m->treemap);

3699. compute_bit2idx(leastbit, i);

3700.

3701. v = t = *treebin_at(m, i);

请求字节数目 nb ，而 tree 里的每个 chunk 块都大于等于 256 ，所以此处不会出现负数，以下某些地方类似考虑。

3702. rsize = chunksize(t) - nb;

3703.

前面曾经说过 dltree 具有一个十分有用的特性（见前面对 dltree 的分析部分），下面这个循环就是利用这个特性查找最优分配的节点（即是空闲 chunk 块大小和请求空间 nb 最接近的节点），也就是最小的 chunk 块节点。

#define leftmost_child(t) ((t)->child[0] != 0? (t)->child[0] : (t)->child[1])

同样应注意到“请求字节数目nb ，而 tree 里的每个 chunk 块都大于等于 256 ”这一点来帮助理解。

3704. while ((t = leftmost_child(t)) != 0) {

3705. size_t trem = chunksize(t) - nb;

3706. if (trem

3707. rsize = trem;

3708. v = t;

3709. }

3710. }

3711.

安全检测。

3712. if (RTCHECK(ok_address(m, v))) {

3713. mchunkptr r = chunk_plus_offset(v, nb);

3714. assert(chunksize(v) == rsize + nb);

3715. if (RTCHECK(ok_next(v, r))) {

将其拆出 dltree 。

3716. unlink_large_chunk(m, v);

剩余空间太小则直接全部分配。

3717. if (rsize

3718. set_inuse_and_pinuse(m, v, (rsize + nb));

3719. else {

否则将剩余空间组建成新的 chunk 块并替换为新的 dv chunk 块。

3720. set_size_and_pinuse_of_inuse_chunk(m, v, nb);

3721. set_size_and_pinuse_of_free_chunk(r, rsize);

3722. replace_dv(m, r, rsize);

3723. }

3724. return chunk2mem(v);

3725. }

3726. }

3727.

3728. CORRUPTION_ERROR_ACTION(m);

3729. return 0;

3730. }

5.3 函数 tmalloc_large

3620. /* allocate a large request from the best fitting chunk in a treebin */

MAX_SMALL_REQUEST 对齐值对齐值

3621. static void* tmalloc_large(mstate m, size_t nb) {

3622. tchunkptr v = 0;

设置初始值，注意 rsize 是 size_t类型变量，因此一个很小的负数事实上是一个很大的正数。

3623. size_t rsize = -nb; /* Unsigned negation */

3624. tchunkptr t;

3625. bindex_t idx;

计算 nb 字节数所对应的 dltree 树结构。

3626. compute_tree_index(nb, idx);

3627.

该 dltree 树结构不为空，即存在和 nb 字节数同在一个箱子内（不理解“同在一个箱子内”则请查看前面讲解 dltree 内容部分）的空闲 chunk 块。

3628. if ((t = *treebin_at(m, idx)) != 0) {

3629. /* Traverse tree for this bin looking for node with size == nb */

遍历 dltree 试图找到一个 size==nb 的空闲 chunk 块。

前面曾经讲到过 dltree 就是关键码只有 0 和 1 的 Trie 树。并且根据 treebins 箱的分法， 0 号箱和 1 号箱的关键码都只需 7 位长（因为其范围为 128 ，表 xxx 的第二列）， 2 号箱和 3 号箱的关键码都只需 8 位长（因为其范围为 256 ，表 xxx 的第二列），……，依次类似。

宏leftshift_for_tree_index(idx)计算的是 32 减去 idx号箱对应的关键码长度的值。

#define leftshift_for_tree_index(i) \

((i == NTREEBINS-1)? 0 : \

((SIZE_T_BITSIZE-SIZE_T_ONE) - (((i) >> 1) + TREEBIN_SHIFT - 2)))

#define NTREEBINS (32U)

#define SIZE_T_BITSIZE (sizeof(size_t)

#define TREEBIN_SHIFT (8U)

#define SIZE_T_ONE ((size_t)1)

直接来看具体的值吧，依旧是 32 位平台下：

箱号 idx = > leftshift_for_tree_index(idx)值

因此下面这个sizebits的值就是将 nb 中起关键码作用的位移到最左边的结果值。

3630. size_t sizebits = nb

3631. tchunkptr rst = 0; /* The deepest untaken right subtree */

3632. for (;;) {

3633. tchunkptr rt;

相差多大？

宏chunksize用于计算 chunk 块大小。

#define chunksize(p) ((p)->head & ~(INUSE_BITS))

3634. size_t trem = chunksize(t) - nb;

比之前选定的 chunk 块更合适？

3635. if (trem

3636. v = t;

没有比它更合适的了，就是它了。

3637. if ((rsize = trem) == 0)

3638. break;

3639. }

记录当前节点的右子树根节点。

3640. rt = t->child[1];

根据关键码值进入相应的子树。

3641. t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1];

rst 保存包含有最接近 nb 字节数大小 chunk 块的 dltree 子树。

3642. if (rt != 0 && rt != t)

3643. rst = rt;

将要继续查找的子树为空，则保存 rst 到 t ，然后跳出 for 循环。

3644. if (t == 0) {

3645. t = rst; /* set t to least subtree holding sizes > nb */

3646. break;

3647. }

3648. sizebits

3649. }

3650. }

3651.

t 和 v 都为 0 表示请求字节大小对应的 treebin 为空，因此只有在更大的箱号内查找。

3652. if (t == 0 && v == 0) { /* set t to root of next non-empty treebin */

和前面的某些代码类似，计算包含大于请求字节数目 chunk 块的所有箱号对应掩码。

3653. binmap_t leftbits = left_bits(idx2bit(idx)) & m->treemap;

存在。

3654. if (leftbits != 0) {

3655. bindex_t i;

选择最合适的分箱。

3656. binmap_t leastbit = least_bit(leftbits);

计算对应箱号。

3657. compute_bit2idx(leastbit, i);

箱子对应 dltree 根节点。

3658. t = *treebin_at(m, i);

3659. }

3660. }

3661.

执行到这已经可以确定以 t 为根节点的 dltree 中所有 chunk 块都可满足申请请求，下面这个循环只不过试图在这个 dltree 中找到一个最合适的 chunk 块来用于内存分配。最合适的 chunk 块被保存在变量 v 内。

3662. while (t != 0) { /* find smallest of tree or subtree */

3663. size_t trem = chunksize(t) - nb;

3664. if (trem

3665. rsize = trem;

3666. v = t;

3667. }

leftmost_child宏优先选取左子树，在左子树为空的情况下则选取右子树。

#define leftmost_child(t) ((t)->child[0] != 0? (t)->child[0] : (t)->child[1])

3668. t = leftmost_child(t);

3669. }

3670.

3671. /* If dv is a better fit, return 0 so malloc will use it */

前面在 treebins 中选择的 chunk 块存在（即变量 v 不为空），并且它比 dv chunk 块更适合（即选择的 chunk 块大小比 dv chunk 块大小更接近当前请求字节数目）用于内存分配以服务当前申请请求。如果 dv chunk 块更适合用来分配，则本函数将返回 0 ，因此会在返回到 dlmalloc 函数内再进行在 dv chunk 块的内存分配操作。

3672. if (v != 0 && rsize dvsize - nb)) {

下面同样是分割、组建新 chunk 块、设置边界标记等，在此不再累述。

3673. if (RTCHECK(ok_address(m, v))) { /* split */

3674. mchunkptr r = chunk_plus_offset(v, nb);

3675. assert(chunksize(v) == rsize + nb);

3676. if (RTCHECK(ok_next(v, r))) {

3677. unlink_large_chunk(m, v);

3678. if (rsize

3679. set_inuse_and_pinuse(m, v, (rsize + nb));

3680. else {

3681. set_size_and_pinuse_of_inuse_chunk(m, v, nb);

3682. set_size_and_pinuse_of_free_chunk(r, rsize);

3683. insert_chunk(m, r, rsize);

3684. }

3685. return chunk2mem(v);

3686. }

3687. }

3688. CORRUPTION_ERROR_ACTION(m);

3689. }

3690. return 0;

3691. }

3692.

5.4 函数 sys_alloc

3322. /* Get memory from system using MORECORE or MMAP */

3323. static void* sys_alloc(mstate m, size_t nb) {

3324. char* tbase = CMFAIL;

3325. size_t tsize = 0;

3326. flag_t mmap_flag = 0;

3327.