• 博客访问: 395938
  • 博文数量: 36
  • 博客积分: 330
  • 博客等级: 一等列兵
  • 技术积分: 2992
  • 用 户 组: 普通用户
  • 注册时间: 2012-09-05 22:38
个人简介

java开发工程师,专注于内核源码,算法,数据结构。 qq:630501400

文章分类
文章存档

2014年(2)

2013年(25)

2012年(9)

微信关注

IT168企业级官微



微信号:IT168qiye



系统架构师大会



微信号:SACC2013

订阅
热词专题

分类: C/C++

malloc_chunk边界标记法和空间复用

边界标记法

    ptmalloc分配的空间统一用了malloc_chunk结构来管理,malloc_chunk的结构初看比较奇葩,看了注释,分析了一段时间的代码,发现这种边界标记的设计,在malloc_chunk虚拟地址都是彼此相邻的情况下,是十分高效的。

malloc_chunk结构:

struct malloc_chunk {

  INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */ //整个结构体的大小,包括结构体数据和后面可用的空间的大小

  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;

  /* Only used for large blocks: pointer to next larger size.  */ //后面用large bin再考虑
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

    首先我们要清楚,malloc_chunk都是虚拟地址相连的,这样我们需要知道一个chunk相邻chunk的地址。每个malloc_chunk都包括自身的size,又包括虚拟地址前面的那个malloc_chunk,这里不需要记录后面malloc_chunk的size,因为后面的首地址就是当前malloc_chunk的首地址+size,prev_size在前面的chunk如果是空闲的时候才是可用的。如果前面的chunk是正在被使用的,那么这个prev_size的空间则被前面的chunk所征用。如果当前chunk是使用中的,那么fd,bk,fd_nextsize,bk_nextsize,都是无效的,它们都是关于空闲链表的指针,那么这些指针的空间全部被认为是空闲空间。 ptmalloc中的注释画出了空闲malloc_chunk和已分配的malloc_chunk的结构。

空闲chunk的结构:

    上图中是空闲chunk的结构示意图,从图中可以看出当前malloc_chunk的指针是chunk指针,如果想得到地址相邻前面的指针,只需要chunk-prev_size即可。得到地址相邻后面的指针,chunk+size。其中fd,bk指针是bin中的空闲双向链表。这种通过prev_size可以使malloc_chunk的合并过程非常迅速。

    从代码中看下空闲chunk的合并过程,还是malloc_consolidate里面函数的片段:

//合并前面的
      if (!prev_inuse(p)) {
        prevsize = p->prev_size;
        size += prevsize;
        p = chunk_at_offset(p, -((long) prevsize));
        unlink(p, bck, fwd);
      }
//合并后面的
      if (nextchunk != av->top) {
        nextinuse = inuse_bit_at_offset(nextchunk, nextsize);
        if (!nextinuse) {
          size += nextsize;
          unlink(nextchunk, bck, fwd);

    从代码中可以看出来,合并前面的malloc_chunk过程中,可以看到不用获得前面malloc_chunk的指针,合并的过程大概就是当前的chunk指针挪动到前面的位置,同时更新size,把chunk指针从相应的bin双向链表中干掉;从合并过程中可以看到,我们只是用到了prev_size,并没有用前面的chunk的指针,如果有前面chunk的指针,那么合并过程肯定还是需要这个chunk的size的。所以这里只用到prev_size加快合并的速度。向prev方向合并需要更新size和chunk指针,向next方向合并,只要更新size就行。

空间复用

    malloc_chunk来说size是必须的,标志了这个chunk的大小,来决定是否满足malloc的要求,那么对于空闲的malloc_chunk来说fd,bk,fd_nextsize,bk_nextsize是必须的,bin中的空闲双链表;对于非空闲的malloc_chunk来说,fd,bk,fd_nextsize,bk_nextsize是没有用的,所以这部分空间被作为了可用的空间。那么prev_size就比较复杂了,它的状态取决于虚拟地址相邻前面的chunk的状态,如果前面的chunk是使用状态,那么这个chunk的prev_size就没有意义了,也没有合并的必要了,所以就不需要知道前面chunk指针的位置了,所以这个变量的空间被前面的chunk征用了。

使用状态的chunk

    malloc请求的size,要加上结构体的数据大小才和malloc_chunk的size有可比性。

 #define request2size(req)                                       
  (((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE)  ?           
   MINSIZE :                                                    
   ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)
 

    从上面的宏可以看出实际请求的大小是req再加上size_t然后对齐,这里prev_size和size不是应该2*size_t么,但是还要计算上next chunk赠送的prev_size的size_t。

总结

从上面的分析可以看出malloc_chunk设计是巧妙的,prev_size字段可以通过它来找到地址相邻空闲的上一个chunk,使得合并空闲的chunk十分方便,同时如果当前chunk的前一个chunk是使用中的,prev_size的空间可以借给上一个chunk作为可用空间。

阅读(4508) | 评论(0) | 转发(1) |
0

上一篇:ptmalloc中的fastbin chunk的合并过程

下一篇:没有了

给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册