目录
  1. 1. struct chunk结构
    1. 1.1. fastbinY
    2. 1.2. bins
    3. 1.3. FIFO
bins

bin是一个由struct chunk结构体组成的链表

bin 用来管理被释放的free chunk,方便下次申请内存使用

ptmalloc 一共维护了 128 个这样的 bin

malloc chunk

struct chunk结构

struct chunk结构体如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef struct malloc_chunk* mchunkptr;
typedef struct malloc_chunk *mfastbinptr;


struct malloc_state
{
...
/*other member*/
...

/* Fastbins */
mfastbinptr fastbinsY[NFASTBINS];
//存放每个 fast chunk 链表头部的指针

/* Normal bins packed as described above */
mchunkptr bins[NBINS * 2 - 2];
//用于存储 unstored bin,small bins 和 large bins 的 chunk 链表。
...
/*other member*/
...
};

可以看到有fastbinsYbins两种bin数组

fastbinY

  • fastbinsY数组的bin主要回收32字节~128字节(0x20~0x80)的chunk,fastbin 最多可以支持的 bin 的个数为 10 个,

  • fastbin是单链表,只用到fd指针,遍历顺序是LIFO(后进先出)

  • prev_inuse位不置0,防止合并

    32位系统下

    第一个fast bin(index 0)包含16字节chunk的binlist,第二个fast bin(index 1)包含24字节chunk的binlist …

    chunk大小对应下标

    0 1 2 3 4 5 6 7 8 9

    0x10 0x18 0x20 0x28 0x30 0x38 0x40 0x48 0x50 0x58 32位

    0x20 0x30 0x40 0x50 0x60 0x70 0x80 64位

    但是不知道为什么fastbin有十个却好像只用了前七个(貌似与malloc初始化有关)

    在32位系统中,fastbin里chunk的大小范围从16到64; –>0x10到0x40

    在64位系统中,fastbin里chunk的大小范围从32到128; –>0x20到0x80

    fastbinY.png

    求fastbin的索引

    1
    2
    3
    4
    5
    6
    7
    8
    #define fastbin(ar_ptr, idx) ((ar_ptr)->fastbinsY[ idx ])

    /* offset 2 to use otherwise unindexable first 2 bins */
    // chunk size=2*size_sz*(2+idx)
    // 这里要减2,否则的话,前两个bin没有办法索引到。
    #define fastbin_index(sz) \
    ((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)
    //64位除16减去2,32位除8减去2

bins

  • bins数组中的第一个 bin 是 unsorted bin(1个),数组中从第 2 个到第 63 个 bin 是 small bin(62个),64到126为large bin(63个)

  • 三种bin都是由free chunks组成的循环双链表

  • unsortedbinsmall bin采用FIFO(先入先出)算法,

  • unsorted bin中,对chunk的大小并没有限制,任何大小的chunk都可以归属到unsorted bin中。当释放较小或较大的chunk的时候,如果系统没有将它们添加到对应的bins中,系统就将这些chunk添加到unsorted bin中

  • small bin中chunk的大小依次增加两个机器字长,与fastbin一样.不过bin有62个,chunk大小从0x100x1f8(32位)0x200x3f0(64位)

  • largin bin 中 chunk 的大小不是固定的,而是有一个范围。其中的顺序是按从大到小排序的,大的chunk放在一个链表的头部,最小的chunk放在尾部;相同大小的chunk按照最近使用顺序排序

  • 在这63个large bin中,

    • 前32个大bin按以64字节步长为间隔,即第一个大bin中chunk大小为512〜575字节,第二个大bin中chunk大小为576〜 639字节。紧随其后的16个大bin先以512字节步长为间隔;

    • 之后的8个bin以步长4096为间隔;

    • 再之后的4个bin以32768字节为间隔;

    • 之后的2个bin以262144字节为间隔;

    • 剩下的chunk就放在最后一个大bin中。

QQ截图20200408174926.png

FIFO

内存释放操作就将新释放的chunk添加到链表的front end(前端),分配操作就从链表的rear end(尾端)中获取chunk

文章作者: zzl
文章链接: https://www.zzl14.xyz/2020/04/07/bins/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 try
打赏
  • 微信
  • 支付宝

评论