heap

mmp函数：将硬盘上的一块区域映射为虚拟内存

void *mmap(void addr, size_t length, int prot, int flags, int fd, off_t offset); 创建共享内存映射
参数：
addr： 指定映射区的首地址。通常传NULL，表示让系统自动分配
length：共享内存映射区的大小。（<= 文件的实际大小，通常为文件大小）
prot： 共享内存映射区的读写属性。PROT_READ（读）、PROT_WRITE（写）、PROT_READ|PROT_WRITE（读写）
flags： 标注共享内存的共享属性。
MAP_SHARED（共享，会将映射区所做的操作反映到物理设备（磁盘）上。）
MAP_PRIVATE（私有，映射区所做的修改不会反映到物理设备。 ）
fd: 用于创建共享内存映射区的那个文件的 文件描述符。
offset：默认0，表示映射文件全部。偏移位置。需是 4k 的整数倍。
返回值：
成功：映射区的首地址。
失败：MAP_FAILED (void(-1))， errno

堆的大小对齐

堆的大小必须是2SIZE_SZ的整数倍，如果申请的内存大小不是2SIZE_SE的整数倍；32位系统中，SIZE_SE=4,64位系统中SIZE_SE=8;也就是32位系统堆大小为8的倍数，64位系统堆大小为16的倍数，8对应的2进制为1000，所以不管size如何变化对应的低3位固定位0；为了不浪费这3个比特位，它们从高到低分别被用来表示：

A flag

NON_MIAN_ARENA,记录当前chunk是否不属于主线程，1表示不属于，0表示属于。

P flag

IS_MAPPED,记录当前chunk是否是由mmap分配的。一般来说，堆中第一个被分配的内存块的size字段的p位都会被设置为1，以便于防止访问前面的非法内存。当一个chunk的size的p位为0时，我们能通过prev_size字段来获取上一个chunk的大小以及地址。这也方便进行空闲chunk之间的合并。

M flag

PREV_INUSE,记录前一个chunk块是否被分配。

prev_size

若前一个物理相邻的chunk是free chunk，则表示其大小。否则用于储存前一个chunk的数据

size

用于表示当前chunk的大小（整个chunk的大小，包括chunk头）

fd pointer

在bin中指向下一个（非物理相邻）空闲的chunk（chunk被分配后从fd开始是用户的数据）

bk pointer

在bin中指向上一个（非物理相邻）空闲的chunk

fd_nextsize

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

bk_nextsize

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

chunk结构

prev_size
size | A flag | M flag | P flag |
fd_pointer （未被分配时，被分配则为用户数据的开始）
bk_pointer
fd_nextsize
bk_nextsize
……….

bin

管理arena中空闲chunk的结构，以数组的形式存在，数组元素为对应大小的chunk链表的链表头，存在于arena的malloc_state中。

1. unsorted bin （队尾取chunk）
2. fast bin
3. small bins
4. large bins
5. (tcache)glibc-2.27

1.fast bins单向链表（先进后出）

• LIFO
• 管理16、24、32、40、48、56、64Bytes 的 free chunks（32位下默认）
• 其中的chunk的in_use位（下一个物理相邻的chunk的p位）总是为1

2.unsorted bin

• bin[1]
• 双向链表
• 管理刚刚释放还未分类的chunk
• 可以视为空闲chunk回归其所属bin之前的缓冲区
• unsorted bin的特性，若unsorted bin中只有一个chunk的时候，这个chunk的fd和bk指针存放的都是main_arena+88或者main_arena+96，通过main_arena我们就可以获取到libc的基地址。

3.small bins

• bins[2]~bins[63]
• 62个循环双向链表
• FIFO
• 管理16、24、32、40、…….、504Bytes的free chunk（32位以下）
• 每个链表中储存的chunk大小都一致

4.larg bins

• bins[64]~bins[126]
• 63个循环双向链表
• FIFO
• 管理大于504Bytes的free chunks(32位以下)
• 每个链表储存的chunk大小不一定相同

5.tcache bin（先进后出）

• Tcache全名为Thread Local Caching，它为每个线程创建一个缓存，里面包含了一些小堆块。无须对arena上锁既可以使用，所以采用这种机制后分配算法有不错的性能提升。每个线程默认使用64个单链表结构的bins，每个bins最多存放7个chunk，64位机器16字节递增，从0x20到0x410，也就是说位于以上大小的chunk释放后都会先行存入到tcache bin中。对于每个tcache bin单链表，它和fast bin一样都是先进后出，而且prev_inuse标记位都不会被清除，所以tcache bin中的chunk不会被合并，即使和Top chunk相邻。
  另外tcache机制出现后，每次产生堆都会先产生一个0x250大小的堆块，该堆块位于堆的开头，用于记录64个bins的地址（这些地址指向用户数据部分）以及每个bins中chunk数量。在这个0x250大小的堆块中，前0x40个字节用于记录每个bins中chunk数量，每个字节对应一条tcache bin链的数量，从0x20开始到0x410结束，刚好64条链，然后剩下的每8字节记录一条tcache bin链的开头地址，也是从0x20开始到0x410结束。还有一点值得注意的是，tcache bin中的fd指针是指向malloc返回的地址，也就是用户数据部分，而不是像fast bin单链表那样fd指针指向chunk头。
• libc2.26以前的libc是没有该机制的。

malloc

• 它根据用户申请的内存块大小以及相应大小的chunk通常使用的频度（fastbin chunk,small chunk,large chunk）,依次实现了不同的分配方法。
• 它由小到达依次检查不同的bin中是否有相应的空闲块可以满足用户的请求的内存。
• 当所有的空闲chunk都无法满足时，它会考虑top chunk。当top chunk也无法满足时，堆分配器才会进行内存块申请。

free

• 它会将用户暂且不用的chunk回收给堆管理器，适当的时候还会归还给操作系统。
• 它依据chunk的大小来优先试图将free chunk链入teache或者是fast bin。不满足则链入unsorted bin中。
• 在条件满足时free函数遍历usorted bin并将其中的物理相邻的free chunk合并，将相应大小的chunk分类放入small bin或者large bin中。
• 除了tcache chunk与fast bin chunk，其他chunk在free时会与其物理相邻的free chunk合并。