CTF pwn heap-分箱式内存管理结构体bins

发布于 2023-04-25  515 次阅读


什么是bins

/*
   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*.
 */

以上是glibc对bins的解释(大多是对用bins来管理的好处),根据这个和CTF wiki上的解释总结为以下重要的几点:

  • 对于释放的堆块(chunk),它们并不会立刻返还给系统,而是保存在bins中
  • 总共有128个bins,每个bins都是一个双向链表,相似大小的chunk存放在同一个bin里面(实际上会先根据大小区间分为好几类bin),用双向链表进行连接(fd,bk指针)
  • 当申请新的chunk时候,会优先匹配最先释放的跟申请大小相同的chunk,满足先进先出(FIFO)

bins的分类

对应源码注释:

/*
   Indexing

    Bins for sizes < 512 bytes contain chunks of all the same size, spaced
    8 bytes apart. Larger bins are approximately logarithmically spaced:

    64 bins of size       8
    32 bins of size      64
    16 bins of size     512
     8 bins of size    4096
     4 bins of size   32768
     2 bins of size  262144
     1 bin  of size what's left

    There is actually a little bit of slop in the numbers in bin_index
    for the sake of speed. This makes no difference elsewhere.

    The bins top out around 1MB because we expect to service large
    requests via mmap.

    Bin 0 does not exist.  Bin 1 is the unordered list; if that would be
    a valid chunk size the small bins are bumped up one.
 */

small bin

申请的内存大小小于1024字节(0x400)的chunk释放后会进入smallbin中,smallbin的下标从2开始到63,每个下标之间差了一个size_SZ的大小,相同小标中所存放的chunk大小一致,每个 chunk 的大小与其所在的 bin 的 index 的关系为:chunk_size = 2 SIZE_SZ index,如下面的表格所示

下标 SIZE_SZ=4(32 位) SIZE_SZ=8(64 位)
2 16 32
3 24 48
4 32 64
5 40 80
x 8x 16x
63 504 1008

Large bin

申请内存大小大于1024字节(0x400)的chunk释放后会进入Largebin,large bins 中一共包括 63 个 bin,每个 bin 中的 chunk 的大小不一致,而是处于一定区间范围内。此外,这 63 个 bin 被分成了 6 组,每组 bin 中的 chunk 大小之间的公差一致,具体如下:

数量 公差
1 32 64B
2 16 512B
3 8 4096B
4 4 32768B
5 2 262144B
6 1 what's left

Fastbin

源码注释如下:

/*
   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.
 */
  • fastbin采用单链表和LIFO的方式进行管理
  • fastbin 范围的 chunk 的 inuse 始终被置为 1。因此它们不会和其它被释放的 chunk 合并,但是malloc_consolidate函数会将fastbin中的所有chunk都释放并且与其他释放的chunk合并
    /*
    FASTBIN_CONSOLIDATION_THRESHOLD is the size of a chunk in free()
    that triggers automatic consolidation of possibly-surrounding
    fastbin chunks. This is a heuristic, so the exact value should not
    matter too much. It is defined at half the default trim threshold as a
    compromise heuristic to only attempt consolidation if it is likely
    to lead to trimming. However, it is not dynamically tunable, since
    consolidation reduces fragmentation surrounding large chunks even
    if trimming is not used.
    */
  • 但是当释放的 chunk 与该 chunk 相邻的空闲 chunk 合并后的大小大于 FASTBIN_CONSOLIDATION_THRESHOLD 时,内存碎片可能比较多了,我们就需要把 fast bins 中的 chunk 都进行合并,以减少内存碎片对系统的影响
    #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
  • fastbin的大小由global_max_fast决定
    32位:0x10-0x40
    64位:0x20-0x80
    chunk 的大小而不是申请的内存的大小(申请的内存加上 chunk 头)

Top chunk

源码注释如下:

/*
   Top

    The top-most available chunk (i.e., the one bordering the end of
    available memory) is treated specially. It is never included in
    any bin, is used only if no other chunk is available, and is
    released back to the system if it is very large (see
    M_TRIM_THRESHOLD).  Because top initially
    points to its own bin with initial zero size, thus forcing
    extension on the first malloc request, we avoid having any special
    code in malloc to check whether it even exists yet. But we still
    need to do so when getting memory from system, so we make
    initial_top treat the bin as a legal but unusable chunk during the
    interval between initialization and the first call to
    sysmalloc. (This is somewhat delicate, since it relies on
    the 2 preceding words to be zero during this interval as well.)
 */

/* Conveniently, the unsorted bin can be used as dummy top on first call */
#define initial_top(M) (unsorted_chunks(M))
  • Top chunk不属于任何bin
  • 当所有的 bin 都无法满足用户请求的大小时,如果其大小不小于指定的大小,就进行分配,并将剩下的部分作为新的 top chunk。否则,就对 heap 进行扩展后再进行分配
  • 第一次执行malloc函数时可以认为unsorted bin是一个假的top chunk

    unsorted bin(chunk)

    源码注释如下:

    /*
    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.
    */
  • 当一个较大的 chunk 被分割成两半后,如果剩下的部分大于 MINSIZE,就会被放到 unsorted bin 中。
  • 释放一个不属于 fast bin 的 chunk,并且该 chunk 不和 top chunk 紧邻时,该 chunk 会被首先放到 unsorted bin 中
    /* The otherwise unindexable 1-bin is used to hold unsorted chunks. */
  • unsorted bin位于bin 数组下标 1 处
届ける言葉を今は育ててる
最后更新于 2023-04-25