企业官网建设流程全解析

目录

前置知识——内存布局

申请堆/共享区的系统调用

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，失败返回0；
• sbrk（）的参数为申请内存的大小，返回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”，那么p+sizeof（malloc_chunk）就是返回给用户的空间指针。而假设我们有了用户空间指针“q”，(malloc_chunk*)(q -sizeof（malloc_chunk))就是这个内存块的管理结构。

• prev_size表示与这个内存块紧挨着的上一个空闲内存块的大小，以此可以找到上一个内存块的地址，进行前向内存合并。

• size就是本内存块的大小（包括malloc_chunk管理结构和用户数据区），除了描述本内存块大小之外，也可以通过它找到紧挨着本内存块的下一个内存块，进行后向内存合并。

• A、M、P是三个标记位，P标记位表示紧挨着的上一个内存块是否空闲，如果空闲prev_size才有效。剩下两个标记位我们之后介绍。需要注意的是，这三个标记位是依靠size的低三个bit位实现的，并不单独使用空间。

• 所有空闲的内存块是通过链表管理起来的，fd，bk分别指向链表中的上一个、下一个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的内存块时，我们只需要在空闲链表中找到一个大小为 [32B+size的大小+prevsize的大小] 的内存块而不是 [32B+size的大小+prevsize的大小+bk的大小+fk的大小+... ...]。
• 假设两个内存块A，B是紧挨着的内存块，一但A被用户拿走使用，B的P标志位被置0（表示A不是空闲状态），那么B的prev_size就不可以被访问了，只要A不被返还，B的prev_size就绝不会被访问，这样一说，实际上，prevsize也可以被A纳入进去充当用户空间使用，毕竟闲着也是闲着，这样又进一步节省了空间。具体来说，当用户申请32B的内存时，我们只需要找一个大小为 [32B+size的大小+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 chunk

ptmalloc作为一个内存分配器能管理的内存块的大小总是有限的，当用户申请的内存超出了ptmalloc所能管理的极限，就会直接向系统申请内存，申请下来的内存同样被malloc_chunk管理，只不过这个malloc_chunk的M标志位为1，表示这个内存是直接向系统申请的而没有经过ptmalloc的申请流程，当释放内存的时候，一旦检测到这个内存块被标记为M，就会直接调用unmmap释放这个内存而不走ptmalloc的释放流程。本质上，ptmalloc给超大内存块的申请释放开了特殊通道。M标记位为1的chunk被称为mmaped chunk。

下一个数据结构是最后一种具有特殊意义的malloc_chunk——laster mainder chunk

last remainder chunk 出现在申请内存的过程中，假设申请内存过程中满足了如下条件，那么该chunk自动被设置为laster remainder chunk（会有一个指针指向这个chunk，这个指针指向的chunk总是laster remainder chunk）：

1. 请求大小在small bin范围内（64位系统下通常为小于1024字节）且smal lbin中没有相应内存块。

2. unsorted bin中只有一个空闲 chunk。

3. 这个 chunk 的剩余大小，足够被切割（即其大小 > 请求大小 + 最小 chunk 大小MINSIZE）。

假设申请内存的过程中满足了如下条件，那么该次内存分配自动通过切割laster remain chunk实现：

1. 请求大小在small bin范围内（64位系统下通常为小于1024字节）且smal lbin中没有相应内存块。

2. unsorted bin中只有一个空闲 chunk，并且这个chunk是last remainder chunk。

3. 这个 chunk 的剩余大小，足够被切割（即其大小 > 请求大小 + 最小 chunk 大小MINSIZE）。

last remainder chunk是ptmalloc（glibc 的malloc实现）为提升内存分配局部性而设计的特殊缓存机制。比如说连续申请多个小块内存空间，那么他们如果来自同一个内存块切割就满足局部性原理，提高效率。

下一种数据结构是malloc_state，他相当于一个关于内存申请释放的总管家，用户只会向它申请内存，我们之前介绍的top cuhnk指针，last remainder chunk指针、fastbinY，bins都被这个数据结构存放、管理、使用

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指向自己的分配区。但是，线程释放的内存块实际上不一定是本线程申请的内存块，因为线程之间资源共享；而且线程自己也不一定只在一个分配区找内存块。所以，释放内存块有两个步骤：

1. 查看内存块的A标记位，如果A为1说明该内存块从主分配区申请，直接释放到主分配区即可，否则进入下一步
2. 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（小空闲块，≤1024B）

• 1. 判断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中移出，放入对应bin：

    • smallbin：插入对应链表的首部

    • largebin：按块大小降序插入对应链表

  • → 取下一个块，重复本步骤；遍历完毕后，进入下一步

第四步：查找largebin（大空闲块，>1024B）

• 1. 判断req_size是否大于等于1024B（属于largebin范围）：

  • → 是：计算req_size在largebin中的索引，遍历该链表查找合适的内存块：

    • → 找到合适块：

      • 块大小 ≥ req_size + 32B：分裂该块，返回req_size大小的块，剩余部分放入unsorted bin，流程结束

      • 块大小< req_size + 32B：直接返回整个块，流程结束

    • → 未找到合适块：进入下一步（跨尺寸查找更大bin）

  • → 否：直接进入下一步（跨尺寸查找更大bin）

第五步：跨尺寸查找（所有bin中找更大空闲块）

• 1. 从当前bin索引开始，向后遍历，依次查找更大尺寸的bin（从smallbin到largebin）

• 2. 判断是否找到合适的大块内存：

  • → 找到：

    • 块大小 ≥ req_size + 32B：分裂该块，返回req_size大小的块，剩余部分放入unsorted bin并设为last remainder，流程结束

    • 块大小 < req_size + 32B：直接返回整个块，流程结束

  • → 未找到：所有bin均无可用空闲块，进入下一步（使用top chunk）

第六步：使用top chunk（最终分配手段）

• 1. 判断top chunk（arena顶端备用空闲块）大小是否 ≥ req_size + 32B：

  • → 是：分裂top chunk，返回req_size大小的块，剩余部分作为新的top chunk，流程结束

  • → 否：判断fastbin是否非空：

    • → 是：合并fastbin中的所有内存块，重新回到第三步（整理unsorted bin），重新执行流程

    • → 否：向操作系统申请新的内存，扩容top chunk（或开辟新的top chunk），完成分配，流程结束

流程概览（重点）

1. 实际上第一二三四步都是在尝试精确匹配，而第五六步就是在实施保底手段（分裂或再申请），分裂和再申请都是逼不得已的，因为前者增加内存碎片，后者比较浪费时间。
2. 每次申请几乎都会对unsorted bin中的内存块进行遍历合并操作，缓解内存碎片问题。而fastbin的合并操作是在逼不得已才进行的，因为fasbin的目的就是用内存碎片来换取小块内存申请释放的极致速度。
3. 判断时用req_size+32B而不是直接用req_size是因为要保证切割后的内存块仍旧能够被管理起来，这就要求剩余的内存块要符合最小管理大小或者最起码要能存的下malloc_chunk的管理内容。

ptmalloc释放内存大致流程

1. 获取大小
   通过被释放内存块的头部信息，取得该块的实际尺寸，记为fsz。

2. fastbin 路径（fsz≤global_max_fast）

   • 检查该块在堆上紧邻的下一个块是不是 top chunk。

     • 是：将该块与 top chunk 合并，把 top 指针 指向本块，形成一个更大的 top chunk，流程结束。

     • 否：计算fsz对应的 fastbin 索引，将该块插入对应 fastbin 链表的首部（LIFO），流程结束。

3. 非 fastbin 路径（fsz>global_max_fast）

   • 检查该块紧邻的下一个块是不是 top chunk。

     • 是：将该块与 top chunk 合并，更新 top 指针，流程结束。

     • 否：进入步骤 4。

4. 相邻空闲块合并

   • 通过头部标志检查与该块在堆空间上前后相邻的块是否空闲。

   • 若前一个块空闲，则将其从所属 bin 中取出（unlink），并与当前块合并。

   • 若后一个块空闲，同样取出并合并。

   • 合并后的大空闲块仍然记为p，然后将其放入 unsorted bin 链表（头部）。

5. 触发 fastbin 全局合并（可选）

   • 如果步骤 4 合并后的空闲块大小 ≥FASTBIN_CONSOLIDATION_THRESHOLD（如 64 KB），则遍历 fastbin 中所有的 chunk：

     • 逐一检查它们在堆空间的邻居，合并那些相邻的空闲块；

     • 将所有经过合并的新空闲块统一移入 unsorted bin。

流程概览

1. 整个释放流程中，能并入top chunk的内存就会并入，这个操作的优先级很高（好处当然就是可以触发归还系统内存，减少内存占用，并且让top chunk提高承担大内存块分配的能力。至于坏处，比如说本来能进fastbin现在不进去了等等，这是一种权衡吧）。
2. 释放的内存块合并成较大内存块代表空闲内存块比较多了，所以可能会触发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。