《ptmalloc——fastbins》中讲到了ptmalloc用链表的方式将相似大小的chunk链接起来，这些链表称为bin。除了fastbin，ptmalloc还包括unsorted bin，small bins，large bins。
small bins中存放固定大小的chunk，两个相邻的small bin中的chunk大小相差16字节（对于64位系统而言），同一链表中的chunk按照最近使用顺序进行排序，最后释放的chunk被链接到链表的头部，而申请chunk时从链表的尾部开始，small bin中的chunk在内存中大概如下图所示：
相对于small bin中的chunk都是固定大小，large bin链表中的chunk的大小都是在一定范围内的。因此这些chunk按照大小进行排序，相对较大的chunk在链表的头部，相对较小的chunk则在链表的尾部。除了正常的双向链表指针外，还有额外的两个指针，用于双向链接不同长度的chunk。large bin中的chunk在内存中大概如下图所示：
注：A，B，C三个chunk的长度具有相同的大小；同样D，E，F具有相同的大小；G，H，I具有相同的大小，A/B/C chunk的长度最大，其次是D/E/F chunk的长度，最小的是G/H/I。
unsorted bin顾名思义，即大小未排序的链表，不在fastbin范围内的chunk，被释放后，ptmalloc首先将其放到unsorted bin中；而申请chunk时，首先从unsorted bin中查找相同长度的chunk，同时将unsorted bin中的chunk按照其大小分别放到不同的small bin和large bin中。
下面程序验证small bin的链表结构，以及分配的顺序：
void test_smallbin()
{
char * p1[6];
char * p2[6];
int i = 0;
for( i = 0; i < 6; i++ ) {
p1[i] = (char*)malloc(200);
char * pChunkAddr = p1[i] - 16;
printf("[%d] mem: %p chunk: %p\n", i, p1[i], pChunkAddr);
}
for( i = 0; i < 6; i++ ) {
p2[i] = (char*)malloc(400);
char * pChunkAddr = p2[i] - 16;
printf("[%d] mem: %p chunk: %p\n", i, p2[i], pChunkAddr);
}
for( i = 0; i < 6; i += 2 ) {
if( NULL != p1[i] ) {
free( p1[i] );
}
if( NULL != p2[i] ) {
free( p2[i] );
}
}
printf("\nin unsorted bin:\n");
for( i = 0; i < 6; i+= 2 ) {
if( NULL != p1[i] ) {
size_t next = *((size_t*)p1[i]);
size_t forward = *((size_t*)(p1[i]+8));
printf("chunk: %p next chunk-> %p forward chunk-> %p\n", (p1[i]-16), next, forward);
}
if( NULL != p2[i] ) {
size_t next = *((size_t*)p2[i]);
size_t forward = *((size_t*)(p2[i]+8));
printf("chunk: %p next chunk-> %p forward chunk-> %p\n", (p2[i]-16), next, forward);
}
}
char * tmp1 = (char*)malloc(512);
printf("\nin small bins:\n");
for( i = 0; i < 6; i+= 2 ) {
if( NULL != p1[i] ) {
size_t next = *((size_t*)p1[i]);
size_t forward = *((size_t*)(p1[i]+8));
printf("chunk: %p next chunk-> %p forward chunk-> %p\n", (p1[i]-16), next, forward);
}
}
for( i = 0; i < 6; i+= 2 ) {
if( NULL != p2[i] ) {
size_t next = *((size_t*)p2[i]);
size_t forward = *((size_t*)(p2[i]+8));
printf("chunk: %p next chunk-> %p forward chunk-> %p\n", (p2[i]-16), next, forward);
}
}
char * tmp = (char*)malloc(400);
printf("tmp mem: %p chunk: %p\n", tmp, (tmp-16));
// 后续资源清理
}程序运行结果为：
[0] mem: 0x188f010 chunk: 0x188f000
[1] mem: 0x188f0e0 chunk: 0x188f0d0
[2] mem: 0x188f1b0 chunk: 0x188f1a0
[3] mem: 0x188f280 chunk: 0x188f270
[4] mem: 0x188f350 chunk: 0x188f340
[5] mem: 0x188f420 chunk: 0x188f410
[0] mem: 0x188f4f0 chunk: 0x188f4e0
[1] mem: 0x188f690 chunk: 0x188f680
[2] mem: 0x188f830 chunk: 0x188f820
[3] mem: 0x188f9d0 chunk: 0x188f9c0
[4] mem: 0x188fb70 chunk: 0x188fb60
[5] mem: 0x188fd10 chunk: 0x188fd00
in unsort bin:
chunk: 0x188f000 next chunk-> 0x380678e178 forward chunk-> 0x188f4e0
chunk: 0x188f4e0 next chunk-> 0x188f000 forward chunk-> 0x188f1a0
chunk: 0x188f1a0 next chunk-> 0x188f4e0 forward chunk-> 0x188f820
chunk: 0x188f820 next chunk-> 0x188f1a0 forward chunk-> 0x188f340
chunk: 0x188f340 next chunk-> 0x188f820 forward chunk-> 0x188fb60
chunk: 0x188fb60 next chunk-> 0x188f340 forward chunk-> 0x380678e178
in small bins:
chunk: 0x188f000 next chunk-> 0x380678e238 forward chunk-> 0x188f1a0
chunk: 0x188f1a0 next chunk-> 0x188f000 forward chunk-> 0x188f340
chunk: 0x188f340 next chunk-> 0x188f1a0 forward chunk-> 0x380678e238
chunk: 0x188f4e0 next chunk-> 0x380678e308 forward chunk-> 0x188f820
chunk: 0x188f820 next chunk-> 0x188f4e0 forward chunk-> 0x188fb60
chunk: 0x188fb60 next chunk-> 0x188f820 forward chunk-> 0x380678e308
tmp mem: 0x188f4f0 chunk: 0x188f4e0下面程序验证large bin的链表结构
void test_largebin()
{
char * p1[6];
char * p2[6];
char * p3[6];
int i = 0;
for( i = 0; i < 6; i++ ) {
p1[i] = (char*)malloc(1025);
char * pChunkAddr = p1[i] - 16;
printf("[%d] mem: %p chunk: %p\n", i, p1[i], pChunkAddr);
}
for( i = 0; i < 6; i++ ) {
p2[i] = (char*)malloc(1058);
char * pChunkAddr = p2[i] - 16;
printf("[%d] mem: %p chunk: %p\n", i, p2[i], pChunkAddr);
}
for( i = 0; i < 6; i++ ) {
p3[i] = (char*)malloc(1041);
char * pChunkAddr = p3[i] - 16;
printf("[%d] mem: %p chunk: %p\n", i, p3[i], pChunkAddr);
}
for( i = 0; i < 6; i += 2 ) {
if( NULL != p1[i] ) {
free( p1[i] );
}
if( NULL != p2[i] ) {
free( p2[i] );
}
if( NULL != p3[i] ) {
free( p3[i] );
}
}
printf("\nin unsort bins:\n");
for( i = 0; i < 6; i += 2 ) {
if( NULL != p1[i] ) {
size_t next = *((size_t*)p1[i]);
size_t forward = *((size_t*)(p1[i]+8));
printf("chunk: %p next chunk-> %p forward chunk-> %p\n", (p1[i]-16), next, forward);
}
if( NULL != p2[i] ) {
size_t next = *((size_t*)p2[i]);
size_t forward = *((size_t*)(p2[i]+8));
printf("chunk: %p next chunk-> %p forward chunk-> %p\n", (p2[i]-16), next, forward);
}
if( NULL != p3[i] ) {
size_t next = *((size_t*)p3[i]);
size_t forward = *((size_t*)(p3[i]+8));
printf("chunk: %p next chunk-> %p forward chunk-> %p\n", (p3[i]-16), next, forward);
}
}
char * tmp1 = (char*)malloc(1800);
printf("\nin large bins:\n");
for( i = 0; i < 6; i += 2 ) {
if( NULL != p2[i] ) {
size_t nChunkSize = *((size_t*)(p2[i]-8)) & (~(0x7));
size_t next = *((size_t*)p2[i]);
size_t forward = *((size_t*)(p2[i]+8));
size_t nextSizeChunk = *((size_t*)(p2[i]+16));
size_t forwardSizeChunk = *((size_t*)(p2[i]+24));
printf("chunk: %p chunk size: %d\n", (p2[i]-16), nChunkSize);
printf("next chunk-> %p forward chunk-> %p\n", next, forward);
printf("next size chunk-> %p forward size chunk-> %p", nextSizeChunk, forwardSizeChunk);
}
}
for( i = 0; i < 6; i += 2 ) {
if( NULL != p3[i] ) {
size_t nChunkSize = *((size_t*)(p3[i]-8)) & (~(0x7));
size_t next = *((size_t*)p3[i]);
size_t forward = *((size_t*)(p3[i]+8));
size_t nextSizeChunk = *((size_t*)(p3[i]+16));
size_t forwardSizeChunk = *((size_t*)(p3[i]+24));
printf("chunk: %p chunk size: %d\n", (p3[i]-16), nChunkSize);
printf("next chunk-> %p forward chunk-> %p\n", next, forward);
printf("next size chunk-> %p forward size chunk-> %p", nextSizeChunk, forwardSizeChunk);
}
}
for( i = 0; i < 6; i += 2 ) {
if( NULL != p1[i] ) {
size_t nChunkSize = *((size_t*)(p1[i]-8)) & (~(0x7));
size_t next = *((size_t*)p1[i]);
size_t forward = *((size_t*)(p1[i]+8));
size_t nextSizeChunk = *((size_t*)(p1[i]+16));
size_t forwardSizeChunk = *((size_t*)(p1[i]+24));
printf("chunk: %p chunk size: %d\n", (p1[i]-16), nChunkSize);
printf("next chunk-> %p forward chunk-> %p\n", next, forward);
printf("next size chunk-> %p forward size chunk-> %p", nextSizeChunk, forwardSizeChunk);
}
}
}程序运行结果为：
[0] mem: 0x22dc010 chunk: 0x22dc000
[1] mem: 0x22dc420 chunk: 0x22dc410
[2] mem: 0x22dc830 chunk: 0x22dc820
[3] mem: 0x22dcc40 chunk: 0x22dcc30
[4] mem: 0x22dd050 chunk: 0x22dd040
[5] mem: 0x22dd460 chunk: 0x22dd450
[0] mem: 0x22dd870 chunk: 0x22dd860
[1] mem: 0x22ddca0 chunk: 0x22ddc90
[2] mem: 0x22de0d0 chunk: 0x22de0c0
[3] mem: 0x22de500 chunk: 0x22de4f0
[4] mem: 0x22de930 chunk: 0x22de920
[5] mem: 0x22ded60 chunk: 0x22ded50
[0] mem: 0x22df190 chunk: 0x22df180
[1] mem: 0x22df5b0 chunk: 0x22df5a0
[2] mem: 0x22df9d0 chunk: 0x22df9c0
[3] mem: 0x22dfdf0 chunk: 0x22dfde0
[4] mem: 0x22e0210 chunk: 0x22e0200
[5] mem: 0x22e0630 chunk: 0x22e0620
in unsort bins:
chunk: 0x22dc000 next chunk-> 0x380678e178 forward chunk-> 0x22dd860
chunk: 0x22dd860 next chunk-> 0x22dc000 forward chunk-> 0x22df180
chunk: 0x22df180 next chunk-> 0x22dd860 forward chunk-> 0x22dc820
chunk: 0x22dc820 next chunk-> 0x22df180 forward chunk-> 0x22de0c0
chunk: 0x22de0c0 next chunk-> 0x22dc820 forward chunk-> 0x22df9c0
chunk: 0x22df9c0 next chunk-> 0x22de0c0 forward chunk-> 0x22dd040
chunk: 0x22dd040 next chunk-> 0x22df9c0 forward chunk-> 0x22de920
chunk: 0x22de920 next chunk-> 0x22dd040 forward chunk-> 0x22e0200
chunk: 0x22e0200 next chunk-> 0x22de920 forward chunk-> 0x380678e178
in large bins:
chunk: 0x22dc000 chunk size:1040
next chunk-> 0x22dd040 forward chunk-> 0x22df9c0
next large chunk-> 0x22dd860 next small chunk-> 0x22df180
chunk: 0x22dc820 chunk size:1040
next chunk-> 0x380678e568 forward chunk-> 0x22dd040
next large chunk-> (nil) next small chunk-> (nil)
chunk: 0x22dd040 chunk size:1040
next chunk-> 0x22dc820 forward chunk-> 0x22dc000
next large chunk-> (nil) next small chunk-> (nil)
chunk: 0x22dd860 chunk size:1072
next chunk-> 0x22de920 forward chunk-> 0x380678e568
next large chunk-> 0x22df180 next small chunk-> 0x22dc000
chunk: 0x22de0c0 chunk size:1072
next chunk-> 0x22df180 forward chunk-> 0x22de920
next large chunk-> (nil) next small chunk-> (nil)
chunk: 0x22de920 chunk size:1072
next chunk-> 0x22de0c0 forward chunk-> 0x22dd860
next large chunk-> (nil) next small chunk-> (nil)
chunk: 0x22df180 chunk size:1056
next chunk-> 0x22e0200 forward chunk-> 0x22de0c0
next large chunk-> 0x22dc000 next small chunk-> 0x22dd860
chunk: 0x22df9c0 chunk size:1056
next chunk-> 0x22dc000 forward chunk-> 0x22e0200
next large chunk-> (nil) next small chunk-> (nil)
chunk: 0x22e0200 chunk size:1056
next chunk-> 0x22df9c0 forward chunk-> 0x22df180
next large chunk-> (nil) next small chunk-> (nil)
