首页 > 编程 > glibc中malloc()的空间overhead

glibc中malloc()的空间overhead

2010年2月13日

在linux下调用malloc()分配内存的时候,实际占用的内存与请求的内存尺寸的关系是什么呢,这个需要研究一下glibc中malloc()的实现。现在常见linux发行版中带的glibc中采用的都是Doug Lea的实现,下面的分析取自他的2.8.4版本的malloc.c

glibc对内存的管理是以chunk为单位的,未分配的chunk之间用双向链表连接成一个环,遍历的时候用指针遍历,已分配的chunk在其首部有chunk的大小,并以此字节数做遍历。每个chunk的首部要放置一个叫做malloc_chunk的struct,故每个chunk的大小至少是这个struct的大小,如果分配的空间或者free的空间大于这个大小,则struct的后面是raw的数据或者是空白空间。chunk的定义如下所示:

struct malloc_chunk {
  size_t               prev_foot;  /* Size of previous chunk (if free).  */
  size_t               head;       /* Size and inuse bits. */
  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;
};

对于已分配的和未分配的chunk,使用的都这个结构,只是用到的成员不一样。对于这两种情况,head变量存放的都是本chunk的尺寸,由于chunk的大小有对齐的规定(见下文),所以head变量的最后三位一定是0的,用不到,所以这三位被做为三个标志位使用,其实本文涉及的是最低位P,它表示当前chunk紧跟着的上一个chunk是不是一个free的chunk,以及倒数第三位A,它表明当前chunk是否被使用中。如果上一个chunk是free的,prev_foot变量就是有用的,它表明了上一个chunk的尺寸,如果上一个chunk也是分配了的,prev_foot变量就是不使用的(在内存上直接和前一个chunk重叠起来,见下文的图示)。如果当前chunk是个空chunk,那么fd和bk两个指针就会分别指向空闲chunk环中的上一个和下一个,如果当前chunk已经分配了,fd和bk所在的内存存放的就是用户实际申请到的数据空间了。

Doug Lea在malloc.c的源代码中画了图来描述实际分配中的内存使用情况,首先是对于已分配的chunk:

chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        | Size of previous chunk (if P = 0)                             |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        | Size of this chunk                                     |1| |P|+
  mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                                                               |
        +-                                                             -+
        |                                                               |
        +-                                                             -+
        |                                                               :
        +-      size - sizeof(size_t) available payload bytes          -+
        :                                                               |
chunk-> +-                                                             -+
        |                                                               |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        | Size of next chunk (may or may not be in use)              |1|+
  mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

图中,chunk箭头所指的位置是malloc_chunk struct的起始位置,mem箭头所指的位置是malloc()等函数返回给用户的指针的位置,也就是实际数据的位置,mem和chunk箭头之前的2*size_t字节的空间可认为是overhead。但是注意第二个chunk,它的上一个chunk也就是第一个chunk是已经分配的,所以它的head字段的P标志位为1,并且它的prev_foot字段其实是不存在的,因为它和第一个chunk的payload数据的最后size_t个字节是重叠的。如果第二个chunk也被分配了的话,它的overhead就是第二个mem箭头上面的那一条当前chunk尺寸(也就是head变量)的那size_t字节的空间。

对于空闲的chuck是这样的:

chunk-> +-                                                             -+
        | User payload (must be in use, or we would have merged!)       |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        | Size of this chunk                                     |0| |P|+
  mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        | Next pointer                                                  |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        | Prev pointer                                                  |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                                                               :
        +-      size - sizeof(struct chunk) unused bytes               -+
        :                                                               |
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        | Size of this chunk                                            |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        | Size of next chunk (must be in use, or we would have merged|0|+
  mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                                                               :
        +- User payload                                                -+
        :                                                               |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

如图中注释所说,两个free的chunk如果是相邻的,会被合并,所以不会存在两个free的chunk相连的情况。(对于较小的刚刚被free的chunk,glibc中存在一种调度算法,把这种小free chunk加入一个叫fastbins的队列管理,这时尽管被free,它们的A标志位会保持为1,因此就算相邻也不会被合并)。

注意图中的第二个chunk,它是一个被分配了的chunk,它的第一个字段prev_foot表示的是第一个free的chunk的大小。其实这个prev_foot变量也是位于上一个chunk的尾部。真正属于第二个chunk的空间还是从“size of the next chunk”开始的,它距离用户数据的空间mem是size_t字节。

综合上面两个例子可以看出,对于一个已分配了的chunk,如果它的上一个chunk也是分配了的,它的prev_foot就是完全被前一个chunk覆盖的;如果它的上一个chunk是未分配的,它的prev_foot存的是该空间chunk的大小,且prev_foot变量位于前一个chunk的最后size_t个字节。这样看来,已分配的chunk的第一个成员prev_foot总是位于别的chunk内的,所以overhead就是head一个变量的大小,即site_t字节。这样一种chunk之间重叠的设计,使得prev_foot与其说是当前chunk的第一个变量,不如说是上一个chunk结尾尺寸标记(从它的名字foot就可以看出这一点)。这使得对于一个空闲chunk来说,其头(自身的header变量)和尾(下一个chunk的prev_foot)都是此空闲chunk的尺寸,这使得从正向两个方向按字节数遍历都很容易,是个不错的设计。

除了上面讨论的overhead以外,chunk的存储还涉及对齐的问题,glibc中规定chunk的以size_t的两倍大小对齐。与此相关的一些代码如下:

#define MALLOC_ALIGNMENT       (2 * SIZE_SZ)  //在我下载的malloc.c中不是这样定义的,而是分情况讨论的
#define CHUNK_ALIGN_MASK    (MALLOC_ALIGNMENT - SIZE_T_ONE)

#define CHUNK_OVERHEAD      (SIZE_T_SIZE)

#define MCHUNK_SIZE         (sizeof(mchunk))

/* The smallest size we can malloc is an aligned minimal chunk */
#define MIN_CHUNK_SIZE\
  ((MCHUNK_SIZE + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)

/* pad request bytes into a usable size */
#define pad_request(req) \
   (((req) + CHUNK_OVERHEAD + CHUNK_ALIGN_MASK) & ~CHUNK_ALIGN_MASK)

/* pad request, checking for minimum (but not maximum) */
#define request2size(req) \
  (((req) < MIN_REQUEST)? MIN_CHUNK_SIZE : pad_request(req))

request2size这个宏汇合了上文的各个因素,给出一个要申请的空间大小,它返回的就是实际分配的内存大小。只申请1个字节的时候,实际至少也要分配malloc_chunk的大小那么多空间,当申请的字节更多直到一个malloc_chunk的空间放不下后,实际空间会以2倍的size_t为步长增长。

这里写了一个程序验证:

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

#define N 1

int main() {
    int i = 0;
    char *p;
    char *p0, *p1;

    size_t *psize;

    for (i = 0; i < 1000000; i++) {
        p = (char*) malloc(N);
        if (i == 0) p0 = p;
        if (i == 1) p1 = p;
    }
    printf("%d\n", p1 - p0);    //看两个chunk的mem指针相差多少

    psize = (size_t*)(p1 - sizeof(size_t));
    printf("%d\n", (*psize) & ~7);    //看head变量的值,& ~7的作用是把后三个标志位过滤掉

    getchar();
    return 0;

}

在32系统下,size_t和指针均为4字节,当N为1至12时,程序的内存占用为16M,当N为13时,程序占用内存涨到24M。
在64系统下,size_t和指针均为8字节,当N为1至24时,程序的内存占用为32M,当N为25时,程序占用内存涨到48M。

上述程序在centos 5.3下,gcc 4.1.2下测试通过。另外,由于C++的new操作底层调用的也是malloc,所以上述讨论对new同样适用。

最后附上本文主要的参考材料,一个讲述glibc的pdf和malloc.c源代码。

Understanding the heap by breaking it
malloc.c

编程

  1. yifei
    2010年2月13日21:43 | #1

    占座研究,赞一个,大年三十研究技术~

  2. mmx
    2010年2月20日17:27 | #2

    很仔细啊

  3. Ray
    2010年3月2日22:08 | #3

    赞,解释很详细

  1. 目前还没有任何 trackbacks 和 pingbacks.