dlmalloc浅析¶

version 1.0 by Werther Zhang @ 2014.03.15 Write done @WizNote
Version 1.1 by Werther Zhang @ 2014.03.20 Export to @Word
Version 1.2 by Werther Zhang @ 2016.07.02 Move to @leanote

来源: https://pengzhangdev.github.io/dlmalloc%E6%B5%85%E6%9E%90/

dlmalloc介绍¶

dlmalloc在某些程度上说，是最好的内存管理工具之一。它是由Doug Lea 在1987年开始编写，所以大部分人会称呼它为Doug Lea's Malloc，简称dlmalloc。

算法概览¶

dlmalloc 根据内存粒度的大小分别使用chunk和segment进行管理。Segment是通过sbrk分配，类似进程的数据段，属于极少遇到的情况。Dlmalloc中大量存在的内存块是chunk。Chunk的结构如下。

被用户使用的chunk结构看起来像下面这样（非精确图）：

而未被使用的chunk看起来如下（非精确图）：

在虚拟地址上，dlmalloc会保证空闲的内存块存在“孤岛效应”，也就是说，任一块空闲内存块的前后必定是被使用的内存块。因为在free或者其他任何时候，dlmalloc总是会合并空闲的内存块。
对于chunk，根据其大小，分为大内存和小内存。小内存由32个双向链表通过分箱（每一个箱子对应一个大小，每个箱子中存放一个双向链表）进行管理，而大内存统一由bitwise tries树通过分箱（每一个箱子对应一个内存范围，每一个箱子中存放一棵树，每一棵树中若有等大小的内存，由双向链表管理）进行管理。
每一个chunk的大小必须为8byte的整数倍。所以在’size of chunk’ 域的低三位存放了该chunk属性的标志位。
P (PINUSE_BIT) 位, 保存在内存块大小(一般是双字节的倍数)的未使用的低位, 是一个表示前一个内存块是否被使用的bit位.如果这个bit位被清理了,那么在当前内存块之前的一个字大小数据保存着前一个内存块的大小,用于寻找前一个内存块.而第一个内存块这个bit位总是被置上的,防止访问不存在的内存区域.如果某个内存块的 pinuse被设置了,你就无法决定上一个内存块的大小,并且如果你真的尝试这么做了,有可能内存访问出错.
C (CINUSE_BIT) bit位, 保存在内存块的第二低的bit位,冗余地记录着当前块是否被使用了(除非当前内存块是被映射的).这个冗余信息用于在free和realloc操作时的检查,并且减少在执行free和合并内存块时的间接操作.
任何新分配的内存块必须都设置了cinuse和pinuse.这意味着,任何分配了的内存块的边界要么是一个先前分配并且仍然在使用(in-use)的内存块,要么是它自己的大内存区域(segment)的地址.这样确保所有的内存申请(allocations)都是从任何能找到的内存块的“最低”部分获取.进一步地说,不可能存在一个空闲内存块在物理上紧邻着另一个空闲内存块,所以每一个空闲内存块被证实在使用 (inuse)的内存块或者内存尾部之前和之后.
注意: 当前块的 ’foot’实际上代表着下一个内存块的prev_foot.这使对齐等操作处理变得容易但会使人在扩展或维护这份代码时感到困惑.
以下是对特殊的内存块的说明:

特殊的内存块’top’是最顶上的可用内存块(i.e., 紧邻着可用内存的边界). 这块内存块会被特殊对待. Top 内存块不会被包含在任何的内存分类箱里, 只有在没有任何其他内存块可使用时,才被使用,并且在它非常大时(查看 M_TRIM_THRESHOLD) 会被释放一部分回系统.在实际上,top内存块一般被认为是比其他所有的内存块都大.Top内存块从来不会更新它的尾部数据区域因为根本没有内存块会在索引上紧跟其后.但是,空间还是会分配给它 (TOP_FOOT_SIZE) 用户做内存块的拆分和合并,当空间需要扩展时.
dv chunk 是保存了最近被使用并切割过的内存块，保存在全局的gm中。它不归属到双向链表或者树中管理。但当它被替换时，也会加入内存管理中。
Bitwise trie 树, 实际上是结合了二叉树和trie树(又叫字典树, 前缀数).二叉树只有左右子树. Trie树是一种有序树,用于保存关联数组,类似 hash table, 有key 和 value 结构. 如下图.key 实际上就是到达value的路径.而bitwise trie, 它是将 key设置为0/1, 所以, 是一棵二叉树.在dlmalloc的bitwise trie tree中, 0 代表进入左子树, 1 代表进入右子树. 而key的长度对应路径的深度.参考 [treebins和树管理图解] 的图,假设我们现在要查找的是512对应的结点, 则将520对应二进制码是1000001000, 对应的箱子号是2号,则其表示的内存范围为256, 特征码长度为8, 也就是00001000.考虑到, 所有请求大小为8byte倍数,所以, 实际特征码为00001, 树深为5, 前4层为左子树,第五层为右子树.但刚才描述的是trie树和 bitwise trie 树, 不是dlmalloc使用的树.

非MSPACE代码逻辑分析¶

struct malloc_chunk {
size_t               prev_foot;  /* 如果前一个内存块空闲,表示前一个内存块的大小 */
size_t               head;       /* 大小和inuse bit位*/
struct malloc_chunk* fd;         /* 如果是空闲内存块,指向双向链表*/
struct malloc_chunk* bk;
};

typedef struct malloc_chunk  mchunk;
typedef struct malloc_chunk* mchunkptr;
typedef struct malloc_chunk* sbinptr;  /* 内存块分类箱的类型 */

head 域中变量的说明:¶

PINUSE_BIT 在前一个相邻的内存块被使用时,这个标志位被置上. CINUSE_BIT 在当前内存块被使用时,这个标志位被置上. FLAG4_BIT 在当前版本的dlmalloc中未被使用

如何做到在head中既存放块大小又存放标志位的呢?首先提到一点是,所有的块的大小都是按最少8bit对齐的,换句话说,表示大小的数字,低3位必定为 0,所以就有效地利用了低3位存放标志位.所以,获取chunk的大小用下面的宏,将head的低三位清成0,取出.

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

下面介绍下dlmalloc维护的一个全局数据结构.

2579 struct malloc_state { 
2580   binmap_t   smallmap;  // 32bit, 小内存箱子的位图.
2581   binmap_t   treemap;    // 32bit, 大内存箱子的位图
2582   size_t     dvsize;           //  dv chunk 的大小
2583   size_t     topsize;          //  top chunk的大小
2584   char*      least_addr;    //  dlmalloc管理的内存的最小地址,也就是最小的segment 基地址.
2585   mchunkptr  dv;            // dv chunk. 最近被分割使用的chunk
2586   mchunkptr  top;           // top chunk. 顶部,靠近有效内存的chunk,详见总结图.
2587   size_t     trim_check;    // 检查top chunk大小是否超的函数.
2588   size_t     release_checks;  
2589   size_t     magic; 
2590   mchunkptr  smallbins[(NSMALLBINS+1)*2];   // 32个链表头
2591   tbinptr    treebins[NTREEBINS];           // 32棵树
2592   size_t     footprint; 
2593   size_t     max_footprint; 
2594   size_t     footprint_limit; /* zero means no limit */ 
2595   flag_t     mflags; 
2596 #if USE_LOCKS 
2597   MLOCK_T    mutex;     /* locate lock among fields that rarely change */ 
2598 #endif /* USE_LOCKS */ 
2599   msegment   seg;        //  segment链表.
2600   void*      extp;      /* Unused but available for extensions */ 
2601   size_t     exts; 
2602 };

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

这里会有个疑问,理论上, 32个链表头,我们会使用struct malloc_chunk smallbins[NSMALLBINS]; 但这里不使用的原因是, 对于链表头而言, malloc_chunk的 prev_foot和head两个域是没有被使用的,实际需要的大小是2个指针大小.所以,dlmalloc使用了覆盖的方法. 前一个 malloc_state 的fb/bk 踩了后一个的 malloc_state的 prev_foot/head.所以大小应该为 32 * 8 + 8, 也就是33 * 2 个指针大小.

被覆盖的数据结构¶

当内存块未被使用时,他们作为列表或者树的节点.
小内存(“Small”) 块存储在环形双向链表中,看起来像如下这样.

而大的内存块使用内存块大小为关键字的bitwise digital tree (又叫aka tree).因为malloc_tree_trunks只是用于大小大于256bytes的空闲内存块,他们的大小不会受到用户申请的内存大小的限制.每一个节点的结构看起来像如下这样.

每一棵树都拥有唯一的内存块大小.而具有同样大小的内存块会被安排在双向链表里,与最老的内存块一起(指,以FIFO的规则,下一个要被使用的内存块).如果一个具有同样大小的内存块被插入,它就会用类似小内存的fb/bk的指针一样的方式,从原有的节点移除.

每一棵树包含大小为2的乘方范围的内存块(最小为0x100 <= x < 0x180),在树的每一层都会被分成一半,即小的一半 (0x100 <= x < 0x140)作为左子树,大的一半作为右子树(0x140 <= x < 0x180).

通过使用这种规则,每一个节点的左子树包含的内存块大小都小雨其右子树.

Smallbins和双向链表管理小内存图解。

Treebins和树管理大内存的图解：

dlmalloc代码分析¶

dlmalloc 对小内存分配有如下5个规则(按优先级顺序)：

如果与请求内存大小匹配的箱子存在空闲,则使用当前箱子，否则使用临近的箱子。在能不分割内存的情况下尽量不分割内存。
如果dv chunk足够大，那么使用dv chunk。 dv chunk是指最近一次小内存申请时使用的内存块。这个规则是，尽量保证分配的内存连续。
在smallbin和treebin中寻找可以使用的内存块，并分割。将剩下的内存块保存到dv chunk中。
如果top chunk 足够大，则使用top chunk
如果请求内存实在太大，则使用系统分配内存。

大内存分配的规则：

在treebin中找到最适合的最小内存，如果它比dv chunk的更合适，就使用它，如果有需要就分割它。
如果dv chunk 比其他所有的更合适，使用dv chunk。
如果top 足够大，使用top chunk。
如果请求的大小 >= mmap threshold, 则使用系统的mmap。
直接从系统分配内存并使用。

小内存规则一¶

4597     if (bytes <= MAX_SMALL_REQUEST) {

// MAX_SMALL_REQUEST 实现
2577 #define MAX_SMALL_REQUEST (MAX_SMALL_SIZE - CHUNK_ALIGN_MASK - CHUNK_OVERHEAD)

这里bytes为申请的内存大小, MAX_SMALL_REQUEST就是之前提到过的最大的小内存块的大小,就是256byte,即,256byte以下的所有内存都是在双向链表中匹配.

4600       nb = (bytes < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(bytes);

2225 #define MIN_REQUEST         (MIN_CHUNK_SIZE - CHUNK_OVERHEAD - SIZE_T_ONE)

2228 #define pad_request(req) \
2229    (((req) + CHUNK_OVERHEAD + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)

这里nb就是加上协议数据后的实际dlmalloc会分配的内存块大小.前文笔者提到过,小内存块的最小值为8byte,所以,不论申请的内存多小,都使用最小值.

4601      idx = small_index(nb);

2572 #define SMALLBIN_SHIFT    (3U)

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

这里idx得到的是该内存块对应的smallbin箱子的箱号.前文在提到head时,提到过,小内存块的大小为8byte的倍数,所以,右移3位来定位对应箱子的箱号.

4602       smallbits = gm->smallmap >> idx;

smallmap 是各个箱子的位图,32bit,对应32个箱子,每一位为1表示该箱号中有对应大小的内存块,为0则表示没有.该行代码是把对应箱号的比特位移到最右侧.

4604       if ((smallbits & 0x3U) != 0) {
4605         mchunkptr b, p;
4606         idx += ~smallbits & 1;       /* Uses next bin if idx empty */
4607         b = smallbin_at(gm, idx);

这里 0x3U 低8位就是 0000 0011. 所以,smallbits&0x3U 为真的条件如下:(上文提到,smallbits的最右位表示idx箱号是否有空闲块)

低2位为 11. idx有空闲块,比idx大1箱号的有空闲块.
低2位为 10. idx无空闲块,比idx大1箱号的有空闲块.
低2位为 01. idx有空闲块,比idx大1箱号的无空闲块.

4606行是在重新定位到真正有空闲块的箱号. ~smallbits & 1 在当前箱子为0的情况下,值为1;当前箱子为1的情况下,值为0.所以是有限是用正好满足大小的箱子.

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

i 就是 idx, 而M则是gm(需要在上文预先描述gm结构体成员作用).smallbins(需在上文描述)就是双向链表数组,也就是对应箱号内部的空闲块链表的首地址.

值得高兴的是,我们拿到链表了,接下来就是取出空闲块,和一些标志位的处理了.

4608        p = b->fd;
4609        assert(chunksize(p) == small_index2size(idx));
4610        unlink_first_small_chunk(gm, b, p, idx);
4611        set_inuse_and_pinuse(gm, p, small_index2size(idx));
4612        mem = chunk2mem(p);
4613        check_malloced_chunk(gm, mem, nb);
4614        goto postaction;

fd域是前一个链表节点.而B是表头, 也就是说,我们取链表的第一个元素,取到我们需要的内存块地址.这个assert其实就是确认下,当前的箱号的内存块大小跟当前内存块的大小是否匹配.

3629#define unlink_first_small_chunk(M, B, P, I) {\
3630  mchunkptr F = P->fd;\
3631  assert(P != B);\
3632  assert(P != F);\
3633  assert(chunksize(P) == small_index2size(I));\
3634  if (B == F) {\
3635    clear_smallmap(M, I);\
3636  }\
3637  else if (RTCHECK(ok_address(M, F) && F->bk == P)) {\
3638    F->bk = B;\
3639    B->fd = F;\
3640  }\
3641  else {\
3642    CORRUPTION_ERROR_ACTION(M);\
3643  }\
3644}

2921#define clear_smallmap(M,i)     ((M)->smallmap &= ~idx2bit(i))

这里 B P F的关系是 F -> P -> B , 所以,理论上, P 不等于F 也不等于B,如果相等,就意味着是空链表(只有表头).而如果B == F, 意味着该链表中只有一个空闲内存块.取出该内存块之后,咱们要把该箱子标记为空(3635, 2921).当然, 更多的情况是从链表中移除节点P.

// 4611 行函数实现

3058#define set_inuse_and_pinuse(M,p,s)\
3059  ((p)->head = (s|PINUSE_BIT|CINUSE_BIT),\
3060  ((mchunkptr)(((char*)(p)) + (s)))->head |= PINUSE_BIT)

这就是在P 的head中置上CINUSE位和P 的下一块内存的head中设置上PINUSE位.

最后mem = chunk2mem(p); 就是取出传递个用户的有效内存地址,. check_malloced_chunk(gm, mem, nb); 是调试用的,检查该分配的内存块的各个属性是否正常.

到此,小内存的,正好符合或正好临近箱子有空闲块的逻辑分析完成,咱们拿到了需要的内存.

小内存规则三¶

下面,是上述情况不满足,也就是当前内存请求对应的箱号idx的smallbits低2位为 00 ,也就是说,没有空闲块.

4617      else if (nb > gm->dvsize) {
4618        if (smallbits != 0) {

(dvsize需要在gm的分析中描述掉) smallbits != 0 意味着,在比请求的内存块大的箱子中,总有空闲块存在.所以接下来的目的是找到最小的空闲块.

4622          binmap_t leftbits = (smallbits << idx) & left_bits(idx2bit(idx));
4623          binmap_t leastbit = least_bit(leftbits);
4624          compute_bit2idx(leastbit, i);

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

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

2932#define left_bits(x)         ((x<<1) | -(x<<1))

4622 行位与的右操作数是一个32bit的数，该数的低（idx+1）位为0,其余位为1;左操作数就是对应低idx位为0,同时代码逻辑走到这里，我们可以确定，低（idx+2）为0。 least_bit 的功能是，保留leftbits中从右往左的第一个为1的位，其余位为0. 则该leastbit对应的就是符合请求的最小内存块的位图。compute_bit2idx 是将leastit位图转换成箱号。这里 i 就是获取到的箱号。

4625          b = smallbin_at(gm, i);
4626          p = b->fd;
4627          assert(chunksize(p) == small_index2size(i));
4628          unlink_first_small_chunk(gm, b, p, i);

拿到箱号之后，这块的逻辑与上文规则一的逻辑一样。

4629          rsize = small_index2size(i) - nb;

取出当前箱子的内存块大小，减去用户请求的大小，剩下的就是剩余的内存块，这个剩余内存块会放到dv chunk中。

4631          if (SIZE_T_SIZE != 4 && rsize < MIN_CHUNK_SIZE)
4632            set_inuse_and_pinuse(gm, p, small_index2size(i));
4633          else {
4634            set_size_and_pinuse_of_inuse_chunk(gm, p, nb);
4635            r = chunk_plus_offset(p, nb);
4636            set_size_and_pinuse_of_free_chunk(r, rsize);
4637            replace_dv(gm, r, rsize);
4638          }

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

2284#define set_size_and_pinuse_of_free_chunk(p, s)\
2285  ((p)->head = (s|PINUSE_BIT), set_foot(p, s))

3063#define set_size_and_pinuse_of_inuse_chunk(M, p, s)\
3064  ((p)->head = (s|PINUSE_BIT|CINUSE_BIT))

3584#define insert_small_chunk(M, P, S) {\
3585  bindex_t I  = small_index(S);\
3586  mchunkptr B = smallbin_at(M, I);\
3587  mchunkptr F = B;\
3588  assert(S >= MIN_CHUNK_SIZE);\
3589  if (!smallmap_is_marked(M, I))\
        // 如果是对应箱号原状态为0,则置1.
3590    mark_smallmap(M, I);\
3591  else if (RTCHECK(ok_address(M, B->fd)))\
3592    F = B->fd;\
3593  else {\
3594    CORRUPTION_ERROR_ACTION(M);\
3595  }\
3596  B->fd = P;\
3597  F->bk = P;\
3598  P->fd = F;\
3599  P->bk = B;\
3600}

3648#define replace_dv(M, P, S) {\
3649  size_t DVS = M->dvsize;\
3650  assert(is_small(DVS));\
3651  if (DVS != 0) {\
3652    mchunkptr DV = M->dv;\
3653    insert_small_chunk(M, DV, DVS);\
3654  }\
3655  M->dvsize = S;\
3656  M->dv = P;\
3657}

如果剩余大小rsize小于MIN_CHUNK_SIZE，咱们直接将所有内存分配给用户。否则则分割内存，并将剩余的内存块转成mchunkptr，即 r。我们然后，r相当于一个新的内存块，我们设置其head属性（size，PINUSE_BIT，CINUSE_BIT）。 replace_dv 中，我们先获得dv size，确认是小内存块。然后，就是把dv内存块插入到对应的箱号里。就跟之前，根据大小获取到对应箱号的链表头的逻辑一样，只是这里是将内存块插入双向链表的第一个位置。 ok，插入完成后，咱们把刚才分割剩下的内存存放到dv chunk中。

4639          mem = chunk2mem(p);
4640          check_malloced_chunk(gm, mem, nb);
4641          goto postaction;

这里我们返回内存给用户，规则三第一部分内存分配结束。

4644        else if (gm->treemap != 0 && (mem = tmalloc_small(gm, nb))
!= 0) {
4645          check_malloced_chunk(gm, mem, nb);
4646          goto postaction;

这里else 对应“4618 if (smallbits != 0) {” 。也就是说，只有小内存的>=请求内存大小的所有箱子不存在空闲内存快。然后，我们检查treemap中是否存在空闲块，如果存在，则调用tmalloc_small。

2833#define treebin_at(M,i)     (&((M)->treebins[i]))

4527-static void* tmalloc_small(mstate m, size_t nb) {
...
4531  binmap_t leastbit = least_bit(m->treemap);
4532  compute_bit2idx(leastbit, i);
4533  v = t = *treebin_at(m, i);
4534  rsize = chunksize(t) - nb;

least_bit 的作用就是保留最右侧为1的bit位，其余位为0.所以，least_bit和compute_bit2idx的共同作用就是在treemap中找到最小的可用内存箱子。v和t即为找到的内存块树的根节点。

4536  while ((t = leftmost_child(t)) != 0) {
4537    size_t trem = chunksize(t) - nb;
4538    if (trem < rsize) {
4539      rsize = trem;
4540      v = t;
4541    }
4542  }

这段代码是寻找t的最左子树。在前文我们介绍过aka树，每一棵树的做子树总小于其右子树。该代码就是在寻找满足用于请求大小nb的最接近的树的节点。（考虑到请求的字节nb<=256byte, 而在tree中最小的chunksize > 256byte 所以,不会出现负数.）

4545    mchunkptr r = chunk_plus_offset(v, nb);
4546    assert(chunksize(v) == rsize + nb);
4547    if (RTCHECK(ok_next(v, r))) {
4548      unlink_large_chunk(m, v);
4549      if (rsize < MIN_CHUNK_SIZE)
4550        set_inuse_and_pinuse(m, v, (rsize + nb));
4551      else {
4552        set_size_and_pinuse_of_inuse_chunk(m, v, nb);
4553        set_size_and_pinuse_of_free_chunk(r, rsize);
4554        replace_dv(m, r, rsize);
4555      }
4556      return chunk2mem(v);
4557    }
4558  }

(NOT READY) 这段代码跟上文小内存找到后处理的代码相似。唯一的区别是，unlink_large_chunk，所以我们看下unlink_large_chunk的实现.这个过程有三个步骤

如果结点X是链表的结点,则将其重链表中删除.
如果X是该大小的最后一个结点,但是不是叶子结点,它必须用一个叶子结点替换.这里查找叶子结点的方法是从最右侧开始.
如果X是链表的头(拥有parent linker),就需要重新将其x的父结点与替换x的结点重新连接.

3730#define unlink_large_chunk(M, X) {\
3731  tchunkptr XP = X->parent;\
3732  tchunkptr R;\

3733  if (X->bk != X) {\
3734    tchunkptr F = X->fd;\
3735    R = X->bk;\
3736    if (RTCHECK(ok_address(M, F) && F->bk == X && R->fd == X)) {\
3737      F->bk = R;\
3738      R->fd = F;\
3739    }\
3740    else {\
3741      CORRUPTION_ERROR_ACTION(M);\
3742    }\
3743  }\

这里是第一种情况,即x是属于双向链表中的一个结点.

3744  else {\
3745    tchunkptr* RP;\
3746    if (((R = *(RP = &(X->child[1]))) != 0) ||\
3747        ((R = *(RP = &(X->child[0]))) != 0)) {\
3748      tchunkptr* CP;\
3749      while ((*(CP = &(R->child[1])) != 0) ||\
3750             (*(CP = &(R->child[0])) != 0)) {\
3751        R = *(RP = CP);\
3752      }\
3753      if (RTCHECK(ok_address(M, RP)))\
3754        *RP = 0;\
3755      else {\
3756        CORRUPTION_ERROR_ACTION(M);\
3757      }\
3758    }\
3759  }\

这是第二种情况.

3760  if (XP != 0) {\ 
3761    tbinptr* H = treebin_at(M, X->index);\ 
3762    if (X == *H) {\ 
3763      if ((*H = R) == 0) \ 
3764        clear_treemap(M, X->index);\ 
3765    }\ 
3766    else if (RTCHECK(ok_address(M, XP))) {\ 
3767      if (XP->child[0] == X) \ 
3768        XP->child[0] = R;\ 
3769      else \ 
3770        XP->child[1] = R;\ 
3771    }\ 
3772    else\ 
3773      CORRUPTION_ERROR_ACTION(M);\ 
3774    if (R != 0) {\ 
3775      if (RTCHECK(ok_address(M, R))) {\ 
3776        tchunkptr C0, C1;\ 
3777        R->parent = XP;\ 
3778        if ((C0 = X->child[0]) != 0) {\ 
3779          if (RTCHECK(ok_address(M, C0))) {\ 
3780            R->child[0] = C0;\ 
3781            C0->parent = R;\ 
3782          }\ 
3783          else\ 
3784            CORRUPTION_ERROR_ACTION(M);\ 
3785        }\ 
3786        if ((C1 = X->child[1]) != 0) {\ 
3787          if (RTCHECK(ok_address(M, C1))) {\ 
3788            R->child[1] = C1;\ 
3789            C1->parent = R;\ 
3790          }\ 
3791          else\ 
3792            CORRUPTION_ERROR_ACTION(M);\ 
3793        }\ 
3794      }\ 
3795      else\ 
3796        CORRUPTION_ERROR_ACTION(M);\ 
3797    }\ 
3798  }\

这是第三种情况.

以上,独属于小内存的分配规则结束!

4650    else if (bytes >= MAX_REQUEST)
4651      nb = MAX_SIZE_T; /* Too big to allocate. Force failure (in
sys alloc) */

2224#define MAX_REQUEST         ((-((MCHUNK_SIZE + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)) << 2)

这里,当请求内存大小>= MAX_REQUEST时,我们强制分配失败.CHUNK_ALIGN_MASK 为 2 * sizeof(void *) - 1,在32bit上为7.所以MAX_REQUEST是一个极大的数.在这种情况下,我们将nb设置为ffffffff,强制失败.

大内存分配规则一¶

类似小内存分配规则一,从树中找到最适合的内存块.

4652    else {
4653      nb = pad_request(bytes);
4654      if (gm->treemap != 0 && (mem = tmalloc_large(gm, nb)) != 0) {
4655        check_malloced_chunk(gm, mem, nb);
4656        goto postaction;
4657      }
4658    }

这里我们的重点是tmalloc_large,它与tmalloc_small的差别是:tmalloc_small是用于小内存分配的,只需要在treemap中找到最小的有效树,取出树中最小内存即可;而tmalloc_large是按照一定的规则,在所有32棵树中找到最匹配大小的内存块.

4456static void* tmalloc_large(mstate m, size_t nb) {
4457  tchunkptr v = 0;
4458  size_t rsize = -nb; /* Unsigned negation */
4459  tchunkptr t;
4460  bindex_t idx;
4461  compute_tree_index(nb, idx);
4462  if ((t = *treebin_at(m, idx)) != 0) {

rsize 为极大数. compute_tree_index通过请求的大小nb,从treebinmap中计算出箱号.treebin_at 则是取出idx箱号中对应的树根结点.

2880#define compute_tree_index(S, I)\
2881{\
2882  size_t X = S >> TREEBIN_SHIFT;\
2883  if (X == 0)\
2884    I = 0;\
2885  else if (X > 0xFFFF)\
2886    I = NTREEBINS-1;\
2887  else {\
2888    unsigned int Y = (unsigned int)X;\
2889    unsigned int N = ((Y - 0x100) >> 16) & 8;\
2890    unsigned int K = (((Y <<= N) - 0x1000) >> 16) & 4;\
2891    N += K;\
2892    N += K = (((Y <<= K) - 0x4000) >> 16) & 2;\
2893    K = 14 - N + ((Y <<= K) >> 15);\
2894    I = (K << 1) + ((S >> (K + (TREEBIN_SHIFT-1)) & 1));\
2895  }\
2896}

以上计算的结果如下,idx为对应箱号,mem对应该箱子中最小的内存大小.

idx 0 mem 256 hex: 100
idx 1 mem 384 hex: 180
idx 2 mem 512 hex: 200
idx 3 mem 768 hex: 300
idx 4 mem 1024 hex: 400
idx 5 mem 1536 hex: 600
idx 6 mem 2048 hex: 800
idx 7 mem 3072 hex: c00
idx 8 mem 4096 hex: 1000
idx 9 mem 6144 hex: 1800
idx 10 mem 8192 hex: 2000
idx 11 mem 12288 hex: 3000
idx 12 mem 16384 hex: 4000
idx 13 mem 24576 hex: 6000
idx 14 mem 32768 hex: 8000
idx 15 mem 49152 hex: c000
idx 16 mem 65536 hex: 10000
idx 17 mem 98304 hex: 18000
idx 18 mem 131072 hex: 20000
idx 19 mem 196608 hex: 30000
idx 20 mem 262144 hex: 40000
idx 21 mem 393216 hex: 60000
idx 22 mem 524288 hex: 80000
idx 23 mem 786432 hex: c0000
idx 24 mem 1048576 hex: 100000
idx 25 mem 1572864 hex: 180000
idx 26 mem 2097152 hex: 200000
idx 27 mem 3145728 hex: 300000
idx 28 mem 4194304 hex: 400000
idx 29 mem 6291456 hex: 600000
idx 30 mem 8388608 hex: 800000
idx 31 mem 12582912 hex: c00000

4463    /* Traverse tree for this bin looking for node with size == nb */
4464    size_t sizebits = nb << leftshift_for_tree_index(idx);
4465    tchunkptr rst = 0;  /* The deepest untaken right subtree */
4466    for (;;) {
4467      tchunkptr rt;
4468      size_t trem = chunksize(t) - nb;
4469      if (trem < rsize) {
4470        v = t;
4471        if ((rsize = trem) == 0)
4472          break;
4473      }
4474      rt = t->child[1];
4475      t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1];
4476      if (rt != 0 && rt != t)
4477        rst = rt;
4478      if (t == 0) {
4479        t = rst; /* set t to least subtree holding sizes > nb */
4480        break;
4481      }
4482      sizebits <<= 1;
4483    }

这是树的搜索算法,我们来详细看下.首先sizebits变量,类似binmap,每一位对应树的对应深度的左右子树,可以认为是遍历树的key bits.

2904#define leftshift_for_tree_index(i) \
2905   ((i == NTREEBINS-1)? 0 : \
2906    ((SIZE_T_BITSIZE-SIZE_T_ONE) - (((i) >> 1) + TREEBIN_SHIFT - 2)))

1601#define SIZE_T_BITSIZE      (sizeof(size_t) << 3)
1606#define SIZE_T_ONE          ((size_t)1)
2574#define TREEBIN_SHIFT     (8U)

leftshift_for_tree_index 宏将关键码移动到了最左.计算的结果为 (25 - (i >> 1)). 相对于箱子0, 内存范围为128, 关键码长度为 7, leftshift_for_tree_index计算的结果为25. 所以,将 nb << 25 , 就是将关键码移动到最左端.

然后我们看for循环内部的,这就是在遍历树了.

4467      tchunkptr rt;
4468      size_t trem = chunksize(t) - nb;
4469      if (trem < rsize) {
4470        v = t;
4471        if ((rsize = trem) == 0)
4472          break;
4473      }

与寻找最匹配nb最近的点.当然,如果找到大小相等的,就直接跳出, 这个跳出条件可能是关键码还未搜索完.这里就可以看出, dlmalloc树与 bitwise trie树的差异,值在特征码的路径上的任意点. 为什么可以这么做呢?因为dlmalloc的分箱机制,导致了,如果搜索完关键码,则该结点必定只存在叶子结点上. 在这个前提下,为了节省内存空间, 在插入结点时,只要在关键码的路径上不存在被占用的点,就将该值插入. 在查看了 insert_large_chunk 后会有更清晰的体会.

4474      rt = t->child[1];
4475      t = t->child[(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1];
4476      if (rt != 0 && rt != t)
4477        rst = rt;
4478      if (t == 0) {
4479        t = rst; /* set t to least subtree holding sizes > nb */
4480        break;
4481      }
4482      sizebits <<= 1;

(sizebits >> (SIZE_T_BITSIZE-SIZE_T_ONE)) 这个就是每一层树的特征码了.结合上面sizebits的值,我们可以算出这个表达式的值为 nb >> (6 + (i >> 1)). 如果,我们再结合compute_tree_index 中的结果,得到如下表.idx为箱号,mem为该箱子中的最小内存,hex为该值的16进制,mid为区分左子树和右子树的特征码,bitshift为特征码的无效位数. 比如,箱子1中,dix为1,其表示的内存范围为[384, 512),则其左子树表示范围为[384,448),右子树为[448,512).448即为该树的第一层的特征码,也就是111000000.如果nb < 448, 则第7位为0,否则第7位为1.所以,只要通过将size >> bitshift 之后与1 做位与运算,就可以判断出在该树对应层该进入其左子树还是右子树.

idx 0 mem 256 hex: 100  mid: 101000000 bitshift: 6
idx 1 mem 384 hex: 180 mid: 111000000 bitshift: 6
idx 2 mem 512 hex: 200 mid: 1110000000 bitshift: 7
idx 3 mem 768 hex: 300 mid: 1010000000 bitshift: 7
idx 4 mem 1024 hex: 400 mid: 10100000000 bitshift: 8
idx 5 mem 1536 hex: 600 mid: 11100000000 bitshift: 8
idx 6 mem 2048 hex: 800 mid: 101000000000 bitshift: 9
idx 7 mem 3072 hex: c00 mid: 111000000000 bitshift: 9
idx 8 mem 4096 hex: 1000 mid: 1010000000000 bitshift: 10
idx 9 mem 6144 hex: 1800 mid: 1110000000000 bitshift: 10
idx 10 mem 8192 hex: 2000 mid: 10100000000000 bitshift: 11
idx 11 mem 12288 hex: 3000 mid: 11100000000000 bitshift: 11
idx 12 mem 16384 hex: 4000 mid: 101000000000000 bitshift: 12
idx 13 mem 24576 hex: 6000 mid: 111000000000000 bitshift: 12
idx 14 mem 32768 hex: 8000 mid: 1010000000000000 bitshift: 13
idx 15 mem 49152 hex: c000 mid: 1110000000000000 bitshift: 13
idx 16 mem 65536 hex: 10000 mid 10100000000000000 bitshift: 14
idx 17 mem 98304 hex: 18000 mid 11100000000000000 bitshift: 14
idx 18 mem 131072 hex: 20000 mid 101000000000000000 bitshift: 15
idx 19 mem 196608 hex: 30000 mid 111000000000000000 bitshift: 15
idx 20 mem 262144 hex: 40000 mid 1010000000000000000 bitshift: 16
idx 21 mem 393216 hex: 60000 mid 1110000000000000000 bitshift: 16
idx 22 mem 524288 hex: 80000 mid 10100000000000000000 bitshift: 17
idx 23 mem 786432 hex: c0000 mid 11100000000000000000 bitshift: 17
idx 24 mem 1048576 hex: 100000 mid 101000000000000000000 bitshift: 18
idx 25 mem 1572864 hex: 180000 mid 111000000000000000000 bitshift: 18
idx 26 mem 2097152 hex: 200000 mid 1010000000000000000000 bitshift: 19
idx 27 mem 3145728 hex: 300000 mid 1110000000000000000000 bitshift: 19
idx 28 mem 4194304 hex: 400000 mid 10100000000000000000000 bitshift: 20
idx 29 mem 6291456 hex: 600000 mid 11100000000000000000000 bitshift: 20
idx 30 mem 8388608 hex: 800000 mid 101000000000000000000000 bitshift: 21
idx 31 mem 12582912 hex: c00000 bitshift: 31

// 图, dlammloc 树的图.

4485  if (t == 0 && v == 0) { /* set t to root of next non-empty treebin */
4486    binmap_t leftbits = left_bits(idx2bit(idx)) & m->treemap;
4487    if (leftbits != 0) {
4488      bindex_t i;
4489      binmap_t leastbit = least_bit(leftbits);
4490      compute_bit2idx(leastbit, i);
4491      t = *treebin_at(m, i);
4492    }
4493  }

这里对应上文的4462 if ((t = *treebin_at(m, idx)) != 0) { , 也就是说在当前大小的箱子内不存在空闲的内存块,所以我们要把t设置为最近的存在空闲内存块的箱号.left_bits 和 least_bit 跟上文小内存寻找最近存在空闲内存块的箱子算法一样.

4495  while (t != 0) { /* find smallest of tree or subtree */
4496    size_t trem = chunksize(t) - nb;
4497    if (trem < rsize) {
4498      rsize = trem;
4499      v = t;
4500    }
4501    t = leftmost_child(t);
4502  }

这里跟tmalloc_small寻找最左子树(最小内存)的算法一样.这段代码对上面的两种情况都有效.即,如果在对应箱号有空闲内存,在基于树的搜索算法找到的t就是最匹配nb的大小,所以这里的while循环结果t就不会改变;如果是,寻找最近有空闲块的树,那么该树的最小内存都大于请求大小nb,所以直接寻找最左子树.

4505  if (v != 0 && rsize < (size_t)(m->dvsize - nb)) {
4506    if (RTCHECK(ok_address(m, v))) { /* split */
4507      mchunkptr r = chunk_plus_offset(v, nb);
4508      assert(chunksize(v) == rsize + nb);
4509      if (RTCHECK(ok_next(v, r))) {
4510        unlink_large_chunk(m, v);
4511        if (rsize < MIN_CHUNK_SIZE)
4512          set_inuse_and_pinuse(m, v, (rsize + nb));
4513        else {
4514          set_size_and_pinuse_of_inuse_chunk(m, v, nb);
4515          set_size_and_pinuse_of_free_chunk(r, rsize);
4516          insert_chunk(m, r, rsize);
4517        }
4518        return chunk2mem(v);
4519      }
4520    }
4521    CORRUPTION_ERROR_ACTION(m);
4522  }
4523  return 0;

接下来,只要求顶找到的内存块比dv chunk更合适,则执行一般的内存块收尾处理,然后返回.如果dv chunk更合适,我们返回0, 参考代码 4654 if (gm->treemap != 0 && (mem = tmalloc_large(gm, nb)) != 0) {, 就会继续按照内存分配规则往下走.

大小内存分配规则二¶

如果nb的大小 < dv chunk的大小,则使用dv chunk分配内存.尽量保证连续的内存请求在虚拟内存上连续.

4660    if (nb <= gm->dvsize) {
4661      size_t rsize = gm->dvsize - nb;
4662      mchunkptr p = gm->dv;
4663      if (rsize >= MIN_CHUNK_SIZE) { /* split dv */
4664        mchunkptr r = gm->dv = chunk_plus_offset(p, nb);
4665        gm->dvsize = rsize;
4666        set_size_and_pinuse_of_free_chunk(r, rsize);
4667        set_size_and_pinuse_of_inuse_chunk(gm, p, nb);
4668      }
4669      else { /* exhaust dv */
4670        size_t dvs = gm->dvsize;
4671        gm->dvsize = 0;
4672        gm->dv = 0;
4673        set_inuse_and_pinuse(gm, p, dvs);
4674      }
4675      mem = chunk2mem(p);
4676      check_malloced_chunk(gm, mem, nb);
4677      goto postaction;
4678    }

切分dv chunk, 然后就是基本的域设置.返回给用户.

大小内存分配规则四¶

4680    else if (nb < gm->topsize) { /* Split top */
4681      size_t rsize = gm->topsize -= nb;
4682      mchunkptr p = gm->top;
4683      mchunkptr r = gm->top = chunk_plus_offset(p, nb);
4684      r->head = rsize | PINUSE_BIT;
4685      set_size_and_pinuse_of_inuse_chunk(gm, p, nb);
4686      mem = chunk2mem(p);
4687      check_top_chunk(gm, gm->top);
4688      check_malloced_chunk(gm, mem, nb);
4689      goto postaction;
4690    }

跟dv chunk类似.难点其实是找到符合的chunk.像dv chunk 和top chunk都是找到了的,就直接分配.

大小内存分配规则五¶

调用系统函数进行内存分配.这里使用到了segment.

4692    mem = sys_alloc(gm, nb);
4693
4694  postaction:
4695    POSTACTION(gm);
4696    return mem;
4697  }
4698
4699  return 0;

先说下sys_alloc的规则:

优先使用MORECORE(sbrk())分配连续的内存空间
使用mmap分配不连续的内存空间
使用sbrk()分配不连续的内存空间.

sbrk实际上是对进程的数据段进行扩展,返回增长的区域的基地址.

4059  /* Directly map large chunks, but only if already initialized */
4060  if (use_mmap(m) && nb >= mparams.mmap_threshold && m->topsize != 0) {
4061    void* mem = mmap_alloc(m, nb);
4062    if (mem != 0)
4063      return mem;
4064  }

如果使用mmap的标志被置上并且nb >= mmap的阀值,则直接使用mmap.

4066  asize = granularity_align(nb + SYS_ALLOC_PADDING);

做对齐处理.

4105  if (MORECORE_CONTIGUOUS && !use_noncontiguous(m)) {
4106    char* br = CMFAIL;
4107    size_t ssize = asize; /* sbrk call size */
4108    msegmentptr ss = (m->top == 0)? 0 : segment_holding(m, (char*)m->top);
4109    ACQUIRE_MALLOC_GLOBAL_LOCK();

我们看下segment_holding函数.

2698static msegmentptr segment_holding(mstate m, char* addr) {
2699  msegmentptr sp = &m->seg;
2700  for (;;) {
2701    if (addr >= sp->base && addr < sp->base + sp->size)
2702      return sp;
2703    if ((sp = sp->next) == 0)
2704      return 0;
2705  }
2706}

segment实际上是由单向链表管理的,但由于使用到segment的情况非常少,所以,也没有什么效率问题. 这里的功能就是寻找addr所属的segment块的地址,并返回.结合上面的,ss实际上就是top chunk所在的segment的基地址.

4111    if (ss == 0) {  /* First time through or recovery */
4112      char* base = (char*)CALL_MORECORE(0);
4113      if (base != CMFAIL) {
4114        size_t fp;
4115        /* Adjust to end on a page boundary */
4116        if (!is_page_aligned(base))
4117          ssize += (page_align((size_t)base) - (size_t)base);
4118        fp = m->footprint + ssize; /* recheck limits */
4119        if (ssize > nb && ssize < HALF_MAX_SIZE_T &&
4120            (m->footprint_limit == 0 ||
4121             (fp > m->footprint && fp <= m->footprint_limit)) &&
4122            (br = (char*)(CALL_MORECORE(ssize))) == base) {
4123          tbase = base;
4124          tsize = ssize;
4125        }
4126      }
4127    }

这里就是处理top chunk为NULL 时的情况, 也就是第一次请求内存分配,因为top为0.CALL_MORECORE宏展开来就是sbrk.这里是获取当前的program break的地址. ssize就是请求增加的大小,然后再次调用sbrk.

4128    else {
4129      /* Subtract out existing available top space from MORECORE request. */
4130      ssize = granularity_align(nb - m->topsize + SYS_ALLOC_PADDING);
4131      /* Use mem here only if it did continuously extend old space */
4132      if (ssize < HALF_MAX_SIZE_T &&
4133          (br = (char*)(CALL_MORECORE(ssize))) == ss->base+ss->size) {
4134        tbase = br;
4135        tsize = ssize;
4136      }
4137    }

对应top chunk 存在的情况.直接扩展top chunk所在的segment. 上面两种情况的tbase都指向增长的块的基地址,tsize指向增长的大小.

4139    if (tbase == CMFAIL) {    /* Cope with partial failure */
4140      if (br != CMFAIL) {    /* Try to use/extend the space we did get */
4141        if (ssize < HALF_MAX_SIZE_T &&
4142            ssize < nb + SYS_ALLOC_PADDING) {
4143          size_t esize = granularity_align(nb + SYS_ALLOC_PADDING - ssize);
4144          if (esize < HALF_MAX_SIZE_T) {
4145            char* end = (char*)CALL_MORECORE(esize);
4146            if (end != CMFAIL)
4147              ssize += esize;
4148            else {            /* Can't use; try to release */
4149              (void) CALL_MORECORE(-ssize);
4150              br = CMFAIL;
4151            }
4152          }
4153        }
4154      }
4155      if (br != CMFAIL) {    /* Use the space we did get */
4156        tbase = br;
4157        tsize = ssize;
4158      }
4159      else
4160        disable_contiguous(m); /* Don't try contiguous path in the future */
4161    }
4162
4163    RELEASE_MALLOC_GLOBAL_LOCK();

如果部分失败了,即上文的tbase赋值时,if条件部分不满,也就是,请求的ssize > HALF_MAX_SIZE_T(ffffffff/2)或者其他的情况.则我们继续使用br的地址进行扩展.不过一般情况下tbase == CMFAIL 时, br == CFAIL.从这部分的代码逻辑看,应该是非连续的sbrk的逻辑.

4166  if (HAVE_MMAP && tbase == CMFAIL) {  /* Try MMAP */
4167    char* mp = (char*)(CALL_MMAP(asize));
4168    if (mp != CMFAIL) {
4169      tbase = mp;
4170      tsize = asize;
4171      mmap_flag = USE_MMAP_BIT;
4172    }
4173  }

尝试 mmap.

4175  if (HAVE_MORECORE && tbase == CMFAIL) { /* Try noncontiguous MORECORE */
4176    if (asize < HALF_MAX_SIZE_T) {
4177      char* br = CMFAIL;
4178      char* end = CMFAIL;
4179      ACQUIRE_MALLOC_GLOBAL_LOCK();
4180      br = (char*)(CALL_MORECORE(asize));
4181      end = (char*)(CALL_MORECORE(0));
4182      RELEASE_MALLOC_GLOBAL_LOCK();
4183      if (br != CMFAIL && end != CMFAIL && br < end) {
4184        size_t ssize = end - br;
4185        if (ssize > nb + TOP_FOOT_SIZE) {
4186          tbase = br;
4187          tsize = ssize;
4188        }
4189      }
4190    }
4191  }

尝试非连续的sbrk.

4198    if (!is_initialized(m)) { /* first-time initialization */
4199      if (m->least_addr == 0 || tbase < m->least_addr)
4200        m->least_addr = tbase;
4201      m->seg.base = tbase;
4202      m->seg.size = tsize;
4203      m->seg.sflags = mmap_flag;
4204      m->magic = mparams.magic;
4205      m->release_checks = MAX_RELEASE_CHECK_RATE;
          // 初始化 所有的箱子. 32bit全置0
4206      init_bins(m);
4207#if !ONLY_MSPACES
4208      if (is_global(m))
            // 初始化top chunk.
4209        init_top(m, (mchunkptr)tbase, tsize - TOP_FOOT_SIZE);
4210      else
4211#endif
4212      {
4213        /* Offset top by embedded malloc_state */
4214        mchunkptr mn = next_chunk(mem2chunk(m));
            // 初始化top chunk.
4215        init_top(m, mn, (size_t)((tbase + tsize) - (char*)mn) -TOP_FOOT_SIZE);
4216      }
4217    }

在这里,才是真正地对内存管理的一些结构体进行初始化.

4219    else {
4220      /* Try to merge with an existing segment */
4221      msegmentptr sp = &m->seg;
4222      /* Only consider most recent segment if traversal suppressed */
4223      while (sp != 0 && tbase != sp->base + sp->size)
4224        sp = (NO_SEGMENT_TRAVERSAL) ? 0 : sp->next;
4225      if (sp != 0 &&
4226          !is_extern_segment(sp) &&
4227          (sp->sflags & USE_MMAP_BIT) == mmap_flag &&
4228          segment_holds(sp, m->top)) { /* append */
4229        sp->size += tsize;
4230        init_top(m, m->top, m->topsize + tsize);
4231      }
4232      else {
4233        if (tbase < m->least_addr)
4234          m->least_addr = tbase;
4235        sp = &m->seg;
4236        while (sp != 0 && sp->base != tbase + tsize)
4237          sp = (NO_SEGMENT_TRAVERSAL) ? 0 : sp->next;
4238        if (sp != 0 &&
4239            !is_extern_segment(sp) &&
4240            (sp->sflags & USE_MMAP_BIT) == mmap_flag) {
4241          char* oldbase = sp->base;
4242          sp->base = tbase;
4243          sp->size += tsize;
4244          return prepend_alloc(m, tbase, oldbase, nb);
4245        }
4246        else
4247          add_segment(m, tbase, tsize, mmap_flag);
4248      }
4249    }

逻辑很简单,就是如果新分配的segemnt的基地址是某个segment的尾地址,则这两个合并,否则,直接将该新的segment加入到单向链表中.

4251    if (nb < m->topsize) { /* Allocate from new or extended top space */
4252      size_t rsize = m->topsize -= nb;
4253      mchunkptr p = m->top;
4254      mchunkptr r = m->top = chunk_plus_offset(p, nb);
4255      r->head = rsize | PINUSE_BIT;
4256      set_size_and_pinuse_of_inuse_chunk(m, p, nb);
4257      check_top_chunk(m, m->top);
4258      check_malloced_chunk(m, chunk2mem(p), nb);
4259      return chunk2mem(p);
4260    }
4261  }

如果是第一次内存分配,则逻辑将会到这里,在top chunk初始化后,尝试从top chunk分配内存.

dlfree代码分析¶

dlfree就没有dlmalloc那么多规则了,只要保证边界标记法,保证释放的内存块存放到对应的箱子中即可.

4704void dlfree(void* mem) { 
4711  if (mem != 0) {

检查mem合法性.

4711  if (mem != 0) {
        //将mem转换成chunk p
4712    mchunkptr p  = mem2chunk(mem);
4713#if FOOTERS
4714    mstate fm = get_mstate_for(p);
4715    if (!ok_magic(fm)) {
4716      USAGE_ERROR_ACTION(fm, p);
4717      return;
4718    }
4719#else /* FOOTERS */
4720#define fm gm
4721#endif /* FOOTERS */ 
4722    if (!PREACTION(fm)) {
          // 检查标志位是否为inuse.
4723      check_inuse_chunk(fm, p);
4724      if (RTCHECK(ok_address(fm, p) && ok_inuse(p))) {
            // 获取chunksize
4725        size_t psize = chunksize(p);
            // 获取在内存上相连的下一个内存chunk.
4726        mchunkptr next = chunk_plus_offset(p, psize);

将用户指针转换为chunk结构体并做常规检查.

            // 上一个内存块未被使用
4727        if (!pinuse(p)) {
4728          size_t prevsize = p->prev_foot;
4729          if (is_mmapped(p)) {
                // 是通过系统mmap分配的
4730            psize += prevsize + MMAP_FOOT_PAD;
4731            if (CALL_MUNMAP((char*)p - prevsize, psize) == 0)
4732              fm->footprint -= psize;
4733            goto postaction;
4734          }
4735          else {
               // 与上一个内存块合并
4736            mchunkptr prev = chunk_minus_offset(p, prevsize);
4737            psize += prevsize;
4738            p = prev;
4739            if (RTCHECK(ok_address(fm, prev))) { /* consolidate backward */
4740              if (p != fm->dv) {
                    // p 不为 dv chunk, 直接移除.
4741                unlink_chunk(fm, p, prevsize);
4742              }
4743              else if ((next->head & INUSE_BITS) == INUSE_BITS) {
                    // 否则,合并到dv chunk中.
4744                fm->dvsize = psize;
4745                set_free_with_pinuse(p, psize, next);
4746                goto postaction;
4747              }
4748            }
4749            else
4750              goto erroraction;
4751          }
4752        }

与前一块内存合并的逻辑.

4754        if (RTCHECK(ok_next(p, next) && ok_pinuse(next))) {

ok_pinuse(next)实际上就是cinuse(p). 只是这里是检查next的标志位是否正确.

              // next 未被使用, 则需要合并.
4755          if (!cinuse(next)) {  /* consolidate forward */
4756            if (next == fm->top) {
                  // 如果next为top, 则top增长.基地址改为p.
4757              size_t tsize = fm->topsize += psize;
4758              fm->top = p;
4759              p->head = tsize | PINUSE_BIT;
4760              if (p == fm->dv) {
                    // 如果p为dv, 则清空dv.
4761                fm->dv = 0;
4762                fm->dvsize = 0;
4763              }
                  // 检查top chunk的大小是否需要调整,默认最大为 2 * 1024 * 1024
4764              if (should_trim(fm, tsize))
4765                sys_trim(fm, 0);
4766              goto postaction;
4767            }
4768            else if (next == fm->dv) {
                  // 如果next为div, 则dv增长, 基地址改为p
4769              size_t dsize = fm->dvsize += psize;
4770              fm->dv = p;
4771              set_size_and_pinuse_of_free_chunk(p, dsize);
4772              goto postaction;
4773            }
4774            else {
                  // next为普通的内存块,将next合并到p,并将next冲链表或者树中删除.
4775              size_t nsize = chunksize(next);
4776              psize += nsize;
4777              unlink_chunk(fm, next, nsize);
4778              set_size_and_pinuse_of_free_chunk(p, psize);
4779              if (p == fm->dv) {
4780                fm->dvsize = psize;
4781                goto postaction;
4782              }
4783            }
              // 与后一块内存合并的逻辑.
4785          else
4786            set_free_with_pinuse(p, psize, next);

当然,如果不需要合并,则直接删除.

以上都只是合并块,并删除被合并的结点,接下来就是将合并后的块插入到正确的箱子的结构中.

4788          if (is_small(psize)) {
                // 合并处理后的内存为小内存
                // 已在上文介绍过该函数.
4789            insert_small_chunk(fm, p, psize);
4790            check_free_chunk(fm, p);
4791          }
4792          else {
                // 合并后为大内存
4793            tchunkptr tp = (tchunkptr)p;
4794            insert_large_chunk(fm, tp, psize);
4795            check_free_chunk(fm, p);
4796            if (--fm->release_checks == 0)
4797              release_unused_segments(fm);
4798          }
4799          goto postaction;
4800        }
4801      }
4802    erroraction:
4803      USAGE_ERROR_ACTION(fm, p);
4804    postaction:
4805      POSTACTION(fm);
4806    }
4807  }

insert_small_chunk 已经在上文介绍过.实际行为就是根据内存大小找箱号,如果该箱子本身为空,则修改binmap状态并插入该chunk.如果不为空,则执行双向链表插入. 而insert_large_chunk是我们之前提到的unlink_large_chunk的逆操作.同样是定位箱号,遍历树.然后找到对应该大小的结点.它存在以下两种情况:

该箱子中不存在树. 则创建并将该结点作为根节点.
已存在树,但不存在对应大小的结点, 则插入结点.
已存在树,且存在对应大小的结点,则插入双向链表

3662#define insert_large_chunk(M, X, S) {\ 
3663  tbinptr* H;\ 
3664  bindex_t I;\ 
3665  compute_tree_index(S, I);\ 
3666  H = treebin_at(M, I);\ 
3667  X->index = I;\ 
3668  X->child[0] = X->child[1] = 0;\ 
3669  if (!treemap_is_marked(M, I)) {\ 
3670    mark_treemap(M, I);\ 
3671    *H = X;\ 
3672    X->parent = (tchunkptr)H;\ 
3673    X->fd = X->bk = X;\ 
3674  }\

//上面为情况一. 将treemap 对应I的位置置1,并将该结点作为树的根结点.

3675  else {\ 
3676    tchunkptr T = *H;\ 
3677    size_t K = S << leftshift_for_tree_index(I);\ 
3678    for (;;) {\ 
3679      if (chunksize(T) != S) {\ 
3680        tchunkptr* C = &(T->child[(K >> (SIZE_T_BITSIZE-SIZE_T_ONE)) & 1]);\ 
3681        K <<= 1;\ 
3682        if (*C != 0)\ 
3683          T = *C;\ 
3684        else if (RTCHECK(ok_address(M, C))) {\ 
3685          *C = X;\ 
3686          X->parent = T;\ 
3687          X->fd = X->bk = X;\ 
3688          break;\ 
3689        }\ 
3690        else {\ 
3691          CORRUPTION_ERROR_ACTION(M);\ 
3692          break;\ 
3693        }\ 
3694      }\
// 上面为情况二, 在关键码路径上存在空结点,则插入该结点.
3695      else {\ 
3696        tchunkptr F = T->fd;\ 
3697        if (RTCHECK(ok_address(M, T) && ok_address(M, F))) {\
3698          T->fd = F->bk = X;\ 
3699          X->fd = F;\ 
3700          X->bk = T;\ 
3701          X->parent = 0;\ 
3702          break;\ 
3703        }\ 
3704        else {\ 
3705          CORRUPTION_ERROR_ACTION(M);\ 
3706          break;\ 
3707        }\ 
3708      }\ 
3709    }\ 
3710  }\

// 上面为情况三,该大小的结点存在,则插入双向链表.

总结¶

数据结构总结

dlmalloc中按照内存的粒度大小,分为chunk和segment两种数据结构.
dlmalloc中按照内存的大小,有3种内存管理方式,再加上边界标记法,总共四种管理方式:
- 边界标记法，并且任意相连两块内存不同为空闲内存.
- 双向链表管理大小小于256byte的内存.
- dlmalloc树与双向链表结合管理大小大于256byte的内存.
- 单向链表管理segment结构.
dlmalloc通过两个位图分别管理双向链表和dlmalloc树.

+---------------------------segment-------------------------------------+
+  0X10   |  0X12  |  0x109 |  0x110 |                                  +
+ chunk0  | chunk1 | chunk2 | chunk3 |            top                   +
+-----------------------------------------------------------------------+

上面的数字为chunk结构体中的size. chunk0和chunk1 都为小内存,大小为0x10, 16byte.而 chunk1 的0x02是表示chunk0表示自己使用.chunk0 归属与箱号为2,由双向链表管理. chunk2和chunk3 为大内存, 大小为0x108, 264byte. chunk2 大小 | 0x01表示前一个内存块被使用. chunk3 | 0x02 因为自己在被使用. 这两个归属与箱号为0的树管理. 最后是top块.

setgment由系统通过sbrk分配. top 从segment而来.如果top超过一个阀值,就会通过sbrk,缩小.如果太小,通过sbrk扩大top. 各个chunk 由 top切分, 或者free时, 或者dv chunk被替换时产生.

算法总结:

小内存分配规则
- 跟据请求大小,优先寻找最匹配的箱子,之后临近箱子.在能不分割内存的情况下尽量不分割内存.
- 如果dv chunk足够大,则使用dv chunk.
- 如果前两个不满足,则在smallbin中寻找最接近请求大小的空闲块箱号.
- 如果top 足够大,使用top.
- 如果请求内存实在太大,则使用系统分配.
大内存分配规则
- 如果treebin中找到最合适的最小内存,如果它比dv chunk更合适,就使用它.
- 如果dv chunk比其他所有合适,则使用dv chunk.
- 如果top 足够大,则使用top.
- 如果请求大小 >= mmap的阀值,则使用mmap.
- 直接从系统分配内存.
内存释放规则
- 如果在虚拟内存上的当前释放内存的前/后一个内存为空闲,则合并.
- 如果前/后一个内存为dv chunk, 则合并到dv chunk
- 如果后一个内存为top, 则合并到top
- 如果前/后一个内存为普通内存块,则删除后,查找并插入符合大小的箱子中.
smallbin 和 treebin的规则.
- smallbin 为32bit数,没一个bit对应一个箱子的状态.1 为有空闲内存, 0 为无. 32个箱子的大小为以8 为基数, 以8 为增率, 长度为32的等差数列
- treebin的状态与smallbin一致. treebin的各个箱子的大小见上文.
treebin中的树的搜索算法
- 该树表示一段内存范围.所以没一棵子树用二分法表示对应的区间范围.
- 左子树上的任意chunk大小都小于其右子树的任意chunk的大小,
- 参考 tmalloc_large,insert_large_chunk 和unlink_large_chunk的解析.