Glibc中的内存分配器

时间：2010-06-28 来源：星巴

Glibc最初基于Doug Lea的算法实现了malloc从而对Linux系统的堆进行了管理，高版本的Glibc使用了ptmalloc，后者使用了fastbin机制，以更高的效率进行内存分配。首先，我尝试翻译一下<<A memory allocator>>中的算法段(http://g.oswego.edu/dl/html/malloc.html) ==================================================================================

算法

malloc算法中有两部分内容一直没有变化

边界标记

内存中的所有chunk的头尾中包含他们的大小信息，这些信息有以下重要的功能：

相邻的不用的chunk可以组合成一个大的chunk，这将减小一些小的不可用的chunk块
根据已知的一个chunk信息可以以正反两个方向遍历所有的chunk块

malloc算法中最开始的版本以这种方式实现了边界标记，因为在一个活动的chunk中不需要使用到尾部字段，因此最近的版本在程序中省略了chunk中的尾部字段，删减它们也减少了内存空间的浪费，但是，缺少这些域对于自身的错误检测是比较不利的。

打包(binning)

所有可供使用的chunk块根据不同的大小在chunk箱中保存，因此，这里会有一共128个固定大小的容纳箱，对于小于512字节的容纳箱，他们每个都有一个固定的大小（空间间隔8个字节，简单地以8字节对齐）。收纳箱的查找以最小、最适合为先的顺序，我们知道，与其它通用算法如first-fit比较，这种算法对实际有效负载而言会有更少的碎片，性能更好。

在1995之前，容纳箱中的chunk是不进行排序的，因此，只是大体上实现best-fit策略，在近几年的版本中，根据chunk的大小进行了排序。 ================================================================================== 在Glibc中，当要求分配的内存小于128k时，Glibc通过brk的方式直接从堆中分配，而对大于128k的要求，则使用mmap解决，这点从malloc出来的地址值可以看出。 Glibc的内存管理以chunk为单位，如下所示：

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

虽然对于已分配或空闲的chunk都使用相同的结构，但是用到的成员却不相同，这点从《Glibc中malloc内存分配内幕》可看到，下面这段话摘自一篇文章，详细说明了堆中分配信息的记录方式：

第一．是通过chunk的头，chunk中的头一个字是记录前一个chunk的大小，第二个字是记录当前chunk的大小和一些标志位，从第三个字开始是要使用的内存。所以通过内存地址可以找到chunk，通过chunk也可以找到内存地址。还可以找到相邻的下一个chunk，和相邻的前一个chunk。一个堆完全是由n个chunk组成。

第二．是由3种队列记录，只用空闲chunk才会出现在队列中，使用的chunk不会出现在队列中。如果内存块是空闲的它会挂到其中一个队列中，它是通过内存复用的方式，使用空闲chunk的第3个字和第4个字当作它的前链和后链（变长块是第5个字和第6个字），省的再分配空间给它。

第一种队列是bins，bins有128个队列，前64个队列是定长的（不超过512字节），每隔8个字节大小的块分配在一个队列，后面的64个队列是不定长的，就是在一个范围长度的都分配在一个队列中。所有长度小于512字节（大约）的都分配在定长的队列中。后面的64个队列是变长的队列，每个队列中的chunk都是从小到大排列的。

第二种队列是unsort队列（只有一个队列），（是一个缓冲）所有free下来的如果要进入bins队列中都要经过unsort队列。

第三种队列是fastbins，大约有10个定长队列，（是一个高速缓冲）所有free下来的并且长度是小于80的chunk就会进入这种队列中。进入此队列的chunk在free的时候并不修改使用位，目的是为了避免被相邻的块合并掉。

从以上所有信息可以看到，malloc申请空间时，除了用户指明的长度大小外，Glibc还需要额外的空间保存分配信息，即chunk，为此，引入一个有趣的话题，在Glibc中，malloc(0)会有怎么样的结果？为弄清楚其结果，我们还需要了解一个malloc引入的叫内存对齐的概念，这里的对齐是指在动态分配内存时，最终分配的内存是2的N次幂，因此，malloc消耗的内存除了chunk所占空间外还有对齐所花费的空间，malloc.c中以MINSIZE代表申请内存的最小空间，在32们系统中，该值为16字节。因此，在Glibc中，malloc(0)所占空间为16字节，而在uClibc中，编译时可以对malloc(0)的返回值进行控制。