ptmalloc——smallbin/largebin/unsortedbin

原创
2017/06/21 16:53
阅读数 2K

《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)

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部