dlmalloc解析连载五

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

 

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块大小更接近请求字节数目）则使用它。否则的话，进入下一步。

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

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

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

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

             

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

4024.              /*

4025.                 Basic algorithm:

4026.                 If a small request (< 256 bytes minus per-chunk overhead):

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 <= MAX_SMALL_REQUEST) {

4051.                  bindex_t idx;

4052.                  binmap_t smallbits;

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

4053.                  nb = (bytes < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(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)<<1])))

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)  << SMALLBIN_SHIFT)

#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则用于记录该chunk块所在的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) << (i))

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<<1) | -(x<<1))

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

4075.                      binmap_t leftbits = (smallbits << idx) & left_bits(idx2bit(idx));

选择最佳适合的箱号对应的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 < MIN_CHUNK_SIZE为真的情况的。换句话说，只有当SIZE_T_SIZE!=4的情况下，rsize < MIN_CHUNK_SIZE才有可能为真。至于为什么，可由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 < MIN_CHUNK_SIZE)

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 <= gm->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 < gm->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;

}