目录前置知识——内存布局申请堆/共享区的系统调用brk() 和 sbrk()mmap()ptmalloc中的核心数据结构ptmalloc申请内存大致流程初始步骤第一步查找fastbin快速小空闲块第二步查找smallbin小空闲块≤1024B第三步整理unsorted bin混合空闲块核心步骤第四步查找largebin大空闲块1024B第五步跨尺寸查找所有bin中找更大空闲块第六步使用top chunk最终分配手段流程概览重点ptmalloc释放内存大致流程流程概览全局概览bins和top chunk的作用前置知识——内存布局从上图可以看到栈至顶向下扩展堆至底向上扩展 mmap 映射区域至顶向下扩展。mmap 映射区域和堆相对扩展直至耗尽虚拟地址空间中的剩余区域。申请堆/共享区的系统调用brk() 和 sbrk()#include unistd.h int brk( const void *addr ) void* sbrk ( intptr_t incr );两者的作用都是扩展堆空间brk 的参数代表新的brk上界地址成功返回1失败返回0sbrk的参数为申请内存的大小返回heap新的上界brk的地址;mmap()#include sys/mman.h void *mmap(void *addr, size\_t length, int prot, int flags, int fd, off\_t offset); int munmap(void *addr, size_t length);mmap有两种用法一种是映射文件内容到虚拟地址空间另一种是mmap向共享区申请一块内存空间ptmalloc用的是第二种。Munmap函数用于释放内存。ptmalloc中的核心数据结构第一种数据结构也是ptmalloc的基石malloc_chunk,它是一个内存块的管理结构ptmalloc依靠它标识管理维护一个特定的内存块首先读者要搞明白上面所示的结构图就是一个完整的被管理的内存块而malloc_chunk是位于内存块开头的一个数据结构也包含在内存块中。什么意思呢如果我们有了malloc_chunk类型的指针“p”那么psizeofmalloc_chunk就是返回给用户的空间指针。而假设我们有了用户空间指针“q”(malloc_chunk*)(q -sizeofmalloc_chunk))就是这个内存块的管理结构。prev_size表示与这个内存块紧挨着的上一个空闲内存块的大小以此可以找到上一个内存块的地址进行前向内存合并。size就是本内存块的大小包括malloc_chunk管理结构和用户数据区除了描述本内存块大小之外也可以通过它找到紧挨着本内存块的下一个内存块进行后向内存合并。A、M、P是三个标记位P标记位表示紧挨着的上一个内存块是否空闲如果空闲prev_size才有效。剩下两个标记位我们之后介绍。需要注意的是这三个标记位是依靠size的低三个bit位实现的并不单独使用空间。所有空闲的内存块是通过链表管理起来的fdbk分别指向链表中的上一个、下一个malloc_chunk。fd_nextsize、bk_nextsize也是两个指向malloc_chunk的指针它们主要指用于优化查找空闲块的效率。考虑这么一种情况在一个链表中包含不同大小的内存块它们按照升序排列fd_nextsize、bk_nextsize分别指向上一个、下一个与当前内存块大小不一样的内存块用以快速跳过重复内存块优化查找效率。user_data就是留给用户存放内容的空间上面一个较为完整的malloc_chunk示意图而实际上我们还要知道下面几点一个空闲的内存块一定有prev_size、size、fd、bk四个字段但是不一定有fd_nextsize、bk_nextsize他两的用途我上面介绍过但如果这个链表只包含一种大小的内存块这两个字段当然就没用了fd、bk、fd_nextsize、bk_nextsize都是内存块空闲的时候所用的变量但是一但内存块被分配给用户这些变量就都没用了但是size和prevsize得保留释放内存时有用。具体来说当用户想要一个32B的内存块时我们只需要在空闲链表中找到一个大小为 [32Bsize的大小prevsize的大小] 的内存块而不是 [32Bsize的大小prevsize的大小bk的大小fk的大小... ...]。假设两个内存块AB是紧挨着的内存块一但A被用户拿走使用B的P标志位被置0表示A不是空闲状态那么B的prev_size就不可以被访问了只要A不被返还B的prev_size就绝不会被访问这样一说实际上prevsize也可以被A纳入进去充当用户空间使用毕竟闲着也是闲着这样又进一步节省了空间。具体来说当用户申请32B的内存时我们只需要找一个大小为 [32Bsize的大小prevsize的大小 - prevsize的大小]的内存块。总之prev_size可以有两种用途。下一种数据结构是fastbinY用以组织空闲块没错fastbinY就是一个能存放多个mallo_chunk单链表不是双链表哦所以它只用了bk字段的哈系桶每个slot代表不同的内存块大小同一个单链表上的内存块的大小相同。fastbinY只组织小块内存块并且ptmalloc规定只要在fastbinY中的内存块其P标志位永远是0表示正在使用这听起来有些反直觉因为内存块本身就空闲为什么还要给他标记不空闲实际上这是为了防止被管理在其他位置的内存块进行内存合并的时候把fastbinY中的内存块也合并了毕竟ptmalloc中的内存合并是查找紧挨本内存块的邻居内存块而并非是遍历特定的管理结构实现所以可能会出现跨数据结构合并内存的现象。那么问题又来了为什么不让它合并一句话解释程序申请的90%的内存都是小块内存所以ptmalloc针对这种小块内存的申请做出了优化从而提高效率优化方式就是维护一个fastbinY它管理小内存块并且不让他们合并这样一来malloc一个小内存块不用切割就能直接拿走free一个小内存块就直接放到fastbinY中不进行合并以供下次使用。本质上这是ptmalloc牺牲空间内存碎片增加换取时间极致的申请释放速度。当然小块内存如果永远不合并内存碎片会越来越多因此在合适的时机fastbinY也会被统一清理出去并进行内存合并。正是因为fasbinY中的内存块不合并所以不会涉及链表中间节点的删除操作因此不用使用双链表。下一种数据结构是bins他也用于组织空闲块,不同于fastbinY这种生于优化的内存块管理结构bins是管理内存块的中坚力量bins同样是一个管理malloc_chunk链表的哈系桶。但每个slot里面都是一个双链表哦因为内存的合并方式会涉及到中间节点的拆除。small bins范围的slot存放中小型内存块每个slot存放的内存块大小之间相差固定的字节数比如第一个slot存放32B的内存块第二个就存放40B的内存块第三个就存放48B的内存块... ...large bins范围的slot存放大型内存块。不过需要注意的是因为大内存块的类型太多了直接像small bins一样让每个slot存放的内存块大小相差固定字节的话需要太多的slot浪费空间large bin中的存放规则是这样的unsorted bin中存放的内存块没有大小限制可以是任何大小的内存块它就相当于一个缓冲区下面读者会对其有更多了解。实际上bins中的每个bin都是数组中的两个位置抽象出来的而不是一个当然这不是重点想要了解的话可以参考深入理解ptmalloc的运作机制一文。下一个数据结构是一种具有特殊意义的malloc_chunk——top chunk为了提升性能尽管或许用户暂时申请的内存比较少我们也会开辟出大块的内存留待后用。在ptmalloc中已申请已使用过的空闲内存块是被bin管理起来的而已申请却从未被使用过的内存是由top chunk来维护的top chunk不在任何bin中而是被单独拎出来会有一个指针指向它ptmalloc通过这个指针访问它。如果bin中找不到合适的内存块就会去切割top chunk的一部分进行使用剩余的部分继续做top chunk如果top chunk内存不够就会扩容不管是调用brk还是mmap最后top chunk都会指向管理已申请未被使用的内存块除此之外一些被释放的内存如果能与top chunk合并就合并合并后可以缩小top chunk即把申请了的内存归还给系统。以下是示意图下一个数据结构是另一种具有特殊意义的malloc_chunk——mmaped chunkptmalloc作为一个内存分配器能管理的内存块的大小总是有限的当用户申请的内存超出了ptmalloc所能管理的极限就会直接向系统申请内存申请下来的内存同样被malloc_chunk管理只不过这个malloc_chunk的M标志位为1表示这个内存是直接向系统申请的而没有经过ptmalloc的申请流程当释放内存的时候一旦检测到这个内存块被标记为M就会直接调用unmmap释放这个内存而不走ptmalloc的释放流程。本质上ptmalloc给超大内存块的申请释放开了特殊通道。M标记位为1的chunk被称为mmaped chunk。下一个数据结构是最后一种具有特殊意义的malloc_chunk——laster mainder chunklast remainder chunk 出现在申请内存的过程中假设申请内存过程中满足了如下条件那么该chunk自动被设置为laster remainder chunk会有一个指针指向这个chunk这个指针指向的chunk总是laster remainder chunk请求大小在small bin范围内64位系统下通常为小于1024字节且smal lbin中没有相应内存块。unsorted bin中只有一个空闲 chunk。这个 chunk 的剩余大小足够被切割即其大小 请求大小 最小 chunk 大小MINSIZE。假设申请内存的过程中满足了如下条件那么该次内存分配自动通过切割laster remain chunk实现请求大小在small bin范围内64位系统下通常为小于1024字节且smal lbin中没有相应内存块。unsorted bin中只有一个空闲 chunk并且这个chunk是last remainder chunk。这个 chunk 的剩余大小足够被切割即其大小 请求大小 最小 chunk 大小MINSIZE。last remainder chunk是ptmallocglibc 的malloc实现为提升内存分配局部性而设计的特殊缓存机制。比如说连续申请多个小块内存空间那么他们如果来自同一个内存块切割就满足局部性原理提高效率。下一种数据结构是malloc_state他相当于一个关于内存申请释放的总管家用户只会向它申请内存我们之前介绍的top cuhnk指针last remainder chunk指针、fastbinYbins都被这个数据结构存放、管理、使用malloc_state的示意图如下我们把上图中的一个系统叫做一个分配区每一个分配区有自己独立的内存块和管理结构各个分配区所管理的内存并不交叉。可以看出分配区是有两种的左边是主分配区直接把堆作为自己管理的内存块堆越大其管理的内存块越大同时也可以看到malloc_state不在其所管理的内存块中存储而是被定义成了全局区变量右边是非主分配区把共享区的内存块作为自己管理的内存块malloc_state被内嵌在其所管理的内存块中。如果非主分配区使用完了那么就会再向共享区申请一块大内存将其拼接到非主分配区上拼接方式就是用链表链接起来这也就是为什么要有一个heap_info结构。两个共享区内存块被一个mallloc_state管理。ptmalloc为了提高并发情况下的效率会尽量让所有的线程都私有一个分配区进行内存申请释放但是有上限从而缓解锁竞争所以ptmalloc不是只有一个malloc_state。主分配区只有一个因为主分配区与堆绑定而堆只有一个而非主分配区可以有很多个。一般来说第一个使用malloc的线程绑定主分配区而主线程就使用主分配区。因为pthread_create函数内部也会调用malloc这就意味着要创建子线程主线程一定会调用mallo从而绑定到主分配区上介绍一下整体布局首先malloc库内部定义了一个线程局部存储的malloc_state类型的指针变量假设它叫P这意味着每个线程都会有自己的P给线程绑定分配区就是让P指向一个malloc_state线程只会使用自己绑定的分配区进行内存的申请释放不会跨分配区否则就乱了也无法合并。所有的分配区包括主分配区被一个单向链表连接起来。当一个线程申请内存时发现P为NULL就会遍历分配区链表找到一个未加锁的分配区然后绑定如果一直没有找到就自己创建一个新的分配区并将其绑定and列入链表P不为NULL就会尝试对分配区加锁加锁成功就访问失败就遍历其他分配区尝试获取内存块并把本线程的P更新使其指向新的分配区。释放内存块的时候怎么知道应该释放到哪个分配区读者首先想到的就是释放到P指针指向的分配区毕竟每个线程释放的内存块一定是从这个线程申请的而每个线程都有P指向自己的分配区。但是线程释放的内存块实际上不一定是本线程申请的内存块因为线程之间资源共享而且线程自己也不一定只在一个分配区找内存块。所以释放内存块有两个步骤查看内存块的A标记位如果A为1说明该内存块从主分配区申请直接释放到主分配区即可否则进入下一步ptmalloc创建非主分配区有一个重要的规定就是他会想办法让非主分配区的首地址按照非主分配区的大小对齐。假设现在某分配区的地址是0x 00 11 00 00大小是2^16B那么可以预见这个分配区的所有内存地址上0x 11 11 00 00都会是0x 00 11 00 00即分配区的地址这样我们就可以通过位运算快速找到本内存块所属的非主分配区。具体如何做到可以 参考深入理解ptmalloc的运作机制一文。下面是各个分配区之间关系的示意图ptmalloc申请内存大致流程初始步骤1. 调用malloc函数2. 通过request2size宏对用户传入的分配大小进行对齐处理得到实际需要分配的req_size第一步查找fastbin快速小空闲块1. 计算req_size在fastbin中的索引fastbin_index(req_size)2. 判断该索引对应的fastbin链表是否非空→ 是取出链表首个内存块返回给用户流程结束→ 否不检查其他索引的fastbin直接进入下一步查找smallbin第二步查找smallbin小空闲块≤1024B1. 判断req_size是否小于1024B属于smallbin范围→ 是计算req_size在smallbin中的索引bin_index(req_size)判断该索引对应的链表是否非空→ 非空取出链表首个内存块返回给用户流程结束→ 空进入下一步整理unsorted bin→ 否直接进入下一步整理unsorted bin第三步整理unsorted bin混合空闲块核心步骤1. 遍历unsorted bin自动合并地址相邻的前后空闲块合并后从原对应bin中移除2. 判断是否满足last remainder优化条件条件unsorted bin中只有1个内存块 该块是last remainder 块大小 req_size 32B→ 满足从该块中分裂出req_size大小的块返回剩余部分继续作为last remainder流程结束→ 不满足进入下一步逐个遍历unsorted bin中的所有块3. 逐个取出unsorted bin中的内存块循环判断→ 块大小恰好等于req_size直接返回该块流程结束→ 块大小不匹配将该块从unsorted bin中移出放入对应binsmallbin插入对应链表的首部largebin按块大小降序插入对应链表→ 取下一个块重复本步骤遍历完毕后进入下一步第四步查找largebin大空闲块1024B1. 判断req_size是否大于等于1024B属于largebin范围→ 是计算req_size在largebin中的索引遍历该链表查找合适的内存块→ 找到合适块块大小 ≥ req_size 32B分裂该块返回req_size大小的块剩余部分放入unsorted bin流程结束块大小 req_size 32B直接返回整个块流程结束→ 未找到合适块进入下一步跨尺寸查找更大bin→ 否直接进入下一步跨尺寸查找更大bin第五步跨尺寸查找所有bin中找更大空闲块1. 从当前bin索引开始向后遍历依次查找更大尺寸的bin从smallbin到largebin2. 判断是否找到合适的大块内存→ 找到块大小 ≥ req_size 32B分裂该块返回req_size大小的块剩余部分放入unsorted bin并设为last remainder流程结束块大小 req_size 32B直接返回整个块流程结束→ 未找到所有bin均无可用空闲块进入下一步使用top chunk第六步使用top chunk最终分配手段1. 判断top chunkarena顶端备用空闲块大小是否 ≥ req_size 32B→ 是分裂top chunk返回req_size大小的块剩余部分作为新的top chunk流程结束→ 否判断fastbin是否非空→ 是合并fastbin中的所有内存块重新回到第三步整理unsorted bin重新执行流程→ 否向操作系统申请新的内存扩容top chunk或开辟新的top chunk完成分配流程结束流程概览重点实际上第一二三四步都是在尝试精确匹配而第五六步就是在实施保底手段分裂或再申请分裂和再申请都是逼不得已的因为前者增加内存碎片后者比较浪费时间。每次申请几乎都会对unsorted bin中的内存块进行遍历合并操作缓解内存碎片问题。而fastbin的合并操作是在逼不得已才进行的因为fasbin的目的就是用内存碎片来换取小块内存申请释放的极致速度。判断时用req_size32B而不是直接用req_size是因为要保证切割后的内存块仍旧能够被管理起来这就要求剩余的内存块要符合最小管理大小或者最起码要能存的下malloc_chunk的管理内容。ptmalloc释放内存大致流程获取大小通过被释放内存块的头部信息取得该块的实际尺寸记为fsz。fastbin 路径fsz≤global_max_fast检查该块在堆上紧邻的下一个块是不是 top chunk。是将该块与 top chunk 合并把 top 指针 指向本块形成一个更大的 top chunk流程结束。否计算fsz对应的 fastbin 索引将该块插入对应 fastbin 链表的首部LIFO流程结束。非 fastbin 路径fszglobal_max_fast检查该块紧邻的下一个块是不是 top chunk。是将该块与 top chunk 合并更新 top 指针流程结束。否进入步骤 4。相邻空闲块合并通过头部标志检查与该块在堆空间上前后相邻的块是否空闲。若前一个块空闲则将其从所属 bin 中取出unlink并与当前块合并。若后一个块空闲同样取出并合并。合并后的大空闲块仍然记为p然后将其放入 unsorted bin 链表头部。触发 fastbin 全局合并可选如果步骤 4 合并后的空闲块大小 ≥FASTBIN_CONSOLIDATION_THRESHOLD如 64 KB则遍历 fastbin 中所有的 chunk逐一检查它们在堆空间的邻居合并那些相邻的空闲块将所有经过合并的新空闲块统一移入 unsorted bin。流程概览整个释放流程中能并入top chunk的内存就会并入这个操作的优先级很高好处当然就是可以触发归还系统内存减少内存占用并且让top chunk提高承担大内存块分配的能力。至于坏处比如说本来能进fastbin现在不进去了等等这是一种权衡吧。释放的内存块合并成较大内存块代表空闲内存块比较多了所以可能会触发fastbin的合并逻辑全局概览bins和top chunk的作用一个程序申请的内存90%都是小块内存因此ptmalloc专门设计出fastbin来进行小块内存的快速申请释放。在fastbin中的内存块有这样一个特性就是它永远被标记为“正在使用”因此几乎所有内存合并的操作都不会牵扯到fastbin也正是因此fasbin是单链表因为不会涉及到中间节点的取出。至于为什么不合并这也很好理解fasbin本身就是为了服务于小块内存的快速申请释放如果每次都合并下次申请还得切割这影响了申请释放速度违背了fastbin的初衷当然这样会牺牲一些空间即造成更严重的内存碎片。fastbin存放的内存块范围一般是32B~128B。fastbin算是整个ptmalloc为了提高效率而做出的特例而其他的bin都是双向链表支持合并操作毕竟解决内存碎片问题是除了效率以外内存分配器第二重要的点。samllbin存放中小型内存块largebin存放大型内存块它们各自服务于不同的申请需求。不过需要注意的是因为大内存块的类型太多了直接每8个字节给一个slot空间消耗太大所以largebin中是处在同一个大小范围内的内存块用链表相连这样也就导致了同一个链表的内存块大小不一样影响查找效率。smallbin存放的内存块范围是32~1008B。largebin存放的内存块范围是1024B~128KB(不一定)unsortedbin相当于一个缓冲区它里面的内存块根本没有任何逻辑顺序。free时不能存放在fasbin中的内存块会被直接扔在unsortedbin中这样做有两个好处第一是内存块重复利用概率高不用再切割向下查找什么的第二是free函数调用比较快。上面介绍的所有bin其实就是存放并管理已切割或者分配出去的内存块的容器。而空闲Top chunk本质上就是储备资源是崭新的还未使用过的大块内存查找bins无果后就去找Top chunk。