Glibc 的 malloc 源代码分析
有人写了一个测试程序
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <malloc.h>
main()
{
int alloc_time = 20000;
char* a[alloc_time];
char* b[alloc_time];
for(int j=0; j<5; j++)
{
for(int i=0; i<alloc_time; i++)
{
a[i] = (char*)malloc(52722);
memset(a[i], 1, 52722);
b[i] = (char*)malloc(1);
memset(b[i], 1, 1);
}
for(int i=0; i<alloc_time; i++)
{
free(a[i]);
free(b[i]);
}
}
while(1)
{
sleep(10);
}
}
发现 该程序在测试机上运行会占用 1G 内存，不释放，为了解决这个问题，特别去研究了一下glibc 中malloc 的源代码。
一．对于小于 128k 的块在 heap 中分配。
1. 堆是通过 brk 的方式来增长或压缩的，如果在现有的堆中不能找到合适的 chunk ，会通过增长堆的方式来满足分配，如果堆顶的空闲块超过一定的阀值会收缩堆，所以只要堆顶的空间没释放，堆是一直不会收缩的。
2. 堆中的分配信息是通过两个方式来记录。
第一．是通过 chunk 的头， chunk 中的头一个字是记录前一个 chunk 的大小，第二个字是记录当前 chunk 的大小和一些标志位，从第三个字开始是要使用的内存。所以通过内存地址可以找到 chunk ，通过 chunk 也可以找到内存地址。还可以找到相邻的下一个 chunk ，和相邻的前一个 chunk 。一个堆完全是由 n 个 chunk 组成 。
第二．是由 3 种队列记录 ，只用空闲 chunk 才会出现在队列中，使用的 chunk 不会出现在队列中。如果内存块是空闲的它会挂到其中一个队列中，它是通过内存复用的方式，使用空闲 chunk 的第 3 个字和第 4 个字当作它的前链和后链（变长块是第 5 个字和第 6 个字），省的再分配空间给它。
第一种队列是 bins ， bins 有 128 个队列，前 64 个队列是定长的，每隔 8 个字节大小的块分配在一个队列，后面的 64 个队列是不定长的，就是在一个范围长度的都分配在一个队列中。所有长度小于 512 字节（大约）的都分配在定长的队列中 。后面的 64 个队列是变长的队列，每个队列中的 chunk 都是从小到大排列的。
第二种队列是 unsort 队列（只有一个队列），（是一个缓冲）所有 free 下来的如果要进入 bins 队列中都要经过 unsort 队列。
第三种队列是 fastbins ，大约有 10 个定长队列，（是一个高速缓冲）所有 free 下来的并且长度是小于 80 的 chunk 就会进入这种队列中。进入此队列的 chunk 在 free 的时候并不修改使用位，目的是为了避免被相邻的块合并掉。
3.malloc 的步骤
l 先在 fastbins 中找，如果能找到，从队列中取下后（不需要再置使用位为 1 了）立刻返回。
l 判断需求的块是否在小箱子 （ bins 的前 64 个 bin ）范围，如果在小箱子的范围，并且刚好有需求的块，则直接返回内存地址；如果范围在大箱子（ bins 的后 64 个 bin ）里，则触发 consolidate 。（因为在大箱子找一般都要切割，所以要优先合并，避免过多碎片）
l 然后在 unsort 中取出一个 chunk ，如果能找到刚好和想要的 chunk 相同大小的 chunk ，立刻返回，如果不是想要 chunk 大小的 chunk ，就把他插入到 bins 对应的队列中去。转 3 ，直到清空，或者一次循环了 10000 次。
l 然后才在 bins 中找，找到一个最小的能符合需求的 chunk 从队列中取下，如果剩下的大小还能建一个 chunk ，就把 chunk 分成两个部分，把剩下的 chunk 插入到 unsort 队列中去，把 chunk 的内存地址返回。
l 在 topchunk （是堆顶的一个 chunk ，不会放到任何一个队列里的）找，如果能切出符合要求的，把剩下的一部分当作 topchunk ，然后返回内存地址。
l 如果 fastbins 不为空，触发 consolidate 即把所有的 fanbins 清空 （是把 fanbins 的使用位置 0 ，把相邻的块合并起来，然后挂到 unsort 队列中去），然后继续第 3 步。
l 还找不到话就调用 sysalloc ，其实就是增长堆了。然后返回内存地址。
4.free 的步骤
l 如果和 topchunk 相邻，直接和 topchunk 合并，不会放到其他的空闲队列中去。
l 如果释放的大小小于 80 字节，就把它挂到 fastbins 中去，使用位仍然为 1 ，当然更不会去合并相邻块。
l 如果释放块大小介于 80-128k ，把 chunk 的使用位置成 0 ，然后试图合并相邻块，挂到 unsort 队列中去，如果合并后的大小大于 64k ，也会触发 consolidate ，（可能是周围比较多小块了吧），然后才试图去收缩堆。（收缩堆的条件是当前 free 的块大小加上前后能合并 chunk 的大小大于 64k ，并且要堆顶的大小要达到阀值，才有可能收缩堆）
l 对于大于 128k 的块，直接 munmap
二．大于 128k 的块通过 mmap 的方式来分配。
根据以上的分析，我们可以得出为什么会还占用 1G 的内存。
测试程序有两重循环，内层循环先分配 1G ，然后全部释放，外层执行这个步骤 5 次，但为什么最后一次释放会不成功呢。
主要是因为按照这个程序分配后，内存变成由小块和大块交替出现，释放小块的时候，直接把小块放到 fastbins 中去，而且他的使用位还是 1 ，释放大块的时候，它试图合并相邻的块，但是和它相邻的块的使用位还是 1 ，所以它不能把相邻的块合并去来，而且释放的块的大小小于 64k ，也不会触发 consolidate ，即不会把 fastbins 清空 ，所以当所有的块都被释放完后，所有的小块都在 fastbins 里面，使用位都为 1 ，大块都挂在 unsort 队列里面。全部都无法合并。所以使用的堆更加无法压缩。
如果在外循环后面再分配 2000 字节然后释放的话，所有内存将全部清空。这是因为在申请 2000 字节的时候，由 malloc 的第二步，程序会先调用 consolidate ，即把所有的 fastbins 清空，同时把相邻的块合并起来，等到所有的 fastbins 清空的时候，所有的块也被合并去来了，然后调用 free2000 字节的时候，这块被将被合并起来 ，成为 topchunk ，并且大小远大于 64k ，所有堆将会收缩，内存归还给系统。
转帖自：http://blog.chinaunix.net/u3/94916/showart_1908306.html