dlmalloc解析连载【完整文档见第12楼】

lenky0401

原帖由 lenky0401 于 2009-5-27 17:29 发表
  好了 呵呵

完整文档见第12楼

离去公司上班还有一个来月时间，最近又比较闲散，空闲时间比较多，因此自己专研了一些东西，发点个人总结在这，希望可以和大家一起讨论。
好了，废话少说，开始我的【dlmalloc解析连载】，这个对dlmalloc的解析针对Doug Lea Malloc的最新版Version 2.8.3，已经发布在我的个人博客，不过还是想转帖过来让更多的人讨论，因为如果有错误的话，希望可以得到大家的指点。

dlmalloc解析连载一

dlmalloc是目前一个十分流行的内存分配器，其由Doug Lea（主页为http://gee.cs.oswego.edu/）从1987年开始编写，到目前为止，最新版本为2.8.3（可以从ftp://g.oswego.edu/pub/misc/malloc.c获取），由于其高效率等特点被广泛的使用（比如一些linux系统等用的就是dlmalloc或其变形，比如ptmalloc，主页为http://www.malloc.de/en/index.html）和研究（各位可以搜索关键字“GCspy”）。
dlmalloc的实现只有一个源文件（还有一个头文件），大概5000行，其内注释占了大量篇幅，由于有这么多注释存在的情况下，表面上看上去很容易懂，的确如此，在不追求细节的情况，对其大致思想的确很容易了解（没错，就只是了解而已），但是dlmalloc作为一个高品质的佳作，实现上使用了非常多的技巧，在实现细节上不花费一定的精力是没有办法深入理解其为什么这么做，这么做的好处在哪，只有当真正读懂后回味起来才发现它是如此美妙。
lenky0401个人博客将陆续推出对dlmalloc的解析（针对Doug Lea Malloc的最新版Version 2.8.3，未做说明的情况下以32位平台，8字节对齐作为假定平台环境设置考虑），由于个人水平有限，因此也不能完全保证对dlmalloc的所有理解都准备无误, 但是所有内容均出自个人的理解而并非存心妄自揣测来愚人耳目，所以如果读者发现其中有什么错误，请勿见怪，如果可以则请来信告之，并欢迎来信讨论（lenky0401@163.com）。
描述的内容不会包含dlmalloc全部代码，但会将这其中涉及到的一些技巧尽量讲出，我相信对dlmalloc源代码不感兴趣的朋友也可以学到这些独立的技巧而使用在自己的编程实践中。
最后，转载请保留本博客地址连接[http://lenky0401.cublog.cn]，谢谢。
===========================================================

Dlmalloc将内存分成很多块，并且采用所谓的边界标记法对内存进行管理，在Dlmalloc的实现源码中定义了两种结构体malloc_chunk和malloc_tree_chunk，从它们的定义中可以看到结构体malloc_tree_chunk除了比malloc_chunk多三个字段以外，前四个字段和malloc_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;
};
typedef struct malloc_chunk  mchunk;
typedef struct malloc_chunk* mchunkptr;
typedef struct malloc_chunk* sbinptr;  /* The type of bins of chunks */
struct malloc_tree_chunk {
  /* The first four fields must be compatible with malloc_chunk */
  size_t                    prev_foot;
  size_t                    head;
  struct malloc_tree_chunk* fd;
  struct malloc_tree_chunk* bk;
  struct malloc_tree_chunk* child[2];
  struct malloc_tree_chunk* parent;
  bindex_t                  index;
};

我们先来看看只考虑使用结构体malloc_chunk管理内存的情况（内存都被分为小块，32位机器上即是256字节以下，而对于结构体malloc_tree_chunk，其管理的是大块，32位机器上即是256字节以上）：


按照边界标记法，结构体malloc_chunk通过字段head和prev_foot将内存分割成很多块，从图中①所示，可以看到某结构体内的prev_foot是记录的前一个chunk块的信息（事实上是前一个chunk块的大小），因此我们可以利用如下宏：
#define prev_chunk(p) ((mchunkptr)( ((char*)(p)) - ((p)->prev_foot) ))
来获得前一个chunk块的malloc_chunk结构体指针。
指针fd、bk只有当该chunk块空闲时才存在，其作用时用于加入到空闲chunk块链中统一管理，而如果该chunk块被分配给应用程序使用，那么这两个指针也就没有用（该已经chunk块从空闲链中拆出）了，所以也当作应用程序的使用空间，而不至于浪费，图中②所示。
head字段记录与本chunk块的相关信息，这包括本chunk块大小，本块是否在使用中，前一chunk块是否在使用中。
head一个字段就能存储这么多信息是因为Dlmalloc在分割内存的时候总是以地址对齐（默认是8字节，可以自由设置，但是8字节是最小值并且设置的值必须是2为底的幂函数值，即是alignment = 2^n，n为整数且n>=3）的方式来进行的，所以用head来存储本chunk块大小字节数的话，其末3bit位总是0，因此这三位可以用来存储其它信息，比如：
以第0位作为标志位，标记前一chunk块是否在使用中，为1表示使用，为0表示空闲。
以第1位作为标志位，标记本chunk块是否在使用中，为1表示使用，为0表示空闲。
我们来看看它们的各自相关判断代码：
#define SIZE_T_ONE          ((size_t)1)
#define SIZE_T_TWO          ((size_t)2)
#define PINUSE_BIT          (SIZE_T_ONE)
#define CINUSE_BIT          (SIZE_T_TWO)
#define cinuse(p)           ((p)->head & CINUSE_BIT)
#define pinuse(p)           ((p)->head & PINUSE_BIT)
对于前面说的prev_foot字段，也利用了其一个空闲位用于标记该chunk块是否右mmap分配，于此类似，所以就不多说了，感兴趣的可以查看源码。
对于结构体malloc_tree_chunk，其实在内存分割上合结构体malloc_chunk完全一致，因为它们的前四个字段完全一样（事实上只有两个字段prev_foot和head起边界标记作用），其它的字段都是用于空闲链管理的。
本篇简单的把Dlmalloc如果按照边界标记法分割内存描述了一下，下篇继续两种空闲链的各自管理分析。

[ 本帖最后由 lenky0401 于 2009-5-27 17:30 编辑 ]

lenky0401

dlmalloc解析连载二

前面连载提到过对于大小在256字节以下的chunk块是通过malloc_chunk组织管理的，256字节以下的chunk块一共有256/8=32类，即字节为8字节、16字节、24字节、32字节，……，256字节，因此dlmalloc维护32个双向环形链表（而且具有链表头节点，加头节点的最大作用就是便于对链表内节点的统一处理，即简化编程），每一个链表里的各空闲chunk块的大小一致，因此当应用程序需要某个字节大小（这里的字节大小是考虑了chunk块头和对齐等所占空间了的，即如果应用如果程序调用函数malloc( 8 )，那么到dlmalloc这应该比8大，这种更细节的疑问下面还有，并非我故意不表达，只是转述太多了，倒说不清我自己真正想说的了，阅读时请读者自己注意就好）的内存空间时直接在对应的链表内取就可以了（具体稍有不同，即如果对应链表内没有空闲可用chunk块，则还会查看下一个链表，举个例子：当应用程序申请32个字节，如果32字节大小的链表为空，那么dlmalloc还会在大小为40字节的链表内查找空闲chunk块。），这样既可以很好的满足应用程序的内存空间申请请求而又不会出现太多的内存碎片。我们可以用如下图来表示dlmalloc对256字节以下的空闲chunk块组织方式。

dlmalloc程序使用smallbins数组来记录这32个双向环形链表表头，该字段定义在结构体malloc_state内，在这里我们先不管malloc_state结构体而只关注smallbins这个字段，它的定义如下：
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;
};

mchunkptr
smallbins[(NSMALLBINS+1)*2];
最后，至于为什么是66个数组元素而不是64或65，这个仔细想想也好理解，好了，就到这，下篇继续吧。
其中，mchunkptr在上一小节已经提过，为“typedef struct malloc_chunk* mchunkptr;”，而宏NSMALLBINS为32，即是“#define NSMALLBINS (32U)”。因此smallbins为一个具有66个malloc_chunk结构体指针元素的数组，为什么是66个呢？不是32就可以了么？这里Doug Lea使用了一个技巧，如果按照我们的常规想法，也许会申请32个malloc_chunk结构体指针元素的数组，然后再给链表申请一个头节点（即32个），再让每个指针元素正确指向而形成32个具有头节点的链表。事实上，对于malloc_chunk类型的链表“头节点”，其内的prev_foot和head字段是没有任何实际作用的，因此这两个字段所占空间如果不合理使用的话那就是白白的浪费。我们再来看一看66个malloc_chunk结构体指针元素的数组占了多少内存空间呢？结果为66*4=264字节。而32个malloc_chunk类型的链表“头节点”需要多少内存呢？32*16=512，真的是512么？不是，刚才不是说了，prev_foot和head这两个字段是没有任何实际作用的，因此完全可以被重用（覆盖），因此实际需要内存为32*8=256。264大于256（事实上前8个字节被浪费掉了），那么这66个malloc_chunk结构体指针元素数组所占内存空间就可以存储这32个头节点了，事实上Doug Lea也是这么做的。我们来看下于此相关的这一句代码：

#define smallbin_at(M, i)   ((sbinptr)((char*)&((M)->smallbins[(i)<<1])))

其中的sbinptr也是个malloc_chunk结构体指针类型（typedef struct malloc_chunk* sbinptr;），M表示前面提到的结构体malloc_state，各位仔细体会一下这句代码中的强制转换就会理解这种技巧了。
转载请保留本博客地址连接[http://lenky0401.cublog.cn]，谢谢。

[ 本帖最后由 lenky0401 于 2009-6-2 12:24 编辑 ]

xinglp

gawk

看看

blackuhlan

赶上直播了说，强帖留名，楼主继续，先留名再研究下

lenky0401

dlmalloc解析连载三
上一篇讨论了dlmalloc对大小在256字节以下的chunk块进行的组织管理，本篇我们再来看看对于大小在256字节以上的chunk块，dlmalloc是如何管理的。
对于大小在256字节以上的chunk块，dlmalloc也采用了所谓的分箱机制，不过由于大于256的数目有很多，因此这里的分箱不能够像对于0到256这个有限区间的分箱来得简单。具体来说如下表：

字节范围	范围大小	箱号
[256, 384)	128	0
[384, 512)	128	1
[512, 76	256	2
[768, 1024)	256	3
[1024, 1536)	512	4
[1536, 204	512	5
[2048, 3072)	1024	6
[3072, 4096)	1024	7
[4096, 6144)	2048	8
[6144, 8192)	2048	9
[8192, 1228	4096	10
[12288, 16384)	4096	11
[16384, 24576)	8192	12
[24576, 3276	8192	13
[32768, 49152)	16384	14
[49152, 65536)	16384	15
[65536, 98304)	32768	16
[98304, 131072)	32768	17
[131072, 19660	65536	18
[196608, 262144)	65536	19
[262144, 393216)	131072	20
[393216, 52428	131072	21
[524288, 786432)	262144	22
[786432, 1048576)	262144	23
[1048576, 1572864)	524288	24
[1572864, 2097152)	524288	25
[2097152, 314572	1048576	26
[4194304, 4194304)	1048576	27
[4194304, 6291456)	2097152	28
[6291456, 838860	2097152	29
[8388608, 12582912)	4194304	30
[12582912, 理论上无穷大)	理论上无穷大	31

这个表格里的数字是我先用程序打印出来然后再拷贝过来的，先简单解释一下，第一列“字节范围”表示大小在该范围内chunk块被分配到改行对应的第三列“箱号”所指定的箱子内。第二列表示第一列“字节范围”的范围大小，各位可以看到它们很有规律，在后面我们会讲到这种规律性的作用，因此这里也就先给出来。另外，这种规律性也就是这样分箱的分法，相比上一篇中的那种直接按8、16、24、32…这种确定值的分箱方法相对较为复杂，这里是将一个区间内的值分到一个箱子内，正因如此，对于箱内chunk块的管理也就不能再简单的使用双向链表而是使用树（实际上在具体实现上为Trie树，不过和课本上的那种字典Trie树不一样，Doug Lea给出的注释称之为“bitwise digital trees (aka tries)”，要怎么去把它讲清楚还真不简单啊，试着按照从抽象概念到实现细节的方式来说明吧，另外姑且称这种树为dltree树）结构，当然这种树不是随意的，它具有它自身的最简单规则：①任何节点的左子树上所有节点值均小于它的右子树上所有节点值。②任何节点值和它的左（右）子树上所有节点值不存在确定排序关系。这是直白的描述，如果用更严谨的表述则为如下：
dltree树或者是一颗空树；或者是具有下列性质的二叉树：
（1）若左子树和右子树都不空，则左子树上所有结点的值均小于右子树上所有结点的值；
（2）左、右子树也分别为dltree树；

       每一个箱子里的chunk块都被以dltree树结构组织起来，分了32个箱号，因此dlmalloc具有32个dltree树，记录该32个dltree树根节点的指针变量也定义在结构体malloc_state内，如下：
tbinptr
treebins[NTREEBINS];
#define NTREEBINS (32U)
typedef struct malloc_tree_chunk* tbinptr; /* The type of bins of trees */
其中NTREEBINS为常量宏，类型tbinptr为malloc_tree_chunk结构体指针，数组的32个指针元素指向32个分箱内各个dltree树的根节点，因此通过结构体malloc_state类型变量很方便的找到各种chunk块大小范围的树结构。




         下面讨论具体一棵dltree树的组织情况（就以0号箱管理的树为例），根据dltree树中左子树小于右子树的性质，字节[256, 384)范围被按如下规则划分给0号箱管理的dltree树组织：
         根的左子树T1管理[256, 320)，右子树T2管理[320, 384)，即各管理64字节范围。
       树T1的左子树T3管理[256, 28，树T1的右子树T4管理[288, 320)，即各管理32字节范围。树T2类似。
       树T3的左子树T7管理[256, 272)，树T3的右子树T8管理[272, 28，即各管理16字节范围。其它树类似。
       ……
      

       通过这种分法，任一号箱的字节范围被对应在一颗树上，在查找某一大小的空闲chunk时则按照这种规律来进行“快速”搜索，比如应用程序malloc( 278 )，则由于278在[256, 320)范围内，因此先进入树T1，接着由于278在[256, 288)范围内，因此由进入T3，接着进入T8，……。
       之所以说这种搜索是“快速”的，因为这里的范围划为很巧妙，我们来看一下各字节范围用二进制表示的情况：
       根节点T的左子树T1 [256, 320)为：

[1 0000 0000
1 00xx xxxx]
       而根节点T的右子树T2 [320, 384)为：

[1 01xx xxxx
1 01xx xxxx]
       其中的x表示为1或者0，可以看到T1和T2的管理范围很好区分，即通过判断第6bit位是否为1即可。为1表示在右子树T2范围内，为0表示在左子树T1范围内。

       再来看看树T1的左子树T3和右子树T4情况：

T3管理[256, 288)为：

[1 0000 0000
1 000x xxxx]

T4管理[288, 320)为：

[1 0010 0000
1 001x xxxx]
       可以看到T3和T4的管理范围也很好区分，即通过判断第5bit位是否为1即可。为1表示在右子树T4范围内，为0表示在左子树T3范围内。

       其它的类似……。因此，我们在查找某字节在哪个范围内的树上只需要顺序的比较各bit位就可以了，对比Trie树，我们可以认为dltree是关键码只有0和1的Trie树。

daybreakcx

又更新了啊，刚才去你的blog看了看，支持你

blackuhlan

只所以对其必须是8字节或以上是应为head的低2位用来表示状态了，所以有效位是从第3位开始的。2^3=8

blackuhlan

>4k范围稍显大了点,对于现代的应用来说，不过想了下，如果加大范围的话，0号箱直接管理范围为256字节的怎么样，以此类退。不过真是佩服作者的想象力 啊

sashion

dlmalloc 在实际的C/C++编程中有什么用呢？
关注中 。。。