参考链接：https://ctf-wiki.github.io/ctf-wiki/pwn/linux/glibc-heap/heap_structure-zh/

引言：由malloc申请的内存称为chunk。这块内存在ptmalloc内部用malloc_chunk结构体表示。

当程序申请的chunk被free后，会被加入到相应的空闲管理列表中。

(1)无论一个chunk大小如何，分配还是空闲，都是用一个统一的结构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;

};

prev_size，如果该chunk物理相邻的前一个chunk是空闲的话，表示前一chunk的大小。

否则，用该字段用于存储前一chunk的数据。

size，该chunk的大小。必须是2*SIZE_SZ的整数倍。32位系统中，SIZE_SZ=4；64位系统中，SIZE_SZ=8。该字段的低3个比特对chunk的大小没有影响，它们分别为：

(1)NON_MAIN_ARENA，记录当前chunk是否不属于主线程，1表示不属于，0表示属于。

(2)IS_MAPPED，记录当前chunk是否是由mmap分配的。

(3)PREV_INUSE，记录前一个chunk是否被分配。1表示分配，0表示空闲。一般来说，堆中第一个被分配的内存块的size字段的P位设置为1，防止访问签名的非法内存。当一个chunk 的size的P位置0时，我们可以通过prev_size字段获取上一个 chunk的大小以及地址，方便合并。

fd bk，chunk处于分配状态时，从fd字段开始是用户数据；空闲时，会被添加到对应的空闲管理链表中，其字段的含义如下：

fd指向下一个空闲的chunk，bk指向上一个空闲的chunk

fd_nextsize, bk_nextsize，也是只有chunk空闲时才用，不过用于较大的chunk(large chunk)

fd_nextsize 指向前一个与当前chunk大小不同的第一个空闲块，不包含bin的头指针；

bk_nextsize 指向后一个与当前chunk大小不同的第一个空闲块，不包含bin的头指针。

一般空闲的 large chunk 在fd的遍历顺序中，按照从大到小的顺序排列。这样可以避免寻找合适chunk时挨个遍历。

注：我们称前2个字段为 chunk header，后面的部分为 user data。每次malloc申请得到的内存总是指向user data

可以发现，如果一个 chunk 处于 free 状态，那么会有2个位置记录器相应的大小：本身的size和后一块的prev_size；一般情况下，物理相邻的2个空闲chunk会被合并为一个chunk。堆管理器会通过prev_size字段和size字段进行合并。

(2)chunk 相关宏(主要是chunk大小、对其检查和一些转换的宏)

chunk 与 mem 指针头部的转换

mem 指向用户得到的内存的起始位置

#define chunk2mem(p) ((void *)((char *)(p) + 2*SIZE_SZ))

#define mem2chunk(mem) ((mchunkptr)((char *)(mem)-2*SIZE_SZ))

最小的 chunk 大小

#define MIN_CHUNK_SIZE (offsetof (struct malloc_chunk, fd_nextsize))

这里，offsetof 函数计算出fd_nextsize 在 malloc_chunk中的偏移，说明最小的 chunk 至少要包含bk指针

最小申请的堆内存大小

必须是 2*SIZE_SZ的最小整数倍

检查分配给用户的内存是否对齐

2*SIZE_SZ 大小对齐

#define aligned_OK(m) (((unsigned long) (m) & MALLOC_ALIGN_MASK)==0)

#define misaligned_chunk(p) ((uintptr_t)(MALLOC_ALIGNMENT == 2 *SIZE_SZ ? (p) : chunk2mem(p)) & MALLOC_ALIGN_MASK)

省略各种宏定义……

bin

用户释放掉的chunk不会马上归还给系统，ptmalloc 会统一管理 heap 和 mmap映射区域中的空闲 chunk。当用户再一次请求分配内存时，ptmalloc 分配器会试图在空闲的 chunk中挑选合适的给用户。避免频繁的系统调用，降低内存分配的开销。

根据 chunk 的大小和使用状态，分为 fast bins , small bins, large bins, unsorted bin。ptmalloc将后三个维护在同一个数组中。这些bin对应的数据结构在 malloc_state 中，如下

#define NBINS 128

/* Normal bins packed as described above */

mchunkptr bins[ NBINS * 2 - 2 ];

每个bin的表头使用 mchunkptr 这个数据结构；使用时会将这个指针当做chunk 的fd或bk指针来操作，以便将处于空闲的堆块链接在一起。

数组中的bin依次介绍如下：

第一个为 unsorted bin，这里的chunk没有进行排序，存储的chunk比较杂。

索引从2 到63 的bin 称为 small bin， 同一个 small bin 链表中的chunk 大小相同。两个相邻索引的 small bin 链表中的 chunk 大小相差2个机器字节长，即32位相差8字节，64位相差16字节。

small bins 后面的bin称为 large bins。 large bins 中的每一个bin都包含一定范围内的 chunk，其中chunk 按 fd指针的顺序从大到小排列。相同大小的 chunk 同样按照最近使用顺序排列。

需要注意的是，ptmalloc为了提高分配速度，会把小的 chunk 先放到 fast bins 的容器内。而且，fast bins 容器中的 chunk 的使用标记总是被置位，不满足上述规则。

bin 的通用宏如下：

typedef struct malloc_chunk *mbinptr;

/* addressing -- note that bin_at(0) does not exist */

#define bin_at(m, i) \

(mbinptr)(((char *) &((m)->bins[ ((i) -1) * 2 ])) - \

offsetof(struct malloc_chunk, fd))

/* analog of ++bin */

//获取下一个bin的地址

#define next_bin(b) ((mbinptr)((char *) (b) + (sizeof(mchunkptr) << 1)))

/* Reminders about list directionality within bins */

// 这两个宏可以用来遍历bin

// 获取 bin 的位于链表头的 chunk

#define first(b) ((b)->fd)

// 获取 bin 的位于链表尾的 chunk

#define last(b) ((b)->bk)

**Fast bin**

/*

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 bins，glibc 采用单向链表对其中的每个 bin 进行组织，并且每个 bin 采用LIFO策略。最近释放的 chunk 会更早地被分配。

32 位系统中，fastbin 中默认支持最大 chunk 的数据空间大小为64字节，但是其可疑支持的 chunk 的数据空间最大为80个字节。fastbin 最多可以支持的 bin 个数为10个。数据空间(第8到80个字节)定义如下：

#define NFASTBINS (fastbin_index(request2size(MAX_FAST_SIZE)) + 1)

#ifndef DEFAULT_MXFAST

#define DEFAULT_MXFAST (64 * SIZE_SZ / 4)

#endif

/* The maximum fastbin request size we support */

#define MAX_FAST_SIZE (80 * SIZE_SZ / 4)

/*

Since the lowest 2 bits in max_fast don't matter in size comparisons,

they are used as flags.

*/

/*

FASTCHUNKS_BIT held in max_fast indicates that there are probably

some fastbin chunks. It is set true on entering a chunk into any

fastbin, and cleared only in malloc_consolidate.

The truth value is inverted so that have_fastchunks will be true

upon startup (since statics are zero-filled), simplifying

initialization checks.

*/

//判断分配区是否有 fast bin chunk，1表示没有

#define FASTCHUNKS_BIT (1U)

#define have_fastchunks(M) (((M)->flags & FASTCHUNKS_BIT) == 0)

#define clear_fastchunks(M) catomic_or(&(M)->flags, FASTCHUNKS_BIT)

#define set_fastchunks(M) catomic_and(&(M)->flags, ~FASTCHUNKS_BIT)

/*

NONCONTIGUOUS_BIT indicates that MORECORE does not return contiguous

regions. Otherwise, contiguity is exploited in merging together,

when possible, results from consecutive MORECORE calls.

The initial value comes from MORECORE_CONTIGUOUS, but is

changed dynamically if mmap is ever used as an sbrk substitute.

*/

// MORECODE是否返回连续的内存区域。

// 主分配区中的MORECORE其实为sbr()，默认返回连续虚拟地址空间

// 非主分配区使用mmap()分配大块虚拟内存，然后进行切分来模拟主分配区的行为

// 而默认情况下mmap映射区域是不保证虚拟地址空间连续的，所以非主分配区默认分配非连续虚拟地址空间。

#define NONCONTIGUOUS_BIT (2U)

#define contiguous(M) (((M)->flags & NONCONTIGUOUS_BIT) == 0)

#define noncontiguous(M) (((M)->flags & NONCONTIGUOUS_BIT) != 0)

#define set_noncontiguous(M) ((M)->flags |= NONCONTIGUOUS_BIT)

#define set_contiguous(M) ((M)->flags &= ~NONCONTIGUOUS_BIT)

/* ARENA_CORRUPTION_BIT is set if a memory corruption was detected on the

arena. Such an arena is no longer used to allocate chunks. Chunks

allocated in that arena before detecting corruption are not freed. */

#define ARENA_CORRUPTION_BIT (4U)

#define arena_is_corrupt(A) (((A)->flags & ARENA_CORRUPTION_BIT))

#define set_arena_corrupt(A) ((A)->flags |= ARENA_CORRUPTION_BIT)

/*

Set value of max_fast.

Use impossibly small value if 0.

Precondition: there are no existing fastbin chunks.

Setting the value clears fastchunk bit but preserves noncontiguous bit.

*/

#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

ptmalloc 默认情况下会调用 set_max_fast(s) 将全局变量 global_max_fast 设置为 DEFAULT_MAXFAST，即设置 fastbins 中 chunk 的最大值，当MAX_FAST_SIZE被设为0时，系统就不支持 fastbin.

fastbin 的索引

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

由于 fast bin 中的inuse 始终为1，因此不回合并。但是当释放的 chunk 与该 chunk 相邻的空闲 chunk 合并后的大小大于 FASTBIN_CONSOLIDATION_THRESHOLD时，内存碎片可能就比较多了，我们就需要把 fast bins 中的 chunk 都进行合并，减少内存碎片对系统的影响。

Small bin

small bin 中的每个 chunk 的大小与其所在的 bin 的 index 的关系为： chunk_size = 2* SIZE_SZ * index，具体如下：

small bins 中一共有62个循环双向链表，每个链表中的 chunk 大小相同。FIFO规则，因此同一个链表中先被释放的 chunk 会先被分配出去。

small bin 相关的宏如下：

#define NSMALLBINS 64

#define SMALLBIN_WIDTH MALLOC_ALIGNMENT

// 是否需要对small bin的下标进行纠正

#define SMALLBIN_CORRECTION (MALLOC_ALIGNMENT > 2 * SIZE_SZ)

#define MIN_LARGE_SIZE ((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH)

//判断chunk的大小是否在small bin范围内

#define in_smallbin_range(sz) \

((unsigned long) (sz) < (unsigned long) MIN_LARGE_SIZE)

// 根据chunk的大小得到small bin对应的索引。

#define smallbin_index(sz) \

((SMALLBIN_WIDTH == 16 ? (((unsigned) (sz)) >> 4) \

: (((unsigned) (sz)) >> 3)) + \

SMALLBIN_CORRECTION)

fast bin 与 small bin 中的 chunk 的大小有很大一部分是重合的(？？？额……我咋没看出来？)

那么 small bin 中对应的 bin 有什么用呢？

答：有时候 fast bin 中的 chunk 是可能被放到 small bin 中去的。(什么情况下？)

Large bin

Large bins 中一共有63 个bin，每个 bin 中的 chunk 的大小不一致，而处于一定区间范围内。

此外，63 个 bin 被分为6组，每组 bin 中的 chunk 大小之间的公差一致，具体如下：

这里我们以32位平台为例，第一个large bin的起始 chunk 大小为 512 字节，因此该 bin 可存储的 chunk 的范围是[512, 512+64]。

第一个 large bin 的起始 chunk 为512字节，那么 512 >>6 =8，因此下标为56+8=64。

Unsorted Bin

unsorted bin 可以视为 空闲 chunk 回归其所属 bin 之前的缓冲区。

/* The otherwise unindexable 1-bin is used to hold unsorted chunks. */

#define unsorted_chunks(M) (bin_at(M, 1))

unsorted bin 处于 bin 数组下标1处，因此 unsorted bin 只有1个链表。乱序原因如下：

(1)当一个较大的 chunk 被分割成2个后，如果剩下的部分大于 MINSIZE，就会被放到 unsorted bin中。

(2)释放一个不属于 fast bin 的chunk ，且该chunk 不与 top chunk 相邻，该 chunk 会被首先放到 unsorted bin中。

遍历顺序依然是FIFO。

根据 chunk 的大小统一获得 chunk 所在的索引

#define bin_index(sz) \

((in_smallbin_range(sz)) ? smallbin_index(sz) : largebin_index(sz))

TOP chunk

glibc 中对 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))

程序第一次 malloc 时， heap 会被分为2块，一块给用户，一块给 top chunk。

top chunk 相当于 堆的物理地址最高的 chunk。当所有的 bin 无法满足用户请求时，如果大小不小于指定大小，就进行分配，并将剩下的部分作为新的 top chunk。否则，就对heap 进行拓展后再分配。

在 main arena 中通过 sbrk 拓展 heap，在 thread arena 中使用 mmap 拓展 heap。

top chunk 的 prev_inuse 也是始终为1.

初始情况下，可以将 unsorted bin 作为 top chunk。

last remainder

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