Malloc技术原理解析以及在转转搜索业务上的实践( 三 ) _Malloc

当p=1时，表示前一个chunk正在使用，此时prev_size字段无效。

值得注意的是， ptmalloc分配的第一个块总是将p设为1 ，以防止程序引用到不存在的区域。此外，还有M和A字段，其中M=1表示该内存块来自mmap映射区域，而M=0表示来自heap区域；A=0表示主分配区分配， A=1表示非主分配区分配。

文章插图
图片
在内存中，空闲的chunk具有如下结构：

fp和bp分别指向前一个和后一个空闲链表上的chunk；
fp_nextsize和bp_nextsize分别指向前一个空闲chunk和后一个空闲chunk的大小，用于在空闲链表上快速查找合适大小的chunk 。

这些指针的值都存储在原始用户区域中，这样就不需要为每个chunk准备单独的内存存储指针。

文章插图
图片
ptmalloc还维护了多个bin ，用于存储相似大小的chunk ，这些bin以双向链表的形式链接在一起。总共有128个bin ，根据chunk的大小可以分为四种类型：

Fast bin（小于64B）
Unsorted bin
Small bin
Large bin

这些bin被保存在数组fastbinsY（fast bin）和bins（其他bin）中。当用户调用malloc时，系统可以快速查找适合用户需求大小的内存块是否在这些bin中，并通过双向链表查找合适的chunk内存块提供给用户使用。
Fast bins记录着大小以8字节递增的Fast bin链表，主要用于存储较小的内存块（小于默认的max_fast大小64B），这些chunk一般不会被合并，因此分配速度很快。
Unsorted bin的队列使用bins数组的第一个bin ，相当于small bins和large bins的一个缓冲区，存放最近释放的大小大于max_fast 的chunk、合并后的chunk以及切割剩余的chunk等。这个bin没有尺寸上限，可以快速找到最近释放的chunk 。如果找不到合适大小的chunk ， ptmalloc会清空unsorted bin ，将其中的chunks按照大小分类放入其他适当的bin中。
Small bin保存大小小于512字节的chunk ，从2开始编号，一共有63个，相邻的small bin之间相差8字节。同一个small bin中的chunk具有相同的大小。在释放一个chunk时，会检查其前后的chunk是否为空闲，如果是，则将它们合并成一个新的chunk ，然后将新chunk添加到unsorted bin的前端。
Large bin保存大小大于等于512字节的chunk ，位于small bin之后。每个bin包含了一个给定范围内的chunk ，这些chunk按大小递减排序。在分配chunk时，会寻找大小最合适的chunk ，并进行切割，剩余部分放入unsorted bin 。释放操作类似于small bin ，如果条件满足，将会进行合并。
除了以上类型的chunk ，还有mmaped chunk和top chunk：
mmaped chunk用于分配非常大的内存块（大于默认的分配阈值，通常为128K）。在释放mmaped chunk上的内存时，会直接返回给操作系统。
top chunk相当于分配区的顶部空闲内存，当bins上无法满足内存分配要求且小于mmap分配阈值时，就会使用top chunk来分配。如果top chunk的大小比用户请求的大小大，会将其切割为两部分：User chunk（用户请求大小）和Remainder chunk（剩余大小）。其中Remainder chunk成为新的top chunk 。当top chunk大小小于用户所请求的大小时， top chunk就通过sbrk（主分配区）或mmap（非主分配区）系统调用来扩容。
last remainder是一种特殊的chunk ，类似于top chunk和mmaped chunk ，它不会出现在任何bins中。当需要分配一个small chunk ，但在small bins中找不到合适的chunk ，如果last remainder chunk的大小大于所需的small chunk大小， last remainder chunk被分裂成两个chunk ，其中一个chunk返回给用户，另一个chunk变成新的last remainder chuk 。
3.2 内存分配ptmalloc的内存申请过程其实是：获取arena并加锁–> fast bin –> unsorted bin –> small bin –> large bin –> top chunk –> 扩展堆的过程，详细流程如下：