全部博文（22）
分类： C/C++
2009-05-23 10:27:24
上一篇讨论了dlmalloc对大小在256字节以下的chunk块进行的组织管理，本篇我们再来看看对于大小在256字节以上的chunk块，dlmalloc是如何管理的。
对于大小在256字节以上的chunk块，dlmalloc也采用了所谓的分箱机制，不过由于大于256的数目有很多，因此这里的分箱不能够像对于0到256这个有限区间的分箱来得简单。具体来说如下表：
|
字节范围 |
范围大小 |
箱号 |
|
[256, 384) |
128 |
0 |
|
[384, 512) |
128 |
1 |
|
[512, 768) |
256 |
2 |
|
[768, 1024) |
256 |
3 |
|
[1024, 1536) |
512 |
4 |
|
[1536, 2048) |
512 |
5 |
|
[2048, 3072) |
1024 |
6 |
|
[3072, 4096) |
1024 |
7 |
|
[4096, 6144) |
2048 |
8 |
|
[6144, 8192) |
2048 |
9 |
|
[8192, 12288) |
4096 |
10 |
|
[12288, 16384) |
4096 |
11 |
|
[16384, 24576) |
8192 |
12 |
|
[24576, 32768) |
8192 |
13 |
|
[32768, 49152) |
16384 |
14 |
|
[49152, 65536) |
16384 |
15 |
|
[65536, 98304) |
32768 |
16 |
|
[98304, 131072) |
32768 |
17 |
|
[131072, 196608) |
65536 |
18 |
|
[196608, 262144) |
65536 |
19 |
|
[262144, 393216) |
131072 |
20 |
|
[393216, 524288) |
131072 |
21 |
|
[524288, 786432) |
262144 |
22 |
|
[786432, 1048576) |
262144 |
23 |
|
[1048576, 1572864) |
524288 |
24 |
|
[1572864, 2097152) |
524288 |
25 |
|
[2097152, 3145728) |
1048576 |
26 |
|
[4194304, 4194304) |
1048576 |
27 |
|
[4194304, 6291456) |
2097152 |
28 |
|
[6291456, 8388608) |
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, 288)，树T1的右子树T4管理[288, 320)，即各管理32字节范围。树T2类似。
树T3的左子树T7管理[256, 272)，树T3的右子树T8管理[272, 288)，即各管理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树。
还有其他细节，比如当应用程序申请某一字节的内存空间，而该字节所属范围tree不存在时则只有在更接近该范围的tree内申请节点，这些都是具体实现，后面会具体讲到吧。
转载请保留本博客地址连接[http://lenky0401.cublog.cn]，谢谢。
