内存碎片深度剖析
目录
什么是内存碎片
内部碎片的解决
malloc
STL二级空间配置器
外部碎片的解决
伙伴系统算法
slab分配器
什么是内存碎片
内存碎片是指在内存中存在的一些不连续的、较小的空闲内存块，这些小块内存由于太小而无法被有效地分配给程序使用，从而导致内存空间的浪费。
内存碎片可以分为两种：内部碎片与外部碎片。简单来说，内部碎片是程序内部产生的内存碎片，外部碎片是未分配给程序的内存中存在的内存碎片。
外部碎片：
内部碎片：
内部碎片的解决
内部碎片实际上是无法被完全解决的，因为操作系统以页（4KB）为单位分配内存，当程序请求的内存大小不是页大小的整数倍时，就会有部分内存被浪费，这部分浪费的内存就是内部碎片。
例如，一个程序请求分配 3KB 的内存，系统会为其分配一个 4KB 的页，那么就有 1KB 的内存被浪费了，这 1KB 就是内部碎片。由于程序对内存的需求大小各异，很难保证每次分配的内存都能刚好被完全利用，所以内部碎片在这种固定粒度的分配方式下是不可避免的。
虽然内部碎片无法完全解决，但可以通过一些方法来尽量减少其影响。这里以C++/C语言为例，介绍malloc与stl是如何减少内存碎片的。
malloc
在介绍malloc对内存碎片的优化时，我们需要简单了解malloc是如何进行内存分配的（实际上malloc有多个版本，每个版本有不同的实现方法，本文介绍的分配方法是极大简化了的）。
malloc实际上是在程序内部维护了一个内存池，在程序启动或者首次调用 malloc 时，会向操作系统一次性申请一块较大的内存区域，这块区域就是内存池。
在程序运行过程中，随着内存的分配与释放，会出现不连续的空闲区域，malloc会在这个内存池内部进行管理，记录哪些内存块是已分配的，哪些是空闲的。通常采用的是隐式链表法
内存块（包括已分配和空闲的）的结构类似于链表，它们之间通过指针连接在一起。在实际应用中，一个内存块的结构如下图所示：
每个内存块除了包含用户数据外，还包含一些元数据，如块的大小、是否已分配等信息。同时还有一个指针指向下一个内存块，通过这样的操作，空闲的内存块与已使用的内存块实现了逻辑上的连续：
当程序调用malloc请求分配内存时,malloc会先从内存池中查找合适大小的空闲内存块进行分配，而不是每次都向操作系统发起新的内存分配请求。
malloc会使用某种搜索算法来查找合适的空闲内存块。常见的算法有首次适配算法、最佳适配算法和最差适配算法等。
- 首次适配算法
- 原理：从空闲内存块链表的头部开始遍历，依次检查每个空闲块，找到第一个大小大于等于请求内存大小的空闲块，就将其分配给程序。
- 优点：实现简单，分配速度快。当有新的内存分配请求时，只要从链表头部开始查找，很快就能找到合适的空闲块进行分配，不需要遍历整个链表。
- 缺点：容易产生内存碎片。由于总是优先使用链表头部的空闲块，随着时间的推移，链表头部的空闲块会被不断分割，导致小的空闲块越来越多，而后面较大的空闲块却得不到充分利用。
- 最佳适配算法
- 原理：遍历整个空闲内存块链表，找到大小最接近请求内存大小的空闲块进行分配。这样可以尽量减少内存碎片，因为分配后剩余的空闲块大小相对较小，更不容易被再次分配，从而减少了内存碎片的产生。
- 优点：能有效利用内存空间，减少内存碎片的产生。通过选择最接近请求大小的空闲块，可以使每次分配后剩余的空闲块尽可能小，提高了内存的利用率。
- 缺点：搜索成本高，分配速度慢。为了找到最佳适配的空闲块，需要遍历整个链表，比较每个空闲块的大小与请求大小的差值，这在链表较长时会消耗大量的时间。
- 最差适配算法
- 原理：选择空闲内存块链表中最大的空闲块进行分配。其思路是，优先使用大的空闲块，这样可以避免产生过多的小碎片，因为大的空闲块在分配后剩余的部分仍然可能是较大的空闲块，还能继续满足其他较大的内存分配请求。
- 优点：实现相对简单，且能避免产生过多的小碎片。与首次适配算法相比，它不会优先分割小的空闲块，而是先使用大的空闲块，所以在一定程度上可以减少内存碎片的数量。
- 缺点：可能会很快耗尽大的内存块。由于总是优先选择最大的空闲块进行分配，当有连续的较大内存分配请求时，大的空闲块会被迅速耗尽，导致后续较大的内存分配请求可能无法得到满足，即使此时内存中存在一些小的空闲块，但它们的总和无法满足大的请求。
如果内存池中的内存不足，malloc就会向操作系统申请内存，malloc会调用 brk/mmap 申请内存：
brk系统调用
- brk用于将进程的数据段（堆）的边界向上扩展（增加）或向下收缩（减少）。它通过设置进程的break指针来实现内存的分配和释放。当调用brk时，内核会调整break指针的位置，将堆空间扩大或缩小。如果是扩大堆空间，新分配的内存就在原来堆的顶部连续增加；如果是缩小堆空间，内核会释放break指针以下的部分内存。
mmap系统调用
- mmap用于将一个文件或设备的内存区域映射到进程的虚拟地址空间中。它可以将磁盘文件的内容直接映射到进程的地址空间，使得进程可以像访问内存一样访问文件内容，也可以用于分配匿名内存（即不与任何文件关联的内存）。当使用mmap分配内存时，内核会在进程的虚拟地址空间中找到一段合适的空闲区域，并将其与物理内存建立映射关系。
在申请空间大于 128 KB的内存时，malloc会调用mmap。而在申请小于128KB的内存时，malloc会调用 brk。 为什么这么设计？
首先我们需要了解malloc的内存归还机制，当我们调用free时，会将归还的内存块标记未空闲。同时将空闲块加入空闲链表，并检查附近是否有可合并的空闲内存。
当我们释放A内存块会经历以下过程：
将A标记为空闲块：
将A加入空闲链表：
合并附近空闲内存块：
我们释放的内存并不直接归还给操作系统，而是继续存在在内存池中，同时malloc还会尝试合并空闲内存块，通过这样的操作减少内存碎片的生成。
而当malloc要将内存归还给操作系统时，也是通过 brk 调用，设置堆的break指针。缩小堆的大小，从而归还堆的内存。
不难看出，当malloc归还内存时，只能归还堆顶的空闲内存。那么我们模拟一下，当malloc申请大内存时也使用 brk 会发生什么：
malloc使用brk申请 200KB 内存：
此时再次申请内存块A：
用户释放200KB内存块：
而此时，当malloc要归还 200KB 内存块给操作系统时会发现，由于内存块 A 非空闲，所以无法归还 200KB 内存块，而随着后续的内存分配与释放，这 200 KB 的内存块会变的 “支离破碎” ，此时完整的大块内存就会产生大量内存碎片。
为了规避这种现象的产生，所以malloc在申请大内存分配时，不使用brk。不在堆上分配内存。而是使用 mmap，在用户释放后可以“整取整还”。
STL二级空间配置器
STL 重载了 new 运算符，在 new 中 STL 用二级空间配置器来分配内存。在STL二级空间分配器中，分为两种内存分配模式：
- 第一级空间配置器：直接使用 malloc/free 分配内存。
- 第二级空间配置器：当要分配内存大于 128 字节由第一级空间分配器分配。当要分配内存小于 128 字节，从内存池中分配。
第二级空间配置器分为两部分：空闲链表（free_list）与内存池。
第二级空间配置器会维护 16 个空闲链表，每个链表对应一种固定大小的内存块，这些内存块的大小以 8 字节为单位递增，从 8 字节到 128 字节。每个空闲链表由一系列的内存块节点构成，这些节点通过指针相互连接，形成一个单向链表。
当需要分配小于等于 128 字节的内存时，二级空间配置器会执行以下步骤：
- 查找合适的空闲链表：根据所需分配的内存大小，计算出对应的空闲链表编号。例如，若要分配 20 字节的内存，会将其调整为 24 字节（8 的倍数），然后找到对应 24 字节的空闲链表。
- 检查空闲链表是否为空：
- 不为空：从链表头部取出一个节点，将其从链表中移除，然后返回该节点的地址给用户。
- 为空：调用 refill 函数重新填充该空闲链表。refill 函数会调用 chunk_alloc 从内存池分配一大块内存，接着将其分割成多个小块，插入到空闲链表中，最后返回其中一个小块给用户。
refill 与 chunk_alloc 都用于向内存池申请内存，refill 函数的主要步骤如下：
- 调用 chunk_alloc 分配内存：尝试从内存池分配一定数量（通常为 20 个）的指定大小的内存块。
- 分割内存块：将分配到的大块内存分割成多个小块。
- 插入空闲链表：把除第一个小块之外的其他小块插入到对应的空闲链表中，第一个小块返回给用户。
chunk_alloc 函数负责从内存池分配内存，其主要步骤如下：
- 检查内存池剩余空间：
- 足够：直接从内存池分配所需数量的内存块。
- 部分足够：分配尽可能多的内存块，调整剩余空间。
- 不足：尝试从堆中分配更多内存，更新内存池的起始和结束指针。如果堆内存不足，会尝试从其他空闲链表中寻找可用的内存块。
而当归还内存时，二级空间配置器会执行以下步骤：
- 查找合适的空闲链表：根据释放的内存块大小，找到对应的空闲链表。
- 将内存块插入链表头部：把释放的内存块转换为空闲内存块类型，将其空闲链表头指针指向当前链表头部，然后更新链表头部指针为该内存块。
STL二级空间配置器通过借助空闲链表高效管理小内存块的分配与回收。将不同大小的内存块分类存储在不同的空闲链表中，避免了频繁的系统调用，减少了内存碎片，提高了内存分配的效率。
外部碎片的解决
外部碎片主要由操作系统的物理内存管理算法解决。对于物理内存的管理，Liunx采用伙伴系统算法管理物理页。
伙伴系统算法
Linux系统会以页为单位分配物理内存，并通过伙伴系统算法管理内存块。具体来说，Linux维护了12个空闲块链表，链表中记录了所有空闲的物理页。
每个链表对应不同大小的内存块，按照内存块大小从小到大排序。比如 list[0]存储的每个内存块大小为2^0个页， list[1]存储的每个内存块大小为2^1个页，以此类推。
分配内存时，操作系统会根据请求物理内存大小，计算出需要的最小页数，并找到对应的空闲链表索引。例如，如果请求的内存大小为 16KB，而页框大小为 4KB，则需要 4 个页框，对应的索引为 2。
在查找到对应的空闲链表后，操作系统会从对应的空闲链表中查找是否有空闲的内存块。如果链表不为空，则直接从链表中取出一个空闲内存块进行分配，并更新相关的状态信息。
如果对应的空闲链表为空，则需要从更大的内存块中进行分裂。从下一个更大的空闲链表中查找空闲块，找到后将其分裂成两个相等的子块，一个子块用于满足当前分配请求，另一个子块放入相应大小的空闲链表中。这两个内存块就互为伙伴块。
如果下一个更大的空闲链表也为空，则继续向上查找，直到找到一个有空闲块的链表或者到达最大的内存块链表。如果到达最大的内存块链表仍无法满足请求，则表示内存不足，分配失败。
当进程释放内存时，首先将释放的内存块对应的内存描述符中的状态标记为空闲，并将其引用计数减 1。如果引用计数变为 0，则表示该内存块可以被回收。
操作系统会根据释放的内存块的地址和大小，计算出其伙伴内存块的地址。伙伴内存块是指在内存分配过程中与当前内存块一起被分裂出来的另一个内存块，它们具有相同的大小且地址相邻。
如果伙伴是空闲的，则将它们合并成一个更大的内存块，并将合并后的内存块放入相应大小的空闲链表中。然后继续检查合并后的内存块的伙伴是否空闲，重复合并过程，直到无法合并为止。如果伙伴内存块正在被使用，则将释放的内存块直接放入其所属大小的空闲链表中。
通过这样的设计，伙伴系统能够快速地找到合适的内存块进行分配，并且在内存回收时能够有效地合并相邻的空闲内存块，减少内存碎片的产生，提高内存的利用率。同时还可以满足各种不同大小的内存分配请求，无论是小的页级分配还是大的连续内存区域分配，都能够在一定程度上高效地处理。
slab分配器
在页的尺度上，Linux通过伙伴系统防止内存碎片化。而在更细粒度上，伙伴系统就无能为力了。在页内，Linux通过slab分配器减少内存碎片的产生。
slab 分配器是一种用于管理内存中较小对象的内存分配机制。slab 分配器的核心思想是将内核中经常使用的对象放到 slab 缓存中，并保持这些对象处于可利用状态。当需要分配内存时，直接从 slab 缓存中获取对象，而不是每次都从伙伴系统中申请内存页。
slab 分配器主要由缓存、slab 和对象等结构组成。slab 分配器为不同类型的对象建立了专门的缓存。每个缓存都由多个 slab 组成，每个 slab 包含了若干个大小固定的对象。例如，对于经常使用的文件描述符结构体，会有一个对应的缓存，其中的 slab 专门用来存放这种结构体对象。
- 缓存（Cache）：缓存是 slab 分配器中管理特定类型对象的结构。系统为不同类型的对象（如进程控制块、文件描述符结构体等）分别创建不同的缓存。缓存中包含了多个 slab，用于存储同一类型的对象。它提供了对这些对象的快速分配和释放功能，通过维护空闲对象链表和已分配对象链表等数据结构，实现对对象的有效管理，避免了频繁地在内存中查找和分配小内存块，提高了内存分配效率，减少了内存碎片。
- slab：slab 是由连续的内存页组成的区域，它是缓存的基本组成单位。每个 slab 包含了若干个大小固定的对象。slab 在内存管理中起到了承上启下的作用。它将较大的内存空间划分为多个固定大小的对象，供缓存进行分配和管理。当缓存需要分配一个对象时，会从某个 slab 中取出一个空闲对象；当对象被释放时，也会被放回对应的 slab 中。同时，slab 还记录了自身的状态信息，如已分配对象的数量、空闲对象的指针等，以便缓存对其进行管理。
- 对象：对象是 slab 分配器分配和管理的基本单元，是实际被内核或应用程序使用的数据结构。不同类型的对象具有不同的大小和用途，例如进程控制块对象用于存储进程的相关信息，文件描述符对象用于管理文件的打开、读写等操作。对象是内存分配的最终目标，内核中的各种模块和应用程序通过请求分配对象来获得内存空间，以存储和操作相关的数据。对象在创建后会被初始化为特定的状态，然后被使用，使用完毕后被释放回 slab 分配器，以便重复利用。
slab 主要有以下三种状态类型：
- 满（Full）的 slab ：此状态下 slab 中的所有对象都被标记为使用中，不存在空闲对象 。例如，当一个 slab 中所有用于存放进程描述符结构体的空间都被占用时，该 slab 就是满状态 。
- 空（Empty）的 slab ：该 slab 中的所有对象均标记为空闲，没有被分配使用 。像刚刚创建好还未分配对象，或者之前对象都被释放完的 slab，就处于空状态 。
- 部分（Partial）的 slab ：slab 内部分对象被标记为使用，部分对象标记为空闲 。比如一个 slab 有 10 个对象空间，其中 6 个已被分配，4 个空闲，此时它就是部分状态 。
在 Linux 内核中，slab 分配器被广泛用于分配各种内核对象，如进程控制块（PCB）、文件描述符结构体、内存页结构体等。这些对象大小相对固定且频繁地被创建和销毁，非常适合使用 slab 分配器进行管理。
当内核申请一个对象会经历以下流程：
- 查找空闲对象：当内核模块请求分配一个对象时，slab 分配器首先依据对象类型找到对应的缓存。接着在该缓存里查找是否存在空闲对象。这是因为 slab 分配器为不同类型对象分别设置缓存，缓存内有多个 slab，每个 slab 又包含若干对象，所以能快速定位。
- 分配新 slab：若缓存中无空闲对象，分配器会查看有无空闲的 slab。若有，从该 slab 中取出一个对象分配给请求者；若没有，slab 分配器就向内存申请分配一个新的 slab 。新 slab 通常由连续内存页组成，会按对象大小划分成若干个固定大小的对象空间。
- 返回对象：从空闲对象、现有空闲 slab 或新分配的 slab 中获取对象后，将其分配给请求的内核模块，并将对象标记为已分配状态。
对象释放的流程如下：
- 标记空闲：当对象使用完毕被释放时，slab 分配器将其标记为空闲状态 ，并把对象放回所属缓存的 slab 中。
- 检查 slab 状态：释放对象后，检查该 slab 的空闲对象数量。若一个 slab 中的所有对象都变为空闲状态，那么这个 slab 会被标记为空闲 。空闲的 slab 可能会被后续对象分配操作重新利用，或者在特定情况下（如内存紧张时）被释放回内存池。
简单总结一下 slab 分配器解决内存碎片的思想是：预先在连续内存上构建对象缓存，将其分割成固定大小的对象单元。针对内核中频繁分配与释放的小对象，从缓存中直接分配与回收，避免在内存中零散分配和释放小内存块，减少外部碎片；固定大小的对象分配方式，规避因按需分配导致的内存空间切割，降低内部碎片。同时，释放的对象复用回原缓存，减少内存频繁分配回收操作，让内存空间更规整 。