Heap 基础知识

malloc

#include <stdlib.h>
void *malloc(size_t size);

size = 0时，返回系统允许的最小内存块

32位系统下malloc(0)分配8Bytes，64位分配16Bytes

calloc

会清空chunk，并且不从tcache种拿chunk，但是free时还是会放到tcache bin

brk

堆段的起点和终点标识符：start_brk、brk（program brk)

不开ASLR，初始时都指向bss段末尾（end_data)

开启ASLR，会随机向后偏移一段距离

brk()函数作用为抬高brk指针，获取一段heap

程序开始时heap大小为0，第一次申请堆的时候，通过brk()向系统申请一段内存 main_arena，后面malloc都会从main_arena中申请内存

chunk

struct malloc chunk{
    INTERNAL_SIZE_T mchunk_prev_size; /* Size of previous chunk (if free).*/
    INTERNAL_SIZE_T mchunk_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;
}
typedef struct malloc_chunk* mchunkptr;

allocated chunk

prevsize ：如果前一个chunk是free的（这里指的是内存中的前一个，而不是freelist中的前一个），它代表前一个chunk的大小；如果不是free的，存储前一个的user data 。32位中是4字节，64位中是8字节

size：此chunk大小。最低3位用来存储N（chunk 在 non_main_arena里为1）、M（chunk是mmap得到的为1）、P（前一个chunk已被分配为1 对应prevsize），因此size是8字节对齐的

没有 fd bk fd_nextsieze bk_nextsize

userdata：数据

（下一个chunk的prevsize也会存储userdata）

#define request2size(req) ...   //可以计算申请字节需要实际分配多少字节

chunk是在prevsize开始，但是malloc返回的指针指向userdata

free chunk

prevsize：上一个chunk的userdata，因为上一个如果也是free，则会被合并（fast bin中可能会例外，后面会提及）

size：同上

fd bk：（在freelist中的）前一个/后一个chunk

top chunk

位于arena顶部。在所有bin都没有满足需求的chunk时，从top chunk切割

top chunk 不够，在main_arena中会用brk扩张top chunk，non_main_arena中，用mmap分配新的堆

Bin

除了fastbin被存储在一个长度为10的fastbinY的数组里，其余的small large unsorted bin都存储在一个bins数组里

NBINS是126，包括1个unsorted bin，62个small bin，63个large bin。

#### fast bin

在free一个chunk到fast bin时，它下一个chunk的P位（PREV_INUSE)是不会变的，还是为1，为了加快free的效率。因此地址连续的两个chunk 被free到fast bin，他们不会被合并。

content的大小范围：32位：8~80，64位：16~160，都是10个bin，但是实际上fastbin的大小范围并不包含最大的两个bin (64bit 0x80就已经不进fastbin了)

新的chunk加入bin时，fd指向原来的栈顶，先进后出（LIFO）

small bin

大小范围

32位，最小为16字节，公差为8，最大为504字节，所以是62个small bin

64为，最小为32字节，公差为16，最大为1008字节

large bin

大小范围

32位（大于等于512字节）64位（大于等于1024字节），每个链表里的chunk不一定一样大，只要是属于某个特定区间就行

63个bin被分为6组

	数量	公差
1	32	64字节
2	16	512
3	8	4096
4	4	32768
5	2	262144
6	1	不限制

第一组起始大小是512，也就是第一组的第一个bin的范围为[512,512+64) ， 最后一个为[512 + 64*31, 512 + 64*32)

第二组接着第一组的末尾，第一个bin也就是[2560, 2560+ 512)，以此类推

每个的具体大小可在第四个参考文献里看

unsorted bin

释放一个不属于 fast bin 的 chunk，并且该 chunk 不和 top chunk 紧邻时，该 chunk 会被首先放到 unsorted bin 中

分配时，如果在unsorted bin里没找到合适的chunk，则把unsorted bin里的chunk分配到small 和 large里，，然后再在 bin 中分配合适的 chunk

内存分配流程

内存释放流程

tcache相关知识

以下全是64位机器来说

tcache从2.26开始才有，tcache同fastbin，先进后出，不动inuse

tcache出现后，每次产生堆都会先产生一个0x250大小的堆块，位于堆的开头。这0x250中（header占16字节），前0x40字节，对应64条tcache的链表，描述每个链表中的个数（每个链表最多7个chunk），然后0x200字节对应每个链表的开头地址。

tcache的64个链表从0x20开始，到0x410结束，公差16字节

tcache的链表指针指向的是chunk的content，而不是开头

在老的2.27中没有doublefree检查

参考文献

Heap Exploitation

Understanding glibc malloc

Syscalls used by malloc

glibc 内存管理 ptmalloc 源代码分析

Painless intro to the Linux userland heap