众所周知，解决问题需要数据结构+算法。
对于malloc和free，其需要解决的问题有：
- 满足能够分配任意大的内存的需求
- 内存能够有效回收和重复利用
- 效率足够高，尽量保证安全（但我们学二进制安全的，总是能找到漏洞，或者说利用方法）
那么，就可以看到为满足这样的需求所设计的数据结构和算法。
要了解malloc和free的实现原理，最好的办法就是去查看glibc中实现这两个函数的代码，而在分析代码时，数据结构和算法是我们的两个主线。
定义几个名词，方便阐述一些事情：
p32和p64：这两个本来是pwntools中的两个函数，用于包装数据
首先我们知道机器字长的概念，也就是机器的寄存器的大小，
32位机器的寄存器有32个二进制位，也就是4个字节，8个十六进制位
64位机器的寄存器有64个二进制位，也就是8个字节，16个十六进制位
那么我们用p32来代指32位机器的机器字长， p64代指64位机器的机器字长。
我们默认是在64位机器上进行实验，因此默认使用p64
二、数据结构 0x00 概论
我们知道很多数据结构，例如二叉树、图等，单把这些数据结构拿出来似乎看不出什么名堂，需要在解决具体问题时与算法结合才能看出其特点。堆所用的数据结构更是如此，有些功能很明显的数据结构就直接进行说明，对于一些不方便解说的数据结构，后面展示算法时就会明晰。
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;
};
有关malloc_chunk，需要牢记三点：
malloc_chunk是堆中的各个内存块真正的载体malloc返回的是fd字段的地址，也就是说，从fd字段开始才是真正存储数据的地方- 不要认为一个
malloc_chunk”结构体“占用的内存大小就是定义中展示的六个字段所占用的内存大小（否则怎么存储更大的数据呢？），也不要认为后四个字段一定能够按照它们被声明的类型那样正常工作
对于一个线程，无论是主线程还是新线程，当在这个线程上执行的代码第一次申请内存时，都会出现线程间独立的arena。这里不讨论多线程的情况，先只考虑单一主线程的情况。
main_arena是一个全局变量，存储在libc.so的数据段内
具体什么作用我也不知道，总之对于实现malloc本身的功能来说很重要就是了。
正如其命名，它用于记录堆中的全局状态，从而能够对堆进行管理。
malloc_state也是一个全局变量，存储在libc.so的数据段内
malloc_state记录着每一个arena当前申请的内存的具体状态，
按照CTF-wiki中的描述，已知每个线程首次申请堆内存时都会创建一个
arena，CTF-wiki原话是“无论是 thread arena 还是 main arena，它们都只有一个 malloc state 结构。由于 thread 的 arena 可能有多个，malloc state 结构会在最新申请的 arena 中。”
感觉有点难以理解，因为假设有三个线程依次申请了堆内存，假定依次为Main, Theard1, Thread2，那么是不是只有Thread2 arena有对应的malloc_state？那Thread1 arena和Main arena的信息保存在哪里？还怎么继续管理？我暂且蒙在鼓里。不过，由于我们目前只考虑仅有主线程的程序，所以暂且不需要在意多线程的情况。
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;
};
__libc_lock_define(, mutex);涉及到多线程，暂且不进行展开了。flags：类似于标志寄存器，实际上被当成一个boolean型数组使用，每一个比特位是都标记某个情况是true还是false。以下是其中几个标志位的意义：（从右往左数比特位）- 第1位（与0000 0001b位运算）：是否有fastbin chunk——1无0有
- 第2位（与0000 0010b位运算）：能否返回连续的虚拟地址空间——1无0有
- 第3位（与0000 0100b位运算）：arena是否corrupt——1是0否
- 其中
mchunkptr和mfastbinptr就是struct malloc_chunk*，fastbinsY和bins涉及到堆的回收管理，但是可以看到，它们都被定义成了指针数组 top：在pwndbg中调试程序，输入heap指令查看到的视图中的top chunk的地址last_remainder：最新的chunk分割后剩下的部分
0x04 heap_info
malloc_state似乎还具有链表结构？指向哪个malloc_state？也许这就和对多线程的支持有关了。
说明摘自CTF-wiki
程序刚开始执行时，每个线程是没有 heap 区域的。当其申请内存时，就需要一个结构来记录对应的信息，而 heap_info 的作用就是这个。而且当该 heap 的资源被使用完后，就必须得再次申请内存了。此外，一般申请的 heap 是不连续的，因此需要记录不同 heap 之间的链接结构。
该数据结构是专门为从 Memory Mapping Segment 处申请的内存准备的，即为非主线程准备的。
主线程可以通过 sbrk() 函数扩展 program break location 获得（直到触及 Memory Mapping Segment），只有一个 heap，没有 heap_info 数据结构。
#define HEAP_MIN_SIZE (32 * 1024)
#ifndef HEAP_MAX_SIZE
# ifdef DEFAULT_MMAP_THRESHOLD_MAX
# define HEAP_MAX_SIZE (2 * DEFAULT_MMAP_THRESHOLD_MAX)
# else
# define HEAP_MAX_SIZE (1024 * 1024) /* must be a power of two */
# endif
#endif
/* HEAP_MIN_SIZE and HEAP_MAX_SIZE limit the size of mmap()ed heaps
that are dynamically created for multi-threaded programs. The
maximum size must be a power of two, for fast determination of
which heap belongs to a chunk. It should be much larger than the
mmap threshold, so that requests with a size just below that
threshold can be fulfilled without creating too many heaps. */
/***************************************************************************/
/* A heap is a single contiguous memory region holding (coalesceable)
malloc_chunks. It is allocated with mmap() and always starts at an
address aligned to HEAP_MAX_SIZE. */
typedef struct _heap_info
{
mstate ar_ptr; /* Arena for this heap. */
struct _heap_info *prev; /* Previous heap. */
size_t size; /* Current size in bytes. */
size_t mprotect_size; /* Size in bytes that has been mprotected
PROT_READ|PROT_WRITE. */
/* Make sure the following data is properly aligned, particularly
that sizeof (heap_info) + 2 * SIZE_SZ is a multiple of
MALLOC_ALIGNMENT. */
char pad[-6 * SIZE_SZ & MALLOC_ALIGN_MASK];
} heap_info;
这里先不涉及malloc函数、free函数涉及的算法，仅涉及对这些结构体进行基本 *** 作的算法。
其中，大部分算法的实现载体是宏定义函数。由于宏定义函数的特殊性（即其本质是直接赋值代码到调用位置），我们实际上并不能写出与其用法和功能都完全一致的一般函数。
0x01 *** 作malloc_chunk的 1. chunk与mem指针头部的转换/* conversion from malloc headers to user pointers, and back */
#define chunk2mem(p) ((void *) ((char *) (p) + 2 * SIZE_SZ))
#define mem2chunk(mem) ((mchunkptr)((char *) (mem) -2 * SIZE_SZ))
其中，SIZE_SZ就是p64，字面量以字节为单位，也就是说SIZE_SZ=0x8
这样我们也定义几个词：
- chunk：从chunk结构体的起始位置开始一直到这个chunk结束，这段内存称作chunk
- mem：
malloc返回的是fd字段的指针，这里是用户真正输入数据的起始位置，那么这个位置就称作mem - chunk_head：chunk去掉了mem的部分，也就是chunk结构体的
prev_size和size字段
对两个宏定义函数”一言以蔽之“：
- check2mem就是把指针向后移动两个p64，返回mem指针
- mem2chunk就是把指针向前移动两个p64，返回chunk指针
/* The smallest possible chunk */
#define MIN_CHUNK_SIZE (offsetof(struct malloc_chunk, fd_nextsize))
/* The smallest size we can malloc is an aligned minimal chunk */
//MALLOC_ALIGN_MASK = 2 * SIZE_SZ -1
#define MINSIZE \
(unsigned long) (((MIN_CHUNK_SIZE + MALLOC_ALIGN_MASK) & \
~MALLOC_ALIGN_MASK))
实际上就是4个p64的大小，也就是0x20（实际上写数据的空间是0x10）
3. 检查分配的内存是否对齐/* Check if m has acceptable alignment */
// MALLOC_ALIGN_MASK = 2 * SIZE_SZ -1
#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)
MALLOC_ALIGN_MASK可以就是0xF，其二进制形式为0x1111，也就是低四位二进制位都是1
考虑到堆视图中所有chunk的地址，最后一位数都是0，也就是说其后四个二进制位都是0，且每一个chunk的实际size都是0x10的整数倍，这应该就是所谓的”对齐“
那么两个aligned函数应该是兼具了检测chunk的地址和实际内存大小是否对齐的检查的功能。
这也启示我们：
如果要涉及伪造chunk的 *** 作，或许要选用一个似乎是”对齐“的数值
由于对齐，chunk的size字段低四位比特位都是0，其中低三位被我们选作用标志位，因此我们在pwndbg中查看堆视图的时候，size字段往往不是”准确“值，而是包含了标志位的值。
三个标志位从高到低的意义分别为：
- NON_MAIN_ARENA，记录当前 chunk 是否不属于主线程，1 表示不属于，0 表示属于。
- IS_MAPPED，记录当前 chunk 是否是由 mmap 分配的。
- PREV_INUSE，记录前一个 chunk 块是否被分配。一般来说，堆中第一个被分配的内存块的 size 字段的 P 位都会被设置为 1，以便于防止访问前面的非法内存。当一个 chunk 的 size 的 P 位为 0 时，我们能通过 prev_size 字段来获取上一个 chunk 的大小以及地址。这也方便进行空闲 chunk 之间的合并。
分别记为A|M|P
4. 判断申请的字节数是否过大/*
Check if a request is so large that it would wrap around zero when
padded and aligned. To simplify some other code, the bound is made
low enough so that adding MINSIZE will also not wrap around zero.
*/
#define REQUEST_OUT_OF_RANGE(req) \
((unsigned long) (req) >= (unsigned long) (INTERNAL_SIZE_T)(-2 * MINSIZE))
注意这里的-2 * MINSIZE，实际上是0xFFFF FFFF FFFF FFF0。被转换成无符号数是一个特别大的数。
5. 将用户请求内存大小转为实际分配内存大小/* pad request bytes into a usable size -- internal version */
//MALLOC_ALIGN_MASK = 2 * SIZE_SZ -1
#define request2size(req) \
(((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE) \
? MINSIZE \
: ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)
/* Same, except also perform argument check */
#define checked_request2size(req, sz) \
if (REQUEST_OUT_OF_RANGE(req)) { \
__set_errno(ENOMEM); \
return 0; \
} \
(sz) = request2size(req);
request2size的算法具体原理是什么我们不关心，只需要知道这个宏会算出一个不小于req和MINSIZE的最小的能整除的2 * SIZE_SZ数就可以了，这个数才是实际上分配的内存的大小。
checked_request2size则是综合封装了检测申请数据是否过大和把req转换成size
/* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */
#define PREV_INUSE 0x1
/* extract inuse bit of previous chunk */
#define prev_inuse(p) ((p)->mchunk_size & PREV_INUSE)
/* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */
#define IS_MMAPPED 0x2
/* check for mmap()'ed chunk */
#define chunk_is_mmapped(p) ((p)->mchunk_size & IS_MMAPPED)
/* size field is or'ed with NON_MAIN_ARENA if the chunk was obtained
from a non-main arena. This is only set immediately before handing
the chunk to the user, if necessary. */
#define NON_MAIN_ARENA 0x4
/* Check for chunk from main arena. */
#define chunk_main_arena(p) (((p)->mchunk_size & NON_MAIN_ARENA) == 0)
/* Mark a chunk as not being on the main arena. */
#define set_non_main_arena(p) ((p)->mchunk_size |= NON_MAIN_ARENA)
/*
Bits to mask off when extracting size
Note: IS_MMAPPED is intentionally not masked off from size field in
macros for which mmapped chunks should never be seen. This should
cause helpful core dumps to occur if it is tried by accident by
people extending or adapting this malloc.
*/
#define SIZE_BITS (PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
实际上就是涉及位运算的 *** 作，看看就得了，具体怎么实现不需要过度关心
7. 获取chunk size/* Get size, ignoring use bits */
#define chunksize(p) (chunksize_nomask(p) & ~(SIZE_BITS))
/* Like chunksize, but do not mask SIZE_BITS. */
#define chunksize_nomask(p) ((p)->mchunk_size)
chunksize_nomask返回没有去除标志位的size，chunksize返回去除了标志位的size
/* Ptr to next physical malloc_chunk. */
#define next_chunk(p) ((mchunkptr)(((char *) (p)) + chunksize(p)))
这个算法一定要牢记，之后涉及的漏洞利用 *** 作很可能利用它。
9. 获取前一个chunk的信息/* Size of the chunk below P. Only valid if !prev_inuse (P). */
#define prev_size(p) ((p)->mchunk_prev_size)
/* Set the size of the chunk below P. Only valid if !prev_inuse (P). */
#define set_prev_size(p, sz) ((p)->mchunk_prev_size = (sz))
/* Ptr to previous physical malloc_chunk. Only valid if !prev_inuse (P). */
#define prev_chunk(p) ((mchunkptr)(((char *) (p)) - prev_size(p)))
这个算法也要牢记
10. 当前chunk使用状态的相关 *** 作/* extract p's inuse bit */
#define inuse(p) \
((((mchunkptr)(((char *) (p)) + chunksize(p)))->mchunk_size) & PREV_INUSE)
/* set/clear chunk as being inuse without otherwise disturbing */
#define set_inuse(p) \
((mchunkptr)(((char *) (p)) + chunksize(p)))->mchunk_size |= PREV_INUSE
#define clear_inuse(p) \
((mchunkptr)(((char *) (p)) + chunksize(p)))->mchunk_size &= ~(PREV_INUSE)
可以看到，这里都是通过修改物理相邻的前一个chunk的size标志位来改变自己的使用状态，这里也需要额外关注
11. 涉及chunk_head的一些 *** 作/* Set size at head, without disturbing its use bit */
// SIZE_BITS = 7
#define set_head_size(p, s) \
((p)->mchunk_size = (((p)->mchunk_size & SIZE_BITS) | (s)))
/* Set size/use field */
#define set_head(p, s) ((p)->mchunk_size = (s))
/* Set size at footer (only when chunk is not in use) */
#define set_foot(p, s) \
(((mchunkptr)((char *) (p) + (s)))->mchunk_prev_size = (s))
/* Treat space at ptr + offset as a chunk */
#define chunk_at_offset(p, s) ((mchunkptr)(((char *) (p)) + (s)))
/* check/set/clear inuse bits in known places */
#define inuse_bit_at_offset(p, s) \
(((mchunkptr)(((char *) (p)) + (s)))->mchunk_size & PREV_INUSE)
#define set_inuse_bit_at_offset(p, s) \
(((mchunkptr)(((char *) (p)) + (s)))->mchunk_size |= PREV_INUSE)
#define clear_inuse_bit_at_offset(p, s) \
(((mchunkptr)(((char *) (p)) + (s)))->mchunk_size &= ~(PREV_INUSE))
0x02 *** 作bin的
我们之前看到，bin是定义在malloc_state内的一个数组，它们实际上是用作chunk的回收管理
bin一共有254个索引，其中不同索引范围的意义和作用都不同
-
bins[0]和bins[1]是unsorted bin -
bins[2]到bins[63]这62个索引是small bin -
剩下的190个索引（
bins[63]到bins[253]）是large bin
在这里可以看到，每一种bin所占索引数量都是偶数
mchunkptr bins[ NBINS * 2 - 2 ];
以下表格来自CTF-wiki
| 含义 | bin1 的 fd/bin2 的 prev_size | bin1 的 bk/bin2 的 size | bin2 的 fd/bin3 的 prev_size | bin2 的 bk/bin3 的 size |
|---|---|---|---|---|
| bin 下标 | 0 | 1 | 2 | 3 |
bin的类型是mchunkptr也就是struct malloc_chunk *，我想，我们应该这样认识bins数组
| bin1的prev | bin1的size |
|---|---|
| bins[0]:bin1的fd/bin2的prev | bins[1]:bin1的bk/bin2的size |
| bins[2]:bin2的fd/bin3的prev | bins[3]:bin2的bk/bin3的size |
| bins[4]:bin3的fd/bin4的prev | bins[5]:bin3的bk/bin4的size |
| bins[6]:bin4的fd/bin5的prev | bins[7]:bin4的bk/bin5的size |
| bins[8]:bin5的fd/bin6的prev | bins[9]:bin5的bk/bin6的size |
| bins[10]:bin6的fd/bin7的prev | bins[11]:bin6的bk/bin7的size |
| bins[12]:bin7的fd/bin8的prev | bins[13]:bin7的bk/bin8的size |
bins被声明为一个mchunkptr数组，恰好，malloc_chunk的fd和bk字段的类型都是mchunkptr，那么，如果把bins[0]，bins[1]看作prev_size和size，bins[2]和bins[3]看作是fd和bk，同时，bins[0], bins[1], bins[2], bins[3]又是相邻的，那么这四个元素大概就可以看作是一个完整的malloc_chunk了
bins是这样维护堆的：
首先，bins数组中每相邻的两个元素构成一个bin，我们知道仅就bins数组而言分成了三类bin
每一类bin都只负责某一特定大小或者是某一特定大小范围的chunk的维护，被维护的chunk以双向链表的形式链接。我们又知道，bins数组每相邻的两个元素，与这两个元素的前两个元素能够构成一个malloc_chunk，这个特殊的chunk就是访问整个双向链表的入口。
1. 获取bin那么有人要问了，为什么不能一个数组元素对应一个bin呢？这是因为数组在创建之初就已经初始化了，如果我们要让每个元素都指向一个完整的
malloc_chunk用来当遍历双向链表的入口，那么或许还会用malloc为每个指针分配相应的内存。我想，开发malloc函数的时候应该用不了malloc函数吧……
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))
可以看到，mbinptr和mchunkptr都是struct malloc_chunk *
这个宏就是用来以mbinptr的形式来取出一个bin。譬如说bin_at(2)就是一个以bins[0]为prev_size，以bins[1]为size，以bins[2]为fd，以bins[3]为bk的malloc_chunk的指针。尽管对于这个特殊chunk，用到的只有fd和bk
//analog of ++bin
#define next_bin(b) ((mbinptr)((char *) (b) + (sizeof(mchunkptr) << 1)))
譬如说我们想获取bin_at(1)的下一个bin，也就是bin_at(2)，只需要把地址右移两个p64就可以了。（<< 1就是乘以2，位移符号应该会计算的更快）
/* Reminders about list directionality within bins */
// 这两个宏可以用来遍历bin
// 获取 bin 的位于链表头的 chunk
#define first(b) ((b)->fd)
// 获取 bin 的位于链表尾的 chunk
#define last(b) ((b)->bk)
#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)
重点分析smallbin_index：
不知道为什么MALLOC_ALIGNMENT和SMALLBIN_WIDTH作为等于0xF的宏常量为什么会等于16，那么SMALLBIN_CORRECTION不也恒为0了嘛
那么smallbin_index直接把sz除以8就得到对应的索引了。（sz是0x10的整数倍，所以一定可以除得尽8，不过此处实际上用的是右移运算）
smallbin对应bins数组的bins[2]到bins[63]，也就是说第一个small bin是bin_at(2)，这也对应了最小size：0x10
#define largebin_index(sz) \
(SIZE_SZ == 8 ? largebin_index_64(sz) : MALLOC_ALIGNMENT == 16 \
? largebin_index_32_big(sz) \
: largebin_index_32(sz))
这是直接通过sz求对应large bin索引的宏，其涉及到的三个宏largebin_index， largebin_index_32_big和largebin_index_32嵌套了大量三目运算符，相当复杂，因此我们这里不贴原先的宏定义代码，而是改写出与之等效的正常函数的代码
unsigned long largebin_index_32(SIZE_T sz) {
if(sz >> 6 <= 38) {
return 56 + sz >> 6;
}else if(sz >> 9 <= 20) {
return 91 + sz >> 9;
}else if(sz >> 12 <= 10) {
return 110 + sz >> 12;
}else if(sz >> 15 <= 4) {
return 110 + sz >> 15;
}else if(sz >> 18 <= 2) {
return 124 + sz >> 18;
}else {
return 126;
}
}
unsigned long largebin_index_32_big(SIZE_T sz) {
if(sz >> 6 <= 45) {
return 49 + sz >> 6;
}else if(sz >> 9 <= 20) {
return 91 + sz >> 9;
}else if(sz >> 12 <= 10) {
return 110 + sz >> 12;
}else if(sz >> 15 <= 4) {
return 110 + sz >> 15;
}else if(sz >> 18 <= 2) {
return 124 + sz >> 18;
}else {
return 126;
}
}
unsigned long largebin_index_64(SIZE_T sz) {
if(sz >> 6 <= 48) {
return 48 + sz >> 6;
}else if(sz >> 9 <= 20) {
return 91 + sz >> 9;
}else if(sz >> 12 <= 10) {
return 110 + sz >> 12;
}else if(sz >> 15 <= 4) {
return 119 + sz >> 15;
}else if(sz >> 18 <= 2) {
return 124 + sz >> 18;
}else {
return 126;
}
}
可以看到，large bin大小对应的索引值是比较复杂的，CTF-wiki中对此的总结如下：
6. 直接计算序列
组 数量 公差 1 32 64B 2 16 512B 3 8 4096B 4 4 32768B 5 2 262144B 6 1 不限制 这里我们以 32 位平台的 large bin 为例，第一个 large bin 的起始 chunk 大小为 512 字节，位于第一组，所以该 bin 可以存储的 chunk 的大小范围为 [512,512+64)。
#define bin_index(sz) \
((in_smallbin_range(sz)) ? smallbin_index(sz) : largebin_index(sz))
0x03 Fast Bin
在之前的malloc_state中，可以看到一个mfastbinptr fastbinsY[NFASTBINS];
mfastbinptr当然也是struct malloc_chunk *
#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)
#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 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)
可以看到，fastbin每个bin之间的大小差距是两个p64
fastbin以单向链表的形式维护数组，因此一个fastbinY中的元素就是一个fastbin，且每一个bin都是LIFO表
0x04 Top Chunk
以下内容来自CTF-wiki
0x05 last remainder程序第一次进行 malloc 的时候，heap 会被分为两块，一块给用户，剩下的那块就是 top chunk。其实，所谓的 top chunk 就是处于当前堆的物理地址最高的 chunk。这个 chunk 不属于任何一个 bin，它的作用在于当所有的 bin 都无法满足用户请求的大小时，如果其大小不小于指定的大小，就进行分配，并将剩下的部分作为新的 top chunk。否则，就对 heap 进行扩展后再进行分配。在 main arena 中通过 sbrk 扩展 heap，而在 thread arena 中通过 mmap 分配新的 heap。
需要注意的是，top chunk 的 prev_inuse 比特位始终为 1，否则其前面的 chunk 就会被合并到 top chunk 中。
初始情况下，我们可以将 unsorted chunk 作为 top chunk。
以下内容来自CTF-wiki
在用户使用 malloc 请求分配内存时，ptmalloc2 找到的 chunk 可能并不和申请的内存大小一致，这时候就将分割之后的剩余部分称之为 last remainder chunk ，unsort bin 也会存这一块。top chunk 分割剩下的部分不会作为 last remainder.
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）