本文只捡练了一些（以32位系统为例），高手绕过，参考：CTF-wiki堆，glibc内存管理ptmalloc2源码分析

同时感谢长歌短笛师傅的指导

0x01 malloc_chunk的基本结构

/*

 This struct declaration is misleading (but accurate and necessary).

 It declares a "view" into memory allowing access to necessary

 fields at known offsets from a given base. See explanation below.

*/

struct malloc_chunk {

 INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */

 INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */

  struct malloc_chunk* fd; /* double links -- used only if free. */

  struct malloc_chunk* bk;

  /* Only used for large blocks: pointer to next larger size. */

  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */

  struct malloc_chunk* bk_nextsize;

};

（free之后）

基本结构
mem指向用户得到的内存的起始位置。
1.size字段的低三个比特位对chunk的大小没有影响，他们从高到底分别表示：
-NON_MAIN_ARENA，记录当前 chunk 是否不属于主线程（main_arena），1 表示不属于，0 表示属于。
-ID_MAPPED，记录当前 chunk 是否是由 mmap 分配的。（chunk空闲时，M不存在）
-PREV_INUSE，记录前一个chunk是否被分配。1表示被分配，0表示没有。堆的第一个chunk所记录的prev_inuse位默认为1
2.fd_nextsize bk_nextsize在chunk空闲时才使用，（Large bin中特有）暂不讲解。
3.一般情况下，物理相邻的两个空闲chunk会被合并为一个chunk，堆管理器会通过prev_size字段及size字段合并两个物理相邻的空闲chunk。

0x02 chunk的复用

当一个chunk处于使用状态时，它的下一个chunk的prev_size无效，该prev_size域被当前chunk使用。可以理解为，当chunk在使用时，在二进制文件中执行，而不归共享库管理，下一个chunk的prev_size域直接分配给当前chunk，可以使内存空间高效利用，也省去重新分配空间的麻烦。

0x03 Bin

一．概述

·用户释放掉的 chunk 不会马上归还给系统，ptmalloc 会统一管理 heap 和 mmap 映射区域中的空闲的 chunk。
·free掉一个chunk时根据chunk大小加入到对应的bin中。
·将相似大小的chunk用链表链接，此链表称为bin。

当用户再一次请求分配内存时，ptmalloc 分配器会试图在空闲的 chunk 中挑选一块合适的给用户。这样可以避免频繁的系统调用，降低内存分配的开销。
在具体的实现中，ptmalloc 采用分箱式方法对空闲的 chunk 进行管理。
故而实际分配的空间=（用户申请的空间+8-4）align to 8b【+8==>用来存放prev_size和size，-4==>使用了下一个chunk的prev_size，再和8b对齐】

二．分类

1.第一类：fast bins

/*
   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.
 */
typedef struct malloc_chunk *mfastbinptr;

/*
    This is in malloc_state.
    /* Fastbins */
    mfastbinptr fastbinsY[ NFASTBINS ];
*/

fast bin为单链表。采用LIFO（Last In First Out）。fastbinsY[10]只使用前八个bin，所以大小范围为[0x10,0x80]。当用户需要的chunk大小<MAX（fastbin）时，ptmalloc会首先判断fastbin中相应的bin中是否有对应大小的空闲块（这里比较的是无符号整数），如果有，直接从fastbin头结点开始取chunk。free之后如果再次malloc相同size，会申请到同一块内存。不取消prev_inuse位，所以不会相互合并。

2.第二类：

• small bins
• unsort bins
• large bins

#define NBINS 128</pre>

/* Normal bins packed as described above */</pre>

mchunkptr bins[ NBINS * 2 - 2 ];</pre>

bin[128]中0和127不使用

unsort bin为bin[1]，其中的chunk没有排序，大小不限制，双链表，成环。采用FIFO。
当small chunk和large chunk被free的时候，先放到unsorted bin中作为缓冲。
如果unsorted bin中没有合适的chunk，就将unsorted bin中的chunk放到所属的bin中再分配。

small bin为索引2到63，大小为（2 * SIZE_SZ * ndx）（即size < 512），双链表，成环。采用FIFO。同一个small bin 链表中的 chunk 的大小相同。两个相邻索引的 small bin 链表中的 chunk 大小相差的字节数为2个机器字长，即 32 位相差 8 字节，64 位相差 16 字节。

large bin为索引64到126，大小为[512,512+64)。每个 bin 中的 chunk 的大小不一致，而是处于一定区间范围内。此外，这 63 个 bin 被分成了 6 组，每组 bin 中的 chunk 大小之间的公差一致。large bins 中的每一个 bin 都包含一定范围内的 chunk，其中的 chunk 按 fd 指针的顺序从大到小排列。相同大小的 chunk 同样按照最近使用顺序排列。

——上述这些 bin 的排布都会遵循一个原则：任意两个物理相邻的空闲 chunk 不能在一起。

需要注意的是，并不是所有的 chunk 被释放后就立即被放到 bin 中。ptmalloc 为了提高分配的速度，会把一些小的 chunk先放到 fast bins 的容器内。而且，fastbin 容器中的 chunk 的使用标记总是被置位的，所以不满足上面的原则。

0x04 Top Chunk

程序第一次进行 malloc 的时候，heap 会被分为两块，一块给用户，剩下的那块就是 top chunk。其实，所谓的 top chunk 就是处于当前堆的物理地址最高的 chunk。这个 chunk 不属于任何一个 bin，它的作用在于当所有的 bin 都无法满足用户请求的大小时，如果其大小不小于指定的大小，就进行分配，并将剩下的部分作为新的 top chunk。否则，就对 heap 进行扩展后再进行分配。在 main arena 中通过 sbrk 扩展 heap，而在 thread arena 中通过 mmap 分配新的 heap。

0x05 last remainder（略）

在用户使用 malloc 请求分配内存时，ptmalloc2 找到的 chunk 可能并不和申请的内存大小一致，这时候就将分割之后的剩余部分称之为 last remainder chunk ，unsort bin 也会存这一块。top chunk 分割剩下的部分不会作为 last remainer.

0x06 arena（分配区）

arena的个数是跟系统中处理器核心个数相关

For 32 bit systems:
     Number of arena = 2 * number of cores.
For 64 bit systems:
     Number of arena = 8 * number of cores.

包含：main arena（一个）
thread arena（多个）

0x07 malloc_state

该结构用于管理堆，记录每个 arena 当前申请的内存的具体状态，比如说是否有空闲 chunk，有什么大小的空闲 chunk 等等。无论是 thread arena 还是 main arena，它们都只有一个 malloc state 结构。由于 thread 的 arena 可能有多个，malloc state 结构会在最新申请的 arena 中。
注意，main arena 的 malloc_state 并不是 heap segment 的一部分，而是一个全局变量，存储在 libc.so 的数据段。

struct malloc_state {
    /* Serialize access.  */
    __libc_lock_define(, mutex);

    /* Flags (formerly in max_fast).  */
    int flags;

    /* Fastbins */
    mfastbinptr fastbinsY[ NFASTBINS ];

    /* Base of the topmost chunk -- not otherwise kept in a bin */
    mchunkptr top;

    /* The remainder from the most recent split of a small request */
    mchunkptr last_remainder;

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

    /* Bitmap of bins, help to speed up the process of determinating if a given bin is definitely empty.*/
    unsigned int binmap[ BINMAPSIZE ];

    /* Linked list, points to the next arena */
    struct malloc_state *next;

    /* Linked list for free arenas.  Access to this field is serialized
       by free_list_lock in arena.c.  */
    struct malloc_state *next_free;

    /* Number of threads attached to this arena.  0 if the arena is on
       the free list.  Access to this field is serialized by
       free_list_lock in arena.c.  */
    INTERNAL_SIZE_T attached_threads;

    /* Memory allocated from the system in this arena.  */
    INTERNAL_SIZE_T system_mem;
    INTERNAL_SIZE_T max_system_mem;
};