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作为可用空间。