.2.2
Large bins
在
SIZE_SZ
为
4B
的平台上,大于等于
512B
的空闲
chunk
,或者,在
SIZE_SZ
为
8B
的平台上,大小大于等于
1024B
的空闲
chunk
,由
sorted bins
管理。
Large bins
一共包括
63
个
bin
,每个
bin
中的
chunk
大小不是一个固定公差的等差数列,而是分成
6
组
bin
,每组
bin
是一个固定公差的等差数列,每组的
bin
数量依次为
32
、
16
、
8
、
4
、
2
、
1
,公差依次为
64B
、
512B
、
4096B
、
32768B
、
262144B
等。
以
SIZE_SZ
为
4B
的平台为例,第一个
large
bin
的起始
chunk
大小为
512B
,共
32
个
bin
,公差为
64B
,等差数列满足如下关系:
Chunk_size=512 +
64 * index
第二个
large bin
的起始
chunk
大小为第一组
bin
的结束
chunk
大小,满足如下关系:
Chunk_size=512 +
64 * 32 + 512 * index
同理,我们可计算出每个
bin
的起始
chunk
大小和结束
chunk
大小。这些
bin
都是很有规律的,其实
small
bins
也是满足类似规律,
small bins
可以看着是公差为
8
的等差数列,一共有
64
个
bin
(第
0
和
1bin
不存在),所以我们可以将
small bins
和
large bins
存放在同一个包含
128
个
chunk
的数组上,数组的前一部分位
small bins
,后一部分为
large bins
,每个
bin
的
index
为
chunk
数组的下标,于是,我们可以根据数组下标计算出该
bin
的
chunk
大小(
small bins
)或是
chunk
大小范围(
large bins
),也可以根据需要分配内存块大小计算出所需
chunk
所属
bin
的
index
,
ptmalloc
使用了一组宏巧妙的实现了这种计算。
#define NBINS 128
#define NSMALLBINS 64
#define SMALLBIN_WIDTH MALLOC_ALIGNMENT
#define MIN_LARGE_SIZE (NSMALLBINS * SMALLBIN_WIDTH)
#define in_smallbin_range(sz) \
((unsigned long)(sz) < (unsigned long)MIN_LARGE_SIZE)
#define smallbin_index(sz) \
(SMALLBIN_WIDTH == 16 ? (((unsigned)(sz)) >> 4) : (((unsigned)(sz)) >> 3))
#define largebin_index_32(sz) \
(((((unsigned long)(sz)) >> 6) <= 38)? 56 + (((unsigned long)(sz)) >> 6): \
((((unsigned long)(sz)) >> 9) <= 20)? 91 + (((unsigned long)(sz)) >> 9): \
((((unsigned long)(sz)) >> 12) <= 10)? 110 + (((unsigned long)(sz)) >> 12): \
((((unsigned long)(sz)) >> 15) <= 4)? 119 + (((unsigned long)(sz)) >> 15): \
((((unsigned long)(sz)) >> 18) <= 2)? 124 + (((unsigned long)(sz)) >> 18): \
126)
// XXX It remains to be seen whether it is good to keep the widths of
// XXX the buckets the same or whether it should be scaled by a factor
// XXX of two as well.
#define largebin_index_64(sz) \
(((((unsigned long)(sz)) >> 6) <= 48)? 48 + (((unsigned long)(sz)) >> 6): \
((((unsigned long)(sz)) >> 9) <= 20)? 91 + (((unsigned long)(sz)) >> 9): \
((((unsigned long)(sz)) >> 12) <= 10)? 110 + (((unsigned long)(sz)) >> 12): \
((((unsigned long)(sz)) >> 15) <= 4)? 119 + (((unsigned long)(sz)) >> 15): \
((((unsigned long)(sz)) >> 18) <= 2)? 124 + (((unsigned long)(sz)) >> 18): \
126)
#define largebin_index(sz) \
(SIZE_SZ == 8 ? largebin_index_64 (sz) : largebin_index_32 (sz))
#define bin_index(sz) \
((in_smallbin_range(sz)) ? smallbin_index(sz) : largebin_index(sz))
宏
bin_index(sz)
根据所需内存大小计算出所需
bin
的
index
,如果所需内存大小属于
small bins
的大小范围,调用
smallbin_index(sz)
,否则调用
largebin_index(sz))
。
smallbin_index(sz)
的计算相当简单,如果
SIZE_SZ
为
4B
,则将
sz
除以
8
,如果
SIZE_SZ
为
8B
,则将
sz
除以
16
,也就是除以
small bins
中等差数列的公差。
largebin_index(sz)
的计算相对复杂一些,可以用如下的表格直观的显示
chunk
的大小范围与
bin index
的关系。以
SIZE_SZ
为
4B
的平台为例,
chunk
大小与
bin index
的对应关系如下表所示:(博客编辑器太弱,不能全部贴出来)
开始(
字节)
|
结束(字节)
|
Bin index
|
0
|
7
|
不存在
|
8
|
15
|
不存在
|
16
|
23
|
2
|
24
|
31
|
3
|
32
|
39
|
4
|
40
|
47
|
5
|
48
|
55
|
6
|
56
|
63
|
7
|
64
|
71
|
8
|
72
|
79
|
9
|
80
|
87
|
10
|
88
|
95
|
11
|
96
|
103
|
12
|
104
|
111
|
13
|
112
|
119
|
14
|
120
|
127
|
15
|
128
|
135
|
16
|
136
|
143
|
17
|
144
|
151
|
18
|
152
|
159
|
19
|
160
|
167
|
20
|
168
|
175
|
21
|
176
|
183
|
22
|
184
|
191
|
23
|
192
|
199
|
24
|
200
|
207
|
25
|
208
|
215
|
26
|
216
|
223
|
27
|
224
|
231
|
28
|
232
|
239
|
29
|
240
|
247
|
30
|
248
|
255
|
31
|
256
|
263
|
32
|
注意:上表是
chunk
大小与
bin index
的对应关系,如果对于用户要分配的内存大小
size
,必须先使用
checked_request2size(req, sz)
计算出
chunk
的大小,再使用
bin_index(sz)
计算出
chunk
所属的
bin index
。
对于
SIZE_SZ
为
4B
的平台,
bin[0]
和
bin[1]
是不存在的,因为最小的
chunk
为
16B
,
small bins
一共
62
个,
large bins
一共
63
个,加起来一共
125
个
bin
。而
NBINS
定义为
128
,其实
bin[0]
和
bin[127]
都不存在,
bin[1]
为
unsorted bin
的
chunk
链表头。
typedef struct malloc_chunk* mbinptr;
/* addressing -- note that bin_at(0) does not exist */
#define bin_at(m, i) \
(mbinptr) (((char *) &((m)->bins[((i) - 1) * 2])) \
- offsetof (struct malloc_chunk, fd))
/* analog of ++bin */
#define next_bin(b) ((mbinptr)((char*)(b) + (sizeof(mchunkptr)<<1)))
/* Reminders about list directionality within bins */
#define first(b) ((b)->fd)
#define last(b) ((b)->bk)
/* Take a chunk off a bin list */
#define unlink(P, BK, FD) { \
FD = P->fd; \
BK = P->bk; \
if (__builtin_expect (FD->bk != P || BK->fd != P, 0)) \
malloc_printerr (check_action, "corrupted double-linked list", P); \
else { \
FD->bk = BK; \
BK->fd = FD; \
if (!in_smallbin_range (P->size) \
&& __builtin_expect (P->fd_nextsize != NULL, 0)) { \
assert (P->fd_nextsize->bk_nextsize == P); \
assert (P->bk_nextsize->fd_nextsize == P); \
if (FD->fd_nextsize == NULL) { \
if (P->fd_nextsize == P) \
FD->fd_nextsize = FD->bk_nextsize = FD; \
else { \
FD->fd_nextsize = P->fd_nextsize; \
FD->bk_nextsize = P->bk_nextsize; \
P->fd_nextsize->bk_nextsize = FD; \
P->bk_nextsize->fd_nextsize = FD; \
} \
} else { \
P->fd_nextsize->bk_nextsize = P->bk_nextsize; \
P->bk_nextsize->fd_nextsize = P->fd_nextsize; \
} \
} \
} \
}
宏
bin_at(m, i)
通过
bin index
获得
bin
的链表头,
chunk
中的
fb
和
bk
用于将空闲
chunk
链入链表中,而对于每个
bin
的链表头,只需要这两个域就可以了,
prev_size
和
size
对链表都来说都没有意义,浪费空间,
ptmalloc
为了节约这点内存空间,增大
cpu
高速缓存的命中率,在
bins
数组中只为每个
bin
预留了两个指针的内存空间用于存放
bin
的链表头的
fb
和
bk
指针。
从
bin_at(m, i)
的定义可以看出,
bin[0]
不存在,以
SIZE_SZ
为
4B
的平台为例,
bin[1]
的前
4B
存储的是指针
fb
,后
4B
存储的是指针
bk
,而
bin_at
返回的是
malloc_chunk
的指针,由于
fb
在
malloc_chunk
的偏移地址为
offsetof
(struct malloc_chunk, fd))=8
,所以用
fb
的地址减去
8
就得到
malloc_chunk
的地址。但切记,对
bin
的链表头的
chunk
,一定不能修改
prev_size
和
size
域,这两个域是与其他
bin
的链表头的
fb
和
bk
内存复用的。
宏
next_bin(b)
用于获得下一个
bin
的地址,根据前面的分析,我们知道只需要将当前
bin
的地址向后移动两个指针的长度就得到下一个
bin
的链表头地址。
每个
bin
使用双向循环链表管理空闲
chunk
,
bin
的链表头的指针
fb
指向第一个可用的
chunk
,指针
bk
指向最后一个可用的
chunk
。宏
first(b)
用于获得
bin
的第一个可用
chunk
,宏
last(b)
用于获得
bin
的最后一个可用的
chunk
,这两个宏便于遍历
bin
,而跳过
bin
的链表头。
宏
unlink(P, BK, FD)
用于将
chunk
从所在的空闲链表中取出来,注意
large bins
中的空闲
chunk
可能处于两个双向循环链表中,
unlink
时需要从两个链表中都删除。
分享到:
相关推荐
NULL 博文链接:https://mqzhuang.iteye.com/blog/1064966
Glibc内存管理 Ptmalloc2 源代码分析
glibc内存管理ptmalloc源代码分析-电子资料-高清PDF版-pdf打印版
简介133.2.2内存管理的设计假设 143.2.3内存管理数据结构概述 143.2.4内存分配概述 193.2.5内存回收概述 213.2.6配置选项概述 2
淘宝网的研发人员写的文档,对了解GNU C的内存分配机制有很大的帮助!
该文档详细分析了c库中的内存管理细节,可广大程序员做参考。
简介133.2.2内存管理的设计假设 143.2.3内存管理数据结构概述 143.2.4内存分配概述 193.2.5内存回收概述 213.2.6配置选项概述 2
清晰版,对内存分析,程序设计非常有帮助。适合进阶的。
5. 源代码分析 5.1 边界标记法 5.2 分箱式内存管理 5.2.1 Small bins 5.2.2 Large bins 5.2.3 Unsorted bin 5.2.4 Fast bins 5.3 核心结构体分析 5.3.1 malloc_state 5.3.2 Malloc_par 5.3.3 分配区的初始...
glibc内存管理ptmalloc源代码分析.pdf
源代码分析 glibc的ptmalloc 分析
glibc内存管理ptmalloc源代码分析4.pdf
学习自《glibc内存管理ptmalloc源代码分析》庄明强 著 部分资料参考自互联网 chunk 描述: 当用户通过malloc等函数申请空间时,实际上是从堆中分配内存 目前 Linux 标准发行版中使用的是 glibc 中的堆分配器:...