翻到以前的笔记，整理一下
堆
elf中的堆和算法提到的堆不是一个东西，elf中提到的堆是被分配到的一块内存区域，和栈的区别主要是在于堆内存是动态分配的。也就是说，程序可以从heap段请求一块内存，或者释放一块内存
堆内存是全局的，即在程序的任意位置都可以访问堆，并不一定是要在malloc那个函数里访问，因为C语言使用指针指向动态分配的内存。但相比访问栈上的静态局部变量，使用指针也会带来一定的开销
（从低地址 $$\rightarrow$$ 高地址）
使用动态分配的内存
GLibc采用ptmalloc2内存分配器管理堆内存，增加了对多线程的支持
mmap
用于创建私有的匿名映射段，主要是为了分配一块新的内存，且这块内存只有调用mmap的进程可以使用，所以为私有的，与之相反的操作是munmap()，删除一块内存区域上的映射
多线程与Arena
每个线程要维护一些独立的数据结构，并且对这些数据结构的访问是需要加锁的。在ptmalloc2中，每个线程拥有自己的freelist（bins），也就是维护空闲内存的一个链表；以及自己的arena，一段连续的堆内存区域。特别的，主线程的arena叫做main_arena，注意只有main_arena可以访问heap段和mmap映射区域，non_main_arena只能访问mmap映射区域
线程较多时，互斥锁机制导致性能下降
第一次申请内存时还没有heap段，因此通过向上移动brk()，我们的main_arena（132KB的heap段）会被创建。无论后续申请的内存多大，malloc都会从main_arena中尝试取出一小块内存来进行分配，如果空间不够，main_arena可以通过brk()扩张，如果空闲太多，也可以缩小
对于non_main_arena，是由mmap()创建的1MB的内存空间映射到进程地址的空间，不过实际上也只有132KB可读可写，这132KB就是该线程的heap结构，或者叫non_main_arena
当申请的空间大于128KB且arena没有足够的空间时，无论在哪个arena里都只能通过mmap()分配内存
维护多个堆
main_arena只有一个堆，可以灵活的缩放
non_main_arena可以创建多个堆
所以在non_main_arena中，我们需要考虑如何维护多个堆的问题，这里涉及到三个头部：
-
heap_info：每个heap的头部，main_arena是没有的
-
malloc_state：arena的头部，main_arena的这个部分是全局变量而不属于堆段
-
malloc_chunk：每个chunk的头部
chunk的结构
Allocate chunk
prev_size：只有在前一个chunk空闲时才会表示前一个块的大小，否则这里是无效的，可以被前一个chunk征用（存储用户数据）
P：PREV_INUSE => 之前的chunk已经被分配则为1
M：IS_MAPPED => 当前chunk是mmap()得到的则为1
N：NON_MAIN_ARENA => 当前chunk在non_main_arena里则为1
mem指针：调用malloc时返回给用户的指针。实际上，真正的chunk是从chunk指针开始的
用户申请的内存大小不一定是用户数据可用的内存大小，由于字节对齐问题。要获得可用内存大小，可以用malloc_usable__size()获得
Free chunk
相比于Allocate chunk，fd和bk生效了。
由于free chunk会一直合并，知道前一个chunk是allocate chunk，所以free chunk的prev_size必定会被上一个chunk征用，用于存放用户数据
bk => back / fd => forward（指在bins中）
Top chunk
不属于bins，处于arena顶部。当所有的bin中都没有空闲的可用chunk时，我们切割top chunk来满足用户的内存申请。假设top chunk当前大小为N字节，用户申请了K字节的内存，那么top chunk会被切割为：
-
一个k字节的chunk，分配给用户
-
一个N-k字节的chunk，成为Last Remainder chunk
后者为新的top chunk，如果连top chunk都不够用了：
-
如果在main_arena中，则用brk()扩张top hcunk
-
如果在non_main_arena中，则用mmap()分配新的堆块
top chunk的PREV_INUSE位总为1
Last Remainder chunk
当需要分配一个比较小的k字节的chunk，但是small bins中找不到满足要求的，且Last Remainder chunk的大小N能满足要求，那么Last Remainder chunk将被切割为：
-
一个k字节的chunk，分配给用户
-
一个N-k字节的chunk，成为新的Last Remainder chunk
Bin的结构
bin实现了空闲链表的数据结构，用来存储空闲chunk，可分为：
-
10个fast bins => 存储在fastbinsY
-
1个unsorted bins => 存储在bin[1]
-
62个small bins => 存储在bin[2]~bin[63]
-
63个large bins => 存储在bin[64]~bin[126]
fast bins
像高速缓存，相邻空闲chunk不会被合并，这回导致外部碎片增多但是free效率提升，fast bins是10个LIFO的单链表，最后三个链表保留未使用
chunk大小（含chunk头部）：0x10~0x40（64位0x20~0x80）B，相邻bin存放的大小相差0x8（0x10）B
unsorted bin
像缓冲区buffer，大小超过fast bins阈值的chunk被释放会加入到这里，使得ptmalloc2可以复用最近释放的chunk，从而提升效率；双向循环链表
chunk大小：大于global_max_fast
small bins
小于0x200（0x400）B的chunk叫做small chunk，small bins可以存放的就是这些chunks，chunk大小同样是从16B开始每次+8B；双向循环链表，FIFO，和fast bins相反，且相邻的空闲chunk会被合并
chunk大小：0x10~0x1f0 B（0x20~0x3f0），相邻bin存放的大小相差0x8（0x10）B
large bins
大于等于0x200（0x400）B的chunk叫做large chunk，而large bins可以存放的就是这些large chunks；双向循环链表，插入和删除可以发生在任意位置，相邻空间chunk也会被合并，chunk大小比较复杂：
-
前32个bins：从0x200B开始每次+40B
-
接下来的16个bins：每次+0x200B
-
接下来的8个bins：每次+0x1000B
-
接下来的4个bins：每次+0x8000B
-
接下来的2个bins：每次+0x40000B
-
最后的一个bin：只有一个chunk，大小和large bins剩余的大小相同
同一个bin中chunks不是相同大小的，按大小降序排列。这和上面的几种bins都不一样，而在取出chunk时，也遵循best fit原则，取出满足大小的最小chunk
内存分配流程
内存释放流程
