ptmalloc中的fastbin chunk的合并过程

    最近在设计一个memcache协议队列的内存管理模块,其实malloc和free并不是想象中的那种,malloc完空间free就会马上把内存返回给操作系统,所以了解一下glibc 中malloc和free函数的实现是十分必要的。了解了glibc中malloc实现原理对于设计一个自己的内存管理模块是十分有意义的,可以从中学到很多的优良设计。

    glibc中malloc类函数的实现是ptmalloc,分配内存大致思想就是依赖于底层brk或者mmap系统调用,来开辟新的地址空间,free函数会把释放的地址空间放到不同的容器中,fastbin存放的都是一些free后小的地址空间,具体这个阈值是可以mallopt函数进行配置的,默认的size_t*16字节。

    分配出的地址空间的结构体是malloc_chunk,而malloc_chunk按照所存储的地址空间的大小,存放在不同的容器中,有fastbin,small bin,unsorted bin ,large bin,但是本文只分析small bin和fast bin

fastbin结构图:

ptmalloc中的fastbin chunk的合并过程-LMLPHP

smallbin结构图:

ptmalloc中的fastbin chunk的合并过程-LMLPHP

    从上面两张图可以看出都是由数组+双向链表构成,fast bin缓存16B-64B大小的malloc _chunk,而small bin缓存的是16B-511B大小的malloc_chunk,这两个bin存储的malloc_chunk大小是有重叠的,fast bin存在的意义就在于非fast bin中malloc_chunk在free的时候,如果这个chunk前后的chunk是空闲的,那么这个chunk会合并,然后放到unsort bin中,这里需要注意的是这个前后,并不是指的是malloc_chunk双向链表的prev和next,而是虚拟地址空间前后,试想malloc函数肯定是通过brk或者mmap分配一段虚拟地址空间,然后从这个大地址空间根据malloc大小切割地址空间,所以这样在地址空间相邻的malloc_chunk才能彼此合并。双向链表的前后元素在地址空间上根本不能保证相邻。在合并的过程中肯定会判断地址空间相邻的malloc_chunk是否是空闲,如果不是空闲,那么肯定是被malloc函数分配出去了,还有一种可能就是fast bin中的malloc_chunk。fast bin中malloc_chunk的特点就是不会清除空闲标志,free chunk之后直接放到了fast bin中,并且保证不会被合并。保证了malloc_chunk空闲容器中会存在这种小的地址空间,方便malloc快速分配小地址空间。

    通过上面的分析,如果malloc函数请求的大小小于等于64B,那么首先会去fast bin中找合适的malloc_chunk,这样malloc的速度会大大加快,主要是fast bin中malloc_chunk保证了不会其他容器的malloc_chunk被合并。

    通过代码分析一下,在free malloc_chunk的过程中会尝试与地址空间相邻的空闲的malloc_chunk进行合并(fast bin 中的chunk不清除inuse状态)。

free函数片段

/* consolidate backward */  //如果前面的chunk空闲,合并前面的chunk
if (!prev_inuse(p)) {
  prevsize = p->prev_size;
  size += prevsize;
  p = chunk_at_offset(p, -((long) prevsize)); //必须更新这个chunk的首地址
  unlink(p, bck, fwd);
}

if (nextchunk != av->top) {
  /* get and clear inuse bit */
  nextinuse = inuse_bit_at_offset(nextchunk, nextsize);

  /* consolidate forward */  //判断后面的chunk是否空闲
  if (!nextinuse) {
    unlink(nextchunk, bck, fwd); //如果空闲,不需要在改变首地址了,只需要更新size
    size += nextsize;
  } else
    clear_inuse_bit_at_offset(nextchunk, 0); //如果后面的chunk在用,更新标志。

    为什么上面的chunk只关心相邻的chunk,不用再去递归再相邻的chunk了,因为相邻的chunk如果它的周围还是空闲的,那么之前的free过程肯定会去合并他们,所以这里根本不用考虑那种情况。在fast bin中我们不必担心malloc_chunk中的空闲状态,这个状态只是给合并操作看的,告诉不要合并它们。任何容器中的chunk都是空闲的。一旦被malloc函数所征用,会移除容器的。

    那么fast bin中的chunk也不是一成不变的,在一些情况下fast bin中的chunk也会被merge移动到unsort bin中,其中fast bin的chunk会参考相邻的chunk,如果是空闲的就会被fast bin中的chunk所合并,然后移动到unsort bin中。也就是说有一些除了fast bin中彼此虚拟地址空间相邻的被合并到unsort bin,small bin或者large bin中的一些和fast bin地址相邻的chunk合并到unsort bin,

  1. 如果size是small bin中的,对应的链表没有chunk,那么会合并一下fast bin中的chunk,这样有可能产生满足chunk。

  2. 如果size是large bin中的,直接合并一下fast bin中的chunk,注释上说避免fast bin中太多碎片,很有可能在合并过后,分配到了large bin中,正是我们所需要的。

  3. 在调用brk或者mmap函数之前会最后一次尝试合并一下fast bin中chunk。

  4. 在free函数的最后,如果free的malloc_chunk和虚拟地址空间相邻的空闲chunk合并后的size> FASTBIN_CONSOLIDATION_THRESHOLD,那么会合并fast bin中的chunk,目的是更新top chunk的指针,因为fast bin中malloc_chunk都是使用状态,这样合并后,会更新top chunk的指针,因为合并操作会合并地址空间相邻的chunk,如果chunk的next是top chunk指针,说明可以更新top chunk指针了,这样更有利于释放空间到系统。

下面看下合并fast bin中malloc_chunk的代码:

static void malloc_consolidate(mstate av)
{
  mfastbinptr*    fb;                 /* current fastbin being consolidated */
  mfastbinptr*    maxfb;              /* last fastbin (for loop control) */
  mchunkptr       p;                  /* current chunk being consolidated */
  mchunkptr       nextp;              /* next chunk to consolidate */
  mchunkptr       unsorted_bin;       /* bin header */
  mchunkptr       first_unsorted;     /* chunk to link to */

  /* These have same use as in free() */
  mchunkptr       nextchunk;
  INTERNAL_SIZE_T size;
  INTERNAL_SIZE_T nextsize;
  INTERNAL_SIZE_T prevsize;
  int             nextinuse;
  mchunkptr       bck;
  mchunkptr       fwd;

  /*
     If max_fast is 0, we know that av hasn't
     yet been initialized, in which case do so below
   */

  if (get_max_fast () != 0) {  //表示已经初始化过了
    clear_fastchunks(av);

    unsorted_bin = unsorted_chunks(av);

    maxfb = &fastbin (av, NFASTBINS - 1);
    fb = &fastbin (av, 0);
    //开始递归fastbin每一个双向链表的每一个元素,第一层递归每一个链表,第二层递归链表中每一个元素
    do {
      p = atomic_exchange_acq (fb, 0);
      if (p != 0) {
        do {
          check_inuse_chunk(av, p);
          nextp = p->fd;
          size = p->size & ~(PREV_INUSE|NON_MAIN_ARENA);
          nextchunk = chunk_at_offset(p, size);
          nextsize = chunksize(nextchunk);
          //如果虚拟地址空间的前一个chunk是空闲的,就开始合并到当前chunk中,同时更新size,和p指针,把前一个chunk从它的链表中摘除
          if (!prev_inuse(p)) {
            prevsize = p->prev_size;
            size += prevsize;
            p = chunk_at_offset(p, -((long) prevsize));
            unlink(p, bck, fwd);
          }
          //判断next chunk是否是top chunk,就是说判断当前chunk的虚拟地址空间的后面是否是top chunk的初始地址。
          if (nextchunk != av->top) {
            nextinuse = inuse_bit_at_offset(nextchunk, nextsize);
            //如果next不是top chunk,那么当前chunk就开始合并next chunk
            if (!nextinuse) {
              size += nextsize;
              unlink(nextchunk, bck, fwd);
            } else
              clear_inuse_bit_at_offset(nextchunk, 0);//如果next chunk不空闲,那么更新它的inuse状态,因为chunk的是否空闲决定于next chunk(chunk的结构决定)
            //放到unsorted bin中
            first_unsorted = unsorted_bin->fd;
            unsorted_bin->fd = p;
            first_unsorted->bk = p;

            if (!in_smallbin_range (size)) {
              p->fd_nextsize = NULL;
              p->bk_nextsize = NULL;
            }

            set_head(p, size | PREV_INUSE);
            p->bk = unsorted_bin;
            p->fd = first_unsorted;
            set_foot(p, size);
          }
          //如果当前chunk地址空间紧紧挨着top chunk的指针,那么更新top chunk指针就行了,相当于合并了
          else {
            size += nextsize;
            set_head(p, size | PREV_INUSE);
            av->top = p;
          }

        } while ( (p = nextp) != 0);
      }
    } while (fb++ != maxfb);
  }
  else {
    malloc_init_state(av);
    check_malloc_state(av);
  }
}

总结:

    ptmalloc的分配中,fast bin中chunk,通过不清除inuse状态位,防止了free函数,被动的把fast bin中的chunk合并到其他bin中,大大加速连续小块内存分配的速度;fast bin中的chunk在一定条件是还是会被合并到unsorted bin中,然后分配到small bin或者large bin中的,减少内存碎片,有机会满足大块内存的请求。

09-01 22:40