heap - 3 - bins分类

字数统计: 1.9k   |   阅读时长≈ 9 分钟

存放free chunks的链表 ——— bins !

1. bin链的介绍

  • bin链是由struct chunk组成的链表
  • 不同的chunk根据不同的特点将它们区分开，为了便于分开管理，glibc引入了bin链这个概念
  • bin链上的chunk都是free chunk
  • bin链都是由当前线程的arena管理的

2. bin链的分类

  1. Fast bin
  2. Small bin
  3. Unsorted bin
  4. Large bin

  • 关系如下

      graph TB
total[Total Bins] --> fast[Fast bins]
total --> bins[Bins]
bins --> small[Small bins]
bins --> unsorted[Unsorted bins]
bins --> large[Large bins]

3. bin链的存储

  • bin链存储在arena里，详细代码如下

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    struct malloc_state
    {
    /* Other members ... */

    /* Fastbins */
    mfastbinptr fastbinsY[NFASTBINS];

    /* Normal bins packed as described above */
    mchunkptr bins[NBINS * 2 - 2];

    /* Other members ... */
    };

  • fast bin存储于arena.fastbinY数组中

  • small bin、 unsorted bin以及large bin都存储于arena的bins数组中

4. Fast bin

介绍

  • glibc的介绍

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    Fastbins

    An array of lists holding recently freed small chunks.  Fastbins
    are not doubly linked.  It is faster to single-link them, and
    since chunks are never removed from the middles of these lists,
    double linking is not necessary. Also, unlike regular bins, they
    are not even processed in FIFO order (they use faster LIFO) since
    ordering doesn't much matter in the transient contexts in which
    fastbins are normally used.

    Chunks in fastbins keep their inuse bit set, so they cannot
    be consolidated with other free chunks. malloc_consolidate
    releases all chunks in fastbins and consolidates them with
    other free chunks.

  • 设计fast bin的初衷就是进行快速的小内存分配和释放

  • chunk大小 小于64(0x40)（32位）/ 128(0x80)（64位）字节的free chunk为fast chunk，其由fast bin管理
    该大小是在malloc_init_state函数中设置的
    其默认值为(DEFAULT_MXFAST + SIZE_SZ) & ~MALLOC_ALIGN_MASK
    相关代码如下：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    #define DEFAULT_MXFAST     (64 * SIZE_SZ / 4)

    #define set_max_fast(s) \
      global_max_fast = (((s) == 0)      \
                        ? SMALLBIN_WIDTH : ((s + SIZE_SZ) & ~MALLOC_ALIGN_MASK))
    #define get_max_fast() global_max_fast

    #define MALLOC_ALIGNMENT       (2 *SIZE_SZ)
    /* The corresponding bit mask value */
    #define MALLOC_ALIGN_MASK      (MALLOC_ALIGNMENT - 1)

  • fast bin链共有10条

    1
    2
    3
    /* The maximum fastbin request size we support */
    #define MAX_FAST_SIZE     (80 * SIZE_SZ / 4)
    #define NFASTBINS  (fastbin_index (request2size (MAX_FAST_SIZE)) + 1)

  • fast bin的分组依据fast chunk的大小
    两个相邻bin链里的chunk最大值相差8字节（32位）或16字节（64位）

    • 以64字节为例
      fastbinY[0]指向的chunk大小为0x20 - 0x30
      fastbinY[1]指向的chunk大小为0x30 - 0x40
      ......
      fastbinY[5]指向的chunk大小为0x70 - 0x80

    • 相关代码如下

      1
      2
      3
      /* offset 2 to use otherwise unindexable first 2 bins */
      #define fastbin_index(sz) \
          ((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)

特点

  • LIFO（后进先出, 从链头取出 / 插入chunk），更快速的分配chunk
  • 单向 链表，fast chunk只使用fd指针指向下一个fast chunk，其bk指针置空
  • 属于fast bin的chunk的PREV_INUSE位 总是设置为1 ，以保证当前fast chunk不会被其他free chunks合并

5. Bins

  • glibc的介绍

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    Bins

    An array of bin headers for free chunks. Each bin is doubly
    linked.  The bins are approximately proportionally (log) spaced.
    There are a lot of these bins (128). This may look excessive, but
    works very well in practice.  Most bins hold sizes that are
    unusual as malloc request sizes, but are more usual for fragments
    and consolidated sets of chunks, which is what these bins hold, so
    they can be found quickly.  All procedures maintain the invariant
    that no consolidated chunk physically borders another one, so each
    chunk in a list is known to be preceeded and followed by either
    inuse chunks or the ends of memory.

    Chunks in bins are kept in size order, with ties going to the
    approximately least recently used chunk. Ordering isn't needed
    for the small bins, which all contain the same-sized chunks, but
    facilitates best-fit allocation for larger chunks. These lists
    are just sequential. Keeping them in order almost never requires
    enough traversal to warrant using fancier ordered data
    structures.

    Chunks of the same size are linked with the most
    recently freed at the front, and allocations are taken from the
    back.  This results in LRU (FIFO) allocation order, which tends
    to give each chunk an equal opportunity to be consolidated with
    adjacent freed chunks, resulting in larger free chunks and less
    fragmentation.

    To simplify use in double-linked lists, each bin header acts
    as a malloc_chunk. This avoids special-casing for headers.
    But to conserve space and improve locality, we allocate
    only the fd/bk pointers of bins, and then use repositioning tricks
    to treat these as the fields of a malloc_chunk*.

  • bin链共有128条

    • 相关代码如下

      1
      2
      3
      4
      5
      #define NBINS             128

      // in struct malloc_state
      /* Normal bins packed as described above */
      mchunkptr bins[NBINS * 2 - 2];

    为什么arena中，bins数组的大小为 NBINS * 2 - 2 呢？
    因为每个bin链在bins数组中存储的是一个指针fd指针和一个bk指针，即两个malloc chunk指针，所以要NBINS * 2
    又因为数组bins中索引为0、1的指针是不使用的，所以要减去2

    例： bins[2]为unsorted bin链的fd成员，bin[3]为其bk成员

1. Unsorted bin

介绍

  • glibc的介绍

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    Unsorted chunks

    All remainders from chunk splits, as well as all returned chunks,
    are first placed in the "unsorted" bin. They are then placed
    in regular bins after malloc gives them ONE chance to be used before
    binning. So, basically, the unsorted_chunks list acts as a queue,
    with chunks being placed on it in free (and malloc_consolidate),
    and taken off (to be either used or placed in bins) in malloc.

    The NON_MAIN_ARENA flag is never set for unsorted chunks, so it
    does not have to be taken into account in size comparisons.

  • 被用户释放的allocated chunk，以及分割其他free chunk产生的剩余free chunk，都会被放置进unsorted bin里

  • 其主要目的是为了让 glibc malloc机制 能够有第二次机会重新利用最近释放的chunk

  • unsorted bin只有 一个，位于arena中的 bin[1] 。 任何大小 的chunk都可加入unsorted bin中

特点

  • 无序双向 链表
  • FIFO（从链尾取出chunk，从链头插入chunk）

2. Small bin

介绍

  • chunk大小 小于512(0x200)（32位）/ 1024(0x400)（64位）字节的free chunk为small chunk，其由small bin管理

    • 相关代码如下

      1
      2
      3
      4
      5
      6
      7
      #define NSMALLBINS         64
      #define SMALLBIN_WIDTH    MALLOC_ALIGNMENT
      #define SMALLBIN_CORRECTION (MALLOC_ALIGNMENT > 2 * SIZE_SZ)
      #define MIN_LARGE_SIZE    ((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH)

      #define in_smallbin_range(sz)  \
        ((unsigned long) (sz) < (unsigned long) MIN_LARGE_SIZE)

  • small bin共有62个

  • small bin的分组依据small chunk的大小
    两个相邻bin链里的chunk最大值相差8字节（32位）或16字节（64位）,
    与fastbin的分组策略相同

    • 以64字节为例
      索引为2中chunk大小为0x20 - 0x30
      索引为3里的chunk大小为0x30 - 0x40
      ......
      索引为63里的chunk大小为0x3F0 - 0x400

    • 相关代码如下

      1
      2
      3
      #define smallbin_index(sz) \
        ((SMALLBIN_WIDTH == 16 ? (((unsigned) (sz)) >> 4) : (((unsigned) (sz)) >> 3))\
        + SMALLBIN_CORRECTION)

特点

  • 无序双向 链表
  • FIFO（从链尾取出chunk，从链头插入chunk）
  • 就内存的分配和释放速度而言，small bin比large bin快，但比fast bin慢

3. Large bin

介绍

  • chunk大小 小于512(0x200)（32位）/ 1024(0x400)（64位）字节的free chunk为small chunk，其由small bin管理

  • large bin共有64个

  • large bin的分组同样依据large chunk的大小，不过稍有不同

    • large bin 大体上分为6大组，其中每个大组里都有若干小组（此处不再展开，笔者想偷懒了QwQ）

    • 相关源代码如下：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      // 2^6 = 64 ; 2^9 = 512 ; 2^12 = 4096 ; 2^15 = 32768 ;
      #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)

      #define largebin_index_32_big(sz)                                            \
        (((((unsigned long) (sz)) >> 6) <= 45) ?  49 + (((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)                                     \
        : MALLOC_ALIGNMENT == 16 ? largebin_index_32_big (sz)                     \
        : largebin_index_32 (sz))

  • large bin相对于small bin和fast bin来讲，比较特殊
    在一条large bin链里，free chunks的大小并不相同，所以

    • large chunk中有两个特殊的指针
      • 指针fd_nextsize : 该指针指向下一个大小更小的chunk（注意可能不是相邻chunk）
      • 指针bk_nextsize : 该指针指向上一个大小更大的chunk（注意可能不是相邻chunk）
      • 一个例子
        img
    • large bin上chunks是按大小排列的
      • 从链头(bin处) 到 链尾，沿着各个chunk的fd指针，chunks大小从高到低，依次排序

特点

  • 有序双向 链表，有序插入和取出chunks
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2020-2024 Kiprey
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~